高速分拣机器人集中式调度实时路径规划方法及装置与流程

1.本发明涉及分拣机器人路径规划技术领域，尤其涉及一种高速分拣机器人集中式调度实时路径规划方法及装置。


背景技术：

2.新型轻小包裹高速分拣机器人系统在运行时不需要搭建专用的分拣平台，可以在地面上进行分拣，具有基于需求的变化动态调整机器人数量、分拣区域形状和面积、以及随时随地快速部署分拣的特征，极具应用前景。而对于大规模的高速分拣机器人系统，往往包含多种类型的机器人以及多种类型的任务，如分拣机器人、空料箱搬运机器人以及满料箱搬运机器人、分拣任务、空料箱搬运任务以及满料箱搬运任务等。
3.目前的分拣机器人系统在对机器人的行驶路径进行规划时仅仅考虑了单一类型的分拣机器人和分拣任务，其在进行机器人路径规划时大多都采用传统的启发式算法实现，该方法在仅具有单一类型机器人和单一类型任务的小规模场景下的分拣系统中虽然可完成机器人的路径规划，但该路径规划方法存在着求解质量较低、求解时间长并且容易陷入局部最优解的缺点；尤其是在多类型机器人和多类型任务的复杂场景下，随着机器人数据的增加和环境复杂度的不断增大，现有技术中普遍采用的路径规划方法无法适应环境规模的动态变化，因而无法为具有多类型机器人和多类型任务的复杂场景下的分拣系统中的各机器人规划较佳的行驶路径，从而导致系统调度效率低以及作业成本高。因此，在多类型机器人和多类型任务的复杂场景下如何为各机器人规划较佳的行驶路径是亟待解决的技术问题。


技术实现要素：

4.有鉴于此，本发明提供了一种高速分拣机器人集中式调度实时路径规划方法及装置，以解决现有技术中存在的一个或多个问题。
5.根据本发明的一个方面，本发明公开了一种高速分拣机器人集中式调度实时路径规划方法，所述方法包括：获取机器人集合，所述机器人集合包括用于执行分拣任务的分拣机器人集合、用于执行空料箱搬运任务的空料箱搬运机器人集合和用于执行满料箱搬运任务的满料箱搬运机器人集合；构建初始种群，所述初始种群内的个体为机器人优先级序列；基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径；构建所述分拣机器人执行其行驶路径的第一行驶成本、所述空料箱搬运机器人执行其行驶路径的第二行驶成本以及所述满料箱搬运机器人执行其行驶路径的第三行驶成本，基于所述第一行驶成本、第二行驶成本以及第三行驶成本确定成本目标函数，基于所述成本目标函数计算各个体的适应度值；
基于各个体的适应度值确定各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的最优行驶路径。
6.在本发明的一些实施例中，所述方法还包括：对所述初始种群内的个体进行遗传操作得到新种群。
7.在本发明的一些实施例中，对所述初始种群内的个体进行遗传操作得到新种群，包括：对所述初始种群内的个体进行选择操作、交叉操作以及变异操作得到新种群。
8.在本发明的一些实施例中，基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径，包括：在第一时间步中：获取各所述机器人的初始状态，并将各所述初始状态存储至open表中，基于各所述机器人的初始状态构建时间步约束集；其中，所述初始状态包括各机器人在第一时间步的位置信息，所述时间步约束集中的各约束包括时间步信息以及机器人的位置信息；将第一机器人的初始状态添加至close表中，在所述第一机器人的初始状态与所述第一机器人的目标位置不同时，基于所述时间步约束集和所述第一机器人的初始状态确定第一机器人在第一时间步中可扩展的第一父代子状态，基于确定的所述第一父代子状态更新所述open表；基于评价函数确定所述第一父代子状态中的第一最优父代子状态，基于所述时间步约束集和第一最优父代子状态确定第一机器人在第一时间步中可扩展的第一子代子状态，基于评价函数确定所述第一子代子状态中的第一最优子代子状态和第一次优子代子状态，基于确定的所述第一最优子代子状态和第一次优子代子状态更新所述时间步约束集；将第二机器人的初始状态添加至close表中，在所述第二机器人的初始状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集和所述第二机器人的初始状态确定第二机器人在第一时间步中可扩展的第三父代子状态，基于确定的所述第三父代子状态更新所述open表；基于评价函数确定所述第三父代子状态中的第三最优父代子状态，基于更新后的所述时间步约束集和第三最优父代子状态确定第二机器人在第一时间步中可扩展的第三子代子状态，基于评价函数确定所述第三子代子状态中的第三最优子代子状态和第三次优子代子状态，基于确定的所述第三最优子代子状态和第三次优子代子状态更新所述时间步约束集。
9.在本发明的一些实施例中，所述方法还包括：在第二时间步中：将在第一时间步中确定的所述第一最优父代子状态添加至close表中，在所述第一机器人的第一最优父代子状态与所述第一机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第一最优子代子状态和第一次优子代子状态中的其中一个作为所述第一机器人在第二时间步中的第二最优父代子状态，基于更新后的时间步约束集和所述第二最优父代子状态确定第一机器人在第二时间步可扩展的第二子代子状态，基于评价函数确定第二子代子状态中的第二最优子代子状态和第二次优子代子状态，基于确定的所述第二最优子代子状态和第二次优子代子状态更新所述时间步约束集；
将在第一时间步中确定的所述第三最优父代子状态添加至close表中，在所述第二机器人的第三最优父代子状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第三最优子代子状态和第三次优子代子状态中的其中一个作为所述第二机器人在第二时间步中的第四最优父代子状态，基于更新后的时间步约束集和所述第四最优父代子状态确定第二机器人在第二时间步中可扩展的第四子代子状态，基于评价函数确定第四子代子状态中的第四最优子代子状态和第四次优子代子状态，基于确定的所述第四最优子代子状态和第四次优子代子状态更新所述时间步约束集。
10.在本发明的一些实施例中，在确定高优先级的机器人的可扩展的父代子状态、子代子状态时，忽视所述低优先级的机器人在所述时间步约束集中的约束。
11.在本发明的一些实施例中，所述成本目标函数为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rdi执行其行驶路径的第一行驶成本，表示空料箱搬运机器人rcei执行其行驶路径的第二行驶成本，表示满料箱搬运机器人rcfi执行其行驶路径的第三行驶成本。
12.分拣机器人rdi执行其行驶路径的第一行驶成本为：空料箱搬运机器人rcei执行其行驶路径的第二行驶成本为：满料箱搬运机器人rcfi执行其行驶路径的第三行驶成本为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rdi行驶路径中的第j个位置点，表示分拣机器人rdi行驶路径中的第j+1个位置点，表示空料箱搬运机器人rcei行驶路径中的第j个位置点，表示空料箱搬运机器人rcei行驶路径中的第j+1个位置点，表示满料箱搬运机器人rcfi行驶路径中的第j个位置点，表示满料箱搬运机器人rcfi行驶路径中的第j+1个位置，d表示行驶路径中的位置点总数量。
13.根据本发明的另一方面，还公开了一种高速分拣机器人集中式调度实时路径规划系统，该系统包括处理器和存储器，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该系统实现如上任一实施例所述方法的步骤。
14.根据本发明的再一方面，还公开了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上任一实施例所述方法的步骤。
15.本发明实施例所公开的高速分拣机器人集中式调度实时路径规划方法在为各机
器人规划路径时考虑了各机器人的优先级顺序，即基于外层的遗传算法对机器人的优先级进行排序，进而采用内层的搜索算法基于机器人的优先级完成各机器人的路径规划，该方法在多类型机器人和多类型任务的复杂场景下不仅可为各机器人规划较佳的行驶路径，还进一步的提升了算法的精确性，大大降低了算法执行的时间，从而也可提高系统调度效率以及降低系统作业成本。
16.除上述之外，在基于内层的搜索算法对机器人的行驶路径进行规划时，若机器人之间出现路径冲突的情况时，高优先级的机器人忽视低优先级的机器人的约束，从而使得采用该方法获得的各机器人的行驶路径在避免路径冲突的前提下，还能确保各机器人获得最优行驶路径。
17.本发明的附加优点、目的，以及特征将在下面的描述中将部分地加以阐述，且将对于本领域普通技术人员在研究下文后部分地变得明显，或者可以根据本发明的实践而获知。本发明的目的和其它优点可以通过在书面说明及其权利要求书以及附图中具体指出的结构实现到并获得。
18.本领域技术人员将会理解的是，能够用本发明实现的目的和优点不限于以上具体所述，并且根据以下详细说明将更清楚地理解本发明能够实现的上述和其他目的。
附图说明
19.此处所说明的附图用来提供对本发明的进一步理解，构成本技术的一部分，并不构成对本发明的限定。附图中的部件不是成比例绘制的，而只是为了示出本发明的原理。为了便于示出和描述本发明的一些部分，附图中对应部分可能被放大，即，相对于依据本发明实际制造的示例性装置中的其它部件可能变得更大。在附图中：图1为本发明一实施例的高速分拣机器人集中式调度实时路径规划方法的流程示意图。
20.图2为一实施例的分拣系统的仓库中的栅格化地图模型示意图。
21.图3为本发明另一实施例的高速分拣机器人集中式调度实时路径规划方法的流程示意图。
22.图4为本发明一实施例的搜索算法的流程示意图。
23.图5为本发明一实施例的种群内个体的编码示意图。
24.图6为对个体进行交叉操作的编码示意图。
25.图7为对个体进行变异操作的编码示意图。
26.图8为外层遗传算法和内层搜索算法进行正反馈的流程示意图。
具体实施方式
27.为使本发明实施例的目的、技术方案和优点更加清楚明白，下面结合附图对本发明实施例做进一步详细说明。在此，本发明的示意性实施例及其说明用于解释本发明，但并不作为对本发明的限定。
28.在此，需要说明的是，为了避免因不必要的细节而模糊了本发明，在附图中仅仅示出了与根据本发明的方案密切相关的结构和/或处理步骤，而省略了与本发明关系不大的其他细节。
29.应该强调，术语“包括/包含/具有”在本文使用时指特征、要素、步骤或组件的存在，但并不排除一个或更多个其它特征、要素、步骤或组件的存在或附加。
30.轻小件高速分拣机器人系统集中式调度实时路径规划问题是指为当前时刻有任务的机器人规划出无碰撞的路径集合，各机器人以规划的路径来完成当前时刻的任务。具体来说就是以总行驶成本最低为目标，给出每个分拣机器人和料箱搬运机器人的最优行驶路径。本技术的具有多类型机器人和多类型任务的复杂场景的分拣机器人系统涉及三种类型机器人以及三种类型任务，三种类型机器人分别为分拣机器人、空料箱搬运机器人以及满料箱搬运机器人，而三种类型任务分别为分拣任务、空料箱搬运任务和满料箱搬运任务；即分拣机器人用于完成包裹分拣任务，空料箱搬运机器人用于完成空料箱搬运任务，满料箱搬运机器人用于完成满料箱搬运任务。
31.在下文中，将参考附图描述本发明的实施例。在附图中，相同的附图标记代表相同或类似的部件，或者相同或类似的步骤。
32.图1为本发明一实施例的高速分拣机器人集中式调度实时路径规划方法的流程示意图，参考图1，该方法至少包括步骤s10至s50。
33.步骤s10：获取机器人集合，所述机器人集合包括用于执行分拣任务的分拣机器人集合、用于执行空料箱搬运任务的空料箱搬运机器人集合和用于执行满料箱搬运任务的满料箱搬运机器人集合。
34.在该步骤中，所获取的机器人集合为执行当前波次任务的所有机器人的集合，包括分拣机器人、空料箱搬运机器人和满料箱搬运机器人。而分拣系统中的仓库地图如图2所示，图2所示的栅格化地图模型示意图中的空白方格代表可被机器人在当前波次任务中占用的位置点，即作为机器人行驶路径中的位置点，此时具体的可将分拣机器人系统中的仓库根据实际尺寸按照一定的单元长度进行切分为多个栅格，而栅格化地图模型示意图中的灰色方格代表在某时刻上货台的位置、装箱位置以及周转料箱的位置。可以理解的，随着机器人的行驶运动以及周转料箱的位置的变化，则周转料箱占用的位置点会随之改变。
35.具体的，用于执行分拣任务的分拣机器人从上货台将待分拣包裹搬运且放置在指定分拣料口的周转料箱中，用于执行空料箱搬运任务的空料箱搬运机器人将空的周转料箱搬运至相应的分拣料口，用于执行满料箱搬运任务的满料箱搬运机器人将盛放有包裹的满的周转料箱搬运至装箱位置以进行打包。
36.示例性的，获取到的分拣机器人的数量为n，则分拣机器人集合表示为；获取到的空料箱搬运机器人的数量为m，则空料箱搬运机器人集合表示为；获取到的满料箱搬运机器人的数量为l，则满料箱搬运机器人集合表示为。
37.步骤s20：构建初始种群，所述初始种群内的个体为机器人优先级序列。
38.在该步骤中构建初始种群，以通过遗传算法对各机器人的优先级进行排序。初始种群内的各个体表示机器人的优先级序列，具体的为优先级序列编码，用于表示各机器人的优先级。优先级序列编码如图5所示，三种类型的机器人编码根据优先级从前至后进行排列，该示例编码所表示的各机器人的路径规划的优先级为：编码为1的分拣机器人、编码为1的空料箱搬运机器人、编码为3的满料箱搬运机器人、编码为2的分拣机器人、编码为2的空料箱搬运机器人、编码为1的满料箱搬运机器人、编码为3的分拣机器人、编码为3的空料箱搬运机器人、编码为2的满料箱搬运机器人和编码为4的分拣机器人。可以理解的，在图5中
所示的个体的编码方式仅是一种优选示例，在其他实施例中，还可以通过其他类型的编码表示机器人的优先级序列。另外，在具体编码时，也可通过不同颜色的编码表示不同类型的机器人，如红色编码代表分拣机器人，灰色编码代表空料箱搬运机器人，黄色编码代表满料箱搬运机器人。
39.步骤s30：基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径。
40.在该步骤中，搜索算法作为遗传算法的内层算法，用于规划种群内各个体所对应的各机器人的行驶路径；以使得在后续步骤(s40和s50)中基于搜索算法规划的各个体所对应的各机器人的行驶路径被反馈至外层的遗传算法，进而基于遗传算法确定最优的机器人优先级序列，从而将最优的机器人优先级序列对应的各机器人的行驶路径作为各机器人的最优行驶路径。
41.步骤s40：构建所述分拣机器人执行其行驶路径的第一行驶成本、所述空料箱搬运机器人执行其行驶路径的第二行驶成本以及所述满料箱搬运机器人执行其行驶路径的第三行驶成本，基于所述第一行驶成本、第二行驶成本以及第三行驶成本确定成本目标函数，基于所述成本目标函数计算各个体的适应度值。
42.在该步骤中，规划的最优行驶路径为总行驶成本最低所对应的路径，即以总行驶成本作为成本目标函数。成本目标函数为各机器人的行驶成本之和，即成本目标函数为各第一行驶成本、各第二行驶成本以及各第三行驶成本之和。
43.示例性的，分拣机器人rdi的长度为d的规划路径可表示为，表示机器人rdi的规划路径中的第j个位置点。空料箱搬运机器人rcei的长度为d的规划路径可表示为，类似的，表示机器人rcei的规划路径中的第j个位置点。满料箱搬运机器人rcfi的长度为d的规划路径可表示为，类似的，表示机器人rcfi的规划路径中的第j个位置点。
44.进一步的，第一行驶成本、第二行驶成本以及第三行驶成本分别通过、和表示。则成本目标函数可为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rdi执行其行驶路径的第一行驶成本，表示空料箱搬运机器人rcei执行其行驶路径的第二行驶成本，表示满料箱搬运机器人rcfi执行其行驶路径的第三行驶成本。为了获得最优的行驶路径，则以总成本最小化为目标的模型函数为：。
45.在一实施例中，分拣机器人rdi执行其行驶路径的第一行驶成本为：空料箱搬运机器人rcei执行其行驶路径的第二行驶成本为：
满料箱搬运机器人rcfi执行其行驶路径的第三行驶成本为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rdi行驶路径中的第j个位置点，表示分拣机器人rdi行驶路径中的第j+1个位置点，表示空料箱搬运机器人rcei行驶路径中的第j个位置点，表示空料箱搬运机器人rcei行驶路径中的第j+1个位置点，表示满料箱搬运机器人rcfi行驶路径中的第j个位置点，表示满料箱搬运机器人rcfi行驶路径中的第j+1个位置，d表示行驶路径中的位置点总数量。其中，dis用于计算两个位置点之间的距离，分别为三种类型的机器人的路径行驶成本系数，在一实施例中，设定。
46.另外，上述的成本目标函数还需满足如下条件：（1）；（2）；（3）上述式（1）表示不允许在同一时刻同一位置出现两个机器人，即防止机器人位置冲突；式（2）和式（3）表示不允许两个机器人出现位置交换，即防止位置交换冲突。，可理解为两个机器人在同一时刻的位置点，n、m、l分别表示分拣机器人、空料箱搬运机器人以及满料箱搬运机器人的总数量，d表示各机器人的规划路径中的位置点的长度或数量。
47.步骤s50：基于各个体的适应度值确定各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的最优行驶路径。
48.在该步骤中，总行驶成本越低的个体的适应度值越大，则以总行驶成本为成本目标函数的适应度函数表示为：。为个体o的适应度值，为个体o对应的目标函数值。本技术的实时路径规划方法，遗传算法种群内的个体通过搜索算法搜索之后得到基于各机器人路径规划的可行解，然后再进一步的确定各个体的适应度值，最终基于各个体的适应度值确定最优的个体，从而也相应的得到基于搜索算法规划的最优的各机器人的行驶路径。
49.进一步的，高速分拣机器人集中式调度实时路径规划方法还包括如下步骤：对所述初始种群内的个体进行遗传操作得到新种群。为了基于遗传算法获得较高质量的解，则具体的对所述初始种群内的个体可进行选择操作、交叉操作以及变异操作得到新种群。
50.选择算子被用来从当前的群体中选出一些个体，这些个体作为下一代个体的双亲。一般选择是基于概率的，但是每个个体被选择的概率与其适应度相关联，这样会使得高质量的解能够遗传给下一代。为了避免遗传操作的随机性破坏最优个体，可采用轮盘赌选
择和最优个体保存策略相结合的方法进行个体的选择，即将当前种群中适应度最高的个体直接复制到下一代种群中，而余下的个体采用轮盘赌选择方法进行选择。个体o被选中遗传到下一代的概率可以表示为：；其中表示个体o的适应度，n表示种群大小。
51.交叉算子，也被叫做重组，用于把双亲的遗传信息结合起来，产生后代；需要在保证后代个体质量的同时，保证后代的多样性。在一实施例中，可采用均匀交叉的方式对个体进行交叉操作；在均匀交叉中，每个基因的选择都是通过随机选择双亲之一来确定的。每个父代被选择的概率都是50%，每个父代均有机会影响其后代；这种方法没有交换编码的全部片段，因而在保证后代质量的同时保证了后代的多样性，如图6所示，将两个父代个体中的第三个编码、第六个编码和第七个编码分别进行交叉操作得到两个子代个体，在该图6中，仅例举出机器人的编码对交叉操作进行举例说明，而对于机器人的类型可通过编码颜色或机器人标记进行区分。
52.变异算子，一般应用于选择和交叉操作之后而产生的后代中，变异是低概率事件，因此在遗传算法中通常以较低的概率发生，因为它可能会损害个体的表现值，降低个体的适应度；但是同时变异也会增加种群的多样性，有利于搜索的扩展，但是需要控制变异的概率，否则遗传算法会变得和随机搜索算法等效。在一实施例中，可采用交换变异对个体进行变异操作，即随机选择两个基因值，并且交换他们的值（不需要保证选择的值不同，因为机器人编号相同也会是不同类型的机器人）。如图7所示，将父代个体中的第二个编码第六个编码进行互换得到子代个体；该图7与图6类似的，仅例举出机器人的编码对变异操作进行举例说明，而对于机器人的类型可通过编码颜色或机器人标记进行区分。
53.在上述实施例中，遗传算法作为外层算法，主要负责规划各机器人之间的优先级，优先级顺序将直接影响内层路径规划算法最终搜索出的可行路径的优劣程度。另外该遗传算法可进一步的设定成本目标函数的界限，即当成本目标函数值小于阈值时，搜索结束。
54.在一些实施例中，基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径，包括：在第一时间步中：获取各所述机器人的初始状态，并将各所述初始状态存储至open表中，基于各所述机器人的初始状态构建时间步约束集；其中，所述初始状态包括各机器人在第一时间步的位置信息，所述时间步约束集中的各约束包括时间步信息以及机器人的位置信息；将第一机器人的初始状态添加至close表中，在所述第一机器人的初始状态与所述第一机器人的目标位置不同时，基于所述时间步约束集和所述第一机器人的初始状态确定第一机器人在第一时间步中可扩展的第一父代子状态，基于确定的所述第一父代子状态更新所述open表；基于评价函数确定所述第一父代子状态中的第一最优父代子状态，基于所述时间步约束集和第一最优父代子状态确定第一机器人在第一时间步中可扩展的第一子代子状态，基于评价函数确定所述第一子代子状态中的第一最优子代子状态和第一次优子代子状态，基于确定的所述第一最优子代子状态和第一次优子代子状态更新所述时间步约束集；将第二机器人的初始状态添加至close表中，在所述第二机器人的初始状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集和所述第二机器人的初
始状态确定第二机器人在第一时间步中可扩展的第三父代子状态，基于确定的所述第三父代子状态更新所述open表；基于评价函数确定所述第三父代子状态中的第三最优父代子状态，基于更新后的所述时间步约束集和第三最优父代子状态确定第二机器人在第一时间步中可扩展的第三子代子状态，基于评价函数确定所述第三子代子状态中的第三最优子代子状态和第三次优子代子状态，基于确定的所述第三最优子代子状态和第三次优子代子状态更新所述时间步约束集。
55.进一步的，基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径，还可以包括如下步骤：在第二时间步中：将在第一时间步中确定的所述第一最优父代子状态添加至close表中，在所述第一机器人的第一最优父代子状态与所述第一机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第一最优子代子状态和第一次优子代子状态中的其中一个作为所述第一机器人在第二时间步中的第二最优父代子状态，基于更新后的时间步约束集和所述第二最优父代子状态确定第一机器人在第二时间步可扩展的第二子代子状态，基于评价函数确定第二子代子状态中的第二最优子代子状态和第二次优子代子状态，基于确定的所述第二最优子代子状态和第二次优子代子状态更新所述时间步约束集；将在第一时间步中确定的所述第三最优父代子状态添加至close表中，在所述第二机器人的第三最优父代子状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第三最优子代子状态和第三次优子代子状态中的其中一个作为所述第二机器人在第二时间步中的第四最优父代子状态，基于更新后的时间步约束集和所述第四最优父代子状态确定第二机器人在第二时间步中可扩展的第四子代子状态，基于评价函数确定第四子代子状态中的第四最优子代子状态和第四次优子代子状态，基于确定的所述第四最优子代子状态和第四次优子代子状态更新所述时间步约束集。
56.在上述实施例中，在确保基于搜索算法搜索到的各机器人的行驶路径为最优的前提下，为了确保各机器人的行驶路径避免碰撞，则在确定高优先级的机器人的可扩展的父代子状态、子代子状态时，忽视所述低优先级的机器人在所述时间步约束集中的约束。即优先级较高的机器人会优先扩展最优子状态，并且占用该状态之后的m个时间步的状态。
57.具体的，由于采用集中式调度的方式，所以内层的搜索算法在进行多机器人路径规划时，可以通过事先预知其他机器人未来m个时间步的运动来避免路径的冲突。具体而言，通过外层遗传算法计算后，每个机器人有一个优先级（该优先级用于在搜索过程中决定各机器人扩展子状态的顺序），所以在内层搜索算法进行路径规划时，各机器人扩展最优子状态时会把当前步之后的m步作为约束加入动态的时间步约束集中；则优先级较低的机器人在扩展子状态时需要考虑时间步约束集中的约束，以此使优先级较低的机器人为优先级较高的机器人进行路径让步以避免路径的冲突。在一些具体的实施例中，为了保证高优先级的机器人可以搜索到更优的解，则可设定高优先级的机器人可以无视低优先级的机器人在时间步约束集中添加的约束。
58.可以理解的，在多类型任务和多类型机器人的大规模场景下，机器人之间存在路径冲突是十分常见的，因此采取合适的冲突规避策略是十分重要的，在本技术的搜索算法
中，规定当机器人间发生路径冲突时，可以选择原地停留或者积极规避的方式（即：向左、向右、向前、向后）；由于先规划的机器人约束较少拥有更多的选择权，所以有更多的规避方向（绕路成本增加有限），后规划的机器人约束较多规避方向较少（绕路成本较大）。因此在处理机器人路径冲突问题时，高优先级的机器人尽量积极选择绕路（因为约束少绕路较近），低优先级的机器人尽量选择原地停留（因为约束多绕路更远）。
59.图4为本发明一实施例的搜索算法的流程示意图，参考图4，在进行各机器人的路径搜索时，首先输入外层遗传算法搜索得到的k个机器人的优先级顺序，其中k=n+m+l。然后将各机器人的初始状态s添加至open表中，open表指待扩展的状态集合；进一步的创建时间步约束集（time_bound表），time_bound表表示在三维坐标中的约束集合，表示某个位置在某个时刻已经被占用。首先判断open表是否为空，则当open表为空时，搜索算法结束；当open表不为空时，则基于评价函数计算open表中各状态的f值，并将最小f值对应的状态作为t时间步下机器人p的状态n，并进一步将状态n从open表中移至close表中，close表中存储的为当前已经搜索过的状态集合；该实施例中所采用的评价函数与a*算法的评价函数相同，即f(n)=g(n)+h(n)，其中f(n)为从初始点经由节点n到目标点的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h（n）是从n到目标节点最佳路径的评估代价。在初始状态下，机器人指针p=1，时间步t=1，此时直接将机器人p的初始状态添加至close表中即可，而在时间步t=2中，由于open表中已在t=1时间步中被扩展，则此时需要计算各状态的f值。
60.在将机器人p的状态n添加至close表中后，则进一步的判断机器人p的状态n是否为机器人p的目标位置，若是，则令p=p%k+1，即进一步的循环执行对应步骤以搜索其他机器人的状态n，若当所有机器人的状态n均为目标位置时，则此时搜索算法结束；而若同一时间步中的所有机器人的状态均被搜索完毕，则进一步的令p=1，t=t+1，以进行机器人p的下一时间步的状态搜索。另外；当机器人p的状态n与机器人p的目标位置不同时，则进一步的参考时间步约束集，确定机器人p可扩展的第一父代子状态，并且高优先级的机器人可以忽视低优先级的机器人在时间步约束集中的约束；进一步的将确定的第一父代子状态中的已存在于close表中的状态删除，并将第一父代子状态中的剩余状态添加至open表中，并进一步的基于评价函数计算open表中各状态的f值，以将open表中f值最低的状态作为第一最优父代子状态ms。
61.进一步的，基于时间步约束集确定第一最优父代子状态ms可扩展的第一子代子状态，并通过评价函数确定第一子代子状态中的第一最优子代子状态mms和第一次优子代子状态sms。此时进一步的将机器人p先前添加至time_bound表中的约束删除，并进一步把第一最优子代子状态和第一次优子代子状态更新至时间步约束集，即把机器人p在mms状态和sms状态中的位置、时间t，如p(xmms，ymms，t，p) 、p(xsms，ysms，t，p)存储至time_bound表。进一步的，令 p=p%k+1或当p=1时，令t=t+1循环执行上述步骤直至搜索到各机器人各时刻的状态。
62.在上述实施例中，在进行子状态的扩展时，各循环过程中只扩展其中一个机器人的子状态；同时在扩展完一个机器人的父代子状态后，需要再扩展最优父代子状态的子状态，同时把最优父代子状态的最优子代子状态和次优子代子状态加入time_bound约束表中；该过程即是走一步占m步的思想，每个循环中约束表动态更新，并且在下次循环时删除
之前的约束并且重新添加约束。本技术在搜索算法中设定高优先级的机器人可以无视低优先级的机器人添加的约束，因此可以保证高优先级的机器人可以搜索到更优的解，并且能够更先到达目标位置。在本技术的搜索方法中，当执行完机器人p在时间步t的子状态扩展后，则机器人指针加一，直至执行完所有机器人在时间步t的子状态扩展；然后时间步t+1，并循环执行完所有机器人在t+1时间步的子状态扩展。
63.本技术的高速分拣机器人集中式调度实时路径规划方法，外层采用遗传算法确定机器人路径规划的顺序，然后再结合内层搜索算法得到多机器人的规划路径，并计算所规划的路径对应的适应度值，此后进行迭代，以此来得到更优的路径规划方案。该实时路径规划方法采用外层遗传算法、内层搜索算法正反馈的方式，参考图8，外层的遗传算法基于机器人的优先级序列确定各机器人进行路径规划的顺序，内层的改进的基于时间步的搜索算法依据外层遗传算法反馈的规划顺序，快速的迭代出较佳的规划路径。
64.图3为本发明另一实施例的高速分拣机器人集中式调度实时路径规划方法的流程示意图，参考图3，在该实施例中，首先获取三种类型机器人的任务信息，如波次任务、分拣机器人的数量、空料箱搬运机器人的数量以及满料箱搬运机器人的数量等；然后加载所设定的参数和功能区的信息；初始化种群，种群内的各个体均为机器人优先级序列，代表各机器人被进行路径规划的顺序；遍历种群，对每个个体基于改进的搜索算法进行路径搜索；依据成本目标函数，计算各个体的适应度值；判断遗传算法是否满足终止条件；在满足时，则输出最优的机器人优先级序列以及搜索算法规划的机器人行驶路径；未满足时，进行遗传操作，即对个体进行选择操作、交叉操作和变异操作，产生新种群；直至遗传算法满足终止条件。
65.通过上述实施例可以发现，本技术的多类型机器人和多类型任务的大规模的分拣机器人系统中考虑三种不同的任务组合，同时需要规划的机器人数量较多，相比于传统的多机器人路径规划问题，规划问题的规模和复杂度都呈指数上升；现有技术中普遍采用的搜索算法如a*搜索算法等虽然在小规模场景下表现良好，但是在规模较大的路径规划问题上其求解速度和求解质量都不尽人意；基于此本技术采用改进的搜索算法以在提高了算法的求解速度的前提下还进一步的解决了多个机器人的路径碰撞问题。
66.本技术综合考虑分拣机器人系统中多种任务的组合，以及不同类型机器人的行驶成本，建立以系统总行驶成本最低为目标的模型，设计了一个基于优先级的双层路径规划算法（外层遗传算法和内层的搜索算法），既能满足大规模场景下多任务组合和多机器人路径规划的要求，又能提高算法的搜索速度和求解质量。
67.另外，在本技术的上述实施例中，所建立的路径规划方法对应的模型具体可满足如下条件：分拣系统地图的全局信息已知，不会在地图中随机出现障碍物；所有机器人均为良好状态，不考虑机器人充电过程或随机故障；在各时间步中，所有机器人均统一执行其相应的动作，动作包括向前、向后、向左、向右和暂停等；各机器人保持匀速v行驶；各机器人执行完其任务停留在原地不动。可以理解的，上述的条件仅是一种示例，在其他实施例中，可根据实际应用场景设定具体的应用条件。
68.相应的，本发明还提供了一种高速分拣机器人集中式调度实时路径规划系统，该系统包括处理器和存储器，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该系统实现如上任一实施例
所述方法的步骤。
69.本技术所公开的高速分拣机器人集中式调度实时路径规划方法及装置，针对多数量机器人和多类型任务的分拣系统进行路径规划时，建立了以总行驶成本最低为目标的模型函数；并且采用外层遗传算法和内层搜索算法相结合的方法对路径进行规划，即基于外层遗传算法首先对机器人优先级进行排序，进而内层的搜索算法根据机器人的优先级完成各机器人的路径规划，且在路径规划过程中，高优先级的机器人可无视低优先级的机器人预先在时间步约束集中的约束，从而基于执行一步且动态规划多步的方式减小算法的运算复杂度和提高了算法的精确度；因而本技术的高速分拣机器人集中式调度实时路径规划方法及装置在多类型机器人和多类型任务的复杂场景下不仅可为各机器人规划较佳的行驶路径，还提高了算法的求解质量和求解速度。
70.另外，该发明还公开了一种计算机可读存储介质，其上存储有计算机程序，该程序被处理器执行时实现如上任一实施例所述方法的步骤。
71.本领域普通技术人员应该可以明白，结合本文中所公开的实施方式描述的各示例性的组成部分、系统和方法，能够以硬件、软件或者二者的结合来实现。具体究竟以硬件还是软件方式来执行，取决于技术方案的特定应用和设计约束条件。专业技术人员可以对每个特定的应用来使用不同方法来实现所描述的功能，但是这种实现不应认为超出本发明的范围。当以硬件方式实现时，其可以例如是电子电路、专用集成电路（asic）、适当的固件、插件、功能卡等等。当以软件方式实现时，本发明的元素是被用于执行所需任务的程序或者代码段。程序或者代码段可以存储在机器可读介质中，或者通过载波中携带的数据信号在传输介质或者通信链路上传送。“机器可读介质”可以包括能够存储或传输信息的任何介质。机器可读介质的例子包括电子电路、半导体存储器设备、rom、闪存、可擦除rom（erom）、软盘、cd-rom、光盘、硬盘、光纤介质、射频（rf）链路，等等。代码段可以经由诸如因特网、内联网等的计算机网络被下载。
72.还需要说明的是，本发明中提及的示例性实施例，基于一系列的步骤或者装置描述一些方法或系统。但是，本发明不局限于上述步骤的顺序，也就是说，可以按照实施例中提及的顺序执行步骤，也可以不同于实施例中的顺序，或者若干步骤同时执行。
73.本发明中，针对一个实施方式描述和/或例示的特征，可以在一个或更多个其它实施方式中以相同方式或以类似方式使用，和/或与其他实施方式的特征相结合或代替其他实施方式的特征。
74.以上所述仅为本发明的优选实施例而已，并不用于限制本发明，对于本领域的技术人员来说，本发明实施例可以有各种更改和变化。凡在本发明的精神和原则之内，所作的任何修改、等同替换、改进等，均应包含在本发明的保护范围之内。

技术特征：
1.一种高速分拣机器人集中式调度实时路径规划方法，其特征在于，所述方法包括：获取机器人集合，所述机器人集合包括用于执行分拣任务的分拣机器人集合、用于执行空料箱搬运任务的空料箱搬运机器人集合和用于执行满料箱搬运任务的满料箱搬运机器人集合；构建初始种群，所述初始种群内的个体为机器人优先级序列；基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径；构建所述分拣机器人执行其行驶路径的第一行驶成本、所述空料箱搬运机器人执行其行驶路径的第二行驶成本以及所述满料箱搬运机器人执行其行驶路径的第三行驶成本，基于所述第一行驶成本、第二行驶成本以及第三行驶成本确定成本目标函数，基于所述成本目标函数计算各个体的适应度值；基于各个体的适应度值确定各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的最优行驶路径。2.根据权利要求1所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，所述方法还包括：对所述初始种群内的个体进行遗传操作得到新种群。3.根据权利要求2所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，对所述初始种群内的个体进行遗传操作得到新种群，包括：对所述初始种群内的个体进行选择操作、交叉操作以及变异操作得到新种群。4.根据权利要求1所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，基于搜索算法确定各个体对应的各所述分拣机器人、各所述空料箱搬运机器人和各所述满料箱搬运机器人的行驶路径，包括：在第一时间步中：获取各所述机器人的初始状态，并将各所述初始状态存储至open表中，基于各所述机器人的初始状态构建时间步约束集；其中，所述初始状态包括各机器人在第一时间步的位置信息，所述时间步约束集中的各约束包括时间步信息以及机器人的位置信息；将第一机器人的初始状态添加至close表中，在所述第一机器人的初始状态与所述第一机器人的目标位置不同时，基于所述时间步约束集和所述第一机器人的初始状态确定第一机器人在第一时间步中可扩展的第一父代子状态，基于确定的所述第一父代子状态更新所述open表；基于评价函数确定所述第一父代子状态中的第一最优父代子状态，基于所述时间步约束集和第一最优父代子状态确定第一机器人在第一时间步中可扩展的第一子代子状态，基于评价函数确定所述第一子代子状态中的第一最优子代子状态和第一次优子代子状态，基于确定的所述第一最优子代子状态和第一次优子代子状态更新所述时间步约束集；将第二机器人的初始状态添加至close表中，在所述第二机器人的初始状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集和所述第二机器人的初始状态确定第二机器人在第一时间步中可扩展的第三父代子状态，基于确定的所述第三父代子状态更新所述open表；基于评价函数确定所述第三父代子状态中的第三最优父代子状态，基于更新后的所述
时间步约束集和第三最优父代子状态确定第二机器人在第一时间步中可扩展的第三子代子状态，基于评价函数确定所述第三子代子状态中的第三最优子代子状态和第三次优子代子状态，基于确定的所述第三最优子代子状态和第三次优子代子状态更新所述时间步约束集。5.根据权利要求4所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，所述方法还包括：在第二时间步中：将在第一时间步中确定的所述第一最优父代子状态添加至close表中，在所述第一机器人的第一最优父代子状态与所述第一机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第一最优子代子状态和第一次优子代子状态中的其中一个作为所述第一机器人在第二时间步中的第二最优父代子状态，基于更新后的时间步约束集和所述第二最优父代子状态确定第一机器人在第二时间步可扩展的第二子代子状态，基于评价函数确定第二子代子状态中的第二最优子代子状态和第二次优子代子状态，基于确定的所述第二最优子代子状态和第二次优子代子状态更新所述时间步约束集；将在第一时间步中确定的所述第三最优父代子状态添加至close表中，在所述第二机器人的第三最优父代子状态与所述第二机器人的目标位置不同时，基于更新后的所述时间步约束集选取所述第三最优子代子状态和第三次优子代子状态中的其中一个作为所述第二机器人在第二时间步中的第四最优父代子状态，基于更新后的时间步约束集和所述第四最优父代子状态确定第二机器人在第二时间步中可扩展的第四子代子状态，基于评价函数确定第四子代子状态中的第四最优子代子状态和第四次优子代子状态，基于确定的所述第四最优子代子状态和第四次优子代子状态更新所述时间步约束集。6.根据权利要求5所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，在确定高优先级的机器人的可扩展的父代子状态、子代子状态时，忽视所述低优先级的机器人在所述时间步约束集中的约束。7.根据权利要求1所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，所述成本目标函数为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rd
i
执行其行驶路径的第一行驶成本， 表示空料箱搬运机器人rce
i
执行其行驶路径的第二行驶成本，表示满料箱搬运机器人rcf
i
执行其行驶路径的第三行驶成本。8.根据权利要求7所述的高速分拣机器人集中式调度实时路径规划方法，其特征在于，分拣机器人rd
i
执行其行驶路径的第一行驶成本为：空料箱搬运机器人rce
i
执行其行驶路径的第二行驶成本为：
满料箱搬运机器人rcf
i
执行其行驶路径的第三行驶成本为：其中，n为分拣机器人集合中的分拣机器人的总数量，m为空料箱搬运机器人集合中的空料箱搬运机器人的总数量，l为满料箱搬运机器人集合中的满料箱搬运机器人的总数量，表示分拣机器人rd
i
行驶路径中的第j个位置点， 表示分拣机器人rd
i
行驶路径中的第j+1个位置点，表示空料箱搬运机器人rce
i
行驶路径中的第j个位置点，表示空料箱搬运机器人rce
i
行驶路径中的第j+1个位置点，表示满料箱搬运机器人rcf
i
行驶路径中的第j个位置点，表示满料箱搬运机器人rcf
i
行驶路径中的第j+1个位置，d表示行驶路径中的位置点总数量。9.一种高速分拣机器人集中式调度实时路径规划系统，该系统包括处理器和存储器，其特征在于，所述存储器中存储有计算机指令，所述处理器用于执行所述存储器中存储的计算机指令，当所述计算机指令被处理器执行时该系统实现如权利要求1至8中任意一项所述方法的步骤。10.一种计算机可读存储介质，其上存储有计算机程序，其特征在于，该程序被处理器执行时实现如权利要求1至8中任意一项所述方法的步骤。

技术总结
本发明提供一种高速分拣机器人集中式调度实时路径规划方法及装置，包括：获取机器人集合；构建初始种群；基于搜索算法确定各个体对应的各机器人的行驶路径；构建分拣机器人执行其行驶路径的第一行驶成本、空料箱搬运机器人执行其行驶路径的第二行驶成本以及满料箱搬运机器人执行其行驶路径的第三行驶成本，基于第一行驶成本、第二行驶成本以及第三行驶成本确定成本目标函数，基于成本目标函数计算各个体的适应度值；基于各个体的适应度值确定各分拣机器人、各空料箱搬运机器人和各满料箱搬运机器人的最优行驶路径。该方法及装置在多类型机器人和多类型任务的复杂场景下可为各机器人规划较佳的行驶路径。器人规划较佳的行驶路径。器人规划较佳的行驶路径。


技术研发人员：苏志远 谭树勇 李金澎 汪朝林
受保护的技术使用者：宝开（上海）智能物流科技有限公司
技术研发日：2023.07.04
技术公布日：2023/8/6