Embedded Motion Control 2017 Group 5
This page contains the progress of the development of the PICO maze controller for the course 4SC020 Embedded Motion Control. The objective of the project is to design a controller for PICO, a small robot equipped with a holonomic base, wheel encoders and a laser range finder (LRF). This controller shall enable PICO to autonomously navigate through a random maze without bumping into walls. The designed system recieves data from the wheel encoders and the LRF and converts these to movement commands for the actuation of the base.
Members Group 5
| Name | Student ID | |
| Torben Beernaert | 0778690 | t.f.beernaert@student.tue.nl |
| Rodrigo Estrella Treviño | 1035228 | r.estrella.trevino@student.tue.nl |
| Kagan Incetan | 1037760 | k.incetan@student.tue.nl |
| Sjoerd Knippenberg | 0738104 | s.c.m.knippenberg@student.tue.nl |
| Angel Molina Acosta | 1036456 | a.molina.acosta@student.tue.nl |
| Bart Vercoulen | 0747283 | b.c.g.vercoulen@student.tue.nl |
Requirements
The requirements for the system are deducted from the course page and established from a brainstorm session. The FURPS model is used to group the requirements together in the following aspects:
- Functionality
- Usability
- Reliability
- Performance
- Supportability
A complete list of all requirements can be found in the requirements overview.
System Architecture
This section describes the development of the system architecture. First, the translation from the established requirements to functions the system should perform is covered. These functions are assigned to separate subsystems and the information flow between these subsystems is specified.
Functionality
From the requirements list several functionalities can be extracted, which are arranged using the Task-Skill-Motion hierarchy. In this hierarchy one main task, the most abstract and all-embracing functionality, is specified. In this case the main task is to exit the maze. To perform this task a combination of several subordinate functionalities, the skills, is necessary. Finally, the motions are one level deeper than the skills and contain basic functionalities.
Task
- Exit maze
Skills
- Observe environment
- Determine action
- Manoeuvre PICO
Motions
- Process sensor data
- Maintain world map
- Request open door
- Turn base
- Drive forward
The relationships between functionalities can be classified as "include" or "extend" types, which complete the hierarchy. An include relationship indicates that the functionality at the arrow tail is a necessary part of the arrow head function, while an extend relationship means that the arrow tail functionality can be a follow-up action of the one on the arrow head.
Subsystems
The previously introduced functionalities are grouped together to create the subsystems WorldMap, ActionManager and MovementController. Every subsystem will be responsible for executing any of these functionalities. The figure below shows that the main system is composed of these three subsystems and the functionalities they are mapped to:
Internal flows
Finally, the information flows between the subsystems are specified. The incoming sensor data is gathered in the WorldMap module, where it is converted to relevant information about the current situation and position of the robot. The situational information is then sent to the ActionManager, which will decide the upcoming action based on the situation (straight corridor / corner / T-junction etc.). The MovementController will then receive this command from the ActionManager and perform the manoeuvre using raw and processed position data provided by the WorldMap. The diagram below shows this flow of data through the system:
Initial Design
The Initial Design document can be found here: Initial_Design_Group5.
Maze-solving Algorithms
Wall follower
This algorithm is very simple to implement since only one rule applies: Follow the wall on either your left or right side (depending on the setting). This wall will be tracked until eventually, an exit is found. The algorithm is guaranteed to work when the robot starts at the entrance of a maze. However, if PICO starts at an arbitrary position it might get stuck in a loop, keeping track of the walls of an ‘island’. Since the case description states that the robot will be start from an arbitrary position and that the maze will contain a loop, this algorithm is risky to use and might not be able to guide the robot to the exit.
Pledge algorithm
The Pledge algorithm is very similar to the wall follower, but contains an upgrade to enable the robot to break free from isolated islands. The robot is given a preference direction (north, south, east or west) and follows this heading until it bumps into a wall. Then, an arbitrary (left or right) wall follower starts and keeps track of the orientation of the robot. This wall follower stops when the robot is heading towards the preference direction again and the orientation is zero degrees. Note that for this case, zero degrees is not equal to 360 degrees. Special care has to be taken when the maze is not made up of straight-angled corners, which is luckily not the case in this specific application. The Pledge algorithm is still fairly simple and guaranteed to find the exit of the maze.
Trémaux algorithm
The Trémaux algorithm is a more efficient, but also more complex algorithm. This algorithm keeps track of where PICO has already been by marking paths between junctions. When a junction is detected, a decision is made based on the markings that are already present on the other paths of the junction. The increased efficiency of the algorithm imposes more dependency on the detection of maze elements and maintenance of a world map.
World Skills
Filtering
To be able to process the laser data for detecting gaps, aligning or detecting doors, it is filtered first. Consecutive points have to be within a certain distance from each other, otherwise the points will be ignored. Furthermore this filtering is used to look at a certain bundle of beams between two specified angles. Also the maximum length of a beam can be specified. When a point is within these boundaries it is considered as a valid point. This valid point is than stored as a coordinate.
Struct coordinate{
x double;
y double;
orig_r double;
orig_angle double;
}
Alignment
Guiding PICO to the exit of a maze needs a proper alignment according to the walls. Since the obtained odometry data are not as precise as in the simulations, the robot is aligned after each 90 degrees turn that is made. Important to mention is that the first thing that PICO does when the controller software is started is aligning itself. This is done because the exact position and orientation of the robot in the maze is not known beforehand.
For determining the alignment with respect to walls of the maze, the laser beams of both the left- and right side of PICO are used. The ranges that are used for both sides are from XX to XX degrees on the left and from XX to XX degrees on the right, as shown in Figure filtering.
Using the Pythagorean theorem, the corresponding distance ‘d’ is calculated for each of the laser beams in the range, using its angle and length. When these distances are determined, the difference between the mean distance of the beams in front of PICO and the ones behind PICO are subtracted. The sign of the value that comes out of this comparison indicates the direction in which PICO has to turn for proper aligning with respect to the walls of the maze. For example, when the compared value of the laser beams on the right side of PICO has a positive sign, the robot has to turn in ….tive direction. As clarification, Figure XPYTHdX is added in which the example as explained before is pictured.
AFBEELDING XPYTHdX
It can be the case that the robot is in an open space and only notices a wall on one side of the robot. Since PICO is able to align using only one wall, this is not a problem at all. In this case, the range of laser beams on the side where no wall is detected is neglected. The part of the designed controller that is responsible for the alignment of PICO can be found here.
The amount of alignment that is needed for driving through the maze safely, without bumping, is set to a fixed value that is tuned during the testing sessions. Below it is shown how PICO aligns between two walls of the maze.
Side Free Left/Right
One of the basic skills that is implemented in the code of the robot controller is detecting if a side is free or not. When a side is free, the algorithm as used in the action manager decides if PICO drives into the free direction or continues its path.
For the detection if one or both of the sides of PICO are free, the laser ranges from XX to XX degrees on the left and from XX to XX degrees on the right or the robot are used, as indicated in Figure filtering. For the detection of the free sides of the robot, a range of XX meters is used. Laser beams with an angle or length outside the specified ranges will not be taken into account by PICO.
Door detection
Essential for finding the exit of the maze, a door located in a dead end of a corridor or in a wall has to be opened. In the figure below, a graphical representation of both these situations is shown. When PICO has detected a dead end, a bell will be rung and the door in the maze will be opened within a time of five seconds. Worth mentioning is that when PICO has opened a door in the maze, it will not ring a bell again when it reaches a dead end or detects a fake door in the side of the walls of the maze.
Meetings Overview
Brief summaries on the contents of team meetings are available here: [1]