DEL-based epistemic planning: Decidability and complexity

Thomas Bolander; Tristan Charrier; Sophie Pinchinat; François Schwarzentruber

doi:10.1016/j.artint.2020.103304

DEL-based epistemic planning: Decidability and complexity

Thomas Bolander^*, Tristan Charrier, Sophie Pinchinat, François Schwarzentruber

^*Corresponding author for this work

Department of Applied Mathematics and Computer Science

Université de Rennes 1

Research output: Contribution to journal › Journal article › Research › peer-review

31 Downloads (Pure)

Abstract

Epistemic planning can be used for decision making in multi-agent systems with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we present a systematic overview of known complexity and decidability results for epistemic planning based on DEL, as well as provide some new results and improved proofs of existing results based on reductions between the problems.

Original language	English
Article number	103304
Journal	Artificial Intelligence
Volume	287
Number of pages	34
ISSN	0004-3702
DOIs	https://doi.org/10.1016/j.artint.2020.103304
Publication status	Published - Oct 2020

Keywords

Automata theory
Automated planning
Complexity theory
Decision problems
Dynamic epistemic logic
Epistemic planning

Access to Document

10.1016/j.artint.2020.103304

FulltextAccepted author manuscript, 1.3 MBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{99e051691e844099bb9d578c1f1a3480,

title = "DEL-based epistemic planning: Decidability and complexity",

abstract = "Epistemic planning can be used for decision making in multi-agent systems with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we present a systematic overview of known complexity and decidability results for epistemic planning based on DEL, as well as provide some new results and improved proofs of existing results based on reductions between the problems.",

keywords = "Automata theory, Automated planning, Complexity theory, Decision problems, Dynamic epistemic logic, Epistemic planning",

author = "Thomas Bolander and Tristan Charrier and Sophie Pinchinat and Fran{\c c}ois Schwarzentruber",

year = "2020",

month = oct,

doi = "10.1016/j.artint.2020.103304",

language = "English",

volume = "287",

journal = "Artificial Intelligence",

issn = "0004-3702",

publisher = "Elsevier",

}

TY - JOUR

T1 - DEL-based epistemic planning

T2 - Decidability and complexity

AU - Bolander, Thomas

AU - Charrier, Tristan

AU - Pinchinat, Sophie

AU - Schwarzentruber, François

PY - 2020/10

Y1 - 2020/10

N2 - Epistemic planning can be used for decision making in multi-agent systems with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we present a systematic overview of known complexity and decidability results for epistemic planning based on DEL, as well as provide some new results and improved proofs of existing results based on reductions between the problems.

AB - Epistemic planning can be used for decision making in multi-agent systems with distributed knowledge and capabilities. Dynamic Epistemic Logic (DEL) has been shown to provide a very natural and expressive framework for epistemic planning. In this paper, we present a systematic overview of known complexity and decidability results for epistemic planning based on DEL, as well as provide some new results and improved proofs of existing results based on reductions between the problems.

KW - Automata theory

KW - Automated planning

KW - Complexity theory

KW - Decision problems

KW - Dynamic epistemic logic

KW - Epistemic planning

U2 - 10.1016/j.artint.2020.103304

DO - 10.1016/j.artint.2020.103304

M3 - Journal article

AN - SCOPUS:85087590086

SN - 0004-3702

VL - 287

JO - Artificial Intelligence

JF - Artificial Intelligence

M1 - 103304

ER -

DEL-based epistemic planning: Decidability and complexity

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this