# Computing Plan-Length Bounds Using Lengths of Longest Paths

arXiv: https://arxiv.org/abs/2006.01011 · HTML: https://mlsanity.com/paper/2006.01011/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Jun 2020.

## Built on by (most cited first, 2 of 2)

- [Cost Optimal Planning as Satisfiability](https://mlsanity.com/paper/2103.02355/) (2021)
- [Actions You Can Handle: Dependent Types for AI Plans](https://mlsanity.com/paper/2105.11267/) (2021)

## Abstract (arXiv)

We devise a method to exactly compute the length of the longest simple path in factored state spaces, like state spaces encountered in classical planning. Although the complexity of this problem is NEXP-Hard, we show that our method can be used to compute practically useful upper-bounds on lengths of plans. We show that the computed upper-bounds are significantly (in many cases, orders of magnitude) better than bounds produced by previous bounding techniques and that they can be used to improve the SAT-based planning.