0 引言

随着同时定位与建图(simultaneous localization and mapping, SLAM)技术的发展^[1-2], 移动机器人环境感知和定位导航能力得到迅速提升, 使得移动机器人自主执行任务成为可能.此外, 旋翼无人机因其具有良好的视野、自主起降能力、悬停能力以及高机动性和敏捷性等优势而被学术界和工业界广泛研究.时至今日, 将旋翼无人机搭载视觉或激光等传感器来自主获取周围环境的数据信息, 已成为环境建模自动化的一种有效手段, 其已成功应用于近景摄影测量^[3-4]、环境动态监测^[5-6]、精准农业^[7-8]、考古保护^[9-10]、灾后救援^[11-13]等领域.

移动机器人环境覆盖和探索规划主要研究如何规划机器人的最优路径, 使其沿该路径运动的同时利用机载传感器进行环境信息收集, 从而得到环境的三维重建模型或地图表达.地面移动机器人因直接与环境接触, 其运动与视野易受障碍物的限制, 而旋翼无人机由于其具有空中悬停能力且视野更好、机动性更强, 常被用于复杂三维场景的覆盖和探索.然而, 旋翼无人机的续航能力与负载能力有限, 因此如何实现高效的环境覆盖和探索成为基于旋翼无人机的环境覆盖和探索规划研究领域的关键科学问题, 同时也是机器人领域的热门研究方向.

对于环境覆盖规划而言, 其主要研究如何确定一条机器人的可行路径, 使得机器人携带传感器沿该路径可以实现一个目标区域的完全访问或覆盖^[14-16].针对环境覆盖规划的研究, 大部分工作聚焦于环境信息已知的覆盖规划问题, 这类研究根据环境的几何信息以及机器人传感器模型, 对机器人覆盖路径进行规划, 从而达到最优的环境覆盖效果.一个典型的环境覆盖路径规划框架主要包括兴趣区域分解、覆盖路径点生成、覆盖路径规划以及覆盖路径执行4个部分, 如图 1(a)所示.其中, 兴趣区域分解是指针对复杂的目标环境, 由于存在障碍物阻塞和区域间连通性问题^[17], 需要将兴趣区域中的自由空间(即机器人可通行的无障碍区域)分解为一个个小的单元, 然后对这些小的单元依次访问即可实现整个兴趣区域的全覆盖.常见的区域分解算法有梯形分解法^[18]、牛耕式分解法^[19]以及基于Morse函数的分解方法^[20].覆盖路径点生成则是综合考虑传感器模型、机器人模型及环境模型计算出能够实现兴趣区域全覆盖的机器人传感器位姿, 与此同时, 覆盖路径点需要满足传感器感知约束以及机器人运动学与动力学约束等^[21-23].最后, 规划出机器人能够遍历所有覆盖路径点的最优路径并执行, 从而完成环境覆盖任务.

对于环境探索规划而言, 其主要研究如何在环境信息未知的前提下, 根据机器人当前累计获得的传感器数据规划出机器人下一步移动目标, 从而实现整个目标区域的地图构建或环境建模^[24-25].机器人环境探索规划的研究内容与计算机视觉或计算机图形学领域内的下一最佳视图问题(next-best view problem, NBVP)类似^[26-27], 不同之处在于NBVP主要解决围绕一个固定目标进行传感器信息收集时的传感器观测方位规划问题, 一般假设传感器的规划空间是安全自由的.然而, 机器人环境探索规划需要时刻考虑与环境中障碍物的碰撞避免问题.一个优秀的环境探索策略, 可以在合理的时间内全部完成或近似全部完成整个环境的地图构建.如图 1(b)所示, 典型的机器人环境探索流程主要分4个步骤: 1)确定探索候选目标点; 2)评估候选目标点的效用, 并选出最佳探索目标; 3)规划出从机器人当前位置到最佳探索目标点的无碰撞路径; 4)完成上述规划流程后, 机器人沿该路径到达目标点, 与此同时利用机载传感器收集环境信息并实时更新环境地图.以上流程迭代执行, 直到整个环境被完全探索或所有探索候选目标点的效用均低于某个阈值, 至此认为探索任务完成.

机器人环境覆盖和探索虽然面向的任务场景不尽相同, 但是两者之间有着紧密联系.尽管关于环境覆盖的研究主要集中于环境信息已知的覆盖路径规划这类属于离线规划的策略, 但是也有部分工作致力于研究环境信息未知的覆盖路径规划问题, 即根据机器人传感器信息在线规划覆盖路径^[28-30].由此可见, 在环境信息未知的前提下, 环境覆盖规划问题与环境探索规划问题在某种意义上是等价问题, 二者均根据当前累积的传感器信息规划出机器人下一步移动目标, 从而完成整个环境中可达区域的访问.除此之外, 越来越多的研究者投身于研究同时兼顾环境探索与覆盖的机器人路径规划问题, 并涌现出一系列具有学术研究意义和实际应用价值的研究成果.

机器人环境覆盖与探索规划领域涉及的研究范围甚广, 且不同类型的机器人所对应的研究方法和应用场景具有一定差异, 因此很难在一篇文章中囊括该领域内的所有研究成果.鉴于旋翼无人机环境覆盖与探索规划具有较好的理论与应用价值, 而目前尚未有学者将环境覆盖与探索两个方面的研究进行整体综述, 本文通过研究近年来国内外发表的相关研究文献, 从覆盖规划、探索规划以及同时覆盖与探索规划三方面分别入手, 回顾相关研究发展历程, 分析不同方法的基本工作原理、优势以及局限性, 总结当前研究所面临的问题与挑战, 把握未来的发展趋势.

1 基于旋翼无人机的环境覆盖路径规划

目前, 关于移动机器人覆盖路径规划的研究已经趋于成熟, 近年来涉及移动机器人覆盖路径规划的综述文章也在不断涌现, 研究趋势正从单个机器人覆盖规划^{[15-16, 31]}逐渐转向多机器人协同覆盖规划^[32].此外, 最近有学者专门针对无人机覆盖路径规划研究现状^[33]进行了总结, 但其主要围绕各种单元分解方法展开综述, 因此所关注的覆盖对象基本都是二维平面环境.然而, 实际应用中的待覆盖对象多为结构复杂的三维环境, 仅依靠单元分解并辅之以简单的运动模式(图 2所示为两种常用运动模式: 之字形路径^[34]或螺旋线形路径^[35])往往无法达到预期的覆盖效果.鉴于此, 本节将以二维环境覆盖和三维环境覆盖作为分类标准, 探讨基于旋翼无人机的环境覆盖路径规划研究现状.

1.1 二维环境覆盖路径规划

基于旋翼无人机的二维环境覆盖路径规划研究与地面移动机器人的研究内容基本一致, 主要研究如何将复杂形状的二维环境平面进行分解进而得到最优的覆盖路径.\: 然而, 空中机器人相较于地面移动机器人具有一些平台特性, 如移动速度快、续航能力差、载荷能力弱等, 因此针对不同类型的机器人平台进行覆盖路径规划时算法侧重应略有不同.例如, 对于固定翼无人机而言, 在对其覆盖路径进行规划时需要考虑无人机的非完整性约束, 大多数研究致力于如何有效划分不同形状的兴趣区域并规划出相应的最优覆盖路径^[36-40], 从而减少固定翼无人机完成覆盖所需的转弯次数、路径长度或飞行时间.与之相似, 基于旋翼无人机的二维环境覆盖规划的关注点主要集中于如何优化图像获取质量^{[7, 34, 41-43]}和如何减少能量消耗^{[34-35, 44-47]}.

旋翼无人机的载荷能力有限, 一般通过搭载视觉传感器完成兴趣区域的覆盖.然而, 视觉传感器具有较强的感知约束, 为提高环境视觉覆盖的质量进而得到高精度环境模型, 在进行旋翼无人机覆盖规划时需要考虑获取图像的分辨率问题.文献[7, 34]均提出根据图像获取分辨率需求(即单位面积的成像分辨率)和视觉传感器参数(例如焦距、视角等)来直接确定旋翼无人机完成覆盖时的飞行高度.文献[41]在之字形覆盖路径的基础上, 通过最优化的方式计算旋翼无人机的飞行配置, 即飞行速度、高度、相机快门时间, 进而实现获取图像分辨率最大化.如图 3所示, 除了考虑获取图像的分辨率外, 视觉覆盖的另一个关注点是图像间的重叠率问题, 其对于覆盖任务之后的环境模型重建环节至关重要.文献[41-43]均对航拍图像的重叠率设计进行了深入探究, 其中文献[43]指出覆盖路径的纵向重叠率应该不低于55%, 横向重叠率应该不低于30%.

旋翼无人机在实际应用中面临的最大问题是续航能力差, 因此在研究基于旋翼无人机覆盖规划的过程中自然需要考虑其能量消耗问题.文献[44]根据大量工程实验分析得出旋翼无人机在不同运动状态下的能量消耗模型, 即悬停、匀速运动、加减速运动时的能量消耗情况, 从而得出耗能最小的无人机运动速度和加速度.此后利用文献[44]所提的能量消耗模型分别规划了能量最优的之字形覆盖路径和螺旋线形覆盖路径^[34-35].然而, 该方法的最大问题在于不具备泛化能力, 即针对不同尺寸、重量、形状的旋翼无人机均需要重复实验以确定其能量消耗模型.针对旋翼无人机群组覆盖路径规划问题, 文献[45]采用线性模型近似单个旋翼无人机的能量消耗模型, 在此基础上通过问题分解的方式先将整个待覆盖区域分解并指派给每个旋翼无人机, 再构建min-max车辆路径问题(vehicle routing problem, VRP)为每个无人机规划出一条能量最小的覆盖路径.与上述方法不同, 部分学者认为通过减少覆盖路径的转弯次数或长度可间接节省无人机的能量消耗.文献[46]提出将三维地形投影到二维凸多边形平面上, 针对该凸多边形找到转弯次数最少的扫描方向, 并沿扫描方向规划之字形覆盖路径, 从而达到减少无人机能耗的目的.此外, 文献[47]提出利用VRP求解具有能量约束的无人机最短覆盖路径规划问题, 进而认为旋翼无人机沿该路径进行环境覆盖可实现能量最小化.

1.2 三维环境覆盖路径规划

与二维环境覆盖路径规划类似, 三维环境覆盖路径规划主要关注如何提高旋翼无人机环境覆盖质量(如图像分辨率、覆盖完整度等)和效率(如路径长度、能量消耗等).主要区别在于: 1)三维覆盖规划多利用旋翼无人机覆盖结构复杂的环境, 其需要考虑覆盖对象曲率变化以及自身遮挡等问题对覆盖质量的影响; 2)二维覆盖规划一般假设旋翼无人机在高空飞行以实现兴趣环境的覆盖, 无需关心与障碍物发生碰撞的问题.然而, 三维环境覆盖往往需要旋翼无人机进入到环境内部, 此时如何规划出无碰撞的覆盖路径显得尤为重要.

三维环境往往具有复杂的结构特征, 利用简单的覆盖规划模式难以解决由覆盖对象表面曲率变化等导致的图像质量问题, 因此三维环境覆盖路径规划需要根据覆盖对象的结构特点合理规划覆盖路径点.针对三维地形的覆盖, 文献[48]首先利用已知的地形数字高程模型(digital elevation model, DEM)进行贝塞尔网格曲面拟合, 根据传感器模型(如图 4(a)所示)确定曲面网格大小; 然后以网格中心作为相机的投影中心点, 以恒定的对地距离作为约束生成每个地形网格所对应的无人机空中路径点, 同时根据地形网格模型和无人机能量消耗模型构建了目标三维地形的能量消耗地图; 最后以空中路径点为节点, 以节点间的连通为边构建了加权无向图(此时边的代价为其所需能量的估计值), 并利用遗传算法得到了能量最优的覆盖路径.与之类似, 文献[23]利用准均匀B-样条曲面拟合地形DEM, 根据文献[34]的策略生成二维覆盖路径, 再结合“等距-正视-重叠率”摄影测量约束生成覆盖三维地形所需的无人机空中路径点, 最后通过求解开环起点旅行商问题(travelling salesman problem, TSP)得到了最短覆盖路径.不同于上述三维地形覆盖问题, 针对城市建筑物的覆盖, 文献[49]利用不同的几何体模型作为待覆盖建筑物的近似表达, 将覆盖对象进行分层, 并在每层分别规划无人机的覆盖路径以达到兴趣区域的完全覆盖.类似地, 文献[50]针对高层塔形建筑物进行分层规划, 并在每层利用图 4(b)所示的相机视锥模型进行无人机覆盖路径点规划, 在得到覆盖路径点集合后, 通过求解TSP问题得到覆盖视点的最佳连通顺序(即覆盖路径).文献[51-52]提出一个两步优化范式以获得实现场景全覆盖的旋翼/固定翼无人机路径点及其最优的遍历路径, 与其他算法致力于最小化覆盖路径点数量不同, 覆盖对象三角网格模型中的每个三角网格均生成一个对应的覆盖路径点, 得到覆盖路径点集合, 通过求解TSP问题得到最优的路径点连接顺序.以上规划方法均通过摄影测量约束生成无人机路径点以及对应的覆盖路径.此外, 上述方法大都假设覆盖对象的外形是凸的, 无需考虑覆盖路径碰撞问题.

对于空间受限的三维复杂环境覆盖问题, 无法通过上述简单的规划模式得到可行的覆盖路径, 而基于采样的方法则是一种有效策略^[53].文献[53]通过分析覆盖采样问题, 总结了两种相互对偶的覆盖采样策略: 原始采样(primal sampling)和对偶采样(dual sampling), 如图 5所示.其中, 原始采样策略由机器人构型空间向覆盖对象表面映射, 即在机器人的可行构型空间内随机采样, 从而获得对兴趣目标完成覆盖的机器人路径点; 而对偶采样策略由覆盖对象表面向机器人可行构型空间映射, 生成对兴趣目标点进行覆盖的可行路径点集合, 从该集合中随机采样得到最佳覆盖路径点.从广义上讲, 上述基于覆盖对象分解的方法均属于对偶采样策略的范畴, 其均根据覆盖对象分解和摄影测量约束向机器人可行构型空间映射直接生成覆盖所需的旋翼无人机空中路径点, 然而这类方法在空间受限的三维复杂环境难以实现有效的覆盖路径规划.

原始采样策略具有在空间受限的三维环境内找到可行覆盖路径的能力, 因此广泛应用于三维覆盖规划任务中.文献[54]利用类似NBVP的思想在覆盖对象周围预先通过均匀采样生成一组离散的相机位姿集合, 并对集合中的所有相机位姿计算最优的覆盖朝向, 然后通过构建一个次模定向问题(submodular orienteering problem)获得可以完全覆盖兴趣对象的最小相机位姿集合, 从而得到最优的无人机覆盖路径.针对复杂结构的视觉检测问题, 文献[55]提出了一种自适应采样策略以生成复杂结构三维模型的覆盖路径点.其根据已知的覆盖对象三维网格模型和传感器参数(感知范围、测量误差等), 对三维模型未覆盖部分和覆盖精度低的部分进行不同分辨率的覆盖路径点采样, 然后将覆盖路径点进行聚类并构建成图, 以图搜索的方式找到遍历覆盖路径点的最优路径, 从而避免求解大规模TSP问题.文献[56]提出采用路径基元采样策略实现复杂结构的覆盖, 首先围绕模型已知的目标建筑物进行无人机经过点和路径基元采样, 然后使用一个拓扑图来编码经过点的拓扑信息、路径代价、可见性信息等.最后与文献[55]相似, 采用图搜索的方式解决覆盖路径规划问题.文献[57]将文献[56]中的采样策略扩展到多无人机覆盖路径规划问题中, 并将其构建成集合覆盖问题(set covering problem, SCP)与车辆路径问题相结合的SC-VRP问题, 通过改进的遗传算法实现问题的求解.文献[22]同样提出采用多无人机系统进行大尺度复杂环境的覆盖, 利用如图 4(a)所示的相机模型设计覆盖感知质量估计标准, 用于评估无人机在指定路径点处的感知质量.根据该感知质量评估标准生成可以完全覆盖兴趣区域的无人机空中路径点, 与文献[45]类似, 最后通过求解一个min-max VRP问题得到能量消耗最小的多无人机覆盖路径.

目前, 关于旋翼无人机覆盖路径规划的研究比较多, 其研究趋势正在向着大尺度复杂三维环境发展.但是, 绝大多数机器人覆盖路径规划研究建立在覆盖对象模型已知的前提下, 而实际应用中目标环境的先验信息并不容易得到, 因此有必要研究环境先验信息未知情况下的旋翼无人机覆盖路径规划问题(即旋翼无人机环境探索规划问题).

2 基于旋翼无人机的环境探索路径规划

自20世纪80年代至今, 机器人环境探索的研究已有30余年的历史^[24].从最早基于地面移动机器人平台的环境探索规划研究到近些年兴起的基于旋翼无人机的环境探索规划, 机器人环境探索的应用范围包括简单的室内场景以及复杂的室外场景, 如办公环境^[58]、校园环境^[59]和野外森林^[60]等.虽然关于地面移动机器人平台的研究较为成熟, 且移动机器人具有续航与负载能力方面的优势, 但是地面移动机器人因其直接与环境接触, 其运动受地形变化的影响且视野易受障碍物的遮挡.因此, 采用具有灵活机动能力的旋翼无人机进行复杂环境的探索具有诸多优势.例如: 视野不易受障碍物影响、移动速度快等.然而, 旋翼无人机的续航与负载能力有限, 所以基于旋翼无人机的环境探索规划需要保证所提出算法的最优性与轻量化.基于旋翼无人机的环境探索算法按照探索候选目标点的生成策略可以分为3大类: 1)基于边界检测策略的方法; 2)基于视点采样策略的方法; 3)基于边界检测和视点采样混合策略的环境探索方法.

2.1 基于边界检测策略的环境探索方法

基于边界检测策略的机器人环境探索方法最早由Yamauchi^[24]提出, 该方法利用传感器构建兴趣环境的二维占据网格地图, 通过分辨占据网格地图中已知自由空间和未知空间的边界确定待探索区域, 然后对边界处的网格进行聚类得到边界中心(这些边界中心即为探索候选目标点)并对其进行评估, 选择最优的边界中心点作为探索目标, 从而用于驱动环境探索的进行.基于边界检测策略的机器人环境探索方法一经提出便被广泛采用^[61-65], 然而最原始的基于边界检测策略的机器人环境探索方法具有一定的局限性, 主要表现为以下两个方面: 1)边界检测效率低; 2)候选目标点评估策略缺乏关于目标点处信息增益的考量, 从而导致探索效率低下.因此, 基于边界检测的机器人环境探索方法, 多致力于研究如何提高边界检测效率和优化候选目标评估策略.

高效的边界检测算法可以提高机器人环境探索效率, 做出反应敏捷的探索规划行为.文献[24, 66]提出采用计算机视觉中的边缘检测算法检测二维占据网格地图上的边界, 然后利用聚类算法得到探索候选目标点.图 6为经典边界检测算法示意图.经典方法需要在每个规划周期对整个环境地图进行遍历, 然后对整个地图中的边界进行检测和聚类以得到探索候选目标点.这类方法虽然实现简单, 但运算效率低, 扩展性较差, 尤其是在三维环境探索中无法保证算法的实时性.文献[67]指出, 边界检测速度过慢会导致探索效率低下, 即环境边界发生变化时不能及时进行检测, 机器人仍向先前目标点移动, 尤其是在多机器人协调探索的情况下, 机器人会重复探索已经访问过的区域, 如图 7所示.作为基于边界检测探索方法的核心环节, 边界检测算法的计算效率十分关键^[68-72].为提高边界检测的效率, 文献[67]提出两种被广泛采用的两种边界检测器: 波动前沿边界检测器(wavefront frontier detector, WFD)和快速边界检测器(fast frontier detector, FFD).其中: WFD算法利用两个广度优先搜索(breath first search, BFS)策略将每次边界检测时的地图搜索范围缩小到当前地图中的已知区域, 从而避免对整个地图进行遍历, 然而, 随着探索的进行, 地图中已知区域越来越大, WFD会退化成经典方法; FFD算法不对探索过程中构建的地图进行操作, 直接利用机器人激光传感数据进行边界检测, 从而将每次边界检测的范围缩小至机器人传感器范围内.虽然FFD可以有效减少边界检测的搜索范围, 但是其需要在每次传感器数据到来时刻立即进行边界检测操作, 会造成计算资源浪费.此外, 该算法仅适用于单线激光传感器, 这大大降低了算法的灵活性.尽管WFD和FFD边界检测算法具有一定的局限性, 但其提出的思想具有启发意义, 因此研究者分别针对WFD和FFD进行了改进^[69-74].但是, 这些方法只考虑了二维情况下的边界检测问题, 而基于旋翼无人机的环境探索通常面向结构复杂的三维环境, 需要构建环境三维地图, 最常采用的地图形式为三维占据体积地图, 即volumetric map.例如OctoMap^[75], 其中每个体积单元称作体素, 即voxel.此时, 上述针对二维环境探索的边界检测算法将不再适用.

针对旋翼无人机飞行速度快、相较于地面移动机器人而言所要求的重规划频率较高的问题, 文献[76]提出了一种高效的基于边界检测策略的旋翼无人机环境探索方法.该方法利用无人机携带的RGB-D传感器视野约束, 将每次边界检测的范围限制在无人机正前方的视野范围(field of view, FOV)内, 从而降低边界检测的运算时间.此外, 该方法还有降低待评估的探索候选目标点数量以及减少无人机飞行方向改变次数的优点, 因此可以极大地提高探索效率.与之不同, 文献[77-78]利用三维占据地图的八叉树数据结构进行边界检测的加速, 通过八叉树叶子节点与根节点的连通性提高边界体素的聚类效率, 如果边界体素位于八叉树的同一个分支, 则可以将这些边界体素视为一个簇以避免经典方法中的边界体素聚类操作.文献[60]利用WFD中的BFS思想和轴对齐边界包围盒(axis-aligned bounding box, AABB)的概念缩小地图中边界检测的搜索范围.具体而言, 在探索过程中其为已检测到的每个边界都计算一个对应的三维AABB, 同时将传感器扫描范围的AABB也保存下来; 然后通过AABB碰撞检测提取出可能被传感器扫描过的边界体素, 并判断其是否依然为边界, 如果不是则更新其状态, 其余边界体素由于未被传感器观测到不必进行状态更新; 最后在传感器扫描范围的AABB内利用区域生长算法进行边界体素搜索, 进而有效地将边界检测的范围缩小至传感器扫描范围的AABB内, 实现高效精确的边界检测.此外, 由于该算法是基于地图表达形式的边界检测策略, 不受传感器类型的限制, 算法灵活性较高.

除边界检测速度影响探索的效率外, 探索候选目标点的评估策略对于探索的效率也至关重要.经典的基于边界的机器人探索方法^[24]最早采用一种简单候选目标点评估策略, 即评估候选目标点距离当前机器人位置的欧氏距离代价, 选择距离最短的目标点作为机器人的探索目标.此外, 为了在最短时间内降低地图的不确定性, 也有一些文献[79-81]提出采用距离代价和目标点处期望信息量的综合指标作为候选目标点的评估标准^[25], 即

$ \begin{align} F = \mathop {\arg \min }\limits_{i \in N} (U({f_i}) - \lambda C({f_i})), \end{align} $

(1)

或者采用指数衰减形式^{[25, 52-53]}, 即

$ \begin{align} &F = \mathop {\arg \min }\limits_{i \in N} U({f_i}){{\rm e}^{-\lambda C({f_i})}}, \end{align} $

(2)

$ \begin{align} &F = \mathop {\arg \min }\limits_{i \in N} \dfrac{{U({f_i})}}{{{{\rm e}^{\lambda C({f_i})}}}}. \end{align} $

(3)

其中: $ N $为候选目标点的总数量(即边界个数), $ C({f_i}) $为机器人距离候选目标点的欧氏距离代价, $ U({f_i}) $为候选目标点的期望信息量(即候选目标点处未知体素个数或信息增益大小).虽然这种策略可以在一定程度上提高环境探索的探索效率, 但是, 如图 8所示, 这类算法采用欧氏距离作为机器人运动代价, 容易导致错误的代价估计, 因此在复杂环境中不太适用.与上述评估策略不同, 文献[76]提出一个惩罚运动方向改变的代价项来尽量保持无人机连续飞行, 进而提高探索效率.与文献[76]类似, 文献[60]也引入方向改变代价作为惩罚, 此外还采用A*算法为每个候选目标点规划路径, 计算其真实路径代价, 结合候选目标点处的期望信息量大小选择最终的最优目标点.除采用路径代价作为惩罚项外, 文献[77, 82]提出采用飞行时间作为代价, 即

$ \begin{align} F = \mathop {\arg \min }\limits_{i \in N} \frac{{U({f_i})}}{{T({f_i})}}, \end{align} $

(4)

其中$ T({f_i}) $为从无人机当前位置到达候选目标点的运动时间代价.即: 先规划其从当前位置到达候选目标点的路径, 然后假设无人机以最大线速度和角速度跟踪该路径所需的时间.式(4)中的评估指标相较于(2)和(3)的优势在于其无需调节参数, 在不同环境中均可直接使用.

基于边界检测的机器人环境探索规划策略思路简单, 广泛应用于各类机器人探索任务, 尤其是二维环境的探索.但是, 由于边界检测较为复杂, 导致其在基于旋翼无人机的三维环境探索中的实现效率低下.此外, 基于边界检测的探索方法, 其候选目标点确定与路径规划过程完全解耦, 每次重规划都需要为每个候选目标点规划路径, 计算代价较高.而基于视点采样策略的环境探索方法则是候选目标点生成与路径规划相互耦合的方法, 因此受到广大研究者的青睐.

2.2 基于视点采样策略的环境探索方法

基于视点采样策略的机器人环境探索方法类似于NBVP^[83]的思想, 利用随机采样的方式在环境地图内进行探索视点随机采样, 然后评估这些视点的探索效用, 进而驱动探索的进行.具体而言, 基于视点采样策略的环境探索方法^[84-85]一般利用快速扩展随机树(rapidly-exploring random tree, RRT)算法及其变种算法在环境地图内进行机器人传感器位姿(本文称其为视点, 即viewpoint)采样, 利用RRT本身具有的探索特性^[86]在环境地图内进行采样以获得可以覆盖未知区域的视点.由于利用RRT算法进行视点采样, 每个随机采样点到树的根节点的路径也随之确定, 从而省去了路径规划过程.文献[87]首次提出一种滚动时域NBV规划器用于旋翼无人机环境探索, 利用RRT在三维地图内进行探索视点采样, 该算法以机器人当前位置作为树的根节点, 通过随机采样进行树的扩展, 同时计算采样视点处的信息量, 当采样次数达到预先设定的最大次数$ N $时采样停止, 对RRT中每条分支的探索效用进行评估, 其评估方法如下:

$ \begin{align} F( {{n_k}} ) = F( {{n_{k - 1}}} ) + U( {{n_k}}){{\rm e}^{ - \lambda C( {{n_{k - 1}}, {n_k}})}}, \end{align} $

(5)

将一条分支上所有视点的累积效用作为最终评估指标, 即选择效用最高的分支作为最终的探索路径.为了避免控制与感知误差的影响, 无人机在执行完最佳分支的第一段后, 以该最佳分支的剩余视点为种子节点重新进行上述规划过程.由于整个过程与控制理论中的滚动时域概念相似, 该方法被命名为滚动时域NBV规划器(receding horizon next best view planner, RH-NBVP).实验结果表明, 该方法可以在复杂的环境探索任务中比传统基于边界的探索方法更加高效.由于文献[87]首次将NBV思想引入环境探索任务, 尚有一些考虑不足之处, 如图 9所示: 1)对视点朝向随机采样, 从而导致视点对未知区域的观测效率较低, 且利用光线投射方式评估所有视点朝向效用代价较大, 视点朝向采样密度影响算法运行速度; 2)RH-NBVP沿袭了RRT的单次查询(singlequery)特性, 需要不断重复树的构建过程, 并且难以跳出狭窄空间, 易致探索陷入局部最优, 在大尺度或具有独立子空间的场景探索任务中效率较低.

无人机携带的传感器视场角度有限, 因此在探索过程中对视点朝向进行优化可以提高其环境信息获取量, 进而加速环境探索进程.针对视点信息量评估计算复杂度较高的问题, 文献[88]提出利用降采样的方式减少信息量评估所需查询的体素数量, 从而加速视点评估速度.实验结果表明, 在体素评估数量降低5%的情况下, 仅会造成4%的估计误差, 却可以将评估速度提升20倍以上.在此基础上, 文献[77]针对视点偏航角(yaw)随机采样导致的探索效率低下问题, 设计了一种优化策略: 首先以当前视点为中心, 在其周围进行$ {360^ \circ} $稀疏光线投射, 并计算每条光线上的信息熵大小, 以每条光线为像素构建信息熵地图; 然后在信息熵地图上利用滑动窗口求和算法计算出信息熵最大的窗口(该窗口大小与视点FOV一致); 最后将其对应的偏航角作为该视点最佳朝向, 保证每个视点的观测信息量最大化.与文献[77]类似, 文献[89-90]以每个采样视点为中心建立一个圆柱体区域; 然后以视点为原点在$ {360^ \circ} $范围内每间隔一定角度划分$ N $个楔形切片, 对每个切片计算其期望的信息量; 最后利用滑动窗口求和算法在$ {360^ \circ } $内计算期望信息量最大的窗口作为最佳视点偏航角.理论上楔形切片的角度越小, 后续对视点观测信息量的估计越准确, 但为了权衡计算效率和估计准确性, 间隔角度一般设置较大, 因此该估计方法在实际应用时也会存在估计误差.

基于RRT采样策略的环境探索方法具有与RRT类路径规划算法相似的特点, 即单次查询特性, 该特性会导致这类算法在探索大范围复杂环境时陷入局部最优.为解决这一问题, 文献[89]提出了一种具有历史意识的环境探索规划方法.与传统RRT类算法将无用的树节点和边直接丢弃不同, 其提出保存先前采样的树节点并构建成历史图(history graph), 在无人机探索的过程中(即环境地图更新时)维护更新这些节点的效用, 从而保留了在探索陷入局部最优时可以帮助无人机跳出困境的“种子”.在无人机发现自己邻域内不存在具有探索价值的区域时, 通过搜索历史图可以快速找到具有探索潜力的节点.随着地图的不断扩大, 维护所有的树节点将会消耗巨大的运算资源, 因此文献[89]又通过构建环境欧氏符号距离场(euclidean signed distance field, ESDF)^[91-92]将树节点向障碍物之间的自由区域推移, 进而将位置相近的树节点相互消融, 这与构建环境Voronoi图类似^[93], 既减少了树节点的规模又保存了环境的骨架结构.与之相似, 文献[90]也通过在无人机探索过程中保存RRT历史图完成了大范围复杂环境的高效完整探索.文献[94]为实现旋翼无人机高效探索矿井、洞穴这类具有鲜明特点的环境(即具有多个分支且整体呈长管道型), 提出了一个基于RRT图结构的局部-全局两步规划方法.具体而言, 首先在无人机邻域内进行视点随机采样, 并结合RRT的思想扩展局部RRT图, 以保证无人机在完全探索一个局部区域后再进行下一个区域的探索, 避免了在矿井、洞穴类环境中出现折返和重复探索的现象.而全局RRT图主要负责两个方面: 1)在无人机电量将要耗尽前为无人机提供从当前位置返回出发点的最短路径; 2)当无人机的探索陷入局部最优时, 快速寻找距离无人机当前位置最近的潜在探索区域.上述方法可以在大范围环境或具有多个子空间的复杂环境中实现高效探索, 但均需要在局部探索与全局探索之间进行显式切换, 且每次计算最佳探索目标时均采用贪婪策略, 即局部最优的方式, 没有从全局的角度考虑问题.针对上述问题, 文献[95]基于RRT*算法提出一种高效的信息路径规划方法, 无需显式策略切换且可以保证每次规划结果的全局最优性.

除了采用具有历史记忆的图结构进行高效探索规划外, 也有研究者提出直接采用具有多次查询(multi-query)特性的采样方法^{[81, 96-97]}进行机器人环境探索路径规划.例如, 文献[96]受文献[81]启发, 提出了将概率路线图(probabilistic roadmap, PRM)用于旋翼无人机环境探索路径规划.无人机进行环境探索时通过在其传感器范围内随机采样来实现增量式扩展全局路线图, 进而可以构建出环境的三维拓扑结构, 利用该拓扑地图达到与上述RRT历史图相似的作用, 可以快速地找到具有探索价值的区域.此外, 文献[97]通过局部-全局相结合的采样策略, 增量式构建概率路线图, 对具有动态障碍物的环境实现了高效探索.得益于概率路线图, 其可实现探索目标快速重规划, 进而保证在探索过程中遇到动态障碍物时无人机可以快速找到新的探索目标.

2.3 基于混合策略的环境探索方法

基于边界检测的探索方法对环境的适应性较好, 无论是小场景探索任务还是复杂大场景探索任务均可以保证探索的完整性, 但在探索过程中易产生来回折返的探索路径而导致机器人对某些区域重复探索, 进而影响探索效率.基于采样策略的探索方法通常是在保证机器人临近区域完全探索后再进行下一区域的探索, 不易出现机器人折返现象, 但难以在具有狭窄入口的多子空间环境中实现完整探索.综合考虑两种探索策略的优缺点可以发现其具有一定的互补性, 若将两者相结合则有可能提升机器人环境探索的效率.因此, 有研究者提出将边界检测与视点采样相结合的混合式环境探索策略^[98-99].基于混合策略的环境探索方法大多将探索规划分为两个部分, 即局部规划和全局规划.例如, 文献[100]提出一种基于RRT的边界检测模块, 由一个局部边界检测器和一个全局边界检测器组成.边界的定义为RRT扩展过程中落在边界的节点或者穿过边界的边与边界的交点.局部边界检测器采用一个不断重复重规划的RRT树来检测机器人附近的边界点, 全局边界检测器利用一个在探索中不断扩张的RRT树检测全局的边界点, 从而实现完整的环境探索.与文献[100]的边界定义类似, 文献[101]通过随机采样一对视点的方式检测环境探索的边界, 构建旅行商问题求解每次规划时候选目标的访问顺序.与上述方法不同, 文献[102]提出局部探索规划, 利用基于RRT的视点采样策略优先对单个独立空间完成充分局部探索; 而全局探索规划利用保留的环境地图边界将无人机引导至全局探索目标处, 避免探索过程陷入局部最优而导致探索完整性下降.由上述分析可知, 基于混合策略的探索方法, 其根本目的是利用环境边界的概念将暂时不会被探索的全局候选目标区域记录下来, 待基于采样策略的探索方法陷入局部最优时, 通过访问全局候选目标来引导机器人完成整个环境的探索.从广义上讲, 第2.2节中那些具有历史记忆的探索方法也应纳入混合探索策略的范畴.

3 基于旋翼无人机的环境同时覆盖与探索路径规划

机器人环境覆盖路径规划多为离线规划, 根据覆盖对象的先验信息计算出全局最优的覆盖路径, 从而获得高精度环境模型.机器人环境探索路径规划虽然不需要兴趣目标的任何先验信息, 但是获得的环境模型或地图精度较低, 无法满足某些实际应用需求, 如文物保护、灾后评估、精细化自主操作等.鉴于此, 部分研究者提出将机器人覆盖与探索任务相结合, 同时规划出可以兼顾环境覆盖与探索的机器人路径, 以此实现未知环境的高质量建模.

无人机进行环境探索时如何保证环境建模的完整性是未知环境探索规划所面临的主要难题.文献[103]对文献[87]中的环境探索算法进行了扩展, 将其应用于环境表面模型在线覆盖.所提出算法需要提前建立兴趣环境的三角网格模型, 然后利用RH-NBVP思想实现环境模型表面的在线覆盖路径规划.文献[104]针对未知环境覆盖任务, 设计了旋翼无人机最优覆盖路径在线迭代优化算法.该算法首先利用RH-NBVP的方法找到信息量最大的全局探索目标点$ q_{\rm goal} $以及到达该目标点的全局路径$ \xi_{\rm goal} $, 然后在$ \xi_{\rm goal} $周围进行视点采样完成局部在线覆盖路径规划, 并通过streaming set cover算法迭代优化局部覆盖路径, 实现了在完全覆盖探索边界的同时优化无人机探索路径, 保证了环境模型建模的完整性.文献[105]针对户外环境的完整建模问题提出了一种基于边界检测的三维表面探索算法, 与传统边界检测算法中的边界定义不同, 该算法将环境探索过程中的“表面边界”单元定义为与占据状态的体素和未知状态的体素相邻的自由体素(如图 10所示), 并利用该“表面边界”引导无人机对未知表面进行观测, 从而完成整个兴趣环境的建模.与之类似, 文献[106]同样利用“表面边界”的概念实现环境的同时探索与覆盖, 并且通过主动闭环的形式回到先前访问过的路径点以减小定位累积误差, 从而实现长走廊环境的精确建模.上述方法虽然可以提高无人机环境探索得到的模型完整度, 但是没有显式地考虑由于传感器噪声或模型表达方式等导致的环境模型精度问题, 并且环境模型的完整并不意味着模型的重建精度高.

为了同时保证未知环境建模的完整性和精确性, 需要规划出可以同时兼顾未知环境覆盖与探索的旋翼无人机运动路径.文献[107]首次提出通过实时选择可以同时最大化探索信息量和覆盖面积的目标以实现杂乱未知环境的建模.具体而言, 首先选择信息量最大的环境探索目标, 然后规划无人机到达探索目标的路径同时最大化该路径上无人机视点对环境的覆盖面积.采用如图 4(b)所示的相机视锥模型, 环境表面是否被有效覆盖的判断标准如下:

$ \begin{align} &{D_{\min }} \leqslant\| {{{P}_s} - {{P}_v}} \| \leqslant {D_{\max }}, \end{align} $

(6)

$ \begin{align} &{ n}_s \cdot ({P}_v - {P}_s)/\| {{{ n}_s}} \|\| {{{P}_s} - {{P}_c}} \| \geqslant T_{\min }. \end{align} $

(7)

其中: $ P_v $为无人机视点, $ P_s $为体素的表面中心点, $ n_s $为体素表面点的法向量, $ D $和$ T $为关于测量距离和传感器朝向的常数阈值.虽然所提出方法生成的探索路径不是最短的, 但是可以实现覆盖面积最大化.文献[108]同样采用上述相机模型和视点评估指标完成机器人环境探索与覆盖目标的选择.此外, 其采用局部-全局综合规划框架, 提高环境建模的完整性.该框架首先将环境划分为互不相交的小立方体子区域, 然后从全局角度利用TSP问题求解每个小立方体的访问顺序, 而在局部范围内(即小立方体内)通过采样策略获得可以完成环境表面覆盖的机器人视点, 并通过类似文献[54]的方法得到局部最佳探索路径.通过以上策略, 文献[108]实现了校园环境等大范围场景的建模, 并将该方法成功应用于旋翼无人机和地面移动机器人平台上.针对环境同时覆盖与探索问题, 文献[109]首次提出同时构建未知环境的三维体素地图和截断符号距离场(truncated signed distance field, TSDF)表面模型.其中: 三维体素地图用于环境边界提取, 并利用文献[104]所提算法进行探索规划; TSDF模型用于评估环境表面模型的质量, 并根据表面模型质量确定用于表面覆盖的无人机视点, 文献总体探索框架与文献[108]提出的局部-全局规划策略相似.为了量化无人机采样视点对环境重建精度的影响, 文献[95]通过分析TSDF地图构建原理以及深度传感器的测量噪声模型, 提出无人机视点的信息增益计算方式如下:

$ \begin{align} &{\rm gain}(\xi ) = \\ & \sum\limits_{{m} \in {\rm Vis}(\xi )} \begin{cases} 1, m \in U;\\ \dfrac{\eta (m) - \eta _{\min }}{1 - \eta _{\min }}, m \in S\bigwedge \eta (m) > {\eta _{\min }};\\ {0, } {\rm otherwise}. \end{cases} \end{align} $

(8)

其中: $ \xi = [{x, y, z, {\rm yaw}}] $为某个无人机的视点, $ {m} $为TSDF地图中的体素单元, $ U $和$ S $分别为$ {m} $处于未知状态和占据状态(即属于模型表面的体素), $ \eta({m}) $为视点对TSDF模型构建产生的期望影响, $ \eta _{\min } $为视点影响因子的最小值.在进行探索规划时, 通过式(8)进行候选视点效用评估可以提高环境模型的重建质量.与上述方法类似, 文献[110]通过分析当前环境的TSDF模型, 提取环境中重建精度低或者重建不完整的表面区域, 利用类似文献[53]的对偶采样方法生成无人机覆盖路径点, 最后通过求解一个非对称的TSP问题得到相应的探索路径.在此基础上, 将所提出算法应用于多无人机协同的未知环境表面重建^[111]任务中, 取得了出色的重建效率与质量.

虽然上述方法实现了未知环境的同时覆盖与探索, 但与多传感器网络覆盖规划^[112-115]或计算机图形学领域的NBVP^[116]相比, 所采用的传感器模型较为简单, 并且所考虑的覆盖质量评价指标也较为单一.因此, 今后关于同时覆盖与探索规划方面的研究除聚焦于高效的探索策略设计外, 还需要考虑引入更加复杂的传感器模型和更加全面的视点评估指标, 以提高未知环境信息下的环境建模精度.

4 总结与展望 4.1 总结

旋翼无人机由于具有灵活机动性、轻量化、成本低等优点受到国内外学者的广泛关注.不同于地面移动机器人, 旋翼无人机不直接与环境进行接触式交互, 因此适用于复杂三维环境的覆盖与探索.基于此, 本文围绕覆盖规划、探索规划、同时覆盖与探索规划3个方面进行了详细的综述.具体而言, 目前关于旋翼无人机环境覆盖规划的研究一般需要提前掌握环境先验信息, 适合已知环境信息情形下的高精度三维模型重建问题, 因此关于覆盖规划的研究属于离线运动规划范畴; 与之相反, 关于旋翼无人机环境探索规划的研究不需要环境的任何先验知识, 可以实现未知环境的全自主探索与建图, 因此关于探索规划的研究属于在线运动规划范畴; 随着研究的深入与硬件设备的发展, 使得基于旋翼无人机的环境同时覆盖与探索规划成为可能, 其充分考虑机器人覆盖与探索规划中存在的问题, 实现无人机完成环境探索的同时提高环境建模质量.

4.2 展望

虽然关于旋翼无人机环境覆盖与探索规划的研究正处于飞速发展阶段, 越来越多的算法已成功应用于工程实践中, 但是因实际任务场景中具有诸多约束与不确定性, 导致现有算法的鲁棒性和可扩展性无法得到充分保证.因此, 关于旋翼无人机环境覆盖与探索规划的未来发展方向可以大致归结为以下几点:

1) 异构多机器人协同环境覆盖与探索规划.

目前, 关于多机器人协同环境覆盖与探索方面的研究, 大多还关注于同构多机器人协同的情形, 例如多个地面移动机器人协同的环境覆盖^[117]或探索^[118]、多个旋翼无人机协同的环境覆盖^[119]或探索^[120].而关于异构多机器人协同场景下的环境覆盖与探索规划研究相对较少.通常异构多机器人系统由两种及以上不同类型的机器人平台构成, 若将其优缺点互补, 则可以提高任务完成效率与质量.例如, 空中机器人与地面移动机器人相互组合, 可以进行无人机回收充电保证无人机续航能力, 实现大范围场景的长期覆盖与探索; 利用无人机-水面艇-水下潜器形成一个立体覆盖网络实现面向海洋环境监测等任务的海陆空协同覆盖.因此, 如何开发异构多机器人自主协同系统, 并根据不同机器人特性以及特定任务目标为其设计协同覆盖与探索规划算法有望成为未来的重点研究方向.

2) 基于学习方法的环境覆盖与探索规划.

传统的机器人环境覆盖和探索规划研究已经取得巨大成功, 并且形成了一系列行之有效的研究框架, 大量研究成果早已被应用于真实的任务场景.然而, 在现有硬件设备条件下传统方法难以有进一步的重大突破, 因此有学者将目前炙手可热的智能学习算法引入到机器人环境覆盖和探索规划中^{[117, 121]}, 并取得了令人满意的实验结果.目前, 关于这部分的研究才刚刚起步, 仍需要进一步探究其在实际应用中的可行性.此外, 基于学习的方法具有计算资源消耗大、算法验证周期长、算法泛化能力弱等缺点, 这也将成为其在实际应用中的主要阻碍.随着研究的不断深入, 基于学习的方法有望成为机器人环境覆盖与探索规划领域的研究热点.

3) 考虑定位不确定性的环境覆盖与探索规划.

本文分析的所有方法基本都具有一个前提假设, 即旋翼无人机在执行覆盖或探索任务时认为其本身定位是准确无误的.显然, 这在实际应用中是无法满足的, 现有的各种机器人定位算法^[1-2]都存在或多或少的定位误差或漂移.而当覆盖或探索任务对环境建模精度要求较高时, 研究考虑定位不确定性的旋翼无人机环境覆盖与探索规划方法则非常必要^[122].此外, 在规划过程中考虑机器人地位的不确定性也可以为机器人导航安全提供保障^[123].然而, 目前关于这方面的研究尚未形成统一的研究框架, 考虑定位不确定性的环境覆盖与探索规划是一个非常具有发展前景的研究方向.

4) 通信约束下的多无人机环境覆盖与探索规划.

现有方法除对旋翼无人机定位问题作出假设外, 多无人机协同情形下的环境覆盖和探索通常假设无人机间的通信良好并可以确保信息及时共享, 但无人机负载能力有限无法携带大型天线阵列, 往往会导致无人机间的通信质量无法保证.因此, 如何确保无人机移动过程中的良好通信是多无人机协同环境覆盖与探索在实际应用场景中的切实需求.传统基于全向天线的移动自组网方式, 无法保证在节点高速移动过程中依然保持链路稳定性, 并且易受地面基站干扰, 不适合无人机多机协同系统.目前, 通过在无人机上部署定向天线成为实现多无人机系统高质量通信的一种有效手段^[124-127], 其具有体积小、重量轻、能耗低等优点, 而且较少受到地面基站的干扰, 是今后研究通信约束下多无人机协同环境覆盖与探索问题的可行方案.

张雪波教授科研团队依托南开大学人工智能学 院机器人与信息自动化研究所和天津市智能机器人 技术重点实验室,长期围绕移动与飞行机器人的运动 规划与伺服控制、定位建图与场景理解、遥操作与 人机交互、强化学习与智能博弈等问题展开科学研 究. 承担了国家重点研发计划、国家自然科学基金、天津市杰出青年科学基金、国防项目等20余项,并在 IEEE 汇刊上发表了近50篇学术论文. 团队注重理论 联系实际,正在面向国家需求,推动高海拔科考机器 人、救援机器人、服务机器人的落地应用.

团队负责人张雪波教授入选了教育部青年长 江学者, 天津市杰出青年基金获得者,现任南开大 学人工智能学院智能科学系系主任,天津市智能机 器人技术重点实验室副主任,曾获天津市自然科学 一等奖和二等奖、吴文俊人工智能自然科学一等 奖、天津市优秀博士学位论文, 担任 IEEE/ASME Transactions on Mechatronics 和 ASME Journal of Dynamic Systems, Measurement and Control的编委,以 及多个国际学术会议的程序主席或组织主席. 团队 重视合作研究,与加拿大温莎大学、香港城市大学、大 连理工大学等多家国内外科研机构保持长期的合作 关系.