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

Songtuan Lin; Pascal Bercher

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

18 Citations (Scopus)

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.

Original language	English
Title of host publication	Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)
Editors	Zhi-Hua Zhou
Publisher	International Joint Conferences on Artificial Intelligence
Pages	4152-4159
Number of pages	8
ISBN (Electronic)	978-0-9992411-9-6
ISBN (Print)	978-1-7138-3632-2
DOIs	https://doi.org/10.24963/ijcai.2021/571
Publication status	Published - 2021
Event	30th International Joint Conference on Artificial Intelligence, IJCAI 2021: Montreal-themed Virtual Reality - Virtual, Online, Canada Duration: 19 Aug 2021 → 27 Aug 2021 Conference number: 30th https://ijcai-21.org/ https://www.ijcai.org/proceedings/2021/

Publication series

Name	IJCAI International Joint Conference on Artificial Intelligence
ISSN (Print)	1045-0823

Conference

Conference	30th International Joint Conference on Artificial Intelligence, IJCAI 2021
Abbreviated title	IJCAI-21
Country/Territory	Canada
City	Virtual, Online
Period	19/08/21 → 27/08/21
Other	The 30th International Joint Conference on Artificial Intelligence (IJCAI-21)! IJCAI-21 will held in Montreal-themed virtual reality from August 19th to August 27th, 2021 due to the Covid-19 pandemic.
Internet address	https://ijcai-21.org/ https://www.ijcai.org/proceedings/2021/

Access to Document

10.24963/ijcai.2021/571Licence: Unspecified

Cite this

Lin, S., & Bercher, P. (2021). Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. In Z.-H. Zhou (Ed.), Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021) (pp. 4152-4159). (IJCAI International Joint Conference on Artificial Intelligence). International Joint Conferences on Artificial Intelligence. https://doi.org/10.24963/ijcai.2021/571

Lin, Songtuan ; Bercher, Pascal. / Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). editor / Zhi-Hua Zhou. International Joint Conferences on Artificial Intelligence, 2021. pp. 4152-4159 (IJCAI International Joint Conference on Artificial Intelligence).

@inproceedings{7e13bf9373e44abeb09f126d92e2a350,

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

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.",

author = "Songtuan Lin and Pascal Bercher",

note = "Publisher Copyright: {\textcopyright} 2021 International Joint Conferences on Artificial Intelligence. All rights reserved.; 30th International Joint Conference on Artificial Intelligence, IJCAI 2021 : Montreal-themed Virtual Reality, IJCAI-21 ; Conference date: 19-08-2021 Through 27-08-2021",

year = "2021",

doi = "10.24963/ijcai.2021/571",

language = "English",

isbn = "978-1-7138-3632-2",

series = "IJCAI International Joint Conference on Artificial Intelligence",

publisher = "International Joint Conferences on Artificial Intelligence",

pages = "4152--4159",

editor = "Zhi-Hua Zhou",

booktitle = "Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)",

url = "https://ijcai-21.org/, https://www.ijcai.org/proceedings/2021/",

}

Lin, S & Bercher, P 2021, Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. in Z-H Zhou (ed.), Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). IJCAI International Joint Conference on Artificial Intelligence, International Joint Conferences on Artificial Intelligence, pp. 4152-4159, 30th International Joint Conference on Artificial Intelligence, IJCAI 2021, Virtual, Online, Canada, 19/08/21. https://doi.org/10.24963/ijcai.2021/571

Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. / Lin, Songtuan; Bercher, Pascal.
Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). ed. / Zhi-Hua Zhou. International Joint Conferences on Artificial Intelligence, 2021. p. 4152-4159 (IJCAI International Joint Conference on Artificial Intelligence).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

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

AU - Lin, Songtuan

AU - Bercher, Pascal

N1 - Conference code: 30th

PY - 2021

Y1 - 2021

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

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

UR - http://www.scopus.com/inward/record.url?scp=85123909661&partnerID=8YFLogxK

U2 - 10.24963/ijcai.2021/571

DO - 10.24963/ijcai.2021/571

M3 - Conference contribution

SN - 978-1-7138-3632-2

T3 - IJCAI International Joint Conference on Artificial Intelligence

SP - 4152

EP - 4159

BT - Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021)

A2 - Zhou, Zhi-Hua

PB - International Joint Conferences on Artificial Intelligence

T2 - 30th International Joint Conference on Artificial Intelligence, IJCAI 2021

Y2 - 19 August 2021 through 27 August 2021

ER -

Lin S, Bercher P. Change the World - How Hard Can that Be? On the Computational Complexity of Fixing Planning Models. In Zhou ZH, editor, Proceedings of the 30th International Joint Conference on Artificial Intelligence (IJCAI 2021). International Joint Conferences on Artificial Intelligence. 2021. p. 4152-4159. (IJCAI International Joint Conference on Artificial Intelligence). doi: 10.24963/ijcai.2021/571

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

Abstract

Publication series

Conference

Access to Document

Other files and links

Fingerprint

Cite this