（计算机应用技术专业论文）基于马尔可夫决策理论的规划问题的研究.pdf

摘要 摘要 近年来，智能体及多智能体规划问题成为人工智能领域新的研究热点，且有 着广泛的应用前景。本文针对马尔可夫决策过程及其相关理论展开研究，对这些 决策理论在接触现实世界的应用时所面临的问题及解决方法做了一定的探讨，最 后对相关的一类基本决策算法进行了一定的理论分析和改进。 主要涉及到以下几个方面的工作： ( 1 ) 较为系统的研究了与智能体及多智能体不确定性规划相关的几类基础决策 模型及算法。模型部分，首先是最基本的马尔可夫决策模型，然后是在此基 础上加入观察不确定性的部分可观察马尔可夫决策模型，以及进一步加入多 智能体合作的分布式部分可观察马尔可夫决策模型和多智能体对抗的部分 可观察的随机博弈模型。算法部分，针对上述几类模型，均按照后向迭代和 前向搜索两大类进行了对比分析。最后，进一步讨论了与时间抽象相关的半 马尔可夫决策模型及o p t i o n 理论，这一理论是设计分等级的规划框架及算 法的基础。 ( 2 ) r o b o c u p 仿真2 d 提供了一个研究大规模不确定环境下多智能体规划问题的 标准测试平台。结合对该平台的一些必要的说明，分析了在这种接近现实世 界应用的问题中，进行整体规划所需要处理的一些子问题的设计方法，并通 过结合现有马尔可夫决策过程相关理论对这些问题进行建模及分析，给出该 平台更一般的研究意义。 ( 3 ) o p t i o n 理论对应了时间抽象的概念，它为马尔可夫决策理论更多的接触现实 世界应用提供一个分等级规划的研究方向。针对类似r o b o c u p 仿真2 d 这种 带有观察不确定性的大规模多智能体系统的规划问题，在部分可观察随机博 弈模型的基础上，结合策略启发，信念状态压缩，因子化表示法及o p t i o n 理论，给出了一个新的基于动态行为生成器的决策框架，并在此基础上设计 了一个以快速寻找可行解为目标的实时启发式搜索算法。最后，结合仿真 2 d 这一标准平台，对这一决策框架及算法的实用效果进行了检验。 ( 4 ) 基于o p t i o n 的理论分等级规划时，大规模f - j 题中子策略的求解效率也至关 重要。实时动态规划是求解马尔可夫决策过程的一类较新的方法。这类方法 除了具有求解效率上的优势外，还很容易被设计成a n y t i m e 的工作方式。实 时动态规划类i 墓法结合了启发式搜索与值迭代的技术，算法的核心问题是分 支选择策略与收敛判据。分支选择策略决定了值迭代的收敛速度，收敛判据 用以判定解的最优性。通过对启发式函数上界及下界的分析及利用，给出了 一个新的收敛判据，称为最优行动判据，以及一个更适合实时算法的分支选 摘要 择策略。最优行动判据可以更早的标定当前状态满足精度要求的最优行动供 立即执行，而新的分支选择策略可以加快这一判据的满足。并据此设计了一 个有界增量实时动态规划算法( b i r t d p ) 。在两种典型仿真实时环境的实验 中，b i r t d p 显示了比现有相关算法更好的实时性能。最后，通过对算法异 步值迭代机制的研究改进了其在搜索图上处理环的能力，并展示了算法离线 求解效果。 关键词：多智能体马尔可夫决策过程部分可观察随机博弈半马尔可夫决策 过程o p t i o n 机器人足球实时动态规划 i i a b s t r a c t a b s t r a c t i nr e c e n ty e a r s ，a g e n ta n dm u l t i a g e n tp l a n n i n gh a v eb e e nn e wr e s e a r c hh o t s p o t s i nt h ef i e l do fa r t i f i c i a li n t e l l i g e n c ew i t hab r o a dp r o s p e c t i nt h i sp a p e r , t h er e s e a r c h i so nt h eb a s i so fm a r k o vd e c i s i o np r o c e s sa n di t sr e l a t e dt h e o r i e s ，s t u d yt h ei s s u e s a n ds o l u t i o n so ft h e s et h e o r i e sw h e nc o n t a c t 而t ht h er e a l w o r l da p p l i c a t i o n ，p r e s e n t s o m et h e o r e t i c a l a n a l y s i s a n d i m p r o v e m e n t o n ac l a s so fb a s i cm a r k o v d e c i s i o n - m a k i n ga l g o r i t h m t h er e s e a r c hi nt h i sp a p e ri sm a i n l yr e l a t e dt ot h ef o l l o w i n gc o n t e n t ： ( 1 ) as y s t e m a t i cs t u d yo ft h ef o u n d a t i o nm o d e l sa n da l g o r i t h m sr e l a t e dt ot h e a g e n ta n dm u l t i - a g e n tp l a n n i n gp r o b l e mw i t hu n c e r t a i n t i e s a m o n gt h em o d e l s ，f i r s t o fa l l ，i st h em a r k o vd e c i s i o np r o c e s s e sm o d e la st h em o s tb a s i co n e ，a n dt h e ni st h e p a r t i a l l yo b s e r v a b l em a r k o vd e c i s i o np r o c e s s e sm o d e lw h i c ht a k ei n t oa c c o u n to f t h e o b s e r v a t i o nu n c e r t a i n t y , a n df u r t h e ri st h ed e c e n t r a l i z e dp a r t i a l l yo b s e r v a b l em a r k o v d e c i s i o np r o c e s s e sm o d e 丽也m u l t i - a g e n tc o o p e r a t i o nj o i n e da n dt h ep a r t i a l l y o b s e r v a b l es t o c h a s t i cg a m e sm o d e lw i t hm u l t i a g e n tc o m p e t i t i o ni n v o l v e d a m o n g t h ea l g o r i t h m s ，as u r v e ya n ds o m ec o m p a r a t i v ea n a l y s i sa r ec a r r i e do u tf o l l o w i n gs u c h ac l a s s i f i c a t i o nt h a t ，o n ei sab a c k w a r di t e r a t i o nf a s h i o na n dt h eo t h e ri saf o r w a r d s e a r c hf a s h i o n a tl a s t ，f u r t h e rd i s c u s s i o ni sm a d ea b o u tt h es e m i m a r k o vd e c i s i o n p r o c e s s e sm o d e la n dt h eo p t i o nt h e o r yi n v o l v i n gt e m p o r a la b s t r a c t i o n ，w h i c hi s a f o u n d a t i o nf o rt h ed e s i g no fh i e r a r c h i c a lp l a n n i n gf r a m e w o r ka n di t sa l g o r i t h m s ( 2 ) r o b o c u ps i m u l a t i o n2 di sr e g a r d e da sas t a n d a r dp l a t f o r mf o rr e s e a r c ho n m u l t i - a g e n tp l a n n i n gp r o b l e mi nl a r g e s c a l eu n c e r t a i ne n v i r o n m e n t w i t hs o m e n e c e s s a r ye x p l a n a t i o na b o u tt h ep l a t f o r mi t s e l f , a d d r e s sa n da n a l y z et h ed e s i g n m e t h o d so ns o m es u b - p r o b l e mf o rt h eo v e r a l lp l a n n i n gi ns u c hk i n d so fr e a lw o r l d a p p l i c a t i o n b ye m p l o y i n ge x i s t i n gm a r k o vd e c i s i o nt h e o r yt om o d e lt h e s ei s s u e s ， g i v et h ep l a t f o r mm o r eg e n e r a lr e s e a r c hs i g n i f i c a n c e ( 3 ) o p t i o nt h e o r yi n v o l v e s t h ec o n c e p to ft e m p o r a la b s t r a c t i o na n dc a nb e a p p l i e df o rh i e r a r c h i c a lp l a n n i n g ，w h i c hg i v e san e wr e s e a r c hd i r e c t i o nf o rm a r k o v d e c i s i o nt h e o r yb e i n gc a p a b l et oc o n t r a c tm o r ew i t ht h er e a lw o r l da p p l i c a t i o n t o w a r dt h el a r g es c a l em u l t i a g e n tp l a n n i n gp r o b l e mw i t ht h eo b s e r v a t i o nu n c e r t a i n t y l i k er o b o c u ps i m u l a t i o n2 d ，o nt h eb a s i s o ft h ep a r t i a l l yo b s e r v a b l es t o c h a s t i cg a m e s m o d e l ，b yc o m b i n i n gt h et e c h n i q u eo fp o l i c yh e u r i s t i c ，b e l i e fs t a t ec o m p r e s s i o n ， i i i a b s t r a c t f a c t o r e dr e p r e s e n t a t i o na n do p t i o nt h e o r y , g i v ean e wd e c i s i o n m a k i n gf r a m e w o r k w i t hac o n c e p to fb e h a v i o rg e n e r a t o r , a n dd e s i g nan e wr e a l t i m eh e u r i s t i cs e a r c h a l g o r i t h mc o n s e q u e n t l y , w h i c hi sa i m e dt oq u i c k l yf i n daf e a s i b l es o l u t i o no n l i n e f i n a l l y , s h o wt h ep r a c t i c a le f f e c to ft e s t i n gt h e s en e wm e t h o d so nr o b o c u ps i m u l a t i o n 2 da sas t a n d a r dp l a t f o r m ( 4 ) o nt h eb a s i so ft h eo p t i o nt h e o r y , w h e na p p l y i n gh i e r a r c h i c a lp l a n n i n g t o w a r dt h el a r g e s c a l ep r o b l e m ，t h ec a p a b i l i t yo fs o l v i n gs u b p r o b l e me f f i c i e n c yi s a l s oc r u c i a l r e a l - t i m ed y n a m i cp r o g r a m m i n gc o m b i n e st h et e c h n o l o g yo fh e u r i s t i c s e a r c ha n dv a l u ei t e r a t i o nt os o l v et h em a r k o vd e c i s i o np r o b l e m s t h ec o r ei s s u e so f t h ea l g o r i t h md e s i g na r et h eb r a n c hs t r a t e g ya n dt h ec o n v e r g e n c ec r i t e r i o n t h e b r a n c hs t r m e g yi n f l u e n c e st h ec o n v e r g e n c es p e e do fv a l u ei t e r a t i o n ；t h ec o n v e r g e n c e c r i t e r i o ni sa p p l i e dt od e t e r m i n et h eo p t i m a ls o l u t i o n s e v e r a lt y p i c a lc o n v e r g e n c e c r i t e r i o n sa r ec o m p a r e da n da n a l y z e d ，a f t e r w a r d ，an e wo n en a m e dt h eo p t i m a la c t i o n c r i t e r i o na n dac o r r e s p o n d i n gb r a n c hs t r a t e g ya r ep r o p o s e do nt h eb a s i so ft h eu p p e r a n dl o w e rb o u n dt h e o r y t h i sc r i t e r i o ng u a r a n t e e st h a tt h ea g e n tc a na c te a r l i e ri na r e a l t i m ed e c i s i o np r o c e s sw h i l ea no p t i m a lp o l i c yw i t hs u f f i c i e n tp r e c i s i o ns t i l l r e m a i n s i tc a r lb ep r o v e nt h a t ，u n d e rc e r t a i nc o n d i t i o n s ，o n ec a no b m i na no p t i m a l p o l i c yw i t ha r b i t r a r yp r e c i s i o nu s i n gs u c ha ni n c r e m e n t a lm e t h o d w i mt h e s en e w t e c h n i q u e s ，ab o u n d e di n c r e m e n t a lr e a l - t i m ed y n a m i cp r o g r a m m i n ga l g o r i t h mi s d e s i g n e d i nt h ee x p e r i m e n t so ft w ot y p i c a lr e a l t i m es i m u l m i o ns y s t e m s ，b i - r t d p o u t p e r f o r m st h eo t h e r s t a t e - o f - t h e a r tr t d pa l g o r i t h m s f i n a l l y , t h r o u g ht h es t u d yo n t h ea s y n c h r o n o u sv a l u ef f e r a t i o nm e c h a n i s mo fr t d p , i m p r o v ei t sc a p a b i l i t yo f d e a l i n gw i t hc y c l ei nt h es e a r c hg r a p h ，a n ds h o wt h eo f f - l i n ee x p e r i m e n t a lr e s u l t s k e yw o r d s ：m u l t i - a g e n t ，m d p , p o s g , s m d p , o p t i o n ，r o b o c u p ，r t d p i v 图表目录 图表目录 图1 1 决策问题中的信息划分6 图2 1m d p 的基本模型1 4 图2 2 马尔可夫链1 4 图2 3 对给定行动的状态间概率转移图1 5 图2 4 与或图基本结构2 1 图2 5p o m d p 模型。2 3 图2 6p o m d p 决策过程2 4 图2 7 示例信念状态的简单模型2 4 图2 8 状态p o m d p 的一维信念空间2 5 图2 9 状态p o m d p 的一维信念空间2 6 图2 1 0 一棵t - s t e p 策略树2 6 图2 1 l 简单的p w l c 函数和它在信念空间上的划分2 7 图2 1 2 向量被支配的几种情况的示例2 9 图2 1 3p o m d p 上搜索树3 4 图2 1 4 几种模型之间的关系。3 5 图2 1 5 一个部分m a a * 搜索树。4 1 图2 1 6m d p ，s m d p 及结合o p t i o n 的m d p 4 4 图3 1 仿真2 d 平台c s 结构4 7 图3 2 智能体球员的分层设计4 9 图3 3 需进行身份识别的一个示意观察场景。5 1 图3 4 状态空间简化5 8 图3 5 球运行轨迹统计图6 0 图3 6 正态分布x 维的均值与方差6 1 图3 7 正态分布y 维的均值与方差6 2 图3 8 正态分布x 与y 的相关系数6 2 图3 9 采用中垂线的控制段划分6 4 图3 1 0 球员在场上的多边形控制区域6 5 图3 n 采用新的圆形控制区域模型。6 6 图4 1 系统决策流程框图7 2 图4 2 因子化状态表示7 3 图4 3 一个生成的传球行为的例子8 0 图4 4 基于梯度搜索的传球点选择8 l i x 图表目录 图4 5 实时决策中的搜索树8 3 图4 6 启发式函数中的低精度估计8 4 图4 7 单向延伸示例8 6 图5 1 值函数与行动值函数的上下界9 2 图5 2 判据( i ) 和判据( i i ) 的区别9 6 图5 3 一个多步决策问题的例子9 7 图5 4r a c e t r a c kl a r g e b 地图。1 0 1 图5 5 同步值迭代与异步值迭代1 0 4 表2 1 信念状态计算示例2 4 表2 2p o m d p 值迭代算法比较3 3 表3 i 异构参数6 6 表4 1 状态因子取值范围7 2 表4 2r o b o c u p 2 0 0 52 dr e s u l t s 8 8 表4 3r o b o e u p 2 0 0 62 dr e s u l t s 8 8 表5 1 软实时测试l 1 0 1 表5 2 软实时测试2 ：1 0 2 表5 3 硬实时测试1 0 2 表5 4 离线实验数据1 0 5 x 声明 中国科学技术大学学位论文 原创性和授权使用声明 本人声明所呈交的学位论文，是本人在导师指导 = b = c ，进而可虢对闯题做下蚕的分类： l 当a = b = c 时是一个确定性问题。 当a = 转。c 时是一个m d p 闯题。 3 当a = b c 时是一个p o m d p 问题。 m d p 本身既可以处理确定性阀题，也可处理不确定性问题。而p o m d p 在 6 第1 章绪论 m d p 模型上进行了一定扩展，引入了对观察不确定性的处理。从一定意义上也 可以认为，m d p 是p o m d p 的一种极端的情况，即决策相关信息全部可观察。 m d p 及p o m d p 模型中都认为决策的智能镩只有一个，并把其它一切因素 都归于客观环境。这些因素一部分是确定性的知识；另一部分则是已归入统计概 率的不确定性，认为在当前条件下，扶处理阀题筋实际情况出发，不适会再进行 探究，只作概率推理。当一个过程中，有多个智能体同时决策合作来解决一个问 题时，上述模型是否适用的关键因素即其他智能体灼策略是否已知。策略是决策 的结果，指出在过程某个状态要采用哪个行动。如果认为其他智能体策略已知， 无论是确定性的簧略亦或禽概率表示的不确定性策略，那么其他智能体一样可以 归入环境，仍可使用m d p 或p o m d p 模型处理。否则，其它智能体会采用何种 策略也是需要纳入考虑的，在生成智能体自身决策的同时，也要生成其他智能体 的决策，这是其客观过程本身的模型决定的。分布式马尔可夫决策过程 ( d e c m d p ) 及分布式部分可观察马尔可夫决策过程( d e c p o m d p ) 可以处理这类 多智能体合侮闻题。 在现实应用中，多智能体间除了合作也可能存在对抗，这类问题可以归为博 弈。其中本质的区别即智能体闻收益评价的不同。合作类问题，各个智能体有相 同的收益评价，或者说有共同的目标；而博弈类闯题，各个智能体收益评价存在 区别，甚至完全对立。部分可观察的随机博弈( p o s g ) 便是进一步扩展的一个决 策模型，可以处理这类带有不确定性的博弈阏题。 半马尔可夫过程又可以称为非时齐马尔可夫过程，这是相对于一般的时齐马 尔可夫过程丽言的。所谓时齐是指过程鲍每两个相邻状态点阆的时阗闻隔是一致 的，对应决策过程则是每步行动的执行时间是定长的。非时齐则是描述了一类更 一般的情况，对应决策过程中行动的执行时阍并不固定，甚至是时间上麴一个概 率分布。 以上，是本文所涉及的几类与马尔可夫过程紧密相关的决策模型。同时，它 们也构成了本文研究工俸的理论基础。 1 2 3 大规模不确定性规划问题 不确定性规划问题是马尔可夫决策理论的一个主要研究点。而所谓的大规模 规划问题本身并没骞严格的定义，一个决策问题的规模会受其状态空间，行动空 阗，以及霈规划的步数等因素影响。而通常的情况下，谈到大规模规划闷题指的 一般是接近现实世界的应用。 马尔可夫决策领域的奠基入之，l i t t m a n ( 1 9 9 7 ) 有这样的段描述。近些年 来，在不确定性规划领域有大量的形式化的模型及相应的算法被提出。这些模型 看起来在描述现实世界的闻遂上是很有瘸的，两这些算法也显示出在解决趁类目 7 第1 章绪论 题中是有很大希望的。但这种景象下的一个极为缺失的成分是，与应用的真实的 接触。很多算法都被放在一些“证明概念 类的问题进行测试，并且没有可利用 的信息能够说明算法如何向上扩展。现在是一个关键的时期来做出认真的努力将 这些新生的技术应用在现实世界的问题中去；只有通过接触应用才有希望将这一 领域研究的努力集中在最有前途最富有成效的方向。 就现阶段而言，分等级的设计是在大规模规划问题中应用最多的方式。分等 级方法( h i e r a r c h i c a la p p r o a c h e s ) 的目标是减少问题的复杂性( b a r t oe ta l ，2 0 0 3 ) 。其 核心问题是时延行为( t e m p o r a l l y e x t e n d e da c t i v i t i e s ) 的使用，它与子策略，选择 ( o p t i o n s ) ，行为，模式等概念类似。 结合分等级的思想及与半马尔可夫决策过程相联系的o p t i o n s 的理论来设计 大规模多主体规划方法，使现有马尔可夫决策理论能够更好的应用在现实世界的 问题中也是本文研究工作的一个主要目标。 1 3 研究平台 仿真2 d 机器人足球比赛是本文采用的一个主要研究平台。机器人足球比赛 的最初想法由加拿大不列颠哥伦比亚大学的a l a nm a c k w o r t h 教授于1 9 9 2 年正式 提出。随后，m i n o r ua s a d a 、h i r o a k ik i t a n o 和y a s u ok u n i y o s h i 等学者创立了 r o b o c u p 机器人足球世界杯比赛( 最初是t h er o b o tw b r l dc u p 的简称，由于选择 了足球比赛作为背景，因此又被称为t h er o b o tw o r l dc u ps o c c e rg a m e sa n d c o n f e r e n c e s 。1 9 9 7 年，在国际最权威的人工智能系列学术大会一第1 5 届国际人 工智能联合会议( t h e1 5 t hi n t e m a t i o n a lj o i n tc o n f e r e n c eo na r t i f i c i a li n t e l l i g e n c e ， 简称i j c a i 9 7 ) 上，机器人足球比赛被正式列为人工智能的一项挑战。至此，机 器人足球比赛成为人工智能和机器人学的一个标准问题以及公共测试平台。 1 3 1r o b o c u p 的目标 r o b o c u p 的长期目标是：到2 0 5 0 年一支完全类人的机器人足球队能够战胜 当时的人类足球世界冠军队伍( k i t a n o ，1 9 9 8 ) 。从1 9 0 3 年莱特兄弟飞机上天到 1 9 6 9 年阿波罗登月成功花了整整6 6 年；从1 9 4 6 年首台通用电子计算机问世到 1 9 9 7 年深蓝战胜当时的国际象棋世界冠军经历了5 1 年，r o b o c u p 组织也将自身 长期目标的实现定为半个世纪左右的时间。事实上，机器人足球所涵盖的关键技 术的深度及广度，意味着这一目标的实现将基本代表了机器人已可以真正走进人 们的生活。回顾人类历史，第一第二次工业革命，人类分别进入蒸汽时代与电气 时代，使人类从体力劳动中解放出来：第三次工业革命，计算机及网络技术的蓬 勃发展，作为人类智能的延伸，人类进入信息技术时代。展望未来，人工智能技 8 第1 章绪论 术的发展将使人类逐渐从脑力劳动中解放出来，而机器人则是所有这些技术的一 个综合应用所在。做为r o b o c u p 的长期目标，也做为一项极大的挑战，人类是否 能够再次完成这一新的里程碑式的任务，将具有深远的意义。 就近期而言，r o b o c u p 通过其不同项目组为人工智能和机器入学提供了多个 标准的测试平台，可用来检验信息自动化前沿最新研究成果，包括动态不确定的 对抗环境下的多智能体合作、知识表示，实时推理、机器学习和策略获取等当前 人工智能的热点问题以及自动控制、传感与感知融合、无线通讯、精密机械和仿 生材料等众多学科的前沿研究与综合集成。同时与影响范围最广的足球运动结 合，容易受到公众的关注，利于促进了基础研究和实际应用的联系与转化。 1 3 2 仿真2 1 ) 平台特点 r o b o c u p 仿真2 d 提供了一个典型的研究大规模不确定环境下多智能体合作 及对抗问题的测试平台。虽然，其中也会涉及知识表示，机器学习，智能优化方 法等等，但仿真2 d 平台本身的设定决定了其核心研究问题仍是智能体的决策理 论。仿真2 d 所涉及的决策问题的特点主要体现在以下方面： 问题规模超大( 1 a r g e s c a l e ) 一战胜人类世界冠军的深蓝所处理的国际象棋问题的规模约在1 0 e + 2 0 ， 围棋的量级大约是1 0 e + 2 0 0 。 一 而r o b o c u p 仿真2 d 具有连续的状态及行动空间，按粗略离散，其决策 问题的规模在1 0 e + 4 0 0 以上。 多智能体( m u l t i a g e n t ) 一由于队友的存在涉及到合作。 一 由于对手的存在涉及到博弈。 大量不确定因素( u n c e r t a i n t y ) 一行动结果不确定。 一环境部分可观察且存在噪声。 一 队友之间信息不一致。 一对手模型不确定。 实时系统( r e a l t i m e ) 一在每个极短的仿真离散周期内需要作出决策，实际一般为l o o m s 。 1 3 3 仿真2 d 发展回顾 仿真2 d 做为r o b o c u p 最早确定的一个标准测试平台，至今已举办过1 1 界 世界杯比赛。下面对这一平台上的研究队伍使用的技术方法做以简单回顾。 a th u m b o l d t 9 第1 章绪论 a th u m b o l d t 来自德国h u m b o l d t 大学，获得1 9 9 7 年筐界杯冠军。主要特点 是使用了基于范例的推理及面向智能体编程( c a s e b a s e dr e a s o n i n ga n d a g e n t - o r i e n t e dp r o g r a m m i n g ) 的技术。 c m u c m u 是美国卡耐基梅隆大学的球队，曾连续获褥1 9 9 8 年及1 9 9 9 年的世界 冠军，为r o b c u p 2 d 的发展做了大量奠基性的工作。该球队最大特点是提出并使 用了分层学习的理论。其主要设计入p e t e rs t o n e ( 1 9 9 8 ) 在他的博士论文 ( l a y e r e d l e a r n i n gi nm u l t i a g e n ts y s t e m s ) ) 中详细的描述了这支球队。最底层利用神经网 络训练截球行为；在此基础上，第二层利用截球的训练结果学习传球成功率判断， 并以c 4 5 算法构造决策树( q u i n l a nj 1 9 9 3 ) ；最后通过t p o t - r l ( t e a m p a r t i t i o n e do p a q u e - t r a n s i t i o nr e i n f o r c e m e n tl e a r n i n g ) ( s t o n ee ta l ，19 9 9 ) 在 线学习传球对象，t r p t - r l 是用予多智畿体系统延迟反馈的强化学霹方法。我 外，c m u 还使用预测记l | l ( b o w l i n g e ta l ，1 9 9 6 ) 来更新世界模型，实现动态阵型的 柔性角色变换，定位球( 如器外球、球门球) 的固定应对策略( s t o n ep ，v e l o s om ， 1 9 9 8 ) a f cp o r t u g a l f cp o r t u g a l 是由葡萄牙的里斯本大学和波尔图大学合作完成的一支球队，获 彳导2 0 0 0 年世界杯冠军。该球队的特点是使用了大量人类足球的知识，其中最主 要的是对阵型的研究及设计承e i slp ，l a ujn ，2 0 0 0 ) 。f cp o r t u g a l 在c m u 9 9 公 开的底层源代码基础上，引入了球队阵型、战术、角色类型等方面的设计，提出 了基予场上形势的策略站位( s i t u a t i o nb a s e d s v a t r g i cp o s i t i o n i n g s b s p ) ，根据怒 球位置和角色类型等场上形势决定智能体的站位；在同一套阵型内，以 d p r e ( d y n a m i cp o s i t i o n i n ga n dr o l ee x c h a n g e ) 机制实现是色和站位的动态变换； 最后，提出了策略观察机9 1 ( s t m t e g i e l o o k i n gm e c h a n i s m ) 和智能通讯机制来实现 世界模型和决策的多智能体闻的共享。 t s i n g h u a e o l u s t s i n g h u a e o l u s 是中国清华大学球队，曾获得2 0 0 1 年及2 0 0 2 年世界冠军， 2 0 0 3 年世界亚军。球队的主要特点是对某些问题进行数学建模分析，基于数值 计算获得更精确的求解；接体上，a e o l u s 加强了智能体的个人技术，如截球、带 球、传球等并使用t经网络相关的一些技术( 李实，2 0 0 1 ) 。智能体的决策结构 从下到上，首先对所有的可行底层动作都进行分析，然后将分析结果交由评价层 和仲裁层进行评估选择，主要是根据进攻价值、防守价值、成功概率、是否动作 冲突等因素进行分析，这样的结构较好的覆盖了动作备选空间，其选择结果将更 为合理。多智能体的协作则主要依赖于事先设定的规则进行局部合作( 杨帆， l o 第1 章绪论 2 0 0 3 ) 。 u v at r i l e a m u v at r i l e a m 是荷兰阿姆斯特丹大学的一支球队，获2 0 0 3 年世界冠军。该 球队的特点是使用软件工程的思想重新设计代码，最早尝试并成功的使用异构球 员。u v a 实现了一个较完善的底层开发基础( b o e rr ，k o kj ，2 0 0 2 ) ，以几何分析、 数值计算的方法重新实现了大部分底层动作，离线训练最优射门策略( k o ke ta l ， 2 0 0 2 ) ，并对艮。i 从成员的行为进行相互建模；在不依赖通讯的情况下，用协调图 的方法实现多矗能体间的协作( k o ke ta l ，2 0 0 2 ，2 0 0 3 ) 。 s t e p s t e p 是俄罗斯e l e c t r o p u l tp l a n t 研究组织的一支球队，获2 0 0 4 年世界冠军。 s t e p 的特点是引入了场景战术的设计，并使用脚本的方式记录供添加及修改，实 现了场上智能体更为默契的配合。 b r a i n s t r o r m s k a r l s r u h eb r a i n s t r o r m e r s 是德国卡尔斯鲁厄大学的一支球队，也是当今一支 老牌强队，曾获2 0 0 0 年及2 0 0 1 年拶界亚军，2 0 0 5 年及2 0 0 7 年世界冠军。这支 球队的特点是大量的使用了强化学习( r e i n f o r c e m e n tl e a r n i n g ) 的方法( r i e d m i l l e r m ，m e r k ea ，2 0 0 2 ) 。b r a i n s t r o r m 把r o b o c u p 仿真2 d 比赛看成一个部分可观察的 马尔可夫决策问题，在经过一定简化后的模型上使用反馈神经网络来近似来对各 个子问题进行学习。 1 4 主要工作及章节安排 本文以不确定环境下的大规模多智能系统的规划问题作为研究背景，以马尔 可夫决策过程的相关理论为研究内容，以r o b o c u p 仿真2 d 为主要测试平台，主 要工作可以分为四大部分，分别对应了后面的四个章节。 第2 章为相关决策理论及方法的调研及综述。分别介绍了m d p ，p o m d p ， p o s g ( d e c p o m d p ) 及s m d p 这几个与本文工作相关的决策模型。算法部分， 除了s m d p ，其它几个决策模型的求解算法部分都按反向迭代与前向搜索两大类 进行分析介绍。 第3 章为r o b c u p 仿真2 d 实验平台的简单介绍及一些典型子问题的分析与 设计。将这些问题按现有相关马尔可夫决策理论进行建模，并结合其特性给出了 一些解决方法。 第4 章为针对大规模多主体规划问题的模型及算法的研究。提出了一种基于 半马尔可夫理论的分层规划的模型框架，以及在此基础上设计的一个实时启发式 搜索算法，并最后通过在仿真2 d 平台上的测试对其使用效果进行说明。 第1 章绪论 第5 章为针对基本m d p 求解算法本身所做的理论上的改进。分层规划的机 制使得大规模问题的求解效果既依赖于高层算法，也依赖于半马尔可夫过程对应 的各子问题的策略的质量。这一章的工作旨在提高子策略的求解能力。 最后一章为全文的总结及展望。 第2 章马尔可夫决策基础理论 第2 章马尔可夫决策基础理论 内容提要 本章介绍与研究背景相关的几类决策模型及算法。模型部分，首先是最基本 的马尔可夫决策模型，然后是在此基础上加入观察不确定性的部分可观察马尔可 夫决策模型，以及进一步加入多智能体的分布式部分可观察马尔可夫决策模型和 部分可观察的随