本发明公开了一种影子跟随的多无人机区域覆盖路径规划方法，目的是解决多架无人机从单一起点出发导致起点周围冗余覆盖和无人机负载不均匀的问题。技术方案是：对已知目标区域进行预处理；计算内部障碍物集合的包围网格、待覆盖网格单元集合G中所有网格的连接关系和G中所有网格到起点的最短距离；采用影子跟随方法计算无人机的数量N和N架无人机的飞行路径集合P，计算无人机的前进位置时同步更新影子路径；使用负载均衡方法重规划P，N架无人机按照P中的路径从p1到pN的顺序执行覆盖任务。本发明使用最少的无人机数目通过每架无人机单次往返起点完成目标区域的覆盖任务，通过均衡多架无人机的任务负载，提高了整体的覆盖效率。
1.一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于包括以下步骤：
第一步，对已知的目标区域进行预处理；目标区域包括待覆盖区域的边界、待覆盖区域内的障碍物的位置和起点位置，充电站设置在起点处；通过分解的方式将目标区域T划分为形状大小相同的正方形网格单元；网格单元的边长记作R，R根据机载传感器的能力及任务要求确定；目标区域T中包括两类网格单元：待覆盖的网格单元g和障碍物网格单元m；待覆盖网格单元g组成的集合记作待覆盖网格单元集合G，障碍物网格单元m组成的集合记作障碍物网格单元集合M；其中，G内有一个网格单元作为起点，记作S；无人机从S出发执行覆盖任务，并在能量不足或者任务结束时返回S；M中的网格单元分为两类：边界障碍物集合Md和内部障碍物集合Me；Md中包括与目标区域边界具有连接关系的网格单元和与其它边界障碍物网格单元具有连接关系的网格单元，边界障碍物网格单元记作md；除了Md中的网格单元，M中的剩余网格单元为内部障碍物网格单元me组成了内部障碍物集合Me；这里的连接关系包括直接相邻关系和斜向相邻关系；直接相邻是指两个网格单元的中心距离等于R；斜向相邻是指两个网格单元的中心距离等于第二步，计算内部障碍物集合Me的包围网格、待覆盖网格单元集合G中所有网格的连接关系和G中所有网格到起点的最短距离，方法是：
2.1根据内部障碍物集合Me中的网格单元之间的连接关系对Me中的网格单元进行分组，分别计算每一组内部障碍物网格单元的包围网格并按照顺时针方向对包围网格排序，将排好序的包围网格均放到包围网格集合Sur中，Sur＝{Sur1,…,Surk,…,SurK},1≤k≤K，Surk为第k组排好序的包围网格的集合；包围网格指与Me中的任一网格单元具有连接关系的待覆盖网格单元；
2.2统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的直接相邻网格单元，将直接相邻网格单元分别保存至g1,...,gj,...gnum(G)的直接相邻网格单元集合中，得到g1,...,gj,...gnum(G)的直接相邻网格单元集合其中，num(G)表示G中网格单元的数目， 表示G中第j个网格
单元gj的直接相邻网格单元集合，1≤j≤num(G)；
2.3统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的斜向相邻网格单元，将斜向相邻网格单元保存至g1,...,gj,...gnum(G)的斜向相邻网格单元集合中，得到待覆盖网格单元的斜向相邻网格单元集合其中， 表示G中第j个网格单元gj的斜向相邻网格单元集
2.4在区域覆盖算法研究领域，当目标区域用正方形网格划分时，默认无人机的移动规则为从当前位置所在的网格单元向直接相邻网格单元移动，不能直接到达当前位置所在网格单元的斜向相邻网格单元；根据无人机从当前位置所在网格单元向直接相邻的网格单元移动的规则，计算G中每个待覆盖网格单元到起点S的最短距离，即g1,...,gj,...gnum(G)到S需要经过的最少的网格单元数目，记作 得到g1,...,gj,...gnum(G)到起点的最短距离集合 其中， 表示gj到S的最短距离；
第三步，计算无人机的数量N和N架无人机的飞行路径集合P；无人机的数量N在数值上等于单架无人机执行覆盖任务时，无人机往返起点的次数；P由N架无人机的飞行路径组成，即P＝{p1,...,pi,...pN}；基于影子跟随的单架无人机区域覆盖路径规划方法计算无人机往返起点的总次数；用pi表示无人机第i次从起点出发执行覆盖任务后回到起点的路径，1≤i≤N；pi由无人机飞行过程中经过的网格单元组成，即 其中，gim表示pi中的第m个网格单元，num(pi)表示pi中网格单元的总数；无人机N次往返起点后完全覆盖目标区域，即p1∪...∪pi∪...∪pN＝G；用有限飞行距离D表示无人机的有限机载能量；通过网格单元边长R将D转换成无人机最多可飞行的网格单元数目B，满足 基于影子跟随的单架无人机区域覆盖路径规划方法计算N和P的方法为：
3.1令无人机从起点出发，即初始化无人机的当前网格单元g的位置为S；初始化无人机的飞行路径集合P＝{}；初始化无人机往返起点的次数i＝1；令第i次往返起点的路径pi＝{S}，表示无人机从起点网格单元出发；令影子路径pw＝{S}，表示无人机沿影子路径返回起点网格单元；初始化G中的所有网格单元为未覆盖状态，设置g的状态state(g)为已覆盖状态，即令state(g)＝covered；初始化无人机的剩余飞行能力Brest＝B；初始化包围网格保存变量Sur′＝Sur；
3.2若G中还存在未覆盖状态的网格单元，转到第3.3步；否则，目标区域已被完全覆盖，转到第3.6步；
3.3根据无人机的当前网格单元g的位置、目标区域覆盖状态和障碍物信息，计算无人机下一步前往的网格单元gnext的位置；
3.4根据gnext找到影子路径的更新值 是不考虑包围网格单元的
影子路径更新值， 是考虑包围网格单元的影子路径更新值；
3.5根据无人机的剩余飞行能力Brest更新无人机的当前网格单元g的位置和影子路径pw，方法为：
3.5.1若无人机的剩余飞行能力Brest能够支撑无人机从g飞到gnext并沿着 返回起点，即满足 则更新无人机的剩余飞行能力，即将Brest更新为Brest‑len(g,gnext)；更新无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi最后一个网格单元后面；更新影子路径为 转到第3.5.4步；其中，len(g,gnext)表示从当前位置所在的网格单元g到目标网格单元gnext的最短距离； 表示从目标网格单元gnext到 的最后一个网格单元 的最短距离； 表
示从 的最后一个网格单元 经过 的网格单元到达 的第一个网
格单元 的最短距离；若无人机的剩余飞行能力Brest不能支撑无人机从g飞到gnext并沿着 返回起点，则转到第3.5.2步；
3.5.2若无人机的剩余飞行能力能够支撑无人机从g飞到gnext并沿着 返回起点，即满足 则更新无人机的剩余飞行能力，即将Brest更新为Brest‑len(g,gnext)；无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为已覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi的最后一个网格单元后面；更新影子路径为 转到第3.5.4步；其中，表示从当前位置所在的网格单元gnext到 的最后一个网格单元 的最短距
离； 表示从 的最后一个网格单元 经过 的网格单元到达
的第一个网格单元 的最短距离；若无人机的剩余飞行能力Brest不能支撑无人机从g飞到gnext并沿着 返回起点，则转到第3.5.3步；
3.5.3此时无人机剩余飞行能量不足以支撑无人机继续前进执行覆盖任务，须沿着影子路径pw返回起点补充能量，方法是：将pw中的网格单元从后向前依次加入到第i次往返起点的路径pi的末端，并设置每个加入的网格单元为已覆盖状态；无人机返回起点后令g＝S，更新路径索引值i,将i增加1，初始化第i条路径和影子路径为pi＝{g},pw＝{g}；令无人机在起点时剩余飞行能力等于最大可飞行网格单元数目Brest＝B，转到第3.5.4步；
3.5.4若包围网格单元集合Sur′中存在某组障碍物的包围网格单元为覆盖状态，则从Sur′中删除该组包围网格单元，转到第3.2步；
3.6目标区域已被完全覆盖，得到单架无人机往返起点的次数N＝i，令无人机群中无人机的数目等于N，无人机群的飞行路径集合P＝{p1,...,pi,...,pN}；
第四步，使用负载均衡方法重规划N架无人机组成的无人机群执行覆盖任务的飞行路径集合P，方法是：
4.1初始化无人机群中N架无人机的负载上限均为Bmax，令Bmax＝B；初始化N架无人机的负载下限均为Bmin，令Bmin＝2Bfar，Bfar为目标区域中距离起点最远的网格单元到起点的距离；
4.3计算新的单架无人机任务负载Bnew，Bnew＝Bmin+(Bmax‑Bmin)/N；
4.5将Bnew作为单架无人机的飞行能力，采用第三步所述的影子跟随的单架无人机区域覆盖路径规划方法，根据Bnew计算单架无人机往返起点的次数N′new和飞行路径集合P′new；令单架无人机最大负载等于Bnew时无人机群中无人机的数目Nnew＝N′new，无人机群中第inew架无人机的飞行路径 等于 无人机群的飞行路径集合为Pnew；其中，
4.6若Nnew大于无人机群中无人机的架数N，增大负载下限，即令Bmin＝Bnew，转到第4.2步；否则，减小负载上限，即令Bmax＝Bnew，并且更新每架无人机的飞行路径集合，即令P＝Pnew，转到第4.2步；
4.7得到无人机群的飞行路径集合P，无人机群中第i架无人机按照pi执行覆盖任务，P＝{p1,...,pi,...,pN}，1≤i≤N；
第五步，输出无人机群中无人机的数目N和飞行路径集合P。
2.如权利要求1所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于所述网格单元的边长 h为无人机的飞行高度，α为无人机上的机载摄像头的视野范围。
3.如权利要求1所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于
2.1步所述根据内部障碍物集合Me中的网格单元之间的连接关系对Me中的网格单元进行分组，分别计算每一组内部障碍物网格单元的包围网格并按照顺时针方向对包围网格排序的方法是：
2.1.1将Me中具有连接关系的网格单元划分为一组，不同组之间的网格单元不存在任何连接关系；令Me被分为K组，K为正整数；
2.1.3根据网格单元连接关系，找到第k组内部障碍物网格单元中每个网格单元的直接相邻和斜向相邻的网格单元，并将直接相邻和斜向相邻的网格单元保存至第k组包围网格集合Surk，并从集合Surk中删除碍物网格单元；此时集合Surk中的网格单元为第k组内部障碍物网格的包围网格；
2.1.4根据Surk中网格单元的位置，自下而上、自左向右对Surk中的网格单元进行排序和编号；位于左下角的网格单元编号值最小；根据编号值按升序重新排列Surk中的网格单元；
2.1.5初始化有序集合order＝{}，初始化网格单元记录栈stack＝{}，令当前网格单元位置g＝Surk[1]，即以Surk中编号值最小的网格单元作为遍历起点；
2.1.6从待覆盖网格单元集合G中找到所有与g直接相邻的网格单元，将找到的与g直接相邻的网格单元且位于Surk中的网格单元保存至与g直接相邻网格单元集合adg；
2.1.7若adg中有网格单元，转到第2.1.8步；否则，G中没有与g直接相邻且位于Surk中的网格单元，转到2.1.13步；
2.1.8若adg中有且仅有一个网格单元，将g放至order的末端，从Surk中删除g，此时g等于adg中仅有的网格单元，转到第2.1.6步；若adg中有多个网格单元，转到第2.1.9步；
2.1.9若g位于遍历起点，则将g放至order的末端，从Surk中删除g，此时g等于adg中编号值最小的网格单元，转到第2.1.6步；若g不位于遍历起点，则转到第2.1.10步；
2.1.10从adg中选择与order中最后一个网格单元具有相同的直接相邻障碍物网格单元的网格单元，记作gnext；
2.1.11若gnext的直接相邻网格单元中障碍物网格单元的数目≥2，将g压入stack栈顶，转到第2.1.12步；若gnext的直接相邻网格单元中障碍物网格单元的数目＜2，直接转到第
2.1.12将g放至order的末端，从Surk中删除g，令g＝gnext，转到第2.1.6步；
2.1.13查看stack的信息；若stack中没有保存网格单元，说明当前这一组内部障碍物的包围网格单元的遍历结束，转到第2.1.14步；若stack中有网格单元，则令g等于stack栈顶的网格单元，删除stack栈顶的网格单元，转到第2.1.6步；
2.1.14令Surk＝order，将Surk保存至包围网格集合Sur，更新索引值k，将k增加1；若k>K,说明所有包围网格单元均完成遍历和排序，得到Sur＝{Sur1,…,Surk,…,SurK},1≤k≤K，结束；否则，转到第2.1.3步。
4.如权利要求1所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于第三步基于影子跟随的单架无人机区域覆盖路径规划方法计算N和P时要求所有待覆盖网格单元到S的距离不超过2B。
5.如权利要求1所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于
3.3步所述根据无人机的当前网格单元g的位置、目标区域覆盖状态和障碍物信息，计算无人机下一步前往的网格单元gnext位置的方法是：
3.3.1找到G中所有与g直接相邻且为未覆盖状态的网格单元，保存至直接相邻网格单元集合adg；
3.3.2若adg为空集，则找到G中所有到g距离最短且为未覆盖状态的网格单元，保存至adg；
3.3.3若adg中仅有一个网格单元，则该网格单元作为无人机的目标网格单元gnext，结束；若adg中有多个网格单元，转到第3.3.4步；
3.3.4找到adg中网格单元到起点S的距离；距离越短，网格单元的优先级越高；距离相等，网格单元的优先级相同；将adg中低优先级的网格单元删除，仅保留优先级最高的网格单元；若adg中仅有一个网格单元，则将该网格单元作为无人机的目标网格单元gnext，结束；
若adg中有多个优先级最高的网格单元，转到第3.3.5步；
3.3.5计算adg中每个网格单元的直接相邻网格单元中，位于G中且为已覆盖状态的网格单元和障碍物网格单元的数目之和；adg中网格单元周围的已覆盖网格单元和障碍物网格单元的数目越多，adg中网格单元的优先级越高；数目相等，adg中网格单元的优先级相同；
adg中仅保留优先级最高的网格单元；若adg中仅有一个网格单元，则将该网格单元设为gnext，结束；若adg中仍有多个优先级最高的网格单元，转到第3.3.6步；
3.3.6根据路径pi中的最后一个网格单元得到上一个被覆盖的网格单元pi(end)，连接g和pi(end)组成线段，并沿着线段从g向外即与线段相反的方向做延长线，延长线为以g为起点的射线；以g为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线；根据延长线与adg中的网格单元相交的顺序给adg中的网格单元排序；延长线与adg中的网格单元越早相交，则adg中的网格单元的优先级越高；取adg中优先级最高的网格单元作为gnext，结束。
6.如权利要求5所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于
3.3.2步所述找到G中所有到g距离最短且为未覆盖状态的网格单元，保存至adg的方法是：
3.3.2.1计算G中网格单元到g的距离，方法是：g所在的网格单元到自身的距离等于0，标记g为0；与g直接相邻且不是障碍物的网格单元到g的距离等于1，标记与g直接相邻且不是障碍物的网格单元为1；遍历标记为1的网格单元的直接相邻网格单元，将不是障碍物且未标记的网格单元的标记值加一，即网格单元到g的距离等于2；按照广度优先的思想，标记G中的所有网格单元，得到G中所有网格单元到g的距离；
3.3.2.2若adg为空集，从G中到g距离等于2的网格单元开始，按照到g距离从小到大的顺序，查找G中未覆盖状态的网格单元；当找到G中第一个未覆盖网格单元时，记录找到的第一个未覆盖网格单元到g距离为dis；
3.3.2.3找到G中所有到g距离等于dis且为未覆盖状态的网格单元，保存至adg。
7.如权利要求1所述的一种影子跟随的多无人机区域覆盖路径规划方法，其特征在于
3.4步所述根据gnext找到影子路径的更新值 的方法是：
3.4.1初始化不考虑包围网格单元的影子路径更新值
3.4.2若 中含有gnext，删除 的最后一个网格单元，转到第3.4.3步；否则，转到第3.4.4步；
3.4.3若 中不含有gnext，转到第3.4.4步；否则，转到第3.4.2步；
3.4.4若 的最后一个网格单元 与gnext直接相邻，转到第3.4.8步；若与gnext不是直接相邻，转到第3.4.5步；
3.4.5将G中与gnext直接相邻且为非覆盖状态的网格单元保存至目标网格单元的相邻网格单元集合 若 中没有网格单元，转到第3.4.9步；若 中有且仅有一个网格单元，则将 中的网格单元放到 中最后一个网格单元 后面，转到第
3.4.9步；若 中有多个满足条件的网格单元，则转到第3.4.6步；
3.4.6计算 中的网格单元到 的最后一个网格单元 的距离；距离
越短， 中的网格单元优先级越高；距离相等， 中的网格单元优先级相同；删除中低优先级的网格单元，仅保留 中优先级最高的网格单元；若 中仅有一个网格单元，则将该网格单元放到 后面，转到第3.4.9步；否则， 中有多个最高优先级的网格单元，转到第3.4.7步；
3.4.7计算 中的网格单元到S的距离；距离越远， 中的网格单元优先级越高；
删除 中低优先级的网格单元，仅保留 中优先级最高的网格单元；若 中仅有一个网格单元，将该网格单元放到 后面，转到第3.4.9步；否则，转到第3.4.8步；
3.4.8连接g和gnext组成线段，并沿着线段从gnext向外即与线段相反的方向做延长线，延长线为以gnext为起点的射线；以gnext为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线；根据延长线与 中的网格单元相交的顺序给 中的网格单元排序；延长线与 中的网格单元越早相交，则 中的网格单元的优先级越高；取 中优先级最高的网格单元放到 后面；
3.4.10若 的最后一个网格单元 和gnext在Sur的同一组内部障碍物的包围网格单元Surk中，则从Surk中的 开始将有序的包围网格单元依次放到
后面，直到遇到Surk中的gnext，停止将包围网格放到 后面。
一种影子跟随的多无人机区域覆盖路径规划方法
技术领域
[0001] 本发明涉及无人机基于路径规划的区域覆盖领域，尤其涉及一种考虑有限机载能量约束的多架无人机往返相同起点的路径规划方法。
背景技术
[0002] 无人机作为智能无人系统的代表之一，因其高机动、高效用等优势，被广泛应用于各个领域、解决各种问题。区域覆盖是一类经典的路径规划问题，用于求解从起点开始遍历目标区域内所有点并且避开障碍物的规划路径。随着无人机技术的持续发展和不断降低的成本，无人机解决区域覆盖问题的实际应用十分广泛，例如农业植保中使用无人机执行农药喷洒，确保耕地内的农作物由农药全覆盖；地理测绘中使用无人机替代人力完成高寒或高海拔区域的全景测绘工作等。
[0003] 当目标区域范围较大时，若不考虑无人机在实际飞行过程中机载能量有限的约束条件，则可能因为无人机的飞行能力不足导致覆盖任务无法完成，造成未知的灾难。常用的考虑无人机有限能量的方法是在起点部署一个充电站。无人机在飞行能量不足时返回充电站补充能量并继续执行覆盖任务，多次充电操作使得无人机有能力完全覆盖目标区域。但是单架无人机在起点补充能量的操作延长了覆盖任务的完成时间，降低了覆盖任务的效率。使用多架无人机并行执行覆盖任务是提高任务执行效率的有效方法。
[0004] 多架无人机并行执行覆盖任务的问题可以拆分成两个子问题：第一个子问题是执行覆盖任务的无人机数目问题，第二个子问题是目标区域的划分与分配问题。当确定执行覆盖任务的无人机数目后，将目标区域划分为与无人机数量相等的子区域，再将每个子区域分配给无人机执行覆盖任务。
[0005] 针对第一个子问题，国际机器人与自动化大会(ICRA2011)上Hyeun Jeong Min等人发表的文章《The Multi‑robot Coverage Problem for Optimal Coordinated Searchwith an Unknown Number of Robots》(《机器人数量未知的最优多机器人协作覆盖问题》)中指出，机器人数目的增加不等同于覆盖任务执行效率的提高。此外，考虑到无人机数目的增加会带来无人机成本的提高，因此针对第一个子问题，多机覆盖任务的优化目标为保证覆盖任务执行效率的同时尽量减少无人机数目。当无人机的覆盖任务执行效率没有约束时，无人机的最少数目显然等于一。但是为了减少单架无人机在起点补充能量导致覆盖效率降低的问题，无人机的数目等于满足所有无人机均只往返起点一次且所有无人机经过的位点能够完全覆盖目标区域这两个条件的最小值。由于每架无人机均只往返起点一次(即从起点chu发，执行完覆盖任务由返回到起点)，无人机的数目在数值上等于单架无人机覆盖目标区域时往返起点的次数。因此，需要优化单架无人机的覆盖效率，提高单架无人机的覆盖效率。针对相同的目标区域，单架无人机的覆盖效率越高，无人机往返起点的次数越少。将无人机每次往返起点的路径分配给单架无人机，即能够使用更少的无人机数目完成目标区域的覆盖任务。
[0006] 考虑到无人机的机载能量有限，2016年IEEE自动化科学与工程学报(IEEE Transactions on Automation Science and Engineering)第13卷第2期上发表的文章《Online Coverage of Planar Environments by a Battery Powered Autonomous Mobile Robot》(《电池供电的自动移动机器人在线覆盖平面环境》)中将有限机载能量映射为速度为常数时的有限移动距离。当目标区域一定时，覆盖效率等于多无人机组成的无人机群完成覆盖任务的时间。覆盖效率取决于无人机群中执行覆盖任务时间最长的无人机。由于无人机的有限机载能量等于飞行速度为常数时的有限飞行距离，因此单架无人机执行覆盖任务的时间正比于无人机的飞行距离，即无人机群的覆盖效率取决于无人机群中飞行距离最长的无人机。因此，针对第二个子问题的优化目标为无人机数目一定且每架无人机只往返起点一次的条件下，最小化无人机群中的单架无人机的最长飞行距离。
[0007] 现有的多架无人机并行执行覆盖任务的方法中通常没有考虑无人机的有限机载能量，给定无人机的数量，将多架无人机的并行覆盖问题转化成目标区域的划分与分配问题。例如第21届地中海控制与自动化会议(2013)上Alessandro Renzaglia等人发表的文章《Distributed multi‑robot coverage using micro aerial vehicles》(《使用微型飞行器的分布式多机器人覆盖》)和2017年智能与机器人系统期刊(Journal of Intelligent&Robotic Systems)第86卷第3‑4期上发表的文章《DARP:Divide Areas Algorithm for Optimal Multi‑Robot Coverage Path Planning》(《DARP：用于优化多机器人覆盖路径规划的区域划分算法》)假设机器人的起始位置不同，将目标区域划分为相同的子区域分配给每个机器人。但是，设置多架无人机从不同的位置出发相当于强制使用额外的时间和代价将机器人移动到所需的起始位置，缺乏一定的实用性。
[0008] 因此，如何在多架无人机飞行能力相同且有限的情况下，使用最少的无人机数目，使得每架无人机单次往返相同起点的同时无人机群的覆盖效率最高是本领域人员亟需解决的技术问题。
发明内容
[0009] 本发明要解决的技术问题是针对多架无人机往返起点时从单一起点出发导致起点周围冗余覆盖和每架无人机负载不均匀的问题，提供一种影子跟随的多无人机区域覆盖路径规划方法。该方法主要包括两个目标：最小化无人机的数量和最小化每架无人机的飞行路径。
[0010] 针对第一个目标，本发明基于影子跟随的单无人机区域覆盖路径规划方法优化单架无人机的覆盖效率和能量利用率，将采用基于影子跟随的单无人机区域覆盖路径规划方法计算得到的无人机往返起点的路径数目从数值上等同于本发明中的无人机的数量。
[0011] 针对第二个目标，本发明通过约束无人机的最短飞行距离和最长飞行距离组成的飞行距离区间，使用负载均衡的方法在无人机数目不增加的条件下找到最短的无人机群的飞行距离，无人机群的飞行距离取决于无人机群中飞行距离最长的无人机。其中，单架无人机的最短飞行距离至少能够保证无人机有能力往返于目标区域的任意位置，即假设目标区域中距离起点最远位置到起点的距离为dfar，则单架无人机的最短飞行距离dmin应满足dmin≥2dfar；单架无人机的最长飞行距离取决于无人机的飞行能力，即假设无人机的有限机载能量在固定速度下的最长可飞行距离等于denergy，则单架无人机的最长飞行距离dmax应满足dmax≤denergy。
[0012] 本发明基于影子跟随的单无人机区域覆盖路径规划方法，提高单架无人机的能量利用率和覆盖效率。在保证覆盖效率的同时，使用最少的无人机数目，通过负载均衡方法优化无人机集群中每架无人机的任务分配，提高无人机集群的覆盖效率。本发明能提高覆盖任务的完成效率和无人机的能量利用率，确保集群中的每架无人机能够高效完成目标区域的覆盖任务，进而提高整个集群的完成效率。
[0013] 本发明包括以下步骤：
[0014] 第一步，对已知的目标区域进行预处理。目标区域包括待覆盖区域的边界、待覆盖区域内的障碍物的位置和起点位置，充电站设置在起点处。通过分解的方式将目标区域T划分为形状大小相同的正方形网格单元。网格单元的边长记作R，R根据机载传感器的能力及任务要求确定。 h为无人机的飞行高度，α为无人机上的机载摄像头的视野范围。目标区域T中包括两类网格单元：待覆盖的网格单元g和障碍物网格单元m。待覆盖网格单元g组成的集合记作待覆盖网格单元集合G，障碍物网格单元m组成的集合记作障碍物网格单元集合M。其中，G内有一个网格单元作为起点，记作S。无人机从S出发执行覆盖任务，并在能量不足或者任务结束时返回S。M中的网格单元分为两类：边界障碍物集合Md和内部障碍物集合Me。Md中包括与目标区域边界具有连接关系的网格单元和与其它边界障碍物网格单元具有连接关系的网格单元，边界障碍物网格单元记作md。除了Md中的网格单元，M中的剩余网格单元为内部障碍物网格单元me组成了内部障碍物集合Me。这里的连接关系包括直接相邻关系和斜向相邻关系。直接相邻是指两个网格单元的中心距离等于R；斜向相邻是指两个网格单元的中心距离等于
[0015] 第二步，计算内部障碍物集合Me的包围网格、待覆盖网格单元集合G中所有网格的连接关系和G中所有网格到起点的最短距离，方法是：
[0016] 2.1根据内部障碍物集合Me中的网格单元之间的连接关系对Me中的网格单元进行分组，分别计算每一组内部障碍物网格单元的包围网格并按照顺时针方向对包围网格排序，将排好序的包围网格均放到包围网格集合Sur中，Sur＝{Sur1,...,Surk,...,SurK},1≤k≤K，Surk为第k组排好序的包围网格的集合。包围网格是指与Me中的任一网格单元具有连接关系的待覆盖网格单元。
[0017] 具体步骤为：
[0018] 2.1.1将Me中具有连接关系的网格单元划分为一组，不同组之间的网格单元不存在任何连接关系。令Me被分为K组，K为正整数。
[0019] 2.1.2初始化索引值k＝1。
[0020] 2.1.3根据网格单元连接关系，找到第k组内部障碍物网格单元中每个网格单元的直接相邻和斜向相邻的网格单元，并将直接相邻和斜向相邻的网格单元保存至第k组包围网格集合Surk，并从集合Surk中删除碍物网格单元。此时集合Surk中的网格单元为第k组内部障碍物网格的包围网格。
[0021] 2.1.4根据Surk中网格单元的位置，自下而上、自左向右对Surk中的网格单元进行排序和编号。位于左下角的网格单元编号值最小。根据编号值按升序重新排列Surk中的网格单元。
[0022] 2.1.5初始化有序集合order＝{}，初始化网格单元记录栈stack＝{}，令当前网格单元位置g＝Surk[1]，即以Surk中编号值最小的网格单元作为遍历起点。
[0023] 2.1.6从待覆盖网格单元集合G中找到所有与g直接相邻的网格单元，将找到的与g直接相邻的网格单元且位于Surk中的网格单元保存至与g直接相邻网格单元集合adg。
[0024] 2.1.7若adg中有网格单元，转到第2.1.8步；否则，G中没有与g直接相邻且位于Surk中的网格单元，转到2.1.13步。
[0025] 2.1.8若adg中有且仅有一个网格单元，将g放至order的末端，从Surk中删除g，此时g等于adg中仅有的网格单元，转到第2.1.6步；若adg中有多个网格单元，转到第2.1.9步。
[0026] 2.1.9若g位于遍历起点，则将g放至order的末端，从Surk中删除g，此时g等于adg中编号值最小的网格单元，转到第2.1.6步；若g不位于遍历起点，则转到第2.1.10步。
[0027] 2.1.10从adg中选择与order中最后一个网格单元具有相同的直接相邻障碍物网格单元的网格单元，记作gnext。
[0028] 2.1.11若gnext的直接相邻网格单元中障碍物网格单元的数目≥2，将g压入stack栈顶，转到第2.1.12步；若gnext的直接相邻网格单元中障碍物网格单元的数目＜2，直接转到第2.1.12步。
[0029] 2.1.12将g放至order的末端，从Surk中删除g，令g＝gnext，转到第2.1.6步；
[0030] 2.1.13查看stack的信息。若stack中没有保存网格单元，则说明当前这一组内部障碍物的包围网格单元的遍历结束，转到第2.1.14步；若stack中有网格单元，则令g等于stack栈顶的网格单元，删除stack栈顶的网格单元，转到第2.1.6步。
[0031] 2.1.14令Surk＝order，将Surk保存至包围网格集合Sur，更新索引值k＝k+1。若k>K,则说明所有包围网格单元均完成遍历和排序，此时Sur＝{Sur1，...，Surk,...,SurK},1≤k≤K，转到第2.2步；否则，转到第2.1.3步，继续遍历内部障碍物的包围网格单元。
[0032] 2.2统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的直接相邻网格单元，将直接相邻网格单元分别保存至g1,...,gj,...gnum(G)的直接相邻网格单元集合中，得到g1,...,gj,...gnum(G)的直接相邻网格单元集合其中，num(G)表示G中网格单元的数目， 表示G中第j个网格单
元gj的直接相邻网格单元集合，1≤j≤num(G)。
[0033] 2.3统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的斜向相邻网格单元，将斜向相邻网格单元保存至g1,...,gj,...gnum(G)的斜向相邻网格单元集合中，得到待覆盖网格单元的斜向相邻网格单元集合其中， 表示G中第j个网格单元gj的斜向相邻网格单元集
合。
[0034] 2.4在区域覆盖算法研究领域，当目标区域用正方形网格划分时，默认无人机的移动规则为从当前位置所在的网格单元向直接相邻网格单元移动，不能直接到达当前位置所在网格单元的斜向相邻网格单元，参见国际机器人与自动化大会(ICRA 2018)上Minghan Wei和Volkan Isler发表的文章《Coverage Path Planning Under the Energy Constraint》(《能源约束下的路径规划与覆盖》)。根据无人机从当前位置所在网格单元向直接相邻的网格单元移动的规则，计算G中每个待覆盖网格单元到起点S的最短距离，即g1,...,gj,...gnum(G)到S需要经过的最少的网格单元数目，记作 得
到g1,...,gj,...gnum(G)到起点的最短距离集合 其中，
表示gj到S的最短距离。
[0035] 第三步，计算无人机的数量N和N架无人机的飞行路径集合P。无人机的数量N在数值上等于单架无人机执行覆盖任务时，无人机往返起点的次数；P由N架无人机的飞行路径组成，即P＝{p1,...,pi,...pN}。这里基于影子跟随的单架无人机区域覆盖路径规划方法，计算无人机往返起点的总次数。用pi表示无人机第i次从起点出发执行覆盖任务后回到起点的路径，1≤i≤N。pi由无人机飞行过程中经过的网格单元组成，即其中，gim表示pi中的第m个网格单元，num(pi)表示pi中网格单
元的总数。无人机N次往返起点后完全覆盖目标区域，即p1∪...∪pi∪...∪pN＝G。基于影子跟随的单架无人机区域覆盖路径规划方法，在计算目标网格单元的同时更新影子路径，使得无人机在能量不足时可以沿着影子路径返回起点，在不破坏未覆盖目标区域连续性的同时执行覆盖任务，提高单架无人机的覆盖效率，减少无人机往返起点的次数。采用国际机器人与自动化大会(ICRA2018)上Minghan Wei和Volkan Isler发表的文章《Coverage Path Planning Under the Energy Constraint》(《能源约束下的路径规划与覆盖》)中的假设，即用有限飞行距离D表示无人机的有限机载能量。通过网格单元边长R将D转换成无人机最多可飞行的网格单元数目B，满足 为保证无人机有能力完成目标区域的覆盖任务，要求所有待覆盖网格单元到S的距离不超过2B，否则需要飞行能力更优的无人机执行覆盖任务。
[0036] 基于影子跟随的单架无人机区域覆盖路径规划方法计算N和P的具体步骤为：
[0037] 3.1令无人机从起点出发，即初始化无人机的当前网格单元g的位置为S；初始化无人机的飞行路径集合P＝{}；初始化无人机往返起点的次数i＝1。令第i次往返起点的路径pi＝{S}，表示无人机从起点网格单元出发；令影子路径pw＝{S}，表示无人机沿影子路径返回起点网格单元。初始化G中的所有网格单元为未覆盖状态，设置g的状态state(g)为已覆盖状态，即令state(g)＝covered。初始化无人机的剩余飞行能力Brest＝B，即无人机剩余可飞行的网格单元数目在初始状态时等于无人机的最多可飞行网格单元数目。初始化包围网格保存变量Sur′＝Sur，以保存Sur的初始值。
[0038] 3.2若G中还存在未覆盖状态的网格单元，转到第3.3步；否则，目标区域已被完全覆盖，转到第3.6步。
[0039] 3.3根据无人机的当前网格单元g的位置、目标区域覆盖状态和障碍物信息，计算无人机下一步前往的网格单元gnext的位置。
[0040] 具体步骤为：
[0041] 3.3.1找到G中所有与g直接相邻且为未覆盖状态的网格单元，保存至直接相邻网格单元集合adg。
[0042] 3.3.2若adg为空集，则找到G中所有到g距离最短且为未覆盖状态的网格单元，保存至adg，方法为：
[0043] 3.3.2.1计算G中网格单元到g的距离，方法是：g所在的网格单元到自身的距离等于0，标记g为0；与g直接相邻且不是障碍物的网格单元到g的距离等于1，标记与g直接相邻且不是障碍物的网格单元为1；遍历标记为1的网格单元的直接相邻网格单元，将不是障碍物且未标记的网格单元的标记值加一，即网格单元到g的距离等于2；按照广度优先的思想，标记G中的所有网格单元，得到G中所有网格单元到g的距离。
[0044] 3.3.2.2当adg为空集时，说明G中所有与g直接相邻的网格单元均为已覆盖状态，即G中到g距离等于1的网格单元均为已覆盖状态。因此，从G中到g距离等于2的网格单元开始，按照到g距离从小到大的顺序，查找G中未覆盖状态的网格单元。当找到G中第一个未覆盖网格单元时，记录找到的第一个未覆盖网格单元到g距离为dis。
[0045] 3.3.2.3找到G中所有到g距离等于dis且为未覆盖状态的网格单元，保存至adg。
[0046] 3.3.3若adg中仅有一个网格单元，则该网格单元作为无人机的目标网格单元gnext，转到第3.4步；若adg中有多个网格单元，转到第3.3.4步。
[0047] 3.3.4找到adg中网格单元到起点S的距离。距离越短，网格单元的优先级越高；距离相等，网格单元的优先级相同。将adg中低优先级的网格单元删除，仅保留优先级最高的网格单元。若adg中仅有一个网格单元，则将该网格单元作为无人机的目标网格单元gnext，转到第3.4步；若adg中有多个优先级最高的网格单元，转到第3.3.5步。
[0048] 3.3.5计算adg中每个网格单元的直接相邻网格单元中，位于G中且为已覆盖状态的网格单元和障碍物网格单元的数目之和。若网格单元周围的已覆盖网格单元和障碍物网格单元的数目越多，说明这个网格单元直接相邻的未覆盖网格单元数目越少。如果不优先覆盖这个网格单元，则可能出现这个网格单元周围没有直接相邻的未覆盖网格单元，导致覆盖这个网格单元时需要经过其它已覆盖的网格单元，造成重复覆盖，浪费无人机的有限能量。因此，adg中网格单元周围的已覆盖网格单元和障碍物网格单元的数目越多，adg中网格单元的优先级越高；数目相等，adg中网格单元的优先级相同。adg中仅保留优先级最高的网格单元。若adg中仅有一个网格单元，则将该网格单元设为gnext，转到第3.4步；若adg中仍有多个优先级最高的网格单元，转到第3.3.6步。
[0049] 3.3.6根据路径pi中的最后一个网格单元得到上一个被覆盖的网格单元pi(end)，连接g和pi(end)组成线段，并沿着线段从g向外(即与线段相反的方向)做延长线，延长线为以g为起点的射线。以g为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线。根据延长线与adg中的网格单元相交的顺序给adg中的网格单元排序。延长线与adg中的网格单元越早相交，则adg中的网格单元的优先级越高。由于adg中的网格单元都是g的直接相邻网格单元或者到g距离相等的网格单元，则扫描过程中不会出现同时存在两个或多个网格单元位于扫描线上的情况。取adg中优先级最高的网格单元作为gnext。
[0050] 3.4根据gnext找到影子路径的更新值 是不考虑包围网格单元的影子路径更新值， 是考虑包围网格单元的影子路径更新值，方法是：
[0051] 3.4.1初始化不考虑包围网格单元的影子路径更新值
[0052] 3.4.2若 中含有gnext，说明影子路径和gnext重叠，删除 的最后一个网格单元，转到第3.4.3步；否则，转到第3.4.4步。
[0053] 3.4.3若 中不含有gnext，说明已删除 中的冗余网格，转到第3.4.4步；否则，转到第3.4.2步，继续执行删除操作。
[0054] 3.4.4若 的最后一个网格单元 与gnext直接相邻，说明无人机位于gnext时，可以从gnext去到 再沿着 返回起点网格单元，转到第3.4.8步；若
与gnext不是直接相邻，则需要计算无人机如果从gnext去到 时，是否经
过其它的未覆盖网格单元，转到第3.4.5步。
[0055] 3.4.5将G中与gnext直接相邻且为非覆盖状态的网格单元保存至目标网格单元的相邻网格单元集合 若 中没有网格单元，转到第3.4.9步；若 中有且仅有一个网格单元，则将 中的网格单元放到 中最后一个网格单元 后面，
转到第3.4.9步；若 中有多个满足条件的网格单元，则转到第3.4.6步。
[0056] 3.4.6计算 中的网格单元到 的最后一个网格单元 的距离。距离越短， 中的网格单元优先级越高；距离相等， 中的网格单元优先级相同。
删除 中低优先级的网格单元，仅保留 中优先级最高的网格单元。若 中仅
有一个网格单元，则将该网格单元放到 后面，转到第3.4.9步；否则， 中有
多个最高优先级的网格单元，转到第3.4.7步。
[0057] 3.4.7计算 中的网格单元到S的距离。距离越远， 中的网格单元优先级越高。删除 中低优先级的网格单元，仅保留 中优先级最高的网格单元。若
中仅有一个网格单元，将该网格单元放到 后面，转到第3.4.9步；否则，转
到第3.4.8步。
[0058] 3.4.8连接g和gnext组成线段，并沿着线段从gnext向外(即与线段相反的方向)做延长线，延长线为以gnext为起点的射线。以gnext为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线。根据延长线与 中的网格单元相交的顺序给 中的网格单元排序。延长线与 中的网格单元越早相交，则 中的网格单元的优先级越高。由于
中的网格单元都是gnext的直接相邻网格单元，扫描过程中不会出现同时存在两个或多个网格单元位于扫描线上的情况。取 中优先级最高的网格单元放到 后
面。
[0059] 3.4.9初始化考虑包围网格单元的影子路径更新值 以保存的原始值。
[0060] 3.4.10若 的最后一个网格单元 和gnext在Sur′的同一组内部障碍物的包围网格单元(令为Sur′k)中，则从Sur′k中的 开始将有序的包围网格单元依次放到 后面，直到遇到Sur′k中的gnext，停止将包围网格放到 后面。
注意，这里的gnext不放到 后面，以避免重复覆盖gnext。
[0061] 3.5根据无人机的剩余飞行能力Brest更新无人机的当前网格单元g的位置和影子路径pw。
[0062] 方法为：
[0063] 3.5.1若无人机的剩余飞行能力Brest能够支撑无人机从g飞到gnext并沿着 返回起点，即满足 则更新无人机的剩余飞行能力，即令Brest＝Brest‑len(g,gnext)；更新无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi最后一个网格单元后面；更新影子路径为 转到第3.5.4步；其中，len(g,gnext)表示从当前位置所在的网格单元g到目标网格单元gnext的最短距离； 表
示从目标网格单元gnext到 的最后一个网格单元 的最短距离；
表示从 的最后一个网格单元 经过 的网格单元到达 的第一个
网格单元 的最短距离。若无人机的剩余飞行能力Brest不能支撑无人机从g飞到gnext并沿着 返回起点，则转到第3.5.2步。
[0064] 3.5.2若无人机的剩余飞行能力能够支撑无人机从g飞到gnext并沿着 返回起点，即满足 则更新无人机的剩余飞行能力，即令Brest＝Brest‑len(g,gnext)；无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为已覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi的最后一个网格单元后面；更新影子路径为 转到第3 .5.4步；其中，
表示从当前位置所在的网格单元gnext到 的最后一个网格单元
的最短距离； 表示从 的最后一个网格单元 经过
的网格单元到达 的第一个网格单元 的最短距离。若无人机的剩余飞行
能力Brest不能支撑无人机从g飞到gnext并沿着 返回起点，则转到第3.5.3步。
[0065] 3.5.3此时无人机剩余飞行能量不足以支撑无人机继续前进执行覆盖任务，须沿着影子路径pw返回起点补充能量，方法是：将pw中的网格单元从后向前依次加入到第i次往返起点的路径pi的末端，并设置每个加入的网格单元为已覆盖状态；无人机返回起点后令g＝S，更新路径索引值i＝i+1，初始化第i条路径和影子路径为pi＝{g},pw＝{g}；令无人机在起点时剩余飞行能力等于最大可飞行网格单元数目Brest＝B，转到第3.5.4步。
[0066] 3.5.4若包围网格单元集合Sur′中存在某组障碍物的包围网格单元为覆盖状态，则从Sur′中删除该组包围网格单元，以避免重复覆盖，转到第3.2步。
[0067] 3.6目标区域已被完全覆盖，得到单架无人机往返起点的次数N＝i，令无人机群中无人机的数目等于N，无人机群的飞行路径集合P＝{p1,...,pi,...,pN}。
[0068] 第四步，使用负载均衡方法重规划N架无人机组成的无人机群执行覆盖任务的飞行路径集合P。通过优化无人机群的飞行路径集合P，最大化无人机群执行覆盖任务的效率。
[0069] 采用负载均衡方法重规划P的具体步骤为：
[0070] 4.1初始化无人机群中N架无人机的负载上限均为Bmax，令Bmax＝B，即Bmax不能超过单架无人机的自身飞行能力；初始化N架无人机的负载下限均为Bmin，令Bmin＝2Bfar，Bfar为目标区域中距离起点最远的网格单元到起点的距离，Bmin确保单架无人机从目标区域的任意位置都有能力返回起点。
[0071] 4.2若Bmin+1
[0072] 4.3计算新的单架无人机任务负载Bnew，Bnew＝Bmin+(Bmax‑Bmin)/N。
[0073] 4.4初始化包围网格保存变量Sur′＝Sur，以保存Sur的初始值。
[0074] 4.5将Bnew作为单架无人机的飞行能力，采用第三步所述的影子跟随的单架无人机区域覆盖路径规划方法，根据Bnew计算单架无人机往返起点的次数N′new和飞行路径集合P′new。令单架无人机最大负载等于Bnew时无人机群中无人机的数目Nnew＝N′new，无人机群中第inew架无人机的飞行路径 等于 无人机群的飞行路径集合为Pnew。其中，
[0075] 4.6若Nnew大于无人机群中无人机的架数N，说明飞行能力较小，需要增强无人机的飞行能力以保证无人机数目不变的情况下，每架无人机单次往返起点就能完全覆盖目标区域，因此增大负载下限，即令Bmin＝Bnew，转到第4.2步；否则，无人机数目不变的情况下完成目标区域的覆盖，目标区域重分配可行，减小负载上限，即令Bmax＝Bnew，并且更新每架无人机的飞行路径集合为P＝Pnew，转到第4.2步。
[0076] 4.7得到无人机群的飞行路径集合P，无人机群中第i架无人机按照pi执行覆盖任务，P＝{p1,...，pi,...,pN}，1≤i≤N。
[0077] 第五步，输出无人机群中无人机的数目N和飞行路径集合P。
[0078] 采用本发明可以达到以下技术效果：
[0079] 本发明基于影子跟随的单架无人机的区域覆盖路径规划方法计算无人机集群中无人机的数量，在考虑无人机有限机载能量的同时使用最少的无人机数目可以通过每架无人机单次往返起点完成目标区域的覆盖任务。本发明设置每架无人机在相同起点出发，将无人机在起点及周围的冗余覆盖问题考虑到单架无人机的任务负载中，通过均衡多架无人机的任务负载(见第四步)，提高了集群整体的覆盖效率。
附图说明
[0080] 图1为本发明总体流程图；
[0081] 图2为本发明一个实施例第一步目标区域的场景表示示意图
[0082] 图3为本发明一个实施例第二步包围网格单元遍历顺序示意图；
[0083] 图4为本发明一个实施例第二步目标区域中待覆盖网格到起点的最短距离示意图；
[0084] 图5为本发明第四步采用负载均衡方法重规划每架无人机的飞行路径的流程图；
[0085] 图6为本发明与背景技术其他多机算法的路径规划结果对比示意图；
具体实施方式
[0086] 为了使本技术领域的人员更好地理解本发明的技术方案，下面结合附图对本发明作进一步的详细说明。
[0087] 图1是本发明总体流程图；如图1所示，本发明包括以下步骤：
[0088] 第一步，对已知的目标区域进行预处理。目标区域包括待覆盖区域的边界、待覆盖区域内的障碍物的位置和起点位置，充电站设置在起点处。通过分解的方式将目标区域T划分为形状大小相同的正方形网格单元。网格单元的边长记作R，R根据机载传感器的能力及任务要求确定。 h为无人机的飞行高度，α为无人机上的机载摄像头的视野范围。目标区域T中包括两类网格单元：待覆盖的网格单元g和障碍物网格单元m，如图2所示。
图2中用阴影填充的网格单元表示障碍物网格单元，其它网格为待覆盖网格单元。待覆盖网格单元g组成的集合记作待覆盖网格单元集合G，障碍物网格单元m组成的集合记作障碍物网格单元集合M。其中，G内有一个网格单元作为起点，记作S。图2中g37为S。无人机从S出发执行覆盖任务，并在能量不足或者任务结束时返回S。M中的网格单元分为两类：边界障碍物集合Md和内部障碍物集合Me。Md中包括与目标区域边界具有连接关系的网格单元和与其它边界障碍物网格单元具有连接关系的网格单元，边界障碍物网格单元记作md。图2中的边界障碍物网格单元用 表示，其中r和c分别表示边界障碍物网格单元所在的行数和列数。图2中的 是与目标区域边界具有连接关系的网格单元；
与 斜向相邻，因此 也是边界障碍物网格单元； 与 直接相邻，因此 也是
边界障碍物网格单元。除了Md中的网格单元，M中的剩余网格单元为内部障碍物网格单元me组成了内部障碍物集合Me。图2中的内部障碍物网格单元用 表示，其中r和c分别表示内部障碍物网格单元所在的行数和列数。这里的连接关系包括直接相邻关系和斜向相邻关系。直接相邻是指两个网格单元的中心距离等于R；斜向相邻是指两个网格单元的中心距离等于 例如，图2中 和 是直接相邻关系， 和 是斜向相邻关系。
[0089] 第二步，计算内部障碍物集合Me的包围网格、待覆盖网格单元集合G中所有网格的连接关系和G中所有网格到起点的最短距离，方法是：
[0090] 2.1根据内部障碍物集合Me中的网格单元之间的连接关系对Me中的网格单元进行分组，分别计算每一组内部障碍物网格单元的包围网格并按照顺时针方向对包围网格排序，将排好序的包围网格均放到包围网格集合Sur中。包围网格是指与Me中的任一网格单元具有连接关系的待覆盖网格单元。
[0091] 具体步骤为：
[0092] 2.1.1将Me中具有连接关系的网格单元划分为一组，不同组之间的网格单元不存在任何连接关系。令Me被分为K组，K为正整数。如图3所示，目标区域中共有两组(K＝2)内部碍物 和 图3中用空心点填充的网格单元表示目标区域中两组内部障碍物的包围网格。
[0093] 2.1.2初始化索引值k＝1。
[0094] 2.1.3根据网格单元连接关系，找到第k组内部障碍物网格单元中每个网格单元的直接相邻和斜向相邻的网格单元，并将直接相邻和斜向相邻的网格单元保存至第k组包围网格集合Surk，并从集合Surk中删除碍物网格单元。此时集合Surk中的网格单元为第k组内部障碍物网格的包围网格。
[0095] 2.1.4根据Surk中网格单元的位置，自下而上、自左向右对Surk中的网格单元进行排序和编号。位于左下角的网格单元编号值最小。根据编号值按升序重新排列Surk中的网格单元。
[0096] 2.1.5初始化有序集合order＝{}，初始化网格单元记录栈stack＝{}，令当前网格单元位置g＝Surk[1]，即以Surk中编号值最小的网格单元作为遍历起点。
[0097] 2.1.6从待覆盖网格单元集合G中找到所有与g直接相邻的网格单元，将找到的与g直接相邻的网格单元且位于Surk中的网格单元保存至直接相邻网格单元集合adg。
[0098] 2.1.7若adg中有网格单元，转到第2.1.8步；否则，G中没有与g直接相邻且位于Surk中的网格单元，转到2.1.13步。
[0099] 2.1.8若adg中有且仅有一个网格单元，将g放至order的末端，从Surk中删除g，g等于adg中仅有的网格单元，转到第2.1.6步；若adg中有多个网格单元，转到第2.1.9步；
[0100] 2.1.9若g位于遍历起点，则将g放至order的末端，从Surk中删除g，g等于adg中编号值最小的网格单元，转到第2.1.6步；若g不位于遍历起点，则转到第2.1.10步；
[0101] 2.1.10从adg中选择与order中最后一个网格单元具有相同的直接相邻障碍物网格单元的网格单元，记作gnext。
[0102] 2.1.11若gnext的直接相邻网格单元中障碍物网格单元的数目≥2，将g压入stack栈顶，转到第2.1.12步；若gnext的直接相邻网格单元中障碍物网格单元的数目＜2，直接转到第2.1.12步。
[0103] 2.1.12将g放至order的末端，从Surk中删除g，令g＝gnext，转到第2.1.6步；
[0104] 2.1.13查看stack的信息。若stack中没有保存网格单元，则说明当前这一组内部障碍物的包围网格单元的遍历结束，转到第2.1.14步；若stack中有网格单元，则g等于stack栈顶的网格单元，删除stack栈顶的网格单元，转到第2.1.6步。
[0105] 2.1.14令Surk＝order，将Surk保存至包围网格集合Sur，更新索引值k＝k+1。若k>K,则说明所有包围网格单元均完成遍历和排序。如图3所示，箭头方向表示包围网格的遍历和排序方向，k＝1时遍历 的包围网格{g1，g2,g3,g4,g5,g7,g12,g11,g10,g15,g16,g17,g20,g25,g32,g31,g30,g24,g29,g28,g23,g19,g14,g9,g6}，k＝2时遍历 的包围网格{g38，g39,g40,g41,g45,g50,g49,g48,g47,g44}。此时Sur＝{Sur1,...,Surk,...,SurK},1≤k≤K，转到第2.2步；否则，转到第2.1.3步，继续遍历内部障碍物的包围网格单元。
[0106] 2.2统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的直接相邻网格单元，将直接相邻网格单元分别保存至g1,...,gj,...gnum(G)的直接相邻网格单元集合中，得到待覆盖网格单元g1,...,gj,...gnum(G)的直接相邻网格单元集合 其中，num(G)表示G中网格单元的数目(图4中num(G)＝
46)， 表示G中第j个网格单元gj的直接相邻网格单元集合，1≤j≤num(G)。例如，图2中网格单元g20的直接相邻网格单元集合
[0107] 2.3统计待覆盖网格单元集合G中每个网格单元即g1,...,gj,...gnum(G)的斜向相邻网格单元，将斜向相邻网格单元保存至g1,...,gj,...gnum(G)的斜向相邻网格单元集合中，得到待覆盖网格单元的斜向相邻网格单元集合其中， 表示G中第j个网格单元gj的斜向相邻网格单元集
合。例如，图2中网格单元g20的斜向相邻网格单元集合
[0108] 2.4根据无人机从当前位置所在网格单元向直接相邻的网格单元移动的规则，计算G中每个待覆盖网格单元到起点S的最短距离，即g1,...,gj,...gnum(G)到S需要经过的最少的网格单元数目，记作 得到待覆盖网格单元到起点的最短距离集合 其中， 表示G中第j个网格单元gj到S的最短距离。
如图4中待覆盖网格上的数字标记表示对应网格单元到起点的最短距离。例如，起点S为图2中的网格单元g37，即图4中数字标号为0的网格单元；网格g1到起点的最短距离disg1＝9。
[0109] 第三步，计算无人机的数量N和N架无人机的飞行路径集合P。无人机的数量N在数值上等于单架无人机执行覆盖任务时，无人机往返起点的次数；P由N架无人机的飞行路径组成，即P＝{p1,...,pi,...pN}。这里基于影子跟随的单架无人机区域覆盖路径规划方法，计算无人机往返起点的总次数。用pi表示无人机第i次从起点出发执行覆盖任务后回到起点的路径，1≤i≤N。pi由无人机飞行过程中经过的网格单元组成，即其中，gim表示pi中的第m个网格单元，num(pi)表示pi中网格单
元的总数。无人机N次往返起点后完全覆盖目标区域，即p1∪...∪pi∪...∪pN＝G。基于影子跟随的单架无人机区域覆盖路径规划方法，在计算目标网格单元的同时更新影子路径，使得无人机在能量不足时可以沿着影子路径返回起点，在不破坏未覆盖目标区域连续性的同时执行覆盖任务，提高单架无人机的覆盖效率，减少无人机往返起点的次数。用有限飞行距离D表示无人机的有限机载能量。通过网格单元边长R将D转换成无人机最多可飞行的网格单元数目B，满足
[0110] 基于影子跟随的单架无人机区域覆盖路径规划方法计算N和P的具体步骤为：
[0111] 3.1令无人机从起点出发，即初始化无人机的当前网格单元g的位置为S；初始化无人机的飞行路径集合P＝{}；初始化无人机往返起点的次数i＝1。令第i次往返起点的路径pi＝{S}，表示无人机从起点网格单元出发；令影子路径pw＝{S}，表示无人机沿影子路径返回起点网格单元。初始化G中的所有网格单元为未覆盖状态，设置g的状态state(g)为已覆盖状态，即令state(g)＝covered。初始化无人机的剩余飞行能力Brest＝B，即无人机剩余可飞行的网格单元数目在初始状态时等于无人机的最多可飞行网格单元数目。初始化包围网格保存变量Sur′＝Sur，以保存Sur的初始值。
[0112] 3.2若G中还存在未覆盖状态的网格单元，则转到第3.3步；否则，目标区域已被完全覆盖，转到第3.6步。
[0113] 3.3根据无人机的当前网格单元g的位置、目标区域覆盖状态和障碍物信息，计算无人机下一步前往的网格单元gnext的位置。
[0114] 具体步骤为：
[0115] 3.3.1找到G中所有与g直接相邻且为未覆盖状态的网格单元，保存至直接相邻网格单元集合adg。
[0116] 3.3.2若adg为空集，则找到G中所有到g距离最短且为未覆盖状态的网格单元，保存至adg，方法为：
[0117] 3.3.2.1计算G中网格单元到g的距离，方法是：g所在的网格单元到自身的距离等于0，标记g为0；与g直接相邻且不是障碍物的网格单元到g的距离等于1，标记与g直接相邻且不是障碍物的网格单元为1；遍历标记为1的网格单元的直接相邻网格单元，将不是障碍物且未标记的网格单元的标记值加一，即网格单元到g的距离等于2；按照广度优先的思想，标记G中的所有网格单元，得到G中所有网格单元到g的距离。
[0118] 3.3.2.2当adg为空集时，说明G中所有与g直接相邻的网格单元均为已覆盖状态，即G中到g距离等于1的网格单元均为已覆盖状态。因此，从G中到g距离等于2的网格单元开始，按照到g距离从小到大的顺序，查找G中未覆盖状态的网格单元。当找到G中第一个未覆盖网格单元时，记录找到的第一个未覆盖网格单元到g距离为dis。
[0119] 3.3.2.3找到G中所有到g距离等于dis且为未覆盖状态的网格单元，保存至adg。
[0120] 3.3.3若adg中仅有一个网格单元，则该网格单元作为无人机的目标网格单元gnext，转到第3.4步；若adg中有多个网格单元，转到第3.3.4步。
[0121] 3.3.4找到adg中网格单元到起点S的距离。距离越短，网格单元的优先级越高；距离相等，网格单元的优先级相同。将adg中低优先级的网格单元删除，仅保留优先级最高的网格单元。若adg中仅有一个网格单元，则将该网格单元作为无人机的目标网格单元gnext，转到第3.4步；若adg中有多个优先级最高的网格单元，转到第3.3.5步。
[0122] 3.3.5计算adg中每个网格单元的直接相邻网格单元中，位于G中且为已覆盖状态的网格单元和障碍物网格单元的数目之和。若网格单元周围的已覆盖网格单元和障碍物网格单元的数目越多，说明这个网格单元直接相邻的未覆盖网格单元数目越少。如果不优先覆盖这个网格单元，则可能出现这个网格单元周围没有直接相邻的未覆盖网格单元，导致覆盖这个网格单元时需要经过其它已覆盖的网格单元，造成重复覆盖，浪费无人机的有限能量。因此，adg中网格单元周围的已覆盖网格单元和障碍物网格单元的数目越多，adg中网格单元的优先级越高；数目相等，adg中网格单元的优先级相同。adg中仅保留优先级最高的网格单元。若adg中仅有一个网格单元，则将该网格单元设为gnext，转到第3.4步；若adg中仍有多个优先级最高的网格单元，转到第3.3.6步。
[0123] 3.3.6根据路径pi中的最后一个网格单元得到上一个被覆盖的网格单元pi(end)，连接g和pi(end)组成线段，并沿着线段从g向外(即与线段相反的方向)做延长线，延长线为以g为起点的射线。以g为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线。根据延长线与adg中的网格单元相交的顺序给adg中的网格单元排序。延长线与adg中的网格单元越早相交，则adg中的网格单元的优先级越高。由于adg中的网格单元都是g的直接相邻网格单元或者到g距离相等的网格单元，则扫描过程中不会出现同时存在两个或多个网格单元位于扫描线上的情况。取adg中优先级最高的网格单元作为gnext。
[0124] 3.4根据gnext找到影子路径的更新值 是不考虑包围网格单元的影子路径更新值， 是考虑包围网格单元的影子路径更新值，方法是：
[0125] 3.4.1初始化不考虑包围网格单元的影子路径更新值
[0126] 3.4.2若 中含有gnext，说明影子路径和gnext重叠，删除 的最后一个网格单元，转到第3.4.3步；否则，转到第3.4.4步。
[0127] 3.4.3若 中不含有gnext，则说明已删除 中的冗余网格，转到第3.4.4步；否则，转到第3.4.2步，继续执行删除操作。
[0128] 3.4.4若 的最后一个网格单元 与gnext直接相邻，说明无人机位于gnext时，可以从gnext去到 再沿着 返回起点网格单元，转到第3.4.8步；若
与gnext不是直接相邻，则需要计算无人机如果从gnext去到 时，是否经
过其它的未覆盖网格单元，转到第3.4.5步。
[0129] 3.4.5将G中与gnext直接相邻且为非覆盖状态的网格单元保存至目标网格单元的相邻网格单元集合 若 中没有网格单元，转到第3.4.9步；若 中有且仅有一个网格单元，则将 中的网格单元放到 中最后一个网格单元 后面，
转到第3.4.9步；若 中有多个满足条件的网格单元，则转到第3.4.6步。
[0130] 3.4.6计算 中的网格单元到 的最后一个网格单元 的距离。距离越短， 中的网格单元优先级越高；距离相等， 中的网格单元优先级相同。删除 中低优先级的网格单元，仅保留 中优先级最高的网格单元。若 中仅有
一个网格单元，则将该网格单元放到 后面，转到第3.4.9步；否则， 中有多
个最高优先级的网格单元，转到第3.4.7步。
[0131] 3.4.7计算 中的网格单元到S的距离。距离越远， 中的网格单元优先级越高。删除 中低优先级的网格单元，仅保留 中优先级最高的网格单元。若
中仅有一个网格单元，则将该网格单元放到 后面，转到第3.4.9步；否则，转到第
3.4.8步。
[0132] 3.4.8连接g和gnext组成线段，并沿着线段从gnext向外(即与线段相反的方向)做延长线，延长线为以gnext为起点的射线。以gnext为中心，延长线所在方向为起始方向，按照顺时针方向转动延长线。根据延长线与 中的网格单元相交的顺序给 中的网格单元排序。延长线与 中的网格单元越早相交，则 中的网格单元的优先级越高。由于
中的网格单元都是gnext的直接相邻网格单元，扫描过程中不会出现同时存在两个或多个网格单元位于扫描线上的情况。取 中优先级最高的网格单元放到 后
面。
[0133] 3.4.9初始化考虑包围网格单元的影子路径更新值 以保存的原始值。
[0134] 3.4.10若 的最后一个网格单元 和gnext在Sur′的同一组内部障碍物的包围网格单元(令为Sur′k)中，则从Sur′k中的 开始将有序的包围网格单元依次放到 后面，直到遇到Sur′k中的gnext，停止将包围网格放到 后面。
注意，这里的gnext不放到 后面，以避免重复覆盖gnext。
[0135] 3.5根据无人机的剩余飞行能力Brest更新无人机的当前位置g和影子路径pw。
[0136] 具体步骤为：
[0137] 3.5.1若无人机的剩余飞行能力Brest能够支撑无人机从g飞到gnext并沿着 返回起点，即满足 其中，len(g,gnext)表示从当前位置所在的网格单元g到目标网格单元gnext的最短距离；
表示从目标网格单元gnext到 的最后一个网格单元 的最短距离；
表示从 的最后一个网格单元 经过 的网格单元到达
的第一个网格单元 的最短距离。更新无人机的剩余飞行能力，即令Brest＝
Brest‑len(g,gnext)；更新无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi最后一个网格单元后面；更新影子路径为 转到第3.5.4步；若无人机的剩余飞行能力Brest不能支撑无人机
从g飞到gnext并沿着 返回起点，则转到第3.5.2步。
[0138] 3.5.2若无人机的剩余飞行能力能够支撑无人机从g飞到gnext并沿着 返回起点，，即满足 其中，表示从当前位置所在的网格单元gnext到 的最后一个网格单元
的最短距离； 表示从 的最后一个网格单元 经过
的网格单元到达 的第一个网格单元 的最短距离。更新无人机的剩余飞
行能力，即令Brest＝Brest‑len(g,gnext)；无人机从当前位置所在的网格单元移动到目标网格单元，即令g＝gnext；更新无人机的当前位置所在的网格单元为已覆盖状态，即令state(g)＝covered；将无人机当前位置所在的网格单元g加入到第i次往返起点的路径pi的最后一个网格单元后面；更新影子路径为 转到第3.5.4步；若无人机的剩余飞行能力
Brest不能支撑无人机从g飞到gnext并沿着 返回起点，则转到第3.5.3步。
[0139] 3.5.3此时无人机剩余飞行能量不足以支撑无人机继续前进执行覆盖任务，须沿着影子路径pw返回起点补充能量，方法是：将pw中的网格单元从后向前依次加入到第i次往返起点的路径pi的末端，并设置每个加入的网格单元为已覆盖状态；无人机返回起点后令g＝S，更新路径索引值i＝i+1，初始化第i条路径和影子路径为pi＝{g},pw＝{g}；令无人机在起点时剩余飞行能力等于最大可飞行网格单元数目Brest＝B，转到第3.5.4步。
[0140] 3.5.4若包围网格单元集合Sur′中存在某组障碍物的包围网格单元为覆盖状态，则从Sur′中删除该组包围网格单元，以避免重复覆盖，转到第3.2步。
[0141] 3.6目标区域已被完全覆盖，得到单架无人机往返起点的次数N＝i，单架无人机往返起点的次数在数值上等于无人机群中无人机的数目。
[0142] 第四步，使用负载均衡方法重规划N架无人机组成的无人机群执行覆盖任务的飞行路径集合P。通过优化无人机群的飞行路径集合P，最大化无人机群执行覆盖任务的效率。
[0143] 如图5所示，采用负载均衡方法重规划P的具体步骤为：
[0144] 4.1初始化无人机群中N架无人机的负载上限均为Bmax，令Bmax＝B，即Bmax不能超过单架无人机的自身飞行能力；初始化N架无人机的负载下限均为Bmin，令Bmin＝2Bfar，Bfar为目标区域中距离起点最远的网格单元到起点的距离。
[0145] 4.2若Bmin+1
[0146] 4.3计算新的单架无人机任务负载Bnew，Bnew＝Bmin+(Bmax‑Bmin)/N。
[0147] 4.4初始化包围网格保存变量Sur′＝Sur，以保存Sur的初始值。
[0148] 4.5将Bnew作为单架无人机的飞行能力，采用第三步所述的影子跟随的单架无人机区域覆盖路径规划方法，根据Bnew计算单架无人机往返起点的次数N′new和飞行路径集合P′new。令单架无人机最大负载等于Bnew时无人机群中无人机的数目Nnew＝N′new，无人机群中第inew架无人机的飞行路径 等于 无人机群的飞行路径集合为Pnew。其中，
[0149] 4.6若Nnew大于无人机群中无人机的架数N，增大负载下限，即令Bmin＝Bnew，转到第4.2步；否则，减小负载上限，即令Bmax＝Bnew，并且更新每架无人机的飞行路径集合为P＝Pnew，转到第4.2步。
[0150] 4.7得到无人机群的飞行路径集合P，无人机群中第i架无人机按照pi执行覆盖任务，P＝{p1,...,pi,...,pN}，1≤i≤N。
[0151] 第五步，输出无人机群中无人机的数目N和飞行路径集合P。
[0152] 随机设置70个目标区域，每个目标区域G的边长为20R，即目标区域中的每行每列均有20个网格单元。设置目标区域中的障碍物密度，即目标区域中的障碍物网格总数占目标区域中的网格总数的百分比，分别为10％、15％、20％、25％、30％、35％、40％。每种密度下随机生成十个目标区域，共生成70个目标区域对本发明进行测试。设置无人机的飞行能力为B＝80。实验的软件系统环境为乌班图16.04版本(即Ubuntu 16.04，Linux系统的一个版本)，搭载因特尔i7‑9750H处理器，处理器的频率为2.6GHz，RAM大小为16GB。
[0153] 基于已知目标区域和有限飞行能力的约束，对比第37届萨尔诺夫研讨会(2016)上Hazim Shakhatreh等人发表的文章《On the continuous coverage problem for a swarm of UAVs》(《无人机集群的连续覆盖问题》)给出的规划算法(简称CLE算法)和本发明提出的考虑影子路径和负载均衡的多机路径规划方法(简称LB)。
[0154] 图6为本发明(LB)与CLE算法的无人机数目和无人机群飞行路径总长度的对比值。图6(a)是在不同障碍物密度的环境下，本发明和CLE算法得到执行覆盖任务的无人机最少数目的对比图；图6(b)是在不同障碍物密度的环境下，本发明(LB)和CLE算法得到的无人机群覆盖目标区域时总路径长度的对比图。图6(a)和图6(b)中横轴表示目标区域中的障碍物密度。图6(a)和图6(b)中每种障碍物密度下，虚线表示CLE算法的结果，实线表示本发明的结果。
[0155] 图6(a)的纵坐标表示覆盖目标区域时无人机的数目。图6(a)中由虚线连接的每个障碍物密度下的误差棒表示CLE算法在十个密度相同且障碍物随机的场景中无人机数目的最小值和最大值的区间，误差棒与虚线的交点表示对应障碍物密度下的无人机数目的平均值；图6(a)中由实线连接的每个障碍物密度下的误差棒表示LB算法在十个密度相同且障碍物随机的场景中无人机数目的最小值和最大值的区间，误差棒与实线的交点表示对应障碍物密度下的无人机数目的平均值。相同目标区域下，无人机数目越少，说明使用更少的无人机成本即可完成相同目标区域的覆盖。从图6(a)可见，本发明相比CLE算法，在覆盖目标区域的过程中使用更少的无人机，每架无人机均单次往返起点，说明无人机群能够更高效地完成目标区域的覆盖任务，提高了无人机的能量利用率。
[0156] 图6(b)的纵坐标表示无人机覆盖目标区域的总路径长度。图6(b)中由虚线连接的每个障碍物密度下的误差棒表示CLE算法在十个密度相同且障碍物随机的场景中无人机总飞行路径长度的最小值和最大值的区间，误差棒与虚线的交点表示对应障碍物密度下的无人机飞行路径长度的平均值；图6(b)中由实线连接的每个障碍物密度下的误差棒表示LB算法在十个密度相同且障碍物随机的场景中无人机总飞行路径长度的最小值和最大值的区间，误差棒与实线的交点表示对应障碍物密度下的无人机飞行路径长度的平均值。相同目标区域下，无人机的总路径长度越短，说明无人机的覆盖效率越高。从图6(b)可见，本发明相比CLE算法，显著减少了无人机覆盖目标区域需要飞行的长度，提高了无人机的覆盖效率。
[0157] 以上对本发明所提供的一种影子跟随的多无人机区域覆盖路径规划方法进行了详细介绍。本文对本发明的原理及实施方式进行了阐述，以上说明用于帮助理解本发明的核心思想。应当指出，对于本技术领域的普通研究人员来说，在不脱离本发明原理的前提下，还可以对本发明进行若干改进和修饰，这些改进和修饰也落入本发明权利要求的保护范围内。
