Content based routing via an active message board for both intra and inter agent communication.

Nikolaos Skarmeas and Keith L. Clark

Department of Computing,

Imperial College,

London, UK

email: {ns4,klc}@doc.ic.ac.uk

Abstract

This proposal is about a way of integrating agent components and facilitating intra-agent communication. The main assumption is that an agent consists of a number of components that interact with each other. We suggest that interaction is mediated by a message board, where components place messages and these messages are forwarded to the appropriate component(s). The novelty of the approach that is proposed is that the forwarding mechanism is based on active patterns. An active pattern is a piece of code that is sent by the components to the message board and expreses component interests. The active patterns are tested upon incoming messages (by executing their code) and the messages are forwarded to the components whose patterns have succeeded.

As an implementation platform, the April langauge is recommended. It is a process oriented language, and within the advanced features that it provides, it allows to easily implement code (the active patterns in the present situation) migration.

Introduction

A common approach, for the internal architecture of an agent, is, the separation of the agent functionalities into two main categories: the domain independent and the domain dependent one. The domain dependent part of the agent deals with the (possibly local) problem solving activities of the agent. The domain independent part deals with the communication oriented activities of the agent and the coordination of its actions with respect to other agents.

Figure 1: The two layer agent

In the proposal we are mostly concerned with the intra-agent activity. Considering the current trends, with the introduction of distribution, concurrency and openness in software systems, the domain dependent part of the agent might consists of the several components that are possibly distributed and/or executing concurrently. Also they need to communicate with each other and coordinate their actions since they are possibly complementary and may lneed to interact with each other to accomplish the agents's goals.

One way of designing and implementing agents is to hardwire the agent component communication and interaction into the components. However, this has the disadvantage of creating inflexible architectures. Deletions and additions of components affect the overall agent functioning and causes possibly the need for re-implementing the components. Therefore, what is needed is a way of allowing the components to communicate with each other which allows dynamic deletion, addition and modification of components. A standard approach for this purpose is the use of a message board, a shared repository of messages which components can use as a communication medium. The advantage of message board is that the components can be heterogeneous and they can join and leave the session without any disruption to the rest of the components (provided that there remains, or they get replaced by, another component that offers the same or similar functionality).

The rest of this paper, explains in detail a proposal for an active message board architecture that can be used to integrate (possibly pre-existing) agent components. The main purpose of the message board it to provide intelligent routing between a set of components that use it to communicate with one another, or which at least use of it for their initial, opening, communication. The message board acts as an intelligent router because it actively forwards the messages placed on it to the agent's components that have registered with the message board an interest in messages of that form.

The message board understands KQML style messages. Components register an interest by sending a KQML advertisement to the message board. The content of this advertisement is an message pattern. A message pattern advertised by a component C is applied by the message board to each new message placed on it. Whether ot not the message is forwarded to C now depends on qualifications, concerning the destinations, optionally attached to the message by the sender. For example, the sender can specify one or all destinations, and can attach a function to be applied to the the set of identities of all the potential destinations to prune the set.

This bilateral control of the message routing, by both senders and receivers, provides a powerful mechanism for processing and routing messages, more powerful than passive pattern matching and much more powerful than Linda style tuple spaces used as passive message boards that must be continually polled by processes for messages of interest.

This active message board architecture can also serve as the basis for building facilitators for interagent communication. Service providers can register with a message board actings as a communication facilitator by advertsising a set of active message patterns.

Active Pattern based Intelligent Routing

This section elaborates on the message board architecture. Initially the generic agent architecture that is assumed is explained and the motivation behind the use of message board is elaborated. Next, the way the message board can be realised in explained and the use of active patterns is explained. Finally, the extension of this approach in the inter-agent applications is also covered.

The Agent Architecture

Agent architectures range from quite abstract proposals of what agents should comprise to more concrete artifacts designed for specific kinds of applications. A common approach, is an agent comprising a set of interrelated components whose functionality contributes to the overall agent behaviour. The operation of those modules may be concurrent. The concurrency is controlled by a control unit which is the agent meta-level control unit. Finally, the agents must communicate with other external agents or non-agent applications, so a communication component is also needed. Considering these very general requirements, the general software architecture assumed is depicted in the following figure (figure 2).

Figure 2: The general agent architecture

The knowledge base Another common requirement of an agent architecture is a knowledge base component, which keeps information shared by all the other components. It is the global memory for all the components of the agent (each of which may also have private memory) and can be used to store information such as the beliefs, intentions and plans of the agent as well as meta-level information about other agents and the capabilites of the behaviour components. This knowledge base can be accessed and updated by all the other agent components.

Behaviour components The behaviour that the agent exhibits is implemented by a number of behaviour components. The behaviour components will generally differ from agent to agent. A behavioural component can be composite, indeed it can itself be an agent comprising all the agent components. So agents can have a recursive structure. Ideally, these behavioural components are changeable over the lifetime of the agent. This allows the agent to be reconfigured and gives it the ability to adapt to new requirements that its environment imposes. The manipulation of the behavioural components is the purpose and role of the ``meta-component''.

Message board The agent components interact with each other in two ways. They store and retrieve information from the shared knowledge base. They also interact via messages. The message interaction is supported by the active message board. Any agent component can place messages intended for one or more other components on the message board. They are also sent messages by the message board, hence the active label. A message board architecture, for facilitating component interaction, was chosen because it allows heterogeneous information sources to be integrated. Also components can join and withdraw without disrupting the functionality of the rest of the agent. When a new component is added to the agent it signals its presence by advertising a set of active message patterns to the message board.

An active message pattern is of the form filter_pattern + auxilary_test_code. It is applied by the message board to each new message M placed on it. If the filter pattern matches the message, the auxiliary test code is executed. This usually further processes and tests parts of the message extracted as a result of the successful match with the filter pattern to make sure the message really is of interest to the component C that lodged it. However, it can also do arbitrary processing on behalf of C. As part of this processing it can communicate with other agent components. It can even communicate with C, and the component that sent the message M, to determine whether or not M is really of interest to C. If this test code succeeds, C is a potential destination for the message.

If the message M was communicated as a broadcast message, all the potential component destinations are found be applying each of the message boards active message patterns to the message. Then, the destination filter function which the sender may have attached to the message is applied to prune this set of potential destinations. The message M is then forwarded to each destination in the pruned set, if there are any. Finally, the message is retained on the message board until its sender specified expiry time in case a component C' subsequently advertises an active pattern that successfully applies to the message. If so, providing this component also satisfies the destination filter function, the message is forwarded to C'. The default expiry time for a message is immediate, in which case the message is not retained by the message board.

There is a similar scenario for a message M' communicated to the message board as a single destination message. The main difference is that M' will only be forwarded to one component destination and, after forwarding, is no longer retained by the message board even if its expiry time has not elapsed.

Agent head Agents also need to have a communication mechanism that deals with incoming messages from other agents. This is the purpose of the head communicator which is the external communication interface of the agent. The head communicator is also a security wall to the outside world. Incoming messages arrive first at it, and are then forwarded to the message board in order to be forwarded to the appropriate agent components. Therefore, outside agents do not have direct access to the message board which is the internal agent backbone.

An example agent

In order to better illustrate the above, consider an agent that implements a travel agency which can be contacted for ticket reservation. This agent can offer tickets for European and Asian flights. It has two main broker components. They are flight brokers, each dealing with a particular geographical area (figure 3).

Figure 3: The travel agency example

Assume that a message for a flight reservation between London and Tokyo arrives with some constraints on the fare (fare < 700). This message is forwarded to the broker responsible for the Asian flights. Assume that this broker cannot find a direct flight with the money constraints specified by the client but it finds an indirect flight from London to Tokyo through Frankfurt. Then it sends a message to the broker responsible for the European flights to book a seat the specified date and when a confirmation by this broker is replied back to the first broker a reply is sent back to the client with the flight details. During the above processing the brokers might consult the agent database where information about, say airlines and destinations, is stored.

The message board (active pattern based intelligent routing)

We adopt the KQML approach of having message sent to the message board wrapped in an outer message with a performative indicating the senders intent. The router can takes appropriate action according to the performative of the wrapper message For a

(forward :content M :destination_filter F :timeout T)

message, for example, the router will forward M to a just one appropriate component. For a

( forward-to-all :content M :destination_filer F :timeout T)

message, the router will find the set D all the components that are intetested in the message and foward the message to the subset of these that are are returned by the application of the filter F to D.

The interests are sent to the message board as

(advertise :pattern_name N :pattern P)

messages where P is the active pattern, ie code that can be applied to a message, which may itself involve communication, but which eventually returns true or false.

The architecture of the message board (router) is depicted in the following figure:

Figure 4: The message board (router) architecture

As this figure depicts the message board consists of three main parts: the message queue where incoming messages are received, the message repository where the pending messages are stored (after they have been deleted from the message queue), the active filter repository where the component filters are stored and the control unit that picks messages from the message queue and applies it on the list of filters that have been stored.

When an incoming message arrives in the board, the filters that board has stored in the filter repository are applied on the content of the message in order to generate a set of handles for the components that the message will be forwarded to. In addition to the performative and the actual content of the message a sender defined script with an expire time is also provided. The script is intended to filter out the returned set of components. If for example, the sender of the message has a some specific preferences on specific components, this can be expressed by the script. The script is provided with the set of the generated components and it returns a subset of it which expresses the components that have been approved by the sender (through its script). If not all of the required components have been found, the message is removed from the message queue and is placed in the message repository. This is where all the messages are stored, for which not all for the required components have been found and the expiry date has not expired, i.e. it is still relevant. When a new filter is registered by a component, it is checked upon all the suspended messages and is sent all these for which their corressponding sender scripts also succeeds. Furthermore, the filter is stored in the filter repository, for being considered for future messages.

Reconsidering the travel agency example, a message of the form:

"(forward :content (destination ...))"

will arrive in the agent and placed on the message board. Then it will be forwarded to the "Asian" broker, since we assume it has registered a message pattern that looks at the destination field of the content message. As a result of the processing in the broker, the following message will be placed back to the message board and subsequently forwarded to the "Europe" broker:

"(forward

:language April

:ontology ticket-reservation

:reply-with id1

:content (:destination Frankfurt

:From London

:departure-date 7/2/97

:return -date 14/2/97))"

which will send the following reply back to the "Asia" broker:

"(reply

:reply-to id1

:language April

:ontrology ticket-reservation

:content (:filghtno BA345

:destination Frankfurt

:From London))"

The implementation Platform

The above proposal serves the conceptual basis for constructing and developing agents, especially the aspect of them concerning integrating the agent components and facilitating their communication. The whole framework gives some guidiles for the features that the implementation platform should offer to the agent developers. Some of these are summarised below:

· Concurrency and Communication: The components can be executed concurrently and the interaction among them and the blackboard is based on message passing. So, the language platform should allow the implemenation of concurrent processes and also provide syntactic features for easily specifying inter-process communication.

· Symbolic computation: The message echanged have a rich content with complex structure. Thefore the language should provide advanced data structures and offer also operators for manipulating these structures.

· Mobile Code: Active patterns can be imnplemented as code (function and/or procedure closures) that can be embedded into messages and been sent to the blackboard, stored and executed when message arrive. Therefore, it would be very convenient, and save a lot of programming effort, if the language supported code migration, in terms of message passing, as first class. And because the code is stored by the processes it is also essential from a language to provide higher order features in general.

The above features are not only essential for the specific framework. Modern applications, especially those that are developed with distribution and openess in mind should offer some (if not all) of the above features.

As an implementation platform for the above framework, we use the April language. April supports all of the above features and a number of others. Summarising the April features, it is a process oriented language. Processes can be forked and be given a unique Internet wide identifier. Processes accept symbolic messages, that are matched against a set of predefined patterns. Therefore offers pattern matching. April processes can store data as records or lists that can be manipulated by using a set of primitives that the language provides. Also it is hiher order. Function or procedure closures can be defined, stored in variables or sent in messages. Therefore, April provide as first class mobility of code.

Finally, April provides powerful macro pre-processor that can be used to extend the declarativeness and expresiveness of the language. Using this macro process a database layer has been implemented on top of April. This enhances April processes with the the ability to store information is a Prolog like format (a facts and rules). This information can be queried by queries whose syntax is a hybrid of Prolog and SQL. They can either be local quiries or remote that are sent as April messages. This extension and its distributed database facility has been especially useful for implementing the shared knowledge base component of the agent.

Forking for example the code that implements the blackboard, is accomplished by the command:

handle? BlackboardId := fork Blackboard;

where Blackboard() is the procedure that implements the code and BlackboardId is the handle identifier of the process.

The KQML like message, for example, that is sent to the blackboard can be written as an April record:

(forward,[(language,April),(ontology,ticket_reservation),(reply_with,id1),

(content, [(destination, Tokyo), (From, London),

(departure_date, "7/2/97"), (return_date, "14/2/97")])

])

For the filters that components can register in the blackboard, the higher order facilities of April can be proven extremely useful. They can be boolean function closures that process the content of the message and evaluate some conditions. A possible filter that the "Asian" broker can register is:

(advertise,asian_tickets,{(any?Performative,any[]?Args)::{

(content, any[]?Content) in Args and

(destination, symbol?Destination) in Content and

is_true { asian_city(Destination) } ! database}) >> BlackboardId

The following message when received by the blackboard will cause it to store the third argument of the record (which is the filter) in the filter repository. When the filter will be applied on, will retrieve the destination of flight from the content of the message and will contact the agent knowledge base to find out whether the destination is an Asian city:

is_true {asian_city(Destination)} ! DatabaseId

where DatabaseId is the handle identifier of the agent knowledge base. This is a database query (from the April database extension) that is sent to the knowledge base process, evaluated and the result of the evaluation returned back. This is also an example of the power of the active filters, which not only do local processing but can have as actions messages beign sent etc.

Summarising the Proposal

Summarising the proposal, we suggest that an agent should contain a message board and a knowledge base, which can be used to integrate the several agent components the agetn consists of and facilitate intra-agent communication1. As far as the messag board is concerned the following main points can be highlighted:

· Messages consists of a performative, content a script and a timeout (other items can also be included, depending on the application domain). The performative instructs the board how to deal with the incoming message, and the script is a sender defined script that is executed before the message is forwarded. It it used to allow some control from the sender point of view of the message forwarding. A message is of no interest as soon as the time period specified in the timeout expires.

· The message board consists of a message repository where incoming pending messages are placed and a filter spool where the component patterns are stored and a control unit that control the board operation.

· The component patterns are active in the sense that they are executable code which can involve complex processing of the message content and also communication with othe rprocesses including the component that registerd this pattern. This provides simple but very powerful way of controlling message dispatching.

Also, we recommend the April language as the implementation platform. The reason for doing so is that its advanced features make it an ideal language for distributed, symbolic based computation (agent based applications are a typical example of this). It can be used free for research purposes. More details about it can be found in the web sites:

http://laotzu.doc.ic.ac.uk/software.html

http://www.fujitsu.co.jp/hypertext/Products/Software/April/Eindex.html

Also, in the following sites a collection of papers can be found, that cover issues related to the material presented in this proposal.

http://laotzu.doc.ic.ac.uk/UserPages/staff/ns4/ns4.html

http://laotzu.doc.ic.ac.uk/UserPages/staff/klc/klc.html