Distributed Intelligent Agents Katia Sycara Keith Decker Anandeep Pannu Mike Williamson DaJun Zeng The Robotics Institute Carnegie Mellon University Pittsburgh, PA 15213, U. S. A. voice: (412) 268-8825 Fax: (412) 268-5569 URL: http://www. cs. cmu. edu/ softagents/ Abstract We are investigating techniques for developing distributed and adaptive collections of agents that coordinate to retrieve, Iter and fuse information relevant to the user, task and situation, as well as anticipate a user’s information needs. In our system of agents, information gathering is seamlessly integrated with decision support.
The task for which particular information is requested of the agents does not remain in the user’s head but it is explicitly represented and supported through agent collaboration. In this paper we present the distributed system architecture, agent collaboration interactions, and a reusable set of software components for constructing agents. We call this reusable multi-agent computational infrastructure RETSINA (Reusable Task Structure-based Intelligent Network Agents). It has three types of agents. Interface agents interact with the user receiving user speci cations and delivering results.
They acquire, model, and utilize user preferences to guide system coordination in support of the user’s tasks. Task agents help users perform tasks by formulating problem solving plans and carrying out these plans through querying and exchanging information with other software agents. Information agents provide intelligent access to a heterogeneous collection of information sources. We have implemented this system framework and are developing collaborating agents in diverse complex real world tasks, such as organizational decision making (the PLEIADES system), and nancial portfolio anagement (the WARREN system). Introduction E ective use of the Internet by humans or decision support machine systems has been hampered by some dominant characteristics of the Infosphere. First, information available from the net is unorganized, multi-modal, and distributed on server sites all over the world. Second, the number and variety of data sources and services is dramatically increasing every day. Furthermore, the availability, type and ambiguous and possibly erroneous due to the dynamic nature of the information sources and potential information updating and maintenance problems.
Therefore, information is becoming increasingly di cult for a person or machine system to collect, Iter, evaluate, and use in problem solving. As a result, the problem of locating information sources, accessing, Itering, and integrating information in support of decision making, as well as coordinating information retrieval and problem solving e orts of information sources and decision-making systems has become a very critical task. The notion of Intelligent Software Agents (e. g. , 1, 19, 20, 25, 13, 22]) has been proposed to address this challenge.
Although a precise de nition of an intelligent gent is still forthcoming, the current working notion is that Intelligent Software Agents are programs that act on behalf of their human users in order to perform laborious information gathering tasks, such as locating and accessing information from various on-line information sources, resolving inconsistencies in the retrieved information, Itering away irrelevant or unwanted information, integrating information from heterogeneous information sources and adapting over time to their human users’ information needs and the shape of the Infosphere.
Most current agent- riented approaches have focussed on what we call interface agents la single agent with simple knowledge and problem solving capabilities whose main task is information Itering to alleviate the user’s cognitive overload (e. g. , 15, 16]). Another type of agent is the Softbot ( 6]), a single agent with general knowledge that performs a wide range of user-delegated information- nding tasks. 2 We believe that such centralized approaches have several limitations. A single general agent would need an enormous amount of knowledge to be able to deal e ectively with user information requests that cover a variety of tasks.
In addition, a entralized system constitutes a processing bottleneck and a Xsingle point of failure”. Finally, because of the complexity of the information nding and Itering task, and the large amount of information, the required processing would overwhelm a single agent. Another proposed solution is to address the problem by using multi-agent systems to access, Iter, evaluate, and integrate this information 23, 17]. Such multi-agent systems can compartmentalize specialized task knowledge, organize themselves to avoid processing bottlenecks, and can be built expressly to deal with dynamic changes in the agent and information-source landscape.
In addition, multiple intelligent coordinating agents are ideally suited to the predominant characteristics of the Infosphere, such as the heterogeneity of the information sources, the diversity of information gathering and problem solving tasks that the gathered information supports, and the presence of multiple users with related information needs. We therefore believe that a distributed approach is superior, and possibly the only one that would work for information gathering and coherent information fusion. The context of multi-agent systems widens the notion of intelligent agent in at least two eneral ways.
First, an agent’s user” that imparts goals to it and delegates tasks might be not only a human but also another agent. Second, an agent must have been agents. Our notion is that such multi agent systems may comprise interface agents tied closely to an individual human’s goals, task agents involved in the processes associated with arbitrary problem-solving tasks, and information agents that are closely tied to a source or sources of data. An information agent is di erent from an interface agent in that an information agent is tied more closely to the data that it is roviding, while an interface agent closely interacts with the user.
Typically, a single information agent will serve the information needs of many other agents (humans or intelligent software agents). An information agent is also quite di erent from a typical World Wide Web (WWW) service that provides data to multiple users. Besides the obvious interface di erences, an information agent can reason about the way it will handle external requests and the order in which it will carry them out (WWW services are typically blindly concurrent).
Moreover, information agents not only perform infor3 ation gathering in response to queries but also can carry out long-term interactions that involve monitoring the Infosphere for particular conditions, as well as information updating. In this paper, we report on our work on developing distributed collections of intelligent software agents that cooperate asynchronously to perform goal-directed information retrieval and information integration in support of performing a variety of decision making tasks 23, 2]. We have been developing RETSINA, an open society of reusable agents that self organize and cooperate in response to task requirements.
In particular, we will focus on three crucial characteristics of the overall framework that di erentiate our work from others: ours is a multi-agent system where the agents operate asynchronously and collaborate with each other and their users, the agents actively seek out information, the information gathering is seamlessly integrated with problem solving and decision support We will present the overall architectural framework, our agent design commitments, and agent architecture to enable the above characteristics.
We will draw examples from our work on Intelligent Agents in the domains of organizational decision making the PLEIADES system), and nancial portfolio management (the WARREN system). The rest of the paper is organized as follows. Section 2 brie y lists some agent characteristics we consider desirable. Section 3 motivates the distributed architecture for intelligent information retrieval and problem solving, and presents an overview of the system architecture, the di erent types of agents in the proposed multi agent organization, and agent coordination mechanisms.
Section 4 presents in detail the reusable agent architecture and discusses planning, control, and execution monitoring in agent operations. Description and examples from the application of RETSINA to everyday organizational decision making and nancial portfolio management are given in Section 5. Section 6 presents concluding remarks. 4 Many di erent de nitions of intelligent agents have been proposed. In this section, we give a brief list of what we see as essential characteristics of intelligent agents. askable. By “taskable” we mean agents that can take direction from humans or other agents. network-centric: by this we mean that agents should be distributed and self organizing. When situations warrant it, agent mobility may also be desirable. emi-autonomous rather than under direct human control all the time. For example, in an information gathering task, because of the large amount of potential requests for information, humans would be swamped, if they had to initiate every single information request.
The amount of agent autonomy should be user controllable. persistent, i. e. capable of long periods of unattended operation. trustworthy: An agent should serve users’ needs in a reliable way so that users will develop trust in its performance. anticipatory: An agent should anticipate user information needs through task, role nd situational models as well as learning to serve as an intelligent cache, acquiring and holding information likely to be needed. active: An agent should initiate problem solving activities (e. g. onitor the infosphere for the occurrence of given patterns), anticipate user information needs and bring to the attention of users situationappropriate information, deciding when to fuse information or present “raw” information. collaborative with humans and with other machine agents. Collaborative agent interactions allow them to increase their local knowledge, resolve con icts and nconsistencies in information, current task and world models, thus improving their decision support capabilities. 5 able to deal with heterogeneity of other agents and information resources. daptive to changing user needs, and task environment. 3 Distributed Intelligent Agents in Information Processing and Problem Solving In this section, we motivate and describe the distributed agent framework for intelligent information retrieval and problem solving, and then present the agent coordination mechanisms. The issues of how to engineer these agents are the topics of Section 4. RETSINA has been motivated by the following considerations: Distributed information sources: Information sources available on-line are inherently distributed. Furthermore, these sources typically are of di erent modalities.
Therefore it is natural to adopt a distributed architecture consisting of many software agents specialized for di erent heterogeneous information sources. Sharability: Typically, user applications need to access several services or resources in an asynchronous manner in support of a variety of tasks. It would be wasteful to replicate agent information gathering or problem solving capabilities for each user and each application. It is desirable that the architecture support sharability of agent Complexity hiding: Often information retrieval in support of a task involves quite complex coordination of many di erent agents.
To avoid overloading the user with a confusing array of di erent agents and agent interfaces, it is necessary to develop an architecture that hides the underlying distributed information gathering and problem solving complexity from the user. Modularity and Reuseability: Although software agents will be operating on behalf of their individual patrons I human users, or other agents, pieces of agent code for a articular task can be copied from one agent 6 to another and can be customized for new users to take into consideration particular users’ preferences or idiosyncrasies.
One of the basic ideas behind the distributed agent-based approach is that software agents will be kept simple for ease of maintenance, initialization and customization. Another facet of reuseability is that pre-existing information services, whose implementation, query language and communication channels are beyond the control of user applications, could be easily incorporated in problem-solving. Flexibility: Software agents can interact in new con gurations ondemand”, depending on the information requirements of a particular decision making task.
Robustness: When information and control is distributed, the system is able to degrade gracefully even when some of the agents are out of service temporarily. This feature of the system has signi cant practical implications because of the dynamic and unstable nature of on-line information services. Quality of Information: The existence of (usually partial) overlapping of available information items from multiple information sources offers the opportunity to ensure and probably enhance) the correctness of data through cross-validation.
Software agents providing the same piece of information can interact and negotiate to nd the most accurate data. Legacy Data: Many information sources exist prior to the emergence of the Internet-based agent technology. New functionalities and access methods are necessary for them to become full- edged members of the new information era. Directly updating these systems, however, is a nontrivial task. A preferable way of updating is to construct agent wrappers around existing systems.
These agent wrappers interface to the information sources and information onsumers and provide a uniform way of accessing the data as well as o er additional functionalities such as monitoring for changes. This agent wrapper approach o ers much exibility and extensibility. Practically speaking, it is also easier to implement since the internal data structure and updating mechanism of the legacy information systems dont need to be modi ed. 7 The above considerations clearly motivate the development of systems of distributed software agents for information gathering and decision support in the Internet-based information environment.
The critical question then is how to structure and organize oftware components in such a way that building software agents for new tasks and applications and organizing them can be relatively easy. It seems di cult to engineer a general agent paradigm which can cover in an e cient manner a broad range of di erent tasks including interaction with the user, acquisition of user preferences, information retrieval, and task-speci c decision making. For example, in building an agent that is primarily concerned with interacting with a human user, we need to emphasize acquisition, modeling and utilization of user information needs and preferences.
On the other hand, in developing an agent that interacts with information sources, issues of acquiring user preferences are de-emphasized and, instead, issues of information source availability, e ciency of data access, data quality and information source reliability become critical. Therefore, reusable software components must e ciently address the critical issues associated with each of these three agent categories. 3. 1 Agent Types In the RETSINA framework, each user is associated with a set of agents which collaborate to support him/her in various tasks and act on the user’s behalf.
The agents are distributed and run across di erent machines. The agents have access to models of the user and of other agents as well as the task and information gathering needs associated with di erent steps of the task. Based on this knowledge, the agents decide how to decompose and delegate tasks, what information is needed at each decision point, and when to initiate collaborative searches with other agents to get, fuse and evaluate the information.
In this way, the information gathering activities of the agents are automatically activated by models of the task and processing needs of he agents rather than wholly initiated by the user. The user can leave some of the information gathering decisions to the discretion of the agents. This saves user time and cognitive load and increases user productivity. The degree of agent autonomy is user-controlled. As a user gains more con dence in the agents’ capabilities, more latitude over decisions is given over to them.
During search, the agents communicate with each other to request or provide 8 information, nd information sources, Iter or integrate information, and negotiate to resolve con icts in information and task models. The returned information is communicated to display agents for appropriate display to the user. RETSINA has three types of agents (see Figure 1): interface agents, task agents and information agents. Interface agents interact with the user receiving user speci cations and delivering results.
They acquire, model and utilize user preferences to guide system coordination in support of the user’s tasks. For example, an agent that Iters electronic mail according to its user’s preferences is an interface agent. The main functions of an interface agent include: (1) collecting relevant information from he user to initiate a task, (2) presenting relevant information including results and explanations, (3) asking the user for additional information during problem solving, and (4) asking for user con rmation, when necessary.
From the user’s viewpoint, underlying distributed information gathering and problem solving complexity and frees the user from having to know of, access and interact with a potentially large number of task agents and information seeking agents in support of a task. For example, the task of hosting a visitor in a university (see Section 5. 1), one of the tasks upported by our intelligent agents, involves more than 10 agents. However, the user interacts directly only with the visitor hoster interface agent.
Task agents support decision making by formulating problem solving plans and carrying out these plans through querying and exchanging information with other software agents. Task agents have knowledge of the task domain, and which other task assistants or information assistants are relevant to performing various parts of the task. In addition, task assistants have strategies for resolving con icts and fusing information retrieved by information agents. A task agent performs most of the autonomous problem solving.
It exhibits a higher level of sophistication and complexity than either an interface or an information agent. A task agent (1) receives user delegated task speci cations from an interface agent, (2) interprets the speci cations and extracts problem solving goals, (3) forms plans to satisfy these goals, (4) identi es information seeking subgoals that are present in its plans, (5) decomposes the plans and coordinates with appropriate task agents or information agents for plan execution, monitoring and results composition.
An example of a task agent from he nancial portfolio management domain 9 is one that makes recommendations to buy or sell stocks. Information agents provide intelligent access to a heterogeneous collection of information sources depicted at the bottom of Figure 1 . Information agents have models of the associated information resources, and strategies for source selection, information access, con ict resolution and information fusion. For example, an agent that monitors stock prices of the New York Stock Exchange is an information agent.
An information agent’s activities are initiated either top down, by a user or a task gent through queries, or bottom up through monitoring information sources for the occurrence of particular information patterns (e. g. , a particular stock price has exceeded a prede ned threshold). Once the monitored-for condition has been observed, the information agent sends noti cation messages to agents that have registered interest in the occurrence of particular information patterns (See Section 5. 2).
For example, in the nancial domain, a human or machine agent may be interested in being noti ed every time a given stock price has risen by 10%. Thus, information agents are active, in the sense that they actively monitor information ources and proactively deliver the information, rather than Just waiting for and servicing one-shot information queries. An information agent may receive in messages from other agents three important types of goals: (1) Answering a one-shot query about associated information sources, (2) Answering periodic queries that will be run repeatedly, and the results sent to the requester each time (e. . , ell me the price of IBM every 30 minutes”), and (3) Monitoring an information source for a change in a piece of information (e. g. , ell me if the price of IBM drops below $80 within 15 minutes of the occurrence of that gents can retain useful information from their interactions as training examples and utilize various machine learning techniques to adapt to new situations and improve their performance 18, 26, 16]. . 2 Agent Organization and Coordination In RETSINA, agents are distributed across di erent machines and are directly activated based on the top-down elaboration of the current situation (as opposed to indirect activation via manager or matchmaker agents 12], 10 USER 1 Goals and Task Specifications USER 2 USER h Results Interface Agent 1 Interface Agent 2 Task Proposed Solution TaskAgent 1 Interface Agent k
Conflict TaskAgent J Resolution Information Request Information Integration Reply Collaborative InfoAgent 2 InfoAgent m Query Processing query answer Info Source 1 Info Source 2 Info Source 3 Figure 1: The RETSINA Distributed Agent Organization 11 Info Source n or self-directed activation)l . These agent activations dynamically form an organizational structure on-demand” that ts in with the task, the user’s information needs and resulting decomposed information requests from related software agents.
This task-based organization may change over time, but will also remain relatively static for extended periods. Notice that the agent organization will not change as a result of appearance or disappearance of information sources but the agent interactions could be a ected by appearance (or disappearance) of agents that are capable of ful Iling task subgoals in new ways. Information that is important for decision-making (and thus might cause an eventual change in organizational structuring) is monitored at the lowest levels of the organization and passed upward when necessary.
In this type of organization, task-speci c agents continually interleave planning, scheduling, coordination, and the execution of domain-level problem-solving actions. This system organization has the following characteristics: There is a nite number of task agents that each agent communicates with. The task agents are eventually responsible for resolving information con icts and integrating information from heterogeneous information sources for their respective tasks. The task agents are responsible for activating relevant information agents and coordinating the information nding and Itering activity for their task.
In our organization, the majority of interactions of interface agents are with the information sources, whereas task agents spend most of their processing interacting ith other task agents and information agents. We brie y describe the distributed coordination processes. When a task-speci c agent receives a task from an interface agent or from another task-speci c agent, it decomposes the task based on the domain knowledge it has and then delegates the subtasks to other task-speci c agents or directly to informationspeci c agents.
The task-speci c agent will take responsibility for collecting data, resolving con icts, coordinating among the related agents and reporting 1 Matchmaking is, however used for locating agents. 12 to whoever initiated the task. The agents who are responsible for assigned sub-tasks will either decompose these sub-tasks further, or perform data retrieval (or possibly other domain-speci c local problem solving activities). When information sources are partially replicated with varying degrees of reliability, cost and processing time, information agents must optimize information source selection.
If the chosen information sources fail to provide a useful answer, the information agent should seek and try other sources to re-do the data query. Because of these complexities, we view information retrieval as a planning task itself 11]. The plans that task-speci c gents have (see 4) include information gathering goals, which, in turn are satis ed through relevant plans for information retrieval. This type of intelligent agent di ers from traditional A1 systems since information-seeking during problem solving is an inherent part of the system.
In e ect, the planning and execution stages are interleaved since the retrieved information may change the planner’s view of the outside world or alter the planner’s inner belief system. Information is Itered and fused incrementally by information or task agents as the goals and plans of the various tasks and subtasks dictate, before it is passed on to ther agents. This incremental information fusion and con ict resolution increases e ciency and potential scalability (e. g. inconsistencies detected at the information- assistant level may be resolved at that level and not propagated to the task agent level) and robustness (e. g. , whatever inconsistencies were not detected during information assistant interaction can be detected at the task-assistant level). A task agent can be said to be proactive in the sense that it actively generates information seeking goals and in turn activates other relevant agents. Obviously, one of the major issues involved in multi-agent systems is the problem of interoperability and communication between the agents.
In our framework, we use the KQML language 7] for inter-agent communication. In order to incorporate and utilize pre-existing software agents or information services that have been developed by others, we adopt the following strategy: If the agent is under our control, it will be built using KQML as a communication language. If not, we build a gateway agent that connects the legacy system to our agent organization and handles di erent communication channels, di erent data and query formats, etc.