Embedded Motion Control 2017 Group 5: Difference between revisions
No edit summary |
|||
| Line 59: | Line 59: | ||
== Maze-solving Algorithms == | == Maze-solving Algorithms == | ||
'''Wall follower''' | '''Wall follower'''<br /> | ||
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. | 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''' | '''Pledge algorithm'''<br /> | ||
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. | 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''' | '''Trémaux algorithm'''<br /> | ||
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. | 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. | ||
Revision as of 16:03, 18 May 2017
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 |
| Wouter Houtman | - | w.houtman@tue.nl |
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.
Meetings Overview
Brief summaries on the contents of team meetings are available here: [1]