Epistemic planning is a branch of Artificial Intelligence that stems from the combination of automated planning and Dynamic Epistemic Logic (DEL). While DEL provides a very expressive framework-which comes at the cost of undecidability-to guarantee the feasibility of the planning process, various fragments have been studied in the literature, that rely on very specific syntax for representing domains. As a result, a comprehensive language that is able to capture the general DEL framework is currently not present in the literature. In this paper, we propose a new language called EPDDL (Epistemic Planning Domain Definition Language), through which we can capture the full DEL semantics, thus allowing for a general and unified syntax for representing epistemic planning domains.
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 ∈ , ∈ and ⊆ . We read the formulae □ and as “agent knows/believes that ” and “group has common knowledge/belief that ”, respectively. In the possible world semantics of DEL, a Kripke model [12] 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 ), 3) : →2 assigns to each atom a set of worlds.
An epistemic state is a pair (, ), where ⊆ is a non-empty set of designated worlds denoting the real state of afairs. Truth of formulae is defined as follows: i. (, ) |= if ∈ (); ii. (, ) |= ¬ if (, ) ̸|= ; iii. (, ) |= ∧ if (, ) |= and (, ) |= ; iv. (, ) |= □ if ∀ if (, ) ∈ then (, ) |= ; and v. (, ) |= if ∀ if (, ) ∈ * then (, ) |= (where = ∪∈ and * denotes its transitive closure). Finally, (, ) |= if (, ) |= , for all ∈ . Event Models. In DEL, actions are modeled by event models [13, 14], that represent how new information changes the perspectives of agents. Here, events can be seen as possible actions and the accessibility relation describes which events are considered possible by agent . Definition 2 (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, 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. Product Update. The product update formalizes how actions bring about information change in epistemic states in DEL. An action (ℰ , ) is applicable in (, ) if and only if for each world ∈ there exists an event ∈ such that (, ) |= ().
Definition 3 (Product Update). Given an action (ℰ , ) applicable in an epistemic state (, ), where = (, , ) and ℰ = (, , , ), the product update of (, ) with (ℰ , ) is the multi-pointed Kripke model (, ) ⊗ (ℰ , ) = (( ′, ′, ′), ′), where: 1. ′ = {(, ) ∈ × | (, ) |= ()}, 2. ′ = {((, ), (, )) ∈ ′ × ′ | (, ) ∈ and (, ) ∈ }, 3. ′() = {(, ) ∈ ′ | (, ) |= ()()}, 4. ′ = {(, ) ∈ ′ | ∈ and ∈ }.
Example 1 (DEL). Consider the above situation with Anne () and Bob (). Before Anne reads the letter, both agents consider possible two options: either she was admitted in the university (), or not. Thus, we need two worlds to represent this uncertainty (1 and 2, respectively). As we are universal observers, we assume that we know that 1 is the designated world (circled dot). This is modeled by the epistemic state on the left. When Anne reads the letter, Bob can not read its content. In the center of the picture, events 1 (Anne learns that ) and 2 (Anne learns that ¬) are needed to represent Bob’s uncertainty about the outcomes of the action (we use the notation ⟨, ⟩ for events). In this way, Anne learns that she was admitted, while Bob remains uncertain. Moreover, both Anne and Bob are reciprocally aware of their perspective. The epistemic state ′ that results from this action is on the right. Notice that now Anne knows that she was admitted, i.e., ( ′, (1, 1)) |= □ , while Bob does not change his perspective. ,
, 1: 2:¬ ,
, ⊗ , = ,
, 1:⟨,⟩ 2:⟨¬,⟩ (1, 1): (2, 2):¬
The development of the syntax of EPDDL was driven by three design principles: (
Since a library is intended to describe universal aspects, action types should not refer to specific entities of a problem. To this end, we implemented two important design choices: 1) parametrized events and action types, and 2) observability groups. First, parameters allow to abstract from particular predicates and agents. Importantly, in EPDDL, apart from objects, parameters can also refer to agents, formulae and postconditions. This aspect is crucial to maintain the universality of action types: for instance, if we pass the preconditions of events as parameters, we can simply refer to them as variables within an action type. As a result, action type libraries can be used transversally across diferent domains . Second, observability groups generalize accessibility relations. Each group represents the perspective of one or more agents. For instance, when Anne reads the letter, she is fully observant, since she learns its content, while Bob is partially observant, since he remains uncertain about Anne’s knowledge. Action types only refer to observability groups (lines 13-15). Then, in each action we assign each agent to a group (lines 29-33). We now show the EPDDL representation of the action of Example 1. 1 (define (library lib) 2 (:event e1 3 :parameters (?sensed - predicate) 4 :precondition (?sensed)) 5 (:event e2 6 :parameters (?sensed - predicate) 7 :precondition (not (?sensed))) 8 (:action-type sensing 9 :parameters (?p - predicate) 10 :observability-groups (Fully Partially) 11 :events (e1 (?sensed :: ?p) ) 12 (e2 (?sensed :: ?p) ) 13 :relations (Fully (e1 e1) (e2 e2)) 14 (Partially (e1 e1) (e2 e2) 15 (e1 e2) (e2 e1)) 16 :designated (e1))) 4. Discussion 17 (define (domain example1) 18 (:action-type-libraries lib) 19 (:requirements :del :typing :equality 20 :universal-conditions) 21 (:predicates (u) 22 (has_letter ?ag - agent)) 23 (:action read_letter 24 :parameters (?ag - agent) 25 :action-type (sensing (?p :: (u)) ) 26 :precondition (has_letter ?ag) 27 :observability-conditions 28 (?ag Fully) 29 (forall (?ag2 - agent) 30 (if (not (= ?ag2 ?ag)) 31 (Partially) 32 )))) In this paper, we have introduced a new language for describing epistemic planning domains, called EPDDL. Importantly, this language is able to capture the full DEL semantics. Intuitively, this follows from the fact that each component of an event model (events, relations, preconditions, postconditions) is captured by a corresponding syntactical element of EPDDL. Thus, we obtain a syntax through which we can represent the existing fragments of epistemic planning in an unified way. Due to space limits, we could not address all features of the language. As future work, we plan on finalizing the syntax of EPDDL and to implement a full-fledged parser (also including a type checker). Moreover, we intend to use EPDDL to create a public repository of epistemic planning domains to be used as benchmarks for epistemic planners. (1963) 83–94. [13] 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. [14] 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. [15] T. C. Son, E. Pontelli, C. Baral, G. Gelfond, Finitary s5-theories, in: E. Fermé, J. Leite (Eds.), Logics in Artificial Intelligence - 14th European Conference, JELIA 2014, Funchal, Madeira, Portugal, September 24-26, 2014. Proceedings, volume 8761 of Lecture Notes in Computer Science, Springer, 2014, pp. 239–252. URL: https://doi.org/10.1007/978-3-319-11558-0_17. doi:10.1007/978-3-319-11558-0\_17.