CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs

• URL: http://arxiv.org/abs/2606.04746v2
• Date: Tue, 09 Jun 2026 09:33:04 GMT
• Title: CADENCE: Predicting Realized MAPF Execution Time Beyond Sum of Costs
• Abstract summary: Multi-Agent Path Finding (MAPF) algorithms are increasingly used to plan motion for robot teams in industrial warehouses and robotic shared workspaces.<n>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.<n>We present CADENCE, a hardware study of this evaluation gap on a fixed 7 by 7 workcell with seven differential drive robots.
• Score: 0.8602553195689513
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• 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.

Related papers

• ASTRIL-MPC: Autonomous Traversal Framework of Articulated Tracked Robots with Language-Guided Neural-Kinematic MPC [10.434774696873793]
  In urban search and rescue, articulated tracked robots (ATRs) must traverse structured but contact-rich environments.<n>We present ASTRIL-MPC, a language-guided neural kinematics model predictive control framework.
  arXiv  Detail & Related papers  (2026-09-11T17:17:52Z)
• PACE: Phase-Aware Chunk Execution for Robot Policies with Action Chunking [37.9894332388921]
  PACE is a training-free test-time execution method that selects the execution horizon online from the predicted chunk itself.<n>Because PACE uses only the predicted action chunk, it is plug-and-play and requires no retraining or access to policy internals.<n>We validate PACE through large-scale evaluations in both simulation and real-robot settings.
  arXiv  Detail & Related papers  (2026-05-30T05:11:06Z)
• Object-Informed Model Predictive Path Integral Control for Non-Prehensile Robot Manipulation [7.6557550594212715]
  Long-horizon planning for non-prehensile robot manipulation is challenging due to underactuated and discontinuous interactions.<n>We propose a hierarchical formulation of model predictive path integral (MPPI) control that guides robot-level planning with a separately computed object-level plan.<n>We evaluate our method in both simulation and hardware using a 6-DoF xArm6 manipulator to perform object pushing tasks.
  arXiv  Detail & Related papers  (2026-05-29T03:10:44Z)
• Simulation-Informed Diffusion for Decentralized Multi-robot Motion Planning [56.240199425429445]
  Multi-robot motion planning requires each robot to generate collision-free trajectories from local observations.<n>Most existing planners generate trajectories from a static snapshot of the local observation.<n>This paper introduces Simulation-Informed Diffusion (SID), a decentralized framework built on constraint-aware diffusion models.
  arXiv  Detail & Related papers  (2026-05-26T21:17:53Z)
• Time-series Meets Complex Motion Modeling: Robust and Computational-effective Motion Predictor for Multi-object Tracking [0.0]
  Multi-object tracking (MOT) is critical in numerous real-world applications, including surveillance, autonomous driving, and robotics.<n>We introduce the Temporal Convolutional Motion Predictor (TCMP), a novel framework for MOT that leverages a modified Temporal Convolutional Network (TCN) featuring dilated convolutions and a regression head.<n> Experimental results demonstrate that our approach achieves state-of-the-art performance, specifically improves upon the previous best method in several key metrics.
  arXiv  Detail & Related papers  (2026-05-01T02:51:59Z)
• UMBRELLA: Uncertainty-aware Multi-robot Reactive Coordination under Dynamic Temporal Logic Tasks [5.794342083222513]
  This paper addresses the problem of coordinating multi-robot systems for collaborative tasks involving dynamic and moving targets.<n>We explicitly model the uncertainty in target motion prediction via Conformal Prediction (CP)<n>The proposed framework (UMBRELLA) combines the Monte Carlo Tree Search (MCTS) over partial plans with uncertainty-aware rollouts.
  arXiv  Detail & Related papers  (2026-03-26T12:40:04Z)
• Autonomous Vehicle Path Planning by Searching With Differentiable Simulation [55.46735086899153]
  Planning allows an agent to safely refine its actions before executing them in the real world.<n>In autonomous driving, this is crucial to avoid collisions and navigate in complex, dense traffic scenarios.<n>Here we propose Differentiable Simulation for Search (DSS), a framework that leverages the differentiable simulator Waymax as both a next state predictor and a critic.
  arXiv  Detail & Related papers  (2025-11-14T07:56:34Z)
• Agentic World Modeling for 6G: Near-Real-Time Generative State-Space Reasoning [70.56067503630486]
  We argue that sixth-generation (6G) intelligence is not fluent token prediction but calibrated the capacity to imagine and choose.<n>We show that WM-MS3M cuts mean absolute error (MAE) by 1.69% versus MS3M with 32% fewer parameters and similar latency, and achieves 35-80% lower root mean squared error (RMSE) than attention/hybrid baselines with 2.3-4.1x faster inference.
  arXiv  Detail & Related papers  (2025-11-04T17:22:22Z)
• PIVOT-R: Primitive-Driven Waypoint-Aware World Model for Robotic Manipulation [68.17081518640934]
  We propose a PrIrmitive-driVen waypOinT-aware world model for Robotic manipulation (PIVOT-R) PIVOT-R consists of a Waypoint-aware World Model (WAWM) and a lightweight action prediction module. Our PIVOT-R outperforms state-of-the-art open-source models on the SeaWave benchmark, achieving an average relative improvement of 19.45% across four levels of instruction tasks.
  arXiv  Detail & Related papers  (2024-10-14T11:30:18Z)
• AMP: Autoregressive Motion Prediction Revisited with Next Token Prediction for Autonomous Driving [59.94343412438211]
  We introduce the GPT style next token motion prediction into motion prediction. Different from language data which is composed of homogeneous units -words, the elements in the driving scene could have complex spatial-temporal and semantic relations. We propose to adopt three factorized attention modules with different neighbors for information aggregation and different position encoding styles to capture their relations.
  arXiv  Detail & Related papers  (2024-03-20T06:22:37Z)
• RobKiNet: Robotic Kinematics Informed Neural Network for Optimal Robot Configuration Prediction [5.570224095327175]
  Task and Motion Planning (TAMP) is essential for robots to interact with the world and accomplish complex tasks.<n>We propose a framework called the Robotic Kinematics Informed Neural Network (RobKiNet) as a bridge between task and motion layers.<n>RobKiNet integrates kinematic knowledge into neural networks to train models capable of efficient configuration prediction.
  arXiv  Detail & Related papers  (2024-02-26T03:54:32Z)
• SABER: Data-Driven Motion Planner for Autonomously Navigating Heterogeneous Robots [112.2491765424719]
  We present an end-to-end online motion planning framework that uses a data-driven approach to navigate a heterogeneous robot team towards a global goal. We use model predictive control (SMPC) to calculate control inputs that satisfy robot dynamics, and consider uncertainty during obstacle avoidance with chance constraints. recurrent neural networks are used to provide a quick estimate of future state uncertainty considered in the SMPC finite-time horizon solution. A Deep Q-learning agent is employed to serve as a high-level path planner, providing the SMPC with target positions that move the robots towards a desired global goal.
  arXiv  Detail & Related papers  (2021-08-03T02:56:21Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.