CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

summary

The gist

Multi-Agent Path Finding (MAPF) algorithms are increasingly used to plan motion for robot teams in industrial warehouses and robotic shared workspaces…

In short

The study investigated whether standard Multi-Agent Path Finding (MAPF) plan metrics, like Sum of Costs (SoC), accurately predict actual robot execution time on physical hardware. By testing 120 plans across different scenarios, the research found that including 'primitive motion burden'—metrics detailing basic movement demands—significantly improved prediction accuracy over SoC alone. This suggests that plan quality needs more than just cost to estimate real-world performance on robots.

Key concepts

Sum of Costs (SoC)
This is a standard, coarse metric used to evaluate MAPF plans, representing the total estimated cost of the path taken by all robots combined. While useful for initial planning, the paper shows SoC alone is insufficient because it ignores physical execution details that cause actual delays in real-world robot movement.
Primitive Motion Burden
This concept measures how much basic, fundamental motion a plan requires from the robots, such as total turns or consecutive moves. The study found this feature provides the strongest predictive power for actual execution time because it captures structural demands that scalar cost metrics miss.
Interaction-Aware Coordination Structure
This layer analyzes how a plan dictates the coordination between different robots, looking at factors like cross-robot precedence count and crowding exposure. This helps predict delays caused by inter-robot conflicts or inefficient shared space usage during execution.

Terminology used across episodes

This episode discusses

The paper

CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs · Read on arXiv

Abhishek Seetharamu, Badrikanath Praharaj, Sreeram M.V., Mohan Prakash V

BuildMachineLabs · IISc, Bengaluru

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.

Transcript

Introduction to the show: ident: Robotics Radio. Generated commentary on the latest robotics and control papers.

Rosa: We're looking at the paper: "CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs".

Dev: Here's the gist of the paper. 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.

Rosa: The study presents CADENCE (Coordination- and Action-Driven Estimation for Networked Continuous Execution), a hardware study of this evaluation gap on a fixed 7 × 7 workcell with seven differentialdrive robots, asking which features available before execution can best predict final wall-clock completion time.

Dev: The core research question and methodology The central research question is: Once an MAPF plan is executed on physical robots, to what extent can the execution time be predicted before deployment.

Rosa: The study examines how much of the observed execution time is evident in the pre-execution plan.

Title and authors: Rosa: So after setting up this hardware study, the paper breaks down what they’re measuring and why it matters. They are comparing four models: just the Sum of Costs, then adding primitive motion burden, and then adding interaction aware coordination structure.

Dev: The core idea is that primitive motion burden captures how much basic movement a plan demands—things like total turn count or consecutive move runs—while interaction aware coordination looks at how much inter-robot coordination load the plan puts on everyone else.

Taro: I’m interested in the scenario families they used, like Empty, Medium Random, and Bottleneck. They say this library spans different interaction regimes rather than just being a broad benchmark suite, which is a specific design choice for their corpus construction.

Rosa: That's right. They built a real hardware execution time corpus using fifteen scenarios across those three families to cover distinct interaction regimes, which they call the Empty Medium Random and Bottleneck scenario families.

Dev: The authors mention that they generated one hundred twenty planned MAPF plans for this study, pulling from different plan generation sources like CBSH2-RTC and others.

Taro: So what’s the actual finding here? Does adding those extra layers of information actually help predict the execution time better than just using the standard Sum of Costs alone?

Rosa: The results show that Sum of Costs alone is informative but it’s incomplete, and primitive motion burden gives the strongest improvement, reducing error by about forty-eight point six to fifty-nine point eight percent in mean absolute error.

Dev: Primitive execution burden produces the largest shared signal beyond the basic Sum of Costs metric when looking at both ridge and mixed effects models.

The paper's summary: Rosa: To summarize what this study shows, it confirms that standard MAPF plan quality metrics are not enough to predict realized execution time on a physical workcell. There is definitely more structure in the offline plan that translates into slower or faster execution than just the scalar cost numbers suggest.

Dev: The paper’s main contribution is proposing a disciplined three-layer decomposition of plan side predictors: first, Sum of Costs, second, primitive motion burden, and third, interaction aware plan structure.

Taro: That layering approach seems smart because it breaks down the complex execution time into analytically distinct parts that we can measure before any robot moves.

Rosa: It’s about separating the coarse plancost trend from the basic motion demands and then looking at the specific inter-robot coordination load a plan creates, like cross-robot precedence count or crowding exposure.

Dev: The methodology involves building a real hardware execution time corpus using an interaction regime stratified library, and then evaluating this four model ladder using scenario level held out validation to see what predicts the realized execution time on that fixed hardware stack.

Taro: It’s interesting how they use that specific combination of scenario families to intentionally create pressure points, like the Bottleneck family concentrating narrow passage dependency pressure.

Rosa: That specific setup helps them span those different interaction regimes—Empty, Medium Random, and Bottleneck—which is key because it shows which plan descriptors are robust across different physical situations.

The paper's improvements: Dev: The paper suggests a few direct improvements for how we evaluate these plans for physical deployment. First, they argue that plan selection systems should prioritize primitive motion burden over just the Sum of Costs using model M2.

Rosa: That means instead of picking the cheapest plan based on cost, you’d pick one that minimizes actual wall-clock time because primitive motion burden gives them the largest and most reliable improvement across both trained analyses.

Taro: And from a systems engineering standpoint, they suggest implementing execution monitoring within the MAPF system to explicitly track and penalize stop go delays during execution.

Dev: That directly addresses what primitive motion burden captures: those cumulative stop and go delays that happen when robots compete for the same space during actual movement, which is a key factor in these real-time loops.

Rosa: Also, they suggest enhancing plan generation interfaces to include interaction aware coordination features like cross-robot precedence count and crowding exposure. This helps evaluate if a plan induces too much inter-robot coordination load before deployment.

Taro: So the suggested improvements are moving from just cost optimization to explicitly optimizing for physical execution reality by incorporating both basic motion demands and coordination structure into the selection process.

Conclusion: Rosa: So, to wrap up on "CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs," the study concludes that standard MAPF plan quality is insufficient for predicting real execution time on a physical multi-robot workcell. Additional plan side structure is definitely needed before any robot moves.

Dev: They emphasize that primitive motion burden provides the clearest additional signal, suggesting much of the execution time gap is already visible in the offline plan before any robot starts moving on this platform.

Taro: I think the main uncertainty they flag is scale transfer, meaning these claims are conditioned on this specific seven robot fleet and workcell, so applying them to larger teams or different hardware requires new evidence.

Rosa: They also mention that interaction aware coordination features carry a directionally consistent additional signal, but its resolution under their held out comparison is limited by the information content of the current corpus.

Dev: So the joint reading from this paper is that primitive motion burden is the supported missing layer between Sum of Costs and realized execution time on this hardware stack.

Taro: It’s a good piece of work for showing us exactly where to look when we try to move from theoretical planning costs to actual physical performance metrics.

Rosa: Right. That’s CADENCE, predicting realized MAPF execution time beyond Sum of Costs, and it leaves us thinking about how we can better score plans using those three layers before execution begins.

More episodes

← Home