毕业论文--多机器人系统的路径规划算法研究 （含外文翻译）

毕业--多机器人系统的路径规划算法研究 （含外文翻译） 华东交通大学 毕业设计(论文) 题 目: 多机器人系统的路径规划算法研究 英 文 题 目: Research on Path Planning Algorithm of Multi-robot System 学 院: 电气与电子工程学院 专业班级: 03级工业自动化(1)班 学生姓名: 井雅洁 学号 20030210030408 指导教师: 陈世明 完成日期: 2007. 6.11 毕业设计(论文)诚信声明 本人郑重声明:所呈交的毕业设计,论文,是我个人 在导师指导下进行的研究工作及取得的研究成果。就我所 知～除了文中特别加以标注和致谢的地方外～论文中不包 含其他人已经发表和撰写的研究成果～也不包含为获得华 东交通大学或其他教育机构的学位或证书所使用过的材 料。 如在文中涉及抄袭或剽窃行为～本人愿承担由此而造 成的一切后果及责任。 本人签名____________ 导师签名__________ 年 月 日 华东交通大学毕业设计(论文)任务书 姓 名 井雅洁 学 号 20030210030408 毕业届别 2007 专 业 工业自动化 毕业设计(论文)题目 多机器人系统的路径规划算法研究 指导教师 陈世明 学 历 博士 职 称 副教授 具体要求: 1.设计内容 (1) 熟悉静态环境中的全局优化路径规划算法。 (2) 熟悉适合于动态不确定环境的局部优化路径规划算法。 (3) 掌握粒子群优化算法在移动机器人路径规划中的应用。 2.设计的基本要求 (1) 完成基于粒子群算法的移动机器人路径规划实验仿真。 (2) 完成对仿真结果的分析。 (3) 完成毕业论文(15000字以上)。 (4) 完成3000汉字的与设计内容相关的英文资料的翻译。 (5) 查阅中文文献12篇以上，外文文献2篇以上。 3.主要参考文献 [1]谭民，王硕，曹志强.多机器人系统[M]. 清华大学出版社. [2]曾建潮，介婧，崔志华.粒子群算法[M].科学出版社. [3]刘卫国.MATLAB程序设计与应用.高等教育出版社. 进度安排: 设计各阶段名称 日期 % 1 文献阅读，熟悉MATLAB平台 1月24日-3月22日 10 2 开题报告 3月23日-3月30日 5 3 静态全局规划研究 3月31日-4月27日 30 4 基于粒子群算法的路径规划研究 4月28日-5月25日 30 5 毕业论文写作、答辩 5月26日-6月20日 25 6 英文资料翻译 设计期间自行安排时 间 指导教师签字: 年 月 日 教研室意见: 教研室主任签字: 年 月 日 题目发出日2006/1/24 设计(论文)起止时间 2006/1/24,2007/6/20 期 附注: 华东交通大学毕业设计(论文)开题报告书 课题名称 多机器人系统的路径规划算法研究 课题来源 本科毕业设计 课题类型 DY 导 师 陈世明 学生姓名 井雅洁 学 号 20030210030408 专 业 自动化 课题研究背景及应用的意义 1(课题研究背景; 随着计算机技术、信息技术、控制理论、人工智能和传感器技术等学科的发展和成熟，以此交叉而形成的机器人学的研究也进入了一个崭新的阶段。机器人的研究经历了从可编程的、示教再现型的工业机器人到具有一定传感、适应能力的机器人再到配备多种先进传感器，具有自学习和较强适应能力的智能机器人;从结构简单、功能单一的单机机器人到结构复杂，适应复杂环境，功能多样的多机器人系统的发展过程。在机器人研究的早期，单机器人的结构、运动学、控制和信息处理是研究的重点。随着机器人技术的发展，单个机器人的工作能力、鲁棒性、可靠性和效率等都有很大的提升，但是面对一些复杂任务，在环境比较复杂的情况下，单个机器人很难高效，可靠的完成预期目标。为此，在研究和应用的双重推动下，机器人学的研究一方面进入高智能、柔性更好、能力更强的机器人研究方向;另一方面，通过协作工作的多机器人系统的研究成为一个活跃的研究方向。 多机器人系统作为一种人工系统，实际上是对自然界和人类社会中群体系统的一种模拟。多机器人协作与控制研究的基本思想就是将多机器人系统看作是一个群体或社会，从组织和系统的角度研究多个机器人之间的协作机制，以便充分发挥多机器人系统各种内在优势。多机器人系统具有空间分布的特性，通过多个机器人并行工作可以提高完成任务的效率;其次系统内各种资源(信息、知识、物理装置)的共享可弥补个体能力的不足，扩大完成任务的能力范围;各机器人能力的互补性也可提高完成任务的可能性，增强系统的容错性、鲁棒性和灵活性。多机器人协调协作研究工作的目标就是尽量发挥系统的优势，解决系统中存在的问题或降低其不利影响，使系统能灵活、快速地响应环境和任务的变化，从而在复杂环境中高效、可靠地完成任务。 移动机器人的路径规划是机器人导航系统中不可缺少的重要部分，导航系统是移动机器人的研究核心，同时也是移动机器人实现智能化及完全自主的关键技术。移动机器人的导航问题主要是由Durrant Whyte H F提出的三个问题 ?“我现在何处?”?“我要往何处去?”?“要如何到该处去?”。大多数导航系统由两级规划组成，即局部规划(Local Planning)和全局规划(Global Planning)。前者主要解决?、?两个问题,即机器人定位和路径跟踪问题，而后者主要解决问题?，即全局目标分解成局部目标，再由局部规划实现局部目标。 移动机器人按照预先给出的任务命令，根据已知的环境信息做出全局路径规划，并在行进过程中，不断感知周围的局部环境信息，自主地做出各种决策，并随时调整自身位置，引导自身安全行驶或跟踪已知路径达到目标位置。移动机器人要实现导航涉及到的基本行为有:自身位置和周围环境的感知与识别、路径规划、路径跟踪、障碍回避等。 路径规划是移动机器人导航技术中不可缺少的重要组成部分，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标。 路径规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高移动机器人的智力水平， 减少移动机器人在移动过程中存在的不确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机器人、探测机器人、服务机器人、汽车自动驾驶系统打下基础。 2(应用意义 自动控制、计算机、微电子、人工智能、通信等理论和技术的不断发展和普遍应用使机器人化的各种工程设备、自动化机械具有越来越强的智能性和自主工作能力。这些具有一定智能、可以自主完成某些工作的自动化设备构成的复杂多机器人系统在船舶制造、产品装配、交通系统、航空航天等国民经济和国防建设领域的应用中具有极大的经济价值和社会价值。它们在信息处理、协调协作算法、实时控制、冲突消解以及解除死锁等问题的研究中可以为交通系统中自动驾驶、自动导航、路径优化以及交通流量控制等问题的解决提供了许多基本方法，在减轻驾驶员的负担、提高运输效率等方面具有潜在的应用价值。路径规划是移动机器人导航技术中不可缺少的重要组成部分，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标。 路径规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高移动机器人的智力水平，减少移动机器人在移动过程中存在的不确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机器人、探测机器人、服务机器人、汽车自动驾驶系统打下基础。 课题研究现状及发展趋势 1(研究现状 对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划和局部路径规划是按照机器人获取环境信息的多少划分的。全局路径规划是指机器人能够获取全部的环境信息，并以此为基础进行的规划;局部路径规划是指在环境信息未知或部分未知的情况下，机器人通过传感器感知周围局部信息进行的路径规划。根据环境中分布物体运动特点的不同，路径规划又可分为静态路径规划和动态路径规划。障碍物与目标静止情况下机器人的路径寻优为静态路径规划;机器人寻优过程中障碍物与目标处于运动状态即为动态路径规划。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法;局部路径规划方法主要有人工势场法，遗传算法等。这些方法都各有优缺点，对于实际的应用场合，需要将各种方法结合起来使用。 (1)静态环境中的全局优化路径规划算法。 静态环境下的全局路径规划是发展比较成熟的一个研究方向。目前进行规划的方法也比较多。最常用的方法有位形空间法、广义锥法、顶点图像法、栅格划归法、最短切线法。同时一些智能算法如遗传算法、粒子群算法也越来越多的应用于全局路径规划。 (2)动态不确定环境的局部优化路径规划算法。 动态环境下路径规划的方法主要有几何计算法、人工势场法、基于模糊控制器的路径规划法等。 2.发展趋势 移动机器人的路径规划是机器人导航和控制中非常重要的一个环节。对于路规划算法的研究经历了从传统常规算法到新型智能算法的发展过程。随着信息技术、通信技术、传感器技术和人工智能等相关学科的发展，优化算法走向了灵活、智能、高效的发展方向。可以预见，在不久的将来，新的信息处理技术和智能算法会大量并入该 领域，在优秀算法的协助下，机器人可以灵活应用于军事、航空、交通运输等各种领域。 本课题研究的内容 主要包括多机器人系统在静态环境中的全局优化路径规划算法、动态不确定环境中的局部优化算法。重点研究粒子群算法在移动机器人路径规划中的应用。 具体要求: 1(设计要求 (1) 熟悉静态环境中全局优化路径规划算法 (2) 熟悉合适于动态不确定环境的局部优化路径规划算法 (3) 掌握粒子群优化算法的应用 课题研究 本课题应用粒子群算法进行移动机器人路径规划。整个规划过程分两步进行。第一步进行环境建模，即建立一个坐标系，并在其中设置一定数量一定形状的障碍物、机器人的起始位置和目标位置，并采用区域划分的环境建模思想划分工作空间，将路径优化问题转化为目标函数优化问题。第二步采用粒子群算法进行路径优化，生成一条从起始位置到目标位置的最优或近似最优无碰路径。 1.环境建模 环境建模是进行路径规划的首要步骤，也是非常重要的一个步骤。模型建立的好坏会直接影响优化算法的实现程度和优化路径的优劣。这篇论文采用区域划分的环境建模的思想，即对机器人的工作环境依实际情况的需求进行划分，为简化模型我们做纵向的n(可称作维度)等分。路径规划即可表示在区域边界确定的情况下，在每条纵 p线上找一个合适的点 (第i条纵线上的点)，组成一个点的有序点序列i p,p,？p,？p()，这个序列即可表示机器人的一条路径。如果知道每个点的坐标位12in 置，就可以用一个2×n的矩阵表示这一条路径，矩阵的第一行存储每个维度的横坐标，第二行存储纵坐标。考虑到区域划分的特殊性，各个维度的横坐标有一个等差关系，可以不用表示出来，所以一个1×n的矩阵即可表示机器人的一条路径。例如我们用X=x,x,？x,？xx()表示机器人的一条路径，表示第i个维度的纵坐标,则X为路径12ini 规划中的一个解。 x,x,？x,？x我们定义路径的长度为目标函数F=f()，也称作适应度函数。Min F12in 即为全局路径规划的最优解。考虑到环境中存在障碍物，该课题为带约束条件下目标函数的优化问题，既需要在可行区域内找到一个解X,使得目标函数的值为最小。对于不可行解(即X中存在障碍物中的点或X决定的路径穿过障碍物)，采用惩罚技术加一个惩罚函数使其适应值高于可行解的适应值。 2.路径优化 本篇论文在路径优化中采用粒子群进化算法寻求目标函数的最优解，即全局的最优路径。粒子群算法借助“群体”和“进化”的生物学概念，通过多次进化找出群体中的最优个体。对于每个个体，都有两个行为，认知与学习。认知的过程就是个体与自身经历作比较，试图达到个体最优的过程;学习的过程就是个体与群体最优进行比较趋进群体最优的过程。在整个进化过程中，个体通过跟踪两个极值更改自身的速度和位置信息，以便趋向全局最优位置。将粒子群算法应用于路径规划中，采用粒子群算法寻求全局的最优路径，即目标函数的最优解X,也即使得路径最短的可行解X。算 法的流程如下: (1)设置粒子数N,粒子维数n，及最大迭代次数t。 (2)初试化粒子速度v和位置x(各个时间维度上的位置)。 (3)计算每个粒子的适应值(即每个粒子所走路径的长度)，对于不可行解适应值加 一个惩罚值。 (4)确定个体最优p和群体最优g。 (5)考虑约束条件，对粒子的速度、位置进行进化。 (6)未达到最大迭代次数返回(3)，否则结束。 3.算法改进 针对基本粒子群算法在移动机器人路径优化中存在的局部极小值问题，采用位置加权到无约束解和加变异算子两种方法，改进路径优化的效果。 4.结果评价 采用粒子群算法进行移动机器人的路径规划算法简单、寻优过程快、且具有自适应智能效果。位置加权到无约束最优和加变异算子的方法可加快算法的收敛速度，有效解决局部最小问题。 设计进度安排 1(1月24日-3月22日 文献阅读，熟悉MATLAB仿真平台 2(3月23日-3月30日 开题报告 3(3月31日-4月27日 静态全局规划及单机控制研究 4(4月28日-5月25日 动态规划及群集控制研究 5(5月26日-6月20日 毕业论文写作、答辩 设计参考文献: [1] 谭民.王硕.曹志强,多机器人系统, 清华大学出版社. [2] Jiming Liu著,靳小龙等译,多智能体原理与技术. [3] 曾建潮.介 .崔志华,粒子群算法,科学出版社. [4] 刘卫国,MATLAB程序设计与应用,高等教育出版社. [5]张颖，吴成东，原宝龙. 机器人路径规划方法综述.控制工程，2003，10. [6]黄祎，孙德宝，秦元庆.基于粒子群算法的移动机器人路径规划[J].测控技术,2006,25(4). [7]侯志荣，吕振肃.基于MATLAB的粒子群优化算法及其应用.计算机仿真[J],2003,20(10). [8]Dong H.Kim. Seiichi Shin .Self-Organization of Decentralized Swarm Agents Based on Modified Particle Swarm Algorithm. J Intel Robot Syst. DOI 10.1007/s10846-006-9047-3 指导教师签名: 日期: 课题类型:(1)A—工程设计;B—技术开发;C—软件工程;D—理论研究; (2)X—真实课题;Y—模拟课题;Z—虚拟课题 (1)、(2)均要填，如AY、BX等。 多机器人系统的路径规划算法研究 摘 要 移动机器人路径规划的研究是机器人研究领域中的一个热点，它对实现机器人导航制导及跟踪控制起着无可替代的作用。路径规划是机器人有效完成任务的安全保障，同时也是反映机器人智能化水平的重要标志。随着信息技术，通信技术，传感器技术和人工智能等相关学科的发展，许多新技术和智能算法并入该领域，促进了路径规划技术的提高。 基于粒子群算法开展移动机器人路径规划问题的研究。 本文 首先阐述了粒子群算法的原理及各个参数的物理意义，指出它作为一种智能优化算法在函数优化问题中的优越性:进化速度快，算法简单，且具有自适应性和群体智能性。对于算法会引起的局部最小问题，创造性的提出了位置加权到无约束解和加变异算子两种改进方案。 其次针对路径规划问题，采用区域划分的环境建模思想，通过构造简单的环境模型将该问题转化为带约束目标函数优化求解问题。 最后，通过仿真实现了基于粒子群算法的路径优化，比较了基本粒子群算法和各种改进算法在解决固定初始化方式下局部极小值问题上的不同效果，证明了位置加权和加变异算子的方法在解决局部最优问题上的有效性。 关键词: 移动机器人; 路径规划; 粒子群算法; 位置加权; 变异算子 I Research on Path Planning Algorithm of Multi-robot System ABSTRACT The study of path planning for mobile robot is becoming increasingly popular in the field of robot. It plays an indispensable role in the achievements of navigation and locus follow control of the robot. Path planning can guarantees security of robot’s work, it can also shows intelligence level of the robot. The development of some coherent subjects (information technology, communication technology, transducer technology and artificial intelligence) and incorporation of these new techniques give a huge advancement of skills of path planning. In this paper, path planning for mobile robot based on particle swarm optimization algorithm is studied. Firstly, the principle of PSO and physical meaning of its parameters are elaborated. As an intelligent algorithm, it shows the advantages of rapidity, simplicity, adaptivity and intelligence in application of function optimization. To solve the problem of local optimum introduced by this method, two modified schemes, position weighted to the unconstraint best solution and adding mutation operator, are creatively proposed. Secondly, a region division conception is adopted to build environment model. In this way, path planning problem is changed to be a constraint function optimization problem. The optimized path is obtained and different effects of path planning based on various modified algorithm are compared through simulation. Simulation results demonstrate the effectiveness of position weighted and mutation operator methods in solving local optimum problem. Keywords: mobile robot; path planning; particle swarm algorithm; position weighted; mutation operator II 目录 1 绪论 ........................................................... 1 1.1课题研究的背景及意义 .......................................... 1 1.2 移动机器人路径规划研究现状 ................................... 2 1.3 智能算法及其应用 ............................................. 3 1.4 课题研究的主要内容及框架 ..................................... 3 2 粒子群算法综述 ................................................. 5 2.1 粒子群算法的研究背景 ......................................... 5 2.2 基本粒子群算法 ............................................... 5 2.2.1 基本概念 ................................................... 5 2.2.2 算法原理及流程 ............................................. 6 2.3 改进粒子群算法 ............................................... 7 2.4 粒子群算法和其他进化算法的比较 ............................... 8 3 移动机器人路径规划 ............................................ 10 3.1 环境建模 .................................................... 10 3.2 路径规划的方法 .............................................. 11 3.2.1传统路径规划方法 ........................................... 11 3.2.2 智能路径规划方法 .......................................... 11 3.3 约束优化问题及处理方法 ...................................... 13 3.3.1 约束优化问题的描述 ........................................ 13 3.3.2 约束优化问题的处理方法 .................................... 13 III 4 基于粒子群优化的路径规划算法及仿真 ............................ 14 4.1仿真平台简介 ................................................. 14 4.2 问题描述与环境建模 .......................................... 14 4.3 路径初始化 .................................................. 16 4.4 基于粒子群算法的路径规划仿真 ................................ 18 4.4.1 基于基本粒子群算法的路径规划仿真 .......................... 18 4.4.2 基于改进粒子群算法的路径规划仿真 .......................... 21 4.5 仿真结果分析 ................................................ 23 4.6程序调试中的问题及处理 ....................................... 24 5 结论与展望 .................................................... 25 5.1 结论总结 .................................................... 25 5.2 以后可做的工作和展望 ........................................ 26 谢辞 ............................................................ 27 参考文献 ........................................................ 28 附录A 外文翻译-原文部分 ......................................... 29 附录B 外文翻译-译文部分 ......................................... 35 附录C 流程图及仿真图形 .......................................... 39 附录D 主要源程序 ................................................ 52 IV 华东交通大学毕业设计 1 绪论 1.1课题研究的背景及意义 随着计算机技术、信息技术、控制理论、人工智能和传感器技术等学科的发展和成熟，以此交叉而形成的机器人学的研究也进入了一个崭新的阶段。机器人的研究经历了从可编程的、示教再现型的工业机器人到具有一定传感、适应能力的机器人再到配备多种先进传感器，具有自学习和较强适应能力的智能机器人;从结构简单、功能单一的单机机器人到[]1结构复杂，适应复杂环境，功能多样的多机器人系统的发展过程。移动机器人的研究始于20世纪60年代末期，斯坦福研究院的Nils Nilssen和Charles Rosen等人，在1966年至1972年间研究制造出了名为Shakey的自主移动机器人，目的是研究应用人工智能技术，在复杂环境下机器人系统的自主推理、规划和控制问题。与此同时，最早的操作式步行机器人也研制成功，从而开始了机器人步行机构方面的研究，以解决机器人在不平整地域内的运动问题。70 年代末，随着计算机的应用和传感技术的发展，移动机器人研究又出现了新的高潮。特别是在80年代中期，设计和制造机器人的浪潮席卷全世界，一大批世界著名的公司开始研制移动机器人平台，这些移动机器人主要作为大学实验室及研究机构的移动机器人实验平台，从而促进了移动机器人学多种研究方向的出现。90年代以来，以研制高水平的环境信息传感器和信息处理技术，高适应性的移动机器人控制技术，真实环境下的规划技术为标志，开展了移动机器人更高层次的研究。2004年3月13日，作为研制无人驾驶作战车的一部分，DARPA在美国西部的莫哈维沙漠组织了首次无人驾驶车赛，其中CMLJ的基于HMMWV(类似于jeep由悍马车改造)的NAVLAB移动机器人系统取得了最好的成绩，在越野环境下自主行驶了7.4英里，它还配备了扫描雷达、立体影像系统、扫描测距雷达系统、地图绘制工具、方位评估系统以及强大的计算系统。其路径规划系统正是针对野外环境下环境信息不完全，甚至完全未知的情况设计的。 移动机器人的路径规划是机器人导航系统中不可缺少的重要部分，导航系统是移动机器人的研究核心，同时也是移动机器人实现智能化及完全自主的关键技术。移动机器人的导航问题主要是由Durrant Whyte H F提出的三个问题 ?“我现在何处?”?“我要往何[]2处去?”?“要如何到该处去?”。大多数导航系统由两级规划组成，即局部规划(Local Planning)和全局规划(Global Planning)。前者主要解决?、?两个问题,即机器人定位和路径跟踪问题，而后者主要解决问题?，即全局目标分解成局部目标，再由局部规划实现局部目标。 移动机器人按照预先给出的任务命令，根据已知的环境信息做出全局路径规划，并在行进过程中，不断感知周围的局部环境信息，自主地做出各种决策，并随时调整自身位置，引导自身安全行驶或跟踪已知路径达到目标位置。移动机器人要实现导航涉及到的基本行为有:自身位置和周围环境的感知与识别、路径规划、路径跟踪、障碍回避等。 路径规划是移动机器人导航技术中不可缺少的重要组成部分，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标。 路径规划是移动机器人完成任务的安全保障，同时也是移动机器人智能化程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高移动机器人的智力水平，减少移动机器人在移动过程中存在的不确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距 1 井雅洁:多机器人系统的路径规划算法研究 离搬运机器人、探测机器人、服务机器人、汽车自动驾驶系统打下基础。 多机器人系统的路径规划意味着在同一工作空间中为系统中的每一个机器人找到一条合适的路径，并保证每一时刻机器人与机器人之间无碰撞，机器人与环境之间无碰撞，这就涉及到机器人之间的路径协调与避碰问题。多机器人系统路径规划的研究是机器人学 多个移动机器人在复杂的工作环境下按路径规划领域中的一个非常活跃的分支，它对引导 何种路径运动有着重要的理论指导意义，其现实的应用价值也随着移动机器人在工业、航空、航天等领域的应用越来越多的突显出来。 1.2 移动机器人路径规划研究现状 移动机器人路径规划(Path Planning of Mobil Robot)是机器人学的一个重要的研究领域，也是一个最基本的问题。它被描述为:给定一个移动机器人所处的环境(环境可以通过移动机器人传感器系统或者别的途径获得)，一个起始点和一个期望的终止点，规划出一条移动机器人可行的从起始点到达终止点，且避开环境中障碍物的最短的运动路径。这个问题从表面上看是一个简单易描述的问题，而实际上它的复杂度随着移动机器人的构型空间维度的增加而不断增长。对移动机器人路径规划的研究目前主要有两类:一类是移动机器人自主导航;另一种是根据移动机器人所处的环境，由一个主机首先规划好移动机器人的路径，然后设计相应的控制器，控制移动机器人跟踪给定的规划好的路径。单移动机器人路径规划的研究经过多年的发展已成为一个日趋丰富、成熟的方向。近几年，多移动机器人系统路径规划的问题受到了众多学者的重视，成为了一个比较复杂而又独具特色的优化问题。在生产与科研中，如工厂的复杂装配中，需由许多移动机器人代替人类在恶劣的环境下合作完成繁重的装配任务。在这种情况下，多个移动机器人与所处的环境就构成了一个系统，为完成给定的任务，就需要对多个机器人同时进行路径规划，即在规划多个机器人的运动轨迹时要考虑群体协调的问题。多机器人系统的路径规划现在已经成为一个研究的热点，所采用的优化算法也从传统的算法发展为群体智能算法。智能算法作为一种模拟自然界生物群体行为的进化算法，为优化问题提供了一种有效的求解方法。常用的智能算法有遗传算法、蚁群算法、粒子群算法等，它们都在不同程度上被借鉴用来规划移动机器人的运动路径。本课题重点研究粒子群算法在移动机器人路径规划中的应用。 路径规划是按照某一性能指标搜索一条机器人从起始状态到目标状态的最优或近似最优的无碰路径。进行路径规划需要做两大块工作:构建环境模型以及采用优化技术优化路径。根据规划过程中环境信息获取方式的不同和路径优化过程中采取的优化算法的不同可对路径规划问题做出不同的分类。 在环境信息获取方式方面，根据机器人的工作环境模型的不同可以分为两种。一种是基于环境先验信息的路径规划，作业环境的全部信息都是预知的，也即全局路径规划;另一种是基于传感器信息的路径规划，作业环境的信息是全部未知或部分未知的，即障碍物形状、尺寸和位置等信息必须通过传感器在线获取，也即局部路径规划。常用的全局路径规划的方法有可视图法、自由空间法、环境地图法和栅格法等。常用的局部路径规划的方法有人工势场法等。 在算法优化方面，可将路径规划分为传统优化和智能优化两种。传统的优化方法有自由空间法、图搜索法、栅格解耦法等;智能优化方法有模糊逻辑法、神经网络法、遗传算法、粒子群算法等。 另外，根据机器人工作空间中障碍物的运动特点的不同还可将路径规划分为静态确定环境下的路径规划和动态不确定环境下的路径规划。在静态环境中，障碍物的位置、形状、大小是确定不变的，这种情况下进行路径规划不用过多考虑障碍物的运动情况和信息，相 2 华东交通大学毕业设计 对于要实时分析障碍物运动情况的动态环境路径规划算法要简单一些。 采用智能算法进行复杂环境下移动机器人路径规划的研究是当今路径规划领域研究的热点，其研究成果已经应用于复杂装配车间、军事、航空航天等多个领域，显示出了巨大的经济价值和社会应用价值。本篇论文重点研究复杂障碍物环境下移动机器人的路径规划。所采用的优化算法是智能算法中的粒子群算法。 1.3 智能算法及其应用 智能算法(Swarm Intelligence Algorithm)的研究开始于20世纪90年代初，其基[]3本思想是模拟自然界生物的群体行为来构造随机优化算法。它是受自然界中生物的群体行为启发，研究生物群体的生存、活动特性的规则进而建立数学模型，抽象的表示群体行为的算法。智能算法主要采用“群体”、“选择”、“进化”、“学习”等概念表述群体的行为特性，通过建立相应的数学算式，将对群体行为的研究生成的算法应用到更广泛的优化领域。典型的智能算法有遗传算法和粒子群算法。 遗传算法(Genetic Algorithm)是美国Michigan大学的J.H. Holland教授和他的学生于20世纪六七十年代提出的，是一类基于自然界生物进化和种群基因原理的随机搜索算法。作为一种新型参数优化方法，80年代中期以来它获得广泛应用。遗传算法基于自然选择原理和群体进化机制，采用从自然界选择，群体进化中抽象出来的几个算子——复制、交叉和变异操作，对参数编码的字符串进行操作，每一个字符串对应于一个可行解，这种遗传操作可对多个可行解组成的群体进行优化。作为一种进化算法，遗传算法具有鲁棒性强，应用灵活等特点，已被广泛应用于决策规划、调度、机器学习等领域。 粒子群算法(Particle Swarm Optimizer)是在1995年由美国心理学家James Kennedy和电气工程师 Russel Eberhart 共同提出的，其基本思想是受他们早期对许多鸟类的群[]3体行为进行建模和仿真研究结果的启发。该算法是模拟鸟群飞行觅食的行为，通过鸟之间的集体协作使得群体达到最优目的的基于群体智能(Swarm Intelligence)的随机优化方法。在粒子群优化算法中，个体通过“认知”和“学习”两个行为，动态跟踪两个极值(个体最优和群体最优)来更新其速度和位置，经过多次迭代，达到群体全局最优的效果。作为一种仿生算法，粒子群算法有着个体数目少、计算简单、鲁棒性好等特点，在各类多维连续空间优化问题上均可取得非常好的效果。同时，因为有着深刻的智能背景，它既适合科学研究，又适合工程应用。近几年，已提出了多种PSO改进的算法，并且PSO已广泛应用于目标函数优化，神经网络训练，模式分类，模糊系统以及其他应用领域。 本篇论文重点研究采用粒子群算法进行移动机器人路径规划，同时也研究了加入变异算子改进粒子群算法时路径优化的效果。 1.4 课题研究的主要内容及框架 针对采用智能算法进行移动机器人路径规划研究的现状，本论文主要讨论了将粒子群算法应用于复杂环境下机器人路径规划的问题。论文首先研究了受仿生群体行为启发的粒子群优化算法的原理和相关参数的物理意义，随后将其应用于移动机器人路径规划问题中，并以MATLAB仿真平台为基础实现了基于粒子群优化算法的移动机器人路径规划的仿真实验，最后研究了位置加权改进粒子群算法、加变异算子改进粒子群算法在解决局部极小值问题上的应用效果。具体的结构编排如下: 第一章简单介绍了移动机器人路径规划研究的背景、现状并指出常用的规划方法。讲 3 井雅洁:多机器人系统的路径规划算法研究 述了智能算法，尤其是粒子群算法及其应用。 第二章详细阐述了粒子群算法的思想和原理，研究该算法中各个参数的物理意义及其对进化过程的影响。针对优化问题中出现的局部极小值问题提出采用位置加权改进粒子群算法和加遗传变异算子改进粒子群算法两种解决方案。通过与其它进化算法的比较，进一步研究了粒子群算法的特性。 第三章系统阐述了移动机器人路径规划中的两大块内容:环境建模和路径规划的方法。从传统和智能两种角度讲述了常用的路径规划方法及特点。最后提出约束优化问题及其解决方案。 第四章研究了将粒子群算法应用于移动机器人路径规划中的整个过程并进行了实验仿真。其中主要内容有问题描述与环境建模、生成初始化路径、采用各种粒子群进化算法优化路径及仿真结果分析等。其中，针对局部极小问题，研究了改进算法，如位置加权法和加变异算子法的解决效果。 最后第五章我们对本篇论文做了总结。指明了本论文的创新之处并对以后可做的工作进行了展望。 4 华东交通大学毕业设计 2 粒子群算法综述 2.1 粒子群算法的研究背景 寻求性能良好的全局优化算法并使之能可靠收敛于问题的全局最优解，这一直是优化领域孜孜以求的研究目标和热点。所谓最优化问题，就是在满足一定的约束条件下，寻求一组参数值，以使某些最优性能度量得到满足，即使系统的某些性能指标达到最大或最小。最优化的应用可以说涉及到工业，社会，经济，管理等各个领域，其重要性是不言而喻的。按照目标函数，约束函数的性质以及优化变量的取值范围等，可将最优化问题分成许多类型，每一种类型根据其特征不同有特定的求解方法。 x,S常见的优化方法大多数为局部优化的方法，都是从一个给定的初始点开始，0依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止条件。成熟的局部优化算法有Newton-Raphsonf法， Fletcher-Reeves法 Polar-Ribiere 法Davidon-Fletcher-Power(DFP)法 Broyden-Fletcher-Goldfarb-Shann (BFGS)方法等，所有这些局部优化算法都是针对无约束优化问题提出的，而且对目标函数均有一定的解析性要求。对于约束非线性优化问题，最常用的方法是将约束问题通过罚函数转换成无约束优化问题，然后再采用无约束优化方法进行求解。 全局优化是另外一种优化方法，它是在全局范围内寻求目标的最优解。到目前为止，全局优化问题也已存在许多优化方法，如填充函数法等，但比起局部优化问题的众多成熟的方法，其间还有很大差距。解析性优化是全局优化的一种常用的方法，但它对目标函数及约束域均有较强的解析性要求，对于诸如目标函数不连续，约束域不连通，目标函数难以用解析函数表达或者难以精确估计等问题，就难以适应。为了可靠解决全局优化问题，人们试图离开解析确定型的优化算法研究，转而探讨对函数解析性质要求较低甚至不做要求的随机型优化方法。最早的随机优化方法是基于Monte-Carlo方法的思想，针对具体问题性质的特点，构造以概率1收敛于全局最小点的随机搜索算法。真正有效且具有普遍适应性的随机全局优化方法是近十几年人们模拟自然界的一些自然现象而发展起来的一系列仿生智能优化算法，如模拟退火法，进化类算法，群体智能等。群体智能算法(Swarm 的研究开始于20世纪90年代初，其基本思想是模拟自然界生物Intelligence Algorithm) 的群体行为来构造随机优化算法。典型的方法有M.Dorigo提出的蚁群算法和R.Eberthart [3]提出的粒子群算法。它们因计算快速性和算法本身的易实现性，引起了国际上优化领域众多学者的关注和研究。 2.2 基本粒子群算法 2.2.1 基本概念 自然界中各种生物体均有一定的群体行为，而人工生命的主要研究领域之一就是探索这种群体行为，从而在计算机上构建其群体模型。通常，群体行为可由几条简单的规则进行建模，如鱼群，鸟群等。虽然每个个体具有非常简单的行为规则，但群体的行为却非常复杂。Reynolds将这种类型的个体称为boid，并使用计算机图形动画对复杂的群体行为进行仿真，他在仿真中采用了下列三条简单的规则:(1)飞离最近的个体，以避免碰撞; 5 井雅洁:多机器人系统的路径规划算法研究 (2)飞向目标;(3)飞向群体中心。采用上述规则描述群体内每个个体的行为，这是粒子群算法的基本概念之一。Boyd和Richerson[2]在研究人类决策的过程中，提出了个体学习和文化传递的概念。根据他们的研究结果，人们在决策的过程中使用两类重要的信息，一是自身的经验，二是他人的经验。也就是说，人们根据自身的经验和他人的经验进行自己的决策。这是粒子群算法的另一基本思想。 粒子群算法(Particle Swarm Optimizer)是在1995年由美国心理学家James Kennedy和电气工程师Russel Eberhart 共同提出的，其基本思想是受他们早期对许多鸟类的群体行为进行建模和仿真研究结果的启发。而他们的模型及仿真算法主要利用了生物学家Frank Hepper的模型。Frank Hepper模型是一种鸟类被吸引飞向栖息地的群体行为模型。飞行过程中，每一只鸟试图停在鸟群而又不相互碰撞，一只鸟飞向栖息地，将导致它周围的其他鸟也飞向栖息地，最终整个鸟群都落在栖息地。粒子群算法借助该模型将鸟群看作是粒子群，寻找使粒子飞向解空间最好解(全局最优)处的进化算法。James Kennedy和Russel Eberhart 在1995年的IEEE国际神经网络学术会议上正式发表了题为“Particle Swarm Optimization”的文章，标志着粒子群算法的诞生。 2.2.2 算法原理及流程 粒子群算法与其他进化类算法相类似，也采用“群体”与“进化”的概念，同样也是依据个体的适应值大小进行操作。所不同的是，粒子群算法不像其他进化算法那样，对个体使用进化算子，而是将每个个体看作是在n维搜索空间中的没有重量和体积的粒子，并在搜索空间中以一定的速度飞行。该飞行速度由个体的飞行经验和群体的飞行经验进行 X,(x,x？,x)V,(v,v,？,v)动态调整。设为粒子i的当前位置，为粒子i的当前ii1i2inii1i2in P,(p,p,？,p)飞行速度。为粒子i所经历的最好位置，也就是其所经历的具有最好ii1i2in 适应值的位置，称为个体最优位置。对于最小化问题，目标函数值越小，对应的适应值越好。 我们取f(X)为最小化问题的目标函数，则粒子i的当前最好位置由下式确定: P(t)f(X(t，1)),f(P(t))　　　　　　若,iiiP(t，1), 　 (2.1) ,iX(t，1)　　　　　若f(X(t，1)),f(P(t)iii, 设群体中的粒子个数为N，群体中所有粒子所经历过的最好位置为g(t),称为全局最好位置，则 (2.2) ,,,,g(t),P(t),P(t),？,P(t)f(g(t)),minf(P(t)),f(P(t)),？,f(P(t))12N12N 有了以上定义，基本粒子群算法的进化方程可描述为: (2.3) v(t，1),v(t)，cr(t)(p(t),x(t))，cr(t)(g(t),x(t))ijij11jijij22jjij (2.4) x(t，1),x(t)，v(t，1)ijijij c,c其中:下标“j”表示粒子的第j维，“i”表示粒子i，t表示第t代，为加速常数，12 r，U(0,1),r，U(0,1)通常在0-2之间取值，为两个相互独立的随机函数。式(2.3)表明，12 P粒子通过动态跟踪两个极值(个体最优和群体最优g)来更新其速度和位置，速度决定i c了粒子在搜索空间单位迭代次数的位移，即位置的变化量。调节粒子飞向自身最好位置1 c方向的步长，称为认知系数;调节粒子飞向全局最好位置方向的步长，称为社会学习2 系数。 6 华东交通大学毕业设计 v为了减少在进化过程中粒子离开搜索空间的可能性，通常限定在一定范围内，即ij ,,v,,v,vv。粒子的速度在空间中的每一维上的最大速度限制值为，它用来限制ijmaxmaxmax v粒子速度的边界值。该值一般由使用者自己设定，是一个非常重要的参数。如果取值max v太大，则粒子也许会飞过优秀区域;另一方面，如果取值太小，则粒子可能无法对局max 部最优区域以外的地方进行充分的探测，从而问题求解容易陷入局部最优，无法搜索到解空间，，每一维都用相同的设置方更佳的粒子位置。通常设置v,k,x0.1,k,0.2jmaxjmax 法。 加速常数c，c分别调节粒子向个体最优和群体最优方向飞行的最大步长，决定个12 体经验和群体经验对粒子运行情况的影响大小，反映了粒子之间的信息交流与学习。如果c=0，则粒子只有表现社会行为，它的收敛速度更快，但对于复杂问题，容易陷入局部最1 优;如果c=0，则粒子没有群体信息共享，这样一个规模为N的粒子群等价于N个独立2 的粒子，得到最优解的概率非常小。一般设置c=c，改变这些常数会改变系统的“张力”，12 较低的c、c值使得粒子徘徊在远离目标的区域，较高的c、c值产生陡峭的运动或越1122 过目标区域。为了平衡随机因素的作用，一般情况下设置c=c=2，大部分算法都采用这12 个建议。 基本粒子群算法的初始化过程为: (1)设定群体规模N; x,,,x,x(2)对任意i,j在内随机产生; ijmaxmax v,,,v,v(3)对任意i,j在内随机产生; ijmaxmax y,x(4)对任意i,设。 ii 基本粒子群算法的流程如下: 依据初始化过程，对粒子群的随机位置和速度进行初始设定; (1) (2)计算每个粒子的适应值; P，将其适应值与所经历的最好位置(3)对于每个粒子的适应值进行比较，若较好，i 则将其作为当前的最好位置; (4)对于每个粒子，将其适应值与全局所经历的最好位置g的适应值进行比较，若 较好，则将其作为当前的全局最好位置; (5)根据方程(2.3)，(2.4)对粒子的速度和位置进行进化; (6)如未达到结束条件(通常为足够好的适应值或达到一个预定最大代数)，则返回 步骤(2)。 2.3 改进粒子群算法 基本粒子群算法存在收敛速度慢，易陷入局部极小点等问题。因此需要对基本粒子群算法进行改进，使得算法在保持结构简单特点的基础上可以加快收敛速度，同时有效摆脱局部极小点的束缚。改进粒子群算法的方法很多，本论文涉及到的方法有加惯性权重w改进粒子群算法、位置加权到无约束解改进粒子群算法、引入遗传算法中变异算子改进粒子群算法等。 加惯性权重w改进粒子群算法的公式如下所示: (2.5) v(t，1),w,v(t)，cr(t)(p(t),x(t))，cr(t)(g(t),x(t))ijij11jijij22jjij (2.6) x(t，1),x(t)，v(t，1)ijijij 7 井雅洁:多机器人系统的路径规划算法研究 比较公式(2.3)和(2.5)可见，当惯性权重w=1时，两式相同，从而表明带惯性权重的粒子群算法是基本粒子群算法的扩展。惯性权重w表明粒子原先的速度在多大程度上得到保留。较大的w可加强PSO算法的全局搜索能力，较快地定位最优解的大致位置;较小的w有较强的局部搜索能力，即粒子速度及位置变化减慢，开始精细的局部搜索。随着迭代次数的增加，惯性权重w应不断的减少，从而使得粒子群算法在初期具有较强 [4]的全局收敛能力，而晚期具有较强的局部收敛能力。在文献中，惯性权重满足: t (2.7) w,0.9,，0.5MaxNumber 这样自适应的调整w值，可使全局搜索能力和局部搜索能力得到良好的平衡，使得搜索快速收敛到全局最优解。 位置加权到无约束解改进粒子群算法的公式如下: xx,0jijxtxtvtk(，1),()，(，1)，， (2.8) ijijijxx,ij0j x,x0jijk，比较(2.8)与(2.6)可见，(2.8)中多了一项，它表示粒子趋向无约束 x,xij0j 解的分量，称为位置加权到无约束解项，其中“”表示粒子第j个维度在无约束条件x0j 下的最好位置。当粒子第j维的位置在无约束最优解的上面时，该项为负值;在无约束最优解的下面时，该项为正值。可见，加入该项可使粒子更快的趋向无约束最优解。k的大小决定粒子位置趋向无约束解的步长。这样改进之后，可加快粒子群的收敛速度。 另一种位置加权的方法是改进群体最优的位置，即令群体最优更快的趋向无约束解，这样整个群体中的粒子都会更快的趋向全局最优解，具体公式如下: xx,0jijgjgjk(),()，， (2.9) xx,ij0j x,x0jijk，其中的意义及用法同(2.8)。速度进化与位置进化公式与基本粒子群进 x,xij0j 化公式相同。以上几种方法单独使用时效果可能不是很明显，因此可以结合起来使用，优化粒子群算法的性能，加快算法的收敛速度。 借鉴遗传算法中变异的思想是改进粒子群算法的又一方法，它对于解决局部最小点的问题有着很好的效果。在使用基本粒子群算法优化目标函数时，对于局部最小问题的解决是一个研究的热点，一些改进的算法存在着复杂度高，不便于使用或收敛速度慢的特点。使用遗传算法中的变异算子，对于用基本粒子群算法进化了的粒子位置信息，以一定的概率，将粒子某些维度的位置强制变异到无约束最优解处，或变异粒子相邻维度的位置信息，使得相近维度无尖峰值存在，再经过选择得到相同规模的适应性较强的粒子。这样处理，可使目标函数快速跳出局部最小点的束缚，同时算法的复杂度也不是很高。 2.4 粒子群算法和其他进化算法的比较 粒子群算法与其他进化算法有许多共同之处。首先，都使用了“群体”概念，用于表示一组解空间中的个体集合。如果把粒子所经过的最好位置看作是群体的组成部分，则粒子群的每一步进化呈现出弱化形式的“选择”机制。在进化策略算法中，子代与(u，,) 父代竞争，若子代具有更好的适应值，则用来代替父代，而PSO算法的进化方程式(2.1)具有与此相类似的机制。其唯一的差别在于，只有当粒子的当前位置与所经历的最好位置 8 华东交通大学毕业设计 P相比具有更好的适应值时，粒子所经历的最好位置(父代)才会唯一地被粒子的当前位置(子代)所取代，即PSO算法隐喻着一定形式的“选择”机制。 其次，式(2.3)所描述的速度进化方程与实数编码遗传算法的算术交叉算子相类似。通常，算术交叉算子由两父代个体的线性组合产生两个子代个体，而在PSO算法的速度 V(t，1)项，就可以将它理解为由两个父代个体产生一个子代进化方程中，假若先不考虑ij V(t，1)个体的算术交叉运算。从另一个角度，不考虑项的情况下，速度进化方程也可以ij 看作是一个变异算子，其变异的强度(大小)取决于两个父代粒子间的距离，即代表个体 V(t，1)最好和全局最好的两个粒子位置的距离。至于项，也可理解为一种变异的形式，ij 其变异的大小与粒子在当前代中的位置相关。 在进化算法中，人们习惯于将每一步进化迭代理解为用一个新的个体(即子代)代替旧个体(即父代)的过程。如果我们将PSO算法的进化迭代理解为一个自适应过程， XV则粒子的位置就不是被新的粒子所取代，而是根据速度向量进行自适应变化。这样，ii PSO算法与其他进化算法的最大不同点在于:PSO算法在进化过程中同时保留和利用位置与速度(即位置变化程度)信息，而其他算法仅保留和利用位置的信息。 如果将式(2.4)看作一个变异算子，则PSO算法与进化规划很相似。所不同的是，在每一代，PSO算法中的每一个粒子只朝一些根据群体的经验认为是好的方向飞行，而在进化规划中可通过一个随机函数变异到任何方向。也就是说，PSO算法执行一种有“意识(conscious)”的变异。从理论上讲，进化规则具有更多的机会在优化点附近开发，而PSO在“意识”能提供的有用的信息的条件下，有更多的机会更快地飞向更好解的区域。 9 井雅洁:多机器人系统的路径规划算法研究 3 移动机器人路径规划 移动机器人路径规划是机器人学研究的一个重要分支。所谓机器人的最优路径规划问题，就是依据某个或某些准则(如工作代价最小，行走路径最短，行走时间最短等)，在其工作空间中找到一条从起始状态到目标状态的能避开障碍物的最优路径。这是一个带约束条件的优化问题，整个过程可以分为几个块来完成，包括问题描述与规划空间建模，初始路径生成和利用算法优化路径等。本章介绍了路径规划中的一些基本知识和方法，如环境建模、路径规划的方法和约束优化问题的解决。 3.1 环境建模 进行机器人路径规划首先必须对机器人所在的自由空间进行描述，即进行规划空间建模，也即环境建模。环境建模是机器人路径规划的第一步，也是非常重要的一步，建模方式的不同，会影响路径优化的效果，同时也会影响算法的复杂度和程序运行的速度。环境建模可分为连续环境建模和离散环境建模两种。 自由空间法是机器人连续环境建模的一种常用的方法。采用这种方法建立的机器人运动空间模型比较简单，且能得到较好的优化路径。自由空间法是采用预先定义的如广义锥形和凸多边形等基本形状构造自由空间,并将自由空间表示为连通图,通过搜索连通图来进行路径规划,其算法的复杂程度往往与障碍物的个数成正比。链接图法就是这样一种方[]5法。 图搜索法是另外一种连续环境建模的方法。它机器人视为一点，将机器人、目标点和多边形障碍物的各顶点进行组合连接，要求机器人和障碍物各顶点之间、目标点和障碍物各顶点之间以及各障碍物顶点与顶点之间的连线，均不能穿越障碍物，即直线是可视的。搜索最优路径的问题变为求这些可视直线的最短距离问题，可运用优化算法，简化可视图,缩短搜索时间。 栅格法是离散环境建模的一种常用的方法。它是目前研究最广泛的路径规划方法。该方法将机器人的工作空间解耦为多个简单的区域,一般称为栅格。由这些栅格构成了一个连通图,在这个连通图上搜索一条从起始栅格到目标栅格的路径,这条路径是用栅格的序号来表示的。在进行环境建模时，首先要按照一定的规则将机器人工作空间划分为用栅格可以表示的小区域，然后采用一定的编码机制对栅格进行编码，通常采用的是二进制和十进制两种编码机制。编码机制必须要确保待求解问题的最优解包含于编码机制所确定的搜索空间中，同时，还必须便于适应度函数的计算。经过栅格编码，可将移动机器人的路径表示为一定长度的染色体串，染色体串中的某一位代表移动机器人的路径经过该位所表示[]6的相应编码的工作空间中的一点。这样对染色体串进行操作，就可以对路径进行优化。 本篇论文采用区域划分的环境建模思想。将机器人的工作环境按垂直于起始点到目标点连线的方向进行等分。在每一垂线上取一个自由点，依次连接从起始点到目标点的这一系列点，即可表示出一条移动机器人的运动路径。这种环境建模的思想简单易行，规划出来的构型空间易于表示，减小了算法的复杂度，有利于路径优化的实现。 10 华东交通大学毕业设计 3.2 路径规划的方法 移动机器人的路径规划研究是一个比较活跃的领域。其中对规划方法的研究已经形成了很多成熟的理论。路径规划的方法可分为传统方法和智能方法两大类，下面分别进行阐述。 3.2.1传统路径规划方法 (1)自由空间法 为了简化问题,通常采用“结构空间”来描述机器人及其周围的环境。这种方法将机器人缩小成点,将其周围的障碍物及边界按比例相应地扩大,使机器人点能够在障碍物空间中移动到任意一点,而不与障碍物及边界发生碰撞。 (2)图搜索法 图搜索方法中的路径图由捕捉到的存在于机器人一维网络曲线(称为路径图)自由空间中的节点组成。建立起来的路径图可以看作是一系列的路径。而路径的初始状态和目标状态同路径图中的点相对应,这样路径规划问题就演变为在这些点间搜索路径的问题。通过起始点和目标点及障碍物的顶点在内的一系列点来构造可视图。连接这些点,使某点与其周围的某可视点相连(即使相连接的两点间不存在障碍物或边界)。然后机器人沿着这些点在图中搜索最优路径。 (3)人工势场法 []6 人工势场法是Khatib提出的。其基本思想是将机器人的工作空间看作一种虚拟力场,障碍物产生对机器人的排斥力,使得机器人不会进入障碍物范围，目标产生对机器人的吸引力,使得机器人奔向目标。以吸引力和排斥力的合力作为机器人的加速力，用该力来控制机器人的运动方向和计算机器人的位置。该方法结构简单,便于底层的实时控制，在实时避障和平滑的轨迹控制方面，得到了广泛的应用。但是，由于势场法把所有信息压缩为单个合力,这样就存在把有关障碍物分布的有价值的信息抛弃的缺陷,因此易陷入局部最小值，使机器人在到达目标点之前就停留在局部最优点。除此之外，势场法还存在三个方面的问题:1)在相近障碍物之间不能发现路径;2)在障碍物前面振荡;3)在狭窄通道中摆动。 大部分机器人路径规划都是基于上述几种方法进行的,但是以上这些传统方法在路径搜索效率及路径优化方面尚有待于进一步改善。而现在通常使用的搜索技术包括:梯度法,图搜索方法,枚举法、随机搜索法等。这些方法中梯度法易陷入局部最小点,图搜索方法、枚举法不能用于高维的优化问题,而随机搜索法则计算效率太低。 3.2.2 智能路径规划方法 近年来,随着粒子群等智能方法的广泛应用,机器人路径规划方法也有了长足的进展,许多研究者把目光放在了基于智能方法的路径规划研究上。其中,应用较多的算法主要有模糊方法、神经网络、遗传算法和粒子群算法等。 (1)基于模糊逻辑的机器人路径规划 模糊方法是在线规划中通常采用的一种规划方法，包括建模和局部规划。庄晓东等提出一种基于模糊概念的动态环境模型,参照物体的位置和运动信息构造二维隶属度函数，然后通过模糊综合评价对各个方向进行综合考察,得到搜索结果。该方法在移动障碍物和 11 井雅洁:多机器人系统的路径规划算法研究 移动目标的环境中能有效地实现机器人避碰和导航。李彩虹等提出了一种在未知环境下移动机器人的模糊控制算法,并对此算法进行了推导与仿真,证明该算法鲁棒性强,可消除传统算法中存在的对移动机器人的定位精度敏感、对环境信息依赖性强等缺点,使移动机器人的行为表现出很好的一致性、连续性和稳定性。Hartmut Surmann等提出一种未知环境 由8个不同的超声传感器来提供环境信息,然后利用基于下的高级机器人模糊导航方法,[]7模糊控制的导航器来计算这些信息,规划机器人路径。其模糊规则建立见表1。 该方法在环境未知或发生变化的情况下,能够快速而准确地规划机器人路径,对于要求有较少路径规划时间的机器人是一种很好导航方法。但是,其缺点是当障碍物数目增加时,该方法的计算量会很大,影响规划结果。 表1 基于模糊控制的机器人导航模糊规则建立 命令 模糊量 命令 模糊量 停止 0?[- 015,015] 立即右转 6?[515,615] 面向前 1?[015,115] 前行 7?[615,715] 下个命令左转 2?[115,215] 转向 8?[715,815] 下个命令右转 3?[215,315] 新:前一个命令左转 9?[815,915] 后退 4?[315,415] 新:前一个命令右转 10?[915,1015] 立即左转 5?[415,515] — — (2)基于神经网络方法的机器人路径规划 禹建丽等提出了一种基于神经网络的机器人路径规划法,研究了障碍物形状和位置已知情况下的机器人路径规划算法,其能量函数的定义利用了神经网络结构根据路径点位于障碍物内外的不同位置选取不同的动态运动方程,规划出的路径达到了折线形的最短无碰路径,计算简单,收敛速度快。陈宗海等提出了一种在不确定环境中移动机器人的路径规划 为了提高规划的效率,在避障规划中采方法,将全局路径规划分解为局部路径规划的组合, 用了基于案例的学习方法, 以ART—2神经网络实现案例的匹配学习和扩充,满足了规划的实时性要求。为了提高机器人路径规划的速度,禹建丽等在利用神经网络路径规划方法的基础上,又引进了线性再励的自适应变步长算法。这种方法实现了步长的自适应选择,使路径规划速度比原来的神经网络规划提高了10倍左右。 (3)基于遗传算法的机器人路径规划 遗传算法是一种借鉴生物界自然选择和遗传机制的搜索算法，采用从自然界选择，群体进化中抽象出来的几个算子——复制、交叉和变异操作，对群体某项指标进行优化。由于它具有简单、健壮、隐含并行性和全局优化等优点，对于传统搜索方法难以解决的复杂和非线性问题具有良好的适用性。应用遗传算法解决自主移动机器人路径规划问题，可以避免困难的理论推导,直接获得问题的最优解。 (4)基于粒子群算法的机器人路径规划 粒子群算法是应用于移动机器人路径规划中的一种新的方法，由于其计算简单，鲁棒性强，规划出的路径好，已受到优化领域专家的广泛重视。粒子群算法适宜于连续空间下机器人的路径规划，该算法在规划空间上采用与遗传算法相同的链接图建模法，其次使用图论中成熟的算法粗略搜索出可选路径(多条)，最后通过粒子群算法优化各条路径并得出全局最优(群体最优)解。有关用粒子群优化进行路径规划的细节，将在第四章重点阐述，它是本论文研究的重点内容。 12 华东交通大学毕业设计 3.3 约束优化问题及处理方法 3.3.1 约束优化问题的描述 在科学与工程领域中，许多极值问题的求解往往受到各种现实因素的制约，这些制约通常由一系列的约束条件来描述，求解带约束条件的极值问题则被称为约束优化问题(Constrained Optimization)。具体可由下述一般形式的非线性规划来表示: nminf(X)　　　　X,E　　　　 (3.1) s.t.　　g(X),0　　i,1,2,3,？,mi g(X)其中表示问题的约束条件。 i 由于约束条件的存在，使得约束极值问题的求解要比无约束极值的求解复杂、困难的多。对于约束极小值问题来说，不仅要使得目标函数在迭代过程中不断减小，而且还要注意解的可行性。为了简化约束优化问题的寻优过程，通常可用将约束优化问题转化为无约束优化问题、将非线性规划问题转化为线性优化问题的方法，把复杂的问题简单化。 移动机器人路径规划问题就是一种带约束的优化问题，即是在满足机器人不与障碍物相撞的条件下，寻找一条从起始点到目标点的最优路径。约束条件为机器人路径不与障碍物相交。为此需要寻求使得表示路径长度的目标函数取得极小值的可行解(一个解表示机器人的一条路径)。对于不可行解，要通过约束优化问题的处理方法，化之为无约束优化问题。 3.3.2 约束优化问题的处理方法 处理约束优化问题常用的方法有三种:搜索空间限定法，可行解变换法，罚函数法等。对于本课题中的约束优化问题，我们采用罚函数法将它化为无约束优化问题。 罚函数法的基本思想是:对解空间中无对应可行解的个体，计算其适应度时，处以一个罚值，从而增加该个体的适应度值，使得在最小优化中该个体不被选为最优。具体可用下式来对个体的适应度值进行调整: f(X)　　　　　　　　(X满足约束条件),F(X), (3.2) ,f(X)，P(X)　　　　　(X不满足约束条件), 式中f(X)为原适应度函数，F(X)为考虑了罚函数之后新的适应度函数，P(X)为罚函数。 如何确定合理的罚函数是这种处理方法的难点之处，因为这时既要考虑如何度量解对约束条件的不满足程度，又要考虑算法进化的效率。罚函数的强度太小的话，部分个体仍有可能破坏约束条件，罚函数的强度太大的话，会影响优化算法的运行效率。 在本论文中，对于不可行解，即与障碍物碰撞的路径解，需要根据位置碰撞点与障碍物中心的距离的关系定义合适的惩罚值函数。在碰撞发生的情况下，由于距离障碍物中心远的路径要优于近的路径，它要加的惩罚值相对就要小一点;相应的，距离障碍物中心近的路径效果更差，它要加的惩罚值相对就要大一些。因此在对解空间中不可行解的个体，取罚函数为位置碰撞点与障碍物中心的距离倒数的函数。这样定义罚函数，不容易损失最优解，可以比较好的将约束条件下的路径寻优转化为无约束条件下的路径寻优。 13 井雅洁:多机器人系统的路径规划算法研究 4 基于粒子群优化的路径规划算法及仿真 本章重点研究粒子群算法在移动机器人路径规划中的应用。主要内容有问题描述与环境建模、生成初始化路径、采用各种改进粒子群进化算法优化路径及仿真结果分析等。其中，针对局部极小问题，研究了改进算法，如位置加权法和加变异算子法的解决效果。 4.1仿真平台简介 本课题的研究是通过编程仿真实现的，使用的仿真平台是MATLAB 7.0。MATLAB意为矩阵实验室(matrix laboratory)，是一种功能强、效率高、简单易学的科学计算语言。它以矩阵和数组为基本数据处理单元，能高效的处理大量的数据，有着强大的数值计算和数据分析功能。同时它也有强大的绘图功能，通过调用不同的绘图函数设置图形的属性，如坐标范围、图形线型、图题和绘制栅格等，用户不需要过多地考虑绘图细节，只需给出一些基本参数，就能绘制所需图形。 MATLAB命令有两种执行方式:一种是交互式的命令执行方式，另一种是M文件执行方式。仿真过程中的程序都存在M文件中，运行程序，即可执行文件中的命令。 作为一种演算式执行语言，MATLAB编程方便，使用灵活，容易掌握，已广泛应用于[]8科学及工程计算领域。本次毕业设计主要利用M文件编写程序，充分利用它强大的数据处理功能和绘图功能进行实验仿真。 4.2 问题描述与环境建模 在进行移动机器人路径规划时，首先必须用计算机语言描述机器人的工作环境，即进行规划空间建模。我们在机器人运动空间建模时作如下假设:(1)移动机器人在二维有限空间中运动，不考虑高度信息;(2)机器人的运动空间中分布着有限个已知的障碍物，障碍物的位置和形状已经确定，可用大小已知的圆形描述，半径为机器人与障碍物碰撞半径，在半径以外即无碰撞危险，且在机器人运动过程中障碍物的形状、位置、大小均不发生变化;(3)忽略障碍物的高度信息，即用(x,y)平面来描述;(4)为了保证路径不太接近障碍物，把障碍物的边界向外扩展机器人本体的长宽方向上最大尺寸的1/2加上传感器最小传感距离，机器人可看作质点，尺寸大小忽略不计。图4-1为所构建的机器人运动空间的平面模型，S为起始点，G为目标点(终止点)，3个圆为分布于机器人工作空间的障碍物。如此建立的工作空间模型是静态的，对于动态不确定环境中的移动机器人路径规划问题，可以将它看成是分阶段静态环境规划问题的叠加。即在两次通过传感器采样环境信息的时间间隔内，认为环境信息是固定不变的，根据这些信息可以按静态环境进行路径规划。 14 华东交通大学毕业设计 这时需要算法的实时性高、收敛速度快，以保证在环境信息没有大的变化时就可规划出机器人的路径，否则规划出的路径是无效的。为减小算法的复杂度，这里研究固定障碍物环境下路径规划的问题，其算法可以应用于动态不确定环境机器人的路径规划。 我们采用区域划分的环境建模思想，对机器人的工作环境依实际情况的需要作纵向 [9]L,L,？,L表示。移动机划分。为了便于计算和研究，这里作纵向n等分，n条竖线用12n器人从起始点S到目标点G的无碰路径一定与每条竖线都有一个交点，从左到右依次记P,P,？,PL为。那么路径规划即可表示在区域边界确定的范围内，在每一条竖线上找12ni PP,P,？,P一个合适的点，组成一个点的序列(S,,G)。考虑到起始点与目标点已经固i12n P,P,？,P定，则序列()可唯一确定移动机器人的一条运动路径，若用各个点的坐标表12n 示，则可用一个的矩阵描述该条路径，矩阵的第一行存储各个点的横坐标，第二行2，n 存储各个点的纵坐标。由于纵线作的是等分，各个点的横坐标有固定的等差关系，即每个 ,,X,x,x,？,x相交点横坐标是已知的，可不必表示出来。那么一个的向量即可表1，n12n xP示移动机器人的一条路径(一个个体)，其中为点的纵坐标，X也称作路径规划问题ii 的一个解。 50 40 L2 L3 L4 L5 L6 L8 L9 L1 L7 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-1 构建环境模型 x如果把作为竖直线上可上下移动的未知可变量，障碍物作为约束限制，这样可得i 一个移动机器人从起始点到终止点的无碰距离函数: n22f(X),f，la，(x,x)，f (4.1) ,1，12ii,1i PfPf式中表示与起始点S之间的距离，表示与目标点G之间的距离，n112 la,Ln，1x,表示两相邻竖线之间的距离。(4.1)中只有为未知变量，只要把它限制在SGi 障碍物图形之外，则该式就变为一个高维函数，从而把移动机器人路径规划问题转化为一个约束优化问题。不失一般性，这个约束优化问题可表示为: 15 井雅洁:多机器人系统的路径规划算法研究 fXmin(), (4.2) ,s.t.g(X)　　　i,1,2,？,mi, 可以引入罚函数将上述问题转化为无约束优化问题 f(X)　　　　　　　　(X满足不与障碍物相交的条件),F(X), (4.3) ,f(X)　，P(X)　　　　　(X不满足不与障碍物相交的条件), 这样得到的F(X) 即为机器人路径规划问题中的目标函数，也即适应度函数。对于可行解X(即X表示的路径不与障碍物相交)，F(X)就表示移动机器人从起始点S到目标点G所经过的路径的长度;对于不可行解(即X表示的路径中有位置点在障碍物内，或路径穿过障碍物)采用罚函数技术可加入罚值，算出其在无约束条件下的适应值，再评价个体最优和群体最优。在使用粒子群算法规划移动机器人路径时，评价个体最好和群体最好的目标函数即为F(X)。 4.3 路径初始化 在4.2节，通过问题描述与环境建模将移动机器人路径规划问题转换为了求目标函数最小值的问题。采用粒子群算法优化这个目标函数就可得到全局最优路径。路径初始化是路径优化的第一步，也是关键的一步。在进行路径优化之前，首先要定义一些重要的参数，具体如下: (1)粒子群的种群规模N:即粒子的个数，它也表示路径规划问题中解空间的维数，在本篇论文中，取种群规模为40; (2)粒子的维度n:粒子维度表示的是粒子不同时刻位置的时刻个数，它是描述机器人工作空间划分情况的一个参数，也是路径优化问题解的维数，其大小会影响优化算法的效果; (3)群体最优适应值G:也即要规划出的移动机器人的路径长度; (4)群体中个体位置X(N×n):存储群体中N个粒子的位置信息; (5)群体中个体速度V(N×n):存储群体中N个粒子的速度信息; (6)个体适应值矩阵fitness(1×N):存储N个粒子的适应值; (7)个体最优适应值矩阵Lbest(1×N):存储N个粒子所经历的历史最优适应值; (8)个体最优位置pbest(N×n):存储群体中N个个体的最优位置; (1×N):存储群体中最优个体的位置，即移动机器人的路径(9)群体最优位置gbest 信息; (10)进化代数t:表明粒子速度和位置信息进化的代数，一般情况下t越大，进化的效果越好，但程序运行的时间会变长。 c还有许多与粒子群速度进化和位置进化方程相关的参数，如惯性权重w、认知系数，1 c调节粒子飞向自身最好位置方向的步长，社会学习系数，调节粒子飞向全局最好位置2 方向的步长等。它们的定义与表示方式与第二章所描述的相同。 在用粒子群算法进行移动机器人路径规划时，路径的初始化包括粒子群的初始化和生成初始路径两个部分。粒子群的初始化包括: (1)设定群体规模N和表示粒子位置、速度的维度信息(在该问题中为1); ,,,,,V,V,X,X(2)设定粒子的位置范围和速度范围; maxmaxmaxmax (3)对各个粒子的位置和速度信息进行初始化。 16 华东交通大学毕业设计 机器人的路径是由群体中最优粒子在不同时刻的位置信息组成的，如图4-1 所示，每 ，，L,L,？,Lx,x,？,x个粒子在经过竖线时的位置信息可决定出一条路径。我们称n12n12n 为路径解的维度或粒子维度，表示粒子在规划空间中n个时刻取值。反复将粒子群的初始 L化进行n次(其中第i次表示对各个粒子到达竖线时刻的位置进行初始化)，给每个维i 度初始化一个位置信息，这样就可以生成N条可供移动机器人选择的路径，可用一个N，n的矩阵表示: x,x,？,x，，11121n ,,x,x,？,x21222n,, (4.4) X,　　？？？,, ,,x,x,？,xN1N2Nn，， ,,X,x,x,？,x表示第i个个体，也即是移动机器人的一个路径解，它是用其中ii1i2in 粒子在n个维度上的位置信息表示的。初始化的另外一种方式是先初始化一条移动机器人的路径，即一个粒子在路径解n个维度上的位置信息，然后循环N次，生成N条路径。路径生成之后，需要对个体进行适应性评价，选出个体最优和群体最优。由于是初始化，个体没有历史值，因此个体的适应值即为个体最优适应值，个体的位置即为个体最优位置。附录C中图1表明了路径初始化时的流程图。 值得注意的是，由于在位置初始化时采用的是随机的方法，没有考虑避障问题，生成的某些路径解可能是不可行的。为了保证带约束路径优化问题有解存在，同时也为了使粒子群算法的收敛速度较快，对于全部路径解为不可行的情况，我们认为此次初始化无效，重新进行路径的初始化。生成N条路径之后，考虑到到避碰问题，我们加入罚函数P(X)，化约束优化问题为无约束优化问题。 在后续用粒子群算法优化路径的过程中，需要将优化后的路径与初试化后的路径进行比较，以便评价进化算法的优劣。这时，因为初始化路径的随机性，若多次运行程序，多次生成的初始路径不同，无法对比优化前后的路径优劣。同时，在改进优化算法时，也无法对比算法的参数改变或不同的算法对路径优化效果的影响。因此，在进行仿真实验时，为了便于比较多次运行程序时，不同算法的不同优化效果，我们可以将N条初始路径固定下来，即在初始化时，不采用随机的方式，而是给每条路径赋特定的初始值。本论文采用对环境自下向上等分的固定初始化方式，生成的初始路径见附录C图3所示。 图4-2与图4-3分别表示采用随机方式和固定方式初始化后生成的N条路径中的最优的那一条。多次运行程序时，图4-2中的路径随机的变化，而图4-3中的路径总是固定不变，其长度为127.9590。 17 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-2 随机初始化生成的一条移动机器人路径 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-3 固定初始化生成的一条移动机器人路径 4.4 基于粒子群算法的路径规划仿真 4.4.1 基于基本粒子群算法的路径规划仿真 初始化过程完成后，就会产生N条可供移动机器人选择的路径，其中群体最优的那一 18 华东交通大学毕业设计 条，可以认为是最好的，我们认定它为移动机器人路径优化中所需要规划出的那条路径。从机器人的全局工作空间来看，该路径可能并不是非常好。这就需要对路径进行优化，经过多次迭代，使群体趋于全局最优，进而得到所需的可供机器人行走的全局最优或近似最优路径。在这一部分中，采用基本粒子群算法对移动机器人的路径进行优化。初始化生成 ，进化的N条路径可以看作是规模为N的一个粒子群群体，每条路径可以看作是一个粒子的过程中，每条粒子根据两个极值(自身所经历的最优路径和群体所经历的最优路径)动态更新其速度和位置信息，优化的结果是整个群体的性能都有所提高，且群体最优的那条路径达到全局最优。评判个体性能指标的是适应度函数，即路径的长度F(X)。具体的速度进化与位置进化方程如下式所示: (4.5) v(t，1),v(t)，cr(t)(p(t),x(t))，cr(t)(g(t),x(t))ijij11jijij22jjij (4.6) x(t，1),x(t)，v(t，1)ijijij 其中:下标“j”表示路径解的第j个维度，“i”表示粒子i，t表示第t代，c,c为加速常12数，通常在0-2之间取值，r，U(0,1),r，U(0,1)为两个相互独立的随机函数。 12 在每一步的进化中，粒子的速度和位置信息都得到了更新，对更新后的粒子在考虑约束条件的情况下进行适应度评价。通过与其历史值的比较可确定出新的个体最优位置及适应值;通过与群体的最优值比较可确定出新的群体最优位置及适应值。如此反复，经过多次迭代，即可获得好的群体最优位置，也即最优路径。粒子群算法优化路径的流程图如附录C中图2所示。图4-4和图4-5分别显示了t=100代时随机初始化和固定初始化两种情 粒子群算法优化后的移动机器人路径。 况下采用基本 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-4 基本粒子群算法优化随机初始化路径(t=100) 19 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-5 基本粒子群算法优化固定初始化路径(t=100) 它们表示的路径长度分别为121.0101和102.9410。增大进化代数，随机初始化时粒 子群算法优化的效果会变的更好，如图4-6所示，这时的路径长度为102.6659;固定初始 化时粒子群算法的优化效果没有大的变化。 50 40 30 20 10 S G 0 -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-6 基本粒子群算法优化随机初始化路径(t=200) 20 华东交通大学毕业设计 4.4.2 基于改进粒子群算法的路径规划仿真 在4.4.1中，采用基本粒子群算法对两种初始化方式生成的路径进行了优化。可以看出，对于随机初始化生成的路径，在一定的代数之内，优化的效果不是非常好，只要增大进化代数就可得到更好的路径。而对于固定初始化生成的路径，进化代数的增大对进一步优化路径的效果不大，这是因为目标函数陷入了局部极小值，生成图4-5那样的路径。这时，为了在不牺牲代数的情况下提高问题解的搜索能力，使得路径解跳出局部极小点，得 基本粒子群算法进行改进。 到更好的优化效果，可以对 在2.3中，阐述了三种改进基本粒子群算法的方法。在此，将它们应用于随机初始化和固定初始化两种方式下用粒子群算法优化移动机器人路径的过程中，以改进基本粒子群优化路径的效果。 首先考虑加惯性权重w时的情况，即将粒子的速度和位置进化公式改为(2.5)和(2.6)。 这时运行程序，进化代数取t=100，得到的移动机器人的路径如图4-7 。它表示优化随机初始化路径的情况，其路径长度为103.8448。对于固定初始化生成的路径，采用该方法优化没有明显的效果。这表明加惯性权重可以提高算法搜索最优解的能力和速度，但不能解决局部最小问题。 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-7 加惯性权重优化随机初始化路径(t=100) 其次，考虑采用位置加权到无约束解的改进粒子群的方法，即用式(2.8)代替(4.6)中的粒子位置进化方程。仿真结果表明，对于固定初始化生成的路径，该方法比之基本粒子群算法有时没有明显的优化效果;有时优化效果比较好，在t=100时会生成图4-6的路径，即该算法不能很好的解决局部最小问题。但对于随机初始化生成的路径，采用该方法可以加快寻找到全局最优路径的速度，即提高算法的收敛速度。图4-8表明，对于随机初始化方式，采用该方法在进化到t=38代即可生成的一条移动机器人的较好的路径，其长度为102.2731。 21 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-8 位置加权优化随机初始化路径(t=38) 最后，研究采用加变异算子改进粒子群算法的优化方法。对于随机初始化和固定初始 化两种方式，采用该算法优化出的路径如图4-9，图4-10所示。其中的路径长度分别为 103.6014和103.7898。 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-9 遗传变异改进粒子群优化随机初始化路径(t=51) 22 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4-10 遗传变异改进粒子群优化固定初始化路径(t=56) 由仿真图可知，加变异算子改进基本粒子群的算法可以加快目标函数收敛的速度。在t=51时，就可得到随机初始化方式下好的优化路径。同时，该方法可以有效的解决局部最小问题，使得在固定初始化方式下生成的路径较快的跳出局部最小，达到全局最优。 4.5 仿真结果分析 对于固定初始化和随机初始化两种路径生成的方式，采用各种粒子群进化算法优化路径，其结果如表2和表3所示:其中每组数据对应的仿真图见于附录C。 表2 各种算法优化固定初始化路径(Pm=0.54为变异概率) 基本粒子群算法 加惯性权重的粒子群 t 100 100 200 100 200 G 102.9639 103.0116 102.9410 102.9582 102.9392 位置加权改进粒子群 加遗传变异改进粒子群Pm=0.54 t 100 100 100 56 56 57 100 G 103.5301 102.9554 103.5550 103.7892 103.7898 103.8302 107.4662 表3 各种算法优化随机初始化路径(Pm=0.20为变异概率) 23 井雅洁:多机器人系统的路径规划算法研究 基本粒子群算法 加惯性权重的粒子群 t 100 100 200 100 100 G 121.0101 105.1901 102.6659 104.7509 103.8448 位置加权改进粒子群 加遗传变异改进粒子群Pm=0.20 t 82 38 43 80 51 100 12 G 103.9555 102.2731 102.7104 103.9903 103.6014 103.9199 103.9245 由表格中的数据可知，对于本论文所用的固定初始化方式，采用增加进化代数、加惯性权重的粒子群算法优化的效果与基本粒子群算法优化的效果相比没有明显的改进，这是由于这种初始化方式会使得路径优化问题陷入局部极小点，生成如图4-5那样的路径。位置加权法的效果比前两种方法要好，效果最好的是加遗传变异的方法，它可使路径寻优过程快速跳出局部最小值点，在短时间得到好的全局优化效果。 对于随机初始化方式，进化代数的增大和加入惯性权重都可以提高路径寻优的效果，其他几种方法可以进一步提高算法收敛的速度和寻优的能力，使得在较小的进化代数下就可优化出好的路径。 4.6程序调试中的问题及处理 在研究使用粒子群算法规划移动机器人运动路径及编程实现算法的过程中，在程序调试阶段，我们遇到了大大小小许多的问题。小的问题，如语法和变量使用不当或编程语言不规范的问题自不必说。大的问题，如算法实现及如何使用数学式表达的问题出现的也不少。本节对这类问题做了一个小结。具体说明如下: (1)判断避障的方法选择问题。 移动机器人路径规划需要寻找一条从起始点到达目标点的无碰路径。因此，对于与环境中的障碍物相交的路径，可认为它是路径规划问题的不可行解。在采用粒子群算法优化路径的过程中，需要对生成的每个解进行评价，判断它有没有可能与障碍物发生碰撞。在这篇论文中，判断机器人运行的一条路径是否与障碍物相撞，是通过比较路径中的任一点 ,,PPL,X,X与障碍物的位置关系实现的。在第i条竖线上的取值范围是，它必须iiimaxmax P,PP是自由点，即满足两个条件:1)不在任何障碍物的区域内;2)与相邻的两个点i,1i，1i P的连线不穿过障碍物。考虑到障碍物为圆形，第1)个条件可通过判断到任一障碍物中i心点的距离与障碍物半径的关系来实现;对于第2)个条件，起初我们采用的方法是判断 P,P障碍物圆心到相邻两点所连直线的距离与障碍物半径的关系，距离大于半径即表明i,1i 路径没有穿过障碍物。调试程序的过程中，我们发现有时候路径没有与障碍物相撞，程序却会执行避障处理，可见避障判断部分的方法有问题。通过反复分析和比较，我们发现， P,P在处理第2)个条件的时候存在漏洞，即在障碍物圆心到线段延长线的距离小于障i,1i 碍物半径时不会产生碰撞，而我们采用的算法会将这类情况当成是产生碰撞来处理。为此， 24 华东交通大学毕业设计 PP对于第2)个条件，需要重新设置算法来实现。具体方案是，通过比较线段的纵坐i,1i PP标与障碍物方程的纵坐标范围的关系来判断线段有无穿过障碍物。这样考虑避障问i,1i 题，在路径点不满足条件时进行避障处理，即可化约束优化为非约束优化，得到不与障碍物相交的全局最优路径。 的问题 (2)约束优化处理 在避障判断环节，若判断出有路径与障碍相交，即认为该路径不满足约束条件。这时为了保证约束的完整性，就要对该条路径的评价函数进行处理，化约束优化问题为无约束优化问题，进而求解表示路径的可行的最优解。在开始编程的过程中，对于不满足约束条件的解，我们都对它们进行重新初始化，直到保证它们都在约束范围内，即其表示的路径不与障碍物相撞。这样处理存在的问题是算法效率低，处理约束优化问题所用的时间太长。为此，我们对这里的处理方法进行了改进。采用加罚函数的方法，通过加大不可行解的适应值，同时保证可行解的存在，化约束优化问题为无约束优化问题。 (3)路径初始化方式的问题 在生成移动机器人的初始路径的过程中，开始时我们采用的是随机初始化的方式，即随机生成N条路径。这种情况下，由于每次运行程序都是随机产生初始位置值，不便于比较修改进化参数或改进粒子群算法后各种方法的优化效果，也不能分析各个参数对优化算法的影响。为了比较清晰的分析各种参数和改进算法对优化的影响，我们在仿真中首先研究了固定初始化方式下各种优化算法的效果，再将这些算法应用于更为常见的随机初始化方式。本论文采用对环境自下向上等分的固定初始化方式，生成的初始路径见附录C图3所示。这种方法初始化的路径存在局部极小问题，优化过程比较困难。 处理完这类问题，所编的程序就没了思维漏洞，同时算法也比较优，可快速解决要处理问题。程序运行效率比较高。 5 结论与展望 5.1 结论总结 随着计算机技术、信息技术、控制理论、人工智能和传感器技术等学科的发展和成熟，以此交叉而形成的机器人学的研究也经历着日新月异的发展变化。机器人的学习研究是机器人学研究中的一个非常活跃的分支，它借助对自然界中群体生物的社会行为和个体行为的研究抽象出学习的各种模式，并将它应用于机器人的运动规划中。智能算法中的粒子群算是一种典型的研究群体行为及学习模式的算法，该算法可用来优化群体行为，使得群体的某项指标达到预期的效果。 本篇论文将这种优化算法应用于移动机器人路径规划领域，进行基于粒子群算法的移动机器人路径规划的仿真研究，分析了粒子群算法中各个参数的物理意义及对优化效果的影响，比较了各种改进粒子群算法在路径规划中的不同效果。另外针对局部极小值问题，提出了位置加权改进粒子群的方法和加变异算子改进粒子群的方法。仿真结果表明，作为一种算法简单、编程易实现的智能优化算法，粒子群算法能够快速优化出移动机器人的运动路径，各种改进方法可以加快算法收敛速度，提高算法的寻优能力，并且较好得解决局部极小问题。 本论文的创新之处在于:针对路径优化过程中出现的局部极小值问题，提出了采用位置加权改进粒子群和加变异算子改进粒子群两种解决方案。在进行算法研究中，我们采用 25 井雅洁:多机器人系统的路径规划算法研究 固定初始化的方式生成初始路径。这种方式简单，方便，程序运行效率高，但会引入局部极小问题，即路径陷入局部最优，这时，增大进化代数和修改参数都不能跳出局部最小值点。采用位置加权法，给粒子群位置进化方程中加入趋向全局无约束最优解的附加项(2.8)或加入遗传算法中变异的思想，将粒子某些维度的位置信息变异到无约束最优解处都可以不同程度上解决局部极小问题，加快路径寻优的速度，使寻优过程有效地跳出局部最优点。 5.2 以后可做的工作和展望 移动机器人的路径规划其实是一个很灵活，很智能化的研究方向。表面看它是一个简单易描述的问题，规划过程中思路清晰，方法明了。实际上，随着机器人工作空间复杂度的增加和机器人工作任务的增加，这个问题会变的很复杂。 本篇论文重点研究了粒子群算法在移动机器人路径规划中的应用，将环境中的障碍物简化为简单易描述的规则图形。对于障碍物形状不规则和分布密集的动态不确定环境下移动机器人如何实时采集环境信息，进行有效的路径规划，在以后的工作中都可以进行进一步的研究。此外，机器人工作空间中障碍物分布的疏密不同对路径优化效果也有影响，如何在这种情况下构建合适的规划空间模型以便更好的发挥出优化算法的优越性是一个值得研究的问题。构建环境模型时可根据工作空间不同区域障碍物分布的疏密不同自适应地调整划分维度，障碍物分布密集的地方可进行细密划分;稀疏的地方可进行粗略划分，这样优化效果会更好。 在实际的工业应用领域，单个机器人很难胜任代替人类进行高强度复杂劳动的任务，尤其是在复杂的装配车间，只有在多个机器人相互协作分工的方式下才能完成某道工序。这就要求对多机器人系统的运动情况进行控制，需要规划出多条路径，这中间包括多个机器人之间的协调和整体的路径寻优。在多机器人系统路径规划的过程中，可以把别的机器人看作分布在某个机器人工作空间中的活动障碍物，对每个机器人进行动态环境下的路径规划，按整体指标选出各个机器人的最好路径。目前多机器人系统路径规划的研究是一个热点，如何将群体智能算法应用于该领域是一个很好的发展方向。 移动机器人的路径规划是机器人导航和控制中非常重要的一个环节。对于路径规划算法的研究经历了从传统常规算法到新型智能算法的发展过程。随着信息技术、通信技术、传感器技术和人工智能等相关学科的发展，优化算法走向了灵活、智能、高效的发展方向。可以预见，在不久的将来，在优秀算法的协助下，机器人可以灵活应用于各种领域。 26 华东交通大学毕业设计 谢辞 经过为期3个月的努力，本次毕业设计终于定稿完工。回头想想做这篇论文的整个过程，里面除了自己的辛苦劳动之外，老师及组内其他成员也给了我很大的帮助。在此，我要诚心表达自己对他们的感激之情。 首先，我要特别感谢我的指导老师陈世明副教授。在做毕业设计的初期，他给我们提供了很多与课题相关的资料，并引导我们用较短的时间确定出自己所做毕业设计的小方向，将我们从一片盲目，不知从何处着手的状态中解脱出来。在此后的过程中，他一直热心关注我们的工作进展情况，在适当时候给我们一些建议和提点，帮助我们攻克了许多问题。在遇到问题时，陈老师总会鼓励我们跳出的自己思维限制，发散的思考问题，做出自己有创新点的东西，这种思维方式是我这次体验最多也受益最多的。 其次，我要感谢我的同组同学毛金堂，裴惠琴，薛丽萍，何声鑫等，尤其是毛金堂。作为一个团队，他所做的工作是我们毕业设计中必不可少的环节，没有他的协作我不可能胜任这个课题论文。其他成员自始至终的陪伴和中肯的建议对我也很有帮助。 最后，我要感谢学校和老师为我们提供学习环境和做毕业设计的设备，尤其感谢研究生江卷同学，他提供自己用的电脑让我们调程序，写论文，给我们的工作带来了很大的方便。 27 井雅洁:多机器人系统的路径规划算法研究 参考文献 【1】谭民，王硕，曹志强.多机器人系统[M]. 清华大学出版社. 【2】李江抒.多移动机器人路径规划算法与导航系统研究[D].吉林大学硕士学位论文，2004.5 【3】曾建潮，介婧，崔志华.粒子群算法[M].科学出版社. 【4】shi Y, Eberhart R C. Empirical Study of Particle Swarm Optimization. In: Processings of the 1999CongessonEvolutionaryComputation. Piscataway, NJ, IEEE Service Centerm,1999,1945-1950. 【5】秦元庆,孙得宝,李宁等.基于粒子群算法的移动机器人路径规划[J].机器人，2004，26(3). 【6】王凡.基于Agent的多机器人路径规划研究[D].武汉理工大学硕士学位论文，2006.4 【7】张颖，吴成东，原宝龙. 机器人路径规划方法综述.控制工程，2003，10. 【8】刘卫国.MATLAB程序设计与应用.高等教育出版社. 【9】黄祎，孙德宝，秦元庆.基于粒子群算法的移动机器人路径规划[J].测控技术,2006,25(4). 10】张宏烈.移动机器人全局规划的研究[D].哈尔滨工程大学硕士学位论文.2002(1):2 【 【11】孙波,陈卫东，席裕庚.基于粒子群算法的移动机器人全局路径规划[J].控制与决策,2005,20(9). 【12】刘钊，陈建勋.基于粒子群算法的足球机器人动作选择研究[J].武汉科技大学学报(自然科学版)， 2006，29(1). 【13】雷开友，邱玉辉，刘博勤等.基于改进粒子群算法的移动机器人全局路径规划[J].西南师范大学 学报(自然科学版),2006，31(2). 【14】侯志荣，吕振肃.基于MATLAB的粒子群优化算法及其应用.计算机仿真[J],2003,20(10). 【15】Dong H.Kim. Seiichi Shin .Self-Organization of Decentralized Swarm Agents Based on Modified Particle Swarm Algorithm. J Intel Robot Syst. DOI 10.1007/s10846-006-9047-3 【16】Zhiyun Lin(Local control stragies for goups of mobile autonomous agents.IEEE Transaction on Automatic Control.2004,49(4):622-629 17】Dong H.Kim and Seiichi shin,Self-organization of decentralized swarm agents based on 【 modified particle swarm algorithm, Journal of Intelligent Robot System. 28 华东交通大学毕业设计 附录A 外文翻译-原文部分 Self-organization of Decentralized Swarm Agents Based on Modified Particle Swarm Algorithm Abstract In this paper, an attempt has been made by incorporating some special features in the conventional particle swarm optimization (PSO) technique for decentralized swarm agents .The modified particle swarm algorithm (MPSA)for the self-organization of decentralized swarm agents is proposed and studied .In the MPSA , the update rule of the best agent in swarm is based on a proportional control concept and the objective value of each agent is evaluated on-line .In this scheme ,each agent self-organizes to flock to the best agent in swarm and migrate to a moving target while avoiding collision between the agent and the nearest obstacle/agent. To analyze the dynamics of the MPSA, stability analysis is carried out on the basis of the eigenvalue analysis for the time-varying discrete system. Moreover, a guideline about how to tune the MPSA’s parameters is proposed. The simulation results have shown that the proposed scheme effectively constructs a self-organized swarm system in the capability of flocking and migration. Keywords decentralized swarm systems; particle swarm optimization; self-organization. 29 井雅洁:多机器人系统的路径规划算法研究 1. Introduction A swarm is a distributed system with a large number of autonomous agents or robots .in[3],many simple agents occupied one or two dimensional environments and were able -organization .Self-organization in a swarm to perform tasks such as pattern generation and self is the ability to distribute itself optimally for a given task, e.g., via geometric pattern formation or structural organization. Mechanism for self-organization in swarm are studied in [13-15].It is generally believed that proper organization of swarms of cooperating mobile agents provides significant benefits over single unit approaches for various missions. For specific tasks, cooperating agents do not need to be sophisticated or expensive to compete with their advanced in dependent counterparts. In addition, the integrated, multi-agent systems facilitate increased mobility, survivability, sensor coverage and information flows. It has been proposed that a sequence of basic behaviors(random wandering, obstacle avoidance and light following) based on a nonlinear oscillator scheme are coordinated in the robot to produce the higher behavior of foraging for light. However, these behavior-based computational organizations lack insightful comprehension to the problems and sometimes exhibit unpredicted and undesirable performances. They need much time to be trained for selection of proper parameter values in different working environments. These schemes should be combined in a certain trade-off and might be employed in different levels for different scenarios for the future hierarchically architectural and multi-strategy adaptive intelligent system consisting of a swarm of inhomogeneous mobile agents. On the other hand, much attention in recent years has been focused on behavior-based reactive systems. The behavior-based intelligences are motivated by natural species and can show great adaptability and robustness to time-varying environment with relatively simple algorithm, as well as corresponding low computation cost during real-time operations. Taking an example of the prey-pursuit of ants, a conceptional figure of decentralized swarm agents with behavior-based intelligences is shown in Figure 1 where ants find the most efficient routes to a food source. In Figure1,the ants following the shorter path reinforce the odor cue ‘pheromones ’on the shorter path and communicate even shorter paths to groups or individuals in the ant colony, as the pheromones dissipate. Very few attempts have been made by applying particle swarm optimization (PSO),one of the evolutionary computation(EC) techniques , for self-organization of swarm agents, e.g., the prey-pursuit of ants. PSO has been compared to genetic algorithm for efficiently finding optimal or near-optimal solutions in large search space. The most striking difference between PSO and the other evolutionary algorithms is that PSO chooses the path of cooperation over competition. The other algorithms commonly use some form of decimation, survival of the fittest. In contrast, the PSO population is stable and individuals are not destroyed or created. 30 华东交通大学毕业设计 Individuals are influenced by the best performance of their neighbors. Individuals eventually converge on optimal points in the problem domain. PSO has been developed through simulation of simplified social models such as bird flocking and fish schooling. Also, it is based on a simple concept. Therefore, the computation time is short and it requires little memory, which makes dealing with on-line computation possible. PSO is originally developed for nonlinear ECoptimization problems on off-line as other .In[21],an attempt has been made for a control s application-tuning PID controller for optimal settling time of the plant transfer function .However ,the method is off-line gain tuning. There was a first look at adapting PSO to dynamic environment which is a sort of proof of concept experiments. However, these experiments have many obvious weakness such as simplification in the mechanism to trigger for reset in order to avoid making direction on the basis of outdated information. In addition, what seems to be lacking is a consideration of stability analysis and collision problem between agents. Inspired by such studies, our focus is to apply a conventional PSO concept for the dynamic environment such as self-organization of swarm agents and develop a stable algorithm guaranteeing stable conditions on its dynamics . In this paper, we present a framework for decentralized control of self-organizing swarm agents based on the MPSA. The goal is not to tackle all possible formation and collision problems in self-organizing configurations , instead we shall restrict our attention to the application of a conventional PSO concept for distributed swarm agents and the proposition of stable self-organizing scheme. In this scheme, each agent self-organizes to flock to the best agent in swarm and migrate to a moving target while avoiding the obstacles that may appear on the path of formation. While others have previously studied a target-following strategy, the purpose of this study is specifically to obtain global behaviors such as flocking among agents, group migration by using simple local individual rules MPSA, and collision avoidance. Also, in contrast to previous researches on particle swarm optimization [7,22]and[4],our study explicitly addresses issues of the stability analysis on the dynamics of the MPSA and proposes a guideline about how to tune the MPSA’s parameters. This paper is organized as follows. Section 2 discusses the environment and swarm agent model and overviews conventional particle swarm optimization. In Section 3, the self-organizing scheme by the MPSA and its stability analysis are proposed and studied. In Section 4, simulation examples for the comparison of the proposed method and a conventional PSO concept and a prey-pursuit missionary example are illustrated. Finally conclusion is drawn 31 井雅洁:多机器人系统的路径规划算法研究 in Section5. 2. Swarm Model Description and Problem Statement 2.1. Environment and Agent Model Formation and maintenance of coherent group movement has long been studied in natural systems, and more recently efforts have been made to reproduce this type of behavior in artificial systems. The first such work appeared in the context of computer animation, and since then this behavior has been extensively studied in simulation. It has successfully synthesized birds’ behaviors such as collision avoidance, velocity matching and flock centering .To avoid collision with other birds and obstacles, a bird uses a steer-to-avoid rule. However, theoretical treatments or analysis of flocking behavior was not presented. Because boid model is used a computer model of coordinated animal motion such as bird flocks and fish schools for simulating visually satisfying flocking and schooling behaviors for animation industry. It was based on three dimensional computational geometry of the sort normally used in computer animation or computer aided design. Hence, the generic simulated flocking creatures are called boids. Other experiments by the same author have been conducted by evolving groups of artificial creatures. Reynolds evolved the control system of a group of creatures placed in an environment with static obstacles and a manually programmed predator for the ability to avoid obstacles and predation. Despite the results described in the paper are rather preliminary, some evidences indicate that coordinated motion strategies begun to emerge. The agent model is based on the premise that in the near future technology will allow the production and deployment of large-scale masses of robots. The robots will be small . They will likely possess only basic capabilities and mission specific sensors. Direct communication between agents may or may not exist. The environment model is very’ object-oriented’ in it’s approach to agent construction. Sensors and behaviors are encapsulated when possible. This approach allows individual components to be added and removed from the model as if the corresponding physical components were being added to or removed from a real agent. A swarm system may consist of from two robots to hundreds or more autonomous robots. The costs of robots are going down, and the robots are getting more compact, more capable, and flexible. Hence in the near future, many industrial and military applications of swarm systems in tasks such as hazardous inspection, patrolling, guarding and attacking are expected. In this paper, the model of swarm agent is constructed by building upon an autonomous agent object. In abstract programming terms it may also be thought of as an object with general capabilities. The basic agent possesses only locomotion as an innate capability. Neighbor position information may be used for group behaviors such as flocking and migration. 2.2. Overview of Particle Swarm Optimization PSO is motivated from the simulation of social behavior. PSO was originally designed and developed by Eberhart and Kennedy [11] and [6].By adding a new inertia weight into PSO, a new version of PSO is introduced in [22]. The original PSO formulae define each particle as a potential solution to a problem in D-dimensional space. The i-th individual, which is called particle, of the population, which is called swarm, can be presented by a D-dimensional vector , T. x,[x,x,？,x]12iiiiD In this work, PSO is developed in two dimensional space for group behavior such as a colony of Tx,[x,x]insects. Each particle becomes an agent and is the current position of agent i. 12iii 32 华东交通大学毕业设计 x,yThe position of each agent is represented by axis position and the velocity is modified by PSO. Modification of the agent position is realized by the position and velocity information. An optimization technique based on the above concept can be described as follows: Namely, a colony of insects optimizes a certain objective function. Each agent knows its best value so far and its position. Moreover, each agent knows the best value so far in the group among their own best values. Each agent tries to modify its position using the above information. The objective function is the distance of the best agent from a target as follows: 2 (1) minF(k),|x(k),x(k)|idi TWhere is a target position for migration. x,,,x,x12ddd min,j,F(j)The best previous position (i.e. the position corresponding to of the i-th 1kiTp,[p,p].The best agent in swarm (i.e. the agent agent is recorded and represented as 12iii min,j,F(k)with where N is the number of agents)is represented as 1kiTdenoted by index g. p,[p,p]12gggTv,[v,v].This modification can be The position change (i.e. velocity) of the i-th agent is 12iii represented by the concept of velocity. Velocity of each agent can be modified by the following equation. (2) v(k，1),cv(k)，crand()(p(k),x(k))，crand()(p(k),x(k))i1i2ii3gi cc0,c,1cwhere is the inertia weight such that .and are two positive constants, called 3112 the cognitive and social parameter, respectively. rand():Uniformly distributed random number between 0and1. ppUsing (2), a certain velocity that gets close to and can be calculated. The current gi position is updated by the following equation. x(k，1),x(k)，v(k，1) (3) iii Equation (3) provides the new position of the i-th agent, adding its new velocity to its current position. A PSO run is considered to be successful if any particle in the swarm ‘lands’ within a specified radius of a goal solution [22]. This radius is dependent on the precision of the solution desired. However, for the dynamic environment where the goal value (or position) changes during the execution of a PSO run, the original PSO algorithm has no method for detecting this change, and the particles are still influenced by their memories of the original goal position. Moreover, for swarm agents (can be ‘a small robot’ as a physical subject) in the dynamic environment, collision avoidance problem between the agent and the nearest obstacle/agent in swarm may be considered. 3. Modified Particle Swarm Algorithm In this section, a self-organized swarm scheme controlled by the modified particle swarm algorithm is presented for the dynamic environment. Obstacle avoidance problem is considered on the basis that a penalty value is added to an objective function. To analyze the dynamics of the MPSA, stability analysis is carried out on the basis of the eigenvalue analysis for time-varying discrete systems .The virtual zone is developed to avoid collisions among agents. 3.1.Modification of PSO 33 井雅洁:多机器人系统的路径规划算法研究 Modification can be represented by the concept of velocity. Velocity of agent can be modified by the following equation. v(k，1),cv(k)，crand()(p(k),x(k))，,(k) (4) i1i2iii where, d,,(k),crand()(x(k),x(k)),ifx(k),p(k)i4diig,,(k), (5) ,ig,()()(()()),k,crandpk,xkotherwise,i3gi, where c is the beacon parameter. 4d,(k)x,x in is a sort of proportional control concept. It accelerates the best swarm agent idi fast toward better solution which makes tracking of the moving target possible. Hence, the new best swarm agent allows the other swarm agents to move fast in a new direction. A higher d,(k)random value for or the case with out a random value reflects faster tracking to the i moving target in open space without obstacles. On the contrary, a lower random value for each sample reflects a higher swarming behavior in order to keep formation, which makes faster tracking to the moving target by more changes of the best agent in the existence of obstacles. pxpThese knowledge components, ,and are blended with each agent’s current velocity gdi vector to determine the next position of the agent. The best swarm agent become a beacon for g,(k)migration using in (5) that helps the other agents flock to best swarm agent, which is a i ,(k)coordinated biological behavior such as bird flocks and fish schools. Thus, enables i swarm agents to possess the behavior that an ant following the shortest path dissipates pheromones and the other ants follow the best ant as shown in Figure1. VVAccording to circumstance, the velocity can be limited to the range to by following maxmin equation. This is one strategy for keeping the algorithm from becoming unstable. V,v,V (6) minimax VvVwhere andare the minimum and maximum values of velocity ,respectively. maximin 34 华东交通大学毕业设计 附录B 外文翻译-译文部分 基于改进粒子群算法的分散群集个体的自组织 摘 要 这篇论文通过尝试在常规粒子群优化技术中并入一些特殊特性来研究分散群集个体。提出和研究了针对分散群集个体自组织的改进粒子群算法。在改进粒子群算法(MPSA)中，群体中最优个体的更新规则是基于一种比例控制的概念的，并且每个个体的目标值是在线估计的。在这一方案中，各个个体自组织群集到群体中的最优个体，移向移动目标，同时避免与最近障碍物或个体发生碰撞。为了分析MPSA中的动力学特性，针对时变离散系统进行了以特征值分析为基础的稳定性分析。另外，还提出了一个如何改变MPSA参数的方案。仿真结果表明所提方案有效地创建了一个能够聚集、移动的自组织群集系统。 关键词:分散群集系统;粒子群优化;自组织 1. 介绍 群体是一个拥有大量自主个体或机器人的分布式系统[9，10]。在[3]中，许多简单的个体占有一维或二维空间环境并且能够从事譬如仿生下代，自组织这样的任务。一个群体的自组织是指它能够根据给定任务，如通过几何图案编队或结构组织以最适宜的方式分布自身。在[13-15]中，研究了群体中自组织的机制。人们普遍认为，协作式可移动个体的合适群体组织比趋向多个任务的个体单元拥有更大的优势。对于具体任务，协作式个体不必要精密或昂贵到与它们先进的、独立个体产品进行竞争。此外，集成式多个体系统促进了可移动性、可存活性、传感器覆盖范围和信息流通能力的提高。有人提出基于非线性振荡器方案的一系列基本行为(随机波动、避障、光线跟踪)可与机器人协同动作以产生更高级的搜索光线[5]的行为。然而，这些基于行为的计算组织缺乏对问题的深刻理解，有时会出现预料不到和不期望的行为。它们需要很长时间的训练来选择不同工作环境[5]下合适的参数值。这些参数应通过一定权衡结合起来，并且为不同领域如未来居于统治地位的建筑学和由不同类移动个体组成群体的多策略自适应智能系统不同层次上所采用。 另一方面，近几年很多人关注基于行为的反作用系统[16，17]。基于行为的智能是受自然物种激发的，它能够对有相对简单算法，实时操作[1]时计算量相对较小的时变环境显示出巨大的适应性和鲁棒性。以寻找食物的蚂蚁为例，图表1显示了一个基于行为智能的分散群集个体的概念图形，在那儿，蚂蚁寻找到达食物源的最有效的路径。在图表1中，随着气味的发散追踪更短路径的蚂蚁加强了更短路径上有气味暗示的“外激素”，与蚁群群体和其他个体讨论得出更短的路径。 很少有人尝试应用粒子群优化技术，一种进化计算法[11]，进行群集个体的自组织，例如蚂蚁觅食。粒子群优化技术(POS)已被比做在大的搜索空间[6，12]有效寻找最优和近最优解的遗传算法。POS与其他进化算法的最大不同之处在于POS选择合作而非竞争的方法。其它算法普遍采用某些大批淘汰，最适者生存的形式。相反的，POS群体是稳定的，个体也不被毁灭或创造，它受其周围同伴优秀行为的影响，在问题解决的范围内，最终汇聚到最适宜点。POS已经通过模仿简化的社会模型例如鸟和鱼的群集得到了发展。此外，它以一个简单概念为基础，因此，计算时间短，不需要记忆，这使得它处理在线计算成为 EC可能。PSO算法起初被发展是用来像其他一样，解决离线状态非线性最优化问题。在s [21]中，试图进行一种控制应用——为被控对象传递函数的最优设置时间改变PID控制 35 井雅洁:多机器人系统的路径规划算法研究 器。然而，这一方法是离线改变增益的。有人初步尝试使POS适应于动态环境，这也是概念环境[4]的一种证明。然而，这些实验有许多明显的不足之处:例如，为了避免因过时的信息为基础要改变方向简化了激发复位的机制，此外似乎缺少考虑稳定性分析和个体之间的碰撞问题。受这些研究的启发，我们致力于将常规POS概念应用于动态环境，例如群集个体的自组织，并且发展了一种确保群体动力学系统处于稳定状态的稳定规则。 在论文中，我们针对基于MPSA的自组织群集个体的分散控制提出了一种框架。目的不是解决在自组织形态中所有可能的队形和碰撞问题，相反的我们要限制把注意力放在将常规POS概念应用于分布式群集个体和稳定自组织方案的命题。在这一方案中，各个个体自组织群集到群体中的最优个体，移向移动目标，同时避开可能出现在队形路线上的障碍物。由于先前有人研究出一个目标跟随策略[18，23]，这一研究的目的是具体地获取全局行为，例如个体之间的群集，使用简单局部个体规则MPSA进行群体迁移以及避障。同时，与先前对粒子群优化[7，22]和[4]的研究相反，我们的研究明确强调了MPSA动力学稳定性分析的问题并且提出一个如何更改MPSA的参数的方案。 这一论文是按如下编排的:第2部分讨论环境模型和群集个体模型并且纵览常规粒子群最优化。第3部分，提出并研究MPSA的自组织方案及其稳定性分析。第4部分，通过仿真实例比较所提方法与一种常规PSO概念并阐述一个以觅食为任务的例子。 2. 群集模型描述和问题陈述 2.1 环境和个体模型 群居组织移动的队形和维持在自然系统中已经研究很久了，近来，人们则更努力地在人工系统中再创这种类型的行为。首次这样的工作出现在计算机动画制作领域，自此，这一行为在仿真[20]中被大量研究。它成功的综合了鸟的行为，例如避撞，速度匹配和群体集中。为了避免与其它鸟或障碍物的相撞，鸟使用导航避障的规则。然而，群集行为的理论论述或分析还没有提出。因为群体中的个体模型利用一种协同动物运动，如鸟群集和鱼群集的计算机模型来进行视觉上满足动画制作产业群集行为的仿真。它以那种通常使用在计算机动画制作和计算机辅助设计上的三维计算几何为基础。因此，一般模仿群集生物叫做boids。同一作者[20]做的其他实验是通过引入多组人工生物来进行的。Reynolds[19]引进了一个有一组生物的控制系统模型，这些生物被放在一个有静态障碍物和有能力避开障碍物和侵略者的手持编程掠夺者的环境中。尽管论文中的描述的结果是很初级的，一些证据仍表明协调运动策略开始出现了。 个体模型以假设在不久的将来技术将允许大规模众多机器人的生产和发展为基础。机器人将会变得小型化，并且可能只拥有基本功能和以特定传感器为目标。个体之间的直接交流可能存在也可能不存在。环境模型在趋近个体建设方面是非常面向对象的。可能的话传感器和行为会封装起来。这种方法允许从模型上增加或去除个体元素，就像从真实个体上增加或去除相应的物理元素一样。 一个群集系统可能由两到数百或更多个独立机器人组成。机器人的成本价格在下降，自身也变得更小巧，能干，适应性强。因此，在不久的将来，有望看到群集系统在许多工业，军事领域中的应用，它可用于危险检查，巡防，保卫和袭击等任务中。在这篇论文中，群集个体模型是通过建立在一个自主个体目标上而建立起来的。在抽象编程语言中，它也可被认为是一个有一般能力的物体。基础个体仅拥有移动这一先天能力，周围的位置信息可用作群体行为如群集和迁移。 2.2 纵览粒子群最优化算法 POS是从模仿社会行为中启发出来的，它起初是由Eberhart和kennedy[11]和[6]设计、发展的。通过在POS算法中加入一个新的惯性因子，可产生一种新的 POS算法[22]。 36 华东交通大学毕业设计 起初的POS方案定义每个粒子为D维空间中一个问题的一个潜在的解。第i个个体，也叫 T群体粒子，可以用一个D维向量，表示。 x,[x,x,？,x]12iiiiD 在这一工作中，POS在二维空间得到发展以便研究群体行为例如昆虫群体行为。每个 Tx,[x,x]x,y粒子变成个体，是第i个个体的当前位置。每个个体的位置用轴位置12iii 表示，速度通过POS算法改进。通过位置和速度信息可以改变个体位置。一种基于上述概念的最优化技术可描述如下:名义上，一个昆虫群体最优化一种目标函数。每个个体知道它的最优值和当前位置，此外，知道在它们自身最优值之间的群体最优值。个体根据上述信息试图改进自身位置。 目标函数是指如下最优个体与一个目标之间的距离 2 (1) minF(k),|x(k),x(k)|idi T 是要移向的目标的位置，第i个个体的最佳先前位置被记录下来用,,x,x,x12dddTTp,[p,p]表示。群体中的最佳个体的位置用表示用g 标记。 p,[p,p]12iii12gggT第i个个体的位置变化是，这一改进可用速度这一概念表示。每个个体,,v,v,v12iii 的速度可通过下述等式改进。 (2) v(k，1),cv(k)，crand()(p(k),x(k))，crand()(p(k),x(k))i1i2ii3gi cc0,c,1c表示的惯性因子, 、为两个正常数，分别叫做认知参数和社会参数。rand():3112 0、1之间的正态分布的随机数字。 p使用(2)式，可计算出接近和Pg的某一速度，当前位置被下列方程更新。 i xx(k+1)= (k)+ v(k+1) (3) iii 方程(3)提供了第i个个体的新位置，它是把其更新的速度值加到它的当前位置上得到的。 如果群体中的任何个体落在全局解[22]的特定半径之内，运行PSO算法就认为是成功的。这一半径取决于所期望解的精确度。然而，对于目标值(或位置)在POS算法运行中改变的动态环境，基本POS算法没有办法检测到这一变化，个体仍受它们所记忆的最初目标位置的影响。另外，对于动态环境中的群集个体(可以是作为物理主体的小机器人)，群体中个体与最近障碍物/个体之间的避撞问题可能需要考虑。 (改进粒子群算法 1 在这一部分，针对动态环境提出了一种受改进离子群算法控制的自组织群集方案。以给目标函数加补偿值为基础考虑避障问题。为了研究MPSA的动力学特性，以时变离散系统的特征值分析为基础进行稳定性分析。提出虚拟区域以避免个体之间的碰撞。 3.1 PSO算法的改进 改进可用速度这一概念表示。个体速度可用下列方程改进 v(k，1),cv(k)，crand()(p(k),x(k))，,(k) (4) i1i2iii d,,(k),crand()(x(k),x(k)),如果x(k),p(k)i4diig,,(k), (5) ,ig,kcrandpkxk(),()((),()),其他,i3gi, d,(k)x,xc为警告参数。中的是一种比例控制概念。它加快最优群体个体快速趋向更idi4 好解，使得追踪移动目标成为可能。因此，新的最优群体个体允许其他个体快速在新的方d,(k)向移动。取一个更高随机值或不取随机值时群体个体在开放无障碍环境下会更快跟i 踪移动目标。相反的，更低的随机值就会有更高的群体行为以便维持队形，使得在有障碍 37 井雅洁:多机器人系统的路径规划算法研究 pxp物存在时通过更多次更改最优个体来实现更快追踪移动目标。三个知识单元,,与gdig,(k)每个个体的当前速度向量相关，决定着个体下一时刻的位置。通过使用(5)中的，最i优个体成为一个移动警告，帮助其他个体群集到其身边。这是一种协调的生物行为，就像 ,(k)鸟和鱼的群集一样。因此，使得群集个体拥有图1所示的一个蚂蚁追踪发散源最短i 路径，其它蚂蚁跟随最优蚂蚁的行为。 V 根据环境，速度可被如下方程限定在V到之间。这是保持算法稳定的一个策略。 maxmin V,v,V (6) minimax V和V是速度对应的最大值和最小值。 maxmin 38 华东交通大学毕业设计 附录C 流程图及仿真图形 ,X,,V 初始化N,nmaxmax i=1 控制粒子个数 j=1 控制时间维度 初始化j时刻位置 x,和速度vjj j=n? N Y X计算距离函数f () i 避障判断 避障处理 Y N X计算i个个体适应值F() i 存个体最优适应值及位置 XF()?G 为群体最优, i N Y 存群体最优适应值和位置 i=N? N Y 39 井雅洁:多机器人系统的路径规划算法研究 图1 路径初始化流程图 t=1 (迭代次数) i=1 (控制粒子个数) 个体速度及位置更新 f(X) 计算距离函数i Y 避障判断 避障处理 N F(X)第i个个体目标函数 i N F(X),Lbest(i) 为个体最优, i Y 存个体最优位置及适应值 N F(X),G 为群体最优, i Y 存群体最优位置及适应 值 i=N ? N T=100? Y 40 华东交通大学毕业设计 图2 粒子群算法优化流程图 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图3 固定初始化生成的N条初始路径 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图4 基本粒子群算法进化固定初始化路径 t=100 G= 102.9639 41 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图5 基本粒子群算法进化固定初始化路径t=100 G= 103.0116 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图6基本粒子群进化固定初始化 t=200 G= 102.9410 42 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图7 位置加权改进粒子群优化固定初始化路径 t=100 G=103.5301 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图8 位置加权改进粒子群优化固定初始化路径t=100 G= 102.9554 43 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图9 位置加权改进粒子群优化固定初始化路径 t=100 G=103.5550 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图10位置加权改进粒子群优化固定初始化路径 t=200 G=103.2554 44 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图11 加遗传变异改进粒子群优化固定初始化路径 t=56 G=103.7898 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图12 加遗传变异改进粒子群优化固定初始化路径t=56 G=103.7898 45 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图13 加遗传变异改进粒子群优化固定初始化路径t=57 G= 103.8302 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图14 加遗传变异改进粒子群优化固定初始化路径t=100 G= 107.6462 46 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图15 基本粒子群算法优化随机初始化路径 t = 100 G =121.0101 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图16 基本粒子群算法优化随机初始化路径t=100 G=105.1901 47 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图17 加惯性权重粒子群算法优化随机初始化路径t=100 G=104.7509 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图18 加惯性权重粒子群算法优化随机初始化路径t=100 G=103.8448 48 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图19 位置加权改进粒子群优化随机初始化路径t=82 G=103.9555 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图20 位置加权改进粒子群优化随机初始化路径t=38 G= 102.2731 49 井雅洁:多机器人系统的路径规划算法研究 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图21 位置加权改进粒子群优化随机初始化路径t=100 G= 103.0318 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图22遗传变异改进粒子群优化随机初始化路径t=80 G = 103.9903 50 华东交通大学毕业设计 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图23遗传变异改进粒子群优化随机初始化路径t=100 G=103.3728 50 40 30 20 10 0 S G -10 -20 -30 -40 -50 0 10 20 30 40 50 60 70 80 90 100 图24 遗传变异改进粒子群优化随机初始化路径 t=12 G= 103.9199 51 井雅洁:多机器人系统的路径规划算法研究 附录D 主要源程序 %基本粒子群算法优化随机初始路径.m clear clc t=0:pi/50:2*pi; %环境建模 x1=15*cos(t)+20; y1=15*sin(t)+10; x2=10*cos(t)+50; y2=10*sin(t)-10; x3=5*cos(t)+75; y3=5*sin(t); plot(x1,y1,x2,y2,x3,y3) hold on fill(x1,y1,'b') hold on fill(x2,y2,'b') hold on fill(x3,y3,'b') hold on x1=1*cos(t); y1=1*sin(t); x2=1*cos(t)+100; y2=1*sin(t); plot(x1,y1,x2,y2) hold on fill(x1,y1,'b') hold on text(0,0,'\fontname{隶书}\fontsize{20}S') fill(x2,y2,'b') text(100,0,'\fontname{隶书}\fontsize{20}G') hold on grid on %环境建模 Lsg=100;n=9;N=40; %参数声明 Xmin=-50;Xmax=50;Vmax=(Xmax-Xmin)*0.1; Lbest=zeros(1,N); %个体最优适应值 G=1000; %群体最优适应值 M=1000; la=Lsg/(n+1); fitness=zeros(1,N); %个体适应值 x=zeros(N,n);v=zeros(N,n); %个体位置和速度 pbest=zeros(N,n);gbest=zeros(1,n); %个体最优和群体最优 g=1; %初始化 52 华东交通大学毕业设计 while(g==1) i=1; for i=1:N j=1; while(j<=n) x(i,j)=rand(1)*(Xmax-Xmin)+Xmin; v(i,j)=Vmax*rand(1); j=j+1; end sm=0; for j=1:n-1 s=sqrt((x(i,j+1)-x(i,j))^2+la^2); sm=sm+s; end s1=sqrt(x(i,1)^2+la^2); s2=sqrt(x(i,n)^2+la^2); sm=sm+s1+s2; for j=1:n if (norm([la*j,x(i,j)]-[20,10])<=15)|(norm([la*j,x(i,j)]-[50,-10])<=10)|(norm([la*j,x(i,j)]-[75, 0])<=5) sm=sm+M; break end end x1=[0 x(i,:) 0]; for j=0:n a=cxbz(la*j,la*(j+1),x1(1,j+1),x1(1,j+2)); if(a==1) sm=sm+M; break end end fitness(i)=sm; %第i个个体的适应值 Lbest(i)=sm; %第i个个体的最优适应值 pbest(i,:)=x(i,:); %个体最优位置 if(fitness(i)Vmax) v(i,j)=Vmax; elseif (tempv<-Vmax) v(i,j)=-Vmax; else v(i,j)=tempv; end tempx=x(i,j)+v(i,j); if (tempxXmax) x(i,j)=Xmax; else x(i,j)=tempx; end j=j+1; end sm=0; for j=1:n-1 s=sqrt((x(i,j+1)-x(i,j))^2+la^2); sm=sm+s; end s1=sqrt(x(i,1)^2+la^2); s2=sqrt(x(i,n)+la^2); sm=s1+sm+s2; for j=1:n if (norm([la*j,x(i,j)]-[20,10])<=15)|(norm([la*j,x(i,j)]-[50,-10])<=10)|(norm([la*j,x(i,j)]-[75, 0])<=5) sm=sm+M; break end 54 华东交通大学毕业设计 end x2=[0 x(i,:) 0]; for j=0:n a=cxbz(la*j,la*(j+1),x2(1,j+1),x2(1,j+2)); if(a==1) sm=sm+M; break end end fitness(i)=sm; %第i个个体的适应值 if(fitness(i)=y2&y<=y1)|(y>=y4&y<=y3)|(y>=y6&y<=y5) flag=1; break 55 井雅洁:多机器人系统的路径规划算法研究 else flag=0; end end %位置加权 while(j<=n) %进化粒子的速度和位置 tempv=o*v(i,j)+c1*rand(1)*(pbest(i,j)-x(i,j))+c2*rand(1)*(gbest(1,j)-x(i,j)); if (tempv>Vmax) v(i,j)=Vmax; elseif (tempv<-Vmax) v(i,j)=-Vmax; else v(i,j)=tempv; end if x(i,j)>2 %位置加权到无约束最优 tempx=x(i,j)+v(i,j)-k*2; else x(i,j)<2 tempx=x(i,j)+v(i,j)+k*2; end if (tempxXmax) x(i,j)=Xmax; else x(i,j)=tempx; end j=j+1; end %加变异算子部分的程序: Temp1x=x; %遗传算法之变异 Pm=0.2; for i=1:N for j=1:n Temp=rand(1); Temp; if Pm>Temp Temp1x(i,j)=0; end end Temp1x(i,1)=Temp1x(i,2)/2; Tmep1x(i,n)=Temp1x(i,n-1)/2; for j=2:n-1 Temp1x(i,j)=(Temp1x(i,j-1)+Temp1x(i,j+1))/2; end 56 华东交通大学毕业设计 end h=[x;Temp1x]; for i=1:2*N %个体评价 sm=0; for j=1:n-1 s=sqrt((h(i,j+1)-h(i,j))^2+la^2); sm=sm+s; end s1=sqrt(h(i,1)^2+la^2); s2=sqrt(h(i,n)^2+la^2); sm=sm+s1+s2; for j=1:n if (norm([la*j,h(i,j)]-[20,10])<=15)|(norm([la*j,h(i,j)]-[50,-10])<=10)|(norm([la*j,h(i,j)]-[75, 0])<=5) sm=sm+M; break end end h1=[0 h(i,:) 0]; for j=0:n a=cxbz(la*j,la*(j+1),h1(1,j+1),h1(1,j+2)); if(a==1) sm=sm+M; break end end fitness2(i)=sm; end [oderfitness2,indexfitness2]=sort(fitness2); for i=1:N %遗传算法之选择 x(i,:)=h(indexfitness2(i),:); end 57