Farthest-point sampling

Overview

Farthest-point sampling (FPS) picks a subset of N points from a larger set so that the chosen points are spread out. It is greedy. It starts from one point, then repeatedly adds the point whose distance to the chosen set is largest. The paper calls it the standard greedy algorithm for this job [arxiv:2411.02446 app. E.1].

FPS is used here as a subroutine. The paper does not run it on states. It runs it on the actions of a batch of recorded steps, then keeps the states at the chosen steps 2411.02446 §3.2. The output is therefore a set of milestone states, not a set of actions.

This page covers one paper so far. Only one card in this wiki lists the slug, so there is one variant below, plus one ablation that replaces FPS with a fixed rule.

Variants

Action-space subgoal selection (DAD)

The paper calls this selection rule DAD. It takes recent episodes that used an environment goal, flattens the actions of all their steps into one pool, runs FPS on that pool, and keeps the states at the chosen steps as subgoals 2411.02446 §3.2 alg. 2. The authors argue that large action changes mark milestones such as closing the gripper, grasping, lifting and releasing a block 2411.02446 §3.2. Card: Learning World Models for Unconstrained Goal Navigation.

• Candidate pool. The released configs draw a batch of 45 episodes of 50 steps in most task blocks, which gives about 2250 candidate steps per call. The paper does not state the pool size 2411.02446 app. E.1.
• Number chosen. Table 2 sets 20 subgoals for five of the six simulated tasks and 10 for the sixth 2411.02446 tab. 2.
• Distance. The paper does not state the metric [arxiv:2411.02446 app. E.1]. The card's Pitfalls section records the released code's choice.
• Refresh. The paper says the subgoal set is refreshed periodically, with no rate given 2411.02446 alg. 1.
• Limitation the authors name. When the action space is complex or weakly tied to the goal space, DAD can select irrelevant states and this degrades the method 2411.02446 app. B.

Fixed-interval subgoals (ablation, no FPS)

MUN-noDAD replaces FPS with states taken at evenly spaced times in the sampled episodes 2411.02446 app. D.5 alg. 8. It keeps the rest of the method. It is the paper's own control for the selection rule, and it is the only other option on this page.

When to use which

Implementation sketch

The core is greedy selection over a pool of vectors. Variants differ in what the vectors are (actions here), how the distance is measured, and how the chosen indices are mapped back to states.

# Farthest-point sampling  [arxiv:2411.02446 app. E.1]
# Metric and start rule are not fixed by the paper

def farthest_point_sampling(points, num_samples):
    # Start from a random point  [arxiv:2411.02446 app. E.1]
    chosen = [random_index(len(points))]
    # Distance from each point to its nearest chosen point
    min_dist = distance(points, points[chosen[0]])
    for _ in range(num_samples - 1):
        # Take the point farthest from every chosen point
        nxt = argmax(min_dist)
        chosen.append(nxt)
        # Update each point's distance to its nearest chosen point
        min_dist = minimum(min_dist, distance(points, points[nxt]))
    return chosen  # indices into points

For DAD, points holds the flattened actions of the batch. The returned indices are step numbers, so the caller keeps the state recorded at each step as a subgoal 2411.02446 alg. 2. The paper's eta map is the identity in this setting 2411.02446 §2.

Contradictions

• Where FPS is used. The paper describes DAD as the subgoal method for all tasks 2411.02446 §3.2 alg. 2. The released code uses a different selection strategy for the 3-Block, Walker and Block Rotation configs, and implements FPS in only one of its strategies. The paper does not say which strategy produced its 3-Block figures. Details are in the card's Paper vs code section.
• Stopping early. The paper's pseudocode returns the requested number of points 2411.02446 app. E.1. The released code can return fewer, when the largest remaining distance falls below a small threshold. The card's Pitfalls section records this.

Papers

• Learning World Models for Unconstrained Goal Navigation: introduces DAD, which uses FPS over action vectors to choose subgoal states for training a goal-conditioned world model.