Tell me more ×
Robotics Stack Exchange is a question and answer site for professional robotic engineers, hobbyists, researchers and students. It's 100% free, no registration required.
up vote 3 down vote favorite

I'm planning on programming a prebuilt robot to solve a maze as fast as possible. The robot has forward obstacle sensors (no side sensors) and 3-axis accelerometer. I'm planning on using the wall following algorithm. Is this the fastest possible algorithm? Also, since there are no side sensors, the robot needs to continuously turn to check if there is a wall on its side, so is there a clever way to use the accelerometer and sensors?

share|improve this question
Maze solving is a complex topic, and some approaches depend on the nature of the maze. Is there any pre-knowledge about the maze? Is it known to be solvable with wall following? – anorton Apr 13 at 3:00
I don't know the maze in advance, and it should be solvable with wall following. The maze should be simple. – user1159 Apr 13 at 3:29
What are the rules? Are you allowed to include a tethered balloon with an attached camera to you robot? *8') – Mark Booth♦ Apr 13 at 14:20
Are the initial position and goal location always on the sides of the maze? Or could they be somewhere in the middle of it? – Shahbaz Apr 14 at 12:35
if the maze is a tree (no cycles), wall following is probably the best and simplest method – ronalchn Apr 19 at 13:17

2 Answers

up vote 1 down vote

You can't say much about solving a maze unless you are allowed to explore first, or know the maze before-hand. Otherwise, it is easy to build a maze that will take arbitrarily long to solve using wall-following, but which has a simple solution. See the following example.

Oops! We followed the wrong wall

In this case, it is faster on average to just chose turns randomly. So maybe this is a tough problem that requires a little more thought. In some contexts, an iterative-deepening approach isn't bad. Start your research there, and come back when you have specific questions.

share|improve this answer
up vote 1 down vote

The wall following algorithm will benefit more from sensors on a side. Since you follow the side until you find a gap then you turn into that gap. You could then use the accelerometer to sense a bump when you hit the wall in front. However not sure how you can determine that you are out of the maze (in case you need to do that). Just an idea...

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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