CN103699135B - 无人直升机农药喷洒农田作业区域的航迹自动规划方法 - Google Patents

Abstract

本发明公开了一种无人直升机农药喷洒农田作业区域的航迹自动规划方法，规划多边形农田作业区域任一起始顶点、任一起始航向的局部最优S型航迹规划和任一起始顶点、任一起始航向的局部最优“回”字型航迹，从局部最优S型航迹规划和局部最优“回”字型航迹分别找出全局最优S型航迹和全局最优“回”字型航迹。本发明方法克服了传统人工作业方式中人工规划航迹的不足，使无人直升机能在满足作业任务的前提下，降低各种成本消耗因素，提高喷洒效率。

Description

无人直升机农药喷洒农田作业区域的航迹自动规划方法

技术领域

本发明涉及无人直升机航迹规划领域,特别是一种无人直升机农药喷洒农田作业区域的航迹自动规划方法。

背景技术

在农业部的大力推进下，近年来我国在耕、播、收等方面的机械化水平有了显着提高，但农药喷洒（特别是水稻农药喷洒），基本上还是传统的人工操作。我国是一个农业大国，如何有效预防农业有害生物已成为我国农业生产的重要目标之一，特别是在国家大力提倡推广绿色农业、精准农业的过程中，适合我国农村现状的低成本、精确、高环保的农药喷洒机械化和自动化成为一个必不可少的技术，而利用小型无人直升机进行农药喷洒是农药喷洒机械化最佳选择。

在目前我国农村条件下，运用小型无人驾驶直升飞机喷洒农药是我国，特别是南方地区比较现实可行的一种方法。2012年长沙农业部门就签购了50架无人植保飞机用于农药喷洒作业。

无人驾驶农药喷洒直升机不仅速度快，且使用超低容量农药喷洒，节省农药和水资源，减少农作物的农药残留和环境污染，远程操作还能减少对施药人员的伤害。适应于各种地形，符合我市农村道路现状，配一台面包车便可实现跨区域作业。

目前，我国民用无人直升机正处在快速发展阶段，民用无人直升机的使用率越来越高，尤其是在农业领域，使用直升机可以极大地提高作业效率。但是由于无人直升机的可操控距离远，导致用人眼无法判断具体的飞行状态，如飞行方向、飞行距离等。缺乏对无人直升机在农田作业区域的飞行航迹进行合理有效的规划的方法，导致操作人员所选飞行路径并非最优；以及由于视觉误差所引起的漏喷、误喷、重喷，使喷洒效率降低，作业成本升高。

无人飞行器在完成任务过程中，需要对如何有效、安全地完成自己的任务过程进行规划，这就是所谓的任务规划。在任务规划过程中，最重要、也是最复杂的就是为无人飞行器规划出一条完成飞行任务所需要的飞行航迹，即无人飞行器航迹规划。

无人机航迹规划就是综合考虑各种因素，如：到达时间、飞行距离、燃料消耗、威胁以及飞行区域等，为无人机规划出一条最优，或者是最满意的飞行航迹，以保证圆满完成飞行任务。

无人直升机航迹规划有多种方法，如A*搜索法、Voronoi图算法、遗传算法、蚁群算法、粒子群优化算法和启发式搜索等。A*算法是一种经典的最优启发式搜索算法，一般多用于解决静态规划问题，在路径规划和图搜索中有着广泛的应用。该算法通过启发信息引导搜索，达到减小搜索范围、提高计算速度的目的。利用传统A*算法进行航迹搜索时，通常将规划环境表示为网格的形式，然后按照预先确定的代价函数寻找最小代价航迹。该方法对当前位置的每一个可能到达的网格单元计算代价，然后选择最低代价的网格单元加入搜索空间来探索。加入搜索空间的这一新网格单元又被用来产生更多的可能路径。Voronoi图是计算机几何学中一种重要的几何结构。McLain和Beard等提出了一种基于Voronoi图的多飞行器协同航迹规划方法。首先通过已知的地方雷达或威胁构造Voronoi图，Voronoi图的边界就是所有可飞的航迹，然后给出这些边界的权值，最后搜索最优航迹。遗传算法是模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型，是一种通过模拟自然进化过程搜索最优解的方法。用遗传算法进行航迹规划的一般步骤有：a）对航迹编码；b)构造合适的航迹评价函数；c)选择适合于航迹规划的遗传算子；d)计算并微调算子来获取最终解。蚁群算法是通过蚂蚁的信息交流和相互协作来实现路径搜索，该算法具有很好的通用性和鲁棒性。蚁群算法搜索路径的过程为：a)初始化飞行区域图上所有节点处的信息素，形成初始信息素矩阵；b)M只蚂蚁位于起始点A等待出发；c)每只蚂蚁根据状态转移规则选择网格图上的下一点，最终到达目标点，形成一条可行航路；d)计算各蚂蚁的可行航路的目标函数，保存最优航路解；e)根据目标函数，依据信息素调整准则对各点的信息素进行调整；f)查看最优解，判断是否要进行信息蒸发素因子P的调整，如果需要按一定规则进行相应调整；g)判断是否满足迭代条件（即是否达到设定的迭代次数或最小目标函数），若满足，则完成搜索；若不满足，则返回步骤b），重复执行，直到满足迭代条件。启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标。这样可以省略大量无谓的搜索路径，提高了效率。在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。

传统的启发式搜索以及其他路径搜索方法，在处理最短可达路径、最佳飞行航迹（时间短、油耗低、安全性高）、避开障碍物等方面拥有各自的优势，但是却都不适用于在农田作业的航迹规划。这是由于农田作业的特殊性决定的。主要表现在：

a)无人直升机在农田作业的航迹首先是必须覆盖全部的农田作业区域，这就与传统的最短或最佳飞行路径相异。

b)在满足覆盖全部作业区域的基础上，进一步考虑在整个区域的飞行路径以及飞行方式，即如何飞行可以使得作业效率最高。

c)飞行过程中还要考虑到油耗以及剩余农药量，当油耗或农药量不足时，需要返航添加后继续进行作业，其往返基站的路程也必须计算在整个规划方法内。

本发明的目的在于将传统启发式搜索算法应用于无人直升机的农田作业航迹规划中。

本发明中用到的名词解释如下：

航迹规划：飞行器能够满足飞行任务，并且满足约束条件的飞行轨迹。

无人直升机：无人驾驶直升机。

S型飞行航迹：是指无人直升机沿着预定航向飞行进行农药喷洒，到达边界点后侧飞一段距离，再按与原航向相反的方向飞行，由此形成弯曲的S型飞行航迹。

“回”字型飞行航迹：是指无人直升机沿着预定航向飞行进行农药喷洒，到达拐弯点后，悬停转弯，沿着下一条航向继续向前飞行，由此形成“回”字型飞行航迹。

基站：是一个基本工作站，当无人直升机燃油或农药不足时，可以返回基站为无人直升机添加燃油、农药后再出发继续作业。

发明内容

本发明所要解决的技术问题是，针对现有技术不足，提供一种无人直升机农药喷洒农田作业区域的航迹自动规划方法，对无人直升机在农田作业区域飞行航迹进行自动规划，生成全局最优S型飞行航迹和“回”字型飞行航迹，克服传统人工作业方式中人工规划航迹的不足，使无人直升机能在满足作业任务的前提下，降低各种成本消耗因素，提高喷洒效率。

为解决上述技术问题，本发明所采用的技术方案是：一种无人直升机农药喷洒农田作业区域的航迹自动规划方法，该方法为：

1）利用栅格法数字化多边形农田作业区域，将多边形农田作业区域划分为若干个栅格；所述多边形农田作业区域顶点个数为n；

2）为数字化后的多边形农田作业区域建立节点索引矩阵，以每一个栅格为一个节点，将每个栅格的地形信息存入所述节点索引矩阵；

3）定义以下代价函数h(n)：

$h\left(n\right)=\left\{\begin{array}{cc}1,& \stackrel{\→}{v}\∈I\\ 2,& \stackrel{\→}{v}\∈J\\ 3,& \stackrel{\→}{v}\∈K\end{array}\right.;$

其中，为无人直升机从当前节点飞行到下一个目标节点的速度向量；I为无人直升机直飞航向向量集合；J为无人直升机侧飞航向向量集合；K为无人直升机斜飞航向向量集合；

4）利用启发记忆式方法进行无人直升机航迹搜索，得到多边形农田作业区域所有起始顶点任意起始航向的局部S型最优飞行参考航迹以及多边形农田作业区域所有起始顶点任意起始航向的局部“回”字型最优飞行参考航迹，其中局部S型最优飞行参考航迹和局部“回”字型最优飞行参考航迹分别为2n条；

5）分别求解所述步骤4）中的2n条局部S型最优飞行参考航迹的代价值和2n条局部“回”字型最优飞行参考航迹的代价值；将2n条局部S型最优飞行参考航迹中代价值最小的局部S型最优飞行参考航迹定为全局最优S型航迹；将2n条局部“回”字型最优飞行参考航迹中代价值最小的局部“回”字型最优飞行参考航迹定为全局最优“回”字型航迹。

局部S型最优飞行参考航迹的获取方法为：

1）选择多边形农田作业区域一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点。

2）搜索与无人直升机飞行的当前节点相邻的所有节点，寻找满足约束条件的节点，将满足约束条件的相邻节点作为下一可能的目标节点；满足约束条件是指：在与当前节点相邻的节点中，寻找各个相邻节点在节点索引矩阵内对应的数值，数值最小的相邻节点即满足约束条件；

3）判断当前节点是否为转弯点，若是，则依次计算从当前节点到下一可能的目标节点的速度向量，选择与当前直飞航向向量夹角最小的节点作为下一个目标节点，进入步骤6）；若当前节点不是转弯点，则进入步骤4）；

4）利用代价函数h(n)计算从当前节点到所有下一可能的目标节点的代价值；

5）选择代价值最小的可能的目标节点作为下一个目标节点；

6）将所得到的下一个目标节点在所述节点索引矩阵内的值加1，表示此节点被探访一次，并将此节点放入到航迹节点序列表内；

7）将所得到的下一个目标节点作为下一次循环的当前节点，重复步骤2）～步骤6），直到遍历完数字化后的多边形农田作业区域内的所有节点，得到一条局部S型最优飞行参考航迹；

8）重复步骤1）～7），遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部S型最优飞行参考航迹，得到2n条局部S型最优飞行参考航迹。

局部“回”字型最优飞行参考航迹的获取方法为：

1）选择多边形农田作业区域一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点。

2）搜索与无人直升机飞行的当前节点相邻的所有节点，寻找满足约束条件的节点，将满足约束条件的相邻节点作为下一可能的目标节点；满足约束条件是指：在与当前节点相邻的节点中，寻找各个相邻节点在节点索引矩阵内对应的数值，数值最小的相邻节点即满足约束条件；

3）判断当前节点是否为转弯点，若是，则依次计算从当前节点到下一可能的目标节点的速度向量，选择与当前直飞航向向量夹角最小的节点作为下一个目标节点，并更新直飞航向向量集合I，侧飞航向向量集合J，斜飞航向向量集合K，进入步骤6）；若当前节点不是转弯点，则进入步骤4）；

4）利用代价函数h(n)计算从当前节点到所有下一可能的目标节点的代价值；

5）选择代价值最小的可能的目标节点作为下一个目标节点；

6）将所得到的下一个目标节点在所述节点索引矩阵内的值加1，表示此节点被探访一次，并将此节点放入到航迹节点序列表内；

7）将所得到的下一个目标节点作为下一次循环的当前节点，重复步骤2）～步骤6），直到遍历完数字化后的多边形农田作业区域内的所有节点，得到一条局部“回”字型最优飞行参考航迹；

8）重复步骤1）～7），遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部“回”字型最优飞行参考航迹，得到2n条局部“回”字型最优飞行参考航迹。

全局最优S型航迹的获取方法为：

1）计算每一条局部S型最优飞行参考航迹内，无人直升机的直飞距离x_p1、侧飞距离x_p5、起飞点距航迹起始点距离x_p2、中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回到无人直升机操作人员所在位置的距离x_p4；

2）计算每一条局部S型最优飞行参考航迹的代价值，其中局部S型最优飞行参考航迹p的代价值f(p)的计算公式为：其中w₁为无人直升机所有直飞距离之和的系数，w₂为无人直升机所有侧飞距离之和的系数，w₁+w₂=1；

3）将代价值最小的局部S型最优飞行参考航迹定为全局最优S型航迹。

全局最优“回”字型航迹的获取方法为：

1）计算每一条局部“回”字型最优飞行参考航迹内，无人直升机的直飞距离x_q1、转弯次数t、起飞点距航迹起始点距离x_q2、中途返航点距基站的距离x_q3；以及无人直升机作业完成后返回到无人直升机操作人员所在位置的距离x_q4；

2）计算每一条局部“回”字型最优飞行参考航迹的代价值，其中“回”字型最优飞行参考航迹q的代价值f(q)的计算公式为：

3）将代价值最小的局部“回”字型最优飞行参考航迹定为全局最优S型航迹

与现有技术相比，本发明所具有的有益效果为：本发明能对无人直升机在农田作业区域飞行航迹进行自动规划，生成全局最优S型飞行航迹和“回”字型飞行航迹，操作员可根据操作习惯和作业区域条件，任意选择其中一种航迹规划进行农药喷洒作业，本发明的方法克服了传统人工作业方式中人工规划航迹的不足，使其能在满足作业任务的前提下，降低各种成本消耗因素，提高喷洒效率；本发明实现了任意凸多边形农田作业区域任一起始顶点、任一起始航向的局部最优S型航迹规划和局部最优“回”字型航迹规划；本发明充分考虑了无人直升机在作业区域内飞行距离、拐弯次数、农药量、燃油量等成本因素，基于成本代价函数最小化原则，从局部最优S型航迹和局部最优“回”字型航迹中，选择出全局最优航迹，计算简单，容易实现；本发明可推广到任意形状的农田，包括凸多边形和凹多边形，其中凹多边形可分割成多个凸多边形，然后再使用本发明的方法对每一个凸多边形农田作业区域进行航迹规划。

附图说明

图1为本发明实施例中矩形农田区域ABCD示意图；

图2为本发明实施例中旋转后的农田作业区域显示图；

图3为本发明实施例中栅格化后的农田作业区域示意图；

图4为本发明实施例中节点索引矩阵建立示意图；

图5为本发明实施例中当前节点的相邻节点示意图；

图6为本发明实施例中下一可能的目标节点示意图；

图7为本发明实施例中下一步循环的当前节点图；

图8为本发明实施例中下一个目标节点值加1后的节点索引矩阵；

图9为本发明实施例得到的S型航迹线；

图10为本发明实施例原参考坐标系的S型航迹线；

图11为本发明实施例原参考坐标系的“回”字型航迹；

图12为无人直升机起飞点S点、基站M点、作业完成返航点E点均不在同一点的航迹示意图一；

图13为无人直升机起飞点S点、基站M点、作业完成返航点E点均不在同一点的航迹示意图二；

图14为本发明全局最优航迹规划流程图；

图15为本发明局部S型最优航迹规划流程图；

图16为本发明局部“回”字型最优航迹规划流程图。

具体实施方式

本发明方法如下：

（一）局部最优S型航迹规划

1.数字化农田作业区域

数字化地图是进行航迹规划的主要信息来源，国内外研究数字地图大多数采用栅格法，将地形分成等间距的栅格，栅格间距根据所需的实际情况选取。

本发明利用栅格法对农田作业区域数字化。即对于区域为((x,y)|0≤x≤a,0≤y≤b)的农田，将x轴与y轴按照给定的间距划分成小单元格，得到离散化的农田区域。

不失一般性，针对任意多边形农田区域，假设其顶点个数为n，那么可作为航迹规划的起始点就等于n。而对于每个起始顶点，为保证航迹能够覆盖整个区域，其最佳起始航向是延其左右两边直线飞行。因此对于每个起始顶点有两个飞行方向可供搜索。则一共有2n个S型可能航迹需要搜索。

2.航迹规划初始化

初始化内容包括：

1)创建数字地图的地形信息，划分作业区域和非作业区域。

具体实现方式是，为创建的数字化区域建立节点索引矩阵（NodeList）。每个栅格就是一个节点（以后均用节点表示），索引矩阵内存储着每个栅格单元的地形信息，作业区域用0表示，非作业区域用#表示。这样就建立了一个存储地形信息的节点索引矩阵。节点索引值用来表示当前节点的探访优先级，值越小优先级越高。节点索引矩阵具有记忆能力，当一个节点在搜索过程中被探访后，其索引矩阵内的值将+1，访问优先级就会下降。当作业区域的一个节点被探访后，其值就由0变为1，这时此节点的优先级下降。以此来实现搜索过程中，未探访节点始终拥有探访的最高优先级，引导启发式搜索能够遍历完作业区域内的所有节点，使规划的航迹满足农田作业的首要需求。

2)为搜索指定启发式信息

在启发式搜索中，对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。启发中的估价是用估价函数表示的，如：f(n)=g(n)+h(n)。其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最佳路径的估计代价。在这里主要是h(n)体现了搜索的启发信息，因为g(n)是已知的。当h(n)>>g(n)时，可以省略g(n)，从而提高效率。

无人直升机作业区域的航迹是必须经过作业区域内的所有节点，以保证覆盖所有作业区域，因此每一种航迹从起始点到作业结束，我们都需要指定从当前点到下一目标点的代价函数h(n)。

在定义代价函数之前，先需要了解几种飞行方式。无人直升机作业时的飞行方式有：直飞、侧飞、斜飞。考虑到无人直升机的实际操纵复杂度，这三者的优先级顺序依次是从高到低。那么在实际中，应尽量采用直飞进行作业，只有在到达边界或需要拐弯时才采用侧飞或者斜飞。因此，从当前节点到下一个目标节点采用不同的飞行方式，所需要的代价也是不一样的。

定义无人直升机直飞航向向量集合为I（集合I包含所有的直飞航向向量），侧飞航向向量集合为J，斜飞航向向量集合为K。从当前节点到下一个目标节点的速度为向量由于x轴与起始航向重合，所以I就是与x轴平行的单位向量的集合（比如向量（1，0）就属于I，（-1，0）也属于I），J就是与y轴平行的单位向量的集合，K就是平行于直线y=x的单位向量集合。

定义 $h\left(n\right)=\left\{\begin{array}{cc}1,& \stackrel{\→}{v}\∈I\\ 2,& \stackrel{\→}{v}\∈J\\ 3,& \stackrel{\→}{v}\∈K\end{array}\right.,$ 也就是说从当前节点到下一个目标节点的速度向量如果属于直飞航向向量集合I，那么所需代价为1，即为最小估计代价；如果属于侧飞航向向量集合J，那么所需代价为2；如果属于斜飞航向向量集合K，那么所需代价为3。这样定义是为了与实际操作符合。同时也体现了探访下一目标节点的优先级顺序，使其能够往估计代价最小的方向探访。

3.利用启发记忆式算法进行航迹搜索，得到2n条S型局部最优飞行参考航迹。具体实现方法为（见图15）：

Step1.选择一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点。

Step2.搜索与当前节点相邻的所有节点，寻找满足约束条件的节点，将符合条件的相邻节点作为下一步可能目标节点。约束条件为节点索引矩阵内值最小的相邻节点。

Step3.判断当前节点是否为转弯点。如果是转弯点，则依次计算从当前节点到下一可能节点的速度向量选择与当前直飞航向向量夹角最小的节点作为下一目标节点。执行Step6。

如果不是转弯点，跳转至Step4。

Step4.确定可能目标节点后，计算从当前节点到下一可能节点的所有代价值f(n)。f(n)=h(n)，h(n)由从当前节点到下一可能节点的速度向量决定。

Step5.对f(n)进行排序，选择f(n)值最小的作为下一个目标节点。

Step6.将得到的下一个目标节点作为下一步循环的当前节点，将其节点索引矩阵内的值+1，表示此节点被探访一次。并放入到航迹节点序列表内。

Step7.重复Step2至Step6，寻找下一航迹点，直到遍历完作业区域内所有节点，搜索过程完成。得到一条局部S型最优飞行参考航迹。

Step8.利用步骤1）～7），遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部S型最优飞行参考航迹，得到所有可能的2n条局部S型最优飞行参考航迹。

（二）局部最优“回”字型航迹规划

“回”字型航迹规划与S型航迹规划的数字化农田作业区域与航迹规划初始化是相同。不同点在于与S型相比，无人直升机在到达转弯点后会悬停转弯，改变其直飞航向。因此，利用启发记忆式算法进行航迹搜索过程与S型不同。下面主要针对不同点进行说明。

3.利用启发记忆式算法进行航迹搜索，得到任意起始顶点任意起始航向的一条“回”字型最优飞行参考航迹。具体实现方法为（见图16）：

Step1.选择一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点。

Step2.搜索与当前节点相邻的所有节点，寻找满足约束条件的节点，将符合条件的相邻节点作为下一步可能目标节点。约束条件为节点索引矩阵内值最小的相邻节点。

Step3.判断当前节点是否为转弯点。如果是拐弯点，则依次计算从当前节点到下一可能节点的的速度向量选择与当前直飞航向向量夹角最小的节点作为下一目标节点。执行Step6，并更新直飞航向向量集合I，侧飞航向向量集合J，斜飞航向向量集合K。其中集合I包括与从下一确定目标节点到当前节点的速度向量平行的所有单位向量，侧飞航向向量集合J包括与集合I垂直的所有单位向量，斜飞航向向量集合K包括与集合I向量夹角与45度的所有单位向量。

如果不是转弯点，跳转至Step4。

Step4.确定可能目标节点后，计算从当前节点到下一可能节点的所有代价值f(n)。f(n)=h(n)，h(n)由从当前节点到下一可能节点的速度向量决定。

Step5.对f(n)进行排序，选择f(n)值最小的作为下一个目标节点。

Step6.将得到的下一个目标节点作为下一步循环的当前节点，将其节点索引矩阵内的值+1，表示此节点被探访一次。并放入到航迹节点序列表内。

Step7.重复步骤Step2至步骤Step6，寻找下一航迹点，直到遍历完作业区域内所有节点，搜索过程完成。得到一条“回”字型局部最优飞行参考航迹。

Step8.利用步骤1）～7），遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部“回”字型最优飞行参考航迹，得到所有可能的2n条局部“回”字型最优飞行参考航迹。

（三）全局最优S型航迹和“回”字型航迹规划（见图14）

全局最优航迹规划在各局部最优的基础上，需综合考虑各种成本问题，下面分别讨论S型航迹和“回”字型航迹的全局最优规划。

1.全局最优S型航迹规划

全局最优S型航迹需要考虑的成本因素有：无人直升机在作业区域内的直飞距离、侧飞距离，无人直升机起飞点距某条航迹起始点的距离，无人直升机由于燃油或农药不足中途返航位置距基站的距离，以及无人直升机作业完成后返回的距离。为综合考虑以上各种因素，需提出一种全局最优S型航迹决策方法。该方法用于从所有局部最优S型航迹中判断选择全局最优航迹。

具体实现方法为：

Step1.计算每一条航迹p内，无人直升机的直飞距离x_p1、侧飞距离x_p5、；起飞点距航迹起始点距离x_p2；中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回的距离x_p4。

Step2.计算每一条航迹p的代价值f(p)，f(p)的计算公式为其中w₁为所有直飞距离之和的系数，w₂为所有侧飞距离之和的系数，w₁+w₂=1。

Step3.对所有代价值f(p)排序，代价值最小的即为全局最优S型航迹。

2.全局最优“回”字型航迹规划

全局最优“回”字型航迹需要考虑的成本因素有：无人直升机在作业区域内飞行距离、拐弯次数；无人直升机起飞点距某条航迹起始点的距离；无人直升机由于燃油或农药不足中途返航位置距基站的距离；无人直升机作业完成后返回的距离。为综合考虑以上各种因素，需提出一种全局最优“回”字型航迹决策方法。该方法用于从所有局部最优“回”字型航迹中判断选择全局最优航迹。

具体实现方法为：

Step1.计算每一条航迹p内，无人直升机的直飞距离x_p1、转弯次数t；起飞点距航迹起始点距离x_p2；中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回的距离x_p4。

Step2.计算每一条航迹p的代价值f(p)，f(p)的计算公式为其中w₁为所有直飞距离之和的系数，w₂为转弯次数的系数，w₁+w₂=1。

Step3.对所有代价值f(p)排序，代价值最小的即为全局最优“回”字型航迹。

至此，就实现了对无人直升机在农田作业区域最优飞行航迹规划。

下面结合附图和实施例对本技术方案做进一步详细说明。

（一）局部最优S型航迹规划

如图1所示的矩形农田区域ABCD，无人直升机可以选择任一顶点为起始顶点，以及以任一顶点相连的两条边为起始航向飞行。下面说明如何得到矩形农田区域ABCD所有8条局部最优S型航迹规划。

1.数字化农田作业区域

利用栅格法对农田作业区域数字化。即对于区域为((x,y)|0≤x≤a,0≤y≤b)的农田，将x轴与y轴按照给定的间距划分成小单元格，得到离散化的农田区域，间距大小由无人直升机喷洒农药宽幅决定。在此，将x轴与y轴按照单位长为5米的间距划分成小单元格，如图3所示。

2.航迹规划初始化

初始化内容包括：

1)创建数字地图的地形信息，划分作业区域和非作业区域。

具体实现方式是，为创建的数字化区域建立节点索引矩阵（NodeList）。每个栅格就是一个节点（以后均用节点表示），索引矩阵内存储着每个栅格单元的地形信息，作业区域用0表示，非作业区域用#表示。这样就建立了一个存储地形信息的节点索引矩阵。

2)为搜索指定启发式信息

定义无人直升机直飞航向向量集合为I（集合I包含所有的直飞航向向量），侧飞航向向量集合为J，斜飞航向向量集合为K。从当前节点到下一个目标节点的速度为向量

定义 $h\left(n\right)=\left\{\begin{array}{cc}1,& \stackrel{\→}{v}\∈I\\ 2,& \stackrel{\→}{v}\∈J\\ 3,& \stackrel{\→}{v}\∈K\end{array}\right.$

也就是说，从当前节点到下一目标节点速度向量如果属于直飞航向集合I，那么所需代价为1，即为最小估计代价。以此类推。

3.利用启发记忆式算法进行航迹搜索，得到矩形农田区域ABCD所有8条局部S型最优参考飞行航迹。具体实现方法为：

Step1.选择一个顶点A作为起始顶点并选择一条航向AB作为起始航向，将与起始顶点距离最近的节点作为当前节点。

Step2.搜索与当前节点（图5中的黑色圆点表示）相邻的所有节点，寻找满足约束条件的节点，将符合条件的相邻节点作为下一步可能目标节点。约束条件为节点索引矩阵内值最小的相邻节点。

根据Step2，得到的下一步可能目标节点如图6所示，带编号的三个黑色圆点即为下一步可能目标点。

Step3.判断当前节点是否为转弯点。如果是转弯点，则依次计算从当前节点到下一可能节点的速度向量选择与当前直飞航向向量夹角最小的节点作为下一目标节点。执行Step6。

如果不是转弯点，跳转至Step4。

Step4.确定可能目标节点后，计算从当前节点到下一可能节点的所有代价值f(n)。f(n)=h(n)，h(n)由从当前节点到下一可能节点的速度向量决定。

根据Step4，分别计算从当前节点点到带编号的三个黑色点的速度向量根据速度向量来计算到达每一可能目标点的代价值。到1号圆点的代价值为1，2号圆点的代价值为2，3号圆点的代价值为3。

Step5.对f(n)进行排序，选择f(n)值最小的作为下一个目标节点。

根据Step5可以确定1号圆点为下一个目标节点。

Step6.将得到的下一个目标节点作为下一步循环的当前节点，将其节点索引矩阵内的值+1，表示此节点被探访一次（如图8所示）。并放入到航迹节点序列表内。

如图7所示，1号圆点已成为下一步循环的当前节点。

Step7.重复Step2至Step6，寻找下一航迹点，直到遍历完作业区域内所有节点，搜索过程完成。得到一条局部S型最优飞行参考航迹。

根据Step7得到以A为起始顶点AB为起始航向的一条S型最优飞行参考航迹线。

Step8.利用步骤1）～7），依次遍历矩形农田作业区域的四个顶点A、B、C和D，分别规划出每一个顶点的局部S型最优飞行参考航迹，得到所有可能的8条局部S型最优飞行参考航迹。

图9显示了搜索的整个过程，并最终得到了一条S型航迹线。区域内黑色圆点表示航迹节点序列表中的点。

（二）局部最优“回”字型航迹规划

其过程与（一）所述一致，只是在第3步中到达转弯点后，需改变直飞航向，其最终结果如图11所示。

（三）全局最优S型航迹和“回”字型航迹规划

1.全局最优S型航迹规划

全局最优S型航迹需要考虑的成本因素有：无人直升机在作业区域内的直飞距离、侧飞距离，无人直升机起飞点距某条航迹起始点的距离，无人直升机由于燃油或农药不足中途返航位置距基站的距离，以及无人直升机作业完成后返回的距离。为综合考虑以上各种因素，需提出一种全局最优S型航迹决策方法。该系方法用于从所有局部最优S型航迹中判断选择全局最优航迹。

该系统具体实现方法为：

Step1.计算矩形ABCD每一条S型局部最优航迹p内，无人直升机的直飞距离x_p1、侧飞距离x_p5；起飞点距航迹起始点距离x_p2；中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回的距离x_p4。

下面以顶点A为起始点，AB为起始航向的S型航迹为例，计算其代价值f(p)。

假设无人直升机起飞点S点、基站M点、作业完成返航点E点均不在同一点，如图12所示。

首先计算该航迹内，无人直升机的直飞距离x_p1、侧飞距离x_p5。x_p1等于航迹内所有直飞线段之和。x_p5等于航迹内所有侧飞线段之和。

再计算起飞点S距航迹起始点A₁距离x_p2等于线段SA₁的长度；中途返航点距基站M的距离x_p3等于线段MA₂长度的2倍；作业完成后距返回点E的距离x_p4等于线段EA₃的长度。

Step2.计算该条航迹的代价值f(p)，f(p)的计算公式为其中w₁为所有直飞距离之和的系数，w₂为所有侧飞距离之和的系数，w₁+w₂=1。

系数w₁、w₂根据直飞速度与侧飞速度的比值计算出来

w₁=0.1，w₂=0.9

由此可以计算出该条航迹的代价值f(p)。

Step3.重复以上步骤，就可以计算出每一条局部最优S型航迹的代价值，对所有代价值f(p)排序，代价值最小的即为全局最优S型航迹。

由此，实现了全局最优S型作业参考航迹规划。

2.全局最优“回”字型航迹规划

全局最优“回”字型航迹需要考虑的成本因素有：无人直升机在作业区域内飞行距离、拐弯次数；无人直升机起飞点距某条航迹起始点的距离；无人直升机由于燃油或农药不足中途返航位置距基站的距离；无人直升机作业完成后返回的距离。为综合考虑以上各种因素，本发明提出一种全局最优“回”字型航迹决策方法。该方法用于从所有局部最优“回”字型航迹中判断选择全局最优航迹。

具体实现方法为：

Step1.计算矩形ABCD每一条局部最优“回”字型航迹p内，无人直升机的直飞距离x_p1、转弯次数t；起飞点距航迹起始点距离x_p2；中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回的距离x_p4。

下面以顶点A为起始点，AB为起始航向的“回”字型航迹为例，计算其代价值f(p)。

假设无人直升机起飞点S点、基站M点、作业完成返航点E点均不在同一点，如图13所示。

首先计算该航迹内，无人直升机的直飞距离x_p1、转弯次数t。x_p1等于航迹内所有直飞线段之和。t等于航迹内所有转弯点个数之和（带数字编号（1～4）的4个黑色圆点为转弯点）。

再计算起飞点S距航迹起始点A₁距离x_p2等于线段SA₁的长度；中途返航点距基站M的距离x_p3等于线段MA₂长度的2倍；作业完成后距返回点E的距离x_p4等于线段EA₃的长度。

Step2.计算该条航迹的代价值f(p)，f(p)的计算公式为其中w₁为所有直飞距离之和的系数，w₂为转弯次数的系数，w₁+w₂=1。

系数w₁、w₂根据直飞操作与转弯操作复杂度的比值计算出来

w₁=0.25，w₂=0.75

由此可以计算出该条航迹的代价值f(p)。

Step3.重复以上步骤，就可以计算出每一条局部最优“回”字型航迹的代价值，对所有代价值f(p)排序，代价值最小的即为全局最优“回”字型航迹。

由此，实现了全局最优“回”字型作业参考航迹规划。

Claims (4)

1.一种无人直升机农药喷洒农田作业区域的航迹自动规划方法，其特征在于，该方法为：

1)利用栅格法数字化多边形农田作业区域，将多边形农田作业区域划分为若干个栅格；所述多边形农田作业区域顶点个数为n；

2)为数字化后的多边形农田作业区域建立节点索引矩阵，以每一个栅格为一个节点，将每个栅格的地形信息存入所述节点索引矩阵；

3)定义以下代价函数h(n)：

其中，为无人直升机从当前节点飞行到下一个目标节点的速度向量；I为无人直升机直飞航向向量集合；J为无人直升机侧飞航向向量集合；K为无人直升机斜飞航向向量集合；

4)利用启发记忆式方法进行无人直升机航迹搜索，得到多边形农田作业区域所有起始顶点任意起始航向的局部S型最优飞行参考航迹以及多边形农田作业区域所有起始顶点任意起始航向的局部“回”字型最优飞行参考航迹，其中局部S型最优飞行参考航迹和局部“回”字型最优飞行参考航迹分别为2n条；

5)分别求解所述步骤4)中的2n条局部S型最优飞行参考航迹的代价值和2n条局部“回”字型最优飞行参考航迹的代价值；将2n条局部S型最优飞行参考航迹中代价值最小的局部S型最优飞行参考航迹定为全局最优S型航迹；将2n条局部“回”字型最优飞行参考航迹中代价值最小的局部“回”字型最优飞行参考航迹定为全局最优“回”字型航迹；

局部S型最优飞行参考航迹的获取方法为：

1)选择多边形农田作业区域一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点；

2)搜索与无人直升机飞行的当前节点相邻的所有节点，寻找满足约束条件的节点，将满足约束条件的相邻节点作为下一可能的目标节点；满足约束条件是指：在与当前节点相邻的节点中，寻找各个相邻节点在节点索引矩阵内对应的数值，数值最小的相邻节点即满足约束条件；

3)判断当前节点是否为转弯点，若是，则依次计算从当前节点到下一可能的目标节点的速度向量，选择与当前直飞航向向量夹角最小的节点作为下一个目标节点，进入步骤6)；若当前节点不是转弯点，则进入步骤4)；

4)利用代价函数h(n)计算从当前节点到所有下一可能的目标节点的代价值；

5)选择代价值最小的可能的目标节点作为下一个目标节点；

6)将所得到的下一个目标节点在所述节点索引矩阵内的值加1，表示此节点被探访一次，并将此节点放入到航迹节点序列表内；

7)将所得到的下一个目标节点作为下一次循环的当前节点，重复步骤2)～步骤6)，直到遍历完数字化后的多边形农田作业区域内的所有节点，得到一条局部S型最优飞行参考航迹；

8)重复步骤1)～7)，遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部S型最优飞行参考航迹，得到2n条局部S型最优飞行参考航迹。

2.根据权利要求1所述的无人直升机农药喷洒农田作业区域的航迹自动规划方法，其特征在于，局部“回”字型最优飞行参考航迹的获取方法为：

1)选择多边形农田作业区域一个顶点作为起始顶点并选择一条航向作为起始航向，将与起始顶点距离最近的节点作为当前节点；

2)搜索与无人直升机飞行的当前节点相邻的所有节点，寻找满足约束条件的节点，将满足约束条件的相邻节点作为下一可能的目标节点；满足约束条件是指：在与当前节点相邻的节点中，寻找各个相邻节点在节点索引矩阵内对应的数值，数值最小的相邻节点即满足约束条件；

3)判断当前节点是否为转弯点，若是，则依次计算从当前节点到下一可能的目标节点的速度向量，选择与当前直飞航向向量夹角最小的节点作为下一个目标节点，并更新直飞航向向量集合I，侧飞航向向量集合J，斜飞航向向量集合K，进入步骤6)；若当前节点不是转弯点，则进入步骤4)；

4)利用代价函数h(n)计算从当前节点到所有下一可能的目标节点的代价值；

5)选择代价值最小的可能的目标节点作为下一个目标节点；

6)将所得到的下一个目标节点在所述节点索引矩阵内的值加1，表示此节点被探访一次，并将此节点放入到航迹节点序列表内；

7)将所得到的下一个目标节点作为下一次循环的当前节点，重复步骤2)～步骤6)，直到遍历完数字化后的多边形农田作业区域内的所有节点，得到一条局部“回”字型最优飞行参考航迹；

8)重复步骤1)～7)，遍历多边形农田作业区域所有顶点，分别规划出每一个顶点的局部“回”字型最优飞行参考航迹，得到2n条局部“回”字型最优飞行参考航迹。

3.根据权利要求1所述的无人直升机农药喷洒农田作业区域的航迹自动规划方法，其特征在于，全局最优S型航迹的获取方法为：

1)计算每一条局部S型最优飞行参考航迹内，无人直升机的直飞距离x_p1、侧飞距离x_p5、起飞点距航迹起始点距离x_p2、中途返航点距基站的距离x_p3；以及无人直升机作业完成后返回到无人直升机操作人员所在位置的距离x_p4；

2)计算每一条局部S型最优飞行参考航迹的代价值，其中局部S型最优飞行参考航迹p的代价值f(p)的计算公式为：其中w₁为无人直升机所有直飞距离之和的系数，w₂为无人直升机所有侧飞距离之和的系数，w₁+w₂＝1；

3)将代价值最小的局部S型最优飞行参考航迹定为全局最优S型航迹。

4.根据权利要求2所述的无人直升机农药喷洒农田作业区域的航迹自动规划方法，其特征在于，全局最优“回”字型航迹的获取方法为：

1)计算每一条局部“回”字型最优飞行参考航迹内，无人直升机的直飞距离x_q1、转弯次数t、起飞点距航迹起始点距离x_q2、中途返航点距基站的距离x_q3；以及无人直升机作业完成后返回到无人直升机操作人员所在位置的距离x_q4；

2)计算每一条局部“回”字型最优飞行参考航迹的代价值，其中“回”字型最优飞行参考航迹q的代价值f(q)的计算公式为：

3)将代价值最小的局部“回”字型最优飞行参考航迹定为全局最优S型航迹。