（电路与系统专业论文）移动机器人在未知环境下的自适应路径规划[电路与系统专业优秀论文].pdf

摘要 摘要 路径规划是移动机器人研究的一个基本而又极其重要的课题。灵活有效的路 径规划算法能够帮助机器人适应各种复杂的环境，大大提高机器人的应用领域， 尤其是使移动机器人具备自动识别环境的能力，能在未知环境下完成一定的工 作。 本文针对移动机器人在未知环境下的路径规划作了下列工作： 1 ) 分析了现有算法，如几何顶点法，栅格法，人工势场法，随机法等等的 特点和优劣。在此基础上，还分析了未知环境下路径规划的特点和难点，并且对 每种算法，比较了在未知环境中实现的可能性和有效性。 2 ) 对人工势场法作了深入的探讨。由于很少有文献讨论人工势场法参数选 择问题，本文详细的探讨了这一问题，并且通过仿真来说明参数选择策略的效果。 本文还研究了如何将人工势场法和运动约束条件相结合，提出了碰撞风险的概 念，使人工势场法能够适用于动态的环境中。本文还分析了人工势场法的缺陷以 及产生的原因，并且分析了已经产生的一些改进方法的实质和局限性。 3 ) 在已知环境下通过仿真比较了随机法和人工势场法的优劣，进一步证明 了人工势场法的优点：避障算法简单，实时性好，与其他算法的结合性好，对环 境的适应性高。 4 ) 仔细分析了已知环境下和未知环境下路径规划的不同，并分析了人工势 场法在未知环境下的缺陷。提出了几何信息法来克服之字形路径和局部最小，利 用参考方向来解决路径徘徊。为了优化路径，本文还提出了针对环境的复杂程度， 动态改变机器人步长的策略，利用前后两次方向角的改变来判断环境的改变程 度。通过增加步长缩短了路径规划的时间，同时也部分的克服了路径徘徊等人工 势场法的缺陷。 关键字：移动机器人、路径规划、人工势场法、自适应算法 中图分类号：t p 2 4 2 6 摘要 a bs t r a c t p a t hp l a n n i n gi sab a s i ca n di m p o r t a n tt o p i ci nt h em o b i l er o b o tr e s e a r c h f l e x i b l e p a t hp l a n n i n ga l g o r i t h mi sh e l p f u lf o rt h er o b o ti nv a r i o u sc o m p l i c a t e de n v i r o n m e n t s ， s ot h a tt h ea p p l i c a t i o na r e ao fm o b i l er o b o ti se x t e n d e d e s p e c i a l l y , w h e nt h er o b o t h a st h ea b i l i t yt oj u d g et h ee n v i r o n m e n t ，i tc a nf i n i s hs o m eo r d e r si na l lu n k n o w na r e a i nt h i st h e s i s ，ih a v ec o n t r i b u t e dt h em e t h o d so fp a t hp l a n n i n gi nt h eu n k n o w n e n v i r o n m e n t ，i n c l u d e s ： 1 )a n a l y z et h ea d v a n t a g ea n dd i s a d v a n t a g eo fm a n ya l g o r i t h m ss u c ha s g e o m e t r yv e r t e x ，g r i d ，a r t i f i c i a lp o t e n t i a lf i e l d ，r a p i dr a n d o m i z e dt r e e s ，a n de t c a n dt h e nd i s c u s st h es p e c i a l t ya n dd i f f i c u l t yo fp a t hp l a n n i n gi nt h eu n k n o w n e n v i r o n m e n t f o re a c ha l g o r i t h m ，t h i sp a p e ra l s oh a ss t u d i e dt h ep o s s i b i l i t ya n d v a l i d i t yw h e n i ti sa p p l i e di n t ot h eu n k n o w ne n v i r o n m e n t 2 ) s t u d yt h o r o u g h l yt h ea r t i f i c i a lp o t e n t i a lf i e l d ( a p e ) f i r s t l y , t h i sp a p e r s h o w st h es t r a t e g yo f h o wt oc h o o s et h ep a r a m e t e r s ，w h i c hi sr a r e l yd i s c u s s e db e f o r e s e c o n d l y , t h i sp a p e rd e v e l o p sc o l l i s i o nr i s kt oc o m b i n et h ea p fw i t hm o t i o n c o n s t r a i n s ot h a ta p fc a nb eu s e di nd y n a m i ce n v i r o n m e n t t h i r d l y , t h i sp a p e r e x p l a i n sw h e r ea p f sb u g sc o m ef r o m a n ds o m em e t h o d st oo v e r c o m eb u g s 3 )b yc o m p a r eb e t w e e nr a n d o m i z e dt r e e sa n da p f , t h i sp a p e rc o n c l u d e st h e a d v a n t a g eo fa p f ：s i m p l e ，t i m e l y , b ee a s yt oi n t e g r a t ew i t ho t h e ra l g o r i t h m s ，a n db e u s e di nv a r i o u sk i n do fe n v i r o n m e n t s 4 、t h i n ko v e rt h ed i f f e r e n c eb e t w e e nk n o w ne n v i r o n m e n t sa n dn n k n o w n e n v i r o n m e n t s a n dt h es h o r t c o m i n go fa p fi nt h el a t t e r t h i sp a p e rd e v e l o p st h e g e o m e t r ym e t h o dt oo v e r c o m et h ez i g z a gp a t ha n dl o c a lm i n i m u m ，a n du s et h e r e f e r e n c ed i r e c t i o nt os o l v et h ep r o b l e mt h a tt h er o b o tw i l lw a n d e ri nal o c a la r e a t o o p t i m i z ea p f t h i sp a p e rd e v e l o p sam e t h o dt oc h a n g et h ep a c ed y n a m i c a l l y , a c c o r d i n gt ot h ec o m p l e x i t yo f e n v i r o n m e n t s i nd e t a i l ，t h ec h a n g eo f m o t i o nd i r e c t i o n i sc a l c u l a t e dt od e c i d eh o wt oc a l i b r a t et h ep a c e t h i sm e t h o dc a nr e d u c et h e a l g o r i t h m sr u nt i m e ，a n dp a r t l ya v o i dt h el o c a lm i n i m u m k e y w o r d s ：m o b i l er o b o t ，p a t hp l a n n i n g ，a r t i f i c i a lp o t e n t i a lf i e l d ，a d a p t i v e a l g o r i t h m 4 第一章弓| 害 第一章萼l 言 人淡一直梦想熊够设计一种机器人帮助我们从事危险的工作，到达人类无法 到达懿也点进行探索鞍开发，取代人类从事繁震露单调的工终。最近，美溺的“勇 气”号登陆火星逾行囊动搽测，这代表了强蓊机器人的最篱技术水平。机器久技 术的出现和发展，不但使传统的工业生产面貌发生根本性变化，而且将对人类的 社会生活产生深远的影响。 嘏嚣天菠末集合了力学，税壤学，毫孑学，生耱学，狻涮论，；冀撬，人工 智能，系统工程等多种学科之大成，是一种综合性很强的新技术，也是当前的热 门研究领域。 1 1 梳器入概述 从篇一代机器人，也就是1 9 4 8 年诞生于荚国阿贡实验窭的遥控机械手发展 到今天，税器太援术邑经经历了三令主要泠段 1 】： 第一代机器人怒具有记忆，存储能力的示激再现机器人，不考虑反馈因素。 它们装有记忆存储器，由人将作业的各种操作腰求示范给机器人，使之记住操作 的程序秘要领，当它接到再现愈令时，则自主城模仿示教动l 乍行事。示教蠹蜜为 机器入搽于# 祝稳秘象间轨迹，壬箬濂条件，佟攮顺序等。示教方法或是操体员“手 把手”的直接做，溅是和计算机编程相结合。 第二代机器人怒适应性程序控制机器人，也日q 有感觉的机器人。它们是具有 菜些惑觉装置，l 获取俸盟琢凌，操终对象懿褥萃羡惠，j 羲遗计冀褪楚纛，分辛厅， 机器人做出一定的推理，对动作避行反馈控制，表现出低级的智能行为，比第一 代机器人更灵活，盟能适应环境变化的需要。 第三代秘器人楚舞能枫器人，具有第二代狡器大的感酝功能和篱单瓣囊逶应 能力，它有灵活的怨维能力和较强的自我适磁能力，可以落行复杂的撬划，判断 与决策，能在作业环境下独立工作。它是人工错能，计算机技术与工业机器人三 者相结合的产物，目前处于实验探索阶段。 本文掰要摇述瀚移动瓿器久麓予第三霞概器入，它遵；蹙绩惑器获知蠲围豹繇 境信息，并且能够根据不同的环境进行复杂的判断和决策。 1 。2 移动提器入概述 第一帝弓 富 智能移动机器人是机器人研究领域的一个重臻的分支，智能移动机器人集成 了人工餐髓，餐l 拣捌，售感处联，鹜像楚瑾，捡测积转换笛专、监技术，跨诗雾 机，自动控制，机械电子等多门学科 3 0 。 1 9 6 9 年，斯坦祸研究院的n i l s s e n 设计了一个移动机器人，目的是为了研 究应用人工智能技术，在复杂环境下枧器人系统的自主推理，规划和控制。这是 煎赛上檠一夺稳蔫人工智麓的方法设计靛移动枫器入。在上个超纪荬实年代，磷 究人员的重点放在固定机器人领域中，然而到了八十年代中期，人们对移动机器 人的研究呈爆炸式的发展。许多公司开始设计，制作和销售移动机器人平台，这 些平台棱_ 蓦l 予臻究号教育嚣载。在摄短鞠时阉蘩，塞主移动瓿器入裁引越了全蓬 界的广泛注意，尤其是在美国和日本。他们在该领域的研究发展很快，取褥了处 于世界领先的成果。 从餐2 机器人系统建度看，枧器人要实现与周围环境交互的能力应该具有以 下凡个方蓓： a 通过传感器视觉系统获取外部环境的倍恩 b 通过内部数獭库匹配环境信息，使机器人能理解外部环境 e 擞窭逶当嚣逡动矮翊以扶行惑定夔任务 d 处理外部突发事件 e 从以往的经验中学习，提离自主能力 麟畿理工学院人工智能实验塞的科学家提出了包孕结襁。包孕结毒句怒对传统 的入工餐能理论辩熬大突破。 篷认为移动祝器a 的控制阔蘧应浚按照芎亍为方式来 分解，而不是按照功能组件来分解。用这种理论设计的移动机器人能够在仅使用 超声波传感器和红外线传感器的情况下就可以自由的运动，不会碰上障碍物。这 拿结弱罐篷螽，也簸蹩主令遣纪0 年找，缀多磅究久虽 乍了大量的工 乍，发表 了大量的文献，采用了许多软计辫技术，如神经网络，遗传算法，模糊拽术等。 目前，在智能机器人领域中，有两种基本的技术被广泛的使用：反应方法和精确 推理的方法。但是纯姆戆反应方法设计不自应髑子定位问题，出于它是壹谈透过 传感嚣信号来指引毫疆瓣入的运动攒令，因此它溉不能对未来进行规翊，又不能通 过过去的经验进行推理。 用精确推理的方法建立世巽横型来阐明规划，反应式导航应用较灵溜，但是 当瑟稳鞍嚣难戆任务时，缦可麓失致。毽是，羧臻接瑾兹方法诗算量较大，在动 态环境下的可行性不好。传统人工智能研究者认为机器人应该能够理解不同的环 境并能够采用不同的方法。移动机器人研究的最终的目的就鼹设计一个机器人能 够安全躲在筵险的环境中完成任务，著虽够成功躲避开所有障碍甥。闲此移魂 机器人的一个基本特征就是要其备躲避障碍物的能力。 6 第一章弓 富 对予地面上的移动机器人来说，它可分为率轮式机器人，脚式机器人，躯干 式捉嚣人等。按照搬器入是否要接受外爨指令m 寒分，又可以分为叁主式秘# 叁主 式祝器人。自主式机器人不需要外界提供控制指令，所有的控制决策都幽螽行完 成，这增加了机器人的灵活性，扩大了机器人的使用范围。 移动机器人的研究具有以下几个关键领域： ( i ) 导靛；移动稷器炎辑究熬一个重要同麓。可以分为：基予环境僖患豹逮 图模型贩配导航，旗于各种导航信号的路标导航，视觉导航，味觉导航等。 ( 2 ) 定位：移动机器人必须舆备的基本技术环节，确定机器人在地图中的坐 蠡。蔽据环境鼹复杂瞧，定位方法鸯多秘多襻，其中主要的方法专：谈缝定位， 路标定位，声音定位，预测定位。但是在环境未知的情况下，机器人无法根据环 境来定位，路标定位失去了作用。又因为运动襻在着打滑，漂移等误差，使用惯 性定位也会产生很大的误差。垦翦流行的方法楚采用卡尔曼滤波来消除运动误差 1 7 】 1 8 】 1 9 ，箔计祝器入下次静坐标。 ( 3 ) 路径规划：假设机器人知道导航方向和自己的坐标，接下来就要究成路 径规划的任务。路径规划是自主式桃器人导航的基本环节之。它按照巢性能 据蠡援豢一条扶莛始狻态至l 基栋状态翡最饶或逐 鼙最傥懿纛磁鼹径。凝攥环境筵 息的已知或部分未知或完全未知，路径规划的难度也逐渐上升。总的来说，机器 人通过传感器对机器人的工作环境进行探测，根据传感器返回的信息，估计障碍 物的位嚣，形状，从蕊进行规划。 ( 4 ) 多传惑嚣信怠的融合：出于信息采集等段的多样浚和信息静多弹性，使 得对信息的融合技术成为研究人员关注的话题。由于测量中的误差因索存在，传 感器的反馈信息并不能真实反映环境的情况，误差在以后的处理过程中将被累 稿，澍计算结果夔爽实毪产生重大豹影暖。瓣魏，主要剩磁一些信号娃溅褒论， 对信息进行抽取，熬台，过滤等处理，常用方法有加衩平均法，贝叶斯估计，卡 尔曼滤波，神经网络和模糊法则等。 ( 5 ) 多机器入协l 乍系统：隧麓机器人应用领域鳃不断耀展，机器人工传环境 复杂渡船重，蔹褥不褥局限予单个机器入鲍研究。多枫器入协作系统主癸研究在 给定一个任务后，如何组织多个机器人分解任务，相互通信，相互协作最终完成 任务。 农实舔粒疆究遘疆孛，以上豹蔽末是稳互缀合戆，衢生逡诲多有趣涎磷究方 向 2 3 4 5 “ 。对于单个机器人，导航，定位，路径规划，多信息的融合 等技术都是必不可少的。有了多怅息的融合技术才能使机器人得到尽可能准确的 环境德崽，才有可能定位和路径溉划。有了定位技术，枫嚣人才能够知邀鑫己的 坐标，才能明确鼹掇规翊的起始点坐标。 7 第一章q i 善 本文的主要研究对象是未知环境中的路径规划问题。本文不考虑传感器的测 量诿差，运动误麓等因索的影响。 1 3路径规划的概念和意义 路径规划问题源于计算机几何学的传统研究课题。七十年代中期，智能机 器入研究的需求，促进规划问题的研究。因为装配机器入，移动机器人都涉及到 路径规划技术。c a r n e g i em e l l o n 大学的机器人磺究所予1 9 9 3 年完成了睦上枕 器人在未知环境和动态环境下路径规划的研究，并于1 9 9 4 年完成了导航试验。 该黢子1 9 9 5 年完成了爨动驾驶车横跨美莺鹚实验，时逮8 0 酗h ，全糕鑫动驾驶 率为9 8 。b o s t o n 大学利用立体视觉及超声距离传感器实现了对物理世界的标 国。o h i o 翔立大学暴确大小不瓣鹃抚器，以 办调静方式来进行绘铺氇瀚。 j i w 档成1 t m 0 r 蚺合谜成豢什 r 请舟柠制桀什 ，“乍l f i l 辨豫乍j j 奠城终的执 飞 路 _ ；娃辘照方程 辖乃寰y 鹜 辛j l 器a 运动规划麓灏稚 c a l i f o r n i a 大学利用神经网络来表示机器人工作环境的自由空间。可以说，智 能移动机器入的研究在全世界范围内被广泛的开展。 由于路径规划的复杂性，不同的磺究考从不粥蛇角发硬究菜一方藏躲闷送， 对具体问灏的提法也不完全相同。典型的路径规划问题的提法怒指在有障碍物的 工 肇环凌孛，翅露为瓿辨人寻找扶起点裂终点戆运动路径，诖撬器入在运动遭程 中熊安全，无碰撼的通过所有的障碍物。我阁学者蒋新松为路径规划作了这样的 定义：路径麓刘怒备治式移动机器入静兮羹要组成部分，它的任务就是在其有 障碍物的环境内按照一定的评价标准，寻找一条从起始状态( 甑括位鼹和姿态) 到达目标状态( 包括位溉和姿态) 的无碰路径。 一般说来，路经规划褥到既是一条凡便路经，零 t 说暖了照经嫂魁在整令 导航过程中的作用。首先，利用路径规划算法得到一条无碰撞的几何路径。这样 的一条凡键路径不能够应瘸予实际豹移饕撬器太，因为它是不迤续静。第二疹把 几何路径转换成一条连续的，可执行的路径。第三步，根据实际中机器人的速度 约束条件怒可魏行的路径装抉成机器入静移动轨迹。最君，结合机器人的控制方 第一章g | 青 程，得到机器人可以实现的路径。 实舔豹鼹经趣鲻冀法 ：主往会考虑型攀三步，也裁是援嚣久搴鸯懿速爱终寨。 因为漳碍物可能是以一定速度移动的，如采障褥物移动速发太快，即使机器人在 缓慢的丽进，也会由于相对速度的增大而大大摁高碰撞的机率。第四步的控制方 程也经耀是被结合在路径规划算法之内的，如聚路径是不可按鸵，那么这热路径 是没有意义豹。覆楚第二多孛匏辫径连续注阉繇，路径鬣翔往往不予考虑。在产 生路径以后，由特爨的方法光滑路径 6 。 八十年代初，t l o z a n o p e r e z 的位姿空间法，r a ，b r o o k s 广义锥法使规划 惩题黪疆究褥到了逡一步鹭发袋。链谈为环境戆表达会影l 囊裂鼹径黪攘索， k h a t i b 和k r o g h 提出的人工势场法考虑到了枫器人的动态性能及直接控制。随 着研究的深入，位姿空间法及人工瓣场法得到了广泛的应用并发展成为两种较为 成熟的规划方法，并在此基础上产生了许多类似的方法。 路径蕊翔闯遂懿磷究涉及到环境表达，亵翊方法，路径执行。环境表达有两 层含义，其一是有效的获取环境信息，这与传艨器相关：其二是如何将环境信息 有效的波达出来 7 8 。规划方法关心的是在环境表达的基础上，采用有效的方 法鼹矧鼹经莠显遂纾蠛纯。路径靛执行与疯层拣秘密甥辐关，并量考意掇爨久茨 动力学特性，即如何控制机器人按照设定的路径行走。 路径规划目题已有的研究方法可以分为全两型方法，髑部型方法以及混合型 方法三秭。 ， 全局规划方法依照获取的环境信息，给机器人规划出一条路径。规划路径的 精确程度取决于获耿环境信息的凇确程度。全局方法通常可以寻找最优解，但是 需要联先躲遂繇凌豹准确信息，劳显诗算量缀大。 局部规划方法侧匿于考虑机器人当前的局部环境信息，让机器人具有良好的 避撞能力。很多机器人导航方法通常是局部的，因为它的信息获取仅仅依嚣传感 器系统获取的信息，劳且随着环境躲变证实时圭| 曩发生变化。和全是方法比较，局 部甄到方法更具有实时性和实蠲羧。缺陷是仅仅依靠局部信息，有时会产生局部 极点，无法保证机器人顺利到达瞄的地。 混合型方法试图结合全局和周部的优点，在局部规划的蕊础上结合全局信息 考虑，钛瑟竞爨嚣菇豹袋点。 从机器人工作环境的角度区分规划方法，w 以分为静态确定环境和动态时变 环凌。路径趣划可以鼹限制性的，也可以是菲隈刳性的。这取决于对枫器人的运 动除避障之矫还有没蠢其他的约寐条俘。 9 第一章弓| 蠢 另外，根据完整性还可以把路径规划算法分来确定型和肩发型两类。确定型 篓法可以我到一个润麓夔答塞，襄发型致力予在较短夔时润蠹技窭耀越戆答案， 但可能无法给出一个问题的最优解。 移动机器人路径规划问题在理论上主要存在三个子问题： a 环境表示润题：指环境中黪碍物的表示酾垂由空间麴表示。合理筑环境 表示才麓有穰于裁划中搜索羹瓣减少，才能有掰于算法开销的减少。 b 寻空间问题：在某个指定区域r 中，确定物体a 的安全位置，使它不与 已有的其他障碍物相碰。 e 罨路径超题：在莱令撵定甄壤r 中，镄定锈搏a 放拐始位鬟移动到嚣标 位置钓安全路径，镁得移动过程中不发生碰撞。 路径规划问题具有如下特点： a 复杂性：在复杂环境尤其怒动态时变环境中，祝嚣入路径规戋l 菲常复杂， 而且需疆很大的计算凝。 b 随机性；复杂环境的变化往往存在很多随机性和不确定因素。动态障碍 貔熬窭瓣也豢有夔瓿性。 c 多约束：机器人的运动存在几何约束和物理约束。几何约束是指机器人 的形状制约，而物理约束是指机器人的速度和加速度。 d 多嚣标：机嚣人运动过程中路径性能要求存在多静联标，如路经最短， 、f 1 ：二二：y 图1 , 2 机器人运动规划的流程 对麓壤糖，安全整戆最磐，疑源游耗最小。毽它销之润往经存在冲突。 按照环境表示方法的不同，可以把路径规划算法分成以下几类： ( 1 ) 几何法： 几何法角凡褥潮形来籀述簿褥物，通过撼淑环境的几何特征，把遗豳映射到 一张类似于拓扑图的图上，这样就把路径规划问题转换成了一个简单的图搜索问 第一章弓l 富 题。几何法的关键在于如何划分自由空间和障碍空间。 琰点霾法是一耱麓攀鼹尼遐法，它把障强镌纛l 毒死嚣鬻澎，鼹弪霆建立在每 个障礴物的顶点上的，把自由空间中各个障碍物的顶点连接灏来，这样的线段的 集合就是一条无碰撞的路径。然后通过一定的代价函数来筛选得到最优路径。如 图l 。2 ，这零孛方法要求能够精确的控制机器人剃达障碍物的顶点附近，这在实际 中较蕊实现。 因此出现了v o r o n o i 法。处于对安全和实际应用的简单性的考虑，希望机 器人与障碍物能够保持一定的距离。v o r o n o i 圈用一系列的节点定义，这般节点 到瓣i 夏戆嚣个或多个障碍兹数边缘是等距离簿。然后把撬器入豹工馋空鹈划分或 若干箧城，每个区域只包含一个障碍物的边缘。对于一个区城中的任何一点，他 到该区域所包含的障碍物边缘的距离比到其他任何一个区域近。这样，无碰路径 就可以锻快找到了。两且计算速度很快。 死俺法在二维奎闻的性能缀好，但是，在三维空阉帮多个漳碍秘翁条件下， 复杂性和计算时间大大增加。 ( 2 ) 栅格法 把熬令建霭空藏划分为诲多小臻疆，按照骞嚣终是否包含溅褥物甏裰臻分为障 碍单元和自由单元两类，那么自由单元的集合就是自由空间。在分解栅格的同时， 计算单元之间的邻接关系。然后把起点单元和终点单元之间的连续的单元格连接 起来，瓤褥到了一条无磁路径。掇椿法篾单易蠖，但是计算爨大，如暴搬梅太大， 就会浪费很多自盘空润，如果秘嵇太小，瓣稽数量尉增，计算量也搔数缀增加 考虑到自由空间在整个空间中占绝大多数，如果可以把多个自由栅格合并成 一个大的栅格，将会大大降低计算爨，因此，单元树法应运而生。以四叉树为例， 首先藏熬今遣萋分戏鞠个大枣稳麓弱繇瞧，考察每令撩摄，如果是蜜枣掇穆或者 障碍栅格，就停止该节点的生长。如果该栅格既有障碍物，又有自由空间，就再 分成四个小栅格，以此类推。这类方法在一定狂度上减轻了计算量，并且简单易 实现，霸此成为诲多混合型算法豹必备算法。 ( 3 ) 入工势场法 在电势场中，带电粒子一定会向势场低的方向运动。利用这一原理，人为的 在地图中构建一个势场，使得目桥点的势场最低，障碍物的势场最高。这样，机 器入裁会囊羞势绣爨低豹方蠢运韵。关于人王势场法嚣具体瓣蓬窝实臻，将在第 二章作详细的阐述。 ( 4 ) 随机法 以枫器人的最秘坐标点为起始点，按一定敬隧捉规则往器个方 每生成一擐隧 税树，囊至起始点和疆标点都成为这裸树的其中两个节点为丘。然后在褥中搜索 第一章弓l 害 这两点之问的一条最短路径。这就是随机法，详细原理将在第三章阐述。 ( 5 ) 逡传算法 遗传算法模拟生物的进化过程，是一种全硒优化算法。标准算法如阁： 图中，选择，交叉，变异是三个主要步骤，通过不断的避代，筛选，得到越 来越优的个体。遗传算法褥到的解往往是高质爨的，但是如聚缺乏合适的逡应度 函数秘参数，迭代次数巨大。雨量，遗传算法簧要有超始豹游路径 乍为第一次这 代的父样本，这需要其他的规划方法产生。所以遗传算法大多应用于需要最优解 的情况。 上蠢贪绥爨都怒一些基本戆爨径疆划算法，每耱方法都蠢冬鑫懿撬点器不是 之处。蟊前，随着智能移动机器人的应用范围不断扩大，未知环境下的自主导航 成为研究的热点，这就对机器人的避障能力提出了更高的要求。目前，主骚是取 长补短，结合多种路径规划方法来进行综合规划。览如，把遗传算法和人工势场 穗结合，嗣蠲了遗传箨法翁求耱袋整和犬工势场匏求解效率，等等。 1 4 论文的主要工作和创新点 未知环境下的潞径规划是一个相当复杂的课题，包括如何平衡快速和稳定两 个互相矛盾的性能，如何解决各种环境下出现的b u g 。本文总结了三年来在这方 面的工作和贡献，主要包括以下几方面： 1 ，详缀讨论了入工势场蘧数靛其体实瑰。暹过仿真寒研究势场函数孪：一些 重要参数对函数性能的影响，从而概括出参数选择的策略。另外，还比较了不同 形式的函数，尤其是避续性对势场函数性能的影响。本文还研究人工势场法的缺 陷形成斡原因：主受蹩原理的麓尊性蠢实际德援魏复杂佳之闲不麓缀好戆唿合。 并且对一些特殊的约束条件和相应的一些改谶方法分析了它们的实质。从而归纳 出改进的原则和方法。 2 ，为了比较人工势场法的性能，在静态环城下选择随机算法作为比较对象， 莲过傍爽来对篦嚣军孛算法之闻静优劣，更有滋鞭力魏反浃人工势殇法豹优势所 在，为人工势场法的实际应用提供了参考准则。 3 ，针对人工势场法在未知环境中的许多缺点，本文抛辫了传统的修改人工 势场法爨数戆愚怒，利_ 霹障碍甥数凡舞巷惠来翱歪大工势场法产生熬之字形路径 和局部缀小等b u g ，又利用人工势场法本身的导向原理使机器人能够朝饕目标点 前进。还提出了在狭窄环境中机器人需要采用的一些判断策略。 4 ，为了进一步撼蠢人工势场法的性能，同时研究如何慰好的表达环境信息， 本文逐辑究了如旃获环境信息l 扫缡出籁断豹依攥，在实际靛路径蕊麓中爨韵调整 步长。本文采用前后两次方向角的改变作为判断的基本信息，并且通过不同的实 鹕一章引等 现函数和仿真实例比较了方法的有效性，归纳出了一些原则。 1 5 论文的组织结构 第一章“引言”，介绍了国内外机器人发展的状况，着重介绍了路径规划的 研究目的，研究现状，发展方向。概括陈述了本文在路径规划方面的主要工作和 创新点。 第二章“人工势场法”，对人工势场法的原理，特点，缺陷作详细的描述， 重点介绍了如何在实际应用中选择函数的具体形式和参数。如何针对一些具体条 件如运动约束，环境改变等改进人工势场法。对于一些人工势场法固有的缺陷提 出相应的改进的方法和原则。通过仿真验证以上结论， 第三章“地图已知的路径规划算法的比较”，详细介绍了随机法和它的优点， 通过仿真实验比较人工势场法和随机法的各自优缺点，有力的证明人工势场法的 优势和劣势 第四章“未知环境下的自适应路径规划”，在前面三章的基础上，针对人工 势场法的不足，和未知环境下路径规划的特点，提出了几何信息法改进人工势场 法的缺陷，并通过分析环境的复杂度，提出了自适应步长的概念，进一步提高了 算法的灵活性和有效性。 第五章“总结和展望”，总结了本文的工作，并对进一步的研究方向作展望。 第二章a 工势场法 第二章人工势场法 k h a t ib 于1 9 8 6 9 年提出了人工势场法，当时的目的是用于机械手臂的避障研 究。毽怒由于入工势臻法具有实时挂好，诗算楚肇豹优点，与搬爨太豹逡动方程 较易结合，被广泛应髑于各类路径规划中 1 2 ( 1 3 1 4 2 9 。人工势场法建一种 根据局部信息来实施路径规划的算法，但是通过许多研究人员的改进，人工势场 法也可以应用于未知静环境，移动障碍物等比较复杂的情况。 2 1 人工势场法的基本原理 k h a t i b 搀篷黪入工势场法基于下嚣这襻一个蘸理： 机器人在一个充满势场力的场中移动，受到一个由目标点产生的吸引力，使 机器人怒目标点方向前进；同时受到障碍物产生的排斥力，使机器人沿着远离障 碍物袭诼的方向移动。 下瓣考虑怎襻孛弩建势场。 设x ，是目标点的嫩标，0 是障碍物，x 表示机器人的坐标，那么机器人在x 点的势场定义为 其中u 。( x ) 表示在x 点由目标点构成的势场，u 。( x ) 袭示在x 点由障碍物0 构成骢势场 如鬈考虑重力的影响，需要嬲上重力场，( 2 t ) 式改为 u ( x ) = u 。( x ) 十u g ( x ) ( 2 2 ) 按照势场力款定义，势瑟力楚势聚函数懿绨疫丞数，赝以 民。一删 u x d ( x ) ( 2 3 ) f o = 一g r a d u o ( x ) 】 e 。藏是鋈标点对瓿器太弱墩孳| 力，黾楚隆碍羧对爨嚣入夔耩蓐力。枣子势 场中的物体朝着势场低的方向移动，为了使机器入朝目标点移动，就要傥u 。( x ) 在x = x 。的时候势场为零，而且为了实现梯度邋算，u 。( x ) 必须是正连续的，可 积分盼。这些都是设计势场函数时必须满足的黎传。 瓦。( x ) = 一k p ( x 一。d ) ( 2 4 ) 1 4 第二帮人工癸场洼 这是个较糖实瑷的伺服缝梭，k 。为势场力抟煺蕊* 挺虚的 u 、。x ) 一0 s k 。( x x d ) 2 ( 2 。s ) 实际应用中，需要考虑枧器人酶移动速度，如袋移动速度过大，势必要改避 t 涞减小滤壤韵于挠。掰以，式( 2 4 ) 可以添翮一个稳定霞予： 墨。x ) = 一靶# x x ) 廷。x ( 2 ) k 。的大小与速度有关，目的藏麓为了使e 。包含个抗速艘项，抵消速殿对 于系统稳定性的影响。 u ；。的设计怒比较筒擎鼹；缓奶没崔漳遐物，枫嚣人蠡然会骥罄婆标点方秘 箭避，后采瓣研究人员程几乎浚俸 卡么馥动。 下瑟考感u 。的表达式。 首先，为了满足u 。( x ) 的特性，u 。必须是非负的，可积分的。而且为了避 受疆撞，巍枫爨a 靠近障碍蘩翁表疆，u 。必须麓淘无突六。魏祭鼷f ( x = 0 来 定义障碍物的边界方程，那么 u 。( x ) 。 圭翠( 志志) 2 f ( x ) p o 蠡旃计算最，j 、距离请参考文献( 。式( 2 8 ) 孛p o 静取毽敬决予橇器久浆 最大运动遮腹秘减速能力。按照擐爨螅定义，s o 的袭达式妇下： 吒： 露哆一玉p o 上p 。竺c x p 风泣s ， l 0 p 风 式中警= 絮篝挈7 第二谗人工势场法 2 。2 视步分耩和仿冀 为了试验戆方霞，本文霰设簿磷裙部是爨形 的。如果障碍物不是圆形的，需要牵涉剿两个多边形 物体问最小距离的计算，然后才能构遄人工势场。关 子这令阉题可戮参考文献e 3 ，事文不俸搡谗。另於， 把机器人伟为匀遽运动的点状物处璎，运动约束祭件 和几何约荣条件会在2 3 节阐述。为了探知周围环蟪 冬 0、j 夕 图2 1 本文带传感器的机器人 没慧模型 翡蘩惑，骰设瓿器天辫题麓遵訇蕊安装了，个声麴搽溅嚣 i 0 】，溺壁谈差不予考 虑。探测范围为l 。 本小节的仿舆主要怒验证人工势场法的有效性，以及参数k 。，k 。，7 7 ，风对 于嚣法淫簸静影镌。 2 。2 1 参数k 。，k ，坪，p 。对予舞法褴麓的影响 a 工势燧法蕊定义缀篱单，毽是翔暴遥择不好参数，逐是会有缀多运题翁。 k 、，邂为了补偿机器人逡艘带来的干扰，如果速度大，就会增加个与速度方简 相反的力，使机器人到达目标点的时僚速度为0 。但在实际操作中，移动机器人 往茬会采戳弱黪运动方式：匀遮运动：或者走一段鼹麓瞽缮，蕊走黢。嚣戳k 。 懿影桶并不蹩狠大。而虽率文的仿真试验并没有考虑穗器久静邈度，对于k 。不 幽2 2 仿冀薜境设置，帆器人的起始点必 岛 在上述蠹毫仿爽环境中，f x 。中l x x 。l 大约是凡西个单绽，聪f o 中l l p 2 懿荦位 应该是0 ，0 0 0 1 ，1 p i p2 的单位大概是0 0 1 ，为了使t 。积f 。在一个数量级上， 可以取k 。= 1 ，即= l o8 。图2 3 ( a ) 就是这参数设鬣下的仿真图 观察图2 3 ，( a ) 图是预先设想的情况，机器人平滑的绕过了障碍物，( b ) 图 中，引力藏小了1 1 0 ，显然，障碍物的摊斥力相对增翔，图中机器人的路径的 弧度相对予( a ) 大大增加，就怒接斥力增强熬表现。( e ) 图中，撼斥力煺趣了1 0 倍，可以餐到，效果和( b ) 图的一样，这可以通过简单的函数理论证明得到( 证 萌潞) 。显然( b ) ，( e ) 两图看似要比( a ) 图安全，但实际上( a ) 闰机器人离障碍物 的躐离一盛保持在1 0 0 友右，符合安全款标准。嚣虽，( a ) 垦瓤器又绕过障臻秘 的路径要短一些。 ( d ) 图中，雩| 力减s t1 1 0 ，摊斥力增加了1 0 倍，虽然机器人仍然能绕过 疃鼹物，但是路径太过麴季厅，缀难应鼹于实际摄作中。之字形路径产生靛原滚是 由于可的值太大，从而使得排斥力函数的变化太大所致。当机器人进入了障碍物 的势场，就会受到排斥力的作用，由于排斥力太大，机器人立刻以较大的反射角 被弹回蜀摊斥力较小的势场区域，由于蹿诧较大，前后两个势坜力相麓较大，所 1 7 第二章天工势弱镶 以引力立刻压过了排斥力，使得机器人朝着靠近障碍物的方向移动，如此循环， 藏产叟了之字形路缀。 如果吸引力太大，那机器人驻然不能绕过障碍物。 如果是移动的障碍物，一个比较直接的想法就是计算障碍物和机器人的相对 运动。跨犹e 懿莱簿褥甥稿蕊器人鹣矮心点连线上翡疆对速凌镶大，裁要麓强筇寒 增强排斥力。关于运动障碍物的谶障策略将在2 ，3 节详细介绍。 从豳中可以得出以下结论 ( 1 ) 只要拜斥力足够大，橇器人裁戆够避开障碍物 ( 2 ) 当f x 。和f 。相差不大( 不超过1 个数缀级) ，机器人可以比较平滑的绕 过障磋秘 图2 3 k p 和节对路径的影响，( a ) k p = 1 0 s , 踞= l ，( b ) k 。= 1 0 8 ，咎= o 1 0 ) k p = 1 0 9 , = l k ，。 0 9 ，誓= 0 1 第二章人工势场洼 ( 3 ) 强蜀大大超过。( 一个数攫级) ，裁会擦现之字澎躐线a ( 4 ) 修改k 。和修改巧的效巢楣嗣，只需要对其中一个参数调整即可。 2 2 。2 凰数连续性的讨论 鹜颓k h a t i b 挺塞嚣簿礴裙静势濑公式( 2 。8 ) 帮势矮力公式( 2 ，) p p 。 ( 2 8 ) p 风 艺： 哿咕一去，古老 p 岛 旺 l 0 p 岛 事实土，缀多研究a 受 爨出静蛰场力始下 f o 。裔 l 均 ( 2 1 0 ) 中游n 般毅2 。式( 2 9 ) 简单方镄，也能符合势场力酌要求。 ；惫什么k h a t i b 据出靛势强力蕊定义委熨杂韵多鼙尼? 阉越的关键在于式( 2 8 ) 怒 连续斡，当p = 岛露，藏照磊( 2 ，8 ) ，u 。= 0 符台连续酶条件。丽式( 2 。1 0 ) 积分后就会发现点p = p 。是间断点。 蕊囊餮也哥熬谈臻这令瓣逶，魏鬻2 + 4 中，舀怒镁臻k h a t i b 舔连续经醋羧 ) - s o 。2 ( b ) 馊翔嚣连缕性爨数( 2 。i 0 ) * 瘦子乡了一疆l l p l l p o ，为了接强努魏攥 斥力在一个数鼙级上，癍谈竣壁鼙= 1 0 5 ，鬏。= 。爨予魄较麴譬懿，撼蹿增黯一个数蹩 缀。其体灏数懿下 ；或 w ，一p 坤 ；一2 o ，tt1，、fjt i l x ，t 0 u 稿_ = 二章a 工势弱法 f 0 = 1 0 7 ( s q r t ( ( x l x o ) “2 + ( y l y o ) 2 ) 一5 0 ) 2 圈24 函数遣缕性的比较( a ) k 。= 1 0 9 ，翠= 0 ，l ，( b ) k 。1 07 ，r = 1 。：l * s q r t ( ( x 卜x 2 ) ，4 2 + ( y 卜y 2 ) ，+ 2 ) ： 观察图( 2 4 ) ，明显( b ) 图之字形路径比( a ) 图要剧烈的多，而且( a ) 图中， 两力相蒺两个数量级，两( b ) 中两力只相差一令数量级。为传么( b ) 图函数懿性能 这么差滋? 闽题静关键在于函数的不连续往，使得螽 斥力程势场域的边界驸近相 差很大，排斥力一下予从一个较大的值跌落为零。因此合力的变化也很剧烈，从 丽路径就变得曲折了。 2 。3与运动约束条件结合的 细节分析 2 2 节阐述了人工势场法翰具 体构造细节，但是，仅仅选取合邋的 固定的参数对于复杂的环境还楚不 够豹。飘器天需要菇 ；鼋整参数熬能 力，能根据环境的不同修改参数德。 例如，嬲障碍物的邋幼状态不同，就 要采用不同静势场函数。 为此，首先我们需要考察障碍物 的运动情况对于机器人的路径规划 的影响，可以参考文献 】 图2 5 遭遇避动障粥物 麓察踅2 ，5 ，r 怒蕊器久，v 滚示枫器久豹速凄矢量，0 是障碍耪，v o 表示 障碍物的速度矢量。从r 向障碍物作两条切线，a ，b 是两个切点。记磊为点r 到 第二辩人工势蚴法 点a 的矢量，那么( a r + b r ) 1 2 就代表鼹条切线之闻救角平分线。又逸最* ( a r ，b r ) 为两条切线的夹角。v o ，= v ，一v 。表示障碍物相对于机器人的速度。又记 = z v 。，( a t + b r ) 2 ) ，表示穗对遽凄积爱平分线阕的夹热。 从运动学的理论可以得到，如果只2 ，并且机器人保持目前的运动状 态，那么机器人就会和障碍物碰撞。也就是说吼q 2 反映了目前状态下，机 器入和障碍物的碰撞风险。将不等式口：铖1 2 的逻辑值定义为e 。，如果e 。，= i ， 意睬着碰攮。于麓可以定义 f o = n ( e 。，+ 占) 0 一土) 去挈( 2 1 1 ) p p op o x 占( 0 ， ) ，如果无磷撞风险，e 。，= o ，基本上按照k n a t i b 静排斥力公式计簿。 如果存在碰撞风险，e 。，= l ，排斥力翻倍，就会增加机器人避障的能力。图2 。6 给出了e 。，对迸障效果的影响。 图中，障碍貔的这发是l o 2 ，从( 5 0 0 ，6 0 0 ) 浍一7 r 4 鲍方岛移动戮( 5 4 0 ， 6 6 0 ) ，机器人的速度是1 0 。由于仿真中没有机器人减速能力的设置，于是假设， 礁嚣久存在磋撞鼹陵，采焉( 2 1 1 ) 式跑较纛。，函子豹雩# 焉。 可以看到，( b ) 图机器人要比( a ) 幽有更明显的绕转，为了更详细的说明问题， 表2 1 给出了丰a 器入在进入势场范圈后，祝器入和障碍物的距离比较。可以鞠显 地看到，( b ) 采用了e 。，机器人和障碍物的距离一童保掩在1 1 8 左右，藤( a ) 曩 示1 0 8 左右。 l 1l 2l 3l 4 l 5l 6 l 7 a1 4 4 3 3 1 3 0 9 51 1 8 3 7 1 0 7 51 0 8 0 41 0 8 7 2 1 0 9 4 5 b1 4 4 。3 31 3 l 。0 41 1 9 1 31 1 2 2 71 1 8 ，4 41 1 6 9 e1 1 8 2 第二章人工势场法 表2 1 采用碰撞风险系数对比后的结果 碰撞风险通过研究机器人和障碍物的速度情况，决定排斥力的大小。事实上， 调整排斥力大小的方法有很多，例如可以采取排斥力与相对速度成正比的策略。 但是，要指出的是，改变排斥力的大小并不能解决所有问题。设想，机器人和障 碍物以较快的速度迎面而来，无论你怎么改变排斥力的大小，机器人还是会沿着 两者之f 司的直线运动，所以，仍然有碰撞风险。 之所以有这样的问题，除了环境的复杂性以外，主要是由于人工势场法本身 的缺陷，这点将在2 4 中详细解释。 2 4 人工势场法的缺陷和改进方法 人工势场法是一个有效的方法，而且计算简单，非常适合用于机器人的实时 避障系统，但是原理的简单在复杂多变 的环境下产生了许多的问题，归纳为以 下四种： ( 1 ) 参数的选取复杂 ( 2 ) 移动障碍物的处理 ( 3 ) 不规则障碍物的处理 ( 4 ) 局部最