KODAMA: as a distributed multi-agent system

KODAMA: As a Distributed Multi-agent System Guoqiang Zhong, Kenichi Takahashi, Tarek Helmy, Kouichirou Takaki Tsunenori Mine, Shigeru Kusakabe and Makoto Amamiya Graduate School of Information Science and Electrical Engineering, Kyushu University 6-1 Kasuga-Koen, Kasuga, Fukuoka 816, Japan {zhong, tkenichi, helmy, ktakaki, mine, kusakabe, amamiya) @al.is.kyushu-u.ac.jp Abstract

no solid, centralized, or monolithic system would be adequate [3]. From the agents’ point of view, they are required to act as “open” agents that they can: + Percept current environment by themselves. + Interact with other agents that “live” anywhere in the network. + Try to contribute their capabilities for solving the given problem. Due to the heterogeneous and open environment, as the Internet is, agents (usually residing on anywhere in the Internet) need to exchange various kinds of information. Thus, an efficient and reasonable scheme of collaboration among agents is clearly indispensable. So far, a lot of efforts have been devoted to developing a new approach of agent communication, and KODAMA system is actually distinct from its precedents because it has a new application-independent layer called “Agent Communication Zone” (ACZ). It is important to note that ACZ itself is naturally distributed to every computer where might have KODAMA agents. That means, from each agent’s point of view, the agent always talks with a local ACZ, which acts like a gateway or proxy of agent because any exchanged information is either coming from or sending to the local ACZ. From all ACZs’ point of view, they work together to form a unified virtual “Agent Communication Zones” where agents can talk with each other freely. With the help of ACZs, the low-level implementation details of agent communication and agent categorization have been successfully hidden from each individual agent. As a result, every agent can be kept simpler without weakening its cooperative ability. The aim of this paper is to present the design and application of the KODAMA system. In the following sections, we will first introduce the agent architecture and the organization of KODAMA system as a whole, and then, focus on our new solution of the agent communication, especially discusses the ACZ in an application-independent way. In addition, a practical application example is also presented.

With the explosion of the Internet, we are evolving a worldwide network computing environment. A t this point, the surged challenge is the next evolutionary technology for the Internet-oriented applications. A KODAMA (Kyushu university Open & Distributed Autonomous Multi-Agent) system is deployed for this demand. KODAMA system can interconnect disparate and distributed agents together to solve some problem whose solution is typically beyond any singular agent S capabilities. The key aspects of KODAMA agents are their autonomy, collaboration, flexibility, as well a s stability. To obtain all these features, appropriate scheme of collaboration among agents is clearly critical. Our new approach focuses on both raising the level of abstraction at which agents cooperate with each other, and hiding the implementation details of communications from agents.

1. Introduction Multi-agent approach has recently become popular in mainstream computing because they are sensible for problems that are inherently distributed (either physically or geographically) [ 5 ] . As a distributed and autonomous multi-agent system designed for Internet applications, the core concept of KODAMA is that an individual agent can be distributed over a network of computers, yet still work together to do cooperative tasks. The intelligent behavior and efficiency of KODAMA system are basically emergent from the distribution of overall task and the cooperation within agent communities. In other words, KODAMA agents are able to choose rational actions based on their own percept of environment as well as appropriate interactions with other agents. Note that, from both hardware and software perspectives, the Internet is naturally distributed, large-scale and dynamic. Therefore

435 0-7695-0571-6/00 $10.000 2000 IEEE

2. The framework of KODAMA As figure 1 depicts, a KODAMA agent has a clearly defined modular architecture with a pool of general components whose capabilities can be easily set up in different ways. Each component effectively encapsulates the functionality and data of an object while respecting common conventions to facilitate interoperability. The set of components is extensible, that is, agents may choose to use new components if they can agree on the intercomponent relationships. By doing so, we can easily facilitate code reuse and extend our agent system’s capability by providing additional components. In addition, the domain-dependent behavior relevant to different agents could be independently defined at the time of actual implementation. To make this separation more explicit, we can also say that an agent consists of two units. One is called a kernel unir, which encapsulates agent-level issues. Another is called an applicationoriented unir,which encapsulates domain-level issues.

+

+

+

A-(

Compmma

Inrormrrim

+

Figure 1. The framework of KODAMA agent Although the available components for KODAMA agents are open to be extended, the main components of a typical agent is described as the following: + Context: acts as a facilitator in one agent. It has, for example, a full link with “communication”. Hence, other components in the agent can simply send data to or receive data from “context” while exchanging data with outside agents. It also keeps the fresh data about agent current status. + Reasoning: searches for solutions to the incoming problems and resolves any possible conflicts. If this

436

agent does not have enough knowledge (or resources) for a certain problem, it would require for social interaction with other agents to reach a set of rational solutions. Furthermore, it only gives up certain goals when either that the agent cannot achieve it or that it is no longer necessary. The knowledge for reasoning is stored in “agent policy” whose content can be improved through agent learning. Learning: improves agent’s overall performance after its execution through self-learning. It utilizes classical machine learning techniques to multi-agent systems. The main problem here is that an agent has to deal with its limited view of the interaction between its own activities and those of other agents. In order to solve this problem, reinforcement learning is employed because it enables agent to learn through trial-anderror interaction with an open environment. The utility functions should cover at least the agent local capabilities as well as its interaction abilities. Its raw learning material comes from “feedback’ and “temporary problem”, and it will try to enhance the “agent policy” after learning. Log: provides generic methods to keep a history recorder of an agent. It is worth noting that history size has a great effect on system performance. Intuitively, adding more memories to agents does make the system perform better on average, but at some point those memories can be too old to use. Log also provides methods to renew, retrieve and analyze the agent’s trial history. The most frequently accessed information is extracted out and forms a “cache” of agent action history, which is expected to speed up reasoning time. Communication: enables communication among agents (which can stay in one site or on a remote site) with respecting to common extensible interface of ACL. Extensible means that whenever it is necessary, agents can adapt to any change of interface or new interface. In short, it makes agent to be a certain ACL speaker and listener. Security manager: protects our agents (and the hosts on which agents execute) from both unauthorized access and malfunction of other agents. In an open and distributed environment, the protection of data and resources that carry data involves a couple of areas, such as, agent identification, resource permission, against network hostility and so on. Whenever it is necessary, agents can also be protected by encrypting agent data before transmission. Its main task is to ensure the robustness of the agent system. The security model of Java 2 is policy-based, that is, Java 2 separates out the actual permission specifics from the runtime code. Thus, security manager can define resource- access permissions of users via an external

4

policy file. Default permissions may also be configured and assigned to even unknown users. Problem solver: isolates application level behaviors from agent level ones, which are relatively common. It is natural that this component is more sensitive to different application than other components. Obviously, it is the main part of agent’s application oriented unit. After its execution, the result is sent to the “context”, whereas the feedback information is sent “leaming”.

agents are in charge of a certain kind of task, and tend to talk with agents within local domain more often than other outside agents. The top-level domain is called “root”, and all other agent domains are extended from “root” directly or indirectly. By doing so, the location of any agent in the system can be specified from “root”.

4. Agent communication Interaction among agents is one of distinguished properties of multi-agent systems (like KODAMA). Agent communications are kind of interactions that respect the heterogeneity and preserve the autonomy of agents [7]. This is largely due to this fact that the solution to the system’s task is typically beyond any singular agent’s capabilities. Rather, the task solving process can be an incremental process that involves coordination among agents. Coordination among agents is basically decentralized and heterogeneous because they can reside on anywhere over the network. Agent can even, for instance, dynamically enter or leave the system. This makes it difficult to maintain consistency across the system.

3. Agent domain structure of KODAMA In KODAMA system, both agents and data are distributed and dynamic. While considering the overall structure of the KODAMA system, we note that the main challenges are coming from the following facts: The Intemet itself is naturally distributed, large-scale, heterogeneous and dynamic. So that, no solid, centralized, or monolithic system would be adequate. KODAMA agents may reside on anywhere over the Internet, and they need to exchange various kinds of information. Some intelligent behaviors of agent are based on its appropriate cooperation with others within agent community. [8] None of the communication protocol can be universally available and suitable. In fact, several communication protocols should be supported respectively. Agents can be created, deleted or moved dynamically. That is, the community of agents is scalable. It is desirable that the communication volume does not grow exponentially after the increasing of agents.

LOW Level

Figure 3: Hierarchical view of agent communication

0

In most cases, agents would exchange various kinds of information, which are ranged from simple message passing to structured conversations. Depending on the application of a multi-agent system, the underlying agent interaction mechanism might need to support point-topoint messages passing between agents, broadcast messages to the entire agent community, or to a specific groups of participating agents. Our new approach and its Java implementation of agent communication are based on four hierarchical layers, as shown in figure 3. From high level to low level, the hierarchical structure consists of: KODAMA agents (who speaking in a certain agent communication language), ACZ (Agent Communication Zone), network connection protocols and implementations, Java virtual machine (Java VM). This four-layer view helps us to understand core concepts of agents’ interactions quite clearly. Thus, we can design its implementation in a more flexible, efficient, and robust

A n A s O O ~ u

Figure 2: An example of “agent domain” structure

In order to make it more efficient and easier for agents to communicate with each other, all agents in KODAMA system are organized by a hierarchical “agent domain” structure (see Figure 2). For agents they are categorized to various agent domains based on their own facilities. Note that, it is possible for an agent to join more than two different domains if it can do several different jobs. For agent domains, they consist of a number of distributed agents with a close relationship. In particular, those

437

Another consideration is that the design of ACZ should be open, so that, it can be independently extended, updated or modified according to the practical communication needs of the system. For instance, the support of a new ACL or network connection protocol can be added to the ACZ. To a large extend, ACZ can help our KODAMA system to interact with agents created by other research groups, taking full advantage of flexibility through the network.

way. Java VM comes to the lowest level because the KODAMA system is currently implemented in the Java language. Once a number of Java VMs can interact with one another, we can raise the abstraction level up to a higher coordination level in which social interaction is allowable. And the rest of three layers will be fully discussed in the following sections.

4.1. Agent communication language layer In a KODAMA system, agent communication can be modeled as the exchange of declarative statements. The salient feature of the declarative language used by agents is its expressiveness because it allows agents to communicate complex information, and trigger each other directly or indirectly in efficient ways. By insisting on an agent independent ACL, the agent-level issues can be separated from domain-level ones. Agents thus can interact with other agents, while local resources can be various. The intelligent behavior inherent from ACL is fundamentally determined by its abilities of mutual understanding of knowledge and the communication of that knowledge. In order to solve the problem of inconsistencies in the use of syntax and vocabularies, a universal communication language should be used. Although there is no universally accepted ACL [7],two prominent ACLs are KQML (knowledge query and manipulation language) [ 2 ] and FIPA (foundation for intelligent physical agents) [www.fipa.org]. Belief in that KQML are enough for common purpose, our agents use it as their primary ACL. Another reason is that KQML is designed as a universal language, which can meet our requirement to exchange something more than predefined or fixed statements.

q Message Pasring

Nltmrk Conncdon

4

ACL SpcsMng A p t %

ACZ

I

I

b

Figure 4: Hierarchical view of agent communication (Java RMI and message passing are two examples of network

connection protocols) Depending on its internal design (see Figure 4), the decentralization of ACZ is guaranteed. ACZ consequently can be prevented from causing message traffic or becoming a bottleneck. (Most central blackboards may have such trouble as the size of the system scales up.) In a summary, ACZ has the following functions: + Agent communication mediator ACZ is designed to facilitate agent communication, as well as to hide the low-level implementation details of network connection from high-level development of multiagent system. Agent categorization ACZ supports agent categorization by providing agent name registration and agent name resolution services. In fact, the hierarchical agent domain structure is maintained and managed by all ACZs. For instance, when a new agent is created, deleted or moved, it simply registers itself in local ACZ, which has the responsibility to

4.2. Agent communicationzone layer In brief, “Agent Communication Zone” is designed to facilitate agent interaction, as well as to hide the implementation details of communication from high-level development of multi-agent system. ACZ is actually placed between the KODAMA agents layer and network connection protocols and implementation layer. By doing so, the agent-level issues can be separated from the implementation details of network connection. In particular, ACZ itself is naturally distributed to every computer that might have KODAMA agents. ACZ therefore acts like a gateway or proxy for each agent because any exchanged information is either coming from or sending to local ACZ. For all ACZs, they work together to form a unified virtual “Agent Communication Zones” where agents can talk with each other freely.

438

broadcast this news to other ACZs. + Multithreading Sophisticated agents often include several concurrent processes performing various kinds of tasks. To optimize computing resources and speed up overall performance, multithreading is an effective way. In our design, multiple threads (listener thread and sender thread) are continually listening for incoming messages or dispatching outgoing messages respectively. Queuing &buffer In order to avoid becoming a bottleneck and causing deadlocks, a store-and-forward mechanism is applied. ACZ holds message queues for both incoming and outgoing messages. In the case that either the receiver of the message cannot be found or network connection fails, the message will be stored into the buffer, and an error exception is thrown. Both the queuing and buffer subsystem provides additional flexibility and robustness to agent communication. + ACL reader and writer As we discussed earlier, ACZ stays between KODAMA agent’s layer and network connection protocols and implementation layer. As Figure 4 shows, incoming messages need to be translated into ACL, while ACL-expressed messages from agents should be correctly understood, and sent out. ACL reader and writer thus bring great flexibility and transparency to the low-level implementation of agent communication.

also more difficult to extend an existed message passing based system if new objects and operations should be added dynamically. In general, different approaches are suitable for different situations. Therefore implementing agent communication based on several network protocols can bring us more flexible, robust.

5. KODAMA in distributed DB retrieval

+

Network connection implementation layer 4.3.

protocols

In this section, we present the implementation example of using KODAMA system in distributed database retrieval (see Figure 5 ) . There are several reasons for choosing KODAMA system in this field:

I

-

Agent CommunlcatmnZcne

and

=

Merrage pssrmg

Figure 5: KODAMA in distributed DB retrieval

+

In this layer, the physical network connection can be done. There are large varieties of protocols available now, such as UDP, TCPAP, SMTP, HTTP, Java RMI, CORBA and so on. UDP allows the delivery of a message to multiple recipients, but it makes no guarantees about delivery of packets, or the order in which packets are delivered. UDP sockets are typically used in bandwidthlimited or multicasting cases [I]. TCP/IP is a kind of lowlevel communication protocol. Although TCP/IP is not as sophisticated as other distributed object based protocols, it is relatively simple and can be widely supported. On the other hand, Java RMI allows us to do remote method calls in a natural way, and RMI takes care of all of the network-level details of the remote methods calls [4]. In a small application, for example, it is not difficult to put together a catalog of simple messages that is enough for remote agents to perform all of their critical operation through online transactions. RMI, however, may be useful because it is complicated and difficult to maintain a protocol of message passing in a larger application. It is

Reducing the network load Instead of moving large amounts of data to the user’s terminal, user agent can interact with remote agents to ask them to carry out a certain task. Later, the correct result can be shipped back to the user later. The motivation for this processing is simple: move the computation to the data rather than the data to the computation [6]. + Autonomy ’ KODAMA system provides higher-level abstractions than traditional distributed computing system, and gives the system more autonomy and flexibility in making decision. Rather than hardwiring a specific behavior for a given problem, agents might negotiate with one another to determine the best course of action for each situation. For instance, user agent can even send query in keywords to database agent where it can be interpreted and executed. 6 Decentralization and concurrency Distributed database retrieval often involves a variety of heterogeneous entities, and probably takes expensive computing resources. KODAMA system is good for

439

KODAMA system would become suitable for the Internet-oriented applications that usually requires both intelligence and distribution, such as information retrieval, e-commerce, scientific computing, personal assistant system, wrapper of legacy systems and so on.

doing this kind of job, because distributed agents can operate independently and concurrently while keep interactions asynchronously. + User-centric In general, there is one user agent specialized for one user, which holds a user profile consisting of user preferences, such as, user’s favorite newspaper, interested news, working schedule, and so on. This user profile is then used by the user agent to restrict the scope of the user’s requests, and it can be dynamically enhanced based on the self-learning facility of the user agent. + Robustness Robustness is primary guaranteed by the organization structure of KODAMA system, as well as the flexible design of network communication mechanism, exception handling, and so on. Currently, this application example has been tested in a local network environment where we have at least seven different databases and three user agents. Both user agents and database agents can enter or leave the system freely, and they are all residing in the same domain. The user can give out the queries by keywords. Then, the user agent will try to find out where is the appropriate database by looking for its local knowledge base. If the right database agent can be found, then the user’s query will be sent to that database agent directly. Otherwise, the query will be sent to all database agents, and they will try to interpret the query based on their metadata of the databases. If the query can be completed, the result will be sent back and shown to user by user agent. Especially, if there are several possible answers from different databases, all of them will be sent back.

7. Future work The KODAMA system is still far from a sophisticated multiagent system, and there are a lot of works remained for further study. First, we will try to enlarge the current implementation of KODAMA system to a large scale, so that, more agents and agent domains will be involved. Also, we are conceming the online leaming issues of agents. In other words, we want agents to be able to add new actions based on online interaction with other agents or users. Finally, network security is a lasting concern in an Internet-oriented application. In order to enhance our agents’ security, we will add the support of SSL (secure socket layer) protocol, use message cryptography, and apply authentication and authorization services for agents.

8. References [ I ] Farley, J., JAVA Distributed Sebastopol, CA, 1998.

Computing, O’Reilly,

[2] Finin, T., Labrou, Y.and Mayfield, J., “KQML as an agent communication language”, In Sofware Agents, MIT Press, Cambridge, 1997, pp. 291-316. [3] Huhns, M. N., and Singh, M. P., “Agents on the Web”, Internet Computing of the IEEE, May 1997, pp. 80-82.

6. Conclusion

[4] Java Remote Method Invocation Specification, Sun Microsystems,California, October 1998.

Multi-agent based computing is a promising approach to developing a range of complex, distributed, intelligent, scalable, and reusable systems. Building an effective distributed multi-agent system, like a KODAMA system, requires the integration of techniques on distributed artificial intelligence, agent communication, parallel computing, distributed object, the Intemet computing, and so forth. Our KODAMA agent basically has a component-based architecture that grants future enhancement, extension and reuse across domains with a little modification. For agents to be more interactive and autonomous, our solution is adding a new application independent layer, called agent communication zone (ACZ). This additional layer makes the low-level interaction protocol be hidden from the agent-level development, and both can be updated independently. By looking at the application example of KODAMA system in distributed database retrieval, we believe that

[5] Joshi, A., and Singh, M. P., “Multiagent Systems on the Net”, Communications of the ACM, ACM, New York, March 1999, V01.42, NO. 3, pp. 39-40. [6] Lesser, V. R., “Reflections on the Nature of Multi-Agent Coordination and Its Implications for an Agent Architecture”, Autonomous Agents and Multi-Agent Systems, Kluwer Academic Publishers, No. I , 1998, pp. 89-11 1 .

[7] Singh, M. P., “Agent Communication Languages: Rethinking the Principles”, IEEE Computer, vol. 31, No. 12, December 1998, pp. 40-47. [8] Wooldridge, M. and Jennings, N. R., “Pitfalls of AgentOriented Development”, In Agents ’98: Proceedings of the Second International Conference on Autonomous Agents, ACM Press, May 1998.

440