ML Anthology

Computing Plan-Length Bounds Using Lengths of Longest Paths

Mohammad Abdulaziz, Dominik Berger
AAAI 2021 pp. 11709-11717
doi:10.1609/AAAI.V35I13.17392 /aaai/2021/abdulaziz2021aaai-computing/

Abstract

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 better than bounds produced by state-of-the-art bounding techniques and that they can be used to improve the SAT-based planning.

PDF AAAI Semantic Scholar

Cite

Text

Abdulaziz and Berger. "Computing Plan-Length Bounds Using Lengths of Longest Paths." AAAI Conference on Artificial Intelligence, 2021. doi:10.1609/AAAI.V35I13.17392

Markdown

[Abdulaziz and Berger. "Computing Plan-Length Bounds Using Lengths of Longest Paths." AAAI Conference on Artificial Intelligence, 2021.](https://mlanthology.org/aaai/2021/abdulaziz2021aaai-computing/) doi:10.1609/AAAI.V35I13.17392

BibTeX

@inproceedings{abdulaziz2021aaai-computing,
  title     = {{Computing Plan-Length Bounds Using Lengths of Longest Paths}},
  author    = {Abdulaziz, Mohammad and Berger, Dominik},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2021},
  pages     = {11709-11717},
  doi       = {10.1609/AAAI.V35I13.17392},
  url       = {https://mlanthology.org/aaai/2021/abdulaziz2021aaai-computing/}
}