Next: References Up: No Title Previous: Path Planning for a
As mentioned in the Introduction, the Ariadne's clew algorithm has two main qualities: efficiency, and generality. Let us, in conclusion, explain and discuss these two qualities.
Comparing the performance of this kind of algorithm is a very delicate subject. Performance may be a matter of computing time, efforts needed to program, or ease of application to different problems (see Section 5.2). Evaluating the performance in terms of computing time is very difficult for one fundamental and three practical reasons:
Considering all these reasons, we tested our algorithm by implementing a realistic robotic application to the very end. To achieve this goal, we assembled a complex experimental setup including six different machines (1 MEGANODE, 2 68030, 2 SUN 4, and 1 SILICON GRAPHICS), two mechanical arms, and running seven different cooperative programs (2 KALI, 1 ACT, 2 VXWORKS, 1 PARX, and 1 Ariadne's clew algorithm).
Our challenge was to be able to solve the path planning problem fast enough to drive a real six DOF arm in a dynamic environment. The Ariadne's clew algorithm indeed achieved this goal in our experiments where the environment is composed of five fixed obstacles and a six DOF arm moving independently.
We are not aware of any other methods capable of such performance. To the best of our knowledge, currently implemented planners would take a number of seconds (ten) to place a set of landmarks on a 2D example for a robot with five DOF [Kavraki, Svestka, Latombe, Overmars 1996]. Despite the fact that finding a general purpose planning technique for real industrial application is a very difficult problem, we believe that the Ariadne's clew algorithm provides an effective approach to such problems.
The number of range computations for a Manhattan motion of order 1 is where n is the number of faces, k the number of DOF, and C a constant factor, depending on the number of parts used to model the robot. Obviously, such a number of faces may be a severe difficulty for the implementation of the Ariadne's clew algorithm described so far. To speed up the computation we use a number of geometric filters that reduce the number of pairs of entities to be analyzed.
However, it was possible to follow two research tracks in combination. First, we could use collision checking methods that allow access to the pairs in collision in a logarithmic time [Faverjon Tournassoud 1987]. Second, we could preserve part of the landmark graph when the environment is changing [McLean Mazon 1996].
The Ariadne's clew algorithm is general in the sense that it may be used for numerous and very different applications in robotics. Basically, the main thing that needs to be changed in the algorithm is the distance d used in the evaluation functions of the two optimization problems.
Several planners have been implemented in this way: a fine motion planner [De la Rosa, Laugier, Najera 1996], two motion planners for holonomic and non-holonomic mobile robots [Scheuer Fraichard 1997], a reorientation planner for an articulated hand[Gupta 1995], a planner for grasping and regrasping [Ahuactzin, Gupta, Mazer 1998], and a planner for a robotic arm placed in the steam generator of a nuclear plant [McLean Mazon 1996]. Adapting the algorithm to a new application is, therefore, clearly a very easy task. For instance, the application to path planning for the non-holonomic trailer was developed in three days.
The Ariadne's clew algorithm is also general in the sense that it may be used for any kind of path planning problem in a continuous space, in fields other than robotics. Although it may be sufficient to change the distance function d, one may also consider changing the form of the function d, or even the nature of the searched spaces. For instance, the concept of obstacles may be reconsidered. Instead of ``hard'' obstacles, one could replace them by zones of constraints. In that case, the path planning problem does not consist of finding a path without collisions but rather finding a path best satisfying the different constraints. Such a planner has been developed for a naval application where the problem was to find a path for a boat with various constraints on the trajectory. This opens numerous perspectives of applications for applying the Ariadne's clew algorithm in a broader field than pure robotics.
The authors are greatly indebted to Dr. Kamal Gupta from Simon Fraser University who carefully read the paper and suggested valuable corrections that greatly improve the quality of the final paper.
This work has been made possible by: Le Centre National de la Recherche Scientifique (France), Consejo Nacional de Ciencia y Tecnologia (Mexico) and ESPRIT 2, P2528 (EEC).