`
`(12) United States Patent
`US 7,036,128 B1
`(10) Patent No.:
`Julia et al.
`(45) Date of Patent:
`fiApr.25,2006
`
`(54)
`
`(75)
`
`(73)
`
`USING A COMMUNITY OF DISTRIBUTED
`ELECTRONIC AGENTS TO SUPPORT A
`HIGHLY MOBILE, AMBIENT COMPUTING
`ENVIRONMENT
`
`Inventors: Luc Julia, Oakland, CA (US); Adam
`Cheyer, Oakland, CA (US)
`
`Assignee: SRI International Oflices, Menlo Park,
`CA (US)
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`
`0 803 826 A2
`
`10/1997
`
`(Continued)
`OTHER PUBLICATIONS
`
`Moran, Douglas et al. Multimodal User Interfaces in the
`Open Agent Architecture. Jan. 1997.*
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 1261 days.
`
`(Continued)
`
`Primary ExamineriLewis A. Bullock, Jr.
`(74) Attorney, Agent, or FirmiPerkins Coie LLP
`
`This patent is subject to a terminal dis-
`claimer.
`
`(57)
`
`ABSTRACT
`
`(21)
`
`Appl. No.: 09/475,092
`
`(22)
`
`Filed:
`
`Aug. 9, 2000
`
`Related US. Application Data
`
`Continuation-in-part of application No. 09/225,198,
`filed on Jan. 5, 1999, now Pat. No. 6,851,115.
`
`Provisional application No. 60/ 124,718, filed on Mar.
`17, 1999, provisional application No. 60/124,719,
`filed on Mar. 17, 1999, provisional application No.
`60/124,720, filed on Mar. 17, 1999.
`
`Int. Cl.
`
`(2006.01)
`G06F 9/54
`US. Cl.
`....................................... 719/317; 709/202
`Field of Classification Search ................ 709/202;
`71 9/3 17
`
`See application file for complete search history.
`
`References Cited
`
`(63)
`
`(60)
`
`(51)
`
`(52)
`(58)
`
`(56)
`
`U.S. PATENT DOCUMENTS
`
`5,197,005 A
`
`3/1993 Shwartz et al.
`
`A highly mobile, ambient computing environment is dis-
`closed for serving a knowledge worker away from the their
`desk. The present invention allows a knowledge worker to
`get increased leverage from personal, networked, and inter-
`active computing devices while in their car, airplane seat, or
`in a conference room with others. An Open Agent Archi-
`tecture is used to incorporate elements such as GPS agents,
`speech recognition, and opportunistic connectivity among
`meeting participants. Communication and cooperation
`between agents are brokered by one or more facilitators,
`which are responsible for matching requests, from users and
`agents, with descriptions of the capabilities of other agents.
`It is not generally required that a user or agent know the
`identities, locations, or number of other agents involved in
`satisfying a request, and relatively minimal effort is involved
`in incorporating new agents and “wrapping” legacy appli-
`cations. Extreme flexibility is achieved through an architec-
`ture organized around the declaration of capabilities by
`service-providing agents,
`the construction of arbitrarily
`complex goals by users and service-requesting agents, and
`the role of facilitators in delegating and coordinating the
`satisfaction of these goals, subject to advice and constraints
`that may accompany them.
`
`(Continued)
`
`45 Claims, 22 Drawing Sheets
`
`
`
`
`
`Modality Agents
`
`Page 1 of 44
`
`GOOGLE EXHIBIT 1001
`
`GOOGLE EXHIBIT 1001
`
`Page 1 of 44
`
`
`
`US 7,036,128 B1
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`Busetta, Paolo et al. “The BDIM Agent Toolkit Design.”
`1997.*
`
`Mayfield, James et al. “Desiderable for Agent Communica-
`tion Languages.” Mar. 27-29, 1995*
`Dowding, John et al., “Gemini: A Natural Language System
`For Spoken-Language Understanding”, SRI International.
`http://www.ai.sri.com/~0aa/inf0wiz.html, InfoWiZ: An Ani-
`mated Voice Interactive Information System, May 8, 2000.
`Dowding, John, “Interleaving Syntax and Semantics in an
`Efficient Bottom-up Parser”, SRI International.
`Moore, Robert et al., “Combining Linguistic and Statistical
`Knowledge Sources in a Natural-Language Processing for
`ATIS”, SRI International.
`Stent, Amanda et al., “The CommandTalk Spoken Dialog
`System”, SRI International.
`Moore, Robert et al., CommandTalk: A Spoken-Language
`Interface for Battlefield Simulationsz, Oct. 23, 1997, SRI
`International.
`
`Dowding, John et al., “Interpreting Language in Context in
`CommandTalk”, Feb. 5, 1999, SRI International.
`Moran, Douglas B. et al., “Intelligent Agent-based User
`Interfaces”, Article Intelligence center, SRI International.
`Martin, David L. et al., “Building Distributes Software
`Systems with the Open Agent Architecture”.
`Julia, Luc. et al., “Cooperative Agents and Recognition
`System (CARS) for Drivers and Passengers”, SRI Interna-
`tional.
`
`Moran, Douglas et al., “Multimodal User Interfaces in the
`Open Agent Architecture”.
`Cheyer, Adam et al., “Multimodal Maps: An Agent-based
`Approach”, SRI International.
`Cutkosky, Mark R. et al., “An Experiment in Integrating
`Concurrent Engineering Systems”.
`Martin, David et al., “Development Tools for the Open
`Agent Architecture”, The Practical Application of Intel-
`leigent Agents and Multi-Agent Technology (PAAM96),
`London, Apr. 1996.
`Cheyer, Adam et al., “The Open Agent Architecturetm”, SRI
`International. AI center.
`
`Dejima, Inc., http://www.dejima.com/.
`Cohen, Philip et al., “An Open Agent Architecture”, AAAI
`Spring Symposium, pp. 1-8, Mar. 1994.
`Martin, David et al., “Information Brokering in an Agent
`Architecture”, Proceeding of the 2nd Int’l Conference 011
`Practical Application of Intelligent Agents & Multi-Agent
`Technology, London, Apr. 1997.
`
`* cited by examiner
`
`........... 701/201
`........... 345/2.1
`
`1/1995 Hedin et al.
`5,386,556 A
`7/1995 Luciw
`5,434,777 A
`5/1996 Kupiec
`5,519,608 A
`3/1997 Luciw
`5,608,624 A
`5,697,844 A * 12/1997 Von Kohorn ................ 463/40
`5,721,938 A
`2/1998 Stuckey
`5,729,659 A
`3/1998 Potter
`5,748,974 A
`5/1998 Johnson
`5,774,859 A
`6/1998 Houser et al.
`5,794,050 A
`8/1998 Dahlgren et al.
`5,802,526 A
`9/1998 Fawcett et al.
`5,805,775 A
`9/1998 Eberman et al.
`5,855,002 A
`12/1998 Armstrong
`5,890,123 A
`3/1999 Brown et al.
`5,948,040 A
`9/1999 DeLorme et al.
`5,959,596 A
`9/1999 McCarten et al.
`5,963,940 A
`10/1999 Liddy et al.
`6,003,072 A
`12/1999 Gerritsen et al.
`6,012,030 A
`1/2000 French-St. George et al.
`6,021,427 A
`2/2000 Spagna et al.
`6,026,375 A *
`2/2000 Hall et al.
`.................... 705/26
`6,026,388 A
`2/2000 Liddy et al.
`6,047,127 A *
`4/2000 McCarten et al.
`6,080,202 A
`6/2000 Strickland et al.
`6,144,989 A
`11/2000 Hodjat et al.
`6,173,279 B1
`1/2001 Levin et al.
`6,192,338 B1
`2/2001 Haszto et al.
`6,219,676 B1*
`4/2001 Reiner ........................ 707/201
`6,226,666 B1
`5/2001 Chang et al.
`6,263,322 B1 *
`7/2001 Kirkevold et al.
`6,338,081 B1
`1/2002 Furusawa et al.
`.......... 701/29
`6,339,736 B1 *
`1/2002 Moskowitz et al.
`6,519,241 B1*
`2/2003 Theimer ..................... 370/338
`.. 701/213
`6,553,310 B1*
`4/2003 Lopke ...........
`
`............ 713/202
`6,594,765 B1 *
`7/2003 Sherman et al.
`6,757,718 B1 *
`6/2004 Halverson et al.
`.......... 709/218
`2001/0013051 A1*
`8/2001 Nakada et al.
`.....
`709/202
`
`2001/0039562 A1* 11/2001 Sato ...........
`709/202
`. 706/46
`2003/0167247 A1*
`9/2003 Masuoka
`FOREIGN PATENT DOCUMENTS
`
`.......... 717/173
`
`.......... 705/400
`
`WC
`
`WO 00/11869
`
`3/2000
`
`OTHER PUBLICATIONS
`
`Foundation for Intelligent Physical Agents (FIPA). “FIPA,
`97 Specification Part 5, Personal Assistant.” Oct. 10, 1997.*
`Khedro, Taha et al. “Concurrent Engineering Through
`Interoperable Software Agents.”*
`Espinoz, Fredrik. “sicsDAIS: Managing User Interaction
`with Multiple Agents.” Oct. 1998*
`Nwana, Hyacinth et al. “Software Agent Technologies”. BT
`Technology Journal. 1998*
`
`Page 2 of 44
`
`Page 2 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 1 0f 22
`
`US 7,036,128 B1
`
`100
`
`Client
`Computer
`System
`
`Client
`Computer
`System
`
`Client
`Computer
`System
`
`System
`
`Server
`Computer
`System
`
`Server
`Computer
`
`Fig. 1
`(Prior Art)
`
`Page 3 of 44
`
`Page 3 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 2 0f 22
`
`US 7,036,128 B1
`
`Interface Specific
`Invocation
`
`
`Transparent
`
`
`Response
`Response
`
`
`
`
`IDL Interface
`IDL Interface
`
`
`
`
`
`
`
`
`
`Client
`
`Object
`
`
`Methods
`
`Data
`
`
`
`
`Server
`Object
`Methods
`
`Data
`
`
`
`Distributed Computing Environment
`
`
`
`Fig. 2
`(Prior Art)
`
`Page 4 of 44
`
`Page 4 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 3 0f 22
`
`US 7,036,128 B1
`
`Facilitator
`
`Agent
`
`Fig. 3
`
`Page 5 of 44
`
`Page 5 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 4 0f 22
`
`US 7,036,128 B1
`
`
`
`User
`
`Interface
`
`Application
`
`Fig. 4
`
`Page 6 of 44
`
`Page 6 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 5 of 22
`
`US 7,036,128 B1
`
`:mno
`E:Bn:yam=Btsumm=wzonmmE‘5"—mm>_tm:mE552,
`
`
`
`
`
`8335593ucmm<
`
`7305375>9
`
`Page 7 of 44
`
`Page 7 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 6 of 22
`
`US 7,036,128 B1
`
`Eom<
`
`mafia.
`
`
`
`\WM1MEaem“
`.vmv0...t8....7150Em:
`
`
`:8QOH59“.
`
`”3%;emi
`
`“3%.aE‘93,
`
`llflm.3%?5%?w5%:m
`cmcon“?a;ii32
`ma«m‘:E3
`
`ammnummmcfik1(\
`
`
`
`HZmO<MOH<EAHU<L
`
`“I!‘mommmgEEWWWMmfi?swag.xomv:a‘
`
`New
`
`Page 8 of 44
`
`Page 8 of 44
`
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 7 of 22
`
`US 7,036,128 B1
`
`.80.omasmcfi
`
`8556820
`
`xmmh
`
`09¢.”Egon—é
`
`3035208
`
`2822389acoufifloua
`
`Emma.3mm5:585
`
`$223232
`
`2625308:3
`
`wok.#2.
`
`RQSO
`
`Eofimsm
`
`3835
`
`»mm magnum—89
`
`$8on
`
`
`
`msflmomEom<
`
`0E.
`
`Page 9 of 44
`
`Page 9 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 8 of 22
`
`US 7,036,128 B1
`
`Start Agent
`Registration
`
`800
`
`
`
`
`
`
`Installer Invokes
`New Client Agent
`
`
`
`802
`
`System Instantiates
`New Client Agent
`
`304
`
`
`
`
`
`
`
`
`Facilitator And New
`Client Agent Establish
`Communications Link
`
`806
`
`Client Agent Transmits
`Profile To Facilitator
`
`
`
`
` Facilitator Registers
` 812
`
`Client Agent
`
`
`
`
`808
`
`810
`
`Fig. 8
`
`Page 10 of 44
`
`Page 10 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 9 0f 22
`
`US 7,036,128 B1
`
`Determine A Goal
`
`Facilitator
`
`Construct
`Goal Into
`ICL
`
`Transmit Goal
`To Parent
`
`902
`
`904
`
`905
`
`908
`
`Receive
`
`Results
`
`Fig. 9
`
`Page 11 of 44
`
`Page 11 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 10 0f 22
`
`US 7,036,128 B1
`
`1002
`
`Receive Request
`For Service
`
`Parse Request For Request
`
`1004
`
`N0
`
`Service
`Available?
`
`Yes
`
`1006
`
`1010
`
`Perform
`Service
`
`‘
`
`Report
`
`Return Results
`And/Or Status
`
`1012
`
`Fig. 10
`
`1008
`
`Page 12 of 44
`
`Page 12 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 11 of 22
`
`US 7,036,128 B1
`
`
`
`
`
`1106
`
`
`
`1116
`
`
`
`Select Agents Suitable For
`Performing Required Sub-Goals
`
`1120
`
`Fig. 11
`
`Page 13 of 44
`
`Receive Goal Request
`
`Parse And Interpret
`Goal Request
`
`Construct Goal
`Satisfaction Plan
`
`Determine Required Sub-Goals
`
`Transmit Requests To
`Selected Agents
`
`Original Goal
`Completed?
`
`Yes
`
`1102
`
`1104
`
`1108
`
`1110
`
`1112
`
`1114
`
`1118
`
`Page 13 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 12 0f 22
`
`US 7,036,128 B1
`
`
`
`EEE
`
`\HIH1
`“52E8aWK
`vmvohaxe.42.50
`
`Em?
`
`
`
`commaw.59.
`
`mmocmuwwwgn—
`
`ama
`
`
`
`DHIHIHEm?62mm
`
`a?.lmmmagflEamz
`
`
`rm.5thmCasothoomoxI£53“I_ENV?‘Qaa4.00mg“:—mhg:
`Emm<Em?gm;Ewm<”as.Q5%on
`
`
`van.83st
`
`
`
`\Ew.<
`
`MOH<HEHU<m New
`
`rap/Ema»
`
`Page 14 of 44
`
`Page 14 of 44
`
`
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 13 0f 22
`
`US 7,036,128 B1
`
`‘
`
`,‘za‘qr‘firxo;NA‘.
`ii”
`
`.9-cu
`
`I 3O
`
`1::
`
`‘.
`
`E I
`
`:OD(
`
`US—
`o
`.0
`.59
`
`‘
`
`BU c
`
`.9
`
`5<
`
`(
`.4:
`'o
`IJJ
`
`
`
`[SanFrancisco,CA:12]
`
`2'
`
`u':E
`
`Page 15 of 44
`
`
`
`—.
`r
`\.\
`W4 («-2.1
`\K\E§§~$flmg v
`
`..
`
`-
`
`Page 15 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 14 0f 22
`
`US 7,036,128 B1
`
`Facilitator
`
`Facilitator
`Agent 1
`
`Agent 2
`
`Fig. 14
`
`Page 16 of 44
`
`Page 16 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 15 0f 22
`
`US 7,036,128 B1
`
`
`
`Page 17 of 44
`
`Page 17 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 16 0f 22
`
`US 7,036,128 B1
`
`w HP
`
`EWE
`
`Hmbumflwom
`
`“magma
`
`Page 18 of 44
`
`Page 18 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 17 0f 22
`
`US 7,036,128 B1
`
`1 702
`
`'
`
`West - 05 miles
`
`South — 21 miles
`
`West - 15 miles
`
`1704
`
` Navigation 1 Sound | Office I Games] Car
`
`
`
`
`
`
`
`
`CD TRK
`TIME
`[:3
`53 W llllllllll *‘—
`
`EB
`
`
`
`
`
`
`
`FIG. 18
`
`_---llllnlu um
`main—Immune:
`
`Stopped
`
`Applet starled.
`
`Page 19 of 44
`
`Page 19 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 18 0f 22
`
`US 7,036,128 B1
`
`
`
`
`QIE
`
`2008
`
`2002
`
`2004
`
`2006
`
`Page 20 of 44
`
`Page 20 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 19 0f 22
`
`US 7,036,128 B1
`
`Stopped
`
`~=
`
`FIG. 21
`
`
`
`Speech output:
`
`
`Language:
`0 Deutch @-
`
`
`
`© English
`
`0 Female
`
`
`
`
`0 Espafiol
`
`
`
`IO Frangais V0|ce Mall Config
`
`I Email Account Config I
`
`
`IReturnEIIII|
`
`
`
`
`Stopped
`CD2-Trk3
`SKIP
`
`l::::l
`
`Applet started.
`
`Quit
`
`I
`
`Page 21 of 44
`
`Page 21 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 20 0f 22
`
`US 7,036,128 B1
`
`FIG. 23
`
`Page 22 of 44
`
`Page 22 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 21 0f 22
`
`US 7,036,128 B1
`
`Control Agent & Application Core
`
`*x‘lnteraction Model
`
`[Object]* [VariableF/f/
`
`“
`
`2406
`
`Modalities
`
`
`Page 23 of 44
`
`Page 23 of 44
`
`
`
`U.S. Patent
`
`Apr. 25, 2006
`
`Sheet 22 0f 22
`
`US 7,036,128 B1
`
`
`
`Page 24 of 44
`
`Page 24 of 44
`
`
`
`US 7,036,128 B1
`
`1
`USING A COMMUNITY OF DISTRIBUTED
`ELECTRONIC AGENTS TO SUPPORT A
`
`HIGHLY MOBILE, AMBIENT COMPUTING
`ENVIRONMENT
`
`BACKGROUND OF THE INVENTION
`
`This is a Continuation In Part of US. patent application
`Ser. No. 09/225,198, filed Jan. 5, 1999, now US. Pat. No.
`6,851,115 Provisional US. Patent Application No. 60/124,
`718, filed Mar. 17, 1999, Provisional US. Patent Application
`No. 60/124,720, filed Mar. 17, 1999, and Provisional US.
`Patent Application No. 60/ 124,719, filed Mar. 17, 1999,
`from which applications priority is claimed and these appli-
`cations are incorporated herein by reference.
`
`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 to
`incorporate elements such as GPS or positioning agents and
`speech recognition into a highly mobile computing environ-
`ment.
`
`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-
`worked computing model, rapidly rising expectations for
`smarter, longer-lived, more autonomous software applica-
`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
`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 resources to other computers and
`are known as server computers (servers). The servers 122
`can vary greatly in the resources they possess, access they
`provide and services made available to other computers
`across a network. Servers may service other servers as well
`as clients.
`
`is a computing system based upon this
`The Internet
`network computing model. The Internet is continually grow-
`ing, 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 docu-
`ments, and audio and video streams. With the popularization
`of programming languages such as JAVA, data transported
`between local and remote machines may also include pro-
`grams that can be downloaded and executed on the local
`machine. There is an ever increasing reliance on networked
`computing, necessitating software design approaches that
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`
`allow for flexible composition of distributed processing
`elements in a dynamically changing and relatively unstable
`environment.
`
`In an increasing variety of domains, application designers
`and users are coming to expect the deployment of smarter,
`longer-lived, more autonomous, software applications. Push
`technology, persistent monitoring of information sources,
`and the maintenance of user models, allowing for person-
`alized responses and sharing of preferences, are examples of
`the simplest manifestations of this trend. Commercial enter-
`prises
`are
`introducing
`significantly more
`advanced
`approaches, in many cases employing recent research results
`from artificial intelligence, data mining, machine learning,
`and other fields.
`
`the increasing complexity of
`More than ever before,
`systems,
`the development 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 sys-
`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.
`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
`approaches. Fortunately,
`input modalities now becoming
`widely available, such as speech recognition, pen-based
`handwriting/gesture recognition, 3D motion recognition,
`and the ability to manage the presentation of systems’
`responses by using multiple media provide an opportunity to
`fashion a style of human-computer interaction that draws
`much more heavily on our experience with human-human
`interactions.
`
`PRIOR RELATED ART
`
`Existing approaches and technologies for distributed
`computing include 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 polymorphism. Encapsula-
`tion encourages the creation of library interfaces that mini-
`mize dependencies on underlying algorithms or data struc-
`tures. Changes to programming internals can be made at a
`later date with requiring modifications to the code that uses
`the library. Inheritance permits the extension and modifica-
`tion of a library ofroutines 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
`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
`directed.
`
`With reference to FIG. 2, a distributed object technology
`based around an Object Request Broker will now be
`described. Whereas “standard” object-oriented program-
`ming (OOP) languages can be used to build monolithic
`
`Page 25 of 44
`
`Page 25 of 44
`
`
`
`US 7,036,128 B1
`
`3
`programs out of many object building blocks, distributed
`object technologies (DOOP) allow the creation of programs
`whose components may be spread across multiple machines.
`As shown in FIG. 2, an object system 200 includes client
`objects 210 and server objects 220. To implement a client-
`server relationship between objects, the distributed object
`system 200 uses a registry mechanism (CORBA’s registry is
`called an Object Request Broker, or ORB) 230 to store the
`interface descriptions of available objects. Through the
`services of the ORB 230, a client can transparently invoke
`a method on a remote server object. The ORB 230 is then
`responsible for finding the object 220 that can implement the
`request, passing it the parameters, invoking its method, and
`returning the results. In the most sophisticated systems, the
`client 210 does not have to be aware of where the object is
`located, its programming language, its operating system, or
`any other system aspects that are not part of the server
`object’s interface.
`Although distributed objects offer a powerful paradigm
`for creating networked applications, certain aspects of the
`approach are not perfectly tailored to the constantly chang-
`ing environment of the Internet. A major restriction of the
`DOOP approach is that the interactions among objects are
`fixed through explicitly coded instructions by the applica-
`tion developer. It is often difficult to reuse an object in a new
`application without bringing along all its inherent depen-
`dencies on other objects (embedded interface definitions and
`explicit method calls). Another restriction of the DOOP
`approach is the result of its reliance on a remote procedure
`call (RPC) style of communication. Although easy to debug,
`this single thread of execution model does not facilitate
`programming to exploit the potential for parallel computa-
`tion that one would expect in a distributed environment. In
`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
`on a different machine) under their own programmatic
`control, where they can then interact with the local envi-
`ronment. For certain types of problems, the mobile object
`paradigm offers advantages over more traditional distributed
`object approaches. These advantages include network band-
`width and parallelism. Network bandwidth advantages exist
`for some database queries or electronic commerce applica-
`tions, 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 advantages
`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
`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
`how to interact with the target environment. There is gen-
`erally little coordination support to encourage interactions
`among multiple (mobile) participants. Agents must be writ-
`ten in the programming language supported by the execution
`environment, whereas many other distributed technologies
`support heterogeneous communities of components, written
`in diverse programming languages.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Blackboard Architectures
`
`4
`
`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-
`munity of distributed processes. A blackboard architecture
`provides one solution to eliminating the tightly bound inter-
`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-
`uted computing by casting it as a problem of modeling
`communication and cooperation among autonomous enti-
`ties, or agents. Effective communication among independent
`agents requires four components: (1) a transport mechanism
`carrying messages in an asynchronous fashion, (2) an inter-
`action protocol defining various types of communication
`interchange and their social implications (for instance, a
`response is expected of a question), (3) a content language
`permitting the expression and interpretation of utterances,
`and (4) an agreed-upon set of shared vocabulary and mean-
`ing for concepts (often called an ontology). Such mecha-
`nisms 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-
`ized exchange approach.
`Agent-based systems have shown much promise for flex-
`ible,
`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
`ArchitectureTM (“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-
`ity was not adequately addressed in this prior work.
`SUMMARY OF INVENTION
`
`The present invention provides a highly mobile, ambient
`computing environment for serving a knowledge worker
`away from the their desk. The present invention allows a
`knowledge worker to obtain increased leverage from per-
`sonal, networked, and interactive computing devices while
`on the move in their car, airplane seat, or in a conference
`room with other local or remote participants. An Open Agent
`Architecture is used to incorporate elements such as GPS
`and positioning agents or speech recognition.
`
`Page 26 of 44
`
`Page 26 of 44
`
`
`
`US 7,036,128 B1
`
`5
`A first embodiment of the present invention discloses
`utilizing the Open Agent Architecture to provide a human-
`machine interface for a car environment. Utilizing speech,
`2D and 3D gesture, and natural language recognition and
`understanding, the interface allows the driver to interact with
`the navigation system, control electronic devices, and com-
`municate with the rest of the world. Passengers are also able
`to interact with the system allowing the passengers to use the
`system to watch TV or play games.
`A second embodiment of the present invention discloses
`utilizing the Open Agent Architecture to provide opportu-
`nistic connectivity among meeting participants. Meeting
`participants are connected through the Internet or other
`electronic connection to each other an a shared display
`space. Participants are allowed to share their ideas with
`others using their personal connection and the shared display
`space.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Prior Art FIG. 1 depicts a networked computing model;
`Prior Art FIG. 2 depicts a distributed object technology
`based around an Object Resource Broker;
`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 anAutomated 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-
`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 ArchitectureTM based
`system of agents implementing a unified messaging appli-
`cation in accordance with a preferred embodiment of the
`present invention;
`FIG. 13 depicts a map oriented graphical user interface
`display as might be displayed by a multi-modal map appli-
`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
`with a preferred embodiment of the present invention;
`FIG. 15 depicts a multiple facilitator agent system sup-
`porting at least a limited form of a hierarchy of facilitators
`in accordance with a preferred embodiment of the present
`invention;
`FIG. 16 depicts a replicated facilitator architecture in
`accordance with one embodiment of the present invention;
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`6
`FIG. 17 is an illustration showing a navigation panel in
`accordance with one embodiment of the present invention;
`FIG. 18 is an illustration showing a sound system panel in
`accordance with one embodiment of the present invention;
`FIG. 19 is an illustration showing a communication center
`in accordance with one embodiment of the present inven-
`tion;
`FIG. 20 is an illustration showing a recreation center in
`accordance with one embodiment of the present invention;
`FIG. 21 is an illustration showing a technical information
`center in accordance with one embodiment of the present
`invention;
`in
`FIG. 22 is an illustration showing a setup panel
`accordance with one embodiment of the present invention;
`FIG. 23 is an illustration showing some gestures that can
`be recognized using algorithms in accordance with one
`embodiment of the present invention;
`FIG. 24 is an illustration showing a VO*V* model in
`accordance with one embodiment of the present invention;
`and
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`FIG. 3 illustrates a distributed agent system 300 in accor-
`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-
`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-
`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
`modified in a variety of ways consistent with the present
`invention. For example, the agent system 300 can be dis-
`tributed across a computer network such as that illustrated in
`FIG. 1. The facilitator agent 310 may itself have its func-
`tionality distributed across several different computing plat-
`forms. The agents 320 may engage in interagent communi-
`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-
`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
`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-
`sible for coordinating agent communications and coopera-
`tive problem-solving. The facilitator 402 may also