Dynamic Interactions between Goals and Beliefs

1 Introduction

Shapiro et al. [2005; 2006], presented a framework for representing goal change in the situation calculus. In that framework, agents adopt a goal when requested to do so (by some agent reqr), and they remain committed to the goal unless the request is cancelled by reqr. A common assumption in the agent theory literature, e.g., [Cohen and Levesque, 1990; Rao and Georgeff, 1991], is that achievement goals that are believed to be impossible to achieve should be dropped. In this paper, we incorporate this assumption into Shapiro et al.'s framework, however we differ from previous approaches in two respects. If an agent believes a goal is impossible to achieve, it is dropped. However, if the agent revises its beliefs, it may later come to believe that it was mistaken about the impossibility of achieving the goal. In that case, the agent should readopt the goal. To our knowledge, this has not been considered in previous approaches. In addition, most frameworks 1 consider goals in isolation when checking compatibility with beliefs. However, it could be the case that each goal individually is compatible with an agent's beliefs, but the set of all goals of the agent is incompatible with its beliefs.

1 Bell and Huang [1997] consider the compatibility of all of an agent's goals with its beliefs, but they do not consider the possibility of readopting a goal previously believed impossible.

In Sec. 2, we present the situation calculus and Reiter's action theories, which form the basis of our framework. In Sec. 3, we present Shapiro et al.'s framework, and in Sec. 4, we show how to extend the framework to take into consideration the dynamic interactions between beliefs and goals. Some properties of the new framework are presented in Sec. 5. In Sec. 6, we sketch how to extend the framework further so that achievement goals that are believed to have been already achieved are dropped by the agents. We conclude in Sec. 7.

2 Representation of Action and Beliefs

The basis of our framework for goal change is an action theory [Reiter, 2001] based on the situation calculus [McCarthy and Hayes, 1969; Levesque et al., 1998]. The situation calculus is a predicate calculus language for representing dynamically changing domains. A situation represents a possible state of the domain. There is a set of initial situations corresponding to the ways the agents believe the domain might be initially. The actual initial state of the domain is represented by the distinguished initial situation constant, S0. The term do(a, s) denotes the unique situation that results from the agent doing action a in situation s. Thus, the situations can be structured into a set of trees, where the root of each tree is an initial situation and the arcs are actions. The sequence of situations that precedes a situation s in its tree is called history of s. Predicates and functions whose value may change from situation to situation (and whose last argument is a situation) are called fluents. For instance, we might use the fluent INROOM(Agt, R1, S) to represent the fact that agent Agt is in room R1 in situation S. The effects of actions on fluents are defined using successor state axioms [Reiter, 2001], which provide a succinct representation for both effect axioms and frame axioms [McCarthy and Hayes, 1969].

We will be quantifying over formulae, so we assume that we have an encoding of formulae as first-order terms. As shown by De Giacomo et al. [2000], this is laborious but straightforward. It includes introducing constants for variables, defining substitution, introducing a Holds predicate to define the truth of formulae, etc. We assume we have such an axiomatization, and so we will freely quantify over formulae here (using first-order quantifiers). To simplify notation, we ignore the details of the encoding and use formulae directly instead of the terms that represent them.

We will also be using lists of formulae, so we need an axiomatization of lists. We do not present the details here but such a formalization is well known. We use the functions car(l), cdr(l), cons(ψ, l), reverse(l), and remove(ψ, l); and the relation member(ψ, l) with their usual meanings. nil denotes the empty list. We will also use lists of formulae (without repetitions) to represent finite sets of formulae, and therefore use finite sets when it is convenient, along with the usual set functions and relations.

To axiomatize a dynamic domain in the situation calculus, we use Reiter's [2001] action theory, which consists of (1) successor state axioms for each fluent; (2) initial state axioms, which describe the initial state of the domain and the initial mental states of the agents; (3) unique names axioms for the actions, and domain-independent foundational axioms (given below); and (4) the axioms to encode formulae as terms, and to define lists of (terms for) formulae. 2

Unique names axioms are used to ensure that distinct action function symbols denote different actions. For distinct action function symbols, a1 and a2, we need an axiom of the following form: 3

Axiom 2.1

Also, for each action function symbol, a, we need an axiom of the following form:

Axiom 2.2

We want the situations to be the smallest set generated by sequences of actions starting in an initial situation. We axiomatize the structure of the situations with foundational axioms based on the ones listed in Levesque et al. [1998] for the language of the "epistemic situation calculus". We first define the initial situations to be those that have no predecessors:

We declare S0 to be an initial situation.

Axiom 2.3

2 Action theories normally also include axioms to specify the distinguished predicate Poss(a, s) which is used to described the conditions under which it is physically possible to execute an action, however to simplify notation, we omit the use of Poss here and assume that it is always possible to execute all actions.

3 We adopt the convention that unbound variables are universally quantified in the widest scope.

We also need an axiom stating that do is injective.

Axiom 2.4

The induction axiom for situations says that if a property P holds of all initial situations, and P holds for all successors to situation s if it holds for s, then P holds for all situations.

Axiom 2.5

We now define precedence for situations. We say that s strictly precedes s′ if there is a (non-empty) sequence of actions that take s to s′ .

Axiom 2.6

where s1 ⪯ s2 def = s1 = s2 ∨ s1 ≺ s2 denotes that s1 precedes s2.

Although belief change plays a large role in this paper, the focus is on the goal change framework. Belief change frameworks in Reiter's action theory framework have been developed [Shapiro et al., 2000; Shapiro and Pagnucco, 2004; Shapiro, 2005], however we will not assume a particular framework here. Instead, we will make a few general assumptions about the belief change framework as needed. In particular, we assume a possible worlds approach (with B as the accessibility relation) using situations as possible worlds. The accessible situations are the ones that are used to determine the beliefs of the agent, as usual. These would correspond to, e.g., the most plausible accessible situations of Shapiro et al. [2000] or simply the situations that the agent considers possible in a framework without plausibilities over situations. Therefore, we assume that the language contains a distinguished predicate B(agt , s′ , s). We also assume that the agents' beliefs are always consistent:

Axiom 2.7

The beliefs of the agent are defined as those formulae true in all the accessible situations:

Here, φ is a formula that may contain the distinguished constant Now instead of its (final) situation argument. φ[s] denotes the formula that results from substituting s for Now in φ. When the intended meaning is clear, we may suppress this situation argument of φ.

3 Goal Change

Shapiro et al. [2005; 2006], presented a framework for representing goal change in the situation calculus. In that framework, agents adopt goals when requested to do so (by some agent reqr) and they remain committed to their goals unless the request is cancelled by reqr. One problem with this approach is that an agent will retain a goal even if it believes the goal is impossible to achieve. We address this problem here. We first introduce Shapiro et al.'s [2006] framework, and then show how it can be changed to better reflect the intuitive interactions between beliefs and goals.

An agent's goals are future oriented. For example, an agent might want some property to hold eventually, i.e., the agent's goal is of the form Ev(ψ), for some formula ψ. We evaluate formulae such as these with respect to a path of situations rather than a single situation, and we call such formulae goal formulae. Cohen and Levesque [1990] used infinite time-lines to evaluate such formulae, but for simplicity, we evaluate goal formulae with respect to finite paths of situations which we represent by pairs of situations, (Now, Then), such that Now ⪯ Then. Now corresponds to the "current time" on the path of situations defined by the sequence of situations in the history of Then. Goal formulae may contain two situation constants, Now and Then. For example, ∃r.INROOM(JOHN, r, Now)∧¬INROOM(JOHN, r, Then) could be used to denote the goal that John eventually leaves the room he is in currently. If ψ is a goal formula then ψ[s, s′ ] denotes the formula that results from substituting s for Now and s′ for Then. When the intended meaning is clear, we may suppress these situation arguments of goal formulae.

Following Cohen and Levesque [1990], Shapiro et al. model goals using an accessibility relation over possible worlds (situations, in our case). The accessible worlds are the ones that are compatible with what the agent wants to be the case. Shapiro et al.'s W accessibility relation, like the B relation, is a relation on situations. Intuitively, W(agt , s′ , s) holds if in situation s, agt considers that in s′ everything that it wants to be true is actually true. For example, if the agent wants to become a millionaire in a situation S, then in all situations W-related to S, the agent is a millionaire, but these situations can be arbitrarily far in the future.

Following Cohen and Levesque [1990], the goals of the agent should be compatible with what it believes. The situations that the agent wants to actualize should be on a path from a situation that the agent considers possible. Therefore, the situations that will be used to determine the goals of an agent will be the W-accessible situations that are also compatible with what the agent believes, in the sense that there is B-accessible situation in their history. We will say that s′ Bagt,s-intersects s′′ if B(agt, s′′ , s) and s′′ ⪯ s′ . We will suppress agt or s if they are understood from the context. Shapiro et al. define the goals of agt in s to be those formulae that are true in all the situations s′ that are W-accessible from s and that B-intersect some situation, s′′ :

Note that s′′ corresponds to the "current situation" (or the current time) in the path defined by s′ . We define a similar accessibility relation C below and define Goal in the same way but using C instead of W.

Shapiro et al. specify how actions change the goals of agents. They do not give a successor state axiom for W directly, instead they use an auxiliary predicate, REQUESTED. REQUESTED records which goals have been requested of and adopted by an agent, as well as which situations should be dropped from W to accommodate these requests. When a request is cancelled, the corresponding goal (and dropped situations) are removed from the REQUESTED relation. A requested goal is adopted by an agent if the agent does not currently have a conflicting goal. This maintains consistency of goals. REQUESTED(agt , ψ, s′ , s) holds if some agent has requested that agt adopt ψ as a goal in situation s and this request causes agt to cease to want situation s′ . Here is the successor state axiom for REQUESTED:

Axiom 3.1

where W - is defined below. An agent's goals are expanded when it is requested to do something by another agent. After the REQUEST(requester, agt, ψ) action occurs, agt should adopt the goal that ψ, unless it currently has a conflicting goal (i.e., we assume agents are maximally cooperative). Therefore, the REQUEST(requester, agt, ψ) action should cause agt to drop any paths in W where ψ does not hold. This is taken into account in the definition of W -:

According to this definition, s′ will be dropped from W, due to a request for ψ, if s′ B-intersects some s′′ such that ψ does not hold on the path (do(a, s′′ ), s′ ). The reason that we check whether ¬ψ holds at (do(a, s′′ ), s′ ) rather than at (s′′ , s′ ) is to handle goals that are relative to the current time. If, for example, ψ states that the very next action should be to get some coffee, then we need to check whether the next action after the request is getting the coffee. If we checked ¬ψ at (s′′ , s′ ), then the next action would be the REQUEST action.

We also have to assert that initially no requests have been made. We do so with the following initial state axiom:

Axiom 3.2

Shapiro et al. defined W in terms of REQUESTED. s′ is W-accessible from s iff there is no outstanding request that caused s′ to become inaccessible.

4 Dynamic interactions between goals and beliefs

A common assumption in the agent theory literature [Cohen and Levesque, 1990; Rao and Georgeff, 1991] is that achievement goals that are believed to be impossible to achieve should be dropped. However, we go a step further. If some time later, an agent revises its beliefs and decides that the goal is achievable after all, the agent should reconsider and possibly readopt the goal. Also, the previous focus has been on individual goals that are incompatible with an agent's beliefs. However, it could be the case that each goal is individually compatible with an agent's beliefs but the set of goals of the agent is incompatible, so some of them should be dropped.

First, we make precise the notion of a finite set of goal formulae being compatible with an agent's beliefs. We say that a finite set of goal formulae α is B-consistent in situation s, if there exists a path (s′′ , s′ ) such that s′′ is B-accessible from s, and none of the goals in α caused s′ to be dropped from W .

If α is a singleton, we may replace it with its element.

To make its goals compatible with its beliefs, an agent takes the set of requested formulae which may be Binconsistent and chooses a maximally B-consistent set to be its goals. We assume that each agent has a preorder (≤) over goal formulae corresponding to a prioritization of goals. ψ ≤ ψ′ indicates that ψ has equal or greater priority than ψ′ . This ordering could be used to, e.g., represent that an agent gives different priorities to requests from different sources, or to give higher priority to emergency requests. The agent chooses a maximally B-consistent subset of the requested formulae respecting this ordering. To simplify notation, we fix here a single such ordering for all agents, but in practice different agents will have different orderings, and it is not difficult to generalize the definitions to accommodate this.

Let:

denote the set of formulae that have been requested for agt in situation s. Since there are no requests initially, and an action adds at most one goal formula to the set of requests, it is easy to see that this set is finite in any situation. Therefore, we can consider the set of requests in a situation to be a list. The list is sorted according to the priority ordering (≤), using the recursively defined function sort(α), which takes a finite set α and returns a list of elements of α sorted according to ≤: 4

Axiom 4.1

4 if P then A else B is an abbreviation for (P ⊃ A)∧(¬P ⊃ B)

where chooseMin is a function which takes a finite set of formulae and returns an element of the set that is minimal in ≤:

Axiom 4.2

After the set of requests is sorted, a maximally B-consistent sublist is selected that respects the ordering, using the function makecons, which is defined using a recursively defined auxiliary function makecons′ . 5

Axiom 4.3

l′ = makecons′ (agt , cdr(l), s). reverse(l), s)).

In other words, the list α is checked starting from the end to see if the last element is B-consistent with the result of recursively making the rest of the list B-consistent. If it is Bconsistent, then it is added to the result, otherwise it is left out. Finally, the resulting list is reversed to restore the ordering.

This list is used to define our accessibility relation for goals. First, we define CHOSEN(agt , ψ, s′ , s) (in analogy to Shapiro et al.'s REQUESTED), which holds if ψ was chosen by agt and that choice should cause s′ to be dropped from the accessibility relation (i.e., REQUESTED(agt , ψ, s′ , s) holds).

We define a new accessibility relation for goals, C(agt , s′ , s), based on the chosen set of goal formulae rather than the requested set. Intuitively, s′ is a situation that the agent wants to realize in situation s. We say that C(agt , s′ , s) holds if s′ is a situation that was not caused to be dropped by any chosen goal formula ψ:

Finally, the goals of the agent are defined analogously to the way it was done by Shapiro et al., but using C instead of W:

5 A similar function was defined in Booth and Nittka [2005]. This way of handling preferences can also be viewed as a special case of [Brewka, 1989].

5 Properties

We now consider some properties of goal change. Let Σ consist of the encoding axioms, the axioms defining lists, and Axioms 2.1-4.3. Our first result is that the agents' goals are always (simply) consistent.

Theorem 5.1

As we have discussed, it should be the case that if an agent believes a goal ψ is impossible to achieve then the agent should drop the goal. For this theorem, we assume that ψ is an achievement goal, i.e., of the form eventually ψ′ for some goal formula ψ′ . The theorem states that if an agent believes that ψ is impossible to achieve, then the agent does not have the goal Ev(ψ). We need to give a definition for Ev to be used both inside the Bel operator and the Goal operator. Since belief formulae take a situation as an argument and goal formulae take a path as an argument, we need two definitions in order to use them in the two contexts, therefore, we overload the definition.

In the belief context, Ev(ψ, s) takes a single situation argument. It holds if there exists a path (s′′ , s′ ) in the future of s such that ψ[s′′ , s′ ] holds.

In the goal context, Ev(ψ, s, s′ ) takes a path (a pair of situations) as an argument. It holds if there is a situation s′′ in the future of s such that ψ[s′′ , s′ ] holds.

Note that we suppress the situation arguments of Ev when it is passed as an argument to Bel or Goal.

Theorem 5.2

As a corollary, we have a result about belief contraction. If an agent has Ev(ψ) as a goal in s but after an action a occurs, the agent believes ψ is impossible to achieve, then the agent drops the goal that Ev(ψ).

Corollary 5.3

We also have a result concerning the expansion of goals. If an agent gets a request for ψ, it will not necessarily adopt ψ as a goal, for example, if it has a conflicting higher priority goal. But if ψ is the highest priority goal formula, and it is B-consistent, it should be adopted as a goal. We say that a goal formula ψ is highest priority among a finite set of goal formulae α, if the priority of ψ is at least as high as the priority of any goal formula in the set, and any goal formula in the set whose priority is at least as high as ψ is equal to ψ.

For this theorem, we need an assumption about the belief change framework. Namely, it must be the case that request actions are not "belief producing". More precisely, if a situation s′′ is accessible after a request action was executed in situation s, then s′′ came about by executing the same request action in a situation s′ accessible from s. In other words, successor situations are not dropped from the B relation after a request action is executed.

Axiom 5.4

Theorem 5.5

Σ ∪ {Axiom 5.4} |= ∀agt , ψ, reqr , s. BCons(agt , ψ, do(REQUEST(reqr , agt , ψ), s)) ∧ Hp(ψ, ({ψ} ∪ reqs(agt , s))) ⊃

Goal(agt , ψ, do(REQUEST(reqr , agt , ψ), s)).

6 Future Work

Another interaction between achievement goals and beliefs is that once an agent believes that an achievement goal has been realized, it should drop that goal. We have not addressed this yet, but it will not be difficult to add it to our framework, as described in the following. In the context of belief change, the agent may believe that a goal has been achieved but later change its mind. In this case, the agent should first drop its achievement goal, but later readopt it after the mind change. Therefore, we need to check whether it is the case that agent believes that an achievement goal ψ has been false continuously since the last request for ψ. If not ψ, should be dropped. This can be formalized in the situation calculus as follows. We first define a predicate Prev(a, s′ , s), which holds iff the last occurrence of a in the history of s occurs just before situation s′ .

Then, we say that ψ is live in situation s, if the agent believes that ψ has been continuously false since that last request for ψ:

If ψ is believed to have been already achieved, it should be dropped regardless of the agent's other goals and should therefore not be taken into account when determining the maximally B-consistent set. Therefore, for all goals ψ s.t. ¬Live(ψ, s), we remove ψ from reqs(agt, s) before it is passed to makecons. This ensures that ψ will not be chosen and will therefore not be a goal of the agent.

7 Conclusion

In this paper, we extended a previous framework for goal change so that agents drop goals that are believed impossible to achieve. To our knowledge this is the first framework to take into account the possibility that the agents change their minds about the impossibility of their goals. When this happens the agents may readopt goals that were previously believed to be impossible to achieve. Some properties about goal consistency, contraction, and expansion were shown. We also sketched how to further extend the framework so that agents will drop achievement goals that are believed to be already achieved. Again, agents might later change their mind about whether the goal has been already achieved and possibly readopt the goal.

8 Acknowledgments

We would like to thank M. David Sadek for suggesting this avenue of research. We also thank Philip R. Cohen, Andreas Herzig, Yves Lesp´erance, Hector J. Levesque, and Sebastian Sardina for useful discussions pertaining to this paper.