Next: The Path Planning Problem Up: No Title Previous: No Title
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:
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.