Maze Solving Algorithm For Mazes With Loops

Question

I am trying to implement a line following robot that can solve mazes similar to the Pololu robots you can watch on youtube. My problem is the maze that I am trying to solve is looped and therefore simple Left/Right hand rule can not solve the maze. I have done some research and think either Flood-Fill or Breadth-First-Search algorithm will be able to solve these looped mazes. Solving the maze is reaching a large black area where all the sensors will read black. When the robot is following the line some of the sensors will read white and the central ones black.

Is there any other algorithms that can solve looped mazes? I understand how the Flood-Fill algorithm works but am unsure how it could be implemented in this situation.

My robot has 3 sensors on the bottom. The one in the centre is expected to always read black (the black line it follows) and the sensors on the right and left are expected to read white (while following a straight line) and then black once a junction or turn is reached. My robot has no problem following the line, turning etc. I need to find an algorithm that can solve looped mazes (that is, find a path from an entrance to an exit).

Answer 1

If both entrance and exit of the maze is at the edges of the maze, the left/right hand (wall following) algorithm should work. If you start following a wall that is connected to the exit, you could never get into a loop.

If you want the robot to be able to start in the middle of a maze with loops then simple wall following is not enough. I would recommend the Pledge algorithm in that case. The basic idea is that you pick an arbritary direction and follow it until you encounter a wall. Then you follow the wall until you have made as many righ turns as left turns, then continue forward (along the direction you originally picked).

The Pledge algorithm is proven to work in the ideal case with perfect sensors or some kind of error correction. If there could be errors when turning and not all angles are 90° some further measures may be needed (for example a compass). See this article for more details (direct link to the pdf). In your case the errors should be small enough.