MAXPLAN: A New Approach to Probabilistic Planning

Stephen M. Majercik and Michael L. Littman

Classical AI planning can handle large domains but typically assumes a
deterministic universe.  Planning as practiced in operations research
handles probabilistic domains but breaks when the domains approach
realistic sizes.  We present MAXPLAN, a new approach to planning under
uncertainty, which aims at combining the best of these two worlds.
MAXPLAN converts a planning problem into an EMAJSAT problem, an
NP^PP-complete problem that is essentially a probabilistic version of
SAT.  We draw on techniques from Boolean satisfiability and dynamic
programming to solve the resulting E-Majsat problem.  MAXPLAN performs
as much as an order of magnitude better on some standard stochastic
test problems than BURIDAN---a state-of-the-art probabilistic
planner---and two algorithms based on dynamic programming.