Thread Subject:

Find a path from point A to point B while avoiding obstacles

I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.
Does anybody have an idea of how I might do this using a smart approach instead of just manually doing it?
Thanks in advance.

"Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iapfr4$luv$1@fred.mathworks.com>...
> I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.
> Does anybody have an idea of how I might do this using a smart approach instead of just manually doing it?
> Thanks in advance.

This probably isn't everything you need but is worth a read:

http://www.cb.uu.se/~cris/blog/index.php/archives/277
(Cris Luengo's blog on mazes)

On 02/11/10 11:56 AM, Modestas Sekreckis wrote:
> I have two points in 3D space (A and B) and some sort of obstacle
> between them, I need to find a path to avoid colliding with an obstacle.
> Does anybody have an idea of how I might do this using a smart approach
> instead of just manually doing it?

There are different approaches depending upon the properties you need
the path to have.

If the points to be passed through are discrete and you want to find the
shortest path, then you might as well use
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
unless you have too many points to make that computationally practical.

If the points to be passed through are continuous, I believe the
shortest path would hug the convex hull of the obstacle.

Walter Roberson <roberson@hushmail.com> wrote in message <pYXzo.5119$iX5.5091@newsfe21.iad>...
> On 02/11/10 11:56 AM, Modestas Sekreckis wrote:
> > I have two points in 3D space (A and B) and some sort of obstacle
> > between them, I need to find a path to avoid colliding with an obstacle.
> > Does anybody have an idea of how I might do this using a smart approach
> > instead of just manually doing it?
>
> There are different approaches depending upon the properties you need
> the path to have.
>
> If the points to be passed through are discrete and you want to find the
> shortest path, then you might as well use
> http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
> unless you have too many points to make that computationally practical.
>
> If the points to be passed through are continuous, I believe the
> shortest path would hug the convex hull of the obstacle.

That doesn't seem to be true in general, certainly not for a single, non-convex obstacle... For example, you might have an obstacle made up of 3 mutually orthogonal thin rods, intersecting at their centers. The convex hull is a sort of octahedron shape, but constraining the path to hug that hull ignores the possibility of passing through the hull, close to the rods.

The question didn't specifically ask for the "shortest" path though, so that might be fine.

On 10-11-02 03:01 PM, Alan B wrote:
> Walter Roberson <roberson@hushmail.com> wrote in message

>> If the points to be passed through are continuous, I believe the
>> shortest path would hug the convex hull of the obstacle.

> That doesn't seem to be true in general, certainly not for a single,
> non-convex obstacle... For example, you might have an obstacle made up
> of 3 mutually orthogonal thin rods, intersecting at their centers. The
> convex hull is a sort of octahedron shape, but constraining the path to
> hug that hull ignores the possibility of passing through the hull, close
> to the rods.

Oh, good point! Especially if the obstruction has holes in it.

In that case, if a shortest path was required... ummm, let's see... Quantize
space into cells of size proportional to the allowed maximum difference
between the theoretical shortest path and the practical path, and Dijkstra the
result?? I have some hesitation, though, about the appropriate cell size, as a
path that skims the object is going to be accumulating more error than if the
path is through free space.

I'm tempted to think instead in terms of octree'ing the shape and calculating
explicit intersection points, but at the moment a "shortest path" algorithm
for that does not come to mind.

I was also put in mind of ray tracing, but I realized that reflections of
light do not turn corners sharply enough. For example, if there is a
cylindrical hole through the object, the shortest light path might involve
bouncing the light back and forth between the top and bottom of the cylinder,
whereas the shortest physical distance would just go to one edge of the
cylinder and straight through it and then turn.

This is a classic motion planning problem and an introductory text should suffice.

I love potential models because of their simplicity. I would "surround" this object with a force field as simple as:

F= 10000 N for distance<r
  =0

choose r wisely.

Of course, I am not going to debate over the faults of this method(numerical problems etc etc). If it works and it's simple, then that's engineering. If not, it is math.

Dear Modestas,

> I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.

Is the 3D shape of the obstacle known at the beginning? Or do you have to collect the needed information during walking along the path.

Han Solo used a laser blaster to get a free path through the fields of asteroids. Is this an option?

Kind regards, Jan

On 10-11-02 05:41 PM, Jan Simon wrote:

> Han Solo used a laser blaster to get a free path through the fields of
> asteroids. Is this an option?

Something sounded suspicious about that, so I checked. If one follows the
detailed Wikipedia discussion about asteroids, Hans Solo could not have been
travelling through an asteroid field, as "asteroid" refers to objects within
the orbit of Jupiter. Hans must instead have been flying through "small solar
system bodies".

"Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iapfr4$luv$1@fred.mathworks.com>...
> I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.
> Does anybody have an idea of how I might do this using a smart approach instead of just manually doing it?
> Thanks in advance.
I try to make it easier to get the job done 2D plane. How to find the point C (x, y). The system is shown in the picture. http://img502.imageshack.us/img502/193/51082985.jpg

"Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iau50s$btr$1@fred.mathworks.com>...
> "Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message <iapfr4$luv$1@fred.mathworks.com>...
> > I have two points in 3D space (A and B) and some sort of obstacle between them, I need to find a path to avoid colliding with an obstacle.
> > Does anybody have an idea of how I might do this using a smart approach instead of just manually doing it?
> > Thanks in advance.
> I try to make it easier to get the job done 2D plane. How to find the point C (x, y). The system is shown in the picture. http://img502.imageshack.us/img502/193/51082985.jpg

If you know you want a two-line-segment path, that is entirely outside the convex hull of the shape, then here is a simple, but not optimal, approach to try:

1. Choose one plane on which your intermediate point will lie. For simplicity, choose the plane perpendicular to line AB, and passing through the centroid of the obstacle.
2. Find the perspective projection of the obstacle onto the plane, with respect to both point A, and point B. These projections represent regions on the plane where the intermediate point can NOT be.
3. Look at the union of these two regions, and find the point on the perimeter closest to the centroid of the obstacle. This is your intermediate point.

Even for convex objects, this will be much longer than the shortest path, in the cases where one or both of the points is relatively close to the obstacle. If you don't care about the path length, the above should suffice. You could also replace the object with a pre-determined, appropriately sized sphere, to simplify the calculations further. Or use a PCA box if the shape is very irregular.

If you need a shorter path length, but don't need it to be optimal, then you can try doing the same thing, but with two planes - both still be perpendicular to line AB, but one passes through the point on the obstacle closest to point A, and one through the point closest to point B. You'll need two intermediate points, which means you'll need to check many combinations of points between the two projection regions, but it seems to me that one of those combinations will get you a fairly short path, though not optimal in general.

Dear Walter,

> > Han Solo used a laser blaster to get a free path through the fields of
> > asteroids. Is this an option?
>
> Something sounded suspicious about that, so I checked. If one follows the
> detailed Wikipedia discussion about asteroids, Hans Solo could not have been
> travelling through an asteroid field, as "asteroid" refers to objects within
> the orbit of Jupiter. Hans must instead have been flying through "small solar
> system bodies".

I know, I'm German. Inspite of this, I'm absolutely sure, that the name was *not* Hans Olo.
The setup of bodies, independent from the correct name, shown in the movie, is obviously instable due to the size and density of the bodies. Especially if the crew leaves the space ship and can breath *air* on the "small solar system body", it is absolutely clear: The landing of the space ship inside the cave has a more metaphoric sense and the viewer has to investigate the situation from a psychological point of view. Han, Lea, the laser blaster and the cave...

So my personal conclusion: "asteroids" is correct - because the scene was definitely not recorded outside the Jupiter orbit to save the money for transporting the camera team.

But coming back the the OPs problem: In the 2D picture there we cannot see a laser blaster, so there is not need to follow this theory any longer.
 
Kind regards, Jan

"Jan Simon" <matlab.THIS_YEAR@nMINUSsimon.de> wrote in message
news:iauqji$mmr$1@fred.mathworks.com...
> Dear Walter,
>
>> > Han Solo used a laser blaster to get a free path through the fields of
>> > asteroids. Is this an option?
>>
>> Something sounded suspicious about that, so I checked. If one follows the
>> detailed Wikipedia discussion about asteroids, Hans Solo could not have
>> been travelling through an asteroid field, as "asteroid" refers to
>> objects within the orbit of Jupiter. Hans must instead have been flying
>> through "small solar system bodies".
>
> I know, I'm German. Inspite of this, I'm absolutely sure, that the name
> was *not* Hans Olo.
> The setup of bodies, independent from the correct name, shown in the
> movie, is obviously instable due to the size and density of the bodies.
> Especially if the crew leaves the space ship and can breath *air* on the
> "small solar system body", it is absolutely clear: The landing of the
> space ship inside the cave has a more metaphoric sense and the viewer has
> to investigate the situation from a psychological point of view. Han, Lea,
> the laser blaster and the cave...

Nitpick: The princess's name is Leia.

And I hate linking to TV Tropes and killing hours of peoples' time, but
"Repeat to yourself it's just a show ..."

http://tvtropes.org/pmwiki/pmwiki.php/Main/MST3KMantra

--
Steve Lord
slord@mathworks.com
comp.soft-sys.matlab (CSSM) FAQ: http://matlabwiki.mathworks.com/MATLAB_FAQ
To contact Technical Support use the Contact Us link on
http://www.mathworks.com

On 10-11-04 10:16 AM, Alan B wrote:
> "Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message
> <iau50s$btr$1@fred.mathworks.com>...
>> "Modestas Sekreckis" <modestas.sekreckis@gmail.com> wrote in message
>> <iapfr4$luv$1@fred.mathworks.com>...
>> > I have two points in 3D space (A and B) and some sort of obstacle
>> between them, I need to find a path to avoid colliding with an
>> obstacle. > Does anybody have an idea of how I might do this using a
>> smart approach instead of just manually doing it?
>> > Thanks in advance. I try to make it easier to get the job done 2D
>> plane. How to find the point C (x, y). The system is shown in the
>> picture. http://img502.imageshack.us/img502/193/51082985.jpg
>
> If you know you want a two-line-segment path, that is entirely outside
> the convex hull of the shape, then here is a simple, but not optimal,
> approach to try:
>
> 1. Choose one plane on which your intermediate point will lie. For
> simplicity, choose the plane perpendicular to line AB, and passing
> through the centroid of the obstacle.
> 2. Find the perspective projection of the obstacle onto the plane, with
> respect to both point A, and point B. These projections represent
> regions on the plane where the intermediate point can NOT be.

I'll have to think more about your algorithm when I have some time to
concentrate more deeply.


While I was showering this morning, I was thinking that there might be an
approach something like this, at least for 2D and under the assumption that
there is no (permitted) path that passes inside the obstacle:

1. Find the line connecting the endpoints;

2. Using the above line, divide the vertices of the obstacle according to
which side of the line they are on; if all of the vertices of the obstacle end
up on the same side of the line, then there is a direct unimpeded path between
the endpoints so do not continue;

3. For each of the two sides of the line, find the perpendicular distance of
each of the points on that side to the line, and select out of that set the
point that has the largest perpendicular distance for that side (if there are
multiple points with the exact same maximum perpendicular distance, select any
one of them);

4. One point and corresponding perpendicular distance will remain for each
side. Out of those two, select the one with the smaller perpendicular distance
to the line.

5. If my fuzzy mental visualization was correct [a dubious proposition!], the
shortest two-segment path (presuming no holes in the obstacle) between the
endpoints passes arbitrarily close to the selected point, through a point
along the vector between the selected point and the line but further out along
that vector than the point selected in step (4). That is, the absolute
shortest such path would connect the endpoints to the selected point; if the
requirement is that the path not actually touch the obstacle then move the
minimum necessary distance away from the selected point in the indicated
direction.

On 10-11-04 01:17 PM, Walter Roberson wrote:

> While I was showering this morning, I was thinking that there might be
> an approach something like this, at least for 2D and under the
> assumption that there is no (permitted) path that passes inside the
> obstacle:

Uh, no, I realized that will not work. On the other hand, I realized that
there is a vectorizable way that should work for the above assumptions.

Let A be the endpoint with lower X coordinate and let B be the endpoint with
higher X coordinate.

For any given point, C, the angle formed by BAC can be calculated through the
usual dot-product and arccos process. The points CL and CR with the greatest
clockwise and counter-clockwise angles relative to BA are the two candidate
points for being the limiting obstruction points. The one of the two that has
the lower absolute angle is the one that will lead to the shorter two-segment
path. To avoid problems with arccos wanting to produce positive angles (which
makes the clockwise vs counter-clockwise classification more difficult), don't
bother actually taking the arccos() and just compare the cosines themselves.

If all of the obstruction points are stored in a single matrix, the cosine
calculation can obviously be vectorized. From there it is just a matter of
finding the indices of the max and min elements, figuring out which of the two
has the *higher* absolute value (higher because higher absolute cosine value
is a *smaller* angle), and the corresponding point is the limiting one for the
two-segment path.

On Nov 2, 6:10 pm, "Saurabh Mahapatra"
<saurabh.mahapa...@mathworks.com> wrote:
> This is a classic motion planning problem and an introductory text should suffice.
---------------------------------------------------

I wouldn't doubt it. I know it is a field of study. It seems like
there could be many ways of solving it. I don't know much about
classic motion planning problems, but I know it could be solved with
dynamic programming (http://en.wikipedia.org/wiki/Dynamic_programming)
because I've done something similar with dynamic programming: blood
vessel tracking in angiograms where you go from point A to point B
along the ridgeline. I pretty certain it could also be solved with an
algorithm like the well-known and loved A* (http://en.wikipedia.org/
wiki/A*) (similar to Dijkstra's algorithm mentioned by Walter).
-ImageAnalyst

There are several shortest path algorithms here in this File Exchange
submission:
http://www.mathworks.com/matlabcentral/fileexchange/10922
including Johnson's algorithm, and the Floyd-Warshall algorithm.