Author name cluster

Faustine Maffre

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

7 papers

2 author rows

AIJ Journal 2021 Journal Article

A lightweight epistemic logic and its application to planning

Martin C. Cooper
Andreas Herzig
Faustine Maffre
Frédéric Maris
Elise Perrotin
Pierre Régnier

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.

Details DOI

ECAI Conference 2016 Conference Paper

A Simple Account of Multi-Agent Epistemic Planning

Martin C. Cooper
Andreas Herzig
Faustine Maffre
Frederic Maris
Pierre Régnier

A realistic model of multi-agent planning must allow us to formalize notions which are absent in classical planning, such as communication and knowledge. We investigate multi-agent planning based on a simple logic of knowledge that is grounded on the visibility of propositional variables. Using such a formal logic allows us to prove the existence of a plan given the description of the individual actions. We present an encoding of multi-agent planning problems expressed in this logic into the standard planning language PDDL. The solvability of a planning task is reduced to a model checking problem in a dynamic extension of our logic, proving its complexity. Feeding the resulting problem into a PDDL planner provides a provably correct plan for the original multi-agent planning problem. We apply our method on several examples such as the gossip problem.

Details

KR Conference 2016 Conference Paper

Building epistemic logic from observationsand public announcements

Tristan Charrier
Andreas Herzig
Emiliano Lorini
Faustine Maffre
Francois Schwarzentruber

As to the ﬁrst problem, we adopt the solution of (Herzig, We study an epistemic logic where knowledge is built from what the agents observe (including higher-order visibility) and what the agents learn from public announcements. This ﬁxes two main drawbacks of previous observability-based approaches where who sees what is common knowledge and where the epistemic operators distribute over disjunction. The latter forbids the modeling of most of the classical epistemic problems, starting with the muddy children puzzle. We integrate a dynamic dimension where both facts of the world and the agents’ observability can be modiﬁed by assignment programs. We establish that the model checking problem is PS PACE-complete.

IJCAI Conference 2016 Conference Paper

Epistemic Boolean Games Based on a Logic of Visibility and Control

Andreas Herzig
Emiliano Lorini
Faustine Maffre
Francois Schwarzentruber

We analyse epistemic boolean games ina computationally grounded dynamic epistemic logic. The agents' knowledge is determined by what they see, including higher-order visibility: agents may observe whether another agent observes an atom or not. The agents' actions consist in modifying the truth values of atoms. We provide an axiomatisation of the logic, establish that the model checking problem is in PSPACE, and show how one can reason about equilibria in epistemic boolean games.

PDF Details

ECAI Conference 2016 Conference Paper

Simple Epistemic Planning: Generalised Gossiping

Martin C. Cooper
Andreas Herzig
Faustine Maffre
Frederic Maris
Pierre Régnier

The gossip problem, in which information (secrets) must be shared among a certain number of agents using the minimum number of calls, is of interest in the conception of communication networks and protocols. We extend the gossip problem to arbitrary epistemic depths. For example, we may require not only that all agents know all secrets but also that all agents know that all agents know all secrets. We give optimal protocols for the generalised gossip problem, in the case of two-way communications, one-way communications and parallel communication. In the presence of negative goals testing the existence of a successful protocol is NP-complete.

Details

LORI Conference 2015 Conference Paper

A Poor Man's Epistemic Logic Based on Propositional Assignment and Higher-Order Observation

Andreas Herzig
Emiliano Lorini
Faustine Maffre

Abstract We introduce a dynamic epistemic logic that is based on what an agent can observe, including joint observation and observation of what other agents observe. This generalizes van der Hoek, Wooldridge and colleague’s logics ECL-PC(PO) and LRC where it is common knowledge which propositional variables each agent observes. In our logic, facts of the world and their observability can both be modified by assignment programs. We show how epistemic operators can be interpreted in this framework and identify the conditions under which the principles of positive and negative introspection are valid. We also provide a sound and complete axiomatization and prove that the satisfiability problem is PSpace -complete. Finally, we show how public and private announcements can be expressed and illustrate the latter by the gossip spreading problem.

Details

EUMAS Conference 2015 Conference Paper

How to Share Knowledge by Gossiping

Andreas Herzig
Faustine Maffre

Abstract Given n agents each of which has a secret (a fact not known to anybody else), the classical version of the gossip problem is to achieve shared knowledge of all secrets in a minimal number of phone calls. There exist protocols achieving shared knowledge in \(2(n{-}2)\) calls: when the protocol terminates everybody knows all the secrets. We generalize that problem and focus on higher-order shared knowledge: how many calls does it take to obtain that everybody knows that everybody knows all secrets? More generally, how many calls does it take to obtain shared knowledge of order k? This requires not only the communication of secrets, but also the communication of knowledge about secrets. We give a protocol that works in \((k{+}1)(n{-}2)\) steps and prove that it is correct: it achieves shared knowledge of level k. The proof is presented in a dynamic epistemic logic that is based on the observability of propositional variables by agents.

Details DOI