Activity Planning and Sequencing

Activity planning turns a set of science and engineering goals into a time-ordered set of commands that fits inside the vehicle’s energy, thermal, data volume and pointing constraints. Almost all of it is done on the ground. The question every onboard scheduler answers is a narrower one: given the plan the ground built and the state the vehicle is actually in, what may be moved [1].

The cost of ground conservatism

Ground sequencing assigns each activity a fixed start time and a duration estimated conservatively enough that an overrun almost never cancels the activity that depends on it, targeted at fewer than one plan in 100 [4]. A study of Mars Science Laboratory science campaigns found submaster sequences finishing on average more than 20 percent early. That early finish is not recovered: the rover stays awake, drawing power, until the next fixed start time arrives [1][4].

The onboard scheduler exists to spend that margin. On Perseverance it is also given a job the ground used to do: generating the wakeup, shutdown, preheat and maintenance heating activities, which on MSL the operations team created by hand [1].

The Mars 2020 onboard planner

Input is a plan file the ground uplinks in place of a timed sequence, holding on the order of a few hundred candidate activities, each with priority, sequence identifier, predicted duration, average and peak power rate, data generation rate, claimed unit resources, heating requirements, required sequence engine count, CPU state requirement, a cleanup sequence with its own predicted duration, earliest, preferred, latest and cutoff times, and dependencies on other activities [1][5]. Output is a schedule plus a generated wake, sleep and heating plan [3].

The algorithm is priority-first, greedy and non-backtracking [2][3]. For each activity in ground-assigned priority order it computes the valid temporal intervals for each constraint separately and intersects them, then in a second phase checks plan-wide energy, generates the wake and sleep activities, and generates preheat and maintenance heating whose duration depends on ambient temperature at the candidate start time[4]. If all of that succeeds the activity is placed, and once placed it is never moved or deleted within a run [2].

Constraints checked are the allowed start time windows, dependencies, unit resources, state requirements and effects, data volume, UHF communication interactions, minimum battery state of charge both globally and at handover, maximum peak power, minimum sleep time and minimum awake time [2].

What it costs on the RAD750

Perseverance runs a BAE RAD750 at 133 MHz with 128 MB of DRAM and 4 GB of NAND on a separate card, under VxWorks, with the flight software written in C and decomposed into VxWorks tasks communicating by priority-queued interprocess messages [1]. The onboard planner receives only a fraction of that machine.

Quantity	Value
RAD750 measured performance	200 to 300 MIPS
Contemporary 2016 Intel Core i7	over 300,000 MIPS, over 1000 times faster
Effective speed of the scheduler’s share	several thousand times slower than a typical laptop
Conservative estimated runtime budget per invocation	60 s
Target schedule generation time	on the order of a minute
Expected invocations per sol	15 to 20

Sources: [2] for the processor and runtime budget, [3] for the schedule generation time and invocation count.

The cost of the valid-interval computation scales as O(N^2) in the number of resource impacts, and because impacts are proportional to activities, scheduling N activities is an O(N^3) algorithm [3]. The plan is therefore truncated rather than solved. The full plan specification may define up to 100 activities spanning several sols, but the scheduler considers only the 40 highest priority at a time, the “considered set”, with the remainder held in a “hopper” and promoted as considered activities finish [3]. Backtracking was rejected for the same reason: it would raise runtime [2].

Two mechanisms recover some of what non-backtracking loses. A switch group is a set of activities differing only in how much time, energy or data volume they consume, of which exactly one must be scheduled; the Multiple Scheduler Invocation approach calls the scheduler repeatedly with the most consumptive option first, then the next, until a schedule containing all requested activities is produced, which is a heavily constrained form of backtracking [3]. An expanding activity is grown by binary search to the largest valid duration [1]. Throttling imposes an increasing wait between consecutive scheduler invocations.

Because the result is sensitive to the priority order and only one static priority set is configured per plan, the ground scheduler Copilot runs a Monte Carlo analysis of sol execution variability to choose the priorities, which outperformed handcrafted static strategies [3].

What the onboard planner is allowed to change

Deployment was phased, and each phase widens the executive’s authority [5]:

Phase	What the scheduler may do	Status as published
Master and Submaster	nothing; every activity is pinned to a start time on the ground, and separate sequences give exact heater timing	the pre-autonomy baseline [5]
Simple Planner 1, “Accordion”	expand or contract the schedule while keeping activity order and time ranges fixed; take full control of CPU awake and asleep state and of heating	first Mars use planned spring 2023, standard operations from August 2023 [5]
Simple Planner 2	drop the fixed order and time range; schedule opportunistic activities after mandatory ones when time, energy and data volume allow	expected ready 2024 [5]
Simple Planner 3	commit groups, where a set of activities is scheduled only if all fit, and single selection groups, where the best affordable of several options is taken	may be descoped [5]

Mandatory activities are exempt from several constraints, may be scheduled even where an optional one could not, and are not aborted for running past their duration; the planner may still move them so long as their constraints hold [1]. Optional activities must never displace a mandatory one and are aborted if they overrun.

The onboard planner was originally to enter operations about 180 sols after landing [3]. As of September 2020 it was on hold under project schedule pressure [3]. The capability that did run from shortly after the February 2021 landing was the ground half: taking a time grounded plan from the COCPIT planning tool and generating the wake, sleep, preheat and maintenance heating activities [4].

Explaining a non-backtracking scheduler

A greedy scheduler that refuses an activity gives no reason, and the operator has to work out which constraint to relax. Crosscheck reconstructs it [2][6]. It finds the earliest scheduling step at which the failure occurred by binary search over the steps, then identifies the minimal subsets of the activity’s constraints whose valid intervals have an empty intersection, and reports those as the reason together with candidate relaxations [2]. The subset search is worst case O(n 2^n) in the number of constraints, which is tractable only because on realistic plans the largest such minimal subset observed has been three. Crosscheck’s Failure Note field names the constraints that could not be satisfied and the Failure Step field names the activity in conflict; where an activity fails during the sleep and heating phase instead, the Failure Note reports the constraint violated in that phase, such as state of charge or peak power [6]. Copilot shares its core algorithms with the onboard planner, so the ground schedule is built the same way the rover would build it [6].

Ground simulation of a flexible plan is harder than of a pinned one. SSim, the uplink simulator, uses direct copies of the onboard planner flight software modules including the scheduler, plan controller and timeline libraries, with the power and thermal interfaces stubbed because the ground has no access to real battery and temperature state [5]. A Monte Carlo mode running ground scheduling 1000 or more times with different duration predictions was designed to show operators how often all activities schedule and how much they shift, but as published it had not completed development or entered the operations process.

MEXEC: planning and execution in one system

MEXEC represents the plan as a task network rather than a sequence. Each task carries an identifier, a command, a priority, its expected effects as pre, maintenance and post impacts on timelines, the constraints required for execution, control conditions that skip it, and contingencies [7]. Timelines come in atomic, state, claimable, cumulative and cumulative-rate types. The planner cycle commits tasks to the executive, consolidates past impacts on the timelines to reduce memory, schedules tasks in the scheduling window, and optionally repairs conflicts by iterative repair and shifts tasks toward preferred times.

The window structure is what keeps the planner and executive from fighting. The plan process interval must exceed the worst-case planner cycle duration; the commit window is at least that long and determines which tasks are handed to the executive; the plan horizon and the conflict checking window both start after the commit window, so the planner cannot alter a task that may already have begun executing.

MEXEC flew on the ASTERIA 6U CubeSat from 4 to 20 September 2019, commanding observations of HD219134, New York City, the Moon and Vesta [7]. ASTERIA had no spare memory, so buffers were shrunk to make room and MEXEC was fitted into 2 MB, which limited task networks to 100 tasks or fewer, against the few hundred candidate activities a Mars 2020 plan file carries [1]. ASTERIA sequences run to thousands of commands, so tasks issue stored sequences rather than individual commands [7]. All uploaded task networks scheduled and executed in order.

Two flight-observed defects are instructive. ASTERIA reported a stored sequence complete when the command that started it was dispatched, not when the sequence finished, and task durations were inferred from relative sequence command times, so a long-running sequence could let the next task dispatch on top of it; the fix was a precondition that no stored sequence be running [7]. Separately, the planner and executive truncate system time to the nearest second, and the imprecision occasionally caused a task to dispatch or commit one second late.

The second experiment ran on the ASTERIA testbed after contact with the spacecraft was lost [7]. A long-running momentum monitor task carried a maintenance constraint on momentum magnitude, set below the fault protection threshold. When momentum exceeded it, the task failed, the executive dispatched a momentum dump sequence as an immediate response, the planner removed the science observation tasks that depended on the monitor, and a contingency rescheduled the monitor and an observation setup task once momentum dropped to a safe level. The task network crossed the threshold four times and recovered every time without tripping a fault or entering safe mode.

Endurance: planning around 100 km per lunar day

The Endurance lunar rover concept requires roughly 2500 km over four years in the South Pole-Aitken Basin, at about 100 km per lunar day, which puts resource management rather than activity selection at the center of the onboard problem [8]. MEXEC is being adapted for it, the same executive flown on ASTERIA [8].

Two constructs carry most of the work. A supporting task is bound to its primary task either by a start-after-end constraint, as a preheat is to a drive, or by a contained constraint, as maintenance heating is to a drive, and the scheduler queries the functional autonomy layer for the preheat duration given the anticipated start time and current temperatures before deciding whether the group fits [8]. Battery recharge was first left implicit, with the battery charging during idle gaps, which made the scheduler start drives as early as possible and produced chattering between short drives and brief recharge intervals at low state of charge, each drive paying its preheat overhead again. The replacement inserts an explicit recharge task whose duration is computed from the target and current battery energy divided by the difference between generation and idle power, and which typically charges to 95 percent; its remaining defect is power shunting, charging past what the upcoming tasks need [8].

Architecture followed the same cost argument. Waypoint goals were originally handled directly by the system-level autonomy, which coupled it tightly to navigation and was described as fragile and computationally inefficient; a three-layer split inserting a Drive Manager between system autonomy and navigation leaves the scheduler with fewer tasks and events to reason about. Navigation is the competing consumer, and visual odometry load grows with the square of maximum driving speed [8], the same coupling between sensing cost and drive rate that constrains Mars rovers [1].

A field test on 2 October 2025 in the JPL Mars Yard ran 6.5 hours, of which 5.2 hours were autonomous driving covering 4.1 km on a 200-waypoint route at an average 0.8 km/h, with the remaining 1.3 hours spent on communication, simulated recharge, physical battery swaps and four unplanned navigation interventions [8]. All task networks executed as expected and driving resumed after every interruption, a rate the paper notes exceeds any teleoperated lunar or Mars rover flown to date.

Continuous planning on a rover testbed

The precursor is CLEaR, which put the CASPER continuous planner over the TDL task-level executive on the Rocky 7 and Rocky 8 testbeds in the JPL Mars Yard [9]. CASPER generates an activity sequence from science goals and rover state, monitors execution, and repairs the plan by iterative repair when projections change [9]. In the reported scenario the planner ordered science targets with a traveling salesman heuristic, then repaired the plan twice for memory oversubscription by deleting a lower-priority spectrometer read, and once for a navigation deviation after the rover veered off the planned path; a separate obstacle encounter was absorbed by the executive without replanning because enough time margin remained. Position error of 5 to 10 percent of distance traveled, and Sojourner’s average heading drift of 13 degrees per day, are cited as the reason the planner must tolerate the executive’s deviations [9]. No processor, memory or runtime figure is published for the testbed runs. The flown descendant of CASPER, on Earth Observing 1 [9], is covered under onboard science autonomy.

The ground tools

APGEN, the Activity Plan Generator, is part of the Advanced Multi-Mission Operations System and has been applied to Cassini, Deep Impact and EPOXI, InSight, Juno, MRO and MSL [10]. Its scheduling is a two-pass algorithm: the first pass predicts the effect of the current activity plan on spacecraft states and ground resources, and the second examines where activities may be added, given intervals over which a scheduling condition holds for a required length of time. Models are written in a domain-specific language that acquired arrays, global variables, conditionals, loops and function calls over its life, and link to external tools including SPICE, the Multi-Mission Power Analysis Tool, the Dawn attitude control verification tool and the Telecom Forecast Predictor. The Cassini cruise adaptation, the first mission application, defined 61 resources, 345 activity types and 15 constraints [10]. Simulating one encounter sequence on the Deep Impact testbed took 36 hours [10].

Aerie replaces it, along with Blackbird, COCPIT and the German Space Operations Center’s PINTA and PLATO, with a web-deployed system whose mission models are written as an embedded domain-specific language in Java rather than a custom language, so missions can use existing libraries [11]. Simulation is discrete event with integer dense time and transactional concurrent activity semantics, so two activities acting in the same time step do not observe each other’s effects until the step ends. Scheduling is constructive and priority-first over goal types: coexistence, recurrence, cardinality and composites of those. It is deployed as containerized microservices over a PostgreSQL database with a GraphQL API, with synchronous collaboration over web sockets and asynchronous collaboration by branching and merging plans. Europa Clipper is the case study. No simulation runtime or plan size figure is published.

The stated limitation is the same one that constrains the onboard scheduler: the scheduler has limited access to the mission model, cannot infer an activity’s preconditions or effects from its definition, and must simulate to find out, so the eDSL sometimes cannot express a Europa Clipper scheduling goal [11]. Explainability is called out as the open problem there too.