异构多机器人系统中基于个体能力的任务分配算法

摘要

本发明属于机器人研究领域，重点在于研究异构多机器人系统中的机器人个体能力模型。首先把多机器人系统中个体机器人的能力分为三种：一种是时不变的A类物理能力，第二种是随着时间衰减的B类能力，第三类是与机器人个体意愿因素相关的C类能力。分别评估这三种能力，最后形成个体机器人的能力评估模型及方法，并讨论了影响每类能力的因素，特别是对于变化较为复杂的C类能力，通过对比试验得出参数变化对C类能力的影响。该能力模型解决了异构多机器人系统中机器人能力复杂多变难于评估的问题，同时可以实时的评估个体机器人的能力，在此任务模型的基础上生成任务列表，基于任务列表，提出了任务分配方案。

说明书

技术领域

本发明属于机器人研究领域，提出了一种适用于异构多机器人系 统的基于机器人个体差异分析的机器人能力列表的求解方法,并给出 基于该能力列表的任务分配算法。

背景技术

为了让多机器人系统向着人们期望的方向发展，R.A.Brooks 提出了行为主义的思想；不再将为机器人系统制定精细而复杂的控制 算法作为努力目标，而是模拟自然界中的实际情况，尝试着为机器人 配备不同的基本行为，再赋予其组合基本行为的能力，从而来实现比 较高级的能力。在行为主义思想的基础上，多机器人系统的研究得到 了很大的发展。然而，多机器人系统内部的关系仍然是极其复杂的， 若处理不当，不仅不能发挥预期的功能，很有可能还使得单个机器人 的性能也受到影响。

放眼生物界，多姿多彩、生机勃勃。它最主要的特征便是多样性， 即个体差异，也就是说存在着多种多样而不是单一简单的种群。同理， 在一个群体内部，个体特征也是非常明显而丰富的。这使我们想到， 在模拟生物系统而产生的多机器人系统中，个体差异也应当给予充分 重视，这很可能是系统得以不断完善和发展的基础。因此，我们考虑 将个性引入到多机器人系统中，赋予不同的机器人不同的个性要素， 并且允许它们通过对工作效果的评估和在环境中的尝试总结经验，不 断的调整自身所具有的个体要素，以达到不断调整自身策略以更好的 适应环境以及工作伙伴特性的要求，根据任务的需要和其他个体相配 合，从而更多的发挥自身以及系统整体的潜力。

任务分配是多机器人系统研究中的核心问题之一，学者们分别从 多个方面做了任务分配模型的研究。许多学者还从自然生物的行为中 获得灵感将MRS中的单个机器人看作是生物群体中的一个对象，于是 引入了社会学和经济管理学的原理来研究，如Gerkey提出了基于市 场经济的任务分配方法等。如果各个机器人争着完成一件任务，为了 有效的处理这种竞争冲突，就需要有较为公平、通用的衡量标准来评 估机器人的能力，从而使得任务能够更加高效、高质量的完成。

发明内容

本发明的目的是解决异构机器人系统中机器人个体的能力评估 问题，具体方法如下：

（1）异构机器人能力描述

一般情况下，把机器人的能力分为三种：A类能力是与生俱来的 不会变动的基本属性，包括：听觉、视觉和运动、通信带宽；B类能 力是随时间递减消耗的能力，或者说是机器人可供消耗的能量，包括： 计算速度、电力储备和机械性能；C类能力是A、B类能力之外的其 他能力，由友好程度和协作意愿、鲁棒性等拟人化情感因素随机组成， 体现机器人主观工作能力。每类能力中的能力属性又分为优、良、中、 差四个级别，表示能力的强弱。每类能力可以根据实际情况继续添加 能力属性。

对于每类基本能力，可以定义其能力集合如下：

S={s_i|i＝1,2,...,N}

其中N表示每类能力中能力属性的个数。用P_i表示第i种能力的 权重，或者说贡献值。

则机器人能力的概率空间模型可以表示为

$\left(\begin{array}{c}S\\ P\end{array}\right)=\left(\begin{array}{cccc}{s}_1& s_2& ...& s_N\\ P_1& P_2& ...& P_N\end{array}\right)$

（2）机器人个体能力评估

机器人的能力可以表示为：

ΔE=(αE₁+βE₂)(α+β)/(α+β+γ)+γΨ

=(αE₁+βE₂)(α+β)+γΨ

其中，E₁是与生俱来的基本硬件能力，不会随着时间的变化而改 变的A类能力；E₂是随着时间而递减的B类能力，Ψ表示机器人C类 能力的需求权重矩阵之间的匹配度。不同的参数得到不同个性特点的 机器人。假设三个参数已经归一化，即：

α+β+γ=1

该参数系数根据任务的不同而不同。每次任务来临时，根据任务 的对各项能力需求的权重，确定三个参数，然后计算多机器人系统中 各机器人的能力，择优选择能力较高的机器人来执行任务。下面将讲 解每类能力的具体求解思路。

1）A类能力评估

对于A类能力，其表示比较简单

$E_i=\underset{i=1}{\overset{N}{\Sigma }}{P}_i\times {\phi }_i$

其中P_i为当前任务下，A类能力中属性能力i的权重，φ_i为属性 能力i的等级，分为优良中差四个等级，分别对应1、3/4、1/2、0 四个级别值，即认为机器人不具备该能力时，其能力级别为差。

2）B类能力评估

B能力是随着时间衰减的能力值，在没有负载的情况下，即没有 被分配任务的情况下，其能力呈现自然衰减函数。

设为个体能力i初始能力值，则t+1时刻的个体能力可以表示 为

φ^(t+1)=φ^(t)·A

其中A叫做转移矩阵，同时也可以称为衰减矩阵，意味着机器人 的能力随着时间的推移慢慢减小，即能量被消耗。

在有负载的情况下，其转移矩阵变为B，B也是一个衰减函数

|B|<|A|<1

即它的衰减程度比A大。

此时个体能力可以表示为：

φ^(t+1)=φ^(t)·B

B类能力可以表示为

$E_2=\underset{i=0}{\overset{N}{\Sigma }}{P}_i\times {\phi }_i^{\left(t\right)}$

3）C类能力评估

C类能力是最能体现机器人个体意愿的能力，通过各能力属性的 随机组合来形成个体的差异。其中各能力属性的概率或者说权重满足

其中0≤P_i≤1(i=1,2,...N)

在任意时刻，各能力的概率之和都为1，这说明各能力状态是相 互制约的，一种能力强度的增加，必然会使其他能力状态强度减小。

对于每一个机器人，在任务来临时刻t，都有一个C类能力权重， 表示如下：

${\bar{P}}^t=[p_1^t,p_2^t,...,p_N^t]$

而对于每一个分解的任务i，都有一个C类能力需求权重，表示 如下：

${\bar{P}}_i=[p_1^i,p_2^i,...,p_N^i]$

定义两权重矩阵的匹配度如下：

$\psi =\underset{k=1}{\overset{N}{\Sigma }}\frac{p_k^t}{p_k^i}$

A.自发转移个体能力差异研究

在概率空间的基础上，把能力的变化过程看成一个随机过程，并 用马尔科夫链来描述能力状态自发转移过程。并假定总是向平静点转 移，即在没有任务负载的情况下，能力的转移趋向于各能力属性概率 平均分布的状态，即概率为1/N。相当于没有凸显的能力属性，即平 庸状态。

此时${\bar{P}}^t=\left(\begin{array}{cccc}{\bar{P}}_1^t& {\bar{P}}_2^t& ...& {\bar{P}}_N^t\end{array}\right)$表示在时刻t的能力的概率分布，t＝0 时为初始能力概率分布。

${\bar{P}}^{t+1}={\bar{P}}^t·A$

其中

${\bar{P}}^t=[p_1^t,p_2^t,...,p_N^t]$

$A={\left\{a_{\mathrm{ij}}\right\}}_{\mathrm{MxN}}=\left(\begin{array}{cccc}\frac{\theta {\pi }_1^{*}-(N-1)}{\theta {\pi }_1^{*}}& \frac{1}{\theta {\pi }_1^{*}}& ...& \frac{1}{\theta {\pi }_1^{*}}\\ \frac{1}{\theta {\pi }_2^{*}}& \frac{\theta {\pi }_2^{*}-(N-1)}{\theta {\pi }_2^{*}}& ...& \frac{1}{\theta {\pi }_2^{*}}\\ ...& ...& ...& ...\\ \frac{1}{\theta {\pi }_N^{*}}& \frac{1}{\theta {\pi }_N^{*}}& ...& \frac{\theta {\pi }_N^{*}-(N-1)}{\theta {\pi }_N^{*}}\end{array}\right)$

θ是待定参数，${\bar{\pi }}^{*}=\left(\begin{array}{cccc}{\pi }_1^{*}& {\pi }_2^{*}& ...& {\pi }_N^{*}\end{array}\right)$是极限概率。

能力状态自发转移过程，即个体的能力转移差异，取决于矩阵A， 因此，参数θ和的确定，是对个体差异研究的关键。

B.刺激转移个体能力差异研究

当机器人在t时刻接受任务时，将发生在刺激作用下的能力刺激 转移过程，此时的将作为能力刺激转移过程的出发点，称为能力转 移的初始概率分布，用π=[π₁ π₂...π_N]表示，这 时用隐马尔科夫模型来表示该能力转移过程，用建立五元组模型

$\lambda =(N,M,{\hat{\bar{P}}}^0,\hat{A},\hat{B})$

其中N是能力维度，即个数，M是刺激种类，默认为M＝N，是 初始能力概率分布向量，是状态转移概率矩阵，观测值矩阵为

$\hat{B}=\left(\begin{array}{c}{B}_{1·}\\ B_{2·}\\ ...\\ B_{N·}\end{array}\right)=\left(\begin{array}{cccc}a& b& ...& b\\ b& a& ...& b\\ ...& ...& ...& ...\\ b& b& ...& a\end{array}\right)$

$a=\frac{r}{N-1+r}$

$b=\frac{1}{N-1+r}$

r>1，r是可调参数。

根据HMM模型的五元组描述，得知能力状态转移过程中，个体的 能力差异，取决于矩阵和因此，参数r、θ和的确定， 是对个体差异研究的关键。

（2）异构机器人任务分配

当任务来临时，对于每个分任务，处于相应工作区域的异构机器 人会生成一个能力列表。对于任务，能生成一个能力列表，该能力列 表包含：任务，机器人，机器人在该任务下的能力，以及任务级别。 相应的，对于每个机器人，都能生成一个能力列表，该能力列表包含 机器人、任务、该任务条件下的能力以及是否有负载。按照任务优先 级的顺序，按照列表顺序，分配任务，即选取该任务的能力列表中排 在最前面的机器人，一般情况下，按照任务优先级安排任务，对于优 先级相同的多个任务的分配。

以<e_i，R_j，n，level_i，assigned_i>表示任务列表，其中e_i表示 第i个子任务，按照级别排列，同级别的任务顺序排列，n表示该任 务对应的机器人的能力列表顺序，如果n＝1，则对应的R_i表示对于任 务e_i具有最高能力的机器人，n越大表示对应的机器人执行该任务的 能力越小，level表示任务的级别，assigned＝true表示任务已经分 配，assigned＝false表示任务还未分配，assigned＝0表示待定； <R₁,e_k,m，load₁>表示单个机器人的能力列表，R₁表示第l个机器人， m表示机器人对应的子任务的能力列表顺序，如果m＝1，则执行对应 的e_k任务时，机器人R₁能力最强，m越大表示机器人执行对应任务的 能力越小，load₁表示机器人R₁是否被分配任务。

程序流程如下：

1）设定初始状态<e_i，R_j，n，level_i，assigned_i>，i＝1，level＝A；

2）令n＝1，assigned_i=false，如果<e_i，R_j，n，level_i，assigned_i> 为空，则转到7）；

3）读取<e_i，R_j，n，level_i，assigned_i>对应的机器人R_j，得出 j的值；

4）对于<R₁,e_k,m，load₁>，令l＝j，m＝1，读取对应的任务e_k，得 到k的值；

5）如果load₁=false，并且k＝i，则把任务e_i分配给机器人R_j， 令assigned_i=true，load₁=true;如果k不等于i，load₁=false,读 取<e_k，R_j，n，level_k>，得到level_k，若level_k=！level_i,则把e_i分 配给机器人R_j，令assigned_i=true，load₁=true；反之，令assigned_i=0； 如果load₁=true，令n＝n+1转向步骤3）；

6）判断level_i+1=level_i，如果是，则令p＝i，i＝i+1转向步骤2）， 如果不是，则读取<e_i1，R_j，n，level_i-1，0>,如果为空，则令i＝p+1， 转向步骤2），反之，则令i＝il，执行步骤3）4）5）

7）结束程序

本发明建立了一种机器人个体的能力模型，该模型可以模拟物理 世界中机器人能力的转移过程，实时评估机器人个体的能力，为机器 人系统的任务分配打下基础。

具体实施方式

假设以下场景：一个任务被分解成四个子任务：e₁,e₂,e₃,e₄，在 工作场景中存在四个机器人R_A,R_B,R_C,R_D，每个机器人都有执行各任 务的权利，环境因素设置如下：

表1任务环境描述

对应的任务的能力列表如下表所示：

表2任务的能力列表

从上面的列表可知，子任务e₁就有最高的级别，子任务e₁，e₂具有相同的级别。

同时可以得到机器人R_A对应的能力列表如下表所示，从表中可以 看出，子任务e₁对应的能力最高，且因为e₁具有最高的级别，这就 意味着有最高级别的子任务e₁应该分配给机器人R_A。

表3机器人R_A的能力列表

从机器人R_B的能力列表中可以看出，R_B在子任务e₃条件下具有最 高的能力，但是子任务e₂条件下，最高能力也属于R_B，最后，因为子 任务e₂，e₃拥有相同的级别，而R_B在任务e₃下具有更高的能力，所以 任务e₃被分配给R_B。

表4机器人R_B的能力列表

由于e₃被分配给机器人R_B，而机器人R_C是任务e₂的最佳选择， 在机器人R_C的能力列表中，在任务e₄条件下，机器人R_C有最高的能 力，但是任务e₂比e₄的级别高，所以机器人R_C应该被分配任务e₂.

表5机器人R_C的能力列表

最后，最低级别的任务e₄被分配给机器人R_D。运用前面介绍的任 务分配方法，最后的分配结果如下所示：

表6任务分配结果

这个例子包含了上面任务分配方法中提到的三种情况，同时该例 子证明了上述基于能力列表的任务分配方法能够保证具有最高能力 的机器人选择具有最高级别的任务，从而提高任务分配效率。