Page 388 - Introduction to AI Robotics

371
10.7 Summary
and memory limitations, such as a planetary rover. Second, continuous re-
planning is highly dependent on the sensing quality. If the robot senses an
unmodeled obstacle at time T1, it computes a new path and makes a large
course correction. If it no longer senses that obstacle at time T2 because the
first reading was a phantom from sensor noise, it will recompute another
large course correction. The result can be a robot which has a very jerky
motion and actually takes longer to reach the goal.
In the cases of path planning with embedded processors and noisy sensors,
EVENT-DRIVEN it would be desirable to have some sort of event-driven scheme, where an
REPLANNING event noticeable by the reactive system would trigger replanning. Trulla uses
the dot-product of the intended path vector and the actual path vector. When
the actual path deviates by 90 or more, the dot product of the path vector
and the actual vector the robot is following becomes 0 or negative. Therefore
the dot product acts as an affordance for triggering replanning: the robot
doesn’t have to know why it is drifting off-course, only that it has drifted
noticeably off-course.
This is very good for situations that would interfere with making progress
on the originally computed path, in effect, situations where the real world
is less amenable to reaching the intended goal. But it doesn’t handle the
situation where the real world is actually friendlier. In Fig. 10.14, an obstacle
thought to be there really isn’t. The robot could achieve a significant savings
in navigation by opportunistically going through the gap.
Such opportunism requires the robot to notice that the world is really
more favorable than originally modeled. A continuous replanner such as D*
has a distinct advantage, since it will automatically notice the change in the
world and respond appropriately, whereas Trulla will not notice the favor-
able change because it won’t lead to a path deviation. It is an open research
question whether there are affordances for noticing favorable changes in the
world that allow the robot to opportunistically optimize it path.

10.7 Summary

Metric path planning converts the world space to a configuration space, or
Cspace, representation that facilitates path planning. Cspace representations
such as generalized Voronoi diagrams exploit interesting geometric prop-
erties of the environment. These representations can then be converted to
graphs, suitable for an A* search. Since Voronoi diagrams tend to produce
sparser graphs, they work particularly well with A*. Regular grids work