Multi-Agent Path Finding (MAPF) coordinates multiple agents in a shared environment so that they reach their goals without collisions. It supports large robotic systems such as automated warehouses and manufacturing, and is also relevant to traffic-intersection coordination and airport surface operations. Conventional MAPF solvers usually use discrete time and simplified robot models while optimizing discrete objectives such as the sum of path lengths or makespan. Physical execution instead depends on heterogeneous robot dynamics, accumulated delays, communication, low-level control, and asynchronous interactions, so a plan that is good in the discrete model need not be good in wall-clock time.
The first contribution is ExecTimeNet, a learned world model that predicts the realized execution state of each action in a discrete MAPF solution, including its wall-clock completion time and terminal kinodynamic state. The second is REMAP, which uses those predictions during MAPF search to favor solutions with better expected execution performance. The paper also introduces ESADG, a post-planning optimizer that changes inter-agent precedence at shared locations while preserving path feasibility. In addition, an adaptive gating mechanism selectively invokes the predictor to reduce REMAP’s prediction overhead. Together, these components bridge discrete planning and physical execution through learned execution prediction and schedule optimization, rather than placing every detailed robot dynamic directly inside planning search.
ExecTimeNet takes an Action Dependency Graph (ADG) induced by a discrete MAPF solution as its input. The graph represents both each agent’s sequence of actions and inter-agent dependencies created by interactions at shared locations. Node features include the action’s position along its agent path, the in-degree and out-degree of Type-2 edges, cumulative counts of preceding and subsequent translations and rotations by the same agent, and whether the node has an outgoing inter-agent edge that blocks another agent. A weight-shared, three-layer unidirectional LSTM processes each agent’s action sequence, and three stacked GATv2 graph-attention layers aggregate spatial context across inter-agent dependency edges. ExecTimeNet predicts completion times and execution states; because true execution times are unavailable during planning, REMAP uses these predictions as a surrogate objective inside representative CBS and MAPF-LNS search procedures. The adaptive gate estimates when an oracle prediction is worthwhile, and the algorithm returns the best known solution on timeout. After planning, ESADG evaluates candidate reversals of switchable Type-2 edges and preserves ADG acyclicity, which is equivalent to deadlock-free ADG execution according to the supplied evidence.
The evaluation uses SMART, a physics-based simulator that models continuous robot kinodynamics, low-level controller behavior, network communication, and inter-agent interaction effects. The simulation experiments use up to 300 agents and eight maps converted from the MovingAI Benchmark: empty, maze, random, room, den312d, WH-S, WH-L, and boston, with 25 instances per map. ExecTimeNet is trained from MAPF-LNS solutions collected on six maps, with agent counts from 10 to 300 and solutions saved at successive iterations, producing 28,177 graphs. The model is evaluated on in-distribution and out-of-distribution data, including transfer to unseen maps and agent counts, and the paper also reports a feature-ablation study. Physical-robot validation is included, but the supplied excerpt does not establish every baseline identity, the number and configuration of physical robots, or complete metric tables.
In simulation, REMAP reduces delay by up to 21% relative to baselines, while ESADG achieves up to 40% normalized improvement. On physical hardware, the full pipeline reduces total execution time by up to 15.3%, indicating transfer from simulation-based evaluation toward real deployment. The results suggest that plan selection and execution-order adjustment can remain useful even when the predictor is not exact. However, prediction errors arise because some physical sources of variation cannot be inferred from a MAPF plan alone. The physical calibration set contained only 100 executions because of laboratory constraints, and the paper identifies broader execution-aware objectives and additional robot platforms as future directions.
Standard MAPF is defined on an undirected graph with a start vertex and a goal vertex for each agent and uniform discrete time steps. A valid solution avoids vertex conflicts, in which two agents occupy the same vertex at the same time, and edge conflicts, in which two agents traverse the same edge in opposite directions at the same time. CBS resolves conflicts by incrementally adding constraints, whereas LNS repeatedly replans subsets of agents from a feasible solution. During deployment, ADG-like execution frameworks transform discrete paths into executable schedules and encode precedence at shared locations. Methods that incorporate more accurate robot models directly into planning can improve plan fidelity, but the supplied evidence states that they increase computational complexity and may be limited in scalability.
The central problem is not only to find collision-free paths, but also to predict and improve how those paths unfold in a physical multi-robot system. A discrete action may take different amounts of time for different robots, and its delay can affect later actions of the same robot as well as dependent actions of other robots. Shared locations couple agents, so a local disturbance can cascade through a long dependency chain and worsen the overall completion time. The desired framework must therefore reason about inter-agent delay propagation and intra-agent timing and kinodynamic state while retaining the practical benefits of MAPF search.
ExecTimeNet combines a temporal encoder for each agent with graph attention over inter-agent dependencies. Its features explicitly describe action order, Type-2 dependency degrees, counts of preceding and subsequent translations and rotations, and whether an action blocks another agent. REMAP treats predicted execution time as a planning-time surrogate and is instantiated with both CBS and MAPF-LNS representatives. ESADG treats Type-2 precedence directions as an additional execution decision, changing the ordering at shared locations without changing the planned paths. Maintaining ADG acyclicity is central because, according to the supplied evidence, ADG execution is deadlock-free if and only if the graph is acyclic.
The SMART experiments use a warehouse-oriented motion model in which a robot translates along its current direction and changes direction through in-place rotation. Each instance specifies start-goal pairs and per-agent maximum linear velocity, linear acceleration, and maximum angular velocity sampled from a correlated distribution. Training data are collected from MAPF-LNS solutions on six of the eight benchmark maps, including solutions saved at successive iterations. The evaluation includes unseen maps and agent counts, feature ablation, and physical-robot validation. The excerpt does not provide the full hardware setup, all execution conditions, or the names and implementations of every comparison method.
The paper reports that ExecTimeNet accurately predicts execution information and transfers to unseen maps and agent counts. Across simulation benchmarks with diverse topologies, REMAP reduces delay by up to 21% over baselines, and ESADG achieves up to 40% normalized improvement. On physical robots, the full pipeline reduces total execution time by up to 15.3%. These are “up to” values; the supplied evidence does not establish that they are averages, medians, or guaranteed improvements, and it does not provide complete statistical-significance information.
The paper presents a world-model-driven framework for connecting discrete MAPF planning with realistic execution performance. ExecTimeNet predicts realized execution times and states from dependency structure, REMAP uses those predictions during search, and ESADG improves execution ordering after a plan has been found. Simulation and hardware results support the claim that execution-aware reasoning can improve performance over methods based only on discrete planning objectives. Deadline satisfaction is studied as a representative execution-aware objective, where predicted wall-clock arrival times can improve performance under timing constraints. The overall conclusion is that a learned execution model can provide a practical bridge between scalable MAPF planning and physical multi-robot deployment.
The predictor can have errors because a MAPF plan does not expose every physical source of execution variation. The physical calibration set was limited to 100 executions, although larger fleet-level logs could potentially provide more data for fine-tuning. The supplied excerpt does not establish the framework’s behavior across many robot platforms, severe communication failures, dynamic obstacles, or specified computational-time limits. It also does not provide enough detail to determine how broadly the reported percentage improvements generalize beyond the tested maps and hardware. These omissions limit what can be concluded about robustness outside the reported settings.
A MAPF solution can be strong under a discrete objective while producing poor wall-clock performance because robots move at different speeds, wait at shared locations, or accumulate delays. Making execution performance an explicit object of prediction and optimization is therefore important for transferring MAPF from benchmarks to deployed robot fleets. The proposed approach offers a middle ground between ignoring execution and embedding a detailed dynamics model in every planning operation. Its combination of realistic simulation, experiments with up to 300 agents, and physical validation is relevant to researchers studying execution-aware multi-robot coordination.
This paper is recommended for researchers interested in the difference between discrete MAPF solution quality and actual robot completion time. It is particularly relevant to work on MAPF, CBS, LNS, Action Dependency Graphs, learned world models, execution scheduling, warehouse robotics, and deadline-aware MAPF. Researchers seeking to extend existing search solvers toward execution-aware objectives can use REMAP and its adaptive gating idea as design references, while those studying post-planning coordination can examine ESADG’s precedence-order optimization. Readers who need complete hardware specifications, exhaustive baseline definitions, or broad cross-platform evidence will need information beyond the supplied excerpt.