Communication-Restricted Exploration for Robot Teams
Communication-Restricted Exploration for Robot Teams
复制标题
机器人团队的通信受限探索
DOI：
--
复制
发表时间：
2014
期刊：
影响因子：
--
通讯作者：
Maria L. Gini
中科院分区：
文献类型：
--
作者：
Elizabeth A. Jensen;Ernesto Nunes;Maria L. Gini
在发生地震或火灾的情况下，搜救工作可能会推迟，直到人类救援队安全进入该地区。一个机器人团队可以提前进入，为人类团队提供地图、图像和感兴趣的位置，让他们在可以进入时做好准备。在灾区，由于基础设施瘫痪或环境干扰，通信可能受到限制。我们提出了一种利用少量机器人的算法，这些机器人在通信允许的范围内传播，但在探索未知环境时，它们会呆在一起。我们表明，该算法将允许机器人团队充分探索环境并保持通信，以便将信息返回给等待的搜救团队。我们还表明，这可以通过多种通信方法来实现。在发生火灾或地震的情况下，出于安全考虑，救援队并不总是能够立即进入一个地区。为了帮助加快救援进程，许多人考虑使用机器人提前探测环境，这样就可以绘制出感兴趣的点，比如墙壁上的薄弱环节或幸存者的位置，并将其传回给救援队。这种方法使救援队能够更精确地规划救援工作并确定任务的优先级。然而，这种方法需要保证机器人到达环境的每一个部分。机器人团队探索未知环境有多种方法。盖奇（Gage 1992）提出了三种类型的保险。在地毯式覆盖中，机器人可以同时覆盖整个环境。在障碍物覆盖范围内，机器人在一个区域周围设置一个边界，这样任何东西都不能在不被至少一个机器人看到的情况下进出该区域。在扫描覆盖范围内，机器人在环境中进行一次穿越，并确保至少有一个机器人看到每个点，但不会停留在任何一个位置，而是在环境中逐步移动。Choset （Choset 2001）后来根据这些类别提出了覆盖路径规划算法的广泛概述。大多数覆盖算法的目标是实现地毯式覆盖或屏障式覆盖。然而，毯子和barr版权所有c©2014，人工智能促进协会（www.aaai.org）。版权所有。河流覆盖需要足够的机器人来提供全面覆盖，而这个数字可能会大得令人望而却步。相比之下，当团队中的所有其他机器人都失败时，可以用一个小团队完成扫描覆盖，如果必要的话，可以减少到一个机器人。由于环境是未知的，覆盖地面所需的机器人数量也是未知的，即使知道，也可能远远超过现场可用的机器人数量。因此，在我们的方法中，我们使用了一种探索算法，在这种算法中，机器人团队完成了对环境的一次扫描，以定位感兴趣的点，这些点可以传递给搜索和救援团队。我们的主要贡献是一种全新的算法，它是完全分布式的，可以提供对未知环境的完全覆盖，同时还能保持机器人之间的通信，即使对通信类型、范围和质量有严格的限制。该算法的主要创新之处在于它使用了最小数量的消息，无论是在大小还是类型上，这使得使用广泛的通信方法来适应环境的限制成为可能。我们提供的仿真结果和深入分析表明，无论机器人数量多少，该算法都可以保证充分的探索，并且机器人之间保持通信。
In the event of an earthquake or fire, search and rescue efforts may be delayed until it is safe for the human rescue team to enter the area. A team of robots could enter in advance to provide maps, images and locations of interest to the human team, allowing them to prepare their approach when they can enter. In a disaster area, communication may be limited, either due to infrastructure being down, or because of environmental interference. We propose an algorithm that makes use of a small number of robots, which spread as far as their communication allows, but which otherwise stay together while they explore the unknown environment. We show that the algorithm will allow the team of robots to fully explore the environment and maintain communication in order to return the information to the waiting search and rescue team. We also show that this can be achieved with multiple methods of communication. In the event of a fire or earthquake, it is not always possible for a rescue team to enter an area immediately, due to safety concerns. To help speed the rescue process, many have looked into using robots to explore the environment in advance, so that points of interest, such as weak spots in a wall or the location of survivors can be mapped out and relayed back to the rescue team. This approach allows the rescue team to plan their rescue efforts more precisely and prioritize tasks. However, such an approach requires to guarantee that the robots reach every part of the environment. There are multiple methods for a team of robots to explore an unknown environment. Gage (Gage 1992) proposed three types of coverage. In blanket coverage, the robots cover the entire environment simultaneously. In barrier coverage, the robots set up a perimeter around an area such that nothing can pass into or out of that area without being seen by at least one robot. In sweep coverage, the robots make a pass over the environment and ensure every point has been seen by at least one robot, but don’t stay in any one location, instead moving progressively through the environment. Choset (Choset 2001) later presented an extensive overview of coverage path planning algorithms according to those categories. Most coverage algorithms aim to achieve either blanket or barrier coverage. However, both blanket and barCopyright c © 2014, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. rier coverage require enough robots to provide the full coverage, and that number can be prohibitively large. In contrast, sweep coverage can be done with a small team, down to a single robot, if necessary, when all other robots on the team have failed. Since the environment is unknown, the required number of robots for blanket coverage is also unknown, and, even if known, may well exceed the number of robots available on site. Thus, in our approach, we use an exploration algorithm, in which the team of robots completes a single sweep of the environment to locate points of interest that can be relayed to the search and rescue team. Our main contribution is a novel algorithm that is fully distributed and which provides full coverage of an unknown environment, while also maintaining communication amongst the robots, even with severe restrictions on the communication type, range, and quality. The primary innovation of this algorithm is that it uses the minimum number of messages, both in size and number of types, making it possible to use a wide range of communication methods to accommodate restrictions from the environment. We provide simulation results and in-depth analysis to show that the algorithm can guarantee full exploration regardless of the number of robots, and that the robots maintain communication.