14.3.1.3 Collision detection

As in Chapter 5, efficient collision detection algorithms are a key enabler of sampling-based planning. If $X = {\cal C}$, then the methods of Section 5.3 directly apply. If $X$ includes phase constraints, then additional tests must be performed. These constraints are usually given and are therefore straightforward to evaluate. Recall from Section 4.3 that this is not efficient for the obstacle constraints on ${\cal C}$ due to the complicated mapping between obstacles in ${\cal W}$ and obstacles in ${\cal C}$.

If only pointwise tests are performed, the trajectory segment between the points is not guaranteed to stay in ${X_{free}}$. This problem was addressed in Section 5.3.4 by using distance information from collision checking algorithms. The same problem exists for the phase constraints of the form $h_i(x) \leq 0$. In this general form there is no additional information that can be used to ensure that some neighborhood of $x$ is contained in ${X_{free}}$. Fortunately, the phase constraints are not complicated in most applications, and it is possible to ensure that $x$ is at least some distance away from the constraint boundary. In general, careful analysis of each phase constraint is required to ensure that the state trajectory segments are violation-free.

In summary, determining whether $x \in {X_{free}}$ involves

1. Using a collision detection algorithm as in Section 5.3 to ensure that ${\kappa}(x) \in {\cal C}_{free}$.
2. Checking $x$ to ensure that other constraints of the form $h_i(x) \leq 0$ have been satisfied.

Entire trajectory segments should theoretically be checked. Often times, in practice, only individual points are checked, which is more efficient but technically incorrect.