AAAI 2023technical8 citations
On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm
Songtuan Lin, Gregor Behnke, Simona Ondrčková, Roman Barták, Pascal Bercher
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.
BibTeX
@article{Lin_Behnke_Ondrčková_Barták_Bercher_2023, title={On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26420}, DOI={10.1609/aaai.v37i10.26420}, abstractNote={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.}, number={10}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Lin, Songtuan and Behnke, Gregor and Ondrčková, Simona and Barták, Roman and Bercher, Pascal}, year={2023}, month={Jun.}, pages={12041-12048} }