7.1.1 Problem Formulation

The formulation is designed to allow the tools and concepts learned so
far to be applied directly. Let
denote the *time
interval*, which may be *bounded* or *unbounded*. If is
bounded, then
, in which 0 is the *initial time*
and is the *final time*. If is unbounded, then
. An initial time other than 0 could alternatively be
defined without difficulty, but this will not be done here.

Let the state space be defined as
, in which
is the usual C-space of the robot, as defined in Chapter
4. A state is represented as , to
indicate the configuration and time components of the
state vector. The planning will occur directly in , and in many
ways it can be treated as any C-space seen to far, but there is one
critical difference: *Time marches forward*. Imagine a path that
travels through . If it first reaches a state , and then
later some state , some traveling backward through time is
required! There is no mathematical problem with allowing such time
travel, but it is not realistic for most applications. Therefore,
paths in are forced to follow a constraint that they must move
forward in time.

Now consider making the following time-varying versions of the items used in Formulation 4.1 for motion planning.

- A
*world*in which either or . This is the same as in Formulation 4.1. - A
*time interval*that is either*bounded*to yield for some*final time*, , or*unbounded*to yield . - A semi-algebraic, time-varying
*obstacle region*for every . It is assumed that the obstacle region is a finite collection of rigid bodies that undergoes continuous, time-dependent rigid-body transformations. - The
*robot*(or , , for a linkage) and*configuration space*definitions are the same as in Formulation 4.1. - The
*state space*is the Cartesian product and a state is denoted as to denote the configuration and time components. See Figure 7.1. The obstacle region, , in the state space is defined as

and . For a given , slices of and are obtained. These are denoted as and , respectively, in which (assuming is one body)(7.2)

and . - A state
is designated as the
*initial state*, with the constraint that for some . In other words, at the initial time the robot cannot be in collision. - A subset
is designated as the
*goal region*. A typical definition is to pick some and let , which means that the goal is*stationary*for all time. - A complete algorithm must compute a continuous, time-monotonic
*path*, , such that and , or correctly report that such a path does not exist. To be*time-monotonic*implies that for any such that , we have , in which and .

In the general formulation, there are no additional constraints on the
path, , which means that the robot motion model allows infinite
acceleration and unbounded speed. The robot velocity may change
instantaneously, but the path through must always be continuous.
These issues did not arise in Chapter 4 because there
was no need to mention time. Now it becomes necessary.^{7.1}

Steven M LaValle 2012-04-20