INET Conferences


Conferences


INET


NDSS

Other Conferences


[INET'98] [ Up ][Prev][Next]

ARCADIA: An Architecture for Cooperating Information Access Agents

Henri BROUCHOUD <henri.brouchoud@cnet.francetelecom.fr>
Alain LEGER <alain.leger@cnet.francetelecom.fr>
Eric MALVILLE <eric.malville@cnet.francetelecom.fr>
Henry THOMAS <henry.thomas@cnet.francetelecom.fr>
France Telecom/CNET
France

Valérie CAMPS <camps@irit.fr>
Bernard CARPUAT <carpuat@irit.fr>
Marie-Pierre GLEIZES <gleizes@irit.fr>
Pierre GLIZE <glize@irit.fr>
André MACHONIN <machonin@irit.fr>
Jo PEZET <pezet@irit.fr>
Institut de Recherche en Informatique de Toulouse
France

Pierre BIEBER <pierre.bieber@cert.fr>
Patrice CROS <patrice.cros@cert.fr>
Centre d'Études et de Recherches de Toulouse
France

Abstract

This paper describes a multi-agent architecture that can help users locate services (or other users) that propose relevant information. We experimented with this architecture by implementing a service that performs matchmaking between sellers and buyers of secondhand vehicles.

Contents

Introduction

As the Internet grows, the search for relevant services becomes problematic. Frustrated users might restrain their Internet use to a few well-known services. Therefore the economic viability of new and little-known services is compromised. Of course, very popular indexing services could be used to direct the search. But it is not certain that these services will be able to cope with the Net evolution. These indexing services require a huge amount of work and resources to harvest every Web page and then to store locally an index of it. To reduce this amount of work and resource, an obvious idea is to share the effort among several cooperating agents. These cooperating agents should help users to access relevant services and, conversely, they should help a service to become known by interested users.

This paper describes an architecture for such cooperating agents based on a multi-agent theory. This architecture was developed in the context of Arcadia, a collaborative project of France Telecom/CNET, IRIT and ONERA/CERT laboratories [3]. The project goal was to show that the principles of multi-agent systems could be applied to implement innovative information access services.

The first section presents the multi-agent theory as well as a three-layered agent architecture. The second section explains how these multi-agent principles can be applied to the collaborative information access problem. Finally, we describe an experimental service that we implemented using the agent architecture; it performs matchmaking between sellers and buyers of secondhand cars.

Arcadia multi-agent architecture

Multi-agent principles

A multi-agent system can be viewed as a system composed of many interacting agents. The technical approaches to implementing agents are similar; each could have an individual goal. The main difference is that the multi-agent system must also possess a global task to solve: for example, an information system that can efficiently give all the relevant information. This global task is very difficult to solve in a dynamic environment in which unexpected events frequently occur under the constraint that no agent has a global view of the system. In order to overcome these unexpected events, the basic multi-agent principle is that agent communication is driven by "social conventions"[9].

The theory used in Arcadia [2] explains why a system having cooperative interactions between its parts (here, the agents) gives good results for the environment (users and services in Arcadia). Thus, the aim of the agents in Arcadia is to correct non-collaborative situations. "Incompetence" is an example of a non-collaborative situation where a request cannot be properly interpreted by the receiver. A cooperative way to correct this situation is for the receiver to send this request to agents assumed to be competent. Eventually, the request will reach a competent expert. When an agent receives an answer, it can make the correction on other agent capabilities. Conflict, redundancy, and ambiguity are other non-collaborative situations.

Three-layer agent architecture

Arcadia multi-agent architecture is a three-layer architecture; each layer is made of communicating agents following the same "social conventions." An agent at a level is made of cooperating agents at the sublevel.

Figure 1: Arcadia Multi-agent Architecture

Because the goal of Arcadia is to be applied in many topics and with numerous users, it cannot be centralized on a single machine. Thus, the first role of the top-layer agents is to add in a totally incremental fashion new users and services located anywhere in the world. These agents called Mediation Agents (MA) are distributed on interrelated computers. In the top layer, agents can be added or suppressed inside the system in avoiding any global view. In their second role, these agents could also be associated with service or user domains such as the set of users with the same Internet service provider or a collection of services sharing the same topic. Their goal is to structure the set of users and services in order to decrease the complexity of locating them.

The second layer is made of Transaction Agents (TA); each user or service in a domain is associated with such an agent. They are built when a new service is created or when a user makes his first connection. Transaction Agents have beliefs on the skills of other Transaction Agents which are on the same site. The transaction agent is in charge of exchanging autonomously requests or answers with other transaction agents. The transaction agent should also communicate with the user or service it is associated with.

All agents of the two previous types possess beliefs which describe the organization of the agent society. These beliefs constitute the third layer and express the viewpoint that can have an agent on another. They link the common concepts of two agents and confer on an agent the possibility of reasoning with others. They give the possible interaction links between the agents of the society. The third layer manages the knowledge of a transaction agent or a mediation agent in a fashion similar to a neural network. This network is precisely a multi-agent of beliefs composed of reactive agents, called belief agents, interacting locally. A belief from one agent to another is a number expressing the link strength. This knowledge is continuously updated on the basis of the transactions' flow. Thus, each layer is constantly improving its internal organization in order to give out relevant information efficiently.

Users send requests, receive answers, and provide feedback on the answers through a man-machine interface agent. An agent communicates with a service thanks to a service interface program called an adapter.

The Arcadia multi-agent system was implemented in C++, allowing one to implement the three agent layers as three instances of the same generic class. The man-machine interface is composed of several HTML pages and CGI scripts that can be viewed with a Web browser. Adapter parts are realized using CORBA and Tcl scripts [6].

Cooperative information access with Arcadia

The main objective of Arcadia is to perform a mediation between users and online services as Web sites or newsgroups. Arcadia helps users to get in touch with other users or services that might provide relevant information. Hence, users and services are likely to communicate with Arcadia in order to locate other users or services, and then they will communicate directly with these users or services.

Figure 2: Arcadia mediation service

A user or a service communicates with Arcadia through its adapter and transaction agent (TA). Whenever a user or service submits an information (request or answer) to its TA, it is systematically archived and indexed by the adapter. Then, Arcadia multi-agent system performs an information search.

Figure 3: Arcadia multi-agent system

The objective of indexing is to extract attribute values from the submitted information in order to be able to later query an archive maintained by the adapter. We might look for domain-independent attributes such as article status (query or answer) or domain-dependent attributes such as the brand, age, or mileage of a car.

The objective of the search function is to find relevant information among information previously submitted to Arcadia. The search proceeds in two steps: first locate a transaction agent that is likely to have relevant information and then query its adapter to collect the references (for instance, URLs) that will enable the user to access directly this information.

Information location is implemented by using agent "social conventions," whose aim is to correct non-cooperating situations. In this case, agents try to correct a non-cooperating situation called "incompetence" that occurs when an agent receives a request and it is unable to propose information corresponding to that request. A cooperative way to correct this situation is for the receiver agent to send this request to agents assumed to be competent (this step is called relaxation). Eventually, after several relaxation steps, the request will reach a competent agent that will send an answer message to the sender. When an agent receives an answer, it can correct its knowledge on other agent capabilities. This should help agents to faster locate relevant information for further transactions.

Figure 4: Information Location Scenario

Figure 4 shows the various messages exchanged by agents to locate information in the following typical scenario:

  1. User 1 desires some information about a topic but she does not know any source. She submits a message to Arcadia that only contains her topic of interest.
  2. Her transaction agent TA1 receives the message containing the topic by the way of its adapter. Because TA1 is incompetent, and it has no knowledge about a TA possessing relevant information about the topic, it enters the "blocked" state that allows a transaction agent to interact with its mediation agent.
  3. As mediation agent, MA1 has no knowledge about a TA within it that would be competent. It tried to correct this incompetence situation by sending a TA1 request to another MA that may be relevant.
  4. MA2 receives the corresponding message. MA2 believes that some of the TAs within it could answer to the TA1 request. Thus, MA2 "agentifies" the request by creating TAl' (a clone of TA1) with beliefs about TAs that MA2 thinks relevant.
  5. TAl' interacts autonomously with these TAs. After several relaxation steps, the request message is received by TA3 that is competent. TA3 queries its adapter in order to send an answer.
  6. TA3 sends directly the responses to TA1' although it did not receive the request directly from TA1'.
  7. As the goal of TAl' is reached, it enters the "fulfilled" state and it is suppressed by MA2. MA2 sends the responses to MA1 and updates also its beliefs.
  8. TA1 receives the answers and presents it to User 1.

When answers are found, they are placed in a result file devoted to the query so that users do not have to read every incoming article to look for an answer. Furthermore, the attributes associated with the articles can be used to present in a synthetic fashion the information found. Hence, the user can browse rapidly through the collected answers to assess whether they are worth being read in detail.

The search for relevant information should not stop as long as the user is interested in a query. Hence, whenever new information is submitted it should trigger a search and new information found should be appended to the result file. If, after the last step of our previous scenario, TA3 knows some new information relevant to the previous request of User 1, it tries to send it to TAl'. Because TAl' no longer exists, this information reaches MA2 which returns it to TA1 by the way of MA1. This last behavior is called "spontaneous communication" and allows recent information to be received without further query submission.

Belief management process

An MA or a TA uses its belief agent network in order to decide if it is competent for a given request. For example, at step 3 of the scenario, each word of the request activates a corresponding agent, which in turn sends messages to other linked agents. Services which seem to be relevant are excitated into the network which returns them to the outside. In our case, MA1 decides to send User 1 request to MA2 because MA1 thinks that MA2 is relevant.

After each communication step, agents update their knowledge about other agent capabilities. For instance, at step six of the previous scenario, TA1' updates its beliefs about TA3; it now knows that the service represented by TA3 is competent for the topic. Similarly, when at step seven MA2 sends the answers to MA1, it updates also its beliefs about TA3 capabilities. In order to keep track of this evaluation, the belief agent network is now used for a learning phase. It leads to an increase or decrease in confidence in the service. This new information is inserted in the beliefs network and disturbs the actual internal organization. A new organization is founded by the network when interactions are cooperative. Thus, the learning process is similar to those applied in self-organizing mediation agents or belief agents.

The most innovative aspect of the enhanced newsgroup is that user opinion is taken into account in order to locate relevant information sources. Users are requested to provide a feedback when they read answers to their queries. Using user feedback, the search function elaborates a collaborative recommendation for information sources. At the last step of the scenario, User 1 should evaluate the relevance of the answers provided by TA3 in order to improve the beliefs of TA1 and MA1 about TA3 capabilities.

Experiment: an electronic marketplace for secondhand vehicles

We implemented an experimental service in the domain of classified ads for secondhand cars. We archived and indexed around 3,000 articles of newsgroup fr.petites-annonces.vehicules between March 1996 and November 1996. This enhanced newsgroup also contains ads found in ten Web services including the electronic version of the French classified ads newspaper "La centrale des particuliers" as well as Web sites such as WebDataBase or Toutela. Each article is analyzed in order to find information about the brand of the vehicle, its price, its mileage, and its owner's phone number. We also analyze the ad in order to find out whether its author wants to sell or buy a car.

The goal of the experimental service that we designed is to provide information of at least the same quality as that found in a classified ad from a newsgroup and to eliminate some of the drawbacks such as the need to consult a lot a articles in order to find interesting stuff or the difficulty of finding out what was already posted on the newsgroup.

This experiment does not illustrate the problem of indexing and having to search through a vast number of independent services, as only a small number of well-known services are used. But, as there are a great number of people who post articles in newsgroup, our experiment illustrates how multi-agent principles can be used to tackle the problem of searching for interesting ads among a great number of articles.

Figure 5: A Result Page

We tested various uses of this experimental service. Of course, a seller could use it to locate users who want to buy a matching car. A seller could also use the experimental service to have a global view of the market in order to decide for what price she should sell her car. She would be interested in the articles selling an identical car.

This experiment was mainly used to validate Arcadia architecture and implementation techniques. It would now be interesting to perform another experiment with actual users in order to validate this service's added value. Our prototype architecture should enable researchers to perform such an experiment as it has a distributed architecture, and it can be reached through a Web page. So this service could be potentially used by a great number of people.

Related works

Agents, based on artificial intelligence like Topic (Verity) and Internet Sleuth (MCC Carnot), allow users to search the Web in depth with a friendly interface. Autonomy (Cambridge University) is a search engine capable of a dynamic reasoning suggesting similar notions to reach the greatest possible precision. For more information see [10].

The collective filters represent a new means of evaluating the resources on the Web.

  • Metadata: Dublin Core Metadata and Warwick projects deal with automatic classification (see [11]) and define a set of metadata and methods to integrate them in the Web pages: metatags (titles, authors, style, type of document)
  • Boulder University has developed the program Harvest, which indexes its own pages that transmit to the various search engines (see [12]).
  • Cooperative filtering systems, like Group Lens, Phoaks, or Firefly of Yahoo (to a lesser degree) are based on the favorite sites of groups of people sharing the same interests. Such systems carry the dangers of influencing the users (hiding marketing under recommendations), which is not the case with multi-agents systems, like Arcadia.

Many authors [7], [8], [5] have developed the applications of an agent in the field of Cooperative Information Systems. The basic assumption of these works is that an entity (for example a mediator) has the ability to link different terms or topics in order to find the right information source. In a dynamic world, this assumption must be replaced by some learning mechanisms about concept acquisition and relationships [1]. This is done in Arcadia, where new knowledge about agents' skills is acquired cooperatively as the result of their interactions.

Conclusion

The experimental service described in this paper shows that the multi-agent system has brought about intrinsic innovations for

  • convergence towards maximal satisfaction of the clients (final users and service offers) of the mediation service ("win-win" approach);
  • great flexibility to follow the dynamic evolution of the offers-demands context; and
  • contextual and personalized help for the clients (e.g., information pushing according to the user profile).

Extensions to other applications are foreseen in the tourism and job research domains. These extensions to new data fields should prove the robustness of the approach -- in other words, the genericity of the basic functions provided by the multi-agent architecture, and above all, the added value of the Arcadia multi-agent service to new business domains.

References

  1. Bollen Johan, Heylighen Francis, "Algorithms for the self-organization of distributed, multi-user networks. Possible application to the future World Wide Web" Cybernetics and Systems'96 - R. Trappl (Ed.) - 1996
  2. Camps Valérie, " Vers une théorie de l'auto-organisation dans les systèmes multi-agents basée sur la coopération : Application à la recherche d'information dans un système d'information répartie ", Thèse de l'Université Paul Sabatier N. 2890 - 1998
  3. Camps V., Gleizes M.P., "Cooperative and mobile agents to find relevant information in a distributed resources network", Workshop on Artificial Intelligence-based tools to help W3 users, Fifth international conference on WWW - 1996
  4. Cesta Amedeo, Miceli Maria, Rizzo Paola, "Effects of Different Interaction Attitudes on a Multi-Agent System Performance", Lecture Notes in Artificial Intelligence 1038 - MAAMAW'96 - The Netherlands, January 1996
  5. Knoblock Craig A., Arens Yigal : "An architecture for information retrieval agents", AAAI Spring Symposium on Software Agents, Stanford, 1994.
  6. Ousterhout John, Tcl : an embeddable Command Language, proceedings of the Usenix winter Conference, 1990
  7. Singh Munindar, Huhns Michael, "Challenges for Machine Learning in Cooperative Information Systems"- Lecture notes in AI - Vol 1221 - Springer-Verlag, 1997
  8. Wiederhold, Gio, "Mediators in the architecture of future information systems" IEEE Computer, Vol25 N.3, 1992
  9. Wooldridge Michael, Jennings Nicholas, "A theory of cooperative problem solving," Intelligent Agent Workshop of the British Computer Society - November 1995
  10. URFIST, http://www-sv.cict.fr/urfist
  11. Dublin Core Metadata, http://www.dlib.org/dlib/july96/07contents.html
  12. Harvest, http://harvest.transarc.com

[INET'98] [ Up ][Prev][Next]