Maze Robot: Simulation in Webots
Maze Design
Original maze: Labyrinth

Maze:
- Crete structure:Labyrinth: no diverge and bypass
- graph structure: simply connected or multi-connected
Our robot can find pathways in simply connected mazes, which means no loop and connected. There are many maze solving algorithms are closely related to graph theory.
- A traveler with no prior knowledge of the maze, which is our research focus. There are three typical strategies: random mouse, depth-first search, wall follower
- A supervisor can see the whole maze at once: This problem is much easier and there are various efficient algorithms: shortest path algorithms, breadth-first search or depth-first search
Exploing the Maze as a Traveller
Random Mouse
a trivial method
- proceed following the current direction until an obstacle is reached
- make a random choice of accessible directions and proceed
Wall follower
the best known algorithm for traversing maze
- left direction rule
- right direction rule
Why wall following works?
- Mazes containing no loops are known as “simply connected”, or “perfect” mazes, and are equivalent to a tree in graph theory.
- internal wall: branch streched out from the outside wall
- If the walls are connected, then they may be deformed into a loop or circle.
https://www.youtube.com/watch?v=k1tSK5V1pds
if the maze is not simply connected ?
(i.e. if the start or endpoints are in the center of the structure surrounded by passage loops, or the pathways cross over and under each other and such parts of the solution path are surrounded by passage loops), this method will not reach the goal.

We can set up a favored direction
If the current direction is the same as the favored direction, keep forward instead of following the wall.
However, when entering a G-shape maze, it will trap.

#### We can also set a value named “Sum of turns taken”
- when turn right , decrement
- when turning left, decrement
- keep stepping forward
- set a favored direction
- if current direcition is the same as favored direction
- if “sum of turns taken” equals 0:
- else
2. Robot Design
Robot Prototype

We attach compass sensor to the initial e-puck prototype. E-puck Prototype with sensors:
- differential_Wheels and encoder
- camera
- leds
- distance sensor: IR sensor
Controller
- random controller
- wall following controller
- pledge controller
Controller Modules:
- wall changed
- threshold
- bias back
- decide which direction to continue proceed
- turn left
- turn right
3. Performace Demo
Video Deme : please make sure you can visit youtube fluently.
Checkout our source code here: https://github.com/haoransh/Maze-Robot-on-Webots!
