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 whch the bot can determine the instruction sequence - but will the turns not not all come out turn 45 deg +\-?
Thanks
Mark
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
snipped-for-privacy@yahoo.co.uk wrote:

I'm not familiar with Lee's algorithm, but "A-star" (A*) path planning is a popular, efficient method.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
On Mon, 05 Feb 2007 20:56:13 -0500, D Herring

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: http://theory.stanford.edu/~amitp/GameProgramming /
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
Mike wrote:

One of these papers? http://citeseer.ist.psu.edu/49505.html http://citeseer.ist.psu.edu/lee96rectilinear.html
Or is it a different Lee? (Sorry; not my field, but one I'm interested in.)
- Daniel
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
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 .
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
On Sun, 11 Feb 2007 21:13:41 -0500, D Herring

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:
http://en.wikipedia.org/wiki/Routing_%28EDA%29
gives this citation:
C.Y. Lee, An algorithm for path connections and its applications, IRE Trans. Electronic Comput., EC-10, 346365, 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.
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload
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
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 whch the bot can determine the instruction sequence - but will the turns not not all come out turn 45 deg +\-?
Thanks
Mark
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

If you do find a good reference please post the link here.
Thanks, TC
Add pictures here
<% if( /^image/.test(type) ){ %>
<% } %>
<%-name%>
Add image file
Upload

Polytechforum.com is a website by engineers for engineers. It is not affiliated with any of manufacturers or vendors discussed here. All logos and trade names are the property of their respective owners.