Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models

Lin, Songtuan; Bercher, Pascal

doi:10.24963/ijcai.2021/571

Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models

Songtuan Lin, Pascal Bercher

Download BibTeX Cite

Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. Main Track. Pages 4152-4159.

https://doi.org/10.24963/ijcai.2021/571

Keywords

Planning and Scheduling: Theoretical Foundations of Planning
Planning and Scheduling: Model-Based Reasoning
Planning and Scheduling: Hierarchical Planning

Abstract

Incorporating humans into AI planning is an important feature of flexible planning technology. Such human integration allows to incorporate previously unknown constraints, and is also an integral part of automated modeling assistance. As a foundation for integrating user requests, we study the computational complexity of determining the existence of changes to an existing model, such that the resulting model allows for specific user-provided solutions. We are provided with a planning problem modeled either in the classical (non-hierarchical) or hierarchical task network (HTN) planning formalism, as well as with a supposed-to-be solution plan, which is actually not a solution for the current model. Considering changing decomposition methods as well as preconditions and effects of actions, we show that most change requests are NP-complete though some turn out to be tractable.

Songtuan Lin, and Pascal Bercher. 2021. Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21. IJCAI, 4152–4159. https://doi.org/10.24963/ijcai.2021/571

@inproceedings{ijcai2021p571,
  title     = {Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models},
  author    = {Lin, Songtuan and Bercher, Pascal},
  booktitle = {Proceedings of the Thirtieth International Joint Conference on
               Artificial Intelligence, {IJCAI-21}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Prof. Zhi-Hua Zhou},
  pages     = {4152--4159},
  year      = {2021},
  month     = {8},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2021/571},
  url       = {https://doi.org/10.24963/ijcai.2021/571},
}

TY  - CPAPER
TI  - Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models
AU  - Lin, Songtuan
AU  - Bercher, Pascal
T2  - Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence, IJCAI-21
PB  - International Joint Conferences on Artificial Intelligence Organization
PY  - 2021
SP  - 4152
EP  - 4159
DO  - 10.24963/ijcai.2021/571
UR  - https://doi.org/10.24963/ijcai.2021/571
ER  -