Planning under Uncertainty via Stochastic Satisfiability

Proceedings of the AAAI Conference on Artificial Intelligence, 16

Volume

Proceedings of the AAAI Conference on Artificial Intelligence, 16

1999 SIGART/AAAI Doctoral Consortium

A probabilistic propositional planning problem can be solved by converting it to a stochastic satisfiability problem and solving that problem instead. I have developed three planners that use this approach: maxplan , c-maxplan , and zander . maxplan , which assumes complete unobservability, converts a dynamic belief network representation of the planning problem to an instance of a stochastic satisfiability problem called E-Majsat . maxplan then solves that problem using a modified version of the Davis-Putnam-Logemann-Loveland (DPLL) procedure for determining satisfiability along with time-ordered splitting and memoization.