On the Computational Complexity of Model Reconciliations

Sarath Sreedharan; Pascal Bercher; Subbarao Kambhampati

IJCAI 2022poster10 citations

On the Computational Complexity of Model Reconciliations

Sarath Sreedharan, Pascal Bercher, Subbarao Kambhampati

Abstract

Model-reconciliation explanation is a popular framework for generating explanations for planning problems. While the framework has been extended to multiple settings since its introduction for classical planning problems, there is little agreement on the computational complexity of generating minimal model reconciliation explanations in the basic setting. In this paper, we address this lacuna by introducing a decision-version of the model-reconciliation explanation generation problem and we show that it is Sigma-2-P Complete.

Planning and Scheduling: Theoretical Foundations of PlanningAI Ethics, Trust, Fairness: Explainability and Interpretability

BibTeX

@inproceedings{ijcai2022p646,
  title     = {On the Computational Complexity of Model Reconciliations},
  author    = {Sreedharan, Sarath and Bercher, Pascal and Kambhampati, Subbarao},
  booktitle = {Proceedings of the Thirty-First International Joint Conference on
               Artificial Intelligence, {IJCAI-22}},
  publisher = {International Joint Conferences on Artificial Intelligence Organization},
  editor    = {Lud De Raedt},
  pages     = {4657--4664},
  year      = {2022},
  month     = {7},
  note      = {Main Track},
  doi       = {10.24963/ijcai.2022/646},
  url       = {https://doi.org/10.24963/ijcai.2022/646},
}