目录

摘要

一.介绍

二.问题公式化

2.1情节

2.2方法

三.构建在线地图

3.1世界

3.2信息共享

3.2.1没有信息

3.2.2自己的信息

3.2.3完整的信息

3.3地图更新

四.产生可行的路径

4.1无人机kinematics

4.2探索算法

五.路径规划

5.1评估路径

传感器、通信和运动学约束的影响-toc" style="margin-left:0px;">六.传感器、通信和运动学约束的影响

6.1遥不可及的细胞

6.2传感器和通信范围的限制

七.结论

7.1示例场景

7.2增加传感器范围的影响

7.3.信息交换效应

7.4增加agent数量的效果

7.5.比较最佳路径规划和启发路径规划

7.6勘探技术花费的时间

八结论

---

摘要

在模拟未知区域的多架无人机导航探测系统中，存在形状、大小和初始位置未知的障碍物。无人机必须不断探索和监测该地区。uav传感器、通信范围和运动学约束有限。死胡同可能存在于环境中，可能导致无人机与障碍物相撞。由于无人机的传感器范围有限，它们无法检测小巷是否有障碍物。无人机在选择路径时必须相互配合，否则可能会发生碰撞。

无人机的物理约束和传感器约束，加上环境的不确定性，使多架无人机探测未知区域成为一个难题。我们开发了使用该系统的探索系统(a)一个探索算法来生成狭窄走廊中的安全路径，(b)考虑到多个智能体存在的动态领导者选择方案。我们还确定了最小通信范围，以确保在狭窄的走廊内没有碰撞。智能体数量、传感器距离和通信距离的变化通过蒙特卡罗模拟分析。

关键词 路径规划 多无人机 探索 合作

一.介绍

近年来，无人机(uav)越来越多的用于搜索和监控行动。在大多数任务中，无人机必须探索和收集未知区域的信息。无人机必须仔细探索该区域，因为该区域是未知的，包括未知形状和大小的障碍物。此外，由于无人机具有运动学约束，传感器和通信距离有限，安全探测路径规划算法的设计是一个需要解决的问题。

这些特殊团体的主要要求之一是尽快探索该区域。因此，我们部署了多架无人机，可以快速覆盖该区域，并通过冗余为任务提供鲁棒[1,2]。虽然使用多架无人机有其优点，但也存在设计多架无人机协调机制、低计算需求、可扩展性等挑战。无人机应相互合作，更好地分配搜索努力，避免无人机之间的碰撞。

因此，路径规划问题的复杂性不仅来自于无人机探索的安全路径，还来自于无人机之间的碰撞避免和搜索努力的分配。

探索未知区域一直是机器人研究人员感兴趣的话题。多机器人检测的理想特征之一是覆盖整个区域。Choset[3]提供了使用单个和多个机器人的区域覆盖算法的调查。在连续域或离散域中可以执行探索区域的任务。机器人在探索区域时，将区域划分为单元，并更新单元值。在连续区域中，机器人通过前后移动探测和覆盖区域，在线生成不同大小的单元。Rekleitis et al。[4]提出了多机器人有效覆盖算法，将区域分解，并将单元分配给机器人。Gabriely和Rimon[5]为单个机器人覆盖一个区域，提出了多项时间生成树算法。然而，使用多机器人生成树涉及到更多的问题[6-8]。Zheng等人[9]提出了一个基础Even[10]算法的多机器人森林技术，该算法查找图的树覆盖。Batalin和Sukhatme[11]提出了覆盖算法，机器人在覆盖整个区域的同时展开并相互远离。Wagner等人研究基于信息素的多机器人覆盖。[12]。Spires和Goldsmith[13]描述了基于希尔伯特空间填充曲线的多机器人覆盖算法。Koenig等人[14]提出了一种用途LRTA区域覆盖算法的方法。机器人在它访问的细胞中留下信息素标记，作为交流媒介。Balch和Arkin讨论了多机器人系统合作过程中通信的影响。Roy和Dudek[16]开发了几种交会算法，探索通信范围有限的异构机器人未知区域。Zolt等人提出了基于市场的多机器人探测技术。随着任务的进展，每个机器人都会通过拍卖有效地探索目标点的路线。Yamauchi开发了一种基于边界细胞的未知区域探索方案。边界细胞是已知细胞和未知细胞的边界。机器人自然会向前沿细胞移动，以探索未知区域。然而，作者可能不考虑多机器人之间的合作探索无效。Burgard等人[19]提出了一种多机器人协作技术，通过为机器人选择目标点，使机器人的探索分布在整个搜索区域。

任意一个感兴趣的区域可能包含各种形状、大小和位置的障碍物，在该区域形成狭窄的走廊。如图1(区域(a)至(e))所示的走廊可以在障碍物内、障碍物之间或障碍物与区域边界之间。假设机器人感知范围有限，使用[4-19]中提出的任意解的概念对图1所示的环境执行探索任务。这样机器人就可以在不发生碰撞的情况下探索环境。这一探索之所以成为可能，是因为当障碍物出现在机器人面前时，它可以停下来，向后移动，转向开放空间，从而避开狭窄走廊中的障碍物。文献[4-19]提出了探索有障碍物环境的关键问题，然而，无人机有运动学约束，因此当它们使用[4-19]提出的任何策略在狭窄的走廊中旅行时，它们可能会与障碍物发生碰撞。

如果机器人有运动学约束，即不能后退，不能停止，有转弯半径约束，这些策略也会导致机器人与障碍物发生碰撞。例如，如果我们对机器人施加运动学约束，那么机器人在探索区域(b)和(c)时可能会因为缺乏足够的转向空间而发生碰撞。另一方面，如果我们设计了一个悲观的规划者，不允许机器人探索区域(c)，那么像区域(e)和区域(d)这样的区域就不能被探索。因此，利用无人机探索区域，[4-19]中提出的概念不能直接应用，因此有必要开发新的路径规划算法。

多架无人机协同搜索未知区域已成为研究热点[20-22]。在这些研究中，对搜索空间进行了离散化，并对搜索空间进行了离散化，无人机相互协作确定路径，减少了地图的不确定性。这些文件没有考虑到该区域的障碍。Beard和Mclain[23]开发了在有限通信条件下具有避碰的合作搜索算法，但没有解决探索整个区域的问题。对于搜索和监视应用，有必要避开障碍并对该地区进行持续监测。

许多多无人机路径规划算法已经使用基于市场的方法[24]、动态规划[25]、进化计算[26]、概率映射[27]和MILP[28]被开发。Salva等人[29]提出了一种区域覆盖策略，无人机在它们自己之间分配要覆盖的区域，并在该区域周围游荡。他们不考虑障碍的存在。在无人机领域，探索受限于传感器和通信距离有限、无人机运动学和未知性质障碍的整个区域的路径规划算法的发展尚未得到充分解决。

在本文中，我们解决了在未知性质的障碍物存在下，受无人机传感器、通信和运动学约束的未知区域的探索问题。设计了环境在线地图构建机制、安全路径确定算法和多无人机协同路径规划算法，以避免无人机间的碰撞和在区域内分配搜索努力。

本文的组织结构如下。在下一节中，我们将介绍问题公式和解决问题的方法。第三部分介绍了在线地图的构建机制。使用该地图，无人机生成安全路径，如第4节所述。在此基础上，我们提出了一种协同路径规划技术，用于智能体确定其去冲突路径。在第6节中，我们研究了传感器和通信距离对无人机决策的影响。模拟结果在第7节中给出，我们在第8节中总结。

 图1两架无人机探索未知区域，障碍物大小、形状各异，在区域内形成走廊的场景

二.问题公式化

2.1情节

如图1所示，在一个有界区域内，两架无人机执行搜索任务。E ac h U a V al so al ld a an agent，有一个rs米的传感器范围，我们假设通信范围rc等于或大于传感器范围rs。世界中包含障碍物，它们的初始位置、形状和大小是未知的。无人机必须在避开这些障碍物的同时探索和持续搜索该区域。

正如fig1所示，障碍物形状可以不同。障碍物附近、障碍物之间以及障碍物与区域边界之间可能有狭窄的通道。图1中的区域(a)描述了足以使无人机掉头并因此覆盖障碍物中的区域的区域。然而，区域(b)和(c)的开放区域的宽度不足以让无人机转向，因此不能探索这些区域。由于传感器范围有限，无人机不知道狭窄通道的末端是否有障碍物，或是否有一个自由空间移动出通道。这种情况在(d)和(e)区域可见一斑。其中狭窄的走廊连接到开放的区域。悲观路径规划器可以设计，将不允许无人机进入这样的通道。在这种情况下，我们无法探索(d)和(e)区域，因此无法完全探索无人机可能访问的所有区域。

无人机应该完全探索该地区，构建一个在线世界地图。由于无人机的通信范围有限，只能在本地共享信息。代理还应该在确定路径时与邻居进行协调。所形成的路径应避开可能导致无人机与障碍物碰撞的走廊、无人机间碰撞、探索未知区域。

2.2方法

在本文中，我们解决了在探索过程中无人机固有的决策模糊性所提出的问题。我们提出了一个探索系统，该系统将在线构建地图，智能体使用该地图来确定不导致智能体与障碍物碰撞的安全路径。我们构建了区域的离散版本，并使用这种基于网格的单元结构来绘制环境和在区域中导航。勘探系统如图2所示。一旦生成了未知区域的网格，探索该区域的过程可以在以下四个阶段中进行描述。

阶段1:第一阶段，存在于细胞C j的智能体Ai检测其传感器范围内的自由细胞和障碍物细胞。如果智能体有邻居，那么它们在本地共享信息。

阶段2:智能体根据从传感器和邻居获得的信息更新单元值。在更新过程中，如果一个cell Ck被多个agent感知到，则将该cell的值取平均值并分配给该cell。我们使用一种平均机制作为共识模式，当相邻智能体之间关于一个细胞的信息不同时发生。在线地图的构建和更新机制将在第3节中解释。

 阶段3:智能体使用更新的映射生成路径。代理具有有限的传感器范围，因此使用q步前视策略生成长度为q的路径，其中q的值等于无人机的传感器范围rs。假设代理Ai生成的路径集是Pi。

Pi∈Pi的一些路径可以引导无人机朝向障碍物。可以很容易地从Pi中移除与障碍物相交的路径，但移除可能引导无人机走向潜在碰撞的路径是困难的。由于路径长度具有有限的视界，因此无人机无法预测该路径Pi是否是安全路径。为了消除这种模糊性，我们开发了一种探索算法(EA)，它将不允许无人机选择可能引导它们走向潜在碰撞的路径。EA是基于直觉的，如果一个智能体Ai出现在单元格Ci，如果存在一个路径Pi，这样的路径将使无人机回到当前位置，其航向等于当前航向或当前航向+ π， π是一个安全的路径。探索算法在第4节中介绍。

阶段4:一旦智能体确定了一组安全路径，它们需要从这组路径中选择一条路径用于导航。路径的选择应该在一种合作的方式，否则能体可能会相互碰撞。这些因子天性贪婪，因此会向未被探索的细胞移动。因此，路径选择算法包含两个部分:(1)避免无人机之间的碰撞;(2)向未知单元移动。该合作机制基于改进的leader-follower方法，能够处理区域的环境约束，并协助agent确定其路径。协同路径规划算法见第5节。一旦一个代理确定了它的路径，它就会移动到该路径的下一个单元格，这个过程一直持续到任务完成。在下一节中，我们将描述在线地图构建和更新过程。

 图2多架无人机探测未知区域的探测系统

三.在线地图构建

智能体在探索未知区域时动态地构建环境地图。首先，构建一个未知区域的网格，这个网格是智能体在其上更新环境的映射的基础。无人机在每个时间步更新地图，生成可行路径。

3.1世界

假设未知区域为宽度为W、长度为l的方形区域，将该区域分解为长度为l、宽度为W的单元格集合，其中W W和ll为整数。我们假设部署了N个agent，通过探索来建立该区域的知识。提供给所有无人机的初始地图是相同的，每个单元格C j有一个值Vi(C j) = 0，∀i, j其中j = 1，…， WL WL, an n d i = 1，…， n每个U a V 表示为Ai，其地图表示为Mi。

人工智能的路径是一个细胞序列。我们假设代理以细胞中心为路径点，细胞C j的中心表示为C j = {x j, y j}。我们还假设无人机从一个细胞到另一个细胞需要单位时间。因此，我们需要设计单元的l和w，使无人机能够在考虑其运动学约束的网格中飞行。如果取l和w小于无人机的最小转弯半径(Rmin)，则无人机会在单位时间之前到达航路点。如果我们将l和w增大到大于Rmin，那么代理将无法在单位时间内到达航路点。因此，我们用l和w等于Rmin，允许无人机在单位时间内到达航路点。

我们假设每个agent都配备了全向传感器，可以准确地检测环境中的障碍物。因此，他们可以在Mi地图上标注自由细胞和障碍细胞的区别。假设智能体Ai位于一个细胞C j，它可以感知周围所有深度为rs细胞的细胞Ck∈N (C j, rs)，(其中N(·)为邻域函数)。Ai在t时刻检测到的自由细胞用集合F(C j, t)表示，障碍细胞集合用集合O(C j, t)表示，L et U, F, O表示世界上所有未探索的细胞、自由细胞和障碍细胞。最初，该区域是未知的，因此所有单元格都是未探索的，值Vi(C j) = 0。当无人机探测到一个未探测的细胞时，它的值根据该细胞是自由细胞还是障碍物细胞而改变。

自由单元赋值为1，障碍物单元赋值为−1。无人机给传感器内的单元赋值的一般规则是:

 

一个障碍可以是单个细胞，也可以是一群聚集在一起的细胞。为了简单起见，我们假设障碍物占据完整的单元。传感器的范围是rs米，而且是圆形的，因此它可以部分感知到周围的一些细胞。

但我们假设障碍物占据了完整的细胞，因此我们可以准确地将部分检测到的细胞分为自由细胞还是障碍细胞。图3显示了一个带有障碍的典型探索空间的快照。

环境中包含不同形状和大小的障碍物，在该地区形成狭窄的走廊和陷阱。陷阱是一组以区域边界或障碍物结束的自由细胞序列。圈闭可以是任何形状，但在离散域中很难表示一般形状的圈闭，因此我们假设有两种类型的圈闭:(1)水平圈闭和(2)垂直圈闭。这些陷阱的几何形状如图4所示。如图4 (c)所示，水平陷阱是一个自由细胞序列，它可以以区域边界结束，也可以以障碍物细胞结束。(d)、(i)和(h)。陷阱的宽度可以是一个或两个格子，长度可以是L?细胞,L在哪里?水平圈闭的定义为

 

 图3含有自由细胞和障碍物细胞的未知区域

式中(xh j, yh j)表示陷阱的第一个单元格，(xh j+d, yh j)表示陷阱的最后一个单元格，d表示陷阱的深度。(xh j, yh j)到(xh j+d, yh j)表示水平陷阱的第一行，(xh j, yh j+1)到(xh j+d, yh j+1)表示Gh的第二行。单元格(xh j+d+1, yh j)和(xh j+d+1, yh j+1)要么是障碍物单元格，要么是搜索空间的边界单元格{(xh j, yh j+2)，…， (xh j+d, yh j+2)}表示区域边界的障碍物细胞，同样，细胞{(xh j, yh j−1)，…， (xh j+d, yh j−1)}表示障碍细胞或边界。

图4 (a)以边界结束的两个单元格垂直阱(b)以障碍物结束的一个单元格。(c)以边界结束的一个单元水平捕集器。(d)有障碍物结尾的单细胞水平捕鼠器(e)有边界角的单细胞垂直捕鼠器。

(f)以障碍物结束的两个单元垂直捕集器。(g)有边界的单细胞垂直阱。(h)两个以障碍物结尾的单元水平陷阱。(i)两端有边界的两个单元水平捕集器。

垂直陷阱是一组细胞序列，其中一个或两个细胞的长度和宽度均为W'细胞,其中W'< W，以障碍物单元或边界结束。

垂向圈闭的几何形状如图4(a)、(b)、(e)、(f)和(g)所示。垂向圈闭表示为

式中(xv j, yv j)和(xv j+1, yv j)为垂直陷阱Gv的起始单元，and (xv j, yv j+d)和(xv j+1, yv j+d)为Gv的最终单元。(xv j, yv j+d+1)和(xv j+1, yv j+d+1)不是障碍物就是边界外的单元格。单元格{(xv j−1,yv j)，…， (xv j−1,yv j+d)和{(xv j+2, yv j)，…， (xv j+2, yv j+d)}表示障碍细胞或区域边界。

注意，如果细胞(xh j+d+1, yh j)和(xh j+d+1, yh j+1)是自由细胞，那么陷阱是连接到开放空间的走廊。陷阱的深度d可以大于无人机的感知范围rs。在这种情况下，无人机将不知道该走廊是否为陷阱。因此，无人机必须生成能够避开陷阱的安全路径，同时允许智能体穿越连接搜索空间不同部分的狭窄走廊。为了生成一组安全的路径，我们使用下一节将描述的探索算法。

3.2信息共享

当智能体处于通信范围rc内时，它们可以共享两种类型的信息:感知到的环境地图和预期的路径。共享地图将导致更快的探索，同时共享路径使邻居选择不冲突的路线。地图共享可分为三个层次:(1)无信息(2)自信息(3)完整信息。每一层对覆盖时间都有不同的影响。

3.2.1没有信息

在这个方案中，智能体不与它的邻居共享映射信息。这种机制类似于单个无人机探索整个区域。因此，多辆车的可用性没有得到充分利用，导致性能低下。由于代理之间没有信息交换，通信开销很小。在路径规划和区域覆盖应用中，通常不采用无信息交换方案。然而，也有一些研究者开发了不需要通信的任务分配算法[30,31]。虽然noinformation-exchange方案提供了最低的性能，但为了进行比较，有时有必要知道在不共享信息的情况下可以实现多少性能。

3.2.2自己的信息

假设agent Ai在搜索空间的时间t遇到agent aj。当智能体使用自信息交换方案时，智能体Ai将共享该方案的信息。在与agent A j会面之前，agent不会共享从其他agent处获得的任何信息。L etˆCi(0, t)是Ai在时间t之前更新的单元集。agent Ai与agent A j共享ˆCi(0, t)， agent A j与Ai共享ˆC j(0, t)。它们的本地实例化映射会按照3.3节的描述进行更新。

什么时候Ai在时间t再次遇到同一个agent，则双方代理将分别通过共享ˆCi(t, t?)和ˆC j(t, t?)来更新各自的地图。随着智能体通过其邻居获得额外的信息，完成团队任务的能力得到提高。

除了细胞的信息外，这些代理还共享它们所走过的路线。路由信息有助于减少确定安全路径的计算时间(见第4.2节)。每个代理存储它所走过的路线，以及它在探索过程中遇到的代理的路线。路由存储在一个集合中。

式中Rij为第j架无人机的航路，航路Rij表示为:

其中Cij k是第i个agent对agent A j在步骤k的位置的知识，ψij k是步骤k单元Cij的航向角。当agent Ai和A j通信时，它们的路线Rij∈Ri和R ji∈R j被更新。

每架无人机都有一个时间记录Ei(a j, ti)，其中Ei是Ai与a j相遇的时间步长记录。该记录需要记录Ai何时与相邻的无人机相遇，以便信息共享，当这些无人机在t时间再次相遇时，它们只在ti - t时间之间共享获得的信息。

3.2.3完整的信息

在这个方案中，每个代理与它的邻居共享它的整个地图和路由信息。由于代理共享完整的映射信息，代理映射的保真度提高，从而比其他两种方案更快地实现覆盖。

3.3地图更新

在每个时间步，无人机通过两个步骤更新地图:(1)通过感知环境更新地图(2)更新代理当前单元位置的值。在步骤(1)中，agent利用(1)对检测到的细胞是障碍细胞还是游离细胞进行分类。在步骤(2)中，代理更新单元格的值，以确保代理不会绕着几个单元格转。当agent移动到细胞Ck时，细胞的值会降低。在合作搜索领域，这种单元值的减少被称为不确定性降低[20-22]。该数值的减少不会让agent进入局部最小值，这类似于蚂蚁信息素基于区域覆盖的情况，即蚂蚁在它访问的细胞中存放信息素。另一只蚂蚁可以检测到储存在细胞中的信息素的数量，并选择路径到储存信息素较少的细胞，从而确保均匀覆盖[14,32]。

在本文中，我们使用相同的策略，即降低下一段所述的单元格值。

在每个时间步骤中，智能体Ai会根据自己所走的路线，并利用从邻居那里收到的信息更新地图。世界地图的更新方式如下:

1. 如果t时刻单元格Ck有Ai，则单元格值降低为Vi(Ck)←0.5Vi(Ck)。UAV只遍历那些单元值大于零的单元。

2. 当Ai收到agent A j关于cell Ck的信息时，则Ck的值更新为Vi(Ck)←Vi(Ck)+V j(Ck) 2。

平均方法使代理具有更好的地图保真度，从而更快地探索该区域。智能体使用更新后的地图生成可供探索的安全可行路径集。

四.生成可行的路径

无人机的传感器范围有限，因此我们使用有限视距前瞻策略来生成路径。所生成的路径应考虑到无人机的运动学约束和避免陷阱。

4.1无人机kinematics

我们假设无人机在一个恒定的和共享的高度飞行。无人机有转弯半径限制，因此单元之间的运动取决于当前的航向角。将无人机的运动学建模为

 其中，vi为地面速度，ψi为航向角，φi为控制翻滚角，g为引力常数。横摇角度命令约束为

由于运动学的限制，无人机不能直线移动到它前面的单元。在本文中，我们将约束无人机在单元之间的运动，使无人机在每个单元的中心，具有等于0，π 2， π，−π 2的航向角。设前置步长q = 1，此时无人机可以移动到前置单元，如图5(1)所示。如果有一个代理存在于Ci空间，且该空间的ψi = π 2，则该代理可以分别到达C1 i空间，C1 i空间的ψi = 0, C2 i空间的ψi = π 2和C3 i空间的ψi = π。

如果无人机以正确的方向接近障碍物，障碍物周围的一些区域会被覆盖，因此产生可行路径是困难的。然而，如果从其他方向靠近，一些细胞可能会导致碰撞。例如，考虑图5(2)中的场景。如果无人机沿(a)方向移动，那么它可以覆盖障碍物内部的区域。另一方面，如果无人机行进方向为(b)，则agent会与障碍物发生碰撞。注意，这个区域在障碍物内部，宽度为3个cell，深度为3个cell，因此这个区域不是垂直陷阱Gv，而是由于路径的选择而发生碰撞。

因此，路径规划的主要问题之一是确保无人机生成安全的路径，不允许无人机与障碍物发生潜在碰撞。为了解决这个问题，我们开发了一个探索算法。

图5(1)无人机航向角α=π/ 2出席细胞细胞C1i Ci可以移动,C2i, C3iwith航向角α= 0,α=π/ 2,α=π。

(2) (a)障碍物内的所有区域都能被覆盖。(b)区域无法涵盖的方向

4.2探索算法

代理Ai出现在细胞Ci处，生成一组路径Pi。元组中的每个元组由一个单元格和单元格中的方向角组成。第j条路径pji∈Pi给定为pji = [(C j,0 i， ψ j,0 i)， (C j,1 i， ψ j,1 i)，…， (C j,q i， ψ j,q i)]， w he r e (C j,k i， ψ j,k i)是agent在时间步长k时的位置及其方向角。

集合可以分解为两个集合，= P f i ?Po i，其中P f i是无碰撞路径的集合Po i是与障碍物相交的路径的集合，而P f i ?Po i =∅。并不是所有的路径都可以用于探索，因为其中一些可能会导致无人机进入陷阱。为了生成安全路径，我们使用了一种探索算法。

在探索算法中，我们假设Ai出现在单元格C j, 0i上，标题为ψ j, 0i，那么它到达(C j, 0i， ψ j, 0i)的路径一定是无碰撞路径。假设存在一条路径P，从C j, qi∈P j i，航向角ψ j, qi到C j, 0i，其中P j i∈P f i。令路径pji = [(C j,q i， ψ j,q i)， (C j,q+1 i， ψ j,q+1 i)，…， (C j,q+m i， ψ j,q+m i)]，其中C j,q+m i = C j, 0i, an d ψ j,q+m i是细胞C j,q+m i对应的到达角。

关于路径pji是否是安全路径的分类，取决于到达角ψ j,q+ mii在单元C j, 0i处的到达角。当航向角ψ j,q+m i at C j, 0i等于ψ j, 0i或ψ j, 0i + π时，路径pji是安全路径，否则认为它不是安全路径。如果ψ j,q+m i等于ψ j,0 i，则该路径会遍历到代理的当前位置。因此，代理可以选择不同方向的路径，这意味着该路径是安全的。如果ψ j,q+m i等于ψ j,0 i + π，那么这个方向与当前的方向角ψ j,0 i是相反的，这意味着代理可以通过原来到达C j 0 i的路径返回，并且该路径是安全的。如果ψ j,q+m i等于ψ j,0 i±π/2，那么C j,0 i前面的单元就有可能走向障碍物或陷阱而导致碰撞。因此，我们不将这些路径划分为安全路径。这个概念类似于[33]中描述的小型无人机的避障技术。

让最后所有单元格的集合 c j,q i对每个路径P j i∈P f i表示为Cq i:

集合Cq i中元素的数量取决于向前查找步骤的长度。现在我们将使用递归搜索方法确定安全路径。

设N (C j,q i， ψ j,q i)为邻域函数，考虑到无人机的运动学约束，该邻域函数决定了相邻单元以及无人机可能到达这些单元的角度。在递归搜索方法中，我们取一个单元C j,q i∈Cq i，其角度为ψ j,q i，并确定下一个单元和角度。对由邻域函数确定的新单元格进行检验，看是否有任何单元格等于C j, 0i和ψ j, 0i等于ψ j,q i或ψ j,q i + π。如果满足此条件，则认为路径pji是安全路径。否则，递归地探索端点，直到到达cj, 0i。安全路径集合用Ps i⊆P f i表示。算法1形式化了确定Ps i的过程。

函数nextCellsAngles表示邻域函数N (C j,q i， ψ j,q i)，并根据当前的单元格和角度，返回无人机可以移动到的下一个单元格和角度。采用递归搜索的搜索算法生成所有安全路径。

算法1将生成一条安全的路径，不允许无人机引导到陷阱。

假设agent Ai在时间t时位于cell Ci，使用算法1确定安全路径。考虑一个路径P j i∈P fi，算法1对这条路径P j∈Ps i进行分类，当且仅当，Ck等于C j,0 i ψk等于ψ j,0 i或ψ j,0 i + π， o er wi s e P j /∈Ps i。I f P j I /∈Ps I表示nextCellsAngles函数返回的cells=∅。

nextCellsAngles函数可以返回一个空向量，当且仅当，每个单元格C?k∈O还是C?k∈U, w h e r e C?k∈细胞。每个单元格C?k∈cells，引导agent走向障碍物或未知的细胞，因此得到路径P j i /∈Ps i。因此，算法1正确地分类了路径P j i∈Ps i或P j i /∈Ps i，因此不会将agent引入陷阱。

智能体Ai利用算法1为所有路径P j i∈P f i生成安全路径。由于定理1保证算法1生成安全路径，且agent Ai对其每个路径P j i∈P f i使用算法1，因此路径集P j i∈Ps iare安全路径集。

定理2算法1生成Ps i⊆P f i，每条路径P j i∈Ps i都是安全路径。

证明假设路径pji被错误地分类为安全路径(P j i∈Ps i) byy算法1，路径pji将引导agent走向深度为d的水平陷阱Gh。这意味着C j,q i∈Gh和ψ j,q i = 0, w he C j,q i是路径pji的第qth cell。

当代理Ai对P j i使用算法1时，当遇到障碍物单元(xh j+d+1, yh j)或(xh j+d+1, yh j+1)或未探索的单元(xh j+d?， yh j， (xh j+d?， yh j+1) d?表示Gh中(xh j+2, yh j)到(xh j+d, yh j)或(xh j+2, yh j+1)到(xh j+d, yh j+1)之间的某个单元格。由于单元格(xh j+d+1, yh j)∈Gh和(xh j+d+1, yh j+1)∈Gh, the nextCellsAngles函数将返回一个空向量，算法1将对P j i /∈Ps i进行分类。因此，算法1生成的所有路径都是安全路径。

在每一个时间步，每个无人机使用算法1生成一组安全路径。

当障碍物较大时，递归需要的步数会很大，如果每个时间步都进行递归，那么计算时间会增加。因此，我们开发了一种基于其他智能体路径知识的启发式算法，以减少算法1的计算时间。

利用路径知识:每架无人机都有其飞行路线的信息，以及在探索过程中遇到的其他无人机的路线信息。如3.2节所述，agent所拥有的信息依赖于所采用的信息共享方案的类型。

不是搜索从C j,q i到C j, 0i的路径，而是搜索从C j,q i到任何细胞Cn i∈ˆCi的路径，w h e r eˆCi = ?N m=1 Rim ?C j 0 i是Ri中所有路由的单元格和角度的集合。启发式算法见算法2。

 算法2也生成安全的路径集合Ps i⊆P f i。

每个细胞Cn i∈ˆCi是某agent aj路线的一部分，即某agent aj经过Cn i。如果agent aj使用Cn i，意味着经过Cn i的路由被归类为安全路径，因为aj使用算法1生成了安全路径，定理1证明算法1保证生成安全路径。因此，当智能体Ai使用角度为ψk或ψk + π的cell Cn i作为终止准则时，路径pji可以到达cell Cn i，并且可以在ψk + π范围内到达aj，因此路径pji是一条安全的路径。agent使用算法2来确定每个路径P j i∈P f i sa safe P ath，因此集合Ps i⊆P f i表示使用算法2生成的不使agent陷入陷阱的安全路径集合。

使用路由信息使无人机能够快速确定一组安全路径。最初，当区域未知时，算法2可能不会显著减少计算时间。然而，随着探索的继续，路线不断积累，算法2可以更好地减少计算时间。

一旦生成了一组安全路径，代理就必须选择一个路径。由于共享高度存在多架无人机，各智能体在路径选择上必须相互配合，以避免无人机之间发生碰撞。

五.路径规划

选择合适的路径会影响探测的性能。制剂选择可以通过向未开发区域或高细胞值移动而获得高产量的路径。由于空间中存在多个智能体，由于无人机的运动学约束，所有智能体可能无法向未开发区域移动。因此，需要一种既能有效分配无人机探索未知区域，又能避免无人机间冲突的冲突解决方案。如果有多架无人机同时碰撞在同一单元，或在转换期间从一个单元切换到另一个单元，则可能发生无人机之间的切换。对于全球通信的情况，冲突解决方案的开发相对容易，但对于通信有限的代理，冲突解决方案的开发比较困难。

当智能体受到有限的通信时，有不同的方法可以解决冲突。这些方案是基于(1)基于领导者的追随者和(2)基于谈判的方案。在leader-follower方案中，令牌数最高的agent被选为leader，其他agent被选为follower。领导者做出第一个决定，追随者考虑领导者的决定，并为自己产生去冲突的路径。在[23]中，主导UAV评估其路径时不考虑团队成员的行动。

追随者通过考虑领导的所有决定来评估他们的道路。

但是在本文中，leader-follower方法不能直接使用。例如，考虑图6a，其中A2和A3有两个可行的下一个单元，而A1只有一个可能的下一个单元。每个座席都有一个唯一的令牌编号Ti，令牌编号形式为T1 > T2 > T3。H en ce A1是leader并宣布它的路径，然后A2根据这个信息生成它的路径并宣布它，如图6b所示。由于A1和A2选择了它们的下一个细胞而不考虑A3，它们无意中从A3移除了所有可能的去冲突路径。另一方面，如果令牌排序为T1 > T3 > T2，则会如图6c所示选择路径，从而产生去冲突的轨迹。

基于谈判的方案可以用于解决问题，但这些方案通常需要更多的时间来达成协议。因此，我们不探讨使用这些方案的可能性。为解决路径规划中的冲突问题，提出了一种基于优先级的动态领袖选举算法。

在我们的动态leader选择算法中，leader是根据自由c_j, 1i个单元的数量动态选出的。座席的令牌号增加，根据自由C j的数量，1i细胞可用来生成可行路径。代理Ai的新代币号Ti由

 图6 (a) A1、A2、A3无人机可能的移动方向(b) A3没有任何出路时发生冲突。(c)由于基于优先级的令牌号生成而实现的冲突解决

其中，3表示任意agent可以拥有的下一个cell (C j,1 i)的最大数量，F表示可以生成可行路径的下一个cell的数量，而B是一个大于N(无人机总数)的正常数整数。在该令牌号生成方法中，下一个可行单元数量最少的无人机优先级高于下一个可行单元数量较多的无人机。一旦leader宣布了它的决定，拥有相同数量可行的下一个细胞的follower将重新生成它们的token数字。由于leader的决定，一个follower可能没有相同数量的去冲突的next cell。

在图6a中，A1有一个可行的下一个cell，而agent A2和A3有两个可行的下一个cell，因此A1是leader，宣布自己的路径。在A1宣布其路径后，A2和A3重新生成令牌编号，A3成为下一个leader。A3选择自己的路径后，A2也选择自己的路径。这种冲突解决方法避免了无人机之间的碰撞。无人机的路径如图6c所示。

5.1评估路径

设Ps i为执行算法1后确定的安全路径集合。该负责人评估其路径时没有考虑其他无人机的行动

 并使用贪心策略选择路径Ps i

跟随者无人机必须考虑它转弯前所有无人机宣布的路径。假设agent Ai有Di的leader，让Di代表Ai的leader集合，让每个leader agent选择的路径Ad∈Di be¯Ps d。agent Ai对其路径的评估为

 其中¯Vi(C j,k i)是由

其中K >q是大于超前步长q的一个正数。条件C j, K i ?= Cs, K d表示细胞C j, K i ?= Cs, K +1 d和条件C j, K +1 i ?= Cs, K d检验如果智能体的路径交叉于任何leader路径。由于交叉先导路径是一种碰撞，因此我们将−K赋值给该路径。一旦确定了J(P J i)，我们将集合J分割为J+和J -，当J = J+ ?J−，J+表示正代价路径，J−表示负代价路径。负成本路径表示与某个leader Di∈Di发生冲突的路径。代理人使用(14)选择一个治疗方案

如果Ai是leader，那么(10)和(11)将生成无碰撞路径。如果Ai是追随者，则(12)、(13)和(14)产生一条无碰撞路径。

证明艾探员既可以是领导者也可以是追随者。我们首先证明Ai是leader时生成无碰撞路径，然后证明Ai是follower时生成无碰撞路径。

设Ai为前导，Ps i ?=∅。路径pji的代价用(10)计算。由于Ps i中的所有路径都是无碰撞路径，而Ai是第一个进行决策的代理，因此这些路径的代价将为正。智能体Ai使用(11)来确定具有最大收益的路径。因此，所选路径Ps i∈Ps iis是一条安全且无碰撞的路径。

设Ai为follower, Ps i ?=∅，leader数|Di|。各代理使用(12)and(13)通过考虑相同的cell和与其他代理的交叉碰撞来确定路径的代价。如果J+ ?=∅，th ent h er e xi st s至少有一条路径P J i∈Ps i，且不与其前导子碰撞。由于(14)只从J+的无碰撞集合中选取一条路径，因此所选路径P si为无碰撞路径。

但是，如果J+ =∅表示对于每个路径P J i∈Ps i，代理与至少一个前导发生碰撞。因此，代理将没有移动路径。

因此，(12)(13)a n d(14)如果存在一条无碰撞路径，则会产生一条无碰撞路径。

注意，世界是离散的，使用网格的代理具有有限的机动能力(只有三个方向)。如果一个区域内代理的数量比自由路径的数量大，那么一些代理可能没有冲突自由路径。在这种情况下，可能会发生无人机之间的碰撞。这个问题是由于有限的传感器范围和通信范围。路径规划算法只能在安全路径集中选择一条与其他无人机不冲突的路径。一旦代理选择了一个路径，它就将该路径广播给其他代理。尚未做出决定的代理将使用这些信息来评估路径。这个过程一直进行到任务完成。可以覆盖的区域取决于传感器的范围，我们将在下一节中研究。

六.传感器、通信和运动学约束的影响

正如4.1节所讨论的，无人机有运动学约束，可能会阻止它们覆盖所有单元。无人机也有有限的传感器和通信范围，限制了告知其他智能体路径的能力，在狭窄的走廊上旅行。由于这种限制，碰撞可能会发生。在本节中，我们将描述碰撞可能发生的情况和消除无人机之间碰撞的任何可能性所需的必要条件。在狭窄的走廊上旅行。由于这种限制，碰撞可能会发生。在本节中，我们将描述碰撞可能发生的情况和消除无人机之间碰撞的任何可能性所需的必要条件。

 图7无人机无法覆盖的小区

6.1遥不可及的细胞

图7显示了无法到达的单元格。角落里的牢房和陷阱是无法到达的。角单元格定义为:如果一个中心(x j, y j)的单元格C j在正交角上有一对障碍物或障碍物与边界的组合，则该单元格不能被覆盖。例如，考虑单元C j的位置，如果一对障碍物位于π 2且与(x j, y j)成0角，则该单元格不被覆盖。虽然这个单元是一个自由单元，但由于无人机的运动学约束，这种类型的单元不能被覆盖。因此，可达单元格的集合被表示为R = F \ E，其中E表示环境中角落单元格的集合。如果R中的所有单元都被访问，我们可以说无人机已经探索了该区域。

6.2传感器和通信范围的限制

代理的传感器范围有限，因此一些狭窄的通道不能完全覆盖。如果狭窄通道d的深度大于代理传感器范围rs的两倍，那么这些通道将永远不会被覆盖。例如，考虑图8a所示的场景，有一个由6个细胞组成的走廊，一个rs = 3的agent在勘探过程中探测到狭窄走廊的一部分。

一段时间后，代理检测走廊的另一半，如图8b所示。

因此，agent已经感知到整个通道，并可以通过探索来覆盖它。

另一方面，如果传感器的量程减小到2倍，则传感器的量程为2倍。很可能在狭窄通道中的一些细胞没有被探测到。算法1在生成安全路径时，遇到走廊中未探索的单元，不生成通过走廊的路径。所以这条走廊永远不会被封锁。

定理5如果传感器的范围rs≥d2，那么深度d的走廊将被覆盖。

图8 (a - c)示例表明，如果走廊的深度大于agent传感器范围的两倍，则该走廊不能被覆盖

考虑(2)w i th ce l l (xh j+d+1, yh j)∈F定义的走廊Gh，即陷阱将agent引向开放空间。假设Gh的深度为d, d > 2rs。

当智能体Ai出席细胞(xh j−1,y j h)与标题π2或3π2,t h e n i t c n检测细胞(xh j, yh j) (xh j + rc, yh j), n d w h e n Ai是出席细胞(xh j + d + 1, yh j)与标题π2或3π2,那么它可以检测细胞(xh j + d, yh j) (xh j + d−rc, yh j) Gh。其中存在(xh j+rc+1, yh j)， (xh j+rc+2, yh j)，…， (xh j+d−rc−1,yh j)∈U;

算法1遇到这些未检测到的细胞，不生成经过Gh的路径。因此，要覆盖Gh，传感器量程rs≥d2。

智能体之间的通信范围也有限，这意味着不同的智能体可以从相反的方向进入狭窄的走廊，而不知道它们正在发生碰撞。根据定理5，任何深度小于或等于2rs的通道都可以被覆盖，为了避免在这些通道中发生碰撞，代理应该在进入这些通道之前就它们的运动进行交流。

因此，各agent之间应该有最小的通信范围，以保证在走廊内不发生冲突。最小通信距离还取决于agent进入通道前的到达角度。例如，考虑如图9a所示，agent A1和A2为零度航向，这两个agent可以分别以90和270的航向进入通道。为了避免代理进入通道，我们需要2rs + 1的通信范围。现在，考虑最坏的情况，代理已经在碰撞过程中，如图9b所示。在此场景中，代理没有任何其他路径，因此会发生碰撞。为了避免这种情况，代理应该提前一步交流它们的路径。因此，为了避免走廊内的碰撞，需要各agent之间的通信范围为2rs + 2。

图9a, b示例表明，如果走廊深度大于agent传感器范围的两倍，则该走廊不能被覆盖

定理6在狭窄的走廊中保证不发生碰撞所需的最小通信距离rc为2rs + 2，且rs≥d2。

我们考虑了最坏的情况:一个胞宽的陷阱Gh，两个代理分别位于Ch j−1 = (xh j−1,yh j)和Ch j+d+1 = (xh j+d+1, yh j)，方向角分别为0和π度。我们假设d≤2rs, Gh中的所有细胞都被检测到。由于药剂以相反的方向进入Gh，它们会发生碰撞。为了使代理之间进行通信，通信范围为2rs + 1，但为了确保不发生冲突，代理之间应该至少提前一步进行通信。因此，确保在狭窄走廊上不发生碰撞所需的最小通信距离是2rs + 2。

如第5节所述，agent使用leader - follower策略，leader首先做出决定，follower agent在做出决策时必须考虑之前leader的所有决策。假设存在深度为d = 2rs的陷阱Gh，智能体Ai和Ai+1分别位于单元格(xh j−2,yh j)和(xh j+d+2, yh j)，方向角分别为0和π。我们还假定rc≥2rs + 2。L et Ai是领导者，Ai+1是追随者，因此Ai决定它的路径，并让这条路径为Pi = {(xh j−1,yh j)， (xh j, yh j)，…， (xh j+rs−1,yh j)}。现在，追随者代理将leader路径考虑在内，并假设它决定在一条路径上Pi+1 = {(xh j+d+1, yh j)， (xh j+d, yh j)，…， (xh j+d−rs−1,yh j)}。这两条路径是不相交的，因为d等于2rs，并且这两条路径都将agent引向同一个走廊。

由于agent只规划rs步长，Gh的深度为2rs，这可能会导致碰撞，为了避免这种情况，我们需要修改路径评估算法。

为了重新评估路径，代理必须知道他们的路径何时会导致无人机进入走廊。假设Ai位于细胞C j，设经过细胞C1 j的路径数为|ps,1 i |， C ell C2 j为|Ps,2 i |， and C ell C3 j为|ps,3 i |。I f |Ps,k I | < 3，则所有从细胞Ck j发出的路径都进入通道。当检测到这种情况时，追随者代理可以将这些路径从q = rc扩展到q = rc + 2，以检查是否发生碰撞。如果有碰撞，那么这些路径就不被认为是算法3所描述的。

需要注意的是，由于leader follower策略，只有一个agent可以进入Gh，而follower agent会扩展自己的路径长度来检查Gh中是否有碰撞。

一旦智能体决定了它的路径，然后它将移动到路径中的下一个细胞。代理商在每一步都使用探索系统来探索区域。通过仿真分析了该方法的有效性。

七.结论

该智能体利用所提出的探索算法对包含未知大小和位置障碍物的区域进行探测。利用蒙特卡洛仿真对该算法进行了验证。首先，我们将使用一个示例场景演示算法的功能，其中代理避开陷阱并通过安全走廊。覆盖整个区域所需的时间取决于(a)代理人采用的信息交换机制的种类(b)任务中的代理人数量和(c)传感器的范围。在本节中，我们将研究这些参数对覆盖时间的影响。

7.1示例场景

我们使用带有障碍物的模拟20 × 20正方形网格演示了所提出技术的功能。我们使用5架无人机，传感器距离rs = 4，通信距离rc = 10。agent在探索过程中使用完整的信息交换方案。

图10a显示了agent的初始位置，走廊C1和C2为矩形，陷阱为椭圆。走廊C1的纵深为6英尺，深为2英尺，深为7英尺。最初，整个区域是未知的，因此细胞没有着色。一旦药物检测到游离细胞，这些细胞就会变成橙色。特工必须避开陷阱，探索走廊。图10b显示了两个步骤后的代理路由。从图中我们可以看到，当探索技术遇到陷阱中未被探索的细胞时，agent A1避开了椭圆表示的T1陷阱。agent A2检测到通道C1中的一些细胞。因为走廊不完全知道，代理不会通过它。所有试剂检测到的游离细胞均为橙色。

图10 (a)用陷阱和走廊探索的初始感兴趣区域。(b)两个步骤后代理的路线。

A1避开了T1陷阱，A5在通道C1中发现了少量的细胞

经过7个步骤的探查，C1中的细胞最多可达3个步骤，如图11a所示。在图中我们还可以看到A2避开了用椭圆表示的陷阱。42步后座席的路由如图11b所示。从图中我们可以看到，A5检测到了C1中的所有细胞，除了一个细胞。因此，它可以利用走廊进行探索。从图中我们可以看到，agent A1到A4在完全探索了搜索空间的左侧后，正在向搜索空间右侧的未探索区域移动。图12a显示了A5探索走廊的一部分。所有agent用117步探索了整个区域，所探索的区域如图12b所示。

从图10a a d 12b我们可以看到，C2通道没有被探索，因为它没有被agent完全探测到。因此，考虑到传感器范围的限制，给定一个区域的代理可以覆盖所有可行的细胞。

为了覆盖C2，我们可能要增加传感器的范围。接下来,通过蒙特卡罗模拟研究了传感器距离和信息交换对覆盖面积百分比的影响。

图11 (a) agent经过7个步骤后的路径。A2避开了陷阱T2，通道C1中的细胞可深度感知到3个步骤。(b) A5能探测到C1中剩余未被探测到的细胞，因此现在知道了整个通道，agent可以利用这个通道进行探测

7.2传感器范围增加的影响

随着传感器范围的增加，无人机可以探测到更大的环境区域。所以，代理可以规划更好的路径。自然地，随着传感器范围的增加，覆盖时间减少。我们假设通信距离可以大于或等于传感器距离，随着传感器距离的增加，通信距离也会增加。因此，信息共享更好，区域覆盖更快。在不同agent数量下，对传感器距离rs = 2,3和4进行了仿真。随机选取20 × 20个单元的20张图，对各agent的位置和方向进行模拟。

 图12 (a) Agent A5通过走廊。(b)该区域有117个步骤

图13显示了模拟得到的结果。对于两个agent的情况，我们可以看到对于传感器范围rs = 2和rs = 3的agent，并没有达到100%的区域覆盖率。而当传感器范围rs = 4时，agent能够覆盖整个区域。注意，对于较小的传感器范围，狭窄的走廊或障碍物内的区域永远不会被完全探测到，因此不能被覆盖。例如，考虑使用5个代理实现的覆盖率和传感器范围rs = 4 a s s h on in F i g。12. 但当传感器距离rs = 2和3时，如图14所示，无法覆盖C1通道。

在探索过程中，所有特工成功地避开了所有地图的陷阱。

然而，由于传感器范围的限制，安全走廊的百分比数量没有完全探索。当传感器范围rs=2时，只有22.45%的探索了可用的狭窄走廊。如图13所示，由于探索的窄走廊百分比较少，这导致较低的区域覆盖率。如图13所示，随着传感器范围增加到rs = 3和rs = 4，狭窄通道覆盖的百分比分别增加到42.86%和83.67%。

 图13给定数量的代理和不同传感器范围的平均覆盖面积百分比

 图14传感器范围q = 2和3的5个agent覆盖区域

7.3信息交换效应

信息交换在确定覆盖时间方面起着重要作用。

在第3.2节中，我们提出了三种类型的信息交换方案，agent可以使用这些方案来提高性能，减少覆盖一个区域的时间。从直观上看，无信息覆盖方案的覆盖率最差，完全信息交换方案的覆盖率最好，自信息交换方案介于无信息和完全信息方案之间。我们进行了蒙特卡洛模拟，以研究在固定数量的代理和传感器范围下，信息对覆盖时间的影响。

图15所示为20张带有障碍物的随机地图覆盖面积的平均百分比。在模拟中，我们假设传感器和通信距离为rs = 4。从图15a中可以看出，完全信息和自信息方案的性能要优于无信息交换方案。然而，在图15b, c和d中，自信息和完全信息交换方案的性能是相似的。当代理人见面时，他们共享信息，但如果会议之间的时间间隔很大，那么他们的地图之间的差异就会增加。如果两个代理经常见面，那么他们的地图的保真度就更高。因此，一个可能的原因，代理使用自我信息方案执行类似于完整的信息方案是由于代理之间频繁的会议。

 

图15 (a)两种智能体覆盖面积百分比。(b)三名智能体所覆盖地区百分比。

(c)有四名智能体的地区百分比。(d)五名智能体所占地区百分比

7.4增加agent数量的效果

对随机障碍物和无人机位置的20幅地图进行了蒙特卡洛模拟。覆盖一个地区所需的时间取决于探索该地区的代理的数量。因此，每组仿真都针对不同数量的无人机(2 ~ 5架)进行。增加无人机的数量会导致该地区被覆盖的时间变短。从图16的性能曲线可以看出，5个agent覆盖该区域所需的时间比2个agent要短。从图中我们可以看到，随着agent数量的增加，覆盖时间减少。

然而，随着代理数量的增加超过3个，覆盖时间所获得的效益对于这种地图大小来说是边际的。

在大搜索空间(50 × 50网格)上，分别设置10个和20个agent，传感器距离rs = 4，通信距离rc = 10。

图17显示了代理实现的性能。从图中我们可以看出，使用大量agent覆盖的百分比区域比使用少量agent覆盖的百分比区域要快。我们还可以看到，随着传感器范围的增加，性能也会提高。在模拟过程中，没有报告冲突。

7.5最优路径规划与启发式路径规划的比较

提出的路径规划技术(算法3)不能产生最优解。因此，我们做了一个实验来确定解与最优解的接近程度。在这个实验中，我们考虑20个不同的地图，随机放置障碍物和5个agent。

从图18可以看出，最优路径规划器的性能要优于启发式路径规划器。然而，在覆盖了70%的区域之前，这两种策略的性能是相似的，但在此之后，有一个显著的不同的性能。这是因为使用最优路径规划的智能体能够有效地覆盖区域。

即使最优策略覆盖区域很快，计算决策所需的计算时间也需要14.37 s。启发式路径规划算法计算一个决策耗时0.13 s。因此，需要在计算时间和所获得的性能之间进行权衡。

 图16不同agent数量覆盖面积百分比

 图17大搜索空间覆盖的百分比

7.6勘探技术所花费的时间

如第4.2节所述，勘探技术可能需要更长的时间来确定安全路径。为了减少搜索时间，我们提出了一种基于路径知识的启发式算法。通过5个智能体和20张地图的传感器范围rs = 4的实验，确定了使用和不使用启发式探测技术所需的时间。图19显示了该勘探技术所花费的平均时间。从图中我们可以看到，没有启发式的探索技术所花费的时间几乎是使用启发式的4倍。因此，存储代理的路由并使用它们来确定安全路径可以减少生成安全路径的计算时间。

 图18最优启发式路径规划器性能

图19 (a)使用启发式勘探技术确定安全路径集所需的平均时间。(b)没有启发式方法的勘探技术确定安全路径所需的平均时间

八 结论

本文提出了一种多架无人机对未知区域进行探测的方法。地形包含未知形状、大小和位置的障碍物。智能体通过感知环境和接收其他智能体的信息在线构建区域地图。根据地图，通过探索技术生成一组安全的路径，确保这些路径不会引导无人机进入陷阱。提出了一种基于路径知识的启发式算法，以减少安全路径的搜索时间。提出了一种协同路径规划技术，使无人机能够与相邻智能体协同从安全集合中选择路径，同时避免无人机之间的碰撞。通过仿真，我们已经表明无人机覆盖可行区域，并且随着agent数量的增加，覆盖该区域所需的时间减少。我们还表明，随着传感器范围的增加，覆盖该区域的时间减少。使用启发式的探索技术所花费的时间几乎是不使用启发式的4倍。