多机器人对抗覆盖外文翻译资料

 2022-01-18 10:01

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

多机器人对抗覆盖

摘要：论文的工作探讨了对抗覆盖问题，该问题一个或多个机器人需要完全覆盖给定区域，区域内可能有导致机器人停止工作的威胁。机器人的目标是尽可能快地覆盖目标区域的同时，每一个机器人在停止运行前的覆盖面积也要最大化。这个问题有很多实际应用，例如在像核电站这样危险的地方执行覆盖任务，或者在战场上监视敌军和野战排雷。以前关于该问题的研究是通过单机器人的覆盖来解决的。使用多机器人群体来完成区域覆盖在覆盖时间和鲁棒性上都有非常明显的优势：即使有机器人完全被损毁，其他机器人也能够承担它的覆盖子任务。因此，本文我们主要描述了针对对抗环境的多机器人覆盖算法，使得每个机器人在机器人群体停止工作前能够使覆盖面积最大化。通过分析显示算法具有鲁棒性，即只要有一个机器人能够移动，整片区域就能够被完全覆盖。我们也通过算法设置了理论上的最小覆盖边界和最少覆盖时间。最后，我们通过已有的环境设置集对算法的有效性进行评估。

  1. 简介（引言）

区域覆盖的路径规划问题是机器人领域的一个基础问题。其目标是找到能够让机器人访问目标区域内的每一个部分并且使某些条件最优化的一系列世界坐标，一般是子啊避开障碍物的同时最小化机器人的能耗。这个问题在现实生活有有广泛地应用，例如自动扫地机器人[2]和超市打包机器人[4]，野外排雷[14]或者用无人机进行侦查[7]等。

在对抗覆盖问题最新的版本（例如[20]）中，机器人需要避开障碍物覆盖给定的区域。区域内的每一个点都有一定的概率使机器人在该点停止搜索。机器人的目标是尽快覆盖（包括有危险的点在内的）整片目标区域的同时在完全覆盖前最小化它会被停止工作的概率。这个问题是在一般环境（没有对抗性的存在）下的覆盖问题的一个扩展，一般环境下没有危险存在则唯一的目标是最小化覆盖时间[13],[5],[8]。

之前对抗覆盖问题通过单个机器人解决的。但用多机器人完成对抗覆盖任务的优点也非常明显。使用多机器人会因为任务负载的分散明显减少完成任务的时间，就像我们看到的一般的多机器人覆盖问题[8],[1]。除此之外，使用多机器人会提高鲁棒性，即使群体中有部分机器人出现问题，可以通过群体中的其他机器人来进行补偿。因此，在本文中我们扩展为多机器人系统来解决对抗覆盖问题。我们通过工作区地图（通过离线覆盖得到该地图[6]）来判断他们的覆盖率。

首先，我们正式定义对抗覆盖中的多机器人版本和如何通过多机器人系统找到最安全的覆盖路径的问题。在这篇文章中，我们主要关注机器人群的生存能力，而不是区域覆盖的时间。不过，我们提出的算法在不损害机器人群的存活能力的同时，尽量使覆盖时间最小化。显然，在覆盖时间和机器人群的存活能力之间存在一个折衷：若要最小化机器人在沿着覆盖路径过程中的危险则意味着要执行一些冗余的步骤，这样反回来会因为他们的覆盖路径更长导致他们遇到的危险和覆盖时间的增加。

其次，我们描述的高效的分布式多机器人对抗覆盖算法，最大化机器人群的存活能力的同时也要使覆盖时间最优化。算法基于将目标区域分解为包含安全位点和危险位点的连续区域，并且覆盖安全区域的优先级比覆盖危险区域的优先级要高。由于我们使用多机器人来覆盖给定区域，我们使用地图分割的技术来加速覆盖过程。我们通过算法提供一个理论上的覆盖率期望门限值，并且分析算法在最好情形和最坏情形下的完成次数。

最后，我们通过一系列现有的实验集来评估我们的方法。实验结果表示，添加更多的机器人来完成区域覆盖能很好地增加区域的覆盖率和减少区域覆盖的时间。

  1. 相关工作

单机器人和多机器人的覆盖问题在机器人文献中一直被广泛讨论（可参见Galceran和Carreras最近的一个调查[6]）.大多是多机器人覆盖方法是通过某种策略划分覆盖区域来讲单机器人的方法扩展至多机器人的方法。Hazon和Kaminka[8]基于多机器人生成树（MSTC，Multi Robot Spanning Tree Coverage）算法提出了一种STC方法。他们的解决办法，不仅减少了总覆盖时间，还实现了鲁棒性，即只要有一个机器人仍在工作，就能保证给定区域被覆盖。他们也说明了多机器人的冗余对提高覆盖效率的重要性。Agmon等人[1]提出了一种生成树建设算法，能得到就距离而言的有效路径，该算法能够作为MSTC算法的基础。

Rekleitis等人[16]针对未知环境并将环境划分为精确的网格，基于移动机器人群体，提出一系列区域覆盖路径规划算法。仅能在视线范围内通信的情况下，为实现区域覆盖，机器人需要扮演两个角色：一部分机器人被称为探索者，覆盖当前目标网格的边界；另一部分机器人被称为覆盖者，仅通过前进和后退的动作覆盖该网格的剩余部分。对于如何将任务或者网格的分配给机器人群体，则使用贪婪竞争机制。

文献中提到的其他多机器人区域覆盖方法还有从自然中生物行为受到启发得到的算法。例如，Luo 和 Yang [12]提出一种受到神经网络启发的方法应用到多机器人场景的区域覆盖任务，该场景下即使障碍物在移动，机器人也可以相互看到对方。Wagner和Bruckstein [17]研究用机器人群体完成打扫房间的问题，提出一种具有鲁棒性的算法来完成区域完全覆盖。在这些例子中，机器人群体能力受限并且仅能通过信息素进行交流。

关于离线的单机器人对抗覆盖问题在文献[21]中已被正式定义，在文献中我们提出一种简单的启发式覆盖路径生成算法，其目标是最小化机器人生存能力和覆盖路径长度的总代价。该启发式算法仅适用于无障碍物区域，且不具有鲁棒性。在后一篇文献[22]中，我们对该问题进行了更具体地讨论，即找到最安全的覆盖路径。这里我们提出两种启发式算法:STAC，一种基于扩展树的覆盖算法，以及GAC，基于贪心方法。我们得到结果表明：虽然STAC倾向于获得比预期更高的覆盖率，但GAC产生的覆盖路径更短，累积风险更低。在文献[18]中，我们基于对抗环境建立了一个更加复杂的模型，在这个模型中，我们可以选择威胁点的最佳位置，使得该位置停止机器人完成覆盖任务的概率最大化。最后，在文献[19]中我们给出了该问题的在线单机器人版本的解决方案。

当遇到与巡逻相关的问题([15]，[3])时，一个多机器人群体需要在一个有敌人试图进入的封闭区域内巡逻。巡逻问题与覆盖问题相似，都要求机器人或机器人群体访问给定区域内的所有点。然而，覆盖是希望最小化每个点的访问次数(理想情况下，只访问一次)，但是巡逻问题却试图最大化访问次数(同时仍然定位所有点)。

  1. 问题描述

一个机器人群体内有k个机器人，表示为R = {R1，hellip;，R k}，它们需要覆盖给定的区域。该区域包含可能让机器人停止工作的威胁，例如障碍物。与机器人无法通过的障碍物相比，存在危险的地方是机器人必须访问但可能会被迫停止工作的地方。机器人群体事先会被给定一张环境地图。我们假设机器人之间的通信没有任何限制。每个机器人自主覆盖被分配的区域，并且通过与其他机器人通信来跟踪所有被覆盖和未覆盖的空间(通信要求参见4.2节)。

此外，我们假设给定的区域可以分解成n个规则单元的网格。我们用G来表示这个网格。G包含两种类型的单元:自由单元和被障碍物占据的单元。一些自由单元有威胁机器人停止覆盖的因素。每一个自由单元i都有一个威胁概率Pi，Pi表示该单元中的阻止机器人访问它的可能性。我们定义安全单元格为威胁概率为Pi = 0的单元格，而危险单元格为Pi gt; 0的单元格。机器人可以朝四个基本方向(北、南、东、西)移动，并且可以在工作区域内定位到特定的网格单元。

图1显示了一个20times;20大小的世界地图的例子，有8机器人位于左上角的区域。障碍物用黑色的网格单元表示，安全的网格单元用白色表示，危险的网格单元用5种深浅不同的洋红色表示。颜色越深表示该网格单元的Pi值越高(较危险的地区)。

我们假设由于遇到威胁而停止覆盖的机器人不会对其他正常覆盖的机器人产生影响，即其他机器人仍然可以继续覆盖网格单元动，但威胁依旧存在。这种假设在现实场景下的一个实例是，当完成覆盖的机器人多架无人机，并且覆盖区域内的威胁在时间上是恒定的(例如，针对特定位置的反无人机武器)。

存活性可以从两个方面表示:每个机器人的存活性和整个机器人群体的存活性。我们认为，如果一个机器人能够毫发无损地完成它的覆盖任务，则表示它在覆盖范围内存活下来。为了正式定义机器人的存活性，我们首先标记机器人遵循的每一条覆盖路径为Pi =(，，hellip;，)，其中表示机器人i在时间步长j时刻所处的单元格。

机器人R i在覆盖范围内存活的概率为:

公式中表示一个机器人在单元格中因遇到威胁而停止覆盖的概率。

我们定义一个机器人群体在被覆盖区域内存活，要求群体中至少有一个机器人存活到该区域的所有单元格都被访问(即覆盖完成)。

因此，如果覆盖整个区域需要t个时间步长，则由k个机器人组成的机器人群体R = {R1，hellip;，R k}能完全覆盖整个区域的概率是：

根据以上这些定义，我们就可以定义多机器人安全对抗覆盖问题(MRSACP)如下：

定义1：多机器人安全对抗覆盖问题(MRSACP)：给定一个机器人群体包含k个机器人和一个用网格表示的现实空间的一片区域，包含障碍物和有危险的位点，找到一组覆盖路径使得机器人群体的存活性最大化。

MRSACP的NP难度直接来源于单机器人最安全的路径覆盖问题的NP难度[22]。

  1. 多机器人对抗覆盖算法

多机器人对抗覆盖算法(MRAC，算法1中描述)使用一种基于层的方法。它首先用给定的k个机器人尽可能有效地覆盖目标区域内的所有安全单元格。然后再从最不危险的区域覆盖到最危险的区域。这种算法试图在整个机器人群体停覆盖之前使化覆盖率最大化。

在描述算法细节之前，让我们先介绍以下定义：

定义2：一个连续区域是指网格中相同危险等级的单元格的连续子集。

我们还使用安全区域和危险区域来质点仅由安全单元格或仅由危险单元格组成的连续区域。图2为一个网格图的举例说明，其中包含两个安全区域和五个危险区域，它们属于两种不同的威胁级别。两个低威胁级别区域用黄线表示，三个高威胁级别区域用蓝线表示。

此外，我们用p0hellip;，p l (p 0 = 0)表示网格中不同威胁的概率(l是有限的，因为网格中的单元格数量是有限的)，定义威胁级别i为所有让机器人停止覆盖的概率为pi的单元格的组。

多机器人覆盖算法的主要步骤如下：

  1. 将目标区域根据危险级别划分为不同的层，例如：第i层包含的所有危险级别为i的单元格。
  2. 针对每个危险层i，用，，hellip;，表示属于第i层的连续区域。
  3. 每个机器人都被分配一块安全区域A{，hellip;，}，他们都有从当前位置覆盖安全区域的最安全的路径。分配给多个机器人的区域在分配给它们的机器人之间进行分割。
  4. 对于每一块区域的覆盖，我们使用改进的GAC(贪婪对抗覆盖)，最先进的单机器人对抗覆盖问题的解决方案[20]。
  5. 当机器人R i完成当前的覆盖任务时，它将从尚未完成的最安全级别中被分配一个未覆盖的区域。如果存在多个这样的区域，则选择从机器人当前位置出发风险路径最小的区域。如果所有区域都已分配，则将机器人添加到另一个机器人已经覆盖的区域。该区域将被分为两个部分，每个机器人被分配到从当前位置开始覆盖存在最安全路径的子区域。
  6. 如果一个机器人在完成被分配的覆盖任务的过程中遭遇危险，则该区域将被放到未覆盖区域池中。
  7. 如果所有机器人都扫描完了他们需要覆盖的区域，即不存在未覆盖单元格，则称机器人群体完成了该区域的覆盖任务

该算法由两个主要阶段组成:第一阶段(步骤1 - 3)在覆盖之前执行，计算机器人的初始区域分配。这个计算可以由其中一个机器人离线或在线执行，并且它的结果可以传输给群体中的所有其他机器人。第二阶段(步骤4-7)在覆盖过程中由每个机器人以分布式方式独立执行任务。

    1. 多级地图划分

算法中有几个地方需要使用图划分的方法，以便将给定的区域划分给多个机器人。更具体地说，我们需要在给机器人分配区域的初始阶段应用图划分，在覆盖结束时所有的区域都已经分配好，并且有一些空闲的机器人可以帮助其他机器人完成覆盖任务。

将一个图分割成k个大小相等的部分是著名的NP难题[10]。因此，实际的解决方案是基于启发式的。这里我们使用一个多级图划分算法[9]，它由三个主要阶段组成：粗化、划分和细化(图3)。然后在划分阶段对得到的粗略图进行划分。最后，在细化阶段，对划分进行细化，恢复原始图。

    1. 数据结构

该算法包含一个连续区域的列表，用A来表示。每个区域被包含在下列步骤中的一个：

  1. Sunassigned 表示该区域未被分配给任何机器人
  2. Sassigned 表示该区域被分配给一个机器人，但该机器人未覆盖区域
  3. Scovered 表示该区域

    全文共11786字，剩余内容已隐藏，支付完成后下载完整资料

    资料编号：[970]

原文和译文剩余内容已隐藏，您需要先支付 30元 才能查看原文和译文全部内容！立即支付

以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。

您可能感兴趣的文章