Chapter 9
Agents in Program Mining

9.1 INTELLIGENT AGENT
9.2 INTELLIGENT AGENT SYSTEM IN PROGRAM MINING
9.3 AGENT INTERACTION LANGUAGE AND PROTOCOL
9.4 ARE—THE AGENT RUNNING ENVIRONMENT IN PROGRAM MINING
REFERENCES

Agent is the result of artificial intelligence research and network technology development. It endows the software system with a certain amount of intelligence allowing it to autonomously implement tasks on behalf of users or other agents, and interact with surrounding environments in appropriate modes. An intelligent agent consists of three basic elements: perception, deduction and behavior. Of this, perception evokes the deduction, which in turn results in behavior and results. If an agent can move freely among network nodes, it is termed a mobile agent. The mobile agent can respond to user requests to move freely in the network node agent running environment, seeking proper computing resources, information resources, and software resources to better fulfill user tasks. Meanwhile, these agents can co-share the knowledge they bear by means of communication, divide the work and collaborate with each other, form an organic entity, and help the user to complete some complex tasks. Such a multi-agent-based interactive system is termed a multi-agent system (MAS). At present, this multi-agent system has been widely applied in e-business, distributed information inquiry, parallel process, information publication, personal assistance, network management, computer-supported cooperative work, workflow control, etc.

Program mining provides the users with Active Service. It can customize application programs for users under their requests. It is a complex distributed application system, and is quite demanding in terms of system automation,

intelligence, and coordination among various modules. Therefore, the program mining process requires a management and control model of high automation and intelligence. Thanks to the development of intelligent agent technology and its wide application on the Internet, the required technical support has been provided for the development and implementation of program mining under network circumstances. To put it concretely, the agent technology can be applied in all processes of program mining, such as user requirements analyzing, component searching, automatic composing, and result validating. With the intelligence, autonomy, and mobility of agents, the program mining system can analyze and understand the computing requests of the user, rapidly and effectively search for the components, assemble these components automatically, and verify the program. In this way, with multi-agent interaction and collaboration, we can implement the collaboration among the modules of the program mining system, and smoothly complete the customization of program mining and active services.

In this chapter, we first introduce the intelligent agent technology, then the design and realization of the multi-agent system for program mining. We also present a detailed description of the respective agent, and the interactive protocol among agents. Finally, we introduce a Java-based Agent Running Environment (ARE).

9.1 INTELLIGENT AGENT

The agent technology is a newly developed software technology. It organically combines artificial intelligence with distributed computing. The agent can autonomously implement tasks on behalf of the user or other agents, and interact with the surrounding environment in appropriate modes.

There are three main features of agents: autonomy, intelligence, and mobility.

Autonomy means that agents can be consulted by the user—for example, when running a task, it can make suggestions and supporting advice to users, or even make decisions for users under authorization.

Intelligence refers to the agent's capability of acquiring related knowledge and applying the knowledge to solve the problem. The intelligence of agents varies. Some simple agents are no more than process flows. A complex intelligent agent can acquire some artificial-intelligence-based methods, such as ones for the deduction and learning of knowledge.

Mobility refers to whether agents can move among network nodes and fulfill the assigned functions. The migration of the agent enables it to move to the corresponding network node according to requirements, so as to obtain a more convenient and appropriate computing resource and information

resource. But the mobility of the agent will also increase system complexity and insecurity.

The agent mainly plays the role of helping or replacing the user to finish the entrusted tasks. Agents can be classified as interface agents, information agents, or task agents according to the different functions they perform.

Interface agents are to help or guide users to finish specific tasks. Through learning, it can adapt to the user's personal preference of a certain user, and run some frequently-used procedures automatically instead of the user.

Information agents are responsible for making intelligent searches on the Internet or distributed database to acquire user needed information.

The task agent can help users complete a specific task and make complicated decisions by means of planning, deduction, or learning in a specific domain.

In this section, we will first introduce the intelligence of the agent, including the representation, deduction, and learning of knowledge. Then, we present the architecture of agents, including agent management, directory service, agent communication, and software interface.

9.1.1 INTELLIGENCE OF THE AGENT

When we refer to intelligent agents, people will likely ask what is intelligence? As early as in 1950, Alan Turing, a British mathematician, put forward the famous Turing Test to judge whether a machine is intelligent. When a machine or a person can answer the same questions behind screens, and, after a while, if people cannot distinguish the machine from the person through the answers, we can safely conclude that the machine has human intelligence. Of course, intelligent agents do not necessarily fully pass the Turing test to show that they are intelligent. So long as they have considerable deduction and learning capability to help users accomplish certain tasks, that will be enough.

The intelligent agent is the result of the application of artificial intelligence in distributed computing. Since the 1960s, conventional artificial intelligence researchers have been committed to the research of knowledge representation, deduction, machine learning, etc. Knowledge is used to present the rules and facts in a certain domain, while deduction is used to make a true–false judgment of the proposition, on the basis of existing rules and facts, meanwhile, creating new rules with machine learning.

Each intelligent agent usually has a knowledge base. The knowledge base stores the relevant deductive rules and facts. When the agent perceives an event, the machine will make a deduction, according to the current status of agent, contexts of operation, and the rules in the knowledge base, and perform certain actions or give a corresponding response. Besides, some agents can, based on past operations, generate statistics as the parameters in

deduction, or directly generate some new deductive rules. That means agents have the capability of learning.

Knowledge representation is a basic problem in artificial intelligence research, because both deduction and learning are based on knowledge. There are many types of knowledge in the real world that need appropriate representation, such as various simple facts, complex relationships, mathematic formula, logic expressions, natural language grammars, correlation and inheritance among concepts, etc. Although natural languages can describe such knowledge very well and make people easily understood, they are not the best method as far as the computer is concerned, because natural languages are not, by nature, accurate and strict, and therefore unsuitable for machines to reason with. There is no omnipotent representation method for all the different types of knowledge, which not only can be well handled by the machine but also describes all knowledge. Therefore, according to the specific applications in different domains, we should select corresponding methods that can better describe a specific sort of knowledge. Generally speaking, knowledge can be represented using the following methods: Relation Representation Method, Hierarchy Representation Method, Predicate Logic Representation Method, and Program Interface Representation Method. In the selection and design of knowledge representation methods, we should take into account not only the knowledge's representation ability and processibility but also its extensibility and readability. Since the variety of knowledge representation methods will usually make it hard for co-sharing of knowledge among the intelligent application programs, a bridge connecting different knowledge representations is highly necessary, especially for such a multi-agent system, which often incorporates many different expert systems into collaborative work. The Knowledge Interchange Format (KIF) is designed for the interchange of knowledge among different agents.

How one makes use of the knowledge at hand to deduce and solve a problem is the concrete materialization of intelligence. The deduction means to reach a conclusion by reasoning according to the rules and facts. Deduction can be classified into forward deduction and backward deduction, in terms of deductive direction. Forward deduction draws out new truths from the existing ones on certain rules. Backward deduction makes a true–false judgment upon a proposition according to certain rules. Now, we take an example of forward deduction to explain the process of deduction.

Example 9.1 Deductive process of forward deduction

The Existing rules in the knowledge base are as follows:

1. If (num_wheels 2) and (motor no) then vehicleType cycle
2. If (num_wheels 2) and (motor yes) then vehicleType motocycle
3. If (num_wheels 4) and (motor yes) then vehicleType automobile

The known facts are as follows:

num_wheels = 4

motor = yes

num_doors = 3

size = medium

The deductive machine will judge whether each rule can be met according to the known facts. If true, a new fact will be generated.

As shown in the above example, known fact “num_wheels = 4; motor = yes” so the rule #3 is activated to deduce the new fact of “vehicleType = automobile.”

One of the important features of the intelligent agent is that it can adapt to the changing environment. However, no matter how complex the knowledge representation and deductive methods are, the agent cannot make appropriate adaptation to an unknown situation. Learning will enable the intelligent agent to keep obtaining new knowledge and adapting to the changing environment.

Learning can take the form of mechanical repetition of taught operations. Easy as the theory is, the functionality of the learning could be effective. The agent may learn about user behavior, and memorize their habitual operations, so as to facilitate user prospective application. Besides, by learning, the agent can perform the user's operation tirelessly all the time.

Another way of learning is based on the adjustment of parameters and weights according to the statistical figures. In such a way, we can make sure which parameters would definitely influence the decision-making, but we are not sure about the exact weight of each parameter. Learning can optimize the decision-making by continuously adjusting parameters. This method constitutes the foundation of neural network learning.

Induction is another learning method by which we can abstract a series of instances and then form a general rule. Both decisive tree and neural network can make inductions. They process input instances, acquire problem essence, and automatically convert them into internal knowledge forms.

Clustering is also an effective learning algorithm. By scanning obtained high-dimensional data samples, it creates classification standards on the basis of similarity. The clustered data samples are usually highly relevant in terms of features. Therefore, we can recognize the pattern of different data through clustering learning.

After long years of research, we have witnessed a remarkable development in the theory and technology of knowledge representation, knowledge deduction, and knowledge learning, some of which have come close to practical application. In the program mining system, we are able to make use of the existing agent technology to provide Internet users with Active Services.

These intelligent agents can apply present knowledge presentation, knowledge deduction, and learning methods to improve service capability to complete user request tasks. As for different applications, related agents will adopt different knowledge representations, deduction, and learning methods. For instance, if agents only need to respond to a simple situation, they may directly write the situations and corresponding processes into the program codes; if the agent has to answer questions, or generate new knowledge from the statistical data, we have to take the knowledge base and deduction ability into account. In the case of a complicated application system, if there are many kinds of knowledge representations, there will be a need for unified exchange formats similar to KIF for agents to share and exchange knowledge. If there is a necessity to adjust to surrounding environment, for instance to user operation preference, the learning capability of agents is needed.

9.1.2 ARCHITECTURE OF THE INTELLIGENT AGENT

To understand the use of the intelligent agent in the program mining system, it is necessary to be acquainted with the architecture of intelligent agents.

The architecture of the intelligent agent specifies the basic implementation framework of the agent and how to provide these functions, including defining the agent's mechanism of communication, management, directory service, interface service, etc. To ensure the interaction among heterogeneous agents, many international standardization organizations hammer at the standardization of agent systems. Of them, the most influential organizations are Foundation for Intelligent Physical Agent (FIPA) and Object Management Group (OMG). FIPA's work is mainly concerned with the overall structure of the agent system and interactive language among agents, while OMG emphasizes the migration mechanism of agents. In March 1999, the two organizations officially established a liaison agency to coordinate their work in agent standardization. Here, we give a brief explanation of the reference model of agent architecture proposed by FIPA.

Figure 9.1 shows the FIPA-proposed reference model of agent architecture. As shown in this figure, every agent runs on a supporting platform, and these platforms can exchange information. Each agent platform has an agent management system, directory service, and information transfer service.

The agent runs on the base of supplied services. The agent management system can manage agents and resources of the platforms. The directory service can provide the registration and agent inquiry service. The information transfer service can offer communication services among agents. The agent-based software can implement an advanced application in which agents provide the upper-layer software with intelligent and object-oriented service interfaces.

9.2 INTELLIGENT AGENT SYSTEM IN PROGRAM MINING

To provide users with Active Services, the program mining system needs to access and search the heterogeneous component warehouses distributed on the Internet and LANs, as well as realize the co-sharing and reuse of the component resources distributed in these component warehouses. In the process of program mining, it is necessary to make functional decomposition of user service requests, and make a judgment upon whether the service offered by the component can meet functional needs. If the services offered by the components can meet the demand of the user, the system can directly return the service functionality offered by the component to the user. Otherwise, the system will further the component searching and matching according to the service functions after further subdividing. After the relevant components are found, the system will compose, compile, validate, and test them. Finally, the system will submit the requested services to the user. Besides, the intelligent agent can also record the former cases and and learn them to increase its capability, no matter whether they are successful or not.

9.2.1 MULTI-AGENT COOPERATION MODEL

In Chapter 4, we have introduced the general process of program mining:

1. the user submitting computing requests;
2. the system analyzing user requirements and making a functional decomposition;
3. component searching and acquiring;
4. component analyzing, selecting, and composing;
5. validating the consistency of the composing program and the service required;
6. compiling and executing the mined program and offering services to the user.

To implement the program mining progress, the program mining system should set up relevant intelligent agents in the client and server, and organize them in accordance with a certain protocol to constitute a multi-agent system in support of program mining. Xia et al. (2003) propose and implement a multi-agent cooperation model for program mining.

This multi-agent system consists of the following agents:

• User Interface Agent (UIAgent) at the client side
• Task Management Agent (TMAgent) at the program mining server side
• Task Analysis Agent (TAAgent) at the program mining server side
• Component Retrieval Agent (CRAgent) at the program mining server side
• Composing and Validating Agent (CVAgent) at the program mining server side
• Domain Knowledge Agent (DKAgent) at the domain knowledge base side
• Directory Library Agent (DLAgent) at the component warehouse side
• Component Library Agent (CLAgent) at the component warehouse side.

Now, we briefly discuss the main functions of these agents.

• UIAgent. The UIAgent (User interface agent) is located at the client end. It interacts with, guides, and helps the user to put in program mining task, or in other words, accepts the user's computing requests actively. Then, it submits the computing requests to the program mining server and records the user's requests using history and characteristics. After program mining servers return mined components or component sets, it will provide the user with these components.
• TMAgent. The TMAgent (Task management agent) receives the computing requests from the UIAgent, and allocates the needed resources to

these requests. Meanwhile, the TMAgent is responsible for recording the status of each task, including the execution status and result of the task. Here, we term every single computing request from the user as a task.

• Task Analysis Agent (TAAgent). The task analysis agent is responsible for user requirement analysis and corresponding function decomposition. We term functions that cannot be further subdivided as primitive functions, which corresponds to a service function provided by a single component. Here, we should note that, due to the heterogeneity of components and the diversity of developers, it is inevitable to witness a component whose functions contain another component's functions, or the functional intersection with another component. It thus demands that the TAAgent should be equipped with the capability of partitioning primitive functions and recording the partition process and history. Before decomposing of primitive functions, the task analysis agent demands that the domain knowledge agent supply the classification information about the relevant components in the component warehouse, as well as the component's service functions. After the task analysis agent decomposes the user requirements into a group of primitive functions, it will transfer the primitive function requests to the component retrieval agent.
• Component Retrieval Agent (CRAgent). The component retrieval agent is a movable agent, which is used to search and acquire the components that can meet the required primitive functions from the distributed component warehouses or local ones. It has two functions:
  1. Accept requests from the task analysis agent and acquire the component resource information from the component directory library, or, according to the component resource information, move to the corresponding component warehouse, and query and acquire the component entity.
  2. Accept the request of the component directory library agent, search in the stored component information in each component warehouse, and update the component resource information in the component directory library.
• Composing and Validating Agent (CVAgent). When the component retrieval agent has found the needed component, it transfers the component's information to the CVAgent. The CVAgent, according to the user requirements and the Component Composing scheme, composes the components into an application program that can offer the service required by the user, and then validates its consistency. Finally, the CVAgent compiles and runs the composed and validated application program to offers active service for the user.

• Domain Knowledge Agent (DKAgent). The DKAgent accepts the request from the TAAgent and sends back the relevant domain knowledge and component service function to the TAAgent after searching the domain knowledge base. The domain knowledge includes the domain classification information and the function sets information in the domain. In addition, the domain knowledge agent is responsible for updating the domain knowledge base.
• Directory Library Agent (DLAgent). The DLAgent accepts the request from the CRAgent, and, after querying the component directory library, sends back the relevant component resource location information to the CRAgent for the component searching. Besides, it also accepts the component resource's update information obtained from the search engine agent, and maintains and updates the component's resource information.
• Component Library Agent (CLAgent). The CLAgent accepts the request from the component retrieval agent, and, after querying the component warehouse, sends the relevant component information and component entity to the component retrieval agent. Meanwhile, the CLAgent is also responsible for the management and maintenance of the components in the warehouse, including the addition, deletion, or modification of the components.

The collaborative work relationship among the above agents in the mining system are shown in Figure 9.2.

In Figure 9.2, the user interface agent is set at the client to complete interactive functions with the user. Other agents are located in the component management server, component directory library, component warehouse, etc. Since the intelligent multi-agent system is an Internet-based distributed computing system, the locations of these intelligent agents in the abovementioned servers, directory library, or component warehouse have relative and changing positions.

The communication between different agents is directed by the protocol connecting them. Figure 9.3 indicates the protocol link relations among these intelligent agents. As shown in Figure 9.3, the connective protocol between the UIAgent and TMAgent is UITM. Moreover, the connective protocol between the TMAgent and task analysis agent is TMTA, the UIAgent and task analysis agent, UITA, the task analysis agent and domain knowledge agent, TADK, the task analysis agent and component retrieval agent, TACR, the task analysis agent and composing and validating agent, TACV, the component retrieval agent and directory library agent, CRDL, and the component retrieval agent and component warehouse agent, CRCL.

These protocols define the information interactive rules, formats and orders among intelligent agents. The interactive messages are described by the relevant agent communication languages.

9.2.2 AGENT FUNCTION DESIGN

In this section, we give an introduction to the function designs of agents, because the functions each intelligent agent is about to fulfill depend on the system designer's allocation of each agent's tasks, and on the functionality and supporting environments of the selected intelligent agent platform. The functional design of the UIAgent is illustrated as an example.

Eample 9.2 The function design of the UIAgent

As stated, UIAgents are mainly used to help and guide the user to accomplish program mining. The UIAgent, by means of learning, will adapt to the user's preference, and automatically run some commonly used procedures. Generally speaking, the UIAgent adopts four approaches to learning:

1. observing the user's operations and conducting imitation learning;
2. making suggestions to the user, or executing operations on behalf of the users, then learning and adjusting itself through receiving the feedback or evaluation from the user;
3. directly accepting the user's commands and then learning and recording relevant operating flows;
4. consulting other agents for their experience.

With such a broad learning mechanism, the interface agent can offer users personalized interaction interfaces to customize users' own interaction styles. Besides, interface agents can co-share the knowledge by bilateral collaboration. When a user customizes or modifies an application service with the help of the program mining system, the UIAgent can learn and remember this procedure and lay a foundation for other users to share the service in future.

Figure 9.4 illustrates the module structure of the UIAgent, which consists of the sensor module, reasoning machine, communication module, knowledge base, database, controller, and effect module. Users submit computing service requests through the input/output interface. When the sensor module receives the user's computing service requests, it will send messages to the reasoning machine, which analyzes the sensed events according to the rules in the knowledge base and the statistical data in the database. Then, the reasoning machine will decide the subsequent actions in accordance with the analysis result. Particularly, if an event has been input by a user, the application result of this event will serve as a reference for future handling of the user's input. Similarly, when the same user has been using the agent for a while, the UIAgent is supposed to memorize the user's input habit and character, such as the frequently used input modes or frequently requested services.

Therefore, once the sensor module perceives that one user's input can match the related habit or character, the reasoning machine can instantly confirm the user requested services, and start corresponding, subsequent acts. The acts are sent to the controller, which will trigger them in some arranged sequence. The controller executes the acts according to their concrete contents, which ranges from sending messages to other agents, generating new rules and putting them into the knowledge base, recording the latest statistical data, or outputting information through the effect module.

The UIAgent can intercommunicate with other agents through communication modules. As shown in Figure 9.3, the communication objects of the UIAgent are the TMAgent and TAAgent. The communication protocol and message will be elaborated in Section 9.3.

9.3 AGENT INTERACTION LANGUAGE AND PROTOCOL

9.3.1 AGENT INTERACTION LANGUAGE

The agent interaction protocol prescribes the rules, sequence, and formats of agent communication. The agent interaction language is used to describe the

messages among agents. Different from the messages transmitted by other protocols, messages of the intelligent agents contain three basic elements: the agent interaction language, the universal format of message content, and the ontology defined among the agents for mutual understanding.

XML can be used to describe the messages exchanged between agents. An example of a message format defined by XML is as follows:

Example 9.3 The common format of message described by XML

Each message has a sender, and one or more receivers. The “content” in a message corresponds to the concrete content sent in the message.

The “ontology” in a message refers to the commonly understood terms by the intercommunicating agents. It is a description of some terms contained in the content, such as objects, methods, etc.

For example “<content> <Domain name=“car”>…</Domain> </content>” contains a domain object named car. Domain is an ontology understood by multi-agents. The definition is given as follows:

Example 9.4 Domain's definition in ontology

Example 9.5 The XML description of the message “Request Service” to the TMAgent, sent by the UIAgent

9.3.2 AGENT INTERACTION PROTOCOL

This section is concerned with the agent's interaction protocol. Because the agent interaction protocols between intelligent agents depends on the task classification of each agent and functional interrelationship between agents, and also because there is little difference between interaction protocols themselves, we only specify UITM the interaction protocol between the UIAgent and TMAgent.

Figure 9.5 is the state transition of a UIAgent in UITM. Figure 9.6 is the state transition of the TMAgent in UITM. In the figures, the state of the agent is indicated by an ellipse. The arrow refers to the target directions of the state transition. The notes above the arrow with “+” indicate the received message during the state transition, and indicate the sent message with “-” below the line.

As shown in Figure 9.5, in the whole interaction process of the UTIM protocol, the UIAgent should undergo six states: INITIAL, WAIT, SENT-1, SENT-2, DELAY, and FAIL. The UIAgent's state transition is triggered by sending or receiving of the message. Initially, the UIAgent is in state INITIAL. When the user inputs the request, the UIAgent packs it into the message “Request Service” and sends it to the TMAgent, meanwhile shifting the current state to SENT-1. If the TMAgent is busy, it answers “NCK”. Then, the UIAgent changes to state DELAY, and resends the message “Request Service” after a while, shifting to state SENT-2. If TMAgent replies “NCK” for two

successive times, the UIAgent will shift to state FAIL, reporting to the user that this task fails and then returning to state INITIAL automatically. If the UIAgent, in state SENT-1 or SENT-2, receives “ACK” from the TMAgent, it means that the TMAgent has accepted “Request Service.” In turn, the UIAgent will send “RSP” to the TMAgent, requesting the TMAgent to process “Request Service” and shifting to state WAIT. When the program mining server returns mined components or component sets, it is up to the TMAgent to send “AWAKE” to UIAgent, which is then awakened and shifts its status to state INITIAL, submits the mining results to the user, and starts to accept the next request service.

Figure 9.6 is a state transition of the TMAgent in the UITM protocol. In the beginning the TMAgent is in state INITIAL. When receiving the “Request Service” message from the UIAgent, TMAgent will decide whether to accept this request of service or not, according to its service type, current resource status, etc. If it has been declined, the TMAgent will answer a “NCK” and return to state INITIAL, waiting for the next service request. If accepted, the TMAgent will answer “ACK,” shifting to state READY. After receiving the UIAgent's message “RSP,” the TMAgent will go into state “PROCESS” and work with other agents to jointly process the service request of the “Request Service” message. When it is done, the TMAgent sends a “AWAKE” to the UIAgent to awaken it for corresponding processing. Then, the TMAgent returns to state INITIAL.

As mentioned, we use XML to describe the messages among agents. The following is a description of messages in interactions between the UIAgent and TMAgent.

1. Message “Request Service”. The message “Request Service” is sent by the UIAgent to TMAgent for the submission of user requests. The message is described as in Section 9.3.1.
2. Message “NCK”. The “NCK” message is sent by the TMAgent, indicating that it is too busy to respond to the “Request Service” message temporarily.
   
   
3. Message “ACK”. The “ACK” message is sent by the TMAgent, indicating that it has accepted the “Request Service” from the UIAgent and started to jointly process this request by coordinating with other agents.
   
   
   
4. Message “RCV”. The “RCV” message is sent by the UIAgent, indicating that it has already received “ACK/NCK”, and started corresponding processing.
   
5. Message “Awake”. When the TMAgent has mined the required service of “Request Service,” or when the TMAgent needs further interaction with the user in the process of processing, it will send the message “Awake” to the UIAgent, which is then awakened and provides the results of mining to the user or starts other interactive work.

9.4 ARE—THE AGENT RUNNING ENVIRONMENT IN PROGRAM MINING

In Section 9.2 of this chapter, we presented a multi-agent cooperation model in the program mining system. In this model, intelligent agents are introduced to each process step of program mining. The intelligent agent can help complete the tasks of user requirement input and analysis, component search, and assembling, so as to improve the automation of the whole process of program mining and to better meet the requirements of Active Service for the user.

The agent running environment is indispensable to the running and cooperative work of agents. In this section, we introduce ARE, the Agent Running Environment in Program Mining. Then, we also illustrate the implementation of the multi-agent system on the ARE platform as well as a design model of the program mining agent.

9.4.1 SERVICE FUNCTIONS OF ARE

ARE is a Java-based running platform. It applies the Java language owing to the fact that it may facilitate the trans-platform migration of the agent.

ARE is an enhanced platform on the basis of the Ki platform. Ki has functions such as agent migration mechanism, persistence mechanism, and RMI-based communication mechanism. On the basis of Ki, ARE introduces Java Agent Services (JAS) package, which offers an agent system interface API conforming to the criteria of FIPA. Through the integration between Ki and JAS, ARE has the agent naming system, directory service mechanism, and communication mechanism, all of which conform to the standards of FIPA.

In the process of program mining, in order to support the cooperative operations of various agents, ARE supplies the following services: Agent management Service, Agent Directory Service, Agent Communication Service, Agent Persistence Service, Agent Mobile Service, and Agent Security Service. The purpose is to provide the necessary resources and services in the establishment, start-up, running, motion, and communication of agents, as shown in Figure 9.7. The services provided by ARE are as follows:

1. Agent management service. It is responsible for the management of all agents in the running environment. It maintains two registration forms of the agents in the process of agent management. One is responsible for saving the registration of the agents created in the local environment, while the other for saving the registration of the agents running in the ARE. With the help of these two registration forms, ARE can management the local agents in a unified manner, as well as the agents
   
   
   from other running environments, supervise the running of agents and their interaction, and make a proper process to all exceptional situations. What is more, agent management also covers the functions of loading, unloading, interrupting, and restoring the agent's running, sequentializing, and unsequentializing agent. By means of agent management service, ARE can control the life process of each agent and manage the local resources.
2. Agent directory service. It supplies agents with name registration and agent searching services, and establishes mapping relations between agent logical name and physical address. The agent directory service can provide address information for the communication between agents and management of agents. It will also help to dynamically track down the activity of each agent.
3. Agent communication service. It is responsible for agent communications, providing a unified means of exchanging messages and knowledge among agents. The agent communication service is the foundation of collaboration among agents. On the ARE platform, the communication between agents is based on the asynchronous message delivery. By means of exchanging messages, agents can realize the co-sharing of information. ARE also supports agent communication between the local and remote environment, and allows agents to keep contact with other agents in the mobile process.
4. Agent security service. The agent security service includes two aspects. One is the security of the ARE itself, including the protection from malicious exhaustion of resources or the protection agents from hostile agent's influence in ARE. Another is the security of the agent, mainly referring to the integrity and security of agent codes; in other words, the agent's codes are not subject to modification during the running or migration, and the data carried by agents are protected, so as not to be illegally accessed. The ARE of program mining adopts a credit mechanism to cope with these security problems. It classifies the resources according to the access level of the agent, to limit malicious access to the local resource. As for the security of the agent itself, it adopts the digital signature method to test the integrity of the agent code and the carried data before and after the running of agent, and records malicious interpolation to the data, and thereby to some extent guarantees the security of agents.
5. Agent persistence service. The agent persistence service refers to persistently storing some information, including the codes of the agent and the running status of agents, and the restoration of such information when needed. The main purpose of this service is to ensure that, in case the host computer that provides ARE restarts up or collapses, the agent can be restored to the status before the collapse. The ARE of program
   
   mining adopts the checkpoint mechanism to implement the persistent service of the agent.
6. Agent migration service. When the agent is to migrate between the component servers in order to fulfill the component searching task, it proposes the request to ARE first. Then, ARE records the current running status of the agent and transfers the agent to the running environment of the target host, resuming the running of the agent. The whole process of agent migration is initiated by the migration agent and accomplished by ARE.

The aforementioned services provided by the ARE of program mining exchange system information through message channels, cooperating with each other, which provides conditions for the normal running of agents. In the following, we take agent migration service and agent persistence service as examples to illustrate the concrete implementation of these major services in ARE.

1. Agent Migration Service.

Agent migration service implements the autonomous migration function of the agent. In the program mining process, the migration of the agent is autonomously initiated by the agent. ARE is responsible for saving the current status of the agent and the related resource files, establishing connection with the target host's ARE, transferring the agent's resource files, codes, and data to the target host, activating this agent in the target host, and resuming its running process. Since the network connection or communication might have problems in the process of agent migration, it is necessary to introduce relay transmission and a reliable transmission mechanism to ensure the reliability and safety of agent migration. The detailed process of agent's migration in ARE is illustrated in Figure 9.8.

As shown in Figure 9.8, the autonomous migration of the agent in ARE includes the following seven steps:

1. At first, the agent should send a migration request to ARE, when it needs to migrate.
2. The ARE temporarily suspends the running program of the agent when receiving the request of the agent for migration, and makes necessary preparations for the migration of the agent.
3. The local ARE moves the agent to the target agent running environment.
4. The target ARE resumes the program that is suspended when receiving the migrating agent, and thus enables the agent to resume the task.
5. If the migrated agent is resumed successfully, then an OK message will be sent to the former ARE; otherwise, a failure message will be sent instead.
6. If the agent migration is successful, the duplicate of the agent in the original ARE will be removed; otherwise, the request of re-migration will be sent instead.
7. The current position of the migrated agent will be reported to its home ARE.

The migration process of the agent between hosts is actually the migration between two AREs, respectively provided by the two hosts. The ARE of the initiator of migration is responsible for packing and sending the program codes and data files of an agent; the receiving ARE is responsible for collecting these files, activating, and restoring the running of the agent. ARE implements the sending and receiving of agent through five ports. as shown in Figure 9.9.

1. requestToSend. The requestToSend port is the port invoked by the sender, which passes the identification of the agent waiting for migration and the reference of the receiver's ARE, by calling the port. The receiver decides whether to accept this agent or not according to the identification of the agent. If it decides to receive the agent, the receiver

calls back the interface provided by the sender via the reference of the sender's ARE, and activates the transfer process of the agent.

1. beginTransfer. The beginTransfer port is the port called back by the receiver. If the receiver agrees to accept this agent, it uses this port to tell the sender preparing for the transmission.
2. transferResource. The transferResource port is another port called back by the receiver, by which the resource files needed to be sent are returned to the receiver as a result.
3. transferData. Similar to the transferResource port, the receiver obtains the agent's attributes, data, and other needed information by calling the port transferData.
4. endTransfer. When the receiver has received all resource and data, it uses the endTransfer port to inform the receiving agent to end the transmission.

During the transferring process of resource files and data of agents, some functions, such as relay transmission and transmission confirmation, are implemented in the interface methods of transferResource and transferData.

2. Agent Persistence Service.

The persistence mechanism of the agent is to serialize the ARE and save its backup in the persistent storage, in case of resuming the data in an emergent situation, and thus ensure the persistence of agent.

In the agent management system of ARE, the Checkpoint mechanism is adopted. This mechanism resembles the serializing function of Java. It will serialize all agent codes and data on the agent platforms at regular intervals to form temporary files and save them in hard disks. When the restoration is needed, it will simply recover from the serialized data on the hard disks to rebuild the agents. The working process of the Checkpoint mechanism is illustrated in Figure 9.10.

Process of saving:

1. The timer periodically sends the message of the need-setting checkpoints.
2. After the agent management system receives the request of the serialized agent, it saves the current status of the agent platform.
3. The running agents are stopped in turn. Then, the agents are serialized. Corresponding files are created and saved on the hard disc.

Process of restoration:

1. Once the agent platform is destroyed accidentally, the restoration process, is activated.
2. The normal agent platform is started up, and the latest running status of ARE is resumed.
3. Select the latest serializing version, and all agents are loaded to the memory.
4. Start up the serialized agents in turn.

9.4.2 AGENT DESIGN IN ARE

ARE defines a unified agent design model and provides such functions as agent management service, directory service, and communication service, which provides necessary resources, and services for the agent's establishment, start-up, running, migration, and communication. Thus, each intelligent agent in the program mining system, so long as it is designed according to the universal model defined by ARE, can make use of ARE's services to communicate, co-share information, and cooperate with each other. If necessary, it can migrate autonomously among AREs. This makes it possible that, when designing and implementing the program mining system, we only need to consider the specific tasks the agents need to fulfill, instead of involving in other system functions, such as agent interaction, migration, and status saving. Thus, the complexity of system implementation is substantially simplified.

As for the concrete implementation of agents, all agents have a set of universal interfaces, by which agents can interact with ARE and utilize all services provided by ARE. The design of agents adopts the object-oriented design method. First, we define an abstract class RootAgent. By means of defining a number of abstract methods to regulate universal interfaces for all agents, the definition of every agent should inherit this class, realizing the defined method in its abstract interfaces.

The abstract methods defined in the RootAgent are as follows.

Besides the aforementioned standard methods, the agent, according to different tasks, can implement different main methods and specific message processing methods.

In ARE, each agent is established in a uniform mode through its inheritance of the abstract class of RootAgent. All agents have the same life cycle, including the seven states of initialing, running, idling, suspending, migrating, serializing, and ending. Transition among different states is triggered by

different events. The agent's life cycle and its status shift are illustrated in Figure 9.11. The agent is loaded to the memory by class loader in ARE to run the initializing method, establish the initial data structure, and then it enters the “initial” state. The agent in this state, after receiving the event “start-up,” starts the main process of the agent, and enters the “running” state. In the running state, according to the requirements of the task schedule, the agent can suspend the running and enter the “suspension” state. Whenever it receives a “resume” indication, it will wake up and resume running. After the agent completes all assigned tasks, it will enter the “idle” state, in which the agent can receive messages from the ARE or other agents or return to active states. When in the “running” state, the agents may be stopped by the ARE, execute the Terminate method, release occupied resources, and terminate local running of the agent. If the agent needs to migrate to other hosts and continues its running, it sends request to the ARE; then, the ARE serializes the agent asking for migration and saves all its attribute values. The agent then transits from the “running” to the “migrating” state. The class files and state information of the agent are sent to the target host's ARE through the network. The receiver reconstructs the agent based on the class files of the agent, restores its attribute values, and makes the agent re-enter the running state.

The abstract class RootAgent provides agents in the program mining system with a unified design model. To facilitate agent communications and agent management, it is necessary to set up a naming mechanism to uniquely identify the agents in different AREs. In the program mining agent system, the name of the agent is composed of the name of the ARE plus a

unique string of characters in the local ARE. When an agent is created, there is an initial module which is called HAD (Home Agent Dock). The name HAD plus the initial name of the agent constitutes the unique identification of the agent. If there is more than one instance of the same agent running simultaneously, adding the process ID to the original identification makes the name of the agent. The concrete format is as follows:

<name><progress ID>@<hostname>

Since the HAD of each agent is designated, the agent should register its destination to its HAD before migration. During the communication of agents, the HAD of an agent can serve as a relay station of messages, disregarding the current locations of the agents. Since messages can be forwarded via HAD, the location-transparent communication in the process of agent migration can be realized.

To sum up, the ARE can support services of agent communication, agent management, and agent migration, and provides an agent design method. Based on these system services provided by ARE, we develop a MAS used for program mining, realizing the functional design of agents in program mining, and thereby laying a foundation for implementing a prototype program mining system. In the next chapter, we will elaborate on the prototype system and application examples of program mining, together with the MAS.

REFERENCES

Aalst, W. V. (1996). Structural characterizations of sound workflow nets. Technical Report Computing Science Report 96/23, Eindhoven University of Technology, The Netherlands,

Aalst, W. V. (1997). Verification of workflow nets. In Application and Theory of Petri nets 1997. 18th International Conference Proceedings, LNCS 1248. (pp. 407–426) Springer-Verlag.

Aalst, W. V. (1999). Introrganizational workflows—an approach based on message sequence charts and Petri nets. System Analysis-Modeling-Simulation, 34(3), 335–367.

Cugola, G., Ghzzi, C., Picco, G. P., and Vigna, G. (1997). Analyzing mobile code Languages. Mobile object system. Lecture Notes in Computer Science, 1222, 94–109.

Decker, K., Pannu, A., Sycara, K., and Williamson, M. (1997). Designing behaviors for information agents. In Proc. Autonomous Agents 97. (pp. 404–413) ACM Press.

Finin, T., Labrou, Y., and Mayfield, J. (1997). KQML as an agent communication language. Software Agents, MIT Press.

FIPA Abstract Architecture Specification. (2003).http://www.fipa.org/specs/fipa00020/

FIPA ACL Message Representation in Bit-Efficient Encoding Specification (2003).http://www.fipa.org/specs/fipa00069/

FIPA ACL Message Representation in String Specification (2000). Foundation for intelligent physical agents, from http://www.fipa.org/specs/fipa00070/

FIPA ACL Message Representation in XML Specification (2003). http://www.fipa.org/specs/fipa00071/

FIPA Agent Management Specification. Foundation for Intelligent Physical Agents (2000).http://www.fipa.org/specs/fipa00023/

FIPA Agent Management Specification (2003). http://www.fipa.org/specs/fipa00023/

FIPA Agent Management Specification (2003). http://www.fipa.org/specs/fipa00086/ Genesereth, M. (1997). An agent-based framework for interoperability (pp. 317–345). Software Agents, AAAI Press.

Java Agent Services-An Introduction (2000). http://www.java-agent.org/JAS_Intro.htm Lesser, V., Horling, B., Klassner, F., Thomas, A. R., Shelley, W., and Zhang, X. Q. (1998). A Next Generation Information Gathering Agent. UMass Computer Science Technical Report 1998-72.

Maes, P. (1994). Agents that reduce work and information overload. Communications of the ACM, 37(7), 31–40.

Milojicic, D. S., Laforge, W., and Chauhan, D. (1998). Mobile objects and agents (MOA). Distributed System Engineering, 5, 214–227.

Mobile Agent Facility formal specification.OGM. http://www.omg.org/cgi-bin/apps/doc?formal/00-01-02.pdf

Patil, R. S., Fikes, R. E., Patel, S. P. F., Mc K. D., Finin, T., Gruber, T., and Neches, R.(1992). The DARPA knowledge sharing effort: progress report. Proc. of the third Conf. On Principles of Knowledge Representation and Reasoning, Cambridge, MA (pp. 103–114). IEEE (IEEE Press).

Petrie, C. J. (1996). Agent-based engineering, the Web, and Intelligence. IEEE Expert. December.

RMI. http://java.sun.com/products/jdk/rmi/index.html

Russell, S., and Norvig, P. (1995). Artificial intelligence: a modern approach. Englewood Cliffs, NJ: Prentice Hall.

Searle, J. R. (1969). Speech acts. Cambridge: Cambridge University Press.

Shi, Z. Z. (2000). Agent and its applications. Beijing: Science Press.

Silva, L. M., Simoes, P., et al. (1999). JAMES: a platform of mobile agents for the management of telecommunication networks. Proc. IATA'99, Intelligent Agents for Telecommunication Applications. Stockholm, Sweden, August.

Tao, X. P., Lu, J., et al. (1999). Mobile agent: a future distributed computing mode. Computer Science, 26(2), 1–6.

Verbeek, H., Basten, T., and Aalst, W. V. (1999). Diagnosing workflow processes using Woflan. Technical Report 99/02, Department of Math and Comp Sci, Eindhoven University of Technology, The Netherlands.

Welcome to Ki for JavaWorld. http://dianacpsunizares/banares/IC/work/ki/,1998-10-16.

Wong, J. S. K., and Miker, A. R. (1999). Intelligent mobile agents in large distributed autonomous cooperative systems. The Journal of Systems and Software, 47, 75–87.

Xia, D. L., Zhang, Y. X., and Fang, C. H. (2003). Design and Implementation of an agent-based program mining system. Chinese Journal of Electronic, 31(5), 793–796.