Designing autonomous agents, that interact with others to perform complex tasks, has always been one of the main objective of the Arti cial Intelligence community. For such systems to be employed in complex scenarios, where the information about others is key (e.g., self-driving cars), it is necessary to de ne robust formalisms that allow each agent to act considering her beliefs on both: i) the state of the world; and ii) the other agents' perspective of it. The branch of AI that studies such formalisms is known in literature as Multi-Agent Epistemic Planning (MEP). The epistemic action-based language mA , to the best of our knowledge, is the most comprehensive tool to model MEP domains but still lacks concepts that are necessary to reason on real-world scenarios. In this paper we introduce the actions (un)trustworthy announcement and (mis)trustworthy announcement for mA . These actions increase the language's expressiveness introducing the notion of trust, therefore allowing for a more profound representation of real-world scenarios. In particular, we will provide the characterization, along with some desired properties, of the aforementioned actions' transition functions. Finally, we will discuss the importance of formalizing the concept of trust in the MEP problem.
Recently, techniques derived from the elds of automated reasoning and knowledge representation have been heavily exploited in both our daily life and in the industry. The natural evolution of such applications, i.e., systems that involve hundreds of agents each acting upon her beliefs to achieve her own goals (e.g., self-driving cars), is going to be widely deployed in just few years. The branch of AI interested in studying and modeling such agent-based technologies is referred ? Copyright ' 2020 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0). to as automated planning. In particular, multi-agent planning [1, 6{8, 13] provides a powerful tool to model scenarios comprised of agents that interact with each other. To maximize the potentials of such autonomous systems each agent should be able to reason on both: i) her perspective of the \concrete" world; and ii) her beliefs of the other agents' perspective of the environment|that is, their viewpoint of the \concrete" world and of the others' perspective of it. The planning problem in this new setting is referred to as multi-agent epistemic planning in the literature.
Nevertheless, as said in [
In this paper we expand the language mA [
In particular, i) (un)trustworthy announcement formalizes the situation when the untrusty agents will not change their beliefs about the world no matter what the announcer says; and ii) (mis)trustworthy announcement captures the scenarios where the announcer, when not trusted, is believed to have a systematic faulty perception of the announced environment's properties. This leads the untrusty agents to believe the opposite of what has been announced.
The paper is organized as follows: Section 2 will present the eld of epistemic reasoning. The background will be then concluded with Section 3 where we will introduce the epistemic action language mA . In Section 4 we will present the semantics of the newly formalized actions along with some desired properties, formally demonstrated in the Supplementary Documentation (available at http://clp.dimi.uniud.it/sw/). Finally, in Section 5 we will discuss the impact of the new actions and some possible future developments.
Moreover, in the Supplementary Documentation we also provide the
formalization of the (un/mis)trustworthy announcement actions for mA [
The research on autonomous reasoners has lead, among other things, to the
formalization of the well-known planning problem [
In particular, Dynamic Epistemic Logic (DEL), the foundation of multi-agent
epistemic planning (MEP), is used to reason not only on the state of the world
but also on information change. As said in [
In what follows, we will provide a short description of the basic concepts
that de ne DEL and MEP. As it is beyond the scope of this work to give an
exhaustive introduction, the interested reader can refer to [
Let AG be a nite set of agents s.t. jAGj = n with n 1 and let F be a set of
propositional variables, called uents. Each world is described by a subset of
elements of F (intuitively, those that are \true"). Moreover, in epistemic logic each
agent ag 2 AG is associated to an epistemic modal operator Bag that represents
the knowledge/belief of ag herself. Finally, epistemic group operators E and
C are also introduced in epistemic logic. Intuitively, E and C represent the
knowledge/belief of a group of agents and the common knowledge/belief of ,
respectively. To be more precise, as in [
With a slight abuse of notation, we will refer to uent literals simply as uents. De nition 2 (Belief formula). A belief formula is de ned as follows: { A uent formula is a belief formula; { If ' is a belief formula and ag 2 AG, then Bag' is a belief formula; { If '1; '2 and '3 are belief formulae, then :'3 and '1 op '2 are belief formulae, where op 2 f^; _; )g; { If ' is a belief formula and ; =6 AG then E ' and C ' are belief formulae.
Example 1. Let us consider the formula Bag1 Bag2 '. This formula expresses that the agent ag1 believes that the agent ag2 believes that ' is true. The formula Bag1 :' expresses that the agent ag1 believes that ' is false. Let us also introduce the notion of multi-agent epistemic planning domain. Intuitively, an epistemic planning domain contains all the necessary information to de ne a planning problem in a multi-agent epistemic scenario. De nition 3 (Multi-agent epistemic planning domain). We de ne a multiagent epistemic domain as the tuple D = hF ; AG; A; 'i; 'gi where: { F is the set of all the uents of D; { AG is the set of the agents of D; { A represents the set of all the actions of D; { 'i is the belief formula that describes the initial conditions of the planning process; and { 'g is the belief formula that represents the goal condition.
Moreover, from now on, with the term action instance we will indicate an element of the set AI = A AG. Intuitively, an action instance ahagi identi es the execution of the action a by the agent ag.
Given a domain D we will refer to its components through the parenthesis operator. For instance to access the elements F and AG of D we will use the more compact notation D(F ) and D(AG), respectively.
Furthermore, we will indicate a state of an epistemic planning domain as
e-state. Intuitively, an e-state contains all the information needed to encode
both the concrete properties of the world and the knowledge/belief relations.
The language mA , derived by the language mA [
The Epistemic action language mA
Let us brie y introduce the epistemic action language mA [
First, we need to de ne the three di erent types of action used by mA to model the e-states update: { World-altering action (also called ontic): used to modify certain properties (i.e., uents) of the world; { Sensing action: used by an agent to re ne her beliefs about the world; { Announcement action: used by an agent to a ect the beliefs of other agents. The action language also allows to specify, for each action instance ahagi, the observability relation of each agent. Namely, an agent x may be fully observant (x 2 F ), partially observant (x 2 P ), or oblivious (x 2 O) w.r.t. ahagi. If an agent is fully observant, then she is aware of both the execution of the action instance and its e ects; she is partially observant if she is only aware of the action execution but not of the outcomes; she is oblivious if she is ignorant of the execution of the action. More precisely, given an action instance ahagi, a uent literal f, a uent formula and the belief formula ', the syntax of mA is de ned as follows: executable a if ': captures the executability conditions ; a causes f if ': captures the e ects of ontic actions; a determines f if ': captures the e ects of sensing actions; a announces if ': captures the e ects of announcement actions; ag observes a if ': captures fully observant agents for an action; and ag aware of a if ': captures partially observant agents for a given action. Notice that if we do not state otherwise, an agent will be considered oblivious. Finally, statements of the form initially ' and goal ' capture the initial and goal conditions, respectively.
The language mA , introduced in [
{ A possibility u is a function that assigns to each uent f 2 F a truth value u(f) 2 f0; 1g and to each agent ag 2 AG an information state u(ag) = ; { An information state is a set of possibilities.
Intuitively, a possibility u allows to capture the concept of e-state by: i) encoding a possible world through the truth values u(f) 8f 2 F ; and ii) capturing the beliefs of an agent ag 2 AG thanks to the assignment of information states u(ag). Since possibilities are non-well-founded objects, the concepts of state and possible world collapse. In fact, a possibility contains both the information of a possible world and the information about the agents' beliefs (represented by other possibilities).
De nition 5 (Entailment w.r.t. possibilities [
E (Ek ').
For the sake of readability we will omit the complete speci cation of the ontic,
sensing and annoumcement transition function. The interested reader is referred
to [
In de ning the actions we consider a static and globally visible version of `trust' that can be formalized with a simple function T : AG AG 7! f0; 1g. For the sake of readability we will consider only the case where T is a static and globally visible function. Let us notice that having T to be dynamic is easily achievable. In particular, we just need to de ne how T may vary, e.g., making the function depending on some uents value. For the sake of simplicity let us imagine T to be xed and not dependent from the plan execution. On the other hand, making T not globally visible|i.e., each agent knows her own version of the trust function|is not straightforward. The problem arise when two agents have di erent views of the same trust relation leading to the generation of non-consistent beliefs, an open problem in the MEP community. We leave the investigation of this scenario as future work.
To clarify the e-state update after the execution of the new actions we will also present a graphical representation of the transition function application.
The examples of execution will be based on a variation of the Grapevine
domain [
We can now introduce the transition function of the action (un)trustworthy announcement for mA . Intuitively, this action models an announcement where the listening agents can or cannot trust the announcer. That is: i) the trusty agents will update their belief consistently with what has been announced; and ii) the untrusty1 ones will maintain their beliefs about the world and will update 1 The agents that are fully observant w.r.t. announcement but that do not trust the announcer. their perspective on the beliefs of the trusty agents. Let us recall that the sets Fa; Pa; Oa represent the set of fully observant, partially observant and oblivious agents w.r.t. to the execution of an action instance ahagi, respectively.
Let a domain D, its set of action instances D(AI), and the set S of all the possibilities reachable from D('i) with a nite sequence of action instances be given. The transition function : D(AI) S ! S [ f;g for the (un)trustworthy announcement relative to D is de ned as follows.
De nition 6 (mA (un)trustworthy announcement transition function). Allow us to use the compact notation u(F ) = ff j f 2 D(F ) ^ u j= fg [ f:f j f 2 D(F ) ^ u 6j= fg for the sake of readability. Let an action instance ahagi 2 D(AI) where agent ag 2 D(AG) announces the uent formula and a possibility u 2 S be given.
If a is not executable in u, then
(a; u) = ; otherwise (a; u) = u0, where: with (a; w) = w0 such that
Intuitively this transition function allows, through the use of and , to model
the idea that the untrusty agents maintain their beliefs while knowing that the
trusty ones updated their point of view of the \physical world" (and viceversa).
An example of execution As mentioned above, we will provide a
graphical representation of the newly introduced transition function. Following [
Oann a.
Example 2 (Five Agents Trust Grapevine).
The example has ve agents: A, B, C, D and E;
A, B, C are located in the same room (room 1) while D is in a room (room 2) adjacent to room 1 and E is located in room 3, not adjacent to room 1; Agents B and D trust A while C and E do not; Agent A knows secret a; The value of secret a is true;
Initially everyone knows the position of each agent and that only A knows the value of secret a.
Let us now present a graphical representation of the above described initial state, in Figure 1.
In Figure 2 instead we represent the e-state generated after the execution of the (un)trustworthy announcement action instance announce secret ahAi (ann a for brevity). In ann a A announces the value of secret a. Let us note that from the position of the agents we know that A, B, C 2 Fann a, D 2 Pann a and E 2 fEg
fC,Dg In De ntion 6 we assumed that an agent agi, that does not trust the announcer, will not change her beliefs about what has been announced. That is, an untrusty agent will not change her perspective on the \physical" state of the world. Let us notice that this type of trust captures the idea that, for the untrusty agents, the announcer is not reliable and the information she is providing is not worth taking into consideration as it can be not accurate.
Depending on the scenario it could be necessary to model a stronger concept of untrust. In particular, it could be required to design an (un)trustworthy announcement such that the untrusty agents will believe the contrary of what has been announced (while still believing that the announcer believes what she announced). We will call this type of action (mis)trustworthy announcement . The formalization of such variation of the action presented in De ntion 6 is as follows.
De nition 7 (mA (mis)trustworthy announcement transition function). Let an action instance ahagi 2 D(AI) where agent ag 2 D(AG) announces the uent formula and a possibility u 2 S be given. If a is not executable in u, then (a; u) = ; otherwise (a; u) = u0, where: with (a; w) = w0 such that and (a; w) = w0 such that
Let us note that the transition functions introduced in De nitions 6 and 7 only di er in the speci cation of and for the untrusty fully observant agents. This di erence is needed to represent the fact that in the case of (un)trustworthy announcement the untrusty agents maintain their beliefs while in the (mis)trustworthy one they will believe the opposite of what has been announced.
An example of execution As for the (un)trustworthy announcement , we will provide an example of (mis)trustworthy announcement execution. The initial state is identical the one introduced in Example 2. The only di erence is that now the action announce secret ahAi (or ann a for brevity) is a (mis)trustworthy announcement instead of a (un)trustworthy announcement . The initial state is, therefore, represented in Figure 1 while the e-state obtained after the execution of the (mis)trustworthy announcement is shown in Figure 3.
fA,B,Dg fEg
fC,Dg
In [
e j= By =By: =(:By ^ :By: ); 6. for every agent y 2 Oa and a belief formula ', e0 j= By' i e j= By'; and 7. for every pair of agents x 2 Fa [ Ua [ Pa and y 2 Oa and a belief formula ', if e j= BxBy' then e0 j= BxBy'.
The properties presented in Proposition 1 try to capture some fundamental aspects of an (un)trustworthy announcement action. Intuitively: 1. Captures the idea that all the trusty fully observant agents should believe i) what has been announced; and ii) that all the other trusty fully observant agents believe what has been announced and so on ad in nitum (that is why we use the C operator). 2. Models the fact that all the untrusty agents believe that all the trusty ones have common belief on what has been announced. 3. Captures that the partially observants believe that the trusty fully observants have common knowledge on what has been announced while the partially observants themselves do not know the announced value. 4. States that the fully observant agents have common knowledge on the previous property. 5. Models the idea that all the untrusty agents do not modify their beliefs about the announced values. 6. Captures the fact that the oblivious agents do not change their beliefs. 7. States that the observant agents (trusty, untrusty and partial) believe that the oblivious agents did not change their beliefs.
As we did for the (un)trustworthy announcement , let us identify some properties also for the (mis)trustworthy announcement action.
Proposition 2 ((mis)Trustworthy announcement properties). Let ahagi be a (mis)trustworthy announcement action instance where ag m announces . Let e be an e-state and let e0 be its updated version (that is, (a; e) = e0), then in mA properties 1; 2; 3; 4; 6 and 7 of Proposition 1 hold. In addition, a. e0 j= CUa : ; c. e0 j= CPa (CUa _ CUa : );
b. e0 j= CFa (CUa : ); Proposition 2 describes the core ideas behind a (mis)trustworthy announcement action. While properties 1; 2; 3; 4; 6 of Proposition 1 have already been described, the intuitive meaning of the remaining ones is as follows. a. Captures the idea that all the untrusty fully observant agents should believe i) the contrary of what has been announced; and ii) that all the other untrusty fully observant agents believe the negation of what has been announced and so on ad in nitum (that is why we use the C operator). b. Models the fact that all the trusty agents believe that all the untrusty ones have common belief on the negation of what as been announced. c. Captures that the partially observants believe that the untrusty fully observant have common knowledge on what has been announced, while the partially observant themselves do not know the announced value. 5
In this paper we introduced the notion of trust in the eld of multi-agent epistemic planning. In particular, we provided a formalization for two actions, i.e., (un)trustworthy announcement and (mis)trustworthy announcement , that model two di erent scenarios of information sharing when the concept of trust is involved. The former action captures the idea that whenever an agent does not trust another she considers the announcer as an unreliable source of information, and therefore does not change her beliefs about the world. The latter, on the other hand, describes the situation where the untrusty agents will believe the contrary of what has been announced while still believing that the announcer believes what she announced. Both of the newly presented actions have been formalized for, at the best of our knowledge, the most comprehensive epistemic action-based language: mA . In particular, in Section 4 we presented the transition functions of the actions along with their desired properties (formally demonstrated in the Supplementary Documentation).
As already mentioned, the idea of trust is presented as static and globally
visible. While making it dynamic would not increase the \di culty" of the
transition functions, allowing each agent to have her own point of view on the trust
relations would require a redesign of the e-state updates. In particular, to
formalize this type of trust, the idea of non-consistent belief is necessary. Since such
concept is still an open issue in the MEP community, we leave the formalization
of e-state update when trust depends on the agents' point of view as future work.
Finally, another concept that arises when trust is taken into consideration is the
idea of lies. Modeling this concept would require major modi cations of De
ntion 6 and, as for the dynamic version of trust, the idea of non-consistent belief.
Capturing subtle concepts such as lies and misconception is not straightforward
and will provide a contribution on its own. The di culty of characterizing such
ideas derives from the complexity of devising a transition function that correctly
captures all the possible nested beliefs of the domain's agents. We, therefore,
leave the investigation of lies as future work. A more immediate future work is
the introduction of the new actions in EFP 2.0 [
The author wishes to thank Dovier Agostino, Pontelli Enrico and Burigana Alessandro for the illuminating discussions on epistemology and the anonymous Reviewers for their comments that allowed to improve the presentation.
This research is partially supported by the Universita di Udine PRID ENCASE project, and by GNCS-INdAM 2017{2020 projects.