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

MAXIMUM TURN STRATEGY 147

2. Using sensing data, define the farthest visible intermediate target T i on the
obstacle boundary and on a convergent path; make a step toward T i ; iterate
Step 2 until you detect the M-line; go to Step 1.
To this process we add a control procedure for handling dynamics. It is clear
already that from time to time dynamics will prevent the robot from carefully
following an obstacle boundary. For example, in Figure 4.1, while trying to pass
the obstacle from the left, under a VisBug procedure the robot would make a
sharp turn at point P . Such motion is not possible in a system with dynamics.
At times the current intermediate target T i may go out of the robot’s sight,
because of the robot inertia or because of occluding obstacles. In such cases the
robot will be designating temporary intermediate targets and use them until it
can spot the point T i again. The final algorithm will also include mechanisms for
checking the target reachability and for local path optimization.
Safety Considerations. Dynamics affects safety. Given the uncertainty beyond
the distance r v from the robot (or even closer to it in case of occluding obstacles),
a guaranteed stopping path is the only way to ensure collision-free motion. Unless
this last resort path is available, new obstacles may appear in the sensing range
at the next step, and collision may be imminent. A stopping path implies a
safe direction of motion and a safe velocity value. We choose the stopping path
as a straight-line segment along the step’s velocity vector. A candidate for the
next step is “approved” by the algorithm only if its execution would guarantee
a stopping path. In this sense our planning procedure is based on a one-step
analysis. 3
As one will see, the procedure for a detour around a suddenly appearing
obstacle operates in a similar fashion. We emphasize that the stopping path does
not mean stopping. While moving along, at every step the robot just makes sure
that if a stop is suddenly necessary, there is always a guarantee for it.
Allowing for a straight-line stopping path with the stop at the sensing range
boundary implies the following relationship between the velocity V,mass m,and
controls u = (p, q):

V ≤ 2pd (4.1)
where d is the distance from the current position C to the stop point. So, for
example, an increase in the radius of vision r v would allow the robot to raise
the maximum velocity, by the virtue of providing more information farther along
the path. Some control ramifications of this relationship will be analyzed in
Section 4.2.3.

Convergence. Because of the effect of dynamics, the convergence mechanism
borrowed from a kinematic algorithm—here VisBug—needs some modification.

3 A deeper multistep analysis can in principle produce locally shorter paths. It would not add to
safety, however, and is not likely to justify the steep rise in computational expenses.