14.6.3.5 A bang-bang approach for time optimality

The dynamic programming approach is already very efficient because the search is confined to two dimensions. Nevertheless, trajectories that are time optimal can be computed even more efficiently if ${S}_{obs}$ has some special structure. The idea is to find an alternating sequence between two motion primitives: one of maximum acceleration and one of maximum deceleration. This kind of switching between extreme opposites is often called bang-bang control and arises often in the development of time-optimal control laws (look ahead to Example 15.4). The method explained here was introduced in [121,879]. One drawback of obtaining time-optimal trajectories is that they cannot be tracked (the fourth module from Section 14.6.1) if errors occur because the solutions travel on the boundary of the reachable set.

The approach was developed for robot arms, as considered in Example 14.7. Suppose that ${S}_{obs}$ is a single connected component that is bounded above by ${\dot s}_{max}$, and on the sides it is bounded by $s = 0$ and $s = 1$. It is assumed that ${S}$ arises only due to the vanishing of the interval of allowable values for ${\ddot s}$ (in this case, $U'(s,{\dot s})$ becomes empty). It is also assumed that the lower boundary of ${S}_{obs}$ can be expressed as a differentiable function $\phi : [0,1] \rightarrow {S}$, called the limit curve, which yields the maximum speed ${\dot s}= \phi(s)$ for every $s \in [0,1]$. The method is extended to handle multiple obstacles in [879], but this case is not considered here. Assume also that $d\tau_i/ds \not = 0$ for every $i$; the case of $d\tau_i/ds = 0$ can also be handled in the method [878].

Let $u'_{min}(s,{\dot s})$ and $u'_{max}(s,{\dot s})$ denote the smallest and largest possible accelerations, respectively, from $(s,{\dot s}) \in {S}$. If $(s,{\dot s}) \not \in {S}_{obs}$, then $u'_{min}(s,{\dot s}) < u'_{max}(s,{\dot s})$. At the limit curve, $u'_{min}(s,\phi(s)) = u'_{max}(s,\phi(s))$. Applying the only feasible action in this case generates a velocity that is tangent to the limit curve. This is called a tangent point, $(s_{tan},{\dot s}_{tan})$, to $\phi$. Inside of ${S}_{obs}$, no accelerations are possible.

Figure 14.28: The bang-bang approach finds a time-optimal, path-constrained trajectory with less searching than the dynamic programming approach.

Figure 14.29: An illustration of the bang-bang approach to computing a time-optimal trajectory. The solution trajectory is obtained by connecting the dots.

The bang-bang approach is described in Figure 14.28, and a graphical illustration appears in Figure 14.29. Assume that the initial and goal phases are $(0,0)$ and $(1,0)$, respectively. Step 1 essentially enlarges the goal by constructing a maximum-deceleration curve that terminates at $(1,0)$. A trajectory that contacts this curve can optimally reach $(1,0)$ by switching to maximum deceleration. Steps 3 and 4 construct a maximum-acceleration curve followed by a maximum-deceleration curve. The acceleration curve runs until it pierces the limit curve. This constraint violation must be avoided. Therefore, a deceleration must be determined that departs earlier from the acceleration curve and just barely misses entering the interior of ${S}_{obs}$. This curve must become tangent to the limit curve; therefore, a search is made along the limit curve for the next possible tangent point. From there, reverse-time integration is used in Step 4 to generate a deceleration curve that contacts the acceleration curve. A portion of the solution has now been obtained in which an acceleration is followed by a deceleration that arrives at a tangent point of $\phi$. It is possible that Step 4 is not reached because the curve that connects to the goal is contacted. Starting from the tangent point, Steps 3 and 4 are repeated until the goal curve is contacted.