On Evaluation of Embodied Navigation Agents

In plain words

Researchers who build robots and game-like agents that move through rooms have been testing them in many different ways. One paper asks a bad question and another asks a different one, so their results cannot be compared. This paper is the output of a working group that agreed on how such agents should be tested.

The group's main points are these. An agent should say out loud when it thinks it has arrived, because an agent that stumbles near the goal has not navigated to it on purpose. Distance should be measured along the walkable path, not through walls. The score should reward both reaching the goal and not wasting the trip, and the paper names one such score as the main number. Tests should run in simulators with continuous space and real-world units, so that what works in simulation can be moved to a physical robot. Finally, the group publishes a set of fixed test scenarios so that everyone runs the same tasks.

TL;DR

This is a recommendation paper, not a new method: it contains no trained model and no experiments of its own. It asks for explicit goal and sensor reporting, quantified prior exploration, a DONE action, geodesic success distance, and SPL as the primary measure. It also defines standard scenarios for four simulator datasets. Use it when you design or compare navigation benchmarks.

Problem

Navigation research uses many task definitions and evaluation protocols that do not agree with each other §1. Protocols that end an episode as soon as the agent comes close to the goal do not test whether the agent knew it had reached the goal §4. Euclidean distance ignores walls, so a point behind a wall can look close §4. The amount of prior experience an agent has in the test environment varies widely between protocols, which affects how the results should be read §3. The paper notes that simulators are often regarded with skepticism, but that they allow reproducible comparisons §5.

Method

The paper's output is seven recommendations. There is no algorithm and no pseudocode in the source. Recommendations 1 to 7 are labelled in the text §4 §5 §7. The sections below restate them as an implementer needs them.

1. Goal types and sensors §2. The paper distinguishes three goal types: PointGoal (navigate to coordinates), ObjectGoal (navigate to an object of a category), and AreaGoal (navigate to an area of a category). It also notes that goals can be specified by an image or by natural language. The paper asks that the sensory input be stated explicitly, including any perfect odometry or GPS assumption.
2. Prior exploration regime §3. The paper names three regimes: no prior exploration; pre-recorded exploration of the test environment supplied with the benchmark; and time-limited exploration by the agent under a budget. In the last regime, navigation performance is reported as a function of the exploration budget. The paper uses 500 m, 1,000 m and 2,000 m as examples of budgets §3. It asks that the amount of prior exposure be quantified and documented.
3. Explicit DONE action (Recommendation 1) §4. The agent must have a dedicated action that it emits when it has finished. Success is evaluated at the moment the agent emits DONE, and the agent's configuration relative to the goal at that moment is the one that counts. An episode without DONE is not successful, even if the agent passed the goal earlier.
4. Geodesic distance (Recommendation 2) §4. Proximity to the goal is measured as the shortest path distance inside the environment. Euclidean distance is discouraged.
5. Success criterion §4. A PointGoal or ObjectGoal episode is successful if, at DONE, the distance to the goal is below a threshold τ. The default τ is twice the agent's body width. An AreaGoal episode is successful if the agent's centre of mass is inside the specified area §4.
6. SPL as the primary measure (Recommendation 3) §4. The paper defines SPL (success weighted by normalised inverse path length) with the formula in eq. 1. The auxiliary measures suggested are: success rate as a function of the normalised inverse distance travelled; distance to goal at the end of the episode; SPL swept over thresholds τ; the distribution of normalised inverse path length; the number of infractions, such as contact with obstacles; and actuation time and energy §4.
7. Continuous state spaces (Recommendation 4) §5. The paper recommends continuous state spaces, while acknowledging that discrete environments are convenient §5.
8. SI units (Recommendation 5) §5. Simulators should use SI units, so that a distance of 1 unit corresponds to 1 metre.
9. Simulator-to-robot path (Recommendation 6) §5. Simulators should ship with open-source software that lets an agent trained in simulation be deployed on a physical robot. The paper gives ROS as an example, with an API identical to the simulator's, and mentions a possible domain adaptation module §5.
10. Standard scenarios §6. Start and goal positions are sampled at random from free space and checked for navigability with a tile-based shortest-path computation. The paper gives the scenario sets for SUNCG, Matterport3D, AI2-THOR and Gibson in §6; see the Hyperparameters table.
11. Representation research (Recommendation 7) §7. The paper asks for research on the internal representation an agent builds while it moves through an environment. It does not recommend a specific form §7.

Evaluation protocol in pseudocode, from §4 and eq. 1:

# SPL over N episodes  [§4] [eq. 1]
# Input:  episodes, a list of N records (done_called, geodesic_to_goal,
#         shortest_len, path_len)
# Output: scalar in [0, 1]

def success_flag(done_called, geodesic_to_goal, threshold):
    # Only an explicit DONE counts; distance is geodesic  [§4 Rec. 1-2]
    # Threshold default is 2x body width  [§4]
    return done_called and geodesic_to_goal < threshold

def spl(episodes, threshold):
    # Accumulate S_i * l_i / max(p_i, l_i) over the N episodes  [eq. 1]
    total = 0.0
    for episode in episodes:
        # S_i: binary success flag  [§4]
        success = success_flag(episode.done_called,
                               episode.geodesic_to_goal,
                               threshold)
        # l_i: shortest-path length from start to goal  [§4]
        # p_i: length of the path the agent actually took  [§4]
        ratio = episode.shortest_len / max(episode.path_len,
                                           episode.shortest_len)
        total += success * ratio
    # Average over all N episodes, failed episodes included  [eq. 1]
    return total / len(episodes)

Hyperparameters

Values stated in the paper. Where the paper gives no value, the table says so.

Standard scenario sets §6:

For AI2-THOR, PointGoal uses 5 target points, 5 start points and 5 scene configurations per test scene (5 × 5 × 5 = 125). The PointGoal action set is Move Forward, Move Backward, Rotate Right, Rotate Left and Terminate §6. ObjectGoal uses 5 object categories and 5 configurations per scene, which the paper also counts as 125 scenarios §6.

Results

The paper reports no experimental results of its own. Its quantitative content is the worked SPL examples §4 and the scenario statistics §6. Both are the paper's own numbers.

SPL worked examples §4:

The paper expects an SPL of 0.5 to be a good level of navigation performance in reasonably complex environments not seen before, and suggests calibrating the figure against human SPL on each dataset §4.

Paper vs code

The only linked code is github.com/minosworld/scenarios (MIT, commit ad0dc57dae363480974b352c628025c65ded4ce0). It contains two scenario files and a README, and no method, simulator or evaluation code. It is the authors' scenario set referred to in §6. Clone: raw/code/1807.06757/.

• The repository ships navigation/suncg/pointgoal_suncg_v1.csv.bz2 (SUNCG, PointGoal) and navigation/mp3d/roomgoal_mp3d_v1.csv.bz2 (Matterport3D, room goal) pointgoal_suncg_v1.csv.bz2 roomgoal_mp3d_v1.csv.bz2. The paper names no goal type for either dataset §6, so the paper does not state which goal type the files encode.
• The README calls the goal type room_goal README.md. The paper calls the corresponding goal AreaGoal §2. The paper does not say whether these are the same task.
• The README defines dist as Euclidean and pathDist as geodesic distance from start to goal README.md. The paper recommends geodesic distance for proximity §4 Rec. 2. An implementer should use pathDist for the success check and for ℓ_i. This mapping is inferred from the README.
• The README changelog records version 0.1.0 (beta), released 2018-06-03 README.md. The paper is dated 2018-07-18 §6. Whether the shipped files match the numbers in §6 was not verified: I did not count the episodes per split.
• The AI2-THOR and Gibson scenario files are not in this repository. The paper points to other URLs for them §6. They were not fetched.
• No discrepancies found between the code and the recommendations §4 §5 beyond the points above. Only the scenario files are in the code, so the paper's method recommendations cannot be checked against code.

Pitfalls

• Recommendations, not measurements. Most of the card describes what the paper asks for. Nothing here was measured by the authors on an agent. Treat the thresholds and budgets as proposals.
• DONE is part of success. An agent that stops moving near the goal but never emits DONE scores 0 for that episode §4 Rec. 1. Agents trained without a DONE action need one added before they are evaluated under this protocol.
• Success is evaluated at DONE, not at the closest point. The paper says the configuration at the time of DONE counts, not a more favourable preceding moment §4.
• Geodesic distance depends on the agent. The paper notes that a ground vehicle and a drone can have different geodesic distances, because one must stay on the floor. Its default is computed at a fixed height above the floor §6. Compare agents only with the same distance definition.
• Undefined SPL term. If the path length p_i and the shortest path ℓ_i are both zero, the ratio in eq. 1 is 0/0. The paper does not say how to handle this case.
• Episode time limit not stated. The paper does not give a maximum episode length or a step budget.
• Thresholds are inequalities. Success uses "below τ" §4. Measurement noise at the threshold changes success counts, and the paper does not discuss it.
• Prior exploration changes what is measured. Under pre-recorded or time-limited regimes, an agent has seen the environment before the episode §3. Results from different regimes are not directly comparable. The paper asks for the regime to be stated with each result.
• Sensor and odometry assumptions. The paper asks that perfect odometry or GPS be stated explicitly §2. Without this statement, results cannot be compared with agents that do not have those inputs.
• SPL is strict. The paper calls SPL a rather stringent measure §4. A low SPL can come from a correct but long path, and the auxiliary measures §4 are meant to show that.
• AI2-THOR visibility rule. An ObjectGoal object counts as visible if it is within 1 m of the camera and in the field of view §6. The paper does not say whether this rule also gates success.
• Unfixed action space. In Gibson the action space is not fixed. The simulator offers discrete or continuous controllers §6. Results from different controllers are not directly comparable.

Lineage

• Builds on: not stated. The paper is a working-group consensus document §1.
• Compared against: not applicable. No method is evaluated.
• Simulators named, with arXiv ids in the paper's reference list: AI2-THOR arXiv:1712.05474 (reference 16) and MINOS arXiv:1712.03931 (reference 28). These papers have no cards here, so nothing from their content is used.
• Superseded by: not known from content in this wiki.