Contingent 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

Planning

We describe how to map the problem of contingent planning in a probabilistic propositional domain to two different probabilistic satisfiability problems. In the first approach, a set of Boolean variables encode the contingent plan and a second set the probabilistic outcome of the plan--the satisfiability problem is to find the setting of the plan variables that maximizes the probability of satisfaction with respect to the outcome variables. This is equivalent to the E-MAJSAT problem. A difficulty with this approach (C-MAXPLAN) is that the efficiency with which the resulting satisfiability problem is solved depends critically on the contingent-plan representation, for which there are many possible choices. A second approach is to intermingle plan variables and outcome variables in the formula so values for plan variables can be chosen conditionally based on observable values of outcome variables. This approach, while equivalent to a satisfiability problem called S-SAT from a higher complexity class, has the virtue of providing substantially more direct problem encodings. We report results using a preliminary implementation of the S-SAT approach (ZANDER), which is competitive with existing planners on a variety of problems.