`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`CERTIFICATE OF EXPRESS MAILING
`I hereby certify that this paper and the documents and/or fees referred to as
`attached therein are being deposited with the United States Postal Service
`on January 05, 1999 in an envelope as "Express Mail Post Office to
`Addressee" service u
`r 37 CFR §1.10, Mair
`bel Number
`EL221766053US
`dr ssed to the Assista Co
`Washingto,e, D 2~
`
`Attorney Docket No.: SRI1P016
`
`First Named Inventor:
`
`CHEYER, Adam J.
`
`UTILITY PATENT APPLICATION TRANSMITTAL (37 CFR § 1.53(b))
`0 Duplicate for
`fee processing
`
`Assistant Commissioner for Patents
`Box Patent Application
`Washington, DC 20231
`
`Sir:
`
`This is a request for filing a patent application under 37 CFR § 1.53(b) in the name of inventors:
`Adam J. Cheyer and David L. Martin
`
`For:
`SOFfW ARE-BASED ARCHITECTURE FOR COMMUNICATION AND COOPERATION AMONG
`DISTRIBUTED ELECTRONIC AGENTS
`
`Application Elements:
`I:8J 59 Pages of Specification, Claims and Abstract
`1:3] 16 Sheets ofDrawings
`I:8J 01 Pages Combined Declaration and Power of Attorney
`
`,~
`
`Accompanying Application Parts:
`
`1:3] Assignment and Assignment Recordation Cover Sheet (recording fee not enclosed)
`I:8J Return Receipt Postcard
`
`Fee Calculation (37 CFR § 1.16)
`
`SMALL ENTITY OR
`(Col. 1)
`(Col. 2)
`NO. FILED NO. EXTRA RATE FEE
`BASIC FEE
`$395 $
`TOTAL CLAIMS ~ -20= ~ x11 = $
`x41 = $
`QQ.____ -03 = _QL
`INDEP CLAIMS
`* Ifthe difference in Col. 1 is less
`Total $
`than zero, enter "0" in Col. 2.
`
`OR
`OR
`OR
`OR
`
`LARGE ENTITY
`RATE FEE
`$760 $760.00
`x18 = $1242.00
`x78 = $234.00
`Total $2236.00
`
`Including filing fees and the assignment recordation fee of $40.00, the Commissioner is authorized to
`charge all required fees to Deposit Account No. 50-0384 (Order No. SRI1P016).
`I:8J The Commissioner is authorized to charge any fees beyond the amount enclosed which may be
`required, or to credit any overpayment, to Deposit Account No. 50-0384 (Order No. SRI1P016).
`
`(Revised 12/97, Pat App Trans 53(b) Reg
`
`Page 1 of2
`
`GOOGLE EXHIBIT 1008
`Part 1 of 2
`
`Page 1 of 778
`
`
`
`1
`
`~ ....
`General Authorization for Petition for Extension of Time (37 CFR § 1.136)
`1:8] Applicants hereby make and generally authorize any Petitions for Extensions of Time as may be
`needed for any subsequent filings. The Commissioner is also authorized to charge any extension fees under
`37 CFR § 1.17 as may be needed to Deposit Account No. 50-0384.
`
`rg] Please send correspondence to the following address:
`
`Brian R. Coleman
`HICKMAN STEPHENS & COLEMAN, LLP
`P.O. Box 52037
`Palo Alto, CA 94303-0746
`
`Tel (650) 470-7430
`Fax (650) 470-7440
`
`Date: -----+--{ [:7--+--(9 _ _9_
`
`Brian R. Coleman
`Registration No. 39,145
`
`(Revised 12/97, Pat App Trans 53(b) Reg
`
`Page 2 of2
`
`Page 2 of 778
`
`
`
`Software-Based Architecture for Communication and Cooperation Among
`
`Distributed Electronic Agents
`
`5
`
`By:
`
`Adam J. Cheyer and David L. Martin
`
`BACKGROUND OF THE INVENTION
`1 o Field of the Invention
`The present invention is related to distributed computing environments and the
`
`completion of tasks within such environments. In particular, the present invention
`
`teaches a variety of software-based architectures for communication and cooperation
`
`among distributed electronic agents. Certain embodiments teach interagent
`
`15
`
`communication languages enabling client agents to make requests in the form of
`
`arbitrarily complex goal expressions that are solved through facilitation by a
`
`facilitator agent.
`
`Context and Motivation for Distributed Software Systems
`
`20
`
`The evolution of models for the design and construction of distributed
`
`software systems is being driven forward by several closely interrelated trends: the
`
`adoption of a networked computing model, rapidly rising expectations for smarter,
`
`longer-lived, more autonomous software applications and an ever increasing demand
`
`for more accessible and intuitive user interfaces.
`
`25
`
`Prior Art Figure 1 illustrates a networked computing modellOO having a
`
`plurality of client and server computer systems 120 and 122 coupled together over a
`
`physical transport mechanism 140. The adoption ofthe networked computing model
`
`100 has lead to a greatly increased reliance on distributed sites for both data and
`
`processing resources. Systems such as the networked computing modellOO are based
`
`30
`
`upon at least one physical transport mechanism 140 coupling the multiple computer
`
`systems 120 and 122 to support the transfer of information between these computers.
`
`Some of these computers basically support using the network and are known as client
`
`Attornev Docket No: SRI1P016(3477VBRC/EWJ
`
`Page 1 of 59
`
`Page 3 of 778
`
`
`
`computers (clients). Some of these computers provide resources to other computers
`
`and are known as server computers (servers). The servers 122 can vary greatly in the
`
`resources they possess, access they provide and services made available to other
`
`computers across a network. Servers may service other servers as well as clients.
`
`5
`
`The Internet is a computing system based upon this network computing model.
`
`The Internet is continually growing, stimulating a paradigm shift for computing away
`
`from requiring all relevant data and programs to reside on the user's desktop machine.
`
`The data now routinely accessed from computers spread around the world has become
`
`increasingly rich in format, comprising multimedia documents, and audio and video
`
`10
`
`streams. With the popularization of programming languages such as JAVA, data
`
`transported between local and remote machines may also include programs that can
`
`be downloaded and executed on the local machine. There is an ever increasing
`
`reliance on networked computing, necessitating software design approaches that allow
`
`for flexible composition of distributed processing elements in a dynamically changing
`
`15
`
`and relatively unstable environment.
`
`In an increasing variety of domains, application designers and users are
`
`coming to expect the deployment of smarter, longer-lived, more autonomous,
`
`software applications. Push technology, persistent monitoring of information sources,
`
`and the maintenance of user models, allowing for personalized responses and sharing
`
`20
`
`of preferences, are examples of the simplest manifestations of this trend. Commercial
`
`enterprises are introducing significantly more advanced approaches, in many cases
`
`employing recent research results from artificial intelligence, data mining, machine
`
`learning, and other fields.
`
`More than ever before, the increasing complexity of systems, the development
`
`25
`
`of new technologies, and the availability of multimedia material and environments are
`
`creating a demand for more accessible and intuitive user interfaces. Autonomous,
`
`distributed, multi-component systems providing sophisticated services will no longer
`
`lend themselves to the familiar "direct manipulation" model of interaction, in which
`
`an individual user masters a fixed selection of commands provided by a single
`
`30
`
`application. Ubiquitous computing, in networked environments, has brought about a
`
`situation in which the typical user of many software services is likely to be a non(cid:173)
`
`expert, who may access a given service infrequently or only a few times.
`
`Attorney Docket No: SRIIPOI6(3477)/BRC/EWJ
`
`Page 2 of 59
`
`Page 4 of 778
`
`
`
`Accommodating such usage patterns calls for new approaches. Fortunately, input
`
`modalities now becoming widely available, such as speech recognition and pen-based
`
`handwriting/gesture recognition, and the ability to manage the presentation of
`
`systems' responses by using multiple media provide an opportunity to fashion a style
`
`5
`
`of human-computer interaction that draws much more heavily on our experience with
`
`human-human interactions.
`
`PRIOR RELATED ART
`
`Existing approaches and technologies for distributed computing include
`
`10
`
`distributed objects, mobile objects, blackboard-style architectures, and agent-based
`
`software engineering.
`
`The Distributed Object Approach
`
`Object-oriented languages, such as C++ or JAVA, provide significant
`
`advances over standard procedural languages with respect to the reusability and
`
`15
`
`modularity of code: encapsulation, inheritance and polymorhpism. Encapsulation
`
`encourages the creation of library interfaces that minimize dependencies on
`
`underlying algorithms or data structures. Changes to programming internals can be
`
`made at a later date with requiring modifications to the code that uses the library.
`
`Inheritance permits the extension and modification of a library of routines and data
`
`20 without requiring source code to the original library. Polymorphism allows one body
`
`of code to work on an arbitrary number of data types. For the sake of simplicity
`
`traditional objects may be seen to contain both methods and data. Methods provide
`
`the mechanisms by which the internal state of an object may be modified or by which
`
`communication may occur with another object or by which the instantiation or
`
`25
`
`removal of objects may be directed.
`
`With reference to Figure 2, a distributed object technology based around an
`
`Object Request Broker will now be described. Whereas "standard" object-oriented
`
`programming (OOP) languages can be used to build monolithic programs out of many
`
`object building blocks, distributed object technologies (DOOP) allow the creation of
`
`30
`
`programs whose components may be spread across multiple machines. As shown in
`
`Figure 2, an object system 200 includes client objects 210 and server objects 220. To
`
`implement a client-server relationship between objects, the distributed object system
`
`Attornev Docket No: SRIIP016(3477)/BRC/EWJ
`
`Page 3 of 59
`
`Page 5 of 778
`
`
`
`200 uses a registry mechanism (COREA's registry is called an Object Request Broker,
`
`or ORB) 230 to store the interface descriptions of available objects. Through the
`
`services of the ORB 230, a client can transparently invoke a method on a remote
`
`server object. The ORB 230 is then responsible for finding the object 220 that can
`
`5
`
`implement the request, passing it the parameters, invoking its method, and returning
`
`the results. In the most sophisticated systems, the client 210 does not have to be aware
`
`of where the object is located, its programming language, its operating system, or any
`
`other system aspects that are not part of the server object's interface.
`
`Although distributed objects offer a powerful paradigm for creating networked
`
`10
`
`applications, certain aspects of the approach are not perfectly tailored to the
`
`constantly changing environment of the Internet. A major restriction of the DOOP
`
`approach is that the interactions among objects are fixed through explicitly coded
`
`instructions by the application developer. It is often difficult to reuse an object in a
`
`new application without bringing along all its inherent dependencies on other objects
`
`15
`
`(embedded interface definitions and explicit method calls). Another restriction of the
`
`DOOP approach is the result of its reliance on a remote procedure call (RPC) style of
`
`communication. Although easy to debug, this single thread of execution model does
`
`not facilitate programming to exploit the potential for parallel computation that one
`
`would expect in a distributed environment. In addition, RPC uses a blocking
`
`20
`
`(synchronous) scheme that does not scale well for high-volume transactions.
`
`Mobile Objects
`
`Mobile objects, sometimes called mobile agents, are bits of code that can
`
`move to another execution site (presumably on a different machine) under their own
`
`programmatic control, where they can then interact with the local environment. For
`
`25
`
`certain types of problems, the mobile object paradigm offers advantages over more
`
`traditional distributed object approaches. These advantages include network
`
`bandwidth and parallelism. Network bandwidth advantages exist for some database
`
`queries or electronic commerce applications, where it is more efficient to perform
`
`tests on data by bringing the tests to the data than by bringing large amounts of data to
`
`30
`
`the testing program. Parallelism advantages include situations in which mobile agents
`
`can be spawned in parallel to accomplish many tasks at once.
`
`Attornev Docket No: SRI1P016(3477)/BRC/EWJ
`
`Pa!!e 4 of 59
`
`Page 6 of 778
`
`
`
`Some of the disadvantages and inconveniences of the mobile agent approach
`
`include the programmatic specificity of the agent interactions, lack of coordination
`
`support between participant agents and execution environment irregularities regarding
`
`specific programming languages supported by host processors upon which agents
`
`5
`
`reside. In a fashion similar to that of DOOP programming, an agent developer must
`
`programmatically specify where to go and how to interact with the target
`
`environment. There is generally little coordination support to encourage interactions
`
`among multiple (mobile) participants. Agents must be written in the programming
`
`language supported by the execution environment, whereas many other distributed
`
`10
`
`technologies support heterogeneous communities of components, written in diverse
`
`programming languages.
`
`Blackboard Architectures
`
`Blackboard architectures typically allow multiple processes to communicate
`
`by reading and writing tuples from a global data store. Each process can watch for
`
`15
`
`items of interest, perform computations based on the state of the blackboard, and then
`
`add partial results or queries that other processes can consider. Blackboard
`
`architectures provide a flexible framework for problem solving by a dynamic
`
`community of distributed processes. A blackboard architecture provides one solution
`
`to eliminating the tightly bound interaction links that some of the other distributed
`
`20
`
`technologies require during interprocess communication. This advantage can also be a
`
`disadvantage: although a programmer does not need to refer to a specific process
`
`during computation, the framework does not provide programmatic control for doing
`
`so in cases where this would be practical.
`
`Agent-based Software Engineering
`
`25
`
`Several research communities have approached distributed computing by
`
`casting it as a problem of modeling communication and cooperation among
`
`autonomous entities, or agents. Effective communication among independent agents
`
`requires four components: ( 1) a transport mechanism carrying messages in an
`
`asynchronous fashion, (2) an interaction protocol defining various types of
`
`30
`
`communication interchange and their social implications (for instance, a response is
`
`expected of a question), (3) a content language permitting the expression and
`
`interpretation of utterances, and (4) an agreed-upon set of shared vocabulary and
`
`Attornev Docket No: SRIIP016(3477)/BRCIEWJ
`
`Page 5 of 59
`
`Page 7 of 778
`
`
`
`meaning for concepts (often called an ontology). Such mechanisms permit a much
`
`richer style of interaction among participants than can be expressed using a distributed
`
`object's RPC model or a blackboard architecture's centralized exchange approach.
`
`Agent-based systems have shown much promise for flexible, fault-tolerant,
`
`5
`
`distributed problem solving. Several agent-based projects have helped to evolve the
`
`notion of facilitation. However, existing agent-based technologies and architectures
`
`are typically very limited in the extent to which agents can specify complex goals or
`
`influence the strategies used by the facilitator. Further, such prior systems are not
`
`sufficiently attuned to the importance of integrating human agents (i.e., users) through
`
`10
`
`natural language and other human-oriented user interface technologies.
`
`The initial version of SRI International's Open Agent Architecture ™
`("OAA @")technology provided only a very limited mechanism for dealing with
`
`compound goals. Fixed formats were available for specifying a flat list of either
`
`conjoined (AND) sub-goals or disjoined (OR) sub-goals; in both cases, parallel goal
`
`15
`
`solving was hard-wired in, and only a single set of parameters for the entire list could
`
`be specified. More complex goal expressions involving (for example) combinations
`
`of different boolean connectors, nested expressions, or conditionally interdependent
`
`("IF .. THEN") goals were not supported. Further, system scalability was not
`
`adequately addressed in this prior work.
`
`20
`
`SUMMARY OF INVENTION
`
`A first embodiment of the present invention discloses a highly flexible,
`
`software-based architecture for constructing distributed systems. The architecture
`
`25
`
`supports cooperative task completion by flexible, dynamic configurations of
`
`autonomous electronic agents. Communication and cooperation between agents are
`
`brokered by one or more facilitators, which are responsible for matching requests,
`
`from users and agents, with descriptions of the capabilities of other agents. It is not
`
`generally required that a user or agent know the identities, locations, or number of
`
`30
`
`other agents involved in satisfying a request, and relatively minimal effort is involved
`
`in incorporating new agents and "wrapping" legacy applications. Extreme flexibility
`
`is achieved through an architecture organized around the declaration of capabilities by
`
`Attorney Docket No: SRIIP016(3477)/BRC/EWJ
`
`Page 6 of 59
`
`Page 8 of 778
`
`
`
`service-providing agents, the construction of arbitrarily complex goals by users and
`
`service-requesting agents, and the role of facilitators in delegating and coordinating
`
`the satisfaction of these goals, subject to advice and constraints that may accompany
`
`them. Additional mechanisms and features include facilities for creating and
`
`5 maintaining shared repositories of data; the use of triggers to instantiate commitments
`
`within and between agents; agent-based provision of multi-modal user interfaces,
`
`including natural language; and built-in support for including the user as a privileged
`
`member of the agent community. Specific embodiments providing enhanced
`
`scalability are also described.
`
`10
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Prior Art
`
`Prior Art FIGURE 1 depicts a networked computing model;
`
`15
`
`Prior Art FIGURE 2 depicts a distributed object technology based around an
`
`Object Resource Broker;
`
`Examples of the Invention
`
`FIGURE 3 depicts a distributed agent system based around a facilitator agent;
`
`FIGURE 4 presents a structure typical of one small system of the present
`
`20
`
`invention;
`
`FIGURE 5 depicts an Automated Office system implemented in accordance
`
`with an example embodiment of the present invention supporting a mobile user with a
`
`laptop computer and a telephone;
`
`FIGURE 6 schematically depicts an Automated Office system implemented as
`
`25
`
`a network of agents in accordance with a preferred embodiment of the present
`
`invention;
`
`FIGURE 7 schematically shows data structures internal to a facilitator in
`
`accordance with a preferred embodiment of the present invention;
`
`FIGURE 8 depicts operations involved in instantiating a client agent with its
`
`30
`
`parent facilitator in accordance with a preferred embodiment of the present invention;
`
`Attorney Docket No: SRIIP016(3477)/BRC/EWJ
`
`Page 7 of 59
`
`Page 9 of 778
`
`
`
`FIGURE 9 depicts operations involved in a client agent initiating a service
`
`request and receiving the response to that service request in accordance with a certain
`
`preferred embodiment of the present invention;
`
`FIGURE 10 depicts operations involved in a client agent responding to a
`
`5
`
`service request in accordance with another preferable embodiment of the present
`
`invention;
`
`FIGURE 11 depicts operations involved in a facilitator agent response to a
`
`service request in accordance with a preferred embodiment of the present invention;
`
`FIGURE 12 depicts an Open Agent Architecture TM based system of agents
`
`IO
`
`implementing a unified messaging application in accordance with a preferred
`
`embodiment of the present invention;
`
`FIGURE 13 depicts a map oriented graphical user interface display as might
`
`be displayed by a multi-modal map application in accordance with a preferred
`
`embodiment of the present invention;
`
`15
`
`FIGURE 14 depicts a peer to peer multiple facilitator based agent system
`
`supporting distributed agents in accordance with a preferred embodiment of the
`
`present invention;
`
`FIGURE 15 depicts a multiple facilitator agent system supporting at least a
`
`limited form of a hierarchy of facilitators in accordance with a preferred embodiment
`
`20
`
`of the present invention; and
`
`FIGURE 16 depicts a replicated facilitator architecture in accordance with one
`
`embodiment of the present invention.
`
`BRIEF DESCRIPTION OF THE APPENDICES
`
`25
`
`The Appendices provide source code for an embodiment of the present
`
`invention written in the PROLOG programming language.
`
`APPENDIX A: Source code file named compound. pl.
`
`APPENDIX B: Source code file named fac.pl.
`
`APPENDIX C: Source code file named libcom_tcp.pl.
`
`Attornev Docket No: SRI1P016(3477)fBRC/EWJ
`
`Page 8 of 59
`
`Page 10 of 778
`
`
`
`APPENDIX D: Source code file named liboaa.pl.
`
`APPENDIX E: Source code file named translations.pl.
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`5
`
`Figure 3 illustrates a distributed agent system 300 in accordance with one
`
`embodiment of the present invention. The agent system 300 includes a facilitator
`
`agent 310 and a plurality of agents 320. The illustration of Figure 3 provides a high
`
`level view of one simple system structure contemplated by the present invention. The
`
`facilitator agent 310 is in essence the "parent" facilitator for its "children" agents 320.
`
`10
`
`The agents 320 forward service requests to the facilitator agent 310. The facilitator
`
`agent 310 interprets these requests, organizing a set of goals which are then delegated
`
`to appropriate agents for task completion.
`
`The system 300 of Figure 3 can be expanded upon and modified in a variety of
`
`ways consistent with the present invention. For example, the agent system 300 can be
`
`IS
`
`distributed across a computer network such as that illustrated in Figure 1. The
`
`facilitator agent 310 may itself have its functionality distributed across several
`
`different computing platforms. The agents 320 may engage in interagent
`
`communication (also called peer to peer communications). Several different systems
`
`300 may be coupled together for enhanced performance. These and a variety of other
`
`20
`
`structural configurations are described below in greater detail.
`
`Figure 4 presents the structure typical of a small system 400 in one
`
`embodiment of the present invention, showing user interface agents 408, several
`
`application agents 404 and meta-agents 406, the system 400 organized as a
`
`community of peers by their common relationship to a facilitator agent 402. As will
`
`25
`
`be appreciated, Figure 4 places more structure upon the system 400 than shown in
`
`Figure 3, but both are valid representations of structures of the present invention. The
`
`facilitator 402 is a specialized server agent that is responsible for coordinating agent
`
`communications and cooperative problem-solving. The facilitator 402 may also
`
`provide a global data store for its client agents, allowing them to adopt a blackboard
`
`30
`
`style of interaction. Note that certain advantages are found in utilizing two or more
`
`facilitator agents within the system 400. For example, larger systems can be
`
`assembled from multiple facilitator/client groups, each having the sort of structure
`
`Attornev Docket No: SRIIP016(3477)/BRC!EWJ
`
`Page 9 of 59
`
`Page 11 of 778
`
`
`
`shown in Figure 4. All agents that are not facilitators are referred to herein
`
`generically as client agents-- so called because each acts (in some respects) as a client
`
`of some facilitator, which provides communication and other essential services for the
`
`client.
`
`5
`
`The variety of possible client agents is essentially unlimited. Some typical
`
`categories of client agents would include application agents 404, meta-agents 406,
`
`and user interface agents 408, as depicted in Figure 4. Application agents 404 denote
`
`specialists that provide a collection of services of a particular sort. These services
`
`could be domain-independent technologies (such as speech recognition, natural
`
`10
`
`language processing 410, email, and some forms of data retrieval and data mining) or
`
`user-specific or domain-specific (such as a travel planning and reservations agent).
`
`Application agents may be based on legacy applications or libraries, in which case the
`
`agent may be little more than a wrapper that calls a pre-existing API 412, for
`
`example. Meta-agents 406 are agents whose role is to assist the facilitator agent 402
`
`15
`
`in coordinating the activities of other agents. While the facilitator 402 possesses
`
`domain-independent coordination strategies, meta-agents 406 can augment these by
`
`using domain- and application-specific knowledge or reasoning (including but not
`
`limited to rules, learning algorithms and planning).
`
`With further reference to Figure 4, user interface agents 408 can play an
`
`20
`
`extremely important and interesting role in certain embodiments of the present
`
`invention. By way of explanation, in some systems, a user interface agent can be
`
`implemented as a collection of "micro-agents", each monitoring a different input
`
`modality (point-and-click, handwriting, pen gestures, speech), and collaborating to
`
`produce the best interpretation of the current inputs. These micro-agents are depicted
`
`25
`
`in Figure 4, for example, as Modality Agents 414. While describing such
`
`subcategories of client agents is useful for purposes of illustration and understanding,
`
`they need not be formally distinguished within the system in preferred
`
`implementations of the present invention.
`
`The operation of one preferred embodiment of the present invention will be
`
`30
`
`discussed in greater detail below, but may be briefly outlined as follows. When
`
`invoked, a client agent makes a connection to a facilitator, which is known as its
`
`parent facilitator. These connections are depicted as a double headed arrow between
`
`Attornev Docket No: SRI1P016(3477)1BRC/EWJ
`
`Page 10 of 59
`
`Page 12 of 778
`
`
`
`the client agent and the facilitator agent in Figure 3 and 4, for example. Upon
`
`connection, an agent registers with its parent facilitator a specification of the
`
`capabilities and services it can provide. For example, a natural language agent may
`
`register the characteristics of its available natural language vocabulary. (For more
`
`5
`
`details regarding client agent connections, see the discussion of Figure 8 below.)
`
`Later during task completion, when a facilitator determines that the registered services
`
`416 of one of its client agents will help satisfy a goal, the facilitator sends that client a
`
`request expressed in the Interagent Communication Language (ICL) 418. (See Figure
`
`11 below for a more detailed discussion of the facilitator operations involved.) The
`
`10
`
`agent parses this request, processes it, and returns answers or status reports to the
`
`facilitator. In processing a request, the client agent can make use of a variety of
`
`infrastructure capabilities provided in the preferred embodiment. For example, the
`
`client agent can use ICL 418 to request services of other agents, set triggers, and read
`
`or write shared data on the facilitator or other client agents that maintain shared data.
`
`15
`
`(See the discussion of Figures 9-11 below for a more detailed discussion of request
`
`processing.)
`
`The functionality of each client agent are made available to the agent
`
`community through registration of the client agent's capabilities with a facilitator 402.
`
`A software "wrapper" essentially surrounds the underlying application program
`
`20
`
`performing the services offered by each client. The common infrastructure for
`
`constructing agents is preferably supplied by an agent library. The agent library is
`
`preferably accessible in the runtime environment of several different programming
`
`languages. The agent library preferably minimizes the effort required to construct a
`
`new system and maximizes the ease with which legacy systems can be "wrapped" and
`
`25 made compatible with the agent-based architecture of the present invention.
`
`By way of further illustration, a representative application is now briefly
`
`presented with reference to Figures 5 and 6. In the Automated Office system depicted
`
`in Figure 5, a mobile user with a telephone and a laptop computer can access and task
`
`commercial applications such as calendars, databases, and email systems running
`
`30
`
`back at the office. A user interface (UI) agent 408, shown in Figure 6, runs on the
`
`user's local laptop and is responsible for accepting user input, sending requests to the
`
`facilitator 402 for delegation to appropriate agents, and displaying the results of the
`
`Attornev Docket No: SRIIPOI6(3477l/BRC/EWJ
`
`Page 11 of 59
`
`Page 13 of 778
`
`
`
`distributed computation. The user may interact directly with a specific remote
`
`application by clicking on active areas in the interface, calling up a form or window
`
`for that application, and making queries with standard interface dialog mechanisms.
`
`Conversely, a user may express a task to be executed by using typed, handwritten, or
`
`5
`
`spoken (over the telephone) English sentences, without explicitly specifying which
`
`agent or agents should perform the task.
`
`For instance, if the question "What is my schedule?" is written 420 in the user
`
`interface 408, this request will be sent 422 by the UI 408 to the facilitator 402, which
`
`in tum will ask 424 a natural language (NL) agent 426 to translate the query into ICL
`
`10
`
`18. To accomplish this task, the NL agent 426 may itself need to make requests of the
`
`agent community to resolve unknown words such as "me" 428 (the UI agent 408 can
`
`respond 430 with the name of the current user) or "schedule" 432 (the calendar agent
`
`434 defines this word 436). The resulting ICL expression is then routed by the
`
`facilitator 402 to appropriate agents (in this case, the calendar agent 434) to execute
`
`15
`
`the request. Results are sent back 438 to the UI agent 408 for display.
`
`The spoken request "When mail arrives for me about security, notify me
`
`immediately." produces a slightly more complex example involving communication
`
`among all agents in the system. After translation into ICL as described above, the
`
`facilitator installs a trigger 440 on the mail agent 442 to look for new messages about
`
`20
`
`security. When one such message does arrive in its mail spool, the trigger fires, and
`
`the facilitator matches the action part of the trigger to capabilities published by the
`
`notification agent 446. The notification agent 446 is a meta-agent, as it makes use of
`
`rules concerning the optimal use of different output modalities (email, fax, speech
`
`generation over the telephone) plus information about an individual user's preferences
`
`25
`
`448 to determine the best way of relaying a message through available media transfer
`
`application agents. After some competitive parallelism to locate the user (the
`
`calendar agent 434 and database agent 450 may have different guesses as to where to
`
`find the user) and some cooperative parallelism to produce required information
`
`(telephone number of location, user password, and an audio file containing a text-to-
`
`30
`
`speech representation of the email message), a telephone agent 452 calls the user,
`
`verifying its identity through touchtones, and then play the message.
`
`Attornev Docket No: SRI1P016(3477)/BRC/EWJ
`
`Pa2e 12 of 59
`
`Page 14 of 778
`
`
`
`The above example illustrates a number of inventive features. As new agents
`
`connect to the facilitator, registering capability specifications and natural language
`
`vocabulary, what the user can say and do dynamically changes; in other words, the
`
`ICL is dynamically expandable. For example, adding a calendar agent to the system
`
`5
`
`in the previous example and registering its capabilities enables users to ask natural
`
`language questions about their "schedule" without any need to revise code for the
`
`facilitator, the natural language agents, or any other client agents. In addition, the
`
`interpretation and execution of a task is a distributed process, with no single agent
`
`defining the set of possible inputs to the system. Further, a single request can produce
`
`10
`
`cooperation and flexible communication among m