Abstract
This paper, originally presented at AAAI in 1983, describes a computationally efficient method for planning the "gross motion" of a PUMA-style robot arm. By representing free space as a series of overlapping "freeways" and decomposing the robot into manageable segments, the algorithm circumvents the computational complexity typically associated with high-degree-of-freedom (DOF) motion planning. The approach demonstrated the ability to find complex, collision-free paths in under a minute on contemporary hardware.
Introduction
In the early 1980s, motion planning—then referred to as the "find-path" problem—was a significant bottleneck in robotics. While Cartesian robots moving along linear axes were relatively easy to manage, revolute robots like the PUMA presented non-linear relationships between joint angles and physical space. Existing methods often relied on memory-intensive grid tessellations or were limited to simple geometries. Rodney Brooks proposed a practical alternative capable of navigating a 6-jointed arm through cluttered workspaces containing tables and hanging fixtures without requiring excessive processing power.
Methodology
The core of the algorithm lies in two primary concepts: Freeway Representation and Constraint Propagation.
Freeway Representation
Instead of modeling obstacles directly, the algorithm models the "free space" as a set of overlapping channels called freeways. Each freeway is defined by a straight axis (or spine) and a "left and right radius" that indicates the available clearance from obstacles. This inversion of the search space significantly reduces the complexity of finding a path.
Decomposition and C-Space Mapping
The robot is decomposed into three components: the upper arm, the forearm, and the payload ensemble (wrist and hand). The planner first maps the upper arm's obstacles into a 2D Configuration Space (C-space) based on the first two joint angles ($\phi$ and $\alpha$). This transforms a 3D collision problem into a 2D search for a path through rectangular "free" regions in joint-space.
Radius Functions and Hierarchical Search
To manage the payload, Brooks introduced a "radius function" $R(\theta)$ to describe the object's shape, allowing for rapid calculation of safe orientations within a freeway. The planner follows a hierarchical search: it first identifies a path for the upper arm, uses those constraints to guide a depth-first search for the payload's path, and finally verifies the forearm's clearance.
Results
The algorithm was evaluated in a simulated environment featuring various prismatic obstacles, including tables and hanging fixtures. A key result was the successful planning of a complex path—requiring the robot to duck under a hanging obstacle while rotating its payload—in less than one minute. This was achieved on an original MIT Lisp Machine, which lacked dedicated floating-point hardware, proving the algorithm's practical viability for real-world assembly tasks compared to theoretical $O(n^{64})$ approaches of the era.
Limitations and Future Work
While effective, the 1983 implementation included several simplifications:
- Reduced DOF: The problem was effectively reduced to 4-DOF by locking joint 4 and coupling joint 5 to joints 2 and 3 to maintain a vertical payload axis.
- Geometric Constraints: Obstacles were assumed to be vertical prisms, and the payload was restricted to horizontal or vertical translations and rotations around the vertical axis.
- Convexity: Non-convex obstacles required decomposition into overlapping convex prisms.
Brooks noted that future work would involve integrating stereo overhead cameras to automatically extract these prismatic obstacle descriptions from the environment.
Summary updated