Delete- and Ordering-Relaxation Heuristics for HTN Planning

Delete- and Ordering-Relaxation Heuristics for HTN Planning. Höller, D., Bercher, P., & Behnke, G. In Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020), pages 4076–4083, 2020. IJCAI.

Paper doi abstract bibtex 3 downloads

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 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 linear programming model to solve it.

@InProceedings{Hoeller2020ILP,
  author    = {Daniel H\"oller and Pascal Bercher and Gregor Behnke},
  title     = {Delete- and Ordering-Relaxation Heuristics for HTN Planning},
  booktitle = {Proceedings of the 29th International Joint Conference on Artificial Intelligence (IJCAI 2020)},
  year      = {2020},
  publisher = {IJCAI},
  doi       = {10.24963/ijcai.2020/564},
  pages     = {4076--4083},
  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 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 linear programming model to solve it.},
  url_Paper = {https://bercher.net/publications/2020/Hoeller2020ILPHTNHeuristics.pdf},
  keywords  = {conference}
}

Downloads: 3