5.1.2 Important Metric Spaces for Motion Planning
This section presents some metric spaces that arise frequently in
motion planning.
Example 5..1 (
Metric Using Complex Numbers)
If
is represented by unit complex numbers, recall that the
C-space is the subset of
given by
. Any
metric from
may be applied. Using
the Euclidean metric,
|
(5.6) |
for any pair of points
and
.
Example 5..2 (
Metric by Comparing Angles)
You might have noticed that the previous metric for
does not
give the distance traveling along the circle. It instead takes a
shortcut by computing the length of the line segment in
that
connects the two points. This distortion may be undesirable. An
alternative metric is obtained by directly comparing angles,
and
. However, in this case special care has to
be given to the identification, because there are two ways to reach
from
by traveling along the circle. This causes
a
to appear in the metric definition:
|
(5.7) |
for which
. This may
alternatively be expressed using the complex number representation
as an angle between two vectors:
|
(5.8) |
for two points
and
.
Example 5..3 (An
Metric)
Again by using the subspace principle, a metric can easily be obtained
for
. Using the complex number representation of
, each
element of
is a point
. The
Euclidean metric, or any other
metric on
, can be
immediately applied to obtain a metric.
Example 5..4 (
Metrics Using Quaternions)
As usual, the situation becomes more complicated for
. The
unit quaternions form a subset
of
. Therefore, any
metric may be used to define a metric on
, but this will not
be a metric for
because antipodal points need to be
identified. Let
represent two unit quaternions
(which are being interpreted here as elements of
by ignoring
the quaternion algebra). Taking the identifications into account, the
metric is
|
(5.9) |
in which the two arguments of the
correspond to the distances
from
to
and
, respectively. The
appears
because
was negated to yield its antipodal point,
.
As in the case of , the metric in (5.9)
may seem distorted because it measures the length of line segments
that cut through the interior of
, as opposed to traveling along
the surface. This problem can be fixed to give a very natural metric
for , which is based on spherical linear interpolation.
This takes the line segment that connects the points and pushes it
outward onto
. It is easier to visualize this by dropping a
dimension. Imagine computing the distance between two points on
. If these points lie on the equator, then spherical linear
interpolation yields a distance proportional to that obtained by
traveling along the equator, as opposed to cutting through the
interior of
(for points not on the equator, use the great
circle through the points).
It turns out that this metric can easily be defined in terms of the
inner product between the two quaternions. Recall that for unit
vectors and in
,
, in
which is the angle between the vectors. This angle is
precisely what is needed to give the proper distance along
.
The resulting metric is a surprisingly simple extension of
(5.8). The distance along
between two
quaternions is
|
(5.10) |
in which each
. Taking identification into
account yields the metric
|
(5.11) |
Example 5..5 (Another
Metric)
For many C-spaces, the problem of relating different kinds of
quantities arises. For example, any metric defined on
must
compare both distance in the plane and an angular quantity. For
example, even if
, the range for
is
using radians but
using degrees. If the same constant
is used in either case, two very different metrics are obtained.
The units applied to
and
are completely
incompatible.
Example 5..6 (Robot Displacement Metric)
Sometimes this incompatibility problem can be fixed by considering the
robot displacement. For any two configurations
, a
robot displacement metric can be defined as
|
(5.12) |
in which
is the position of the point
in the world when
the robot
is at configuration
. Intuitively, the robot
displacement metric yields the maximum amount in
that any part of
the robot is displaced when moving from configuration
to
.
The difficulty and efficiency with which this metric can be computed
depend strongly on the particular robot geometric model and
kinematics. For a convex polyhedral robot that can translate and
rotate, it is sufficient to check only vertices. The metric may
appear to be ideal, but efficient algorithms are not known for most
situations.
Example 5..7 (
Metrics)
Next consider making a metric over a torus
. The Cartesian
product rules such as (
5.4) and
(
5.5) can be extended over every copy of
(one for each parameter
). This leads to
arbitrary
coefficients
,
,
,
. Robot displacement could
be used to determine the coefficients. For example, if the robot is a
chain of links, it might make sense to weight changes in the first
link more heavily because the entire chain moves in this case. When
the last parameter is changed, only the last link moves; in this case,
it might make sense to give it less weight.
Example 5..8 (
Metrics)
Metrics for
can be formed by applying the Cartesian product
rules to a metric for
and a metric for
, such as that
given in (
5.11). Again, this unfortunately leaves
coefficients to be specified. These issues will arise again in Section
5.3.4, where more details appear on robot
displacement.
Subsections
Steven M LaValle
2020-08-14