On Delete Relaxation in Partial-Order Causal-Link Planning

On Delete Relaxation in Partial-Order Causal-Link Planning. Bercher, P., Geier, T., Richter, F., & Biundo, S. In Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence (ICTAI 2013), pages 674–681, 2013. IEEE Computer Society.

Paper

Slides doi abstract bibtex 3 downloads

We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both of the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.

@InProceedings{Bercher2013POCL-DeleteRelaxation,
  Title      = {On Delete Relaxation in Partial-Order Causal-Link Planning},
  Author     = {Pascal Bercher and Thomas Geier and Felix Richter and Susanne Biundo},
  Booktitle  = {Proceedings of the 2013 IEEE 25th International Conference on Tools with Artificial Intelligence ({ICTAI} 2013)},
  Year       = {2013},
  Pages      = {674--681},
  doi        = {10.1109/ICTAI.2013.105},
  publisher  = {{IEEE} Computer Society},
  abstract   = {We prove a new complexity result for Partial-Order Causal-Link (POCL) planning, in which we study the hardness of refining a search node (i.e., a partial plan) to a valid solution given a delete effect-free domain model. While the corresponding decision problem is known to be polynomial in state-based search (where search nodes are states), it turns out to be intractable in the POCL setting. Since both of the currently best-informed heuristics for POCL planning are based on delete relaxation, we hope that our result sheds some new light on the problem of designing heuristics for POCL planning. Based on this result, we developed a new variant of one of these heuristics which incorporates more information of the current partial plan. We evaluate our heuristic on several domains of the early International Planning Competitions and compare it with other POCL heuristics from the literature.},
  url_Paper  = {https://bercher.net/publications/2013/Bercher2013POCL-DeleteRelaxation.pdf},
  url_Slides = {https://bercher.net/publications/2013/Bercher2013POCL-DeleteRelaxationSlides.pdf},
  keywords   = {conference}
}

Downloads: 3