CS Paper Radar

A traffic management system for large and heterogeneous vehicles in narrow industrial environments

Alessandro Bonetti, Silvia Proia, Simone Guidetti, Lorenzo Sabattini

cs.RO cs.MA ·submitted 2026-09-09 16:20 UTC · v1
published

Abstract

The coordination of Automated Guided Vehicles (AGVs) in high-density industrial environments represents a critical challenge within Logistics 4.0, as traditional traffic management methods often lead to inefficiencies caused by negotiation-based priority assignment. To overcome the resulting limitations, this paper presents an innovative AGV traffic management system based on a Lifelong Multi-Agent Path Finding (L-MAPF) algorithm operating on roadmaps generated with Non-Uniform Rational B-Splines (NURBS) curves. The approach guarantees locally optimal coordination and ensures safe operation of large and heterogeneous AGVs. Building on this concept, the proposed framework integrates a modified version of the Bounded Horizon Conflict Based Search (CBS) technique within a Rolling Horizon Conflict Resolution strategy, utilizing an extended time horizon for each agent to enable effective conflict resolution in corridors identified by a topological map. In contrast to state-of-the-art methods for AGV fleet traffic management, the proposed solution is designed for real-world, non-standardized (i.e., non-grid-like) industrial settings characterized by narrow bidirectional corridors and high-traffic density, where AGVs of various sizes and capabilities operate simultaneously. Key contributions include an anytime conflict resolution strategy with adaptive time horizon regulation, an execution layer for safe and standard-compliant interaction with real AGVs, and an advanced mechanism for deadlock detection and resolution. Experimental results obtained in realistic industrial environments demonstrate higher throughput, with improvements of up to 11% over a conventional rule-based traffic management system, a state-of-the-art industrial method, and a priority-based L-MAPF variant, while maintaining continuous operation and improved efficiency.

Journal ref
The International Journal of Robotics Research. 2026
DOI
10.1177/02783649261470035

Closest papers

Nearest neighbours by meaning across the whole index.

The Cost of Classical Multi-Agent Path Finding

cs.MA ·2026-10-07 ·Alvin Combrink, Sabino Francesco Roselli, Martin Fabian
theory similarity 0.64
Abstract · 9 pages, 5 figures

Multi-Agent Path Finding (MAPF) is the problem of planning conflict-free paths for multiple agents in a shared space, each from its start to its goal. Classical MAPF has been the dominant formulation for many years, with its assumptions of discrete time and graph-based conflicts presumably easing the search for solutions. These assumptions limit the physical environments and agents for which a solution is truly collision-free, and also place an upper bound on solution quality that no algorithmic improvements can lift. This work investigates how much solution quality, and in what contexts, the classical MAPF formulation forfeits. Continuous-time MAPF (MAPF$_R$) relaxes these assumptions, making it a natural counter-formulation to compare against across various agent counts and sizes, and graph connectedness, topologies, and resolutions. We find that continuous time and agent shape consideration are worth relatively little on their own; their value comes from enabling an expanded range of move actions, on average improving solution quality by at least $5\%$ on narrow and constrained maps and $17\%$ on maps with open spaces. In some cases, the improvements exceed $20\%$. Doubling the map resolution with classical MAPF recovers less than $3\%$, meaning that little of what is forfeited can be bought back through more compute. This work therefore provides insight on when classical MAPF is a reasonable simplification, and when MAPF$_R$ unlocks significantly higher-quality solutions.

0.08

LSRP*: Scalable and Anytime Planning for Multi-Agent Path Finding with Asynchronous Actions

cs.RO cs.AIcs.MA ·2026-11-07 ·Dachuan Liu, Shuai Zhou, Shizhe Zhao, Zhongqiang Ren
publishedhighly cited similarity 0.64
Abstract · 15 pages, 14 figures

Multi-Agent Path Finding (MAPF) seeks collision-free paths for multiple agents from their respective starting locations to their respective goal locations while minimizing path costs. Although many MAPF algorithms were developed, most of them rely on a common assumption on synchronized actions, where the actions of all agents start at the same time and always take a time unit. This assumption may limit the use of MAPF planners in practice. To get rid of this assumption, recently, an algorithm called Loosely Synchronized Rule-based Planning (LSRP) was proposed, which can find sub-optimal solutions for many agents. However, LSRP often finds poor quality solutions due to its unbounded sub-optimality. This paper develops a new anytime planner called LSRP* that can keep improving solution quality after the initial solution is obtained until the runtime budget depletes. We analyze the properties of LSRP* and test it against several baselines with up to 1000 agents on various maps. LSRP* can handle up to 25% more agents than LSRP and can reduce up to 40% of the solution cost found by LSRP.

0.61

TRACS: A Geometry-Aware Framework for Scalable Multi-Agent Path Finding in Warehouses

eess.SY cs.MA ·2026-09-19 ·Siddhant Erande, Anuj Tiwari
similarity 0.63
Abstract · 9 pages, 6 figures, under review

Large scale warehouse automation relies on efficient multi agent path finding (MAPF) to coordinate thousands of robots in structured environments. Existing MAPF algorithms primarily improve conflict resolution while representing warehouses as generic navigation graphs, overlooking their inherent geometric structure and traffic patterns. This paper presents TRACS (Traffic aware Routing and Aisle Coordination System), a geometry aware planning framework that exploits warehouse layout to simplify planning rather than introducing another conflict-resolution algorithm. TRACS constructs a directed routing graph with alternating one way aisles that eliminates head on and edge swap conflicts by design, decoupling spatial routing from temporal traffic coordination. Independent hybrid graph grid routing is combined with lightweight edge based scheduling to avoid joint space time search while ensuring collision free execution. Experimental evaluation on warehouse benchmarks against representative priority based, iterative repair, and search based MAPF planners shows that TRACS consistently achieves a 100% empirical success rate while substantially improving planning scalability. On fixed scene benchmarks with up to 1000 robots, TRACS reduces planning time by up to 14.7X while maintaining competitive makespan, lower flowtime, and near optimal path quality. Under a fixed 10 minute planning budget, TRACS routes up to 5120 robots, roughly twice the largest fleet reached by the strongest baselines, while sustaining a 100% success rate, demonstrating the effectiveness of exploiting warehouse geometry for scalable robotic warehouse systems.

0.19

The Cost of Executability: Temporal Margins for Continuous-Time Multi-Agent Path Finding under Closed-Loop Control

eess.SY ·2026-10-14 ·Sabino Roselli, Alvin Combrink, Ze Zhang
benchmark similarity 0.60
Abstract

Multi-agent path finding (MAPF) solvers are evaluated on the schedules they produce, not on how well those schedules can be executed. Specifically, continuous-time optimal solvers can achieve even lower cost than their discrete counterparts by scheduling agents with near-zero temporal/spatial separation, and by exploiting graphs with higher connectedness; however, such schedules may prove hard to execute under a realistic controller. We integrate AOC-CBS, an anytime-optimal continuous-time MAPF solver, into a fleet coordination framework in which each agent tracks its timed path using model predictive control, and we evaluate the resulting system on congested MovingAI benchmark instances with 21 to 40 agents. Without intervention, only a fraction of the instances complete execution. We then apply T-robustness by adding a time-margin, i.e., a minimum temporal gap between agents at shared locations, as well as spatial inflation of the agent footprint. Increasing either margin raises execution success, for a relatively small increase in the schedule's sum-of-costs; it also improves how closely agents adhere to the schedule: when tracking each agent's position throughout execution and comparing it against the position it should occupy according to the schedule, the mean discrepancy falls significantly as the margin increases. In general, the two margins have different effects; temporal margin decreases deviation, giving the controller room to stay on schedule. Spatial margin affects deviation less and instead increases the clearance between agents, so that the same deviation no longer leads to a blocking stall. They are nonetheless substitutes rather than complements: spatial inflation is almost free in schedule cost, but its effect on execution success is small and does not compound with a temporal margin already in place.

0.12

A Theoretical Framework for Parallel Lifelong MAPF Using Group Decentralized Planning

cs.MA cs.AIcs.RO ·2026-08-18 ·Alex DeWeese, Jiaoyang Li, Guannan Qu
similarity 0.60
Abstract

In the Lifelong Multi-Agent Path Finding (L-MAPF) problem, agents must repeatedly move from one destination to another while avoiding obstacles and inter-agent collisions. Widely regarded as one of the highest-performing solutions to this problem is the Rolling-Horizon Collision Resolution (RHCR) framework. However, commensurate with its quality solutions, it incurs a computational cost that limits its applicability to even modest agent counts. In this paper, leveraging theoretical methods from the Locally Interdependent Multi-Agent MDP literature, we first theoretically prove the near-optimality of RHCR in a discounted MDP formulation of the L-MAPF problem. Then, we leverage these results to naturally motivate an extended framework called Group Decentralized RHCR (GD-RHCR) which incorporates a group decentralized structure that partitions agents based on a transitive communication scheme and plans for each partition of agents in parallel. We show that both RHCR and GD-RHCR achieve similar exponentially close to optimal guarantees, establishing a theoretical duality between the time based restrictions performed by vanilla RHCR and the additional space based partitioning performed by GD-RHCR. Lastly, we show that across varying maps, GD-RHCR is able to attain high throughput that scales into higher agent counts while maintaining a significantly lower per plan cost.

0.14

Solving Multi-Agent Sokoban via LaCAM

cs.MA ·2026-09-30 ·Keisuke Okumura
benchmark similarity 0.60
Abstract

Sokoban, a puzzle game in which an agent pushes boxes onto unlabelled target locations in a grid world, is a long-standing benchmark planning problem. While it is easy to see the connection to practical applications such as warehouse logistics with autonomous forklifts, its multi-agent counterpart has remained underdeveloped. This is because Multi-Agent Sokoban is substantially more difficult due to factors specific to multi-agent planning, such as the rapidly growing branching factor as the number of agents grows and the need to handle integrated task assignment and collision-free pathfinding. In this paper, we show that a scalable planner for Multi-Agent Sokoban can be designed by leveraging recent advances in multi-agent pathfinding (MAPF). Specifically, our Sokoban-LaCAM efficiently solves instances involving tens of agents and boxes while preserving both completeness and eventual optimality guarantees. This provides evidence that MAPF can serve as a powerful primitive for solving broader collective automation problems.

0.17

Paying for Space: Incentive-Aware Motion Planning for Multi-Agent Collision Avoidance

eess.SY ·2026-09-20 ·Debajyoti Chakrabarti, Anushri Dixit
published similarity 0.60
Abstract · Accepted to the 2026 IEEE Conference on Decision and Control (CDC)

Advanced Air Mobility (AAM) systems require scalable coordination mechanisms to manage large fleets of aerial vehicles operating in shared, capacity-limited airspace. In such environments, different operators may have private preferences over trajectory characteristics, such as travel time, fuel consumption, or deviation from nominal routes. If centralized traffic management relies on self-reported preferences, operators may strategically misreport their costs to obtain more favorable trajectories. This paper proposes a multistage motion planning framework augmented with mechanism design to enable collision avoidance for AAM systems with privately known costs. The proposed approach integrates convex safe corridor construction with a VCG-inspired mechanism to ensure conflict-free passage through constrained airspace while incentivizing truthful revelation of private preferences. Simulation results demonstrate safe and decentralized coordination among agents with heterogeneous preferences.

0.26

CARRS: A Constraint-Aware, Real-Time Routing System for Emergency Vehicles in Urban Environments

cs.AI ·2026-10-19 ·Vincent Sello, Timothy Adeliyi, Ridewaan Hanslo
similarity 0.59
Abstract · 10 pages, 3 figures, 3 tables

Emergency vehicles such as police vehicles, fire engines, and ambulances require a stable and efficient route optimization to reach life-critical events in the shortest times possible. However, the dynamic nature of urban traffic makes this ideal scenario much more challenging, causing critical life-threatening delays. Traditional civilian navigation systems cannot account for real-time traffic changes alongside vehicle-specific constraints, creating inadequate routing scenarios. This research presents the Constraint-Aware Real-Time Routing System (CARRS), a unified software architecture tailored for emergency coordination. The CARRS architecture is engineered to fuse together classical pathfinding algorithms such as A*, Dijkstra, and Bidirectional A*, with Constraint Satisfaction Problem methodologies. The Design Science Research Methodology is the research framework, and prototyping is the iterative process. The artifact was empirically evaluated using OpenStreetMap data for major metropolitan road networks, combined with simulated dynamic traffic scenarios. Performance metrics focused on route optimality, constraint adherence, rerouting responsiveness, and the potential for future system scalability. Findings revealed the system's capability to generate optimal routes for operationally relevant subgraphs in under 35 seconds, with incremental rerouting responsiveness below 20 seconds. Furthermore, the system achieved more than 90% adherence to vehicle-specific constraints, making the CARRS architecture viable for real-time dynamic routing requirements. This study delivers a routing platform that bridges artificial intelligence-driven optimization with software engineering operational compliance, presenting a practical transformative step toward adaptive emergency vehicle coordination in dynamic urban environments.

0.28