Complexity Results in Epistemic Planning

Thomas Bolander, Martin Holm Jensen, Francois Schwarzentruber

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

65 Downloads (Pure)

Abstract

Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.
Original languageEnglish
Title of host publicationProceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)
EditorsQiang Yang, Michael Wooldridge
PublisherAAAI Press
Publication date2015
Pages2791-2797
ISBN (Print)978-1-57735-738-4
Publication statusPublished - 2015
Event24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25 Jul 201531 Jul 2015
Conference number: 24
http://ijcai-15.org/

Conference

Conference24th International Joint Conference on Artificial Intelligence
Number24
CountryArgentina
CityBuenos Aires
Period25/07/201531/07/2015
Internet address

Cite this

Bolander, T., Jensen, M. H., & Schwarzentruber, F. (2015). Complexity Results in Epistemic Planning. In Q. Yang, & M. Wooldridge (Eds.), Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015) (pp. 2791-2797). AAAI Press.
Bolander, Thomas ; Jensen, Martin Holm ; Schwarzentruber, Francois . / Complexity Results in Epistemic Planning. Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). editor / Qiang Yang ; Michael Wooldridge. AAAI Press, 2015. pp. 2791-2797
@inproceedings{205b16262d474a94aabe20ab5fb8c356,
title = "Complexity Results in Epistemic Planning",
abstract = "Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.",
author = "Thomas Bolander and Jensen, {Martin Holm} and Francois Schwarzentruber",
year = "2015",
language = "English",
isbn = "978-1-57735-738-4",
pages = "2791--2797",
editor = "Yang, {Qiang } and Wooldridge, {Michael }",
booktitle = "Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)",
publisher = "AAAI Press",

}

Bolander, T, Jensen, MH & Schwarzentruber, F 2015, Complexity Results in Epistemic Planning. in Q Yang & M Wooldridge (eds), Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI Press, pp. 2791-2797, 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25/07/2015.

Complexity Results in Epistemic Planning. / Bolander, Thomas; Jensen, Martin Holm; Schwarzentruber, Francois .

Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). ed. / Qiang Yang; Michael Wooldridge. AAAI Press, 2015. p. 2791-2797.

Research output: Chapter in Book/Report/Conference proceedingArticle in proceedingsResearchpeer-review

TY - GEN

T1 - Complexity Results in Epistemic Planning

AU - Bolander, Thomas

AU - Jensen, Martin Holm

AU - Schwarzentruber, Francois

PY - 2015

Y1 - 2015

N2 - Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.

AB - Epistemic planning is a very expressive framework that extends automated planning by the incorporation of dynamic epistemic logic (DEL). We provide complexity results on the plan existence problem for multi-agent planning tasks, focusing on purely epistemic actions with propositional preconditions. We show that moving from epistemic preconditions to propositional preconditions makes it decidable, more precisely in EXPSPACE. The plan existence problem is PSPACE-complete when the underlying graphs are trees and NP-complete when they are chains (including singletons). We also show PSPACE-hardness of the plan verification problem, which strengthens previous results on the complexity of DEL model checking.

M3 - Article in proceedings

SN - 978-1-57735-738-4

SP - 2791

EP - 2797

BT - Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015)

A2 - Yang, Qiang

A2 - Wooldridge, Michael

PB - AAAI Press

ER -

Bolander T, Jensen MH, Schwarzentruber F. Complexity Results in Epistemic Planning. In Yang Q, Wooldridge M, editors, Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015). AAAI Press. 2015. p. 2791-2797