A Simple Motion Planning Algorithm for General Robot Manipulators

Tomás Lozano-Pérez

Abstract

This paper presents a simple and efficient algorithm, using configuration space, to plan collision-free motions for general manipulators. We describe an implementation of the algorithm for manipulators made up of revolute joints. The configuration-space obstacles for an n degree-of-freedom manipulator are approximated by sets of n - 1 dimensional slices, recursively built up from one dimensional slices. This obstacle representation leads to an efficient approximation of the free space outside of the configuration-space obstacles.

Introduction

In the mid-1980s, the "Find-Path" problem—determining a collision-free trajectory from a starting point to a goal—remained a significant hurdle in robotics. While exact mathematical solutions existed, they were often computationally prohibitive for high-degree-of-freedom (DOF) systems like the 6-link PUMA arm. The core difficulty lies in the transition from workspace (the physical 3D environment) to configuration space (C-space), where the robot's state is defined by its joint angles. In C-space, simple workspace obstacles transform into complex, non-linear "forbidden zones." This paper introduces a practical algorithm that utilizes recursive slicing to approximate these C-space obstacles, transforming a complex geometric problem into an efficient search task.

Methodology

The proposed algorithm relies on representing the robot's free space through a discretized approximation of C-space obstacles.

C-Space Mapping and Representation

Instead of performing collision checks directly in 3D workspace coordinates, the algorithm maps obstacles into the robot's joint-parameter space. As shown in Figure 2, a simple obstacle in the workspace (a) corresponds to a complex region in the 2D C-space of a two-link manipulator (b).

Mapping workspace obstacles (a) to configuration space (b).

Recursive Slice Projection

To manage the complexity of high-dimensional spaces, the algorithm employs a Recursive Slice Projection method. For an $n$-DOF robot, the algorithm fixes $n-1$ joint angles and identifies the ranges of the $n^{th}$ joint that result in a collision. These 1D "slices" are recursively aggregated to form $(n-1)$-dimensional volumes. This process effectively reduces the problem into a tree-like data structure where the leaves represent valid joint ranges.

The recursive slice projection method: decomposing high-dimensional C-space obstacles into 1D intervals.

The algorithm explicitly characterizes the "free space" as a collection of Regions. Each region contains a Kernel—a rectangular sub-region of guaranteed free space. By discretizing the free space into a "region graph," the path planning problem is reduced to an A* search. This search finds the optimal sequence of regions to traverse from the start configuration to the goal.

Evaluation and Results

The algorithm was evaluated using simulated polyhedral environments and models of real-world robots, including a two-link planar manipulator and a six-link PUMA arm with a three-fingered hand.

  • Efficiency: For a 2-link manipulator, the algorithm planned paths in approximately 6 seconds on a Symbolics 3600 Lisp Machine.
  • Generality: The method successfully handled complex 6-DOF systems in cluttered environments, demonstrating its applicability to industrial manipulators.
  • Robustness: The slice-based approach proved capable of handling arbitrary non-convex polyhedral obstacles, a significant improvement over contemporary methods.

Discussion and Insights

A key insight of this work is that quantization acts as a powerful enabler. By accepting a minor loss in precision through joint angle discretization, the algorithm replaces complex intersection equations with simple linear range arithmetic, drastically increasing speed. Furthermore, the author observed that path computation time was comparable to the time required for 3D graphical rendering, establishing a new benchmark for "practical" performance.

However, the algorithm faces the "curse of dimensionality," as execution time grows exponentially with the number of joints. For 6+ DOF systems, the author suggests decoupling the problem—planning for the primary arm links first and treating the wrist/hand as a simplified bounding box. Additionally, the current implementation is limited to static environments; dynamic obstacles would require real-time recomputation of the C-space representation.

Summary updated

Abstract

This paper presents a simple and efficient algorithm, using configuration space, to plan collision-free motions for general manipulators. We describe an implementation of the algorithm for manipulators made up of revolute joints. The configuration-space obstacles for an n degree-of-freedom manipulator are approximated by sets of n - 1 dimensional slices, recursively built up from one dimensional slices. This obstacle representation leads to an efficient approximation of the free space outside of the configuration-space obstacles.
BibTeX
@inproceedings{lozanoperez1986simple,
  author = {Tomás Lozano-Pérez},
  title = {{A Simple Motion Planning Algorithm for General Robot Manipulators}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1986},
  url = {https://openreview.net/forum?id=HJVUykWObS},
}
Figure