Source-linked AI summary
A traffic management system for large and heterogeneous vehicles in narrow industrial environments
Alessandro Bonetti, Silvia Proia, Simone Guidetti, Lorenzo Sabattini
TL;DR
The paper addresses traffic coordination for large, heterogeneous AGVs in dense, complex industrial environments where real-world constraints can produce deadlocks. It proposes an L-MAPF-based architecture with smooth NURBS roadmaps, conflict resolution, safe execution, and deadlock handling, achieving throughput improvements of up to 11% in realistic layouts.
Problem
Dense, constrained industrial AGV environments remain difficult to coordinate because real-world implementation constraints and unpredictable conditions can lead to deadlocks.
Method
The paper proposes an L-MAPF coordination strategy using smooth, kinematically feasible NURBS roadmaps, precomputed collision handling, precedence-based deadlock detection, and conflict resolution.
Results
Throughput improvements of up to 11% were demonstrated in realistic layouts against a conventional rule-based system, a state-of-the-art industrial solution, and an alternative L-MAPF variant.
Takeaways & Limitations
The validated architecture supports continuous, safe, and efficient coordination of heterogeneous AGVs in complex industrial environments.
Takeaways & Limitations
The current system assumes AGVs follow paths established during task assignment, motivating future work on adaptive path adjustment and online replanning.
Abstract
from arXiv · showhide
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.
1 Introduction
AGV traffic management remains difficult in dense, irregular industrial environments because rule-based coordination and grid-oriented L-MAPF assumptions do not fully reflect real operating conditions. The paper proposes an integrated L-MAPF-based architecture with safe execution and deadlock handling for large, heterogeneous fleets.
- Rule-based coordination can create bottlenecks and inappropriate priority handling, reducing traffic-management efficiency.
- L-MAPF extends MAPF to continuously resolve changing task and operating conditions throughout agents’ operational lifespans.
- Most L-MAPF algorithms target grid-like environments and often assume homogeneous vehicles and unit-time actions, limiting applicability to complex industrial systems.
- Real-world constraints and unpredictable conditions can still produce deadlocks, requiring detection and resolution for conflict-free, continuous AGV operation.
- The proposed system periodically computes collision-free trajectories for large, heterogeneous AGVs and adds a path allocator plus deadlock detection and resolution for deployable operation.
2 Related Works and Paper Contributions
Existing AGV coordination methods address parts of the problem but generally do not jointly support heterogeneous vehicles, continuous non-grid roadmaps, variable traversal times, and dense industrial traffic. The paper therefore introduces an integrated architecture combining locally optimal L-MAPF coordination with execution and conflict-management mechanisms.
- Research gap: Existing methods generally do not jointly support heterogeneous geometries and capabilities, non-grid layouts, variable-duration actions, and rolling-horizon replanning.
- Related works: Rule-based methods rely on static rules or heuristics, limiting general applicability and formal performance guarantees in complex traffic.
- Related works: Search-based and L-MAPF methods offer systematic coordination or solution-quality guarantees, but commonly assume homogeneous agents, unit-time actions, or grid-based environments.
- Contributions: The architecture targets real industrial environments while preserving real-time solvability and locally optimal coordination under simultaneous realistic constraints.
- Contributions: Its contributions include an anytime Bounded Horizon CBS extension, a safe standard-compliant path allocator, and deadlock detection and resolution.
3 Preliminaries
The paper formulates traffic management for large, heterogeneous AGVs in non-standardized industrial environments with narrow corridors, intersections, and irregular layouts. It defines roadmap, vehicle, collision, and operating assumptions for safe, efficient, dynamically feasible coordination.
- The problem combines safe, efficient motion planning, collision avoidance, deadlock handling, and traversal-cost minimization for heterogeneous AGVs performing sequential tasks.
- The environment is modeled as a predefined roadmap of locations and connecting segments embedded in a partitioned industrial workspace.
- An AGV footprint is a convex polygon placed at pose q = (x, y, θ), defining the vehicle’s occupied workspace.
- Roadmap collisions cover location-location, segment-segment, and segment-location footprint overlaps during simultaneous occupation or traversal.
- The formulation assumes fixed task-provided roadmaps and paths, task lists supplied externally, and AGVs that wait at locations or move along segments.
4 Traffic Management Architecture
The proposed architecture uses a centralized Traffic Manager to maintain global system information and coordinate heterogeneous AGVs. It periodically recomputes collision-free trajectories through an L-MAPF coordinator as tasks, states, and uncertainties evolve.
- A centralized Traffic Manager supports global coordination, optimization, deadlock resolution, and consistent decisions in dense or frequently changing operations.
- The Traffic Manager receives updated AGV states and Task Lists, including transport, navigation, and battery-charging assignments.
- The L-MAPF coordinator periodically computes collision-free, coherent trajectories while adapting to task updates and execution uncertainties.
5 Environment Model
The environment model combines a geometric roadmap with a topological sector layer to represent heterogeneous AGV motion and corridor-specific coordination. Precomputed collision sets provide exact roadmap-element conflict information with constant-time lookup during operation.
- Environment layers: The roadmap layer calculates AGV paths, velocities, and spatial occupancy, while the topological layer partitions the environment for customized coordination strategies.
- Heterogeneous AGVs: Each AGV class is assigned a strongly connected roadmap subgraph with class-specific kinematic constraints and footprints.
- Roadmap layer: Roadmap segments use smooth G1-continuous NURBS curves to satisfy geometric and curvature constraints and reduce abrupt vehicle-orientation changes.
- Collision representation: Collision sets are computed offline for roadmap vertices and edges, enabling O(1) runtime lookup while preserving geometric accuracy in confined spaces.
- Collision representation: The collision-set algorithm is exact: its computed set Y_m neither adds nor omits colliding roadmap elements relative to the true set D_m.
6 Path Generation and Trajectory Definition
Tasks provide fixed paths for active AGVs, whose trajectories are sequences of move and wait actions over heterogeneous roadmap edges. The framework incorporates upcoming tasks so coordination can anticipate conflicts beyond the current goal and avoid deadlocks.
- Task representation: The system distinguishes operational pick-up/drop-off tasks from return-to-battery-charger tasks, each defined by start and goal vertices.
- Task representation: Considering each AGV’s next task prevents the coordinator from treating its current goal as permanently occupied, avoiding coordination choices that can produce deadlocks.
- Deadlock considerations: The fixed-path strategy is valid for return-to-charger tasks but unsuitable for operational tasks under Assumption 5, creating two described deadlock scenarios.
- Path generation: Each active AGV follows a fixed path computed on its class-specific roadmap subgraph, with a main path extended by a next-task path when applicable.
- Trajectory definition: A trajectory is an ordered sequence of move and wait actions, where edge traversal durations equal edge costs and waiting lasts one timestep.
7 L-MAPF Coordinator
The L-MAPF coordinator repeatedly computes collision-free trajectories for active AGVs while respecting fixed paths, obstacles, and narrow-corridor constraints. Its anytime ABH-CBS planner refines bounded-horizon solutions as computation permits, although optimal coordination is NP-hard.
- 7 L-MAPF Coordinator: The coordinator periodically recomputes space-time-consistent, collision-free trajectories so AGVs can adapt to task changes, evolving states, and execution uncertainties.Unlike one-shot planning, rolling-horizon instances are recomputed continuously.
- 7 L-MAPF Coordinator: Coordination is restricted to each AGV's fixed-path subgraph and accounts for static obstacles, allocated trajectories of other AGVs, and dynamic obstacle occupancy.Allocated trajectories are treated as dynamic obstacles when planning for other AGVs.
- 7 L-MAPF Coordinator: Extended horizons resolve conflicts in narrow bidirectional corridors, while Corridor eXtension also covers deadlocks that arise outside corridor boundaries because roadmap segments vary in length and shape.The extended-corridor set is updated by comparing active AGV paths and applying the CX strategy to corridor sectors.
- 7 L-MAPF Coordinator: Because optimal coordination is NP-hard, the system targets real-time solutions in dense industrial environments rather than exact optimization.The complexity arises from combinatorial temporal interactions among multiple agents.
- 7 L-MAPF Coordinator: ABH-CBS uses best-first Constraint Tree search with anytime functionality, progressively refining bounded-horizon conflict-free trajectories toward optimality as computation time permits.The planner computes the lowest-cost solution found within the explored horizon together with its constraint set.
8 Path Allocator
The path allocator converts coordinator trajectories into short, mutually exclusive edge queues that can be executed safely despite continuous-time deviations. It limits allocation to a configurable horizon and communicates right-of-way through each AGV's local queue.
- 8 Path Allocator: Execution uncertainties can make nominally conflict-free trajectories unsafe, so the path allocator regulates roadmap access and enforces mutual exclusion during execution.It assigns edges, allocated trajectories, and target vertices from the coordinator output.
- 8 Path Allocator: Each AGV receives an ordered allocated queue from its current vertex to a target vertex, while the remaining path is reserved for later coordination.The queue determines the allocated trajectory and target vertex used by the next coordinator instance.
- 8 Path Allocator: A user-defined horizon ϵ stops allocation beyond ϵ timesteps, preventing unnecessarily long reservations and preserving responsiveness to updated information.The algorithm processes move and wait actions until the horizon, the goal vertex, or a detected collision stops analysis.
- 8 Path Allocator: An edge is added only when it does not collide with edges in another AGV's allocated queue; otherwise, processing of that trajectory stops.The allocator checks each candidate edge against the other queues' collision sets.
- 8 Path Allocator: Under VDA5050, the local queue grants right-of-way over its allocated edges, and the AGV reports its state while traversing them.Consumed edges are removed from the queue and corresponding trajectory as the AGV advances.
9 Deadlock Detector and Handler
The deadlock detector builds a precedence graph from coordinator constraints to identify cyclic and nested acyclic deadlocks. A handler replans involved AGVs with CBS, but highly constrained layouts may still require manual repositioning.
- 9 Deadlock Detector and Handler: The system detects deadlocks caused by task updates or insufficient bounded horizons, covering both cyclic dependencies and nested acyclic dependencies.The two scenarios are illustrated as circular and nested acyclic structures among AGVs.
- 9 Deadlock Detector and Handler: The detector constructs a precedence graph whose vertices are active AGVs and whose edges represent immediate precedence relations derived from the coordinator's constraint set.This graph captures the current instance rather than the full temporal evolution of the system.
- 9 Deadlock Detector and Handler: DFS identifies AGVs in precedence cycles, while recursive edge analysis adds AGVs nested behind cyclically blocked vehicles to the resolution set.The acyclic procedure finds edges from nodes outside the cyclic set into nodes inside it.
- 9 Deadlock Detector and Handler: CBS recomputes paths for the involved AGVs and updates their paths, path subgraphs, and extended corridors before the next coordination instance.CBS completeness guarantees recovery when a feasible conflict-free trajectory set exists for the involved AGVs.
- 9 Deadlock Detector and Handler: Rare failures remain possible when the directed roadmap provides no feasible detour or backtracking maneuver, requiring operators to switch affected AGVs to manual mode.This boundary occurs in highly constrained plant areas where reconfiguration segments are unavailable.
10 Case Study
The case study evaluates the proposed traffic-management system across realistic layouts, varying fleet density, allocation horizons, algorithmic components, and competing coordination methods. Results show strong throughput and deadlock-handling performance, especially in constrained layouts with narrow corridors.
- Scalability Analysis: Throughput increases with fleet size until layout-specific congestion thresholds, after which waiting, flow time, and coordination complexity reduce further productivity.The throughput-maximizing reference configurations are 1.B, 2.C, and 3.C for Layouts 1, 2, and 3, respectively.
- Scalability Analysis: Deadlocks become more frequent as fleets grow, but the detector and resolver observe no undetected deadlocks and resolve most events.In the most overloaded scenarios, the resolved fraction falls to 75-85% because some involved AGVs lack feasible recovery motions.
- Scalability Analysis: The full coordinator preserves high valid-solution rates under dense traffic, although ABH-CBS average TW decreases as more computation is devoted to imminent conflicts.This supports real-time robustness while revealing the computational pressure created by larger fleets.
- Sensitivity Analysis: Allocation horizon ϵ = 6 is the most balanced choice for Layouts 1 and 2, while ϵ = 10 degrades their operational KPIs despite increasing average TW.Longer reservations reduce flexibility when execution uncertainties keep roadmap segments unavailable; Layout 3 is largely insensitive to ϵ.
- Ablation Study: Disabling anytime refinement reduces throughput by 3% in 1.B.d and 4% in 2.C.d, while disabling both anytime refinement and EHC reduces throughput by about 12% in 1.B.e and 15% in 2.C.e.The degradation is concentrated in narrow, non-standardized layouts where delayed conflict detection causes corridor deadlocks; Layout 3 is largely unaffected.
- Comparative Evaluation: The proposed traffic manager improves throughput by approximately 10%, 7%, and 6% over rule-based, state-of-the-art, and priority-based methods in Layout 1, respectively.Its advantage is attributed to flexible search-based conflict resolution and explicit deadlock handling in spatially constrained regions.
11 Conclusions and Outlooks
The paper presents an integrated architecture for high-density AGV traffic management in complex industrial environments, combining L-MAPF coordination, safe execution, and deadlock resolution. Validation reports throughput improvements of up to 11% while retaining real-time performance, and future work targets adaptive routing and proactive coordination.
- Up to 11% throughput improvement was demonstrated against rule-based, industrial, and alternative L-MAPF methods in non-standardized settings.The evaluation involved large and heterogeneous AGVs operating on roadmaps in real-world layouts.
- The architecture combines L-MAPF coordination, VDA5050-compliant path allocation, and enhanced CBS-based real-time deadlock resolution.
- Future work will relax fixed task-assigned paths through adaptive path adjustment and online replanning around obstacles.The stated aim is to alleviate congestion, reduce conflicts, and avoid prolonged waiting.
- Further extensions include proactive deadlock prevention, integrated task assignment and coordination, and learning-based strategies for larger uncertain environments.
15 ORCID iDs
The section lists the authors’ ORCID identifiers.
- The paper identifies Alessandro Bonetti, Silvia Proia, Simone Guidetti, and Lorenzo Sabattini with ORCID identifiers.
A Low-Level Planner
The low-level planner uses space-time A* to construct an AGV trajectory under high-level constraints and static or dynamic obstacle checks. It expands candidate moves or waits, rejects unsafe actions, and reconstructs a feasible trajectory when the goal is reached.
- The planner initializes OPEN, CLOSED, and traceback structures, then expands the lowest-cost node until reaching the goal or exhausting candidates.
- When the goal is reached, traceback reconstructs the trajectory by backtracking from the goal vertex.
- Candidate move or wait actions are checked against the constraint set before collision checks with static and dynamic obstacles.
- Space-time collision checking tests overlapping action intervals and whether another AGV’s vertex or edge lies in the relevant collision set.
- Space-time A* returns an AGV trajectory compliant with high-level constraints and static or dynamic obstacles, or an empty sequence if none exists.
AGV Model
The AGV model defines the fleet, charging infrastructure, active vehicles, vehicle classes, footprints, and kinematic constraints used by the system.
- The model includes the number of AGVs, battery chargers, active AGVs, and AGV classes.
- Each AGV class is represented by a convex polygonal footprint and kinematic constraints.
Environment Model
The environment model represents AGV navigation through layered roadmap and topological graphs, with paths, trajectories, obstacles, corridors, queues, and deadlock states encoded as formal sets and costs.
- The roadmap layer models locations and directed segments as vertices and edges, with traversal time and duration assigned to each edge.
- Additional notation defines path subgraphs, graph elements, iteration indices, and root, parent, child, and optimal values for algorithmic processing.
- AGV routes connect starting, goal, and next-goal vertices through a main path and an extension path.
- Path evaluation uses length, total traversal cost, trajectory actions, target vertices, target timesteps, and a sum-of-costs objective.
- The model captures static and dynamic obstacles, including obstructed edges, and represents extended corridors as a distinct set.
- Operational coordination includes allocated queues and trajectories, while deadlock handling tracks the AGVs involved in a deadlock.