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 language | English |
|---|---|
| Title of host publication | Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI 2015) |
| Editors | Qiang Yang, Michael Wooldridge |
| Publisher | AAAI Press |
| Publication date | 2015 |
| Pages | 2791-2797 |
| ISBN (Print) | 978-1-57735-738-4 |
| Publication status | Published - 2015 |
| Event | 24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015 Conference number: 24 http://ijcai-15.org/ |
Conference
| Conference | 24th International Joint Conference on Artificial Intelligence |
|---|---|
| Number | 24 |
| Country/Territory | Argentina |
| City | Buenos Aires |
| Period | 25/07/2015 → 31/07/2015 |
| Internet address |