基于拓扑地图的移动机器人室内环境高效自主探索算法

基于拓扑地图的移动机器人室内环境高效自主探索算法

齐立哲 何东东 陈骞 孙云权
复旦大学工程与应用技术研究院

1 引言(Introduction)

随着科学技术的快速发展,移动机器人从最初的工厂物流搬运,渐渐应用到家庭服务、农业、军事、医疗等各个领域,提升了生产效率并改变了人类的生活方式 [1-6]。同步定位和地图构建(SLAM)技术是自主移动机器人的核心技术之一[7-9],该技术可以根据运动过程中传感器的实时数据实现机器人自身的位姿估计,同时增量式地构建整个环境的地图 [10],进而根据构建好的地图实现自主规划与导航。可见,构建机器人应用场景地图是使机器人具有自主运动能力的关键环节。但目前移动机器人还是需要技术人员手动控制机器人在陌生场景中的运动来实现地图构建。这种人工控制机器人建图的方式不仅对人员要求高且预先部署需要花费大量时间,效率低下,而且也会影响机器人在人类无法进入的场景中使用[11-12]。因此,使机器人具备自主探索的能力,从而在陌生的环境中能够自动构建地图,是目前移动机器人需要解决的难题之一,这不仅要求机器人具备基本的 SLAM 能力,还要具备对当前接收到的环境信息进行分析和决策的能力,机器人需要自主地决策运动方向并规划移动路径[13-15]。

在机器人自主探索领域的研究中,Yamauchi [16]提出了一种基于前沿点的自主探索算法,该算法的核心思想是不断地从当前地图边界选取最佳目标点,在驱动机器人前往该目标点移动的同时,逐渐扩展地图边界,重复这个过程可构建出整个环境的地图。该算法最大的亮点在于机器人在探索过程中会更加有目的性地自主选取探索区域,相对随机式的探索而言,建图的效率得到了很大的提升。文[17-18] 均是基于这一思路提出的自主探索方法,在基于前沿点的自主探索方法中,探测地图的边界是选取最佳目标点的前提;Keidar [18] 和 Senarathne [19]等改进了原有的边界提取模块,避免对整个地图数据进行处理,降低了算法的运算时间和内存消耗;刘瑞雪等 [20] 提出了一种基于曲线拟合和目标探索点邻域规划的自主建图方法,同样也取得了一定的效果;李秀智等[21] 在前沿点探索理论的基础上,提出了一种基于几何规则的候选目标点生成方法,实现了目标点的快速提取。

快速扩展随机树(RRT)是一种用于解决点到点路径规划问题的算法,尽管所选取的路径并非是全局最优路径,但是 RRT 算法在执行时具有概率完备性。机器人在自主探索任务中,需要自主构建一个覆盖完整度较高的地图,而 RRT 算法的良好特性刚好可以保证较高的地图覆盖程度。文 [22-25]均是通过动态建立的随机探索树来完成整个环境的探测。国内的高环宇等[24] 改善了探索树的回溯策略,减少了多次覆盖和陷入回路的情况。杨傥月等[26] 提出了一种改进的 RRT 算法,利用变生长率的全局 RRT 来提高探索的效率。杜明博等[27] 提出了一种连续曲率 RRT 算法,结合环境约束以及车辆自身的约束大大提高了规划的速度和质量。

在自主探索过程中,移动机器人的建图与定位还要依赖于视觉或激光传感器。基于粒子滤波的 SLAM 算法有 Hector-SLAM、Gmapping 等,这类算法在对机器人进行位姿估计时只需对当前帧的位姿进行优化,并不需要处理当前帧之前的位姿。在这种情况下,自主探索算法可以分成 2 个独立的模块,分别是未知环境路径规划模块和 SLAM 算法。Sun 等[28] 采用了一种基于图优化的 SLAM 算法,由于图优化算法进行位姿估计时会对所有的历史位姿进行优化,因此将基于图优化的算法用于自主探索任务中时,地图建立的准确性会更高。文[29-30] 同样也是把自主探索任务中的 SLAM 模块改为基于图优化的算法。然而基于图优化的 SLAM算法在自主探索任务中计算量增长较快,将降低机器人自主探索的效率。

综上可知,目前机器人自主探索可以从以下 2个方面进行改进:一个是在算法循环执行过程中,如何更加快速地提取前沿区域;另一个是在机器人移动探索过程中,如何减少其陷入回路的次数,进而提升整个自主探索算法的执行效率。因此本文提出了 TMRRT 自主探索算法,以 RRT 探索算法为基础,加入拓扑地图模块,拓扑地图模块会记录机器人过往探索的目标点,用于辅助筛选下一刻的最佳探索点,在一定程度上减少机器人陷入回路的次数。通过 Means Shift 算法对前沿点进行聚类处理,在 RRT 模块中设置自适应的增长速度,加快初始阶段对前沿区域的检测速度,提高移动机器人自主探索的实时性。

2 TMRRT 自主探索算法(TMRRT autonomous exploration algorithm)

本文提出的自主探索算法的执行流程如图 1 所示。整个算法总体可分为 3 个模块,分别是基于改进 RRT 算法的前沿点探测模块、前沿点筛选模块以及执行器模块。前沿点探测模块利用改进的 RRT 路径规划算法探测当前地图的已知区域与未知区域的边界,并提取边界上周围所有可能有一定的未知区域点的前沿目标点。前沿点筛选模块接收探测模块探测到的所有前沿点,并对前沿点进行聚类处理,通过设定效用函数筛选出最佳前沿点。执行器模块将筛选出的最佳前沿点发送给执行器进行后续的路径规划,并利用 SLAM 技术同步扩展更新地图。同时,执行器会将最佳前沿点添加到拓扑地图中,从而更新拓扑地图。

2.1 拓扑地图表示法

在拓扑地图的表示模型中,整个环境地图根据一定的分辨率进行栅格化处理,每个栅格有占用、空闲和未知 3 种状态。用 −1、0 和 1 来表示每个栅格的 3 种状态,在地图建立的过程中,对于已经建立地图的区域,所有的栅格只会有 2 种状态。若某个栅格对应的物理空间中是有障碍物的,则该栅格的状态为占用,在地图上的值为 1;若该物理空间没有障碍物存在,则该栅格的状态为空闲,其对应的值为 0。其他未显示的区域为未知栅格,其对应的值为 −1。与未知栅格相邻的所有空闲栅格(即图 2 中标注有 f 的栅格)都属于当前地图的边界,也被称为前沿点。

图片[1]-基于拓扑地图的移动机器人室内环境高效自主探索算法
图 1 TMRRT 自主探索算法的执行流程
图片[2]-基于拓扑地图的移动机器人室内环境高效自主探索算法
图 2 栅格地图

RRT 算法具有概率完备性,因而可以根据是否生成新的前沿点来判断地图是否还有未探索的区域。若没有新的前沿点生成,且聚类后的前沿点皆被探索到,则认为已经完成对未知区域的探索。

2.2 TMRRT 前沿点探测模块

在前沿点探测模块中,分别采用全局 RRT 和局部 RRT 算法探测地图上的边界。初始阶段,RRT的状态为 V = {Xinit},E = Ø,其中 Xinit 表示机器人的出发位置,E 表示节点间的拓扑距离的集合,初始为空,V 表示整个生成树的所有节点,令 G(V,E)表示整个 RRT 树状结构。全局 RRT 算法以机器人出发点为根节点,通过 SampleTree 函数不断地在地图中进行采点,得到 Xsample,随后从当前的生成树中找到与采样点最近的树节点 Xnearest,然后在Xsample 和 Xnearest 之间根据 RRT 的生长率参数 η,通过 Steer 函数生成一个新节点 Xnew。将参数 η 由一般的经验值设置为可变的值来加快 RRT 的生长速率,其具体的值由 ηgain 函数确定,ηgain 的求解原理是通过求解 Xinit 和 Xnearest 之间的距离,在满足一定距离条件下设置 η 与该距离的值成反比。最后通过一个 Check 函数来判断 Xnew 周围的情况,当检测到Xnew 周围没有未探索的栅格点时,则将 Xnew 加入到RRT G 中;反之将 Xnew 视作一个前沿点,并将其发送到前沿点筛选模块中。整个过程执行的伪代码如算法 1 所示。

图片[3]-基于拓扑地图的移动机器人室内环境高效自主探索算法
算法 1 自适应生长速率的全局 RRT

局部 RRT 探测器的执行过程和全局 RRT 探测器的执行流程基本一致。考虑到探索后期,全局RRT 的步长会越来越短,导致无法及时有效地探测到部分角落处的点,因此需要用局部 RRT 来弥补这一缺陷,且局部 RRT 的生长速率较全局 RRT 更低。为了提高执行速度,利用局部 RRT 每探测到一个前沿点,便清空局部 RRT 的所有节点,并重新建立新的 RRT。

2.3 前沿点筛选模块

算法在执行过程中,前沿点探测模块的探测速度会比较快,因此筛选模块会收到大量的前沿点,并且一部分前沿点会聚集分布在地图中。故本文采用 MeanShift 聚类算法在筛选最佳前沿点之前对所有前沿点的 2 维坐标进行均值聚类,从而降低前沿点的数据规模,最后得到若干个聚类中心坐标。

基于拓扑地图的移动机器人室内环境高效自主探索算法-AGV吧
基于拓扑地图的移动机器人室内环境高效自主探索算法
此内容为免费资源,请登录后查看
积分
免费资源
© 版权声明
THE END
喜欢就支持一下吧
点赞7 分享
评论 抢沙发

请登录后发表评论

    暂无评论内容