CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

Abhishek Seetharamu; Badrikanath Praharaj; Sreeram MV

REVIEW 3 major objections 3 minor 15 references

CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

T0 review · 3 major / 3 minor · reviewed 2026-08-02 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read On a fixed seven-robot workcell, multi-agent pathfinding plans' realized wall-clock completion time is largely predictable before execution — and the standard Sum of Costs metric is too coarse to do it alone.

desk verdict A careful hardware study showing SoC is not enough and primitive motion burden is the best offline signal, but 15 scenarios is thin for the strongest generalization claims. read the letter →

arxiv 2606.04746 v3 pith:FI4O2Z7I submitted 2026-06-03 cs.RO

Abhishek Seetharamu , Badrikanath Praharaj , Sreeram MV This is my paper · ORCID

classification cs.RO

keywords multi-agentpathfindingexecutiontimepredictionsumofcostsprimitivemotionburdenhardwareevaluationactiondependencygraphplanqualitymetricsscenario-held-outvalidation

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper sets out to show that on a fixed seven-robot workcell, the wall-clock time a MAPF plan actually takes to execute can be predicted largely before any robot moves — and that the standard Sum of Costs metric is too coarse to do it. The authors build a 480-trial hardware corpus by running 120 plans across 15 scenarios on seven differential-drive robots, then test a ladder of plan-side feature sets under scenario-held-out validation. Their central result is that adding 'primitive motion burden' — planner-side makespan, turns, consecutive moves, and start–stop transitions — to SoC cuts held-out absolute error by roughly half, while interaction-aware coordination features add only a smaller, not fully resolved, further gain. A sympathetic reader would care because the finding suggests execution-aware plan selection can be done cheaply, from offline features, rather than only after expensive hardware trials.

What carries the argument

The Action Dependency Graph (ADG) — a graph whose nodes are per-robot stages and whose inter-robot edges record where one robot must wait for another — is the central object that carries the argument. It is compiled from each plan before execution and yields the interaction-aware features (dependency count, pairs, depth), while the primitive-motion features are read directly from the raw path sequences; together they form the four-model feature ladder tested under scenario-held-out validation with ridge and mixed-effects estimators.

What would settle it

Run the same feature ladder on a fresh set of, say, 30 scenarios drawn from a different layout distribution on the same hardware; if adding primitive-motion features to SoC no longer cuts held-out MAE by roughly half, the central claim fails.

Watch

Extended reading notes

Core claim

The central discovery is that most of the gap between planned and realized execution time is already visible in the offline plan: augmenting Sum of Costs with four primitive-motion features reduces held-out mean absolute error from 2.76 s to 1.42 s in the ridge model and from 4.79 s to 1.93 s in the mixed-effects model, roughly a 49–60% improvement. The additional interaction-aware coordination tier — dependency edges, pairs, depth, and crowding — moves both estimators in the same direction, but the strictest scenario-held-out comparison does not separate it from the primitive-motion tier with confidence intervals away from zero. The authors' own reading is that primitive motion burden is th

Load-bearing premise

The load-bearing premise is that the 15 hand-constructed scenarios — five each of Empty, Medium-Random, and Bottleneck — are representative enough that scenario-held-out error estimates the feature ranking's generalization; if actual deployment layouts differ, the ranking may not transfer.

Editorial extensions

If this is right

Plan-selection and deployment-side screening can use primitive-motion features computed before any robot moves, rather than relying on SoC alone.
MAPF benchmark evaluation could report motion-burden descriptors alongside SoC and makespan, since they capture execution-relevant structure that scalar cost suppresses.
On this hardware, interaction-aware coordination features are directionally consistent but not yet sized; a larger scenario corpus would be needed to certify their contribution.
Because much of the execution-time gap is visible offline, hardware-in-the-loop evaluation is not required for the first-order improvement; it becomes a refinement layer.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

An obvious next test is to hold Sum of Costs fixed across plans that vary in turns, stops, or consecutive moves; if wall-clock time tracks the motion-burden features while SoC is constant, the causal role of primitive burden is confirmed.
The same features could be folded into planner objectives, creating bounded-suboptimal search that explicitly trades SoC against predicted wall-clock time — the paper shows enough signal exists to make that trade meaningful.
On larger fleets or sparser arenas, interaction-aware coordination structure may matter more than it did here; the 7×7 arena is dense and small, so scaling to warehouses could shift the ranking.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

The short version: this is a careful, honestly-scoped hardware study that confirms SoC is incomplete and identifies primitive motion burden as the strongest offline-visible signal on this platform. The main weakness is the evidence base: 15 scenarios is thin for the 'most reliable' wording, and there is no code or data.

What is actually new: the 480-run hardware corpus on a 7×7 workcell with seven differential-drive robots, the explicit three-tier decomposition (SoC / primitive motion burden / interaction-aware ADG structure), and the scenario-level family-balanced held-out protocol. The validation is done properly: scenario-level splits, bootstrap and paired-t intervals on stepwise comparisons, and a disciplined M0–M3 ladder. The M2-vs-M1 improvement is large (held-out MAE roughly halved in both the ridge and mixed-effects models) and the intervals exclude zero. The paper is also honest about the interaction tier: the ridge interval crosses zero, the mixed-effects bootstrap is below zero but the t-interval is not, and they say the effect size is not settled. That is the right amount of caution.

Where the soft spots are. First, the 15-scenario library with five per family means each outer fold holds out only three scenarios. The pooled deltas could be driven by one family—for instance, Bottleneck scenarios have longer times and more start–stop transitions—and the paper does not report family-stratified deltas or leave-one-scenario-out sensitivity. So 'most reliable additional signal' is a bit strong; 'most reliable within this 15-scenario sample' is what the data show. Second, the interaction-aware features are read off the same Action Dependency Graph that the executor uses to gate releases. That is not circular for the regression target, which is hardware wall-clock time, but it does make the interaction-tier result executor-conditioned in a fairly direct way. The paper acknowledges this, but the framing could be clearer that a different executor could easily change the relative value of the ADG features. Third, no code or data is released, which will slow reproduction by other labs—although the protocol is described in enough detail to rebuild something close.

Overall: the central claim—SoC alone is insufficient and primitive motion burden adds the largest held-out gain—holds up on this platform. The paper deserves peer review. A good referee should push for family-stratified sensitivity analysis, LOSO checks, and a sharper statement of the executor-conditioned scope. I'd cite it as a useful hardware data point and bring it to a reading group.

Referee Report

3 major / 3 minor

Summary. The paper presents CADENCE, a fixed-platform hardware study (7×7 arena, seven differential-drive robots, precedence-faithful continuous executor) of how well pre-execution MAPF plan descriptors predict realized wall-clock completion time. A 15-scenario library (5 Empty, 5 Medium-Random, 5 Bottleneck) with an eight-slot planner menu produces 120 plans, each executed four times (480 trials). The authors compare a four-tier feature ladder: null, SoC, SoC + primitive motion burden (planner-side makespan, turns, consecutive moves, start–stop transitions), and the latter plus interaction-aware ADG-derived structure. Using scenario-level family-balanced 5-fold splits, ridge and mixed-effects models, they report that adding primitive motion burden to SoC cuts held-out MAE from 2.76 to 1.42 s (ridge) and 4.79 to 1.93 s (mixed-effects), with bootstrap and paired-t intervals excluding zero, while M3 adds smaller, less uniform gains. The central claim is that primitive motion burden is the most reliable additional signal beyond SoC.

Significance. If the conclusions hold, the work provides a useful, platform-scoped finding for MAPF evaluation: standard SoC is insufficient, and simple motion-burden descriptors recover a large share of the missing execution-time signal before deployment. The study is carefully designed in several respects: scenario-level held-out splits prevent plan leakage; family balance in folds preserves regime coverage; plan means rather than individual trials are the confirmatory unit; both bootstrap and paired-scenario t intervals are reported; and executor-conditioning is stated explicitly. The authors are also appropriately cautious about the interaction-aware tier. The main limitation is not internal inconsistency but the narrow evidence base for cross-scenario generalization; this limits the strength of the 'most reliable' wording.

major comments (3)

[§V, Table III; §VI] The central claim that primitive motion burden is the 'most reliable' signal rests on pooled M2-vs-M1 deltas over 15 scenarios. With only 5 scenarios per family and family-balanced folds holding out one scenario per family, the pooled bootstrap and t intervals could be significant even if the improvement is absent or reversed in one or two families. Report family-stratified held-out deltas (or leave-one-scenario-out results) for M2 vs M1, or restrict the claim to the exact 15-scenario mixture. This is needed before the cross-regime wording in the abstract and conclusion is supported.
[§IV.D] The mixed-effects model is underspecified. The text says it is fit at the trial level and evaluated on held-out plan means, but gives no fixed-effect structure, random-effect structure, or estimation method. Without this, the large mixed-effects M2-vs-M1 delta and the M2→M3 bootstrap intervals in Table III cannot be audited. In particular, M1 (SoC only) is close to M0 in the mixed-effects panel but not in the ridge panel; a specification detail (e.g., scenario random intercepts) may explain this, but the reader cannot tell. Provide the model equation and fitting details.
[§IV.C vs §V.C] The definition of M2 is inconsistent. Section IV.C defines M2 as SoC plus planner-side makespan, total turn count, consecutive-move count, and start–stop transition count. Section V.C describes M2 as adding per-plan turn count, start–stop count, and 'total commanded path length' on top of SoC, omitting makespan and consecutive-move count. If 'total commanded path length' is essentially SoC, the description is redundant; if not, the feature set used for the main result is unclear. Correct the inconsistency and report the exact M2 feature list.

minor comments (3)

[Abstract] 'Reducing held-out error by about 48.6%–59.8% in MAE and 44.2%–61.4% in RMSE' should state that these are relative reductions from M1 to M2 within each model, not a single universal range.
[§IV.D] 'Between-plan variance accounts for 99.4% of total execution-time variance' — clarify how this was computed (e.g., random-effects ANOVA on plan means vs. repeats).
[References] References [14] and [15] duplicate the same work; [15] is an arXiv version. Cite once.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the prediction target is measured hardware time and all predictors are offline plan descriptors.

full rationale

The paper's derivation chain is self-contained and not circular. The target is "realized total execution wall-clock time, measured per trial from the hardware logs," which is independent of the model and of the plan-side features. All predictors are "computed before hardware execution from the MAPF plan alone; no hardware timing outcome enters the extraction pipeline." The held-out evaluation is scenario-level family-balanced, so the regression coefficients are not fit to the evaluated plans. The primitive-motion and interaction-aware features are not renamed versions of the target: they are logical plan properties (makespan in timesteps, turn counts, ADG edge counts) that are causally related to, but not identical to, wall-clock seconds. The interaction-aware features are read from the same ADG that the executor consumes, but this is a mechanistic link, not a definitional equivalence; the paper does not define execution time as an ADG function, and it explicitly reports the interaction-aware tier as directionally consistent but not settled under the strictest held-out comparison. No load-bearing self-citations or imported uniqueness claims are present. The acknowledged limitations (compact scenario support, controlled hardware scope) are statistical-external-validity caveats, not circularity.

Assumptions & free parameters 3 free parameters · 4 assumptions · 0 invented entities

No new physical entities are postulated. 'Primitive motion burden', 'interaction-aware coordination structure', and 'crowding exposure' are operationalized plan features, not invented theoretical objects; the Action Dependency Graph is adopted from prior work [2].

free parameters (3)

Ridge and mixed-effects feature coefficients = estimated from training folds; numeric values not reported
All tier comparisons are measured through these fitted weights; they are the fitted parameters of the prediction models.
Ridge penalty lambda = per fold, chosen by inner scenario-grouped cross-validation
Regularization strength is selected from training data; standard practice but data-dependent.
Mixed-effects variance components = estimated during model fitting
Random-effect variances are fitted to repeated-trial data and affect held-out predictions.

assumptions (4)

ad hoc to paper The 15-scenario library is an adequate sample of interaction regimes (Empty/Medium/Bottleneck) for generalization claims.
Scenarios are hand-picked, not randomly sampled from a defined population; the reliability claims assume this sample represents future deployments.
domain assumption The precedence-faithful continuous executor faithfully implements the ADG's dependency order and does not introduce scheduling artifacts that dominate wall-clock times.
If the executor imposed different waits, the measured times and the predictive value of coordination features would change; the paper notes all claims are executor-conditioned.
domain assumption Generated plans (CBSH2-RTC, EECBS, LaCAM3) are feasible under the hardware execution model.
Scenario admission uses a feasibility oracle before hardware runs; hardware feasibility and absence of execution failures are assumed throughout.
standard math Standard linear-model assumptions for ridge and mixed-effects regressions: linearity, homoscedastic errors, scenario-block independence.
The reported bootstrap and t-intervals rely on these assumptions.

how reviews work

0 comments

Cite this review

Pith. "Pith review of CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs." pith.science (2026). https://pith.science/paper/FI4O2Z7I

@misc{pith2026260604746,
  author       = {Pith},
  title        = {Pith review of: CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/FI4O2Z7I}},
  note         = {Machine review of arXiv:2606.04746}
}

read the original 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.

Figures

Figures reproduced from arXiv: 2606.04746 by the authors.

**Figure 1.** Hardware OptiTrack trace. Color-coded trajectories for Robots 1–7 on a representative 7 × 7 bottleneck execution. Circles mark starts; squares mark goals. This question matters because physical execution introduces structure that scalar plan costs suppress. Robots must preserve the same-agent action order, satisfy cross-robot precedence constraints, pass through locally contested spaces, and often incur stop–go dela… view at source ↗

**Figure 2.** 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. We separate plan descriptors into three analytically distinct layers: (i) SoC, t… view at source ↗

**Figure 3.** Executor dependency-wait diagnostic. In one representative hardware trial, dependency-gated waiting accounts for a visible share of several robots’ wall-clock finish times. This illustrates the execution mechanism rather than a corpus-level result. B. Pre-execution feature extraction All predictors are computed before hardware execution from the MAPF plan alone; no hardware timing outcome enters the extraction pipe… view at source ↗

Figures from the paper (1 more)

**Figure 4.** Figure 4: SoC-only model. Each point is a plan mean; the dashed line is the SoC-only model. The vertical spread shows why SoC alone is not a complete predictor of hardware time. In the ridge model, SoC reduces held-out MAE from [PITH_FULL_IMAGE:figures/full_fig_p005_4.png]

Review history (2 revisions) →

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 1 linked inside Pith

[1]

Multi-agent path finding with delay probabilities,

H. Ma, T. K. S. Kumar, and S. Koenig, “Multi-agent path finding with delay probabilities,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017

2017
[2]

Persistent and robust execution of mapf schedules in warehouses,

W. H ¨onig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Persistent and robust execution of mapf schedules in warehouses,”IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1125–1131, 2019

2019
[3]

Bidirectional temporal plan graph: Enabling switchable passing orders for more efficient multi-agent path finding plan execution,

Y . Su, R. Veerapaneni, and J. Li, “Bidirectional temporal plan graph: Enabling switchable passing orders for more efficient multi-agent path finding plan execution,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 16, 2024, pp. 17 559–17 566

2024
[4]

Multi-agent pathfinding: Definitions, variants, and benchmarks,

R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Bartak, and E. Boyarski, “Multi-agent pathfinding: Definitions, variants, and benchmarks,” in Proceedings of the Annual Symposium on Combinatorial Search, 2019

2019
[5]

Conflict-based search for optimal multi-agent pathfinding,

G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,”Artificial Intelligence, vol. 219, pp. 40–66, 2015

2015
[6]

Coordinating hundreds of cooperative, autonomous vehicles in warehouses,

P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,”AI Magazine, vol. 29, no. 1, pp. 9–20, 2008

2008
[7]

Analyzing planner design trade-offs for mapf under adg-based realistic execution,

J. Yan, Z. Li, W. Kang, S. F. Smith, and J. Li, “Analyzing planner design trade-offs for mapf under adg-based realistic execution,” 2025

2025
[8]

Which mapf model works best for automated warehousing?

S. Varambally, J. Li, and S. Koenig, “Which mapf model works best for automated warehousing?”Proceedings of the International Symposium on Combinatorial Search, vol. 15, no. 1, pp. 190–198, 2022

2022

Show all 15 references

[9]

Traffic flow optimisation for lifelong multi-agent path finding,

Z. Chen, D. Harabor, J. Li, and P. J. Stuckey, “Traffic flow optimisation for lifelong multi-agent path finding,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 18, 2024, pp. 20 674– 20 682

2024
[10]

P3gasus: Pre-planned path execution graphs for multi-agent systems at ultra-large scale,

T. Duhan, C. He, and G. Sartoretti, “P3gasus: Pre-planned path execution graphs for multi-agent systems at ultra-large scale,”IEEE Robotics and Automation Letters, vol. 11, no. 2, pp. 1274–1281, 2026

2026
[11]

Improved heuristics for multi-agent path finding with conflict-based search,

J. Li, A. Felner, E. Boyarski, H. Ma, and S. Koenig, “Improved heuristics for multi-agent path finding with conflict-based search,” in Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence, 2019, pp. 442–449

2019
[12]

Eecbs: A bounded-suboptimal search for multi-agent path finding,

J. Li, W. Ruml, and S. Koenig, “Eecbs: A bounded-suboptimal search for multi-agent path finding,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 35, no. 14, 2021, pp. 12 353–12 362

2021
[13]

Lacam: Search- based algorithm for quick multi-agent pathfinding,

K. Okumura, M. Machida, X. Defago, and Y . Tamura, “Lacam: Search- based algorithm for quick multi-agent pathfinding,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 37, no. 10, 2023, pp. 11 655–11 662

2023
[14]

Engineering lacam*: Towards real-time, large-scale, and near-optimal multi-agent pathfinding,

K. Okumura, R. Kuroiwa, and Y . Tamura, “Engineering lacam*: Towards real-time, large-scale, and near-optimal multi-agent pathfinding,” inIn- ternational Conference on Autonomous Agents and Multiagent Systems, 2024

2024
[15]

Engineering LaCAM: Towards real-time, large-scale, and near-optimal multi-agent pathfinding,

K. Okumura, “Engineering LaCAM: Towards real-time, large-scale, and near-optimal multi-agent pathfinding,” 2024, presented at AAMAS-24. [Online]. Available: https://arxiv.org/abs/2308.04292

2024 arXiv

Pith tools

Reviewed August 2, 2026 · model on record in the stance chip above.

[1] [1]

Multi-agent path finding with delay probabilities,

H. Ma, T. K. S. Kumar, and S. Koenig, “Multi-agent path finding with delay probabilities,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 31, no. 1, 2017

2017

[2] [2]

Persistent and robust execution of mapf schedules in warehouses,

W. H ¨onig, S. Kiesel, A. Tinka, J. W. Durham, and N. Ayanian, “Persistent and robust execution of mapf schedules in warehouses,”IEEE Robotics and Automation Letters, vol. 4, no. 2, pp. 1125–1131, 2019

2019

[3] [3]

Bidirectional temporal plan graph: Enabling switchable passing orders for more efficient multi-agent path finding plan execution,

Y . Su, R. Veerapaneni, and J. Li, “Bidirectional temporal plan graph: Enabling switchable passing orders for more efficient multi-agent path finding plan execution,” inProceedings of the AAAI Conference on Artificial Intelligence, vol. 38, no. 16, 2024, pp. 17 559–17 566

2024

[4] [4]

Multi-agent pathfinding: Definitions, variants, and benchmarks,

R. Stern, N. Sturtevant, A. Felner, S. Koenig, H. Ma, T. Walker, J. Li, D. Atzmon, L. Cohen, T. K. S. Kumar, R. Bartak, and E. Boyarski, “Multi-agent pathfinding: Definitions, variants, and benchmarks,” in Proceedings of the Annual Symposium on Combinatorial Search, 2019

2019

[5] [5]

Conflict-based search for optimal multi-agent pathfinding,

G. Sharon, R. Stern, A. Felner, and N. R. Sturtevant, “Conflict-based search for optimal multi-agent pathfinding,”Artificial Intelligence, vol. 219, pp. 40–66, 2015

2015

[6] [6]

Coordinating hundreds of cooperative, autonomous vehicles in warehouses,

P. R. Wurman, R. D’Andrea, and M. Mountz, “Coordinating hundreds of cooperative, autonomous vehicles in warehouses,”AI Magazine, vol. 29, no. 1, pp. 9–20, 2008

2008

[7] [7]

Analyzing planner design trade-offs for mapf under adg-based realistic execution,

J. Yan, Z. Li, W. Kang, S. F. Smith, and J. Li, “Analyzing planner design trade-offs for mapf under adg-based realistic execution,” 2025

2025

[8] [8]

Which mapf model works best for automated warehousing?

S. Varambally, J. Li, and S. Koenig, “Which mapf model works best for automated warehousing?”Proceedings of the International Symposium on Combinatorial Search, vol. 15, no. 1, pp. 190–198, 2022

2022