（通信与信息系统专业论文）基于动态人工势场的路径规划研究与应用.pdf

摘要 路径规划问题是近年来机器人技术领域研究的热点问题之一，也是机器人学 在研究人工智能方面的一个重要分支。本论文以机器人对抗比赛( 主要包括微软 轮式微型机器人仿真比赛平台和全局视觉机器人水球比赛平台) 为研究对象，针 对机器人对抗比赛体系中路径规划问题特有的复杂度高、实时性强、反映要求迅 速和多智能体等特点，提出一种基于动态人工势场算法思想的路径规划方法。主 要解决了传统人工势场法用于路径规划时存在的无法到达目的地问题和局部最 小陷阱问题，并将该路径规划方法最终写入实际比赛决策中，取得了较好的效果。 本文的主要工作有： 第一，对机器人系统研究背景、移动机器人路径规划的研究现状、课题研究 背景及现实意义进行综述性介绍，对微软轮式微型足球机器人仿真( m s r s ) 比 赛平台和全局视觉机器人水球比赛平台，以及在实验过程中用的一些主要规则。 第二，分析了经典人工势场模型法以及其用于路径规划存在的主要问题，针 对这些问题提出了相应的解决措施，包括：针对机器人无法到达目标点问题改进 了势场模型中的斥力构成以及采用虚拟水流法解决局部最小陷阱问题，并根据提 出的解决思路，在m a t l a b 中做了仿真对比实验。最后将改进的人工势场法一 一动态人工势场法应用于路径规划中。 第三，详细介绍了m s r s 仿真比赛策略构成，将基于动态人工势场法的路径 规划方法应用在m s r s 比赛决策中，并与基于遗传算法、蚁群算法以及一般几 何算法的路径规划方法作比较，分析实战比赛数据；将基于动态人工势场法的路 径规划方法在机器人水球比赛平台中检验，并分析比较该路径规划方法在不同实 验平台中的效果。 实战比赛实验结果表明，基于动态人工势场法的路径规划方法具有计算量 小、计算方法简单且在轨迹规划时考虑了机器人的运动性能等特点，使其在对抗 比赛中有较好的避障效果，能够很好的满足比赛的复杂性和实时性等要求。 关键词：路径规划；动态人工势场法；多智能体对抗环境；避障；虚拟水流法 a b s t r a c t i nr e c e n ty e a r s ，p a t hp l a n n i n gp r o b l e mi sah o ti s s u eo fr o b o tt e c h n o l o g ya r e aa n d a ni m p o r t a n tb r a n c ho fr o b o ts t u d yi n a r t i f i c a li n t e l l i g e n c e t h i st h e s i si sb a s e do n r o b o tc o m b a tg a m e s ，w h i c hm a i n l yi n c l u d em i c r o s o f tw h e e lm i c r or o b o ts i m u l a t i o n g a m ep l a t f o r m ( m s r s ) a n dt h eo v e r a l lv i s i o nr o b o tf o rw a t e rp o l om a t c hp l a t f o r m a g a i n s tt h ec o m p e t i t i o ns y s t e mf o rr o b o tp a t hp l a n n i n gp r o b l e mu n i q u et oh i g h c o m p l e x i t y , r e a l t i m e ，r e f l e c t i n g t h ed e m a n df o r p r o m p t a n dm u l t i a g e n t c h a r a c t e r i s t i c s ，ap a t hp l a n n i n gm e t h o db a s e do nd y n a m i ca r t i f i c i a lp o t e n t i a lf i e l di s p r o p o s e di nt h ep a p e r a n di ti sm a i n l yt os o l v et h ep r o b l e mt h a tt h ed e s t i n a t i o nc a n n o tb er e a c h e da n dt h el o c a lm i n i m u mt r a pp r o b l e mw h e nu s i n gt r a d i t i o n a la r t i f i c i a l p o t e n t i a lf i e l dm e t h o df o rp a t hp l a n n i n g ，a n df i n a l l yt h a tp a t hp l a n n i n gm e t h o di s w r i t t e nt ot h eu l t i m a t ed e c i s i o n m a k i n gi nt h er e a lg a m e ，w h i c ha c h i e v e dg o o dr e s u l t s t h em a i nw o r ko ft h i sp a p e ra r e f i r s t l y , t h i sp a p e rp r o v i d e sa ni n t r o d u c t i o nt ot h eb a c k g r o u n do fr o b o ts y s t e m ， m o b i l er o b o tp a t hp l a n n i n gr e s e a r c ha n dt h er e s e a r c hp r a c t i c a ls i g n i f i c a n c e t h ep a p e r p r o v i d e sai n t r o d u c t i o nt om i c r o s o f tw h e e lm i c r o s o c c e rr o b o ts i m u l a t i o ng a m e p l a t f o r ma n dt h eo v e r a l lv i s i o nr o b o tf o rw a t e rp o l om a t c hp l a t f o r mi n c l u d i n gs o m e r u l e sw h i c ha r eu s e di nt h ee x p e r i m e n t s e c o n d l y , t h et h e s i sm a k e sa na n a l y s i so ft h et r a d i t i o n a la r t i f i c i a lp o t e n t i a lf i e l d m o d e la n dt h em a i ni s s u e ，i nr e s p o n s et ot h e s ei s s u e sa d v a n c et h ec o r r e s p o n d i n g c o u n t e r m e a s u r e s ，w h i c hi n c l u d ea g a i n s tt h er o b o tc a nn o tr e a c ht h ed e s t i n a t i o n p r o b l e mt oi n p r o v et h er e p u l s i v ec o n s i t u t eo fp o t e n t i a lf i e l dm o d e la n du s ev i r t u a l w a t e r - r i ot os o l v et h el o c a lm i n i m u mt r a pp r o b l e m a n db o t ha r ed o n es i m u l a t i o n c o n t r a s te x p e r i m e n ti nt h em a t l a bp l a t f o r m l a s t l y , t h ei m p r o v e da r t i f i c a lp o t e n t i a l f i e l dc a l l e dd y n a m i ca r t i f i c a lp o t e n t i a lf e l di su s e di np a t hp l a n n i n g t h i r d l y , t h ep a p e rp r o v i d e s ap a r t i c u l a ri n t r o d u c t i o nt od e c i s i o n m a k i n g c o n s t i t u t e so fm s r s t h ep a t hp l a n n i n gm e t h o dw i t ht h ed y n a m i ca r t i f i c a lp o t e n t i a l i i f i e l di su s e di nt h ed e c i s i o n m a k i n go fm s r s ，a n a l y z ea c t u a lg a m ed a t ac o m p a r e d w i t ho t h e rp l a n n i n gm e t h o d ，s u c ha sg e n e t i ca l g o r i t h m ，a n tc o l o n ya l g o r i t h ma n d g e n e r a lg e o m e t r i ca l g o r i t h m e x a m i n et h a tp a t hp l a n n i n gm e t h o di nt h eo v e r a l l v i s i o nr o b o tf o rw a t e rp o l om a t c hp l a t f o r m ，t h e na n a l y z ea n dc o m p a r et h ee f f e c to f d i f f e r e n te x p e f i m e n t f lp l a t f o r m a c t u a lr a c er e s u l t ss h o wt h a tas m a l la m o u n to fc a l c u l a t i o n ，s i m p l i f yc a l c u l a t i o n m e t h o da n dt a k i n gi n t oa c c o u n tt h ep e r f o r m a n c eo ft h er o b o tm o v e m e n ti nt r a j e c t o r y p l a n n i n ga r et h ef e a m m so ft h ep a t hp l a n n i n gm e t h o dw i t ht h ed y n a m i ca r t i f i c a l p o t e n t i a lf i e l d s oi th a sb e r e rr e s u l ti na v o i d i n go b s t a c l ei nr o b o tc o m b a tg a m e ，a n d c a nb ew e l lp o s i t i o n e dt om e e tt h ec o m p l e x i t ya n dr e a l t i m er e q u i r e m e n t so ft h e g a m e k e yw o r d s ：p a t hp l a n n i n g ；d y n a m i ca r t i f i c a lp o t e n t i a lf i e l d ；m u t l i a g e n ta g a i n s t e n v i r o n m e n t ；o b s t a c l ea v o i d a n c e ；v i r t u a lw a t e r - r i o i i i 长沙理工大学 学位论文原创性声明 本人郑重声明：所呈交的论文是本人在导师的指导下独立进行研究所 取得的研究成果。除了文中特别加以标注引用的内容外，本论文不包含任 何其他个人或集体已经发表或撰写的成果作品。对本文的研究做出重要贡 献的个人和集体，均已在文中以明确方式标明。本人完全意识到本声明的 法律后果由本人承担。 名：叼 嗍晰厂月泌日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，同意 学校保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文 被查阅和借阅。本人授权长沙理工大学可以将本学位论文的全部或部分内 容编入有关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存 和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书。 2 、不保密团。 ( 请在以上相应方框内打“4 ) 作者签名： 导师签名： 孺掴 严 日期：洲砗歹月形i t i tl i ：矽i 。年箩月撕 1 1 引言 第一章绪论 随着计算机技术、超大规模集成电路、控制理论、人工智能理论、传感器技 术等的不断成熟和发展，由多个学科交叉而形成的机器人学研究也进入了一个崭 新的阶段。从可编程的、示教再现型的工业机器人到具有一定传感能力、一定适 应能力的机器人，再到配备多种先进传感器，具有较强的适应能力的智能机器人， 机器人学的研究工作经历了一个从简单到复杂，从功能单- n 功能多样，从工业 制造领域到军事侦察、核工业、航天航空、服务业、医疗器械、基因工程等诸多 领域的过程。可以预见，在不久的将来，机器人技术在各个领域的应用将会更加 广泛且深入。而各种机器人系统在实际工作中的广泛应用又为机器人学提出了新 的要求和新的研究课题。 随着社会需求的提高和机器人技术本身的发展，人们对机器人的要求不再局 限于单个机器人，而是对多个机器人组成的系统给予了更多的关注。多机器人系 统相关技术的研究核心之一路径规划，是实现机器人完全的自主移动和真正的智 能化的关键技术。对于多机器人的路径规划问题，国内外学者、科研机构对其进 行了广泛的研究，提出了很多不同的路径规划方法并取得了长足的发展。l e o n a r d 和d u r r a n w h y t e 将机器人的路径规划问题归结为“我在哪”、“我要去哪”和“我 如何到达那里”三个问题的解答【1 1 。但是，由于问题本身特有的难度：动态环境、 机器人与障碍物不确定、机器人始木位置不确定、系统复杂度不确定等等。到今 天为止，仍未设计出一个适用于任何环境的令人满意的解决办法。 1 2 机器人路径规划研究现状 作为机器人学中的一个重要课题，路径规划技术在逐步得到改善，国内外学 者多年来的研究更是硕果累累。从早期的栅格法、可视图法到a 宰算法、自由空 间法、d 宰算法以及其改进算法，再到人工势场法、神经网络算法、遗传算法、 模糊逻辑算法、各种群智能算法，其发展过程正体现了移动机器人发展之路。路 径规划是自主移动机器人中最重要的任务之一，其数学描述为：通过移动机器人 视觉系统或其它途径所获得的环境信息来给定移动机器人所处的实时环境，一个 起始点和一个期望的终止目标点。路径规划则是根据一定的任务要求，基于机器 人的参数和转弯角度、加速度等约束，寻求一条能够连接起始点到终止目标点且 能避开环境中障碍物的移动机器人的运动轨迹，通常此运动轨迹为最优或次最优 无碰撞有效路径【2 1 。 1 。2 ，1 机器人路径规划方法分类 路径规划因其依据不同有着不同的分类： ( 1 ) 根据不同的工作环境模型，可将路径规划分为基于模型全局路径规划 方法、基于传感器件的局部路径规划方法以及混合型规划方法【3 】。基于模型的全 局路径规划，已知其作业的全部环境信息，又叫离线或静态路径规划；基于传感 器的局部路径规划，作业环境部分未知或全部未知，只能靠传感器获取周围信息， 又称在线或动态路径规划；而混合型路径规划试图结合局部和全局规划的优点， 将全局规划中的“大致 路径当成局部规划的子路径，从而引导机器人找到目标 点。 ( 2 ) 根据机器人平台环境不同，可分为平整路面规划与起伏路面规划或者 室内规划与室外规划。 ( 3 ) 根据环境中是否存在运动着的障碍物，可将其分为周围环境静止的静 态规划和动态规划。 ( 4 ) 根据路径规划方法的不同，可分为常规路径规划方法和智能路径规划 方法，也有的分为基于地图、基于传感器探测模型，以及基于行为的路径规划方 法。 ( 5 ) 按照机器人系统中控制的变量数目与其位姿空间维数关系，可分成非 完整系统运动规划和完整系统路径规划。 事实上，移动机器人的路径规划是基于不同环境和具体机器人平台控制的体 系结构，在差异较大环境中对于不同性能的移动机器人平台，不同规划方法有着 各自的优势和劣势。目前，还没有适合各种环境系统的路径规划方法，并且有时 候结合不同的路径规划方法可以取得更理想的路径规划效果。下面根据第一种分 类方法分别介绍几种典型路径规划算法。 2 1 2 2 局部路径规划方法 机器人所处环境是未知或部分未知的局部路径规划的主要方法有模糊逻辑 算法、遗传算法和人工势场法等。模糊逻辑算法是基于实时传感信息，通过查表 得到规划信息实现局部路径规划，其缺点缺点为过于依赖专家经验，对于未知系 统难于得出模糊规则【4 】。遗传算法是一种多点搜索算法，能搜索到全局最优解但 其运算速度不快，进行众多规划需要占据较大的存储空间和较多的运算时间【5 j 。 1 模糊逻辑算法 模糊逻辑算法是根据机器人所处环境信息，通过确定好的规则库得到规划出 的信息完成局部路径规划。其优点是克服了势场法易产生的局部极小问题，对处 理未知环境下的规划问题显示出很强的优越性。 模糊逻辑算法就是以模糊控制为基础，对环境中障碍物的信息进行模糊化。 基于模糊集合理论的模糊逻辑控制，对于每一个元素x x ，存在一个 值( x ) lo ，1 j ，表示在给定论域上x 属于集合x 的程度，称为隶属度。模糊推理 系统的基本结构由四个主要部件组成：知识库、推理单元、模糊化输入接口与去 模糊化输出接口。知识库又包含模糊规则库和数据库，其中规则库是由一系列的 i f - t h e n 语句构成。规则库中的模糊规则体现了与该领域问题相关的专家知识或经 验。而规则库中的数据库则定义隶属函数、模糊等级数以及尺度变化因子等信息。 推理单元按照这些规则和给定的限制条件执行推理过程，求得合理的输出。模糊 输入接口将精确的输入量转换为模糊量，并将其用模糊集合表示。去模糊化输出 接口的作用就是将模糊化的输出转换为精确的输出量。设计模糊逻辑控制的大致 步骤如下： ( 1 ) 选择能够反映系统工作机制的控制输入输出变量； ( 2 ) 定义输入输出量的模糊子集； ( 3 ) 用模糊规则建立输出集与输入集的关系，即建立规则库； ( 4 ) 确定好隶属函数并且对模糊控制器的核心部分进行模糊推理及输出控 制量的清晰化。 模糊逻辑算法首先是由n e d u n q a d i1 6 1 提出，起初是由于移动机器人的逆运动 学方程的求解较困难，而且难得到机器人精确的运动学方程，因此如果用传统设 计控制器的方法来控制机器人运动，很难得到一个比较好的控制效果。而且机器 人的逆运动学方程和运动学方程都与机器人本身特性是相关联的。不同特性的机 器人拥有不同的运动学方程，因此运动学方程不具有普适性。处理器在计算运动 学方程上需要花费较多的时间，对于机器人路径规划的实时性有较大的影响。基 于以上考虑，此文献的作者着眼于不获得机器入精确的运动学方程，提出了利用 模糊逻辑控制的思想来规划移动机器人的路径，并且控制机器人向规划好的路径 运动。设计模糊逻辑控制器的过程首先是将得到的测量信号模糊化，然后根据条 件规则也就是模糊规则得出输出的控制量的模糊量表示，最后通过解模糊化得出 相应的控制值。通过实验可以看出这样方法可以有效地节约在计算逆运动学方程 求解上的时间，将更多的时间用在控制器的优化设计上。不过也遇到了一些问题， 例如模糊规则的设计，因为模糊规则是通过专家预测、实验数据等得出，存在一 些不确定性，有时无法很好的体现输入输出之间的直接关系。 文献【7 】中，提出了一种基于避免和周围障碍物碰撞的自适应模糊逻辑控制算 法来处理机器人的逆运动学规划问题。当机器人进入离障碍物较近的区域时，此 时模糊规则立即进行修改，使得机器人以最快的时间离开此区域。实验证明了此 种方法适合各种类型的机器人，然而由于障碍物的信息不是直接作为一个模糊输 入信号，因此此算法在为了获得一个能够很好的避免和障碍物相撞的路线时，可 能无法获得一个全局最优的路径。 文献【8 】中，为了避免和障碍物相撞，将机器人与障碍物之间的危险等级模糊 化为三个等级，分别为危险、不确定、安全。将机器人的运动速度和旋转角度模 糊化为相应的模糊量。然后通过一定的模糊规则得出避障的模糊算法和寻找目标 点的模糊算法，文中把障碍物的信息作为一个模糊量来直接影响机器人的速度和 旋转的角度，在危险系数最小的情况下，可以实现机器人到达目标点的路径规化。 通过理论证明，在存在最优路径的情况下，基于此种方法的路经规划得到的路经 是全局收敛的。所以经过多次规划，可以得到一个全局的最优路径。但此方法在 处理障碍物是运动的情况下时，可能也难得到一个最优的路经，只能得到一个次 优的路经。但是计算的时间比较短，容易提高机器人的实时处理能力。 模糊逻辑算法可以较好的处理局部极小值的问题，而且对环境具体信息的要 求不高且不要求较精确的模型。由于模糊控制算法是一种基于控制规则的，而这 些控制规则都是通过实验得出，或是经验得出的，在没有专家知识的情况下该算 法的计算时间比较长，不利于及时的规划出机器人的路径。因此模糊逻辑控制算 法在处理一些复杂多变环境下路径规划问题时存在一定的缺陷。 2 遗传算法 遗传算法是模拟达尔文的自然界遗传选择和生物优胜劣汰的进化过程的一 4 种模型算法。它采用简单的编码技术来表示系统中各种复杂的结构，并对其中的 各组编码进行一系列的遗传操作和优胜劣汰的自然选择柬获得需要的组合并且 确定搜索的方向。遗传操作是由选择、交叉、变异、删除四个主要的操作算予构 成。正是由于这些算子的存在，使遗传算法有了其特殊的特点和不一样的用途。 其基本要素如下： ( 1 ) 编码：遗传算法过程中的编码就是将环境中的各个点进行一定的代码 的编制。遗传算法中影响计算时间的主要因素是需要编码的长度和搜索空间。太 长的编码长度和太大的搜索空间都会使计算时间迅速增长。文献【9 l 里面把路径的 二维编码简化为一维编码，以简化编码的个数，提高了计算的速度。 ( 2 ) 适应度函数：在适应度函数的选择上应该考虑到避障和最优路径，使 规划处的路径不通过障碍物。由于该算法适应度函数中的各个权系数比较难调整 和确定，各个权系数不是恒定不变的，是随着路径和障碍物的变化而变化的，容 易引起优化不稳定。因此可以利用加权的方式来修改此适应度函数，在比较重要 的时候设置权值大而比较一般的地方设置权值小，可以节约计算时间。 ( 3 ) 基本的遗传算子：交叉算子，将复制产生的个体随机两两配对，随机 地选择交叉点。在交叉点的选择上可以选择双点交叉也可以多点交叉，匹配的个 体按杂交概率进行交叉繁殖，产生一对新的个体。变异算子，交叉后的子代个体 基因按小概率扰动进行变异，通常取很小的值。文献1 9 1 中选择在新的个体中加入 【_ 0 1 1 5 ，0 1 1 5 】之间的零均值高斯白噪声作为随机扰动，寻找最优解。整修算子， 为了使得到的路径是最优的，则将较次的路径取消，使下一次的搜索路径的次数 减少。可以节约在获得最优路径上的计算时间。删除算子，将得到的搜索点数量 减少，可以节约每次最优路径搜索的时间，提高效率。 遗传算法具有高效的路径规划和搜索能力，在较大的空间中可以较快获得最 优路径或是次优路径。它具有简单通用、鲁棒性强、适合于并行处理以及应用范 围广等显著特点。受环境影响比较小，不容易出现死锁的情况，适合于存在较多 参数需要优化的路径规划的情况下。但存在一些缺陷，首先遗传算法需要初始化 一些种群。而在初始化这些种群时，可能会存在不需要的种群点，这样会增加后 来计算的复杂程度。其次遗传操作算子无法适用于各种情况，在一些特殊情况下 操作算子需要改变，但是这些需要变化的算子可能无法确定，增加了实现的难度。 例如在运用交叉算子和变异算子上，需要给定一定的变化概率。然而这些概率的 选择也不是确定的，需要凭借定的经验来选择，而且此时获得的路径不定是 最优的。 3 人工势场法 人工势场法将机器人运行环境视为存在一种抽象的人工受力场，机器人在受 力场中运动，其运行方向受建立的人工势场负梯度方向控制，将机器人看成在人 工势场影响下的一个点。人工势场法的核心思想是：构造障碍物周围的斥力场与 目标位置的引力场，搜索势函数下降的方向即势函数负梯度方向来寻找最优路 径。人工势场法具有计算速度快、算法描述简便、硬件要求低( 只需测距离传感 器如声纳等) 等特点，因而在未知动态环境的避障路径规划中得到了广泛的应用。 然而，由于人工势场法所依据的环境信息是局部的，缺乏全局环境上的自我调节 能力，因此在应用中，容易产生局部最小等问题，关于这类问题的解决将在本文 第三章中详细地介绍。 1 2 3 全局路径规划方法 全局路劲规划的主要方法有：可视图法、自由空间法、栅格法、蚁群算法等。 这类路径规划方法的主要过程可分成三个步骤： ( 1 ) 采用相关建模技术去划分环境空间； ( 2 ) 形成含环境空间的信息搜索空间； ( 3 ) 在空间上用搜索策略搜索。 1 可视图法 可视图法是将所有障碍物等生成投影在平面内的多边形集合，并将起始点和 目标点在空间中对应的点扩充到多边形集合中。然后将所有障碍物的顶点( 设 是所有障碍物的顶点构成的集合) 、起始点j 和目标点g 用直线组合相连， 同时要求三者之间的连线不能穿越障碍物，即此直线是“可视的。给定图中的 边赋权值，构造图g ( v ，e ) ， 节点集v = v o u ( s ，g ) ，e 为所有弧段( 只，只) 即 边的集合，其中连接g 中第f 和第，个结点的线段与任何障碍物均不相交。因为 图中相邻的顶点能相互看到，所以g ( v ，e ) 称为可视图。然后采用某种算法( 如 d i j k s t m 算法) 搜索从起始点s 到目标点g 的最优路径。规划最优路径的问题就 转化为从起始点到目标点经过这些可视直线的最短距离问题。其中的d i j k s t r a 算 法是典型最短路算法，用于计算一个节点到其他所有节点的最短路径。其主要特 点是以起始点为中心向外层层扩展，直到扩展到终点为止。d i j k s t r a 算法能得出 最短路径的最优解，但由于它需要遍历计算的节点很多，所以效率比较低。 6 然而此方法是通过连接的线段的长度的值来获得最优路径的，当线段连接不 合适时可能导致无法获得最优路径。文献【l o 】提出了一种改进后的可视图法，此 算法主要改进有： ( 1 ) 用直线划分机器人所处环境的自由空间为多边形区域： ( 2 ) 耿各线段的中间点为结点； ( 3 ) 考虑所有可能存在的路径，连接这些结点，从而形成结点间的弧； ( 4 ) 增加起点和终点，并将它们作为新的结点，考虑它们与其他结点问若 可能存在弧，则把它们连接起来； ( 5 ) 对这些结点问所形成的弧加以权值( 一般假设机器人匀速运动，并且 把路径长度作为其权值) 。 切线图法和v o r o n o i 图法对可视图法进行了改造。其中切线图用障碍物的切 线表示弧，是从起始点到目标点的最短路径的图，即移动机器人必须几乎接近障 碍物行走。其缺点是如果控制过程中产生位置误差，移动机器人碰撞的可能性会 很高。而v o r o n o i 法则是尽可能远离障碍物和墙壁的路径表示弧，从起始节点到 目标节点的路径将会增长，采用这种控制方式时，即使产生位置误差，移动机器 人也不会碰到障碍物。 总的来说，可视图法只适合于全局环境都知道的情况。对于动态变化的环境， 以及对于未知的一个环境时，但是使用此方法是无法得到最优路径的。在针对未 知环境的路径规划问题，以及动态环境的路径规划问题上，不能采用可视图的方 法。 2 自由空间法与栅格法 自由空间法是采用预先定义的如广义锥形和凸多边形等基本形状构造自由 空间，并将自由空间表示为连通图，通过搜索连通图来进行路径规划。该法比较 灵活，起始点和目标点的改变不会造成连通图的重构，算法的复杂程度与障碍物 的数量成正比，且不能在任何情况都获得最优路径。自由空间法和栅格法在某种 规划程度上是类似的。因此下面简单的介绍一下栅格法的定义以及其是如何进行 路径规划的。 栅格法则是用相同尺寸的栅格对机器人的二维移动空间进行划分，将移动机 器人运动环境分解成一系列固定大小的网格单元。工作空间中障碍物的大小和位 置是不发生改变，在机器人运动过程中，被障碍物占据的栅格位置和数目是不发 生变化的。 7 栅格尺寸的大小是依据机器人自身的尺寸来确定的。若某个栅格范围内不含 任何障碍物，则称此栅格为空栅格；反之，则称为障碍栅格。自由空间和障碍物 均可表示为栅格块的集成。栅格的标识方法有两种；直角坐标法和序号法。多采 用四叉树或八叉树表示工作环境，并通过优化算法完成路径搜索。该法以栅格为 单位记录环境信息，环境被量化成具有一定分辨率的栅格，栅格的大小直接影响 着环境信息存储量的大小和规划时间的长短，栅格尺寸太大，则环境信息存储量 小，规划时间短。但分辨率下降，且规划出来的路径可能不是最优的。 用栅格法建模受到了空间分辨率和内存容量的双重限制。而自由空间法建模 解决了这一矛盾。自由空间法的分割需构造一种被称为假想的边界。由于假想的 边界本身具有任意性，易导致路径的不确定性。一些研究者给出的自由空间网络 法结合了栅格法和自由空间法的基本思想，依照环境中的信息结构来解决自由空 间分割过程中构造假想边界的任意性问题，消除规划路径中所存在的不确定性。 自由空间法是由b r o o k s j 提出，用于解决智能轮式机器人系统的路径规化 问题，比如机器车或者是双驱动的四轮机器人。其中在路径规划的初始阶段，机 器人的起始位置和方向，以及目标点的位置和方向，障碍物的位置都是已知的， 并且把机器人和障碍物的外形认为是多边形的。通过选择中间的点，来规划出最 短的可行运动路径。在文献中，机器人以两种运动方式来完成此算法，分别为前 向移动和转弯。在操作此算法时，机器人由起始点运动到最近的一个中间点；然 后在此中间点停下，选择下一个中间点，选择完毕后，在此时的中间点旋转，当 机器人的方向指向下一个中间点时，则此时执行前向移动。这种算法存在一定的 缺陷，因为机器人在旋转时，存在一定的物理限制，而且也无法保证旋转后还处 在原来的那个起始点。在停下的时候有一定的惯性，使的在停下的时候就偏离了 预定的点。此方法可以很快地得出最优路径，可以很好的避免与障碍物相撞。 文献【1 2 j 中，基于b r o o k s 所提出来的方法以及对机器人运动的要求，通过一 定的验证，分析得到前向移动和旋转运动对机器人的设计要求很高；而较多机器 人由于自身硬件的限制，如旋转角的限制等等是无法实现纯某项运动的。自由空 间法的限制条件较高，不容易得到一个最优的路径而且计算比较复杂，所以后来 应用的比较少。 3 蚁群算法 蚁群算法是受自然界中真实蚁群的集体行为的启发而提出的一种基于群体 的模拟进化算法，属于一种随机搜索算法【1 3 1 。用于寻找最短路径的蚁群算法来 8 源于蚂蚁寻食的过程。人们经过大量的研究发现，蚂蚁个体之i 自j 是通过一种称之 为外激素的物质进行信息传递从而能相互协作，完成复杂的任务。同时，蚂蚁在 运动过程中能够在它所经过的路径上留下这种物质，能够感知这种物质的存在及 其强度，并以此指导自己的运动方向，而且蚂蚁倾向于朝着该物质强度高的方向 移动。这种物质在蚁群算法中称为信息素。由大量蚂蚁组成的蚁群的集体行为便 表现出一种信息j 下反馈现象，某一路径上走过的蚂蚁越多，则后来者选择该路径 的概率就越大。蚂蚁个体之间就是通过这种信息的交流选择出最佳路线，达到搜 索食物的目的。蚁群算法是由意大利学者m 。d o t i g o 等人提出来的，称之为蚁群 系统，并成功地用于一些实际问题的求解当中，例如分配问题、水作业调度问题 等，取得了一系列较好的结果，后来人们开始研究将此系统用于路径规划中。 在此算法中主要用到了一个概率路标，通过一定的概率来使蚂蚁从一个点转 移到下一个点，当蚂蚁到达目标点后，则各个点的信息素和选择概率都会进行相 应的改变。 由于蚁群算法存在着过早成熟的问题，即只获得次优路线时就停止了对其他 路线的搜索的问题。可以通过调整从一个点到另一个点的转移概率，能更好的对 最优路径进行搜索。通过实验可以得知，通过改进后的算法可以更快的得到最优 路径。在文献【1 4 】中，通过以加入虚拟起始点的方式，改进了此算法，并且将信 息素的更新分为局部信息素和全局信息素的更新。这样通过不同区域的信息素的 更新可以提高搜索的速度，能快速的得到环境的最优路径。也有提出两个种群的 蚁群，其中一群从起始点开始出发进行搜索，另一群从目地点反向出发，进行相 互之间的搜索，实验证明此种改进可以提高搜索的速度。 文献【l5 】中利用蚁群搜索食物的过程与著名的旅行商问题之间的相似性，通过 模拟蚂蚁搜索食物的过程即通过个体之间的信息交流与相互协作，最终找到从蚁 穴到食物源的最短路径来求解t s p 问题。在文献l l6 j 中，针对蚁群算法算法容易 产生类似于“s t a c k e dc a n y o n p r o b l e m ，也就是当局部的信息素最多的时候，越 来越多的蚂蚁都出现在这个局部的时候，其他地方的蚂蚁则会相应的减少使搜索 受阻，提出了一种“s t a c k e d c a n y o n h o r m o n e 的方法来处理此问题。当出现蚁群 往局部拥挤的情况时，此时由于有很多蚂蚁的存在，使得其中的蚂蚁在选择自己 的点时，出现不能执行的情况。则此时通过释放信息素，这就可以使蚂蚁避免往 局部信息素多的区域运动。相对于信息素的蒸发速度来说，信息素的蒸发更快， 不会影响到蚁群的搜索。通过释放信息素后，能很快地解决局最大的问题，而且 9 还可以减少搜索中的蚂蚁的数目。文献【1 7 1 中，对于蚁群对环境适应性差的问题， 提出了一种自适应的蚁群算法，其中的自适应主要是在最优函数、适应性选择函 数和适应性调整函数的选择上加入了自适应，使得在不同的情况下选择不同函 数。而且各参数也是根据具体的情况而确定的，具有一定的自调整的特性。实验 证明此种方法能够以更快的速度获得最优的路径。 尽管蚁群算法有以上这些优点，但是还是具有一定的缺陷。在考虑实际机器 人行走路线的时候，得考虑机器人本身的大小，如果路径宽度太小可能机器人无 法通过。于是在之后的改进中，可以将机器人的实际特点加入到函数值的选择当 中。例如可以在当路径宽度小于一个值时，视为该路径不可通，不让蚁群往这个 方向运行。 1 3 论文结构及主要内容 本文主要介绍的是基于动态人工势场法的多机器人系统路径规划研究，并将 该算法成功应用于微软轮式微型足球机器人( 仿真) 决策和水中机器鱼( 实物) 中，通过在“2 0 0 9 中国机器人大赛暨r o b o c u p 公开赛 中检验，取得了较好的 成绩。论文章节内容如下： 第一章介绍了机器人系统研究背景以及移动机器人路径规划现状，并且介 绍了本文的主要工作。 第二章介绍了微软轮式微型足球机器人仿真( m s r s ) 比赛平台和水中机器 鱼比赛平台，以及一些主要规则。 第三章分析了经典人工势场模型以及存在的主要问题，针对这些问题提出 了相应的解决措施，并将改进的人工势场法动态人工势场法应用于路径规 划，在m a t l a b 仿真中检验算法的有效性。 第四章主要包括： ( 1 ) 将基于动态人工势场法的路径规划方法应用于m s r s 比赛决策中，并 与基于遗传算法、蚁群算法以及一般几何算法的路径规划法作比较，分析实战比 赛数据； ( 2 ) 将基于动态人工势场法的路径规划方法在水中机器鱼比赛平台中检验， 并比较该路径规划方法在不同实验平台中的效果。 1 0 2 1 引言 第二章多机器人系统实验平台 从2 0 世纪8 0 年代中期开始，分布式人工智能和复杂系统的研究工作逐渐深 入开展，多机器人系统研究丰富发展。在研究过程中，学者将分布式人工智能、 复杂系统、社会学、管理学等其他研究领域的理论及方法引入多机器人学的研究 中，探讨机器人群体乃至机器人社会的各种组织方式、信息交互方式、进化机制 等基本问题，为多机器人系统发展提供了新的视野。 然而多机器人系统作为一种人工系统，实际上是对自然界和人类社会中群体 系统的一种模拟。多机器人控制研究与协作的基本思想就是把多机器人系统看成 一个社会或一个群体，从组织与系统的角度去研究多个机器人间的协作机制，从 而发挥多机器人系统各种内在的优势【1 8 1 。与单个机器人相比，多机器入系统有 着更多优点的同时也面临着诸多挑战，像系统结构、组织协调、冲突消解、通讯 机制、学习能力等【1 9 】。而机器人比赛为这些问题的探讨与研究提供了一个良好 的实验平台，它具有动态实时系统、分布式合作与对抗、带噪声的非全面的环境 模型、非符号化的环境信息和受限的通讯带宽等技术特点。 国际性的机器人竞赛起源于2 0 世纪9 0 年代，最先出现在美国和欧洲发达国 家。目前国际机器人竞赛类别主要有机器人足球竞赛、机器人灭火竞赛和机器人 综合竞赛【2 0 】。机器人足球竞赛中最具有影响力主要是f i r a 和r o b o c u p ，这两大 比赛有严格的比赛规则，融趣味性、观赏性、科普性为一体，为更多青少年参与 国际性的科技活动提供了更好平台。 目前国内的机器人竞赛主要有中国机器人大赛暨r o b o c u p 公开赛、全国机器 人足球锦标赛、c c t v - r o b o c o n 、中国青少年机器人竞赛。中国机器人大赛暨 r o b o c u p 公开赛是国内最权威、影响力最大的机器人技术大赛和学术大会，覆盖 了中国现有最顶级、全部的机器人专家和众多日本、美国、德国知名机器人学者， 为当今中国、乃至亚洲机器人尖端技术产业竞赛和国际顶尖人才汇集的活动之 一。从1 9 9 9 年首次在重庆举行后，以后每年举办一次，已在国内重要城市举办 了十届。 本文所用到的实验平台j 下是中国机器人大赛暨r o b o c u p 公开赛中微软( m s 轮式微型机器人仿真项目以及全局视觉机器人水球项目中使用的标准比赛平台 下面简要介绍这两个实验平台。 22 微软轮式微型足球机器人仿真比赛平台 中困机器人大赛暨r o b o c u p 公开赛中微软( m s ) 轮式微型足球机器人仿真 项目所用的比赛平台是东北大学所开发的n c w n e u 足球机器人3 d 仿真平台。 该平台是基于m i c r o s o f t r o b o t i c s s t u d i os d k i5 丌发的，充分利用了丌发平台提 供的仿真引擎服务。m i c r o s o f tr o b o t i c ss t u d i o 是支持报多机器人硬件平台的 w i n d o w s 机器人开发环境，包括一个轻量级的r e s t 模式的、面向服务的运行时 以及一系列可视化的组件和仿真工具。m i c r o s o f tr o b o t i c ss t u d i o 运行时同时支 持n e t 框架和精简n e t 框架。运行时由c c r ( c o n c u r r e n c ya n dc o o r d i n a t i o n r u n t i m e ，c c 鼬和d s s ( d e c e n t r a l i z e ds y s t e ms e r v i c e s d s s ) 两个主要的组件构成， 方便用户编译、监视、发布以及根据需要构建各种各样的府用程序f 2 ”。 目前，足球机器人比赛系统主要包括集控式足球机器人系统和分布式足球机 器人系统。n e w n e u 足球机器人3 d 仿真平台提供的机器人系统是对实物模式集 控式足球机器人系统的一种仿真，因此，下面先简要介绍下实物摸式的集控式足 球机器人系统。 囤2 l 集控式系统概念图 2 2 1 集控式足球机器人系统 首先给出集控式足球系统的概念图，如图2 1 ，从功能上可分为：小车子系 统、视觉子系统、决策子系统、总控子系统和通讯子系统【2 2 】。 ( 1 ) 视觉子系统：视觉子系统是机器人的眼睛。它由悬挂在球场中圈上空 约2 米的摄像头摄取图像，送入主计算机进行分析。由于双方各有不同颜色的队 标( 黄色和蓝色) ，而机器人也有不同的队员色标。这样计算机就可以通过颜色 分隔来识别全部机器人与球的位置与朝向了。 ( 2 ) 决策子系统：装在主机中的决策子系统根据视觉系统给出的数据，应 用专家系统技术，判断场上攻守态势，分配本方机器人攻守任务，决定各机器人 的运动轨线，然后形成给各小车左右轮轮速的命令值。 ( 3 ) 通讯子系统：无线通讯子系统从主机拿到命令值，再由独立的发射装 置与装在小车上的接收模块建立无线通讯联系，遥控场上各机器人的运动。 ( 4 ) 小车子系统：机器人小车由车架、车轮、电机、减速机、测速码盘、 驱动电源、单片机控制电路与无线接收模块等构成。它可以按着主机发出的命令 调整左、右轮转速，以保证按预定的轨迹运动。 ( 5 ) 总控子系统：总控子系统不仅是人机交互接口，而且更恰当的说是整 个系统的大管家，负责管理整个系统的运行状态，各个子系统的初始化，对各个 子系