---
title: "Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models"
authors:
  - "Songtuan Lin"
  - "Pascal Bercher"
doi: "10.24963/ijcai.2021/571"
url: "https://ijcai.org/proceedings/2021/571"
pdf: "https://ijcai.org/proceedings/2021/0571.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4152-4159"
track: "Main Track"
keywords:
  - "Planning and Scheduling: Theoretical Foundations of Planning"
  - "Planning and Scheduling: Model-Based Reasoning"
  - "Planning and Scheduling: Hierarchical Planning"
---

# 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*, pages 4152-4159. DOI: [10.24963/ijcai.2021/571](https://doi.org/10.24963/ijcai.2021/571)

## 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.