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

54 A QUICK SKETCH OF MAJOR ISSUES IN ROBOTICS

A B C

Figure 2.17 Which of the three obstacles, A, B, or C, would be easier to pass around?

of approximation can cause a dramatic change in the number and positions of
nodes of the approximated surfaces and eventually in the generated paths.
Measuring the computational burden in terms of complexity of the connec-
tivity graph may create peculiar situations where the derived computational
complexity of a given task contradicts our intuitive notion of problem com-
plexity. Consider, for example, a circular obstacle A in Figure 2.17. Assume that
the motion planning algorithm that we plan to use requires polygonal obstacles.
Then, obstacle A is first approximated—say, by one of the polygons B or C in
Figure 2.17.
Now, according to Piano Mover’s algorithms, planning a path around obstacle
C is computationally more difficult than planning a path around the obstacle B,
because of the greater number of nodes in C. Moreover, in the limit, increas-
ing the accuracy of polygon approximation takes the computational burden to
infinity. But, from the human and from the robotics control viewpoints, walk-
ing around the circle A is actually easier than walking around obstacles B or
C, because the latter require special decisions at the corners of the obstacle.
Also, from the dynamics standpoint, there is an undesirable sharp change in
the velocity vector at the corners of obstacles B and C. One can, of course,
solve this specific example by including circular objects in the list of those
allowed by the algorithm, but this will only shift this discussion to some other
shapes.
For more detail on the Piano Mover’s model, the reader is referred to the liter-
ature. The model’s computational complexity for cases of rigid or hinged bodies
has been studied extensively. The problem was shown to be computationally
prohibitive [15–17]. A 2D case has been studied in Refs. 18–20. Cases where
objects to be moved are polygons (polyhedra) or discs (spheres) moving amidst
polygonal (polyhedral) obstacles are considered in [15, 18, 19, 21–23]. The first
attempt to study the case of moving an object with a number of free-hinged
links was initiated in 1968 by Pieper [24], in the context of motion planning for
robot arm manipulators. Exact algorithms for this problem have been described
[15, 16, 20], as have various heuristics (e.g., see Refs. 25 and 26).
The computational complexity of the problem was first reported by Reif [15],
who showed that the general Piano Mover’s problem is PSPACE-hard. He also