Frontier exploration

Overview

A robot that maps unknown space has to pick where to go next. A frontier is an explored free cell that touches unexplored space. Any route into unseen space crosses a frontier, so the choice of goal can be limited to frontiers 2201.10029 §3.3. The modular active SLAM pipeline follows the same pattern: list candidate goals, score each one with a utility, and go to the best 2207.00254 §2.2.

The invariant all variants share is the selection rule: the goal is the candidate with the highest score, and a planner then drives the robot there 2201.10029 §3.3 2207.00254 eq. 24. The variants differ in where the score comes from. One learns it from maps that already exist. The other computes it from the robot's own uncertainty.

Variants

Learned frontier potentials for object goals

A small image-to-image network reads a partial top-down semantic map. For each frontier it predicts two values: how much unexplored room lies beyond it, and how close it is to a named object category 2201.10029 §3.3. The two values are averaged with equal weight, and the frontier with the highest value becomes the goal. A Fast Marching planner then moves the agent there, with no learned policy in the loop 2201.10029 §3.2, §3.5. Card: PONI.

The network is trained with a supervised mean-squared-error loss. Its training examples are partial maps cut from complete semantic maps of scenes, and the targets come from the complete maps 2201.10029 §3.6. The paper reports 400,000 training tuples per dataset 2201.10029 §4.2. Author-reported results on the ObjectGoal task: Gibson validation success 73.6 and SPL 41.0; MP3D validation success 31.8 and SPL 12.1 [arxiv:2201.10029 tab. 1]. The paper reports training cost up to 1,600 times lower than the MP3D method THDA, measured in GPU-hours 2201.10029 §5.

Information utilities on frontiers in active SLAM

Active SLAM is cast as a POMDP over the joint state of robot and map, and the robot's action should reduce uncertainty 2207.00254 §2.1. Many of the surveyed systems take frontiers as candidate goals. In the survey's condensed table, 13 of 24 rows list frontiers among their goal candidates [arxiv:2207.00254 tab. 1]. Each candidate is scored by an expected information gain, such as mutual information 2207.00254 eq. 14, or by an optimal-design criterion such as D-optimality, A-optimality or E-optimality 2207.00254 eq. 19 2207.00254 eq. 20 2207.00254 eq. 21. The survey is a review and runs no experiments of its own 2207.00254 §1. Card: A Survey on Active SLAM.

When to use which

Pitfalls:

• PONI assumes noise-free depth and odometry in simulation 2201.10029 §4. It does not model localisation uncertainty, so the active SLAM concern does not apply to it.
• The object cutoff distance is not given in the paper. It was chosen on validation data 2201.10029 §3.3.
• Area normalisation differs by dataset. The paper divides by total free space of the complete map, but uses a fixed constant on MP3D 2201.10029 §3.3.
• Table 1 of PONI has no variance, and its Gibson margin over SemExp is 1.9 points of success 2201.10029 tab. 1.
• On the MP3D test-standard challenge, PONI is best on SPL, SoftSPL and DTS but not on success 2201.10029 tab. 2.
• The survey gives no algorithm to implement. Its joint-entropy sum is an approximation, and the weights it says are needed are not given 2207.00254 §4.2.
• The survey states that the monotonic growth of uncertainty depends on the representation, not only on the criterion 2207.00254 §4.3.

Implementation sketch

Common core of both variants. Candidates are frontiers only. The score function is the variant-specific part. The sketch is not a reference implementation.

# One frontier-exploration step  [arxiv:2201.10029 §3.3]
# Input:  explored, free: (M, M) bool masks of the partial map
#         score_fn(cell) -> float, learned or information-based
# Output: goal cell for the local planner

def next_frontier_goal(explored, free, score_fn):
    # A frontier is an explored free cell next to unexplored space [§3.3]
    frontier = free_cells_adjacent_to_unexplored(explored, free)
    if not frontier:
        return None  # nothing left to explore
    # Score each candidate: PONI averages area and object potentials
    # [arxiv:2201.10029 eq. 2]; the survey uses an information utility
    # on the belief [arxiv:2207.00254 §4]
    scores = {cell: score_fn(cell) for cell in frontier}
    # Pick the best candidate; ties are not specified [arxiv:2201.10029 §3.3]
    return max(scores, key=scores.get)

Contradictions

None known. The two sources score frontiers with different objectives: one predicts a value for an object category, the other computes an information measure on the belief 2201.10029 §3.3 2207.00254 §4. Their numbers do not compare directly, because the survey reports no experiments.

Papers

• PONI: Potential Functions for ObjectGoal Navigation with Interaction-free Learning: learned area and object potentials at frontiers, with a Fast Marching planner.
• A Survey on Active Simultaneous Localization and Mapping: formulation and modular pipeline for choosing frontier goals by information utility.