Introduction
In the early days of robotics research, Shriram M. Udupa (1977) addressed a fundamental challenge: path planning for multi-link manipulators in cluttered environments. At the time, calculating collision-free trajectories for a 6-degree-of-freedom (DOF) arm, such as the Scheinman Arm, was computationally prohibitive. The complexity arose from the non-convex "trajectory envelope" swept by the arm, which had to be checked against arbitrary polygonal obstacles in real-time on limited hardware like the DEC PDP-10.
Hierarchical Problem Spaces
Udupa’s primary contribution was a hierarchical decomposition that simplified 3D collision avoidance. By abstracting the robot and its environment into different "problem spaces," the system could plan trajectories using simple geometric primitives rather than complex 3D volumes.
As illustrated in the table above, the approach utilizes three distinct levels of abstraction:
- Real Problem Space: The physical reality where the robot and obstacles are modeled as 3D cylinders and polyhedra.
- Primary Problem Space: Obstacles are "grown" by the radius of the robot's links, allowing the links to be treated as simple line segments.
- Secondary Problem Space: Obstacles are further expanded by the length of the forearm, enabling the "boom" (the main arm segment) to be treated as a single moving point.
Navigational Space and Planning Heuristics
The system represents guaranteed empty space through "Charts" within a "Navspace" (Navigational Space). These charts consist of "sectoroids" or "pases"—geometric boxes defined in polar or spherical coordinates.
The planning process employs a "Boom-First" heuristic to reduce search complexity:
- Mid-section Planning: A path for the boom tip is first planned in the secondary chart where the boom is treated as a point.
- Forearm Planning: The forearm's orientation is then "juggled" along this path to avoid collisions, using "pgram" (parallelogram) and "circle/sphere" motion primitives.
- Terminal Phase: Near start and goal positions, where the robot is in close proximity to obstacles, the system switches to a granular "adjust and move" strategy.
Key Insights and Legacy
Udupa’s work pioneered several concepts that remain central to modern robotics:
- Obstacle Expansion: This was one of the earliest formalizations of what is now known as Configuration Space (C-space), transforming the problem of moving a complex shape into the simpler problem of moving a point.
- Selective Refinement: Instead of high-resolution mapping of the entire environment, the system only performs detailed refinement in areas where the robot must maneuver closely to an obstacle.
- Infrequent Environment Initialization: The assumption that the overall layout changes slowly justifies the one-time computational cost of generating complex empty-space Charts.
Results and Limitations
The hierarchical approach successfully reduced 3D collision detection into a sequence of simpler 2D and 1D problems. The algorithm proved robust enough to handle concave obstacles and narrow passages via recursive splitting of trajectory segments. While implemented in the SAIL programming language and validated through simulations of the 6-DOF Stanford Arm, the system was primarily designed for static environments and small payloads. Future work suggested integrating proximity sensors to handle the "terminal phase" more fluidly and extending the logic for larger transported objects.
Summary updated