# Presentation: 683956

## The Deep Space Network Scheduling Problem

- Brad Clement, Mark Johnston
- Artificial Intelligence Group
- Jet Propulsion Laboratory
- California Institute of Technology
**{bclement, mdj}@aig.jpl.nasa.gov**
**http://ai.jpl.nasa.gov/**

## Space Networks

## Deep Space Network (DSN)

## Activities, Tracks, & Viewperiods

- A **track** is an allocation of an antenna to a mission over some time interval
- A **viewperiod** is the time interval when a spacecraft is visible to an antenna
- An **activity** is a track wrapped with *setup* and *teardown* time

## Deep Space Network Scheduling

- 56 missions
- 12 antennas
- different capabilities
- shared equipment
- geometric constraints
- human operator constraints
- some schedule as long as 10 years into future
- ~370 tracks & ~1650 viewperiods per week
- ~2000 tracks & ~80000 viewperiods per year
- some require schedule freeze 6 months out
- complicated requirements originally from agreement with NASA with flexibility in antennas, timing, numbers of tracks, gaps, etc.
- ~30 people employed full time to schedule for multiple missions
- schedule centrally generated, meetings and horse trading to resolve conflicts
- similar to coordination operations across missions

## Other Space Scheduling Problems

- comm. scheduling TDRSS and AFSCN
- Mars relay scheduling
- antenna command generation
- science planning
- measurement scheduling
- command sequence generation (ground and onboard)

## Constraints

**Constraints**

- No two spacecraft can use antenna at same time
- except MSPA where antenna points to both (2 at most) and uplinks to at most one
- Spacecraft must be in view of antenna
- At Goldstone, no track/activity can be scheduled where two other tracks/activities start within 15 minutes
- except the four Cluster s/c
- At other complexes, no two may start within 5 minutes of each other

**U/L**

**D/L**

**D/L**

**U/L**

**D/L**

**MEX**

**MERA**

**NAV**

**0**

**5**

**2**

**3**

**2**

**2**

**3**

**2**

**30**

## Scheduling Requirements Under Constraints

- B. Clement, S. Schaffer

- Implemented algorithm for automating scheduling of requirements:
- optional antennas (DSS14, 15, or 24)
- BOT and duration ranges
- periodic tracks
- locks on BOT, duration, and antenna
- MSPA
- arraying / VLBI / delta DOR
- continuous tracks
- segmentation
- gap-to-track ratio

- DSS-25

- MEX

- MGS

- ODY

## abstraction of requirements as an AND/OR tree
use HTN planning
optional and/or multiple resource usage 
start time and duration ranges
temporal constraints (STN)
all activity/track start times and durations must be evenly divisible by 5 minutes (except for Cluster)
locks on resource and timing
remove resource choices (OR branches)
add/shrink temporal constraints to current time allocation
ASPEN has scheduling permissions
override / blockout

**abstraction of requirements as an AND/OR tree**
**use HTN planning**
**optional and/or multiple resource usage **
**start time and duration ranges**
**temporal constraints (STN)**
**all activity/track start times and ****durations must be evenly divisible ****by 5 minutes (except for Cluster)**
**locks on resource and timing**
**remove resource choices (OR branches)**
**add/shrink temporal constraints ****to current time allocation**
**ASPEN has scheduling permissions**
**override / blockout**

**[3hr, 8hr]**

## 	periodic tracks – ranges specifiedfor some of:
initial start time
overall end of period
number of tracks
total duration of tracks
duration of individual tracks
time gap/overlap 

**	****periodic tracks – ranges specified****for some of:**
**initial start time**
**overall end of period**
**number of tracks**
**total duration of tracks**
**duration of individual ****tracks**
**time gap/overlap **

## Scheduling in ASPEN

## Scheduling Performance

- Generates schedule of 1861 tracks from ~3 weeks of requests in 39 minutes (resolving 2305 initial view period/antenna conflicts)
- Reschedules to accommodate individual emergency tracks in 0.2 seconds and emergency antenna downtime in 0.2 seconds
- Handles doubling of one mission’s track requests over one week (to 42 total) in 2.7 seconds
- Initial performance acceptable for interactive conflict resolution, possibly for initial schedule generation

## Systematic Search Algorithms

- Local search in ASPEN can handle large schedules (for long-term requirements) but gives no guarantees of optimality or that an existing solution will be found
- Systematic search can give these guarantees for small problems (conflict resolution)
- BT1: depth-first backtracking, all times/resources permitted (provided there are viewperiods available)
- most constrained first track selection
- smallest  from original time/antenna assignment
- BT2: same as BT1 but limited to original antenna
- A*: optimal graph search, objective is to minimize changes from original schedule (in both both antenna and time)
- Assumptions made for these algorithms and experiments:
- track durations are fixed in these experiments
- tracks that span day boundaries are considered locked in place
- tracks without viewperiods are considered locked in place

## Resolving conflicts forSchedule after Conflict Negotiation Meeting

- M. Johnston

- Resolving conflicts forSchedule after Conflict Negotiation Meeting

- Finds solution (or proves no solution) to each within a few hundredths of a secondFound optimal solutions to most within a few minutes

## Resolving conflicts Schedule Before Conflict Negotiation Meeting

- M. Johnston

- Finds solution to each within a few hundredths of a secondFound optimal solutions to most within a few minutes

- Resolving conflicts Schedule Before Conflict Negotiation Meeting

## User-Interface Design

**Met repeatedly with users (MDAPT, RAPSO, DSN, and mission operations staff) to understand requirements and obtain feedback on application design.**
**Collaboration with NASA Ames’ Human Computer Interaction group (Alonzo Vera, Mike McCurdy & Chris Connors), who (with us and user feedback) have designed user-interfaces.**
**designed interface for****editing of requirements**
**designed interface for****refining requirements with****aid of automated scheduler**

## Requirements Editor Dialog

## Visualization

- Gantt chart design
- Mouse over details in tabular view
- simultaneous schedule + metric visibility w/user-specifiable gradient
- visualization of differences between two schedule versions

## Applications – DSN Arrays

- NASA may build 3600 10m weather-sensitive antennas
- 1200 at each complex in groups of 100 spread over wide area
- High automation requested—one operator for 100 or 1200 antennas
- Spacecraft may use any number of antennas for varying QoS, and may need link carried across complexes
- Only some subsets of antenna signals can be combined
- depends on design of wiring/switching to combiners
- combiners may be limited
- Local response time should be minimized