Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models
Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models
Songtuan Lin, Pascal Bercher
Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence
Main Track. Pages 4152-4159.
https://doi.org/10.24963/ijcai.2021/571
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.
Keywords:
Planning and Scheduling: Hierarchical Planning
Planning and Scheduling: Model-Based Reasoning
Planning and Scheduling: Theoretical Foundations of Planning