Tutorial

Building and UsingPractical Agent Applications: 

Building and Using Practical Agent Applications SRI International David Martin Adam Cheyer PAAM ’98 Tutorial

Contents: 

Contents Context: Agents & Distributed Computing Challenges & Opportunities Inside the Open Agent Architecture Example Systems & Useful Techniques Concluding Remarks

Slide3: 

Context: Agents & Distributed Computing Areas of Agent Research Evolving Paradigms for Distributed Systems SRI’s Open Agent Architecture Challenges & Opportunities Inside the Open Agent Architecture Example Systems & Useful Techniques Concluding Remarks

What Is an Agent?: 

What Is an Agent? Mobile Agents Programs that move among computer hosts Autonomous Agents Based on planning technologies Learning Agents User preferences, collaborative filtering,... Animated Interface Agents Avatars, chatbots, ... Simulation-based Entities Data/Info finding, filtering and merging Cooperative Agents Cooperation among distributed heterogeneous programmatic components Examples Voyager, Aglets, Odyssey Robots, Softbots, BDI Microsoft Agent, Julia ModSAF, RoboCup OAA, KQML, FIPA FireFly, MIT Media Lab SIMS, InfoSleuth, IR

Approaches to Building Applications: 

Approaches to Building Applications Monolithic Applications Object-Oriented Applications Distributed Object Applications OAA Applications Dynamic addition Objective Suitable for Internet environment Virtual community of dynamic services Adaptable to changing, evolving network resources Flexible interactions among components

Approaches to Distributed Computing: 

Approaches to Distributed Computing Mobile Objects Blackboard Architectures Agent Communication Languages (ACL) Publish & Subscribe Brokers

Mobile Objects (Agents): 

Mobile Objects (Agents) Objects move under their own power (e.g., Voyager, Aglets) Advantages Network bandwidth for certain classes of problems Parallelism - many objects can be spawned Disadvantages Programmatically specify where to go and what to do, through a known interface Little automated support for inter-object cooperation Programming language specific (non-heterogeneous)

Blackboard Architectures: 

Blackboard Architectures Knowledge Sources read and write tuples from a common information space (e.g. LINDA, FLiPSiDE) Advantages Eliminates explicitly programmed interactions among participants Disadvantages KS cannot coordinate interactions Polling tuple(abc,1,2,3)

Publish & Subscribe Brokers: 

Publish & Subscribe Brokers Clients register interest, broker routes/filters msgs Examples: Talarian SmartSockets, Active Software’s ActiveWeb, ACL Brokers Advantages Destination process(es) not explicitly encoded No polling Disadvantages Simple filtering, unitary messages Broker

Agent Communication Languages: 

Agent Communication Languages Communication message types based on speech acts (e.g., ask, tell, deny) + conversational policies Examples: FIPA ACL, KQML Advantages Rich interaction model, peer-to-peer based Standardized message types, content-agnostic Disadvantages Conformance to specs not universal Explicitly coded interactions among participants ANS, Service Broker Ask Reply

Comparison of Distributed Approaches: 

Comparison of Distributed Approaches

Overview of the OAA: 

Overview of the OAA OAA: A framework for integrating a community of software agents in a distributed environment Facilitates flexible, adaptable interactions among distributed components through delegation of tasks, data requests & triggers Enables natural, mobile, multimodal user interfaces to distributed services Definition What, not how or who Distributed Computing Through Delegation: User Interface

OAA Architecture: 

OAA Architecture Facilitator Agent Modality Agents Registry Interagent Communication Language

Automated Office Application: 

Automated Office Application Main Points Mobile access to distributed services Legacy applications interacting with AI technologies Flexible interactions among components High-level tasking of agents through NL and speech Delegated Triggers

OAA Characteristics: 

OAA Characteristics Open: Extensible: Distributed: Parallel: Mobile: High-level: Multimodal: agents can be created in many languages and interface with existing systems agents can be added or replaced dynamically agents are spread across many computers Parallel execution of subtasks Lightweight interfaces on phone and/or PDA hides software and hardware dependencies handwriting, speech, gestures, and direct manipulation can be combined together

OAA-based Applications: 

OAA-based Applications 1. Automated Office 2. Unified Messaging 3. Multimodal Maps 4. CommandTalk 5. ATIS-Web 6. Spoken Dialog Summarization 7. Agent Development Tools 8. InfoBroker 9. Rental Finder 10. InfoWiz Kiosk 11. Multi-Robot Control 12. MVIEWS Video Tools 13. MARVEL 14. SOLVIT 15. Surgical Training 16. Instant Collaboration 17.Crisis Response 18. WebGrader 19. Speech Translation 20-25+ ...

Slide17: 

Context: Agents & Distributed Computing Challenges & Opportunities Interoperation Coordination & Control Information Management and Sharing Intelligent User Interfaces Inside the Open Agent Architecture Example Systems & Useful Techniques Concluding Remarks

Interoperation: 

Interoperation

Interoperation: 

Interoperation Language, Ontology, Conversational Protocol Imposing the Right Amount of Structure Legacy & “Owned-elsewhere” Applications Multi-platform, Multi-language Wrappers & Surrogates Backwards Compatibility With Older Paradigms Integration with Standards Opportunities Support Greater Flexibility & Dynamism in Structuring Communities & Interactions Provide Economical Means of Coding Interactions Leverage Our Understanding Of Conversations Minimize Platform & Language Barriers

Coordination & Control: 

Coordination & Control No Fully General Solutions Available Families of C & C Strategies Knowledge-Sharing Team Coordination Economic (Market-Driven) Evolutionary Opportunities Flexibility, Synergy Advice and Constraints Temporal Control Sophisticated Facilitation, Reactive Execution

Alternative Agent Control Strategies: 

Alternative Agent Control Strategies Knowledge-Sharing Agents share knowledge about capabilities and requests. Agent brokers dynamically match requests to capabilities. System dynamically adjusts as capabilities are added to and removed from the environment. Team Coordination Agents share knowledge about goals, plans, tasks & subtasks, commitments and performance. Teams cooperative through partially synchronized actions to accomplish individual subtasks and common goals. Market-Driven Economy Self-interested agents pursue personal profit. Behavior is driven by the cost of resources. Agents are controlled by specifying market rules, rewards and penalties. Evolutionary Systems Agents populations evolve over time through “reproduction”, mutation and natural selection. Agents are controlled by specifying selection criteria and reproduction process.

Applicability of Strategies: 

Complexity vs. Number of Agents Applicability of Strategies Coordination and Control Strategies Knowledge-Sharing Team Coordination Market-Driven Economy Evolutionary Systems The strategies differ in the complexity and number of agents for which they are suited to control 101 - 103 105 - 107 Knowledge Sharing Number of agents in system Complexity of individual agents Team Coord. Market Driven Evolutionary System low high

Information Management and Sharing: 

Information Management and Sharing External Data Heterogeneous, Dynamic, Unreliable Sources Operational Data Maintaining Consistent World-views Transactions, Snapshots, Roll-back Sharing Strategies How Much to Share, Cost of Sharing Support for Collaboration Opportunities Tight Integration With Service-providing & Requesting Mechanisms Built-in Support for Handling Dynamism Use Intelligence, Autonomy to Address Reliability

Intelligent User Interfaces: 

Intelligent User Interfaces Make User Requests Comprehensible to System Make System Results Comprehensible to User Help User Understand System Complexity … Multiple Autonomous Actors Dynamic Communities … Or Not Be Required to Opportunities Agent-based Approaches to UI Implementation Integrate Multimodality User As Privileged Member of Agent Community Use of Mixed-initiative Interactions Collaboration

Slide25: 

Context: Agents & Distributed Computing Opportunities & Challenges Inside the Open Agent Architecture Example Systems & Useful Techniques Concluding Remarks

OAA Architecture: 

OAA Architecture Facilitator Agent Modality Agents Registry Interagent Communication Language

Interagent Communication Language: 

Interagent Communication Language Used by Agents to: Declare Capabilities Request Services of Community Respond to Requests from Other Agents Manage and Exchange Information Conversation & Content Layers Advice/Constraints Can Accompany Requests Platform- and Language-Independence

Providing Services: 

Providing Services Declaring Capabilities solvable(Goal, Parameters, Permissions) Examples of Parameters type: {data, procedure} private: Boolean utility: [0 .. 10] solvable(send_message(email, +ToPerson, +Params), [type(procedure), callback(send_mail)], []), solvable(last_message(email, -MessageId), [type(data), single_value(true)], [write(true)])

Requesting Services: 

Requesting Services oaa_Solve(TaskExpr, ParamList) Expressions: logic-based (cf. Prolog) Parameters: provide advice & constraints High-level task types: query, action, inform, ... Low-level: solution_limit(N), time_limit(T), parallel_ok(TF), priority(P), address(Agt), reply(Mode), block(TF), collect(Mode), ... oaa_AddData(DataExpr, ParamList) oaa_AddTrigger(Typ,Cond,Action,Ps) oaa_Solve((manager(‘John Bear’,M), phone_number(M,P)), [query(var(P))]) Task Management Data & Trigger Management Example

Compound Queries: 

Compound Queries Address:Goal::Parameters Address & Parameters Optional Value-returning Parameters Composable Using Standard Prolog Operators Extensions Parallel Disjunction oaa_Solve( (locate(‘Adam Cheyer’, Where)::[strategy(query)], notify(MsgRef, ‘Adam Cheyer’, [at(Where), by(fax)])::[strategy(action)]), [])

Facilitation: 

Facilitation Facilitator

OAA Data Management: 

OAA Data Management Declaring & Utilizing Data Solvables Built-in Support Example Parameters single_value(t_f), unique_values(t_f) bookkeeping(t_f), persistent(t_f) synonym(Synonym, Original) rules_ok(t_f) Maintaining Data Solvables Sharing Data

OAA Triggers: 

OAA Triggers OAA agents can dynamically register interest in any data change, communication event, or real-world occurrence accessible by any agent. oaa_AddTrigger(Type, Cond, Action, Params) comm: on_send, on_receive message time: “in ten minutes”, “every day at 5pm” data: on_change, on_remove, on_add task: “when mail arrives about...” The actions of triggers may be any ICL expression solvable by the community of agents Trigger Types Purpose Actions Adding a Trigger

System-Building Infrastructure: 

System-Building Infrastructure The Event Loop Event Types Built-In Task-Specific Hybrid Libraries Multiple Languages Supported Minimal Structure Imposed on Agents

A Sample Text-to-Speech Agent in C: 

A Sample Text-to-Speech Agent in C #include <libcom_tcp.h> #include <liboaa.h> ICLTerm capabilities = icl_TermFromStr(“[play(tts, Msg)]”); ICLTerm oaa_AppDoEvent(ICLTerm Event, ICLTerm Params) { if (strcmp(icl_Str(Event), “play”) == 0) { return playTTS(icl_ArgumentAsStr(Event, 2)); } else return NULL; } main() { com_Connect(“parent”, connectionInfo); oaa_Register(“parent”, “tts”, capabilities); oaa_MainLoop(True); } Include libraries List capabilities Define capabilities Agent Startup

A Sample Text-to-Speech Agent in Prolog: 

A Sample Text-to-Speech Agent in Prolog :- use_module(com). :- use_module(oaa). capabilities([ solvable(play(tts, Msg), [type(procedure), callback(tts_events)], [])]). tts_events(play(tts, Msg), Params) :- tts_api(Msg). start :- capabilities(C), com_Connect(parent, ConnectionInfo), oaa_Register(parent, tts, C), oaa_MainLoop(true). Include libraries List capabilities Define capabilities Agent Startup

OAA and Scalability: 

OAA and Scalability Facilitator is single point of failure Facilitator is bottleneck for communication Limitations: Solutions? Multi-Facilitator topologies Distribution of planning & execution functions of Facilitator + peer-to-peer communication Registry & Planner Agent E Replicated

Slide38: 

Context: Agent Types & Approaches Challenges & Opportunities Inside the Open Agent Architecture Example Systems & Useful Techniques Agent & Interagent Programming Tips Dynamic Presentation: Unified Messaging Reference Resolution: Multimodal Map Information Management and Collaboration: InfoBroker & Multimodal Map Incremental System Development & Evaluation: Stimulate Looking for the Killer App: Other Tries Concluding Remarks

Agent & Interagent Programming Tips: 

Agent & Interagent Programming Tips Choosing an Agent Interface Information Sharing Strategies Domain-Specific vs. Domain-Independent Agents Adding Speech & NL to Interfaces

Tips: Choosing an Agent Interface: 

Tips: Choosing an Agent Interface Natural-language inspired interfaces Imperative Verb, Direct Object, ParamList, (Result) Parameter lists hold Adjs, Advs & Prepositions as well as extensible programmatic instruction Classes tagged by type inform(phone, ringing, Params) send_message(MsgRef, Params) :- memberchk(by(fax), Params) Succeed once with list vs. Multiple success get(email, message_headers, +Params, -ListOfHeaders) phone_number(Person, PhoneNum)

Tips: 3 Information Sharing Strategies: 

Tips: 3 Information Sharing Strategies Example: Phone Dialer Agent 1. Query When an agent wants to know the status of the phone, it asks the Facilitator who asks the phone agent pa: oaa_Declare(status(phone, S),[]) ?a: oaa_Solve(status(phone, S), [])

Tips: Information Sharing Strategies - Post: 

Tips: Information Sharing Strategies - Post 2. Post (Blackboard) The phone agent writes its status to the Facilitator; agents can query the facilitator for status, and install a trigger which proactively monitors changes to status pa: oaa_AddData(status(phone, busy), []) ia: oaa_Solve(status(phone, S), []), oaa_AddTrigger(data, status(phone,S), notify(Me, phone(S)), [on(change)])

Tips: Information Sharing Strategies - Inform: 

Tips: Information Sharing Strategies - Inform 3. Inform Broadcast time-critical events to interested parties ia: oaa_Declare(msg(phone, Msg), []) pa: oaa_Solve(msg(phone, ringing, []), [inform])

Tips: Domain-Specific vs. Domain Independent Agents: 

Tips: Domain-Specific vs. Domain Independent Agents Move domain-dependent code into separate agent Employ hooks and parameters to allow domain-specific tailoring of functionality Always ask: Domain-specific or domain independent? Phone agent? Office interface? Notify agent? Speech recognition? Natural language? Facilitator?

Tips: Adding Speech & NL: 

Tips: Adding Speech & NL User Interface responsible for: accepting user input, sending requests, displaying results controlling interactions of Speech and NL Complex interpretation processed by external domain agent

Unified Messaging: Problem: 

Unified Messaging: Problem Universal Access: Access to web, email, voicemail, applications (e.g., calendar, database, scheduler) from multiple interfaces (e.g., web browser, desktop, telephone) Delegated triggers to monitor information Message dissemination across various media (e.g., fax, printer, email, phone, pager) Locating destination target Plan route according to user preferences & resources Media translation as necessary Extensible and distributed! Minimize dependencies among component technologies

Unified Messaging: Components: 

Unified Messaging: Components Main Points Mobile, adaptable access to distributed services Integrated Messaging: web, email, voice, fax Flexible interactions among components Distributed reference resolution and media format translation Delegated Triggers

Unified Messaging: Implementation 1/2: 

Unified Messaging: Implementation 1/2 Universal Access Every user interface (including phone) must identify user UI’s coordinate themselves to ensure only one “primary” interface per user, per utterance Message Dissemination Media agents: distributed reference resolution and translation print(Object, Params) ref(it): oaa_Solve(resolve_reference(the, document, Params, NewObj)) id(Pointer): oaa_Solve(resolve_reference_id_as(id(Pointer), postscript, [], PostScript) print TextObject or PostScript

Unified Messaging: Implementation 2/2: 

Unified Messaging: Implementation 2/2 Adaptable Presentation GenNL agent produces simple or structured text-based response for any ICL query Reads distributed NL vocabulary definitions in forming simple responses: Vocabulary: noun(‘telephone number’, phone_number, []) NL -> ICL: “What is Adam Cheyer’s telephone number?” ICL: oaa_Solve(phone_number(‘Adam Cheyer’, X),[query(var(X))]) Reponse: [phone_number(‘Adam Cheyer’, ‘859-4119’)] GenNL: “The telephone number of Adam Cheyer is 859-4119.” Structured response: description(list(EltList, AttrList)) title(Title): Title of list, e.g. ‘Schedule’ elt(Elt): Name of individual element in list, e.g. ‘Appointment’ intro(Intro): Introduction to be played at start of list, e.g., ‘Here is today’s schedule for Adam Cheyer’ max_len(Max): Num < Max Display All, else Display 1st & iterate

Multimodal Maps Application: 

Multimodal Maps Application Main Points Natural interface to distributed (web) data Synergistic combination of handwriting, drawing, speech, direct manipulation Parallel cooperation and competition among many agents Human & Agent collaboration Adaptable displays according to user preferences

Multimodal Interfaces using Parallel Distributed Agents: 

Multimodal Interfaces using Parallel Distributed Agents Competition and cooperation among agents at many levels Pen input: gesture recognizer vs. handwriting recognizer Natural language: multiple NL systems (multilingual, diff. capabilities) Reference Resolution Multiple modalities for resolving ambiguities e.g. arrow + “scroll map” vs. arrow + “photo of this hotel”

Multimodal Reference Resolution: 

Multimodal Reference Resolution Context by object type: “show photo of the hotel” Deictic: “Find distance from here to here”, “this one” Positional context: Write “photo?” on hotel Visual context: “Photo of the [visible] hotel” Database queries: “show photo of the hotel in Menlo Park” Discourse: “No, the other one” User disambiguation through prompting: “Which hotel?”

Information Broker: Requirements: 

Information Broker: Requirements Integrate Internet sources with enterprise sources Heterogeneity handled transparently Structured and “semi-structured” sources Flexible access to unreliable information sources Easily extensible to new domains User and task models used to guide retrievals Infrastructure must provide a basis for tools

Information Broker: Functionality: 

Information Broker: Functionality Mediation Retrieval Strategies User & Task Models

Mediation: 

Mediation Transparent access to heterogeneous sources WWW structured and semi-structured sources SQL sources Knowledge bases Multimedia repositories Dynamic source registration & schema update Query planning across distributed sources Queries in broker or source schema Domain knowledge used to increase query range Built-in normalizations and conversions Incomplete & inconsistent information

Retrieval Strategies: 

Retrieval Strategies Identification of relevant sources Extraction of desired information Imposing structure on semi-structured Web pages Local caching of virtual databases Sensitivity to time constraints Flexible strategies for web vs. cache retrievals Dealing with unreliability and change Cache maintenance Use of alternate sources Tracking and rating of sources

User and Task Modeling: 

User and Task Modeling Representation of salient characteristics of users and tasks Mapping from situation to information request What information is needed and when? User and task models used as constraints Mapping information retrieval to presentation What information does the user want to see? User and task models used as filters User-friendly knowledge acquisition Learning user and task models where feasible

Sample Queries: 

Sample Queries Mediation “Find all hotels (meeting certain constraints) in San Francisco” Use of domain knowledge “Find hotels halfway between S. F. and Portland” User modeling “Apply my preferences” (to the same query) Legacy and Web data source integration “Show just the hotels for which we get a corporate discount” (Accesses WWW sources and employee db) “Find the names and extensions of employees in the AI Center who have written about …” (Accesses Harvest index, Bibtex file and employee db) “Persistent” queries “Notify me of any ad selling a used color inkjet printer”

Information Broker: Architecture: 

Information Broker: Architecture Semi-structured Source (Surrogate) Structured Source (Surrogate) Broker RDB Source (Wrapped) Broker schema Source schemas BQ BR SQ SR

The Broker: 

The Broker Agent Interactions Management

Surrogates: 

Surrogates Cache

Persistent Queries: 

Persistent Queries Broker Q T T T T Transaction Management Surrogate Helper Agent R

Useful Features of the Framework: 

Useful Features of the Framework Tight Integration of Data Capabilities Standardized, Visible Content Language Extension of Logic Programming Paradigm

Collaboration-ready Data Management: 

Collaboration-ready Data Management Store data using OAA Data Management oaa_DbDeclare(icon(Id, X, Y, PictureType), [shareable, callback(icon_change)]) Separate code which changes data from results, using callback feature NOT: { oaa_AddData(icon(hilton, 100, 100, hotel), []) map_Display(icon(hilton, 100, 100, hotel)) } BUT: { oaa_AddData(icon(hilton, 100, 100, hotel), []) } icon_change(add, icon(Id, X, Y, Picture)) :- map_Display(icon(Id, X, Y, Picture)).

Incremental System Development & Evaluation: 

Incremental System Development & Evaluation Collaborative Multimodal Map application adapted for Wizard Of Oz (WOZ) experiment to elicit data about coordinated use of language and gesture

Subject Screen vs. Wizard Screen: 

Subject Screen vs. Wizard Screen

Subject Video: 

Subject Video

Hybrid Wizard Of Oz Experiment: 

Hybrid Wizard Of Oz Experiment Naive user free to write, draw, or speak without constraints imposed by current technology Wizard must respond quickly and accurately by using existing means, including pen and voice Simultaneous evaluation of: Experienced user manipulating real system New user, providing data for future extensions Bootstrap effect: continuous loop from data to theory, to system enhancement Improvements from data analysis quantifiable General-purpose approach

Hybrid WOZ: Implementation: 

Hybrid WOZ: Implementation System logging and playback “for free” using OAA collaboration facilities “Subject mode”: functional interpretation (mostly) turned off Addition of simple Wizard Feedback panel (separate agent) for text-to-speech messages (e.g., “Function not available.”)

Looking for Killer Apps: 

Looking for Killer Apps OAA has been used to implement more than 25 systems and prototypes Not good for every application, but good for: integrating numerous components which need to cooperate, often across language boundaries supporting media translation distributed reference resolution tasking through adaptable or multimodal user interfaces human/agent collaborative systems & incremental dvpt exploring direct manipulation/task delegation tradeoffs

OAA-based Applications: 

OAA-based Applications 1. Automated Office 2. Unified Messaging 3. Multimodal Maps 4. CommandTalk 5. ATIS-Web 6. Spoken Dialog Summarization 7. Agent Development Tools 8. InfoBroker 9. Rental Finder 10. InfoWiz Kiosk 11. Multi-Robot Control 12. MVIEWS Video Tools 13. MARVEL 14. SOLVIT 15. Surgical Training 16. Instant Collaboration 17.Crisis Response 18. WebGrader 19. Speech Translation 20-25+ ...

MVIEWS Application: 

MVIEWS Application Interactive Map Main Points Multimodal annotation of video using speech & pen Automated detection, tracking, and geolocation of moving objects Search and replay of videos indexed by multimodal and auxilliary data Applications: multi-sensor surveillance, Predator UAV, Olympic bombing Interactive Map Video browser with multimedia timeline

MVIEWS Architecture: 

MVIEWS Architecture

InfoWiz Kiosk: 

InfoWiz Kiosk Main Points An information kiosk with an animated wizard who : answers questions, gives tours, and helps navigate the information space OAA integrates SRI’s speech recognition, NL, dialogue, and knowledge representation with Microsoft Agent graphics and Netscape’s webbrowser Soon in SRI ’s lobby

InfoWiz Kiosk Architecture: 

InfoWiz Kiosk Architecture

Multi-Robot Control: 

Multi-Robot Control Concept Design Monitoring Maps, video, status Configurable displays Global or individual views Directed camera & robot control Delegated tasking through speech & gesture Tasking

Agent Development Tools: 

Agent Development Tools Tools are implemented themselves in OAA Guide user through process of creating an agent: Definition of capabilities Documentation management (publication on Web) Code generation of agent template Definition of NL vocabulary Update NL & speech recognition systems Assembly of multiagent projects Runtime tool for launching and monitoring agent communities

Concluding Remarks: 

Concluding Remarks Many Varieties of Agents Agent-based Systems Agent Frameworks Useful Features of Agent Frameworks Important Design Choices Strategies for Interoperation & Coordination Managing and Sharing Data User Interface Functionality Framework