1.本发明涉及一种具有运动学约束的多任务分配与多机器人路径规划的协同调度方法，属于多机器人路径规划领域。
背景技术：
2.多机器人任务分配及路径规划问题是为多个机器人分配指定数量的任务，并对于给定起点和分配的任务目标点规划无冲突路径。
3.多机器人任务分配及路径规划的研究成果可以在许多领域中，例如仓储物流，机场运输等等领域，解决了的实际工程中的问题。但是对于具有运动学约束的运输场景，普通栅格地图下的多机器人系统无法满足场景要求，因此有必要研究考虑具有运动学约束的多机器人任务分配及路径规划方法。
技术实现要素：
4.本发明提供了一种具有运动学约束的多任务分配与多机器人路径规划的协同调度方法，以用于对任务分配的同时获取多机器人的路径。
5.本发明的技术方案是：
6.根据本发明的一方面，提供了一种具有运动学约束的多任务分配与多机器人路径规划的协同调度方法，包括：对连续地图中多机器人输入起点；将连续地图中加入多个任务点；对多机器人依据优化算法进行多任务分配；多机器人依据分配的任务规划符合运动学约束的路径。
7.所述对多机器人依据优化算法进行多任务分配，包括：对连续地图中的多机器人起点以及任务点，依据整体适应度函数进行迭代进化，获得各个机器人分配的任务点；其中，整体适应度函数为路径适应度函数与冲突适应度函数之和。
8.所述路径适应度函数为从机器人起点到各个任务点使用标准a*算法求得的路径长度总和。
9.所述冲突适应度函数为机器人之间符合交点判断条件所产生的惩罚值总和。
10.所述对连续地图中的多机器人起点以及任务点，依据整体适应度函数进行迭代进化，获得各个机器人分配的任务点，包括：
11.依据随机的方式，将连续地图中n个任务点分配给m个机器人，每个机器人及该机器人分配到的任务点构成一个基因，m个机器人基因作为一个种群个体，依据上述方式，进行p次随机分配产生p个个体；
12.对p个个体依次进行变异交叉操作，操作结束后，根据单个个体整体适应度值进行个体排序，选择整体适应度值靠前的q个个体保留，依据保留的q个个体将种群规模扩充为p个个体；依据上述变异交叉操作过程进行迭代，直至达至终止条件，将整体适应度值最小的个体保留输出，获得各个机器人分配的任务点。
13.每次迭代过程中的变异交叉操作具体为：
14.变异操作：对个体中每个基因进行判断，若随机生成的概率大于第一预设概率，则在任务集合范围内随机选择一个任务点序号a，将随机选择的当前基因所对应的机器人的任务点序号b变异为任务点序号a，将具有任务点序号a的基因所对应的机器人的任务点序号a替换为任务点序号b；
15.交叉操作：对个体中每个基因进行判断，若随机生成的概率大于第二预设概率，则将当前基因所对应的机器人分配的全部任务点序号与同一个体中随机选择的一个基因所对应机器人分配的全部任务点序号进行替换；其中，参与替换操作的两个基因为不同的基因。
16.所述单个个体整体适应度值获取过程包括：
17.根据每个个体中机器人分配的任务点通过标准a*算法求解机器人起点依次到达各个分配的任务点的路径长度，获得单个个体的路径适应度值；
18.依据交点判断条件，确定每个个体中机器人路径的交点个数；依据交点个数，获得每个个体中机器人的冲突适应度值；依次每个个体中机器人的冲突适应度值，获得单个个体的冲突适应度；
19.依据单个个体的路径适应度值、单个个体的冲突适应度，获得单个个体的整体适应度值。
20.所述交点判断条件，具体为：任意两个机器人路径之间出现交点，且交点与两个机器人路径位于交点的前一个位置点之间的距离处于预设范围内，则交点计数加1。
21.所述多机器人依据分配的任务规划符合运动学约束的路径，具体为：多机器人依据分配的任务使用改进类车冲突搜索算法规划符合运动学约束的路径。
22.所述多机器人依据分配的任务使用改进类车冲突搜索算法规划符合运动学约束的路径，包括：利用混合a*算法将所有机器人从自身起点依据任务点顺序规划获得路径，判断路径上是否出现冲突，将没有冲突的机器人路径保存，对于存在冲突的路径，搜索各个路径之间的第一个冲突，判断第一个冲突的机器人优先级条件，将优先级最高的机器人路径保存，对除优先级最高的机器人添加路径约束重新规划路径，继续搜索路径之间的下一个冲突直至所有机器人路径之间没有冲突，整合获得所有机器人符合运动学约束的路径。
23.根据本发明的另一方面，提供了一种具有运动学约束的多任务分配与多机器人路径规划的协同调度系统，包括上述中任意一项所述方法的模块。
24.根据本发明的另一方面，提供了一种处理器，所述处理器用于运行程序，其中，所述程序运行时执行上述中任意一项所述的具有运动学约束的多任务分配与多机器人路径规划的协同调度方法。
25.根据本发明的另一方面，提供了一种计算机可读存储介质，所述计算机可读存储介质包括存储的程序，其中，在所述程序运行时控制所述计算机可读存储介质所在设备执行上述中任意一项所述的具有运动学约束的多任务分配与多机器人路径规划的协同调度方法。
26.本发明的有益效果是：本发明将优化算法和具有运动学约束的多机器人路径规划相结合，使得多机器人系统能够完成多个任务的同时，减少了冲突的次数以及路径搜索的时间，与实际相结合，提高了系统的安全性；有效地减少了机器人之间的冲突，减少了多机
器人系统路径代价；进一步通过实验表明，本发明在存在多个任务的情况下，保证了多机器人的路径规划的执行，并且在正常求解的前提下大大缩短了系统求解路径的时间，提高了系统的求解速度。
附图说明
27.图1是本发明的流程图；
28.图2是路径适应度函数解释示意图；
29.图3冲突适应度函数解释示意图；
30.图4是pcl-cbs剪枝示意图；
31.图5为展示的可选实例图；
32.图6为本发明与其它算法对比实验结果展示图。
具体实施方式
33.下面结合附图和实施例，对发明作进一步的说明，但本发明的内容并不限于所述范围。
34.实施例1：如图1-6所示，根据本发明实施例的一方面，提供了一种具有运动学约束的多任务分配与多机器人路径规划的协同调度方法，包括：对连续地图中多机器人输入起点；将连续地图中加入多个任务点；对多机器人依据优化算法进行多任务分配；多机器人依据分配的任务规划符合运动学约束的路径。多个任务点构成任务集合，满足任务集合中不同的任务点在连续地图中不能具有相同的位置点，不同机器人分配到的任务点不能相同。
35.进一步地，所述对多机器人依据优化算法进行多任务分配，具体为：对连续地图中的多机器人起点以及任务点，依据整体适应度函数进行迭代进化，获得各个机器人分配的任务点及任务点顺序；其中，整体适应度函数为路径适应度函数与冲突适应度函数之和。
36.如图2、3所示，图2左侧部分为连续地图，连续地图中空白部分表示机器人工作的连续空间，黑色矩形表示障碍物，虚线矩形表示机器人需要执行的任务点；为了更好地展示连续区间中机器人的位置，将连续空间进行栅格化显示，如图2右侧为栅格化后的连续空间，两条黑色线段表示不同机器人通过标准a*求解的路径。所述栅格化为对连续地图提取坐标点，将一定范围内的坐标点作为一个单元格。
37.进一步地，所述对连续地图中的多机器人起点以及任务点，依据整体适应度函数进行迭代进化，获得各个机器人分配的任务点，包括：
38.如下以任务点为机器人倍数的情况进行多任务分配说明：
39.依据随机的方式，将连续地图中n个任务点平均分配给m个机器人，每个机器人及该机器人分配到的任务点构成一个基因，m个机器人基因作为一个种群个体，依据上述方式，进行p次随机分配产生p个个体；
40.对p个个体依次进行变异交叉操作，操作结束后，根据单个个体整体适应度值进行个体排序，选择整体适应度值靠前的q个个体保留，依据保留的q个个体将种群规模扩充为p个个体；依据上述变异交叉操作过程进行迭代，直至达至终止条件(在本发明的实施例中，设置的终止条件为迭代次数为50次)，将整体适应度值最小的个体保留输出，获得各个机器人分配的任务点；其中，整体适应度值靠前指的是整体适应度值小的个体q《p，从q个个体中
随机选择个体生成p-q个个体，实现将q个个体扩充为p个个体。
41.其中，n＝l*m；其中，l、m、n为正整数且l》1。
42.进一步地，每次迭代过程中的变异交叉操作具体为：
43.变异操作：对个体中每个基因进行判断，若随机生成的概率大于第一预设概率，则在任务集合范围内随机选择一个任务点序号a，将随机选择的当前基因所对应的机器人的任务点序号b变异为任务点序号a，将具有任务点序号a的基因所对应的机器人的任务点序号a替换为任务点序号b；基于该操作，可以实现在进行变异操作后，仍然满足不同机器人分配的任务不能相同。
44.交叉操作：对个体中每个基因进行判断，若随机生成的概率大于第二预设概率，则将当前基因所对应的机器人分配的全部任务点序号与同一个体中随机选择的一个基因所对应机器人分配的全部任务点序号进行替换；其中，参与替换操作的两个基因为不同的基因；比如，种群中存在1个个体，该个体有三个基因：第一基因、第二基因、第三基因，当前基因为第一基因时，随机选择的另一个基因为第二基因，则将第一基因所对应的全部任务点序号与第二基因所对应的全部任务点序号进行替换。在本发明的实施例中，第一、二预设概率均取值0.5。
45.进一步地，所述单个个体整体适应度值获取过程包括：根据每个个体中机器人分配的任务点通过标准a*算法求解机器人起点依次到达各个分配的任务点的路径长度，获得单个个体的路径适应度值；依据交点判断条件，确定每个个体中机器人路径的交点个数；依据交点个数，获得每个个体中机器人的冲突适应度值；依次每个个体中机器人的冲突适应度值，获得单个个体的冲突适应度；依据单个个体的路径适应度值、单个个体的冲突适应度，获得单个个体的整体适应度值。
46.进一步地，所述路径适应度函数为从机器人起点到各个任务点使用标准a*算法求得的路径长度总和。
47.进一步地，所述冲突适应度函数为机器人之间符合交点判断条件所产生的惩罚值总和。
48.上述中，涉及的单个基因的路径适应度函数：单个基因的冲突适应度函数：单个个体的路径适应度函数：单个个体的路径适应度函数：单个个体的冲突适应度函数：单个个体的整体适应度函数：f(n)＝f
conflict
(n) f
dist
(n)；其中，表示第i个机器人ai的路径适应度值，si表示第i个机器人ai的起点，表示第i个机器人ai分配到的第1个任务点，m表示表示第i个机器人ai分配到的任务点总数；表示依据标准a*算法求解第i个机器人ai从起点到第1个任务点的路径长度；表示第i个机器人ai的冲突适应度值，表示第i个机器人ai路径的交点个数，p表示机器人交点的惩罚值(在本发明的实施例中，设置该取值为连续地图边长1/10，连续地图为正方形)；f
dist
(n)表示第n个个体的路径适应度值，总个体数量为p；f
conflict
(n)表示第n个个体的冲突适应度值，f(n)表示第n个个体的整体适应度值。需要
说明的是，采用标准a*算法获取路径时，采用的是栅格化地图，对于机器人，以其两后轮的中心点所在位置为栅格位置。
49.进一步地，所述交点判断条件，具体为：任意两个机器人路径之间出现交点，且交点与两个机器人路径位于交点的前一个位置点之间的距离处于预设范围内，则交点计数加1；其中，前一个位置点可能为任务点或者起点。如图3所示为例，在图3左侧的部分，表示机器人发生实际碰撞，虚线矩形表示机器人需要执行的任务，纯色矩形表示机器人，在图3右侧的部分，圆圈部分表示机器人路径之间的交点。在本发明的实施例中，设置交点与两个机器人路径位于交点的前一个位置点之间的距离相等，则交点计数加1，对于存在多个机器人的工作环境，对于当前机器人而言，将其与除自身外的其它机器人路径依次进行交点判断，每判断符合条件，则交点计数加1。
50.进一步地，所述多机器人依据分配的任务规划符合运动学约束的路径，具体为：多机器人依据分配的任务使用改进类车冲突搜索算法(improved cl-cbs,pcl-cbs)规划符合运动学约束的路径；其中，cl-cbs(car-like conflict based search)。
51.进一步地，所述多机器人依据分配的任务使用改进类车冲突搜索算法规划符合运动学约束的路径，包括：
52.通过所述对多机器人依据优化算法进行多任务分配步骤获取机器人及机器人分配的任务点顺序；
53.利用混合a*算法hybrida*将所有机器人从自身起点依据任务点顺序规划获得路径，判断路径上是否出现冲突，将没有冲突的机器人路径保存，对于存在冲突的路径，搜索各个路径之间的第一个冲突，判断第一个冲突的机器人优先级条件，将优先级最高的机器人路径保存，对除优先级最高的机器人添加路径约束重新规划路径，继续搜索路径之间的下一个冲突直至所有机器人路径之间没有冲突，整合获得所有机器人符合运动学约束kinematic constraint的路径。
54.进一步地，所述机器人优先级条件，具体为：发生冲突的机器人与下一个任务点之间的距离，距离较近的机器人优先级较高。
55.应用上述技术方案可知，可以将多机器人统一规划路径，并根据出现的路径冲突以及机器人优先级，添加路径约束。即根据发生冲突的机器人距离任务点的远近，给距离较远的机器人添加约束，当完成第i个机器人ai的路径规划且没有冲突后，便将该路径信息添加到路径集合中，直至获得全部机器人没有冲突的路径规划方案。
56.根据本发明实施例的另一方面，提供了一种具有运动学约束的多任务分配与多机器人路径规划的协同调度系统，包括上述中任意一项所述方法的模块，具体包括：用于对连续地图中多机器人输入起点的模块；用于将连续地图中加入多个任务点的模块；用于对多机器人依据优化算法进行多任务分配的模块；用于多机器人依据分配的任务规划符合运动学约束的路径的模块。
57.根据本发明实施例的另一方面，提供了一种处理器，所述处理器用于运行程序，其中，所述程序运行时执行上述中任意一项所述的具有运动学约束的多任务分配与多机器人路径规划的协同调度方法。
58.根据本发明实施例的另一方面，提供了一种计算机可读存储介质，所述计算机可读存储介质包括存储的程序，其中，在所述程序运行时控制所述计算机可读存储介质所在
设备执行上述中任意一项所述的具有运动学约束的多任务分配与多机器人路径规划的协同调度方法。
59.下面对本发明一种可选的实施方式进行详细说明：
60.如图5，在50m*50m的无障碍地图中，两个机器人编号分别为1,2，设置任务数量为4，机器人大小为2m*3m。机器人移动速度为2m/s。已知当初始时刻，t＝0时，机器人分别在各自的起点位置，图中标有数字的黑色块矩形表示地图中存在的机器人，虚线矩形表示机器人需要完成的任务点。路径规划步骤如下：
61.步骤1，由给定的连续地图，地图中存在2个机器人组成的一组多机器人a＝{a1,a2}，4个任务点组成的任务集合t＝{t1,t2,
…
,t4}，每个机器人都有一个起点、两个任务点，标数字的黑色块矩形在t＝0时刻所在位置代表起点，标数字的虚线矩形代表任务点。
62.步骤2，一组机器人在规划路径之前引入优化算法分配任务，优化算法采用遗传算法架构，由于多任务分配与多机器人路径规划中任务数量较多，通过该优化算法分配，可以实现为多机器人分配多任务，达到减少路径长度、降低系统运行时间的效果。由于机器人随机分配任务，为了获得无冲突路径，会带来机器人路径长度过大、重新规划次数较多的不足，基于此，本发明采用路径适应度和冲突适应度函数，减少机器人执行任务的路径长度和可能发生的冲突次数，并进一步配合改进类车冲突搜索算法规划方法，更进一步地提升效果。
63.步骤3，依据分配的任务进行规划，执行的任务顺序为分配得到的顺序，对所有机器人进行统一路径规划；规划过程中涉及冲突处理，系统将机器人路径规划中出现的冲突按照机器人优先级添加约束，进一步进行规划，最终所有机器人规划出的无冲突路径整合为完整规划方案；其中，冲突判断过程为：所有机器人利用混合a*算法求解路径，判断是否存在机器人之间的冲突，若发生冲突，判断机器人优先级条件：发生冲突的机器人与下一个任务点之间的距离，距离较近的机器人优先级较高；混合a*算法选取扩展节点的规则是使路径所消耗的代价值最小，时间最短，且满足运动学约束。如图4中，1号机器人在路径规划时，与2号机器人发生冲突，在判断了1号和2号机器人的优先级之后，1号机器人由于优先级较低，重新规划路径，而2号机器人则直接通过冲突区域。
64.如下以图5所示，给出具体地路径规划过程：
65.在路径规划开始前，为1号机器人随机分配任务1和4，2号机器人随机分配任务2和3，经过任务规划后，1号机器人分配得到的任务为1和3，2号机器人分配得到的任务为2和4。
66.机器人a1的路径扩展：在时刻t＝0，机器人a1位于起始点(18，2，0)(18表示机器人a1的x轴坐标位于连续地图的18m处，2表示机器人a1的y轴坐标位于连续地图的2m处，0表示机器人a1的偏转角度为0度，后续同理)，依据混合a*算法获得扩展节点(20，2，0)这个位置，其扩展节点(20，2，0)，在t＝1时刻满足不会与其它机器人冲突，依次类推，在t＝2时刻其扩展节点为(22，2.7，5.5)，在t＝3时刻其扩展节点为(23.5，4，5.5)，在t＝4时刻其扩展节点为(24.5，5.9，4.9)，在t＝5时刻其扩展节点为(24.3，7.9，4.2)，在t＝6时刻其扩展节点为(23.4，9.5，4.2)，在t＝7时刻其扩展节点为(23，11，-1.57)，至此机器人a1完成了1号任务；此时机器人a1继续完成3号任务在t＝8时刻其扩展节点为(22.3，9，5.4)，在t＝9时刻其扩展节点为(24，10，6.1)，在t＝10时刻其扩展节点为(26.1，9.7，0.5)，在t＝11时刻其扩展节点为(28，8.6，0.5)，在t＝12时刻其扩展节点为(29，7.5，9.5)，在t＝13时刻其扩展节点为
(31.5，6.3，0.5)，在t＝14时刻其扩展节点为(33.3，5.3，0.5)，在t＝15时刻其扩展节点为(35.2，4.1，0.5)，在t＝16时刻其扩展节点为(37，3，0.5)，在t＝17时刻其扩展节点为(38.7，2，0.5)，在t＝18时刻其扩展节点为(40.6，0.8，0.5)，在t＝19时刻其扩展节点为(42.6，0.4，6.1)，在t＝20时刻其扩展节点为(43.7，0.8，5.7)，在t＝21时刻其扩展节点为(45.5，2，5.7)，在t＝22时刻其扩展节点为(46.4，2.5，5.7)，在t＝22时刻其扩展节点为(48，3，0)，至此机器人a1完成了3号任务。
67.接着另一个机器人a2的路径扩展：在时刻t＝0，机器人a2位于起始点(14，17，1.57)，依据混合a*算法获得扩展节点(14.7，15，0.8)这个位置，其扩展节点(14.7，15，0.8)在t＝1时刻满足不会与其它机器人冲突，依次类推，在t＝2时刻其扩展节点为(16.5，14，0.1)，在t＝3时刻其扩展节点为(18.5，14.4，5.7)，在t＝4时刻其扩展节点为(19.8，16，5)，在t＝5时刻其扩展节点为(19.8，18.1，4.3)，在t＝6时刻其扩展节点为(18.9，20.1，4.3)，在t＝7时刻其扩展节点为(18.1，22，4.3)，在t＝8时刻其扩展节点为(17.3，24，4.3)，在t＝9时刻其扩展节点为(17.3，26，5)，在t＝10时刻其扩展节点为(17.9，28，5)，在t＝11时刻其扩展节点为(18.6，30.1，5)，在t＝12时刻其扩展节点为(19.4，32.2，5)，在t＝13时刻其扩展节点为(20.2，34.2，5)，在t＝14时刻其扩展节点为(20.6，35.3，5)，在t＝15时刻其扩展节点为(20.6，37.4，4.3)，在t＝16时刻其扩展节点为(19.3，39，3.6)，在t＝17时刻其扩展节点为(19，39.2，3.5)，在t＝18时刻其扩展节点为(20，39，3.14)，至此机器人a2完成了2号任务；此时机器人a2继续完成4号任务，在t＝19时刻其扩展节点为(22.1，39，3.14)，在t＝20时刻其扩展节点为(24.2，39，3.14)，在t＝21时刻其扩展节点为(28.2，38.3，3.8)，在t＝22时刻其扩展节点为(29.9，37，3.8)，在t＝23时刻其扩展节点为(30.4，36.5，3.8)，在t＝24时刻其扩展节点为(32.4，35.8，3.1)，在t＝25时刻其扩展节点为(34.3，36.6，2.4)，在t＝26时刻其扩展节点为(34.6，36.9，2.3)，在t＝27时刻其扩展节点为(34，35，1.57)，至此机器人a2完成了4号任务。
68.应用上述技术方案可知，若机器人随机选择任务，路径长度和重新规划次数将增加，通过任务规划后，机器人按照系统探索出的路径行进，使得机器人之间路径交汇减少，从而减少路径长度的同时，降低了冲突出现的概率，因而本发明提高系统的快速性和安全性。
69.进一步地，结合实验数据验证本发明的性能：
70.一、选取典型地图算例50m*50m的地图中，以执行时间作为路径规划终止条件(本实施例中取60s)，分别随机选取2个机器人以及10、20个任务进行十次实验，运行平均时间分别为0.007，0.032秒；最大完工时间分别为96.657、203.809秒，见表1。
71.表1
[0072][0073]
二、选取典型仓储地图50m*50m以及100m*100m地图，在50m*50m地图中分别随机选取8,10,14个任务以及2个机器人；在100m*100m地图中分别随机选取10、20、30个任务以及5个机器人，每张地图进行十次本发明方法优化算法 改进类车冲突搜索算法(ga pcl-cbs)，
随机任务分配 类车冲突搜索算法(r cl-cbs)和优化算法 类车冲突搜索(ga cl-cbs)的对比实验，以执行时间为终止条件(本实施例中取60s)。通过图6可知(横坐标为任务数量、纵坐标为时间/s)，本发明方法、ga cl-cbs性能远远优于r cl-cbs，而将本发明方法对比ga cl-cbs在最大完工时间有小幅度升高的基础上，可以大大缩短系统运行时间。
[0074]
上面结合附图对本发明的具体实施方式作了详细说明，但是本发明并不限于上述实施方式，在本领域普通技术人员所具备的知识范围内，还可以在不脱离本发明宗旨的前提下做出各种变化。