（控制理论与控制工程专业论文）多移动机器人环境探索与地图创建关键技术研究.pdf

摘要 多移动机器人环境探索与地图创建关键技术研究 摘要 随着机器人技术的快速发展，其应用领域从结构化的已知室内环境，拓展到危险区域的 搜救、勘探、有毒物品的处理和军事应用等未知动态环境，在真实动态未知环境中移动机器 人完成各种智能任务的首要前提是对未知环境进行有效探索及创建环境地图。 多个功能有限的机器人组成的多机器人系统远比单个功能复杂的机器人具有优势，可以 完成单个机器人无法完成的任务，更加有效和可靠地完成任务，鲁棒性强。多机器人系统可 以提高环境探索和环境地图创建的效率，多个机器人并行工作可减少探索所需时间，灵活性、 可靠性及容错能力更强：通过融合多个机器人的感知信息，可以创建更精确的环境地图，获 得更精确的环境认知。与在单个机器人环境建模和探索方面已经取得的相当成熟的研究成果 相比，在未知环境中，在时间、能源、计算能力、通讯能力、感测能力、移动能力等各种约 束条件下，实现多机器人的有效协同探索和环境地图创建是一个具有挑战性的问题，有许多 难题亟待解决。本文主要针对多移动机器人系统的协同环境探索策略及多移动机器人的环境 地图创建展开研究，主要研究内容如下： 首先，本文综述了多机器人系统环境探索和环境地图创建方面的研究现状，介绍了论文 的研究背景和论文结构。 其次，在分析目前多移动机器人协同环境探索常用拍卖算法局限性基础上，应用多智能 体的合同网协议实现分布式的多移动机器人协同环境探索，提高整个系统的容错性和可靠 性，改进的多轮单物品拍卖算法可有效地为多机器人分配目标点，仿真结果验证了该算法可 以实现多移动机器人有效的协同探索，并且与组合拍卖相比，计算量大大降低。 第三，针对多机器人环境探索中为多机器人分配多目标点的组合优化问题，利用遗传 算法的全局搜索能力，解决多移动机器人的多目标点分配问题；引入免疫网络理论和克隆选 择算法建立动态分布式的多机器人协同环境探索机制，尝试在多个机器人之间以及在机器人 与未知环境之间建立智能，提高探索系统的冗余性和鲁棒性；针对传统遗传算法的早熟收敛 局限，应用免疫遗传算法为多移动机器人分配多目标点，将遗传算法的随机全局搜索能力、 并行性与免疫系统的抗体多样性相结合，免疫遗传算法能够更有效地为多移动机器人分配目 标点。仿真结果表明了这一方法的有效性，特别是在复杂的环境中，其在目标分配上的时间 大大减少。 第四，针对室内结构化环境地图创建，在对移动机器人固定配置的声纳传感器不确定信 息的分析基础上，利用h o u g h 变换对原始声纳数据进行直线特征提取，对声纳数据的预处 理，不仅改善了地图的精度，而且减少了数据融合的计算量，提高了环境地图创建的效率； 利用d s 证据理论对声纳数据进行融合，引入自适应的距离置信因子消除大量不确定信息， i i上海交通大学博士后研究t 作报告 建立环境的栅格地图；通过p i o n e e ri i ia t 机器人实验，验证了算法的有效性。 第五，针对声纳数据的不确定性信息，基于粗集理论，引入分层约简方法处理声纳数据； 在约简的基础上，应用多个神经网络进行目标识别，多神经网络的有效组合可以增强模式分 类的有效性，局部并行网络结构可以增加识别精度，应用平均加权策略融合并行神经网络的 输出以改善识别系统对于噪声、声纳数据丢失等的鲁棒性。仿真结果表明，与传统的基于声 纳数据的目标识别算法相结合，该方法可以提高室内环境下移动机器人基于声纳数据的目标 识别率，可以快速有效识别室内环境中的平面、锐角、转角、圆柱等典型目标。 第六，研究了在没有公共参考坐标系及机器人相对位置信息未知情况下的栅格子地图融 合问题，在地图相异度概念基础上，采用一种基于免疫自适应遗传算法的移动机器人栅格子 地图融合方法，搜索两个栅格子地图的最佳重叠区域。利用免疫算法的抗体多样性维持机制， 克服遗传算法的早熟收敛问题；基于抗体相似度和矢量距计算选择概率，保证抗体的多样性； 基于抗体的适应度实时调节交叉和变异概率，降低遗传算法陷入局部最优解的可能性。仿真 研究结果表明，该算法具有较快的收敛速度和较强的全局搜索能力，能够有效地搜索到两个 栅格子地图的最佳重叠区域，实现地图融合。 最后，论文对所取得的研究成果进行了总结，并阐述了下一步的工作。 关键词：多移动机器人系统；环境探索：环境建模；免疫算法；粗集：神经网络； a b s t r a c t r e s e a r c ho nm u l t i - r o b o te x p l o r a t i o na n dm a p p i n g a b s t r a c t w i t ht h eq u i c kd e v e l o p m e n to fr o b o t i c s ，r o b o t sh a v eb e e na p p l i e df r o mt h ek n o w ns t r u c t u r a l s t a t i ci n d o o re n v i r o n m e n t st ou n k n o w nd y n a m i ce n v i r o n m e n t s ，s u c ha s ，s e a r c ha n dr e s c u e ， s u r v e i l l a n c e ，r e c o n n a i s s a n c e ，h a z a r d o u sm a t e r i a l sh a n d l i n g ，m i l i t a r ya c t i o n s ，e t c i no r d e rt o a c c o m p l i s hs o m ei n t e l l i g e n tt a s ki nu n k n o w nd y n a m i ce n v i r o n m e n t sa u t o n o m o u s l ya n de f f e c t i v e l y , t h er o b o t sn e e dt oe x p l o r ea n dm a pt h eu n k n o w ne n v i r o n m e n t s i ti saf u n d a m e n t a lp r o b l e mi n m o b i l er o b o t i c s o b v i o u s l y , t h e r ea r em a n ya d v a n t a g e sf o re x p l o r a t i o na n dm a p p i n gu n k n o w ne n v i r o n m e n t s w i t hm u l t i p l er o b o t sc o m p a r e dw i t has i n g l er o b o t m u l t i p l er o b o t sc a na c c o m p l i s hs o m ed i f f i c u l t t a s k st h a ti m p o s s i b l ef o ras i n g l er o b o tm o r ee f f e c t i v e l y , r e l i a b l ya n dr o b u s t l y m u l t i p l er o b o t s w h i c hw o r kp a r a l l e lc a ne x p l o r ea n dm a pu n k n o w ne n v i r o n m e n tm o r eq u i c k l y , m o r et o l e r a n t l y a n dm o r ef l e x i b l y w i t hf u s i n gt h ep e r c e p t i o ni n f o r m a t i o no fm u l t i p l er o b o t s ，t h em o r ep r e c i s e m a po fe n v i r o n m e n tc a r tb eb u i l t c o m p a r e dw i t ht h es i n g l er o b o t ，m u l t i r o b o tc o o p e r a t i v e c o o r d i n a t i o na n dm a pb u i l d i n gu n d e rt h ec o n s t r a i n t so ft i m e ，p o w e r , c o m p u t a t i o n ，c o m m u n i c a t i o n ， s e n s i n ga n dm o b i l i t yi s ac h a l l e n g er e s e a r c hf i e l d t h e r ea r em a n yu n s o l v e dp r o b l e m t h i s d i s s e r t a t i o nh a sd o n es o m er e s e a r c ho nm u l t i - r o b o tc o o p e r a t i v ee x p l o r a t i o na n dm a p p i n g t h e p r i m a r yw o r ka n dt h ec o n t r i b u t i o n si nt h i sd i s s e r t a t i o na r ea sf o l l o w s ： f i r s t l y , t h ed i s s e r t a t i o nr e v i e w st h es t a t e - o f - t h e a r tm u l t i - - r o b o te x p l o r a t i o na n dm a p p i n ga n d i n 仃o d u c e st h eb a c k g r o u n do f o u rr e s e a r c ha n dt h ef r a m e w o r ko f t h ed i s s e r t a t i o n s e c o n d l y , o nt h eb a s i so ft h ea n a l y s i so ft h el i m i t a t i o n so ft h eu s u a la u c t i o na l g o r i t h m sf o r m u l t i - r o b o tc o o p e r a t i v ee x p l o r a t i o n ，a na u c t i o na l g o r i t h mb a s e do nt h ec o n t r a c tn e tp r o t o c o lo ft h e m u l t i - a g e n tt h e o r yh a sb e e na p p l i e df o rm u l t i - r o b o te x p l o r a t i o n t h ec o n t r a c tn e tp r o t o c o li nt h e m u l t i a g e n tt h e o r y i sa p p l i e df o rt h em u l t i - r o b o te x p l o r a t i o ni no r d e rt oi n c r e a s et h et o l e r a n c ea n d r e l i a b i l i t yo ft h ew h o l es y s t e m a ni m p r o v e dm u l t i - r o u n ds i n g l e - i t e ma u c t i o na l g o r i t h m i s p r e s e n t e dt oa s s i g nt h ef r o n t i e r st ot h em u l t i p l er o b o t se f f e c t i v e l y t h es i m u l a t i o ne x p e r i m e n t s p r o v et h a tt h ea l g o r i t h mc a nl e a dt ot h ee f f e c t i v ec o o r d i n a t i o no fm u l t i r o b o te x p l o r a t i o nw i mt h e d e c r e a s i n gc o m p u t a t i o nc o m p a r e dt ot h ec o m b i n a t o r i a la u c t i o n s t h i r d l y , t h ed i s t r i b u t i o no ft a r g e t sf o rm u l t i p l er o b o t si sac o m b i n a r i a lo p t i m i z a t i o np r o b l e m t h i sd i s s e r t a t i o np r e s e n t sam u l t i - r o b o tc o o p e r a t i v ee x p l o r a t i o ns t r a t e g yb a s e do nt h ei m m u n e g e n e t i ca l g o r i t h m w i t hi t sr a n d o mg l o b a ls e a r c h i n ga n dp a r a l l e lp r o c e s s i n g ，g e n e t i ca l g o r i t h mi s a p p l i e df o rm u l t i - r o b o t sm u l t i p l et a r g e t sc o m b i n a t o r i a ld i s t r i b u t i o n w i t hi t sa n t i b o d yd i v e r s i t y m a i n t a i n i n gm e c h a n i s m ，t h ei m m u n ea l g o r i t h mi su s e dt og e to v e rt h ep r e m a t u r ec o n v e r g e n c eo f g e n e t i ca l g o r i t h m t h es e l e c t i o np r o b a b i l i t yi sc o m p u t e db a s e do nt h es i m i l a r i t yv e c t o rd i s t a n c et o g u a r a n t e et h ea n t i b o d y sd i v e r s i t y t h ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t ya r ea d j u s t e db a s e do n i v 上海交通大学博十后研究工作报告 t h ef i t n e s so fa n t i b o d yt od e c r e a s et h ep o s s i b i l i t yo fl o c a lo p t i m a l t h ee x t e n s i v es i m u l a t i o n s d e m o n s t r a t et h a tt h ei m m u n i t y - b a s e da d a p t i v eg e n e t i ca l g o r i t h mc a ne f f e c t i v e l yd i s t r i b u t et h e t a r g e t st om u l t i p l er o b o t si nv a r i o u se n v i r o n m e n t sw i t hd e c r e a s i n gt i m ec o s tf o rd i s t r i b u t i n gt a r g e t s a m o n gm u l t i p l er o b o t s ，e s p e c i a l l yf o rc o m p l e xe n v i r o n m e n t s f o u r t h l y , a i m i n ga tm a pb u i l d i n gf o rs t r u c t u r a li n d o o re n v i r o n m e n t s ，h o u g ht r a n s f o r mi s a p p l i e df o re x t r a c t i n gl i n ef e a t u r e sf i o mr a ws o n a rd a t ao nt h eb a s i so ft h ea n a l y s i so fu n c e r t a i n t y o fs o n a rd a t a 啊mt h ep r e - p r o c e s s i n go fs o n a rd a t a t h ea c c u r a c yo fm a pi si m p r o v e da n dt h e c o m p u t a t i o n a lc o m p l e x i t yf o rd a t af u s i o ni sd e c r e a s e d t h ee f f i c i e n c yo fm a pb u i l d i n gi si n c r e a s e d d e m p s t e r - s h a f e re v i d e n t i a lt h e o r yi sa p p l i e df o rf u s i n gt h es o n a rd a t a t h ea d a p t i v er a n g e c o n f i d e n c ef a c t o ri si n t r o d u c e df o ra na d a p t i v es o n a rm o d e lt or e d u c eu n r e l i a b l es o n a rr e a d i n g s c a u s e db ys p e c u l a rr e f l e c t i o n si ni n d o o re n v i r o n m e n t s t h ee x p e r i m e n t sw i t hp i o n e e r3p r o v et h a t t h eh y b r i dm a p p i n g a p p r o a c hi se f f e c t i v ea n dr o b u s t f i f t h l y , a i m i n ga tt h eu n c e r t a i n t yo fs o n a rd a t ai nt h ep r o b l e mo fs o n a r - b a s e dt a r g e t d i f f e r e n t i a t i o nf o rm o b i l er o b o t ，ah i e r a r c h i c a lr e d u c t i o na p p r o a c ht or e d u c es o n a rd a t as e tb a s e d o nr o u 曲s e tt h e o r y o nt h eb a s i so ft h er e d u c t i o n , am u l t i - n e u r a ln e t w o r kb a s e dt a r g e t d i f f e r e n t i a t i o na l g o r i t h mi sd e s i g n e do nt h ef a c tt h a tt h ee f f e c t i v ec o m b i n a t i o no fm u l t i p l en e u r a l n e t w o r k sc a l li n c r e a s et h ea b i l i t yt op a t t e r nc l a s s i f i c a t i o na n dg e n e r a l i z a t i o no ft h ew h o l es y s t e m , p a r a l l e ln e t w o r ka r c h i t e c t u r ei s a d o p t e dl o c a l l yt oi n c r e a s et h ed i f f e r e n t i a t i o na c c u r a c y 1 1 1 e a v e r a g ew e i g h e ds t r a t e g yi sa p p l i e dt of u s et h eo u t p u t so ft h ep a r a l l e ln e u r a ln e t w o r kc l a s s i f i e r st o i m p r o v et h er o b u s t n e s so ft h ed i f f e r e n t i a t i o ns y s t e mt on o i s e ，p h y s i c a l l yp l a u s i b l ef a i l u r ea n d m i s s i n gs o n a rd a t a t h es i m u l a t i o n se x p e r i m e n t sp r o v et h a tt h en e wm e t h o dc o m b i n i n gw i t ht h e t r a d i t i o n a lt a r g e td i f f e r e n t i a t i o na l g o r i t h mc a ni n c r e a s et h ea c c u r a c yo fs o n a r - b a s e dt a r g e t d i f f e r e n t i a t i o nf o rm o b i l er o b o ti ni n d o o re n v i r o n m e n t s s i x t h l y , t h ep r o b l e mo ff u s i n gt w op a r t i a lm a p sw i t h o u tc o m m o nr e f e r e n c ef r a m e sa n d r e l a t i v ep o s i t i o ni n f o r m a t i o no fr o b o t si ss t u d i e d o nt h eb a s i so ft h es i m i l a r i t ym e t r i c ，an e w i m m u n i t y - b a s e da d a p t i v eg e n e t i ca l g o r i t h mi sa p p l i e df o rs e a r c h i n gt h em a t c h - o v e r l a p p i n gr e g i o n b e t w e e nt h ep a r t i a lo c c u p a n c yg r i dm a p s w i t hi t sa n t i b o d yd i v e r s i t ym a i n t a i n i n gm e c h a n i s m , t h e i m m u n ea l g o r i t h mi su s e dt og e to v e rt h ep r e m a t u r ec o n v e r g e n c eo fg e n e t i ca l g o r i t h m t h e s e l e c t i o np r o b a b i l i 哆i sc o m p u t e db a s e do nt h es i m i l a r i t ya n dt h ev e c t o rd i s t a n c et og u a r a n t e et h e a n t i b o d y sd i v e r s i t y t h ec r o s s o v e ra n dm u t a t i o np r o b a b i l i t ya r ea d j u s t e db a s e do nt h ef i t n e s so f a n t i b o d yt od e c r e a s et h ep o s s i b i l i t yo fl o c a lo p t i m a l t h es 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 a t t h ei m m u n i t y - b a s e da d a p t i v eg e n e t i ca l g o r i t h mb a s e dm a pm e r g i n gc o u l db er o b u s ta n dp r o v i d e f a s tc o n v e r g e n c ef o rt h eo p t i m a lo v e r l a p p i n gp a r t i a lm a p s f i n a l l y , t h ed i s s e r t a t i o nc o n c l u d e so u rr e s e a r c ha n dd i s c u s s e st h ef u t u r ew o r k k e yw o r d s ：m u l t i r o b o ts y s t e m ；e x p l o r a t i o n ；m a p p i n g ；i m m u n i t ya l g o r i t h m ；r o u g hs e t ；n e u r a l n e t w o r k 第一章概述 1 1 项目的选题背景 第一章概述 近十年来，科学技术的快速稳步发展，极大地促进了机器人技术的发展：另一方面，多 发的自然灾害如雪灾、地震，以及人为的恐怖活动，威胁着人民的生命财产和社会安全，如 何快速安全地进行施救：神舟系列宇宙飞船的成功发射及美国机遇号、勇气号火星探测器登 上火星，旨在了解太阳系起源及现状、探索生命起源和演变、开发和利用空间资源、扩展人 类生存空间、为人类社会长期可持续发展提供服务的空间探索越来越成为全球关注的焦点， 这些关系到人类生存安全及未来、实际亟待解决的问题向机器人技术提出了挑战，要求机器 人从结构化的已知室内环境走到未知非结构化环境，如行星探索f 、危险区域的勘探【2 】、搜 划3 1 、有毒物品的处理州和军事应用嘲等。 显然，移动机器人在未知环境中自主地完成各种智能任务的前提要求它具有感知环境的 能力，即机器人在未知环境中不断探索，在探索过程中，机器人利用其自身所携带的传感器 不断感知环境，收集环境信息，逐渐建立起环境地图，并在所创建的环境地图中进行定位， 环境地图的有效创建要求有效的探索策略，环境探索和环境地图创建是移动机器人学的基本 问题之一。 计算机硬件成本的大幅下降及各种移动无线通信网络新技术不断涌现，极大地促进了多 移动机器人系统发展。由多个移动机器人按照某种结构关系结合起来的多移动机器人系统具 有单个机器人所无法比拟的优势1 6 , 7 ： 1 ) 多移动机器人系统具有更好的时空分布性、并行性，整个系统的效率将大大提高； 2 ) 多移动机器人系统中各机器人能够提供冗余性、互补性更强的传感器信息； 3 ) 多移动机器人系统中单个机器人不需要很好的功能配置，整个系统的成本更低、可 维护性更强； 4 ) 多移动机器人系统的灵活性、容错性更强： 5 ) 通过协作，多移动机器人系统可以完成单个机器人难以完成，或根本不可能完成的 工作。 针对环境探索与环境地图创建这一移动机器人学的基本任务，与单个移动机器人相比， 多移动机器人系统具有明显优势：多个移动机器人可以分散开来，并行工作，同时探索不同 环境、创建不同环境的地图，在多个移动机器人之间实现信息共享，提高了整个系统进行环 境探索的效率：多个移动机器人可以携带多个异类或同类传感器来感知环境，通过对这些具 有冗余性和互补性的传感器信息进行多传感器信息融合，可以获得精度更高的环境地图，提 2 上海交通大学博上后研究f t 作报告 高机器人对环境认知的水平及定位精度【8 】；多移动机器人系统中某个机器人或某个传感器故 障，不会给整个系统的环境探索和地图创建工作造成致命影响，整个系统的灵活性、可靠性、 容错性大大提高。利用多移动机器人系统进行环境探索和环境地图创建是目前多移动机器人 学界的一个研究热点。 然而，与单个机器人在定位、环境建模和探索方面已经取得的相当成熟的研究成果相比， 在未知不确定的非结构环境中，在时间、能源、计算能力、通讯能力、感测能力、移动能力 等各种约束条件下，如何有效地组织和协调多个移动机器人的探索行为，减少机器人之间的 冲突，进行有效的多传感器信息融合，充分发挥多移动机器人系统的优势，实现多移动机器 人的有效协同环境探索及环境地图创建是一个具有挑战性的问题【9 】。 多移动机器人系统有效工作的关键是对多个移动机器人构成的群体加以组织，并有适当 的组织结构和协调控制机制，组织与控制方式在很火程度上决定了系统的有效性，机器人的 数目越多，协调机制的制定越重要，多移动机器人的组织和控制方式在很大程度上决定了系 统的有效性。要使多移动机器人系统能够有效地进行环境探索、创建高精度的环境地图，就 必须对多移动机器人构成的群体加以组织，并有有效的组织结构和控制机制。能够产生高度 一致性、鲁棒性、可扩展性、实用性和适应性的多移动机器人群体协同环境探索行为的设计 方法，已成为多移动机器人学中日渐活跃的领域。 在多个移动机器人之间如何有效实现信息共享，即如何融合安装在多个移动机器人上的 异类或同类传感器所得到的关于环境的冗余、互补信息，获得对环境的更精确、更全面认知， 建立全局地图，并在此全局地图上进行机器人的自定位，不仅是多移动机器人协同环境探索 的最终目标，而且还影响着多移动机器人协同环境探索的效率，是保证多移动机器人系统进 行有效协调、避免冲突和重复探索的关键【lo 】。 本论文针对多移动机器人系统协同环境探索与环境地图创建这一基本问题进行研究，尝 试应用人工免疫网络理论、遗传算法、多智能体理论，研究多移动机器人系统协同探索策略 的制定；将神经网络和智能信息处理研究领域近年来迅速发展的粗集理论相结合，研究和探 索新的具有分层结构的、能够减少多机器人之间通讯量、便于实现局部地图融合、并保证地 图一致性的环境表示方法；应用h o u g h 变换和带有自适应距离置信因子的改进d s 证据理 论处理声纳数据的不确定信息，对声纳数据进行融合，提高环境地图创建的效率和地图精度； 将免疫算法和遗传算法相结合，研究在没有公共参考坐标系及机器人相对位置信息未知情况 下的栅格子地图融合问题。本论文的研究成果将丰富多移动机器人系统在环境探索与环境地 图创建方面的研究成果，在民用和特种领域，如国防、航天、海洋等，具有广阔的应用前景。 1 2 多移动机器人环境探索发展概况 在未知环境中，移动机器人自主地实现导航、路径规划等智能任务的前提是对环境的有 效认知，有效的探索策略可以提高机器人认知环境的能力和速度。 第一章概述 3 一 早期关丁移动机器人环境探索问题的研究强调对于环境区域覆盖的完全性和无重复性， 一般归结丁先验环境信息未知的覆盖( c o v e r a g e ) 问题。c h o s e t 在其综述移动机器人覆盖问 题时，把移动机器人环境探索问题归类为环境先验信息未知的在线机器人覆盖问题( o n l i n e c o v e r a g e ) 或基于传感器的覆盖问题( s e n s o r - b a s e dc o v e r a g e ) 【l ，即机器人利用自身所携带 的传感器获得的环境信息指导其自身的移动行为，在尽量短的时间内、用尽量短的行走距离 完全地、无重复地覆盖整个环境区域，可以看作是连续域的广义旅行商问题( t r a v e l i n g s a l e s m a np r o b l e m ) ，即使已知先验环境信息，也是一个n p - h a r d 问题【l2 1 。 多移动机器人环境探索策略与单个移动机器人环境探索策略一样，可以分为随机探索和 基于边界的主动式环境探索方法。 1 2 1 随机探索 早期移动机器人的探索策略是随机探索方法，由一系列基本行为( 如沿墙行走、避障随 机行走等) 的集合构成了机器人的行为集，直接在环境感知信息和机器人行为控制命令之间 建立一种映射关系，由这些基本行为的分层组合形成移动机器人的随机探索行为【l 3 1 。 b a l c h 和a r k i n 将此随机搜索方法应用于多个移动机器人在未知区域内搜索目标i t 4 ，各 机器人之间互相排斥作用保证各机器人能够在探索区域尽量分散开，提高搜索目标的效率。 这种基于行为的随机探索方法并没有对机器人的探索路径进行规划，也不能够保证对环境的 完全覆盖及覆盖的无重复性，但是这种随机探索方法也有其优点。b a l c h 和g a g e 各自从花 费效益比的观点分析了随机探索的优点【1 5 一们。随机探索方法不需要昂贵的定位传感器( 如 g p s ) ，也无需花费有限的计算资源进行机器人定位计算，这种方法与需要精确定位的探索 策略相比，所需花费较少。但是，整体来说，基于行为的随机探索方法属于被动式探索策略， 效率低下，并且无法避免重复探索。 1 2 2 基于边界点的主动式环境探索 针对被动式随机探索策略的不足，y a m a u c h i 首先提出基于边界点的探索策略【1 7 】，“边界” 定义为已知开阔区域与未知区域之间的分界线，机器人在已经获取的环境部分信息基础上创 建环境地图，在已创建的环境地图上，按照某种策略，选择某一个或某几个“边界点”作为 下一个目标点，期望在“边界点”获得关于环境的最大量新信息，在这一主动式环境探索策 略指导下，机器人能够主动地对环境进行探索，探索效率得到提高。 y a m a u c h i 将基于边界的环境探索策略扩展到多移动机器人系统【体】，各机器人共享环境 信息，独自创建和维护各自的环境地图，独自不断地选择边界点对环境进行探索，整个系统 对于单个机器人故障具有鲁棒性，但由于各机器人之间缺乏明确的协调，多个机器人可能会 探索同一区域，引起冲突和重复探索，探索效率低，然而，“边界点”这一概念为多移动机 器人协同环境探索的研究奠定了基石。r e k l e i t i s 等人设计的多移动机器人系统中，各机器人 4 上海交通大学博上后研究工作报告 始终在各自的视野范围内，当一个机器人移动时，其他机器人静止，并观测运动机器人的移 动，这样依次对环境进行探索，通过信息融合减少了里程计误差引起的环境建模的精度降低 d 9 1 ，但并没有充分发挥多移动机器人系统的优势，探索时间并不会大大减少。上述探索方 法实际上都没有真正考虑多机器人之间的协调。 p a r k e r 提出了多机器人意图明确的合作协调模型【2 0 1 ，在动态环境中，a l l i a n c e 系统 中各异质机器人进行目的明确的合作，实现完全分布式的、基于行为的、具有容错能力的任 务分配和协调。实现多移动机器人系统有效、协调环境探索的关键是如何合理地为多移动机 器人分配边界点，而这是一个n p h a r d 难题。 l a t i m e r 等提出多移动机器人保持一定的队形，进行环境探索，这种策略要求机器人之 间密切的协调及通讯【2 l 】。s o l a n a s 等在y a m a u c h i 的“边界”概念基础上，提出利用k 。m e a n s 聚类方法把未知区域分成不相连接的小区域，各机器人分别探索不同区域，提高探索速度 1 2 2 1 。s v e n n e b r i n g 和k o e n i g 提出在各机器人走过的路径上留下印迹，这种方法不需要机器人 的位置信息，也不需要在机器人之间交换地图信息，可间接地通过“信息素”在多个机器人 之间实现协同环境探索【2 3 j 。 研究者们成功地借鉴市场经济的基本原理，特别是拍卖机制，实现多机器人的协调与合 作 2 4 , 2 5 】。应用到多移动机器人环境探索方面，各机器人根据达到目标点的代价、目标点的效 用值进行估价和投标，实现各机器人利益最大化、系统整体资源利用最大化的有效协调。 s i m m o n s 等提出了基于单个物品第一价位拍卖机制的多机器人环境探索策略，一个中央智能 体接收其他机器人的投标，从系统信息获取最大化、代价( 行走距离) 最小化出发，将边界 单元分配给各机器人【2 刚。z l o t 等在s i m m o n s 提出的拍卖协议基础上，通过类似于市场经济 中的谈判过程实现目标点在多机器人之间的分配，但没有考虑各目标点之间的距离关系【2 7 1 。 b e r h a u l t 等针对单物品拍卖协议的缺点，提出了基于组合拍卖的多移动机器人协同探索策 略，考虑各目标点之间的关系，对多个目标点进行组合拍卖，提高了探索效率，但组合的形 式以目标点指数级增加，目标点分配的计算量很大【2 引。g e r k e y 等在m u r d o c h 系统上实现 了基于拍卖机制的多移动机器人协同探索【2 4 1 ，g r a b o w s k i 等在微型机器人系统m i l l i b o t s 上用 一个中央模块实现多移动机器人的环境探索【2 9 1 。以上方法都属于集中式协调，由中央模块 或拍卖人( a u c t i o n e e r ) 融合系统中其他机器人的位置、环境信息，创建全局地图，在全局 地图上实现各目标点的分配，适用于静态环境下的小规模的多移动机器人系统，不适用于大 规模的多移动机器人系统，易遭受单点故障、通讯量大，对局部变化的反应慢，并且都假设 所有的机器人已知各自的位置，通讯完善，没有考虑不可预测的通讯故障等约束问题。 1 2 3 考虑各种约束条件的分布式多移动机器人环境探索 麓 近几年来，多移动机器人环境探索方面的研究不再局限于覆盖问题，开始更多地考虑探 索的鲁棒性以及在更苛刻条件下的环境探索，研究者们在各种约束条件下的分布式多移动机 器人环境探索问题方面的研究取得了一些成果。 第一章概述 5 一 r o y 等提出了通讯能力约束条件下的基于集结的多移动机器人环境探索机制【3 0 1 ，然而， 多机器人的集结会降低整个系统的探索效率。b u 曜a r d 等提出基于决策理论的意图明确的集 中式协调机制实现多机器人的协调环境探索，并考虑了机器人有限通讯能力的约束问趔3 1 1 。 r e k l e i t i s 研究了通讯能力有限的多移动机器人的环境探索，并能够保证环境区域的全覆盖 p 引。f o x 等提出了分布式的多移动机器人环境探索策略，没有建立通讯连接的各机器人可以 单独进行探索，当机器人之间建立通讯时，机器人进行集结，形成一个聚类，融合各自环境 信息，采用贝叶斯决策理论进行协调，提高了系统的鲁棒性和可靠性【3 2 1 。s h e n g 等提出了在 机器人通讯距离有限约束条件下的基于竞标模型的分布式多移动机器人协同探索，竞标的估 价不仅考虑各机器人到达目标点的代价及目标点的效用值，还考虑各机器人之间的相对距离 信息【3 3 1 。s t a c h n i s s 等估计环境的语义信息对目标点进行分类，提高了探索效率3 4 1 。 对于单个机器人而言，具有完全性和无重复性的覆盖意味着最小的探索时间，然而对于 多移动机器人，无重复性的覆盖和探索效率是两个不相关的优化指标：无重复性的覆盖算法 可能探索效率不高，效率高的探索算法可能区域多次被重复覆盖。 在g a b r i e l y 等提出的基于生成树( s p a n n i n g - t r e e ) 的用于单个移动机器人连续域覆盖算 法的基础上【3 5 1 ，h a z o n 等提出了多移动机器人生成树覆盖算法( m u l t i r o b o ts p a n n i n g - t r e e c o v e r a g e ) ，并研究了算法的鲁棒性和效率，但这一算法假设环境先验信息已知1 3 6 1 。 c o r r e l l 等提出将概率算法与确定性算法相结合用于多机器人探索问题，提高覆盖的鲁 棒性【3 7 】。r e k l e i t i s 利用b o u s t r o p h e d o n 分解方法保证通讯能力有限的多移动机器人的环境探 索系统的全覆盖p 引。g e 等研究环境连通情况下的多移动机器人环境探索的完全覆盖问题， 该算法可以