An efficient algorithm for environmental coverage with multiple robots
An efficient algorithm for environmental coverage with multiple robots
复制标题
多机器人环境覆盖的高效算法
DOI：
--
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
A. Stentz
中科院分区：
文献类型：
--
作者：
Ling Xu;A. Stentz
诸如街道地图绘制和安全监视之类的任务寻求穿过给定空间以执行功能的路线。这些任务功能可能涉及映射空间以进行精确建模，感测空间以进行异常活动，或搜索空间以寻找对象。在许多情况下，使用多个机器人可以大大提高这些任务的性能。我们假设先前的地图是可用的，但由于遮挡、年龄、动态对象和分辨率限制等因素，它可能不准确。在这项工作中，我们使用k个机器人解决了先验地图信息不完整的环境覆盖的NP难题。为了利用图论中的相关算法，我们将环境表示为图，并将覆盖问题建模为k-农村邮递员问题。使用这种表示，我们提出了一个图覆盖的计划生成方法，可以在线处理图的变化。我们的方法提出了两个改进现有的启发式算法的覆盖问题。我们的改进试图通过最小化最大巡回赛的长度来均衡k条路径的长度。我们评估我们的方法在一组比较测试模拟。
Tasks such as street mapping and security surveillance seek a route that traverses a given space to perform a function. These task functions may involve mapping the space for accurate modeling, sensing the space for unusual activity, or searching the space for an object. In many cases, the use of multiple robots can greatly improve the performance of these tasks. We assume a prior map is available, but it may be inaccurate due to factors such as occlusion, age, dynamic objects, and resolution limitations. In this work, we address the NP-hard problem of environmental coverage with incomplete prior map information using k robots. To utilize related algorithms in graph theory, we represent the environment as a graph and model the coverage problem as a k-Rural Postman Problem. Using this representation, we present a graph coverage approach for plan generation that can handle graph changes online. Our approach proposes two improvements to an existing heuristic algorithm for the coverage problem. Our improvements seek to equalize the length of the k paths by minimizing the length of the maximum tour. We evaluate our approach on a set of comparison tests in simulation.