# On Exploiting Hitting Sets for Model Reconciliation

arXiv: https://arxiv.org/abs/2012.09274 · HTML: https://mlsanity.com/paper/2012.09274/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Dec 2020.

## Built on by (most cited first, 11 of 11)

- [Semantic-Based Explainable AI: Leveraging Semantic Scene Graphs and Pairwise Ranking to Explain Robot Failures](https://mlsanity.com/paper/2108.03554/) (2021)
- [Dialectical Reconciliation via Structured Argumentative Dialogues](https://mlsanity.com/paper/2306.14694/) (2023)
- [A Domain-Independent Agent Architecture for Adaptive Operation in Evolving Open Worlds](https://mlsanity.com/paper/2306.06272/) (2023)
- [Does Your AI Agent Get You? A Personalizable Framework for Approximating Human Models from Argumentation-based Dialogue Traces](https://mlsanity.com/paper/2502.16376/) (2025)
- [On Model Reconciliation: How to Reconcile When Robot Does not Know Human's Model?](https://mlsanity.com/paper/2208.03091/) (2022)
- [On Generating Monolithic and Model Reconciling Explanations in Probabilistic Scenarios](https://mlsanity.com/paper/2405.19229/) (2024)
- [Human-Modeling in Sequential Decision-Making: An Analysis through the Lens of Human-Aware AI](https://mlsanity.com/paper/2405.07773/) (2024)
- [Approximating Human Models During Argumentation-based Dialogues](https://mlsanity.com/paper/2405.18650/) (2024)
- [Human-Aware Belief Revision: A Cognitively Inspired Framework for Explanation-Guided Revision of Human Models](https://mlsanity.com/paper/2405.19238/) (2024)
- [TRACE-CS: A Hybrid Logic-LLM System for Explainable Course Scheduling](https://mlsanity.com/paper/2409.03671/) (2024)
- [The Sets of Power](https://mlsanity.com/paper/2410.07867/) (2024)

## Abstract (arXiv)

In human-aware planning, a planning agent may need to provide an explanation to a human user on why its plan is optimal. A popular approach to do this is called model reconciliation, where the agent tries to reconcile the differences in its model and the human's model such that the plan is also optimal in the human's model. In this paper, we present a logic-based framework for model reconciliation that extends beyond the realm of planning. More specifically, given a knowledge base KB1 entailing a formula varphi and a second knowledge base KB2 not entailing it, model reconciliation seeks an explanation, in the form of a cardinality-minimal subset of KB1, whose integration into KB2 makes the entailment possible. Our approach, based on ideas originating in the context of analysis of inconsistencies, exploits the existing hitting set duality between minimal correction sets (MCSes) and minimal unsatisfiable sets (MUSes) in order to identify an appropriate explanation. However, differently from those works targeting inconsistent formulas, which assume a single knowledge base, MCSes and MUSes are computed over two distinct knowledge bases. We conclude our paper with an empirical evaluation of the newly introduced approach on planning instances, where we show how it outperforms an existing state-of-the-art solver, and generic non-planning instances from recent SAT competitions, for which no other solver exists.