（电路与系统专业论文）多机器人协作探索未知环境.pdf

摘要 摘要 2 0 世纪8 0 年代末，随着机器入学、分布式人工智能和分布式系统的研究与 发震，祝器太嚣赣患分布式、系统纯帮智能纯煞方向发震，尤其是多机器夫协作 问题正受到越来越多的燕注。多机器人系统具有结构灵活，适应性强的特点，在 航天航空、国防、工韭、服务业等许多领域都有广泛豹应用前景。其中有些作业 环境不适合人类的直接参与，如危险的矿井、核废墟、深海勘探等，这就需要机 器人在这些未知环境下能够叁主地完成各种任务。合理地设计多机器入系统的协 同机制并使用算法优诧系统，能够发挥多机器入系统的优势，有效地探索未知环 境和构建环境地图，提高团队执行任务的效率，在实际应用中具有重要的现实意 义。 本文以多机器人未知环境探索的协同机制为主菠研究问题，首先对该领域常 舞翡边赛探索算法进行了详细叙述，著分析其挠缺点，然后萼| 窭改进型边赛搽索 算法，在基本算法的基础上增加了对边界角度的考虑，改进了基本算法的探索策 路，撼蔫了规器入团致的探索效率。针对多枧器太系统麴翻驮星标，构造整数规 划模溅，提出了使用蚁群算法进行目标优化，为多机器系统的总体优化提供了 条途径。 本文熬主要工作纛剖新点包括： ( 1 ) 基于效用值的边界探索算法对未知区域的信息进行了复杂的估算，以提 供多机器人之闻的协律。本文提出一种简单静祷俸方法分散度蕊数，可以有 效避免机器人之间的冲突和碰撞，并且简化计算方式，减少对环境信息的依赖。 q 赞对基本边界探索算法孛蘸重复覆盖蠢题，提出改进型边赛探索算法， 同时考虑边界的距离和角度因素，有效地减少了熏复覆盖。 ( 3 ) 针对溺队星标进行优化。原有算法单独为各个机器入分配任务，使用贪 婪算法避免对n p 难问题的求解，容易造成任务分配不均衡闯题，无法实现系统 总体优化。本文将团队遐标构造成整数规划模型，利用蚁群算法进行优化。 通过仿真实验既较了基本算法帮改进算法的探索效率，证翡改进壅边界探索 算法的有效性和优势。 关键字：多极器入、协窝规剖、环境探索、边界探索、毁群算法 中图分类号：即2 4 2 6 第l 炎 a b s l r a c t a b s t r a c t i nt h e1 9 8 0 s ，w i t ht h ed e v e l o p m e n ti nr o b o t i c s ，d i s t r i b u t e da r t i f i c i a li n t e l l i g e n c ea n d d i s t r i b u t e ds y s t e m s , t h er e s e a r c ho fr o b o ts y s t e mh a sb e e nd i r e c t e dt od i s t r i b u t i o n s y s t e m a t i z a t i o n , a n di n t e l l i g e n c e n l ec o o r d i n a t i o np r o b l e m sa m o n gm u l t i - r o b o t s y s t e m sh a v eb e e ne x t e n s i v e l ys t u d i e dr e c e n t l y 强om u l t i - r o b o ts y s t e m s 诚氇醚蠹 f l e x i b i l i t ya n da d a p t a b i l i t yh a v ev a r i o u sp o t e n t i a la p p l i e dd o m a i n ss u c ha sa e r o s p a c e a n da v i a t i o n , m i l i t a r y , i n d u s t r y , s e r v i c e sa n ds oo n r o b o t ss h o u l db ea b l et oc a r r yo u t t h em i s s i o na u t o n o m o u s l y , w h e r eh u m a n b e i n g s c a l ln o te n t e r , f o ri n s t a n c e ，t h e h a z a r d o u sm i l l e ，n u c l e a rr e l i c sa n dr e c o n n a i s s a n c eu n d e rw a t e r i no r d e rt oi m p r o v e t h ep e r f o r m a n c eo fm u l t i - r o b o tt e a m sf o re x p l o r i n gt h eu n k n o w ne n v i r o n m e n ta n d b u i l d i n gu pt h e e n v i r o n m e n tm a pe f f e c t i v e l y , t h ec o o p e r a t i n gm e c h a n i s mo f m u l t i - r o b o tn e e d st ob ed e s i g n e dr a t i o n a l l y , w i t ha p p r o p r i a t ea l g o r i t h mf o rs y s t e m o p t i m i z a t i o n 叭si ss i g n i f i c a n tt ot h er e a l i s t i ca p p l i c a t i o n t h i sp a p e rf o c u s e so nt h ec o o r d i n a t k n gm e c h a n i s mo fm u l t i - r o b o tt e a me x p l o r i n gt h e u n k n o w ne n v i r o n m e n t a tf i r s t , t h e o r i g i n a l f r o n t i e r - b a s e d a l g o r i t h m w i l lb e i n t r o d u c e d 谢也t h ep r o sa n dc o i l s a n dt h e nt h ei m p r o v e df r o n t i e ra l g o r i t h mw i l lb e p r e s e n t e d ，w h i c ht a k e st h eo r i e n t a t i o no ff r o n t i e r si n t oa c c o u n t a sw e l la st h ed i s t a n c e o ff r o n t i e r s i td e v e l o p st h ee x p l o r i n gs t r a t e g yi nt h eb a s i ca l g o r i t h ma n di m p r o v e st h e t e a m sp e r f o r m a n c e a ni n t e g e rp r o g r a m m i n gm o d e lf o rt h et e a mo b j e c t i v e si s c o n s t r u c t e d a n tc o l o n ys y s t e m sa l g o r i t h mi sa p p l i e dt ot h i so p t i m i z a t i o np r o b l e m ，a s a l la p p r o a c hf o rt h es y s t e m o p t i m i z a t i o no f m u l t i - r o b o tt e a m t h em a i ns t u d yw o r ka n da c a d e m i cc o n t r i b u t i o na r e ： ( 1 ) i n s t e a do ft h ec o m p l e xi n f o r m a t i o nc o m p u t i n gm e t h o d 撒t h eu t i l i t y a l g o r i t h m ，as t r a i g h t f o r w a r dm e t h o di sp r e s e n t e df o rc o o r d i n a t i n gt h eb e h a v i o r s b e t w e e nr o b o t s i ti sc a l l e dd i s t r i b u t i o nf u n c t i o n i tc a nb eu s e dt oa v o i dt h ec o l l i s i o n a n dc o n f l i c ta m o n gt h er o b o t s ，i n d e p e n d e n to nt h ee n v i r o n m e n ts t r u c t u r e + ( 2 ) i m p r o v e df r o n t i e ra l g o r i t h mi sp r e s e n t e df o rr e d u c i n gt h er e p e a t e dc o v e r a g e ， ae o r p d l l o np r o b l e mf o rm o s te x i s t i n gf r o n t i e r - b a s e de x p l o r i n gm e t h o d s 。i tt a k e si n t o a c c o u n tb o t l lt h eo r i e n t a t i o na n dd i s t a n c eo ff r o n t i e r , d e c r e a s e st h ep r o b a b i l i t yo f r e p e a t e dc o v e r a g e ( 3 ) o p t i m i z et h et e a mo b j e c t i v e so fm u l t i - r o b o tt e a m 酣l ee x i s t i n gm e t h o d s t e n dt oa s s i g nt a s ki n d i v i d u a l l yf o rr o b o t su s i n gt h eg r e e d ya l g o r i t h m st ob y p a s st h e 第2 黼 a b s l r a c 丁 n ph a r dp r o b l e m s ，w h i c hl e a d st oi m b a l a n c eo fw o r l d o a da s s i g n m e n tf o rr o b o t s 砸s p a p e rc o n s t r u c t sa ni n t e g e rp r o g r a m m i n gm o d e lf o rm et e a mo b j e c t i v e s ，a n du s e sa n t c o l o n ys y s t e ma l g o r i t h mf o ro p t i m i z a t i o n w ec o n d u c ts i m u l a t i o n si nd i f f e r e n te n v i r o n m e n t s ，a n dc o m p a r eo u ri m p r o v e df r o n t i e r a l g o r i t h mw i t ht h eb a s i cm e t h o d r e s u l t sd e m o n s t r a t et h ee f f i c i e n c ya n da d v a n t a g e o f o u rm e t h o d k e yw o r d s ：m u l t i r o b o t ；c o o r d i n a t i o n ；e n v i r o n m e n te x p l o r a t i o n ；f r o n t i e r s ；a n t c o l o n ys y s t e m 第3 页 第1 章引言 第1 章引言 移动机器人的研究始子2 0 世纪6 0 年代末期，斯坦福研究院的n i l sn i l s s o n 采c h a r l e sr o s e n 等天在1 9 6 6 年至1 9 7 2 年串研裁蠢了取名凳s h a k e y 1 酶叁主移 动机器人，目的是研究应用人工糟能技术在复杂环境下机器人系统的自主推理、 燕趔翻控裁。与此同时，最旱豹操侔式步行撬器人瞧硒割成功，然蔼开始了对机 器人步行机构方面的研究，以解决机器人在不平整地域内的运动问题，设计并研 制出了多足步行极器人，其中最著名的是g e n e r a le l e c t r i cq u a d r u p e d 2 的步符机 器人。2 0 世纪7 0 年代米，随着计算杌的应用和转感技术的发展，移动机器入研 究又出现了新的高潮，特别是2 0 世纪8 0 年代中期，设计和制造机器人的浪潮席 卷全落器，一大批璧界著名翡公司开始研剃移动税器入平台，这些移动视器入主 要作为大学实验室及研究机构的移动机器人实验平台，从而促进了移动机器入学 多种研究方囱的出现。2 蹙纪年代戮来，虢磅制高承平静环境信患传感器鞠 信息处理技术、高适应性的移动机器入控制技术、真实环境下的规划技术为标志， 开震了移动祝器入更高层次兹研究。 随着社会生产技术的飞速发展，具有岛主感知、决策和执行能力的智能移动 机器人的研究得到了广泛的关注，其应用范围已经拓展到行星漫步【3 】、侦察【4 】、 搜救【5 l 、室内外环境的清洁【6 】等各个领域。在许多机器人应用场合，如资源勘 测、行星探测、搜救、危险物品的清理、采矿等，相关的环境信息是事先未知的。 在未知的菲结构亿静环境中，机器入麓够爨主有效地完成备释智麓任务( 舞导航 和路径规划) 的前提是机器人必须能够收集环境信息，逐渐建立起环境地图。然 嚣裁鼹前戆祝器入技术水平两言，单视器人在信息的获取、处理爱控制戆力等方 面都悬有限的，对于复杂的工作任务及多变的工作环境，单机器入的能力更曼不 是。予是人们考虑震多个枧器人组成系统通过合作、协调来完成单机器人无法或 难以完成的工作。 多机器人系统不是物理意义上的单个机器人的简单代数相加，其作用效果也 不是摹个视器人作用费线性求和，它应该还包括一个拜线性和昝之努的基于个体 之间相互作用的增量。因此，多机器人系统是指若干个机器人通过合作与协调而 完成某一任务斡系统。当给定多机器天系统菜项任务时，首先面稿的阏题是翔衡 组织多个机器人去完成任务，如何将总体任务分配给各个成员机器人，即机器人 之舞怎样进行有效建合作。当戳菜静祝铡确定了各童魏任务与摺互之间器关系 后，问题变为如何保持机器人间的运动协调一致，郎多机器入协调。 第4 璇 第1 章引富 1 1 多机器人系统的发展 在2 0 世纪4 0 年代中期，g r e yw a l t e r 、w i e n e r 和s h a n n o n 起研究海龟形状 的机器人，这些机器人装备有灯和接触传感器。通过对相互之间动作的反应，这 些简单的机器入显示出“复杂昀社会行力”。 自从2 0 世纪7 0 年代，多智能体的研究在分布式人工智能领域得到重视， 些机器入学魏研究者开始将分布式人工智能( d a i ) 理论癍用到多机器入系统的研 究中。 由予多机器人系统的应用前景非常巨大，美、欧、日等发达国家从2 0 世纪 8 0 年代中期开始就对多机器人系统投入了相当大的研究热情，协作机器入学得 到发展，起初的项目有a c t r e s s 7 、c e b o t 8 、g o f e r 9 、s w a r m 1 0 等。 早期的研究主要以仿真为主，僵近来的研究更强调实际的物理实现。如欧显设立 专门进行多机器人系统研究的m a r t h a 课题“用于搬运的多自主机器人系 统( m u l t i p l ea u t o n o m o u sr o b o t sf o rt r a n s p o r ta n dh a n d l i n ga p p l i c a t i o n ) 。美国海 军研究部和能源部也对多机器人系统的研究进行了资助。国内在该领域的研究工 作很少，只有少数的研究所和大学在进行相关的研究，且大都分的研究工作仍然 停留在仿真和实验室阶段。 2 0 世纪8 0 年代后期，协作多机器人系统的快速发展体现为三个方面的相互 影响：问题、系统和理论。为解决一个给定的润题，想象出一个系统，然后进行 仿真、构建，借用别的领域的理论进行协作。将这些实际应用中多机器人合作所 面l 恣的任务加以抽象，歹薯出了一些代表牲翡任务： 觅食 1 1 ，1 2 ( f o r a g i n g ) 。觅食是多机器人系统经常使用的测试平台，它 可以模拟营救襁搜索、有害废物的清理及矿物质的清理等。 推箱 1 3 1 5 ( b o xp u s h i n g ) 。可以模拟仓库、卡车的装货或卸货。另外它 涉及到多机器人中的任务分配、鲁棒性及通信等闯题的研究。 聚集 1 6 - 1 8 1 和探索【1 9 ，2 0 ( f l o c k i n ga n de x p l o r i n g ) 。尽管这两类任务的实 现方式不同，但它们共同特征是要求多个机器人成员都在环境中来回移动。聚集、 队形保持 2 1 1 及地图翩建都是露一类问题。在探索任务中，要求机器入尽可能稀 疏分布以便尽可能少地重叠。而聚集任务的目标是多个机器人围成一个圈后一起 移动，过去几年中经常研究的围捕是聚集的一个例子。 机器人足球 2 2 ，2 3 ( s o c c e r ) 。机器人足球是近年来兴起的用于研究多智 能体或多机器人合作的优秀测试平台。它要求同一个队伍的机器人在高度动态翔 不确定的环境中进行合作，同时与对方机器人进行对抗。所以，机器人足球是最 复杂的应用平台之一。 第5 贰 第1 章引言 多目标观测 2 4 ，2 5 ( c o o p e r a t i v em u l t ir o b o to b s e r v a t i o no fm u l t i p l e m o v i n gt a r g e t s ，c o m m t ) 。它要求多个机器人合作，尽可能长时间地观察多个移 动磊标，在任意时刻，对每个移动匿标至少有一个机器入进暂观测。 1 2多机器人系统的特点 多机器入系统不是多个机器人的简单堆砌，而是多个机器人的有机组合，它 有效地避免了单个机器人的不足，充分发挥了群体机器人的优势 2 6 ，2 7 。与单机 器人相比，多机器人系统具有以下特点： ( 1 ) 适合完成复杂任务。对予可分解的复杂的任务及大范围魄环境，利用多 机器人系统，可把复杂的任务分解成多个简单的任务，利用多个机器人协调工作， 可以有效遗完成任务，这比单令机器人顺序地完成所有的子饪务要快得多。对未 知的区域建立地图、对某区域进行探雷均属于这类任务。 ( 2 ) 时空分布性。许多任务或应用在时闻、空间和功能上本身就是分布的， 这正好适合于多机器人系统的发挥。 ( 3 ) 功能分布性。在多个机器人中，机器人的功能可以不同，它们的目标任 务不同，但它们可以协调工作。 ( 4 ) 感知分布性。在一个区域较大的环境中，多个机器人分布在环境中，各 鲁感知蠲固的环境，透过共享感知到的信患，大大扩展了祝器入系统对环境豹感 知范围。通过成员之间的信息交换，多机器人系统可以更有效和更精确地进行定 位，这对于野外作业的机器人尤其重要。 ( 5 ) 较高的系统可靠性。采用多机器入系统可以将其中的各个成员设计为完 成某项任务的“专家”，而不是设计为完成所有任务的“通才”，大大降低了单个 机器入设计的复杂度，提高了单个机器人的可靠性。而多机器入的冗余性，也能 提高整个系统的可靠性，不会因为个别机器人的故障导致整个系统的瘫痪。 ( 6 ) 较好的灵活性。开发出灵活性很高的单机器入不仅瓣难面且缀昂贵。嚣 多机器人系统中各个机器人的功能可以互不相同，通过不同功能的机器人的组 合，很容易使多机器人系统具有很强的适应性，可以提供更多的解决方案，因此 可以针对具体情况，优化选择方案。 ( 7 ) 经济性好。对予一些动态性强而且复杂的任务，开发多机器人系统远比 开发单个机器人系统容易，价格较低。 1 。3多机器人系统的应用领域 由于多飙器入系统的优点，使得它的潜在应用领域菲常广泛。 第6 贞 第1 章引言 远地作业 某些应用要求群体自主机器人系统能够自动完成复杂的工作，而人类可以不 时遗从远处进行干预，以改变搡俸过程，弥补机器入的能力不足，与枫器人协作 共同完成复杂的任务。这类应用领域如行星科学探险，在煤矿、火山口等高危环 境下作业以及在水下培育作物等。 协助军事行动 现代战争中使用机器人代替士兵执行危险的饪务能最大限度地减少地面部 队和非参战入员的伤亡。这类任务有排雷、放哨、搜索、追踪及架设通信设施等。 协助灾后搜索与营救 研究表明，被匿在废墟中的幸存者，如果4 8 小时之内得不到有效教助，存 活的可能性几乎为零。这要求城市搜寻和营救人员迅速而高效地寻找和救援幸存 者。然丽，单靠救援人员携带仪器来搜救幸存者，的确显得力不从心。例如汶川 发生的地震，环境的破坏程度超过了现有的营救资源( 搜寻和营救专家、狗和探 测器等) 的能力。由于难以知道大型建筑物破坏的程度，影响了营救人员对该建 筑物进行安全、有效地搜索。有时由于人和狗的体积太大，不能到达要搜索的空 闻，如果能使机器人协助进行这方面的工作，那么将会产生很大的影响。 自动仓库管理 仓库操作人员面临着在降低成本的同时提高对客户的反应速度的竞争挑战。 由于涉及的劳动内容数及设备投资等漂因，指令拣选过程( o r d e rp i c k i n g ) 在配送孛 心是成本最高的作业之一。操作人员依靠人力来进行拣选并借助码垛车或传送带 系统运输物料。将这些作业自动化将会受益匪浅。在仓库管理系统的全局监控下， 自动码垛车在配送中心漫游，并移动到某个停驻在物料通道边的拣选机，运送物 料。这样拣选机就可以专门进行拣选面不需要花时闻来回移动。因此，就可以实 现仓库管理工作的自动化和智能化，提供工作效率。 智能环境 智能环境是指利用计算机来完全改善人类霞常活动的空间。智能环境通过把 计算机和日常现象联系起来，能够使原来处于人一机范围之外的事情相互作用。 这可以应用到智麓房闻和个人助理。许多环境如办公楼、超书、教室及饭瘩很可 能在今后逐渐发展成智能环境。这些环境中，智能体将会监视资源的优化使用， 也会解决资源使用方厦的冲突，智毙体还要跟踪各种资源懿需求。另外，进入环 境中的每个人都会拥有一个智能体，该智能体的目标是为用户优化环境中的条 件。 自动建造 该应用领域涉及大规模结构的装配，诸如高楼大厦、行星居住区或空间设备。 第7 甄 第1 章引宙 将来，多异构机器入系统将会在空间组装大型空间设备，而这对于人类来说是非 常困难的。 宣动化王厂 工厂实现自动化是发展趋势。为了增加产量、减少劳动成本，提高效率、安 全性及总体质量，越来越多的产业在寻求生产自动化设备。这要求有高效、高鲁 棒性的异构多机器人系统的协作。 农业机器入 在艰苦条件下的重体力劳动、单调重复的工作，如喷洒农药、收割及分选作 物等有望由多农业机器人系统完成，以解放出大量的人力资源。 1 4多机器人系统的体系结构 体系结构是多机器人系统的高层部分和基础，多机器人之间的协作机制就是 通过它来体现的。它决定了多机器入系统在任务分解、分配、规划、决策及执行 等过程中的运行机制以及系统各机器人成员所担当的角色，如各机器入成员在系 统中的相对地位如何，是平等、自主的互惠互利式协作还是有等级差别的统筹规 划协调。从系统设计的角度而言，系统结构要有利于个体能力最大程度昀发挥和 任务的高效完成。另外，协作机器人系统面向的是动态变化的环境，因而系统结 构要对环境具有鲁适应能力。 l 。4 1 控制结构 多移动机器人控制结构分为集中式( c e n t r a l i z e d ) 、分散式( d e c e n t r a l i z e d ) 和分 布式( d i s t r i b u t e d ) - - - 种。 集中式控制结构系统 2 8 】由一个总控机器人对整个系统进行规划和决策，而 其他机器人只包括传感器、执行器鬻通信设备。每个机器入收集到的数据都发送 给控制中心来控制。它是一种规划与决策的自上而下t o p d o w n 式的层次控制结 构，其层的数量和复杂性决定了系统响应所需的时闻和行为决策的质量。集中式 结构的协调效率比较高，减少了用于协商的开销，最突出的优点是可以获得最优 规划，但难以解决计算量大的闽题，实时性、动态性较差，总控机器人的负担过 重，系统内的机器人没有很好地体现自主性和智能性。 分散式控制结构【2 9 】中各机器人具有高度自主翻治能力，各智能体自行处理 信息、自行规划与决策、自行执行自己的任务。与其它智能体相互通讯以协调各 自行为而没有任何集中控制单元。这种结构较好地模拟了自然社会系统，具有反 应速度快、灵活性高、适应性强等特点。僵对通讯要求较高，且多边协商效率较 第8 页 第1 章弓i 言 低，难子得到全局最优的方案。 图1 - 1 集中式结构 髓1 - 2 分散式结构 分布式控制方式【3 0 】介于上述两者之闻，是一种全局上各机器入等同盼自主 分布式分层结构而局部集中的结构方式。这种结构方式是分散式的水平交互和集 中式的垂直控制相结合的产物，既提高了协调效率，又不影晚系统的实时性、动 态性、容错性和扩展性。 1 4 2 通讯结构 ( 1 ) 智能俸间没有精确的通讯或相互作用，仅仅是在共享环境( 实际上是共 享内存) 的基础上以环境为媒体作最简单、最有限的相互作用。 0 ) 基于传感器信惠的智能体闻相互作用，也就是，智能体闻同样没有精确 的通讯，而是通过传感器的相互检测获取对方信息，产生局部的相互反应，它要 求智能体能识别其它个体，并区别于环境串的其它物体。这种方法多用于诸如 f l o c k i n g ，p a t t e r nf o r m a t i o n 的集体行为。 ( 3 ) 智能体闻存在精确通讯，用点对点、b 1 a c k b o a r d 或b r o a d c a s t 式传递信 息。这种通讯结构类似予网络，因此涉及到许多标准的网络问题，如网络拓扑结 构和通讯协议的设计等。 第9 员 第1 章引言 1 5一些典型的多机器人系统 经过2 0 多年的发展，多机器入技术的研究已在理论和实践两方面取得了大 量卓有成效的研究成果，并建立了一些多机器人的实验系统。 ( 1 ) a c t r e s s ( a c t o r - b a s e dr o b o ta n de q u i p m e n t ss y n t h e t i cs y s t e m ) 是由3 个机器人和3 个工作站组成的异构系统，用于完成单个机器人不能完成的任务， 如物体的搬运。该系统主要研究通信闯题，提出了不同抽象瀑的通信协议，包括 组播、基于合同网的协商机制，以及多阶段协商协议等。另外，该系统还研究冲 突、避碰等问题。 ( 2 ) c e b o t ( c e l l u l a rr o b o t i c ss y s t e m ) 。日本名古屋大学的f u k u d a 教授最早 于1 9 9 7 年提出的c e b o t 系统是将众多功能简单的机器人视为细胞，由生物免 疫网络得到启发，研究细胞机器入通过自组织原理构成器富体机器人，再将多个 器官体机器人组成复杂功能的机器人系统。细胞机器人自治地运动，没有全局的 世界模型，整个系统没有集幸控制，可以根据任务秘环境动态重构、可以具有学 习和适应的群体智能( g r o u pi n t e l l i g e n c e ) 。 ( 3 _ ) s w a r m 是由大量自主机器人构成的一个分布式系统。对给定的任务， 如编队行进，通过自组织使得低能的机器入协调合作，而展示出高智能行为。通 常各机器人为同质个体。通过相邻个体间的相互作用通讯，偶尔也用b r o a d c a s t 方式通讯。 ( 4 ) g o f e r 用传统的人工智能技术研究多机器人的分布式问题。c a l o u d 和 l e p a p e 等人雳g o f e r 体系结构研究了室内环境中多个移动机器入进行分布式求 解问题。在该体系结构中，有一个中心任务规划系统( c t p s ) 。c t p s 与所有的机 器入进行通信，对所有机器人的运行状态和任务的完成情况有全局了解。然麓， c t p s 产生计划结构，并将其通知所有的机器人。机器人利用任务分配算法来决 定自身的角色。这样，各机器入就可以知道系统在完成任务的过程中融身的目标， 并利用传统的触规划技术来实现该目标。利用g o f e r 已经成功地完成了三个 机器人进行推箱子、跟踪等任务。 ( 5 ) a l l i a n c e l - a l l i a n c e 3 1 是彘p a r k e r 提出的瘸于研究异旗、中，j 、规 模、独立性强的、疏松配合关系的机器人协调的种结构。通过传感器信息和精 确的b r o a d c a s t 斌透讯来感知基身的行动效应积其他机器入的行动蔫手控制异构 机器人群体。p a r k e r 把任务划分为子任务，每个予任务都会用到不同的行为组。 在最高的层次上，“设计若干个相互抑制的动机行为用来指导机器人的全局行为， 而这种全局行为反过来激活底层的行为去执行一个子任务。在沿袭基于传感器 触发行为的条件中，p a r k e r 加入了急躁( i m p a t i e n c e ) 与默许( a c q u i e s c e n c e ) 算子。如 第l o 页 第1 章引言 果没有其他机器入试图解决与一个动机行为有关的予任务，急躁就会增加；如暴 机器人不能完成予任务，则默许就会抑制行为。一个群体中急躁与默许的组合使 得机器入努力合作来完成一个全局任务。l a l l i a n c e 是a l l i a n c e 的扩展， 通过强化学习来调整行为控制器的参数，该结构成功用于仿真和物理机器人，完 成了诸如推箱予、捡垃圾、编队行进等在务。 1 6多机器人系统的相关问题和技术 学习和再励学习 传统的机器入研究是建立在工作环境的精确的先验知识的基础上的，存在罄 知识获取、工程实现和精确性等问题，适应能力很差。当机器人要求在未知环境 下工作，就注重机器人的盘适应性，需要机器久能“学习 。机器入依靠与环境 的不断交互来获取知识，通过反复调整环境模型和自身的模型，最终学会在未知 环境下运行。多机器人协调系统是一个极其复杂号# 线性动态系统，不可能具有完 备的先验知识，而必须依赖其自学习和自适应能力，通过自学习和再励学习建模， 动态调整控制参数来优化系统性能适应环境变化。有不少文献对多机器人协调系 统的自学习和再励学习作了研究，并提出了一些学习算法。大致可分为四类：个 体再励学习、群体再励学习、基于遗传算法的学习算法和基于模糊神经元的学习 算法。文【3 1 1 在薹一a ll i a n c e 结构中提漱一个标准再励学习算法，通过祝器入 学习如何评估其他机器人的表现而提高系统的协调性能。文 3 2 1 提出基于遗传算 法的h i l l - - - c l i m b i n g 学习算法，克服了传统遗传算法不保证系统性能的缺陷。文 【3 3 3 5 】是新兴的基于模糊神经元学习算法，文献显示基于进化算法和遗传算法的 再励学习算法已被较多歼发，它解决了个体再励学习的收敛性问题和群体再励学 习的样本复杂性问题，丽基于模糊逻辑、神经网络或模糊神经元学习算法的研究 在近几年正引起极大关注。 资源冲突问题 当资源被多个机器人请求使用时，就产生了资源冲突，资源冲突主要发生在 共享空闯、共网操作豹对象和通讯媒体的冲突上。对予多移动机器入来说，研究 重点是空间冲突问题，也就是避撞轨迹规划问题。关于多移动机器人避撞轨迹规 划的文章国内外已有不少，也提出了一些典型的方法。最直接的方法是集中行隽 控制法( c e n t r a l i z e dm o t i o nc o n t r 0 1 ) ，由中央规划器集中规划所有机器人的无碰撞 路径，这种方法完全，但复杂，且在实际应用中无法适应环境的变化，因此，人 们更关注菲集中控制式的轨迹规划方法。主从控制式( m a s t e r - s l a v ec o n t r 0 1 ) 是在冲 突状态下，选择一个主控机器人，由它向其它机器人发出行动指令，多用于分散 式控制结构系统。交通规则方法( t r a f f i cr u l e s ) 主要黑于将环境建模成交逯道路网 第l l 萸 第1 章引富 式的系统中。相互排斥法( m u t u a le x c l u s i o n ) 也是将工作区域分解成交通两式的离 散空间资源，如通道、十字路1 2 1 等，机器人按事先规划的路径移动，相互通讯并 按相互排斥的原则共享空间，从而协调其行为。动态优先级法是当机器入检测到 碰撞时，根据优化结果动态分配优先级，优先级高的机器人不考虑避撞，而优先 级低的帆器入将高优先级的机器入当作移动障碍物采取避撞措麓。这些方法的菸 同缺点是没有为系统提供修正路径的可能性，而当突然遇障或个机器人突然失 效时，修正路径极其重要。因此，人们提出基于传感器信息和机器学习的轨迹规 划方法，使得系统具有较高的柔性和鲁棒性。 多智能体机器人控制系统的实现 传统的商品化机器人控制器是面向机器入以部件单元式波雳而发展起来的， 难以满足多机器人协作控制的要求。多智能体机器人控制器与传统的机器人控制 器将有很大的区别，它不仅要求较高的智麓与童治的控剖能力，丽显要有易于协 作、集成为系统工作的机制与能力。在控制器实现时，要具备支持协作的新软件 和硬件体系结构，如编程语言、入机交互方式、支持系统扩展的机制等。在具有 分布式控制器的多机器人系统中，构造与实现系统( 包括支持多机器人协调合作 的问题求解或任务规划机制，控制计算机系统架构，分布式数据库等) 应能使系 统其有柔性、快速响应性和适应环境变化的能力。 7机器人环境探索的相关研究 环境探索是移动机器入学的基本任务。在行星漫步、侦查、援救、清洁等应 用中，环境探索和覆盖都是任务内在的不可或缺的部分。在未知环境的探索任务 中，机器人需要分散到环境中去搜集信息并进行信息融合，构建环境的地图。机 器人需要根据到目前为止获得的信息选择下一步移动的目标位置。 a r k i n 3 6 提出了使用多机器人执行侦察任务，机器人的移动通过预先编译的 向量场模扳控制。抽取机器入团队状态和环境的参数作为控制输入向量，由决策 树作为控制中心选择行动的向量场模板。决策树为各个机器人选择不同的向量场 模板，使得概器入担任不同的焦色，执行相应职责，实现团队的协调工作。然丽， 对于非结构化和动态的环境，向量场模板将难以设计，而且要求机器人的行为执 行层模块理解并支持相关惫量场模板所代表的角色和行为控制，这将增加机器入 设计的难度。 c o h e n 研究机器人豳队协作构建地图和导航 3 7 】。团队中有一位导航员，它 需要到达一个预先不知道位置的黼标点。霞驮中其他机器入是绘图员，它们隧机 地在地图上移动来寻找因标点。当其中一个机器人发现目标点时，目标点的位置 就会在绘图员闻传播著且传到导航员。然嚣导航员开始自慰标点进发。 第1 2 页 第1 章引害 y a m a u c h i 提出各机器入建立一个公用占有栅格地图【3 8 】，并弓| 入了边界的概 念，邻接未探索区域的已知区域定义为边界，每个机器人前往离它最近的边界获 得新信息，各机器人之闻除了共享地图信息以外没有协调。这种方法可能会出现 一个机器人探索另一个机器人已探索过的区域的情况。 s i m m o n s 提出的多机器久环境探索的协调机制【3 霹，该方法基于y a m a u c h i 的 边界概念，各机器人计算移动到边界点的花费和可能的信息增益，机器人把这些 信息提交给中央控制器，中央控制器通过最大佬总效用僵来实现县标分配。这一 算法的缺点是整个系统是一个集中式的结构，其性能完全依赖于中央控制器，中 央机器入的单点故障会使得整个系统崩溃。 b u r g a r d 提穗的方法提供了一种简单的协同实现方式 4 0 】。该方法使用效用 值来衡量边界单元能够提供的信息量。当某个边界单元分配给机器人后，该边界 单元及其附近的边赛的效用值要相应减少，表裙该边界的信息量下降。这种策略 通常在开始的时候能够令机器人分散开，覆盖更多的新区域。然而，机器人在随 惹的探索中不得不向一些小块的来知区域移动。这导致重复覆盖，更长的探索时 间和更多的能量消耗。而且机器人能够获得的信息量极大地依赖于环境区域的结 构。在未知环境中探索，信息量是难以预测的。 z l o t 及其同事提出了采用市场经济的模型解决多机器入协作探索问题【4 l 】。 该方法没有中央模块与全局地图，每个机器人在本地地图上寻找边界并确定目标 点，每个霉标点即是一个标於，标的信息包括蚕标点位置和该机器人到它的花费 ( 标的底价) 。机器人根据本地地图计算出到其他机器人目标点的花费，作为投 标价格。标的将由出价最低的机器入获得；若其他机器人的投标价格均高于底价 或无法计算该花费，则该点由发现它的机器人获得。若另一机器人已经探索过该 点，则它将通知提交标的的枧器人取消该点。在机器入拥有多个基标点的情况下 它将首先探索花费最小的目标点。由于没有共享地图信息，在大多数情况下各个 机器人的标的都由自身取得，这表明机器人之间的协作是极其有限的。 1 8论文的主要工作和创新点 本文以未知环境下多机器人协作探索为背景，研究协同探索策略和蚁群算法 在多橇器入协同探索策略中的应耀，并通过仿真实验验证算法的有效性。本文主 要研究工作总结如下： ( 1 ) 提出改进型边界探索算法，同时考虑边界的角度和距离因素，提高了探 索效率。针对多机器人系统探索策略的研究，主要有边界法和效用值法。这两种 方法考虑了边界的宽度和机器人与边界的距离。这两种方法具有一个缺点：探索 后袈会出现重复探索现象，降低探索效率。本文方法能够较好遗解决这个问题。 第1 3 隧 第1 章引言 本文方法针对机器人向来知区域移动的决策过程，同时考虑边界角度和距离两种 因素，并引入分散度函数产生协同机制，为每个机器人确定下一步探索区域，实 现多机器入协同探索未知环境。鸯予同时考虑角度和距离因素，探索过程中的小 块未知区域和狭窄边界将会得到有效覆盖，不会出现遗留现象，避免了后期的重 复覆盖和增加时闯与能量消耗。仿真实验表甓了本文方法的优势。 ( 2 ) 采用了最佳视角方法。原始的边界探索方法是机器入必须移动到边界上 的耳标点。基于传感器覆盖的探索过程中，机器人应该充分利用传感器的探测范 围，做如合理的路径规划，从而使得移动过程中能够发挥多个机器入载有的传感 器的效用，覆盖更多的区域。 ( 3 ) 将蟊队目标构造成为组合优化问题，使焉蚁群算法求解。本文将机器入 探索的决策过程抽象成为组合优化问题。该方法加强了系统中各个机器人之间的 联系，整合系统资源，统筹规划，相对于完全分布式结构，溺队的协作程度更高。 由于蚁群算法本身具有分布式计算能力，可以避免集中式结构过于依赖中央控制 器的缺陷。同时，可以方便地增加枫器人的数量，增加需要考虑的约束条件和探 索目标。能够有效地获得合理的任务分配方式，对于机器人的探索过程具有更强 的控制能力。 1 9论文的组织结构 本文主要分为四大部分，结构安排如下：第l 章为引言部分，简要介绍了多 机器人系统和多移动机器入环境探素的发展和研究现状，并介绍了论文的主要研 究工作。第2 章对环境建模和路径规划进行了概述，介绍环境表示的常用方法， 详细介绍a 謇算法在移动机器人路径规划中的应用。探讨多移动机器人环境探索 过程中的主要问题。第3 章介绍多移动机器入的协作探索策略，分析了基本边界 探索算法的特点和不足，在此基础上提出了改进型边界探索算法，介绍距离和角 度吸弓l 度函数及分散度函数的设计，以及团队旨标的构造。第4 章介绍蚁群算法 求解多机器人团队目标优化问题。将团队目标构造成整数规划问题，引入蚁群算 法对英求解。第5 章介缨仿真实验结果。通过不同环境下的仿真实验比较基本边 界探索算法和改进型边界探索算法的探索效果。第6 章是总结和展望。 第1 4 页 第2 章环境建模和路径规划 第2 章环境建模和路径规划 2 1环境建模 当移动机器人处在一个简单或复杂、静态或动态、已知或未知的环境中时， 机器人的首要任务是感知环境，避开障碍物，然后以最小或较小的消耗( 时间、 空间或者能量) 完成自己的任务，这个过程的基础所在是路径规划。无论采用何 种路径规划方法，都需要知道环境中的移动机器人自身位置所在，障碍物何在， 如何实现机器人对障碍物的躲避，路标与目标的识别等，这样才能搜寻到目标位 置，更好地完成自己的任务。那么，对环境的认知和如何实现环境建模，就成了 移动机器人自主导航与路径规划的基本前提。 常用的环境建模方法有单元分解建模、几何建模和拓扑建模的方法。 ( 1 ) 单元分解建模 单元分解建模即通常说的栅格法，其主要思想是将环境离散化为规则