Fat- and Heavy-Tailed Behavior in Satisficing Planning

Eldan Cohen, J. Christopher BeckAAAI 2018 · OpenReview

Abstract

In this work, we study the runtime distribution of satisficing planning in ensembles of random planning problems and in multiple runs of a randomized heuristic search on a single planning instance. Using common heuristic functions (such as FF) and six benchmark problem domains from the IPC, we find a heavy-tailed behavior, similar to that found in CSP and SAT. We investigate two notions of constrainedness, often used in the modeling of planning problems, and show that the heavy-tailed behavior tends to appear in relatively relaxed problems, where the required effort is, on average, low. Finally, we show that as with randomized restarts in CSP and SAT solving, recent search enhancements that incorporate randomness in the search process can help mitigate the effect of the heavy tail.

Introduction: The Outlier Problem in Planning

In automated planning, researchers frequently encounter "exceptionally hard problems" (EHPs)—instances where a planner that typically solves problems in seconds suddenly stalls for hours. While this phenomenon is well-recognized in Constraint Satisfaction Problems (CSP) and Boolean Satisfiability (SAT), its formal characterization in satisficing planning (finding any valid plan) has been less explored.

This paper demonstrates that these outliers are not merely random bad luck but are symptomatic of heavy-tailed runtime distributions. Unlike normal distributions, where extreme values are exponentially rare, heavy-tailed distributions have tails that decay according to a power law, making extreme outliers statistically "expected."

Methodology

To quantify tail behavior, we employed two primary statistical metrics:

  1. L-kurtosis ($\tau_4$): A measure of the "fatness" of the distribution's tail.
  2. Stability Index ($\alpha$): A parameter where $\alpha < 2$ indicates infinite variance, and $\alpha < 1$ indicates an infinite mean.

Since standard Greedy Best-First Search (GBFS) is deterministic, we introduced a $p$-randomized heuristic. By adding controlled noise to heuristic values, we could execute multiple runs on the same problem instance to observe how search choices alone influence runtime variance. We tested this across six IPC benchmark domains, including resource-constrained (e.g., NoMystery) and goal-constrained (e.g., Freecell) tasks, primarily using the FF (Fast-Forward) heuristic.

The Relaxation Paradox

A key finding of this research is the "Relaxation Paradox." Intuitively, one might expect heavy tails to appear in the most difficult, highly constrained problems. However, our results show that heavy-tailed behavior is most prevalent in relatively relaxed problems.

Survival functions (1-CDF) for different constrainedness levels (C) across three experimental settings. Higher C values (more relaxed problems) correlate with higher L-kurtosis ($\tau_4$), indicating heavier tails.

In highly constrained environments, the search space is restricted; the planner either finds a solution quickly or exhausts the possibilities and fails. In relaxed environments, the search space is vast. A single suboptimal choice can lead the planner into a massive local minimum—a "black hole" of states—that requires exhaustive exploration before the planner can return to a productive path. As shown in the figure above, as the problem becomes more relaxed (increasing $C$ value), the L-kurtosis ($\tau_4$) increases significantly, indicating a transition into a heavy-tailed regime.

Empirical Evidence of Heavy Tails

Our analysis confirms that planning runtimes often follow power-law distributions. In the NoMystery domain, we observed stability indices as low as $\alpha \approx 0.82$, implying that the underlying distribution has both infinite mean and infinite variance.

Statistical evidence of heavy tails in planning: (Left) Power-law fit to runtime distribution; (Middle) Non-stabilizing sample mean in heavy-tailed regimes; (Right) Shift toward heavy-tailed behavior as problems become more relaxed (higher C).

As shown in the figure above, the sample mean of expanded nodes fails to stabilize in heavy-tailed regimes (middle panel), fluctuating wildly as new "outliers" are encountered. The left panel demonstrates the characteristic linear decay on a log-log survival plot, which is the hallmark of a power-law distribution.

Mitigating the Tail with Randomization

The study also provides a theoretical explanation for the success of modern search enhancements like $\epsilon$-GBFS and Type-GBFS. By incorporating non-greedy randomized exploration, these algorithms effectively "clip" the heavy tail. Instead of getting trapped indefinitely in a single large local minimum, the randomized exploration allows the search to "jump" out, significantly reducing the probability of extremely long runs and stabilizing the average performance.

Conclusion

This work establishes that heavy-tailed behavior is a fundamental characteristic of satisficing planning, particularly in relaxed problem regions. Recognizing this statistical reality suggests that future planner benchmarks should explicitly include relaxed instances to evaluate robustness against heavy tails. Moreover, it validates the use of randomization not just as a heuristic "trick," but as a necessary structural fix for the heavy-tail problem in heuristic search.

Summary updated

Abstract

In this work, we study the runtime distribution of satisficing planning in ensembles of random planning problems and in multiple runs of a randomized heuristic search on a single planning instance. Using common heuristic functions (such as FF) and six benchmark problem domains from the IPC, we find a heavy-tailed behavior, similar to that found in CSP and SAT. We investigate two notions of constrainedness, often used in the modeling of planning problems, and show that the heavy-tailed behavior tends to appear in relatively relaxed problems, where the required effort is, on average, low. Finally, we show that as with randomized restarts in CSP and SAT solving, recent search enhancements that incorporate randomness in the search process can help mitigate the effect of the heavy tail.
BibTeX
@inproceedings{cohen2018fat,
  author = {Eldan Cohen and J. Christopher Beck},
  title = {{Fat- and Heavy-Tailed Behavior in Satisficing Planning}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2018},
  url = {https://openreview.net/forum?id=rk-e-AeuWB},
}
Figure