基于D-S证据理论的机器人功能模块粒度划分评价方法

摘要

基于D‑S证据理论的机器人功能模块粒度划分评价方法，属于机器人分散控制领域，该评价方法主要分四步完成：以智能服务机器人系统的各功能模块独立性为原则，分别构建各功能模块间的联系度量指标与各功能模块内的联系度量指标，结合相关性度量矩阵求取各模块划分方案的内聚度与耦合度效用值。将内聚度和耦合度作为证据理论的两个证据源，构造多属性决策矩阵，同时引入隶属度函数概念，对决策矩阵中的效用值进行转换。结合基本概率分配值的定义，求取各焦元的效用分配值，并对每个方案不同属性下的偏好信息进行合成，构造信任区间。最后，基于区间数偏好排序方法，对各决策方案进行排序，获取智能服务机器人系统的各功能模块最优划分粒度。

说明书

技术领域

本发明属于机器人分散控制领域，结合机器人控制系统模块划分方案，本发明尤其涉及一种基于D-S证据理论的机器人功能模块粒度划分评价方法。

背景技术

近年来，随着智能服务机器人研究的快速发展，机器人模块化控制技术受到越来越多研究者的关注。模块粒度划分作为分散控制系统研究的一项关键性技术，可有效缩短开发周期、提高系统的灵活性。如何对不同粒度下的模块划分方案进行评价，进而选出最优方案是机器人模块化技术亟需解决的问题。

智能服务机器人功能模块划分是一个聚类的过程，目前的划分策略有以下几种：1)在模块划分过程中引入复杂网络理论；2)利用现有的聚类算法结合模块划分实际问题进行改进，例如模糊聚类算法、改进的遗传算法等；3)将系统映射为图论理论中的点和边，利用相关原理解决模块划分问题，例如采用MDC(Module Dependency Graph，MDC)模型表示各功能模块之间的关系；4)采用bunch tools等模块属性度量工具实现模块划分。但是以上研究主要集中在模块划分方法的探讨，对于多种模块划分方案的评价与决策准则的研究相对较少。

D-S证据理论属于人工智能和专家系统等领域的研究范畴，在推理、决策以及聚类问题中应用较为广泛。本发明在模糊聚类算法的基础上实现了机器人控制系统功能模块粒度划分，并针对划分粒度寻优问题，提出了基于D-S证据理论的粒度划分评价方法。通过分析各机器人功能模块的相关性矩阵，从模块的内聚度和耦合度两个方面定性地度量模块独立性程度，并将其视为证据理论的两条证据，得到不同粒度下机器人功能模块划分方案的信任区间，进而确定系统的最优划分粒度。

发明内容

本发明的目的是提供一种有效而可靠的机器人功能模块粒度划分评价方法。

为实现上述目的，本发明采用的技术方案如下，

从智能服务机器人系统各模块之间的功能和结构相关性角度进行分析，基于层次分析法结合专家经验对各相关性要素的相对重要性做出判断，并赋予相应的权重，进而构造最细粒度下的各功能子模块相关性度量矩阵。利用模糊树图聚类算法获取不同粒度下的机器人系统模块划分方案，针对划分粒度寻优问题提出了基于D-S证据理论的粒度划分评价方法。该评价方法主要分四步完成：首先，以智能服务机器人系统的各功能模块独立性为原则，分别构建各功能模块间的联系度量指标与各功能模块内的联系度量指标，结合相关性度量矩阵求取各模块划分方案的内聚度与耦合度效用值。其次，将内聚度和耦合度作为证据理论的两个证据源，构造多属性决策矩阵，同时引入隶属度函数概念，对决策矩阵中的效用值进行转换。结合基本概率分配值的定义，求取各焦元的效用分配值，并对每个方案不同属性下的偏好信息进行合成，构造信任区间。最后，基于区间数偏好排序方法，对各决策方案进行排序，获取智能服务机器人系统的各功能模块最优划分粒度。

本发明的技术特征如下：

(1)基于模糊树图理论的机器人的功能模块划分；

功能和结构独立是机器人的功能模块独立性的最基本要求。首先从功能和结构的角度对机器人系统各子结构间的相关性进行分析，应用模糊树图聚类方法将各子结构聚类为模块。具体过程分为以下步骤，

1)通过分析各模块之间的功能依赖性、控制流联系以及数据流联系，建立模块功能相关性量化值指标。

2)通过分析各模块之间的接口数量、接口类型以及功能模块所对应的硬件设备关联程度，建立模块结构相关性量化值指标。

3)基于层次分析法结合专家经验对各相关性要素的相对重要性做出判断，并赋予相应权重，进而构造最细粒度下的各功能子模块相关性度量矩阵R。矩阵中各元素的求解公式如下所示：

$r_{ij}=\left(\begin{array}{cc}{w}_f{r}_{ij}^f+\underset{k=1}{\overset{3}{\Sigma }}{w}_s^k{r}_{ij}^{s^k}& (i\ne j)\\ 1& (i=j)\end{array}\right),(i,j\in \{1,2,\mathrm{...},n\left\}\right)---\left(1\right)$

式中，与分别为模块的功能和结构相关度，表示第k个结构相关度指标，w_f与为权重系数。上式中的i与j表示各模块的编码，f为功能相关性权重标志，s表示结构相关性权重标志，n为系统模块数量。

权重反应了不同相关度属性在决策过程中的重要程度，直接关系到相关性度量矩阵R的准确性。本方法采用层次分析法对机器人系统模块间相关性进行赋权，并根据两两比较标度，结合专家经验构造判断矩阵J。重要性标度如下，

表1重要性标度

标度含义1表示两个要素相比，具有同样的重要性3表示两个要素相比，前者比后者稍重要5表示两个要素相比，前者比后者明显重要7表示两个要素相比，前者比后者极其重要9表示两个要素相比，前者比后者强烈重要2，4，6，8表示上述相邻判断的中间值

利用Matlab软件求得判断矩阵的最大特征根λ_max及其正规化特征向量w，即为权重向量。在一致性检验过程中，若一致性比率CR<0.1时，判断矩阵的不一致性程度在容许范围内，否则需要重新构造判断矩阵J。一致性比率CR计算公式如下所示，

$\begin{array}{c}CR=\frac{CI}{RI}\\ CI=\frac{{\lambda }_{\max }-h}{n-1}\end{array}---\left(2\right)$

CI为一致性指标，其数值越大代表J偏离完全一致性的程度越大；RI为多阶判断矩阵的平均随机一致性指标，表2列出了1到11阶正互反矩阵计算1000次所得到的RI数值。其中，h为判断矩阵的阶数。

表2平均随机一致性指标

n1234567891011RI000.580.901.121.241.321.411.451.491.51

4)本方法采用最大生成树模糊聚类算法对机器人功能模块进行聚类，通过选取不同的阈值λ，即可实现对机器人系统不同粒度的划分。

模糊树图的数学模型为G＝(V,Q^*)，其中V表示节点集合，代表最小粒度下的机器人系统模块，Q^*是根据关系矩阵Q得到的各节点之间的模糊相似关系。若E＝{e_k＝v_iv_j|Q^*(v_i,v_j)>0；v_i,v_jV}，则称G^*＝(V,E)是G＝(V,Q^*)的基础图。将上文所求r_ij分别赋值给G的对应边，其具体规则为w(v_iv_j)＝r_ij(i≠j)，w(v_iv_j)表示第i与第j个模块所代表的节点之间连线的标度值。

T是G的一个生成树，若对于G的全部生成树T’都有

$\underset{e\in E\left(T^{\prime }\right)}{\Sigma }w\left(e\right)\le \underset{e\in E\left(T\right)}{\Sigma }w\left(e\right)---\left(3\right)$

则称T是G的最大生成树。通过对T中的w(e)设置不同的阈值λ，将w(e)<λ的边进行截割，得到当前粒度λ下的机器人系统模块划分方案。

(2)基于D-S证据理论的机器人功能模块划分评价；

对模糊树图进行截割的阈值λ越大，则模块数越多，模块粒度越细，反之模块数越少，模块粒度越粗(定义模块粒度因子为β＝1/λ)。根据模块粒度因子β得到机器人系统模块划分方案集A＝{a_i,i＝1,2,…,n}，通过对不同方案进行评价，获取最优的模块粒度划分。针对以上多属性决策问题，本方法引入D-S证据理论实现对模块划分粒度的寻优。具体过程分为以下步骤：

1)构建模块间联系度量指标与模块内联系度量指标，结合相关性度量矩阵R求取各模块划分方案的内聚度与耦合度效用值。

本方法首先从内聚度和耦合度两个方面构建模块独立性定性指标，并对各指标赋予相应的效用值，如表3、表4所示。

表3模块间联系度量

评价等级内容耦合公共耦合控制耦合数据耦合独立耦合效用值00.250.50.751

表4模块内联系度量

在此基础上，将区间[0,1]划分为5个耦合度子区间，即[0,0.2]，(0.2,0.4]，(0.4,0.6]，(0.6,0.8]，(0.8,1]，每个子区间依次与模块间联系度量效用值1，0.75，0.5，0.25，0对应。相关性度量矩阵中的元素r_ij数值越小，两模块的耦合度越低，对应的效用值越高。相反，r_ij数值越大，两模块的耦合度越高，对应的效用值越低。当r₄₅＝0.80时，由于0.80∈(0.6,0.8]，则模块4与模块5的耦合度效用值为0.25，记为

求取各模块划分方案的耦合度效用值P_O，并做归一化处理，

式中，N为机器人系统功能模块数，表示第i个模块与第j个模块的耦合度效用值，为归一化因子。

同理，将区间[0,1]划分为7个内聚度子区间，即[0,0.1429]，(0.1429,0.2857]，(0.2857,0.4286]，(0.4286,0.5714]，(0.5714,0.7143]，(0.7143,0.8571]，(0.8571,1]，每个子区间依次与模块内联系度量效用值0，0.17，0.33，0.5，0.67，0.83，1对应。例如r₄₅＝0.80时，若模块4与模块5合并为一个模块，由于0.80∈(0.7143,0.8571]，则两模块的内聚度效用值为0.83，记为ψ₄₅＝0.83。

求取各模块划分方案的内聚度效用值P_N，并做归一化处理，

$P_N=\frac{\frac{1}{2}\underset{k=1}{\overset{D}{\Sigma }}\frac{\underset{i\ne j}{\Sigma }{\psi }_{ij}}{C_{M_k}^2}}{D}---\left(5\right)$

式中，D是由基本功能模块聚合而成的模块数量，M_k是聚合模块内所包含的子模块数量，ψ_ij表示第i个模块与第j个模块的内聚度效用值，为归一化因子。

2)将内聚度和耦合度作为D-S证据理论的两个证据源，构造多属性决策矩阵，同时引入隶属度函数概念，对决策矩阵中的效用值进行转换。

本方法求得的划分方案内聚度效用值P_N和耦合度效用值P_O均为数轴上的一个点，由此制定隶属度函数计算方法：

当V_j是一个点值时，g^l＜g^l+1(l∈[1,2,...,L-1])，

$\begin{array}{c}{G}_j^l\left(V_j\right)=\frac{g^{l+1}-V_j}{g^{l+1}-g^l}\\ G_j^{l+1}\left(V_j\right)=1-G_j^l\left(V_j\right)\end{array}---\left(6\right)$

式中，与分别为第j个属性值隶属于等级和的程度，g^l为定性评价等级的定量值。本发明对内聚度和耦合度均设置5个评价等级，各等级对应的效用值如表5所示，

表5属性评价等级效用值列表

评价等级PoorAverageGoodExcellentIdeal效用值00.250.50.751

3)求取各焦元的基本效用分配值，并对每个方案不同属性下的偏好信息进行合成，构造信任区间。以下为D-S证据理论中几个基本概念：

Mass函数定义：设Θ为识别框架，若集函数m:2^Θ→[0,1](2^Θ为Θ的幂集)，并且满足和则称函数m为Θ上基本概率分配；m(X)称为命题X的基本可信数。

信度函数定义：设Θ为识别框架，集函数m:2^Θ→[0,1]为框架Θ上的基本概率分配，则称由

$\begin{array}{cc}Bel\left(X\right)=\underset{Y\subseteq X}{\Sigma }m\left(Y\right)& \forall X,Y\subseteq \Theta \end{array}---\left(7\right)$

所定义的函数Bel：m:2^Θ→[0,1]为Θ上的信度函数。Bel(X)为所有X的子集的精确度总和。

似真函数定义：设Θ为识别框架，Bel：m:2^Θ→[0,1]为Θ上的信度函数，则称由

所定义的函数Pls：m:2^Θ→[0,1]为Θ上的似真函数，Pls(X)称为X的似真度。

本方法设某个决策属性C_j下的所有焦元为A_k(k＝1,2,...,t；t<2^Θ)，则该属性全部焦元的偏好程度可以用以下公式来表示，

P(A_k)＝w_jb_j(9)

其中，w_j为相应属性的重要性权重，b_j为第j个属性的模糊规则取值。

对于若焦元A_k的决策偏好程度为P(A_k)，则加权并归一化后各焦元的基本效用偏好值为，

$m_j\left(A_k\right)=\frac{P\left(A_k\right)}{\underset{k}{\Sigma }P\left(A_k\right)}---\left(10\right)$

根据Dempster合成法则得到两个证据源下所有E效用的合成法则，即假定辨别框架Θ下的两个证据E₁和E₂，其相应的基本概率分配函数为m₁和m₂，则组合规则为：

其中，K为冲突系数，为正则化因子，A_i、B_j分别为m₁和m₂的焦元。基本概率分配函数m称为m₁和m₂的正交和，记为m₁⊕m₂。如果冲突系数K≥1成立，则说明m₁和m₂的正交和m₁⊕m₂不存在。

之后，依据信度函数和似真函数的定义，确定每个决策方案a_i(i＝1,2,…,n)的Bel({a_i})和Pls({a_i})，从而得到每个决策方案的信任区间[Bel({a_i}),Pls({a_i})]。

4)基于区间数偏好排序方法，对各决策方案进行排序，获取智能服务机器人系统功能模块最优划分粒度。

对于两个区间数[a₁,a₂]和[b₁,b₂]，两区间的可能关系如图1所示。通过参考偏好程度规则来参考一个区间效用值优于另一个区间。定义如下：

a>b的偏好程度可以定义为：

b>a的偏好程度可以定义为：

依据以上模型，可以得到如下定义：

如果P(a>b)>P(a<b)，则认为区间a优于区间b，此时a优于b的程度为P(a>b)，记做a＞b；P(a>b)＝P(a<b)＝0.5，则认为a与b没有差别，记做a～b；同理，若P(a>b)<P(a<b)，则认为a劣于b的程度为P(a<b)，记做a＜b。

本发明将上述区间数偏好排序方法引入到机器人功能模块划分方案的寻优问题中，通过对模糊聚类算法得到的n个方案进行次两两对比，最终获得模块的最优划分粒度。

附图说明

图1基于D-S证据理论的机器人模块粒度划分评价方法流程图

图2机器人三维地图创建分散控制系统最大模糊生成树

具体实施方式

下面结合附图和具体实施方式对本发明作进一步的说明。

本发明在模糊聚类算法的基础上实现了机器人控制系统功能模块粒度划分，并针对划分粒度寻优问题，提出了基于D-S证据理论的粒度划分评价方法。所涉及的方法流程图如附图1所示，具体实施过程分为以下步骤：

步骤一，将智能服务机器人系统功能模块按照基本功能和结构进行划分，进而得到最细粒度下的模块集合。

步骤二，参照表6对模块集合中的元素进行两两分析，得到机器人系统功能模块的功能相关性矩阵与结构相关性矩阵。运用层次分析法结合表1构造判断矩阵J，求取其最大特征根以及权重向量w，并通过公式(2)对判断矩阵进行一致性检验，若CR<0.1，则重新构造判断矩阵。

按照公式(1)依次求取相关性度量矩阵R中的元素r_ij。其中功能相关性与结构相关性评价指标如表6所示，

表6功能与结构相关性评价指标

步骤三，将所求r_ij分别赋值给模糊树图G的对应边，即为w(v_iv_j)＝r_ij(i≠j)。依据最大生成树定义以及公式(3)，通过对T中的w(e)设置不同的阈值λ，得到不同粒度下的机器人系统模块划分方案A＝{a_i,i＝1,2,…,n}。

步骤四，依据制定的模块间联系度量指标与模块内联系度量指标，按照公式(4)和公式(5)求取各模块划分方案的耦合度和内聚度效用值P_O、P_N。

步骤五，将内聚度和耦合度作为D-S证据理论的两个证据源，构造多属性决策矩阵。参照表5中的属性评价等级效用值，以及隶属度函数计算方法(具体计算过程间公式(6))，对决策矩阵中的效用值进行转换。

步骤六，根据公式(9)、公式(10)求取各焦元的基本效用分配值，并用公式(11)对每个方案不同属性下的偏好信息进行合成。之后，依据信度函数和似真函数的定义，确定每个决策方案a_i(i＝1,2,…,n)的Bel({a_i})和Pls({a_i})，从而得到每个决策方案的信任区间[Bel({a_i}),Pls({a_i})]。

步骤七，基于上述区间数偏好排序方法，对各决策方案的信任区间进行排序，获取智能服务机器人系统功能模块最优划分粒度。

下面为本发明的在机器人三维地图创建系统中的应用。

按照最小机能对系统进行划分，得到最细粒度的划分方案，该方案由Kinect模块(K₁)、图像预处理模块(K₂)、机器人控制模块(K₃)、SURF图像特征提取模块(K₄)、SURF图像特征匹配模块(K₅)、位姿估计模块(K₆)、关键帧选取模块(K₇)、地图更新模块(K₈)和GUI显示模块(K₉)组成。

依据本发明所提策略，对机器人三维地图创建系统各个子模块进行功能和结构相关度分析，得到子结构之间的相关性度量矩阵R，见表7。

表7相关性度量矩阵R

运用层次分析法结合表1构造判断矩阵J，

求得矩阵J的的最大特征根λmax＝4.1368，正规化特征向量为

w＝[0.5590 0.1039 0.2628 0.0742]

为了进一步证实结论的合理性，需要对矩阵J进行一致性检验。当一致性比率CR<0.1时，判别矩阵的一致性程度在容许范围以内，否则需要重新构造判断矩阵J。经检验，该示例中CI＝0.0456，CR＝0.0507<0.1，满足一致性检验，求得的权重向量w有效。

根据所提模糊树图方法，构建机器人三维地图创建系统最大模糊生成树，如图2所示。在λ取不同值时，对最大生成树进行截割，得到6种模块粒度划分方案：

1)λ＝1时，P1＝K1，P2＝K2，P3＝K3，P4＝K4，P5＝K5，P6＝K6，P7＝K7，P8＝K8，P9＝K9。

2)λ＝0.92时，P1＝(K1+K2)，P2＝K3，P3＝K4，P4＝K5，P5＝K6，P6＝K7，P7＝(K8+K9)。

3)λ＝0.83时，P1＝(K1+K2+K3)，P2＝(K4+K5)，P3＝K6，P4＝K7，P5＝(K8+K9)。

4)λ＝0.76时，P1＝(K1+K2+K3)，P2＝(K4+K5)，P3＝K6，P4＝(K7+K8+K9)。

5)λ＝0.54时，P1＝(K1+K2+K3)，P2＝(K4+K5+K6+K7+K8+K9)。

6)λ＝0.42时，9个子结构合成一个模块。

方案一的耦合度效用值由于该方案为最细粒度下模块划分，对其各模块内部联系效用值不做评判；

方案二的耦合度效用值模块内聚度

方案三的耦合度效用值模块内聚度P_N＝2.66/3＝0.888；

方案四的耦合度效用值模块内聚度P_N＝2.497/3＝0.832；

方案五的耦合度效用值模块内聚度P_N＝1.243/2＝0.622；

方案六的模块间联系度量值无法进行评判，模块内聚度P_N＝10.47/36＝0.291。

表8转化后的决策矩阵

由于P_O和P_N的范围均属于[0,1]区间内，此处为了方便计算，设置不同属性下等价于定性评价等级的定量值分别为：

$G^{P_O}=\{0,0.25,0.5,0.75,1\}$

$G^{P_N}=\{0,0.25,0.5,0.75,1\}$

对决策矩阵中的效用值进行转换，得到转化后的决策矩阵，如表8所示。

设内聚度与耦合度的权重均为0.5，根据公式(9)、公式(10)计算得到各焦元的基本效用分配值：

m₁({A})＝0.1380，m₁({B})＝0.1337，m₁({C})＝0.1132，m₁({D})＝0.1230，m₁({E})＝0.0984，m₁(Θ)＝0.3937；

m₂({B})＝0.1775，m₂({C})＝0.1576，m₂({D})＝0.1477，m₂({E})＝0.1104，m₂({F})＝0.0517，m₂(Θ)＝0.3551。

应用公式(11)对每个方案不同属性下的偏好信息进行合成：

m({A})＝0.0721，m({B})＝0.2076，m({C})＝0.1766，m({D})＝0.1768，m({E})＝0.1314，m({F})＝0.0300，m(Θ)＝0.2057。

依据信度函数和似真函数的定义，确定每个决策方案a_i(i＝1,2,…,n)的Bel({a_i})和Pls({a_i})，从而得到每个决策方案的信任区间[Bel({a_i}),Pls({a_i})]：

Bel({A})＝m({A})＝0.0721；Pl({A})＝0.2778

Bel({B})＝m({B})＝0.2076；Pl({B})＝0.4133

Bel({C})＝m({C})＝0.1766；Pl({C})＝0.3823

Bel({D})＝m({D})＝0.1768；Pl({D})＝0.3825

Bel({E})＝m({E})＝0.1314；Pl({E})＝0.3371

Bel({F})＝m({F})＝0.0300；Pl({E})＝0.2357

基于上述区间数偏好排序方法，对各决策方案的信任区间进行排序，获取智能服务机器人系统功能模块最优划分粒度，计算结果如下：

P(A>B)＝0.1706；P(A>C)＝0.2460；P(A>D)＝0.2455

P(A>E)＝0.3559；P(A>F)＝0.6023；P(B>C)＝0.5754

P(B>D)＝0.5749；P(B>E)＝0.6852；P(B>F)＝0.9317

P(C>D)＝0.4995；P(C>E)＝0.6099；P(C>F)＝0.8563

P(D>E)＝0.6104；P(D>F)＝0.8568；P(E>F)＝0.7465

最终得到机器人三维地图创建系统最优模块划分方案排序为B＞D＞C＞E＞A＞F，因此，系统最优功能模块划分为方案二。