It is important to understand how to construct a representation of . In some algorithms, especially the combinatorial methods of Chapter 6, this represents an important first step to solving the problem. In other algorithms, especially the sampling-based planning algorithms of Chapter 5, it helps to understand why such constructions are avoided due to their complexity.
The simplest case for characterizing is when for , , and , and the robot is a rigid body that is restricted to translation only. Under these conditions, can be expressed as a type of convolution. For any two sets , let their Minkowski difference^{4.10} be defined as
In terms of the Minkowski difference, . To see this, it is helpful to consider a one-dimensional example.
The Minkowski difference is often considered as a convolution. It can even be defined to appear the same as studied in differential equations and system theory. For a one-dimensional example, let be a function such that if and only if . Similarly, let be a function such that if and only if . The convolution
(4.38) |