← Back to all news
arXiv AI By Foivos Fioravantes, Du\v{s}an Knop, Jan Maty\'a\v{s} K\v{r}i\v{s}\v{t}an, Nikolaos Melissinos, Michal Opler

Exact Algorithms for Multiagent Path Finding with Communication Constraints on Tree-Like Structures

Read the original on arXiv AI →

The paper studies Multiagent Path Finding with limited communication ranges, aiming to minimize makespan while preserving a communication backbone. It presents three exact algorithms that are efficient for networks with tree or bounded‑treewidth topologies when the communication range and number of agents are given as input. The authors also prove that efficient algorithms are unlikely when the number of agents is part of the input, even for small makespan and communication range values.

Machine-generated by The Flow from the publisher's headline and feed description — not written or checked by a human. The full article lives at arXiv AI.

Related stories

arXiv AI
Aug 19

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

The paper presents a theoretical analysis of the Rolling‑Horizon Collision Resolution (RHCR) framework for Lifelong Multi‑Agent Path Finding (L‑MAPF), proving its near‑optimality in a discounted MDP setting. Building on this, the authors introduce Group Decentralized RHCR (GD‑RHCR), which partitions agents via a transitive communication scheme and plans each partition in parallel, achieving similar optimality guarantees while reducing per‑plan computational cost. Experiments across various maps demonstrate that GD‑RHCR scales to higher agent counts with high throughput and lower cost compared to vanilla RHCR.

By Alex DeWeese, Jiaoyang Li, Guannan Qu
agentsefficiency
More like this →
arXiv AI
Oct 9

Simultaneous Computation with Multiple Prioritizations in Multi-Agent Motion Planning

The paper proposes a method that allows agents in multi‑agent motion planning to compute with multiple prioritizations simultaneously, avoiding reliance on domain‑specific heuristics or costly iterative searches. This general approach is applied to receding‑horizon motion planning with system dynamics, and numerical experiments show near‑optimal prioritization and performance gains over state‑of‑the‑art methods with only a slight increase in computation time. Real‑time feasibility is demonstrated on a road network with ten vehicles in a Cyber‑Physical Mobility Lab.

By Patrick Scheffe, Julius Kahle, Bassam Alrifaee
agentsbenchmarks
More like this →
arXiv AI
Aug 26

Pivot-and-Station Multi-Agent Path Finding: Solvability, Complexity, and Algorithms

The paper introduces Pivot-and-Station Multi-Agent Path Finding (PS‑MAPF), a variant of MAPF where a subset of agents must visit interchangeable pivots before all agents occupy anonymous stations. It provides a full solvability characterization: every instance on a 2‑edge‑connected graph is solvable, and for arbitrary connected graphs a structural effective‑distance measure relative to unoccupied vertices gives a necessary and sufficient condition. The authors prove that minimizing station‑makespan or station‑flowtime is NP‑hard even with a single pivot, and present three algorithms—a complete baseline, a SAT‑based optimal solver, and Pivot‑Prioritized Planning (PPP), which solves 74‑89% of benchmark instances with significantly lower makespan and flowtime than the baseline.

By Andrea Di Nezza, Mihir Patel, Fabio Fagnani, Sara Bernardini
agentsroboticsbenchmarks
More like this →