No License

Download apps, toolboxes, and other File Exchange content using Add-On Explorer in MATLAB.

» Watch video

Highlights from
Shortest Path with Obstacle Avoidance (ver 1.3)

4.2 | 10 ratings Rate this file 48 Downloads (last 30 days) File Size: 8.66 KB File ID: #8625 Version: 1.0
image thumbnail

Shortest Path with Obstacle Avoidance (ver 1.3)


Michael Kleder (view profile)


03 Oct 2005 (Updated )

Computes shortest path between two points in the plane, avoiding obstacles.

| Watch this File

File Information

SHPATH - shortest path with obstacle avoidance (ver 1.3)
Given a "terrain" matrix consisting of zeros (for open space) and ones (for obstacles), this function computes the shortest path between two specified points while avoiding obstacles.

A two-stage solution is employed. In stage one, the algorithm rapidly propagates through all possible pathways to find a representative shortest route. In stage two, the path is contracted to follow closely around sharp corners and eliminate quantization noise. Although the map coordinates (and intial and final points) are integers, the solution coordinates are reals to allow for the elimination of jitter from map quantization.

Note that diagonal "moves" ARE allowed.

To avoid confusion over X/Y conventions for grid matrices, the issue is avoided entirely by referring only to the row and column entries in the grid. The user is invited to employ whatever convention he or she is comfortable using for mapping Cartesian coordinates to the grid matrix entries.

The user is encouraged to see the code comments (or the "help" text) and to run the example code.

Michael Kleder, Oct 2005

MATLAB release MATLAB 7.0.4 (R14SP2)
Tags for This File   Please login to tag files.
Please login to add a comment or rating.
Comments and Ratings (28)
10 Apr 2016 ibrahim cihan

12 Oct 2015 IISc

IISc (view profile)

Hi, Can you share documentation behind this algorithm.

Comment only
04 Sep 2015 Ronan

Ronan (view profile)

Hi, is it normal for this to take 4mins to process with a 2.2Ghz intel core duo and 3GB ram?

Is it possible to get lines perpendicular rather than diagonal?

Comment only
30 Jun 2014 sharmin

i am also having error in line 137
any1 sorted that out?
MM undefined

Comment only
04 May 2014 Shruti

Shruti (view profile)

unable to execute the code due to error at line 137.Kindly help me resolve this as it is very urgent.(what are the input arguments to b given?)

Comment only
03 Mar 2014 Phan Phat

could you give me the flowchart of this algorithm?

Comment only
17 Feb 2014 Amod

Amod (view profile)

The algorithm is working fine in our case. I want to know on basis of which algorithm you have implemented this code. Or this is your own algo.
Thanks Michael

16 Apr 2013 am

am (view profile)

Please help with the following error:
??? Input argument "MM" is undefined.

Error in ==> test at 137

Comment only

hi,i am not able to execute the code
please help me

Comment only
30 Aug 2010 Thijs

Thijs (view profile)

Dear Michael,

The algortihm is working perfectly in my case. I was only wondering whether or not it is possible to calculate the length of the final path?

Thank you for your reply.


Comment only
30 Aug 2010 Thijs

Thijs (view profile)

02 Nov 2009 James

James (view profile)

30 Jan 2008 Amiya Patanaik

Thank you so much. I was in search of similar algorithm for an autonomous robot navigation event. Credits assured. Keep it up

Comment only
12 Jan 2008 afaz uddin

thi is one of good soft

Comment only
23 Dec 2007 mandana noroozi

29 Mar 2007 Simon Jin

very interesting!

13 Feb 2007 The Author

Hello Subrata,
Since this is comand-line function, it wants its input arguments when it is called. There is a lengthy example at the end of the help text that appears when you type "help shpath".

Comment only
13 Feb 2007 Subrata Bhowmik

This is not working. MM is undefined.

17 May 2006 The Author

Hi Jackson,
Since this is comand-line function rather than an interactive GUI, it wants its input arguments when it is called. There is a lengthy example at the end of the help text that appears when you type "help shpath" which you can copy and paste all at once onto the command line to see an example.
Hope it helps,

Comment only
16 May 2006 Jackson Wong

Hi. I can't get it to work. When I type shpath in Matlab command window, it says:

??? Input argument 'MM' is undefined.
Error in ==> F:\shpath.m
On line 137 ==> M=logical(MM);

Any advice?

Comment only
19 Dec 2005 MAK Adams

I feel the algorithm works too good.But, there is a problem: it doesnt recognise diagonal obstacles eg- in the given figure itself the shortest path crosses the diagonal line.

07 Oct 2005 Michael Kleder

Version 1.3 has been uploaded and should be available soon. It is faster, more precise, and has greatly improved handling of tight spaces and corridors.

Comment only
06 Oct 2005 Michael Kleder

Ver 1.2 (recently posted) outputs relative path distances from all points to the final point. (One can reverse the order of the inputs to observe distances from the intial point.) Distance units are arbitrary. (See updated example code in the function.)

Comment only
06 Oct 2005 Rick Behrens

Related to my previous post, if I am interested not in a single, shortest path, but rather marking distance in all directions around whatever obstacles exist, can the guts of your code be leveraged to that end? Thanks for the quick turnaround on the improvements too - very useful.

Comment only
05 Oct 2005 Michael Kleder

Thank you for your comments. I have uploaded version 1.1 as an "update." In that version, the function performs checks on the inputs and also returns NaNs and a warning if no unobstructed route exists. (Also, note that ones are for obstacles and zeros are for open space.)

Comment only
05 Oct 2005 Rick Behrens

Great algorithm, Mike. Was wondering whether an optional output could be added that shows the propogation result, whether it be a figure or just the underlying matrix. This would be useful to show all possible paths in addition to the shortest path shown now.

05 Oct 2005 ron chand

04 Oct 2005 Steven Lord

Not bad, Michael, but you might want to add in some error checking for the case where there is no path between the starting and ending points.

% Generate our map
M = ones(25);
M([5 20], 5:20) = 0;
M(5:20, [5 20]) = 0;
% Note the white square -- impenetrable
% You can't get to (10, 10) from (2, 2)
X = shpath(M, 2, 2, 10, 10);

Right now, the code generates an error on line 133 during the interpolation in the second iteration.

Comment only
06 Oct 2005

Input checks added. Unsolvable case handled. Description text edited.

07 Oct 2005

Additional output created. Description updated.

10 Oct 2005

Improved speed and precision; improved unit-width corridor penetration; improved penetration between diagonally adjacent obstacle squares; improved example plot; improved description text

Contact us