# The  Ariadne'S  Clew   Algorit Hm

Emmanuel Mazer Laboratoire GRAVIR, INRIA 665 Avenue de L'Europe 330 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 EMMANUEL. MAZER@IMAG.FR
JMAL @ MAIL. UD LA P. MX
PIERRE. BESSIERE@IMAG. FR

## Abstract

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.

## 1. Introduction

The path planning problem is of major interest for industrial robotics. A basic version of this problem consists of finding a sequence of motions for a robot from a start configuration to a given goal configuration while avoiding collisions with any obstacles in the environment.

A simple version of the problem, that of planning the motion of a point robot among 3-dimensional polyhedral obstacles, has been proved to be NP-complete (Canny, 1988). Generally speaking, the complexity of the problem is exponential in the number of degrees of freedom ( DOF ) of the robot, and polynomial in the number of obstacles in the environment. Consequently, finding a path for a robot with many DOF (more than five) in an environment with several obstacles is, indeed, a very difficult problem. Unfortunately, many realistic industrial problems deal with robots of at least six DOF and hundreds of obstacles. Even worse, often the environment is dynamic in the sense that some of the obstacles may move, thereby further requiring that new paths be found in very short computing times.