Multi Robot Motion Planning Eval

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

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

@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