基于与或依赖图的多Agent系统任务分解算法  

Multi-agent task decomposition algorithm based on and-or dependence graph

作　　者：肖增良[1] 乐晓波[1] 周辉[1] 

机构地区：[1]长沙理工大学计算机与通信工程学院,湖南长沙410076

出　　处：《计算机工程与设计》2009年第2期426-428,共3页Computer Engineering and Design

基　　金：湖南省自然科学基金项目(08JJ3124);教育部重点科研基金项目(208098);湖南省教育厅重点科研基金项目(07A056)

摘　　要：针对多Agent系统任务分解问题,提出了基于与或依赖图的任务分解模型及算法。通过引入与或依赖图概念,以描述任务中各操作之间的依赖关系,然后给出了构造操作集的与或依赖图算法,最后在此基础上设计了任务的分解模型及其算法。算法优点是能区分出各操作之间是否具有并行性且能分解出所有可并行执行的操作集,而且由于按与或依赖图中的各层而不是按各操作进行循环,其循环的次数大大减少。实例应用表明,该算法具有较高的时间与空间效率,并支持任务的动态分解。To multi-agent system task decomposition problem, a task decomposition model and algorithm based on dependence is proposed. In order to formalize the dependence relations of operations, the concept of and-or dependency graph is introduced, then a construction algorithm of and-or dependency graph is put forward. Finally, based on these, a task decomposition model and algorithm is designed. The new task decomposition algorithm has the advantages as follows： It can distinguish such operations that can be computed parallelizably and further resolves out all the operation sets that are with parallelity. It reduces cyclic times cycling lay by lay, rather than operation by operation of the and-or dependency graph. An applied instance of the algorithm shows that the algorithm has good time and space efficiency, and support task dynamic decomposition.

关 键 词：智能主体 多AGENT系统 任务分解 子任务 与或依赖图 依赖集 

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