基于网格的多个无人机搜索和救援应用的覆盖路径规划
基于网格的多个无人机搜索和救援应用的覆盖路径规划
摘要
本论文研究了使用多个无人机进行自动搜救（SAR）的问题。该问题被表述为分布式和离线的多机器人路径规划（MCPP）问题。使用多个机器人通常可以缩短探测幸存者的时间，假设幸存者在整个自动搜索期间保持静止。幸存者的探测假定使用向下朝向的机载摄像头进行。搜索过程中，无人机假定以恒定高度飞行，将问题简化为二维平面上的搜索 。根据所需的地面采样距离（GSD），环境被归类为已知的离散化网格，以保证幸存者的探测。环境中的静态障碍物由占据的单元格表示。在搜索区域中，未占据的单元格被分成相等大小、连续的子区域，由各自的无人机进行搜索。这消除了无人机之间的碰撞问题。闭环覆盖路径是使用生成树覆盖技术(STC)为每个子区域生成的。覆盖路径会根据无人机的动态约束进行修改。开发了一项集中部署策略，使得所有无人机在同一位置起飞和降落。还开发了飞行计划和加油协议以考虑无人机的有限续航能力。使用多个无人机进行自动搜寻的方法在以地面、山地和海洋环境为代表的真实世界地图的模拟中进行了测试和评估。模拟结果表明，无人机能够在合理的时间内覆盖搜寻区域，并获得较为有利的幸存者检测时间。因此，该系统应该可行用于实际实施。
第一章
引言
1.1 背景
无人机（UAV）在各种应用中越来越受欢迎。最初，UAV只是由地面飞行员远程操作，但近年来它们变得越来越自动化。UAV自动化已被应用于多个领域，例如但不限于结构检查 [10]、智能农业 [11]、灾难管理 [12]、电力线检查 [13]、监视 [14]和野火跟踪 [15]。大多数这些应用使用多旋翼UAV，特别是四旋翼。然而，UAV这个术语也包括其他飞机类型，如固定翼（飞机）和旋翼（直升机）UAV。也存在混合UAV，其包含旋翼和固定翼组件。
UAV可以在执行空中搜索时支持搜索和救援（SAR）操作。它们飞越景观和三维结构的能力使它们比无人地面车辆（UGV）具有相当大的优势。它们相对较高的飞行高度也使它们非常适合于自动化搜索应用。
也许最值得注意的使用无人机执行自动化搜索和救援的例子是由无人机搜索与救援（DroneSAR）进行的使用DJI无人机的项目[1]。DroneSAR在每次搜救任务中使用一架无人机。其实现包括一个移动应用程序，允许用户手动指定搜索区域。图1.1显示了他们的移动应用程序的截图。一旦指定了搜索区域，无人机就会在该区域内来回移动以实现覆盖。如果成像系统在该区域内检测到可能的目标，搜索操作可以被停止。无人机可以切换到手动飞行模式以进行更近距离的检查，并且可以将目标的坐标，例如遇险人员的坐标，发送给搜救小组。根据DroneSAR的说法，平均来说，一个五人救援小组在陆地上搜寻一平方公里内的一名人员需要两个小时，而他们的无人机可以在不到20分钟内完成同样的任务。
基于DroneSAR例子，下一步逻辑进展应该是利用多个无人机合作搜索指定的搜索区域。这将缩短搜索给定搜索区域的时间，或者在同样时间内允许覆盖更大的搜索区域。因此，开发这样的系统将是为支持搜索和救援操作做出有价值的贡献。
1.2 研究目的
开发一种多个无人机使用分布式离线覆盖路径规划（CPP）方法的自动搜索和救援（SAR）方法。
1.3 研究目标
本研究旨在开发一种多个无人机的自动路径规划算法。这些无人机需要在搜索和救援操作中协作搜索环境中的幸存者。无人机路径需要被开发出来，以完全覆盖所涉及的环境，同时避免无人机之间以及与静态环境之间的碰撞。
需要考虑UAV的动态限制和操作限制。动态限制包括前进速度和相关的最小UAV转弯半径。操作限制包括UAV的持续时间限制，需要加油覆盖环境，并且需要从中央基地起降的限制或跑道的限制。
此外，无人机装载摄像头的限制也要考虑到底。根据这些研究目标，制定了以下研究目标：
回顾现有文献，包括涉及搜救操作的文献以及已经应用无人机进行支援搜救操作的解决方案。
构想和建模搜救问题，包括搜索区域，地形，无人机以及环境中的幸存者。需要考虑整个搜救行动的全过程和各组成部分。
开发自动化搜索和救援算法，规划多架无人机的覆盖路径。无人机在搜索指定区域时必须遵循其动态限制，这取决于无人机的前进速度。应考虑一般的运营限制，包括车辆的耐久性以及中央部署的约束。最后，需要考虑到无人机上载摄像头用于寻找幸存者的限制。
开发一个以中央降落跑道或操作基地为假设的无人机起飞和降落程序，以及飞行时间表。
- 构建一个模拟可能的搜索和救援场景的平台。这些模拟应该用于测试算法作为自动化多个无人机的搜索和救援手段。
- 评估算法在随机生成的模拟环境以及映射的现实环境中的表现。评估在真实的搜索和救援任务中使用该算法的可行性。
1.4 提出的解决方案和贡献
自动化的搜索和救援问题被解释为一个覆盖运动规划问题。这个问题使用一种离线、基于网格的分布式覆盖路径规划（CPP）方法来解决多个无人机的问题。划定的搜索区域被划分成一个网格，其中静态障碍物被表示为占用单元格。网格表示中的空闲单元格被划分为大小相等、连续的子区域，由各个无人机搜索。所使用的算法称为最佳多机器人覆盖路径规划的分区算法(DARP)。生成的子区域大致相等。这意味着覆盖每个子区域的时间也相似。覆盖各个子区域也可以独立完成。无需考虑碰撞避免，由于每架无人机可以在未遍历另一架无人机所在区域的情况下搜索其分配的区域，
因此在中央基地周边选择无人机的初始位置。各个子区域被确定，以便每个子区域内都开始搜索一架无人机。使用生成树遍历 (STC) 技术为每个子区域生成一个闭合覆盖路径。然后根据无人机的恒定前进速度引入最小的无人机转弯半径，以考虑无人机的动态约束。原始路径将被修改以纳入这个转弯半径。
由于物理无人机的耐久性限制了子区域的大小，因此可能会有更多的子区域而不是无人机。在这种情况下，多个区域会被分配给一架实际的无人机进行搜索，但是无人机会在各自的子区域搜索之间加油。这是通过使用中央地面站进行起飞、着陆和加油来实现的。初始的机器人位置（UAV），可能与一个实际的UAV相关联，它们被排列成一个围绕地面站的周边配置。
UAV机群从基地依次起飞，并飞到地面站周围的初始位置。一旦它们各自到达一个相应的子区域，它们就会跟随它们的封闭循环路径行动，最终再次到达初始位置，然后从那里降落回基地。如果将更多的子区域分配给这些UAV，它们将被加油或充电，并为不同的未搜索子区域集开始另一个过程。
图1.2展示了在假设环境中使用DARP算法的结果。中央地面站显示为障碍物，机器人的初始位置位于其周围。它们显示为黑点，中心为白色。
只有两个可用的UAV，并且将分配给它们的子区域分别表示为蓝色和橙色。每个UAV被分配多个区域，每个区域都有多个初始位置。它们可以通过每个颜色中不同的着色来区分。目标位置显示为“X”。请注意，这不是实际场景中无人机所知道的值。
无人机将在其每个地区执行一系列闭环覆盖路径，如图1.3所示，从最深色阴影的区域开始。该图显示了发现幸存者时环境的一瞬间。在这个例子中，幸存者被发现在最后搜索的橙色子区域。在地面站降落和起飞的路径没有显示在这里，但是可以推断出来。
总之，多机器人自动搜救问题被制定为一个离线CPP问题。这是使用基于网格、二维、分布式方法解决的，这种方法导致了一个搜索区域的近乎完全覆盖。
1.5 研究范围
本文介绍的多UAV自动化搜索方法旨在作为SAR操作的一部分使用。它可能是一个涉及各种专业团队的更大的搜救计划的一部分。
在任何具体的搜救场景中，搜救协调团队需要决定如何使用一组无人机（UAVs）最为有用。它们可以用于搜索更大的搜索区域中的一个子区域，也可以作为手动搜索的空中协助。本研究项目的重点是开发一种算法，以生成UAV自动搜索中所遵循的路径。
该项目中开发的自动搜索与救援方法已在基于真实地图的搜索区域模拟中进行了测试和评估，并考虑了代表真实UAV和机载摄像头负载的动态和操作限制。然而，该项目没有进一步实施在真实的飞行计算机上并使用实物UAV进行实际飞行测试。这可能是未来研究项目的主题。
机载成像系统和目标检测算法的开发被认为超出了本项目的范围。目标检测的抽象化假设是，当目标在 UAV 的范围内时被检测到。算法被假设青睐于假阳性而不是假负。
本项目考虑范围之外的是无人机飞行控制系统的开发。假定无人机配备有飞行控制系统，使其能够遵循给定的参考轨迹。
多机器人路径规划(MCPP)方法已经隐含地为搜索区域内的静态地形特征提供了障碍物避让和协同搜索无人机之间的碰撞避免。
动态障碍物的碰撞避免未被考虑在内。假定无人机配备有短期碰撞避免系统，类似于Meiring等人[16]提出的系统。该短期碰撞避免系统的开发被认为超出了本项目的范围。
制定了飞行计划，以使无人机可以按顺序起飞和降落，并在必要时等待保持模式。这可以防止在起飞和着陆区域内发生无人机碰撞。同时假定该区域内不会有静态障碍物。
1.6 限制条件
本文提出的解决方案不适用于洞穴、城市或战斗搜救等环境。在能见度不佳的区域（如密林或恶劣天气的区域）进行空中搜索也不合适。这些区域被假定由搜索协调组排除在空中搜索之外。
本文所采用的方法将搜索区域划分为基于二维网格的环境。这有利于区域划分和路径生成，但也引入了一些限制条件。要生成一个具有恒定网格单元大小的二维网格，必须假定进行恒定高度的搜索。对于地形高差变化较大的搜索区域，能够在不同高度进行搜索将是有利的。
基于网格的方法也使得对实际连续环境进行完全覆盖更具有挑战性。当需要追踪小型或不规则移动目标时，基于网格的方法可能会导致搜索策略不连续或不一致。静态障碍物的避碰超出了本项目的范围。障碍物必须被高估或低估，以标记网格单元格为空闲或占据状态，这意味着基于网格的环境只是实际连续环境的近似。虽然可以实现对网格环境的完全覆盖，但对实际连续环境的完全覆盖只能近似实现[17]。
提出的覆盖路径规划方法假定静态目标，或者至少是相对于无人机移动缓慢的目标。如果目标是静态的，则可以保证目标检测，但对于移动目标则无法保证。假设目标是静态或缓慢移动的是合理的，因为需要搜救的个人被鼓励留在一个地方，或者可能会步行。
这篇文章介绍了一种基于无人机的搜索和救援(SAR)覆盖路径规划方法。这种方法旨在提高SAR任务的效率和准确性，同时减少搜寻时间和减少对人力资源的需求。该方法的目标是通过使用无人机在覆盖区域内搜索任何失踪的人员或遭遇危险的人员。
该方法假设需要搜寻的区域是已知的，并且在搜索之前进行了地图测绘。这种离线覆盖路径规划方法只考虑静态的障碍物，不考虑在同一搜索区域操作的其它飞机等动态障碍物。该方法假定任何动态障碍物都将通过短期避碰系统在线处理。
无人机的动态限制，即前进速度和最小转弯半径，强制要求产生完全覆盖的最低飞行高度。另一方面，机载摄像机的分辨率对飞行高度施加了最大限制，超过这个高度目标探测就无法保证。因此，必须仔细选择无人机和摄像机组合，以产生可行的飞行高度范围。
为了确保在无人机转弯时完全覆盖一个网格，必须使用小于机载摄像头视野的网格单元大小。这样做的缺点是可能会出现一些重复覆盖。但是重叠部分的优点是可以增加探测移动缓慢的目标，例如在不同的栅格之间移动。此外，重叠部分还可以解决覆盖区域不准确的问题，使其趋近于完全覆盖。
为了让无人机到达其初始位置，需要一系列的操作。这些操作以围绕地面站的方式进行排列，地面站被视为一个障碍物。目前，这种方法仅适用于八架无人机，但如果需要，可以扩展为更多的无人机。这是一种有限制的配置，可能存在其他更适合某种场景的配置。
本文提出的解决方案假设所有无人机都是从一个中央指挥基地部署出发的。然而，也可以采用其他的部署策略，例如从多个地面站部署无人机，并且无人机可能不需要降落在起飞的同一个地面站。所提出的解决方案必须根据特定的部署策略进行适应。这可能成为未来研究的主题。
1.7 论文大纲
除了引言，下面简要介绍了本论文的结构：
第2章-文献综述。本章建立了一些有关搜救行动的背景信息和背景，概述了机器人和无人机在过去用于搜救的情况，并对运动规划、单个机器人 CPP 和多个机器人 CPP 进行了文献综述。
第3章 - 概念设计和建模。本章介绍了搜索和救援场景及其主要要素，包括搜索区域、地形、无人机和目标。同时介绍了如何建模目标检测和碰撞的方法。
- 第4章 - 系统概述。本章概述了所提出解决方案的概述以及每个组件的简要描述和它们之间的关系。
- 第5章 - 环境表示。本章介绍了所提出解决方案的第一阶段。具体描述了选择一种适合某个环境的无人机和相机，以及选择合适的飞行速度和高度的过程。章节还介绍了将特定环境离散化为网格的过程。
- 第6章 - 区域划分算法。本章描述了使用DARP算法将指定的搜索区域划分为相等的子区域的方法。
第7章 - 子区域覆盖技术。本章描述了用于为分配的子区域中的单个无人机生成路径的方法，其中使用了跨度树覆盖（STC）算法，然后修改路径以考虑无人机的动态约束。
第8章 - 中央展开和调度。本章考虑从中央基地部署无人机的实际影响。我们制定了流程，生成了从中央地面站到其周边搜索路径起始位置的起降路径。还开发了飞行计划和加油协议，以允许无人机按序起飞和降落。
第9章 - 蒙特卡罗模拟。本章描述了进行蒙特卡罗模拟以测试和评估提出的自动搜索方法的过程。模拟结果被展示和讨论。
第10章 - 结论和未来工作。最后，论文总结了所做的工作及其研究目标的达成情况。还提供了未来研究和改进的建议。
第二章
文献综述
为了获取搜救问题的背景信息，了解机器人和无人机在实践和之前的研究中如何用于搜救，以及审查现有的运动规划和覆盖路径规划（CPP）技术，以便使用多个无人机执行自动搜索，进行了文献综述。CPP分为单个机器人覆盖路径规划和多机器人覆盖路径规划（MCPP）。MCPP又分为分布式离线MCPP，非分布式离线MCPP和在线MCPP三类。在本章末尾，总结了文献综述的关键结论，并用于本项目的研究决策。
第2.1节提供了搜救问题的背景信息，包括SAR组织，SAR的阶段以及不同类型的SAR。第2.2节概述了机器人和无人机在实践和之前的研究中如何用于搜救。2.3和2.4部分提供了有关一般运动规划和CPP的一些背景理论。2.5节回顾了单个机器人CPP技术的技术。2.6节回顾了MCPP的技术。2.7节总结了文献中的关键结论和所作出的研究决定。2.1搜索和救援本节讨论了有关SAR的原则和惯例，为一般SAR问题提供背景。2.1.1节讨论了全局意义下的SAR操作，涉及主要管理机构和文件。第2.1.2节讨论了SAR操作的不同阶段，第2.1.3节讨论了不同类型的SAR，具体涉及环境类型。
2.1.1 全球搜救
历史上，搜救行动通常是由地面团队进行计划搜索。随着技术的进步，技术开始被用于辅助行动。例如，载人船只和飞行器通常被用来在搜救行动中提供帮助。其他不太常见的技术，如热像仪，也可以被利用来加快搜救行动的速度。
本节中的信息来自三个来源：国际航空海上搜救手册（IAMSAR）的第一卷和第二卷以及国际民航组织（ICAO）关于最佳搜救实践的幻灯片集。由于搜救行动通常涉及海上和/或航空组成部分，因此国际海事组织（IMO）和国际民航组织（ICAO）已成为全球搜救的两个主要机构。
两个组织共同构想了一个全球搜救网络，将全球划分为搜救区域（SRRs），每个区域都有一个相关的救援协调中心（RCC）负责该区域内的任何搜救行动。总体目标是，无论一个人在哪里遇到困境，搜救服务都将是可用的。任何同意这一全球愿景的国家或州都应遵循特定的程序和协议进行搜救行动。他们还应遵守特定的组织结构，并始终应该有特定的设备可用。
有一本手册，概述了所有这些要求和协议，称为IAMSAR手册。这本手册获得了国际民航组织和国际海事组织的批准，并帮助协调具有航空和海事组成部分的行动。该手册由三卷组成，每卷针对搜救系统的不同组成部分。第一卷组织和管理卷面向搜救系统经理，涵盖全局搜救概念。本文重点讨论了RCCs的责任和邻近地区之间的合作。第二卷是任务协调卷，它提供了协调多个机构和区域进行SAR操作的指导方针。该卷面向救援协调中心（RCC）和救援子中心（RSC）人员。第三卷是针对SRUs的直接指南，包括他们应该遵循的协议，以及如果他们自己遇险时船只应该怎么做。
在全球SAR系统的角度来看，地球分为几个SRR。每个地区都被指派一个国家或区域机构，即RCC，在该地区负责SAR服务。预期此服务将迅速而有效地提供，无论情况或国籍如何。预计各个国家将以这种方式分享资源和设施。在进行搜救操作时，确保这些操作能够有条不紊、高效地进行是非常重要的。
海上和空中搜救区域可能略有差异，但通常非常相似。分配这些区域的好处是可以自动将遇险信号路由到相关的搜救协调中心，以便迅速进行紧急响应。
2.1.2 搜救的阶段
IAMSAR手册的第二卷详细介绍了搜救操作的阶段。接收遇险呼叫通常是进行搜救操作的第一步。保持联络并开放通信渠道是搜救操作中最重要的技术组成部分之一。遇险警报可以通过海岸无线电台、空中交通服务单位、陆地地球站、其他搜救协调中心和许多其他资源中继至相关的搜救协调中心。
在搜救响应期间，通信也是确保所有相关方保持了解的关键。便携式收音机、移动设备和卫星电话对有效的搜救操作非常重要。SAR飞机和船只也会在特定频率上进行通信，以确保没有干扰。
根据设备，还可能具备寻航能力。许多船只和飞机都有某种方式可以向其他人发出位置警告。例如，民用飞机通常配备应急定位发射器。在紧急情况下确定幸存者的位置至关重要。在这些情况下，极端条件或伤势并不罕见，必须尽快确定位置，以便必要时可以提供医疗服务，避免进一步的伤害，甚至死亡。IAMSAR手册将SAR响应分为五个阶段。第一个阶段被称为意识阶段。这是SAR机构通过通信渠道了解到有人遇险的阶段。一旦确定了可能的SAR情况，接下来的阶段涉及确定适当的紧急情况。这被称为初步行动阶段。紧急阶段可以有三种分类：不确定、警报或困境阶段。这种分类可以随着关于情况的新信息的出现而改变。评估情况的紧急程度可以确定需要哪种类型和程度的搜救响应。
适当的搜救响应规划和协调对于其成功至关重要。因此，在初始行动之后，下一阶段是规划阶段。在这个阶段需要做出许多关键决定，比如需要搜索哪个区域，需要使用哪些资源、设备和设施。
一般来讲，规划阶段从确定可能的幸存者位置开始，利用这些信息来划定需要搜索的区域。通常用于估计的信息包括：搜救人员在过去在该地区搜救过程中的经验，失踪者的生理和心理状况，天气情况以及地形和地理条件。在进行搜救任务时，必须考虑多个因素，如以往搜索工作的结果、海流或风向等环境条件、幸存者最后被发现的位置、遇险事件发生的位置、幸存者原本的旅行路线、幸存者和他们所乘工具的状态以及可能存在的环境危险因素。
然后，利用该区域内的设施和SRU（搜救队）的分布来制定搜索计划。一般来说，搜索队伍不采用系统搜索，特别是当需要覆盖大面积时，而是采用概率方法，首先搜索幸存者更有可能出现的区域。部分原因是研究发现，三天后，遇险人员的存活几率迅速降低。如果一个人受伤，24小时内存活的几率会降低80%。因此，迅速寻找幸存者对于搜救任务至关重要。一旦制定了计划，就可以在操作阶段开始实施。实际搜索操作在这里执行。在此阶段，旨在找到幸存者，为他们提供任何必要的立即帮助，并将其送回安全地带。这之后是最后阶段，称为结束阶段。这是当幸存者不再处于危险状态时。如果发现不存在危险情况，或者寻找幸存者的可能性几乎为零，则可以提前到达结论阶段。如果发现对搜寻人员来说过于危险，则搜寻可能被放弃。无论原因如何，搜索行动最终都会终止，然后由RCC详细记录整个搜索过程。
2.1.3 搜索和救援的类型
搜索和救援行动的性质对搜索过程中所采取的程序和使用的设施具有重要影响。地形是其中的重要一部分。IAMSAR手册的第二卷讨论了地形对搜索行动的影响[19]。
一个山区通常会有稀薄的空气和飞机湍流的问题，因此直升机搜索通常不适用。在这种情况下，更适合在较高海拔使用固定翼飞机，但是这样一来目标就不能被吊起来安全撤离，而必须由其他熟练的团队进行营救。在极端气象条件下也可能出现类似的问题。地形越复杂，搜索队伍就需要越有经验和技能。许多类型的服务可能需要被调动，其中包括志愿者、森林服务、山地救援队、空降救援队、执法部门、消防人员甚至滑雪俱乐部。
通常情况下，飞机内的人员或在其他搜救船只上的人员以及地面上的搜救队伍都存在一定的危险。因此，评估区域的危险性对于提供有效的援助以避免使搜救人员陷入不必要的危险至关重要。根据搜索需要发生的环境类型，可以将搜救操作分为不同的类别。根据“搜索与恢复工程网站”上的一篇文章[21]，通常的做法是将搜救分为以下几类：地面搜救、山地搜救、海上搜救、城市搜救和战斗搜救。地面搜救通常由志愿者或当地执法部门执行，涉及到地面上处于困境中的人员。这种搜救可能涉及逃离家庭的人、迷路的人、由于天气等原因处于困境中的人或其他任何原因导致的人。它还可能发生在乡村和城市地区。山地救援通常涉及在洞穴或山地地形中处于困境的人。这可能是由于洞穴探险或攀岩事故造成的。需要专业的带有登山装备的队伍来协助那些处于困境中的人。由于地形可能很危险，而且洞穴网络通常没有详细的地图，因此这通常是危险的工作。
海上救援通常涉及处于困境的海上船只。搜索通常由海军或海岸警卫队等机构进行。使用海上船只和飞机，例如直升机，来定位和营救那些处于困境中的人。
城市救援不应与地面搜救混淆。它涉及在自然灾害或其他干扰导致建筑物倒塌的城市地区中寻找处于困境的人。人们被困在瓦砾中，挖掘通常非常具有挑战性。消防员、医疗人员、当地执法部门和各种其他团队可能参与城市救援。战斗救援涉及在或靠近战争活动区域的救援行动。这是一种非常专业化的救援行动，通常涉及到受伤的战斗人员。无论是哪种类型的救援行动，规划和协调对于搜索行动的成功至关重要。确定地形的类型、危险以及所需的救援服务对于确保响应迅速，帮助处于困境的人尽快得到帮助至关重要。
2.2 搜索和救援中的机器人技术
搜索和救援机器人技术可以分为两类。第2.2.1节简要介绍了被用于搜索和救援的遥控机器人和无人机。特别讨论了机器人在搜索和救援行动中能够扮演的各种角色。相比之下，第2.2.2节通过使用路径规划和优化算法的自动化无人机帮助搜索行动。
2.2.1 用于搜救的遥控机器人和无人机
根据Springer机器人手册[22]，机器人可以以多种方式应用于搜救工作中。除非另有说明，本部分的例子均来自该手册。机器人可以应用于实际的搜救任务中，或用于绘制需要搜索的区域地图。机器人可以用于清除瓦砾或检查建筑物，以确定是否安全。它们也可以用于医疗援助，如运送医疗用品或帮助医务人员与幸存者进行沟通。此外，它们还可以用于提供后勤支援，例如协助运输设备和物资。无论其角色如何，搜救机器人旨在加速搜救行动，尽可能迅速地援助幸存者。机器人被用于大型搜救行动的一个最显著的例子就是在2001年世界贸易中心灾难中。无人地面车辆被用来在瓦砾中搜寻幸存者。他们成功发现了几组遗骸并检查了基础设施的损坏。在美国的几场大型飓风期间，无人机和地面机器人被用于辅助搜索和救援。在卡特里娜飓风期间，使用了一架电池供电的固定翼无人机，以及一架适用于高风速操作的电池供电直升机。它们被用于探索难以到达的地区，例如被废墟和洪水隔绝的地区。为了确定仍需要援助的地区，还使用了一个银狐。这是一种内燃机固定翼无人机，通常由美国海军使用。所有无人机都飞行在受管制的空域以下，并在检查各个地区时直接向搜救人员提供信息。在丽塔飓风和威尔玛飓风中，还使用了内燃机固定翼无人机来勘测灾区，但它们是在受管制的空域内飞行的。这些是特别为耐久性而制造的军用Predator无人机，但需要更多的操作人员。它们通常也更大，需要更大的降落和起飞区域。在海上搜索和救援中，可以使用远程操作的水面或水下车辆进行协助。其中一个例子是名为“紧急综合救生绞索”（EMILY）的机器人，它是一个能在水面上移动的远程操作机器人，并且充当浮标。它已经成功地用于帮助地中海难民，并正在全世界范围内部署。研究人员希望在未来为这个机器人增加更多的自主能力。在搜索和救援行动中，无人地面、空中、水面和水下车辆显然是必不可少的，它们可以进入难以到达的区域，代替搜索人员行动或收集有价值的信息，以确保他们自己和幸存者的安全。
2.2.2 用于搜救的自动化无人机
本节讨论了无人机应用于搜救方面的情况。自动化部分通常采用无人机的路径规划或搭载热像和/或视觉摄像头进行目标检测。每种情况下使用的算法和取得的成功水平进行了总体讨论。第2.2.2.1节描述了一种实际上已被用于地面和海上搜救的技术。随后的各节介绍的是在仿真或实际中进行测试但尚未积极用于搜救行动的应用。
2.2.2.1 由DroneSAR实现的完整方案
DroneSAR是一家爱尔兰公司，开发了一套用于协助搜救的DJI四旋翼无人机系统[1]。他们创建了一个用户友好的应用程序，用户可以标记要搜索的区域，它将为四旋翼无人机规划覆盖路径。该算法使用简单的来回操作或手动输入航点的方式来规划四旋翼的航线。实时将机载视觉或热成像视频传回地面站，以帮助地面团队快速反应发现目标。目标是更快地找到幸存者，减少地面和海上搜救队伍的风险。根据与搜索和救援队伍的测试，发现在一个平方公里内，五个人搜索幸存者需要两个小时，而他们的系统能够在不到20分钟内发现目标。据该公司发布的一段信息视频[24]显示，目前由飞行员在飞行中回顾录像，并定位目标。然后，无人机将发送GPS坐标给搜索和救援队伍，以协助和营救幸存者。未来，他们计划添加基于人工智能（AI）的自动人体检测算法。
2.2.2.2 基于人工智能的多无人机方法
San Juan 等[25]提出了多种方法，用于进行智能无人机地图生成和离散路径规划，以用于搜索和救援行动。搜索区域的地图被分成网格，并为每个格子分配一个风险/占用值，表示该格子被占用的概率和对占用者生命的潜在危险。风险/占用网格指示哪些格子应该更早地被访问，并用于离散路径规划。使用四种不同的离散路径规划方法来为单个无人机生成要遵循的路径点：一个潜力场方法，一个模糊逻辑方法，一个自适应网络模糊干扰系统（ANFIS）。该方法通过执行两种不同的群体形态（自由形态和分布形态）的离散路径规划，将其扩展为使用多个无人机。
对于自由群体形态，离散路径规划算法同时并行地为两个或更多无人机执行。每个无人机沿着独立的路径进行覆盖区域的移动。在计算航点时，分享已被无人机访问过的单元格的信息，以避免计划访问已经被访问过的单元格。
对于分布群体形态，地图被分割成与无人机数量相等的子区域，并为每个无人机分配一个需要覆盖的区域。
这些方法在模拟中进行了测试，结果显示，自适应网络基于模糊干扰系统（ANFIS）方法在一般情况下表现最佳，并且分布形态比自由形态效果更好。
2.2.2.3 多架无人机和不断变化的高度在线进近
在2009年和2010年，有研究者发表了多篇有关使用无人机进行搜救的文章。他们的第一项工作涉及协调搜索行动，使用一群无人机来寻找位于二维搜索区域内的单个静止目标[26]。他们提出了一种在线方法，使用四旋翼飞行器进行搜索。无人机使用朝下的摄像头进行目标检测，使用板载 GPS 进行定位。将搜索区域划分为一个网格，并为每个单元格分配一个数值，表示目标在该单元格内的概率，创建一个概率占用网格。每个无人机都维护其自己的占用网格，并在探索区域时更新单元格的值。当它们在通信范围内时，无人机会相互传递其占用网格。无人机们以解耦的方式搜索区域，并应用最陡梯度法来确定下一个要访问的单元格。该方法在模拟中进行了测试，结果显示，使用多个共享信息的无人机，可以显著缩短找到目标所需的时间。
在第二篇论文[27]中，作者们在原有工作的基础上增加了对同一细胞多个观察结果进行融合的能力，并考虑了无人机的高度变化。在第三篇论文[28]中，他们提出了目标检测算法，利用无人机下向摄像机的视频进行目标检测。他们发现，采样率应根据应用需求选择。在搜救方面，采样率应选择最小化漏检的情况。在第四篇论文[29]中，他们研究了三种不同的策略应用于搜救中，即贪婪启发式、基于潜力的算法和部分可观测马尔可夫决策过程(PO-MDP)。这些在线方法旨在解决信息共享限制、避免碰撞以及传感器数据中的不确定性。这些方法在模拟中进行了测试，结果显示，PO-MDP实现了最快的目标检测。
2.2.2.4 基于一个无人机和人体检测算法的在线方法
Rudol和Doherty（引用[30]）提出了一种用于无人机搜救任务的人体检测和地理定位技术，该技术利用了彩色和热像数据。
他们的技术使用一架配备了视觉和热像相机的单一无人直升机。无人直升机在搜寻区域上方来回移动，并收集视频片段。然后使用人体检测算法对这些片段进行分析。
低分辨率的热像图像被用来寻找潜在的人体位置，然后利用高分辨率的视觉图像进行确认。
路径规划器使用Wzorek等人之前开发的运动规划框架来制定无人机的来回移动路径。
[31]. Wrozek等人开发了一种单旋翼无人机的动作规划框架，该框架整合了两种基于样本的动作规划技术——概率路线图（PRM）和快速探索随机树（RRT），以及一个在路径执行过程中使用的路径跟踪控制器。他们采用在线规划方法来改变无人机的飞行路径，以响应环境中的某些动态变化。动态变化通过使用禁飞区或弹出区域来处理，这些区域可以由地面操作员添加或删除。他们的系统经过仿真和实际飞行验证。他们的算法被发现以25 Hz的速率检测人类，并且被设计成优先考虑错误正面检测而不是错误的未检测。值得注意的是，Wrozek等人开发的动作规划框架是一种点对点路径规划器。Rudol和Doherty通过使用点对点路径规划器来执行前后运动以覆盖搜索区域，将其扩展为CPP。
2.2.2.5 具有服务质量要求的多个无人机方法
Hayat等人[32]提出了一项利用多个无人机进行自动化搜索和救援的研究工作。该问题被形式化为一个MCPP问题，并将通信作为一个附加的任务目标。此前开发的多目标路径规划（MOPP）算法称为Simultaneous Inform and Connect（SIC）算法[33]，因为它可以根据不同程度的覆盖范围和连通性进行调整。
SAR问题可以分为三个任务：搜索任务，通知任务和监视任务。搜索任务涉及到路径规划器的使用，以实现覆盖和检测静止目标。一旦检测到目标，其位置需要作为通知任务的一部分传输到地面站。最后，需要建立良好的服务质量 (QoS) 连接链路，以便在监视任务中可以实时监视目标位置。使用遗传算法 (GA) 来优化完成所有三个任务所需的时间。重新规划被用来在检测到目标后重新配置 UAV，并建立与地面站的稳定连接。在模拟中测试了两种不同的 SIC 策略。其中一种同时优化了三个任务，而另一种则优先优化了搜索和通知任务，然后是监视任务。通过模拟发现联合优化技术能够产生更好的结果。结果还表明，对于小型 UAV 群组，偏重连通性能够产生更好的结果，而对于大型群组，则偏重覆盖能够产生更好的结果。总体而言，与仅将连通性视为限制而非目标的类似算法相比，这些算法也显示出更快的任务完成时间。
2.3 运动规划
本节概述了文献中发现的一般运动规划概念和技术，特别是来自 Steven Lavalle[34] 运动规划书的内容。
在机器人学中，运动规划是将机器人任务的高级规范转换为机器人必须移动的低级描述的问题。Lavalle将运动规划和轨迹规划分为两种不同的问题。运动规划专注于在某个环境中从一个构型移动机器人所需的一系列平移和旋转，通常忽略动力学和其他微分约束。轨迹规划通常指如何执行一个运动规划算法的解决方案，以遵守动力学和微分约束。
运动规划问题通常由机器人、环境和计划组成。规划算法用于规划机器人在环境中执行的路径，机器人然后执行该计划。计划可以在仿真或实际世界中执行。
运动规划问题可以分为连续和离散两类。连续规划将机器人建模为具有连续输入的实体，这些输入用于将机器人移动到连续状态空间中，解决方案是通过确定适当的输入信号与时间来建立的。离散规划将机器人建模为具有一组有限的操作，这些操作可以应用于离散的状态集合，解决方案是通过确定适当的操作序列来建立的。
离散规划技术通常使用搜索方法，如Dijkstra算法和$A^*$算法，来寻找状态和操作的最佳序列。连续规划技术分为两类：组合方法和基于采样的方法。
组合方法通过构建离散环境表示来制定连续路径，包括机器人和环境中的障碍物。这些方法也被称为确切方法，因为它们完全表示原始的连续问题。组合方法是完整的，这意味着当存在解决方案时，它们会保证找到一个解决方案，或者在解决方案不存在时正确报告失败。组合方法使用像梯形分解和Voronoi图这样的方法生成离散路线图，然后使用离散搜索方法如$A^*$遍历这些路线图。
基于采样的方法使用碰撞检测方法对连续状态空间进行采样，然后执行离散搜索。基于采样的方法可以分为分辨率完备和概率完备两种，它们是完备性的较弱形式。分辨率完备意味着如果存在解，则算法将在有限时间内找到；然而，如果不存在解，则算法可能会永远运行。概率完备意味着随着采样点数量趋近于无穷大，找到解的概率趋近于一。采样方法的例子包括快速随机探索树（RRTs）和概率路标图（PRMs），分别是单查询和多查询方法。
运动规划问题也可以根据完成的高级任务的性质进行分类，任务可以涉及单个机器人或多个机器人。在人工智能领域，机器人也被称为智能体或决策者。多机器人规划可能非常具有挑战性，因为机器人不仅必须避免与环境中的障碍物相撞，还要避免彼此之间的碰撞。
图2.1提供了根据高级任务对不同类型路径规划的概述。
通常运动规划可分为点对点路径规划和覆盖路径规划（CPP）。在点对点路径规划中，任务是从一个点移动到另一个点并/或改变方向。而在CPP中，任务是覆盖环境中的每个点。涉及多机器人的点对点路径规划可分为汇合任务和分配任务。如果所有机器人的目标位置都相同，则称为汇合任务。如果机器人具有不同的目标位置，则称为分配任务。
最后将运动规划算法分为离线或在线。对于离线规划，路径规划在路径执行开始前进行和完成。而对于在线规划，路径规划和路径执行是同时进行的。离线规划假定具有完整的环境信息。对于在线规划，机器人在移动过程中感知环境，并且在机器人执行计划的同时生成和更新计划[35]。
2.4 覆盖路径规划
覆盖路径规划（Coverage Path Planning，CPP）是一般运动规划问题的一个子集。覆盖任务指的是访问环境中的所有点，而不是通常的起点-目标类型任务[36]。CPP可以归类为与运动规划相同的几个类别。它可以被分类为离散或连续、在线或离线，以及单个代理或多个代理问题。
CPP可用于多种不同的应用领域。一些过去的例子包括与吸尘机器人、喷漆机器人[37]、清洗窗户机器人[38]和自动割草机[39]的使用。对于水下车辆，它可用于检查难以到达的水下结构[40]；对于地面车辆，它可以用于自动化农业机械实现智能农业[41]。
已经进行了许多研究，以概述CPP领域的可用文献和取得的进展。在2001年，Choset [17]进行了一项研究，将CPP分为四个类别：启发式、近似、半近似和精确细胞分解。在后来的论文中，这被称为Choset的分类法，并且被广泛用于对不同类型的CPP算法进行分类。细胞分解方法都依赖于简化环境以实现可证明的完全覆盖。Choset还简要介绍了多机器人覆盖路径规划（MCPP）算法。
启发式方法使用一组规则来产生简单的行为，例如沿墙壁行走，以覆盖搜索区域。
这些启发式方法可能效果不错，但不能提供任何可证明的保证来确保成功的覆盖。近似细胞分解方法使用细网格来表示要搜索的自由空间。半近似细胞分解方法依赖于搜索空间的部分离散化，其中单元格宽度固定，但顶部和底部（或天花板和地板）可以具有任何形状。精确的细胞分解方法使用一组不相交的区域，每个区域称为一个细胞，它们的并集填充目标环境。然后机器人使用简单的前后运动覆盖每个单元格。
2013年，Galceran和Carreras[42]提供了最新的机器人覆盖路径规划研究报告，反映了自Choset调查以来的进展。该调查回顾了最成功的覆盖路径规划方法，并讨论了它们所报道的现场应用。该调查还涵盖了三维场景中的CPP，并简要介绍了在CPP中应用同时定位和映射（SLAM）来处理定位不确定性的情况。
在2019年，Cabreira等人[43]发表了一篇关于无人机覆盖路径规划的综述。他们考虑了简单的几何飞行模式和更复杂的基于网格的解决方案，这些解决方案考虑了关于搜索区域的完整和部分信息。他们还根据Choset的分类法对调查的覆盖方法进行了分类，包括无分解、精确细胞分解和近似细胞分解。他们的评论还考虑了搜索区域的不同形状，如矩形、凹多边形和凸多边形。
一般来说，多机器人方法为CPP增加了复杂性。最明显的挑战是避免碰撞。机器人需要相互合作来实现覆盖，同时避免与障碍物和彼此相撞。在2020年，张等人[36]对无人机团队的合作路径规划进行了全面的调查。他们提出了一种分类法，将合作路径规划问题分为三个方面：任务类型、规划框架和环境。任务类型分类为约会任务、分配任务或覆盖任务。规划框架分类为集中式、分散式或混合式。环境可分为已知和未知。
下面的章节将探讨不同类型的覆盖路径规划技术。第2.5节将涵盖单个机器人的覆盖路径规划。单个机器人路径规划将分为精确方法、基于采样的方法、A*和波前覆盖、生成树覆盖和人工智能方法。
第2.6节将涵盖多机器人覆盖路径规划（MCPP）。MCPP方法可分为分布式或非分布式，以及离线或在线。分布式方法是指单个无人机的路径不交叉的方法。搜索区域通常被分为若干个独立子区域，每个无人机被分配到一个独立子区域进行搜索。非分布式方法是指无人机可以自由交叉的方法。搜索区域不被分割，无人机的路径同时计算，知道哪些单元已被访问[25]。离线方法是指路径规划在路径执行开始之前完成的方法，通常在已知环境下进行。在线方法是指路径规划和执行同时进行的方法，通常在未知或部分已知的环境中进行。
2.5 单机器人覆盖路径规划
在这里详细讨论单机器人覆盖，是因为几个多机器人覆盖路径规划问题利用了它们。
例如，分布式多机器人覆盖路径规划往往将环境划分为可以由单个机器人覆盖的子区域。
第2.5.1节和第2.5.2节讨论了精确和基于采样的覆盖技术，而第2.5.3节至第2.5.5节涵盖了不同的基于网格的方法。
2.5.1 精确方法
Lavalle描述的组合方法也称为精确方法。CPP的精确方法使用相同的几何原理将区域划分为单元格。然而，与其创建路网不如创建邻接图，并用其在单元格之间移动。然后，每个单元格通常使用简单的操作进行单独覆盖[42]。
分解中的每个单元格都是邻接图中的一个节点。使用详尽的步行来确定访问这些节点的顺序，以实现覆盖。然后使用简单的操作（例如来回移动），对每个单元格进行单独覆盖，通常提供完全覆盖[44]。
一种流行的确切方法是梯形分解法[34]，该方法基于多边形障碍物的顶点将环境分解为梯形（凸单元格）。 boustrophedon方法建立在梯形方法上。它仅查看可以从其上下延伸线的顶点，从而减少单元格的数量[42]。这减少了覆盖路径的最终长度，使其更加高效。
这两种分解方法都适用于二维覆盖问题。它们是离线方法，因为环境必须事先已知，并且仅适用于多边形障碍物[42]。这意味着可能需要进行一些近似来使用多边形来表示环境。
还有一种更灵活的精确方法，它使用摩尔斯函数进行分解，也可用于此类问题[45]。
这种方法不再需要多边形环境，理论上可以扩展到更高维度的环境中。
2.5.2 基于采样的方法
基于采样的方法已经被应用于覆盖路径规划。它们更容易适配三维环境，更适用于在线或实时方法。它们也更容易处理包含动态障碍物的变化环境。[34]
Nourani-Voutani等人[46]使用基于采样的CPP执行自动修剪草坪。RRT作为局部规划器与使用螺旋运动覆盖地图中的点的全局规划器组合使用。然而，不能保证解决方案。由于路径的随机性，也不一定能够实现完全覆盖，但这被认为是实时方法。
Englot和Hover[47]使用概率完整的基于采样的CPP来检查复杂结构。冗余路标算法构造路标，然后使用RRT进行局部点对点规划，其中还包括避免碰撞。
Danner和Kavraki[48]应用了类似的策略，旨在自主检查三维结构。使用的方法是概率完备的。在三维情况下，类似于概率路图的方法被用来实现覆盖。
Wzorek等人[31]使用了PRM和RRT的结合方法来开发一种具有重新规划功能的在线点对点路径规划器。后来，由Rudol和Doherty[30]扩展为覆盖解决方案，使用来回运动方式。
2.5.3 $A^*$和Wavefront基础的覆盖
$A^$是一种离散规划方法，通常用于点对点路径规划。在组合运动规划或多次查询的基于采样的方法中，如PRM，路标通常被形成以表示环境。这些路标可以使用$A^$或其他离散算法进行导航。$A^$是从Dijkstra算法构建的，它可以被看作是一个考虑优先队列成本的前向搜索。$A^$简单地预测到使用启发式方法到达目标的成本。Dijkstra也被优化为所谓的波前规划器。利用这种技术，等成本点被分成“波浪”，算法基本上会向外传播这些波浪直到达到目标。[34]
Barrientos等人[49]将这种波动式规划方法应用于CPP，旨在最小化旋转和重访单元格的数量。
一些作者也将$A^$算法扩展到CPP上。Viet等人[50]将$A^$方法与 boustrophedon 方法相结合，后者通常用于精确CPP。这是一种在线方法，逐步构建 boustrophedon 区域，并使用A*从一个区域移动到下一个。
在点对点路径规划中，通常的目标是实现尽可能短的路径，启发函数被设置为这个目的。对于CPP，代价函数可以改变为最大化覆盖面积。Le[51]等人在基于网格的离线方法中使用这个技术，他们试图将得到重新访问的单元格的数量最小化。他们使用关键路径点和基于A*的锯齿形运动。
Dogrue和Marques[52]使用启发式函数，目标是最小化旋转的数量，类似于之前提到的波前规划器。这是有用的，因为旋转通常比直线运动消耗更多的能量。
2.5.4生成树覆盖
生成树应用于离散环境中。当它们用于覆盖路径规划应用时，被称为生成树覆盖(STC)，可以用于离线或在线方法。
Gabriely和Rimon[53]展示了生成树可用于实现覆盖的各种方式。他们首先展示了环境在规划阶段之前已经完全知道的离线情况。环境被离散化为一个由大单元格组成的网格，每个大单元格包含四个小单元格。机器人移动到小单元格时，使用大单元格中心作为生成树公式的节点。生成树可以绕过来实现近似完整覆盖而无需回溯。使用最小生成树 (MST) 算法（称为 Prim 算法）创建生成树。这最小化了树的总权重。权重可以用来偏向于某个坐标轴方向进行搜索。
还展示了在线 STC 技术，其中对环境的唯一先验知识是障碍物是静态的。该算法类似于离线方法增量式地增长跨度树，并随着获取更多环境知识的不断推进。
由于采用了环绕方法，故离线情况下生成的覆盖路径是闭环路径。在线情况下，地图通常从起始位置向外扩展，一般会形成一个或多个螺旋形的覆盖路径。
2.5.5 人工智能方法
Juan等人[25]比较了几种用于CPP的人工智能技术。比较了四种方法，其中一个方法采用了GA算法。这四种方法分别是拉帕尔玛引力、拉帕尔玛模糊逻辑、自适应网络模糊推理系统（ANFIS）和粒子群优化（PSO）方法。
所有的方法都在离散化的网格环境中实现。一个风险/占用的地图作为输入提供给每个环境。这张地图给予了单元格优先级，以鼓励首先覆盖特定区域。
这些算法在搜救与救援（SAR）的背景下进行了评估，发现ANFIS方法在这种应用中表现最佳。如果单元格之间的优先级变化很小，吸引方法效果良好。如果环境中的一个大部分区域具有较高的优先级值，模糊逻辑方法表现良好。总体而言，PSO技术的表现不佳。
2.6 多机器人覆盖路径规划
本节讨论在使用多个机器人时的覆盖路径规划（CPP）。分布式情况下的离线技术在第2.6.1节中进行了讨论，非分布式情况下的离线技术在第2.6.2节中进行了讨论。在线技术在第2.6.3节中进行了简要讨论。
2.6.1 分布式离线方法
一个成熟的离线CPP方法是区域划分技术。这种方法将一个区域划分为多个子区域，供各个机器人覆盖。每个机器人应该能够使用单机器人覆盖路径规划技术来覆盖其分配的区域。本节讨论了几种不同的区域划分方法。在每个区域划分的部分中提及了用于执行子区域覆盖的方法，因为这些方法对于生成最终的覆盖计划非常重要。这些部分显示了各种不同的划分结果，这些结果来自于各自部分中讨论的研究论文。这些图示旨在说明每个算法所实现的不同划分方式。
2.6.1.1 六边形分割
Azpúrua等人[2]提出了一种用于地球物理勘测的分布式MCPP方法。他们的实现使用规则的六边形来分割感兴趣的区域。六边形单元格大小相等，并分配给单个机器人进行搜索。
六边形方法使用K-means算法对六边形进行聚类，以便将它们分配给机器人。这样可以确保每个机器人分配到相似数量的单元格。种子单元格与机器人是对应的，因此一旦确定了种子位置以实现均匀的单元格分布，机器人的初始位置也就确定了。生成的子区域由多个六边形单元格组成，并且是连续的。然后，可以使用来回运动方式覆盖分配给一个机器人的所有六边形单元格，类似于精确的单机器人覆盖方法。
拥有相似大小的子区域意味着每个机器人可以在相似的时间内执行其覆盖路径，这在优化燃料使用和任务完成时间时具有优势。然而，这种算法不允许随机的机器人初始位置，这可能是一个不利因素。
在此实现中考虑了静态障碍物，但最小障碍物分辨率是一个六边形的大小，可能无法很好地代表环境。然而，覆盖是分辨率完整的，六边形的大小表示分辨率。
该应用在具有有限飞行时间的无人机上在真实环境中进行了测试。即使存在传感器噪声和环境因素，路径仍然是可行的。
2.6.1.2 Voronoi划分
Nandakumar和Rao[54]展示了一种将多边形划分为一定数量相等面积多边形的区域划分方法。
另一个相关的方法也源自数学领域，即Voronoi划分。这种划分基于距离将区域分配给种子点。其核心思想是，分配给种子点的区域包含了距离该种子点比其他任何种子点更近的所有点。
如果将Voronoi划分应用于MCPP问题，那么种子点就等同于机器人。这种划分适用于任意数量的机器人和任意起始位置，但除非它们均匀分布，否则区域的大小将不相等。在这些情况下，距离通常使用欧几里得距离，而区域之间的边界表示距离两个种子点相等的位置。
Nair和Guruprasad于2020年发表了一篇文章[3]，介绍了在离散空间中使用静态障碍物的维诺图划分实现MCPP的方法。他们使用基于网格的区域表示，并比较了几种不同的方法。他们研究了基于地理曼哈顿、曼哈顿、地理和欧几里得距离的维诺图划分。
欧几里得距离技术会产生作者所称的“不连续子区域”。这意味着属于子区域的单元格由于该子区域内的障碍物而无法被指派到机器人。他们通过使用地理距离解决了这个问题。这种方法使用的是欧几里得测量，但它不是计算两个单元格之间的直线距离，而是使用两个单元格之间的无碰撞路径来计算距离。
另一个问题是，由于他们使用的是离散空间，当使用欧几里得距离时，一些单元格部分属于两个子区域，而不是完全属于其中一个。他们的解决方案是使用曼哈顿距离。最终，他们利用测地线曼哈顿距离生成分区。因此，他们提出了测地线曼哈顿泰森多边形覆盖（GM-VPC）。
图2.3显示了一篇文章中使用不同距离度量进行Voronoi划分的区域划分结果。在两个图中，黑色方块表示障碍物，圆点表示机器人的起始位置，网格上的黑线表示Voronoi划分的边界。在图2.3a中，灰色方块表示不会被覆盖的区域。通过图2.3b中展示的GM-VPC技术，这个问题得到了明显的解决。
作者在精确解决方案和近似解决方案的模拟测试中使用了这些划分方法。
精确解决方案采用了一个boustrophedon覆盖规划，而近似解决方案采用了一个生成树。
在使用测地线曼哈顿距离时，两种方法的性能都表现更好[3]。
2.6.1.3 协商协议
协商或谈判协议是指涉及任务分割的过程。在CPP的区域划分中，任务代表要分割的区域。
Rossi等人[4]提出了一种使用Rubinstein的交替提议协议的协商模型，用于区域划分。Barrientos等人[49]通过引入个体区域覆盖技术的Wavefront规划器，进一步完善了这一实现。还进行了一系列现场测试，以评估系统在精密农业环境中的表现。
该实现的重点是开发一种分布式算法，能够考虑机器人的能力。这意味着机器人不必是同质的，可以具有不同的飞行时间能力、机动性、板载设备等。
他们实现了他们的算法，发现它可以实现接近最优的结果。该算法试图最大化每个机器人的区域细分大小（基于其能力），同时最小化子区域重叠。该算法还可避免区域中的静态障碍物或禁飞区。图2.4显示了使用该方法实现的区域划分示例。该区域被划分为两个不同的机器人的红色和绿色区域。蓝色区域表示禁飞区。
区域划分后，根据机载摄像头的视野范围将环境分割成单元格，以便波前规划器可以使用覆盖这些区域。为了覆盖这些区域，他们使用了一种叫做 Bresenham 线算法的方法来逼近离散空间中的划分线，以使其经过单元格中心，从而有效实现协商协议生成的多边形。
所实现的区域划分有时会产生非凸形状，但是波前规划器可以有效处理。他们还通过最小化旋转次数和不允许返回路径的方式最小化能源消耗，可以指定机器人的起飞位置。在子任务协商中，会考虑从指定起飞点到子区域覆盖起点的距离。此外，他们还能够预先指定机器人降落位置。
但是他们的实现明显存在一个缺点，那就是覆盖似乎不完整。区域之间的边界经过路径点（单元格重心），从而被排除在覆盖算法之外，未被覆盖。
2.6.1.4 多机器人生成树覆盖算法
多机器人生成树覆盖算法(MSTC)是单机器人生成树覆盖(STC)算法的一种变体。Hazon和Kaminka [5] 在2005年的一篇论文中介绍了MSTC的实现。他们提供了两种MSTC的变化形式：一种允许回溯，一种不允许。这两种变体仍然利用单个生成树，只是用多个机器人而不是一个。
他们强调鲁棒性和效率，同时也保证了完整性。他们演示了一种算法，将围绕生成树的路径分段，以平均分配给机器人。然而，当机器人紧密聚集在一起时，他们的方法变得低效。这是由于一个机器人只能导航路径，直到它到达路径上下一个机器人的初始位置。
图2.5显示了当机器人沿着绕过树的路径均匀分布时生成的路径。蓝色圆点表示机器人的初始位置，生成树以红色表示。他们建议的第二种方法在一定程度上弥补了这个问题。它允许回溯并提高效率。
理想情况是，所有机器人的路径长度都接近，前提是它们是同质机器人。当机器人的起始位置随机时，该算法不能保证这一点，但是允许回溯可以改进结果并缩短完成覆盖的时间。
2.6.1.5 DARP
Kapoutsis等人[6]提出了一种独特的分布式技术，称为最优多机器人覆盖路径规划(DARP)的分区算法。该算法基于机器人在基于网格的环境中的起始位置将环境划分给多个机器人。它采用迭代方法，使子区域随着时间的推移趋向于最优划分。该环境包括静态障碍物，但不允许形成封闭的、无法到达的障碍物区域。
该算法通过将每个单元格分配给最近的无人机来开始。然后，该算法迭代地调整单元格距离值以改变单元格分配并制定解决方案。当所有单元格都分配给一个机器人，所有子区域大小相同，子区域连续且分配给一个特定区域的无人机具有初始位置时，就可以实现最优解。
如果无人机是同质的，那么等大小的子区域意味着覆盖每个子区域所需的时间是相似的。如果这些区域是相邻的，并且每个区域都包含一个无人机的初始位置，那么这些区域可以独立地进行覆盖，无需无人机穿越彼此的区域。这意味着消除了无人机之间的碰撞。
DARP实现的区域细分结果如图2.6所示，该图是直接从其论文中提取的图形。
采用生成树覆盖（STC）方法来覆盖各个子区域，最终在网格分辨率下实现了完全覆盖。该算法的性能与MSTC和多机器人森林覆盖（MFC）方法进行了比较，以展示哪种算法最适合创建每个子区域等长路径。DARP算法性能优于其他算法，最长和最短的机器人覆盖路径之间最多相差四个单元。
迄今为止，多位作者已经利用这种算法。高等人[55]将蚂蚁群优化应用于DARP和STC的组合中，以减少旋转次数，从而降低飞行过程中的总能量消耗。Baras等人[56]通过允许垂直机动来避免障碍物，解决了无法到达的区域问题。通常，他们的算法与原始的DARP算法相同，但添加了第二个阶段，即使用三维机动处理未连接的区域。
2.6.2 非分布式离线方法
本节介绍三种不能归类为分布式方法的方法，因为计划的覆盖路径可能会相交。规划过程中区域不被划分为子区域。每个小节都涵盖了不同的技术。有趣的是，这些方法通常是基于现有的单机器人覆盖技术。
2.6.2.1 使用MFC的MCPP
曾等人在2005年发表了多机器人森林覆盖（MFC）作为一种多机器人覆盖技术。其目的是改进多机器人跨越树覆盖（MSTC）方法。他们的想法是构建一棵树，并考虑将其分割，而不是像MSTC那样。它允许机器人路径重叠，这意味着存在冗余覆盖和机器人之间需要考虑避免碰撞。然而，它可以很好地处理无法避免回溯的独特场景。
Even等人[58]发表了一篇关于近似算法的文章，用于MFC的开发，其中特别使用了根树覆盖情景。对于MFC，根表示机器人的初始位置，然后为每个机器人生成一棵树。应用目标是最小化最大重量树的权重。这些树被其机器人（根）用于覆盖区域。
基于MSTC和MFC的模拟，他们发现MFC生成了更接近最佳结果，并通常在较短时间内实现了覆盖。由于某些情况下存在路径重叠，因此MFC并不是真正的分布式方法。然而，此算法产生的结果可能非常接近分布式算法，这取决于环境。
2.6.2.2 使用人工智能的MCPP
Juan等人[25]在单个机器人的CPP案例中使用了人工智能（AI）方法，但也将其应用扩展到多个机器人的CPP案例中。他们研究了分布式情况，但没有提出将环境分成子区域的方法。他们还研究了两个和三个UAV情况下的自由编队情况，这将是本节的主要讨论。
自由编队CPP表示同时规划多个无人机在环境中的路径，了解机器人已经访问过哪些单元格。这意味着机器人的路径可能会在环境中交叉，因此实现时需要考虑避免碰撞。但是，他们的文章中没有涉及避免碰撞，只允许路径交叉。
预先对环境应用风险/占用格。这通过为单元格分配优先级，鼓励算法首先访问地图的某些区域。该算法被设计用于SAR场景，在这种情况下会很有用。
研究了三种人工智能方法，以及在基于网格的环境中进行优先分配。LaPalma景点法被发现在具有相当均匀优先级分配的环境中产生最短的路径。自适应网络模糊干涉系统（ANFIS）方法排名第二，模糊逻辑方法产生的路径显著更长。模糊逻辑方法在环境中优先级值相对较高的区域中表现良好。总体而言，ANFIS方法在一系列优先级网格上表现最佳。
2.6.2.3 MCPP 使用线性规划
MCPP使用线性规划线性规划可用于优化具有多个变量的线性问题，并尝试最小化或最大化某个成本。它们通常还受到多种约束条件的限制。
Avellar等人[59]将这种方法应用于多个无人机的CPP应用中。他们通过最小化最长无人机飞行路径的长度来设计优化问题，以最小化覆盖时间。
他们提供的一个贡献是考虑设置时间。根据他们的定义，设置时间是指操作员为无人机准备飞行所需的时间。他们具体考虑了场景，其中运营商少于无人机，这导致某些无人机的设置时间累积。
问题应用了几个约束条件。它们基于电池电源限制无人机的飞行时间，设置一个约束条件，使得每个节点只能被一个无人机访问，并将路径限制为封闭回路路径。
为了确保完全覆盖，他们制定了一个约束条件，确保一排中的所有节点都被一个无人机访问。他们还有两个可选的约束条件，避免穿过环境的对角线。障碍物在实现中没有被考虑，无人机的碰撞也没有被考虑。
2.6.3 在线方法
在线路径规划通常指在仍在收集环境信息的情况下生成规划。这种方法通常适用于高度动态的环境，其中障碍物位置难以（或成本较高地）预测。本节简要介绍了在线MCPP的一些内容。
一些单个机器人覆盖算法也有在线版本。Viet等人[50] 使用了牛耕式-$A^$算法，其中环境的牛耕区域是逐步构建的，$A^$算法用于从一个区域移动到下一个区域以进行遍历。Gabriely和Rimon [53] 制定了一种在线生成最小生成树覆盖（STC）算法，通过在不断了解的环境中逐步生成生成树。
采样方法非常适合在线方法。像RRT这样的单个查询方法避免了环境的显式表示，因此更容易在动态环境中使用 [34]。
通常，算法也会使用在线和离线的混合模式，其中对环境的某些信息是先验已知的，但数据仍然被收集以增量更新环境的某些方面。由于算法中存在在线元素，因此它仍然被视为整体上是在线的[34]。
通常，无人机的路径是动态创建的，用于在线路径规划，由于并非所有环境信息都可以先验知道，因此通常无法保证完全覆盖[34]。
当涉及到多机器人的在线CPP时，有一些例子。Luo和Yang [60]发表了一篇文章，展示了多个清洁机器人的CPP。该应用程序实现了神经网络来计划多个机器人在动态环境中的路径。没有学习程序,机器人在环境中将彼此视为动态障碍物，并始终知道其他机器人相对于自身的位置。
目标是最小化旋转并避免与环境中的其他障碍物和机器人发生碰撞，同时覆盖整个区域。
研究表明该算法在仓库环境中使用地面车辆可以有效工作，并能够实时执行。机器人在避免彼此和障碍物碰撞的同时，覆盖整个区域，且不会交叉路径或倒退
Waharte和Trigoni开发了一种多个无人机的在线应用程序，旨在进行搜索和救援操作。他们的算法迭代地更新环境的占用网格。这代表了目标可能在任何给定的网格单元中的可能性，基于所收集到的信息。每个无人机使用一个最陡峭的梯度方法来选择下一步行动。这种方法可能被认为是偏向于目标查找而非覆盖率，但结果类似于覆盖算法。
Hayat等人[32]使用遗传算法来优化在SAR操作中多个无人机的覆盖和通信。优先考虑与地面站的连通性，以确保新的目标信息能够有效地传达给SAR团队。这些信息可用于动态重新规划无人机路径。采用了一种多目标路径规划（MOPP）算法，以不同程度地优先考虑连通性和覆盖率。对于一小组无人机，优先考虑连通性效果更好，而对于大型组则优先考虑覆盖率效果更好。
2.7主要研究发现和设计决策
本节总结了文献中的主要研究发现以及基于所获得的知识做出的研究决策。
根据文献，得出结论:无人机可以为SAR操作提供有价值的支持。然而，使用无人机进行空中搜索并不适用于任何类型的环境。SAR（搜救）行动基于环境类型分为几个类别。航空无人机搜索非常适合地面、山区或海上搜救。但对于洞穴搜救来说不太适合，也不适合战斗和城市搜救。
在SAR行动的计划阶段，会确定可能的生还者位置，然后将可用的资源分配到各个搜索区域。无人机可以作为更大的SAR行动的一部分使用。搜索协调团队可以将更大的搜索区域划分为无人机搜索的子区域。
如果无人机搜索是自动化的，这意味着可以进行搜索而无需大量的人力资源。一个区域可以相比单个无人机，多个无人机可以更快地覆盖区域。
将多个无人机的自动化搜救行动建模为覆盖路径规划（CPP）问题时，可以选择分布式或非分布式解决方案。分布式CPP本质上提供了碰撞避免功能，因为各个无人机独立地搜索不重叠的子区域，彼此之间不存在碰撞的可能。非分布式解决方案允许路径相交，这意味着需要考虑碰撞避免问题。
在线路径规划可以灵活地适应动态环境，这些环境在搜索之前无法完全了解。离线路径规划适用于可以提前了解的环境。
本研究的目标是开发一种自动SAR方法，利用多个UAV协同搜索划定的区域。航空搜索方法被认为是最合适的方法，仅用于地面，山地和海洋环境。
自动化搜索将被建模为CPP问题，以便UAV对其分配的搜索区域执行系统化搜索。将使用分布式方法消除UAV之间的碰撞。
由于在SAR操作之前通常已经了解到环境状况，因此该问题被建模为一个带有静态障碍物的离线问题。由于SAR操作通常涉及大面积，因此假定固定翼UAV更适合进行搜索。它们往往比旋翼替代方案具有更长的续航能力。
第三章
概念化和建模
本章的主要目标是概述为本项目制定的假设以及它们对应用程序的限制。建立每个系统组件的一般数学模型，以提供整体问题的模型。第3.1节说明了一般的SAR问题，接下来的第3.2节描述了环境及其建模方式。第3.3到3.7节描述和建模环境中的元素，包括障碍物、无人机和需要查找的目标。
3.1 SAR问题
在SAR操作中，空中支援非常有用。历史上，像直升机这样的有人驾驶飞行器已被用于此类操作。然而，这些有人驾驶飞行器的飞行时间有限，它们的飞行路线并不一定适合在SAR情况下检测目标。
无人机等机器人的使用在SAR领域也有一些，第2.2节详细介绍了其中一些用途。无人机带来了一个令人兴奋的机会，使其在操作中支持自主飞行路径的车辆。搜索路径可以进行优化以减少寻找幸存者的时间。
此外，没有人需要驾驶飞行器，不仅降低了潜在飞行员的危险，还使人力可以集中在定位和救援幸存者上。有时某些区域可能很难到达，需要专业团队搜索这些区域以寻找幸存者[19]。无人驾驶飞行器可以用于搜索这些区域，而不会危及搜索团队。有人和无人驾驶飞行器的结合在SAR操作中也可能对更快地找到和援助幸存者有益。
DroneSAR在第2.2.2.1节中讨论过，证明了使用无人机可以显着加快SAR操作并协助找到目标。他们在20分钟内在一个一平方公里的区域内找到了目标，在一架自主无人机协助时，相比之下，一个由五人组成的地面团队在没有帮助的情况下大约需要两个小时才能达到同样的目标。
也可以推断出，使用多个无人机来协助搜救行动将会进一步提高发现幸存者的时间效率。如果它们并行搜索，更大的区域可以在更短的时间内搜索完毕。使用多个无人机，从系统搜索区域入手，可以为一个搜索和救援问题构建基础。
在图3.1中，可以看到一个使用多个无人机协助搜救行动的基本组成部分并进行了标记。
第一个显着的组成部分就是搜索区域边界代表了一支搜救团队所需搜索的范围。在这个区域内，需要找到的目标被标记为“X”，代表需要救援的一个或多个幸存者。
需要区分整个搜索区域和将要被无人机系统性搜索的区域。在第2.1.2节中，介绍了SAR的不同阶段。在规划阶段[19]中
确定整个搜索区域并制定搜索计划的阶段被认为是决定是否使用系统性无人机搜索来协助SAR操作的阶段。在SAR中，对整个搜索区域进行系统性搜索的情况并不常见，因为需要被搜索的区域通常很大，这样做是不实际的。通常采用概率方法，从可能存活者更有可能出现的区域开始搜索[19]。
如果认为在整个区域内进行系统搜索不切实际，那么无人机仍然可能很有用。可以利用无人机在区域内搜索一个或多个划定的子区域，作为更大搜索计划的一部分。实际的搜索将在操作阶段进行。
重要的是要注意，如果认为对搜索队伍来说太危险，搜索可能会被放弃。使用自动化无人机代替有人飞机或搜索小组意味着在搜索人员无法进行搜救时，搜救仍可继续进行。
在大多数搜救场景中，搜索小组可以根据经验猜测目标可能的位置。因此，无人机在飞行前并不知道目标的确切位置，而是试图确定它们的位置。
在图表中，无人机正在离开地面站，很自然地在SAR操作期间需要一个基地运营无人机，因为这将是它们起飞、降落和必要时加油的地方。该基站很可能是搜索团队接收由UAV收集的数据以协助SAR操作的地方。环境中的静态障碍物也显示在其中。这些障碍物是任何UAV不能飞行的区域的代表，可能是物理障碍物，例如电线或悬崖，或诸如人口密集地区或受限空域之类的不可飞行区域。 UAV必须在无障碍的空中飞行，直到找到目标。
3.2 搜索环境
根据搜索所进行的地形类型，SAR情况可以进行分类。一般来说，SAR被分为地面，城市，山区，洞穴，战斗或海上救援 [21]。第2.1.3节讨论了这些不同种类的SAR操作之间的区别。
自动化UAV可以提供的援助范围取决于救援的类型。在开阔的平原或海洋中，由于没有障碍物，它们可以从任何视觉或热相机中清楚地看到搜索区域。在极度森林的地区，由于植被的原因，能见度可能受到限制，因此航空支援是无助的。
不利的天气条件也会对能见度和飞行能力构成挑战。无人机通常是为在特定风况下飞行而设计的。高风速可能会使其无法飞行。雪、雨、雾、闪电或灰尘也可能通过损坏组件或使传感器读数不准确来影响无人机的飞行能力。特别是高湿度已知会影响光学传感器[61]。
除了损坏部件，这些元素还会降低能见度，使无人机上的摄像头更难检测目标。在夜间，无人机可能必须完全依赖于热图像，因为传统相机的图像大部分是黑暗的。
无人机在极端温度下也会面临挑战。火灾地区必须考虑为无人机的禁飞区。温度过高或过低的区域也需要排除在搜索区域之外。
如第2.1.3节所述，山区低密度空气也可能是一个危险。一般来说，固定翼无人机更适合这种搜索。值得注意的是，山地救援搜救队通常在困难的地形中工作，需要专业的技能和设备。使用空中搜索可以减少这类团队的风险。
洞穴搜索通常也与山岳搜索分组讨论。然而，高空、系统化的无人机搜索在洞穴中并不实用。因此，洞穴不适用于本项研究。由于战场环境不稳定且不可预测，与其他场景相比需要进行特别考虑，因此在该项目中不涉及战斗救援。
自然障碍物会影响无人机，这取决于无人机的飞行高度。这些障碍物可能是树木、岩石突出部或其它高度足以遮挡无人机的天然元素。人造障碍物如电话塔、电力线路、塔和桥梁也可能在飞行过程中成为障碍物。人造建筑和残骸也可能会使空中搜索出现可见性挑战，如果幸存者在建筑物内或下面。
城市搜索和救援，通常涉及人们被困在某种碎石中。因此，系统的空中搜索可能并不十分适用于寻找幸存者。然而，在过去的大型灾难如“卡特里娜飓风”中，无人机已被使用过。这在第2.2.1节中已经讨论过了。
在人口稠密地区飞行无人机具有独特的挑战。如果独立考虑，将无人机用于诸如勘测等非目标定位的角色将更有用。因此，并未在本项目中专门考虑城市搜救。
另外，也可能会遇到禁飞区的障碍，这可能是受限制的空域、人口密集区、私人土地或受保护的野生动物区域等，无人机不得飞行。
一般而言，无人机面临与有人机相似的限制，需要搜索团队进行仔细考虑。优点是如果无人机在危险条件下飞行，没有飞行员会受到危险，最坏的情况是无人机失事。
假定无人机预计将在一个有界的地理区域内协助搜救行动。在更大的搜索计划中，需要系统搜索的地区需要进行标记。由于期望 UAV 在恒定高度飞行，因此环境被表示为二维平面。这将在3.4节中进一步讨论。
在标记的边界内部的区域被称为搜索的环境（E）。在 UAV 执行系统搜索之前，应该对此环境进行完全映射。图3.1显示了一个已被标记为搜索环境的地图示例。
该环境可以看作是在某些坐标边界内的一组连续点。应注意，该地图中的任何点都应该可以通过 UAV 从地图中的任何其他点到达，不包括有障碍物的点。不应该有任何封闭区域。第五章将详细讨论如何使用数字高程模型（DEM）等工具，来对此环境进行模拟。
本环境中包含了无人机和障碍物。幸存者可能位于搜索区域之外，但是这不会彻底改变实现方式。在没有找到较大搜索目标的情况下，无人机将完成它们的搜索任务。
3.3 环境障碍
假定环境是静态的，而动态障碍物不会被显式地建模出来。在高空中，动态障碍物的出现是不太可能的。在管理的飞行空域中，飞行计划和其他飞行器的避碰措施意味着无人机通常不需要避开其他飞行器。将环境假定为静态环境并在搜索之前完全进行地图映射是这种实现方式的局限性，但是在更高的高度上，这被认为是合理的。
假定短期的在线避碰系统与Meiring等人开发的系统类似，内置于无人机中。该系统将帮助无人机避免与动态障碍物（例如鸟类）等可能存在于环境中的障碍物碰撞。本机械臂的碰撞避免技术旨在尽可能紧密地遵循原始路径，从而不对无人机的整体飞行时间和能耗产生明显影响。
由于不同类型的障碍物往往是环境特定的，因此在第3.2节中对它们进行了讨论。障碍物可能包括人造结构、自然障碍和禁飞区。这些禁飞区可能是由于恶劣的天气、难以进入的地形或限制的空域而引起的。禁飞区也可能仅仅是已经被搜索过的区域。搜索团队也可能排除他们确定幸存者未占用的区域，或已经使用其他策略进行搜索的区域。