一种骨架重构Voronoi路径规划方法、装置、设备及介质

一种骨架重构voronoi路径规划方法、装置、设备及介质
技术领域
1.本发明属于机器人建图定位导航技术领域，具体涉及一种骨架重构voronoi路径规划方法、装置、设备及介质。


背景技术：

2.voronoi图方法在众多科学领域得到了广泛应用，许多科研工作者利用voronoi方法构建拓扑地图，用以减少计算量，提高机器人运动的实时性。voronoi图法就是先生成voronoi图，然后将机器人的起始点和目标点连接到voronoi图上，每次规划时利用图搜索法找出包括起始点和目标点在内的全局最短路径。与栅格法相比，这种方法在路径搜索时计算量减少，路径远离障碍物，安全性较高。但是原始voronoi方法对于不理想的环境生成的全局路径冗余、路径不平滑，依据voronoi地图进行路径规划的实时性不好，不适合机器人的导航运动。


技术实现要素：

3.根据现有技术的不足，本发明的目的是提供一种骨架重构voronoi路径规划方法、装置、设备及介质，能够生成更加精简笔直的骨架，生成更加适合机器人导航运动的路径，实时性强。
4.为了解决上述技术问题，本发明采用的技术方案为：
5.一种骨架重构voronoi路径规划方法，包括以下步骤：
6.机器人实时采集方位及距离数据并对其进行处理后生成基于voronoi图的第一骨架且提取关键节点；
7.依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架；
8.根据第二骨架进行逆向优化出第三骨架，实现骨架重构；
9.基于第三骨架进行全局路径搜索与路径平滑。
10.进一步地，控制机器人在室内运动，实时采集室内物体与机器人的距离和方向角，通过建图处理得到环境栅格地图；
11.将环境栅格地图预处理后，形成新的地图，预处理包括对环境栅格地图二值化、开运算及简化；
12.遍历新的地图中所有像素值不为零的像素点，生成基于voronoi图的第一骨架。
13.进一步地，对于新的地图中的像素点，将黑色的像素点赋值为0，白色的像素点赋值为1，将每一个像素点p1上方的像素点设为p2，由p2绕p1顺时针依次设定p1周围的八邻域为p2-p9；
14.其中，按照顺指针或逆时针顺序遍历每一个像素点p1周围的八邻域p2-p9，将一个邻域到另一个邻域值由0变为1的次数计为a，每个像素点px的八邻域中非0的像素点的数量为bx，x∈[1,9]；
[0015]
若某一个像素点周围的八邻域不完整，则不对该像素点进行遍历操作，将满足
[0016]
2≤b1≤6、a＝1、p2
·
p4
·
p8＝0或b2≠1及p2
·
p4
·
p6＝0或b4≠1的像素点p1赋值为0后形成黑色像素点；
[0017]
遍历新的地图中的所有像素点后根据赋值为0的黑色像素点生成基于voronoi的第一骨架。
[0018]
进一步地，在生成的基于voronoi的第一骨架提取关键节点，关键节点包括端节点和分支节点，依次遍历每一个骨架点n1，并根据其八邻域n2-n9值的和进行关键节点判断；
[0019]
将满足n2+n3+n4+n5+n6+n7+n8+n9＝1的骨架点n1确定为端节点：
[0020]
将满足n1+n3+n5+n7＝3或n2+n4+n6+n8＝3或n1+n3+n6＝3或n1+n4+n6＝3或n1+n4+n7＝3或n2+n4+n7＝3或n2+n5+n7＝3或n2+n5+n8＝3或n3+n5+n8＝3或n3+n6+n8＝3的骨架点n1确定为分支节点；
[0021]
将所有端节点和分支节点在第一骨架上标注出来。
[0022]
进一步地，依次选择第一骨架上具有连接关系的第一关键节点和第二关键节点，由第一关键节点向第二关键节点发出射线，若第一关键节点和第二关键节点间无障碍物则直接到达第二关键节点，将射线经过的路径作为再生成的第二骨架，反之，记录射线与障碍物的碰撞点；
[0023]
找到碰撞点邻域内无障碍物覆盖且与第二关键节点曼哈顿距离最小的点作为子目标点，若此时同时存在两个子目标点，则优先选择与原始骨架延展方向相同的点作为子目标点；
[0024]
将找出的子目标点向目标点发出射线，若与障碍物碰撞，则记录该碰撞点；
[0025]
继续找寻子目标点，直到找到发出射线与第二关键节点不发生障碍物碰撞的子目标点，将该子目标点邻域内无障碍物覆盖且与障碍物保持相对安全距离的子目标点作为最终的子目标点，将第一关键节点、多个子目标点和第二关键节点依次连接作为第一最短路径；
[0026]
遍历第一骨架的路径上所有相邻的关键节点直至获取所有第一最短路径，所述所有第一最短路径组成第二骨架。
[0027]
进一步地，以第二关键节点为发射点，依次向子目标点发出射线；
[0028]
若发出的射线上存在障碍物，则将接收该射线子目标点删除，若发出的射线上不存在障碍物，则将接收该射线子目标点保留，且将该子目标点作为最优子目标点；
[0029]
将第一关键节点、最优子目标点和第二关键节点之间的连线作为第二最短路径；
[0030]
遍历第二骨架的路径上所有相邻的关键节点直至获取所有第二最短路径，所述所有第二最短路径组成第三骨架。
[0031]
进一步地，基于第三骨架进行全局路径搜索的方法为：
[0032]
获取第三骨架上的第一点，所述第一点与给定位置的距离最近且两者间无障碍物，将给定位置和第三骨架上的第一点连接作为全局路径的第一部分；
[0033]
获取第三骨架上的第二点，所述第二点与目标位置的距离最近且两者间无障碍物，将目标位置和第三骨架上的第二点连接作为全局路径的第二部分；
[0034]
搜索第三骨架上第一点和第二点之间的最短路径作为全局路径的第三部分；
[0035]
将第一部分、第二部分和第三部分连接后组成全局路径。
[0036]
一种骨架重构voronoi路径规划装置，包括以下步骤：
[0037]
第一骨架生成模块，用于机器人实时采集方位及距离数据并对其进行处理后生成基于voronoi图的第一骨架且提取关键节点；
[0038]
第二骨架生成模块，用于依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架；
[0039]
第三骨架生成模块，用于根据第二骨架进行逆向优化出第三骨架，实现骨架重构；
[0040]
全局路径搜索与路径平滑处理模块，用于基于第三骨架进行全局路径搜索与路径平滑。
[0041]
一种骨架重构voronoi路径规划设备，包括处理器和用于存储能够在处理器上运行计算机程序的存储器，处理器用于运行计算机程序时，执行上述任一项骨架重构voronoi路径规划方法的步骤。
[0042]
一种计算机存储介质，存储介质中存储有计算机程序，计算机程序被处理器执行时，实现上述任一项骨架重构voronoi路径规划方法的步骤。
[0043]
与现有技术相比，本发明具有以下优点和有益效果：
[0044]
本发明提供的一种骨架重构voronoi路径规划方法、装置、设备及介质，能够在弯曲的基于voronoi图的第一骨架上找出关键节点，将这些关键节点进行重新连接，避开障碍物，生成更加精简笔直的骨架，进而进行逆向优化，实现骨架重构，最后进行全局路径搜索与路径平滑，便于生成更加适合机器人导航运动的路径，实时性强。
附图说明
[0045]
此处所说明的附图用来提供对本发明的进一步理解，构成本技术的一部分。本发明的示意性实施例及其说明用于解释本发明，并不构成对本发明的不当限定。在附图中：
[0046]
图1为本发明骨架重构voronoi路径规划方法的实施流程图。
[0047]
图2为本发明环境栅格地图构建图。
[0048]
图3为本发明环境栅格地图二值化与开运算图。
[0049]
图4为本发明地图简化的过程图。
[0050]
图5为本发明新的地图中每个像素点的八邻域图。
[0051]
图6(a)为预处理和简化前生成的基于voronoi的第一骨架图。
[0052]
图6(b)为预处理和简化后生成的基于voronoi的第一骨架图。
[0053]
图7为本发明第一骨架上的点的八邻域图。
[0054]
图8为本发明生成的第一骨架的关键节点图。
[0055]
图9为本发明射线模型示意图。
[0056]
图10为本发明第二骨架搜索图。
[0057]
图11为本发明逆向优化过程图。
[0058]
图12为本发明第三骨架生成图。
[0059]
图13为本发明全局路径搜索图。
[0060]
图14(a)为复杂场景下原始voronoi路径规划方法生成的骨架示意图。
[0061]
图14(b)为复杂场景下预处理后voronoi路径规划方法生成的骨架示意图。
[0062]
图14(c)为复杂场景下关键节点提取后voronoi路径规划方法生成的骨架示意图。
[0063]
图14(d)为本发明复杂场景下原始voronoi路径规划方法生成的骨架示意图。
具体实施方式
[0064]
为了便于本领域普通技术人员理解和实施本发明，下面结合附图及实施例对本发明作进一步的详细描述，应当理解，此处所描述的实施示例仅用于说明和解释本发明，并不用于限定本发明。
[0065]
第一实施例
[0066]
本发明提供一种骨架重构voronoi路径规划方法，如图1所示，包括以下步骤：
[0067]
步骤1、控制机器人在室内运动，机器人实时采集方位及距离梳理并对其进行处理后生成生成基于voronoi图的第一骨架且提取关键节点；
[0068]
步骤2、依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架；
[0069]
步骤3、根据第二骨架进行逆向优化出第三骨架，实现骨架重构；
[0070]
步骤4、基于第三骨架进行全局路径搜索与路径平滑。
[0071]
相关技术中，原始voronoi算法对于不理想的环境生成的全局路径冗余、路径不平滑，依据voronoi地图进行路径规划的实时性不好，不适合机器人的导航运动。本发明能够在弯曲的基于voronoi图的第一骨架上找出关键节点，将这些关键节点进行重新连接，避开障碍物，生成更加精简笔直的骨架，进而进行逆向优化，实现骨架重构，最后进行全局路径搜索与路径平滑，便于生成更加适合机器人导航运动的路径，实时性强。
[0072]
通常而言，机器人的轮式移动结构主要包括三种类型：全向移动结构、四轮独立转向驱动结构和两轮差速驱动结构，它们各有优缺点。全向移动结构不需要机器人本体做出任何转动便可实现任意方向的移动，并且可以原地旋转任意角度，能在任意位姿下向任何目标位置运动，每个驱动轮只需要安装一个电机就能满足要求，整体结构简单，适用于室内环境；四轮独立转向驱动结构底盘构造复杂，每个驱动轮需要配备两个电机，其中一个电机用于转向控制，另外一个电机用于驱动控制，总共需要八个驱动电机，整体成本高；两轮差速驱动结构有两个彼此独立工作的驱动轮，共同起到驱动与转向的作用，然后配合万向轮实现任意方向的运动，这种驱动结构构造简单、易于控制，是目前使用最广泛的一种驱动方式，本发明中使用的机器人实验平台驱动方式采用两轮差速驱动模型。
[0073]
具体地，在步骤1中，机器人为圆柱形，机器人底部设有一个万向轮和左右两个驱动轮，万向轮和左右两个驱动轮呈三角布置，中心速度为：
[0074][0075]
其中，vo表示机器人中心速度，v
l
和vr分别为左右两个驱动轮速度，ω
l
和ωr分别为左右两个驱动轮的角速度，通过调节左右两个驱动轮的驱动电机的转速控制左右两个驱动轮速度，进而调节机器人的运动方式。
[0076]
生成基于voronoi图的第一骨架的方法为：
[0077]
控制机器人在室内运动，实时采集室内物体与机器人的距离和方向角，通过建图处理得到环境栅格地图；
[0078]
将环境栅格地图预处理后，形成新的地图，预处理包括对环境栅格地图二值化、开
运算及简化；
[0079]
遍历新的地图中所有像素值不为零的像素点，生成基于voronoi图的第一骨架。
[0080]
如图2所示，为本发明环境栅格地图构建图，通过机器人在室内移动，通过激光雷达传感器实时采集室内物体与机器人的距离、室内物体与机器人的方向角，并传输至处理器，处理器将室内物体与机器人的距离、室内物体与机器人的方向角通过建图处理得到环境栅格地图。
[0081]
在步骤2中，如图3所示，为本发明环境栅格地图二值化与开运算图，对环境栅格地图进行预处理的方法：对环境栅格地图二值化、开运算及简化。
[0082]
具体地，对环境栅格地图二值化的方法为：设置一个像素阈值t，将环境栅格地图中像素值小于t的像素点的像素值变为0、像素值大于t的像素点变为255，并对二值化后的环境栅格地图开运算，去除环境地图中的毛刺和噪点，二值化的环境栅格地图只有黑色像素点和白色像素点。
[0083]
在步骤2中，如图4所示，为本发明地图简化的过程图，环境栅格地图简化的方法为：把障碍物和机器人近似为离散的质点，根据地图中障碍物的形状大小，用每个障碍物的外接圆表示障碍物，并对障碍物的外接圆进行一定程度的膨胀。去除具体的障碍物，以障碍物外接圆的圆心作为障碍物的近似质心，仅保留外接圆膨胀后的抽象区域，并将该区域定为机器人运行的危险区域。
[0084]
若两个外接圆间的距离小于机器人通过的最小安全距离，则将这两个外接圆合并成一个外接圆，简化后的环境地图中仅包含外接圆圆心表示的各个障碍物以及膨胀外接圆表示的危险区域。当两个外接圆满足下述公式时，将两个障碍物合并为一个障碍物，两个障碍物的两个外接圆合并成一个外接圆：
[0085]oij
《ri+rj+r
[0086]
其中，o
ij
表示两个外接圆圆心间的直线距离，ri和rj表示两个外接圆的半径，r表示机器人运动的安全距离。
[0087]
在步骤3中，对于二值化后的地图中的像素点，将黑色的像素点赋值为0，白色的像素点赋值为1，如图5所示，为本发明新的地图中每个像素点的八邻域图，将每一个像素点p1上方的像素点设为p2，由p2绕p1顺时针依次设定p1周围的八邻域为p2-p9；
[0088]
按照顺指针或逆时针顺序遍历每一个像素点p1周围的八邻域p2-p9，将一个邻域到另一个邻域值由0变为1的次数计为a，每个像素点px的八邻域中非0的像素点的数量为bx，x∈[1,9]，若某一个像素点周围的八邻域不完整，则不对该像素点进行遍历操作，将满足2≤b1≤6、a＝1、p2
·
p4
·
p8＝0或b2≠1及p2
·
p4
·
p6＝0或b4≠1的像素点p1赋值为0后形成黑色像素点，遍历新的地图中的所有像素点后根据赋值为0的黑色像素点生成基于voronoi的第一骨架。
[0089]
在本发明的一个具体实施例中，如图6(a)所示，为原始地图生成的骨架，如图6(b)所示，为预处理和简化后的新的地图生成的骨架，可以看出，本发明能够去除环境地图中的毛刺和噪点，且生成的基于voronoi的第一骨架更加平滑，另外，本发明将障碍物膨胀后，机器人在运动过程中，不容易与障碍物相撞。
[0090]
在步骤3中，如图7所示，在基于voronoi图的第一骨架上提取关键节点，将黑色像素点赋值为0，白色像素点赋值为1，将每一个第一骨架上点n1上方的点设为n2，由n2绕n1顺
时针依次设定n1周围的八邻域为n2-n9，依次遍历每一个第一骨架上的点n1，并根据其八邻域n2-n9值的和进行关键节点判断，将满足下述条件的第一骨架上的点n1确定为端节点：
[0091]
n2+n3+n4+n5+n6+n7+n8+n9＝1；
[0092]
将满足下述条件的第一骨架上的点n1确定为分支节点：
[0093]
n1+n3+n5+n7＝3或n2+n4+n6+n8＝3或n1+n3+n6＝3或n1+n4+n6＝3或n1+n4+n7＝3或n2+n4+n7＝3或n2+n5+n7＝3或n2+n5+n8＝3或n3+n5+n8＝3或n3+n6+n8＝3
[0094]
找出基于voronoi图的第一骨架上的全部关键节点，将端节点和分支节点在基于voronoi图的第一骨架上标注出来，如图7所示，为第一骨架上的点的八邻域图，如图8所示，为生成的第一骨架的关键节点图。
[0095]
其中，关键节点中，端节点指的是骨架末端处的点，通常处于环境边界处；分支节点指的是骨架分叉处的点。
[0096]
在步骤4中，生成第二骨架的方法为：处理器进行基于射线模型的骨架重构，利用射线模型原理，如图9所示，为射线模型示意图，在第一骨架上的路径上，将其中一个关键节点作为起始点，与该关键节点相邻的下一个关键节点作为目标点，由起始点向目标点发射一条射线，当起始点或目标点中间没有障碍物时可以直接到达，当起始点或目标点中间有障碍物时可以得到障碍物阻碍射线穿越的位置，以启发式的方法通过射线找出起始点向目标点之间不存在障碍物的最短路径，直到遍历完第一骨架的路径上所有相邻的关键节点。
[0097]
原始算法生成的骨架曲折、数据量大，若直接利用其进行机器人导航，会产生效率低下、实时性不佳和速度损失多等问题，利用射线模型结合关键点对骨架进行重新生成与优化。
[0098]
如图10所示，为第二骨架搜索图，本发明步骤2具体包括：
[0099]
步骤2.1、依次选择第一骨架上具有连接关系的第一关键节点a和第二关键节点b，第一关键节点a作为起始点，第二关键节点b作为目标点，由第一关键节点a向第二关键节点b发出射线，若第一关键节点a和第二关键节点b间无障碍物则直接到达第二关键节点b，将射线经过的路径作为再生成的第二骨架，反之，记录射线与障碍物的碰撞点；
[0100]
步骤2.2、找到步骤2.1中的碰撞点邻域内无障碍物覆盖且与第二关键节点b曼哈顿距离最小的点作为子目标点，若此时同时存在两个子目标点，则优先选择与原始骨架延展方向相同的点作为子目标点；
[0101]
步骤2.3、将步骤2.2找出的子目标点向目标点发出射线，若与障碍物碰撞，则记录该碰撞点；
[0102]
步骤2.4、重复步骤2.2和步骤3.3，继续找寻子目标点，直到找到发出射线与第二关键节点b不发生障碍物碰撞的子目标点，将该子目标点邻域内无障碍物覆盖且与障碍物保持相对安全距离的子目标点作为最终的子目标点，将第一关键节点a、多个子目标点和第二关键节点b依次连接作为第一最短路径；
[0103]
步骤2.5、遍历第一骨架的路径上所有相邻的关键节点直至获取所有第一最短路径，所述所有第一最短路径组成第二骨架。
[0104]
其中，射线模型使用的直线函数以及遍历步长计算方法如下：
[0105]
[0106][0107]
其中，x和y分别为遍历的节点的横纵坐标，δx和δy分别为横纵坐标的差值，d为遍历的步长；步长d的选择对于能否成功遍历射线经过的所有路径非常重要，并且应该在归一化后进行计算；当步长d为纵坐标的差值时，先计算纵坐标，然后依据新的纵坐标结合直线函数计算得到新的坐标点；当步长d为横坐标的差值时，先计算横坐标，然后依据新的纵坐标结合直线函数计算得到新的坐标点。
[0108]
在本发明的一个具体实施例中，如图8所示，选择第一骨架上具有连接关系的两个关键节点作为第一关键节点a和第二关键节点b，由第一关键节点a向第二关键节点b发出射线，记录射线与障碍物的碰撞点c1，找到碰撞点c1邻域内无障碍物覆盖且与第二关键节点b曼哈顿距离最小的点b1作为子目标点，向第二关键节点b发出射线，记录与障碍物碰撞的碰撞点c2，将碰撞点c2邻域内无障碍物覆盖且与第二关键节点b曼哈顿距离最小的点b2作为子目标点，向第二关键节点b发出射线，记录与障碍物碰撞的碰撞点c3，找到碰撞点c3邻域内无障碍物覆盖且与第二关键节点b曼哈顿距离最小的点b3作为子目标点，向第二关键节点b发出射线，没有与障碍物碰撞，则将b3邻域内无障碍物覆盖且与障碍物保持相对安全距离的子目标点b4作为新的关键节点c。
[0109]
在步骤3中，如图11所示，为逆向优化过程图，根据第二骨架进行逆向优化为：
[0110]
根据生成的第二骨架进行逆向优化，生成从起始点到安全绕开障碍物的新的关键节点再到目标点的新路径，按如下步骤进行：
[0111]
步骤3.1、以第二关键节点b为发射点，依次向子目标点发出射线；
[0112]
步骤3.2、若发出的射线上存在障碍物，则将接收该射线子目标点删除，若发出的射线上不存在障碍物，则将接收该射线子目标点保留，且将该子目标点作为最优子目标点；
[0113]
步骤3.3、将第一关键节点、最优子目标点和第二关键节点之间的连线作为第二最短路径；
[0114]
步骤3.4、遍历第二骨架的路径上所有相邻的关键节点直至获取所有第二最短路径，所述所有第二最短路径组成第三骨架。
[0115]
如图12为第三骨架生成图。图13为全局路径搜索图。
[0116]
在步骤4中，基于第三骨架进行全局路径搜索与路径平滑为：
[0117]
在机器人实际的室内运动中，机器人能够在任意位置开启运动，在任意位置停止运动，因此需要基于第三骨架进行全局路径搜索，便于机器人在给定位置和目的位置之间进行全局路径搜索，给定机器人的起始点和目标点搜索全局路径，主要分为三个部分：给定位置到第三骨架上的第一点的路径，第三骨架上第二点到目的位置的路径，第一点和第二点之前的第三骨架上的路径。具体搜索过程如下：
[0118]
步骤6.1、获取第三骨架上的第一点，所述第一点与给定位置的距离最近且两者间无障碍物，将给定位置和第三骨架上的第一点连接作为全局路径的第一部分；
[0119]
步骤6.2、获取第三骨架上的第二点，所述第二点与目标位置的距离最近且两者间无障碍物，将目标位置和第三骨架上的第二点连接作为全局路径的第二部分；
[0120]
步骤6.3、利用广度优先算法(bread-first search，bfs)搜索第三骨架上第一点
和第二点之间的最短路径作为全局路径的第三部分；
[0121]
步骤6.4、将第一部分、第二部分和第三部分连接后组成全局路径。
[0122]
基于线性插值方法对路径平滑，根据二维数据序列中需要插值的点(x,y)的左右邻近两个数据点(x',y')和(x”,y”)来进行数值的估计，插值函数为一次多项式，线性插值在各插值节点处的插值误差为0。利用线性插值进行路径平滑的具体步骤为：设函数y＝f(x)经过坐标为(x',y')和(x”,y”)的两点，求多项式使得满足使得满足
[0123]
得到区间[x',x”]区间内某一位置在直线上的具体值，可以得到式：
[0124][0125]
由于x的值已知，可根据上式得到y的值：
[0126][0127]
称为函数y＝f(x)在x'、x”处的一阶均差，记为f(x',x”)，可得到：
[0128][0129]
线性插值将x和x'、x”的距离作为权重用于y'和y”的加权，通过插值方法将路径进行平滑。
[0130]
本发明提供一个具体实施例，根据本发明提出的骨架重构voronoi路径规划方法，在某室内进行实验，实验器材包括机器人平台、处理器、激光雷达传感器；在机器人平台上装载处理器、激光雷达传感器；处理器分别与的机器人平台底盘、激光雷达传感器通过有线方式依次连接。
[0131]
其中，处理器选用的是酷睿m4i7-d迷你主机；机器人平台底盘选用的是pibot品牌的arduino驱动板底盘；激光雷达传感器选用性能稳定的sick lms111激光雷达。
[0132]
图14(a)为复杂场景下原始voronoi路径规划方法生成的骨架示意图，图14(b)为复杂场景下预处理后voronoi路径规划方法生成的骨架示意图，图14(c)为复杂场景下关键节点提取后voronoi路径规划方法生成的骨架示意图，图14(d)为本发明复杂场景下原始voronoi路径规划方法生成的骨架示意图。
[0133]
图14(a)生成的骨架溢出环境边界且存在一些毛刺，由于部分边界不封闭还会生成不必要的分支；图14(b)改进了骨架提取方式，但是生成的路径曲折冗余；图14(c)在一定程度上减少了路径转折次数，并平直了部分路径，但是存在着重规划失败导致路径与障碍物产生交叉、有不必要的转折路径和骨架关键节点等问题；如图14(d)所示，本发明算法生成的全局路径笔直，绕开障碍物的路径转折次数和关键节点数量进一步减少，所有路径都考虑了运动的安全性，将移动机器人本体尺寸和运动的危险区域考虑在内。
[0134]
第二实施例
[0135]
本发明提供骨架重构voronoi路径规划装置，如图2所示，包括：
[0136]
环境栅格地图获取模块，用于控制机器人在室内运动，实时采集室内物体与机器人的距离和方向角，通过建图处理得到环境栅格地图；
accessmemory)，其用作外部高速缓存。通过示例性但不是限制性说明，许多形式的ram可用，例如静态随机存取存储器(sram，static random access memory)、同步静态随机存取存储器(ssram，synchronous static random access memory)、动态随机存取存储器(dram，dynamic random access memory)、同步动态随机存取存储器(sdram，synchronousdynamic random access memory)、双倍数据速率同步动态随机存取存储器(ddrsdram，double data rate synchronous dynamic random access memory)、增强型同步动态随机存取存储器(esdram，enhanced synchronous dynamic random access memory)、同步连接动态随机存取存储器(sldram，synclink dynamic random access memory)、直接内存总线随机存取存储器(drram，direct rambus random access memory)。本发明实施例描述的存储器旨在包括但不限于这些和任意其它适合类型的存储器。
[0148]
第四实施例
[0149]
本发明还提供一种计算机存储介质，存储介质中存储有计算机程序，其特征在于，计算机程序被处理器执行时，实现上述任一项骨架重构voronoi路径规划方法的步骤。
[0150]
显然，本领域的技术人员可以对本发明进行各种改动和变型而不脱离本发明的精神和范围。这样，倘若本发明的这些修改和变型属于本发明权利要求及其等同技术的范围之内，则本发明也意图包含这些改动和变型在内。

技术特征：
1.一种骨架重构voronoi路径规划方法，其特征在于，包括以下步骤：机器人实时采集方位及距离数据并对其进行处理后生成基于voronoi图的第一骨架且提取关键节点；依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架；根据第二骨架进行逆向优化出第三骨架，实现骨架重构；基于第三骨架进行全局路径搜索与路径平滑。2.根据权利要求1的骨架重构voronoi路径规划方法，其特征在于：控制机器人在室内运动，实时采集室内物体与机器人的距离和方向角，通过建图处理得到环境栅格地图；将环境栅格地图预处理后，形成新的地图，预处理包括对环境栅格地图二值化、开运算及简化；遍历新的地图中所有像素值不为零的像素点，生成基于voronoi图的第一骨架。3.根据权利要求1的骨架重构voronoi路径规划方法，其特征在于：对于新的地图中的像素点，将黑色的像素点赋值为0，白色的像素点赋值为1，将每一个像素点p1上方的像素点设为p2，由p2绕p1顺时针依次设定p1周围的八邻域为p2-p9；其中，按照顺指针或逆时针顺序遍历每一个像素点p1周围的八邻域p2-p9，将一个邻域到另一个邻域值由0变为1的次数计为a，每个像素点px的八邻域中非0的像素点的数量为bx，x∈[1,9]；若某一个像素点周围的八邻域不完整，则不对该像素点进行遍历操作，将满足2≤b1≤6、a＝1、p2
·
p4
·
p8＝0或b2≠1及p2
·
p4
·
p6＝0或b4≠1的像素点p1赋值为0后形成黑色像素点；遍历新的地图中的所有像素点后根据赋值为0的黑色像素点生成基于voronoi的第一骨架。4.根据权利要求1的骨架重构voronoi路径规划方法，其特征在于：在生成的基于voronoi的第一骨架提取关键节点，关键节点包括端节点和分支节点，依次遍历每一个骨架点n1，并根据其八邻域n2-n9值的和进行关键节点判断；将满足n2+n3+n4+n5+n6+n7+n8+n9＝1的骨架点n1确定为端节点：将满足n1+n3+n5+n7＝3或n2+n4+n6+n8＝3或n1+n3+n6＝3或n1+n4+n6＝3或n1+n4+n7＝3或n2+n4+n7＝3或n2+n5+n7＝3或n2+n5+n8＝3或n3+n5+n8＝3或n3+n6+n8＝3的骨架点n1确定为分支节点；将所有端节点和分支节点在第一骨架上标注出来。5.根据权利要求1的骨架重构voronoi路径规划方法，其特征在于，生成第二骨架的方法为：依次选择第一骨架上具有连接关系的第一关键节点和第二关键节点，由第一关键节点向第二关键节点发出射线，若第一关键节点和第二关键节点间无障碍物则直接到达第二关键节点，将射线经过的路径作为再生成的第二骨架，反之，记录射线与障碍物的碰撞点；找到碰撞点邻域内无障碍物覆盖且与第二关键节点曼哈顿距离最小的点作为子目标点，若此时同时存在两个子目标点，则优先选择与原始骨架延展方向相同的点作为子目标
点；将找出的子目标点向目标点发出射线，若与障碍物碰撞，则记录该碰撞点；继续找寻子目标点，直到找到发出射线与第二关键节点不发生障碍物碰撞的子目标点，将该子目标点邻域内无障碍物覆盖且与障碍物保持相对安全距离的子目标点作为最终的子目标点，将第一关键节点、多个子目标点和第二关键节点依次连接作为第一最短路径；遍历第一骨架的路径上所有相邻的关键节点直至获取所有第一最短路径，所述所有第一最短路径组成第二骨架。6.根据权利要求5的骨架重构voronoi路径规划方法，其特征在于，生成第三骨架的方法为：以第二关键节点为发射点，依次向子目标点发出射线；若发出的射线上存在障碍物，则将接收该射线子目标点删除，若发出的射线上不存在障碍物，则将接收该射线子目标点保留，且将该子目标点作为最优子目标点；将第一关键节点、最优子目标点和第二关键节点之间的连线作为第二最短路径；遍历第二骨架的路径上所有相邻的关键节点直至获取所有第二最短路径，所述所有第二最短路径组成第三骨架。7.根据权利要求1的骨架重构voronoi路径规划方法，其特征在于：基于第三骨架进行全局路径搜索的方法为：获取第三骨架上的第一点，所述第一点与给定位置的距离最近且两者间无障碍物，将给定位置和第三骨架上的第一点连接作为全局路径的第一部分；获取第三骨架上的第二点，所述第二点与目标位置的距离最近且两者间无障碍物，将目标位置和第三骨架上的第二点连接作为全局路径的第二部分；搜索第三骨架上第一点和第二点之间的最短路径作为全局路径的第三部分；将第一部分、第二部分和第三部分连接后组成全局路径。8.一种骨架重构voronoi路径规划装置，其特征在于，包括以下步骤：第一骨架生成模块，用于机器人实时采集方位及距离数据并对其进行处理后生成基于voronoi图的第一骨架且提取关键节点；第二骨架生成模块，用于依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架；第三骨架生成模块，用于根据第二骨架进行逆向优化出第三骨架，实现骨架重构；全局路径搜索与路径平滑处理模块，用于基于第三骨架进行全局路径搜索与路径平滑。9.一种骨架重构voronoi路径规划设备，其特征在于：包括处理器和用于存储能够在处理器上运行计算机程序的存储器，处理器用于运行计算机程序时，执行上述权利要求1-7任一项骨架重构voronoi路径规划方法的步骤。10.一种计算机存储介质，存储介质中存储有计算机程序，其特征在于，计算机程序被处理器执行时，实现上述权利要求1-7任一项骨架重构voronoi路径规划方法的步骤。

技术总结
本发明提供一种骨架重构Voronoi路径规划方法、装置、设备及介质，包括机器人实时采集方位及距离数据并对其进行处理后生成基于Voronoi图的第一骨架且提取关键节点，依次在第一骨架上具有连接关系的两个关键节点间建立避开障碍物的第一最短路径，生成第二骨架，根据第二骨架进行逆向优化出第三骨架，实现骨架重构，基于第三骨架进行全局路径搜索与路径平滑。本发明能够生成更加精简笔直的骨架，生成更加适合机器人导航运动的路径，实时性强。实时性强。实时性强。


技术研发人员：蒋林 杨婉振 陈肯 罗焱 赵慧
受保护的技术使用者：武汉科技大学
技术研发日：2023.05.19
技术公布日：2023/9/12