On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

Songtuan Lin; Conny Olz; Malte Helmert; Pascal Bercher

doi:10.1609/aaai.v38i18.30000

On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

Songtuan Lin
, Conny Olz
, Malte Helmert
, Pascal Bercher

School of Computing

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

6 Citations (Scopus)

Abstract

In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.

Original language	English
Title of host publication	Proceedings of the AAAI Conference on Artificial Intelligence
Editors	Michael Wooldridge, Jennifer Dy, Sriraam Natarajan
Place of Publication	USA
Publisher	AAAI Press
Pages	20203-20211
Number of pages	9
Volume	38
Edition	18
ISBN (Print)	978-1-57735-887-9
DOIs	https://doi.org/10.1609/aaai.v38i18.30000
Publication status	Published - 24 Mar 2024
Event	38th AAAI Conference on Artificial Intelligence, AAAI 2024 - Vancouver, Canada Duration: 20 Feb 2024 → 27 Feb 2024

Publication series

Name	Proceedings of the AAAI Conference on Artificial Intelligence
Publisher	Association for the Advancement of Artificial Intelligence
ISSN (Print)	2159-5399

Conference

Conference	38th AAAI Conference on Artificial Intelligence, AAAI 2024
Country/Territory	Canada
City	Vancouver
Period	20/02/24 → 27/02/24

Access to Document

10.1609/aaai.v38i18.30000

Cite this

Lin, S., Olz, C., Helmert, M., & Bercher, P. (2024). On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence. In M. Wooldridge, J. Dy, & S. Natarajan (Eds.), Proceedings of the AAAI Conference on Artificial Intelligence (18 ed., Vol. 38, pp. 20203-20211). (Proceedings of the AAAI Conference on Artificial Intelligence). AAAI Press. https://doi.org/10.1609/aaai.v38i18.30000

Lin, Songtuan ; Olz, Conny ; Helmert, Malte et al. / On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence. Proceedings of the AAAI Conference on Artificial Intelligence. editor / Michael Wooldridge ; Jennifer Dy ; Sriraam Natarajan. Vol. 38 18. ed. USA : AAAI Press, 2024. pp. 20203-20211 (Proceedings of the AAAI Conference on Artificial Intelligence).

@inproceedings{611dc899cb074954957d4bc23eeaa424,

title = "On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence",

abstract = "In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.",

author = "Songtuan Lin and Conny Olz and Malte Helmert and Pascal Bercher",

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

year = "2024",

month = mar,

day = "24",

doi = "10.1609/aaai.v38i18.30000",

language = "English",

isbn = "978-1-57735-887-9",

volume = "38",

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

publisher = "AAAI Press",

pages = "20203--20211",

editor = "Michael Wooldridge and Dy, \{ Jennifer\} and Sriraam Natarajan",

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

edition = "18",

}

Lin, S, Olz, C, Helmert, M & Bercher, P 2024, On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence. in M Wooldridge, J Dy & S Natarajan (eds), Proceedings of the AAAI Conference on Artificial Intelligence. 18 edn, vol. 38, Proceedings of the AAAI Conference on Artificial Intelligence, AAAI Press, USA, pp. 20203-20211, 38th AAAI Conference on Artificial Intelligence, AAAI 2024, Vancouver, Canada, 20/02/24. https://doi.org/10.1609/aaai.v38i18.30000

On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence. / Lin, Songtuan; Olz, Conny; Helmert, Malte et al.
Proceedings of the AAAI Conference on Artificial Intelligence. ed. / Michael Wooldridge; Jennifer Dy; Sriraam Natarajan. Vol. 38 18. ed. USA: AAAI Press, 2024. p. 20203-20211 (Proceedings of the AAAI Conference on Artificial Intelligence).

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

TY - GEN

T1 - On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

AU - Lin, Songtuan

AU - Olz, Conny

AU - Helmert, Malte

AU - Bercher, Pascal

PY - 2024/3/24

Y1 - 2024/3/24

N2 - In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.

AB - In this paper we study the computational complexity of several reasoning tasks centered around the bounded plan existence problem. We do this for standard classical planning and hierarchical task network (HTN) planning and each for a grounded and a lifted representation. Whereas bounded plan existence complexity is known for classical planning, it has not yet been studied for HTN planning. For plan verification, results were available for both formalisms except for the lifted HTN planning. We will present lower and upper bounds of the complexity of plan verification in lifted HTN planning and provide some new insights into its grounded counterpart, in which we show that verification is not just NP-complete in the general case, but already for a severely restricted special case. Finally, we show the complexity concerning verifying the optimality of a given plan and discuss its connection to the bounded plan existence problem.

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

U2 - 10.1609/aaai.v38i18.30000

DO - 10.1609/aaai.v38i18.30000

M3 - Conference Paper

AN - SCOPUS:85189536591

SN - 978-1-57735-887-9

VL - 38

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 20203

EP - 20211

BT - Proceedings of the AAAI Conference on Artificial Intelligence

A2 - Wooldridge, Michael

A2 - Dy, Jennifer

A2 - Natarajan, Sriraam

PB - AAAI Press

CY - USA

T2 - 38th AAAI Conference on Artificial Intelligence, AAAI 2024

Y2 - 20 February 2024 through 27 February 2024

ER -

Lin S, Olz C, Helmert M, Bercher P. On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence. In Wooldridge M, Dy J, Natarajan S, editors, Proceedings of the AAAI Conference on Artificial Intelligence. 18 ed. Vol. 38. USA: AAAI Press. 2024. p. 20203-20211. (Proceedings of the AAAI Conference on Artificial Intelligence). doi: 10.1609/aaai.v38i18.30000

On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

On the Computational Complexity of Plan Verification, (Bounded) Plan-Optimality Verification, and Bounded Plan Existence

Cite this