Journal of South China University of Technology(Natural Science) >
Conflict-Free Path Planning For Multi-AGVs in Automated Terminals Considering Road Load Balancing
Received date: 2023-04-11
Online published: 2023-06-21
Supported by
the Natural Science Foundation of Guangdong Province(2023A1515011322)
With the increasing demand for container transportation and the widespread application of new information technologies, the automation of container terminal operations has become the main development trend in domestic and international ports. It can not only effectively improve the efficiency and safety of terminal operations, but also significantly reduce the demand for human resources and the operational costs. The horizontal transportation system is an essential part of the container terminal handling system and an important link enabling the highly efficient container transportation between the quayside and the storage yard, so its operational reliability and the reasonableness of the scheduling directly affect the operational efficiency of the automated container handling system. The mostly used horizontal transportation equipment in container terminals is the automated guided vehicles (AGVs), which is responsible for horizontal transportation from the front quay crane to the rear yard in automated container terminals. In actual operation process, conflicts and congestion is inevitable when multiple AGVs operate simultaneously. On this basis, this paper used conflict-based search (CBS) to solve the conflict problem arising from the cooperative operation of multi-AGVs at the terminal. The upper layer algorithm searched for conflicts among AGVs, while the lower layer algorithm used the A* algorithm for path planning of AGVs. A load factor was introduced into the heuristic function of the A* algorithm in order to avoid congestion in the path planning and achieve load balancing on terminal roads. Further, a sliding time window conflict resolution (STWCR) based on CBS was adopted to improve computational efficiency for multiple AGVs path planning in the continuous operation scenario of multiple task points at the terminal. Simulation experiments verified that the proposed algorithm in this paper can effectively solve the conflict problem of multiple AGVs path planning at the terminal, while balancing the road network load, alleviating local road congestion, and improving the utilization of road resources. The research results of this paper provide a reference for the optimization of the horizontal transportation system in automated container terminals.
WEN Huiying , YUAN Yuqing , LIN Yifeng . Conflict-Free Path Planning For Multi-AGVs in Automated Terminals Considering Road Load Balancing[J]. Journal of South China University of Technology(Natural Science), 2023 , 51(10) : 1 -10 . DOI: 10.12141/j.issn.1000-565X.230227
| 1 | XIE S T, HU J Y, BHOWMICK P,et al .Distributed motion planning for safe autonomous vehicle overtaking via artificial potential field[J].IEEE Transactions on Intelligent Transportation Systems,2022,23(11):21531-21547. |
| 2 | HUANG Y, DING H, ZHANG Y,et al .A motion planning and tracking framework for autonomous vehicles based on artificial potential field elaborated resistance network approach[J].IEEE Transactions on Industrial Electronics,2019,67(2):1376-1386. |
| 3 | AZZABI A, NOURI K .An advanced potential field method proposed for mobile robot path planning[J].Transactions of the Institute of Measurement and Control,2019,41(11):3132-3144. |
| 4 | LIYUN X, NING W, XUFENG L .Study on conflict-free AGVs path planning strategy for workshop material distribution systems[J].Procedia CIRP,2021,104:1071-1076. |
| 5 | ZHONG M, YANG Y, DESSOUKY Y,et al .Multi-AGV scheduling for conflict-free path planning in automated container terminals[J].Computers & Industrial Engineering,2020,142:106371. |
| 6 | ZHOU Y, HUANG N .Airport AGV path optimization model based on ant colony algorithm to optimize Dijkstra algorithm in urban systems[J].Sustainable Computing:Informatics and Systems,2022,35:100716. |
| 7 | 许伦辉,曹宇超,林培群 .基于多影响因素RDMA~*算法的无人驾驶动态路径规划[J].交通信息与安全,2020,38(2):24-36. |
| XU Lunhui, CAO Yuchao, LIN Peiqun. Dynamic path planning for unmanned driving based on multi-influencing factors RDMA* algorithm[J].Journal of Transport Information and Safety,2020,38(2):24-36. | |
| 8 | WU M P, GAO J, LI L,et al .Control optimisation of automated guided vehicles in container terminal based on Petri network and dynamic path planning[J].Computers & Electrical Engineering,2022,104:108471. |
| 9 | YUE L, FAN H .Dynamic scheduling and path planning of automated guided vehicles in automatic container terminal[J].IEEE/CAA Journal of Automatica Sinica,2022,9(11):2005-2019. |
| 10 | 左秀峰,沈万杰 .基于Floyd算法的多重最短路问题的改进算法[J].计算机科学,2017,44(5):232-234,267. |
| ZUO Xiufeng, SHEN Wanjie .Improved algorithm about muti-shortest path problem based on floyd algorithm[J].Computer Science,2017,44(5):232-234,267. | |
| 11 | SINGGIH I K, HONG S, KIM K H .Flow path design for automated transport systems in container terminals considering traffic congestion [J].Industrial Engineering & Management Systems,2016,15(1):19-31. |
| 12 | MARTIN J, CASQUERO O, FORTES B,et al .A generic multi-layer architecture based on ROS-JADE integration for autonomous transport vehicles[J].Sensors,2018,19(1):69. |
| 13 | 高一鹭,胡志华 .基于时空网络的自动化集装箱码头自动化导引车路径规划[J].计算机应用,2020,40(7):2155-2163. |
| GAO Yilu, HU Zhihua .Path planning for automated guided vehicles based on tempo-spatial network at automated container terminal[J].Journal of Computer Applications,2020,40(7):2155-2163. | |
| 14 | LI Q, POGROMSKY A, ADRIAANSEN T,et al .A control of collision and deadlock avoidance for automated guided vehicles with a fault-tolerance capability[J].International Journal of Advanced Robotic Systems,2016,13(2):64. |
| 15 | 张素云,杨勇生,梁承姬,等 .自动化码头多AGV路径冲突的优化控制研究[J].交通运输系统工程与信息,2017,17(2):83-89. |
| ZHANG Suyun, YANG Yongsheng, LIANG Chengji,et al .Optimal control of multiple AGV path conflict in automated terminals[J].Journal of Transportation Systems Engineering and Information Technology,2017,17(2):83-89. | |
| 16 | 张中伟,张博晖,代争争,等 .基于动态优先级策略的多AGV无冲突路径规划[J].计算机应用研究,2021,38(7):2108-2111. |
| ZHANG Zhongwei, ZHANG Bohui, DAI Zhengzheng, et al. RMulti-AGV conflict-free path planning based on dynamic priority strategy [J]. Application Research of Computers,2021,38(7):2108-2111. | |
| 17 | LIANG C, ZHANG Y, DONG L. A three stage optimal scheduling algorithm for AGV route planning considering collision avoidance under speed control strategy[J].Mathematics,2022,11(1):138. |
| 18 | SMOLIC-ROCAK N, BOGDAN S, KOVACIC Z,et al .Time windows based dynamic routing in multi-AGV systems[J].IEEE Transactions on Automation Science and Engineering,2010,7(1):151-155. |
| 19 | 万千 .基于CBS算法的物流分拣多AGV路径规划的研究[D].哈尔滨:哈尔滨工业大学,2018. |
| 20 | GUO K, ZHU J, SHEN L .An improved acceleration method based on multi-agent system for AGVs conflict-free path planning in automated terminals[J].IEEE Access,2020,9:3326-3338 |
| 21 | 李静 .基于在线学习的自动化码头AGV调度方法研究[D].大连:大连理工大学,2018. |
| 22 | SHARON G, STERN R, GOLDENBERG M,et al .The increasing cost tree search for optimal multi-agent pathfinding[J].Artificial Intelligence,2013,195:470-495. |
| 23 | SHARON G, STERN R, FELNER A,et al .Conflict-based search for optimal multi-agent pathfinding[J].Artificial Intelligence,2015,219:40-66. |
| 24 | MA H, LI J Y, KUMAR T K S,et al .Lifelong multi-agent path finding for online pickup and delivery tasks [C]∥Proceedings of the 16th International Conference on Autonomous Agents and Multiagent Systems (AAMAS).Sao Paulo:ACM,2017:837-845 |
| 25 | HU Y, YANG H, HUANG Y .Conflict-free scheduling of large-scale multi-load AGVs in material transportation network[J].Transportation Research Part E:Logistics and Transportation Review,2022,158:102623. |
| 26 | 刘恒麟 .多AGV路径规划算法的研究与实现[D].南京:东南大学,2020. |
/
| 〈 |
|
〉 |