Skip to content

TALOS v0.5 -- Scheduling Architecture

Date: April 2026 Scope: Automated pass scheduling design for multi-campaign ground station networks Author: Engineering (automated review)

1. Problem Statement

TALOS currently requires operators to manually assign stations to campaigns. An operator must:

  1. Know which satellites a campaign targets.
  2. Check which stations have line-of-sight to those satellites and when.
  3. Ensure no two campaigns overlap on the same station at the same time.
  4. Account for antenna slew time between consecutive passes.

This process does not scale. With 10 stations and 5 campaigns, the combinatorial space is manageable. With 50 stations and 20 campaigns, manual assignment becomes impractical and error-prone. Automated scheduling is a prerequisite for network growth.

2. Pass Window Computation

Before scheduling can occur, the system needs predicted pass windows -- the time intervals during which a satellite is above a station's local horizon.

2.1 Pass Prediction Algorithm

For each (station, satellite) pair:

  1. Propagate the satellite position using SGP4 (Skyfield or dSGP4).
  2. Compute the topocentric position relative to the station.
  3. Find rise/set events by searching for zero crossings of the elevation angle.
  4. Record: (station_id, satellite_id, aos_time, los_time, max_elevation).

AOS = Acquisition of Signal (rise above horizon). LOS = Loss of Signal (set below horizon).

2.2 Pass Window Data Model

from dataclasses import dataclass
from datetime import datetime

@dataclass(frozen=True)
class PassWindow:
    """A predicted pass of a satellite over a ground station."""
    station_id: str
    satellite_id: int          # NORAD catalog number
    campaign_id: str | None    # Assigned campaign, or None if unassigned
    aos: datetime              # Acquisition of signal (UTC)
    los: datetime              # Loss of signal (UTC)
    max_elevation: float       # Peak elevation in degrees
    duration_seconds: float    # los - aos
    priority: int              # Inherited from campaign (1=highest, 10=lowest)

2.3 Prediction Horizon

The scheduler operates on a rolling window:

Parameter Default Rationale
SCHEDULE_HORIZON_HOURS 24 One day of upcoming passes
SCHEDULE_REFRESH_MINUTES 15 Re-run scheduler as TLEs update
MIN_ELEVATION_DEGREES 10 Ignore low-elevation passes (atmospheric loss)

3. Conflict Detection

A conflict occurs when two pass windows overlap on the same station and both are assigned to different campaigns.

3.1 Overlap Test

Two passes A and B on the same station conflict if:

A.aos < B.los AND B.aos < A.los

This is the standard interval overlap check.

3.2 Slew Time Constraint

Even non-overlapping passes conflict if the gap between them is shorter than the antenna slew time. A rotator moving at 3 degrees/second needs time to reposition between consecutive targets.

def slew_time(az1: float, el1: float, az2: float, el2: float,
              rate_deg_per_sec: float = 3.0) -> float:
    """Minimum time in seconds to slew from one position to another."""
    delta_az = abs(az2 - az1)
    delta_el = abs(el2 - el1)
    max_delta = max(delta_az, delta_el)
    return max_delta / rate_deg_per_sec

Effective conflict check with slew margin:

A.los + slew_time(A_end_pos, B_start_pos) > B.aos

3.3 Conflict Graph

Build an undirected conflict graph where:

  • Each node is a PassWindow.
  • An edge connects two nodes if they conflict on the same station (overlap + slew).

The scheduling problem is then: select a maximum-weight independent set from this graph, where weight encodes campaign priority and pass quality.

4. Greedy Scheduler (Phase 1)

The initial implementation uses a greedy algorithm -- simple, deterministic, and easy to debug. This covers single-campaign scenarios and provides a working baseline before introducing OR-Tools.

4.1 Algorithm

def greedy_schedule(passes: list[PassWindow],
                    slew_margin_sec: float = 30.0) -> list[PassWindow]:
    """
    Assign passes to campaigns using a priority-first greedy algorithm.

    1. Sort passes by (priority ASC, max_elevation DESC).
    2. For each pass, check if the station is free during the window + slew margin.
    3. If free, assign the pass. If not, skip it.
    """
    # Sort: highest priority first, then best elevation
    sorted_passes = sorted(passes, key=lambda p: (p.priority, -p.max_elevation))

    assigned: list[PassWindow] = []
    # station_id -> list of assigned time intervals
    station_timeline: dict[str, list[tuple[datetime, datetime]]] = {}

    for pw in sorted_passes:
        sid = pw.station_id
        window_start = pw.aos
        window_end = pw.los + timedelta(seconds=slew_margin_sec)

        if sid not in station_timeline:
            station_timeline[sid] = []

        conflict = False
        for (busy_start, busy_end) in station_timeline[sid]:
            if window_start < busy_end and busy_start < window_end:
                conflict = True
                break

        if not conflict:
            station_timeline[sid].append((window_start, window_end))
            assigned.append(pw)

    return assigned

4.2 Complexity

  • Time: O(n^2) in the worst case (each pass checked against all assigned passes on the same station).
  • Space: O(n) for the timeline.
  • Acceptable for n < 1,000 passes (typical 24-hour horizon for 50 stations).

4.3 Limitations

  • No global optimization. A greedy choice early in the sort order may block a better combination later.
  • Cannot express complex constraints (e.g., "campaign X needs at least 3 passes per day").
  • No backtracking.

5. OR-Tools CP-SAT Scheduler (Phase 2)

For multi-campaign optimization with complex constraints, the OR-Tools CP-SAT (Constraint Programming with Satisfiability) solver is the right tool. It handles interval scheduling natively and scales to thousands of variables.

5.1 Decision Variables

For each pass window i:

from ortools.sat.python import cp_model

model = cp_model.CpModel()

# Binary: is this pass assigned to its campaign?
assigned = {}
for i, pw in enumerate(pass_windows):
    assigned[i] = model.new_bool_var(f"assigned_{i}")

# Interval variable (only active when assigned)
intervals = {}
for i, pw in enumerate(pass_windows):
    start = int(pw.aos.timestamp())
    end = int(pw.los.timestamp()) + slew_margin
    size = end - start
    intervals[i] = model.new_optional_fixed_size_interval_var(
        start=start,
        size=size,
        is_present=assigned[i],
        name=f"interval_{i}",
    )

5.2 Constraints

No-overlap per station:

# Group intervals by station
from collections import defaultdict

station_intervals = defaultdict(list)
for i, pw in enumerate(pass_windows):
    station_intervals[pw.station_id].append(intervals[i])

# Add no-overlap constraint for each station
for station_id, ivs in station_intervals.items():
    model.add_no_overlap(ivs)

Minimum passes per campaign (optional):

# Campaign X needs at least 3 passes in the scheduling horizon
campaign_passes = [i for i, pw in enumerate(pass_windows)
                   if pw.campaign_id == campaign_x_id]
model.add(sum(assigned[i] for i in campaign_passes) >= 3)

Maximum station utilization (optional):

# No station should be busy more than 80% of the scheduling horizon
for station_id in all_stations:
    station_pass_indices = [i for i, pw in enumerate(pass_windows)
                           if pw.station_id == station_id]
    total_busy = sum(
        (int(pass_windows[i].los.timestamp()) - int(pass_windows[i].aos.timestamp()))
        * assigned[i]
        for i in station_pass_indices
    )
    horizon_seconds = int(schedule_horizon.total_seconds())
    model.add(total_busy <= int(horizon_seconds * 0.8))

5.3 Objective Function

Maximize total weighted pass quality:

# Weight = priority_weight * elevation_weight
# Higher priority campaigns and higher elevation passes score higher
objective_terms = []
for i, pw in enumerate(pass_windows):
    priority_weight = 100 - (pw.priority * 10)   # priority 1 -> 90, priority 10 -> 0
    elevation_weight = int(pw.max_elevation)       # 0-90 degrees
    score = priority_weight + elevation_weight
    objective_terms.append(score * assigned[i])

model.maximize(sum(objective_terms))

5.4 Solver Invocation

solver = cp_model.CpSolver()
solver.parameters.max_time_in_seconds = 10.0    # Hard timeout
solver.parameters.num_workers = 4               # Parallel search

status = solver.solve(model)

if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
    schedule = []
    for i, pw in enumerate(pass_windows):
        if solver.value(assigned[i]):
            schedule.append(pw)
    return schedule
else:
    # Fall back to greedy scheduler
    return greedy_schedule(pass_windows)

5.5 Performance Expectations

Scenario Variables Constraints Expected Solve Time
10 stations, 5 campaigns, 24h ~200 ~50 < 100ms
50 stations, 20 campaigns, 24h ~2,000 ~500 < 2s
100 stations, 50 campaigns, 24h ~10,000 ~2,500 < 10s
200 stations, 100 campaigns, 48h ~50,000 ~12,000 10-30s

CP-SAT is designed for this scale. The 10-second timeout provides a hard guarantee for API response times.

6. API Design

6.1 Scheduler Endpoints

POST /api/v1/org/{slug}/schedule/generate
    Body: { "horizon_hours": 24, "min_elevation": 10.0 }
    Response: { "schedule_id": "...", "passes": [...], "conflicts_resolved": 7 }

GET  /api/v1/org/{slug}/schedule/{schedule_id}
    Response: Full schedule with assigned passes

POST /api/v1/org/{slug}/schedule/{schedule_id}/approve
    Body: { "pass_ids": ["...", "..."] }
    Response: Creates Assignment records for approved passes

GET  /api/v1/org/{slug}/schedule/conflicts
    Response: List of detected conflicts in current manual assignments

6.2 Workflow

  1. Operator triggers schedule generation (or it runs on a cron cycle every 15 minutes).
  2. Scheduler computes pass windows for all active campaigns in the organization.
  3. OR-Tools solver (or greedy fallback) produces an optimal assignment.
  4. Operator reviews the proposed schedule in the dashboard.
  5. Operator approves all or selected passes, which creates Assignment records in the database.
  6. Director picks up new assignments on its next tick.

6.3 Dashboard Integration

The schedule view shows:

  • Timeline view (Gantt-style) of station utilization over the next 24 hours.
  • Color-coded passes by campaign.
  • Conflict indicators for overlapping manual assignments.
  • One-click approval for proposed schedules.

7. Integration with Existing Models

7.1 Assignment Model

The current Assignment model links a station to a campaign:

class Assignment(Base):
    __tablename__ = "assignments"
    id: Mapped[str]
    station_id: Mapped[str]
    campaign_id: Mapped[str]
    organization_id: Mapped[str]
    created_at: Mapped[datetime]

The scheduler does not replace this model. It creates Assignment records as output. The distinction is:

  • Manual assignment: Operator creates an assignment directly. No time window -- the station tracks whenever the satellite is visible.
  • Scheduled assignment: Scheduler creates an assignment with an explicit time window (aos/los). The Director only commands the station during that window.

7.2 Schema Extension

Add optional time window fields to the Assignment model:

class Assignment(Base):
    __tablename__ = "assignments"
    # ... existing fields ...
    scheduled_aos: Mapped[datetime | None] = mapped_column(default=None)
    scheduled_los: Mapped[datetime | None] = mapped_column(default=None)
    max_elevation: Mapped[float | None] = mapped_column(default=None)
    scheduler_run_id: Mapped[str | None] = mapped_column(default=None)

This is backward-compatible. Existing manual assignments have scheduled_aos = None and continue to work as before.

7.3 Director Changes

The Director's get_active_assignments() query must be updated to respect time windows:

# Current: all assignments for active campaigns
# New: all assignments where NOW is within [scheduled_aos, scheduled_los]
#      OR scheduled_aos is NULL (manual assignment, always active)

8. Testing Strategy

8.1 Unit Tests

  • Pass window overlap detection (edge cases: adjacent, touching, nested).
  • Slew time calculation with various antenna positions.
  • Greedy scheduler with known inputs and expected outputs.
  • OR-Tools formulation correctness (small problem, verify optimality).

8.2 Integration Tests

  • End-to-end schedule generation via API.
  • Conflict detection with existing manual assignments.
  • Schedule approval creating correct Assignment records.
  • Director respecting scheduled time windows.

8.3 Performance Tests

  • Solver runtime with 50/100/200 station scenarios.
  • Verify 10-second timeout is respected.
  • Greedy fallback activation when solver times out.

9. Implementation Plan

Phase Scope Effort
Phase 1 Pass window computation + conflict detection 2-3 days
Phase 2 Greedy scheduler + API endpoints 2-3 days
Phase 3 OR-Tools CP-SAT formulation 3-5 days
Phase 4 Dashboard timeline view 2-3 days
Phase 5 Director time-window enforcement 1-2 days
Total 10-16 days

Phase 1-2 deliver immediate value (conflict detection + basic scheduling). Phase 3 unlocks multi-campaign optimization. Phases 4-5 complete the user experience.

10. Dependencies

Package Version Purpose
ortools >= 9.9 CP-SAT constraint solver
skyfield >= 1.48 Pass prediction (existing)
dsgp4 >= 1.1.5 Batch propagation (optional, Phase 3+)

OR-Tools is available via pip (pip install ortools) and has no native compilation requirements on Linux/macOS/Windows. The package is ~60 MB installed.

Summary

Automated scheduling transforms TALOS from a tool that requires expert operators into a system that can manage complex multi-campaign networks autonomously. The two-phase approach (greedy first, OR-Tools second) ensures rapid delivery of basic scheduling while building toward globally optimal solutions. The design is backward-compatible with existing manual assignments and requires minimal Director changes.