Lee's algorithm - Described?

Posted by on February 5, 2007, 12:09 pm

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

Posted by D Herring on February 5, 2007, 8:56 pm

markwod@yahoo.co.uk wrote:

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

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

Posted by Mike on February 11, 2007, 2:45 am

On Mon, 05 Feb 2007 20:56:13 -0500, D Herring

>markwod@yahoo.co.uk wrote:

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

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

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/

Posted by D Herring on February 11, 2007, 9:13 pm

Mike wrote:

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

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

Posted by werty on February 12, 2007, 5:38 pm

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 .

Page 1 of 2 1 2 > last >>

Subject
Posted In
Date

Visual recognition and the SIFT algorithm
General Robotics Forum
2006-02-23

More Visual Recognition and the SIFT algorithm
General Robotics Forum
2006-02-24

Algorithm for counting number of lines travelled over
General Robotics Forum
2005-12-23

Closed-loop proportional motion control algorithm.
General Robotics Forum
2005-10-10

Transformation matrix from global to localframe
General Robotics Forum
2012-05-11