References No Title Path Planning for a

Conclusion: Contributions, Difficulties, and Perspectives

 

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.

Performance

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:

1. The fundamental reason is, once again, the NP-completeness of the path planning problem. As deceptive cases may always be designed, the only performance results one may reasonably present are always specific.
2. The three practical reasons are:
1. Obviously, the first requirement for such a comparison is that different algorithms run on the same machines with the same available memory. This may seem simple but it is a main difficulty in our case because our algorithm has been designed to run on rather specific kinds of machines, namely, massively parallel ones. It could also be implemented on non-parallel machines, but then it may lose part of its interest. A fair comparison would be to compare the algorithms on both types of machines. This would imply programming other algorithms in parallel, which is very difficult in practice.
2. Many known path planning algorithms first compute the configuration space (or an approximation of it) off-line, and then efficiently solve the path planning problem on-line. As we saw, in order to deal with a dynamic environment, the Ariadne's clew algorithm adopts a completely different approach.
3. For practical reasons, many test problems are toy problems (2D, few obstacles, few faces, simulated robots) and the performance results using these kinds of problems are very difficult to generalize to realistic industrial problems (3D, tens of obstacles, hundreds of faces, real robots).

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

Generality

 

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.

Acknowledgments

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

References No Title Path Planning for a