Implementing BDI-like Systems by Direct Execution

1 Introduction

The inability of traditional software to handle complex mod­ ern applications, together with the rapid expansion of infras­ tructure such as the INTERNET, has Jed to the introduction of a new technology, termed agent-based systems. An agent is a semi-autonomous process, typically communicating via message-passing and cooperating with other agents in order to achieve common goals. This technology has been particu­ larly successful in producing distributed information systems where centralised control is either impractical or undesirable. Here, not only is the ability of agents to act autonomously vi­ tal , but such agents are often required to dynamically adapt to unforeseen circumstances and to work cooperatively with other agents in order to overcome problems. These facets make agent-based systems ideal for complex tasks in real­ world applications and, consequently, this technology has been applied in a wide variety of areas, from industrial pro­ cess control to cooperative information retrieval.

In spite of the rapid spread of agent technology, there are, as yet, relatively few high-level programming languages for agent-based systems. Although considerable research has been carried out concerning the development of theo­ ries of agency and cooperation, the lack of appropriate high­ level logic-based programming languages often means that implemented systems have very little connection with these high-level theories (an exception to this is Shoham's Agent­ Oriented Programming work [Shoham, 1993]). Traditional programming languages typically lack the flexibility to han­ dle high-level concepts such as an agent's dynamic control of its own behaviour. Consequently, it is widely regarded as important that high-level languages be provided, which can support the principled development of multi-agent systems, from logical theory to implemented system.

In this paper, we consider two approaches to the high­ level representation of agent-based systems, namely Rao and Georgeff's BDI model [Rao and Georgeff, 1991] and Fisher's Concurrent METATEM language [Fisher, 1993]. In spite of their differing backgrounds we show that they have a great deal in common and introduce, in §4, a hybrid approach. Whilst not as general as the BDI model, nor as simple as the Concurrent METATEM language, this hybrid approach can capture a range of agent behaviours, while retaining many of the advantages of executable specifications.

2 The BDI Framework

Rao and Georgeff [ 1991] considered a particular agent frame­ work whereby individual rational agents incorporate certain "mental attitudes" of Belief, Desire and Intention (BDI). These are used to represent, respectively, the information, motivational and deliberative states of the agent, and together effectively determine the system's behaviour. This frame­ work is both appealing and influential, being used in a number of practical systems [Jennings and Wooldridge, 1995].

2.1 Agents

The core components of the BDI framework are rational agents [Wooldridge and Jennings, 1995]. These are au­ tonomous entities, which execute independently, and have complete control over their own internal behaviour. The core elements of BDI agents are as follows. Beliefs correspond to the information that the agent has assimilated about the world; the set of beliefs is typically incomplete and may be incorrect with respect to the true situation. Desires are the agent's high-level goals, which need not be achievable simul­ taneously, but are usually consistent. Intentions essentially represent a subset of the agent's desires that it has committed to achieve.

2.2 Executing Agent Descriptions

The key process in executing BDI systems is deliberation. This consists of two aspects:

• deciding which desires will become intentions;
• deciding how to achieve those intentions.

Thus, an abstract execution cycle usually involves following steps [Rao and Georgeff, 1991].

1. Update beliefs based upon observations and actions.
2. Based on these beliefs, generate new desires.
3. Select a subset of desires to act as intentions.
4. Select a step to perform based upon intentions and the current state of the agent.

Thus, intentions are only completed one step at a time. The step selected corresponds either to performing an action, modifying a belief, or generating a subgoal and, once this step has been completed, the execution cycle begins again.

2.3 Real BDI Systems

Since its inception, many real-world agent-based systems have been based upon the BDI philosophy, most notably the Procedural Reasoning System (PRS) [Georgeff and lngrand, 1989), but also systems such as INTERRAP [Fischer et at., 1996]. In the PRS, the selection of a step to be performed involves searching a plan library for plans which can achieve the selected intention. This library consists of pre-constructed plans; planning from first principles is not undertaken. In the PRS, intention structures, which are essentially partial orders of dependencies, provide linkage between all related intentions. For example, such structures record the fact that some intentions may be suspended, some may be deferred and some depend on further intentions.

Although both PRS and its successor, dMARS, have been successfully used in a number of areas, such as Air Traffic Control [Rao and Georgeff, 1995], the link between such sys­ tems and the BDI framework is often tenuous. In particular, while the practical systems incorporate elements termed be­ liefs and intentions, these are distinct from the formally de­ fined beliefs and intentions of BDI model.

Consequently, there is a requirement for mechanisms link­ ing the high-level BDI model with its low-level realisation. Several different approaches have been considered. For ex­ ample, a number of BDI-based programming languages have been proposed [Weerasooriya et at., 1995; Rao, 1996a]. However, these have either been too low-level or not expres­ sive enough to capture the key elements of BDI systems.

More recently, object-oriented development methodologies have been adapted in order to provide, through a form of agent-oriented development methodology, a closer link be­ tween the model and its realisation [Kinny and Georgeff, 1997]. Since this practical development approach still does not consider the maintenance of formal properties, the need for high-level logic-based languages capturing the key com­ ponents of the BDI model remains.

3 The Concurrent METATEM Framework

Fisher [ 1993] introduced Concurrent METATEM, an agent­ based programming language comprising two elements:

1. The representation of each individual agent's behaviour using a temporal specification.
2. An operational framework providing both asynchronous concurrency and broadcast message-passing.

Temporal logic provides a means of declaratively specifying agent behaviour. It not only represents the dynamic aspects of an execution, but also contains a mechanism for represent­ ing and manipulating the goals of the agent. The operational model of Concurrent METATEM is both general purpose and intuitively appealing. The use of broadcast message-passing provides both a general and flexible communication model for concurrent objects [Birman, 1991] and a natural interpre­ tation of distributed deduction [Fisher, 1997b]. These fea­ tures together provide a coherent and consistent programming model within which a variety of agent applications can be rep­ resented [Fisher, 1994].

3.1 Agents

As in the BDI framework, the basic elements of Concurrent METATEM are agents, although these need not necessarily be rational. There are two elements to each agent: its inteiface definition and its internal definition.

The definition of which messages an agent recognises, to­ gether with a definition of the messages that an agent may itself produce, is provided by the interface definition, which may be given as follows.

car() in: go,stop,turn out: empty,overheat

Here, {go, stop, turn} is the set of messages the 'car' agent recognises, while the agent itself is able to produce the messages {empty, overheat}.

The internal definition of each agent is given by a temporal logic specification [Manna and Pnueli, 1992]. Temporal logic is seen as classical logic extended with various modalities for representing temporal aspects of logical formulae [Emerson, 1990]. The temporal logic used here is based on a linear, discrete model of time. Thus, time is modelled as an infi­ nite sequence of discrete 'moments', with an identified start­ ing point, called 'the beginning of time'. Classical formulae are used to represent constraints within individual moments, while temporal formulae represent constraints between mo­ ments. Examples of temporal operators are given below.

()cp is true now if cp is true at some moment in the future.

• Ocp is true now if cp is true always in the future.

cp U 1jJ is true now if cp is true from now until a future moment when 1jJ is true.

Ocp is true now if cp is true at the next moment in time.

start is only true at the beginning of time.

As an agent's behaviour is represented by a temporal for­ mula, this can be transformed into the temporal normal form, SNF [Fisher, 1997a]. This process not only removes the ma­ jority of the temporal operators, but also translates the for­ mula into a set of rules suitable for either execution or verifi­ cation. Each of these rules is of one of the following varieties.

where each k;, m 1 or lis a literal. Note that SNF is just as ex­ pressive as the full temporal logic. This logical form provides the core elements for describing basic dynamic execution:

• a description of the current moment;
• a description of transitions that might occur between the current and the next moment;
• a description of situations that will occur at some, unspecified, moment in the future.

Thus, using this approach, the behaviour of an agent can be represented now, in transition to the next moment in time and at some time in the future [Fisher, 1995].

3.2 Executing Agent Descriptions

An agent's temporal specification can be implemented in a number of ways, for example through refinement to tradi­ tional programming languages. However, since temporal logic represents a powerful, high-level notation, a viable al­ ternative, at least for prototyping purposes if not for full im­ plementation, is to animate the agent by directly executing its temporal specification [Fisher, 1996].

In the case of Concurrent METATEM, the set of SNF rules is executed using the imperative future paradigm [Barringer eta/., 1996]. Here, a forward-chaining process is employed, using information about both the history of the agent and its current set of rules in order to constrain its future execution.

As an example of a simple set of rules which might be part of the car agent's description, consider the following.

Here, moving is false at the beginning of time and when­ ever go is true (for example, if a go message has just been received), a commitment to eventually make moving true is given. Similarly, whenever both go and moving are true, then either overheat or empty will be made true in the next moment in time.

The operator used to represent basic temporal indetermi­ nacy is the sometime operator, '0'. When a formula such as 'Ocp' is executed, the system must attempt to ensure that cp eventually becomes true. As such eventualities might not be able to be satisfied immediately, a record of the outstanding eventualities must be kept, so that they can be re-tried as ex­ ecution proceeds. The standard heuristic used is to attempt to satisfy as many eventualities as possible, starting with the oldest outstanding eventuality [Fisher and Owens, 1992].

An important consideration with respect to the practical implementation of Concurrent METATEM is that, although it can be made into a complete theorem-prover for tempo­ ral logic (at least in the propositional case), this is rarely done. Thus, the complexity of full theorem-proving is usu­ ally avoided [Fisher, 1996].

3.3 Concurrency, Communication and Grouping

We note that such asynchronously executing agents, commu­ nicating via broadcast message-passing, are very useful for developing open systems [Hewitt, 1991], while the notion of agent groups [Marui chi et at., 1991] is essential both for re­ stricting the extent of broadcast messages and for structuring the agent space.

3.4 Applications

The combination of executable temporal logic, asynchronous message-passing and broadcast communication provides a powerful and flexible basis for the development of agent­ based systems. Consequently, Concurrent METATEM has been applied in a number of areas, including distributed artifi­ cial intelligence, concurrent theorem-proving, artificial agent societies and transport systems [Fisher, 1994].

4 A Hybrid Approach

In this section, we show how an extended version of Concur­ rent METATEM can be used to implement the core facets of the BDI model. As we are keen to represent only the fun­ damental elements, there are a variety of details that we ig­ nore. For example, we will not consider real-time constraints, complex plan structures/libraries, or complex intention struc­ tures from the PRS, nor will we consider first-order temporal specifications, concurrent actions, multiple threads, cloning or grouping from Concurrent METATEM. In spite of these re- . strictions, we will show that the key elements of simple BDI architectures can be concisely and consistently represented and implemented using extended Concurrent METATEM.

4.1 Informational Aspects

As, in practical BDI architectures such as the PRS, beliefs are usually coded by ground instances of first-order predicate calculus, then these can be represented directly as (internal agent) facts in Concurrent METATEM. However, as Concur­ rent METATEM does not incorporate persistence, then this necessitates the addition of meta-level frame axioms, such as

Thus, an alternative approach is to directly add a new modal operator for belief to the logic executed within Concurrent METATEM. As in BDI, this is a modal dimension satisfying the KD45 axioms and the execution mechanism itself is mod­ ified to handle the persistence of beliefs, i.e. both the above frame axiom and the KD45 axioms are 'built in' to the exe­ cution mechanism.

Thus, this is the key logical extension provided to Con­ current METATEM. The logic executed is now a multi­ modal logic consisting of both temporal and doxastic dimen­ sions. Note that SNF has been extended to such logics else­ where [Fisher et at., 1996], and rules now incorporate the new belief modality, 'B'.

4.2 Motivational Aspects

The key observation we use regarding the BDI framework is that, in practice, there is often little fundamental difference between desires and intentions. The former represent all the goals that the agent wishes to achieve; the latter represent those that it is actively pursuing at present. Indeed, in the logical foundations of the BDI model [Rao, 1996b], both de­ sires and intentions are represented by the same type of modal logic (KD), while beliefs are represented by a different one (KD45). Thus, a very natural (althoughBratman [1987] takes a different view) mechanism for representing both intentions and desires is to use temporal eventualities. In particular, these are required to be satisfied eventually (if consistent), can be conflicting (e.g. ()cp and ()-.cp), and the system must choose between them in order to generate further execution.

4.3 Deliberative/Execution Aspects

Before considering the detailed execution within our ap­ proach and its relationship to BDI architectures, it is useful to examine the basic interpretation cycles for both the PRS [Rao and Georgeff, I 995] and core METATEM execution [Fisher and Owens, 1992]. These are presented in Fig. l. Note the close similarities, the main difference being the more com­ plex (and stratified) deliberation phase in the PRS.

Thus, the key modification of the execution mechanism concerns the implementation of deliberation. The subset of eventualities selected, the order in which they are attempted, and the mechanism for achieving them, are all the concern of deliberation. If, for the moment, we assume that desires and intentions are trivially achievable (this restriction is con­ sidered further below), then we can describe the key deci­ sion mechanisms of the two approaches as follows. As de­ liberation is concerned with weighing up each of the possible choices and choosing a subset to actually undertake, then in Concurrent METATEM, the eventualities (desires/intentions) are simply ordered by age and the oldest one is attempted first, while in BDI systems, each is examined in turn and a specific cost function is used to generate an ordering.

In order to provide added flexibility within the language, we allow the user to redefine the priority functions used within deliberation. Thus, the system requires a desire pri­ ority function, Pd. which takes as arguments a list of eventu­ alities (desires), and the history of the execution, and returns an ordered list of eventualities (intentions). This is then used to control the part of deliberation that extracts intentions from desires. In standard Concurrent METATEM, this would sim­ ply involve comparing the age of each eventuality; in the PRS this function would typically be much more complex, incor­ porating a variety of aspects of the current and past state of the agent.

If we were to remove the above simplification whereby in­ tentions are trivially achieved, we could also allow a user de­ fined intention priority function, Pi· which takes as arguments a list of eventualities (intentions), the history of the execu­ tion, and a list of plan definitions, and returns an ordered list of eventualities (intentions) to be executed immediately. In the PRS, the list returned would typically only contain one element (as only one step is taken at each cycle), though this framework can obviously accommodate more complex sys­ tems.

Thus, the simple deliberation mechanism in Concurrent METATEM (see Fig. I) is replaced by a two stage process whereby the function Pd is used to generate a list of inten­ tions and the function p; is used to choose appropriate ac­ tions, based upon this intention list. The implementation of these priority functions may be carried out in a number of ways, for example via meta-level METATEM rules [Barringer et al., 1991] directly provided by the user.

In this way a language for implementing simple BDI-like systems can be provided by extending Concurrent METATEM with belief elements and user definable priority functions for use in deliberation. Note that the more complex elements of practical BDI systems may also be represented in this lan­ guage. For example, in [Mulder et al., 1996], an implementa­ tion of a simplified version of the PRS is provided, incorpo­ rating a range of low-level details, such as the manipulation and interpretation of plan components. Simply, dependen­ cies between plans can be provided by asserting that if any sub-plan has not been constructed, the plan itself can not be completed, e.g.

However, motivation for the work described in this paper is provided by the observation that such a representation of the PRS can be improved, simply by extending Concurrent METATEM with elements from the BDI model.

4.4 Analysis

There are five notable points to make regarding this hybrid approach of extending executable temporal logic with aspects of the BDI model.

Firstly, since the key elements added are the KD45 belief modality and the user defined priority functions, the Concur­ rent METATEM execution mechanism remains relatively un­ changed. The efficiency of such an approach depends primar­ ily on the complexity of the priority functions provided. For example, if a simple age-ordering function is used, then the speed is comparable with that of Concurrent METATEM.

A variety of deliberation mechanisms can be represented by the use of user definable priority functions within the ex­ ecution mechanism. The constraints upon this are the com­ plexity of evaluating such functions and the expressive power of the logical notation. Regarding the latter, the logical rule form is as expressive as full temporal logic and so a wide va­ riety of functions can potentially be provided.

For this hybrid approach a formal semantics can be devel­ oped, though it would be parameterised by the semantics of the priority functions . If only sequences of actions under­ taken are considered, then executions represent appropriate models for the BDI logics [Rao, 1996b].

This approach provides increased expressive power. Not only can a variety of priority functions be defined, but ad­ ditional elements of Concurrent METATEM, such as multi­ threading and disjunctive rules, can potentially be incorpo­ rated.

Finally, while there are no explicit axioms linking, say, be­ liefs and intentions (as are often found in theoretical works concerning BDI), rules in the program can be used to par­ tially provide these, for example Bcp '* 0€ links beliefs and desires (eventualities).

5 Conclusions and Future Work

In this paper, we have described an extension to Fisher's Con­ current METATEM language that presents the possibility of implementing BDI-like systems using a form of executable multi-modal logic. While we do not claim that all BDI sys­ tems can be implemented using this approach, we believe a significant range of applications can be, providing the prior­ ity functions defined are not excessively complex.

The key observations from this work are that, in BDI sys­ tems, beliefs are primitive and distinct, while desires and intentions can essentially be represented as the same kind of entities. This, together with the observation that de­ sires/intentions correspond, in many respects, to eventualities in temporal logic, allows the definition of basic BDI entities within Concurrent METATEM. Thus, this work separates the basic elements of the model (beliefs and desires) from the mechanisms for manipulating these and deciding how to act (deliberation).

While this approach will not be as efficient as directly im­ plemented BDI systems, such as the PRS, it provides the op­ portunity at least for prototyping of BDI systems. The execu­ tion of temporal logic through Concurrent METATEM is well understood and, although the extended language requires the execution of a multi-modal logic, it remains a relatively in­ expensive extension. As execution at an attempt to construct a model, rather than a complete theorem-proving process, it represents a relatively cheap mechanism for animating a spec­ ification. At the other extreme, it is difficult to see how the multi-modal BDI logic from [Rao, 1996b] could be directly executed.

Our future work concerns three areas: extended lan­ guages; refined priority functions; and expanded formal se­ mantics. As mentioned above, there are elements of Con­ current METATEM that are not required in the BDI model. It is thus interesting to consider how these elements could be used in the framework described here. Also, once such a system is produced, it is relatively easy to extend it with the other elements of Concurrent METATEM, such as cloning and grouping. The definition of a range of detailed deliberation strategies, via appropriate priority functions, is another obvious direction. Finally, the temporal semantics of Con­ current METATEM must be adapted to fully incorporate the above extensions.