Decision-Making in an Embedded Reasoning System

1 Introduction

While there has been an increasing amount of inter­ est in the development of reasoning systems suited to real-time operations, very few currently exhibit the kind of behavioral properties that we would expect of such systems [Laffey et al. , 1988]. Much of this de­ rives from their inability to reason effectively about actions and plans. On the other hand, most existing planning systems cannot operate under the stringent constraints on both information availability and de­ cision time that are typical of real-time applications. As a rule, these systems formulate an entire course of action before commencing execution of the plan Fran~ois Felix Ingrand Artificial Intelligence Center SRI International 333 Ravenswood A venue Menlo Park, California 94025

This research is partly supported by the National Aeronautics and Space Administration, Ames Research Center, under Contract No. NAS2-12521.

· Also a member of the Artificial Intelligence Cen­ ter, SRI International, and the Center for the Study of Language and Information, Stanford University.

[Wilkins, 1988]. However, in real-world domains, in­ formation about how best to achieve some given goal (and thus how best to complete a plan) can often only be acquired after executing some initial part of that plan.

Real-time constraints pose yet further problems for traditionally structured planning and reasoning systems. First, the planning and deductive tech­ niques typically used by these systems are very time consuming. While this may be .acceptable in some situations, it is not suited to domains where replan­ ning is frequently necessary and where system viabil­ ity depends on readiness to act. Second, traditional planning systems usually provide no mechanisms for responding to new situations or goals during plan execution, let alone during plan formation. Yet the very survival of an autonomous system may depend on its ability to react to new situations and to mod­ ify its goals and intentions accordingly [Georgeff and Lansky, 1987].

A number of systems developed for the control of robots and other real-time processes do have a high degree of reactivity [Brooks, 1985, Kaelbling, 1987]. Such architectures could lead to more viable and ro­ bust systems than traditionally structured planning systems. Yet most of this work has not addressed the issues of general problem-solving and commonsense reasoning; the work is instead almost exclusively de­ voted to problems of navigation and the execution of low-level actions.

There has been some recent work in the design of systems that attempt to integrate goal-directed reasoning and reactive behavior . For example, the RAP system [Firby, 1987] invokes tasks on the basis of system beliefs about the current world situation and then expands these tasks hierarchically. It has many features in common with the system described in this paper. However, it does not appear to pro­ vide sufficiently powerful mechanisms for balancing the decision-making requirements against the con­ straints on time and information that are typical of complex domains.

As Bratman, Israel, and Pollack [1988] remark: " ... Rational agents must perform both means-end reasoning and weigh alternative courses of action; so an adequate architecture of intelligent agents must therefore include capabilities for both. The design of such an architecture must also specify how these capacities interact. But there is yet another prob­ lem. All this must be done in a way that recognizes the fact that agents are [bounded both in resources and knowledge]." In this paper, we describe a sys­ tem architecture that aims to achieve this balance between acting and decision-making.

2 Procedural Reasoning Systems

The problem domain we discuss in this paper is the task of malfunction handling for the Reaction Con­ trol System (RCS) of NASA's space shuttle. The shuttle contains three such systems, one forward and two aft. Each is a relatively complex propulsion system that is used to control the attitude of the shuttle. The astronaut handles system malfunctions by carrying out prespecified malfunction handling procedures. These procedures can be viewed as un­ elaborated plans of action, and are designed to be executed in a complex and changing environment.

To tackle this problem, we developed an embed­ ded reasoning system called PRS (Procedural Rea­ soning System). Early versions of the system have been described before [Georgeff and Lansky, 1986a, Georgeff and Lansky, 1986b, Georgeff and Lansky, 1987] and the full application is described in a re­ cent report [Georgeff and lngrand, 1988].

PRS consists of (1) a database containing current beliefs or facts about the world; (2) a set of current goals to be realized; (3) a set of plans (called Knowl­ edge Areas) describing how certain sequences of ac­ tions and tests may be performed to achieve given goals or to react to particular situations; and (4) an intention structure containing those plans that have been chosen for [eventual] execution (Figure 1). An interpreter (or inference mechanism) manip­ ulates these components, selecting appropriate plans based on the system's beliefs and goals, placing those selected on the intention structure, and executing them.

The system interacts with its environment, includ­ ing other systems, through its database (which ac­ quires new beliefs in response to changes in the en­ vironment) and through the actions that it performs as it carries out its intentions.

2.1 The System Database

The contents of the PRS database may be viewed as representing the current beliefs of the system. Typi­ cally, these will include facts about static properties of the application domain, such as the structure of some subsystems or the physical laws that must be obeyed by certain mechanical components. Other beliefs are acquired by PRS itself as it executes its KAs. These will typically be current observations about the world or conclusions derived by the sys­ tem from these observations, and these may change over time. The knowledge contained in the database is represented in first-order predicate calculus.

State descriptions that describe internal system states are called meta/eve/ expressions . These typ­ ically describe the beliefs, goals, and intentions of the system, as well as other important processing information.

2.2 Goals

Goals are expressed as conditions over some interval of time (i.e., over some sequence of world states) and are described by applying various temporal opera­ tors to state descriptions. This allows us to represent a wide variety of goals, including goals of achieve­ ment, goals of maintenance, and goals to test for given conditions. A given action (or sequence of ac­ tions) is said to succeed in achieving a given goal if its execution results in a behavior that satisfies the goal description.

As with state descriptions, goal descriptions are not restricted to specifying desired behaviors of the external environment but can also characterize the internal behavior of the system. Such descriptions are called metalevel goal specifications.

2.3 Knowledge Areas

Knowledge about how to accomplish given goals or react to certain situations is represented in PRS by declarative procedure specifications called Knowl­ edge Areas (KAs). Each KA consists of a body, which describes the steps of the procedure, and an invoca­ tion condition, which specifies under what situations the KA is useful (applicable). Together, the invoca­ tion condition and body of a KA express a declara­ tive fact about the results and utility of performing certain sequences of actions under certain conditions [Georgeff and Lansky, 1986a].

The body of a KA can be viewed as a plan or plan schema. It is represented as a graph with one distinguished start node and possibly multiple end nodes. The arcs in the graph are labeled with the subgoals to be achieved in carrying out the plan. Successful execution of a KA consists of achieving each of the subgoals labeling a path from the start node to an end node. This formalism allows richer control constructs (including conditional selection, iteration, and recursion) than most plan representa­ tions.

The invocation condition contains a triggering part describing the events that must occur for the KA to be executed. Usually, these consist of the ac­ quisition of some new goal (in which case, the KA is invoked in a goal-directed fashion) or some change in system beliefs (resulting in data-directed or reactive invocation), and may involve both.

Some KAs have no bodies. These are so-called primitive KAs and have associated with them some primitive action that is directly performable by the system.

The set of KAs in a PRS application system not only consists of procedural knowledge about a spe­ cific domain, but also includes metal eve/ KAs- that is, information about the manipulation of the beliefs, desires, and intentions of PRS itself. For example, typical metalevel KAs encode various methods for choosing among multiple applicable KAs, modify­ ing and manipulating intentions, and computing the amount of reasoning that can be undertaken, given the real-time constraints of the problem domain.

2.4 The Intention Structure

The intention structure contains all those tasks that the system has chosen for execution, either imme­ diately or at some later time. These adopted tasks are called intentions. A single intention consists of some initial KA together with all the [sub-) KAs that are being used in attempting to successfully execute that KA. It is directly analogous to a process in a conventional programming system.

At any given moment, the intention structure may contain a number of such intentions, some of which may be suspended or deferred, some of which may be waiting for certain conditions to hold prior to ac­ tivation, and some of which may be metalevel inten­ tions for deciding among various alternative courses of action.

For example, in handling a malfunction in the RCS, the system might have, at some instant, three tasks (intentions) in the intention structure: one sus­ pended while waiting for, say, the fuel-tank pressure to decrease below some designated threshold; an­ other suspended after having just posted some goal that is to be accomplished (such as interconnect­ ing one shuttle subsystem with another); and the third, a metalevel procedure, being executed to de­ cide which way to accomplish that goal.

The set of intentions comprising the intention structure form a partial ordering with possibly mul­ tiple least elements (called the roots of the struc­ ture). An intention earlier in the ordering must be either realized or dropped (and thus disappear from the intention structure) before intentions ap­ pearing later in the ordering can be executed. This precedence relationship between intentions enables the system to establish priorities and other relation­ ships between intentions.

2.5 The System Interpreter

The PRS interpreter runs the entire system. From a conceptual standpoint, it operates in a relatively simple way. At any particular time, certain goals are active in the system and certain beliefs are held in the system database. Given these extant goals and beliefs, a subset of KAs in the system will be appli­ cable (i.e., will be invoked). One or more of these applicable KAs will then be chosen for execution and thus will be placed on the intention structure.

In determining KA applicability, the interpreter will not automatically perform any deduction. Both beliefs and goals are matched directly with invoca­ tion conditions by using unification only. This al­ lows appropriate KAs to be selected very quickly and guarantees a certain degree of reactivity. If we allowed arbitrary deductions to be made, we could no longer furnish such a guarantee. However, PRS is always able to perform any deductions it chooses by invoking appropriate metalevel KAs. These met­ alevel KAs are themselves interruptible, so that the reactivity of the system is retained.

Once selected, the chosen KAs are inserted into the intention structure. If a selected KA arose due to the acquisition of a new intrinsic goal 1 or a new belief, it will be inserted into the intention structure as a new intention. For example, this will be the case for a KA that is invoked by the activation of some caution-warning alarm during shuttle opera­ tions. Otherwise, the KA instance must have arisen as a result of some operational goal of some existing intention, and will be pushed onto the stack of KAs comprising that intention.

Finally, an intention at one of the roots of the intention structure is selected for further execution. The next step of that intention will comprise either a primitive action or one or more unelaborated sub­ goals. If the former, the action is directly initiated; if the latter, these subgoals are posted as new oper­ ational goals of the system.

Execution of primitive actions can effect not only the external world but also the internal state of the system. For example, a primitive action may oper­ ate directly on the beliefs, goals, or intentions of the system. Alternatively, the action may indirectly af­ fect the system's state as a result of the knowledge gained by its interaction with the external world.

At this point the interpreter cycle begins again: the newly established goals and beliefs trigger new KAs, one or more of these are selected and placed on the intention structure, and finally an intention is selected from that structure and partially executed.

1 An intrinsic goal is one that is not a means to an already intended end, whereas an operational goal is a subgoal of some already existing intention.

Unless some new belief or goal activates some new KA, PRS will try to fulfill any intentions it has pre­ viously decided upon. This results in focussed, goal­ directed reasoning in which KAs are expanded in a manner analogous to the execution of subroutines in procedural programming systems. But if some important new fact or goal does become known, PRS will reassess its current intentions, and perhaps choose to work on something else. Thus, not all op­ tions that are considered by PRS arise as a result of means-end reasoning. Changes in the environment may lead to changes in the system's goals or be­ liefs, which in turn may result in the consideration of new plans that are not means to any already in­ tended end. PRS is therefore able to change its focus completely and pursue new goals when the situation warrants it. In many space operations, this happens quite frequently as emergencies of various degrees of severity occur in the process of handling other, less critical tasks.

We have, of course, left out a crucial component of the system's reasoning: how does it make the various selections and decisions mentioned above? We now turn to this and other important features of PRS.

3 . Integrating Decision-Making and Means-Ends Reasoning

PRS is designed so that, in the absence of any de­ cision knowledge being provided to the system, it nevertheless continues to function in an acceptable way as an embedded reasoning system. As more and more decision knowledge is added to the system, it can more effectively choose its actions, but always with a guaranteed upper bound on reaction time.

This is accomplished by embedding in the system interpreter certain fixed decision-making processes that are stringently bounded in execution time, yet which can be overridden whenever the system can bring more powerful decision-making knowledge to bear. Bratman et al. [1988] have outlined a simi­ lar design philosophy, in which they distinguish be­ tween a computationally efficient compatibility filter and a possibly computationally complex filter over­ ride mechanism. In PRS, the fixed decision-making processes are hardwired into the basic system inter­ preter, whereas the knowledge to override or elabo­ rate these decisions is contained in appropriate met­ alevel KAs.

The way these metalevel KAs are brought to bear on any particular problem is via their invocation cri­ teria. These criteria may depend both on conditions obtaining in the external world and, more typically, on conditions relating to the internal state of the system. Such conditions might include, for exam­ ple, the applicability of multiple KAs in the current situation, the failure to achieve a certain goal, or the awakening of some previously suspended intention.

In some of these cases (such as the latter two of those mentioned above), these conditions will be known at the beginning of each interpretation cycle.

But others (such as the number of KAs applicable at a given moment) can only be determined part­ way through this cycle. Thus, the actual manner of invocation of metalevel KAs is somewhat complex [Gem·geff and Ingrand, 1988], but eventually results in the selection of a single KA at some level in the metahierarchy. This KA is then executed just as any other KA. In the process of execution, such met­ alevel KAs typically make choices about the adop­ tion of lower-level KAs (which may themselves be metaKAs), the posting of alternative subgoals, or the best way to respond to goal failures . Any of these decisions may require an arbitrary amount of processing or deduction, yet system reactivity is al­ ways guaranteed (see Section 5.1).

Thus, when decisions have to be made in the ab­ sence of any information about what is best to do, the system interpreter defaults to some fixed deci­ sion procedure. However, if there is any knowledge that can be brought to bear on the decision (via appropriate metalevel KAs), this will override the default action and determine the selection. In this way, the addition of appropriate metalevel KAs en­ ables the system to make more informed choices at the cost of longer decision times.

This approach to the design of PRS is important in another way. We can now construct a relatively simple basic interpreter, knowing that the system is not going to always be constrained to behave in the way dictated by this component - its decisions can, in situations determined by the invocation con­ ditions of the metalevel KAs, be overridden. Of course, it is important that the basic interpreter be able to handle appropriately the most commonly oc­ curring situations so that the metalevel KAs are uti­ lized only in the more exceptional circumstances.

Before concluding this section, it is important to note that the decision-making behavior of PRS is strongly influenced by the choice of the invoca­ tion conditions of metalevel KAs. For example, if these conditions are such that the decision-making metaKAs are frequently invoked, PRS will spend more time making decisions than otherwise. It will thus tend to act in a cautious manner [Bratman et a/., 1988], carefully choosing what actions to per­ form next . If, on the other hand, these metalevel KAs are rarely invoked, PRS will act in a bold man­ ner, rapidly choosing its actions in response to the changing world in which it is embedded.

4 The Nature and Role of Intentions

Intentions play a significant role in PRS. In this sec­ tion we examine their use both in managing events in the real world and in limiting the amount of de­ cision making that has to be undertaken, given the real-time constraints of the domain.

4.1 Intention States

In PRS, an intention can be in one of three possi­ ble states: active, suspended, or conditionally suspended. An active intention is one that is available for execution as soon as it becomes a root of the intention structure. A suspended intention is one that PRS has adopted but for which no decision has been made as to when it should be carried out; that is, it must be explicitly activated before it can be executed. A conditionally suspended intention (or, simply, a conditional intention) is one that is tem­ porarily suspended until some specified condition, called the activation condition of the intention, is satisfied.

In PRS, intentions can be suspended (condition­ ally or otherwise) by means of certain metalevel KAs. When a conditional intention is reactivated, it is necessary to decide whether or notrto reorder the intention structure ana what to do, if anything, with currently executing intentions. In the absence of any decision knowledge, it is desirable to ensure immediate response to the condition that activated the intention. Thus, the basic interpreter is designed to begin execution of the reactivated intention im­ mediately, suspending all currently executing inten­ tions. However, as with all other default decisions taken by the interpreter, metaKAs can respond to reactivation and choose to override this decision.

Similarly, various metalevel KAs exist for reorder­ ing intentions on the intention structure. In the ab­ sence of any decision knowledge the basic interpreter inserts new intentions at the root of the existing intention structure, and removes them when com­ pleted (see Section 4.3). However, metalevel KAs may choose to alter this ordering on the basis of task priorities, time availability, and so on.

4.2 The Role of Intentions

The role of commitment to previously adopted plans or intentions has been claimed to be a criti­ cal component of rational agency [Bratman, 1987, Cohen and Levesque, 1987]. It is also a critical com­ ponent of the PRS architecture, allowing the system to meet the real-time constraints of a continuously changing world.

Unless some particular metalevel KA intervenes, PRS will perform its means-ends reasoning and other planning in the context of its existing inten­ tions. For example, consider that PRS has adopted the intention of achieving a goal g by accomplish­ ing the subgoals g1 , g2, and g3, in that order. In the process of determining how to accomplish these subgoals, the system will not reconsider other means of achieving g. That is, it is committed to achieving g by doing g1, g2, and g3, even if circumstances have so changed that there is now a better way to achieve g than the one chosen. The gain here is in reducing decision time - in highly dynamic domains it is not possible to continually reassess one's plans of action. What makes the approach workable is that the basis upon which one chooses a particular plan of action is more often correct than not.

It is not only in means-ends reasoning that PRS's commitment to its existing intentions is important . For example, in tackling some new task, it is of­ ten desirable that the means or time chosen for ac­ complishing that task take account of one's exist­ ing intentions towards the fulfillment of other tasks. In the RCS application, this happens, for example, when PRS receives a request for a pressure reading when it is in the process of evaluating the status of a suspected faulty transducer. In this case, PRS will either defer or suspend attending to that re­ quest (possibly advising the requester) until it has completed its evaluation of the transducer.

4.3 The Establishment and Dropping of Goals

One does not want to be committed to one's inten­ tions forever. Thus, it is important to understand the way in which intentions are managed in PRS - in particular, how the goals comprising an intention are established and dropped.

As discussed in previous sections, intentions are established by a change in the system's goals or beliefs, and their execution will generate certain operational goals . Should the system attempt to achieve an operational goal and fail, that goal will be reestablished, and another attempt made to achieve it . This will continue until the system comes to be­ lieve either that the goal is accomplished ( through its own efforts or those of some other agent) or that the goal cannot be readily accomplished. Once this state is reached, the goal will be dropped.

This raises two related issues: what other at­ tempts are .made to achieve the goal and how does the system come to believe a goal cannot be readily accomplished? We shall answer the latter question first . One way for the system to believe that a goal cannot be accomplished (or, at least, that the goal is not worth pursuing further) is to deduce it using appropriate metalevel KAs. However, the system rarely has sufficient knowledge of the world to prove that a goal cannot be achieved; this is thus unaccept­ able as the only (or even as the primary) manner of dropping goals ( cf. the work of Cohen and Levesque [1987], who base their axiomatization of rational be­ havior solely on this kind of mechanism).

Another good reason for dropping a goal is simply to fail in all attempts at achieving the goal. This re­ quires no more knowledge than the system acquires in its striving for the goal, and thus is appropriate to be used as the default method for the basic inter­ preter. But it brings us back to the former question: what attempts does the system make to achieve a given goal?

In PRS, the basic system interpreter tries, exactly once, every possible KA instance that can possi­ bly achieve the goal. It does not ask that previ­ ously achieved goals be reachieved (in some other way), nor does it try the same KA instance more than once. In this sense, it is equivalent to a "fast­ backtrack" parser. There are good reasons for these choices.

Unlike off-line planning or the parsing of sen­ tences, PRS operates in the real world rather than an hypothetical one. Thus, the actions it takes can­ not be withdrawn and alternative approaches tried in their stead. Once some goal has been achieved, it has really been achieved - there is no point in in­ voking KAs solely because they represent alternative ways to achieve an already achieved goal.

The remaining issue concerns the number of tries we make of a single KA instance to achieve a given goal. It is, of course, quite possible that, where the first try does not succeed, the next will, even if we carry out exactly the same actions as we did the first time. However, to determine if retrying could suc­ ceed would, in most practical cases, require knowl­ edge of the state of the world that goes well be­ yond that available to the system. · In the absence of such knowledge, the system therefore tries each applicable KA instance exactly once. (The RAP system [Firby, 1987], on the other hand, continues to reinvoke already-tried task networks; clearly, this presents the serious problem of indefinite looping.)

Once all attempts at achieving a given goal have been exhausted, it is still possible for some met­ alevel KA to respond to this failure and invoke yet other means to achieve the goal. For example, a meta-KA could invoke certain deductive machinery, or could decide to retry some KA instances that, although having been tried once, appear (for some reason known to the meta-KA) to be worth trying again. In this way, the provision of additional de­ cision knowledge can always override the basic pro­ cessing method described above.

5 Planning in Real Time

5.1 Guaranteed Reactivity

Response time is one of the most important mea­ sures in real-time applications; if events are not han­ dled in a timely fashion, the system can go out of control. Yet few existing real-time systems are guar­ anteed to respond within a bounded time interval [Laffey et al., 1988].

Response time is the time the system takes to rec­ ognize and respond to an external event. Thus, a bound on reaction time (that is, the ability of a system to recognize or notice changes in its envi­ ronment) is a prerequisite for providing a bound on response time. PRS has been designed to operate under a well-defined measure of reactivity. Because the interpreter continuously attempts to match KAs with any newly acquired beliefs or goals, the system is able to notice newly applicable KAs after every primitive action it takes.

Let p be an upper bound on the execution times of the primitive actions that the system is capable of pe~forming. Let's also assume that n is an upper bound on the number of events that can occur in unit time, and that the PRS interpreter takes at most time t to select the set of KAs applicable to each event occurrence. 2 By calculating the number of events that can occur in a single cycle of the PRS interpreter, it is not difficult to show [Georgeff and lngrand, 1988] that the maximum reactivity delay is tlR = p/(1 - nt), where we assume that t < 1/n.

This means that, provided the number of events that occur in unit time is less than 1/t, PRS will notice every event that occurs and is guaranteed to do so within a time interval llR. (If the event rate exceeds 1/t, the system may not be able to keep abreast of the changes in the environment.) In the shuttle application, which includes over 100 KAs and 1000 facts about the RCS, the values of p and t are less than 0.1 seconds, giving a reactivity delay of at most 0.2 second for an event rate of 5 events per second.

Because metalevel procedures are treated just like any other, they too are subject to being interrupted after every primitive metalevel action they take. Thus, reactivity is guaranteed even when the system is choosing between alternative courses of action or performing deductions of arbitrary complexity.

Having reacted to some event, it is necessary for the system to respond to this event by perform­ ing some appropriate action. As the system can be performing other tasks at the time the critical event is observed, a choice has to be made concern­ ing the possible termination or suspension of those tasks while the critical event is handled. Further­ more, it may be necessary to decided among differ­ ent alternatives for handling the event. With appro­ priate metalevel KAs, it is possible to guarantee a bound on this decision time [Georgeff and lngrand, 1988]. However, the construction of such algorithms remains one of the more interesting areas of research in the design of real-time systems [Bratman et al., 1988, Dean and Boddy, 1988].

5.2 Planning or Not?

There has always been some confusion in the liter­ ature about the notion of planning, especially with respect to the kind of practical reasoning that PRS performs. In the AI literature, planning is viewed as the generation of a sequence of actions to achieve some given goal. The classical approach to this prob­ lem is to simulate the effects of performing the ac­ tions so as to ensure that their execution does indeed achieve the required goal.

However, this is not the only way to construct an effective plan. For example, the choice among al­ ternative courses of action could be based on the expected time to complete the actions, or the like­ lihood of success of the plans as gained through ex­ perience. In any case, simply making the choice as to which course of action to pursue, no matter how one does it, constitutes forming a plan to achieving ones goals.

2 As selection of KAs does not involve any general deduction beyond unification and evaluation of a boolean expression, an upper bound does indeed exist.

This is exactly the way PRS operates. The method of choosing between alternative courses of action is embedded in the metalevel KAs of the sys­ tem and thus, in essence, the particular approach to forming plans is not hard-wired into the system. To the extent that the choice is made arbitrarily, one may wish to avoid calling this process "planning." But where it is based on any information at all, no matter how meager, the determination of an appro­ priate course of action is indeed a form of planning.

In the RCS example, the system decides between different courses of action depending on how the KA was invoked and what sort of priority it has. This is clearly quite a weak form of planning, and more complex meta-KAs - taking time availability, costs, and benefits into account - could be expected to improve system reliability. However, it is interesting to observe just how weak the planning component can be when we have a wealth of experience (a rich set of object-level KAs) to assist us.

6 Conclusions

The system described above was implemented on a Symbolics 3600 Series LISP machine and has been used to detect and recover from most of the possi­ ble malfunctions of the RCS, including sensor faults, leaking components, and regulator and jet failures. This was accomplished by using multiple commu­ nicating instantiations of PRS and a simulator for providing real-time input to the system. Complete details of this large-scale application are given else­ where [Georgeff and lngrand, 1988].

The experiment provided a severe and positive test of the system's ability to operate proficiently in real time, to weigh alternative courses of action, to coordinate its activities, and to modify its inten­ tions in response to a continuously changing environ­ ment. In addition, PRS met every criterion outlined by Laffey et al. [1988] for evaluating real-time rea­ soning systems: high performance, guaranteed re­ sponse, temporal reasoning capabilities, support for asynchronous inputs, interrupt handling, continuous operation, handling of noisy (possibly inaccurate) data, and shift of focus of attention.

The features of PRS that, we believe, contributed most to its success at this task were (1) its partial planning strategy, (2) its reactivity, (3) its use of pro­ cedural knowledge, and (4) its metalevel (reflective) capabilities. In particular, the manner in which the system integrates its means-ends reasoning with the use of decision knowledge is considered an important component of rational activity.

Acknowledgments

Pierre Bessiere, Amy Lansky, Anand Rao, Lorna Shinkle, Joshua Singer, Mabry Tyson, and Dave Wilkins helped in the development of PRS and ex­ tended the implementation as needed. The project has also benefited greatly from our discussions with Michael Bratman, Phil Cohen, David Israel, and Martha Pollack.