多Agent系统问题求解的广义粒子模型方法  

A Generalized Particle Model For Problem-Solving in Multi-Agent Systems

作　　者：帅典勋[1,2] 王兴[1,2] 冯翔[1,2] 

机构地区：[1]华东理工大学计算机科学与工程系,上海200237 [2]清华大学智能技术与系统国家重点实验室,北京100080

出　　处：《计算机学报》2006年第5期740-750,共11页Chinese Journal of Computers

基　　金：国家自然科学基金重点项目基金(60135010);国家自然科学基金(60473044;60575040和60073008)资助.

摘　　要：提出一种多Agent系统分布式问题求解的新的广义粒子模型,将复杂环境下多Agent系统资源分配和任务规划的优化问题转变为广义粒子模型中的粒子运动学和动力学问题.广义粒子模型可以描述和处理的复杂环境包括多Agent系统中的Agent之间存在的随机、并发、多类型的交互行为.各Agent有不同的个性、自治性、生命周期、拥塞程度和故障几率等.本文讨论了广义粒子模型和多Agent系统分布式问题求解的关系,提出了广义粒子模型的数学物理模型和多Agent系统分布式问题求解算法,并且证明了它们的正确性、收敛性、稳定平衡性等基本性质.通过复杂环境下多Agent系统资源分配和任务规划问题的实验和比较,证实了广义粒子模型方法的有效性及其特点.This paper is devoted to a novel generalized particle model （GPM） approach to distributed problem-solving in MAS, which transforms the optimization problem of resource assignments and task allocations of MAS in complex environment into the kinematics and dynamics in GPM. The complex environment in MAS that the proposed GPM approach may deal with in- cludes. A variety of interactions randomly and concurrently occurring among agents; different personality and autonomy of distinct agents; different life-cycle period, congestion degree and failure rate for distinct entities in MAS. At first, the relation between the GPM and MAS in the context of distributed problem-solving is expatiated. Then the mathematical physical formalization for GPM and the parallel algorithm GPMA are presented. The basic properties of the GPMA algorithm, including the feasibility, convergency and stability, are discussed. Through a number of simulation experiments and comparisons related to resource assignments and task allocations in MAS in complex environment, the authors demonstrate many advantages of the proposed GPM approach over other coalition methods for MAS problem-solving in terms of the parallelism and the suitability for complex environment.

关 键 词：多AGENT系统 资源分配和任务规划 分布式问题求解 动力学系统 广义粒子模型 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]