In advanced robotics, we rarely evaluate algorithms on a single hand-crafted scenario. Instead, we consider families of tasks such as motion planning problems in different cluttered environments, or grasping tasks over a set of unknown objects. A dataset is a finite collection of such tasks (and possibly demonstration or sensor data), while a benchmark adds a protocol for how algorithms interact with these tasks: train/test splits, repeated trials, and metrics (Lesson 1).

Let \( \mathcal{T} \) denote a task space (e.g., all collision-free motion planning problems for a given manipulator). A benchmark designer implicitly chooses a distribution \( p_{\text{bench}} \) over \( \mathcal{T} \) and draws a finite sample:

\[ D = \{ \tau_i \}_{i=1}^n, \quad \tau_i \sim p_{\text{bench}} \;\text{i.i.d.} \]

An algorithm \( \pi \) (planner, controller, or policy) interacts with each task \( \tau_i \) and produces a trajectory, policy, or discrete plan; a loss functional \( L(\pi,\tau_i) \) (e.g., failure indicator, path cost) is then computed via the metrics of Lesson 1.

From a systems viewpoint, benchmark design couples:

• Task parametrization: compact description of environments, goals, dynamics.
• Sampling scheme: how tasks are drawn to approximate the desired \( p_{\text{bench}} \).
• Evaluation protocol: number of trials, timeouts, random seeds, etc.

flowchart TD
  A["Define task space T"] --> B["Specify target distribution p_bench over T"]
  B --> C["Sample finite task set D = {tau_i}"]
  C --> D["Release dataset + protocol (splits, seeds, limits)"]
  D --> E["Algorithms run on D under common protocol"]
  E --> F["Compute metrics (success, cost, time, etc.)"]
  F --> G["Compare methods + analyze generalization"]
        

For motion planning, a single task can be idealized as a tuple

\[ \tau = \big( C_{\text{free}}, q_{\text{start}}, q_{\text{goal}}, J \big), \]

where \( C_{\text{free}} \subseteq C \) is the collision-free subset of configuration space, \( q_{\text{start}}, q_{\text{goal}} \in C_{\text{free}} \) are boundary configurations, and \( J \) is a cost functional on trajectories (e.g., path length, integrated squared acceleration).

A dataset of such tasks is then

\[ D_{\text{plan}} = \{ \tau_i \}_{i=1}^{n}, \quad \tau_i = \big( C_{\text{free}}^{(i)}, q_{\text{start}}^{(i)}, q_{\text{goal}}^{(i)}, J^{(i)} \big). \]

For manipulation or RL-based controllers (Chapters 11–12), a task can be modeled as a Markov decision process (MDP):

\[ \tau = \big( \mathcal{S}, \mathcal{A}, P, r, \gamma, \rho_0 \big), \]

where \( \mathcal{S} \) is the state space, \( \mathcal{A} \) the action space, \( P \) transition kernel, \( r \) reward, \( \gamma \) discount factor, and \( \rho_0 \) initial-state distribution.

In both cases we may introduce a task parameter vector \( \theta \in \Theta \) (e.g., obstacle layouts, object shapes, friction coefficients) and a deterministic map \( \Phi : \Theta \rightarrow \mathcal{T} \) from parameters to fully specified tasks:

\[ \tau = \Phi(\theta), \quad \theta \sim p(\theta). \]

The benchmark designer chooses \( p(\theta) \) to control what is considered “typical” or “hard” in the evaluation. This parameterization is extremely useful in simulation where randomization over scenes, object placements, and physical parameters is cheap.

Given a fixed algorithm \( \pi \) and tasks \( \tau_i \sim p_{\text{test}} \), the true expected loss is

\[ R(\pi) = \mathbb{E}_{\tau \sim p_{\text{test}}}\big[ L(\pi,\tau) \big], \]

while the empirical benchmark estimate on \( m \) test tasks is

\[ \hat{R}_m(\pi) = \frac{1}{m} \sum_{i=1}^{m} L\big(\pi,\tau_i\big). \]

Suppose the loss is bounded, e.g. \( L(\pi,\tau) \in [0,1] \) (success/failure or a normalized cost). Since \( L(\pi,\tau_i) \) are i.i.d., Hoeffding’s inequality yields, for any \( \varepsilon > 0 \),

\[ \Pr\big( \big|\hat{R}_m(\pi) - R(\pi)\big| \ge \varepsilon \big) \le 2 \exp\big( -2 m \varepsilon^2 \big). \]

To obtain a deviation \( \varepsilon \) with confidence \( 1-\delta \) it suffices that

\[ m \ge \frac{1}{2 \varepsilon^2} \log\!\left(\frac{2}{\delta}\right). \]

Interpretation for robotic benchmarks. If we want the estimated failure probability on random planning problems to be within \( \pm 0.05 \) with probability \( 0.95 \), then \( \varepsilon = 0.05, \delta = 0.05 \) gives \( m \approx 600 \) tasks. This shows why modern benchmarks often contain hundreds or thousands of tasks rather than a handful of “toy” scenes.

For comparing two algorithms \( \pi_1, \pi_2 \), a similar argument on the difference of losses leads to slightly larger but same-order sample requirements.

Robotic tasks are rarely homogeneous. For example, we might partition motion planning problems into:

• low-DOF vs high-DOF manipulators,
• sparse vs cluttered environments,
• quasi-static vs dynamic tasks.

Let these form \( K \) disjoint strata \( \mathcal{T}_1, \dots, \mathcal{T}_K \), with mixing weights \( w_k = \Pr(\tau \in \mathcal{T}_k) \) under the target test distribution. Within each stratum, define the variance of the loss \( \sigma_k^2 = \operatorname{Var}\big[L(\pi,\tau) \mid \tau \in \mathcal{T}_k\big] \).

Suppose we choose \( n_k \) benchmark tasks from stratum \( k \), with total budget \( \sum_k n_k = N \). The stratified empirical risk is

\[ \hat{R}_{\text{strat}}(\pi) = \sum_{k=1}^{K} w_k \left( \frac{1}{n_k} \sum_{i \in S_k} L(\pi,\tau_i) \right). \]

Under independence, its variance is approximately

\[ \operatorname{Var}\big[\hat{R}_{\text{strat}}(\pi)\big] \approx \sum_{k=1}^{K} \frac{w_k^2 \sigma_k^2}{n_k}. \]

We can optimize \( n_k \) to minimize this variance under the constraint \( \sum_k n_k = N \). Introduce a Lagrange multiplier \( \lambda \) and consider

\[ \mathcal{L}(n_1,\dots,n_K,\lambda) = \sum_{k=1}^{K} \frac{w_k^2 \sigma_k^2}{n_k} + \lambda\left( \sum_{k=1}^{K} n_k - N \right). \]

Setting partial derivatives to zero,

\[ \frac{\partial \mathcal{L}}{\partial n_k} = -\frac{w_k^2 \sigma_k^2}{n_k^2} + \lambda = 0 \quad \Rightarrow \quad n_k = \frac{w_k \sigma_k}{\sqrt{\lambda}}. \]

Using \( \sum_k n_k = N \) determines \( \sqrt{\lambda} \), yielding

\[ n_k^{\star} = N \cdot \frac{w_k \sigma_k}{\sum_{j=1}^{K} w_j \sigma_j}. \]

Thus, more tasks should be placed in strata that are both likely (large \( w_k \)) and high-variance (large \( \sigma_k \)). This is a principled recipe for “balancing” easy vs hard scenes in a benchmark.

Practically, we estimate \( \sigma_k \) from pilot runs and then choose \( n_k \) accordingly.

Often we have a large pool of candidate tasks \( U = \{\tau^{(1)},\dots,\tau^{(M)}\} \) (e.g. many randomly generated environments) and wish to select a smaller benchmark subset \( S \subset U \) of size \( |S| = B \). To formalize diversity, we embed each task into a feature space via \( \varphi : \mathcal{T} \rightarrow \mathbb{R}^d \), where features might include:

• number of obstacles, average clearance, narrow passage scores;
• manipulator reachability indices;
• RL task features such as horizon length or reward sparsity.

A classic design objective is the k-center (coverage) objective:

\[ \min_{S \subset U,\, |S| = B} \;\max_{\tau \in U} \;\min_{\sigma \in S} \big\| \varphi(\tau) - \varphi(\sigma) \big\|_2. \]

This chooses \( B \) tasks so that every candidate is close in feature space to some selected benchmark task. The problem is NP-hard, but a simple greedy algorithm (always add the task farthest from the current set in feature space) achieves a constant-factor approximation.

In practice, the benchmark designer:

1. Defines task features \( \varphi(\tau) \) from geometry and dynamics.
2. Computes pairwise distances on a large pool of generated tasks.
3. Runs a greedy selection or clustering algorithm (k-center, k-medoids, or k-means).
4. Allocates per-stratum budgets \( n_k \) using the stratified analysis above.

flowchart TD
  U["Generate large task pool U"] --> FEAT["Compute feature vectors phi(tau)"]
  FEAT --> SEL["Select B centers maximizing coverage in feature space"]
  SEL --> STRAT["Adjust counts per stratum using n_k*"]
  STRAT --> BENCH["Finalize benchmark suite S and publish metadata"]
        

We illustrate a simple benchmark generator for 2D motion planning using Python. In a real project you would integrate with ompl (Open Motion Planning Library) Python bindings or moveit task definitions; here we focus on task sampling and selection.

import numpy as np
from dataclasses import dataclass
from typing import List, Tuple

np.random.seed(0)

@dataclass
class PlanningTask2D:
    start: np.ndarray        # shape (2,)
    goal: np.ndarray         # shape (2,)
    obstacles: np.ndarray    # shape (K, 4), axis-aligned boxes [x_min, y_min, x_max, y_max]

def random_box():
    x1, y1 = np.random.rand(2)
    x2, y2 = np.random.rand(2)
    x_min, x_max = sorted([x1, x2])
    y_min, y_max = sorted([y1, y2])
    # Shrink to avoid full blockage
    w = (x_max - x_min) * 0.7
    h = (y_max - y_min) * 0.7
    return np.array([x_min, y_min, x_min + w, y_min + h])

def sample_task(num_obstacles: int) -> PlanningTask2D:
    start = np.random.rand(2)
    goal = np.random.rand(2)
    obstacles = np.stack([random_box() for _ in range(num_obstacles)], axis=0)
    return PlanningTask2D(start=start, goal=goal, obstacles=obstacles)

def clearance_feature(task: PlanningTask2D, num_samples: int = 32) -> float:
    """
    Crude estimate of average clearance along straight-line path.
    """
    ts = np.linspace(0.0, 1.0, num_samples)
    pts = (1 - ts)[:, None] * task.start[None, :] + ts[:, None] * task.goal[None, :]
    min_dists = []
    for p in pts:
        # signed distance to axis-aligned boxes (positive outside)
        d = []
        for (xmin, ymin, xmax, ymax) in task.obstacles:
            dx = max(xmin - p[0], 0, p[0] - xmax)
            dy = max(ymin - p[1], 0, p[1] - ymax)
            d.append(np.hypot(dx, dy))
        min_dists.append(min(d) if d else 1.0)
    return float(np.mean(min_dists))

def feature_vector(task: PlanningTask2D) -> np.ndarray:
    # Example features: num_obstacles, path_length, avg_clearance
    num_obs = float(task.obstacles.shape[0])
    path_len = float(np.linalg.norm(task.goal - task.start))
    clear = clearance_feature(task)
    return np.array([num_obs, path_len, clear], dtype=float)

def greedy_k_center(tasks: List[PlanningTask2D], B: int) -> List[int]:
    """
    Greedy k-center over feature vectors. Returns indices of selected tasks.
    """
    feats = np.stack([feature_vector(t) for t in tasks], axis=0)
    # Normalize features for fair distances
    mu = feats.mean(axis=0, keepdims=True)
    sigma = feats.std(axis=0, keepdims=True) + 1e-8
    feats_n = (feats - mu) / sigma

    n = feats_n.shape[0]
    # Start with a random center
    centers = [np.random.randint(0, n)]
    # Precompute distance matrix (small demo)
    dists = np.linalg.norm(feats_n[:, None, :] - feats_n[None, :, :], axis=-1)

    while len(centers) < B:
        # For each candidate, compute distance to closest chosen center
        min_to_center = dists[:, centers].min(axis=1)
        # Pick point with maximum such distance
        next_center = int(np.argmax(min_to_center))
        centers.append(next_center)
    return centers

# Generate a pool of tasks
pool_size = 200
tasks = []
for i in range(pool_size):
    # mixture of sparse and cluttered scenes
    num_obs = np.random.choice([2, 4, 8, 12], p=[0.2, 0.3, 0.3, 0.2])
    tasks.append(sample_task(num_obs))

# Select B benchmark tasks
B = 40
selected_indices = greedy_k_center(tasks, B)
benchmark_tasks = [tasks[i] for i in selected_indices]

print(f"Selected {len(benchmark_tasks)} tasks for the benchmark suite.")
      

The selected benchmark_tasks can be exported (e.g., as JSON) and used by planning libraries such as ompl or moveit. Additional metadata (stratum labels, difficulty scores, ground-truth optimal costs) should be stored alongside.

In C++, benchmark infrastructures (e.g. in OMPL and ROS MoveIt) typically define an abstract task class and store tasks in configuration files. Below is a minimal example of such an abstraction, independent of a specific planner library:

#include <vector>
#include <array>
#include <string>
#include <random>
#include <memory>

struct Box2D {
  double xmin, ymin, xmax, ymax;
};

struct PlanningTask2D {
  std::array<double, 2> start;
  std::array<double, 2> goal;
  std::vector<Box2D> obstacles;
  std::string id;       // unique name for logging
  int stratum_id;       // e.g. clutter level
};

class TaskGenerator {
public:
  explicit TaskGenerator(unsigned seed = 0)
      : gen_(seed), uni_(0.0, 1.0) {}

  PlanningTask2D sampleTask(int numObs, int stratumId, const std::string& prefix) {
    PlanningTask2D t;
    t.start = {rand01(), rand01()};
    t.goal  = {rand01(), rand01()};
    t.stratum_id = stratumId;

    for (int i = 0; i < numObs; ++i) {
      t.obstacles.push_back(randomBox());
    }
    t.id = prefix + "_" + std::to_string(counter_++);
    return t;
  }

private:
  std::mt19937 gen_;
  std::uniform_real_distribution<double> uni_;
  int counter_ = 0;

  double rand01() { return uni_(gen_); }

  Box2D randomBox() {
    double x1 = rand01(), y1 = rand01();
    double x2 = rand01(), y2 = rand01();
    double xmin = std::min(x1, x2);
    double xmax = std::max(x1, x2);
    double ymin = std::min(y1, y2);
    double ymax = std::max(y1, y2);
    double w = (xmax - xmin) * 0.7;
    double h = (ymax - ymin) * 0.7;
    return Box2D{xmin, ymin, xmin + w, ymin + h};
  }
};

// Example usage: generate tasks and serialize them for a ROS/MoveIt benchmark node.
int main() {
  TaskGenerator gen(42);
  std::vector<PlanningTask2D> pool;
  for (int i = 0; i < 200; ++i) {
    int numObs = (i % 4 + 1) * 2;  // vary clutter
    int stratum = i % 3;
    pool.push_back(gen.sampleTask(numObs, stratum, "task"));
  }

  // TODO: compute feature vectors and run same greedy k-center selection as in Python.
  // TODO: save to YAML/JSON for consumption by OMPL or MoveIt.
  return 0;
}
      

In an actual benchmark, you would connect PlanningTask2D to an OMPL SpaceInformation object and use a benchmark harness to run multiple planners with consistent time limits and random seeds across all tasks.

For Java-based robotic systems (e.g., using ROSJava or simulators written in Java), we often write a benchmark harness that loads task descriptions (from JSON/YAML) and calls a planner API. Below is a sketch that mirrors the design used in other languages.

import java.util.*;
import java.util.stream.Collectors;

class Box2D {
    public double xmin, ymin, xmax, ymax;
    public Box2D(double xmin, double ymin, double xmax, double ymax) {
        this.xmin = xmin; this.ymin = ymin;
        this.xmax = xmax; this.ymax = ymax;
    }
}

class PlanningTask2D {
    public double[] start;
    public double[] goal;
    public List<Box2D> obstacles;
    public String id;
    public int stratumId;

    public PlanningTask2D(double[] start, double[] goal, List<Box2D> obstacles,
                          String id, int stratumId) {
        this.start = start;
        this.goal = goal;
        this.obstacles = obstacles;
        this.id = id;
        this.stratumId = stratumId;
    }
}

interface Planner {
    // Returns true if a collision-free solution is found within the time limit.
    boolean solve(PlanningTask2D task, double timeLimitSeconds);
}

class BenchmarkResult {
    public String plannerName;
    public String taskId;
    public boolean success;
    public double solveTime;

    public BenchmarkResult(String plannerName, String taskId,
                           boolean success, double solveTime) {
        this.plannerName = plannerName;
        this.taskId = taskId;
        this.success = success;
        this.solveTime = solveTime;
    }
}

class BenchmarkHarness {
    private List<PlanningTask2D> tasks;
    private List<Planner> planners;
    private Map<Planner,String> plannerNames;

    public BenchmarkHarness(List<PlanningTask2D> tasks) {
        this.tasks = tasks;
        this.planners = new ArrayList<>();
        this.plannerNames = new HashMap<>();
    }

    public void addPlanner(Planner planner, String name) {
        planners.add(planner);
        plannerNames.put(planner, name);
    }

    public List<BenchmarkResult> run(double timeLimitSeconds, int numRepeats) {
        List<BenchmarkResult> results = new ArrayList<>();
        for (Planner planner : planners) {
            for (PlanningTask2D task : tasks) {
                for (int r = 0; r < numRepeats; ++r) {
                    long t0 = System.nanoTime();
                    boolean success = planner.solve(task, timeLimitSeconds);
                    long t1 = System.nanoTime();
                    double elapsed = (t1 - t0) * 1e-9;
                    results.add(new BenchmarkResult(
                        plannerNames.get(planner),
                        task.id,
                        success,
                        elapsed
                    ));
                }
            }
        }
        return results;
    }

    public Map<String, Double> computeSuccessRates(List<BenchmarkResult> results) {
        Map<String, List<BenchmarkResult>> byPlanner =
            results.stream().collect(Collectors.groupingBy(r -> r.plannerName));
        Map<String, Double> success = new HashMap<>();
        for (String p : byPlanner.keySet()) {
            List<BenchmarkResult> rs = byPlanner.get(p);
            long numSuccess = rs.stream().filter(r -> r.success).count();
            success.put(p, numSuccess / (double) rs.size());
        }
        return success;
    }
}
      

The harness enforces a consistent protocol across planners. The task set itself is designed using the statistical and geometric principles from earlier sections.

MATLAB with Robotics System Toolbox and Simulink is frequently used to prototype task generators for manipulation and kinodynamic planning. Below, we build a simple generator for planar reach tasks and compute a scalar difficulty index based on joint-space distance.

% Define a 2-DOF planar arm using Robotics System Toolbox
L1 = 1.0; L2 = 0.7;
robot = rigidBodyTree('DataFormat','row','MaxNumBodies',3);
body1 = rigidBody('link1');
jnt1  = rigidBodyJoint('joint1','revolute');
setFixedTransform(jnt1,trvec2tform([0 0 0]));
body1.Joint = jnt1;
addBody(robot,body1,'base');

body2 = rigidBody('link2');
jnt2  = rigidBodyJoint('joint2','revolute');
setFixedTransform(jnt2,trvec2tform([L1 0 0]));
body2.Joint = jnt2;
addBody(robot,body2,'link1');

% Task generator: random end-effector poses within workspace
numTasks = 100;
qStart = zeros(numTasks,2);
qGoal  = zeros(numTasks,2);
difficulty = zeros(numTasks,1);

ik = inverseKinematics('RigidBodyTree',robot);
weights = [1 1 0 0 0 0];
endEff = 'link2';

for i = 1:numTasks
    % sample reachable XY position
    r = (L1 + L2) * 0.8 * sqrt(rand());
    theta = 2*pi*rand();
    targetPos = [r*cos(theta), r*sin(theta), 0];

    % start and goal poses
    Tstart = trvec2tform([0 0 0]);
    Tgoal  = trvec2tform(targetPos);

    [qStart(i,:), ~] = ik(endEff,Tstart,weights,robot.homeConfiguration);
    [qGoal(i,:),  ~] = ik(endEff,Tgoal, weights,robot.homeConfiguration);

    difficulty(i) = norm(qGoal(i,:) - qStart(i,:)); % joint distance
end

% Stratify tasks by difficulty tertiles for later benchmark design
edges = quantile(difficulty,[0 1/3 2/3 1]);
stratumId = discretize(difficulty, edges);

taskDataset = table(qStart, qGoal, difficulty, stratumId);
disp(head(taskDataset));
      

In Simulink, each task can be fed into a closed-loop controller model as an input signal (desired end-effector pose), while performance metrics (settling time, overshoot, etc.) are logged to construct the benchmark.

Wolfram Mathematica can be used to prototype the coverage-optimization step symbolically or numerically. The snippet below implements a simple k-center objective and greedy selection on a precomputed feature matrix Phi.

(* Phi is an n x d matrix of task features *)
greedyKCenter[phi_, B_Integer] := Module[
  {n = Length[phi], centers, distMat, nearest, farthest},
  distMat = DistanceMatrix[phi];
  centers = {RandomInteger[{1, n}]};
  While[Length[centers] < B,
    nearest = Map[Min[distMat[[#, centers]]] &, Range[n]];
    farthest = First@Ordering[nearest, -1];
    centers = Append[centers, farthest];
  ];
  centers
];

(* Example usage *)
n = 200; d = 3;
phi = RandomReal[{0, 1}, {n, d}];
selected = greedyKCenter[phi, 40];
      

These high-level tools allow rapid exploration of task distributions and benchmark-selection algorithms before committing to large-scale C++ or Python implementations.

Problem 1 (Sample Complexity for Binary Success): Consider a benchmark for a motion planner in which each task yields loss \( L(\pi,\tau_i) \in \{0,1\} \) (0 for success, 1 for failure). Show that to guarantee \( \Pr\big( |\hat{R}_m(\pi) - R(\pi)| \le \varepsilon \big) \ge 1-\delta \), it suffices that \( m \ge \frac{1}{2\varepsilon^2} \log\!\big(\frac{2}{\delta}\big) \).

Solution: Since the losses are bounded in \( [0,1] \), they satisfy Hoeffding’s inequality:

\[ \Pr\big( |\hat{R}_m(\pi) - R(\pi)| \ge \varepsilon \big) \le 2 \exp\big( -2 m \varepsilon^2 \big). \]

We require the right-hand side to be at most \( \delta \), i.e. \( 2 \exp(-2 m \varepsilon^2) \le \delta \). Taking logarithms and rearranging gives \( -2 m \varepsilon^2 \le \log(\delta/2) \), hence \( m \ge \frac{1}{2\varepsilon^2} \log\!\big(\frac{2}{\delta}\big) \), as claimed.

Problem 2 (Optimal Allocation in Stratified Benchmarks): Using the notation of Section 4, derive the optimal sample counts \( n_k^{\star} \) that minimize \( \operatorname{Var}[\hat{R}_{\text{strat}}(\pi)] \approx \sum_{k=1}^{K} \frac{w_k^2 \sigma_k^2}{n_k} \) under the constraint \( \sum_k n_k = N \) and \( n_k > 0 \).

Solution: Introduce a Lagrange multiplier \( \lambda \) and consider

\[ \mathcal{L}(n_1,\dots,n_K,\lambda) = \sum_{k=1}^{K} \frac{w_k^2 \sigma_k^2}{n_k} + \lambda\left( \sum_{k=1}^{K} n_k - N \right). \]

Differentiating with respect to \( n_k \) and setting to zero:

\[ \frac{\partial \mathcal{L}}{\partial n_k} = -\frac{w_k^2 \sigma_k^2}{n_k^2} + \lambda = 0 \quad \Rightarrow \quad n_k = \frac{w_k \sigma_k}{\sqrt{\lambda}}. \]

Summing over \( k \) and imposing \( \sum_k n_k = N \) yields

\[ \sum_{k=1}^{K} \frac{w_k \sigma_k}{\sqrt{\lambda}} = N \quad \Rightarrow \quad \sqrt{\lambda} = \frac{\sum_{j=1}^{K} w_j \sigma_j}{N}. \]

Substitution gives

\[ n_k^{\star} = N \cdot \frac{w_k \sigma_k}{\sum_{j=1}^{K} w_j \sigma_j}, \]

which is the proportional allocation rule used in Section 4.

Problem 3 (Bias from Non-Representative Benchmarks): Let \( p_{\text{bench}} \) be the benchmark task distribution and \( p_{\text{deploy}} \) the distribution encountered in deployment. Show that even if \( \hat{R}_m(\pi) \) is an unbiased estimator of \( R_{\text{bench}}(\pi) = \mathbb{E}_{\tau \sim p_{\text{bench}}}[L(\pi,\tau)] \), it can be a biased estimator of \( R_{\text{deploy}}(\pi) = \mathbb{E}_{\tau \sim p_{\text{deploy}}}[L(\pi,\tau)] \) whenever \( p_{\text{bench}} \neq p_{\text{deploy}} \).

Solution: By construction,

\[ \mathbb{E}\big[\hat{R}_m(\pi)\big] = \mathbb{E}_{\tau \sim p_{\text{bench}}}[L(\pi,\tau)] = R_{\text{bench}}(\pi). \]

The deployment risk is

\[ R_{\text{deploy}}(\pi) = \mathbb{E}_{\tau \sim p_{\text{deploy}}}[L(\pi,\tau)]. \]

Unless \( p_{\text{bench}} = p_{\text{deploy}} \) (almost everywhere), \( R_{\text{bench}}(\pi) \) and \( R_{\text{deploy}}(\pi) \) generally differ, so \( \hat{R}_m(\pi) \) is a biased estimator of \( R_{\text{deploy}}(\pi) \). The difference \( R_{\text{deploy}}(\pi) - R_{\text{bench}}(\pi) \) quantifies the dataset shift bias introduced by a non-representative benchmark.

Problem 4 (Coverage Objective as Upper Bound on Interpolation Error): Suppose that for a given planner family, the loss \( L(\pi,\tau) \) varies Lipschitz-continuously with task features: there exists \( L_f > 0 \) such that \( |L(\pi,\tau) - L(\pi,\sigma)| \le L_f \| \varphi(\tau)-\varphi(\sigma) \|_2 \) for all tasks \( \tau,\sigma \). Show that for any candidate task \( \tau \) and benchmark subset \( S \),

\[ \big| L(\pi,\tau) - L(\pi,\sigma^{\star}) \big| \le L_f \cdot \min_{\sigma \in S} \big\| \varphi(\tau)-\varphi(\sigma) \big\|_2, \]

where \( \sigma^{\star} \) attains the minimum in the right-hand side.

Solution: By definition of the Lipschitz condition applied to the pair \( (\tau,\sigma^{\star}) \),

\[ \big| L(\pi,\tau) - L(\pi,\sigma^{\star}) \big| \le L_f \big\| \varphi(\tau)-\varphi(\sigma^{\star}) \big\|_2. \]

Since \( \sigma^{\star} \) minimizes the feature-space distance over all \( \sigma \in S \), we have \( \|\varphi(\tau)-\varphi(\sigma^{\star})\|_2 = \min_{\sigma \in S} \|\varphi(\tau)-\varphi(\sigma)\|_2 \), which yields the claimed inequality. The k-center objective precisely minimizes the maximum of this bound over \( \tau \in U \).

Problem 5 (Train/Test Leakage in Robotics Benchmarks): Suppose a learned policy \( \pi_{\theta} \) is trained on a dataset of tasks \( D_{\text{train}} \) and evaluated on the same tasks (no hold-out). Argue formally why \( \hat{R}_{\text{train}}(\pi_{\theta}) \) underestimates the true generalization risk on new tasks drawn from the same distribution.

Solution: Because \( \theta \) is chosen by minimizing empirical risk on \( D_{\text{train}} \), i.e.

\[ \theta^{\star} = \arg\min_{\theta} \frac{1}{|D_{\text{train}}|} \sum_{\tau \in D_{\text{train}}} L(\pi_{\theta},\tau), \]

the random variable \( \hat{R}_{\text{train}}(\pi_{\theta^{\star}}) \) is biased downward due to selection. Formally, \( \mathbb{E}[\hat{R}_{\text{train}}(\pi_{\theta^{\star}})] \le \mathbb{E}_{\tau \sim p}[L(\pi_{\theta^{\star}},\tau)] \), where the expectation on the right is over a fresh task \( \tau \). This gap can be made arbitrarily large with sufficiently expressive policy classes, motivating separate validation/test benchmarks drawn after training.

In this lesson we treated datasets and task benchmarks as finite approximations of underlying task distributions for planning and manipulation. By modeling tasks via parameters \( \theta \) and features \( \varphi(\tau) \), we derived sample-complexity guarantees for empirical metrics, optimal stratified allocations, and coverage-based selection objectives. We then connected these mathematical ideas to practical implementations in Python, C++, Java, MATLAB/Simulink, and Mathematica, emphasizing the importance of consistent protocols and representative task distributions for fair comparison of advanced robotic algorithms.