Shop OBEX P1 Docs P2 Docs Learn Events
Maze traversal algorithms for robot car - any hints og pointers? — Parallax Forums

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

hallsteihallstei Posts: 2
edited 2007-01-11 13:12 in Robotics
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

Comments

  • GadgetmanGadgetman Posts: 2,436
    edited 2006-03-07 13:56
    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...
  • allanlane5allanlane5 Posts: 3,815
    edited 2006-03-07 14:13
    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.
  • LoopyBytelooseLoopyByteloose Posts: 12,537
    edited 2006-03-07 15:31
    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 ClarkeRyan Clarke Posts: 738
    edited 2006-03-07 18:11
    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
  • hallsteihallstei Posts: 2
    edited 2006-03-08 09:12
    Thanks for the pointers!

    They look very interesting. smile.gif
  • jiunn82jiunn82 Posts: 5
    edited 2007-01-07 20:43
    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.
  • GadgetmanGadgetman Posts: 2,436
    edited 2007-01-11 13:12
    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
Sign In or Register to comment.