The Path Planning Problem No Title No Title

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.

In this paper, we present a new approach to path planning, called the ``Ariadne's clew algorithm ''. The approach is completely general and applies to a broad range of path planning problems. However, it is particularly designed to find paths for robots with many DOF in dynamic environments.

The ultimate goal of a planner is to find a path from the initial position to the target. However, while searching for this path, the algorithm may consider collecting information about the free space and about the set of possible paths that lie in that free space. The Ariadne's clew algorithm tries to do both at the same time: a sub-algorithm called EXPLORE collects information about the free space with increasingly fine resolution, while, in parallel, an algorithm called SEARCH opportunistically checks whether the target can be reached.

The EXPLORE algorithm works by placing landmarks in the searched space in such a way that a path from the initial position to any landmark is known. In order to learn as much as possible about the free space, the EXPLORE algorithm tries to spread the landmarks uniformly all over the space. To do this, it places the landmarks as far as possible from one another. For each new landmark produced by the EXPLORE algorithm, the SEARCH algorithm checks (with a local method) whether the target can be reached from that landmark. Both the EXPLORE and SEARCH algorithms are posed as optimization problems.

The Ariadne's clew algorithm is efficient and general:

1. The algorithm is efficient in two senses:
1. Experiments show that the algorithm is able to solve path planning problems fast enough to move a six DOF arm in a realistic and dynamic environment where another six DOF robot is used as a moving obstacle.
2. It is well suited for parallel implementation and shows significant speed-up when the number of processors increases.
2. The algorithm is general in two senses:
1. It may be used for a wide range of applications in robotics with little additional effort to adapt it.
2. Finally, the algorithm is general in that it may be adapted for a large range of search problems in continuous spaces that arise in fields that are not related to robotics.

The paper is organized as follows. Section 2 presents the path planning problem and discusses related work. Section 3 presents the principle of the Ariadne's clew algorithm. Section 4 describes the application of the algorithm to a six DOF arm in a dynamic environment. Finally, Section 5 concludes the paper with a discussion of the contributions of our approach, the main difficulties involved, and possible improvements of our method.

The Path Planning Problem No Title No Title