One of the most challenging aspects of planning can be visualized in
terms of the *region of inevitable collision*, denoted by .
This is the set of states from which entry into will
eventually occur, regardless of any actions that are applied. As a
simple example, imagine that a robotic vehicle is traveling
km/hr toward a large wall and is only meters away. Clearly the
robot is doomed. Due to momentum, collision will occur regardless of
any efforts to stop or turn the vehicle. At low enough speeds,
and are approximately the same; however, grows
dramatically as the speed increases.

Let
denote the set of all trajectories
for which the termination action is
*never* applied (we do not want inevitable collision to be avoided
by simply applying ). The *region of inevitable collision*
is defined as

for any such that | (14.3) |

in which is the state at time obtained by applying (14.1) from . This does not include cases in which motions are eventually blocked, but it is possible to bring the system to a state with zero velocity. Suppose that the Dubins car from Section 13.1.2 is used and the car is unable to back its way out of a dead-end alley. In this case, it can avoid collision by stopping and remaining motionless. If it continues to move, it will eventually have no choice but to collide. This case appears more like being trapped and technically does not fit under the definition of . For driftless systems, .

In higher dimensions and for more general systems, the problem becomes substantially more complicated. For example, in the robot can swerve to avoid small obstacles. In general, the particular direction of motion becomes important. Also, the topology of may be quite different from that of . Imagine that a small airplane flies into a cave that consists of a complicated network of corridors. Once the plane enters the cave, there may be no possible actions that can avoid collision. The entire part of the state space that corresponds to the plane in the cave would be included in . Furthermore, even parts of the state space from which the plane cannot avoid entering the cave must be included.

In sampling-based planning under differential constraints, is
not computed because it is too complicated.^{14.3} It is not even known how to make a ``collision
detector'' for . By working instead with , challenges
arise due to momentum. There may be large parts of the state space
that are never worth exploring because they lie in .
Unfortunately, there is no practical way at present to accurately
determine whether states lie in . As the momentum and amount
of clutter increase, this becomes increasingly problematic.

Steven M LaValle 2012-04-20