Planning under Uncertainty via Stochastic Satisfiability

Contents

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).