无人机覆盖航迹规划中子区域合并方法设计

王文旭，李 立，李 俨

（西北工业大学 陕西 西安 710072）

无人机区域覆盖航迹规划 （Coverage Flight Path Planning，CFPP）定义为：在满足某种（某些）性能指标最优的前提下，避开障碍物和威胁源，规划出一条能够遍历待覆盖区域的最优飞行路线。在机器人领域，该技术称为区域覆盖路径规划（Coverage Path Planning，CPP）技术。

现今，国内外对覆盖航迹（路径）规划技术的研究主要集中在机器人领域，对无人机领域的研究相对较少。在机器人领域，覆盖路径规划技术的应用领域主要包括：室内清洁、擦窗、割草、自动喷漆、耕犁、播撒、检测探伤、排雷等。在无人机领域，覆盖航迹规划技术的应用领域主要包括：安全监控、战场侦察、目标搜索、地形测绘、矿藏勘测等[1]。

随着无人机在民用及军用领域应用范围的不断扩大，无人机对覆盖航迹规划技术的需求也更加的强烈。由于机器人和无人机所处的环境及特性都有所区别，很多在机器人领域得到成功运用的技术和方法，在无人机领域将不再适用。相对于机器人，无人机覆盖航迹规划的特点主要在于以下几点：

1）无人机不允许飞行过程中出现直角转弯、停止、侧移，甚至倒退等机动，而机器人则很容易实现上述机动；

2）无人机转弯时有最小转弯半径的限制，而机器人一般则没有；

3）无人机携带成像传感器的探测范围会随着无人机飞行高度、俯仰角、偏航角和滚转角的变化而变化，而机器人则不会出现这种情况。

文献[2]中给出了一种较为完整的2维平面上的无人机覆盖航迹规划的实现算法，其核心是子区域的分解。子区域分解的目的是为了将复杂的地形尽可能的简单化。其基本思想是运用分类的方法，将基本的几何图形从待覆盖区域表面分离出来。而后将每个区域沿着按照既定的规则生成覆盖的轨迹进行覆盖规划。本文考虑到在分解之后，应当重新合并一些相邻的子区域。由于在之前的区域分解步骤中将算法的步骤严格限定为覆盖完一个子区域之前不能进入下一个子区域，所以应当重新合并一些分解过多的区域。将一些区域合并到相邻的区域中可以降低整个算法设计的复杂度。因此，本文提出了一种相邻子区域间合并的算法，通过计算子区域的特性，设计相关规则对子区域进行合并，从而有效地简化覆盖的过程，加快无人机覆盖速率。

1 相邻子区域合并法

在文献[2]中，通过将一个复杂的区域分解为简单子区域的方式来将覆盖的问题简化，然后对每个子区域分别进行覆盖使得每个子区域内无人机的转弯次数达到最低，最后用尽可能短的路径将子区域连接起来，这样就得到了一个相对最优的航迹规划结果。

然而，由于方法选择的限制，无人机在将一个子区域完全覆盖前不会进入到下一个子区域中，这使得在覆盖某些相邻区域时，将带来很多不必要的转弯机动，如果用平滑的路径从一个区域过渡到另一个区域，将极大的减少这种损耗。如图1所示，按照原来的方法，整个区域将会被划分成两个子区域，然后按照顺序依次进行覆盖，在一个区域覆盖完成之前，无人机飞行到两区域的交界线时，将进行180度转弯，继续在原区域飞行，这样在两个区域的交界线上无人机会进行大量的转弯机动，这将带来极大的燃油和时间上的损耗（如图1所示）。我们可以通过制定更灵活的飞行策略来避免这种损耗，当无人机飞行到区域交界线时，用平滑的轨迹进入到下一个区域中，让两个区域在无人机的往复飞行中同时被覆盖（如图2所示）。这样，交界线上的大量转弯能够得到避免，以此节约大量的时间和燃油成本。

图1 依次覆盖子区域示意图Fig.1 An example of covering sub-regions one-by-one

图2 两个子区域过渡示意图Fig.2 Transition between sub-regions can save turning cost and head land area

下面我们开始讨论用以上思路，即合并一些相邻的子区域以此来减少区域边界上的转弯消耗，对航迹进行优化的具体方法。在子区域划分的步骤完成之后，子区域的边界可以分为两类，“原始边”（原区域边界，图3中实线所示）以及“插入边”（为分割子区域所加入的边，图3中虚线所示）。由于合并子区域时所消除的边一定是后来加入的，所以首先应当做的挑出出所有的“插入边”，然后逐个判断是否应当合并其所相邻的两个子区域。判断的结果可以根据如下判定函数来决定：

其中，F，Ft分别代表子区域合并前后转弯过程的损失函数；n1，n2为子区域合并前两区域在交界线处的转弯机动次数；θ1，θ2为两区域中航迹方向角；Li为相邻区域交界线的长度；φi为该交界线的方向角；Rc为子区域合并可能带来的覆盖率的损失；ε为协同系数。当D＞0时保留区域划分，当D＞0时，将该条边分割的两个子区域合并。

图3 子区域分解示意图Fig.3 Decomposition of the uncovered region

一般来讲，由于θ1，θ2与φi夹角的不同，两侧子区域与交界线相交的平行航迹的条数也不相同（如图4所示），这将会带来两个问题：第一，如何将交界线两边的航迹线两两配对，将之连接成一条新的整体的可行航迹，第二，两个子区域中平行航迹与交界线的交点是交错的，在完成配对后如何从一条航迹过渡到另外一条航迹[5]。

图4 相邻子区域扫描线条数不同Fig.4 One case with unequal numbers of rows on the two sides of the dividing line

2 子区域间轨迹衔接

整个转弯过程的损失，其实就是无人机转过|θ1－θ2|度角的过程的飞行消耗。首先想到的方法是不改变原有的航迹，在两条航迹与边界线的交点中间添加对应的过渡航迹。L.E.Dubin在1957年提出了名为Dubins曲线的理论[3]，在给定曲率的情况下寻找连接同一平面内具有特定方向向量的任意两点的最短轨迹曲线。如图5所示，对于起始向量和结束向量分别作两个切圆，其半径为无人机的最小转弯半径。Dubins曲线的最短路径即为两圆公切线和对应的过渡圆弧所连成的轨迹。

容易计算出，穿过交界线的次数为：

设内切线长度为L’，的方向角为φ’，沿内切线方向作辅助圆，可以得到 η=п/2－φ’（如图 6 所示）。此时（忽略直线飞行L’所带来的影响）：

图5 Dubins曲线过渡法Fig.5 Transition using Dubins curves

图6 损失函数计算示意图Fig.6 Calculation of cost function

可以看出，采用这种方法，从一个区域过渡到另一个区域的过程中，仍然需要进行大量的转弯机动，对于覆盖效率的提升并不明显，于是考虑一种更简单的方法：将两条航迹延长至相交，然后在两条航迹的交角处用最短的圆弧过渡（如图7所示）。此时

图7 转弯中平滑过渡示意图Fig.7 The smooth turning during transition

在转弯的过程中，由于两条相邻航迹间距离的不均匀，在拐角处会有一定的区域遗漏，如图8所示。两条航迹间损失区域的面积为

其中 α=|θ1-θ2|/2，全部面积损失为：

图8 覆盖损失面积计算示意图Fig.8 Calculation of cost area

3 相邻子区域扫描线配对

对于扫描线数量不相等的相邻子区域，路径的连接方法通常有两种：多出的扫描线可以通过外角连接（如图9所示），也可以通过内角连接（如图10所示）。对于这个问题，图10中的连接方式是更好的选择，这是因为采用图9中的连接方式会导致如下问题：当外角的路径确定后，内角的路径需要更小的转弯半径才能，这会导致内角的路径需要更小的转弯半径完成不同子区域间扫描线的过渡，而无人机存在最小转弯半径的限制，因此可能会导致规划出的路径是不可用的[5]。

图9 扫描线的外角连接Fig.9 Pair the swaths from outside corner

图10 扫描线的内角连接Fig.10 Pair the swaths from inside corner

4 算法实现

下面给出改进后算法的具体实现步骤以及一个实例

1）获取待覆盖区域的信息，将其边界简化为多边形的形式（如图11所示）；

2）根据无人机的飞行特性以及区域的特性，将带覆盖区域分解为凸多边形区域（如图12所示）；

3）对相邻子区域运用判定函数D进行计算，如果结果D＞0，则将其合并；

4）根据合并后的子区域规划出无人机的飞行路径（如图13所示）。

图11 待覆盖区域示意图Fig.11 Uncovered area

图12 子区域分解示意图Fig.12 Decomposition of uncovered area

图13 子区域合并及路径规划Fig.13 Combination of sub－regions and path planning

5 结 论

文中通过分析二维平面上多边形区域的特性，给出的无人机覆盖航迹规划中子区域合并的算法。按照本方法在整体的规划后需进行一次子区域的合并，将具有特定几何特性的相邻子区域合并为一个区域，这样就克服了之前一些算法在某些情形下子区域划分过多的缺点。无人机按照本方法规划的路径进行飞行时，可获得更少的转弯次数以及更短的航程，这样就节约了飞行成本并且提高的任务执行的效率，因此具有更好的实用性。

[1]陈海，王新民，焦裕松，等.无人机覆盖路径规划中转弯机动的运动学分析[J].飞行力学，2010（2）:31－34.CHEN Hai，WANG Xin-min，JIAO Yu-song，et al.Kinematics analysis of UAV turning motion in coverage path planning[J].Flight Dynamics，2010（2）:31－34.

[2]陈海，王新民，焦裕松，等.一种凸多边形区域的无人机覆盖航迹规划算法[J].航空学报，2010（9）:1802－1808.CHEN Hai，WANG Xin-min，JIAO Yu-song，et al.An algorithm of coverage flight path planning for UAVs in convex polygon areas[J].Acta Aeronautica et Astronautica Sinica，2010（9）:1802－1808.

[3]Dubins L.On plane curves with curvature[J].Pacific Journal of Mathematics，1961，11（2）:471－481.

[4]Shkel A M，Lumelsky V.Classification of the Dubins set[J].Robotics and Autonomous Systems，2001，34（4）:179－202.

[5]Jin J.Optimal field coverage path planning on 2D and 3D surfaces[J].Dissertations&Theses Gradworks，2009:152.

[6]Chazelle B.Dobkin D.Optimal convex decompositions[C]//In:Toussaint G.T.Ed.Computational GeometryAmslerdam:North－Holland，1985:63－133.

[7]Huang Y Q，Liu Y K.An algorithm for the clipping against a polygon based on shearing transformation [J].Computer Graphics Forum，2002，21（4）:683－688.