<figure><img src="image_2.png" /><figcaption>Figure 1: Generalised gossiping: time to find an optimal plan vs. epistemic depth (for different fixed numbers of agents)</figcaption></figure>

<table><caption>Table 6: Generalised gossiping with ignorance goals: optimal plans found by FDSS-2014 and Planning-PDBs, for n = 4 agents</caption><tr><td>G-neg<sub>1, {S<sub>1</sub> S<sub>2</sub>}</sub></td><td>&lt;call<sup>1</sup><sub>3</sub>, call<sup>1</sup><sub>4</sub>, call<sup>2</sup><sub>4</sub>, call<sup>3</sup><sub>4</sub>&gt;</td></tr><tr><td>G-neg<sub>1, {S<sub>1</sub> S<sub>3</sub>, S<sub>2</sub> S<sub>4</sub>}</sub></td><td>&lt;call<sup>1</sup><sub>2</sub>, call<sup>1</sup><sub>4</sub>, call<sup>2</sup><sub>3</sub>, call<sup>3</sup><sub>4</sub>&gt;</td></tr><tr><td>G-neg<sub>2, {S<sub>1</sub> S<sub>2</sub> S<sub>3</sub>}</sub></td><td>&lt;call<sup>1</sup><sub>2</sub>, call<sup>2</sup><sub>4</sub>, call<sup>3</sup><sub>4</sub>, call<sup>1</sup><sub>3</sub>, call<sup>2</sup><sub>3</sub>, call<sup>2</sup><sub>4</sub>&gt;</td></tr><tr><td>G-neg<sub>3, {S<sub>1</sub> S<sub>2</sub> S<sub>3</sub>}</sub></td><td>(timeout)</td></tr></table>
<figure><img src="image_2.png" /><figcaption>Figure 2: Generalised gossiping: time to find an optimal plan vs. number of agents (for different fixed epistemic depths)</figcaption></figure>

**Authorisation via plenary meetings.** We ran Planning-PDBs on the plenary meetings problem for varying numbers of agents $n$ and numbers of meetings ('steps') $m$.

Figure 3 shows the time needed by Planning-PDBs to find an optimal plan, in seconds, relative to the number of agents, where each curve plotted is for a fixed number of meetings. For $m = 1$ the timeout obtained when $n = 7$; for $m = 2$ when $n = 5$; and for $m = 3$ when $n = 4$.

Figure 4 depicts the time to find an optimal plan w.r.t. the number of meetings, each curve being for a fixed number of agents. The curve for two agents provides some evidence for an exponential effect depending on the number of meetings.
<figure><img src="image_3.png" /><figcaption>Figure 2: Generalised gossiping: time to find an optimal plan vs. number of agents (for different fixed epistemic depths)</figcaption></figure>

**Authorisation via plenary meetings.** We ran Planning-PDBs on the plenary meetings problem for varying numbers of agents $n$ and numbers of meetings ('steps') $m$.

Figure 3 shows the time needed by Planning-PDBs to find an optimal plan, in seconds, relative to the number of agents, where each curve plotted is for a fixed number of meetings. For $m = 1$ the timeout obtained when $n = 7$; for $m = 2$ when $n = 5$; and for $m = 3$ when $n = 4$.

Figure 4 depicts the time to find an optimal plan w.r.t. the number of meetings, each curve being for a fixed number of agents. The curve for two agents provides some evidence for an exponential effect depending on the number of meetings.
<figure><img src="image_3.png" /><figcaption>Figure 3: Plenary meetings: time to find an optimal parallel plan vs. number of agents (for different fixed numbers of meetings)</figcaption></figure>

# 8. Related work

We now compare our approach with DEL-based planning as well as with the three existing approaches that can be viewed as particular cases of it. The latter either restrict the language to epistemic literals or restrict DEL's event models in a way such that actions are public or semi-private.

## 8.1. *Planning with DEL event models*

DEL-based planning was studied extensively in the literature in the last ten years [15, 16, 17, 18, 59, 19]. We show that our action descriptions can capture several important kinds of DEL event models (precisely, public, private and semi-private announcements) and the other way round, we show for some of our action descriptions how they correspond to DEL event models. One might expect that all such descriptions have a corresponding DEL event model; however, the correspondence is not obvious due to fundamen-
<figure><img src="image_4.png" /><figcaption>Figure 3: Plenary meetings: time to find an optimal parallel plan vs. number of agents (for different fixed numbers of meetings)</figcaption></figure>

# 8. Related work

We now compare our approach with DEL-based planning as well as with the three existing approaches that can be viewed as particular cases of it. The latter either restrict the language to epistemic literals or restrict DEL's event models in a way such that actions are public or semi-private.

## 8.1. *Planning with DEL event models*

DEL-based planning was studied extensively in the literature in the last ten years [15, 16, 17, 18, 59, 19]. We show that our action descriptions can capture several important kinds of DEL event models (precisely, public, private and semi-private announcements) and the other way round, we show for some of our action descriptions how they correspond to DEL event models. One might expect that all such descriptions have a corresponding DEL event model; however, the correspondence is not obvious due to fundamen-
<figure><img src="image_4.png" /><figcaption>Figure 4: Plenary meetings: time to find an optimal parallel plan vs. number of meetings (for different fixed numbers of agents)</figcaption></figure>

tal differences in the way epistemic effects are modelled. We explain this in detail in Section 8.1.5.

### 8.1.1. Event models and product updates

A DEL *event model* is a tuple $Evt = \langle W^{Evt}, \sim_A^{Evt}, \{\sim_i^{Evt}\}_{i \in A}, pre^{Evt}, post^{Evt} \rangle$ where $W^{Evt}$ is a finite set of events; $\sim_A^{Evt}$ and the $\sim_i^{Evt}$ are equivalence relations on $W^{Evt}$ such that every $\sim_i^{Evt}$ is a subset of $\sim_A^{Evt}$; $pre^{Evt} : W^{Evt} \to \mathcal{L}_{EL}$ maps events to their preconditions; and $post^{Evt} : W^{Evt} \to (\mathbb{P} \to \mathcal{L}_{EL})$ maps events to partial functions such that for every $e \in W^{Evt}$, $post^{Evt}(e)$ is undefined almost everywhere. A *pointed event model* is a pair $(Evt, e)$ where $e \in W^{Evt}$ is the designated event (or the actual event). A *multipointed event model* is a pair $(Evt, E)$ where $E \subseteq W^{Evt}$ is such that for any two distinct events $e, e'$ in $E$, the preconditions of $e$ and $e'$ are incompatible, that is, $pre^{Evt}(e) \wedge pre^{Evt}(e')$ is unsatisfiable.

Here are some examples and their representations as graphs, in which
<figure><img src="image_5.png" /><figcaption>Figure 4: Plenary meetings: time to find an optimal parallel plan vs. number of meetings (for different fixed numbers of agents)</figcaption></figure>

tal differences in the way epistemic effects are modelled. We explain this in detail in Section 8.1.5.

### 8.1.1. Event models and product updates

A DEL *event model* is a tuple $Evt = \langle W^{Evt}, \sim_A^{Evt}, \{\sim_i^{Evt}\}_{i \in A}, pre^{Evt}, post^{Evt} \rangle$ where $W^{Evt}$ is a finite set of events; $\sim_A^{Evt}$ and the $\sim_i^{Evt}$ are equivalence relations on $W^{Evt}$ such that every $\sim_i^{Evt}$ is a subset of $\sim_A^{Evt}$; $pre^{Evt} : W^{Evt} \to \mathcal{L}_{EL}$ maps events to their preconditions; and $post^{Evt} : W^{Evt} \to (\mathbb{P} \to \mathcal{L}_{EL})$ maps events to partial functions such that for every $e \in W^{Evt}$, $post^{Evt}(e)$ is undefined almost everywhere. A *pointed event model* is a pair $(Evt, e)$ where $e \in W^{Evt}$ is the designated event (or the actual event). A *multipointed event model* is a pair $(Evt, E)$ where $E \subseteq W^{Evt}$ is such that for any two distinct events $e, e'$ in $E$, the preconditions of $e$ and $e'$ are incompatible, that is, $pre^{Evt}(e) \wedge pre^{Evt}(e')$ is unsatisfiable.

Here are some examples and their representations as graphs, in which
<figure><img src="image_5.png" /><figcaption>Figure 5: DEL event models for the public assignment of $\varphi$ to $p$ (on the left) and for the truthful public announcement of $\varphi$ (on the right).</figcaption></figure>

nodes are events, labelled arrows represent the equivalence relations, the actual event is denoted via a double outline, and pre- and postconditions are given respectively in the top and bottom line in the nodes. An undefined postcondition is denoted by *skip*. We will often omit transitive and reflexive arrows for clarity.

1. The public assignment of $\varphi$ to $p$, i.e., the event where $p$ publicly gets the truth value of $\varphi$, is modelled by an event model Assign($p, \varphi$) with a single point $e_1$ whose precondition is $\top$, with total relations, i.e., such that $\sim_{\mathcal{A}}^{\text{Evt}} = \sim_i^{\text{Evt}} = \{(e_1, e_1)\}$, and with the postcondition function post$^{\text{Evt}}(e_1)$ such that post$^{\text{Evt}}(e_1)(p) = \varphi$ and undefined for all $q \neq p$. This event model is shown on the left-hand side in Figure 5.

2. The truthful public announcement of a formula $\varphi$ is modelled by an event model PubAnn($\varphi$), represented on the right-hand side of Figure 5, with a single point $e_2$ whose precondition is $\varphi$, with total relations and with an undefined postcondition function.

3. The truthful semi-private announcement whether $\varphi$ to agent $i$ is when $i$ learns whether $p$ and the other agents only learn that $i$ learns whether $p$ without learning whether $p$ themselves. This is modelled by an event model SemiPrivAnn($\varphi, i$) with two points $e^+$ and $e^-$ where $pre^{\text{Evt}}(e^+) = \varphi$ and $pre^{\text{Evt}}(e^-) = \neg\varphi$, with an undefined postcondition function, and with $\sim_{\mathcal{A}}^{\text{Evt}} = \sim_j^{\text{Evt}} = \{e^+, e^-\} \times \{e^+, e^-\}$ for every $j \neq i$ and $\sim_i^{\text{Evt}} = \{(e^+, e^+), (e^-, e^-)\}$. When we want to model that $i$ learns that $\varphi$ then $e^+$ is the designated event; otherwise it is $e^-$, as is the case in Figure 6.
<figure><img src="image_6.png" /><figcaption>Figure 5: DEL event models for the public assignment of $\varphi$ to $p$ (on the left) and for the truthful public announcement of $\varphi$ (on the right).</figcaption></figure>

nodes are events, labelled arrows represent the equivalence relations, the actual event is denoted via a double outline, and pre- and postconditions are given respectively in the top and bottom line in the nodes. An undefined postcondition is denoted by *skip*. We will often omit transitive and reflexive arrows for clarity.

1. The public assignment of $\varphi$ to $p$, i.e., the event where $p$ publicly gets the truth value of $\varphi$, is modelled by an event model Assign($p, \varphi$) with a single point $e_1$ whose precondition is $\top$, with total relations, i.e., such that $\sim_{\mathcal{A}}^{\text{Evt}} = \sim_i^{\text{Evt}} = \{(e_1, e_1)\}$, and with the postcondition function post$^{\text{Evt}}(e_1)$ such that post$^{\text{Evt}}(e_1)(p) = \varphi$ and undefined for all $q \neq p$. This event model is shown on the left-hand side in Figure 5.

2. The truthful public announcement of a formula $\varphi$ is modelled by an event model PubAnn($\varphi$), represented on the right-hand side of Figure 5, with a single point $e_2$ whose precondition is $\varphi$, with total relations and with an undefined postcondition function.

3. The truthful semi-private announcement whether $\varphi$ to agent $i$ is when $i$ learns whether $p$ and the other agents only learn that $i$ learns whether $p$ without learning whether $p$ themselves. This is modelled by an event model SemiPrivAnn($\varphi, i$) with two points $e^+$ and $e^-$ where $pre^{\text{Evt}}(e^+) = \varphi$ and $pre^{\text{Evt}}(e^-) = \neg\varphi$, with an undefined postcondition function, and with $\sim_{\mathcal{A}}^{\text{Evt}} = \sim_j^{\text{Evt}} = \{e^+, e^-\} \times \{e^+, e^-\}$ for every $j \neq i$ and $\sim_i^{\text{Evt}} = \{(e^+, e^+), (e^-, e^-)\}$. When we want to model that $i$ learns that $\varphi$ then $e^+$ is the designated event; otherwise it is $e^-$, as is the case in Figure 6.
<figure><img src="image_6.png" /><figcaption>Figure 6: DEL event model for the truthful semi-private announcement of $\neg \varphi$ to agent $i$.</figcaption></figure>

<figure><img src="image_7.png" /><figcaption>Figure 7: DEL event model for the public forgetting of $p$.</figcaption></figure>

4. The public forgetting of a propositional variable $p$ by all agents [60] can be captured by an event model PubForget($p$) with three points $n$, $e^+$ and $e^-$ where $pre^{Evt}(n) = pre^{Evt}(e^+) = pre^{Evt}(e^-) = \top$, where $\sim_A^{Evt} = \sim_i^{Evt} = \{n, e^+, e^-\} \times \{n, e^+, e^-\}$ for every $i$, and where $post^{Evt}$ is such that $post^{Evt}(n)(p) = p$, $post^{Evt}(e^+)(p) = \top$, $post^{Evt}(e^-)(p) = \bot$, and $post^{Evt}(n) = skip$. This event model is represented in Figure 7. Note that a (single-pointed) event model with two points would not do the job: it would force commitment to some ontic event taking place.

950

Given a Kripke model $M = (W, \sim_A, \{\sim_i\}_{i \in A}, V)$ as defined in Section 4 and an event model Evt, the product update of $M$ by Evt is the Kripke model $M \otimes Evt = (W', \sim'_A, \{\sim'_i\}_{i \in A}, V')$ with

955

* $W' = \{(s, e) : s \in W, e \in W^{Evt}, \text{ and } (M, s) \models pre^{Evt}(e)\}$;

* $(s, e) \sim'_A (t, f)$ iff $s \sim_A t$ and $e \sim_A^{Evt} f$;
<figure><img src="image_7.png" /><figcaption>Figure 6: DEL event model for the truthful semi-private announcement of $\neg \varphi$ to agent i.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Figure 7: DEL event model for the public forgetting of $p$.</figcaption></figure>

4. The public forgetting of a propositional variable $p$ by all agents [60] can be captured by an event model PubForget($p$) with three points $n$, $e^+$ and $e^-$ where $pre^{Evt}(n) = pre^{Evt}(e^+) = pre^{Evt}(e^-) = \top$, where $\sim_{\mathcal{A}}^{Evt} = \sim_i^{Evt} = \{n, e^+, e^-\} \times \{n, e^+, e^-\}$ for every $i$, and where $post^{Evt}$ is such that $post^{Evt}(n)(p) = p$, $post^{Evt}(e^+)(p) = \top$, $post^{Evt}(e^-)(p) = \bot$, and $post^{Evt}(n) = skip$. This event model is represented in Figure 7. Note that a (single-pointed) event model with two points would not do the job: it would force commitment to some ontic event taking place.

950

Given a Kripke model $M = (W, \sim_{\mathcal{A}}, \{\sim_i\}_{i \in \mathcal{A}}, V)$ as defined in Section 4 and an event model Evt, the product update of $M$ by Evt is the Kripke model $M \otimes Evt = (W', \sim'_{\mathcal{A}}, \{\sim'_i\}_{i \in \mathcal{A}}, V')$ with

955

* $W' = \{(s, e) : s \in W, e \in W^{Evt}, \text{ and } (M, s) \models pre^{Evt}(e)\}$;

* $(s, e) \sim'_{\mathcal{A}} (t, f)$ iff $s \sim_{\mathcal{A}} t$ and $e \sim_{\mathcal{A}}^{Evt} f$;
• $(s, e) \sim'_{i} (t, f)$ iff $s \sim_i t$ and $e \sim^{{\tt Evt}}_{i} f$, for every $i \in A$;

• $V'((s, e)) = \{p : \mathit{post}^{\mathit{Evt}}(e)(p) \text{ is undefined and } (M, s) \models p\} \cup \{p : \mathit{post}^{\mathit{Evt}}(e)(p) \text{ is defined and } (M, s) \models \mathit{post}^{\mathit{Evt}}(e)(p)\}$.

The product update of a pointed Kripke model $(M, s)$ with a pointed event model $(\mathit{Evt}, e)$ is the pointed Kripke model $(M \otimes \mathit{Evt}, (s, e))$, defined only when $(M, s) \models \mathit{pre}^{\mathit{Evt}}(e)$. The product update of a pointed model $(M, s)$ with a multi-pointed event model $(\mathit{Evt}, E)$ is the pointed model $(M \otimes \mathit{Evt}, (s, e))$ where $e \in E$ is such that $(M, s) \models \mathit{pre}^{\mathit{Evt}}(e)$, defined when such an $e$ exists in $E$. In that case the hypothesis in the definition of a multipointed event model that the preconditions of different events are incompatible ensures that it is unique.

### 8.1.2. Bisimulations

We recall a standard notion in modal logics that will be instrumental to prove our results: a *bisimulation* [61] between two Kripke models $M = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$ and $M' = \langle W', \sim'_{A}, \{\sim'_i\}_{i \in A}, V' \rangle$ is a relation $Z \subseteq W \times W'$ such that for all $w \in W$ and $w' \in W'$ such that $wZw'$: $V(w) = V'(w')$ (atomic); if $w \sim_A u$ then $uZu'$ and $w' \sim'_{A} u'$ for some $u'$, and if $w \sim_i u$ then $uZu'$ and $w' \sim'_i u'$ for some $u'$ (forth); if $w' \sim'_{A} u'$ then $uZu'$ and $w \sim_A u$ for some $u$, and if $w' \sim'_i u'$ then $uZu'$ and $w \sim_i u$ for some $u$ (back). Two pointed models $(M, w)$ and $(M', w')$ are *bisimilar* if there exists a bisimulation $Z$ between $M$ and $M'$ such that $wZw'$. In that case, we have $M, w \models \varphi$ iff $M', w' \models \varphi$ for every formula $\varphi \in \mathcal{L}_{\mathrm{EL}}$ [35].

### 8.1.3. From DEL event models to EL-O action descriptions

In what follows we show that we can express several kinds of event models, where we sometimes restrict preconditions to literals and conjunctions thereof. We are going to associate an EL-O action description $a(\mathit{Evt}, e)$ to a given pointed event model $(\mathit{Evt}, e)$. In all cases, the precondition of $a(\mathit{Evt}, e)$ is $\mathit{pre}^{\mathit{Evt}}(e)$. (More precisely, it is the reduction of $\mathit{pre}^{\mathit{Evt}}(e)$ to an $\mathcal{L}_{\mathit{bool}}(\mathit{OA})$ formula obtained by exhaustively applying the reduction axioms of Section 4.4.) So $M^{\mathrm{EL-O}}$, $s \models \mathit{pre}^{\mathit{Evt}}(e)$ exactly when $R_{a(\mathit{Evt},e)}^{\mathrm{EL-O}}$ is defined at $s$. For such
• $(s, e) \sim'_{i} (t, f)$ iff $s \sim_i t$ and $e \sim^{{\tt Evt}}_{i} f$, for every $i \in A$;

• $V'((s, e)) = \{p : \text{post}^{\text{Evt}}(e)(p) \text{ is undefined and } (M, s) \models p\} \cup \{p : \text{post}^{\text{Evt}}(e)(p) \text{ is defined and } (M, s) \models \text{post}^{\text{Evt}}(e)(p)\}$.

The product update of a pointed Kripke model $(M, s)$ with a pointed event model $(\text{Evt}, e)$ is the pointed Kripke model $(M \otimes \text{Evt}, (s, e))$, defined only when $(M, s) \models \text{pre}^{\text{Evt}}(e)$. The product update of a pointed model $(M, s)$ with a multi-pointed event model $(\text{Evt}, E)$ is the pointed model $(M \otimes \text{Evt}, (s, e))$ where $e \in E$ is such that $(M, s) \models \text{pre}^{\text{Evt}}(e)$, defined when such an $e$ exists in $E$. In that case the hypothesis in the definition of a multipointed event model that the preconditions of different events are incompatible ensures that it is unique.

### 8.1.2. Bisimulations

We recall a standard notion in modal logics that will be instrumental to prove our results: a *bisimulation* [61] between two Kripke models $M = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$ and $M' = \langle W', \sim'_{A}, \{\sim'_i\}_{i \in A}, V' \rangle$ is a relation $Z \subseteq W \times W'$ such that for all $w \in W$ and $w' \in W'$ such that $wZw'$: $V(w) = V'(w')$ (atomic); if $w \sim_A u$ then $uZu'$ and $w' \sim'_{A} u'$ for some $u'$, and if $w \sim_i u$ then $uZu'$ and $w' \sim'_i u'$ for some $u'$ (forth); if $w' \sim'_{A} u'$ then $uZu'$ and $w \sim_A u$ for some $u$, and if $w' \sim'_i u'$ then $uZu'$ and $w \sim_i u$ for some $u$ (back). Two pointed models $(M, w)$ and $(M', w')$ are *bisimilar* if there exists a bisimulation $Z$ between $M$ and $M'$ such that $wZw'$. In that case, we have $M, w \models \varphi$ iff $M', w' \models \varphi$ for every formula $\varphi \in \mathcal{L}_{\text{EL}}$ [35].

### 8.1.3. From DEL event models to EL-O action descriptions

In what follows we show that we can express several kinds of event models, where we sometimes restrict preconditions to literals and conjunctions thereof. We are going to associate an EL-O action description $a(\text{Evt}, e)$ to a given pointed event model $(\text{Evt}, e)$. In all cases, the precondition of $a(\text{Evt}, e)$ is $\text{pre}^{\text{Evt}}(e)$. (More precisely, it is the reduction of $\text{pre}^{\text{Evt}}(e)$ to an $\mathcal{L}_{\text{bool}}(\text{OA})$ formula obtained by exhaustively applying the reduction axioms of Section 4.4.) So $M^{\text{EL-O}}$, $s \models \text{pre}^{\text{Evt}}(e)$ exactly when $R_{a(\text{Evt},e)}^{\text{EL-O}}$ is defined at $s$. For such
points $s$, it can be shown that the pointed product update $(M^{\mathrm{EL-O}} \otimes \mathrm{Evt}, (s, e))$ is bisimilar to the pointed Kripke model $(M^{\mathrm{EL-O}}, t)$ for the state $t$ such that
$$sR_{a(\mathrm{Evt},e)}^{\mathrm{EL-O}} t.$$

990

First, let us look at some kinds of public assignments. Assign($p, \top$) is captured by the action description $a(\mathrm{Assign}(p, \top), e_1) = \langle \top, \{\langle \top, \{JS p, p\}, \emptyset \rangle\} \rangle$ and Assign($p, \bot$) is captured by $a(\mathrm{Assign}(p, \bot), e_1) = \langle \top, \{\langle \top, \{JS p\}, \{p\} \rangle\} \rangle$. Finally, Assign($p, \neg p$) is the public toggling of the truth value of $p$ and is captured by an action description with two conditional effects

995

$$a(\mathrm{Assign}(p, \neg p), e_1) = \langle \top, \{\langle \neg p, \{p\}, \emptyset \rangle, \langle p, \emptyset, \{p\} \rangle \} \rangle.$$

Observe that, contrarily to Assign($p, \top$) and Assign($p, \bot$), Assign($p, \neg p$) does not modify $JS p$: if an agent does not know whether $p$ before the public toggling of $p$ then she also does not know whether $p$ afterwards.

Second, let us look at some kinds of public announcements. The truthful public announcement of a propositional variable $p$ is captured by the action description with precondition $p$, unconditional positive effect $JS p$, and without negative effects: $a(\mathrm{PubAnn}(p), e_2) = \langle p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle$. Symmetrically, the public announcement of $\neg p$ is captured by $a(\mathrm{PubAnn}(\neg p), e_2) = \langle \neg p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle$. More generally, we can capture the public announcement of conjunctions of atoms and negations of atoms:

$$a(\mathrm{PubAnn}((\bigwedge_{\alpha \in A^+} \alpha) \wedge (\bigwedge_{\alpha \in A^-} \neg \alpha)), e_2) = \langle (\bigwedge_{\alpha \in A^+} \alpha) \wedge (\bigwedge_{\alpha \in A^-} \neg \alpha), \{\langle \top, \{JS \alpha : \alpha \in A^+ \cup A^-\}, \emptyset \rangle\} \rangle.$$

The precondition guarantees that for example the public announcement of $JS p \wedge \neg S_i p$ cannot be made. Here are some examples of public announcements of the above conjunctions. We also add the equivalent formulation in the standard epistemic language.

$$a(\mathrm{PubAnn}(\neg K_i p \wedge \neg K_i \neg p), e_2) = a(\mathrm{PubAnn}(\neg S_i p), e_2) = \langle \neg S_i p, \{\langle \top, \{JS S_i p\}, \emptyset \rangle\} \rangle,$$

$$a(\mathrm{PubAnn}(K_i p), e_2) = a(\mathrm{PubAnn}(p \wedge S_i p), e_2) = \langle p \wedge S_i p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle,$$

$$a(\mathrm{PubAnn}(p \wedge \neg K_i p), e_2) = a(\mathrm{PubAnn}(p \wedge \neg S_i p), e_2) = \langle p \wedge \neg S_i p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle.$$

1000

In the announcement of $p \wedge S_i p$ and of the Moore sentence $p \wedge \neg S_i p$ we have
points $s$, it can be shown that the pointed product update $(M^{\mathrm{EL-O}} \otimes \mathrm{Evt}, (s, e))$ is bisimilar to the pointed Kripke model $(M^{\mathrm{EL-O}}, t)$ for the state $t$ such that
$sR_{a(\mathrm{Evt},e)}^{\mathrm{EL-O}} t$.

990

First, let us look at some kinds of public assignments. Assign($p, \top$) is captured by the action description $a(\mathrm{Assign}(p, \top), e_1) = \langle \top, \{\langle \top, \{JS p, p\}, \emptyset \rangle\} \rangle$ and Assign($p, \bot$) is captured by $a(\mathrm{Assign}(p, \bot), e_1) = \langle \top, \{\langle \top, \{JS p\}, \{p\} \rangle\} \rangle$. Finally, Assign($p, \neg p$) is the public toggling of the truth value of $p$ and is captured by an action description with two conditional effects

995

$$a(\mathrm{Assign}(p, \neg p), e_1) = \langle \top, \{\langle \neg p, \{p\}, \emptyset \rangle, \langle p, \emptyset, \{p\} \rangle\} \rangle.$$

Observe that, contrarily to Assign($p, \top$) and Assign($p, \bot$), Assign($p, \neg p$) does not modify $JS p$: if an agent does not know whether $p$ before the public toggling of $p$ then she also does not know whether $p$ afterwards.

Second, let us look at some kinds of public announcements. The truthful public announcement of a propositional variable $p$ is captured by the action description with precondition $p$, unconditional positive effect $JS p$, and without negative effects: $a(\mathrm{PubAnn}(p), e_2) = \langle p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle$. Symmetrically, the public announcement of $\neg p$ is captured by $a(\mathrm{PubAnn}(\neg p), e_2) = \langle \neg p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle$. More generally, we can capture the public announcement of conjunctions of atoms and negations of atoms:

$$a(\mathrm{PubAnn}((\bigwedge_{\alpha \in A^+} \alpha) \wedge (\bigwedge_{\alpha \in A^-} \neg \alpha)), e_2) = \langle (\bigwedge_{\alpha \in A^+} \alpha) \wedge (\bigwedge_{\alpha \in A^-} \neg \alpha), \{\langle \top, \{JS \alpha : \alpha \in A^+ \cup A^-\}, \emptyset \rangle\} \rangle.$$

The precondition guarantees that for example the public announcement of $JS p \wedge \neg S_i p$ cannot be made. Here are some examples of public announcements of the above conjunctions. We also add the equivalent formulation in the standard epistemic language.

$$a(\mathrm{PubAnn}(\neg K_i p \wedge \neg K_i \neg p), e_2) = a(\mathrm{PubAnn}(\neg S_i p), e_2) = \langle \neg S_i p, \{\langle \top, \{JS S_i p\}, \emptyset \rangle\} \rangle,$$

$$a(\mathrm{PubAnn}(K_i p), e_2) = a(\mathrm{PubAnn}(p \wedge S_i p), e_2) = \langle p \wedge S_i p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle,$$

$$a(\mathrm{PubAnn}(p \wedge \neg K_i p), e_2) = a(\mathrm{PubAnn}(p \wedge \neg S_i p), e_2) = \langle p \wedge \neg S_i p, \{\langle \top, \{JS p\}, \emptyset \rangle\} \rangle.$$

1000

In the announcement of $p \wedge S_i p$ and of the Moore sentence $p \wedge \neg S_i p$ we have
dropped $JS S_i p$ from the add-list because it already contains $JS p$ (cf. the EL-O axiom $Vis_5$).

Third, the semi-private announcement to $i$ that $p$ is true is captured by the action description

1005

$$a(\text{SemiPrivAnn}(p, i), e^+) = \langle p, \{\langle \top, \{S_i p, JS S_i p\}, \emptyset \rangle\} \rangle.$$

So the effect is that $i$ sees whether $p$ and that all agents jointly see that; in other words, that it becomes common knowledge that $i$ sees whether $p$.

Fourth, the event model PubForget($p$) of publicly forgetting $p$ corresponds to the action description

1010

$$a(\text{PubForget}(p), n) = \langle \top, \{\langle \top, \{JS S_i p : i \in A\}, \{S_i p : i \in A\} \rangle\} \rangle.$$

That is, all $S_i p$ become false and this becomes common knowledge.

**Proposition 15.** For each of the above event models $Evt$:

1. $M^{\text{EL-O}}$, $s \models \text{pre}^{\text{Evt}}(e)$ if and only if $R_{a(\text{Evt},e)}^{\text{EL-O}}$ is defined at $s$;

2. If $sR_{a(\text{Evt},e)}^{\text{EL-O}}$ then $(M^{\text{EL-O}}, s')$ and $(M^{\text{EL-O}} \otimes \text{Evt}, (s, e))$ are bisimilar.

1015

*Proof.* The first item is the case because, as already mentioned, the precondition of the action descriptions $a(\text{Evt}, e)$ are all equivalent to $\text{pre}^{\text{Evt}}(e)$.

We sketch the proof of the second item for the public announcement of $p$. Let $M^{\text{EL-O}} \otimes \text{PubAnn}(p) = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$, and consider $s \in W^{\text{EL-O}}$ such that $sR_{a(\text{PubAnn}(p))}^{\text{EL-O}}$ $s'$, i.e., such that $s' = s \cup \{JS p\}$. We show that the pointed models $(M^{\text{EL-O}}, s')$ and $(M^{\text{EL-O}} \otimes \text{PubAnn}(p), (s, e_2))$ are bisimilar, where $e_2$ is the single event of the event model PubAnn($p$). To that end we define the relation $Z$ between $W^{\text{EL-O}}$ and $W$ as: $s'Z(s, e_2)$ iff $s' = s \cup \{JS p\}$. It can be checked that the three conditions for $Z$ being a bisimulation are satisfied: atomic, forth, and back.

1020

The other proofs are similar; we only sketch the case of public forgetting of $p$, PubForget($p$). Suppose $sR_{a(\text{PubForget}(p))}^{\text{EL-O}}$ $t$, i.e.,

$$t = (s \setminus \{S_i p : i \in A\}) \leftrightarrow) \cup \{JS S_i p : i \in A\}.$$

For every $s$, this state $t$ is unique: we denote it by $R_{a(\text{PubForget}(p))}^{\text{EL-O}}(s)$. We show that $(M^{\text{EL-O}}, t)$ and $(M^{\text{EL-O}} \otimes \text{PubForget}(p), (s, n))$ are bisimilar via the following
dropped $JS S_i p$ from the add-list because it already contains $JS p$ (cf. the EL-O axiom $Vis_5$).

Third, the semi-private announcement to $i$ that $p$ is true is captured by the action description

$$ a(\text{SemiPrivAnn}(p, i), e^+) = \langle p, \{\langle \top, \{S_i p, JS S_i p\}, \emptyset \rangle\} \rangle. $$

So the effect is that $i$ sees whether $p$ and that all agents jointly see that; in other words, that it becomes common knowledge that $i$ sees whether $p$.

Fourth, the event model PubForget($p$) of publicly forgetting $p$ corresponds to the action description

$$ a(\text{PubForget}(p), n) = \langle \top, \{\langle \top, \{JS S_i p : i \in A\}, \{S_i p : i \in A\} \rangle\} \rangle. $$

That is, all $S_i p$ become false and this becomes common knowledge.

**Proposition 15.** For each of the above event models $Evt$:

1. $M^{\text{EL-O}}$, $s \models \text{pre}^{\text{Evt}}(e)$ if and only if $R_{a(\text{Evt},e)}^{\text{EL-O}}$ is defined at $s$;

2. If $sR_{a(\text{Evt},e)}^{\text{EL-O}}$ then $(M^{\text{EL-O}}, s')$ and $(M^{\text{EL-O}} \otimes \text{Evt}, (s, e))$ are bisimilar.

*Proof.* The first item is the case because, as already mentioned, the precondition of the action descriptions $a(\text{Evt}, e)$ are all equivalent to $\text{pre}^{\text{Evt}}(e)$.

We sketch the proof of the second item for the public announcement of $p$. Let $M^{\text{EL-O}} \otimes \text{PubAnn}(p) = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$, and consider $s \in W^{\text{EL-O}}$ such that $sR_{a(\text{PubAnn}(p))}^{\text{EL-O}}$ s', i.e., such that $s' = s \cup \{JS p\}$. We show that the pointed models $(M^{\text{EL-O}}, s')$ and $(M^{\text{EL-O}} \otimes \text{PubAnn}(p), (s, e_2))$ are bisimilar, where $e_2$ is the single event of the event model PubAnn($p$). To that end we define the relation $Z$ between $W^{\text{EL-O}}$ and $W$ as: $s'Z(s, e_2)$ iff $s' = s \cup \{JS p\}$. It can be checked that the three conditions for $Z$ being a bisimulation are satisfied: atomic, forth, and back.

The other proofs are similar; we only sketch the case of public forgetting of $p$, PubForget($p$). Suppose $sR_{a(\text{PubForget}(p))}^{\text{EL-O}}$ t, i.e.,

$$ t = (s \setminus \{S_i p : i \in A\}) \leftrightarrow) \cup \{JS S_i p : i \in A\} \Rightarrow. $$

For every $s$, this state $t$ is unique: we denote it by $R_{a(\text{PubForget}(p))}^{\text{EL-O}}(s)$. We show that $(M^{\text{EL-O}}, t)$ and $(M^{\text{EL-O}} \otimes \text{PubForget}(p), (s, n))$ are bisimilar via the following
relation Z between W and $W^{\text{EL-O}}$:

$$
\begin{align*}
Z &= \{ \langle R_{a(\text{PubForget}(p))}^{\text{EL-O}}(s), (s, n) \rangle \} \cup \\
  &\quad \{ \langle R_{a(\text{PubForget}(p))}^{\text{EL-O}}(s) \cup \{p\}, (s, e^+) \rangle \} \cup \\
  &\quad \{ \langle R_{a(\text{PubForget}(p))}^{\text{EL-O}}(s) \setminus \{p\}, (s, e^-) \rangle \}
\end{align*}
$$

1025 It can be checked that Z is indeed a bisimulation. □

Something that cannot be modelled in our framework is the public an-
nouncement that $\neg K_i p$, or, expressed in the EL-O fragment, that $\neg (p \wedge S_i p)$.
The reason is that it is not clear how the disjunctive effect of that announce-
ment could be described in terms of an add-list.

8.1.4. *From EL-O action descriptions to DEL event models*

We now consider the converse direction: given an EL-O action descrip-
tion a, can we find a DEL event model (Evt, E) such that for any state s ∈
W<sup>EL-O</sup>, the product (M<sup>EL-O</sup> ⊗ Evt, (s, e)) of (M<sup>EL-O</sup>, s) and (Evt, E) is defined iff
s |= pre(a), and such that in that case, (M<sup>EL-O</sup> ⊗ Evt, (s, e)) and (M<sup>EL-O</sup>, s') are
bisimilar, where s' is the state such that sR<sub>a</sub><sup>EL-O</sup>s'?

1035

Let us here restrict our attention to a few very basic EL-O action descrip-
tions in which there is a single conditional effect either adding or deleting
one atom. The idea behind the construction of an equivalent event model is
the following: when adding or deleting an atom from a world, only agents
who see this atom know that it has been modified.

1040

The easiest way to translate this into DEL event models is through
the use of Bolander's *edge-conditioned event models* [62, 63]. Such mod-
els incorporate conditions on accessibility relations, so that a model is a
tuple Evt = ⟨W<sup>Evt</sup>, R<sub>⊤</sub><sup>Evt</sup>, {R<sub>i</sub><sup>Evt</sup>}<sub>i∈⊤</sub>, pre<sup>Evt</sup>, post<sup>Evt</sup>⟩ where R<sub>⊤</sub><sup>Evt</sup> : W<sup>Evt</sup> × W<sup>Evt</sup> → ℒ<sub>EL</sub>,
R<sub>i</sub><sup>Evt</sup> : W<sup>Evt</sup> × W<sup>Evt</sup> → ℒ<sub>EL</sub> for every i ∈ ⊤, and the rest is defined as previ-
ously. The product of such an edge-conditioned event model with a model
M = ⟨W, ∼<sub>⊤</sub>, {∼<sub>i</sub>}<sub>i∈⊤</sub>, V⟩ is M ⊗ Evt = ⟨W', ∼'<sub>⊤</sub>, {∼'<sub>i</sub>}<sub>i∈⊤</sub>, V'⟩ where

1045

• (s, e) ~'_{\mathbb{A}} (t, f) \text{ iff } s \sim_{\mathbb{A}} t \text{ and } (M, s) \models R_{\mathbb{A}}^{\text{Evt}}(e, f) \text{ and } (M, t) \models R_{\mathbb{A}}^{\text{Evt}}(e, f);
relation Z between W and $W^{\text{EL-O}}$:

$$
\begin{aligned}
Z = & \{ \langle R_{a(PubForget(p))}^{\text{EL-O}}(s), (s, n) \rangle \} \cup \\
    & \{ \langle R_{a(PubForget(p))}^{\text{EL-O}}(s) \cup \{p\}, (s, e^+) \rangle \} \cup \\
    & \{ \langle R_{a(PubForget(p))}^{\text{EL-O}}(s) \setminus \{p\}, (s, e^-) \rangle \}
\end{aligned}
$$

1025 It can be checked that Z is indeed a bisimulation. □

Something that cannot be modelled in our framework is the public announcement that $\neg K_i p$, or, expressed in the EL-O fragment, that $\neg (p \wedge S_i p)$. The reason is that it is not clear how the disjunctive effect of that announcement could be described in terms of an add-list.

### 8.1.4. From EL-O action descriptions to DEL event models

We now consider the converse direction: given an EL-O action description a, can we find a DEL event model (Evt, E) such that for any state $s \in W^{\text{EL-O}}$, the product $(M^{\text{EL-O}} \otimes \text{Evt}, (s, e))$ of $(M^{\text{EL-O}}$, $s$) and $(\text{Evt}, E)$ is defined iff $s \models \text{pre}(a)$, and such that in that case, $(M^{\text{EL-O}} \otimes \text{Evt}, (s, e))$ and $(M^{\text{EL-O}}$, $s'$) are bisimilar, where $s'$ is the state such that $sR_a^{\text{EL-O}}s'$?

Let us here restrict our attention to a few very basic EL-O action descriptions in which there is a single conditional effect either adding or deleting one atom. The idea behind the construction of an equivalent event model is the following: when adding or deleting an atom from a world, only agents who see this atom know that it has been modified.

The easiest way to translate this into DEL event models is through the use of Bolander's *edge-conditioned event models* [62, 63]. Such models incorporate conditions on accessibility relations, so that a model is a tuple Evt = ⟨W<sup>Evt</sup>, R<sub>Λ</sub><sup>Evt</sup>, {R<sub>i</sub><sup>Evt</sup>}<sub>i∈Λ</sub>, pre<sup>Evt</sup>, post<sup>Evt</sup>⟩ where R<sub>Λ</sub><sup>Evt</sup> : W<sup>Evt</sup> × W<sup>Evt</sup> → L<sub>EL</sub>, R<sub>i</sub><sup>Evt</sup> : W<sup>Evt</sup> × W<sup>Evt</sup> → L<sub>EL</sub> for every i ∈ Λ, and the rest is defined as previously. The product of such an edge-conditioned event model with a model M = ⟨W, ~<sub>Λ</sub>, {~<sub>i</sub>}<sub>i∈Λ</sub>, V⟩ is M ⊗ Evt = ⟨W', ~'<sub>Λ</sub>, {~'<sub>i</sub>}<sub>i∈Λ</sub>, V'⟩ where

* (s, e) ~'<sub>Λ</sub> (t, f) iff s ~<sub>Λ</sub> t and (M, s) ⊨ R<sub>Λ</sub><sup>Evt</sup>(e, f) and (M, t) ⊨ R<sub>Λ</sub><sup>Evt</sup>(e, f);
<figure><img src="image_8.png" /><figcaption>Figure 8: An event model equivalent to $\langle \tau, \{(\tau, \{p\}, \emptyset)\} \rangle$.</figcaption></figure>

• $(s, e) \sim'_{i} (t, f)$ iff $s \sim_{i} t$ and $(M, s) \models R_{i}^{\text{Evt}}(e, f)$ and $(M, t) \models R_{i}^{\text{Evt}}(e, f)$, for every $i \in A$;

and the rest is defined as previously. As mentioned in [63], edge-conditioned event models can be simulated by standard event models, though the former are more succinct.

We now give a few examples of DEL event model translations of such simple action descriptions. We will only give the bisimulation relations without the proofs that they are indeed bisimulations, as those proofs are tedious but uncomplicated.

An equivalent event model to the assignment of $p$ to true, $\langle \tau, \{(\tau, \{p\}, \emptyset) \} \rangle$, is given in Figure 8. The bisimulation relation $Z$ is as follows: for every state $s \in W^{\text{EL-O}}$, $sZ(s, a)$ and $(s \cup \{p\})Z(s, b)$. If we wish to assign $p$ to false rather than true (action $\langle \tau, \{(\tau, \emptyset, \{p\}) \} \rangle$), we simply replace the assignment $p \leftarrow \tau$ in the actual event by $p \leftarrow \bot$, and change the bisimulation relation so that $(s \setminus \{p\})Z(s, b)$ for any $s \in W^{\text{EL-O}}$. This action can be interpreted as the value of $p$ (the property of an object) changing, while only agents who are looking at this object can see the change.

For the action $\langle \tau, \{(\tau, \{S_i \alpha\}, \emptyset) \} \rangle$ making $S_i \alpha$ true, we need in the general case two actual events, one for when $\alpha$ is true and one for when it is false. An event model equivalent to this action description is given in Figure 9. The corresponding bisimulation $Z$ is the following: for every state $s \in W^{\text{EL-O}}$,

• $sZ(s, a)$;

• $(s \cup \{S_i \alpha\})Z(s, b)$ if $s \models \alpha$;

• $(s \cup \{S_i \alpha\})Z(s, c)$ if $s \models \neg \alpha$.
<figure><img src="image_9.png" /><figcaption>Figure 8: An event model equivalent to $\langle \tau, \{(\tau, \{p\}, \emptyset)\} \rangle$.</figcaption></figure>

• $(s, e) \sim'_{i} (t, f)$ iff $s \sim_i t$ and $(M, s) \models R_i^{\text{Evt}}(e, f)$ and $(M, t) \models R_i^{\text{Evt}}(e, f)$, for every $i \in A$;

and the rest is defined as previously. As mentioned in [63], edge-conditioned event models can be simulated by standard event models, though the former are more succinct.

We now give a few examples of DEL event model translations of such simple action descriptions. We will only give the bisimulation relations without the proofs that they are indeed bisimulations, as those proofs are tedious but uncomplicated.

An equivalent event model to the assignment of $p$ to true, $\langle \tau, \{(\tau, \{p\}, \emptyset) \} \rangle$, is given in Figure 8. The bisimulation relation $Z$ is as follows: for every state $s \in W^{\text{EL-O}}$, $sZ(s, a)$ and $(s \cup \{p\})Z(s, b)$. If we wish to assign $p$ to false rather than true (action $\langle \tau, \{(\tau, \emptyset, \{p\}) \} \rangle$), we simply replace the assignment $p \leftarrow \tau$ in the actual event by $p \leftarrow \bot$, and change the bisimulation relation so that $(s \setminus \{p\})Z(s, b)$ for any $s \in W^{\text{EL-O}}$. This action can be interpreted as the value of $p$ (the property of an object) changing, while only agents who are looking at this object can see the change.

For the action $\langle \tau, \{(\tau, \{S_i \alpha\}, \emptyset) \} \rangle$ making $S_i \alpha$ true, we need in the general case two actual events, one for when $\alpha$ is true and one for when it is false. An event model equivalent to this action description is given in Figure 9. The corresponding bisimulation $Z$ is the following: for every state $s \in W^{\text{EL-O}}$,

• $sZ(s, a)$;

• $(s \cup \{S_i \alpha\})Z(s, b)$ if $s \models \alpha$;

• $(s \cup \{S_i \alpha\})Z(s, c)$ if $s \models \neg \alpha$.
<figure><img src="image_9.png" /><figcaption>Figure 9: An event model equivalent to $\langle \tau, \{\langle \tau, \{S_i \alpha\}, \emptyset\rangle\} \rangle$.</figcaption></figure>

A more complex example, given in Figure 10, is that of an event model equivalent to an action making the atom $S_i p$ false. This can be interpreted as agent $i$ looking away from $p$. Agents who saw agent $i$ looking at $p$ will see her look away, and the other agents will not be aware of this change. While this is a fairly natural action to consider, it is difficult to generalize to assigning $S_i \alpha$ to false for any given $\alpha$, as only propositional variables can receive assignments in DEL event models. The bisimulation Z in the case of Figure 10 is as follows: for every state $s \in W^{\text{EL-O}}$,

* $sZ(s, a);$

* $(s \setminus \{JS p, S_i p\})Z(s, b);$

* $(s \setminus \{JS p, S_i p, p\})Z(s, c) \text{ if } s \models p;$

* $((s \cup \{p\}) \setminus \{JS p, S_i p\})Z(s, c) \text{ if } s \models \neg p;$

* $(s \setminus \{p\})Z(s, d) \text{ if } s \models p;$

* $(s \cup \{p\})Z(s, d) \text{ if } s \models \neg p.$

Let us give one more example, this time involving a precondition: private announcements. In an S5 setting, an announcement can only be private if no one is watching (as we cannot represent agents “believing that nothing has happened”). That is, we can only privately announce whether
<figure><img src="image_10.png" /><figcaption>Figure 9: An event model equivalent to $\langle \tau, \{\langle \tau, \{S_i \alpha\}, \emptyset\rangle\} \rangle$.</figcaption></figure>

A more complex example, given in Figure 10, is that of an event model equivalent to an action making the atom $S_i p$ false. This can be interpreted as agent $i$ looking away from $p$. Agents who saw agent $i$ looking at $p$ will see her look away, and the other agents will not be aware of this change. While this is a fairly natural action to consider, it is difficult to generalize to assigning $S_i \alpha$ to false for any given $\alpha$, as only propositional variables can receive assignments in DEL event models. The bisimulation Z in the case of Figure 10 is as follows: for every state $s \in W^{\text{EL-O}}$,

* $sZ(s, a);$

* $(s \setminus \{JS p, S_i p\})Z(s, b);$

* $(s \setminus \{JS p, S_i p, p\})Z(s, c) \text{ if } s \models p;$

* $((s \cup \{p\}) \setminus \{JS p, S_i p\})Z(s, c) \text{ if } s \models \neg p;$

* $(s \setminus \{p\})Z(s, d) \text{ if } s \models p;$

* $(s \cup \{p\})Z(s, d) \text{ if } s \models \neg p.$

Let us give one more example, this time involving a precondition: private announcements. In an S5 setting, an announcement can only be private if no one is watching (as we cannot represent agents “believing that nothing has happened”). That is, we can only privately announce whether
<figure><img src="image_10.png" /><figcaption>Figure 10: An event model equivalent to $\langle \tau, \{\langle \tau, \emptyset, \{S_i p\}\rangle\} \rangle$.</figcaption></figure>

<figure><img src="image_11.png" /><figcaption>Figure 11: An event model equivalent to the private announcement whether $\alpha$ to $i$.</figcaption></figure>

$\alpha$ is true to an agent $i$ if for all $j \neq i$, $\neg S_j S_i \alpha$ holds. The corresponding action description has condition $\bigwedge_{j \neq i} \neg S_j S_i \alpha$ and a single conditional effect $\langle \tau, \{S_i \alpha\}, \emptyset \rangle$. The corresponding event model is given in Figure 11. The bisimulation $Z$ is: for every state $s \in W^{\text{EL-O}}$, $sZ(s, a)$, and $(s \cup S_i \alpha)Z(s, e)$ if $s \models \text{pre}^{\text{Evt}}(e)$ for $e \in \{b, b', c, c'\}$.

We stop here without delving into the territory of deleting longer atoms or combining several effects. It is, we hope, fairly obvious that given an action description, the construction of an equivalent DEL event model is neither straightforward nor systematic. This, we believe, is an argument in favour of our framework, in which many actions can be defined very succinctly and in a natural manner.

### 8.1.5. Discussion: DEL vs. EL-O

The comparison with DEL leads us to a fundamental question: how should an action be described? All the approaches in the literature advo-
<figure><img src="image_11.png" /><figcaption>Figure 10: An event model equivalent to $\langle \tau, \{\langle \tau, \emptyset, \{S_i p\}\rangle\} \rangle$.</figcaption></figure>

<figure><img src="image_12.png" /><figcaption>Figure 11: An event model equivalent to the private announcement whether $\alpha$ to $i$.</figcaption></figure>

$\alpha$ is true to an agent $i$ if for all $j \neq i$, $\neg S_j S_i \alpha$ holds. The corresponding action description has condition $\bigwedge_{j \neq i} \neg S_j S_i \alpha$ and a single conditional effect $\langle \tau, \{S_i \alpha\}, \emptyset \rangle$. The corresponding event model is given in Figure 11. The bisimulation Z is: for every state $s \in W^{\text{EL-O}}$, $sZ(s, a)$, and $(s \cup S_i \alpha)Z(s, e)$ if $s \models \text{pre}^{\text{Evt}}(e)$ for $e \in \{b, b', c, c'\}$.

We stop here without delving into the territory of deleting longer atoms or combining several effects. It is, we hope, fairly obvious that given an action description, the construction of an equivalent DEL event model is neither straightforward nor systematic. This, we believe, is an argument in favour of our framework, in which many actions can be defined very succinctly and in a natural manner.

### 8.1.5. Discussion: DEL vs. EL-O

The comparison with DEL leads us to a fundamental question: how should an action be described? All the approaches in the literature advo-
1105

cating DEL for epistemic planning presuppose that event models provide an
appropriate tool for the description of actions. This, however, seems ques-
tionable to us. For example, how should we describe the action of pushing
a light button? It is useful for our discussion to recall the fundamental dis-
tinction in philosophy of action between *action types* and *action tokens* [64].
Pushing a light button is an example of the former, while an example of the
latter is the pushing of a particular button at a particular point in time by
a particular agent. The elements of the set of action descriptions *Act* are
clearly action types. In contrast, the elements of the execution of a solution
to a planning task are typically action tokens.<fnref n="9" />

1110

1115

Let us suppose that the action type of pushing a light button can be de-
scribed by means of preconditions and effects. Reasonably, the precondition
is that the agent is close to the switch<fnref n="10" /> and the effect is that the light is on.
However, a DEL event model has to contain more information than that:
it also has to say how the button-pushing is perceived (or not) by each of
the agents. Now remember that we have to describe an action type: we
have to account for all possible circumstances of button pushing. For each
agent there are at least two cases: the one where the agent is present and
observes the light bulb and the one where she is absent. Altogether, this re-
quires an exponential numbers of points in an event model. Worse, we also
have to take care of the evolution of the agents' higher-order knowledge:
for each couple of observing agents *i* and *j* we have to distinguish whether *i*
sees that *j* observes the bulb, and so on, the limit case being when there is
joint observation of the bulb. So exhaustive action descriptions by means of
DEL event models systematically have to have an infinite number of points
in order to take all the possible effects into account! This can actually be

1120

1125

1130

<footnote n="9">⁹In DEL-based planning this distinction is clarified for the first time in [65].</footnote>

<footnote n="10">¹⁰There might be more, such as that the wires leading to the light bulb are working, that the light bulb is not broken etc.: we here neglect the qualification problem [66] which is that the precondition is typically an infinite conjunction.</footnote>
1105

cating DEL for epistemic planning presuppose that event models provide an
appropriate tool for the description of actions. This, however, seems ques-
tionable to us. For example, how should we describe the action of pushing
a light button? It is useful for our discussion to recall the fundamental dis-
tinction in philosophy of action between *action types* and *action tokens* [64].
Pushing a light button is an example of the former, while an example of the
latter is the pushing of a particular button at a particular point in time by
a particular agent. The elements of the set of action descriptions *Act* are
clearly action types. In contrast, the elements of the execution of a solution
to a planning task are typically action tokens.<fnref n="9" />

1110

1115

Let us suppose that the action type of pushing a light button can be de-
scribed by means of preconditions and effects. Reasonably, the precondition
is that the agent is close to the switch<fnref n="10" /> and the effect is that the light is on.
However, a DEL event model has to contain more information than that:
it also has to say how the button-pushing is perceived (or not) by each of
the agents. Now remember that we have to describe an action type: we
have to account for all possible circumstances of button pushing. For each
agent there are at least two cases: the one where the agent is present and
observes the light bulb and the one where she is absent. Altogether, this re-
quires an exponential numbers of points in an event model. Worse, we also
have to take care of the evolution of the agents' higher-order knowledge:
for each couple of observing agents *i* and *j* we have to distinguish whether *i*
sees that *j* observes the bulb, and so on, the limit case being when there is
joint observation of the bulb. So exhaustive action descriptions by means of
DEL event models systematically have to have an infinite number of points
in order to take all the possible effects into account! This can actually be

1120

1125

1130

<footnote n="9">⁹In DEL-based planning this distinction is clarified for the first time in [65].</footnote>

<footnote n="10">¹⁰There might be more, such as that the wires leading to the light bulb are working, that the light bulb is not broken etc.: we here neglect the qualification problem [66] which is that the precondition is typically an infinite conjunction.</footnote>
seen as an epistemic version of the ramification problem [66].

Contrasting with DEL event models, our EL-O-based action descriptions do not require to fully describe all possible ramifications: the direct effect of pushing the light button is simply that the light is on, and the indirect epis-temic effects follow from the description of the state, namely who observes the light bulb and who doesn't. This is a fundamentally different answer to the question of how actions should be described. It makes the modeller's task much simpler and more natural. (A similar argument was first put forward in [67].)

1135

1140

1145

1150

To sum it up, we believe that our action descriptions are a more nat-
ural way of modelling action types... at least when this can be done. For
example, the public announcement of the disjunction $p \lor q$ (the event model
PubAnn($p \lor q$)) or the assignment of $q$ to $p$ (the event model Assign($p, q$)) can-
not be captured. This is because all propositional variables are independent
in our approach, as witnessed by the fact that the knowledge operator dis-
tributes over disjunctions of literals: for different $p$ and $q$, $K_i(p \lor q)$ is equiv-
alent to $K_i p \lor K_i q$, and $K_i(p \leftrightarrow q)$ is equivalent to $(K_i p \land K_i q) \lor (K_i \neg p \land K_i \neg q)$.
This is clearly a limitation of our approach. In particular, we cannot cap-
ture the muddy children problem, in which the children learn that one of
them has a muddy forehead without knowing who. Note that while DEL is
more general as far as preconditions are concerned (any complex formula
can be announced), its postconditions are restricted: they assign proposi-
tional variables and therefore cannot model actions with disjunctive ontic
effects such as $p \lor q$.

1155

1160

For the same reason we cannot capture the poisonous liquid example
from [45]. In this problem there is a bottle of liquid, a healthy lawn, and two
actions: pour and senseLawn. The first is the action of pouring some liquid
on the lawn that we have already described in Example 8 (Section 5.3). The
second senses whether or not the lawn is dead: we have pre(senseLawn) = ⊤
and eff(senseLawn) = {⟨⊤, {Sᵢ Dead}, ∅⟩}. Then for the set of actions Act =
{pour, senseLawn}, there is no solution of the planning task
seen as an epistemic version of the ramification problem [66].

Contrasting with DEL event models, our EL-O-based action descriptions do not require to fully describe all possible ramifications: the direct effect of pushing the light button is simply that the light is on, and the indirect epis-temic effects follow from the description of the state, namely who observes the light bulb and who doesn't. This is a fundamentally different answer to the question of how actions should be described. It makes the modeller's task much simpler and more natural. (A similar argument was first put forward in [67].)

1135

1140

1145

1150

1155

1160

To sum it up, we believe that our action descriptions are a more nat-
ural way of modelling action types... at least when this can be done. For
example, the public announcement of the disjunction $p \lor q$ (the event model
PubAnn($p \lor q$)) or the assignment of $q$ to $p$ (the event model Assign($p, q$)) can-
not be captured. This is because all propositional variables are independent
in our approach, as witnessed by the fact that the knowledge operator dis-
tributes over disjunctions of literals: for different $p$ and $q$, $K_i(p \lor q)$ is equiv-
alent to $K_i p \lor K_i q$, and $K_i(p \leftrightarrow q)$ is equivalent to $(K_i p \land K_i q) \lor (K_i \neg p \land K_i \neg q)$.
This is clearly a limitation of our approach. In particular, we cannot cap-
ture the muddy children problem, in which the children learn that one of
them has a muddy forehead without knowing who. Note that while DEL is
more general as far as preconditions are concerned (any complex formula
can be announced), its postconditions are restricted: they assign proposi-
tional variables and therefore cannot model actions with disjunctive ontic
effects such as $p \lor q$.

For the same reason we cannot capture the poisonous liquid example
from [45]. In this problem there is a bottle of liquid, a healthy lawn, and two
actions: pour and senseLawn. The first is the action of pouring some liquid
on the lawn that we have already described in Example 8 (Section 5.3). The
second senses whether or not the lawn is dead: we have pre(senseLawn) = ⊤
and eff(senseLawn) = {⟨⊤, {Sᵢ Dead}, ∅⟩}. Then for the set of actions Act =
{pour, senseLawn}, there is no solution of the planning task
⟨OA, *Act*, {Dead, $S_i$ Dead}, $S_i$ Poisonous⟩.

In particular, pouring some liquid on the lawn and checking whether the lawn is dead does not inform the agent whether Poisonous is the case. This is because after pouring the liquid the agent should know that the state of the lawn is tied to the toxicity of the liquid. Such knowledge cannot be captured in our framework.

1165

An interesting avenue for future research are implicitly coordinated plans as introduce by Bolander et al. [59]. For example, suppose agent 2 would like to borrow the apartment of his friend 1 while 1 is away on vacation. Agent 1 has an action `putMat` of putting the key under the door mat that is described by `pre(putMat) = ⊤` and `eff(putMat) = {⟨⊤, {Mat}, ∅⟩};` agent 2 has an action `tryTake` of trying to take the key with `pre(tryTake) = ⊤` and `eff(tryTake) = {⟨⊤, {$S_2$ Mat}, ∅⟩, ⟨Mat, {hasKey$_2$}, ∅⟩}`. The initial state is $s_0 = ∅$. Then 1 putting the key under the mat and 2 taking the key solves the planning task

1170

1175

⟨OA, *Act*, $s_0$, `hasKey$_2$`⟩.

However, when 2 arrives at the apartment he will not know that the key is under the mat, unless 1 has told him. A better plan, baptised 'implicitly coordinated' in [59], involves 1's action `infoMat` which can be described in EL-O terms by `pre(infoMat) = ⊤` and `eff(tryTake) = {⟨⊤, {$S_2$ Mat}, ∅⟩}`. The formal characterisation of such plans requires a language with action operators in which one can describe solutions in the language as sequences of actions, prefixing each action of agent *i* by $K_i$: it is not enough that the action leads to the goal, the acting agent must also know that. This fails to be the case for 2's action `tryTake`: as 2 does not know whether the key is under the mat, he does not know whether the conditional effect $⟨Mat, \{hasKey_2\}, \emptyset⟩$ will be triggered. The extension of EL-O with dynamic modal operators, DEL-PAO, has such operators and should therefore enable reasoning about implicitly coordinated plans. The details however remain to be worked out.

1180

1185

1190
⟨OA, *Act*, {Dead, $S_i$ Dead}, $S_i$ Poisonous⟩.

In particular, pouring some liquid on the lawn and checking whether the lawn is dead does not inform the agent whether Poisonous is the case. This is because after pouring the liquid the agent should know that the state of the lawn is tied to the toxicity of the liquid. Such knowledge cannot be captured in our framework.

1165

An interesting avenue for future research are implicitly coordinated plans as introduce by Bolander et al. [59]. For example, suppose agent 2 would like to borrow the apartment of his friend 1 while 1 is away on vacation. Agent 1 has an action `putMat` of putting the key under the door mat that is described by `pre(putMat) = ⊤` and `eff(putMat) = {⟨⊤, {Mat}, ∅⟩};` agent 2 has an action `tryTake` of trying to take the key with `pre(tryTake) = ⊤` and `eff(tryTake) = {⟨⊤, {$S_2$ Mat}, ∅⟩, ⟨Mat, {hasKey$_2$}, ∅⟩}`. The initial state is $s_0 = ∅$. Then 1 putting the key under the mat and 2 taking the key solves the planning task

1170

1175

⟨OA, *Act*, $s_0$, `hasKey$_2$`⟩.

However, when 2 arrives at the apartment he will not know that the key is under the mat, unless 1 has told him. A better plan, baptised 'implicitly coordinated' in [59], involves 1's action `infoMat` which can be described in EL-O terms by `pre(infoMat) = ⊤` and `eff(tryTake) = {⟨⊤, {$S_2$ Mat}, ∅⟩}`. The formal characterisation of such plans requires a language with action operators in which one can describe solutions in the language as sequences of actions, prefixing each action of agent *i* by $K_i$: it is not enough that the action leads to the goal, the acting agent must also know that. This fails to be the case for 2's action `tryTake`: as 2 does not know whether the key is under the mat, he does not know whether the conditional effect $⟨Mat, \{hasKey_2\}, \emptyset⟩$ will be triggered. The extension of EL-O with dynamic modal operators, DEL-PAO, has such operators and should therefore enable reasoning about implicitly coordinated plans. The details however remain to be worked out.

1180

1185

1190
<figure><img src="image_12.png" /><figcaption>Figure 12: Models M (left) and M' (right); reflexive arrows omitted.</figcaption></figure>

## 8.2. Muise et al.

Muise et al. [25] follow a strategy that is very similar to ours where they restrict formulas to boolean combinations of epistemic literals: sequences of belief operators and negations that are followed by a propositional variable; in other terms, formulas of $\mathcal{L}_{EL}$ without conjunctions and disjunctions. So their grammar of epistemic literals is:

$$ \lambda ::= p | \neg \lambda | K_i \lambda $$

where $p$ ranges over $\mathbb{P}$ and $i$ over $\mathbb{A}$. Muise et al.'s proper epistemic knowledge bases (PEKBs) are conjunctions of such epistemic literals [25]. The authors have also started to consider the integration of 'knowing-whether' operators in [68], but have not integrated this into the planning formalism of [25].

The major advantage of our EL-O-based approach over the epistemic literals-based approach is that boolean combinations of epistemic literals cannot express $K_i(K_j p \lor K_j \neg p) \land \neg K_i p \land \neg K_i \neg p$ is true, that is, $i$ knows that $j$ knows whether $p$ while $i$ does not know about $p$ herself. As we had argued in Section 2, such situations are important in interaction and more specifically in communication. They can be expressed in our framework by $\mathcal{L}_{bool}(OA)$ formulas of the form $S_i S_j p \land \neg S_i p$. To prove this formally it suffices to show that $K_i(K_j p \lor K_j \neg p)$ cannot be expressed by boolean combinations of epistemic literals.
<figure><img src="image_13.png" /><figcaption>Figure 12: Models M (left) and M' (right); reflexive arrows omitted.</figcaption></figure>

## 8.2. Muise et al.

Muise et al. [25] follow a strategy that is very similar to ours where they restrict formulas to boolean combinations of epistemic literals: sequences of belief operators and negations that are followed by a propositional variable; in other terms, formulas of $\mathcal{L}_{EL}$ without conjunctions and disjunctions. So their grammar of epistemic literals is:

$$ \lambda ::= p | \neg \lambda | K_i \lambda $$

where p ranges over $\mathbb{P}$ and i over $\mathbb{A}$. Muise et al.'s proper epistemic knowledge bases (PEKBs) are conjunctions of such epistemic literals [25]. The authors have also started to consider the integration of 'knowing-whether' operators in [68], but have not integrated this into the planning formalism of [25].

The major advantage of our EL-O-based approach over the epistemic literals-based approach is that boolean combinations of epistemic literals cannot express $K_i(K_j p \lor K_j \neg p) \land \neg K_i p \land \neg K_i \neg p$ is true, that is, i knows that j knows whether p while i does not know about p herself. As we had argued in Section 2, such situations are important in interaction and more specifically in communication. They can be expressed in our framework by $\mathcal{L}_{bool}(OA)$ formulas of the form $S_i S_j p \land \neg S_i p$. To prove this formally it suffices to show that $K_i(K_j p \lor K_j \neg p)$ cannot be expressed by boolean combinations of epistemic literals.
**Proposition 16.** Let $i$ and $j$ be different. Then there is no boolean combination of epistemic literals $\varphi$ that is equivalent to $K_i(K_j p \lor K_j \neg p)$ in S5 Kripke models.

*Proof.* Consider the two S5 Kripke models $M = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$ and $M' = \langle W', \sim'_{A}, \{\sim'_i\}_{i \in A}, V' \rangle$ with

$$W = \{w_0, w_1\},$$

$$\sim_A = W \times W = \sim_i,$$

$$\sim_j = \delta_W,$$

$$W' = \{w_0, w_1, w_2, w_3\},$$

$$\sim'_{A} = W' \times W' = \sim'_{i},$$

$$\sim'_{j} = \delta_{W'} \cup \{\langle w_2, w_3 \rangle, \langle w_3, w_2 \rangle\},$$

$$V(w_0) = \emptyset \text{ and } V(w_1) = \{p\};$$

$$V'(w_0) = V'(w_3) = \emptyset \text{ and } V'(w_1) = V'(w_2) = \{p\};$$

where $\delta_W = \{\langle w_0, w_0 \rangle, \langle w_1, w_1 \rangle\}$ is the identity relation of $W$ and $\delta_{W'}$ is the identity relation of $W'$. They are depicted in Figure 12. Clearly, $M, w_0 \models K_i(K_j p \lor K_j \neg p)$ and $M', w_0 \not\models K_i(K_j p \lor K_j \neg p)$. We prove that no boolean combinations of epistemic literals can tell the pointed models $(M, w_0)$ and $(M', w_0)$ apart. From that it immediately follows that there can be no such boolean combination that is equivalent to $K_i(K_j p \lor K_j \neg p)$.

1210

To establish that of $(M, w_0)$ and $(M', w_0)$ satisfy the same formulas as far as the language of boolean combinations of epistemic literals is concerned it suffices to prove that $M, w_0 \models \lambda$ iff $M', w_0 \models \lambda$ for every epistemic literal $\lambda$. We use induction on the length of $\lambda$. We have to check the following exhaustive list of cases; each of them is straightforward.

1215

**Case 1.** $\lambda = q$ for some $q \in \mathbb{P}$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$, regardless whether $q$ equals $p$ or not.)

1220

**Case 2.** $\lambda = \neg\mu$, for some epistemic literal $\mu$. Straightforward application of the induction hypothesis.

**Case 3.** $\lambda = K_i\mu$. We have the following subcases.

1225

**Case 3.1.** $\lambda = K_i q$ for some $q \in \mathbb{P}$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

**Case 3.2.** $\lambda = K_i \neg\mu$, for some epistemic literal $\mu$. We have to dive deeper into the subcases here.

**Case 3.2.1.** $\lambda = K_i \neg q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)
**Proposition 16.** Let $i$ and $j$ be different. Then there is no boolean combination of epistemic literals $\varphi$ that is equivalent to $K_i(K_j p \lor K_j \neg p)$ in S5 Kripke models.

*Proof.* Consider the two S5 Kripke models $M = \langle W, \sim_A, \{\sim_i\}_{i \in A}, V \rangle$ and $M' = \langle W', \sim'_{A}, \{\sim'_i\}_{i \in A}, V' \rangle$ with

$$ 
\begin{array}{l@{\qquad}l}
W = \{w_0, w_1\}, & W' = \{w_0, w_1, w_2, w_3\}, \\
\sim_A = W \times W = \sim_i, & \sim'_{A} = W' \times W' = \sim'_i, \\
\sim_j = \delta_W, & \sim'_j = \delta_{W'} \cup \{\langle w_2, w_3 \rangle, \langle w_3, w_2 \rangle\}, \\
V(w_0) = \emptyset \text{ and } V(w_1) = \{p\}; & V'(w_0) = V'(w_3) = \emptyset \text{ and } V'(w_1) = V'(w_2) = \{p\};
\end{array}
$$

where $\delta_W = \{\langle w_0, w_0 \rangle, \langle w_1, w_1 \rangle\}$ is the identity relation of $W$ and $\delta_{W'}$ is the identity relation of $W'$. They are depicted in Figure 12. Clearly, $M, w_0 \models K_i(K_j p \lor K_j \neg p)$ and $M', w_0 \not\models K_i(K_j p \lor K_j \neg p)$. We prove that no boolean combinations of epistemic literals can tell the pointed models $(M, w_0)$ and $(M', w_0)$ apart. From that it immediately follows that there can be no such boolean combination that is equivalent to $K_i(K_j p \lor K_j \neg p)$.

1210

1215

To establish that of $(M, w_0)$ and $(M', w_0)$ satisfy the same formulas as far as the language of boolean combinations of epistemic literals is concerned it suffices to prove that $M, w_0 \models \lambda$ iff $M', w_0 \models \lambda$ for every epistemic literal $\lambda$. We use induction on the length of $\lambda$. We have to check the following exhaustive list of cases; each of them is straightforward.

1220

**Case 1.** $\lambda = q$ for some $q \in \mathbb{P}$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$, regardless whether $q$ equals $p$ or not.)

**Case 2.** $\lambda = \neg\mu$, for some epistemic literal $\mu$. Straightforward application of the induction hypothesis.

**Case 3.** $\lambda = K_i\mu$. We have the following subcases.

1225

**Case 3.1.** $\lambda = K_i q$ for some $q \in \mathbb{P}$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

**Case 3.2.** $\lambda = K_i \neg\mu$, for some epistemic literal $\mu$. We have to dive deeper into the subcases here.

**Case 3.2.1.** $\lambda = K_i \neg q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)
1230

**Case 3.2.2.** $\lambda = K_i \neg \neg \mu$. We use that $\lambda \leftrightarrow K_i \mu$ is valid and apply the induction hypothesis.

**Case 3.2.3.** $\lambda = K_i \neg K_i \mu$. We use that $K_i \neg K_i \mu$ and $\neg K_i \mu$ are equivalent in S5 and apply the induction hypothesis.

**Case 3.2.4.** $\lambda = K_i \neg K_j \mu$. We do yet another case analysis.

**Case 3.2.4.1.** $\lambda = K_i \neg K_j q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

1235

**Case 3.2.4.2.** $\lambda = K_i \neg K_j \neg \mu$. This is the last case analysis we have to do:

**Case 3.2.4.2.1.** $\lambda = K_i \neg K_j \neg q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

1240

**Case 3.2.4.2.2.** $\lambda = K_i \neg K_j \neg \neg \mu$. We use that $\lambda \leftrightarrow K_i \neg K_j \mu$ is valid and apply the induction hypothesis.

**Case 3.2.4.2.3.** $\lambda = K_i \neg K_j \neg K_i \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 3.2.4.2.4.** $\lambda = K_i \neg K_j \neg K_j \mu$. We use that $K_i \neg K_j \neg K_j \mu$ and $K_i K_j \mu$ are equivalent in S5 and apply the induction hypothesis.

1245

**Case 3.2.4.3.** $\lambda = K_i \neg K_j K_i \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 3.2.4.4.** $\lambda = K_i \neg K_j K_i \mu$. We use that $K_i \neg K_j K_i \mu$ and $K_i \neg K_j \mu$ are equivalent in S5 and apply the induction hypothesis.

**Case 3.3.** $\lambda = K_i K_i \mu$. We use that $K_i K_i \mu$ and $K_i \mu$ are equivalent in S5 and apply the induction hypothesis.

1250

**Case 3.4.** $\lambda = K_i K_j \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 4.** $\lambda = K_j \mu$. We have $M, w_0 \models \lambda \leftrightarrow \mu$ and $M', w_0 \models \lambda \leftrightarrow \mu$, allowing us to apply the induction hypothesis. $\square$

## 8.3. Kominis and Geffner

1255

Kominis and Geffner's approach [53, 69] distinguishes three kinds of actions: physical actions modifying the world, public updates (that are nothing but DEL-like public announcements), and sensing actions by means of which an agent learns whether a formula is true or not.
1230

**Case 3.2.2.** $\lambda = K_i \neg \neg \mu$. We use that $\lambda \leftrightarrow K_i \mu$ is valid and apply the induction hypothesis.

**Case 3.2.3.** $\lambda = K_i \neg K_i \mu$. We use that $K_i \neg K_i \mu$ and $\neg K_i \mu$ are equivalent in S5 and apply the induction hypothesis.

**Case 3.2.4.** $\lambda = K_i \neg K_j \mu$. We do yet another case analysis.

**Case 3.2.4.1.** $\lambda = K_i \neg K_j q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

1235

**Case 3.2.4.2.** $\lambda = K_i \neg K_j \neg \mu$. This is the last case analysis we have to do:

**Case 3.2.4.2.1.** $\lambda = K_i \neg K_j \neg q$. Obvious. ($M, w_0 \not\models \lambda$ and $M', w_0 \not\models \lambda$.)

1240

**Case 3.2.4.2.2.** $\lambda = K_i \neg K_j \neg \neg \mu$. We use that $\lambda \leftrightarrow K_i \neg K_j \mu$ is valid and apply the induction hypothesis.

**Case 3.2.4.2.3.** $\lambda = K_i \neg K_j \neg K_i \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 3.2.4.2.4.** $\lambda = K_i \neg K_j \neg K_j \mu$. We use that $K_i \neg K_j \neg K_j \mu$ and $K_i K_j \mu$ are equivalent in S5 and apply the induction hypothesis.

1245

**Case 3.2.4.3.** $\lambda = K_i \neg K_j K_i \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 3.2.4.4.** $\lambda = K_i \neg K_j K_j \mu$. We use that $K_i \neg K_j K_j \mu$ and $K_i \neg K_j \mu$ are equivalent in S5 and apply the induction hypothesis.

**Case 3.3.** $\lambda = K_i K_i \mu$. We use that $K_i K_i \mu$ and $K_i \mu$ are equivalent in S5 and apply the induction hypothesis.

1250

**Case 3.4.** $\lambda = K_i K_j \mu$. We have $M, w_0 \models \lambda \leftrightarrow K_i \mu$ and $M', w_0 \models \lambda \leftrightarrow K_i \mu$, allowing us to apply the induction hypothesis.

**Case 4.** $\lambda = K_j \mu$. We have $M, w_0 \models \lambda \leftrightarrow \mu$ and $M', w_0 \models \lambda \leftrightarrow \mu$, allowing us to apply the induction hypothesis. $\square$

## 8.3. Kominis and Geffner

1255

Kominis and Geffner's approach [53, 69] distinguishes three kinds of actions: physical actions modifying the world, public updates (that are nothing but DEL-like public announcements), and sensing actions by means of which an agent learns whether a formula is true or not.
1260

1265

1270

1275

1280

1285

On the one hand, their approach is more general than ours because agents can sense arbitrary formulas. This allows them to model the muddy children problem, which we cannot express as a simple epistemic planning task (see Section 8.1.5). However, if we restrict the formulas describing the set of initially possible states, the formulas that are publicly announced, and the formulas that are sensed to observability atoms (more precisely: to the equivalent $\mathcal{L}_{EL}$ formulas) then everything that can be modelled in Kominis and Geffner's approach can also be in ours.

On the other hand, Kominis and Geffner's approach imposes three severe restrictions:

* all actions can be split up in one of the three categories;

* the set of initially possible states is common knowledge among all agents;

* all physical actions and all public updates are public;

* all sensing actions are semi-private.

The first hypothesis is clearly too strong for many natural everyday situations, as we have already said in Section 4.2 (Remark 5). The second hypothesis is also very strong: it forbids the modelling of private actions modifying the world as required in several of our examples of Section 6. The third hypothesis means that when an agent $i$ senses the truth value of $\varphi$ then all other agents see this: they learn that $i$ knows whether $\varphi$ is true or not but ignore whether what $i$ has learned is $\varphi$ or $\neg\varphi$. This means that there can be no private communication; in particular, one cannot model what we take to be a paradigmatic epistemic planning task, viz. the gossip problem.

## 8.4. Petrick and Bacchus

There is also an older approach due to Petrick and Bacchus about planning under incomplete information for a single agent [70, 45] which bears some similarities to ours. Their language is first-order but does not have
1260

1265

1270

1275

1280

1285

On the one hand, their approach is more general than ours because agents can sense arbitrary formulas. This allows them to model the muddy children problem, which we cannot express as a simple epistemic planning task (see Section 8.1.5). However, if we restrict the formulas describing the set of initially possible states, the formulas that are publicly announced, and the formulas that are sensed to observability atoms (more precisely: to the equivalent $\mathcal{L}_{EL}$ formulas) then everything that can be modelled in Kominis and Geffner's approach can also be in ours.

On the other hand, Kominis and Geffner's approach imposes three severe restrictions:

* all actions can be split up in one of the three categories;

* the set of initially possible states is common knowledge among all agents;

* all physical actions and all public updates are public;

* all sensing actions are semi-private.

The first hypothesis is clearly too strong for many natural everyday situations, as we have already said in Section 4.2 (Remark 5). The second hypothesis is also very strong: it forbids the modelling of private actions modifying the world as required in several of our examples of Section 6. The third hypothesis means that when an agent *i* senses the truth value of $\varphi$ then all other agents see this: they learn that *i* knows whether $\varphi$ is true or not but ignore whether what *i* has learned is $\varphi$ or $\neg\varphi$. This means that there can be no private communication; in particular, one cannot model what we take to be a paradigmatic epistemic planning task, viz. the gossip problem.

## 8.4. Petrick and Bacchus

There is also an older approach due to Petrick and Bacchus about planning under incomplete information for a single agent [70, 45] which bears some similarities to ours. Their language is first-order but does not have
epistemic operators. Instead, there are several kinds of knowledge bases by means of which the epistemic status of pieces of information is represented. In particular, there is a 'knowing-that' database whose elements are literals and a 'knowing-whether' database whose elements are atoms. The point of view is subjective, while ours is objective, i.e., the agent's knowledge is represented, but not what is true in the world. Therefore the identity of $K_i p$ and $p \wedge K_i f_p$ cannot be expressed in their language. Just as the original proposal in [70], our approach does not account for postdiction (deducing the past from the present), as illustrated by Example 8. This is because in our approach the knowledge operator distributes over disjunctions of literals. This limitation of our approach is also the reason why we cannot account for the muddy children problem: the latter requires actions where the children learn a disjunction, namely that one of them is dirty. A solution to the muddy children problem where public announcements were integrated into DEL-PAO was presented in [7]; however, in that paper only the semantics was designed, without an axiomatisation or complexity result. The study of such mathematical properties will be subject of future work.

## 9. Conclusion

We have made a first step towards realistic multi-agent epistemic planning. Our approach is based on observability atoms, which, we argue, are more appropriate than epistemic literals as previously proposed in the literature. We have also argued that observability atoms provide a simple, finite way to represent situations of maximal ignorance, namely by states that equal the empty set, while such situations require infinite Kripke models in standard epistemic logic (cf. Remark 5 in Section 4.2 and Remark 6 in Section 6.1).

We have shown that goals and conditions of our action descriptions can be reduced to boolean formulas, which has allowed us to encode epistemic planning into classical planning. As our reduction is polynomial, we main-
epistemic operators. Instead, there are several kinds of knowledge bases by means of which the epistemic status of pieces of information is represented. In particular, there is a 'knowing-that' database whose elements are literals and a 'knowing-whether' database whose elements are atoms. The point of view is subjective, while ours is objective, i.e., the agent's knowledge is represented, but not what is true in the world. Therefore the identity of $K_i p$ and $p \wedge K_i f_p$ cannot be expressed in their language. Just as the original proposal in [70], our approach does not account for postdiction (deducing the past from the present), as illustrated by Example 8. This is because in our approach the knowledge operator distributes over disjunctions of literals. This limitation of our approach is also the reason why we cannot account for the muddy children problem: the latter requires actions where the children learn a disjunction, namely that one of them is dirty. A solution to the muddy children problem where public announcements were integrated into DEL-PAO was presented in [7]; however, in that paper only the semantics was designed, without an axiomatisation or complexity result. The study of such mathematical properties will be subject of future work.

## 9. Conclusion

We have made a first step towards realistic multi-agent epistemic planning. Our approach is based on observability atoms, which, we argue, are more appropriate than epistemic literals as previously proposed in the literature. We have also argued that observability atoms provide a simple, finite way to represent situations of maximal ignorance, namely by states that equal the empty set, while such situations require infinite Kripke models in standard epistemic logic (cf. Remark 5 in Section 4.2 and Remark 6 in Section 6.1).

We have shown that goals and conditions of our action descriptions can be reduced to boolean formulas, which has allowed us to encode epistemic planning into classical planning. As our reduction is polynomial, we main-
1315

tain the PSPACE complexity of classical planning. Building on this we have encoded epistemic action descriptions into PDDL and performed some experiments with a PDDL planner in order to find plans efficiently. Moreover, our use of a logic of knowledge together with a state of the art automated planner—which we assume to be correct in the case of classical planning with conditional effects—provides a method for producing plans that are guaranteed to be correct. We have illustrated our approach with several examples, most importantly the generalised gossip problem, which, we argue, is an interesting candidate for a paradigmatic epistemic planning task.

1320

Alternatively we could encode epistemic planning tasks into Answer-Set Programming (ASP). An encoding of several variants of the generalised gossip problem together with an experimental evaluation that fares better than our encoding can be found in [71].

1325

An extension of our approach to parallel planning was recently proposed in [49], based on the account of non-epistemic parallel planning of [72].

1330

The decidability of EL-O-based epistemic planning contrasts with the undecidability of DEL-based epistemic planning, which is the case even for simple fragments. For example, if actions also change the world (and not only the agents' knowledge), then plan existence is undecidable whenever epistemic operators are allowed in preconditions; if actions are purely epistemic, then it is undecidable whenever two agents are involved or the epistemic depth exceeds 2 [16]. We have nevertheless shown that several simple kinds of event models can be captured by our action descriptions (Section 8.1). Moreover and as we have explained there, there is a fundamental difference between the modelling of actions by means of DEL event models on the one hand and by means of action descriptions on the other: in an EL-O-based modelling, the agents' observational abilities are part of the state, while they are part of the action description in a DEL-based modelling. We have argued that our approach is more natural and that DEL-based approaches face an epistemic version of the ramification problem.

1335

1340

As we have said in Remark 2, it is not obvious how EL-O's operator of

1345
1315

tain the PSPACE complexity of classical planning. Building on this we have encoded epistemic action descriptions into PDDL and performed some experiments with a PDDL planner in order to find plans efficiently. Moreover, our use of a logic of knowledge together with a state of the art automated planner—which we assume to be correct in the case of classical planning with conditional effects—provides a method for producing plans that are guaranteed to be correct. We have illustrated our approach with several examples, most importantly the generalised gossip problem, which, we argue, is an interesting candidate for a paradigmatic epistemic planning task.

1320

Alternatively we could encode epistemic planning tasks into Answer-Set Programming (ASP). An encoding of several variants of the generalised gossip problem together with an experimental evaluation that fares better than our encoding can be found in [71].

1325

An extension of our approach to parallel planning was recently proposed in [49], based on the account of non-epistemic parallel planning of [72].

1330

The decidability of EL-O-based epistemic planning contrasts with the undecidability of DEL-based epistemic planning, which is the case even for simple fragments. For example, if actions also change the world (and not only the agents' knowledge), then plan existence is undecidable whenever epistemic operators are allowed in preconditions; if actions are purely epistemic, then it is undecidable whenever two agents are involved or the epistemic depth exceeds 2 [16]. We have nevertheless shown that several simple kinds of event models can be captured by our action descriptions (Section 8.1). Moreover and as we have explained there, there is a fundamental difference between the modelling of actions by means of DEL event models on the one hand and by means of action descriptions on the other: in an EL-O-based modelling, the agents' observational abilities are part of the state, while they are part of the action description in a DEL-based modelling. We have argued that our approach is more natural and that DEL-based approaches face an epistemic version of the ramification problem.

1335

1340

As we have said in Remark 2, it is not obvious how EL-O's operator of

1345
joint observability of the grand coalition A should be generalised to joint
observability of arbitrary groups. We would like to address this issue in
future work.

In this paper we have assumed a centralised approach in which a single
planner decides the actions of all agents. Other approaches have studied
the classical gossip problem from a completely different perspective, as-
suming that all agents are autonomous [5, 73, 74]. An interesting research
avenue is to study generalised gossiping as a distributed planning task.

## Acknowledgements

We would like to thank the reviewers who did an excellent job in spotting
problematic points and suggesting improvements. Thanks are also due to
Julien Vianey who ran the experiments on which we report in Section 7.

This research was partially funded by TAILOR, a project funded by EU
Horizon 2020 research and innovation programme under GA No 952215, as
well as by ANITI, funded by the French program "Investing for the Future
– PIA3" under Grant agreement no ANR-19-PI3A-0004.

## References

[1] S. Khuller, Y. A. Kim, Y. J. Wan, On generalized gossiping and broadcasting (extended abstract), in: G. Di Battista, U. Zwick (Eds.), Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, Vol. 2832 of Lecture Notes in Computer Science, Springer, 2003, pp. 373–384.

[2] D. Liben-Nowell, Gossip is synteny: Incomplete gossip and the syntenic distance between genomes, J. Algorithms 43 (2) (2002) 264–283.

[3] S. M. Hedetniemi, S. T. Hedetniemi, A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks 18 (4) (1988) 319–349. doi:10.1002/net.3230180406.
joint observability of the grand coalition A should be generalised to joint
observability of arbitrary groups. We would like to address this issue in
future work.

In this paper we have assumed a centralised approach in which a single
planner decides the actions of all agents. Other approaches have studied
the classical gossip problem from a completely different perspective, as-
suming that all agents are autonomous [5, 73, 74]. An interesting research
avenue is to study generalised gossiping as a distributed planning task.

## Acknowledgements

We would like to thank the reviewers who did an excellent job in spotting
problematic points and suggesting improvements. Thanks are also due to
Julien Vianey who ran the experiments on which we report in Section 7.

This research was partially funded by TAILOR, a project funded by EU
Horizon 2020 research and innovation programme under GA No 952215, as
well as by ANITI, funded by the French program "Investing for the Future
– PIA3" under Grant agreement no ANR-19-PI3A-0004.

## References

[1] S. Khuller, Y. A. Kim, Y. J. Wan, On generalized gossiping and broadcasting (extended abstract), in: G. Di Battista, U. Zwick (Eds.), Algorithms - ESA 2003, 11th Annual European Symposium, Budapest, Hungary, September 16-19, 2003, Proceedings, Vol. 2832 of Lecture Notes in Computer Science, Springer, 2003, pp. 373–384.

[2] D. Liben-Nowell, Gossip is synteny: Incomplete gossip and the syntenic distance between genomes, J. Algorithms 43 (2) (2002) 264–283.

[3] S. M. Hedetniemi, S. T. Hedetniemi, A. L. Liestman, A survey of gossiping and broadcasting in communication networks, Networks 18 (4) (1988) 319–349. doi:10.1002/net.3230180406.
1375

[4] M. C. Cooper, A. Herzig, F. Maffre, F. Maris, P. Régnier, The epistemic
gossip problem, Discrete Mathematics 342 (3) (2019) 654–663.
URL https://doi.org/10.1016/j.disc.2018.10.041

[5] M. Attamah, H. van Ditmarsch, D. Grossi, W. van der Hoek, Knowl-edge and gossip, in: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), 2014, pp. 21–26.

1380

[6] A. Herzig, E. Lorini, F. Maffre, A poor man's epistemic logic based on propositional assignment and higher-order observation, in: W. van der Hoek, W. H. Holliday, W.-f. Wang (Eds.), Proceedings of the 5th International Conference on Logic, Rationality and Interaction (LORI 2015), Springer Verlag, 2015, pp. 156–168.
URL http://www.irit.fr/~Andreas.Herzig/P/Lori15.html

1385

[7] T. Charrier, A. Herzig, E. Lorini, F. Maffre, F. Schwarzentruber, Build-ing epistemic logic from observations and public announcements, in: C. Baral, J. P. Delgrande, F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth Interna-tional Conference, KR 2016, Cape Town, South Africa, April 25-29, 2016, AAAI Press, 2016, pp. 268–277.
URL http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12899

1390

[8] A. Herzig, E. Lorini, F. Maffre, F. Schwarzentruber, Epistemic boolean
games based on a logic of visibility and control, in: S. Kambhampati
(Ed.), Proceedings of the Twenty-Fifth International Joint Conference
on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July
2016, IJCAI/AAAI Press, 2016, pp. 1116–1122.
URL http://www.ijcai.org/Abstract/16/162

1395

[9] F. Maffre, Ignorance is bliss: observability-based dynamic epistemic logics and their applications. (le bonheur est dans l'ignorance : logiques épistémiques dynamiques basées sur l'observabilité et leurs

1400
1375

[4] M. C. Cooper, A. Herzig, F. Maffre, F. Maris, P. Régnier, The epistemic
gossip problem, Discrete Mathematics 342 (3) (2019) 654–663.
URL https://doi.org/10.1016/j.disc.2018.10.041

[5] M. Attamah, H. van Ditmarsch, D. Grossi, W. van der Hoek, Knowl-edge and gossip, in: Proceedings of the 21st European Conference on Artificial Intelligence (ECAI 2014), 2014, pp. 21–26.

1380

[6] A. Herzig, E. Lorini, F. Maffre, A poor man's epistemic logic based on propositional assignment and higher-order observation, in: W. van der Hoek, W. H. Holliday, W.-f. Wang (Eds.), Proceedings of the 5th International Conference on Logic, Rationality and Interaction (LORI 2015), Springer Verlag, 2015, pp. 156–168.
URL http://www.irit.fr/~Andreas.Herzig/P/Lori15.html

1385

[7] T. Charrier, A. Herzig, E. Lorini, F. Maffre, F. Schwarzentruber, Build-ing epistemic logic from observations and public announcements, in: C. Baral, J. P. Delgrande, F. Wolter (Eds.), Principles of Knowledge Representation and Reasoning: Proceedings of the Fifteenth Interna-tional Conference, KR 2016, Cape Town, South Africa, April 25-29, 2016, AAAI Press, 2016, pp. 268–277.
URL http://www.aaai.org/ocs/index.php/KR/KR16/paper/view/12899

1390

[8] A. Herzig, E. Lorini, F. Maffre, F. Schwarzentruber, Epistemic boolean
games based on a logic of visibility and control, in: S. Kambhampati
(Ed.), Proceedings of the Twenty-Fifth International Joint Conference
on Artificial Intelligence, IJCAI 2016, New York, NY, USA, 9-15 July
2016, IJCAI/AAAI Press, 2016, pp. 1116–1122.
URL http://www.ijcai.org/Abstract/16/162

1395

[9] F. Maffre, Ignorance is bliss: observability-based dynamic epistemic logics and their applications. (le bonheur est dans l'ignorance : logiques épistémiques dynamiques basées sur l'observabilité et leurs

1400
applications), Ph.D. thesis, Paul Sabatier University, Toulouse, France
(2016).

URL https://tel.archives-ouvertes.fr/tel-01488408

1405

[10] M. C. Cooper, A. Herzig, F. Maffre, F. Maris, P. Régnier, A simple account of multi-agent epistemic planning, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 193–201.

1410

[11] J. Hintikka, Knowledge and Belief: An Introduction to the Logic of the Two Notions, Cornell University Press, 1962.

[12] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about Knowledge, MIT Press, 1995.

1415

[13] J. Y. Halpern, Y. Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence 54 (3) (1992) 319–379.

[14] T. Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence 69 (1994) 165–204. doi:10.1016/0004-3702(94)90081-7.

1420

[15] T. Bolander, M. B. Andersen, Epistemic planning for single and multi-agent systems, Journal of Applied Non-Classical Logics 21 (1) (2011) 9–34.

URL http://www.tandfonline.com/doi/abs/10.3166/jancl.21.9-34

1425

[16] G. Aucher, T. Bolander, Undecidability in epistemic planning, in: F. Rossi (Ed.), Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), AAAI Press, 2013, pp. 27–33.

[17] T. Bolander, M. H. Jensen, F. Schwarzentruber, Complexity results in epistemic planning, in: Q. Yang, M. Wooldridge (Eds.), Proceedings of
applications), Ph.D. thesis, Paul Sabatier University, Toulouse, France
(2016).

URL https://tel.archives-ouvertes.fr/tel-01488408

1405

[10] M. C. Cooper, A. Herzig, F. Maffre, F. Maris, P. Régnier, A simple account of multi-agent epistemic planning, in: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI 2016), 2016, pp. 193–201.

1410

[11] J. Hintikka, Knowledge and Belief: An Introduction to the Logic of the Two Notions, Cornell University Press, 1962.

[12] R. Fagin, J. Y. Halpern, Y. Moses, M. Y. Vardi, Reasoning about Knowledge, MIT Press, 1995.

1415

[13] J. Y. Halpern, Y. Moses, A guide to completeness and complexity for modal logics of knowledge and belief, Artificial Intelligence 54 (3) (1992) 319–379.

[14] T. Bylander, The computational complexity of propositional STRIPS planning, Artificial Intelligence 69 (1994) 165–204. doi:10.1016/0004-3702(94)90081-7.

1420

[15] T. Bolander, M. B. Andersen, Epistemic planning for single and multi-agent systems, Journal of Applied Non-Classical Logics 21 (1) (2011) 9–34.
URL http://www.tandfonline.com/doi/abs/10.3166/jancl.21.9-34

1425

[16] G. Aucher, T. Bolander, Undecidability in epistemic planning, in: F. Rossi (Ed.), Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI 2013), AAAI Press, 2013, pp. 27–33.

[17] T. Bolander, M. H. Jensen, F. Schwarzentruber, Complexity results in epistemic planning, in: Q. Yang, M. Wooldridge (Eds.), Proceedings of
1430

the Twenty-Fourth International Joint Conference on Artificial Intel-
ligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, AAAI
Press, 2015, pp. 2791–2797.

URL http://ijcai.org/Abstract/15/395

1435

[18] S. L. Cong, S. Pinchinat, F. Schwarzentruber, Small undecidable prob- lems in epistemic planning, in: J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelli- gence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, ijcai.org, 2018, pp. 4780–4786.

URL https://doi.org/10.24963/ijcai.2018/664

1440

[19] T. Bolander, T. Charrier, S. Pinchinat, F. Schwarzentruber, Del-based epistemic planning: Decidability and complexity, Artif. Intell. 287 (2020) 103304. doi:10.1016/j.artint.2020.103304.

URL https://doi.org/10.1016/j.artint.2020.103304

1445

[20] R. Demolombe, M. del Pilar Pozos Parra, A simple and tractable exten-
sion of situation calculus to epistemic logic, in: Z. W. Ras, S. Ohsuga
(Eds.), Foundations of Intelligent Systems, 12th International Sympo-
sium, ISMIS 2000, Charlotte, NC, USA, October 11-14, 2000, Proceed-
ings, Vol. 1932 of Lecture Notes in Computer Science, Springer, 2000,
pp. 515–524.

URL https://doi.org/10.1007/3-540-39963-1_54

1450

[21] T. C. Son, C. Baral, Formalizing sensing actions A transition function based approach, Artif. Intell. 125 (1-2) (2001) 19–91.

URL https://doi.org/10.1016/S0004-3702(00)00080-1

1455

[22] M. Steedman, R. P. Petrick, Planning dialog actions, in: Proceedings of the 8th SIGDIAL Workshop on Discourse and Dialogue (SIGdial 2007), 2007, pp. 265–272.

[23] G. Lakemeyer, Y. Lespérance, Efficient reasoning in multiagent epis-
temic logics, in: L. D. Raedt, C. Bessière, D. Dubois, P. Doherty, P. Fras-
1430

the Twenty-Fourth International Joint Conference on Artificial Intel-
ligence, IJCAI 2015, Buenos Aires, Argentina, July 25-31, 2015, AAAI
Press, 2015, pp. 2791–2797.

URL http://ijcai.org/Abstract/15/395

1435

[18] S. L. Cong, S. Pinchinat, F. Schwarzentruber, Small undecidable problems in epistemic planning, in: J. Lang (Ed.), Proceedings of the Twenty-Seventh International Joint Conference on Artificial Intelligence, IJCAI 2018, July 13-19, 2018, Stockholm, Sweden, ijcai.org, 2018, pp. 4780–4786.

URL https://doi.org/10.24963/ijcai.2018/664

1440

[19] T. Bolander, T. Charrier, S. Pinchinat, F. Schwarzentruber, Del-based epistemic planning: Decidability and complexity, Artif. Intell. 287 (2020) 103304. doi:10.1016/j.artint.2020.103304.

URL https://doi.org/10.1016/j.artint.2020.103304

1445

[20] R. Demolombe, M. del Pilar Pozos Parra, A simple and tractable extension of situation calculus to epistemic logic, in: Z. W. Ras, S. Ohsuga (Eds.), Foundations of Intelligent Systems, 12th International Symposium, ISMIS 2000, Charlotte, NC, USA, October 11-14, 2000, Proceedings, Vol. 1932 of Lecture Notes in Computer Science, Springer, 2000, pp. 515–524.

URL https://doi.org/10.1007/3-540-39963-1_54

1450

[21] T. C. Son, C. Baral, Formalizing sensing actions A transition function based approach, Artif. Intell. 125 (1-2) (2001) 19–91.

URL https://doi.org/10.1016/S0004-3702(00)00080-1

1455

[22] M. Steedman, R. P. Petrick, Planning dialog actions, in: Proceedings of the 8th SIGDIAL Workshop on Discourse and Dialogue (SIGdial 2007), 2007, pp. 265–272.

[23] G. Lakemeyer, Y. Lespérance, Efficient reasoning in multiagent epis-
temic logics, in: L. D. Raedt, C. Bessière, D. Dubois, P. Doherty, P. Fras-
1460

coni, F. Heintz, P. J. F. Lucas (Eds.), ECAI 2012 - 20th European Con-
ference on Artificial Intelligence. Including Prestigious Applications
of Artificial Intelligence (PAIS-2012) System Demonstrations Track,
Montpellier, France, August 27-31, 2012, Vol. 242 of Frontiers in Ar-
tificial Intelligence and Applications, IOS Press, 2012, pp. 498–503.

URL https://doi.org/10.3233/978-1-61499-098-7-498

1465

[24] H. Palacios, H. Geffner, Compiling uncertainty away: Solving confor-
mant planning problems using a classical planner (sometimes), in:
Proceedings, The Twenty-First National Conference on Artificial In-
telligence and the Eighteenth Innovative Applications of Artificial In-
telligence Conference, July 16-20, 2006, Boston, Massachusetts, USA,
AAAI Press, 2006, pp. 900–905.

1470

URL http://www.aaai.org/Library/AAAI/2006/aaai06-142.php

1475

[25] C. Muise, V. Belle, P. Felli, S. A. McIlraith, T. Miller, A. R. Pearce, L. Sonenberg, Planning over multi-agent epistemic states: A classical planning approach, in: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), AAAI Press, 2015, pp. 3327–3334.

[26] J. Fan, Y. Wang, H. van Ditmarsch, Contingency and knowing
whether, Rew. Symb. Logic 8 (1) (2015) 75–107.

URL https://doi.org/10.1017/S1755020314000343

1480

[27] K. Su, A. Sattar, X. Luo, Model checking temporal logics of knowledge
via OBDDs, The Computer Journal 50 (4) (2007) 403–420.

[28] W. van der Hoek, P. Iliev, M. Wooldridge, A logic of revelation and con-
cealment, in: W. van der Hoek, L. Padgham, V. Conitzer, M. Winikoff
(Eds.), Proceedings of the 11th International Conference on Au-
tonomous Agents and Multiagent Systems (AAMAS 2012), IFAAMAS,
2012, pp. 1115–1122.

1485

URL http://dl.acm.org/citation.cfm?id=2343856
1460

coni, F. Heintz, P. J. F. Lucas (Eds.), ECAI 2012 - 20th European Con-
ference on Artificial Intelligence. Including Prestigious Applications
of Artificial Intelligence (PAIS-2012) System Demonstrations Track,
Montpellier, France, August 27-31, 2012, Vol. 242 of Frontiers in Ar-
tificial Intelligence and Applications, IOS Press, 2012, pp. 498–503.

URL https://doi.org/10.3233/978-1-61499-098-7-498

1465

[24] H. Palacios, H. Geffner, Compiling uncertainty away: Solving confor-
mant planning problems using a classical planner (sometimes), in:
Proceedings, The Twenty-First National Conference on Artificial In-
telligence and the Eighteenth Innovative Applications of Artificial In-
telligence Conference, July 16-20, 2006, Boston, Massachusetts, USA,
AAAI Press, 2006, pp. 900–905.

1470

URL http://www.aaai.org/Library/AAAI/2006/aaai06-142.php

1475

[25] C. Muise, V. Belle, P. Felli, S. A. McIlraith, T. Miller, A. R. Pearce, L. Sonenberg, Planning over multi-agent epistemic states: A classical planning approach, in: Proceedings of the 29th AAAI Conference on Artificial Intelligence (AAAI 2015), AAAI Press, 2015, pp. 3327–3334.

[26] J. Fan, Y. Wang, H. van Ditmarsch, Contingency and knowing
whether, Rew. Symb. Logic 8 (1) (2015) 75–107.

URL https://doi.org/10.1017/S1755020314000343

1480

[27] K. Su, A. Sattar, X. Luo, Model checking temporal logics of knowledge
via OBDDs, The Computer Journal 50 (4) (2007) 403–420.

[28] W. van der Hoek, P. Iliev, M. Wooldridge, A logic of revelation and con-
cealment, in: W. van der Hoek, L. Padgham, V. Conitzer, M. Winikoff
(Eds.), Proceedings of the 11th International Conference on Au-
tonomous Agents and Multiagent Systems (AAMAS 2012), IFAAMAS,
2012, pp. 1115–1122.

1485

URL http://dl.acm.org/citation.cfm?id=2343856
[29] J. van Benthem, J. van Eijck, M. Gattinger, K. Su, Symbolic model checking for dynamic epistemic logic - S5 and beyond, J. Log. Comput. 28 (2) (2018) 367–402.

URL https://doi.org/10.1093/logcom/exx038

1490

[30] W. Lenzen, Recent work in epistemic logic, North Holland Publishing Company, Amsterdam, 1978.

[31] W. Lenzen, On the semantics and pragmatics of epistemic attitudes, in: A. Laux, H. Wansing (Eds.), Knowledge and belief in philosophy and AI, Akademie Verlag, Berlin, 1995, pp. 181–197.

1495

[32] W. H. Holliday, Epistemic logic and epistemology, in: Introduction to Formal Philosophy, Springer, 2018, pp. 351–369.

[33] M. Cooper, A. Herzig, F. Maffre, F. Maris, E. Perrotin, P. Regnier, When ‘knowing whether’ is better than ‘knowing that’, in: 13èmes Journées d’Intelligence Artificielle Fondamentale (JIAF 2019), hal-02302984, 2019.

1500

[34] A. Herzig, E. Perrotin, On the axiomatisation of common knowledge, in: Proceedings of the 13th conference on Advances in Modal Logic (AiML 2012), College Publications, 2020.

[35] P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2001.

1505

[36] A. Herzig, F. Maffre, How to share knowledge by gossiping, in: Proceedings of the 3rd International Conference on Agreement Technologies (AT 2015), Springer-Verlag, 2016, pp. 249–263.

[37] M. R. Genesereth, N. J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann Publishers, 1989.

1510

[38] M. Baldoni, L. Giordano, A. Martelli, A modal extension of logic programming: Modularity, beliefs and hypothetical reasoning, J. Log.
[29] J. van Benthem, J. van Eijck, M. Gattinger, K. Su, Symbolic model checking for dynamic epistemic logic - S5 and beyond, J. Log. Comput. 28 (2) (2018) 367–402.

URL https://doi.org/10.1093/logcom/exx038

1490

[30] W. Lenzen, Recent work in epistemic logic, North Holland Publishing Company, Amsterdam, 1978.

[31] W. Lenzen, On the semantics and pragmatics of epistemic attitudes, in: A. Laux, H. Wansing (Eds.), Knowledge and belief in philosophy and AI, Akademie Verlag, Berlin, 1995, pp. 181–197.

1495

[32] W. H. Holliday, Epistemic logic and epistemology, in: Introduction to Formal Philosophy, Springer, 2018, pp. 351–369.

[33] M. Cooper, A. Herzig, F. Maffre, F. Maris, E. Perrotin, P. Regnier, When ‘knowing whether’ is better than ‘knowing that’, in: 13èmes Journées d’Intelligence Artificielle Fondamentale (JIAF 2019), hal-02302984, 2019.

1500

[34] A. Herzig, E. Perrotin, On the axiomatisation of common knowledge, in: Proceedings of the 13th conference on Advances in Modal Logic (AiML 2012), College Publications, 2020.

[35] P. Blackburn, M. de Rijke, Y. Venema, Modal Logic, Cambridge Tracts in Theoretical Computer Science, Cambridge University Press, 2001.

1505

[36] A. Herzig, F. Maffre, How to share knowledge by gossiping, in: Proceedings of the 3rd International Conference on Agreement Technologies (AT 2015), Springer-Verlag, 2016, pp. 249–263.

[37] M. R. Genesereth, N. J. Nilsson, Logical Foundations of Artificial Intelligence, Morgan Kaufmann Publishers, 1989.

1510

[38] M. Baldoni, L. Giordano, A. Martelli, A modal extension of logic programming: Modularity, beliefs and hypothetical reasoning, J. Log.
1515

Comput. 8 (5) (1998) 597-635. doi:10.1093/logcom/8.5.597.

URL https://doi.org/10.1093/logcom/8.5.597

[39] M. Baldoni, Normal multimodal logics: Automatic deduction and logic programming extension, Ph.D. thesis, Università degli Studi di Torino, Dipartimento di Informatica (1998).

1520

[40] E. Lorini, A. Herzig, Direct and indirect common belief, in: A. Konzelmann Ziv, H. B. Schmid (Eds.), Institutions, Emotions, and Group Agents: Contributions to Social Ontology, Springer, 2014, pp. 355-372.

[41] A. Herzig, Logics of knowledge and action: critical analysis and challenges, Auton. Agents Multi Agent Syst. 29 (5) (2015) 719-753.
URL https://doi.org/10.1007/s10458-014-9267-z

1525

[42] S. N. Artemov, Observable models, in: S. N. Artemov, A. Nerode (Eds.), Logical Foundations of Computer Science - International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4-7, 2020, Proceedings, Vol. 11972 of Lecture Notes in Computer Science, Springer, 2020, pp. 12-26.
URL https://doi.org/10.1007/978-3-030-36755-8_2

1530

[43] A. Herzig, E. Lorini, F. Maffre, Possible worlds semantics based on observation and communication, in: H. van Ditmarsch, G. Sandu (Eds.), Jaakko Hintikka on Knowledge and Game-Theoretical Semantics, Springer International Publishing, Cham, 2018, pp. 339-362.
URL https://doi.org/10.1007/978-3-319-62864-6_14

1535

[44] H. Geffner, B. Bonet, A Concise Introduction to Models and Methods for Automated Planning, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2013.

[45] R. P. A. Petrick, F. Bacchus, Extending the knowledge-based approach to planning with incomplete information and sensing, in: D. Dubois,

1540
1515

Comput. 8 (5) (1998) 597-635. doi:10.1093/logcom/8.5.597.

URL https://doi.org/10.1093/logcom/8.5.597

[39] M. Baldoni, Normal multimodal logics: Automatic deduction and logic programming extension, Ph.D. thesis, Università degli Studi di Torino, Dipartimento di Informatica (1998).

1520

[40] E. Lorini, A. Herzig, Direct and indirect common belief, in: A. Konzelmann Ziv, H. B. Schmid (Eds.), Institutions, Emotions, and Group Agents: Contributions to Social Ontology, Springer, 2014, pp. 355-372.

[41] A. Herzig, Logics of knowledge and action: critical analysis and challenges, Auton. Agents Multi Agent Syst. 29 (5) (2015) 719-753.
URL https://doi.org/10.1007/s10458-014-9267-z

1525

[42] S. N. Artemov, Observable models, in: S. N. Artemov, A. Nerode (Eds.), Logical Foundations of Computer Science - International Symposium, LFCS 2020, Deerfield Beach, FL, USA, January 4-7, 2020, Proceedings, Vol. 11972 of Lecture Notes in Computer Science, Springer, 2020, pp. 12-26.
URL https://doi.org/10.1007/978-3-030-36755-8_2

1530

[43] A. Herzig, E. Lorini, F. Maffre, Possible worlds semantics based on observation and communication, in: H. van Ditmarsch, G. Sandu (Eds.), Jaakko Hintikka on Knowledge and Game-Theoretical Semantics, Springer International Publishing, Cham, 2018, pp. 339-362.
URL https://doi.org/10.1007/978-3-319-62864-6_14

1535

[44] H. Geffner, B. Bonet, A Concise Introduction to Models and Methods for Automated Planning, Synthesis Lectures on Artificial Intelligence and Machine Learning, Morgan & Claypool Publishers, 2013.

[45] R. P. A. Petrick, F. Bacchus, Extending the knowledge-based approach to planning with incomplete information and sensing, in: D. Dubois,

1540
C. A. Welty, M. Williams (Eds.), Principles of Knowledge Representa-
tion and Reasoning: Proceedings of the Ninth International Confer-
ence (KR2004), Whistler, Canada, June 2-5, 2004, AAAI Press, 2004,
pp. 613–622.

URL http://www.aaai.org/Library/KR/2004/kr04-064.php

1545

[46] B. Baker, R. Shostak, Gossips and telephones, Discrete Mathematics 2 (3) (1972) 191–193. doi:10.1016/0012-365X(72)90001-5.

[47] R. Tijdeman, On a telephone problem, Nieuw Archief voor Wiskunde 19 (3) (1971) 188–192.

1550

[48] A. Hajnal, E. C. B. Milner, E. Szemerédi, A cure for the telephone disease, Canadian Mathematical Bulletin 15 (3) (1972) 447–450.

[49] M. Cooper, A. Herzig, F. Maris, E. Perrotin, J. Vianey, Lightweight Parallel Multi-Agent Epistemic Planning, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, 2020, pp. 274–283.

1555

URL https://doi.org/10.24963/kr.2020/28

[50] E. A. Akkoyunlu, K. Ekanadham, R. V. Hubert, Some constraints and tradeoffs in the design of network communications, in: Proceedings of the 5th ACM Symposium on Operating Systems Principles (SOSP 1975), ACM Press, 1975, pp. 67–74.

1560

[51] J. Gray, Notes on data base operating systems, in: Operating Systems, An Advanced Course, Springer-Verlag, 1978, pp. 393–481.

[52] L. Lamport, R. Shostak, M. Pease, The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4 (3) (1982) 382–401.

1565

[53] F. Kominis, H. Geffner, Beliefs in multiagent planning: From one agent to many, in: R. I. Brafman, C. Domshlak, P. Haslum, S. Zilberstein (Eds.), Proceedings of the Twenty-Fifth International Conference
C. A. Welty, M. Williams (Eds.), Principles of Knowledge Representa-
tion and Reasoning: Proceedings of the Ninth International Confer-
ence (KR2004), Whistler, Canada, June 2-5, 2004, AAAI Press, 2004,
pp. 613–622.

URL http://www.aaai.org/Library/KR/2004/kr04-064.php

1545

[46] B. Baker, R. Shostak, Gossips and telephones, Discrete Mathematics 2 (3) (1972) 191–193. doi:10.1016/0012-365X(72)90001-5.

[47] R. Tijdeman, On a telephone problem, Nieuw Archief voor Wiskunde 19 (3) (1971) 188–192.

1550

[48] A. Hajnal, E. C. B. Milner, E. Szemerédi, A cure for the telephone disease, Canadian Mathematical Bulletin 15 (3) (1972) 447–450.

[49] M. Cooper, A. Herzig, F. Maris, E. Perrotin, J. Vianey, Lightweight Parallel Multi-Agent Epistemic Planning, in: Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning, 2020, pp. 274–283.

1555

URL https://doi.org/10.24963/kr.2020/28

[50] E. A. Akkoyunlu, K. Ekanadham, R. V. Hubert, Some constraints and tradeoffs in the design of network communications, in: Proceedings of the 5th ACM Symposium on Operating Systems Principles (SOSP 1975), ACM Press, 1975, pp. 67–74.

1560

[51] J. Gray, Notes on data base operating systems, in: Operating Systems, An Advanced Course, Springer-Verlag, 1978, pp. 393–481.

[52] L. Lamport, R. Shostak, M. Pease, The Byzantine generals problem, ACM Transactions on Programming Languages and Systems 4 (3) (1982) 382–401.

1565

[53] F. Kominis, H. Geffner, Beliefs in multiagent planning: From one agent to many, in: R. I. Brafman, C. Domshlak, P. Haslum, S. Zilberstein (Eds.), Proceedings of the Twenty-Fifth International Conference
1570

on Automated Planning and Scheduling, ICAPS 2015, Jerusalem, Israel, June 7-11, 2015, AAAI Press, 2015, pp. 147-155.

URL http://www.aaai.org/ocs/index.php/ICAPS/ICAPS15/paper/view/10617

[54] D. Lewis (Ed.), Convention: A Philosophical Study, Harvard University Press, 1969.

1575

[55] M. C. Cooper, A. Herzig, F. Maris, J. Vianey, Temporal epistemic gossip problems, in: M. Slavkovik (Ed.), Multi-Agent Systems - 16th European Conference, EUMAS 2018, Bergen, Norway, December 6-7, 2018, Revised Selected Papers, Vol. 11450 of Lecture Notes in Computer Science, Springer, 2018, pp. 1-14. doi:10.1007/978-3-030-14174-5_1

1580

URL https://doi.org/10.1007/978-3-030-14174-5_1

[56] D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, D. Wilkins, PDDL - The Planning Domain Definition Language, Tech. rep., Yale Center for Computational Vision and Control (1998).

1585

[57] G. Röger, F. Pommerening, J. Seipp, Fast downward stone soup 2014, in: Eighth International Planning Competition (IPC-8): planner abstracts, 2014, pp. 28-31.

[58] M. Martinez, I. Moraru, S. Edelkamp, S. Franco, Planning-PDBs planer in the IPC 2018, IPC-9 planner abstracts (2018) 63-66.

1590

[59] T. Bolander, T. Engesser, R. Mattmüller, B. Nebel, Better eager than lazy? How agent types impact the successfulness of implicit coordination, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, 2018, pp. 445-453.

1595

URL https://aaai.org/ocs/index.php/KR/KR18/paper/view/18070
1570

on Automated Planning and Scheduling, ICAPS 2015, Jerusalem,
Israel, June 7-11, 2015, AAAI Press, 2015, pp. 147–155.

URL http://www.aaai.org/ocs/index.php/ICAPS/ICAPS15/
paper/view/10617

1575

[54] D. Lewis (Ed.), Convention: A Philosophical Study, Harvard University Press, 1969.

1580

[55] M. C. Cooper, A. Herzig, F. Maris, J. Vianey, Temporal epistemic
gossip problems, in: M. Slavkovik (Ed.), Multi-Agent Systems -
16th European Conference, EUMAS 2018, Bergen, Norway, Decem-
ber 6-7, 2018, Revised Selected Papers, Vol. 11450 of Lecture Notes
in Computer Science, Springer, 2018, pp. 1–14. doi:10.1007/
978-3-030-14174-5_1.

URL https://doi.org/10.1007/978-3-030-14174-5_1

1585

[56] D. McDermott, M. Ghallab, A. Howe, C. Knoblock, A. Ram, M. Veloso, D. Weld, D. Wilkins, PDDL – The Planning Domain Definition Language, Tech. rep., Yale Center for Computational Vision and Control (1998).

[57] G. Röger, F. Pommerening, J. Seipp, Fast downward stone soup 2014, in: Eighth International Planning Competition (IPC-8): planner abstracts, 2014, pp. 28–31.

1590

[58] M. Martinez, I. Moraru, S. Edelkamp, S. Franco, Planning-PDBs plan-
ner in the IPC 2018, IPC-9 planner abstracts (2018) 63–66.

[59] T. Bolander, T. Engesser, R. Mattmüller, B. Nebel, Better eager than lazy? How agent types impact the successfulness of implicit coordination, in: Principles of Knowledge Representation and Reasoning: Proceedings of the Sixteenth International Conference, KR 2018, 2018, pp. 445–453.

1595

URL https://aaai.org/ocs/index.php/KR/KR18/paper/view/18070
1600

[60] H. van Ditmarsch, A. Herzig, J. Lang, P. Marquis, Introspective forgetting, Synthese 169 (2) (2009) 405–423.
URL https://doi.org/10.1007/s11229-009-9554-4

1605

[61] R. Milner, An algebraic definition of simulation between programs, in: D. C. Cooper (Ed.), Proceedings of the 2nd International Joint Conference on Artificial Intelligence. London, UK, September 1-3, 1971, William Kaufmann, 1971, pp. 481–489.
URL http://ijcai.org/Proceedings/71/Papers/044.pdf

1610

[62] T. Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: A. Herzig, E. Lorini (Eds.), Proceedings of the European Conference on Social Intelligence (ECSI-2014), Barcelona, Spain, November 3-5, 2014, Vol. 1283 of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 87–107.
URL http://ceur-ws.org/Vol-1283/paper_14.pdf

1615

[63] T. Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: H. van Ditmarsch, G. Sandu (Eds.), Jaakko Hintikka on Knowledge and Game-Theoretical Semantics, Springer International Publishing, Cham, 2018, pp. 207–236.
URL https://doi.org/10.1007/978-3-319-62864-6_14

1620

[64] R. Audi (Ed.), The Cambridge Dictionary of Philosophy, Second Edition, Cambridge University Press, 1999, entry ‘Action’.
[65] A. O. Liberman, A. Achen, R. K. Rendsvig, Dynamic term-modal logics for first-order epistemic planning, Artif. Intell. 286 (2020) 103305.
URL https://doi.org/10.1016/j.artint.2020.103305

1625

[66] J. McCarthy, Epistemological problems of artificial intelligence, in: B. L. Webber, N. J. Nilsson (Eds.), Readings in Artificial Intelligence, Morgan Kaufmann Publishers, 1981, pp. 459 – 465.
URL http://www.sciencedirect.com/science/article/pii/B9780934613033500350
[60] H. van Ditmarsch, A. Herzig, J. Lang, P. Marquis, Introspective forgetting, Synthese 169 (2) (2009) 405–423.

URL https://doi.org/10.1007/s11229-009-9554-4

1600

[61] R. Milner, An algebraic definition of simulation between programs, in: D. C. Cooper (Ed.), Proceedings of the 2nd International Joint Conference on Artificial Intelligence. London, UK, September 1-3, 1971, William Kaufmann, 1971, pp. 481–489.

URL http://ijcai.org/Proceedings/71/Papers/044.pdf

1605

[62] T. Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: A. Herzig, E. Lorini (Eds.), Proceedings of the European Conference on Social Intelligence (ECSI-2014), Barcelona, Spain, November 3-5, 2014, Vol. 1283 of CEUR Workshop Proceedings, CEUR-WS.org, 2014, pp. 87–107.

URL http://ceur-ws.org/Vol-1283/paper_14.pdf

1610

[63] T. Bolander, Seeing is believing: Formalising false-belief tasks in dynamic epistemic logic, in: H. van Ditmarsch, G. Sandu (Eds.), Jaakko Hintikka on Knowledge and Game-Theoretical Semantics, Springer International Publishing, Cham, 2018, pp. 207–236.

URL https://doi.org/10.1007/978-3-319-62864-6_14

1615

[64] R. Audi (Ed.), The Cambridge Dictionary of Philosophy, Second Edition, Cambridge University Press, 1999, entry ‘Action’.

[65] A. O. Liberman, A. Achen, R. K. Rendsvig, Dynamic term-modal logics for first-order epistemic planning, Artif. Intell. 286 (2020) 103305.

URL https://doi.org/10.1016/j.artint.2020.103305

1620

[66] J. McCarthy, Epistemological problems of artificial intelligence, in: B. L. Webber, N. J. Nilsson (Eds.), Readings in Artificial Intelligence, Morgan Kaufmann Publishers, 1981, pp. 459 – 465.

URL http://www.sciencedirect.com/science/article/pii/B9780934613033500350

1625
[67] T. Bolander, H. van Ditmarsch, A. Herzig, E. Lorini, P. Pardo, F. Schwarzentruber, Announcements to attentive agents, Journal of Logic, Language and Information 25 (1) (2016) 1–35.

URL https://doi.org/10.1007/s10849-015-9234-3

1630

[68] T. Miller, P. Felli, C. J. Muise, A. R. Pearce, L. Sonenberg, 'Knowing whether' in proper epistemic knowledge bases, in: D. Schuurmans, M. P. Wellman (Eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, AAAI Press, 2016, pp. 1044–1050.

URL http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12291

1635

[69] F. Kominis, H. Geffner, Multiagent online planning with nested beliefs and dialogue, in: L. Barbulescu, J. Frank, Mausam, S. F. Smith (Eds.), Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, ICAPS 2017, Pittsburgh, Pennsylvania, USA, June 18-23, 2017, AAAI Press, 2017, pp. 186–194.

URL https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15748

1640

[70] R. P. A. Petrick, F. Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: M. Ghallab, J. Hertzberg, P. Traverso (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, April 23-27, 2002, Toulouse, France, AAAI, 2002, pp. 212–222.

URL http://www.aaai.org/Library/AIPS/2002/aips02-022.php

1645

[71] E. Erdem, A. Herzig, Solving gossip problems using answer set programming: An epistemic planning approach, Electronic Proceedings in Theoretical Computer Science 325 (2020) 52–58, F. Ricca, A. Russo et al. (Eds.): Proc. 36th International Conference on Logic Program-

1655
[67] T. Bolander, H. van Ditmarsch, A. Herzig, E. Lorini, P. Pardo, F. Schwarzentruber, Announcements to attentive agents, Journal of Logic, Language and Information 25 (1) (2016) 1–35.

URL https://doi.org/10.1007/s10849-015-9234-3

1630

[68] T. Miller, P. Felli, C. J. Muise, A. R. Pearce, L. Sonenberg, 'Knowing whether' in proper epistemic knowledge bases, in: D. Schuurmans, M. P. Wellman (Eds.), Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona, USA, AAAI Press, 2016, pp. 1044–1050.

URL http://www.aaai.org/ocs/index.php/AAAI/AAAI16/paper/view/12291

1635

[69] F. Kominis, H. Geffner, Multiagent online planning with nested beliefs and dialogue, in: L. Barbulescu, J. Frank, Mausam, S. F. Smith (Eds.), Proceedings of the Twenty-Seventh International Conference on Automated Planning and Scheduling, ICAPS 2017, Pittsburgh, Pennsylvania, USA, June 18-23, 2017, AAAI Press, 2017, pp. 186–194.

URL https://aaai.org/ocs/index.php/ICAPS/ICAPS17/paper/view/15748

1640

[70] R. P. A. Petrick, F. Bacchus, A knowledge-based approach to planning with incomplete information and sensing, in: M. Ghallab, J. Hertzberg, P. Traverso (Eds.), Proceedings of the Sixth International Conference on Artificial Intelligence Planning Systems, April 23-27, 2002, Toulouse, France, AAAI, 2002, pp. 212–222.

URL http://www.aaai.org/Library/AIPS/2002/aips02-022.php

1645

[71] E. Erdem, A. Herzig, Solving gossip problems using answer set programming: An epistemic planning approach, Electronic Proceedings in Theoretical Computer Science 325 (2020) 52–58, F. Ricca, A. Russo et al. (Eds.): Proc. 36th International Conference on Logic Program-

1655
ming (Technical Communications) (ICLP 2020), EPTCS 325. doi:
10.4204/eptcs.325.11.

URL http://dx.doi.org/10.4204/EPTCS.325.11

[72] A. Herzig, F. Maris, J. Vianey, Dynamic logic of parallel propositional assignments and its applications to planning, in: S. Kraus (Ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, ijcai.org, 2019, pp. 5576–5582.

URL https://doi.org/10.24963/ijcai.2019/774

1660

[73] H. v. Ditmarsch, D. Grossi, A. Herzig, W. v. d. Hoek, L. B. Kuijer, Parameters for epistemic gossip problems, in: Proc. LOFT 2016, 2016.

1665

[74] H. van Ditmarsch, J. van Eijck, P. Pardo, R. Ramezanian, F. Schwarzentruber, Epistemic protocols for dynamic gossip, J. Applied Logic 20 (2017) 1–31.
ming (Technical Communications) (ICLP 2020), EPTCS 325. doi:
10.4204/eptcs.325.11.

URL http://dx.doi.org/10.4204/EPTCS.325.11

1660

[72] A. Herzig, F. Maris, J. Vianey, Dynamic logic of parallel propositional assignments and its applications to planning, in: S. Kraus (Ed.), Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, IJCAI 2019, Macao, China, August 10-16, 2019, ijcai.org, 2019, pp. 5576–5582.

URL https://doi.org/10.24963/ijcai.2019/774

1665

[73] H. v. Ditmarsch, D. Grossi, A. Herzig, W. v. d. Hoek, L. B. Kuijer, Parameters for epistemic gossip problems, in: Proc. LOFT 2016, 2016.

[74] H. van Ditmarsch, J. van Eijck, P. Pardo, R. Ramezanian, F. Schwarzentruber, Epistemic protocols for dynamic gossip, J. Applied Logic 20 (2017) 1–31.