基于遗传算法的水下机器人的一种途径规划方法.docx

基于遗传算法的水下机器人的一种途径规划方法0导语：本文主要研究了利用遗传算法实现深海集矿车避障途径规划的方法与途径。【专家点评】：遗传算法是一种借鉴生物界自然选择和进化机制开展起来的高度并行、随机、自适应搜索算法。十分合适于处理传统搜索算法解决不好的复杂的和非线性问题。本论文采用遗传算法对深海集矿车的避障途径进展规划，思路和经过表达明晰。结果通过了计算机仿真测试初步证明了其可行性。应该讲本论文阐述的内容是在自动化领域使用先进控制算法的一次有益和有效的尝试。摘要：本文主要研究了利用遗传算法实现深海集矿车避障途径规划的方法与途径。将连续的途径离散化，并用随机数模拟各途径种群。把二维的途径转化为一维，生成简单的途径基因。提出了物理意义明确的适应度函数和相应的变异算子，进而引导遗传算法快速收敛于最优解。实验仿真说明，该算法可以快速，稳定的搜寻到所需的最正确途径。关键词:挪动机器人，遗传算法,避障途径规划Abstract:Akindofpathplanningmethodbasedongeneticalgorithmformobilerobotwiththeconsiderationoftheobstaclesintheenvironmentisanalyzedandworkedout.Inthispaperthecontinuouspathissimulatedbyscatterpoint,andusestherandomnumbertorepresentthepath.Thepathoftwodimensionsisreducedintoonedimensiontoproducesimplepathgene.Inthemethod,thefitnessfunctioncontainsexplicitphysicmeansandcorrespondingmutationoperatorisprovided,sothatGAcanbeleadtoanoptimizedresultrapidly.Theexperimentshowsthat:thisalgorithmcangetaoptimalpathfastandsteadily.Keyword:MobileRobot,GeneticAlgorithm,PathPlanning;1.引言在深海集矿车的导航控制中,途径规划是一个很关键的问题。深海集矿车途径规划的主要任务是在具有障碍物的环境中,按照一定的评价标准,寻找一条从起始状态到达目的状态的无碰撞途径。一般来讲有许多途径可供集矿车行走,可事实上需要集矿车必须找到一个最优途径,既能避开障碍物，又能以最小的消耗(如时间)返回预定途径。集矿车途径规划是一个困难的非线性问题,传统的寻优策略因复杂而费时1,难以用于集矿车的实时导航。本文提出的途径规划算法,应用简单的遗传编码,并有明确物理意义的适应度函数。通过计算机仿真证明该方法能解决动态环境中的深海集矿车途径规划问题。2.基于遗传算法的深海集矿车途径规划方法2.1途径编码方式怎样将问题的解转换为编码表达的染色体，并利于后续约束条件下的优化操作是遗传算法的关键问题。在遗传算法中，编码串的长度和查找空间对于系统的运行速度是非常重要的2,因此必须设计一种简洁实用的编码技术,才能缩短规划时间，实现实时控制。在现实运动中，途径点是二维的，假如能对途径坐标点进展降维处理，必将大大进步计算速度。本文中，令当前坐标系为XOY,其中原点与起始点重合，X轴位于起始点与目的点的连线上。将连接起点与目的点的线段等分,取等分点Xj(j=1,2,n-2),过Xj点作直线Lj与X轴正交，在每个Lj上随机地选择一点Pj,共得到n-2个点,再令Po,Pn-1分别为起点，终点，如下列图所示：途径编码示意图记各点纵坐标为yi,j,进而形成一条随机途径Rj。这样途径就转化为一维的Y坐标编码。详细编码采用浮点数方式，如下列图所示：图中的yi,o即挪动机器人的当前位置纵坐标,yi,n-1即是机器人的目的点纵坐标,途径就是：2.2适应度函数确实定适应值函数的选取直接影响到遗传算法收敛速度的快慢和算法的成败。结合详细问题的特征,该适应度函数应考虑以下因素：2.2.1途径长度本文的途径长度指标函数定义如下：2.2.2途径的光滑度本文的途径光滑度指标函数定义规划时必须考虑途径光滑性对机器人运动性能的影响。机器人转弯时，角度应尽可能的小，因此要求生成的途径尽可能变化均匀。故途径的转角差累积值(vi)较小的基因较为优越。2.3途径的平安性及相应的惩罚策略在设计平安保障策略前，首先假设障碍物的个数,位置信息已由安装在机器人上的声纳传感器获得。那么惩罚策略的目的是在机器人规划途径与障碍物覆盖范围进展比拟的根底上,形成平安、无碰撞可行途径。一条可行的途径必须保证机器人任何部位都不与障碍物发生碰撞,即机器人与障碍物边缘的间隔必须大于最小平安间隔，即：MiO=0其中：Mi为机器人的某条运动轨迹；O指考虑平安间隔条件时所有障碍物覆盖范围的集合。对于进入障碍物覆盖范围的随机点，如下列图所示：注：图中阴影局部为障碍物范围，Pi,j为随机途径点,P,i,j为该点对应的障碍物边缘点；本文设计了一个罚函数(vi)令：2.2.4适应度函数的选取综合以上几点，可得到适应度函数为：其中,为相应的加权系数。该适应度函数把3个约束条件有机的结合到一起，物理意义明了，计算简单。2.3穿插方法采用算术穿插法产生新的个体。这里将两个染色体中的各元素以如下的方式组合，得到新染色体的相应元素，方法如下：2.4变异操作算子的选择2.4.1修复操作算子：挪动一个点。按照一定的概率，对位于障碍区域内的点重新取值，使其获得避开障碍物的时机。2.4.2优化操作算子：删除一个点。同样，在一定的概率下，假如三个连续点皆在障碍物覆盖范围外部，且首尾点连线的中间点还位于障碍物覆盖范围外部，那么删除中间点。两种变异操作分别如下列图所示：2.5遗传算法操作步骤综上所述，该算法可描绘如下：1.编码：生成一组随机数，以一维数组的形式转化成染色体vi。2.评估及选择：3.以一定的概率，对新种群进展穿插，变异。4.进展遗传迭代操作，经过假设干代的搜索，即可得到一条最正确途径。3.仿真实验本文在VC+6.0环境下进展了仿真，用两个椭圆物体代表障碍物，用遗传算法求得避障途径，效果图如下：注：Po为起点，Pn-1为目的点，障碍物的标记分别为BLOCK1,BLOCK24.结论本文设计了一套基于遗传算法的途径规划的方法，通过适当的适应度函数引导遗传搜索，得到了集矿车避障的最正确途径。仿真实验证明了该方法的稳定性和有效性。它的应用将使深海集矿车具备一定的自主导航、避障的才能，为其智能化研究提供了一条有益的思路。参考文献： 1孙明，孙树栋。遗传算法原理及应用。国防工业出版社,1999:45-47. 2玄光男(日)，程润伟。遗传算法与工程设计。科学出版社,2000:64-66. 3仲欣,吕恬生。基于遗传算法的汽车式挪动机器人途径规划方法。上海交通大学学报，1999年7月。 4Bauer,R.GeneticAlgorithmsandInvestmentStrategies.JohnWileySons,NewYork.1994:102-105.5Allbrecht,R.,C.Reeves,andN.Steele,editors,ArtificialNeuralNetsandGeneticAlgorithms.Springer-Verlag,NewYork,1993:88-91.