Exploiting Structure in Solving Planning Problems
or
Coping with the Blooming and Buzzing World that Surrounds Us

Tom Dean
Computer Sciences Department
Brown University

Abstract

In describing the world for planning purposes, the relevant features often multiply, seeming to indicate the need for complicated descriptions of the underlying dynamics. For many decision problems, however, we can structure our knowledge so as to realize compact, factored representations of the dynamics [McCarthy and Hayes, 1969] that take advantage of independence relationships involving the problem features. Factored representations have long been a mainstay of AI approaches to planning [Fikes and Nilsson, 1971]. Unfortunately, the existence of a compact representation does not imply a simple decision problem. In the first part of this talk, we consider methods based on model reduction and related to the work of Hartmanis and Stearns [1966] that attempt to simplify decision making by exploiting structure implicit in factored representations.

If factored representations constitute the beans and chili peppers of AI planning, then what's the big burrito, the whole enchilada, and do you really need beans to put together a satisfying meal? In many planning and control problems, accurate models are hard to come by. It may not be necessary to construct a factored representation enroute to a satisfactory solution to a planning problem. In the second part of the talk, we re-examine our motives for studying planning and propose an alternative perspective that combines traditional planning with learning. The result is an AI version of adaptive control with an emphasis on factored representations and a distinctly Bayesian flavor.


Eyal Amir
Last modified: Tue Apr 28 00:40:20 PDT 1998