求解多智能体简单时序问题的弧相容方法

讲座内容：简单时序问题(simple temporal problem, STP) 是时序推理的一个重要模型，用STP我们可以描述事件之间的定量约束。自图灵奖得主 Judea Pearl等 1991年提出此模型以来，STP已经成为规划和调度问题的重要组成部分。近年来，我们越来越依赖智能手机来安排管理我们的日常任务。可以预见，以后更多的协调任务将由虚拟个人助理来完成。鉴于此，美国学者Boekoel 和 Durfee提出了多智能体 (multiagent) 时序推理问题，并将STP推广到多智能体框架下，此即为MaSTP问题。利用Planken等提出的部分路径相容 (patial path-consistency) 算法，他们提出了解决MaSTP的方法。这个方法虽然有效，但存在一个严重问题：在求解过程中，该方法需要将约束网络三角化。这需要在不同变元间引入原本不存在的约束。如果这些变元属于同一个智能体，这是可行的。但如果这些变元属于不同智能体，则会泄漏相关智能体的隐私。在我们这篇工作中，我们提出了基于弧相容 (arc-consistency) 的求解方法，完全避开了这一问题。同时，我们的理论和实验结果表明，这一新方法更有效。