Skip to main navigation Skip to search Skip to main content

Delete- And ordering-relaxation heuristics for HTN planning

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

17 Citations (Scopus)

Abstract

In HTN planning, the hierarchy has a wide impact on solutions. First, there is (usually) no state-based goal given, the objective is given via the hierarchy. Second, it enforces actions to be in a plan. Third, planners are not allowed to add actions apart from those introduced via decomposition, i.e. via the hierarchy. However, no heuristic considers the interplay of hierarchy and actions in the plan exactly (without relaxation) because this makes heuristic calculation NP-hard even under delete relaxation. We introduce the problem class of delete- and ordering-free HTN planning as basis for novel HTN heuristics and show that its plan existence problem is still NP-complete. We then introduce heuristics based on the new class using an integer programming model to solve it.

Original languageEnglish
Title of host publicationProceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence
EditorsChristian Bessiere
PublisherInternational Joint Conferences on Artificial Intelligence
Pages4076-4083
Number of pages8
Volume29
ISBN (Electronic)978-0-9992411-6-5
DOIs
Publication statusPublished - 11 Jul 2020
Event29th International Joint Conference on Artificial Intelligence, IJCAI 2020 - Yokohama, Japan
Duration: 1 Jan 2021 → …

Publication series

NameIJCAI International Joint Conference on Artificial Intelligence
PublisherInternational Joint Conferences on Artificial Intelligence
Volume29
ISSN (Print)1045-0823

Conference

Conference29th International Joint Conference on Artificial Intelligence, IJCAI 2020
Country/TerritoryJapan
CityYokohama
Period1/01/21 → …

Fingerprint

Dive into the research topics of 'Delete- And ordering-relaxation heuristics for HTN planning'. Together they form a unique fingerprint.

Cite this