Bibliography Agents – The Multi-agent Community

Bibliography Agents – The Multi-agent Community

張碧娟Pi-Chuan Chang, 余家興Chia-Hsing Yu

黃振修Chen-Hsiu Huang, 葉人豪Jen-Hao Yeh,

Department of Computer Science and Information Engineering

National Taiwan University, Taipei, Taiwan, ROC

ABSTRACT

  1. INTRODUCTION

Finding useful information on the web is an interesting topic. There are some benefits in using multi-agent system to do this kind of job because whenever a more intelligent agent joins, the search power will increase.

The ultimate goal is to find the publication given complete or partial bibliography from user input. There are also some agents who do the data post-processing job (such as clustering and format conversion) to show more analyzed information to the user. In our work, we present a flexible agent architecture, which enables agents with new (or improved) skills to join the community.

In Section 2, we will describe the way our agents communicate and coordinate, and an exemplary workflow is shown in Section 3. The detailed description of each agent in the community will be explained in Section 4. Some technical issues we encountered while we were implementing the system will be discussed in Section 5. Section 6 is about how to setup the agents in our community. And in the end, all references will be listed in Section 7.

  1. AGENT COMMUNICATION AND COORDINATION
  2. Communication Language

Our agents communicate in reduced KQML, and we choose Scheme as the language for the content. The KQML performatives implemented in our system are described below:

ASK
The ASK performative is used to ask the truth of a question given in the content. It is the most common performative used in multi-agent systems.

TELL
In response to the ASK performative, agents use TELL to reply questions being asked.

ADVERTISE
Agents use this performative to advertise the facilitator of their capabilities.

RECRUIT
The RECRUIT performative is used to tell the facilitator what the agent need from other agents.

One benefit to use Scheme is that we can treat KQML as a specialized version of Scheme. Thus we need only one parser in agent communication. Besides, Scheme is simple and powerful enough to present data structures used in this system. In fact, we use a reduced version of Scheme.

2.2.Coordination Mechanism

Thefacilitatoris the key of the coordination between agents. It is an agent who maintains capabilities of all agents in the system. When joining the system, every agent advertises its capabilities to the facilitator. An agent who needs help from other agents will tell the facilitator what it is interested in, and the facilitator will redirect the message to the agents who can help. So new agents may join the system easily without modification of other agents.

When the agent B joins the system, it sends a message to the facilitator like this:

B tells F (facilitator) that it can find the paper given in x. Once another agent A sendsa recruit message to the facilitator:

The facilitator will ask B“(find-paper x)”for A. Finally B tells A the truth of “(find-paper x).” The interactions between agents are illustrated in Figure 1.

Under this architecture, agents can freely join and leave the community. Agents can have some common capabilities/skills. In our system, there are more than four agents who can find paper. Each of them uses different information sources. The repetition of capabilities improves the performance and robustness of the entire system.

Another benefit of this architecture is that agents can fork themselves when necessary. We use lots of this technique to improve the speed of fetching data from the Internet. In our experiments, sometimes there were more than fifty agents and their child agents in the community at the same time.

2.3.Underlying Network Implementation

The underlying communication network is implementing over the TCP layer. The server works like a hub in Ethernet. Each agent has one TCP connection to the “hub” server. A message sent from an agent to the server will be broadcasted to all other agents connecting to the server.

  1. WORKFLOW

User interacts with our agent system via web interface and posts the bibliography in the form of BibTeX to ask our agent system to do the job. The overall work flow may be described as follows:
The user input one or more BibTeX from web (twenty in the test case).

  1. Given input BibTeX, the Interface Agent asks the agent community if someone can answer/solve the question/problem from the facilitator.
  2. The question may be something like “where is the paper of bibliography xxxx ?” (Certainly, in the agent communication language). So the information source agents will try to answer the question.
  3. Information source agents know that if the supplied material is enough to accomplish their job. If the BibTeX is not regarded as complete, it may just give up (e.g. book without book title) or do its best to find it out (e.g. IEEE papers but with no IEEE indication in the BibTeX fields).

Figure 2. General architecture of information source agents

  1. There are three different kinds of information source agents: Publisher Agent, Bookstore Agent, Library Agents, and Search Engine Agent. Information agents do their best to find the exact paper, not to find as more as possible.
  2. All of them share the common architecture shown above: first read the input BibTeX questioned from facilitator and compose it into specific query string (e.g. ACM and IEEE have their own query notations). Then send the search request to the information source and wait for the response. At last, parsing the result for available information (e.g. match items or nothing found).
  3. Now the interface agent gets the answer, it sees the answer if it contains paper’s URL. If provided with paper’s URL, it asks the Retrieve Agent to get the paper’s electronic file.
  4. The data of the paper are now stored in the database, which is served as the NFS of our agent community. The data post-processing agents, such as the Format Agent, the Document Agent, the Abstract Agent, will try to process these data fetched from the Internet. The Format Agent transforms between several formats. The Document Agent will analyze the text files generated by the Format Agent, and the Abstract Agents will try to extract abstract from the text file.
  1. INDIVIDUAL AGENT DESIGN
  2. Implementation Language and Platform

Agents in our system need not reside in one central host, whereas they can be dispersed over different computers with heterogeneous system environments. The TCP/IP network provides the best infrastructure of agents’communication.

Language used for implementation is not limited, since support for socket programming interface is the only requirement. C/C++, PERL, Java are all candidates, depending on the team members’personal preference. And all of them support a variety of platforms, so the overall multi-agent system can be regards as platform independent.

4.2.User Interface Agent (UI Agent)

4.2.1.Agent architecture

The UI agent is a purely reactive agent; it works between the real world and the agent community. Its goal is after understanding the input of user, and presents the result obtained from other agents to the user. The actionof this agent is simple:

  1. Translate the input (BibTeX in here) into agent languages(KQML) and ask other agents where the paper is, it will also asking for information of the author if user specified.
  2. Collect the answers returned by others, arrange them. Ask if there's anyone could extract the abstract from this paper.
  3. Present the possiblecandidates o to user.

4.2.2.Detailed Function Specification

The interaction between the user and our agent system is achieved via a web interface. Upon visiting our site, the user can use BibTeX for querying, and our agents will use those clues to find the possible target publications.

The Agent will translate the input into KQML format and recruit help from the facilitator and see if any agent can help with it. After receiving the answer, UI agent will arrange the answer and ask if there’s any agent could get the file, or the abstract of the papers for him to show.

This Agent is implemented in C on UNIX (FreeBSD) to provide web interface in CGI form.

Also, it will save the answer in this query for future use. It may report failure to the user if nothing is found. Following image is an example of our output.

4.2.3.Interface with other agents:

This Agent may ask/say the following to other agents:

Interface
/ Description
Ask(find-paper(BibTeX)) / Where is the paper related to the following BibTeX?
Ask(find-author(BibTeX)) / Please find the homepage of the Author who was described in BibTeX for me
Ask(abstract(filename)) / Please extract the abstract of the paper for me if possible

4.3.Retrieve Agent

4.3.1.Agent Architecture

The goal of retrieve agent's is simple, Given the URL and retrieve the file from the Internet by invoking program “wget”. After the file has been downloaded, it will be inserted into database for further processing. Of course it may fail if the link is dead or the network is terrible. Obviously, it is also a purely reactive agent.

4.3.2.Interface with other agents:

It could answer the following:

Interface
/ Description
(get URL) / Retrieve Agent will try to download the file from the given URL.

According to the question, it may answer:

Interface
/ Description
tell(file-path(F)) / The file is downloaded and is put in the following path F.
tell(fail(F)) / Retrieve has failed due to the reason F.

4.4.Information Source Agents (Publisher, Bookstore, Search Engine, and Library Agent)

4.4.1.Agent Architecture

We have Google agent, IEEE agent, ACM agent, Amazon agent, NTU Library agent, CiteSeer Agent, and SDOS agent as our information source agent. They are purely reactive agents with internal states. Their actions and internal state transition can be illustrated as the following figure:

The actions of information source agents are already described in the WORK FLOW section.

4.4.2.Detailed Function Specification

Function
/ Description
Advertise() / When system boot, advertise the Facilitator their capability of doing something
Receive() / Function constantly listens on the agent communication channel. When asked with some question, agent will be wakened from here.
Reply() / Reply to the sender with the answer which agent solved.
Judge() / Judge the answer is yes or no (found or not)

4.4.3.Interface with Other Agents

Interface
/ Target/Description
Tell(answer(P)) / Interface Agent
Reply the answer of P to sender

4.5.Document Agent

4.5.1.Agent Design

The mission of the Document Agent is to analyze the documents in the database and provide useful analysis result to the user, e.g., the clustering of previously found papers.

Document clustering definitely isn’t an easy problem. There are many issues to be thought over. For example, how to set the number of clusters, the number of documents in each clusters, what clustering method should be used, etc. I will cover these issues in “Implementation strategies”.

4.5.2.Interface with Other Agents

The Document Agent is a hardworking agent. Most time it works on its own tasks, but other agents can also ask it for services. There are two kinds of services it can provide, that is, produce the document vector and clustering of every document.

When the computation is over, the Document Agent store the results into the database, where every agent in the society can access.

Also, the Document Agent might need file format conversion service, which can be provided by the Format Agent.

4.5.3.Detailed Function Specification

Produce document vectors for documents in database
The Document Agent will actively check the existing documents in the database. If there’s any unprocessed document, the Document Agent will first perform word stemming (using Porter stemming algorithm[1]) and stop-word elimination, and then process it into a document vector. The table below is an example.
The actual program used by Document Agent is doc2mat[2], which can convert documents into the vector-space format used by CLUTO.

A document:
/
Corresponding document vector
This is a book.
There are books and pencils. / book 2 pencil 1

Ask others for converting the paper format to pure text
A subtask of producing document vectors. Oftentimes the retrieved papers are PDF or PS files. Since the Document Agent needs to do text processing, the pure text of the papers must be extracted first.

Cluster all documents in database
The Document Agent will cluster all documents in database, using the document vectors processed beforehand. This can be done when other agents ask for this skill to be performed, or the Document Agent would perform it every now and then.

4.5.4.Implementation Strategies

At first I intended to use the Bow toolkit [10], but unfortunately, the document clustering front-end (crossbow) in the Bow toolkit is not a bug-free program. I tested some data with the crossbow program and found bugs in it. Therefore, I tried to find another clustering toolkit for this task.

The clustering part of my Document Agent relies on the clustering toolkit: CLUTO. There are several reasons why I choose it. First of all, it’s a well-documented [11] tool. This also means the development of this tool is quite well-organized. Second, it’s a general clustering toolkit, which provides us three different classes of clustering algorithms. These algorithms are based on the partitional, agglomerative, and graph-partitioning paradigms. The clustering method I used was k-way clustering via repeated bisections [12]. In this approach, a k-way solution is obtained by first bisecting the entire collection.Then, one of the two clusters is selectedand it is further bisected, leading to a total of three clusters.The process of selecting and bisecting a particular cluster continues until k clusters are obtained.Each of these bisections is performed so that the resulting two-way clustering solution optimizes a particular criterion function.

Beside its generality, it also provides several functionalities that aims at document clustering problems, e.g., I use a parameter -colmodel=idf which scales the columns of the matrix according to the inverse-document-frequency (IDF) paradigm.

Although CLUTO provides many different clustering method, I don’t make use of all of them. In this project, I use the stand-alone program vcluster of CLUTO, and the command is:

vcluster -colmodel=idf -clabelfile=$CLABEL $matfile $numcluster

“$matfile”, the primary input of CLUTO’s vcluster program, is a matrix storing the documents to be clustered. Each row of this matrix is a document vector of a single document, and its various columns correspond to the dimensions (i.e., features) of the documents.

“$clabel” stores all columns (features) of the document matrix.

“$numcluster” is the number of clusters that is desired. As I said before, choosing the number of clusters is also a nontrivial problem. There are some papers discussing this issue [13], but I merely apply a naïve heuristic to decide the cluster number. If the number of all files (with converted text) is N, the cluster number is set to N/5. If the cluster number is greater than 10, then the cluster number is set to 10.

The implementation programming language of Document Agent is Perl, and the platform it runs on is a FreeBSD server.

4.6.Format Agent

4.6.1.Agent Design

Format Agent welcomes any kinds of file conversions task, if it knows how to do. Now there are two kinds of target formats: html and pure text; the kinds of source formats are pdf, ps, ps.Z, ps.gz, html.

4.6.2.Interface with Other Agents

When other agents ask for tohtml or totext skills, Format Agent will look up the given file name in the filetable (our NFS). If the file exists, it will complete the requested conversion and store the results into the file table. Then the Format Agent will send back a message to notify the sender that the job is done.

4.6.3.Detailed Function Specification

Convert file formats
When tohtml or totext skills are requested, Format Agent will do the conversion if it can.

4.6.4.Implementation Strategies

The following table shows the conversions available now and how they are accomplished:

Conversion kinds:
/
How to do the conversion
PDF to Pure Text / pdftotext[3] –raw PDF-file text-file
PS to Pure Text / ps2ascii[4] PS-file text-file
ps.Z to Pure Text / uncompress, then ps2ascii
ps.gz to Pure Text / gunzip, then ps2ascii
HTML to Pure Text / Remove html tags (everything enclosed in angle brackets)
PDF to HTML / Pdftohtml[5] -q -noframes -i PDF-file html-file
PS to HTML / ps2pdf PS-file PDF-file,
pdftohtml[6] -q -noframes -i PDF-file html-file
ps.Z to HTML / uncompress, then perform PS to HTML
ps.gz to HTML / gunzip, then perform PS to HTML

The performance from PS to HTML is not very satisfying because the PS files are converted to PDF files first, then converted to HTML files. But as far as I know, there’s no good way to directly do the conversion. Thus, the method adopted in my implementation is an indirect one.

4.7.Abstract Agent

4.7.1.Interface with Other Agents

Abstract Agent is purely reactive because it will act only when someone asks it to perform the abstract extraction. Abstract Agent will look up the given text file name in the filetable (our NFS). If the file exists, it tries to extract the abstract and return the result to the sender.