CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

arXiv:2606.04746 · cs.RO · Submitted 2026-06-03 · Read on arXiv

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

Where the paper says it

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.

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. p. 0
Where the paper says it

* 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.

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

Where the paper says it

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.

This is motivated by the fact that physical execution introduces structure that scalar plan costs suppress. p. 0
Where the paper says it

Circles mark starts; squares mark goals. This question matters because physical execution introduces structure that scalar plan costs suppress.

The research uses a layered view where 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. p. 0
Where the paper says it

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.

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

Where the paper says it

• Compact scenario support. The 15 scenarios span Empty, Medium-Random, and Bottleneck regimes, but they do not constitute a broad benchmark suite.

The plan corpus consists of 120 planned MAPF plans generated using a fixed menu containing one optimal reference plan from CBSH2-RTC, four bounded-suboptimal plans from EECBS, and three seed-varied plans from LaCAM3. p. 2
Where the paper says it

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].

The feature ladder evaluates four levels: Model 1 (SoC only), Model 2 (SoC + primitive motion burden), and Model 3 (SoC + primitive motion burden + interaction-aware coordination load). p. 3
Where the paper says it

• 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 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

Where the paper says it

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.

2%–61.4% in RMSE relative to SoC-only models. p. 0
Where the paper says it

8% in MAE and 44. 4% in RMSE relative to SoC-only models.

Primitive execution burden produces the largest shared signal beyond SoC, with M2 reducing MAE from 2. p. 4
Where the paper says it

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 to 1. p. 5
Where the paper says it

7626 s and RMSE from 6. In the mixed-effects model, the SoC-only tier remains close to the null baseline, with MAE 4.

4196 s in the ridge model and from 4. p. 4
Where the paper says it

In the ridge model, M2 reduces MAE from 2. 4196 s (down by 1.

7933 s to 1. p. 5
Where the paper says it

In the mixed-effects model, the SoC-only tier remains close to the null baseline, with MAE 4. 7933 s and RMSE 6.

9273 s in the mixed-effects model. p. 5
Where the paper says it

Under the mixed-effects model, MAE drops from 1. 9273 s to 1.

Interaction-aware coordination features add smaller, less uniform gains, most clearly in the mixed-effects analysis. p. 0
Where the paper says it

4% in RMSE relative to SoC-only models. Interaction-aware coordination features add smaller, less uniform gains, most clearly in the mixed-effects analysis.

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

Where the paper says it

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.

Therefore, execution-aware MAPF evaluation should not rely on SoC alone. p. 6
Where the paper says it

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.

The main uncertainty is scale transfer, as all claims remain platform-scoped and executor-conditioned. p. 5
Where the paper says it

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 joint reading is that primitive motion burden is the supported missing layer between SoC and realized execution time on this platform. p. 5
Where the paper says it

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 interaction-aware tier carries a directionally consistent additional signal whose resolution under the primary held-out comparison is bounded by the information content of the present corpus. p. 5
Where the paper says it

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.

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

Where the paper says it

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.

V. BuildMachineLabs mail Mohan Prakash V IISc, Bengaluru mail

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

Where the paper says it

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.

• A disciplined three-layer decomposition of plan-side predictors of realized execution time. p. 1
Where the paper says it

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.

We separate plan descriptors into three analytically distinct layers: (i) SoC, the standard MAPF plan quality scalar; (ii) primitive motion burden total turn count, consecutive-move runs, and start–stop transitions; and (iii) interaction-aware plan structure cross-robot precedence count, precedence depth, and crowding exposure

2606.047464pg4 C. Plan-corpus construction For each frozen scenario, we instantiate the same eight plan-generation slots. p. 2

Where the paper says it

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.

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

2606.047465pg5 TABLE II HELD-OUT MODEL-LADDER ERRORS FOR THE RIDGE AND MIXED-EFFECTS MODELS ON THE HARDWARE CORPUS. p. 4

Where the paper says it

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.

BOTH PANELS USE THE SAME M0–M3 FEATURE LADDER. p. 4
Where the paper says it

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.

DELTA COLUMNS ARE RELATIVE TO THE PREVIOUS MODEL TIER; NEGATIVE VALUES INDICATE BETTER PREDICTION

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

Where the paper says it

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?

Because these descriptors are computable from the offline plan before any robot moves, they can be used to score or compare candidate plans using a quantity that is closer to realized execution time than SoC alone on this hardware stack

2606.047468pg1 VI DISCUSSION AND LIMITATIONS Limitations. p. 5

Where the paper says it

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?

• Controlled hardware scope. p. 5
Where the paper says it

Limitations. • Controlled hardware scope.

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

2606.047468pg1 VI DISCUSSION AND LIMITATIONS Compact scenario support. p. 5

Where the paper says it

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.

The 15 scenarios span Empty, Medium-Random, and Bottleneck regimes, but they do not constitute a broad benchmark suite

2606.047468pg1 VI DISCUSSION AND LIMITATIONS Declared corpus design. p. 5

Where the paper says it

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?

The fixed eight-slot plangeneration menu makes the corpus auditable and repeatable, but not representative of all MAPF tasks, solvers, or deployment settings

2606.047468pg1 VII CONCLUSION ACKNOWLEDGMENT The authors thank Prof. p. 5

Where the paper says it

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.

Pavankumar Tallapragada, Associate Professor at the Robert Bosch Centre for Cyber-Physical Systems (RBCCPS), Indian Institute of Science (IISc), Bengaluru, for his guidance and the resources that made this work possible

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

  1. 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.

  2. 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.

  3. Enhance plan generation interfaces to incorporate interaction-aware coordination features like cross-robot precedence count and crowding 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.

  4. 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."

  5. 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