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

doi:10.1609/aaai.v37i10.26420

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

School of Computing

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

13 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the AAAI Conference on Artificial Intelligence
Editors	Brian Williams, Yiling Chen, Jennifer Neville
Place of Publication	USA
Publisher	AAAI Press
Pages	12041-12048
Number of pages	8
Volume	37
Edition	10
ISBN (Electronic)	978-1-57735-880-0
DOIs	https://doi.org/10.1609/aaai.v37i10.26420
Publication status	Published - 26 Jun 2023
Event	37th AAAI Conference on Artificial Intelligence, AAAI 2023 - Washington, United States Duration: 7 Feb 2023 → 14 Feb 2023

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence.
Publisher	AAAI Press
Number	10
Volume	37
ISSN (Print)	2159-5399

Conference

Conference	37th AAAI Conference on Artificial Intelligence, AAAI 2023
Country/Territory	United States
City	Washington
Period	7/02/23 → 14/02/23

Access to Document

10.1609/aaai.v37i10.26420Licence: Unspecified

Cite this

Lin, S., Behnke, G., Ondrčková, S., Barták, R., & Bercher, P. (2023). On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm. In B. Williams, Y. Chen, & J. Neville (Eds.), Proceedings of the AAAI Conference on Artificial Intelligence (10 ed., Vol. 37, pp. 12041-12048). (Proceedings of the AAAI Conference on Artificial Intelligence.; Vol. 37, No. 10). AAAI Press. https://doi.org/10.1609/aaai.v37i10.26420

Lin, Songtuan ; Behnke, Gregor ; Ondrčková, Simona et al. / On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm. Proceedings of the AAAI Conference on Artificial Intelligence. editor / Brian Williams ; Yiling Chen ; Jennifer Neville. Vol. 37 10. ed. USA : AAAI Press, 2023. pp. 12041-12048 (Proceedings of the AAAI Conference on Artificial Intelligence.; 10).

@inproceedings{a4d3146bd2144a6faaf2117ee2984843,

title = "On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm",

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.",

author = "Songtuan Lin and Gregor Behnke and Simona Ondr{\v c}kov{\'a} and Roman Bart{\'a}k and Pascal Bercher",

note = "Publisher Copyright: Copyright {\textcopyright} 2023, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 37th AAAI Conference on Artificial Intelligence, AAAI 2023 ; Conference date: 07-02-2023 Through 14-02-2023",

year = "2023",

month = jun,

day = "26",

doi = "10.1609/aaai.v37i10.26420",

language = "English",

volume = "37",

series = "Proceedings of the AAAI Conference on Artificial Intelligence.",

publisher = "AAAI Press",

number = "10",

pages = "12041--12048",

editor = "Brian Williams and Yiling Chen and Jennifer Neville",

booktitle = "Proceedings of the AAAI Conference on Artificial Intelligence",

edition = "10",

}

Lin, S, Behnke, G, Ondrčková, S, Barták, R & Bercher, P 2023, On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm. in B Williams, Y Chen & J Neville (eds), Proceedings of the AAAI Conference on Artificial Intelligence. 10 edn, vol. 37, Proceedings of the AAAI Conference on Artificial Intelligence., no. 10, vol. 37, AAAI Press, USA, pp. 12041-12048, 37th AAAI Conference on Artificial Intelligence, AAAI 2023, Washington, United States, 7/02/23. https://doi.org/10.1609/aaai.v37i10.26420

On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm. / Lin, Songtuan; Behnke, Gregor; Ondrčková, Simona et al.
Proceedings of the AAAI Conference on Artificial Intelligence. ed. / Brian Williams; Yiling Chen; Jennifer Neville. Vol. 37 10. ed. USA: AAAI Press, 2023. p. 12041-12048 (Proceedings of the AAAI Conference on Artificial Intelligence.; Vol. 37, No. 10).

Research output: Chapter in Book/Report/Conference proceeding › Conference Paper › peer-review

TY - GEN

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

AU - Lin, Songtuan

AU - Behnke, Gregor

AU - Ondrčková, Simona

AU - Barták, Roman

AU - Bercher, Pascal

PY - 2023/6/26

Y1 - 2023/6/26

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/85161428428

U2 - 10.1609/aaai.v37i10.26420

DO - 10.1609/aaai.v37i10.26420

M3 - Conference Paper

VL - 37

T3 - Proceedings of the AAAI Conference on Artificial Intelligence.

SP - 12041

EP - 12048

BT - Proceedings of the AAAI Conference on Artificial Intelligence

A2 - Williams, Brian

A2 - Chen, Yiling

A2 - Neville, Jennifer

PB - AAAI Press

CY - USA

T2 - 37th AAAI Conference on Artificial Intelligence, AAAI 2023

Y2 - 7 February 2023 through 14 February 2023

ER -

Lin S, Behnke G, Ondrčková S, Barták R, Bercher P. On Total-Order HTN Plan Verification with Method Preconditions – An Extension of the CYK Parsing Algorithm. In Williams B, Chen Y, Neville J, editors, Proceedings of the AAAI Conference on Artificial Intelligence. 10 ed. Vol. 37. USA: AAAI Press. 2023. p. 12041-12048. (Proceedings of the AAAI Conference on Artificial Intelligence.; 10). doi: 10.1609/aaai.v37i10.26420

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this