Maps X Eval

maps-x-eval

MAPS-X: Explainable Multi-Robot Motion Planning via Segmentation — Kottinger et al. (2020) (arXiv:2010.16106, 2020)

What this evaluates

Evaluates the performance of explainable multi-robot motion planning algorithms (MAPS-X and Lazy MAPS-X) combined with sampling-based planners like RRT* across custom environments. It measures the trade-off between planning efficiency (runtime, success rate) and explainability (number of trajectory segments), highlighting how segmentation constraints impact computational cost and plan optimality.

Datasets

• MAPS-X custom environments — total ?; splits: (unstated); repo https://github.com/aria-systems-group/MAPS-X

Metrics

• Runtime(s) (primary) — range: seconds
  • Total computation time per planning run in seconds. Reported as mean ± standard deviation over 200 runs.
• Ave.Cost — range: other
  • Average plan cost (e.g., path length or makespan) across successful runs.
• # Solns.Found (%) — range: percent
  • Success rate, calculated as the percentage of runs that found a valid collision-free plan within the time limit.
• SegmentTime (s) — range: seconds
  • Time spent specifically on computing the trajectory segmentation for explainability.

Input / output format

Input: Environment configuration (space type, agent dynamics, number of agents), start/goal states, and maximum allowed time (30s or 100s).

Output: Planned trajectory (collision-free path for each agent), segmented into disjoint time intervals for explainability.

Scoring recipe

def compute_metrics(runs):
    metrics = {'Runtime(s)': [], 'Ave.Cost': [], '# Solns.Found (%)': 0, 'SegmentTime (s)': []}
    for run in runs:
        metrics['Runtime(s)'].append(run.runtime)
        metrics['SegmentTime (s)'].append(run.segment_time)
        if run.success:
            metrics['Ave.Cost'].append(run.cost)
            metrics['# Solns.Found (%)'] += 1
    metrics['# Solns.Found (%)'] = (metrics['# Solns.Found (%)'] / len(runs)) * 100
    return {k: (mean(v), std(v)) for k, v in metrics.items() if isinstance(v, list)}

Common pitfalls

• The time limit varies by environment (30s for Open, 100s for Congested/Corridor/Hallway), which heavily influences success rates and must be explicitly stated when comparing results.
• Runtime(s) measures total wall-clock time, while RuntimeSuccess (s) only averages over successful runs; confusing them leads to incorrect performance assessments.
• The segmentation bound r drastically affects Lazy MAPS-X's pruning frequency and runtime, making direct comparisons with r=∞ or MAPS-RRT misleading without context.

Evidence (verbatim from paper)

The benchmarking results are shown in Table I. TABLE I: Benchmark results with 200 runs. The two character dynamics are $1^{st}$- and $2^{nd}$- order Linear, Unicycle, and Car, respectively. The maximum allowed time was $30s$ for rows 1-4, and $100s$ for rows 5-17. The mean and standard deviation over all planning runs are shown for columns 7-11. | Runtime(s) | RuntimeSuccess (s) | Ave.Cost | SegmentTime (s) | States addedper sec. |

Citation

@misc{kottinger2020mapsx,
  title={MAPS-X: Explainable Multi-Robot Motion Planning via Segmentation},
  author={Kottinger et al. (2020)},
  year={2020},
  note={arXiv:2010.16106}
}

• arXiv: 2010.16106