英语原文共 4 页，剩余内容已隐藏，支付完成后下载完整资料

任意数量的无人机完成覆盖路径规划

Dimitris Dedousis Vana Kalogeraki

Department of Informatics Department of Informatics

Athens University of Economics and Business Athens University of Economics and Business

dedousis@aueb.gr vana@aueb.gr

摘要

本文研究了城市环境下一套无人飞行器(uav)的完整路径覆盖规划问题。我们打算覆盖的地理区域表示为无孔的单元格网格，网格中每个单元的中心代表一个节点。因此，我们要解决的问题是:给定一个由一组无人机开发的地理区域，如何规划一条路径，确保在给定区域内的所有节点都被覆盖，同时最小化无人机的行驶距离。我们提出了一种算法来确定完整的覆盖路径，这为探索开辟了一条路径，即路径中的每一个节点都将被精确地访问一次，同时最小化无人机的总距离。我们举例说明，我们的方法也可以应用于多个无人机的情况下，可以同飞越该区域，从而减少勘探时间。

CCS概念

• 数学计算 图论法；
• 计算方法 运动路径轨迹；
• 计算机系统结构 机器人学；自主机器人

关键词

AR.Drone;完全覆盖;路径规划算法;自主导航

1.介绍

近年来，无人飞行器(UAVs)具有显著提高生活质量和提高人类在各种城市环境中表现的潜力，包括农业监测、救援行动、运输系统、边境监视等。因为他们引入了一种新的方法来完成任务，这些任务既不涉及人类的参与，也不具有最低的成本。例如，在农业领域，空中图像是无人机快速、特别地监测农场的主要工具。使用无人机，农民可以检查他们的农田，并确定在较短的时间内采取的行动，而使用传统的(通常是手动的)方式。无人驾驶飞行器装备了传感器，可以收集植物的各种信息，并告知农民他们公司的情况。

无人机的另一个重要用途是在拯救人类生命的救援任务中，这可能取决于及时的反应。在这些情况下，响应团队应该能够以一种快速和依赖的方式收集和分析数据，以便快速地了解情况，评估损失，识别需要的人，协调救援任务。这种类型的视图通常只能从天空中看到。UAVs被证明是解决这个问题的特别方案，因为它们是快速的，敏捷的并且可以到达不友好的环境[10]。在幸存者被发现的情况下，无人机可以通过直接通信链路或通过建立一个空中网络，在无人机之间相互通信，并向空间站报告，从而有助于向空间站报告。在室内城市环境中也可以找到其他的例子。例如，在对植物的监视中，随着时间的推移，或在超市里防止商店扒窃。对于各种任务来说，时间的最小化是至关重要的，它可以通过使用无人机完成。

使用无人机的主要目的是覆盖某一区域并向控制它的用户或官员报告。因此，在这些设置中，一个重要的问题是如何在减少勘探时间的同时，将该区域内所有的点都覆盖好，这是一个被称为完整路径覆盖规划问题的问题。这个问题是最重要的，特别是在搜救任务中，需要实时扫描勘探区域。这可以通过使用多个无人机进行探测来实现。然后，用户可以根据接收到的报告和使用无人机的领域采取适当的行动。可能出现的主要缺点是需要人工干预来控制无人机，这可能导致过程中的错误，而自治的方法可以消除这些错误。

在文献中提出了解决完全覆盖路径规划问题的现有工作，其目标是尽量减少旅行的总距离，减少探索的时间。在[7]和[11]中，作者提出了一个完整的覆盖路径规划的解决方案。尽管两种方法提出的技术保证了该区域的全面覆盖。在许多情况下，重访可能导致长途旅行。也有一些工作在道路上，但没有目标实现全面覆盖。还有一种比较已知的算法，比如Dijkstra算法，Bellman-Ford算法，a *等，用于uav[8]。所有这些算法都可以保证最短路径的发现，但是他们不能找到一个完整探索区域的路径。

本文提出了一种完全覆盖路径规划的算法，该算法的目标是覆盖指定地理区域的所有点，同时最小化移动的总距离。我们从两个角度来研究这个问题:首先，我们假设只有一架无人机覆盖该区域。然后，我们将该算法扩展到多个无人机可以使用的情况下，这样我们就可以减少在同一地理区域的探索时间。我们提出实验结果以说明我们的方法的工作原理和方法。

1. 相关工作

在文献中研究了覆盖问题。两个已知的问题是旅行商问题(TSP)和中国邮差问题(CPP)。这两个问题都是指对某一地区的全面覆盖。旅行商的问题已经被证明是NP完全问题，并且已经引入了一些近似算法来解决诸如[4]这样的问题。在中国邮差问题(CPP)中，Ioannis Rekletis等人[11]提出了一种算法，用于对给定区域的完全覆盖，该区域使用牛耕式细胞分解将该区域划分为非重叠的细胞，并解决CPP问题，以计算穿过这些细胞的路径。他们的算法保证了对一个区域的全面覆盖，但在很多情况下，它的缺点是会重新访问一些单元格，从而产生一种无人机必须旅行的更长的路径。另一种解决同样问题的方法是爱德华·桑塔玛尔的作品。[7]。他们的算法是基于大踏步的，并设计出一条覆盖给定区域的路径。作者将一大步作为“连续相邻细胞序列”。给定一个起始点，他们的算法在一个方向上找到了最长的步幅，而该步幅的最后一个单元格是新跨步的第一个单元。虽然作者保证会有一个完整的覆盖范围，但仍然存在相同的问题。有些情况下，某些细胞可能会被多次访问，从而导致长途旅行。另一种方法是使用细胞分解。在[2,5,6,1,11]中，他们的算法的关键概念是分解多个子区域中的一个区域，该区域的联合将覆盖目标区域。之后，用简单的动作，如背部和向前，他们覆盖了想要的区域。在我们的方法中，正如我们在我们的实验评估中所显示的那样，我们获得了完全的覆盖，而在大多数情况下，我们没有经历任何的再访问。

1. 路径规划算法

在本文中，我们考虑了一种无人机的使用，比如我们在实验中使用的AR.Drone 2.0，它有两个嵌入式摄像头。一个前置摄像头和一个地面摄像机。它的最大速度是11.11m/s。海拔高度取决于地面摄像机的清晰度和我们所要覆盖的范围。在图1中，我们演示了在我们的实验中使用的无人机。在任何飞行之前，我们都能在照片的宽度和清晰度之间找到最佳的平衡。一旦我们选择了一个被限制的高度，每幅照片的宽度将是相同的。虽然在我们的工作中，我们考虑了一种特定类型的无人机，但所提出的算法可以应用于可以悬停的不同类型的无人机。总飞行时间取决于必须探索的区域的大小。在本文中，我们假设一架无人机能够探测选定区域。

图1 AR.Drone 2.0 Parrot无人机

在本文中，我们假设给定的勘探区域已经被转化为网格的单元格。将一个区域转换成网格，可以使用一个名为AMFIS[9]的工具来处理。我们假设这个网格没有任何漏洞。一个洞可能是一个障碍物，或者是网格中不能覆盖的限制区域。假设一个有洞的区域可能导致无人机进行不可预测的长距离跳跃，因此飞行的总距离可能会更长。

我们在这项工作中的目标是确保所有的细胞都被充分的探索，同时最小化无人机的总距离。该区域的大小可以任意大，面积大小不影响我们的算法的工作，尽管在实验中我们选择与可以被一架无人机完全探测的区域一起工作。注意，每个单元格都由位于单元格中心的节点表示;连接所有节点构成我们希望覆盖的网格图。

实现该算法的灵感来自于一个名为汉密尔顿路径的问题。汉密尔顿路径是在图中找到路径的问题，一次访问图的所有节点。在我们的实验中，我们使用的图形是网格图，我们应用了我们的算法。在这些图形[3]。在图中找到汉密尔顿路径的缺点是这是一个NP完全问题，因此使用近似或启发式解。

在下面我们提出了一种贪婪算法，它的目标是计算一个无人机的路径。假设一个节点表示为位于网格单元，其邻域为，，和。我们表示一个节点可用来访问，如果在整个探测过程中，我们的算法没有访问该节点。在探索之初，我们假设每个节点都可以访问。从节点开始，我们识别下列候选节点如下所示：

1.我们选择未访问的节点位于前一行。

2.如果前面的行没有可用节点，那么我们选择在我们的方向相同的行中未访问的节点，也就是说，如果我们从左向右移动，则选择节点，我们选择；如果这个方向的邻居不存在，那么我们就会改变我们的方向(如果我们从左向右，我们就会改变它，我们从右到左，反之亦然)

3.最后，如果我们不能在前一个或同一行中访问未访问的节点，那么我们将从下一行选择节点;

在决定访问哪个候选节点之后，接下来的函数将检查要访问的候选节点的邻居是否可用。这些步骤如下所示。

1.如果它至少有一个可用的邻居节点，那么它将访问候选节点。

2.如果候选节点有两个相反的邻居节点，或者，，这意味着该节点的访问将创建一个垂直或水平分割.在这种情况下，如果分割是水平的，我们选择在分离的最上面的节点上访问，然后继续。另外，如果分割是垂直的，我们检查左边的节点和拆分的右边的节点，我们选择访问第一个没有创建拆分的节点。

3.如果它有两个非对立的或多于两个相邻节点，那么访问该节点而不产生分裂是安全的。

在我们的算法中，我们表示一个垂直或水平的图形分割，如果它将被访问，它将有两个相反的邻居，它们都必须访问。通过访问其中的一个节点，我们必须重新访问该节点，以到达另一个节点，而这正是我们试图避免的。最后，只有当第一个进程未能找到访问的候选节点时，才使用第三个进程。如果我们当前所在的节点没有邻居节点，并且图形探测还没有完成，这是可能的。在这种情况下，将采取以下步骤。

1.检查对角线相邻节点，即，，，，然后到单个可用的邻居。

2.如果当前节点没有可用的对角邻居节点，则必须执行回溯，直到找到至少一个可用的邻居节点的最后一个节点。如果这样的节点被发现，我们就会给它的邻居新的优先权。首先，如果可用，我们更愿意访问下一行的邻居节点。如果没有可用，我们选择访问前一行的邻居，我们选择剩下的邻居。我们从不同的行中选择邻居节点，因为我们不希望在同一行中经历对旧节点的重新访问。

我们的算法保证会有完整的图像覆盖。证据是矛盾的。假设我们有一个连通的网格图，其中是顶点数，而是边数。所有顶点都连接在一起(也就是说，一个无人机可以从一个节点移动到图中任何一个节点)。如果所涵盖的顶点总数为，则意味着勘探尚未完成。基于我们算法的第三个过程，在回溯搜索过程中必须找到未覆盖的最后一个顶点。如果没有发现这样的顶点，那么探索还没有实现完全覆盖，这与第三步是矛盾的，因为它在连接的网格图中搜索所有的顶点。在图2中，我们演示了由我们的算法生成的给定网格区域的结果路径(在实验评估部分中提供了实验的描述)。

在这个例子中，起点是在图的顶行上的一个节点上，该算法在到达顶点之前，将优先级分配给节点。

图2:我们方法的结果路径，黑圆圈代表跳跃

图3:用我们的方法进行 图4:基于步幅的算法.

的无人机探索.每个UAV 黑圆圈显示出

的起始点显示. 重访和跳跃.

4.多个无人机

现在让我们考虑在多架无人机的情况下的路径规划问题。我们的目标是使用超过一架无人机来减少总勘探时间。让我们用多架无人机来表示这张图的总探测时间，是的探测时间，是被分配给的节点的数量，k是图中节点的总数，n是无人机的总数量。从这一点来看，=。

假设我们有n个UAVs (n gt; 1)，最好的解决方案是，如果我们给每一个无人机分配相同数量的节点，在假定不会有任何跳跃的前提下进行探索。如果我们经历了跳跃，同样的技术也会被使用，因为我们的实验表明即使有跳跃，探索时间也会减少。这样，覆盖整个路径所需的时间将根据可用的无人机数量而减少。我们计算需要分配给每个节点的节点数量为，因此，必须分配给最后一个UAV的节点计算为。

最后一步是对每一种无人机进行起始点。这与算法的执行是并行的。该算法将每一种无人机的起始点按如下方式进行。对于第一架无人机，它计算了必须分配给UAV的节点数，然后为下一个UAV创建一个新的起始点，并像以前一样继续。这样，它保证了每一架无人机在探索时不会与其他无人机重叠。无人机是平行飞行的，所以这张图的入口点对所有人来说都是一样的。我们计算每一架无人机从入口点到指定的起点所需的时间，然后将其添加到探测所需的时间。在图3中，我们演示了每一种无人机的起始点，以及我们的算法所识别的路径。绿线表示从入口点到每一个起点的路径。完整探索图形所需的最大时间是最后一个UAV完成探测分配给它的节点的时间。

表1：我们算法的结果

表2：基于步幅的算法的结果

剩余内容已隐藏，支付完成后下载完整资料

资料编号：[22838]，资料为PDF文档或Word文档，PDF文档可免费转换为Word