Satellite Scheduling via Graph

Satellite scheduling is a constraint satisfaction problem: given limited passes over targets and ground stations, which actions should be performed and when? Linear Programming (LP) and Mixed Integer Programming (MIP) are common approaches, but graphs offer compelling advantages.

Why Graph Over LP/MIP?

LP/MIP solvers are powerful but come with overhead. They can be slow for real-time decisions, and infeasible constraints produce no solution at all. A graph-based approach is fast and always yields a valid schedule. We use longest path because we want to maximize the total value of scheduled actions, equivalent to a maximization objective in LP/MIP. Time-ordered windows form a directed acyclic graph (DAG), making longest path solvable in O(V+E)—optimal for the graph as constructed, though the graph itself is a simplification of the full problem.

LP handles richer constraints (resource limits, minimum captures per client) more naturally. But for operational systems, this trade-off is worthwhile because a good answer now beats the best answer later.

The key challenge shifts from solver configuration to graph construction.

Modeling Actions as Windows

A satellite's schedule consists of time windows during which actions are possible. We model three action types:

- Upload — commands sent from ground station
- Capture — imagery acquired over target
- Download — data transmitted to ground station

fsharp
type Action = Upload | Capture | Download

type Window = {
    Id: string
    Target: string
    StartMin: int
    EndMin: int
    Priority: float
    Action: Action
}

Each window has a priority reflecting its value. This could be client importance, data urgency, or any business logic—computed before graph construction.

Building the Graph

The graph construction is straightforward: windows become nodes, and edges connect windows that can be scheduled sequentially (no overlap).

fsharp
let buildGraph (windows: Window array) : Graph =
    let nodes = 
        Array.append 
            [| mkNode "START"; mkNode "END" |]
            (windows |> Array.map (fun w -> mkNode w.Id))
    
    let startEdges = 
        windows 
        |> Array.map (fun w -> mkEdge $"s_{w.Id}" w.Priority "START" w.Id)
    
    let transitionEdges =
        windows
        |> Array.collect (fun src ->
            windows
            |> Array.filter (fun dst -> src.EndMin < dst.StartMin)
            |> Array.map (fun dst -> 
                mkEdge $"{src.Id}_{dst.Id}" dst.Priority src.Id dst.Id))
    
    let endEdges =
        windows
        |> Array.map (fun w -> mkEdge $"{w.Id}_e" 0.0 w.Id "END")
    
    { Nodes = nodes; Edges = Array.concat [| startEdges; transitionEdges; endEdges |] }

Edge weights carry the destination window's priority. The longest path algorithm then maximizes total priority.

Example

Consider a satellite pass with uploads, captures, and downloads. The resulting graph structure:

U1 ──┬──→ C1 ──┬──→ C3 ──→ D1 ──┬──→ C4 ──→ D2 ──→ C6
     │         │                │
     └──→ C2 ──┘                └──→ C5 ──┬──→ D2
                                          │
                                          └──→ C6

Note: START and END nodes (omitted above) serve as entry/exit points for the algorithm. Every window connects to END, guaranteeing a solution even when no future windows are reachable.

Overlapping windows (C1/C2, C4/C5) create branching paths—the algorithm chooses the higher-value route.

Running the Solver

With the graph constructed, we pass it to a longest path solver:

fsharp
let windows = [|
    { Id = "U1"; Target = "GS-Madrid";   StartMin = 0;  EndMin = 5;   Priority = 2.0; Action = Upload }
    { Id = "C1"; Target = "Beijing";     StartMin = 8;  EndMin = 15;  Priority = 5.0; Action = Capture }
    { Id = "C2"; Target = "Tokyo";       StartMin = 12; EndMin = 20;  Priority = 4.0; Action = Capture }
    { Id = "C3"; Target = "Seoul";       StartMin = 22; EndMin = 28;  Priority = 6.0; Action = Capture }
    { Id = "D1"; Target = "GS-Alaska";   StartMin = 30; EndMin = 38;  Priority = 3.0; Action = Download }
    { Id = "C4"; Target = "Mumbai";      StartMin = 40; EndMin = 48;  Priority = 4.0; Action = Capture }
    { Id = "C5"; Target = "Dubai";       StartMin = 45; EndMin = 52;  Priority = 7.0; Action = Capture }
    { Id = "D2"; Target = "GS-Svalbard"; StartMin = 55; EndMin = 62;  Priority = 3.0; Action = Download }
    { Id = "C6"; Target = "London";      StartMin = 65; EndMin = 72;  Priority = 5.0; Action = Capture }
|]

let graph = buildGraph windows
let response: Response = Cruiser.solveGraph graph LongestPath "START" "END" client

...

let result = Cruiser.fetchGraphResult id (CancellationToken()) client

// error handling omitted for brevity (but let's assume all is well ;))
// match result.Error with
// | ...

let path = result.Paths.Value[0]
printfn "Time: %d ms" result.Time
printfn "Path: %A" (String.Join(" > ", path.Path))
printfn "Weight: %.2f" path.TotalWeight

Expected output:

Time: 6 ms
Path: "START > U1 > C1 > C3 > D1 > C5 > D2 > C6 > END"
Weight: 31.00

I use a custom solver, but the concepts apply to any graph library that implements longest path (or shortest path with negated weights).

From Path to Schedule

The solver outputs a path of node IDs. We then use this list to create a schedule with the appropriate window metadata to build the operational schedule for upload. This separation keeps the path solver lightweight.

Considerations

Buffer time between actions (slew time, sensor cooldown) can be factored into priority—windows with tight transitions receive lower priority, nudging the algorithm toward safer schedules. Priority computation is where domain expertise lives: client SLAs; revisit requirements; and load balancing. All influence edge weights.

The graph formulation makes these trade-offs explicit and testable. Each priority rule becomes a function you can unit test in isolation. The graph structure itself can be validated: check edge counts, verify no orphaned nodes, confirm expected paths exist. When schedules don't meet expectations, you debug the graph construction, not a solver's internal state.