(12) United States Patent
`Cheyer et al.
`
`I 1111111111111111 11111 111111111111111 IIIII IIIII 11111 11111 1111111111 11111111
`US006851115Bl
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,851,115 Bl
`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 O days.
`
`(21) Appl. No.: 09/225,198
`
`(22)
`
`Filed:
`
`Jan. 5, 1999
`
`(51)
`(52)
`(58)
`
`(56)
`
`Int. Cl.7 .................................................. 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 Bl *
`6,216,173 Bl *
`6,256,771 Bl
`6,338,081 Bl *
`6,411,684 Bl
`6,484,155 Bl *
`2001/0039562 Al *
`2003/0167247 Al *
`
`6/1997
`9/1998
`9/1999
`4/2000
`4/2001
`4/2001
`7/2001
`1/2002
`6/2002
`11/2002
`11/2001
`9/2003
`
`. . . . . . . . . . . . . . . 709 /202
`Pinard et al.
`Gray ........................... 710/20
`Chaar et al. . . . . . . . . . . . . . . . . . . 705 /11
`Miner et al.
`Yalowitz et al. .............. 714/31
`Jones et al. . . . . . . . . . . . . . . . . . . . 135 /77
`O'Neil et al.
`Furusawa et al. ........... 709/202
`Cohn et al.
`.................... 706/46
`Kiss et al.
`Sato ........................... 709/202
`Masuoka . ... .. ... ... ... ... .. . 706/46
`
`OTI-IER PUBLICATIONS
`
`Cheyer, Adam. "Mechanisms of Cooperation." Oct. 19,
`1998.*
`De Voe, 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
`
`400
`
`402
`
`Facilitator Agent
`
`_ --
`
`--------- -- <'.°418
`
`( ___ --~~•~~:_°~~-~o~~~~~t~~~~~~~I:_L~)
`_____ )
`
`Meta
`Agent
`
`404
`
`406
`
`Modality Agents 414
`
`Application
`
`412
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 1
`
`

`

`US 6,851,115 Bl
`Page 2
`
`OTI-IER PUBLICATIONS
`
`Cohen, Philip R. and Cheyer, Adam, SRI International,
`Wang, Michelle, Stanford University, BAEG, Soon Cheol,
`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 Cheol 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
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 2
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 1 of 16
`
`US 6,851,115 Bl
`
`100
`
`120
`
`120
`
`120
`
`Client
`Computer
`System
`
`Client
`Computer
`System
`
`Client
`Computer
`System
`
`140
`
`Server
`Computer
`System
`
`Server
`Computer
`System
`
`122
`
`122
`
`Fig. 1
`(Prior Art)
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 3
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 2 of 16
`
`US 6,851,115 Bl
`
`230
`
`Orb
`
`Distributed C~mputing Environment
`
`Fig. 2
`(Prior Art)
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 4
`
`

`

`U.S. Patent
`US. Patent
`
`Feb. 1, 2005
`Feb.1,2005
`
`Sheet 3 of 16
`Sheet 3 of 16
`
`US 6,851,115 Bl
`US 6,851,115 B1
`
`Facilitator
`
`Agent
`
`Fig. 3
`Fig. 3
`
`Petitioner Microsoft Corporation - EX. 1001, p. 5
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 5
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 4 of 16
`
`US 6,851,115 Bl
`
`400
`
`402
`
`Facilitator Agent ~ 416
`Registry
`
`------------ - ---------- __ t ___________ t/418
`Interagent Communication Language (_ICL)
`--
`----
`---------
`
`<.
`... )
`
`,,,.--
`(...,_
`
`--
`
`User
`Interface
`Agent
`
`NL to ICL
`Agent
`
`Application
`Agent
`
`Meta
`Agent
`
`408
`
`414
`
`Modality Agents
`
`410
`
`404
`
`406
`
`API
`Application
`
`412
`
`Fig. 4
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 6
`
`

`

`El7I.I_|_'_I_I_l.l_l_'.IWI_I_I_|?'1I,I_IHI_I_I,I_I_'_l_l_|_lfil_'_l_Hmm>mIUEE
`wEon.u:50_.>u_._:uwm=ScamoELou.moztm=mEcog;
`
`
`
`
`EBUEEUEEmm<:mao
`
`U.S. Patent
`US. Patent
`
`Feb.1,2005
`Feb. 1, 2005
`
`Sheet 5 0f 16
`Sheet 5 of 16
`
`US 6,851,115 Bl
`US 6,851,115 B1
`
`-I I I-
`
`Q)
`
`E
`
`I:
`
`==
`=
`I::
`
`QJ
`L. ::,
`~
`QJ
`.,I
`.c
`u
`L-
`<(
`.µ
`C:
`QJ
`en
`<(
`C
`(lJ
`C.
`0
`
`
`
`0
`0
`
`_.mcocam_mu>2
`
`Petitioner Microsoft Corporation - EX. 1001, p. 7
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 7
`
`

`

`i,-
`~
`(1)
`i,(cid:173)
`1-
`i,-
`(It
`00
`O'I
`rJ'J.
`e
`
`'"""' O'I
`0 ....,
`~ ....
`'JJ. =(cid:173)~
`
`O'I
`
`Ul
`0
`0
`N
`!'"'
`?'
`~
`"'!"j
`
`~ = ......
`
`~ ......
`~
`r:JJ. .
`d .
`
`Telephone
`
`Agent
`
`Agent
`Fax
`
`Agent
`Prilter
`
`Agent
`Speech
`Text To 454
`
`[j]
`
`Preferences
`
`User
`
`~1448
`
`Fig. 6
`
`Notify Agent ~
`~446
`
`Agent
`Calender
`-432
`
`~
`
`426
`
`Parser Agent
`
`Nahrallang.Jage
`~-ill>
`,,~(u
`
`~ •
`Recogrition m
`Agents --.
`
`·1))))
`
`---~· • 408 Agent
`
`Speech
`~JI
`
`}
`
`~ titerface
`ci)/ · Oser
`
`Agent
`Voicernail
`
`420
`
`Database
`
`Agent
`
`~
`
`Agent
`Web
`
`442
`
`:z..1
`Mal Agent
`Becironic
`
`1
`
`I~
`
`\\
`Speaker D
`
`Agent
`
`450
`
`402
`
`FACILITATOR AGENT
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 8
`
`

`

`i,-
`~
`(1)
`i,(cid:173)
`1-
`i,-
`(It
`00
`O'I
`rJ'J.
`e
`
`'"""' O'I
`0 ....,
`-..J
`~ ....
`'JJ. =(cid:173)~
`
`Ul
`0
`0
`N
`!'"'
`?'
`~
`"'!"j
`
`~ = ......
`
`~ ......
`~
`r:JJ. .
`d .
`
`Fig. 7
`
`~
`
`720
`
`Database
`Persistent
`Global
`
`716
`(
`
`714
`(
`
`712
`(
`
`710
`(
`
`708
`(
`
`706
`(
`
`704
`(
`
`Language. etc.
`(Machine Type
`Characteristics
`
`Process
`
`Declarations
`
`Task
`
`Declarations Declarations Declarations
`Capability
`
`Trigger
`
`Data
`
`Agent Registry
`
`/102
`
`Address
`Unique
`
`SymboJic
`
`Name
`
`70
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 9
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 8 of 16
`
`US 6,851,115 Bl
`
`800
`
`802
`
`804
`
`806
`
`808
`
`810
`
`Installer Invokes
`New Client Agent
`
`System Instantiates
`New Client Agent
`
`Facilitator And New
`Client Agent Establish
`Communications Link
`
`Client Agent Transmits
`Profile To Facilitator
`
`Facilitator Registers
`Client Agent
`
`Fig. 8
`
`Cone
`
`812
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 10
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 9 of 16
`
`US 6,851,115 Bl
`
`Start
`
`900
`
`Determine A Goal
`
`902
`
`Construct
`Goal Into
`ICL
`
`Transmit Goal
`To Parent
`Facilitator
`
`Receive
`Results
`
`904
`
`906
`
`908
`
`Done
`
`910
`
`Fig. 9
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 11
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 10 of 16
`
`US 6,851,115 Bl
`
`Start
`
`1000
`
`Receive Request
`For Service
`
`Parse Request
`For Request
`
`1002
`
`1004
`
`No
`
`1006
`
`Yes
`
`Perform
`Service
`
`Return Results
`And/Or Status
`Report
`
`1010
`
`1012
`
`Done
`
`1014
`
`Fig. 10
`
`Return
`Status
`Report
`
`1008
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 12
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 11 of 16
`
`US 6,851,115 Bl
`
`Start
`
`noo
`
`Receive Goal RCGuest
`
`Parse And Interpret
`Goal Request
`
`Construct Goal
`Satisfaction Plan
`
`Determine Required Sub-Ooals
`
`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
`
`Done
`
`1120
`
`Fig. 11
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 13
`
`

`

`i,-
`~
`(It
`i,-
`1-
`i,-
`(It
`
`00
`O'I
`rJ'J.
`e
`
`'"""' O'I
`0 ....,
`'"""' N
`~ ....
`'JJ. =-~
`
`Ul
`0
`0
`N
`!'"'
`?'
`~
`"'!"j
`
`~ = ......
`
`~ ......
`~
`r:JJ. .
`d .
`
`Agent
`Prilter
`
`~
`
`!1
`L
`
`Agent
`Speech
`Text To 454
`
`I
`
`Telephone
`
`Agent
`
`Agent
`Fax
`
`Database
`
`Agent
`
`~
`
`Preferences
`
`User
`
`Fig. 12
`
`450
`
`402
`
`FACILITATOR AGENT
`
`I~ 0
`
`Speaker D
`
`Aaent
`
`Recogition
`
`408 Agent
`
`Speech
`"oU ur
`
`JJ
`
`~
`~ • Natlral Language
`
`Parser Agent
`
`~)))
`
`426
`
`Agent
`Volcemal
`
`420
`
`Interface
`
`Agents -
`
`User
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 14
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 13 of 16
`
`US 6,851,115 Bl
`
`X
`
`(cid:141)
`
`r--,
`
`Cr
`[]
`~
`(cid:127) N ..... [Q]
`
`/
`
`C
`ro
`l/}
`
`(cid:141)
`0
`u
`Ill
`·g >-
`IU n:,
`it'°
`
`•
`
`<( u
`o' ~ u
`VI ·o
`~ C
`~
`u.. [m],
`~[i] m
`@] [g]
`[D
`~
`01 Cr
`[E
`~
`~
`0. § ~
`:r: 61
`~
`0 [i]
`3: BB
`[Q]
`C
`,--,
`0 ~
`,.......,
`:p
`N
`.....
`....
`ro
`N
`~
`0 [!] <i.
`L.
`<(
`u
`.0
`u
`ro
`~
`0 ~ 0 [§]
`u
`0
`Ill u
`u
`·o
`C ~ ·a
`VI
`C
`~
`ltl
`L. B
`u.. ~ LL
`:!=
`l/} ~ l/}
`-0
`w
`Q)
`[Q) u::
`
`Q)
`
`~
`"'O
`.£:
`
`0
`
`<(
`
`C
`l'O
`........
`
`C
`ro
`'-
`
`C
`ro
`,..._.
`
`('()
`~
`
`bb
`~
`
`•...-4
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 15
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 14 of 16
`
`US 6,851,115 Bl
`
`Facilitator
`Agent 2
`
`1410
`
`Fig. 14
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 16
`
`

`

`U.S. Patent
`
`Feb.1,2005
`
`Sheet 15 of 16
`
`US 6,851,115 Bl
`
`1500
`
`/ 1502
`Facilitator
`
`I
`
`I
`
`I
`I
`
`I
`
`I
`
`I
`
`I
`
`I
`
`, ,
`
`I
`I
`
`I
`I
`I
`
`I
`
`I
`
`/
`
`1508
`
`I ,
`
`I
`I
`
`1504
`
`Facilitator
`
`1510
`
`1516
`
`1514
`
`Fig. 15
`
`' ' ' ' ' ' ' ·\
`' ' ' ' '
`
`1506
`
`\
`
`Facilitator
`
`'
`
`[]
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 17
`
`

`

`i,-
`~
`(1)
`i,(cid:173)
`1-
`i,-
`(It
`00
`O'I
`rJ'J.
`e
`
`'"""' O'I
`0 ....,
`'"""' O'I
`~ ....
`'JJ. =(cid:173)~
`
`Ul
`0
`0
`N
`!'"'
`?'
`~
`"'!"j
`
`~ = ......
`
`~ ......
`~
`r:JJ. .
`d .
`
`Figure 16
`
`1614
`
`1618
`
`1612
`
`Agent IE
`
`1616
`
`Replicated
`
`161
`
`Planner
`
`Registry &
`
`1604
`
`1
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 18
`
`

`

`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,
`45 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
`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
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 19
`
`

`

`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 (CORBA'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 envi(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 flat 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
`
`Petitioner Microsoft Corporation - Ex. 1001, p. 20
`
`

`

`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
`
`25
`
`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
`
`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