Usage Scenario: Single or Multiagent Plan Coordination Service
Author(s): Jeffrey Cox and Edmund Durfee, University of Michigan
URL(s) or other references:
- Bradley J. Clement,
Edmund H. Durfee. Top-Down
Search for Coordinating the Hierarchical
Plans of Multiple Agents (paper), Proceedings
of the Third International Conference on Autonomous Agents (Agents '99).
- Jeffrey S. Cox, Edmund
H. Durfee. "Discovering
and Exploiting Synergy
Between Hierarchical Planning Agents." (paper) Second
International Joint Conference On Autonomous Agents and Multiagent
Systems (AAMAS '03)
Domain: Planning, Multiagent Coordination, Synergy
Description
This is a service provided to coordinate the
independently generated plans of one or more agents to resolve
conflicts and exploit unexpected cooperative opportunities. Our service
supports both a partial-order and a hierarchical plan representation of
agent activity.
Scope
At its core, the plan coordination service works to resolve
conflicts and exploit unexpected cooperative opportunities between
subplans of a single agent,
identifying individual plan steps between the plans that either
conflict (meaning that they must be synchronized in order to ensure
correct execution) or are redundant, meaning the steps can be combined
into a single step, reducing the agent's execution cost.
The service supports more sophisticated problems in which each plan
belongs to a separate agent (human,
robot, computer program, organization, etc.) and the goal is to prevent
interference and exploit common actions between the agents to improve
plan execution. In addition, the service also supports an expanded plan
representation in which agent plans are represented hierarchically (both in
decomposition and option selection). The service can reason about
interactions between agent plans at various levels of abstraction,
exploiting the representation to more quickly arrive at coordinated
solutions.
Stakeholders & Interests
Stakeholders can include an individual wishing to integrate existing
solutions to subproblems
when solving a larger problem or different organizations wishing to
coordinate their behaviors given their existing planning solutions.
Actors & Goals
- Human planners
- (Semi-)automated planning systems
- Reactive plan execution systems
Modification History
- Created by Jeffrey Cox,
University of Michigan on 6-Nov-2003
Use Case: Plan Coordination
Requirements
- Input: Independenty generated plans from a single or multiple
agents,
sharing a common plan format.
- Input: Sets of goals for each participating agent.
- Input: [Optional - Search guidance, or solution preferences]
- Output: Modified, coordinated plans in the shared format.
Actors/Roles
Technologies
Automated plan coordination and plan merging.
Goal/Context
Environments in which separate plans to achieve specific goals
have already been formulated, and that are now to be executed in a
shared context (thus introducing the possibility of interaction between
plan executors). Examples might be:
- ensuring coalition partners in a military conflict avoid friendly
fire accidents
- coordinating logistics/transportation agents in which agents have
shared delivery (sub)routes to improve efficiency
- generation of merged plans for NASA mars rovers operating in
concert on Mars
- ...
Assumptions
Inputs and Output formats agreed on by participating agents.
Scenario/Steps
Simple case is a single coordination episode, in which agents submit
their plans, the coordination system searches for and identifies
required/optional modifications, and returns modifications to the
agents who then execute their plans. A more sophisticated usage
scenario is an iterative/sequential one, in which agents iteratively
submit plans, receive coordination feedback, and resubmit plans to
further improve their coordinated behavior.
Extensions
Fits well within a larger system for partitioning a planning
problem into subproblems, planning for each problem separately, and
then integrating subplans together.
Ontologies Needed
Initial plans to be coordinated, plan
representation and solution criteria.
Reasoning Techniques Required
Search, action refinement, synchronization, constraint satisfaction,
unification, hierarchical planning
Open Issues or Questions
None noted.