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

华东交通大学毕业设计论文题 目： 多机器人系统的路径规划算法研究 英 文 题 目： Research on Path Planning Algorithm ofMulti-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日102开题报告3月23日-3月30日53静态全局规划研究3月31日-4月27日304基于粒子群算法的路径规划研究4月28日-5月25日305毕业论文写作、辩论5月26日-6月20日256英文资料翻译设计期间自行安排时间 指导教师签字： 年 月 日教研室意见：教研室主任签字：年 月 日题目发出日期2006/1/24设计论文起止时间2006/1/242007/6/20附注： 华东交通大学毕业设计论文开题报告书课题名称多机器人系统的路径规划算法研究课题来源本科毕业设计课题类型DY导 师陈世明学生姓名井雅洁学 号20030210030408专 业自动化课题研究背景及应用的意义1课题研究背景；随着计算机技术、信息技术、控制理论、人工智能和传感器技术等学科的开展和成熟，以此交叉而形成的机器人学的研究也进入了一个崭新的阶段。机器人的研究经历了从可编程的、示教再现型的工业机器人到具有一定传感、适应能力的机器人再到配备多种先进传感器，具有自学习和较强适应能力的智能机器人；从结构简单、功能单一的单机机器人到结构复杂，适应复杂环境，功能多样的多机器人系统的开展过程。在机器人研究的早期，单机器人的结构、运动学、控制和信息处理是研究的重点。随着机器人技术的开展，单个机器人的工作能力、鲁棒性、可靠性和效率等都有很大的提升，但是面对一些复杂任务，在环境比拟复杂的情况下，单个机器人很难高效，可靠的完成预期目标。为此，在研究和应用的双重推动下，机器人学的研究一方面进入高智能、柔性更好、能力更强的机器人研究方向；另一方面，通过协作工作的多机器人系统的研究成为一个活泼的研究方向。 多机器人系统作为一种人工系统，实际上是对自然界和人类社会中群体系统的一种模拟。多机器人协作与控制研究的根本思想就是将多机器人系统看作是一个群体或社会，从组织和系统的角度研究多个机器人之间的协作机制，以便充分发挥多机器人系统各种内在优势。多机器人系统具有空间分布的特性，通过多个机器人并行工作可以提高完成任务的效率；其次系统内各种资源信息、知识、物理装置的共享可弥补个体能力的缺乏，扩大完成任务的能力范围；各机器人能力的互补性也可提高完成任务的可能性，增强系统的容错性、鲁棒性和灵活性。多机器人协调协作研究工作的目标就是尽量发挥系统的优势，解决系统中存在的问题或降低其不利影响，使系统能灵活、快速地响应环境和任务的变化，从而在复杂环境中高效、可靠地完成任务。 移动机器人的路径规划是机器人导航系统中不可缺少的重要局部，导航系统是移动机器人的研究核心，同时也是移动机器人实现智能化及完全自主的关键技术。移动机器人的导航问题主要是由Durrant Whyte H F提出的三个问题 “我现在何处?“我要往何处去?“要如何到该处去?。大多数导航系统由两级规划组成，即局部规划(Local Planning)和全局规划(Global Planning)。前者主要解决、两个问题,即机器人定位和路径跟踪问题，而后者主要解决问题，即全局目标分解成局部目标，再由局部规划实现局部目标。 移动机器人按照预先给出的任务命令，根据的环境信息做出全局路径规划，并在行进过程中，不断感知周围的局部环境信息，自主地做出各种决策，并随时调整自身位置，引导自身平安行驶或跟踪路径到达目标位置。移动机器人要实现导航涉及到的根本行为有：自身位置和周围环境的感知与识别、路径规划、路径跟踪、障碍回避等。路径规划是移动机器人导航技术中不可缺少的重要组成局部，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标。 路径规划是移动机器人完成任务的平安保障，同时也是移动机器人智能化程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高移动机器人的智力水平，减少移动机器人在移动过程中存在的不确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机器人、探测机器人、效劳机器人、汽车自动驾驶系统打下根底。2应用意义自动控制、计算机、微电子、人工智能、通信等理论和技术的不断开展和普遍应用使机器人化的各种工程设备、自动化机械具有越来越强的智能性和自主工作能力。这些具有一定智能、可以自主完成某些工作的自动化设备构成的复杂多机器人系统在船舶制造、产品装配、交通系统、航空航天等国民经济和国防建设领域的应用中具有极大的经济价值和社会价值。它们在信息处理、协调协作算法、实时控制、冲突消解以及解除死锁等问题的研究中可以为交通系统中自动驾驶、自动导航、路径优化以及交通流量控制等问题的解决提供了许多根本方法，在减轻驾驶员的负担、提高运输效率等方面具有潜在的应用价值。路径规划是移动机器人导航技术中不可缺少的重要组成局部，它要求机器人根据给予的指令及环境信息自主地决定路径，避开障碍物，实现任务目标。 路径规划是移动机器人完成任务的平安保障，同时也是移动机器人智能化程度的重要标志。尤其是在机器人硬件系统的精度在短期内不能得到解决的情况下，对路径规划算法的研究尤为重要，这将从根本上改变移动机器人的导航性能，将提高移动机器人的智力水平，减少移动机器人在移动过程中存在的不确定状态，提高移动机器人移动的速度及灵活性，为开发高智能的远距离搬运机器人、探测机器人、效劳机器人、汽车自动驾驶系统打下根底。课题研究现状及开展趋势1研究现状对机器人路径规划的研究，世界各国的专家学者们提出了许多不同的路径规划方法，主要可分为全局路径和局部路径规划方法。全局路径规划和局部路径规划是按照机器人获取环境信息的多少划分的。全局路径规划是指机器人能够获取全部的环境信息，并以此为根底进行的规划；局部路径规划是指在环境信息未知或局部未知的情况下，机器人通过传感器感知周围局部信息进行的路径规划。根据环境中分布物体运动特点的不同，路径规划又可分为静态路径规划和动态路径规划。障碍物与目标静止情况下机器人的路径寻优为静态路径规划；机器人寻优过程中障碍物与目标处于运动状态即为动态路径规划。全局路径规划方法有位形空间法、广义锥方法、顶点图像法、栅格划归法；局部路径规划方法主要有人工势场法，遗传算法等。这些方法都各有优缺点，对于实际的应用场合，需要将各种方法结合起来使用。1静态环境中的全局优化路径规划算法。静态环境下的全局路径规划是开展比拟成熟的一个研究方向。目前进行规划的方法也比拟多。最常用的方法有位形空间法、广义锥法、顶点图像法、栅格划归法、最短切线法。同时一些智能算法如遗传算法、粒子群算法也越来越多的应用于全局路径规划。2动态不确定环境的局部优化路径规划算法。动态环境下路径规划的方法主要有几何计算法、人工势场法、基于模糊控制器的路径规划法等。2.开展趋势移动机器人的路径规划是机器人导航和控制中非常重要的一个环节。对于路规划算法的研究经历了从传统常规算法到新型智能算法的开展过程。随着信息技术、通信技术、传感器技术和人工智能等相关学科的开展，优化算法走向了灵活、智能、高效的开展方向。可以预见，在不久的将来，新的信息处理技术和智能算法会大量并入该领域，在优秀算法的协助下，机器人可以灵活应用于军事、航空、交通运输等各种领域。本课题研究的内容主要包括多机器人系统在静态环境中的全局优化路径规划算法、动态不确定环境中的局部优化算法。重点研究粒子群算法在移动机器人路径规划中的应用。具体要求：1 设计要求（1） 熟悉静态环境中全局优化路径规划算法（2） 熟悉适宜于动态不确定环境的局部优化路径规划算法（3） 掌握粒子群优化算法的应用课题研究方案 本课题应用粒子群算法进行移动机器人路径规划。整个规划过程分两步进行。第一步进行环境建模，即建立一个坐标系，并在其中设置一定数量一定形状的障碍物、机器人的起始位置和目标位置，并采用区域划分的环境建模思想划分工作空间，将路径优化问题转化为目标函数优化问题。第二步采用粒子群算法进行路径优化，生成一条从起始位置到目标位置的最优或近似最优无碰路径。1.环境建模环境建模是进行路径规划的首要步骤，也是非常重要的一个步骤。模型建立的好坏会直接影响优化算法的实现程度和优化路径的优劣。这篇论文采用区域划分的环境建模的思想，即对机器人的工作环境依实际情况的需求进行划分，为简化模型我们做纵向的n可称作维度等分。路径规划即可表示在区域边界确定的情况下，在每条纵线上找一个适宜的点 (第i条纵线上的点)，组成一个点的有序点序列，这个序列即可表示机器人的一条路径。如果知道每个点的坐标位置，就可以用一个2×n的矩阵表示这一条路径，矩阵的第一行存储每个维度的横坐标，第二行存储纵坐标。考虑到区域划分的特殊性，各个维度的横坐标有一个等差关系，可以不用表示出来，所以一个1×n的矩阵即可表示机器人的一条路径。例如我们用X=表示机器人的一条路径，表示第i个维度的纵坐标,那么X为路径规划中的一个解。我们定义路径的长度为目标函数F=f，也称作适应度函数。Min F即为全局路径规划的最优解。考虑到环境中存在障碍物，该课题为带约束条件下目标函数的优化问题，既需要在可行区域内找到一个解X,使得目标函数的值为最小。对于不可行解即X中存在障碍物中的点或X决定的路径穿过障碍物，采用惩罚技术加一个惩罚函数使其适应值高于可行解的适应值。2.路径优化本篇论文在路径优化中采用粒子群进化算法寻求目标函数的最优解，即全局的最优路径。粒子群算法借助“群体和“进化的生物学概念，通过屡次进化找出群体中的最优个体。对于每个个体，都有两个行为，认知与学习。认知的过程就是个体与自身经历作比拟，试图到达个体最优的过程；学习的过程就是个体与群体最优进行比拟趋进群体最优的过程。在整个进化过程中，个体通过跟踪两个极值更改自身的速度和位置信息，以便趋向全局最优位置。将粒子群算法应用于路径规划中，采用粒子群算法寻求全局的最优路径，即目标函数的最优解X,也即使得路径最短的可行解X。算法的流程如下：1设置粒子数N,粒子维数n，及最大迭代次数t。2初试化粒子速度v和位置x各个时间维度上的位置。3计算每个粒子的适应值即每个粒子所走路径的长度，对于不可行解适应值加一个惩罚值。4确定个体最优p和群体最优g。5考虑约束条件，对粒子的速度、位置进行进化。6未到达最大迭代次数返回3，否那么结束。3.算法改良 针对根本粒子群算法在移动机器人路径优化中存在的局部极小值问题，采用位置加权到无约束解和加变异算子两种方法，改良路径优化的效果。4.结果评价 采用粒子群算法进行移动机器人的路径规划算法简单、寻优过程快、且具有自适应智能效果。位置加权到无约束最优和加变异算子的方法可加快算法的收敛速度，有效解决局部最小问题。设计进度安排11月24日-3月22日 文献阅读，熟悉MATLAB仿真平台23月23日-3月30日 开题报告33月31日-4月27日 静态全局规划及单机控制研究44月28日-5月25日 动态规划及群集控制研究55月26日-6月20日 毕业论文写作、辩论设计参考文献：1 谭民.王硕.曹志强,多机器人系统, 清华大学出版社.2 Jiming Liu著,靳小龙等译,多智能体原理与技术.3 曾建潮.介 .崔志华,粒子群算法,科学出版社.4 刘卫国,MATLAB程序设计与应用,高等教育出版社.5张颖，吴成东，原宝龙. 机器人路径规划方法综述.控制工程，2003，10.6黄祎，孙德宝，秦元庆.基于粒子群算法的移动机器人路径规划J.测控技术,2006,25(4).7侯志荣，吕振肃.基于MATLAB的粒子群优化算法及其应用.计算机仿真J,2003,20(10). 8Dong 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指导教师签名： 日期：课题类型：1A工程设计；B技术开发；C软件工程；D理论研究；2X真实课题；Y模拟课题；Z虚拟课题1、2均要填，如AY、BX等。多机器人系统的路径规划算法研究摘 要移动机器人路径规划的研究是机器人研究领域中的一个热点，它对实现机器人导航制导及跟踪控制起着无可替代的作用。路径规划是机器人有效完成任务的平安保障，同时也是反映机器人智能化水平的重要标志。随着信息技术，通信技术，传感器技术和人工智能等相关学科的开展，许多新技术和智能算法并入该领域，促进了路径规划技术的提高。本文基于粒子群算法开展移动机器人路径规划问题的研究。首先阐述了粒子群算法的原理及各个参数的物理意义，指出它作为一种智能优化算法在函数优化问题中的优越性：进化速度快，算法简单，且具有自适应性和群体智能性。对于算法会引起的局部最小问题，创造性的提出了位置加权到无约束解和加变异算子两种改良方案。其次针对路径规划问题，采用区域划分的环境建模思想，通过构造简单的环境模型将该问题转化为带约束目标函数优化求解问题。最后，通过仿真实现了基于粒子群算法的路径优化，比拟了根本粒子群算法和各种改良算法在解决固定初始化方式下局部极小值问题上的不同效果，证明了位置加权和加变异算子的方法在解决局部最优问题上的有效性。关键词: 移动机器人; 路径规划; 粒子群算法; 位置加权; 变异算子 Research on Path Planning Algorithm of Multi-robot SystemABSTRACTThe 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 robots 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 目录1 绪论11.1课题研究的背景及意义11.2 移动机器人路径规划研究现状21.3 智能算法及其应用31.4 课题研究的主要内容及框架32 粒子群算法综述52.1 粒子群算法的研究背景52.2 根本粒子群算法52.2.1 根本概念52.2.2 算法原理及流程62.3 改良粒子群算法72.4 粒子群算法和其他进化算法的比拟83 移动机器人路径规划103.1 环境建模103.2 路径规划的方法11传统路径规划方法11 智能路径规划方法113.3 约束优化问题及处理方法133.3.1 约束优化问题的描述133.3.2 约束优化问题的处理方法134 基于粒子群优化的路径规划算法及仿真144.1仿真平台简介144.2 问题描述与环境建模144.3 路径初始化164.4 基于粒子群算法的路径规划仿真184.4.1 基于根本粒子群算法的路径规划仿真184.4.2 基于改良粒子群算法的路径规划仿真214.5 仿真结果分析234.6程序调试中的问题及处理245 结论与展望255.1 结论总结255.2 以后可做的工作和展望26谢辞27参考文献28附录A 外文翻译-原文局部29附录B 外文翻译-译文局部35附录C 流程图及仿真图形39附录D 主要源程序521 绪论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.2 移动机器人路径规划研究现状 移动机器人路径规划Path Planning of Mobil Robot是机器人学的一个重要的研究领域，也是一个最根本的问题。它被描述为：给定一个移动机器人所处的环境环境可以通过移动机器人传感器系统或者别的途径获得，一个起始点和一个期望的终止点，规划出一条移动机器人可行的从起始点到达终止点，且避开环境中障碍物的最短的运动路径。这个问题从外表上看是一个简单易描述的问题，而实际上它的复杂度随着移动机器人的构型空间维度的增加而不断增长。对移动机器人路径规划的研究目前主要有两类：一类是移动机器人自主导航；另一种是根据移动机器人所处的环境，由一个主机首先规划好移动机器人的路径，然后设计相应的控制器，控制移动机器人跟踪给定的规划好的路径。单移动机器人路径规划的研究经过多年的开展已成为一个日趋丰富、成熟的方向。近几年，多移动机器人系统路径规划的问题受到了众多学者的重视，成为了一个比拟复杂而又独具特色的优化问题。在生产与科研中，如工厂的复杂装配中，需由许多移动机器人代替人类在恶劣的环境下合作完成繁重的装配任务。在这种情况下，多个移动机器人与所处的环境就构成了一个系统，为完成给定的任务，就需要对多个机器人同时进行路径规划，即在规划多个机器人的运动轨迹时要考虑群体协调的问题。多机器人系统的路径规划现在已经成为一个研究的热点，所采用的优化算法也从传统的算法开展为群体智能算法。智能算法作为一种模拟自然界生物群体行为的进化算法，为优化问题提供了一种有效的求解方法。常用的智能算法有遗传算法、蚁群算法、粒子群算法等，它们都在不同程度上被借鉴用来规划移动机器人的运动路径。本课题重点研究粒子群算法在移动机器人路径规划中的应用。 路径规划是按照某一性能指标搜索一条机器人从起始状态到目标状态的最优或近似最优的无碰路径。进行路径规划需要做两大块工作：构建环境模型以及采用优化技术优化路径。根据规划过程中环境信息获取方式的不同和路径优化过程中采取的优化算法的不同可对路径规划问题做出不同的分类。在环境信息获取方式方面，根据机器人的工作环境模型的不同可以分为两种。一种是基于环境先验信息的路径规划，作业环境的全部信息都是预知的，也即全局路径规划；另一种是基于传感器信息的路径规划，作业环境的信息是全部未知或局部未知的，即障碍物形状、尺寸和位置等信息必须通过传感器在线获取，也即局部路径规划。常用的全局路径规划的方法有可视图法、自由空间法、环境地图法和栅格法等。常用的局部路径规划的方法有人工势场法等。在算法优化方面，可将路径规划分为传统优化和智能优化两种。传统的优化方法有自由空间法、图搜索法、栅格解耦法等；智能优化方法有模糊逻辑法、神经网络法、遗传算法、粒子群算法等。另外，根据机器人工作空间中障碍物的运动特点的不同还可将路径规划分为静态确定环境下的路径规划和动态不确定环境下的路径规划。在静态环境中，障碍物的位置、形状、大小是确定不变的，这种情况下进行路径规划不用过多考虑障碍物的运动情况和信息，相对于要实时分析障碍物运动情况的动态环境路径规划算法要简单一些。采用智能算法进行复杂环境下移动机器人路径规划的研究是当今路径规划领域研究的热点，其研究成果已经应用于复杂装配车间、军事、航空航天等多个领域，显示出了巨大的经济价值和社会应用价值。本篇论文重点研究复杂障碍物环境下移动机器人的路径规划。所采用的优化算法是智能算法中的粒子群算法。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仿真平台为根底实现了基于粒子群优化算法的移动机器人路径规划的仿真实验，最后研究了位置加权改良粒子群算法、加变异算子改良粒子群算法在解决局部极小值问题上的应用效果。具体的结构编排如下：第一章简单介绍了移动机器人路径规划研究的背景、现状并指出常用的规划方法。讲述了智能算法，尤其是粒子群算法及其应用。第二章详细阐述了粒子群算法的思想和原理，研究该算法中各个参数的物理意义及其对进化过程的影响。针对优化问题中出现的局部极小值问题提出采用位置加权改良粒子群算法和加遗传变异算子改良粒子群算法两种解决方案。通过与其它进化算法的比拟，进一步研究了粒子群算法的特性。第三章系统阐述了移动机器人路径规划中的两大块内容：环境建模和路径规划的方法。从传统和智能两种角度讲述了常用的路径规划方法及特点。最后提出约束优化问题及其解决方案。第四章研究了将粒子群算法应用于移动机器人路径规划中的整个过程并进行了实验仿真。其中主要内容有问题描述与环境建模、生成初始化路径、采用各种粒子群进化算法优化路径及仿真结果分析等。其中，针对局部极小问题，研究了改良算法，如位置加权法和加变异算子法的解决效果。最后第五章我们对本篇论文做了总结。指明了本论文的创新之处并对以后可做的工作进行了展望。2 粒子群算法综述2.1 粒子群算法的研究背景寻求性能良好的全局优化算法并使之能可靠收敛于问题的全局最优解，这一直是优化领域孜孜以求的研究目标和热点。所谓最优化问题，就是在满足一定的约束条件下，寻求一组参数值，以使某些最优性能度量得到满足，即使系统的某些性能指标到达最大或最小。最优化的应用可以说涉及到工业，社会，经济，管理等各个领域，其重要性是不言而喻的。按照目标函数，约束函数的性质以及优化变量的取值范围等，可将最优化问题分成许多类型，每一种类型根据其特征不同有特定的求解方法。常见的优化方法大多数为局部优化的方法，都是从一个给定的初始点开始，依据一定的方法寻找下一个使得目标函数得到改善的更好解，直至满足某种停止条件。成熟的局部优化算法有Newton-Raphsonf法， Fletcher-Reeves法 Polar-Ribiere 法Davidon-Fletcher-Power(DFP)法 Broyden-Fletcher-Goldfarb-Shann (BFGS)方法等，所有这些局部优化算法都