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

山东大学硕士学位论文 摘要 随着科学技术的飞速发展，机器人学的研究已经从最初的工业领域拓展到 航空航天、军事、民用等各领域，对于那些不适合人类直接参与的作业环境， 需要机器人能够自主地完成各种智能任务。有效的环境探索是机器人创建环境 地图及完成各种复杂任务的关键，在实际应用中具有十分重要的意义。与单个 机器人相比，多移动机器人系统具有明显优势。然而，多机器人环境探索策略 的制定比单个机器人困难得多，各机器人间存在着组织和协调问题。本文主要 针对未知环境下的多机器人系统协同环境探索的策略进行了研究。 本文首先对多移动机器人系统环境探索的相关内容以及研究现状等进行了 综述性介绍，并对本文的选题背景和主要内容作了阐述。 其次，针对多机器人环境探索中如何分配多目标点的组合优化问题，前人 提出了基于决策理论的分配方法，但此法存在计算量大和时效性差的问题，文 中提出了一种基于单纯遗传算法的目标分配策略，利用遗传算法的全局搜索特 性来提高求解速率。但由于单纯遗传算法易于早熟收敛，文中进一步提出了基 于改进的遗传算法的目标分配策略，不仅利用了基于相似矢量距的选择概率计 算方法来保证抗体的多样性，并且引入自适应遗传算法的思想来实现自适应地 调节交叉和变异概率。 第三，考虑到集中式结构的弊端和多机器人系统的可扩展性，本文借鉴生 物免疫系统的分布式结构和自适应平衡特性，建立起动态分布式的多移动机器 人系统，并结合人工免疫中抗原与抗体、抗体与抗体间的相互作用机制，提出 了一种基于免疫原理的多机器人组网探索策略。 第四，为了进一步优化多机器人环境探索的行为策略，本文在研究克隆选 择原理的基础上，提出了一种改进的克隆选择算法，选用实数编码的候选解为 抗体，采用可自适应调整的克隆操作和柯西变异算子，以提高对局部解的搜索 能力和保证抗体群的多样性。 文中提出的算法都通过仿真平台下的多次实验进行了验证和对比。最后对 本论文做出总结，并指明需要进一步研究的工作。 关键词：多机器人；环境探索；免疫遗传；分布式；克隆选择 山东大学硕士学位论文 a b s t r a c t w i t ht h ef a s td e v e l o p m e n to fs c i e n c ea n dt e c h n o l o g y , r o b o t sh a v eb e e na p p l i e d f r o mm a n u f a c t u r i n gi n d u s t r yt oa e r o s p a c e & a v i a t i o n ，m i l i t a r ya n ds oo i l r o b o t sc a n c a r r yo u tt h e i ri n t e l l i g e n tw o r ka u t o n o m o u s l yi nu n k n o w ne n v i r o n m e n t s t h ek e y p r o b l e mo fm a p b u i l d i n ga n do t h e rt a s k sf o ra u t o n o m o u sr o b o t s i s e x p l o r a t i o n c o m p a r e dw i t hs i n g l er o b o t ，m u l t i - r o b o ts y s t e mh a sal o to fa d v a n t a g e s h o w e v e r , e x p l o r a t i o ns t r a t e g yo fm u l t i r o b o ts y s t e m ，w h i c hs h o u l d t a k ei n t oa c c o u n to f c o o p e r a t i o no fm u l t i p l er o b o t s ，i sm o r ed i f f i c u l tt h a ns i n g l er o b o t t h i sd i s s e r t a t i o n s t u d i e s c 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 y o fm u l t i r o b o ts y s t e mi nu n k n o w n e n v i r o n m e n t 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 er 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 d i t s r e l a t i v ea s p e c t si nt h ew o r l d t h eb a c k g r o u n da n dt h em a i nc o n t e n t so ft h i s d i s s e r t a t i o na r ed e s c r i b e db r i e f l y s e c o n d l y ，t h ek e yt om u l t i r o b o te x p l o r a t i o ni st h ed i s t r i b u t i o no ft a r g e t sf o r m u l t i p l er o b o t s a i m i n g a tt h ec o m b i n a t o r i a lo p t i m i z a t i o np r o b l e m ，b u r g a r d p r e s e n t e dad e c i s i o n t h e o r e t i ca p p r o a c ht oc o o r d i n a t e t h er o b o t s h o w e v e r ，t h e c o m p u t a t i o nb u r d e nf o ro p t i m a la l l o c a t i o ni n c r e a s e se x p o n e n t i a l l yw i t ht h en u m b e r o fr o b o t sa n dt a r g e t p o i n t s t os o l v e t h i s p r o b l e m ，w ep r o p o s e ag e n e t i c a l g o r i t h m - b a s e d c o o r d i n a t e dm u l t i r o b o t e x p l o r a t i o n a l g o r i t h m w i t hi t s c h a r a c t e r i s t i c so fr a n d o mg l o b a ls e a r c h i n gt os e e kt h es o l u t i o nq u i c k l y t og e to v e r t h ep r e m a t u r ec o n v e r g e n c eo fs i m p l eg e n e t i ca l g o r i t h m ，w ep r e s e n tam u l t i r o b o t c 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 p r o v e dg 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 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 e t 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 e c 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 yi s a d j u s t e db a s e do nt 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 f l o c a lo p t i m a l t h i r d l y ，i n o r d e rt og e to v e rt h ed r a w b a c k so fc e n t r a l i z e ds t r u c t u r ea n di m p r o v e t h es c a l a b i l i t yo fm u l t i r o b o ts y s t e m s ，t h ed i s s e r t a t i o nl e a r n sf r o mt h ed i s t r i b u t e d a r c h i t e c t u r ea n da d a p t i v eb a l a n c ea b i l i t yo ft h ei m m u n es y s t e ma n de s t a b l i s h e s d y n a m i cd i s t r i b u t e dm u l t i r o b o ts y s t e m c o m b i n i n gw i t ht h ei n t e r a c t i o nm e c h a n i s m b e t w e e na n t i g e na n da n t i b o d ya n da m o n ga n t i b o d i e s ，t h i sp a p e rp r o p o s e sa d i s t r i b u t e dm u l t i r o b o tn e t w o r ke 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 ep r i n c i p l e f o u r t h l y ，a ni m p r o v e de l o n a ls e l e c t i o na l g o r i t h mb a s e do nt h ec l o n a ls e l e c t i o n p r i n c i p l ei sp r o p o s e df o rm u l t i r o b o te x p l o r a t i o n b e c a u s et h ec o m p u t a t i o nb u r d e n f o rt h eb i n a r y c o d e dc l o n a ls e l e c t i o na l g o r i t h mi sh e a v y ，t h er e a l c o d e dc l o n a i s e l e c t i o na l g o r i t h mi sa d o p t e d w i t ht h eh e l po fc l o n ea n da d a p t i v ec a u c h ym u t a t i o n o p e r a t o r , t h es p e e do fc o n v e r g e n c ea n dd i v e r s i t yo ft h ea n t i b o d i e si si m p r o v e d a p p a r e n t l y 山东大学硕士学位论文 a l lo ft h ea b o v ea l g o r i t h m sa r ep r o v e da n dc o m p a r e dw i t ht h ee x t e n s i v e s i m u l a t i o ne x p e r i m e n t s f i n a l l y ，c o n c l u s i o n sa r eg i v e nw i t hr e c o m m e n d a t i o nf o rf u t u r ew o r k k e y w o r d s ：m u l t i r o b o t ；e n v i r o n m e n te x p l o r a t i o n ；i m m u n eg e n e t i c ；d i s t r i b u t e d ； e l o n a ls e l e c t i o n i i i 山东大学硕士学位论文 缩略语 a i sa r t i f i c i a li m m u n es y s t e m ，人工免疫系统 c l o n a l gc l o n a ls e l e c t i o na l g o r i t h m ，克隆选择算法 d a r s d t a g a i c s a i g a i n a m a s m r c e s d i s t r i b u t e da u t o n o m o u sr o b o t i cs y s t e m ，分布式自治机器人系统 d e c i s i o n t h e o r e t i ca p p r o a c h ，决策理论方法 g e n e t i ca l g o r i t h m ，遗传算法 i m p r o v e dc l o n a ls e l e c t i o na l g o r i t h m ，改进的克隆选择算法 i m m u n eg e n e t i ca l g o r i t h m ，免疫遗传算法 i m m u n en e t w o r ka l g o r i t h m ，免疫网络算法 m u l t i a g e n ts y s t e m ，多智能体系统 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 ns y s t e m ，多机器人协同环境 探索系统 s g a s i m p l eg e n e t i ca l g o r i t h m ，单纯遗传算法 i v 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究所取得的成果。除文中已经注明引用的内容外，本论文不 包含任何其他个人或集体己经发表或撰写过的科研成果。对本文的研 究作出重要贡献的个人和集体，均已在文中以明确方式标明。本声明 的法律责任由本人承担。 论文作者签名：数勃 e t 期：呈堂：主：度 关于学位论文使用授权的声明 本人完全了解山东大学有关保留、使用学位论文的规定，同意学 校保留或向国家有关部门或机构送交论文的复印件和电子版，允许论 文被查阅和借阅；本人授权山东大学可以将本学位论文的全部或部分 内容编入有关数据库进行检索，可以采用影印、缩印或其他复制手段 保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：j 欹勤一导师签名：斗e t 期：j 坐业 山东大学硕士学位论文 1 1 引言 第一章绪论 近年来，随着计算机、通讯、电子、传感、控制等技术以及人工智能的飞速 发展，移动机器人的设计与应用水平得到了不断提高，和传统的工业机器人相比， 具有自主感知、决策和执行功能的移动机器人具有更加广阔的应用前景。在国防、 工农业生产、抢险等领域的任务执行过程中，移动机器人具备了人类所无法比拟 的巨大优势。其中，未知环境的探索和地图构建是移动机器人领域的一项重要研 究内容，具有广泛的应用背景，如军事上的扫雷、侦察和灾后救援等。二者是相 辅相承的，地图创建需要合适的探索算法来获取环境中的完整信息，并创建完整 的环境地图；同时探索又可以利用不断累积的地图信息来提高效率。 然而，随着机器人工作环境的日益复杂以及任务的加重，单个机器人已经无 法满足人们的需求，与单个机器人相比，多移动机器人系统具有更显著的优势【l l l ，2 2 2 3 】： ( 1 ) 多机器人可以并行探索，具有更好的时间和空间分布性，将会大大节省 完成任务所需的时间，故探索速度要比单个机器人快； ( 2 ) 多机器人系统中各机器人的传感器信息可以有效互补，使整个系统具有 更高的数据冗余度和更好的鲁棒性； ( 3 ) 多机器人系统中各机器人的结构比较简单，成本低廉，设计和维护难度 都远低于单机器人； ( 4 ) 多机器人不仅能够高性能地完成单机器人所能完成的任务，而且能以团 队形式的合作来重新分配资源，完成许多单机器人所不能完成的复杂任务。 因此，利用多机器人系统探索未知动态环境并建立环境地图己成为近年来多 机器人系统研究的重点和热点。但是，多机器人共同进行环境探索必然存在相 互协调的问题，如何有效地组织和协调多个机器人的探索行为，减少机器人之 间的目标冲突、区域重复等问题，成为了新的难题【lj 。 近年来，基于多机器人协作的探索算法引起了越来越多的研究人员的关注， 针对机器人路径规划、环境探索和地图构建等不同的应用背景，出现了多种研 究方法，例如：引入经济学领域的市场法等原理来解决多机器人间的任务分配 问题，以提高机器人对未知环境的探索效率【1 1 l 】；利用各种人工智能算法来实 山东大学硕士学位论文 现多机器人间的协同。本文利用遗传算法来解决多机器人间的多目标点分配问 题，引入免疫网络理论和克隆选择算法来建立多机器人协同环境探索的动态分 布式的一致决策机制，实现多个机器人之间的协调以及在机器人与未知环境之 间建立智能，使整个系统保持较好的冗余性和鲁棒性。这在多机器人应用日益 广泛的军事、工业以及民用等领域，将具有十分重要的意义。 1 2 研究现状 1 2 1 多移动机器人环境探索的研究历程及现状 多移动机器人间的协调与协作是多机器人系统研究中的一个重要问题，已 经经历了一段较长的发展历史。多机器人协调是指具有不同目标的多个机器人 对其目标、资源等进行合理安排，以调整自身行为，最大限度地实现各自的目 标。而多机器人协作是指多个机器人通过协调各自的行为，合作完成共同目标 例。自8 0 年代以来，多机器人协调作为机器人应用领域的新方向引起了国内外 学者的广泛关注。1 9 8 7 年，美国圣地亚哥召开的多机器人协调研讨会着重提出 了多机器人协调研究的主要问题。1 9 8 9 年，国际杂志 r o b o t i c sa n da u t o n o m o u s s y s t e m ) ) 专门推出了多机器人协调研究专辑，此外，i e e e 的机器人与自动化国 际会议从1 9 8 6 年起已将多机器人协调研究列为一个专题组【3 】。而随着机器人在 未知非结构化环境中的应用研究的深入，多移动机器人协作系统在环境探索领 域的应用也逐渐受到人们的关注，并成为机器人领域的研究热点。 从系统结构上来说，多机器人环境探索系统通常可以分为集中式和分散式 两种。集中式结构可以得到近似最优解，能避免区域重叠并提高探索效率，但 易导致中央机器人成为整个系统的瓶颈，且通讯量大，对局部变化反应不灵敏， 故仅适用于机器人数量较少和静态的或易于获得全局信息的环境【4 j 。分散式结 构又可细分为分布式和分层式两种结构【5 j 。分布式系统中各机器人关系平等， 以通讯等手段与其它机器人进行信息交互，自主地进行决策。此法具有很好的 灵活性和鲁棒性，但易产生很多次优解。分层式结构与分布式结构的不同之处 在于存在局部集中，它是一种介于集中式与分布式的混合结构，故具备更强的 灵活性和可扩展性，但有可能带来计算、通讯量大以及冲突死锁问题【2 j 。 近年来，建立在局部无线通讯网络基础上的分布式传感系统在理论和实验 方面都取得了明显进展，其主要特性是功耗低、尺寸小、成本低，这为多机器 2 山东大学硕士学位论文 人系统开辟了一个全新的研究领域，由此出现了一系列低功耗、具有基本传感 和短距离通讯能力的多机器人系统研究平台。 先前的分布式多机器人环境探索系统中各机器人之间没有协调，它们独立 工作，只有当机器人在通讯范围内时才交换地图【6 】。在y a m a u c h i 提出边界的 概念以前1 7 ，移动机器人环境探索策略都是简单的沿墙行走8 1 或随机行走9 1 等被 动的探索策略，只适用于结构化的较小环境，探索效率低。y a m a u c h i 提出各机 器人建立一幅公用的占有率栅格地图【1 0 】，并引入了边界的概念。 另外，一些经济学方面的理论也被应用到多机器人环境探索中来。其中， 基于市场法的协商机制是一种广泛采用的多机器人协同探索策略【l l 】。它采用完 全分布式的结构，具有计算量小、通讯量少的优点，但各机器人自身探索的局 限性限制了整个系统协作效率的提高。拍卖是市场法中最常用的机制，文献 1 2 ， 1 3 分别采用了不同的拍卖机制在机器人间分配目标点。 后来，由于多智能体系统( m u l t i a g e n ts y s t e m ，m a s ) 的许多优势逐渐被 人们发现，基于m a s 的很多算法和技术也被运用于多机器人协同环境探索。 例如在文献 1 4 ，1 5 】中，作者均运用了m a s 的算法，并在不同算法之间进行了 对比、分析。 在很多实际应用中，多机器人协同环境探索也取得了一定成果。如文献 1 6 】 中，作者在实际的空中机器人和地面机器人之间的协同问题上做了研究，并通 过实际操作验证了其算法的有效性。而文献 1 7 】关注的是水下机器人协同探索 水下多变环境的问题。 随着多智能体系统原理、分布式学习理论和机器人控制技术的逐步成熟， 多机器人学的发展正面临新的突破。人工免疫学、进化计算、机器学习以及近 年来智能信息处理研究领域迅速发展起来的粗集理论等与多机器人环境探索系 统的结合，不仅为多机器人环境探索系统的综合和分析提供了有力工具，而且 赋予机器人群体以自适应能力，使其从相对固定和人工化的环境走向了非结构 化的自然环境，拓宽了多机器人的应用领域。这将在理论和实际中提出一系列 新的问题，从而进一步推动多机器人学的发展，并且在工业、民用和军事等领 域拥有更广阔的应用前景。 1 2 2 代表性研究工作 y a m a u c h i 的多机器人系统是一种完全分布式的控制系统【l0 1 ，即各机器人建 山东大学硕士学位论文 立一幅公用的占有率栅格地图，并引入了“边界”的概念，即接近未探索区域的 已知区域。每个机器人前往离它最近的边界获得新信息，各机器人共享感知信息， 更新自己维护的全局地图并进行行为决策。整个系统的特点可描述为：信息共享， 独立决策，具有较好的鲁棒性。但由于多机器人之间缺乏协调，有可能出现多个 机器人探索同一边界或者重复探索的问题，而且同时运动的机器人对其它机器人 来讲也是一种动态干扰。 s i m m o n s 等采用了另外一种控制结构【4 】：分散探索，集中建图。即利用一个 中央机器人将各个机器人根据各自的传感器信息创建的局部地图融合成一幅全 局地图，各机器人根据各自传感器的传感距离、精度、到各边界的花费、在各边 界可能获得的信息对各边界进行投标，中央机器人在全局地图根据投标，从能够 获取最大的系统效用( 获取的新信息减去花费) 出发，为各机器人分配边界，实 现多机器人的有效协调，这一算法能够保证各机器人之间相隔足够的距离，避免 了区域重叠，提高了探索效率；但缺点是易导致中央机器人成为整个系统的瓶颈， 且通讯量大，对局部变化反应不灵敏。 p a r k e r 等开发的a l l i a n c e 结构【1 8 】是一种完全分布式的、基于行为方法 的机器人控制体系结构，它通过软件的方法定义团队中机器人的控制，以确保整 个团队能够协作地完成给定的任务，其中加入了数学模型化的动机模型来帮助机 器人自动产生具有容错性、适应性和可靠性的行为。 在m a r t h a 计划中，a l a m i 等在由一个中心站和一组自治移动机器人组 成的系统中采用分层式结构来组织协调一群机器人共同工作，并提出了计划合并 机制来实现多机器人之间的合作【1 9 】。其中，中心站负责规划机器人的任务和运行 路线并将其发送给机器人；机器人从中心站接受命令，进行路线规划、轨迹生成， 同其它机器人进行协调，并实时地向中心站报告无法恢复的失败动作。 此外，文献 2 0 】提出了使用多a g e n t 理论解决多机器人、多传感器带来的信 息管理问题，使得系统高度模块化，易于维护和修改。文献 2 1 贝l j 实现了通过进 化算法减少环境模型信息的不确定性。但他们都没有提出一个多机器人协作地图 创建的总体解决方案。 z l o t 等提出利用市场机制解决多机器人协作探索问题【1 1 1 。这里采用了完全 分布式系统，机器人间共享的只有标的信息( 即目标点信息) ，它们之间的协作 通过投标来体现。机器人根据本地地图计算出到达其他机器人目标点的花费作 为投标价格，再按照单项目的第一价格密封标价的拍卖法将标的分给出价最低 4 山东大学硕士学位论文 的机器人；若其它机器人的投标价格均高于底价，则该点由充当拍卖人的机器 人获得。此法有三个优点：一是基于分布式系统，鲁棒性好；二是通讯量小， 只需传递标的和投标信息；三是计算量小。但是由于每个机器人只根据本地地 图计算花费，这就导致大多数情况下各机器人的标的都由自身取得，这表明机 器人间的协作是极其有限的，限制了多机器人系统协作效率的提高。 b u r g a r d 等在文献 1 0 的基础上进一步提出了基于边界的多机器人协同环 境探索策略【2 2 1 ，整个环境由栅格地图来描述，各机器人通过自身传感器扫描周 围环境后得出一组边界点，再计算每个机器人到达所有边界的花费和该边界的 效用，采用效用与花费间差值最大化的思想，通过迭代运算将所有边界分配给 不同的机器人。但是此法的最大问题在于当机器人和目标点数量增多时，可能 的分配方案数呈指数级剧增，从而导致运算时间过长，时效性变差。 1 2 3 多机器人协同环境探索中存在的问题 虽然近年来在多机器人环境探索方面已经取得了不少研究成果，但仍然存 在很多问题，在上节中也对这些问题进行了阐述和对比。多机器人协同环境探 索为随后的机器人定位、构建地图以及后续的其他工作奠定了基础，但未知环 境的不确定性甚至是动态性给多机器人协同探索环境带来了很大难题。采用何 种合理、有效的环境描述方式将会对后续的探索策略的执行带来很大影响，直 接关系到探索策略的复杂程度，同时对机器人的通信能力的要求和整个系统的 实时性也有很大影响，而探索策略的有效性则是实现任务要求的关键。近年来 这方面研究中存在的主要问题如下： ( 1 ) 环境的空间表示方法：目前主要有三种地图模型用来描述机器人所处 的环境：占据栅格法、几何表示法和拓扑地图法【2 3 】，它们各有利弊。基于栅格 的地图表示方法是使用较为成功的一种方法，此法将整个环境划分成若干大小 相同的栅格，且每个栅格的信息直接与环境对应，栅格地图易于创建，机器人 借助该地图可以方便地完成自定位和路径规划。但缺点是：当栅格数量增大时， 地图维护所占用的内存和c p u 时间迅速增长。几何表示法是利用点、线、圆等 几何元素表示地图，因此精度较高，适用于自定位，但缺点是环境表示模型单 一，不宜于描述复杂环境。拓扑图是利用节点间的连线来表示环境位置以及它 们之间的关系，此法适于基于行为的导航，可以实现快速的路径规划，但地图 中包含的几何信息过少，故不适于定位； 山东大学硕士学位论文 ( 2 ) 目标点的选择策略：目前的机器人探索环境比较简单，当面对更为复 杂的动态环境时，存在搜索空间的组合爆炸问题。当机器人和目标点数量增多 时，可能的分配方案数呈指数级剧增，使得求解最优的目标点分配方案变得很 困难； ( 3 ) 基于行为选择的决策理论：在环境探索任务中，对多机器人的角色分 工、群体规范、群体规模等高层次的群体行为与整体绩效的关系还缺乏研究。 虽然已经开展了大量的工作，并取得了不少成果，但都受到了实际应用环境的 限制； ( 4 ) 研究途径：主要偏重于计算机仿真和实验，缺乏数学方面的严谨证明， 无法形成系统性的理论。 1 3 本文选题背景及结构 本文以多机器人对未知环境的协同探索为应用背景，结合山东省科技计划 项目( 2 0 0 6 - - 2 0 0 8 ) “多移动机器人协同环境探索系统研究 ，研究人工智能领 域的免疫遗传算法和人工免疫学方面的免疫网络理论、克隆选择原理等在多机 器人协同环境探索中的应用，并通过仿真实验实现理论与实际相融合。本文的 结构安排如下： 第一章为绪论部分，对多移动机器人环境探索策略的研究意义、发展历史， 以及研究现状进行了介绍，阐述了多移动机器人环境探索过程中存在的主要问 题，并介绍了本文的研究背景和研究内容。 第二章提出了多机器人环境探索中如何分配多目标点的组合优化问题，介 绍了基于决策理论的分配策略【2 2 1 ，但它存在计算量大和时效性差的问题。考虑 到遗传算法具有良好的全局搜索能力，提出了一种基于单纯遗传算法的目标分 配策略。本章对这一策略进行了详细阐述，并在自行开发的仿真平台上进行了 大量的仿真实验对其做出验证。本章的最后是内容小结。 第三章针对前一章中单纯遗传算法存在的早熟收敛问题，进一步提出了一 种基于免疫遗传算法的多移动机器人协同探索策略来解决多机器人选择多目标 点的组合优化问题。不仅利用了基于相似矢量距的选择概率计算方法来保证抗 体的多样性，并且在免疫遗传算法的基础上引入了自适应遗传算法的思想，以 实现对交叉和变异概率的自适应调节。并通过仿真实验给出了详尽的验证。本 章的最后是内容小结。 6 山东大学硕士学位论文 第四章首先介绍了生物免疫系统的一些基本原理，包括它的功能、特点和 工作原理，然后介绍了生物免疫机制与人工免疫系统之间的关系，并重点阐述 了人工免疫系统的定义和研究范围、发展历程以及几种典型的人工免疫网络模 型。介绍了免疫系统相关原理应用于多机器人系统方面已有的研究成果，进而 借鉴生物免疫系统的特性建立起动态分布式的多机器人系统，并在此系统基础 上结合人工免疫相关机理，提出了一种基于免疫网络的目标分配算法。最后在 仿真实验部分，通过不同环境模式下的多次实验给出了相应的结果分析，以验 证算法的有效性和稳定性。本章的最后给出了内容小结。 第五章首先概述了克隆选择学说的基本原理，然后重点介绍了最具代表性 的克隆选择算法( c l o n a ls e l e c t i o na l g o r i t h m ，c l o n a l g ) ，包括算法流程、 应用、不足之处以及其他研究人员所做的改进。为了进一步优化多机器人环境 探索的行为策略，提出了一种改进的克隆选择算法( i m p r o v e dc l o n a ls e l e c t i o n a l g o r i t h m ，i c s a ) ，针对c l o n a l g 中二进制编码的计算量大的缺点，选用 实数编码的候选解为抗体，且算法中采用了可自适应调整的克隆操作和柯西变 异算子，以提高对局部解的搜索能力和保证抗体群的多样性。将此算法应用于 多机器人探索的决策机制中，最后通过仿真实验与c l o n a l g 进行对比，以验 证i c s a 的有效性，并给出了实验结果分析。本章的最后是内容小结。 最后对全文进行了总结，指出了文章的创新点，并对相关工作进行了下一 步展望。 7 山东大学硕士学位论文 第二章基于单纯遗传算法的多移动机器人协同探索策略 多机器人协同环境探索要解决的关键问题是为每个机器人选择合适的目标 点来让其同时探索环境中的不同区域。多机器人的目标点分配问题属于n p 问 题，由于遗传算法具有良好的全局搜索能力，本章提出了一种基于单纯遗传算 法( s i m p l eg e n e t i ca l g o r i t h m ，s g a ) 的目标分配策略，并同时考虑到机器人到 达各目标点的花费和相应目标的效用。当机器人选择了某具体目标点后，该目 标周围未探测区域的效用值相应降低。并且通过大量的仿真实验证明：这种方 法能有效地分配环境中的机器人来快速完成任务，且计算量明显下降。 2 1 引言 在完全未知的环境中，由机器人自主地依靠其自身携带的传感器所提供的信 息创建环境地图是移动机器人学中一个极具挑战性的问题。完全未知环境，即机 器人对环境一无所知，不存在任何先验信息，包括环境大小、形状、障碍物位置 等，这正是许多应用环境的特点。在探索这种未知环境的过程中，机器人创建地 图行为的完成必须依赖于其传感器所获得的信息。这里的“探索 可定义为：从 未知或部分已知的环境中收集相关信息。探索是创建地图的基础，创建地图就是 在探索未知环境的过程中，确定机器人所感兴趣的实体( 如目标点、障碍物等) 在某坐标系中的位置。而“探索策略”是指在机器人创建地图过程中的行走行为 策略，其目的在于确定目标点，它是机器人感知与行为间的决策模块。 在环境探索和地图创建方面，与单机器人相比，多机器人系统具有可拆分 性、可重构性、容错性和鲁棒性等优点。多个机器人并行作业，减少了完成任 务所需要的时间。使用多个机器人同时进行地图创建，不仅提高了任务执行的 速度，而且多个机器人的感知范围必然大于单个机器人，通过融合多个机器人 的感知数据可以提高地图的精确度。但是多机器人系统也带来了新的问题，就 目前的研究水平而言，多移动机器人系统的设计、实现和使用并没有太多经验。 而多机器人环境探索策略的制定要比单个机器人环境探索策略的选择复杂得 多，关键问题是如何协调多个机器人的行为来避免它们之间的重复探索和目标 点冲突，从而发挥整个系统的效用以获取更多的环境信息，这又成了新的难题。 8 山东大学硕士学位论文 在y a r n a u c h i 提出边界的概念以前【丌，移动机器人的环境探索策略都是简 单的沿墙行走【8 】或随机行走【9 】等被动的探索策略，只适用于结构化的较小环境， 探索效率低。文献 1 0 】中，y a m a u c h i 提出各机器人建立一幅公用的占有率栅格 地图，并将邻近未知栅格的空白栅格定义为“边界”，机器人通过不断寻找新 的边界，逐步完成对未知环境的探索。各机器人共享感知信息，独立决策，但 由于多机器人之间缺乏协调，有可能出现多个机器人探索同一边界或者重复探 索的问题。因此，如何合理地分配边界点来实现多机器人协调、有效的探索成 为了关键。s i m m o n s 等利用一个中央机器人将各机器人的局部地图融合成一个 全局地t 虱t 4 1 ，各机器人根据自身传感器的传感距离、精度、到各边界的花费、 在各边界可能获得的信息对各边界进行投标，中央机器人在全局地图根据投标， 从能够获取最大的系统效用( 获取的新信息减去花费) 出发，为各机器人分配 边界，实现多机器人的有效协调，这一算法能够保证各机器人之间相隔足够的 距离，避免了区域重叠，提高了探索效率；但中央机器人易成为整个系统的瓶 颈，且通讯量大，对局部变化反应不灵敏。 2 2 多机器人选择多目标点的组合优化问题 2 2 1 目标点的定义 多机器人协同环境探索的最终目的是在最短时间内覆盖整个环境。本文利 用了文 7 ，1 0 中“边界的概念。整个环境用栅格地图来描述，每个栅格单元 对应该单元是否有障碍的概率( 即占有概率) 。占有概率的环境描述方法反映 了多种常用传感器( 本文采用了声纳) 的感知模型。在初始状态，各栅格的占 有概率都设为0 5 ，随着探索的逐步深入，通过多传感器数据的不断融合来更 新这些占有概率，从而将各栅格划分为有障碍、无障碍和未知三种状态。边界 是邻近未知栅格的空白栅格，而这些栅格如果连成一个区域，则称为边界区域。 当机器人运行至边界时，易于获得更多的关于位置区域的新信息。因此，我们 将边界定义为机器人有可能到达的目标点，在本文的实验中，通常取任意一段 连续边界上的一点( 一般为中点) 作为目标点。在探索环境的过程中，要解决 的关键问题是如何确立各机器人的目标点以提高探索效率。机器人每完成一次 对周围环境的探索，就会得出系列新的边界点。如果将所有边界点作为机器 9 山东大学硕士学位论文 人的候选目标点，那么提高探索效率的问题就转化为各候选目标点与各机器人 之间的组合优化问题。 2 2 2 花费的定义 机器人最终选择哪个边界点作为下一步的行走目标点，必然首先要考虑它到 达各边界所需的花费值。由于这里采用了占有概率的环境描述方式，我们很容易 将花费的计算与栅格数联系起来，此处借用了文献 2 2 1q b 的算法。机器人经过一 个栅格( x ，y ) 的花费k ) 与该栅格的占有概率尸( d 矽) 成正比。两点间的花费计 算就是寻找它们之间途径栅格的花费累计最少的一条路径。这里使用了动态规划 中的值迭代方法，计算从当前机器人位置到所有目标点的最优路径。最小花费值 的计算可分为两步： 初始化： ，卜怪萋潆懈胁姗觯元 亿， 迭代更新： ，卜嬲秒一+ 缈+ 厨可p ( 叱+ a x , y + a y ) ( 2 2 ) 6 = 一1 0 ，1 因为目标点的位置都是明确的，因此必能保证此算法收敛。那么每个花费 值实际上是到达对应目标点的累计的花费值。 2 2 3 效用值的定义 接下来需要计算机器人对于目标点的效用值，因为这部分计算要考虑很多 因素，所以效用值的计算就显得很复杂。计算某边界点对于一个机器人的效用 值，要考虑已分配的边界到该待分配边界点的距离，并考虑若机器人已经到达 已分配的边界，该待分配的边界点是否在其感知范围内。此处借鉴文献 2 2 】的 思想，根据机器人声纳可以覆盖栅格的概率值来计算效用值。具体算法如下： 所有边界的效用均初始化为同一个值； 若机器人选择目标点为r ，计算f 周围距离d 处的栅格被机器人声纳覆 盖的概率尸( d ) ： 1 0 山东大学硕士学位论文 ) ：j 1 0 一面d( 狄垅a x _ r a n g e ) p ( d( 2 3 ) = 忉织加孵 、 ( 2 3 ) 1 0 其它 上式中：m a xr a n g e 是声纳传感器的最大探测范围。因此当机器人到达目 标点r 时，离指定目标点f 距离为d 的栅格，将会被机器人声纳覆盖的概率值 即为e ( d ) 。 假设有1 1 个边界点，乞，乙，且 ，乞，t n 一。已经分配给机器人 1 ，2 ，n 1 ，则乇的效用值可用下式计算： u ( ot , ，气一1 ) = 一p ( t n - - t ，0 ) ( 2 4 ) 其中，u ( ) 表示边界点的效用值。由式( 2 4 ) 可见，同一时刻向乇运动的机器 人的数量越多，则乙的效用值越低。 2 2 4 基于迭代运算的分配策略 探索过程中，各机器人利用传感器对周围环境进行扫描可得出一组有效的 边界点，然后计算每个机器人到达各边界的花费值( c o s t ) 和该边界的效用值 ( u t i l i t y ) ，采用u t i l i t y f l 宰c o s t ( 为一预设权重值) 的差值最大化的思想将这 组边界分配给各机器人。这里使用了动态规划中的值迭代方法，每次循环中计 算出u t i l i t y t p * c o s t ；值最大的对应元组( f ，t ) ，f 为机器人编号，t 为边界点序 号，反复循环直至所有边界都分配给机器人。但是文献 2 2 提出的决策理论方 法存在的主要问题是：当机器人和目标点数量变大时，可能的分配方案数呈指 数级剧增，从而导致运算时间过长，时效性变差。 2 3 基于单纯遗传算法的目标分配策略 由于遗传算法具有良好的并行运算和全局搜索能力，所以我们想到用它来 解决上述问题：将u t i l i t y f l * c o s t 定义为适应度函数，先随机地设定一批分配 方案作为初始种群，再通过选择、交叉和变异操作在经过一定的遗传代数后得 出一个较优的分配方案。 山东大学硕士学位论文 2 3 1 遗传算法简介 遗传算法( g e n e t i ca l g o r i t h m ，g a ) 是一种模仿自然界生物进化机制发展起 来的随机全局搜索和优化方法，它利用从自然界选择、遗传操作中抽象出来的 几个算子一复制、交叉和变异操作，对参数编码的字符串进行遗传操作，每 一字符串对应于一个可行解，这种遗传操作是对多个可行解组成的群体进行的。 它的主要优点是：采用群体方式对目标函数空间进行多线程的并行搜索，交叉 和变异操作使可行解之间交换信息和产生新的可行解，不会陷入局部极小点； g a 只需要可行解目标函数的值，而不需要其它信息。对目标函数的连续性、 可微性没有要求，因此使用方便；解的选择和产生采用概率方式，具有较强的 适应能力和鲁棒性。 2 3 2 染色体编码及初始种群的产生 染色体采用十进制编码，每个基因位代表一个机器人序号。一条染色体表 示一种可能的分配方案。由于仿真实验中设定了三个机器人，故足 1 ，2 ，3 ) ( 汪1 ，2 ，n ) 。 染色体总长度n 等于目标点数 图2 1 染色体的编码 初始种群是随机产生的，种群规模设为4 0 个。 2 3 3 适应度函数 遗传算法在进化过程中以种群中每个个体的适应度函数来进行搜索，因此 适应度函数的选取直接影响到遗传算法的收敛速度以及能否找到最优解。我们 将待求解的目标优化函数直接转化为适应度函数，即： f i t n e s s2u t i l i t y - f l * c o s t ( 2 5 ) 上式中的决定了效用值与花费值之间的权重对比。实验表明：当 【o 0 1 ，5