复杂环境下AGVS路径规划算法

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

摘要/Abstract

摘要：

在仓储物流领域中，自动导向搬运车系统（AGVS）具有可靠性程度高、机动灵活等特点，但其工作环境复杂度的增加也提升了路径规划的难度。针对复杂环境下AGVS路径规划的低效且易冲突问题，文中提出了一种基于分层分布式框架的改进AGVS路径规划算法。首先，为提高算法在路径规划过程中的搜索效率，对传统A ^*算法的评价函数进行改进，并将双向Floyd算法与改进A ^*算法融合，以增加路径平滑度，最终得到AGVS全局最优路径；然后，建立AGVS运动学模型，将全局最优路径中关键节点作为临时目标点，通过调整机器人初始位姿、优化评价函数，在各临时目标点间使用DWA算法完成AGVS局部路径规划；最后，引入AGVS协同规划策略，通过对AGVS分配任务优先级实现AGVS间运动的统一调度，降低移动机器人之间发生冲突的概率，以提高AGVS路径规划算法的鲁棒性。Matlab仿真实验结果表明：提出的改进算法在简单环境和复杂环境下均可以生成AGVS无碰撞路径，在复杂环境下，文中改进算法规划的AGVS路径长度相比传统A ^*算法缩短2.26%；AGVS运动过程中，机器人线速度和角速度始终保持在0.6~1.2 m/s和-0.4~0.4 rad/s区域内，符合机器人运动学特性。

关键词: 移动机器人, 路径规划, 改进A ^*算法, DWA算法, 自动导向搬运车系统

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

中图分类号:

TP242.6

姚道金, 殷雄, 罗真, 等. 复杂环境下AGVS路径规划算法[J]. 华南理工大学学报(自然科学版), 2023, 51(11): 56-62.

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.

图/表 10

图1

图2

图3

图4

图5

表1

图6

图7

图8

图9

参考文献 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]	温惠英, 元昱青, 林译峰. 考虑道路负载均衡的码头多AGV无冲突路径规划[J]. 华南理工大学学报(自然科学版), 2023, 51(10): 1-10.
[2]	魏武, 韩进, 李艳杰, 等. 基于双树 Quick-RRT* 算法的移动机器人路径规划[J]. 华南理工大学学报（自然科学版）, 2021, 49(7): 51-58.
[3]	温惠英, 林译峰, 吴昊书, 等. 基于城市道路交通环境演变的 ECEA 路径规划算法[J]. 华南理工大学学报（自然科学版）, 2021, 49(10): 1-10.
[4]	张家旭, 杨雄, 施正堂, 等. 汽车紧急换道避障的路径规划与跟踪控制[J]. 华南理工大学学报（自然科学版）, 2020, 48(9): 86-93,106.
[5]	赵星吉康林灏徐鹏. 基于多目标路径规划的应急资源配置模型[J]. 华南理工大学学报(自然科学版), 2019, 47(4): 76-82.
[6]	洪晓斌魏新勇黄烨笙刘艳霞肖国权. 融合图像识别和 VFH + 的无人艇局部路径规划方法 [J]. 华南理工大学学报(自然科学版), 2019, 47(10): 24-33.
[7]	潘晓芳周顺平杨林万波. OD 约束的出租车经验模型与路径规划[J]. 华南理工大学学报（自然科学版）, 2017, 45(8): 57-64,83.
[8]	张好剑苏婷婷吴少泓郑军王云宽. 基于改进遗传算法的并联机器人分拣路径优化[J]. 华南理工大学学报（自然科学版）, 2017, 45(10): 93-99.
[9]	吴玉香王超. 一种改进的移动机器人三维路径规划方法[J]. 华南理工大学学报（自然科学版）, 2016, 44(9): 53-60.
[10]	周熙阳杨兆升张伟邴其春商强. 考虑信号交叉口转向类型的最优路径规划算法[J]. 华南理工大学学报（自然科学版）, 2016, 44(4): 101-108.
[11]	全思博李伟光郑少华. 基于 RGB-D 传感器的车间三维场景建模[J]. 华南理工大学学报（自然科学版）, 2015, 43(6): 42-47.
[12]	张铁陈伟华邹焱飚马琼雄. 移动机器人里程计系统误差的校正方法[J]. 华南理工大学学报（自然科学版）, 2014, 42(9): 7-11.
[13]	叶锦华李迪叶峰. 不确定轮式移动机器人的有限时间镇定控制[J]. 华南理工大学学报（自然科学版）, 2013, 41(8): 47-54.
[14]	李琳任俊霖邹焱飚陆州. 基于免疫遗传算法的移动机器人轨迹跟踪[J]. 华南理工大学学报（自然科学版）, 2013, 41(7): 13-18,25.
[15]	章权温惠英孙博. 适于配送车辆导航路径规划的遍历模型的改进型粒子群优化算法[J]. 华南理工大学学报（自然科学版）, 2011, 39(8): 109-112,117.