﻿ 多植保无人机协同路径规划
 文章快速检索 高级检索

1. 山东大学 机械工程学院 高效洁净机械制造教育部重点实验室, 济南 250061;
2. 山东大学 日照智能制造研究院, 日照 276800

Cooperative path planning for multi-sprayer-UAVs
KAN Ping1,2, JIANG Zhaoliang1,2, LIU Yuhao1,2, WANG Zhenwu1,2
1. Key Laboratory of High Efficiency and Clean Mechanical Manufacture, Ministry of Education, School of Mechanical Engineering, Shandong University, Ji'nan 250061, China;
2. Rizhao Intelligent Manufacturing Institute, Shandong University, Rizhao 276800, China
Abstract: In order to achieve collaborative work and improve operation efficiency of multi-sprayer-Unmanned Aerial Vehicles(UAVs), a cooperative path planning algorithm for multi-sprayer-UAVs based on the improved Particle Swarm Optimization(PSO) is proposed. Considering the working area's shape and size and the operating parameters of sprayer-UAV, the working area of each UAV is divided. The full coverage route in each area is generated by grid method. The operation distance during one trip of each sprayer-UAV is used as the algorithm optimization variable. Under the condition that the replenishment time of each UAV meets the interval distribution constraint, four factors of replenishment frequency, total replenishment time, total operation time and minimum replenishment interval are comprehensively considered, constituting the objective function. The improved PSO algorithm is applied to optimize the position of return points and return sequence of UAVs. The simulation results show that compared with the maximum operating distance planning and the minimum return distance planning, the proposed planning alqorithm show better performance and better operation area adaptability, which proved its effectiveness and practicability.
Keywords: path planning    multi-sprayer-Unmanned Aerial Vehicle(UAV)    supply point    Particle Swarm Optimization(PSO)    return points

1 简单路径规划方法 1.1 多植保无人机作业

 图 1 多植保无人机协同作业示例 Fig. 1 Instance of cooperative path planning for multi-sprayer-UAVs
1.2 最大作业距离规划和最小返航距离规划

 图 2 4架无人机规则作业区域下返航点分布图 Fig. 2 Distribution of return points of four UAVs under regular operation area
2 改进PSO算法 2.1 PSO算法描述

 ${\mathit{\boldsymbol{v}}_i}\left( t \right) = {\left[ {{v_{i1}}\left( t \right),{v_{i2}}\left( t \right), \cdots ,{v_{iD}}\left( t \right)} \right]^{\rm{T}}}$ （1）
 ${\mathit{\boldsymbol{x}}_i}\left( t \right) = {\left[ {{x_{i1}}\left( t \right),{x_{i2}}\left( t \right), \cdots ,{x_{iD}}\left( t \right)} \right]^{\rm{T}}}$ （2）

 $\begin{array}{l} {v_{ij}}\left( {t + 1} \right) = \omega {v_{ij}}\left( t \right) + {c_1}{r_1}\left( {{p_{ij}} - {x_{ij}}\left( t \right)} \right) + \\ \;\;\;\;\;{c_2}{r_2}\left( {{g_j} - {x_{ij}}\left( t \right)} \right) \end{array}$ （3）
 ${x_{ij}}\left( {t + 1} \right) = {x_{ij}}\left( t \right) + {v_{ij}}\left( {t + 1} \right)$ （4）

PSO算法具有易实现、收敛快、鲁棒性好等优点，但收敛效率低[17-18]。多年来，不少学者对PSO算法进行了各种改进。惯性权值是PSO算法中的一个重要参数，体现了粒子对之前速度的继承。文献[19]指出，前期全局搜索时取较大的惯性权值，有利于粒子跳出局部收敛；后期局部搜索时取较小的惯性权值，有利于粒子进行精细搜索，使得算法收敛。文献[20]提出了一种动态惯性权重PSO算法的迭代公式，其动态惯性权重随着迭代的增加而减小。PSO属于典型的智能优化算法，本文研究的多植保无人机协同路径规划问题属于多目标优化问题，变量为每架无人机各架次植保作业的飞行距离，目标为无人机的补给总次数、返航补给总时间、总耗时和最小补给时间间隔都尽量取小值，变量与目标函数之间不存在明显的线性关系，适于用智能优化算法求解。本文采用改进PSO算法，对惯性权值采用“阶梯式”调整策略，在迭代过程中，惯性权值阶梯式减小，有利于减少算法优化时间，并且有效兼顾算法全局搜索能力和精细搜索能力[21]

2.2 协同路径规划建模

1) 算法寻优变量为每架无人机各架次植保作业的飞行距离，表示为

 ${\mathit{\boldsymbol{X}}_{M \times n}} = \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {{\mathit{\boldsymbol{X}}_2}}\\ \vdots \\ {{\mathit{\boldsymbol{X}}_M}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {{x_{11}}}&{{x_{12}}}& \cdots &{{x_{1n}}}\\ {{x_{21}}}&{{x_{22}}}& \cdots &{{x_{2n}}}\\ \vdots & \vdots &{}& \vdots \\ {{x_{M1}}}&{{x_{M2}}}& \cdots &{{x_{Mn}}} \end{array}} \right]$ （5）

2) 在植保作业过程中，由于补给点需要为M架无人机进行补给，为减少电池更换次数，应尽量减少每架无人机的补给次数。作业区域面积固定导致植保作业时间一定，为提高效率，应尽量降低无人机返航补给时间消耗，同时应尽量使整个植保作业时间最短。补给时间间隔为上一架次无人机结束补给至下一架次无人机开始补给之间的时长。为降低作业时间偏差对整个作业过程带来的影响，应使作业过程中的最小补给时间间隔尽量大。考虑到以上因素，构建包含以上各要素的目标函数，表示为

 $\min G = {\omega _1}{z_1}\sum\limits_{i = 1}^M {{C_i}} + {\omega _2}{z_2}\sum\limits_{i = 1}^M {{L_i}} + {\omega _3}{z_3}T + {\omega _4}{t_{\min }}$ （6）

3) 各架次无人机返航飞行时间为

 $\begin{array}{l} {f_{ij}} = \frac{{2\left| {{P_{ij}},{P_0}} \right|}}{{{v_{{\rm{max}}}}}} + {t_i}\\ \;\;\;\;\;\;i = 1,2, \cdots ,M;j = 1,2, \cdots \end{array}$ （7）

4) 补给过程包括药剂装填和电池更换，单次补给需要的总时间为tr。多架无人机在协同作业时，由于补给点在同一时刻只能满足一架无人机进行补给，因而同一时刻仅允许一架无人机处于补给状态。为便于补给时间间隔分布，开始作业时各植保无人机依次延时起航，延时时间为td。处于两边作业的无人机距补给点相对较远，应先起航进行作业，位于中间作业的无人机后起航作业。初始起航点位于补给点附近。

5) 设各架无人机补给时间中点时刻按时间先后顺序构成向量α =[α1α2，…，αk]。为确保各架无人机补给时间间隔分布，应满足

 ${\alpha _{i + 1}} - {\alpha _i} \ge {t_{\rm{r}}} + {t_{\rm{s}}}\;\;\;\;\;1 \le i \le k - 1$ （8）

 图 3 多植保无人机协同路径规划流程 Fig. 3 Flowchart of cooperative path planning for multi-sprayer-UAVs
3 仿真分析

3.1 全覆盖作业航线生成

 图 4 规则作业区域全覆盖植保航线生成 Fig. 4 Full coverage route generation in regular operation area

 图 5 非规则作业区域全覆盖植保航线生成 Fig. 5 Full coverage route generation in irregular operation area
3.2 4架无人机规则作业区域下最大作业和最小返航距离规划仿真

 图 6 规则作业区域下最大作业距离规划仿真结果 Fig. 6 Simulation results of maximum operating distance planning under regular operation area

 图 7 规则作业区域下最小返航距离规划仿真结果 Fig. 7 Simulation results of minimum return distance planning under regular operation area
3.3 改进POS算法规划仿真 3.3.1 4架无人机规则作业区域下规划仿真

 $\begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {{\mathit{\boldsymbol{X}}_2}}\\ {{\mathit{\boldsymbol{X}}_3}}\\ {{\mathit{\boldsymbol{X}}_4}} \end{array}} \right] = \\ \;\;\;\;\;\;\;\left[ {\begin{array}{*{20}{c}} {2106}&{2874}&{2147}&{2880}&{2880}&{2113}\\ {2870}&{2217}&{2880}&{2831}&{2238}&{1964}\\ {2880}&{2235}&{2876}&{2853}&{2188}&{1968}\\ {2144}&{2850}&{2880}&{2223}&{2859}&{2044} \end{array}} \right] \end{array}$ （9）
 图 8 4架无人机规则作业区域下路径规划 Fig. 8 Path planning of four UAVs under regular operation area
 图 9 规则作业区域下改进PSO算法规划仿真结果 Fig. 9 Simulation results of improved PSO algorithm under regular operation area
3.3.2 4架无人机非规则边界作业区域下规划仿真

 $\begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {{\mathit{\boldsymbol{X}}_2}}\\ {{\mathit{\boldsymbol{X}}_3}}\\ {{\mathit{\boldsymbol{X}}_4}} \end{array}} \right] = \\ \;\;\;\;\;\;\;\left[ {\begin{array}{*{20}{c}} {2258}&{2671}&{2627}&{2572}&{2687}&{1009}\\ {2142}&{2513}&{2160}&{2865}&{2873}&{2123}\\ {2028}&{2874}&{2260}&{2833}&{2858}&{2147}\\ {2180}&{2501}&{2320}&{2823}&{2258}&{1918} \end{array}} \right] \end{array}$ （10）
 图 10 4架无人机非规则作业区域下路径规划 Fig. 10 Path planning of four UAVs under irregular operation area

 图 11 4架无人机非规则作业区域下返航点分布 Fig. 11 Distribution of return points of four UAVs under irregular operation area
3.3.3 2架和3架无人机路径规划仿真

 $\left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {{\mathit{\boldsymbol{X}}_2}} \end{array}} \right] = \left[ {\begin{array}{*{20}{c}} {2880}&{2142}&{2113}&{2874}&{2880}&{2095}&{2149}&{2880}&{2880}&{2178}&{2880}&{2049}\\ {2880}&{2229}&{2879}&{2861}&{2139}&{2180}&{2878}&{2880}&{2049}&{2081}&{2880}&{2064} \end{array}} \right]$ （11）
 图 12 2架无人机返航点分布 Fig. 12 Distribution of return points of two UAVs
 图 13 2架无人机路径规划 Fig. 13 Path planning of two UAVs

 $\begin{array}{l} \left[ {\begin{array}{*{20}{c}} {{\mathit{\boldsymbol{X}}_1}}\\ {{\mathit{\boldsymbol{X}}_2}}\\ {{\mathit{\boldsymbol{X}}_3}} \end{array}} \right] = \\ \left[ {\begin{array}{*{20}{c}} {2079}&{2827}&{2234}&{2875}&{2878}&{2154}&{2874}&{2079}\\ {2880}&{2242}&{2880}&{2876}&{2226}&{2880}&{2880}&{1136}\\ {2848}&{2247}&{2827}&{2228}&{2758}&{2181}&{2869}&{2042} \end{array}} \right] \end{array}$ （12）
 图 14 3架无人机路径规划 Fig. 14 Path planning of three UAVs

 图 15 3架无人机返航点分布 Fig. 15 Distribution of return points of three UAVs
4 结果分析

 作业区域 参数 改进PSO规划 最大作业距离规划 最小返航距离规划 规则 总返航点数量 20 20 28 返航补给总时间/s 1870 2949 2215 总耗时/s 4638 4919 4691 最小补给时间间隔/s 70.0 59.1 6.8 不规则 总返航点数量 20 18 返航补给总时间/s 1968 2340 总耗时/s 4406 4595 最小补给时间间隔/s 64.2 37.1

 无人机架数 参数 改进PSO规划 最大作业距离规划 最小返航距离规划 2 总返航点数量 22 20 28 返航补给总时间/s 1958 2513 2159 总耗时/s 8788 9066 8876 最小补给时间间隔/s 214.8 207.6 125.0 3 总返航点数量 21 18 27 返航补给总时间/s 1977 2635 2150 总耗时/s 6009 6256 6106 最小补给时间间隔/s 124.9 105.5 55.2

5 结论

1) 针对单架植保无人机作业效率有限的情况，对多植保无人机协同作业问题进行了研究，基于改进PSO算法，提出了一种多植保无人机协同路径规划解决方案，实现了对各无人机返航顺序和返航点位置的寻优。

2) 本文提出的基于改进PSO算法的多植保无人机协同路径规划算法较好地综合了最大作业距离规划和最小返航距离规划的优点，并较好地克服了二者的缺点，表现出了较优的性能，且对作业区域有更好的适应性，具有一定的实用价值。

 [1] ZHAO Y, ZHENG Z, YANG L. Survey on computational-intelligence-based UAV path planning[J]. Knowledge-Based Systems, 2018, 158: 54-64. Click to display the text [2] MINAEIAN S, JIAN L, SON Y J. Vision-based target detection and localization via a team of cooperative UAV and UGVs[J]. IEEE Transactions on Systems Man&Cybernetics Systems, 2017, 46(7): 1005-1016. [3] CONESA-MU OZ J, PAJARES G, RIBEIRO A. Mix-opt:A new route operator for optimal coverage path planning for a fleet in an agricultural environment[J]. Expert Systems with Applications, 2016, 54: 364-378. Click to display the text [4] BEN-GHORBEL M, RODRIGUEZ-DUARTE D, GHAZZAI H, et al. Joint position and travel path optimization for energy efficient wireless data gathering using unmanned aerial vehicles[J]. IEEE Transactions on Vehicular Technology, 2019, 68(3): 2165-2175. Click to display the text [5] PRIMICERIO J, FIORILLO E, GENESIO L, et al. A flexible unmanned aerial vehicle for precision agriculture[J]. Precision Agriculture, 2012, 13(4): 517-523. Click to display the text [6] 刘鑫, 杨霄鹏, 刘雨帆, 等. 基于GA-OCPA学习系统的无人机路径规划方法[J]. 航空学报, 2017, 38(11): 321275. LIU X, YANG X P, LIU Y F, et al. UAV path planning based on GA-OCPA learning system[J]. Acta Aeronautica et Astronautica Sinica, 2017, 38(11): 321275. (in Chinese) Cited By in Cnki | Click to display the text [7] LIN Y, SARIPALLI S. Sampling-based path planning for UAV collision avoidance[J]. IEEE Transactions on Intelligent Transportation Systems, 2017, 18(11): 1-14. Click to display the text [8] 周志艳, 臧英, 罗锡文, 等. 中国农业航空植保产业技术创新发展战略[J]. 农业工程学报, 2013, 29(24): 1-10. ZHOU Z Y, ZANG Y, LUO X W, et al. Technology innovation development strategy on agricultural aviation industry for plant protection in China[J]. Transactions of the Chinese Society of Agricultural Engineering, 2013, 29(24): 1-10. (in Chinese) Cited By in Cnki (107) | Click to display the text [9] 娄尚易, 薛新宇, 顾伟, 等. 农用植保无人机的研究现状及趋势[J]. 农机化研究, 2017, 39(12): 1-6, 31. LOU S Y, XUE X Y, GU W, et al. Current status and trends of agricultural plant protection unmanned aerial vehicle[J]. Journal of Agricultural Mechanization Research, 2017, 39(12): 1-6, 31. (in Chinese) Cited By in Cnki (18) | Click to display the text [10] 陈海, 何开锋, 钱炜祺. 多无人机协同覆盖路径规划[J]. 航空学报, 2016, 37(3): 928-935. CHEN H, HE K F, QIAN W Q. Cooperative coverage path planning for multiple UAVs[J]. Acta Aeronautica et Astronautica Sinica, 2016, 37(3): 928-935. (in Chinese) Cited By in Cnki | Click to display the text [11] 徐博.植保无人机航线规划方法研究[D].北京: 中国农业大学, 2017. XU B. Research on route planning for plant protection unmanned aerial vehicles[D]. Beijing: China Agricultural University, 2017(in Chinese). Cited By in Cnki | Click to display the text [12] 徐博, 陈立平, 谭彧, 等. 多架次作业植保无人机最小能耗航迹规划算法研究[J]. 农业机械学报, 2015, 46(11): 36-42. XU B, CHEN L P, TAN Y, et al. Path planning based on minimum energy consumption for plant protection UAVs in sorties[J]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(11): 36-42. (in Chinese) Cited By in Cnki | Click to display the text [13] 王宇, 陈海涛, 李煜, 等. 基于Grid-GSA算法的植保无人机路径规划方法[J]. 农业机械学报, 2017, 48(7): 29-37. WANG Y, CHEN H T, LI Y, et al. Path planning method based on Grid-GSA for plant protection UAV[J]. Transactions of the Chinese Society for Agricultural Machinery, 2017, 48(7): 29-37. (in Chinese) Cited By in Cnki | Click to display the text [14] 董胜, 袁朝辉, 谷超, 等. 基于多学科技术融合的智能农机控制平台研究综述[J]. 农业工程学报, 2017, 33(8): 1-11. DONG S, YUAN Z H, GU C, et al. Research on intelligent agricultural machinery control platform based on multi-discipline technology integration[J]. Transactions of the Chinese Society of Agricultural Engineering, 2017, 33(8): 1-11. (in Chinese) Cited By in Cnki | Click to display the text [15] KENNEDY J, EBERHART R. Particle swarm optimization[C]//International Conference on Neural Networks. Piscataway, NJ: IEEE Press, 1995: 1942-1948. [16] EBERHART R, KENNEDY J. A new optimizer using particle swarm theory[C]//Proceedings of the Sixth International Symposium on Micro Machine and Human Science. Piscataway, NJ: IEEE Press, 1995: 39-43. [17] 杨维, 李歧强. 粒子群优化算法综述[J]. 中国工程科学, 2004, 6(5): 87-94. YANG W, LI Q Q. Survey on particle swarm optimization algorithm[J]. Strategic Study of CAE, 2004, 6(5): 87-94. (in Chinese) Cited By in Cnki | Click to display the text [18] ESMIN A A A, COELHO R A, MATWIN S. A review on particle swarm optimization algorithm and its variants to clustering high-dimensional data[J]. Artificial Intelligence Review, 2015, 44(1): 23-45. Click to display the text [19] SHI Y H, EBERHART R. Monitoring of particle swarm optimization[J]. Frontiers of Computer Science, 2009, 3(1): 31-37. Click to display the text [20] JIAO B, LIAN Z, GU X. A dynamic inertia weight particle swarm optimization algorithm[J]. Chaos Solitons&Fractals, 2008, 37(3): 698-705. Click to display the text [21] 方群, 徐青. 基于改进粒子群算法的无人机三维航迹规划[J]. 西北工业大学学报, 2017, 35(1): 66-73. FANG Q, XU Q. 3D route planning for UAV based on improved PSO algorithm[J]. Journal of Northwestern Polytechnical University, 2017, 35(1): 66-73. (in Chinese) Cited By in Cnki | Click to display the text
http://dx.doi.org/10.7527/S1000-6893.2019.23610

0

文章信息

KAN Ping, JIANG Zhaoliang, LIU Yuhao, WANG Zhenwu

Cooperative path planning for multi-sprayer-UAVs

Acta Aeronautica et Astronautica Sinica, 2020, 41(4): 323610.
http://dx.doi.org/10.7527/S1000-6893.2019.23610