Lee's algorithm - Described?

Hi all,

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=EDch the bot can determine the instruction sequence - but will the turns not not all come out turn 45 deg +\-?

Thanks

Mark

Reply to
markwod
Loading thread data ...

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

Reply to
D Herring

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

Reply to
Gary Brown

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

Thanks, TC

Reply to
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:

formatting link

Reply to
Mike

One of these papers?

formatting link
Or is it a different Lee? (Sorry; not my field, but one I'm interested in.)

- Daniel

Reply to
D Herring

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 .

Reply to
werty

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:

formatting link
gives this citation:

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.

Reply to
Mike

PolyTech Forum website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.