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 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