A Landmark-Cut Heuristic for Lifted Optimal Planning

Julia Wichlacz; Daniel Höller; Daniel Fišer; Jörg Hoffmann

doi:10.3233/FAIA230569

A Landmark-Cut Heuristic for Lifted Optimal Planning

Julia Wichlacz^*, Daniel Höller, Daniel Fišer, Jörg Hoffmann

^*Corresponding author for this work

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

1 Citation (Scopus)

Abstract

Lifted planning - finding plans directly on the PDDL input model - has attracted renewed attention during the last years. This avoids the process of grounding, which can become computationally prohibitive very easily. However, the main focus of recent research in this area has been on satisficing, i.e., (potentially) suboptimal planning. We present a novel heuristic for optimal lifted planning. Our basic idea is inspired by the LM-cut heuristic, which has been very successful in grounded optimal planning. Like LM-cut, we generate cut-based landmarks via back-chaining from the goal, generating cuts of partially grounded actions. However, exactly mimicking the ground formulation is not feasible, this includes computing the h^max heuristic several times for one computation of the LM-cut heuristic (which is already NP-hard to compute). We show that our heuristic is admissible and evaluate it in a cost optimal setting.

Original language	English
Title of host publication	ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings
Editors	Kobi Gal, Kobi Gal, Ann Nowe, Grzegorz J. Nalepa, Roy Fairstein, Roxana Radulescu
Number of pages	8
Publisher	IOS Press
Publication date	28 Sept 2023
Pages	2623-2630
ISBN (Electronic)	9781643684369
DOIs	https://doi.org/10.3233/FAIA230569
Publication status	Published - 28 Sept 2023
Externally published	Yes
Event	26th European Conference on Artificial Intelligence, ECAI 2023 - Krakow, Poland Duration: 30 Sept 2023 → 4 Oct 2023

Conference

Conference	26th European Conference on Artificial Intelligence, ECAI 2023
Country/Territory	Poland
City	Krakow
Period	30/09/2023 → 04/10/2023
Sponsor	Amazon Alexa, APTIV, et al., Hewlett Packard, IDEAS, Software Force

Series	Frontiers in Artificial Intelligence and Applications
Volume	372
ISSN	0922-6389

Bibliographical note

Publisher Copyright:
© 2023 The Authors.

Access to Document

10.3233/FAIA230569

AUB Link

Search for the material in Aalborg University Library's search engine

Cite this

Wichlacz, J., Höller, D., Fišer, D., & Hoffmann, J. (2023). A Landmark-Cut Heuristic for Lifted Optimal Planning. In K. Gal, K. Gal, A. Nowe, G. J. Nalepa, R. Fairstein, & R. Radulescu (Eds.), ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings (pp. 2623-2630). IOS Press. https://doi.org/10.3233/FAIA230569

Wichlacz, Julia ; Höller, Daniel ; Fišer, Daniel et al. / A Landmark-Cut Heuristic for Lifted Optimal Planning. ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. editor / Kobi Gal ; Kobi Gal ; Ann Nowe ; Grzegorz J. Nalepa ; Roy Fairstein ; Roxana Radulescu. IOS Press, 2023. pp. 2623-2630 (Frontiers in Artificial Intelligence and Applications, Vol. 372).

@inproceedings{7c20852dc03f4f2a917df1fcaff38de4,

title = "A Landmark-Cut Heuristic for Lifted Optimal Planning",

abstract = "Lifted planning - finding plans directly on the PDDL input model - has attracted renewed attention during the last years. This avoids the process of grounding, which can become computationally prohibitive very easily. However, the main focus of recent research in this area has been on satisficing, i.e., (potentially) suboptimal planning. We present a novel heuristic for optimal lifted planning. Our basic idea is inspired by the LM-cut heuristic, which has been very successful in grounded optimal planning. Like LM-cut, we generate cut-based landmarks via back-chaining from the goal, generating cuts of partially grounded actions. However, exactly mimicking the ground formulation is not feasible, this includes computing the hmax heuristic several times for one computation of the LM-cut heuristic (which is already NP-hard to compute). We show that our heuristic is admissible and evaluate it in a cost optimal setting.",

author = "Julia Wichlacz and Daniel H{\"o}ller and Daniel Fi{\v s}er and J{\"o}rg Hoffmann",

note = "Publisher Copyright: {\textcopyright} 2023 The Authors.; 26th European Conference on Artificial Intelligence, ECAI 2023 ; Conference date: 30-09-2023 Through 04-10-2023",

year = "2023",

month = sep,

day = "28",

doi = "10.3233/FAIA230569",

language = "English",

series = "Frontiers in Artificial Intelligence and Applications",

publisher = "IOS Press",

pages = "2623--2630",

editor = "Kobi Gal and Kobi Gal and Ann Nowe and Nalepa, {Grzegorz J.} and Roy Fairstein and Roxana Radulescu",

booktitle = "ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings",

address = "Netherlands",

}

Wichlacz, J, Höller, D, Fišer, D & Hoffmann, J 2023, A Landmark-Cut Heuristic for Lifted Optimal Planning. in K Gal, K Gal, A Nowe, GJ Nalepa, R Fairstein & R Radulescu (eds), ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. IOS Press, Frontiers in Artificial Intelligence and Applications, vol. 372, pp. 2623-2630, 26th European Conference on Artificial Intelligence, ECAI 2023, Krakow, Poland, 30/09/2023. https://doi.org/10.3233/FAIA230569

A Landmark-Cut Heuristic for Lifted Optimal Planning. / Wichlacz, Julia; Höller, Daniel; Fišer, Daniel et al.
ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. ed. / Kobi Gal; Kobi Gal; Ann Nowe; Grzegorz J. Nalepa; Roy Fairstein; Roxana Radulescu. IOS Press, 2023. p. 2623-2630 (Frontiers in Artificial Intelligence and Applications, Vol. 372).

Research output: Contribution to book/anthology/report/conference proceeding › Article in proceeding › Research › peer-review

TY - GEN

T1 - A Landmark-Cut Heuristic for Lifted Optimal Planning

AU - Wichlacz, Julia

AU - Höller, Daniel

AU - Fišer, Daniel

AU - Hoffmann, Jörg

PY - 2023/9/28

Y1 - 2023/9/28

N2 - Lifted planning - finding plans directly on the PDDL input model - has attracted renewed attention during the last years. This avoids the process of grounding, which can become computationally prohibitive very easily. However, the main focus of recent research in this area has been on satisficing, i.e., (potentially) suboptimal planning. We present a novel heuristic for optimal lifted planning. Our basic idea is inspired by the LM-cut heuristic, which has been very successful in grounded optimal planning. Like LM-cut, we generate cut-based landmarks via back-chaining from the goal, generating cuts of partially grounded actions. However, exactly mimicking the ground formulation is not feasible, this includes computing the hmax heuristic several times for one computation of the LM-cut heuristic (which is already NP-hard to compute). We show that our heuristic is admissible and evaluate it in a cost optimal setting.

AB - Lifted planning - finding plans directly on the PDDL input model - has attracted renewed attention during the last years. This avoids the process of grounding, which can become computationally prohibitive very easily. However, the main focus of recent research in this area has been on satisficing, i.e., (potentially) suboptimal planning. We present a novel heuristic for optimal lifted planning. Our basic idea is inspired by the LM-cut heuristic, which has been very successful in grounded optimal planning. Like LM-cut, we generate cut-based landmarks via back-chaining from the goal, generating cuts of partially grounded actions. However, exactly mimicking the ground formulation is not feasible, this includes computing the hmax heuristic several times for one computation of the LM-cut heuristic (which is already NP-hard to compute). We show that our heuristic is admissible and evaluate it in a cost optimal setting.

UR - http://www.scopus.com/inward/record.url?scp=85175870927&partnerID=8YFLogxK

U2 - 10.3233/FAIA230569

DO - 10.3233/FAIA230569

M3 - Article in proceeding

AN - SCOPUS:85175870927

T3 - Frontiers in Artificial Intelligence and Applications

SP - 2623

EP - 2630

BT - ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings

A2 - Gal, Kobi

A2 - Nowe, Ann

A2 - Nalepa, Grzegorz J.

A2 - Fairstein, Roy

A2 - Radulescu, Roxana

PB - IOS Press

T2 - 26th European Conference on Artificial Intelligence, ECAI 2023

Y2 - 30 September 2023 through 4 October 2023

ER -

Wichlacz J, Höller D, Fišer D, Hoffmann J. A Landmark-Cut Heuristic for Lifted Optimal Planning. In Gal K, Gal K, Nowe A, Nalepa GJ, Fairstein R, Radulescu R, editors, ECAI 2023 - 26th European Conference on Artificial Intelligence, including 12th Conference on Prestigious Applications of Intelligent Systems, PAIS 2023 - Proceedings. IOS Press. 2023. p. 2623-2630. (Frontiers in Artificial Intelligence and Applications, Vol. 372). doi: 10.3233/FAIA230569

A Landmark-Cut Heuristic for Lifted Optimal Planning

Abstract

Conference

Bibliographical note

Access to Document

AUB Link

Other files and links

Fingerprint

Cite this