AGVS Path Planning Agorithm in Complex Environments

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

Abstract

Abstract:

In the field of warehousing and logistics, automatic guided truck system (AGVS) has the merits of high reliability and flexibility, but with the increase of the complexity of its working environment, the difficulty of path planning also increases. Aiming at the problem of low efficiency and easy conflict in AGVS path planning in complex environment, this paper proposed an improved AGVS path planning algorithm based on hierarchical distributed framework. Firstly, in order to improve the search efficiency of the algorithm in the path planning process, the evaluation function of the traditional A ^* algorithm was improved and fused with the bidirectional Floyd algorithm to increase the path smoothness, and the global optimal AGVS path is finally obtained. Secondly, the AGVS kinematics modeling was established, and the key nodes in the global optimal path were taken as temporary target points. By adjusting the initial poses of the robot and optimizing the evaluation function, the AGVS local path planning was completed appying the DWA algorithm to the temporary target points. Finally, AGVS collaborative planning strategy was introduced to achieve unified scheduling of inter-AGVS motion by assigning task priorities to AGVS, reducing the probability of conflicts between mobile machines, improving the robustness of AGVS path planning algorithm. Matlab simulation results show that the proposed improved algorithm can generate collision-free paths in both simple and complex environments. In complex environments, AGVS path length planned by the improved algorithm is shortened by 2.26% compared with that planned by the traditional A ^* algorithm. In the process of AGVS motion, the angular velocity and the linear velocity of the mobile robot are always maintained within -0.4~0.4 rad/s, and 0.6~1.2 m/s, which conforms to the kinematic characteristics of the mobile robot.

Key words: mobile robot, path planning, improved A ^* algorithm, DWA algorithm, automatic guided truck

CLC Number:

TP242.6

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.

Figures/Tables 10

Fig.1

Fig.2

Fig.3

Fig.4

Fig.5

Table 1

Fig.6

Fig.7

Fig.8

Fig.9

References 21

1	全燕鸣，何一明．多机器人任务分配调度的克隆选择算法［J］．华南理工大学学报（自然科学版）， 2021， 49（ 5）： 102- 110．
	QUAN Yanming， HE Yiming ． Research on clonal selection algorithm for multi-robot task allocation and scheduling［J］‍． Journal of South China University of Technology （Natural Science Edition）， 2021， 49（ 5）： 102- 110．
2	魏武，韩进，李艳杰，等．基于双树Quick-RRT ^*算法的移动机器人路径规划［J］．华南理工大学学报（自然科学版）， 2021， 49（ 7）： 51- 58．
	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．
3	XU R， YAO S ． Research on UGV path planning in tunnel based on the Dijkstra-PSO algorithm［C］∥ Proceedings of 2022 the 6th Asian Conference on Artificial Intelligence Technology． Changzhou： IEEE， 2022： 1- 9．
4	GUAN W， WANG K ． Autonomous collision avoidance of unmanned surface vehicles based on improved A-star and dynamic window approach algorithms［J］． IEEE Intelligent Transportation Systems Magazine， 2023， 15（ 3）： 36- 50．
5	DUAN Y， MA G， ZHU J， et al ． Research on robot path planning based on A*-weighted JPS algorithm［C］∥ Proceedings of 2021 IEEE International Conference on Recent Advances in Systems Science and Engineering． Shanghai： IEEE， 2021： 1- 7．
6	刘二根，谭茹涵，陈艺琳，等．基于改进人工蚁群的智能巡线机器人路径规划［J］．华东交通大学学报， 2020， 37（ 6）： 103- 107．
	LIU Ergen， TAN Ruhan， CHEN Yilin， et al ． Path planning of intelligent line inspection robot based on artificial ant colony［J］． Journal of East China Jiaotong University， 2020， 37（ 6）： 103- 107．
7	DUAN C， LI S ． Research on mobile robot path planning based on fuzzy artificial potential field algorithm［C］∥ Proceedings of 2023 IEEE International Conference on Control，Electronics and Computer Technology． Jilin： IEEE， 2023： 1408- 1413．
8	XUE Y， HENG Y， LU Q ． Robot path planning based on the improved grey wolf optimization algorithm［C］∥ Proceedings of 2022 Power System and Green Energy Conference． Shanghai： IEEE， 2022： 543- 547．
9	陈光友，余粟．改进A ^*的多机器人双层路径规划算法［J］．计算机工程与应用， 2023， 59（ 11）： 312- 319．
	CHEN Guangyou， YU Su ． Improved A ^* multi-robot bilevel path planning algorithm［J］． Computer Engineering and Applications， 2023， 59（ 11）： 312- 319．
10	史万庆，黄鸿柳，蒋林利．复杂环境下多机器人协同覆盖搜索路径规划［J］．电光与控制， 2022， 29（ 12）： 106- 111．
	SHI Wanqing， HUANG Hongliu， JIANG Linli ． Multi-robot path planning for collaborative full coverage search in complex environments［J］． Electronics Optics & Control， 2022， 29（ 12）： 106- 111．
11	陈南凯，王耀南，贾林．基于改进生物激励神经网络算法的多移动机器人协同变电站巡检作业［J］．控制与决策， 2022， 37（ 6）： 1453- 1459．
	CHEN Nan-kai， WANG Yao-nan， JIA Lin ． Multi-mobile robot cooperative inspection operation based on improved biological excitation neural network algorithm in substation［J］． Control and Decision， 2022， 37（ 6）： 1453- 1459．
12	张丹露，孙小勇，傅顺，等．智能仓库中的多机器人协同路径规划方法［J］．计算机集成制造系统， 2018， 24（ 2）： 410- 418．
	ZHANG Danlu， SUN Xiaoyong， FU Shun， et al ． Cooperative path planning in multi-robots for intelligent warehouse［J］． Computer Integrated Manufacturing Systems， 2018， 24（ 2）： 410- 418．
13	常路，单梁，戴跃伟，等．未知环境下基于改进DWA的多机器人编队控制［J］．控制与决策， 2022， 37（ 10）： 2524- 2534．
	CHANG Lu， SHAN Liang， DAI Yue-wei， et al ． Multi-robot formation control in unknown environment based on improved DWA［J］． Control and Decision， 2022， 37（ 10）： 2524- 2534．
14	孔国杰，冯时，于会龙，等．无人集群系统协同运动规划技术综述［J］．兵工学报， 2023， 44（ 1）： 11- 26．
	KONG Guojie， FENG Shi， YU Huilong， et al ． A review on collaborative motion planning of unmanned vehicles［J］． Acta Armamentarii， 2023， 44（ 1）： 11- 26．
15	陈海，何开锋，钱炜祺．多无人机协同覆盖路径规划［J］．航空学报， 2016， 37（ 3）： 928- 935．
	CHEN Hai， HE Kaifeng， QIAN Weiqi ． Cooperative coverage path planning for multiple UAVs［J］． Acta Aeronautica et Astronautica Sinica， 2016， 37（ 3）： 928- 935．
16	CHEN S， JI J， SU H， et al ． Improved A-star method for collision avoidance and path smoothing［C］∥ Proceedings of 2023 IEEE International Conference on Control，Electronics and Computer Technology． Jilin： IEEE， 2023： 32- 35．
17	石为人，王楷．基于Floyd算法的移动机器人最短路径规划研究［J］．仪器仪表学报， 2009， 30（ 10）： 2088- 2092．
	SHI Weiren， WANG Kai ． Floyd algorithm for the shor-test path planning of mobile robot［J］． Chinese Journal of Scientific Instrument， 2009， 30（ 10）： 2088- 2092．
18	KONG J， CHENG J ． Path planning of mobile robots based on the fusion of an improved A* algorithm and a dynamic window approach［C］∥ Proceedings of 2023 IEEE the 6th Information Technology，Networking，Electronic and Automation Control Conference． Chongqing： IEEE， 2023： 968- 973．
19	李薪颖，单梁，常路，等．复杂环境下基于多目标粒子群的DWA路径规划算法［J］．国防科技大学学报， 2022， 44（ 4）： 52- 59．
	LI Xinying， SHAN Liang， CHANG Lu， et al ． DWA path planning algorithm based on multi-objective particle swarm optimization in complex environment［J］． Journal of National University of Defense Technology， 2022， 44（ 4）： 52- 59．
20	周波，钱来，孟正大，等．基于改进遗传算法工业机器人多路径组合规划［J］．华中科技大学学报（自然科学版）， 2011，39（增刊Ⅱ）：9- 12．
	ZHOU Bo， QIAN Lai， MENG Zhengda， et al ． Multi-path integration planning of industrial robots based on an improved genetic algorithm［J］． Journal of Huazhong University of Science and Technology（Natural Science Edition）， 2011，39（Sup.Ⅱ）：9- 12．
21	赵文政，刘银华，金隼．面向多机器人协调运动规划的层级化任务分配方法［J］．计算机集成制造系统， 2021， 27（ 4）： 999- 1007．
	ZHAO Wenzheng， LIU Yinhua， JIN Sun ． Hierarchical task assignment algorithm for multi-robot coordinated path planning［J］． Computer Integrated Manufacturing Systems， 2021， 27（ 4）： 999- 1007．

算法	路径长度/m
算法	AGV1	AGV2	AGV3
传统A ^*算法	39.112 7	38.526 9	27.656 9
改进的A ^*算法	38.642 3	37.538 1	26.827 1

[1]	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.
[2]	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.
[3]	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.
[4]	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.
[5]	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.
[6]	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.
[7]	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.
[8]	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.
[9]	Quan Si-bo Li Wei-guang Zheng Shao-hua. Three-Dimension Modeling of Manufacturing Plant Scene Based on RGB-D Sensor [J]. Journal of South China University of Technology (Natural Science Edition), 2015, 43(6): 42-47.
[10]	Zhang Tie Chen Wei- hua Zou Yan- biao Ma Qiong- xiong. Calibration Method of Systematic Odometry Errors of Mobile Robot [J]. Journal of South China University of Technology (Natural Science Edition), 2014, 42(9): 7-11.
[11]	Ye Jin- hua Li Di Ye Feng. Finite- Time Stabilization Control of Uncertain Wheeled Mobile Robot [J]. Journal of South China University of Technology (Natural Science Edition), 2013, 41(8): 47-54.
[12]	Li Lin Ren Jun- lin Zou Yan- biao Lu Zhou. Trajectory Tracking of Mobile Robot Based on Immune Genetic Algorithm [J]. Journal of South China University of Technology (Natural Science Edition), 2013, 41(7): 13-18,25.
[13]	Luo Rong-hua Min Hua-qing. Hybrid Conditional Random Field for Multi-Object Tracking of Mobile Robot [J]. Journal of South China University of Technology (Natural Science Edition), 2011, 39(5): 61-67.
[14]	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.
[15]	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.