Interference Detection and Collision Avoidance Among Three Dimensional Objects

Narendra Ahuja, Robert T. Chien, R. Yen, N. BridwellAAAI 1980

In the early 1980s, robotics faced a significant hurdle known as the "Piano Mover’s Problem." Finding a collision-free path for a robot in a cluttered environment required immense computational power that was simply unavailable at the time. This seminal paper from the 1980 AAAI proceedings proposed two efficient strategies for 3D interference detection—the process of determining if two volumes occupy the same space—tailored for the limited hardware of the era.

The Planar Projection Method

The first strategy, often called the "Shadow Method," simplifies the complex 3D problem by projecting polyhedral objects onto 2D planes. The core logic is straightforward: if the 2D shadows of two objects do not overlap on even a single plane, the objects themselves cannot possibly be in contact.

A 3D object projected onto a 2D plane to simplify interference detection.

To handle complex, non-convex shapes, the authors suggest decomposing them into convex polygons or using convex hulls. This approach provides a "conservative" check. While it might occasionally produce a false alarm (indicating a collision where none exists), it guarantees that no actual collision will be missed. This safety-first approach is crucial for real-world robotic manipulation, where a crash is far more costly than a detour.

The Octree Method

The second approach utilizes a hierarchical 3D grid known as an "octree." In this method, the entire workspace is treated as a large cube. If an object partially fills this cube, the space is recursively subdivided into eight smaller octants.

Hierarchical subdivision of a 3D space into an octree structure.

Each node in the resulting tree is labeled as Black (full), White (empty), or Grey (partially full). To detect interference between two objects, their respective octrees are traversed in parallel. If a location is found where both trees contain Black nodes, an intersection is confirmed. This method is highly efficient because it allows the system to quickly discard large volumes of empty space (White nodes), focusing computational power only on areas where objects are actually present.

Key Insights for Robotics

Beyond specific algorithms, the paper introduces several foundational concepts for motion planning:

  • Interference vs. Collision: The authors define interference as a static spatial check, while collision is a dynamic event. They argue that collision detection can be effectively modeled as a sequence of interference checks over time.
  • The Conservative Criterion: Safety is prioritized. The authors advocate for methods that ensure no real collisions are missed, even at the cost of occasional false positives.
  • Growing Obstacles: To account for physical constraints like braking distance and safety margins, the authors propose "growing" obstacles by a distance d. If a robot's path intersects this expanded boundary, it triggers a warning to decelerate or re-route.

Conclusion and Limitations

While groundbreaking, these methods faced practical challenges. Octrees, for instance, must be entirely recalculated if an object rotates or moves, which was computationally taxing for high-speed manipulation. Furthermore, translating between the Cartesian coordinates of octrees and the joint-angle coordinates of robotic arms remains complex. Despite these hurdles, the paper's emphasis on dimensionality reduction and hierarchical modeling laid the groundwork for modern spatial reasoning in robotics.

Summary updated

BibTeX
@inproceedings{ahuja1980interference,
  author = {Narendra Ahuja and Robert T. Chien and R. Yen and N. Bridwell},
  title = {{Interference Detection and Collision Avoidance Among Three Dimensional Objects}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1980},
}
Figure