Path Planning for Highly Redundant Manipulators Using a Continuous Model

Akira Hayashi, Benjamin KuipersAAAI 1991

Introduction

Planning the movement of "highly redundant" manipulators—robots with many more degrees of freedom (DOF) than required for a task, such as snake-like robots or elephant trunks—presents a significant computational challenge. Traditional configuration space approaches are PSPACE-complete, meaning planning time grows exponentially with the number of joints. This "curse of dimensionality" often renders such robots impractical for complex, cluttered environments like nuclear reactors or spacecraft interiors. This paper introduces a "continuous model" heuristic that reduces planning complexity from exponential in the number of joints to polynomial in the complexity of the environment.

The Continuous Manipulator Model

The core innovation is treating the robot as a smooth, continuous curve rather than a collection of discrete joints. By employing differential geometry, specifically the Frenet equations, the robot's shape is defined by its curvature ($\kappa$) and torsion ($\tau$) along its length. This allows the entire robot to be manipulated as a single mathematical entity.

The relationship between a robot's spatial configuration and its intrinsic curvature function.

To make this model computable, the curvature function is discretized using five points per segment. This representation enables the use of specialized "motion schemas"—building block behaviors such as hill-climbing for tip positioning, feed/retract for follow-the-leader movement through narrow gaps, and fold/unfold for managing length in open spaces.

Algorithmic Approach

The planning process involves two primary stages:

  1. Environment Decomposition: The free space is partitioned into Primary Convex Regions (PCRs). The system then utilizes the A* algorithm to find a sequence of these regions that connects the start and goal positions.
  2. Path Smoothing: To ensure the path is physically realizable, cubic spiral curves are used to connect the regions, maintaining continuous curvature throughout the trajectory.

A critical theoretical contribution is the "Mapping Bridge" (Proposition 2). The authors mathematically prove that a continuous curve can be mapped back onto a physical jointed arm with a predictable maximum error. By slightly "growing" obstacles in the map (by approximately 22% of a link's length), the system guarantees that the physical robot will remain collision-free.

Key Results and Performance

The algorithm was evaluated using a 2D simulator featuring various cluttered environments. Despite the high DOF of the simulated robots, the system found paths in 11 to 119 seconds on 1991-era hardware—a task that would be computationally intractable for traditional discrete methods.

Sequence showing a redundant manipulator navigating a cluttered environment with corresponding curvature plots.

The results demonstrate that redundancy can be treated as a resource rather than a burden. By adopting a "macroscopic shape," the robot can simplify obstacle avoidance. The use of Curvature Segment Types also allowed the hill-climbing heuristic to effectively avoid local minima, a common failure point for potential field methods.

Limitations and Future Work

While the mathematical framework supports 3D movement (via torsion), the primary simulations were conducted in 2D. Additionally, the current implementation for identifying PCRs is optimized for rectangular obstacles and assumes a static environment. Future research could integrate more advanced computational geometry for path planning and address dynamic environments with real-time sensor integration.

Summary updated

BibTeX
@inproceedings{hayashi1991path,
  author = {Akira Hayashi and Benjamin Kuipers},
  title = {{Path Planning for Highly Redundant Manipulators Using a Continuous Model}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1991},
}
Figure