More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks

More than a Name? On Implications of Preconditions and Effects of Compound HTN Planning Tasks. Bercher, P., Höller, D., Behnke, G., & Biundo, S. In Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), pages 225–233, 2016. IOS Press. Erratum: Theorem 2 incorrectly claims P-membership for checking whether a plan is a solution to a primitive hybrid problem. This is however NP-complete. We corrected this in Section 3.2 of our follow-up paper "Tight Bounds for Hybrid Planning" (IJCAI-ECAI 2022).

Paper

Slides doi abstract bibtex 7 downloads

There are several formalizations for hierarchical planning. Many of them allow to specify preconditions and effects for compound tasks. They can be used, e.g., to assist during the modeling process by ensuring that the decomposition methods' plans ``implement'' the compound tasks' intended meaning. This is done based on so-called legality criteria that relate these preconditions and effects to the method's plans and pose further restrictions. Despite the variety of expressive hierarchical planning formalisms, most theoretical investigations are only known for standard HTN planning, where compound tasks are just names, i.e., no preconditions or effects can be specified. Thus, up to know, a direct comparison to other hierarchical planning formalisms is hardly possible and fundamental theoretical properties are yet unknown. We therefore investigate the theoretical impact of such preconditions and effects – depending on the legality criteria known from the literature – for two of the most basic questions to planning: plan existence and plan verification. It turns out that for all investigated legality criteria, the respective problems are as hard as in the HTN setting and therefore equally expressive.

@InProceedings{Bercher2016HybridPlanningComplexities,
  Title      = {More than a Name? On Implications of Preconditions and Effects of Compound {HTN} Planning Tasks},
  Author     = {Pascal Bercher and Daniel H{\"o}ller and Gregor Behnke and Susanne Biundo},
  Booktitle  = {Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016)},
  Year       = {2016},
  Pages      = {225--233},
  Publisher  = {IOS Press},
  doi        = {10.3233/978-1-61499-672-9-225},
  abstract   = {There are several formalizations for hierarchical planning. Many of them allow to specify preconditions and effects for compound tasks. They can be used, e.g., to assist during the modeling process by ensuring that the decomposition methods' plans ``implement'' the compound tasks' intended meaning. This is done based on so-called legality criteria that relate these preconditions and effects to the method's plans and pose further restrictions. Despite the variety of expressive hierarchical planning formalisms, most theoretical investigations are only known for standard HTN planning, where compound tasks are just names, i.e., no preconditions or effects can be specified. Thus, up to know, a direct comparison to other hierarchical planning formalisms is hardly possible and fundamental theoretical properties are yet unknown. We therefore investigate the theoretical impact of such preconditions and effects -- depending on the legality criteria known from the literature -- for two of the most basic questions to planning: plan existence and plan verification. It turns out that for all investigated legality criteria, the respective problems are as hard as in the HTN setting and therefore equally expressive.},
  note      = {<strong>Erratum:</strong> Theorem 2 incorrectly claims P-membership for checking whether a plan is a solution to a primitive hybrid problem. This is however NP-complete. We corrected this in Section 3.2 of our follow-up paper "Tight Bounds for Hybrid Planning" (IJCAI-ECAI 2022).},
  url_Paper  = {https://bercher.net/publications/2016/Bercher2016HybridPlanningComplexities.pdf},
  url_Slides = {https://bercher.net/publications/2016/Bercher2016HybridPlanningComplexitiesSlides.pdf},
  keywords   = {conference}
}

Downloads: 7