一种物流搬运机器人任务调度系统及方法

1.本发明涉及物流管理技术领域，更具体的是涉及一种物流搬运机器人任务调度系统及方法。


背景技术：

2.在物流搬运机器人领域，任务调度问题占据着重要地位。任务调度问题是指为多个机器人安排其需要执行的任务。在一个多机器人系统中，机器人位于不同的位置，有多项任务，每项任务需要一台机器人去完成，如何将任务分配给特定的机器人，使得总体任务完成时间最短（或距离最短、成本最小等其它目标）。目前，现有的物流搬运机器人调度系统，其任务调度通常有两种方法：第一种方法是为单个机器人指派单个任务。任务是惯续到达的，有先后顺序。通常采用逐个安排的方法，一次只处理一个任务，为其选择一台合适的机器人来执行。此时，通常采用启发式规则来确定，例如：距离最近的机器人，空闲时间最长的机器人。但上述规则存在明显的短视缺点，特别是在比较小的地图场景下，因为距离近的机器人虽然可以较快到达，但是也许在下一秒在该机器人出发地就有一个新的任务更适合其执行，但是因为任务已指派，所以已无法去执行。另有一种情况是虽然某个机器人目前是工作状态，但是其马上可以到当前任务点附近并完成任务，此时方法一也无法使用该机器人。
3.第二种方法是为多个机器人指派单个任务，这种方法多将问题建模为指派模型，采用任务指派算法，如匈牙利算法。通过设计一定的规则，综合考虑多个任务、更广泛机器人（含工作中但即将完成任务的机器人）的信息，从而为当前任务指派机器人。主要规则与方法一类似，即可以考虑以下指标：距离最近，达到时间最短。第二种方法相较于第一种方法，考虑了更多的机器人，任务分配的结果也更优。但由于只能为每个机器人指派单一任务，对全局信息利用较少，因此也存在短视缺点。


技术实现要素：

4.本发明的目的在于：为了解决上述技术问题，本发明提供一种物流搬运机器人任务调度系统及方法。
5.本发明为了实现上述目的具体采用以下技术方案：一种物流搬运机器人任务调度的方法，包括以下步骤：步骤s1：获取机器人数据和机器人工作的环境地图数据；步骤s2：根据步骤s1获取的数据，对机器人的工作环境进行建模；步骤s3：根据步骤s1获取的数据，生成当前机器人集合k；步骤s4：根据步骤s1获取的数据，生成当前搬运任务集合r；步骤s5：构建数学模型：基于步骤s2、s3、s4，将多机器人任务调度问题建模为车辆路径规划问题模型，将所有机器人看作是车辆，记为，将任务看作顾客点，并记为：
；引入一个虚拟的节点0，所有机器人都从节点0出发，依次访问各个顾客点，并最终返回这个节点，每个任务都只被一个机器人服务；步骤s6：将步骤s5得到的数学模型通过软件进行编程求解；步骤s7：根据步骤s6得到的模型求解结果，获得每个机器人需要执行的任务集合以及任务执行顺序，并将任务序列发送给每个机器人。
6.进一步地，步骤s1中的机器人数据包括机器人当前所在的位置数据和搬运任务数据。
7.进一步地，搬运任务数据包括取货点位置数据和送货点位置数据。
8.进一步地，步骤s2具体为：使用栅格网络对机器人的工作环境进行建模，用有向图来描述多机器人系统的工作环境，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合，所有路径长度为1离散时间单位长度。
9.进一步地，步骤s2具体为：使用点线结构对机器人的工作环境进行建模，用权重图来描述多机器人系统的工作环境，每条路径有对应的权重，可表示为点i与点j的距离，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合。
10.进一步地，步骤s4中的搬运任务包括简单任务和复杂任务；若搬运任务为简单任务，则每个任务用二元组表示；若搬运任务为复杂任务，则每个任务用多元组表示。
11.进一步地，所述步骤s5具体包括以下子步骤：步骤s5.1：构建决策变量：决策变量包括z和，其中z表示最大完工时间，为0-1变量，若机器人k完成任务i后马上执行任务j，则=1，否则为0；为辅助变量，用于消除子回路；步骤s5.2：构建目标函数：最小化任务最大完工时间；步骤s5.2：构建目标函数：最小化任务最大完工时间；；步骤s5.2.1：计算成本矩阵：表示在vrp模型中，从顾客点i到顾客点j的行驶成本，的计算方法由下面公式得出：；其中，表示在地图中从顾客点i到顾客点j的最短行驶成本，p表示搬运任务取
货点，d表示搬运任务送货点，p，；步骤s5.3：构建初始化条件约束：机器人必须从虚拟点出发并最终返回虚拟点；；步骤s5.4：构建节点访问约束：保证每个顾客点只能被机器人访问一次，即每个任务只能由一个机器人执行；；步骤s5.5：构建流平衡约束：机器人若访问了顾客点i，则接下来只能从顾客点i出发，访问下一个顾客点；；步骤s5.6：构建子回路约束：避免最优解中包含子回路；；步骤s5.7：构建决策变量范围约束；。
12.进一步地，步骤s5.2具体为：根据总路径成本最小化的决策目标，来构建目标函数；。
13.进一步地，步骤s5.2.1中计算任务完成成本矩阵时，对完成任务r进行成本估算。
14.一种物流搬运机器人任务调度系统，使用了上述的物流搬运机器人任务调度的方法。
15.本发明的有益效果如下：本发明通过将任务调度问题建模为车辆路径规划问题并进行求解的方法，实现为多个搬运机器人同时分配多个任务，并对每个机器人执行的任务进行最优排序，与现有技术相比，极大程度提高了物流机器人搬运作业的效率。
附图说明
16.图1是本发明的系统框架图；图2是本发明中使用点线结构时的建模环境地图;图3是本发明中多机器人调度问题转化为vrp模型的解释图；图4是本发明中vrp模型各参数及变量示意图；图5是本发明中vrp模型各参数及变量示意图；图6是本发明中成本矩阵的示意图。
具体实施方式
17.为使本发明实施例的目的、技术方案和优点更加清楚，下面将结合本发明实施例中的附图，对本发明实施例中的技术方案进行清楚、完整地描述，显然，所描述的实施例是本发明一部分实施例，而不是全部的实施例。通常在此处附图中描述和示出的本发明实施例的组件可以以各种不同的配置来布置和设计。
18.因此，以下对在附图中提供的本发明的实施例的详细描述并非旨在限制要求保护的本发明的范围，而是仅仅表示本发明的选定实施例。基于本发明中的实施例，本领域普通技术人员在没有作出创造性劳动前提下所获得的所有其他实施例，都属于本发明保护的范围。
19.实施例1本实施例提供一种物流搬运机器人任务调度的方法，包括以下步骤：步骤s1：获取机器人数据和机器人工作的环境地图数据；步骤s2：根据步骤s1获取的数据，对机器人的工作环境进行建模；步骤s3：根据步骤s1获取的数据，生成当前机器人集合k；步骤s4：根据步骤s1获取的数据，生成当前搬运任务集合r；步骤s5：构建数学模型：基于步骤s2、s3、s4，将多机器人任务调度问题建模为车辆路径规划问题模型，将所有机器人看作是车辆，记为，将任务看作顾客点，并记为：；引入一个虚拟的节点0，所有机器人都从节点0出发，依次访问各个顾客点，并最终返回这个节点，每个任务都只被一个机器人服务；步骤s6：将步骤s5得到的数学模型通过软件进行编程求解；步骤s7：根据步骤s6得到的模型求解结果，获得每个机器人需要执行的任务集合以及任务执行顺序，并将任务序列发送给每个机器人。
20.一种物流搬运机器人任务调度系统，使用了上述的物流搬运机器人任务调度的方法。
21.如图1所示，物流搬运机器人任务调度系统将从任务管理系统和机器人端收集到的信息数据加以处理，下发到机器人任务调度算法中，机器人任务调度算法通过计算得到每个机器人需要执行的任务序列后，将信息返回至物流搬运机器人任务调度系统中，物流搬运机器人任务调度系统根据返回的信息，对机器人下发指令完成搬运任务，同时对任务管理系统中的任务池进行更新。
22.本发明通过将任务调度问题建模为车辆路径规划问题并进行求解的方法，实现为多个搬运机器人同时分配多个任务，并对每个机器人执行的任务进行最优排序，与现有技术相比，极大程度提高了物流机器人搬运作业的效率。
23.实施例2本实施例是在实施例1的基础上，对本发明步骤s1中的机器人数据做出具体说明。
24.步骤s1中的机器人数据包括机器人当前所在的位置数据和搬运任务数据。
25.进一步地，搬运任务数据包括取货点位置数据和送货点位置数据。
26.实施例3本实施例是在上述实施例基础上，关于步骤s2做出具体说明。
27.步骤s2：根据步骤s1获取的数据，对机器人的工作环境进行建模。
28.作为一种可实施地方式，步骤s2具体为：使用栅格网络对机器人的工作环境进行建模，用有向图来描述多机器人系统的工作环境，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合，所有路径长度为1离散时间单位长度，其中1离散时间单位长度表示机器人在1时间单位行驶的距离。
29.地图中结点表示机器人可以在该位置停留路径表示机器人可以通过这条路径从点
푖
行驶到点
푗
，同理路径则表示机器人从点
푗
行驶到点
푖
。
30.在某些情景下，作为另一种可实施地方式，步骤s2具体为：使用点线结构对机器人的工作环境进行建模，用权重图来描述多机器人系统的工作环境，每条路径有对应的权重，可表示为点i与点j的距离，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合。
31.需要说明的是，栅格网络建模多用于电商仓储场景，因为电商仓储环境较为规则，且对机器人效率要求较高，无人化程度高，因此多使用二维码导航的机器人，而每一个二维码就相当于栅格网络中的一个格子。但对于民航而言，大多使用的是slam导航的机器人，无需铺设二维码，机器人工作环境相较于电商仓库而言，比较复杂，难以对其进行标准化的栅格网络划分，因此使用点线结构较好。
32.栅格网络与点线结构最大的区别就是，点线结构用来描述，多了一个每条边的权重w。而栅格网络每个网络的距离是相等的，即为1单位距离，可以理解为栅格网络是点线结构的特殊表现。
33.实施例4本实施例是在上述实施例基础上，关于步骤s3做出具体说明。
34.步骤s3：根据步骤s1获取的数据，生成当前机器人集合k；步骤s3具体为：每个机器人在初始时刻都有一个唯一的位置并用表示，，其中
퐿
表示机器人在地图中的初始位置集合。
35.当使用点线结构进行地图建模，在步骤3生成机器人集合时，机器人当前位置有可能位于路径上，此时，。
36.实施例5本实施例是在上述实施例基础上，关于步骤s4做出具体说明。
37.步骤s4：根据步骤s1获取的数据，生成当前搬运任务集合r。
38.搬运任务集合r中的搬运任务包括简单任务和复杂任务；若搬运任务为简单任务，则每个任务用二元组表示；若搬运任务为复杂任务，则每个任务用多元组表示。
39.当搬运任务为简单任务时，如取送货任务，则每个任务可用一个二元组
表示，其中，表示取货位置，表示送货位置。机器人工作地图环境建模图如图2所示。
40.当搬运任务为复杂任务时，需要往返于更多的节点，如搬运货架任务，表示系统中所有货架位置的结点集合，表示任务货架位置的结点集合，表示拣选站台位置的结点集合。给定一批搬运货架任务，每个任务用一个三元组表示，其中，表示任务货架的位置，表示任务对应的拣选台的位置，表示拣选操作完成后货架将要返回的位置。同理，对于需要服务多个结点的任务可用对应的多元组表示。
41.实施例6本实施例是在上述实施例基础上，关于步骤s5做出具体说明。
42.步骤s5：构建数学模型：基于步骤s2、s3、s4，将多机器人任务调度问题建模为车辆路径规划问题模型即vrp模型，将所有机器人看作是车辆，记为，将任务看作顾客点，并记为：；引入一个虚拟的节点0，所有机器人都从节点0出发，依次访问各个顾客点，并最终返回这个节点，每个任务都只被一个机器人服务。
43.构建的vrp模型如图3所示，各参数及变量如图4和图5所示。
44.所述步骤s5具体包括以下子步骤：步骤s5.1：构建决策变量：决策变量包括z和，其中z表示最大完工时间，为0-1变量，若机器人k完成任务i后马上执行任务j，则=1，否则为0；为辅助变量，用于消除子回路；步骤s5.2：构建目标函数：最小化任务最大完工时间；步骤s5.2：构建目标函数：最小化任务最大完工时间；；步骤s5.2.1：计算成本矩阵：表示在vrp模型中，从顾客点i到顾客点j的行驶成本，的计算方法由下面公式得出：；其中，表示在地图中从顾客点i到顾客点j的最短行驶成本，p表示搬运任务取货点，d表示搬运任务送货点，p，；成本矩阵如图6所示。
45.步骤s5.3：构建初始化条件约束：机器人必须从虚拟点出发并最终返回虚拟点；
；步骤s5.4：构建节点访问约束：保证每个顾客点只能被机器人访问一次，即每个任务只能由一个机器人执行；；步骤s5.5：构建流平衡约束：机器人若访问了顾客点i，则接下来只能从顾客点i出发，访问下一个顾客点；；步骤s5.6：构建子回路约束：避免最优解中包含子回路；；步骤s5.7：构建决策变量范围约束；。
46.进一步地，步骤s5.2中构建目标函数时，需要考虑总路径成本最小化的决策目标；。
47.进一步地，步骤s5.2.1中计算任务完成成本矩阵时，对完成任务r进行成本估算；成本估算的方法包括曼哈顿距离估算、最短距离估算。
48.实施例7本实施例是在上述实施例基础上，关于步骤s6做出具体说明。
49.步骤s6：将步骤s5得到的数学模型通过软件进行编程求解；通过调用gurobi、cplex、杉树等求解器求得最优解。
50.步骤s6具体为：通过启发式算法或元启发式算法求解数学模型。
51.实施例8本实施例是在上述实施例基础上，关于步骤s7做出具体说明。
52.步骤s7：根据步骤s6得到的模型求解结果，获得每个机器人需要执行的任务集合以及任务执行顺序，并将任务序列发送给每个机器人。
53.最终得到每个机器人的任务集合及任务顺序为：机器人1：任务6、任务7；机器人2：任务4、任务5；机器人3：任务8、任务9、任务10。

技术特征：
1.一种物流搬运机器人任务调度的方法，其特征在于，包括以下步骤：步骤s1：获取机器人数据和所述机器人工作的环境地图数据；步骤s2：根据步骤s1获取的数据，对机器人的工作环境进行建模；步骤s3：根据步骤s1获取的数据，生成当前机器人集合k；步骤s4：根据步骤s1获取的数据，生成当前搬运任务集合r；步骤s5：构建数学模型：基于步骤s2、s3、s4，将多机器人任务调度问题建模为车辆路径规划问题模型，将所有机器人看作是车辆，记为，将任务看作顾客点，并记为：；引入一个虚拟的节点0，所有机器人都从节点0出发，依次访问各个顾客点，并最终返回这个节点，每个任务都只被一个机器人服务；步骤s6：将步骤s5得到的数学模型通过软件进行编程求解；步骤s7：根据步骤s6得到的模型求解结果，获得每个机器人需要执行的任务集合以及任务执行顺序，并将任务序列发送给每个机器人。2.根据权利要求1所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s1中的机器人数据包括机器人当前所在的位置数据和搬运任务数据。3.根据权利要求2所述的一种物流搬运机器人任务调度的方法，其特征在于，所述搬运任务数据包括取货点位置数据和送货点位置数据。4.根据权利要求1所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s2具体为：使用栅格网络对机器人的工作环境进行建模，用有向图来描述多机器人系统的工作环境，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合，所有路径长度为1离散时间单位长度。5.根据权利要求1所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s2具体为：使用点线结构对机器人的工作环境进行建模，用权重图来描述多机器人系统的工作环境，每条路径有对应的权重，可表示为点i与点j的距离，其中表示地图中所有结点的集合，表示地图中所有可行驶路径的集合。6.根据权利要求1所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s4中的搬运任务包括简单任务和复杂任务；若所述搬运任务为简单任务，则每个任务用二元组表示；若所述搬运任务为复杂任务，则每个任务用多元组表示。7.根据权利要求1所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s5具体包括以下子步骤：步骤s5.1：构建决策变量：决策变量包括z和，其中z表示最大完工时间，为0-1变量，若机器人k完成任务i后马上执行任务j，则=1，否则为0；为辅助变量，用于消除子回路；
步骤s5.2：构建目标函数：最小化任务最大完工时间；步骤s5.2：构建目标函数：最小化任务最大完工时间；；步骤s5.2.1：计算成本矩阵：表示在vrp模型中，从顾客点i到顾客点j的行驶成本，的计算方法由下面公式得出：；其中，表示在地图中从顾客点i到顾客点j的最短行驶成本，p表示搬运任务取货点，d表示搬运任务送货点，p，；步骤s5.3：构建初始化条件约束：机器人必须从虚拟点出发并最终返回虚拟点；；步骤s5.4：构建节点访问约束：保证每个顾客点只能被机器人访问一次，即每个任务只能由一个机器人执行；；步骤s5.5：构建流平衡约束：机器人若访问了顾客点i，则接下来只能从顾客点i出发，访问下一个顾客点；；步骤s5.6：构建子回路约束：避免最优解中包含子回路；；步骤s5.7：构建决策变量范围约束；。8.根据权利要求7所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s5.2具体为：根据总路径成本最小化的决策目标，来构建目标函数；。9.根据权利要求7所述的一种物流搬运机器人任务调度的方法，其特征在于，所述步骤s5.2.1中计算任务完成成本矩阵时，对完成任务r进行成本估算。10.一种物流搬运机器人任务调度系统，其特征在于，使用了如权利要求1-9中任一项所述的一种物流搬运机器人任务调度的方法。

技术总结
本发明公开了一种物流搬运机器人任务调度的方法，涉及物流管理技术领域，解决现有技术中存在的短视缺点，包括以下步骤：获取机器人数据和机器人工作的环境地图数据；对机器人的工作环境进行建模；生成当前机器人集合K；生成当前搬运任务集合R；基于上述步骤将多机器人任务调度问题建模为车辆路径规划问题模型，将所有机器人看作是车辆，将得到的数学模型通过软件进行编程求解；根据得到的模型求解结果，获得每个机器人需要执行的任务集合以及任务执行顺序，并将任务序列发送给每个机器人；本发明能够实现为多个搬运机器人同时分配多个任务，并对执行的任务进行最优排序，极大程度提高了物流机器人搬运作业的效率。度提高了物流机器人搬运作业的效率。度提高了物流机器人搬运作业的效率。


技术研发人员：陈翼 杨秀清 向勇 马俊勇 张耀 王小锐 廖诗来 戚铭尧 余涛 张建权 赵东飞 刘膑丹
受保护的技术使用者：清华大学深圳国际研究生院
技术研发日：2023.05.23
技术公布日：2023/9/5