CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
2026-06-03 • Robotics
Robotics
AI summaryⓘ
The authors studied how well common measures used to plan robot movements in a warehouse predict actual time taken to finish tasks. They tested different planning features on seven robots in a fixed workspace and found that just looking at total planned travel (SoC) isn't enough. Instead, measures of basic motions needed, like turns and stops, better predict completion time before execution. Coordination features between robots helped a little but were less consistent. This means much about real-world timing can be understood from the plan itself, without running the robots first.
Multi-Agent Path Finding (MAPF)Sum of Costs (SoC)makespandifferential drive robotsprimitive motion burdenrobot coordinationexecution time predictionmixed-effects modelrobot motion planning
Authors
Abhishek S, Badrikanath Praharaj, Sreeram MV
Abstract
Multi-Agent Path Finding (MAPF) algorithms are increasingly used to plan motion for robot teams in industrial warehouses and robotic shared workspaces, but standard MAPF algorithm evaluation metrics, such as Sum of Costs (SoC), makespan, and planner runtime, can obscure how planner choices translate into realistic execution performance. We present CADENCE (Coordination 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 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 scenario-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 models and uncertainty checks, primitive motion burden is the most reliable additional signal beyond SoC, suggesting that much of the execution time gap is already visible in the offline plan before any robot starts moving.