CN108303098B - 机器人路径规划方法及设备 - Google Patents

Abstract

本发明的目的是提供一种机器人路径规划方法及设备，本发明基于现有代价地图占用内存大、计算效率低下等不足，采用了稀疏代价地图技术，用稀疏代价地图来保存代价值，降低了内存消耗和访问效率。同时配合瓦片管理器，提高代价地图的复用率，提高平均访问速度，成功降低了每次搜索路径的内存消耗。另外，本发明利用代价地图的局部性，采用缓存技术，用来提高每次访问代图的速度。通过预生成的膨胀信息，提高实时计算代价地图的效率。基于稀疏代价地图的增量更新机制，减少重新计算代价地图的开销。

Description

机器人路径规划方法及设备

技术领域

本发明涉及计算机领域，尤其涉及一种机器人路径规划方法及设备。

背景技术

随着智能移动机器人发展，各种服务类机器人纷纷涌现，譬如扫地机、导游、导购类机器人、咨询机器人等，人们对移动机器人动态的运动路径规划能力有了越来越高的期待。

目前主流的路径规划算法比如A*和D*，运行时都需要参考和使用代价地图。代价地图，是根据环境地图和机器人传感器输入的数据计算得到的一张虚拟地图，表示机器人按照特定方式移动会消耗的代价。机器人路径规划问题就规约为求取在代价地图上，消耗代价最少的路径。

主流的代价地图，比如ROS中采用的，需要跟环境地图大小相匹配，并且每次搜索路径都需要重新计算整个代价地图。现有的方法的问题在于环境地图一般比较大，存储相应大小的代价地图非常消耗内存空间，在某些特定平台的嵌入式系统上会导致程序奔溃。另外，需要根据每个障碍物的栅格点，并考虑机器人实际物理大小来计算代价地图，该过程通常比较慢。由于环境会经常发生变化，所以每一次搜索规划路径的时候都需要重新建立代价地图，这样会导致机器人每次移动规划的延时变得很长，整个体验变差。

图1为传统代价地图，一般为离散的栅格图，路径规划模块通过坐标直接得到代价地图中对应的栅格，来获取代价值。该方法的缺点是需要和环境地图一样大的代价地图来保存代价值，并且两次路径规划期间，环境有所变化，需要重新建立代价地图。这么一来不但内存消耗巨大，而且路径规划效率低下。

发明内容

本发明的一个目的是提供一种机器人路径规划方法及设备，能够解决现有的机器人路径规划方式内存消耗巨大，而且路径规划效率低下的问题。

根据本发明的一个方面，提供了一种机器人路径规划方法，该方法包括：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

进一步的，上述方法中，及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区，包括：

根据机器人物理尺寸预生成膨胀信息；

所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息。

进一步的，上述方法中，所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，包括：

若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦片；

若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；

若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；

若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区。

根据本发明的另一方面，还提供了一种机器人路径规划设备，该设备包括：

分片装置，用于将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

索引计算器，用于获取路径规划的当前目标坐标，根据所述目标坐标分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器，用于根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格，并返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器，用于建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块，用于在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

进一步的，上述设备中，所述及时瓦片构造器，用于根据机器人物理尺寸预生成膨胀信息，及根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息。

进一步的，上述设备中，所述及时瓦片构造器，用于若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦片 ；若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区。

根据本发明的另一面，还提供一种基于计算的设备，其中，包括：

处理器；以及

被安排成存储计算机可执行指令的存储器，所述可执行指令在被执行时使所述处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

根据本发明的另一面，还提供一种计算机可读存储介质，其上存储有计算机可执行指令，其中，该计算机可执行指令被处理器执行时使得该处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

与现有技术相比，本发明基于现有代价地图占用内存大、计算效率低下等不足，采用了稀疏代价地图技术，即将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应，用稀疏代价地图来保存代价值，降低了内存消耗和访问效率。同时配合瓦片管理器，提高代价地图的复用率，提高平均访问速度，成功降低了每次搜索路径的内存消耗。另外，本发明利用代价地图的局部性，采用缓存技术，用来提高每次访问代图的速度。通过预生成的膨胀信息，提高实时计算代价地图的效率。基于稀疏代价地图的增量更新机制，减少重新计算代价地图的开销。

附图说明

通过阅读参照以下附图所作的对非限制性实施例所作的详细描述，本发明的其它特征、目的和优点将会变得更明显：

图1示出传统的代价地图；

图2示出本发明一实施例的稀疏代价地图；

图3示出本发明一实施例的瓦片管理器图；

图4示出本发明一实施例的稀疏代价地图访问流程图。

附图中相同或相似的附图标记代表相同或相似的部件。

具体实施方式

下面结合附图对本发明作进一步详细描述。

在本申请一个典型的配置中，终端、服务网络的设备和可信方均包括一个或多个处理器 (CPU)、输入/输出接口、网络接口和内存。

内存可能包括计算机可读介质中的非永久性存储器，随机存取存储器 (RAM) 和/或非易失性内存等形式，如只读存储器 (ROM) 或闪存(flash RAM)。内存是计算机可读介质的示例。

计算机可读介质包括永久性和非永久性、可移动和非可移动媒体可以由任何方法或技术来实现信息存储。信息可以是计算机可读指令、数据结构、程序的模块或其他数据。计算机的存储介质的例子包括，但不限于相变内存 (PRAM)、静态随机存取存储器 (SRAM)、动态随机存取存储器 (DRAM)、其他类型的随机存取存储器 (RAM)、只读存储器 (ROM)、电可擦除可编程只读存储器 (EEPROM)、快闪记忆体或其他内存技术、只读光盘只读存储器(CD-ROM)、数字多功能光盘 (DVD) 或其他光学存储、磁盒式磁带，磁带磁盘存储或其他磁性存储设备或任何其他非传输介质，可用于存储可以被计算设备访问的信息。按照本文中的界定，计算机可读介质不包括非暂存电脑可读媒体 (transitory media)，如调制的数据信号和载波。

本发明提供一种机器人路径规划方法，包括：

步骤S1，将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

例如，每个瓦片可以依序包含多个不同偏移量的栅格；

在此，代价值对应一个具体的数值，可以是整形也可以是浮点类型，代价值表示机器人中心质点从邻接栅格移动到当前栅格的所需要的代价，代价值越大表示我们越不希望机器人移动到当前栅格，比如靠近障碍物或者墙的地方可以设置大一点的代价，空旷区域可以设置低一点的代价，当代价值大于一定阈值，则表示规划路径的时候不允许机器人在当前栅格，比如当机器人中心在当前栅格的时候会跟周围的障碍物方式碰撞；

所谓瓦片是代价地图中一个区域的代价值（包含多个栅格）；

步骤S2，将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

步骤S3，瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

步骤S4，所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

步骤S51，及时瓦片构造器（Just In Time Tile Builder）建立所述栅格所在的瓦片后放入瓦片缓存区；

在此，瓦片是以一种lazy（懒）的方式生成的，也就是当路径规划时访问到的栅格落在了某个瓦片里面，并且该瓦片没有建立，这个时候会根据环境地图和传感器数据生成瓦片，接下来访问的栅格很有可能是当前访问的栅格邻接的栅格，所以瓦片会放到缓存里面以供后续使用；

本实施例是可以在线运行的系统，通过增量的方式（incremental）来动态生成代价图，可以边构建地图边建立代价图并规划路径，不需要额外预处理时间同时效率也比较高；

所述路径规划模块在搜索路径的时候，可以由及时瓦片构造器动态处理生成代价图的瓦片，查询到哪个栅格就把对应的瓦片的代价图计算出来；

步骤S52，所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

具体的，及时瓦片构造器（Just In Time Tile Builder），在路径规划模块需要访问某个栅格前把会访问到的瓦片准备好，放入瓦片缓存区。本实施例利用代价地图的局部性，采用缓存技术，用来提高每次访问代图的速度。

具体的，图2为稀疏代价地图的结构图。整个代价地图被分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值。每一个瓦片会和一个唯一的索引值一一对应，通过索引值，瓦片管理器可以找到对应的瓦片。

本发明基于现有代价地图占用内存大、计算效率低下等不足，采用了稀疏代价地图技术，即将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应，用稀疏代价地图来保存代价值，降低了内存消耗和访问效率。同时配合瓦片管理器，提高代价地图的复用率，提高平均访问速度，成功降低了每次搜索路径的内存消耗。

本发明的机器人路径规划方法一实施例中，步骤S51，及时瓦片构造器（Just InTime Tile Builder）建立所述栅格所在的瓦片后放入瓦片缓存区，包括：

步骤S511，根据机器人物理尺寸预生成膨胀信息；

具体的，膨胀是指在规划路径的时候把机器人当做一个没有体积和面积的质点（实际并不是），在这种情况下为了避免碰撞障碍物，需要把障碍物在地图上按照机器人尺寸做一个膨胀，一般膨胀大小为机器人外接圆半径，这样机器人中心只要在碰撞区域外就不会发生碰撞障碍物的情况，所谓膨胀信息实际上就是一张以机器人物理轮廓为原型的栅格图，在地图上对障碍物做膨胀的时候直接把栅格图的中心对应在障碍物上，直接画在代价地图上面；

步骤S512，所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息。

在此，环境地图用来表示周围障碍物的位置，可以是各种格式。其中一种常用的是占用栅格图。每个栅格表示该格子有障碍物的概率。

机器人的传感器主要是探测障碍物所用的传感器，传感器探测障碍物得到地数据即为传感器数据，传感器可以是激光雷达、超声波传感器、碰撞条和红外距离传感器等。传感器数据可以是这些传感器探测到的距离数据。

所述第二障碍物信息可以是未包含在环境地图的第一障碍物信息中的信息。通过第一障碍物信息，和所述第二障碍物信息作为所述第一障碍物信息的补充信息，可以将第一障碍物信息和第二障碍物信息结合，保证对应建立地瓦片更高效和准确。

图3为瓦片管理器的结构图。预生成膨胀信息只需要根据机器人物理尺寸生成一次，之后通过生成的膨胀信息可以快速构建代价地图。及时瓦片构造器（Just In TimeTile Builder），在路径规划模块需要访问某个栅格前把会访问到的瓦片准备好。及时瓦片构造器的输入为机器人的环境地图、机器人的传感器数据以及预生成的膨胀信息，输出为稀疏代价地图中的一个个瓦片。预生成的膨胀信息，提高实时计算代价地图的效率。

本发明的机器人路径规划方法一实施例中，步骤S512，所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，包括：

若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦片；

在此，如果环境地图发生了变化，或者传感器探测到了之前未知的障碍物，则瓦片需要重新构建（代价信息变了），会把该瓦片置为失效；

若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；

若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；

若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息。

在此，如图4所示，稀疏代价地图访问流程如下：

1）开始一次路径规划前，清除瓦片缓存区中已经失效稀疏代价地图的部分瓦片。对于已经建立好的瓦片，并且还处于有效状态的，仍旧保留中瓦片缓存区中，以此达到复用部分代价地图信息以提高路径规划效率。

2）如果要访问的瓦片已经在瓦片缓存区，则快速得到对应代价值。

3）如果要访问的瓦片不在缓存区，但是已经建立，则把对应瓦片放入瓦片缓存区，进而访问代价值。

4）如果要访问的瓦片不在瓦片缓存区，并且没有建立，则通过及时瓦片构造器建立对应瓦片，把对应瓦片放入缓存区，进而访问代价值。

最近最常用的瓦片会放在瓦片缓存区内，路径规划模块可以快速的访问瓦片缓存区，得到代价值。同时及时瓦片构造器负责维护瓦片缓存区，更新、换入、换出最近常用的瓦片，维护数据的一致性。

本实施例基于稀疏代价地图的增量更新机制，减少重新计算代价地图的开销。

根据本发明的另一方面，还提供了一种机器人路径规划设备，该设备包括：

分片装置，用于将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

例如，每个瓦片可以依序包含多个不同偏移量的栅格；

在此，代价值对应一个具体的数值，可以是整形也可以是浮点类型，代价值表示机器人中心质点从邻接栅格移动到当前栅格的所需要的代价，代价值越大表示我们越不希望机器人移动到当前栅格，比如靠近障碍物或者墙的地方可以设置大一点的代价，空旷区域可以设置低一点的代价，当代价值大于一定阈值，则表示规划路径的时候不允许机器人在当前栅格，比如当机器人中心在当前栅格的时候会跟周围的障碍物方式碰撞；

所谓瓦片是代价地图中一个区域的代价值（包含多个栅格）；

索引计算器，用于获取路径规划的当前目标坐标，根据所述目标坐标分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器，用于根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格，并返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器，用于建立所述栅格所在的瓦片后放入瓦片缓存区；

在此，瓦片是以一种lazy（懒）的方式生成的，也就是当路径规划时访问到的栅格落在了某个瓦片里面，并且该瓦片没有建立，这个时候会根据环境地图和传感器数据生成瓦片，接下来访问的栅格很有可能是当前访问的栅格邻接的栅格，所以瓦片会放到缓存里面以供后续使用；

本实施例是可以在线运行的系统，通过增量的方式（incremental）来动态生成代价图，可以边构建地图边建立代价图并规划路径，不需要额外预处理时间同时效率也比较高；

所述路径规划模块在搜索路径的时候，可以由及时瓦片构造器动态处理生成代价图的瓦片，查询到哪个栅格就把对应的瓦片的代价图计算出来；

所述路径规划模块，用于在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

具体的，及时瓦片构造器（Just In Time Tile Builder），在路径规划模块需要访问某个栅格前把会访问到的瓦片准备好，放入瓦片缓存区。本实施例利用代价地图的局部性，采用缓存技术，用来提高每次访问代图的速度。

具体的，图2为稀疏代价地图的结构图。整个代价地图被分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值。每一个瓦片会和一个唯一的索引值一一对应，通过索引值，瓦片管理器可以找到对应的瓦片。

本发明基于现有代价地图占用内存大、计算效率低下等不足，采用了稀疏代价地图技术，即将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应，用稀疏代价地图来保存代价值，降低了内存消耗和访问效率。同时配合瓦片管理器，提高代价地图的复用率，提高平均访问速度，成功降低了每次搜索路径的内存消耗。

本发明的机器人路径规划设备一实施例中，所述及时瓦片构造器，用于根据机器人物理尺寸预生成膨胀信息，及根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息。

具体的，膨胀是指在规划路径的时候把机器人当做一个没有体积和面积的质点（实际并不是），在这种情况下为了避免碰撞障碍物，需要把障碍物在地图上按照机器人尺寸做一个膨胀，一般膨胀大小为机器人外接圆半径，这样机器人中心只要在碰撞区域外就不会发生碰撞障碍物的情况，所谓膨胀信息实际上就是一张以机器人物理轮廓为原型的栅格图，在地图上对障碍物做膨胀的时候直接把栅格图的中心对应在障碍物上，直接画在代价地图上面；

环境地图用来表示周围障碍物的位置，可以是各种格式。其中一种常用的是占用栅格图。每个栅格表示该格子有障碍物的概率。

机器人的传感器主要是探测障碍物所用的传感器，传感器探测障碍物得到地数据即为传感器数据，传感器可以是激光雷达、超声波传感器、碰撞条和红外距离传感器等。传感器数据可以是这些传感器探测到的距离数据。

所述第二障碍物信息可以是未包含在环境地图的第一障碍物信息中的信息。通过第一障碍物信息，和所述第二障碍物信息作为所述第一障碍物信息的补充信息，可以将第一障碍物信息和第二障碍物信息结合，保证对应建立地瓦片更高效和准确。

图3为瓦片管理器的结构图。预生成膨胀信息只需要根据机器人物理尺寸生成一次，之后通过生成的膨胀信息可以快速构建代价地图。及时瓦片构造器（Just In TimeTile Builder），在路径规划模块需要访问某个栅格前把会访问到的瓦片准备好。及时瓦片构造器的输入为机器人的环境地图、机器人的传感器数据以及预生成的膨胀信息，输出为稀疏代价地图中的一个个瓦片。预生成的膨胀信息，提高实时计算代价地图的效率。

本发明的机器人路径规划设备一实施例中，所述及时瓦片构造器，用于若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦；若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区。

在此，如果环境地图发生了变化，或者传感器探测到了之前未知的障碍物，则瓦片需要重新构建（代价信息变了），会把该瓦片置为失效。

根据本发明的另一面，还提供一种基于计算的设备，其中，包括：

处理器；以及

被安排成存储计算机可执行指令的存储器，所述可执行指令在被执行时使所述处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

根据本发明的另一面，还提供一种计算机可读存储介质，其上存储有计算机可执行指令，其中，该计算机可执行指令被处理器执行时使得该处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

本发明的设备和计算机可读存储介质各实施例的详细内容，具体可参见各方法实施例的对应部分，在此，不再赘述。

综上所述，本发明基于现有代价地图占用内存大、计算效率低下等不足，采用了稀疏代价地图技术，即将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应，用稀疏代价地图来保存代价值，降低了内存消耗和访问效率。同时配合瓦片管理器，提高代价地图的复用率，提高平均访问速度，成功降低了每次搜索路径的内存消耗。另外，本发明利用代价地图的局部性，采用缓存技术，用来提高每次访问代图的速度。通过预生成的膨胀信息，提高实时计算代价地图的效率。基于稀疏代价地图的增量更新机制，减少重新计算代价地图的开销。

显然，本领域的技术人员可以对本申请进行各种改动和变型而不脱离本申请的精神和范围。这样，倘若本申请的这些修改和变型属于本申请权利要求及其等同技术的范围之内，则本申请也意图包含这些改动和变型在内。

需要注意的是，本发明可在软件和/或软件与硬件的组合体中被实施，例如，可采用专用集成电路（ASIC）、通用目的计算机或任何其他类似硬件设备来实现。在一个实施例中，本发明的软件程序可以通过处理器执行以实现上文所述步骤或功能。同样地，本发明的软件程序（包括相关的数据结构）可以被存储到计算机可读记录介质中，例如，RAM存储器，磁或光驱动器或软磁盘及类似设备。另外，本发明的一些步骤或功能可采用硬件来实现，例如，作为与处理器配合从而执行各个步骤或功能的电路。

另外，本发明的一部分可被应用为计算机程序产品，例如计算机程序指令，当其被计算机执行时，通过该计算机的操作，可以调用或提供根据本发明的方法和/或技术方案。而调用本发明的方法的程序指令，可能被存储在固定的或可移动的记录介质中，和/或通过广播或其他信号承载媒体中的数据流而被传输，和/或被存储在根据所述程序指令运行的计算机设备的工作存储器中。在此，根据本发明的一个实施例包括一个装置，该装置包括用于存储计算机程序指令的存储器和用于执行程序指令的处理器，其中，当该计算机程序指令被该处理器执行时，触发该装置运行基于前述根据本发明的多个实施例的方法和/或技术方案。

对于本领域技术人员而言，显然本发明不限于上述示范性实施例的细节，而且在不背离本发明的精神或基本特征的情况下，能够以其他的具体形式实现本发明。因此，无论从哪一点来看，均应将实施例看作是示范性的，而且是非限制性的，本发明的范围由所附权利要求而不是上述说明限定，因此旨在将落在权利要求的等同要件的含义和范围内的所有变化涵括在本发明内。不应将权利要求中的任何附图标记视为限制所涉及的权利要求。此外，显然“包括”一词不排除其他单元或步骤，单数不排除复数。装置权利要求中陈述的多个单元或装置也可以由一个单元或装置通过软件或者硬件来实现。第一，第二等词语用来表示名称，而并不表示任何特定的顺序。

Claims (6)

1.一种机器人路径规划方法，其中，该方法包括：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区，包括：根据机器人物理尺寸预生成膨胀信息；所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

2.根据权利要求1所述的方法，其中，所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，包括：

若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦片；

若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；

若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；

若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区。

3.一种机器人路径规划设备，其中，该设备包括：

分片装置，用于将整个代价地图分为数个大小相同的瓦片，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

索引计算器，用于获取路径规划的当前目标坐标，根据所述目标坐标分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器，用于根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格，并返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器，用于建立所述栅格所在的瓦片后放入瓦片缓存区，包括：用于根据机器人物理尺寸预生成膨胀信息，及根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息；

所述路径规划模块，用于在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

4.根据权利要求3所述的设备，其中，所述及时瓦片构造器，用于若所述环境地图和传感器数据发生变化，所述及时瓦片构造器清除瓦片缓存区中对应的已经失效的瓦；若所述瓦片缓存区中的瓦片还处于有效状态，所述及时瓦片构造器将该有效的瓦片仍旧保留在所述瓦片缓存区中；若所述栅格所在的瓦片已经建立，但未放入所述瓦片缓存区，则所述及时瓦片构造器将建立好的所述栅格所在的瓦片放入所述瓦片缓存区；若所述栅格所在的瓦片未建立，则所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区。

5.一种基于计算的设备，其中，包括：

处理器；以及

被安排成存储计算机可执行指令的存储器，所述可执行指令在被执行时使所述处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区，包括：根据机器人物理尺寸预生成膨胀信息；所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。

6.一种计算机可读存储介质，其上存储有计算机可执行指令，其中，该计算机可执行指令被处理器执行时使得该处理器：

将整个代价地图分为数个大小相同的瓦片，其中，每个瓦片包含多个不同偏移量的栅格，每个栅格对应一个代价值，每一个瓦片与一个唯一的索引值一一对应；

将路径规划的当前目标坐标送入索引计算器，分别计算出所述当前目标坐标对应的瓦片的索引值和该瓦片内的偏移量；

瓦片管理器根据所述索引值确定待构建的瓦片，根据所述偏移量找到所述待构建的瓦片内对应的栅格；

所述瓦片管理器把对应的栅格返回给路径规划模块和及时瓦片构造器；

及时瓦片构造器建立所述栅格所在的瓦片后放入瓦片缓存区，包括：根据机器人物理尺寸预生成膨胀信息；所述及时瓦片构造器根据机器人的环境地图、机器人的传感器数据以及所述预生成的膨胀信息，建立所述栅格所在的瓦片后放入瓦片缓存区，其中，所述环境地图包括机器人所在环境中的第一障碍物信息，所述传感器数据包括机器人所在环境中的第二障碍物信息，所述第二障碍物信息为所述第一障碍物信息的补充信息；

所述路径规划模块在所述瓦片缓存区内的所述栅格所在的瓦片中获取所述栅格对应的代价值，根据获取到的代价值进行路径规划。