Raisonnement sur les actions : de Toronto à AmsterdamReport as inadecuate




Raisonnement sur les actions : de Toronto à Amsterdam - Download this document for free, or read online. Document in PDF available to download.

1 Computer Science 2 IRIT - Institut de recherche en informatique de Toulouse

Résumé : Nous montrons comment en raisonnement sur les actions la fameuse solution de Reiter du problème du décor peut être modélisée en logique épistémique dynamique, et nous proposons une méthode de régression optimale. Notre méthode étend la solution de Reiter en intégrant des actions d-observation et des opérateurs modaux de connaissance, et traduit le formalisme de Reiter le Calcul des situations dans une logique des actions et des connaissances comprenant des opérateurs d-annonce et d-affectation. En étendant la méthode de réduction de Lutz de la logique des annonces publiques aux affectation, nous établissons des résultats de complexité pour la régression. Nous montrons que ces résultats sont optimaux : le problème de décider la satisfiabilité d-une formule est NP-complet pour un agent, PSPACE-complet pour plusieurs agents et EXPTIME-complet dans la présence de l-opérateur de connaissance commune. We show how in the propositional case Reiter-s well-known solution to the frame problem can be modelled in dynamic epistemic logic, and provide an optimal regression algorithm. Our method is as follows : we extend Reiter-s solution by integrating observation actions and modal operators of knowledge, and encode the resulting formalism in a dynamic epistemic logic with announcement and assignment operators. By extending Lutz- recent satisfiability-preserving reduction for public announcement logic to assignments, we establish optimal complexity results for regression : satisfiability is NP-complete for one agent, PSPACE-complete for multiple agents and EXPTIME-complete when common knowledge is involved.

Mots-clés : raisonnement sur les actions et changement logiques épistémique dynamique systèmes multi-agents régression reasoning about actions and change





Author: Hans Van Dimarsch - Andreas Herzig - Tiago De Lima -

Source: https://hal.archives-ouvertes.fr/



DOWNLOAD PDF




Related documents