Free Web Hosting Provider - Web Hosting - E-commerce - High Speed Internet - Free Web Page

Let's imagine we have to plan a path to move a point from one site to another avoiding
known obstacles. Stepping forward from initial position and looking for a possible move
is not a right strategy, because of some roots would lead to the dead ends.
Let's use an old idea of the "water seeking for a hole". Imaging our space is excitable
media, where obstacles are not excitable regions in it. Let's issue a wave, which starts
from initial position in all directions. It finally finds the way to the target point.
This wave should last a residual excitation. Exploring this "fading smell" we will be
able to find the way back -- from the target site to initial one. Then taking this
way as "Ariadne thread" we might follow it.

Now imaging more complex task of finding the way to move a piano across the flat.
Here we have more parametrs of the task, as piano position and orientation and so on.
Let's propagate our waves in the parameters space. But first we have to map our
obstacles back to this parameters space. The idea is not to solve this "inverse" task,
but rather to have "3D virtual lab" that would reflect the real situation. Let's
make trials -- for each parameters point we reconstruct real situation and see if
it is acceptable. Yes, we might do it in parallel for all possible parameters points.

The following animated GIFs was created from MatLab Movie using the package from http://math.lbl.gov/~wiegmann/Info/movie.html
(Some contain two repeats). Click on it and reload to see again.

The system may also work as well with a moving obstacles as with a moving target.
For each time step for the first wave propagation we should change our obstacle
configuration in parameters space. More over we should remember all previous
steps of the propagation wave in order to be able to find the way back. We do this
by incorporating all snap shots in one array, which have one dimension more.

Some results of moving obstacle avoiding are presented below. GIFs show the motion twice.

You can see mouse finding the way from one corner to another avoiding turning
door. In this case, door is turning fast ( MPEG).
Here it is the same, but door is moving slower. Mouse waits and then "decided"
to cheat the door going upwind -- this way is shorter in time (MPEG).
The door moving slow, but it's initial position is different. In this case
it is possible to go directly to the desired corner ( MPEG).

Described above is related to the situation, for which the future trajectory of the
obstacle set is known or predicted before. Let's regard the simplest undecided
situation when the mouse should come from one room corner to another avoiding
snake. The snake goes to the center of the room and then it can change it's
motion direction.
First two results show the mouse path, when it knows before, where the snake to come.
Snake goes right (MPEG). Snake goes left (MPEG). Both trajectories are
optimal in sence of minimal time required to reach the goal.
We see, when the snake comes to it's decision point, at this moment mouse is at
different places in this different cases. Both places are optimal in order to go
further from them, but optimal only in sence of the optimality of the whole
trajctories for which these places belong.
Actually, the mouse have a manifold of possible positions, where it could be
at the decision moment. So let's find a submanifold in this, from which the
mouse can solve first task, and another submanifold, from which the mouse can
solve second task (the last means to cheat the snake if it decided to go left).
The intersection of both is a desired number of positions where the mouse
should wait for the snake making it's decision. Then the mouse succeed to cheat
the snake in both cases.

In results presented below, mouse waits at some point untill the snake turns.
The whole path is usually longer in both cases compared to the cases above.
Snake decide to go right (MPEG). Snake goes left (MPEG).
In oder to find this submanifolds we solve two tasks separately. For each task
we find all possible pathways leading to the solution. And then, exploring all
these pathways starting from the end point we find those which lead to the
possible waiting manifold at time of decision moment. So, we found the first
waiting submanifold. The same should be done for the second one.
Then we solve three tasks: 1. to come from initial point to the waiting point;
2. to find the path from the waiting point to the goal, while snake goes right;
3. to find the path from the waiting point to the goal, while snake goes left.

Last experiments with the system of two degrees of freedom take less then tens
of second for all calculations including connection matrix calculation.
Tests performed under MatLab6.0 on SunUltraSparcII. Usage of vector or
connection machines seems more preferable.

Bratlett W. Mel
"Connectionist Robot Motion Planning
(A Neurally-Inspired Approach to Visiually-Guided Reaching)".
"Perspectives in Arificial Intelligence",
ACADEMIC PRESS, INC. 1990.
Harcourt Brace Jovanovich, Publishers

J. A. Sethian
"Level Set Methods nd Fast Marching Methods".
"Cambridge monographs on applied and computational mathematics, Vol. 3",
CAMBRIDGE UNIVERSITY PRESS, 1999.

John F. Canny
"The complexity of robot motion planning",
(ACM Doctoral Dissertation Award 1987),
The MIT Press, 1988

Jean-Claude Latombe
"Robot motion planning",
(The Kluwer international series in engineering and computer science; SECS 0124).
Kluwer Acad. Publ. 1991

There are a lot of researchers exploring the same approach. Examples are:
HERE, HERE and HERE. (please, try to invent a bike)

Other approaches to path planning:
smth auto-translated in russian
INTAS-BELARUS-97-2028
WSCG'99
GAMM'2000