Traditionally, AI planning systems have been strongly  related  to theorem provers. The task of the planner is to generate a series of operations (the plan) that will provably transform a given input state into a given goal state. Once uncertainty is introduced to the problem, however, this paradigm ceases to function well. This book introduces a different planning paradigm--dominance proving--as a method to mechanically produce admissible plans in an uncertain environment.

Dominance proving is conceptually simple. Instead of attempting to determine the quantitative value of a plan, as a simpler decision-theoretic approach might, the system compares plan classes against each other, establishing their relative values. A plan class that will provably produce higher utility than all plans in a second class dominates the second class. Therefore, the second class of plans need not be considered further. Plan classes will often be incomparable; this implies tradeoffs between them.

The book explains the theoretical basis for dominance proving, as well as giving an in-depth look at SUDO-Planner, an implemented dominance proving program. All of the data structures needed to implement SUDO-Planner are examined and analyzed in some detail.

Wellman’s “qualitative probabilistic networks” (QPNs), which graphically encode two types of constraints between variables, are fundamental. “Influences” describe the direction of the relationship between two variables; “synergies” encode the covariance of the influences of two variables on a third variable. Nodes are either event variables (those not under the control of the planner), actions, or the value node. QPNs are thus similar to influence diagrams and belief networks. QPNs are robust enough to allow inferences (graph reductions) and the chaining of such inferences. Wellman presents a rigorous definition of QPNs and proofs of the properties of the inferences allowable on them.

SUDO-Planner is a constraint posting planner. All plan classes are kept partially ordered by specificity in a graph. The course of execution is to generate increasingly detailed representations of the planning situation as QPNs, and reduce these to determine what effects the action variables have on the value node. These effects in turn translate directly into constraints on plans, which can then be included in the plan graph.

This book is an excellent addition to the planning literature, not only formalizing important ideas but also clarifying them with copious examples drawn from SUDO-Planner. It should be useful to anyone interested in planning or  uncertainty.