Stephen M. Majercik and Michael L. Littman
Classical artificial 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 two worlds. MAXPLAN converts a planning instance into an E-MAJSAT instance, and then draws on techniques from Boolean satisfiability 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.