maze solving - map building and recall

[freshbrew]

Hello,

Im planning on building a maze solving robot. The maze will be simply connected with no loops and a line opposed to walls. I want the robot to first evaluate the maze by consistently turning either right or left at each junction until it reaches the end. But I want it to be able to remember the shortest route which can be recalled at a later date. I've read articles on quadrature encoders but what i dont understand is how this information is translated into a map and how the map is then used by the robot to find the shortest route. Can anyone point me in the right direction please.

Regards

[waltr]

I believe that quadrature encoders are being used to keep track of how far the wheels turn thus how far the Bot traveled.
The translation of the maze to a map is tricky business but very doable. SoR have a tutorial on mapping that may be a good starting point. Then do some searches on the web for university papers.

But, before you get to mapping the maze you need to build a Bot that can at least travel through the maze. How far are you on this?

[amando96]

No need for encoders if you don't have loops.

Here's a nice tutorial.
It's a really good write up, it tells you basically how you have to do your code.

[freshbrew]

Thankyou for your replys. I am only at the design stage, I have not yet begun building.

I have read the SoR tutorial on mapping, however this requires input from the programmer, i wanted my robot to be able to map the maze itself, during its exploratory initial run.

I have read the linked PDF you suggested and found it interesting but what i really want is for the robot to map the maze, then determine the shortest route. Or is that not possible?

[waltr]

That is a very nice tutorial on a line maze. Thanks.

As to mapping and then solving for the shortest route. This would require a bit of memory and processing power but more important is a good algorithm. If you plan for this pick a little faster processor with more memory than would be needed for a plan line maze Bot. I think many of the micro-controllers commonly used by hobby Bot builders would work. I'm thinking of the Axon II and some of the PIC18Fs. I don't think you need any of the high-end processors for this.

Then get the basics working to do the maze. Research and additional coding can be done without changing the Bot's hardware.

Have you done any google searches? Here are some for starters (searched on "shortest maze route"):
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
http://cboard.cprogramming.com/c-programming/114429-shortest-path-maze-solver-breadth-search-help.html
http://www.techenclave.com/programming/c-program-maze-shortest-path-158368.html
http://i11www.iti.uni-karlsruhe.de/~fschulz/shortest-paths/
http://www.societyofrobots.com/member_tutorials/book/export/html/94
http://www.astrolog.org/non/shP_Habuc.pdf

And there are many more.

[amando96]

The 3Pi robot uses an atmega 328, search it on youtube, it's really fast.

Or is that not possible?

Did you read the whole PDF? 

[voyager2]

How about Wavefront Pathfinding?
http://www.societyofrobots.com/programming_wavefront.shtml

[Soeren]

Hi,

Using PROLOG, it would be very easy, but short of that, the simplest to understand (I think) may be to simply track each possible route and afterwards count the distance and the number of turns (more turns will mean a slower speed) and then select the shortest/fastest.

While processing the possible routes, any route that extends one allready found needs no further evaluation and can be discarded at the point where it extends the reference. Keep the shortest route for reference and if a shorter one is found, make this the reference and continue to all possible routes are evaluated.

[freshbrew]

Thanks once again for all the replies.

I was hoping to build something similar to this http://www.robotroom.com/Maze-Solving-Robot-All-Right.html.

It displays the maze as it is dicovered on an LCD. It then uses this informations to identify the shortest route.

[Soeren]

Hi,

I was hoping to build something similar to this http://www.robotroom.com/Maze-Solving-Robot-All-Right.html.

Why don't you send David Cook a mail then?

[freshbrew]

I have, but i havent recieved a reply.