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

MOTION PLANNING WITH INCOMPLETE INFORMATION 55

sketched a possible solution for moving a solid object in polynomial time, by
direct computation of the “forbidden” volumes in spaces of higher dimensions. 4
Reif also demonstrated that even the preliminary operation of approximating the
robot workspace with a specified accuracy carries a high computational cost.
Schwartz and Sharir [18] presented a polynomial-time algorithm for a 2D Piano
Mover’s problem with convex polygonal obstacles. It has been shown in a number
of works (e.g., Lozano-Perez and Wesley [27]) that the process of moving in the
task’s configuration space carries additional computational costs. In general, even
if the original obstacles are polyhedral, obstacles in the configuration space have
nonplanar walls. In order to keep the problem manageable, various constraints
are typically imposed.
Moravec [28] considered a path planning algorithm for a mobile robot moving
in two dimensions, with the robot presented as a circle. In his treatment of a 2D
path planning problem with a convex polygonal robot and convex polygonal
obstacles, Brooks and Binford [29, 30] used a generalized cylinder presentation
to reduce the planning problem to a graph search. A generalized cylinder is
formed by a volume swept by a cross section (in general, of varying shape and
size) moving along the cylinder axis, which in turn can be some spine curve.
The version of the Piano Movers problem where the robot can consist of a
number of free-hinged links is more difficult. On the heuristic level this ver-
sion was started by Pieper [24] and further investigated by Paul [31]. Both were
attracted to the problem’s obvious relation to control of robot arms with multiple
degrees of freedom. Later, new approaches for this version have been considered
in Refs. 16 and 20. The most general (although very expensive computationally)
algorithm for moving a free-hinged body was given by Schwartz and Sharir [16].
The technique is based on the general method of cell decomposition; the robot
and obstacles are assumed to be limited by algebraic surfaces. A more economi-
cal (but still prohibitive for many practical tasks) algorithm for the general case
was reported by Canny [32]. A variety of special cases shown to lead to simpler
algorithms were described by Hopcroft et al. [20].

2.9 MOTION PLANNING WITH INCOMPLETE INFORMATION

By the mid-1980s it became clear that the inherent uncertainty of a realistic robot
environment and the subsequent need for real-time sensing called for a paradigm
of motion planning that would fundamentally differ from the Piano Mover’s
paradigm. It was further realized that uncertainty and sensing were not some small
irritating “engineering details” but major factors in the theoretical foundation of
motion planning algorithms. As it turned out, uncertainty and sensing became
the very center around which the new paradigm would be built. The result was
the theory and practice of robot motion planning with incomplete information,or
the SIM (Sensing–Intelligence–Motion) paradigm.

4 Higher dimensions d appear when one takes into account the moving rigid object’s orientation
along its way; d = 3 for the 2D case, and d = 6 for the 3D case.