Autonomous Navigation

Autonomous navigation is the onboard selection of the next drive step from stereo range data, without a human having seen the terrain. It exists because a rover commanded once per sol can only be driven blind as far as the previous sol’s imagery resolves the ground, and because the round trip light time forbids a human in the control loop [1].

What it computes

Input is one or more stereo pairs, the current pose estimate, a goal waypoint and a set of human-specified keep-in and keep-out zones. Output is a single arc or turn-in-place command and an updated traversability map. The Mars rovers have used two generations of the same decomposition: build a geometric hazard map from stereo range, score a set of candidate motions against it, execute one, repeat [1][2][4].

GESTALT, MER and MSL

GESTALT (Grid-based Estimation of Surface Traversability Applied to Local Terrain) fits rover-sized patches of the stereo point cloud to a plane and evaluates three hazard classes against it: step obstacles, taken as large elevation deltas from the best fit plane; tilt hazards, taken as a large angle between the surface normal and the up vector; and roughness, taken as the residual of the planar fit [1]. The result is a rover-centred traversability grid, 10 x 10 m on Spirit and 12 x 12 m on Opportunity, both at 0.2 m cells, and as many as ten separate point clouds could be accumulated before an assessment was run.

Stereo feeds it. MER used a windowed 1D search along epipolar lines with a sum of absolute differences metric on images captured binned at 1024x256 and downsampled and rectified to 256x256 [1]. Spirit typically used the 125 degree field of view front and rear HazCams for about 15,000 3D points per pair, Opportunity the 45 degree NavCams for about 48,000.

Curiosity kept GESTALT with a coarser grid, a World Map at 40 x 40 cm cells over 10 x 10 m, updated at the end of each drive step from one HazCam pair and several NavCam pairs [2]. Forward mapping takes three NavCam pairs at -54, -14 and +26 degrees azimuth covering 2.5 to 10 m, plus a front HazCam pair covering 0.3 to 3 m, all captured at 256x1024 and processed at 256x256 [2]. Backward mapping is more expensive because the rear HazCams must be supplemented by two 30 degree turns in place, each producing a near pair at 256x256 and a horizon pair processed at 192x1024.

Curiosity added a global planner. After each drive step the World Map is merged into a Global Map at the same resolution over a default 50 x 50 m, and a version of Field D* selects a globally optimal path across it [2]. Planning is done in the 2.5D world model with no prediction of future slip. Four path selection strategies are available: Directed, which ignores the map; Guarded, which drives at the goal but halts before entering a hazard or keep-out cell; AvoidKOZ, which avoids only human-specified keep-out zones; and AutoNav, which avoids both. Waypoint-style driving was used in 33.2 percent of the first seven years of attempted drives [2].

The optimality that D* guarantees is optimality at every state of the traverse with respect to all information known at that step, conditional on the arc cost corrections received from the sensor being correct and on the robot’s state in the graph being known exactly [10]. Neither condition is met on a rover: the map is built from stereo range with a noise floor that grows with distance and an occluded footprint, and the pose feeding it carries the slip and localization error that visual odometry exists to bound. The speedup that made incremental replanning affordable, close to 300 times faster than brute-force replanning with A* on a 1,000,000-state grid, was measured in simulation on randomly generated grids with an idealized omnidirectional sensor of 10 states radius and perfect detection inside it, timed on a 1994 workstation, and the author states it depends strongly on obstacle density and on the ratio of known to unknown obstacles [10].

ENav and Approximate Clearance Evaluation, Mars 2020

ENav replaces the goodness-grid-plus-arc-vote scheme with an explicit search over a tree of candidate paths and a separate safety oracle [4]. The planning cycle is: process disparity into a 2.5D heightmap centred on the rover; assign each cell a traversal cost, infinite inside a keep-out zone and finite but elevated for unimaged terrain; rank the candidate path tree by a cost that combines maneuver time, sampled terrain cost and a Dijkstra estimate of cost to go from the path end to the global goal; run Approximate Clearance Evaluation on paths in ascending cost order; actuate the first maneuver of the cheapest ACE-validated path.

The default tree is 14 candidate turns in place including the null turn, followed by two levels of 11 3 m arcs of varying curvature, 1694 paths in total, planning about 6 m ahead [4]. ACE takes the rover pose and the heightmap, finds the minimum and maximum terrain height inside the potential footprint of each wheel, and returns infinite cost if the resulting attitude and clearance bounds violate parameterized limits.

Cost on flight hardware

	Spirit and Opportunity	Curiosity	Perseverance
Autonomy processor	20 MHz RAD6000	133 MHz RAD750	133 MHz RAD750 plus Virtex-5QV on a second RAD750 board
RAM	128 MB	128 + 512 MB	128 MB x2 plus 512 MB x2
Stereo pixels per step	10,000 to 50,000	40,000 to 200,000	240,000 to 1,200,000 on the FPGA
Autonomous navigation pause per step	about 120 s	about 120 s	typically 0 if not steering
Speed penalty against directed driving	4 to 10 times slower	4 to 10 times slower	none reported

Sources: [5] Table 1 for the hardware and pause columns, [3] for the speed penalty on MER and MSL, for the Mars 2020 entry.

At most 75 percent of the MER RAD6000 was available to autonomy software, and dynamic allocation was discouraged, leaving fixed pools of 4 MB, 9 MB and up to ten further 2 MB blocks whose use cut into the memory available for image processing [1]. The same processor ran more than 90 concurrent VxWorks tasks, and instrument interfaces were not optimized for speed: acquiring one image and storing it in RAM took a minimum of 5 s [7]. MSL was expected to generate about 100 W on average, which does not permit keeping every sensor powered and the CPU highly utilized for long.

ENav’s cost is dominated by ACE. Each evaluation takes an estimated 10 to 20 ms on the Perseverance RAD750 [4]. The baseline configuration averaged 275 evaluations per planning cycle in benign terrain and 377 in complex terrain, about 4.5 s of ACE per cycle [4]. ENav is defined to be overthinking when a cycle exceeds 275 evaluations, roughly 3 to 4 s of computation, which forces the rover to stop until a path is found; Monte Carlo simulation predicted a 20.0 percent overthink rate in complex terrain and rare exceedance in benign terrain. Evaluating the entire 1694 path tree at 25 cm intervals would call ACE more than 22,000 times and take over 3 minutes [4].

Two heuristics were tested against that budget over 780 Monte Carlo trials per terrain class [4]. A gradient convolution heuristic using Sobel operators cut complex-terrain path inefficiency from 25.4 to 19.9 percent and the overthink rate from 20.0 to 14.2 percent, at a success rate of 67.1 against a 69.9 percent baseline. A learned ACE-probability heuristic reached 72.5 percent success, 20.4 percent inefficiency and a 7.1 percent overthink rate [4]. With no minimum evaluation count, the learned heuristic cut complex-terrain ACE evaluations from 377 to 90, about 1.1 s rather than 4.5 s per cycle. No trial in any experiment failed through a violated safety constraint; all failures were timeouts or no-path outcomes.

Measured performance

MER used onboard terrain assessment for 1354 of Spirit’s 4798 m and 1379 of Opportunity’s 5947 m as of 15 August 2005, about 25 percent of distance for both [1]. Spirit’s longest commanded drive was 124 m on sol 125, 62 m directed followed by 62 m under Terrain Assessment and Local Path Selection [1]. Nearly a third of Spirit’s traverse to the Columbia Hills was driven under Terrain Assessment, and it reached the hills about 50 percent sooner than directed driving alone would have allowed. Opportunity’s longest planned drive covered 390 m over sols 383 to 385, of which 284 m was autonomous in 70, 104 and 110 m increments with no commands sent after the first sol [1].

Curiosity accumulated 1116.7 m of AutoNav odometry in total by 14 April 2022, limited by wheel damage and by sampling priorities rather than by the algorithm [5]. Perseverance drove 4802 m of AutoNav odometry during the 31 sol Rapid Traverse Campaign alone, 94.8 percent of the campaign’s 5063.4 m, at an average 79.7 m/h over a modeled 2.98 h of driving per sol [5]. Strategic planning for that campaign assumed peak AutoNav rates of 200 to 250 m/sol, and chose a 4.8 km route over a 2.4 km one on that basis, because the shorter route crossed the Seitah ripple field where AutoNav was expected to yield under 50 m on many sols. Mid-drive waypoints were set about every 120 m [5].

Perseverance drive mode	Distance to sol 1710	Duration	Effective rate	Share of odometry	Longest sol
AVOID_ALL	31,857.00 m	343.76 h	92.67 m/h	75.28 percent	403.00 m, sol 1540
GUARDED	257.05 m	2.81 h	91.32 m/h	0.61 percent	39.00 m, sol 1292
UNGUARDED	9910.53 m	120.20 h	82.45 m/h	23.42 percent	93.32 m, sol 1288
AVOID_KOZ	0.00 m	0.00 h	not used	0.0 percent	none

Source: [6], Table 1. AVOID_ALL avoids both stereo-detected geometric hazards and human-specified keep-out zones; GUARDED runs the same onboard terrain assessment and visual odometry but stops rather than steering around an obstacle; UNGUARDED follows the uplinked path and ignores whatever image processing is enabled.

The 9.6 m/h gap between AVOID_ALL and UNGUARDED is the entire remaining cost of onboard hazard avoidance on Perseverance, against the 4 to 10 times penalty carried by MER and Curiosity [3][6]. Records set under autonomy include 319.786 m on sol 351, 520.499 m in a single plan on sol 399, 528.7 m over sols 404 to 405, 699.9 m over sols 407 to 409 with no human path input across three sols of driving, and 411.7 m on sol 1540 of which 403 m was autonomous [5][6].

Failure modes

Conservatism against unknown terrain is the dominant one. M2020 AutoNav depends on mast-mounted NavCam stereo, and sand features produce gaps in the onboard stereo results; in complex terrain with dense rocks, frequent outcrops or coverage gaps, the conservative hazard assessment reduces path efficiency and can stop progress entirely [5]. The sol 385 drive terminated on a no-path fault after AutoNav determined there was no route to the goal [5][8].

Position uncertainty propagates into the map. Perseverance grows every human-specified keep-out zone by the accumulated position uncertainty, which is assumed at 5 percent of distance driven when visual odometry converges and 50 percent when it does not, so a run of convergence failures inflates the keep-out geometry until the planner can no longer find a corridor [8][9]. Onboard global localization against orbital maps exists to reset that term [8].

The planner has no slip model. Curiosity’s global path planning runs in the 2.5D world model without predicting future slip [2], and the ENav work attributes the path inefficiency of the baseline to ACE finding narrow safe paths that disappear once slip occurs, forcing backtracking or tight turns [4].

Mapping cost shapes the drive pattern rather than the map. Curiosity’s autonomous imaging capabilities can be used together but in practice are used independently, because combining them costs seconds of extra image processing plus mast repointing that can only happen while the vehicle is stopped [2]. Backward AutoNav is the extreme case, requiring two 30 degree turns in place per mapping cycle.