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.
Emmanuel Mazer
Juan Manuel
Ahuactzin
Pierre Bessière
Laboratoire Gravir,
INRIA 665 Avenue de l'Europe 38330 Montbonnot (France)
Emmanuel.Mazer@imag.fr
Depto. de Ing. en Sistemas Computationales
Unversidad de las Americas Puebla, Cholula, Puebla 72820, Mexico
jmal@mail.udlap.mx
Laboratoire LEIBNIZ,
46 Avenue Felix Viallet, 38000, Grenoble, France
Pierre.Bessiere@imag.fr
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.