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?
5
-
$\begingroup$ 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? $\endgroup$– apnortonApr 13, 2013 at 3:00
-
$\begingroup$ I don't know the maze in advance, and it should be solvable with wall following. The maze should be simple. $\endgroup$– user1159Apr 13, 2013 at 3:29
-
$\begingroup$ What are the rules? Are you allowed to include a tethered balloon with an attached camera to you robot? *8') $\endgroup$– Mark BoothApr 13, 2013 at 14:20
-
$\begingroup$ Are the initial position and goal location always on the sides of the maze? Or could they be somewhere in the middle of it? $\endgroup$– ShahbazApr 14, 2013 at 12:35
-
$\begingroup$ if the maze is a tree (no cycles), wall following is probably the best and simplest method $\endgroup$– ronalchnApr 19, 2013 at 13:17
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
2
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.
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.
answered Apr 13, 2013 at 15:24
-
$\begingroup$ In this case I would fall back to the 'always turn left' algorithm ;) $\endgroup$ May 23, 2013 at 20:47
-
$\begingroup$ Yeah, because you "know the maze before-hand" $\endgroup$ May 24, 2013 at 2:25
$\begingroup$
$\endgroup$
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...
$\begingroup$
$\endgroup$
For any given algoritm (which does not know the maze beforehand) there is a particular maze, where the argorithm does not choose the fastest way on first try.
Many algorithms do the trick, that they travel all ways in maze first, recording the way, than they find optimal way and on second try they drive just to the target by the fastest way.
If your maze is known to be a tree (no loops), with ways just wide for the robot to move, but not too wide and if it have just right angles (which many simple mazes are), then you can use some tricks to solve it faster second time:
side sensors would help a lot, so you would not be forced to constantly turn around
if it is not possible and you have range sensor (usually ultrasound) rather then just obstacle sensor (maybe plain bumper), you can restrict it to narrow beam and choose to just wave a little and see, if the distance is changing consistently, or if there is a hole (which means side way) and how far the hole is. Then you can run fast near to the crossing and then only slow and go full range rotations to excactly find the side way.
also having the sensor on "tank-like" rotating base would allow you to drive stight and rotate just the sensosr, which is faster, than rotating whole robot
if the ways are narrow, you can consider to add bumpers to sides and just bumping to the sides to feel them instead of rotation on place to sensor them properly. Bonus if you can have bug-like antennas to feel both sides at the same time (but they need to be flexible to not break and you need at least 3 state sensors for them (2 bits) - no touch - light touch - hard touch: no touch means side way, light touch means you are just on straight row in centre, hard touch means obstacle or turnining too much to side)
Anyway:
you go your usual "right hand on wall" way, until you find target, then continue to sthe start the same style, so you travel all the maze first time.
you mark any crossing on the way and count them creating kind of map (bonus if you measure the distance), then, when on the start back you go travel the map in memory and when you return to a crossing, you know, that you can skip the first way, that you had choose there, as it does not reach the target and it returns back. Continue, until you find target and you have half of the map solved. Then do it in reverse way from end and solve the other half of map. You should get the same result - if not, you made a mistake or the maze is not a tree.
on the second try you know, which side ways you can skip and which way you have to choose on which crossing, so you go the shorter way to target.
if you also marked the distances, you know, how far next turn should be and you can drive really fast for nearly all the distance, before you need to scan for turn precisely (and probably more slowly)
if your robot construction allows it, you even can ignore the walls and let them lightly bump you back to the centre of that way, so you need a lot less delicate navigation, so you can run even faster.
The same goes to turns, where you can stick to the wall and push a little all the time you think you are approaching turn, until it let you go in, so you know your turn is here. Again much simpler navigation, much less data to evaluate, so much faster speed possible.
If you want to be extra ultra fast, you record this run too and use that for third run, where you know, how long you have to run before turn, with all the acceleration and irrgularities of fast run versus carefull and slow exploring is already accounted for.
