基于KD45闭包的群组角色指派研究

张 巍，仝 茹，吴诗珏，王子奇，滕少华

（广东工业大学 计算机学院，广东 广州 510006）

新兴技术与制造业不断融合应用，使得发展智能制造模式与系统成为了制造业的发展需求[1]。在智能制造模式与系统中，人、机等各类智能体于同一智能制造空间内，生产制造需要人、机等各类智能体协同工作完成[2]。人机协同调度通常涉及多人、多机协作，个体需协同执行任务，并在任务执行中扮演关联角色。人机协同调度根据任务需求和特点，完成从任务到多协作成员的优化分配。通过优化分配，能有效保障任务质量管控、成本节约，提高服务与盈利水平。

指派是解决任务分配的重要方法。数学建模是指派的关键。在文献[3-5]中就运用了数学建模的方式来进行指派。群组角色指派(Group Role Assignment,GRA)是指派建模的通用方法，旨在根据代理评价结果寻找角色对代理的最优分配[6-8]。群组角色指派的作用已经有了很好的验证[6,8-10]。但由于合作约束和冲突约束的存在，计算复杂性大幅增加，群组角色指派空间组合爆炸，给建模与计算带来困难。

避免冲突的群组角色指派GRACAR/G[10]就是以冲突矩阵(AC)的形式引入群组角色指派中，有效解决上述问题。但是由于信息不透明问题——冲突信息的不对称性或个体存在认知问题、关系障碍、关联性和推理性不足等问题，获取的AC矩阵是局部的、不完善的，需要更合理的方法得到。

本文希望通过KD45逻辑闭包原理解决AC矩阵的不完善问题。在实际的生产和工作中既存在冲突约束，也存在合作约束，所以本文将合作约束也引入到AC矩阵中，一并通过KD45逻辑闭包原理进行约束关系的完善。

1 真实案例

针对上述问题，本文以一个真实案例进行描述。在某公司中，首席执行官刚刚签署一个价值不菲的合同。他吩咐人力资源经理组建一个由公司员工构成的项目组。人力资源经理为该项目组草拟一份职位列表，如表1所示。并草拟一份候选人员名单，如表2所示。括号中的数字分别是岗位索引和候选人索引。接下来，人力资源经理开展候选人能力评估工作，吩咐每个候选人的业务主管对候选人在各个岗位上进行评估，得到一份候选人在各个岗位上的评分表。一些员工可能会因为性格、工作风格、情感问题、政治信仰等不同原因而产生合作意向或冲突意向，即约束。这些合作和冲突约束在工作中对员工的满意度和团队的协同效率存在很大影响。

表1 岗位需求Table 1 Required positions

表2 候选人在各个岗位上的评分Table 2 Candidates and evaluations on position

人力资源经理需要考虑这些重要约束。人力资源经理需要候选员工填写一份关于该候选人在某岗位上对其他候选员工在某岗位上合作意向或冲突意向的调查问卷。最后，人力资源经理在整合了候选人填写的调查问卷后，得到如表3所示的合作和冲突约束表。

表3 合作和冲突关系表Table 3 Cooperation and conflict

在表3中-1表示冲突关系，1表示合作关系。表3中一行数据表示位于x岗位的A员工认为他与位于y岗位的B员工有合作或冲突关系。例如，表3的第一行信息表示位于0号岗位的2号员工认为与位于0号岗位的8号员工有合作约束关系；表3的第二行信息表示位于2号岗位上的11号员工认为与位于1号岗位的1号员工有冲突约束关系。

合作和冲突约束信息收集越多，越容易促成高效的协同，避免冲突。人力资源经理希望用目前能够获得的信息组建一个更高效的项目组。由于调查问卷的填写是采用自愿的方式，调查问卷填写都是单方面的，基于员工的主观意愿，局部的，非对称的。局部是因为问卷的填写是自愿的。非对称是因为员工填写时是独立的，该员工并不能知道他填写的合作或冲突对象是否也持有和他相同的观点。可以采用经典的逻辑闭包关系KD45进行丰富(在第三部分展开)。并且丰富后的合作和冲突因素信息是目前现有信息能够推论的约束关系集合的并集，无法再次丰富。

例如，位于0号岗位(项目经理)的2号员工(Abbott)认为与位于0号岗位(项目经理)的8号员工(Bella)有合作约束关系；位于0号岗位(项目经理)的2号员工(Abbott)认为与位于1号岗位(高级程序员)的1号员工(Tom)有合作约束关系；则可以推论出位于0号岗位(项目经理)的8号员工(Bella)认为与位于1号岗位(高级程序员)的1号员工(Tom)有合作约束关系。

据此人力资源经理需要竭尽全力将最合适的候选人指派到最需要他的岗位上。人力资源经理考虑后，告诉首席执行官这样的问题可能需要很长一段时间才能得到满意的解决方案。经验丰富的首席执行官了解情况并允许合理的响应时间。人力资源经理指派后，能得到最优相对项目绩效8.34。表2中，加粗数字是被指派的员工及其岗位。

在此场景中，首席执行官和人力资源经理实际上遵循E-CARGO模型的子模型考虑合作和冲突的群组角色指派(GRACAR/G)[10]的初始步骤，人力资源经理遇到了一个可基于KD45逻辑闭包完善的约束关系问题。

2 建模与问题解决

E-CARGO模型是加拿大华裔学者朱海滨提出的角色协同计算模型。E-CARGO模型用9元组∑::=＜C,O,A,M,R,E,G,S0,H＞抽象并描述了协作系统的组成部分[7,11]。其中C 表示类，O 是对象，两者使E-CARGO建模可以引入面向对象的方法；A(Agent)表示协作个体的单元集合；M (Message)表示消息集合； R (Role)表示角色集合(即任务需求抽象)；E(Environment)用于抽象协作环境；G(group)表示群组集合，可用于表示团队。

根据E-CARGO模型，可对第一节提出的问题建模[6-7]。

定义1[6-7,12-15]role(角色)，r::=＜id,Ⓡ＞。其中id是角色的标识号，不同角色id不一致，Ⓡ是代理扮演角色的要求。

定义2[6-7,12-15]agent(代理)a::=＜id, Ⓠ ＞。其中id是代理的标识号，Ⓠ是代理拥有的能力集合。

进一步地，使用A 表示指派为该角色的代理集，即某岗位的候选员工集。 R 表示代理曾经扮演过的角色集。如曾经是程序员、高级程序员等。

定义3[6-7,12-15]角色需求矩阵L，n表示的角色数量。

在本文案例中，表示项目完成此任务需要的角色种类及数量。L[j](0≤j＜n)表示j号角色需要的数量。

定义4[6-7,12-15]代理资格评估矩阵Q[i,j](0≤i＜m,0≤j＜n)，m表示候选代理数量。

在本文案例中，表示候选员工在各个岗位上的工作能力评分值，Q[i,j]∈[0,1]。

定义5 代理角色合作与冲突矩阵ACC，是一个(m×n)×(m×n)的矩阵。

定义6[6-7,12-15]角色分配矩阵T[i,j](0≤i＜m, 0≤j＜n)表示该角色是否被分配给某个代理，T[i,j]∈{0,1}。

在本文案例中，T[i,j]=1表示为i号员工分配j号岗位，T[i,j]=0表示没有为i号员工分配j号岗位。

定义7 群组角色指派的线性求解，即寻找一个可行的分配矩阵T。

针对第一节提出的问题，提出如下约束函数目标函数：

因为以调查问卷的方式收集员工主观意愿信息，并进一步整合得到ACC矩阵，所以ACC矩阵是局部的，非对称。ACC矩阵的局部性造成了该矩阵的稀疏。表4的合作和冲突约束矩阵就是第二部分案例中员工主观信息整合得到的一个ACC矩阵的一部分。从表4可知，ACC矩阵是非常稀疏的矩阵。本文只需要用到其中的非零元素。故可以将其中的非零元素提取出来减少计算时间。

表4 合作或冲突约束表1)Table 4 Cooperation or conflict factors

第一节的指派问题是一个非线性的规划问题[16-18]，也是二次分配问题的一个特殊情况[19-20]。优化第一节提出的问题还有很多方法，如文献[21]通过Pareto差熵控制种群的交流来进行优化。在文献[22]中，朱海滨提出一种很巧妙的优化类似本文的非线性规划问题，即引入一个新的未知数来解决这个问题。本文学习这种方式作出了以下定义。

定义9 约束效果矩阵T A[k] (0≤k＜nc)表示第k个约束关系是否发挥作用，T A[k]∈{0,1}。T A[k]=1表示第k个约束发挥作用；T A[k]=0表示第k个约束没有发挥作用。

针对实例，依照上述定义，得到关系矩阵ACC、资格评估(Q)、分配矩阵(T)与角色需求矩阵(L)

3 基于KD45闭包的GRA

3.1 KD45逻辑

约束矩阵是由员工基于自愿的方式填写的调查问卷整理得到。由于这种获得方式，约束矩阵ACC是稀疏的、局部的和非对称的。而约束矩阵ACC在团队的协同工作中发挥重要作用。所以约束矩阵越完整，群组角色指派时考虑会越全面，在团队协同工作时才能获取更快的效率和更多的收益。

在人机协同时，利用模态逻辑从语义和公理上刻画了信念、信息获取和信任之间的关系。一个典型的基本的系统公理中，可以这么理解，如果代理i相信代理j告诉他的真相p，他相信代理j在真相p的判断，则他相信真相p。KD45就是模态逻辑中的经典的认知逻辑。

3.2 KD45闭包算法

KD45公理及其对应定理如表5所示。

表5 KD45公理及其对应定理Table 5 KD45 axiom and its corresponding theorem

公理K存在于符合Kripke关系语义的关系中。本文的应用场景就存在公理K。

公理D也就是和持续性。事物之间都有联系，没有孤立存在的事物。代理也是，它可能有与其冲突的代理或者合作的代理。

公理4指的是传递性。如果存在于事物x和事物y之间的关系与存在于事物y和事物z的关系相同，那么根据公理4，可以推论出事物x和事物z之间也存在上述关系。即如果代理x认为与代理y之间存在合作关系，代理y认为与代理z之间存在合作关系，则可以推论出代理x应该认为与代理z之间存在合作关系。

本文定义了一些特殊符号，来更好描述算法。

G为经过关系分类后的同类关系的有向连通图。V是G中的顶点的集合。E是G中的边的集合。(a,b)表示起始顶点为a，终点为b的边。s为起始顶点，u为中间顶点，v为终点。R表示两两可达的顶点对集合。

算法1：基于公理4的关系闭包算法。

算法1基于同类关系集的传递性进行完善。将可以通过传递闭包推论出的该类隐性关系挖掘出来，并将其加入到现有的关系集中。

补充定义了以下特殊符号，以更好描述算法：V′(x)是G中的x顶点的邻接顶点集合；l表示集合中元素个数。

算法 2：基于公理5的关系闭包算法。

公理5指的是欧性。假设存在于事物x和事物y之间的关系与存在于事物x和事物z的关系相同，那么根据公理5，可以推论出事物y和事物z之间也存在上述关系。即如果代理x认为与代理y之间存在合作关系，代理x认为与代理z之间存在合作关系，则可以推论出代理y应该认为与代理z之间存在合作关系，或者是代理z应该认为与代理y之间存在合作关系。

算法2基于同类关系集的欧性进行完善。将可以通过欧性闭包推论出的该类隐性关系挖掘出来，并将其加入到现有的关系集中。

KD45是模态逻辑中的经典的认知逻辑。约束关系就是某候选员工对其他候选人在某岗位上的认知。合作约束关系和冲突约束关系都符合KD45逻辑闭包。下面提出来基于上述算法1和算法2的KD45逻辑闭包算法。

算法3：基于KD45逻辑的关系闭包算法。

针对第一节所举出的实际应用场景，在KD45-GRACAR中的团队相对绩效为10.52。表2中划线部分为指派结果。第二节矩阵实例集中的T矩阵为它的指派矩阵。

4 实验

4.1 实验过程

为了获得一个实际的解决方案，使用ILOG包来解决基于KD45逻辑的群组角色指派问题，这与IBM ILOG CPLEX优化工作室最初使用的优化编程语言(OPL)不同。通过设计Java程序来使用包可以绕过OPL编译器，从而获得更好的性能。

要使用ILOG包提供解决方案，主要工作是收集4个必需的元素，并将目标和约束转换为ILOG所需的表单。

步骤1：将ACC关系矩阵进行KD45闭包处理。

对于每一组，在定义范围内随机选择以下数据。(1)Q[i,j] ∈ [0, 1](0 ≤i＜m, 0 ≤j＜n)，即资格评估矩阵中的元素；

(2)ACC[k,4] ∈ {1，-1}(0≤k＜nc)，即合作或冲突

(3)L[j](0 ≤j＜n), 1 ≤L[j] ≤m/n使得m≥na。

对于每一组，都收集一下数据项：

(1)σ1考虑合作和冲突因素的群组角色指派最大相对绩效组

(2)σ2基于KD45逻辑考虑合作和冲突因素的群组角色指派最大相对绩效组

为了观察不同构型之间的差异，本文还改变了显著性数nc=mx，其中x从1到5，一步为1。为了使数据可信，为每个nc创建随机组。最后，计算每个数据项的100个数字的平均值。表6展示了16人团队和17人团队的仿真结果。

表6 团队的绩效对比Table 6 Comparison of team performance

4.2 规模性实验

表7 实验配置Table 7 Configuration for the experiment

图1 KD45闭包时间趋势(m=20, n=6)Fig.1 Time trends of KD45 closure (m=20, n=6)

图2 KD45闭包补充效果(m=20, n=6)Fig.2 Complementary effects of KD45 closure (m=20, n=6)

第二个实验验证基于KD45逻辑闭包的群组角色指派方法(KD45-GRA)的实用性，展示KD45闭包的时间趋势。在每个步骤中，重复测试100轮。在每一轮Q,L,ACC都是随机产生的(均匀分布)，其中m通过一步从10变化到55，步长为5，n为m/6，nc为mx。图3、图4和图5分别为KD45闭包时间趋势图、指派时间趋势图和总实验时间趋势图。随着m、n和nc的变化，总实验的时间主要由指派时间组成，受指派时间影响较大。图6为考虑冲突的群组角色指派与基于KD45逻辑闭包的群组角色指派方法的相对团队绩效对比图。随着m，n的增长，即候选人数和岗位的增长，KD45逻辑闭包算法对于最后的指派绩效越来越重要。

图3 KD45闭包时间趋势Fig.3 Time trends of KD45 closure

图4 指派时间趋势Fig.4 Allocated time trends

图5 总时间趋势Fig.5 Overall time trends

图6 相对团队绩效Fig.6 Relative time performance

5 总结

上万次不同规模下的仿真实验表明，本文提出对群组角色指派的约束关系集完善后再进行群组角色指派方法是可行的、有效的。通过KD45逻辑闭包算法对约束关系集进行了补充与完善，从而优化了群组角色指派模型。利用相关方法，能高效解决信息不透明情况下，难以获取协作与冲突约束的人机协同任务分配及其优化问题。

基于KD45逻辑闭包的群组角色指派可能需要沿着以下路线进一步的研究。

(1) 基于KD45逻辑的群组角色指派中的合作和冲突约束可以是小数。即每个合作约束和冲突约束对损益的效果不同。这一问题在理论和实践上都可能是非常复杂的。

(2) 可以考虑群组角色指派(GRA)的附加约束，例如，代理对角色的偏好，管理员对角色分配的偏好。

(3) 可以考虑合作约束和冲突约束的阈值。阈值分别为多少时，会产生最好的协作效率，即对社会学的很多理论进行试验。从科学的角度分析问题，指导实际生活中的决策。

(4) 最后需要开发更有针对性的方法，将团队成员的主观意见转化为数值，以便应用所提出的方法进行角色分配。