梁志伟，吴海健

(南京邮电大学自动化学院、人工智能学院，江苏 南京 210023)

1 引言

RoboCup机器人足球赛是由多个机器人组成的多智能体系统MAS(Multi-Agent System)。随着机器人智能水平的提高，由于比赛的对抗性和动态环境的时变性，如何规划各个机器人的运动、发挥球队的整体功能，即多智能体任务分解与分配[1]是机器人研究的关键问题。其中任务分配在比赛中起着重要的作用，主要体现在通过视觉模块和传感器模块获取信息，使得多个机器人之间不会互相干扰、冲突，在任务的执行上具有一致性，同时需要解决各个机器人在每个时刻分别完成什么任务、执行什么动作的问题。任务分解是设计任务分配算法的前提，如何简单适度、有效地分解任务对任务分配算法有至关重要的影响[2]。

任务分配通过构建科学健壮的数学模型，设计优化算法完成任务配置，使个体的资源得到充分利用，从而高效地完成任务，体现了多智能体系统(MAS)的高层组织形式与运行机制[3]。合同网协议CNP(Contract Network Protocol)是一种比较经典的任务协商和资源分配策略。随着多智能体系统的发展，合同网由于具有对分布式系统的适用性，逐渐成为一种有效的多Agent协调机制[4]。然而传统合同网协议存在通行开销大、任务资格评价策略不完善等不足，因此国内外的学者针对诸多不足提出了不同程度的改进。为了减少通信开销，降低协商通信量，陈明等[5]基于对Agent心智的综合评价，将Agent分为熟人、一般熟人和陌生人3种类型，以从大到小的概率选择3种Agent招标。Zhang等[6]为了减少协商过程中产生的冗余信息量，在蚁群算法的基础上，建立动态响应阈值模型和信息素流模型。Yeung[7]针对多智能体系统容易受到消息拥塞的影响从而影响任务分配决策效率的问题，将受众限制AR(Audience Restriction)引入了合同网协议。此外，由于管理者知识的局限性，为全面评价合同者能力，贺利坚[8]采用信誉值从直接与间接2方面获取合同者的信任度；Rob[9]从双边市场经济理论和机制设计的角度出发引入了价值网的概念，扩展了合同网协议。在完善任务资格评价策略方面，钱艳平等[10]首先以常规评价策略将任务分配给合同者，而后以负载系数(定义同负载率)为依据，通过合同者之间的协商，达到负载均衡。同样，考虑到合同者接受任务授权的可能性，周坤[11]通过定义可用度为已投标书与投标费用乘积的倒数来反映合同者的可用度；Zhang等[12]研究了协同任务的目标选择策略、协商的合同投标方法以及合同的评价方法，并在虚拟星座应用场景下对合同网协议进行了扩展;Hu等[13]引入了QoS(Quality of Service)多目标约束，给投标者和招标者提供了双向的筛选约束，大大提高了任务完成的质量。对于突发出现的重要问题或者在任务执行过程中合同者不再满足要求时，郝会成[14]引入了可解约机制。当突发重要任务或者合同者不能完成任务时，合同者可以提出解约合同，中止当前任务，所有的“解约任务”就重新由管理者向其他合同者招标。在减少任务冲突的影响方面，Du等[15]提出了合同网协议的二次分配策略，通过公告、竞价和授标等方式，有效地提高了观测收益。

本文在分析相关工作的基础上，以RoboCup标准平台组机器人足球赛为背景，针对目前对任务分解和任务分配在机器人足球赛上的应用研究较少的问题，首先对多机器人系统进行任务分解和层次规划，将总任务分解为若干子任务，以机器人足球赛为背景建立整个系统的层次分解模型；同时根据机器人的角色建立每个机器人的行为任务树模型，并通过层次分析法AHP(Analytic Hierarchy Process)确定每个子任务的优先级；最后，对传统的合同网协议进行改进，对任务分配流程和中标函数等进行了改进和扩展。

2 任务分配数学模型

2.1 问题描述

动态任务分配问题是指在一定的区域内，有m个机器人需要执行n个任务，m个机器人的集合定义为R={Ri|i=1,2,3,…,m},n个任务的集合定义为T={Tj|j=1,2,3,…,n}[16]；由于比赛中机器人是5V5的赛制，所以m设置为5。

定义1任务用一个四元组描述Tj=〈ID,Name,Pri,Info〉,Info=〈x,y,θ〉，其中，ID表示任务编号，Name表示任务名称，Pri表示任务优先级，Info表示目标点位置信息，〈x,y〉表示目标位置，θ表示目标角度。

定义2多机器人系统中的目标函数定义如式(1)所示：

(1)

(2)

其中，Cij为任务执行代价;θij表示第i个机器人在执行任务Tj时，机器人需要转过的角度;ω表示机器人的角速度;Sij表示第i个机器人在执行任务Tj时，距离任务点的路程长度;V表示机器人的运动速度;maxd表示所有参与投标的机器人距离任务点的最大距离;mind表示所有参与投标的机器人距离任务点的最小距离。

2.2 约束条件

定义3第i个机器人的任务队列为Li={Li1,Li2,Li3,…,Lil},其中，Li1表示机器人待执行的第1个任务；定义变量φij表示任务Tj是否分配给机器人Ri,当φij=1表示分配成功，φij=0表示暂未分配；则目标函数f需要满足的约束条件如式(3)和式(4)所示：

(3)

(4)

式(3)限定了同一时刻任意一个机器人只能执行一个任务；式(4)确保了每个任务都能分配给机器人，保证所有任务都被执行。

3 任务分解以及行为任务树模型

任务分解是设计任务分配算法的前提，简单适度、有效地分解任务对任务分配算法有至关重要的影响[17]。本文将总任务设置为{attack,defend}，当球位于对方半场时，己方总任务为attack;球位于己方半场时，己方总任务为defend。当总任务为attack时，根据场上机器人数量，将机器人分别设置为5个角色，它们是：前锋、助攻1、助攻2、后卫和守门员；当总任务为defend时，将机器人分别设置为：前锋、助攻、后卫1、后卫2和守门员。前锋的主要任务是进攻，把球射入到对方的球门；助攻的主要任务是协作前锋进攻，后卫1和后卫2的主要任务是防守，防止对方射门得分；守门员的主要任务是拦截球，防守球门。

3.1 层次结构分解模型

本文建立多机器人系统任务分配的层次结构模型，模型第1层为根任务，第2层为总任务，第3层为角色层，第4层为各个角色的行为任务树，如图1所示。

Figure 1 Hierarchical model图1 层次结构模型

此外，本文设置一个共享信息区用来提供机器人执行任务过程中需要的交互数据，主要包括视觉处理模块、定位模块和路径规划模块。

3.2 行为任务树模型

在层次结构分解模型的基础上，根据每个机器人角色的不同，建立机器人的行为任务树模型。本文以前锋角色为例建立前锋机器人的行为任务树模型，如图2所示。

Figure 2 Behavior task tree model of forward role 图2 前锋角色行为任务树模型

由图2可知：行为任务树模型分为3层，第1层为角色层，第2层为行为层，第3层为动作层。在此基础上，采用层次分析法AHP对任务进行定量分析，确定每个任务的优先级大小。

4 合同网协议的改进

传统的合同网协议存在协商通信量大、任务评价资格不完善等问题[18]，针对这些问题，本文在降低协商通信量、优化合同网流程和评价策略方面对其进行了改进和扩展。本文以5个机器人组成一个分布式多机器人系统，系统中有管理者和合同者，管理者和合同者的身份可以按照实际情况进行动态转换，管理者主要负责招标任务的发布、标书的评估和任务的分配；合同者可以根据招标信息评估协作成本以及根据任务队列负载决定是否参与投标。

4.1 单个Agent模型

本文首先需要对Agent进行建模，单个Agent基本结构如图3所示。

Figure 3 Basic structure of single Agent图3 单个Agent基本结构

单个Agent基本结构中包含视觉模块、定位模块、路径规划模块、信息库、决策和信息处理中心、任务执行器、动作模块和通信模块。信息库中主要存储任务相关信息(包含任务点坐标和运动路径等)、历史任务信息和Agent状态信息(包含能力信息、角色信息和机器人位置信息)。决策和信息处理中心进行任务的发布、招标、投标、任务资格评价、任务分配以及合同的签署。在合同签署之后任务执行器根据决策和信息处理中心的决定执行相应的任务。动作模块执行Agent需要执行的动作。通信模块用来发布和接收信息，以便在节点之间进行通信，以及在调试阶段与PC(Personal Computer)进行连接[19]。

4.2 单个Agent控制过程

Agent的控制大致分为上线程、下线程、感知、运动和调试5个过程，如图4所示。

Figure 4 Control process of single Agent 图4 单个Agent控制过程

其中上线程用来接收上摄像头的数据，下线程用来接收下摄像头的数据；此外，还可以从世界模型中的感知线程获取环境信息以及从运动线程中获取传感器信息[20]。同时，上、下线程对图像进行处理并将检测结果发送到感知线程。感知线程将这些信息与来自运动线程的传感器数据一起用于世界建模和行为控制，并将高级运动命令发送到运动线程。调试线程执行与主机PC的TCP通信以进行调试[21]。

4.3 优先主动招标策略

为了降低协商通信量，管理者在招标时优先向合适的合同者进行招标；合同者收到招标信息后，首先评估自身能力和负载确定是否投标。本文结合机器人足球赛背景，确定了如表1和表2所示的优先级对照表。

(1)总任务为attack时，优先级如表1所示。

Table 1 Priority comparison table(attack)

(2)总任务为defend时，优先级如表2所示。

本文将优先级分为3个等级，最高为等级3；当管理者需要进行招标时，优先向优先级最高的Agent进行招标，若未得到回应则转向优先级次之的Agent进行招标，依次下去；当所有Agent都没有回应，且等待超时时，管理者向所有合同者进行招标。

Table 2 Priority comparison table(defend)

4.4 评价函数

在合同网协议中管理者收到合同者的标书后，需要对其进行任务资格评价，常见的任务资格评价策略包括时间最短策略、成本最低策略、质量优先策略、负载均衡、协作成本和可用度等，通过设计统一的评标函数对标书进行评价形成综合评价表。然而在不考虑合同者自身特性的情况下使用单一的评价函数对所有任务标书进行评价存在片面性和不合理性，针对此问题，本文按照机器人角色的不同设计了不同的评价函数。

(1)进攻类角色(如前锋、助攻)的评价函数如式(5)所示：

(5)

其中，dball表示球相对于机器人的距离；θgoal表示机器人质心、球、对方球门中心三者之间的夹角；τ表示机器人的视觉丢球时间，单位为s;k1、k2和k3为权重系数。

(2)防守类角色(如后卫、守门员)的评价函数如式(6)所示：

(6)

其中，Lgoal表示机器人与己方球门的横向距离；η表示机器人的方向信息，当机器人朝向己方球门一侧时η=1；当机器人朝向对方球门一侧时η=0；k4和k5为权重系数。

4.5 任务分配算法

(1)管理者招标流程。

机器人有招标需求后变为管理者，根据定义1将任务通过团队通信网络进行发布。管理者根据4.3节制定的优先招标策略，优先进行招标；当收到投标信息后，管理者将投标的标书进行公示。若其他空闲机器人在公示期内有异议则可以发起投标，管理者收到其他机器人发送的标书后进行综合评估形成综合评价排序表，最后选取最优合同者签署合同，完成任务分配。若公示期结束后没有机器人发出异议，管理者直接与优先合同者进行合同签署完成任务分配，结束招标。反之，当管理者没有收到优先合同者发出的投标信息，等待超时时，管理者则向所有机器人发出招标请求，管理者收到标书后进行评估形成综合评价表，最后选取最优合同者签署合同完成任务分配，结束招标。管理者招标算法流程图如图5所示。

Figure 5 Flow chart of tendering algorithm 图5 招标算法流程图

(2)合同者投标流程。

合同者通过感知获取环境中的任务，根据自身能力评估招标任务，并从任务队列中选取合适的任务参与投标。投标的标书由四元组描述：〈ID′,IDT,C,L〉,其中，ID′表示合同者的ID；IDT表示招标任务的ID；C表示合同者的任务执行代价；L表示定义3中的机器人任务队列。合同者等待招标信息，收到招标信息后，首先判断自身是否是管理者的优先招标方，若是优先招标方则评估自身能力和任务负载决定是否投标。若自身不是优先招标方就继续等待公示期管理者进行标书公示，合同者评估自身能力并计算任务执行代价，从而决定是否参与竞争投标。为了防止优先方抢占更多资源以及在获得授权前未加节制地盲目投标，造成投标消息剧增和任务无法最优执行的情况出现，本文采用阈值限定的方式进行限制，即当合同者任务队列中待执行的任务小于阈值时合同者才可以继续投标，否则忽略所有新的招标消息。合同者投标算法流程图如图6所示。

Figure 6 Flow chart of bidding algorithm 图6 投标算法流程图

(3)任务分配过程。

任务分配过程主要包括招标和投标；管理者先发布招标信息，合同者获取招标信息并决定是否进行投标，管理者根据收到的投标信息进行综合评估并选择最优的合同者中标，中标合同者执行中标任务。分配任务的整个过程如下所示：

步骤1管理者为每个招标任务设置ID，同时将任务释放到环境中并向优先招标方进行招标。

步骤2合同者从环境中感知招标任务，若自身为优先招标方则评估自身能力和任务负载决定是否投标；若自身不是优先方则等待管理者进行标书公示。

步骤3管理者将收到的优先标书进行公示，若公示期内没有合同者有异议则评估标书，转步骤6；若合同者有异议则等待投标信息。

步骤4合同者感知到管理者进行公示的标书后，进行评估并计算任务执行代价C，若有异议则进行投标。

步骤5管理者收到相同ID′和IDT的投标信息后，通过计算对标书进行评估，在任务集相同的情况下，按任务的优先级从最大值到最小值进行排序，得到任务的综合评价排序表。

步骤6将任务分配给列表中第1个Agent，通知它中标并发布中标结果。

步骤7签署合同。

步骤8任务分配完成。

5 实验验证

5.1 Matlab仿真实验

本文先使用Matlab进行模拟仿真实验，设定任务数为10，实验结果如图7和图8所示。当任务数为10时，机器人任务分配图如图7所示，由图7可以看到利用传统的合同网协议，2号机器人没有被分配到任务，处于空闲状态，而5号机器人分配路径过长，任务过多，显然是分配不合理的。图8为改进合同网后机器人任务分配结果，可以看出没有机器人处于空闲状态，资源利用最优，分配路径也较为合理。

Figure 7 Result of traditional contract network protocol图7 传统合同网协议结果

Figure 8 Result of improved contract network protocol图8 改进后的合同网协议结果

5.2 SimRobot仿真实验

SimRobot仿真软件是用于RoboCup机器人世界杯标准平台组足球比赛调试的模拟仿真软件，它能够模拟物理世界机器人进行比赛对抗的真实场景。通过软件预先设置2支机器人比赛队伍，以5个机器人为一组进行5V5对抗；本文选用一支队伍使用改进后的合同网协议，另一支队伍使用传统合同网协议进行对抗赛。

如图9所示，守门员为1号，前锋为5号，后卫2为3号，后卫1为4号。当2号前锋根据行为任务树进攻到对方球门准备射门时，射门路线被对方机器人阻断不能进行射门操作。因此，2号前锋(此时为管理者)发出协作请求信息(请求协作进攻)；优先向5号助攻(此时为合同者)进行招标，5号助攻收到招标信息后评价自身能力并计算任务执行代价决定是否投标，2号前锋收到投标请求后对其执行代价进行公示，在公示期内其他机器人若无异议则进行合同签署，招标完成。5号机器人收到中标结果后执行相应任务。

Figure 9 Cooperation between robots after improving contract network protocol图9 改进合同网协议后机器人之间的协作

5.3 实体机器人验证

本文在仿真实验的基础上采用NAO机器人作为实验平台，进行实验验证。机器人在运行时，首先需要从共享信息区获取环境信息(比如足球的位置信息、对方球门信息、对方机器人位置信息等)，如图10所示。

Figure 10 Information sharing area图10 信息共享区获取信息

用实体机器人进行验证实验，如图11a所示，2号前锋机器人的前进射门路线被对方机器人阻挡。因此发出协作请求，优先向5号机器人进行招标，经过投标、公示和评标等流程后，5号机器人中标并走到相应位置；当防守时，如图11b所示，对方机器人进攻我方球门前，1号守门员执行防守任务；同时发出协助防守请求，4号机器人中标并执行中标任务。

Figure 11 Physical robot experiment图11 实体机器人实验

在足球比赛实验中，机器人根据设定的行为任务数执行相应的任务。某一时刻机器人行为任务树如图12所示。

Figure 12 Robot behavior task tree图12 机器人行为任务树

通过上面的实验结果可知，相比使用传统合同网协议的机器人队伍，使用改进后合同网协议的机器人队伍灵活性、协作效率、进攻成功率和防守成功率都有很大的提高。任务完成分配时间对比如图13所示。任务完成分配时间较传统的任务完成分配时间缩短了约57%，有效提高了团队协作效率。

Figure 13 Comparison of task allocation time consumption图13 任务分配时间消耗对比

同时，本文对机器人团队进攻端的任务分配效果进行验证，以机器人足球赛为背景进行了50场次的机器人团队对抗赛，机器人团队的进球数如图14所示。从图14中可以看出，使用改进后合同网协议的团队平均进球数稳定在5左右，而使用传统合同网协议的团队平均进球数稳定在2左右，进球率提高了30%。

Figure 14 Number of goals scored by the team图14 比赛团队进球数

除此之外，为了验证任务分配在机器人防守端的效果，本文通过机器人5V5攻防赛对机器人防守端的任务分配效果进行验证。机器人团队的防守成功率如图15所示。从图15中可以看出，使用改进后的合同网协议的防守成功率较使用传统合同网协议的有了很大的提升，防守成功率在97%左右，鲁棒性较好；而使用传统合同网协议的防守成功率在87.5%左右，并且成功率波动幅度较大。

Figure 15 Defense success rate of robot team图15 机器人团队防守成功率

6 结束语

通过以上实验表明，改进的合同网协议能够有效提高机器人团队之间的协作能力，具有良好的鲁棒性和快速性。本文首先以机器人足球赛为背景提出了系统的层次分解模型以及机器人行为任务树，并对任务进行了分解和确权；针对传统合同网协议的不足之处，从降低协商通信量、任务资格评价和合同网协作模型3方面对传统合同网协议进行了改进，并通过实验进行了验证。实验结果表明了本文算法在解决时间紧迫的实际任务分配问题上的有效性。本文算法还存在一些不足之处，接下来的研究重点主要集中在如何为任务队列中待执行任务和招标任务建立耦合模型，以便在任务分配时考虑任务之间的耦合性。其次，对于任务分解本文主要是根据实际经验手动进行分解和确权，因此如何对任务进行自动分解和确权是接下来需要解决的重点问题之一。