`Cheyer et al.
`
`111111
`
`1111111111111111111111111111111111111111111111111111111111111
`US006851115Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,851,115 B1
`Feb.1,2005
`
`(54) SOFTWARE-BASED ARCHITECTURE FOR
`COMMUNICATION AND COOPERATION
`AMONG DISTRIBUTED ELECTRONIC
`AGENTS
`
`(75)
`
`Inventors: Adam J. Cheyer, Palo Alto, CA (US);
`David L. Martin, Santa Clara, CA
`(US)
`
`(73) Assignee: SRI International, Menlo Park, CA
`(US)
`
`( *) Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/225,198
`
`(22)
`
`Filed:
`
`Jan. 5, 1999
`
`(51)
`(52)
`(58)
`
`(56)
`
`Int. Cl? .................................................. G06F 9/54
`U.S. Cl. ........................ 719/317; 709/202; 717!114
`Field of Search .......................... 719/317; 709/202,
`709/207, 317; 717!114
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,638,494 A *
`5,802,396 A *
`5,960,404 A *
`6,047,053 A
`6,212,649 B1 *
`6,216,173 B1 *
`6,256,771 B1
`6,338,081 B1 *
`6,411,684 B1
`6,484,155 B1 *
`2001!0039562 A1 *
`2003/0167247 A1 *
`
`Pinard et a!.
`. . . . . . . . . . . . . . . 709/202
`Gray ........................... 710/20
`Chaar et a!. . . . . . . . . . . . . . . . . . . 705/11
`Miner eta!.
`Yalowitz eta!. .............. 714/31
`Jones et a!. . . . . . . . . . . . . . . . . . . . 135/77
`O'Neil eta!.
`Furusawa eta!. ........... 709/202
`Cohn eta!.
`Kiss et a!.
`.................... 706/46
`Sato ........................... 709/202
`Masuoka . ... .. ... ... ... ... .. . 706/46
`
`6/1997
`9/1998
`9/1999
`4/2000
`4/2001
`4/2001
`7/2001
`1!2002
`6/2002
`11/2002
`11/2001
`9/2003
`
`01HER PUBLICATIONS
`
`Cheyer, Adam. "Mechanisms of Cooperation." Oct. 19,
`1998.*
`DeVoe, Deborah. "SRI distributed agents promise flexibil(cid:173)
`ity." Info World. Dec. 30, 1996. *
`
`Sycara, Katia et al. "Distributed Intelligent Agents." IEEE.
`Dec. 1996.*
`Nwana, Hyacinth et al. "Software Agent Technologies". BT
`Technology Journal. 1996. *
`Busetta, Paolo et al. "The BDIM Agent Toolkit Design."
`1997.*
`Mayfield, James et al. "Desiderata for Agent Communica(cid:173)
`tion Languages." Mar. 27-29, 1995. *
`Khedro, Taha et al. Concurrent Endineering through Interop(cid:173)
`erable Software Agents. Aug. 1994.*
`Moran et al. "Multimodal User Interfaces in the Open Agent
`Architecture." Proceedings of the International Conference
`on Intelligent User Interfaces. 6-9/1997.*
`Martin, David et al. "The Open Agent Architecture: A
`Framework for Building Distributed Software Systems."
`Oct. 19, 1998.*
`Wilkins, David et al. "Multiagent Planning Architecture."
`SRI International. Dec. 8, 1997.*
`Moran, Douglas B. and Cheyer, Adam J., "Intelligent
`Agent-based User Interfaces", Article Intelligence center,
`SRI International.
`Martin, David L., Cheyer, Adam J. and Moran, Douglas B.,
`"Building Distributed Software Systems with the Open
`Agent Architecture".
`
`(List continued on next page.)
`
`Primary Examiner-Lewis A Bullock, Jr.
`(74) Attorney, Agent, or Firm-Perkins Coie LLP
`
`(57)
`
`ABSTRACT
`
`A highly flexible, software-based architecture is disclosed
`for constructing distributed systems. The architecture sup(cid:173)
`ports cooperative task completion by flexible and autono(cid:173)
`mous electronic agents. One or more facilitators are used to
`broker communication and cooperation among the agents.
`The architecture provides for the construction of arbitrarily
`complex goals by users and service-requesting agents. Addi(cid:173)
`tional features include agent-based provision of multi modal
`interfaces, including natural language.
`
`89 Claims, 16 Drawing Sheets
`
`- --
`
`--------- -- .:'418
`
`( ___ --~~·~~:"~~-~o~~~~:t~~~~~~~~:_L~l
`___ __ )
`
`Meta
`Agent
`
`404
`
`406
`
`412
`
`Modality Agents 414
`
`GOOGLE EXHIBIT 1007
`
`Page 1 of 37
`
`
`
`US 6,851,115 Bl
`Page 2
`
`01HER PUBLICATIONS
`
`Cohen, Philip R. and Cheyer, Adam, SRI International,
`Wang, Michelle, Stanford University, BAEG, Soon Cheal,
`ETRI, "An Open Agent Architecture".
`Julia, Luc E. and Cheyer,Adam J., SRI International "Coop(cid:173)
`erative Agents and Recognition Systems (CARS) for Drivers
`and Passengers".
`Moran, Douglas B., Cheyer, Adam J., Julia, Luc E., Martin,
`David L., SRI International, and Park, Sangkyu, Electronics
`and Telecommunications Research Institute, "Multimodal
`User Interfaces in the Open Agent Architecture".
`Cheyer, Adam and Lulia, Luc, SRI International "Multimo(cid:173)
`dal Maps: An Agent-based Approach".
`Cutkosky, Mark R., Engelmore, Robert S., Fikes, Richard
`E., Genesereth, Michael R., Gruber, Thomas R., Stanford
`University, Mark, William, Lockheed Palo Alto Research
`Labs, Tenenbaum, Jay M., Weber, Jay C., Enterprise Inte(cid:173)
`gration Technologies, "An Experiment in Integrating Con(cid:173)
`current Engineering Systems".
`
`Martin, David L., Cheyer, Adam, SRI International, LEE,
`Gowang-Lo, ETRI, "Development Tools for the Open
`Agent Architecture", The Practical Application of Intelligent
`Agents and Multi-Agent Technology (PAAM96), London,
`Apr. 1996.
`Cheyer, Adam, Martin, David and Moran, Douglas, "The
`Open Agent architecture™", SRI International, AI Center.
`Dejima, Inc., http://www.dejima.com/.
`Cohen, Philip R, Cheyer, Adam, Wang, Michelle, Stanford
`University, BAEG, Soon Cheal ETRI: "An Open Agent
`Architecture," AAAI Spring Symposium, pp. 1-8, Mar.
`1994.
`Martin, David; Oohama, Hiraki; Moran, Douglas; Cheyer,
`Adam; "Information Brokering in an Agent Architecture,"
`Proceeding of the 2nd International Conference on Practical
`Application of Intelligent Agents & Multi-Agent Technol(cid:173)
`ogy, London, Apr. 1997.
`
`* cited by examiner
`
`Page 2 of 37
`
`
`
`U.S. Patent
`
`Feb. 1,2005
`
`Sheet 1 of 16
`
`US 6,851,115 B1
`
`100
`.~
`
`120
`\
`Client
`Computer
`System
`
`~0
`
`Client
`Computer
`System
`
`~0
`
`Client
`Computer
`System
`
`140
`~~--~--~~)~)~1~----~----~J
`
`I
`
`I
`
`( (
`
`Server
`Computer
`System
`1J2
`
`Server
`Computer
`System
`112
`
`Fig. 1
`(Prior Art)
`
`Page 3 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 2 of 16
`
`US 6,851,115 B1
`
`Distributed Computing Environment
`'
`
`Fig. 2
`(Prior Art)
`
`Page 4 of 37
`
`
`
`U.S. Patent
`U.S. Patent
`
`Feb.1, 2005
`Feb.1,2005
`
`Sheet 3 of 16
`Sheet 3 of 16
`
`US 6,851,115 B1
`US 6,851,115 B1
`
`Facilitator
`
`Agent
`
`320
`
`Fig. 3
`Fig, 3
`
`Page 5 of 37
`
`Page 5 of 37
`
`
`
`U.S. Patent
`
`Feb.l,2005
`
`Sheet 4 of 16
`
`US 6,851,115 B1
`
`400
`
`402
`
`Facilitator Agent
`
`Registry
`
`~416
`t 418
`
`-- - ---------- __ t
`---------
`----------
`Interagent Communication Language (ICL)
`----
`.
`
`/
`-- <.
`)
`,.
`
`--
`
`User
`Interface
`Agent
`
`NL to ICL
`Agent
`
`Application
`Agent
`
`Meta
`Agent
`
`406
`
`Modality Agents 414
`
`Application
`
`Fig. 4
`
`Page 6 of 37
`
`
`
`CHEYER
`
`_u
`
`_II
`
`IL
`
`Open Agent Architecture
`
`_11
`
`IL_ll
`
`II
`
`II
`
`H
`
`ll
`
`~ H
`
`IL ~ H H
`
`IL
`
`_II
`
`ll
`
`_jJ
`
`IL
`
`II
`
`D
`
`II
`
`_II
`
`H
`
`ll
`
`H_
`
`ll
`
`._11
`
`IL
`
`.H
`
`J
`
`u
`I MAIL I
`
`\
`
`0
`
`~---.
`
`[]
`D
`CJ
`
`I
`
`I
`
`d •
`\Jl
`•
`
`e
`rJ'l
`-..a-..
`00
`(It
`J-'
`1--"
`1--"
`(It
`~
`1--"
`
`Adam Chever
`Connected to server. Aaents are now active.
`When mail arrives for me about "security" get it to me
`by telephone. I
`
`Do It
`
`Fig. 5
`
`t
`
`~
`r-
`~
`
`Page 7 of 37
`
`
`
`FACILITATOR AGENT
`
`402
`
`450
`
`d 0
`\Jl
`
`0
`
`Speaker D
`A ent \\
`,,~(U
`
`442
`Bee ironic
`Mal Agent
`i-4"
`
`Web
`Agent
`
`Database
`Agent
`
`~446
`~
`
`~"Llb
`Nattrallang.Jage
`Parser Agent
`
`Notify Agent
`
`VoicernaD
`Agent
`
`420
`
`426
`
`Fig. 6
`
`User
`Preferences
`
`Telephone
`Agent
`
`~
`-432
`Calender
`Agent
`
`[j]
`
`Text To 454
`Speech
`Agent
`
`Prilter
`Agent
`
`Page 8 of 37
`
`
`
`/
`70 0
`
`/702
`Agent Registry
`
`Symbolic
`Name
`
`Unique
`Address
`
`Data
`Trigger
`Capability
`Declarations Declarations Declarations
`
`Task
`Declarations
`
`Process
`Characteristics
`(Machine Type
`Language. etc.
`
`(
`704
`
`(
`706
`
`(
`708
`
`7
`710
`
`T
`712
`
`(
`714
`
`(
`716
`
`d •
`\Jl
`•
`
`~
`720
`
`Global
`Persistent
`Database
`
`Fig. 7
`
`Page 9 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 8 of 16
`
`US 6,851,115 B1
`
`800
`
`802
`
`804
`
`806
`
`Installer Invokes
`New Client Agent
`
`System Instantiates
`New Client Agent
`
`Facilitator And New
`Client Agent Establish
`Communications Link
`
`Client Agent Transmits
`Profile To Facilitator
`
`808
`
`Facilitator Registers
`Client Agent
`
`810
`
`Fig. 8
`
`Cone
`
`812
`
`Page 10 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 9 of 16
`
`US 6,851,115 B1
`
`Start
`
`900
`
`Determine A Goal
`
`902
`
`Construct
`Goal Into
`ICL
`
`Transmit Goal
`To Parent
`Facilitator
`
`Receive
`Results
`
`904
`
`906
`
`908
`
`Done
`
`910
`
`Fig. 9
`
`Page 11 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 10 of 16
`
`US 6,851,115 B1
`
`1000
`
`1002
`
`1004
`
`Receive Request
`For Service
`
`Parse Request
`For Request
`
`Return
`Status
`Report
`
`1008
`
`No
`
`1006
`
`Yes
`
`Perform
`Service
`
`Return Results
`And/Or Status
`Report
`
`1010
`
`1012
`
`Done
`
`1014
`
`Fig. 10
`
`Page 12 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 11 of 16
`
`US 6,851,115 B1
`
`noo
`
`Receive Goal Request
`
`Parse And Interpret
`Goal Request
`
`Construct Goal
`Satisfaction Plan
`
`Determine Required Sub--Goals
`
`Select Agents Suitable For
`Performing Required Sub-Goals
`
`Transmit Requests To
`Selected Agents
`
`Receive Results
`
`No
`
`1116
`
`1102
`
`1104
`
`1106
`
`1108
`
`mo
`
`1112
`
`1114
`
`Return Results
`
`1118
`
`1120
`
`Fig. 11
`
`Page 13 of 37
`
`
`
`FACILITATOR AGENT
`
`~~ 0
`
`Speaker D
`A
`t
`
`442
`8ectronic
`Mail Agent
`
`402
`
`450
`
`Database
`Agent
`
`d •
`\Jl
`•
`
`'JJ. =-~
`~ .....
`'"""' N
`0 ......,
`'"""' 0'1
`
`e
`rJ'l
`-..a-..
`00
`(It
`J-'
`1--"
`1--"
`(It
`~
`1--"
`
`=--
`Telephone
`Agent
`
`w
`
`Text To 454
`Speech
`Agent
`
`Prilter
`Agent
`
`Parser Agent
`
`• Natlral Language
`~
`
`Volcemal
`Agent
`
`426
`
`420
`
`Fig. 12
`
`Page 14 of 37
`
`
`
`[San Francisco, CA: 12]
`
`Q)
`File Edit Action Collaboration Window Help
`
`bJ. X
`b]IDJ~ 1Q1 [San Francisco, CA: 12]
`~ [San Francisco, CA: 12]
`~ m~ @!ill~• [)]] 9
`~~ ~[Q)· ~~ [i]] 9
`
`d •
`\Jl
`•
`
`Fig. 13
`
`Page 15 of 37
`
`
`
`U.S. Patent
`U.S. Patent
`
`Feb. 1, 2005
`Feb.1,2005
`
`Sheet 14 of 16
`Sheet 14 of 16
`
`US 6,851,115 B1
`US 6,851,115 B1
`
`Agent 2
`
`Facilitator
`Agent 1
`
`Facilitator
`
`Fig. 14
`Fig. 14
`
`Page 16 of 37
`
`Page 16 of 37
`
`
`
`U.S. Patent
`
`Feb.1,2005
`
`Sheet 15 of 16
`
`US 6,851,115 B1
`
`1500
`
`/ 1502
`Facilitator
`
`i
`
`I
`
`I
`
`I
`
`' ' ' ' ' ' ' ·\
`' ' ' ' '
`
`1506
`
`\
`
`'
`
`1504
`
`Facilitator
`
`I ,
`
`I
`
`I
`
`, , , , ,
`, I
`/, 1508
`,
`
`I
`
`I
`
`I
`
`I ,
`
`Facilitator
`
`1516
`
`1514
`
`Fig. 15
`
`Page 17 of 37
`
`
`
`d •
`\Jl
`•
`
`1
`
`1604
`
`Registry &
`Planner
`
`161
`
`Replicated
`
`1616
`
`Agent E
`
`1612
`
`1618
`
`1614
`
`Figure 16
`
`Page 18 of 37
`
`
`
`US 6,851,115 Bl
`
`1
`SOFTWARE-BASED ARCHITECTURE FOR
`COMMUNICATION AND COOPERATION
`AMONG DISTRIBUTED ELECTRONIC
`AGENTS
`
`A compact disk containing a computer program listing
`has been provided in duplicate (copy 1 and copy 2 of the
`compact disk are identical). The computer program listing in
`the compact disk is incorporated by reference herein. The
`compact disk contains files with their names, size and date 10
`of creation as follow:
`
`5
`
`2
`documents, and audio and video streams. With the popular(cid:173)
`ization 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 and rela-
`tively 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 person-
`15 alized responses and sharing of preferences, are examples of
`the simplest manifestations of this trend. Commercial enter(cid:173)
`prises are introducing significantly more advanced
`approaches, in many cases employing recent research results
`from artificial intelligence, data mining, machine learning,
`20 and other fields.
`More than ever before, the increasing complexity of
`systems, the development of new technologies, and the
`availability of multimedia material and environments are
`creating a demand for more accessible and intuitive user
`25 interfaces. Autonomous, distributed, multi-component sys(cid:173)
`tems 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 application.
`30 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-expert, who may
`access a given service infrequently or only a few times.
`Accommodating such usage patterns calls for new
`35 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-
`40 computer interaction that draws much more heavily on our
`experience with human-human interactions.
`2. Prior Related Art
`Existing approaches and technologies for distributed
`computing include to 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. Encapsula-
`tion encourages the creation of library interfaces that mini(cid:173)
`mize dependencies on underlying algorithms or data struc(cid:173)
`tures. Changes to programming internals can be made at a
`55 later date with requiring modifications to the code that uses
`the library. Inheritance permits the extension and modifica(cid:173)
`tion of a library of routines and data 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
`60 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 removal of objects may be
`65 directed.
`With reference to FIG. 2, a distributed object technology
`based around an Object Request Broker will now be
`
`File Name
`
`Size
`
`Creation Date Last Date
`
`oaa.pl
`fac.pl
`compound.pl
`com_tcp.pl
`translations. pl
`
`159,613 bytes
`52,733 bytes
`42,937 bytes
`18,010 bytes
`19,583 bytes
`
`1996/10/08
`1997/04/24
`1996/12/11
`1998/02/10
`1998/01/29
`
`1998/12/23
`1998/05/06
`1998/04/10
`1998/05/06
`1998/12/23
`
`BACKGROUND OF THE INVENTION
`1. 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. Cer(cid:173)
`tain embodiments teach interagent communication lan(cid:173)
`guages 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
`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 net(cid:173)
`worked computing model, rapidly rising expectations for
`smarter, longer-lived, more autonomous software applica(cid:173)
`tions and an ever increasing demand for more accessible and
`intuitive user interfaces.
`Prior Art FIG. 1 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 45
`model 100 has lead to a greatly increased reliance on
`distributed sites for both data and processing resources.
`Systems such as the networked computing model 100 are
`based upon at least one physical transport mechanism 140
`coupling the multiple computer systems 120 and 122 to 50
`support the transfer of information between these comput-
`ers.
`Some of these computers basically support using the
`network and are known as client computers (clients). Some
`of these computers provide resource 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.
`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
`
`Page 19 of 37
`
`
`
`US 6,851,115 Bl
`
`4
`
`3
`described. Whereas "standard" object-oriented program(cid:173)
`ming (OOP) languages can be used to build monolithic
`programs out of many object building blocks, distributed
`object technologies (DOOP) allow the creation of programs
`whose components may be spread across multiple machines. 5
`As shown in FIG. 2, an object system 200 includes client
`objects 210 and server objects 220. To implement a client(cid:173)
`server relationship between objects, the distributed object
`system 200 uses a registry mechanism (COREA's registry is
`called an object Request Broker, or ORB) 230 to store the 10
`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 implement the
`request, passing it the parameters, invoking its method, and 15
`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 applications, certain aspects of the
`approach are not perfectly tailored to the constantly chang(cid:173)
`ing environment of the Internet. A major restriction of the
`DOOP approach is that the interactions among objects are 25
`fixed through explicitly coded instructions by the applica(cid:173)
`tion developer. It is often difficult to reuse an object in a new
`application without bringing along all its inherent depen(cid:173)
`dencies on other objects (embedded interface definitions and
`explicit method calls). Another restriction of the DOOP 30
`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 computa(cid:173)
`tion that one would expect in a distributed environment. In 35
`addition, RPC uses a blocking (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 40
`on a different machine) under their own programmatic
`control, where they can then interact with the local en vi(cid:173)
`ronment. For certain types of problems, the mobile object
`paradigm offers advantages over more traditional distributed
`object approaches. These advantages include network band- 45
`width 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 the testing program. Parallelism advan- 50
`tages include situations in which mobile agents can be
`spawned in parallel to accomplish many tasks at once.
`Some of the disadvantages and inconveniences of the
`mobile agent approach include the programmatic specificity
`of the agent interactions, lack of coordination support 55
`between participant agents and execution environment
`irregularities 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 60
`how to interact with the target environment. There is gen(cid:173)
`erally little coordination support to encourage interactions
`among multiple (mobile) participants. Agents must be writ(cid:173)
`ten in the programming language supported by the execution
`environment, whereas many other distributed technologies 65
`support heterogeneous communities of components, written
`in diverse programming languages.
`
`Blackboard Architectures
`Blackboard architectures typically allow multiple pro-
`cesses 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 com(cid:173)
`munity of distributed processes. A blackboard architecture
`provides one solution to eliminating the tightly bound inter(cid:173)
`action links that some of the other distributed 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
`Several research communities have approached distrib(cid:173)
`uted computing by casting it as a problem of modeling
`20 communication and cooperation among autonomous
`entities, or agents. Effective communication among inde(cid:173)
`pendent agents requires four components: (1) a transport
`mechanism carrying messages in an asynchronous fashion,
`(2) an interaction protocol defining various types of com(cid:173)
`munication 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 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 central(cid:173)
`ized exchange approach.
`Agent-based systems have shown much promise for
`flexible, 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 the facilitator. 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.
`The initial version of SRI International's Open Agent
`Architecture TM ("OAA®") technology provided only a very
`limited mechanism for dealing with compound goals. Fixed
`formats were available for specifying a fiat list of either
`conjoined (AND) sub-goals or disjoined (OR) sub-goals; in
`both cases, parallel goal 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 scalabil(cid:173)
`ity was not adequately addressed in this prior work.
`
`SUMMARY OF INVENTION
`
`A first embodiment of the present invention discloses a
`highly flexible, software-based architecture for constructing
`distributed systems. The architecture supports cooperative
`task completion by flexible, dynamic configurations of
`autonomous electronic agents. Communication and coop(cid:173)
`eration 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 other
`
`Page 20 of 37
`
`
`
`US 6,851,115 Bl
`
`5
`agents involved in satisfying a request, and relatively mini(cid:173)
`mal effort is involved in incorporating new agents and
`"wrapping" legacy applications. Extreme flexibility is
`achieved through an architecture organized around the dec(cid:173)
`laration of capabilities by service-providing agents, the 5
`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 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 scal(cid:173)
`ability are also described.
`
`10
`
`6
`DETAILED DESCRIPTION OF THE
`INVENTION
`FIG. 3 illustrates a distributed agent system 300 in accor(cid:173)
`dance 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 FIG. 3 provides
`a high level view of one simple system structure contem(cid:173)
`plated by the present invention. The facilitator agent 310 is
`in essence the "parent" facilitator for its "children" agents
`320. The agents 320 forward service requests to the facili(cid:173)
`tator 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 FIG. 3 can be expanded upon and
`15 modified in a variety of ways consistent with the present
`invention. For example, the agent system 300 can be dis(cid:173)
`tributed across a computer network such as that illustrated in
`FIG. 1. The facilitator agent 310 may itself have its func(cid:173)
`tionality distributed across several different computing plat-
`20 forms. The agents 320 may engage in interagent communi(cid:173)
`cation (also called peer to peer communications). Several
`different systems 300 may be coupled together for enhanced
`performance. These and a variety of other structural con(cid:173)
`figurations are described below in greater detail.
`FIG. 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
`30 402. As will be appreciated, FIG. 4 places more structure
`upon the system 400 than shown in FIG. 3, but both are valid
`representations of structures of the present invention. The
`facilitator 402 is a specialized server agent that is respon(cid:173)
`sible for coordinating agent communications and coopera-
`35 tive problem-solving. The facilitator 402 may also provide a
`global data store for its client agents, allowing them to adopt
`a blackboard style of interaction. Note that certain advan(cid:173)
`tages are found in utilizing two or more facilitator agents
`within the system 400. For example, larger systems can be
`40 assembled from multiple facilitator/client groups, each hav(cid:173)
`ing the sort of structure shown in FIG. 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
`45 and other essential services for the client.
`The variety of possible client agents is essentially unlim(cid:173)
`ited. Some typical categories of client agents would include
`application agents 404, meta-agents 406, and user interface
`agents 408, as depicted in FIG. 4. Application agents 404
`50 denote specialists that provide a collection of services of a
`particular sort. These services could be domain-independent
`technologies (such as speech recognition, natural 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 in
`coordinating the activities of other agents. While the facili(cid:173)
`tator 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
`65 planning).
`With further reference to FIG. 4, user interface agents 408
`can play an extremely important and interesting role in
`
`25
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`Prior Art
`Prior Art FIG. 1 depicts a networked computing model;
`Prior Art FIG. 2 depicts a distributed object technology
`based around an Object Resource Broker;
`Examples of the Invention
`FIG. 3 depicts a distributed agent system based around a
`facilitator agent;
`FIG. 4 presents a structure typical of one small system of
`the present invention;
`FIG. 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;
`FIG. 6 schematically depicts an Automated Office system
`implemented as a network of agents in accordance with a
`preferred embodiment of the present invention;
`FIG. 7 schematically shows data structures internal to a
`facilitator in accordance with a preferred embodiment of the
`present invention;
`FIG. 8 depicts operations involved in instantiating a client
`agent with its parent facilitator in accordance with a pre(cid:173)
`ferred embodiment of the present invention;
`FIG. 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;
`FIG. 10 depicts operations involved in a client agent
`responding to a service request in accordance with another
`preferable embodiment of the present invention;
`FIG. 11 depicts operations involved in a facilitator agent
`response to a service request in accordance with a preferred
`embodiment of the present invention;
`FIG. 12 depicts an Open Agent Architecture™ based
`system of agents implementing a unified messaging appli(cid:173)
`cation in accordance with a preferred embodiment of the
`present invention;
`FIG. 13 depicts a map oriented graphical user interface 55
`display as might be displayed by a multi-modal map appli(cid:173)
`cation in accordance with a preferred embodiment of the
`present invention;
`FIG. 14 depicts a peer to peer multiple facilitator based
`agent system supporting distributed agents in accordance 60
`with a preferred embodiment of the present invention;
`FIG. 15 depicts a multiple facilitator agent system sup(cid:173)
`porting at least a limited form of a hierarchy of facilitators
`in accordance with a preferred embodiment of the present
`invention; and
`FIG. 16 depicts a replicated facilitator architecture in
`accordance with one embodiment of the present