On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm

Songtuan Lin, Gregor Behnke, Simona Ondrcková, Roman Barták, Pascal Bercher

AAAI 2023 pp. 12041-12048

doi:10.1609/AAAI.V37I10.26420 /aaai/2023/lin2023aaai-total/

Abstract

In this paper, we consider the plan verification problem for totally ordered (TO) HTN planning. The problem is proved to be solvable in polynomial time by recognizing its connection to the membership decision problem for context-free grammars. Currently, most HTN plan verification approaches do not have special treatments for the TO configuration, and the only one features such an optimization still relies on an exhaustive search. Hence, we will develop a new TOHTN plan verification approach in this paper by extending the standard CYK parsing algorithm which acts as the best decision procedure in general.

PDF AAAI Semantic Scholar

Cite

Text

Lin et al. "On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I10.26420

Markdown

[Lin et al. "On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/lin2023aaai-total/) doi:10.1609/AAAI.V37I10.26420

BibTeX

@inproceedings{lin2023aaai-total,
  title     = {{On Total-Order HTN Plan Verification with Method Preconditions - An Extension of the CYK Parsing Algorithm}},
  author    = {Lin, Songtuan and Behnke, Gregor and Ondrcková, Simona and Barták, Roman and Bercher, Pascal},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2023},
  pages     = {12041-12048},
  doi       = {10.1609/AAAI.V37I10.26420},
  url       = {https://mlanthology.org/aaai/2023/lin2023aaai-total/}
}