Visual Navigation

Visual navigation is the task of moving a robot, or an agent in a simulator, to a goal using what its cameras and depth sensors see. The goal may be a point given in coordinates (“go 5 m ahead and 3 m to the left”), an object category (“find a chair”), a picture of the place to reach, or a sentence of directions. The agent starts in a building it has usually never seen, observes it only through its own sensors, chooses one movement at a time, and must decide for itself when it has arrived. The problem sits between SLAM, which builds a map and tracks the sensor in it but rarely decides where to go, and motion planning, which finds collision-free paths in a known map (Anderson et al., 2018a). Two families of methods compete, with hybrids between them: map-based pipelines that build a map, localize in it and plan a path, and policies learned end to end that map images straight to actions. A 2018 working group noted a surge of navigation research in the preceding two years, much of it in simulation (Anderson et al., 2018a); photorealistic simulators and shared benchmarks have shaped the field since, and raise a question of their own: whether results measured in simulation hold on real robots.

Problem Definition

An episode starts with the agent at a pose in an environment and a goal specification $g$. At each time step $t$ the agent receives an observation $o_t$ (images, depth, sometimes a position sensor) and chooses an action $a_t$ from a small set, typically move forward, turn left, turn right and a special stop action. The episode ends when the agent calls stop or exhausts a budget of actions. The agent never sees the full map: it must infer free space, obstacles and the goal’s whereabouts from its history of observations, which makes navigation a problem of acting under partial observability.

That working group, with members from several laboratories, set out shared definitions (Anderson et al., 2018a). Its recommendations shape most benchmarks since:

• An explicit stop. The agent must declare that it has finished, and is judged where it stops, not at the closest point it passed.
• Geodesic distance. Proximity to the goal is measured along the shortest path through the environment, not in a straight line, since a goal behind a wall is not close.
• Stated sensors. Papers must say what the agent senses, in particular whether it receives perfect odometry or GPS-like localization.
• Stated prior exposure. The agent may face a new building with no prior exploration, receive a recorded exploration run, or explore on its own within a stated budget before the episode. The amount of exposure must be reported, because training for days in the test building and walking into it for the first time are different problems.

The working group also recommended continuous rather than grid-world motion and SI units in simulators, so that 1 unit equals 1 m.

Input and Output

The input is a stream of egocentric observations. Habitat’s reference agent, for example, carries a forward-facing color camera at a height of 1.5 m with a 90° field of view and 256 × 256 pixels, and an idealized depth sensor with the same pose and field of view (Savva et al., 2019). Depth comes from RGB-D or stereo cameras, or is predicted from color by depth estimation. Many point-goal setups add an idealized GPS+Compass sensor that gives the agent’s position and heading relative to the start, which removes localization from the problem; Savva et al. (2019) treat it explicitly as part of the sensor suite rather than of the task, so that agents can be compared by the sensors they use. Real robots get position from wheel odometry, visual odometry or SLAM instead.

The output is a sequence of discrete actions. In Habitat’s 2019 setup the forward action moves 0.25 m and each turn rotates by 10°; motion is continuous, and an agent that bumps into a wall can slide along it, so even without actuation noise a forward action does not always move the agent 0.25 m forward (Savva et al., 2019).

Variants

The working group distinguished three kinds of goal, point, object and area, and noted that a goal can also be specified by an image or in language (Anderson et al., 2018a):

• PointGoal navigation (PointNav). Reach a location given as coordinates relative to the start. With an empty room it is trivial; in cluttered, unseen buildings it requires mapping, planning and obstacle avoidance.
• ObjectGoal navigation (ObjectNav). Reach an instance of an object category such as “refrigerator”. The agent must recognize the object and know where such objects tend to be, which adds object detection or semantic segmentation and prior knowledge of room layouts. A second working group fixed its details in 2020: success requires stopping within a distance $r$ of the object’s surface, with $r = 1$ m as a suggested start, and, depending on the setting, the object in view or viewable by turning in place (Batra et al., 2020).
• AreaGoal navigation. Reach a room of a given type, such as a kitchen.
• ImageGoal navigation. Reach the place where a given picture was taken, or the object it shows. Zhu et al. (2017) trained a policy conditioned on a target image, so that one network could navigate to different targets.
• Vision-and-language navigation (VLN). Follow instructions in natural language, such as “walk past the sofa and stop at the bedroom door”. Anderson et al. (2018b) introduced the Room-to-Room (R2R) dataset of 21,567 instructions for 7,189 paths in Matterport3D buildings, in which the agent moves between precomputed viewpoints of a navigation graph.

Exploration, covering as much of an unseen building as possible within a budget, is a task of its own and, Chaplot et al. (2020a) argue, a core problem of navigation in unknown environments whatever the goal.

Challenges

• Partial observability. The camera sees a cone of the building at a time. Free space behind a door, the far side of furniture and the room that contains the goal must be inferred or explored.
• Long horizons and sparse feedback. An episode can take hundreds of actions, and the only unambiguous signal is whether the agent ended at the goal, which makes learning by trial and error expensive.
• Generalization to new buildings. Benchmarks split buildings, not episodes, into training and test sets, so a policy that memorizes its training homes fails. Chaplot et al. (2020b) observed that their learned ObjectNav baselines performed much better on training scenes than on test scenes and concluded that they memorized object locations and appearance.
• Localization. Without the idealized GPS+Compass sensor, the agent must estimate its own motion, and errors accumulate. Wijmans et al. (2020) report 0.15 SPL for an RGB agent without GPS+Compass after 2.5 billion steps of training; with GPS+Compass, their RGB agent reached 0.920 on the test-std split.
• Semantics. ObjectNav agents fail when they do not recognize the target. Replacing the segmentation model of Chaplot et al.’s (2020b) agent by ground-truth segmentation raised its success rate on their Gibson test scenes from 54.4% to 73.1%.
• The real world. Simulated physics, sensor noise and rendering differ from reality, and agents can learn behaviors that only work in the simulator (see below).

Approaches

Map-based pipelines

The classical solution splits navigation into localization, mapping, planning and control, each solved by an established algorithm (Mishkin et al., 2019).

1. Localization. SLAM or visual odometry estimates the camera pose. Mishkin et al. (2019) used ORB-SLAM2 with color or color and depth; when tracking was lost, resetting the map worked better than relocalizing in it. The SLAM article covers how such systems work.
2. Mapping. Depth pixels are back-projected into 3D with the camera’s intrinsics and pose, points at floor level and above the robot’s height are discarded, and the rest are projected onto a top-down occupancy grid: cells of fixed size (10 × 10 cm in Mishkin et al.’s pipeline) marked occupied once enough points fall into them. A common further step, used in the example below, grows obstacles by the robot’s radius, so that the robot can be planned for as a point.
3. Planning. The grid becomes a graph, with free cells as nodes and edges to the eight neighbours, diagonals weighted by $\sqrt{2}$, and a shortest path is found with Dijkstra’s algorithm (Dijkstra, 1959) or A* (Hart, Nilsson & Raphael, 1968), which expands nodes in order of path cost so far plus a lower bound on the remaining cost. Active Neural SLAM and its successors plan with the Fast Marching Method instead, which computes distances over a grid from an advancing front (Chaplot et al., 2020a).
4. Control. A controller follows the path; with discrete actions, a simple rule turns toward a waypoint a fixed distance ahead and moves forward once facing it.

Unknown cells are treated as free when planning. The plan is optimistic: it runs straight through unexplored space, and when the camera reveals an obstacle on it, the agent replans. Re-running A* after every change is wasteful in large maps; Mishkin et al. used D* Lite, which is identical to A* on the first call and afterwards updates only the costs of nodes affected by newly found obstacles. For object goals, a classical baseline in Chaplot et al. (2020b) pairs such a map with frontier-based exploration, which heads for the boundary between explored free space and unknown space (Chaplot et al., 2020a), and an object detector that redirects the agent once the target is seen.

Map-based pipelines need no training and fail in recognizable ways, such as lost tracking or, with a single camera, unknown scale, which Mishkin et al. fixed with a hard-coded initialization using the agent’s known height. Their weakness is that each module is hand-engineered, and none carries prior knowledge of where things are in buildings.

End-to-end learned policies

A learned policy maps the history of observations and the goal directly to actions. Habitat’s baseline, for example, encodes images with a small convolutional network, feeds the embedding and the goal vector to a recurrent policy, and is trained by reinforcement learning (PPO) with a reward for reducing the geodesic distance to the goal, a bonus for success and a small penalty per step (Savva et al., 2019). Zhu et al. (2017) trained a target-conditioned policy in AI2-THOR and report that it generalized across targets and scenes and, with a little fine-tuning, to a real robot. Savva et al. (2019) trained PPO agents in Habitat on PointNav for 75 million steps, 15 times more experience than earlier comparisons, and found that the conclusion of those comparisons reversed: the classical pipeline of Mishkin et al. dominated at 5 million steps, while a depth-only learned agent matched it at about 10 million (Gibson) and 30 million (Matterport3D) steps and kept improving. On their test sets the depth agent reached an SPL of 0.79 on Gibson and 0.54 on Matterport3D, against 0.51 and 0.39 for the SLAM-based pipeline (Savva et al., 2019, Table 2). The authors stress that “learning” and “SLAM” are broad families, and claim no intrinsic superiority for either.

Two of their observations recur in later work. Depth agents beat RGB and RGB-D agents, which the authors attribute to PointNav needing only free space, which depth gives directly, and to color images being easier to overfit. And RGB agents did not significantly outperform blind agents with only GPS+Compass, which learned to hug walls.

Wijmans et al. (2020) scaled this further with DD-PPO, a decentralized, synchronous distributed version of PPO that reached a 107× speed-up on 128 GPUs. An agent trained for 2.5 billion steps, with RGB-D (in practice depth) and GPS+Compass, reached an SPL of 0.948 and a success rate of 0.980 on the Habitat Challenge 2019 test-std split (0.969 and 0.997 on validation), which the authors describe as essentially solving the task under those sensors. The result has conditions: idealized GPS+Compass and the 2019 challenge’s simulator settings, which Kadian et al. (2020) list as sliding collisions and no actuation noise. The same paper reports that 90% of peak performance came within the first 100 million steps.

Modular learned systems

A third family keeps the structure of the map-based pipeline but learns some of its modules. Active Neural SLAM (Chaplot et al., 2020a) combines a learned mapper and pose estimator, which predict a top-down map of obstacles and explored space and the agent’s pose from RGB images and noisy odometry; a learned global policy, which picks a long-term goal on the map; an analytic planner (the Fast Marching Method) that turns it into a short-term goal; and a learned local policy that outputs actions. It was trained for exploration, with motion and sensor noise models measured on a real robot, and transferred to PointNav without retraining by fixing the long-term goal to the target. On their Gibson validation split it reached a success rate of 0.950 and an SPL of 0.846, against 0.827 and 0.730 for the best baseline trained on PointNav with the same 10 million frames, and it won the CVPR 2019 Habitat PointNav challenge with an SPL of 0.805 (RGB track) and 0.948 (RGB-D track) on the Test Challenge set, a different split from the test-std split of DD-PPO’s 0.948.

Goal-Oriented Semantic Exploration (SemExp; Chaplot et al., 2020b) extends the map with one channel per object category, filled by projecting the output of a Mask R-CNN through the depth image, and trains a goal policy to choose where the target category is likely to be. A deterministic planner (again the Fast Marching Method) moves the agent toward that goal and replans at every step. In their ObjectNav comparison, with a success radius of 1 m and 500 steps, the end-to-end RL baselines reached success rates of 8.2% and 15.9% on Gibson, a classical map with frontier-based exploration and a detector reached 40.3%, and SemExp 54.4% (Table 1, their Gibson test scenes; SPL 0.199). SemExp won the CVPR 2020 Habitat ObjectNav challenge with a success rate of 0.253 and SPL of 0.102 on the Test Challenge set.

Read together, these results suggest (our reading of the cited tables) that the balance depends on the task: on PointNav with ideal localization, large-scale end-to-end training wins; on ObjectNav, where the agent must remember where it has looked and reason about where objects are, explicit maps with learned components lead.

Instruction following

In VLN the instruction describes the route, although R2R scores only where the agent stops. The first R2R baseline, a sequence-to-sequence model, reached a 38.6% success rate in buildings seen during training but 21.8% in unseen validation buildings and 20.4% on the unseen test set, where humans reached 86.4% (Anderson et al., 2018b, Table 1). Anderson et al. (2018b) framed the task as visually grounded sequence-to-sequence translation, close to visual question answering, so that methods for vision and language apply to it.

Example: point-goal navigation on a rendered floor plan

The code below runs a PointNav benchmark in miniature. A 6 m × 8 m apartment is rendered as a binary floor-plan image at 10 cm per pixel, with walls, doorways and four pieces of furniture. Obstacles are grown by one cell, so that a point agent stands in for a robot 0.2 m wide, Habitat’s agent diameter. The agent has eight headings 45° apart and four actions: turn left, turn right, move forward one cell (0.1 m, or 0.14 m diagonally) and stop. At every step it receives a depth scan, one row of 31 ranges across a 90° field of view ray-cast from its pose up to 3 m, and, like Habitat’s PointNav agents, knows its own position and heading exactly. Four agents are compared:

• oracle follows the true shortest path, computed by Dijkstra’s algorithm on the full floor plan;
• map+A* back-projects each depth reading into the map cell it came from, grows the observed obstacles, plans with A* treating unknown cells as free, and replans when a newly seen obstacle, or a cell it bumped into, lies on its path;
• map+A*, 1 m is the same agent with a 1 m depth range;
• greedy keeps no map: it is told which of its three forward moves (45° left, straight, 45° right) are free and takes the one ending nearest the goal, if nearer than where it stands; otherwise it turns left.

An agent calls stop on reaching the goal cell. As in Habitat, an episode succeeds if the agent stops within 0.2 m geodesic distance of the goal and fails after 500 actions; a move into an obstacle leaves the agent where it was, with no sliding. Start and goal pairs at least 3 m apart along the shortest path are drawn with a seeded generator, ten for each of seeds 0 to 4. The script prints success, SPL and SoftSPL (defined under Evaluation Metrics), actions (including turns and stop) and collisions, averaged over the 50 episodes, and the range of SPL over the five seeds.

import heapq
import numpy as np
from scipy.ndimage import binary_dilation, label

CELL = 0.1                      # metres per grid cell
H, W = 60, 80                   # a 6 m x 8 m floor plan

# Render the floor plan as a binary image: 1 = wall or furniture.
plan = np.zeros((H, W), bool)
plan[[0, -1], :] = plan[:, [0, -1]] = True
plan[:, 38:40] = True; plan[12:21, 38:40] = False          # wall with door
plan[30:32, :38] = True; plan[30:32, 8:17] = False         # left rooms
plan[26:28, 40:] = True; plan[26:28, 62:71] = False        # right rooms
plan[44:60, 54:56] = True; plan[48:56, 54:56] = False
plan[8:16, 10:24] = True                                    # table
plan[40:52, 20:26] = True                                   # sofa
plan[36:40, 46:60] = True                                   # shelf
plan[6:14, 52:66] = True                                    # bed

# Configuration space: grow obstacles by the agent radius (0.1 m).
cspace = binary_dilation(plan, np.ones((3, 3), bool))
MOVES = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]

def neighbours(c, blocked):
    for k, (dr, dc) in enumerate(MOVES):
        r, q = c[0] + dr, c[1] + dc
        if blocked[r, q] or (dr and dc and (blocked[c[0] + dr, c[1]]
                                            or blocked[c[0], c[1] + dc])):
            continue                         # no corner cutting
        yield (r, q), k, CELL * (1.4142135623730951 if dr and dc else 1.0)

def dijkstra(goal, blocked):             # geodesic distance to the goal
    dist = np.full((H, W), np.inf); dist[goal] = 0.0
    heap = [(0.0, goal)]
    while heap:
        d, c = heapq.heappop(heap)
        if d > dist[c]:
            continue
        for n, _, w in neighbours(c, blocked):
            if d + w < dist[n]:
                dist[n] = d + w; heapq.heappush(heap, (d + w, n))
    return dist

def astar(start, goal, blocked):         # octile heuristic is admissible
    def h(c):
        a, b = abs(c[0] - goal[0]), abs(c[1] - goal[1])
        return CELL * (max(a, b) + 0.41421356 * min(a, b))
    g, parent, heap = {start: 0.0}, {start: None}, [(h(start), start)]
    while heap:
        _, c = heapq.heappop(heap)
        if c == goal:
            path = []
            while c is not None:
                path.append(c); c = parent[c]
            return path[::-1]
        for n, _, w in neighbours(c, blocked):
            if g[c] + w < g.get(n, np.inf):
                g[n] = g[c] + w; parent[n] = c
                heapq.heappush(heap, (g[n] + h(n), n))
    return None

def ray_angles(heading, n_rays=31, fov=np.pi / 2):  # 90-degree field of view
    return np.arctan2(*MOVES[heading]) + np.linspace(-fov / 2, fov / 2, n_rays)

def depth_scan(pos, heading, max_range):
    """Ray-cast a one-row range image from the floor plan (the sensor)."""
    a, t = ray_angles(heading), np.arange(0.0, max_range, 0.02)
    r = np.clip(pos[0] + 0.5 + np.outer(np.sin(a), t) / CELL, 0, H - 1).astype(int)
    q = np.clip(pos[1] + 0.5 + np.outer(np.cos(a), t) / CELL, 0, W - 1).astype(int)
    hit = plan[r, q]
    return np.where(hit.any(axis=1), t[hit.argmax(axis=1)], max_range)

def project(ranges, pos, heading, max_range):
    """Back-project each return into the map cell it came from."""
    a, ok = ray_angles(heading), ranges < max_range
    r = (pos[0] + 0.5 + np.sin(a[ok]) * ranges[ok] / CELL).astype(int)
    q = (pos[1] + 0.5 + np.cos(a[ok]) * ranges[ok] / CELL).astype(int)
    return r, q

def run_episode(agent, start, goal, true_dist, max_range=3.0, max_actions=500):
    pos, heading, p, collisions = start, 0, 0.0, 0
    known = np.zeros((H, W), bool)                  # observed obstacles
    known[[0, -1], :] = known[:, [0, -1]] = True    # only the map's extent
    bumped = np.zeros((H, W), bool)                 # cells it collided with
    path = None
    for t in range(max_actions):
        ranges = depth_scan(pos, heading, max_range)
        known[project(ranges, pos, heading, max_range)] = True
        if np.hypot(pos[0] - goal[0], pos[1] - goal[1]) < 0.5:
            stopped = True; break                   # the agent calls STOP
        if agent == "oracle":
            nxt = min(neighbours(pos, cspace), key=lambda n: n[2] + true_dist[n[0]])
            want = nxt[1]
        elif agent.startswith("map"):
            blocked = binary_dilation(known, np.ones((3, 3), bool)) | bumped
            if path is None or any(blocked[c] for c in path):
                path = astar(pos, goal, blocked)    # replan on new obstacles
            if path is None:
                stopped = False; break
            i = path.index(pos)
            want = MOVES.index((path[i + 1][0] - pos[0], path[i + 1][1] - pos[1]))
        else:                                       # greedy, no map
            here = np.hypot(goal[0] - pos[0], goal[1] - pos[1])
            free = {k: n for n, k, _ in neighbours(pos, cspace)}
            options = []
            for d in (-1, 0, 1):                    # 45 deg left, ahead, right
                k = (heading + d) % 8
                if k in free:
                    gap = np.hypot(goal[0] - free[k][0], goal[1] - free[k][1])
                    if gap < here:
                        options.append((gap, k))
            want = min(options)[1] if options else (heading - 1) % 8
        if want != heading:                         # turn by 45 degrees
            heading = (heading + (1 if (want - heading) % 8 <= 4 else -1)) % 8
            continue
        nxt = (pos[0] + MOVES[heading][0], pos[1] + MOVES[heading][1])
        if any(n == nxt for n, _, _ in neighbours(pos, cspace)):
            p += CELL * np.hypot(*MOVES[heading]); pos = nxt
        else:
            collisions += 1; bumped[nxt] = True     # blocked: no sliding
    else:
        stopped = False
    d_T = true_dist[pos]
    success = stopped and d_T <= 0.2                # 0.2 m threshold
    return success, p, d_T, t + 1, collisions

def evaluate(seed, n_episodes=10):
    rng = np.random.default_rng(seed)
    comp, _ = label(~cspace)
    free = np.argwhere(comp == np.bincount(comp.ravel())[1:].argmax() + 1)
    episodes = []
    while len(episodes) < n_episodes:
        s, g = map(tuple, free[rng.choice(len(free), 2, replace=False)])
        dist = dijkstra(g, cspace)
        if dist[s] >= 3.0:                          # geodesic at least 3 m
            episodes.append((s, g, dist))
    out = {}
    for agent, max_range in AGENTS:
        rows = []
        for s, g, dist in episodes:
            ok, p, d_T, n_act, col = run_episode(agent, s, g, dist, max_range)
            l = dist[s]
            rows.append((ok, ok * l / max(p, l),
                         (1 - d_T / l) * l / max(p, l), n_act, col))
        out[agent] = np.array(rows, float).mean(axis=0)
    ged = np.mean([d[s] / (CELL * np.hypot(s[0] - g[0], s[1] - g[1]))
                   for s, g, d in episodes])
    return out, ged

AGENTS = [("oracle", 3.0), ("map+A*", 3.0), ("map+A*, 1 m", 1.0), ("greedy", 3.0)]
results = {}
for seed in range(5):
    out, ged = evaluate(seed)
    results[seed] = out
    print(f"seed {seed}: mean geodesic/Euclidean ratio {ged:.2f}")
print(f"\n{'agent':12s} {'success':>8s} {'SPL':>6s} {'SoftSPL':>8s} "
      f"{'actions':>8s} {'collisions':>10s}   SPL min-max over seeds")
for agent, _ in AGENTS:
    m = np.mean([results[s][agent] for s in results], axis=0)
    spl = [results[s][agent][1] for s in results]
    print(f"{agent:12s} {m[0]:8.2f} {m[1]:6.3f} {m[2]:8.3f} {m[3]:8.1f} "
          f"{m[4]:10.1f}   {min(spl):.3f}-{max(spl):.3f}")

Output (NumPy 2.3.5, SciPy 1.16.3; two runs gave identical output):

seed 0: mean geodesic/Euclidean ratio 1.59
seed 1: mean geodesic/Euclidean ratio 3.05
seed 2: mean geodesic/Euclidean ratio 1.56
seed 3: mean geodesic/Euclidean ratio 1.18
seed 4: mean geodesic/Euclidean ratio 1.66

agent         success    SPL  SoftSPL  actions collisions   SPL min-max over seeds
oracle           1.00  1.000    1.000     72.4        0.0   1.000-1.000
map+A*           1.00  0.907    0.907     90.0        0.1   0.868-0.955
map+A*, 1 m      1.00  0.869    0.869     97.0        0.4   0.799-0.927
greedy           0.16  0.160    0.260    426.7        0.0   0.000-0.300

The oracle’s SPL of exactly 1 checks the metric: its path length equals the geodesic distance, because both are measured on the same grid with the same moves. Its 72.4 actions per episode include turns, which SPL does not count, the point Batra et al. (2020) make about turning in place.

The map-based agent reaches the goal in every episode, yet loses about 9% of SPL to detours. The cause is the optimistic plan: it heads through unexplored space, a wall appears in the depth scan, and the agent replans from wherever it now stands. Reasoning from the code rather than from the output: the map blocks only cells seen to be obstacles and cells the agent failed to enter, and each replan is triggered by a newly blocked cell, of which there are finitely many; in a static world an episode therefore ends at the goal, with no path left in the map, or out of actions, and here every episode ended at the goal. Cutting the depth range to 1 m reveals walls later, adds actions, and lowers the mean SPL to 0.869, but the per-seed ranges overlap: which episodes are drawn matters as much here as the sensor’s range. Collisions are possible because the agent may not cut corners and the scan covers only the 90° ahead, so an obstacle beside the agent can block a diagonal move before it has been seen; the agent then marks the cell it tried to enter as blocked, although that cell may itself be free, and plans around it.

The greedy agent shows why memory and planning matter. Its SPL equals its success rate, so every successful path was as short as the geodesic distance: it succeeds only on episodes it can solve by heading straight for the goal. Elsewhere it descends toward the goal until an obstacle stops it, then turns in place, and the mean of 426.7 actions shows that most episodes ran to the 500-action limit. SoftSPL gives it partial credit for the distance it did cover, while success and SPL score those episodes as zero; the per-seed mean ratio of geodesic to straight-line distance, from 1.18 to 3.05, shows how much the sets of episodes differ in how often a wall stands in the way. Habitat’s blind “goal follower” baseline, which turns toward the goal and walks forward without sensing obstacles, scored an SPL of 0.23 on Gibson and 0.12 on Matterport3D test episodes (Savva et al., 2019, Table 2).

Datasets and Benchmarks

Navigation benchmarks combine a simulator, which renders observations and enforces collisions, with a dataset of 3D environments and a set of episodes.

Simulators.

• AI2-THOR (Kolve et al., 2017; first arXiv version December 2017) offers near-photorealistic interactive indoor scenes in the Unity game engine, where agents can also interact with objects, for example opening them or picking them up. Version 1.0 had 120 single-room scenes: kitchens, living rooms, bedrooms and bathrooms (Anderson et al., 2018a).
• Gibson Env (Xia et al., 2018) renders scanned real buildings, 572 buildings with 1,447 floors, and includes “Goggles”, a network that maps real camera images toward the simulator’s rendering so that policies can be deployed without further adaptation.
• Habitat (Savva et al., 2019) separates a fast simulator, Habitat-Sim, from a library for defining tasks and training agents. Rendering Matterport3D scenes, Habitat-Sim reached several thousand frames per second single-threaded and over 10,000 multi-process on one GPU, against the tens to hundreds of frames per second its authors report for earlier simulators; Wijmans et al. (2020) relied on that speed to simulate billions of steps.
• iGibson 1.0 (Shen et al., 2021) adds full interactivity: 15 home-sized scenes with 108 rooms whose rigid and articulated objects can be manipulated, aimed at tasks that combine navigation and manipulation.

Environment datasets.

• Matterport3D (Chang et al., 2017): 10,800 panoramas from 194,400 RGB-D images of 90 building-scale scenes, with reconstructed meshes and semantic annotations. The navigation splits use its 61/11/18 building split for training, validation and test (Anderson et al., 2018a).
• Gibson (Xia et al., 2018): the 572 scanned buildings above. Anderson et al. (2018a) defined tiny, medium and full partitions of 35, 140 and 572 buildings, and DD-PPO’s authors found that training on Gibson scenes with poorer reconstruction quality ratings, in addition to the better ones, raised test SPL by about 0.03 (Wijmans et al., 2020).
• HM3D (Ramakrishnan et al., 2021): 1,000 building-scale reconstructions with 112.5 thousand m² of navigable space by the body text and Table 1 (the abstract in the paper prints it as 112.5 km²), which the authors report as 1.4 to 3.7 times larger than Matterport3D and Gibson.

Challenges. The Habitat challenges, held at CVPR from 2019 (in 2020 at the Embodied AI workshop), fix the sensors, actions, episodes and evaluation server, and report results on held-out test splits: test-standard, the public leaderboard to use in papers, and test-challenge, which decides the winners (Batra et al., 2020). The 2020 ObjectNav challenge used 21 goal categories in Matterport3D scenes. The RoboTHOR 2020 challenge used 12 target categories and trained agents in 75 simulated scenes, then tested them in 10 real scenes whose wall layouts did not occur in training; RoboTHOR’s real scenes have simulated counterparts with identical object layouts (Batra et al., 2020).

Evaluation Metrics

Success. An episode succeeds when the agent calls stop within a threshold distance $\tau$ of the goal. The working group recommended twice the agent’s body width by default, 0.4 m for a 0.2 m agent (Anderson et al., 2018a). Habitat’s PointNav uses 0.2 m of geodesic distance, with an agent 0.2 m in diameter and at most 500 actions (Savva et al., 2019), which is stricter than that default (our comparison). ObjectNav uses a distance to the object’s surface, and R2R calls an episode successful when the agent stops within 3 m of the goal on the navigation graph (Anderson et al., 2018b).

SPL. Success weighted by (normalized inverse) Path Length rewards agents that succeed by short routes (Anderson et al., 2018a). Over $N$ test episodes, with $S_i \in \{0, 1\}$ the success of episode $i$, $\ell_i$ the shortest-path distance from start to goal and $p_i$ the length of the path the agent took,

$$\mathrm{SPL} = \frac{1}{N} \sum_{i=1}^{N} S_i \, \frac{\ell_i}{\max(p_i, \ell_i)}.$$

Each term is 0 for a failure and at most 1 for a success, reaching 1 only for a success along a shortest path; the $\max$ caps it at 1. The working group gives examples: an agent that succeeds in half the episodes by optimal paths scores 0.5, as does one that succeeds always but walks twice as far as needed; one that succeeds in half the episodes with paths twice too long scores 0.25. They called SPL stringent, expected 0.5 to be good performance in complex unseen environments, and suggested calibrating this on each dataset by measuring human SPL. For ObjectNav, $\ell_i$ is the shortest path to the nearest instance of the target category, so an agent that finds a more distant chair succeeds with a low SPL (Batra et al., 2020).

Batra et al. (2020) list known weaknesses of SPL. All failures score 0, whether the agent stopped just outside the threshold or never moved; the binary success term makes the average noisy, which demands many episodes; turning in place costs nothing, so an agent can look around at no penalty; and short episodes leave less room for detours than long ones, so SPL values cannot be compared across datasets with different path lengths.

SoftSPL. Datta et al. (2020) proposed replacing the binary success by the fraction of the initial geodesic distance $d_{\mathrm{init}}$ that the agent covered, with $d_T$ the geodesic distance at termination:

$$\mathrm{SoftSPL}_i = \left(1 - \frac{d_T}{d_{\mathrm{init}}}\right) \frac{\ell_i}{\max(p_i, \ell_i)}.$$

It credits agents that navigate well but stop slightly short, which matters when noisy localization makes the stop decision unreliable; their baseline agent without localization input scored an SPL of 0.096 but a SoftSPL of 0.726 (noise-free actions). Progress can be negative if the agent ends farther away than it started.

Other measures. The working group suggested also reporting the distance to the goal at the end, SPL swept over thresholds, collisions, and actuation time and energy. SemExp’s authors report Distance to Success, the distance to the success boundary at the end, $\max(\lVert x_T - G \rVert_2 - d_s, 0)$ for final position $x_T$, goal $G$ and threshold $d_s$ (Chaplot et al., 2020b). R2R reports trajectory length, navigation error (the shortest-path distance from the stopping point to the goal) and oracle success, scored as if the agent had stopped at the point of its trajectory closest to the goal (Anderson et al., 2018b).

Simulation and the Sim-to-Real Gap

Simulation makes navigation research reproducible and fast, and the working group recommended it, but it also recommended open software to run simulation-trained agents on physical robots (Anderson et al., 2018a). Kadian et al. (2020) measured how well simulation predicts reality. They 3D-scanned a 6.5 m × 10 m lab room in three obstacle configurations, imported the scans into Habitat, and ran nine PointNav agents (depth, predicted depth or RGB, trained under different noise and collision settings) in both the simulated replica and the real room on a LoCoBot mobile robot: 810 runs in simulation and reality combined, about 40.5 hours of them on the robot. Their measure, the Sim2Real Correlation Coefficient (SRCC), is the Pearson correlation between the agents’ simulated and real scores.

With simulator settings like those of the 2019 Habitat challenge, SRCC was 0.603 for SPL and 0.18 for success: nearly every agent succeeded almost always in simulation, while real success rates spread widely, and the ranking by SPL had 9 reversals between simulation and reality. The main cause was sliding. When a simulated agent collided, it slid along the obstacle, and the path length counted for SPL was the straight-line displacement, so agents learned to cut corners through what was in effect non-navigable space, which a real robot that stops on contact cannot do. Disabling sliding and searching over actuation noise raised SRCC to 0.875 for SPL and 0.844 for success, with sliding off and zero actuation noise as the best setting. Reducing reconstruction quality by dropping 5% of mesh triangles lowered SRCC by 23%. The authors argue that simulators should be judged primarily by this predictivity, whether differences between methods in simulation carry over to reality, rather than by visual or physical realism. Habitat’s 2020 challenge disabled sliding for this reason (Batra et al., 2020).

Modular agents whose learned parts work on top-down maps have transferred to robots in small tests. SemExp ran on a LoCoBot in a real environment and succeeded in 13 of 20 ObjectNav trials; its authors attribute this to a detector trained on real images and to modules that operate on top-down maps, and report that end-to-end policies failed consistently on the real robot because of the visual gap (Chaplot et al., 2020b). Active Neural SLAM was likewise deployed for exploration in a real apartment after matching the simulated camera to the robot’s (Chaplot et al., 2020a). These are small numbers of trials in single environments, and they show transfer is possible rather than how reliable it is.

Applications

Habitat’s authors motivate the field with a home robot asked to check whether a laptop is on a desk and to bring it back, which needs perception, language understanding and navigation (Savva et al., 2019). Exploring and mapping a building on a time budget is useful in its own right, for example to pre-map an environment (Chaplot et al., 2020a). Object-goal navigation ends where interaction begins: Batra et al. (2020) present oracle visibility as a proxy for the moment a navigation module can hand control to an interaction module, which leads on to grasping, manipulation and, for a precise final approach, visual servoing. On roads, the equivalent problem is part of autonomous-driving perception and planning. Navigation is one of the tasks Habitat was built for, alongside instruction following and question answering (Savva et al., 2019), and it is a central setting for embodied AI, the wider study of agents that perceive and act, and for robot perception.

Open Problems

• Localization without ideal sensors. In the 2020 results above, PointNav with idealized GPS+Compass and noise-free actions was close to solved in simulation, and without them it was not (Wijmans et al., 2020; Datta et al., 2020).
• Semantic goals. In the same period ObjectNav success in unseen buildings was far below PointNav’s, limited both by recognition and by finding the object (Chaplot et al., 2020b).
• Evaluation. SPL’s blind spots and the dependence of results on simulator details such as collision handling make numbers from different setups hard to compare.
• Transfer to robots. Real-world tests are slow and small, and rankings in simulation need not hold on robots (Kadian et al., 2020).
• Changing environments. The benchmarks above mostly use static scans of buildings (our observation); moving people, moved furniture and closed doors are largely absent.
• Language and interaction. Following instructions, asking questions and moving objects to reach a goal combine navigation with abilities that PointNav deliberately leaves out.