It is difficult to even define optimality for more general C-spaces. What does it mean to have a shortest path in or ? Consider the case of a planar, rigid robot that can translate and rotate. One path could minimize the amount of rotation whereas another tries to minimize the amount of translation. Without more information, there is no clear preference. Ulam's distance is one possibility, which is to minimize the distance traveled by fixed points [474]. In Chapter 13, differential models will be introduced, which lead to meaningful definitions of optimality. For example, the shortest paths for a slow-moving car are shown in Section 15.3; these require a precise specification of the constraints on the motion of the car (it is more costly to move a car sideways than forward).

This section formulates some optimal motion planning problems, to provide a smooth transition into the later concepts. Up until now, actions were used in Chapter 2 for discrete planning problems, but they were successfully avoided for basic motion planning by directly describing paths that map into . It will be convenient to use them once again. Recall that they were convenient for defining costs and optimal planning in Section 2.3.

To avoid for now the complications of differential equations, consider making an approximate model of motion planning in which every path must be composed of a sequence of shortest-path segments in . Most often these are line segments; however, for the case of , circular arcs obtained by spherical linear interpolation may be preferable. Consider extending Formulation 2.3 from Section 2.3.2 to the problem of motion planning.

Let the C-space be embedded in
(i.e.,
). An action will be defined shortly as an -dimensional
vector. Given a scaling constant and a configuration ,
an action produces a new configuration,
. This can be considered as a *configuration transition
equation*,
. The path segment represented by the
action is the shortest path (usually a line segment) between
and . Following Section 2.3, let
denote a *-step plan*, which is a sequence , ,
, of actions. Note that if and
are given, then a sequence of states, , , ,
, can be derived using . Initially,
, and
each following state is obtained by
. From this
a path,
, can be derived.

An approximate optimal planning problem is formalized as follows:

- The following components are defined the same as in Formulation 4.1: , , , , , , and . It is assumed that is an -dimensional manifold.
- For each
, a possibly infinite
*action space*, . Each is an -dimensional vector. - A positive constant
called the
*step size*. - A set of
*stages*, each denoted by , which begins at and continues indefinitely. Each stage is indicated by a subscript, to obtain and . - A
*configuration transition function*in which is computed by vector addition on . - Instead of a goal state, a goal region is defined.
- Let denote a real-valued cost functional, which is
applied to a -step plan, . This means that the sequence
of actions and the sequence
of configurations may appear in an expression of . Let .
The
*cost functional*is

The final term is outside of the sum and is defined as if and otherwise. As in Formulation 2.3, is not necessarily a constant. - Each contains the special
*termination action*, which behaves the same way as in Formulation 2.3. If is applied to at stage , then the action is repeatedly applied forever, the configuration remains in forever, and no more cost accumulates.

The task is to compute a sequence of actions that optimizes
(7.26). Formulation 7.4 can be used to define
a variety of optimal planning problems. The parameter can
be considered as the resolution of the approximation. In many
formulations it can be interpreted as a *time step*,
; however, note that no explicit time reference is necessary
because the problem only requires constructing a path through
.
As approaches zero, the formulation approaches an exact
optimal planning problem. To properly express the exact problem,
differential equations are needed. This is deferred until Part
IV.

(7.27) |

When used in the configuration transition equation, this set of actions produces ``up,'' ``down,'' ``left,'' and ``right'' motions and a ``terminate'' command. This produces a topological graph according to the 1-neighborhood model, (5.37), which was given in Section 5.4.2. The action set for this example and the following two examples are shown in Figure 7.41 for comparison. The cost term is defined to be for all and . If , then . Note that the set of configurations reachable by these actions lies on a grid, in which the spacing between -neighbors is . This corresponds to a convenient special case in which time discretization (implemented by ) leads to a regular space discretization. Consider Figure 7.40. It is impossible to take a shorter path along a diagonal because the actions do not allow it. Therefore, all monotonic paths along the grid produce the same costs.

Optimal paths can be obtained by simply applying the dynamic programming algorithms of Chapter 2. This example provides a nice unification of concepts from Section 2.2, which introduced grid search, and Section 5.4.2, which explained how to adapt search methods to motion planning. In the current setting, only algorithms that produce optimal solutions on the corresponding graph are acceptable.

This form of optimization might not seem relevant because it does not
represent the Euclidean shortest-path problem for
. The next
model adds more actions, and does correspond to an important class of
optimization problems in robotics.

One additional issue for this problem is the precision defined for the
goal. If the goal region is very small relative to , then
complicated paths may have to be selected to arrive precisely at the
goal.

Steven M LaValle 2012-04-20