A Lifted Backward Computation of hAdd. Lauer, P., Torralba, Á., Höller, D., & Hoffmann, J. In Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024), 2024. This paper is the workshop version of Lauer et al. in ICAPS 2025. Please refer to the conference version instead.![A Lifted Backward Computation of hAdd [pdf]](https://bibbase.org/img/filetypes/pdf.svg "pdf")
Paper abstract bibtex 1 download Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.
@inproceedings{Lauer2024LiftedhAdd,
author = {Pascal Lauer and {\'{A}}lvaro Torralba and Daniel H{\"{o}}ller and J{\"{o}}rg Hoffmann},
booktitle = {Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024)},
note = {<i>This paper is the workshop version of Lauer et al. in ICAPS 2025. Please refer to the conference version instead.</i>},
title = {A Lifted Backward Computation of hAdd},
url_Paper = {https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf},
Xurl_Slides = {talks/hsdip-2024.pdf},
Xurl_Technical_Report = {manuscripts/hsdip2024-tr.pdf},
year = {2024},
abstract = {Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.}
}
Downloads: 1
{"_id":"PS8dgCqEGb2k6aXZY","bibbaseid":"lauer-torralba-hller-hoffmann-aliftedbackwardcomputationofhadd-2024","author_short":["Lauer, P.","Torralba, Á.","Höller, D.","Hoffmann, J."],"bibdata":{"bibtype":"inproceedings","type":"inproceedings","author":[{"firstnames":["Pascal"],"propositions":[],"lastnames":["Lauer"],"suffixes":[]},{"firstnames":["Álvaro"],"propositions":[],"lastnames":["Torralba"],"suffixes":[]},{"firstnames":["Daniel"],"propositions":[],"lastnames":["Höller"],"suffixes":[]},{"firstnames":["Jörg"],"propositions":[],"lastnames":["Hoffmann"],"suffixes":[]}],"booktitle":"Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024)","note":"<i>This paper is the workshop version of Lauer et al. in ICAPS 2025. Please refer to the conference version instead.</i>","title":"A Lifted Backward Computation of hAdd","url_paper":"https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf","xurl_slides":"talks/hsdip-2024.pdf","xurl_technical_report":"manuscripts/hsdip2024-tr.pdf","year":"2024","abstract":"Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.","bibtex":"@inproceedings{Lauer2024LiftedhAdd,\n author = {Pascal Lauer and {\\'{A}}lvaro Torralba and Daniel H{\\\"{o}}ller and J{\\\"{o}}rg Hoffmann},\n booktitle = {Proceedings of the 16th Workshop on Heuristic Search for Domain-Independent Planning (HSDIP 2024)},\n note = {<i>This paper is the workshop version of Lauer et al. in ICAPS 2025. Please refer to the conference version instead.</i>},\n title = {A Lifted Backward Computation of hAdd},\n url_Paper = {https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf},\n Xurl_Slides = {talks/hsdip-2024.pdf},\n Xurl_Technical_Report = {manuscripts/hsdip2024-tr.pdf},\n year = {2024},\n abstract = {Recent interest in solving planning tasks where full grounding is infeasible has brought attention to how to compute heuristics to guide the search at a lifted level. h add is a well understood heuristic for classical planning. Methods to compute h add perform a forward fix-point computation, as this takes polynomial time with respect to the grounded representation. However, this computational efficiency does not carry over to lifted planning tasks, where it is EXPTIME-complete to compute hadd. In this paper, we introduce a novel approach for computing h add on lifted planning tasks. Our approach proceeds backwards, constructing a fully lifted regression graph whose nodes are assessed using conjunctive query evaluation. We provide a complexity analysis and show that our backward computation is complementary to the traditional forward computation. Our empirical evaluation confirms that there are significant differences in the performance of both methods in each domain. Overall, both methods are very complementary, and their combination advances the state-of-the-art in lifted h add computations.}\n}\n\n","author_short":["Lauer, P.","Torralba, Á.","Höller, D.","Hoffmann, J."],"key":"Lauer2024LiftedhAdd","id":"Lauer2024LiftedhAdd","bibbaseid":"lauer-torralba-hller-hoffmann-aliftedbackwardcomputationofhadd-2024","role":"author","urls":{" paper":"https://icaps24.icaps-conference.org/program/workshops/hsdip-papers/paper_9.pdf"},"metadata":{"authorlinks":{}},"downloads":1},"bibtype":"inproceedings","biburl":"https://bercher.net/bibtex/bibliography.bib","dataSources":["bPpsmYWjffAy6QHP5"],"keywords":[],"search_terms":["lifted","backward","computation","hadd","lauer","torralba","höller","hoffmann"],"title":"A Lifted Backward Computation of hAdd","year":2024,"downloads":3}