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

MOTION PLANNING WITH COMPLETE INFORMATION 51

category—human intuition is not a good advisor. If, while operating under some
reasonably sounding algorithm with unproven convergence, the robot fails to
find a path, the failure may simply mean that feasible paths do exist but the
algorithm has missed them. A guarantee of convergence then becomes a very
practical issue.

2.8 MOTION PLANNING WITH COMPLETE INFORMATION

In this type of motion planning, input information is processed before the actual
motion starts. This means that the input information must exist beforehand.
3
The model with complete information is formulated as follows. Given a solid
object (robot), or a combination of solid objects, in two- or three-dimensional
space, whose size, shape, and initial and target position and orientation are fully
described, and given a set of obstacles whose shapes, positions, and orientations
in space are likewise known, the task is to find a continuous path for the object
from the initial to the target position while avoiding collisions with obstacles
along the way. An important assumption used in the model is that the surfaces
of the moving object and the obstacles are algebraic or semialgebraic. This guar-
antees a final description of the input data. In some works a stricter requirement
of planar surfaces is imposed.
Because complete information about the problem is assumed, the whole oper-
ation of path planning is a one-time, off-line operation. The main difficulty is
not in proving existence of algorithms that would guarantee a solution (they
obviously exist), but in assessing the problem complexity and obtaining a com-
putationally efficient procedure. Reaching a solution means either finding a path
or concluding in finite time that no path exists. Since a solution is always feasible,
cases of arbitrary complexity can in principle be considered. Another apparent
advantage of dealing with complete information is that various optimization cri-
teria—finding the shortest path, or the minimum-time path, or the safest path,
and so on—can be introduced easily.
Historically, Piano Mover’s approach strategies were the first to come, starting
in late 1960s. Most of the people who formulated the problem of robot collision
avoidance were computer scientists. For them, collision avoidance was a purely
computational problem, and the question of handling input information boiled
down to a search in the database that contained that information. They often
perceived sensing, partial information, uncertainty, control, and all such issues
as small conceptual bumps that only interfered with the beautiful computational
problem in hand. By the late 1980s, the area became one of the richest and popular
areas in computational geometry. Hundreds of planning algorithms with complete
information have been published; the problem’s computational complexity has
been studied in depth, and ingenuous ways of dealing with it were reported [11].

3 A good survey of the work on provable algorithms for the Piano Mover’s problem can be found in
Ref. 11; specialized maze search algorithms are considered in Ref. 12.