ALP-CoABS Technology Integration Design Document

DRAFT 1.0


Frank Manola
Object Services and Consulting, Inc.
February 28, 1999


Contents

Executive Summary

The DARPA ALP program has developed a federated architecture, based on units called clusters.  This approach has demonstrated a scalable logistics architecture that shows how to wrap existing logistics organizations and functions, allowing them to act together in a supply chain to quickly generate a logistics plan that can be continuously evolved in response to changes in an operational plan.  The ALP program has identified a number of architectural challenges that are related to agent technology.  The DARPA CoABS program has focused its efforts on a general agent architecture that supports the concept of a Grid.  The Grid establishes a support environment for agents to share resources and middleware services.  CoABS is also establishing an external relationship with evolving middleware and agent standards efforts.

The two programs have much to offer each other.  ALP offers CoABS a flexible agent construction technology based on clusters and plug-ins, a federated cluster architecture, and a maturing application testbed in which to test agent communication and control ideas.  CoABS offers ALP a collection of agent technologies, an interoperability architecture for tying them together, and a connection to emerging object, Web, and agent standards.  This report is the initial draft, based on one month of activity, of a design document intended to identify detailed technology integration opportunities for ALP and CoABS.  The report currently identifies apparent relationships between aspects of the two programs, and those areas that appear to be the most promising ones for interaction.  As work progresses, the report will define specific plans for program interaction.  It is important to note that, in identifying specific areas for potential interaction, there is no implication that one program is "ahead" of the other;  the technology transfer between the two programs will be two-way.  In addition, technology transfer may be at multiple levels (e.g., at the level of how to apply Java technology in implementing various agent-level capabilities, or at the level of agent and architecture concepts built on this technology).  In addition, in some cases, the two programs can work in parallel, in cases where neither program is directly addressing the area.

ALP has naturally focused on the logistics application, but its architecture is in many ways generic.  An ALP cluster is essentially a generalized agent shell, designed to provide a convenient way to define agents for individual organizations, and specialize them with/for their distinct functions.  The ability to define specialized plugins for task expander, allocator, and assessor components helps modularly specialize these distinct functions of agent behavior (e.g., agents can use the same approach for task expansion and distinct approaches for allocation, and vice versa).  Plugins are JavaBeans, and are dynamically loadable.  ALP has defined a highly flexible Logical Data Model as a common representation for LogPlans and other data.  LDM permits the easy creation of object representing new kinds of "things" by adding units of behavior through delegation and prototyping.  The ALP cluster is in some sense the agent correspondent to the LDM, in terms of creating a flexible agent/object concept.  A plugin represents behavior, and hence is like an object method (or collection of them).  Plugins allow the addition of arbitrary behaviors to a give agent for expanding tasks (deciding how to approach them), allocating resources to do them, assessing results, and accessing data.

CoABS is focusing on more generic agent technology, and is concentrating primarily on general issues related to semantic heterogeneity, open source information, interoperability and brokering, and control protocols in open agent architectures. In particular, CoABS is pursuing a Grid architecture which supports heterogeneous agents and data sources, the dynamic discovery of those resources, and the flexible establishment of relationships between them, based on explicit descriptions of agent capabilities and requirements.  CoABS is also developing a wide range of other agent technology, e.g., dealing with replication, reliability, and consistency issues.

Generally speaking, CoABS and ALP appear to represent different points on a spectrum of agent-based systems. For example, as in the ALP logistics model, real organizations are going to have business rules, standard operating procedures, policies, etc., and it is necessary to be able to capture these, as ALP does (and as expert systems do).  In ALP, these business rules appear to define, e.g., which clusters a given cluster interacts with, and which plug-in capabilities a given cluster uses.  These ALP business rules, together with metadata (resource descriptions) about cluster and plugin capabilities, appear to be embedded in clusters (either in workflow templates the plugins use, or in rules the components use to dispatch work to the plugins). Similarly, mappings between external data sources and systems and ALP's "vocabulary" (represented by the Logical Data Model) appear to be embedded in plug-ins which wrap those systems.  However, more general applications and environments require the ability to dynamically discover new resources, and establish relationships with them (e.g., to deal with resources not originally known, or for which there was no original need), and in general to deal with a greater degree of heterogeneity.  CoABS is attempting to address such issues.

On the basis of our initial investigation, specific areas in which technology interchange should take place appear to be as follows:

ALP to CoABS

CoABS to ALP Further details of these potential interactions are provided in the following sections of this report. The first section is a listing of ALP-CoABS common architectural issues, together with information on related CoABS projects. These lists are preliminary, and should be regarded as subject to change based on further work.  In particular, the association of specific projects with specific issues is tentative at this time.  These associations will be made more concrete as work progresses.  The second section is a list of CoABS project summaries, and relationships to ALP issues.  Again, these lists and relationships are preliminary.  As work progresses and associations of projects and issues are validated, this information will be presented in a matrix form.

It should also be noted that a number of aspects of the CoABS NEO TIEs are similar to the sorts of operations performed in ALP (the NEO scenario involves both operations and logistics planning):

ALP could be used as a planning system in a CoABS TIE to experiment with interoperation of ALP and other systems (e.g., systems doing operations planning).  Two-way interactions could also be investigated in such a TIE, such as developing plugins as wrappers of CoABS capabilities (possibly involving the development of more generic plugins), and registering ALP (or individual clusters, communities) with a CoABS trader/matchmaker.  Integration of trading functionality into ALP (possibly using a plugin-wrapped CoABS trader) would be a further step in such an experiment.
 

ALP - CoABS Common Architectural Issues

(Original issues list: Craig Thompson, Common Architecture Issues related to CoABS and ALP, compiled based on the ALP Workshop held in Tampa on 8-10 December 1998).

The ALP architecture needs to evolve to meet its FY99 and FY00 objectives of connecting to C2 execution environments and real data sources, supporting alternate worlds and contingency monitoring, interoperating with other systems (secret or allies or other logistics systems) and scaling to 100s of sites. This is a listing of some of the important ALP architectural issues that need resolution within the next six months and that are related to parallel CoABS agent architectural concerns.

For each issue, a title is given, followed by a brief description, (in some cases) other related issues, and initial identifications of CoABS projects that appear related to addressing that issue.  These lists are preliminary, and should be regarded as subject to change based on further work.  In particular, the association of specific projects with specific issues is tentative at this time.  These associations will be made more concrete as work progresses.  The issues are not meant to be orthogonal, and are highly interrelated.  In some cases, a generic issue is identified (e.g., dealing with heterogeneous agents and systems), and technologies that may be motivated by that issue are identified as separate issues (e.g., ontologies, Agent Control Languages, trading, resource descriptions).

architecture mapping - mapping between the ALP cluster architecture and other (more "conventional") agent architectures and Grid concepts.  The benefit would be to identify missing features of each kind of architecture and see how to augment each.  Examples of features in conventional agent architectures would be such things as Agent Communication Languages, trading (yellow pages) services, ontology support, and OMG-like services (transaction, query, etc.).  Examples of features in ALP would be plugins and the LDM.  Value to ALP could include augmentation to support additional heterogeneity, ability to more easily interoperate with these other agent (and object) architectures.  Value to CoABS could include more flexible agents via plugins, identification of Grid interfaces for ALP interoperability.

heterogeneous agent/external system interoperability- Interoperability between different multiagent systems and external systems (e.g., distributed object systems, databases, simulations, the Web).  ALP must wrap existing data sources, logistics systems, interoperate with ALP systems at different security levels, with logistics systems from suppliers (CLS = contract logistics support, issue of fairness in marketplace, comparison shopping, eBrokers) and host nations, and other agent systems being developed by DoD.  A view of ALP as not just a fine grained architecture but also an interoperability architecture with migration paths and coexistence relations to existing logistics planners is probably going to be important.  Moreover, interoperability not just with existing legacy but new developments is worth considering now:  the Common Schema/ALP relationship, CoABS/ALP relationships, and ALP/electronic commerce relationships are cases in point.  Note that ALP already has to interoperate with some agent-based systems, and will have to interoperate with other agents in the C2 world.  Cast directives in ACL?  Can a more formal external interface for clusters be identified that would enable clusters to interoperate even if they didn't have the internal structure of clusters?  Related to: explicit resource descriptions and trading;  agent communications languages; ontologies (vocabularies, namespaces). integration of emerging technologies - it is one thing to port from Voyager to Jini and another to understand how to implement ALP on a changing technology base that includes not just Jini but Enterprise Beans and other component protocols, XML/RDF, HTTP-NG, OMG/JTF services, all of these and future ones.  Some unifications of Web-object-agents-clusters are needed.  Both ALP and CoABS can benefit from such work. Examples include XML as data and message representation, RDF as ontology representation. logical data model - what extensions are needed for the current ALP LDM to support behavior (and possibly rules)?  would LDM be useful beyond ALP?  how does it map to other data models?  What extended concepts of identity are needed to deal with time-varying objects/clusters/agents, replication, and aggregation?  Does LDM need to be truly object-oriented (including actual methods/behavior), or can it suffice as a semistructured data representation (could XML be used?  How to associate/attach any required behavior if so?).  How should LDM be mapped to more conventional object models?  Related to: agent/cluster standards, ontologies. ontologies - how do ontologies (or simpler variants to deal with resource descriptions, multiple vocabularies used in interoperating systems) fit into ALP?  The LDM appears to also define a common vocabulary for all clusters.  How to integrate multiple vocabularies and mediator/translator components (other than simply wrapping external systems).  Ontology work from agent world, RDF from Web;  clusters are said to use grammars tailored for specific cluster communities.  Related to:  heterogeneous agent/external system interoperability, agent communication language. information management technology -  a fine-grained, generic information management framework is needed for connecting data sources, and efficient transformation of data between functional perspectives and different levels of granularity.   Integration of data management plugins in ALP and information agents in CoABS.  Related to:  heterogeneous agent/external system interoperability; ontologies, resource descriptions and trading (for data mediation). open rules, constraints, policies - A representation for rules, constraints, policies, and assumptions in ALP clusters and plugins (and agents) that is open and supports dynamic change.  ALP uses rules in components for dispatching work to plugins and workflow templates in plugins for task expansion.  An open rule representation would allow rules to be changed dynamically to adapt clusters/plugins/agents to new requirements, capture policies and user preferences, and deal with system upgrades.  It would also allow rules, constraints, assumptions, etc. to be dynamically inspected (and possibly changed) by authorized users.  Rules can also be used as a representation for notification requests, triggers, and active queries (sentinels). A generic rule processor (e.g., a CLIPS plugin) would be one approach.  Object-oriented models for rules (e.g., separate objects for events, conditions, and actions) have been defined (see OMG proposals).  Related to:  multiple Courses of Action. agent communication language - ALP clusters now communicates via both directives (explicit messages) and the shared LogPlan.  How does this translate to ACL usage (and other shared data representations) in other agent architectures?  Use of a more conventional ACL could help support cluster directive extensions and more precise definitions of the directive vocabulary (likely needed if cluster technology is applied in other domains).  What is the directive response protocol, and how generic can that be made?  At the same time, the ALP task specification notation is intended to be compatible with the Core Plan Representation from the Common Schema work;  CoABS programs need to look at these common representations, as part of examining realistic planning systems and scenarios.  Related to: ontologies. resource descriptions and trading - Different clusters/agents and plugins provide different kinds of specialist functions, e.g., local planners, schedulers, optimizers, etc.  In an open architecture, selection of the required functionality for a given task requires that agents/clusters and plugins explicitly describe their capabilities and services (provide service advertisements), and that there be a way for agents requiring services and functions to access these descriptions.  In ALP the information for selecting other clusters (and plugins within clusters) appears to be at least partially bundled into the workflows and cluster component dispatching rules.  Providing explicit descriptions (metadata) of cluster/agent and plugin functional capabilities and services, a trading function (yellow pages service) for accessing those descriptions, and protocols for interacting with the trader (both to access existing descriptions and add new ones) and selecting among available alternatives could help generalize the architecture in a number of ways (possibly used in combination with pre-assigned assets, as now), e.g., by helping to support: Related to: heterogeneous agent/external system interoperability; dynamic architecture configuration. agent/cluster configuration, adaptation, and mobility - Can plugins, possibly in a modified form, generalize and make more flexible some of the agent concepts in CoABS?  Component configurability of plug-ins and configuration management (e.g., preventing collisions from competing plug-ins).  Adaptation of cluster/agent role and function in evolving situations.   Creation of especially lightweight clusters (e.g., clusters with a distributed implementation, some components on one node, some elsewhere) for integration of low-end PDAs and devices.  Mobility of agents/clusters and agent functions/plugins (e.g., in agent/cluster adaptation, for survivability, or to support disconnected operations).  Related to: agent/cluster construction technologies. agent/cluster construction technologies - are there agent construction technologies (e.g., agent toolkits) that would be useful in ALP to make it easier to construct agents and plugins (e.g., allow domain experts to do so)?  tools to enable more rapid construction of data management plugins to interface with heterogeneous data sources?  Related to:  agent/cluster configuration, adaptation, and mobility. dynamic architecture reconfiguration - how can new organizations and systems (and their associated agents/clusters), or new relationships among them, be quickly added to and agent/cluster architecture? What knowledge is required?  Involves explicit agent rule/knowledge representations to allow any relevant information inside agents to be changed.  Related to:  agent/cluster configuration, adaptation, and mobility; resource descriptions and trading;  open rules, constraints, policies. execution monitoring - the ALP architecture needs to be extended to propagate changes back to trigger dynamic replanning.  It need to model mission phases:  force generation, sustainment, transportation, and execution  The need for continuous replanning, in keeping a plan up to date, suggests a possible role for any work in CoABS concerning guarantees of stability/convergence of these computations.  Related to: decision tracking. decision tracking -  support for tracking/tracing cluster/agent decision-making processes, e.g., to determine why a bad plan was generated so that corrections could be made.  Similar to mechanisms typically found in expert systems (and also to debugging tools).  CoABS work on control should be able to address this problem.  Requires information about agent decision processes, and an audit trail of decisions made (could possibly be bundled with recovery mechanisms).  Related to:  execution monitoring, open rules, constraints, policies. survivability, fault tolerance - agent/cluster architectures must be survivable in the face of various kinds of threats, and resilient to various types of failures.  Involves, e.g., the ability to pick alternative agents or other resources when a failure occurs, the ability to replicate resources and maintain consistency, the ability to recover state when agents fail (not just persistent state, but the state of messages sent to attached databases or systems that may not provide support for such failure modes). Relates to work on the Grid service architecture, and also to work by OBJS and others on survivability, and mechanisms for injecting ilities and Quality of Service without drastic modification of objects/agents.  Related to:   characterizing/maintaining consistency, agent/cluster configuration, adaptability, and mobility. support for disconnected operations -  In some cases, agents/clusters (or groups of them) will be temporarily disconnected from other parts of the architecture (e.g., in mobile operations, or due to intermittent communications).  The architecture should be capable of supporting this mode of operation.  This involves not only agent or component (e.g., plugin) mobility, but also support from the rest of the architecture, e.g., maintenance of message queues for disconnected agents , and procedures for resynchronizing state when the disconnected agents are reconnected.  Jini provides some relevant support.  Related to characterizing/maintaining consistency; survivability, fault tolerance; agent/cluster configuration, adaptability, and mobility. characterizing/maintaining consistency - ACID transactions are not quite the right model for plan consistency.  What are more flexible consistency models that more reasonably apply in a dynamic evolving environment such as ALP planning?  In cases where more rigid consistency needs to be maintained (e.g., among replicas maintained for load balancing or reliability) how can this consistency be maintained efficiently in a large-scale system?  How can resynchronization be done when disconnected agents or systems rejoin the architecture?  How can these mechanisms be added as required to agents/clusters or components/plugins without taking them apart or rewriting them? (There is discussion in ALP of integrating transaction functions by changing the methods in particular plug-ins;  is there a way to open up ALP to provide a way to access services without having to change all the methods, e.g., by interception of some sort?  Having to change methods to access services doesn't scale for multiple ilities).  Work exists on flexible transaction models combined with workflows;  these issues also apply to the databases updated by workflows in carrying out assigned tasks.  Related to: survivability, fault tolerance. multiple Courses of Action (alternate worlds) - bookkeeping for distributed alternate worlds needs to be worked out.  Versioning and annotation support; extended notions of identity.  Related to: characterizing/maintaining consistency . cost modeling/penalty functions - the idea of a pervasive economic model with local mapping to a standard of exchange (clusterbucks) needs refinement;  interoperability between agent systems that use heterogeneous cost models.   CoABS should look at ALP penalty function concepts. scaleability - both CoABS and ALP need scaleable architectures to meet global DoD needs.  There are a number of areas and assumptions being made about scaleablilty that need to be captured, examined, and solution approaches need to fit into the architecture.  Related to:  architecture mapping.

control issues - preventing circular chaining in planning, damping propagations; insuring visiting the log plan nodes does not mean traversing all clusters in a WAN; cluster feedback mechanisms.

planning - ALP is an architecture specializing in planning, and a number of the CoABS projects have a major emphasis in planning.  It would be fruitful for the to programs to exchange information on planning technology.  Two issues seem particularly relevant:  one is heterogeneous planning, where multiple heterogeneous planners must interact in order to solve an overall problem;  the other is an examination of the different plan representations used in the various projects as, e.g., an interoperability vehicle for planning information. resource-starved planning - a special case of planning is when multiple plans (e.g., different regional conflicts) compete for resources and require priorities and replanning.  Similar to QoS. At the computer resource level, related to decisions a Grid architecture might make in deciding when to expend cycles on continuously tweaking a logistics plan vs. other uses of the same computing resources.  (This is less relevant when systems are dedicated to specific functions (e.g., logistics), but in a grid the same systems might be taskable for multiple uses.  Related to:  planning.

user interface technology - a multi-modal user interface visualization framework is needed to allow user interaction with the system as a whole and individual agents/clusters for a wide range of purposes.

agent/cluster standards - agent-cluster interfaces, logistics object models, etc. must be documented for other communities to adopt them.  This complements the open source approach ALP is planning. A mapping of ALP to emerging agent standards from FIPA and OMG (MASIF, Trader, upcoming Negotiation specification) is needed. Related to:  architecture mapping. ALP as electronic commerce infrastructure - ALP will succeed best if its infrastructure can become the basis for how the electronic commerce and host nation communities do business (e.g., builds a user community, provides more support).  If they adopt cluster protocols, then ALP can improve its planning.  An example is the FedEx parcel tracking service. Particularly important to look at the increasing use of Web technologies (XML/EDI, WIDL, XML/RPC) in the EC community.  Related to:  agent/cluster standards.

clusters applied outside logistics - the cluster-agent architecture could also be a good model for complex societies beyond logistics (e.g., C2 and intelligence).  Can an ALP cluster handle agent tasks that don't fall under the heading of "planning" ?

micro-licenses - a flexible scheme is needed to microlicense components with purchasing being a special case.  Negotiation technology is needed to reduce time and cost of making business arrangements.  Pay-per-use logistics system.

sharing common experience and knowledge for case-based decision support -  a general agent architecture should incorporate techniques for recording information about successful activities, and using those as principles to guide other similar activities.  Related to: decision tracking; open rules, constraints, policies.


 

CoABS Project Summaries and Relationship to ALP Issues

(based on original project list: Craig Thompson, "Summary of DARPA/ISO coABS Projects," July 1998).
see coABS homepage (password protected) for full project information

1.  Cooperative control strategies

Team Leader:  An approach to mixed initiative agent team management and evaluation, Mark H. Burstein, Alice Mulvehill, Stephen Deutsch, BBN/GTE

Summary:  Facilities for human users to monitor and manage agent teams, handle problems, etc.  Ability for users to explore alternate models of team management.  TEMPLATES (Team Execution Manager and Planner for Agents by Task Editing System) is composed of monitoring agents (for monitoring agents during execution), team capabilities, plan specification and editing agents (for user interaction with agents), replanning agents, information gathering agents, and a simulation environment called OMAR, used to define requirements and measure performance and explore alternate team structures.  Agent teams interact via grid.  Will use mixed initiative planning and case-based reasoning.  Goal to evaluate tradeoffs in different styles of interaction with agents, and different agent organizations,

Potential ALP relationships:  Air Mobility Command planning is cited as a problem domain:  flight plans to satisfy transport requirements, manage resources (planes, aircrews), monitor and react to problems.  Agent teams and "planning cells" seem somewhat similar to clusters in general organization, but interact via grid.   Support agents to assist in formulation and revision of agent tasking plans may be useful as part of UI.

RETSINA:  Effective coordination of multiple intelligent agents for command and control, Katia Sycara, CMU

Summary:  RETSINA agent architecture.  Goal to cover scalable, robust and adaptive coordination and control strategies that allow large ensembles of software agents to coordinate effectively to achieve predictable and optimized overall system properties and mitigate undesirable ones, taking into consideration the evolving situation and availability of resources. The coordination mechanisms will allow both human-in-the-loop collaboration as well as multiagent coordination. Also covered:  agent control, tools for building agents, reusable agent components, infrastructure coordination tools, learning techniques. RETSINA individual agent architecture (shell) described as a "reusable "agent shell" that includes domain-independent components for representing and controlling agent functionality, so that agents can be easily produced for different types of tasks". Idea is to build agents from reusable components.  Supporting NEO TIE1 and TIE3 with various agents (e.g., route planner) and Matchmaker service (yellow pages, trader).

Potential ALP relationships:  Capability-based coordination deals with environment where agents can leave and join unpredictably, and agents have heterogeneous capabilities;  uses replication to increase robustness;   all relevant to ALP issues.  Agent behaviors are specified declaratively, which could be useful for ALP workflow templates and component dispatch rules.  RETSINA individual agent architecture (shell) somewhat resembles a cluster;  may be useful to see if this, applied to constructing ALP clusters, would enable them to be constructed faster  (can they be plugins?  or the systems that ALP plugins wrap?).   Cooperation methods are supposed to work for very large systems (millions of agents), may be useful in ALP, and should (at least) be validated against ALP.  Tool suite may be useful in constructing clusters/plugins.    Communications planning techiques for restricted communication situations might apply too.  Matchmaker as trader.

Teams of autonomous, cooperative, adaptive agents, Manuela Veloso, CMU

Summary:  The focus is on teams; the assumption is that different team members have different roles and skills.  The teams can act autonomously.  They periodically synchronize.  Supporting NEO TIE2 with simulator and Prodigy (planner).

Potential ALP relationships:  TBD

Quickset:  Robust agent-based systems incorporating teams of communicating agents, Phil Cohen, OGI

Summary:  Developing AgentTalk ACL (Agent Communication Language), plan to propose it to FIPA as a standard.  AgentTalk will contain an extensible set of communication actions with well defined semantics; a probably correct set of conversation policies and protocols; and primitives for forming and disbursing teams.  Will develop an Adaptive Agent Architecture (Quickset) that uses the AgentTalk ACL, enables agents to form teams, dynamically adapts the agent architecture to its environment (changing bandwidth), allows interoperation of agents across different manufacturers and platforms, is built on CORBA and DCOM, and allows humans to be agents in the architecture.  Supporting NEO TIE1.

Potential ALP relationships:  AgentTalk work may be relevant to extension of ALP Directives (a form of ACL).  Quickset provides sentinel agents used to monitor data sources using CQ (Continual Query) technology funded by ALP.  Technology for persistent agent identity, store and forward messages to new location, and facilitator agents to dynamically reconfigure the agent structure, potentially useful in ALP.  QuickSet architecture diagram shows CORBA bridge to ALP.  Possible mechanism to integrate ALP and other ABSs.  Distributed triggers, filtering, and monitoring technology for multiple agents (this technology looks like it could be implemented as a cluster, but appears rather centralized in this architecture;  perhaps one per society or community in ALP).

Taskable Reactive agent communities (TRAC), Karen Myers and Adam Cheyer, SRI

Summary:  Assuming a dynamically changing uncertain environment, assume the initial problem statement is high level and vague and needs successive refinement to expand into a detailed plan.  Also that nodes in the plan can cover certain constraints before replanning is needed.  And that monitoring agents monitor information sources as well as conditions of the network (resource availability, message traffic) and can take action to replace strategies if changes occur.  Builds on SRI Open Agent Architecture (OAA).  Provides a collection of OAA-based appliations, including multimodal maps, video agent, used in support of NEO TIE2.   PRS (reactive control for managing agents) used for Air Campaign Planning;  uses hierarchical task models, delegated scheduling of tasks, agent profiles;

Potential ALP relationships:  TRAC should compare their work to ALP, e.g., compare their plan model to ALP's, PRS reactive control loop compared to way clusters build and monitor the LogPlan.  Adaptable Agent Controller (AAC) could provide ideas for making ALP clusters more open (e.g., using explicit cluster metadata, explicit control strategies, agent instrumention required to support higher-level control and coordination).  Unified Messaging could help provide access to other services (Web, email, voice, fax, etc.) ALP could find useful.

Control and coordination of multiple agents thru decision theoretic and economic methods, Yoav Shoham, Stanford, Moises Goldszmidt, SRI, Craig Boutilier, UBC

Summary:  Assumption: a central command has need to distribute decision making and tasks to units that report to it (its agents).  The goal is to maximize information gathering and dissemination while taking into account safety, reliability, and robustness.  They propose modeling at two levels, micro where  individual agents can learn about other agents via explicit modeling and bayseian nets and macro where a market mechanism and game theory are the dominant mechanisms.  The CPoF is the market designer who sets the reward mechanism.  A goal is easy migration between micro and macro.  Agent for teams or dissolve them according to if interchange will be beneficial to all team members. Ilities are robust, adaptable, scalable, and distributed.

Potential ALP relationships:  The market mech here could be compared to agents that coordinate by working on a common plan representation (and with common operational semantics) as in ALP.  Can this mechanism help in evaluating alternatives for performing the same subtask?  How does their market mechanism compare to ALP use of time-phased penalties as a cost?

Multilevel coordination mechanisms for real-time autonomous agents, Edmund Durfee, U Michigan

Summary:  Preplanning permits predictability among colleagues allowing coordination to happen but gives up some autonomy and flexibility.  This project adopts a hierarchical (distributed) plan so the agent represents what it is doing simultaneously at multiple levels of detail at once.  Each plan representation is a purpose/goal, context of preconditions that must be true thruout the plan execution, body of partially ordered sets of steps including conditionals and branching, and effects (postconditions).  They use Allen's temporal logic so every primitive plan has a duration and the durations of parent plans can be reasoned about.  Agents know some plan combinations are not permitted and can avoid negative interactions, which can guide deeper search.  Agents can reason about their own plans and plans of other agents at different levels of abstraction to search for good plans.  Project describes need for an explicit hierarchical plan structure representation to be used in agent coordination;  that agents need to selectively expand and analyze portions of the plan space;  that temporal relations (and presumably other constraints) need to be propagated between levels (of detail) of the plan, and used to identify conflicts. Investigates mechanisms that agents using hierarchical plan representations can use for determining aspects of a plan that need coordination, the proper level of detail in the plan to address coordination, etc.

Potential ALP relationships:  Project should look at ALP's plan representation (as a realistic example) and ALP time-phased penalties (e.g., the nearer the task is to being executed, the harder it is to change;  a cost/market mechanism).  Can project's approaches apply to the ALP LogPlan (e.g., when coordinating with external planners like C2 planning agents)?  Architectural issue:  how can outside agent get access to ALP LogPlan?  (interface like ALP's UI agent?)  How does their approach scale when plan is distributed, as in ALP (centralized plan not as scalable)?  Approach could also be tested against plans as complex and dynamic as those ALP produces.

Agents for Plan Management, Steve Minton and Craig Knoblock, USC/ISI

Summary:  This project is about Web-based information agents and plans (generalized query plans, information requests, plans in general).  The approach is, given a plan, one or more plan assistent agents are responsible for continuously monitoring parts of the plan and replacing any parts that are failing (the environment has changed) with alternate plans (patches) or requesting a separate human or machine planner to replan. Monitoring agents monitor web information sources for individual conditions (weather reports, location of packages, ...).  Teams seem to be collections of monitors.  Some machine learning going on.  Provides Ariadne system for rapidly constructing Web-based mediator systems (information agents) and SIMS Informaton Mediator (integrates heterogeneous information sources).  Supporting NEO TIE1 and TIE2 (with OBJS WebTrader).  Supports interoperability;  covers monitoring and replanning;  how agents can share meta information to extend capabilities (building on XML), how to handle ontology mismatches (using database view integration techniques), how to handle missing information;  joint work with Boeing on information agent (e.g., Web source) interoperability (mismatches in ontologies and information organization).

Potential ALP relationships:  May help in providing an architecture-wide approach in ALP for dealing with ontology mismatches and missing information in interoperating with heterogeneous systems.  (LDM functions somewhat as a common schema, but defining the mappings to local systems seems to be handled individually in custom plugins.  Some generic technology here could help the integration of heterogeneous systems scale better, and be more open/dynamic, e.g., creating plugin for a newly needed resource in a crisis situation).  SIMS Informaton Mediator could be used for heterogeneous source integration.  Ariadne system might help for rapidly constructing Web-based mediator systems (ALP will need these capabilities, although possibly "behind" plugins).  Some of their agents might be useful as assessors or assessor plugins in ALP.  Could their plan assistant be applied to log plans?  (has rewriter, executor, evaluator, initiator subcomponents, thus seems to resemble a cluster--could plugins be a useful way of specializing behavior in their agents?)  has both action and condition monitoring agents;  they mention logistics scenarios.

TEAMCORE:  Rapidly extending and building agents to form robust, adaptive teams, Milind Tambe and Weimin Shen, USC/ISI

Summary:  In the real world, teams face uncertainties (team members unexpectedly fail to meet responsibilities, have divergent beliefs about their environment, have unexpectedly noisy or faulty communication.  Without a teamwork model, it is difficult to rapidly construct teams, specify team interactions, plan for coordination failures, learn from past failures, or scale teams.  The team pattern encodes team member responsibilities to the team, joint intentions, shared plans.  It scales by hierarchies, also used to control resource utilization.  It uses discrimination-based learning plus a hidden Markov model statistical approach.  Supporting NEO TIE1 (TEAMCORE, helicopter agents).

Potential ALP relationships:  Possible way to extend an ALP cluster to interoperate with another kind of agent (better than a plugin could, or as a plugin).  Can this represent the ALP cooperation model and help integrate ALP and other models?  Help with reorganization, adaptation of ALP cluster roles and functions in changed situation, or to other domains?  How does team pattern compare to ALP workflows in representing participant interactions?  Project talks about organization hierarchies with roles, hierarchical team procedures, with coordination constraints (sounds like ALP).  Possible migration path to how clusters could be opened up to provide more coordination metadata, ability to function in open systems with heterogeneous agents.

2.  Algorithm, System Design, Policies, and Methods for Behavior Control

BORG:  A secure and scalable distributed agent based system, Sebastian Thrun, Pradeep Khosla, Han Kiliccote, CMU

Summary:  In the context of distributed information gathering, how do we make such systems scalable and survivable? If agents can be captured and made to tell what they know or can ask others to tell, this is usually handled in conventional systems by giving agents access to a local amount of information that can be shared.  In BORG there is no central server.  Information is distributed so each agent gets puzzle pieces insufficient information for the reconstruction of the global picture.

Potential ALP relationships:  Can Borg techniques be applied to replicate clusters (or plugins and associated data) to avoid loss, be more reliable, provide fault tolerance (could be done, e.g., at Java level under clusters)?  Does their concurrency control protocol (based on versions) help with concurrency and consistency issues in ALP?  Agent development toolkit and agent manager/visualization tool may be useful;  also storage services (Borg agents wrap persistence mechanisms).

ERA - Environment for Reflective Agents, Crystaliz - Sankar Virdhagriswaran

Summary:  The focus is task automation for the average programmer.  The approach is to use graphical component composition (as in Visual Basic) to select a type of wiring, wizards to identify domain components, document object model, animated displays of control flow and data flow, and the single environment view for agents that actually operate in a distributed fashion.  For example, a mechanical engineering agent is defined using schema that define geometry and material scripts that can compute mass, weight, stress, strain.  The scripts can execute independently and in parallel.  Conflict resolution approach, when multiple agents access and mofify a shared resource, is (a) via negotiation on meaning resulting in a common shared semantics, (b) negotiation on access and update rights resulting in a serialized process, (c) or can invoke a conflict resolution process using some other process that arbitrates.

Potential ALP relationships:  Seems to use a lot of XML, hence may be helpful in exploring application of XML in ALP.

D'Agents:  Resource Control in Large-Scale Mobile-Agent Systems, David Kotz, George Cybenko, Robert Gray, Daniela Rus, Dartmouth

Summary:  D'Agents mobile agent system.  Mobile agents are useful in information gathering as data sources are added to or removed from a variety of networks and computing devices.  Some technical problems w mobile agents are performance, security, fault tolerance, and resource allocation.  The approach is to develop a marketing model using virtual currency to control resource consumption.  The approach decentralizes control and so is robust, provides a clean approach to denial of service attacks, solves load balancing, and avoids consumptive behavior.  It has the potential to work in large systems that span multiple administrative domains and that include legacy apps as subsystems.  Related to ilities, also Grid requirements for load control.  Work on disconnected and PDA operations support (proxy machine as server for PDA);  mobility;  scheduling of sentinel agents (under low bandwidth conditions);  yellow pages server;  allow users to track and monitor mobile agent operation. TIE plans for work on mobility (Lockheed-Martin, BBN) on basic agent services and grid, security and interoperability (Boeing), yellow pages services (CMU), fault-tolerance (MIT, USC/ISI, CMU), exception handling (MIT).

Potential ALP relationships:  Work on disconnected operations and PDA support, sentinel agents.

Exception Handling Service for Software Agent Ensembles, Chrysanthos Dellarocas, MIT

Summary:  Agent systems can suffer from a collection of systemic (system-wide) problems like clogged networks, deadlock, poor performance, system shutdowns, communication channels fail or can be compromised, agents can die or make mistakes, unanticipated agent interdependencies, and security vulnerabilities.  Agents should just be concerned with their normative behavior, not also with locating these systemic problems and taking corrective actions.  The approach is a coordination doctor that knows the different ways a network can get sick (patterns of interaction), actively looks for the illnesses, and prescribes different treatments (detect, diagnose, resolve exceptions).  In the approach, normative agents become exception-capable agents by implementing (reifying) two additional interfaces, to report their behavior and modify their actions if exception handling agents advise.  The exception handing agents watch the system properties and have a knowledge base of reusable exception handling capabilities built in.  The idea is to make this a plug in capability for agent system architectures.  Related to ilities.  Domains:  military logistics and one other.  Provides pluggable exception handling capability for agents (for agent world, not for domain exceptions;  e.g., agents die);  claim to have a generic way to do this.  Involves agents describing their coordination protocols, generating sentinels to watch for symptoms, diagnostic and resolution services.  Analogy with telephone network.

Potential ALP relationships:  These capabilities are needed for open systems with more heterogeneity.  Possible use to handle various kinds of exceptions in ALP to support increased fault tolerance, robustness.  ALP TIE also could demonstrate that these exception handling techniques can truly be plugged into a different kind of agent system (ALP)  (their workplan calls for "second prototype on a real agent testbed".  1999 plans to do exception analysis for other CoABS ABSs, later plug into other CoABS ABS.)

3.  Computer System Architecture

Experiments with multicast protocols for agent-based systems, Mark Fausett, Mark Woodworth, BBN/GTE

Summary:  They will look at three aspects of agent multicast:  (a) tailored reliable delivery where the agent knows when to send messages based on situations. (b) intelligent change notification wherein metadata about the environment helps determine when to send change notices, and (c) scalable agent systems that use multicast.  Service Location Protocol for trading/matchmaking services.

Potential ALP relationships:  Potentially helps with data replication, dynamic joining/leaving of agent architecture, service discovery, and reliability.  (May apply to ALP at Java level).

MACOE:  Multi-Agent common operating environment, Kenneth Whitebread, Lockheed-Martin

Summary:  Promises low cost agent creation, agents from multiple vendors interoperate, dynamic agent ensembles which act like single agents.  Gives example of constraint problem with multiple ships and multiple land based requests for firepower.  Gives long list of requirements.  They are also addressing generic grid issues (agent services:  agent registration, task and data interchange, resource control;  also agent languages and ontology adaptation).

Potential ALP relationships:  Possibly useful in addressing integration of ALP with heterogeneous other agent systems.  They should see how to integrate ALP's agent (cluster) approach;  can also address what hooks grid should have to allow ALP to interoperate with it.

Agility:  Agent Ility Architecture, Craig Thompson, OBJS

Summary:  Developing an agent reference architecture in OMG, FIPA contexts and working on grid concepts.  eGent prototype encodes ACL in XML, and transports the ACL via email.  Advantage is pervasiveness of email, light-weight transport, allows messages to be queued when agents are mobile and intermittently connected, and messages pass firewalls.  Menu-Based Natural Language Interface (MBNLI) for human-agent communications;  attach MBNLI grammars and ontologies as metadata to agents.  WebTrader accepts trader advertisements written as Web pages in mixture of HTML/XML;  trader can use any search engine to locate trader ads;  trader also provides service binding to clients.  WebTrader used to identify information sources (where people are) in NEO TIE2.

Potential ALP relationships:  Individual prototypes (MBNLI, WebTrader, eGents) may be useful (e.g., explore integration of trader services, email as cluster interaction mechanism for intermittent operation).  Use Sun, OMG, FIPA connections to get ALP concepts into other communities and standards environments.  Identification of agent architecture principles, integration of services/ilities, XML and other Web technologies.

Agent-based architecture for dynamic crisis management, James Allen, George Ferguson, U Rochester

Summary:  In a setting like the Command Post of the Future (CPoF), component capabilities would be provided by a diverse set of agents, for information retrieval, data gathering, situation assessment, incremental planning, plan evaluation and visualization, plan monitoring and dynamic replanning. To the commander, however, it would appear that there is a single intelligent interactive assistant agent that is providing all the services. The commander interacts with the system using spoken language and graphical interaction. Independent of the modality of communication, the interaction is modeled as a dialogue in which context is maintained in order to: (1) coordinate and task the component agents and integrate their responses, and (2) coordinate the interaction with the commander in a natural and effective manner. We will be exploring the use of powerful temporal representations and simulation technology across this range of applications.

Potential ALP relationships:  They have tech for integrating "heavyweight" agents with "lightweight" ones (e.g. user interfaces);  a crisis scenario incorporating ALP might be interesting (a challenge problem for both sides;  ALP would need to either wrap other systems or be wrapped, and might need to either discover outside sources itself, or cooperate with other agents that integrate them, to build complete plan).  They need to look at ALP cluster/plugin organization as an approach to agentize existing black boxes.

4.  Related Technologies

Jumpstart:  A toolkit to simplify the development of robust agent security and conversation policies across heterogeneous agent frameworks, Jeffrey M. Bradshaw, Boeing

Summary:  Overall goal is to make it as easy as possible to produce high quality agents that function well in large ad hoc agent ensembles. To address the problem of agents built with differing capabilities, undertook the development of a powerful, open, and extensible Java toolkit for agent design. In its initial incarnation, the toolkit will consist of two primary components: a Communication Design Tool (CDT) and a Security Design Tool (SDT). CDT and SDT will contain graphical and analytical capabilities to help developers understand the effects that different choices in agent communications and security policy will have in the design of an agent, and how to best craft these choices to fit the capabilities and intended context of application of specific agents.  Dialogs of performatives versus individual ones.  Collaboration with Sun on fine-grained security models.  Employing mediating representations in an open extensible Java toolkit to simplify security and conversation policy design while guaranteeing robustness.  Possible TIEs:  conversation design (e.g., control semantics) with MIT and development of ACL semantics (with OGI);  performance and scalability of heterogeneous mobile agent architectures and resource management tools and mechanisms across hetero archs (with Dartmouth, BBN, Lockheed Martin)

Potential ALP relationships:  possible role in addressing security issues (not clear to what extent this done in ALP now).  CDT could possibly help in generalizing cluster communication in ALP.  Can this help construct a cluster more rapidly?  Agent design toolkit--rapid prototype to help build ALP clusters or plugins?  Jumpstart approach needs to see if it can represent clusters/plugins, and deal with agent communication via shared data (e.g., the ALP LogPlan) instead of just messages.  Java mobility, resource management (already working w/ BBN);  mobility and resource management design tool--designing mobile agents for mobility, security, resource management tradeoffs;  anytime mobility with new Java VM.  Could be helpful in dealing with mobility-related issues in ALP.

Cooperative agent test and demonstration environment, Doyle Weishar, GITI/ISX

Summary:  Effort consists of a program management task and four main technical thrusts: (1) Develop a state-of-the-art environment with Event Generation, Monitoring, Instrumentation, Visualization, and Evaluation services to enable technology demonstration and assessment; (2) Establish an ABS Infrastructure Component Technology Repository to support focused research; (3) Provide a Community Clearinghouse for Agent Technology to share lessons learned; and (4) Demonstrate and Transition ABS technologies to users.

Potential ALP relationships:  interchange on grid-related architectural issues.

Agentware, Doug Smith, Kestrel

Summary:  Agents wrap legacy software.  During a crisis, plans, schedules, and queries are reformulated based on constraints and changing availability to data sources and analysis and decision-making components.  "Synthesis" (weaving) allows the ability to compile various situation-specific features into the code, resulting in high-performance software. Components of Agentware are Planware and Specware.  Defines a continuous scheduling architecture that already has logistics as an application;  planning, monitoring/sentinel technology, replanning;  databases in architecture are indicated as including port status, TPFDDs, weather, etc.  Also have technology (Planware) for automated synthesis of planners and schedulers based on declarative specifications;  In-Theater Airlift Scheduler has been delivered to AMC.  Already doing work with BBN.  CAMPS (Combined Air Mobility Planning System;  strategic airlift scheduling system used in TIE) is a joint effort by Kestrel, CMU, and BBN for Air Mobility Command, Scott AFB. CAMPS incorporates Kestrel's high-performance scheduling technology, and CMU's rescheduling and mixed-initiative technology.

Potential ALP relationships:  Can these technologies be applied to develop clusters or plugins?  Agent generation software based on declarative approach.  Would their architecture taxonomy help understand grid and ALP architectures, and aid in integration?  Help with synthesis of glue code between agents (e.g., data translators) .

Order from Chaos - using solution clusters to manage multiple agents, Brian Drabble, David Etherington, Matt Ginsberg, U Oregon/CIRL

Summary:  It is not enough for software agents to solve the specific and narrow problems for which they were designed. Individual agents need to communicate with others so that duplicate solutions are not presented to an already overburdened human user. The project is concerned with cooperative response:  robust means it searches relevant sources without user retasking it, qualititatively different means different answers or courses of action are indeed qualitiatively different and not duplicates, and minus limiting factors means the plan is useful and the agent understands the limits of the plan (the record is not being ordered from China).

Potential ALP relationships:  TBD
 
 
 


This research is sponsored by the Defense Advanced Research Projects Agency.  The views and conclusions contained in this document are those of the author, and should not be interpreted as representing the official policies, either expressed or implied, of the Defense Advanced Research Projects Agency, or the United States Government.