任务优先满足和绩效奖励的重叠联盟效用分配

桂海霞,赵邦磊,张国富,苏兆品,蒋建国

(1.安徽理工大学经济与管理学院,安徽 淮南 232001;2.合肥工业大学计算机与信息学院,安徽 合肥 230009)

1 引言

在多Agent 系统(multi-agent systems,MAS)[1]中,当单个Agent 的资源有限无法独自完成某个任务时,可以联合多个Agent 组成团队共同完成任务,这样的团队即为联盟[2].作为MAS 中一种主要的协作方式,联盟形成已广泛应用于电子商务[3]、研发合作[4]、多机器人协作[5]、传感器网络[6]、电力传输[7]、虚拟企业[8]和动态供应链[9]等诸多领域.

联盟形成是联盟进行一切活动的基础,主要包含三个方面的研究内容:联盟值计算[10,11]、联盟结构生成[12,13]和效用分配[14,15].其中效用分配是联盟形成的关键,直接影响了联盟的稳定性和Agent 执行任务的积极性.效用分配的不合理会导致Agent 提前退出联盟,从而可能导致任务执行失败.因此,在效用分配中,一般要求,每个Agent 获得的效用应该和它自身的贡献相匹配.此外,新Agent 请求加入联盟时要保证不能损害已有Agent 成员的原来的预期效用,即满足效用非减.

虽然目前效用分配研究已经取得了一些研究成果,但大都局限于非重叠联盟[16],即要求每个Agent 在任意时刻只能参与一个任务,造成Agent 资源的极大浪费.在重叠联盟形成(overlapping coalition formation,OCF)[17]中,一个Agent 可以同时参与多个联盟承担多个任务.这种重叠协作模式既提升了MAS 的资源利用率,又提升了任务的执行效率.然而,如何在多个联盟之间分配效用,尤其如何给参与多个任务的Agent 成员划分效用是面临的一个难点问题.已有效用分配策……