Page 194 - Sensing, Intelligence, Motion : How Robots and Humans Move in an Unstructured World

MINIMUM TIME STRATEGY 169

˙ η 2 0 η 0
η s =− +
4q max 2

˙ η 0 2
˙ η s = − η 0 q max
2q max
The number, time, and locations of switchings can be uniquely defined from the
initial and final conditions. It can be shown (see Appendix in Ref. 99) that for
4
˙
every position of the robot in the (ξ, η, ξ, ˙η) the control law obtained guaran-
tees time-optimal motion in both ξ and η directions, as long as the time interval
considered is sufficiently small. Substituting this control law in the equations of
motion (4.15) produces the canonical solution.
To summarize, the procedure for obtaining the first step of the canonical
solution is as follows:

1. Substitute the current position/velocity (ξ, η, ξ, ˙η) into the equations (4.16)
˙
and (4.17) and see if the starting point is above or below the switch curves.
2. Depending on the above/below information, take one of the four possible
bang-bang control pairs p, q from (4.18).
3. With this pair (p, q), find from (4.15) the position C i+1 and from (4.13)
the velocity V i+1 and angle θ i+1 at the end of the step. If this step to C i+1
crosses no obstacles and if there exists a stopping path in the direction
V i+1 , the step is accepted; otherwise, a near-canonical solution is sought
(Section 4.3.5).

Note that though the canonical solution defines a fairly complex multistep path
from C i to T i , only one—the very first—step of that path is calculated explicitly.
The switch curves (4.16) and (4.17), as well as the position and velocity equations
(4.15) and (4.13), are quite simple. The whole computation is therefore very fast.

4.3.5 Near-Canonical Solution
As discussed above, unless a step that is being considered for the next moment
guarantees a stopping path along its velocity vector, it will be rejected. This
step will be always the very first step of the canonical solution. If the stopping
path of the candidate step happens to cross an obstacle within the distance found
from (4.10), the controls are modified into a near-canonical solution that is both
-acceptable and reasonably close to the canonical solution. The near-canonical
solution is one of the nine possible combinations of the bang-bang control pairs
(k 1 · p max ,k 2 · q max ),where k 1 and k 2 are chosen from the set {−1, 0, 1} (see
Figure 4.10).
Since the canonical solution takes one of those nine control pairs, the near-
canonical solution is to be chosen from the remaining eight pairs. This set is
guaranteed to contain an -acceptable solution: Since the current position has
been chosen so as to guarantee a stopping path, this means that if everything