Introduction
In classical AI planning, SAT-based planners translate planning problems into a sequence of Boolean satisfiability (SAT) queries. These planners iteratively check for a plan of length $k=1, 2, 3, \dots$ until a solution is found. A significant bottleneck in this approach is the time spent proving the unsatisfiability of queries for horizons shorter than the optimal plan length. If a tight upper bound on the plan length—a "completeness threshold"—were known, planners could skip these costly queries or definitively prove a problem's unsolvability.
The Challenge of Plan-Length Bounds
The most accurate bound is the state space diameter ($d$), the maximum distance between any two reachable states. However, computing $d$ for factored systems (where states are defined by multiple variables) is computationally prohibitive. While the traversal diameter ($td$) is easier to compute, it often yields excessively large bounds (e.g., $10^9$) that offer little practical benefit.
This research focuses on the recurrence diameter ($rd$), defined as the length of the longest simple path in a state space. While $rd$ is tighter than $td$, it remains NEXP-hard to compute. This paper introduces a novel compositional approach and a compact SMT encoding to make $rd$ computation feasible and useful for SAT-based planning.
Methodology: Compositional Bounding and SMT Encoding
The authors propose a "divide and conquer" strategy to manage the complexity of the state space. Instead of analyzing the entire system at once, the problem is decomposed into smaller subsystems using abstractions such as projections and snapshots.
To compute the $rd$ for these base-case subsystems, the researchers developed a symbolic SMT encoding. Unlike explicit graph-based methods that require constructing the full state space, this encoding describes domain rules (actions, preconditions, and effects) directly to an SMT solver (e.g., Yices). This allows the solver to explore the state space lazily, focusing only on relevant paths.
Furthermore, the authors introduced hybrid functions ($b_1, b_2$) to balance accuracy and computational cost. For instance, the $b_2$ function computes $rd$ only for subsystems with fewer than 50 states, falling back to $td$ for larger components.
Key Insights
A critical theoretical insight is that while the diameter ($d$) cannot be easily bounded by the diameters of its projections, the recurrence diameter ($rd$) is naturally compositional. This mathematical property makes $rd$ a superior choice for modular bounding algorithms. Additionally, the authors demonstrated that $rd$ can be exponentially smaller than $td$, potentially reducing bounds from billions to hundreds.
Experimental Results
The proposed methods were evaluated using standard benchmarks from the International Planning Competition (IPC), including domains like Logistics, BlocksWorld, and Satellite.
The results indicate that $rd$-based bounds are significantly tighter than previous $td$-based state-of-the-art. In domains such as TPP and Nomystery, bounds were reduced by 50% to two orders of magnitude. In extreme cases like BlocksWorld, $rd$ values were found to be less than 10, while $td$ methods produced bounds exceeding $10^9$.
Integrating these tighter bounds into the Madagascar (MP) planner led to an increase in problem coverage. While computing $rd$ is more time-intensive than $td$, the investment pays off for any problem requiring more than five seconds of planning time by significantly reducing the search horizon.
Conclusion and Future Work
By leveraging compositional analysis and SMT-based symbolic search, this work provides a practical way to compute tight plan-length bounds. Future research may explore "radius" versions of these diameters—focusing on paths starting specifically from the initial state—to derive even more localized and tighter bounds for specific planning instances.
Summary updated