WO2001009831A2

WO2001009831A2 - Integrated system and method of creating intelligent agents

Info

Publication number: WO2001009831A2
Application number: PCT/US2000/021059
Authority: WO
Inventors: Danny Rae Ballard
Original assignee: Reticular Systems, Inc.
Priority date: 1999-08-02
Filing date: 2000-08-02
Publication date: 2001-02-08
Also published as: AU6754800A

Abstract

A system (200) and method for developing communicating software agents (220). The development system facilitates defining the intelligent software agents and an agency for the agents. A system toolkit (210) includes a protocol manager (1510) for defining roles (1704) for the agents and for defining communication (1706, 1708) between the agents. The communication may include messages and message protocols (3702) including conditions and actions, and may be represented as state transition diagrams (3800). A set of behavioral rules (108) for the agents may be derived from the state transition diagrams. The system also includes a run-time agency viewer for viewing (534) the messages sent among the agents.

Description

INTEGRATED SYSTEM AND METHOD OF CREATING INTELLIGENT AGENTS

Background of the Invention Field of the Invention Aspects of the present invention generally relate to intelligent agents. More particularly, embodiments of the present invention relate to interactively generating multiple agents in a graphical programming environment. Description of the Related Technology

The concept of an intelligent software agent has captured the popular imagination. People like the idea of delegating complex tasks to software agents. These agents can make airline reservations, order new books from an online store, find out about the latest song from a favorite musician, or monitor stock portfolios. Software agents can roam the Internet finding information for us. Sophisticated software agents can negotiate the purchase of raw materials for a factory, schedule factory production, negotiate delivery schedules with a customer's software agent, or automate the billing process. However, developing intelligent agents requires specialized knowledge and can be difficult, time-consuming and error-prone. New tools are needed to make it easier for software developers to build these sophisticated software agents.

Intelligent software agents are a new class of software that act on behalf of the user to find and filter information, negotiate for services, easily automate complex tasks, or collaborate with other software agents to solve complex problems. Software agents are a powerful abstraction for visualizing and structuring complex software. Procedures, functions, methods and objects are familiar software abstractions that software developers use every day. Software agents, however, are a fundamentally new paradigm unfamiliar to many software developers.

The central idea underlying software agents is that of delegation. The owner or user of a software agent delegates a task to the agent and the agent autonomously performs that task on behalf of the user. The agent must be able to communicate with the user to receive its instructions and provide the user with the results of its activities. Finally, an agent must be able to monitor the state of its own execution environment and make the decisions necessary for it to carry out its delegated tasks. There are two approaches to building agent-based systems: the developer can utilize a single stand-alone agent or implement a multi-agent system. A stand-alone agent communicates only with the user and provides all of the functionality required to implement an agent-based program. Multi-agent systems are computational systems in which several agents cooperate to achieve some task that would otherwise be difficult or impossible for a single agent to achieve. We term these multi-agent systems agencies. Agents within an agency communicate, cooperate, and negotiate with each other to find a solution to a particular problem. Why are They Important

Every day, software developers are tasked with constructing ever larger and more complex software applications. Developers are now building enterprise-wide and global applications that must operate across corporations and continents. More and more corporations need to integrate their information systems with those of their suppliers and customers. New systems must link multiple organizations and multiple application platforms into a unified information management system that uses the World Wide Web and distributed object technologies. Next-generation systems must provide global connectivity through a variety of internets and intranets. Users of these systems will include office and factory workers, suppliers, mobile workers, workgroups, customers, and remote workers. Application platforms will vary from desktop personal computers to large multiprocessor mainframes. The kinds of applications that must communicate and operate with each other will vary in complexity from programs as simple as Intuit's Quicken to complex enterprise applications such as SAP's R 3.

Developing applications for these existing and emerging application domains requires powerful new methods and techniques for conceptualizing and implementing software systems. Intelligent software agents provide a powerful problem-solving paradigm that is well-suited to developing complex enterprise applications. An intelligent software agent is a high-level software abstraction. Building a complex system requires that the developer specify a solution in terms of these high-level abstractions. Implementation of these complex systems simply requires identifying the requisite agents and specifying their behaviors. Why are They Difficult to Build Agents and agent technology have been an active area of research in the artificial intelligence and computer science community for a number of years. Many universities have developed intelligent software agents. A number of companies deliver software agents capable of performing a wide variety of specialized tasks. However, each of these agents had to be handcrafted for a particular application. Building an intelligent software agent is a difficult and time-consuming task that requires an understanding of advanced technologies such as knowledge representation, inferencing, network communications methods and protocols, etc. Sophisticated applications often require expertise in machine learning and machine planning technology.

A developer using intelligent agents in a new application must decide on the overall agent processing architecture, the agent's reasoning (inferencing) mechanism and associated pattern matching technology, internal knowledge and data representations, agent-to-agent communications protocols and message formats. In addition, if the agent is to learn from its environment or its owner then some kind of machine learning technology will be required. Sophisticated agents may require a planning capability and this will require that the developer select a planning algorithm and implementation. If the application requires multiple communicating agents then the developer needs to establish a robust communications protocol between the agents. This will require that the developer have knowledge and expertise in the underlying communications technologies used for interagent communications. Intelligent Agent

For purposes of this invention, an intelligent agent may be considered to be any software program that can operate autonomously (i.e., without user intervention), learn the habits and preferences of the user, take instructions from and communicate with the user and/or other agents, and perform the duties that the user or other agent assigns it. Intelligent agents are specialized to provide a high level of competence and capability in narrow domains. An intelligent agent must be able to develop high-level plans and goals and attempt to satisfy those goals. Early Development

Agent architecture was developed and described by Y. Shoham [Agent-Oriented Programming, Technical Report No. TR STAN-CS-90-1335, 1990, Stanford University; AGENT- 0: A simple agent language and its interpreter, Proceedings of the Ninth National Conference on Artificial Intelligence, Vol. II, pp. 704 - 709, 1991, Anaheim, CA: MIT Press; Agent-oriented programming, Artificial Intelligence, 60(1), pp. 51 - 92, 1993; and CSLI Agent-oriented Programming Project: Applying software agents to software communication, integration and HCI, CSLI Web page, 1995, Stanford University, Center for the Study of Language and Information]. Shoham developed cognitive, i.e., mental model-based, agents and defined an agent programming language (AGENT-0) for writing agent programs. He theorized that cognitive agents possess a mental state which is composed of various mental elements: beliefs, commitments, capabilities, and commitment rules.

Shoham describes two primitive modalities of mental state - belief and commitment. Commitment is treated as a decision to act rather than a decision to pursue a goal. A strong condition is placed on belief; namely that agents have perfect memory of, and faith in, their beliefs and only relinquish a belief if they learn a contradictory fact. Beliefs persist by default. Furthermore, the absence of a belief also persists by default but in a slightly different sense. If an agent does not believe a fact at a certain time (as opposed to believing the negation of the fact), then the only reason the agent will come to believe it is if the agent learns it.

AGENT-0 defines two different action types: private actions and communicative actions. Private actions are the primary method agents use to accomplish tasks that affect the agent's environment. For example, a database agent might include private actions that execute SQL queries on a database. Communicative actions are the mechanism for exchanging messages with other agents.

While agent behavior can be arbitrarily complex, it is produced using relatively simple operations. Agents can receive messages, send messages, perform private actions, and update their own mental models. The behavior of an agent is governed by its program. An AGENT-0 program consists of initial beliefs, initial commitments, the capabilities of the agent, and the commitment rules. Initial beliefs and initial commitments are present in the mental state at agent start-up. Even though initial commitments are instantiated when the agent starts executing, they may not be applicable until some specific time in the future. Capabilities define the actions that the agent can perform and are fixed for the lifetime of the agent. Commitment rules determine the actions performed and the mental changes of the agent in all situations. KQML

The Knowledge Query and Manipulation Language (KQML) is a high-level language intended to support interoperability among intelligent agents in distributed applications. It is both a message format and a message-handling protocol to support run-time knowledge sharing among agents. KQML is an interlingua, a language that allows an application program to interact with an intelligent system. It can also be used for sharing knowledge among multiple intelligent systems engaged in cooperative problem solving. This language, originally developed as part of a DARPA Knowledge Sharing initiative, is becoming a de facto standard for interagent communications languages [Finin, T., Fritzon, R., McKay, D., & McEntire, R., KQML as an agent communication language, Proceedings of the Third International Conference on Information and Knowledge Management (CE M'94), 1994, ACM Press; Finin, T., Fritzson, R., McKay, D., & McEntire, R., KQML - A Language and Protocol for Knowledge and Information Exchange, Technical Report No. CS-94-02, 1994, University of Maryland, Department of Computer Science; Finin, T., Weber, J., Wiederhold, G., Genesereth, M., Fritzon, R, McGuire, J., Shapiro, S., McKay, D., Pelavin, R., & Beck, C, Specification of the KQML Agent-Communication Language plus example agent policies and architectures (DRAFT Report), DARPA Knowledge Sharing Initiative External Interface Working Group, 1994; Labrou, Y. and T. Finin, "A semantics approach for KQML - a general purpose communication language for software agents," 1994, University of Maryland; Labrou, Y., "Semantics for an agent communication language," 1996, Computer Science and Electrical Engineering Department, Baltimore, MD: University of Maryland Graduate School, p. 116]. A KQML message consists of a performative, the content of the message, and a set of optional arguments. The performative specifies an assertion or a query used for examining or changing a Virtual Knowledge Base (VKB) in a remote agent. Needs in the Technology Software developers need a set of tools that will aid them in developing agent-based applications. Tools are needed that can help the software developer analyze the application domain; formally recognize and describe the concepts, relationships and objects relevant to that domain, and specify the behavior of the agent(s) operating in that domain. The software developer also needs tools that can specify a collection of agents; analyze and specify the messages and message protocols between agents; and execute and evaluate the actions of the agents. The tools should be integrated into a toolkit using a graphical user interface to provide these capabilities.

Summary of the Invention In one aspect of the present invention, there is a development system for developing a plurality of communicating software agents, comprising an agency manager adapted to manage a plurality of agent roles, each software agent associated with one or more of the agent roles, an agent manager adapted to define a plurality of rules, each software agent associated with a set of rules, and a protocol manager adapted to define messages which are communicated among the software agents.

In another aspect of the present invention, there is a method of developing message protocols among communicating software agents, the protocol editor comprising creating a plurality of protocol states; creating a plurality of protocol transitions, wherein each transition is associated with a sender agent of a message, a receiver agent of a message, and selected ones of the protocol states; converting the protocol states and the protocol transitions to a protocol state table; and converting the protocol state table to a plurality of agent state tables, each agent state table associated with one of the software agents.

In another aspect of the present invention, there is a development system for communicating software agents, comprising a set of development tools adapted to generate codes for the software agents, and a debugger adapted to permit examination of the mental model associated with the software agents. In another aspect of the present invention, there is a method of developing communicating software agents, comprising displaying a plurality of icons, each icon representative of a plurality of software agents, and graphically viewing messages sent among the software agents.

In another aspect of the present invention, there is a method of developing communicating software agents, comprising creating a plurality of protocol roles; creating a plurality of protocol states; creating a plurality of protocol transitions, wherein each transition specifies one of the agent roles associated with a sender agent of a message, one of the protocol roles associated with a receiver agent of a message, and selected ones of the protocol states; and mapping the agent roles into a plurality of communicating software agents.

In another aspect of the present invention, there is a communicating software agent system, comprising a set of development tools adapted to create, modify and generate message protocols and software codes for a plurality of software agents, and an agent engine adapted to execute the agent codes, wherein the software agents communicate with the message protocols.

In yet another aspect of the present invention, there is a method of developing a plurality of communicating software agents, comprising creating a first software agent, creating a second software agent, and automatically generating communication protocols associated with the first and second software agents thereby allowing the software agents to communicate.

In a final aspect of the present invention, there is a method of developing a plurality of communicating software agents, comprising developing rules for a plurality of software agents, and combining the rules with roles and protocols so as to define the behavior of each software agent when a communication from another software agent is received.

Brief Description of the Drawings Figure 1 is a diagram of an agent mental model as used by an embodiment of the invention. Figure 2 is a high level diagram of the components of one embodiment of the invention.

Figure 3 is a block diagram of a system embodiment of the invention. Figure 4 is a flowchart of an interpreter process for one embodiment of an intelligent agent architecture operating on the system shown in Figure 3.

Figure 5 is a diagram for an Intelligent Agent Construction process using the Agent Creation Toolkit shown in Figures 2 and 3.

Figure 6 is an exemplary display of the components of the Agent Creation Toolkit shown in Figures 2 and 3.

Figure 7 is an exemplary display during operation of the project control tools shown in Figure 6. Figure 8 is an exemplary display during operation of the object modeling tools shown in

Figure 6.

Figure 9 is an exemplary display during operation of the agency viewer tools shown in Figure 6.

Figure 10 is an exemplary display during operation of the protocol editor shown in Figure 6. Figure 11 is an exemplary display during operation of the agent manager shown in Figure 6.

Figure 12 is an exemplary display of the agent manager displaying a behavioral rule.

Figure 13 is an exemplary display during operation of the rule editor shown in Figure 6 for the left hand side of a rule.

Figure 14 is an exemplary display during operation of the rule editor shown in Figure 6 for the right hand side of a rule.

Figure 15 is a flowchart of the process for the Creating Agents with Protocols portion of the Intelligent Agent Construction process shown in Figure 5. Figure 16 is an exemplary display during operation of the project manager for a Buyer

Seller with Protocol agency example.

Figure 17 is a flowchart of the process for the Create Protocol and Rules process shown in Figure 15.

Figure 18 is an exemplary display during operation of the protocol manager for the Buyer Seller with Protocol agency example.

Figure 19 is an exemplary display of a roles dialog for the Buyer Seller with Protocol agency example.

Figure 20 is an exemplary display of a state properties dialog for the Buyer Seller with Protocol agency example. Figure 21 is an exemplary display during operation of the protocol editor for the Buyer

Seller with Protocol agency example.

Figure 22 is an exemplary display of a price request transition dialog for the Buyer Seller with Protocol agency example.

Figure 23 is an exemplary display of a transition properties dialog for the Buyer Seller with Protocol agency example.

Figure 24 is an exemplary display of an assign agents dialog for the Buyer Seller with Protocol agency example.

Figure 25 is an exemplary display during operation of the role editor for the Buyer Seller with Protocol agency example. Figure 26 is an exemplary display during operation of the agent manager showing a set of simple buyer rules for the Buyer Seller with Protocol agency example.

Figure 27 is an exemplary handler rule for the simple buyer of the Buyer Seller with Protocol agency example.

Figure 28 is an exemplary price request message rule for the simple buyer of the Buyer Seller with Protocol agency example. Figure 29 is an exemplary simple seller rule for the Buyer Seller with Protocol agency example.

Figure 30 is an exemplary price request message handler rule for the Buyer Seller with Protocol agency example. Figure 31 is an exemplary display during operation of the agency viewer with buyer seller agents for the Buyer Seller with Protocol agency example.

Figure 32 is an exemplary display during operation of a simple buyer console for the Buyer Seller with Protocol agency example.

Figure 33 is an exemplary display during operation of a simple seller console for the Buyer Seller with Protocol agency example.

Figure 34 is an exemplary display of a simple buyer messages screen for the Buyer Seller with Protocol agency example.

Figure 35 is an exemplary diagram of a conversational protocol represented as a state transition. Figure 36 is an exemplary diagram of condition/action pairs represented as a state transition.

Figure 37 is an exemplary diagram of an agent protocol specification such as developed during the operation of the Create Protocol and Rules process shown in Figure 17.

Figure 38 is an exemplary diagram of a simple agent protocol such as developed during the operation of the Create Protocol and Rules process shown in Figure 17.

Detailed Description of the Preferred Embodiments The following detailed description presents a description of certain specific embodiments of the present invention. However, the present invention may be embodied in a multitude of different ways as defined and covered by the claims. In this description, reference is made to the drawings wherein like parts are designated with like numerals throughout.

An integrated intelligent agent construction toolkit and graphical programming environment is described in Applicant's papers: AgentBuilder White Paper, Version 1.3, htφ://www.agentbuilder.corn/Documentation/white_paper_r L3.pdf, February 1999 (date of document and not necessarily publication on Internet), Reticular Systems Inc.; AgentBuilder User's Guide, Version 1.2, August 1999; and AgentBuilder Reference Manual, Version 1.2, August 1999, all of which are hereby incorporated by reference. Intelligent Agent Architecture

Shoham' s AGENT-0 research was extended by Thomas, who developed PLAnning

Communicating Agents - PLACA [Thomas, S. R., PLACA, An Agent Oriented Programming Language, PhD Thesis, 1993, Stanford University and Thomas, S. R., The PLACA Agent Programming Language, M. J. Wooldridge & N. R. Jennings (Eds.), Lecture Notes in Artificial Intelligence, 1994, pp. 355 - 370, Berlin: Springer- Verlag]. PLACA is an agent programming language similar to AGENT-0 with extensions for planning. Applicant has further extended the work of Shoham and Thomas and has developed a new agent programming language. This object- oriented language is called the Reticular Agent Definition Language (RADL). The Agent Creation system provides graphical tools for creating RADL programs that execute in a Reticular run-time system. The following paragraphs describe one embodiment of the language and agent architecture in more detail. Applicant's mental model 100 is shown in Figure 1 and is further described below. Beliefs 102

Beliefs 102 are a fundamental part of the agent's mental model 100. Beliefs represent the current state of the agent's internal and external world and are updated as new information about the world is received. An agent can have beliefs about the world, beliefs about another agent's beliefs, beliefs about interactions with other agents, and beliefs about its own beliefs. All of the beliefs in the agent's mental model are instantiations of Java classes.

Mental model integrity is improved because beliefs and pattern variables are always of known type, so the agent's inference engine can ensure that comparisons between mental model elements are always valid. This prevents accidental matches between beliefs and variables of differing types. Runtime efficiency is improved because beliefs allow the agent's inference engine to focus its search activities when looking for beliefs that match specified rule conditions. In most situations only one or at most a small subset of the beliefs need be examined. Capabilities 104

A capability 104 is a construct used by the agent to associate an action with that action's necessary preconditions. The necessary preconditions (sometimes known as executability or primary preconditions) are the preconditions that must be satisfied before execution of the action [Thomas, 1993]. An agent's list of capabilities defines the actions which the agent can perform provided that the necessary preconditions are satisfied. A capability is static and holds for the lifetime of an agent. However, the actions an agent can perform may change over time because changes in the agent's beliefs may alter the truth value of precondition patterns in the capability.

For example, consider an agent used to control access to a database. One of the actions of such an agent is to perform queries. A simple capability for a MakeQuery action is:

Action: MakeQuery (database, ?Query)

Preconditions: database. Status IS Online In this example, the precondition is satisfied when the agent believes the database is online. Only then can the execution of the MakeQuery action proceed. Although this capability will not change during the lifetime of the agent, the agent's ability to perform the MakeQuery action will depend on the agent's belief about the status of the database. The Agent Creation agent architecture classifies actions in two main categories, private actions and communicative actions, as did Shoham. Private actions are actions that affect or interact with the environment of the agent and do not depend on interaction with other agents. Communicative actions are defined as actions that send messages to other agents.

Capabilities are used by the agent to decide whether to adopt commitments (described below). An agent will not adopt a commitment to perform an action if the agent can never be capable of performing that action. Capabilities are also used to determine whether a committed action can be executed. Commitments 106

A commitment 106 is an agreement, usually communicated to another agent, to perform a particular action at a particular time. The usual sequence of operations will be as follows: one agent, say agent "Alice", will send a commitment request in a message to another agent, say agent "Betty". Betty will accept or reject the request based on the details of the request, her behavioral rules and current mental model (beliefs, existing commitments, etc.). Finally, Betty will send a message to Alice indicating acceptance or rejection of the request. If Betty accepts the request she agrees to perform the requested action at the requested time, if possible. It should be noted that a commitment is not a guarantee that an action will be performed; more precisely, a commitment is an agreement to attempt a particular action at a particular time if the necessary preconditions for that action are satisfied at that time.

When the current time equals the commitment time (assuming Betty adopted the commitment), Betty must test the necessary preconditions of the committed action to ensure that the action can be executed. Betty must have a capability corresponding to the committed action (otherwise she could not have adopted the commitment), and the capability will have zero or more precondition patterns that define the necessary preconditions for the action. To test the preconditions Betty must match the precondition patterns against her current beliefs. If all patterns evaluate to true, Betty can initiate execution of the committed action. Otherwise she cannot - an agent should not attempt to execute an action for which the necessary preconditions fail even if the agent is committed to that action.

In general, successful execution of an action may be beyond the agent's control. For example, agent Betty may have committed to make an inquiry into a database on behalf of Alice. Even if the necessary preconditions are met (e.g., Betty believes the database is currently functioning) and Betty is able to initiate execution, the action may still fail (e.g., a disk could crash during the database access). Betty must monitor the execution so she will be able to send a message back to Alice to report the success or failure of the commitment. Behavioral Rules 108 In Shoham's model, all actions were performed only as the result of commitments. One embodiment of the invention has extended the idea of a commitment rule 110 (as in Shoham) to include a general behavioral rule, so as to supersede the commitment rules 110. Behavioral rules 108 determine the course of action an agent takes at every point throughout the agent's execution. Behavioral rules match the set of possible responses against the current environment as described by the agent's current beliefs. If a rule's conditions are satisfied by the environment, then the rule is applicable and the actions it specifies are performed.

Behavioral rules 108 can be viewed as WHEN-IF-THEN statements. The WHEN portion of the rule addresses new events occurring in the agent's environment and includes new messages received from other agents. The IF portion compares the current mental model with the conditions that are required for the rule to be applicable. Patterns in the IF portion match against beliefs, commitments, capabilities, and intentions. The THEN portion defines the agent's actions and mental changes performed in response to the current event, mental model and external environment. These may include:

• mental model update • communicative actions

• private actions

A behavioral rule is allowed to have any combination of the possible actions outlined above. The following listing describes the format for the behavioral rules 108: NAME rule name WHEN

Message Condition(s) IF

Mental Condition(s) THEN Private Action(s)

Mental Change(s) Message Action(s) Behavioral Rule Example

The following paragraphs provide an example and a description of behavioral rules 108. The agent used in this example is a seller agent representing a grocery store in an electronic marketplace. One of the agent's behavioral rules is shown along with a snapshot of the agent's mental model at a particular point in time.

The agent's mental model in this example is composed of several user-defined PAC instances (e.g., InventoryRecord and SellerFrame instances), several built-in PAC instances (e.g., Time and Agent instances), and two Java instances. Some of the instances are named instances, such as the currentTime and accounfBalance instances. Some of the instances are not named, such as the InventoryRecord instances. The currentTime instance is marked with a * to indicate that it changed during the last cycle. Table 1 shows an exemplary agent's mental model.

TABLE 1 - Agent's Mental Model (Beliefs)

Mental Model (Beliefs) Time<currentTime> Mon Jun 08 14:23:08 PDT 1998 Time<startupTime> Mon Jun 08 14:22:44 PDT 1998 Agent<SELF> Agent Name: Store 2 Address: harding.reticular.com Agent<Buyer> Agent Name: Buyer Address: quincy.reticular.com

Agen Store 1> Agent Name: Store 1 Address: harding.reticular.com InventoryRecordo ProductName = Milk, Quantity = 41 gallon, UnitPrice = 2.24 InventoryRecordo ProductName = Bread, Quantity = 28 loaf, UnitPrice = 2.33 InventoryRecordo ProductName = Bananas, Quantity = 32 lb., UnitPrice = 0.55 SellerFrame<sellerFrame> com.reticular.agents.buyerSeller.SellerFrame

[framel,780,136,467x428,layout=java.awt.GridBagLayout,resizable, title=Store 2 agent on harding.reticular.com] Float<accountBalance> 204.48 Boolean<Interface_ready_to_print> true

This mental model contains three Agent beliefs, one for the store agent called the Store 2 agent and two other known agents. There are three InventoryRecord beliefs, one for each product sold by this store. The SellerFrame is a graphical interface (derived from java.awtFrame) used to display the store agent's activities to the user. The mental model contains a belief about the store's current account balance, stored in a Float object, and a belief about the status of the graphical interface.

The rule shown below in Table 2 is used to accept a message containing a price quote request from a known buyer agent, fill in this store's price, then return the message to the buyer agent. This is just one rule of approximately a dozen rules that define the behavior of this agent in a highly simplified electronic marketplace. TABLE 2 - Example Rule "Receive Bid Request" WHEN 1. ( %message.sender EQUALS ?buyer.name )

2. ( %message.performative EQUALS "ask-one" )

3. ( %message.contentType EQUALS PriceQuote )

4. ( %message.content.producfName EQUALS ?inventoryRecord.productName )

5. ( %message.content.quantity <= ?inventoryRecord.quantity ) IF

1. ( Interface_ready_to_print EQUALS true ) THEN

1. ( DO PrintStatus( Concat( "Sent price quote to ", %message.sender )) )

2. ( SET_VALUE_OF %message.content.price TO ?inventoryRecord.unitPrice ) 3. ( SET_VALUE_OF %message.content.storeName TO SELF.name )

4. ( DO SendKqmlMessage( %message, SELF.name, %message.sender, "tell",, %message.replyWith„„„) )

5. ( DO SleepUntilMessage() )

The WHEN section of the rule is used to test an incoming message from another agent and the IF section of the rule is used to test conditions in this agent's mental model. All of these conditions in the WHEN and IF sections are implicitly ANDed together, i.e., the set is satisfied if and only if all conditions are satisfied. If any condition is not satisfied then the rule is not applicable to the situation. Evaluation stops as soon as a single condition fails. If, however, all conditions are satisfied then the rule will be activated and then its actions and mental changes are put on the agenda for execution. In this example the rule will send a return message containing a complete price quote to the buyer agent that sent a price quote request.

The "%message" is a variable of type KqmlMessage; the leading character "%" is used to indicate that this is a message variable which binds to incoming messages. The dot-separated list following a variable name represents subobjects, or subobjects of subobjects, etc. In the first pattern, for example, %message.sender accesses the sender field (a String) of the KqmlMessage binding. In the fourth pattern, %message.content.productName means "bind to an incoming message, then access the content subobject of the message, then access the productName subobject of the content". The "?buyer" is a variable of type Agent, which is a built-in class provided with the Agent

Creation Toolkit to represent beliefs about agents (e.g., name, address, etc.). The leading character

"?" is used to indicate that this variable binds to Agent instances in the mental model.

?buyer.name evaluates to a String, so the first pattern in the WHEN section is a comparison between the String objects bound to two variables.

The second pattern in the WHEN section is similar to the first except that it compares a field in the message to a String constant. If evaluation of the first pattern is successful then evaluation proceeds to the second pattern, using the same binding for the %message variable as was used in the first pattern. The third pattern checks the type of the content of the message and compares it to the

PriceQuote class, which is a PAC designed for this problem domain. If the content object is a PriceQuote object then rule evaluation proceeds to the fourth pattern. The fourth pattern checks the value of one subobject in the content of the message.

The "?inventoryRecord" is a variable of type InventoryRecord, another PAC designed for this problem domain. This has fields for productName, quantity, and unitPrice. The fifth WHEN condition compares the quantity field in the PriceQuote from the message with the quantity field in an InventoryRecord in the mental model. Note that the InventoryRecord binding used in pattern 5 is the same binding that was used in pattern 4. The quantity field in the InventoryRecord which has the same product name as the PriceQuote in the message is tested. The first and only IF condition in this rule is a test of a named instance. This pattern evaluates to true if the mental model contains a Boolean instance named "Interface_ready_to_print" with a value of true. The Boolean instance needed by this pattern gets asserted by another rule, the Launch Interface rule, which fires before the Receive Bid Request rule. The left-hand side of the Receive Bid Request rule can be paraphrased as follows, from the point of view of the store agent:

WHEN I receive a KQML message sent from a known buyer agent, and the performative in that message is "ask-one", and the content type in that message is PriceQuote, and the product name in the message's PriceQuote is the same as the product name in one of my InventoryRecords, and (according to that same InventoryRecord) I have at least as much product on hand as the quantity requested in the PriceQuote, and IF the interface is ready to receive a PrintStatus command, THEN ...

The THEN section of this example rule consists of three actions and two mental changes.

The first THEN pattern is an action statement with the user-defined action PrintStatus. This invokes a method on the SellerFrame interface PAC, which prints the status of the store agent so the user can follow the progress of the transaction. The argument for the PrintStatus action is constructed using the built-in Concat function, which concatenates two strings into a single string.

The next two THEN patterns modify fields in the KQML message that was tested in the WHEN section. The first pattern fills in the price field of the PriceQuote content object, using a value from the same InventoryRecord object used in patterns 4 and 5 in the WHEN section. Next, the storeName field in the PriceQuote content object is filled in using the agent's belief about its own name, taken from the SELF Agent belief. The SELF belief is automatically added to the agent's mental model by the run-time system.

After the message has been modified, it is sent back to the buyer agent via the built-in action SendKqmlMessage. This action takes several arguments such as message, sender, receiver, performative, etc. The ordering of the arguments may be difficult to understand in a printed example such as this, but they are easy to specify in the Rule Editor.

In this example, the received message is being sent back to the buyer, the sender is now the store agent (i.e., SELF .name), the receiver will be the original sender (i.e., %message.sender), the performative is "tell", and the reply-with field of the original message is used to set the in-reply-to field of the new outgoing message. The empty argument slots indicate that all other fields in the message should be left as they are (the content object has already been changed from its original values by the SET_VALUE_OF statements).

Finally, after the content object has been updated and the message sent back to the buyer agent, the store agent goes to sleep by invoking the built-in SleepUntilMessage action. The store agent will automatically be re-awakened by its controller when another message is received. Intentions

An intention is an agreement, usually communicated to another agent, to achieve a particular state of the world at a particular time. Intentions are similar to commitments in that one agent performs action(s) on behalf of another. However, a commitment is an agreement to perform a single action whereas an intention is an agreement to perform whatever actions are necessary to achieve a desired state of the world.

Requests containing intentions allow agents to communicate in terms of high-level goals and allow the receiving agent (the one who adopts the intention) the freedom to achieve the state of the world using whatever actions are appropriate for that agent. This is more efficient and more robust than requesting a specific sequence of commitments. The agent performing the actions has a better understanding of its own area of expertise within the problem domain and may be able to skip unneeded actions, redo actions when necessary, find alternate actions that will achieve the goal, etc. In order to achieve the goal specified by an intention, the agent must be able to construct plans to achieve that goal, monitor the success of the actions performed, and construct alternate plans if the original plan fails. Thus, support for processing intentions requires an additional level of sophistication and capability in the agent. Component and Run-time System Overview

Referring to Figure 2, a high level view of an Agent Creation system 200 will be described. The system 200 has a Agent Creation Toolkit module 210 and a Run-time system portion 215. The Run-time system 215 includes an Agent Program 220 and a run-time agent engine 230 available from Reticular, Inc. The Agent Program 220 is a combination of an Agent Definition defined in a RADL file and a set of classes defined in the agent's Project Accessory Class (PAC) library (i.e., Agent Actions and User Interface libraries). The Agent Program 220 is executed by the run-time agent engine 230. The combination of the Agent Program 220 and the agent engine 230 produces an executable agent.

At start-up, the Run-time system initializes the agent engine 230 using information stored in the Agent Definition file and links the required components from the PAC Library. Both the agent definition and the private actions are needed: the agent definition supplies the agent with a reasoning capability and an initial mental model; the private actions give the agent the ability to interact with its environment.

Referring to Figure 3, the Agent Creation system 200 permits an agent to be created in a development environment 320, such as a Java Development Environment, and then be deployed as a stand-alone entity executing in a run-time environment 330, such as a Java Virtual Machine. The Agent Creation Toolkit 210 runs in the development environment 320 and generates user-defined classes 322 and an agent definition file 324.

Note that it is the agent executing in the Run-time System that performs useful work. The Run-time system 215 is distinct from the Agent Creation Toolkit 210. After the agent development process is completed, an agent can be executed on any platform with a Java Virtual Machine (version 1.1 or later). The Run-time system does not require access to the Java Development Environment 320. Only the user-defined classes 322 and the Agent Creation libraries 332, along with the Agent Definition file 324, are required for runtime execution of agents by the engine 230. In one embodiment, the agent engine 230 is a proprietary inferencing engine available from Reticular Inc., and is implemented in Java. This engine 230 utilizes an efficient and robust inferencing procedure to match the agent's behavioral rules with the agent's beliefs and incoming messages. The agent engine 230 performs the reasoning defined in the Agent Definition file 324 and executes the specified actions, by invoking routines in the Private Action library. The agent engine also monitors the execution of the private actions and returns execution results to the agent. Protect Accessory Class (PAC) Libraries

In one embodiment, an agent's PACs contains all of the domain-specific code an agent requires for operation in its domain. The PAC is the mechanism that the agent uses to interact with its environment; by calling methods, the agent executes its private actions. Generally, agents operate in unique domains, and every domain requires its own PACs.

A PAC may be made of classes and packages from a variety of sources. The developer may write part of the library, other classes may come from commercial off-the-shelf (COTS) packages, and other classes might be freeware downloaded from the Internet. Although the developer can write PACs entirely in Java, there are situations where Java alone does not meet the needs of an application. Developers may use the Java Native Interface (JNI) to create non- Java methods to handle those situations when an action cannot be implemented in Java; C/C++ functions that conform to the JNI can be used to implement private actions. The developer is free to create new methods and/or integrate existing code (Java, C or C++) into the PAC library. This database-query method can either be written by the agent developer (in Java, C, or C++) or obtained as part of a COTS database package. Either way, the method is invoked as the agent's private action and executed in the Run-time System.

Not all private actions are suitable for running on the agent's execution thread i.e., as part of the sequence of instruction execution within a computational process. Actions running on the same thread as the agent must execute relatively quickly, because the agent is blocked until the private action finishes execution. To prevent blocking, it can be appropriate to run a private action on its own thread. Allowing actions to run on their own threads provides for long-running private actions without interfering with the basic agent cycle. For example, GUI elements usually require execution on a separate thread because of their long-running nature.

The private actions in the PAC are able to communicate information back to the agent in two ways. For non-threaded actions, information is usually returned to the agent via a return value. For threaded actions, information can only be returned to the agent in a message. For example, a GUI element can send messages back to an agent as the user enters information. Agent Creation and Run-Time System Requirements

In certain embodiments, developers usually utilize some kind of Java development environment. Example environments include Javasoft's Java Development Kit (JDK) available from Sun, IBM's VisualAge, Visix's Vibe, Symantec's Cafe or Inprise (Borland) JBuilder. A developer can easily use these general purpose Java development tools to create user interfaces (GUIs) and PACs. The Agent Creation system 200 makes it easy to import the classes created with these tools into the Agent Creation agent construction environment. The Agent Creation system 200 is distributed with the Java Runtime Environment 330 (JRE) for each supported platform. A Java virtual machine is included with the JRE. Both the Agent Creation Toolkit 210 and the Run-time System execute on this Java Virtual Machine.

In one embodiment, both the development environment 320 and the virtual machine/runtime environment 330 execute on a single computer or workstation 310. In another embodiment, the development environment 320 and the virtual machine/runtime environment 330 execute on different computers or workstations, which may be connected via a network connection 342 to a network 340, such as a local area network (LAN), a wide area network (WAN), an intranet, an extranet, the Internet, and so forth. In one embodiment, the operating system requirements for a personal computer 310 are either Windows 95/98 or Windows NT. The recommended minimum hardware is a Pentium 200 MHz processor with a minimum of 32 MB of RAM. While the Agent Creation system 200 will run on slower computers with less memory, it will run very slowly.

In other embodiments, for workstations 310, Solaris, LINUX and IRIX are currently supported. Other UNIX platforms will be supported as the appropriate JREs become available. Solaris 2.5.1 or higher is currently supported, and the recommended hardware is a SUN SPARC processor or higher with 64 MB of RAM. For LINUX, the i386 LINUX port is the currently supported platform, with the recommended hardware being at least a Pentium 200 MHz processor with 32 MB of RAM. For IRIX, IRK 6.2 or higher is supported, with the recommended hardware being at least a MIPS 133 MHz processor with 64 MB of RAM. Agent Interpreter

Referring to Figure 4, one embodiment of an intelligent agent architecture and execution process 400 will be described. In this architecture, an interpreter continually monitors incoming messages 432, such as from an external environment 430, updates the agent's mental model 100 and takes appropriate actions.

At start-up, an agent is initialized with initial beliefs, initial commitments, initial intentions, capabilities, and behavioral rules at state 410. A non-trivial agent requires at least one behavioral rule; the other elements are optional. For example, if an agent has no initial commitments, then the agent is not initially committed to doing anything (for itself or anyone else). The same logic applies to initial beliefs and initial intentions. If the capabilities list is empty the agent will not be able to perform any actions.

The mental model 100 contains the current beliefs, commitments, intentions, capabilities and rules of the agent. Although rules and capabilities are static, the agent's beliefs, commitments and intentions are dynamic and can change over the agent's lifetime. An agent execution cycle 412 may include the following steps: processing new messages (state 414) determining which rules are applicable to the current situation (state 416) executing the actions specified by these rules (state 418) updating the mental model in accordance with these rules (state 420) planning (state (422)

Processing a new message, e.g., incoming message 432, at state 414 requires identifying the sender and determining the sender's authenticity; then the message is parsed and made part of the mental model 100. The next step at state 416 is determining which rules match the current situation. Pattern matching compares the elements of the mental model 100 with conditional patterns in the behavioral rules to determine which rules are satisfied. A rule is marked for execution when all of its conditions are satisfied; the rule is then placed on the agent's agenda for execution. Rule execution at state 418 consists of performing private and communicative actions and making mental changes. During execution, all of the actions (private and communicative) are executed sequentially.

Next, the agent's mental model 100 is updated at state 420 by adding mental elements (assertions) or removing mental elements (retractions) as specified by the executing behavioral rules. The final step at state 422 in the agent cycle requires developing a plan for the agent. Planning is performed by a planning module attached to the agent. An agent's planning module must develop plans that satisfy goals specified by the agent's intentions.

States 414 (processing new messages), 418 (executing the actions specified by the rules) and 422 (planning) are under control of a scheduler 424. State 422 provides an input to the scheduler 424. The scheduler 424 ensures that appropriate actions are performed at the appropriate time in the agent cycle 412.

Agent Communication Language

Agent Creation agents provide support for all of the performatives specified for the Knowledge Query and Manipulation Language (KQML). Of course, other embodiments could be implemented with other messaging languages. Agents constructed with the Agent Creation system may communicate and interoperate with any other agent who also "speaks" KQML. Thus, Agent Creation agents may communicate with existing agents or agents constructed using other methods, tools and architectures other than those supported by the Agent Creation system.

KQML is further described in Chapter 3 (pages 53-67) and in Appendix A (pages 243-257) of the AgentBuilder User's Guide, Version 1.2, Rev. 0, which was previously incorporated by reference. Agent Development Process

As noted in the previous discussion, specifying an agent's mental model requires defining its initial beliefs, initial commitments, capabilities and behavioral rules. The key to building intelligent agents is having an efficient mechanism for specifying behavioral rules and other components of the mental model. The Agent Creation Toolkit 210 (Figure 3) provides a graphical interface for easily and quickly defining a collection of agents and specifying their mental models and behaviors.

Developing an intelligent software agent is similar to other software development activities in that the software developer must perform the traditional steps of analysis, design, implementation, testing and debugging, integration and maintenance. In many ways agent software development is similar to object-oriented software development.

A software developer using traditional object-oriented programming techniques must identify the objects of interest and specify the various interactions among those objects. The developer can define objects as very high-level abstractions (e.g., a bank account) or very low- level abstractions (e.g., a push button in a graphical user interface).

In contrast, developing intelligent software agent programs (sometimes called agent- oriented programming) consists of identifying the roles and functions of various agents and then specifying each agent's behavior. Agent-oriented programming is very similar to object-oriented programming except the software developer works with complex entities (agents) at much higher levels of abstraction than is normally done in object-oriented programming. It is much easier for a software developer to develop complex software and systems using these high levels of abstraction. After this high-level analysis and design is complete, standard object-oriented analysis and design techniques can be used to develop the agents and the lower-level objects that agents manipulate and reason about. An agent-programming language is a high-level language used to specify the behavior of the agent for any given situation. The Agent Creation Toolkit 210 (Figure 3) provides an object- oriented language called RADL (Reticular Agent Definition Language) to create agent programs. The RADL is further described in an Extended Backus Normal Form (BNF) in the Appendix. Of course, other embodiments could be implemented with other computer languages. An agent engine (i.e., agent execution environment) is required for executing the agent program. This engine (e.g., engine 230) must be able to execute on a wide variety of platforms, provide high performance, and support creation of sophisticated agent-based application programs.

The Agent Creation system 200 provides facilities for creating agent-based applications programs and includes tools for: organization and control of the development project problem domain analysis agency architecture definition defining agent roles and communications protocols importing code (e.g., Java) and using it for implementing agent user interfaces and accessory classes specifying agent behavior executing the agents viewing and debugging executing agents

The following paragraphs describe this process in more detail. Referring to Figure 5, a process 500 of intelligent agent construction using the Agent Creation Toolkit will now be described. Organize Project 502 Developers of agent-based software create intelligent agents for a variety of uses and applications. The Agent Creation tools allow the developer to organize projects and associate particular agents and collections of agents (i.e., agency) with those projects at state 502. Developers can reuse agents developed for one project on a related project.

Likewise, developers will reuse domain knowledge gained in the course of analyzing a particular domain. For example, a developer building an e-mail agent will develop an ontology for e-mail and can then reuse this e-mail ontology on a new project requiring development of a spam- filtering agent. Analyze Problem Domain 504

The developer will perform an analysis of the problem domain at state 504 in order to understand the functional and performance requirements of his agents and agent-based solution. The Agent Creation system 200 provides tools for analyzing and structuring the domain and codifying information about that domain. Domain analysis is facilitated using conceptual mapping tools and object modeling tools. An object model specifies all of the objects in the domain and the operations they can perform. Another product of the domain analysis is an ontology 506 for that particular domain. This ontology is a formal description of the problem domain.

An ontology gives meaning to the symbols and expressions used to describe a domain. For one agent to properly understand the meaning of a message from another agent, both agents must ascribe the same meaning to the symbols (constants) used in that message. The ontology 506 maps these symbols to a well-understood meaning for the problem domain [FTP A Foundation for Intelligent Physical Agents, "FIPA 97 Specification Part 1 Agent Management," Specification

October 10, 1997].

Define Agency Architecture 508

After completing the domain analysis, the software developer normally decomposes the problem into functions that can be performed by one or more intelligent agents at state 508. The developer identifies each agent and its role in solving the overall problem. The developer can then create a skeletal agent and define the basic characteristics of that agent with respect to its interaction with other agents.

Define Agent Roles and Communications Protocols 510 The developer defines agent roles and communications protocols at state 510. A role defines the characteristics or expected social behavior of an agent. For example, in an e-commerce application, an agent might take on the role of buyer or seller. Often, agents take on multiple roles. For example a broker agent might take on the roles of both buyer and seller. It is also important to separate the physical implementation of an agent from the roles of that agent. This provides significant flexibility in designing and implementing an agent-based system. The Agent

Creation Toolkit 210 provides a role editor for defining roles and assigning roles to a specific agent.

After identifying the agents and their roles, the agent developer defines the interagent communication protocols. The Agent Creation Toolkit provides a Protocol Editor that make it easy for the developer to specify the messages and handshaking required between agents. Defining agent roles and communications protocols will be further described below in conjunction with a

Create Protocols and Rules process 1510 (Figure 17).

Specify Agent Behavior 512

After completing the agency definition, the developer then specifies the behavior of each agent. Agent development is the process of defining agent behavior. Agent Creation provides tools for specifying behavioral rules, initial beliefs, commitments, intentions, and agent capabilities.

The toolkit aids the user in developing the requisite code for specifying agent behavior.

For example, Agent Creation Toolkit automatically converts the agent protocols (defined using the Protocol Editor) into skeletal behavior rules that implement the agents conversational protocol.

This feature will be further described in conjunction with Figure 15. In one embodiment, this feature includes a process 505 for Creating Agents with Protocols which corresponds with states

506, 508, 510, and 512.

The Agent Creation Toolkit produces an Agent Definition file 514 that contains a detailed specification of the agent's initial mental model and behavior. This definition file 514 may be combined with a User Interface Library 524 and/or a Project Accessory Class Library 526 to generate the Agent Program 220.

Import Java Code for User Interfaces and Accessory Classes 520-526

The Agent Creation Toolkit 210 makes it easy to add a user interface to an agent. While many agents may not require interaction with a user, in many cases it is desirable to add a graphical interface to control agent operations, display agent status, and enter and display data. In one embodiment, one may use Sun's JDK or any of a variety of third party development kits for creating a user interface at state 520. The Java code may be integrated with the ontology description at state 522 to produce the User Interface Library 524. In many cases it is desirable to have the agent execute procedural code. Project Accessory

Classes (PACs) are user-defined classes that the developer can use for this processing. Developers may use this code to implement a variety of different functions and operations. In certain embodiments, a number of PACs for performing common functions such as FTP, HTTP, e-mail, NNTP and document analysis may be implemented. PACs can be coded in Java or C and C++ code can be utilized through the Java Native Interface (JNI). PACs provide an ideal mechanism for allowing agents to utilize legacy code. The PACs may be used to form a Project Accessory Class library 526. Of course, other computer languages may also be used. Agent Program 220

The Agent Program 220 fully specifies agent activities and behavior and is executed by the Run-time Agent Engine 230. The Agent Program 220 receives input from the Agent Definition file 514, the User Interface Library 524 and/or the Project Accessory Class Library 526. The Agent Program 220 may be embodied as a flat text file called a Reticular Agent Definition Language (RADL) file. Create Agent Application 530 The final step in the agent construction process includes loading the Agent Program into the Run-time Agent Engine 230. The Agent Engine 230 is a high-performance execution mechanism that interprets the Agent Program 220 and performs the actions specified in the user interface and agent actions libraries. An Intelligent Agent Application 530 is composed of the Agent Program 220 and the Run-time Engine 230. The Run-time Engine 230 was previously described above. The user may run or execute the agents at a state 532. Agent and Agency Debugging 534

The Agent Creation Toolkit 210 provides tools that support all phases of the software agent development process. The Agent Creation Toolkit provides an environment for integrating agents to form agencies and then controlling the execution of the agents. In agent-oriented programming, low-level source code debugging is not necessary because the developer works with a high-level abstraction - the intelligent agent. However, a capability for high-level debugging of the agent's interactions may be required. In certain embodiments, the Agent Creation Toolkit permits the developer to examine the contents of all messages transmitted between agents and start, stop and pause agent execution by use of a Debugger 534. Toolkit and Run-time Agent System Introduction to Agent Creation

The Agent Creation system 200 (Figure 2 and 3) consists of two major components - the Toolkit 210 and the Run-time System 215. The Agent Creation Toolkit 210 includes tools for managing the agent-based software development process, analyzing the domain of agent operations, designing and developing networks of communicating agents, defining behaviors of individual agents, and debugging and testing agent software. The Run-time System 215 includes the agent engine 230 that provides an environment for execution of agent software.

In one embodiment, all components of both the Agent Creation Toolkit 210 and the Runtime System 215 are implemented in Java. This means that agent development can be accomplished on any platform that supports Java and has a Java development environment. Likewise, the agents created with the Agent Creation Toolkit 210 are Java programs so they can be executed on any Java virtual machine. Software developers can create powerful intelligent agents in Java that execute on a wide variety of computer platforms. The Toolkit 210 and the Run-time System 215 are further described in the following paragraphs. Figure 6 shows the major components 600 of the Agent Creation system and their relation to each other.

One specific embodiment of the Agent Creation system is described in the following paragraphs; however, it will be understood that skilled technologists could implement the inventive system in a variety of ways. The invention is not limited to the specific details of the described system. Agent Creation Toolkit

The Agent Creation Toolkit 210 is designed to provide the agent software developer with an integrated environment for quickly and easily constructing intelligent agents and agent-based software. Project Control Tools Project Control Tools are provided to help the agent developer manage the overall agent development process. These tools include a Project Manager and a Project Repository Manager.

The Project Manager allows the developer to identify and manage multiple agent development efforts. For example, a developer can concurrently develop a travel reservations system and a banking application. Although these are very different applications with different agents and agent architectures, the developer needs a way to share information between these two projects. The project manager allows the developer to assign particular agents and agencies to a project and to share information between projects.

All information entered into the various Agent Creation tools is maintained in a persistent store called the Agent Creation Repository. Tools are provided for accessing and modifying this repository. The tools provide the capability to connect and utilize any repository in accordance with defined access permissions. The Project Repository Manager controls access to all of the data created using the Agent Creation Toolkit. This data includes domain knowledge, agent definitions, agency specifications, etc. These tools allow information to be stored and used by multiple projects. Figure 7 illustrates a control panel for the Project Manager. Note that the panel provides a convenient display of all projects, their associated agencies, and agents.

Ontology Manager

The Ontology Manager assists the developer in analyzing the agent application problem domain and in identifying and defining the concepts relevant to the agent's operation in that domain. An ontology is a (formal or informal) specification of a conceptualization. For example, the software developer may want to develop an ontology that describes the e-mail domain or perhaps an electronic commerce domain. The Ontology Manger provides tools for visualizing domain concepts and relationships, graphically representing these concepts and relationships, and codifying them for storage and subsequent retrieval. The Ontology Manager provides the developer with a graphical mechanism for creating, defining, and refining concepts and relations in the agent's application domain. The Agent

Creation Toolkit provides a number of tools for ontology development. These include a conceptual mapping tool that graphically shows the major domain concepts and their relationships.

An object modeling tool provides a mechanism for the developer to take the concepts identified using the conceptual mapping tool and express these concepts in terms of objects and relationships between objects defined in the domain.

The Ontology Manager also produces a knowledge and data representation that can subsequently be used by the Agent Toolkit during agent construction. For example, an ontology for an airline reservations systems might include concepts such as passenger, ticket, reservation, price, arrival time, departure time, etc. The travel ontology provides a formal, consistent representation of an airline travel domain which the agent developer can use in defining agent behavior.

Ontologies can be reused; ontologies developed on one project can be reused on a second project. An ontology library is a collection of related ontologies. These libraries provide a foundation for building intelligent software agents and predefine many of the concepts and relations that are encountered in agent applications development.

The Agent Creation system 200 fully supports object-oriented analysis and design methodologies. Agent Creation agents can reason about objects and agents can communicate by sending and receiving complex objects (not just simple strings). Figure 8 illustrates an Object Modeling tool, one of the Agent Creation tools provided for analyzing and characterizing the agent domain. In the figure, the object modeling tool is used to display the default classes provided with the Agent Creation tools. Note that the object modeler uses UML notation. The developer can use these graphical tools to show the project's classes and their relationships. The developer may graphically establish associations, aggregation (whole-part relationships) and generalization (inheritance). Agency Manager

An Agency Manager is designed to help the developer construct an agency. An agency consists of two or more agents that communicate and cooperate with each other to perform some task. The agents may be identical or specialized for performing different functions. The Agency Manger allows the developer to identify and characterize all of the agents and agent types in the system under development.

The Agency Manager provides a run-time window for viewing the operation of a system of agents. Thus, the developer can monitor interagent communications, control the agents, or run the agent debugger to examine the state of any or all agents.

Figure 9 shows a run-time window viewing a pair of agents used in a shopping application. This tool provides controls for starting, stopping each agent and examining the messages transmitted between agents. Protocol Manager A Protocol Manager provides tools to specify the messages and conversational protocols between agents. This allows the developer to dictate the high-level information flow that occurs as part of agent-to-agent transactions. These tools are indispensable when the agent's conversational protocols are complex. The specification of interagent communication messages and conversational protocols provides the basis for specifying an individual agent's behavior. In one embodiment, the Agent Creation Toolkit automatically generates the skeletal behavioral rules for implementing the agent-to-agent conversations. This capability will further discussed in conjunction with Figure 17. This feature saves the developer significant amounts of time because he/she no longer has to generate the code for handling incoming messages and transmitting outgoing messages. The developer now only needs to specify the conditions necessary for sending a particular message and the actions to be taken and mental model changes needed on receiving an incoming message. Figure 10 illustrates the use of the Protocol Editor in diagramming the conversations involved in solving a producer consumer problem. Agent Manager

An Agent Manager provides tools for defining an individual agent's initial mental model and behavior. The agent definition tools include graphical editors for defining the various mental constructs that make up the agent: initial beliefs, initial commitments, capabilities and behavioral rules. An Agent Manager control panel is shown in Figure 11. The tabbed display panel allows the developer to easily examine the properties, PACs, PAC Instances, Java Instances, Actions, Commitments and Rules for a particular agent. The Agent Manager is used to create an agent definition file written in the Reticular Agent

Definition Language (RADL). The RADL file is a complete specification of the agent's behavior and initial mental model; this file is interpreted and executed by the Run-time System. Commitment Editor

A commitment editor portion of the Agent Manager is used to specify commitments for an agent. By specifying commitments, the developer instructs the agent to pursue certain actions at certain times. All commitments, including initial commitments, have a time field that specifies when the agent will perform the action specified by the commitment. Action Editor

An action editor in the Agent Manager allows the developer to associate agent actions with methods in software libraries. The developer can browse the previously defined object model and choose objects and methods to associate with agent actions.

The action editor allows the developer to specify that an action will execute on its own thread, so the agent can implement long-running actions. For example, a control panel might require a thread that lasts for the lifetime of the agent. Rule Editor

The Agent Manger also includes a behavioral rule editor. The behavioral rule editor defines how the agent operates given a particular internal and external environmental state. Figure 12 shows the Agent Manager with the Rules tab selected.

The behavioral rules are made up of message conditions, mental conditions, private actions, communicative actions and mental model changes. The rule editor permits the developer to graphically build up the WHEN-IF-THEN portions of a rule. Figure 13 illustrates use of the Rule Editor. Figure 13 illustrates the left-hand-side (LHS) editor. Figure 14 illustrates the right- hand-side (RHS) editor. The LHS editor builds the WHEN and IF portions of a rule, and the RHS editor builds the THEN portions of the rule. The LHS panel of the Rule Editor allows the developer to specify operators (e.g., EQUALS), Instances, New Variables, Defined Variables and Values for use in the LHS of the behavioral rule. The Message Conditions section of the LHS editor is used by the developer to build the WHEN portion of the rule. Each message condition consists of a KQML property and an associated value. The developer may build up arbitrarily complex patterns using the provided operators such as AND, OR, or NOT.

The IF portion of a rule is constructed in the Mental Conditions section of the LHS editor. The developer constructs a list of mental conditions using any combination of beliefs, intentions, commitments, messages, and variables. The developer is able to build up arbitrarily complex patterns using the provided operators:

Boolean (AND, OR, NOT)

Relational (>=, <=, >, <, !=, =)

Quantifiers (FOR-ALL, ELEMENT-OF, EXISTS)

Math (+, -, *, /, SQRT, LOG, etc.) • String (CONCATENATE, SUBSTRING, etc.)

The editor for constructing the RHS of the rule allows the developer to specify Operators, Actions, Built-in Actions, Defined Variables, Return Variables, Instances and Values. The Built-in Actions button allows the developer to select the private actions that will execute when the rule fires. The available actions are selected from the list of capabilities constructed earlier in the action editor. The developer selects the action, selects parameter values, and selects return variables from the provided pull-down menus. The return variable stores the value returned by the private action for subsequent use.

The Build Message section of the editor is used for constructing KQML messages. The developer uses the menus to construct outgoing messages using received messages and mental elements.

The Mental Change section allows the developer to specify changes to the mental model which should occur in response to the rule firing. The developer can choose from the previously specified pattern variables, beliefs, and message contents; these elements specify the changes that will be made to the mental model at run time. Planning and Learning

There is no single learning algorithm or planning algorithm that is best suited for use in all agent applications. Therefore, the Agent Creation Toolkit is designed to make it easy for the agent developer to add the learning or planning algorithm that is most appropriate for the problem domain. Creating and Running Agents Using Protocols

This section provides detailed information on constructing agents that use a communications protocol, including:

• Roles and protocols • Protocol Editor

• Agency Viewer

• Debugging Agencies

Two agents, a Simple Buyer agent and a simple Seller agent, are created using agent interaction protocols. This section describes:

• Creating the "Simple Buyer Seller with Protocol" agency.

• Creating the "Simple Buyer 2" and the "Simple Seller 2" agents.

• Constructing the "Simple Buyer Seller Protocol" which is an interaction protocol.

• Applying the protocol to the "Simple Buyer Seller with Protocol" agency. • Finishing the "Simple Buyer 2" and the "Simple Seller 2" agents.

• Running the agents using the Agency Viewer tool.

This example demonstrates how to build two agents that communicate with each other using the built-in agent communication subsystem. The agents will communicate with each other using a protocol built using the Protocol Editor. The protocol specifies how the agents interact when they are involved in negotiation. In this example, the content of the messages is the PriceRequest PAC from the Simple Buyer and Seller ontology. The basics of the interaction are that the Simple Buyer sends a partially completed PriceRequest PAC and the Simple Seller completes it and returns it. Chapter 10 of the AgentBuilder User's Guide, Version 1.2, provides more information about the Simple Buyer and Simple Seller interaction.

Referring to Figure 15, the process 505 for creating agents with protocols will now be described. Process 505 conesponds with states 506 to 512 of Figure 5. Beginning at a start state 1502, process 505 moves to state 1504 to create an agency. In this example, a "Buyer Seller with Protocol" agency is to be created. The specific steps in one embodiment are as follows: Go to the Project Manager and select the project containing other example agents (Quick Tour Projects). From the Project Manager's File menu, select New. This will display an Agency Properties Dialog . Type in the name of the agency (Simple Buyer Seller with Protocol) and click OK.

Proceeding to a state 1506, at least two agents are created. The agents are referred to as "Simple Buyer 2" and "Simple Seller 2" agents. The specific steps in one embodiment are as follows: Go to the Project Manager and select the newly created agency. Now select New from the File menu. This will again display an Agent Properties Dialog. Fill in the information and click OK. The suggested name is Simple Buyer 2. Now repeat the process to create a Simple Seller 2. The Project Manager should now appear like that shown in the exemplary display of Figure 16.

Continuing at state 1508, a new ontology is created or an existing ontology retrieved from the system repository. In this example, a "Simple Buyer Seller Ontology" is retrieved by copying the Simple Buyer Seller Ontology from the System Repository to the user repository. This is a simple ontology; the object model contains a single item, the PriceRequest class.

Next, process 505 advances to a Create Protocol and Rules process 1510 to create a protocol for use by the agents. In this example, a "Simple Buyer Seller Protocol" is created with the Protocol Editor. This process 505 involves several steps which are performed in a specific order, in one embodiment. The protocol being created is called the Simple Buyer Seller Protocol and will be imported by the new agency. This requires defining two roles, the Buyer and Seller roles as well as a protocol state diagram. A role is the defined pattern of communications that an agent can assume when implementing a protocol. An agent may assume zero, one or more roles, depending on the protocol. Sometimes it may be appropriate for a buyer to also be a seller and vice- versa. Thus, an agent may assume more than one role when appropriate. The state diagram describes the state of the protocol, which should not be confused with the overall state of the agency. Transitions in the state diagram represent changes in the state of the protocol, i.e., communications between agents. The process 1510 will be further described in conjunction with Figure 17. The specific steps to begin the protocol manager in one embodiment are as follows: Go to the protocol manager by selecting the Protocols tab in the Project Manager. Click on the User icon and then select New from the File menu. Name the new protocol Simple Buyer Seller Protocol. Click on OK to close the window and continue. The window should appear like that shown in the exemplary display of Figure 18. Create Protocol and Rules Process

Portions of the Create Protocol and Rules Process 1510 will now be described. Beginning at a start state 1702, process 1510 advances to state 1704 where roles to be used by the previously created agents (state 1506, Figure 15) are created. The specific steps in one embodiment are as follows: The first step in defining a protocol is to specify the roles that exist in the protocol. In this particular protocol there are two roles, the Buyer Role and the Seller Role. Click on the Simple BuyerSeller Protocol item in the Protocols tree. Now select the Protocol Editor menu item from the Tools menu. This will display the tool used to build the protocol. Now select Roles... from the Diagram menu. This will display a dialog for entering, editing and deleting roles from this protocol. Select the New menu item from the File menu. Now type in Buyer Role in the name field, a description and then enter 1 in the Instances field (the combo box is editable, so delete the label and type 1).

The instances permit the user to specify a specific number of instances or a range. There are three choices when specifying the value of the instances field: zero or more, one or more, or a specific number. The first two mean that a dynamic number of agents can implement this particular role. For example, it may not be known how many buyers are going to be part of an agency, so the user would select "zero or more". If it is known that at least one buyer is needed for the protocol to work, choose the "one or more" option. If there needs to be an exact number of agents implementing a role to make the protocol work, specifying the exact number would be appropriate. For example, the user may want one and only one facilitator in an agency. Click OK, and this will enter the role into the Roles Dialog. Now repeat the procedure to create a Seller Role. The Roles Dialog should now appear like that shown in the exemplary display of Figure 19. When finished, select File < Close.

Process 1510 for creating a protocol continues at state 1706 to define a communication state diagram by creating states appropriate for the agents. The specific steps in one embodiment are as follows: Return to the Protocol Editor (if not already done), place the cursor in the drawing area and right-click. This will display a popup dialog that allows the user to create states and transitions of the protocol. First create a new state; this is done by selecting the New State menu item popup menu. This displays a State Properties Dialog. Fill in the Name field with Start, then add a description, and select the type as Initial for an initial state. This means that the protocol starts from this state. The dialog should now appear like that shown in the exemplary display of Figure 20. Click on OK to complete this state. Now create two more states. One non-terminal state will be of type Standard and will be called Request, and a final state will be called Done. When finished, the diagram should appear like that shown in the exemplary display of Figure 21. Process 1510 moves to state 1708 to define the transitions between the states previously defined at state 1706. A transition specifies a communication that causes an event which produces a state change in the protocol. In this example, the first transition is a Request Quote Transition. A template is generated for a KQML message that will be sent and received by the agents implementing the roles. The user specifies various fields in a KQML message which will then be used by the tools to develop message sending and handling rules in the appropriate agents. New rules are created for each agent sending messages to the receiving agents for handling incoming messages. The rule generation is accomplished when importing the protocol into an agency.

The specific steps in one embodiment are as follows: The first step is to place the cursor on the drawing area of the display (not over a state) and right-click. Now choose the New Transition menu item which will cause the cursor to change to cross-hairs. Then select the state for which the transition is to start from (the Start state), hold down the mouse button and move it to the new transition state (the Request state). This will display the Transition Properties Dialog. The dialog allows the user to specify fields that go into a KQML message. Fill in the name with Price_Request (in one embodiment, the Transition Properties Dialog does not allow white space in the name). Add a description such as:

"This transition represents a requests that the Seller Role agent fill out a PriceRequest PAC and return it."

The transition must be properly filled out for it to be added to the protocol. In one embodiment, the Sender, Receiver, Performative and Content Type fields must all be specified. Add the following information:

Name: Price_Request

Sender: Buyer Role

Receiver: Seller Role

Performative: Ask-one Ontology: Simple Buyer Seller Ontology

ContentType: PriceRequest

Reply-With: price-request It should be noted that the user will not be able to find the PriceRequest in the Content Type list until the correct ontology is selected. This is because the ontology selection dictates which classes are available for sending. All classes defined in the object model of that ontology are available for selection as the content type of the message.

The Transition Properties Dialog should appear like that shown in the exemplary display of Figure 22. Select OK after entering all of the relevant information. If the required fields are not completed, the dialog cannot be closed. Next, a new transition between the Request and Done states is created. The fields should be filled out as follows:

Name: Price_Quote_Reply

Sender: Seller Role

Receiver: Buyer Role Performative: tell

Ontology: Simple Buyer Seller Ontology

ContentType: PriceRequest

In-Reply-To: price-request When finished, the dialog should appear like that shown in the exemplary display of Figure 23. After a save is done, the Protocol Editor may be closed. Moving to state 1710, process 1510 converts the protocol diagram to a protocol state table. Continuing at state 1712, process 1510 converts the protocol state table to individual agent state tables for each agent. Proceeding to state 1714, process 1510 utilizes behavioral rule templates to construct skeletal rules. These skeletal behavioral rules are then displayed to the user at state 1716. The Create Protocol and Rules process 1510 completes and returns at state 1718 to the process 505 (Figure 15). A further description of the processing performed at states 1710, 1712 and 1714 is provided in conjunction with Figures 35-38 in the Automatically Generating Agent Behaviors from Agent Protocols section below. Import Protocol. Assign Agents and Finish Agents At the completion and return of the Create Protocol and Rules process 1510, execution of process 505 continues at state 1512. At state 1512, the protocol created by the process 1510 is imported into the agency created at state 1504. In this example, the protocol is imported into the "Simple Buyer Seller with Protocol" agency. In one embodiment, protocols are completely decoupled from actual agents and agencies. After the protocols are completed, they are imported into an agency (or more than one agency) and a mapping is made between the roles of the protocols and the agents in the agency.

The specific steps in one embodiment are as follows: First, open the Simple Buyer Seller with Protocol agency in the Agency Manager. This requires either clicking on the Agencies tab and opening the agency using the File menu, or clicking on the desired agency in the Projects tree and then clicking the Agencies tab. Either technique loads the Simple Buyer Seller with Protocol agency into the Agency Manager. In the Agency Manager, select the File < Import Protocols... menu item. The Import Protocol Dialog will be displayed with the Simple Buyer Seller Protocol in the list. Select this protocol and then click OK.

Proceeding to state 1514, agents are assigned to roles, thereby making role assignments. In one embodiment, the Role Editor is utilized to make the assignments.

The specific steps in one embodiment are as follows: While in the Agency Manager, click on the Protocols tab and then select the Simple Buyer Seller Protocol. Now select the Tools < Role Editor menu item. This will display the Role Editor tool. The user can use this tool to assign agents to specific protocol roles. Select the Buyer Role in the left side panel and then click Options < Assign Agents... menu item. This will display the Assign Agents Dialog. Now select Simple Buyer 2 and click on the Add button. The Assign Agents dialog should appear like that shown in the exemplary display of Figure 24. Click on OK to close the dialog.

Now select the Seller Role in the left panel and follow the same steps except choose Simple Seller 2 agent for implementing the role. A Role Editor display should appear like that shown in the exemplary display of Figure 25. The next step is to update the agents that are affected by the protocol. This step is easily accomplished by choosing the Options < Update All Agents menu item. This has the effect of generating information (primarily rules) for each agent that assumes a role in the protocol. Save and Close the Role Editor using the File menu. Continuing at state 1516, agents are finished as necessary, such as by modifying or creating rules for the agents. State 1516 completes the construction of the agents. The protocol that was imported into the Simple Buyer Seller with Protocol agency at state 1512 added several key rules to the agents, but they must be completed. In one embodiment, the protocol only provides high-level information, and therefore, additional detail is necessary to complete the agents.

The specific steps in one embodiment are as follows: Load Simple Buyer 2 in the Agent Manager, click on the Rules tab and select the Simple Buyer Seller Protocol Price_Request Message Sender rule. A Simple Buyer Rules window should appear like that shown in the exemplary display of Figure 26. These rules aren't complete because some information must be generated by the developer at agent construction time. For example, the first, second, and fourth parameters need to be added to the sendKqmlMessage built-in action. The message handler rules have only conditions and no actions. The appropriate actions need to be added. The use of protocols provides two main benefits; every rule that needs to be created for communication is created. Further; many of the conditions and actions are automatically added. Unfortunately, not all of the information can be specified in the Protocol Editor.

It should be noted that the automatically generated rule names are rather large, but the name follows a specified format in one embodiment. The format is protocol-name, transition- name, and rule-type. This provides the automatically generated rules with a unique name. These rules appear in the exemplary display of Figure 26. The next steps involve modifying the existing rules of the Simple Buyer 2 agent to implement the functionality of the original Simple Buyer agent. The rules should appear like those shown in the exemplary displays of Figure 27 and Figure 28. An entirely new rule, the Create Price Request rule, is to be created also. In the process of updating the rules, the user edits needs to edit several existing patterns and import the PriceRequest PAC via the PAC Editor. The next step is to perform a similar task for the Simple Seller 2 agent. When done, the rules should appear like those shown in the exemplary displays of Figure 29 and Figure 30. Notice that the Simple Seller agent uses two rules. The automatic rule generation produced one rule for handling incoming messages and one rule for sending a reply. Instead of merging these two rules, they are tied together by asserting KqmlMessage and protocol state beliefs into the mental state and then using them as a test condition in the sender rule. The user can run/test each agent from the Project Manager by selecting the Projects tab, clicking on the agent in the agency hierarchy and selecting the Tools < Agent Engine pull-down menu. Execution of the Seller agent should be started before starting the Buyer agent. Agency Viewer After the agents are completed, the user may elect to run and test the agents in an Agency

Viewer, such as at state 534 (Figure 5). The Agency Manager provides a tool, the Agency Viewer, to help in running more than one agent at a time. This tool allows the user to start, stop, pause and reset one or all of the agents. It also allows the user to inspect messages sent from one agent to another and save the results of a run. The specific steps in one embodiment are as follows: Start the Agency Viewer by loading the Agency Manager with the correct agency. As mentioned previously, there are two different techniques for loading an agency. The user may either click on the Projects tab in the Project Manager and select the agency in the left-hand panel, or click on the Agencies tab and then use File < Open to load the conect agency. Once the agency is loaded, select the Tools < Agency Viewer menu item. This will load the tool with all of the agents from the agency (in this case, the Simple Buyer 2 and Simple Seller 2 agents will be loaded).

The Agency Viewer uses an icon to represent each agent. Each agent has a default icon. These default icons can be easily replaced. In one embodiment, all agent icons can be found in the <agenfBuilder-install-directory>/lib/icons/agentIcons/ directory. The user may create new icons using any kind of drawing or painting program. An icon is made available for use by placing it in the above-identified directory. An icon is selected by editing the agent icon field in the Agent Properties Dialog. A browser is provided to help change the icon.

Notice that icon labels use different colors to represent the state of the agent in one embodiment. As the agent's state changes from stopped, registered, or waiting to running, the state changes visually by color. See Table 3 for an exemplary assignment of colors.

TABLE 3 - Agency Viewer Colors

State Color Code

Stopped Red

Registered Pink

Ready to Begin Yellow

Running Green

Pause Cyan The first step in running the agency is to click on the Exec < Register Mode menu item. This places the tool into registration mode. At this point, agents can join the agency. The user may run the agents either locally or remotely (using the agency run-time option agency-mode) and they can register with the tool. In one embodiment, the Agency Viewer appears as an agent to the running agents; i.e., the agents communicate with the tool using KQML messages like all other agents. The major difference is that the Agency Viewer is a special controller type agent. After the register mode is entered, the agents are started. If all the agents are running on the same computer (which is true in this example), then the user may use the Exec < Run All command to start all the agents. This, in turn, causes an Engine Options Dialog to be display for every agent that is run. In this case, a dialog will be displayed for the Simple Buyer 2 and Simple Seller 2 agents. Click on the OK button, for each of the Engine Option Dialogs. After the agents are started and their consoles appear, the agents are still not running. This is expected because the agents are waiting for a "begin" command from the Agency Viewer. The agents are started by clicking on Exec < Begin. At this point, the icons for the agents will turn green, indicating that the agents are running.

There will be two lines drawn between the agents; these lines represent communication between the agents. The Agency Viewer should appear like that shown in the exemplary display of Figure 31. A Console for each agent displays the output generated by the created rules. A Simple Buyer 2 console should appear like that shown in the exemplary display of Figure 32. A Simple Seller 2 console should appear like that shown in the exemplary display of Figure 33. A warning generated by execution of the Simple Seller 2 agent may be seen in the error window of the agent console. This warning indicates that a modified mental state element has been retracted. Normally, this is very useful to the developer. This warning is typically generated when two rules are operating on the same object with one modifying the object and the other retracting it. This may lead to errors in the control and logic of the agent. In this particular case, it is acceptable to retract the KqmlMessage object. The reason is that even though the object was modified, there is no need to reason with it in the future.

The Agency Viewer tool is useful for debugging agent communication during the development cycle. It provides a way to examine messages sent between agents and a way to save the results of the run. To examine the messages sent from the Simple Buyer 2 to the Simple Seller 2, the user may right-click on the Simple Buyer 2 icon and select the Message History popup menu item. This displays a dialog showing the messages sent and received by this agent. To examine a particular message, the user may click on it in the Received or Sent lists. The Message History dialog should appear like that shown in the exemplary display of Figure 34. The results of a run (Open Run, Save Run, Save Run As...) may be saved. A nm is a session in which all message traffic between agents is monitored and captured. A File menu item is used to turn the message log on or off (Message Log) using a check box next to the menu item.

The Edit menu may be used to edit the properties of the agents and agencies by using the Edit < Properties... and Edit < Agent Properties... items.

An Exec menu item controls execution of agents in the agency. This menu item includes provision for registering agents (Register Mode), running all agents (Run All), starting (Begin) and stopping (Stop) agents, pausing the agents (Pause), and resetting the agents (Reset). The Agent Creation Toolkit allows the user to control individual agents or all agents in an agency. The Exec menu permits global control of the agents, or each agent may be controlled by individually right- clicking on it. A popup menu provides controls for running, starting, stopping and pausing the agents.

An Options menu item allows the user to turn on and off the agent message display by using a check box in the Options < Show Message menu item. The user may also use the Options menu to examine the status of an agent (Options < Agent Status) and to change the message buffer size (Options < Buffer Size...). The user may also disable the message trace window located at the bottom of the window.

Another useful and interesting feature of the tool is the pause/unpause and reset feature. The user may globally or individually use the pause feature to step through a protocol and examine the messages being sent, by whom and when. The user may also reset the entire agency when necessary by clicking on Exec < Reset. This will rerun the agents without forcing a restart of them. Notice that the color of the agent icons changes.

When finished with a development session, the user may select Exec < Stop to stop all agents and then choose the File < Close menu item. The user is given an option as to whether or not to save the run. If the run is saved, all of the message information may be retrieved at a later time.

Automatically Generating Agent Behaviors from Agent Protocols Background

Agents communicate and cooperate with each other to solve complex problems. They are a powerful distributed problem-solving methodology. This is accomplished in part by the ability of the agents to send and receive messages. For example, a grocery-shopping agent accomplishes its tasks by communicating with a grocery store agent. The shopping agent may send a list of desired products and quantity. The grocery store agent would then send a list of available quantities and prices. This simple message transaction is called a protocol. If an agent based system has many agents, then designing and implementing these protocols may be quite difficult. The Agent Creation Toolkit provides a graphical protocol editor for constructing these protocols.

Further, the innovation automatically converts the message protocols into the agent program required to implement the protocol.

This innovation is based on the observation that an agent conversation may be represented as a state machine diagram in which the nodes of the state machine represent pauses in conversation and the links represent messages transmitted between participants in the conversation.

Note that the state machine represents the conversation and not the states of the individual agents participating in the conversation.

In its simplest form, a conversational protocol is represented as a state transition diagram 3500 as shown in Figure 35. In the diagram, x represents the sending agent, y represents the receiving agent and m represents the message 3502 transmitted by x toy. The diagram indicates that the conversation moves from State 1 to State 2 when agent x sends message m to agent v.

The innovation further extends this concept by utilizing the capability of a traditional state machine to represent condition-action activities in a complex system. That is, the state machine may be used to indicate that when a particular condition occurs, then and only then, the state machine should transition to a new state. Referring to Figure 36, condition action pairs may be represented as a state transition diagram 3600. The notation used in the diagram 3600 means that if condition ca occurs, then the system should perform action pal and transition 3602 to State 2; however, if condition cb occurs, then the system should perform action pa2 and transition 3604 to State 3.

Representing a Conversation as a State Diagram

Agent Creation system agents operate using behavioral rules of the form:

IF condition-name THEN action-name

This means that if the agent detects that condition-name occurs, then the agent should perform action-name.

The present invention combines the concept of using a state machine to represent a conversation with the concept that a state machine may represent condition-action transitions in a complex system.

Thus, for an agent-based system, the communications protocol can now be represented by an agent protocol specification 3702 as shown in a diagram 3700 of Figure 37. This specification

3702 is interpreted to read: if a condition cal occurs in agent x, then agent x will send message m to agent y and perform action pal. Note that a condition for action (e.g., cal) may be a message with particular content received from some other agent requesting that the receiving agent perform some action. Agent protocol specifications may be extremely complex and may represent the conversations between many agents as these agents perform complex tasks. However, a complete process for an agent protocol may be captured with a simple diagram, such as diagram 3800 shown in Figure 38. Converting Protocols to State Diagrams

The protocol shown in the diagram 3800 of Figure 38 may be represented as a State Table shown in Table 4 below.

TABLE 4 - State Table for Multi-Agent Conversation

This table describes the inter-agent conversations 3802 and 3804 of Figure 38, and may be used to describe agencies and protocols of arbitrary complexity. However, it may be necessary to program the individual agents in such a way that the individual, independent and autonomous agents may implement the protocol. This is accomplished by parsing the Conversation State Table into an Agent State Table for each agent participating in the conversational protocol.

Converting Protocol State Tables to Agent State Tables For the example in Table 4, the agent state tables are shown in Table 5 and Table 6.

TABLE 5 - Agent x State Table

Converting State Table Contents to Agent Creator Behavioral Rules In general, an Agent Creator behavior rules takes the form: IF condition- 1, condition-2, condition-3,

condition-/* THEN action- 1, action-2,

action-m

The conditions in a rule may be of two types. The conditions may be based on the contents of the agent's mental model (mental conditions), or they may be based on the contents of received messages (message conditions). Likewise, agent actions may be of two types. The actions may either be private actions or message actions. A message action implies sending a message to another agent. A private action is any other action that the agent is capable of performing.

The innovation uses the information from the agent state tables to determine the message conditions, mental conditions and message actions. These components are inserted into skeletal behavioral rules. A programmer using the Toolkit need only complete the rules by inserting other mental conditions or actions that are not explicitly denoted in the agent protocol. For example, the other mental conditions or actions may include inserting delays, printing results, etc. Conclusion

Specific blocks, sections, devices, functions and modules may have been set forth. However, a skilled technologist will realize that there are many ways to partition the system of the present invention, and that there are many parts, components, modules or functions that may be substituted for those listed above.

While the above detailed description has shown, described, and pointed out the fundamental novel features of the invention as applied to various embodiments, it will be understood that various omissions and substitutions and changes in the form and details of the system illustrated may be made by those skilled in the art, without departing from the intent of the invention. Appendix

Reticular Agent Definition Language

Parentheses, square brackets and angled brackets are to be interpreted as literals except for angled brackets surrounding a word, e.g. as in <belief-templates>. A line such as <template-type> < <instance-name> > is intended to represent a name such as Location<currentLocation>, or in the case where the instance is not named, Locationo.

NULL means that nothing is printed in the agent definition file.

<agent-definition> <version-number> <unstructured-comments>

<separator-line> <abbreviated-names>

<separator-line> <initial-objects>

<separator-line> <action-definitions>

<separator-line> <capabilities>

<separator-line> <belief-templates>

<separator-line> <initial-beliefs>

<separator-line> <initial-agency-beliefs>

<separator-line <initial-commitments>

<separator-line <initial-intentions>

<separator-line> <behavioral-rules>

<separator-line>

<version-statement> : := RETICULAR AGENT DEFINITION BNF VERSION: <version>

<version> := <numeral> { .<numeral>}* <unstructured-comments> <string>*

The separator line may be any length, composed of the SEPARATOR LINE_CHAR. The <unstructured-comments> may be anything. ABBREVIATED NAMES

<abbreviated-names> ::= ABBREVIATED NAMES <name-table-entry>*

<name-table-entry> : := ( <abbreviated-name> <full-pkg-class-name> ) <abbreviated-name> ::= <string> <full-pkg-class-name> ::= <string> INITIAL OBJECTS

<initial-objects> ::= INITIAL OBJECTS <initial-object>*

# Note: the CTOR_ARGS keyword is now optional. <initial-object> ::= ( <pkg-class-name>

< <instance-name> > {CTOR ARGS I NULL} <ctor-arg-spec>* )

#Note: You only use quotes on the String when the type of object is String.

<ctor-arg-spec> ::= ( <ctor-arg-type> <ctor-arg-value>* ) | ( Java. lang. String "<string>" )

<ctor-arg-type> : := <pkg-class-name> <ctor-arg-value> ::= <string> | <numeral> | <ctor-arg-spec> | DEFAULT | NULL <string> : := <alphanumeric>* <numeral> ::= <digit>* { .<digit>* } <instance-name> : := <string> | NULL

<pkg-class-name> ::= <package-name>. <class-name> | <class-name>

<package-name> ::= {<string>. } *<string> <class-name> ::= <string> ACTION DEFINITIONS

<action-definitions> ::= ACTION DEFINITIONS <action-definition>*

<action-definition> : := ( <action-name> PAC_OBJECT <pkg-class-name> < <pac-object-name> > PAC_METHOD <method-name> ( <method-arg-type>* ) ) I ( <action-name> SEPARATE_THREAD PAC_OBJECT <pkg-class-name>< <pac-object-name> > )

<action-name> : := <string> <method-name> : := <string> <method-arg-type> : := <pkg-class-name> <pac-object-name> : := <string> | NULL CAPABILITIES

<capabilities> : := CAPABILITIES <capability>*

<capability> ::= ( <action-name> ( <pattern-variable>* ) PRECONDITIONS ( <lhs-pattern>* ) EFFECTS ( <mental-change>* ) ) BELIEF TEMPLATES

<belief-templates> ::= BELIEF TEMPLATES <belief-template>* <belief-template> : := (<template-type>

FIELDS [{<field-type> «field-name> >}* ] CTOR-ARGS [ <arg-type>* ] )

<template-type> : := <string> <field-type> ::= <string> <arg-type> ::= <string> <field-name> ::= <string> INITIAL BELIEFS

<initial-beliefs> : := INITIAL BELIEFS <initial-belief>* <initial-belief> : := ( <template-type> < <instance-name> > CTOR-ARGS <ctor-arg-spec>* ) INITIAL COMMITMENTS

<initial-commitments> : := INITIAL COMMITMENTS <commitment>*

<commitment> ::= (<agent-name> [ <time> ] <action-name> ( <bound- element>* ) )

<time> ::= <year>:<month>: <day> <hour>: <minute>:<second> | STARTUP SHUTDOWN

<year> ::= <numeral> <month> ::= <numeral> <day> ::= <numeral> <hour> ::= <numeral> <minute> : : = <numeral> <second> ::= <numeral> BEHAVIORAL RULES

<behavioral-rules> ::= BEHAVIORAL RULES <behavioral-rule>* <behavioral-rule> ::= ( <rule-name> WHEN <when-clause> IF <if-clause> THEN <then-clause> )

<rule-name> : := <quoted-string>

<when-clause> : := <compound-lhs-pattern>*

<if-clause> : := <compound-lhs-pattern>* <then-clause> : := <action-statement>*

{ <mental-change> | <temp-var-rhs-pattern> }'

RULE PATTERN SUPPORT

# This section breaks up the rule "compound-lhs-patterns" into more specific

# elements which are needed for correct representation.

<compound-lhs-pattern> ::= ( <simple-lhs-pattern> ) | ( <compound-lhs-pattern> AND <compound-lhs-pattern> ) | ( <compound-lhs-pattern> OR <compound-lhs-pattern> ) | ( NOT( <compound-lhs-pattern> ) ) | (<quantified-pattern> )

<simple-lhs-pattern> : := <object-relation> | <numerical-relation> | <bind-pattern> | <message-pattern> | <temp-var-lhs-pattern> # Example of new object relation using predicate method with args:

# OBJ [INST Time<currentTime>] during ( (Time [VAR Time<?tl>] ) ,

# (Time [VAR Time<?t2>] ) )

# The comma in the arg list is optional <object-relation> ::= OBJ <lhs-pattern-element>

<operator-keyword>

<lhs-pattern-element> |

OBJ <lhs-pattern-element>

<predicate-method-name> ( <arg-element-spec>* )

<arg-element-spec> : := ( <arg-class-name> <lhs-pattern-element>* )

<operator-keyword> ::= EQUALS | NOT EQUALS I ELEMENT-OF | NOT-ELEMENT-OF <numerical-relation> : := NUM <lhs-pattern-element> <rel-op-symbol> <lhs-pattern-element>

<rel-op-symbol> : := = 1 != I < | <= I > I >=

<bind-pattern> ::= BIND <pattern-variable> | BIND <named-instance-var>

<temp-var-lhs-pattern> : := SET_TEMPORARY <pattern-variable> TO <lhs-pattern-element>

<quantified-pattern> ::= <quantifier> <quant-var-list> ( <compound-lhs-pattern> )

<quantifier> ::= FOR_ALL | EXISTS <quant-var-list> : := <top-level-pattern-variable>+

<pattern-element> ::= <lhs-pattern-element> | <rhs-pattern-element>

#The second option is a special case for handling KqmlMessage casting. #This is because the content field is an object and needs to be cast #to its specific type.

<pattern-variable> : := [ VAR <pkg-class-name> < <var-name> >{ .<field-name>}* ] | [VAR ( ( <pkg-class-name> ) KqmlMessage < <var-name> >. content ) { .<field-name>}* ]

<message-pattern-variable> ::= [ VAR <pkg-class-name> < <var-name> > { .<field-name>}* ] | [VAR ( ( <pkg-class-name> ) KqmlMessage < <var-name> >. content ) { .<field-name>} * ]

# The <top-level-pattern-var> is a restricted form of pattern variable

# which is used as the target variable in <quantified-pattern> and

# <retraction> <top-level-pattern-var> : := [ VAR <pkg-class-name> < <var-name> > ]

<var-name> : := <string>

<field-name> ::= <string>

<bound-element> ::= [ VAL <pkg-class-name> <value> ] | [ VAL <pkg-class-name> <ctor-arg-spec>* ]

<value> ::= "<string>" | <numeral> | NULL

<named-instance-var> ::= [ INST <pkg-class-name> < <instance-name> > { .<field-name>}* ]

# The <top-level-named-instance-var> is a restricted form of named instance

# variable used as the target variable in <retraction>

<top-level-named-instance-var>: := [INST <pkg-class-name> «instance-name> >]

<return-variable> ::= [ RVAR <pkg-class-name> < <var-name> > ]

<new-object-element> ::= [ NEW <pkg-class-name> <ctor-arg-element-spec>* ]

<ctor-arg-element-spec> : := ( <ctor-arg-class-name> <rhs-pattern- element>* )

<function> : := <math-function> | <arithmetic-function> | <string- function> <arithmetic-func> ::= [ AFUNC <pattern-element> <arithmetic-symbol> <pattern-element> ]

<arithmetic-symbol> ::= + | I I /

<math-function> : := [MFUNC <math-func-keyword> ( <math-func-operand-list> ) ]

<math-func-operand-list> ::= NULL | <pattern-element> | <pattern-element> <pattern-element>

<string-function> ::= [ SFUNC <string-func-keyword> ( <string-func-operand-list> ) ]

<string-func-operand-list> : := <pattern-element> | <pattern-element> <pattern-element> | <pattern-element> <pattern-element> <pattern-element>

#This section lays out the agent's beliefs about its own agency and #all of the other agents it knows about. It does this in a general #initial beliefs manner (i.e. it uses the format for an initial belief) #It will look like an initial belief to the agent engine parser. #The <comm-info> for the self agent cannot be null.

<initial-agency-beliefs> : := INITIAL AGENCY BELIEFS <self-spec> { <agency-tool-spec> | NULL } { <debugger-spec> I NULL } { <remote-agents-spec> | NULL } | NULL

<self-spec> : := ( SELF <agent-name> [ <agent-address> ] { [<comm-info>] }+ [ <keys> ] [ <agencies> ] )

<agency-tool-spec> : := ( AGENCY_TOOL <remote-agent> )

<debugger-spec> ::= ( DEBUGGER <remote-agent> )

<remote-agents-spec> : := REMOTE_AGENTS { ( <remote-agent> ) }*

<remote-agent> : := <agent-name> [ <agent-address> ] [<comm-info>] [ <keys> ] [ <agencies> ]

<agent> = <String> (quoted string)

<agencies> = <agency> { , <agency> } *

<agency> = <String> (quoted string)

<comm-info> = <rmi> I <socket> | NULL

<rmi> = RMI : rmiRegistry-port-number

<socket> = SOCKET : socket-port-number

<agent-address> = <IPaddress> | CURRENT_IP_ADDRESS

<IPAddress> = address (number or name) <keys> = <public-key> <private-key> | NULL

<public-key> = byte [ ]

<private-key> = byte [ ]

#RHS support

<rhs-pattern> : := ( <action-statement> ) |

( <mental-change> ) |

( <temp-var-rhs-pattern> )

<action-statement> ::= DO <action-name> ( <rhs-pattern-element>

{ , <rhs-pattern-element> }* )|

DO <return-variable> = <action-name>

( <rhs-pattern-element> { , <rhs-pattern-element> }* ) |

DO SendKqmlMessage ( <mssg-pattern-element>

<sender-pattern-element>

<receiver-pattern-element>

<performative-pattern-element>

<reply-with-pattern-element>

<in-reply-to-pattern-element>

<to-pattern-element>

<from-pattern-element>

<language-pattern-element>

<ontology-pattern-element>

<content-pattern-element> ) |

DO <target-element> <method-name>

( <ctor-arg-element-spec>

{ , <ctor-arg-element-spec> }* |

NULL ) # For the "run" method |

DO <target-element> run ( ) SEPARATE_THREAD |

DO <return-variable> = <target-element>

<method-name> ( <ctor-arg-element-spec> { , <ctor-arg-element-spec> }* | NULL )

<target-element> ::= <pattern-variable> | <named-instance-var>

<method-name> : := <String>

<mssg-pattern-element> : := <rhs-pattern-element>

<sender-pattern-element> SENDER <rhs-pattern-element> | []

<receiver-pattern-element> RECEIVER <rhs-pattern-element> I []

<performative-pattern-element> ^■■ PERFORMATIVE <rhs-pattern-element> | []

<reply-with-pattern-element> REPLY_WITH <rhs-pattern-element> | []

<in-reply-to-pattern-element> IN_REPLY_TO <rhs-pattern-element> I []

<to-pattern-element> TO <rhs-pattern-element> | []

<from-pattern-element> FROM <rhs-pattern-element> I []

<language-pattern-element> LANGUAGE <rhs-pattern-element> | []

<ontology-pattern-element> ONTOLOGY <rhs-pattern-element> I []

<content-pattern-element> CONTENT <rhs-pattern-element> | [] <mental-change> <assertion> | <retraction> <assertion> : := ASSERT ( <instance-name> <object-pattern> ) | ASSERT ( <replacement> )

<instance-name> : := <bound-element> | NULL

<new-object-element> | <bound-element> I

<named-instance-var> <replacement> : := SET_VALUE_OF <pattern-variable> TO <rhs-pattern- element> |

SET_VALUE_OF <named-instance-var> TO <rhs-pattern-element>

# A retraction target will be either a <top-level-pattern-variable> or a # <top-level-named-instance-var>. These are restricted forms of pattern

# vars or named instance vars which cannot have any subobjects specified.

<retraction> ::= RETRACT ( <top-level-pattern-variable> ) | RETRACT ( <top-level-named-instance-var> )

<temp-var-rhs-pattern> : := SET_TEMPORARY <pattern-variable> TO <rhs-pattern-element>

Claims

WHAT IS CLAIMED IS:

1. A development system for developing a plurality of communicating software agents, compnsing: an agency manager adapted to manage a plurality of agent roles, each software agent associated with one or more of the agent roles; an agent manager adapted to define a plurality of rules, each software agent associated with a set of rules; and a protocol manager adapted to define messages which are communicated among the software agents.

2. The system of Claim 1, wherein the agency manager compnses an agency viewer and a role editor.

3. The system of Claim 1, wherein the agent manager includes a rule editor

4 The system of Claim 1 , wherein the protocol manager includes a protocol editor.

5. The system of Claim 1 , wherein the protocol manager includes a role dialog.

6. The system of Claim 1, additionally compnsing an ontology manager adapted to generate and modify an ontology descnption.

7. The system of Claim 1, wherein the system produces an agent definition file which can be executed by a run-time agent engine.

8. The system of Claim 1, wherein the system is adapted to develop software agents which communicate over the Internet.

9. A method of developing message protocols among communicating software agents, the protocol editor compnsing: creating a plurality of protocol states; creating a plurality of protocol transitions, wherein each transition is associated with a sender agent of a message, a receiver agent of a message, and selected ones of the protocol states; converting the protocol states and the protocol transitions to a protocol state table, and converting the protocol state table to a plurality of agent state tables, each agent state table associated with one of the software agents.

10. The method of Claim 9, additionally compnsing: converting a plurality of stored behavioral rule templates and the agent state tables to a plurality of skeletal rules for each software agent; and displaying the skeletal rules on a display device.

11. The method of Claim 9, wherein the protocol state table includes the following fields: initial state, final state, condition, pnvate action, message, sending agent and receiving agent.

12. The method of Claim 9, wherein each agent state table includes the following fields: state, condition, message received, message to send, pnvate action and message recipient.

13. A development system for communicating software agents, compnsing: a set of development tools adapted to generate codes for the software agents; and a debugger adapted to permit examination of the mental model associated with the software agents.

14. The system of Claim 13, wherein a developer can step through the execution of each software agent cycle-by-cycle.

15. The system of Claim 13, wherein a developer can specify breakpoints and run one of the software agents until a breakpoint is reached.

16. A method of developing communicating software agents, compnsing: displaying a plurality of icons, each icon representative of a plurality of software agents; and graphically viewing messages sent among the software agents.

17 The method of Claim 16, additionally compnsing saving results associated with the execution of the software agents.

18. The method of Claim 16, wherein the method is implemented with a debugger software agent.

19. The method of Claim 16, wherein the icons are displayed with different colors representative of running states.

20 The method of Claim 16, wherein the agents are run either locally or remotely.

21. The method of Claim 16, wherein agents may be selectively controlled individually or globally.

22. The method of Claim 16, additionally compnsing pausing and unpausmg each software agent to examine messages.

23. The method of Claim 16, additionally compnsing resetting the agents for execution.

24. A method of developing communicating software agents, compnsing: creating a plurality of protocol roles; creating a plurality of protocol states; creating a plurality of protocol transitions, wherein each transition specifies one of the agent roles associated with a sender agent of a message, one of the protocol roles associated with a receiver agent of a message, and selected ones of the protocol states; and mapping the agent roles into a plurality of communicating software agents.

25. The method of Claim 24, wherein the protocol roles include a buyer role and a seller role.

26. The method of Claim 24, wherein the protocol states include start, request and done.

27. The method of Claim 24, wherein the protocol transitions include a pnce request transition from a start state to a request state, and a pnce quote reply transition from a request state to a done state.

28. The method of Claim 24, wherein the creating of protocol transitions includes creating a template for a knowledge query and manipulation language (KQML) message that will be sent and received by a set of agents implementing the protocol roles.

29. The method of Claim 24, wherein the creating of protocol states and the creating of protocol transitions include graphically displaying the created states and transitions.

30. A communicating software agent system, compnsing: a set of development tools adapted to create, modify and generate message protocols and software codes for a plurality of software agents, and an agent engine adapted to execute the agent codes, wherein the software agents communicate with the message protocols.

31. A method of developing a plurality of communicating software agents, compnsing: creating a first software agent, creating a second software agent; and automatically generating communication protocols associated with the first and second software agents thereby allowing the software agents to communicate.

32. The method of Claim 31, wherein the communication occurs via at least messaging.

33. The method of Claim 31, wherein the software agents compnse a mental model having intentions, beliefs, commitments, capabilities and behavioral rules.

34. A method of developing a plurality of communicating software agents, compnsing: developing rules for a plurality of software agents; and combining the rules with roles and protocols so as to define the behavior of each software agent when a communication from another software agent is received.

35. The method of Claim 34, wherein the software agents comprise a mental model having intentions, beliefs, commitments, capabilities and behavioral rules.