Next: Principle of the Ariadne's Up: No Title Previous: Introduction
Next: Principle
of the Ariadne's Up: No
Title Previous: Introduction
Many versions of the path planning problem exist. An exhaustive classification of these problems and of the methods developed to solve them can be found in a survey by Hwang and Ahuja [1992]. We choose to illustrate our discussion with a particular case. A robot arm is placed among a set of obstacles. Given an initial and a final position of the robot arm, the problem is to find a set of motions that will lead the robot to move between the two positions without colliding with the obstacles.
To drive the robot amidst the obstacles, early methods [Brooks 1983] directly used the 3D CAD models of the robot and of the obstacles to find a solution, i.e., they considered the ``operational 3D space''. In this space, the path planning problem consists of finding the movements of a complex 3D structure (the robot) in a cluttered 3D space.
A major advance was to express the problem in another space known as
the configuration space, denoted by 
[Lozano-Pérez 1987]. In
this space, the position (or configuration) of a robot is completely determined
by a single point having n independent parameters as coordinates.
The positions that are not physically legal (because of a collision) are
represented by particular regions of
, and are called 
. In the configuration space, the path planning problem consists of finding
a continuous curve (representing a path for a single geometrical point)
that (i) connects the points representing the initial and the final configuration
of the robot, and (ii) does not intersect any
. This method trades a simplification of the path planning problem (it
searches a path for a single point) against a higher-dimensional search
space (the dimension of
is the number DOF of the robot) and against more complex
shapes of obstacles (very simple physical obstacles may result in very
complex
).
For example, let us consider the planar arm of Figure 1.
Its position among the obstacles is totally known once the values of the
angles between its links 
are known. Thus, for each pair
, it is possible to decide whether the robot collides with the surrounding
obstacles. This is what we did in Figure 2
to represent the mapping between the physical obstacles in the operational
space and the
. Now, by moving a point along the curve joining 
and 
one will also define a collision-free motion for the planar arm between
the corresponding positions 
and 
in the operational space. This curve is one solution to this particular
path planning problem.
A recent trend in the field is to consider the ``trajectory space'' [Ferbach
1996] where a whole path is represented by a single point. The coordinates
of this point are the values of the parameters defining the successive
movements of the robot. For instance, the list of successive commands sent
to the robot controller indeed encode an entire path of the robot. In this
space, the path planning problem is reduced to the search for a single
point. Once again, we trade a simplification of the path planning problem
(searching for a point) against a higher dimension of the search space
(the dimension of the trajectory space is the number of parameters needed
to specify completely a whole path). For example, in Figure 2,
the path between 
and 
can be represented by a point in a seven-dimensional space simply by considering
the length of its seven segments.
Figure 1: A two DOF arm placed among obstacles
in the operational space
Figure: The configuration space corresponding to Figure 1.
Note: (1)
is a torus, (2) it is divided into two regions 
and 
that cannot be connected by a continuous path, and (3) there is not a
-obstacle for 
because it does not interfere with the arm.
Global approaches are classically divided into two main classes: (i) retraction methods, and (ii) decomposition methods. In the retraction methods, one tries to reduce the dimension of the initial problem by recursively considering sub-manifolds of the configuration space. In the decomposition methods, one tries to characterize the regions of the configuration space that are free of obstacles. Both methods end up with a classical graph search over a discrete space. In principle, these methods are complete because they will find a path if one exists and will still terminate in a finite time if a path does not exist. Unfortunately, computing the retraction or the decomposition graph is an NP-complete problem: the complexity of this task grows exponentially as the number of DOF increases [Canny 1988]. Consequently, these planners are used only for robots having a limited number (three or four) of DOF. In addition, they are slow and can only be used off-line: the planner is invoked with a model of the environment, it produces a plan that is passed to the robot controller which, in turn, executes it. In general, the time necessary to achieve this is not short enough to allow the robot to move in a dynamic environment.
One way to combat the complexity of the problem is to trade completeness against performance. To do this, the local planners are guided by the gradient of a cost function (usually the Euclidean distance to the goal) and take into account the constraints introduced by the obstacles to avoid them [Faverjon Tournassoud 1987]. Since the path planning problem is NP-complete, knowing the cost function, it is always possible to design a deceptive environment where the method will get trapped in a local minimum. However, these methods are useful in many industrial applications because they can deal with complex robots and environment models having thousands of faces, that are often too time-consuming for global methods.
The stochastic or random approach was first introduced by Barraquand and Latombe [1990], and later used by Overmars [1992], and more recently by Kavraki [1996]. The main idea behind these algorithms is to build a graph in the configuration space. The graph is obtained incrementally as follows: a local planner is used to try to reach the goal. Should the motion stop at a local minimum, a new node (or landmark) is created by generating a random motion starting from that local minimum. The method iterates these two steps until the goal configuration has been reached from one of these intermediary positions by a gradient descent motion. These algorithms work with a discretized representation of the configuration space. They are known to be probabilistically complete because the probability of terminating with a solution (a path has been found or no path exists) converges to one as the allowed time increase towards infinity. As in the previous section, it is also possible to design simple deceptive environments that will make this kind of algorithm slower than a pure random approach. However, they have been tested for robots with a high number of DOF and they have been shown to work quickly in relatively complex and natural environments.
Other methods using landmarks have been devised. For example, SANDROS, introduced by Chen and Hwang[Hwang 1992], makes use of landmarks to approximate the free space. This approach is similar to the ``hierarchical planning'' approach used in AI: should the method fail to reach a goal, new subgoals are generated until the problem is easy enough to be solved. In their approach, first a local planner is used to reach the final position: should the local planner fail, the configuration space is divided into two subspaces, one containing the goal and the other a new sub-goal. The problem is therefore divided into two sub-problems: (i) going from the initial position to the subgoal, and (ii) going from the subgoal to the final position. SANDROS has been shown to be particularly well adapted to find paths for manipulators. It has been implemented and tested for planning paths for Puma and Adept robots.
The previous methods were essentially based on the configuration space:
the retraction, the decomposition, or the optimization is made in this
space. An alternative is to consider the ``trajectory space''. For example,
in his method VDP, Ferbach [Ferbach
1996] starts by considering the straight line segment joining the initial
and the final configuration in
. This path is progressively modified in such a manner that the forbidden
regions it crosses are reduced. At each iteration, a sub-manifold of
containing the current path is randomly generated. It is then discretized
and explored using a dynamic programming method that uses the length across
the forbidden region as the cost function in order to minimize. The search
results in a new trajectory whose intersection with the forbidden regions
is smaller than the original trajectory. The process is repeated until
an admissible trajectory is found. As in the previous sections, it is also
possible to design simple deceptive environments that will make this kind
of algorithm slower than a pure random approach.
The work of Lin, Xiao, and Michalewicz [1994] is similar to our approach. As in an early version of our algorithm [Ahuactzin, Mazer, Bessière, Talbi 1992], genetic algorithms are used to carry out optimization in the trajectory space. Trajectories are parameterized using the coordinates of intermediary via-points. An evolutionary algorithm is used to optimize a cost function based on the length of the trajectory and the forbidden region crossed. The standard operators of the genetic algorithms have been modified and later extended to produce a large variety of paths [Xiao, Michalewicz, Zhang 1996]. The number of intermediary via-points is fixed and chosen using an heuristic. Given this number, nothing prevents to design a deceptive problem which solution will require more intermediary points, leading the algorithm to fail while one solution exists.