Hazard Detection

Hazard detection converts a stereo point cloud into a statement about where the vehicle can put itself. Two families have flown. GESTALT, on Sojourner’s successors from 2004 through Curiosity, reduces the rover to a point and inflates obstacles by the rover radius [1]. Approximate Clearance Evaluation, on Perseverance, keeps the wheels and the suspension and bounds what the vehicle would actually do on the terrain [3].

Where the height threshold and the driving cycle came from

The criterion underneath every geometric hazard detector, fit a reference ground surface and call anything more than a height threshold above it an object, was established on stereo imagery from Viking Lander 1 [6]. Thresholds of 3, 5, 6 and 7 cm above the fitted ground surface were used on one image pair from the lander’s two facsimile cameras, 0.8187 m apart at 1.3 m above the reference plane, with the points above threshold grouped and approximated by ellipsoids [6]. Scene range in the test area was 3 to 4.5 m at one illumination, so the threshold was never established at rover standoff distances, and there was no independent ground truth for the rock positions, hence no detection or false alarm rate. The same work carried a per-pixel range variance and match probability out of the area correlator rather than a bare disparity, which is what makes a stereo range map usable against a height threshold at all.

The stop-perceive-plan-step cycle that MER, MSL and Mars 2020 still drive on is a consequence of perception cost, not of a control argument. The Stanford Cart took 10 to 15 minutes per meter, nine images per stop through an interest operator, a coarse-to-fine correlator, a camera solver and a path replan on a timeshared DEC KL-10 over a radio link, and completed 20 m indoors in about five hours [7]. Three of its five runs ended on obstacles the interest operator put no feature on, including one outdoor collision, which is the same failure class a modern goodness map addresses by fitting terrain rather than tracking isolated points.

GESTALT

Grid-based Estimation of Surface Traversability Applied to Local Terrain takes the 3D point cloud from stereo and produces a goodness map, also called a traversability map [1][2].

Parameter	Spirit	Opportunity
Map extent	10 x 10 m	12 x 12 m
Cell size	0.2 m	0.2 m
Fitted patch	circle of rover diameter, nominally 2.6 m	same
Point clouds merged before an assessment	up to 10	up to 10

Sources: [1], [2]. For each map cell in turn, the complete set of range points is fitted with a planar patch centered on that cell, the patch being a circle of the rover’s diameter. Four quantities from that fit produce the cell’s goodness: the surface normal, the RMS residual, and the minimum and maximum elevation difference from the best fit plane [1]. These correspond to the three named hazard classes: Step Obstacles, large elevation deltas from the fit plane; Tilt Hazards, large angle between the surface normal and the up vector; and Roughness hazards, the residual of the planar fit [2].

Goodness maps from successive range images are registered and accumulated using modulo map indexing, which bounds the map without scrolling; new data overwrites old where they overlap [1]. The merged map is then used to score a fixed set of candidate steering trajectories: 23 forward arcs, 23 backward arcs and two point turns, evaluated every driving cycle by summing goodness along each arc with nearby cells weighted more heavily. The votes go to an arbiter that also weighs operator-supplied waypoints, and the rover drives a fixed distance along the winning arc, set by operators anywhere from 35 cm to 1 m or more depending on terrain and the distance goal for the sol, before stopping to image again [1].

What it cost

A GESTALT cycle takes about 70 s on the MER flight processor [1]. Peak driving speed is 5 cm/s and the rovers were typically driven at 3.75 cm/s for power reasons, but with computing time included the median net driving speed under autonomous navigation was about 0.6 cm/s. The response was the hybrid daily drive: operators plan a blind segment as far as they can verify safety in navigation and panoramic camera stereo, the rover drives that blind, then switches to autonomous navigation for whatever time remains. Spirit’s longest commanded drive to mid-June 2004 was 124 m on sol 125, 62 m directed and 62 m under Terrain Assessment with Local Path Selection [1][2]. Opportunity’s longest planned drive, a February 2005 holiday weekend, was 106 m of Local Path Selection with no vision processing followed by 284 m with Terrain Assessment over sols 383 to 385, in segments of 70, 104 and 110 m, with humans reviewing telemetry each sol but sending no further commands after the first day.

As of 15 August 2005, onboard terrain assessment had been used for 1354 m of Spirit’s 4798 m and 1379 m of Opportunity’s 5947 m, about 25 percent for both [2]. Nearly a third of Spirit’s more than 2 km trek to the Columbia Hills was driven under Terrain Assessment, which the mission credits with reaching the hills 50 percent sooner than directed driving alone would have allowed safely.

Failure behavior

The asymmetry that governs the design is that a false positive, a safe path assessed as unsafe, is acceptable, and a false negative, an unsafe path assessed as safe, is not [3]. GESTALT is therefore built conservative, and its documented failure mode is the false positive. Representing the rover as a point and inflating obstacles by the rover radius means a rock that the vehicle could straddle with the belly pan clear is treated as impassable, and GESTALT is known to fail frequently in high rock density. In a MATLAB reimplementation driven over 80 randomly generated 30 by 40 m terrains at four cumulative fractional area rock coverages, the GESTALT-equivalent planner reached a goal 20 m away in only 40 percent of runs at 10 percent CFA, and failed to find any path at 15 and 20 percent CFA [3]. Its paths were also the most winding of the three planners compared.

The opposite failure appeared early in flight: GESTALT was tuned after landing to overcome excessively conservative behavior at slope changes [1]. On the Meridiani plains the only geometric obstacles were occasional hollows from small infilled craters, and inside Eagle and Endurance craters the binding hazards were slope and slip rather than obstacles at all [1], which is the limitation that motivated slip prediction and terrain classification [5].

Approximate Clearance Evaluation

ACE replaces the point-plus-inflation model with bounds on the vehicle’s actual state. From a terrain height map it estimates the lowest and highest height each wheel may reach at a given pose, then derives conservative upper and lower bounds on body clearance, roll, pitch and rocker and bogie angles from those extreme wheel heights, without iterative optimization [3]. The bounds are guaranteed conservative, so a pose ACE calls safe is safe; the gain over GESTALT is that a rock in a wheel track is no longer automatically an obstacle, because the belly pan clearance is evaluated rather than assumed away.

Platform	Configuration	Time per pose evaluation
RAD750, as on Curiosity and Mars 2020	10 cm resolution DEM	10 to 15 ms
NVIDIA Jetson TK1, Athena rover	single pose	11.2 microseconds
NVIDIA Jetson TK1, plane fitting for comparison	about 100 points	26.1 microseconds
NVIDIA Jetson TK1, plane fitting for comparison	about 200 points	68.2 microseconds
Intel Core i7 at 2.8 GHz	single pose	2 microseconds

Source: [3]. The RAD750 figure is given as typical, with the note that precise timing is hard given the specialized configuration of the flight software. Constant execution time is the property that matters operationally: because ACE is closed form, its cost does not depend on terrain pattern, where an iterative method needs more iterations on rough ground.

Measured against the same 80 terrain benchmark, ACE-based planning held a success rate of at least 95 percent up to 15 percent CFA, against 40 percent for the GESTALT equivalent at 10 percent CFA, and its success rate fell off sharply at 20 percent CFA [3]. All three planners used the same depth-five tree search with 1.5 m edges and a collision check every 0.25 m; only the collision check differed.

ACE’s own failure mode is residual conservatism. In a Jezero crater simulation with rocks populated at 10 percent CFA, the bounds always contained the ground truth, with the span between upper and lower bound within a few degrees most of the time, but at one point the upper bound on pitch reached about 10 degrees against an actual 1 degree [3]. These false alarms occur when a large rock lies in a wheel box that the rover did not in fact step on [3]. ACE was validated on the Athena rover, MER sized, and on Scarecrow, the MSL mobility testbed, in the JPL Mars Yard.

The cost of hazard checking inside a planning cycle

On Perseverance, Enhanced AutoNav ranks candidate paths and calls ACE to check the top-ranked ones. The number of ACE calls per planning cycle is therefore the compute budget for hazard detection. The overthink threshold is 275 calls, about 3 to 4 s at 10 to 20 ms per call, and exceeding it means the highest-ranked paths were all rejected and the rover may have to stop driving before a solution is found [4]. Evaluating the entire baseline tree of 1694 candidate paths at 25 cm intervals would take more than 22,000 calls and over 3 minutes of computation, which is why the ranking exists at all. In Monte Carlo simulation on complex terrain, replacing the ranking heuristic with a learned one cut the overthink rate from 20.0 percent to 7.1 percent and path inefficiency from 25.4 to 20.4 percent, with no trial failure caused by a violated safety constraint in any experiment [4].