Multi-AGV path planning method for the textile industry based on improved ant colony optimization algorithm and R-tree line-segment bilayer conflict detection Authors: Wei Xie, Xiangle Zheng, Jiachen Ma, Jun Chen, Bin Du, Xiaoli Wang, Reza Rostamzadeh, Reza Rostamzadeh, Reza Rostamzadeh Published: 2025 Abstract The Automated Guided Vehicle (AGV) is crucial for intelligent transportation in textile workshops. Existing centralized system planning research on multi-AGV conflict detection is still limited to simple node or line segment detection, making it difficult to meet the needs of large-scale simultaneous AGV operation to quickly detect whether a conflict exists. Aiming at this problem, this paper designs an R-tree Line-segment Bilayer Conflict Detection mechanism (RLBCD) for efficient collision detection among multi-AGVs by introducing R-tree indexing and analyzing AGV path characteristics, and proposes an Improved Ant Colony Optimization algorithm (IACO) to enhance the quality of AGV path planning, with time as the objective for multi-AGV priority and path strategy design, which ultimately results in collision-free path planning for multiple AGVs. By setting up multiple sets of experiments, it is proved that the RLBCD is not only able to identify the common types of AGV conflicts but also reduces the times of conflict detection comparisons by at least 88.2% and 78.1% compared to the Conflict Based Search and the Grid Time-window Conflict Detection algorithm; the proposed overall algorithm is 29.59 s faster and reduces the cumulative turning angle by 450° compared with the baseline multi-AGV path-planning algorithm, confirming its effectiveness. Introduction With the accelerated transformation of the textile industry to an intelligent production mode, the Automated Guided Vehicle (AGV), as the core carrier of the flexible logistics system, plays a key role in raw material conveying, semi-finished product transfer, and finished product sorting [1]. However, the textile workshop is generally characterized by a dense equipment layout and narrow channels, and multi-AGV operation is very easy to cause deadlock and efficiency loss due to path conflict, which is especially worse when the cluster scale is enlarged. Therefore, in multi-AGV operation collaboration, how to quickly identify whether there is a conflict between AGVs, how to resolve the conflict, and how to plan a collision-free path are the focus of current research by scholars [2]. Currently, there are two popular approaches in multi-AGV collision-free domain planning: a distributed reaction resolution approach, where AGVs dynamically resolve conflicts that arise during their movement towards the target location [3–6], and a centralized system planning approach, where collision-free paths are computed before AGVs start moving towards the target location. The research focus of this paper is on centralized system planning methods. Many centralized system solutions are currently popular, the Conflict Based Search (CBS) achieves collision-free planning via a two-level decomposition: at the lower level, optimal single-agent paths are computed independently without constraints from other agents; at the upper level, upon detecting spatiotemporal occupancy at the vertex or edge level, the corresponding spatiotemporal constraints are introduced and re-planning is triggered, thereby progressively eliminating conflicts [7–10]. CBS can find a globally optimal solution that minimizes the total path cost of all AGVs; however, its drawbacks are evident: because it must compare vertex and edge conflicts across agents, the upper-level branching on constraints and the lower-level re-planning grow increasingly expensive as the number of AGVs and the environmental complexity increase. In parallel to CBS, a line of work based on spatiotemporal networks/time-window search explicitly discretizes time and builds a time-expanded graph, internalizing collision-avoidance constraints into the network via capacity limits and forbidden edges, and then solves the problem using shortest-path or minimum-cost flow methods. This approach is highly verifiable but suffers from rapid state-space growth when the time granularity is fine, the task horizon is long, or the fleet size is large [11,12].Another strand emphasizes regional mutual exclusion: by imposing exclusive occupancy or reservation on bottleneck corridors and intersection areas to preclude passing encounters and concurrent conflicts, it offers a simple engineering implementation; its limitation is that poorly chosen interlock-region granularity induces a trade-off between conservatism and throughput [13,14]. In addition, some studies move conflict suppression upstream to the task-assignment stage by incorporating potential congestion or crossing risks into the cost function and constraints, yielding task–path matches with fewer anticipated conflicts before execution; the drawback is that performance depends on the fidelity of the risk characterization, and local geometric conflicts during operation typically still require online compensation [15]. Beyond the foregoing mature frameworks, another common remedy is to assign AGV priorities and confirm conflicts via a Grid-based Time-window Conflict Detection (GTCD) algorithm. Unlike CBS, GTCD emphasizes priority-based pre-screening: conflicts are detected directly by testing for spatiotemporal overlap on edges, without decomposing into vertex versus edge conflicts or constructing a constraint tree. Any overlap is deemed a conflict and is resolved at runtime through waiting or path re-planning. GTCD is often combined with heuristic path planners such as Particle Swarm Optimization (PSO) [16,17], Genetic Algorithm (GA) [18,19] and Ant Colony Optimization (ACO) [20,21].Guo et al. [22] introduced an ant fallback mechanism based on traditional ACO to enhance the adaptability and used a temporary avoidance-research strategy to solve the opposite conflict in AGV; Zhang et al. [23] incorporated the vehicle waiting time, the distance of the vehicle from the target point, and the urgency of the task performed by the trolley into the AGV priority consideration, which successfully circumvented various common conflict types of AGVs; Yang et al. [24] proposed elastic time window combined with ACO to improve the efficiency of multi-AGV path planning; Zhong et al. [25] used hybrid GA-PSO for AGV path planning in automated container terminal scenarios to achieve integrated scheduling of multi-AGV collision-free path planning; Pratissoli et al. [26] designed a hierarchical control architecture for multi-AGV path planning based on a time window to effectively reduce the occurrence of collision and deadlock processing accidents among multi-AGVs; Zhu et al. [27] proposed a New Ant Colony Optimization (NACO) algorithm that introduces an a priori time window to dynamically adjust the pheromone concentration, make the path time function the iterative goal of ant colony pheromone update, and add a strategy decision threshold in the path optimization process, which affects the accumulation of ant colony pheromone according to the severity of the conflict situation, so as to carry out the path replanning and waiting strategy selection. The above centralized system planning algorithms for multi-AGV conflict detection invariably utilize AGV shortest-path line segment or node information to facilitate conflict detection. However, as the AGV scale increases and the operational range expands, the delay in retrieving conflicts significantly increases. This has a detrimental effect on the algorithm’s real-time performance. Aiming at this problem, this paper designs an R-tree Line-segment Bilayer Conflict Detection mechanism (RLBCD) for efficient collision detection among multi-AGVs by introducing R-tree indexing and analyzing AGV path characteristics and proposes an Improved Ant Colony Optimization algorithm (IACO) on the basis of NACO [27], which ultimately results in a multi-AGV collision-free path planning method. First, IACO quantifies the path deflection angle into the time cost function by introducing a kinematic constrained turn time model, and amends the pheromone updating mechanism of NACO to improve the quality of AGV path planning; then IACO is run for the AGVs that start at the same time to obtain the optimal time cost of the initial path, and each AGV is prioritized through the before-and-after task assignment and the cost of the initial path, and then according to the priority and initial line segment run RLBCD algorithm, using AGV path characteristics coarse screening to quickly obtain the suspected conflict line segment area, fine screening to confirm whether the conflict really exists, to ensure the accuracy of conflict detection; if there is no conflict, the AGV to the initial optimal path driving. Otherwise, the initial path combines with the conflict detection situation to perform precise time waiting; the high-priority AGV’s minimum path segment is mapped as a dynamic obstacle, deeply integrating with IACO to enable collision-free path replanning for the low-priority AGVs. Finally, by measuring the cost of the waiting and path replanning strategy, the smaller time policy is selected to transition from single-AGV path planning to multiple-AGV path synergy, all aimed at prioritizing time. In extreme cases where no deconfliction strategy is feasible for a low-priority AGV at a given time, the algorithm applies a preemptive intervention: the task will be canceled at the current time instant and restarted in the planning for AGVs departing in the next time batch. This strategy is consistent with priority-ordered planning and serves as a feasibility prerequisite for collision-free multi-AGV operation. Overall, this study develops along the CBS framework, adopting a two-level decomposition of “first compute single-agent optima, then perform global deconfliction”: the lower level employs IACO, while the upper level implements deconfliction by combining priority assignments with an RLBCD mechanism. The contributions are summarized as follows: (i) Propose IACO to improve the path-planning quality of individual AGVs. (i) Propose IACO to improve the path-planning quality of individual AGVs. (ii) Leverage the priority scheme to map high-priority AGV paths into dynamic-obstacle regions for low-priority AGVs, tightly coupling IACO so that, through the pheromone-positive-feedback mechanism of ant colonies, optimal alternative paths under collision-free constraints are found automatically. (ii) Leverage the priority scheme to map high-priority AGV paths into dynamic-obstacle regions for low-priority AGVs, tightly coupling IACO so that, through the pheromone-positive-feedback mechanism of ant colonies, optimal alternative paths under collision-free constraints are found automatically. (iii) Introduce an RLBCD mechanism for rapid conflict detection across multiple AGV paths, enhancing detection efficiency while maintaining accuracy. (iii) Introduce an RLBCD mechanism for rapid conflict detection across multiple AGV paths, enhancing detection efficiency while maintaining accuracy. The subsequent chapters are arranged as follows. The “Materials and Methods” chapter describes the model assumptions of the algorithm proposed in this paper, the IACO algorithm formula used for single-AGV path planning, and the multi-AGV collision-free path planning algorithms: RLBCD mechanism design, waiting strategy implementation, dynamic obstacle generation, and path replanning. The “Experimental Results and Analysis” chapter initially delineates the experimental parameters of this paper’s overall algorithm. Subsequently, several experimental scenarios are constructed: (i) the proposed overall algorithm is evaluated on three common conflict types; (ii) RLBCD, CBS, and GTCD are run on six sets of AGV path instances with varying numbers of paths (i.e., fleet sizes) to compare conflict-detection counts and runtime; (iii) IACO is compared with ACO and NACO for single-AGV path planning; and (iv) end-to-end tests are conducted under simultaneous operation with fleets of different sizes to compare the proposed overall algorithm with a NACO-based multi-AGV path-planning algorithm. Finally, the “Conclusion” chapter summarizes the research of this paper. Materials and methods Model-based assumptions (i) To better reflect the realization of multi-AGV cooperative cooperation strategy, the textile workshop map unit grid division (Fig 1), black grid for the static obstacle area, reflecting the textile industry, a variety of raw materials and equipment of different sizes, not marching; white grid can be carried out in the region; red grid for the dynamic obstacle area, only in the special time is not permitted to enter; different AGV travel routes using different color markings; the solid line represents the final conflict-free path, the dotted line represents the original conflicting path, the small circle represents the AGV starting point, and the small square represents the AGV target end point, and the coordinates of each grid node are (x,y,t), the node set is N, and the connection between the nodes is represented by the edge set E. (i) To better reflect the realization of multi-AGV cooperative cooperation strategy, the textile workshop map unit grid division (Fig 1), black grid for the static obstacle area, reflecting the textile industry, a variety of raw materials and equipment of different sizes, not marching; white grid can be carried out in the region; red grid for the dynamic obstacle area, only in the special time is not permitted to enter; different AGV travel routes using different color markings; the solid line represents the final conflict-free path, the dotted line represents the original conflicting path, the small circle represents the AGV starting point, and the small square represents the AGV target end point, and the coordinates of each grid node are (x,y,t), the node set is N, and the connection between the nodes is represented by the edge set E. Textile workshop map. (ii) It is stipulated that the ant colony walks by moving with the center of each frame of the gridded map as the node target, and the movable directions are the eight domain directions. (ii) It is stipulated that the ant colony walks by moving with the center of each frame of the gridded map as the node target, and the movable directions are the eight domain directions. (iii) All AGVs run at the same speed in m/s, assuming that the acceleration during the start phase and the deceleration during the stop phase of the AGV are not taken into account. (iii) All AGVs run at the same speed in m/s, assuming that the acceleration during the start phase and the deceleration during the stop phase of the AGV are not taken into account. (iv) AGV can realize in-situ turning, the turning time with the turning angle is uniformly increasing, and the turning radius is zero. (iv) AGV can realize in-situ turning, the turning time with the turning angle is uniformly increasing, and the turning radius is zero. (v) Provided that all AGVs are of the same size and that the map is divided into the same size per grid length as the AGV size, ensuring that only one AGV can exist at a grid node location in m units. (v) Provided that all AGVs are of the same size and that the map is divided into the same size per grid length as the AGV size, ensuring that only one AGV can exist at a grid node location in m units. Single AGV path planning based on IACO State transfer probability. The probability pijk that ant k moves from node i to node j is defined as: α: parameters of pheromone importance α: parameters of pheromone importance β: parameters for the importance of heuristic information β: parameters for the importance of heuristic information Nkallowed: the set of ant k currently accessible neighboring nodes Nkallowed: the set of ant k currently accessible neighboring nodes τij: pheromone concentration from node i to node j τij: pheromone concentration from node i to node j ηij: heuristic information from node i to node j ηij: heuristic information from node i to node j Heuristic function. Euclidean distance is used as the heuristic function for the ACO algorithm. Euclidean distance: Heuristic function: Pheromone update time cost function Cpath: 1. Define the pheromone update time cost function Cpathk: 1. Define the pheromone update time cost function Cpathk: The traditional ant colony algorithm basically takes the shortest path as the basis of pheromone update, but for AGV planning paths, what should be considered is the time cost of the AGV actually arriving at the destination from the starting point, instead of the simple path length. The reason is that, for the AGV, turning time is costly, which literature [27] is also concerned about this situation and has introduced the concept of the time function to minimize the number of turns in the AGV driving process. AGV driving process of the number of turns, this approach to a certain extent played a role in the effect, but the disadvantage is that the scholar proposed turn time is not enough to fit with the actual, the loss of time between the turn angle is inconsistent, which to a certain extent affects the degree of Ant Colony Decision Making Path deflection, resulting in many large-angle turns appeared and the debugging of the algorithm process output not clear; we further improve the performance of the algorithm based on the consideration of the motion characteristics of the AGV; the cost of the turn time is subdivided, and the pheromone updating time cost function Cpathk is defined as the total time of the path taken by the ant k: tmove: total cost of straight time (s) tmove: total cost of straight time (s) tturn: total cost of turning time (s) tturn: total cost of turning time (s) Ltotal: total length of path (m) Ltotal: total length of path (m) v : constant speed of the AGV (m/s) v : constant speed of the AGV (m/s) tturn_unitIACO: turning time per unit angle (s/°) tturn_unitIACO: turning time per unit angle (s/°) θi: angle of the ith turn (∘) θi: angle of the ith turn (∘) 2. Calculation of turning angle θi: 2. Calculation of turning angle θi: In order to calculate the turning angle, it is necessary to determine the change of direction between three adjacent nodes in the path: Pi−1=(xi−1,yi−1): coordinates of the (i-1) node Pi−1=(xi−1,yi−1): coordinates of the (i-1) node Pi=(xi,yi): coordinates of the ith node Pi=(xi,yi): coordinates of the ith node Pi+1=(xi+1,yi+1): coordinates of the (i + 1) node Pi+1=(xi+1,yi+1): coordinates of the (i + 1) node Calculation of turning angle θi: 𝐯1·𝐯2: dot product of vectors 𝐯1·𝐯2: dot product of vectors ∥ ∥: modulus of a vector ∥ ∥: modulus of a vector Pheromone increment function Δτij: At the end of each iteration, after each ant completes the path search, the pheromone increment is updated according to the total cost of the path time Δτij: Cpathk(T): total path cost of ant k in Tth iteration Cpathk(T): total path cost of ant k in Tth iteration M: total number of ants M: total number of ants Q: pheromone intensity Q: pheromone intensity IACO algorithm pseudo-code The pseudo-code of the above IACO algorithm is as follows: Algorithm 1. Single AGV path planning based on IACO. Input: Set of start and end points for multiple AGVs Grid-based environment representation Set start and end node Output: Optimal path with minimum time cost 1: for T = 1 to MaxIterations do 2: Place M ants at the start node 3: for each ant do 4: while ant not at end node do 5: compute state transition probabilities, (ant k←pijk 6: determine θi using relative direction of neighboring three nodes 7: move to the next node 8: end while 9: calculate total time cost of the ant’s path, (ant k ← Cpathk(T)) 10: end for 11: for each edge (i,j) do 12: update pheromone based on time cost of all ants’ paths 13: perform pheromone evaporation 14: end for 15: end for 16: return Optimal path with minimum time cost over all iterations Multi-AGV path planning strategy AGV priority assignment mechanism. Since the single AGV path planning is using the IACO algorithm, the optimal time path of each AGV can be accurately obtained; for this reason, this paper proposes a time-first multi-AGV priority allocation mechanism on this basis, with the sequence of each AGV executing the task as the first priority judgment, i.e., the priority of AGVs that are already running will be higher than that of those that depart later, and if the AGVs are departing simultaneously, then run single AGV in parallel to IACO algorithm to determine the priority of the AGVs with the initial path cost; the smaller the time cost, the higher the priority, and if the priority is the same, then take a randomized priority ordering, so as to avoid the cycle as if waiting and falling into deadlock when multiple AGVs have conflicts. When an AGV task is canceled or encounters an accident, the priority bubbling mechanism is used to dynamically adjust the AGV task priority. Assume there are 2n AGVs dispatched at two time instants t1 and t2 (t1