Next: 12.1 General Methods Up: III. Decision-Theoretic Planning Previous: Exercises
The main purpose of Chapter 11 was to introduce information space (I-space) concepts and to provide illustrative examples that aid in understanding. This chapter addresses planning under sensing uncertainty, which amounts to planning in an I-space. Section 12.1 covers general-purpose algorithms, for which it will quickly be discovered that only problems with very few states can be solved because of the explosive growth of the I-space. In Chapter 6, it was seen that general-purpose motion planning algorithms apply only to simple problems. Ways to avoid this were either to develop sampling-based techniques or to focus on a narrower class of problems. It is intriguing to apply sampling-based planning ideas to I-spaces, but as of yet this idea remains largely unexplored. Therefore, the majority of this chapter focuses on planning algorithms designed for narrower classes of problems. In each case, interesting algorithms have been developed that can solve problems that are much more complicated than what could be solved by the general-purpose algorithms. This is because they exploit some structure that is specific to the problem.
An important philosophy when dealing with an I-space is to develop an
I-map that reduces its size and complexity as much as possible by
obtaining a simpler derived I-space. Following this, it may be
possible to design a special-purpose algorithm that efficiently solves
the new problem by relying on the fact that the I-space does have the
full generality. This idea will appear repeatedly throughout the
chapter. The most common derived I-space is
from Section
11.2.2;
, from Section 11.2.3, will also
arise.
After Section 12.1, the problems considered in the remainder of the chapter are inspired mainly by robotics applications. Section 12.2 addresses the localization problem, which means that a robot must use sensing information to determine its location. This is essentially a matter of maintaining derived I-states and computing plans that lead to the desired derived I-space. Section 12.3 generalizes localization to problems in which the robot does not even know its environment. In this case, the state space and I-space take into account both the possible environments in which the robot might be and the possible locations of the robot within each environment. This section is fundamental to robotics because it is costly and difficult to build precise maps of a robot's environment. By careful consideration of the I-space, a complete representation may be safely avoided in many applications.
Section 12.4 covers a kind of pursuit-evasion game that can be
considered as a formal version of the children's game of ``hide and
seek.'' The pursuer carries a lantern and must illuminate an
unpredictable evader that moves with unbounded speed. The
nondeterministic I-states for this problem characterize the set of
possible evader locations. The problem is solved by performing a cell
decomposition of
to obtain a finite, graph-search problem.
The method is based on finding critical curves in the I-space, much
like the critical-curve method in Section 6.3.4 for moving
a line-segment robot.
Section 12.5 concludes the chapter with manipulation planning under imperfect state information. This differs from the manipulation planning considered in Section 7.3.2 because it was assumed there that the state is always known. Section 12.5.1 presents the preimage planning framework, which was introduced two decades ago to address manipulation planning problems that have bounded uncertainty models for the state transitions and the sensors. Many important I-space ideas and complexity results were obtained from this framework and the body of literature on which it was based; therefore, it will be covered here. Section 12.5.2 addresses problems in which the robots have very limited sensing information and rely on the information gained from the physical interaction of objects. In some cases, these methods surprisingly do not even require sensing.
)