DELPHIC: Towards an Eficient Possibility-Based Epistemic Planning Framework

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 diferent 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.

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 afairs, and it represents an epistemic state in DEL. Truth of formulae is defined as follows: i. (, ) |= if ∈ (); ii. (, ) |= ¬ if (, ) ̸|= ; iii. (, ) |= ∧ if (, ) |= and (, ) |= ; and iv. (, ) |= □ if ∀ if then (, ) |= . Finally, (, ) |= if (, ) |= , for all ∈ . bTEohxxua.smT,hwpeleyenb1eo.etdAhgtdweonontswoatokralndnosdwtbowarhereeptrihenesreantrhtoeothmciosiwnuhnleicereserhtaaecianoditsnyui(spp(1lℎaa)cneoddr inno2ta,. 1,:ℎ , ,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 |= if u() = 1; ii. u |= ¬ if u ̸|= ; iii. u |= ∧ if u |= and u |= ; and iv. u |= □ if ∀v if v ∈ u() then v |= . Finally, U |= if 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- 1:⟨ℎ,⟩ 2:⟨⊤,⟩ 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 information 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:¬ℎ of1 E=xa(mp1l,e21)raesnudlts2in=th(es2t,at2e)o.nNtohtieceritghhatt, wh1e(rreesp3., =2()a1n,d1)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 if 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 = {w1 ∪× e1} = {v3}, where v3(ℎ) = 1, v3() = {v3} and v3() = {w1 ∪× e2, w2 ∪× 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 diferent 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 eficient 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. 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 domains: Foundations , CoRR abs/1511 . 01960 ( 2015 ). URL: http://arxiv.org/abs/1511. 01960 . arXiv: 1511 . 01960 .

[4] F. Kominis , H. Gefner , 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. Bufet , J. Hofmann , 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 .