`
`
`IN THE UNITED STATES PATENT AND TRADEMARK OFFICE
`
`CERTIFICATE OF EXPRESS MAILING
`Attorney Docket No.: SRI1P016
`I hereby certify that this paper and the documents and/orfees referred to as — 5
`.
`:
`attached therein are being deposited with the United States Postal Service oS,
`on January 05, 1999 in an envelope as “Express Mail Post Office to a =>= First Named Inventor:
`Addressee” service
`e
`abel Number a
`E£L221766053US, «4
`=" ~CHEYER, AdamJ.
`Washington, D¢,
`oS a
`,
`vr Ve
`2 ——e
`Ze
`=
`
`—— 7
`>
`=
`Michael L. Gough
`ES=c
`=
`
`
`
`UTILITY PATENT APPLICATION TRANSMITTAL (37 CFR § 1.53(b))
`
`oO >
`. =
`bg =
`- 7"
`a= Spa
`a
`oo
`ou =
`owSO
`22 ay
`2 =?==
`
`Assistant Commissioner for Patents
`Box Patent Application
`Washington, DC 20231
`
`-
`
`[| Duplicate for
`fee processing
`
`| Sir:
`
`This is a requestfor filing a patent application under 37 CFR § 1.53(b) in the nameof inventors:
`Adam J. Cheyer and David L. Martin
`
`SOFTWARE-BASED ARCHITECTURE FOR COMMUNICATION AND COOPERATION AMONG
`=~ For:
`
`DISTRIBUTED ELECTRONIC AGENTS
`
`ix] 59 Pages of Specification, Claims and Abstract
`hx] 16 Sheets ofDrawings
`x 01 Pages Combined Declaration and Power of Attorney
`
`Accompanying Application Parts:
`
` Application Elements:
`
`
`Assignment and Assignment Recordation Cover Sheet (recording fee not enclosed)
`| Return Receipt Postcard
`
`Fee Calculation (37 CFR§1.16
`
` (Col. 1) (Col. 2) SMALL ENTITY OR LARGE ENTITY
`
`
`
`NO. FILED NO.EXTRA RATE FEE
`RATE FEE
`OR
`$395
`$
`$760
`$760.00
`BASIC FEE
`
`
`
`TOTAL CLAIMS -20=_6989 xll= $ OR x18 = $1242.00
`
`
`
`
`
`INDEP CLAIMS -03 =_0306 x41= $§$ OR x78 = $234.00
`
`
`Total
`$
`OR
`Total $2236.00
`* Tf the difference in Col. 1 is less
`than zero, enter "O" in Col. 2.
`
`
`
`Includingfiling fees and the assignment recordation fee of $40.00, the Commissioneris authorized to
`chargeall required fees to Deposit Account No. 50-0384 (Order No. SRI1P016).
`
`The Commissioneris 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 of 2
`
`DISH, Exh. 1008, p. 1
`
`DISH, Exh. 1008, p. 1
`
`
`
`7
`<
`“General Authorization for Petition for Extension of Time (37 CFR §1.136)
`
`Applicants hereby make and generally authorize any Petitions for Extensions of Time as may be
`needed for any subsequentfilings. 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.
`
`Please send correspondenceto the following address:
`
`:
`
`_., Date:
`
`es
`
`
`
`Brian R. Coleman
`HICKMAN STEPHENS & COLEMAN, LLP
`P.O. Box 52037
`Palo Alto, CA 94303-0746
`
`Tel (650) 470-7430
`Fax (650) 470-7440
`
`Yo
`
`| 2 2S
`
`er
`
`
`Brian R. Coleman
`Registration No. 39,145
`
`(Revised 12/97, Pat App Trans 53(b) Reg
`
`Page 2 of 2
`
`DISH, Exh. 1008, p. 2
`
`DISH, Exh. 1008, p. 2
`
`
`
`wae
`
`Software-Based Architecture for Communication and Cooperation Among
`
`Distributed Electronic Agents
`
`By:
`
`Adam J. Cheyer and David L. Martin
`
`BACKGROUNDOF THE INVENTION
`
`Field of the Invention
`Thepresent inventionis 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
`communication languages enabling client agents to make requests in the form of
`arbitrarily complex goal expressionsthat are solved through facilitation by a
`
`facilitator agent.
`
`Context and Motivation for Distributed Software Systems
`
`20
`
`25
`
`30
`
`The evolution of models for the design and construction of distributed
`software systemsis being driven forward by several closely interrelated trends: the
`adoption of a networked computing model, rapidly rising expectations for smarter,
`longer-lived, more autonomoussoftware applications and an ever increasing demand
`for more accessible andintuitive user interfaces.
`
`Prior Art Figure | illustrates a networked computing model 100 having a
`plurality of client and server computer systems 120 and 122 coupled together over a
`physical transport mechanism 140. The adoption of the networked computing model
`100 has lead to a greatly increased reliance on distributedsites for both data and
`processing resources. Systems suchas the networked computing model 100 are based
`uponat least one physical transport mechanism 140 coupling the multiple computer
`systems 120 and 122 to support the transfer of information between these computers.
`Someof these computers basically support using the network and are known as client
`
`Attorney Docket No: SRI1P016(3477/BRC/EWJ
`
`DISH, Exha¥6obOf 39
`
`
`
`
`
`
`
`DISH, Exh. 1008, p. 3
`
`
`
`
`
`computers (clients). Some of these computers provide resources to other computers
`
`and are knownas server computers (servers). The servers 122 can vary greatly in the
`
`resources they possess, access they provide and services madeavailable to other
`
`computers across a network. Servers may service other servers as well as clients.
`
`ww
`
`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 programsto reside on the user's desktop machine.
`
`The data now routinely accessed from computers spread around the world has become
`
`increasinglyrich 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 mayalso include programsthat can
`
`be downloaded and executed on the local machine. There is an ever increasing
`
`reliance on networked computing, necessitating software design approachesthat 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 deploymentof 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 ofthis trend. Commercial
`enterprises are introducing significantly more advanced approaches, in many cases
`employing recent research results from artificial intelligence, data mining, machine
`
`learning, and otherfields.
`
`Morethan 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” modelof interaction, in which
`
`an individual user masters a fixed selection of commandsprovided bya single
`
`30
`
`application. Ubiquitous computing, in networked environments, has brought about a
`
`situation in whichthe typical user of many softwareservicesis likely to be a non-
`
`expert, who may access a given service infrequently or only a few times.
`
`Attorney Docket No: SRI1P016(3477/BRC/EWJ
`
`Page 2 of 59
`DISH, Exh. 1008, p. 4
`
`DISH, Exh. 1008, p. 4
`
`
`
`
`
`
`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
`
`of human-computerinteraction 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
`
`modularity of code: encapsulation, inheritance and polymorhpism. Encapsulation
`
`encouragesthecreation oflibrary interfaces that minimize dependencies on
`
`underlying algorithms or data structures. Changes to programming internals can be
`
`made ata later date with requiring modifications to the codethat uses the library.
`
`Inheritance permits the extension and modification ofa 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 numberof 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 canbe used to build monolithic programsout of many
`object building blocks, distributed object technologies (DOOP)allow the creation of
`
`30
`
`programs whose components maybe spread across multiple machines. As shown in
`
`Figure 2, an object system 200 includes client objects 210 and server objects 220. To
`
`implementa client-server relationship between objects, the distributed object system
`
`Attorney Docket No: SRI1P016(3477¥BRC/EWJ
`
`Page 3 of 59
`DISH, Exh. 1008, p. 5
`
`DISH, Exh. 1008, p. 5
`
`
`
`
`
`
`200 uses a registry mechanism (CORBA'sregistry is called an Object Request Broker,
`
`or ORB) 230to 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 230is then responsible for finding the object 220 that can
`
`implementthe request, passingit 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.
`
`Althoughdistributed objects offer a powerful paradigm for creating networked
`
`applications, certain aspects of the approachare not perfectly tailored to the
`
`constantly changing environmentof the Internet. A majorrestriction 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 objectin a
`
`new application without bringing alongall its inherent dependencies on other objects
`
`(embeddedinterface definitions and explicit method calls). Another restriction ofthe
`
`DOOPapproachis 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
`
`notfacilitate programmingto exploit the potential for parallel computation that one
`
`would expectin a distributed environment.
`
`In addition, RPC uses a blocking
`
`20
`
`(synchronous) schemethat 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 theninteract 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 amountsof data to
`
`30
`
`the testing program. Parallelism advantagesincludesituations in which mobile agents
`
`can be spawned in parallel to accomplish many tasksat once.
`
`Attorney Docket No: SRILP016(3477)/BRC/EWJ
`
`Page 4 of 59
`DISH, Exh. 1008, p. 6
`
`DISH, Exh. 1008, p. 6
`
`
`
`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 environmentirregularities regarding
`
`specific programming languages supported by host processors upon which agents
`
`reside. In a fashion similar to that of DOOP programming,an agent developer must
`
`programmatically specify where to go and howto 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
`
`technologies support heterogeneous communities of components, written in diverse
`
`programminglanguages.
`
`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
`
`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 someof the other distributed
`
`technologies require during interprocess communication. This advantage can also be a
`
`disadvantage: although a programmerdoesnot needto 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
`
` 20
`
`23
`
`Several research communities have approacheddistributed computing by
`
`casting it as a problem of modeling communication and cooperation among
`
`autonomousentities, or agents. Effective communication among independentagents
`
`requires four components: (1) a transport mechanism carrying messages in an
`
`asynchronousfashion, (2) an interaction protocol defining various types of
`
`30
`
`communication interchange and their social implications (for instance, a responseis
`
`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
`
`Attorney Docket No: SRITP0O16(3477VBRC/EWJ
`
`Page 5 of 59
`DISH, Exh. 1008, p. 7
`
`DISH, Exh. 1008, p. 7
`
`
`
`richer style of interaction amongparticipants than can be expressedusingadistributed
`
`meaning for concepts (often called an ontology). Such mechanisms permit a much
`
`object's RPC modelor a blackboard architecture's centralized exchange approach.
`
`Agent-based systems have shown much promiseforflexible, fault-tolerant,
`
`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 thefacilitator. Further, such prior systems are not
`
`sufficiently attuned to the importance of integrating human agents (i.e., users) through
`
`natural language and other human-oriented user interface technologies.
`
`Theinitial version of SRI International's Open Agent Architecture™
`("OAA®") technology provided only a very limited mechanism for dealing with
`
`compoundgoals. Fixed formats were available for specifying a flatlist of either
`conjoined (AND)sub-goals or disjoined (OR) sub-goals; in both cases, parallel goal
`
`solving was hard-wiredin, 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.
`
`SUMMARYOF INVENTION
`
`
`
`15
`
`20
`
`A first embodimentof 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
`
`autonomouselectronic agents. Communication and cooperation between agents are
`
`brokered by one or morefacilitators, 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
`other agents involvedin satisfying a request, and relatively minimal effort is involved
`
`30
`
`in incorporating new agents and "wrapping" legacy applications. Extremeflexibility
`
`is achieved through an architecture organized around the declaration of capabilities by
`
`Attorney Docket No: SRI1P016(3477/VBRC/EW]
`
`Page 6 of 59
`DISH, Exh. 1008, p. 8
`
`DISH, Exh. 1008, p. 8
`
`
`
`service-providing agents, the construction ofarbitrarily 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
`
`maintaining shared repositories of data; the use oftriggers to instantiate commitments
`
`within and between agents; agent-based provision of multi-modaluserinterfaces,
`
`including natural language; and built-in support for including the useras a privileged
`
`memberof the agent community. Specific embodiments providing enhanced
`
`scalability are also described.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Prior Art
`
`Prior Art FIGURE 1 depicts a networked computing model;
`
`Prior Art FIGURE 2 depicts a distributed object technology based around an
`
`Object Resource Broker;
`
`Examplesof the Invention
`
`FIGURE 3 depicts a distributed agent system based arounda facilitator agent;
`
`
`
`FIGURE4presents 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 embodimentof the present invention supporting a mobile user with a
`
`laptop computer and a telephone;
`
`FIGURE6schematically depicts an Automated Office system implemented as
`
`25
`
`a network of agents in accordance with a preferred embodimentofthe present
`
`invention;
`
`FIGURE 7 schematically shows data structures internal to a facilitator in
`
`accordance with a preferred embodimentof the present invention;
`
`FIGURE 8 depicts operations involvedin instantiating a client agent with its
`
`30
`
`parentfacilitator in accordance with a preferred embodimentof the present invention;
`
`Attorney Docket No: SRI1P016(3477/¥BRC/EWJ
`
`Page 7 of 59
`DISH, Exh. 1008, p. 9
`
`DISH, Exh. 1008, p. 9
`
`
`
`FIGURE9 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 embodimentofthe present invention;
`
`FIGURE 10 depicts operations involved in a client agent responding to a
`
`5
`
`service request in accordance with another preferable embodimentof the present
`
`invention;
`
`FIGURE 11 depicts operations involved in a facilitator agent response to a
`
`service request in accordance with a preferred embodimentof the present invention;
`
`FIGURE12 depicts an Open Agent Architecture™ based system of agents
`implementing a unified messaging application in accordance with a preferred
`
`10
`
`embodimentof 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
`
`embodimentof the present invention;
`
`15
`
`FIGURE 1|4 depicts a peer to peer multiple facilitator based agent system
`
`supporting distributed agents in accordance with a preferred embodimentof the
`
`present invention;
`
`FIGURE 15 depicts a multiple facilitator agent system supportingat 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
`
`embodimentof the present invention.
`
`BRIEF DESCRIPTION OF THE APPENDICES
`
`25
`
`The Appendices provide source code for an embodimentof the present
`
`invention written in the PROLOG programminglanguage.
`
`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.
`
`
`
`Page 8 of 59
`Attorney Docket No: SRI1P016(3477)/BRC/EWS
`DISH, Exh. 1008, p. 10nnaeteata
`
`DISH, Exh. 1008, p. 10
`
`
`
`
`
`‘te
`
`APPENDIX D: Source code file named liboaa.pl.
`
`APPENDIX E: Source code file named translations.p].
`
`DETAILED DESCRIPTION OF THE INVENTION
`
`in
`
`Figure 3 illustrates a distributed agent system 300 in accordance with one
`
`embodimentof the present invention. The agent system 300 includesa 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
`
`i5
`
`distributed across a computer network such as that illustrated in Figure 1. The
`
`facilitator agent 310 mayitself haveits functionality distributed across several
`
`different computing platforms. The agents 320 may engagein 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
`
`embodimentof the present invention, showing userinterface agents 408, several
`
`application agents 404 and meta-agents 406, the system 400 organizedas a
`
`community of peers by their commonrelationship to a facilitator agent 402. As will
`
`25
`
`be appreciated, Figure 4 places more structure upon the system 400 than shownin
`
`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 globaldata store for its client agents, allowing them to adopt a blackboard
`
`30
`
`style of interaction. Note that certain advantages are foundin 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 ofstructure
`
`Attorney Docket No: SRI1P016(3477)/BRC/EWJ
`
`Page 9 of 59
`DISH, Exh. 1008, p. 11
`
`DISH, Exh. 1008, p. 11
`
`
`
`
`
`
`shown in Figure 4. All agentsthatare not facilitators are referred to herein
`
`generically as client agents -- so called because each acts (in some respects)asa client
`
`of somefacilitator, which provides communication and other essential services for the
`
`client.
`
`an
`
`The variety of possible client agents is essentially unlimited. Some typical
`
`categories of client agents would include application agents 404, meta-agents 406,
`
`and userinterface 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 formsofdataretrieval and data mining) or
`
`user-specific or domain-specific (such as a travel planning and reservations agent).
`
`Application agents may be based on legacy applicationsor libraries, in which case the
`
`agent may belittle more than a wrapperthat calls a pre-existing API 412,for
`
`example. Meta-agents 406 are agents whose role is to assist the facilitator agent 402
`
`in coordinating theactivities of other agents. While the facilitator 402 possesses
`
`domain-independentcoordination 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
`
`extremely important andinteresting role in certain embodiments ofthe 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
`
`producethe best interpretation of the current inputs. These micro-agents are depicted
`in Figure 4, for example, as Modality Agents 414. While describing such
`
`subcategoriesof client agents is useful for purposesofillustration and understanding,
`
`they need not be formally distinguished within the system in preferred
`
`implementations of the present invention.
`
`The operation of one preferred embodimentof the present invention will be
`
`30
`
`discussed in greaterdetail below, but may be briefly outlined as follows. When
`
`invoked, a client agent makes a connectionto a facilitator, which is knownasits
`
`parentfacilitator. These connections are depicted as a double headed arrow between
`
`Attorney Docket No: SRIP016(3477VBRC/EWS
`
`Page 10 of 59
`DISH, Exh. 1008, p. 12
`
`DISH, Exh. 1008, p. 12
`
`
`
`
`
`
`
`the client agent andthe 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
`
`details regarding client agent connections, see the discussion of Figure 8 below.)
`
`Later during task completion, when a facilitator determinesthat the registered services
`
`416 of oneofits client agents will help satisfy a goal, the facilitator sends that client a
`
`request expressed in the Interagent Communication Language (CL) 418. (See Figure
`
`11 below for a more detailed discussion of the facilitator operations involved.) The
`
`agent parses this request, processesit, and returns answersor 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 CL 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.
`
`(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 commoninfrastructure for
`
`constructing agents is preferably supplied by an agentlibrary. The agentlibraryis
`
`preferably accessible in the runtime environmentofseveral different programming
`
`languages. The agentlibrary 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 wayof further illustration, a representative application is now briefly
`
`presented with reference to Figures 5 and6. 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 (UD agent 408, shown in Figure 6, runs on the
`
`user's local laptop andis responsible for accepting user input, sending requests to the
`
`facilitator 402 for delegation to appropriate agents, and displaying the results of the
`
`Attorney Docket No: SRI1P016(3477/BRC/EWJ
`
`Page 11 of 59
`DISH, Exh. 1008, p. 13
`
`DISH, Exh. 1008, p. 13
`
`
`
`distributed computation. The user mayinteract 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 standardinterface dialog mechanisms.
`
`Conversely, a user may express a task to be executed by using typed, handwritten, or
`
`spoken (overthe 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 turn will ask 424 a natural language (NL) agent 426 to translate the query into JCL
`
`18. To accomplish this task, the NL agent 426 mayitself need to make requests of the
`
`agent community to resolve unknown wordssuch 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 JCL expression is then routed by the
`
`facilitator 402 to appropriate agents (in this case, the calendar agent 434) to execute
`
`the request. Results are sent back 438 to the UI agent 408fordisplay.
`
`The spoken request "When mail arrives for me about security, notify me
`
`immediately.” produces a slightly more complex example involving communication
`
`amongall agents in the system. After translation into JCL 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 doesarrive in its mail spool, the trigger fires, and
`
`the facilitator matchesthe action part ofthe trigger to capabilities published by the
`
`notification agent 446. Thenotification agent 446 is a meta-agent, as it makes use of
`
`rules concerning the optimaluse of different output modalities (email, fax, speech
`
`generation overthe telephone) plus information aboutan individual user's preferences
`448 to determinethe 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 numberof location, user password, and an audio file containing a text-to-
`
`speechrepresentation of the email message), a telephone agent 452 calls the user,
`
`verifying its identity through touchtones, andthen play the message.
`
`
`
`
`Attorney Docket No: SRI1P016(3477)/BRC/EWJ
`
`Page 12 of 59
`DISH, Exh. 1008, p. 14
`
`DISH, Exh. 1008, p. 14
`
`
`
`
`
`The above example illustrates a numberof inventive features. As new agents
`
`connectto 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
`
`in the previous example and registering its capabilities enables users to ask natural
`
`language questions abouttheir "schedule" without any needto 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 many agents, written in different
`
`programming languages and spread across multiple machines.
`
`Design Philosophy and Considerations
`
`Onepreferred embodimentprovides an integration mechanism for
`
`15
`
`heterogeneous applications in a distributed infrastructure, incorporating someof the
`
`dynamism and extensibility of blackboard approache