7.1.1 Problem Formulation

The formulation is designed to allow the tools and concepts learned so far to be applied directly. Let $ T \subset {\mathbb{R}}$ denote the time interval, which may be bounded or unbounded. If $ T$ is bounded, then $ T = [0,t_f]$, in which 0 is the initial time and $ t_f$ is the final time. If $ T$ is unbounded, then $ T =
[0,\infty)$. An initial time other than 0 could alternatively be defined without difficulty, but this will not be done here.

Let the state space $ X$ be defined as $ X = {\cal C}\times T$, in which $ {\cal C}$ is the usual C-space of the robot, as defined in Chapter 4. A state $ x$ is represented as $ x = (q,t)$, to indicate the configuration $ q$ and time $ t$ components of the state vector. The planning will occur directly in $ X$, 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 $ X$. If it first reaches a state $ (q_1,5)$, and then later some state $ (q_2,3)$, 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 $ X$ 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.

Formulation 7..1 (The Time-Varying Motion Planning Problem)  
  1. A world $ {\cal W}$ in which either $ {\cal W}= {\mathbb{R}}^2$ or $ {\cal W}= {\mathbb{R}}^3$. This is the same as in Formulation 4.1.
  2. A time interval $ T \subset {\mathbb{R}}$ that is either bounded to yield $ T = [0,t_f]$ for some final time, $ t_f > 0$, or unbounded to yield $ T =
  3. A semi-algebraic, time-varying obstacle region $ {\cal O}(t)
\subset {\cal W}$ for every $ t \in T$. It is assumed that the obstacle region is a finite collection of rigid bodies that undergoes continuous, time-dependent rigid-body transformations.
  4. The robot $ {\cal A}$ (or $ {\cal A}_1$, $ \ldots $, $ {\cal A}_m$ for a linkage) and configuration space $ {\cal C}$ definitions are the same as in Formulation 4.1.
  5. The state space $ X$ is the Cartesian product $ X = {\cal C}\times T$ and a state $ x \in X$ is denoted as $ x = (q,t)$ to denote the configuration $ q$ and time $ t$ components. See Figure 7.1. The obstacle region, $ {X_{obs}}$, in the state space is defined as

    $\displaystyle {X_{obs}}= \{ (q,t) \in X \;\vert\; {\cal A}(q) \cap {\cal O}(t) \not = \emptyset \} ,$ (7.1)

    and $ {X_{free}}= X \setminus {X_{obs}}$. For a given $ t \in T$, slices of $ {X_{obs}}$ and $ {X_{free}}$ are obtained. These are denoted as $ {\cal C}_{obs}(t)$ and $ {\cal C}_{free}(t)$, respectively, in which (assuming $ {\cal A}$ is one body)

    $\displaystyle {\cal C}_{obs}(t) = \{ q \in {\cal C}\;\vert\; {\cal A}(q) \cap {\cal O}(t) \not = \emptyset \}$ (7.2)

    and $ {\cal C}_{free}= {\cal C}\setminus {\cal C}_{obs}$.

  6. A state $ {x_{I}}\in {X_{free}}$ is designated as the initial state, with the constraint that $ {x_{I}}= ({q_{I}},0)$ for some $ {q_{I}}\in {\cal C}_{free}(0)$. In other words, at the initial time the robot cannot be in collision.
  7. A subset $ {X_{G}}\subset {X_{free}}$ is designated as the goal region. A typical definition is to pick some $ {q_{G}}\in {\cal C}$ and let $ {X_{G}}= \{ ({q_{G}},t) \in {X_{free}}\;\vert\; t \in T \}$, which means that the goal is stationary for all time.
  8. A complete algorithm must compute a continuous, time-monotonic path, $ \tau[0,1] \rightarrow {X_{free}}$, such that $ \tau(0) =
{x_{I}}$ and $ \tau(1) \in {X_{G}}$, or correctly report that such a path does not exist. To be time-monotonic implies that for any $ s_1,s_2 \in [0,1]$ such that $ s_1 < s_2$, we have $ t_1 < t_2$, in which $ (q_1,t_1) = \tau(s_1)$ and $ (q_2,t_2) =

Figure 7.1: A time-varying example with piecewise-linear obstacle motion.

Example 7..1 (Piecewise-Linear Obstacle Motion)   Figure 7.1 shows an example of a convex, polygonal robot $ {\cal A}$ that translates in $ {\cal W}= {\mathbb{R}}^2$. There is a single, convex, polygonal obstacle $ {\cal O}$. The two of these together yield a convex, polygonal C-space obstacle, $ {\cal C}_{obs}(t)$, which is shown for times $ t_1$, $ t_2$, and $ t_3$. The obstacle moves with a piecewise-linear motion model, which means that transformations applied to $ {\cal O}$ are a piecewise-linear function of time. For example, let $ (x,y)$ be a fixed point on the obstacle. To be a linear motion model, this point must transform as $ (x+c_1
t,y+c_2 t)$ for some constants $ c_1,c_2 \in {\mathbb{R}}$. To be piecewise-linear, it may change to a different linear motion at a finite number of critical times. Between these critical times, the motion must remain linear. There are two critical times in the example. If $ {\cal C}_{obs}(t)$ is polygonal, and a piecewise-linear motion model is used, then $ {X_{obs}}$ is polyhedral, as depicted in Figure 7.1. A stationary goal is also shown, which appears as a line that is parallel to the $ T$-axis. $ \blacksquare$

In the general formulation, there are no additional constraints on the path, $ \tau$, which means that the robot motion model allows infinite acceleration and unbounded speed. The robot velocity may change instantaneously, but the path through $ {\cal C}$ 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