论文标题

利用击球集进行模型对帐

On Exploiting Hitting Sets for Model Reconciliation

论文作者

Vasileiou, Stylianos Loukas, Previti, Alessandro, Yeoh, William

论文摘要

在人类意识计划中,计划代理可能需要向人类用户提供有关其计划为何最佳的解释。一种流行的方法称为模型对帐,在该模型和解中,代理试图调和其模型和人类模型的差异,因此该计划在人类模型中也是最佳的。在本文中,我们提出了一个基于逻辑的模型对帐框架,该框架超出了计划的范围。更具体地说,考虑到知识库$ kb_1 $需要公式$φ$和第二个知识库$ kb_2 $不需要它,模型和解以基数中的$ kb_1 $的形式寻求解释,其集成到$ kb_2 $中,这使您成为可能。我们的方法基于源于对不一致的分析的思想,利用了最小的校正集(MCS)和最小的不满意集(Muses)之间现有的命中二元性,以识别适当的解释。但是,与那些针对不一致的公式的作品不同,该公式假设单个知识库,MCSES和MUSE是在两个不同的知识库中计算的。我们以对新介绍的计划实例的方法进行经验评估来结束论文,在这里我们展示了它如何优于现有的最先进的求解器以及最近的SAT竞赛中的一般非计划实例,而其他求解器不存在。

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 $φ$ 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.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源