Analysis of Inheritance Mechanisms in Agent-Oriented Programming

1 Introduction

Multi-agent systems are concurrent systems based on the notion of autonomous, reactive, internally-motivated agents interacting in a constantly changing environment. Research in this field has been primarily concerned with conceptual and architectural issues of these systems and how they can be applied to real-world problems. More recently, there has been an increasing trend towards cap­ turing the essential features of these systems and em­ bodying them into language constructs, popularly called Agent-Oriented Programming (AOP) [Shoham, 1993; Wooldridge and Jennings, 1994], as well as developing a methodology for analysing and designing such sys­ tems, the emergence of Agent-Oriented Methodology (AOM) [Brazier et al., 1995; Kinny et al., 1996].

Naturally, work in AOP and AOM has been influenced by existing paradigms - especially the Object-Oriented Programming (OOP) paradigm. Although, AOP is often viewed as a special case of OOP [Shoham, 1993], very lit­ tle attention has been given to one of the major aspects

Kotagiri Ramamohanarao

Dept. of Computer Science The University of Melbourne

Vic. 3052, Australia

E-mail: rao@cs.mu.oz.au

of OOP, namely, inheritance. The basic concept of inher­ itance allows the user to define a new class by extending an existing class with additional variables and methods. By sharing code among classes in this way, the total amount of code in a system can be reduced drastically.

Agents, unlike classical objects, need to synchro­ nise their autonomous and reactive behaviour (multiple threads), they need to interact with the environment and other agents (the agent space is inherently concurrent) as well as commonly being required to satisfy real-time constraints. As a result , agents are usually significantly more complex than typical objects, both in their inter­ nal structure and in the behaviours they exhibit. Code re-use becomes highly important in such a context since it is much easier to design systems by extending already proven programs. Thus, the very complexity of agents makes the notion of inheritance a very useful and pow­ erful tool for AOP. This paper addresses the notion of inheritance - its meaning, its potential benefits, and the problems that arise in introducing it within AOP.

An inheritance mechanism specifies exactly how exist­ ing agent descriptions may be inherited to produce new descriptions. One of the important decisions to be made by the language designer with respect to inheritance is deciding on its granularity, i.e., what is the smallest unit of re-use within agents. This choice influences the useful­ ness of the concept, its expressiveness and its flexibility in aiding the development of re-usable agents.

The potential benefits of introducing inheritance in AOP are two-fold. First, it can reduce the complexity of the programming effort by enabling code sharing. In particular, an agent system may be designed by mod­ elling the abstract behaviours of its constituent agents (e.g., their roles). Agents exhibiting related abstract be­ haviours are expected to share a large part of their im­ plementations. Second, it can facilitate the modular ver­ ification of multi-agent systems. Assume that we have proven certain behavioural properties of an agent family. It would be very useful, if rather than starting from first principles, one could prove properties of a derived agent family from provable properties of the original family.

However, the realisation of these potential benefi ts de­ pends crucially on how one defines the inheritance mech­ anism. In particular, two types of problems could occur: the lack of behaviour preservation and the presence of inheritance anomalies. The lack of behaviour preserva­ tion leads to the need to prove properties about each agent implementation in an inheritance hierarchy from first principles (i.e., the second benefit above is notre­ alised). Inheritance anomalies are related to the expres­ sive power of an inheritance mechanism. An inheritance anomaly occurs when the inheritance mechanism is not powerful enough to provide code sharing between agents implementing related abstract behaviours (i.e., the first benefit above is not realised). These two problems can greatly reduce the usefulness of inheritance. Solving them requires the design of more complex inheritance mechanisms. We show that this usually leads to a trade­ off, i.e., designing more complex mechanisms may reduce the occurrence of inheritance anomalies while increasing the problems with behaviour preservation.

The key contributions of the paper are at two lev­ els. At the technical level it presents a formal frame­ work of inheritance, behaviour preservation, and inher­ itance anomaly. Using this framework, we prove that certain classes of inheritance mechanisms are behaviour preserving and anomaly-free. Examples of inheritance mechanisms are provided using the agent model of an implemented agent system - dMARS (distributed Multi­ Agent Reasoning System). At the conceptual level, we believe the paper brings the technical rigour of analysis of classical programming languages to the field of agent­ oriented programming. We hope that our analysis can help other researchers to make similar investigations of formal aspects of agent-oriented concepts before intro­ ducing them as language constructs in AOP languages.

2 Informal analysis

This section presents the dMARS programming environ­ ment and gives examples of typical problems that can arise when inheritance is introduced.

2.1 The agent setting

dMARS is an agent-oriented distributed real-time sys­ tem based on the popular PRS model of agents [Georgeff and Lansky, 1986]. It provides a representational frame­ work and reasoning mechanism for implementing agents.

An agent family X is a tuple (Bx, G x, Px ). Bx is a set of belief atoms where each belief atom b(v) (b is a predicate symbol, v = (v1 , ... , vn), Vi is a term) pro­ vides information about the state of the environment as perceived by the agent . G x is a set of goals, where each goal describes the desired state of the system. If g is a predicate symbol and v is as defined before, the goal !g(v) states that the agent wants to achieve a state where g(v) is a true belief. Px is a set of plans, where each plan specifies how to accomplish a goal or react to certain situations. An agent family is a set of agent instances (or simply agents) that have the same set of beliefs, achieve the same set of goals, and use the same set of plans to achieve all their goals. Agent instances are dynamic, run-time entities, while agent families are static descriptions corresponding to classes in OOP. At any point in time an agent contains a set of ground be­ lief atoms. Agent reacts to events occurring in its en­ vironment by invoking its plans. Plans can also be in­ voked by events generated internally by the agent. Each plan consists of an invocation condition, context condi­ tion and a plan graph, e.g., the plan p is denoted by (pinv, Pcon, Pp 9 ) . The invocation condition identifies the event that must occur for this plan to be invoked. The events considered are the addition (+)/deletion (-) of beliefs/goals. Hence, +b(v), -b(v), +!g(v), -!g(v) are events. The context condition is a logical formula com­ posed from belief atoms and the connectives 1\ and V. The context condition must be satisfied by the set of ground belief atoms of the agent for the plan to IJe ap­ plicable. Plan graphs are acyclic graphs with their edges labelled with the sub-goals or primitive actions that have to be satisfied or performed in order for the main goal to be satisfied. We make a distinction between public goals and private(intemal) goals. In particular,G x ~ {!g(v) : 3p E Px such that Pinv = +!g(v) }, is the set of all public goals that can invoke plans of an agent family X. A specific instance of an agent family acquires anini­ tial set of ground beliefs, goals to be achieved, and the plans of the agent family. When the agent interacts with the environment, it adopts and commits to plans forming intentions. Details are provided elsewhere [Rao, 1996].

Example 1 Figure 1 shows several plans of an agent family SimplePlane which describes agents simulating simple types of planes. The event +!landed(base) triggers the first plan which is designed to land the plane in good weather (w(good)) and good visibility (v(good)). The execution of this plan involves executing the sub-goal !checkPos(V) which then triggers the respective plans. The choice between the two plans for !checkPos(V) is based on a notion of priorities. The higher priority plan is tried first, and if it fails then the second plan is tried.

The plan for +rain(V) reacts to a change in the envi­ ronment. It is triggered when the new belief rain(V) is added to the agent's set of beliefs. ·

We now illustrate the problems that may arise when a simple inheritance mechanism is added to an agent­ oriented language such as dMARS. Inheritance is intro­ duced by following well-known OOP concepts. Hence, an agent (object) inherits all the plans (methods) of its par­ ent, re-defines some plans and possibly adds new plans.

2.2 Behaviour preservation - an example

Agents, interacting with the environment generate be­ haviours. Characterising the interesting aspects of a behaviour is highly application specific and non-trivial. In some applications, behaviour can be characterised by considering what goals were achieved, while in some oth­ ers one may want to capture how the goals were achieved, or when they were achieved (e.g., real-time systems). In this section, we look at behaviour preservation with re­ spect to the first characterisation, i.e., what goals are achieved. Suppose we have implemented an agent family X, and proven that it achieves some desired behaviour. A new agent family Y is defined by inheriting X and adding some new plans. Does an arbitrary instance of Y at least still achieve all the goals that an arbitrary instance of X could achieve (if placed in the same envi­ ronment)? In other words, can we guarantee some prop­ erties of Y without needing to prove them explicitly?

Example 2 Suppose instances of SimplePlane always land successfully in good weather and visibility. Consider a new agent family AdvancedPlane which inherits all the plans of SimplePlane and adds a new plan for the goal !landed(V) enabling its instances to land in all weather and visibility conditions. We have inherited and ex­ tended SimplePlane with a new plan. Now we need to verify that an instance of AdvancedPlane can actually land in all conditions. However, we cannot even guar­ antee that it can land in good weather and visibility. If the new plan has higher priority than the inherited plan for !landed(V) then the new plan is triggered first. The new plan could contain an error, causing SimplePlane to crash. Hence, a verification of the desirable behaviour for AdvancedPlane must be done from first principles. ·

Note that there are always particular examples of in­ heritance which do in fact preserve behaviour. In Exam­ ple 2, if the inherited plan has higher priority than the new plan then the behaviour of SimplePlane is preserved by AdvancedPlane (it is immediately known that both can land in good weather and visibility). More complex examples can be constructed that do not involve plan priority and yet fail to guarantee behaviour preservation. Such examples are based on the operational semantics of plan execution. Ideally, the inheritance mechanism should guarantee behaviour preservation.

2.3 Inheritance anomaly - an example

Suppose we have defined an agent family X which imple­ ments our desired behaviour. Now, we want to build a specialised agent family Y that can achieve all the goals that X can achieve, and also some additional goals. We should be able to implement Y by inheriting all the plans from X, while any behaviours not exhibited by X are im­ plemented by writing new plans. If it is not possible for X and Y to share the code in this way, then we have an occurrence of inheritance anomaly.

Example 3 Suppose we define a new agent family New­ Plane by inheriting SimplePlane and adding a new plan for !checkPos(V). The new plan has the context condi­ tion v(poor), enabling the agent to check its position in poor visibility. Thus, an instance of NewPlane should be able to land in good weather, under any visibility. The problem is that the context condition of the inherited plan for !landed(V) still restricts the agent to land only in good visibility. This plan must be re-written with a new context condition, w(good). Hence, even though there is some code sharing between N ewPlane and Sim­ plePlane (the plan for +rain(V) and the existing two plans for !checkPos(V)), the amount of code sharing has been unnecessarily reduced. It is possible to construct examples where none of the plans can be shared. ·

Re-defining plans of the parent family is error-prone, time consuming, and it violates the notions of modular­ ity and encapsulation. Inheritance was designed to solve exactly this problem by code sharing. Thus, inheritance anomalies greatly decrease the usefulness of inheritance.

3 Formal analysis

In this section, we firstly define an inheritance mech­ anism to be the set of transitions from one syntactic specification to another. We provide two examples of such mechanisms with varying expressive power. Next, abstract behaviours of agent families are formalised and two alternative ways of defining behavioural equiva­ lence (i.e., when do two agent families exhibit the same behaviour) are considered. The language semantics de­ termines how syntactic specifications are mapped into behaviours. The notions of behaviour preservation and inheritance anomaly are then formalised by analysing the behaviours of derived and original syntactic specifi­ cations. Behaviour preservation is similar to the notion of soundness: only the desirable behaviours should be derivable by the given inheritance mechanism. Inheri­ tance anomaly is similar to the notion of completeness: all desirable behaviours should be derivable by the in­ heritance mechanism. Finally, we prove which of our inheritance mechanisms are behaviour preserving and anomaly-free.

3.1 Inheritance mechanism

First, we provide a general definition of an inheritance mechanism and then specialise it to AOP. An inheri­ tance mechanism can be viewed as a transition relation between syntactic specifications. More formally we have:

Definition 1 An inheritance mechanism is a tuple (Spec, A,-+,--+) where -+~ Spec x A x Spec. An ele­ ment of-+, (a, 6, b) is called a transition where a, bE Spec and 6 E A. Spec is the set of all syntactic specifications. The set A is the set of syntactic entities which specify the differences between a and b. We write a ~ b for 6Et> · (a , 6, b) E-+. Furthermore, a "-+ b is used to denote the transitive closure of -+, i.e., a sequence of transitions. Remark that the overloading of the notion a ~ b is quite harmless. The relation --+ ~-+ is the set of in­ cremental transitions which maximise code sharing. ·

In the context of AOP, a syntactic specification is sim­ ply the definition of an agent family. Intuitively, the transitions specify how inheritance can be used to move from a syntactic specification a (e.g., SimplePlane in Ex­ ample 2) to a new specification b (a full definition of Ad­ vancedPlane) by specifying the differences (the new plan for !landed(V)) in 6. The general form of Definition 1 is specialised to AOP by instantiating Spec to the set of all possible agent family definitions, i.e., the set includ­ ing X, Y, ... etc. Introducing inheritance to an agent language also means defining a particular instance of re­ lations-+ and --+, i.e., giving a set of transitions. Given our definition of an agent family the following possibil­ ities arise: We can derive an agent family specification Y from an agent family X, by (a) adding or deleting be­ lief atoms; (b) adding or deleting goals; and (c) adding, deleting, or modifying plans. While additions and dele­ tions of belief atoms, goals, and plans in an agent family specification are straightforward, there are many ways in which a plan can be modified. A plan can be modified by modifying the invocation, context, or plan graph. We do not consider Case (a) in this paper. Now we consider a useful type of inheritance obtained by following the basic idea of inheritance as found in OOP (as in Section 2):

Agent family Y is obtained from X by having the same set of beliefs, but adding more goals, adding new plans for these goals, and modifying some or all of the existing plans for the existing goals. Definition 2 states that if an agent family Y has more plans than an agent fam­ ily X then Y can be obtained by inheritance from X. The point is that re-defining all the inherited plans may leave the specifications of X and Y totally unrelated (no code is shared) apart from their relative number of plans. The specifications of X and Y only share code if at least some inherited plans are not re-written in Y. Of course, the desirable situation arises when there is a maximal amount of code sharing in the system, i.e., when some new plans are added and none of the inherited plans is re-defined. This leads to the notion of incremental tran­ sitions. Incremental transitions only extend the exist­ ing family specifications without re-defining them in any way. ·We consider two useful inheritance mechanisms. The first mechanism (Definitions 2 and 3) allows incre­ mental addition of plans for new and existing goals. The second mechanism (Definitions 2 and 4) allows incremen­ tal addition of plans only for new goals.

The relation --+plan allows family specifications to be extended by the addition of new plans. The granular­ ity of --+plan is a single plan since any new plan can be added. Another possible choice is the granularity of sets of plans, i.e., the set of plans for an existing goal cannot be incrementally extended. The relation --+set is the subset of all incremental transitions of -+mod at the granularity of sets of plans.

Under this definition only the plans written to achieve new goals can be added. For instance, a new plan with the invocation condition +!landed(V), +!checkPos(V) or +rain(V) cannot be added in Example 1.

3.2 Behavioural equivalence

Next, we consider the notion of behaviour of an agent family. As discussed earlier, one can capture the notion of behaviour in many ways depending on the purpose of a particular application domain. We need some way of comparing the behaviours of derived agent families with the behaviours of the original agent families. In this pa­ per, we consider two alternatives. We say that two agent families are behaviourally equivalent if: (a) they have the same public goals; or (b) their instances can achieve the same goals, when placed in the same environment. We consider each of these alternatives more formally.

Definition 5 Let X and Y be agent families . X :::: 1 Y iff Gx = Gy (X ~1 Y iff Gx ~ Gy). ·

Definition 5 is a simple definition of behavioural equivalence which states that agent families X and Y have equivalent behaviour (X :::: 1 Y) if they have the same public goals. Hence, their instances have the potential to achieve the same goals. However, instances of X and Y may achieve the same goals under very different con­ ditions (since their plans may be different). This defini­ tion corresponds to the OOP notion of type-equivalence based on interfaces. It can be shown that =: 1 is an equiv­ alence relation, it is reflexive, symmetric and transitive.

The second definition of behavioural equivalence is concerned with more details about exactly under which conditions are particular goals achieved by an agent. It uses the notion of traces. Assume there is an external ob­ server who records the sequence of all the events occur­ ring in the environment of an agent. At every point in time the observer has noted down a finite trace of a possi­ ble evolution of this concurrent agent/environment sys­ tem. The (infinite) set of all such finite sequences of events is called the set of traces of the system and is de­ noted by traces(xiiE) where x is an agent instance, E is the environment (non-deterministic) and II is the con­ currency operator. Placing an agent into an environment determines the agent's initial beliefs, its initial goals and its subsequent behaviour. Different instances of an agent family yield the same set of traces if placed in the same environment, but may exhibit different sets of traces if placed in different environments. We define traces(X) as the union of all traces(xiiE) for all possible E and x.

Example 4 Two possible traces of the system in Exam­ ple 1 are: tr1 = ( +!landed(base}, +pos(S}, +sun(strong), +pos(3}, +wind(weak}, +pos(l}, +landed(base) ) and tr2 = ( +!landed(base), +rain(strong), +pos(S}, +wind(strong}, +crashed(} ). ·

Definition 6 The trace s j t if s is a prefix of t ((e1) j (e1,e2)) . Concatenation of two traces is denoted by A ((e1r(e2,e3) = (e1,e2,e3)). We use the standard interleaving semantics of concurrent events. ·

Definition 7 Let x, y be arbitrary instances of X, Y. Let goaLtraces!g(v)(xiiE) = {s: sA(+g(v)) E traces(xiiE)} where !g(v) E G x is the goal to be achieved. Then, X ~2 Y if for any environment E, whenever s E goaLtraces!g(v) (xiiE) either:

1. 3t E goaLtraces!g(v) (YIIE) such that t j s; or
2. 3t E traces(yiiE) : s j t, and for each such t 3u E goaLtraces!g(v)(YIIE): s j u j t V t j u.

Also, X =2 Y iff X ~2 Y and Y ~2 X. Again, it can be checked that =:2 is reflexive, symmetric and transitive. ·

This definition of behavioural equivalence requires that all instances of two agent families can achieve the same goals if placed in the same environment (the goals may be achieved by adopting different plans, and thus generating different internal events). An ob­ server records events occurring in the environment un­ t il the achievement of the goal (or failure). The set goaLtraces!g(v) contains all traces which lead to the achievement of goal !g(v) 1 . The trace tr1 from Example 4 (without the last event +landed(base)) is an ele­ ment of goaLtraces!landed(base) of an instance of Simple­ Plane, while tr2 is not. An agent family Y preserves and extends the behaviour of an agent family X (X ~2 Y) if whenever an instance x of X achieves the goal then an instance y of Y (assuming y is in the same environment as x) either: (a) has already achieved the goal; or (b) independently of what happens in the environment after this point, y eventually achieves the goal.

1 We assume that an agent is never asked to achieve a goal which is not in the set of its public goals.

Example 5 Recalling the examples of Section 2 we have: SimplePlane ~2 NewPlane (NewPlane can land in poor visibility), and NewPlane ~2 AdvancedPlane (Ad­ vancedPlane can also land in bad weather). ·

3.3 Behaviour preservation

Having defined the inheritance mechanism and be­ havioural equivalence we examine their relationship by revisiting the notions of behaviour preservation and in­ heritance anomaly. Behaviour preservation expressed in a general form addresses the soundness issue. It ensures that an incremental transition from one syntactic specifi­ cation to another leads to a related behaviour (the origi­ nal behaviour is preserved and extended, as given by ~).

Definition 8 Let a, b E Spec, 8 E .6. and let ~ be an ordering on behaviours. Inheritance mechanism (Spec , .6. , --+, --+) is behaviour preserving under ~ if 'v'a, b. 0

Definition 8 is specialised to AOP by considering spe­ cific inheritance mechanisms and specific behavioural equivalences. Behaviour preservation also depends on the exact semantics of the chosen language. Theorem 1 shows that the inheritance mechanism which allows new plans to be added for new and existing goals is be­ haviour preserving only under our simpler definition ~1 (for counter-example under ~2 see Example 2).

Theorem 1 (SpeCAQP, .6.AoP, -+mod , --+ plan) is be­ haviour preserving under ~1 .

The inheritance mechanism where plans can be added only for new goals is behaviour preserving under both characterisations of behavioural equivalence.

Theorem 2 The mechanism (SpeCAQP, .6.AoP, -+mod , --+set) is behaviour preserving under ~1 and under ~2 · 0 Proof: Let X --+set Y and s E goaLtraces!g(v) (xiiE) . The trace of s contains +!g(v) which triggered some plan q · E Px to execute. Since Py = Px U 8, and since {Pinv : p E Px} n {Pinv : p E 8} = 0, the same plan q E Py was executed in y. It follows by similar arguments that s E goaUraces!g(v)(YIIE). Hence, goaLtraces!g(v)(xiiE) ~ goaLtraces!g(v)(YIIE) . Also, X ~2 Y by letting t = s in Case (a) of Defini­ tion 7. The proof for ~1 is similar to Theorem 1. ·

The results of Theorems 1 and 2 seem to suggest that the inheritance mechanism employing the incremental additions at the granularity of sets of plans is the better solution. The next section will make a similar compari­ son with respect to the problem of inheritance anomalies.

3.4 Inheritance anomaly

Inheritance anomaly, in its general form, addresses the completeness issue. An inheritance mechanism is anomaly-free if all related behaviours can be derived by incremental transitions, thus maximally sharing code.

Definition 9 Let a, bE Spec and :::; be an ordering rela­ tion on behaviours. Inheritance mechanism (Spec,~, -t , ---t) is anomaly-free under :::; if Va, b. a :::; b ==> 0 3 8 E ~ * and c E Spec such that a ---t c and b = c, where = is the equivalence relation induced by :::; . ·

Definition 9 requires that any related behaviour of a must be reachable from a by incremental transitions. The desired behaviour of b is reached by inheriting and extending a to obtain c. If this requirement cannot be satisfied for some a and b then we have an occurrence of the anomaly. Note that in general c and b are differ­ ent implementations of the same behaviour. Similarly to behaviour preservation, the anomaly is highly language dependent, and also depends on the definition of = .

Theorem 3 The inheritance mechanism -*mod is anomaly-free under :::;1 . This holds for both ---t plan and ---t set . The proof follows from Definitions 3 and 4. ·

Both inheritance mechanisms suffer from inheritance anomalies under :::;2, as shown in Example 3. However, the choice of the granularity of sets of plans ( ---t set) leads to more anomalies than the finer granularity of ---t plan.

Theorem 4 Every inheritance anomaly that occurs in -*mod with ---t plan also occurs in -*mod with ---t set . The converse does not hold. The proof follows from the fact that ---tset~---tplan. ·

This theorem illustrates the trade-off in the choice of inheritance mechanisms. The granularity of sets of plans is behaviour preserving, but it leads to more anomalies.

4 Comparison and conclusion

The notion of inheritance has been studied extensively in OOP and is non-existent in AOP. The well-known in­ heritance mechanisms in OOP languages do not suffer from the problems described in the paper. Inheritance anomaly occurs, and has been researched, in concurrent object-oriented programming [Matsuoka and Yonezawa, 1993]. However, it has not been formally defined.

In this paper, we have introduced the notion of in­ heritance into AOP and examined the potential benefits it offers in terms of code sharing and modular verifica­ tion of agent systems. However, there are potentially serious problems with inheritance in AOP, namely be­ haviour preservation and inheritance anomaly. In this paper we have provided a formal framework to exam­ ine these problems and the trade-offs involved in solv­ ing them. We analysed two inheritance mechanisms and two definitions of behavioural equivalence, and showed which of them were behaviour preserving and anomaly­ free. The formal framework we provide is generic and can be applied to other agent-oriented languages, such as AGENTO [Shoham, 1993], PLACA [Thomas, 1994], or CONGOLOG [Lesperance et al., 1995], by altering the definition of specifications (Spec), transitions (~), and behavioural equivalence. More importantly, we believe that our approach to the introduction of inheritance into AOP lays the preliminary groundwork for rigorous anal­ ysis of language issues, such as inheritance, within the framework of multi-agent system research.