4
$\begingroup$

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).

$\endgroup$
3
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ I need a robust algorithm as I don't know whether the start point is at the edge or somewhere inside the maze, nor do i know whether the finish is on the outside or inside. Reading about the pledge algorithm it can't solve all of these cases. $\endgroup$ – user2476983 Jun 26 '13 at 6:38
  • $\begingroup$ It can solve all cases as far as I know. The "G"-shape is only mentioned to explain why it should be implemented that way it is (360° != 0°). $\endgroup$ – Hjulle Jun 26 '13 at 13:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.