改进Theta*算法的物流无人机城域三维路径规划

doi:10.3778/j.issn.1002-8331.2205-0428

摘要/Abstract

摘要： 针对物流无人机城域配送路径规划问题，使用改进栅格法进行环境建模，设计路径安全代价函数提高路径安全性。为了解决Theta*算法在城市区域规划时路径海拔变化较大的问题，同时为减少路径节点数，提高路径平滑性，在算法实际代价函数中引入海拔变化代价及姿态调整代价；在算法搜索路径节点过程中，通过提出视线存在预设策略减少多余检查过程，提高算法搜索效率。与A*算法及Theta*算法对比验证了改进Theta*算法适用性。设计对照实验确定了目标函数权重及估价函数权重最优取值。在随机不同环境及真实环境下进行仿真，结果表明：相比于传统算法，改进Theta*算法规划路径的海拔变化、路径点数、规划时间及路径总代价均有较明显减少，证明了改进策略的有效性，在城域无人机路径规划方面有一定应用价值。

关键词: 三维路径规划, 物流无人机, 改进Theta*算法, 城市区域配送

Abstract: Aiming at the problem of urban regional distribution path planning of logistics UAV, the improved grid method is used to model the environment, and the cost function of path security is designed to improve the path security. In order to solve the problem that Theta* algorithm changes the altitude of the path greatly in urban regional planning, and to reduce the number of path nodes and improve the smoothness of the path, the altitude change cost and attitude adjustment cost are introduced into the actual cost function of the algorithm. In the process of searching path nodes, a preset strategy of line of sight is proposed to reduce the redundant checking process and improve the search efficiency of the algorithm. Compared with A* algorithm and Theta* algorithm, the applicability of the improved Theta* algorithm is verified. The optimal values of objective function weight and evaluation function weight are determined by design of control test. The simulation results in different random environments and real environments show that compared with the traditional algorithm, the altitude change, path number, planning time and total path cost of planned path of the improved Theta* algorithm are significantly reduced, which proves the effectiveness of the improved strategy and has certain application value in the UAV path planning in metropolitan.

Key words: 3D path planning, logistics unmanned aerial vehicle（UAV）, improved Theta* algorithm, urban area distribution

徐伟华, 聊士超, 张根瑞, 熊坚. 改进Theta*算法的物流无人机城域三维路径规划[J]. 计算机工程与应用, 2023, 59(17): 334-340.

XU Weihua, LIAO Shichao, ZHANG Genrui, XIONG Jian. 3D Path Planning of Logistics UAV Based on Improved Theta* Algorithm in Metropolitan Area[J]. Computer Engineering and Applications, 2023, 59(17): 334-340.

参考文献

[1] 闫超，涂良辉，王聿豪，等.无人机在我国民用领域应用综述[J].飞行力学，2022，40（3）：1-6.
YAN C，TU L H，WANG Y H，et al.Application of unmanned aerial vehicle in civil field in China[J].Flight Dynamics，2022，40（3）：1-6.
[2] 韩晓微，韩震，岳高峰，等.救灾无人机的优化A*航迹规划算法[J].计算机工程与应用，2021，57（6）：232-238.
HAN X W，HAN Z，YUE G F，et al.Path planning algorithm of disaster relief UAV based on optimized A*[J].Computer Engineering and Applications，2021，57（6）：232-238.
[3] 张启瑞，魏瑞轩，何仁珂，等.城市密集不规则障碍空间无人机航路规划[J].控制理论与应用，2015，32（10）：1407-1413.
ZHANG Q R，WEI R X，HE R K，et al.Path planning for unmanned aerial vehicle in urban space crowded with irregular obstacles[J].Control Theory & Applications，2015，32（10）：1407-1413.
[4] 成浩浩，杨森，齐晓慧.面向城市环境的四旋翼无人机在线避障航迹规划方法[J].计算机科学，2019，46（4）：241-246.
CHENG H H，YANG S，QI X H，et al.Online obstacle avoidance and path planning of quadrotor oriented to urban environment[J].Computer Science，2019，46（4）：241-246.
[5] 黄小毛，张垒，TANG L，等.复杂边界田块旋翼无人机自主作业路径规划[J].农业机械学报，2020，51（3）：34-42.
HUANG X M，ZHANG L，TANG L，et al.Path planning for autonomous operation of drone in fields with complex boundaries[J].Transactions of the Chinese Society for Agricultural Machinery，2020，51（3）：34-42.
[6] 王宇，王文浩，徐凡，等.基于改进蚁群算法的植保无人机路径规划方法[J].农业机械学报，2020，51（11）：103-112.
WANG Y，WANG W H，XU F，et al.Path planning approach based on improved ant colony optimization for sprayer UAV[J].Transactions of the Chinese Society for Agricultural Machinery，2020，51（11）：103-112.
[7] 唐立，郝鹏，张学军.基于改进蚁群算法的山区无人机路径规划方法[J].交通运输系统工程与信息，2019，19（1）：158-164.
TANG L，HAO P，ZHANG X J.An UAV path planning method in mountainous area based on an improved ant colony algorithm[J].Journal of Transportation Systems Engineering and Information Technology，2019，19（1）：158-164.
[8] 曹建秋，张广言，徐鹏.A*初始化的变异灰狼优化的无人机路径规划[J].计算机工程与应用，2022，58（4）：275-282.
CAO J Q，ZHANG G Y，XU P.A* initialized mutable gray wolf optimizer for UAV path planning[J].Computer Engineering and Applications，2022，58（4）：275-282.
[9] 郭一聪，刘小雄，章卫国，等.基于改进势场法的无人机三维路径规划方法[J].西北工业大学学报，2020，38（5）：977-986.
GUO Y C，LIU X X，ZHANG W G，et al.Three dimensional path planning method of UAV based on improved potential field method[J].Journal of Northwestern Polytechnical University，2020，38（5）：977-986.
[10] WANG H，YAN B J，LI X X，et al.On optimal path planning for UAV based patrolling in complex 3D topographies[C]//International Conference on Information & Automation，2017：986-990.
[11]   JEAUNEAU V，JOUANNEAU L，KOTENKOFF A.Path planner methods for UAVs in real environment[J].IFAC-PapersOnLine，2018，51（22）：292-297.
[12]   SONMEZ A，KOCYIGIT E，KUGU E.Optimal path planning for UAVs using genetic algorithm[C]//International Conference on Unmanned Aircraft Systems（ICUAS），2015：50-55.
[13] 张洪海，李翰，刘皞，等.城市区域物流无人机路径规划[J].交通运输系统工程与信息，2020，20（6）：22-29.
ZHANG H H，LI H，LIU H，et al.Path planning for logistics unmanned aerial vehicle in urban area[J].Journal of Transportation Systems Engineering and Information Technology，2020，20（6）：22-29.
[14] 谭雁英，李洋，周军，等.复杂环境下基于A*算法的无人机路径再规划[J].系统工程与电子技术，2017，39（6）：1268-1273.
TAN Y Y，LI Y，ZHOU J，et al.Path replanning approach for UAV based on A* algorithm in complex environment[J].Systems Engineering and Electronics，2017，39（6）：1268-1273.
[15] 张启钱，许卫卫，张洪海，等.复杂低空物流无人机路径规划[J].北京航空航天大学学报，2020，46（7）：1275-1286.
ZHANG Q Q，XU W W，ZHANG H H，et al.Path planning of complex low altitude logistics UAV[J].Journal of Beijing University of Aeronautics and Astronautics，2020，46（7）：1275-1286.
[16] NASH A，DANIEL K，KOENIG S，et al.Theta*：any-angle path planning on grids[C]//Proceedings of the AAAI，2007：1177-1183.
[17]   FILIPPIS L D，GUGLIERI G，QUAGLIOTTI F.Path planning strategies for UAVS in 3D environments[J].Journal of Intelligent & Robotic Systems，2012，65：247-264.
[18]   任天祥，贺建良，邹杰.基于改进Theta*算法的直升机三维航路规划[J].电光与控制，2022，29（2）：45-48.
REN T X，HE J L，ZOU J.3D route planning for helicopters based on improved Theta* algorithm[J].Electronics Optics ＆ Control，2022，29（2）：45-48.
[19] 东方，吴媚，朱文捷，等.物联网环境下面向能耗优化的无人机飞行规划[J].东南大学学报（自然科学版），2020，50（3）：555-562.
DONG F，WU M，ZHU W J，et al.Energy-efficient flight planning for UAV in IoT environment[J].Journal of Southeast University（Natural Science Edition），2020，50（3）：555-562.