MAXPLAN: A New Approach to Probabilistic Planning

Classical artificial intelligence planningtechniquescan operate in large domains but traditionally assume a deterministic universe. Operations research planning techniques can operate in probabilistic domains but breakwhenthedomains approach realistic sizes. MAXPLANis a newprobabilistic planning technique that aimsat combining thebestofthesetwo~rlds. MAXPLANconverts a planning instance intoan E-MAJSAT instance, andthendrawson techniques fromBoolean satisfiability anddynamic programming to solvethe E-MAJSA’r instance. E-MAJSAT is an NPPP-complete problem thatisessentially a probabilistic version of SAT. MAXPLAN performs as muchas an orderof magnitude better onsomestandard stochastic testproblemsthanBURIDAN--a state-of-the-art probabilistic planner--and scales better on onetestproblem than twoalgorithms basedon dynamic programming.

Authors

• Stephen M. Majercik
• Michael L. Littman

Keywords

No keywords are indexed for this paper.