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