Dr Hongen Lu, School of Information Technology [HREF1], Deakin University [HREF2], 221 Burwood Highway, Burwood, VIC 3125, AUSTRALIA . helu@deakin.edu.au
Web services is one of the main forces driving the Internet from its infant, a vast collection of text and images, to today's huge growing marketplace of service providers and consumers. Agent technology plays an important role in this evolution. One of the fundamental problems in building open Web-based applications is how to find information providers and how to integrate information agents in such a dynamic environment. There is an obvious need for a standardized, meaningful communication among agents to enable them to know each other and perform collaborative task execution. In this paper, I propose an ontology based language for agent services description. This language exploits ontology of service domain, and provides the flexibility for developers to plug in a suitable language to describe the constraints. Multiple matchmaking strategies based on agent service ontology are given to help agents finding appropriate service providers. The series of strategies consider various features of service providers, the nature of requirements, and more importantly the relationships among services.
Web services is one of the main forces driving the Internet from its infant, a vast collection of text and images, to today's huge growing marketplace of service providers and consumers. Agent technology plays an important role in this evolution. How to find information providers and how to integrate information agents in such an open environment are new challenges. Information agents, such as Ahoy (Shakes, Langheinrich, Etzioni, 1997), ShopBot (Doorenbos, Etzioni, Weld, 1997), and SportsFinder (Lu, Sterling, Wyatt, 1999), are programs that assist people to find specific information from the Web. They are information service providers, which have the capabilities to find information for users, for example locating a person's homepage, finding the cheapest available prices for music CDs, or finding sports results of a team or a player.
However, there are new challenges. For a novice user, a challenge is how to find these services; for an information agent, the challenges are how to locate the service providers, and how to communicate with them to solve its tasks cooperatively. One of the basic problems facing designers of open, multi-agent systems for the Internet is the connection problem --- finding the other agents who might have the information or other capabilities that you need (Decker, Sycara, Williamson, 1996).
In (Genesereth, Ketchpel, 1994), two basic approaches to this connection problem are distinguished: direct communication, in which agents handle their own coordination and assisted coordination, in which agents rely on special system programs to achieve coordination. However in the Web application domain, where new agents might come into existence or existing agents might disappear at any time, only the latter approach promises the adaptability required to cope with the dynamic changes in the environment.
In (Decker, Sycara, Williamson, 1997), they have recently described a solution space to the connection problem based on assisted coordination. The special system programs for coordination are called middle agents. They also identify nine different types of middle agents depending on which agents initially know about capabilities and preferences of agents.
Depending on where the preference and capability information is stored, middle agents can be classified into nine different roles (Decker, Sycara, Williamson, 1997). The following three are common roles of middle agents.
How to connect the service providers and consumers? A possible solution is a software mediator. A mediator is a software module that exploits encoded knowledge about some sets or subsets of data to create information for a higher layer of applications (Wiederhold, 1992). In Dao and Perry's work (Dao, Perry, 1996), a mediator is an information producing or serving entity in a large-scale inter networked environment. I present a mediator based middle agent architecture for agent services advertising and requesting. The architecture is given in Figure 1.
Figure 1: Mediator Based Architecture
In my point of view, a mediator is a special kind of information agent acting as middle man to take as input, a request to find an agent that provides a service, and returns as output, a list of such agents and their cooperation relationships. A mediator also stores the services offered by different agents in the existing environment, and when a new agent is introduced into the environment it can register its capability to the mediator, using an agent service description language, if this agent wants its service to be used by others. Information agents can also unregister their services to the mediator when they want to quit the cooperation or exit. Also when an information agent receives a query or a subtask within a query that can not be solved by itself, it can request the mediator to find out other agents that have the capability or a set of agents who can work cooperatively to provide that service.
To register and recommend agent services, a formal language is needed. In this language the essential knowledge about the service has to be represented. Modern representation systems are designed for this task, especially knowledge representation techniques. Knowledge representation concerns how a program, or an agent, models what it knows about the world and itself. In recent years, knowledge presentation focuses on categorization, which enables reasoning about objects and specifying their relationships. Ontology is a concept comes with this direction. Ontologies are content theories about objects, their properties, and relationships among them that are possible in a specific domain of knowledge (Chandrasekaran, Josephson, Benjamins, 1999). The use of ontology is becoming widely accepted in the World Wide Web community, since ontology provides a base for agents, or programs, to interchange knowledge, to structure information on the Web, and to reason the relations among terms.
Since each information agent is developed geographically distributed over the Internet, their capabilities are different from each other. SportsFinder (Lu, Sterling, Wyatt, 1999) can find the sports results of golf, cycling, football and basketball etc. for users; while Ahoy (Shakes, Langheinrich, Etzioni, 1997) is good at locating people's homepages. However considering in an application domain, such as sports, there exists a hierarchy relationship among these information agents.
Figure 2: A Fragment of Sports Service Ontology
In this section, I characterize agent service relations.
To find the service relationship between two information agents, the middle agent should keep the knowledge of the domain service. The knowledge the middle agent would need to match the services of information agents is effectively an ontology of service. The agent service ontology contains all the services of information agents as well as their relationships. A directed cyclic graph (DCG) could be added to present the relations between agent services. Nodes and edges could be described in the DCG.
Before giving the syntax of the language, it is needed to investigate what kind of knowledge the language should contain to express the capabilities of agents. The following parts are essential in ACDL:
In this subsection the syntax for an agent capability description language is proposed. The language begins with the word capability followed by a set of keyword-value pairs as in KQML.
<acdl> ::= ( capability
:cap-id <name>
:constraint-language <name>
:input ( <param-spec>+ )
:output ( <param-spec>+ )
:input-constraints ( <constraint>+ )
:output-constraints ( <constraint>+ )
:io-constraints ( <constraint>+ )
|:cap-ontology <name>
|:isa <name>
|:privacy <name>
|:quality <name> )
<param-spec> ::= ( <name> <term> )
<term> ::= <constant> | <variable> | ( <constant> <term>+ )
<constant> ::= <name>
<variable> ::= ?<name>
<name> ::= <Identifier>
<constraint> ::= << expression in constraint-language >>
|
The syntax of ACDL allows the plugging in of an independent constraint language, that is the syntax of our ACDL is open at this point. This is described in the constraint-language field, which tells what language is used to present the constraints that should be hold on input, output and input-output. Also the cap-id field allows the specification of a name for this capability. The name for the capability is used to enable the middle agent to build a service ontology, and allows the isa field to naming a capability from which this capability will inherit the description. These two fields make it easier and simple to write a service description based on the already existed service ontologies, which is given as the value of cap-ontology field. The privacy and quality fields describe to what degree other agents can access this service and what the quality of this service is respectively. However, it is necessary to define at least one constraint language that can be used to represent the constraints in the description. First-order predicate logic (FOPL) is a promising option to specify constraints.
For example, the service description of an information agent in SportsAgents (Lu, Sterling, 2000) system, who can find out the position of a football team in the AFL (Australian Football League) result ladder, can be written as follow:
(capability :cap-id AFLladder_finder :constraint-language fopl :input ( (AFLTeam ?team) ) :output ( (Position ?position) ) :input-constraints ( (elt ?team TeamName) (Has Location ?team Australia) (CompeteIn ?team AFL) ) :io-constraints ( (Has Position ?team ?position) ) :cap-ontology sports )
This service description tells us that the identification of this capability is AFLladder-finder, it uses fopl (first order predicate language) to specify the constraints. Its input is an AFL team name, and output is the position of this team on the ladder. The three input constraints require that the input string should be a team name and this team is competing in the Australian Football League. Also, the output constraint requires that the position is of that inputted team. The cap-ontology field tells that all the terms in this description are in the sports ontology. Given the above service description, an information agent can explicitly tell other agents what it can offer for them. A mediator agent can also keep a record of this description for further inquiries. In fact, the above description is embedded into the agent communication language, for instance if the communication language is KQML, which is the case in our SportsAgents system, the capability description is actually the content field of KQML. Based on the above service, a more complex service can be built. For example, we can build an information agent that can find out the current ranking of AFL teams in Melbourne, and we want this service only available for customers (human users or other agents) who are in the Melbourne area. This requires the identity of our agent to be kept private from the broader public. The service of such an agent can be described as follows:
(capability :cap-id MelAFLladder_finder :constraint-language fopl :relation ( (isa AFLladder_finder) ) :input ( (AFLTeam ?team) ) :output ( (Position ?position)) :input-constraints ( (Has Location ?team Melbourne) ) :privacy high )
In this description, I define MelAFLladder_finder as a service inherited from AFLladder_finder. MelAFLladder_finder inherits all the constraints of service AFLladder_finder; besides that it has additional constraints and fields. In MelAFLladder_finder, it requires the AFL team is actually from Melbourne and it has a high privacy restriction. From the previous section, we know that for high privacy requirements, a service provider's identity is not allowed to be told to requesters. Instead, the mediator will inform MelAFLladder_finder which agents are requesting its service at the time, and let MelAFLladder_finder decide whom it would like to contact to offer its service. In this process, the details of MelAFLladder_finder are strictly kept in control by itself. Our agent service language gives users the choice to protect service providers' privacy. In some circumstances, this feature is important to the security of agents.
This is the simplest strategy that only matches the types in the input and output fields of service advertisements against the correspondent field in requirements. It makes sure that a provider can take the inputs of requester, and its outputs are compatible with the requester's.
Constraint matchmaking considers the constraint parts in agent service descriptions.
Definition 1. Constraint Match: Let A be an advertised service description, and R be a service request. If all the constraints in R are subsets of the corresponding constraints, or substitutions of constraints in the constraint language, in A, then R is constraint matched with A.
From the above two strategies, it is straightforward to design algorithms to check all the relevant variables and constraints.
Exact match is most strict matchmaking. It requires both the types and constraint fields are well matched. This strategy deals with the services that have the same functions but with different variable and type names. Considering the huge amount of Web-based applications which implemented over times and locations, there are many cases that developers may select different naming space.
Partial match is a combination of type match and constraint match, but both loose a little bit. This strategy aims at services that are not completely matched, but have some functions in common. It is defined as follow:
Definition 2. Partial Match: Let A be an advertised service description, and R be a service request. If there exist variables in the input and/or output fields of R that are subtypes of the corresponding variables in A; and/or there there exist constraints in R are subsets of the corresponding constraints, or substitutions of constraints in the constraint language, in A, then R is partial matched with A.
The above definition means for two capability descriptions, if some of their input, output variables have subtype relations, and there are constraint clauses in their input and output constraint specifications that have substitute relations, these two services are partial matched. Semantically, in some circumstances, i.e. the unmatched variables and constraints are irrelevant; the partial matched service is applicable.
Due to a service provider agent's privacy restriction, the matchmaking result actually is sent to the service provider instead to the service requester. In other words, the provider agent wants to control the communication with consumers, it does not want to expose itself before knowing who are requesting its service. In the real world, we have a similar scenario. For instance, when recruiting for qualified software developers, some companies may not like their names known by their competitors, so they ask the agencies (middle agents) to keep their privacy. After the agency provides them with the resumes of potential experienced programmers, they can decide whom they would like to interview. Until this stage, the identities of these companies are protected from the programmers who are job hunting. The process of privacy matchmaking has the following steps:
Compared with other traditional matchmaking strategies, privacy matchmaking actually matches a service advertisement against service requests each time, while all the other strategies are vice versa; The information flow is different; the result of matchmaking is transferred in a different direction. From the mediator's perspective, privacy matchmaking is a service for capability providers. It supplies service request information to providers to help them market their services.
Matchmaking is a process based on a cooperative partnership between information providers and consumers. In our SportsAgents (Lu, Sterling, 2000) system, a mediator is introduced to solve the connection problem. SportsAgents is an open multi-agent system to answer a user's query about sports, for instance ``which is the best sports city in Australia?''. In SportsAgents three types of agents, mediator, information agents and interface agents, are implemented. To find the best sports city may require the cooperation of different sports information agents. The mediator finds the current available information agents who have the capability that the query agent (information consumer) is asking for. In case no available agent can fulfill the query service itself, the mediator will infer the available services to find a set of available information agents that can cooperate in some way to provide the requested service. The algorithm for cooperative service matchmaking is given below:
matchmaking(S: Service, head: Ontology)
Given S, the service information agent requests, agent table AgentTable,
which contains the contact information of currently available information
agents, and the service ontology Head.
Each node in the service ontology has the following structure:
public class Service extends Vector
{
String name;
Service up;
Service down;
Service next;
.
.
.
}
this algorithm returns the agents contact information and their relationships.
find = false; head = Head;
Agent-found =null; relation = null;
if AgentTable.index(S) = true then {
while} (AgentTable.query(S) != null) {
Agent-found = Agent-found ADD AgentTable.query(S);
}
relation = find-relation(S, head);
find = true;
}
else {
if head.name = S.name then} {
service = head.down;
while} (service != null AND !find) {
matchmaking(S, service);
service = service.next;
}
}
else} {
matchmaking(S, head.down);
matchmaking(S, head.next);
}
}
return Agent-found, relation. |
This algorithm requires an arbitrary amount of deduction and knowledge to match any given service and request. It exploits service ontology, knowledge on the application domain, to discover the hidden relationships among currently available services.
SportsAgents (Lu, Sterling, 2000) is an open multi-agent system to answer sports questions, it exploits a mediator based architecture. Following let us look at some examples in SportsAgents illustrating the above definitions and the matchmaking strategies.
Considering the following agent capability description of SportsFinder (Lu, Sterling, Wyatt, 1999):
(capability :cap-id SportsFinder :constraint-language fopl :input ( (Team ?team) ) :input-constraint ( (elt ?team TeamName) (CompeteIn ?team Sports) ) :output ( (TeamScore ?score) ) :output-constraint ( (Has Score ?team ?score) ) )
The above description shows that SportsFinder can find out the scores of a sports team. Suppose the mediator has already received the above service advertisement. Then some information agent sends the following service request to the mediator:
(capability :cap-id SoccerResult :constraint-language fopl :input ( (SoccerTeam ?soccer_team) ) :input-constraint ( (elt ?soccer_team TeamName) (CompeteIn ?soccer_team Soccer) ) :output ( (Score ?result) ) :output-constraint ( Has Score ?soccer_team ?result) ) )
When applying the type matchmaking algorithm on these two service descriptions, we have input variable soccer_team as a subtype of team and output type TeamScore as a subtype of Score, thus SoccerResult is type matched against SportsFinder. That means the service of SportsFinder can take the variables of the request as input, and its output is compatible with the variables' types of request. From this example it is easy to understand that type match relation is not commutative. For the above two descriptions, service SportsFinder is not type matched with SoccerResult, although vice versa.
Figure 2: Mediator
Consider the scenario in Figure 2. Currently there are three agents available in sports domain. Information agents Tom and Jerry can provide the service of getting the results of AFL and NRL (National Rugby League) respectively. However to answer a user's query ``which is the best sports city in Australia?'', agent must know the result of one of the most popular sports, Football, of Australia. Unfortunately, none of the current available information agents has that capability. Using cooperative matchmaking algorithm, it can be inferred that Tom and Jerry can work cooperatively to get the information. So the mediator will reply the request information agent with Tom and Jerry's contact information as well as their cooperative relationship. This can not be achieved in IMPACT (Arisha, Subrahmanian, etal, 1999) platform. I believe inference and some reasoning abilities are necessary for mediators to provide intelligent matchmaking. Domain specific mediators can be built to help discover other information agents in a specific domain.
Agent services description and matchmaking is one of the fundamental problems in building open Web-based applications; since in such a dynamic domain, applications are developed distributively and they become available or exist at any time.There is an obvious need for a standardized, meaningful communication among agents to enable them to perform collaborative task execution. Mediator agents provide a plateform for information agents to know each other. The proposed ontology based agent service description language enable agents to advertise and request services. The introduction of ontology makes the language capable for describing domain knowledge, which is vital to discover the semantics of services. This language gives a flexible method for developers to plug in a suitable independent constraint language; it is more expressive for service quality and the privacy of service providers. Multiple matchmaking strategies provide more flexible methods for agent service consumers to locate providers. Depending on various features of service requirements and the nature of providers, mediator can select a suitable strategy for the matchmaking process. Especially, when a request can not be fulfilled by a single agents, cooperative match is able to find a set of agents working in a team to solve the problem.
Arisha, K., Kraus S., Subrahmanian, V. S., and etal (1999). "IMPACT: Interactive Maryland Platform for Agents Collaborating Together", IEEE Intelligent Systems, 14(2):64-72.
Chandrasekaran, B., Josephson J. R., and Benjamins, V. R. (1999). "What
are Ontologies, and Why do We Need Them?", IEEE Intelligent Systems,
14(1):20-26.
Dao, S., Perry, B. (1996). "Information Mediation in Cyberspace: Scalable Methods for Declarative Information Networks". Journal of Intelligent Information Systems, 6(2/3):131-150.
Decker, K., Sycara, K., and Williamson, M. (1996). "Matchmaking
and Brokering". In Proceedings of the Second International Conference
on Multi-Agent Systems (ICMAS-96).
Decker, K., Sycara, K., and Williamson, M. (1997). "Middle-Agents
for the Internet". In Proceedings of Fifteenth International Joint
Conference on Artificial Intelligence (IJCAI-97), pages 578-583, Nagoya,
Japan.
Doorenbos, R. B., Etzioni, O., and Weld, D., S. (1997).. "A
Scalable Comparison-Shopping Agent for the World Wide Web". In Proceedings
of the First International Conference on Autonomous Agents.
Genesereth, M. R., Ketchpel, S. P. (1994). "Software
Agents". Communications of the ACM, 37(7):48-53.
Lu, H., Sterling, L. (2000). "SportsAgents: A Mediator-Based
Multi-Agent System for Cooperative Information Gathering from the World Wide
Web". In
Proceedings of the Fifth International Conference on the Practical Application
of Intelligent Agents and Multi-Agent Technology (PAAM 2000), pages 331-334,
Manchester, UK.
Lu, H., Sterling L. and Wyatt, A. (1999). "Knowledge
Discovery in SportsFinder: An Agent to Extract Sports Results from the Web".
In Ning Zhong and Lizhu Zhou, editors, Methodologies for Knowledge Discovery
and Data Mining, Third Pacific-Asia Conference (PAKDD-99) Proceedings,
volume 1574 of Lecture Notes in Artificial Intelligence, pages 469{473, Beijing,
China.
Shakes, J., Langheinrich, M. and Etzioni O. (1997). "Dynamic
Reference Sifting: A Case Study in the Homepage Domain". In Proceedings
of the Sixth International World Wide Web Conference, pages 189-200. Available
online at: HREF3.
Wickler, G. J. (1999). Using Expressive and Flexible Action
Representations to Reason about Capabilities for Intelligent Agent Cooperation,
PhD thesis, University of Edinburgh, Edinburgh, Scotland.
Wiederhold, G. (1992). "Mediators in the Architecture of Future Information Systems". IEEE Computer, 25(3).
Hongen Lu, © 2003. The authors assign to Southern Cross University and
other educational and non-profit institutions a non-exclusive licence to use
this document for personal use and in courses of instruction provided that the
article is used in full and this copyright statement is reproduced. The authors
also grant a non-exclusive licence to Southern Cross University to publish this
document in full on the World Wide Web and on CD-ROM and in printed form with
the conference papers and for the document to be published on mirrors on the
World Wide Web.