多作业区域植保无人机航线规划算法

徐 博 陈立平 徐 旻 谭 彧

(1.北京农业智能装备技术研究中心， 北京 100097； 2.中国农业大学工学院， 北京 100083；3.北京市农林科学院农业智能装备技术北京市重点实验室， 北京 100097)

多作业区域植保无人机航线规划算法

徐 博1,2陈立平1,3徐 旻1,3谭 彧2

(1.北京农业智能装备技术研究中心， 北京 100097； 2.中国农业大学工学院， 北京 100083；3.北京市农林科学院农业智能装备技术北京市重点实验室， 北京 100097)

针对植保施药多个作业区域的情况，研究了一种植保无人机全局航线规划算法，将整个算法分为单个区域航线规划、区域间作业顺序和区域间调度航线规划3部分。从作业路程、多余覆盖和遗漏覆盖的角度，分析了多种覆盖作业方式的优劣，确定了无人机在单区域内的覆盖方式。基于遗传算法与TSP问题得到区域间的优化作业顺序，并基于改进的二进制编码遗传算法进行区域间调度航线的规划，最终实现无人机多作业区域航线的全局规划。仿真结果表明，规划算法可以有效地实现全局航线的规划，缩短了无人机的作业距离与区域间调度飞行的距离，达到了能耗与工作时间的优化，节省了航线规划所需的人力成本，使作业管理更加便利。

植保无人机; 航线规划; 多区域作业; 算法

引言

病虫害是影响粮食安全的一个主要因素[1-2]，病虫害的防治是粮食生产不可或缺的重要环节[3]，我国的种植地形多种多样，既有平原的大面积种植区域，也有水田、丘陵等复杂地形[4-5]，对于后者，大型机械化防治很难实现，给病虫害防治带来了难题[6-7]。无人机具有作业灵活、起降无需跑道、地形适应性好、可悬停等特点[8]，可以适应丘陵、山区、坡地等复杂地形[9]，因此植保无人机已开始逐渐被运用在病虫害防治中[10-11]。植保无人机以小型旋翼无人机作为载体，搭载农药喷雾设备进行作业[12]，目前植保无人机的作业主要是人为遥控为主，实际作业时对操作员依赖过大，文献[13-14]指出了在遥控情况下，驾驶员操纵负荷较大，控制时间延迟，技术难点较多，并且人为即时规划的航线与理论航线偏离严重、无人机的作业遗漏率和重复率往往偏高，因此对于具有自主作业功能的植保无人机研究是很有必要的。

在之前的研究中，针对规则区域的多架次植保无人机航线规划法，合理地分配了各架次的喷药量和返航点，降低了无人机在非作业情况下无效消耗能量，使无人机的工作总能耗得到优化[15]；而对于不规则区域，研究了基于作业航向的植保无人机作业航线规划算法，可根据指定的作业方向，快速规划出较优的作业航线，有效地减少了飞行总距离和多余覆盖面积，通过分析作业航向与距离的关系，在未指定作业航向的情况下，给出某一推荐的作业航向与对应航线，使整个作业过程能耗和药耗最优[16]。但以上研究均是针对单区域进行的，而我国的地形较为复杂，既有较为集中的大块田地，也有田块较为分散的小面积农田，因此在包含多个较小区域的植保作业中，对于全局航线规划的研究也显得尤为必要。多区域的作业规划，不仅包含各区域内作业航线，还包括区域间作业顺序的安排和区域间调度航线规划。本文首先进行无人机作业行走方式的选择，并利用改进的遗传算法实现对区域间作业顺序的优化和调度航线的规划。

1 覆盖区域作业方式的选择

环境已知情况下，覆盖机械的行走方式主要有牛耕往复法和内外螺旋法，衡量行走方式优劣的标准主要有时间、能耗、路程、覆盖重复率与遗漏率，其中影响时间和多余能耗的主要因素为转弯次数，转弯次数越多，费时越多、多余能耗越大[17]。因此对两种行走方式进行分析，确定较优的无人机覆盖方式(图1)。

图1 两种作业行走方式示意图Fig.1 Schematic diagrams of two operation modes

如图1a所示，在一块矩形作业区域中，采用往复行走作业方式，沿纵向(长边)作业与沿横向(短边)相比，路程SBou和转弯次数TBou较优，分别为

(1)

(2)

当作业方向相垂直的区域长度(本文为横向长度M)不为幅宽d的整数倍时，采用向右取整的方式，确保整个区域均被覆盖。

如图1b所示，沿纵向(长边)开始的内螺旋行走方式，与沿横向(短边)开始行走相比，路程SSpi和转弯次数TSpi较优，分别为

(3)

(4)

图2 螺旋法重复与遗漏覆盖示意图Fig.2 Sketch of repeated and missing coverage of spiral method

2 区域间作业顺序规划

各区域的作业优化航线可利用之前研究的基于作业方向的航线规划算法(简称作业航线规划算法)求得[16]，其规划方式也是基于牛耕往复式实现的。当各区域作业航线规划完成后，全局规划算法主要集中在分配各区域作业顺序与区域间调度航线规划。

2.1 区域节点的获取

区域间的调度航线即为上一个作业区域的终止点与下一个作业区域的起始点间的连线，如图3所示，当某区域H1H2H3…Hm的作业航线确定后，作业起始点与终止点的位置可相互对调，即当点A1为作业起始点时，点A2便为作业终止点，反之当点A2为作业起始点，点A1即为此块区域的作业终止点。由于区域间调度航线为某区域终止点与其他区域起始点或某区域起始点与其他区域终止点的连线，且某区域的作业起始点与终止点并不固定(可相互对调)，因此设点A1与A2的中点A3为此区域的节点，通过规划出各区域节点间的最短连通距离，可获得整体调度航线较优的作业区域顺序。

图3 区域节点的获取Fig.3 Node acquisition of one operation area

先利用航线规划算法得到各区域的作业航线，通过作业起始点和终止点求得各区域的节点坐标，如图4所示，5个作业区域A、B、C、D、E，对应的节点分别为A3、B3、C3、D3、E3。区域间节点的连通属于TSP旅行商问题，即寻找一条最短的遍历各个节点的路径，或者表述为搜索自然子集X={1, 2, …,n}(X的元素表示对n个节点的编号)的某个排列P(X)={V0,V1,V2, …,Vn}，使Td取值最小。

(5)

式中d(Vi,Vi+1)——节点Vi到节点Vi+1的距离Td——遍历所有节点的总距离

图4 多区域节点示意图Fig.4 Schematic of multi-area nodes

采用遗传算法对区域的作业顺序进行规划。遗传算法是一种进化算法，其基本原理是仿效生物界中的“物竞天择、适者生存”的演化法则。图5为遗传算法流程图，遗传算法是把问题参数编码为染色体，再利用迭代的方式进行选择、交叉以及变异等运算来交换种群中染色体的信息，最终生成符合优化目标的染色体。

图5 遗传算法求解流程图Fig.5 Flow chart of genetic algorithm

2.2 遗传算法设计

2.2.1 编码与初始化

在遗传算法运算之前，需要针对问题设计染色体，包括基因字串的长度以及基因代表的含义，也就是对要搜索空间的可行解以编码的形式呈现。一般的编码方式采用二进制编码，此外也有整数、实数、文字等编码方式。本研究采用整数排列编码方法，对于n个节点的TSP问题，染色体分为n段，其中每一段对应区域节点的编号，如对10个区域节点的TSP问题{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}，则|10|1|6|5|2|4|8|7|9|3|就是一个合法的染色体。在生成染色体时需要进行染色体合法性检查环节，即染色体恰好是n个区域节点编码的一个排列，不能有重复的节点代码出现。

在完成染色体编码以后，必须产生一个初始种群(染色体集合)作为起始解，初始化结果的好坏，一定程度上决定了遗传算法收敛所用的时间。首先，需要决定初始化种群的数目，一般情况下，初始化种群的数目根据经验得到，如果初始化数目太大，可能会消耗过多的计算时间，但如果数目太小可能难以达到预期效果并导致过早收敛。初始化种群采用随机方式产生，初始化种群的数目往往根据作业区域(节点)数量而定，其取值一般在4n～6n之间[18]。

2.2.2 适应度函数与个体选择

适应度是用来评价个体对“环境”的适应能力，适应度越高，说明适应能力越强。设|V1|V2|…|Vi|…|Vn|为一个采用整数编码的染色体，其适应度函数为

(6)

适应度f1为恰好走遍n个节点，再回到出发节点的距离的倒数，适应度函数值越大的染色体越优，反之越劣。个体的选择即从旧群体中以一定概率选择个体到新的群体中，个体被选中的概率跟适应度值有关，个体的适应度越大，被选中的概率越大。

2.2.3 交叉与变异

交叉操作采用局部映射杂交，确定交叉操作的父代个体，假定节点个数即染色体长度为n，在[1,n]区间内产生随机整数r1和r2，确定两个位置，对父代染色体在这两位置的中间数据进行交叉，形成两个新的个体，如果新的个体中存在重复的节点编号，将不重复的数字保留，对于有冲突的数字，采用部分映射的方法消除冲突，即利用中间段的对应关系进行映射。交叉行为的发生有一定的概率，发生交叉行为的个体占种群个体总数的比例称为交叉率，记为Pc。遗传算法的变异操作指的是对染色体上某位置的信息进行变动，如交换路线上任意2个不同城市的位置。与交叉操作一样，变异操作同样有变异率的约束，是指发生变异的个体占种群中个体总数的比例，记为Pm。代沟是用于控制每代中种群被替换的比例，记为g，即在种群C中每代有C(1-g)个父代个体被选中进入下一代种群。

2.3 作业区域顺序规划算法的基本步骤

(1)对作业区域节点进行编码，确定初始化种群数量，随机生成初始种群。

(2)设置遗传算法的选择率、交叉率与变异率，并确定适应度函数。

(3)利用选择、交叉与变异操作，形成下一代种群。

(4)验证进化的代数是否满足终止条件，即是否得到满意的优化解，若不满足，返回步骤(2)继续运行。

(5)解码并输出优化的区域作业顺序解。

3 区域间调度航线的规划

如图6所示，针对所选5个作业区域A、B、C、D、E，假设利用所选算法得到的优化作业顺序为A→B→C→D→E，通过基于作业方向的航线规划算法分别得到各作业区域的作业起始点和终止点A1和A2、B1和B2、C1和C2、D1和D2、E1和E2，连接A2B1、B2C1、C2D1、D2E1、E2A1，形成了一组区域间调度航线l1、l2、l3、l4、l5。

图6 区域间调度航线示意图Fig.6 Schematic of dispatching routes among areas

图7 二进制编码示意图Fig.7 Schematic diagrams of binary coding

如图7a所示，可将多区域的作业顺序和区域间的调度航线安排通过排列的方式表现出来，当各区域的作业顺序保持不变时，如图7b所示，各区域的作业起始点和终止点均可进行调整，而每个区域作业起始点与终止点的选择均有2种情况。以区域A为例。作业起始点与终止点可分别为A1与A2或A2与A1，这两种状态可分别用0与1来表示，因此如图7c所示，|A1A2|B2B1|C1C2|D1D2|E2E1|排列情况可通过二进制编码01001表示，二进制编码的位数与作业区域数相同。

同样，区域间调度航线规划也可利用遗传算法进行求解，设作业区域数为m，对应的适应度函数为

(7)

适应度f2为m条调度航线总长度的倒数。按照遗传算法的步骤进行调度航线规划。

4 仿真

仿真时，选用5块区域，区域A、B、C、D、E的各边界点坐标如表1所示。

表1 各区域边界点坐标Tab.1 Boundary point coordinates of areas

利用作业航线规划算法得到各区域的作业起始点与终止点，并求出各区域对应的节点，结果如表2所示。

表2 各区域起始点、终止点和节点坐标Tab.2 Coordinates of starting points, ending points and nodes

利用遗传算法计算遍历各区域节点的最短路径，设交叉率Pc=0.9，变异率Pm=0.2，种群大小C=20，代沟g=0.9。如图8所示，当进化第3代时，得到遍历各节点的路径距离最优值为Dmin=1 368.95 m，对应的作业顺序为A→B→D→C→E。

图8 作业顺序遗传算法进化过程图Fig.8 Process of genetic algorithm in operating sequence

确定了作业顺序后，对|A1A2|B1B2|D1D2|C1C2|F1F2|排列进行5位二进制随机编码，再次进行遗传算法运算，适应度计算公式如式(7)所示，设种群大小C=10，交叉率Pc=0.9，变异率Pm=0.2，代沟g=0.9。如图9所示，同样在进化到第3代时，得到调度航线的距离最优解Lmin=1 055.18 m，编码序列为10011，即|A2A1|B1B2|D1D2|C2C1|F2F1|。

图9 调度航线遗传算法进化过程图Fig.9 Process diagram of genetic algorithm in dispatching routes

航线规划仿真结果如图10所示，其中蓝线为无人机在区域中作业航线，红线为区域间调度航线，箭头为调度方向，仿真结果验证了本算法的可行性，可对无人机多区域作业进行全局航线规划。

图10 全局航线规划仿真结果Fig.10 Overall route planning simulation results

5 结论

(1)从作业路程、多余覆盖和遗漏覆盖的角度，分析了多种覆盖作业方式的优劣，确定了牛耕往复法作为无人机在单区域内的作业方式。

(2)将全局航线规划算法划分为单区域航线规划、区域间作业顺序规划和区域间调度航线规划3部分。将区域间作业顺序规划转化为节点间的TSP旅行商问题，基于遗传算法得到作业顺序优化解。之后利用改进的遗传算法，对区域间调度航线进行二进制编码，得到了区域间调度的最短航线，使得整个作业过程的能耗和工作时间得到了优化。

(3)仿真得到了多区域作业的优化顺序与区域间调度航线的最短距离，验证了算法的可行性，在无人机作业前可对整个作业过程的飞行航线进行规划，节省了人力，使作业管理更加方便，同时降低了人为即时规划的不准确性，使无人机植保系统更加智能化，规划算法有效地减少了无人机飞行距离，因此既节省了能耗成本，又提高了无人机作业效率，有助于推动农业植保朝着更加智能、高效、节能和无人化的方向发展。

1 王玲，兰玉彬，HOFFMANN W C,等. 微型无人机低空变量喷药系统设计与雾滴沉积规律研究[J/OL].农业机械学报，2016，47(1)：15-22. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20160103&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2016.01.003. WANG Ling, LAN Yubin, HOFFMANN W C, et al. Design of variable spraying system and influencing factors on droplets deposition of small UAV[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2016, 47(1): 15-22. (in Chinese)

2 李鑫星，李辉，马云飞，等.面向蔬菜病虫害视频移动获取的网络互通网关设计[J/OL]. 农业机械学报，2015，46(11)：309-315. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20151142&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2015.11.042. LI Xinxing, LI Hui, MA Yunfei, et al. Network interworking gateway design for video of vegetables harmed by pets[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(11): 309-315. (in Chinese)

3 张东彦，兰玉彬，陈立平，等. 中国农业航空施药技术研究进展与展望[J/OL].农业机械学报，2014，45(10)：53-59. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20141009&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2014.10.009. ZHANG Dongyan, LAN Yubin, CHEN Liping, et al. Current status and future trends of agricultural aerial spraying technology in China [J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(10): 53-59. (in Chinese)

4 薛新宇，梁建，傅锡敏.我国航空植保技术的发展前景[J].中国农机化，2008(5)：72-74． XUE Xinyu, LIANG Jian, FU Ximin. Prospect of aviation plant protection in China[J]. Chinese Agricultural Mechanization, 2008(5): 72-74. (in Chinese)

5 李成智，徐治立. 中国农业航空技术发展分析与政策建议[J]. 自然辩证法研究，2012，28(11)：36-41. LI Chengzhi, XU Zhili. The analyses and suggestions of technology development of agricultural aviation in China[J]. Studies in Dialectics of Nature, 2012, 28(11): 36-41. (in Chinese)

6 薛新宇，兰玉彬.美国农业航空技术现状和发展趋势分析[J/OL].农业机械学报，2013，44(5)：194-201．http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20130534&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2013.05.034. XUE Xinyu， LAN Yubin. Agricultural aviation applications in USA[J/OL]. Transactions of the Chinese Society for Agricultural Machinery，2013，44(5)：194-201. (in Chinese)

7 茹煜，金兰，贾志成，等.无人机静电喷雾系统设计及试验[J].农业工程学报，2015，31(8)：42-47. RU Yu, JIN Lan, JIA Zhicheng, et al. Design and experiment on electrostatic spraying system for unmanned aerial vehicle [J]. Transactions of the CSAE, 2015, 31(8): 42-47. (in Chinese)

8 李冰，刘镕源，刘素红，等．基于低空无人机遥感的冬小麦覆盖度变化监测[J]．农业工程学报，2012，28(13)：160-165． LI Bing, LIU Rongyuan, LIU Suhong, et al. Monitoring vegetation coverage variation of winter wheat by low-altitude UAV remote sensing system[J]. Transactions of the CSAE, 2012, 28(13): 160-165. (in Chinese)

9 HUANG Y, HOFFMANN W C, LAN Y, et al. Development of a spray system for an unmanned aerial vehicle platform [J]. Applied Engineering in Agriculture, 2009, 25(6): 803-809．

10 JACOPO P, SALVATORE FILIPPO D G, EDOARDO F, et al. A flexible unmanned aerial vehicle for precision agriculture[J]. Precision Agriculture, 2012, 13(4): 517-523.

11 茹煜，贾志成，范庆妮，等.无人直升机远程控制喷雾系统[J/OL].农业机械学报，2012，43(6)：47-52. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20120609&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2012.06.009. RU Yu, JIA Zhicheng, FAN Qingni, et al. Remote control spraying system based on unmanned helicopter[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2012, 43(6): 47-52. (in Chinese)

12 秦维彩，薛新宇，周立新，等. 无人直升机喷雾参数对玉米冠层雾滴沉积分布的影响[J].农业工程学报，2014,30(5)：50-56. QIN Weicai, XUE Xinyu, ZHOU Lixin, et al. Effects of spraying parameters of unmanned aerial vehicle on droplets deposition distribution of maize canopies [J]. Transactions of the CSAE, 2014, 30(5): 50-56.(in Chinese)

13 丁团结，方威，王锋.无人机遥控驾驶关键技术研究与飞行品质分析[J].飞行力学，2011，29(2)：17-24. DING Tuanjie, FANG Wei, WANG Feng. Development of UAV remote-piloted key technology and flight qualities[J]. Flight Dynamics, 2011, 29(2): 17-24. (in Chinese)

14 彭孝东，张铁民，李继宇，等.基于目视遥控的无人机直线飞行与航线作业试验[J/OL]. 农业机械学报，2014，45(11)：258-263. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20141140&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2014.11.040. PENG Xiaodong, ZHANG Tiemin, LI Jiyu, et al. Experiment of straight and airline flight operation for farmland based on UAV in visual remote mode[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2014, 45(11): 258-263. (in Chinese)

15 徐博，陈立平，谭彧，等.多架次作业植保无人机最小能耗航迹规划算法研究[J/OL].农业机械学报，2015，46(11)：36-42. http:∥www.j-csam.org/jcsam/ch/reader/view_abstract.aspx?flag=1&file_no=20151106&journal_id=jcsam. DOI：10.6041/j.issn.1000-1298.2015.11.006. XU Bo, CHEN Liping, TAN Yu, et al. Path planning based on minimum energy consumption for plant protection UAVs in Sorties[J/OL]. Transactions of the Chinese Society for Agricultural Machinery, 2015, 46(11): 36-42. (in Chinese)

16 徐博，陈立平，谭彧，等.基于无人机航向的不规则区域作业航线规划算法与验证[J/OL].农业工程学报，2015，31(23)：173-178. http:∥www.tcsae.org/nygcxb/ch/reader/view_abstract.aspx?file_no=20152323&flag=1. DOI：10.11975/j.issn.1002-6819.2015.23.023. XU Bo, CHEN Liping, TAN Yu, et al. Route planning algorithm and verification based on UAV operation path angle in irregular area[J/OL]. Transactions of the CSAE，2015，31(23)：173-178. (in Chinese)

17 王俭，赵鹤鸣，肖金球.基于区域优化分割的机器人全覆盖路径规划[J].计算机工程与应用，2006，42(22)：59-62. WANG Jian, ZHAO Heming, XIAO Jinqiu. Optimized region decomposition based complete coverage path planning for mobile robot[J]. Computer Engineering and Applications, 2006, 42(22):59-62.(in Chinese)

18 刘晓霞.种群规模对遗传算法性能影响的研究[D].保定：华北电力大学，2010:1-37.

Path Planning Algorithm for Plant Protection UAVs in Multiple Operation Areas

XU Bo1,2CHEN Liping1,3XU Min1,3TAN Yu2

(1.BeijingResearchCenterofIntelligentEquipmentforAgriculture,Beijing100097,China2.CollegeofEngineering,ChinaAgriculturalUniversity,Beijing100083,China3.BeijingKeyLaboratoryofIntelligentEquipmentTechnologyforAgriculture,BeijingAcademyofAgricultureandForestry,Beijing100097,China)

According to multi-area operations, a kind of overall route planning algorithm for plant protection UAVs was developed in order to reduce flight distance in multi-area operations and operating sequence of each area was reasonable allocation to improve operational efficiency and reduce energy consumption of the UAVs. The algorithm was divided into three parts, namely, single area route planning, operating sequences of areas and dispatching route planning among areas. After analyzing a variety of covering operation modes in aspects of operation distance, extra coverage and missed coverage, the UAVs operation mode in single area was determined. Optimized operation sequences of areas were planned based on genetic algorithm and traveling salesman problem (TSP). Dispatching routes among areas were planned based on improved genetic algorithm with binary coding, finally the overall route planning algorithm was achieved. The simulation was performed in an operation of five different irregular areas, numbers of each area were set asA,B,C,DandE. Operation route of each area was planned by using the previously proposed algorithm of route planning algorithm based on operation path angle in irregular, achieving operation start point, end point and node point coordinates of each area. Operation sequences of areas were achieved based on genetic algorithm and TSP, dispatching routes among areas were planned based on the improved genetic algorithm, of which the code was a random five-digit binary sequence, each digit represented arrangement of start point and end point of each area. The simulation result proved feasibility of the multi-area route planning algorithm. Nowadays, unmanned operations becomes trend, this multi-area route planning algorithm not only saves manpower required by route planning, but also makes operation management easier, and it is suitable for autonomous unmanned aerial vehicles and can be widely used in the area of precision agriculture.

plant protection UAVs; path planning; multi-area operation; algorithm

10.6041/j.issn.1000-1298.2017.02.010

2016-10-11

2016-11-23

国家自然科学基金项目(31601228)、北京市农林科学院青年科研基金项目(QNJJ201422、QNJJ201632)和北京市自然科学基金项目(6164032)

徐博(1988—)，男，博士生，主要从事机电一体化研究，E-mail： xubocau@163.com

陈立平(1973—)，女，研究员，博士，主要从事农业信息技术和农业智能装备研究，E-mail： chenlp@nercita.org.cn

TP18

A

1000-1298(2017)02-0075-07