Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding

• URL: http://arxiv.org/abs/2603.26684v1
• Date: Wed, 11 Mar 2026 11:04:54 GMT
• Title: Decoupling Geometric Planning and Execution in Scalable Multi-Agent Path Finding
• Abstract summary: Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph.<n>We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution.
• Score: 44.79409119345322
• License: http://creativecommons.org/licenses/by-sa/4.0/
• Abstract: Multi-Agent Path Finding (MAPF) requires collision-free trajectories for multiple agents on a shared graph, often with the objective of minimizing the sum-of-costs (SOC). Many optimal and bounded-suboptimal solvers rely on time-expanded models and centralized conflict resolution, which limits scalability in large or dense instances. We propose a hybrid prioritized framework that separates geometric planning from execution-time conflict resolution. In the first stage, Geometric Conflict Preemption (GCP) plans agents sequentially with A* on the original graph while inflating costs for transitions entering vertices used by higher-priority paths, encouraging spatial detours without explicit time reasoning. In the second stage, a Decentralized Local Controller (DLC) executes the geometric paths using per-vertex FIFO authorization queues and inserts wait actions only when required to avoid vertex and edge-swap conflicts. Experiments on standard benchmark maps with up to 1000 agents show that the method scales with an empirically near-linear runtime trend and attains a 100% success rate on instances satisfying the geometric feasibility assumption. On bottleneck-heavy maps, GCP reduces synchronization-induced waiting and often improves SOC on bottleneck-heavy maps

Related papers

• GeoPAR: Large-Scale Multi-Agent Combinatorial Optimization with Geometry-Guided Parallel Autoregressive Learning [4.471528509969228]
  GeoPAR is a geometry-guided parallel autoregressive reinforcement learning framework for scalable multi-agent optimization.<n>Experiments show that GeoPAR improves large-scale zero-shot generalization while substantially reducing rollout steps and maintaining efficient inference.
  arXiv  Detail & Related papers  (2026-09-01T02:14:05Z)
• Biconvex Optimization for Smooth Minimum-Time Trajectories around Convex Obstacles [49.315843050082925]
  We present a bi approach for minimum-time motion planning convex obstacles that is guaranteed to converge.<n>We find that the proposed method produces high-quality trajectories with times to produce state-of-the-art decomposition of variables.
  arXiv  Detail & Related papers  (2026-08-03T19:48:24Z)
• Closed-Form Spectral Regularization for Multi-Task Model Merging [96.82449201305234]
  Model merging combines several independently fine-tuned experts into a single multi-task model without any training data.<n>State-of-the-art merging methods formulate merging as a layer-wise interference problem.<n>We propose SWUDI, a closed-form method that combines a soft exponential filter, which matches the gradient-flow trajectory of iterative descent.
  arXiv  Detail & Related papers  (2026-06-05T14:00:47Z)
• Fitting Unknown Number of Hyperplanes with Manifold Optimization [57.48093263119306]
  Fitting unknown number of linearplanes to data is a fundamental yet challenging problem in machine learning.<n>Existing approaches often struggle with optimum optima or lack geometric consistency.
  arXiv  Detail & Related papers  (2026-05-27T14:02:20Z)
• A Learning Method with Gap-Aware Generation for Heterogeneous DAG Scheduling [6.655206888698601]
  We propose an end-to-end reinforcement learning framework for heterogeneous directed acyclic graphs (DAGs)<n>WeCAN addresses task--pool compatibility coefficients and generation-induced optimality gaps.<n>Experiments on graphs and real-world TPC-H DAGs demonstrate improved makespan over strong baselines, with inference time comparable to classicals.
  arXiv  Detail & Related papers  (2026-03-24T14:16:08Z)
• Collision-Free Velocity Scheduling for Multi-Agent Systems on Predefined Routes via Inexact-Projection ADMM [0.0]
  In structured multi-agent projects, agents often must follow predefined routes, making rerouting or impossible.<n>This paper addresses route-constrained multi-agent coordination by optimizing waypoint times while preserving each agent's assigned waypoint order and nominal route assignment.
  arXiv  Detail & Related papers  (2026-03-23T12:34:18Z)
• Speedup Techniques for Switchable Temporal Plan Graph Optimization [7.478072166004144]
  Multi-Agent Path Finding (MAPF) focuses on planning collision-free paths for multiple agents.<n>During the execution of a MAPF plan, agents may encounter unexpected delays, which can lead to inefficiencies, deadlocks, or even collisions.<n>This paper introduces Improved GSES, which significantly accelerates Graph-Based Switchable Edge Search (GSES) through four speedup techniques.
  arXiv  Detail & Related papers  (2024-12-20T13:59:15Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• GoRela: Go Relative for Viewpoint-Invariant Motion Forecasting [121.42898228997538]
  We propose an efficient shared encoding for all agents and the map without sacrificing accuracy or generalization. We leverage pair-wise relative positional encodings to represent geometric relationships between the agents and the map elements in a heterogeneous spatial graph. Our decoder is also viewpoint agnostic, predicting agent goals on the lane graph to enable diverse and context-aware multimodal prediction.
  arXiv  Detail & Related papers  (2022-11-04T16:10:50Z)
• Decoupled Multi-task Learning with Cyclical Self-Regulation for Face Parsing [71.19528222206088]
  We propose a novel Decoupled Multi-task Learning with Cyclical Self-Regulation for face parsing. Specifically, DML-CSR designs a multi-task model which comprises face parsing, binary edge, and category edge detection. Our method achieves the new state-of-the-art performance on the Helen, CelebA-HQ, and LapaMask datasets.
  arXiv  Detail & Related papers  (2022-03-28T02:12:30Z)
• Distributed stochastic optimization with large delays [59.95552973784946]
  One of the most widely used methods for solving large-scale optimization problems is distributed asynchronous gradient descent (DASGD) We show that DASGD converges to a global optimal implementation model under same delay assumptions.
  arXiv  Detail & Related papers  (2021-07-06T21:59:49Z)
• Symmetry Breaking for k-Robust Multi-Agent Path Finding [30.645303869311366]
  k-Robust Conflict-BasedSearch (k-CBS) is an algorithm that produces coordinated and collision-free plan that is robust for up to k delays. We introduce a variety of pairwise symmetry breaking constraints, specific to k-robust planning, that can efficiently find compatible and optimal paths for pairs of conflicting agents.
  arXiv  Detail & Related papers  (2021-02-17T11:09:33Z)
• A Feedback Scheme to Reorder a Multi-Agent Execution Schedule by Persistently Optimizing a Switchable Action Dependency Graph [65.70656676650391]
  We consider multiple Automated Guided Vehicles (AGVs) navigating a common workspace to fulfill various intralogistics tasks. One approach is to construct an Action Dependency Graph (ADG) which encodes the ordering of AGVs as they proceed along their routes. If the workspace is shared by dynamic obstacles such as humans or third party robots, AGVs can experience large delays. We present an online method to repeatedly modify acyclic ADG to minimize route completion times of each AGV.
  arXiv  Detail & Related papers  (2020-10-11T14:39:50Z)

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.