4.3.2 Explicitly Modeling
: The Translational Case
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
The simplest case for characterizing
, , and , and the robot is a rigid body that is
restricted to translation only. Under these conditions,
be expressed as a type of convolution. For any two sets
, let their Minkowski difference4.10 be defined as
in which is just vector subtraction on
. The Minkowski
difference between and can also be considered as the Minkowski
sum of and . The Minkowski sum is obtained
by simply adding elements of and in (4.37), as
opposed to subtracting them. The set is obtained by replacing
each by .
In terms of the Minkowski difference,
see this, it is helpful to consider a one-dimensional example.
(One-Dimensional C-Space Obstacle)
In Figure 4.12
, both the robot
are intervals in a one-dimensional world,
. The negation,
, of the robot is shown as the interval
. Finally, by applying the Minkowski sum to
the C-space obstacle,
, is obtained.
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
. Similarly, let
function such that if and only if
A one-dimensional C-space obstacle.
yields a function , for which if
, and otherwise.
Steven M LaValle