Predictive and adaptive maps for long-term visual navigation in changing environments

In plain words

A robot that repeats a route it was taught finds its place by matching what its camera sees now against a stored set of visual features, one set per stretch of the route. Over weeks and months the light, weather and seasons change, so features stored long ago stop matching, and the robot drifts or gets lost.

The paper asks how the stored feature set should be kept up to date during repeated runs: which old features to throw away, which features to keep because they still help, and which new features from the current camera view to add. It compares several simple update rules. Copying the newest view into the map every run slowly drifts away from the route. Never updating the map fails when the light changes a lot. The best rules keep a score for each feature based on how well it helped, and, in one variant, also model when each feature tends to be visible, such as at a certain time of day. Those rules guided the robot through three months of day, dusk and night runs.

TL;DR

Teach-and-repeat robots need their visual map updated as the environment changes, but naive updates drift. This paper runs eight update rules on one robot dataset gathered over three months, with 178 traversals. The two adaptive rules that use per-feature scores, one of them time-aware (FreMEn), gave the best registration errors. The paper's headline numbers are only plotted, not stated in the text. The repository has the score-based rule but not FreMEn.

Problem

Long-term visual teach-and-repeat needs three things at once: add features that show up after a change, keep only the useful features, and remove obsolete ones so matching stays fast and does not confuse places §I. Updating the map with every new view accumulates sensor and localisation noise, while a map that is never updated becomes irrelevant under environmental change §I.

The map is a sequence of local maps, one per stretch of the path, each holding a camera image and its features §III. In a repeat, each local-map feature is matched to the current view, and a horizontal shift δ is obtained by histogram voting over the horizontal differences of the matched pairs §III. Each matched pair is treated as correct when its difference belongs to the most frequent difference; the other matched pairs are treated as incorrect; features with no match are treated as not matched §IV. The paper's question is how to use this history of feature states to decide what to keep, and how to choose new features to add §I §IV.

The teach-and-repeat core keeps the robot on the path by steering to keep δ small, which relies on the matched features being usable §III. The experiments are outdoor, in a forest park, with a tracked robot, and cover day, dusk, night and light rain §V.

Method

Common setting

The robot is taught a closed path once. During repeats, the system retrieves the local map for its odometry distance, matches features, computes δ by histogram voting, and steers to keep δ small §III. The paper says the repeat phase otherwise uses the taught map unchanged §III.

# Horizontal shift by histogram voting  [§III] [§IV]
# Input:  matched pairs (x_map, x_view) in pixels
# Output: delta, the most frequent horizontal difference (pixels)

def horizontal_shift(pairs):
    # 1. Horizontal difference of every matched pair  [§III]
    differences = [x_map - x_view for x_map, x_view in pairs]
    # 2. Most frequent difference, i.e. the histogram mode  [§III]
    #    Bin width and voting details are not stated in the paper.
    delta = most_frequent(differences)
    # 3. Pairs whose difference fits delta count as correct  [§IV]
    return delta

Map-update strategies (all in §IV-A)

Each strategy decides which features leave the map and how many enter. The state of each feature comes from the histogram test above.

• Static. No update after teaching. This is the baseline and was expected to fail under large appearance change §IV-A.
• Latest. Replace the whole local map with features from the current image. The paper expects a copy-of-a-copy drift, because heading error is never estimated exactly §IV-A.
• Aggressive. Replace every feature that is not matched or matched incorrectly with features from the current image §IV-A.
• Strict. Replace only the features matched incorrectly, with the same number of new features §IV-A.
• Summary. Remove the features matched incorrectly and add 10 % of the features from the current image, so the map grows over time §IV-A.
• Multiple maps. When too few features are matched correctly, store the current features as an extra local map for the same location. At run time, use the map with the most matches §IV-A. The threshold is not stated.
• Score-based (adaptive). Each feature has a score. The score goes up by s_c when the feature is matched correctly, down by s_i when matched incorrectly, and down by s_n when not matched. After each use of a local map, the n features with the worst score are removed and n features from the current view are added §IV-A. The paper's experiments set s_c = s_i = 1 and s_n = 0 §V.
• FreMEn (time-aware adaptive). Feature visibility is modelled over time with spectral analysis, which fits a few harmonic terms. Each match outcome is added to a per-feature model at the time it happened §IV-A fig. 2. At run time the model predicts each feature's score for the current time, and the m highest-scoring features are used §IV-A. Removal uses the mean score over time: the n features with the lowest mean are replaced §IV-A.

# Score-based map update  [§IV-A]
# Input:  local_map (features with scores), matches (state per feature),
#         view (features of the current image), n, s_c, s_i, s_n
# Output: updated local_map

def update_map(local_map, matches, view, n):
    # 1. Update each map feature's score from this use of the map  [§IV-A]
    for feature in local_map:
        state = matches.state_of(feature)
        if state == CORRECT:
            feature.score += s_c
        elif state == INCORRECT:
            feature.score -= s_i
        else:
            feature.score -= s_n
    # 2. Remove the n features with the worst scores  [§IV-A]
    local_map.sort_by_score(best_first=True)
    local_map.drop_last(n)
    # 3. Add n new features from the view  [§IV-B]
    candidates = rank_by_distance_to_map(view, local_map)
    for feature in candidates[:n]:
        # shift position by delta before adding  [§IV-B]
        feature.x += delta
        local_map.add(feature)
    return local_map

Choosing features to add (§IV-B)

Each view feature is scored by its descriptor distance to the nearest feature in the local map. A large distance means the feature is unique, so it is less likely to be mismatched and is a good candidate §IV-B. The paper reports that choosing by this distance was statistically better than random choice across all tested strategies §IV-B §V. Added features are shifted by the current δ before insertion §IV-B.

Choosing features to keep (§IV-A)

Keep the features with the best scores (or, for FreMEn, the best predicted scores at the current time). Remove the worst n. The paper studies the trade-off in n: small n adapts slowly and resists bad registrations, while large n adapts quickly but lets bad features in faster §IV-A.

Hyperparameters

Results

Author-reported. Setup: a tracked robot in a forest park, one taught path, replayed images from a three-month dataset, error measured against manual shifts §V. The paper gives no numeric error values in the text; the comparison is in fig. 4.

Significance: the authors use a paired Student t-test over error sequences. The p-values are not stated in the text §V.

Paper vs code

Repository: gestom/stroll_bearnav at code_commit, default branch master. The owner account belongs to Tomas Krajnik, an author (GitHub profile). The README lists the authors as Majer, Halodová, Vintr and Krajník README.md. The paper's system link (bearnav.eu) redirects to this repository's wiki.

• Feature detector. Paper: SURF detector §III. Code: the default is AGAST, with SURF and upSURF as options featureExtraction.cfg featureExtraction.cfg.
• Update rules present. Paper: eight strategies plus FreMEn §IV-A. Code: only the score-based rule is in master. A keyword search over src/ and cfg/ for FreMEn, summary, strict and aggressive found nothing. The update code is in src/navigator.cpp navigator.cpp. The branch ral_2019_adamap_predictive was checked only at file-list level and has no file named for FreMEn or the other rules. Its contents were not read.
• Score values. Paper: s_c = s_i = 1 and s_n = 0 §V. Code: +1 for correct, −1 for incorrect, 0 for not matched navigator.cpp. The same magnitudes.
• Number exchanged. Paper: 5 % of features per run §V. Code: n equals half the number of correct matches in the current frame, rounded down navigator.cpp. This is not a fixed fraction of the map.
• Trigger. Paper: the score is updated each time a local map is used for navigation §IV-A. Code: the update runs on each distance event navigator.cpp navigator.cpp. Events fire every 0.2 m of travel by default odometryMonitor.cpp distance.cfg. The paper does not state local-map spacing.
• Shift for new features. Paper: δ from histogram voting §IV-B. Code: the mean of the signed differences of correct matches, using the bins within 30 px of the mode navigator.cpp navigator.cpp. Zero if fewer than the minimum number of good features navigator.cpp.
• Ranking of view features. Paper: distance to the nearest map feature §IV-B. Code: the minimum descriptor distance over the 5 nearest neighbours. View features that never appear in any neighbour list keep the sentinel value 5000 and sort first navigator.cpp navigator.cpp navigator.cpp navigator.cpp.
• Map size. Paper: no statement. Code: removes n features and adds min(n, number of view features) navigator.cpp. The map shrinks if the view has fewer features than n.

The values that agree are the 500 features per local map §V, matching the code's target keypoints default featureExtraction.cfg, and the score magnitudes (s_c = s_i = 1, s_n = 0).

Pitfalls

• Numbers are not in the text. The ranking of the eight strategies is stated in words; the error values are only in fig. 4. An implementer cannot reproduce the comparison without the plotted data.
• FreMEn is underspecified. The paper gives no harmonic count, window length, time units, prediction horizon, or value of m. The code does not contain FreMEn navigator.cpp.
• Sign convention. The text says s_i and s_n are penalties (the score is decreased by them), but §V writes s_c = s_i = 1 without a sign. The code applies +1, −1 and 0 navigator.cpp.
• Initial score is not stated. Code uses 0 for new features navigator.cpp. Using a different start value changes which features are removed first, because removal sorts by score.
• Ties. Sorting by score and by ranking is not stable in the code, so features with equal scores are removed or added in no fixed order navigator.cpp navigator.cpp.
• Map size can shrink. Removal is fixed at n while the number of additions depends on the view. Check the map size after each update.
• Update frequency. Updates happen per 0.2 m of travel by default in the code, not per local-map use as the text says. Results depend on how far apart local maps are, which is not stated.
• Feature detector. SURF in the paper, AGAST in the default config. A reproduction using the default config is not the paper's system.
• Latest-view drift is slow. The paper says drift shows up only after many traversals and may not show on straight paths §IV-A §V. Short tests will not show it.
• Source file not compiled. The repository's paper sources include src/vision-loop.tex, which the main file does not include. It describes a separate vision-in-the-loop experiment with its own numbers. Those numbers are not in the compiled paper and are not used in this card.
• Session count. The text says "almost 200 sessions" and also 178 traversals producing 5696 images §V. The card uses 178 and 5696, which agree with 32 local maps.
• Licence. The repository has no LICENSE file and package.xml says TODO package.xml. The paper calls the system open source §I. Code is cited by path and line only, and no snippets are quoted.

Lineage

• Builds on: the teach-and-repeat system of the same group §III and the horizontal-shift navigation proof of §II; score-based updating after dayoub2008, biber and summary_maps §IV-A; FreMEn (krajnik2017fremen) for time-aware visibility §IV-A.
• Compared against: static map (the earlier system, cited as bearnav and jfr10), latest-view map §IV-A, aggressive, strict, summary and multiple-map rules §IV-A.
• Related work discussed: experience-based localisation (churchill), selective experience recommendation (mactavish2018selective), and summary maps §II.
• Superseded by: not known from wiki content.