Introduction
In his 1984 work, Richard S. Wallace addresses the "findpath" problem—the fundamental challenge of moving a robot from a starting configuration to a goal without colliding with obstacles. While the general "Piano Movers' Problem" is known to be NP-complete, Wallace argues that universal solutions for high-degree-of-freedom (n-dof) robots are often computationally prohibitive. Instead, he proposes that specialized heuristics for specific robotic configurations can yield efficient, practical solutions.
The Three Challenges
Wallace identifies three distinct scenarios where general algorithms struggle:
- Tentacle Manipulators: Flexible, spiral-shaped arms that are difficult to model in traditional configuration spaces (C-space).
- Mobile Robot Navigation: The need for a "Goldilocks" approach that avoids the extreme proximity of Visibility Graphs and the inefficiency of Freeway Algorithms.
- Multi-Arm Coordination: Preventing collisions between two arms without the overhead of a full multi-dimensional search.
Algorithmic Approaches
1. Tentacle Mapping
For a tentacle modeled as a logarithmic spiral ($r = e^{a\phi}$), the primary difficulty lies in mapping obstacles into a usable C-space. Wallace demonstrates that by defining "tentacle obstacles" in position space, they can be transformed into manageable geometric shapes—specifically rectangles with V-notches—within the robot's C-space.
This transformation allows for a closed-form inverse kinematic solution, simplifying pathfinding into a geometric search within a 2D plane.
2. Navigation with Linear Uncertainty Growth
Mobile robots often face positional uncertainty that increases as they move. Wallace introduces the "Not Too Near, Not Too Far" algorithm, which assumes uncertainty grows linearly with distance ($R = kd + r$). By "growing" obstacles into virtual shapes based on this uncertainty, the algorithm turns a probabilistic navigation problem into a deterministic geometric one.
The resulting paths are safer than those generated by standard visibility graphs but remain more efficient than conservative freeway-based methods.
3. Velocity Control for Dual Arms
To coordinate two arms, Wallace simplifies the problem by fixing their spatial paths (e.g., straight lines in joint space). Coordination then becomes a scheduling task in an $s \times t$ space, where $s$ and $t$ represent the progress of each arm. Collisions appear as 2D obstacles in this plane. By adjusting the speed of the arms rather than their paths, the system can efficiently resolve potential conflicts.
Key Insights
The core of Wallace's contribution lies in dimensionality reduction and geometric simplification. By recognizing that "interesting" obstacles in C-space often possess natural properties, researchers can avoid exhaustive searches. Whether it is treating uncertainty as a physical growth of the robot or reducing multi-arm coordination to a 2D traffic control problem, the paper emphasizes that clever heuristics are often superior to brute-force general solvers.
Results and Limitations
The proposed algorithms were implemented in C (tentacle and rover) and Lisp (dual-arm coordination). Simulations confirmed that:
- Spiral manipulators could successfully find collision-free trajectories.
- The rover algorithm produced balanced, safe paths in cluttered environments.
- The $s \times t$ approach quickly identified viable velocity-based solutions for dual-arm systems.
However, these methods have limitations. The tentacle model is restricted to specific spiral functions, and the rover algorithm assumes an omnidirectional base. Furthermore, the dual-arm solution cannot re-route an arm spatially if a velocity adjustment is insufficient to avoid a crash. Future work suggested extending these models to 3D polyhedral links and testing on physical hardware.
Summary updated