基于混沌自适应蜣螂优化算法的多机器人任务分配方法

1.本发明属于机器人技术领域，更进一步涉及多机器人任务分配技术领域中的一种基于混沌自适应蜣螂优化算法的多机器人任务分配方法。本发明可应用于由无人机、无人船和无人船等组建的多机器人系统中，实现将一组任务有效地分配给多个异构机器人，以实现系统地高效协同。


背景技术：

2.近年来，机器人在军用和民用领域发挥着越来越重要的作用。然而，随着任务需求的不断增加，单个机器人往往难以独自完成复杂的任务，因此多机器人系统应运而生。在多机器人系统中，任务分配是一个关键技术，它涉及到如何将一组任务有效地分配给多个机器人，以实现系统地高效协同。例如，在服务机器人、工业机器人以及无人驾驶等领域，合理的任务分配可以提高这些系统的整体效率。特别是，无人驾驶技术在地面搜救、快递运输、测绘、监视或勘探等场景下得到了广泛应用。现有的多机器人任务分配方法主要有三种，第一种是基于传统算法的任务分配方法，此类算法大多针对具体结构化问题，但难以解决中、大规模的多机器人任务分配问题。第二种是基于强化学习算法的任务分配方法，此类算法具有求解速度快、模型泛化能力强的优势，但存在预训练时间长和奖励函数设计困难等问题。第三种是基于智能优化算法的任务分配方法，此类算法通过模拟自然界生物群体的协同行为，因其简单、易于实现和鲁棒性强等优点而受到广泛关注，但在解决多机器人任务分配问题时存在极易陷入局部最优的问题，降低了任务分配的效率。
3.南京理工大学在其申请的专利文献“一种预分配结合匈牙利算法的多机器人任务分配方法”(申请号：201811385884.1申请日：2018.11.20申请公布号：cn 109615188a)中公开了一种预分配结合匈牙利算法的多机器人任务分配方法。该方法的具体步骤是，第一步：基于角色协作的模型对多机器人系统建模；第二步：建立所有机器人承担不同任务的效益值矩阵q；第三步：通过判断机器人是否满足分配条件优化多机器人系统；第四步：对所述效益值矩阵进行简化处理；第五步：根据每个任务所需机器人的数量对效益值矩阵进行变形；第六步：对任务进行预分配，获得初始分配矩阵t，并进一步简化效益值矩阵；第七步：利用匈牙利算法处理步骤6简化后的效益值矩阵进行任务分配，获得最终的分配矩阵t，完成任务分配。该方法存在的不足是，由于该方法仅针对结构化环境添加限制性条件下实现多机器人任务分配，无法解决如救援等非结构化环境下的多机器人任务分配问题。
4.西安工程大学在其申请的专利文献“一种基于任务分配协调策略与粒子群算法的任务分配方法”(申请号：201910980023.6申请日：2019.10.15申请公布号：cn 110717684a)中公开了一种基于任务分配协调策略与粒子群算法的任务分配方法。该方法的具体步骤是，第一步：利用粒子群算法优化分配半径，得到初始分配结果；第二步：运用协调策略对初始分配结果进行调整，完成第一次分配；第三步：重复第一步至第二步，对未分配任务进行再次分配，直至任务完全分配。该方法存在的不足是，面对大规模任务和机器人数量时，利用粒子群算法寻优易陷入局部收敛，导致任务分配效率受限，难以进行扩展。


技术实现要素：

5.本发明的目的是针对上述现有技术的不足，提出一种基于混沌自适应蜣螂优化算法的多机器人任务分配方法，用于解决多机器人任务分配方法中存在的未考虑时间窗约束、可扩展性差和分配低效的问题。
6.实现本发明目的的技术思路是：本发明将多机器人任务分配问题建模转化为一个组合优化问题。考虑将行程代价、时间代价和任务完成收益作为评价指标，把任务分配约束、资源种类约束、时间窗约束和载荷约束作为约束条件，引入任务时间衰减特性，建立了符合救援等场景下，具有时限性要求的多机器人任务分配模型，克服了现有技术中无法解决救援等非结构化环境下的多机器人任务分配问题；本发明引入蜣螂优化算法解决多机器人任务分配问题，蜣螂优化算法可以进行并行化处理，即同时搜索多个可能的解决方案。同时，蜣螂优化算法具有自适应搜索的特点，它可以根据问题的复杂度和规模进行调整和优化。在面对大规模任务和机器人数量时，算法可以自动调整搜索策略，以适应不同规模数量的任务和机器人，克服了现有技术中可扩展性差的问题；本发明引入了混沌映射、自适应t分布变异和动态选择概率算子，提高了算法的收敛速度和跳出局部最优解的能力，克服了现有技术中分配低效的问题。
7.本发明的步骤包括如下：
8.步骤1，建立满足约束条件的待优化的多机器人任务分配目标函数：
9.步骤1.1，分别构建约束条件中的任务约束条件，资源约束条件，时间窗约束条件，载荷约束条件；
10.步骤1.2，建立待优化的多机器人任务分配目标函数如下：
[0011][0012]
其中，f表示多机器人任务分配目标函数，nv表示机器人的总数，i表示机器人的序号，n
t
表示任务的总数，j表示任务的序号，cost(vi,tj)表示第i个机器人vi执行第j个任务tj的行程代价函数，re(vi,tj)表示在第i个机器人vi执行第j个任务tj时第j个任务tj的价值随时间衰减的收益函数，timef表示所有机器人完成任务的时间代价函数，w1，w2，w3均为权重系数，表示上述各项函数的重要性，w1，w2，w3取值范围均为[0,1]，且满足w1+w2+w3＝1；
[0013]
步骤2，将最大迭代次数和蜣螂的种群数输入到蜣螂优化算法；
[0014]
步骤3，利用sine混沌映射蜣螂种群中每个蜣螂的位置；
[0015]
步骤4，将多机器人任务分配目标函数作为适应度值函数计算蜣螂种群中每个蜣螂的适应度值，将各蜣螂的适应度值中最小值作为蜣螂种群的全局极值，将同个蜣螂的不同迭代次数中的最小适应度值作为个体极值，比较各蜣螂的适应度值大小，得到蜣螂种群全局极值，比较同蜣螂不同迭代次数的适应度值大小，得到个体极值，保存当前迭代时的个体极值和全局极值；
[0016]
步骤5，将蜣螂种群按照6:6:7:11的比例分为滚球、繁殖、觅食和偷窃四个子群，利用自适应t分布变异算子和动态选择概率p算子，更新每个子群中蜣螂的位置；
[0017]
步骤6，判断是否达到最大迭代次数，若是，将全局极值对应的蜣螂种群中蜣螂的位置作为最佳位置后执行步骤7；否则，执行步骤3；
[0018]
步骤7，将蜣螂最佳位置作为多机器人任务分配结果。
[0019]
本发明与现有技术相比具有以下优点：
[0020]
第一，由于本发明在多机器人任务分配问题建模过程中考虑了时间窗约束等条件，引入任务时间衰减特性，克服了现有技术在处理多机器人任务分配问题时，无法解决救援等非结构化环境下的时限性问题，使得本发明利用所建立的多机器人任务分配问题模型，在解决多机器人任务分配问题时涵盖应用场景更广，通用性和推广性更强。
[0021]
第二，由于本发明引入蜣螂优化算法解决多机器人任务分配问题，克服了现有技术在面对大规模任务和机器人数量时，难以进行扩展的问题，使得本发明具有并行性和自适应性的特点，在面对大规模任务和机器人数量时，算法可以多种群同时搜索和自动调整搜索策略，以适应不同规模数量的任务和机器人，有助于提升算法的可扩展性。
[0022]
第三，由于本发明在蜣螂优化算法中引入sine混沌映射、自适应t分布变异和动态选择概率p算子，克服了现有技术在处理多机器人任务分配问题时，多机器人任务分配低效的问题，使得本发明在选择最优任务分配方案时，具有更快的收敛速度和跳出局部收敛的能力，有助于减少多机器人任务分配的时间。
附图说明
[0023]
图1为本发明实施例场景示意图；
[0024]
图2为本发明的流程图；
[0025]
图3为本发明实施例任务分配结果示意图；
[0026]
图4为本发明实施例最优适应度值迭代示意图；
[0027]
图5为本发明仿真实验1得到的各算法最优适应度值迭代示意图；
[0028]
图6为本发明仿真实验2不同规模场景下各算法的最优适应度值、平均适应度值对比示意图。
具体实施方式
[0029]
下面结合附图和实施例，对本发明做进一步的详细描述。
[0030]
参照图1，对本发明实施例的实现场景做进一步的描述。
[0031]
本发明实施例是在一个机器人数量小于任务数量的救援场景下，由4个异构机器人v1～v4参与救援12个目标任务t1～t
12
，机器人和任务初始信息分别如表1和表2所示。表1所述的初始信息包括机器人的初始位置信息和相关约束条件，表2所述初始信息包括任务的初始位置信息、任务价值信息和相关约束条件。图2中数字1-12表示12个对应任务的序号，12个五角星代表任务的位置，圆圈表示任务所需类型的3种资源(水、药物和衣物)。如任务6有大小不同的三个圆圈，表示任务6需要3种资源。图中c1＝111，表示机器人1可提供三种资源，1代表携带此类型资源，0代表不携带，具体可参考表1。
[0032]
表1机器人初始信息一览表
[0033][0034]
表2任务初始信息一览表
[0035][0036]
参照图2，对本发明实施例的实现步骤做进一步的描述。
[0037]
步骤1，建立满足约束条件的待优化的多机器人任务分配目标函数。
[0038]
步骤1.1，分别构建约束条件中的任务约束条件，资源约束条件，时间窗约束条件，载荷约束条件。
[0039]
所述任务约束条件如下：
[0040][0041]
其中，x
ij
表示任务约束参数，当x
ij
＝1时，代表第j个任务tj被第i个机器人vi执行，当x
ij
＝0时，代表第j个任务tj未被第i个机器人vi执行。
[0042]
由于各异构机器人携带不同的资源，不同的目标任务也有不同的资源需求，携带对应资源的机器人才能满足相应目标任务需求。
[0043]
所述资源约束条件如下：
[0044][0045]
其中，svi表示第i个机器人携带的资源种类，stj表示第j个目标任务的资源种类需求，∩为交集操作，表示空集。
[0046]
在本发明实施例中机器人携带资源种类详见表1，任务资源需求种类详见表2。
[0047]
由于目标任务要求在时间窗内完成故设定时间窗约束条件如下：
[0048][0049]
其中，表示第j个目标任务的出现时间，t
ij
表示第i个机器人开始执行第j个目标任务的时间，aim_ddlj表示第j个目标任务的截止时间。
[0050]
本发明实施例中任务时间窗取值详见表2。
[0051]
由于机器人的载荷能力有限，每次执行任务过程只能执行有限个任务，因此被分配任务个数不能超过其能力上限。同时，为了提升执行任务过程中机器人的利用率，保证完成任务的时间满足最小化，每个机器人至少执行一个任务，步骤1.1所述载荷约束条件如下：
[0052][0053]
其中，p
imax
表示第i个机器人可以执行目标任务的最多个数。本发明实施例中p
imax
取值详见表1。
[0054]
步骤1.2，建立待优化的多机器人任务分配目标函数如下：
[0055][0056]
其中，f表示多机器人任务分配目标函数，nv表示机器人的总数，i表示机器人的序号，n
t
表示任务的总数，j表示任务的序号，cost(vi,tj)表示第i个机器人vi执行第j个任务tj的行程代价函数，re(vi,tj)表示在第i个机器人vi执行第j个任务tj时第j个任务tj的价值随时间衰减的收益函数，timef表示所有机器人完成任务的时间代价函数，w1，w2，w3均为权重系数，表示上述各项函数的重要性，w1，w2，w3取值范围均为[0,1]，且满足w1+w2+w3＝1。
[0057]
所述的行程代价函数如下：
[0058][0059]
其中，dis{
·
}表示取欧氏距离操作，xi表示第i个机器人的出发位置，本发明实施例中4个机器人的出发位置均为(0.5,0.5)，t
i1
表示第i个机器人vi任务序列中第一个待执行任务，|
·
|表示取绝对值操作，mo表示任务序列中待执行任务的总数，c表示第i个机器人vi任务序列中待执行任务的序号。
[0060]
由于在本发明实施例中考虑的是二维平面，因此坐标值是基于二维平面设定的，机器人和任务位置坐标取值分别详见表1和表2，上述行程代价函数可扩展到三维平面等空间场景。
[0061]
所述的收益函数如下：
[0062][0063]
其中，p
ij
表示第i个机器人vi执行第j个任务tj的能力价值系数，p
ij
取值范围为(0,1)，x
ij
表示任务约束参数，当x
ij
＝1时，代表第j个任务tj被第i个机器人vi执行，当x
ij
＝0时，代表第j个任务tj未被第i个机器人vi执行，value(tj)表示第j个任务tj的价值，e
(
·
)
表示以自然常数e为底的指数操作，μj表示第j个任务tj的时间衰减特性影响因子，表示第j个任务tj的出现时间，在本发明实施例中能力价值系数p
ij
取值均为0.5，任务价值value(tj)的取值详见表2，μj＝5e-4
。
[0064]
所述的时间代价函数如下：
[0065][0066]
其中，表示第k个任务tk的完成时间，表示第l个任务t
l
的开始执行时间。
[0067]
步骤2，将最大迭代次数30和蜣螂的种群数60输入到蜣螂优化算法。
[0068]
步骤3，利用sine混沌映射蜣螂种群中每个蜣螂的位置，在蜣螂优化算法中，蜣螂的位置和解空间都是连续的，然而，在多机器人任务分配问题中，任务分配解是离散值。在多机器人任务分配问题中，机器人数量为nv，目标任务数量为n
t
，所以在蜣螂优化算法中蜣螂位置维数为n
t
，每一个蜣螂对应一个潜在目标任务分配解。因此本发明基于蜣螂优化算法设计了蜣螂的编解码过程，采用实数编码方式，令第n个蜣螂位置xn是n
t
维实数向量，并设定上下限[1,nv+1)，保证第n个蜣螂位置xn在其范围内更新。由于编码过程中的xn是n
t
维实数向量，xn存在整数部分和小数部分，因此设计解码过程如下：令xn(in)为xn的整数部分，xn(de)为xn的小数部分，例：8.75(in)＝8，8.75(de)＝0.75。xn(inj)＝i可表示一个任务分配潜在解，即把第j个任务tj分配给第i个机器人vi。在任务分配中，可能出现xn′
(ins)＝
···
＝xn(inj)，即多个蜣螂位置的整数部分相等，因此规定如下：首先通过位置向量x的整数部分x(in)确定有哪些任务将分配给同一个机器人，然后通过位置向量x的小数部分x(de)进行大小排序，小数部分越大，即同一机器人先执行该任务。
[0069]
蜣螂位置指的是本发明中一个任务分配解，每个蜣螂的位置以一个向量表示，在本实施例中，即nv＝4，n
t
＝12，即第n个蜣螂位置xn是在[1,5)内更新的十二维实数向量。向量中的每一个元素表示一个任务，向量中元素的整数部分表示分配到的机器人的编号，小数部分表示分配到的机器人的执行顺序。利用sine混沌映射每个蜣螂的位置是由下式完成的：
[0070][0071]
其中，x
n,s
表示第n个蜣螂经过sine混沌映射后的位置，s表示进行混沌映射操作，n表示蜣螂的序号，表示映射系数，π表示圆周率，xn表示第n个蜣螂混沌映射前的位置。
[0072]
步骤4，将多机器人任务分配目标函数作为适应度值函数计算蜣螂种群中每个蜣螂的适应度值，将各蜣螂的适应度值中最小值作为蜣螂种群的全局极值，将同个蜣螂的不同迭代次数中的最小适应度值作为个体极值，比较各蜣螂的适应度值大小，得到蜣螂种群全局极值，比较同蜣螂不同迭代次数的适应度值大小，得到个体极值，保存当前迭代时的个体极值和全局极值。
[0073]
步骤5，将蜣螂种群按照6:6:7:11的比例分为滚球、繁殖、觅食和偷窃四个子群，利用自适应t分布变异算子和动态选择概率p算子，更新每个子群中蜣螂的位置。
[0074]
蜣螂位置更新是由下式完成的。
[0075]
使用动态选择概率p算子，p算子定义如下：
[0076]
p＝q
1-q2×
(t
max-iter)/t
max
[0077]
其中，q1表示可影响动态选择概率p算子上界的系数，q2表示可影响动态选择概率p算子下界的系数。
[0078]
本发明实施例中q1＝0.5，q2＝0.2。
[0079]
生成(0,1)范围内随机数rand，若rand》p，则对滚球、繁殖、觅食和偷窃四个子群蜣螂位置执行自适应t分布变异操作进行扰动；否则，不执行自适应t分布变异操作，四个子群位置更新公式如下：
[0080]
滚球蜣螂子群位置更新公式如下：
[0081]
不执行自适应t分布变异操作:
[0082]
执行自适应t分布变异操作:
[0083]
其中，表示第n只蜣螂在t+1次迭代时的位置，t表示迭代次数，α表示自然系数取值为1或-1，k表示缺陷系数，k∈(0,0.2]，b表示光强系数，b∈(0,1)，xw表示全局最差位置，δx表示模拟光强变化，表示第n只蜣螂执行自适应t分布变异扰动操作后在t+1次迭代时的滚球蜣螂位置，t
′
表示执行自适应t分布变异操作，t(iter)表示以算法迭代次数
为参数自由度的t分布，iter表示当前迭代次数。
[0084]
跳舞蜣螂子群位置更新公式如下：
[0085]
不执行自适应t分布变异操作:
[0086]
执行自适应t分布变异操作:
[0087]
lb
*
＝max(x
*
×
(1-r),lb)
[0088]
ub
*
＝min(x
*
×
(1+r),ub)
[0089]
r＝1-t/t
max
[0090]
其中，θ表示角度，θ∈[0,180
°
]。
[0091]
繁殖蜣螂子群位置更新公式如下：
[0092]
不执行自适应t分布变异操作:
[0093]
执行自适应t分布变异操作:
[0094]
lb
*
＝max(x
*
×
(1-r),lb)
[0095]
ub
*
＝min(x
*
×
(1+r),ub)
[0096]
r＝1-t/t
max
[0097]
其中，x
*
表示当前局部最优位置，lb
*
和ub
*
分别表示蜣螂产卵区域的下界和上界，t
max
表示最大迭代次数，lb和ub表示优化问题的下界和上界，b1和b2表示大小为1
×nt
的两个独立随机向量。
[0098]
觅食蜣螂位置更新公式如下：
[0099]
不执行自适应t分布变异操作:
[0100]
执行自适应t分布变异操作:
[0101]
lbb＝max(xb×
(1-r),lb)
[0102]
ubb＝min(xb×
(1+r),ub)
[0103]
其中，xb表示全局最优位置，lbb和ubb分别表示蜣螂觅食区域的下界和上界，c1表示服从正态分布的随机数，c2表示随机数，c2∈(0,1)。
[0104]
小偷蜣螂子群位置更新公式如下：
[0105]
不执行自适应t分布变异操作:
[0106]
执行自适应t分布变异操作:
[0107]
其中，g表示服从正态分布的1
×nt
的随机向量，s表示一个常数。
[0108]
步骤6，判断是否达到最大迭代次数，若是，得到蜣螂最佳位置执行步骤7；否则，执行步骤3，最佳位置为全局极值对应的蜣螂种群中蜣螂的位置。
[0109]
步骤7，将蜣螂最佳位置作为多机器人任务分配结果。
[0110]
图3为本发明实施例中蜣螂最优适应度值迭代示意图，横坐标表示位置坐标的第一个无量纲值，纵坐标表示位置坐标的第二个无量纲值。本发明实施例中达到最大迭代时最优适应度值对应的蜣螂最佳位置为通过步骤3可得多机器任务分配结果，表4为本发明实施例中多机器任务分配结果，表4中数字表示任务序号，如《
12,2,10》表示机器人v1分配到了任务t
12
，t2和t
10
，其中表中的排序表示执行任务的顺序，机器人v1先执行任务t
12
，在执行任务t2，最后执行任务t
10
。图4为本发明实施例中结合表3中的任务分配结果示意图。
[0111]
表3任务分配结果
[0112][0113]
本发明的效果可以通过下面的仿真得到进一步证明。
[0114]
1.仿真实验条件。
[0115]
本发明的仿真实验的软件平台为：windows 11操作系统和matlab r2021b。
[0116]
本发明的仿真实验的硬件平台为：处理器为intel i7 9750h cpu，主频为2.6ghz，内存16gb的一台计算机。
[0117]
2.仿真内容与结果分析。
[0118]
本发明的仿真实验有两个。
[0119]
本发明仿真实验1是对一救援场景下采用本发明方法及对比方法进行多机器人任务分配的仿真对比实验。
[0120]
本发明的仿真实验1考虑在一个救援场景下，该场景下有12个需要救援的目标任务t1～t
12
，4个异构机器人v1～v4参与救援。任务和机器人初始信息如表4和表5所示。表4所述的初始信息包括机器人的初始位置信息和相关约束条件，表5所述初始信息包括任务的初始位置信息、任务价值信息和相关约束条件。为了简化实验场景，假设每个机器人均匀速前行。给定初始条件，本发明仿真实验1中所采用的5种算法的最大迭代次数均为t
max
＝500，同时，为了均衡考虑任务收益、行程代价和时间代价的影响，令w1＝w2＝w3，给定种群数60。
[0121]
表4仿真实验1机器人初始信息一览表
[0122][0123]
表5仿真实验1任务初始信息一览表
[0124][0125]
本发明仿真实验1是采用本发明的方法自适应混沌蜣螂优化算法(t-sdbo)、三个现有技术：粒子群算法(pso)、麻雀搜索算法(ssa)和蜣螂优化算法(dbo)，现有技术的改进
蜣螂优化算法(sdbo)，分别得到500次迭代下的最优适应度值，再将得到的最优适应度值与迭代次数之间关系绘制成如图5中所示的五条曲线。
[0126]
在仿真实验1中，采用的三个现有技术和现有技术的一个改进方法是指：
[0127]
现有技术1是指，牛龙辉等人在其发表的论文“结合粒子群算法与任务分配协调策略的仓储多机器人任务分配”(西安工程大学学报，2020,34(06):73-79)中提出一种基于粒子群算法的多机器人任务分配方法。
[0128]
现有技术2是指，桂林理工大学在其申请的专利申请文献“一种面向异构多核处理器的混合式任务调度方法”(申请号：cn202011027749.7,申请公开号：cn112199172a)中提出的基于麻雀搜索算法的任务调度方法。
[0129]
现有技术3是指，xue等人在其发表的论文“dung beetle optimizer:a new meta-heuristic algorithm for global optimization”(the journal of supercomputing,2023,79(7):7305-7336)中提出的蜣螂优化算法。
[0130]
现有方法的改进方法是指在现有技术3的基础上，在种群初始化中引入了sine混沌映射。
[0131]
本发明仿真实验2是为了综合验证本发明在解决多机器人任务分配问题上的能力进行的仿真。
[0132]
本发明的仿真实验2所使用的实验数据集为随机生成的多机器人任务分配问题数据集，其中包括目标任务的位置、所需资源、任务时间窗和任务价值以及机器人的提供资源、能力系数。
[0133]
本发明仿真实验2所采用本发明的方法和三个现有技术，分别得到不同规模下的多机器人任务分配的最优适应度值和平均适应度值，再将得到的最优适应度值和平均适应度值与不同规模场景之间的关系绘制成如图6中所示的四条曲线，其中，图6(a)是各算法不同规模下的多机器人任务分配的最优适应度值示意图，图6(b)是各算法不同规模下的多机器人任务分配的平均适应度值示意图。
[0134]
在仿真实验2中，采用的三个现有技术与仿真实验1相同。
[0135]
下面结合图5和图6对本发明的效果做进一步的描述。
[0136]
图5中横坐标表示算法迭代次数，单位为次，纵坐标表示适应度值。图5中浅蓝色实线的曲线表示本发明的最优适应度值与迭代次数之间的关系曲线，绿色点画线的曲线表示现有技术1的最优适应度值与迭代次数之间的关系曲线，蓝色点画线的曲线表示现有技术2的最优适应度值与迭代次数之间的关系曲线，黑色点画线的曲线表示现有技术3的最优适应度值与迭代次数之间的关系曲线，带圆圈的红色实线的曲线表示现有技术3的改进方法的最优适应度值与迭代次数之间的关系曲线。
[0137]
从图5中可看出：pso算法在局部搜索和全局优化能力方面，所得结果与其他4种算法存在一定差距；ssa算法在前期优化收敛速度较快，但很快陷入了局部收敛；可以看出dbo算法在为改进之前也能取得较好的优化效果，但是易陷入局部收敛；sdbo算法相较dbo取得了更好的优化效果，证明了sine混沌映射的有效性。本发明提出的t-sdbo算法无论是从优化结果、前期收敛速度还是跳出局部收敛的能力，都比其它4种算法表现出更佳的性能，表明t-sdbo在解决多机器人任务分配问题时的可行性。分别运行5种算法的程序各10次，平均适应度值、最优适应度值和求解时间如表6所示。
[0138]
从表6的结果中可以看出t-sdbo算法的平均适应度值4.3556和最优适应度值4.3213均比其他4种算法性能更好。
[0139]
表6不同算法平均适应度值和最优适应度值比较表
[0140][0141]
图6(a)中的横坐标表示不同规模的场景，如横坐标的mrta0310表示3个机器人去执行10个任务的场景。纵坐标表示适应度最小值。其中，红色带星号实线的折线表示本发明的最优适应度值与不同规模场景的关系折线，绿色带圆圈实线的折线表示现有技术1的最优适应度值与不同规模场景的关系折线，蓝色带加号实线的折线表示现有技术2的最优适应度值与不同规模场景的关系折线，浅蓝色带乘号实线表示现有技术3的最优适应度值与不同规模场景的关系折线。
[0142]
图6(b)中横坐标表示不同规模的场景，纵坐标表示适应度平均值。其中，红色带星号实线的折线表示本发明的平均适应度值与不同规模场景的关系折线，绿色带圆圈实线的折线表示现有技术1的平均适应度值与不同规模场景的关系折线，蓝色带加号实线的折线表示现有技术2的平均适应度值与不同规模场景的关系折线，浅蓝色带乘号实线的折线表示现有技术3的平均适应度值与不同规模场景的关系折线。
[0143]
从图6中可以看出：5个实验场景下，在解空间较小时，各算法性能表现差异较小，但随着任务数量和机器人数量的增加，各算法的差异性也出现显著差距，但本发明提出的t-sdbo算法在不同问题规模下均取得了最优效果。

技术特征：
1.一种基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，建立满足约束条件的待优化的多机器人任务分配目标函数，在蜣螂优化算法中利用sine混沌映射蜣螂种群中每个蜣螂的位置，利用自适应t分布变异算子和动态选择概率p算子，更新每个子群中蜣螂的位置；该分配方法的步骤包括如下：步骤1，建立满足约束条件的待优化的多机器人任务分配目标函数：步骤1.1，分别构建约束条件中的任务约束条件，资源约束条件，时间窗约束条件，载荷约束条件；步骤1.2，建立待优化的多机器人任务分配目标函数如下：其中，f表示多机器人任务分配目标函数，n
v
表示机器人的总数，i表示机器人的序号，n
t
表示任务的总数，j表示任务的序号，cost(v
i
,t
j
)表示第i个机器人v
i
执行第j个任务t
j
的行程代价函数，re(v
i
,t
j
)表示在第i个机器人v
i
执行第j个任务t
j
时第j个任务t
j
的价值随时间衰减的收益函数，time
f
表示所有机器人完成任务的时间代价函数，w1，w2，w3均为权重系数，表示上述各项函数的重要性，w1，w2，w3取值范围均为[0,1]，且满足w1+w2+w3＝1；步骤2，将最大迭代次数和蜣螂的种群数输入到蜣螂优化算法；步骤3，利用sine混沌映射蜣螂种群中每个蜣螂的位置；步骤4，将多机器人任务分配目标函数作为适应度值函数计算蜣螂种群中每个蜣螂的适应度值，将各蜣螂的适应度值中最小值作为蜣螂种群的全局极值，将同个蜣螂的不同迭代次数中的最小适应度值作为个体极值，比较各蜣螂的适应度值大小，得到蜣螂种群全局极值，比较同蜣螂不同迭代次数的适应度值大小，得到个体极值，保存当前迭代时的个体极值和全局极值；步骤5，将蜣螂种群按照6:6:7:11的比例分为滚球、繁殖、觅食和偷窃四个子群，利用自适应t分布变异算子和动态选择概率p算子，更新每个子群中蜣螂的位置；步骤6，判断是否达到最大迭代次数，若是，将全局极值对应的蜣螂种群中蜣螂的位置作为最佳位置后执行步骤7；否则，执行步骤3；步骤7，将蜣螂最佳位置作为多机器人任务分配结果。2.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.1中所述的任务约束条件如下：其中，x
ij
表示任务约束参数，当x
ij
＝1时，代表第j个任务t
j
被第i个机器人v
i
执行，当x
ij
＝0时，代表第j个任务t
j
未被第i个机器人v
i
执行。3.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.1中所述的资源约束条件如下：其中，sv
i
表示第i个机器人携带的资源种类，st
j
表示第j个任务的资源种类需求，∩为
交集操作，表示空集。4.根据权利要求2所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.1中所述的时间窗约束条件如下：其中，表示第j个任务的出现时间，t
ij
表示第i个机器人开始执行第j个任务的时间，aim_ddl
j
表示第j个任务的截止时间。5.根据权利要求2所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.1中所述的载荷约束条件如下：其中，p
imax
表示第i个机器人性能系数确定的执行任务的总数。6.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.2中所述的行程代价函数如下：其中，dis{
·
}表示取欧氏距离操作，x
i
表示第i个机器人的出发位置，t
i1
表示第i个机器人v
i
任务序列中第一个待执行任务，|
·
|表示取绝对值操作，m
o
表示任务序列中待执行任务的总数，c表示第i个机器人v
i
任务序列中待执行任务的序号。7.根据权利要求4所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.2中所述的收益函数如下：其中，p
ij
表示第i个机器人v
i
执行第j个任务t
j
的能力价值系数，p
ij
取值范围为(0,1)，value(t
j
)表示第j个任务t
j
的价值，e
()
表示以自然常数e为底的指数操作，μ
j
表示第j个任务t
j
的时间衰减特性影响因子。8.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤1.2中所述的时间代价函数如下：其中，表示第k个任务t
k
的完成时间，表示第l个任务t
l
的开始执行时间。9.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤3中所述的利用sine混沌映射每个蜣螂的位置是由下式完成的：其中，x
n,s
表示第n个蜣螂经过sine混沌映射后的位置，s表示进行混沌映射操作，n表示蜣螂的序号，表示映射系数，π表示圆周率，x
n
表示第n个蜣螂混沌映射前的位置。10.根据权利要求1所述的基于混沌自适应蜣螂优化算法的多机器人任务分配方法，其特征在于，步骤5中所述的蜣螂位置更新是由下式完成的：
引入动态选择概率p算子，p算子定义如下：p＝q
1-q2×
(t
max-iter)/t
max
其中，q1表示可影响动态选择概率p算子上界的系数，q2表示可影响动态选择概率p算子下界的系数；生成(0,1)范围内随机数rand，若rand>p，则对滚球、繁殖、觅食和偷窃四个子群蜣螂位置执行自适应t分布变异操作进行扰动；否则，不执行自适应t分布变异操作，四个子群位置更新公式如下：滚球蜣螂子群位置更新公式如下：不执行自适应t分布变异操作:执行自适应t分布变异操作:其中，表示第n只蜣螂在t+1次迭代时的位置，t表示迭代次数，α表示自然系数取值为1或-1，k表示缺陷系数，k∈(0,0.2]，b表示光强系数，b∈(0,1)，x
w
表示全局最差位置，δx表示模拟光强变化，表示自适应t分布变异扰动后在t+1次迭代时的滚球蜣螂位置，t
′
表示执行自适应t分布变异操作，t(iter)表示以算法迭代次数为参数自由度的t分布，iter表示当前迭代次数；跳舞蜣螂子群位置更新公式如下：不执行自适应t分布变异操作:执行自适应t分布变异操作:lb
*
＝max(x
*
×
(1-r),lb)ub
*
＝min(x
*
×
(1+r),ub)r＝1-t/t
max
其中，θ表示角度，θ∈[0,180
°
]；繁殖蜣螂子群位置更新公式如下：不执行自适应t分布变异操作:执行自适应t分布变异操作:其中，x
*
表示当前局部最优位置，lb
*
和ub
*
分别表示蜣螂产卵区域的下界和上界，t
max
表示最大迭代次数，lb和ub表示优化问题的下界和上界，b1和b2表示大小为1
×
n
t
的两个独立随机向量；觅食蜣螂位置更新公式如下：不执行自适应t分布变异操作:执行自适应t分布变异操作:lb
b
＝max(x
b
×
(1-r),lb)ub
b
＝min(x
b
×
(1+r),ub)其中，x
b
表示全局最优位置，lb
b
和ub
b
分别表示蜣螂觅食区域的下界和上界，c1表示服从正态分布的随机数，c2表示随机数，c2∈(0,1)；小偷蜣螂子群位置更新公式如下：
不执行自适应t分布变异操作:执行自适应t分布变异操作:其中，g表示服从正态分布的1
×
n
t
的随机向量，s表示一个常数。

技术总结
本发明公开了一种基于混沌自适应蜣螂优化算法的多机器人任务分配方法，主要解决多机器人任务分配方法中存在的未考虑时间窗约束、可扩展性差和分配低效的问题。本发明实现步骤为：建立满足约束条件的待优化的多机器人任务分配目标函数；初始化算法参数；初始化蜣螂种群中每个蜣螂的位置；计算各个蜣螂适应度值；更新各个蜣螂的位置；达到最大迭代次数时将蜣螂最佳位置作为多机器人任务分配结果作为输出。本发明通过混沌自适应蜣螂优化算法解决多机器人任务分配问题，提高了多机器人任务分配的质量和效率，有效地解决了多机器人任务分配方法中存在的上述问题。方法中存在的上述问题。方法中存在的上述问题。


技术研发人员：李团结 李显涛 宁宇铭
受保护的技术使用者：西安电子科技大学
技术研发日：2023.07.04
技术公布日：2023/9/20