Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence

Pascal Lauer; Songtuan Lin; Pascal Bercher

doi:10.1609/icaps.v35i1.36102

Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence

Pascal Lauer
, Songtuan Lin
, Pascal Bercher

The Australian National University

Research output: Contribution to journal › Conference article

1 Citation (Scopus)

Abstract

Plan verification is a canonical problem within any planning setting to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.

Original language	English
Pages (from-to)	64-73
Number of pages	10
Journal	Proceedings International Conference on Automated Planning and Scheduling, ICAPS
Volume	35
Issue number	1
DOIs	https://doi.org/10.1609/icaps.v35i1.36102
Publication status	Published - 16 Sept 2025
Event	35th International Conference on Automated Planning and Scheduling, ICAPS 2025 - Melbourne, Australia Duration: 9 Nov 2025 → 14 Nov 2025

Access to Document

10.1609/icaps.v35i1.36102

Cite this

@article{0d170a0d434e4354ae230ae900892f53,

title = "Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence",

abstract = "Plan verification is a canonical problem within any planning setting to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.",

author = "Pascal Lauer and Songtuan Lin and Pascal Bercher",

note = "Publisher Copyright: {\textcopyright} 2025, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 35th International Conference on Automated Planning and Scheduling, ICAPS 2025 ; Conference date: 09-11-2025 Through 14-11-2025",

year = "2025",

month = sep,

day = "16",

doi = "10.1609/icaps.v35i1.36102",

language = "English",

volume = "35",

pages = "64--73",

journal = "Proceedings International Conference on Automated Planning and Scheduling, ICAPS",

issn = "2334-0835",

publisher = "Association for the Advancement of Artificial Intelligence",

number = "1",

}

TY - JOUR

T1 - Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence

AU - Lauer, Pascal

AU - Lin, Songtuan

AU - Bercher, Pascal

PY - 2025/9/16

Y1 - 2025/9/16

N2 - Plan verification is a canonical problem within any planning setting to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.

AB - Plan verification is a canonical problem within any planning setting to ensure correctness. This problem is closely linked to the bounded plan existence problem. We analyze the complexity of these problems on lifted representations for Hierarchical Task Network (HTN) Planning. On top of the general analysis, we impose constraints on method orderings and the amount of tasks that methods decompose to. This pinpoints subclasses with lower complexity. Our results confirm the existence of more efficient algorithms when operating on the lifted, instead of grounded, representation.

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

U2 - 10.1609/icaps.v35i1.36102

DO - 10.1609/icaps.v35i1.36102

M3 - Conference article

AN - SCOPUS:105017508163

SN - 2334-0835

VL - 35

SP - 64

EP - 73

JO - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

JF - Proceedings International Conference on Automated Planning and Scheduling, ICAPS

IS - 1

T2 - 35th International Conference on Automated Planning and Scheduling, ICAPS 2025

Y2 - 9 November 2025 through 14 November 2025

ER -

Tight Bounds for Lifted HTN Plan Verification and Bounded Plan Existence

Abstract

Access to Document

Other files and links

Fingerprint

Cite this