Computing Plan-Length Bounds Using Lengths of Longest Paths
This work addresses the challenge of improving plan-length estimation for classical planning, which can enhance SAT-based planning, though it appears incremental as it builds on existing bounding techniques.
The authors tackled the problem of computing upper bounds on plan lengths in classical planning by exactly computing the longest simple path in factored state spaces, resulting in bounds that are significantly better, often by orders of magnitude, than previous methods.
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.