講座內容：簡單時序問題(simple temporal problem, STP) 是時序推理的一個重要模型，用STP我們可以描述事件之間的定量約束。自圖靈獎得主 Judea Pearl等 1991年提出此模型以來，STP已經成為規劃和調度問題的重要組成部分。近年來，我們越來越依賴智能手機來安排管理我們的日常任務。可以預見，以后更多的協調任務將由虛擬個人助理來完成。鑒于此，美國學者Boekoel 和 Durfee提出了多智能體 (multiagent) 時序推理問題，并將STP推廣到多智能體框架下，此即為MaSTP問題。利用Planken等提出的部分路徑相容 (patial path-consistency) 算法，他們提出了解決MaSTP的方法。這個方法雖然有效，但存在一個嚴重問題：在求解過程中，該方法需要將約束網絡三角化。這需要在不同變元間引入原本不存在的約束。如果這些變元屬于同一個智能體，這是可行的。但如果這些變元屬于不同智能體，則會泄漏相關智能體的隱私。在我們這篇工作中，我們提出了基于弧相容 (arc-consistency) 的求解方法，完全避開了這一問題。同時，我們的理論和實驗結果表明，這一新方法更有效。