Timing and Scheduling

A planetary rover runs a motor control loop measured in tens of milliseconds and a perception step measured in minutes on the same processor. How those coexist is a scheduling problem that has been solved differently on each vehicle, and the solution determines the drive rate.

The fast end

MER and MSL surface software is built around an 8 Hz tick [1]. The MER cruise attitude control task carries an 8 Hz rate requirement, and several tasks wait on the 8 Hz time event, with task priority alone deciding the order in which they execute after it arrives [1]. On Curiosity, Traction Control evaluates the commanded speed of each of the six drive wheels at 8 Hz, and its high rate downlink products are collected at that rate; drive telemetry for the sol 1646 and sol 1662 checkout drives was logged at 64 Hz [8].

There are no rate groups. A task with a rate requirement subscribes to the timer module, which delivers a message at the required interval into a higher-priority queue than the task’s command queue, so periodic work runs before commands within the same task and commands execute in the gaps between time events [1]. Tasks with no rate requirement are purely event driven and never poll.

The Pathfinder 1553 bus cycle is the sharpest published deadline in this family [2]. Its timeline repeats every 0.125 s: bus hardware starts on the 8 Hz boundary using transactions set up by the previous cycle, the distribution task wakes when traffic completes and distributes the data, then the scheduler task wakes and sets up the next cycle. The scheduler is the highest priority task in the system apart from the VxWorks tExec task, the distribution task third, and each checks every cycle that the other completed [2]. Failure of that check is a hard deadline miss, and the response is a computer reset. The hardware inherited from Cassini imposed the 8 Hz rate, and the software architecture followed from it [2].

The slow end

Step	Vehicle	Processor	Time
Visual odometry tracking step	Spirit, Opportunity	20 MHz RAD6000	up to about 3 minutes
Autonomous navigation pause per step	Spirit, Opportunity	20 MHz RAD6000	about 120 s
Autonomous navigation pause per step	Curiosity	133 MHz RAD750	about 120 s
Autonomous navigation pause per step	Perseverance	133 MHz RAD750 plus Virtex-5 FPGA	typically 0 if not steering
Single ACE pose evaluation	Perseverance class	133 MHz RAD750, 10 cm DEM	10 to 15 ms
Single ACE pose evaluation	Athena rover	NVIDIA Jetson TK1	11.2 microseconds
Plane fit, 200 points, for comparison	Athena rover	NVIDIA Jetson TK1	68.2 microseconds
Global localization against orbital imagery	Perseverance	Snapdragon 801, four cores at 2.36 GHz	about 32 s

Sources: [3] for MER visual odometry, [4] Table 1 for the navigation pauses, [6] for ACE, [7] for global localization.

At most 75 percent of the MER RAD6000 is available to autonomy software during normal operations, and telemetry processing can take more than the remaining quarter [3]. A three minute stereo and visual odometry step has to fit in that budget alongside the 8 Hz mobility work. On MER and MSL the vehicle stops: the rover drives a step, halts, thinks for about two minutes, and drives again [4].

Making the slow step overlap the fast one

Three different mechanisms have been flown or demonstrated to remove that stop.

Thinking While Driving, developed for Curiosity from 2015, starts the next drive step immediately after image capture so that the motion estimate is computed while the wheels turn [11]. On the flight-like engineering model, nine runs averaged 51.5 m/h without it and 77.5 m/h with it [11]. The cost is localization latency: a large slip is not detected until two 1 m steps have completed rather than one.

Moving the work off the general purpose processor. Perseverance’s Vision Compute Element is a second RAD750 board carrying a Xilinx Virtex-5QV FPGA that runs stereo correlation and visual odometry image processing at 22 million disparities per second, processing about six times as many pixels per step as Curiosity in less time [4]. For the first time the autonomous drive rate is set by the wheel drive motor rotation rate rather than by sensing or computing [4].

Moving the work to a co-processor with a different operating system. When Ingenuity is not flying, its base station Snapdragon 801 is available to Perseverance as a co-processor [7]. The performance and reliability figures are opposed [7]:

	Perseverance RAD750	Heli Base Station Snapdragon 801
CPU	133 MHz x2	4 cores at 2.36 GHz
Memory	128 MiB ECC RAM	1.55 GiB non-ECC RAM
Storage	2 GB validated ECC	32 GB unvalidated ECC
Operating system	VxWorks 6.7	Linux 3.8
Accelerators	FPGA on the Vision Compute Element	GPU, DSP
Radiation hardened	yes	no
Simulated upsets per device per day	13, corrected	4313, uncorrected

Source: [7], Table 1. The division of labor that follows is that the RAD750 handles critical real-time processing and the Snapdragon runs computationally intensive programs that can be verified independently and run offline. Global localization takes about 32 s of Snapdragon time against an order of magnitude longer on the RAD750, and it was given 0.5 GB of memory, more than the RAD750 has available at all [7]. Most of the wall clock cost is not computation: transferring images and metadata from the Rover Compute Element to the base station over a 10 KB/s serial link takes 30 minutes, which is tolerable only because it runs in parallel with other rover activities.

Scheduling isolation on the co-processor is deliberately primitive: the Linux change-root call for file system isolation, and ulimits, chrt and taskset for resource isolation, chosen over Docker or LXC to avoid uplinking additional software or interfering with Ingenuity operations. It was tested against deliberately malicious code including memory leaks, segmentation faults, thread bombs and file system erasure [7]. Radiation is handled by running the algorithm twice with a reboot between the runs and comparing results, with a 3 minute timeout on each localization run and 1.5 minutes for the reboot, so a stalled run is caught by the clock rather than by inspection.

Planning cycles and overthinking

Perseverance’s Enhanced AutoNav plans while the vehicle is moving, and the timing question becomes whether a solution is found before the current maneuver ends. If it is not, the rover has to stop, which the developers call overthinking; it lowers the average traverse rate, adds wear to wheels and brakes, and raises mission risk [5]. The metric is the number of Approximate Clearance Evaluation calls per planning cycle, and the overthink threshold is 275 calls, which at 10 to 20 ms per call is 3 to 4 s of computation. Evaluating the whole baseline tree of 1694 candidate paths at 25 cm intervals would call ACE more than 22,000 times and take over 3 minutes [5]. In simulation, replacing the path ranking heuristic with a learned one cut the overthink rate on complex terrain from 20.0 percent to 7.1 percent, and a hand-designed convolution heuristic cut it to 14.2 percent with a margin of error of 2.5 percent [5].

ACE exists because its predecessor’s cost is not bounded. Fitting a rover-sized plane to terrain, the basis of GESTALT, is an approximation whose cost varies, and full articulated suspension settling by iterative nonlinear optimization is described as intractable on a RAD750 [6]. ACE has a closed form, so its computation time is constant regardless of terrain pattern, which is what makes a per-cycle call budget meaningful.

Scheduling below the task level

Not all timing is task scheduling. MER camera exposure is specified in units of 5.1 ms [9]. The imaging chain uses two queues per priority level, one for mast-mounted cameras and one for body-mounted, and hands each image to a separate post-processing task as soon as its pixels are read so that the camera control task can start the next exposure, with the result that image acquisition order cannot be predicted from command order. Fault protection is polled rather than interrupt driven: the MSL engine periodically polls monitor states and maps a monitor that has turned red to a system response, and monitors use persistence counts so that a single bad reading does not trip a response [10].