本发明涉及一种基于复合式边界检测的机器人自主探索方法，包括以下步骤：步骤1：利用基于改进随机树算法的全局边界检测算法来检测地图全局范围内的边界点；步骤2：利用多根搜索树边界检测算法和九宫格边界检测算法的局部边界检测算法来检测机器人周围的边界点；步骤3：对检测到的边界点进行筛选，即剔除已被探测过的边界点并对剩余边界点进行聚类；步骤4：综合评估机器人到每个筛选后的边界点的成本和收益，选出其中评估值最大的边界点作为机器人的探索目标点；步骤5：通过对探索目标点进行路径规划，然后驱动机器人对未知环境进行探索，逐步构建环境地图。本发明能够克服现有技术的不足，引导机器人自主探索未知环境并构建环境地图。
1.一种基于复合式边界检测的机器人自主探索方法，其特征在于：包括以下步骤：
步骤S1：基于变步长快速随机搜索树RRT算法检测二维栅格地图全局范围内的边界点实现全局边界检测；
步骤S2：利用融合了基于多棵搜索树边界检测算法和基于九宫格边界检测算法的局部边界检测算法来实时检测机器人周围的边界点；
步骤S3：对步骤S1和步骤S2检测到的边界点进行筛选，即剔除已被探测过的边界点并通过均值漂移聚类算法对剩余边界点进行聚类；
步骤S4：对筛选后的边界点进行评估并选出最优的探索目标点；即通过综合评估机器人到每个边界点的导航成本和信息收益，选出其中评估值最大的边界点作为机器人的探索目标点；
步骤S5：通过动态窗口法DWA算法对探索目标点进行路径规划，驱动机器人沿着规划出的路径对未知环境进行探索，逐步构建环境地图；
所述步骤S2的具体内容为：所述局部边界检测算法用于检测机器人周围边界点，局部边界检测位置跟随机器人的位置而变化；所述局部边界检测算法由基于多棵搜索树边界检测算法和基于九宫格边界检测算法两部分构成：基于多棵搜索树边界检测算法是将RRT算法中的一棵搜索树分拆成多棵子搜索树进行扩展；每棵子树的起始位置称为根节点，所述的多棵搜索树有一个根节点为机器人的当前位置，其余多个根节点设置在机器人周围障碍物另一侧，用以减少搜索树穿过缝隙进入障碍物另一侧空间内的时间，该检测算法中RRT的延伸步长为用户自定义的固定值，该步长应小于传感器探测半径；
基于九宫格边界检测算法用于补充检测基于多棵搜索树边界检测算法中出现漏检的边界，用以提高机器人对周围环境实时的边界检测效率；所述基于九宫格边界检测算法是以机器人为中心在栅格地图上生成8条检测线段，通过遍历每条线段上的栅格状态来查找边界；
步骤S3A：测量机器人到周围障碍物的距离：当机器人到最近障碍物的距离Ln小于一个用户指定值时，测量障碍物在该最近距离方向上的厚度Lt，当障碍物厚度满足预设范围时执行步骤SB；
步骤SB：生成九宫格线段：考虑到漏检的边界常出现在机器人上传感器的检测盲区，即在障碍物的另一侧，所以为了使得九宫格线段能在障碍物的另一侧生成，综合考虑机器人到最近障碍物的距离、最近障碍物的厚度和机器人本体最大尺寸来生成九宫格线段；九宫格线段以机器人为中心，分为内外侧两个正方形，内侧正方形以Lw为边长，外侧正方形以2*Lw为边长；边长Lw的计算公式如公式(1)所示：Lw＝Ln+Lt+Lr (1)
其中，Lw为九宫格内侧正方形边长，Ln为机器人到最近障碍物的距离，Lt为障碍物的厚度，Lr为在俯视图中机器人本体最大的尺寸；
步骤SC：检测线段上的边界点：步骤SB生成的九宫格线段共有8条线段，通过检测每条线段上的每个栅格状态，找出每条线段上的边界点，并进行标记。
2.根据权利要求1所述的一种基于复合式边界检测的机器人自主探索方法，其特征在于：所述步骤S1的具体内容为：使用二维栅格来表示地图，根据每个栅格上的不同情况，将其分为已探索无障碍物、已探索有障碍物和未探索三种状态三种栅格状态，将无障碍物状态区域和未探索状态区域交界处设定为边界，自主探索的目的是驱动机器人探索这些边界直到环境中没有边界出现；
基于变步长快速随机搜索树RRT算法来检测边界，并通过标记边界点的方式来定位边界；其中边界点是指当树新延伸的边与边界的交点；变步长快速随机搜索树RRT算法是在地图中已探索无障碍物的区域构建一个快速随机搜索树，并且全局树进行生长的起始位置为一个用户指定的点，选取机器人不始探索时的位置；每一条边的延伸方式为：首先在地图中选取一个随机点，然后选择树中离该随机点距离最近的树端点作为新延伸边的起点，延伸方向为该起点到随机点的方向；采用变步长的延伸方式来增加边界检测效率，每扩展一条边先以机器人上传感器的探测半径为步长进行边界检测，再分以下三种情况对搜索树进行延伸扩展：情况1：新延伸的边上先遇到未知区域边界，则标出边界点，步长置0，不进行扩展；
情况2：新延伸的边上先遇到障碍物，则采用指定的短步长进行扩展，短步长应小于传感器探测半径；
情况3：新延伸的边上没有边界和障碍物，则将新延伸的边作为步长进行扩展；
在这3种情况中，情况1为直接检测到边界点，并标出边界点位置的情况；
而情况2和情况3没有直接检测到边界点，所以对树进行延伸扩展操作，用以使树能填充已探索区域，同时树的边也能更加靠近未知区域边界，提高边界点被检测到的概率。
3.根据权利要求1所述的一种基于复合式边界检测的机器人自主探索方法，其特征在于：所述步骤S3的具体内容为：将步骤S1和步骤S2检测到的所有边界点进行筛选，筛选方式为：删除已探索的边界点，再利用均值聚类算法对剩余的边界点按照一个圆域进行聚类，并保留聚类后的圆心点，将筛选后的点用于边界点评估。
4.根据权利要求1所述的一种基于复合式边界检测的机器人自主探索方法，其特征在于：所述步骤S4具体包括以下步骤：步骤S41：信息收益是指以边界点为圆心，以小于机器人上传感器测量范围的r为半径，在这一圆内未探索区域面积为该边界点的收益值；
步骤S42：通过分段考虑机器人的导航成本，使得机器人优先探索周围的区域；将机器人导航成本分为两个部分，分别是机器人到边界点的直线距离和机器人通过路径规划后的路径长度；当机器人到边界点的直线距离小于一个设定范围Nrad参数Nrad取3.0～6.0米，则采用路径规划后的路径长度为代价值，对于机器人到边界点的直线距离大于这个设定范围Nrad时，则采用机器人到边界点的直线距离为代价值；机器人的导航成本的计算如公式(2)所示：式中，β为用户自定义常量参数，用于调节代价值的权重；N(Da，Db)为机器人坐标Da到边界点坐标Db的导航成本；||Db‑Da||为机器人坐标Da到边界点坐标Db的直线距离；MakePlan(Da，Db)为从机器人坐标Da经过路径规划导航到边界点坐标Db的路径长度；Nrad为用户自定义的范围半径值；
步骤S43：对每个边界点进行评估，评估值由导航成本N与信息收益I确定；选出其中评估值最大的边界点作为机器人的探索目标点；
式中，λ为用户定义的常量参数，用于调节信息收益的权重；I(Db)为边界点坐标Db的信息收益。
一种基于复合式边界检测的机器人自主探索方法
技术领域
[0001] 本发明涉及工业移动机器人设计领域，特别是一种基于复合式边界检测的机器人自主探索方法。
背景技术
[0002] 随着移动机器人技术的不断发展，机器人所面临的工作环境越来越复杂，因此对机器人的自主性提出了新的挑战。移动机器人自主环境探索是指机器人在未知环境中，通过机器人上传感器获取环境信息确定下一步移动目标的过程，是移动机器人研究中一个重要的研究课题。自主探索未知环境是机器人自主构建环境地图的基础，自主探索策略直接影响未知环境地图构建的高效性和鲁棒性。
[0003] 许多探索策略属于由Yamauchi提出的基于前沿点的探索策略。将已知开放区域与未知区域之间的交界点定义为边界点，由机器人上传感器获取的环境地图信息，通过广度优先搜索获取离移动机器人直线距离最近的边界点作为临时目标点，引导机器人移动到这些边界进行探索。在现有的研究中，一些边界提取算法是基于数字图像处理中的边缘检测和区域提取技术，然而该方法仅适用于二维空间，并且随着地图的增大，图像处理过程将会消耗大量的计算资源。由此Keidar提出一种快速检测边界点的算法，该算法只处理实时接收的新的激光雷达数据，从而避免了搜索的区域，减少计算资源。该算法先根据激光数据的角度对其读数进行分类，再根据分类后的激光数据构建激光轮廓，然后从轮廓中提取新的边界。虽然该算法能够快速检测到边界点，但是需要维护以前的边界信息，这需要与映射组件紧密集成，从而导致算法变得比较复杂。Freda通过改进基于前沿点的随机树算法实现移动机器人未知环境的探索，通过在栅格地图中构造随机树的方式来生成处于已知区域和未知区域的边界点。Holz评估简单有效的基于前沿的探索策略，通过改进经典的基于前沿的探索策略来进一步缩短探索路径。
[0004] 综上可见，国内外学者对自主探索建图算法已有一定的优化效果，但仍然存在以下三个主要问题：
[0005] 第一、由于快速随机搜索树算法中延伸步长的限制导致在大范围环境中快速随机搜索树RRT对边界点检测的速度仍然不太理想；
[0006] 第二、由于快速随机搜索树算法的随机性导致该算法在复杂环境中难以快速通过狭窄入口或缝隙进行延伸，从而影响了机器人对入口或缝隙另一端空间中边界点的检测效率；
[0007] 第三、由于大部分算法在评估边界点的代价时大多是采用边界点到机器人位置的直线距离，当遇到机器人和边界点之间存在墙体或障碍物阻隔的情况时，虽然边界点到机器人的直线距离近但机器人却需要绕路才能到达，这导致了机器人错过周围导航距离更近的边界点。
发明内容
[0008] 有鉴于此，本发明的目的是提供一种基于复合式边界检测的机器人自主探索方法，能够克服现有技术的不足，引导机器人更高效地完成自主探索未知环境并建立相应的环境地图。
[0009] 本发明采用以下方案实现：一种基于复合式边界检测的机器人自主探索方法，包括以下步骤：
[0010] 步骤S1：利用基于变步长快速随机搜索树RRT(Rapidly‑exploring Random Tree)算法检测二维栅格地图全局范围内的边界点实现全局边界检测；
[0011] 步骤S2：利用融合了基于多根搜索树边界检测算法和基于九宫格边界检测算法的局部边界检测算法来实时检测机器人周围的边界点；
[0012] 步骤S3：对步骤S1和步骤S2检测到的边界点进行筛选，即剔除已被探测过的边界点并通过均值漂移聚类算法并对剩余边界点进行聚类；
[0013] 步骤S4：对筛选后的边界点进行评估并选出最优的探索目标点；即通过综合评估机器人到每个边界点的导航成本和信息收益，选出其中评估值最大的边界点作为机器人的探索目标点；
[0014] 步骤S5：通过动态窗口法DWA(Dynamic Window Approach)算法对探索目标点进行路径规划，驱动机器人沿着规划出的路径对未知环境进行探索，逐步构建环境地图。
[0015] 进一步地，所述步骤S1的具体内容为：使用二维栅格来表示地图，根据每个栅格上的不同情况，将其分为已探索无障碍物(0)、已探索有障碍物(1)和未探索(‑1)三种状态，将状态(0)区域和状态(‑1)区域交界处设定为边界，自主探索的目的是驱动机器人探索这些边界直到环境中没有边界出现；
[0016] 基于变步长快速随机搜索树RRT算法来检测边界，并通过标记边界点的方式来定位边界；其中边界点是指当树新延伸的边与边界的交点；变步长快速随机搜索树RRT算法是在地图中已探索无障碍物的区域构建一个快速随机搜索树，并且全局树进行生长的起始位置为一个用户指定的点，通常选取机器人开始探索时的位置；每一条边的延伸方式为：首先在地图中选取一个随机点，然后选择树中离该随机点距离最近的树端点作为新延伸边的起点，延伸方向为该起点到随机点的方向；采用变步长的延伸方式来增加边界检测效率，每扩展一条边先以机器人上传感器的探测半径为步长进行边界检测，再分以下三种情况对搜索树进行延伸扩展：
[0017] 情况1：新延伸的边上先遇到未知区域边界，则标出边界点，步长置0，不进行扩展；
[0018] 情况2：新延伸的边上先遇到障碍物，则采用指定的短步长进行扩展，短步长应小于传感器探测半径；
[0019] 情况3：新延伸的边上没有边界和障碍物，则将新延伸的边作为步长进行扩展。
[0020] 在这3种情况中，情况1为直接检测到边界点，并标出边界点位置的情况；
[0021] 而情况2和情况3没有直接检测到边界点，所以对树进行延伸扩展操作，用以使树能填充已探索区域，同时树的边也能更加靠近未知区域边界，提高边界点被检测到的概率。
[0022] 进一步地，所述步骤S2的具体内容为：所述局部边界检测算法用于检测机器人周围边界点，局部边界检测位置跟随机器人的位置而变化；所述局部边界检测算法由基于多根搜索树边界检测算法和基于九宫格边界检测算法两部分构成：
[0023] 基于多根搜索树边界检测算法是将RRT算法中的一棵搜索树分拆成多棵子搜索树进行扩展；每棵子树的起始位置称为根节点，所述的多根搜索树有一个根节点为机器人的当前位置，其余多个根节点设置在机器人周围障碍物另一侧，用以减少搜索树穿过缝隙进入障碍物另一侧空间内的时间，该检测算法中RRT的延伸步长为用户自定义的固定值，该步长应小于传感器探测半径；
[0024] 基于九宫格边界检测算法用于补充基于多根搜索树边界检测算法中可能出现漏检的边界，用以提高机器人对周围环境实时的边界检测效率；所述基于九宫格边界检测算法是以机器人为中心在栅格地图上生成8条检测线段，通过遍历每条线段上的栅格状态来查找边界；
[0025] 进一步地，所述基于九宫格边界检测算法查找边界的具体步骤如下：
[0026] 步骤S3A：测量机器人到周围障碍物的距离：当机器人到最近障碍物的距离Ln小于一个用户指定值时，测量障碍物在该最短距离方向上的厚度Lt，当障碍物厚度满足预设范围时执行步骤SB；
[0027] 步骤SB：生成九宫格线段：考虑到漏检的边界常出现在机器人上传感器的检测盲区，即在障碍物的另一侧，所以为了使得九宫格线段能在障碍物的另一侧生成，综合考虑机器人到最近障碍物的距离、最近障碍物的厚度和机器人本体最大尺寸来生成九宫格线段；九宫格线段以机器人为中心，分为内外侧两个正方形，内侧正方形以Lw为边长，外侧正方形以2*Lw为边长；边长Lw的计算公式如公式(1)所示：
[0028] Lw＝Ln+Lt+Lr (1)
[0029] 其中，Lw为九宫格内侧正方形边长，Ln为机器人到最近障碍物的距离，Lt为障碍物的厚度，Lr为在俯视图中机器人本体最大的尺寸；
[0030] 步骤SC：检测线段上的边界点：步骤SB生成的九宫格线段共有8条线段，通过检测每条线段上的每个栅格状态，找出每条线段上的边界点，并进行标记。
[0031] 进一步地，所述步骤S3的具体内容为：
[0032] 将步骤S1和步骤S2检测到的所有边界点进行筛选，筛选方式为：删除已探索的边界点，再对剩余的边界点按照一个圆域进行聚类，保留聚类后的圆心点，将筛选后的点用于边界点评估。
[0033] 进一步地，所述步骤S4具体包括以下步骤：
[0034] 步骤S41：信息收益是指以边界点为圆心，以小于机器人上传感器测量范围的r为半径，在这一圆内未探索区域面积为该边界点的收益值；
[0035] 步骤S42：通过分段考虑机器人的导航成本，使得机器人优先探索周围的区域；将机器人导航成本分为两个部分，分别是机器人到边界点的直线距离和机器人通过路径规划后的路径长度；当机器人到边界点的直线距离小于一个设定范围Nrad参数Nrad一般取3.0～6.0米，则采用路径规划后的路径长度为代价值，对于机器人到边界点的直线距离大于这个设定范围Nrad时，则采用机器人到边界点的直线距离为代价值；机器人的导航成本的计算如公式(2)所示：
[0036]
[0037] 式中，β为用户自定义常量参数，用于调节代价值的权重；N(Da,Db)为机器人坐标Da到边界点坐标Db的导航成本；||Db‑Da||为机器人坐标Da到边界点坐标Db的直线距离；MakePlan(Da,Db)为从机器人坐标Da经过路径规划导航到边界点坐标Db的路径长度；Nrad为用户自定义的范围半径值；
[0038] 步骤S43：对每个边界点进行评估，评估值由导航成本N与信息收益I确定；选出其中评估值最大的边界点作为机器人的探索目标点；
[0039] 对边界点的评估函数R(Db)如公式(3)所示：
[0040]
[0041] 式中，λ为用户定义的常量参数，用于调节信息收益的权重；I(Db)为边界点坐标Db的信息收益；N(Da,Db)为机器人坐标Da到边界点坐标Db的导航成本。
[0042] 与现有技术相比，本发明具有以下有益效果：
[0043] (1)本发明变步长快速随机搜索树RRT算法，该算法在保证机器人可以完整探索完整个环境地图的同时，通过先检测以传感器检测半径为步长上的边界，再以变步长的方式进行扩展，相比传统以固定步长进行扩展的RRT，改进后的RRT算法可以提高边界点的检测速度。
[0044] (2)本发明局部边界点检测算法是由基于多根搜索树边界检测算法和基于九宫格的边界检测算法构成来检测机器人周围环境的边界点。其中，多根搜索树边界检测算法通过将一棵搜索树分拆成多棵子搜索树的同时，将多棵子搜索树的位置设置在机器人周围障碍物的另一侧进行扩展，减少搜索树穿过缝隙进入障碍物另一侧空间内的时间，以此提高局部边界检测的速度并增加局部边界检测的范围；通过采用基于九宫格的边界检测算法对周围可能漏检的边界进行补充检测，以适应机器人自主探索的实时性。相比传统基于RRT的边界检测算法，本发明提出的局部边界检测算法可以跨越障碍物进行探索，减少了搜索树探索并通过障碍物之间的缝隙或入口的时间，所以尤其在多障碍物的复杂环境中本发明采用的局部边界检测算法比其他方法能更快地检测到边界。
[0045] (3)本发明通过综合评估机器人到每个边界点的导航成本和信息收益，选出其中评估值最大的边界点作为机器人的探索目标点。本发明根据各个边界点和机器人的位置，分别采用步骤S42中的机器人到边界点的直线距离和路径规划后的路径长度作为导航代价来评估各个边界点，引导机器人优先探索周边区域的边界点，避免重复探索，提高探索的效率。
附图说明
[0046] 图1为本发明实施例的方法流程图。
[0047] 图2为本发明实施例的采用的变步长全局边界检测算法检测边界点和延伸示意图，其中，图2(a)表示新延伸的边xnearestxlidar上先遇到未知区域边界，则标出边界点，不进行扩展,步长η＝0米；图2(b)表示新延伸的边xnearestxlidar上先遇到障碍物，则采用指定的短步长η＝ηglobal进行扩展；图2(c)表示新延伸的边xnearestxlidar上没有边界和障碍物，则将新延伸的边作为步长η＝Llidar进行扩展。
[0048] 图3为本发明实施例的采用的局部边界检测算法示意图，其中，图3(a)为基于多根搜索树边界检测算法示意图，图3(b)为基于九宫格的边界检测算法示意图。
[0049] 图4为本发明实施例的评估函数中导航成本采用机器人到边界点的直线距离和采用路径规划后的导航路程长度对比图。
[0050] 图5为本发明实施例的仿真环境和建立的地图示意图，其中，图5(a)为机器人在仿真软件Gazebo中构建的仿真环境，图5(b)为探索仿真环境后生成的栅格地图。
[0051] 图6为本发明实施例的真实环境和建立的地图示意图。其中，图6(a)为机器人进行实际实验时采用的真实环境，图6(b)为探索真实环境后生成的栅格地图。
具体实施方式
[0052] 下面结合附图及实施例对本发明做进一步说明。
[0053] 应该指出，以下详细说明都是例示性的，旨在对本申请提供进一步的说明。除非另有指明，本文使用的所有技术和科学术语具有与本申请所属技术领域的普通技术人员通常理解的相同含义。
[0054] 需要注意的是，这里所使用的术语仅是为了描述具体实施方式，而非意图限制根据本申请的示例性实施方式。如在这里所使用的，除非上下文另外明确指出，否则单数形式也意图包括复数形式，此外，还应当理解的是，当在本说明书中使用术语“包含”和/或“包括”时，其指明存在特征、步骤、操作、器件、组件和/或它们的组合。
[0055] 如图1所示，本实施例提供一种基于复合式边界检测的机器人自主探索方法，包括以下步骤：
[0056] 步骤S1：基于变步长快速随机搜索树RRT(Rapidly‑exploring Random Tree)算法检测算法来检测二维栅格地图全局范围内的边界点实现全局边界检测；
[0057] 步骤S2：利用融合了基于多根搜索树边界检测算法和基于九宫格边界检测算法的局部边界检测算法来实时检测机器人周围的边界点；
[0058] 步骤S3：对步骤S1和步骤S2检测到的边界点进行筛选，即剔除已被探测过的边界点并通过均值漂移聚类算法对剩余边界点进行聚类；
[0059] 步骤S4：对筛选后的边界点进行评估并选出最优的探索目标点；即通过综合评估机器人到每个边界点的导航成本和信息收益，选出其中评估值最大的边界点作为机器人的探索目标点；
[0060] 步骤S5：通过动态窗口法DWA算法对探索目标点进行路径规划，驱动机器人沿着规划出的路径对未知环境进行探索，逐步构建环境地图。
[0061] 在本实施例中，所述步骤S1的具体内容为：使用二维栅格来表示地图，根据每个栅格上的不同情况，将其分为已探索无障碍物(0)、已探索有障碍物(1)和未探索(‑1)三种状态，将状态(0)区域和状态(‑1)区域交界处设定为边界，自主探索的目的是驱动机器人探索这些边界直到环境中没有边界出现；
[0062] 如图2所示，基于变步长快速随机搜索树RRT算法来检测边界，并通过标记边界点的方式来定位边界；其中边界点是指当树新延伸的边与边界的交点；变步长快速随机搜索树RRT算法是在地图中已探索无障碍物的区域构建一个快速随机搜索树，并且全局树进行生长的起始位置为一个用户指定的点，通常选取机器人开始探索时的位置；每一条边的延伸方式为：首先在地图中选取一个随机点，然后选择树中离该随机点距离最近的树端点作为新延伸边的起点，延伸方向为该起点到随机点的方向；与传统快速随机搜索树RRT算法最大的不同在于，传统RRT算法是以固定的步长进行延伸，边界检测速度慢，而本实施例采用变步长的延伸方式来增加边界检测效率，每扩展一条边先以机器人上传感器的探测半径为步长进行边界检测，再分以下三种情况对搜索树进行延伸扩展：
[0063] 情况1：新延伸的边上先遇到未知区域边界，则标出边界点，步长置0，不进行扩展；
[0064] 情况2：新延伸的边上先遇到障碍物，则采用指定的短步长进行扩展，短步长应小于传感器探测半径，根据经验常指定为1.0米；
[0065] 情况3：新延伸的边上没有边界和障碍物，则将新延伸的边作为步长进行扩展。
[0066] 在这3种情况中，情况1为直接检测到边界点，并标出边界点位置的情况；
[0067] 而情况2和情况3没有直接检测到边界点，所以对树进行延伸扩展操作，用以使树能填充已探索区域，同时树的边也能更加靠近未知区域边界，提高边界点被检测到的概率。
[0068] 如图3所示，在本实施例中，所述步骤S2的具体内容为：所述局部边界检测算法用于检测机器人周围边界点，局部边界检测位置跟随机器人的位置而变化；所述局部检测算法由基于多根搜索树边界检测算法和基于九宫格边界检测算法两部分构成：
[0069] 如图3(a)所示，基于多根搜索树边界检测算法是将RRT算法中的一棵搜索树分拆成多棵树进行扩展。每棵子树的起始位置称为根节点。所述的多根搜索树有一个根节点为机器人的当前位置，其余多个根节点设置在机器人周围障碍物另一侧用以减少搜索树穿过缝隙进入障碍物另一侧空间内的时间；该检测算法中RRT的延伸步长为用户自定义的固定值，该步长应小于传感器探测半径，根据经验通常设置为1.0米；
[0070] 如图3(b)所示，基于九宫格边界检测算法用于补充基于多根搜索树边界检测算法中可能出现漏检的边界，用以提高机器人对周围环境实时的边界检测效率；所述基于九宫格边界检测算法是以机器人为中心在栅格地图上生成8条检测线段，通过遍历每条线段上的栅格状态来查找边界。
[0071] 在本实施例中，所述基于九宫格边界检测算法查找边界的具体步骤如下：
[0072] 步骤S3A：测量机器人到周围障碍物的距离：当机器人到最近障碍物的距离Ln小于一个用户指定值时(Ln应小于机器人上传感器的探测半径，通常指定为3.0米)，测量障碍物在该最短距离方向上的厚度Lt，当障碍物厚度满足预设范围时执行步骤SB(该范围通常指定为0米到1.0米)；
[0073] 步骤SB：生成九宫格线段：考虑到漏检的边界常出现在机器人上传感器的检测盲区，即在障碍物的另一侧，所以为了使得九宫格线段能在障碍物的另一侧生成，综合考虑机器人到最近障碍物的距离、最近障碍物的厚度和机器人本体最大尺寸来生成九宫格线段；九宫格线段以机器人为中心，分为内外侧两个正方形，内侧正方形以Lw为边长，外侧正方形以2*Lw为边长；边长Lw的计算公式如公式(1)所示：
[0074] Lw＝Ln+Lt+Lr (1)
[0075] 其中，Lw为九宫格内侧正方形边长，Ln为机器人到最近障碍物的距离，Lt为障碍物的厚度，Lr为在俯视图中机器人本体最大的尺寸；
[0076] 步骤SC：检测线段上的边界点：步骤SB生成的九宫格线段共有8条线段，通过检测每条线段上的每个栅格状态，找出每条线段上的边界点，并进行标记。
[0077] 在本实施例中，所述步骤S3的具体内容为：
[0078] 将步骤S1和步骤S2检测到的所有边界点进行筛选，筛选方式为：删除已探索的边界点，再利用均值聚类算法对剩余的边界点按照一个圆域进行聚类，并保留聚类后的圆心点，将筛选后的点用于边界点评估。
[0079] 在本实施例中，所述步骤S4具体包括以下步骤：
[0080] 步骤S41：信息收益是指以边界点为圆心，以小于机器人上传感器测量范围的r为半径，在这一圆内未探索区域面积为该边界点的收益值；
[0081] 步骤S42：如图4所示，通过分段考虑机器人的导航成本，使得机器人优先探索周围的区域；将机器人导航成本分为两个部分，分别是机器人到边界点的直线距离和机器人通过路径规划后的路径长度；当机器人到边界点的直线距离小于一个设定范围Nrad，参数Nrad一般取3.0～6.0米，根据经验常将Nrad设置为3.0米，则采用路径规划后的路径长度为代价值，对于机器人到边界点的直线距离大于这个设定范围Nrad时，则采用机器人到边界点的直线距离为代价值；机器人的导航成本的计算如公式(2)所示：
[0082]
[0083] 式中，β为用户自定义常量参数，用于调节代价值的权重；N(Da,Db)为机器人坐标Da到边界点坐标Db的导航成本；||Db‑Da||为机器人坐标Da到边界点坐标Db的直线距离；MakePlan(Da,Db)为从机器人坐标Da经过路径规划导航到边界点坐标Db的路径长度；Nrad为用户自定义的范围半径值；
[0084] 步骤S43：对每个边界点进行评估，评估值由导航成本N与信息收益I确定；选出其中评估值最大的边界点作为机器人的探索目标点；
[0085] 对边界点的评估函数R(Db)如公式(3)所示：
[0086]
[0087] 式中，λ为用户定义的常量参数，用于调节信息收益的权重；I(Db)为边界点坐标Db的信息收益；N(Da,Db)为机器人坐标Da到边界点坐标Db的导航成本。
[0088] 较佳的，在本实施例中，传统RRT是以固定步长进行生长，变步长的特点在于先通过一个大步长检测边界点，再进行生长。传统RRT为一棵树，多根搜索树是将一棵树分拆成多棵树以固定步长进行生长。并且每棵子树的位置都跟随周围的障碍物进行变化。
[0089] 较佳的，本实施例采用Turtlebot2移动机器人配备激光雷达传感器模型。如图5(a)所示，采用移动机器人系统在10.0米×10.0米的仿真地图中进行算法验证。机器人探索该仿真环境并建立完整的二维栅格地图如图5(b)所示。实验中，机器人的速度和角速度分别被设置为0.65米/秒和5.0弧度/秒。全局边界点检测算法的步长ηglobal设置为1.0米，多根搜索树RRT局部边界点检测算法的步长ηlocal设置为1.0米。其它相关参数如下：代价范围半径Nrad＝4.0米，信息收益半径r＝1.0米，代价权重β＝0.5，信息收益权重λ＝2.0，雷达测量范围Llidar＝18.0米。
[0090] 本实施例在采用Turtlebot2移动机器人配备RPLIDARA2激光雷达传感器，同时采用与仿真相同的参数设置，在8.0米×8.0米的真实场景中进行算法验证，并相应地构建完整的二维栅格地图，如图6所示。
[0091] 本领域内的技术人员应明白，本申请的实施例可提供为方法、系统、或计算机程序产品。因此，本申请可采用完全硬件实施例、完全软件实施例、或结合软件和硬件方面的实施例的形式。而且，本申请可采用在一个或多个其中包含有计算机可用程序代码的计算机可用存储介质(包括但不限于磁盘存储器、CD‑ROM、光学存储器等)上实施的计算机程序产品的形式。
[0092] 本申请是参照根据本申请实施例的方法、设备(系统)、和计算机程序产品的流程图和/或方框图来描述的。应理解可由计算机程序指令实现流程图和/或方框图中的每一流程和/或方框、以及流程图和/或方框图中的流程和/或方框的结合。可提供这些计算机程序指令到通用计算机、专用计算机、嵌入式处理机或其他可编程数据处理设备的处理器以产生一个机器，使得通过计算机或其他可编程数据处理设备的处理器执行的指令产生用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的装置。
[0093] 这些计算机程序指令也可存储在能引导计算机或其他可编程数据处理设备以特定方式工作的计算机可读存储器中，使得存储在该计算机可读存储器中的指令产生包括指令装置的制造品，该指令装置实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能。
[0094] 这些计算机程序指令也可装载到计算机或其他可编程数据处理设备上，使得在计算机或其他可编程设备上执行一系列操作步骤以产生计算机实现的处理，从而在计算机或其他可编程设备上执行的指令提供用于实现在流程图一个流程或多个流程和/或方框图一个方框或多个方框中指定的功能的步骤。
[0095] 以上所述，仅是本发明的较佳实施例而已，并非是对本发明作其它形式的限制，任何熟悉本专业的技术人员可能利用上述揭示的技术内容加以变更或改型为等同变化的等效实施例。但是凡是未脱离本发明技术方案内容,依据本发明的技术实质对以上实施例所作的任何简单修改、等同变化与改型，仍属于本发明技术方案的保护范围。
