Journal of Artificial Intelligence Research, 9 (1998) 295-316. Submitted 10/97; published 11/98
© 1998 AI Access Foundation and Morgan Kaufmann Publishers. All rights reserved.
INRIA 665 Avenue de l'Europe 38330 Montbonnot (France)
Depto. de Ing. en Sistemas Computationales
Unversidad de las Americas Puebla, Cholula, Puebla 72820, Mexico
46 Avenue Felix Viallet, 38000, Grenoble, France
We present a new approach to path planning, called the Ariadne's clew algorithm. It is designed to find paths in high-dimensional continuous spaces and applies to robots with many degrees of freedom in static, as well as dynamic environments --- ones where obstacles may move. The Ariadne's clew algorithm comprises two sub-algorithms, called SEARCH and EXPLORE, applied in an interleaved manner. EXPLORE builds a representation of the accessible space while SEARCH looks for the target. Both are posed as optimization problems. We describe a real implementation of the algorithm to plan paths for a six degrees of freedom arm in a dynamic environment where another six degrees of freedom arm is used as a moving obstacle. Experimental results show that a path is found in about one second without any pre-processing.