A general multi-agent epistemic planner based on higher-order belief change

In recent years, multi-agent epistemic planning has received attention from both dynamic logic and planning communities. Existing implementations of multi-agent epistemic planning are based on compilation into classical planning and suffer from various limitations, such as generating only linear pla...

Full description

Saved in:
Bibliographic Details
Published in:Artificial intelligence 2021-12, Vol.301, p.103562, Article 103562
Main Authors: Wan, Hai, Fang, Biqing, Liu, Yongmei
Format: Article
Language:English
Subjects:
Algorithms
Belief change
Canonical forms
Community planning
Epistemic planning
Epistemology
Knowledge bases (artificial intelligence)
Multi-agent epistemic logic
Multiagent systems
Planning
Reasoning
Revisions
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:In recent years, multi-agent epistemic planning has received attention from both dynamic logic and planning communities. Existing implementations of multi-agent epistemic planning are based on compilation into classical planning and suffer from various limitations, such as generating only linear plans, restriction to public actions, and incapability to handle disjunctive beliefs. In this paper, we consider centralized multi-agent epistemic planning from the viewpoint of a third person who coordinates all the agents to achieve the goal. We treat contingent planning, resulting in nonlinear plans. We model private actions and hence handle beliefs, formalized with the multi-agent KD45 logic. We handle static propositional common knowledge, which we call constraints. For such planning settings, we propose a general representation framework where the initial knowledge base (KB) and the goal, the preconditions and effects of actions can be arbitrary KD45n formulas, and the solution is an action tree branching on sensing results. In this framework, the progression of KBs w.r.t. actions is achieved through the operation of belief revision or update on KD45n formulas, that is, higher-order belief revision or update. To support efficient reasoning and progression, we make use of a normal form for KD45n called alternating cover disjunctive formulas (ACDFs). We propose reasoning, revision and update algorithms for ACDFs. Based on these algorithms, adapting the PrAO algorithm for contingent planning from the literature, we implemented a multi-agent epistemic planner called MEPK. Our experimental results show the viability of our approach.
ISSN:0004-3702
1872-7921
DOI:10.1016/j.artint.2021.103562