A Logic-based Framework for Mobile Intelligent Information Agents

Naoki Fukuta, Takayuki Ito, and Toramatsu Shintani
Nagoya Institute of Technology
Department of Intelligence and Computer Science
Gokiso-cho, Showa-ku,Nagoya, Aichi, 466-8555, JAPAN
+81-52-744-3153
{fukuta, itota, tora}@ics.nitech.ac.jp

ABSTRACT

Information agents are computational software systems that can access to distributed, multiple, and heterogeneous information sources, and can integrate them. Since their information sources are dynamically changing, they have to handle their behavior, and cooperate each other in such environment. To realize such intelligent behavior on the agents, it is helpful to use some frameworks for them. In this paper, we propose MiLog, a logic based mobile agent framework for constructing them. In the framework, we provide following three features: (1)a complete programming language for cooperative information agents based on logic language, (2)powerful library to wrap Web-based services, and to provide Web based service by the agent, (3)interrupted anytime migration capability to react their environmental changes on the agents. The framework is implemented by Java and currently used to develop web-based decision support systems and intelligent information integration systems.

Keywords

Mobile Agents, Logic Programming, Programming Tools

1. Introduction

There have been growing interest on information gathering on the Internet. An Information gathering system is consisted of an information retrieval mechanism and an information integration mechanism [7]. In general, in order to find information from the Internet, we can employ meta-search engines, such as MetaCrawler [10], SavvySearch [4], and InfoSpider [8]. Although these meta-search engines can find information with simple procedure, they have no capability to use domain specific strategies or user specific strategies for enhancing the search strategies.

Information agents have been investigated very actively. Information agents are computational software systems that can access to distributed, multiple, and heterogeneous information sources, and can integrate them. Since their information sources are dynamically changing, they have to handle their behavior, and cooperate each other in such environment. For example, item prices on online auction sites are often changed by another bidding. The agent which monitor and gather information on online auction sites must take into account to those changes. Sometimes the change is so often to handle single agent, they must have to handle by two or more agents cooperatively.

To realize such intelligent behavior on the agents, it is helpful to use some frameworks for them. In this paper, we propose MiLog[3], a logic based mobile agent framework for constructing them. In the framework, we provide following three features:

  1. A complete programming language for cooperative information agents based on logic language: The language is an extended prolog language which can handle multi-thread and inter-thread communications. It is considered to realize strong mobility and interrupted execution on the interpreter shown at (3).
  2. Powerful libraries to wrap Web-based services, and to provide Web based service by the agent: The library is quite powerful to integrate both of information extraction programs and HTML based user interface control programs into an agent. Since this omits any agent to wrapper, or agent to server communication mechanisms, the program of the agent is kept quite simple.
  3. Interrupted anytime migration capability to react their environmental changes on the agents: The interpreter supports not only simple strong mobility but also interrupted execution. The agent program may interrupt its execution at nearly anytime and it can move to any hosts(or platforms) with keeping interrupted tasks if needed. This makes it possible flexibly choose the host during its task execution.

The framework is implemented by Java and currently used to develop web-based decision support systems and intelligent information integration systems.

The rest of this paper is organized as follows: Section 2 presents an overview of the MiLog framework. Section 3 presents a method for describing wrappers simply on the MiLog framework. Section 4 presents the implementation model for providing inter-operability among agents. In section 5 we presents the architecture of mobile agents on the MiLog framework. In section 6 we discuss the features of the MiLog by presenting a real world application which supports online auctions on the Internet. Section 7 summarizes this paper, and show some possible directions for future researches.

2. An Overview of the MiLog

Fig.1 The structure of the MiLog framework

Figure 1 shows the structure of the MiLog system. On the framework, each agent has an interpreter which interprets Prolog programs for the agent. Agents can get information from WWW server by using a WWW access library. For extracting words from Japanese documents, agents can use a morphological analysis library. Agents communicate with other agents by using an inter-operability library. Agents can move to other computers by using an agent transport manager. Agents control their platform-depend resources by using an environment access wrapper. The WWW Request Router enables agents to communicate with HTTP client (i.e. WWW browsers).

The framework has been implemented on the JAVA(tm) language. The agent description language interpreter is an extended Prolog interpreter that enables multi-thread programming with using suspension, interruption and resumption for realizing its mobility. The architecture of the mobility are described in section 5. To process multiple queries concurrently, an agent can share a clause its internal database (for recoding Prolog programs) with their clones. The clones can be used for realizing the multi-thread capabilities.

Figure 2 shows a user interface of the MiLog framework. Each agent has a console window to control, query, and edit the Prolog programs. The agent monitor shows which agents exist currently, which agents are communicating, and which agents are coming or going on the agent platform. In the agent monitor, agents are shown by using graphical icons.

Fig.2 A User Interface of the MiLog

3. Extracting WWW information

In this section, we show how to describe programs for extracting WWW information on the MiLog framework. In general, the information extraction programs are called the wrappers. The wrappers provide uniform access methods to specific WWW pages written in HTML by using page-specific pattern matching mechanisms. It is difficult for generating the wrappers automatically. The reasons can be summarized as follows: The first reason is that HTML documents represent only their structures for displaying. The patterns to extract some data from such documents are ill-structured. The patterns should be written in an expressive description language. The second reason can be described as follows. Extracting all data from a document wastes CPU and memory even if the document is written in XML.

In the MiLog, an HTML document is stored in a list by using the built-in functions. For instance, a document that has tags such as <A HREF="link.html">link</A> is stored into a list [[a,[href,'link.html']], link, ['/a']] by using the built-in functions. The powerful list processing of the logic programming language can be effectively used to extract data from the list. By using the list processing functions in the MiLog, a wrapper can parse an HTML document effectively.

Next, we show an example that extracts some information from a HTML document.

?- extract( [ _, [[tr]], _,                     
              [[font|_],                        
               [a,[href,HREF]],                 
               ItemName,_,['/td']],             
              R],                               
            [ ..., [tr],                        
             [td], 'Some text...', ['/td'],     
             [td], [font,[...]],                
             [a,[href,'link.html']], 'The item',
             ['/a'], ['/td'], ['/tr'],          
             ['/table'], ... ] ).               

In this example, two data (ItemName and HREF) are extracted by using the predicate extract/2 in which the first argument takes a pattern, and the second argument takes an HTML document. The predicate (or function) extract/2 is efficiently executed by using backtracking and pattern matching on the system. By processing the query, the variable ItemName and HREF are bound to `The item' and `link.html' respectively. The pattern in the query is quite simple. And the query can be processed at enough speeds without useless memory consumption.

4. Interoperability among agents

To realize inter-operability among agents, there exists a trade-off of usability and compatibility. The usability means how easy can users write programs which realize inter-agent communications and controls (such as bringing some tasks to other agents, sharing some information among several agents, and so on). The compatibility means how widely agents communicate with other agents.

Many agent communication languages (ACLs) are proposed [1][2]. But they are too large and complex for using local communications among agents. They need some wrappers to communicate with other non agent-based systems (such as search engines or auction sites on the Internet). In general, there exist a lot of needs to realize information agents which can communicate with web-based applications. The MiLog can support users to easily implement wrappers.

In the MiLog framework, we provide the following two types of communication methods. Firstly, a direct querying method to other agents for using local communications. Secondly, an HTTP-based indirect communication method to interact with remote web based systems.

In the MiLog framework, the following two types of local communications among agents are available. Firstly, a shared clause database can be used for local communications. The MiLog provides a predicate to make clone agents from a certain agent. These clone agents can share a clause database which is an internal database to store Prolog programs (or clauses). For example, when the predicate clone2(pine) is called on an agent named tiger, the clone agent named pine is created. Each clone agent runs concurrently with a shared clause database. Secondly, querying to other agents is the other type of local communication methods. An agent can query to another agent when that agent is in the idle status. The MiLog provides several predicates for posting a query to another agent. There are the following predicates for posting a query: a synchronized query predicate, an asyncronized query predicate, a concurrent query predicate, and a query predicate which create target agent's clone to respond. For example, when the predicate query( pine, feeling(FEELING)) is called on an agent tiger, the agent pine evaluates feeling(FEELING) and then make a response such as feeling(good). On the agent tiger the variable FEELING is bound to good.

By using the MiLog framework, agents select these two types of local communication methods based on their needs for communication.

The MiLog framework provides WWW Server/Client capability for agents. While an agent can access to a WWW server, the agent can act like as a WWW server to respond to another clients. To access to WWW servers, we provide some built-in predicates. Users can write wrappers simply and easily. To respond to requests from other clients, we provide a WWW request router which converts a HTTP request into a Prolog query in local communication, and sends the client an HTTP response. In order to make an agent be a WWW server, we only add definitions of the clause doService/2 to the agent's program. Consider the following clause is defined in the program of the agent tiger. In this case, a user can access to this agent by using a WWW browser with the URL http://some.host.com:1234/tiger?message=feelGood in which the ``:1234/'' is a port number, the tiger is an agent name, the message=feelGood is data used by the predicate doService. Then the WWW browser can get a responding page(that is, the content of the variable OUT), which includes a string feelGood.

  doService( ID, OUT ) :-                                                                       
     option(ID,message,M),                                                                      
     OUT = ['<HTML><HEAD></HEAD><BODY>',M,'</BODY></HTML>'].

5. Mobility

Fig.3 The implementation model of the mobile agents

Figure 3 shows the architecture for implementing mobile agents. Each computer has one meta agent which is a transmitter and a part of an agent transport manager in Figure 1. A mobile agent migrates from computer `A' to computer `B' as following steps :

The meta agents are also written in the MiLog with some extended built-in predicates which controls the internal states of other agents. The transmitter meta agents are also mobile agents which can migrate from a host to a host. This architecture enables the system to dynamically reconstruct agent migrating and transporting mechanisms such as security manager or hierarchical migration of agents [9]. Figure 4 shows a sample code of a simple meta agent. On the STEP1, the mobile agent requests the predicate move/2 to the meta agent. For example, if mobile agent named mover intends to move the host 123.45.67.8:9012 (this means that IP address is 123.45.67.8 and port number is 9012), the following request is established. move( mover, '123.45.67.8:9012' ) The meta agent captures the status of the agent (Figure 4 line:2), sends them to an appropriate meta agent on the target host(Figure 4 line:3), and then delete the agent(Figure 4 line:4). When the transportation fails, the agent is not migrated and continues its execution on the local host (Figure 4 line:6--7). A meta agent on the target host receives the request to resume the mobile agent. For instance, the following predicate is called on the meta agent ( the string '....' means the encoded binary data of the mobile agent.). receiveAgent( mover, '....' ) The meta agent decodes and verifies the status of the mobile agent, and then resume its execution on the target host (Figure 4 line:9--11). There are many security or transporting issues [13][9][12][11] to apply to meta agents.

 1  move( Agent, Host ) :-                          
 2    serialize( Agent, Bin ),                      
 3    transmitterMetaAgentName(T),                  
 4    request( T, receiveAgent( Agent, Bin ), Host),
 5    deleteAgent(Agent),!.                         
 6  move( Agent ,_ ) :-                             
 7    resume( Agent ).                              
 8  receiveAgent( Agent, Bin ) :-                   
 9    deserialize( Agent, Bin ),                    
10    verify( Agent ),                              
11    resume( Agent ).                              
Fig.4 An example of transmitter meta agent

6. BiddingBot : A Practical Application on the MiLog

We have proposed BiddingBot[5], a system which can support bidding to several auction sites simultaneously by the cooperative bidding agents[6]. In this section, we show how BiddingBot system is implemented by using the MiLog framework.

Fig.5 The BiddingBot System

Figure 5 shows the architecture (on the left of the Figure 5) and the user interface (on the right of the Figure 5) of BiddingBot. BiddingBot consists of one leader agent and several bidder agents. Each bidder agent is assigned to an auction site. Each agent is implemented by using the MiLog framework. The bidder agents cooperatively gather information, monitor, and bid in the multiple auction sites simultaneously. The communications among agents are implemented by using shared clause databases and querying to other agents. The leader agent facilitates cooperation among the bidder agents as a match-maker, sends a user's request to the bidder agents, and presents bidding information to the user. The leader agent interacts with a user as a WWW server on the MiLog framework. The cooperation protocol are implemented by finite state machines in which the state is changed by receiving a certain query from other agents. In BiddingBot, each of the bidder agents is specified to her auction site and can behave as a flexible wrapper, since different auction sites represent information in different forms. Wrapper functions on the bidder agents are implemented by using a pattern description language in the MiLog.

7. Conclusion

In this paper, we proposed the MiLog framework for constructing intelligent information agents on the WWW. We presented the following three useful components on the framework. (1) The information extraction description, (2) The powerful logic programming language interpreter with inter-operability, and (3) The meta agent model and its implementation for mobility of the agents. We presented the following examples to demonstrate how effectively we can program on the MiLog. (a)An expressive pattern description language for wrappers, site-specific information extraction programs to reduce the cost of constructing such ill-formed programs: By using the MiLog, we can simply represent web pages in the style of logic programming. (b) Two types of inter-operability among agents: Firstly, we presented direct inter-operability for local communication with lower overhead. Secondly, we presented indirect inter-operability by using WWW Server/Client mechanisms to interact with other web-based applications or the users by using WWW browser applications. Since the MiLog supports multi-thread programming and messaging mechanisms among agents, we can effectively implement cooperation mechanisms among agents. (c) A meta agent based migration implementation for dynamically selecting the best method for transporting and authorizing agents: We demonstrated a simple meta agent program which can be extended by applying models for security, authorization, and transportation management mechanisms for realizing efficient migrations of agents. We have implemented BiddingBot, an online auction support system by using the MiLog framework. We demonstrate that our approach is useful to incorporate intelligent behaviors into mobile agents.

8. REFERENCES

  1. T. Finin, Y. Labrou, and J. Mayfeld: KQML as an agent communication langauge. J. Bradshaw (Ed.), Software Agents, MIT Press, 1995.
  2. FIPA Agent Communication Language. http://www.fipa.org/spec/fipa97/FIPA97.html
  3. N. Fukuta, T. Ito, and T. Shintani: ``MiLog: A Mobile Agent Framework for Implementing Intelligent Information Agents with Logic Programming,'' Proc. of the First Pacific Rim International Workshop on Intelligent Information Agents(PRIIA'2000), pp.113-123, 2000.
  4. A. E. Howe and D. Dreilinger,``SavvySearch: A Metasearch Engine That Learns Which Search Engines to Quer,'' AI Magazine, SUMMER 1997, pp.19-25, 1997.
  5. T. Ito, N. Fukuta, T. Shintani, and K. Sycara, ``Multiagent Cooperative Bidding Support for Electronic Auctions,'' Proc. of ICMAS2000, pp.435-436, 2000.
  6. T.Ito, N. Fukuta, R. Yamada, T. Shintani, and K. Sycara,``Cooperative Bidding Mechanisms among Agents in Multiple Online Auctions,'' Proc. of PRICAI2000, pp.810, 2000.
  7. M. Klusch, `` Intelligent Information Agents : Agent-Based Information Discovery and Management on the Internet,'' Springer, 1999.
  8. F. Menczer and A. E. Monge,``Scalable Web Search by Adaptive Online Agents: An InfoSpiders Case Study,'' M. Klusch Ed. ``Intelligent Information Agents -Agent-Based Information Discovery and Management on the Internet,'' pp.323-353, Springer-Verlag, 1999.
  9. I. Sato. ``MobileSpaces: A Framework for Building Adaptive Distrubuted Applications using a Hierarchical Mobile Agent System'', Proc. of IEEE International Conference on Distrubuted Computing Systems(ICDCS'2000), IEEE Press, 2000.
  10. E. Selberg and O. Etzioni,``The Multi-Service Search and Comparison Using the MetaCrawler,'' Proc. 4th International World Wide Web Conference,pp.11-14,December,1995.
  11. P. Tarau : `Jinni: Intelligent Mobile Agent Programming at the Intersection of Java and Prolog,' Proc. PAAM'99, 1999.
  12. R. Tolksdorf, ``On Coordinating Information Agents and Mobility'', in M. Klush (Ed.) Intelligent Information Agents -- Agent-Based Information Discovery and Management on the Internet, pp.396--411, 1999.
  13. W. Vieira, L. M. Camarinha-Matos. ``Execution Monitoring in Adaptive Mobile Agents'', in Proc. of 3rd International Workshop on Cooperative Information Agents, pp.220--231, 1999.