收稿日期: 2023-04-11
网络出版日期: 2023-06-21
基金资助
广东省自然科学基金资助项目(2023A1515011322)
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)
随着集装箱运输需求的日益增长以及新型信息技术的广泛应用,集装箱码头作业自动化成为国内外港口发展的主要趋势。集装箱码头作业自动化可有效提高码头的作业效率和安全性,降低码头对人力资源的需求和运营成本。水平运输系统是集装箱码头装卸系统的重要组成部分,同时也是实现集装箱在码头前沿与堆场之间运转的重要纽带,其运行的稳定性和调度的合理性将直接影响码头自动化装卸系统的运行效率。自动导引车(AGV)是自动化集装箱码头常用的水平运输设备,承担着从前沿岸桥到后方堆场的集装箱运输任务。在实际作业过程中,多辆AGV同时运作难免会发生冲突和拥堵。基于此,文中采用基于冲突搜索的双层算法(CBS算法)解决码头多AGV协同作业产生的冲突问题,上层算法搜索AGV间的冲突,下层算法采用A*算法对AGV进行路径规划,并在A*算法中引入负载因子,使得规划路径避开拥堵点,实现码头道路的负载均衡。对于码头多任务点连续作业场景下的多车路径规划,基于CBS算法采用一种滑动时间窗冲突解决方法(STWCR)以提升运算效率。通过仿真实验验证了文中所提算法能够有效解决码头多AGV路径规划的冲突问题,同时均衡路网负载,缓解道路局部拥堵现象,提高道路资源的利用率。研究成果为自动化集装箱码头水平运输系统优化提供了参考。
温惠英 , 元昱青 , 林译峰 . 考虑道路负载均衡的码头多AGV无冲突路径规划[J]. 华南理工大学学报(自然科学版), 2023 , 51(10) : 1 -10 . DOI: 10.12141/j.issn.1000-565X.230227
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.
| 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. |
/
| 〈 |
|
〉 |