基于心智与扩展合同网的半自治多智能体任务分配

张 立，王茜竹，赵春江，汪 霞，姜大立

（1.后勤工程学院 现代物流研究所，重庆 401311；2.重庆邮电大学 电子信息与网络工程研究院，重庆 400065；3.后勤工程学院 基础部，重庆 401311）

0 引言

近年来，随着产品协同设计、网络化制造、虚拟企业联盟等协同计算理论与应用的快速发展，任务分配问题倍受关注。任务分配的关键是分配方法，不同的工业应用背景催生不同的任务分配方法，例如面向静态确定环境的集中式任务分配方法［1］、面向柔性不确定条件的动态任务分配方法［2］以及各种优化算法在任务分配问题上的应用［3-5］。与传统的任务分配方法相比，基于多智能体系统（Multiagent System，MAS）的任务分配方法［6］具有独特优势：一方面，任务候选Agent可以被赋予更多的理性与智能，使得其具有自治能力、主动参与决策；另一方面，当单个任务候选Agent能力不足时，可以通过MAS的协调机制请求其他任务候选Agent进行协作。由于Agent的自治特性和MAS的分布式自组织能力非常适合刻画网络化制造环境下的多实体协同生产模式，MAS模型常常被用于网络化制造及云制造背景下的任务分配计算［7-8］。

在MAS 任务分配系统中，合同网（contract net）［9］是其中非常重要的协调机制。传统的合同网机制虽然给基于MAS的任务分配协调带来了诸多优势，但其纯分布式结构所固有的控制复杂、通信量大、耗费资源多、不确定性突出等缺陷依然限制了实际场景下的有效应用，因此基于合同网机制的扩展成为研究热点。近年来，在合同网扩展研究领域涌现出若干新颖的思路与方法并应用于工业实践。例如：Hsieh等［10］提出两层合同网协议并将其应用于人类心智系统（Human Mind System，HMS）的工作流规划中；Billington等［11］应用有色Petri网技术扩展了合同网协议以支持多管理Agent的并发控制；Raza等［12］将质量评价因素加入合同网协议中，称之为Q-Contract Net，并将其应用于数字业务生态系统中。类似的研究还包括扩展合同网ECNP［13］、基于阈值和可用度的合同网［14］、基于熟人联盟的合同网［15］、基于信任协议的合同网［16］、基于共享心智模型的合同网［17］、动态合同网［18］等。

上述文献中，引入心智概念以提高合同网的协调效率、降低通信开销是一种重要的改进思路［15-18］。但是，此类合同网协议改进主要集中于从招标Agent的角度讨论熟人关系、信任度等心智状态参数，未见到从竞标Agent的意愿进行研究的文献。事实上，竞标Agent的风险承受能力、繁忙状况、参加任务时间紧迫性等因素将同样决定其竞标的态度，因此，需要考虑实际场景中竞标Agent的半自治性并综合招投标的整个过程对心智参数进行系统化设计；在中标决策函数方面，典型的研究［11-14］均以竞标Agent的报价作为其决策依据，忽略了在网络化制造背景下同样重要的竞标Agent间的协作代价和任务距离代价，因此需要改进中标决策目标函数，以使其更符合实际网络化制造的需求。着眼上述问题，本文以MAS任务分配为研究对象，结合网络化制造条件下制造商与供应商的非对等博弈应用背景改进合同网运行机制，提出一种基于心智与扩展合同网的多Agent任务分配协调方法。

1 基于心智模型的MAS任务分配机制

基于心智模型的MAS任务分配机制的描述如图1所示。图中存在一个管理Agent和多个竞标Agent，管理Agent与竞标Agent之间通过基于合同网的方法进行任务分配协调控制。心智模型是基础，基于心智状态的招标优化、竞标报价和中标优化将支持MAS 任务分配协调关键步骤的控制与决策。其任务分配的具体过程如下：①管理Agent对任务进行分解、组合、排序等预处理；②管理Agent将利用基于心智的竞标Agent优选算法，从所有可承担该任务的Agent集中优选Agent、形成竞标Agent集并发送招标书；③竞标Agent通过招标书属性及竞标决策函数计算成本，结合期望的利润率进行报价、发送竞标书；④管理Agent收集竞标书并按照中标选择算法选择承担任务Agent；⑤签订任务合同，完成任务分配。

该MAS任务分配过程设立管理Agent，由管理Agent对任务本身的要求与竞标Agent的能力、资源进行集中规划后分配给相应的竞标Agent，这与集中式任务分配决策实施方式相吻合；在此基础上，该任务分配过程充分考虑心智的特点，既包括管理Agent对任务承担Agent的信任度、忠诚度、积极度的评价，也考虑竞标Agent对自身风险承受度、繁忙度以及对任务紧迫度的评价，保持了竞标Agent的半自治性。这种集中与半自治相结合的MAS任务分配过程更加适用于具有较强时效要求的松散耦合节点联盟任务分配，如云制造、应急物资筹措等环境。

2 心智模型与心智参数

定义1 基于扩展合同网的MAS心智模型，定义为四元组〈agent＿relation，Mental＿parameter，Call＿for＿bidder，Bid〉。其中：agent＿relation=〈agentm，agentp〉，分别表示管理Agent与任务候选Agent；Mental＿parameter=〈B，L，A，RT，BD，UD〉，分别表示信任度、忠诚度、积极度、风险承受度、繁忙度和紧迫度等Agent心智参数；Call＿for＿bidder=〈Cfb＿df，Cfb＿ca〉表示发标决策函数与算法；Bid=〈Bid＿df，Bid＿ca〉表示投标决策函数与算法。

心智参数Mental＿parameter中各心智参数的具体符号表示、含义、范围和更新公式如下：

（1）信任度B表示agentm对agentp历史任务完成情况的评价，B∈［0…1］。其更新函数为

式中：L表示agentp完成任务ti-1的质量，质量越好L越临近1；P表示agentp执行任务ti-1的失败程度，失败得越彻底P越临近1；δ与ε分别是任务完成的奖励因子与任务失败的惩罚因子。

（2）忠诚度L表示agentm与agentp隶属关系的反映，L∈［0…1］。其更新函数为

忠诚度以组织结构树进行量化。式（2）中，忠诚度为1表示绝对服从，此时agentp是agentm的直系子女；忠诚度为0 表示无隶属，此时agentp与agentm不连通或者agentp是agentm的上层节点；否则，忠诚度为节点间距离的倒数；设定忠诚度在确定的MAS任务求解环境中保持不变。

（3）积极度A表示agentp的竞标积极性，A∈［0…1］。其更新函数为

式中：Nmax为准备分配任务ti时agentp收到的招标总次数，Nti为agentp的中标次数，令Nmax=0时A=0。

（4）风险承受度RT表示agentp承受风险的能力，RT∈［0…1］。其更新函数为

式中：σ与φ分别是任务完成的风险承受度变化因子与任务失败时的变化因子；timei-1为任务ti-1的执行时间，τ为执行任务累计时间增加而产生的风险承受度变化因子。

风险承受度的变化依赖于历史任务的完成情况和参与时间两个要素。历史任务完成得越好，agentp风险承受度越高；累计参与任务时间越长，agentp风险承受度越低。

（5）繁忙度BD表示agentp当前的忙碌状况，BD∈［0…1］。其更新函数为

（6）紧迫度UD表示agentp对任务时间紧迫性的评估，UD∈［0…1］。其更新函数为

式中：ti.start＿deadline为任务的最迟执行时间，ET为评估函数，ti.start＿deadline越小，UD越大。

3 基于心智模型的发标决策

3.1 发标适合度

定义2 发标适合度。当准备分配任务ti时，发标适合度表示管理agentm对任务候选agentp是否适合参与竞标的综合评价值，记为Cf＿Bidder＿fitness（agentp，ti），

式中：B，L和A分别为信任度、忠诚度、积极度三种心智参数；α，β，γ，μ，σ，ρ，φ为权重系数。当ti为普通任务NOR 时，发标决策参考的心智参数按权重从高到低分别为信任度、积极度、忠诚度；当ti为重要任务IMP时，发标决策参考的心智参数按权重从高到低分别为信任度、忠诚度；当ti为紧急任务ARD时，发标决策参考的心智参数按权重从高到低分别为忠诚度、信任度。

3.2 发标决策算法

算法1 Call＿for＿bidder（）。

步骤1 算法初始化。

定义一维数组T，C，A分别存储任务、能力与Agent；定义一维数组Cand＿bidder存储待分配任务的候选Agent集；定义二维数组TC，AC分别存储任务—能力、Agent—能力之间关系；定义三维数组TCA存储任务与Agent之间关系；定义BD＿limit表示发标限额。

步骤2 算法输入。

输入T，C，A，TC，AC；输入任务、能力、Agent的数量。

步骤3 产生矩阵TCA。

步骤4 产生竞标候选Agent集。

承蒙大冶市烹饪行业协会秘书长罗文兄的安排，在暖如春阳般的冬日，一位漂亮的导游姑娘带领我们参观了铜绿山古铜矿遗址博物馆和至今仍在开采的天坑般的铜绿山铜矿矿区。

选取发标适合度值大的前BD＿limit个Agent组成竞标候选集Cand＿bidder。步骤5 发送标书给竞标候选Agent集Cand＿bidder。

4 基于心智模型的竞标

4.1 任务（能力）预计开销

定义3 任务消耗预期。当准备分配任务ti某能力cj时，任务消耗预期表示agentp对执行该需求耗费的预估值，记为Cost（agentp，ti，cj），

式中：RT，BD和UD分别为风险承受度、繁忙度、紧迫度三种心智参数；penalty／reward表示任务能力／资源执行的惩奖比；α，β，γ和δ为权重系数。待分配任务ti的性质可为普通任务NOR、重要任务IMP、紧急任务ARD 三类，权重系数关系互异。

4.2 任务（能力）竞标报价

定义4 任务竞标报价。当agentp对任务ti的某能力cj竞标时，任务能力竞标报价表示agentp对执行任务ti需要的某能力cj所期望的价格，记为Price（agentp，ti，ci），

式中φ为利润系数，根据任务ti的性质以及agentp对任务的渴望程度进行设置。

每个竞标Agent计算得到自己的任务竞标开价后，将其封装进竞标书并发送给管理agentm，然后等待竞标结果。

5 MAS任务分配模型与求解

5.1 MAS任务分配模型

5.1.1 问题假设

在网络化制造MAS 任务分配环境中，假设所有任务与Agent按照分布的地理位置构成连通的拓扑网络；任务ti所需的所有能力位于同一节点，而任务候选agentp的每个能力可分布在不同的节点中。假设为任务ti所需能力对应的所有候选（竞标）Agent集。

定义5 基于心智与扩展合同网的MAS分布式任务分配模型。对于任意待分配任务ti，在其对应的竞标Agent集中搜索某个Agent子集以组成任务分配Agent集RS｝，使得任务分配的总成本Cost（ti）最小。

Cost（ti）由三部分成本构成：①执行任务距离成本，表示RS中每个agent提供给任务ti的能力位置到任务节点所在位置的拓扑距离之和；②执行任务的协作成本，表 示RS中agent间的协作距离之和（协作距离的概念见定义6）；③执行任务的价格成本，表示RS中每个agent对任务ti中能力的竞标报价。

定义6 组织结构树OS＿Tree 和协作距离Col＿distance。组织结构树OS＿Tree是将现实中的各级实体组织描述成节点，并按隶属关系映射形成的特殊树状结构；协作距离Col＿distance是OS＿Tree 中任意两点间协作代价的衡量标准，其值等于连接两节点路径中边的数目。节点与自身的Col＿distance定义为0。两点间的Col＿distance越大，协作代价就越大。

任务分配总Cost（ti）的计算式如下：

5.2 MAS任务分配协调算法

算法2 Operation＿agent＿volting（Taskti）。

步骤1 算法初始化。

定义：二维数组CA存储任务ti中能力集与其对应的竞标Agent集，即用CA存储；变量min＿cost存储任务分配的最小代价值；一维数组RS存储MAS任务分配协调的结果集。

步骤2 算法输入。

输入CA；min＿cost赋值为一大数；RS=∅。

步骤3 任务分配协调计算。

／＊ 算法中Calculate＿cost函数计算承担任务Agent集为｛ac1，ac2，…，acn｝时的任务分配总代价，其计算见式（10）＊／

步骤4 返回任务分配结果。

return（RS）。

5.3 任务后处理

（1）管理agentm对任务实施agentp的任务执行状况进行评价，并重置心智参数B，A。

（2）任务实施agentp对自身任务执行状况进行评价，并重置相关心智参数RT，BD。

（3）Agent能力矩阵及拓扑位置更新。当任务分配后，需删除相应的agentp已分配的能力ci；当任务成功执行后，需恢复对应能力；类似地，还需修改能力ci的拓扑位置关系。

6 算例仿真—企业原材料采购任务分配决策

6.1 算例设置

某制造企业需要制订原材料采购计划（任务t）：需要采购的物资集Rt=｛r2，r4，r6，r8｝，需要供应商提供的能力如包装、运输、加工和装卸等，形式化为需求集Ct=｛c1，c3，c5，c8｝；待选供应商Agent集A=｛a1，a3，a4，a5，a6，a8，a9，a11，a13，a14，a16｝。

供应商Agent集与拟采购物资的关系为：Ar2=｛a1，a3，a4，a6，a11，a14，a16｝，Ar4=｛a1，a5，a8，a9，a11，a14｝，Ar6=｛a4｝，Ar8=｛a4，a5，a8，a11，a13，a14｝；供应商Agent集与所需能力的关系为：Ac1=｛a1，a3，a6，a9，a11，a13，a14｝，Ac3=｛a1，a4，a6，a8，a11，a16｝，Ac5=｛a1，a3，a4，a9，a14｝，Ac8=｛a9，a14｝。

求解供应商Agent集RT：RT=｛ac1，ac3，ac5，ac8，ar2，ar4，ar6，ar8｝，使得任务分配的总成本Cost（t）最小（该例中的能力集与物资集均属于agent的能力范畴，处理方式相同）。

6.2 初始数据

拟分配原材料采购计划任务t时，待选供应商Agent的心智状态设置如表1所示；与任务分配相关的系数与常数设置如表2所示；采购企业与供应商间的拓扑距离如图2所示；供应商间的组织结构如图3所示。

表1 拟分配任务t时各候选Agent的心智状态

表2 相关系数及常数设置情况

6.3 基于心智模型的发标决策

6.3.1 发标适合度CF＿Bidder＿fitness计算

由于任务t的性质为普通任务，采购企业Agent根据式（7）以及表1、表2的初始值得到待分配任务Agent的发标适合度CF＿Bidder＿fitness的计算结果，如表3所示。

6.3.2 优化发标Agent集并发标

采购企业Agent根据算法1 和发标限额常量BD＿limit，选择CF＿Bidder＿fitness值较大的供应商Agent形成拟发标Agent集；然后组织竞标书并将其发给对应的拟发标Agent集。

表3 待分配任务Agent发标适合度Cf＿Bidder＿fitness的计算结果

6.4 考虑价格、距离与协作的MAS任务分配协调

由于任务t的性质为普通任务，根据式（8）、式（9）以及表1、表2的相应初始值得到待分配任务Agent对承担任务（能力）的预计开销值Cost与竞标报价Price，如表4所示。

表4 任务（能力）预计开销Cost及竞标报价Price 计算结果（Cost／Price）

根据采购企业与供应商网络拓扑距离图（如图2）即可计算采购企业Agent与供应商Agent间的距离成本。

根据供应商组织结构图（如图3）即可计算供应商Agent节点两两间的协作距离，从而计算得到各任务分配候选Agent集合的总协作成本。

6.4.4 MAS任务分配协调

在Visual Studio 2008 环境下，基于Visual C++语言，以表1 和表2 中的数据为初始值，实现算法1和算法2，其用户界面和运算结果如图4所示。运算结果说明，将企业采购任务t的能力／物资子任务集｛c1，c3，c5，c8，r2，r4，r6，r8｝对 应分配给供应商Agent集｛a3，a1，a3，a14，a3，a5，a4，a5｝，其任务分配的综合成本最低。该算例仿真程序验证了所提MAS任务分配算法的有效性。通过参数化的方法对程序的初始变量进行处理，即可实现支持基于不同初始数据集的MAS任务分配协调，从而进一步提高程序的通用性。

7 结束语

本文综合Agent心智建模的经典文献并针对网络化制造背景下的实际需求，提出心智模型，包括信任度、忠诚度、积极度、风险承受度、繁忙度和紧迫度等心智因素，分别从管理Agent和竞标Agent两个角度进行应用，使心智模型更具系统性和实用性；另一方面，采用集中与分布结合的混合方式设计MAS任务分配协调，管理Agent利用心智模型对竞标Agent进行优选，反映了竞标Agent的绩效；竞标Agent利用心智模型进行竞标报价，体现了竞标Agent的绩效；MAS 任务分配模型算法采用价格、协作与距离作为优化代价的多目标因素，更能反映网络化制造的需求。整个任务分配协调以任务所需的能力而不是整个任务作为处理的基础，具有更精细的粒度与合理性。下一步工作中，将采用多属性优化方法对该机制中的重要参数权重取值进行研究，进一步提高本MAS 任务分配协调机制的实用性。

［1］PAPANTONOPOULOS S.System design in normative and actual practice：a comparative study of cognitive task allocation in advanced manufacturing systems［J］.Human Factors and Ergonomics in Manufacturing &Service Industries，2004，14（2）：181-196.

［2］LIU Hong，LIN Zongkai.A cooperative design approach supporting dynamic task assignation ［J］.Journal of Software，2001，12（12）：1830-1836（in Chinese）.［刘 弘，林宗楷.一种支持动态任务分配的协同设计方法［J］.软件学报，2001，12（12）：1830-1836.］

［3］ZHONG Qiuxi，XIE Tao，CHEN Huowang.Task matching and scheduling by using genetic algorithms［J］.Journal of Computer Research Development，2000，37（10）：1197-1203（in Chinese）.［钟求喜，谢 涛，陈火旺.基于遗传算法的任务分配与调度［J］.计算机研究与发展，2000，37（10）：1197-1203.］

［4］ALEKSANDAR J，ALVARO G，DIEGO A，et al.Distributed bees algorithm for task allocation in swarm of robots［J］.IEEE Systems Journal，2012，6（2）：296-304.

［5］ZHAO F Q，HONG Y，YU D M，et al.A hybrid algorithm based on particle swarm optimization and simulated annealing to holon task allocation for holonic manufacturing system［J］.International Journal of Advanced Manufacturing Technology，2007，32（9／10）：1021-1032.

［6］FATIMA S S，WOOLDRIDGE M.Adaptive task resources allocation in multi-agent systems［C］／／Proceedings of the 5th International Conference on Autonomous Agents.New York，N.Y.，USA：ACM，2001：537-544.

［7］MONOSTORI L，VÁNCZA J，KUMARA S R T.Agent-based systems for manufacturing［J］.CIRP Annals-Manufacturing Technology，2006，55（2）：697-720.

［8］XU X.From cloud computing to cloud manufacturing［J］.Robotics and Computer-Integrated Manufacturing，2012，28（1）：75-86.

［9］DAVIS R，SMITH R G.Negotiation as a metaphor for distributed problem solving［J］.Artificial Intelligence，1983，20（1）：63-109.

［10］HSIEH F S，CHIANG C Y.Workflow planning in holonic manufacturing systems with extended contract net protocol［C］／／Proceedings of Next-Generation Applied Intelligence.Berlin，Germany：Springer-Verlag，2009：701-710.

［11］BILLINGTON J，GUPTA A K，GALLASCH G E.Modelling and analysing the contract net protocol-extension using coloured petri nets［C］／／Proceedings of the 28th International Conference on Formal Techniques for Networked and Distributed Systems.Berlin，Germany：Springer-Verlag，2008：169-184.

［12］RAZA M，HUSSAIN F K，HUSSAIN O K，et al.Q-Contract net：a negotiation protocol to enable quality-based negotiation in digital business ecosystems［C］／／Proceedings of 2010 International Conference on Complex，Intelligent and Soft-ware Intensive Systems.Washington，D.C.，USA：EEE，2010：161-167.

［13］FISCHER K，MÜLLER J R G P，PISCHEL M.Cooperative transportation scheduling：an application domain for DAI［J］.Applied Artificial Intelligence，1996，10（1）：1-34.

［14］YANG Jian，LI Wenli，HONG Chunyu.Improvement to contract net protocol based on threshold and availability［J］.Computer Integrated Manufacturing Systems，2009，15（5）：1017-1022（in Chinese）.［杨 件，李文立，洪春宇.基于阈值和可用度的合同网协议改进方案研究［J］.计算机集成制造系统，2009，15（5）：1017-1022.］

［15］TAO Haijun，WANG Yadong，GUO Maozu，et al.A multiagent negotiation model based on acquaintance coalition and extended contract net protocol［J］.Journal of Computer Research and Development，2006，43（7）：1155-1160（in Chinese）.［陶海军，王亚东，郭茂祖，等.基于熟人联盟及扩充合同网协议的多智能体协商模型［J］.计算机研究与发展，2006，43（7）：1155-1160.］

［16］YU Zhenhua，LIU Yu，CAI Yuanli.On wireless sensor networks collaboration based on an extended contract net protocol［J］.Control and Decision，2009，24（1）：61-65（in Chinese）.［于振华，刘 宇，蔡远利.基于扩展合同网协议的无线传感器网络协作方法研究［J］.控制与决策，2009，24（1）：61-65.］

［17］CHEN Ming，JIAN Yumei.Research on mental-coefficient based multi-agent contract net collaborative model［J］.Computer Application and Software，2013，30（6）：46-51（in Chinese）.［陈 明，简玉梅.基于心智系数的多Agent合同网协作模型研究［J］.计算机应用与软件，2013，30（6）；46-51.］

［18］ZHANG Haijun，SHI Zhongzhi.Dynamic contract net protocol［J］.Computer Engineering，2004，30（21）：44-46（in Chinese）.［张海俊，史忠植.动态合同网协议［J］.计算机工程，2004，30（21）：44-46.］