CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
This research paper introduces CADENCE, a method to predict the actual execution time of Multi-Agent Path Finding (MAPF) plans for robot teams. The authors address the limitation of standard metrics like Sum of Costs (SoC) which often fail to capture realistic performance. Using a hardware study with seven differential drive robots in a 7x7 workcell, they analyzed 480 trials across various scenarios. The study finds that while SoC is informative, incorporating 'primitive motion burden' (such as makespan, turns, and start-stop transitions) provides the strongest improvement, reducing prediction error by approximately 48.6% to 59.8% in Mean Absolute Error compared to SoC-only models. Interaction-aware coordination features offer smaller gains. The results suggest that much of the execution time gap is visible in the offline plan before robots begin moving.
This study validates that primitive motion burden features significantly reduce prediction error for Multi-Agent Path Finding execution times compared to standard Sum of Costs metrics, based on a hardware corpus of 480 trials across seven differential drive robots in a fixed workcell.
Source: arXiv Robotics — research abstracts · Read original article ↗
Loading article text…
What the source reports
Publisher-reported claims, with original evidence. These results have not been independently verified by RoboSignal.
Reported numbers
plans
120
Reported trials
View original evidence
moves, and start-stop transitions), and interaction aware coordination structure (how much inter-robot coordination the plan induces, such as dependency links, interacting robot pairs, dependency depth, and crowding exposure). To test this, we generate 120 plans across 15 scenarios -- 5 Empty, 5 Medium Random, and 5 Bottleneck and execute each plan four times, yielding a 480 trial hardware corpus. Using both a scena
Open source S4trials
480 trials
Reported trials
View original evidence
moves, and start-stop transitions), and interaction aware coordination structure (how much inter-robot coordination the plan induces, such as dependency links, interacting robot pairs, dependency depth, and crowding exposure). To test this, we generate 120 plans across 15 scenarios -- 5 Empty, 5 Medium Random, and 5 Bottleneck and execute each plan four times, yielding a 480 trial hardware corpus. Using both a scena
Open source S4workcell dimensions
7
View original evidence
ion and Action-Driven Estimation for Networked Continuous Execution), a hardware study of this evaluation gap on a fixed 7 by 7 workcell with seven differential drive robots, asking which features available before execution can best predict final wall-clock completion time. We compare SoC, total planned travel cost, primitive motion burden (how much basic motion the plan requires, such as makespan, turns, consecutive
Open source S3
- paper: not_reported
Source excerpts and review record
Automatically extracted; no manual editorial approval recorded.
ion and Action-Driven Estimation for Networked Continuous Execution), a hardware study of this evaluation gap on a fixed 7 by 7 workcell with seven differential drive robots, asking which features available before execution can best predict final wall-clock completion time. We compare SoC, total planned travel cost, primitive motion burden (how much basic motion the plan requires, such as makespan, turns, consecutive
Open source S3
moves, and start-stop transitions), and interaction aware coordination structure (how much inter-robot coordination the plan induces, such as dependency links, interacting robot pairs, dependency depth, and crowding exposure). To test this, we generate 120 plans across 15 scenarios -- 5 Empty, 5 Medium Random, and 5 Bottleneck and execute each plan four times, yielding a 480 trial hardware corpus. Using both a scena
Open source S4
rio-held -- out ridge model and a trial-level mixed-effects model, we find that SoC alone is informative but incomplete, while primitive motion burden gives the strongest improvement, reducing held out error by about 48.6%-59.8% in MAE and 44.2%-61.4% in RMSE relative to SoC-only models. Interaction-aware coordination features add smaller, less uniform gains, most clearly in the mixed-effects analysis. Across both mo
Open source S5
Source：arXiv Robotics — research abstracts · arxiv.org