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

142 ACCOUNTING FOR BODY DYNAMICS: THE JOGGER’S PROBLEM

By the way, which optimization criterion is to be used? We will consider two
criteria. The salient feature of one criterion is that, while maintaining the maximum
velocity allowed by its dynamics, the robot will attempt to maximize its instanta-
neous turning angle toward the required direction of motion. This will allow it to
finish every turning maneuver in minimum time. In a path with many turns, this
should save a good deal of time. In the second strategy (which also assumes the
maximum velocity compatible with collision avoidance), the robot will attempt
a time-optimal arrival at its (constantly shifting) intermediate target. Intermediate
targets will typically be on the boundary of the robot’s field of vision.
Similar to the model used in Chapter 3, our mobile robot operates in two-
dimensional physical space filled with a locally finite number of unknown sta-
tionary obstacles of arbitrary shapes. Planning is done in small steps (say, 30
or 50 times per second, which is typical for real-world robotics), resulting in
continuous motion. The robot is equipped with sensors, such as vision or range
finders, which allow it to detect and measure distances to surrounding objects
within its sensing range. Robot vision works within some limited or unlimited
radius of vision, which allows some steps look-ahead (say, 20 or 30 or more).
Unless obstacles occlude one another, the robot will see them and use this infor-
mation to plan appropriate actions. Occlusions effectively limit a robot’s input
information and call for more careful planning.
Control of body dynamics fits very well into the feedback nature of the SIM
(Sensing–Intelligence–Motion) paradigm. To be sure, such control can in princi-
ple be incorporated in the Piano Mover’s paradigm as well. One way to do this is,
for example, to divide the motion planning process into two stages: First, a path
is produced that satisfies the geometric constraints, and then this path is modified
to fit the dynamic constraints [79], possibly in a time-optimal fashion [80–82].
Among the first attempts to explicitly incorporate body dynamics into robot
motion planning were those by O’Dunlaing [83] for the one-dimensional case
and by Canny et al. [84] in their kinodynamic planning approach for the two-
dimensional case. In the latter work the proposed algorithm was shown to run in
exponential time and to require space that is polynomial in the input. While the
approach operates in the context of the Piano Mover’s paradigm, it is somewhat
akin to the approach considered in this chapter, in that the control strategy adheres
to the L ∞ -norm; that is, the velocity and acceleration components are assumed
bounded with respect to a fixed (absolute) reference system. This allows one to
decouple the equations of robot motion and treat the two-dimensional problem
as two one-dimensional problems. 1

1 Though comparisons between algorithms belonging to the two paradigms are difficult, one com-
parison seems to apply here. Using the L ∞ -norm will result, both in Ref. 84 and in the strategy
described here, in a less efficient use of control resources and a “less optimal” time of path execu-
tion. Since planning with complete information is a one-time computation, this loss in efficiency is
likely to be significant, due to a large deviation over the whole path of the robot’s moving reference
system from the absolute (world) system. In contrast, in the sensor-based approaches the decoupling
of controls occurs again and again, at every step of the motion: The reference system is fixed only
for the duration of one step, and so the resulting loss in efficiency should be less.