基于栅格分区的覆盖路径规划方法

胡馨丹，杨盛毅，朱 力，宋云云

(1.贵州民族大学数据科学与信息工程学院，贵州 贵阳 550025；2.贵州省模式识别与智能系统重点实验室，贵州 贵阳 550025；3.贵州民族大学机械电子工程学院，贵州 贵阳 550025)

0 引言

针对无人机(unmanned aerial vehicle ，UAV)具有操作简便、体积小和机动性高[1]等特点，基于无人机的农业喷药必将成为一项重要的新技术，为作物防护产品提供高效、有效的应用[2]。无人机技术已被广泛用于不同的精准农业(PA)领域，如喷洒[3]、遥感监测[4]和作物生长检测[5]等。在农村农业的发展中，无人机技术更多的是应用于植保作业方面。对于农民来说，在农业生产经营中，需要考虑成本收益最大化。也即是在农田喷洒作业时，需要尽量减少漏喷、多喷，以及喷洒不均匀的问题。对于区域中含有不规则的障碍物的覆盖路径规划，文献[6]提出一种基于A*的覆盖路径规划算法，但重复率较高，转弯次数比较多。因此，本文提出一种基于障碍物分区的A*覆盖路径规划方法。

1 覆盖路径规划方法设计

为确保农用无人机能够在避开障碍物的同时，还能完成区域的药物喷洒。首先以农田环境信息为输入，以作业路径长度、转弯次数和重复点数为输出，整体的算法流程如图1所示。

图1 含障碍区域全覆盖路径规划流程

根据实际的作业环境，人工手持GPS打点，获得作业区域顶点坐标，以及障碍物顶点坐标，然后用黑色填充障碍物，白色填充无障碍区域。对于障碍物所占单元格不足一半的，视为无障碍单元，所占单元格超过一半的，视为障碍单元，从而得到作业环境栅格地图。在栅格地图中，用0表示无障碍单元，1表示障碍单元。对于存在有障碍物的作业区域，本文将进行区域分解。比较常用的方法有单元分解[7]、矩形分解[8]和聚类分解[9]。本文选用聚类分解进行区域划分。

2 栅格区域划分算法

对于栅格地图，为了便于遍历整个单元，且能避开障碍物，最有效的方法就是沿着障碍物边界进行划分，从而将整个地图划分为多个子区域。区域划分流程如图2所示。

2.1 模糊C均值聚类算法

模糊C均值(fuzzyC-means，FCM)是根据隶属度原则最大，从而判定每个数据点归属于某个聚类中心的一种聚类算法[10]。本文利用FCM聚类算法将栅格障碍物进行分类，然后找到每类障碍物x轴和y轴的最大值xmax、ymax和最小值xmin、ymin。

2.2 Bresenham算法

Bresenham算法是计算机图形学领域使用最广泛的直线扫描转换算法[11]。本文利用Bresenham算法得到分割线，如果障碍物中有多个最小值xmin的点，则找出其对应点的最小值ymin。如果障碍物中有多个最大值xmax的点，则找出其对应点的最大值ymax。从而得到栅格区域划分结果，如图3a所示，其中黑色虚线表示分割线。

根据图3a的分解结果，将区域分为9个子区域。然后按照从上到下，从左到右的顺序，将区域进行编号，为了后续处理节点间的访问顺序，以子区域中心点为该区域节点。

根据每个区域的最小和最大的横纵坐标值，求取每个区域的中心点Mi(xmi,ymi)，计算式为

(1)

xmaxi、xmini分别为第i个区域横坐标的最大值和最小值；ymaxi、ymini分别为第i个区域纵坐标的最大值和最小值；n为区域的个数。得到每个子区域中心点分布如图3a所示(黑色实心序号部分)。

图3 栅格分区

2.3 子区域合并

考虑子区域间存在一定的相似性，为了减少寻找各区域起始点的过程，使其能够进行区域间的连续喷洒作业，首先从左到右将相邻子区域宽度相同的区域合并在一起，对于图3a，可以将2、3、4、5和6这5个区域合并为新的区域，区域宽度不同的，则各为单独的区域。对于剩余单独区域，则按照子区域间的中心节点距离，满足小于某一阈值ε，再进行合并，本文设置ε=8，从而最终将区域分为3个子区域如图3b所示。本文将起始区域的起始点位于区域的左上角。

2.4 子区域覆盖路径顺序

子区域进行区域合并后，为了高效率实现农用无人机对喷洒区域进行覆盖，则每个子区域的覆盖只能遍历1次，因此将每个子区域视为1个节点，将节点连接成1条线，且只能经过1个节点，而且相连的2个节点还必须是相邻关系，由此将其转化成求解旅行商问题，所求的最短路径就是子区域间的遍历顺序。通过图3b发现子区域间是相邻的，因此可以直接对子区域进行自上而下的遍历顺序。

2.5 子区域间起点与终点的连接

以图3b为例，针对这3个矩形区域，每个矩形区域都有4个栅格单元，记为Mij(i=1,…,c，j=1,2,3,4)，其中，c为子区域个数，4个栅格单元从左上角开始顺时针排序得到4个单元的坐标点分别为Mi1(xmini1,ymini1)、Mi2(xmaxi2,ymini2)、Mi3(xmaxi3,ymaxi3)和Mi4(xmini4,ymaxi4)，如图4所示。

图4 矩形4个栅格单元示意图

由子区域的访问顺序，以区域的左上角坐标为进入点，考虑到覆盖路径长度以及重复率，则根据扫描方向，则每个子区域的进入点与出口点可分为：

a.如果子区域无障碍物，则农用无人机沿最长边方向作业，根据式(2)可得4个坐标点的关系。

(2)

b.如果子区域内部含有障碍物，则农用无人机沿最短边方向作业，根据式(3)可得4个坐标点的关系。

(3)

“⟺”的两侧为对应关系。

如果子区域进入点为左上角Mi1，当该子区域喷洒作业完成，出入点为Mi4，则下一个子区域的起点根据上面的2种情形可以直接得到为Mi+1,1。而子区域的连接有2种情况：

a.当下一子区域的进入点与Mi4无障碍，则当该子区域喷洒作业完成后，农用无人机直接直线移动1格到下一区域的进入点有2种情况,如果长边长度或短边长度为偶数，则进入点为Mi+1,1；如果长边长度或短边长度为奇数，则进入点为Mi+1,3。

b.当下一子区域的进入点与Mi4有障碍，即是农用无人机进入死区如图5所示。当前子区域完成作业后，下一区域的进入点为Mi+1,2，则2点之间的最优运动轨迹用A*算法求得。

图5 农用无人机进入死区

3 作业区域仿真实验分析

在MATLAB平台上，本文建立的栅格地图尺寸为15×18，农用无人机起始坐标为(1,1)，分别用本文方法、传统的A*覆盖算法和传统的遗传算法，进行仿真实验，仿真结果如图6所示。图6中的灰色栅格表示重复喷洒节点，黑色加粗线条为无人机飞行覆盖路径。根据3种方法进行仿真实验，得到的覆盖效率统计如表1所示。

图6 栅格环境3种方法覆盖路径比较

表1 覆盖路径规划方法比较

从覆盖路径长度来看，本文方法所得的覆盖路径是最优的，重复点数也是最少的，转弯次数虽然不是最优解，但也是次优解；从程序运行时间来看，本文方法是运行时间最少的，其次是A*算法，传统的遗传算法运行时间比较长，且A*算法还存在漏喷的问题，无法实现完全的覆盖。综合来看，本文方法与传统的A*覆盖算法和遗传覆盖算法相比，覆盖路径长度分别减少13.97%和3.78%，重复率分别降低了94.44%和83.33%，转弯次数分别减少16.00%和增加1.61%。可见本文方法有较优的性能，能够减少药物的损失和缩短电池能量的消耗。

4 结束语

针对传统的A*覆盖算法出现重复率高转弯次数多的问题，本文提出将FCM聚类算法与Bresenham算法相结合对含有多个障碍物的区域进行分区，然后按照从上到下的顺序遍历子区域。并分析子区域间出入点的连接问题，运用A*算法获得最优的连接路径。设计仿真实验，验证了算法的可行性。