本发明涉及智能制造领域，具体涉及一种基于路径方案和通行优先权协同进化的多agv路径规划方法。
背景技术：
1、自动导引车(automatic guided vehicle,agv)是一种可用于物料搬运的无人驾驶车，由多台agv组成的agv系统具有运输高效、自动化、柔性化和快速响应等优点，被广泛应用于制造车间、仓储和码头等领域。对于agv系统，多agv路径规划一直是一个热门研究点，其核心在于两点，一是为每台agv需执行的每个任务规划出一条优质路径，二是多条路径间的路径冲突的避免。具体为各任务的路径方案的决策问题，和执行各任务的agv在冲突路径的通行优先权的决策问题。路径方案决定了各任务的行驶距离和可能存在的路径冲突；通行优先权决定了，为避免路径冲突，执行低通行优先权任务的agv如何调整该任务对其的路径方案中各路径段的占用时间窗。因此，路径方案和通行优先权共同决定了多agv路径规划方案的性能。需注意的是，为解决现有路径冲突而进行的占用时间窗的调整，可能导致新的路径冲突，也就是，同一路径方案在不同通行优先权方案下需解决的路径冲突存在差异。此外，同一通行优先权方案下，不同路径方案需解决的路径冲突也不相同。因此，为获得一个优质的多agv路径规划方案，考虑路径方案和通行优先权之间的决策影响是有研究价值的。然而，目前的多agv路径规划方法中，通常采用的策略为独立决策，即基于某一目标为各任务规划一条优质路径，基于某一规则确定执行任务的agv的通行优先权，然后基于时间窗调整或局部路径更新等方法解决出现的路径冲突。如公开号为cn116679694a，专利名称为一种多agv调度的优化方法的中国发明专利，其首先基于遗传算法得到各agv的配送任务的最优路径，然后基于时间窗方法判断不同配送任务的最优路径间是否存在冲突，并采用为较低任务优先级的最优路径设置等待时间或更换最优路径的方法进行冲突规避，最后得到多台agv的无冲突、最短的配送路径。在该专利中，任务的优先级，即通行优先权是固定不变的，公开的方法并未考虑路径方案和通行优先权之间的决策影响。
2、此外，在复杂大型设备装配线中，物料的重量、尺寸差异较大，agv系统中需要同时处理针对常规尺寸组件的单agv物料搬运任务和针对大尺寸部件的多agv协同搬运任务。针对多agv协同搬运任务，其由多个agv协同执行，涉及到每个agv的集结过程，和所有agv共同执行的送货过程。由于只有所有agv都完成集结过程后，才可进行agv队列编队，然后完成装载并进入送货过程，因此，在为多agv协同搬运任务进行路径规划时，存在一个特有问题，即多个agv的集结过程应尽量同时结束。然而，现有的多agv路径规划研究中，其研究对象集中于单agv物料搬运任务，如公开号为cn116224923a，专利名称为一种考虑冲突规避的多agv路径规划方法的中国发明专利申请。上述研究中，不需要考虑多agv协同搬运任务的特有问题，因此并不适用于复杂大型设备装配线场景。
3、因此，亟需一种适用于复杂大型设备装配线且考虑路径方案和通行优先权之间的决策影响的多agv路径规划方法。
技术实现思路
1、为解决现有技术中存在的技术缺陷，本发明提出了基于路径方案和通行优先权协同进化的多agv路径规划方法，通过将种群拆分为两个子种群——路径方案子种群和通行优先权解子种群，两个子种群并行迭代进化，并在迭代进化中互相验证求解对方子种群中各解的质量，从而充分考虑了多agv路径规划问题中路径方案与通行优先权之间的决策影响；通过将任务拆分为取货子任务和送货子任务，将问题转化为各子任务的路径方案决策和通行优先权决策问题，可在迭代进化中，考虑到多agv协同搬运任务的特有问题。
2、本发明通过以下技术方案实现：
3、基于路径方案和通行优先权协同进化的多agv路径规划方法，包括以下步骤：
4、步骤1：判断是否执行了任务分配操作，若是，获得任务分配方案和任务执行顺序，进入步骤2，若否，进入步骤1。
5、所述任务分配方案，为各任务与各agv间的分配关系。
6、步骤2：根据任务分层策略，形成由多层任务层组成的任务分层表。
7、所述任务分层表，存放有参与本次任务分配操作的所有任务。
8、所述任务，由单agv搬运任务和多agv协同搬运任务组成。
9、所述单agv搬运任务，由一个取货子任务和一个送货子任务组成。
10、所述多agv协同搬运任务，由多个取货子任务和一个送货子任务组成。
11、所述取货子任务，为任务的一个执行agv从所在位置到任务的物料装载点的行驶任务。
12、所述送货子任务，为任务的所有执行agv从物料装载点到物料卸载点的行驶任务。
13、步骤3：基于任务分层表，根据通行优先权随机解生成规则，随机生成多个通行优先权解，形成初始通行优先权子种群。
14、所述通行优先权解，由所有任务的子任务的通行优先权的编码组成。
15、所述子任务的通行优先权，为当多个执行子任务的agv间存在路径冲突时，各agv获得冲突路径段的路径使用权的优先级。
16、步骤4：根据路径方案随机解生成规则，随机生成多个路径方案解，形成初始路径方案子种群。
17、所述路径方案解，由所有任务的子任务的路径方案的编码组成。
18、步骤5：形成由初始通行优先权子种群和初始路径方案子种群构成的初始种群，根据适应度求解法计算初始种群中各解的适应度，并确定各解的配对解。
19、所述通行优先权子种群与所述路径方案子种群，互为彼此的互补子种群。
20、所述适应度求解法，具体为：
21、当求解一个子种群中一个解的适应度时，首先将该解与互补子种群中每个解逐一配对形成完整个体，接着解码完整个体得到各子任务的路径方案和通行优先权，检测存在的路径冲突，并基于子任务的通行优先权调整存在冲突的多个子任务对冲突路径的占用时间窗，从而避免路径冲突，然后计算所有个体的适应度，最后以所有完整个体中的最优个体的适应度为该解的适应度值。
22、所述配对解，为与一个解形成最优个体的互补子种群的解。
23、步骤6：运用智能优化算法迭代更新种群，直到满足终止条件，输出最优解及其配对解，解码获得由各子任务的路径方案和各子任务的通行优先权组成的多agv路径规划方案。
24、进一步地，所述任务分层策略，包括以下步骤：
25、步骤2.1：令x为1，令s为1，将任务执行顺序中的第s个任务放入任务分层表的第x层，并将第s个任务的所有执行agv放入任务分层表的第x层的任务层agv集，令s为s+1，令a为x。
26、所述任务层agv集，为放于该任务层的所有任务的执行agv的集合。
27、步骤2.2：判断任务执行顺序中的第s个任务的任务执行agv集与任务分层表的第a层的任务层agv集是否有交集，若否，令a为a-1，进入步骤2.3，若有，令a为a+1，进入步骤2.4。
28、所述任务执行agv集，为分配去执行该任务的所有agv的集合。
29、步骤2.3：判断a＝0是否成立，若是，令a为a+1，将任务执行顺序中的第s个任务放入任务分层表的第a层，并将第s个任务的所有执行agv放入任务分层表的第a层的任务层agv集，进入步骤2.5，若否，进入步骤2.2。
30、步骤2.4：将任务执行顺序中的第s个任务放入任务分层表的第a层，并将第s个任务的所有执行agv放入任务分层表的第a层的任务层agv集，判断a>x是否成立，若是，令x为a，进入步骤2.5，若否，进入步骤2.5。
31、步骤2.5：令s为s+1，判断任务执行顺序中是否存在第s个任务，若存在，令a为x，进入步骤2.2，若否，结束本策略的调用。
32、进一步地，所述通行优先权随机解生成规则，包括以下步骤：
33、步骤3.1：令b为1，复制任务分层表，得到临时任务分层表。
34、步骤3.2：设置临时任务分层表的第b层为编码层，打包临时任务分层表的第b层的所有任务，形成编码层任务集，打包编码层任务集中的所有可变层任务，形成编码层可变层任务集，为编码层任务集中所有任务的子任务随机生成通行优先权，得到第b层的通行优先权。
35、所述通行优先权，其随机生成需满足条件：
36、第b层的所有任务的子任务的通行优先权，均需低于第b-1层的任一任务的任一子任务的通行优先权。
37、所述可变层任务，其定义如下：
38、假设一个任务位于任务分层表的第d层，且任务分层表存在第d+1层，如果该任务的所有执行agv与位于任务分层表的第d+1层的所有任务的执行agv均无相同agv，那么该任务为可变层任务。
39、步骤3.3：判断编码层可变层任务集是否为空，若是，令b为b+1，进入步骤3.7，若否，令c为1，进入步骤3.4。
40、步骤3.4：判断编码层可变层任务集中是否存在第c个任务，若存在，设置编码层可变层任务集中的第c个任务为待定任务，进入步骤3.5，若否，令b为b+1，进入步骤3.7。
41、步骤3.5：判断第b+1层是否为第c个任务的任务可变层，若是，进入步骤3.6，若否，令c为c+1，进入步骤3.4。
42、所述任务可变层，其定义如下：
43、假设一个可变层任务位于任务分层表的第d层，如果该任务的所有执行agv与位于任务分层表的第d+1层到第d+e层的所有任务的执行agv均无相同agv，那么任务分层表的第d层到第d+e层为该可变层任务的任务可变层。
44、步骤3.6：判断待定任务的所有子任务的通行优先权是否均低于编码层任务集中所有非可变层任务的子任务的通行优先权，若是，取消为待定任务的所有子任务生成的通行优先权，并将待定任务从临时任务分层表的第b层移到第b+1层，令c为c+1，进入步骤3.4，若否，令c为c+1，进入步骤3.4。
45、步骤3.7：临时任务分层表是否存在第b层，若是，进入步骤3.2，若否，合并所有层的通行优先权编码得到一个随机生成的优先权解，结束本规则的调用。
46、进一步地，所述路径方案随机解生成规则，包括以下步骤：
47、步骤4.1：获取所有任务的子任务，形成子任务集，令f为1。
48、步骤4.2：获得子任务集中第f个子任务的任务起点和任务目标点，确定与该子任务匹配的路径库，从匹配的路径库中随机选择一个路径方案分配给该子任务，得到该子任务的路径方案编码，令f为f+1。
49、所述路径库，其由一个特定起点和一个特定目标点间的路径最短的多个路径方案组成。
50、步骤4.3：判断子任务集是否存在第f个子任务，若存在，进入步骤4.2，若否，合并所有子任务的路径方案编码得到一个随机生成的路径方案解，结束本规则的调用。
51、进一步地，所述智能优化算法，为改进蜜獾算法，其改进点至少包含改进密度因子更新公式、邻域搜索策略和聚类淘汰策略中的一个。
52、进一步地，所述改进密度因子更新公式，如下：
53、
54、式中，αi为种群中第i个蜜獾的密度因子，c为常量，默认为2，w为当前迭代代数，wmax为最大迭代代数，fi为第i个蜜獾的适应度值；fmax为上一代中最差个体的适应度值；fmin为上一代中最优个体的适应度值。
55、进一步地，所述邻域搜索策略，具体为搜索解的所有邻域解，如果邻域解优于当前解，则用邻域解替换子种群中的原解，并更新解的适应度和配对解。
56、进一步地，所述邻域解，其获得方法如下：
57、对于路径方案解，将该解的编码中的某一位改为匹配路径库中的下一路径方案的编码，其它位保持不变，可得到该解的一个邻域解；
58、对于通行优先权解，将该解的编码中的任意相邻的两个位置的码进行位置交换，其它位保持不变，可得到该解的一个邻域解。
59、进一步地，所述聚类淘汰策略，包括以下步骤：
60、步骤6.1：在每代的一个子种群更新结束后，设置该子种群为目标子种群，将目标子种群中的解从优到劣进行排列，形成序列subip，将subip中的首个解设置为第1个簇的簇中心，获得目标子种群中解的编码长度nrp，设置y为2，设置z为2。
61、步骤6.2：判断subip中是否存在第z个解，若存在，进入步骤6.3，若否，进入步骤6.4。
62、步骤6.3：计算subip中的第z个解距离所有簇中心的海明距离，判断海明距离是否均大于ceil(0.1×nrp)，若是，将该解设置为第y个簇的簇中心，令y+1，若否，将该解分配到距其最近的簇，并标记为淘汰解。
63、步骤6.4：令z为z+1，进入步骤6.2。
64、步骤6.5：对于每一个淘汰解，生成一个随机解替换掉目标子种群中的该解，同时更新解的适应度和配对解。
65、与现有技术相比，本发明至少具有下述的有益效果或优点：
66、本发明提出了基于路径方案和通行优先权协同进化的多agv路径规划方法，通过将种群拆分为两个子种群——路径方案子种群和通行优先权解子种群，且两个子种群并行迭代进化，并在迭代进化中互相验证求解对方子种群中各解的质量，从而充分考虑了多agv路径规划问题中路径方案与通行优先权之间的决策影响；通过将任务拆分为取货子任务和送货子任务，将问题转化为各子任务的路径方案决策和通行优先权决策问题，可在迭代进化中，考虑到多agv协同搬运任务的特有问题。综上，本发明为存在多agv协同搬运任务的复杂大型设备装配线提供了一种有效的多agv路径规划方法；且相比于现有研究中的方法，本发明公开的方法中路径方案和通行优先权均是迭代变化的，更有机会获得最优的多agv路径规划方案。
1.基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，包括以下步骤：
2.根据权利要求1所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述根据任务分层策略形成由多层任务层组成的任务分层表包括以下步骤：
3.根据权利要求1所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述步骤3包括以下步骤：
4.根据权利要求1所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述s4包括以下步骤：
5.根据权利要求1所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述改进的蜜獾算法，包含改进密度因子更新公式、邻域搜索策略和聚类淘汰策略中的一个。
6.根据权利要求5所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述改进密度因子更新公式，为：
7.根据权利要求5所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述邻域搜索策略，具体为搜索解的所有邻域解，如果邻域解优于当前解，则用邻域解替换子种群中的原解，并更新解的适应度和配对解。
8.根据权利要求5所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述聚类淘汰策略，包括以下步骤：
9.根据权利要求7所述的基于路径方案和通行优先权协同进化的多agv路径规划方法，其特征在于，所述邻域解，其获得方法如下：
