文档介绍：摘要
动态任务分配就是将合适的任务实时地分配给合适的成员,以充分利用系统的
资源,提高任务的完成绩效。它通常包含再分配型和新任务型两类:再分配型的动
态任务分配是封闭系统中的一类典型问题,目前已有成熟的技术方法,如动态负载
平衡和各种优化算法等。新任务型的动态分配,是当今以分布式、开放性、智能化
和社会性为特征的复杂系统运作中的重要问题,这些系统成员异构所带来的复杂性
以及系统内外环境变化所产生的不确定性等都给这类动态任务分配问题的求解带来
了困难。多 Agent 系统(MAS)思想的出现,为解决这类新任务型的动态任务分配问题
提供了新的途径。基于 MAS 研究复杂系统不仅可以有效地揭示复杂系统的运作特
征,而且可以借鉴 MAS 研究的理论成果和方法技术,解决复杂系统运作中用传统方
法难以求解的问题。此外,现实需求驱动下的研究成果又可以进一步地丰富 MAS 理
论,指导更为广泛的复杂系统运作。因此,基于 MAS 的动态任务分配问题研究具有
重要意义。
基于 MAS 研究动态任务分配问题的基本思路是:选取 MAS 作为复杂系统的研
究模型,借鉴现有任务分配理论的研究成果和技术方法,围绕任务分解、集中式运
作环境的任务分配以及分布式运作环境的任务分配展开讨论。在形式化分析任务和
Agent 能力特征的基础上,提出基于 MAS 任务分解的原则和方法步骤;针对集中式
运作环境,建立基于马尔可夫决策过程(MDP)的动态任务分配模型,用来指导任务分
配方案的优化;针对分布式决策环境,建立基于扩展合同网的任务分配模型,通过
任务分配运作框架和流程的描述,规范化基于扩展合同网(ECNP)动态任务分配的过
程。
基于 MAS 的任务分解是研究复杂系统任务分配的前期准备。一般地,复杂系统
中被分配的任务可区分为简单任务和复杂任务。简单任务可直接分配给单个 Agent
独立完成;复杂任务通常转化为简单任务后再分配。在对简单任务和 Agent 能力特
征建模的基础上,我们提出了基于 MAS 任务分解所遵循的 6 项原则和 5 个关键步骤。
II
基于 MAS 的任务分解不仅可以为复杂问题的求解提供指导,而且也向规范化的任
务分解迈进了一步。
集中和分布是复杂系统运作的两类重要模式。对于集中式动态任务分配问题,
根据系统运作收益最大化的目标、环境的不确定性和动态任务分配序列决策的要求,
我们构建了相应的马尔可夫决策过程模型,并证明了该模型在状态空间和行动空间
有限时存在最优解,讨论了模型求解的迭代算法。仿真实验表明基于 MDP 的动态任
务分配因考虑了系统的长远收益,虽然在某些决策时点做出的决策不是即时最优的,
但系统长期运作的期望总收益则优于即时最优分配方案。因此,基于 MDP 的动态任
务分配模型适用于解决长期运作的小规模系统中的动态任务分配问题。
对于分布式动态任务分配问题,在建立扩展合同网理论的基础上,通过描述基
于 MAS 动态任务分配问题的两级框架,提出了基于扩展合同网求解动态任务分配的
基本思想,规范化了从招标准备、招标、投标到揭标的运作流程。基于扩展合同网
动态任务分配的基本思想包括:基于任务熟人信任度的招标策略,基于自适应的投
标策略和基于模糊综合评判的评标策略;以及基于时限的联合承诺协议和基于
KQML 的通信规范等。这些思想不仅可以有效地指导分布式环境下复杂系统的任务
分配问题,也丰富和发展了合同网理论。
基于 MAS 的动态任务分配研究涉及 MAS、组织理论、决策技术等多个领域的
内容,其进一步的完善和发展也还有很多工作要做。总体来讲,基于 MAS 的动态任
务分配研究不仅是现实应用的需要,也是理论发展的必然趋势,必将有越来越多的
研究者关注这一课题。
关键词: 多 Agent 系统(MAS) 任务分解任务分配马尔可夫决策过程(MDP)
P)
III
知识水坝为您整理
Abstract
Dynamic task allocation is a process of assigning appropriate tasks to appropriate
members in real time, in which way it can make full use of system resources to improve
the system performance. It usually consists of 2 types, ., reallocation type and new task
type. The former type is a typical iss