We investigate methods for accommodating both agent-actions and events outside the control of an agent for updating an agent's belief state. Update via the mixture of actions and events seems not to have enjoyed much attention in the literature. The framework we consider assumes given, a probability distribution over worlds thought possible, event likelihoods, state transition likelihoods and observation likelihoods. We present three methods: (i) trading off update due to agent actions, and update due to exogenous events via a measure of observation endogeny, (ii) a more direct mixture of expected action and event effects and (iii) employing a causal network involving actions and event.
When an agent performs an action, it expects its surroundings to change due to the effects of the action. An agent might also notice that its surroundings have changed, but not due to one of its own actions, but due to some exogenous event. Or the surroundings might have changed due to a chain of (indirect) effects of some action the agent performed in the past. The agent could have an idea as to the likelihood of particular actions and events happening in different situations. And the agent could have knowledge about the correctness of observations it makes in different situations.
Although agent-actions and events-from-outside (including actions performed by other agents) frequently occur simultaneously, there is very little literature attempting to formalize how an agent should update its beliefs in such cases. There is more literature discussing belief update for purely agent actions (e.g. the literature on Markov decision processes) or purely exogenous events (e.g. the literature on Bayesian networks).
In this work, we assume that an agent has a probability distribution over the possible states it can be in. We then want to answer the question, what is the agent’s new distribution over states, given that it executed a particular action while some (exogenous) events simultaneously occurred and a particular observation is made shortly thereafter?
For instance, if monsters leave the forest when a fire is lit, and you can light a fire (agent action) and someone else can light a fire (event) and the monsters can leave the forest (event), then what should you believe after lighting a fire while knowing that there is a probability that someone else has also lit a fire, there is a probability that the monsters will leave the forest anyway and you think you hear the monsters leaving (observation)?
In this paper, we present three methods to combine knowledge of actions and events for probabilistic belief update. All of the uncertainties about an agent’s environment models may be represented by probabilities of the occurrence of actions, events, effects and observations in the different possible situations. The first method computes a measure of the degree to which an agent believes that the observation it received is the effect of its own action. The agent then updates its beliefs by trading off action update and event update using this measure. The second method assumes that updating due to actions and updating due to events should not be separate but should be more integrated. The third method deals more realistically with the causal relationships between all actions and events. The other two methods do not allow for the explicit modeling of causal relationships.
We start off by covering the necessary technical background, including the basic framework: the language and probabilistic models an agent is assumed to have. Given the formal framework, we are then ready to specify an example scenario to be used throughout the rest of the paper. In Section 4, the three methods of update are presented. Section 5 discusses related work and Section 6 summarizes the findings and looks to future work. 2
Each world feature and environment event may be either true (present in the world,
resp., occurred) or false (absent from the world, resp., did not occur). A valuation
function assigns true (1) or false (0) to each feature or event. Let W be the set of
valuation functions (aka, possible worlds) over world features F , such that for every
function/possible world w 2 W , w assigns either true or false to each feature in F . And
let X be the set of valuation functions (aka, atomic events) over environment events
G, such that for every function/atomic event e 2 X , e assigns either true or false to
each (primitive) event in G. Let L be the classical propositional language induced
from F using conjunction (^ ), disjunction (_ ) and negation (¬). Let ⌦ ✓ L be a set
of observations the agent is interested in. An agent has the following environment
models.1
1 Environment models will have to be learned by the agent or supplied by a knowledge
engineer during the agent design process.
– E : X ⇥ W ! [
Finally, an agent maintains its beliefs using a belief state (probability distribution)
B : W ! [
We say that a sentence 2 L is satisfied by a world w 2 W (denoted w ç ) iff it is true when evaluated under w according to the classical laws of logic. The set of worlds satisfying is denoted as Mod( ). We define satisfaction of primitive event ✏ 2 G evaluated under atomic event e 2 X similarly. When e satisfies ✏ , we denote it as e ç ✏ . We may write a instead of ¬a, and a b instead of a ^ b. A belief state {(w1, p1), (w2, p2), . . . , (wn, pn)} might be written more compactly as h p1, p2, . . . , pni , where for F = {q, r, s}, w1 ç q ^ r ^ s, w2 ç q ^ r ^ ¬ s, . . . , w8 ç ¬q ^ ¬ r ^ ¬ s. 3
Consider the following scenario as a running example.
There is a forest in which a wizard and a witch live. There are also orcs (monsters) living in the area. The orcs move in and out of the forest. Wherever they are, the orcs cause all sorts of mischief. When the orcs get close to the wizard, he sometimes lights a magical fire, at which time they usually leave the forest. The witch also has a magical fire for chasing the orcs away. When the orcs are chased out of the forest, they give an indignant cry. In this example, we are interested in the wizard’s mindset.
To represent belief states more compactly, we use the form (a, b, c, d, p) 2 B instead of (w, p) 2 B such that w ç ¬a ^ b ^ ¬ c ^ d. Let the wizard’s vocabulary be – F = { fwiz, fwch, io, co} where the features have the following respective meanings: the wizard’s fire is lit, the witch’s fire is lit, the orcs are in the forest, the orcs have just cried out. – G = {`wch, n, x } with respective meanings: the witch lit her fire, the orcs entered the forest, the orcs exited the forest.
– A = {`wiz} meaning the wizard has the single action to light his fire. Atomic events `wch, n, x and `wch, n, x are not considered; orcs cannot both enter and exit the forest.
The wizard uses only worlds in which features fwiz, fwch and io are considered. Let the wizard initially believe to a relatively high degree that no fires are lit and the orcs are in the forest. Let the wizard initially believe to a lesser degree that no fires are lit and the orcs are outside the forest. The wizard believes only to a low degree that only the witch’s fire is lite. This initial belief state B can be written as (w, 0.75) 2 B : w ç fwiz ^ fwch ^ io (w, 0.05) 2 B : w ç fwiz ^ fwch ^ io (w, 0.15) 2 B : w ç fwiz ^ fwch ^ io (w, 0.05) 2 B : w ç fwiz ^ fwch ^ io and for all other worlds w 2 W , B(w) = 0. This implies that B( fwiz) = 0, B( fwch) = 0.1, B(i f ) = 0.8 and B(co) = 0. Let the possible observations be ⌦ = {co, ¬co}.
All the environment models are defined in the following tables. Unfortunately, textual explanations are unlikely to clarify the definitions, because the functions were worked out separately for each combination of arguments. This was a knowledge engineering exercise, with probabilities assigned purely according to the first author’s subjective idea about how such a scenario might behave and according to the axioms of probability.
The wizard’s event likelihood function E(e, w) is defined as follows. @w fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio e @ `wchnx 0 0 0 0 0 0 0 0.1 `wchnx 0 0 0.5 0 0 0 0.3 0 `wchnx 0 0 0.1 0.5 0.1 0 0.4 0.2 `wchnx 0 0 0 0.2 0 0.4 0 0.3 `wchnx 1 0 0.3 0 0.6 0 0.2 0 `wchnx 0 1 0.1 0.3 0.3 0.6 0.1 0.4 For all worlds such that w ç fwiz ^ fwch ^ io, T(w, ae, w0) is defined as HHHHw0 fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio ae For all worlds such that w ç fwiz ^ fwch ^ io, T(w, ae, w0) is defined as HHHHw0 fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio ae `wiz `wchnx `wchnx `wchnx `wchnx `wchnx `wchnx `wiz `wchnx `wchnx `wchnx `wchnx `wchnx `wchnx `wiz `wchnx `wchnx `wchnx `wchnx `wchnx `wchnx worlds such that w ç fwiz ^ fwch ^ io
HHHHw0 fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio fwiz fwchio ae For all worlds such that w ç fwiz ^ fwch ^ io, T (w, ae, w0) is defined as The wizard’s observation function O(co, ae, w) is defined as
We say that an observation is exogenous (w.r.t. an agent) when it is caused by an event outside the control of the agent, and an observation is endogenous (w.r.t. an agent) when the observation is due to a recent agent action.
Suppose we know what observation to expect as an effect of an action just executed by an agent. Call that observation . And suppose that the agent actually perceives ↵ . Our reasoning is that the less similar ↵ is to , the more likely it is that ↵ is an effect of some outside (exogenous) event, that is, not due to the agent’s recent action. Intuitively, if the actual observation is completely unexpected, then the agent should update its beliefs as if some environmental event had just occurred. Also intuitively, if the actual observation completely matches what the agent expects due to its most recent action, then the observation should be fully associated with the action and update should proceed as in traditional state estimation (due to a known action).
We thus measure the degree of endogeny of observation ↵ as the degree of similarity of ↵ to the expected observation . In this work, observations are logical propositions. The question thus becomes, how can one compute the degree of similarity between two propositions ↵ and ?
We shall base the degree of similarity on the number of worlds on which the two proposition correspond. This amount is adjusted by the total number of worlds under consideration. For instance, assume that Mod(↵ ) and Mod( ) overlap with one world, and assume that Mod(↵ ) and Mod( ) also overlap with one world. Now assume further that |Mod(↵ )| = 2, |Mod( )| = 2 and |Mod( )| = 4. Then we should consider more similar to ↵ than .
Let the similarity between two proposition be define as follows.
S(↵ , ) =. |Mod(↵ ) \ Mod( )| .
|Mod(↵ ) [ Mod( )| Notice that S is symmetrical, that is, S(↵ , ) = S( , ↵ ) for all ↵ , 2 ⌦ .
Another approach towards defining similarity explicitly counts non-corresponding worlds, and normalizes the final count to fall within 0 and 1: The count is the number of -worlds in Mod(↵ ) minus the number of -worlds in Mod(¬↵ ). The general approach for this kind of normalization is to subtract the minimum possible count (which could be negative in this case) from the total count, and then divide it by the difference between the minimum and maximum counts.
be the number of -worlds in Mod( ). Then
.
S0(↵ , ) = ↵ ¬↵
( |Mod(↵ )| ( ¬↵ ) ¬↵ ) .
Note that the maximum count is |Mod(↵ )| and the minimum is ¬↵ .
Proposition 1. S(↵ , ) = S0(↵ , ).
↵ ¬↵ ( ¬¬↵↵ )) = |Mod(↵ )↵|+ ¬↵ . And note that ↵ = |Mod(↵ )\
PMroodo(f. N)|oatnedthtahtaSt0|(M↵o,d()↵ =)| |+Mod(¬↵↵)| =( |Mod(↵ )| + |(Mod( ) \ Mod(¬↵ ))| = |Mod(↵ ) [
Mod( )|.
190I1t,ttuornmseoausutrtehatthe||XX s[\iYYm|| ,ilwarhiteyreofXpalanndtsYbayrethseet(sn,owr masadliezfiedn)ednubmybPearuloJfaccocmarmdoinn
features they display [
As an example, suppose the vocabulary is { fwiz, fwch, io}. Note that3 – Mod( fwiz ^ fwch) = {111, 110}, – Mod( fwch) = {111, 110, 011, 010}, – Mod(io) = {111, 101, 011, 001}.
Thus, S( fwiz ^ fwch, fwch) = 2/4 = 1/2 and S( fwiz ^ fwch, io) = 1/5 and S( fwiz ^ fwch, ¬ fwch) = 0/4 = 0 and S( fwiz ^ fwch, fwiz ^ fwch) = 2/2 = 1.
In the context of this work, an agent does not expect a particular observation, given an executed action in a belief state. Rather, an agent has different degrees of belief for each of the observations it could possibly receive. The probability of observation is
P r( | a, B) = X X B(w)T (w, a, w0)O( , a, w0).
w02 W w2 W
We are now ready to define the expected endogeny of observation after executing action a in belief state B. received 2 The measure is apparently known by different names: Jaccard index, Intersection over Union and Jaccard similarity coefficient (https://en.wikipedia.org/wiki/Jaccard_index). 3 Here, worlds are represented by strings corresponding to their truth assignments.
EEndo( , a, B) =. X P r( | a, B)S( , ).
2 ⌦
Expected exogeny of observation received after executing action a in belief state B will be defined as 1 EEndo( , a, B).
Definition 4. Let B be a belief state, a an action in A and endogenous update operator endo is defined as be a sentence in L. The Baen,do =. ¶(w0, p) | w0 2 W, p = ⇥O( , a, w0) X B(w)T (w, a, w0)⇤©, w2 W where := 1/ X O( , a, w0) X B(w)T (w, a, w0).
w02 W w2 W Here and in the rest of the paper, denotes a normalizing factor.
Definition 5. Let B be a belief state and operator exo is defined as be a sentence in L. The exogenous update Bexo =. ¶(w0, p) | w0 2 W, p = ⇥ X O( , e, w0) X B(w)E(e, w)T (w, e, w0)⇤©.
e2 X w2 W An agent uses exo when it knows that observation is not (directly) due to the effects of one of its (recent) actions. The agent assumes that is due to some event in the environment, but because of the uncertainty about which events occur in which worlds, it maintains a probability distribution E over event occurrences, given a world (for all worlds).
Given Definition 3, we can generalize (endogenous) state estimation to incorporate the effects of (exogenous) events occurring in nature. We define Ba, as the mixture of endogenous update and exogenous update using expected endogeny as the trade-off factor.
Ba, =. ¶(w0, p) | w0 2 W,
p = EEndo( , a, B) · Baen,do(w0) + (1 EEndo( , a, B)) · Bexo(w0)©.
We now compute B`wiz,co and B`wiz,¬co . It turns out that – EEndo(co, `wiz, B) = 0.28, – Bendo – B`ewxioz,c=o =h0h .01.45,20,.04.40,90,.00.23,40,.00.30,50,.00.70,00,.03.10,00,.00.00,00,.00.00i 0, i , co – EEndo(¬co, `wiz, B) = 0.72, – Bendo – B`¬ewxciooz,¬=co h =0.2h00.,103.0,02.,302.1,0,0.2.104,0,0.3.242,0,0.0.007,0,0.0.100,0,0.0.106,0i..00i ,
B`wiz,co = h 0.24, 0.34, 0.11, 0.04, 0.05, 0.22, 0.00, 0.00i B`wiz,¬co = h 0.15, 0.24, 0.17, 0.29, 0.06, 0.02, 0.03, 0.04i .
Another approach is to think of actions and events truly occurring simultaneously. Let T (w, a, e, w0) be the probability of a transition from world w to world w0, given action a is performed and event e occurs. And let O( , a, e, w0) be the probability of perceiving in w0, given action a is performed and event e occurs. Update could then be defined as follows.
BaH, =. ¶(w0, p) | w0 2 W, p = ⇥ X O( , a, e, w0) X B(w)E(e, w)T (w, a, e, w0)⇤©.
e2 X w2 W
If one assumes that actions and events are independent, then T (w, a, e, w0) can be replaced with T (w, a, w0)T (w, e, w0), and O( , a, e, w0) can be replaced with O( , a, w0)O( , e, w0), and normalizing factor is adjusted accordingly.4
With this method, using the crying orcs scenario, we get and
BH
`wiz,co = h 0.60, 0.34, 0.05, 0.01, 0.00, 0.00, 0.00, 0.00i BH
`wiz,¬co = h 0.26, 0.07, 0.19, 0.48, 0.00, 0.00, 0.00, 0.00i
The reader might have felt uncomfortable with the difference in the chain of effects of the wizard’s fire and the witch’s fire. The wizard’s fire causes the orcs to leave the forest, which in turn cause them to cry out, but there is no ‘exit forest’ event (x) explicitly mentioned. On the other hand, the witch’s ‘fire lighting’ (`wch) is an explicit event and so is ‘exit forest’, but without a causal relationship being modeled. One would expect that fire lighting causes forest exiting (at least stochasticly).
To resolve these inconsistencies, we propose to use a network of actions and
primitive events (elements of G) as nodes, with edges indicating causal relationships.
(See, for instance, [
The crying orcs scenario could be modeled as in Figure 1(a) or 1(b). The arcs show the causal relationships. Figure 1(b) is a made-up network capturing more elaborate causal relationships. Note that some actions (e.g. a1) do not cause any events, and some events (e.g. ✏ 1) are not caused by an action.
Such causal nets are also more compact representations than modeling E(e, w) for every e 2 X . There is likely an opportunity to represent such networks even more 4 Note that if B and C are independent, then P r(A | B, C) = P r(A | B)P r(A | C)/P r(A). (c) An example causal net. (a) One causal net for the crying orcs scenario.
(b) Another causal net for the crying orcs scenario. compactly by reasoning/conditioning over features (F ) instead of worlds (W ), which is left to do in future.
The causal net belief update operation finds the probability of each world w0 in the new belief state by employing the given causal net to calculate the probability of the end node, given the action performed in the current belief state and the subsequent observation perceived in w0.
.
BaC, = {(w0, p) | w0 2 W, p = · CausalNet(a, , B, End, w0)}.
We define CausalNet(a, , B, ✏ 0, w0) with Algorithm 1. It requires that event likelihoods, transition probabilities and observation probabilities are defined in terms of primitive events ✏ 2 G. Hence, we define – E(✏ , w) := Pe2 X ,eç✏ E(e, w), – T (w, ✏ , w0) := P – O( , ✏ , w) := P e2 X ,eç✏ T (w, e, w0),
e2 X ,eç✏ O( , e, w).
These functions involving primitive events could be specified directly and compactly
using factored representations [
Using this method requires no more information than the causal network and the probabilistic models used in the other two methods. Note that conditional probability distributions/tables are not used as in Bayesian networks; probabilistic information is taken from the agent’s environment models.
Our biggest concern with this procedure is that weighting the final probability (sum) by the observation probabilities (line 9) may not be the best approach. Our intuition is that is an aggregate of all effect signals caused by action a and all primitive events (to the degree that they occurred). One would thus like to weight
Input: a, , B, ✏ 0, w0 1 sum 0; 2 for ✏ in Parents(✏ 0) do 3 for w in W do 4 if ✏ is an orphan or ✏ == a then 5 sum sum + B(w)E(✏ , w)T (w, ✏ , w0) BCa
`wiz,co = h 0.00, 0.55, 0.00, 0.02, 0.00, 0.43, 0.00, 0.00i BCa `wiz,¬co = h 0.00, 0.29, 0.00, 0.19, 0.00, 0.32, 0.00, 0.20i BCb
`wiz,co = 0.00, 0.55, 0.00, 0.02, 0.00, 0.42, 0.0, 0.00 BCb
`wiz,¬co = h 0.00, 0.27, 0.00, 0.22, 0.00, 0.30, 0.00, 0.22i 5
Without it being labeled as endogenous, the state estimation function has been the
basic belief state update function in POMDP theory since the 60’s [
The first well-known formal definition of classical (qualitative/non-probabilistic)
belief update was proposed by Katsuno and Mendelzon [
Shapiro and Pagnucco [
Our framework assumes that every action performed by the agent is immediately followed by an observation. Their framework assumes that an (endogenous) action is either a sensing action (with only epistemic and no ontic effects) or a non-sensing action (with only ontic and no epistemic effects).
Agent actions (whether sensing or not) may be interspersed with exogenous actions. When what is sensed contradicts what the agent believes, the occurrence of exogenous actions is hypothesised to correct discrepancies between belief and sensing.
Whereas our framework assumes that endogenous and exogenous actions (and
their corresponding effects/observations) occur more or less simultaneously (hence,
the uncertainty in the source of the subsequent observation), in the framework of
Shapiro and Pagnucco [
Finally, the main difference between the two frameworks is that ours has a model for the likelihood of exogenous actions (which we call events) occurring. Due to our framework assuming that actions are stochastic and observations are noisy, whereas their actions are deterministic and observations exact, it makes a comparison of the two frameworks difficult.
Van Ditmarsch and Kooi [
Agency of agents in their logic is not modeled, that is, events (including ontic events) may or may not be associated with the actions of agents. In a sense, in their framework. all events are exogenous with some uncertainty about what event actually occurred (each agent has a different uncertainty model). It might be possible to simulate the mixing of exogenous and endogenous events/actions in our framework with their multi-pointed update (update given a set of events).
However, besides the fact that Van Ditmarsch and Kooi [
There are many more logics, formalisms and frameworks which contain both notions of ontic actions and epistemic observation. It seems that in most of those, there is the potential to confuse or conflate the idea that an observation is epistemic in nature or has a physical source. But, as far as we know, none of them attempts to model the mixture of the source of an observation from physical events (exogenous or endogenous).
Rens [
B⇧ =. ¶(w0, p) | w0 2 W, p = O( , w0) X X T (w, e, w0)E(e, w)B(w)©,
w2 W e2 X
which is inspired by Boutilier [
Rens [
Ba√, =. ¶(w0, p) | w0 2 W, p = Eng( , w0, a)Baen,do(w0) + (1 Eng( , w0, a))B⇧ (w0)©, where 2 L is a propositional sentence and Eng( , w0, a) is the agent’s confidence that perceived in w0 was caused by action a. In other words, Eng has the same meaning as EEndo but is not derived, but assumed given by the framework designer.
Dynamic Bayesian networks (DBNs) model physical change by specifying how
a BN changes due to an action. A DBN is a pair hB 0, B! i , where B0 is a BN
representing an initial belief state and B! is a BN representing how probabilities
of events change from one time-slice to the next [
Although Lang’s work [
The work of Halpern [
In this paper, we have made a few suggestions on how to take into account both an agent’s action and some other events that might occur simultaneously to update the agent’s belief state. With respect to our crying orcs scenario, the update operation results in very different belief states of the wizard agent. Table 6 places the updated – Do the three methods simply reflect different but reasonable update strategies? – Are some of the methods fundamentally flawed? – Is it possible or even worth it to combine ideas used in the different methods? Developing the method employing causal networks seems especially promising. However, a major question with that method is where and how to employ the observation weight (probability) in the calculations.
Note that most terms in the methods defined in this paper take the form B(w)E(ae, w)T (w, ae, w0)O( , ae, w0). (1) If any one of the functions is zero, the whole term is zero. Knowing this, there are two things to watch out for. One, for an update operator to be well behaved, there must be at least one world w0 such that none of the functions in (1) evaluates to zero. Two, if either E(ae, w) or T (w, ae, w0) is known to be zero at w, then the other function value needs not be known/specified at w, and if either T (w, ae, w0) or O( , ae, w0) is known to be zero at w0, then the other function value needs not be known/specified at w0.
Rationality postulates for qualitative belief update have been proposed [8, e.g.], but we have found it difficult to translate them into probabilistic versions. We would like to tackle this in future.
Gavin Rens was supported by a Clause Leon Foundation postdoctoral fellowship while conducting this research. This work is based on research supported in part by the National Research Foundation of South Africa (Grant number UID 98019). Thomas Meyer has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie grant agr. No. 690974.