Undecidability in Epistemic Planning - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Rapport (Rapport De Recherche) Année : 2013

Undecidability in Epistemic Planning

Résumé

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).
Fichier principal
Vignette du fichier
RR-8310.pdf (706.65 Ko) Télécharger le fichier
Origine : Fichiers produits par l'(les) auteur(s)
Loading...

Dates et versions

hal-00824653 , version 1 (22-05-2013)

Identifiants

  • HAL Id : hal-00824653 , version 1

Citer

Guillaume Aucher, Thomas Bolander. Undecidability in Epistemic Planning. [Research Report] RR-8310, INRIA. 2013. ⟨hal-00824653⟩
460 Consultations
456 Téléchargements

Partager

Gmail Facebook X LinkedIn More