【CICC原创】车机协同多区域覆盖侦察路径规划方法
摘要
针对小型无人机在战场区域侦察中的应用，提出了一种车机协同完成多区域覆盖侦察任务的新模式，汽车充当无人机的移动平台，携带无人机完成多个区域的扫描侦察任务。应用0-1整数规划建模技术，建立了优化汽车地面行驶路径和无人机空中飞行扫描路径的数学优化模型。设计了一种三阶段启发式算法，以快速求解车机路径规划方案。最后应用一个包含20个侦察区域的案例，验证了车机协同模式的优势和三阶段算法的有效性。
在现代战争中，无人驾驶飞机具有成本低、生存能力强、无人员损失风险、机动性好等优点，被广泛用于执行枯燥、恶劣、危险的作战任务，已经成为世界各国战场侦察的重要工具[1]，并在第四次中东战争、海湾战争、科索沃战争和后来的伊拉克战争中发挥了重要的作用[2]。
无人机战场侦察是利用无人机获取战场信息的活动，其中路径规划是无人机执行侦察任务的关键支撑技术，是无人机侦察任务规划领域的重要研究课题[3]。当前无人机侦察路径规划研究主要针对地面固定目标的侦察任务进行路径优化[4]。此外，也有一些考虑敌方雷达探测和地面障碍物的规避路径[5]，以及目标的侦察时间约束[6]等贴近战场实际情况的研究，研究领域也从单无人机向多无人机协同方向发展[7]。在实际战场侦察中，除了固定点目标，有些时候还需要获取某些特定区域内的所有详细信息，此时一般应用小型无人机对整个侦察目标区域进行覆盖扫描。小型无人机具有成本低、隐蔽性好、可以低空高精度扫描等优点，在军事和民用领域的区域覆盖扫描中有着广泛的应用[8]。龙国强等[9]提出集中式预先规划与分布式局部在线再规划相结合的方法，解决多无人机协同区域覆盖侦察问题。吴青坡等[10]研究了如何提高对复杂区域的侦察效率，高春庆等[11]首先将含障碍物的区域单元格化，然后为每一架无人机划分子覆盖区域，最后使用最小生成树的方法为每个子区域规划侦察路径。在民用方面，如评估灾区的破坏情况[12]，观察农业生产中的作物生长情况[13]和地形图的测绘[14]等，都需要优化无人机对目标区域的扫描路径。
当前无人机区域覆盖研究中，大多研究无人机如何对一个区域进行覆盖，通过规划无人机飞行路径，以尽可能低的成本完成整个区域的覆盖扫描[15]。很多时候，需要对多个战场区域进行扫描侦察，当多个区域分散在大范围战场的不同位置时，小型无人机续航能力低成为其完成任务的关键制约因素。
为了扩大小型无人机执行侦察任务的范围以完成多区域覆盖侦察任务，引入汽车作为无人机的移动平台，携带无人机在战场上进行大范围机动，构建车机协同战场侦察系统。汽车作为无人机的指控与保障平台，携带无人机从一个侦察区域机动到另一个侦察区域，并在机动过程中为无人机充电或更换电池。当汽车携带无人机达到某个目标侦察区域附近时，无人机从汽车起飞，飞到侦察区域上空完成该区域的覆盖侦察后返回汽车。汽车和无人机的结合可以有效扩大小型无人机的任务范围，提高战场多区域侦察的效率。Grocholsky等[16]为汽车和无人机协作进行空中和地面监视构建了模型和算法框架。罗志浩、刘忠等[17]建立了一个由地面车辆和无人机协作对多个点目标执行情报，监视和侦察（ISR）任务的数学模型，并通过试验表明车机协同模式可以显著提高ISR任务的完成效率。在民用领域，刘瑶等[18]使用模拟退火算法求解车载无人机协同配送的双层路径规划问题。Tokekar等人[19]结合了地面车辆和无人机的优势，设计了一个用于在农场的特定位置收集氮含量的系统，可以帮助农民有效减少肥料的使用。汽车和小型无人机协同系统在执行多种军事和民用领域的任务中具有显著优势。
当前车机协同路径规划的研究主要关注无人机对点目标的访问顺序和飞行路径，还没有多个区域覆盖侦察路径规划的相关研究。车机协同多区域覆盖侦察的路径规划面临更多新的研究挑战。问题中存在两层路径，其中空中无人机飞行路径与汽车在地面路网的行驶路径在不同的节点上相互连接。由于车辆和无人机之间在速度、续航时间和行驶方式方面的差异，在规划过程中需要考虑两种路径相互之间的影响。这种双层路径的交互作用使问题的解空间比传统路径问题更为复杂，求解难度更大。
1
数学模型
1.1 问题描述
在车机协同完成多个区域的覆盖侦察任务中，道路网络和侦察区域的位置、形状等信息都是已知的。汽车作为小型无人机的移动搭载平台，在行驶过程中可以为无人机充电和更换电池，同时也是无人机的指控中心。汽车的续航能力足以携带无人机完成整个侦察任务，但无人机的续航能力有限的，能够完成一个区域的覆盖侦察，在对不同区域侦察时，需要进行充电或更换电池。车机协同多区域覆盖侦察过程中，一辆汽车搭载一架小型无人机从基地出发，当行驶到需要侦察区域附近时，放飞无人机，由无人机飞到侦察区域上空进行全覆盖扫描并收集信息；无人机完成目标区域的覆盖扫描后，返回汽车，由汽车携带无人机行驶到下一个侦察区域，并在行驶过程中完成无人机的充电或更换电池工作；如此循环，汽车携带无人机在战场上机动，完成所有目标区域的侦察后，返回基地。汽车只能在侦察区域附近的一些特定点（称为临时停点）放飞和回收无人机，放飞无人机后，汽车可以等在原地回收无人机，也可以行驶到其他临时停点回收无人机。
图1 车机协同多区域覆盖侦察示例
Fig. 1 An example of multi-area coverage reconnaissance with cooperated ground vehicle and drone
图1给出了车机协同对3个区域进行侦察的示例。可以看出车机协同侦察过程中，汽车只能在地面路网上行驶，其访问所有侦察区域的路径规划属于典型的旅行商问题；无人机从汽车上出发，飞到侦察区域上空，对侦察区域进行连续覆盖扫描，属于典型的无人机航迹规划问题。同时汽车的路径需要和无人机的路径密切配合，在满足无人机的续航能力约束条件下，快速完成所有区域的侦察。如何优化车辆和无人机的路径，使得在不超出无人机最大续航能力的前提下以最短的时间完成对所有区域的覆盖，比单纯的求解旅行商问题和无人机航迹规划问题更加复杂，需要考虑两类路径的交互影响。
1.2问题建模
为了便于模型描述，表1给出了建模过程中应用的所有符号及其含义。
表1 符号及其含义
Table 1 Notations and their meaning
数学规划模型如下：
目标函数（1）最小化完成所有区域侦察的总时间，其中第1部分是汽车携带无人机在所有覆盖区域和基站之间转移的总行驶时间，第2部分是车载无人机在所有侦察区域进行覆盖扫描的飞行总时间。为了减少第1部分的时间，在不同侦察区域周围选择停点的标准之一是选择彼此之间Floyd距离较小的停点。为了减少第2部分的时间，一方面，在同一个区域内选取彼此之间Floyd距离小的停点；另一方面，选择合适的临时停点以使无人机的总飞行距离更短。
约束条件式（2）确保车载无人机必须从基站出发，完成所有覆盖任务之后返回同一个基站。约束条件式（3）确保每个临时停点的出度等于入度，从而确保车辆行驶路线的连通性。约束条件式（4）确保车辆进入每个侦察区域一次并离开该区域一次，即每个侦察区域只能访问一次。约束条件式（5）确保无人机只能在车辆所访问的临时停点起飞，而约束条件式（6）确保无人机只能在车辆所访问的临时停点降落。约束条件式（7）确保无人机只能在每个侦察区域起飞和降落一次。约束条件式（8）确保无人机在每个侦察区域飞行路径的连通性，并且与约束条件式（7）一起确保在每个侦察区域仅进行一次全覆盖扫描。约束条件式（9）确保无人机在扫描每个侦察区域时的飞行时间都不会超过其最大续航时间。约束条件式（10）和式（11）定义0-1变量的取值范围。
2
三阶段启发式算法设计
这里提出一种三阶段启发式算法来快速求解车机协同多区域覆盖侦察路径规划问题。第1阶段是分析侦察区域的几何特征，计算无人机的覆盖扫描路径；第2阶段是在无人机候选扫描路径的基础上，借鉴节约算法思想，规划汽车的行驶路径以及无人机在每个区域的放飞与回收点；第3阶段，采用局部搜索算法改进第2阶段构造的可行解，得到问题的最优解或近似最优解。
作为三阶段启发式算法的基础输入，需要首先计算出任意两点之间的Floyd距离。令表示从点i到点j的Floyd距离，由Floyd算法计算得出。Floyd算法（也称为插值方法）是一种使用动态编程的思想在给定加权图中找到多个点之间最短路径的算法，与Dijkstra的算法相似。Floyd算法的主要过程如下。
2.1 无人机路径规划算法
当无人机对一个区域进行覆盖扫描侦察时，首先需要分析侦察区域的形状，为无人机选择合适的扫描模式，如割草式扫描或螺旋式扫描；如果选择了割草式扫描，需要进一步检查侦察区域的凹凸性，当该区域为凹多边形时，要将其分解为多个凸多边形子区域；最后，根据无人机的相关性能参数计算覆盖区域的扫描飞行路径。
2.1.1 扫描方式的选取
应用无人机对一个区域进行覆盖扫描时，主要有两种扫描模式，即割草式扫描模式[20]和螺旋式扫描模式[21]。如图2给出了两种扫描模式下无人机的飞行路径。在图2中，用黑色边框包围的多边形表示侦察任务区域，黄色的圆表示扫描路径的起点和终点，蓝色虚线轨迹表示无人机的飞行路径，箭头表示无人机的飞行方向。两种扫描模式具体定义如下。
螺旋式扫描模式：无人机从侦察区域的中心开始，然后以恒定的螺旋间距向外逐渐扫描，直到覆盖完整个区域。也可从最外开始，螺旋向内扫描。
割草式扫描模式：无人机以平行航迹往复推进的方式从侦察区域边缘开始以等间隔距离扫描，直到覆盖完整个区域。
图2 螺旋式扫描模式和割草式扫描模式
Fig. 2 Spiral pattern and lawn mowing pattern
当前研究中大部分采用割草式扫描模式[22-23]，少数采用螺旋式扫描模式，没有研究多种扫描模式的选择优化。而实际工作中，同一区域采用不同的扫描模式时，扫描路径的总长度可能相差很大。例如，在图2中，由螺旋式扫描模式生成的飞行路径明显长于使用割草式扫描模式生成的飞行路径。然而，当侦察区域越接近圆形，使用螺旋式扫描比割草式扫描模式效果会越好。因此，可以根据覆盖区域与圆的接近程度选择不同的扫描模式。
多边形的圆度定义如下：
其中, S是侦察区域的面积，L是其周长。如果该区域更接近圆，则其圆度C更接近1。
为了分析对比两种典型扫描模式对不同圆度的多边形区域的扫描效率，表2给出了几种典型多边形分别采用两种扫描模式时的扫描时间。表2中所有的多边形的面积相等，取值为84个平方单位，无人机的扫描宽度设为2个单位，速度为1 单位/s。从表2中可以看出，当多边形的圆度较小时，割草式扫描模式的扫描时间明显小于螺旋式扫描模式的扫描时间。随着多边形的圆度逐渐变大，它们之间的差距越来越小。当多边形是正五边形(C=0.86)时，两种扫描模式的扫描时间基本相同。当多边形的圆度继续增加时，螺旋式扫描模式的时间变得比割草式扫描模式的时间更短。因此，通过试验观测可以总结如下近似规律：当侦察区域的圆度小于0.86时，割草式扫描模式较优；当圆度大于0.86时，螺旋式扫描模式较优。
表2 对于典型多边形使用两种扫描模式得到的扫描时间
Table 2 Scanning time for typical polygons by the two scanning patterns
2.1.2 凹多边形的判定与分解
当采用螺旋式扫描模式时，多边形的凹凸性对扫描时间的影响很小。然而，当采用割草式扫描模式时，多边形的凹凸性对其影响较大。使用割草式扫描模式生成的扫描路径需要在侦察区域为凸多边形的前提下进行规划的。当侦察区域是凹多边形，必须将凹多边形分解为一系列凸多边形子区域。
图3给出了一个凹多边形的分解示例。图3(a)中用实线包围的图形是要分解的凹多边形，在添加虚线之后，它变成凸多边形，其中蓝色边表示凸多边形的长轴，并且也是凹多边形的长轴。图3(b)表示将凹多边形沿着与其长轴平行的方向进行梯形分解，而图3(c)表示将梯形分解后的一系列凸多边形合并的过程。当两个相邻的凸多边形的一条边彼此重合并且两者长轴彼此平行时，可以将它们合并。该过程可以有效地减少凸多边形的数量，并避免无人机在不同凸多边形之间的不必要转移。图3(d)显示了使用割草式扫描模式产生的Boustrophedon路径。
图3 凹多边形的BCD分解和Boustrophedon路径生成
过程
Fig. 3 BCD decomposition of concave polygon’s and Boustrophedon path generation process
2.1.3 算法流程
基于无人机扫描模式选择和多边形区域分割方法，设计无人机对侦察区域进行覆盖扫描的飞行路径规划算法,总体流程如算法2所示。首先在给定侦察区域的几何信息、潜在临时停点的位置信息以及无人机飞行速度的条件下，计算侦察区域的周长和面积（第1行），然后计算侦察区域的圆度（第2行）。如果该区域的圆度大于0.86，则采用螺旋式扫描模式，然后获得扫描路径（第4行）以及路径的起点和终点（第5行）。扫描路径的长度在第6行中计算。如果圆度小于0.86，则采用割草式扫描模式。在这种情况下，首先检查该区域的凹凸性（第9行）。如果该区域是凹多边形（第10行），则使用上节设计的BCD方法（第11行）将其分解为一系列凸多边形，然后规划侦察区域的Boustrophedon路径。沿着平行于长轴的方向开始，有两条扫描路径（第13行），分别对应两对起点和终点（第14行）。计算两条路径的长度（第15~16行）。
2.2 车辆路径规划算法
车辆路径规划是通过优化汽车访问侦察区域的顺序和选择每个侦察区域附近的临时停点，一方面配合无人机的扫描路径使无人机的飞行时间较短，一方面优化汽车的行驶距离，使得汽车在整个任务过程中的行使时间较短。结合这两个方面，基于节约算法思想，设计了车辆的路径规划算法，如算法3所示。首先，根据全部点的位置信息计算Floyd距离矩阵dis（第1行），然后为每个区域选择扫描路径（第2行），得到扫描路径的起点和终点（第3行）。在每个侦察区域附近随机选择两个临时停点，然后计算无人机从一个临时停点起飞到扫描路径起点的距离和从扫描路径终点飞到另一个临时停点的距离，其中Dis是两个距离的和（第4-10行）。在每个侦察区域中，找到与最小距离Dis对应的两个临时停点作为该区域选定的停点（第12行）以形成停点集合goal（第14行），然后计算节约矩阵（第15-19行），并将其降序排列（第20行）。从最大值开始，将对应的两个侦察区域连接起来，直到包括所有的侦察区域，从而得到汽车和无人机路径规划的可行解（第21行）。
2.3 局部搜索算法
通过前面两个阶段无人机和车辆路径规划算法可以得到车机协同多区域侦察的较优方案，但很多时候可能还不是问题的最优解，还有改进的空间。因此，进一步设计车辆路径和无人机路径的局部搜索算法来改进解的质量。这里主要采用两类随机算子来进行局部搜索，第1类是随机交换两个侦察区域的访问顺序，搜索改进汽车行驶距离的可行解；第2类是随机交换汽车在某个侦察区域附近放飞和回收无人机的临时停点，搜索减少无人机飞行距离和（或）汽车行驶距离的可行解。通过随机调用这两类算子搜索不同的可行解，直到连续Nmax次没有改进时，停止搜索得到最终方案。
3
实验分析
下面通过一个典型算例给出模型和算法的应用示例，并说明车机协同进行多区域侦察的优势。所有计算实验均在华为笔记本电脑上进行，该笔记本电脑使用Core i7 1.8GHz四核处理器，16 GB内存，Windows 10操作系统，并且应用Matlab R2018a进行算法编码。
3.1 实验设计
在平面上生成的道路网络，该道路网络将平面分为49个正方形网格。将每个网格的边长设为10个单位，从49个网格中随机选择20个网格，在每个选中的网格中生成一个不规则多边形，如图4所示。按从左到右，从下到上的顺序对20个多边形区域进行编号。在所有多边形的每一条边上生成一个随机的临时停点，以蓝色星号表示，红色正方形表示基站。最后，将道路网络与覆盖区域用线段连接起来。汽车搭载无人机从基站出发对20个区域进行覆盖侦察，并在完成任务后返回基站。找到汽车和无人机的最佳路线，以完成对所有区域的扫描侦察。
图4 侦察区域和路网分布
Fig. 4 Reconnaissance area and road network distribution
车辆的平均速度设置为0.5单位/s，无人机的飞行速度设置为1单位/s。将无人机的扫描宽度设置为1个单位，最大续航时间设为140 s。局部搜索算法中Nmax设置为200。应用式（12）计算20个侦察区域的圆度，如表3所示。
从表3可以看出，区域1、3、6、11的圆度明显大于0.86，因此，采用螺旋式扫描模式，其余区域采用割草式扫描方式。区域2、12、14、16、17、18是凹多边形，使用先前设计的基于梯形分解的BCD方法分解它们，然后使用割草式扫描模式为它们规划Boustrophedon路径。
表3 20个侦察区域的圆度
Table 3 Roundness of 20 reconnaissance areas
3.2实验分析
如果单纯采用无人机对这些区域进行侦察，考虑到无人机的最大续航时间，以及无人机必须安全返回基地等限制，无人机无法飞到区域14、17、19、20，从而无法对这些区域进行侦察，剩下的区域虽然都在无人机的侦察范围内，但是只有区域1、2、3、5、8、9、11、12能够在无人机一次飞行过程中侦察完毕，其余区域都需要无人机不断地返回基站进行充电之后，再次前往区域进行侦察才能完成总的任务。因此，对于大范围的多区域侦察问题，单纯的小型无人机很难完成侦察任务。
图5 汽车和无人机的路径规划方案
Fig. 5 Path planning solutions for cooperated ground vehicle and drone
如果采用车机协同侦察的模式，应用三阶段启发式算法计算得到的可行解如图5所示，其中汽车访问20个区域的顺序为2-1-3-6-4-7-10-14-20-17-19-13-16-18-15-12-9-5-8-11。无人机扫描路径如图中所示，完成所有区域扫描侦察的总时间为2 379.71 s。三阶段启发式算法求解20个侦察区域的路径规划方案耗时18'32'。可以看出，车机协同模式可以高效完成单纯采用无人机无法完成的侦察任务，同时三阶段启发式算法可以有效解决车机协同带来的复杂路径规划问题，满足实际作用应用需求。
4
结论
随着智能化、无人化、自主化战争的快速发展，小型无人机在战场情报侦察中发挥着越来越大的作用。如何充分利用小型无人机在战场侦察中隐蔽性强、成本低、风险小的优势，同时克服其续航能力小的缺点，更好地发挥小型无人机的作战能力，是无人机指控领域的一个重要课题。车机协同是一种可行且高效的应用模式。针对车机协同多区域覆盖侦察的路径规划问题，提出了侦察区域扫描方式判定、无人机扫描路径规划以及汽车路径规划等系列方法，在此基础上，设计了一种三阶段启发式算法，来快速优化汽车和无人机的行驶路径。
车机协同多区域覆盖侦察路径规划属于路径规划领域的一个全新方向，当前的研究还处于起步阶段。通过解决一车一机协同区域覆盖侦察路径规划问题，验证了车机协同的优势。下一步该方向还有很多扩展研究方向，如一车多机、多车多机等更广泛的应用模式。同时，在车机协同规划中考虑敌方威胁规避、无人机随机损失等战场对抗因素的影响，研究更加体现战场不确定性的优化方法，也是车机协同领域具有重要实际价值的研究。
References
1 于力, 马振利, 江宝城. 外军军用无人机体系现状及发展趋势[J]. 飞航导弹, 2020(5): 34-39.
YU L, MA Z L, JIANG B C. Current status and develop ment trend of foreign military UAV systems[J]. Aerodynamic Missile Journal, 2020(5): 34-39.
2 杨晨, 张少卿, 孟光磊. 多无人机协同任务规划研究[J]. 指挥与控制学报, 2018, 4(3): 234-248.
YANG C, ZHANG S Q, MENG G L. Multi-UAV coop erative mission planning[J]. Journal of Command and Control, 2018, 4(3): 234-248.
3 庞强伟, 胡永江, 李文广, 等. 多无人机协同侦察任务规划方法研究综述[J]. 电讯技术, 2019, 59(6): 741-748.
PANG Q W, HU Y J, LI W G, et al. Research on Multi-UAV cooperative reconnaissance mission planning methods: an overview[J]. Telecommunication Engineering, 2019, 59(6): 741-748.
4 OBERMEYER K. Path planning for a UAV performing reconnaissance of static ground targets in terrain[C]// AIAA Guidance, Navigation, and Control Conference, 2009: 5888.
5 胡艺铭, 孙春生, 李佳宽, 等. 察打一体无人机末端突防路径规划方法研究[J]. 舰船电子工程, 2019, 39(5): 19-23.
HU Y M, SUN C S, LI J K, et al. Research on the motion planning of terminal penetration path for reconnaissance attack integrated UAV[J]. Ship Electronic Engineering, 2019, 39(5): 19-23.
6 王晨, 谢文俊, 赵晓林, 等. 动基地多无人机协同侦察问题研究[J]. 火力与指挥控制, 2019, 44(6): 59-63.
WANG C, XIE W J, ZHAO X L, et al. Research on mov ing-base Multi-UAV cooperative reconnaissance problem[J]. Fire Control & Command Control, 2019, 44(6): 59-63.
7 杨健, 董力勇, 王鸿, 等. 应用分层优化法的多协作无人机任务规划方法[J]. 指挥与控制学报, 2019, 5(1): 41-46.
YANG J, DONG L Y, WANG H, et al. Multiple coopera tive UAVs mission planning by hierarchical optimization method[J]. Journal of Command and Control, 2019, 5(1): 41-46.
8 AVELLAR G S C, PEREIRA G A S, PIMENTA L C A, et al. Multi-UAV routing for area coverage and remote sensing with minimum time[J]. Sensors, 2015, 15(11): 27783-27803.
9 LONG G Q, ZHU X P. Cooperative area coverage re connaissance method for Multi-UAV system[C]// Advanced Materials Research, Trans Tech Publications Ltd, 2012, 4141-4146.
10 吴青坡, 周绍磊, 闫实. 复杂区域多UAV覆盖侦察方法研究[J]. 战术导弹技术, 2016(1): 50-55.
WU Q P, ZHOU S L, YAN S. Multi-UAVs cooperative coverage reconnaissance in complex area[J]. Tactical Missile Technology, 2016(1): 50-55.
11 高春庆, 寇英信, 李战武, 等. 小型无人机协同覆盖侦察路径规划[J]. 系统工程与电子技术, 2019, 41(6): 1294-1299.
GAO Q C, KOU Y X, LI Z W, et al. Cooperative cover age path planning for small UAVs[J]. Systems Engineering and Electronics, 2019, 41(6): 1294-1299.
12 NEDJATI A, IZBIRAK G, VIZVARI B, et al. Complete coverage path planning for a Multi-UAV response system in post-earthquake assessment[J]. Robotics, 2016, 5(4): 26.
13 OKSANEN T, VISALA A. Coverage path planning algorithms for agricultural field machines[J]. Journal of Field Robotics, 2009, 26(8): 651-668.
14 MADJIDI H, NEGAHDARIPOUR S, BANDARI E. Vision-based positioning and terrain mapping by global alignment for UAVs[C]// Proceedings of the IEEE Conference on Advanced Video and Signal Based Surveillance, 2003. IEEE, 2003: 305-312.
15 OTTO A, AGATZ N, CAMPBELL J, et al. Optimization approaches for civil applications of unmanned aerial vehicles (UAVs) or aerial drones: A survey[J]. Networks, 2018, 72(4): 411-458.
16 GROCHOLSKY B, KELLER J, KUMAR V, et al. Cooperative air and ground surveillance[J]. IEEE Robotics & Automation Magazine, 2006, 13(3): 16-25.
17 LUO Z H, LIU Z, SHI J M, et al. The mathematical modeling of the two-echelon ground vehicle and its mounted unmanned aerial vehicle cooperated routing problem[C]// 2018 IEEE Intelligent Vehicles Symposium (IV), IEEE, 2018: 1163-1170.
18 LIU Y, SHI J M, WU G H, et al. Two-echelon routing problem for parcel delivery by cooperated truck and drone[J]. IEEE Transactions on Systems Man and Cybernetics: Systems, 2020, in(process): 1-20.
19 TOKEKAR P, VANDER H J, MULLA D, et al. Sensor planning for a symbiotic UAV and UGV system for precision agriculture[J]. IEEE Transactions on Robotics, 2016, 32(6): 1498-1511.
20 HUANG W H. Optimal line-sweep-based decompositions for coverage algorithms[C]// Proceedings 2001 ICRA. IEEE International Conference on Robotics and Automation, IEEE, 2001: 27-32.
21 MOON S W, SHIM D H C. Study on path planning algorithms for unmanned agricultural helicopters in complex environment[J]. International Journal of Aeronautical and Space Sciences, 2009, 10(2): 1-11.
22 MAZA I, OLLERO A. Multiple UAV cooperative searching operation using polygon area decomposition and efficient coverage algorithms[M]. Distributed Autonomous Robotic Systems 6, Springer, Tokyo, 2007: 221-230.
23 XU A, VIRIYASUTHEE C, RELLEITIS I. Optimal complete terrain coverage using an unmanned aerial vehicle[C]// 2011 IEEE International conference on robotics and automation, IEEE, 2011: 2513-2519.
24 CHOSET H. Coverage of known spaces: The boustrophedon cellular decomposition[J]. Autonomous Robots, 2000, 9(3): 247-253.
25 LI Y, CHEN H, ER M J, et al. Coverage path planning for UAVs based on enhanced exact cellular decomposition method[J]. Mechatronics, 2011, 21(5): 876-885.
26 COOMBES M, FLETCHER T, CHEN W H, et al. Optimal polygon decomposition for UAV survey coverage path planning in wind[J]. Sensors, 2018, 18(7): 21-32.
27 AKL S G, TOUSSIANT G T. A fast convex hull algorithm[J]. Information Processing Letters, 1978, 7(5): 219–222.
《指挥与控制学报》2020年第4期刊发，作者：夏阳升，石建迈，陈超，黄金才，程光权