MAXPLAN: a new approach to probabilistic planning

Abstract

Classical arti#cial intelligence planning techniques can operate in large domains but traditionally assume a deterministic universe. Operations research planning techniques can operate in probabilistic domains but break when the domains approach realistic sizes. maxplan is a new probabilistic planning technique that aims at combining the best of these twoworlds. maxplan converts a planning instance into an E-Majsat instance, and then draws on techniques from Boolean satis#ability and dynamic programming to solve the E-Majsat instance. E-Majsat is an NP PP -complete problem that is essentially a probabilistic version of Sat. 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 scales better on one test problem than two algorithms based on dynamic programming. INTRODUCTION Classical arti#cial intelligence planning techniques can operate in large domains but, t...