Bounded speed

There has been no consideration so far of the speed at which the robot must move to avoid obstacles. It is obviously impractical in many applications if the solution requires the robot to move arbitrarily fast. One step toward making a realistic model is to enforce a bound on the speed of the robot. (More steps towards realism are taken in Chapter 13.) For simplicity, suppose ${\cal C}= {\mathbb{R}}^2$, which corresponds to a translating rigid robot, ${\cal A}$, that moves in ${\cal W}= {\mathbb{R}}^2$. A configuration, $q \in {\cal C}$, is represented as $q = (y,z)$ (since $x$ already refers to the whole state vector). The robot velocity is expressed as $v = ({\dot y},{\dot z}) \in {\mathbb{R}}^2$, in which ${\dot y}= dy/dt$ and ${\dot z}= dz/dt$. The robot speed is $\Vert v\Vert = \sqrt{{\dot y}^2 + {\dot z}^2}$. A speed bound, $b$, is a positive constant, $b \in (0,\infty)$, for which $\Vert v\Vert \leq b$.

In terms of Figure 7.1, this means that the slope of a solution path $\tau$ is bounded. Suppose that the domain of $\tau$ is $T = [0,t_f]$ instead of $[0,1]$. This yields $\tau : T \rightarrow X$ and $\tau(t) = (y,z,t)$. Using this representation, $d\tau_1/dt = {\dot y}$ and $d\tau_2/dt = {\dot z}$, in which $\tau_i$ denotes the $i$th component of $\tau$ (because it is a vector-valued function). Thus, it can seen that $b$ constrains the slope of $\tau(t)$ in $X$. To visualize this, imagine that only motion in the $y$ direction occurs, and suppose $b = 1$. If $\tau$ holds the robot fixed, then the speed is zero, which satisfies any bound. If the robot moves at speed $1$, then $d\tau_1/dt = 1$ and $d\tau_2/dt = 0$, which satisfies the speed bound. In Figure 7.1 this generates a path that has slope $1$ in the $yt$ plane and is horizontal in the $zt$ plane. If $d\tau_1/dt = d\tau_2/dt = 1$, then the bound is exceeded because the speed is $\sqrt 2$. In general, the velocity vector at any state $(y,z,t)$ points into a cone that starts at $(y,z)$ and is aligned in the positive $t$ direction; this is depicted in Figure 7.3. At time $t+\Delta t$, the state must stay within the cone, which means that

$$\big( y(t+\Delta t) - y(t) \big)^2 + \big( z(t+\Delta t) - z(t) \big)^2 \leq b^2 (\Delta t)^2 .$$ (7.4)

Figure 7.3: A projection of the cone constraint for the bounded-speed problem.

This constraint makes it considerably more difficult to adapt the algorithms of Chapters 5 and 6. Even for piecewise-linear motions of the obstacles, the problem has been established to be PSPACE-hard [818,819,928]. A complete algorithm is presented in [819] that is similar to the shortest-path roadmap algorithm of Section 6.2.4. The sampling-based roadmap of Section 5.6 is perhaps one of the easiest of the sampling-based algorithms to adapt for this problem. The neighbors of point $q$, which are determined for attempted connections, must lie within the cone that represents the speed bound. If this constraint is enforced, a resolution complete or probabilistically complete planning algorithm results.