基于带权与或树和AOE-网的多智能体动态任务规划研究

摘要

多智能体系统中的任务规划是近年来研究的热点之一。机器人救援仿真系统是一个典型的异构多智能体系统,为在动态复杂场景下快速、高效规划救援任务,提高救援效率,将灾难损失降到最低,本文引入带权与或树和AOE-网,提出一种高效的动态任务规划方法,主要包括层次任务分解、计划一致协调、动态调整和冲突消除协调这几个相互关联且又紧密结合的过程。
　　 针对任务的复杂性和时序约束问题,提出一种时序约束的带权与或树任务分解层次规划,带权与或树描述了复杂任务与其子任务之间的层次关系以及任务的与或特性；与或树中叶子结点通过添加权值来描述其相应简单任务的执行时间；在带权与或树的基础上,增加辅助线来限定任务结点之间的时序约束,得出时序约束的带权与或树任务分解结构模型,进行层次任务规划。
　　 针对在任务分解后各智能体在执行子任务计划中难以达成一致的问题,提出将带权与或树转化为AOE-网的任务规划。在采用时序约束的带权与或树结构对复杂任务进行分解的基础上,首先基于结点的最小执行权值对带权与或树进行修剪,舍弃部分或子结点,以减少不必要或子任务的执行；然后将时序约束的带权与或树转化为AOE-网,通过AOE-网的关键路径算法,得出各子任务的最早发生时间,基于最早发生时间,计算各子任务的开始执行时间和结束时间,使总任务的完成时间最短,达到计划一致协调。
　　 针对在计划一致协调过程中,智能体执行任务时产生的冲突和动态变化所引起的任务延迟或中断问题,提出基于任务转包和动态再分解的动态任务规划。当智能体的某个子任务产生中断时,便将此任务转包给其他智能体或将此任务再分解成多个简单子任务,形成新的带权与或树,以满足智能体执行任务的可行性；再将新的带权与或树转化为AOE-网,使整个任务能够继续保持计划一致协调,满足任务规划的动态实时性,达到冲突消除和动态调整协调。
　　 通过开发“动态任务规划仿真系统”,验证了所提出的动态任务规划方法的可用性和有效性,并应用到中南大学机器人仿真队CSU_Yunlu中,并在2009年中国机器人公开赛上获得亚军,验证了此任务规划方法的高效性。