A Roadmap of Agent Research and Development
Department of Electronic Engineering, Queen Mary and Westfield College, London E1 4NS, UK
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA. 15213, USA
"#%$& ' '
[email protected] Department of Electronic Engineering, Queen Mary and Westfield College, London E1 4NS, UK
Received November 25, 1995; Revised March 30, 1996 Editor: ???
Abstract. This paper provides an overview of research and development activities in the field of autonomous agents and multi-agent systems. It aims to identify key concepts and applications, and to indicate how they relate to one-another. Some historical context to the field of agent-based computing is given, and contemporary research directions are presented. Finally, a range of open issues and future challenges are highlighted.
Keywords: autonomous agents, multi-agent systems, history
1. Introduction
Autonomous agents and multi-agent systems represent a new way of analysing, design- ing, and implementing complex software systems. The agent-based view offers a power- ful repertoire of tools, techniques, and metaphors that have the potential to considerably improve the way in which people conceptualise and implement many types of software.
Agents are being used in an increasingly wide variety of applications — ranging from comparatively small systems such as personalised email filters to large, complex, mission critical systems such as air-traffic control. At first sight, it may appear that such extremely different types of system can have little in common. And yet this is not the case: in both, the key abstraction used is that of an agent. It is the naturalness and ease with which such a variety of applications can be characterised in terms of agents that leads researchers and de- velopers to be so excited about the potential of the approach. Indeed, several observers feel that certain aspects of agents are being dangerously over-hyped, and that unless this stops soon, agents will suffer a similar backlash to that experienced by the Artificial Intelligence (AI) community in the 1980s [96, 156].
Given this degree of interest and level of activity, in what is a comparatively new and multi-disciplinary subject, it is not surprising that the field of agent-based computing can appear chaotic and incoherent. The purpose of this paper is therefore to try and impose some order and coherence. We thus aim to tease out the common threads that together make up the agent tapestry. Our purpose is not to provide a detailed review of the field, we leave this to others (for example, [154, 11, 74, 111, 158]). Rather than present an in-depth analysis and critique of the field, we instead briefly introduce the key issues, and indicate
how they are inter-related. Where appropriate, references to more detailed treatments are provided.
Before we can embark on our discussion, we first have to define what we mean by such terms as “agent”, “agent-based system” and “multi-agent system”. Unfortunately, we im- mediately run into difficulties, as some key concepts in the field lack universally accepted definitions. In particular, there is no real agreement even on the core question of exactly what an agent is (see [52] for a discussion). Of course, this need not be a serious obstacle to progress, (the AI community has made progress without having a universally accepted definition of intelligence, for example). Nevertheless, we feel it is worth spending some time on the issue, otherwise the terms we use will come to lose all meaning. For us, then, an agent is a computer system, situated in some environment, that is capable of flex- ible autonomous action in order to meet its design objectives (this definition is adapted from [158]). There are thus three key concepts in our definition: situatedness, autonomy, and flexibility.
Situatedness, in this context, means that the agent receives sensory input from its en- vironment and that it can perform actions which change the environment in some way.
Examples of environments in which agents may be situated include the physical world or the Internet. Such situatedness may be contrasted with the notion of disembodied intel- ligence that is often found in expert systems. For example,MYCIN, the paradigm expert system [134], did not interact directly with any environment. It received information not via sensors, but through a user acting as a middle man. In the same way, it did not act on any environment, but rather it gave feedback or advice to a third party.
Autonomy is a difficult concept to pin down precisely, but we mean it simply in the sense that the system should be able to act without the direct intervention of humans (or other agents), and that it should have control over its own actions and internal state. Others use it in a stronger sense, to mean systems that are capable of learning from experience [125, p35].
Of course, situated, autonomous computer systems are not a new development. There are many examples of such systems in existence. Examples include:
# any process control system, which must monitor a real-world environment and per- form actions to modify it as conditions change (typically in real time) — such systems range from the very simple (for example, thermostats) to the extremely complex (for example, nuclear reactor control systems);
# software daemons, which monitor a software environment and perform actions to mod- ify the environment as conditions change — a simple example is the UNIXxbiffpro- gram, which monitors a user’s incoming email and obtains their attention by displaying an icon when new, incoming email is detected.
While the above are certainly examples of situated, autonomous systems, we would not consider them to be agents since they are not capable of flexible action in order to meet their design objectives. By flexible, we mean that the system is [158]:
# responsive: agents should perceive their environment and respond in a timely fashion to changes that occur in it;
pro-active: agents should not simply act in response to their environment, they should be able to exhibit opportunistic, goal-directed behaviour and take the initiative where appropriate;
# social: agents should be able to interact, when appropriate, with other artificial agents and humans in order to complete their own problem solving and to help others with their activities.
While other researchers emphasise different aspects of agency (including, for example, mobility or adaptability) we believe that these four properties are the essence of agent- hood. Naturally, some agents will have additional characteristics, and for certain types of applications, some attributes will be more important than others. However, we believe that it is the presence of all the attributes in a single software entity that provides the power of the agent paradigm and which distinguishes agent systems from related software paradigms
— such as object-oriented systems, distributed systems, and expert systems (see [156] for a discussion).
With the basic building block notion of an agent in place, we can define more of our terminology. By an agent-based system, we mean one in which the key abstraction used is that of an agent. In principle, an agent-based system might be conceptualised in terms of agents, but implemented without any software structures corresponding to agents at all. We can draw a parallel with object-oriented software, where it is entirely possible to design a system in terms of objects, but to implement it without the use of an object- oriented software environment. But this would at best be unusual, and at worst, counter- productive. A similar situation exists with agent technology; we therefore expect an agent- based system to be both designed and implemented in terms of agents.
As we have defined it, an agent-based system may contain one or more agents. There are cases in which a single agent solution is appropriate. A good example, as we shall see later in this article, is the class of systems known as expert assistants, wherein an agent acts as an expert assistant to a user attempting to use a computer to carry out some task. However, the multi-agent case — where the system is designed and implemented as several interacting agents — is arguably more general and more interesting from a software engineering stand- point. Multi-agent systems are ideally suited to representing problems that have multiple problem solving methods, multiple perspectives and/or multiple problem solving entities.
Such systems have the traditional advantages of distributed and concurrent problem solv- ing, but have the additional advantage of sophisticated patterns of interactions. Examples of common types of interactions include: cooperation (working together towards a com- mon aim); coordination (organising problem solving activity so that harmful interactions are avoided or beneficial interactions are exploited); and negotiation (coming to an agree- ment which is acceptable to all the parties involved). It is the flexibility and high-level nature of these interactions which distinguishes multi-agent systems from other forms of software and which provides the underlying power of the paradigm.
The remainder of this article is structured as follows. Section 2 focuses on individual agents, providing some background to the concepts involved, indicating the key issues that are being addressed, and highlighting some likely future directions for research and devel- opment. Section 3 presents a similar discussion for multi-agent systems. Section 4 draws together the two strands. It discusses some exemplar agent-based applications and pro-
vides some pointers to the likely future direction of applied agent work. Finally, section 5 presents some conclusions.
2. Autonomous Agents
The purpose of this section is to identify the various threads of work that have resulted in contemporary research and development activities in agent-based systems. We begin, in section 2.1, by identifying some key developments in the history and pre-history of the autonomous agents area, up to and including current systems. In section 2.2, we then identify some of the key issues and future research directions in autonomous agents.
2.1. History
Current interest in autonomous agents did not emerge from a vacuum. Researchers and developers from many different disciplines have been talking about closely related issues for some time. The main contributors are:
# artificial intelligence [125];
# object-oriented programming [10] and concurrent object-based systems [2, 4];
# human-computer interface design [97].
2.1.1. Artificial Intelligence. Undoubtedly the main contributor to the field of autonomous agents is artificial intelligence. Ultimately, AI is all about building intelligent artifacts, and if these artifacts sense and act in some environment, then they can be considered as agents [125]. Despite the fact that agency can thus be seen to be central to the study of AI, until the 1980s comparatively little effort within the AI community was directed to the study of intelligent agents. The primary reason for this apparently strange state of affairs was that AI researchers had historically tended to focus on the various different compo- nents of intelligent behaviour (learning, reasoning, problem solving, vision understanding and so on) in isolation. The expectation was that progress was more likely to be made with these aspects of intelligent behaviour if they were studied individually, and that the synthesis of these components to create an integrated agent would be straightforward. By the early 1970s, this assumption seems to have been implicit within most mainstream AI research. During this period, the area of research activity most closely connected with that of autonomous agents was AI planning [5].
AI planning research is the sub-field of AI that concerns itself with knowing what to do: what action to perform. Ultimately, an agent is just a system that performs actions in some environment, and so it is not surprising that AI planning research should be closely involved in the study of agents. The AI planning paradigm traces its origins to Newell and Simon’sGPS system [108], but is most commonly associated with the STRIPSplanning system ([45]) and its descendents (such as [23, 155]). A typicalSTRIPS-style planning system will have at least the following components:
a symbolic model of the agent’s environment, typically represented in some limited subset of first-order predicate logic;
# a symbolic specification of the actions available to the agent, typically represented in terms ofPDA(pre-condition, delete, add) lists, which specify both the circumstances under which an action may be performed and the effects of that action;
# a planning algorithm, which takes as input the representation of the environment, a set of action specifications, and a representation of a goal state, and produces as output a plan — essentially, a program — which specifies how the agent can act so as to achieve the goal.
Thus, planning systems decide how to act from first principles. That is, in order to satisfy a goal, they first formulate an entirely new plan or program for that goal. A planning systems would thus continually execute a cycle of picking a goalφ1, generating a planπ forφ1, executingπ, picking a new goalφ2, and so on. Crucially, such planning is based entirely around symbolic representations and reasoning.
Attention in AI planning research during the 1970s and early 1980s focussed primarily on the representations required for actions, and the planning algorithms themselves. Of particular concern was the demonstrated efficiency of the planning algorithm. With simu- lated micro-world examples (such as the well-known blocks world),STRIPS-style planning algorithms appear to give reasonable performance. However, it was rapidly discovered that such techniques do not scale to realistic scenarios. In particular, such algorithms were predicated on the assumption of calculative rationality [126]. The calculative rationality assumption may be informally defined as follows. Suppose we have some agent f , which will accept an observation of the world as input, do some computation, and sometime later generate an action output. Then f is said to enjoy the property of calculative rationality if the action it gives as output would be optimal if performed at the time f began its decision- making. Algorithms that have the property of calculative rationality by this definition will be guaranteed to make the best decision possible — but they will not necessarily make it in time to be of any use. Calculative rationality tends to arise in circumstances where the decision about which action to perform is made by an unconstrained search over the space of all possible decisions. The size of such search spaces are inherently exponential in the complexity of the task to be solved. As a consequence, search-based techniques tend to be impractical if results are required in any fixed time bound. Building on the burgeoning area of algorithmic complexity analysis that emerged in the late 1960s and 1970s, a number of theoretical results appeared in the 1980s which indicated that first-principles planning is not a viable option for agents that operate in such time-constrained environments. The best known of these results is due to David Chapman, who demonstrated that in many circum- stances, first-principles planning is undecidable [23]. So, building reactive agents, that can respond to changes in their environment in time for these responses to be useful, is not likely to be possible using first-principles planning techniques.
The apparent failure of early AI planning techniques to scale up to real-world problems, together with the complexity results of Chapman and others, led many researchers to ques- tion the viability of symbolic reasoning approaches to planning in particular and AI in general. The problem of deploying such algorithms in real-world systems also prompted
researchers to turn to the somewhat neglected issue of agent design. During the mid 1980s, an increasing number of these researchers began to question the assumptions upon which traditional symbolic AI approaches to agency are based. In particular, some researchers began to express grave reservations about whether symbolic AI, and in particular the logi- cist tradition in symbolic AI, was ultimately viable. Arguably the best-known of these critics was Rodney Brooks, who in a series of papers presented a number of objections to the symbolic AI model, and sketched out an alternative research program, which has been variously known as behavioural AI, reactive AI, or situated AI [15, 17, 16]. In these papers, Brooks emphasised several aspects of intelligent behaviour that he suggested were neglected by traditional approaches to agency and AI. In particular, he suggested that intel- ligent, rational behaviour is not an attribute of disembodied systems like theorem provers or traditional expert systems likeMYCIN, but rather that intelligence is a product of the in- teraction between an agent and its environment. In addition, Brooks emphasised the view that intelligent behaviour emerges from the interaction of various simpler behaviours.
As part of his research program, Brooks developed the subsumption architecture, an agent control architecture that employed no symbolic representations or reasoning at all.
Broadly speaking, a subsumption architecture agent is a collection of task accomplishing behaviours. Each behaviour is a finite state machine that continually maps perceptual in- put to action output. In some implemented versions of the subsumption architecture, this mapping is achieved via “situation action” rules, which simply determine an action to perform on the basis of the agent’s current state. However, in Brooks’ implementations, be- haviours were somewhat more sophisticated than this, for example allowing for feedback from previous decisions. The main point is that these behaviours do no symbolic reason- ing (and no search). While each behaviour is generating suggestions with respect to which action to perform, the overall decision about which action to perform is determined by in- teractions between the behaviours. Behaviours can interact in several ways. For example, one behaviour can “suppress” the output of another. Typically, the behaviours are organ- ised into a layered hierarchy, with lower layers representing less abstract behaviours (e.g., obstacle avoidance in physically embodied agents), and higher layers representing more abstract behaviours. Developing agents that exhibit coherent overall behaviour is a process of carefully developing and experimenting with new behaviours, usually by placing the agent in its environment and observing the results.
Despite its apparent simplicity, the subsumption architecture has nevertheless been demon- strated in several impressive applications (see, e.g., [137]). However, there are also a num- ber of disadvantages with the subsumption architecture and its relatives:
# If agents do not employ models of their environment, then they must have sufficient information available in their local environment for them to determine an acceptable action.
# Since purely reactive agents make decisions based on local information, (i.e., infor- mation about the agent’s current state), it is difficult to see how such decision making could take into account non-local information — it must inherently take a “short term”
view.
# It is difficult to see how purely reactive agents can be designed that learn from experi- ence, and improve their performance over time.
action output perceptual
input
(a) Horizontal layering Layer 1 Layer 2 Layer n
...
perceptual input
action output Layer 1 Layer 2 Layer n
...
(b) Vertical layering
Figure 1. Layered Agent Architectures
# A major selling point of purely reactive systems is that overall behaviour emerges from the interaction of the component behaviours when the agent is placed in its environ- ment. But the very term “emerges” suggests that the relationship between individual behaviours, environment, and overall behaviour is not understandable. This necessar- ily makes it very hard to engineer agents to fulfill specific tasks. Ultimately, there is no principled methodology for building such agents: one must use a laborious process of experimentation, trial, and error to engineer an agent.
# While effective agents can be generated with small numbers of behaviours (typically less that ten layers), it is much harder to build agents that contain many layers. The dynamics of the interactions between the different behaviours become too complex to understand.
By the early 1990s, most researchers accepted that reactive architectures are well-suited to certain domains and problems, but less well-suited to others. In fact, for most prob- lems, neither a purely deliberative (e.g., first-principles planner) architecture nor a purely reactive architecture is appropriate. For such domains, an architecture is required that in- corporates aspects of both. As a result, a number of researchers began to investigate hybrid architectures, which attempted to marry the best aspects of both deliberative and reactive approaches. Typically, these architectures were realised as a number of software layers.
The layers may be arranged vertically (so that only one layer has access to the agent’s sen- sors and effectors) or horizontally (so that all layers have access to sensor input and action output); see Figure 1.
As in the subsumption architecture, (see above), layers are arranged into a hierarchy, with different levels in the hierarchy dealing with information about the environment at different levels of abstraction. Most architectures find three layers sufficient. Thus at the lowest level in the hierarchy, there is typically a “reactive” layer, which makes decisions about what to do based on raw sensor input. Often, this layer is implemented using techniques rather similar to Brooks’ subsumption architecture (thus it is itself implemented as a hierarchy
of task accomplishing behaviours, where these behaviours are task-accomplishing finite state machines). The middle layer layer typically abstracts away from raw sensor input and deals with a knowledge level view of the agent’s environment [107], typically making use of symbolic representations. The uppermost level of the architecture tends to deal with the social aspects of the environment — it has a social knowledge level view [80]. We thus typically find representations of other agents in this layer — their goals, beliefs, and so on. In order to produce the global behaviour of the agent, these layers interact with one- another; the specific way that the layers interact differs from architecture to architecture. In some approaches (such as TOURINGMACHINES[43, 44]), each layer is itself constantly producing suggestions about what action to perform. In this case, mediation between these layers in order to ensure that the overall behaviour of the agent is coherent and consistent becomes an issue. In TOURINGMACHINESthis mediation is achieved by a control sub- system that determines which layer should have overall control of the agent. The control subsystem in TOURINGMACHINESis implemented as a set of rules, which can refer to the actions proposed by each layer. A similar idea is used in INTERRAP [104, 103]. Another similar architecture for autonomous agents is 3T [8].
A final tradition in the area of agent architectures is that of practical reasoning agents [14].
Practical reasoning agents are those whose architecture is modelled on or inspired by a the- ory of practical reasoning in humans. By practical reasoning, we simply mean the kind of pragmatic reasoning that we use to decide what to do. Practical reasoning has long been an area of study by philosophers, who are interested in developing theories that can account for human behaviour. Typically, theories of practical reasoning make use of a folk psy- chology, whereby behaviour is understood by the attribution of attitudes such as beliefs, desires, intentions, and so on. Human behaviour can be thought of as arising through the interaction of such attitudes. Practical reasoning architectures are modelled on theories of such interactions. Probably the best-known and most influential type of practical reason- ing architecture is the so-called belief-desire-intention (BDI) model [14, 57]. As the name indicates,BDIagents are characterised by a “mental state” with three components: beliefs, desires, and intentions. Intuitively, beliefs correspond to information that the agent has about its environment. Desires represent “options” available to the agent — different pos- sible states of affairs that the agent may choose to commit to. Intentions represent states of affairs that the agent has chosen and has committed resources to. An agent’s practical reasoning involves repeatedly updating beliefs from information in the environment, decid- ing what options are available, “filtering” these options to determine new intentions, and acting on the basis of these intentions. The philosophical foundations of theBDI model are to be found in Bratman’s account of the role that intentions play in human practical reasoning [12]. A number ofBDIagent systems have been implemented, the best-known of which is probably the Procedural Reasoning System (PRS) [57]. Researchers interested in practical reasoning architectures have developed a number of logical theories of BDI
systems [120, 121]. Closely related to this work on practical reasoning agent architectures is Shoham’s proposal for agent-oriented programming, a multi-agent programming model in which agents are explicitly programmed in terms of mentalistic notions such as belief and desire [133].
2.1.2. Object and Concurrent Object Systems. Object-oriented programmers often fail to see anything novel or new in the idea of agents. When one stops to consider the relative properties of agents and objects, this is perhaps not surprising. Objects are defined as computational entities that encapsulate some state, are able to perform actions, or methods on this state, and communicate by message passing.
While there are obvious similarities, there are also significant differences between agents and objects. The first is in the degree to which agents and objects are autonomous. Recall that the defining characteristic of object-oriented programming is the principle of encapsu- lation — the idea that objects can have control over their own internal state. In program- ming languages likeJAVA, we can declare instance variables (and methods) to beprivate, meaning they are only accessible from within the object. (We can of course also declare thempublic, meaning that they can be accessed from anywhere, and indeed we must do this for methods so that they can be used by other objects. But the use ofpublicinstance variables is generally considered poor programming style.) In this way, an object can be thought of as exhibiting autonomy over its state: it has control over it. But an object does not exhibit control over it’s behaviour. That is, if a methodmis made available for other objects to invoke, then they can do so whenever they wish; the object has no control over whether or not that method is executed. Of course, an object must make methods available to other objects, or else we would be unable to build a system out of them. This is not normally an issue, because if we build a system, then we design the objects that go in it, and they can thus be assumed to share a “common goal”. But in many types of multi-agent system, (in particular, those that contain agents built by different organisations or individ- uals), no such common goal can be assumed. It cannot be taken for granted that an agent i will execute an action (method) a just because another agent j wants it to — a may not be in the best interests of i. We thus do not think of agents as invoking methods upon one-another, but rather as requesting actions to be performed. If j requests i to perform a, then i may perform the action or it may not. The locus of control with respect to the decision about whether to execute an action is thus different in agent and object systems.
In the object-oriented case, the decision lies with the object that invokes the method. In the agent case, the decision lies with the agent that receives the request. The distinction between objects and agents can be summarised in the following slogan: Objects do it for free; agents do it for money.
Note that there is nothing to stop us implementing agents using object-oriented tech- niques. For example, we can build some kind of decision making about whether to execute a method into the method itself, and in this way achieve a stronger kind of autonomy for our objects. However, the point is that autonomy of this kind is not a component of the basic object-oriented model.
The second important distinction between object and agent systems is with respect to the notion of flexible (reactive, pro-active, social) autonomous behaviour. The standard object model has nothing whatsoever to say about how to build systems that integrate these types of behaviour. Again, one could argue that we can build object-oriented programs that do integrate these types of behaviour. But this argument misses the point, which is that the standard object-oriented programming model has nothing to do with these types of behaviour.
The third important distinction between the standard object model and our view of agent systems is that agents are each considered to have their own thread of control — in the standard object model, there is a single thread of control in the system. Of course, a lot of work has recently been devoted to concurrency in object-oriented programming. For example, theJAVAlanguage provides built-in constructs for multi-threaded programming.
There are also many programming languages available (most of them admittedly proto- types) that were specifically designed to allow concurrent object-based programming [4].
But such languages do not capture the idea we have of agents as autonomous entities.
Note, however, that active objects come quite close to our concept of autonomous agents
— though not agents capable of flexible autonomous behaviour [10, p91].
2.1.3. Human-Computer Interfaces Currently, when we interact with a computer via a user interface, we are making use of an interaction paradigm known as direct manipulation.
Put simply, this means that a computer program (a word processor, for example) will only do something if we explicitly tell it to. This makes for very one-way interaction. It would be desirable, therefore, to have computer programs that in certain circumstances could take the initiative, rather than wait for the user to spell out exactly what they wanted to do. This leads to the view of computer programs as cooperating with a user to achieve a task, rather than acting simply as servants. A program capable of taking the initiative in this way would in effect be operating as a semi-autonomous agent. Such agents are sometimes referred to as expert assistants, or more whimsically as digital butlers.
One of the key figures in the development of agent-based interfaces has been Nicholas Negroponte. His vision of agents at the interface was set out in Being Digital [106]:
“The ‘agent’ answers the phone, recognizes the callers, disturbs you when appro- priate, and may even tell a white lie on your behalf. The same agent is well trained in timing, versed in finding opportune moments, and respectful of idiosyncrasies.
” (p150)
“If you have somebody who knows you well and shares much of your information, that person can act on your behalf very effectively. If your secretary falls ill, it would make no difference if the temping agency could send you Albert Einstein.
This issue is not aboutIQ. It is shared knowledge and the practice of using it in your best interests.” (p151)
“Like an army commander sending a scout ahead . . . you will dispatch agents to collect information on your behalf. Agents will dispatch agents. The process multiplies. But [this process] started at the interface where you delegated your desires.” (p158)
The main application of such agents to date has been in the area of information manage- ment systems, particularly email managers and active new readers [97] and active world- wide web browsers [94]. In section 4.1.2, we discuss such applications in more detail.
2.2. Issues and Future Directions
The area of agent architectures, particularly layered, or hybrid architectures, and practical reasoning architectures, continues to be an area of considerable research effort within the agent field. For example, there is ongoing work to investigate the appropriateness of vari- ous architectures for different environment types. It turns out to be quite hard to evaluate one agent architecture against another, although some suggestions have been made as to how this might be done in a neutral way [118].
Finally, if agent technology, of the kind described in this section, is to move from the research lab to the office of the everyday computer worker, then serious attention must be given to development environments and programming languages for such systems. To date, most architectures have been implemented in a rather ad hoc manner. Programming languages and tools for agents would present the developer with a layer of abstraction over such architectures. Shoham’sAGENT0 is one attempt to build such a language [133], as is theCONGOLOGlanguage described in [89], and the Concurrent METATEM programming language [47].APRILis another such language, which provides the developer with a set of software tools for implementingMAS[99].
3. Multi-Agent Systems
Traditionally, research into systems composed of multiple agents was carried out under the banner of Distributed Artificial Intelligence (DAI), and has historically been divided into two main camps [9]: Distributed Problem Solving (DPS) and Multi-Agent Systems (MAS).
More recently, the term “multi-agent systems” has come to have a more general meaning, and is now used to refer to all types of systems composed of multiple (semi-)autonomous components.
Distributed problem solving (DPS) considers how a particular problem can be solved by a number of modules (nodes), which cooperate in dividing and sharing knowledge about the problem and its evolving solutions. In a pureDPSsystem, all interaction strategies are in- corporated as an integral part of the system. In contrast, research inMASis concerned with the behavior of a collection of possibly pre-existing autonomous agents aiming at solving a given problem. AMAScan be defined as a loosely coupled network of problem solvers that work together to solve problems that are beyond the individual capabilities or knowledge of each problem solver [39]. These problem solvers — agents — are autonomous and may be heterogeneous in nature. The characteristics ofMASare:
# each agent has incomplete information, or capabilities for solving the problem, thus each agent has a limited viewpoint;
# there is no global system control;
# data is decentralized; and
# computation is asynchronous.
Some reasons for the increasing interest inMASresearch include: the ability to provide ro- bustness and efficiency; the ability to allow inter-operation of existing legacy systems; and
the ability to solve problems in which data, expertise, or control is distributed. Although
MASprovide many potential advantages, they also face many difficult challenges. Below, we present problems inherent in the design and implementation ofMAS(this list includes both problems first posed in [9] and some we have added):
1. How to formulate, describe, decompose, and allocate problems and synthesize results among a group of intelligent agents?
2. How to enable agents to communicate and interact? What communication languages and protocols to use? What and when to communicate?
3. How to ensure that agents act coherently in making decisions or taking action, accom- modating the nonlocal effects of local decisions and avoiding harmful interactions?
4. How to enable individual agents to represent and reason about the actions, plans, and knowledge of other agents in order to coordinate with them? How to reason about the state of their coordinated process (e.g., initiation and completion)?
5. How to recognize and reconcile disparate viewpoints and conflicting intentions among a collection of agents trying to coordinate their actions?
6. How to effectively balance local computation and communication? More generally, how to manage allocation of limited resources?
7. How to avoid or mitigate harmful overall system behavior, such as chaotic or oscilla- tory behavior?
8. How to engineer and constrain practical MAS systems? How to design technology platforms and development methodologies forMAS?
Solutions to these problems are of course intertwined [54]. For example, different mod- eling schemes for an individual agent may constrain the range of effective coordination regimes; different procedures for communication and interaction have implications for be- havioral coherence; different problem and task decompositions may yield different inter- actions.
From this backdrop, we provide some historical context for the field (section 3.1), discuss contemporary work in distributed problem solving (section 3.2) and multi-agent systems (section 3.3), and finally, we discuss some open issues (section 3.4).
3.1. History
In 1980 a group of AI researchers held the firstDAIworkshop atMITto discuss issues con- cerning intelligent problem solving with systems consisting of multiple problem solvers. It was decided that Distributed AI was not concerned with low level parallelism issues, such as how to distribute processing over different machines, or how to parallelize centralized algorithms, but rather with issues of how intelligent problem solvers could coordinate ef- fectively to solve problems. From these beginnings, theDAIfield has grown into a major international research area.
3.1.1. Actors One of the first models of multi agent problem solving was the actors model [2, 3]. Actors were proposed as universal primitives of concurrent computation.
Actors are self-contained, interactive autonomous components of a computing system that communicate by asynchronous message passing. The basic actor primitives are:
# create: creating an actor from a behavior description and a set of parameters, possibly including existing actors;
# send: sending a message to an actor;
# become: changing an actor’s local state.
Actor models are a natural basis for many kinds of concurrent computation. However, as noted in [9] actor models, along with otherDAImodels, face the issue of coherence. The low-level granularity of actors also poses issues relating to the composition of actor behav- iors in larger communities, and achievement of higher level performance goals with only local knowledge. These issues were addressed in [68] where an overview of Open Systems Science and its challenges were presented, and where an organizational architecture called
ORGwas proposed that included new features and extensions of the Actor model to support organizing large scale work.
3.1.2. Task Allocation through the Contract Net Protocol The issue of flexible alloca- tion of tasks to multiple problem solvers (nodes) received attention early on in the history ofDAI [33]. Davis and Smith’s work resulted in the well-known Contract Net Protocol.
In this protocol, agents can dynamically take two roles: manager or contractor. Given a task to perform, an agent first determines whether it can break it into subtasks that could be performed concurrently. It employs the Contract Net Protocol to announce the tasks that could be transferred, and requests bids from nodes that could perform any of these tasks.
A node that receives a task announcement replies with a bid for that task, indicating how well it thinks it can perform the task. The contractor collects the bids and awards the task to the best bidder. Although the Contract Net was considered by Smith and Davis (as well as many subsequentDAI researchers) to be a negotiation technique, it is really a coordi- nation method for task allocation. The protocol enables dynamic task allocation, allows agents to bid for multiple tasks at a time, and provides natural load balancing (busy agents need not bid). Its limitations are that it does not detect or resolve conflicts, the manager does not inform nodes whose bids have been refused, agents cannot refuse bids, there is no pre-emption in task execution (time critical tasks may not be attended to), and it is com- munication intensive. To rectify some of its shortcoming, a number of extensions to the basic protocol have been proposed, for example [128].
3.1.3. Some Early Applications
Air Traffic Control: Cammarata [21] studied cooperation strategies for resolving con- flicts among plans of a group of agents. They applied these strategies to an air-traffic control domain, in which the aim is to enable each agent (aircraft) to construct a flight
plan that will maintain a safe distance with each aircraft in its vicinity and satisfy ad- ditional constraints (such as reaching its destination with minimal fuel consumption).
Agents involved in a potentially conflicting situation (e.g., aircraft becoming too close according to their current flight path) choose one of the agents involved in the conflict to resolve it. The chosen agent acts as a centralized planner to develop a multi-agent plan that specifies the conflict-free flight paths that the agents will follow. The de- cision of which agent will do the planning is based on different criteria, for example, most-informed agent, or more-constrained agent. The authors carried out experimental evaluations to compare plans made by agents that were chosen using different criteria.
The Distributed Vehicle Monitoring Task (DVMT): In this domain, a set of agents are distributed geographically, and each is capable of sensing some portion of an overall area to be monitored. As vehicles move through its sensed area, each agent detects characteristic sounds from those vehicles at discrete time intervals. By analyzing the combination of sounds heard from a particular location at a specific time, an agent can develop interpretations of what vehicles might have created these sounds. By analyz- ing temporal sequences of vehicle interpretations, and using knowledge about mobility constraints of different vehicles, the agent can generate tentative maps of vehicle move- ments in its area. By communicating tentative maps to one another, agents can obtain increased reliability and avoid redundant tracking in overlapping regions [38].
Blackboards: TheDVMT, along with other early MAS applications use the blackboard systems for coordination. Put crudely, a blackboard is simply a shared data struc- ture [40]. Agents can use a blackboard to communicate by simply writing on the data structure. EarlyDVMT work by Lesser and Corkill [30] used two blackboards, one for data and the other for agents’ goals. In theMINDSproject, Huhns et al also used two specialized blackboards [73]. TheMINDSproject was a distributed information re- trieval system, in which agents shared both knowledge and tasks in order to cooperate in retrieving documents for users. Hayes-Roth proposed a more elaborate blackboard structure, with three interacting sub-agents for perception, control and reasoning [64].
3.2. Cooperative Multi-Agent Interactions
As interest increases in applications that use cooperative agents working towards a com- mon goal, and as more agents are built that cooperate as teams, (such as in virtual train- ing [143], Internet-based information integration [35], ROBOCUP robotic and synthetic soccer [149], and interactive entertainment [66]), so it becomes more important to under- stand the principles that underpin cooperation.
As discussed in section 2.1, planning for a single agent is a process of constructing a sequence of actions considering only goals, capabilities and environmental constraints.
Planning in aMAS environment, on the other hand, considers in addition the constraints that the other agents’ activities place on an agent’s choice of actions, the constraints that an agent’s commitments to others place on its own choice of actions and the unpredictable evolution of the world caused by other, un-modeled agents.
Most early work inDAIdealt with groups of agents pursuing common goals (e.g., [90, 38, 21, 91]). Agent interactions were guided by cooperation strategies meant to improve
their collective performance. In this light, early work on distributed planning took the ap- proach of complete planning before action. To produce a coherent plan, the agents must be able to recognize subgoal interactions and either avoid them or else resolve them. For instance, work by Georgeff [55] included a synchroniser agent to recognize and resolve such interactions. Other agents send this synchroniser their plan; the synchroniser exam- ines plans for critical regions in which, for example, contention for resources could cause them to fail. The synchroniser then inserted synchronization messages (akin to operating systems semaphores) to ensure mutual exclusion. In the work by Cammarata on air traffic control (see section 3.1.3) the synchronizing agent was dynamically assigned according to different criteria, and could alter its plan to remove the interaction (avoid collision).
Another significant approach to resolving sub-problem interdependencies is the “Func- tionally Accurate Model (FA/C)” [91]. In the FA/C model, agents do not need to have all the necessary information locally to solve their sub-problems, but instead interact through the asynchronous, coroutine exchange of partial results. Starting with the FA/C model, a series of sophisticated distributed control schemes for agent coordination were developed, such as use of static meta-level information specified by an organizational structure, and the use of dynamic meta-level information developed in Partial Global Planning (PGP) [38].
Partial Global Planning is a flexible approach to coordination that does not assume any particular distribution of sub-problems, expertise or other resources, but instead allows nodes to coordinate themselves dynamically [38]. Agent interactions take the form of communicating plans and goals at an appropriate level of abstraction. These communica- tions enable a receiving agent to form expectations about the future behavior of a sending agent, thus improving agent predictability and network coherence [38]. Since agents are cooperative, the recipient agent uses the information in the plan to adjust its own local plan- ning appropriately, so that the common planning goals (and planning effectiveness criteria) are met. Besides their commonPGP’s, agents also have some common knowledge about how and when to usePGPs. Decker [34] addressed some of the limitations of thePGPby creating a genericPGP-based framework calledTAEMSto handle issues of real-time (e.g., scheduling to deadlines) and meta-control (e.g., to obviate the need to do detailed planning at all possible node interactions).
Another research direction in cooperative multi-agent planning has been directed towards modeling teamwork explicitly. This is particularly helpful in dynamic environments, where team members may fail or where they may be presented with new opportunities. In such situations, it is necessary that teams monitor their performance and reorganize based on their current situation.
The joint intentions framework [93] is a natural extension to the practical reasoning agents paradigm discussed in section 2.1.1. It focuses on characterising a team’s men- tal state, called a joint intention (see e.g., [77] for survey). A team jointly intends a team action if the team members are jointly committed to completing the team action, while mutually believing they were doing it. A joint commitment is defined as a joint persistent goal. To enter into a joint commitment, all team members must establish appropriate mu- tual beliefs and commitments. This is done through an exchange of request and confirm speech acts [28]. The commitment protocol synchronizes the team, in that all members simultaneously enter into a joint commitment towards a team task. In addition, all team members must consent, via confirmation, to the establishment of a joint commitment goal
— thus a joint commitment goal is not established if a team member refuses. In this case, negotiation could be used, though how this might be done remains an open issue.
The SharedPlan model [60, 61] is based on a different mental attitude: intending that an action be done [13]. “Intending that” concerns a group’s joint activity or a collaborator’s actions. The concept is defined via a set of axioms that guide a team mate to take action, or enter into communication that enables or facilitates its team mates to perform assigned tasks.COLLAGEN[122] is a prototype toolkit that has its origins in the SharedPlan model, and which has been applied to building a collaborative interface agent that helps with air travel arrangements. Jennings [79] presented a framework called joint responsibility based on a joint commitment to a team’s joint goal and a joint recipe commitment to a common recipe. This model was implemented in theGRATE* system [78], and applied to the domain of electricity transport management.
Tambe [144] presents a model of teamwork calledSTEAM(Shell for TEAMwork), based on enhancements to the Soar architecture [109], plus a set of about 300 domain independent Soar rules. Based on the teamwork operationalized in STEAM, three teams have been implemented, two that operate in a commercially available simulation for military training and a third in ROBOCUPsynthetic soccer. STEAMuses a hybrid approach that combines joint intentions with partial SharedPlans.
3.3. Self-Interested Multi Agent Interactions
The notion of interactions among self-interested agents has been centered around negotia- tion. Negotiation is seen as a method for coordination and conflict resolution (e.g., resolv- ing goal disparities in planning, resolving constraints in resource allocation, resolving task inconsistencies in determining organizational structure). Negotiation has also been used as a metaphor for communication of plan changes, task allocation, or centralized resolution of constraint violations. Hence, negotiation is almost as ill-defined as the notion of “agent”.
We give here what we consider to be the main characteristics of negotiation, that are necessary for developing applications in the real world. These are: (a) the presence of some form of conflict that must be resolved in a decentralized manner, by (b) self- interested agents, under conditions of (c) bounded rationality, and (d) incomplete infor- mation. Furthermore, the agents communicate and iteratively exchange proposals and counter-proposals.
ThePERSUADERsystem by Sycara [141, 140] and work by Rosenschein [123, 124] rep- resent the first work byDAIresearchers on negotiation among self-interested agents. The two approaches differ in their assumptions, motivations, and operationalization. The work of Rosenschein was based on game theory. Utility is the single issue that agents consider, and agents are assumed to be omniscient. Utility values for alternative outcomes are rep- resented in a payoff matrix that is common knowledge to both parties in the negotiation.
Each party reasons about and chooses the alternative that will maximize its utility. Despite the mathematical elegance of game theory, game theoretic models suffer from restrictive assumptions that limit their applicability to realistic problems1. Real world negotiations are conducted under uncertainty, involve multiple criteria rather than a single utility di- mension, the utilities of the agents are not common knowledge but are instead private, and the agents are not omniscient.
ThePERSUADERis an implemented system that operates in the domain of labor negotia- tion [139]. It involves three agents (a union, a company, and a mediator), and is inspired by human negotiation. It models the iterative exchange of proposals and counter-proposals in order for the parties to reach agreement. The negotiation involves multiple issues, such as wages, pensions, seniority, subcontracting, and so on. Each agent’s multi-dimensional util- ity model is private (rather than common) knowledge. Belief revision to change the agents’
utilities so that agreement can be reached is achieved via persuasive argumentation [141].
In addition, case-based learning techniques are also incorporated into the model.
Work by Kraus [86], focuses on the role of time in negotiation. Using a distributed mechanism, agents negotiate and can reach efficient agreements without delays. It is also shown that the individual approach of each agent towards the negotiation time affects (and may even determine) the final agreement that is reached.
As electronic commerce is rapidly becoming a reality, the need for negotiation tech- niques that take into consideration the complexities of the real world, such as incomplete information, multiple negotiation issues, negotiation deadlines, and the ability to break contracts will be critically needed. Work in non-binding contracts includes [127] where de- commitment penalties were introduced into the Contract Net Protocol, and theADEPTsys- tem, in which a penalty for contract violation was built into the negotiation agreement [82].
Another important aspect of successful interaction for self-interested agents is the ability to adapt behaviour to changing circumstances (see [138] for a survey). However, learn- ing in a multi-agent environment is complicated by the fact that as other agents learn, the environment effectively changes. Moreover, other agents’ actions are often not directly observable, and the action taken by the learning agent can strongly bias the range of be- haviors that are encountered. Hu and Wellman [69] characterize an agent’s belief process in terms of conjectures about the effect of their actions. A conjectural equilibrium is then defined, in which all agents’ expectations are realized, and each agent responds optimally to its expectations. They present a multi-agent system where an agent builds a model of the response of others. Their experimental results show that depending on the starting point, the agent may be better or worse off than had it not attempted to learn a model of the other agents.
In [159] the Bazaar negotiation model was presented, which included multi-agent learn- ing through agent interactions. The benefits of learning, if any, on the individual utilities of agents, as well as the overall (joint) system utility were examined. The experimental results suggest that: (a) when all agents learn, the joint system utility is near optimal and agents’ individual utilities are very similar; (b) when no agent learns the agents’ individual utilities are almost equal but the joint utility is very low (much lower than in the “all agents learn” condition); and (c) when only one agent learns, its individual utility increases at the expense of both the individual utility of the other agents as well as the overall joint utility of the system (i.e., only one agent learning has a harmful overall effect) [159, 160].
3.4. Issues and Future Directions
One of the most important driving forces behindMAS research and development is the Internet: agents are populating the Internet at an increasingly rapid pace. These agents invariably need to interact with one-another in order to meet their designer’s objectives.
In such open environments, agents that would like to coordinate with each other (either cooperate or negotiate, for example) face two major challenges: first, they must be able to find each other (in an open environment, agents might appear and disappear unpredictably), and once they have done that, they must be able to inter-operate.
To address the issue of finding agents in an open environment like the Internet, middle agents [88] have been proposed. Each agent advertises it capability to some middle agent.
A number of different agent types have been identified, including matchmakers or yellow page agents (that match advertisements to requests for advertised capabilities), blackboard agents (that collect requests), and brokers (that process both). In preliminary experiments [36], it was seen that the behaviors of each type of middle-agent have certain performance characteristics. For example, while brokered systems are more vulnerable to certain fail- ures, they are also able to cope more quickly with a rapidly fluctuating agent work-force.
Middle agents are advantageous since they allow a system to operate robustly in the face of agent appearance and disappearance, and intermittent communications.
To allow agents to inter-operate, a number of agent communication languages have been designed [98, 135, 49]. These provide a set of performatives based on speech acts [132].
Though such performatives can characterize message types, efficient languages to express message content that allows agents to “understand” each other have not been effectively demonstrated. Thus the ontology problem — that of how can agents share meaning — is still open [62].
Another critical issue is effective allocation of limited resources to multiple agents. For example, we have all experienced large time lags in response to Internet queries because of network congestion. Economics-based mechanisms have been utilized inMASto address problems of resource allocation (the central theme of economic research) [102, 128, 71].
Economics-based approaches, and market mechanisms in particular, are becoming increas- ingly attractive toMASresearchers both because of the ready availability of underlying for- mal models, but also because of their potential applicability in Internet-based commerce.
In such approaches, agents are assumed to be self-interested utility maximizers. The areas where economics-based approaches have been applied toMAS research to date are: (a) resource allocation; (b) task allocation; and (c) negotiation. In markets, agents that control scarce resources (labor, raw materials, goods, money) agree to share by exchanging some of their respective resources to achieve some common goal. Resources are exchanged with or without explicit prices. Markets assume that exchange prices are publicly known. In auctions, there is a central auctioneer through which coordination happens. Hence the agents need only exchange minimal amounts of information.
Self interested agents, by definition, simply choose a course of action which maximizes their own utility. In a society of self-interested agents, it is desired that if each agent maxi- mizes it local utility, then the whole society exhibits desirable behavior — in other words, locally good behavior implies globally good behavior. The goal is to design mechanisms for self-interested agents such that if agents follow these mechanisms, the overall system behavior will be acceptable. This is called mechanism design [7]. There are, however, many problems facing such a society of self-interested agents. First, agents might overuse and hence congest a shared resource, such as a communications network. This problem is called the tragedy of the commons [63]. The problem of the tragedy of commons is usually solved by pricing or taxing schemes. Second, a society of self-interested computa-
tional agents can exhibit oscillatory or chaotic behavior [72, 145]. Complex behavior can be exhibited by very simple computational ecosystems. Experimental results indicate that imperfect knowledge suppresses oscillatory behavior at the expense of reducing perfor- mance. In addition, enhancing the decision-making abilities of some of the individuals in the system can either improve or severely degrade overall system performance. Moreover, systems can remain in non-optimal meta-stable states for long periods before reaching a globally optimal state. In [145] a similar problem is considered. Two approaches are eval- uated, corresponding to heterogeneous preferences and heterogeneous transaction costs.
Empirically, the transaction cost case is shown to provide stability with near optimal pay- offs under certain conditions. The final problem with self-interested systems is that agents might be untruthful or deceitful in order to increase their individual utility. This may have harmful effect on the whole society. Mechanism design techniques have been reported that make it beneficial for agents to report the truth [105].
4. Applications
Agent technology is rapidly breaking out of universities and research labs, and is begin- ning to be used to solve real-world problems in a range of industrial and commercial ap- plications. Fielded applications exist today, and new systems are being developed at an increasingly rapid rate. Against this background, the purpose of this section is twofold.
First, it aims to identify the main areas where agent-based approaches are currently being used and to provide pointers to some exemplar systems within these areas (section 4.1).
Secondly, it aims to anticipate likely future directions of applied agent work and to high- light open issues which need to be addressed if this technology is to fulfill its full potential (section 4.2).
4.1. Key Domains and Exemplar Systems
To date, the main areas in which agent-based applications have been reported are as fol- lows: manufacturing, process control, telecommunication systems, air traffic control, traf- fic and transportation management, information filtering and gathering, electronic com- merce, business process management, entertainment and medical care. Whilst a compre- hensive review of all the systems in all of these areas is beyond the scope of this paper (see [22, 83, 114]), we attempt to outline some of the key systems in these areas.
4.1.1. Industrial Applications Industrial applications of agent technology were among the first to be developed, and today, agents are being applied in a wide range of industrial systems:
Manufacturing: Parunak [148] describes theYAMSsystem (Yet Another Manufacturing System), which applies the Contract Net Protocol (see above) to manufacturing control.
The basic problem can be described as follows. A manufacturing enterprise is mod- elled as a hierarchy of workcells. There will, for example, be workcells for milling, lathing, grinding, painting, and so on. These workcells are further grouped into flexible
manufacturing systems (FMS), each of which provides a functionality such as assem- bly, paint spraying, buffering of products, and so on. A collection of suchFMSs is grouped into a factory. A single company or organisation may have many different factories, though these factories may duplicate functionality and capabilities. The goal ofYAMS is to efficiently manage the production process at these plants. This pro- cess is defined by some constantly changing parameters, such as the products to be manufactured, available resources, time constraints, and so on. In order to achieve this enormously complex task,YAMSadopts a multi-agent approach, where each fac- tory and factory component is represented as an agent. Each agent has a collection of plans, representing its capabilities. The contract net protocol allows tasks (i.e., pro- duction orders) to be delegated to individual factories, and from individual factories down toFMSs, and then to individual work cells. Other systems in this area include those for: configuration design of manufacturing products [32], collaborative design [31, 115], scheduling and controlling manufacturing operations [50, 112, 116, 136], controlling a manufacturing robot [113], and determining production sequences for a factory [26, 157].
Process Control: Process control is a natural application for agents, since process con- trollers are themselves autonomous reactive systems. It is not surprising, therefore, that a number of agent-based process control applications should have been developed.
The best known of these isARCHON, a software platform for building multi-agent sys- tems, and an associated methodology for building applications with this platform [81].
ARCHONhas been applied in several process control applications, including electric- ity transportation management (the application is in use in northern Spain [29]), and particle accelerator control [117]. ARCHON also has the distinction of being one of the world’s earliest field-tested multi-agent systems. Other agent-based process con- trol systems have been written for monitoring and diagnosing faults in nuclear power plants [150], spacecraft control [131, 76], climate control [27] and steel coil processing control [101].
Telecommunications: Telecommunication systems are large, distributed networks of in- terconnected components which need to be monitored and managed in real-time. In what is a fiercely competitive market, telecommunication companies and service providers aim to distinguish themselves from their competitors by providing better, quicker or more reliable services. To achieve this differentiation, they are increasingly turning to state-of-the-art software techniques including agent-based approaches. In one such application, [59], negotiating agents are used to tackle the feature interaction prob- lem. Features in a telecommunication system provide added functionality on top of the basic communication (e.g., call forwarding and caller-id). As new features are being added to the phone network at an ever increasing rate, it is becoming correspond- ingly more difficult to determine which features interact with, and are inconsistent with, which other features. Therefore, the traditional approach of analysing services at design time and hard-wiring in solutions for all possible interaction permutations is doomed to failure. Given this situation, Griffeth and Velthuijsen [59] decided to adopt a different strategy and tackle the problem on an as-needed basis at run-time. They did this by employing negotiating agents to represent the different entities who are in-
terested in the set up of a call. When conflicts are detected, the agents negotiate with one another to resolve them so that an acceptable call configuration is established.
Other problems for which agent-based systems have been constructed include: net- work control [129, 152], transmission and switching [110], service management [19]
and network management [1, 41, 53, 119]. See [153] for a comprehensive review of this area.
Air Traffic Control: Ljunberg and Lucas [95] describe a sophisticated agent-realised air traffic control system known asOASIS. In this system, which is undergoing field trials at Sydney airport in Australia, agents are used to represent both aircraft and the various air-traffic control systems in operation. The agent metaphor thus provides a useful and natural way of modelling real-world autonomous components. As an aircraft enters Sydney airspace, an agent is allocated for it, and the agent is instantiated with the information and goals corresponding to the real-world aircraft. For example, an aircraft might have a goal to land on a certain runway at a certain time. Air traffic control agents are responsible for managing the system.OASISis implemented using a belief-desire- intention system calledDMARS[56].
Transportation Systems: The domain of traffic and transportation management is well suited to an agent-based approach because of its geographically distributed nature. For example, [18] describe a multi-agent system for implementing a future car pooling application. Here there are two types of agent: one representing the customers who require or who can offer transportation, and one representing the stations where cus- tomers congregate in order to be picked up. Customer agents inform relevant stations of their requirements (when and where they want to go) and the station agent deter- mines whether their requests can be accommodated and, if so, which car they should be booked into. Other applications in this area are described in [46].
4.1.2. Commercial Applications While industrial applications tend to be highly-complex, bespoke systems which operate in comparatively small niche areas, commercial applica- tions, especially those concerned with information management, tend to be oriented much more towards the mass market.
Information Management: As the richness and diversity of information available to us in our everyday lives has grown, so the need to manage this information has grown.
The lack of effective information management tools has given rise to what is collo- quially known as the information overload problem. Put simply, the sheer volume of information available to us via the Internet and World-Wide Web (WWW) represents a very real problem. The potential of this resource is enormous, but the reality is often disappointing. There are many reasons for this. Both human factors (such as users getting bored or distracted) and organisational factors (such as poorly organised pages with no semantic mark-up) conspire against users attempting to use the resource in a systematic way. We can characterise the information overload problem in two ways:
# Information filtering: Every day, we are presented with enormous amounts of information (via email and usenet news, for example), only a tiny proportion of
