Was Fixing This Really That Hard? On the Complexity of Correcting HTN Domains

Authors

  • Songtuan Lin The Australian National University
  • Pascal Bercher The Australian National University

DOI:

https://doi.org/10.1609/aaai.v37i10.26419

Keywords:

PRS: Deterministic Planning, HAI: Human-Computer Interaction, PRS: Other Foundations of Planning, Routing & Scheduling

Abstract

Automated modeling assistance is indispensable to the AI planning being deployed in practice, notably in industry and other non-academic contexts. Yet, little progress has been made that goes beyond smart interfaces like programming environments. They focus on autocompletion, but lack intelligent support for guiding the modeler. As a theoretical foundation of a first step towards this direction, we study the computational complexity of correcting a flawed Hierarchical Task Network (HTN) planning domain. Specifically, a modeler provides a (white) list of plans that are supposed to be solutions, and likewise a (black) list of plans that shall not be solutions. We investigate the complexity of finding a set of (optimal or suboptimal) model corrections so that those plans are (resp. not) solutions to the corrected model. More specifically, we factor out each hardness source that contributes towards NP-hardness, including one that we deem important for many other complexity investigations that go beyond our specific context of application. All complexities range between NP and Sigma-2-p, rising the hope for efficient practical tools in the future.

Downloads

Published

2023-06-26

How to Cite

Lin, S., & Bercher, P. (2023). Was Fixing This Really That Hard? On the Complexity of Correcting HTN Domains. Proceedings of the AAAI Conference on Artificial Intelligence, 37(10), 12032-12040. https://doi.org/10.1609/aaai.v37i10.26419

Issue

Section

AAAI Technical Track on Planning, Routing, and Scheduling