=Paper= {{Paper |id=Vol-3311/paper6 |storemode=property |title=DELPHIC: Towards an Efficient Possibility-based Epistemic Planning Framework |pdfUrl=https://ceur-ws.org/Vol-3311/paper6.pdf |volume=Vol-3311 |authors=Alessandro Burigana,Paolo Felli,Marco Montali |dblpUrl=https://dblp.org/rec/conf/aiia/BuriganaFM22 }} ==DELPHIC: Towards an Efficient Possibility-based Epistemic Planning Framework== https://ceur-ws.org/Vol-3311/paper6.pdf 
DELPHIC: Towards an Efficient Possibility-Based
Epistemic Planning Framework
Alessandro Burigana1 , Paolo Felli1 and Marco Montali1
1
    Free University of Bozen-Bolzano, Italy


                                         Abstract
                                         Dynamic Epistemic Logic (DEL) provides a very expressive framework for planning, called epistemic
                                         planning. In this paper, we discuss the shortcomings of the traditional DEL semantics, based on Kripke
                                         models, and we propose a formulation of epistemic planning based on a different kind of object, called
                                         possibility. We argue that the resulting framework, named delphic, constitutes a valid alternative, since
                                         it provides a more compact representation of epistemic information and a lighter update mechanism. We
                                         conclude by discussing the advantages of delphic, both theoretically and in terms of implementation.




1. Introduction
In recent times, there has been a growing interest in the study of Multi-Agent Systems and in
their application to a wide range of settings. Autonomous agents are expected to face dynamic
situations and to be able to adapt in order to reach a given goal. In these contexts, it is paramount
for agents to be able to reason on the physical world that surrounds them as well as on the
knowledge that other agents have about the world and other agents’ knowledge.
   Bolander and Andersen [1] introduced epistemic planning as a planning framework based on
Dynamic Epistemic Logic (DEL) [2]. Although the traditional Kripke semantics of DEL allows
for a great expressive power, only small fragments are implemented in practice [3, 4, 5, 6]. In
fact, computing a solution for an epistemic planning problem requires to handle a large quantity
of information, which results in poor time results. As a result, various epistemic planning
systems rely on simplifying the setting of interest.
   In this paper, as a first step to overcome this issue, we propose a framework for epistemic
planning called delphic (DEL-planning with a Possibility-based Homogeneous Information
Characterization), that relies on an alternative semantics of DEL based on possibilities [7]. The
choice of adopting a possibilities is motivated by the fact that they represent information in a
more compact way, which has been shown to improve performance in the solver EFP [5]. In
what follows, we introduce the main elements of DEL (Kripke models, event models, product
update) and their corresponding ones in delphic (possibilities, eventualities, union update),
discussing the advantages of delphic with respect to the Kripke semantics, both theoretically
and in terms of implementation. We conclude with some future works.

OVERLAY 2022: 4th Workshop on Artificial Intelligence and Formal Verification, Logic, Automata, and Synthesis,
November 28, 2022, Udine, Italy
$ burigana@inf.unibz.it (A. Burigana); paolo.felli@unibz.it (P. Felli); montali@inf.unibz.it (M. Montali)
 0000-0002-9977-6735 (A. Burigana); 0000-0001-9561-8775 (P. Felli); 0000-0002-8021-3430 (M. Montali)
                                       Β© 2022 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0).
    CEUR
    Workshop
    Proceedings
                  http://ceur-ws.org
                  ISSN 1613-0073
                                       CEUR Workshop Proceedings (CEUR-WS.org)
2. A Novel Semantics for Epistemic Planning
Epistemic Models. Let 𝒫 be a countable set of propositional atoms and π’œπ’’ = {1, . . . , 𝑛}
be a finite set of agents. The language ℒ𝒫,π’œπ’’ of multi-agent epistemic logic is defined by the
BNF: πœ™ ::= 𝑝 | Β¬πœ™ | πœ™ ∧ πœ™ | ░𝑖 πœ™, where 𝑝 ∈ 𝒫, 𝑖 ∈ π’œπ’’. The formula ░𝑖 πœ™ is read as β€œagent 𝑖
knows/believes that πœ™β€. In the traditional possible world semantics of DEL, a Kripke model [8]
represents an epistemic model. Epistemic models contain both factual information on multiple
possible worlds and epistemic information, i.e., which worlds are considered possible by agents.

Definition 1 (Kripke Model). A Kripke model is a triple 𝑀 = (π‘Š, 𝑅, 𝑉 ) where: 1) π‘Š ΜΈ= βˆ… is
the set of possible worlds, 2) 𝑅 : π’œπ’’ β†’ 2π‘Š Γ—π‘Š assigns to each agent 𝑖 an accessibility relation
𝑅(𝑖) (abbreviated as 𝑅𝑖 ), and 3) 𝑉 : 𝒫 β†’ 2π‘Š assigns to each atom a set of worlds.

A (multi-)pointed Kripke model is a pair (𝑀, π‘Šπ‘‘ ), where π‘Šπ‘‘ βŠ† π‘Š is a non-empty set of
designated worlds denoting the real state of affairs, and it represents an epistemic state in DEL.
Truth of formulae is defined as follows: i. (𝑀, 𝑀) |= 𝑝 iff 𝑀 ∈ 𝑉 (𝑝); ii. (𝑀, 𝑀) |= Β¬πœ™ iff
(𝑀, 𝑀) ΜΈ|= πœ™; iii. (𝑀, 𝑀) |= πœ™ ∧ πœ“ iff (𝑀, 𝑀) |= πœ™ and (𝑀, 𝑀) |= πœ“; and iv. (𝑀, 𝑀) |= ░𝑖 πœ™ iff
βˆ€π‘£ if 𝑀𝑅𝑖 𝑣 then (𝑀, 𝑣) |= πœ™. Finally, (𝑀, π‘Šπ‘‘ ) |= πœ™ iff (𝑀, 𝑣) |= πœ™, for all 𝑣 ∈ π‘Šπ‘‘ .
Example 1. Agents a and b are in a room where a coin is placed in a          π‘Ž, 𝑏        π‘Ž, 𝑏
box. They both do not know whether the coin lies heads up (β„Ž) or not.             π‘Ž, 𝑏
                                                                            𝑀1 :β„Ž        𝑀2 :Β¬β„Ž
Thus, we need two worlds to represent this uncertainty (𝑀1 and 𝑀2 ,
respectively). As we are omniscient observers, we assume that we know that 𝑀1 is the designated
world (circled dot). In DEL, this is modeled by the epistemic state on the right.

Definition 2 (Possibility [7]). A possibility u is a function that assigns to each atom 𝑝 ∈ 𝒫 a
truth value u(𝑝) ∈ {0, 1} and to each agent 𝑖 ∈ π’œπ’’ a set of possibilities u(𝑖).

In delphic, an epistemic model is represented by a possibility. A possibility spectrum is a finite
set U = {u1 , . . . uπ‘˜ } of possibilities and it represents an epistemic state in delphic. Importantly,
possibility spectrums represent the same information as multi-pointed Kripke models, namely
factual and epistemic information, plus the designated worlds. In Kripke models, the worlds (π‘Š )
and their interpretations (𝑉 ) and relations (𝑅𝑖 ) are given as separated components. On the other
hand, each possibility constitutes a possible world and it contains both an interpretation u(𝑝) for
each atom in 𝒫, and a set of worlds u(𝑖) that agent 𝑖 considers possible, for each agent in π’œπ’’.
Hence, the designated worlds of the spectrum U are exactly the possibilities u1 , . . . uπ‘˜ (whereas
the non-designated worlds correspond to possibilities attributed to agents by a possibility in
U, but not explicitly included in U themselves). Truth of formulae in possibilities is defined as
follows: i. u |= 𝑝 iff u(𝑝) = 1; ii. u |= Β¬πœ™ iff u ΜΈ|= πœ™; iii. u |= πœ™ ∧ πœ“ iff u |= πœ™ and u |= πœ“; and
iv. u |= ░𝑖 πœ™ iff βˆ€v if v ∈ u(𝑖) then v |= πœ™. Finally, U |= πœ™ iff v |= πœ™, for all v ∈ U.

Example 2. The possibility spectrum representing the situation of Example 1 is W = {w1 }, where:
i. w1 (β„Ž) = 1 and w1 (π‘Ž) = w1 (𝑏) = {w1 , w2 }; and ii. w2 (β„Ž) = 0 and w2 (π‘Ž) = w2 (𝑏) = {w1 , w2 }.

Event Models. In DEL, actions are modeled by event models [9, 10], that represent how new
information changes the perspectives of agents. In what follows, events play the role of worlds
and the accessibility relation 𝑄𝑖 describes which events are considered possible by agent 𝑖.
Definition 3 (Event Model). An event model is a quadruple β„° = (𝐸, 𝑄, π‘π‘Ÿπ‘’, π‘π‘œπ‘ π‘‘) where:
1) 𝐸 ΜΈ= βˆ… is the set of events, 2) 𝑄 : π’œπ’’ β†’ 2𝐸×𝐸 assigns to each agent 𝑖 an accessibility
relation 𝑄(𝑖) (abbreviated as 𝑄𝑖 ), 3) π‘π‘Ÿπ‘’ : 𝐸 β†’ ℒ𝒫,π’œπ’’ assigns to each event a precondition, and
4) π‘π‘œπ‘ π‘‘ : 𝐸 β†’ (𝒫 β†’ ℒ𝒫,π’œπ’’ ) assigns to each event a postcondition for each atom.
Informally, preconditions capture the applicability of events, whereas postconditions determine
whether an atom is true after the event is applied. A (multi-)pointed event model is a pair (β„°, 𝐸𝑑 ),
where 𝐸𝑑 βŠ† 𝐸 is a non-empty set of designated events, and it represents an action in DEL.
Example 3. Suppose now that, in the situation of Example 1, a                π‘Ž             π‘Ž, 𝑏
peeks into the box while b is distracted. Events 𝑒1 and 𝑒2 repre- 𝑒 :βŸ¨β„Ž,π‘–π‘‘βŸ©          𝑏
                                                                                            𝑒2 :⟨⊀,π‘–π‘‘βŸ©
                                                                        1
sent a’s and b’s perspectives, respectively (we use the notation
βŸ¨π‘π‘Ÿπ‘’, π‘π‘œπ‘ π‘‘βŸ© for events). In this way, a learns that the coin lies heads up, while b remains ignorant
about the situation. Moreover, a is aware of b’s perspective, but b is not aware of a’s point of view.
In DEL, this is modeled by the action on the right.
   In delphic, we introduce the novel concept of eventuality to model actions. Let π‘π‘Ÿπ‘’ ∈
                                                                                       / 𝒫 be a
fresh atom and let 𝒫 β€² = 𝒫 βˆͺ {π‘π‘Ÿπ‘’}. In the following definition, e(π‘π‘Ÿπ‘’) is the precondition of e,
while e(𝑝), where 𝑝 ∈ 𝒫, is the postcondition of 𝑝 in e.
Definition 4 (Eventuality). An eventuality e is a function that assigns to each atom 𝑝′ ∈ 𝒫 β€² a
formula e(𝑝′ ) ∈ ℒ𝒫,π’œπ’’ and to each agent 𝑖 ∈ π’œπ’’ a set of eventualities e(𝑖).
An eventuality spectrum is a finite set E = {e1 , . . . eπ‘˜ } of eventualities and it represents an action
in delphic. Importantly, eventuality spectrums represent the same information as multi-pointed
event models, namely pre-/postconditions of events (functions π‘π‘Ÿπ‘’ and π‘π‘œπ‘ π‘‘) and epistemic
information (relations 𝑄𝑖 ), plus the designated events. While in event models these are given
as separated components, each eventuality constitutes an event and it contains a precondition
e(π‘π‘Ÿπ‘’), a postcondition e(𝑝) for each 𝑝 ∈ 𝒫, and a set of eventualities e(𝑖) that agent 𝑖 considers
possible, for each 𝑖 ∈ π’œπ’’. The designated events of E are exactly the eventualities e1 , . . . eπ‘˜ .
Example 4. The eventuality spectrum representing the action of Example 3 is E = {e1 }, where:
i. e1 (π‘π‘Ÿπ‘’) = β„Ž, e1 (β„Ž) = β„Ž, e1 (π‘Ž) = {e1 } and e1 (𝑏) = {e2 }; and ii. e2 (π‘π‘Ÿπ‘’) = ⊀, e2 (β„Ž) = β„Ž and
e2 (π‘Ž) = e2 (𝑏) = {e1 , e2 }.
Product Update. The product update formalizes how (applicable) actions bring about informa-
tion change in epistemic states in DEL. An action (β„°, 𝐸𝑑 ) is applicable in (𝑀, π‘Šπ‘‘ ) if for each
world 𝑀 ∈ π‘Šπ‘‘ there exists an event 𝑒 ∈ 𝐸𝑑 such that (𝑀, 𝑀) |= π‘π‘Ÿπ‘’(𝑒).
Definition 5 (Product Update). Let 𝑀 = (π‘Š, 𝑅, 𝑉 ) and β„° = (𝐸, 𝑄, π‘π‘Ÿπ‘’, π‘π‘œπ‘ π‘‘). The product
update of (𝑀, π‘Šπ‘‘ ) with (β„°, 𝐸𝑑 ) is (𝑀, π‘Šπ‘‘ ) βŠ— (β„°, 𝐸𝑑 ) = ((π‘Š β€² , 𝑅′ , 𝑉 β€² ), π‘Šπ‘‘β€² ), where:
    1. π‘Š β€² = {(𝑀, 𝑒) ∈ π‘Š Γ— 𝐸 | (𝑀, 𝑀) |= π‘π‘Ÿπ‘’(𝑒)},
    2. 𝑅𝑖′ = {((𝑀, 𝑒), (𝑣, 𝑓 )) ∈ π‘Š β€² Γ— π‘Š β€² | 𝑀𝑅𝑖 𝑣 and 𝑒𝑄𝑖 𝑓 },
    3. 𝑉 β€² (𝑝) = {(𝑀, 𝑒) ∈ π‘Š β€² | (𝑀, 𝑀) |= π‘π‘œπ‘ π‘‘(𝑒)(𝑝)}, and
    4. π‘Šπ‘‘β€² = {(𝑀, 𝑒) ∈ π‘Š β€² | 𝑀 ∈ π‘Šπ‘‘ and 𝑒 ∈ 𝐸𝑑 }.
Example 5. Applying the action of Example 3 in the epistemic state             𝑣1 :β„Ž π‘Ž, 𝑏 𝑣2 :Β¬β„Ž
of Example 1 results in the state on the right, where 𝑣3 = (𝑀1 , 𝑒1 ), π‘Ž, 𝑏                     π‘Ž, 𝑏
                                                                                     𝑏      𝑏
𝑣1 = (𝑀1 , 𝑒2 ) and 𝑣2 = (𝑀2 , 𝑒2 ). Notice that 𝑀1 (resp., 𝑀2 ) and 𝑣1            𝑣3 :β„Ž     π‘Ž
(resp., 𝑣2 ) encode the same information, but they are distinct objects.
   In delphic, we introduce the concept of union update in place of the traditional product
update to formalize how an (applicable) eventuality spectrum brings about information change
in a possibility spectrum. An eventuality spectrum E is applicable in a possibility spectrum U if
for each possibility u ∈ U there exists an eventuality e ∈ E such that u |= e(π‘π‘Ÿπ‘’).

Definition 6 (Union Update). The union update of a possibility u with an eventuality e is the
possibility uβ€² = u βˆͺ
                   Γ— e, such that if u ΜΈ|= e(π‘π‘Ÿπ‘’), then uβ€² = βˆ…; otherwise:

      uβ€² (𝑝) = 1 iff u |= e(𝑝)
      uβ€² (𝑖) = {v βˆͺ
                  Γ— f | v ∈ u(𝑖), f ∈ e(𝑖) and v |= f(π‘π‘Ÿπ‘’)}

The union update of a possibility spectrum U with an eventuality spectrum E is the possibility
spectrum U βˆͺ Γ— E = {u βˆͺ Γ— e | u ∈ U, e ∈ E and u |= e(π‘π‘Ÿπ‘’)}.



Example 6. Applying E (Example 4) to W (Example 2) results in: W βˆͺ       Γ— E = {w βˆͺ
                                                                                    1 Γ— e1 } = {v3 },
where v3 (β„Ž) = 1, v3 (π‘Ž) = {v3 } and v3 (𝑏) = {w1 βˆͺ Γ— e ,w βˆͺ
                                                        2  2 Γ— e2 } = {w1 , w2 }. Notice that the
union update allows us to reuse previously calculated information (i.e., possibilities w1 and w2 ).


3. Discussion and Future Works
The delphic framework for epistemic planning has various advantages over the traditional
Kripke semantics for DEL. From a conceptual standpoint, possibilities allow for a more natural
representation of epistemic states: while a Kripke model represents information as heterogeneous
components (i.e., set of worlds, accessibility relations, interpretation of atoms in each world),
possibilities encode all this information within one coherent component (namely, the possibility
itself). In other words, a possibility encodes both a possible world and the information about
which worlds are considered possible by each agent. This is more akin to how humans think of
a situation, i.e., as a set of different possibilities. The same argument holds for actions, since an
eventuality is essentially a possibility that maps formulae (instead of truth values) to atoms.
   From a theoretical perspective, possibilities are tightly related to Kripke models and they are
proved to be a more compact representation of epistemic models [7]. This was shown to improve
runtime performance in the solver EFP [5], where a fragment of DEL was implemented with both
semantics. Moreover, the union update overcomes two important shortcomings of the traditional
product update. First, the product update is essentially a blind cross-product between worlds
and events, which may result in epistemic states having unreachable components. Importantly,
this redundant information accumulates during the planning process and produces a significant
overhead in solving time. Second, the cross-product makes it impossible to reuse previous
information. This is a crucial aspect, since it is common to have some agents maintain their
perspective after an action is carried out. Instead, in DEL we are forced to create a new world
and to copy the previous information in it (see Example 5). Conversely, due to the semantics of
union update, in delphic it is possible to reuse information, as shown in Example 6.
   These arguments suggest that delphic allows for a lighter update mechanism, that would
ultimately result in more efficient implementations. To obtain empirical evidence of such
improvement, we plan to develop an encoding both of delphic and the traditional DEL semantics
into various solver, e.g., ASP, Prolog, SMT solvers, and comparatively evaluate the two versions.
Acknowledgments
This work is partially supported by the Italian Ministry of University and Research under
the PRIN programme, grant B87G22000450001 (PINPOINT), and by the Free University of
Bozen-Bolzano with the SMART-APP and ADAPTERS projects.


References
 [1] T. Bolander, M. B. Andersen, Epistemic planning for single and multi-agent systems, J.
     Appl. Non Class. Logics 21 (2011) 9–34. URL: https://doi.org/10.3166/jancl.21.9-34. doi:10.
     3166/jancl.21.9-34.
 [2] H. P. van Ditmarsch, W. van der Hoek, B. P. Kooi, Dynamic Epistemic Logic, volume
     337, Springer Netherlands, 2007. URL: https://doi.org/10.1007/978-1-4020-5839-4. doi:10.
     1007/978-1-4020-5839-4.
 [3] C. Baral, G. Gelfond, E. Pontelli, T. C. Son, An action language for multi-agent do-
     mains: Foundations, CoRR abs/1511.01960 (2015). URL: http://arxiv.org/abs/1511.01960.
     arXiv:1511.01960.
 [4] 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 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.
 [5] F. Fabiano, A. Burigana, A. Dovier, E. Pontelli, EFP 2.0: A multi-agent epistemic solver with
     multiple e-state representations, in: J. C. Beck, O. Buffet, J. Hoffmann, E. Karpas, S. Sohrabi
     (Eds.), Proceedings of the Thirtieth International Conference on Automated Planning and
     Scheduling, Nancy, France, October 26-30, 2020, AAAI Press, 2020, pp. 101–109. URL:
     https://aaai.org/ojs/index.php/ICAPS/article/view/6650.
 [6] F. Fabiano, A. Burigana, A. Dovier, E. Pontelli, T. C. Son, Multi-agent epistemic planning
     with inconsistent beliefs, trust and lies, in: PRICAI 2021: Trends in Artificial Intelligence -
     18th Pacific Rim International Conference on Artificial Intelligence, PRICAI 2021, Hanoi,
     Vietnam, November 8-12, 2021, Proceedings, Part I, Springer, 2021, pp. 586–597. URL:
     https://doi.org/10.1007/978-3-030-89188-6_44.
 [7] J. Gerbrandy, W. Groeneveld, Reasoning about information change, J. Log. Lang.
     Inf. 6 (1997) 147–169. URL: https://doi.org/10.1023/A:1008222603071. doi:10.1023/A:
     1008222603071.
 [8] S. A. Kripke, Semantical considerations on modal logic, Acta Philosophica Fennica 16
     (1963) 83–94.
 [9] A. Baltag, L. S. Moss, S. Solecki, The logic of public announcements and common knowledge
     and private suspicions, in: I. Gilboa (Ed.), Proceedings of the 7th Conference on Theoretical
     Aspects of Rationality and Knowledge (TARK-98), Evanston, IL, USA, July 22-24, 1998,
     Morgan Kaufmann, 1998, pp. 43–56.
[10] H. van Ditmarsch, B. Kooi, Semantic results for ontic and epistemic change, Texts in Logic
     and Games 3, Amsterdam University Press, 2008, pp. 87–117.