Conflict-Free Path Planning For Multi-AGVs in Automated Terminals Considering Road Load Balancing

doi:10.12141/j.issn.1000-565X.230227

Abstract

Abstract:

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.

Key words: automated container terminal, path planning, conflict avoidance, road load balancing, A* algorithm

CLC Number:

U691

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 Edition), 2023, 51(10): 1-10.

Figures/Tables 17

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Fig.6

Fig.7

Table 1

Table 2

Fig.8

Fig.9

Table 3

Table 4

Fig.10

Table 5

Fig.11

Fig.12

References 26

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.

作业点	Y₁	Y₂	Y₃	Y₄	Y₅
坐标	（14，6）	（14，6）	（14，16）	（14，26）	（14，26）
作业点	Y₆	Y₇	Y₈	Y₉
坐标	（14，36）	（14，46）	（14，51）	（14，56）

车辆数	C/时间步		冲突数/个		C偏差/%
车辆数	CBS	IPF	CBS	IPF	C偏差/%
9	293	292	0	2	0.34
10	335	334	0	3	0.30
11	361	359	0	2	0.56
12	390	388	0	4	0.52
13	406	405	0	3	0.25
14	439	436	0	5	0.69
15	473	471	0	4	0.42
16	496	493	0	6	0.61
17	598	594	0	8	0.67
18	613	608	0	10	0.82

车辆数	C/时间步		C偏差/%
车辆数	算法1	算法2	C偏差/%
9	1 458	1 450	0.55
10	1 677	1 669	0.48
11	1 854	1 851	0.16
12	2 046	2 045	0.05
13	2 149	2 151	0.09
14	2 350	2 349	0.04
15	2 564	2 563	0.04
16	2 688	2 679	0.33
17	2 917	2 917	0.00
18	3 074	3 070	0.13

车辆数	C/时间步		C偏差/%
车辆数	实验1	实验2	C偏差/%
9	1 454	1 454	0.00
10	1 669	1 671	0.12
11	1 851	1 851	0.00
12	2 045	2 046	0.05
13	2 145	2 151	0.28
14	2 349	2 354	0.21
15	2 562	2 563	0.04
16	2 679	2 682	0.11
17	2 917	2 923	0.21
18	3 070	3 073	0.10

[1]	ZHUANG Ling, LIU Yuhang. Research on Transmission Scheme Based on Reconfigurable Intelligent Surface in Dense Urban Agglomeration [J]. Journal of South China University of Technology(Natural Science Edition), 2024, 52(3): 112-118.
[2]	YAO Daojin, YIN Xiong, LUO Zhen, et al.. AGVS Path Planning Agorithm in Complex Environments [J]. Journal of South China University of Technology(Natural Science Edition), 2023, 51(11): 56-62.
[3]	CHEN Peng, JIANG Yongqi, YU Tianwei, et al. Quadrotor Trajectory Planning Method Based on Local Soft-Constrained Optimization [J]. Journal of South China University of Technology(Natural Science Edition), 2022, 50(6): 27-36.
[4]	WEI Wu, HAN Jin, LI Yanjie, et al. Path Planning of Mobile Robots Based on Dual-Tree Quick-RRT* Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(7): 51-58.
[5]	WEN Huiying, LIN Yifeng, WU Haoshu, et al. Extended Co-evolutionary Algorithm for Path Planning Based on the Urban Traffic Environment Evolution [J]. Journal of South China University of Technology (Natural Science Edition), 2021, 49(10): 1-10.
[6]	ZHANG Jiaxu, YANG Xiong, SHI Zhengtang, et al. Path Planning and Tracking Control for Emergency Lane Change and Obstacle Avoidance of Vehicles [J]. Journal of South China University of Technology (Natural Science Edition), 2020, 48(9): 86-93,106.
[7]	ZHAO Xing JI Kang LIN Hao XU Peng. Resource Allocation Model Based on Multi-objective Path Planning in Emergency Management [J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(4): 76-82.
[8]	HONG Xiaobin WEI Xinyong HUANG Yesheng LIU Yanxia XIAO Guoquan. Local Path Planning Method for Unmanned Surface Vehicle Based on Image Recognition and VFH + [J]. Journal of South China University of Technology(Natural Science Edition), 2019, 47(10): 24-33.
[9]	PAN Xiao-fang ZHOU Shun-ping YANG Lin WAN Bo. Origin Destination Constraint Experience Model of Taxi and Path Planning [J]. Journal of South China University of Technology (Natural Science Edition), 2017, 45(8): 57-64,83.
[10]	WU Yu-xiang WANG Chao. An Improved Three-Dimensional Path Planning Method of Mobile Robot [J]. Journal of South China University of Technology (Natural Science Edition), 2016, 44(9): 53-60.
[11]	Huang Miao- na Feng Sui- li Chen Jun Zhang Yong- zhong . Strategy of Avoiding Conflict Between MRO and MLB in LTE Self- Optimizing Networks [J]. Journal of South China University of Technology (Natural Science Edition), 2013, 41(11): 36-42.
[12]	Wang Fu-yuan Xu Jia-wen. Process and Key Technologies of NC Electrochemical Machining of Integral Impeller via Fractional-Step Method [J]. Journal of South China University of Technology (Natural Science Edition), 2010, 38(8): 72-77.
[13]	Zhao Dong Zheng Shi-xiong. Multi-Robot Collision Avoidance Algorithm Based on Generalized Potential Field [J]. Journal of South China University of Technology (Natural Science Edition), 2010, 38(1): 124-127.
[14]	Chen Huazhi Xie Cunxi Zeng Dehuai. Simulation of a Neural Network-based Path Planning Algorithm for Mobile Robot [J]. Journal of South China University of Technology(Natural Science Edition), 2003, 31(6): 56-59.