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

MOTION PLANNING WITH INCOMPLETE INFORMATION 67

vehicle navigation. Although robot arm manipulators are very important for
theory and practice, little has been done for them until later, when the underlying
issues became clearer. An incomplete list of path planning heuristics includes
Refs. 28 and 47–52.
Not rarely, attempts for planning with incomplete information have their start-
ing point in the Piano Mover’s model and in planning with complete information.
For example, in heuristic algorithms considered in Refs. 47, 48 and 50, a piece
of the path is formed from the edges of a connectivity graph resulting from
modeling the robot’s surrounding area for which information is available at
the moment (for example, from the robot’s vision sensor). As the robot moves
to the next area, the process repeats. This means that little can be said about
the procedures’ chances for reaching the goal. Obstacles are usually approxi-
mated with polygons; the corresponding connectivity graph is formed by straight-
line segments that connect obstacle vertices, the robot starting point, and its
target point, with a constraint on nonintersection of graph edges with
obstacles.
In these works, path planning is limited to the robot’s immediate surround-
ings, the area for which sensing information on the scene is available from robot
sensors. Within this limited area, the problem is actually treated as one with com-
plete information. Sometimes the navigation problem is treated as a hierarchical
problem [48, 53], where the upper level is concerned with global navigation for
which the information is assumed available, while the lower level is doing local
navigation based on sensory feedback. A heuristic procedure for moving a robot
arm manipulator among unknown obstacles is described in Ref. 54.
Because the above heuristic algorithms have no theoretical assurance of con-
vergence, it is hard to judge how complete they are. Their explicit or implicit
reliance on the so-called common sense is founded on the assumption that humans
are good at orienting and navigation in space and at solving geometrical search
problems. This assumption is questionable, however, especially in the case of
arm manipulators. As we will see in Chapter 7, when lacking global input infor-
mation and directional clues, human operators are confused, lose their sense of
orientation, and exhibit inferior performance. Nevertheless, in relatively simple
scenes, such heuristic procedures have been shown to produce an acceptable
performance.
More recently, algorithms have been reported that do not have the above
limitations—they treat obstacles as they come, have a proof of convergence,
and so on—and are closer to the SIM model. All these works deal with motion
planning for mobile robots; the strategies they propose are in many ways close to
the algorithms studied further in Chapter 3. These works will be reviewed later,
in Section 3.8, once we are ready to discuss the underlying issues.
With time the SIM paradigm acquired popularity and found a way to applica-
tions. Algorithms with guaranteed convergence appeared, along with a plethora
of heuristic schemes. Since knowing the robot location is important for motion
planning, some approaches attempted to address robot localization and motion