物流无人机路径规划算法综述

文/李丹

引言

近年来，随着互联网网购的兴起，物流配送需求增加，但在配送末端环节由于其采用的是人工配送，并且交通拥堵情况日益严重，末端环节的配送成本一直以来居高不下，给物流配送行业带来很大压力。无人机凭借其便捷、快速的特性在物流配送领域占据一席之地，国内为大型的物流企业纷纷加入了无人机物流配送的竞争。路径规划技术是无人机配送研发的关键技术之一，关于路径优化的重点在于研究算法问题。经典智能算法包括粒子群优化算法[1]，蚂蚁聚类算法[2]。还有一些新型仿生智能的算法，如乌贼算法，果蝇算法广泛应用于分布式无人机群合作控制。目前，国内外学者针对算法问题从开展了大量研究，并且在基本算法上提出各种改进算法或者提出新的算法理论，本文将对目前主流的智能算法进行综述，重点介绍算法的基本原理、最新成果以及优缺点。在此基础上，对无人机配送路径规划算法未来的发展方向进行展望。本文根据物流无人机路径规划领域,选取了A*算法、粒子群算法、蚁群算法、遗传算法、果蝇算法、和乌贼算法等四种经典算法和两种新型仿生智能算法进行文献综述。主要介绍基本算法的概念和其存在的优缺点,并且列举了上述优化算法在无人机路径规划和其相关领域的最新研究成果，最后对无人机配送的路径规划算法的发展趋势进行了展望。

1.无人机路径规划

无人机路径规划是研究如何确定最可行的方法起点和终点之间的路径。这个问题是一个NP（Non-deterministic Polynomial）难题，因此可以根据相关约束条件将其建模并且采用算法求解转化为优化问题。主流的路径规划智能算法，大概可以分为两大类，一种是经典的智能算法，例如蚁群算法[3]、遗传算法[4]、A*算法[5]和粒子群算法[6]。另一种是新型仿生智能算法，例如乌贼算法，果蝇优化算法等。本文列举了在经典算法和新型仿生智能算法有代表性的几个算法来探讨。

1.1 经典算法。国内外许多学者在研究无人机配送三维路径规划的时候将其转换为二维问题，这些都可以用经典的智能算法来求解。在无人机配送路径规划的算法研究上使用较多的经典算法有遗传算法，蚁群算法和粒子群算法等。

1.1.1 遗传算法。1975年，Holland首次提出了遗传算法（genetic algorithm，GA）的概念。遗传算法的思路是由生物界优胜劣汰机制衍生出来的搜索算法。遗传算法的优点是它可以在搜索过程不断自适应调整方向以至于找到全局最优解为止。但由于无人机路径规划有着时间短并且对计算机资源要求较高的特性，采用遗传算法进行求解时会有早熟的现象，往往很难得到全局的最优解。一般用于参考路径规划，很难用于实时规划。由于传统的遗传算法用于无人机路径规划存在以上缺陷，一般都是将改进后的遗传算法或者将遗传算法与其他算法相结合用于无人机三维路径规划中。例如神经网络算法有着高效率和环境适应性好的特点，将其与遗传算法结合可以弥补其缺点。陈志军等[7]提出一种基于模糊神经网络和遗传算法，并建立了一种新的路径规划方法。

1.1.2 蚁群算法。蚁群算法（ant colony optimization,ACO）是意大利学者Dorigo由蚂蚁找寻食物产生的想法，是一种路径寻优的概率型算法。但传统的蚁群算法容易使路径规划求解陷入局部最优解中，因此许多学者在研究无人机配送路径规划问题时多数时候是将蚁群算法与其他算法相结合使用，目前比较常用的是将人工势场法与蚁群算法结合、A*算法与蚁群算法结合、栅格法与蚁群算法结合等。王刚等[8]在研究机器人的三维避障路径规划问题时，提出一种基于人工势场法的改进的蚁群算法，修改了蚁群算法的启发值参数，改变了算法的更新规则，使得改进后的蚁群算法能更快地收敛，找到最优解。

1.1.3 粒子群算法。粒子群优化算法（particle swarm optimization，PSO）最初由Kennedy和Eberhart提出，是一种基于鸟类种群捕食的启发式算法。粒子群优化算法有着容易陷入局部最优解和实时避障能力不足的缺陷，对在动态三维环境下，这些都是致命性的问题。由于蚁群算法收敛速度慢，而粒子群算法初期收敛速度太快，许多学者提出在改进的蚁群系统基础上融合粒子群算法。王闯等[9]提出了一种新的随机时滞粒子群优化算法，很好地解决了传统粒子群算法早期收敛速度快和局部寻优的缺点。

1.2 新型仿生智能算法。三维多无人机路径规划非常困难，因为不是只考虑二维平面问题，还得考虑空中环境和安全因素，并且无人机配送路径规划是动态的，传统的二维算法将不再适用。新型仿生智能算法在无人机路径规划中也运用较多。主要有乌贼算法，果蝇算法，鲸鱼算法，鸽群算法等。

1.2.1 乌贼算法。乌贼优化算法(Cuttlefish Optimization Algorithm，COA)由Adel Sabry Eesa等学者于2013年提出，灵感来源于海洋生物中乌贼，一种新型的仿生启发式优化算法，也是一种概率型算法。乌贼算法有着收敛速度快和时间短的优点，但缺点是收敛精度不高。乌贼算法是一种新型的启发式仿生智能优化算法，非常适合用于动态实时变化的路径规划问题。舒纬伟等[10]针对无人机路径规划问题，提出了一种基于乌贼算法求解问题。乌贼算法与经典的智能算法相比，其更收敛速度更快。

1.2.2 果蝇算法。果蝇优化算法(Fruit Fly Optimization Algorith，FFOA)由潘文超[11]于2011年提出，该算法的设计思路来源于自然界中果蝇的觅食行为，通过模拟果蝇的嗅觉和味觉的捕食过程尽快地找到目标点。果蝇算法是一种基于果蝇的觅食行为模拟出的寻找全局最优解的迭代搜索方法，因为该算法有着容易实现、设定参数少等特点受到了许多学者的青睐；然而基本的果蝇算法有着易于早熟、全局和局部寻优不平衡、解决多元复杂问题时会陷入局部最优等问题，许多学者将其用于三维路径规划时都会将其改进。根据以上几种算法的探讨，表1把这几种算法的优缺点，更新机制，适用问题等进行了归纳整理。

表1 算法对比

2.结论

随着对无人机路径规划算法研究的深入，需要明白在空中实时变化的动态环境下，如何选择合适的无人机路径规划智能算法及其实现，是完成无人机配送路径问题迫切需要解决的问题。蚁群算法在其概念是立体的较为接近三维的路径规划问题，但对存储空间的要求较高；遗传算法在路径规划方面的应用非常广泛，但由于无人机在飞行时的动态路径是不确定的，增加了算法的编码难度。因此，为有效利用各种算法各自的优势，混合算法将成为航迹规划的发展趋势。上述的新型仿生智能算法目前研究的学者还不多，也可能是未来的发展趋势。目前无人机三维航迹规划能在单一约束下快速生成航迹，但在复杂环境约束下缺少对最优路径的考虑，且无法同时兼顾复杂环境约束与无人机自身性能约束。

引用出处

[1]王翼虎,王思明.基于改进粒子群算法的无人机路径规划[J].计算机工程与科学,2020,42(9):1690-1696.

[2]李佳盛.基于改进蚁群算法的旅行商路径优化问题研究[J].中国物流与采购,2020,606(17):47-48.

[3]王宇,王文浩,徐凡,等.基于改进蚁群算法的植保无人机路径规划方法[J].农业机械学报,2020,51(11):92,103-112.

[4]李霞,魏瑞轩,周军,等.基于改进遗传算法的无人飞行器三维路径规划[J].西北工业大学学报,2010,28(3):343-348.

[5]李世国,苏卫华,郭鹏飞,等.基于改进A~★算法的无人搜救全局路径规划研究[J].医疗卫生装备,2020,41(12):16-20.

[6]杨超杰,裴以建,刘朋.改进粒子群算法的三维空间路径规划研究[J].计算机工程与应用,2019,55(11):117-122.

[7]陈志军,曾蒸.基于模糊神经网络和遗传算法的机器人三维路径规划[J].重庆师范大学学报(自然科学版),2018,35(1):93-99.

[8]王刚,张方,严大亮,等.基于改进蚁群算法的机器人三维路径规划[J].国外电子测量技术,2020,39(11):1-6.

[9]王闯,董宏丽,谷星澍,等.改进粒子群算法及其在航迹规划中的应用[J].控制工程,2019,26(8):1466-1471.

[10]舒纬伟,敬忠良,董鹏.基于乌贼算法的无人机航迹规划[J].科学技术与工程,2017,17(2):120-125.

[11]潘文超.应用果蝇优化算法优化广义回归神经网络进行企业经营绩效评估[J].太原理工大学学报(社会科学版),2011,29(4):1-5.