（计算机应用技术专业论文）基于博弈论的多机器人运动协调.pdf

硕士论文基于博弈论的多机器人运动协调 摘要 经过了半个世纪的发展，机器人技术从理论到应用都取得了很大的成就，其应 用领域涵盖了航空、农业、建筑业、制造业，服务业等各个方面。随着应用领域的 延伸，多机器人系统研究也越来越受到重视。与单机器人相比，多机器人系统具有 灵活、高效以及容错能力强等优势。如何组织由多个机器入构成的群体，以及在这 样的群体中如何实现机器人的协调与合作已成为当前机器入学研究领域的一个新 课题，具有重要的理论和现实意义。本文利用对策论的原理，基于多机器人编队任 务、追捕一逃跑问题对多机器人协调进行研究，具体内容如下： ， 首先，本文对多机器人系统的研究现状进行综述，介绍了多机器人技术的主要 研究内容、目前的热点问题，还有已经取得的一些成果。 其次，阐述了对策论和随机过程的一些基本概念，使用排除法解零和矩阵对策， 使所有的零和矩阵对策都能解得到纯策略解，从而可以指导智能体策略的选择。形 式化描述了多智能体系统的协调协作模型，为实现多智能体系统的协调控制奠定了 基础。 第三，通过构造评价函数，使机器人在队形形成任务能够实现分布式控制，通 过每个机器人独立进行动作决策，使机器人群体达成协调，形成目标队形。进行仿 真试验对算法进行了验证 第四，在群机器人追捕一逃跑问题的对策论模型基础上，重新定义了支付函数， 并根据仿真实验进行了改进，以此作为双方策略选择的数学模型，仿真实验结果验证 了该模型和算法的可行性 本文最后对论文的主要工作进行了总结，并阐述了下一步的研究工作。 关键字：多机器人，对策论，追逃问题，编队问题，势函数 硕士论文基于博奔论的多机器人运动协调 a b s t r a c t a f t e rt h em o t h a nh a l fc e n t u r yd e v e l o p m e n t , r o b o t i c st e c h n o l o g ya n dr e s e a r c h 伽ei n t o 。an e wa g e t h ca p p l i c a t i o nf i e l do fr o b o t i c sh a sc o v e r e dm a n u f a c t u r i n g , 联锻m 删，m i l i t a r ya p p l i c a t i o n , n u c l e a ri n d u s t r ya n dm e d i c a ls e r v i c ec t c a l o n gw i t h t h ea p p 砒i o n 缸l de x t e n s i o n , t h es i n g i er o b o t sl i m i te m e r g e s ，a n dt h em u l t i - r o b o t s y s t e m ( m r s ) b e g i n s 砒岫惦血l gm o r ea n dm o r ea t t e n t i o n c o m p a r e dw i t hs i n g l er o b o t s y s t e m , m r sh a st h ea d v a n t a g eo ff l e x i b i l i t y , e f f i c i e n c ya n dr o b q s m e s s n o w , t h e r e s e a r c ha b o u tm u l t i - r o b o ts y s t e mh a sb o m ean 蹦d i r e c t i o n t h i st h e s i sf o c u s e so n h o wt h er o b o t si ns u c hs y s t e mc o o p e r a t ew i t he a c ho i h e rt oa c c o m p l i s ht a s k f i r s t l y , t h et h e s i sw i l li n t r o d u c et h em r a sc h a r a c t e r i s t i c s ；m a i nr e s e a r c hf i e l d sa n d t h ec u r r e n td e v e l o p m e n to f m u l t i - r o b o tr e s e a r c ha r ec o n c l u d e d s e c o n d l y , w es e tf o r t hs o m eb a s i cn o t i o n so fg a m et h e o r ya n ds t o c h a s t i ct h e o r y , b u i l daf o r m a l i z e dm o d e lo fm u l t i a g e n ts y s t e mi nf r a m eg , l m l et h e o r y , g i v es o m eb r i e f w a y s t o i n t r o d u c e t h e s e t h e o r i e s i n t o t h e r e s e a r c h o f m u i t i - a g e n ts y s t e m t h i r d l y , w ep r o p o s e dad e c e n t r a l i z e dc o o p e r a t i v ec o n l x o l l e rf o rag r o u po fm o b i l e r o b o t s 髓ec o n t r o ld e s i g ni sb a s e do nt h ep o t e n t i a lf u n c t i o nf o r m a l i s m j 1 1 ”a i mo ft h e g r o u pc o n t r o ll a wi st og e n e r a t eaf o r m a t i o ni nag i v e nw o r k s p a c ew h i l ea v o i d i n g o b s t a c l e sa n dc o l l i s i o n s 1 1 把d e s i r e dg o a li ss p e c i f i e di nt e r m so fd i s t a n c ea m o n gt h e i d b o t 8 s o m es i m u l a t i o n s 辨s h o w nt ot e s tt h es t r a t e g y f o u r t h l y , w ec o n s i d e rg r o u pr o b o t sp u r s u i t - e v a s i o np r o b l e m 躯ad i 印涮d y 加m i c g a m ep r o b l e mw i t ht w op l a y e r s t h eu t i l i t yf u n c t i o ni sc o n s t r u c t e dw i t ht h ed i s t a n c e i n f l u e n c ea n de f f 硎v ee n c i r c l e m e n ti n f l u e n c e t h ep a y o f f m a t r i xo f t h ep m s u e ri sg o tb y c o n s i d e r i n gd i f f e r e n ts t r a t e g i e s t h eo p t i m a l 或蹦e g ) ，f o re a c hm o v 锄髓ti so b t a i n e db y r e s o l v i n gt h ep a y o f fm a t r i x s i m u l a t i o ne x p e r i m e n tr e s u l t ss h o wt h ef e a s i b i l i t yo ft h e m o d e la n da l g o r i t h m f i n a l l y , t h eo b t a i n e dr e s u l t sa 托s t m m a r i z e da st h ec o n c l u s i o no f t h et h e s i s , a n dt h e t o p i c sf o rf u r t h e rr e s e a r c ha r ea l s oa d d r e s s e d k e y w o r d ：m u l t i - r o b o tc o o r d i n a t i o n , g a m et h e o r y , p u r s u i t - e v a s i o np r o b l e m , f o r m a t i o nc o n t r o l ，p o t e n t i a lf u n c t i o n 声明 本学位论文是我在导师的指导下取得的研究成果，尽我所知，在 本学位论文中，除了加以标注和致谢的部分外，不包含其他人已经发 表或公布过的研究成果，也不包含我为获得任何教育机构的学位或学 历而使用过的材料。与我一同工作的同事对本学位论文做出的贡献均 已在论文中作了明确的说明。 研究生签名： 掀冬 驴7 年f 月湃日 学位论文使用授权声明 南京理工大学有权保存本学位论文的电子和纸质文档，可以借阅 或上网公布本学位论文的部分或全部内容，可以向有关部门或机构送 交并授权其保存、借阅或上网公布本学位论文的部分或全部内容。对 于保密论文，按保密的有关规定和程序处理。 研究生签名： 凑榕 枷7 年月研日 碗士论文基于博弈论的多机器人运动协调 l 绪论 1 1 引言 随着计算机技术、超大规模集成电路、控制理论、人工智能理论、传感器等技术、 理论及产品的不断成熟和发展，有多学科交叉而形成的机器人学研究也进入了一个崭 新的阶段。从可编程、示教再现型工业机器人到县有一定传感能力、一定适应能力的 机器人，再到配备多种先进传感器，具有较强的适应能力的智能机器人，机器人学的 研究工作经历了从简单到复杂，功能单一到功能多样，从工业制造领域扩展到军事侦 察、核工业、航空航天、服务业、医疗器械、基因工程等各个领域的过程。在可预见 的将来，机器人技术在各个领域的应用将会更加广泛、深入 机器人技术的发展使得机器人的能力不断提高，机器人应用的领域和范围正不断 扩展。小到战胜国际象棋大师的“深蓝”，大到探索火星的“探路者”，以及我国正在 研制开发的深海探测机器入，都要求机器人充当某种角色，执行某些任务。一方面， 人们希望机器人能完成更加复杂的任务，这些复杂的任务由单个机器入很难完成，需 要多个机器人组成的团队相互协调与合作共同完成，这导致了机器人的应用方式从部 件式单元应用向系统式应用的方向发展。另一方面，人们也希望通过多机器人间的协 调与合作，来提高机器人系统在作业过程中的效率，进而当机器人工作环境发生变化 或系统局部发生故障时，多机器入之间仍可通过本身具有的协调与合作关系完成预定 的任务。如何组织由多个机器人构成的群体，以及在这样的群体中如何实现机器人的 协调与合作已成为当前机器入学研究领域的一个新课题，具有重要的理论和现实意 义 。 8 0 年代以来，多机器人系统凭借着比单个机器入更高的精度、刚度、承载能力和 灵活性而进入我们的生活中，从而引起了越来越广泛的重视。随着机器人向系统应用 的方向发展，人们提出了多机器人群体的组织和控制问题，也就是对机器人协调合作 问题，并形成了协作机器人学。多机器人协调合作是多机器人系统的一个重要部分， 可以使多机器人系统将整体优势发挥得淋漓尽致。多机器人系统具有结构灵活、适应 性、生存能力强、功能强大的特点，在军事、航天、服务业等许多领域都有广泛的应 用前景，正确处理好多个机器人之间的协调合作关系是发挥其优势的关键。 硕士论文基于博弈论的多机器人运动协调 1 2 研究意义 所谓多机器人协调合作，是多个机器人通过互相配合，协调自己的行为，从而合 作完成共同目标。 科技日新月异发展的今天，机器人技术的发展使机器人的能力不断提高，机器人 应用的领域和范围正不断扩展，人们希望机器入能完成更加复杂的作业，然而就目前 的机器人技术而言，当机器人在信息的获取、处理及控制能力等方面的作用都是有限 的，对于复杂的工作人物及多变的工作环境，当机器入的能力更显不足，于是入们考 虑有多个机器人组成的群体系统来完成单个机器人无法或难以完成的工作。多机器人 系统正成为机器人技术应用与研究的热点和趋势，多机器入学也正得到不断的发展和 完善。 。 然而多机器人系统并不是简单的将多个机器人糅合到一起，实际上，简单的将 多个机器人堆砌在一起不但不能实现多机器人的优势，反而可能导致多机器人之间 的冲突、对抗，使得整体性能降低。从整体上看，多机器人系统是一个由多个机器 人有机组织而成的复杂非线性离散系统，能够在动态不确定环境下高效的完成更为 复杂的任务。其综合利用了计算机、自动控制、人工智能、通信、传感等领域的理 论和技术。 与单个机器人相比，多机器人系统具有如下特点和优势： 1 系统的功能性更强 为了完成复杂工作，单个机器人往往结构复杂，控制复杂，难以设计或操作，而 多机器人系统具备空间上、时间上和功能上的分布性，多个机器人可以在同一时间处 于不同的位置，也可以在同一时间完成不同的任务，也可以利用众多单个机器人的协 调合作完成一些单个机器人难以完成的工作，比如围捕、地图构建等等，甚至是更为 复杂的任务，提高作业过程的工作效率。 2 系统具有良好的冗余性 当机器人工作环境发生变化。或系统局部发生故障时，多机器人之间通过其内在 的自组织能力及协作机制重新确立协作关系。仍然可以完成预定作业。多机器人系统 的并行性和冗余性可以提高系统的柔性、鲁棒性和容错性等等。 3 系统的柔性更好，工作更加有效 通过多机器人的协调和协作，多机器人系统可以具有较高的工作效率和柔性，更 适合当前先进制造系统对柔性、智能体、网络化等方面的要求，从而全面提高制造业 自动化程度，同时，在军事应用上，多机器人系统通过与实战部队的配合可以以灵活 的方式完成战斗任务，并达到理想的作战效果。 4 系统经济性好 2 硬士论文基于博弈论的多机器人运动协调 对于一些动态性强，而且较复杂的任务，设计和制造多机器人系统远比开发单个 机器人容易，而且价格较低。 由于多机器人系统相对于单机器入系统的更强的优越性，多机器人越来越受到 各行各业的青睐，所以也受到越来越多研究人员的关注。多机器人协调合作技术则 是多机器人系统中一个关键部分，直接关系到系统完成任务的效率、成本和优劣。 在研究和应用双重需求的推动下，多机器人系统、多机器人协调协作的研究已 经成为机器人学研究中的一个充满活力、具有良好应用前景的研究方向。针对多机 器人系统结构、多机器人协调协作等基础理论开展研究是一项具有重要的理论和现 实意义的、具有挑战性的工作。本文对其作了一些有益的尝试 1 3 多机器人系统 1 3 1 多机器人系统的主要研究问题 卜5 】 1 体系结构 实现协作行为必须依赖于某种系统的体系结构。群体结构是集体行为的基础， 决定了系统的能力。 多机器人系统的群体体系结构基本可以分为集中式和分散式两种。分散式结构 又可以迸一步划分为分层式和分布式两种结构。 集中式结构通常有一个主控单元掌握全部环境信息及各受控机器人的信息，对 任务进行协调规划并集中调度，向各受控机器人发布命令，并组织多个受控机器人 共同完成任务。集中式结构的优点在于理论背景清晰，实现起来较为直观，但存在 容错性差，灵活性差，主控机器人与其他机器人之间存在通信瓶颈等缺点。 分布式的结构中没有主控单元，各个机器人之间的关系式平等的，各机器人均 通过通信等手段与其他机器人进行信息交流，自主的进行决策。分层式结构与分布 式结构的不同之处在于前者存在局部集中，它是介于集中式与分布式结构之问的一 种混合结构。分散式结构具有灵活性强和适应性强的优点，但无法保证全局目标的 优化。 2 。通信 通信也是多机器人系统的一个重要研究问题，是研究多机器人系统的基础，多 机器人系统在执行某项任务时，为了实现协调与合作，个体机器人的传感器必须提 供足够的环境描述信息和其他机器人的信息，因此机器人个体之间或者上层控制和 下层合作之问的通信是必要的。 机器人之间的通信方式主要有两种，即直接通信和间接通信。 硕士论文基于博弈论的多机器人运动协调 间接通信是指多机器人系统通过外界环境、自身传感器来获取所需的信息并实 现相互之间的协作，机器人之间没有显式的数据转移或信息交换，因而无法使用一 些高级的协调协作策略，从而影响了其完成某些复杂任务的能力。 直接通信要求发送和接收信息能保持一致性，各机器人之间通过一定的通信机 制有效的进行数据转移及信息交换，而且直接通信时发送方和接收方必须同时在 线。直接通信虽然可以强化机器人之间的协调协作关系，但也存在一些问题：机器 人之间的通信过程延长了系统对外界环境变化的反应时间。一般来说，直接通信存 在于有智能的机器人之间，通信带宽的限制使机器人之间的信息传递、交换出现瓶 颈，随着多机器人系统中机器人数目的增加，通信所需时间大量增加，信息传递的 瓶颈问题越发严重。 间接通信与直接通信是多机器人系统各局特色的两种通信模式，如果将两者各 自的优势结合起来，则可以增强系统的协调协作能力，完成较复杂的任务。利用直 接通信进行少量的机器人之间的上层协作，通过问接通信进行大量的机器人之问的 底层协调，在出现间接通信无法解决的冲突或死锁时，再利用直接通信进行少量的 协调工作加以解决 目前，大部分关于群体机器人的通信主要采用广播的方式，即个体机器人将自 己的位置和传感器信息以及自己从事的工作信息广播出去，其他个体机器入可以按 自己的需要选择信息，或主控机器人通过广播分配任务等。 通信方式的选择是保证通信的有效性和实时性的基本要求，在实际应用中要根 据机器人的结构和任务要求来选择， 3 冲突解决 在多机器人系统中还有一个很重要的问题就是系统中冲突问题的解决。多机器人 系统中冲突的形式是多种多样的，主要有任务冲突、路径冲突和空间冲突等。多机器 人系统中的冲突很容易造成系统的混乱，严重影响了系统的总体性能。解决冲突除了 要有合理的控制结构和通信方式外，还需要相应的解决策略。在多机器人系统中，每 个机器人都把其他机器人当作障碍物来处理，并通过传感器探测障碍物的有无。同时 机器人也根据定期接收到的信息来处理传感器的不确定性，并区分机器人障碍物和非 机器人障碍物，由此选择不同的处理方法。 群体机器人系统冲突问题的解决方法有很多，最直接的是采用集中控制器来决定 所有机器人的无冲突路径，但是这种方法在实用性方面具有一定的缺陷。另一种方法 是主从控制法，将冲突的机器人中的一个作为主控，指挥别的机器人以解决冲突问题。 4 建模 如果机器人对与之协作的其他机器人的意图、行动、能力和状态等进行建模， 可使机器人之问更有效的合作，当机器人具有对其他机器人行为进行建模的能力 4 硕士论文基于博弈论的多机嚣人运动协调 时，对通信的依赖也就降低了，这种建模要求机器人能够具有其他智能体行为的某 种表达，并依据这种表达对其他机器人的行为进行推理。 5 ：学习 如果多机器人系统要在动态多变的复杂环境中完成复杂的任务，它就必须面对 以下几个问题：工作环境的动态性和不确定性；多机器人系统只有有限的通讯能力； 机器人可能面对多个可选择的决策。通过人为的设计和优化来预先解决多机器人系 统所有的问题是不现实的。而且由于系统中环境状态、机器人状态等多种因素综合 在一起使系统状态出现组合爆炸，所以即使可以通过预先规定的方式来解决某些问 题，这种努力也是得不偿失的。所以如何使系统具有依据实际情况选择适当决策、 自动修正控制参数的机制是一个关键问题。学习是使多机器人系统具有这种机制的 一种有效手段。 按照学习机制的不同特点，大致有以下几个类型。 按学习的过程划分，学习可分为两种形式：独立学习和交互学习。独立学习指 单个机器人独立进行的学习过程，不依赖于其他机器人。交互学习指多个机器人共 同进行的学习过程，多个机器人学习如何完成一个共同的目标，其中每个机器人在 追求其自身学习目标的过程中都会受到其他机器人的影响。 按学习的反馈类型来分，学习可以分为：监督式学习，强化学习，无监督式学 习。在监督式学习中，反馈是学习者所期望的行为，学习的目标是尽可能与所期望 的行为相匹配。在强化学习中，反馈是学习者实际行为所获得的收益，学习的目标 就是使学习者的收益最大化。无监督式学习中没有显式的反馈，多机器人系统在试 错的基础上寻找期望的或有用的行为 机器学习的研究是人工智能研究的一个重要方向，其研究成果对于多机器人系 统学习方法有很大的帮助。多机器人系统通过学习可以获得较强的适应性和灵活性 的智能特性。对于个体机器人而言，学习可以改善扩展个体机器人的技巧和能力， 对于多机器人系统而言，学习有助于改善个体之间的一致性和协调性，提高系统的 整体性能 6 协调协作机制 如何实现各机器人之间的协调协作也是多机器人系统研究中的一个重要问题。 多机器人系统的协调协作机制与系统的群体体系结构、感知、通信和学习方面的研 究密切相关。协调协作按主观意愿来划分，可以分为有意识协作和无意识协作，按 协作的类型来划分，可以分成合作型和竞争型 对于多机器人系统协调协作，现在还没有一个统一的定义。总体上讲，协调与 协作反映了在多机器人系统不同层次上对系统控制与交互提出的不同要求。 w a r a u s c h 等在研究中，提出多机器人系统不同层次的协调协作：隐含协作关系， 硕士论文 。 基于博弈论的多机器人运动协调 机器人按其自有的规划模型考虑其他机器人规划的影响；异步协作关系，多个机器 人在同一环境下存在相互阃干涉的条件下为完成各自目标而产生协作；同步协作关 系，多个机器人为完成一个共同目标而产生的协作如图1 3 2 1 所示 副。 图1 3 2 1 多机器人系统不同层次的协调协作 在实际应用中，各层次的协调协作机制并不一定单独存在于系统中，多机器人 系统通常因为任务的需求而包含了多个不同层次的协调协作机制。 1 3 2 多机器人系统的研究现状 自8 0 年代末以来，基于多智能体系统理论研究多机器人协调合作受到了普遍 的关注。随着多机器人系统研究的深入，c e b o t ，s w a f j h ，a c t r e s s 。g o f e r 等实验仿 真系统逐步建立起来。“ 自重构机器人系统s r r ss e l f - r e c o n f i g u r a b l er o b o t i cs y s t e m s ) 是一种典 型的m a r s ( 多智能体) 系统。s r s s 系统以一些具有不同功能的标准模块作为基本 组件。这样一个系统在运行时，可根据目标的需要，对这些模块进行相应的组合， 进而形成具有不同功能的系统。日本名吉屋大学f u k u d a 教授研究的c e b o t 系统就 是一个典型的s r r s 系统。c e b o t 系统将众多功能简单的机器人视为细胞元，根据任 务或环境的变化，细胞元机器人自组织构成器官机器人，再将多个器官机器人组织 成复杂功能的机器人系统。细胞结构机器人系统强调的是单元体的组合如何根据任 务或环境的要求动态重构，因此，系统具有多变的构型，可以具有学习和适应的群 组智能，并具有分布式的体系结构。 群体智能机器人系统是另一种姒r s 系统，它是由许多无差别的自治机器人组 成的分布式系统，主要研究如何使能力有限的个体机器人通过交互产生群体智能。 自然界的蚂蚁、蜜蜂等昆虫群体，个体能力有限，但它们的交互却呈现出了智能行 6 硕士论文基于博弈论的多机器人运动协调 为，通过人工模仿昆虫社会，有助于群体智能机器人系统的研究。比较著名的有 s w a r m 系统 一 此外，欧美一些大学及研究机构的学者也对协作机器人系统进行了研究。协作 机器人系统是由多个具有一定智能的自治机器人组成，机器人之间通过通信实现相 互问的协作以完成复杂的任务。近年来，机器人足球赛由于其对抗性强，对个体之 间协作的实时性要求高，也成为一个具有挑战性的课题。 1 4 本文的主要工作 本文针对多机器人协调问题和追捕一逃跑问题作了一些研究，提出了一些想 法，并进行了实验和仿真。本文完成的主要工作如下： 一 1 、通过大量的阅读中外文献，了解国内外多机器人技术的研究现状，包括其 主要的研究内容、目前的热点问题，还有已经取得的一些成果； 2 、阐述了对策论和随机过程的一些基本概念，使用捧除法解零和矩阵对策， 使所有的2 人零和矩阵对策都能解得纯策略解，从而可以指导智能体策略的选择。 形式化描述了多智能体系统的协作协调模型，为实现多智能体系统的协调控制奠定 了基础。 3 、通过构造评价函数，使机器人在队形形成任务能够实现分布式控制，通过 每个机器人独立进行动作决策，使机器人群体达成协调目标，形成期望队形，并进 行仿真实验验证了该方法的有效性。 4 、在群机器人追捕一逃跑问题的对策论模型基础上，重新定义了支付函数，并 根据仿真实验进行了改进，以此作为双方策略选择的数学模型，仿真实验结果验证了 该模型和算法的可行性。 7 硕士论文基于博弈论的多机器人运动协调 2 对策论 2 1 引言 多机器人系统的协调与协作通常都是通过协商产生的。拥有自主能力的个体机器 人是自利的，其行动目标就是使自己的效用最大化，但当机器人个体要完成全局目标 时，就需要机器人个体在全局目标上建立一致关系。 对策论又称为博弈论( g a m et h e o r y ) ，是一种用来分析策略的数学工具，它研究 一些个体面对一定环境条件，在一定规则下，同时或先后，一次或多次，从各自允许 选择的行为或者策略中进行选择并加以实施，各自取得相应结果的过程。博弈的关键 就是在一定规则下，考虑对方对其策略做出的反应之后而制订策略，这就是一种协商 策略的体现。因而，可以利用博弈论为工具，对多机器人系统的交互行为进行建模分 析。 同时，在博弈过程的纳什均衡状态下，博弈方策略选择集合具有最优特性，通过 对纳什均衡的研究，可以为多机器人系统协作行为选择的最优化提供参考思路。 对策论起源于日常生活中的棋牌、赌博等游戏以及田径、球类等体育比赛，继而 在生物界、经济界、社会学领域等许多方面得到研究。将对策论用于计算机科学中多 智能体的研究，曾经收到许多学者的置疑，他们认为对策论作为一项工具简化了决策 过程中需要考虑的各种复杂的受益函数。然而，正是由于智能体的一些特性，使得它 更适用于做对策论研究的对象。 ( 1 ) 由于已经被计算机化的智能体比自然界、人类社会中的生物个体更容易被 描述，因而它们具备更强的确定性。 ( 2 ) 一般来说，智能体都具备了效用函数来求得最优化效果，相比之，人类自 身的效用度的衡量就非常的复杂，从而分析由智能体参与的博弈过程比那些涉及了人 类决策的博弈过程要简单得多。 ( 3 ) 计算机比人类具备更高的计算精度和更强的计算能力，更适合于博弈过程 中的机械计算。 2 2 对策论的基本概念 2 2 1 对策的基本要素 对策模型的形式可以千差万别，但本质上都必须包括三个基本要素：局中人， 硬士论文基于博弈论的多机器人运动协调 策略集和支付函数【1 羽，记为 g ； f n 1 局中人 在一个对策中，能够自主决定自己行动方案的参加者称为局中人，通常用 n 表示局中人的集合，一个对策至少要有两个局中人。局中人除了可以是一个 自然人外，也可以是一个鹋e n t 、一个机器人、甚至几个相互合作的机器人组 成的联盟。 2 策略集 。 一个对策中，可供局中人选择的一个实际可行的完整的行动方案称为一个 策略，参加对策的每个局中人i 都有自己的策略集s ，f 仨，它是局中人i 的所有策略的全体。我们把对策中每个局中人的策略集中各取一个策略所组成 的策略组合称为对策的一个局势。 3 支付函数 对策的结果由局势唯一确定，或者说一个局势确定了对策的一种结果。对 策的结果又决定了每个局中人的得与失，这种得失称为局中人的支付。显然， 每个局中人的效用都是局势的函数，因此称其为支付函数。 一旦确定了以上三个要素，一个博弈也就随之确定了，博弈论就是系统研究可 以用上述方法定义的博弈问题。寻求各博弈方在具有充分或有限理性、能力的条件 下，合理的策略选择和合理选择策略时博弈的结果，并分析这些结果的经济意义、 效率意义的理论和方法。 一 由于一个完整的博弈必须具备以上三个要素，因此博弈可以从不同的角度划分 成不同的类别。 按参与对策的局中人的数目的多少可以分为：二人对策与多人对策。 按策略来分：如果策略的个数是有限的，则称为有限对策；如果策略的个数是 无限的，称为无限对策。 按策略是否与时间有关可以分为：静态对策与动态对策。 按局中人之间是否合作可以分为：合作对策与非合作对策 2 2 2 纳什均衡 对策论就是关于包含相互依存情况中理性行为的研究。相互依存是指任一局中人 都受到其他局中人行为的影响，同时它的行为也会影响其他局中人。由于相互依存性， 对策的结果依赖于每一个局中人的决策，任何个体都不能单独控制对策进程，也没有 9 顼士论文基于博弈论的多机器人运动协调 任何一个局中人处于孤立的状态。局中人存在首先合作争取最大总体收益，然后从总 体收益中争取最大分量的愿望，因此相互依存导致了局中人间的竞争与合作。理性行 为是指可给局中人带来最大收益的行为，无论该行为是否损害他人。简单的说，理性 行为就是“利己，不管是否损人”的行为。由于局中人的相互依存性，对策中理性的 决策必然建立在对其他局中人反应的预测之上。局中人将自己置身于其他局中人的位 置而预测其他局中人将选取的行动，在这个基础上决定自己最理想的行动，这就是对 策论方法的本质 。 作为其基本均衡概念的纳什均衡是指，在其他局中人的策略选择既定的前提下， 每个局中人都会选择自己的最优策略( 每个局中人的个人选择均依赖于其他局中人的 选择，不依赖的情况只是例外) ，所有局中人的最优策略组合就是纳什均衡。它意味 着，在给定别人策略的情况下，任何一个局中人都不能通过改变自己的策略得到更大 的效用或收益，从而没有任何人有积极性打破这个均衡。换一种说法就是，其中每个 局中人选择的策略是对其他局中人所选策略的最佳反应。 定义2 1 ：在博弈g = ，f e n 中，如果存在由各个博弈方的策略组成 的某个策略组合( i ，) 中，任一博弈方i 的策略s ：，都是对其余博弈方镶略的组合 ，- - ( s ；，l ”，) 的最佳对策，即砷g ，) 嘶( q ，) 对于任何墨墨都成立， 则称( ，z ) 为g 的一个纳什均衡。r 定义2 2 ：在博弈中，局中人i 的策略空间为s = ，) ，则博弈方i 以概率分 布易= ( 易l ”，m ) 随机在其k 个可选策略中选择的“策略”称为一个“混合策略”， 其中o s 办s l ，对_ ，= 1 ，k 都成立，且b l + + p 业= l 。通常我们把策略岛称为纯策 略。 n a s h 在1 9 5 0 年证明了任何对策在混合意义上必然存在均衡。 定理2 1 ：任何有限策略博弈至少存在一个混合意义上的纳什均衡。 7 n a s h 均衡的意义在于，它是关于博弈结局的一致性预测。在纳什均衡状态下，所 有博弈方都预测一个特定的博弈结果会出现，所有的博弈方都不会利用该预测或者这 种预测能力，选择与预测结果不一致的策略，这个预测结果将最终成为博弈的结果。 从另一个方面来说，如果一个策略组合不是纳什均衡，则至少有一个局中人认为，在 其他局中人都遵守这一组合的规定下，他可以比现在得到更多的利益。纳什均衡被认 为是局中入个人理性选择达成一致的结果。博弈过程也是局中入个人理性选择的过 程，当所有局中人预测一个特定的纳什均衡会出现时，这个纳什均衡构成博弈均衡， 即：个人理性选择达成了对均衡的一致性预测。进一步，纳什均衡深刻地揭示了个人 理性与集体理性之间存在的内在矛盾。纳什均衡是理性局中人之间利益冲突与妥协达 到的一种相对稳定的状态，而这种状态没有一个行为主体可以单方面地加以改变 n a s h 均衡最重要的性质是“自我强制性”，如果局中人就纳什均衡结局达成协议， i o 硕士论文基于博奔论的多机器人运动协调 那么不需要任何外力的帮助，他自身就蕴藏着保障实现的力量。任何非纳什均衡的结 局要达成协议都需要外在的强制力量的帮助，否则有的局中人将会有动机背叛协议。 n a s h 均衡也有其固有的缺点，最大的缺点是它不是唯一的，可能存在多个局中人 认为没有差别的均衡策略，因而，如果对策各方选择的不是同一个均衡就不会达到稳 定的均衡状态，即n a s h 并不能保证局中人一定会选择同一个均衡策略。事实上，对策 中n a s h 均衡的数目随局中人策略集的大小的增加成指数增长。存在多个n a s h 均衡 时哪一个会成为现实中出现或理应出现的理性结局是个难以解决的问题。其次，对 于任意对策至今没有统一可行的求解n a s h 均衡的算法，尽管理论上可以求出很多对策 的n a s h 均衡，但这些算法几乎都涉及到大量复杂度很高的非线性规划方程的求解。第 三，很多对策的n a s h 均衡解不是“有效解”或p a r e t o 最优解，很多情况下n a s h 均衡解 不是人们期望的解。如囚徒困境问题。的n a s h 均衡解为( 坦白，坦白) ，结果各判8 年监禁，而有效解( 抗拒，抗拒) 虽不是n a s h 均衡，却能给局中人带来更好的收益。 2 3 零和矩阵对策 如果对策的博弈方始终是对立关系，一方的收益必然来自对方的损失，则称为 零和对策。 求解2 人有限零和对策时，如果鞍点存在，通常用m a x m i n 法求其纯策略解：如果 鞍点不存在，则该对策无纯策略解，此时运用混合策略解法求对策的混合策略解。常 用的混合策略解法( 如线性规划法、特殊矩阵法、迭代法等) 运用起来比较复杂，而 且混合策略的解表示的是使局中人赢得( 损失) 的期望值达到最大( 最小) 时，局中 人选择各种纯策略的概率分布。在局中人双方互相无法了解对方选择某种纯策略的概 率时，混合策略的解直接指导局中人选择自己的纯策略的意义不是很大，也就是说， 局中人最终应选择哪一个纯策略，很难根据混合策略的解做出明确的决定。 针对上述解法存在的不足，本文使用了一种较简单的解法一“排除法”“”“。 对有鞍点和无鞍点的两人有限零和对策统一求解，并可将混合策略纯化，也就是寻求 无鞍点的两人有限零和对策问题的纯策略解，从而克服混合策略解的缺陷，提高解的 实际指导意义 2 3 1 捧除法 所谓“捧除法”，就是局中人按照对自己的不利程度的大小，逐一排除那些可能 会给自己带来较大不利情况的纯策略，直到剩下最后一个策略，这个纯策略就是局中 人最终所选择的纯策略。可见，“排除法”的求解原则是按照对自己不利程度的大小， 利用反向捧除的方法来寻找对策的解。即双方只要求尽可能避开对自己有较大不利的 硬士论文基于博弈论的多机器人运动协调 情况，逐步寻求对自己较为有利的情况，显然，这是一种较为悲观和保守的做法，所 求得的解是一种满意解。 ， “排除法”使用反向排除的方法逐渐避开较大不利的情况，选择出不利程度最小 的情况，m a x m i n 法是先找出局中人的每个纯策略会给自己带来的最大不利情况，再在 这些最大不利情况中找出不利程度最小的情况，若局中人双方在各自这种情况下的赢 得值或损失值相等，则此值为对策的值，它对应的纯策略是双方的最优纯策略，若不 相等则不存在纯策略解，两种解法都是基于悲观原则的解法。 存在鞍点时两种解法所求得的结果是一致的，当存在多个鞍点时，“排除法”的 解是多个鞍点中的一个当不存在鞍点时，按m a x m i n 法没有纯策略解，而“排除法” 仍然能求出纯策略解。这是因为m a x m i n 法多一个关键性的约束条件，即局中人双方在 各最大不利情况中不利程度最小的情况下的赢得值和损失值要相等。实际上，在悲观 原则下，这个约束的必要性并不是很大，因为它忽略了两人有限零和对策问题的基本 假设前提：局中人双方只知道彼此的纯策略集合，而并不知道对方选择某一个纯策略 的概率 在本文中，机器人群体只知道彼此的纯策略集合及其相应的博弈矩阵，但不知道 对方会具体选择某一个纯策略，对于理智的决策者来说，双方都不想冒险，都不会心 存侥幸，都以避开较大不利为决策依据。这种情况下，可解除m a i n t a i n 法这一约束条件， 运用“排除法”求出无鞍点矩阵对策的纯策略解，这只是对策的满意纯策略解，但可 直接指导策略的选取。 “排除法”的具体求解步骤如下： ( 1 ) 写出追捕者的支付矩阵a ，每行代表追捕者的一个策略，而每列代表猎物的 一个策路。 ( 2 ) 在赢得矩阵a 中寻找最小的元素，将该元素所在的行划去，然后在剩下的各 行中寻找最小的元素，再将该元素所在的行划去，依次进行，直到剩下唯一的一行元 素。剩下的一行即为追捕者将选择的策略。 ( 3 ) 同理，对策的另一局中人猎物在赢得矩阵a 中寻找最大的元素，将该元素所 在的列划去，然后在剩下的各列中寻找最大的元素，再将该元素所在的列划去，依次 进行，直到剩下唯一的一列元素。剩下的一列即为猎物将选择的最优策略。 ( 4 ) 4 如果最大( 最小) 的元素，在若干行( 列) 中同时出现，则比较这几行( 列) 中次小( 大) 的元素，若还相等，则比较再次之的元素，直到能比出大小为止，再按 步骤( 2 ) 、( 3 ) 的标记方法依次进行。 ( 5 ) 最后必有一个元素没有被划去，则此元素的值便是对镱的值，此元素对应 的局中人双方的纯策略便是对策的解。 ( 6 ) 如果对于某些特殊的支付矩阵，通过上述步骤可能找不到最小( 大) 值， 硕士论文，基于博弈论的多机器人运动协调 就意味着对于局中人双方来说，按照“排除法”的原则，每个纯策略的不利程度是相 同的，即取任意一行( 列) 都是可行的。实际上，这种情形的n 阶矩阵对策用混合策 略解法求解，可求出局中人双方的混合策略解均为( i n ，。1 n l ，也不具备很大的实 际指导意义。 2 4 随机对策 在多机器人系统中，机器人之阃相互作用并随时间不断变化，系统中每个机器人 都面临一个动态决策问题。在单个机器人系统中，机器人的动态决策其实是一个 i 缸r k o v 决策过程，而在多机器人系统中的m a r k o v 决策过程的扩展形式就是随机对策， 也即是m a r k o v 对策在随机对策中，每一个机器人面对的是一个不同的马尔可夫决策 过程。这些机器人的马尔可夫决策过程通过他们的支付函数以及依赖于机器人联合行 动的系统动态特性交织在一起。随机对策其实也是动态对策的一个分支。【1 8 2 0 在随机对策的一般形式中，对于一个n 个局中人的随机对策，可以由一个多元组 来定义： s ，彳1 ，a “，p ，1 ，) 式中：s 表示有限环境状态集； n 表示对策中局中人的个数； ，表示局中人i 的有限动作集，1 丹； p ：s a x a 2 a ”_ s 表示状态转移函数，它是在当前状态下各个局中人 采取动作时的状态转移概率函数； ，f ：s x a 。_ r 表示局中人i 的支付函数。 我们考虑一个其过程在离散时间点( t = 0 上2 ，) 上是可观测的二人对策来观察 随机对策。在每一个时间点t ，过程状态由毋表示，假设墨是从集合s 中取值，这个过 程是由两个决策者局中人1 和2 分别控制。在状态s ，局中人独立地选取行为口1e a l 和 口2e a 2 ，并分别获取报酬一0 ，4 i ，d 2 ) 和r 2 q ，q l + 口2 ) 。 假设对每一个状态s ，e s ，每个局中人采取行动口1e a 和口2e a 2 从状态s 转移 到s 是与时间无关的。即存在静态转移概率口1e a l 和p ( s i j ，口i , a 2 ) 满足约束条件 口1e 和烈，i j ，一，口2 ) = l 。 在折蜘瞳机对策中，每个局中人的目标是使折扣报酬总额最大，其中折扣因子 卢【0 , 1 ) 由一和矿分别表示局中人l 和2 的策略。对一个给定初始状态s ，两个局中 人从对策中获得如下的支付： v l ( s ，疗1 ，石2 ) = e ( 一i ，r 1 ，万2 ，- - s ) 硕士论文基于博弈论的多机器人运动协调 v 2 ( s ，石1 ，r 2 ) = e ( 2l 石1 ，石2 ，s o = s ) ，i o ( 2 4 2 ) 对二人随机对策的n a s h 平衡点的定义如下所示，假设局中人具有其他局中人支付 函数的完全信息。 定义2 3 ；一个二人随机对策中，一个n a s h 均衡点是对于所有( $ s ) 一个策略 对( 疲，刃) 满足： v l o ，疵，确；v 1 0 ，石1 ，刃) ，v 万1 1 ( 2 4 3 ) 矿0 ，农，才) 一o ，硝，石2 ) ，v ，2e n 2 ( 2 4 4 ) n a s h 均衡点的定义需要每一个智能体的策略都是对其他智能体的最优响应，组成 一个n a s h 均衡点的策略可以是行为策略也可以是静态策略，即假设一个智能体的决策 依赖于当前的状态而不是以前的记录，静态策略也可看作是行为策略的一个简化形 式，下面的定理给出了对于任何一个折扣随机对策在静态策略中中存在一个n a s h 均衡 点。 定理2 2 ：( e 扫f i l a r 和v r i e z e 提出) 每一个折扣随机对策在静态策略中至少具有 一个n 8 s h 平衡点。 2 1 i - - 0 ，1 ( ，)9 2 ( 一) 一( s ) 田 ，2 ( ，) 口 图2 4 1 1 由双矩阵对策形式表示的随机对策 1 4 田函 硬士论文基于博弈论的多机器人运动协调 2 4 1