Maze Robot: Simulation in Webots

Haoran Shi
Aug 31, 2018 · 3 min read

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!

Haoran Shi

Written by

Master Student @Carnegie Mellon University. Bachelor of Computer Science at Peking University.

Welcome to a place where words matter. On Medium, smart voices and original ideas take center stage - with no ads in sight. Watch
Follow all the topics you care about, and we’ll deliver the best stories for you to your homepage and inbox. Explore
Get unlimited access to the best stories on Medium — and support writers while you’re at it. Just $5/month. Upgrade