MAXPLAN: A New Approach to Probabilistic Planning

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.