Lee's algorithm - Described?

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

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/

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

 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 .

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, 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.

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 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