Position Statement: Contingent Planning in Partially Observable Stochastic Domains via Stochastic Satisfiability

Contents

Our research has successfully extended the plann!ngas- 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. We have also shown that stochastic satisfiability can model compactly represented artificial intelligence planning domains, an insight that led to the development of ZANDE'I~, an implemented framework for contingent planning under uncertainty using stochastic satisfiability.