2005 · 53 citations · 20 references
ComputingAutonomous SystemsDecision TheoryKnowledge RepresentationMarkov Decision ProcessesAction RepresentationConstraint SatisfactionCriterion ValidityPlan Consistency CheckingPruning
Optimal planners in the classical setting are built around two notions: branching and pruning. SAT-based planners for example branch by trying the values of a selected variable, and prune by propagating constraints and checking consistency. In the conformant setting, a similar branching scheme can be used if restricted to action variables, but the pruning scheme must be modified. Indeed, pruning branches that encode inconsistent partial plans is not sufficient since a partial plan may be consistent and complete (covering all the action variables) and still fail to be a conformant plan. This happens indeed when the plan does not conform to some possible initial state or transition. A remedy to this problem is to use a criterion stronger than consistency for pruning. This is actually what we do in this paper where the consistency-based
20
E. M. Clarke, Orna Grümberg, D. Long · 1996 · 6.9K citations
William A. Howard · Journal of Symbolic Logic · 1984 · 840 citations
2002 · 625 citations
Decomposable negation normal form
Adnan Darwiche · Journal of the ACM · 2001 · 333 citations