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.

The Ariadne's Clew Algorithm next up previous
Next: Introduction

The Ariadne's Clew Algorithm

Emmanuel Mazer
Laboratoire Gravir,
INRIA 665 Avenue de l'Europe 38330 Montbonnot (France)

Juan Manuel Ahuactzin
Depto. de Ing. en Sistemas Computationales
Unversidad de las Americas Puebla, Cholula, Puebla 72820, Mexico

Pierre Bessière
Laboratoire LEIBNIZ,
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.

Emmanuel Mazer
Tue Nov 10 17:28:31 MET 1998