Terrain Relative Navigation

Terrain relative navigation (TRN) estimates a vehicle’s position with respect to a map of the body it is approaching, by matching features in descent imagery against that map. It converts an inertial navigation position fix, which for Mars entry can be in error by as much as 3.2 km, into a map-relative fix good enough to steer between hazards that were identified in orbital data before launch [1].

Source: [1]. Public domain (NASA / US government work).

Design space

The technique traces to 1950s cruise missile radar map matching, and took decades of research tasks, field tests and one narrower flown ancestor before Mars 2020 made map relative localization an operational EDL function [9]. Three sensing approaches have flown or been flight-tested, and each trades illumination independence against range and update rate. Camera based matching, flown on Mars 2020 and OSIRIS-REx, needs sunlit terrain that resembles the reference map and is the only approach demonstrated at the multi-kilometer altitudes and tens of meters per second descent rates that Mars entry forces [1][3]. Flash lidar based hazard detection and hazard-relative navigation, flown on the Morpheus rocket lander at Kennedy Space Center in 2014, is illumination independent but pays for it in gimbal scan time, about 6 s to mosaic a 60 x 60 m elevation map from 460 m slant range, and its compute element split a real-time FPGA front end from a manycore Linux processor specifically to keep hard timing off the operating system [10][11]. Radar based localization reuses a terminal descent radar already carried for velocity and altitude: reprocessing the Mars 2020 six-beam terminal descent radar returns through a factor graph smoother gave a usable position estimate at 6.4 km altitude, almost 2 km before the camera based LVS begins, though each scan takes about 10 s to accumulate against the radar’s 20 Hz beam rate [12]. No flown mission has needed to choose between these approaches on one vehicle; each was selected for the illumination and timeline constraints of its own mission.

What it computes

Input is a sequence of descent images, an onboard map of the landing area, inertial measurement unit data, and an initial state estimate [1][3]. Output is a map-relative position, velocity and attitude, and on Mars 2020 a landing target that the Safe Target Selection function derives from it [7]. The answer must be produced inside the descent timeline, which on Mars 2020 is 10 s [8].

Map Relative Localization, Mars 2020

The Lander Vision System (LVS) reduces an initial 3.2 km horizontal position error to 40 m in 10 s, with a degraded requirement of 54 m at 6 s to cover a late start or a reboot inside the operational window [1]. The requirement is to be met over all possible EDL conditions, which is what the field test campaign was built to demonstrate [8]. Processing is coarse to fine, in four stages [1]. The initial state seeds inertial propagation and crops the onboard map, which is about 12 km on a side, with computational constraints capping any processed map at 1024x1024 pixels. At 4200 m above ground level, coarse matching runs five large patches in each of three descent images against a coarse map at about 12 m/pixel, fused with propagated IMU data to give a horizontal correction [1]. The coarse correction then crops a fine map 6 km on a side at 6 m/pixel, and fine matching runs up to 150 small patches per descent image as measurements into an extended Kalman filter estimating position, velocity, attitude and IMU biases. The 40 m requirement is met after three fine images, and processing continues to 2000 m AGL or until the spacecraft reports backshell separation [1].

The operational envelope the algorithm must hold across is vertical velocity 65 to 115 m/s, horizontal velocity to 70 m/s, attitude rates to 50 deg/s, off-nadir angles to 45 degrees, mean terrain slope to 15 degrees and terrain relief to 150 m standard deviation within a 1500 x 1500 m coarse landmark footprint, sun elevation 25 to 55 degrees and image entropy as low as 3.0, roughly 8 DN of contrast in a 256 DN image [1]. The same envelope drove the field test campaign of May 2019, which flew an engineering model camera and inertial measurement unit on a two-axis gimbal on the front of a helicopter over six test sites in the Mojave National Preserve and Death Valley, chosen for cliffs, lava flows, dune fields, salt flats and bland slopes resembling Jezero Crater, with the Vision Compute Element and its flight software in the cabin and over 600 real-time runs executed [8].

A helicopter can only descend a few meters per second, far short of the 65 to 115 m/s vertical velocity a real Mars entry forces, so the field test could not by itself demonstrate that vertical motion does not corrupt the horizontal position estimate [1][13]. That gap was closed three separate ways: replaying real Mars Science Laboratory descent imagery and descent IMU data against an orbital map, a 250-run Monte Carlo of simulated parachute descent to Northeast Syrtis, and synthetic descents stitched from real field-test images taken up ascending helicopter spirals over Kelso Sand Dunes. All three agreed that vertical velocity does not significantly affect horizontal position estimation [13]. Pre-launch verification also depended on a ray-traced camera simulator, validated after landing by rendering the reconstructed flight trajectory and comparing it against two downlinked LCAM images: the renderer reproduced the opposition effect location and the dust-driven contrast reduction to within a few data numbers, while under-predicting the darkening at the image corners [14].

DIMES, Mars Exploration Rovers

The first flown ancestor solved a narrower problem: horizontal velocity rather than position. MER’s radar could not measure horizontal velocity relative to the surface, and atmospheric models predicted sustained winds able to impart more horizontal velocity than the airbag landing system was rated for [6]. The Descent Image Motion Estimation System took three images 2.5 s apart from a target altitude of 2000 m, projected them onto the nominal ground plane using radar and attitude measurements, tracked two surface features between each image pair, and differenced the two resulting velocity measurements to check the implied average acceleration against the accelerometers [6]. Its budget was to acquire three images at 3.75 s each and analyze them within 17 s using no more than 40 percent of the 20 MHz CPU, with the whole system flight-qualified in under two years. Design work covered image smear at slew rates to 60 deg/s and correction of radiometric and frame-transfer artifacts [6]. DIMES produced velocity measurements for both rovers; Opportunity’s horizontal velocity was already inside the airbag envelope, while Spirit met higher winds and the DIMES estimate was required to bring horizontal velocity inside the airbag rating by firing the transverse impulse rocket motors seconds before impact.

Natural Feature Tracking, OSIRIS-REx

NFT estimates the spacecraft orbital state by matching cataloged surface features. For each expected feature it holds a small digital elevation model and co-registered albedo, renders the expected appearance from the predicted spacecraft position, spacecraft attitude, asteroid attitude and sun vector, and matches that render against the NavCam image by normalized cross correlation [3]. Two metrics qualify each match: the correlation score, and the pixel error between the correlation peak and its predicted location. Matches feed a Kalman filter that updates the trajectory estimate.

The sequence is fixed. Orbit departure occurs about 1 km from Bennu’s center, roughly 4 hours before Checkpoint at 125 m altitude, where NFT updates the burn; Matchpoint follows 10 minutes later at 50 m and sets horizontal velocity to match surface rotation; contact is a free fall at -10 cm/s vertical, followed by a 70 cm/s backaway burn [4]. NFT continues processing images through final descent to predict the time and position of contact.

Cost on flight hardware

	Mars 2020 LVS	OSIRIS-REx NFT
Processor	BAE RAD750, build-to-print from MSL, under VxWorks	spacecraft flight computer, not published in the cited work
Accelerator	Xilinx Virtex5QV Vision Processor FPGA on the Computer Vision Accelerator Card	none reported
Second FPGA	RTAX2000 housekeeping, burn-once, loads the Vision Processor	not applicable
Memory	32 MB rad-hard NOR, 1 GB DDR2 SDRAM, 16 GB NAND	not published in the cited work
Camera	LCAM, 1024x1024 global shutter, 90 x 90 deg FOV, about 1 ms exposure, about 100 ms latency, under 1 kg	NavCam
Time budget	40 m in 10 s, 54 m in 6 s	Checkpoint at 125 m, Matchpoint 10 min later at 50 m

Sources: [1] for the LVS column except where noted, [4] for the NFT sequence.

Hundreds of landmarks cannot be matched in under 10 s on a standard flight processor, which is why the LVS carries a dedicated Vision Compute Element rather than running on the Rover Compute Element [1]. The VCE is three cards in a 6U chassis on a cPCI backplane: a power conditioning unit and a RAD750 board, both build-to-print from MSL, and the new Computer Vision Accelerator Card. As flown, the LVS comprises the VCE, the LCAM, the descent IMUs and the Safe Target Selection function that consumes the position fix [7]. The LVS interfaces to the rover compute elements over 1553 at 8 Hz in both directions, and takes inertial data from the descent stage Descent IMUs over RS-422 through a Y-splitter [1]. Flight software runs on a deterministic timeline in which image exposures and landmark match updates occur at fixed times relative to LVS initialization [1]. The internal rates are about 1 Hz megapixel grayscale images from the LCAM and 8 Hz state packets in each direction over 1553.

Source: [1]. Public domain (NASA / US government work).

The LCAM had to take crisp images under high attitude rates with a global shutter and low exposure time, deliver them to the VCE with low latency, and hold a field of view wide enough to cover a useful area of the map at up to 45 degrees off nadir, all inside 1 kg on the outside of the rover [1]. Because it operates only during EDL it does not have to survive surface diurnal cycles, which relaxed its thermal qualification.

The as-built LCAM uses an On Semiconductor Python 5000 detector windowed from 2592x2048 to 1024x1024 in 2x2 summed mode, 9.6 micrometer effective pixel pitch, 1.67 mrad pixel scale, f/2.7 at 5.8 mm focal length, 480 to 720 nm, 880 g, 82 x 102 x 154 mm, 480 Mbps LVDS video output [2]. After landing the camera interface FPGA is reconfigured to support surface stereo and visual odometry processing, which is what makes the same box useful for the rest of the mission.

Reuse after landing

The LVS hardware does not stop working at touchdown. The Vision Compute Element remains powered as a second RAD750 board on the rover, and after landing the camera interface FPGA is reprogrammed for surface stereo correlation and visual odometry [2][5]. That reprogrammed Virtex-5QV is what raises the stereo throughput to 22 million disparities per second and lets Perseverance process 240,000 to 1,200,000 stereo pixels per drive step against 40,000 to 200,000 on Curiosity [5]. A terrain relative navigation sensor bought for 10 s of descent therefore pays for the surface autonomy budget of the whole mission.

Measured performance

The LVS error budget was closed at a 17.3 m root sum square current best estimate against a 28.2 m allocation, both at the 99th percentile [1], against the 40 m requirement:

Error source	Current best estimate (99th percentile)	Allocation
Algorithm resampling, warping, correlation	0.6 m	1 m
DIMU accelerometer and gyro noise	0.4 m	1 m
LCAM image noise and radial distortion	1.1 m	5 m
LCAM focal length error	16.9 m	20 m
LCAM to DIMU misalignment	3.0 m	15 m
Map distortion and rotation	3.4 m	12 m
Total, root sum square	17.3 m	28.2 m

Source: [1], Table 2, dated 29 September 2016.

The dominant term is calibration, not vision. Focal length is estimated to about 1 percent from images of a dot grid on a flat target board, and a 1 percent error shifts the point where the landmark bearing vectors intersect, which produces up to 17 m of horizontal position error when the camera looks off nadir [1]. The algorithm itself contributes 0.6 m, one tenth of a map pixel, measured on a flat high-contrast synthetic map with all sensor and map errors disabled. In flight the local distortion of the map, the largest predicted error contributor, was measured after landing at about 3 m standard deviation, and about 1.5 m over the region where most landmarks were matched [7]. LCAM to DIMU misalignment of 0.75 deg/axis, which shock, parachute dynamics and thermal drift can produce across the slipping cup and cone interface between rover and descent stage, is absorbed into the attitude estimate and costs no more than 3.0 m of position [1].

Simulation over the North East Syrtis site returned horizontal position error under 14.8 m and vertical error under 45 m after six images, inside the root sum square budget [1]. The map itself was specified to under 150 m horizontal and 20 m vertical position error, under 1 mrad orientation error, local distortion under 6 m below 120 m baselines and 12 m above, and 2 m 1-sigma pixel-to-pixel elevation error; the horizontal map error cancels at system level because the hazard map is co-registered with the LVS map.

Flight results from 18 February 2021, compared against the reconstructed trajectory, give velocity errors under 0.25 m/s and attitude errors under 0.05 degrees in two axes and 0.1 degrees in the third, against a 40 m position estimation requirement [7]. LVS marked its position estimate VALID on the first fine image, which matched 150 landmarks for 92 inliers, and held the highest localization accuracy ranking for all 42 fine images matched down to 500 m, every one of them with 80 or more inliers. Coarse landmark correlation peak heights from EDL agreed with the two helicopter field test runs and with simulation, while the interest operator score was lower than in the field tests because Jezero Crater is dustier and lower in contrast than the terrestrial sites. Total landing error was 5 m from the targeted location against a 60 m requirement [7]. The vehicle landed safely surrounded by hazards, and the paper records terrain relative navigation as planned for the Mars Sample Retrieval Lander if that mission is approved for implementation. TRN diverted Perseverance a few kilometers east of the Jezero delta to avoid hazards, which is what the Rapid Traverse Campaign of March 2022 later had to drive back [5].

The full engineering record of the same flight puts the in-flight LVS position error at about 3 m against the 40 m requirement, and attributes more than 60 percent of the pre-flight 33 m error budget, 20 of 33 m, to reference map error rather than to the algorithm; a set of map corrections against the CTX orbital imagery reduced that map error about sevenfold before launch [9][15]. In flight LVS matched all 15 coarse landmarks, producing a 137 m position correction against a design case of up to 3.2 km, and delivered its first valid fine estimate 5.84 s after coarse processing began [15].

What comes next

The Mars Sample Retrieval Lander would remove the landing Doppler radar Mars 2020 still carried and make an extension of LVS, the Enhanced Lander Vision System, the sole EDL navigation sensor from the heading-alignment phase of hypersonic entry down to 50 m altitude, targeting a 60 m pinpoint landing [16]. Preliminary design Monte Carlo results close every axis with margin, for example 15.0 m 99th-percentile horizontal position error against a 35 m requirement late in the terrain relative navigation phase, using maps as large as 90 x 90 km at 18 m per pixel for the hypersonic phase [16]. That mission would also land in early Martian morning, outside the sun elevation envelope Mars 2020 flew in, and landmark matching against an afternoon-lit reference map degrades sharply under a morning descent image: fine landmark inliers fall from the roughly 150 seen in an afternoon control to as few as 20 near 6:30 local solar time, below the threshold needed for a position update [17]. Predicting the morning appearance of the reference map from stacks of afternoon orbital images recovers most of the loss, raising dense correlation on the hardest tested image from 34 percent to as much as 82 percent, still under active development rather than flight-qualified [17].

For OSIRIS-REx the driving number was the mismatch between capability and terrain. The Flight Dynamics System requirement was delivery to a site of 25 m radius, and no hazard-free site on Bennu proved larger than 8 m in radius [4]. NFT replaced lidar as the prime guidance update because lidar gives accurate range but not cross-track position, and because the lidar automatic gain controller carried a concern. Improved modeling reduced the pre-launch 3-sigma TAG position dispersion of 17 to 20 m to between 5.66 and 8.12 m across the four candidate sites, with horizontal velocity dispersion from 12 to 15 mm/s down to 4.56 to 6.64 mm/s against a 20 mm/s requirement [4]:

Site	TAG position dispersion (3 sigma)	Horizontal velocity (3 sigma)	Vertical velocity (3 sigma)
Pre-launch model	17 to 20 m	12 to 15 mm/s	9.4 to 15 mm/s
Nightingale	8.12 m	6.64 mm/s	6.95 mm/s
Kingfisher	5.89 m	5.03 mm/s	7.54 mm/s
Osprey	5.66 m	4.56 mm/s	6.39 mm/s
Sandpiper	7.29 m	6.47 mm/s	5.57 mm/s

Source: [4], Table 6.

NFT state uncertainty at Checkpoint improved from a pre-launch 3.0 m and 3.0 mm/s per axis, 3 sigma, to 2.1 m and 2.9 mm/s in flight, and the uncertainty in the final onboard TAG position estimate was taken as 1.27 m at 3 sigma for site selection [4].

Failure modes

Illumination mismatch between map and descent image is the standing risk in both systems. The LVS operational envelope admits sun elevations from 25 to 55 degrees and azimuths from 240 to 310 degrees clockwise from north, and these variations introduce appearance differences that landmark matching has to absorb [1]. NFT renders each feature under the predicted sun angle precisely to remove that term, which transfers the problem to the accuracy of the shape model [3].

Shape model quality bounded NFT feature availability. Requirements originally written for global and TAG-site accuracy proved insufficient for building features, so a separate set of correlation pixel error and correlation score thresholds had to be defined per feature [3]. Laser altimeter derived digital terrain models met the correlation pixel error requirement for larger rocks and craters, but for smaller features near the sample site the 3 cm per-measurement error masked the elevation signal, and a large majority of features would not have been adequate under the original requirements. Stereophotoclinometry models carry albedo, which helps where shadows are absent, but the least-squares solution can smooth out feature shape and so remove the shadows that make a feature correlate.

Low terrain contrast is the LVS analogue: bland regions with image entropy as low as 3.0 are inside the required envelope and must still produce matches [1]. The MER precedent for a descent vision system failing gracefully was DIMES, which was required to know when its own measurement was unreliable rather than only to produce one [6].

LVS itself is verified against that risk by a combination of venues rather than by analysis alone: simulation, hardware-in-the-loop system testing and field testing, with the captive carry helicopter field test treated as the most trusted result and used to certify the simulation venue [8].

Neither system has a second chance. The LVS answer is consumed just before backshell separation to compute a landing target that avoids both hazards and the backshell [1]. OSIRIS-REx handles the equivalent case by declaring failure: a flight software patch compares the NFT-predicted TAG position and its uncertainty against an onboard hazard map, computes the probability of unsafe contact and triggers the backaway burn early if that probability exceeds a threshold, which changes the design metric from delivery ellipse size to probability of success [4].

What is not established

Mars 2020 gives one flight in benign illumination, with an unusually small initial position error, so it exercises a small part of the declared operational envelope; the field test that stands in for the rest never covered vertical velocity directly; and it found LVS failing its position requirement under illumination differences and terrain relief outside the declared envelope but plausible elsewhere [1][9]. The 5 m and 3 m flight accuracy figures are system level results, anchored to a reconstructed trajectory that is itself tied to the landing site, not independent measurements of the vision algorithm alone [7][9]. The lidar-based approach has flown fewer times and less successfully: on Morpheus, hazard detection met its requirements on every flight but the paired hazard-relative navigation measurement succeeded on only a handful of attempts out of many, because the tracked feature drifted once its own measurements closed the loop into the vehicle’s navigation filter [10]. The radar-based reprocessing result and the Enhanced Lander Vision System design for early-morning Mars landing are both pre-flight: one a post-hoc replay of Mars 2020 telemetry through an algorithm never run onboard, the other a preliminary design closed entirely in simulation against rendered and predicted imagery [12][16][17]. No source held here reports processor utilization, memory footprint or power for any of these systems in flight, so the computational margin actually available during descent is not established from what is cited.