CN108827309A - 一种机器人路径规划方法及具有它的吸尘器 - Google Patents

Abstract

本发明提供了一种机器人路径规划方法及具有它的吸尘器，包括提取2D地图中机器人可行走的有效区域，并对有效区域进行栅格化划分的步骤；连接栅格中点，生成树路径，机器人根据树路径，进行无目标行走或目标性行走的步骤。本发明的机器人路径规划方法，能够使得机器人在无目标时快速、全面历遍整个有效区域，还能够在有行走目标时快速、精准计算出机器人至目标的最短路径。本路径规划方法应用于扫地机器人时，能够快速让扫地机器人打扫完整个有效区域，且实现了扫地机器人的目标性清扫。

Description

一种机器人路径规划方法及具有它的吸尘器

技术领域

本发明涉及智能机器人领域，具体涉及一种机器人路径规划方法及具有它的吸尘器。

背景技术

路径规划是实现行走机器人控制的关键技术之一。其目的是在一定的环境条件和性能指标要求下，寻找一条从起始位置到目标位置的最优或次优的安全无碰撞路径。针对机器人路径规划，国内外学者提出了许多规划方法，其中主要有人工势场法、神经网络自适应规划法、遗传算法、蚁群算法、粒子群算法等。近年来，越来越多的学者在对路径规划问题研究时更注重多种智能算法相结合，以提高算法性能。如ImenChaari*等将遗传算法和蚁群算法相结合，前阶段用遗传算法产生初始信息素分布，后阶段用蚁群算法求最优解，能够有效结合两算法的优点，提高蚁群的搜索效率，但可能陷入局部最优；X Wang等人提出一种基于粒子群优化(Particle Swarm Optimization，PSO)和蚁群优化(Ant colonyoptimization，ACO)算法的新型路径规划方法，该算法利用粒子群环境建模的方法，生成从起始点到目标点的路径，然后基于之前生成的路径分布信息素，最后，使用改进的优化蚁群来找到最佳路径，该方法可以缩短搜索时间，但对环境要求较高，适应性差；T Zhu，G Dong等提出将蚁群算法与人工势场法结合使用的算法，该算法用势场法初始化总体路径，优化每一代蚂蚁的路径排序，并根据蚂蚁路径的排序更新信息素，同时，在精英蚂蚁的信息素的帮助下，在每个生成路径上使用模因算法的交叉和变异操作，该算法提高了收敛速度和稳定性，但势场法本身容易陷入局部死锁，所以该算法在初始寻找路径时容易陷入局部最优。

申请号为201310604565.6的中国专利，公开了一种无线传感器网络中基于正六边形的移动锚节点路径规划方法，所述网络包括多个静止的未知节点和一个移动的锚节点，其步骤包括：行走锚节点以恒定速度v移动，每隔时间间隔t，以此刻所在位置为圆心，R为通信半径，广播信标信息，信标信息包括该时刻行走锚节点的位置和信标ID，行走锚节点的行走路径为正六边形。在行走蜂窝网络、ZigBee网络等通信技术领域，均存在这种以正六边形为最基本栅格的路径规划算法。

申请号为201410497805.1的中国专利公开了一种机器人静态路径规划方法，包括：设定目标点，以目标点为终点，在地图范围内建立人工势场；引入粒子群算法，在机器人的起点设有数量为m的粒子群，第i个粒子在第t步的飞行速度为按照人工势场并结合粒子群算法对每个粒子从起点到终点的路径进行模拟行走，在模拟行走的过程中，每个粒子形成各自的运动轨迹；大部分粒子逐渐向多条轨迹中的一条轨迹聚拢收敛，进而在地图范围内得到从起点到终点的最优行走路径；机器人最终按照最优行走路径，完成从起点到终点的运动过程。其将势场法、栅格法和粒子群法结合起来，但其算法复杂，路径规划效率低，迫切需要加以改进。

发明内容

为解决上述问题，本发明提供了一种机器人路径规划方法及具有它的吸尘器。本发明的机器人路径规划方法，能够使得机器人在无目标时快速、全面历遍整个有效区域，还能够在有行走目标时快速、精准计算出机器人至目标的最短路径。本路径规划方法应用于扫地机器人时，能够快速让扫地机器人打扫完整个有效区域，且实现了扫地机器人的目标性清扫。

为实现所述技术目的，本发明的技术方案是：一种机器人路径规划方法，包括以下步骤：

S1：提取2D地图中机器人可行走的有效区域，并对有效区域进行栅格化划分；

S2：连接栅格中点，生成树路径，机器人根据树路径，进行无目标行走或目标性行走。

进一步，所述步骤S1中提取2D地图中机器人可行走的有效区域的方法包括以下步骤：

T1：机器人采用避障算法行走整个环境，利用深度摄像头建立环境的3D模型；

T2：提取步骤T1中的3D模型底面作为有效区域；

优选的，所述步骤S1中提取有效区域的方法包括以下步骤：

E1：机器人利用深度摄像头判断障碍，从起始点起，贴近障碍延边行走，且以起始点为目标，最终回到起始点，并标注行走路线和障碍；

E2：计算步骤E1中行走路线的闭合区间，并去除标记障碍处的闭合区间，得到有效区域。

进一步，所述步骤E3中计算行走路线闭合区间的方法为：计算行走路线的二阶导数，并计算其在整个区间内的连续性，若二阶导数连续则行走路线闭合。

进一步，所述步骤S1中栅格化划分的方法为，以机器人所在处生成起始正六边形，在有效区域内，向起始正六边形外生长彼此相接的正六边形。

优选的，所述起始正六边形和所述正六边形大小相同，且不大于机器人外周向的外接圆。

进一步，所述步骤S2中无目标行走的方法包括以下步骤：

P1：对步骤S2中生成的树路径进行等级划分，以所述起始正六边形外接的正六边形作为一级树路径，以一级树路径外接的正六边形作为二级树路径，直至划分至所述树路径末端；

P2：从起始正六边形起向前行走，每次行走历遍每级树路径。

进一步，所述步骤S2中目标性行走的方法包括以下步骤；

D1：以起始正六边形中心为起点，做起始正六边形中心至目标所在六边形中心的第一向量；

D2：判断第一向量是否完全处于有效区域内，若有效区域完全包含第一向量则机器人直线行走至目标，否则第一向量与有效区域至少存在两个交点，并进行步骤D3；

D3：计算距离起始正六边形中心较近的第一交点、另一交点做为第二交点，机器人直线行走至第一交点附近的正六边形中心，沿第一交点至第二交点中间的树路径行走至第二交点后，直线行走至目标。

进一步，所述步骤D3中沿第一交点至第二交点中间的树路径行走至第二交点的方法为：

在第一交点附近的正六边形中心处做向各个相邻正六边形中心的第二向量；判断第二向量与第一向量的夹角，选择夹角较小的向量行走至第二交点位置；

或，机器人预先罗列第一交点至第二交点之间所有树路径，并计算最短的树路径，机器人沿最短的树路径行走至第二交点。

一种吸尘器，包括所述机器人路径规划方法，采用该方法进行无目标清扫或目标性清扫。

本发明的有益效果在于：

本发明的机器人通过深度摄像头能够快速可靠的计算出机器人行走的有效区域，并利用正六边形栅格化，基于栅格中点连线生成树路径，结合栅格化的精度，进一步确保了机器人在进行无目标性行走时，路径能覆盖整个有效区域。其次，基于树路径及其等级划分的方法，本发明的机器人能够通过夹角或路径罗列法、快速计算出机器人至目标的最短路径。

综上，本发明的机器人路径规划方法，能够使得机器人在无目标时快速、全面历遍整个有效区域，还能够在有行走目标时快速、精准计算出机器人至目标的最短路径。本路径规划方法应用于扫地机器人时，能够快速让扫地机器人打扫完整个有效区域，且实现了扫地机器人的目标性清扫。

附图说明

图1是本发明的机器人路径规划方法的流程图；

图2是本发明生成树路径及等级划分的方法示意图；

图3是本发明的机器人无目标行走方法示意图；

图4是本发明的机器人目标性行走的实施方法之一；

图5是本发明的机器人目标性行走的实施方法之二。

具体实施方式

下面将对本发明的技术方案进行清楚、完整地描述。

需要说明的是，本发明中的“内”是指紧靠机器人起始点，“外”是指远离机器人起始点，及本发明的“外周”等方位用语均是为了充分说明本发明的路径规划方法，并不能理解为对本发明的限定。

如图1所示，一种机器人路径规划方法，包括以下步骤：

S1：提取2D地图中机器人1可行走的有效区域，并对有效区域进行栅格化划分；

S2：连接栅格中点，生成树路径，机器人根据树路径，进行无目标行走或目标性行走。

进一步，所述步骤S1中提取2D地图中机器人可行走的有效区域的方法包括以下步骤：

T1：机器人1采用避障算法行走整个环境，利用深度摄像头建立环境的3D模型；其中避障算法是本领域技术人员容易获得的通用技术手段，在此不做赘述。

T2：提取步骤T1中的3D模型底面作为有效区域；需要说明的是，对于存在障碍的地方，机器人只能建立障碍的3D图像，并不能扫描到地面，故深度摄像头建立环境的3D模型中，能扫描到地面部分为3D模型底面，机器人以底面作为其能行走的有效区域。或将步骤T1中的3D模型向地投影，在投影中剔除障碍投影部分即为有效区域。

优选的，所述步骤S1中提取有效区域的方法包括以下步骤：

E1：机器人利用深度摄像头判断障碍，从起始点起，贴近障碍延边行走，且以起始点为目标，最终回到起始点，并标注行走路线和障碍；

E2：计算步骤E1中行走路线的闭合区间，并去除标记障碍处的闭合区间，得到有效区域。也就是说，在实施例中，若机器人能够障碍一周形成闭合区间，在去除该闭合区间后的闭合区间，则为机器人能够行走的最大有效区域，且该有效区域为机器人行走路线的边缘化区域内部。采用本实施例所计算出的有效区域，具有计算速度快，可靠性高的优点。

进一步，所述步骤E3中计算行走路线闭合区间的方法为：计算行走路线的二阶导数，并计算其在整个区间内的连续性，若二阶导数连续则行走路线闭合。

进一步，所述步骤S1中栅格化划分的方法为，以机器人1在处生成起始正六边形2在有效区域内，向起始正六边形外生长彼此相接的正六边形。如图2所示，在起始正六边形2的六边外分别生长第一圈正六边形，第一圈正六边形外继续生长第二圈正六边形，若正六边形于所述有效区域的边缘重叠，则停止改方向的生长，直至正六边形完全覆盖有效区域。具体的，如图3-5所示，是一种利用正六边形栅格化出的一种有效区域的示意图。

优选的，所述起始正六边形和所述正六边形大小相同，且不大于机器人外周向的外接圆，进一步在确保机器人路径能覆盖整个有效区域的情况下，确立了栅格化的精度。

进一步，所述步骤S2中无目标行走的方法包括以下步骤：

P1：对步骤S2中生成的树路径进行等级划分，以所述起始正六边形外接的正六边形作为一级树路径，以一级树路径外接的正六边形作为二级树路径，直至划分至所述树路径末端；

P2：从起始正六边形起向前行走，每次行走历遍每级树路径。如图3所示的栅格化的区域内，第一圆弧5穿过的所有正六边形是从起始正六边形2生长出来的第一圈正六边形，故应机器人至第一圈正六边形中心为一级树路径，同理，第二圆弧6穿过的是第二圈正六边形，故机器人从第一圈正六边形中心至第二圈为二级树路径。机器人1从起始点起，首先沿着第一圆弧5历遍一级树路径，接着行走至二级树路径并历遍，完成无目标行走的任务。需要说明的是，本发明的机器人还可以从起始点起，一边进行步骤S1中的提取有效区域和栅格化划分步骤，一边沿每次步进后生成的树路径前进，从而作为一种新的避障算法。或者说本发明的机器人能够根据深度摄像头判断障碍，进一步计算有效区域，并在深度摄像头可视范围内生长树路径，进一步使得机器人避开障碍，且快速历遍整个有效区域。

进一步，所述步骤S2中目标性行走的方法包括以下步骤；

D1：以起始正六边形2中心为起点，做起始正六边形中心至目标9所在六边形中心的第一向量7；

D2：判断第一向量7是否完全处于有效区域内，如图4所示，若有效区域完全包含第一向量则机器人直线行走至目标，否则第一向量与有效区域至少存在两个交点，并进行步骤D3；

D3：计算距离起始正六边形中心较近的第一交点、另一交点做为第二交点，机器人直线行走至第一交点附近的正六边形中心，沿第一交点至第二交点中间的树路径行走至第二交点后，直线行走至目标。或者说，本发明的机器人无法直线到达目标时，首先直线到达有效区域边缘(第一交点)，再利用正六边形栅格化，生成树路径并进行等级划分，判断目标或第二交点所在树路径的等级，机器人根据等级差n，沿着树路径行走n步到达目标或第二交点。

进一步，所述步骤D3中沿第一交点至第二交点中间的树路径行走至第二交点的方法为：

如图5所示，在第一交点附近的正六边形中心处做向各个相邻正六边形中心的第二向量8；判断第二向量8与第一向量7的夹角，选择夹角较小的向量行走至第二交点位置；或者说，本发明中通过判断第一交点下一级树路径与目标的方向，选择方向最近的树路径前进，从而有方向的前进至目标。

或，机器人预先罗列第一交点至第二交点之间所有树路径，并计算最短的树路径，机器人沿最短的树路径行走至第二交点。不管采用向量夹角方式或树路径罗列方式，最终计算出的最短路径为相同步数的最短路径，本发明目标性的规划路径方法，能够快速找到机器人至目标点的最短路径。

一种吸尘器，包括所述机器人路径规划方法，采用该方法进行无目标清扫或目标性清扫。

对于本领域的普通技术人员来说，在不脱离本发明创造构思的前提下，还可以做出若干变形和改进，这些都属于本发明的保护范围。

Claims (10)

1.一种机器人路径规划方法，其特征在于，包括以下步骤：

S1：提取2D地图中机器人可行走的有效区域，并对有效区域进行栅格化划分；

S2：连接栅格中点，生成树路径，机器人根据树路径，进行无目标行走或目标性行走。

2.根据权利要求1所述的机器人路径规划方法，其特征在于，所述步骤S1中提取2D地图中机器人可行走的有效区域的方法包括以下步骤：

T1：机器人采用避障算法行走整个环境，利用深度摄像头建立环境的3D模型；

T2：提取步骤T1中的3D模型底面作为有效区域。

3.根据权利要求1所述的机器人路径规划方法，其特征在于，所述步骤S1中提取有效区域的方法包括以下步骤：

E1：机器人利用深度摄像头判断障碍，从起始点起，贴近障碍延边行走，且以起始点为目标，最终回到起始点，并标注行走路线和障碍；

E2：计算步骤E1中行走路线的闭合区间，并去除标记障碍处的闭合区间，得到有效区域。

4.根据权利要求3所述的机器人路径规划方法，其特征在于，所述步骤E3中计算行走路线闭合区间的方法为：计算行走路线的二阶导数，并计算其在整个区间内的连续性，若二阶导数连续则行走路线闭合。

5.根据权利要求1所述的机器人路径规划方法，其特征在于，所述步骤S1中栅格化划分的方法为，以机器人所在处生成起始正六边形，在有效区域内，向起始正六边形外生长彼此相接的正六边形。

6.根据权利要求5所述的机器人路径规划方法，其特征在于，所述起始正六边形和所述正六边形大小相同，且不大于机器人外周向的外接圆。

7.根据权利要求5所述的机器人路径规划方法，其特征在于，所述步骤S2中无目标行走的方法包括以下步骤：

P1：对步骤S2中生成的树路径进行等级划分，以所述起始正六边形外接的正六边形作为一级树路径，以一级树路径外接的正六边形作为二级树路径，直至划分至所述树路径末端；

P2：从起始正六边形起向前行走，每次行走历遍每级树路径。

8.根据权利要求5所述的机器人路径规划方法，其特征在于，所述步骤S2中目标性行走的方法包括以下步骤；

D1：以起始正六边形中心为起点，做起始正六边形中心至目标所在六边形中心的第一向量；

D2：判断第一向量是否完全处于有效区域内，若有效区域完全包含第一向量则机器人直线行走至目标，否则第一向量与有效区域至少存在两个交点，并进行步骤D3；

D3：计算距离起始正六边形中心较近的第一交点、另一交点做为第二交点，机器人直线行走至第一交点附近的正六边形中心，沿第一交点至第二交点中间的树路径行走至第二交点后，直线行走至目标。

9.根据权利要求8所述的机器人路径规划方法，其特征在于，所述步骤D3中沿第一交点至第二交点中间的树路径行走至第二交点的方法为：

在第一交点附近的正六边形中心处做向各个相邻正六边形中心的第二向量；判断第二向量与第一向量的夹角，选择夹角较小的向量行走至第二交点位置；

或，机器人预先罗列第一交点至第二交点之间所有树路径，并计算最短的树路径，机器人沿最短的树路径行走至第二交点。

10.一种吸尘器，其特征在于，包括权利要求1-9任一项所述的一种机器人路径规划方法。