Efficient Meta-Level Control for Decision-Theoretic Planners

                            Richard Goodwin
                            rich@cs.cmu.edu
                       School of Computer Science
                       Carnegie Mellon University
                       http://www.cs.cmu.edu/~rich


Agents plan in order to improve their performance.  However, planning
takes time and consumes resources that may degrade performance.
Ideally, an agent should only plan when the expected improvement
outweighs the expected cost.  Resources, including computation, should
be allocated efficiently.  The problem of how to approximate this ideal
is the meta-level control problem.

In my thesis research, I address the meta-level control problem by
explicitly allocating computation to efficiently accomplish the task at
hand, accounting for the fact that planning delays execution.  I build
on the decision-theoretic planning approach that combines AI planning
techniques for efficiently creating plans with decision theory methods
for assessing plan quality.  The problem of allocating computation
amounts to choosing one of the available computations to do next.  I
develop an algorithm that answers this question optimally, given
complete information.  When complete information is too expensive to
compute, my sensitivity analysis techniques can be used to efficiently
approximate the optimal solution.  A decision to begin execution
involves a tradeoff between improving a plan with more computation and
delaying the start of execution.  Previous approaches to this problem
have focused on the the question of whether to plan or execute.  My work
extends these approaches to cover agents that can overlap planning and
execution.  By explicitly accounting for planning during execution,
overall performance improves.

The formal results from my thesis have been applied to a range of
domain-specific and domain-independent decision-theoretic planners.  I
developed a mobile robot route planner that efficiently routes the
Xavier robot around our building.  I have also applied the same results
to Haddawy's domain independent planner, DRIPS.  As a result, the
planner's performance has more than doubled when it is used to create
treatment policies for a domain taken from the medical literature.