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

EXERCISES 135

Turning back to motion planning algorithms for mobile robots, note that
nowhere until now have we talked about the effect of robot dynamics on motion
planning. This implicitly assumed, for example, that any sharp turn in the robot’s
path dictated by the planning algorithm was deemed feasible. For a robot with
flesh and reasonable mass and speed, this is of course not so. In the next chapter
we will turn to the connection between robot dynamics and motion planning.

3.11 EXERCISES

1. Recall that in the so-called out-position situations (Section 3.3.2) the algo-
rithm Bug2 has a very favorable performance: The robot is guaranteed to
have no cycles in the path (i.e., to never pass a path segment more than
once). On the other hand, the in-position situations can sometimes produce
long paths with local cycles. For a given scene, the in-position was defined
in Section 3.3.2 as a situation when either Start or Target points, or both,
lie inside the convex hull of obstacles that the line (Start, Target) intersects.
Note that the in-position situation is only a sufficient condition for trouble:
Simple examples can be designed where no cycles are produced in spite of
the in-position condition being satisfied.
Tryto come upwith a necessary and sufficient condition—call it GOOD-
CON—that would guarantee a no-cycle performance by Bug2 algorithm. Your
statement would say: “Algorithm Bug2 will produce no cycles in the path if
and only if condition GOODCON is satisfied.”

2. The following sensor-based motion planning algorithm, called AlgX (see the
procedure below), has been suggested for moving a mobile point automaton
(MA) in a planar environment with unknown arbitrarily shaped obstacles. MA
knows its own position and that of the target location T , and it has tactile
sensing; that is, it learns about an obstacle only when it touches it. AlgX makes
use of the straight lines that connect MA with point T and are tangential to
the obstacle(s) at the MA’s current position.
The questions being asked are:
• Does AlgX converge?
• If the answer is “yes,” estimate the performance of AlgX.
• If the answer is “no,” why not? Explain and give a counterexample. Using
the same idea of the tangential lines connecting MA and T , try to fix the
algorithm. Your procedure must operate with finite memory. Estimate its
performance.
• Develop a test for target reachability.
Just like the Bug1 and Bug2 algorithms, the AlgX procedure also uses the
notions of (a) hit points, H j ,and leave points, L j , on the obstacle boundaries
and (b) local directions. Given the start S and target T points, here are some
necessary details: