Planning under Uncertainty via Stochastic Satisfiability

Stephen M. Majercik

Our research has successfully extended the planningas- satisfiability paradigm to support contingent planning under uncertainty (uncertain initial conditions, probabilistic effects of actions, uncertain state estimation). Stochastic satisfiability (SSAT), ty pe of Boolean satisfiability problem in which some of the variables have probabilities attached to them, forms the basis of this extension. We have developed an SSAT framework, explored the behavior of randomly generated SSAT problems, and developed algorithms for solving SSAT problems (Littman, Majercik, and Pitassi 2000). We have also shown that stochastic satisfiability can model compactly represented artificial intelligence planning domains, an insight that led to the development of ZANDER, an implemented framework for contingent planning under uncertainty using stochastic satisfiability (Majercik 2000).

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.