C-MAXPLAN: Contingent Planning in the MAXPLAN Framework
Stephen M. Majercik, Probabilistic Planning Representation · 1999
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 sat-isfiability problem in which a set of Boolean variables encodes the plan and a second set of Boolean vari-ables encodes the probabilistic outcome of the plan--the satisfiability problem is to find the setting of the plan variables that maximizes the probability of sat-isfaction with respect to the outcome variables. We describe two different encodings for contingent plans in this framework: the first one explicitly encodes con-tingent 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 compet-itive with state-of-the-art contingent planners on some problems.