Abstract: The past several years have seen much progress in the area of propositional reasoning and satisfiability testing. There is a growing consensus by researchers on the key technical challenges that need to be addressed in order to maintain this momentum. This paper outlines concrete technical challenges in the core areas of systematic search, stochastic search, problem encodings, and criteria for evaluating progress in this area.
Introduction: Bridging the Planning Gap
In the mid-1990s, the AI planning community faced a significant divide. Traditional "refinement planners," such as UCPOP or Prodigy, operated by searching through spaces of partial plans. While theoretically sound, these systems often struggled to scale to complex problems. Conversely, "radically new" approaches like Graphplan and SATPLAN emerged, demonstrating impressive performance but lacking a clear theoretical connection to classical methods.
Subbarao Kambhampati addresses this gap by proposing a generalized framework that treats these diverse algorithms as different points on a single spectrum. The unifying factor is how these systems handle disjunction—the "either/or" choices inherent in plan synthesis. By viewing planning as a balance between pruning (refinement) and splitting (search), we can identify "disjunctive planning" as a critical path toward scalable AI systems.
The Refinement Planning Framework
The proposed framework centers on a generalized Refinement Planning template. This template provides a structured way to view the evolution of a plan from an initial set of possibilities to a concrete solution.
As shown in the Refine algorithm (Figure 5), the process consists of three primary stages:
- Pruning (Refinement): Constraints are added to a "planset" (a set of potential action sequences) to eliminate non-solutions and narrow the search space.
- Termination Check (Solution Extraction): The system checks if a valid, executable solution can be extracted from the current refined planset.
- Splitting: If a solution isn't found, the planset is divided into smaller subsets, which are then explored in different branches of a search tree.
Disjunctive Planning and the "Splitting Malady"
A key insight of this work is the identification of the "Splitting Malady." Traditional planners often fail to scale because they split the search space too early. Every split creates a new branch, leading to the well-known exponential growth of the search tree.
In contrast, disjunctive planners like Graphplan and SATPLAN succeed by "internalizing" these choices. Instead of creating new branches for every alternative action, they maintain multiple possible plans simultaneously within a single, compact representation using disjunctive constraints.
As illustrated in Figure 3, a disjunctive planset can represent choices like "either Load(A) or Load(B) or Fly(R)" within a single structure. This approach allows the planner to delay expensive splitting operations until the planset has been sufficiently refined. To maintain pruning power without splitting, these planners utilize sophisticated constraint propagation techniques, such as the "mutual exclusivity" (mutex) constraints found in Graphplan.
Strategic Challenges for the Community
To further bridge the gap between these paradigms and drive progress in propositional reasoning and search, five strategic challenges are posed:
- Backward Disjunctive Planning: Develop planners based on backward state-space or plan-space refinements, moving beyond the forward-only approach of Graphplan.
- Refinement Tradeoffs: Quantify the performance tradeoffs between different refinement types in a disjunctive context.
- Encoding Difficulty: Characterize how specific planning refinements influence the complexity and solvability of the resulting SAT encodings.
- Controlled Splitting: Explore hybrid strategies that find a "sweet spot" between splitting at every choice and never splitting at all.
- Alternative Representations: Investigate non-standard plan representations to determine if they offer superior efficiency for disjunctive reasoning.
Conclusion
The transition toward disjunctive planning represents a fundamental shift in how we approach complex search problems. While internalizing disjunction avoids the immediate explosion of search branches, it necessitates more powerful constraint propagation to compensate for the loss of pruning power. Future work will focus on hybrid systems that combine the goal-directed strengths of classical planning with the high-performance reasoning of modern SAT-based methods.
Summary updated