移动机器人环境自适应的自主规划方法研究(完整版)资料

移动机器人环境自适应的自主规划方法研究（完整版）资料(可以直接使用，可编辑优秀版资料，欢迎下载）

移动机器人环境自适应的自主规划方法研究（完整版）资料(可以直接使用，可编辑优秀版资料，欢迎下载）学号2021041431密级___________哈尔滨工程大学本科生毕业论文移动机器人环境自适应的自主规划方法研究院（系）名称：自动化学院专业名称：自动化学生姓名：张瑞丰指导教师：王宏健哈尔滨工程大学2021年6月移动机器人环境自适应的自主规划方法研究移动机器人环境自适应的自主规划方法研究张瑞丰哈尔滨工程大学学号2021041431密级___________移动机器人环境自适应的自主规划方法研究ResearchonEnvironmentalAdaptiveAutonomousPlanningMethodforMobileR学生姓名：张瑞丰所在学院：自动化学院所在专业：自动化指导教师：王宏健职称：教授所在单位：哈尔滨工程大学论文提交时间：2021年6月日论文答辩时间：2021年6月日学位授予单位：哈尔滨工程大学摘要作为一项高新科技，如今移动机器人已经被应用于各种生产生活当中。在其面对不同的工作环境时想要完成任务必须拥有适应环境的自主规划方法，因此环境自适应的自主规划方法的研究对于移动机器人实现作业是极其重要的。本文针对移动机器人的路径规划问题展开研究，面向部分已知的环境，运用以波函数表述粒子状态的量子行为粒子群优化算法完成机器人的路径规划问题求解。首先，基于粒子群优化算法和量子粒子群优化原理，通过对比粒子群优化与量子行为粒子群优化的优缺点，选用具有量子行为的QPSO算法用于问题求解；其次，运用MATLAB建立了部分已知的环境模型，根据路径安全性需求，提出粒子有效性的检验方法，解决了因无效粒子的存在容易导致量子粒子群算法应用于路径规划求解时陷入局部最优解甚至规划失败的问题；再次，设计了基于路径长度为目标优化函数和量子粒子群优化路径算法流程；最后，通过量子粒子群参数寻优实验，获得一组优化量子粒子群控制参数，并完成了MATLAB不同仿真环境条件下移动机器人路径规划的仿真验证。经过仿真实验证明：本文提出的算法可以使移动机器人在复杂的工作环境中优化出一条安全路径，说明将量子行为粒子群优化算法应用于移动机器人环境自适应的自主规划问题可以取得较好的效果。关键词：移动机器人；路径规划；粒子群优化；量子粒子群优化ABSTRACTAsahigh-tech,theappliedrangeofmobilerobotexpandedwidelyinrecentyears.Ifrobotswanttocompletethetaskindifferentworkingenvironment,theymusthavethecapacityofautonomousplanningmethodtoadapttheenvironment.Sothecapabilityofautonomousplanningmethodformobilerobotsplaysanimportantandbasicroleinroboticsresearch.Thispaperwasorientedmobilerobotspathplanninganditproposedsolutionstoavoidobstaclesinpartoftheenvironmentthatwasknown.ItusedthealgorithmofQuantumbehaviorparticleswarmoptimizationthatwasbasedonthewavefunctiontodescribethestateoftheparticletodesignautonomousplanningmethod.Firstly,thepaper,basedontheparticleswarmoptimizationandquantumparticleswarmalgorithm,balancetheexcellencesanddisadvantagesbetweenthetwoalgorithms,andthenchooseQPSOtosolvethequestion.Secondly,itestablishedmathematicalmodelingofthetargetenvironmentwithMATLABandanditputforwardsthemethodbyexaminingtheeffectivenessoftheparticlestoimproveinvalidparticlestoavoidfallingintothelocaloptimalintheapplicationsofQPSOpathplanningmethods.AndthenitdesignedtheflowchartofalgorithmbasedonthetargetpathlengthfunctionandQPSO.Finally,thepaperachieveasetofcontrolparametersbasedontheexperienceofthequantumparticleswarmoptimizationanditdevelopedrobotpathplanningsystemwhichwasbasedontheenvironmentofMATLAB.Visualexperimentsshowthattherobotpathplanningmethodwaspresentedinthisthesiswasefficiencyandaccuracy.Andthealgorithmforautonomousmobilerobotindependentprogrammingbasedonquantumparticleswarmoptimizationcanbeachieved.Keywords:mobilerobot;pathplanning;particleswarmoptimization;uantumparticleswarmoptimization

目录第1章绪论 11.1课题研究的目的和意义 11.2移动机器人路径规划现状 21.3群体智能的概况 6 7 81.4量子粒子群优化算法国内外发展现状 9 9 111.5本文研究的主要内容 161.6论文组织结构 17第2章量子行为粒子群优化算法的基本原理 182.1引言 182.2优化问题与优化方法 182.3群体智能算法 19 20 212.4粒子群优化算法与量子行为粒子群优化算法的比较 242.5本章小结 26第3章基于量子粒子群算法的移动机器人路径规划算法设计 183.1引言 273.2移动机器人路径规划环境空间建模 27 27 28 303.3路径规划算法设计 32 32 32 32 33 333.4本章小结 35第4章移动机器人量子粒子群路径规划仿真实验 184.1引言 364.2算法参数寻优 364.3算法仿真实验验证与结果分析 40 40 40 42 424.4本章小结 44结论 45参考文献 46致谢 49第1章绪论1.1课题研究的目的和意义移动机器人技术涉及许多研究领域，例如：自动控制原理、人工智能化技术、机械工艺及其制造技术、多传感器数据融合技术、机电一体化以及仿生学等。两院院士宋健曾指出：“机器人学的进步和应用是当代最高意义上的自动化[1]”。移动机器人技术代是代表高新科技前沿的发展技术，是未来科技的发展方向。因移动机器人技术的不断发展受到人们的关注，对其研究已经到达一个新的阶段。移动机器人技术是国家工业化与信息化过程中的重要发展力，因其应用广泛不仅在研究生产生活中起到了作用，而且为各种智能行为的产生、人类大脑思维的探索的研究提供了有效的工具和平台[2]。将移动机器人以控制方式进行分类，大致可以分为三类，分别是全遥控机器人、半遥控机器人和全自主机器人。在三种类型中，全自主式移动机器人因为其对环境的自我感知能力及自我适应能力使得可以适应更广泛的领域和更复杂的工作环境及任务[3,4]。如果移动机器人想要成功完成任务，就需要在各种复杂环境中找到可以完成任务的路径，在行进的过程避免不必要的碰撞，进而到达指定目标点。移动机器人在运动过程中可以躲避物体正是其自适应性的体现，也是自主机器人的主要优点。这种根据不同的外界环境，建立行为模型，实施决策躲避障碍物的行为不仅是移动机器人的基本能力，也可以使其在执行任务的过程中避免受到不必要损伤，保证更好完成任务。按照固定的搜索方式以一定的标准找到可以使移动机器人从指定作业点到达目标点的方法是移动机器人自主规划的主要任务。所以说，对移动机器人自主规划的方法进行研究，无论在理论上和实践应用中都有着非常重大的意义。自主规划在实际应用中主要体现在路径规划上，从本质上来看，路径规划问题是一种优化问题，其目的就是想要使机器人能得到工作所需要的环境条件，研究路径规划方法在提高机器人的作业能力的同时也从一个方面提升了机器人的智能水平[3]。时至今日，在国内外研究者对路径规划方法的探索中已经诞生了许多具有代表性的方法，例如人工势场法、模糊推理法以及遗传算法等。这些方法无论在理论研究中还是在实际应用中都有着非常好的效果，但在一些方面他们也存在着不可避免的缺点。因此，这些方法都只能针对一些特定要求，在特定的环境中规划出相对比较理想的路径，而不能很好的满足自主规划的整体要求。因此，提出一个较为理想的方法用于路径规划对于移动机器人技术的发展有着相当重要的意义。1.2移动机器人路径规划现状随着机器人的不断发展，它也越来越广泛的被应用在各个领域之中，与此同时，对于机器人的“智能”的要求也越来越高，除了基本能力外，还需要机器人拥有面对周围变换环境时的交互能力[4]。所以当移动机器人处在一个复杂的环境中时在最短的时间里规划出可行的优化路径已经是其在完成任务时的基本要求，除此之外，移动机器人在路径规划方面表现出的优化能力也是其智能水平的一种体现。正因为路径规划问题的这种实用价值，导致国内外的许多研究者对它都很感兴趣。(1)布鲁克林理工学院的F.Khorrami针对无人水下航行器的路径规划问题采用全局与局部分别分级规划的路径规划方法取得了非常好的效果[5]。在全局规划范围通过高级规划进行路径规划，通过传感器获得的数据进行局部的路径规划(图1.1a为规划结构图)。通过手中已经获得的各种环境条件运用A*算法在栅格地图中以距离和平滑度为依据进行全局路径的路径规划，；局部运动规划利用传感器采集现在时刻环境，根据后的的信息通过算法规划运动方向进行局部避碰，图1.1b、1.1c为仿真结果。图1.1a规划结构图图1.1b图1.1c(2)哈尔滨工程大学的潘洪悦针对无人水下航行器在水下进行路径规划问题提出一种基于粒子群优化算法的改进办法，算法中将海底的三维工作环境按照固定的距离进行分割，在改变PSO优化算法的惯性权重的改变方式的基础上对PSO优化算法中粒子的迭代进化公式进行了新的定义，并且基于遗传算法将其思想中的种群共享机制引入粒子群优化算法中，对其进行了改进[6]。在文中将路径规划问题抽象成数学几何问题，通过对路径有效性的判断进行最终路径的筛选。在工作空间中将障碍物所在空间进行分割，选择规划路径中的点，使点不在障碍物中或相邻两点连线不穿过障碍物，最后将选择的路径中的的各点依次连接便可以获得最终路径，如图1.2a、1.2b。图1.2c是实验的仿真结果，实验结果说明文中提出的建模方法以及所改进的算法可以为无人水下航行器在其工作的环境中设计一条无障碍的路径。图1.2a图1.2b图1.2c三维仿真实验图(3)上海交通大学张彪运用三维栅格地图的方法解决了移动机器人在路径规划的过程中使用三维地图所遇到的问题[7]。在算法中将算法进行拓展，并用拓展后的算法将激光扫描仪在三维空间内扫描所得到的三维点云转化成八叉树结构的三维栅格地图，并且在不忽略机器人尺寸的基础上，直接在栅格中生成多条可以保证机器人安全的在工作环境中运动的路径。在进行实物验证的过程中，在工作环境内设置若干障碍物，运用上述算法生成实验中场景的三维栅格地图（如图1.3a、1.3b），对算法进行了验证并生成了两条路径（如图1.3c）。图1.3a实验中实际场景图1.3b图1.3c(4)重庆邮电大学的蒲兴城将细菌觅食过程中的趋化行为应用到移动机器人的路径。规划过程中，提出了一种移动机器人路径规划的方法[8]。文中的算法仿照细菌的觅食过程及细菌的环境为移动机器人提供建模方法，结合智能机器人的自身传感技术设计有效的趋向以及避障的系数，为机器人在简单甚至复杂的环境下提供相应的运动路径策略，实现实时导航任务的目的。研究者以高斯势场作为移动机器人的工作环境，并在证明此法的有效性和可行性的基础上进行了稀疏与稠密障碍物比对证明了这种算法具有很好的安全性、实时性和平滑性(如图1.4)，说明这种方法不仅能实现机器人的路径规划任务，而且优化出的路径能使移动机器人在障碍物密集的区域内领过调整位姿。图1.4a图1.4b1.3群体智能的概况在路径规划的过程中，所求得的最优路径往往受到多方面因素的影响，而且通常情况下各个因素间会存在冲突，在提升单方面因素带来的效果时会降低其他一个甚至多个因素带来的影响，进而导致无法保证所有因素都处于最佳状态，为了使整体能够“最优”，就要尽力调节各方面的的因素之间的冲突，在保证大环境最优的情况下，采取折衷的方式进行规划，而群体智能算法的核心思想为解路径规划过程中多因素影响的问题提供了解决办法[5]。所谓的群体智能，从生物社会学角度来看，就是各种群居动物在集体生活中产生的以群体为单位表现出的“智能”。从计算科学的角度上看，群体智能是许多没有智能的个体以群体的形式在他们组成的系统中表现出智能特性。群体中的每个个体在没有集中控制的情况下通过互相协作来解决问题，这恰好能够解决路径规划问题中子目标间冲突的问题，因此群体智能优化算法更加适合用来解决移动机器人的自主路径规划问题[6]。将群体智能中的生物群体所变现出的智能行为作为研究的基础，进而对这些群体生物表现行为的原理本质进行分析，并运用分析出的原理为基础对实践应用进行指导，便可以开发出针对实际问题求解的新方法，为求解复杂的实际工程提供了更好的条件。群体智能优化算法的搜索方式使以概率密度为依据进行的，这种算法有以下几个优点：（1）为了保证整个系统具有非常好的鲁棒性，不让某个单独的因素影响到整个系统的控制结果，整个系统的控制方式采用分布式控制，而不是集中地约束和控制；（2）由于整个系统中的每个独立的个体都可以通过直接或间接的方式进行信息交流，这使得系统具有非常好的扩展性；（3）在整个系统中，每个个体的属性相对单一并且每个个体的独立行为发生的时间相对较短，使得算法在实现方面比较容易；（4）整个群体所表现出来的复杂的行为动作都是通过每个相对简单的独立个体相互配合协作合作所表现出来的，这表现出自了系统的组织性。1.3.1粒子群优化算法粒子群优化算法)是在1995年由美国社会心理学家和电气工程师共同提出的，其基本思想是受他们早期对鸟类群体行为研究结果的启发，并利用了生物学家的生物群体模型[7]。最早出现的模拟鸟群行为的模型是1986年由提出的（）模型[9]。这个模型受到鸟群飞行的启发，很多集体行为都很复杂，很难解释，比如说鸽子可以在集体飞行时集体同时转向、蝙蝠集体在洞穴中快速飞行时彼此之间不会发生碰撞等。假如说在群体中存在一些确定的行为准则，而且每一个个体对这个准则都能严格遵守，那么当这些各自以群体的形式行动时，他们的行为就能表现出之前所说到的“智能”[8]。在这个模型中，每一只BOID都是一只人工定义的鸟，他们每个个体都能够从附近范围内的环境中后的其他个体的行为信息，以这些信息作为输入结合自己当前的行为信息，群体系统就可以做出一个时刻的飞行策略。群体中每个个体遵循以下三条运动行为准则：（1）避免碰撞：群体中每个个体在飞行的过程中尽量远离与自己距离较近的个体，不能与其他个体产生碰撞；（2）速度保持一致：群体中每个个体在飞行过程中要注意自身速度，不可以与种群的平局速度相差太大；（3）中心集群：群体中每个个体在飞行过程中向其他个体的平均位置移动，即向群体的中心飞行。整个系统在运行的过程中不需要依赖其他任何指令，完全是时系统本身自上而下的力量。虽然每个个体都只是按照自己的运动规律，但是模型中的群体却呈现出了惊人的整体秩序。在以上模型的基础上，Heppner和Grenande又进一步提出鸟群和栖息地之间的吸引关系[10]。起初在鸟群的飞行过程中，他们的飞行方向时不确定的，这种情况会持续到一只鸟找到了栖息地，随后所有的鸟都会向栖息地靠近，最终落到栖息地。在此基础上Kennedy和Eberhart又提出了自己的模型，他们将模型设定为寻找位置方向食物的鸟群。在整个食物的寻找过程中，鸟群中每个个体之间会传递信息，它们会考虑当前时刻鸟群的最好位置和自身在飞行过程中的最好位置，凭借这两个因素综合考虑决定下一步自己的飞行位置，使得自己向最有利于自己的方向飞行，进而找到食物。其中提到影响每个个体下一步动态的因素就是信息传递和个体学习的概念来源，即在个体决策的的过程中会受到自身经验和其他个体经验的影响[9]。粒子群算法就是基于此思想形成的，算法中每个人工鸟称为一个粒子。每个粒子对于整个优化问题都有自己对应的适应度，自身的运动状态由每一时刻的速度和对应时刻的位置来描述。粒子群算法是一种优化搜索技术，在整个解空间内寻找当前已知的最好粒子的位置，搜索过程通过迭代更新进行，即先经过随机初始化，通过更新方程搜索全局产生最优解。1.3.2量子行为粒子群优化算法PSO算法中粒子每一时刻的运动状态都是由上一时刻的速度和对应的位置决定的，而且速度时限定在一定范围内的不是无穷大，所以粒子的位置一直都到限制，不会有大幅度的变化，这就使得粒子不能够不能出现在解空间的每一个位置，进而导致PSO算法不能完全收敛到最优解[10]。针对粒子群算法的缺点以及量子空间的特性，2004年江南大学的孙俊等将粒子群算法与量子行为结合，基于量子势阱建立了新的粒子群模型，并在此基础上改进了粒子群优化算法，提出了具有量子行为的粒子群优化算法（Quantum-behaved）[11]。该算法结合了粒子群算法和量子力学的思想，用波函数代替速度和位置特征来表述粒子的运动状态，这使得粒子在进化和移动时不被轨迹所束缚，而是受到势场吸引而运动，可以出现在空间上的任意一点[11]。由于是受到势场的吸引力又不能跳出解空间，也就可以使粒子在整个解空间中进行搜索，这就大大加大了粒子的搜索范围和不确定性，增加了粒子离开局部最值解的概率，从而解决了粒子群算法不完全收敛的缺点，所以量子粒子群优化算法在搜索能力方面是粒子群算法所不能比拟的。不仅如此，单纯使用波函数来描述粒子状态也让量子粒子群算法的控制参数更少，在调理清晰的同时使得其更易实现，而且运算速度也大大提高。1.4量子粒子群优化算法国内外发展现状1.4.1国外研究现状(1)伯明翰大学的结合欧几里的距离对量子粒子群优化算法算法提出了改进，并将改进后的算法应用于多目标优化问题[12]。在算法中以值代表算法里的粒子，在解空间中值代表的物理意义是解空间中的向量，并且向量与目标空间维数保持一致，向量之间的夹角大小与向量对应的值的欧氏距离成正比，如图1.5表示的是在二维目标空间里对应的值。所以将粒子现在时刻的值与之前所有时刻全局中的值来比较，选出距离最小的值对应的粒子则该粒子即为局部最优，用这种方法可以加快粒子的寻优速度。最后对该算法进行了房展实验，对比结果说明此算法的优越性。表1.1图1.5二维目标空间值(2)印度工业学院的针对量子粒子群优化算法在粒子进化过程中会产生相对不好的粒子的问题，对量子粒子群优化算法进行了改进。在每一次粒子进行进化更新之后，在所有粒子中随机选取三个粒子，计算其平均值用计算结果代替三个粒子中不好的那个粒子[13]。文中运用函数对改进的的算法进行了仿真实验，与另外几种算法)进行对比，实验结果显示了此算法的优越性。表1.2为仿真结果。表1.2不同算法的结果比较1.4.2国内研究现状(1)浙江工业大学的黄泽霞针对量子粒子群的惯性权值线性递减不能适应复杂的非线性优化搜索过程的问题改进了量子粒子群优化算法，提出了一种惯性权自适应调整的量子粒子群优化(DCWQPSO)算法。在该算法中，引入了量子粒子群进化速度因子和聚集度因子，并将惯性因子表示为,2个参数的函数。图1.6表示的是改进算法对优化函数的寻优结果，在每次迭代时，算法中的惯性权值可以根据当前时刻量子粒子群的更新速度和聚集度动态的进行变化，这种改进可以使算法对工作环境拥有更好的适应度。对典型的标准函数的测试结果表明，与量子粒子群算法相比DCWQPSO算法平均迭代次数明显降低,收敛速度明显提高，这在算法早期运行时效果尤其明显，而且具有更好的全局收敛性能，表现了良好的效果[14]。图1.6a标准函数下的最优适应度进化曲线图1.6b标准函数下的最优适应度进化曲线图1.6c标准函数下的最优适应度进化曲线(2)西南交通大学的郑凯等人在针对QPSO算法在粒子更新迭代搜索最优解的过程中，因粒子趋向同一化，导致后期收敛速度较慢，易早熟而陷入局部最优解的问题，提出一种两群量子粒子群算法（TwoSwarm-substitutingQPSO，TSQPSO），即将算法中的粒子群分为两群，分别采取不同的搜索方式在解空间内进行搜索，其中一群为主搜索群，采用全局搜索算法进行搜索，而另一群为辅助搜索群采用局部搜索算法进行搜索，为了保证搜索群中粒子的多样性，人为规定在特定的条件下将两个搜索群中的部分粒子相互调换，这个方法有效的避免了算法因为同一化而陷入早熟，保证了主搜索群科以搜索到全局最优解，郑凯等人将TSQPSO算法应用于电力系统无功优化中，并与用带惯性权重的粒子群算法()和量子粒子群算法()对比进行仿真实验，取得了非常好的效果表1.3三种算法的优化结果比较图1.7a系统节点电压幅值分布图图1.7b、和的收敛曲线(3)江南大学的奚茂龙在分析量子粒子群算法的基础上，针对离散搜索空间的问题，提出了二进制编码的量子粒子群算法。在算法中，重新定义了粒子的位置距离矢量，调整了搜索空间的迭代方程（如表1.4），并引入了多点交叉和精英保留的策略，保证全局收敛的同时加快粒子的收敛速度。并使用DeJong’s测试函数对所提出算法和二进制粒子群算法进行了比较，在函数测试中得到了较好的测试性能，最后使用二进制编码量子粒子群算法对机器人路径规划在的运动空间里进行了仿真实验（如图1.8），在路径最短的优化规则下，能够快速的搜索到最佳路径，为移动机器人路径规划提供了一个有效的方法。表1.4QPSO算法和BQPSO算法进化方程的表达式比较算法算法图1.8a起点为（1，1）终点为（16，16）图1.8b起点为（4，12）终点为（16，16）（4）华中科技大学的付阳光将进化算法（EvolutionaryComputation）领域中种群的繁殖极值（BreedingStrategy）引入QPSO算法，对QPSO算法做了进一步改进，提出一种带繁殖机制的量子粒子群优化算法（HybridQuantum-behavedParitcleSwarmOptimizationwithBreedingStrategy），简称HQPSO。将繁殖策略与QPSO算法结合一方面可以使优秀的基因得以保留，另一方面还可以增加种群的多样性，可以有效的改善QPSO算法中存在的早熟问题。最后将HQPSO算法应用于无人飞行器的三维航迹规划，通过仿真实验比较了HQPSO算法与QPSO算法及PSO算法的性能（如图1.9），结果表明HQPSO算法比其他两种算法具有更强的全局搜索能力和更快的收敛速度。图1.9aPSO算法、QPSO算法和HQPSO算法平均最优适应度的收敛曲线图1.9bPSO算法生成的最优航迹的三维显示及剖面显示图1.9cQPSO算法生成的最优航迹的三维显示及剖面显示图1.9dHQPSO算法生成的最优航迹的三维显示及剖面显示1.5本文研究的主要内容移动机器人在作业运动时必须实现自主的避障与避碰，因此路径规划问题做为一项基本问题已经被广泛的关注和研究。而群体智能算法对于解决路径规划问题有着它独特的优越性，因其模拟群体生物的集体行为，以及其行为为基础表现出智能的特点，可以综合路径规划问题中各个子目标，应用于实际问题中便可使系统达到“最优”所以在路径规划领域有着非常远大的发展前景，其中粒子群算法和两字粒子群算法的产生发展为优化问题提供了便利。研究智能算法在解决实际问题的同时也可以学习了解到最新的科学理论知识。本课题目的是以量子粒子群算法为基础，研究移动机器人环境自适应的自主规划方法，根据已知的环境目标信息，设计适合的量子粒子群算法，实现其全局路径规划。主要研究内容与方法如下：1、QPSO算法的研究与改进在量子粒子群算法中无效粒子对于算法的有很大的影响，会使粒子陷入局部极值而无法到达全局最优，针对这个问题，本文对算法中离子的进化行为进行了深入研究，根据粒子的的有效性与否，将无效的粒子重新初始化使其有效，这样就可以避免算法出现局部最优解的情况。2、对已知的环境目标信息进行全局静态路径规划通过已经掌握的环境目标信息，以运动路径的长度作为优化目标，运用量子粒子群算法在MATLAB工作环境下编写路径规划程序，为移动机器人寻找一条从已知起始点到目标点的优化路径。3、仿真实验验证运行编写的程序，对获取路径的可行性进行验证。1.6论文组织结构第一章为绪论部分，主要介绍移动机器人的路径规划问题及其发展现状并引出群体优化算法的发展过程和理论。引出主要的研究内容：基于量子力群算法的路径规划问题。并阐述了研究的目的和意义。第二章介绍粒子群优化算法和量子粒子群优化算法的详细思想和算法流程，并对二者进行比较。第三章主要介绍移动机器人路径规划问题中使用量子粒子群算法的求解过程。第四章通过仿真结果得出规划路径，并分析结果。第五章总结课题的研究结果和成果，并提出思考和展望。第2章量子行为粒子群优化算法的基本原理2.1引言群体智能是基于环境生物的群体性行为原理，进行设计解决实际问题中最优解问题的，群体智能无疑已成为当今处理最优解问题的主要方法，如今，在世界范围内受到足够的重视。粒子群的优化算法是群体智能的典型代表，利用计算机的迭代计算快速、准确、效率高等特点发展演变而成的[15]。它的应用背景，不仅存在于理论问题的研究中，还在实际工程问题下，有着广泛的应用。从2005年至今一直被“国际演化计算会议（ConferenceofEvolutionaryComputation,CEC）”列为讨论专题之一。随着对群体智能研究的不断深入，人们越来越为它的光明前景投入了大量的精力。在被证明不能保证一定会搜索到全局最优解后，经典粒子群算法便不可以作为仪征全局收敛算法使用，正是由于它存在的这些不足，孙俊教授结合了动力学的知识建立了数学模型，创造了一种量子粒子群优化算法（Quantum-behavedParticleSwarmOptimization,QPSO）算法[16]。这种算法主要思想使在更新粒子时结合了量子物理思想，不依靠速度，根据向量建立方程组，分别利用全局最优化与局部最优化的思想将所建立程求进行求解，这种方法出解决了困扰粒子群优化算法长久以来的因为粒子数量过多导致算法不准确问题。本章最先概述了优化问题并分析解决其必要性和解决方法。通过对基本理论的学习和研究，具体分析适用于本课题的应用方法，并给予原理进行程序编写以及为仿真工作打下良好的基础。2.2优化问题与优化方法优化问题是根据实际问题对工程进行分析应用找出结果最优的情况。在所有的达到目标的问题中找出最好的结果方案作为全局的最优解方案，我们从数学的角度出发进行分析可知，在数学的解方程的问题上，我们通过设定已知条件的列方程对约束条件进行描述进而求出函数最优问题，即函数的极值问题[17]。基于优化方案选择来解决实际问题中的最优解问题可分为以下步骤：（1）信息的采集处理，制定约束条件。（2）对所要解决的实际问题进行信息分类处理工作，方便对约束条件进行设定，建立合适的数学模型，根据以上信息选定合适的变量。（3）对照建立的数学模型选择适当的变量及约束条件进行数学模型的求解操作，为最优解的求解提供良好的基础。（4）根据上一步选定的实际问题解决方法，并依据基本原理进行程序编写工作，通过具有高效率优点的计算机进行方程解的计算。（5）对计算机求得的解进行有效的检验，经过验证符合条件后问题得以解决。通常情况下，优化问题如下式方程所示：或者，其中代表实际问题目标表达式函数，而S代表可行域，则代表存在集合石作为欧几里得范数其中称为最小值，在条件下有，而在都符合要求是就作为其中的最小解加以处理。的全局最小解记做为，或者记为；的全局最大解记作为,或者记为[18]。在计算机技术高速发展的今天，计算机的能力越来越强，以往很多很难甚至不能解决的复杂的优化问题都可以用计算机求解出[20]。运用计算机进行处理优化问题就是在解空间中进行搜索，根据搜索的方法可进行分类，可将这种方法分为以下类别：（1）枚举法：枚举法的思想和策略最简单。就是将空间中的多有解向量优缺点对比，并依据结果来找根据所有可行的结果找出最优解的方法，一次来作为主要解决方法，然而枚举法的计算量要求很大，但其仍然在路径规划中具有很好的效果。（2）直接法：在空间中通过若迭代直接搜索并到最优的解。（3）随机法：通过求解对目标搜索，在过程中实时加以改变，值得注意的是在这一过程中，这个算法的结果是随机的，这样在整个过程中算法进行搜寻的过程是进行局部最优点的选取工作。在本课题中根据分析实际情况采取枚举法，由于解析法用来解决非线性部分，但这种方法的缺点在于这种方法的目标函数是以导数的形式表现出来的，因此具有一阶或二阶的性质，同时在高阶情况下也具有特点，通过数学的基本思想我们可以找到局部的最优解来进行局部最优化问题，要求是将导数设为零时的目标函数的值，这不仅仅有一种极点的形式存在，因此很难用于全局的最优解搜寻解决方法工作。2.3群体智能算法在所有的算法中，群体智能算法出现以来就得到长足的发展，发展至今群体智能算法已经在人工智能、生物、经济等很多领域表现出它强大的实用性，使得成为众多研究。群体是指一组相互之间可以通过直接通信或间接通信从而能够达成合作一堆分布式问题进行求解得主体。为此在不存在集中控制和不提供全局模型的前提下，群体智能能为寻找复杂的分布式问题求解方案提供研究基础和技术支持。群体智能算法分为很多种类，其中最具有代表性得包括粒子群优化算法和量子粒子群算法。粒子群优化算法粒子群算法(ParticleSwarmOptimization,PSO)模拟鸟群的觅食行为[21]。N维搜索空间，粒子群数M,第t次：第i个粒子的当前位置表示为,第i个粒子的当前速度表示为,第i个粒子的最优位置（pbest）, (2-1)全局最优位置,或者(),其中粒子状态的更新公式： (2-2) (2-3),,第次迭代，学习因子影响个体每一次移动到个体最优位置的距离影响粒子移动到全局最优位置的距离，（）区间内彼此独立的分布均匀的随机数序列[23]把粒子更新速度限制在某个区域里以便确定解空间的可能性，即。确认粒子位置。算法的初始化：a给出群体的规模。b对于每一个,在中由均匀分布生成。c对于每一个,在中由均匀分布生成。d对于每一个,令。量子行为粒子群优化算法通过确定粒子位置速度特征确定粒子运动状态，即粒子位置不会产生大幅改变。由于粒子速度有限，粒子位置移动就有限，所以粒子无法达到解空间所有的地方。所以理论上无法做到全局收敛。为此，开发的量子行为粒子群优化算法可以完美的解决这种无法收敛的问题。.1量子力学背景根据经典力学，粒子的运动状态可以依据在某时刻的坐标动量给出准确的定位。而粒子运动状态可以根据牛顿方程进行确定。所以根据粒子的坐标动量可以确定任何时刻的运动状态。微观粒子运动具有波动－粒子二象性（wave-particleduality）。波动性，即波的“相干叠加性”，是波动现象最本质的要素；粒子性，是指微观粒子的“颗粒性”或“原子性”。M.Born，提出的“概率波”（probabilitywave）的概念，是把粒子的“原子性”和波动的“相干叠加性”统一起来的唯一的方法。概率波即波函数的统计诠释，通过计算得到的概率分布，只是对粒子运行结果的一种预期，并非粒子已经具有那样的分布[27]。.2QPSO算法的量子行为通过研究发现，粒子行为具有一定智能，和人类的智能行为有类似性。量子系统也存在不确定性，也和思维的不确定性有相似。所以根据这种相似性，可以建立有效的模型表述这种智能。粒子状态包括位置和速度，但粒子的速度位置却无法被一起确定。为此应用波函数定义粒子运动状态。具体方程如下： （2-4)式（2.4）归一化条件 （2-5)量子束缚态描述： （2-6)概率密度函数为： （2-7)势的特征长度粒子质量普朗克常数。依据蒙特卡洛随机模拟法，确定粒子位置。在区间上去随机数，也就是： （2-8)式（2-8）区间（0,1）均匀分布的随机数，代替式（2-7)中的。从而得到： （2-9) （2-10)用逆变换求出 （2-11)因为，所以可以测量到粒子的精确位置： （2-12)势阱的特征长度如何确定是解决问题的难点。.3QPSO算法的运算过程基本运算流程如下，N维搜索空间，在第时刻时，第个粒子的位置为：个体的最优位置表示为群体的全局最优位置标示为:,且，其中为处于全局最优位置的粒子的下标，。此算法，粒子没有速度向量。在最小化应用中，目标函数的值越小，越理想，具体确定公式如下： （2-13)最优解由式（2-14）和式（2-15）确定： （2-14) （2-15)根据每次的迭代更新，新的最优位置被计算出来，只要根据最优解的适应度和当前位置的适应度进行对比，如果前者好，那么G(t)更新[31]。根据算法定义了平均最优位置（），记为（）。也就是个体最优位置的平均，即： （2-16)粒子i的收敛过程是以为吸引子，其坐标为： （2-17)或者表示为： （2-18)其中 （2-19)如果c1=c2，本（0,1）区间上均匀分布的随机数。粒子的进化方程为： （2-20)其中 （2-21)通过以下公式来评价 （2-22)收缩-扩张系数算是仅有的控制参数。具体步骤步骤：运算初始化，确定粒子位置，将最优位置确定。步骤：计算粒子最优位置。步骤：将粒子群中所有粒子（）,按照算法中步骤47进行运算。步骤：按照算法计算当前粒子的适应度，并将的到得到适应度与上一代的个体最优位置的适应度进行比较得出当前位置的个体最优位置适应度即通过式（2-13）对当前位置的个体最优位置适应度进行更新。步骤：将种群中所有粒子的个体最优位置的适应度与上一时刻的全局最优位置的适应度逐个进行对比，当某一个粒子的个体最优位置的适应度小于上一时刻的全局最优位置的适应度时将全局最有位置更新为该值，如果没有则全局最优位置不变。步骤：通过公式（2-18）进行计算的到一个随机点。步骤：通过公式（2-20）得出粒子的新的位置。步骤：当满足算法终止条件时结束算法，如果不满足则返回步骤2。2.4粒子群优化算法与量子行为粒子群优化算法的比较量子粒子群优化算法相比较传统粒子群优化算法的优点如下[33]：（1）QPSO算法中只需要一个参数，具有参数数量少的特点而且PSO算法根据实际问题进行调参、、起始惯性权重和最大速度，故利用QPSO算法减少在实际问题中参数调节这一环节中的操作，此算法易于程序的编写与实现。（2）QPSO算法相比较传统的PSO算法具有收敛于全局最优点的优点，此算法在全局最优问题和局部最优问题上具有解决的较大优势，使得此算法不容易陷入局部最优点。QPSO算法在全局的规划强，相对在局部问题上效果不理想，通过迭代将全局搜索能力减弱局部搜索能力增强。（3）作为非线性系统，QPSO算法与传统的PSO算法的线性系统的相比，可以描述更多的状态。（4）量子系统中粒子是不存在一个固定的系统，它具有随机性，因此粒子在空间中每一点出现是具有一定的概率，通过不断的迭代可以在当前群体的中选择群体具有更好的适应度值。为比较PSO算法和QPSO算法的性能，分别从以下三个方面测试量子粒子群优化算法介绍其优点：1.函数 （2-23）2.函数 （2-24）3.函数 （2-25）取如下参数进行调整：种群规模大小分别取40和80，最大迭代次数分别取1000、1500和2000，相应的维数取10和20。在粒子群优化算法中，，初始惯性权重值从0.9开始迭代线性递减到0.4。在QPSO中，开始的1.0搜索递减到结束时的0.5。表3-2至表3-4分别记录了三函数运行100次的结果。表3.1测试函数的初始化区间、位置的上限值和速度测试函数初始化区间位置的上限值最大速度（50，100）100100（15，30）100100（-5.12，5.12）600600表3.2函数的寻优结果种群大小维数最大迭代次数PSOQPSO401010003.1e-232.6e-072015004.2e-143.7e-04801010006.2e-288.5e-102015002.7e-171.2e-07表3.3函数的寻优结果种群大小维数最大迭代次数PSOQPSO4010100078.54216.341201500180.25452.2468010100042.57412.43720150085.92430.695表3.4函数的寻优结果种群大小维数最大迭代次数PSOQPSO401010004.1033.49620150015.03710.254801010003.2312.47820150015.6418.904从表3-2至3-4可以看出，QPSO算法比PSO算法具有更好的收敛性能。2.5本章小结本章对课题中所用到的理论与基本思想进行了详细介绍，为接下来运用量子粒子群算法解决路径最优问题提供了强大的理论基础。本章通过对两种理论算法进行对比分析，更加深入透彻地将两种算法进行优缺点分析，为接下来的规划提供理论依据。第3章基于量子粒子群算法的移动机器人路径规划算法设计3.1引言已知基本粒子群优化算法存在一个缺点那就是关于收敛速率大小，这种缺点在量子粒子群优化算法中虽有很大改进，但在量子粒子群优化算法中，粒子容易进入局部最优。在本文中机器人的系统中，需要优化路径，使得机器人在运动中，能够躲避障碍物，达到指定的位置，并且尽量使得路径达到最优。3.2移动机器人路径规划环境空间建模所谓的移动机器人的路径规划问题，就是在环境地图中找到一条连接起点和目的点的不穿过障碍或者碰到障碍的安全路径，这条路径就是就是移动机器人所路过的所有的点的集合[34]。在图3.1中，机器人从s点开始运动到d点的过程中，需要躲避图中的障碍物，在图中实心点是机器人寻优路径。这些点的连接线就是路径优化结果。并且成功躲避障碍物。1.在规划空间中建立平面直角坐标系。2.根据已知信息在图中确定障碍物的大小，坐标位置。3.根据建模的过程，都确定所有P点的横坐标。定义点为，点为路径长度为L：（3-1）最后的优化如上式所示，通过上式确定最优的，进而确定最好的路径信息。图3.1路径规划示意图在已知上述条件的情况下，全局路径规划就是在成功躲避障碍物的前提下，寻找最优的路径。在全局路径规划中，避障的规划是被事先得出的，如果环境中出现了位置的障碍或者出现了动态的变化，全局规划是没有办法解决的，甚至能够使得机器人在运动过程中发生碰撞。全局规划主要包括以下几种方法[36]：（1）栅格法经过上述处理，建立了以单元格为关系连接的连通图。近似的栅格分解法的优点是：由于分解的栅格的形状很规则，因此分解栅格的过程也就比较简单，很容易实现，并且栅格的大小可以根据不同的需求来进行调节，因而具有较强的灵活性和适应性，应用范围也比较广泛。在这种方法中，栅格的大小对路径规划影响很大。图3.2栅格法建模(2)可视图法可视图法是将机器人的质点与目标点进行连线，用障碍物的近似多边形来代替多边形障碍物，然后将所有障碍物的近似多边形的顶点和起始点以及目标点之间用直线组合相连，直线不穿过障碍物，形成一个网图叫做可视图法。如图3.3所示。由于任意两直线的顶点都是可见的，即直线是“可视的”，所以从起始点开始，按照某种原则，沿着这些直线中的某些直线到达目标点，所经过的这些直线的集合便是路径规划的结果，并且这些直线都不穿越障碍物[37]。图3.3可视图法建模（3）拓扑法拓扑法是通过表示环境中所有对象间的拓扑关系来建立环境模型。拓扑法用连通图来描述环境的结构，根据环境和运动物体的几何特点，将规划空间划分成具有若干拓扑特征一致的子空间，接着在拓扑网络的基础上，找到目标的开始的位置和终点的位置，确定最优路径求得最后的路[38]。这种方法的优点是：利用拓扑特征可以大大缩小搜索空间，具有较好的鲁棒性，模型简单，存储空间小，易于改变。缺点是拓扑网络建立的过程不太容易实现，复杂并且需要大量的时间。但是针对一种环境，拓扑网络只需要构建一次，因而在实际应用中能够显示其优越性，可以大大地提高效率。图3.4拓扑图法建模3.2.3环境模型的建立在建立环境模型的过程中，把机器人看做成为一个质点，忽略它的尺寸大小以及回转半径。对障碍物进行处理，将已知的障碍物形状，坐标以及大小加在环境模型中。保持环境模型的参数不变化，建立二维的路径平面图。本课题中环境模型的按照上述要求，使用MATLAB中genHills函数构建环境中的障碍物，根据人工设定的坐标，确定障碍物的位置，而障碍物的大小可以通过改变函数输入的高度来控制。如图3.5所示，为构建的机器人工作环境的简单模型，其中所有障碍物均为圆形，位置确定，以随机生成的矩阵作为障碍物的高度控制障碍物的大小。图3.5实验移动机器人环境模型在上述环境模型的基础上仿照学校内实验室室内环境，以黑板和桌椅作为障碍物，构建模型如图3.6。图3.6根据校园内实验室环境建立的环境模型3.3路径规划的算法设计根据上面已知的模型信息，在本文中采用量子行为粒子群算法优化移动机器人运动路径，最终达到最优路径。本文中的实验方法采用MATLAB作为仿真实验平台，最终达到验证实验效果的目的。在量子粒子群算法中，选取机器人运动路径的长短作为适应度函数，运用优化算法优化其运动轨迹。在本文中，设定粒子的含义使机器人运动轨迹的横纵坐标。在上文中我们选取了量子粒子群算法的适应度函数。适应度函数充分表达了每一个粒子的优劣程度。因此，根据适应度函数的计算值，在众多的粒子中寻找到最优的路径，完成本文的实验仿真。在量子粒子群优化开始之前，必须初始化粒子的位置和初始的飞行速度。粒子种群由个维的粒子组成。分布在可行解空间内。随机在可行的粒子空间中产生设定数量的粒子。根据适应度函数的计算结果，判定粒子的优劣，筛选粒子。在本文中粒子的有效性使根据所随机产生的粒子是否在障碍物内部或者相邻的两个粒子之间的连接线是否横穿障碍物。所以，在程序中很容易判断出粒子是否有效。如图3.7所示。图3.7a粒子位于障碍物内图3.7b相邻元素的连线穿过障碍在本文中使用量子粒子群算法来优化机器人运动轨迹，其具体步骤如下：步骤1：建立上述的环境模型。步骤2：根据量子粒子群算法的要求，设定参数例如群落规模以及粒子维数，并且判定粒子有效性，重新生成粒子。步骤3：计算每个粒子适应度值，根据适应度的值跟新历史最优位置、全局最优位置以及平均最优位置。步骤4：根据粒子的更新公式，更新粒子的位置以及飞行速度，并确定粒子的有效性。步骤5：判断粒子群落是否达到要求的迭代次数或者适应度函数值达到要求的精度，来确定是否结束该算法。步骤6：运行完成优化算法后，得到最有的路径。根据以上的算法描述，设计如下的算法流程。图3.8量子粒子群算法流程图3.4本章小结在本章中重点说明了量子粒子群的原理以及具体运行步骤。这是本课题的关键的算法。详细给出了从建模到最终路径规划的设计过程。第4章移动机器人量子粒子群路径规划仿真实验4.1引言在前文设计思想的基础上为移动机器人编写基于MATLAB环境下的量子粒子群优化算法程序，并运用此程序在前文建立的环境模型中进行仿真，在仿真结果的基础上进行进一步的分析。4.2算法参数寻优在量子粒子群优化算法中有很多影响优化结果的参数，因此在运行量子行为粒子群进行仿真调试之前，本文优先运用试凑法对算法中的一些参数进行了寻优，通过多次仿真实验选取了实验结果比较优的一组参数，后续的所有仿真实验的参数，都是在这组参数的基础上进行的。（1）调节粒子种群的搜索上界及搜索下界实验之初，设置整个搜索种群的规模为30，种群中粒子的维数为8，。将这组参数放置到前文建立的稀疏障碍物环境模型中进行仿真实验，仿真实验结果如图4.1。图4.1移动机器人在稀疏障碍物的环境模型中仿真结果设置整个搜索种群的规模为30，种群中粒子的维数为8，搜索上界以及搜索下界分别为0.7和0.3。将这组参数放置到前文建立的稀疏障碍物环境模型中进行仿真实验，仿真实验结果如图4.2图4.2移动机器人在稀疏障碍物的环境模型中仿真结果以实验结果为基础进行分析比较，以上两个仿真实验在粒子群规模和粒子维数相同的条件下进行，但第二个实验的结果先对较优，因此可以得知，在粒子群规模与粒子维数相同的条件下，。（2）调节粒子群规模与粒子维数40，种群中粒子维数为9。同样将这组参数放置到前文建立的稀疏障碍物环境模型中进行仿真实验，仿真实验结果如图4.3。图4.3移动机器人在稀疏障碍物的环境模型中仿真结果设置整个搜索种群的规模为50，种群中粒子维数为16。同样将这组参数放置到前文建立的稀疏障碍物环境模型中进行仿真实验，仿真实验结果如图4.4。图4.4移动机器人在稀疏障碍物的环境模型中仿真结果通过这组仿真实验的结果，结合上组实验的结果，进行比较分析仿真结果可见，即固定的情况下，提高