CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
Listen
Radio episode about this paper
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.
Abhishek Seetharamu, Badrikanath Praharaj, Sreeram M.V., Mohan Prakash V
BuildMachineLabs · IISc, Bengaluru
cs.RO
Submitted: 2026-06-03
Updated: 2026-11-09
Comments: 7 pages, 4 figures, 3 tables, and This paper was accepted for a poster presentation at Multi-Agent Robotic Systems: Real-World Collaboration and Interaction, a workshop held in conjunction with the 2026 IEEE International Conference on Robotics and Automation (ICRA 2026)
License: http://creativecommons.org/licenses/by-nc-sa/4.0/
Importance score: 83/100
The gist: Multi-Agent Path Finding (MAPF) algorithms are increasingly used to plan motion for robot teams in industrial warehouses and robotic shared workspaces…
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
Summary
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. p. 0 CADENCE: Predicting Realized MAPF Execution Time Beyond Sum
of Costs
Abhishek Seetharamu*
BuildMachineLabs
mail
Badrikanath Praharaj*
BuildMachineLabs
mail
Sreeram M. *
BuildMachineLabs
mail
Mohan Prakash V
IISc, Bengaluru
mail
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. *
BuildMachineLabs
mail
Mohan Prakash V
IISc, Bengaluru
mail
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 × 7 workcell with seven differentialdrive robots, asking which features available before execution
can best predict final wall-clock completion time.Where the paper says it
Where the paper says it
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. The study examines how much of the observed execution time is evident in the pre-execution plan. p. 0 This motivates the central research
question: Once an MAPF plan is executed on physical robots,
to what extent can the execution time be predicted before
deployment? The study examines how much of the observed
execution time is evident in the pre-execution plan. Circles mark starts; squares
mark goals. This question matters because physical execution introduces
structure that scalar plan costs suppress. Figure 1
shows one representative bottleneck execution in which the
realized trajectories reflect these effects. This motivates the
layered view used in this paper: SoC captures a coarse plancost trend, primitive motion burden captures how much basic
motion a plan demands, and interaction-aware coordination
structure captures how much inter-robot coordination load the
plan induces.Where the paper says it
Where the paper says it
Where the paper says it
The corpus construction and feature ladder
A real hardware execution time corpus for offline MAPF plans on a fixed multi-robot platform, built with an interaction-regime-stratified scenario library, was generated. The study utilizes 15 scenarios across three families: Empty, Medium-Random, and Bottleneck to span distinct interaction regimes. p. 5 • Compact scenario support. The 15 scenarios span Empty,
Medium-Random, and Bottleneck regimes, but they do
not constitute a broad benchmark suite. Plan-corpus construction
For each frozen scenario, we instantiate the same eight
plan-generation slots. The fixed menu contains one optimal
reference plan from CBSH2-RTC, four bounded-suboptimal
plans from EECBS at multiple weight settings, and three
seed-varied plans from LaCAM3 [11], [12], [13], [14], [15]. • Model 3 (SoC + primitive motion burden + interactionaware coordination load): further adds four coordination
features that capture how much inter-robot interaction
the plan induces: the number of cross-robot precedence
edges (dependency links where one robot must wait
for another), the number of distinct robot pairs they
connect (how many different robot pairs are involved in
such dependencies), the depth of the longest cross-robot
dependency chain (the length of the longest multi-robot
wait sequence), and a crowding-exposure count (how
much planned motion passes through shared space at the
same logical time). Planner-side makespan is used here as a logical plan-horizon
feature in timesteps rather than as a direct estimate of physical
seconds; the prediction target remains realized wall-clock
execution time.Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The study finds 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. p. 0 Using both a scenario-heldout 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 heldout error by about 48. 8% in MAE and 44. 8% in MAE and 44. 4%
in RMSE relative to SoC-only models. Primitive motion burden recovers the largest shared signal
Primitive execution burden produces the largest shared
improvement beyond SoC. In the ridge model, M2 reduces
MAE from 2. 7626 s and RMSE from 6. In the mixed-effects model, the SoC-only tier remains
close to the null baseline, with MAE 4. In the ridge model, M2 reduces
MAE from 2. 4196 s (down by 1. In the mixed-effects model, the SoC-only tier remains
close to the null baseline, with MAE 4. 7933 s and RMSE
6. Under the mixed-effects model, MAE
drops from 1. 9273 s to 1. 4%
in RMSE relative to SoC-only models. Interaction-aware coordination features add smaller, less uniform gains, most clearly in
the mixed-effects analysis.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion and implications
The study concludes that standard MAPF plan quality is insufficient to predict realized execution time on a physical multi-robot workcell. The clearest additional signal is primitive motion burden, suggesting much of the execution time gap is already visible in the offline plan before any robot starts moving. p. 0 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. The interaction-aware tier improves the point estimates in
both analyses, while the strictest held-out comparison does not
separate it from the primitive-motion tier with intervals away
from zero. The resulting design implication is that executionaware MAPF evaluation should not rely on SoC alone: even
in a compact hardware study, much of the missing executiontime signal is captured by primitive motion descriptors before
any robot moves. In practice, the predicted values
are best used for plan selection, or deployment-side screening
among candidate plans generated for the same platform and
executor, rather than as universal execution-time guarantees. The main uncertainty is scale transfer: all claims here remain
platform-scoped and executor-conditioned, so transfer to larger
fleets or different execution policies requires separate hardware
validation. The next empirical step is therefore to expand
the scenarios. The joint reading is therefore that primitive
motion burden is the supported missing layer between SoC
and realized execution time on this platform; interaction-aware
structure carries a directionally consistent additional signal
whose resolution under the primary held-out comparison is
bounded by the information content of the present corpus. The next empirical step is therefore to expand
the scenarios. The joint reading is therefore that primitive
motion burden is the supported missing layer between SoC
and realized execution time on this platform; interaction-aware
structure carries a directionally consistent additional signal
whose resolution under the primary held-out comparison is
bounded by the information content of the present corpus.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
REFERENCES
2606.047461pg1 CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs Abhishek Seetharamu BuildMachineLabs mail Badrikanath Praharaj BuildMachineLabs mail Sreeram M. p. 0 CADENCE: Predicting Realized MAPF Execution Time Beyond Sum
of Costs
Abhishek Seetharamu*
BuildMachineLabs
mail
Badrikanath Praharaj*
BuildMachineLabs
mail
Sreeram M. *
BuildMachineLabs
mail
Mohan Prakash V
IISc, Bengaluru
mail
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.Where the paper says it
2606.047462pg3 A. Fixed 7x7 hardware workcell Hardware scope for the plan corpus All generated MAPF plans are executed on the same physical arena and sevenrobot fleet
2606.047463pg3 B. Scenario families Empty Medium-random Bottleneck This paper makes three contributions: • A real hardware execution time corpus for offline MAPF plans on a fixed multi-robot platform, built with an interaction-regime-stratified scenario library. p. 1 Hardware platform and scenario-family overview. This paper makes three contributions:
• A real hardware execution time corpus for offline MAPF
plans on a fixed multi-robot platform, built with an
interaction-regime-stratified scenario library. This paper makes three contributions:
• A real hardware execution time corpus for offline MAPF
plans on a fixed multi-robot platform, built with an
interaction-regime-stratified scenario library. • A disciplined three-layer decomposition of plan-side predictors of realized execution time.Where the paper says it
Where the paper says it
2606.047464pg4 C. Plan-corpus construction For each frozen scenario, we instantiate the same eight plan-generation slots. p. 2 Element Value
Platform Seven differential-drive robots on a 7 × 7
physical workcell
Scenario library 15 scenarios: 5 Empty, 5 Medium-Random,
5 Bottleneck
Plan-generation menu 1 CBSH2-RTC; 4 EECBS weights; 3
LaCAM seeds per scenario
Corpus construction Seeded scenario freeze; fixed menu for
every scenario
Plans per scenario 8 planned MAPF solutions
Plan corpus 120 planned MAPF plans
Hardware corpus 480 scheduled executions; four per plan
Hardware repetitions 4 scheduled executions per plan
Evaluation target Plan-level mean execution time
Execution monitor Precedence-faithful continuous executor
Measured target Total execution wall-clock time
Held-out evaluation Scenario-level family-balanced 5-fold split
Estimators Ridge plan-mean ladder and trial-level
mixed-effects ladder
Metrics Held-out MAE and RMSE in seconds
C. Plan-corpus construction
For each frozen scenario, we instantiate the same eight
plan-generation slots.Where the paper says it
2606.047465pg5 TABLE II HELD-OUT MODEL-LADDER ERRORS FOR THE RIDGE AND MIXED-EFFECTS MODELS ON THE HARDWARE CORPUS. p. 4 TABLE II
HELD-OUT MODEL-LADDER ERRORS FOR THE RIDGE AND MIXED-EFFECTS MODELS ON THE HARDWARE CORPUS. BOTH PANELS USE THE SAME M0–M3
FEATURE LADDER. TABLE II
HELD-OUT MODEL-LADDER ERRORS FOR THE RIDGE AND MIXED-EFFECTS MODELS ON THE HARDWARE CORPUS. BOTH PANELS USE THE SAME M0–M3
FEATURE LADDER.Where the paper says it
Where the paper says it
2606.047467pg1 VII CONCLUSION This study concludes that standard MAPF plan quality is insufficient to predict realized execution time on a physical multi-robot workcell and additional plan-side structure is needed before execution
2606.047468pg1 VI DISCUSSION AND LIMITATIONS How can these predictions be used in deployment, and what remains uncertain? p. 5 The joint reading is therefore that primitive
motion burden is the supported missing layer between SoC
and realized execution time on this platform; interaction-aware
structure carries a directionally consistent additional signal
whose resolution under the primary held-out comparison is
bounded by the information content of the present corpus. DISCUSSION AND LIMITATIONS
How can these predictions be used in deployment, and
what remains uncertain?Where the paper says it
2606.047468pg1 VI DISCUSSION AND LIMITATIONS Limitations. p. 5 The joint reading is therefore that primitive
motion burden is the supported missing layer between SoC
and realized execution time on this platform; interaction-aware
structure carries a directionally consistent additional signal
whose resolution under the primary held-out comparison is
bounded by the information content of the present corpus. DISCUSSION AND LIMITATIONS
How can these predictions be used in deployment, and
what remains uncertain? Limitations. • Controlled hardware scope.Where the paper says it
Where the paper says it
2606.047468pg1 VI DISCUSSION AND LIMITATIONS Compact scenario support. p. 5 The findings are conditioned
on seven robots, a 7×7 arena, and one precedence-faithful
continuous executor, so transfer to larger fleets or different execution stacks requires new hardware evidence. • Compact scenario support.Where the paper says it
2606.047468pg1 VI DISCUSSION AND LIMITATIONS Declared corpus design. p. 5 The joint reading is therefore that primitive
motion burden is the supported missing layer between SoC
and realized execution time on this platform; interaction-aware
structure carries a directionally consistent additional signal
whose resolution under the primary held-out comparison is
bounded by the information content of the present corpus. DISCUSSION AND LIMITATIONS
How can these predictions be used in deployment, and
what remains uncertain?Where the paper says it
2606.047468pg1 VII CONCLUSION ACKNOWLEDGMENT The authors thank Prof. p. 5 The ridge
and mixed-effects ladders are designed as disciplined,
interpretable tests of feature families, not as upper bounds
on predictive performance. ACKNOWLEDGMENT
The authors thank Prof.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Develop plan selection systems that prioritize primitive motion burden over Sum of Costs for physical deployment by using model M2, which
gives the largest and most reliable improvement across both trained analyses.
This allows systems to choose plans that minimize real wall-clock time rather than just nominal cost. -
Implement execution monitoring within the MAPF system to explicitly track and penalize
stop–go delays during execution,
as this is a key factor captured by primitive motion burden. This enables the AI to select or modify plans that are inherently less prone to these physical delays, as shown in Figure 3's executor dependency-wait diagnostic. -
Enhance plan generation interfaces to incorporate interaction-aware coordination features like
cross-robot precedence count
andcrowding exposure.
These metrics allow the system to evaluate whether a plan induces too much inter-robot coordination load or passes through shared spaces inefficiently, leading to better planning choices before execution begins. -
Create a hierarchical evaluation framework for MAPF plans that decomposes performance into three distinct layers: Sum of Costs (SoC), primitive motion burden, and interaction-aware coordination structure. This provides a disciplined way to assess plan quality beyond the standard "Sum of Costs (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 interactionaware coordination structure."
-
Utilize scenario-heldout validation to train predictive models for execution time. This ensures that the AI does not overfit to specific obstacle layouts but learns general rules about which plan descriptors
best predict the realized execution time on this fixed hardware stack.
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.
Sources
Related papers
- Rethinking Actions: Continuity-Aware Priors for World-Model Planning
- MOSAIC: Modular Obstacle and Spatial-Aware Framework for Manipulation In Cluttered Scenes
- SAGAS: Semantic-Aware Graph-Assisted Stitching for Offline Temporal Logic Planning
- DexSeed: Expanding Human Hand-Object Interactions into Robot Demonstrations for Dexterous Policy Learning
- LaST0.5: A Generalist World Action Model with Interaction-Centric Latent Reasoning
- CIALLO: Learning Shared Intent Representations for Cross-Embodiment Manipulation