一种基于RRT的栅格地图遍历算法

摘要

本发明公开了一种基于RRT的栅格地图遍历算法，包括步骤：(1)根据待探索栅格地图确定搜索范围；(2)在步骤一确定的搜索范围内以机器人所在位置作为起点，以该起点为根节点，并存入父节点集合中；(3)定义栅格地图中障碍物区域或位置区域内像素点的像素状态为黑色，并在障碍物区域或位置区域内像素点的坐标基础上以半径r的形式进行扩张，扩张得到的区域像素状态定义为黑色；(4)在所述搜索范围内采用RRT算法进行栅格地图遍历。本发明通过对栅格地图进行膨胀处理，减少了地图中不必要的特征，即使在特征不明显得区域也可进行膨胀，并在RRT探索过程中碰撞检测阶段将膨胀后的特征作为检测对象，可完美解决漏检测现象。

说明书

技术领域

本发明涉及机器人技术领域，尤其涉及一种基于RRT的栅格地图遍历算法。

背景技术

目前基于RRT对栅格地图进行探索的策略是从父节点开始，在其周围随机生成相应的一系列子节点，并依次对其进行碰撞检测与距离计算，从而得到最合适的子节点，并将该子节点与父节点连接，加入到整个树状图中。在该过程中，进行碰撞检测的方式是将当前新生成的子节点与父节点连线，以一定的步长来遍历这条线上的各点，查看是否存在这条线上的某点位置为黑色像素(障碍物部分)，若存在，则删除连线，放弃该点。在这个过程中，倘若障碍物厚度较小，会存在漏检测现象，使得子节点冲出障碍物边界，造成错误探索的情况。

在碰撞检测的过程中，由于栅格地图是由正方形像素组成，倘若障碍物的厚度较小，并且排列方式非正交，则存在两个正方形以角点连接，此时若碰撞检测的步长设置的不够小，会造成漏检测情况，若碰撞检测的步长过小，会造成算例负荷较大的情况；若给定的栅格地图是通过slam方法建立，针对某些特征较少的障碍物，呈现出来的黑色像素较少，无法完美地描述整个地图的边界处，也会造成碰撞检测中漏检测现象。针对栅格地图，该设计存在鲁棒性较差的问题。

发明内容

发明目的：本发明针对上述不足，提出了一种基于RRT的栅格地图遍历算法，解决漏检测现象。

技术方案：

一种基于RRT的栅格地图遍历算法，包括步骤：

(1)根据待探索栅格地图确定搜索范围；

(2)在步骤一确定的搜索范围内以机器人所在位置作为起点，以该起点为根节点，并存入父节点集合中；

(3)定义栅格地图中障碍物区域或位置区域内像素点的像素状态为黑色，并在障碍物区域或位置区域内像素点的坐标基础上以半径r的形式进行扩张，扩张得到的区域像素状态定义为黑色；

(4)在所述搜索范围内采用RRT算法进行栅格地图遍历。

所述步骤(1)中搜索范围的确定如下：

将机器人放置于未知区域后，机器人原地旋转360°，扫描出当前环境地图；并得到当前地图的长x_map和宽y_map，并据此确定该矩形区域为当前搜索范围。

所述步骤(4)具体为：

(41)所述搜索范围内随机生成子节点，并根据其与父节点集合中各根节点的距离找到与其距离最近的根节点，将该根节点与该子节点进行连线作为运动路径；

(42)对步骤(41)得到的连线进行碰撞检测：

若连线上存在像素状态为黑色的像素点，则放弃与该子节点连线的根节点，寻找父节点集合中下一个与该子节点距离最近的根节点并连线，重复本步骤；

若与父节点集合中所有父节点连线上均存在像素状态为黑色的像素点，则放弃该子节点，并返回步骤(41)；

若连线上不存在像素状态为黑色的像素点，则将该子节点作为新的父节点加入父节点集合中，并重复步骤(41)；

(43)搜索次数达到n次后，再连续m次搜索无法得到连线上不存在障碍物或未知区域的新的子节点与根节点的连线，则结束遍历过程；

其中，n与m的设置根据搜索的环境大小进行设置。

所述生成子节点的流程为：

设搜索范围的长宽分别为x_map,y_map，新生成的子节点坐标为x_new(x_rand,y_rand)；

则有以下关系：

x_rand＝drand()*x_map

y_rand＝drand()*y_map

其中drand()函数为随机生成一个0～1之间的数，故得到新的未连线的子节点坐标x_new。

栅格地图中根据机器人的探测之后得到其中各个像素点对应的像素状态，所述像素状态分为三种，具体由-1、0、1来表示，其中-1代表未知区域，0代表未被占据区域，1代表被占据区域，且像素状态为0的像素点呈现白色，像素状态为1的像素点呈现黑色，像素状态为-1的像素点呈现浅绿色。

有益效果：本发明通过对栅格地图进行膨胀处理，减少了地图中不必要的特征，充分地将地图形成封闭环境，即使在特征不明显得区域也可进行膨胀，并在RRT探索过程中碰撞检测阶段将膨胀后的特征作为检测对象，可完美解决漏检测现象。

附图说明

图1为遍历环境的流程图。

图2为当栅格地图中障碍物边界较薄的时候，碰撞检测可能出现漏检测的现象图。

图3为未做膨胀的栅格地图。

图4为做膨胀后的栅格地图。

图5为做膨胀后搜索过程中的地图遍历效果图。

具体实施方式

下面结合附图和具体实施例，进一步阐明本发明。

图1为遍历环境的流程图，如图1所示，本发明基于RRT的改进栅格地图遍历算法包括如下步骤：

步骤一、确定搜索范围；

根据机器人要探索的栅格地图确定搜索范围；

将机器人放置于未知区域后，机器人首先原地旋转360°，扫描出当前环境地图的雏形，由此时地图的长宽(x_map,y_map)确定一个矩形区域为当前搜索范围。在地图不断建立的过程中，x_map与y_map在不断增大，矩形搜索区域随之也在不断增大。

步骤二、在步骤一确定的搜索范围内以机器人所在位置作为起点，以该起点作为根节点，存入数组V中，数组V即为父节点集合；

即以机器人初始位置创建第一个父节点；

步骤三、在步骤(1)的搜索范围内生成一个随机点，作为子节点，并按照该子节点到数组V中各个根节点的距离找到距离该子节点最近的根节点，将该根节点与该子节点进行连线，在探索过程中，不断生成新的子节点与父节点，形成无规律蛛网状，被覆盖区域则为已探索区域，直至当前环境全部被全部覆盖；本发明中，该子节点到数组V中各个根节点的距离采用的是欧式距离；

生成子节点的流程为：

设当前栅格地图(即搜索范围)的长宽分别为x_map,y_map，新生成的子节点坐标为x_new(x_rand,y_rand)。

则有以下关系：

x_rand＝drand()*x_map

y_rand＝drand()*y_map

其中drand()函数为随机生成一个0～1之间的数，故得到新的未连线的子节点坐标x_new；

步骤四、对步骤三的连线进行碰撞检测，若连线上不存在任何障碍物，则将该子节点加入数组V中，作为根节点；

碰撞检测的具体流程：

栅格地图也称概率栅格地图，即地图中每个像素都有一个对应的概率值(0～100)。概率值趋近于0的像素呈现白色(未被占据区域)，概率值趋近于100的像素呈现黑色(被占据区域)，概率值为-1的像素呈现浅绿色(未知区域)。在搜索算法中，为了更加清晰地表示地图中各个像素的状态，将概率值大于90的像素重置为1，将概率值低于90的像素重置为0，概率值为-1的像素不变。则此时栅格地图的表征形式为-1代表未知区域，0代表未被占据区域，1代表被占据区域。即像素状态为1，表示该处存在障碍物，像素状态为0，表示该处为空闲区域，无障碍物，像素状态为-1，则代表该处未被探索，无法确定是否存在障碍物。

在进行碰撞检测的过程中，将连接的线以某个步长进行均匀划分，得到连线上的均匀分布的若干点，遍历这些点并判断这些点处在栅格地图中对应像素状态，若该连线各点中存在某点所处像素状态为-1和1，则放弃该条连线，即为在该两点连线中存在障碍物或未知区域，无法形成安全路径；

针对上述遍历流程，在遍历栅格地图的情况下，如图3，即若处在黑色像素点较少的区域，如图2，在进行碰撞检测的过程中，步长通常设为小于等于当前栅格地图的像素尺寸，若步长设置不够小，则会出现漏检测的情况，若步长设置过小，则会出现算力负荷过大的情况。

故本发明采用对栅格地图膨胀的方法进行碰撞检测，如图4，将其中像素状态为1的各个像素点在其坐标上进行以半径r的形式进行扩张，扩张之后的区域像素形式均为黑色，即放大了原先黑色像素点所在的部分，如图4，这样使得减少了栅格地图中的特征，避免了由于碰撞检测中的步长偏大造成漏检测的情况。通过膨胀障碍物之后，再对步骤三得到的连线进行碰撞检测，在遍历栅格地图时可以更加准确地进行对可通行的环境遍历；

步骤五、若连线上不存在障碍物或未知区域，则将该子节点作为新的父节点加入数组V中，并返回步骤三；若连线上存在障碍物或未知区域，则放弃与该根节点的连线，寻找数组V中下一个距离最近的根节点并连线，并重复本步骤；若与数组V中所有根节点连线均存在障碍物或未知区域，则放弃该子节点，重新随机生成下一个子节点；步骤六、搜索次数达到n次后，再连续m次搜索无法得到连线上不存在障碍物或未知区域的新的子节点与根节点的连线，结束遍历过程。

其中，n与m的设置根据搜索的环境大小进行设置，即环境大的话，m与n对应设置较大，环境小的话，m与n对应设置较小。

以上详细描述了本发明的优选实施方式，但是本发明并不限于上述实施方式中的具体细节，在本发明的技术构思范围内，可以对本发明的技术方案进行多种等同变换(如数量、形状、位置等)，这些等同变换均属于本发明的保护范围。