Agents, Actions and Goals in Dynamic Environments

1 Motivation

In dynamic environments agent's actions can fail. This might be either directly due to failing effectors of the agent, or indirectly due to incompleteness of information. The latter situation may arise either because precise and complete information is inherently impossible (think of a robot dealing with complex physical phenomena, such as the weather), or technically infeasible, resp. undesirable in the given application domain (e.g., high space complexity of the environment representation, or high rate of environment change in relation to the speed of the agent's deliberation).

Construction of agents in the face of unexpected failures is difficult. As a reaction to difficulties with classical planning in dynamic environments, the paradigm of agent-oriented programming (AOP) based on reactive planning (e.g., [Bordini et al., 2006]) became one of the state-of-the-art techniques for construction of intelligent agents. Even though the motivation behind AOP is rooted in the idea that more ∗ Supported by the Czech Ministry of Education, Youth and Sports, grant MSM6840770038 and the Grant Agency of the Czech Technical University in Prague, grant SGS10/189/OHK3/2T/13.

†Supported by the FNR (National Research Fund) Luxembourg under project S-GAMES - C08/IS/03.

Wojciech Jamroga†

Computer Science and Communications University of Luxembourg Luxembourg

reactive style of deliberation is more appropriate for agent's interaction with a dynamic environment, the precise characteristics of the relationship have not yet been deeply studied.

In this paper we precisely investigate the relationships between capabilities and control mechanisms of an agent, its design objectives, the goal, and characteristics of the environment it is embodied in. As a conceptual framework supporting the discourse, in Section 2 we introduce a series of agent behaviour performance measures. We start from relating the set of agent's generic capabilities to an environment in which actions can fail. Subsequently, we introduce agent programs constructed from the basic actions and based on their performance in the environment, we provide a taxonomy of their mutual matchings. Finally, in Section 3 we consider the relationship between a program, its design objective, a goal it is aimed to fulfil, and characteristics of the environment. We study the relationships of the triad using Probabilistic Dynamic CTL* logic (pDCTL*), a novel temporal logic framework facilitating reasoning about agent system specifications and actual programs aimed at realising it. We observe, that imperfect performance of agent programs situated in dynamic environments w.r.t. their goals can in fact be caused by two distinct phenomena. While the environment by its dynamics can make the program fail, it can be also the program itself, which is not implemented perfectly w.r.t. the goal. We conclude the discourse of the paper by discussion in Section 4 of how program construction influences its performance w.r.t. the design specification, and finally, in Section 5 we formally relate the two causes of program imperfection. In particular, we introduce an impact metric, a measure indicating how much the imperfections in program implementation influence the chances for reaching the goal.

2 Agents, actions, environments

We focus on actions of an agent acting in an environment. The agent's actions can change the state of the environment, possibly in a probabilistic way. Other agents, if present in the system, are not relevant at this stage and are assumed to be appropriately modelled as a part of the environment. Due to this characteristics, we will model environments as Markov decision processes (MDP's) [Bellman, 1957]. By this, we implicitly assume that agents can always exactly recognise the current state of the environment. We leave analysis of the more general case (partial observability) for future work.

2.1 Basic notions

Definition 2.1 (Environment). Environment E is modelled as a Markov decision process (S, E, P) where S is a set of states the environment can be in, E is a set of events which can happen in E and P : S ×E ×S → [0, 1] is a probabilistic transition function with transitions labelled by events. That is, P(s, e, s′ ) defines the probability that, upon occurrence of the event e in the state s, the next state of the environment will be s′ . We will adopt the convention that if e is not enabled in s then P(s, e, s′ ) = 0 for all s′ ∈ S.

Furthermore, we assume that some propositional language L is available to characterise properties of states of E. L comes with a standard satisfaction relation |=, with E, s |= φ meaning that the formula φ ∈ L holds in the state s of the environment E.

An agent consists of a template that specifies how it can act (i.e., provides a set of basic operations available to the agent) and a program that prescribes how it will act (e.g., by defining its deliberation mechanism). An agent must match its environment in the sense that its actions must be events in the environment. Moreover, each action is annotated with a specification of its envisaged effects. In an ideal environment, the annotation should hold after the action has been executed.

Definition 2.2 (Agent template). Let E = (S, E, P) be an environment. An agent template (Act,Ann) situated in E specifies the set of basic actions (capabilities) Act ⊆ E that the agent can execute in E, together with the function Ann : Act → L that annotates the agent's actions by formal descriptions of their expected effects.

Definition 2.3 (Macro actions and traces). A macro action is a possibly infinite sequence of actions ρ = a1, . . . , an, . . . with ai ∈ Act .

An execution trace λ of macro action ρ rooted in a state s0 ∈ S of environment E is a (finite or infinite) sequence of labelled transitions s0 a1→ s1 a2→ · · · an→ sn an+1 → · · · such that si ∈ S and P(si-1, ai, si) > 0 for all i. By λ[i] = si, we denote the ith state on λ, and λ[i..j] = si ai+1 → . . . aj→ sj denotes the "cutout" from λ from position i to j. The ith prefix and suffix of λ are defined by λ[0..i] and λ[i..∞], respectively. |λ| denotes the number of transitions in λ. In the case λ is infinite, we write |λ| = ∞. For a given trace λ = s0 a1→ s1 a2→ · · · an→ sn an+1 → · · · , we denote ρ(λ) = a1, a2, . . . , an, . . . the macro action, execution of which resulted in λ.

Definition 2.4 (Situated agent). An agent is represented by a tuple A = (Act , Ann, τ ) where (Act , Ann) is an agent template situated in an environment E, and τ is an agent program over Act. The set P of well-formed programs is defined as follows:

• a is a program for every a ∈ Act ;
• If τ, τ ′ are programs, then also τ ∪ τ ′ , τ; τ ′ and τ ∗ are programs denoting non-deterministic choice, sequential composition and unbounded iteration respectively;
• Additionally, fixed iteration τ n is defined recursively as τ 1 = τ and τ n+1 = τ n ; τ.

The semantics of an agent program is defined in terms of the set of traces TE(τ, s0) it induces in the environment E, rooted in some initial state s0. Formally, TE(τ, s0) is defined inductively

• TE(〈a〉, s0) = {s0 a→ s1 | P(s0, a, s1) > 0},
• TE(τ; τ ′ , s0) = {λ | there exists i : λ[0..i] ∈ TE(τ, s0) and λ[i..∞] ∈ TE(τ ′ , λ[i])},
• TE(τ ∪ τ ′ , s0) = TE(τ, s0) ∪ TE(τ ′ , s0),
• TE(τ ∗ , s0) = {λ | λ[0] = s0, k0 = 0 and there exist k1, k2, . . . s.t., λ[ki, ki+1] ∈ TE(τ, λ[ki])}.

Additionally, TE(τ) denotes the set of all traces induced by τ in states of E, i.e., TE(τ) = ⋃s∈S TE(τ, s). Moreover, given a set of sequences X, we will use F in(X) to denote the set of finite prefixes of the sequences from X. For example, Fin(TE(τ)) is the set of finite histories that can occur during execution of τ in E.

Note, that the generic form of agent programs we define in Definition 2.4, serves only for exposition of ideas in this paper. In fact, any succinct way of encoding of agent's behaviour in terms of enabled execution traces (intended system evolutions) would serve equally well. This broader understanding of agent behaviours naturally includes various planning mechanisms, as well as most state-of-the-art AOP languages.

Hereafter, unless specifically stated otherwise, we will assume an agent A = (Act , Ann, τ ) situated in an environment E = (S, E, P), s.t. the annotation function Ann is expressed in some propositional language L with a satisfaction relation |= that interprets formulae of L in states of E.

2.2 Probabilistic execution of actions and programs

Annotations play dual role in the specification of agents' capabilities. On one hand, they put forward the envisaged outcome of an action in an ideal environment. On the other, they allow to define the notion of successful execution of the action (and, dually, the notion of execution failure).

Definition 2.5 (Success and failure of actions). A transition s a→ s′ is a successful execution of a if s′ |= Ann(a), otherwise it is a failure.

Given a state s ∈ S, the probability of successful execution of action a ∈ Act in s is defined as

Straightforwardly, the probability of failure of a in s is Pfail (a, s) = 1 - Pok (a, s).

A macro action is successful if and only if all its components succeed along the trace.

Definition 2.6 (Success of macro actions). Let ρ = a1, . . . , an be a macro action. The probability of successful execution is extended to macro actions as follows:

Note that Pok is a probability distribution determining execution success of sequences of actions in states of E.

Now we are ready to introduce probability-based measures of successful execution of actions and programs in an environment.

Definition 2.7 (Execution success measures: actions). Let ρ be a (macro) action. The minimal certainty of successful execution of ρ in the environment E is defined as:

Similarly, we define the maximal certainty of successful execution of ρ in E:

Definition 2.8 (Execution success measures: programs). Let τ ∈ P be an agent program over the actions of some agent A. The minimal certainty of successful execution of τ w.r.t. a state s in the environment E is the minimal probability of execution success among the individual traces induced by the program rooted in s:

Moreover, the minimal certainty of execution success for program τ in the environment E is defined as

The notions of maximal certainty of successful execution P + ok (τ, s) and P + ok (τ,E) for an agent program are defined analogically.

2.3 Classification of environments w.r.t agent templates

In the first approach, we gauge how well the agent's basic capabilities (e.g., effectors of a robot) match the environment in which the agent is to be situated.

Definition 2.9 (Taxonomy of environments w.r.t. success of actions). Given an agent template (Act,Ann) in an environment E, we can distinguish several relations between the two, depending on how well the template specification meets the dynamics of the environment. Formally, we say that the matching between (Act , Ann) and E is:

consistent iff P - ok (a, E) > 0 for all a ∈ Act ,

strictly consistent iff it is consistent and P + ok (a, E) < 1 for all a ∈ Act ,

inconsistent otherwise.

We argue, that the most interesting cases of relationship between an agent and an environment is when from the agent's perspective the environment is strictly consistent, or at least contains a significant strictly consistent fragment. For a mobile robot, a controlled indoor environment is usually ideal. Examples of (strictly) consistent agent-environment systems include e.g., outdoor robots operating in rain, snow, on icy, or sandy surfaces, or on gravel roads. From a robot's perspective, an environment is also strictly consistent when it features only imprecise sensors and/or unreliable effectors. For the agent's controller, such situation is indistinguishable from the case when the failures are truly exogenous.

The view promoted in the Definition 2.9 is rather pessimistic. Especially for agent templates based on large libraries of actions, even if one action does not match the environment, the whole agent template is seen as a mismatch. In a more complex agent program, designer might want to take into account also some failures of actions e.g., by encoding various contingencies, or refining the conditions under which actions and plans can be executed. The following refinement of the environment vs. agent classification takes the agent program as a basis for the matching.

Definition 2.10 (Environments vs. agents). Given an agent A = (Act,Ann, τ) in an environment E, we say that the matching between A and E is:

consistent iff P - ok (τ, E) > 0,

strictly consistent iff it is consistent and P + ok (τ, E) < 1, inconsistent otherwise.

Still, this notion of matching between agents and environments is not perfect. In particular, if τ includes unbounded iteration (an infinite deliberation cycle in an event-driven agent is a good example) then it is easy to see that all the environments are either ideal or inconsistent w.r.t. such an agent. This is because the notion of success relates executions to the annotations of all the actions that are going to be performed, regardless of their relevance to a larger context. In many scenarios, such context is provided by an objective, a goal, that the agent is supposed to pursue. We will formalise the concept and discuss the consequences in the next section.

3 Reasoning about temporal goals

In the previous section, we showed how "perfectness" of an environment can be classified with respect to the agent's repository of actions and/or its main algorithm. However, the classification is quite rough in the sense that it depends on all the actions behaving as expected (according to the provided annotations). An alternative is to consider a particular objective, and to measure how the environment reacts in the context of the objective.

Objectives that refer to execution patterns (like achievement of a property sometime in the future, or maintenance of a safety condition in all future states) can be conveniently specified in linear time logic. LTL [Pnueli, 1977] enables reasoning about properties of execution traces by means of temporal operators ❣(in the next moment) and U (strong until). To facilitate reasoning about finite sequences of actions and compositions thereof, we will use a version of LTL that includes the "chop" operator C [Rosner and Pnueli, 1986].

3.1 Temporal goals: LTL

Formally, the version of LTL used in this paper is defined as follows.

Definition 3.1 (LTL). The syntax of LTL is given by the following grammar:

Other Boolean operators (disjunction ∨, material implication →, etc.) are defined in the usual way. The semantics is defined through the clauses below (where E is an environment and λ is an execution trace of some macro action of an agent A situated in E):

Additional operators ♦ (sometime in the future) and □ (always in the future) are defined as ♦φ ≡ ⊤Uφ and □φ ≡ ¬♦¬φ. Note that achievement goals can be naturally specified with formulae of type ♦φ, whereas a goal to maintain φ corresponds to the formula □φ. Finally, we say that LTL formula φ is valid in E w.r.t. a program τ (written E, τ |= φ) iff for all s ∈ S, φ holds on every trace λ ∈ T (τ, s) .

For an agent situated in an environment, we can easily define how likely the agent is to bring about a given goal.

Definition 3.2 (Probabilistic fulfilment of goals). Given an agent program τ situated in an environment E = (S, E, P) and an LTL formula φ, we first define the probability space (TE(τ, s), Fin(TE(τ, s)), pr ) induced by the next-state transition probabilities P. In this space, elementary outcomes are runs from TE(τ, s), events are sets of runs that share the same finite prefix (i.e., ones from Fin(TE(τ, s))), and the probability measure pr : Fin(TE(τ, s)) → [0, 1] is defined as

Then, the probability of fulfilling goal φ from state s on is defined through the following Lebesgue integral:

The interested reader is referred to [Kemeny et al., 1966] for details of the construction and a proof of correctness.

Analogously to Section 2.2, the basic measure of fulfilment for a whole environment is based on the worst case analysis.

Definition 3.3 (Fulfilment of goals: P - ok , P + ok ). Let τ ∈ P be an agent program over the actions of some agent A. The minimal certainty of fulfilment of goal φ by τ in an environment E is the probability of fulfilment from the "worst" state in E:

The maximal certainty of fulfilment is defined analogously.

3.2 Reasoning about goals in pDCTL*

In order to reason about the expected fulfilment of goals, we propose a refinement of the branching-time logic CTL* [Emerson, 1990] with explicit quantification over program executions and probability thresholds. In the extension, [τ]ζφ reads as "agent program τ fulfils goal φ with probability at least ζ". The logic is called "probabilistic Dynamic CTL*" (pDCTL*). It is a straightforward extension of "dynamic CTL*" from [Nov´ak and Jamroga, 2009] (which in turn can be seen as a variant of Harel's process logic [Harel and Kozen, 1982]) along the lines of probabilistic temporal logics [Aziz et al., 1995; Hansson and Jonsson, 1994].

Definition 3.4 (pDCTL*). The syntax of pDCTL* is defined as an extension of LTL by the following grammar:

where p is a propositional formula from L, and τ is an agent program.

The semantics of pDCTL* extends that of LTL by the clauses below:

pDCTL* formula θ is valid in E (written E |= θ) iff E, s |= θ for every state s of E. Finally, ψ is a semantic consequence of φ (written: φ ⇒ ψ) iff for every environment E, E |= φ implies E |= ψ.

The following proposition is straightforward and shows a strong relationship between formulae of pDCTL* and the measures of goal fulfilment introduced in Section 3.1.

Additionally, we define [τ]φ as [τ]1φ. It is easy to see that the semantics of [τ]φ in pDCTL* and DCTL* coincide. Moreover, pDCTL* validity corresponds to LTL validity w.r.t. a program (the proofs are straightforward).

Proposition 3.6. For every environment E, program τ and DCTL* formula φ, we have E, s |=DCTL* [τ]φ iff E, s |=pDCTL* [τ]φ.

Proposition 3.7. For every environment E, program τ and LTL formula φ, we have: E, λ |=LTL φ for every λ ∈ TE(τ) iff E |=pDCTL* [τ]φ.

We note that the operator dual to [τ]ζ has almost the same meaning, except of being underpinned by strict, instead of weak inequality.

Thus, pDCTL* allows also to refer to the exact probability of fulfilment by [τ ]=ζφ ≡ [τ ]ζφ ∧ ¬〈τ 〉ζφ.

3.3 Classifying environments w.r.t. goals

Assuming a particular temporal goal allows for a finergrained taxonomy of environments than we proposed in Subsection 2.3.

Definition 3.9 (Taxonomy of environments w.r.t. goal fulfilment). Given an agent program τ and a goal φ, we can distinguish between several types of environments according to the probability of fulfilment of φ by τ . We say that E is:

manageable iff P - ok (τ, φ) ≥ ζ for some ζ > 0 (equivalently: E |= [τ]ζφ for some ζ > 0). Note that, for finite environments, it is equivalent to P - ok (τ, φ) > 0 (and E |= 〈τ〉0φ);

strictly manageable iff the environment is manageable and P + ok (τ, φ) < 1,

Consider the mobile robot from Subsection 2.3. Aiming to move along a pre-defined path, an outdoor environment is manageable for the robot, but a crowded place could even turn hopeless due to continuously moving people interfering with the robot. In effect, such a classification can give a good formal hint on limitations of usability of the robot.

For agent programs inducing only finite traces, we can distinguish environments w.r.t. the degree of iteration needed for the program to achieve a goal.

Definition 3.10 (Taxonomy of environments cont.). Given a program τ such that |λ| < ∞ for every λ ∈ TE(τ), we can distinguish between several additional types of environments according to the certainty of fulfilment of φ by τ in E:

completely hopeless iff E |= [τ ∗ ]=0φ.

Additionally, we define the following limit cases:

• E |= [τ ∗ ]φ, but there is no k ∈ N : E |= [τ k ]φ,
• there exists ζ > 0, s.t. E |= [τ ∗ ]ζφ, but there is no k ∈ N : E |= [τ k ]ζφ, and
• for all k ∈ N, there exists ζ > 0, s.t. [τ k ]ζφ, however [τ ∗ ]=0φ.

This line of thought can be elaborated upon further by considering special types of programs. E.g., τ = a1 ∪ · · · ∪ an, where Act = {a1, . . . , an}. Now TE(τ) include all the possible plans which can be constructed out of the actions in Act .

4 Program composition vs. goals

In this section, we turn our interest to the the following question: how program composition affects the certainty level of goal fulfilment by agents in dynamic environments? In particular, we are interested in how likelihood of fulfilling general maintenance and achievement goals (involving the □ and ♦ modalities respectively) relates to the way how the corresponding programs are constructed. Throughout this section, we implicitly assume that environments are strictly manageable w.r.t. programs and goals in consideration.

The following theorem articulates the intuition, that concatenation of programs leads to a strict decrease of the certainty of goal fulfilment by the joined program.

Theorem 4.1. If τ1, τ2 are programs, s.t., E |= [τ1]=ζφ1 ∧ E |= [τ2]ζφ2 and at the same time E |= ¬[τ1]ζφ2, then E |= ¬[τ1; τ2]ζφ1Cφ2.

Proof sketch. The idea behind the proof is that due to the independence of τ1 and τ2 w.r.t. φ2 (E |= ¬[τ1]ζφ2), to establish Pok((τ1; τ2), so, φ1Cφ2), we must consider traces induced by τ1 prolonged by traces induced by τ2. By approximating the sum of probabilities for sets of such prolongations rooted in terminal states of traces of τ1 by ξ = P + ok (τ2,E, φ2), we arrive to the inequality Pok((τ1; τ2), so, φ1Cφ2) ≤ ξ · ζ. Since the environment is only strictly manageable w.r.t. τ2 and φ2, by necessity ξ < 1, hence ξ · ζ < ζ, i.e., the minimal certainty of execution success of τ1; τ2 w.r.t. the goal φ1Cφ2 and the environment E is strictly less than the original ζ.

In Theorem 4.1 we used the C operator for joining the goal formulae. Concatenation and further iteration of the same program leads to the following property of maintenance goals involving □ modality on ever longer traces.

Let's assume that the behaviour of an agent conforms to some performance quality measure when continuously operating at a particular level of probability of fulfilment of its goal by the agent program in a particular environment. We can formulate the following informal consequence of Theorem 4.1 and Corollary 4.2: in dynamic environments, behaviour specifications involving temporal maintenance goals of the form □φ are undesirable. The main reason behind this conjecture is, that to ensure satisfaction of strict maintenance goals, such as □p, necessarily programs have to be joined by sequential composition, what leads to decrease of the level of certainty of execution success w.r.t. the envisaged goal. In fact, by subsequently prolonging the induced traces by sequential program composition, the level of certainty eventually eventually drops below the minimal required performance threshold.

Let's turn our attention to achievement goals, i.e., those which involve the ♦ modality.

Theorem 4.3. Given τ is a program, s.t., E |= [τ]ζφ, then E |= [τ k ]ζ♦φ for every k > 0.

Proof sketch. The idea behind the proof is that by inductively iterating τ k , the traces which satisfy ♦φ are i) those on which the goal was already satisfied for lower k's and prolonged by any trace regardless whether it satisfies ♦φ, or not; plus ii) all the traces which did not satisfy ♦φ for lower k's prolonged by the traces induced by τ which satisfy ♦φ. In result, for every k, the number of traces which satisfy the formula ♦φ is not decreasing, nor is the ratio to those which do not satisfy the goal.

In fact, we hypothesise that if E |= [τ ]=ζφ, then we should have E |= [τ k ]=ξ♦φ, where ξ > ζ and k > 0.

5 Program perfection vs. fulfilment

Agent programs in dynamic environments can perform in an imperfect manner w.r.t. their goals due to two reasons. Firstly, it can be the environment by its dynamics which can cause the program not to fulfil its goal. Secondly, it can be the implementation of the program itself, which results in execution traces along which the goal is not fulfilled. In the following, we look at the probability of goal fulfilment had the implementation of the agent's capabilities been ideal. This allows us to measure the impact of the imperfection in the implementation on the fulfilment likelihood.

Definition 5.1 (Idealised environment). The idealised variant of an environment E = (S, E, P ) with respect to an agent template (Act,Ann) is defined as the environment EAnn = (S, E, P Ann ) where the new probabilistic transition relation P Ann is as follows:

That is, we take the transition relation P in E and remove all the transitions that do not conform with Ann (normalising P afterwards). Note that this scheme can be seen as a probabilistic version of model update similar to the one in Public Announcement Logic [Baltag, 2002].

The idealised probability of fulfilling a goal φ is the probability of fulfilment of φ under the assumption that the agent's actions will behave as specified.

Definition 5.2 (Idealised fulfilment of φ). P Ann ok (τ, s, φ) (resp. P Ann ok (τ, φ)) in an environment E is simply defined as Pok (τ, s, φ) (resp. P - ok (τ, φ)) in the idealised environment EAnn .

Now we can measure the impact of imperfect implementation as the difference in certainty of fulfilment between the ideal and the real case:

Definition 5.3 (Impact metric Imp). Given environment E = (S, E, P), agent A = (Act,Ann, τ), and goal φ, we define

Imp(φ) indicates how much the imperfections in implementation of the agent's capabilities influence the chances for reaching the goal φ. In this context, it can be interpreted in two ways:

• Imp indicates how inaccurate the agent implementation is with respect to the given goal. In contrast, P - ok (τ, φ) shows only the general inaccuracy of the agent implementation.
• Assuming that the designer has some control over the deployment of the agent in the environment, Imp can be understood as a measure of how much they should improve the implementation of the agent's capabilities in order to get the objective met.

6 Final remarks

The discussion in the last two sections only scratched the surface of what the introduced conceptual framework allows to rigorously investigate. One of interesting examples is the notion of a planning horizon. I.e., given a set of agent's capabilities, a goal and a specific level of certainty with which it should be satisfied, we can ask: what is the maximal plan length beyond which the probability of fulfilling the goal decreases below the required quality threshold? An estimate of the planning horizon could have an impact on parametrisation of planning algorithms used in dynamic environments, or can lead to constraints on lengths of plans in a library of a reactive planner. Similarly, deeper insights into how program composition influences the impact metric of the resulting programs have a potential to influence formulation of useful code patterns for agent programming, such as those introduced in [Nov´ak and Jamroga, 2009]. We leave these interesting issues for further work along this line of research.