Current agents use communication in a collaborative setting, exchanging truthful information to achieve a common plan. This paper defines games where agents may exchange information about the physical situation (both fluents a nd action events), arbitrarily nested beliefs, and action consequences, to manipulate other agents for their own goals, i.e. guide the other agents' own reasoning and planning. We propose a model for an ”agent mind” that can cater for all these aspects through revisable, prioritized belief bases; goal recognition including epistemic situations; or planning including speech acts with structured content. We also discuss recent algorithms to address each one of them, and propose a concrete implementation for a future stage.
We define m anipulation g ames a s g amesi n w hich players not only affect some shared physical state, but also exchange information in the hope of influencing t he o ther p layers so their goals can be achieved. Goals are often hidden from other players, and may or may not be conflicting. Observability is often restricted, and information can only be gained through third-party accounts. In this paper, we propose an action language specification and a doxastic model to reason about and share both actions and beliefs that enable manipulation of agents in games. Not all aspects of reasoning (e.g. fully reasoning about actions, or the planning of actions itself) have been implemented in source code, but suitable alternatives have been identified f or e ach o f t he p rocesses in the model.
Interactions with NPCs in RPG-like games can be modelled as non-zero sum games with hidden goals. Although there are sources of knowledge, stemming from observability (either an agent observes a situation or another agent directly), most information is more or less grounded belief, specially about the beliefs and motivations of other agents. Since only actions can be truthfully observed, intent and plan recognition are the only ways to estimate what another agent wants and believes, so the agent can adjust their own plans. After these models are built, one agent can plan to provide such information that other agents conclude beliefs or take actions in a way that benefits the planning agent. We need to consider such capabilities as: • Reasoning and representation: reason about predicates with open world assumptions with a base of prioritized beliefs, and represent communicative actions • Goals, goal recognition and goal recognition design: find out about other agents’ plans to guide the planning • Discourse and action planning: plan actions and predicates to communicate to indirectly guide other agents’ actions
Agents, in fact, assume that all of them perform the same loop when facing a change in the environment: first nonobvious predicates are deduced from existing and new information; then the goals of the agents involved in the new situation are re-assessed; and then current actions are re-planned, or new actions are planned. The classic game Diplomacy, in fact, restricts its mechanics in such a degree that these mechanisms are the basis for the game.
A related field, from which we borrow, is that of
persuasion and argumentation theory. A description of how
automated planning techniques can be used to promote
arguments can be found in
people1 Let us consider a sample fantasy RPG scenario with three actors: Aisha, Bo Yang and Chinira. The three of them are officers in the same army, and Chinira is the common boss of Aisha and Bo Yang.
Aisha has currently a goal of recovering the McGuffin of
Diabolic Wisdom, which she hid in the common room of
1A humble tribute to
During the paper we will show a formal description of the messages exchanged, and the beliefs and plans generated by the agents within bounding boxes.
This framework is very similar to a BDI architecture
Horswill’s MKULTRA
Ryan’s Talk of the Town
Within the automated planning community, epistemic
planning (taking the epistemic state of other agents into
consideration) has become so important as to have a dedicated
workshop in ICAPS 2020
(https://icaps20subpages.icapsconference.org/workshops/epip/). The work in (Shvo et al.
2020) includes epistemic plan recognition (which includes
epistemic planning itself) leveraging the planners in
Multi agent systems such as
As we have mentioned before, each agent performs a loop of goal recognition and sensing followed by action planning, supported by doxastic reasoning, in a variation of the traditional Sense-Plan-Act loop.
The internal model of each agent, as illustrated in Figure 1, consists of a prioritized and time-versioned belief base including certain knowledge (sensing actions), a list of internal goals and associated plans, and a set of agent models with the same structure, rebuilt whenever new information is added. The state is updated by processes of belief insertion, planning, goal recognition and higher order epistemic reasoning, as described in the rest of the paper.
Dynamic Epistemic Logic has often been used to model
reasoning of higher order beliefs such as those that can
be expressed in this model. It is a formalism describing
epistemic states and their changes after executing actions,
which has experienced a substantial growth in the last 15
years. A very complete account of its evolution from
public announcement logics to its current form can be found in
However, we have found two important shortcomings in
this family of logics:
• it puts the burden on the problem to fully specify the
initial model;
• it models actions as semantic changes that directly modify
this model, without few guidelines about what conditions
should the actions fulfill to preserve model properties (e.g.
KD45 for belief or S5 for knowledge) across updates, as
Herzig has pointed out in
Hence, we have decided to focus on actions with
syntactic effects as much as possible (e.g. forcing as a result that
A believes in p after an action), so the user of the model
needs to build partial models from the acting agent’s point of
view using techniques like tableaux whenever it is necessary,
adding computational burden at the expense of flexibility.
We have nonetheless studied the formalization of prioritized
belief bases from a DEL perspective as described in
The doxastic model proposed consists of prioritized belief
bases as described in
These structures are more succinct than, for example, POMDP models, since they use logic sentences to express sets of worlds, and human agents tend to use vaguely defined confidence or plausibility levels instead of exact probabilities.
Sentences in such a model keep track of their origin, such as: • Past direct observations. A belief could be implicitly formed about the current situation depending on a state that was observable in the past, but not anymore, with its plausibility degrading with time up to complete uncertainty being removed from the belief base. • Accounts from other agents, accepted according to observed certainties and the perceived ”honesty record” of other agents. • Abduction, mainly targeted at action reasoning, so causes will be ordered according to their plausibility depending on the simplicity of their attributions to effects. • Induction, for agents that perform some kind of statistical analysis of observed facts.
Note that the current paper does not propose explicit mechanisms for the inclusion of a belief in the base, apart from these suggestions.
A version timeline of the belief base is kept, so past and point temporal modalities like AT(t=3)(p) can be used to refer to any (including the acting) agent’s beliefs. Deduced propositions are indirectly referenced whenever a check using a tableau starts.
We allow the following types of predicates in the belief base: • first order predicates; e.g. has(B; knif e) • visibility statements of first order predicates; e.g. see(A; has(B; knif e)) • temporal statements of any other item; e.g. ATt=3(has (B; knif e)) • goal statements about agents; e.g. GOALA(catch killer) • statements about actions with preconditions and postconditions, with probabilistic outcomes; e.g. search roomfpre : empty(room 123); post : ft := t + 3 with p = 1; in(knif e; room 123) with p = 0:5; :in(knif e; room 123) with p = 0:5gg • predicates that express that an action has just been performed; e.g. done(fired(A; B)) • beliefs from other agents; e.g. BA(is killer(B))
Special predicates like those described in
To allow some approximation to probabilistic reasoning, plausibilities are related to discrete probabilities. Values from 0 to 2n, expressing probabilities from 0 to 1, are used. Operations that would result in intermediate values are rounded towards 2(n 1), a probability of 0.5. This value is important since it represents uncertainty, and as such can be removed from the belief base. We expect long term reasoning to be ”diluted” in this way to control state explosion, since the further a result is in terms of operations (e.g. a situation several steps ahead in a plan), the more probable it is to turn into an uncertainty. In no way are complex probabilistic logic frameworks (e.g. Markov logic networks) involved in these estimations: derived statements always inherit the least plausible value from those among all the input statements.
In Figure 2 we can see a prioritized belief base consisting of three layers, each with a certain plausibility. In this example, we will use a value of 0 to 16 levels of probability, with a plausibility of 0 corresponding to a probability of 1, and 8 corresponding to complete uncertainty (50/50 estimation), and therefore not represented. Note that believing p with plausibility plaus higher than 8 is equivalent to believing :p with plausibility 16 plaus. In the example, we see levels of plausibility from 1 to 6, that would correspond to probabilities 15 (almost certain) to 196 (more likely than not).
16 Note that certain knowledge is assumed to come only from direct observation in the current moment, so it is tracked separately. This structure induces a system of spheres, where each sphere includes layers from the base incrementally, as long as the sentences from a less plausible layer do not contradict those from a more plausible one. Let us see what spheres would be induced by this base: • Plausibility 1 / Probability 1156 : all worlds complying with p; q _ r (e.g. pqrst; pqrst; pqrst) • Plausibility 3 / Probability 1126 : all worlds complying with p; q; s t (e.g. pqrst; pqrst), within the previous sphere The last layer contradicts previous, more plausible beliefs, and therefore does not induce any layer.
Keeping past states of this base and referring to them using dedicated past and point modalities allows us nonmonotonic reasoning, since only new beliefs are added to the base, as all beliefs are implicitly tagged with the moment in which they were believed. A belief in p is not replaced, but rather it is asserted that ATt=3:p but also ATt=6p.
First-hand, certain knowledge is handled apart from belief. This may exclude certain scenarios of misunderstandings: the step where an agent creates a false belief from a truthful observation. In the film ”Knives Out”, Great Nana mistakes character Marta for another, even though Marta is standing at plain sight in front of her. Marta then derives the incorrect belief that Great Nana has recognized her, since this model takes a ”sensing” action by another agent as something about which we can have certain knowledge (and we see how this may not always be the case).
Actions are first class objects in the language.
Preconditions and postconditions can be communicated and they are
certainly used in planning, but in no way are they
considered immutable or fixed. This has already been described in
The postconditions of actions can have three different natures, as summarized in 3: • ontic, e.g. open(door). The specification for ontic (physical) actions is very similar to traditional specification in STRIPS planning: a list of set/unset atomic predicates. • epistemic, e.g. see(B; open(door)). Epistemic effects are tracked through observability predicates, as opposed to epistemic model modification as in logics in the DEL family, due to the issues of semantic action models as explained before. Note that observability itself is directly observable and applicable (we know for sure whether agent A sees something if we see them), and hence is an epistemic, not doxastic, effect. • doxastic, e.g. BB(GOALA(out(A; room))). These effects can be computed using doxastic logic and goal recognition, as will be detailed later, and therefore depend on what the acting agent believes about the other agents; these complex effects will need to be evaluated again in every individual planning step, and may of course be incorrect if the higher order beliefs are themselves incorrect.
An agent may communicate action specifications
(preconditions and effects). Both linear and contingent action plans
can be communicated as composite actions using sequence
(;), nondeterministic ([) and test (?) operators as in dynamic
logics (e.g. as described in
We consider the following basic actions in our framework: • Perform an action with pure ontic or epistemic effects; e.g. fire(E; D) • Say a proposition to a set of agents; e.g. say(A; "9X ATt=3(done(fire(X; D)))"; fB; Cg), which means that A says to B and C that someone fired upon D at t=3. • Ask an agent about something to a set of agents, that is, check the validity of a statement or request a value for the free variables in a statement that makes it true according to their beliefs, e.g. ask(A; "ATt=3(done(fire(E; D)))"; fg; fB; Cg or ask(A; "ATt=3(done(fire(X; D)))"; fXg; fB; Cg • Request an agent to do somehing, e.g. request(A; "ask(B; "BELC (ATt=3(done(fire(X; D)))"; fXg; fCg"; fBg)
Internal actions are considered in planning, but they are not modelled as communicative acts. The reason is that they are clear enough to be modelled by each agent, and also known to happen whenever enough information is provided (a goal may be recognized as soon as there is evidence for it). There is no need to communicate anything about internal actions because all agents have enough stable knowledge to reason about them, even though the specific treatment of each agent of course depends on their beliefs. Agents however need to have a bounded rationality, so we cannot rely on other agents to come to conclusions, even though they may be logically valid.
Aisha provides Chinira with the information that an incoming squad includes a spirit, vulnerable to a ritual from a certain book. This information comes from Deepak, an unreliable source, but Aisha hides this uncertainty from the message to let Chinira draw her own conclusions.
A say(8X(in(patrol; X) ) BX (in(squad; spirit)))) Chinira incorporates Aisha’s account with high plausibility in their prioritized belief base based on a previous track record of complete and accurate information. A lower plausibility could have been assigned if e.g. induction had shown that information from source Aisha is not reliable when checked against facts. Also, a higher, conflicting evidence already present (e.g. the report from an inside informant) would also have invalidated Aisha’s information due to the construction of the spheres from the base. Using a simple breadth-first search, Chinira decides to request Bo Yang to stay in the garrison while she goes with her own squad to the ruins where this book is located, as other actions (sending Aisha or Bo Yang, perceived as inferiors; using some other strategy against the spirit; not doing anything in the hope of the spirit posing a lesser threat) would pay a lower performance/cost balance, always according to her current beliefs.
C in(squad; spirit) : plaus 1
request(C; request(A; stay()); B); fAg)
Beliefs and goals are not directly observable: an agent can only infer them in another agent through observation of their behaviors. Goal recognition is, thus, a very important piece of manipulation games. Whether an action is taken or not depends on the beliefs about preconditions and effects, and whether the effects lead to a goal. Goal recognition is a kind of abduction process, where agents’ goals are deemed the most probable or concise explanation for those agents’ actions. To illustrate the importance of goals and goal recognition, let us take the muddy children puzzle, a staple in dynamic epistemic logic. Agents need to assume that everyone’s goal includes a truthful account of their observations. Without this assumption, for example with a lying agent, the puzzle cannot proceed.
The current section only describes the open issue of the need for goal recognition mechanisms to compute doxastic preconditions of actions in a setting where these include speech acts like saying, asking or requesting, and beliefs of other agents may not match the contents of such statements. We do identify some algorithms as potential candidates for implementation.
We approach the concepts of desire and intention from
BDI logics
In Figure 4 we can see two observed steps, with two possible plan completions to different goals. We can rule out the goal in white, due to the second event observed. However, without some evidence pointing towards one of the greypatterned goals, we cannot predict further actions.
It is worth mentioning Geib’s PHATT algorithm as
described in
A further concept in automated planning is goal
recognition design, whereby some action is designed to make an
agent’s goals as easy to discover as possible, as described
in
Ontic actions can be planned using planners that can
handle a probabilistic outcome using the action specifications
stored in the agent’s belief base, like probabilistic planners
or a deterministic planner with replanning like
However, a complication for communicative actions in our setting is that traditional agent frameworks are oriented toward collaborative agents. Feasibility preconditions express a socially agreed reason to why the action is performed, but in fact nothing prevents an agent to say whatever it wants. Furthermore, when seen from the perspective of the ”sender”, a communicative act may be issued precisely to guide the goal recognition process in the ”receiver” towards a certain goal or plan. The possession or not of a certain knowledge does not enable us to ask a question; rather, our goal of reducing uncertainty or of making another agent believe that one does not know something is what will compel us toward that action. In a similar way, evaluating the outcome of a communicative action needs to take goals into account.
Postconditions in communicative actions become complicated to compute: the sender has to try and replicate a goal recognition step, using the receiver’s beliefs about the sender and goals to the extent to the sender itself ’s belief, and then try to predict what will the receiver belief about the sender’s intentions. Note that even ontic actions may carry a doxastic effect, in the sense that any action is framed within an estimation of goals. Opening a door is evidence for the other agent to have run through it, but it may have been left open on purpose to lure the observer into that conclusion. We believe that the increase in memory and computation power of user equipment justifies exploring this modelling. As mentioned before, re-planning or MCTS techniques in automated planning have yielded satisfactory results.
Selecting the content to present in a speech act can be guided by bulding a model for the receiver, including goals and beliefs, so candidates for items in sentences can be proposed from incomplete proofs (e.g. whether they can close open branches in a tableaux) or plans (e.g. communicating action preconditions to the receiver, regardless of their actual truth) that are related to the current goals. The whole loop of goal recognition, reasoning and planning is performed in the simulated model for the other agent, to the extent to which resources can be dedicated. If we belief that
lows it to plan further actions, like asking B for the knife. If we believe that BA(8X(has(X; knif e) ) is killer(X))) this information item is a particularly powerful lever to guide A’s actions.
Some authors use existing planners adapted with
epistemic predicates. For example
Aisha then takes Chinira’s request to Bo Yang. However, she mentions Deepak when mentioning the patrol report to Bo Yang. When issuing Chinira’s request, Aisha does not reveal how Chinira has come to this conclusion, but she makes it clear that it comes from Chinira.
A say(BD(in(squad; spirit))) say(done(request(C; request(A; stay(); fBg); fAg))) request(A; stay(); fBg)
The specification language for higher order epistemic actions would allow Bo Yang to examine a possible plan where Aisha’s goal is represented and this observation is matched, but goal probability priors would rank the corresponding goal fairly lower than alternative goals from other agents, or would have too many unknown factors. Bo Yang may suspect that 9X(GOALX (:in(B; city))), but he would not be able to progress the reasoning much further without a lot of time consuming sensing actions. Bo Yang believes Aisha to be a loyal individual due again to induction from past observations. A more plausible goal at play is assuming that Bo Yang has the goal of impressing higher officers (a wrong belief that has nonetheless crept up high in Bo Yang’s prioritized belief base due to previous interactions with Aisha) by recovering the book and keeping him in the garrison. Bo Yang decides instead to face the incoming army (as he cannot go for the book himself and clash with Chinira, staying would result in a loss of face, and no sentence could possibly land higher in Chinira’s belief base to change their mind in Bo Yang’s belief). This results in Bo Yang’s soldiers leaving their barracks for a few days.
B :in(squad; spirit) : plaus 4
We have presented a definition for games of manipulation, as games with open communication and unknown goals, whose players use models of other agents to guide their actions. We have pointed out at three aspects that enable these games: doxastic higher order reasoning, goal recognition, and epistemic planning. For each of these areas we have identified alternatives for data structures and algorithms that can support these aspects. In future communications we plan to present prototypes for each of them.