Slide1: Agents and Multiagents in the Internet and Intranets Michael N. Huhns Munindar P. Singh huhns@sc.edu singh@ncsu.edu http://www.ece.sc.edu/faculty/Huhns/ http://www.csc.ncsu.edu/faculty/mpsingh/


Kinds of Networks: Kinds of Networks Internet Intranet: network restricted within an enterprise Extranet: private network restricted to selected enterprises Virtual Private Network (VPN): a way to realize an intranet or extranet over the Internet.


Open Environments: Characteristics: Open Environments: Characteristics Cross enterprise boundaries Comprise autonomous resources that Involve loosely structured addition and removal Range from weak to subtle consistency requirements Involve updates only under local control Frequently involve nonstandard data Have intricate interdependencies


Open Environments:Technical Challenges: Open Environments: Technical Challenges Coping with scale Respecting autonomy Accommodating heterogeneity Maintaining coordination Getting work done Acquiring, managing, advertising, finding, fusing, and using information over uncontrollable environments


Tremendous Interest in Agent Technology: Tremendous Interest in Agent Technology Evidence: 400 people at Autonomous Agents 98 550 people at Agents World in Paris Why? Vast information resources now accessible Ubiquitous processors New interface technology Problems in producing software


What is an Agent?: What is an Agent? The term agent in computing covers a wide range of behavior and functionality. We shall review this range in a later section In general, an agent is an active computational entity with a persistent identity that can perceive, reason about, and initiate activities in its environment that can communicate (with other agents) It is the last feature that makes agents a worthwhile metaphor in computing


What is CIS?: What is CIS? CIS is concerned with how decentralized information system components, consisting of resources, applications, and human-computer interfaces, should coordinate their activities to achieve their goals. When pursuing common or overlapping goals, they should act cooperatively so as to accomplish more as a group than individually; when pursuing conflicting goals, they should compete intelligently


Properties of CIS: Properties of CIS Decentralization Complex components, best described at the knowledge level Complex interactions Adaptive behavior Coordination


Heritage of CIS: Economics Heritage of CIS Cognitive Science Linguistics Databases Sociology Psychology Systems Theory Distributed Computing Cooperative Information Systems Most work


Dimensions of Abstraction/1: Dimensions of Abstraction/1 Information resources are associated with abstractions over different dimensions. These may be thought of as constraints that must be discovered and represented. Data domain specifications value ranges, e.g., Price >+= 0 allow/disallow “maybe” values


Dimensions of Abstraction/2: Dimensions of Abstraction/2 Structure schemas and views, e.g., securities are stocks specializations and generalizations of domain concepts, e.g., stocks are a kind of liquid asset value maps, e.g., S&P A+ rating corresponds to Moody’s A rating semantic data properties, sufficient to characterize the value maps, e.g., prices on the Madrid Exchange are daily averages rather than closing prices cardinality constraints integrity constraints, e.g., each stock must have a unique SEC identifier


Dimensions of Abstraction/3: Dimensions of Abstraction/3 Process procedures, i.e., how to process information, e.g., how to decide what stock to recommend preferences for accesses and updates in case of data replication (based on recency or accuracy of data) preferences to capture view update semantics contingency strategies, e.g., whether to ignore, redo, or compensate contingency procedures, i.e., how to compensate transactions flow, e.g., where to forward requests or results temporal constraints, e.g., must report tax data every quarter


Dimensions of Abstraction/4: Dimensions of Abstraction/4 Policy security, i.e., who has rights to access or update what information? (e.g., customers can access all of their accounts, except blind trusts) authentication, i.e., a sufficient test to establish identity (e.g., passwords, retinal scans, or smart cards) bookkeeping (e.g., logging all accesses)


Slide14: Characteristics of CIS Applications Inappropriate for conventional distributed processing: local data may be incomplete or inaccurate local problem solving is prone to error the nodes are complex enough to be agents Inappropriate for conventional AI: local autonomy is critical strong semantic constraints exist among agents Complexity Number of agents


Examples of CIS Applications: Examples of CIS Applications Semantic integration of heterogeneous resources Tools to capture requirements Systems to execute those requirements Information access over loosely-coupled systems, e.g., the Internet Most effort in interoperability of existing or separately developed applications; hardly any effort in new applications per se Schema integration Integration of business procedures Legacy applications abound


CIS Advantages over DC: CIS Advantages over DC CIS is a subclass of DC with the following features: High-level messages lead to lower communication costs easy reimplementability more concurrency Autonomy at the knowledge level leads to lower synchronization costs Intelligence embedded at each site leads to increased robustness


Benefits of CIS: Benefits of CIS Due to Distributed Computing Modularity: many problems are inherently decentralized; large problems are easier if they are decomposed and distributed Speed Reliability Due to AI Maintaining systems becomes harder as they scale up sometimes you want to mix and match parts--easy, if they were designed to cooperate sometimes you want to extend capabilities: easier if you can just add more players to a team Knowledge acquisition: use many narrow experts Reusability Ease of requirements acquisition Platform independence


When Is CIS Appropriate?: When Is CIS Appropriate? When information is distributed, as in office automation When metadata is heterogeneous, as in schema integration When autonomous applications are to be integrated, as in legacy systems When data sources are distributed, as in traffic management When expertise is distributed, as in healthcare systems When rewards are distributed, as in automated markets When diverse interests must be represented, as in electronic commerce


When Is CIS Appropriate?: When Is CIS Appropriate? When decisions are distributed, as in manufacturing control When independently developed knowledge bases must be interconnected When resources and actions are distributed


CIS Application:Office Workflow: CIS Application: Office Workflow The claims department of an insurance company processes claims by routing them electronically among appropriate clerical workers. Unfortunately, the system cannot handle exceptions to the normal workflow. Expert systems assisting each clerical worker could aid in this, but they would be more effective if they could communicate their intentions to each other [exception conditions]


CIS Application:Automated Markets: CIS Application: Automated Markets A mail-order hardware retailer sells its own brand of wrenches. It asks its suppliers for particular kinds of wrenches whose demand is high. It would like to achieve this through an automated system, which requests bids for each kind of wrench that has low inventory gathers and evaluates bids negotiates as necessary with the more promising suppliers,and places orders [representing autonomous interests]


CIS Application:Manufacturing Control: CIS Application: Manufacturing Control An automotive parts manufacturer uses a decision-support system to schedule down-time for machine tools. Independently, each machining operation is monitored for the parts produced, so that the tool may be replaced when too many parts fall out of tolerance When a tool is taken off-line, upstream parts pile up and downstream parts dry up. The systems should communicate the nature and expected extent of the down-time [distributed decision-making]


CIS Application:Process Control: CIS Application: Process Control One chemical process supplies a solvent needed by a second chemical process. The process controllers are written in the same language and run on identical computers. The computers are linked by Ethernet. However, when the first process is shut down, the second process may not learn about it until the solvent suddenly stops flowing. This can prove expensive [homogeneity of platforms is insufficient]


Dimensions of CIS: Agent: Dimensions of CIS: Agent Dynamism is the ability of an agent to learn: Autonomy: Interactions: Sociability (awareness): Fixed Teachable Autodidactic Controlled Independent Simple Complex Interdependent Autistic Collaborative Committing


Dimensions of CIS: System: Dimensions of CIS: System Scale is the number of agents: Interactions: Coordination (self interest): Agent Heterogeneity: Communication Paradigm: Individual Committee Society Reactive Planned Antagonistic Altruistic Collaborative Competitive Cooperative Benevolent Identical Unique Point-to-Point Multi-by-name/role Broadcast


Basic Problems of CIS: Basic Problems of CIS 1. Description, decomposition, and distribution of tasks among agents 2. Interaction and communication among agents 3. Distribution of control among agents 4. Representation of goals, problem-solving states, and other agents 5. Rationality, consistency maintenance, and reconciliation of conflicts among agents


2. ENTERPRISE INTEGRATION: 2. ENTERPRISE INTEGRATION


Enterprise Modeling: Enterprise Modeling Model static and dynamic aspects of enterprises Models document business functions databases applications knowledge bases workflows, and the information they create, maintain, and use the organization itself Models enable reusability integrity validation consistency analysis change impact analysis automatic database and application generation


Building a System: Building a System Cognition Universe of Discourse 1 Conceptual Schema CASE Tool Interface Application Database use generate construct observe


Building Cooperating Systems: Building Cooperating Systems Cognition Universe of Discourse 1 Conceptual Schema CASE Tool Interface Application Database use generate Cognition Conceptual Schema CASE Tool Interface Application Database use generate Universe of Discourse 2 Ontology construct construct observe observe


Cooperation in Information Systems: Cooperation in Information Systems Connectivity: ability to exchange messages Interoperability: ability to exchange messages to request and receive services, i.e., use each other’s functionality Cooperation: ability to perform tasks jointly


Information System Architectures:Centralized: Information System Architectures: Centralized Mainframe Terminal 3270 Terminal Terminal Terminal Terminal Terminal Terminal Terminal Terminal Terminal Terminal


Information System Architectures:Client-Server: Information System Architectures: Client-Server E-Mail Server Web Server Database Server PC Client PC Client PC Client Workstation Client Master-Slave


Information System Architectures:Distributed: Information System Architectures: Distributed E-Mail System Web System Database System Application Application Application Application Peer-to-Peer


Information System Architectures:Cooperative: Information System Architectures: Cooperative E-Mail System Web System Database System Application Application Application Application (Mediators, Proxies, Aides, Wrappers) Agent Agent Agent Agent Agent Agent Agent Agent


Cooperating Information Systems: Cooperating Information Systems Hospital CIS Doctor’s CIS Insurance CIS Clinic/HMO CIS Lab data Claims Accounting


Legacy Systems: Legacy Systems


Legacy Systems: Legacy Systems A pejorative term for computing systems that run on obsolete hardware and nonstandard communication networks run poorly documented, unmaintainable software consist of poorly modeled databases on hierarchical or network DBMSs support rigid user interfaces Legacy systems are important for us precisely because they are not cooperative!


How Legacy Systems Arise: How Legacy Systems Arise Proprietary software not documented not supporting industry standards (vendors who hope to lock in the market through incompatibility) Semantics embedded procedurally in the code Ad hoc changes to software in response to changing requirements, because of changes in laws, regulations, competition, or other business needs bugs


Legacy Systems: Negative: Legacy Systems: Negative Difficulties in reuse and sharing of data and programs cause redundancy, wasted effort, and integrity violations Closed: typically, use a vendor’s proprietary software, and cannot cooperate with other systems


Legacy Systems: Positive: Legacy Systems: Positive Fulfill crucial business functions Work, albeit suboptimally Run the world’s airline reservation systems Run most air traffic control programs Have dedicated users Represent huge investments in time and money


Current Trends: Current Trends Create open systems Follow industry standards Use advances in software engineering and databases Enable applications to talk to one another, even if developed by different manufacturers This leads to better systems, because components can be built by specialists and system designers have more choice. But what about the older systems?


Accommodating Legacy Systems: Accommodating Legacy Systems Introduce new technology as needed Integrate legacy systems with new components Integrate the legacy systems with each other But don’t spoil existing applications Is this even possible? If not, why not? If so, how might one achieve this?


Important Considerations: Important Considerations The effort per system one is willing to invest in modifying existing applications acquiring knowledge about, i.e., models of, the existing applications The limits on the ranges of the new applications Whether improvements to legacy applications are sought


Levels of Interoperation: Levels of Interoperation Respond to the various ways in which legacy systems misbehave: Transport Messaging Task Coordination Semantics Application Development In addition, a means to manage change is important


Transport: Transport Glue s/w provides maps among communication protocols. (Often, such s/w is available from the legacy system vendors making their systems compatible with newer ones.) Legacy HW & SW Glue S/W • • • New, Open System(s)


Messages: Messages A client application can access and update databases without concern for the message protocol for the server DBMS, e.g., use JDBC to access databases on a DBMS products such as Oracle or Sybase Clients Servers Middleware Legacy HW & SW Glue S/W • • • Open Systems


Task Coordination: Task Coordination Tasks execute on multiple client, server, and middleware systems; Need to coordinate them for distributed queries and transactions general workflow processing Coordinate the tasks by ordering the execution of the tasks setting up data flow among the tasks


Semantic Interoperability: Semantic Interoperability Integrate or relate database schemas Generate business rules Generate integrity constraints on various information resources that can be combined to capture the proper behavior of any application


Application Development: Application Development How to develop new applications that extend over multiple new and legacy systems respect the semantics of the various resources they involve


Managing Change: Managing Change Adding or removing components dynamically without modifying applications, and without affecting the ongoing activities in the system Using new components, applications, user interfaces concurrently with old ones


Autonomy: Autonomy Design vs. control autonomy Political reasons Ownership of resources Control, especially of access privileges Payments Technical reasons Conceptual problems in integration Fragility of integration Difficult to guarantee behavior of integrated systems Opacity of systems with respect to key features, e.g., precommit Leverage: Use agents! Modularity User control Negotiation among agents to resolve conflicts


Locality: Locality Global information (data, schemas, constraints) causes Inconsistencies Anomalies Difficulties in maintenance Relaxation of constraints works often Correct rather than prevent violations of constraints--often feasible When, where, and how of corrections must be specified, but it is easier to make it local (recall process abstractions) Still need some global information, or way to obtain it Locations of services or agents Applicable business rules Obtain other global knowledge only when needed


Migration: Migration Updating technology is Essential A continual process All at once? Expensive Risky Brittle Frustrating for users Gradual change: dismantle legacy and build desired system hand-in-hand Install and test piecemeal


Old-to-New Converters: Old-to-New Converters Example: hierarchical to relational converters, which generate SQL from hierarchical (e.g., IMS) programs Convert Old Interface to New IMS Code Legacy HW & SW SQL New System


New-to-Old Converters: New-to-Old Converters Example: relational to hierarchical converters, which generate hierarchical (e.g., IMS) programs from SQL Convert New Interface to Old IMS Code Legacy HW & SW SQL New System


Converters Applied to Interoperation: Converters Applied to Interoperation Converters work well where there are only a small number of applications Converters can be applied, but expensively need a converter between every pair of applications, user interfaces, and database systems


A Better Picture: A Better Picture With enough such generic converters, we can make legacy systems talk to one another and to new systems Bonus: we can handle disparities among new systems as well Convert Any New or Old Interface Legacy HW & SW New Systems Application Applications and Interfaces Convert Any New or Old Interface


Applying Agents: Applying Agents Agents can be the generic converters. We also need to nondestructively interpose agents between the components (weakly) type the messages exchanged use tools to keep track of the resources, i.e., applications and databases use tools to coordinate tasks


One Approach: One Approach The glue software does all the work Is such a glue possible? How might it be constructed? Clients Servers Middleware Legacy HW & SW Glue S/W • • • Open Systems Distributed UNIX Systems


XML-Based Information System : XML-Based Information System


Database Integration: Database Integration


Dimensions of Integration: Dimensions of Integration Existence of global schema Location transparency: same view of data and behavior at all sites Uniform access and update language Uniform interaction protocols Opacity of replication Strict semantic guarantees of overall system


Full Integration: Full Integration Distributed databases are the most tightly integrated. They provide A global schema and a unique way to access data through that schema Location transparency Replication managed automatically ACID transactions (explained below)


Federation: Federation Less than full integration Local schemas and a global schema coexist: access may be through either (at a given site, the local schema and the global schema are visible) ACID transactions are optional, but still possible if the local transaction managers are open—problems of extraneous conflicts must be solved Location transparency


Multidatabases: Multidatabases Multidatabases are a loose form of federation involving No global schema A uniform language to access the DB The locations of the data are visible to the application There may be some support for semantic constraints, depending on what the underlying systems provide


Interoperation: Interoperation Interoperation is the loosest form of integration, in that there is no real integration of the databases There might be no global schema Heterogeneous ways to access the DB must coexist Location transparency is not easy to achieve Different languages might be required at different databases, because they might have different underlying metamodels Applications must handle all semantics


Workflows: Workflows Tasks include queries, transactions, applications, and administrative activities Tasks decompose into subtasks that are distributed and heterogeneous, but coordinated Subtasks have mutual constraints on order occurrence return values


Workflow Applications: Workflow Applications Loan application processing Processing admissions to graduate program Telecommunications service provisioning often requires several weeks many operations (48 in all, 23 manual) coordination among many operation-support systems and network elements (16 database systems)


Traditional Transactions: Traditional Transactions DB abstraction for activity ACID properties Atomicity: all or none Consistency: final state is consistent if initial state is consistent Isolation: intermediate states are invisible Durability: committed results are permanent In distributed settings, use mutual (e.g., two-phase) commit to prevent violation of ACID properties x:=x-a y:=y+a


Why Workflows?: Why Workflows? ACID transactions are applicable for brief, simple activities (few updates; seconds, at most) on centralized architectures By contrast, open environments require tasks that are Complex, i.e., long-running, failure-prone, update data across systems with subtle consistency requirements Cooperative, i.e., involve several applications and humans Over heterogeneous environments Have autonomous unchangeable parts


Workflow Challenges: Workflow Challenges Modeling a workflow Notion of correctness of executions Notion of resource constraints Interfacing a workflow interface with underlying databases? Concurrency control Recovery Exception handling: normal executions are often easy—just a partial order of activities Handling revisions


Extended Transactions: Extended Transactions Numerous extended transaction models that relax the ACID properties in set ways. They consider features such as Nesting traditional: closed (ACID) newer: open (non-ACID) Constraints among subtransactions, such as commit dependencies abort Atomicity, e.g., contingency procedures to ensure “all” Consistency restoration, e.g, compensation


Extended Transaction Models: Extended Transaction Models Sagas Poly transactions Flex transactions Cooperative transactions DOM transactions Split-and-join transactions ACTA metamodel Long-running activities ConTracts


Scheduling Approaches: Scheduling Approaches These address the issues of how activities may be scheduled, assuming that desired semantic properties are known Significant events of a task are the events that are relevant for coordination. Thus a complex activity may be reduced to a single state and termination of that activity to a significant event Workflows can be modeled in terms of dependencies among the significant events of their subtasks Example: If the booking assignment transaction fails, then initiate a compensate transaction for the billing transaction


Dependency Enforcement: Dependency Enforcement A specified workflow may only be executed if the corresponding dependencies can be enforced. Is this always possible? No! The stated dependencies may be mutually inconsistent, e.g., in requiring e before f and f before e e should occur and should not occur The assumptions made about the significant events may not be realized in the given tasks. For example a task commits before it starts a task commits and aborts a commit should be triggered


Syntactic Event Attributes: Syntactic Event Attributes Many of the assumptions can be syntactically tested. These are independent of the exact nature of the tasks or the significant events: Whether an event occurs or not The mutual ordering of various events The consistency of the ordering of the schedule with the ordering of events in the task, e.g., start precedes commit The consistency of the schedule with the events in the task, e.g., abort and commit are complementary events The last is borderline between syntactic and semantic attributes


Semantic Event Attributes: Semantic Event Attributes There are also certain semantic event attributes that affect the enforceability of a set of dependencies. Events may variously be Delayable: those which the scheduler can defer commit of a transaction Rejectable: those which the scheduler can prevent commit of a transaction Triggerable: those which the scheduler can cause to occur start of a task


Transaction Management in Multidatabase Systems: Transaction Management in Multidatabase Systems


MDBS: MDBS 3 levels of autonomy are possible design, e.g., LDB software is fixed execution, e.g., LDB retains full control on execution even if in conflict with GTM communication, e.g., LDB decides what (control) information to release GTM LDB LDB server server Global Transactions Local Transactions


Global Serializability: Global Serializability Transactions throughout the MDBS are serializable, i.e., the transactions are equivalent to some serial execution What the GTM can ensure is that the global transactions are serializable This doesn't guarantee global serializability, because of indirect conflicts: GTM does T1: r1(a); r1(c) GTM does T2: r2(b); r2(d) LDB1 does T3: w3(a); w3(b) LDB2 does T4: w4(c); w4(d) Since T1 and T2 are read-only, they are serializable. LDB1 sees S1=r1(a); c1; w3(a); w3(b); c3; r2(b); c2 LDB2 sees S2=w4(c); r1(c); c1; r2(d); c2; w4(d); c4 Each LDB has a serializable schedule; yet jointly they put T1 before and after T2


Global Atomicity: Global Atomicity This arises because some sites may not release their prepare-to-commit state and not participate in a global commit protocol Global Deadlock Easy to construct scenarios in which a deadlock is achieved. Assume LDB1 and LDB2 use 2PL. If a deadlock is formed solely of global transactions, then the GTM may detect it of a combination of local and global transactions, then GTM won't know of it LDBs won't share control information


Tickets: Tickets Global serializability occurs because of local conflicts that the GTM doesn't see Fix by always causing conflicts--whenever two GTs execute at a site, they must conflict there. Indirect conflicts become local conflicts visible to the LDB Make each GT increment a ticket at each site Downside: Causes all local subtransactions of a global transaction to go through a local hotspot GTs are serialized but only because lots are aborted!


Rigorous DBMS: Rigorous DBMS Rigorous = Strict. Check that this prevents the bad example. The GTM must delay all commits until all actions are completed possible only if allowed by LDB requires an operation-level interface to LDB Downside: Causes all sites to be held up until all are ready to commit Essentially like the 2PC approach


Global Constraints: Global Constraints When no global constraints, local serializability is enough Can split data into local and global LDB controls local data GTM controls global (local read but only write via GTM) Downside: doesn’t work in all cases


Atomicity & Durability: Atomicity & Durability What happens when a GT fails? The local sites ensure atomicity and durability of the local subtransactions With 2PC, GTM can guarantee that all or none commit Otherwise, redo: rerun the writes from log retry: rerun all of a subtransactions compensate: semantically undo all others


3. INFORMATION APPLICATIONS: 3. INFORMATION APPLICATIONS


Retrieval versus Discovery: Retrieval versus Discovery What or who? Retrieval is concerned with obtaining information from a specific set of servers with a specific query and consistency might matter (correctness) Resource discovery is concerned with finding where to get the information incompleteness might matter relevance might matter Retrieval is almost as difficult in closed environments as in open ones. Discovery is not as difficult a problem in closed environments Fusing information can require both


Network Navigation: Network Navigation Organize servers into a network so that you can reach appropriate ones from each other. Examples: Gopher, WWW Typically a matter of following pointers through a friendly, but not very helpful, interface: No semantics or notion of relevance No support for query routing No support for making links


Network-Based Retrieval: Network-Based Retrieval These are minimalist approaches to getting at information Wide Area Information Service (WAIS) can help retrieve information. It is keyword based requires the user to select a site, possibly through the directory of servers, which may not be very good allows simple relevance feedback from a user to control the documents retrieved


Resource Discovery: Resource Discovery Key issues include Scalability (w.r.t. network and server loads) amount of data number of server sites number of users Efficient and effective indexing of information sources high relevancy low volume


Harvest: Harvest Main architectural components: Provider, which runs a service (resource) Gatherer, which resides on the provider's site and monitors it for indexing info; specialized for a topic Broker, which gives an indexed query interface to a number of providers Replicator, which manages a wide-area file-system (with eventual consistency) Service Registry, which knows about all gatherers and brokers Brokers can be nested Users can get to succinct indexes from which they can find the server sites with the best fit for their query No semantic support; topic-specific indexing can be demanding, but is still a good solution


Content Routing: Content Routing Associates a content label with each document or collection (may be recursive). The label abstractly specified the contents of its document or collection Queries (and labels) are boolean combinations of attributes User begins a query at a server; a standard server exists for novices The query is matched against labels to select good collections; this is done repeatedly until a base collection (one with documents) is found Good approach, but gives no semantics to the labels


MINDS: Agent-Based Management of Flat-File Documents: MINDS: Agent-Based Management of Flat-File Documents Documents Surrogates TCP/IP Other Nodes File System Relational Database System MINDS User Documents Surrogates


Key Features of MINDS: Key Features of MINDS Uses metaknowledge (about other agents and how information is used) knowledge about the contents and locations of documents-these are acquired dynamically certainty factors that indicate the likelihood that one user will supply relevant information to another to control query processing Maintains a system view at each node user models at each node Is self-initializing Processes queries best-first and in parallel Improves its performance over time


System Dynamics of MINDS: System Dynamics of MINDS Query Engine Learning Subsystem RDBMS: Documents and Metaknowledge x(k) (command) y(k) (retrieved documents and surrogates) h(k) Output function: y(k) = q(x(k), h(k)) State function: h(k+1) = a(x(k), h(k))


Updating Metaknowledge in MINDS: Updating Metaknowledge in MINDS Heuristic 1: IF a document is deleted, THEN no metaknowledge is changed Heuristic 2: IF a document is created by user1, THEN metaknowledge of user1 about user1 regarding each keyword of the document is increased to 1.0 (maximum relevance) Heuristic 3: IF a retrieve predicated on keyword1 is issued by user1, AND at least one user2 surrogate contains keyword1, THEN (a) user1 metaknowledge about user2 regarding keyword1 is increased (weight 0.1), (b) user2 metaknowledge about user1 regarding keyword1 is increased (weight 0.1)


SIMS: SIMS A network of information agents each specialized with knowledge represented in a taxonomic (concept) language (LOOM) Queries are also in LOOM. They guide selection of information sources reformulation of query generation of query plans Important heuristics include generalize or specialize concept partition concept decompose relation Includes a learning component


4. AGENTS: 4. AGENTS


Agent Environments: Agent Environments Communication Infrastructure Shared memory (blackboard) Connected or Connectionless (email) Point-to-Point, Multicast, or Broadcast Directory Service Communication Protocol KQML HTTP and HTML OLE, CORBA, DCOM, etc. Interaction Protocol Mediation Services Security Services (timestamps/authentication/currency) Remittance Services Operations Support (archiving/billing/redundancy/restoration/accounting)


Protocol Handlers: Protocol Handlers Mediators [Wiederhold] Aides [Carnot DCA] Database and Protocol Agents [Carnot ESS] Heads [Steiner] Brokers [OMNI] Knowledge handlers [COSMO] Intelligent information agents [Papazoglou] Front-end processors [Hecodes] Integrating agents, routers, and wrappers [Gray] Facilitators [ARPA Knowledge Sharing Effort]


Mediators: Mediators Modules that exploit encoded knowledge about data to create information for higher-level applications. Mediators, thus, provide logical views of the underlying information reside in an active layer between applications and resources are small, simple, and maintainable independently of others are declaratively specified, where possible, and inspectable by users come in a wide range of capabilities, from database and protocol converters, to intelligent modules that capture the semantics of the domain and learn from the data


Mediator Architecture: Mediator Architecture Application Programs Information Resources User Interfaces Networks Network Interfaces and Mediators


Mediator Interfaces: Mediator Interfaces Mediators should be separate from databases mediators contain knowledge beyond the scope of a database mediators contain abstractions that are not part of a database mediators must deal with uncertainty mediators access multiple databases to combine disjoint data Mediators should be separate from applications their functions are different in scope than those of applications separate mediators are easier to maintain Because mediators are stable and small, they can be mobile they can be shipped to sites where large volumes of data must be processed


Learning in Mediators: Learning in Mediators Learning can be driven by feedback from performance measures explicit induction over information resources Result of learning can be modifications to certainty parameters augmented tabular knowledge new symbolic concepts


Type Brokers: Type Brokers A means to manage structure and semantics of information and query languages. Define standard types by which computations can communicate. Most of this work pertains to lower level issues than CIS Typically these involve a set of type servers or brokers and a way to distribute type information. An application uses the broker to find a service, and then communicates directly with the desired service Brokers give slightly more semantics than directories--the type signature of methods, not just their names With more sophisticated notions of service semantics, these could be more useful


II. Progress in Agent-Based Information Management: II. Progress in Agent-Based Information Management Middleware: Mediators, Brokers, and Facilitators


Types of Cooperative Information Agents: Types of Cooperative Information Agents “Standard” information agents and architectures are now available Ontology Agent Application Program Mediator Agent Broker Agent Database Resource Agent Database Resource Agent Query or Update In SQL Reply Reg/Unreg (KQML) Reg/Unreg (KQML) Reg/Unreg (KQML) Mediated Query (SQL) Reply Schemas (CLIPS) Reply Mediated Query (SQL) Ontology (CLIPS) User Interface Agent Reply Reg/Unreg (KQML)


Intranet Agent Architecture: Intranet Agent Architecture Intranet services enable the federation of distributed heterogeneous agents to interoperate and collaborate Agents register their names and capabilities using naming service directory service Agents use a brokerage service to find other agents that can deal with a specified request Agent activity within the net is recorded by a logging service Agent status and interactions are shown by a visualization service Interactions via FIPA ACL


Access to Services: Access to Services


Network Services: Network Services 1 instance of the Naming Service per LAN 1..n instances of Directory Service and Brokerage Service per LAN


Naming Service: Naming Service Architecture requires scalable, symbolic name resolution Alternative naming protocols FIPA Tim Finin’s KNS proposal to FIPA LDAP Jini CORBA Naming Service JNDI


Directory Service: Directory Service Simple yellow pages service Registered agents advertise their services by providing their name, address, and service description Agents request recommendations for available services (provided by other registered agents or services) A simple database-like mechanism that allows agents to insert descriptions of the services they offer query for services offered by other agents. 1..n Directory Service Agents on a LAN Brokerage, recruitment and mediation services are not provided by Directory Service


Brokerage Service: Brokerage Service Cooperates with the Directory Service An agent requests the Brokerage Service to recruit one or more agents who can answer a query Brokerage Service uses knowledge about the requirements and capabilities of registered agents to determine the appropriate agents to which to forward a query send the query to those agents relay their answers back to the original requestor learn about the properties of the responses it passes on example: Brokerage agent determines that advertised results from agent X are incomplete and seeks out a substitute for agent X


Agent Technology Toolkit at IBM: Agent Technology Toolkit at IBM ABE "Agent Building Environment" from IBM written in C++ and Java, agents have rule-based reasoning and interfaces to the web (http), news groups (nntp), and email (smtp)


Agent Technology Toolkit at IBM: Agent Technology Toolkit at IBM JKQML from IBM: a framework and API for constructing Java-based, KQML-speaking software agents that communicate over the Internet. JKQML includes KTP (KQML transfer protocol): a socket-based transport protocol for a KQML message represented in ASCII. ATP (agent transfer protocol): a protocol for KQML messages transferred by a mobile agent that is implemented by Aglets. OTP (object transfer protocol): a transfer protocol for Java objects that are contained in a KQML message


Agent Technology Toolkit at Stanford: Agent Technology Toolkit at Stanford The "Java Agent Template" JATLite enables simple Java agents to communicate over a LAN via KQML provides an agent nameserver provides a message router that implements a store-and-forward capability (useful for disconnected agents) enables communication via TCP/IP or email


Agent Technology Toolkit at CMU: Agent Technology Toolkit at CMU RETSINA: an architecture for multiple agents that team up on demand to access, filter, and integrate information in support of user tasks


Agent Technology Toolkit from Sandia: Agent Technology Toolkit from Sandia JESS "Java Expert System Shell" (CLIPS in Java) enables solitary, rule-based reasoning agents to be constructed agents can reason about Java objects


Agent Technology at MCC: Agent Technology at MCC The InfoSleuth Project a toolkit of agent types for interconnecting heterogeneous resources resource agents ontology agents query and transaction agents user interface agents a toolkit for dealing with semantic heterogeneity applications to healthcare IS, environmental data, semiconductor manufacturing control, logistics, battlefield situation awareness


Agent Technology Toolkit at SRI: Agent Technology Toolkit at SRI Open Agent Architecture from SRI agents use a logic-based InterAgent Communication Language and run on CORBA; a facilitator distributes tasks to agents, with results sent to user agents. It has the following features: Open: agents can be created in multiple programming languages and interface with existing legacy systems Extensible: agents can be added or replaced at runtime Distributed: agents can be spread over networked computers Parallel: agents can cooperate or compete on tasks in parallel Mobile: user interfaces can run on handheld PDA's Multimodal: handwriting, speech, pen gestures, and direct manipulation GUIs can be used to communicate with agents


Agent Technology at USC-ISI: Agent Technology at USC-ISI Ariadne Project Technology and tools for rapidly constructing mediators to extract, query, and integrate data from web sources wrappers that make web sources look like databases The mediator and wrapper approach makes it easy to maintain applications and incorporate new sources as they become available


Tools from Reticular Systems Inc.: Tools from Reticular Systems Inc. AgentBuilder is an integrated tool suite for constructing intelligent software agents. It consists of two major components The AgentBuilder Toolkit includes tools for managing the agent-based software development process, analyzing the domain of agent operations, designing and developing networks of communicating agents, defining behaviors of individual agents, and debugging and testing agent software The Run-Time System includes an agent engine that provides an environment for execution of agent software. Agents constructed using AgentBuilder communicate using KQML


Agent Technology Toolkit from ObjectSpace Inc.: Agent Technology Toolkit from ObjectSpace Inc. AgentSpace is a Java-based framework for mobile agent systems developed on top of the ObjectSpace Voyager system. It provides a Java multithreaded server process in which agents can be executed a set of Java client applets that support the management and monitoring of agents and related resources a package of Java interfaces and classes that defines the rules to build agents


Mobility: Mobility


Mobility: Mobility Anything that can be done with mobile agents can be done with conventional software technology, so the key question is Are there tasks that are easier to develop using mobile agents? or Are mobile agents a useful part of a distributed computing platform? Appropriate Applications: Disconnected operation, especially for PDAs Testing distributed network hardware (a multihop application) Concerns: Security Efficiency Survivability - too short or too long!


Itinerant Agents: Itinerant Agents Itinerant agents are remote computational entities that are most useful when a large amount of data must be processed and the remote site does not have the procedures to perform the processing. Itinerant agents can be used to initiate and maintain long-lived sessions over intermittent communications


Mobile Agent Toolkit from IBM: Mobile Agent Toolkit from IBM Aglets are mobile Java agents that can roam the Internet. They are developed using the Aglets Workbench Aglets are in use in Japan http://www.tabican.ne.jp/index.html will help you to find a package tour or flight that matches your requirements


Mobile Agent Technology at Mitsubishi: Mobile Agent Technology at Mitsubishi Concordia - a framework for development and management of network-efficient mobile agent applications for accessing information anytime, anywhere, and on any device supporting Java. With Concordia, applications: Process data at the data source Process data even if the user is disconnected from the network Access and deliver information across multiple networks (LANs, Intranets and Internet), using wire-line or wireless communication Support multiple client devices, such as Desktop Computers, PDAs, Notebook Computers, and Smart Phones


Mobile Agent Frameworks: Mobile Agent Frameworks Odyssey from General Magic agents are programmed in Java ARA "Agents for Remote Action" from University of Kaiserslautern agents are programmed in Tcl, C/C++, or Java MOA "Mobile Objects and Agents" from The OpenGroup uses OS process migration technology Concordia from Mitsubishi Electric Information Technology Center agents are programmed in Java Aglets from IBM agents are programmed in Java TKQML from University of Maryland Baltimore County migrating agents are programmed in Tcl and communicate in KQML Most allow agents to be started, stopped, moved, and monitored


Enabled Email: Enabled Email Generic term for ways to extend email capabilities, by enhancing functionality at delivery time (sender controls message) receipt time (receiver controls message) activation time (receiver processes message) Conceptually, a superset of multimedia email and filtering mechanisms. Enabled email messages can perform computations in receiver's environment Borenstein proposed a language, Safe-Tcl, for enabled email. There are proposed standards afoot


Rosette: Rosette The Carnot Project at MCC has developed the Rosette language, which is object-oriented is based on Actors with multithreading includes tree spaces (like Linda's tuple-spaces) has scripts that execute in an actor's environment Rosette was used for managing computations and services in intra-enterprise environments. It was extended for open environments, in terms of security and authentication


Telescript: Telescript General Magic’s language for developing itinerant agents, Telescript is object-oriented persistent interpreted with special primitives for communication The telescript environment consists of places organized into regions with homogeneous control agents can travel over places agents must prove their credentials before entering a new region


Telescript: Telescript Agents move from one Place to another Place to perform their assigned tasks Agents and Places are processes Agents and Places can request operations and data from each other Places are grouped into Clouds, each of which has a local directory (Finder database)


Challenges for Itinerant Agents: Challenges for Itinerant Agents Programming languages are needed that can express useful remote computations are understood at remote sites and are portable (standards) do not violate security of the sender or receiver are extensible Understand the semantics of the different information resources being accessed


Challenges for Itinerant Agents: Challenges for Itinerant Agents Techniques to manage distributed computations that disseminate extensions to the programming language interpreter authenticate senders improve interfaces so that advanced users are not penalized while older systems are supported prevent deadlock prevent livelock control lifetimes prevent flooding of communication or storage resources


Control: Control


Importance of Control: Importance of Control How to maintain global coherence without explicit global control? Important aspects include how to determine shared goals determine common tasks avoid unnecessary conflicts pool knowledge and evidence


Task Decomposition: Task Decomposition Divide-and-conquer to reduce complexity: smaller subtasks require less capable agents and fewer resources Task decomposition must consider the resources and capabilities of the agents, and potential conflicts among tasks and agents The designer decides what operators to decompose over The system decides among alternative decompositions, if available


Task Decomposition Methods: Task Decomposition Methods Inherent (free!): the representation of the problem contains its decomposition, as in an AND-OR graph System designer (human does it): decomposition is programmed during implementation. (There are few principles for automatically decomposing tasks) Hierarchical planning (agents do it): decomposition again depends heavily on task and operator representation


Task Decomposition Examples: Task Decomposition Examples Spatial decomposition by information source or decision point: Functional decomposition by expertise: Pediatrician Internist Psychologist Neurologist Cardiologist Agent 1 Agent 2 Agent 3


Task Distribution Criteria: Task Distribution Criteria Avoid overloading critical resources Assign tasks to agents with matching capabilities Make an agent with a wide view assign tasks to other agents Assign overlapping responsibilities to agents to achieve coherence Assign highly interdependent tasks to agents in spatial or semantic proximity. This minimizes communication and synchronization costs Reassign tasks if necessary for completing urgent tasks


Task Distribution Mechanisms: Task Distribution Mechanisms Market mechanisms: tasks are matched to agents by generalized agreement or mutual selection (analogous to pricing commodities) Contract net: announce, bid, and award cycles Multiagent planning: planning agents have the responsibility for task assignment Organizational structure: agents have fixed responsibilities for particular tasks Recursive allocation: responsible agent may further decompose task and allocate the resultant subtasks


The Contract Net Protocol: The Contract Net Protocol An important generic protocol A manager announces the existence of tasks via a (possibly selective) multicast Agents evaluate the announcement. Some of these agents submit bids The manager awards a contract to the most appropriate agent The manager and contractor communicate privately as necessary


Task Announcement Message: Task Announcement Message Eligibility specification: criteria that a node must meet to be eligible to submit a bid Task abstraction: a brief description of the task to be executed Bid specification: a description of the expected format of the bid Expiration time: a statement of the time interval during which the task announcement is valid


Bid and Award Messages: Bid and Award Messages A bid consists of a node abstraction—a brief specification of the agent’s capabilities that are relevant to the task An award consists of a task specification—the complete specification of the task


Applicability of Contract Net: Applicability of Contract Net The Contract Net is a high-level communication protocol a way of distributing tasks a means of self-organization for a group of agents Best used when the application has a well-defined hierarchy of tasks the problem has a coarse-grained decomposition the subtasks minimally interact with each other, but cooperate when they do


5. INTERACTION AND COMMUNICATION: 5. INTERACTION AND COMMUNICATION


Communication: Communication The primary reason for communication among agents is to coordinate activities Agents may coordinate without communication provided they have models of the others’ behavior Communication involves the dimensions of who, what, when, how (resources and protocol), and why To facilitate cooperation, agents often need to communicate their intentions, goals, results, and state


Communication Versus Computation: Communication Versus Computation Communication is generally more expensive and less reliable: Recomputing is often faster than requesting information over a communication channel Communication can lead to prolonged negotiation Chains of belief and goal updates caused by communication may not terminate Communication is qualitatively superior: Information cannot always be reconstructed locally Communication can be avoided only when the agents are set up to share all necessary knowledge (a limiting assumption)


Interaction and Communication: Interaction and Communication Interactions occur when agents exist and act in close proximity: resource contention, e.g., bumping into each other Communication occurs when agents send messages to one another with a view to influencing beliefs and intentions. Implementation details are irrelevant: can occur over communication links can occur through shared memory can occur because of shared conventions


CIS Communication Protocols: CIS Communication Protocols A CIS protocol is specified by the following fields: sender receiver(s) language in the protocol actions to be taken by the participants at various stages A CIS protocol is defined above the transport layer not about bit patterns not about retransmissions or routing A CIS protocol is defined at the knowledge level involves high-level concepts, such as commitments, beliefs, intentions permissions, requests


A Classification of Message Classifications: A Classification of Message Classifications Syntactic distinguish messages based on grammatical forms in natural language Semantic distinguish messages based on a notion of intrinsic meaning prohibitive is different from directive, despite syntactic similarity Use-based distinguish messages based on their roles in specific classes of protocols assertion is different from acknowledgment


Speech Act Theory: Speech Act Theory Speech act theory, developed for natural language, views communication as action. It considers three aspects of a message: Locution, or how it is phrased, e.g., "It is hot here" or "Turn on the cooler" Illocution, or how it is meant by the sender or understood by the receiver, e.g., a request to turn on the cooler or an assertion about the temperature Perlocution, or how it influences the recipient, e.g., turns on the cooler, opens the window, ignores the speaker Illocution is the core aspect.


Speech Act Theory and MAS: Speech Act Theory and MAS Classifications of illocution motivate message types in MAS. However, they are typically designed for natural language rely on NL syntax, e.g., they conflate directives and prohibitives Most research in speech act theory is about determining how locutions map to illocutions. This is trivial in CIS, since the message type is usually explicitly encoded However, speech act theory can contribute by giving a principled basis for studying communication related to beliefs, intentions, know-how of agents can have a formal semantics


Informing: Informing How can one agent tell another agent something? Send the information in a message (message passing) Write the information in a location where the other agent is likely to look (shared memory) Show or demonstrate to the other agent (teaching) Insert or program the information directly into the other agent (master --> slave; controller --> controllee; "brain surgery")


Querying: Querying How can one agent get information from another agent? Ask the other agent a question (message passing) Read a location where the other agent is likely to write something (shared memory) Observe the other agent (learning) Access the information directly from the other agent ("brain surgery")


Syntax, Semantics, Pragmatics: Syntax, Semantics, Pragmatics For message passing Syntax: requires a common language to represent information and queries, or languages that are intertranslatable Semantics: requires a structured vocabulary and a shared framework of knowledge-a shared ontology Pragmatics: knowing whom to communicate with and how to find them knowing how to initiate and maintain an exchange knowing the effect of the communication on the recipient


KQML: Knowledge Query and Manipulation Language: KQML: Knowledge Query and Manipulation Language KQML KQML Agent Agent Application Program


KQML Protocols: KQML Protocols Client Server Client Server Client Server Query Reply Query Handle Next Next Reply Reply Reply Reply Reply Subscribe Synchronous: a blocking query waits for an expected reply Asynchronous: a nonblocking subscribe results in replies Server maintains state; replies sent individually when requested


KQML Is a Layered Language: KQML Is a Layered Language Content of Communication Message: Logic of Communication Communication: Mechanics of Communication


Communication Assumptions: Communication Assumptions Agents are connected by unidirectional links that carry discrete messages Links have nonzero transport delay Agent knows link of received message Agent controls link for sending Messages to a single destination arrive in the order they were sent Message delivery is reliable


KQML Semantics: KQML Semantics Each agent manages a virtual knowledge base (VKB) Statements in a VKB can be classified into beliefs and goals Beliefs encode information an agent has about itself and its environment Goals encode states of an agent’s environment that it will act to achieve Agents use KQML to communicate about the contents of their own and others’ VKBs


Reserved Performative Types: Reserved Performative Types 1. Query performatives: evaluate, ask-if, ask-one, ask-all 2. Multiresponse performatives: stream-in, stream-all 3. Response performatives: reply, sorry 4. Generic informational performatives: tell, achieve, cancel, untell, unachieve 5. Generator performatives: standby, ready, next, rest, discard 6. Capability-definition performatives: advertise, subscribe, monitor, import, export 7. Networking performatives: register, unregister, forward, broadcast, route, recommend


Informatives: Informatives tell :content :language :ontology :in-reply-to :force :sender :receiver deny :content :language KQML :ontology :in-reply-to :sender :receiver untell :content :language :ontology :in-reply-to :force :sender :receiver


Database Informatives: Database Informatives insert :content :language :ontology :reply-with :in-reply-to :force :sender :receiver delete :content :language KQML :ontology :reply-with :in-reply-to :sender :receiver


Query Performatives: Query Performatives evaluate :content :language :ontology :reply-with :sender :receiver reply :content :language KQML :ontology :in-reply-to :force :sender :receiver ask-one :content :aspect :language :ontology :reply-with :sender :receiver


Semantics of Communications: Semantics of Communications What if the agents have different terms for the same concept? same term for different concepts? different class systems or schemas? differences in depth and breadth of coverage?


Common Ontologies: Common Ontologies A shared representation is essential to successful communication and coordination For humans, this is provided by the physical, biological, and social world For computational agents, this is provided by a common ontology: terms used in communication can be coherently defined interaction policies can be shared Current efforts are Cyc DARPA ontology sharing project Ontology Base (ISI) WordNet (Princeton)


6. CONSISTENCY MAINTENANCE AND NEGOTIATION: 6. CONSISTENCY MAINTENANCE AND NEGOTIATION


What Is a TMS?: What Is a TMS? A truth maintenance system performs some form of propositional deduction maintains justifications and explains the results of its deductions updates beliefs incrementally when data are added or removed uses its justifications to perform dependency-directed backtracking TMSs are important because they deal with atomicity deal with the frame problem lead to efficient search


Architecture of TMS-Based Agent: Architecture of TMS-Based Agent The problem solver represents domain knowledge in the form of rules, procedures, etc. and chooses what to focus on next The TMS keeps track of the current state of the search for a solution. It uses constraint satisfaction to maintain consistency in the inferences made by the problem solver Problem Solver TMS justifications beliefs


Knowledge Base Integrity: Knowledge Base Integrity Stability: believe everything justified validly; disbelieve everything justified invalidly Well-Foundedness: beliefs are not circular Logical consistency: logical contradictions do not exist Completeness: a system will find a consistent state if it exists, or report failure Problems arise when knowledge is distributed


Kinds of Inconsistency: Kinds of Inconsistency Both a fact and its negation are believed A fact is both believed and disbelieved An object is believed to be of two incompatible types, i.e., two terms are used for the same object Two different objects are believed to be of the same type, i.e., the same term is used for two different objects A single-valued fact is given more than one different value; e.g., (age Bob 7) and(age Bob 8) Separate TMSs could be used for domain knowledge, control knowledge, know-what, and know-how


Degrees of Logical Consistency: Degrees of Logical Consistency Inconsistency: one or more agents are inconsistent Local Consistency: agents are locally consistent Local-and-Shared Consistency: agents are locally consistent and all agents agree about shared data Global Consistency: agents are globally consistent The RAD DTMS maintains local-and-shared consistency and well foundedness


The RAD DTMS: The RAD DTMS Each agent has a justification-based TMS Each datum can have status OUT, INTERNAL (valid local justification), or EXTERNAL. A shared datum must be INTERNAL to one of the agents that shares it When a problem solver adds or removes a justification, the DTMS Unlabels data based on the changed justification Labels all unlabeled shared data Chooses labels for remaining unlabeled data; if this fails, it backtracks by unlabeling additional data and iterating


DTMS Example: DTMS Example Client f3: afford(Xcorp) INTERNAL r3: Infer buy(?X) from query(Broker recommend(?X)) and afford(?X) INTERNAL Broker f1: afford(Xcorp) OUT f2: cash-rich(Xcorp) INTERNAL r1: Infer recommend(?X) from takeover-bid(?X) INTERNAL r1: Infer takeover-bid(?X) from cash-rich(?X) INTERNAL ? recommend(?X)


DTMS Example (cont.): DTMS Example (cont.) Client f3: afford(Xcorp) INTERNAL r3: Infer buy(?X) from query(Broker recommend(?X)) and afford(?X) INTERNAL Broker f1: afford(Xcorp) OUT f2: cash-rich(Xcorp) INTERNAL r1: Infer recommend(?X) from takeover-bid(?X) INTERNAL r1: Infer takeover-bid(?X) from cash-rich(?X) INTERNAL f3: recommend(Xcorp) INTERNAL Shared with: Client; Justification: (f2 r1 r2) recommend(XCorp)


DTMS Example (cont.): DTMS Example (cont.) Client f3: afford(Xcorp) INTERNAL r3: Infer buy(?X) from query(Broker recommend(?X)) and afford(?X) INTERNAL f4: recommend(Xcorp) EXTERNAL Shared with: Broker; Justification: ( ) f5: buy(Xcorp) INTERNAL Justification: (f3 f4 r3) Broker f1: afford(Xcorp) OUT f2: cash-rich(Xcorp) INTERNAL r1: Infer recommend(?X) from takeover-bid(?X) INTERNAL r1: Infer takeover-bid(?X) from cash-rich(?X) INTERNAL f3: recommend(Xcorp) INTERNAL Shared with: Client; Justification: (f2 r1 r2)


DTMS Example (cont.): DTMS Example (cont.) Client f3: afford(Xcorp) INTERNAL r3: Infer buy(?X) from query(Broker recommend(?X)) and afford(?X) INTERNAL f4: recommend(Xcorp) EXTERNAL Shared with: Broker; Justification: ( ) f5: buy(Xcorp) INTERNAL Justification: (f3 f4 r3) Broker f1: afford(Xcorp) OUT f2: cash-rich(Xcorp) INTERNAL --> OUT r1: Infer recommend(?X) from takeover-bid(?X) INTERNAL r1: Infer takeover-bid(?X) from cash-rich(?X) INTERNAL f3: recommend(Xcorp) INTERNAL --> OUT Shared with: Client; Justification: (f2 r1 r2) relabel recommend(XCorp)


DTMS Example (cont.): DTMS Example (cont.) Client f3: afford(Xcorp) INTERNAL r3: Infer buy(?X) from query(Broker recommend(?X)) and afford(?X) INTERNAL f4: recommend(Xcorp) OUT Shared with: Broker; Justification: ( ) f5: buy(Xcorp) OUT Justification: (f3 f4 r3) Broker f1: afford(Xcorp) OUT f2: cash-rich(Xcorp) OUT r1: Infer recommend(?X) from takeover-bid(?X) INTERNAL r1: Infer takeover-bid(?X) from cash-rich(?X) INTERNAL f3: recommend(Xcorp) OUT Shared with: Client; Justification: (f2 r1 r2)


Distributed ATMS: Distributed ATMS Agents are locally, but not globally, consistent, based on a local ATMS Agent interactions are limited to result sharing Agents communicate only their own results Agents believe only results they can substantiate locally Agents communicate inconsistent assumption sets, termed “NOGOODS,” which receiving agents use to disbelieve any results that have been obtained from the sending agent and that are justified by one of these sets [Mason and Johnson]


Principles of Negotiation: Principles of Negotiation Negotiation involves a small set of agents Actions are propose, counterpropose, support, accept, reject, dismiss, retract Negotiation requires a common language and common framework (an abstraction of the problem and its solution) RAD agents exchange DTMS justifications and class information Specialized negotiation knowledge may be encoded in third-party agents The only negotiation formalism is unified negotiation protocol [Rosenschein, Hebrew U.]


Negotiation: Negotiation A deal is a joint plan between two agents that would satisfy both of their goals The utility of a deal for an agent is the amount he is willing to pay minus the cost to him of the deal The negotiation set is the set of all deals that have a positive utility for every agent The possible situations for interaction are conflict: the negotiation set is empty compromise: agents prefer to be alone, but will agree to a negotiated deal cooperative: all deals in the negotiation set are preferred by both agents over achieving their goals alone [Rosenschein and Zlotkin, 1994]


Negotiation Mechanism: Negotiation Mechanism The agents follow a Unified Negotiation Protocol, which applies to any situation. In this protocol, the agents negotiate on mixed-joint plans, i.e., plans that bring the world to a new state that is better for both agents if there is a conflict, they "flip a coin" to decide which agent gets to satisfy his goal


Negotiation Mechanism Attributes: Negotiation Mechanism Attributes Efficiency Stability Simplicity Distribution Symmetry e.g., sharing book purchases, with cost decided by coin flip


Third-Party Negotiation: Third-Party Negotiation Resolves conflicts among antagonistic agents directly or through a mediator Handles multiagent, multiple-issue, multiple-encounter interactions using case-based reasoning and multiattribute utility theory Agents exchange messages that contain the proposed compromise persuasive arguments agreement (or not) with the compromise or argument requests for additional information reasons for disagreement utilities / preferences for the disagreed-upon issues [Sycara]


Negotiation in RAD: Negotiation in RAD Resolves conflicts among agents during problem solving To negotiate, agents exchange justifications, which are maintained by a DTMS class information, which is maintained by a frame system Maintains global consistency, but only where necessary for problem solving


Negotiation amongUtility-Based Agents: Negotiation among Utility-Based Agents Problem: How to design the rules of an environment so that agents interact productively and fairly, e.g., Vickrey’s Mechanism: lowest bidder wins, but gets paid second lowest bid (this motivates telling the truth?? and is best for the consumer??)


Problem Domain Hierarchy: Problem Domain Hierarchy Worth-Oriented Domains State-Oriented Domains Task-Oriented Domains


Task-Oriented Domains: Task-Oriented Domains A TOD is a tuple , where T is the set of tasks, A is the set of agents, and c(X) is a monotonic function for the cost of executing the set of tasks X Examples delivery domain: c(X) is length of minimal path that visits X postmen domain: c(X) is length of minimal path plus return database queries: c(X) is minimal number of needed DB ops


TODs: TODs A deal is a redistribution of tasks Utility of deal d for agent k is Uk (d) = c(Tk) - c(dk) The conflict deal, D, is no deal A deal d is individual rational if d>D Deal d dominates d’ if d is better for at least one agent and not worse for the rest Deal d is Pareto optimal if there is no d’>d The set of all deals that are individual rational and Pareto optimal is the negotiation set, NS


Monotonic Concession Protocol: Monotonic Concession Protocol Each agent proposes a deal If one agent matches or exceeds what the other demands, the negotiation ends Else, the agents propose the same or more (concede) If no agent concedes, the negotiation ends with the conflict deal This protocol is simple, symmetric, distributed, and guaranteed to end in a finite number of steps in any TOD. What strategy should an agent adopt?


Zeuthen Strategy: Zeuthen Strategy Offer deal that is best among all deals in NS Calculate risks of self and opponent R1=(utility A1 loses by accepting A2’s offer) (utility A1 loses by causing a conflict) If risk is smaller than opponent, offer minimal sufficient concession (a sufficient concession makes opponent’s risk less than yours); else offer original deal If both use this strategy, they will agree on deal that maximizes the product of their utilities (Pareto optimal) The strategy is not stable (when both should concede on last step, but it’s sufficient for only one to concede, then one can benefit by dropping strategy)


Deception-Free Protocols: Deception-Free Protocols Zeuthen strategy requires full knowledge of tasks protocol strategies commitments Hidden tasks Phantom tasks Decoy tasks P.O. A1 (hidden) A1 A2


Multiagent Frameworks: Multiagent Frameworks ABE "Agent Building Environment" from IBM written in C++ and Java, agents have rule-based reasoning and interfaces to the web (http), news groups (nntp), and email (smtp) JAT "Java Agent Template" and JAT-Lite from Stanford enables simple Java agents to communicate over a LAN via KQML JESS "Java Expert System Shell" CLIPS in Java, enables solitary reasoning agents to be constructed Voyager from ObjectSpace Inc. an Object Request Broker for Java agents Open Agent Architecture from SRI agents are based on a logic-based declarative InterAgent Communication Language, running on top of CORBA; a facilitator agent distributes tasks to other agents, with results sent to user agents


Information Agent Applications: Information Agent Applications Financial Decision Support WARREN from CMU is a system of agents for managing your financial portfolio: one agent monitors stock prices, while others monitor newswires for items about the companies whose stock you own Decision Support from Firefly, AgentSoft, Verity, and Amulet information agents that learn and adapt to users' information needs and then proactively retrieve and organize targeted information; Firefly uses collaborative filtering Information Filtering from Intel a Smart News Reader sorts and ranks newsgroup articles based on learned user preferences Hyperlink Assistance Intel's Selection Recognition Agent looks at anything copied to your clipboard and, if it recognizes a URL, email address, or date, automatically launches the right application to view the URL, or send mail, or modify your scheduler


7. REPRESENTATIVE TOOLS AND INFRASTRUCTURE: 7. REPRESENTATIVE TOOLS AND INFRASTRUCTURE


RAD: A DAI Shell: RAD: A DAI Shell RAD supports both human and computational agents, which can be organized arbitrarily. Each computational agent has knowledge representation frames for predicates and objects, including itself and other agents rules justifications reasoning mechanisms inheritance forward chaining backward chaining a DTMS used for explanation, learning, defeasible reasoning, and negotiation a communication aide domain knowledge for its area of expertise


Architectural Overview: Architectural Overview Agents interact by message-passing: they tell each other things, and ask and answer questions Agents can be anywhere that is reachable by TCP/IP or OSI Agent1 Agent2 Agent4 Agent3 (human) Agent5 Database


Agent Messages: Agent Messages Any agent can make an assertion to another agent. When agent A makes an assertion x to agent B: • Assertion x is given a justification by agent B that roughly translates to "Agent A said so." Agent A Agent B Aide A Message Buffer Aide B Message Buffer Tree Space Interface Tree Space Interface Statement, Demand Transmit Forward


Reasoning about Other Agents: Reasoning about Other Agents Each agent models other agents (including users) and databases when they are encountered: Instances of class AGENT are used to justify communicated data An agent can reason about the reliability of other agents Delphi Instance of: AGENT Reliable: Yes Unreliable: No Expertise: (Circuit-design)


Reasoning about Databases: Reasoning about Databases A (computational travel) agent might have the rule If ( travels-to (?NAME:PERSON ?PLACE) db-query(galactica hotelinv (?HOTEL ?PLACE)) unless( home-town(?NAME ?PLACE)) ) then stays-at(?NAME ?HOTEL ?PLACE) If Joe travels to San Diego, e.g., travels-to(Joe “San Diego”) the agent will conclude stays-at(Joe “Hilton” “San Diego”) and book a room for him there. If the agent finds out that Joe has moved to San Diego, then when he travels there it will NOT conclude he stays at the Hilton and will NOT book a room there Galactica Instance of: DATABASE DBTables: (Hotels, Flights) DataModel: Relational Host: (onyx)


MCC Carnot Project: MCC Carnot Project Interoperation: any front-end should work with any back-end on any hardware or operating system incompatibilities limit interoperation needed information is often inaccessible, inconsistent, and incomprehensible! Scalability: imagine an enterprise with 1000 people, each with a PC and a local database or spreadsheet. How can these systems interoperate, and how can a manager obtain an enterprise-wide view?


Carnot Strategy: Carnot Strategy Exploit enterprise information modeling each user will relate his own database to a common, enterprise-wide ontology via a set of mappings the number of mappings needed by each user is equal to the number of concepts in his local database, independent of the size of the common ontology the mappings are applied by agents in an ESS that runs on each PC, providing communication and mediation facilities Use shared ontology to enforce semantic consistency among intelligent agents, databases, applications, and interfaces Resultant approach is distributed: not centralized mediated: not federated or composite heterogeneous scalable


Carnot Provides:: Carnot Provides: A layered architecture for the middleware to interconnect information resources and applications Tools for the semantic integration of components Advancements in distributed query processing and relaxed transaction processing, leading to new technology for decision support, workflow automation, and knowledge discovery Clients Servers Middleware Legacy HW & SW Semantic Services Task Distribution Support Services Communication Services Carnot


Creating Semantic Mappings: Creating Semantic Mappings Cognition Universe of Discourse 1 Conceptual Schema CASE Tool Interface Application Database use generate Cognition Conceptual Schema CASE Tool Interface Application Database use generate Universe of Discourse 2 MIST


Ontologies and Articulation Axioms: Ontologies and Articulation Axioms TransportationDevice Train Vehicle Boat Truck Automobile Jeep DB1 id make Car DB2 no model Auto Application 1 Interface 1 Common Ontology Articulation Axiom 1 Articulation Axiom 2 Articulation Axiom 3 Articulation Axiom 4


Topic Trees, Ontologies, and Database Schemas: Topic Trees, Ontologies, and Database Schemas MiG29 People Terms Mikoyan ivan artem mikoyan r73 mig29 sirena Weapon Person Number Air Sea Fighter Bomber speed weight price designer expertIn Person DOB Specialty Fighter Speed Weight Price


Semantic Translation: Semantic Translation Application 1 Application n Common Enterprise-Wide View Agent for Application Agent for Resource User Agent for Application Agent for Resource Agent for Resource


Logistics Information Management: Logistics Information Management Multiuser SAAS DB Queries Information Data SQL AMDF DB GLAD DB . . . Multiple Domain Ontologies Multiple Information Resources


Logistics Domain Ontology: Logistics Domain Ontology name name name name name type type niin fsc-code quantity class Army Brigade Main-Support-Battalion isa isa isa isa isa isa is-part-of is-part-of supports maintains stored-in located-in has-as-part maintains consist-of Stock Storage Mobile-Storage Stock-Item Geographic-Area Direct-Support-Unit Forward-Support-Battalion Military-Unit War-Reserves ress-code is-authorized-to quantity


Logistics Query Editor: Logistics Query Editor “How many depot level repairables are in the 2ID main support battalion?” IS: Log C7 DoIt RD: None Misc Stock Item class = 9 type = DLR quantity = ?.request.? niin = ?.request.? is part of Stock is maintained by Direct-Support-Unit activity address code = ?.request.? is part of Division name = 2ID


I3 Mediation Technology for LFW: I3 Mediation Technology for LFW Information Sources Use mediators and agents to: access heterogeneous databases - increase extensibility and scalability support ad-hoc queries respond to conceptual queries - query relaxation manage information by exception - approximate consistency actively provide monitors and alerts GTN TAV STAMIS Domain Query Building Interface GLAD MasterMind MIST Query Server xxxxxx xxxxx Query Relaxation CoBase Information Integration & Mediation UniSQL SIMS Info Sleuth


CORBA Services: CORBA Services


Persistence: Persistence Objects may be stateless have an internal state For those that have a state, persistence means that the client finds them as it left them, unless the object was shared, in which others may have modified it deleted, in which case its state is undefined


Persistence: Persistence Typically persistence of objects presumes an underlying persistent storage, e.g., files relational databases object databases Certain operations come up naturally store checkpoint restore (or revert)


Persistent Object Service: Persistent Object Service The POS standardizes how an object's persistent state is stored and retrieved. The variations the POS must handle include whether control of the storage is automatic or by the client whether control is over individual objects or sets (or graphs) of them what underlying systems are available what is the granularity of the underlying operations The POS seeks to provide a persistence service with an IDL interface. The POS might be superfluous if an OODB is available.


POS Architecture: POS Architecture PID: ID for storage of objects, but not for use in dispatching messages. PO (persistent object) or Client control persistence POM: Manages use of different PDSs, etc. PDS: persistent data service coordinates actual persistence operations Datastore: file system or DB Client PO Protocols PDS Data store POM PID


Control Paradigms: Control Paradigms The connection paradigm makes the object's dynamic and persistent states mirror each other: connect: dynamic and persistent states are the same which way does info flow on reconnect? disconnect: persistent version holds on to its state at time of disconnect The functional paradigm provides operations to explicitly move information between dynamic and persistent states: store restore Both support zapping a PID through delete PO, POM, and PDS implement the above 5 operations


Protocols: Protocols Currently 3 protocols are specified, but more might be added: Direct Access: gives access to attributes on an object in the usual manner ODMG-93: OODB standard Dynamic Data Protocol: refers to the entire object through its PID, and moves it atomically Lower-level data access APIs are borrowed from X/Open. These allow access to file systems and relational databases for use as datastores in POS


Externalization: Externalization The Externalization Service provides a means to represent an object as a standardized stream for storage and communication. Two operations: externalize: object => stream internalize: stream => object The output representation is permanent but not amenable to processing (hence not like POS). The above operations can take arbitrarily long In conjunction with the Relationship Service (entity-relationship diagrams), we can affect groups of objects


Streams: Streams ES is built on the Stream object Clients invoke operations on Stream, which lead to print and parse of objects On externalization, the type is recorded On internalization, the type of the object is used to invoke its factory object Thus an object type must support Lifecycle Service Identifiable Object interface from Relationship Service Streamable and StreamIO interfaces Standard formats exist to capture the basic data types, etc.


Naming Services: Naming Services Essence: bind names to objects (their references) find objects given their names Key issues: Representing names Making NSs federate, i.e., share names so that objects in different domains can be found-key to interoperability


Names: Names Lots of naming conventions exist, e.g., Unix DOS OMG defines a name as a sequence of name components, each component being an identifier and a type field. The last component binds to an object reference All preceding components define successive naming contexts It is claimed this can map to any existing naming convention (IMHO, should work for any (tree-based) hierarchical naming scheme) NS accepts a compound name wherever it accepts a name


NS Operations: NS Operations A naming context corresponds to a directory of objects. The above scheme supports 3 main operations bind: binds the last component of a name to the given object bind_context: just like bind when the object is of type Naming Context (so it can be internally processed by the NS) resolve: retrieves the object reference corresponding to a particular name Some additional operations exist, e.g., unbind


Trader: Trader Whereas the name service corresponds to traditional white pages, the trader corresponds to the traditional yellow pages combined with a mail-order catalog. YP to discover objects that meet some criteria Mail-order to dynamically invoke operations on them (formally through the DII)


Trader Usage: Trader Usage Typical mode of usage: VAR implements browser using OMG Trader API Client invokes browser API--without necessarily having to learn the OMG API--to show objects to user End-user sees objects in appropriate UI, and chooses some Client invokes selected objects


Trader Service Setup: Trader Service Setup Server objects register service offers with local trader-called export in the ISO std. Export involves offer properties: object reference for server what how how much List of properties is domain-specific Traders should federate with other traders to find remote information


Event Service: Event Service Generalization of techniques for maintaining referential integrity One way to maintain constraints is to propagate changes-in case of autonomy, this means to notify other objects of changes in a given object. Notification is independent of whatever else the object is doing-thus notification is a clear candidate for implementing separately. Turns out notification requires communications of the form not supported by plain CORBA invocations, so they are encapsulated in a separate Event Service


ORB Communication: ORB Communication ORB communications are of 3 kinds: synchronous: sender blocks until receiver responds asynchronous: (one-way) sender doesn't wait for receiver deferred synchronous: sender proceeds independently of the receiver, but only up to a point Execution is best effort, at most once With idempotent operations, more than once would be OK, but with nonidempotent operations it wouldn't


Event Communication: Event Communication ORB communication satisfies 3 properties senders select the receiver there is a unique receiver messages are not queued: communication fails if receiver is unavailable Event Service relaxes the first two Pure message-based ES relaxes all three (receiver pulls messages from queue) These are still implemented using CORBA as the underlying transport Also allows broadcast and multicast Basic Operation Recipients register with ES to receive certain events Events are shipped as they occur Senders have no knowledge of recipients’ identities


ES Architecture: ES Architecture Event channels decouple communication Each event from a supplier is sent to every consumer multiple channels can be defined to limit message traffic and interruptions Amount of storage for notifications is a QoS issue, left to implementers Supplier Supplier Event Channel


ES Interfaces: ES Interfaces Operations push, pull, try_pull (all available at both ends) interface PushConsumer { void push (in any dat) raises (disconnected); void disconnect_push_consumer();} interface PushSupplier {void disconnect_push_supplier();} interface PullSupplier { any pull() raises (disconnected); any try_pull(out Boolean has_event) raises (disconnected); void disconnect_push_supplier();} Additional features The object that creates a channel owns it use to limit access create private channels Channels can be typed


Transaction Services: Transaction Services OTS supports OnLine Transaction Processing ACID transactions: flat or nested Wrapping existing systems Interoperability of various shades, e.g., single transaction over ORB and nonORB apps access to nonobject programs and resources access to objects from existing programs coordination over the above Network interoperability: >=1 OTS over >=1 ORB (4 cases) Flexible transaction control: client determines if op is part of transaction client can invoke trans and nontrans objects objects can specify transaction behavior of interfaces TP monitors: concurrency and recovery across processes


OTS Components: OTS Components Recoverable objects: owns its data implements failure recovery upon recovery from failure, restores its state from stable storage if in the scope of a transaction, participates in atomic commit protocol with OTS responds to commit/rollback messages Transactional objects: those affected by being in the scope of a transaction responds to commit/rollback messages either owns data or refers to a recoverable object Recoverable is a subset of Transactional. Transactions execute within the scope of begin and commit or rollback. ACIDity is guaranteed only for operations on transactional objects. 2PC


Transaction Contexts: Transaction Contexts The ORB is transaction-aware, a deviation from the typical goal of ignoring the content of “applications” detects begin and end transaction inserts begin and end for each operation context is used by transactional objects R: may force rollback C: participates in transaction completion Transactional object client Op Op Object Transactional Service Transaction Context Begin/End Resource Recoverable object C R,C Registers resource R, not C


CORBA Facilities: CORBA Facilities Info Mgmt: storage, retrieval, encoding, exchange Task Mgmt: workflow, agents, rule mgmt, automation Vertical facilities depend on industry groups in their domains Application Objects Object Request Brokers Healthcare CORBA Facilities Vertical Facilities UI Info Mgmt SystemsMgmt Task Mgmt


Distributed Component Object Model (DCOM): Distributed Component Object Model (DCOM) COM is an ORB; it provides an object standard and a common method of inter-ORB communication using OLE. DCOM distributes this across platforms Client Application In-Process Object Local Object Remote Object Client Process Local Object Local Object Stub Stub Local Server Remote Server (DCOM) RPC LRPC


Jini: Jini


Jini Architecture: Jini Architecture Jini extends Java from one machine to a network of machines Jini uses Java Remote Method Invocation (RMI) to move code around a network Jini provides mechanisms for devices, services, and users to join and detach from a network


Jini Services and Protocols: Jini Services and Protocols Service Provider (printer) Lookup Service Client (digital camera) Service object & attributes Service object & attributes Service object & attributes 1. discovery 2. join 3. look up 4. invoke


Jini as an Agent Architecture: Jini as an Agent Architecture + Jini provides two-phase commit for transactions + Clients have leases on services for specific duration + Lookup services can be arranged hierarchically - Lookup service requires exact match on name of Java class (or its subclass) - Agents (clients and servers) exchange code via RMI


8. SYNTHESIS: 8. SYNTHESIS


Distributed Web Applications: Distributed Web Applications Example: suppose you want to sell $1000 cameras over the web, debit a credit card, and guarantee next-day delivery Your application must record a sale in a sales database debit the credit card send an order to the shipping department receive an OK from the shipping department for next-day delivery update an inventory database Problems What if the order is shipped, but the debit fails? What if the debit succeeds, but the order was never entered or shipped?


Solution for Closed Environment: Solution for Closed Environment Transaction processing (TP) monitors, such as IBM’s CICS Transarc’s Encina BEA System’s Tuxedo will ensure that all or none of the steps are completed, and that systems eventually reach a consistent state But what if user’s modem is disconnected right after he clicks on OK? Did order succeed? What if line went dead before acknowledgement arrives? Will the user order again? The TP monitor cannot get the user into a consistent state!


Solution for Open Environment: Solution for Open Environment Server application could send email about credit problems, or detect duplicate transactions Downloaded Java applet could synchronize with server after broken connection was reestablished, and recover transaction; applet could communicate using http, or directly with server objects via CORBA/IIOP or RMI If there are too many orders to process synchronously, they could be put in a message queue, managed by a Message Oriented Middleware server (which guarantees message delivery or failure notification), and customers would be notified by email when transaction is complete.


Microsoft Middleware Approach: Microsoft Middleware Approach Windows Client Microsoft Message Queuing / Microsoft Transaction Server SQL Server The Enterprise COM Transaction Integrator Distributed COM (transport layer)


Slide249: Sun Middleware Approach Web Browser JavaBeans Enterprise JavaBeans Server Java Database Connectivity Oracle Remote Method Invocation/Internet Inter-ORB Protocol (transport layer) Sybase IBM


III. Personal Information Agents: III. Personal Information Agents


Personal Agent Technology at IBM: Personal Agent Technology at IBM Web-Browser Intelligence agent software that gives your web browser the intelligence to remember wherever you've been on the web and what you found there, and can help you recall any word on any page that you've visited MemoryAgent Knowledge Capture learns what people know and builds a knowledge base incrementally while people do their normal jobs Virtual Consultation lets people consult the knowledge of others without speaking to them in person


Personal Agent Technology at Microsoft: Personal Agent Technology at Microsoft Development of social user interfaces based on life-like computer characters that can interact and build a rapport with a user. The characters may be assistants or used within interactive entertainment scenarios Incorporating speech recognition, natural language understanding, and conversation (or discourse) management into a user interface to allow spoken conversation with a computer agent. An example of this is Persona: Conversational Interfaces Reactive 3D-animation including complex animated behavior, real-time specification and synchronization of various time-based streams


Agents and Tools from AgentSoft Inc.: Agents and Tools from AgentSoft Inc. AgentSoft's Web macros can be used to automate Internet and intranet jobs For example, LiveAgent Pro makes it easy to create scripts that gather information from all over the Web


Agent Projects at MIT: Agent Projects at MIT Amalthea - ecosystem of evolving information-filtering and discovery agents that cooperate and compete in markets Butterfly - an agent that samples 1000s of groups and recommends ones of interest Expert Finder - agents who help find experts that can assist people with problems Friend of a Friend Finder - a network of agents that enables using social networks to get answers to personal questions Kasbah - a multiagent system that helps people transact goods Letizia - a user interface agent that helps a user browse the web by learning the user’s interests and scouting ahead Mobile Agents for Routing Discovery - mobile agents that map dynamic network topologies


Agent Projects at MIT: Agent Projects at MIT PDA@Shop - mobile agents on handheld computers for point-of-sale comparison shopping Remembrance Agents - proactive just-in-time memory aids that use a person’s current environment to recommend information Straum - representing a person’s Internet presence by creating an ecology of distributed agents Tete-a-Tete - agent-mediated integrative negotiation techniques for online merchants to differentiate their wares Trafficopter - a decentralized self-organizing network of agents to collect and communicate traffic information Yenta - an agent-based system that finds clusters of people with common interests


Agent Projects at MIT: Agent Projects at MIT Calendar Agent - an agent that learns a user’s calendar scheduling rules and preferences via observations of actions and via direct feedback Challenger - a multiagent system that performs completely distributed resource allocation of CPU time Maxims - email filtering using collaborating agents


Agent Project at University of Tromsoe: Agent Project at University of Tromsoe ViSe, the “virtual secretary” project Phase 1: agents focus on three secretarial tasks: local information filtering (e-mail, news and diary); global information filtering (file retrieval and WWW); and, user environment personification Phase2: agents can replace human secretaries for miscellaneous tasks, or act as expert consultants to assist humans. Individual ViSe2 agents have limited knowledge and problem solving capabilities, so they cooperate with each other to solve problems. We have focused on the development of a twin-base agent modeling approach for ViSe2 agents to model and reason the activities of each other, and thus efficiently locate peer agents for cooperation


Agent Technology at NASA: Agent Technology at NASA


Agent Technology at NASA: Agent Technology at NASA


Agent Technology at NASA: Agent Technology at NASA


Agent Technology at NASA: Agent Technology at NASA


Other Agent Projects: Other Agent Projects University of Tulsa is working on intelligent distributed scheduling, and multiagent learning and adaptation Societies of Computation (SoC) is a research project at the University of Karlskrona/Ronneby in Sweden that studies agent technologies for industrial applications Ishida Laboratory at Kyoto University conducts basic research on multiagent systems. One interesting system is AgenTalk, a coordination protocol description language for multiagent systems The Autonomous Mobile Robotics Lab at the University of Maryland College Park has several projects that involve the intelligent control of goal-based robotics and motion planning UMBC Laboratory for Advanced Information Technology U. Washington softbots research group


Other Agent Projects: Other Agent Projects CWRU Autonomous Agents Research Group UMASS Distributed Artificial Intelligence Laboratory UNH Cooperative Distributed Problem Solving Research Group USC Soar Project Agent Projects at HCRL (Chicago) Stanford Nobotics Group Michigan Distributed Intelligent Agent Group - agents for digital libraries Intelligent Web Agents / Houston (IWAH) (Research Institute for Computing and Information Systems - University of Houston) Intelligent Autonomous Software Agents for Virtual Environments and other areas of telematics at the Austrian Research Institute for Artificial Intelligence


Other Agent Projects: Other Agent Projects MAS Research at Vrije Universiteit Brussel (VUB) Distributed Artificial Intelligence at the Dept of Information Engineering of PARMA University Knowledgeable Community Project (Nishida Lab.) DAI Research Unit at QMW Electronic Engineering Department specializes in building real-world multiagent systems Multi-Agent Systems Research Group at Université de Laval CALVIN : Communicating Agents Living Vicariously In Networks - KSL (NRC - CNR) The Multi-Agent Systems Group of the University of Maastricht DAI at Geneva University Hospital HUJI DAI group


Selected Applications of Information Agents: Selected Applications of Information Agents WARREN from CMU is a system of agents for managing your financial portfolio: one agent monitors stock prices, while others monitor newswires for items about the companies whose stock you own Decision Support from Firefly, AgentSoft, Verity, and Amulet: information agents that learn and adapt to users' information needs and then proactively retrieve and organize targeted information; Firefly uses collaborative filtering Information Filtering from Intel: a Smart News Reader sorts and ranks newsgroup articles based on learned user preferences


Other Applications: Other Applications Sainsbury’s Supermarkets (UK) simulates customers with agents Sydkraft (Sweden) controls electricity distribution HealthMagic (USA) reminds patients of prescriptions and appointments France Telecom and Deutsch Telekom diagnose circuit faults and route message traffic Siemens (Germany) provides personalized telecom services Amazon and Barnes & Noble help customers purchase books on-line US Postal Service includes smart-card agents on packages to track deliveries University of Michigan auctions access to information for digital libraries Raytheon/TI sensors cooperate in target detection


Future Applications: Future Applications Information gathering, presentation, and management in large, heterogeneous, open environments: Internet and intranets Energy distribution and management Electronic commerce Telecommunications Smart vehicles and smart highways Inventory management and logistics Smart houses and buildings Active, distributed, and intelligent data dictionaries containing constraints, and constraint enforcement business rules, and rule processing business processes, and process enactment business semantics, and semantics resolution Cooperative mobile sensing Software engineering: Interaction-Oriented Programming Distance learning


Materiel Management: Materiel Management Distributed, autonomous agents enable Robust inventory control Decentralized logistics based on a “Commuter” approach


The Logistics Problem: The Logistics Problem Efficiently and rapidly moving large quantities of equipment, personnel, and supplies is a massive problem in planning and scheduling Current solutions to this problem are centralized and top-down, based on hierarchical decomposition Such solutions are extremely complex unable to deal with unforeseen delays and breakdowns unable to take advantage of synergism among tasks susceptible to single-point failures difficult to change once started!


The USC Approach:a “commuter” paradigm: The USC Approach: a “commuter” paradigm Imagine that each item of materiel is an intelligent agent whose sole objective is to reach its assigned destination. Just like a person commuting to work, this agent would dynamically decide its means of conveyance contend for storage and transportation resources avoid or resolve conflicts with other agents make local decisions as it wends its way through a distribution network


Agent-Based Decentralized Logistics: Agent-Based Decentralized Logistics


Hardware/Software Architecture: Hardware/Software Architecture Each item of materiel would have a "smart card" containing a mechanism for communicating locally and globally a reasoning engine a knowledge base with information about routes, conveyances, and ways to resolve conflicts its objective, priority, needs, and relationships to other items Each part of the distribution network would have a scanner to interrogate and command the items


Agents Communicate via LEOS: Agents Communicate via LEOS


Technical Challenges: Technical Challenges Setting-up a deployment centralized planning is still required to assign objectives, priorities, and responsibilities to the items Controlling a deployment: maximize responsiveness and minimize resource usage a market approach would allow items to compete fairly and intelligently, while cooperating altruistically when appropriate items would continually and optimally replan during execution Monitoring a deployment intelligent items would be able to state when they might reach their destinations, not just where they are at the moment


Environmental Data Exchange Network (EDEN): Environmental Data Exchange Network (EDEN)


EDEN: EDEN Construction and operation of EDEN presupposes The construction and maintenance of large ontologies involving cooperative efforts by several individuals adapting to improvements in information resources, while allowing older resources and techniques to coexist The scalable application of mediators involving large numbers of computational agents to act concurrently, yet cooperatively Capturing the semantics of analysis tools declaratively and uniformly


CaseStudy:Agents in Healthcare Intranet: CaseStudy: Agents in Healthcare Intranet


Business Opportunities in Healthcare Process: Business Opportunities in Healthcare Process


Disease Management Infrastructure - Dataflow Diagram: Disease Management Infrastructure - Dataflow Diagram Revise Treament Plan physician may make revisions to patient’s treatment plan changes motivated by lack of progress on care guidelines changes result in new care instructions to caregiver changes also result in new directives for agents. Revise Protocol physician may make revisions to the defined protocol based on new studies or personal empirical observations. Protocol management system would need to suport ability to modify protocol definitions.


Disease Management Infrastructure - Dataflow Diagram: Disease Management Infrastructure - Dataflow Diagram Compliance Agent a general type of agent structure tasks are defined by the prescribed care guidelines in patient’s Treatment Plan agent monitors for compliance events, matches observed data against expected results agent intervenes by notifying caregiver and/or physician in event of non-compliance. Non-compliance events non-compliance inferred due to absense of data in prescribed amount of time. non-compliance inferred due to data readings outside of target ranges.


Medication Compliance Agent Interactions: Medication Compliance Agent Interactions Agent interactions captured and designed using UML Use Case analysis to identify and organize specific interagent transactions Each transaction further decomposed into Sequence diagrams Each Sequence diagram represents a specific behavior scenario that the agent must follow Agent must manage multiple interaction sequences one for each prescribed medication for which patient has an entry in their Treament Plan agent manages objects for each active prescribed medication


Prescribed Medication Lifecycle Model: Prescribed Medication Lifecycle Model


Prescribed State Model : Prescribed State Model


Prescription Compliance Scenario: Prescription Compliance Scenario AMA -> MCA: new data AMA detects event, finds out the patient, finds the appropriate agent AMA wakes up patient’s MCA MCA: determine next task MCA checks Treatment Plan for new prescribed medication MCA -> Timer agent: wake me up later if I don’t get compliance data AMA -> MCA: new data MCA gets new HealthRecord entry MCA matches medication entry against prescribed medication MCA writes Compliance Record


Prescription Compliance Scenario: Prescription Compliance Scenario AMA -> MCA: new data AMA detects event & wakes up patient’s MCA as before MCA: determine next task MCA checks Treatment Plan for new prescribed medication MCA -> Timer: wake me up later Timer -> MCA: timeout MCA wakes up and checks what event the timer is for MCA recognizes timeout, writes to Compliance Record MCA sends notification message to caregivers and/or physician If reminder count < threshhold, Then send reminder to caregiver Else send alert to physician


Interaction-Oriented Software Development: Interaction-Oriented Software Development Active modules, representing real-world objects Declarative specification (“what,” not “how”) Modules that volunteer Modules hold beliefs about the world, especially about themselves and others


Research Trends in CIS: Research Trends in CIS Social behavior: organizational theory and open systems—Hewitt, Gasser, Castelfranchi Learning—Shaw, Sen, Mitchell, Weiss Formal Methods—Singh, Wooldridge, Jennings, Georgeff Negotiation—Sycara, Rosenschein, Mueller Multiagent-Oriented programming—Huhns, Singh Enterprise integration—Sheth, Papazoglou, Woo


Lessons: Lessons Most real-world problems are mundane A moderate application of AI can help significantly Interfaces and database systems deserve much attention Much effort expended in discovering the specification Don’t mess with autonomy Do it locally Should try to integrate new technology into existing systems, and with standard techniques be problem-driven, not solution-driven


Open Problems in Agent Technology: Open Problems in Agent Technology Design rules for cooperative systems Workflows Ontologies Security concerns in open environments Scaling to millions of agents User interfaces to heterogeneous resources to acquire resource constraints to access information to control workflows Shared ontology maintenance Change management


To Probe Further: To Probe Further Readings in Agents (Huhns & Singh, eds.), Morgan Kaufmann, 1998 http://www.mkp.com/books_catalog/1-55860-495-2.asp IEEE Internet Computing, http://computer.org/internet DAI-List-Request@ece.sc.edu International Journal of Cooperative Information Systems International Conference on Multiagent Systems (ICMAS) International Joint Conference on Artificial Intelligence International Workshop on Agent Theories, Architectures, and Languages (ATAL) IFCIS Conference on Cooperative Information Systems