The Composite Decision Process: A Unifying Formulation for Heuristic Search, Dynamic Programming and Branch & Bound Procedures

Vipin Kumar, Laveen N. KanalAAAI 1983

Introduction

In the early 1980s, the fields of Artificial Intelligence (AI) and Operations Research (OR) were often viewed as distinct domains with overlapping but separate methodologies. A central point of contention was the relationship between various search and optimization algorithms. Researchers debated whether AI's heuristic search methods, such as $A^*$, were fundamentally different from OR's Dynamic Programming (DP) or Branch & Bound (B&B) techniques. In their seminal 1983 paper, Kumar and Kanal addressed this lack of a common mathematical language by introducing the Composite Decision Process (CDP), a "Grand Unified Theory" that bridges these disciplines.

The CDP Framework: Search as Parsing

The core innovation of the CDP is the representation of the solution space as a context-free grammar. In this framework, any potential solution—whether it be a path through a graph, a strategy in a game, or a schedule in a supply chain—is viewed as a parse tree generated by the grammar.

By framing search as a parsing problem, the authors could leverage the established theory of formal languages to analyze search complexity. Each production rule in the grammar is associated with a cost attribute, allowing the total cost of a problem to be calculated recursively from its constituent sub-problems.

Recursive cost calculation in an And-Or tree representing a parse tree in the CDP framework.

As illustrated in the figure above, the CDP utilizes And-Or tree structures to model decision-making. In this example, node $A$ acts as an "AND" node, where the total cost is the sum of its components ($5 + 10 + 15 = 30$). Node $S$ acts as an "OR" node, representing a choice between different sub-solutions, where the optimal cost is the minimum of the available paths ($\min\{5, 30\} = 5$).

Monotonicity and the Principle of Optimality

To ensure that these recursive structures can be solved efficiently, the authors define the Monotone CDP (MCDP). A CDP is monotone if its cost functions are non-decreasing with respect to the costs of sub-components. This property is crucial because it allows the problem to obey a generalized version of Bellman’s Principle of Optimality: an optimal global solution can be constructed from optimal local sub-solutions.

The authors provide formal proofs for the optimality of solutions within MCDPs and identify specific classes—acyclic, positive, and strictly monotone—where the minimization problem is guaranteed to be solvable. This distinction between the "syntactic" structure (the grammar) and "semantic" information (heuristics and bounds) clarifies how domain-specific knowledge improves search efficiency.

Unifying Dynamic Programming and Branch & Bound

The CDP framework reveals that DP and B&B are not competing methodologies but rather dual strategies for exploring the same mathematical space:

  • Dynamic Programming is characterized as a bottom-up approach. It begins by solving the smallest sub-problems and iteratively combines them to build the optimal parse tree.
  • Branch & Bound is characterized as a top-down approach. It starts with the set of all possible parse trees and uses cost estimates (bounds) to repeatedly partition the space and prune branches that cannot contain an optimal solution.

This unification allows for a direct comparison of diverse algorithms. For instance, the authors demonstrate that the $SSS^*$ algorithm and the classic alpha-beta pruning algorithm—despite their surface differences—are both variations of the same B&B procedure applied to And-Or graphs. Similarly, algorithms like $A^*$, Dijkstra’s, and $AO^*$ are shown to be special cases of the generalized DP or B&B procedures within the CDP framework.

Conclusion

The Composite Decision Process provided a much-needed theoretical foundation for the study of search and optimization. By showing that heuristic search, DP, and B&B are all facets of the same recursive process, Kumar and Kanal ended decades of debate and offered a unified lens through which to view algorithmic efficiency. While the general CDP minimization problem remains undecidable, the framework identifies the specific properties, such as monotonicity, that make practical problems tractable, guiding the development of more robust search strategies in both AI and Operations Research.

Summary updated

BibTeX
@inproceedings{kumar1983composite,
  author = {Vipin Kumar and Laveen N. Kanal},
  title = {{The Composite Decision Process: A Unifying Formulation for Heuristic Search, Dynamic Programming and Branch \& Bound Procedures}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {1983},
}
Figure