Shortest Path with Obstacle Avoidance (ver 1.3)

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

Description

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)

[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
spy(M)
% 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.

[ron chand]

 

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

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

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

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

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

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

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

[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,
Mike

[Subrata Bhowmik]

This is not working. MM is undefined.

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

[Simon Jin]

very interesting!

[mandana noroozi]

 

[afaz uddin]

thi is one of good soft

[Amiya Patanaik]

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

[James]