基于Grid-GSA算法的植保无人机路径规划方法

王 宇 陈海涛 李 煜 李海川

(东北农业大学工程学院，哈尔滨150030)

基于Grid-GSA算法的植保无人机路径规划方法

王 宇 陈海涛 李 煜 李海川

(东北农业大学工程学院，哈尔滨150030)

为了提高植保无人机的作业效率，研究了一种路径规划方法。运用栅格法构建环境模型，根据实际的作业区域规模、形状等环境信息和无人机航向，为相应栅格赋予概率，无人机优先选择概率高的栅格行进。基于上述机制实现了在形状不规则的作业区域内进行往复回转式全覆盖路径规划;以每次植保作业距离为变量，根据仿真算法得出返航点数量与位置来确定寻优模型中的变量维数范围，以往返飞行、电池更换与药剂装填等非植保作业耗费时间最短为目标函数，通过采用引力搜索算法，实现对返航点数量与位置的寻优;为无人机设置必要的路径纠偏与光顺机制，使无人机能够按既定路线与速度飞行。对提出的路径规划方法进行了实例检验，结果显示，相比于简单规划与未规划的情况，运用Grid-GSA规划方法得出的结果中往返飞行距离总和分别减少了14%与68%，非植保作业时间分别减少了21%与36%，其它各项指标也均有不同程度的提高。在验证测试试验中，实际的往返距离总和减少了322m，实际路径与规划路径存在较小偏差。验证了路径规划方法具有合理性、可行性以及一定的实用性。

植保无人机;路径规划;栅格法;返航点;引力搜索算法

引言

无人机(Unmanned aerial vehicle，UAV)凭借其尺寸小、机动性好、对起降跑道要求低或无要求、造价相对低廉以及无人化等优势，已经在军事与民用领域得到了广泛使用［1－2］。植保无人机以无人机为载体，搭载农药喷雾设备，用于植保作业，其具有作业高度低、漂移少、对环境的污染较低，受作业区域电线杆、防护林等限制条件的影响较小，且旋翼产生的气流场有助于增加雾流对作物的穿透性，可获得良好的喷施效果等优点，随着相关技术的逐步成熟，植保无人机越来越受到关注，其使用也更加普及［3－4］。但目前植保无人机作业以遥控方式为主，操作难度较大，操纵人员往往需要经过专业培训［5］;而且人为遥控时，难免产生偏离最佳路径的现象，导致药剂重施、漏施等问题［6］。因此，为了降低操纵人员的技术要求与工作压力，同时使植保作业更加精准、高效与节能，针对植保无人机作业过程，编制合理的路径规划算法，并配套定位技术，使无人机能够稳定的按照规划路径进行植保作业，已经成为当前植保无人机相关研究中需要解决的一个重要问题。另外，植保无人机的作业区域形状较为规则，一般开阔无障碍，作业环境相对优越，这也为植保无人机朝着自动化与智能化方向发展提供了条件。

无人机路径规划方法主要包括目标区域侦察监测及定点、移动目标跟踪打击、诱敌飞行等，其中涉及到寻求最优路径的优化方法，躲避火力威胁、地形障碍与雷达侦测等不利因素的避障方法以及相关定位、传感方法等［7－8］。植保无人机路径规划属于全覆盖路径规划的范畴，大多数技术与研究均能够实现该种路径的规划［9－10］。但路径规划还应该与实际的农艺要求相结合，如CONESA-MUOZ等［11］针对多辆拖拉机田间协同作业路径规划问题，以消耗最小为目标建立了数学模型，对模拟退火算法进行了改进并用于路径寻优计算。在植保无人机路径规划方面也已经开展了一些研究，徐博等［12－13］针对形状规则的作业区域内无人机返航点的规划问题，提出了一种多架次作业植保无人机航迹规划算法，该算法以无人机的工作总耗能最小为目标;其还针对不规则区域提出了一种植保作业航迹规划算法，算法可根据指定作业方向规划出与作业区域相应的路径。

在植保无人机实际作业过程中，随着药剂或电量耗尽，无人机需要返航至保障点进行药剂装填或电池更换，其中返航点的数量与位置不仅受到载药量、续航时间、飞行速度、作业幅宽等无人机固有属性的影响，还与作业方向、作业区域尺寸和形状等环境有关。以往的植保无人机路径规划方法中，返航点往往位于无人机起始点所在的作业区域边界上，且在作业区域规模较大的情况下，返航点数量会多于未规划时的情况，由于返航点数量增多，随着往返次数增加，不仅会使往返距离总和变大，还会增加保障作业次数，从而导致非植保作业时间变长。针对这种情况，本文以缩短往返飞行、电池更换与药剂装填等非植保作业消耗的时间为目标，开展植保无人机路径规划方法研究。

1 植保无人机路径规划的基本思路

当作业区域面积较小时，植保无人机无需中途装填药剂或更换电池即可完成植保作业。但当作业区域较大，植保无人机单次植保作业无法满足作业要求时，就需要中途多次飞至保障点进行保障作业。无人机在工作区域与保障点之间进行往返时，属于非作业状态，所以路径规划应尽量减少返航点与保障点之间的距离总和。表1首先对本文涉及的名词进行定义。

设保障点位于坐标系原点，植保无人机续航时间为25min，飞行速度为6m/s，最长植保作业时间为15min，作业速度为3m/s，作业幅宽为2m。图1中未规划与简单规划情况下各返航点与保障点之间的往返距离总和分别为1 479m与629m，返航点数量均为5，此时图1中的简单规划情况即可认为是最优路径，出现此种最优情况的条件可表示为

表1 相关名词定义Tab．1 Terms and definitions

图1 300m×100m作业区域路径规划Fig．1 Path planning for 300m×100m working area

当无法满足式(1)时，若仍要各返航点均位于起始点所在的作业区域边界上，则必须增加返航点的数量。

图2为相同型号植保无人机在400 m×100 m作业区域内未规划与简单规划的返航点对比情况，返航点数量分别为7和8，而且这种返航点数量之间的差距还会随着作业区域尺寸的改变而发生变化，如表2与表3所示。

图2 400m×100m作业区域路径规划Fig．2 Path planning for 400m×100m working area

表2 返航点数量随作业区域长度变化情况Tab．2 Number of return points varying w ith length of working area

表3 返航点数量随作业区域宽度变化情况Tab．3 Number of return point varying w ith w idth of working area

定义植保无人机作业方向为作业区域长度方向，表2中，作业区域宽度为200 m，表3中，作业区域长度为400m，表2与表3中括号外数值为选取规则矩形作业区域时的测算结果。从表2、3中可知，当保持长度不变时，随着宽度的增加，未规划与简单规划的返航点数量之差将逐渐变大;当保持宽度不变时，随着长度的增加，未规划与简单规划的返航点数量之差未呈现单调变化趋势，该差值主要与植保无人机载药量所允许的最远作业距离Dmax和作业区域长度L有关，Dmax/L越接近偶数，未规划与简单规划的返航点数量之差就越小。除上述影响因素外，返航点数量还会受到作业区域不规则边界的影响，表中括号内数字即为在不规则边界的作业区域内未规划与简单规划的返航点的数量情况，如图2所示，不规则边界由矩形区域去掉左上角三角形区域形成，表中的作业区域为去掉边长40m的等腰直角三角形后的区域。

综上所述，植保无人机路径规划主要是对作业过程中返航点数量与位置的规划，其主要受到无人机固有属性与作业区域环境的影响，而且通过表2中数据可知，简单规划的返航点数量比未规划情况最多高出96%，随着往返次数增多，往返距离与作业时间也随之增大，需要对路径进一步优化。针对上述问题，本文将栅格法(Grid method)［14］与引力搜索算法(Gravitational search algorithm，GSA)［15－16］相结合，运用栅格法建立作业区域环境，通过为栅格附加移动权值，使植保无人机路径规划方法能够适应形状不规则的作业区域，以非植保作业时间最小为目标，运用引力搜索算法进行寻优，从而获得返航点数量与位置最优解。

2 基于Grid-GSA算法的路径规划方法

2.1 栅格化环境

植保无人机的路径规划可以视为已知环境下的路径规划问题，且由于植保作业的各条路径相互平行或垂直，相邻平行路径之间的距离为作业幅宽。一般情况下，作业区域形状较为规则，因此适宜应用栅格法表示环境情况。构造初始栅格时，以无人机的作业幅宽为边长，根据实际环境信息对相应位置上的栅格赋予移动权值，位于作业区域边界或障碍物处的栅格权值ω0=0，位于待作业区域中的栅格权值ωe=1。

2.2 作业路径仿真

为能够识别边界，在作业区域内规划出如图1所示的往复回转式作业路径，首先计算无人机前进的概率为

式中 Pf——无人机前进的概率

ωf——无人机前进的权值

ωl、ωr、ωb——无人机左侧、右侧与后方栅格的权值，ωb=0表示无人机飞过区域均被视为边界

其余方向的移动概率计算与式(2)同理。无人机前进方向的权值添加奖励机制表示为

式中 S——直行奖励系数，S＞1

Gf——无人机前方栅格

B——边界栅格

利用式(2)与式(3)计算各个方向的移动概率，使无人机优先选择概率大的移动方向，即可实现直行作业，且遇到作业区域边界或障碍物时进行转弯，但此时无人机作业路径呈螺旋形，并不适用于植保作业。为使无人机在作业区域边界处进行回转，对无人机左后方或右后方栅格的权值进行奖励

式中 U——回转奖励系数，U＞S

ωlb——无人机左后方栅格权值

Glb——无人机左后方栅格

如图3所示，在t1时刻，无人机飞行至作业区域边界，ωf=ω0=0，且通过式(4)所示的奖励机制，栅格2权值ω2=ωe+U，设无人机右侧为已作业区域，则此时无人机左转概率最大;在t2时刻，无人机进入栅格1，此时ωf=ωe+S，而ωl=ω2=ωe+U，又因为U＞S，使得此时无人机左转概率依然最大。通过上述方法，即可实现无人机的往复回转式作业路径规划，再为无人机附加载药量属性，记录每次植保作业时药量耗尽的返航点位置，就能够通过仿真得到未规划状态的返航点数量与位置。

2.3 引力搜索算法寻优

图3 植保无人机周围权值分布Fig．3 Weight distribution around plant protection UAV

遗传算法、粒子群算法、模拟退火算法等智能优化算法已经被用于路径规划问题，在最短路径规划中表现出较好的性能［17－19］。引力搜索算法也属于启发式算法，对于本文研究的路径规划问题，变量为每次植保作业的飞行距离，目标为返航点与保障点之间往返距离总和最短，变量与目标函数之间不存在明显的线性关系，且该函数关系还会受到无人机固有属性与作业区域环境的影响，属于较为典型的NP-Hard问题，适于智能优化算法求解［20］。引力搜索算法的迭代规则为:一个粒子在下一时刻的速度等于该时刻的速度加上加速度，在下一时刻的位置等于该时刻的位置加上下一时刻的速度，即

(1)算法寻优变量为每次植保作业的飞行距离，表示为

(2)由于固定的作业区域面积使得植保作业飞行时间一定，若要缩短总的作业时间，就应尽量降低往返飞行、电池更换与药剂装填等非植保作业的时间消耗，以非植保作业时间最短为目标建立目标函数

其中 Pn=(xn，yn) P0=(x0，y0)

式中 Ten——第n次保障作业时更换电池时间

Tpn——第n次保障作业时装填药剂时间

voff——非植保作业状态下的飞行速度

Pn——第n个返航点的位置坐标

P0——保障点的位置坐标

xn、yn分别与Dn存在函数关系，可分别表示为

图4 f与函数曲线Fig．4 Function graph of f and

式(7)表示电池更换与药剂装填两项保障工作可同时进行，且取其中消耗时间较长者作为保障作业时间。

(3)以式(1)为每次寻优的约束条件。基于Grid-GSA算法的路径规划方法步骤为:①栅格化作业区域，为栅格设置初始权值。②运用仿真方法得出未规划与简单规划的返航点数量与位置。③根据未规划与简单规划的返航点数量之差确定搜索空间。④生成初始搜索群体。⑤计算个体目标函数值。⑥计算个体不同维度上的加速度和速度。⑦更新个体位置。⑧重复步骤⑤～⑦，直至达到终止条件。⑨输出规划结果并结束。

2.4 路径纠偏与光顺

从规划好的路径中选取关键点，并将其位置信息输入无人机控制器，再配合无人机自身纠偏算法、定位系统、电动机、螺旋桨等硬件，即可使无人机按照既定路径与速度自主飞行。本文方法所需的主要纠偏机制如图5所示。

图5 纠偏机制Fig．5 Machanism of deviation rectification

无人机通过机载定位系统反馈得到实际位置F，通过与输入的关键点R1与R2形成直线进行比较，得出偏航距离d，以此为依据调整飞行速度。另外，无人机还需具备如图5所示的光顺路径的能力。

3 实例检验

3.1 算例检验

设植保无人机续航时间为25 min，最长植保作业时间为15min，飞行速度voff为6m/s，作业速度von为3 m/s，计算得出载药量所允许的最远作业距离Dmax=2 700m，作业幅宽为2m，电池更换时间Te与最大药剂装填时间Tpmax均为1min，由于药剂装填时间与每次植保作业的载药量有关，计算药剂装填时间Tpn为

式中 tb——药剂装填时间基数，本文取20 s

选取作业区域长700 m、宽100 m，边界形状不规则，如图6所示，不规则边界由矩形区域去掉左上角三角形区域形成，该三角形区域为直角边长40 m的等腰直角三角形。图6中坐标系为非等比坐标系，保障点位于坐标系原点处，根据植保无人机作业幅宽对作业区域栅格化，栅格边长为2 m。运用仿真方法得出的未规划与简单规划的返航点数量与位置如图6所示，返航点数量分别为12与22，往返距离总和分别为6 440m和2 413m，非植保作业时间分别为29.9min和24.2min。

图6 700m×100m作业区域路径规划Fig．6 Path planning for 700m×100m working area

运用Grid-GSA算法规划返航点情况如图7所示，植保无人机需要进行15次返航保障，返航点与保障点之间往返距离总和为2 073m，由于终点位置固定，所以该距离总和未考虑终点到保障点的距离，非植保作业时间19min，具体的规划结果见表4。

图7 基于Grid-GSA算法的路径规划返航点情况Fig．7 Planned path by Grid-GSA

表4 基于Grid-GSA算法的路径规划结果Tab．4 Results of path planning based on Grid-GSA

3.2 验证试验

试验主要测量在实际环境中，无人机分别按照未规划返航点与运用Grid-GSA算法规划返航点飞行得出往返距离总和，检验该测量数据与计算机输出数据的偏差，分析产生偏差的主要影响因素，以此为依据判断本文提出方法的可行性与实用性。根据试验要求，需要无人机具有按照设定航点飞行的功能，试验选取大疆精灵3无人机，具体参数为最大水平飞行速度16 m/s，飞行时间约25 min，采用GPS定位，信号最大有效距离1 000m。

试验于2017年1月在东北农业大学进行，试验区域开阔无障碍，形状为矩形，尺寸为200m×60m。人为设置边界，于作业区域一角去掉直角边长40m的等腰直角三角形区域，以验证Grid-GSA算法对不规则边界的适用性，天气良好，试验环境如图8所示。

图8 试验环境Fig．8 Experiment environment

运用本文提出方法，对试验田地的作业区域进行返航点规划，结果如表5所示。根据表5数据，在作业区域内进行无人机航点定位。

完成定位后，使无人机按照既定航点飞行，并打开摄像功能，通过后期处理摄像中标志点的位置信息，来记录实际航迹与理想航迹的偏差，现场情况如图9所示。

表5 计算机输出的返航点坐标数据Tab．5 Data of return point outputted by com puter m

图9 航点定位Fig．9 Flight points positioning

通过试验测得无人机实际飞行路径如图10所示。

图10 无人机实际飞行路径Fig．10 Path of UAV from test

通过试验测得未规划和Grid-GSA算法规划的返航点情况如表6所示。

表6 试验测得的返航点坐标数据Tab．6 Measured data of return point m

4 结果分析

对基于Grid-GSA算法规划、简单规划与未规划3种情况的数据进行对比，如表7所示。

表7 路径规划结果数据对比Tab．7 Data of path planning results

表7中，情况1、2、3分别对应Grid-GSA算法规划、简单规划、未规划。情况1中的返航点数量少于情况2，多于情况3，且由图7可知，大多数返航点没有位于起始点所在的作业区域边界。设情况1的返航点数量与位置均为未规划情况，保持15个返航点数量不变，将其移至作业距离所允许的最近起始点所在作业区域边界，即进行简单规划，计算得

由该结果可知，无法满足式(1)要求，并通过进一步计算验证，在返航点数量少于22时均无法满足式(1)要求。说明针对本文实例，简单规划结果必然导致返航点数量激增。

情况1相比于情况2、3，往返距离总和分别缩短了14%与68%，非植保作业时间分别减少了21%与36%。取情况1所有的返航点与情况2前15个返航点计算往返距离总和分别为2 073 m与1 223m，情况2剩余返航点与保障点之间的往返距离总和为1 190m。由此可见，虽然情况1与情况2相对应的返航点中，均是情况1返航点距离保障点较远，但由于情况2返航点数量的增多，导致了往返距离总和的变大。而且保持作业区域长度不变，随着宽度不断增大，这种差距还会更加明显。

3种情况更换电池的次数分别为9、8和12，装填药剂的次数与返航次数相同，分别为15、22和12，即情况3每次保障作业均进行了电池更换与药剂装填。情况3的保障作业时间最短，但由于往返距离较远，使得非植保作业时间最长。情况1与情况2相比较，往返飞行时间与保障作业时间均较短，两种情况的药剂装填平均时间分别为51.5 s与41.5 s，虽然情况2优于情况1，但由于保障次数增多，使得总的药剂装填时间较长，而且还加大了人工作业密度。

无人机电池充电时间较长，所以每次植保作业需要配备多组电池以备更换。本文规划方法可计算出每块电池电量消耗情况如表8所示，配合表4中电池更换的次数与时机，可为电池配备提供参考。3种情况中，电池的利用率平均值分别为79%、88%与65%，电池用量分别为10、9、13块。若对情况1中低利用率电池1与10进行合并，则利用率平均值变为88%，电池用量变为9块，所以在该方面情况1也表现出较优的性能。

表8 电池使用情况Tab．8 Consumption of battery power %

根据表5、6中的返航点坐标，可计算各返航点至保障点之间的距离，从而得出未规划与Grid-GSA算法规划后的往返距离总和，如表9所示。

表9 往返距离总和Tab．9 Total distance of round trip m

由表9可知，对于同一作业区域，运用Grid-GSA算法规划返航点能够使往返距离总和减少，且试验结果显示，运用Grid-GSA算法得出的往返距离总和减少幅度更加明显，说明Grid-GSA算法具有一定的实用性与可行性。仿真结果与试验结果存在一定偏差，主要由无人机定位系统与实际位置偏差造成，在试验中，通过无人机航拍获得标志点位置出现了偏离中心位置的情况，这说明试验中的无人机没有完全按照设定航点与路线飞行。虽然无人机具有自主的纠偏算法，但由于定位系统精度低的问题，就会导致无人机认为已经通过纠偏回归正确航线，但实际上仍存在偏差。若采用MG-1S型植保无人机，使用手持RTK导航系统，精度可达到厘米级，且实现高精度定位还有较多手段，本文路径规划方法可以进一步得到改进。

5 结论

(1)将栅格法与引力搜索算法相结合，提出了基于Grid-GSA算法的路径规划方法。通过将无人机固有属性与作业区域环境相关参数输入算法，即可自动输出最优的作业路径，其中包含了合理的返航点数量与位置，保证非植保作业时间最短，且该方法适用于具有不规则边界的作业区域。将规划出的路径输入植保无人机控制器，通过无人机的纠偏算法、定位系统以及控制器与各硬件之间的协调配合，来实现自主作业。

(2)运用实例对本文提出的路径规划方法进行了检验。采用本文提出的基于Grid-GSA算法的路径规划方法得出的结果，相比于简单规划与未规划情况，往返距离总和分别缩短了14%与68%，非植保作业时间分别减少了21%与36%，耗费电池数量与电池利用率等指标均较好，从而验证了该方法的合理性与可行性。在验证试验中，运用Grid-GSA算法规划返航点比未规划的实际往返距离总和少322m，说明方法具有一定的实用性与可行性。

1 HUANG L，QU H，JIP，et al．A novel coordinated path planningmethod using k-degree smoothing formulti-UAVs［J］．Applied Soft Computing，2016，48:182－192．

2 TISDALE J，KIM Z W，HEDRICK J K．Autonomous UAV path planning and estimation［J］．IEEE Robotics＆Automation Magazine，2009，16(2):35－42．

3 张东彦，兰玉彬，陈立平，等．中国农业航空施药技术研究进展与展望［J/OL］．农业机械学报，2014，45(10):53－59．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20141009＆flag=1．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－39．(in Chinese)

4 周志艳，臧英，罗锡文，等．中国农业航空植保产业技术创新发展战略［J］．农业工程学报，2013，29(24):1－10．ZHOU Zhiyan，ZANG Ying，LUO Xiwen，et al．Technology innovation development strategy on agricultural aviation industry for plant protection in China［J］．Transactions of the CSAE，2013，29(24):1－10．(in Chinese)

5 丁团结，方威，王锋．无人机遥控驾驶关键技术研究与飞行品质分析［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)

6 彭孝东，张铁民，李继宇，等．基于目视遥控的无人机直线飞行与航线作业试验［J/OL］．农业机械学报，2014，45(11): 258－263．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20141140＆flag=1．DOI:10．6041/j．issn．1000-1298．2014．11．040．PENG Xiaodong，ZHANG Tiemin，LIJiyu，et al．Experimentof straight and airline flight operation for farmland based on UAV in visual remotemode［J/OL］．Transactions of the Chinese Society for Agricultural Machinery，2014，45(11):258－263．(in Chinese)

7 YAO P，WANG H，SU Z．Cooperative path planning with applications to target tracking and obstacle avoidance for multi-UAVs［J］．Aerospace Science＆Technology，2016，54:10－22．

8 RAMANA M V，VARMA SA，KOTHARIM．Motion planning for a fixed-wing UAV in urban environments［J］．IFAC-Papers Online，2016，49(1):419－424．

9 POPESCU D，STOICAN F，ICHIM L．Control and optimization of UAV trajectory for aerial coverage in photogrammetry applications［J］．Advances in Electrical and Computer Engineering，2016，16(3):99－106．

10 TORRES M，PELTA D A，VERDEGAY J L，et al．Coverage path planning with unmanned aerial vehicles for 3D terrain reconstruction［J］．Expert Systems with Applications，2016，55(C):441－451．

11 CONESA-MUOZ J，PAJARESG，RIBEIRO A．Mix-opt:a new route operator for optimal coverage path planning for a fleet in an agricultural environment［J］．Expert Systemswith Applications，2016，54:364－378．

12 徐博，陈立平，谭彧，等．多架次作业植保无人机最小能耗航迹规划算法研究［J/OL］．农业机械学报，2015，46(11): 36－42．http:∥www．j-csam．org/jcsam/ch/reader/view_abstract．aspx?file_no=20151106＆flag=1．DOI:10．6041/j．issn．1000-1298．2015．11．006．XU Bo，CHEN Liping，TAN Yu，et al．Path planning based onminimum 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)

13 徐博，陈立平，谭彧，等．基于无人机航向的不规则区域作业航线规划算法与验证［J］．农业工程学报，2015，31(23): 173－178．XU Bo，CHEN Liping，TAN Yu，et al．Route planning algorithm and verification based on UAV operation path angle in irregular area［J］．Transactions of the CSAE，2015，31(23):173－178．(in Chinese)

14 GU J，CAO Q．Path planning formobile robot in a 2.5 dimensional grid based map［J］．Industrial Robot，2011，38(3):315－321．

15 王宇，黄胜，廖全蜜，等．基于引力搜索算法的船舶舱室布置方法［J］．上海交通大学学报，2016，50(1):131－139．WANG Yu，HUANG Sheng，LIAO Quanmi，et al．A method for ship compartment layout design based on gravitational search algorithm［J］．Journal of Shanghai Jiao Tong University，2016，50(1):131－139．(in Chinese)

16 王宇，黄胜，廖全蜜，等．基于引力搜索算法的舱室分布方案设计方法［J］．哈尔滨工程大学学报，2016，37(1):48－52．WANG Yu，HUANG Sheng，LIAO Quanmi，et al．Method for the layout design of ship cabins based on gravitational search algorithm［J］．Journal of Harbin Engineering University，2016，37(1):48－52．(in Chinese)

17 MAC T T，COPOT C，TRAN D T，et al．Heuristic approaches in robot path planning:a survey［J］．Robotics＆Autonomous Systems，2016，86:13－28．

18 DAS P K，BEHERA H S，DAS S，et al．A hybrid improved PSO-DV algorithm for multi-robot path planning in a clutter environment［J］．Neurocomputing，2016，207:735－753．

19 BEHNCK L P，DOERING D，PEREIRA C E，et al．A modified simulated annealing algorithm for SUAVs path planning［J］．IFAC-Papers Online，2015，48(10):63－68．

20 RASHEDIE，NEZAMABADI-POUR H，SARYAZDIS．GSA:a gravitational search algorithm［J］．Information Sciences，2009，179(13):2232－2248．

Path Planning Method Based on Grid-GSA for Plant Protection UAV

WANG Yu CHEN Haitao LIYu LIHaichuan
(College of Engineering，Northeast Agricultural University，Harbin 150030，China)

Due to the limited battery power and pesticide capacity，the plant protection UAV need return to the supply point frequently in the process of plant protection．With thework area increasing，more time would be spent on battery replacement，pesticide filling and round trips between each return pointand the supply point．So an appropriate path with the optimal return pointsmust be planned before starting the work，in order to minimize the total time and improve the efficiency of the plant protection．For the purpose，a research was conducted on the path planning method for the plant protection UAV．Firstly，aiming at building an environmentmodel which could describe the working area，the grid method was selected to divide the working area into small gridswith the initialized weights，which were depended on the working area’s size and shape．Secondly，the UAV was made to fly from the current grid to the adjacent one with the highest probability，which was calculated according to both the grids’initialized weights and the heading direction of the UAV．Incentive coefficients were added to the weights of the grids located in the front，left rear and right rear of the UAV so that the parallel routes were followed which moved from one extreme of the working area to the other alternately and turned at the boundary．Then the quantity and position of the return point could be outputted by controlling the distance in the sprayingmode．Thirdly，amathematicalmodelwas established．The quantities of the return times in the artificial planned path and the unplanned path were taken as the upper and lower limits of the search space respectively．The distance of each flight in the sprayingmode was chosen as the variable，and the dimensions ofwhich were depended on the search space．The objective was to obtain the optimal return points with the minimum time in the non-spraying mode．After that the gravitational search algorithm (GSA)was applied to solve themodel．Based on themethods and processes above，a new path planning method was proposed．Then themethod would output the planned path with return points automatically byinputting the data about the environment and the UAV such as the size of the working area，the direction of the crop row and the speed of the UAV．At last，for the test of the performance of the proposed path planningmethod，a 700m×100m working area with the irregular boundary was taken as an example for the path calculation．The path calculated by the proposed method was also compared with the artificial planned path and the unplanned path respectively，which showed the non-spraying distance of the proposed method was reduced by 14%and 68%，while the non-spraying time was reduced by 21%and 36%．Furthermore，a field experiment with the real UAV was used to test the proposed deviation rectification algorithm．Finally，the study indicated that the proposed method which could produce paths with lessworking timewas a reasonable，feasible and useful solution for the path planning problem of the plant protection UAV．

plant protection UAV;path planning;grid method;return point;gravitational search algorithm

TP301.6;V279+.2

A

1000-1298(2017)07-0029-09

2016-11-05

2017-02-04

公益性行业(农业)科研专项(201303011)和国家现代农业产业技术体系建设专项(CARS-04-PS22)

王宇(1989—)，男，讲师，主要从事农业机械化工程研究，E-mail:wang_neau@163．com

陈海涛(1962—)，男，教授，博士生导师，主要从事农业机械化工程与生物质材料研究，E-mail:CHT_neau@163．com

10．6041/j．issn．1000-1298．2017．07．004