A Lightweight Epistemic Logic and its Application to Planning

Autor: Pierre Régnier, Faustine Maffre, Frédéric Maris, Andreas Herzig, Elise Perrotin, Martin C. Cooper
Přispěvatelé: Artificial and Natural Intelligence Toulouse Institute (ANITI), Argumentation, Décision, Raisonnement, Incertitude et Apprentissage (IRIT-ADRIA), Institut de recherche en informatique de Toulouse (IRIT), Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées-Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse - Jean Jaurès (UT2J)-Université Toulouse III - Paul Sabatier (UT3), Université Fédérale Toulouse Midi-Pyrénées-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université Fédérale Toulouse Midi-Pyrénées-Université Toulouse 1 Capitole (UT1), Université Fédérale Toulouse Midi-Pyrénées, Université Toulouse III - Paul Sabatier (UT3), Logique, Interaction, Langue et Calcul (IRIT-LILaC), Centre National de la Recherche Scientifique (CNRS), ANR-19-P3IA-0004,ANITI,Artificial and Natural Intelligence Toulouse Institute(2019), European Project: 952215,TAILOR(2020), Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Centre National de la Recherche Scientifique (CNRS)-Institut National Polytechnique (Toulouse) (Toulouse INP), Université de Toulouse (UT)-Toulouse Mind & Brain Institut (TMBI), Université Toulouse - Jean Jaurès (UT2J), Université de Toulouse (UT)-Université de Toulouse (UT)-Université Toulouse III - Paul Sabatier (UT3), Université de Toulouse (UT)-Université Toulouse Capitole (UT Capitole), Université de Toulouse (UT)
Jazyk: angličtina
Rok vydání: 2020
Předmět:
Epistemic planning
Linguistics and Language
Common knowledge (logic)
Theoretical computer science
Computer science
02 engineering and technology
[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]
Language and Linguistics
[INFO.INFO-AI]Computer Science [cs]/Artificial Intelligence [cs.AI]
Negation
Epistemic modal logic
Artificial Intelligence
Simple (abstract algebra)
020204 information systems
0202 electrical engineering
electronic engineering
information engineering
Observability
PSPACE
[INFO.INFO-SC]Computer Science [cs]/Symbolic Computation [cs.SC]
Propositional variable
Multiagent planning
Gossip problem
Satisfiability
[MATH.MATH-LO]Mathematics [math]/Logic [math.LO]
TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES
020201 artificial intelligence & image processing
Epistemic logic
Zdroj: Mémoires en Sciences de l'Information et de la Communication
Hyper Article en Ligne
Hal-Diderot
ORCID
Microsoft Academic Graph
HAL Descartes
Artificial Intelligence, Elsevier, 2020, 298, pp.103437. ⟨10.1016/j.artint.2020.103437⟩
Artificial Intelligence
Artificial Intelligence, 2021, Special issue: SI: Ethics for Autonomous Systems, 298, pp.103437. ⟨10.1016/j.artint.2020.103437⟩
ISSN: 0004-3702
Popis: Edited by Michael Fisher, Sven Koenig and Marija Slavkovik.; International audience; We study multiagent epistemic planning with a simple epistemic logic whose language is a restriction of that of standard epistemic logic. Its formulas are boolean combinations of observability atoms: sequences of ‘knowing whether’ operators followed by propositional variables. This compares favourably with other restricted languages where formulas are boolean combinations of epistemic literals: sequences of ‘knowing that’ epistemic operators and negations followed by propositional variables; or in other terms: epistemic formulas without conjunctions or disjunctions. The reason is that our language enables a richer theory of mind: we can express statements such as “I don’t know whether p, but I know that you know whether p” which are important in communication and more generally in interaction and which cannot be expressed with epistemic literals. Going beyond previous work, we also introduce a ‘common knowledge whether’ operator. We show that satisfiability is nevertheless NP-complete. We then define simple epistemic planning tasks as generalisations of classical planning tasks: action descriptions have sets of observability atoms as add- and delete-lists, initial states are sets of observability atoms, and goals are boolean combinations of observability atoms. We show that simple epistemic planning tasks can be polynomially translated into classical planning tasks. It follows that checking solvability of simple epistemic planning tasks is PSpace-complete. We present some application examples such as the gossip problem and some experimental results and clarify the relationship with Dynamic Epistemic Logic-based planning.
Databáze: OpenAIRE
Externí odkaz: