Undecidability in Epistemic Planning

Guillaume Aucher 1 Thomas Bolander 2
1 S4 - System synthesis and supervision, scenarios
IRISA - Institut de Recherche en Informatique et Systèmes Aléatoires, Inria Rennes – Bretagne Atlantique
Abstract : Dynamic epistemic logic (DEL) provides a very expressive framework for multi-agent planning that can deal with nondeterminism, partial observability, sensing actions, and arbitrary nesting of beliefs about other agents' beliefs. However, as we show in this paper, this expressiveness comes at a price. The planning framework is undecidable, even if we allow only purely epistemic actions (actions that change only beliefs, not ontic facts). Undecidability holds already in the S5 setting with at least 2 agents, and even with 1 agent in S4. It shows that multi-agent planning is robustly undecidable if we assume that agents can reason with an arbitrary nesting of beliefs about beliefs. We also prove a corollary showing undecidability of the DEL model checking problem with the star operator on actions (iteration).
Type de document :
Communication dans un congrès
IJCAI - International Joint Conference in Artificial Intelligence - 2013, Aug 2013, Beijing, China. 2013
Liste complète des métadonnées

Littérature citée [22 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00856469
Contributeur : Guillaume Aucher <>
Soumis le : dimanche 1 septembre 2013 - 01:30:00
Dernière modification le : mercredi 16 mai 2018 - 11:23:05
Document(s) archivé(s) le : jeudi 6 avril 2017 - 11:23:34

Fichier

IJCAI2013a.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-00856469, version 1

Citation

Guillaume Aucher, Thomas Bolander. Undecidability in Epistemic Planning. IJCAI - International Joint Conference in Artificial Intelligence - 2013, Aug 2013, Beijing, China. 2013. 〈hal-00856469〉

Partager

Métriques

Consultations de la notice

324

Téléchargements de fichiers

149