Multi Robot Motion Planning Eval

---
name: multi-robot-motion-planning-eval
description: This evaluation probes the scalability, asymptotic optimality, and computational efficiency of sampling-based motion planners in high-dimensional multi-robot configuration spaces. It measures how quickly algorithms find initial feasible paths, converge to optimal costs, and succeed under increasing dimensionality and robot counts. Use when the user wants to benchmark on 2 Disk Robots among 2D Polygons, Many Disk Robots among 2D Polygons, Dual-arm Manipulator (Motoman SDA10F), Motoman Tabletop Benchmark, Motoman Shelf Benchmark, or asks about evaluating this task. Reports success ratio.
metadata:
  skill_kind: dataset_eval
  source_arxiv: 1903.00994
  bibtex_key: shome2019drrt
  confidence: high
---

# multi-robot-motion-planning-eval

> dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning — Shome et al. (2019) (arXiv:1903.00994, 2019)

## What this evaluates

This evaluation probes the scalability, asymptotic optimality, and computational efficiency of sampling-based motion planners in high-dimensional multi-robot configuration spaces. It measures how quickly algorithms find initial feasible paths, converge to optimal costs, and succeed under increasing dimensionality and robot counts.

## Datasets

- **2 Disk Robots among 2D Polygons** — total ?; splits: test (-1)
- **Many Disk Robots among 2D Polygons** — total ?; splits: test (-1)
- **Dual-arm Manipulator (Motoman SDA10F)** — total ?; splits: test (-1)
- **Motoman Tabletop Benchmark** — total ?; splits: test (-1)
- **Motoman Shelf Benchmark** — total ?; splits: test (-1)

## Metrics

- `success ratio` **(primary)** — range: [0, 1]
  - Fraction of independent runs that successfully return a valid collision-free path within the iteration limit.
- `solution cost` — range: other
  - Sum of Euclidean arc lengths along the computed path. Often normalized by an optimistic lower bound (sum of individual robot optimal paths) for cross-environment comparison.
- `initial solution time` — range: other
  - Wall-clock time required to find the first feasible path.

## Input / output format

**Input**: Start and goal configurations for N robots in a defined geometric environment (e.g., 2D polygonal workspace or 3D manipulator with obstacles), along with algorithm parameters (roadmap size N, max iterations).

**Output**: A sequence of configurations forming a collision-free path, along with computed metrics: success flag, total path cost, time to first solution, and cost evolution over iterations.

## Scoring recipe

```python
def evaluate(planner, env, start, goal, max_iter=100000, runs=20):
    results = []
    for _ in range(runs):
        path, success, time_init, cost = planner.run(start, goal, max_iter)
        results.append({'success': success, 'initial_time': time_init, 'final_cost': cost})
    success_ratio = sum(1 for r in results if r['success']) / len(results)
    optimal_cost = env.get_optimistic_lower_bound()
    avg_normalized_cost = np.mean([r['final_cost'] / optimal_cost for r in results if r['success']])
    return success_ratio, avg_normalized_cost, results
```

## Common pitfalls

- Confusing initial solution time with full convergence time; the paper explicitly separates early anytime performance from asymptotic optimality.
- Assuming explicit roadmap construction scales to high dimensions; the paper notes PRM* hits memory limits (~1.7GB for N=500) and fails for R≥6.
- Comparing raw solution costs across different robot counts without normalization; costs must be divided by the optimistic lower bound to be comparable.

## Evidence (verbatim from paper)

> The success ratio shows the fraction of the runs that returned a solution. Solution costs are normalized by an optimistic estimate of the path cost for each case, which is the sum of the optimal solutions for each robot, disregarding robot-robot interactions.

## Citation

```bibtex
@misc{shome2019drrt,
  title={dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning},
  author={Shome et al. (2019)},
  year={2019},
  note={arXiv:1903.00994}
}
```

- arXiv: 1903.00994