# Presentation: 689728

## Continual Coordination through Shared Activities 

- Continual Coordination through Shared Activities

- Brad Clement & Tony Barrett
- Artificial Intelligence Group
- Jet Propulsion Laboratory
- California Institute of Technology
**{bclement,barrett}@aig.jpl.nasa.gov**
**http://www-aig.jpl.nasa.gov/**

- All rights reserved, California Institute of Technology © 2002

## Outline

- motivation
- shared activity model
- SHAC algorithm
- protocol development
- consensus windows
- Mars scenario
- conclusion & future work

- All rights reserved, California Institute of Technology © 2002

## Why Decentralized Planning?

- Why plan?
- near-term actions can effect subsequent ones in achieving longer-term goals
- Why decentralize?
- competing objectives (self-interest)
- control is already distributed
- communication constraints/costs (b/w, delay, privacy)
- computation constraints (parallel processing)
- robustness to failure?

- All rights reserved, California Institute of Technology © 2002

## Motivation for Space

**Over 40 multi-spacecraft missions proposed!**
- Autonomous single spacecraft missions have not yet reached maturity.
- How can we cost-effectively manage multiple spacecraft?

**Earth Observing System**

**Sun-Earth Connections**

**Origins Program**

**Structure & Evolution **
**of the Universe**

**Mars Network**

**NMP**

**NMP**

- All rights reserved, California Institute of Technology © 2002

## Motivation for Space

- Considerable ground operations effort and cost involved in coordinating mission plans for interacting missions.
- Human collaboration can be error-prone and slow to react.
- Automating this coordination reduces operations costs and increases science return.
- Can automate coordination on ground or on board spacecraft

- All rights reserved, California Institute of Technology © 2002

## Prior Work

- Treats decentralized planning as an offline, collaborative problem
- planners collaborate on resolving state conflicts, ignore communication costs
- Space missions present real-time problems with self-interested agents
- scientists compete for instrument/spacecraft use
- missions compete for bandwidth to Earth
- remote explorers may need to respond to dynamics autonomously

- All rights reserved, California Institute of Technology © 2002

## Problems

- How should planning agents communicate with each other?
- How can they coordinate joint actions during execution?
- How can coordination algorithms be developed efficiently?

- All rights reserved, California Institute of Technology © 2002

## Problems

- How should planning agents communicate with each other?
- shared activities
- How can they coordinate joint actions during execution?
- continual coordination algorithm
- consensus window
- How can coordination algorithms be developed efficiently?
- Protocol classes that manipulate shared activities

- All rights reserved, California Institute of Technology © 2002

## Shared Activity Coordination (SHAC)

- Software for getting separate planners to interact
- Communication language
- Continual coordination algorithm
- Framework for defining and implementing automated interactions between planning systems (a.k.a. coordination protocols)
- Testbed for evaluating protocols
- Agents react as team to unexpected events.

- All rights reserved, California Institute of Technology © 2002

## Optimize a function of variable assignments with both local and non-local constraints.

- Distributed Constrained Optimization

- All rights reserved, California Institute of Technology © 2002

## Shared Activity Coordination

- Shared activities implement team plans, joint actions, and shared states/resources

- All rights reserved, California Institute of Technology © 2002

## Shared Activity Model

**parameters** (string, integer, *etc*.)
**constraints** (e.g. agent4 allows start_time [0,20], [40,50])
**decompositions** (shared subplans)
**permissions** - to modify parameters, move, add, delete, choose decomposition, constrain
**roles** - maps each agent to a local activity
**protocols** - defined for each role
- change constraints
- change permissions
- change roles
- includes adding/removing agents assigned to activity

- All rights reserved, California Institute of Technology © 2002

## SHAC Algorithm

- Given: 	a ***plan*** with multiple activities, including a set of ***shared_activities****,* 	and a ***projection*** of ***plan*** into the future.
- Revise ***projection*** using the currently perceived state and any newly added goal activities.
- Alter ***plan*** and ***projection*** while honoring ***constraints****** ***and*** ******permissions****** of ******shared_activities***.
- Release relevant near-term activities of ***plan*** to the real-time execution system.
- For each shared activity in ***shared_activities***
- if outside consensus window,
- apply each associated *protocol* to modify the activity
- else
- apply simple *consensus_protocol*
- Communicate changes in ***shared_activities***.
- Update ***shared_activities*** based on received communications.
- Go to 1.

- All rights reserved, California Institute of Technology © 2002

## Protocol Capabilities

- Default protocol class
- joint intention
- mutual belief
- resource sharing
- active/passive roles
- master/slave roles
- Extending protocol classes
- modify permissions
- modify local parameter constraints
- add/delete sharing agents
- change roles of sharing agents

- All rights reserved, California Institute of Technology © 2002

## Example Protocol Classes

- modify permissions
- modify local parameter constraints
- add/delete sharing agents
- change roles of sharing agents
- Argumentation (1,2)
- Delegation (3)
- Asynchronous weak commitment (1,2)
- Constraint-based conflict resolution (2,4)
- Round robin (1)
- Centralized conflict delegator (extends delegation)

- All rights reserved, California Institute of Technology © 2002

## Delegation Protocol(variant used in MISUS)

- Delegation::modifyRoles()
- if *roles* does not contain exactly 1 subordinate
- choose a *subordinate* to whom to delegate the activity
- add *subordinate* to *roles*
- Subordination::modifyRoles()
- if cannot resolve conflicts involving activity
- remove self from *roles*

- All rights reserved, California Institute of Technology © 2002

## Round Robin

- Modify permissions
- if have modification permissions
- update *time_elapsed*
- if finished planning or *time_elapsed* > *threshold*
- remove self's modification permissions (e.g. move and delete)
- add modification permissions for next agent
- set *time_elapsed* to 0

- All rights reserved, California Institute of Technology © 2002

## Constraint-Based Conflict Resolution

- Modify parameter constraints:
- if cannot resolve conflicts involving shared activity
- update parameter constraints describing locally consistent values
- Modify roles:
- if reached consensus on constraints or time_elapsed > threshold
- switch to role for solution convergence(e.g. argumentation, voting, highest rank decides)

- All rights reserved, California Institute of Technology © 2002

## Asynchronous Weak Commitment

- AWC::modifyPermissions()
- if have highest priority
- remove self’s modification permissions (add, move, delete)
- else
- give self modification permissions
- AWC::modifyConstraints()
- if cannot resolve local conflicts and conflicts with constraints of higher ranking agents
- set own rank to highest rank plus one
- generate parameter constraints (no-good) describing locally consistent values

- All rights reserved, California Institute of Technology © 2002

## MER depends on orbiters to route data
Orbiters have their own agendas, but agree to relay MER data based on priority.
Orbiters schedule comm requests and respond with downlink times.
MER delegates to orbiter with best downlink time or plans to send directly to Earth.

- Orbiters have their own agendas, but agree to relay MER data based on priority.
- Orbiters schedule comm requests and respond with downlink times.
- MER delegates to orbiter with best downlink time or plans to send directly to Earth.

**Mars Scenario**

- B. Clement

**SHAC**

**MGS**

**MEX**

**Odyssey**

**MER A**

**MER B**

- All rights reserved, California Institute of Technology © 2002

## SHAC Model File

**  ****datasize;**
**  ****critical_size;**
**  ****high_size;**
**  ****response_time;**
**  ****start_time;**
**  ****roles =**
**    ****comm_orbiter_a by mera,**
**    ****move_mer_data by mgs,**
**    ****move_mer_data by odyssey,**
**    ****move_mer_data by mex;**
**  ****protocols =**
**    ****mera MarsDelegation,**
**    ****mgs Subordination,**
**    ****mex Subordination,**
**    ****odyssey Subordination;**
**  ****permissions =**
**    ****comm_orbiter_time_a (all),**
**    ****move_mer_data (place,****      detail, connect, ****      disconnect, ****      response_time);**
**};**
**shared_activity comm_b {**
** ****. . .**
**};**

**agent mera {**
**  ****planner = **
**    ****AspenPlannerInterface(80, 20, comm_windows, **
**                          ****odyssey, odyssey_view_sv0, in,**
**                          ****mgs, mgs_view_sv0, in,**
**                          ****mex, mex_view_sv0, in);**
**  ****communication =**
**    ****SocketCommunication("../dist-coord/mars-ports.txt");**
**  ****communicator = AspenCommunicator;**
**};**
**agent merb {**
**  ****. . .**
**};**
**agent odyssey {**
**  ****planner = AspenPlannerInterface(60, 20);**
**  ****communication =**
**    ****SocketCommunication("../dist-coord/mars-ports.txt");**
**  ****communicator = AspenCommunicator;**
**};**
**agent mgs {**
**  ****. . .**
**};**
**agent mex {**
**  ****. . .**
**};**
**protocol MarsDelegation();**
**protocol Subordination();**

- _SHAC Model File_

- All rights reserved, California Institute of Technology © 2002

## Reaction to unexpected events

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- comm opportunities

- If a communication fails, or new comm is requested, the planner must either schedule later in open comm slots or swap comm slots to send earlier.  MER can only estimate orbiter downlink times.  MER and orbiters must be in agreement, so near-term changes may be impossible.

**MER Planner**

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- Problem: when should xmit commitments be made on communication?
- If too early, chances to optimize are lost.  If too late, de-commitments could result in lengthy returns to Earth.

- comm opportunities

**MER Planner**

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

- Immediate requests may not be fulfilled during communication because replanning is needed.  By starting request in prior comm window, consensus can be reached more easily because there is time to replan in between comm windows.  Would a single consensus window be better because of dependencies among orbiters?

**MER Planner**

**MGS**

**Odyssey**

**MEX**

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- Single consensus window spans to next comm opportunity.  This forces the orbiter to commit to requests on-the-fly.  This either optimistically assumes the orbiter can replan immediately while leaving time to transfer the image, or resources are reserved up-front for on-the-fly communication and storage (potentially restricting the flexibility of operations).

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- Separate consensus windows for each orbiters spans to next comm opportunities

**MER Planner**

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- Separate consensus windows span two ahead.
- Immediate requests may not be fulfilled during communication because replanning is needed.  By starting request in prior comm window, consensus can be reached more easily because there is time to replan in between comm windows.

**MER Planner**

- All rights reserved, California Institute of Technology © 2002

## Communication Window-Based Protocols

**Executive**

**DSN**

**MGS**

**Odyssey**

**MEX**

- Single consensus window spans two ahead.
- May be better because of dependencies among orbiters.

**MER Planner**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**consensus window**

**highest rank decides**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**consensus window**

**voting or auction**

**votes****collected**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

**Agent A**

**Agent C**

**Agent B**

**1**

**1**

**2**

**2**

**Agent A**

**Agent B**

**Agent C**

**time**

**execute**

**consensus window**

**voting or auction**

- All rights reserved, California Institute of Technology © 2002

## Computing Consensus Windows

- All rights reserved, California Institute of Technology © 2002

## SHAC Design

- All rights reserved, California Institute of Technology © 2002

## SHAC Design

- All rights reserved, California Institute of Technology © 2002

## Mars Scenario

**no pending****request**

**request**

**wait for****uplink**

**critical****pancam**

**comm****earth**

**comm****odyssey**

**no pending****request**

**comm****earth**

**through Odyssey**

**direct**

**must-be wait**

**wait for****uplink**

**no pending****request**

**request**

**wait for****uplink**

**critical****pancam**

**comm****earth**

**must-be wait**

**odyssey****received**

**no pending****request**

**comm****earth**

**comm****odyssey**

**wait for****uplink**

**downlink****critical****data**

**uplink****from****DSN**

- All rights reserved, California Institute of Technology © 2002

## Mars Scenario

**no pending****request**

**Odyssey**

**MER A**

**must wait**

**comm earth**

**critical pancam**

**comm earth**

**comm earth**

**comm odyssey**

**traverse**

**comm earth**

**no pending****request**

**request**

**no pending****request**

**wait for****uplink**

**science activities**

**science activities**

- All rights reserved, California Institute of Technology © 2002

## Mars Scenario

**Odyssey**

**MER A**

**must wait**

**comm earth**

**critical pancam**

**comm earth**

**comm earth**

**comm odyssey**

**traverse**

**comm earth**

**no pending****request**

**request**

**no pending****request**

**wait for****uplink**

**science activities**

**science activities**

**critical pancam**

**comm earth**

**comm earth**

**comm odyssey**

**traverse**

**comm earth**

**no pending****request**

**request**

**no pending****request**

**comm earth**

**must wait**

**wait for****uplink**

**odyssey****received**

**must wait**

**wait for****uplink**

**no pending****request**

- All rights reserved, California Institute of Technology © 2002

## Mars Scenario

**Odyssey**

**MER A**

**comm earth**

**critical pancam**

**comm earth**

**comm earth**

**comm odyssey**

**traverse**

**comm earth**

**no pending****request**

**request**

**science activities**

**science activities**

**critical pancam**

**comm earth**

**comm earth**

**comm odyssey**

**traverse**

**comm earth**

**no pending****request**

**request**

**comm earth**

**must wait**

**wait for****uplink**

**odyssey****received**

**must wait**

**wait for****uplink**

**odyssey****received**

**no pending****request**

**no pending****request**

- All rights reserved, California Institute of Technology © 2002

## Related Work

- WITS and VOLT provide collaborative interfaces for visualization and data entry
- Plan merging (Georgeff, Ephrati & Rosenchein, Durfee *et al.*)
- Divide & conquer collaborative planning (Corkill, Lansky)
- DSIPE (des Jardins & Wolverton)
- TAEMS & GPGP (Decker & Lesser)
- Shared Plans (Grosz *et al.*)
- TEAMCORE & TOP (Tambe & Pynadath)
- SHAC

| resolve conflicts | opti-miza-tion | resour-ces | decen-tralized search | process auto-mation | self-interest |
| --- | --- | --- | --- | --- | --- |
|  |  | X |  |  | X |
| X |  | X |  |  |  |
| X |  |  |  |  |  |
| X |  |  | X |  |  |
| X | X | X | X |  |  |
| X |  |  | X |  |  |
|  |  |  |  |  |  |
| X | X | X | X | X | X |

- All rights reserved, California Institute of Technology © 2002

## Single vs. Multiple ASPENs

- Users access separate GUIs to central ASPEN
- Different views by hiding acts & timelines
- User access uniform
- Updates instantaneously
- Must develop custom interfaces to other tools

- Users each have planner interface
- Different views from different models
- Protocols model a coordination process: heterogeneous and adaptive access
- Updates controlled
- Provides planner-independent interface

_**ASPEN**_

_**SHAC**_

- All rights reserved, California Institute of Technology © 2002

## Ground Planning

- Techsat-21
- Problem:Multiple groups needto collaborate onbuilding commandsequences
- Almost all (if not all) missions have this problem
- Hubble Space Telescope (one spacecraft, one instrument, many scientists)
- scientists collaborate with each other
- scientists collaborate with operations staff
- missions collaborate with each other (e.g. Mars, Earth-orbiters, Great Observatories)

- All rights reserved, California Institute of Technology © 2002

## Collaborating ASPENs

**Centralized approach**
- advantages
- sequence uplinks must be centralized anyway
- decisions simplified with central authority
- disadvantages
- planning decisions centralized
- bottleneck for communication and problem solving
- central point of failure (with proper backup procedure, not a big issue)

**MPW**

- All rights reserved, California Institute of Technology © 2002

## Collaborating ASPENs

**Decentralized approach**
- advantages
- heterogeneous planning capabilities
- conflicts localized and resolved by subgroup
- parallel problem solving
- disadvantages
- distributed problem solving more complex—may require increased communication

- All rights reserved, California Institute of Technology © 2002

## Proposed Solution

**Hybrid approach**
- central authoritative schedule (e.g. MPW)
- heterogeneous planning
- hierarchical activities providing scheduling at different levels of abstraction
- SHAI custom interface
- conflict resolution
- regulated by central authority
- localized to subgroups

**Example planning interactions**

- All rights reserved, California Institute of Technology © 2002

## Example: How it Would WorkPlanning Phase: ASPEN + ShAC

- Users plan activities in parallel
- add goals to schedule,
- automated scheduling using ASPEN,
- explore alternative schedules.
- Users command ShAC (depending on scheduling permissions) to
- input constraints on activities,
- send out plan changes, rejections, and constraints,
- receive changes (schedule updates) from others,
- incorporate (enforce) constraints from others.
- ShAC can automate subsets of the above commands, taking user out of the loop if desired.

**MPW**

**new activities**

**some accepted,****some rescheduled,****constraints**

**all accepted**

**ASE**

**TENCAP**

**new activities**

**some rescheduled,****constraints**

**rescheduled****activities**

**rescheduled****activities**

**rescheduled****activities,****new activities**

**rescheduled****activities,****deleted activities,**
**new activities**

**some rescheduled,****constraints**

**some rescheduled,****constraints**

**constraints**

- All rights reserved, California Institute of Technology © 2002

## Example: How it Would WorkPlanning Phase: non-ASPEN + ShAC

- Process could be the same with
- translation between planning languages or
- manual encoding of activity changes and reports giving feedback
- ShAC enforces  constraints and permissions but notifies with reports

**Planning Tool X**

**ShAC**

**Translate****activity languages**

**activity****changes**

**activity****changes**

**reports on **
**accepted, rejected, and modified activities**
**constraints**
**permission changes**

- All rights reserved, California Institute of Technology © 2002

## Contributions

- communication language for distributed planning
- general algorithm for continual coordination
- framework for developing coordination protocols
- planner independent interface

- All rights reserved, California Institute of Technology © 2002

## Current Future Work

- evaluate protocols (including DCSP) for a few domains
- distributed network scheduling
- abstraction techniques for limiting communication and preserving flexibility
- find a customer

- All rights reserved, California Institute of Technology © 2002