法律状态公告日
法律状态信息
法律状态
2022-06-03
公开
发明专利申请公布
技术领域
本申请涉及机器人路径规划技术领域，具体而言，涉及一种基于冯洛诺伊图的路径规划方法、装置、设备及存储介质。
背景技术
随着近年来机器人产业的飞速发展，机器人在人们的日常生活中扮演着重要的角色。机器人的简易、方便、智能等优点受到了人们的喜爱。机器人可以满足人们的各种需求,如货物搬运、地形侦查等繁重、危险的工作。为了让移动机器人能够自主寻找移动路径,对其路径规划的研究尤为必要。
然而现有的路径规划方法在为移动机器人进行路径规划时仍然存在一些缺点，例如传统的基于采样的路径规划方法，规划路径速度较慢、路径不稳定、无法保证规划路径的最优以及在一些狭小空间处，机器人的路径搜索效率大幅下降等问题。
基于上述问题，目前尚未有有效的解决方法。
发明内容
本申请的目的在于提供一种基于冯洛诺伊图的路径规划方法、装置、设备及存储介质，路径规划速度快，能够提高路径搜索效率。
第一方面，本申请提供了一种基于冯洛诺伊图的路径规划方法，包括以下步骤：
S1.获取环境地图信息；
S2.将所述环境地图信息转换为Vonoroi图，所述Vonoroi图包含障碍物图像；
S3.获取起点的第一位置信息和终点的第二位置信息；
S4.根据所述第一位置信息和所述第二位置信息，在所述Vonoroi图中搜索从所述起点到所述终点的初始移动路径；所述初始移动路径包含多个路径节点；所述路径节点包含所述起点、所述终点和至少一个Vonoroi图节点；
S5.根据所述路径节点之间的连线和所述障碍物图像优化所述初始移动路径。
本申请通过利用冯洛诺伊图搜索移动路径，相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
可选地，步骤S5包括：
S501.获取所述初始移动路径的三个相邻的所述路径节点，从前到后依次记为第一节点、第二节点和第三节点；
S502.判断所述第一节点和所述第三节点之间的连线是否穿过所述障碍物图像；
S503.若穿过，则利用路径规划算法搜索从所述第一节点到所述第三节点的避障路径段，以替代所述初始移动路径中的从所述第一节点到所述第三节点的初始路径段。
当第一节点到第三节点之间的连线穿过障碍物图像时，利用路径规划算法重新选取第一节点到第三节点的避障路径段来替代第一节点到第三节点的初始路径段，而采用路径规划算法算出的避障路径段的长度比初始路径段的长度短，通过这种替换路径段的方式，可以有效减少机器人的移动距离，减少机器人的移动时间。
可选地，步骤S502之后，还包括：
S504.若所述第一节点和所述第三节点之间的连线不穿过所述障碍物图像，则判断所述第三节点是否为所述终点；
S505.若所述第三节点是所述终点，则停止路径优化；
S506.若所述第三节点不是所述终点，则重新把所述第三节点及其后一个路径节点分别标记为新的第二节点和新的第三节点，并以所述新的第二节点和新的第三节点分别代替原先的第二节点和原先的第三节点，并执行步骤S502-S506。
可选地，步骤S503包括：
利用RRT*算法在以所述第一节点、所述第二节点和所述第三节点为三个角点的三角形区域内，搜索所述避障路径段。
在实际应用中，RRT*算法具有渐进最优性，同时，由于有初始移动路径作为基础，利用RRT*算法在提升算法效率的同时，也保证了用RRT*算法规划得到的避障路径段长度下限，其避障路径段长度必然会小于等于初始路径段，且由于限制了搜索区域（以第一节点、第二节点和第三节点为三个角点的三角形区域），能够使RRT*算法以较快的运算速度收敛得到接近最短或者最短的避障路径段。
可选地，步骤S503还包括：
S5031.判断所述第三节点是否为所述终点；
S5032.若所述第三节点为所述终点，则停止路径优化；
S5033.若所述第三节点不是所述终点，则重新将所述第三节点及其后的第一个路径节点、第二个路径点分别标记为新的第一节点、新的第二节点和新的第三节点，并以所述新的第一节点、新的第二节点和新的第三节点分别代替原先的第一节点、原先的第二节点和原先的第三节点，并执行步骤S502-S506。
可选地，步骤S4包括:
S401.利用A*算法，根据所述第一位置信息和所述第二位置信息在所述Vonoroi图中搜索所述初始移动路径。
本申请提供的基于冯洛诺伊图的路径规划方法，通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
第二方面，本申请提供一种基于冯洛诺伊图的路径规划装置，用于机器人规划路径，所述装置包括：
包括以下模块：
第一获取模块：用于获取环境地图信息；
转化模块：用于将所述环境地图信息转换为Vonoroi图，所述Vonoroi图包含障碍物图像；
第二获取模块：用于获取起点的第一位置信息和终点的第二位置信息；
搜索模块：用于根据所述第一位置信息和所述第二位置信息，在所述Vonoroi图中搜索从所述起点到所述终点的初始移动路径；所述初始移动路径包含多个路径节点；所述路径节点包含所述起点、所述终点和至少一个Vonoroi图节点；
优化模块：用于根据所述路径节点之间的连线和所述障碍物图像优化所述初始移动路径。
可选地，所述优化模块在根据所述路径节点之间的连线和所述障碍物图像优化所述初始移动路径的时候，执行以下步骤：
S501.获取所述初始移动路径的三个相邻的所述路径节点，从前到后依次记为第一节点、第二节点和第三节点；
S502.判断所述第一节点和所述第三节点之间的连线是否穿过所述障碍物图像；
S503.若穿过，则利用路径规划算法搜索从所述第一节点到所述第三节点的避障路径段，以替代所述初始移动路径中的从所述第一节点到所述第三节点的初始路径段。
本申请提供的基于冯洛诺伊图的路径规划装置，通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
第三方面，本申请提供一种电子设备，包括处理器以及存储器，所述存储器存储有计算机可读取指令，当所述计算机可读取指令由所述处理器执行时，运行如上述第一方面提供的所述方法中的步骤。
第四方面，本申请提供一种存储介质，其上存储有计算机程序，所述计算机程序被处理器执行时运行如上述第一方面提供的所述方法中的步骤。
本申请的有益效果：路径节点少，路径规划速度快，路径搜索效率高，节省算法的运算时间。
附图说明
图1为本申请提供的基于冯洛诺伊图的路径规划方法的一种流程图。
图2为本申请提供的基于冯洛诺伊图的路径规划装置的一种结构示意图。
图3为本申请提供的电子设备的结构示意图。
图4为本申请提供的以第一节点、第二节点和第三节点为角点的三角形区域示意图。
图5为本申请提供的经过RRT*算法搜寻后的路径节点示意图。
图6为本申请提供的开始遍历初始移动路径的路径节点示意图。
图7为本申请提供的把第三节点及其后一个路径节点分别标记为新的第二节点和新的第三节点的路径节点示意图。
标号说明：
201、第一获取模块；202、转化模块；203、第二获取模块；204、搜索模块；205、优化模块；301、处理器；302、存储器；303、通信总线；400、障碍物。
具体实施方式
下面将结合本申请实施方式中附图，对本申请实施方式中的技术方案进行清楚、完整地描述，显然，所描述的实施方式仅仅是本申请一部分实施方式，而不是全部的实施方式。通常在此处附图中描述和示出的本申请实施方式的组件可以以各种不同的配置来布置和设计。因此，以下对在附图中提供的本申请的实施方式的详细描述并非旨在限制要求保护的本申请的范围，而是仅仅表示本申请的选定实施方式。基于本申请的实施方式，本领域技术人员在没有做出创造性劳动的前提下所获得的所有其他实施方式，都属于本申请保护的范围。
应注意到：相似的标号和字母在下面的附图中表示类似项，因此，一旦某一项在一个附图中被定义，则在随后的附图中不需要对其进行进一步定义和解释。同时，在本申请的描述中，术语“第一”、“第二”等仅用于区分描述，而不能理解为指示或暗示相对重要性。
在实际应用中，机器人广泛应用于货仓、商场和车间内，机器人可以替代人类从事繁琐的搬运工作，而这些工作场所一般都不是空旷的场地，工作场所内会设置有大小不一且不可移动的障碍物，例如货架、加工台等，机器人需要对移动路径进行合理规划，绕开障碍物的同时保证机器人的移动路径要最短，尽量节省移动时间，最终到达目标地点。
请参照图1，图1是本申请一些实施方式中的基于冯洛诺伊图的路径规划方法的流程图，用于机器人规划路径，包括以下步骤：
S1.获取环境地图信息；
S2.将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；
S3.获取起点的第一位置信息和终点的第二位置信息；
S4.根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；
S5.根据路径节点之间的连线和障碍物图像优化初始移动路径。
其中，环境地图信息的获取为现有技术，在此不再赘述。
其中，将环境地图信息转换为Vonoroi图的方法很多，常见的有分治法、扫描线算法和三角剖分算法。Vonoroi图又叫泰森多边形或冯洛诺伊图（其中，Vonoroi图节点包括Vonoroi图的控制点和/或这些多边形的角点），Vonoroi图相比其他地图类型具有路径节点少的特点，因此将环境地图信息转换为Vonoroi图，可以在保证整体路径节点完备性的基础上，使路径规划算法减少对路径节点的搜索，从而减少路径规划算法的算力消耗。
其中，获取起点的第一位置信息和终点的第二位置信息为现有技术，在此不再赘述。其中，起点的第一位置信息即起点的位置信息，终点的第二位置信息即终点的位置信息，为了便于区分两个位置信息，本文中把起点的位置信息称为第一位置信息，把终点的位置信息称为第二位置信息。
其中，搜索初始移动路径的方法可以采用现有的路径规划算法，例如组合规划算法、基于采样的规划算法或者RRT（快速扩展随机树）算法。
其中，根据路径节点之间的连线（直线连线）和障碍物图像优化初始移动路径，可以是指根据任意两个路径节点之间的连线是否穿过障碍物为依据，选择是否优化初始移动路径，优化的方法也可采用上述的路径规划算法。
本申请的基于冯洛诺伊图的路径规划方法，通过获取环境地图信息；将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；获取起点的第一位置信息和终点的第二位置信息；根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；根据路径节点之间的连线和障碍物图像优化初始移动路径。通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
在一些实施方式中，步骤S5包括：
S501.获取初始移动路径的三个相邻的路径节点，从前到后依次记为第一节点、第二节点和第三节点；
S502.判断第一节点和第三节点之间的连线是否穿过障碍物图像；
S503.若穿过，则利用路径规划算法搜索从第一节点到第三节点的避障路径段，以替代初始移动路径中的从第一节点到第三节点的初始路径段。
在一些实施方式中，获取初始移动路径的三个相邻的路径节点可以是从起点开始选取，然后按起点到终点的顺序选取三个，即上述的从前到后顺序是按照从起点到终点的顺序；也可以是从终点开始选取，然后按终点到起点的顺序选取三个，此时上述的从前到后顺序是从终点到起点的顺序；还可以是从靠近障碍物图像的路径段中按顺序选取三个路径节点，此时上述的从前到后则是根据实际情况，来确定是从起点到终点的顺序或者从终点到起点的顺序。
为了方便解释说明，以下的实施方式均是从起点开始选取，即上述的从前到后顺序是按照从起点到终点的顺序。
在一些优选的实施方式中，获取初始移动路径的三个相邻的路径节点采用的是从起点开始选取的方式，通过这种选取方式，可以遍历到初始移动路径上所有路径节点，对每个以三个相邻的路径节点所组成的初始路径段重新调整，最终能有效缩短第一节点到第三节点的初始路径段。
其中，步骤S503中，路径规划算法可以采用上述现有的路径规划算法。
查阅图4，其中，第一节点为s，第二节点为m，第三节点为e。
当第一节点到第三节点之间的连线穿过障碍物图像时，利用路径规划算法重新选取第一节点到第三节点的避障路径段来替代第一节点到第三节点的初始路径段，而采用路径规划算法算出的避障路径段的长度比初始路径段的长度短，通过这种替换路径段的方式，可以有效减少机器人的移动距离，减少机器人的移动时间。
在一些优选的实施方式中，步骤S503包括：
利用RRT*算法在以第一节点、第二节点和第三节点为三个角点的三角形区域内，搜索避障路径段。
其中，RRT*算法具有渐进最优性，同时，由于有初始移动路径作为基础，利用RRT*算法在提升算法效率的同时，也保证了用RRT*算法规划得到的避障路径段长度下限，其避障路径段长度必然会小于等于初始路径段，且由于限制了搜索区域（以第一节点、第二节点和第三节点为三个角点的三角形区域），能够使RRT*算法以较快的运算速度收敛得到接近最短或者最短的避障路径段。
在进一步的实施方式中，步骤S503还包括：
S5031.判断第三节点是否为终点；
S5032.若第三节点为终点，则停止路径优化；
S5033.若第三节点不是终点，则重新将第三节点及其后的第一个路径节点、第二个路径点分别标记为新的第一节点、新的第二节点和新的第三节点，并以所述新的第一节点、新的第二节点和新的第三节点分别代替原先的第一节点、原先的第二节点和原先的第三节点，并执行步骤S502-S506。
参阅图5，原先的第一节点为a，原先的第二节点为b，新的第一节点（原先的第三节点）为s，新的第二节点为m，新的第三节点为e，可以看出此时的第一节点s为原先的第三节点，第二节点m为原先的第三节点后的第一个路径节点，第三节点e为原先的第三节点后的第二个路径节点，原先的第一节点a到第一节点（原先的第三节点）s之间的避障路径段（实线部分，经过RRT*算法搜索得到）已经比原先的第一节点a到原先的第二节点为b，再到第一节点（原先的第三节点）s的初始路径段（虚线部分）短。
在进一步的实施方式中，步骤S502之后，还包括：
S504.若第一节点和第三节点之间的连线不穿过障碍物图像，则判断第三节点是否为终点；
S505.若第三节点是终点，则停止路径优化；
S506.若第三节点不是终点，则重新把第三节点及其后一个路径节点分别标记为新的第二节点和新的第三节点，并以所述新的第二节点和新的第三节点分别代替原先的第二节点和原先的第三节点，并执行步骤S502-S506。
参阅图6，其中，第一节点为s，第二节点为m，第三节点为e。由于第一节点s到第三节点e之间的连线没穿过障碍物400，且第三节点e不是终点，所以要重新把第三节点标记为第二节点，把第三节点的后一个路径节点标记为第三节点，即演化至图7，可以看出，图7的第一节点为s，第二节点（原图6的第三节点）为m，第三节点（原图6的第三节点的后一个路径节点）为e。
通过这种依次巡检的方式，可以遍历到初始移动路径上的所有路径节点，对每个以三个相邻的路径节点所组成的初始路径段进行检查，从而判断是否需要使用路径规划算法重新规划或者剔除多余的路径节点，能进一步减少初始路径段的长度。
在一些优选的实施方式中，步骤S4包括:
S401.利用A*算法，根据第一位置信息和第二位置信息在Vonoroi图中搜索初始移动路径。
一方面，通过利用A*算法作为一个启发式的搜索算法，在Vonoroi图中搜索初始移动路径，搜索效率相比传统的深度优先算法和广度优先算法要高。另一方面，通过利用A*算法在在Vonoroi图中搜索初始移动路径，将初始移动路径作为引导，使得后续利用RRT*算法在以第一节点、第二节点和第三节点为三个角点的三角形区域内进行搜索时，在面对狭小空间处的路径规划问题上，不会因为采集到的路径节点频繁落入障碍物，导致RRT*算法效率大幅降低。
由上可知，本申请的基于冯洛诺伊图的路径规划方法，通过获取环境地图信息；将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；获取起点的第一位置信息和终点的第二位置信息；根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；根据路径节点之间的连线和障碍物图像优化初始移动路径。通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
请参照图2，图2是本申请一些实施方式中的基于冯洛诺伊图的路径规划装置，用于机器人规划路径，包括以下模块：
第一获取模块201：用于获取环境地图信息；
转化模块202：用于将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；
第二获取模块203：用于获取起点的第一位置信息和终点的第二位置信息；
搜索模块204：用于根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；
优化模块205：用于根据路径节点之间的连线和障碍物图像优化初始移动路径。
其中，第一获取模块201获取环境地图信息的方式为现有技术，在此不再赘述。
其中，转化模块202将环境地图信息转换为Vonoroi图的方法很多，常见的有分治法、扫描线算法和三角剖分算法。Vonoroi图又叫泰森多边形或冯洛诺伊图（其中，Vonoroi图节点包括Vonoroi图的控制点和/或这些多边形的角点），Vonoroi图相比其他地图类型具有路径节点少的特点，因此将环境地图信息转换为Vonoroi图，可以在保证整体路径节点完备性的基础上，使路径规划算法减少对路径节点的搜索，从而减少路径规划算法的算力消耗。
其中，第二获取模块203获取起点的第一位置信息和终点的第二位置信息为现有技术，在此不再赘述。其中，起点的第一位置信息即起点的位置信息，终点的第二位置信息即终点的位置信息，为了便于区分两个位置信息，本文中把起点的位置信息称为第一位置信息，把终点的位置信息称为第二位置信息。
其中，搜索模块204搜索初始移动路径的方法可以采用现有的路径规划算法，例如组合规划算法、基于采样的规划算法或者RRT（快速扩展随机树）算法。
其中，根据路径节点之间的连线（直线连线）和障碍物图像优化初始移动路径，可以是指根据任意两个路径节点之间的连线是否穿过障碍物为依据，选择是否优化初始移动路径，优化的方法也可采用上述的路径规划算法。
本申请的基于冯洛诺伊图的路径规划装置，通过第一获取模块201获取环境地图信息；转化模块202将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；第二获取模块203获取起点的第一位置信息和终点的第二位置信息；搜索模块204根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；优化模块205根据路径节点之间的连线和障碍物图像优化初始移动路径。通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
在一些实施方式中，优化模块205在根据路径节点之间的连线和障碍物图像优化初始移动路径的时候，执行以下步骤：
S501.获取初始移动路径的三个相邻的路径节点，从前到后依次记为第一节点、第二节点和第三节点；
S502.判断第一节点和第三节点之间的连线是否穿过障碍物图像；
S503.若穿过，则利用路径规划算法搜索从第一节点到第三节点的避障路径段，以替代初始移动路径中的从第一节点到第三节点的初始路径段。
在一些实施方式中，获取初始移动路径的三个相邻的路径节点可以是从起点开始选取，然后按起点到终点的顺序选取三个，即上述的从前到后顺序是按照从起点到终点的顺序；也可以是从终点开始选取，然后按终点到起点的顺序选取三个，此时上述的从前到后顺序是从终点到起点的顺序；还可以是从靠近障碍物图像的路径段中按顺序选取三个路径节点，此时上述的从前到后则是根据实际情况，来确定是从起点到终点的顺序或者从终点到起点的顺序。
为了方便解释说明，以下的实施方式均是从起点开始选取，即上述的从前到后顺序是按照从起点到终点的顺序。
在一些优选的实施方式中，获取初始移动路径的三个相邻的路径节点采用的是从起点开始选取的方式，通过这种选取方式，可以遍历到初始移动路径上所有路径节点，对每个以三个相邻的路径节点所组成的初始路径段重新调整，最终能有效缩短第一节点到第三节点的初始路径段。
其中，步骤S503中，路径规划算法可以采用上述现有的路径规划算法。
查阅图4，其中，第一节点为s，第二节点为m，第三节点为e。
当第一节点到第三节点之间的连线穿过障碍物图像时，利用路径规划算法重新选取第一节点到第三节点的避障路径段来替代第一节点到第三节点的初始路径段，而采用路径规划算法算出的避障路径段的长度比初始路径段的长度短，通过这种替换路径段的方式，可以有效减少机器人的移动距离，减少机器人的移动时间。
在一些优选的实施方式中，步骤S503包括：
利用RRT*算法在以第一节点、第二节点和第三节点为三个角点的三角形区域内，搜索避障路径段。
其中，RRT*算法具有渐进最优性，同时，由于有初始移动路径作为基础，利用RRT*算法在提升算法效率的同时，也保证了用RRT*算法规划得到的避障路径段长度下限，其避障路径段长度必然会小于等于初始路径段，且由于限制了搜索区域（以第一节点、第二节点和第三节点为三个角点的三角形区域），能够使RRT*算法以较快的运算速度收敛得到接近最短或者最短的避障路径段。
在进一步的实施方式中，步骤S503还包括：
S5031.判断第三节点是否为终点；
S5032.若第三节点为终点，则停止路径优化；
S5033.若第三节点不是终点，则重新将第三节点及其后的第一个路径节点、第二个路径点分别标记为新的第一节点、新的第二节点和新的第三节点，并以所述新的第一节点、新的第二节点和新的第三节点分别代替原先的第一节点、原先的第二节点和原先的第三节点，并执行步骤S502-S506。
参阅图5，原先的第一节点为a，原先的第二节点为b，新的第一节点（原先的第三节点）为s，新的第二节点为m，新的第三节点为e，可以看出此时的第一节点s为原先的第三节点，第二节点m为原先的第三节点后的第一个路径节点，第三节点e为原先的第三节点后的第二个路径节点，原先的第一节点a到第一节点（原先的第三节点）s之间的避障路径段（实线部分，经过RRT*算法搜索得到）已经比原先的第一节点a到原先的第二节点为b，再到第一节点（原先的第三节点）s的初始路径段（虚线部分）短。
在进一步的实施方式中，步骤S502之后，还包括：
S504.若第一节点和第三节点之间的连线不穿过障碍物图像，则判断第三节点是否为终点；
S505.若第三节点是终点，则停止路径优化；
S506.若第三节点不是终点，则重新把第三节点及其后一个路径节点分别标记为新的第二节点和新的第三节点，并以所述新的第二节点和新的第三节点分别代替原先的第二节点和原先的第三节点，并执行步骤S502-S506。
参阅图6，其中，第一节点为s，第二节点为m，第三节点为e。由于第一节点s到第三节点e之间的连线没穿过障碍物400，且第三节点e不是终点，所以要重新把第三节点标记为第二节点，把第三节点的后一个路径节点标记为第三节点，即演化至图7，可以看出，图7的第一节点为s，第二节点（原图6的第三节点）为m，第三节点（原图6的第三节点的后一个路径节点）为e。
通过这种依次巡检的方式，可以遍历到初始移动路径上的所有路径节点，对每个以三个相邻的路径节点所组成的初始路径段进行检查，从而判断是否需要使用路径规划算法重新规划或者剔除多余的路径节点，能进一步减少初始路径段的长度。
在一些优选的实施方式中，搜索模块204在根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径时，执行以下步骤:
S401.利用A*算法，根据第一位置信息和第二位置信息在Vonoroi图中搜索初始移动路径。
一方面，通过利用A*算法作为一个启发式的搜索算法，在Vonoroi图中搜索初始移动路径，搜索效率相比传统的深度优先算法和广度优先算法要高。另一方面，通过利用A*算法在在Vonoroi图中搜索初始移动路径，将初始移动路径作为引导，使得后续利用RRT*算法在以第一节点、第二节点和第三节点为三个角点的三角形区域内进行搜索时，在面对狭小空间处的路径规划问题上，不会因为采集到的路径节点频繁落入障碍物，导致RRT*算法效率大幅降低。
由上可知，本申请的基于冯洛诺伊图的路径规划装置，通过第一获取模块201获取环境地图信息；转化模块202将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；第二获取模块203获取起点的第一位置信息和终点的第二位置信息；搜索模块204根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；优化模块205根据路径节点之间的连线和障碍物图像优化初始移动路径。通过利用冯洛诺伊图搜索移动路径相比使用其他地图类型进行路径规划具有路径节点少的优势，解决了传统路径规划算法需要对大量路径节点进行规划的问题，节省了运算时间，提高了机器人的对路径的搜索和规划效率。
请参照图3，图3为本申请实施方式提供的一种电子设备的结构示意图，本申请提供一种电子设备，包括：处理器301和存储器302，处理器301和存储器302通过通信总线303和/或其他形式的连接机构（未标出）互连并相互通讯，存储器302存储有处理器301可执行的计算机程序，当计算设备运行时，处理器301执行该计算机程序，以在执行时执行上述实施方式的任一可选的实现方式中的方法，以实现以下功能：获取环境地图信息；将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；获取起点的第一位置信息和终点的第二位置信息；根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；根据路径节点之间的连线和障碍物图像优化初始移动路径。
本申请实施方式提供一种存储介质，其上存储有计算机程序，计算机程序被处理器执行时，执行上述实施方式的任一可选的实现方式中的方法，以实现以下功能：获取环境地图信息；将环境地图信息转换为Vonoroi图，Vonoroi图包含障碍物图像；获取起点的第一位置信息和终点的第二位置信息；根据第一位置信息和第二位置信息，在Vonoroi图中搜索从起点到终点的初始移动路径；初始移动路径包含多个路径节点；路径节点包含起点、终点和至少一个Vonoroi图节点；根据路径节点之间的连线和障碍物图像优化初始移动路径。其中，存储介质可以由任何类型的易失性或非易失性存储设备或者它们的组合实现，如静态随机存取存储器（Static Random Access Memory, 简称SRAM），电可擦除可编程只读存储器（Electrically Erasable Programmable Read-Only Memory, 简称EEPROM），可擦除可编程只读存储器（Erasable Programmable Read Only Memory, 简称EPROM），可编程只读存储器（Programmable Red-Only Memory, 简称PROM），只读存储器（Read-Only Memory,简称ROM），磁存储器，快闪存储器，磁盘或光盘。
在本申请所提供的实施方式中，应该理解到，所揭露系统和方法，可以通过其它的方式实现。以上所描述的系统实施方式仅仅是示意性的，例如，所述单元的划分，仅仅为一种逻辑功能划分，实际实现时可以有另外的划分方式，又例如，多个单元或组件可以结合或者可以集成到另一个系统，或一些特征可以忽略，或不执行。另一点，所显示或讨论的相互之间的耦合或直接耦合或通信连接可以是通过一些通信接口，系统或单元的间接耦合或通信连接，可以是电性，机械或其它的形式。
另外，作为分离部件说明的单元可以是或者也可以不是物理上分开的，作为单元显示的部件可以是或者也可以不是物理单元，即可以位于一个地方，或者也可以分布到多个网络单元上。可以根据实际的需要选择其中的部分或者全部单元来实现本实施方式方案的目的。
再者，在本申请各个实施方式中的各功能模块可以集成在一起形成一个独立的部分，也可以是各个模块单独存在，也可以两个或两个以上模块集成形成一个独立的部分。
在本文中，诸如第一和第二等之类的关系术语仅仅用来将一个实体或者操作与另一个实体或操作区分开来，而不一定要求或者暗示这些实体或操作之间存在任何这种实际的关系或者顺序。
以上所述仅为本申请的实施方式而已，并不用于限制本申请的保护范围，对于本领域的技术人员来说，本申请可以有各种更改和变化。凡在本申请的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本申请的保护范围之内。
