Lee's algorithm - Described?

I'm not familiar with Lee's algorithm, but "A-star" (A*) path planning is a popular, efficient method.

A Google on "lee's algorithm" yielded 668 entries. I didn't look to carefully at any but you should find what you want.

Gary

I'm implementing my robots navigation system and as a starting point I want to use Lee's algorithm to help figure out the route and therefore the sequence of commands the robot needs to perform inorder to get from A to B.

Q1) Does anyone know where I can find a good explaination of how the algorithm works? I've tried google but the results seem to be papers on varients and alternatives.

Q2) I know it works with a grid and it'll trace back to the starting point (From whích the bot can determine the instruction sequence - but will the turns not not all come out turn 45 deg +\-?

Thanks

Mark

If you do find a good reference please post the link here.

Thanks, TC

You might try reading Lee's original paper. Note that it is for a graph, so you can make your "grid" in any shape (circular, irregular, etc.) - you just need to know the connections between nodes.

For A*, you might look at Amit's A* Pages:

One of these papers?

- Daniel

Let the Robot teach its self , in terms

of what it can see thru its sensors ,,,

it does have sensors , does it not ?

Or is it on tracks , as a train , and

not need a computer to figure ...

I like to place keys/buttons next

next to each sensor , so i can program

the mcu .

A single key can have a one shot ,

sending a square wave , and while

i hold the key down , it signals the mcu .

A bit like morse code , you can also

do a bit of local programming .

I think the books , now , have old ideas

to make robots .

Those appear to be more recent papers in the same subject area. I was unable to find my hardcopy of Lee's paper in a few minutes searching, so I fell back on Wikipedia. This page:

C.Y. Lee, An algorithm for path connections and its applications, IRE Trans. Electronic Comput., EC-10, 346?365, 1961. One of the first descriptions of a maze router

My memory says the algorithm starts at the destinationand numbers all graph nodes which are adjacent to the destination as "1". Then labels all not already labelled nodes adjacent to the "1"-nodes as "2". Repeat this process, incrementing the label, until the start node is reached. You can then follow the labels between the start node and destination node. There will probably be multiple paths from which to chose. With some thought, you should be able to modify the algorithm with a "cost" or "goodness" metric to help you choose an "optimimum" path.

I hope this helps.