Elements of a Utilitarian Theory of Knowledge and Action

1 Introduction

Reasoning about actions and their effects is a central issue in Artificial Intelligence. Agents that are to be successful in their interactions with the real world have to be able to plan their actions and execute them efficiently in time­ constrained situations, without having complete knowledge about the state of their environment, and hence, about its future development.

Our approach to these issues is strongly motivated by the utilitarian paradigm for designing autonomous intelligent agents (see [Doyle, 1992] for convincing arguments support­ ing this view). According to this paradigm, an agent's ratio­ nality is equivalent to its ability to choose among its possible behaviors so as to maximize its expected utility. The pos­ sible behaviors of even a mildly sophisticated agent could include: information gathering (informative) actions, like scanning; computational actions, like inference and plan­ ning; and physical actions that directly influence the agent's environment In this paper, we concentrate on physical and informative actions. We present a preliminary framework to model an agent's uncertain knowledge about the temporal evolution of its environment. The model, essentially a tem­ poral Kripke structure, is based on sets of branching time lines [McDermott, 1982]. We augment a set of time lines with accessibility relations to represent the knowledge of the agent evolving in time. The time lines are described by fluents, that is, by attributes with time-varying values.

0 This research was supported, in part, by the Golda Meir Fel­ lowship and the Alfassa Fund administered by the Hebrew Univer­ sity of Jerusalem, and by the National Science Foundation under grant IRI-9015423 and PYI award IRI-9158473.

Our model depicts an agent's knowledge about its actions as how those actions transform the structure of the possi­ ble time lines and the accessibility relations among them. We further provide the definitions needed to compute the expected utilities of these actions based on our model, and show how the important notion of urgency, or the value of time naturally arises from our approach. Urgency, in some cas~. makes it rational for an agent to undertake immediate physical action despite uncertainty that could be resolved by an informative action (it can "leap before looking"). We believe that the same basic tradeoffs exist in the problem of whether it is rational to "leap before thinking", that is very much in the middle of the debate of deliberative versus reactive planning.

Our work builds on a large body of previously reported re­ search on utility-based approaches in AI [Doyle, 1992]. The work by Haddawy and Hanks [Haddawy and Hanks, 1990; Hanks and Firby, 1990] is similar to ours, but it differs in its emphasis on symbolic goals as the basis for utility cal­ culations, suggesting that these goals are imposed on the agent during operation. We, on the other hand, see utilit.y as a reflection of general preferences, maybe more appropn­ ately called values, that are inherent in any truly autonom~us agent. We also believe that it is possible to represent explic­ itly the tradeoffs among sensing,. ac~ng, and planning, ~nd thus to decide among them in a pnnctpled way. Further sim­ ilarities exist between our model based on branching time lines and the probabilistic temporal projection described in [Hanks, 1988], and although our approach is, at this point, more knowledge-theoretic, the practical methods outlined in [Hanks, 1988] are relevant to our model as well.

Models similar to branching time lines have also been examined as a basis for temporal probabilistic logics for actions and planning [Haddawy, 1991; Pelavin, 1988]. Our contribution in this paper is to show how these models can be used to rationally guide action and perception, in addition to providing semantics of probabilistic temporal logic. Further, while the logical language capturing various fonns of action is useful, these logics by themselves are not capable of fully supporting purposeful choice among alternative behaviors [Doyle, 19921.

Other related work on formal, logically oriented ap­ proaches [Moore, 1990; Morgenstern, 1987] is based on sim­ ilar intuitions to ours, but lacks the utilitarian perspective. In particular, we argue that, in realistic settings, an agent will never possess enough knowledge about the state of the world to be able to prove that executing any particular ac­ tion, such as dialing a phone, will be successful. Further, from a strictly logical perspective the lack of knowledge is, taken by itself, no obstacle to acting at all. If, for instance, an agent wants to reach someone by phone without actually knowing the telephone number (other than that it contains 7 digits), the agent can simply dial all possible seven digit numbers in sequence, being quite convinced that eventually it will get through. The part that is missing, of course, is the relative value of time and other resources wasted in the process, but that is precisely what makes this an issue in economics, rather than in logic [Doyle, 1992]. It is in this context that one can understand why looking up a number in the phone book actually pays off.

Yoav Shoham also relies on branching time lines to rep­ resent an agent's uncertain knowledge, its evolution, and the effects of action [Shoham, 1989]. The major difference between his work and ours is that his does not include the element of expected utility, and therefore does not address the crucial issue of motivation and choice of action [Doyle, 1992], referring instead to the logically-motivated work of Cohen and Levesque [Cohen and Levesque, 19871. Further, Shoham envisions the evolution of the agent's knowledge as a series of time line structures, while we represent it as accessibility relations within one such structure. He also seems to include the uncertainty about the agent's own fu­ ture actions as branching in his model, while we forbid it.

Finally, our work builds on the enonnous body of research done over the years in the fields of mathematical economics, and utility and decision theories. We refer to it in the text of the paper as we go.

In the following sections of the paper, we first introduce our branching time lines model of knowledge. We then describe how the model can be used to reflect results of physical and infonnative actions, and how expected utility calculations can be perfonned on it. We then give examples of expected utility calculation for plans involving physical and infonnative actions, and show how our approach natu­ rally gives rise to the notion of urgency as the value of time. We end with conclusions and further research directions.

2 Modeling Temporal Knowledge by Branching Time Lines

Branching time lines were proposed by McDennott as a model for temporal logic of processes and plans [McDer­ mott, 1982] and they provide a basis for various logics of probability, time and action in other related work [Haddawy, 1991; Pelavin, 1988; Dean and Wellman, 1991]. We have adopted this model here, and augmented it with accessi­ bility relations so that it fonns a temporalized version of the Kripke structure (for details on Kripke structures, see

[Halpern and Moses, 1990; Halpern and Moses, 1991]). The branching time lines are composed of chronicles consisting of totally temporally ordered states. A chronicle is intended to represent a possible course of events in an agent's en­ vironment, and it can be described by a set of fluents, i.e., attributes with values changing over time [Ginsberg, 1990; McDennott, 1982].

Loosely speaking, the current uncertainty in an agent's knowledge about the possible past courses of events is repre­ sented by the fact that the time lines branch off into the past; the uncertainty of the agent's knowledge about the present state of the world is represented by the fact that there are many branching time lines at the present date, NOW; and the current uncertainty in the agent's knowledge about the future evolution of the world is represented by the fact that the time lines are branching off into the future. In this pa­ per, we are interested in the utilities of the optional future actions of the agent, and therefore we only consider the rep­ resentations starting at NOW and extending into the future.

Thus, the branching time lines represent the current uncer­ tainty in the agent's knowledge. To complement the picture with the knowledge that the agent may have about its future knowledge, we introduce the accessibility relations that can hold among the time lines and the branches in the model. We say that if one of the time lines in the model is acces­ sible from another line, then the agent situated in the world evolving according to the first time line will consider the evolution of the world according to the other time line as possible. If two time lines are accessible from each other then the agent will not be able to tell if the world evolves according to one or the other. 1

The model of branching time lines introduced above corre­ sponds precisely to a temporal sequence of classical Kripke structures. Let us also note that if the accessibility rela­ tions defined above fonn a partition of possible states of the world at any given time into a set of exhaustive equivalence classes, then the model of branching time lines becomes identical to what in the economics literature is called the infonnation structure of the agent [Radner, 1982].

In our graphical representation, the accessibility relations, depicted by dotted arrows, will be assumed to hold for the whole section of the time line between the nearest points, which can be either branching points, or temporal marks on the time lines. As an example, let us take the case of an agent sitting by his desk in his office not knowing whether the building is on fire, but having some indication that it might be {burning smell, commotion, etc.). The agent knows that there is a sprinkler system installed in the building, but he does not know whether the system will function properly. Let us assume for the moment that our agent knows that it is positioned so that it would not notice the sprinkler sys­ tem's operation. The uncertain knowledge about the present state of the world, and about the future developments that will follow, can be represented as two time lines in Figure 1. According to one of the time lines, the building is on fire. This time line has a branching, B, corresponding to the agent's uncertainty as to the automatic activation of the sprinlcler system sometime later, in the case of fire. The other time line presents the possibility that the building is not on fire. Both of the time lines are each accessible from the other, and each is accessible from itself, with the acces­ sibility relations depicted in Figure 1 as arrows. The arrows also connect the branches of the time line according to which the building is on fire, since, as assumed, our agent would not be aware of the sprinlcler system's operation in the case it is activated. These branches are similarly connected to the other time line to indicate that the sprinlcler's operation would not resolve the question of whether the building is on fire for this agent.

1 This is just an intuitive description sufficient for the purpose of this paper. For now let us only note that the accessibility relation connecting two time lines defined above is, in fact, vague, since it does not specify whether each of the states in one line is accessible from each of the states in the other line, or whether it is accessible only from the state with the same date. The first interpretation corresponds to the situation in which the agent does not know what time it is, while the other corresponds to an agent equipped with a clock. In the following discussion we will use the second interpretation of the agent being aware of the exact time, although we plan to investigate the first alternative in future research.

Let us now consider a variation of the above situation that indicates how our model can represent somewhat different knowledge of the agent. In this case, we assume that the sprinkler system is also installed in the agent's office, so it will certainly notice its operation. The branching time lines model of this situation is depicted in Figure 2. Note that the two branches of the time line corresponding to the fire are not connected via the accessibility relation. This is because, in this situation, the cases of the sprinkler being on or off are not indistinguishable any more. Further, the upper branch, according to which the sprinkler Icicles in, is not connected to the lower time line, while the lower branch is. This is the representation of the fact that the sprinkler's operation would be noticed by the agent and effectively identify for it whether the building is, in fact, on fire. Of course, the agent still would not be able to distinguish the case where the building is not on fire from the case when there is a fire but the sprinkler system is not operational, as indicated in Figure 2.

In what follows, we will call the model of an agent's knowledge that does not include results of any action of this agent (although it may contain effects of actions of other agents, with their corresponding uncertainties) the base model.

3 Acting in the Model of Branching Time Lines

As we have mentioned, an agent can construct the branching time line models that represent its knowledge of the dynamic effects of performing various activities in its environment, and then can compute the expected utility of these activities allowing a rational decision on the proper course of action. Before describing this calculation, we examine how changes in the model can reflect the effects of an agent's possible courses of action. ·

Let us take the example of the agent in his office won­ dering about the building being on fire, as in the previous section. Consider an action our agent might contemplate performing, for instance one of immediately activating the sprinlcler system. The result of this action in our represen­ tation is a pair of time lines, this time with no branches (see Figure 3). The fact that the sprinkler system has been activated is true in both of them, but, according to one of the possible courses of events, the sprinlcler system is extin­ guishing a real fire, while in the other the building is just getting sprayed. The lack of branching in the time line ac­ cording to which there is a fire reflects the fact that the agent has some newly acquired certainty; it has not left matters up to an unpredictable sprinkler actuator which was the source of the branching in its model before.

Let us now take an example of a different type of action - one aimed specifically at gathering information. Let us say that it is possible for our agent to check whether there really is a fire, for instance by performing an action that we will refer to as AFireTe.t. that is expected to take TFireTe·t time units. The result of this action is sketched in Figure 4, which depicts the two time lines, as before, but now the accessibility relations between the lines have been severed after time TFireTe·t· 2 The severance corresponds to the fact that after the AFireTe·t has been successfully performed, our agent will know whether the building is on fire or not. The time line according to which there is a fire, however, still has a branching in it, corresponding to the agent's uncertainty about the proper functioning of the sprinkler system.

The agent can also consider more complex actions, for in­ stance those consisting of a series of simpler actions, those involving conditionals, or those with while loops (see also [Moore, 1990; Morgenstern, 1987]). For example, the agent might consider an action consisting of performing the action AFireTe·t first, and then, if the fire is burning, on turning the sprinkler system on. The effect of this composite ac­ tion is depicted in Figure 5. We still have two time lines corresponding to the cases of the fire burning and not, that are accessible from each other for all times before the ac­ tion AFireTe·t has been completed, but not accessible af­ terwards. Also, at the time TFireTe·t· the agent activates the sprinkler system in the upper time line, as indicated in Figure 5.

2 Recall that the accessibility relations depicted graphically hold only between the nearest branching points or time marks.

4 Computing Utilities in the Model of Branching Time Lines

In this section we show how utility associated with the model of branching time lines can be defined. The definition will require that we enrich our model with probabilistic informa­ tion, supplementing the possibilistic information represented by the model presented so far. Thus, we assume that an agent's knowledge about the likelihoods of time lines, T L;, in its model can be represented by probability distributions, PT L; · The states that comprise each time line are in total temporal order, and each of them can be described by the propositions stating the values of the ftuents, F(t), in this particular state. The descriptions, F(t), can be then used to assign a numerical value, UTLr (t), to the state, representing the state's desirability to the agent (see [Keeney and Raiffa, 1976] for details on combining the effects of several ftuents (or attributes) using a multiattribute utility calculation) .

The expected utility, EUTL(t), associated with a set of states belonging to the time lines at time t, can be defined as a probabilistic mixture of the utilities, UTL, (t), of states on each time line i at timet:

where PT L; is the probability of the time line T L;.

In practice, the part of a set of time lines, T L, used by the agent to compute the expected utilities of its optional actions lies between the point in time called NOW, corresponding to the current date, and the point that lies in the infinite future, oo. Consequently, we define the expected utility, EUTL· of this set of time lines, as:

where the constant, a, is the discount rate. 3 The definition above accepts the simplifying assumption of simple additiv­ ity of the expected utility over the states (see [Keeney and Raiffa, 1976; McKenzie, 1986] for discussion).

The problem of existence for EUTL· that is, the conver­ gence of the integral in Eq.(2), can be overcome by demand­ ing that the discount rate, a, be large enough. We find this demand counterintuitive at times, and for cases where con­ vergence is a problem, as when a = 0, we use the method developed in [Ramsey, 1928], which advocates shifting the utility scale to force the convergence of the integral, or the method introduced in [Weizsaecker, 1965], which uses the so-called overtaking criterion, based on comparing finite par­ tial integrals over time. A somewhat ad hoc way of dealing with the nonconvergence of the integral in Eq. 2 would be to introduce a finite time horizon, which might be a legitimate simplification at times, but we will not use it here.

5 Utilities of Physical and Informative Actions

Having defined the utilities for the branching time lines model above, it is quite straightforward to define the utilities of physical actions. Since the physical actions that an agent can perform in its environment transform the model of the branching time lines, the utility of an action can be identified as the utility of the branching time lines model that reflects the effects of this action.

3 The discount rate corresponds, roughly, to the agent's possibly preferring to receive a payoff sooner rather then later. See [Keeney and Raiffa, 1976] for more details.

To continue the example of the agent wondering about the fire in the office building, the expected utility of the agent's action, AsprOn. of immediately activating the sprin­ kler system can be computed from the model in Figure 3. To illustrate this example calculation we assume that the fluents, F(t), describing the possible time lines in Figure 3 are the attributes of FireSize and GettingWet. The attribute Getting Wet will have a value that we will denote by Wetl, at time NOW, and monotonically decrease to 0 at time 10, when everything is already wet, in both possible time lines. The attribute FireSize will be equal to zero in the time line according to which the fire is not burning, and will be mono­ tonically decreasing from a value, denoted Sizel, at time NOW, to zero at time 10 (see Figure 6a). Given the above, we will assume that the utility functions are linear over the values of attributes, with the proportionality constant of -1, and additive, so that the utility of a state is the sum of the utilities associated with each of the attributes. 4 Assuming that the discount rate, a , is equal to zero, the total utility of immediately activating the sprinklers can be easily com­ puted, using Equation 2 (see Figure 6a). For the upper time line, the contribution of the fire is the negative of the area under the FireSize fluent line: -0.5 x Si ze 1 x 10. The sprin­ kler's contribution is, similarly: -0.5 x W et1 x 10. Adding the contribution of the upper time line with probability PFire and the lower time line with probability 1 - PFir e· we get:

utiles, where PFi,·e is the probability associated with the fire burning (we will compare this result with another shortly).

The case of informative actions is less straightforward. 5 Let us take the action A FireTe. t, and its resulting branching time lines model, depicted in Figure 4. The only change in this model , as compared to one in which the agent is quiescent (Figure 1), is the change in the accessibility rela­ tions between the two time lines after the time TFir eT e. t· But, according to the equations defining the utility calcula­ tions given in the preceding section, the accessibility rela­ tions by themselves do not impact the utility of the model in any way. 6 That the possession of knowledge by itself does not impact the agent's welfare is quite understandable; the agent's information only counts as far as it puts it in a better position to make desimble physical changes to the environment This observation leads us to the conclusion that the desimbility of certain actions, for example informa­ tive (and computational) ones, has to be always assessed as embedded in other, physical actions, that these non-physical ones facilitate.

4 These simplifying assumptions are made only to make the example easier to follow. They are in no way inherent in our approach.

5 There are, probably, no actions that are purely informative in the sense that no action's sole effect is the change of the agent's knowledge. There will always be some physical resources con­ sumed and possibly other physical side effects. There may be no reason, though, to include them in the branching time lines model if these effects are negligible from the agent's welfare point of view.

6 That is, unless the agent's possession of knowledge is by itself desirable, and included in the set of fluents, F. in Eq. 1. We do not consider this case here.

As an example, let us take the composite conditional ac­ tion considered before, consisting of AFireTe·to and, if the fire is burning, followed by the activation of the sprinkler system, which we will call AFireTutfSprOn· The utility of this composite action can be calculated based on the model depicted in Figures 5. To make this calculation concrete we will use the same parameters as in the case of the agent acti­ vating the sprinklers without testing, above. The difference boils down to the time delay, TFireTe·t· Thus, in the case that there is the fire, it would go on burning for the time TFireTe·t· at the level Sizel, after which the agent would find the positive result of the test and activate the sprinkler system resulting in linear decrease of the FireSize to zero at the time (TF;,·eTe·t + 10) (see Figure 6b). In the case there is no fire, the sprinkler system is, of course, not activated. With the simplifying assumptions of the utility being addi­ tive and inversely proportional to the attributes, the utility of the conditional action can be computed as:

utiles. The relative value of AFireTe.t· in this particular context of the action activating the sprinklers, could be as­ sessed by comparing the utilities of activating the sprinkler system conditioned on outcome of the AFireTe·t· versus activating the sprinkler system without performing the test. As can be easily seen from Equations 3 and 4, this boils down to comparing the disutility of the office building get­ ting sprayed unnecessarily if there is no fire if the sprinklers were activated without testing: -5(1- PFir e) Wet!, and the disutility of the fire, if there is one, burning for additional time TFireTe.t in the other case: -PFireSize 1 X TFireTe·t ·

Clearly, the result of this comparison is not guaranteed to favor the performance of AFireTe·t· One can easily imag­ ine the situation in which the lengthy time required to per­ form the test, coupled with the high a priori probability that the fire is burning and possibly high losses incurred during the time TFireTe.to gives priority to activating the sprinklers without the test For example, if we assume that Size! = 10M' et 1, then it is rational to perform the testing operation only if TFireTe·t ~ (1- PFire)/2PFire· So, if the probability of a fire were 10%, for example, then running the test if it takes 4 time units would be rational, but if the test takes 5 time units it would be rational to activate the sprinklers NOW instead.

5.1 Urgency: The Value of Time

In the example above, one is tempted to say that the prob­ ability of losses due to fire have made the situation urgent, so that wasting time on an action like testing that does not have the immediate physical effects of remedying the sit­ uation, may not be worth it. Said more succinctly: the probability of losses due to inaction have created urgency,

-

i.e., have imparted value to time. To make the above insight more precise:

Definition: The urgency, U RG(t), or the value of time function, is defined as the negative of the expected utility, EUn(t), of the base model of the agent's knowledge, rep­ resented by the set of branching time lines, T L, as defined in Equation 1.

Recall that the base model is the model of branching time lines that represents the agent's knowledge about the evo­ lution of the events in the world but does not include any of the agent's own actions. The above definition, therefore, formalizes urgency as the rate of accumulation of disutility to an agent, if it delays physical action.

For instance, for the base model in the example of the agent in the office building that is possibly on fire, the urgency for the points in time NOW and afterwards 7 is: U RG(t) = PFireSizel utiles/sec.

Clearly, the fact that time is valuable forces rational agents to be time-effective in executing physical actions, and cru­ cially impacts on the viability of non-physical action, as shown in the example above of the action AFireTe&t. which becomes ill-advised if it takes too long and the situation is too urgent

Possibly the most important non-physical action that the urgency of the situation could make ill-advised is, of course, the agent's reasoning, and, in particular, planning. We an­ ticipate that the approach we have taken can prove fruitful in addressing the issue of reactive versus deliberative behav­ ior in rational agents; we will investigate this in our future research.

6 Conclusions and Future Work

In this preliminary report we have presented an applica­ tion of the utilitarian paradigm (maximization of expected utility) to reasoning about knowledge and action. In our approach, an agent's knowledge is represented as a set of branching time lines, with probability distributions describing the agent's knowledge about the likelihoods of possible courses of action, and with accessibility relations connect­ ing the lines and branches describing the future states of the agent's knowledge. The rational agent can use this model to investigate the expected utilities of the various courses of action it could take, and behave rationally based on this cal­ culation. We have investigated examples of physical action and informative action. The utility of the latter was due to the fact that it would enhance the efficiency of the agent's physical action.

7 We neglect here for simplicity the fact that the fire would burn itself out after some long time, and the urgency would then be zero.

We showed how the important notion of urgency, or the value of time, arises from our approach. Urgency has the intuitive property of favoring immediate physical actions, sometimes making non-physical actions, such as sensing and reasoning, ill advised. Our result here goes along other work previously reported that treats time as a resource [Boddy and Dean, 1989; Dean and Boddy, 1988; Dean, 1990; Horvitz et a/., 1989; Russell and Wefald, 1989], but our contribution is the rigorous derivation of the value of this resource.

In our future work, drawing on our earlier investigation [Gmytrasiewicz and Durfee, 1992], we will address the is­ sue of representing the temporal uncertain knowledge of agents in multiagent situations, in which recursion in mod­ els arises due to agents' modeling others modeling them, and so on. We will attempt to apply this framework to the process of coordination and communication in dynamic and uncertain multiagent situations [Gmytrasiewicz eta/., 1991a; Gmytrasiewicz et a/., 1991bl. Further, we will develop a suitable language of knowledge and action, drawing on previous work in [McDermott, 1982; Moore, 1990; Morgenstern, 1987]. Finally, we plan on investigating the issue of rationality of reasoning under time pressure in an at­ tempt to address the issue of rational choice among sensing, reasoning, and physical actions in time-constrained domains.