To Be Announced! Synthesis of Epistemic Protocols

17 - 21 August 2015

Venue: Lorentz Center@Oort

If you are invited or already registered for this workshop, you have received login details by email.

'To be announced!': an announcement is a communicative action, publicly observable. Seeing that a light is on is an observation, or sensing action, also known as an epistemic action. Turning the light switch is a physical action, also known as an ontic action. In planning, various aspects can be called epistemic: the condition for executing an action may be knowledge or ignorance of agents, the actions themselves may have an epistemic aspect (they are executed by an agent, or announced, or the communicated information may be about knowledge or ignorance) and they may only be partially observable (so that the agent does not know which action has really been executed), and the goals of plans may be epistemic (the spy may not learn the secret). Plans with epistemic features are also, because of the epistemic aspect, called protocols. This workshop is on synthesis of epistemic protocols in the widest sense of the word.

What is an epistemic protocol? Given my current state of knowledge, and a desirable state of knowledge, how do I get from one to the other? It is possible in principle to reach the desirable state of knowledge, i.e., does it make sense at all to start trying to obtain the desirable state? If I know it is impossible to obtain, there is no use trying. But even if I know that it is possible in principle, is there a way to approach the desirable state in steps or phases, i.e., can I iteratively construct an epistemic protocol to achieve the desirable state? And can this be done

with some or with full assurance that I am getting closer to the goal? Such problems become more complex if they involve more agents. The knowledge states of agents may be in terms of knowledge properties of other agents (I do not know if you know that I broke the teapot, so it makes sense for me to plan to replace it before you find out, in case you were not to know it). Such assumed knowledge properties may be incorrect (in fact you heard the teapot crash while in the next room), or the agents may act at unpredictable or unknown moments, or by way of possibly delayed or faulty communication channels, as typically in asynchronous systems.

The focus of much research in dynamic epistemic logic, and more generally in epistemic and temporal modal logics, is analysis: given a well-specified input epistemic state, and some well-specified dynamic process, compute the output epistemic state. Synthesis has received less attention: given a well-specified input epistemic state, and desirable output (typically less well specified), find the process transforming the input into the output.The process found is the epistemic protocol.

Synthesis of epistemic protocols is related to planning in artificial intelligence. In artificial intelligence, the focus of planning is on heuristics. In AI terms, synthesis of protocols is epistemic planning, and a suitable logical setting is that of modal logic with PDL and epistemic operators. Useful standard notions in their AI setting are the notions of progression and regression of information state specifications (a.k.a. progression/regression of beliefs, or belief states). If you execute an action in an information state satisfying a given initial specification (formula),

then the formula such that any resulting next information state satisfies it, is the progression of the initial specification. Regression is defined analogously, in the other direction.

Synthesis of protocols in dynamic epistemic logic has only recently been investigated. Dynamic epistemic logics are modal logics with modal operators for knowledge, and also dynamic modal operators of a rather particular kind, namely wherein the information state transition is already encoded in the operator. A well-known such dynamic operator is 'public announcement'. In that case, the current information state is restricted to the submodel satisfying the announcement formula. Topics in the current interest of the dynamic epistemic planning research community include the analysis and synthesis of epistemic protocols for certain dedicated applications,

such as gossip protocols, the integration of temporal epistemic and dynamic epistemic logics, the integration of agency in dynamic epistemic logics, and dedicated protocol logics. Restrictions to specific protocols may make synthesis problems tractable.

The workshop 'To be announced!' is focussed around five themes involving epistemic planning:

Agency concurrency uncertainty communication strategy

The keynote invitees for the workshop 'To be announced!" are

Natasha Alechina, University of Nottingham, United Kingdom

Guillaume Aucher, IRISA / University of Rennes, France

Valentin Goranko, Stockholm University, Sweden

Jerome Lang, Universite Paris Dauphine, France

Yongmei Liu, Sun Yat-sen University, China

Robert Mattmüller, University Freiburg, Germany

Sheila McIlraith, University of Toronto, Canada

Yoram Moses, Israel Institute of Technology, Israel

Ron Petrick, Edinburgh University, United Kingdom

Sophie Pinchinat, IRISA / University of Rennes, France

Matthijs Spaan, Delft University, Netherlands

Yanjing Wang, Peking University, China

Typical works in the area of epistemic planning by these authors will later be added to the webpage.


Follow us on:

Niels Bohrweg 1 & 2

2333 CA Leiden

The Netherlands

+31 71 527 5400