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 = [0,\infty)$.
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

   $${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)

   $${\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) = \tau(s_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