本发明涉及一种复杂狭窄环境下多机器人系统协同综合调度方法，属于多机器人系统调度规划。
背景技术：
1、多机器人系统因其高效、低成本、高安全性和作业标准化等优点，正广泛应用于智能仓库、自动化港口、无人工厂和智能农业等领域，从而显著提升了整体智能水平。
2、当前，多机器人系统的研究主要集中在协调调度方面，通过合理的任务分配和路径规划，使系统能够快速、高效且低能耗地完成任务。目前，尽管现有的多机器人系统在开放环境中表现良好，但在狭小空间内的应用较少。而在任务分配方面，现有的解决方案通常将其转化为多约束优化问题，主要难点依然是如何根据实际情况建立更为贴近实际的模型与编码和解码机制，提高求解的准确性和高效性，并减少任务执行过程中机器人之间的拥堵和冲突。多车路径规划的研究主要集中在搜索和优化算法上，但大多数仅考虑智能体在基本方向上的运动，忽略了智能体的大小和运动学约束。尽管部分研究考虑了车辆的运动学约束，但通常将场景抽象为拓扑图，或在非结构化环境中存在少量障碍物，因此难以应用于设备密度较高的工厂或车辆较多的滚装码头环境中。
技术实现思路
1、本发明的目的是提供一种复杂狭窄环境下多机器人系统协同综合调度方法，适用于四轮独立驱动和独立转向机器人，该方法能够根据现有地图及机器人的位置和朝向信息、机器人需要执行的任务的位置和朝向信息，进行任务分配和无冲突路径规划，根据无冲突路径实现多机器人系统的协同综合调度。
2、本发明的目的是通过下述技术方案实现的。
3、本发明公开的一种复杂狭窄环境下多机器人系统协同综合调度方法，包括以下步骤：
4、步骤1：设计粒子编码规则。
5、粒子的编码方式选用整数编码，粒子的每个位置代表一个任务分配方案，每个位置上包含m个维度，每个维度代表一个任务，根据执行任务的机器人数量对粒子位置上所包含的维数进行均分，根据总任务数量m、机器人数量和任务所在的维度，获取执行各任务的机器人编号以及每个机器人执行任务的次序信息；
6、每个位置包含m个维度，即存在m个需执行的任务，当机器人数量为n个，则第1维到m/n维为第一个机器人所要执行的任务，第m/n+1维到第2m/n维为第二个机器人所要执行的任务，依次类推，且第一个机器人任务执行的顺序为第1维、第2维、……、第m/n维上的任务。
7、步骤2：构建粒子群上各粒子所在位置的适应度值计算方法。
8、将单个机器人最小行驶距离成本、所有机器人总行驶距离成本以及所有机器人总运动模态切换成本作为粒子不同位置上所代表的任务分配方案的评价指标，根据公式(1)计算粒子群中各粒子所在位置的适应度值；
9、fallcost＝α1fmindisence+α2falldisance+α3fswitch (1)
10、其中：fmindisence为单个机器人最小行驶距离成本，falldisance为所有机器人总行驶距离成本，fswitch为机器人总运动模态切换成本，αi(i＝1，2，3)为三个成本的权重；
11、单个机器人最小行驶距离成本计算过程为：首先根据单个粒子上所确定的所有机器人任务执行顺序，获得各个机器人由起始点到执行完所有任务所需要的距离，选取所有机器人中最小的距离作为单个机器人最小行驶距离成本；
12、所有机器人总行驶距离计算过程为：首先根据单个粒子上所确定的所有机器人任务执行顺序，获得各个机器人由起始点到执行完所有任务所需要的距离，将所有机器人所需要的距离加和作为所有机器人总行驶距离成本；
13、所述获得各个机器人由起始点到执行完所有任务所需要的距离的方法为：基于地图采用a*搜索方法获取机器人由起始点到第一个任务点、第一个任务点到第二个任务点、……，第m-1个任务点到第m个任务点的代价值，并把所有代价值进行累加以作为机器人由起始点到执行完所有任务所需要的距离。
14、所有机器人总运动模态切换成本计算过程为：根据单个粒子上所确定的所有机器人任务执行顺序，获得各个机器人由起始点到首个任务点，以及按执行顺序两两任务点之间的朝向角之差，并将获得的单个机器人的所有朝向角之差进行累计以估算各个机器人的运动模态切换代价，将所有机器人的运动模态切换代价加和作为总运动模态切换成本。
15、步骤3：确定迭代过程中粒子的速度和位置更新准则，以对粒子的速度和位置进行更新。
16、对粒子群进行迭代更新时，通过公式(2)对粒子迭代的速度和位置进行更新，其中惯性权重和学习因子在迭代进化过程中根据迭代的次数及粒子聚集程度进行自适应调整；
17、
18、其中：分别表示第i个粒子第t+1次更新迭代的位置和速度，分别表示第i个粒子第t次更新迭代的位置和速度，d为该粒子位置上的维度信息；分别表示截止到第t次迭代，第i个粒子的局部最优位置和粒子群中的全局最优位置；r1和r2为[0,1]内的均匀随机数；ω为惯性权重；c1为局部位置的学习因子，c2为全局位置的学习因子；
19、在粒子迭代更新计算过程中，当计算出的粒子位置的维度上的值存在非整数时，则根据该非整数与其临近的两个整数值的差来确定上下取整的概率p，具体公式(3)：
20、
21、其中，为向上取整后的值，为向下取整后的值；
22、粒子更新后，如果同一个粒子不同维度上存在同一个值时，即任务被重复分配，此时则随机选取删除其中一个任务，从未被分配任务中随机选取一项任务进行填充，确保任务的完整性。
23、步骤4：确定交叉与变异准则。
24、从当前粒子群中随机选取粒子并组成n/2对粒子作为父代，在两个粒子的任意位置随机选择两个片段进行交换产生新的粒子；并以设定的概率对交叉后的粒子进行随机变异，所述随机变异为随机选取粒子上的某个维度的任务进行更改，更改后的任务应包含在所有需执行的任务内；当粒子交叉变异后，如果同一个粒子不同维度上存在同一个值时，即任务被重复分配，此时则随机选取删除其中一个任务，从未被分配任务中随机选取一项任务进行填充，确保任务的完整性。
25、步骤5：初始化粒子群并开始迭代，获取任务分配结果。
26、s51：初始化粒子群，生成n个粒子，根据步骤1的粒子编码准则，将需执行的任务随机分配到同一个粒子的不同维度上，当n个粒子都完成任务的随机分配后，得到n个粒子的初始位置，即得到n个任务分配方案；
27、s52：采用步骤2的方法，计算步骤s51得到的n个粒子的初始位置的适应度值；并比较各粒子的适应度值，将适应度值最小的粒子位置设为粒子群中的全局最优位置，将各粒子的初始位置设为各粒子的局部最优位置；
28、s53：根据步骤s52所得到的局部最优位置和全局最优位置以及步骤3中所确定的迭代过程中粒子的速度更新准则，计算各粒子迭代的速度，并根据所计算的粒子迭代速度按照步骤3中所确定的迭代过程中粒子的位置更新准则，更新各粒子的位置；
29、s54：根据s53所更新后的粒子群的粒子位置信息以及步骤4中所确定的交叉与变异准则，对粒子群进行交叉与变异，并在变异和交叉完成后，将交叉变异后产生的n/2个粒子与原有粒子群中的n个粒子按适应度值进行排序，按照精英保留原则，按适应度值由小到大的选取新n个粒子进入下一代粒子群的迭代过程；
30、同时将新产生的粒子群中的最小适应度值与原粒子群中的全局最优位置粒子的适应度值进行比较，并将适应度值小的粒子位置设为粒子群中的全局最优位置；选取的新n个粒子中，如果粒子为交叉编译后新产生的粒子，则该粒子的当前位置为本粒子的局部最优位置，如果粒子是未进行交叉变异的粒子，则比较该粒子位置与其局部最优位置粒子的适应度值，当该粒子位置的适应度值小于其局部最优位置粒子的适应度值时，将该粒子的位置设为该粒子的局部最优位置，当该粒子位置的适应度值大于其局部最优位置粒子的适应度值时，保持该粒子的局部最优位置不变；
31、s55：基于步骤s54获取的n个粒子、粒子群中的全局最优位置以及各粒子的局部最优位置，再次根据步骤3确定的迭代过程中粒子的速度和位置更新准则以及步骤4确定的交叉与变异准则，对粒子进行反复迭代更新与交叉变异，即重复步骤s53和s54；当迭代次数达到设定值后，停止粒子更新和交叉变异过程，并对全局最优位置的粒子按照步骤1的编码方式进行解码，得到分配给每个机器人的任务及执行顺序。
32、步骤6：基于改进混合a*搜索算法构建单个机器人路径规划算法。
33、单个机器人路径规划算法为改进混合a*搜索算法，如公式(4)至公式(6)，在成本函数g中引入转向惩罚和不同运动模式之间的切换惩罚；在成本函数h中引入当前节点到终点的朝向代价；此外，当前节点与终点的距离小于设定距离时，分别调用直行和横移的reeds-shepp曲线生成函数来计算一条从当前点到终点的不考虑静态障碍物的reeds-shepp曲线路径，如果该曲线路径未与环境障碍物发生碰撞，则认为该路径可行，直接生成由该节点到终点的路径，否则，继续搜索可行驶路径；引入自适应启发权重ξ因子，ξ根据机器人当前位置与目标点的位置自适应调整，以在求解过程中平衡最优性与求解速度之间的折衷；
34、所述ξ根据机器人当前位置与目标点的位置自适应调整的准则为：在机器人向目标点移动过程中，不同距离区间内设定不同的ξ值，其原则为随着机器人向目标点的距离变小，ξ也会变小；
35、所述的转向惩罚为机器人处于前进左转状态、前进右转状态、后退左转状态或后退右转状态时所增加的惩罚；所述的不同运动模式之间的切换惩罚为机器人在进行直行、后退、横移、自转、转向运动状态切换时所增加的惩罚。
36、g(s)＝g(sf)+λturn·dist(sf，s)+λswitch·dist(sf，s) (4)
37、h(s，sgoal)＝ho(s，sgoal)+hh(s，sgoal) (5)
38、f(s)＝g(s)+ξ*h(s，sgoal) (6)
39、式中，f(s)为代价，g(s)为机器人由起始点至当前位置的路径代价，h(s，sgoal)为机器人由当前位置至终点的预估代价，g(sf)表示父节点累计代价，dist(sf，s)表示当前节点到父节点的距离代价，λturn代表转向惩罚因子，λswitch代表运动模式切换惩罚因子，ho(s，sgoal)为当前位置到终点的曼哈顿距离；hh(s，sgoal)表示当前节点到终点的朝向代价；ξ为启发权重因子。
40、步骤7：生成多机器人的无冲突路径，根据无冲突路径实现多机器人系统的协同综合调度。
41、s71：基于现有地图、步骤5所获取的任务分配结果，步骤6的单机器人路径规划算法，生成所有机器人的可行驶路径；
42、s72：对步骤s71生成的所有机器人的可行驶路径进行冲突检测，判断是否存在同一时刻，地图上的同一位置出现两个以上机器人，如果不存在，则生成多机器无冲突路径；如果存在，则随机保留一个机器人的路径，并生成其他机器人在冲突时刻冲突位置的约束，即不允许其在冲突时刻出现在该位置；
43、s73：基于现有地图、步骤5所获取的任务分配结果，步骤6的单机器人路径规划算法以及步骤s72生成的位置约束，再次进行单机器人可行驶路径生成，并根据步骤s72中的冲突检测方式进行冲突检测，如有冲突则再次增加位置约束，并重复生成单机器人路径、冲突检测、增加位置约束过程，直到获得多个机器人无冲突路径，根据无冲突路径实现多机器人系统的协同综合调度。
44、有益效果：
45、1、本发明公开的一种复杂狭窄环境下多机器人系统协同综合调度方法，采用适用于四轮独立驱动和独立转向机器人的协同综合调度框架，首次将四轮独立驱动和独立转向机器人用于多机器人系统，同时充分考虑机器人的尺寸和运动学约束，能够直接应用于设备密度较高的工厂或车辆密集的滚装码头环境。
46、2、本发明公开的一种复杂狭窄环境下多机器人系统协同综合调度方法，利用自适应粒子群遗传算法解决狭小空间内的任务分配问题，并采用a*搜索的代价替代传统的距离计算方式，以获取在求解适应度时机器人与任务以及任务之间的距离。根据迭代进化过程和粒子聚集程度自适应调整算法参数，该方法比传统的粒子群算法和遗传算法更有效地解决狭小空间内的任务分配问题。
47、3、本发明公开的一种复杂狭窄环境下多机器人系统协同综合调度方法，采用改进的混合a*机器人路径搜索算法，考虑运动模式切换，并引入自适应启发权重以加速单车搜索过程。该方法利用冲突搜索算法进行机器人之间的冲突检测与消除，获得所有机器人的最优任务行驶路径。本发明不仅适用于对狭小空间内的四轮独立驱动和独立转向机器人，也可以应用于其他场景下的四轮独立驱动和独立转向机器人，如巡检和运输等。
1.一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：适用于四轮独立驱动和独立转向机器人，该方法能够根据现有地图及机器人的位置和朝向信息、机器人需要执行的任务的位置和朝向信息，进行任务分配和无冲突路径规划；包括以下步骤，
2.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤1的具体实现方法如下，
3.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤2的具体实现方法如下，
4.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤3的具体实现方法如下，
5.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤5的具体实现方法如下，
6.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤6的具体实现方法如下，
7.如权利要求1所述一种复杂狭窄环境下多机器人系统协同综合调度方法，其特征在于：步骤7的具体实现方法如下，
