（检测技术与自动化装置专业论文）多移动机器人协同环境探索策略研究.pdf

山东大学硕士学位论文 中文摘要 随着科学技术的发展，机器人学的研究已经从最初的工业领域拓展到航 空航天、军事等许多不同的领域，其中有些作业环境不适合人类的直接参与， 例如危险的矿井、核废墟等，这就需要机器人在这些未知环境中能够自主地 完成各种智能任务。有效的环境探索是机器人建立环境模型及完成各种复杂 智能任务的关键，在实际应用中具有十分重要的意义多移动机器人系统相 对于单个机器人又具有更明显的优势。然而，多移动机器人环境探索策略的 制定也比单个机器人环境探索策略的选择要困难得多。本文就主要针对多机 器人系统在完全未知的静态环境下的探索策略的选择和协调机制的运用进行 了探讨。 _ 本文首先对移动机器人以及多移动机器人系统环境探索的相关内容以及 研究现状等进行了综述性介绍，并对本文的选题背景和主要内容作了阐述。 其次，很多学者尝试将其他学科的理论引入机器人领域，如市场机制。 本文对此进行了简要介绍，并提出了一种改进的基于多a g e n t 理论的合同网 协议框架的拍卖策略文中对多a g e n t 系统和合同网协议进行了介绍，并将 此思想运用于多机器人系统，让不同的机器人担当不同的角色，实现了分布 式的多机器人环境探索过程。同时证明了此算法具有较高的容错性和鲁棒性。 独立开发的仿真平台为算法的仿真验证提供了很好的平台基础，在平台上可 以模拟机器人探索环境的全过程。在此基础上的对基于多a g e n t 理论的合同 网协议框架的拍卖策略算法的仿真实验，得到了很好的仿真结果。 第三，人工势场是机器人领域应用较为成熟的人工智能算法之一，但是 多应用于路径规划问题的解决中其应用背景多是已知环境而本文则将其 应用于机器人在未知环境的探索过程。在基于栅格地图的完全未知的环境中， 在边界概念的基础上，我们引入人工势场理论。将边界对机器人的引力和障 碍物对机器人的斥力进行定义和量化，并由此确定机器人每前进一步的运动 方向。在单机器人系统中验证了此算法的基础上，又在多机器人系统中引入 山东大学硕士学位论文 机器人之间的排斥力，从而实现了多机器人系统环境探索过程的有效性和多 个机器人之间的协作。此算法与应用组合拍卖等复杂决策算法的方法相比， 在计算量上要小很多，同时探索效率也有相应的提高。在仿真平台上进行的 对算法的仿真实验则验证了基于人工势场理论的机器人环境探索算法的有效 性。 最后，对本论文所做的工作和取得的成果加以总结，并指出需要进一步 研究的工作。 关键词：多机器人；环境探索；多a g e n t ；合同网；人工势场； 山东大学硕士学位论文 r e s e a r c ho nt h ec o o p e r a t i o na l g o r i i 即o f m u it i - r o b o te x p l o r 枷o n ( a b s t r a c t ) w i 也t h ed e v e l o l 舢to f i e n c e 锄dt c c b i l o l o g y m c b o d c sr 船e a r c hh a s b e 懿t 吼d 耐觎匝m 矾f k n l r i n gi n d u s 仃yt om a n yd i 岱册td o 玎1 a i ms u c h 勰 a e s p e & a v i a t i o n ，m i h t a r y 印p l i c a t i 缸d r 0 1 ，o t ss b 肌l dc a n yo u tt h e i r w o r ka u t o 小m m s l yi n m e 豇i v i r o m n e n 忸，w h e 卵h l m l 龃b c i n g sc a nn o t 伽t e r ，f o r c x 锄p l e ，t h eh 配甜d o l 培m i n ea n dm l c l e 啦r e l i c s r o b o 慨s h 训de x p i o t h e v i m 晌地 姐d “咖d i f f e r 锄ti n t e m g c n t 勰bb yt h 伽e l v 髂a u t 删1 删n o l 玛e x p l 硎蛐i 8 让呤 p m i 盯t 勰kf b fm a p b l l i l d i n g 觚dv a r i o 岫i n t e l l i g c et a s l 岱t h l 墙，棚l t o n o m o u s 唧1 0 僦o nh 私i n l p o i t a n tm n i n gi np r a c t i c ea p p l i c a t i o n m o r v e f m u m 莉b o t s y s t 锄h 嬲al o to fa d l 舢t a g e sc 伽p a d t ot h eg i n 出e r o b o ts y s t 锄h o w e v e r t o c h o o s et h e 懿p i o 瑚矗强a l g c 疵t l l mt ot h e 枷城一如b o ts y s t 锄i 8m u c hm 聘d i 伍c l l l t m a nt ot h c 醯n g l m o ts y n 锄ht h i sp a p e r 、e 缸yt o s e 砌t h e 钍p l o 强歧o n a l g o r i t h mo f t h em l l l 吐b o ts y s t e mi nt l l ec 锄p l e t e l ym 出n v na i r o 砌e n ta n d 让幢 c o o p 锄d o na l g c 梳岫b e 撕e e nt h e b o t s f i r s t l y ，t h ei n 伽u c t i o nr e v i e w st h em s e a h m u m - 加b o t 句【p l o 枷o na n di t s 他l a 垃v ea s p t si nl h ew o r l d a n dt h eb k g r d m l d 她dt h em a i nc t e m 8o ft h i s d i s s e r t a l i a r cd e s c r i b e db r i e n y s o n d l y m o 锄dm o 他s e a r c h e 岱a t t 锄p tt o 咖tt h et h l i j l lt h eo m 口 丘e l d st om b o t i c 8 ，跏c h 鹬o n o i n i c s 锄dm 酬k 酬i n gm e c h a 面锄t k sp a p 睇西v ea q u i c ：k 、，i e wa b o u tt h i s ，a n dt h 姐，p ”s e n tan o v d 卸c t i o na l g o r i 岫b 勰e d 蛐t h e c 0 懂l 切_ c tn e tp m t o c o lo fl h em u 城- a g e n tt h e o r y a n 盯t h em d l 比吐o no ft h e 删撕一a g 饥ts y s t 锄锄dt h ec o n t a c tn e tp 加t o c o l ，w eu s et l l i sa l g o r i t l l mt ot h e 删l 虹- r o b o ts y s t 锄l e t1 h cd i f r e r e n t b o t st oa c tt h ed i f f e 坞n tr o l c ，a n dt b i sc 弛 m a k et h ee x p l 啪6 0 nb ead i 蛐r i b 咖ep m 伊e s s m e 瓠1 w h i l e ，t h ea l g o f i t h mi sp v e d t oh a v e 黜t 0 1 删c cm d 加b 咖e s s a no p e ns i m u l a d o np l a 土f o 】mf o rr o b o t 既p l o r a t i i sd e v e l o p e d t os a t i s 母t h e 瑚槐r c hp u r i m s a n dl h ea l g o r i t h m m 咖i e d a b o v e i s u s e d i n l h i s p l a 响m n i s p v c d t o b e e f 鼠石v e m 山东大学硕士学位论文 倔r d l y ，也ep o t 础a l 丘e l dt h c o r yi so n eo f 也em 栅ea n i 丘c i a li n t e l l i g c n t a 1 剃l l l 傩，b u tm o s ta r eu s e di nt h e 胁o no ft h ep a t hp l a i l n i i l ga n do b s t a c l e a v o i 妇e t h eb a c k g r o u n do fa p p l y i n gm o s tp r o b a b l yi sab l o v m 锄瑚n c n t h 刚州e r ，i nt l l i ss n m y i ti su s e di nt h er o b o t 唧1 0 枷o no f t h ec 0 幢i p l e t e l ym 妇o w n 钮、r i l 咖e n t h t h e 瑚h m 忸髓v i l 舶m c n td e s c 曲e d b y t l l e 鲥d m a p ，b 硒e do n t h e c c 印n o ft h e 丘d n t i t l 圮p o t e 耐a l 丘e l dt h e o 巧i s 璐c di nn l i ss t u d y t h e r e p u l s i v e 自田c cf 蛔t b 忙o b s t 1 懿粕dm e 甜廿a c t 伍r c e 丘_ d mt h e 丘o n 蛀e 塔t ot h er o b o t s a g i v e n 饥也锄da 璐e dt od c c i d et h ed i r e c t i o no ft h er o b o ti ne v e 哆s t 印 c o m p 捌t ot h es i 叫昏r o b o t 毋吲弛t h e 砖p l l l s i v ef 0 eb e t w 铷t o wn l b yr o b o t s i sa d o p t e di nl h em l l l t i - 耐b o ts y 髓锄a n d “m i k c st h ec o o p 删d f 硎v ei nt h e m u m 寸o b o t 锣s t e mi n 也e 麟p l o r a 硒np f o g s s c 彻叩a r e d t ot h em e i l l o dt l l a td c c i d 髓 也ed 懿t i i l a l i o ni l s i n gs 锄ec o m p l i c a t e dd i s i o na 1 9 0 r i t l l m ，t l l i sa l g o r i t h mn e e d sl 铭s c o m p u 伽o n ，a n dt h e 中l 训o nc 伍c i e n c yi sa l s o 朋h a 玎c c d m o r v e r t i l c 商艇l l l a t i o n e 】【p e r i m e n t 曲1 0 u t t 1 1 i sa 1 9 0 r i t l l mi 8 a l i z o di i lm ep l a t f o m t 1 坞r e s u l to ft l 璩 池1 1 1 a t i o ni m p r 0 v e s 也ee 伍c i e n to fl h ea l g o r i t h mi ns i n 舀ea n dm u m b o ts y s t e m e 】【p l o m 在o m f i n a l l y ，c o n c l u s i o 璐a r e 百v 硒t hr e c 咖m d a t i o nf o rf i l 咖w o r k k e y w o r d s ：m u l t i - r d b o t ；曲啊r o n m e m 懿p l o r a t i o n ；m u 城- a g t ；c o n t tn c t ；p o t e n t i a l 丘e l d ： 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体已经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名： 弦宝 日 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学校保留或向 国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅；本人 授权山东大学可以将本学位论文的全部或部分内容编入有关数据库进行检索，可 以采用影印、缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：塾盔导师签名：墨豳日期：递z ：缝 l 山东大学硕士学位论文 1 1 引言 第一章绪论 随着机器人技术的不断发展，具有自主感知、决策和执行功能的智能机器 人的研究得到了更广泛的关注，其应用范围已经拓展到行星探索、勘探、搜救、 室内外环境的清洁、农药的喷洒等各个领域，因此人们在智能机器人相关技术 的研究中投入了大量的工作。在许多机器人应用场合，如资源勘测、行星探测、 搜救、危险物品的清理、采矿等，相关的环境信息是事先未知的，在未知的非 结构化的环境中，机器人能够自主有效地完成各种智能任务( 如导航和路径规 划) 的前提是机器人必须能够收集环境信息，逐渐建立起环境地图。环境地图 的有效创建不仅要求有效的探索策略，即如何在最短的时间内得到最多的环境 信息，而且还要求探索策略具有高的可靠性和鲁棒性。 在环境探索和地图创建方面，多机器人系统相对于单个机器人具有明显的 优势，多个机器人并行对环境进行探索，比单个机器人可以更快地覆盖一个未 知区域，具有更高的效率；多机器人系统具有单个机器人所无法比拟的容错性 和冗余能力“】同时，在实际问题中，制作多个具有简单的不同或相同功能的 机器人，远比制作一个具有复杂功能的单个机器人容易得多。因此，在越来越 多的场合，研究人员都尝试应用多机器人系统来实现快速灵活的环境探索。这 不仅可以满足特定场合下对探索效率的要求，而且可以实现环境探索过程的高 鲁棒性。如果有个别机器人停止工作，整个系统仍能保证探索过程不中断。因 而不会对任务的完成造成致命的影响。但是，多机器人环境探索策略的制定要 比单个机器人环境探索策略的选择要困难得多，关键问题是如何协调多个机器 人的行为，才能发挥整个系统的效用，有效地获得环境信息，这也成为了机器 人研究领域的一个较热的方向。 近年来，多机器人协同方面的研究取得了很大的进展，例如：引入经济学 等其他领域和学科的理论原理或方法，引入多种人工智能算法等。涉及到机器 人路径规划、环境探索和地图构建等各个方向。各种方法针对不同的应用背景 都有一定的优点，但同时也有一定的局限性。本文将多a g e n t 系统的相关理论 和人工势场等智能算法引入到多机器人协同环境探索这一研究领域。以建立一 山东大学硕士学位论文 个灵活高效的多机器人分布式系统结构，使之可以实现对未知环境的快速精确 的探索，同时使整个系统具有较高的冗余性和鲁棒性，能够适应多交的甚至是 动态的未知环境。这在多机器人应用日益广泛的军事、工业等各个领域，都具 有非常重要的意义。 1 2 研究现状 1 2 1多移动机器人环境探索的发展历史 多移动机器人协调与多机器人协作系统的发展已经经历了一个较长的历 史自8 0 年代以来，多机器人协调作为机器入应用领域的新方向引起了国内外 学者的关注。1 9 8 7 年在美国圣地亚哥召开的多机器人协调研讨会上，着重提出 了多机器人协调研究的主要问题。1 9 8 9 年，国际杂志r o b o t i c sa n d a u t o n 伽o u ss y s t 鲫专门推出了多机器人协调研究专辑，此外，i 旺e 的机器 人与自动化国际会议从1 9 8 6 年起已将多机器人协调研究列为一个专题组嘲。而 随着机器人在未知非结构化环境中的应用研究的深入，多移动机器人协作系统 在环境探索领域的应用也逐渐受到了人们的关注，并成为机器人领域的研究热 点。 多机器人系统的环境探索最初只是单个机器人的在数量上的简单扩展嗍， 从系统结构上来说，多机器入环境探索系统通常可以分为两类：集中式和分散 式。集中式系统可以得到近似最优解，但是计算量大，并且中央控制器的单点 故障会使得整个系统崩溃。集中式系统的环境探索策略实现的是散布的概念， 即为了有效地探索未知环境，各机器人应当尽量分散开以避免互相影响哪，但 是仅适用于机器人数量较少的情况。分散式系统结构灵活、鲁棒性强，但经常 会得到次优解。 在最近几年，建立在局部无线通讯网络基础上的分布式传感系统在理论和 实验方面都取得了明显进展，其主要特性是功耗低、尺寸小、成本低，适用于 大量的低成本机器人组成的多机器人系统。该领域的研究主要集中在为得到最 大覆盖的传感器的静态排列4 1 ，通讯系统的延迟分析嘲，以及路径规划的有效算 法。分布式无线传感系统的新技术为多机器人系统开辟了一个全新的研究领域， 如r o b o m o t e “1 和m i l l i b o t s 8 1 等低功耗、具有基本传感和短距离通讯能力的多机 2 山东大学硕士学位论文 器人系统研究平台都是基于分布式无线传感技术的多机器人系统。 先前的分散式的多机器人环境探索系统中各机器人之间没有协调，各机器 人独立工作，只有当机器人在通讯范围内时，互相交换地图嘲。在y 鲫a u c h i 提 出边界的概念以前【啪，移动机器人环境探索策略都是简单的沿墙行走“”或随机 行走“2 1 等被动探索策略，只适用于结构化的较小环境，探索效率低。y a 删c h i 提出各机器人建立一个公用占有率栅格地图嘲，并引入了边界的概念 近几年来，随着智能体技术和各种智能算法的开发和发展，这些新思想也 被广泛运用于多机器人协同和机器人环境探索中。在文献“”中，作者将经济 学中的拍卖概念引入多机器人环境探索中，将机器人视为竞标者，将不同的目 标点视为待拍卖物品而另一文献“目中，作者也运用了类似的思想，只是在目 标点的选择过程中，考虑了各机器人之间互相的影响，在代价计算方面做了较 细致的探索。 由于多智能体系统的很多优势逐渐被人们发现，l i a s ( 1 t i _ a g e n ts y s t e m ) 的很多算法和技术也被运用于多机器人协同环境探索中来。例如在文献“川中， 笔者均运用了姒s 的算法，并在不同算法之间进行了比较，也取得了一些不错 的结果。 甚至在很多实际的应用中，多机器人协同环境探索都取得了一些实际的进 展。如文献“町中，在实际的空中机器人和地面机器人之间的协同问题上，作者 做了研究，并在实际试验中验证了其算法的有效性。而文献“”中则关注的是水 下机器人协同探索水下多变环境的问题。 由于多智能体理论、分布式学习理论和机器人控制技术的研究越来越成熟， 多机器人学的发展正面临新的突破。人工免疫学、进化计算、机器学习以及智 能信息处理研究领域近年来迅速发展的粗集理论、古典的凸集和组合学中的超 图理论与多机器人环境探索系统的结合，不仅为多机器人环境探索系统的综合 和分析提供了有力工具，而且赋予机器人群体以自适应能力，使其从相对固定 和人工化的环境走向非结构化的自然环境，拓宽了多机器人的应用领域。这将 在理论上提出一系列新的问题，有力地推动多机器人学的发展，并且在工业、 民用和特种领域( 国防、航天、海洋等) 具有广阔的应用前景。 山东大学硕士学位论文 1 2 2 代表性研究工作 y 绷a u c h i 提出各机器人建立一个公用占有率栅格地图叫，并引入了边界的 概念，接近未探索区域的已知区域定义为边界，每个机器人前往离它最近的边 界获得新信息，各机器人之间除了共享地图信息以外没有协调。这种方法可能 会有机器人又会探索别的机器人已探索过的区域的情况；文献则使用了拓扑 地图。 s i 珊o n s 提出的多机器人环境探索的协调机制啪，该方法基于y 撇u c h i 的 边界概念，各机器人计算一组边界点，计算机器人到边界点的花费和可能的信 息增益，机器人把这些信息提交给中央机器人，该中央机器人根据各机器人的 投标为各机器人分配边界点。这一算法的缺点是整个系统是一个集中式的结构， 其性能完全依赖于中央机器人，中央机器人的单点故障会使得整个系统崩溃。 v a z q u e z 提出的分散式多机器人环境探索方法啪1 ，机器人总是与至少一个 机器入保持通讯，通过与其他机器人的通讯，各机器人能够通过共享目标点实 现协调和最小化重叠，提高了容错性和系统的可扩展性，并且由于行为协调， 避免了次优解；基于行为的多机器人环境探索的体系结构，该分散式体系结构 中的移动传感网通过局部短距离通讯协调，该系统能够对环境探索过程中移动 传感鼹的动态变化作出适当反应，从避免碰撞、鼓励对未知环境的探索和维护 移动传感网的目的出发定义行为，基于当前的不同网络条件选择行为。 m i l l i b o t s 和r o b 鲫o t e 是基于移动传感网的多机器人系统平台，这些平台 主要用于研究在危险环境下如何协调和部署大量的多机器人。r o b o t e 是基于 在未计划的环境下的通讯和协调的移动传感网测试平台，基于该平台，h o w a 州 研究了如何配置增加的传感器“1 。基于该平台的多机器人环境探索仍在研究 中。舭1 l i b o t s 面向各机器人的协同定位，每个机器人都装有超声传感器，各 机器人根据与其他另外三个m i l l i b o t s 的位置检测，进行三边测量。 在a r k i n 的研究中，一组机器人都保持在各自的视线以内，在任一机器人 移动时，其他机器人在原位置不动“订，这样对于系统的资源是极大的浪费，不 能有效地降低探索时间。 4 山东大学硕士学位论文 1 2 3 多机器人协同环境探索中存在的问题 虽然近年来在多机器人环境探索研究中，已经取得了卓有成效的成果，但 我们认为还存在很多问题，在上节中也对这些问题进行了阐述和对比。多机器 人协同环境探索是为随后的机器人定位和构建地图以及后续的其他作业工作打 基础的而未知环境的不确定性甚至是动态性，都给多机器人协同探索环境带 来了很大的难题。采用何种合理有效的环境描述方式将会对后续的探索策略的 执行带来很大影响，直接关系着探索策略的复杂程度，同时对机器人的通信能 力的要求和整个系统的实时性也有很大影响。而探索策略的有效性则是实现任 务要求的关键。近年的研究中，主要存在以下问题： ( 1 )对于探索任务的描述：在机器人环境探索问题中，对于任务的描述 一般都是根据环境描述方式来确定。目前较为成熟的环境描述方式主要有栅 格地图和拓扑地图两种。因而在对探索任务进行描述时也主要局限于此。若 采用栅格地图，则主要任务被描述为确定各栅格是否有障碍物直至环境探索 完毕；而若采用拓扑地图，则主要是建立环境元素间的拓扑关系。如何能建 立一种探索任务描述方式，使这种描述方式既能体现机器人对环境探索的效 率，又能体现出对环境元素和信息的描述的精确程度，这还是个需要进一步 研究的问题； ( 2 )目标点的选择策略：目前的机器人探索的环境比较简单，当面对更 为复杂的动态环境时，存在着搜索空间的组合爆炸问题。随着搜索空间的增 大，求得最优解变得十分困难； ( 3 )基于行为选择的决策理论：在环境探索任务中，对多机器人的角色 分工、群体规范、群体规模等高层次的群体行为与整体绩效的关系，还缺乏 研究。虽然已经开展了大量的工作和进行了大量的试验，也取得了不少成果， 但是都受到了实际应用环境的限制； ( 4 )多机器人坐标间的标定：采用多机器人系统进行环境探索，虽然可 以大大提高探索的效率，但同时也会带来新的问题。由于环境探索常常与环 境建模相联系，同时多机器人之间也需要环境信息的共享，因此多机器人坐 标间的标定是一个非常重要的问题。然而在完全未知的环境中，机器人没有 5 山东大学硕士学位论文 任何关于环境的信息，即使机器人之间有相对位置信息，如何能将各自探索 的各种环境信息统一为同一坐标下的共同描述仍然是个棘手的问题。 近年来，由于信息处理、人工智能、多智能体理论和机器人控制技术研究 的日趋成熟，未知动态环境下多移动机器人环境探索策略的研究正面临新的突 破。本文试图将多a 窖t 领域的相关理论、人工势场等智能算法与现有的移动 机器人环境探索策略相结合，解决多移动机器人环境探索过程中的协同和高效 建模等问题，使多移动机器人系统能够充分的实现个体机器人之间的协作，以 及资源和信息的最大化利用。 1 3 本文选题背景及结构 本文以未知环境下多机器人环境探索为背景，结合山东省科技发展计划项 目“移动机器人协同环境探索系统研究”，研究多a g e n t 领域的合同网理论和 人工智能领域的人工势场法在多移动机器人未知环境探索中的应用，并通过仿 真实验验证算法的有效性。本文主要分为三个大部分，结构安排如下：第一章 为引言部分，对多移动机器人环境探索策略的研究意义、发展历史，以及研究 现状进行了介绍，综述了多移动机器人环境探索过程中的主要问题，并介绍了 本文的研究背景和研究内容。 第二章对多a g e n t 领域的相关知识进行了概述，并对合同网协议算法进行 了详细介绍。同时，引入市场机制，对其中的拍卖算法进行了详细的介绍和对 比，并在此基础上提出了一种基于多a g e n t 理论的合同网协议框架的拍卖策略。 本章中对这一策略算法进行了详细阐述。此算法实现了对多机器人环境探索系 统探索效率的提高，提高了整个系统的容错性和可靠性。而后是在自行开发的 仿真平台环境中对此算法进行了仿真实验，并给出了仿真结果和分析。本章的 最后是内容小结。 第三章则介绍了人工势场的基本原理，以及其在机器人领域的应用。在本 文的研究背景下，本章首先分析了引入入工势场算法的可行性。在基于栅格地 图的完全未知的环境中，在边界概念的基础上，引入人工势场理论，将边界对 机器人的引力和障碍物对机器人的斥力进行定义和量化，并由此确定机器人 6 山东大学硕士学位论文 每前进一步的运动方向在此基础上提出了基于人工势场的机器人协同环境探 索算法介绍了单机器人运用人工势场理论进行环境探索的算法，在此基础上 又在多机器人系统中引入机器人之间的排斥力，从而将算法扩展到多机器人系 统同时实现了多机器人系统环境探索过程的有效性和多个机器人之间的协作。 此算法仍然可以使多机器人系统保持分布式的结构，并提高机器人环境探索的 效率。系统具有较高的鲁棒性和容错性此算法与在每步探索完得到边界后， 再通过一系列决策算法来决定机器人的下一步行进目标的方法相比，在计算 量上要小很多，同时探索效率也有相应的提高。随后，在仿真平台上进行的 对算法的仿真实验则验证了基于人工势场理论的机器人环境探索算法的有效 性。结果随后给出，并进行了分析。章节最后仍然是内容小结 最后，给出了论文的结论，并对相关工作进行了下一步展望。 7 山东大学硕士学位论文 第二章基于多a g e n t 的拍卖策略在多机器人环境 探索中的应用 本章利用基于多a g t 理论合同网协议框架的拍卖策略实现提高多机器人 环境探索问题的效率，首先分析了常用的拍卖算法在多机器人环境探索中应用 的局限，在此基础上，提出利用多a g e n t 理论的合同网协议构建完全分布的多 机器人环境探索的体系结构，提高了整个系统的容错性和可靠性；然后提出改 进的多轮单拍卖算法，完成多个机器人对于多个边界区域的实时有效合理分配， 通过理论分析和仿真实验，说明了该改进的多轮单拍卖算法可以实现多个机器 人的有效协调的目的，但计算量大大减少，并且有可能达到比简化的组合拍卖 更优的效果。 2 1 引言 在许多机器人应用场合，如资源勘测、行星探测、搜救、危险物品的清理、 采矿等，关于环境是事先未知的，在未知的非结构化的环境中，机器人能够自 主有效地完成各种智能任务( 如导航和路径规划) 的前提是机器人必须能够收 集环境信息，逐渐建立起环境地图，环境地图的有效创建不仅要求有效的探索 策略，即如何在最短的时间内得到最多的环境信息，而且还要求探索策略具有 高的可靠性和鲁棒性。 在环境探索和地图创建方面，多机器人系统相对子单个机器人具有明显的 优势，多个机器人并行对环境进行探索，比单个机器人可以更快地覆盖一个未 知区域；多机器人系统具有单个机器人所无法比拟的容错性和冗余能力。但 是，多机器人环境探索策略的制定要比单个机器人环境探索策略的选择要困难 得多，关键问题是如何协调多个机器人的行为，才能发挥整个系统的效用，有 效地获得环境信息，这又成了新的难题。 在y 锄a u c h i 提出边界的概念以前“”，移动机器人环境探索策略都是简单的 沿墙行走“o 或随机行走“”等被动探索策略，只适用于结构化的较小环境，探索 效率低。在文献“帕中，在不断刷新的栅格地图上定义边界为已知开放区域与未 知区域的分界线，机器人通过不断地寻找新的边界，主动地完成未知环境的探 山东大学硕士学位论文 索，提高了探索效率。在文献“1 中，y 舢c h i 将基于边界的方法应用于多机器 人环境探索，各机器人共享感知信息，独自维护各自的全局地图，独自确定其 探索行为，整个系统对于单个机器人故障具有鲁棒性，但由于多机器人之间缺 乏协调，有可能出现多个机器人探索同一个边界的问题，甚至会出现多个机器 人互相妨碍的问题。因此如何通过分配边界来达到多机器人协调探索成为了关 键。许多研究者尝试引入了市场机制。s i 岫o n s 等人咖利用一个中央机器人把各 个机器人根据各自的传感器信息创建的局部地图融合成一个全局地图，各机器 人根据各自传感器的传感距离、精度、到各边界的花费、在各边界可能获得的 信息对各边界进行投标，中央机器入在全局地图的基础上，根据接收到的投标， 从能够获取最大的系统效用( 获取的新信息减去花费) 出发，为各机器人分配 边界，实现多机器人的有效协调，这就能够有效保证各机器人之间相隔足够的 距离，避免了区域重叠，提高了探索效率；但是中央机器人成为整个系统的瓶 颈。 2 2 拍卖算法应用及其缺陷 拍卖是一个源于经济学的概念。一般的定义认为跚1 ：从广义上理解，拍卖 是市场经济价格均衡机制及资源配置的内在过程和本质机理：从狭义上理解， 拍卖是有一定适用范围及特殊规则的市场交易行为它是通过一系列明确的规 则和买者竞价所决定的价格，并以价格来配置资源的一种市场机制；即在确定 的时间和地点，通过一定的组织机构，以公开竟价的形式，将特定物品或者财 产权利转让给最高( 或者最低) 应价者的买卖方式。 近年来，由于拍卖理论的发展和其在资源配置中表现出的优势，它被越来 越多地运用于国民经济的各个方面。例如：政府证券、古玩字画、电力资源等。 特别是在互联网日益发展的今天，网上拍卖也越来越盛行这使拍卖理论的发 展又有了新的空问，并产生了基于移动a g e n t 的拍卖算法 很多研究者将拍卖理论运用于多机器人协同和环境探索中，取得了很多不 错的结果，也引起了越来越多的重视。在文献嘲中，笔者提出了一种p r i m a l l 0 c a t l 0 n 算法，并将这种算法视为一种多轮单拍卖机制作者将目标看作是 标的物，机器人作为竞标者，而拍卖者则是由特定的机器人或者工作站 9 山东大学硕士学位论文 ( w o r k s t a t i o n ) 担当。每个机器人均估算从它当前位置或者从隶属于它的其他 目标点的位置到达标的物位置之间的最小距离，并以此作为报价提供给卖方 ( a u c t i o n e e r ) 卖方收集所有报价，决定报价最低的机器人胜出。在文献“” 中，作者定义了明确的代价函数和收益函数，文中对任务的售出采用的是最高 价密封单物品拍卖( as i n 9 1 e i t e mh i g h e s t p r i c es e a l e d b i da u c t i o n ) 。卖 方公布一个保留价格p r ，p r 是卖方所能接受的最低价格。每个买方机器人均计 算出目标点估价v i ，找出期待的收益，并计算出竞标价。单拍卖虽然解决了多 任务对于多机器人的分配问题，但是仍然有些不足。拍卖者由特定的机器人、 工作站或者虚拟a g e n t 担当，实际上对于整个系统是一个瓶颈。系统无法达到真 正的分布式管理和控制，也就无法保证系统的容错性和鲁棒性。在很多情况下， 不同标的物之间有着各种各样的联系，单拍卖无法考虑这些因素，因此在很多 情况下，无法保证最优的探索质量。 由于以上单拍卖具有这样的缺陷，研究者们又提出了利用组合拍卖理论来 解决多机器人环境探索中的任务分配问题。但是相关的结果还较少，有待进一 步探讨。组合拍卖的中心思想就是允许买方将一组有关联的目标视为一个标的 物进行竞标。例如文献“”，文中采用了单轮密封式组合拍卖。胜者决策采用了 文献1 中的算法。笔者还介绍了几种投标策略，并进行了对比但是由于组合 拍卖算法本身较为复杂，其中的胜者决策问题是个n p 难度的问题，因此需要大 量的计算，在运用到实际过程中还有很多问题需要解决。 2 3 a g e n t 与多a g e n t 系统 通常a g e n t 都被看作是个具有自主性、交互性、反应性和主动性的计算 实体1 ，而多a g e n t 系统，在传统的控制领域以及人工智能领域也成为了研究 的热点。多a g e n t 系统的资源是分散的，计算和任务的执行是分布式的。各a g e n t 之间的任务划分、资源分配、行为的协调，在遵循一定的知识规则和管理策略 基础上，由各a g e n t 通过相互作用和对环境的感知来进行判断和决策。多a g e n t 系统更加适合于开放式动态环境，比传统的控制体系具有更大的灵活性。可以 更充分的利用环境中的各种资源，效率也更高。同时增强系统的并行性、可靠 l o 山东大学硕士学位论文 性、扩展性、可维护性和可重用性。基于这些优点，我们将多a g e n t 体系的思 想运用于多机器人环境探索 2 4 合同网协议及其应用 r a n d a l ld a v i 8 和蹦dgs m i t h 于1 9 8 3 年首先在嘲和嘲文中提出了合同网 ( n t r a c tn e t ) 的概念和思想。问题的提出是针对分布式问题的解决。这种结 构将任务的分配看作是一个交互式的过程是一个将要被执行的任务节点与一 组有能力执行该任务的节点之间的交互。任务分配被看作是一种合同谈判过程。 在合同网中，每个节点有两种角色：管理者( m 锄a g c r ) 或者承包者( c o n h 徼t o r ) 管理者( m 粕a g 盯) 负责监控任务的执行，而承包者( c o n 臼a c t o r ) 则是具体负责 任务的实际执行。每个节点并不是事先设计好为m 缸a g 盯或者劬随c t o r 的，而 只是两种角色任一节点均可动态扮演任一角色。在嘲文中，作者对经典的合 同网进行了改进，结合群体智能提出了一种适应环境及主体能力动态变化的动 态合同网协议并给出了动态合同网协议的算法。经过在多主体平台 m a g e ( m u l t i a g t 衄、r i i 伽m 吼t ) 上的多次试验，证明了动态合同网协议的优越 性。而在嘲一文中，作者提出了另一种扩充的合同网协议的会话策略和一个b d i 精神形成模型，并在此基础上将b d i 模型用于合同网协议，给出了实现合同网 协议的一系列b d i 行为驱动规则。文章在合同网协议的招投标过程中引入了信 任度、稳健度和积极度等精神状态参数，这类参数有助于改善协作质量，从而 使系统具有较好的适应性和灵活性 经典的合同网的不足之处是：忽略了主体之间可能存在的矛盾因而根本 没有考虑到冲突的识别和消解；而且由于所有承包商都可以参加投标，管理器 必须评价大量的投标书，合同网通信开销和资源占用较大。虽然已经提出了一 些改进方法，比如接收者限制，集中选择，基于范例的推理，忽略过期消息等。 但都有一定的缺陷。 2 5 基于合同网的多轮单拍卖策略 2 5 1 目标点的产生 在此文中我们对于环境的描述采用了栅格地图的形式。每个栅格都有一个 山东大学硕士学位论文 与之对应的值，代表了此栅格被占的概率值。同时我们运用了y 锄u c h i 在文献 n 。1 中提出的边界的概念即将已知区域中与未知区域相邻的那些栅格称为边界 栅格，而这些栅格如果连在一起成为一个区域，则称为边界区域。当机器人运 行至边界栅格或者边界区域处时，最容易获得多的对位置区域的新信息。那么 很自然的，我们将此方法借鉴过来，用于确定目标点的产生。当机器人完成一 轮探索后，则会产生一系列新的边界区域。我们即将这些边界区域作为目标点 ( t a r g e t s ) ，并作为下一步拍卖过程中的标的物( b i d s ) 2 5 2 拍卖策略 本文中我们运用了拍卖算法。因为环境探索问题是个动态的问题，因此我 们引用了文献。”中的思想，提出了一种改进的多轮单拍卖策略。起始时刻，本 文中我们均认为机器人是互相知道各自的相对位置的，但是其他信息是不知道 的，需要在后面的过程中进行通信。同时认为机器人之间的通信是可靠的。当 机器人进行了一次探索后，按上节中的方法形成了若干边界区域作为标的物等 待拍卖。所有机器人探索到的边界区域的信息均汇总到当前执行管理者任务的 机器人处，此卖方机器人对每个标的物依次进行拍卖。当一轮拍卖开始时，由 卖方指定一个标的物，所有买方机器人均对此进行投标。每个机器人均计算它 当前的位置或者它已经得到的标的物中的任一标的物位置到当前标的物位置间 的代价值和效用值。与文不同的是，我们根据到标的物的距离给出了在栅格 地图中的代价值和效用值的具体计算方法。其中不仅考虑了距离因素，而且考 虑了各机器人之间的对各自效用值的影响。机器人选择效用值减去代价值之后 的剩余收益最大的一个值作为竞标价进行投标。卖方机器人收集所有标价，决 定收益最大的机器人拥有该标的物，并将结果通知所有买方机器人。然后再开 始下一轮的拍卖。直到所有标的物拍卖完成。 在拍卖完成之后，如果机器人得到了多于一个标的物，则通过t s p 算法( t s p h e u r i s t i c s ) 计算出各自的最佳路径。关于t s p 算法可参考文献瞄1 ，在此不作详 细介绍了。然后机器人按照此最佳路径对环境进行新一轮的探索，并重新更新 所得的环境信息。 山东大学硕士学位论文 2 5 3 代价计算 由于采用了栅格地图的描述方式，我们很容易将代价计算与栅格数联系起 来。在此，我们借用了文献“”中的算法。其中的机器人穿越一个栅格的代价值 与此栅格被占据的概率p 、成正比。最小代价值的计算分成了两步： 蚴j 初始化：被机器人占据的栅格初值赋0 ，其他栅格赋初值一 卜仁徽2 妇一胛砌 亿- ， 循环更新：对于所有的栅格x ，y 都进行代价值的更新 矿。 ，卜是甄杪一舳+ 压百矿p k 。- 舢) ( 2 2 ) 代价值的计算是循环进行的。因为目标点的位置都是明确的，因此必能保 证此算法收敛。那么每个代价值实际上是到达对应目标点的累积的代价值 2 5 4 效用值计算 因为机器人对目标点的效用需要考虑很多因素，因此效用值的计算就显得 很复杂。而且对于机器人到达目标点之后究竟可以获得多少有用信息，在机器 人未到达之前是无法准确预知的。所以，我们只能对效用值进行大致的估计。 并考虑，当一个机器人正在向一个目标移动时，则此目标对于其他机器人的效 用值将会下降【“，且其周围可以被机器人声纳覆盖的区域的效用值也下降。借 鉴文献“。中的思想，我们根据机器人声纳可以覆盖栅格的概率值来计算效用值。 具体算法如下： a 赋初值。对所有边界区域赋相同的初值( l b 计算与指定的目标点f 距离为d 的区域内的栅格的效用值下降程度取一系 列离散的距离值面，畋，以则距离为d 的栅格被机器人声纳覆盖的概率值 p ( d ) 为： 山东大学硕士学位论文 。西甜i l ( t ) 州卜蜀希 ( 2 3 ) 其中：h ( d ，) 为距离d ，被所有机器人计算到的次数。因此当机器人到达目 标点f t 时，离指定目标点f 。距离为d 的栅格f 将会被机器人声纳覆盖的概率值即 为p 似) 。 c 当有n 个边界区域f l ，f 2 ，而其中f l ，岛，f h 已经被分配给机器人1 ，2 ， n l 时，一个边界栅格厶的效用值u 以i ，f ：，乙- ) 可由下式计算： - l 【厂( 乙| ，乞，。_ ) = 一尸( i k 一i ( 2 4 ) 商 由上式可以看出，当同一时刻向厶运动的机器人的数量越多，则厶的效用 值越低。 2 5 5 竞标价的计算 当机器人计算了代价值和效用值后，会产生一个综合考虑两部分因素的竞 标价格。我们将其定义为： e = q ，一口k ! ( 2 5 ) 其中口o ，表示效用值相对于代价值的重要性“”。一般取为1 。基于以上价格， 机器人即可对标的物进行投标了。 2 5 6 角色转换 我们在文中利用了合同网协议，使机器人的角色可以转换。在转换中，我 们可以充分考虑机器人的工作情况，对于拍卖过程中获得大的标的物的机器人 给予一个奖励，并给予一个与奖励值成反比的管理权数值。因为获