CN113865607A - 路径规划方法、装置、设备及存储介质 - Google Patents

Abstract

本申请实施例公开了一种路径规划方法、装置、设备及存储介质，所述方法包括：对至少两个待配送点进行分组，得到局部路径规划组；根据各所述局部路径规划组中的各所述待配送点，得到各所述局部路径规划组对应的局部路径；根据各所述局部路径，生成所述至少两个待配送点对应的全局路径；通过上述技术方案，降低了对路径规划方法的执行设备的硬件算力要求。

Description

路径规划方法、装置、设备及存储介质

技术领域

本申请实施例涉及路径规划技术领域，尤其涉及一种路径规划方法、装置、设备及存储介质。

背景技术

随着机器人技术的不断发展，机器人开始在人们的生活和工作中发挥作用，其中，移动机器人因其灵活性和机动性，更是在很多场景中能够帮助人们完成相应的任务，例如，在物流运输、电力巡检和室内引导等场景中，移动机器人已经逐步替代人工独立执行指定的工作。

目前，现有的路径规划方法需要一次针对所有待配送点进行路径规划，对其执行设备的硬件算力要求较高。

发明内容

本申请提供一种路径规划方法、装置、设备及存储介质，以降低对路径规划方法执行设备的算力要求。

第一方面，本申请实施例提供了一种路径规划方法，该方法包括：

对至少两个待配送点进行分组，得到局部路径规划组；

根据各所述局部路径规划组中的各所述待配送点，得到各所述局部路径规划组对应的局部路径；

根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。进一步的，所述根据各所述局部路径，生成所述至少两个待配送点对应的全局路径，包括：

根据各所述局部路径和各所述局部路径规划组间的配送顺序，生成所述至少两个待配送点对应的全局路径。

进一步的，所述根据各所述局部路径和各所述局部路径规划组间的配送顺序，生成所述至少两个待配送点对应的全局路径，包括：

根据所述局部路径中起始路径点的位置信息，确定所述局部路径所属局部路径规划组的配送顺序；

根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径。

进一步的，若所述局部路径规划组对应至少两个局部路径，则所述根据所述局部路径规划组的局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径，包括：

分别从各局部路径规划组中选取配送顺序不同的局部路径顺序组合，生成至少一个候选全局路径；

从所述至少一个候选全局路径中，选取目标全局路径。

进一步的，所述从所述至少一个候选全局路径中，选取目标全局路径，包括：

判断所述候选全局路径中不同局部路径规划组的相邻待配送点之间是否存在可行驶路径；

根据判断结果，从所述至少一个候选全局路径中，选取目标全局路径。

进一步的，所述对至少两个待配送点进行分组，得到局部路径规划组，包括：

将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配；

根据匹配结果，将各所述待配送点进行分组，得到所述局部路径规划组。

进一步的，所述方法还包括：

确定各局部路径规划组中的待配送点数量；

将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组。

进一步的，所述将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组，包括：

将所述待配送点数量大于设定数量阈值的局部路径规划组作为待拆分组；

根据所述待拆分组中的待配送点位置信息，将所述待拆分组拆分成至少两个局部路径规划组。

第二方面，本申请实施例还提供了一种路径规划装置，该装置包括：

配送点分组模块，用于对至少两个待配送点进行分组，得到至少一个局部路径规划组；

局部路径生成模块，用于根据各所述局部路径规划组中的各所述待配送点和机器人当前位置，得到各所述局部路径规划组对应的局部路径；

全局路径生成模块，用于根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。

第三方面，本申请实施例还提供了一种电子设备，所述设备包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如第一方面实施例所提供的任意一种路径规划方法。

第四方面，本申请实施例还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如第一方面实施例所提供的任意一种路径规划方法。

本申请实施例通过对至少两个待配送点进行分组，得到局部路径规划组后，根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径，根据各局部路径，生成了至少两个待配送点对应的全局路径。通过上述技术方案，实现了对分组后各局部路径规划组中至少一个待配送点的局部路径规划，在得到各局部路径规划组对应的局部路径后，将局部路径进行合并得到全局路径，从而实现了对机器人所要进行配送的待配送点的整体路径规划。由于本申请中将待配送点分组进行局部路径规划，无需一次对全部待配送点进行全局路径规划，分散了单次路径规划压力，从而降低了对执行设备的硬件算力要求。

附图说明

图1是本申请实施例一提供的一种路径规划方法的流程图；

图2是本申请实施例二提供的一种路径规划方法的流程图；

图3是本申请实施例二提供的一种分组路径规划的示意图；

图4是本申请实施例二提供的一种分组路径规划的示意图；

图5是本申请实施例三提供的一种路径规划方法的流程图；

图6是本申请实施例四提供的一种路径规划装置的示意图；

图7是本申请实施例五提供的一种电子设备的示意图。

具体实施方式

下面结合附图和实施例对本申请作进一步的详细说明。可以理解的是，此处所描述的具体实施例仅仅用于解释本申请，而非对本申请的限定。另外还需要说明的是，为了便于描述，附图中仅示出了与本申请相关的部分而非全部结构。

在更加详细地讨论示例性实施例之前应当提到的是，一些示例性实施例被描述成作为流程图描绘的处理或方法。虽然流程图将各步骤描述成顺序的处理，但是其中的许多步骤可以被并行地、并发地或者同时实施。此外，各步骤的顺序可以被重新安排。当其操作完成时所述处理可以被终止，但是还可以具有未包括在附图中的附加步骤。所述处理可以对应于方法、函数、规程、子例程、子程序等等。

实施例一

图1为本申请实施例一提供的一种路径规划方法的流程图。本申请实施例可适用于对机器人所要进行配送的待配送点，进行路径规划的情况。该方法可以由一种路径规划装置来执行，该装置可以由软件和/或硬件的方式实现，并具体配置于电子设备中，该电子设备可以是移动终端或固定终端。例如，电子设备可以是机器人。该电子设备还可以是服务端，例如对机器人进行管理控制的后台服务器。

参见图1，本申请实施例提供的路径规划方法，包括：

S110、对至少两个待配送点进行分组，得到局部路径规划组。

其中，待配送点是指机器人所要进行配送的配送点，也即待配送的目标点，该目标点具体可以是在送餐场景中，送餐机器人对待进行送餐的餐桌进行配送的情况，当然，该目标点也可以是其他应用场景下的待配送点。

本实施例中，分组后的局部路径规划组包括至少一个待配送点，这些待配送点在特定属性上具有一致的特征，例如，待配送点的地理位置相近，或者，待配送点分属于同一个小区或同一栋楼等。

可选地，可以根据待配送点的位置，对待配送点进行聚类分析，将位置相近的待配送点划分到同一个局部路径规划组。具体地，进行聚类分析所采用的算法可以是K-Means算法(K-Means Clustering Algorithm，K均值聚类算法)，其中，K为聚类的个数，也即本实施例中局部路径规划组的个数。在具体采用K-Means算法对待配送点进行分组时，可以根据待配送点的数量来合理确定K值。通过将位置相近的待配送点划分到同一局部路径规划组，能够使位置相近的点在配送的先后顺序上也比较接近，进而提升配送效率，避免例如，在目标点A和B的位置在同一条路径上且相距很近，机器人却在目标点A执行完配送任务后，接着去配送距离很远的目标点C，然后再对目标点B进行配送等情况导致的机器人走很多重复弯路，配送效率低的问题。

或者可选地，还可以根据用户的输入数据，对至少两个待配送点进行分组，以得到至少一个局部路径规划组，其中，用户的输入数据可以是用户的分组偏好数据，也即由用户来确定待配送点的分组情况。

在一些实施例中，还可以根据待配送点与机器人当前位置的距离远近进行分组，从而得到预设数量局部路径规划组，局部路径规划组的数量可以根据对距离的划分等级进行确定，如可以将待配送点与机器人当前位置的距离划分成三种距离等级，包括很近、较近和较远三种等级。

例如，可以将距离机器人当前位置较近(如距离小于100米)的部分待配送点划分到同一个局部路径规划组；可以将距离机器人当前位置较远(如距离大于等于100米小于200米)的部分待配送点划分到同一个局部路径规划组；可以将距离机器人当前位置较远(如距离大于等于200米)的部分待配送点划分到同一个局部路径规划组。

可以理解的是，分组方式有多种形式，除了上述提到的分组方式之外，还有其他的分组方式，可以根据实际情况选择合适的分组方式。

S120、根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径。

其中，机器人是指能够在各类作业环境中自主地或交互地执行各种拟人任务的智能机器人。机器人的具体类型通常包括但不限于送餐机器人、物流机器人和送货机器人等。

本实施例中，可以根据各局部路径规划组中的各待配送点的位置，采用预设的局部路径规划方法，来计算得到各局部路径规划组对应的局部路径。

其中，预设的局部路径规划方法可以是根据各局部路径规划组中的各待配送点的位置关系，分别确定各局部路径规划组内全部配送点所构建的可行驶路径，在将所有可行驶路径统计完毕后，可以根据预设的路径选取方法(如人为进行选取或预设规则选取)，确定出局部路径规划组对应的局部路径。其中，可以根据需求，确定出至少一条局部路径规划组对应的局部路径，当然，也可以确定出至少两条局部路径规划组对应的局部路径。

在一些实施例中，在考虑机器人实际的工作环境的情况下(如考虑拥堵情况)，还可以采用基于时间最短原则的路径规划方法，计算各局部路径规划组对应的局部路径；或者，还可以采用基于路径最短原则的路径规划方法，计算各局部路径规划组对应的局部路径。

可以理解的是，局部路径规划方法有多种形式，除了上述提到的局部路径规划方法之外，还有其他的局部路径规划方法，可以根据实际情况选择合适的局部路径规划方法，本申请实施例对此不做具有限定。

S130、根据各局部路径，生成至少两个待配送点对应的全局路径。

其中，全局路径由各局部路径按照设定规则进行组合，生成的机器人对所有待配送点进行配送的全局路径。

例如，存在三个局部路径A、B和C，则总共可以生成A-B-C、A-C-B、B-A-C、B-C-A、C-A-B和C-B-A总共6种全局路径。其中，机器人会对全局路径中组合顺序靠前的局部路径中的待配送点进行优先配送。

本实施例中，通过计算各局部路径规划组的局部路径，将各局部路径进行合并，最后统计得到的全局路径的技术方案，能够利用有限的机器算力，计算至少两个待配送点(可以计算多于20个待配送点)的相对较优路径，相较于现有技术一次性对所有待配送点进行整体路径规划，本申请先局部再整体能够减小运算量，并且降低了对执行路径规划方法的算力要求。在一个可选实施例中，若路径规划方法的执行设备为机器人，则降低了机器人的硬件成本；若路径规划方法的执行设备为后台服务器，则在降低了服务器的硬件成本的同时，还能够适配路径规划方法的高并发执行情况。

在一个可选实施例中，可以直接将各局部路径随机组合，生成全局路径，以使目标机器人按照该全局路径前往各待配送点进行物品获取获配送。

示例性的，在订单货物分拣场景中，若某笔订单中包括多个目标物品，且不同目标物品放置在待配送点中，因此，可以针对各局部路径规划组中的待配送点规划局部路径，并通过随机组合的方式，生成全局路径。在生成全局路径之后，告知机器人前往全局路径的起始点或其中一个待配送点，开始沿着全局路径获取目标物品，直至全部目标物品获取完毕。或者可选的，在机器人数量较多时，告知距离全局路径的起始点较近的目标机器人，开始沿着全局路径进行目标物品的获取，直至全部目标物品获取完毕。

在另一可选实施例中，还可以确定各局部路径规划组间的配送顺序，进而根据各局部路径和各局部路径规划组间的配送顺序，生成至少两个待配送点对应的全局路径。

可选的，可以在确定各局部路径规划组时人为设定各局部路径规划组间的配送顺序，并预先存储各局部路径规划组和相应配送顺序之间的对应关系，后续根据该对应关系，生成全局路径。

可选的，还可以根据各局部路径规划组之间的相对位置关系和/或机器人停靠区域，确定各局部路径规划组间的配送顺序。例如，靠近机器人停靠区域的局部路径规划组的配送顺序靠前，远离机器人停靠区域的局部路径规划组的配送顺序靠后等。

可选地，可以根据预设偏好，人为预先为各局部路径设置配送优先级，其中，优先级高的局部路径中的待配送点优先进行配送。例如，某一局部路径中的待配送点对时间要求很严格，希望机器人能够在较短的时间内进行配送，此时可以人为预先将该局部路径设置一个较高的配送优先级。

例如，在机器人送餐场景中，可以根据各待配送点所需配送的餐品种类和重量等属性中的至少一种，确定各局部路径的配送优先级，进而根据所确定优先级进行局部路径配送顺序的确定。延续前例，若局部路径C的优先级较高，则可以生成的全局路径为C-A-B和C-B-A。

可选地，计算各局部路径规划组内部各待配送点的已等待时长之和，比较各局部路径规划组间的已等待时长之和，值最大的局部路径规划组优先级最高。以机器人送餐场景为例，能够避免用户长期等待，提升用户的用餐体验。

或者可选地，还可以根据各局部路径与机器人的位置关系，确定各局部路对应的全局路径。例如，可以根据各局部路径中待配送点与机器人的距离远近，确定各局部路径在全局路径中的组合顺序。

在一些实施例中，在对优先级高的局部路径进行配送完毕之后，对于处于同一优先级的各局部路径，可以根据各局部路径与机器人的位置关系，确定各局部路径在全局路径中的组合顺序。

可以理解的是，根据各局部路径，生成所有待配送点对应的全局路径的方法有多种形式，可以根据实际情况进行选取。

需要说明的是，当各局部路径规划组间的配送顺序确定后，首个配送的局部路径规划组可以基于机器人当前位置和该局部路径规划组中的各待配送点的位置信息，进行局部路径规划；其他局部路径规划组，则根据前一配送顺序的局部路径规划组中的终止路径点的位置信息和自身局部路径规划组中的各待配送的位置信息，进行自身局部路径规划；相应的，按照各局部路径规划组间的配送顺序，将各局部路径组合，得到全局路径。

值得注意的是，通过借助各局部路径规划组的局部路径，以及各局部路径规划组间的配送顺序，进行全局路径规划，用于指示机器人根据该全局路径进行物品获取或配送。机器人依照该全局路径行驶时，能够避免由于忽略局部路径规划组间的配送顺序，导致行驶效率较低或相同的待配送点所生成全局路径规划结果再现性差等问题。

本申请实施例通过对至少两个待配送点进行分组，得到局部路径规划组后，根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径，根据各局部路径，生成了至少两个待配送点对应的全局路径。通过上述技术方案，实现了对分组后各局部路径规划组中至少一个待配送点的局部路径规划，在得到各局部路径规划组对应的局部路径后，将局部路径进行合并得到全局路径，从而实现了对机器人所要进行配送的待配送点的整体路径规划。由于本申请中将待配送点分组进行局部路径规划，无需一次对全部待配送点进行全局路径规划，分散了单次路径规划压力，从而降低了对执行设备的硬件算力要求。

实施例二

图2为本申请实施例二提供的一种路径规划方法的流程图，本实施例是在上述实施例的基础上，对上述方案的优化。

进一步地，将操作“根据各所述局部路径，生成所述至少两个待配送点对应的全局路径”，细化为“根据所述局部路径中起始路径点的位置信息，确定所述局部路径所属局部路径规划组的配送顺序；根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径”，以明确全局路径的生成过程。

其中与上述实施例相同或相应的术语的解释在此不再赘述。

参见图2，本实施例提供的路径规划方法，包括：

S210、对至少两个待配送点进行分组，得到局部路径规划组。

S220、根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径。

S230、根据局部路径中起始路径点的位置信息，确定局部路径所属局部路径规划组的配送顺序。

其中，局部路径中起始路径点是指在局部路径中，机器人最先进行配送的待配送点。具体地，可以将各局部路径中距离机器人当前位置最近的待配送点作为局部路径中起始路径点。

本实施例中，配送顺序优先的局部路径规划组，机器人会优先为该局部路径规划组中的待配送点进行配送。

可选地，可以根据各局部路径中起始路径点的位置信息和机器人的位置信息，确定各局部路径中起始路径点与机器人的配送距离，并根据配送距离，来确定局部路径所属局部路径规划组的配送顺序。

具体地，局部路径中起始路径点与机器人的配送距离越短，机器人会优先为该起始路径点所在的局部路径规划组进行配送。

或者可选地，也可以根据各局部路径中起始路径点的位置信息和机器人的位置信息，确定机器人到各局部路径中起始路径点的配送时长，并根据配送时长，来确定局部路径所属局部路径规划组的配送顺序。

具体地，机器人到局部路径中起始路径点的配送时间越短，机器人会优先为该起始路径点所在的局部路径规划组进行配送。

可以理解的是，对各局部路径规划组的配送顺序的确定有多种方式，可以根据实际情况进行设置，当然也可以根据偏好为各局部路径规划组确定配送顺序，如某一局部路径规划组所在区域属于需要优先进行配送的区域，则可以优先对该局部路径规划组进行配送。

S240、根据各局部路径和对应配送顺序，生成至少两个待配送点对应的全局路径。

参见图3所示的一种分组路径规划的示意图，图中示例性给出了有A、B和C总共三组局部路径规划组的情况。其中，A组局部路径规划组包括P1、P2、P4和P5共4个待配送点，B组局部路径规划组包括P3、P7和P8共3个待配送点，C组局部路径规划组包括P6、P9、P10、P11和P12共5个待配送点；C组局部路径规划组的配送顺序优先级大于A组局部路径规划组，A组局部路径规划组的配送顺序优先级大于B组局部路径规划组。根据各局部路径和对应配送顺序，可以将各局部路径规划组A、B和C的局部路径按配送顺序优先级进行依次连接，生成所有待配送点对应的全局路径。

具体地，根据图3生成的全局路径，机器人将从待配送点P12所在的局部路径规划组C进行配送，在机器人到达待配送点P12后，会根据C组的局部路径，对C组中的其他待配送点(包括P11、P10、P9和P6)进行依次配送；当机器人完成对C组的配送后，机器人会来到A组的起始路径点P4，之后会根据A组的局部路径，对A组中的其他待配送点(包括P2、P5和P1)进行依次配送；当机器人完成对A组的配送后，机器人会来到B组的起始路径点P8，之后会根据B组的局部路径，对B组中的其他待配送点(包括P7和P3)进行依次配送，从而完成对所有待配送点的配送。

可选地，若所述局部路径规划组对应至少两个局部路径，则所述根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径，包括：分别从各局部路径规划组中选取配送顺序不同的局部路径顺序组合，生成至少一个候选全局路径；从所述至少一个候选全局路径中，选取目标全局路径。

其中，局部路径规划组对应至少两个局部路径是指，在该局部路径规划组中，对局部路径规划组中的各待配送点进行配送的路径至少有两个。

目标全局路径是指选取的机器人进行配送的最终路径。

参见图4所示的一种分组路径规划的示意图，该图中待配送点的位置和数量，以及机器人的当前位置与图3中的一致。假设A组只有1个局部路径R11(P4-P2-P5-P1)，B组也只有1个局部路径R21(P8-P7-P3)，而C组有2个局部路径R31(P9-P10-P11-P12-P6)和R32(P12-P11-P10-P9-P6)，则对应生成的全局路径可以包括两种局部路径组合，分别为局部路径组合R11、R21和R31，以及R11、R21和R32。

其中，不同的局部路径组合，可以对应不同的配送顺序。假设在局部路径R11、R21和R31中，配送顺序为从R11到R21，从R21再到R31，则相应生成的全局路径为R11-R21-R31，也即图4中示例性给出的分组路径规划的示意图；在局部路径R11、R21和R32中，配送顺序为从R32到R11，从R11再到R21，则相应生成的候选全局路径为R32-R11-R21，也即图3中示例性给出的分组路径规划的示意图。

当然，图3和图4中示出的分组路径规划的示意图仅为一种较简单的情况，实际情况更为复杂，如每个局部路径规划组均可以有多种不同的局部路径。

可以理解的是，若局部路径规划组对应至少两个局部路径，则还可以从各局部路径规划组中选取配送顺序不同的局部路径顺序组合，生成至少一个候选全局路径，保证了全局路径的多样性，从而便于进行最优全局路径的选取。

可选地，所述从所述至少一个候选全局路径中，选取目标全局路径，包括：判断所述候选全局路径中不同局部路径规划组的相邻待配送点之间是否存在可行驶路径；根据判断结果，从所述至少一个候选全局路径中，选取目标全局路径。

本实施例中，可以结合机器人的工作环境，判断相邻的待配送点是否存在可行驶路径。

继续参见图4所示的一种分组路径规划的示意图，P1为A组局部路径规划组的结束路径点，P8为B组局部路径规划组的起始路径点，P1和P8为相邻的待配送点，在待配送点P1和P8之间存在实际可以通行的路径；以此类似，依次确定全局路径中其他相邻的待配送点是否也存在可行驶路径，若确认所有相邻的待配送点均存在可行驶路径，则可以保留该条候选全局路径。

可以理解的是，通过可行驶路径的筛选机制，从至少一个候选全局路径中，筛选出了可以顺利通行的目标全局路径，确保了目标全局路径的可行性。

在一些实施例中，通过可行驶路径的筛选机制，从至少一个候选全局路径中筛选出的全局路径可能不止一个，此时还可以根据路径最短原则或者配送时间最短原则(可以考虑实时交通信息)，对上述筛选后的全局路径进行进一步筛选，从上述全局路径选取出最终机器人进行配送所使用的目标全局路径，进一步提升了配送效率。

可选地，设置有第一等待时长阈值，计算各个候选全局路径下各待配送点的已等待时长以及按照对应候选全局路径进行配送时各待配送点的配送时长，进而得到各个候选全局路径下各待配送点的预计等待时长。即，预计等待时长等于已等待时长加上配送时长。

优选地，选取能够使待配送点的预计等待时长在第一等待时长阈值范围内数量最多的候选全局路径作为目标全局路径。例如，第一等待时长阈值为20分钟，则选取能使预计等待时长小于等于20分钟的待配送点的数量最多的候选全局路径作为目标全局路径。即选取能使尽量多的配送点按时完成配送的候选全局路径作为目标全局路径，尤其是在送餐环境中，能够尽量确保各待配送点的配送不超时，进一步提升用户体验。

进一步地，还设置有第二等待时长阈值，第二等待时长阈值为等待上限阈值，目标全局路径中各待配送点的预计等待时长均需小于或等于第二等待时长阈值，第二等待时长阈值大于第一等待时长阈值，避免部分待配送点配送严重超时，影响用户体验。若各候选全局路径中某个待配送点预计等待时长均超时，则可剔除该点，将该点改为人工配送，基于剩下的待配送点生成全局路径，确保配送效率和用户体验。

本申请实施例在上述实施例的基础上，对全局路径的生成过程进行了具体细化，通过根据局部路径中起始路径点的位置信息，确定了局部路径所属局部路径规划组的配送顺序，之后再根据各局部路径和对应配送顺序，生成了至少两个待配送点对应的全局路径。通过上述技术方案，通过考虑局部路径中起始路径点的位置信息，确定了各局部路径的配送顺序，根据该配送顺序，将局部路径进行合并得到了全局路径，对全局路径的生成过程进行了优化，一方面避免了忽略配送顺序导致全局路径规划结果再现性差的问题，另一方面还提高了机器人的配送效率。

在一个可选实施例中，可以通过并行执行的方式，分别确定各局部路径规划组的局部路径，再得到各局部路径规划组间的配送顺序，进而生成全局路径，能够显著提升全局路径生成效率，进而提高了机器人的配送效率。

实施例三

图5为本申请实施例三提供的一种路径规划方法的流程图，本实施例是在上述实施例的基础上，对上述方案的优化。

进一步地，将操作“对至少两个待配送点进行分组，得到至少一个局部路径规划组”，细化为“将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配；根据匹配结果，将各所述待配送点进行分组，得到至少一个所述局部路径规划组”，以明确局部路径规划组的生成过程。

其中与上述实施例相同或相应的术语的解释在此不再赘述。

参见图5，本实施例提供的路径规划方法，包括：

S310、将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配。

其中，机器人的作业环境可以是餐厅、车间或者分拣中心等。

预设规划组是指结合机器人的作业环境，预先将位置相对集中靠近的待配送点进行逻辑编组，得到的预设规划组。

例如，在机器人送餐场景中，可以根据餐厅的就餐区域将餐厅划分为多个不同的预设规划组，如可以将餐厅划分为A区、B区、C区、D区和E区共5个预设规划组。其中，各预设规划组至少包括一个预先确定的候选配送点。

当然，在机器人的作业环境发生改变的时候，可以及时对预设规划组中的各候选配送点进行调整，以使对预设规划组中各候选配送点的分组设置符合实际。

具体地，所述将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配的方式可以是：根据各待配送点的位置信息，将各待配送点的位置与作业环境中预设规划组中的各候选配送点的位置进行匹配；或者，还可以根据各待配送点的标识信息，将各待配送点的标识与作业环境中预设规划组中的各候选配送点的标识进行匹配。

S320、根据匹配结果，将各待配送点进行分组，得到局部路径规划组。

本实施例中，考虑到分组后各局部路径规划组中待配送点数量存在较大差异，影响对局部路径规划组的局部路径规划，因此，还可以进一步确定各局部路径规划组中的待配送点数量；将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组。

其中，设定数量阈值是指预先为局部路径规划组中的待配送点设置的数量限制要求，如分组后的局部路径规划组中待配送点的数量不得大于5个。当然，局部路径规划组中待配送点的数量也可以是其他数量限制要求，如8个或3个等，具体数量限制要求可以根据实际情况进行合理设置，本申请实施例对此不做任何限定。

在一些实施例中，若分组后的局部路径规划组中待配送点的数量大于设定数量阈值，则可以进一步对该局部路径规划组进行再次分组，以满足局部路径规划组对待配送点数量的限制要求。

可以理解的是，通过阈值比较的方式，将局部路径规划组中待配送点的数量进行了限制，使得各局部路径规划组中待配送点的数量得到合理的控制，有利于后续对局部路径规划组中的待配送点进行局部路径规划，减小运算量。

具体地，所述将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组，包括：将所述待配送点数量大于设定数量阈值的局部路径规划组作为待拆分组；根据所述待拆分组中的待配送点位置信息，将所述待拆分组拆分成至少两个局部路径规划组。

本实施例中，根据待拆分组中的待配送点位置信息，可以采用聚类分析方法如K-Means算法，将待拆分组中位置相近的待配送点拆分到同一个局部路径规划组；或者，为了简单起见，可以在确定出待拆分组的中心点后，将位于机器人与中心点连线左边的待配送点拆分到同一个局部路径规划组，将位于机器人与中心点连线右边的待配送点拆分到同一个局部路径规划组。当然，还可以采用其他的分组方法(如人工分组方法或者预设规划组匹配方法)对待拆分组进行分组。

需要注意的是，在对所有待配送点进行第一次分组时，所使用的分组方法与上述对待拆分组进行分组的分组方法可以相同也可以不同，具体可以根据实际情况进行确定。

可以理解的是，考虑待配送点位置信息，对待拆分组中的待配送点进行了合理拆分，有利于后续对局部路径规划组中的待配送点进行局部路径规划。

S330、根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径。

S340、根据各局部路径，生成至少两个待配送点对应的全局路径。

本申请实施例在上述实施例的基础上，对局部路径规划组的生成过程进行了具体细化，通过将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配，并根据匹配结果，将各待配送点进行分组，得到至少一个局部路径规划组；通过上述技术方案，根据作业环境中预设规划组，对待配送点进行合理分组，减少了进行局部路径规划组确定过程的计算量，从而优化了局部路径规划组的生成过程，有利于对机器人所要进行配送的待配送点进行路径规划，提高机器人的配送效率。

实施例四

图6是本申请实施例四提供的一种路径规划装置的结构示意图。参见图6，本申请实施例提供的一种路径规划装置，该装置包括：配送点分组模块410、局部路径生成模块420和全局路径生成模块430。

配送点分组模块410，用于对至少两个待配送点进行分组，得到局部路径规划组；

局部路径生成模块420，用于根据各所述局部路径规划组中的各所述待配送点，得到各所述局部路径规划组对应的局部路径；

全局路径生成模块430，用于根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。

本申请实施例通过对至少两个待配送点进行分组，得到局部路径规划组后，根据各局部路径规划组中的各待配送点，得到各局部路径规划组对应的局部路径，根据各局部路径，生成了至少两个待配送点对应的全局路径。通过上述技术方案，实现了对分组后各局部路径规划组中至少一个待配送点的局部路径规划，在得到各局部路径规划组对应的局部路径后，将局部路径进行合并得到全局路径，从而实现了对机器人所要进行配送的待配送点的整体路径规划。由于本申请中将待配送点分组进行局部路径规划，无需一次对全部待配送点进行全局路径规划，分散了单次路径规划压力，从而降低了对执行设备的硬件算力要求。

进一步地，所述配送点分组模块410，包括：

匹配子模块，用于将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配；

第一配送点分组子模块，用于根据匹配结果，将各所述待配送点进行分组，得到所述局部路径规划组。

进一步地，所述配送点分组模块410，还包括：

配送点数量确定子模块，用于确定各局部路径规划组中的待配送点数量；

第二配送点分组子模块，用于将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组。

进一步地，所述全局路径生成模块403，包括：

全局路径生成子模块，用于根据各所述局部路径和各所述局部路径规划组间的配送顺序，生成所述至少两个待配送点对应的全局路径。

进一步的，全局路径生成子模块，包括：

配送顺序确定单元，用于根据所述局部路径中起始路径点的位置信息，确定所述局部路径所属局部路径规划组的配送顺序；

路径生成单元，用于根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径。

进一步地，所述路径生成单元，包括：

候选路径生成子单元，用于若所述局部路径规划组对应至少两个局部路径，则分别从各局部路径规划组中选取配送顺序不同的局部路径顺序组合，生成至少一个候选全局路径；

路径选取子单元，用于从所述至少一个候选全局路径中，选取目标全局路径。

进一步地，所述路径生成子单元，包括：

判断从单元，用于判断所述候选全局路径中不同局部路径规划组的相邻待配送点之间是否存在可行驶路径；路径生成从单元，用于根据判断结果，从所述至少一个候选全局路径中，选取目标全局路径。

本申请实施例所提供的路径规划装置可执行本申请任意实施例所提供的路径规划方法，具备执行方法相应的功能模块和有益效果。

实施例五

图7为本申请实施例五提供的一种电子设备的结构图。图7示出了适于用来实现本申请实施方式的示例性电子设备512的框图。图7显示的电子设备512仅仅是一个示例，不应对本申请实施例的功能和使用范围带来任何限制。

如图7所示，电子设备512以通用计算设备的形式表现。电子设备512的组件可以包括但不限于：一个或者多个处理器或者处理单元516，系统存储器528，连接不同系统组件(包括系统存储器528和处理单元516)的总线518。

总线518表示几类总线结构中的一种或多种，包括存储器总线或者存储器控制器，外围总线，图形加速端口，处理器或者使用多种总线结构中的任意总线结构的局域总线。举例来说，这些体系结构包括但不限于工业标准体系结构(ISA)总线，微通道体系结构(MAC)总线，增强型ISA总线、视频电子标准协会(VESA)局域总线以及外围组件互连(PCI)总线。

电子设备512典型地包括多种计算机系统可读介质。这些介质可以是任何能够被电子设备512访问的可用介质，包括易失性和非易失性介质，可移动的和不可移动的介质。

系统存储器528可以包括易失性存储器形式的计算机系统可读介质，例如随机存取存储器(RAM)530和/或高速缓存存储器532。电子设备512可以进一步包括其它可移动/不可移动的、易失性/非易失性计算机系统存储介质。仅作为举例，存储系统534可以用于读写不可移动的、非易失性磁介质(图7未显示，通常称为“硬盘驱动器”)。尽管图7中未示出，可以提供用于对可移动非易失性磁盘(例如“软盘”)读写的磁盘驱动器，以及对可移动非易失性光盘(例如CD-ROM，DVD-ROM或者其它光介质)读写的光盘驱动器。在这些情况下，每个驱动器可以通过一个或者多个数据介质接口与总线518相连。系统存储器528可以包括至少一个程序产品，该程序产品具有一组(例如至少一个)程序模块，这些程序模块被配置以执行本申请各实施例的功能。

具有一组(至少一个)程序模块542的程序/实用工具540，可以存储在例如系统存储器528中，这样的程序模块542包括——但不限于——操作系统、一个或者多个应用程序、其它程序模块以及程序数据，这些示例中的每一个或某种组合中可能包括网络环境的实现。程序模块542通常执行本申请所描述的实施例中的功能和/或方法。

电子设备512也可以与一个或多个外部设备514(例如键盘、指向设备、显示器524等)通信，还可与一个或者多个使得用户能与该电子设备512交互的设备通信，和/或与使得该电子设备512能与一个或多个其它计算设备进行通信的任何设备(例如网卡，调制解调器等等)通信。这种通信可以通过输入/输出(I/O)接口522进行。并且，电子设备512还可以通过网络适配器520与一个或者多个网络(例如局域网(LAN)，广域网(WAN)和/或公共网络，例如因特网)通信。如图所示，网络适配器520通过总线518与电子设备512的其它模块通信。应当明白，尽管图7中未示出，可以结合电子设备512使用其它硬件和/或软件模块，包括但不限于：微代码、设备驱动器、冗余处理单元、外部磁盘驱动阵列、RAID系统、磁带驱动器以及数据备份存储系统等。

处理单元516通过运行存储在系统存储器528中的多个程序中其他程序的至少一个，从而执行各种功能应用以及数据处理，例如实现本申请实施例所提供的任意一种路径规划方法。

实施例六

本申请实施例六还提供了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现本申请任一实施例所提供的一种路径规划方法，该方法包括：

对至少两个待配送点进行分组，得到至少一个局部路径规划组；根据各所述局部路径规划组中的各所述待配送点和机器人当前位置，得到各所述局部路径规划组对应的局部路径；根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。

通过以上关于实施方式的描述，所属领域的技术人员可以清楚地了解到，本申请可借助软件及必需的通用硬件来实现，当然也可以通过硬件实现，但很多情况下前者是更佳的实施方式。基于这样的理解，本申请的技术方案本质上或者说对现有技术做出贡献的部分可以以软件产品的形式体现出来，该计算机软件产品可以存储在计算机可读存储介质中，如计算机的软盘、只读存储器(Read-Only Memory，ROM)、随机存取存储器(RandomAccess Memory，RAM)、闪存(FLASH)、硬盘或光盘等，包括若干指令用以使得一台计算机设备(可以是个人计算机，服务器，或者网络设备等)执行本申请各个实施例所述的方法。

值得注意的是，上述路径规划装置的实施例中，所包括的各个单元和模块只是按照功能逻辑进行划分的，但并不局限于上述的划分，只要能够实现相应的功能即可；另外，各功能单元的具体名称也只是为了便于相互区分，并不用于限制本申请的保护范围。

注意，上述仅为本申请的较佳实施例及所运用技术原理。本领域技术人员会理解，本申请不限于这里所述的特定实施例，对本领域技术人员来说能够进行各种明显的变化、重新调整和替代而不会脱离本申请的保护范围。因此，虽然通过以上实施例对本申请进行了较为详细的说明，但是本申请不仅仅限于以上实施例，在不脱离本申请构思的情况下，还可以包括更多其他等效实施例，而本申请的范围由所附的权利要求范围决定。

Claims (11)

1.一种路径规划方法，其特征在于，包括：

对至少两个待配送点进行分组，得到局部路径规划组；

根据各所述局部路径规划组中的各所述待配送点，得到各所述局部路径规划组对应的局部路径；

根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。

2.根据权利要求1所述的方法，其特征在于，所述根据各所述局部路径，生成所述至少两个待配送点对应的全局路径，包括：

根据各所述局部路径和各所述局部路径规划组间的配送顺序，生成所述至少两个待配送点对应的全局路径。

3.根据权利要求2所述的方法，其特征在于，所述根据各所述局部路径和各所述局部路径规划组间的配送顺序，生成所述至少两个待配送点对应的全局路径，包括：

根据所述局部路径中起始路径点的位置信息，确定所述局部路径所属局部路径规划组的配送顺序；

根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径。

4.根据权利要求3所述的方法，其特征在于，若所述局部路径规划组对应至少两个局部路径，则所述根据各所述局部路径和对应配送顺序，生成所述至少两个待配送点对应的全局路径，包括：

分别从各局部路径规划组中选取配送顺序不同的局部路径顺序组合，生成至少一个候选全局路径；

从所述至少一个候选全局路径中，选取目标全局路径。

5.根据权利要求4所述的方法，其特征在于，所述从所述至少一个候选全局路径中，选取目标全局路径，包括：

判断所述候选全局路径中不同局部路径规划组的相邻待配送点之间是否存在可行驶路径；

根据判断结果，从所述至少一个候选全局路径中，选取目标全局路径。

6.根据权利要求1所述的方法，其特征在于，所述对至少两个待配送点进行分组，得到局部路径规划组，包括：

将各待配送点与作业环境中预设规划组中的各候选配送点进行匹配；

根据匹配结果，将各所述待配送点进行分组，得到所述局部路径规划组。

7.根据权利要求1所述的方法，其特征在于，所述方法还包括：

确定各所述局部路径规划组中的待配送点数量；

将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组。

8.根据权利要求7所述的方法，其特征在于，所述将所述待配送点数量大于设定数量阈值的局部路径规划组，拆分成至少两个局部路径规划组，包括：

将所述待配送点数量大于设定数量阈值的局部路径规划组作为待拆分组；

根据所述待拆分组中的待配送点位置信息，将所述待拆分组拆分成至少两个局部路径规划组。

9.一种路径规划装置，其特征在于，包括：

配送点分组模块，用于对至少两个待配送点进行分组，得到局部路径规划组；

局部路径生成模块，用于根据各所述局部路径规划组中的各所述待配送点，得到各所述局部路径规划组对应的局部路径；

全局路径生成模块，用于根据各所述局部路径，生成所述至少两个待配送点对应的全局路径。

10.一种电子设备，其特征在于，包括：

一个或多个处理器；

存储装置，用于存储一个或多个程序，

当所述一个或多个程序被所述一个或多个处理器执行，使得所述一个或多个处理器实现如权利要求1-8中任一项所述的一种路径规划方法。

11.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1-8中任一项所述的一种路径规划方法。

Images