Thesis Proposal: Reasoning about when to plan and what to plan.

Richard Goodwin,

School of Computer Science, Carnegie Mellon University

Agents plan in order to improve their performance. However, planning takes time and consumes resources that may in fact degrade an agents performance. Ideally, an agent should only plan when the expected improvement outweighs the expected cost and no resources should be expended on making this decision. To do this, an agent would have to be omniscient. The problem of how to approximate this ideal, without consuming too many resources in the process, is the meta-level control problem for a resource bounded rational agent.

In this research, I propose to develop techniques for meta-level control that can be used to create resource bounded rational agents. The base level problem of creating and selecting a plan for the agent to execute will be modeled as a standard decision problem. The planning process that generates approximate solutions to the decision problem can be viewed as consisting of three anytime algorithms: plan generation, plan refinement, variable estimation. The meta-level controller is responsible for allocating computation to each of these algorithms and for focusing them on specific aspects of the problem. The meta-level controller will be provided with performance profiles for each algorithm and a representation of the agents utility function. An approximate sensitivity analysis will then used as the basis for implementing meta-level control. Information derived from the sensitivity analysis can be used to estimate the value of further plan generation and refinement and to identify which variable estimates need to be refined. A sensitivity analysis also identifies plans that are dominated or not potentially optimal. The meta-level controller can then exclude such plans from further consideration.

The objective of this research is to develop techniques for efficient and effective decision-theoretic meta-level planning control that can be applied to a wide variety of agents and tasks.