14.1.3.2 The region of inevitable collision

One of the most challenging aspects of planning can be visualized in terms of the region of inevitable collision, denoted by ${X_{ric}}$. This is the set of states from which entry into ${X_{obs}}$ will eventually occur, regardless of any actions that are applied. As a simple example, imagine that a robotic vehicle is traveling $100$ km/hr toward a large wall and is only $2$ 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, ${X_{ric}}$ and ${X_{obs}}$ are approximately the same; however, ${X_{ric}}$ grows dramatically as the speed increases.

Let ${\cal U}_\infty$ denote the set of all trajectories ${\tilde{u}}: [0,\infty) \rightarrow U$ for which the termination action $u_T$ is never applied (we do not want inevitable collision to be avoided by simply applying $u_T$). The region of inevitable collision is defined as

$$X_{ric} = \{x(0) \in X \;\vert\; {\tilde{u}}\in {\cal U}_\infty \;,\; \exists t>0 x(t) \in X_{obs}\} ,$$ (14.3)

in which $x(t)$ is the state at time $t$ obtained by applying (14.1) from $x(0)$. 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 ${X_{ric}}$. For driftless systems, ${X_{ric}}= {X_{obs}}$.

Figure 14.3: The region of inevitable collision grows quadratically with the speed.

Example 14..1 (Region of Inevitable Collision)   Figure 14.3 shows a simple illustration of ${X_{ric}}$. Suppose that ${\cal W}= {\mathbb{R}}$, and the robot is a particle (or point mass) that moves according to the double integrator model ${\ddot q} = u$ (for mass, assume $m = 1$). For simplicity, suppose that $u$ represents a force that must be chosen from $U = [-1,1]$. The C-space is ${\cal C}= {\mathbb{R}}$, the phase space is $X = {\mathbb{R}}^2$, and a phase (or state) is expressed as $x = (q,{\dot q})$. Suppose that there are two obstacles in ${\cal C}$: a point and an interval. These are shown in Figure 14.3 along the $q$-axis. In the cylinder above them, ${X_{obs}}$ appears. In the slice at ${\dot q}= 0$, ${X_{ric}}= {X_{obs}}= {\cal C}_{obs}$. As ${\dot q}$ increases, ${X_{ric}}$ becomes larger, even though ${X_{obs}}$ remains fixed. Note that ${X_{ric}}$ only grows toward the left because ${\dot q}> 0$ indicates a positive velocity, which causes momentum in the positive $q$ direction. As this momentum increases, the distance required to stop increases quadratically. From a speed of ${\dot q}= v$, the minimum distance required to stop is $v^2/2$, which can be calculated by applying the action $u = -1$ and integrating ${\ddot q} = u$ twice. If ${\dot q}> 0$ and $q$ is to the right of an obstacle, then it will safely avoid the obstacle, regardless of its speed. If ${\dot q}< 0$, then ${X_{ric}}$ extends to the right instead of the left. Again, this is due to the required stopping distance. $\blacksquare$

In higher dimensions and for more general systems, the problem becomes substantially more complicated. For example, in ${\mathbb{R}}^2$ the robot can swerve to avoid small obstacles. In general, the particular direction of motion becomes important. Also, the topology of ${X_{ric}}$ may be quite different from that of ${X_{obs}}$. 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 ${X_{ric}}$. 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, ${X_{ric}}$ is not computed because it is too complicated.^14.3 It is not even known how to make a ``collision detector'' for ${X_{ric}}$. By working instead with ${X_{obs}}$, challenges arise due to momentum. There may be large parts of the state space that are never worth exploring because they lie in ${X_{ric}}$. Unfortunately, there is no practical way at present to accurately determine whether states lie in ${X_{ric}}$. As the momentum and amount of clutter increase, this becomes increasingly problematic.