Plan-Length Bounds: Beyond 1-Way Dependency

Mohammad AbdulazizAAAI 2019 · DOI

Abstract

In automated planning, determining the completeness threshold—the maximum steps needed to reach a goal—is essential for proving unsolvability. Traditional compositional methods for calculating these bounds often fail when system variables exhibit cyclic dependencies. This paper presents the traversal diameter ($td$), a new topological metric that remains compositional even under cyclic conditions. We introduce the ARB algorithm, which leverages $td$ to provide tighter plan-length bounds. Experimental results show that our approach improves bounds in 68% of tested problems and significantly boosts the effectiveness of SAT-based planners in solving both solvable and unsolvable instances.

Introduction: The Challenge of Completeness Thresholds

A critical problem in automated planning and model checking is identifying the "completeness threshold." This value represents the maximum number of steps a planner must search before it can definitively conclude that no solution exists. While metrics like the diameter (the longest shortest path) or the recurrence diameter (the longest path without cycles) provide ideal bounds, they are computationally expensive to determine, with the latter being NP-hard.

To address this, researchers often use "compositional" methods. These techniques decompose a complex system into smaller projections, calculate bounds for each, and then combine them. However, existing state-of-the-art methods rely heavily on the assumption that dependencies between variables are acyclic (1-way). When variables exhibit cyclic (2-way) dependencies—where variable A affects B and B affects A—these methods typically revert to a trivial exponential bound ($2^n$), which is often too large to be useful in practice.

The Traversal Diameter: A Compositional Metric

To overcome the limitations of acyclic decomposition, we propose the traversal diameter ($td$). The traversal diameter of a state space is defined as one less than the maximum number of states that can be visited by any path.

Examples of state transition graphs and variable dependency structures that motivate the need for traversal diameter in cyclic systems.

The primary advantage of $td$ is its mathematical behavior during composition. Unlike other diameter metrics, the $td$ of a global system is guaranteed to be less than or equal to the product of the $td$s of its constituent parts, regardless of whether the dependencies between those parts are cyclic or acyclic. We provide a linear-time algorithm, TRAVD, which computes $td$ by identifying Strongly Connected Components (SCCs) within the state transition graph.

The ARB Bounding Procedure

We integrate the traversal diameter into a new bounding procedure called ARB. ARB acts as a sophisticated "base case" for decomposition. When a planning problem cannot be further simplified using traditional acyclic methods, ARB steps in to provide a bound based on the traversal diameter of the remaining atomic sub-problems. This prevents the algorithm from defaulting to the massive state-space maximum and allows for a "divide and conquer" approach even on sub-problems previously considered indecomposable.

Experimental Results

The effectiveness of the ARB algorithm was evaluated against the standard exponential fallback (EXP) using a wide range of benchmarks, including the International Planning Competitions (IPC), the Unsolvability IPC, and specific verification problems like the Hotel-Key protocol.

Comparison of plan-length bounds: HYB<ARB> (proposed) vs. HYB<EXP> (baseline). Points above the diagonal indicate tighter bounds achieved by the ARB algorithm.

Our results demonstrate that the hybrid approach (HYB<ARB>) improved plan-length bounds in 68% of the tested problems. In 71% of these improved cases, the bound was reduced by more than half. Furthermore, when these tighter bounds were used as search horizons for the Madagascar (MP) SAT-planner, the system solved 234 more solvable problems and proved the unsolvability of 56 additional problems that were previously intractable.

Conclusion and Future Work

The traversal diameter provides a robust way to handle cyclic dependencies in plan-length bounding. By allowing for compositional reasoning where it was previously impossible, we achieve significantly tighter bounds and improve the practical performance of SAT-based planners. Future research will focus on more advanced partitioning strategies for state variables to further refine these bounds and reduce the inherent looseness of product-based calculations.

Summary updated

BibTeX
@inproceedings{abdulaziz2019plan,
  author = {Mohammad Abdulaziz},
  title = {{Plan-Length Bounds: Beyond 1-Way Dependency}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017502},
}
Figure