Suppose that the robot is a collection of attached links,
, and that has connected components.
For this complicated situation, collision detection can be viewed as
a two-phase process.
- Broad Phase: In the
broad phase, the task is
to avoid performing expensive computations for bodies that are far
away from each other. Simple bounding boxes can be placed around each
of the bodies, and simple tests can be performed to avoid costly
collision checking unless the boxes overlap. Hashing schemes can be
employed in some cases to greatly reduce the number of pairs of boxes
that have to be tested for overlap . For a robot that
consists of multiple bodies, the pairs of bodies that should be
considered for collision must be specified in advance, as described in
- Narrow Phase: In
the narrow phase,
individual pairs of bodies are each checked carefully for collision.
Approaches to this phase are described in Sections 5.3.2
Steven M LaValle