# Presentation: 689726

## Continual Coordination of Spacecraft through Shared Activities 

- Continual Coordination of Spacecraft 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

## Shared Activity Coordination (SHAC)

- SHAC
- Framework for defining and implementing automated interactions between planning systems (a.k.a. coordination protocols)
- Continual coordination algorithm
- Testbed for evaluating protocols
- Prior state-of-art
- scientists meet to negotiate mission plan(s)
- distributed planning treated as a collaborative problem
- planners collaborate on resolving state conflicts
- space mission planning is decentralized; requires complex resources
- Main Capabilities
- Spacecraft react as team to unexpected events.
- Missions can evaluate distributed planning protocols in real-time environment.
- Alternative protocols easy to design and implement.

- All rights reserved, California Institute of Technology © 2002

## Motivation

**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

- 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.
- Applies to autonomous missions

- 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)
- physically distributed points of control
- limited shared resources
- communication constraints/costs
- computation constraints (parallel processing)
- greater capabilities/efficiency of distributed assets

- 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 roles
- changes sharing agents and protocol assignments
- handle changes received from other agents

- All rights reserved, California Institute of Technology © 2002

## SHAC Algorithm

- Given: 	a ***plan*** with multiple activities, including a set of ***shared_activities*** 	with ***constraints****,* 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***.
- 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*** and ***constraints***.
- Update ***shared_activities*** and ***constraints*** 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

## Delegation Protocol

- 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

## 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

## TeamModel

**  ****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, response_time);**
**};**
**shared_activity comm_b {**
** ****datasize;**
**  ****critical_size;**
**  ****high_size;**
**  ****response_time;**
**  ****start_time;**
**  ****roles =**
**    ****comm_orbiter_b by merb,**
**    ****move_mer_data by mgs,**
**    ****move_mer_data by odyssey,**
**    ****move_mer_data by mex;**
**  ****protocols =**
**    ****merb MarsDelegation,**
**    ****mgs Subordination,**
**    ****mex Subordination,**
**    ****odyssey Subordination;**
**  ****permissions =**
**    ****comm_orbiter_time_b (all),**
**    ****move_mer_data (place, detail, response_time);**
**};**

**agent mera {**
**  ****planner = AspenPlannerInterface(10, 10, 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 {**
**  ****planner = AspenPlannerInterface(10, 10, 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 odyssey {**
**  ****planner = AspenPlannerInterface(10, 10);**
**  ****communication = SocketCommunication("../dist-coord/mars-ports.txt");**
**  ****communicator = AspenCommunicator;**
**};**
**agent mgs {**
**  ****planner = AspenPlannerInterface(10, 10);**
**  ****communication = SocketCommunication("../dist-coord/mars-ports.txt");**
**  ****communicator = AspenCommunicator;**
**};**
**agent mex {**
**  ****planner = AspenPlannerInterface(10, 10);**
**  ****communication = SocketCommunication("../dist-coord/mars-ports.txt");**
**  ****communicator = AspenCommunicator;**
**};**
**protocol MarsDelegation();**
**protocol Subordination();**

- TeamModel
- File

- 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

## 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

## Tech Sat 21 Mission adopts SHAC coordination system for use in coordinating multiple experiments for Mission
Technology enables automated conflict detection and resolution between distributed experiment operations teams when experiments require use of shared spacecraft resources

- Technology enables automated conflict detection and resolution between distributed experiment operations teams when experiments require use of shared spacecraft resources

**SHAC for ground planning systems**

- B. Clement

- Individual TS-21 Experiment Plans

- ...

- SHACCoordination

- De-conflicted Master TS-21 Schedule

- All rights reserved, California Institute of Technology © 2002