Graph Planning for Environmental Coverage
Graph Planning for Environmental Coverage
复制标题
环境覆盖图规划
DOI：
10.1184/r1/6718364.v1
复制
发表时间：
2011
期刊：
影响因子：
--
通讯作者：
Ling Xu
中科院分区：
文献类型：
--
作者：
Ling Xu
诸如街道地图绘制和安全监视之类的任务寻求穿过给定空间以执行功能的路线。这些任务功能可能涉及映射空间以进行精确建模，感测空间以进行异常活动，或搜索空间以寻找对象。当这些任务由机器人自主执行时，必须考虑环境的约束，以生成更多的可行路径。此外，在真实的世界中执行这些任务提出了在动态变化的环境中操作的挑战。
本文研究了在环境约束和先验地图信息不完全的情况下图的有效覆盖问题。关于环境的先验信息被假定为以图的形式给出。我们寻求一种解决方案，有效地覆盖了图形，同时考虑到空间限制和在线更改。对于实时应用程序，我们寻求一个完整但有效的解决方案，具有快速重新规划能力。
在这项工作中，我们将覆盖问题建模为弧路由问题。虽然这些路由问题一般是NP-难的，我们的方法的目标是通过使用低复杂度的算法在分支定界框架时，时间允许和近似时，时间限制适用的最佳解决方案。此外，我们通过将这些约束嵌入到图中来考虑环境约束。在这篇论文中，我们提出了解决多维路由问题及其子问题的算法，并在计算机生成的和物理道路网络数据上对其进行评估。
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 objects. When these tasks are performed autonomously by robots, the constraints of the environment must be considered in order to generate more feasible paths. Additionally, performing these tasks in the real world presents the challenge of operating in dynamic, changing environments.
This thesis addresses the problem of effective graph coverage with environmental constraints and incomplete prior map information. Prior information about the environment is assumed to be given in the form of a graph. We seek a solution that effectively covers the graph while accounting for space restrictions and online changes. For real-time applications, we seek a complete but efficient solution that has fast replanning capabilities.
For this work, we model the set of coverage problems as arc routing problems. Although these routing problems are generally NP-hard, our approach aims for optimal solutions through the use of low-complexity algorithms in a branch-and-bound framework when time permits and approximations when time restrictions apply. Additionally, we account for environmental constraints by embedding those constraints into the graph. In this thesis, we present algorithms that address the multi-dimensional routing problem and its subproblems and evaluate them on both computer-generated and physical road network data.