Planning and replanning with truth maintenance
Jr. Charles Joseph Petrie · 1992
Classical AI planning, in the form of nonlinear hierarchical planning, provides a useful method of search reduction for specialized problems. However, the method is too narrow for solving a large class of practical planning problems, primarily because of the lack of general constraint satisfaction. Classical constraint satisfaction formalisms lack search by reduction. We provide a theory of Constrained Decision Problems (CDPs) for which neither classical AI planning nor constraint satisfaction formalisms are adequate. CDPs are characterized by multiple objectives, general constraints, succinct representation by decomposable goals, and replanning: the ability to react precisely to changed conditions. A model of CDP solving is presented that provides a general approach to heuristic-guided search reduction, backtracking, and replanning lacking in the classical techniques. A computational architecture that implements the model is also described. The architecture uses the standard techniques of backward rule chaining and truth maintenance, but also provides a novel use of truth maintenance that overcomes several outstanding technical problems.