On Exploiting Hitting Sets for Model Reconciliation

• URL: http://arxiv.org/abs/2012.09274v3
• Date: Wed, 27 Sep 2023 17:59:03 GMT
• Title: On Exploiting Hitting Sets for Model Reconciliation
• Authors: Stylianos Loukas Vasileiou, Alessandro Previti, William Yeoh
• Abstract summary: 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. We present a logic-based framework for model reconciliation that extends beyond the realm of planning.
• Score: 53.81101846598925
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 $KB_1$ entailing a formula $\varphi$ and a second knowledge base $KB_2$ not entailing it, model reconciliation seeks an explanation, in the form of a cardinality-minimal subset of $KB_1$, whose integration into $KB_2$ 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.

Related papers

• Metareasoning in uncertain environments: a meta-BAMDP framework [1.0923877073891441]
  This paper proposes a meta Bayes-Adaptive MDP framework to handle metareasoning in environments with unknown reward/transition distributions. As a first step, we apply the framework to two-armed Bernoulli bandit (TABB) tasks, which have often been used to study human decision making.
  arXiv  Detail & Related papers  (2024-08-02T13:15:01Z)
• MAP: Low-compute Model Merging with Amortized Pareto Fronts via Quadratic Approximation [80.47072100963017]
  We introduce a novel and low-compute algorithm, Model Merging with Amortized Pareto Front (MAP) MAP efficiently identifies a set of scaling coefficients for merging multiple models, reflecting the trade-offs involved. We also introduce Bayesian MAP for scenarios with a relatively low number of tasks and Nested MAP for situations with a high number of tasks, further reducing the computational cost of evaluation.
  arXiv  Detail & Related papers  (2024-06-11T17:55:25Z)
• Accelerating Ensemble Error Bar Prediction with Single Models Fits [0.5249805590164902]
  An ensemble of N models is approximately N times more computationally demanding compared to a single model when it is used for inference. In this work, we explore fitting a single model to predicted ensemble error bar data, which allows us to estimate uncertainties without the need for a full ensemble.
  arXiv  Detail & Related papers  (2024-04-15T16:10:27Z)
• COPlanner: Plan to Roll Out Conservatively but to Explore Optimistically for Model-Based RL [50.385005413810084]
  Dyna-style model-based reinforcement learning contains two phases: model rollouts to generate sample for policy learning and real environment exploration. $textttCOPlanner$ is a planning-driven framework for model-based methods to address the inaccurately learned dynamics model problem.
  arXiv  Detail & Related papers  (2023-10-11T06:10:07Z)
• Action-State Dependent Dynamic Model Selection [6.5268245109828005]
  A Reinforcement learning algorithm is used to approximate and estimate from the data the optimal solution to a dynamic programming problem. A typical example is the one of switching between different portfolio models under rebalancing costs. Using a set of macroeconomic variables and price data, an empirical application shows superior performance to choosing the best portfolio model with hindsight.
  arXiv  Detail & Related papers  (2023-07-07T09:23:14Z)
• Lifted Model Checking for Relational MDPs [12.574454799055026]
  pCTL-REBEL is a lifted model checking approach for verifying pCTL properties on relational MDPs. We show that the pCTL model checking approach is decidable for relational MDPs even for possibly infinite domains.
  arXiv  Detail & Related papers  (2021-06-22T13:12:36Z)
• Forethought and Hindsight in Credit Assignment [62.05690959741223]
  We work to understand the gains and peculiarities of planning employed as forethought via forward models or as hindsight operating with backward models. We investigate the best use of models in planning, primarily focusing on the selection of states in which predictions should be (re)-evaluated.
  arXiv  Detail & Related papers  (2020-10-26T16:00:47Z)
• Control as Hybrid Inference [62.997667081978825]
  We present an implementation of CHI which naturally mediates the balance between iterative and amortised inference. We verify the scalability of our algorithm on a continuous control benchmark, demonstrating that it outperforms strong model-free and model-based baselines.
  arXiv  Detail & Related papers  (2020-07-11T19:44:09Z)
• A Simple Approach to Case-Based Reasoning in Knowledge Bases [56.661396189466664]
  We present a surprisingly simple yet accurate approach to reasoning in knowledge graphs (KGs) that requires emphno training, and is reminiscent of case-based reasoning in classical artificial intelligence (AI) Consider the task of finding a target entity given a source entity and a binary relation. Our non-parametric approach derives crisp logical rules for each query by finding multiple textitgraph path patterns that connect similar source entities through the given relation.
  arXiv  Detail & Related papers  (2020-06-25T06:28:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.