Maze traversal algorithms for robot car - any hints og pointers?
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
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
Comments
If the maze is built of shorter, non-interlinked walls, so that there are several alternate paths, though...
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Don't visit my new website...
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
▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔▔
Ryan Clarke
Parallax Tech Support
RClarke@Parallax.com
They look very interesting.
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