部分已知环境下的覆盖规划方法文献综述

文 献 综 述

研究背景：随着智能服务型机器人的迅速发展，移动机器人的全覆盖路径规划技术的研究越来越受到研究者的青睐，全覆盖路径规划是指机器人以尽可能低的重复率遍历环境中的全部无障碍地区，在清洁智能机器人、草坪修剪机器人、矿藏探测机器人以及扫雷机器人、和救援机器人方面，还有在军事、核电站、宇宙探索和海洋开发方面有着很大的应用。

在国外的很多对于这方面的文献贡献，对于全面覆盖算法，Middlebury和Strecha等人提出了多视图立体基准评估在推动多视角立体视觉（MVS）方法，但由于数据集的规模和可变性小，限制了范围，所以^[1]中提出了一个新的，多样的数据集，包括80个场景，从49或64个准确的相机位置，且从Middlebury评估中扩展了评估协议，但MVS的两个最紧迫的问题是缺乏纹理和网格;在^[3]中提出了一种新的结构检测快速迭代算法。 新算法采用了交替的两步优化范式，以找到良好的观点，共同提供全面覆盖，并导致低成本的连接路径。 在每一次迭代中，选择每个观点以减少其本身与其邻居之间的成本（第一步），随后重新计算最佳连接旅程（第二步），同时总体上遵守车辆约束和传感器限制阶段。该种算法在AGP中进行取样，使得连接路径较短，同时确保全覆盖。这种新颖的方法优点是会导致全覆盖路径，成本低，计算速度快；还有一个是提出了一个新的路径规划框架，^[2]中通过采用迭代策略来改善从重新网格技术中受益的检查路径，同时第一个完整的解决方案计算速度非常快，从而提供三维结构的统一覆盖率。所得到的路径从直接依赖于结构的局部几何复杂度的距离检查结构的每个细节，并相应地选择观点。 对于每个可接受的视点集合，解决旅行推销员问题，并导致算法在每次迭代中输出的检查路线，该算法可以迭代地加载改进的更高保真度的网格模型，而不是完全重新计算路径（作为基本的UC3D-IPP），而是通过增加一组新的观点来修改现有的观点，这将导致几乎相同的统一覆盖基于更新的网格模型，但是该算法也存在着缺点，就是飞行器在检查查找路径的时候，为了避免的碰撞，需要在UC3D-IPP中进行大量的计算，会花费相当大的时间；在文献^[4]中，提出了一种新的利用空中机器人平台对未知空间进行自主探测的路径规划算法。 拟议规划者采用后退视界“次最佳视图”方案：在在线计算随机树中，找到最佳分支，其质量取决于可探索的未映射空间的数量。 只有这个分支的第一个边缘是在每个规划步骤中执行的，而重复这个过程会导致完整的勘探结果，该方案有利探索和解决复杂环境，机器人具有较高的自主性，有利减少危险环境中人的接触程度；基于信息理论的规划的方法也可以来实现移动机器人自主的构建密集的3D地图，^[5]实现的原理主要是通过CauchySchwarz二次互信息（CSQMI）的信息论目标函数来实现，来指导机器人在地图的不确定区域获得测量结果，在该文献的这个方案中，它的优势所在是将探索环境的时间缩短了70%，最接近的前沿探索战略的时间减少了57%，在实践中具有较好的效果；与^[5]使用方法差不多是一样的文献^[6]中，但是用了柯西 - 施瓦茨二次相互信息（CSQMI），且有创新之处是，该算法是通过搜素一组路径，不会造成局部最小，收敛性也会比较好，再有的是这种有效的控制政策主动感知，纳入显式模型的感知和流动性与地面和空中机器人建立3D地图的方法，充分考虑了传感和移动模型，不仅适用于地面，而且飞行器也可以使用；在于机器人检查与覆盖路径的问题中，^[7]中给出了利用了无向图的和有向图的定向问题的思想，来解决最优化的路径问题；关于定向问题的具体优化算法，可以通过^[8]中给出的利用递归的贪心算法，可以解决旅行推销员问题的约束是严格的和旅行推销员结合了调度和网络设计方面且为它们提供的算法工具并没有强烈的重叠的问题，通过来对一个弧加权有向图操作，使其实现最大化访问节点的数量，跟全面覆盖问题是一样的道理；在文献^[9]中我们可以了解到，积极视觉的发展，以及主动感知与传感器问题的新概念，介绍了主动视觉方法的任务、问题和应用，主动视觉在机器人感知中扮演着重要的角色，有目标感知，对象和站点建模，机器人定位和映射，导航，路径规划，探索，监视，跟踪，搜索，识别，检查，机器人操纵装配和拆卸等应用，而且可以解决3D传感器视野有限、只能从单一视角看到一部分场景和对象的全局描述常常由于遮挡而不能从一个视点重建；为了能够最大限度的收集到信息，^[10]提出了一种通过模仿来收集信息的算法，探索，训练目标分布政策模仿透视甲骨文，因为甲骨文有全面的的信息关于世界和计算非近视的解决方案，并且该算法的优点是对于一系列2D和3D探索问题，EXPLORE能够适应不同的目标分布，对信息收集领域大有益处；关于覆盖、优化和解决检查路径问题的算法，在^[11]一书中都有关于这方面的介绍；为了帮助用户实现4D域的良好覆盖，尽管手持采集的挑战，^[12]提出了一个使用手持商品相机交互式获取和渲染光场的系统，在该文献中，通过限制视角之间的重投影误差来定义覆盖范围，这涉及到光场的所有四个维度，并进一步提出了一种新的渲染算法，是针对捕获的非结构化而密集的数据量身定制的，优点是可以实现分段双三次重建，使用捕获的视点的三角剖分和适用于重建权重的细分规则；同时，凸优化问题在信号和图像处理方面有很多的应用，但是在应用程序中使用凸优化需要开发自定义求解器或将问题转换为标准形式，耗时且容易出错，在^[13]中，提出了一种新的凸面优化DSL：CVXPY，基于CVX（Grant和Boyd，2014），但引入了新的特征，如签名的规则凸规划分析和参数。 CVXPY是一个普通的Python库，它可以很容易地将凸优化与Python的高级功能（如并行性和面向对象的设计）相结合，对于曲线优化具有较好的效果；当面临着视图选择、为多视图立体过程部署最有利的视图，以实现尽可能高的准确性和最少的视图数量的问题时，在^[14,15]中做了主动三维模型的改进算法，该算法被认为是系统地增加估计的三维模型的精度和完整性的顺序过程，提出了下一个最佳视图问题（NBV），该规划方法使用自适应平面斑块作为结构表示的基本元素和这些斑块的协方差矩阵作为三维重建不确定性的表示。我们将这些元素与对象的纹理属性结合起来，提出了一种新的视点选择标准，以求在几何不确定性的降低和可靠图像测量的实现之间取得平衡，能够有效地从图像中构建高度精确的3D模型；为了并行解决视点选择和路径规划问题的移动机器人平台用于视觉三维重建;最新一些的方法是基于双启发式优化算法^[16]，该算法通过分层划区的方法，对全局路径先进行粗划分，划分为均等大小的网格，障碍物也在其中，在对网格内进行细化分，在粗划分上面使用蚁群算法，先实现大网格的优化路径，然后在细化分中使用TS算法来实现局部最优化，最终实现全局覆盖路径规划，该算法的优点是可以大大提高机器人运行速度。

参考文献：

[1] H. Aanaelig;s, R. R. Jensen, G. Vogiatzis, E. Tola, and A. B.Dahl. Large-scale data for multiple-view stereopsis. IJCV,120(2), 2016.

[2] K. Alexis, C. Papachristos, R. Siegwart, and A. Tzes. Uniform coverage structural inspection path-planning for micro aerial vehicles. In IEEE International Symposium on Intelligent Control 2015.

[3] A. Bircher, K. Alexis, M. Burri, P. Oettershagen, S. Omari, T. Mantel, and R. Siegwart. Structural inspection path planning via iterative viewpoint resampling with application to
aerial robotics. In International Conference on Robotics and Automation (ICRA) 2015.

[4] A. Bircher, M. Kamel, K. Alexis, H. Oleynikova, and R. Siegwart. Receding horizon “next-best-view” planner for 3D exploration. In International Conference on Robotics and Automation (ICRA) 2016.

[5] B. Charrow, G. Kahn, S. Patil, S. Liu, K. Goldberg, P. Abbeel, N. Michael, and V. Kumar. Information-theoretic planning with trajectory optimization for dense 3D mapping. In Robotics: Science and Systems (RSS) 2015.

[6] B. Charrow, S. Liu, V. Kumar, and N. Michael. Informationtheoretic mapping using Cauchy-Schwarz quadratic mutual information. In International Conference on Robotics and Automation (ICRA) 2015.