Maze traversal algorithms for robot car - any hints og pointers?

hallstei

Hello, everyone!

Some colleagues and I have started experimenting using the robot car that comes with a BASIC Stamp, but we use the Javelin processor instead.

We were planning to try and navigate this car through a maze, using an ultrasonic sound device for detecting obstacles, and a LED beacon in order to know where the goal of the car is.

My question is:

Does anyone know where I can find information on algorithms and techniques that I can program in order to solve this problem using only the sensors that I have available to me. (Most information I have found on the Internet either requires one to have a complete map of the area the car is to operate in - or a system with three or more beacons)

I know of the Depth First Search algorithm, but I assume that one cannot implement it directly.

Cheers,

Hallstein

PS. I apologize for my bad English, and for not knowing the precise names of the hardware I have described.

Post Edited (hallstei) : 3/7/2006 11:33:15 AM GMT

Gadgetman

The simplest algorithm, if the maze only contains ONE possible route(not lots of shorter walls) is the 'follow the righthand wall'. Another, just as popular is 'follow the lefthand wall'.

If the maze is built of shorter, non-interlinked walls, so that there are several alternate paths, though...

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Don't visit my new website...

allanlane5

Lookup "Micro-Mouse" on Google. Follow the links from there. It turns out there's several mapping algorithms and approaches, and those links should have papers on them.

LoopyByteloose

I think Gadgetman's method won't work in some cases.

If you have islands of maze within a maze, you may get into a circular routine and never get out. Nonetheless, it is the extremely famous 'Harvey Wallbanger' approach that won many early maze competitions with very simple devices.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
"When all think alike, no one is thinking very much.' - Walter Lippmann (1889-1974)

······································································ Warm regards,····· G. Herzog [noparse][[/noparse]·黃鶴 ]·in Taiwan

Ryan Clarke

Do a Google search on "Flood-Fill" algorithm. This will send you in the right direction.

Ryan

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ryan Clarke
Parallax Tech Support

RClarke@Parallax.com

hallstei

Thanks for the pointers!

They look very interesting.

jiunn82

Hi everyone, I have a question, is that a BASIC language able to perform the flood-fill algorithm...I am quite confuse whether to apply C or BASIC.

Gadgetman

ANY language where you can scan an array can handle a flood-fill algorithm.

An array is just a row of variables, or even the bits in a Byte or Word, so yes, even PBASIC can do it.
(And most other BASICs have ARRAY constructs to make it easier)

What makes it a bit difficult to implement in PBASIC is that it's a RECURSIVE algorithm, and PBASIC isn't fond of those... (you can solve this using a 'stack' array, though.

The big trick with the Flood-fill algorithm is that you start at the entry-point in the maze, and when you 'flood' the maze, you use increasing numbers.

Start with walls being 0, everything else being 255. Set your start to be 1, then the non-wall squares next to it to 2, the ones next to those again to 3.
Whenever it encounters squares that have been numbered with a larger number, treat it as 254, as you're on a shorter solution than the previous flood.
Whenever you bump into a lower number, treat it as a wall, because you already have a better solution to reaching that point.

This algorithm can be considered finished either when:

1.·a sucessful solution(found exit) is found,

2. Or the algorithm runs out of areas to flood.


The shortest path can then be decided by reading the value on the 'Exit', picking an adjacent sqare with a value that is less than it, and stepping backwards to the start.

▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Don't visit my new website...

Post Edited (Gadgetman) : 1/11/2007 1:34:12 PM GMT