2:30 Friday Sep 12 1997, Wean 4601

	       Solving Propositional Decision Processes

		  Prof. Michael Littman, Duke Univ.

Classic algorithms for solving Markov decision processes (MDPs) and
partially observable Markov decision processes (POMDPs) are limited in
their ability to scale because they require a representation of world
states that is "flat"---every state is considered completely distinct
from every other state.  Many domains can be expressed more succinctly
using AI-like *propositional* representations in which a state is
represented by an assignment to a set of Boolean variables.  Solving
this type of propositional decision process can be quite challenging.
I will describe some recent complexity results concerning this problem
and argue that they suggest a promising direction for the creation of
new algorithms.  This new class of algorithms searches for small plans
using heuristic methods for a complexity class known as NP^PP.  With
luck, I'll also present some very preliminary results on one such
algorithm (joint work-in-progress with Steve Majercik at Duke).