（计算机科学与技术专业论文）基于带权与或树和aoe网的多智能体动态任务规划研究.pdf

t 。， 、 ，一二| 、 ， 原创性声明 本人声明，所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果。尽我所知，除了论文中特别加以标注和致谢 的地方外，论文中不包含其他人已经发表或撰写过的研究成果，也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料。与我 共同工作的同志对本研究所作的贡献均己在论文中作了明确的说明。 作者签名：i 醯国塑。日期：2 里坦年五月三日 学位论文版权使用授权书 本人了解中南大学有关保留、使用学位论文的规定，即：学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文， 允许学位论文被查阅和借阅；学校可以公布学位论文的全部或部分内 容，可以采用复印、缩印或其它手段保存学位论文。同时授权中国科 学技术信息研究所将本学位论文收录到中国学位论文全文数据库， 并通过网络向社会公众提供信息服务。 毖 日期：盖堂年么月王日日期：型! ! 年上月互日 摘要 多智能体系统中的任务规划是近年来研究的热点之一。机器人救 援仿真系统是一个典型的异构多智能体系统，为在动态复杂场景下快 速、高效规划救援任务，提高救援效率，将灾难损失降到最低，本文 引入带权与或树和a o e 网，提出一种高效的动态任务规划方法，主 要包括层次任务分解、计划一致协调、动态调整和冲突消除协调这几 个相互关联且又紧密结合的过程。 针对任务的复杂性和时序约束问题，提出一种时序约束的带权与 或树任务分解层次规划，带权与或树描述了复杂任务与其子任务之间 的层次关系以及任务的与或特性；与或树中叶子结点通过添加权值来 描述其相应简单任务的执行时间；在带权与或树的基础上，增加辅助 线来限定任务结点之间的时序约束，得出时序约束的带权与或树任务 分解结构模型，进行层次任务规划。 针对在任务分解后各智能体在执行子任务计划中难以达成一致 的问题，提出将带权与或树转化为a o e 一网的任务规划。在采用时序 约束的带权与或树结构对复杂任务进行分解的基础上，首先基于结点 的最小执行权值对带权与或树进行修剪，舍弃部分或子结点，以减少 不必要或子任务的执行；然后将时序约束的带权与或树转化为a o e 网，通过a o e 网的关键路径算法，得出各子任务的最早发生时间， 基于最早发生时间，计算各子任务的开始执行时间和结束时间，使总 任务的完成时间最短，达到计划一致协调。 针对在计划一致协调过程中，智能体执行任务时产生的冲突和动 态变化所引起的任务延迟或中断问题，提出基于任务转包和动态再分 解的动态任务规划。当智能体的某个子任务产生中断时，便将此任务 转包给其他智能体或将此任务再分解成多个简单子任务，形成新的带 权与或树，以满足智能体执行任务的可行性；再将新的带权与或树转 化为a o e 网，使整个任务能够继续保持计划一致协调，满足任务规 划的动态实时性，达到冲突消除和动态调整协调。 通过开发“动态任务规划仿真系统”，验证了所提出的动态任务 规划方法的可用性和有效性，并应用到中南大学机器人仿真队 c s uy u n l u 中，并在2 0 0 9 年中国机器人公开赛上获得亚军，验证了 此任务规划方法的高效性。 关键词机器人救援仿真系统，多智能体系统，带权与或树，任务规 戈0 ，a o e 网 a bs t r a c t t a s kp l a n n i n gi nm u l t i a g e n ts y s t e mi so n eo ft h eh o t s p o t si nr e c e n t y e a r s r o b o c u p r e s c u es i m u l a t i o ns y s t e m i sa t y p i c a lh e t e r o g e n e o u s m u l t i a g e n ts y s t e m ，f o rq u i c ka n de f f i c i e n t r e s c u et a s k p l a na n dt o m i n i m i z ed i s a s t e rl o s s e sa n di m p r o v et h ee 伍c i e n c yo fr e s c u et a s k si na c o m p l e xa n dd y n a m i cs c e n a r i o s ，a ne f f e c t i v ed y n a m i ct a s kp l a n n i n g m e t h o dw h i c h m a i n l y i n c l u d e sh i e r a r c h i c a lt a s k d e c o m p o s i t i o n c o n s i s t e n tp l a n n i n gc o o r d i n a t i o n ，d y n a m i ca d j u s t m e n ta n dc o n f l i c t e l i m i n a t i n gc o o r d i n a t i o nw h i c ha r ei n t e r r e l a t e da n dc l o s e l yi n t e g r a t e d p r o c e s s i s p r e s e n t e db yi n t r o d u c i n gw e i g h t e d a n d o rt r e ea n d a o e n e t w o r ki nt h i sd i s s e r t a t i o n f o rt h ec o m p l e x i t yo ft h et a s k sa n dt i m i n gc o n s t r a i n t s ，at a s k d e c o m p o s i t i o nh i e r a r c h yp l a n n i n gu s i n gw e i g h t e da n d o rt r e e w i t h t i m i n gc o n s t r a i n t si sp r e s e n t e d t h ew e i g h t e da n d 0 r t r e ed e s c r i b e st h e h i e r a r c h i c a lr e l a t i o n s h i pb e t w e e nc o m p l e xt a s k sa n ds u b t a s k sa n dt h e 炖| o rf e a t u r e so ft a s k s ；t h e 、e a fn o d e so fa n d | o rt r e ea r ea p p e n d e d w e i g h t st or e p r e s e n tt h ee x e c u t i o nt i m eo fc o r r e s p o n d i n gs u b t a s k s ；a i d l i n ei sa d d e di n t ot h et r e et or e s t r i c tt h et i m ec o n s t r a i n ta m o n gt h e r e l a t i o n a lt a s kn o d e s ，a r r i v i n gat a s kd e c o m p o s i t i o ns t r u c t u r em o d e lw i t h t i m i n gc o n s t r a i n t sa n df o rh i e r a r c h i c a lt a s kp l a n n i n g w i t hr e g a r d st ot h ed i f j f i c u l tf o re a c ha g e n tt or e a c hc o n s i s t e n c yi n e x e c u t i n gs u b - t a s kp l a na f t e rt a s kd e c o m p o s i t i o n ，at a s kc o o r d i n a t i o n a p p r o a c ht h a tt h ew e i g h t e da n d o rt r e ei sc o n v e r t e dt oa o e n e t w o r k i sp r o p o s e d f i r s t l y , o nt h eb a s i so fd e c o m p o s i n gt h ec o m p l e xt a s kb ya w e i g h t e da n d o rt r e ew i t ht i m i n gc o n s t r a i n t s ，p r u n i n gt h ew e i g h t e d 焖| q rt r e eb a s e do ne x e c u t i o n w e i g h t s o fn o d et od i s c a r d p a r t l yo r - s u b t a s kf o rr e d u c t i o no ft h ee x e c u t i o no fu n n e c e s s a r yo r - s u b t a s k ； t h e nt h ew e i g h t e da n d o rt r e ew i t ht i m i n gc o n s t r a i n t si sc h a n g e di n t o a na o e n e t w o r kt og e tt h ee a c hs u b t a s k se a r l i e s to c c u r r e n c et i m eo n w h i c hc a l c u l a t i n gt h es t a r tt i m ea n de n dt i m eo fs u b t a s k s ，m a k i n gt h e e n t i r et a s kb ec o m p l e t e di nt h es h o r t e s tt i m e ，a c h i e v i n gt h ec o n s i s t e n t p l a n n i n gc o o r d i n a t i o n c o n s i d e r i n gt h ep r o b l e m sf o rt h ed e l a y o ri n t e r r u p t i o no ft a s k s c a u s e db yc o n f l i c t sw h e na g e n t sc a r r y i n go u tt h e ma n dd y n a m i cc h a n g e s u n d e rt h ep r o c e s so fc o n s i s t e n tp l a n n i n gc o o r d i n a t i o n ，ad y n a m i ct a s k p l a n n i n gb a s e do nt a s ks u b c o n t r a c t i n ga n dd y n a m i cr e d e c o m p o s i t i o ni s p r e s e n t e d m e n a n a g e n t s s u b - t a s kg e n e r a t e sa ni n t e r r u p t ，i ti s s u b c o n t r a c t e dt oo t h e ra g e n to rb r o k e nd o w ni n t os e v e r a ls i m p l es u b - t a s k s ， f o r m i n gan e ww e i g h t e da n d o r t r e ea n dm e e t i n gt h ee n f o r c e a b i l i t yo f t a s k s ；b yc o n v e r t i n gt h en e ww e i g h t e dan d 0 r t r e ei n t oa o e n e t w o r k t oc o n t i n u o u s l ym a i n t a i nc o n s i s t e n tp l a n n i n gc o o r d i n a t i o no ft o t a lt a s k a n dm e e tt h ed y n a m i cr e a l t i m er e q u i r e m e n t si nt a s kp l a n n i n g ，a n dr e a c h c o n f l i c te l i m i n a t i o nc o o r d i n a t i o na n dd y n a m i ca d j u s t m e n tc o o r d i n a t i o n ad y n a m i ct a s k p l a n n i n g s i m u l a t i o n s y s t e m i s d e v e l o p e d t o d e m o n s t r a t et h e a v a i l a b i l i t ya n de f f e c t i v e n e s s o f d y n a m i cp l a n n i n g m e t h o da n di th a sb e e na p p l i e dt ot h er o b o tr e s c u es i m u l a t i o nt e a m c s uy u n l uo fc e n t r a ls o u t hu n i v e r s i t y , w h i c hw o nt h es e c o n dp l a c ei n 2 0 0 9c h i n a r o b o tc o n t e s t ，t h i sa l s oc o n f i r m e dt h a tt h ea b o v em e t h o di s e f f e c t i v e k e yw o r d s r o b o c u p r e s c u e s i m u l a t i o ns y s t e m ，m u l t i a g e n t - s y s t e m ，w e i g h t e d - a n d o rt r e e ，t a s kp l a n n i n g ，a o e - n e t w o r k 目录 第一章绪论。1 1 1 研究背景及意义1 1 2 国内外研究现状4 1 3 研究内容和组织结构6 1 3 1 研究内容6 1 3 2 论文的组织结构7 第二章机器人救援仿真系统及任务规划问题研究8 2 1 机器人救援仿真系统8 2 1 1 机器人仿真救援系统结构8 2 1 2 机器人救援仿真系统中智能体及其任务1 0 2 2 任务与智能体规划的表现形式1 1 2 2 1 简单任务与复杂任务，11 2 2 2 智能体规划的表现形式1 2 2 3 机器人救援仿真系统任务规划设计难点与关键问题1 3 2 3 1 任务规划设计难点1 4 2 3 2 任务规划要解决的关键问题1 4 2 4 机器人救援仿真系统任务规划解决方案一1 5 2 5 小结1 6 第三章时序约束的带权与或树任务分解层次规划1 7 3 1 任务分解及原则：1 7 3 2 时序约束的带权与或树任务分解结构模型1 8 3 2 1 带权与或树任务分解结构1 8 3 2 2 时序约束的带权与或树任务结构2 0 3 3r c r s s 任务规划问题描述2 1 3 4 时序约束的带权与或树任务结构生成2 3 3 5 小结o 2 3 第四章带权与或树转化为a o e 网的任务规划2 5 4 1 计划一致协调与a o e 网2 5 4 2 基于执行权值的带权与或树的修剪2 6 4 3 时序约束的带权与或树转化为a o e 一网2 8 4 4 基于a o e 网的最早发生时问的计划一致协调2 9 4 5 任务规划仿真与分析3 0 4 5 1 时序约束的带权与或树的任务分解3 0 4 5 2 计划一致协调仿真与分析31 4 5 3 机器人救援仿真系统中任务规划的实例。3 3 4 6 小结3 5 第五章基于任务转包与动态再分解的动态任务规划3 6 5 1 冲突消除协调与动态调整协调：3 6 5 2 基于任务转包与动态再分解的动态协调规划3 7 5 2 1 单个智能体的简单任务集3 7 5 2 2 基于任务转包与动态再分解的动态协调3 8 5 2 3 动态任务协调规划过程4 0 5 3 动态任务规划仿真4 0 5 3 1 冲突消除与动态调整协调仿真与分析4 0 5 3 2 任务转包与动态再分解仿真与分析4 1 5 4 动态任务规划在机器人救援仿真系统中的应用4 3 5 4 1 机器人救援仿真系统中动态任务规划实例4 3 5 4 2 实验数据与性能比较4 5 5 5 小结4 8 第六章总结与展望4 9 6 1 结论4 9 6 2 展望5 0 参考文献：5l 附录1图索引：5 6 附录2 表索引5 7 致谢5 8 攻读学位期间主要的论文情况和科研情况5 9 m a s r c r s s d d l a o e 符号说明 m u l t i a g e n ts y s t e m r o b o c u p r e s c u es i m u l a t i o ns y s t e m d y n a m i cd e s c r i p t i o nl o g i c a c t i v i t yo ne d g e 多智能体系统 机器人救援仿真系统 动态描述逻辑 边表示活动 硕十学位论文 第一章绪论 第一章绪论 作为分布式人工智能的一个重要分支，多智能体系统( m u l t i a g e n ts y s t e m ， m a s ) 在计算技术和自动化领域都有着深入的研究；动态任务规划由于面对当 前的实际应用需求已受到极大的关注并成为当前研究的热点。机器人救援仿真系 统( r o b o c u p r e s c u es i m u l a t i o ns y s t e m ，r c r s s ) 是一个各类异构智能体之间进 行有效合作的多智能体系统，机器人救援就是满足在复杂、动态等不确定因素下 对救援任务进行合理的规划，在更短的时间里完成更多的救援任务。本文以机器 人救援仿真系统为平台，以实现复杂救援任务的合理规划和最优化实现救援任务 为主要目标，研究复杂救援任务的层次分解、计划协调、以及进行冲突消解和动 态调整的动态任务规划这几个关键问题，使机器人救援仿真系统以尽可能小的代 价获得更高的效益。 1 1 研究背景及意义 1 课题来源 本文课题来源于国家自然科学基金“基于动态分层与自学习的多智能体自 适应协作模型”( 6 0 8 7 4 0 4 2 ) 和湖南省自然科学基金“基于状态预测的多智能体 动态协作模型及其应用研究”( 0 6 j j 5 0 1 4 4 ) 的资助。 2 多智能体系统 近年来，多智能体系统已成为计算机科学与技术领域最广泛的术语和重要研 究内容之一【l ，2 j 。智能体( a g e n t ) 是指驻留在某一环境下能够自主、灵活地执行动 作以满足设计目标的行为实体【3 1 。多智能体系统是指将两个或者更多个相对独立 同时又相互作用的智能体所构成的系统【3 】。当前多智能体系统是分布式人工智能 研究的热点，多智能体系统具有分布式并行处理、强壮性、可伸缩性、可维护性 等特尉4 1 ，适合于求解分布式动态环境下的决策问题，且量应用于分布式计算、系 统仿真、交通控制、电子商务、软件工程等诸多领域。方面，出于对智能体本 身的特性和实际应用需要的考虑，智能体能够通过其自主性、灵活性和交互性等 特点实现自主运行并执行任务，达到对多智能体的任务进行自主的规划【3 ，4 】。另 一方面，由于智能体运行在一个复杂多变的不确定的环境中，其在执行任务的过 程中常常会遇到许多动态变化的情况，例如在实时的环境下执行任务时出现的环 境态势变化、任务的执行前提得不到满足、以及出现新目标任务等不确定因素。 因此要求智能体能够持续感知上下文环境，并随着动态变化的环境和知识信息对 硕+ 学位论文 第一章绪论 整个任务做出快速、稳定和高效的调整，这也是多智能体系统中执行任务时需要 达到的重要目标【3 - 5 i 。 多智能体系统中多个智能体可以是模型结构和功能完全相同的，这种系统称 为同构的多智能体系统；也可以由性质和功能完全不同的智能体组成，每个智能 体可以有不同的子目标，系统的整体目标在各个子目标的实现过程中被实现，这 样的系统称为异构多智能体系统【6 l 。现实中的大部分应用系统都是基于异构多智 能体系统。异构多智能体系统的核心目标之一就是通过个体智能体之间的交互与 协作，把多智能体系统作为整体的问题求解来对待，最终任务的完成能力要大于 各单个智能体所拥有的能力的简单相加之后的总能力，以最短的时间完成任务或 在规定的时间内完成更多的任务【_ 卜9 1 。其主要特征首先表现在多智能体系统中的 智能体可以相互协作，解决单个智能体无法解决的问题；其次多智能体系统可以 通过智能体间的异步并行活动，提高处理复杂任务的质量和效率；同时多智能体 系统松散耦合的特征，保证了其组件的可重用性和可扩充性【9 j 。 3 任务规划 规划是指生成满足当f j 目标集合的动作序列的过程，即在行动之前决定行动 的进程 1 0 j l j 。规划也即给定问题的初始状态和目标状态，以及规划动作的描述， 要求能自动找到一动作序列，使系统能从初始状态转换到目标状态 1 0 , 1 2 】。目标获 取( g o a la c h i e v e m e n t ) 规划是一种常用的规划描述形式，包括问题的所有状态 集合、动作集合、初始状态和目标状态；而分层任务规划是一种层次化分解规划 方法，其问题模型由任务或动作构成的网络表示【l2 1 ，规划过程中将任务合理地进 行分解，确定任务的执行参数和任务间的约束，得到实现顶层任务的各原始任务 的动作序列。 多智能体的任务规划是生成满足多智能体任务目标的动作序列。通过考虑多 智能体在实时动态变化的环境下执行任务时的任务失效情况，同时避免智能体执 行任务发生的潜在冲突，或者在动态变化的情况下仍然满足任务目标的动态序列 性。多智能体的动态任务规划包括任务分解、任务计划协调、动态调整与冲突消 除协调等几个方面。 任务分解就是出现新任务后，获取任务的智能体将其分解为一系列各智能体 可执行的子任务；任务协调指各智能体实现个体任务计划的时间同步与行为协 调，形成多智能体多任务计划；动态调整与冲突消解即各智能体在按照协调好的 计划执行任务的过程中因为动态变化或智能体任务集冲突所造成的任务执行中 断而进行的协调。 异构多智能体系统中的任务规划，需要考虑智能体类型、属性资源和任务特 征等【l3 1 4 j 。由于任务之间的约束关系，智能体之f n j 执行任务的顺序和智能体执行 2 硕士学位论文 第一章绪论 某个任务所需要的执行时间都存在差别【1 5 , 1 6 1 。多智能体系统中的任务规划的主要 优势有以下几点1 9 j ： ( 1 ) 通过任务的并行执行与计划一致缩短整个任务完成的时间 智能体在任务执行过程中通过分工协作并行执行任务，只要满足任务的执行 条件就立即执行任务，减少延迟所带来的时间开销，提高整个任务的完成度。 ( 2 ) 通过对复杂任务的合理分解增加任务成功执行的概率 某些任务因为其本身的复杂性，不能由单个智能体执行，需要通过多次的分 解后才能交给相应的智能体执行，使得任务都能得到执行的机会。 ( 3 ) 通过任务的动态分解增加整个任务在执行过程中的完成度 多智能体系统中的动态复杂不确定因素，造成了智能体执行任务时发生的冲 突与中断，而任务的动态分解则可以增加任务的实时性，解决冲突。 ( 4 ) 通过智能体的任务转包提高任务完成的质量 多个智能体协同执行任务，当一个智能体因为自身或外界条件的变化不能完 成任务时，该智能体的任务可以动态转包给其它智能体，其它智能体仍然可以完 成既定任务i j 。 ( 5 ) 通过资源的相互共享扩展执行任务的能力 单个智能体的能力有限，但多个不同能力的智能体通过合作可以具备完成复 杂任务的能力。 每个多智能体系统都有一个整体目标任务，这个整体目标任务也成为系统中 每个智能体共同的目标任务，智能体为了达到该目标任务，就要一个联合行动， 所以多智能体系统的重要研究问题就是将一个群体所要完成的总目标任务进行 分解并赋予相关智能体，使各个智能体根据总目标并通过相互协作来完成任务。 异构多智能体系统是针对一群不同种类的、自治的智能体的群体行为所进行 的研究，这些智能体可能为同一个目标共同工作，也可能为存在潜在冲突的各自 不同的任务工作【1 8 1 。如何对多智能体系统的任务进行规划，避免任务间的冲突， 提高合作行动的效率，成为多智能体系统的一个重要研究内容，在实际应用中有 着重要的意义。 4 机器人救援仿真系统 机器人救援仿真系统【1 9 ，2 0 1 是一个经典的异构多智能体系统。它是通过模拟现 实生活中的城市中地震、火灾等灾难场景，用各类救援机器人( 即各类救援智能 体) 进行任务救援的仿真系统。此仿真系统的主要目的是使各类救援智能体进行 有效的分工协作，完成营救市民和灭火等紧急救援任务，以减小灾难带来的损失 【2 引。机器人救援仿真系统在全球很多科研机构、学校和社区团队等得到了大量的 研究和开发，并且在r o b o c u p 机器人世界杯比赛中成为越来越备受关注的一项国 3 硕士学位论文 第一章绪论 际性对抗项目 2 2 1 。机器人救援仿真系统的救援任务具有如下特点【2 3 , 2 4 】。 ( 1 ) 系统中救援智能体异构多样性，各智能体之间需要经过相互的协作才 能达到完成某一任务的目的。 ( 2 ) 救援任务复杂，整个救援场景就是一个总任务，需要将救援任务局部 划分，形成相对简单的任务，满足智能体执行任务的需要。 ( 3 ) 救援环境动态变化、救援路况复杂、道路是否畅通不可及时预知、智 能体感知信息有限、通信环境不可靠等。 针对机器人仿真系统的这些特点，救援智能体的决策和规范存在一定的难 度，同时也为设计一支高效的r o b o c u p r e s c u e 仿真队伍的设计带了极大的挑战。 r o b o c u p r e s c u e 仿真比赛系统为异构多智能体系统的研究，特别是任务规划的研 究提供了一个重要的实验平台，机器人救援要解决的关键问题是合理对救援任务 进行实时的动态规划，使得灾难损失尽可能降到最低。通过在此平台的实验和研 究，为救援任务提供一种高效的方法，进一步推动机器人救援仿真系统和分布式 人工智能的发展；为实体机器人救援提供决策和算法支持，促进研究和发展灾难 救援这一现实问题。 1 2 国内外研究现状 近几年，针对任务规划主要集中在任务分解、分配合协调等方面，并且取得 了较大进展。但是，针对多智能体系统任务规划中存在的任务复杂程度大、任务 执行时间要求严格、任务存在动态冲突等特点，如何满足任务简单化，缩短任务 完成时间，消除任务冲突，是一个有待于深入研究的课题。目前国内外学者在任 务规划等方面作了相关的研究，主要工作如下： 1 复杂任务规划 任务规划在很多领域得到了应用。易侃【2 5 】提出基于n a s h 均衡的网格多调度 结点的任务规划方法，能够有效地减轻任务负载。t a o 掣2 6 j 针对异构嵌入式系统 网络提出了一种b e a t a 任务规划算法，该算法引入了“能量一延迟”效能机制， 在节能和任务调度长度上能取得很好的平衡。g o n z a l e z 纠2 7 1 提出了一种基于有穷 状态自动机的r f i d 工作流模型，通过计算不同路径的执行概率来进行任务规划。 龙涛1 2 驯等针对u c a v ( u n m a n n e dc o m b ma e r i a lv e h i c l e ) 分布式控制中的任务协 调问题提出了一种部分全局规划的协商机制，通过p e t r i 网建模方法对执行相关任 务的u c a v 的任务规划进行协调。x i a o 等【2 9 j 提出了针对复杂任务的规划提出了一 种增强的分布式自适应调度算法，该算法能根据任务流进行动态的自适应调整， 且考虑了其他任务对其任务执行的影h 向。高平安等提出了一种基于移动吸引子分 组的任务规划算法，该算法通过萨交遗传算法确定移动吸引子的坐标，利用移动 4 硕士学位论文第一章绪论 吸引子确定未探测任务的分组，将不同的任务组分配给不同的机器人p o 。 z h u a n g 3 l 】分别以最小迁移次数( m n m ) 和最小数据传输( n d t ) 为优化指标对 单个智能体中的智能体路线进行了静态和动态规划，其只考虑系统中只有一个智 能体的情况。上述几种方法都是针对各自具体的应用领域，不具有普遍性；这些 方法没有对复杂任务进行合理的分解，不利于任务本身的可达性、粒度性、动态 柔性等原则，任务的执行效率不高；而且上述方法不能清楚地表示任务之间的约 束和任务分解的层次性，且表现形式也没有得到体现。 2 基于分解的分层任务规划 由于复杂任务规划没有考虑层次性和可达性等原则，有学者提出了基于分解 的分层任务规划。t a n 等【3 2 】提出了利用分层任务分析方法解决多机器协作的任务 分解问题，并将分层任务分析方法应用到工人和机器人的电缆组装任务分解中。 但是在该文只针对具体的应用来进行任务的分解。l o p e s 等 3 3 1 提出了基于a i 协调 无组织多智能体任务分解算法，该方法确保了智能体能够运用自己的能力进行协 作以求解问题。但这些方法不能清楚地表示任务之间的约束，任务分解的层次性 和表现形式也没有得到体现。层级任务网络规划( h i e r a r c h i c a lt a s k - n e t w o r k p l a n n i n g ，h t n ) 的分解方法1 3 4 】在人工智能领域已有重要应用，通过将任务分解 成智能体可以直接执行的子任务，并执行自主规划。张j 下强1 3 5 j 提出了层级任务网 络的卫星自主规划模型与算法，但层级任务网络在图形化表示形式不够具体和完 整，不利于算法实现。刘波等【3 6 】在给出基于多智能体的网络管理框架的基础上， 提出了一种基于任务依赖关系和子任务优先级的任务分解和调度算法，提高时间 效率和减轻网络负载。上面这些任务分解方法，或者任务之间的依赖关系没有作 出具体的解释，或者且其表示形式仅仅是一个简单的有向无环图。 3 基于树结构的任务规划 由于树结构具有很好的层次性和扩展性，又有学者将人工智能的图论等引入 到任务规划中来。曾伟【”】等提出了动作树对智能体的动作规划进行了形式化描 述，v e e r a v a l l i 3 8 1 署1 1 b e a u m o n t 3 9 】等提出了基于分布式多层树结构，研究了任务通 信延迟的可分任务调度问题；d u t o t d o 和林伟伟【4 l 】在树型多处理器计算平台下， 研究了独立相同任务调度问题的复杂性并考虑了计算时间和通信时间的约束。上 述方法所提出的基于有向无环图的层次树任务规划与调度问题，能够很好的表示 任务之间的依赖关系，但是忽略了任务的复杂度，不能满足任务分解的特性。罗 杰文【4 2 】等提出了规划树概念，解释了任务之间的依赖关系并提出了子目标排序算 法，但没有考虑任务本身的与或特性；王汝传1 4 3 】等提出了与或树的协作结构，并 定义了协作结构进程来规划任务的执行。上述几种方法都只考虑了任务预先规 划，不能满足任务的动态实时规划，同时也只考虑了任务之间的依赖关系，没有 5 硕士学位论文 第一章绪论 考虑子任务本身的特点，如任务的执行时间。时间是现实应用中任务的一个很重 要的属性，是衡量任务完成效率的必要因素，因此扩充时序因素，更加符合任务 现实性的需要。 总之，国内外学者在任务规划方面己作了大量的研究工作，并取得了显著成 果，但从相关文献来看，还存在一些关键问题有待解决： 1 目前关于任务规划的研究主要集中在任务分配上，对其之前的任务分解 2 7 , 3 0 1 和任务协t 3 4 , 3 5 1 缺乏充分考虑。通过任务分解可以将复杂任务分解为一系列 智能体可以执行的简单任务，任务本身的执行时间和任务之间的约束关系等是任 务分解中必须考虑的因素，目前许多研究都假设各智能体执行的是相互独立的任 务，忽略了问题的复杂性，偏离了智能体任务执行应用中的实际情况。 2 目前关于多智能体时序约束的研究，主要集中在智能体之间任务执行的 先后顺序，没有考虑具体任务的执行时间和整个任务的完成时间问题【3 7 , 4 2 , 4 3 1 。任 务执行的时间关系到任务本身的一个重要属性，任务的协调往往是考虑任务的执 行时问因素，以最短时间的完成任务或者在规定时间内完成更多的任务。 3 目前多智能体规划大部分是预先任务规划【4 卜4 引，但任务开始后随着环境 态势不断变化，需要通过动态任务规划对受到影响的智能体的任务计划进行调 整。动态任务规划是在任务执行过程中进行，更强调在动态的不确定复杂环境中， 智能体的实时规划能力，比预先规划面临更大的挑战。 1 3 研究内容和组织结构 目前已有的关于任务规划方面的研究成果对复杂任务分解中的约束关系和 任务协调中任务的执行时间方面缺乏充分考虑，而且缺乏足够的动态实时规划能 力。因此，需要对多智能体系统中的任务规划问题深入研究，针对每个问题寻求 对应的解决方法，使其能够适合复杂动态环境的机器人救援仿真系统。 1 3 1 研究内容 本文以机器人救援仿真系统为研究背景，针对动态变化的复杂救援环境，研 究复杂、动态异构多智能体系统中的动态实时任务规划这一关键问题。主要研究 工作如下： 1 任务规划中的分解问题 针对多智能体系统中任务的复杂性和时序约束问题，提出一种基于带权与或 树的任务分解层次规划方法。引入时序约束的带权与或树结构任务分解结构模 型，充分考虑子任务之间的执行时间和时序约束，将复杂任务分解为单个智能体 6 硕十学位论文第一章绪论 能独立执行的子任务。 2 任务规划中的协调问题 在任务协调时考虑到时间因素，提出将时序约束的带权与或树转换为a o e 网的算法进行任务协调，使整个任务的执行保持一致性，以最短的时间完成任务， 达到计划一致协调。 3 任务规划中的动态实时处理与冲突消除问题 针对复杂动态环境下智能体可能存在的冲突和动态变化引起的复杂任务延 迟或中断问题，提出了基于任务转包和动态再分解方法进行冲突消除和动态调整 协调，使整个任务能够继续保持计划一致性，满足任务规划的动态实时性要求。 并在机器人救援仿真系统中验证动态实时任务规划的可行性和有效性。 1 3 2 论文的组织结构 论文的后续章节构成如下： 第二章集中分析机器人救援仿真系统中的任务规划问题。主要包括对机器人 救援仿真系统的各智能体的任务进行具体的说明和解释、对智能体规划形式进行 概要总结、分析器人救援仿真系统中的难点与关键问题并给出解决方案。 第三章针对任务的复杂性和时序约束，对复杂任务进行逐层分解或变换，建 立基于时序约束的带权与或树任务结构模型并就此模型对r c r s s 任务规划问题 进行描述，实现任务分解的层次规划。 第四章针对各智能体任务的计划一致性，对时序约束的带权与或树进行修 剪，然后将时序约束的带权与或树转换为a o e 网，通过a o e 网的关键路径算法 得出各个任务的最早执行时间和完成时间，进行基于a o e 网的最早发生时间的 计划一致协调任务规划。 第五章针对多智能体系统中的任务之间的冲突与动态变化问题，引入任务转 包方法对智能体所承担的任务转包给其他智能体，能根据系统中智能体的实际情 况对任务进行动态再分解，解除任务之问的冲突，满足动态环境的实时性要求， 具有较好的动态性能，实现冲突消除协调和动态调整协调的动态任务规划。 第六章是对论文工作进行总结，并就相关研究工作作出展望。 7 硕士学位论文第二章机器人救援仿真系统中的任务规划研究 第二章机器人救援仿真系统及任务规划问题研究 机器人救援仿真系统是一个实时、动态复杂环境下的异构多智能体系统，一 个健壮、稳定和高效的救援方案主要依赖于一个成功的实时动态任务规划方法。 本章首先介绍机器人救援仿真系统的特点，然后就智能体任务规划的表现形式作 了分析，为设计一个满足机器人救援仿真系统的任务结构模型提供基础支持，对 任务规划中所面临的难点和需要解决的关键问题进行总结，并得出任务分解、计 划协调、冲突消除和动态调整等关键方案，为实现机器人救援仿真系统中的任务 规划提供依据。 2 1 机器人救援仿真系统 机器人救援仿真系统提供了一个完全分布式控制、实时异步的多智能体环 境，通过这个平台，可以测试各种理论、算法和智能体的体系结构，以及研究多 智能体之间的规划与协作问题。 2 1 1 机器人仿真救援系统结构 机器人救援仿真系统是一个实时的分布式仿真系统，其结构如图2 1 所示。 系统是由许多模块通过网络连接起来而构造的，每个不同的模块可以在不同的计 算机上作为一个独立的程序运行，所以计算任务可以分散到许多台计算机上。比 如，倒塌的建筑物和蔓延的大火由专门的子模拟器仿真；救护队和救火队扮演着 不同的几个独立的机器人救援智能体；地理信息系统提供灾难现场最初的条件， 并且监视灾难场地的实时环境；内核管理各个模块和仿真器之间的通信。 图2 1 机器人救援仿真系统结构 8 硕士学位论文 第二章机器人救援仿真系统中的任务规划研究 系统各个部分之间采用t c p i p 和u d p f l p 协议进行通信，由服务器提供一 个地图信息，根据地图的不同来确定智能体的个数和比赛的得分。每个比赛由 3 0 0 个时间周期组成。 ( 1 ) 地理信息系统 提供世界模型的最初配置，其中包括了道路、建筑物、市民和智能体在仿真 过程中的位置，记录仿真的日志。通过内核发过来的消息，进行世界模型的更新， 并且把结果反馈给监视器，以便其进行实时的显示。 ( 2 ) 内核 内核控制整个仿真过程并且促进各个部分的信息共享。在仿真过程中，内核 实时地管理多智能体以及他们之间的通信。把从仿真器接收到的信息进行综合分 析并广播给地理信息系统和仿真器，然后更新仿真周期，通知监视器进行更新。 ( 3 ) 子仿真器 一 由几个不同的仿真域组成，例如：地址、火灾和交通阻塞等。根据仿真器内 部的状态和从内核接收到的信息和命令来计算世界模型中将要发生的事情，包括 智能体的动作，以及他们的动作带来的效果，然后把结果返回给内核。 ( 4 ) 监视器 监视器的目的是方便编程，并且方便调试机器人救援仿真系统这样复杂的系 统，如图2 2 所示为监视器监视的一机器人救援仿真场景。 图2 - 2 机器人救援仿真场景 9 硕士学位论文第二章机器人救援仿真系统中的任务规划研究 2 1 2 机器人救援仿真系统中智能体及其