C-MAXPLAN: Contingent Planning in the MAXPLAN Framework

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Volume

Search Techniques for Problem Solving Under Uncertainty and Incomplete Information

Contents

C-MAXPLAN extends MAXPLAN to include contingent planning in probabilistic propositional domains. Like MAXPLAN, C-MAXPLAN converts the planning problem into an E-MAJSAT instance, a type of probabilistic satisfiability problem in which a set of Boolean variables encodes the plan and a second set of Boolean variables encodes 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. We describe two different encodings for contingent plans in this framework: the first one explicitly encodes contingent actions and is similar to the approach taken by C-BURIDAN; the second encodes a policy rather than a plan. Although the efficiency with which the resulting satisfiability problem is solved depends critically on the contingent-plan representation, C-MAXPLAN is competitive with state-of-the-art contingent planners on some problems.