C-MAXPLAN: Contingent Planning in the MAXPLAN Framework

Stephen M. Majercik 

Abstract: 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.