Multilevel Coordinator Agent

University of Michigan CoABS Project

The Multilevel Coordinator Agent (MCA) has been developed to facilitate the coordination of plans that are formulated by separate agents. It provides the following functionality:

Preplanning:

· Can take as input a hierarchical plan library (plans that accomplish goals, where a plan can include subgoals - the library implicitly represents and and/or graph of elaborations from high-level goals into primitive actions

· Returns (or locally stores, depending on parameter settings) summary information associated with non-primitive plans

· Builds a temporal constraint network representing allowable timings of potentially conflicting primitive actions

Planning:

· Detects possible interferences between high-level plans selected by asynchronously executing agents, AND

· Recommends resolutions to interferences (synchronizations or or-branch-eliminations)

· OR identifies branches of plans involved in interferences, accepts elaborations (selected by agents) of these portions of the plans, and performs interference detection/resolution at deeper levels.

Execution:

· Enforces resolutions to potential interferences agreed upon by participating agents

· Detects and resolves potential interferences that were not predicted prior to execution (that is, as agents exercise "or" branches of the hierarchy in response to emerging, dynamic situations)

A powerpoint briefing on the MCA can be found here. The readme file associated with the software is here.

The MCA is being used as part of the Coalition TIE. A description of this follows.

Overview.

In a Coalition exercise, objectives and responsibilities will be distributed among numerous functional teams, such as warfighting, logistics, media relations, etc., with their own human and computational agents. Occasionally, operational choices made by one team have unintended consequences on what other teams should or can do (e.g., conflict over transportation resources, friendly fire).

The non-warfighting (“blunt-end”) functional teams can work with the warfighting component through agents that employ access to operation plans so that they can deconflict and advise better. Agent technologies thus can open the door to an improved concept of operation by allowing the military to work in a more dispersed way (so-called collaborative virtual working).

Michigan’s technical contributions to the Coalition TIE will include:

· Use of hierarchical plan representations to facilitate flexible and efficient communication and computation for plan conflict detection.

· Search algorithms for identifying candidate deconfliction strategies.

· Integration with operator interfaces (such as AIAI’s Process Panel) to alert humans of potential conflicts, recommend conflict resolutions, and enact chosen resolutions.

· Run-time monitoring and enforcement of coordination decisions.

In the CoAX demonstrations, Michigan will provide one or more instances of a Multilevel Coordination Agent (MCA) that implements plan conflict detection, resolution, monitoring, and enforcement capabilities.

Triggers from events.

The MCA will receive from different functional teams requests to analyse plans and report back (or to a higher authority) potential conflicts and resolutions.

The MCA will receive runtime plan updates and monitor/enforce coordination decisions that adhere to resolutions previously committed to.

Resulting Agent Tasks.

The MCA will perform deconfliction analyses and report on potential conflicts and candidate conflict resolutions.

The MCA, can block pursuit of some teams’ plans until sufficient coordination conditions are achieved, allowing runtime coordination enforcement.

Extra tasks

(1) Much of the logistics area involves coordinating with civilian suppliers/transport, which could raise extra complications (e.g., security) in Domain Management

Issues still to be Addressed.

The CoAX scenario has so far emphasized battle planning by a single authority, and needs to be extended to include a broader array of functional teams acting semi-independently

Knowledge engineering must be done to capture a sufficiently rich set of plans for each of the functional teams to enable interesting interactions to arise.

Domain Membership.

The MCA will be a component on the Grid before the 6-month demo.

In the 9-month demonstration, the MCA will be illustrated using simplified plan sets in a fairly contrived (researcher-developed) scenario to highlight some of its basic technological capabilities and motivate its role in the CoAX TIE.

In the 18-month demonstration, the MCA will interact with AIAI’s Process Panel within an integrated demonstration.

Beyond 18 months, the MCA will be extended to include:

· Coordination over plan synergies (not just conflicts) for non-episodic cases

· Guidelines for the construction of effective hierarchical plan representations

· Quantitative estimates of quality for alternative coordination candidates

· The ability to cache prior coordination strategies for future team use

Information to be Exchanged.

MCA will communicate about plans and constraints on their execution

Links to other Participants.

Initially, there will be a strong link to AIAI’s Process Panel, as the interface between the automation for coordination provided by the MCA and the human user.

To the extent that the plan spaces to be coordinated are generated on the fly (such as by Master Battle Planner, CAMPS), those plans need to be translated into f form in which MCA can reason about them.

There are possibilities to tie MCA activities more closely with aspects of other CoAX TIE activities. For example, the protocol through which plans are exchanged and coordinated could be made more robust with MIT’s exception handling technologies, and the negotiation leading to the selection of one of the candidate conflict resolution strategies discovered by MCA could involve Stanford’s techniques.

Other Technical Aspects

The MCA will invest appropriate effort to impose just enough constraints on activity timings and choices to ensure successful and efficient accomplishment.

The MCA uses hierarchical plan representations to search abstract plan spaces more efficiently in a top-down manner, allowing agents to communicate less about each other, model less about each other, and leave themselves more room for improvisation.

The MCA reasons at abstract levels using “summary information” about what might or must hold over alternative plan refinements, and interleaves planning with execution by performing dynamic analyses of temporal constraint networks.