多目标优化在路径优化中的应用

第31卷第4期计算机仿真2014年4月文章编号:1006 -9348(2014)04 -0364 -05多目标优化在路径优化中的应用梁静',宋慧',瞿博阳2(1.郑州大学电气工程学院,河南郑州450001 ;2.中原工学院电子信息学院,河南郑州450007)摘要:在移动机器人路径规划问题的研究中,路径规划的实质是机器人按照- -定的技术指标找到一条从起 点到终点与障碍物无碰擅的最短路径。由于路径长度和安全性指标是相互矛盾的两个技术指标,大多数现存算法在把它们作为单目标优化时容易陷人局部最优,用多目标优化中的帕累托最优则能够很好地平衡和解决这两个目标不同资源分配下的组合情况。用贝塞尔曲线来描述路径,用帕累托最优解决路径长度和安全性指标之间的共存问题。实验结果表明,比起单目标处理,多目标优化在解决路径优化问题中路径长度及安全性指标时较稳定,能够找到满足条件的更短路径，并且帕累托最优能够很好地解决不兼容目标之间的共存问题,找到不同安全性指标下优化最短路径。关键词:贝塞尔曲线;多目标优化;帕累托最优中图分类号:TP18文献标识码:AApplication of Multi - objective Optimizer in Path PlanningLIANG Jing'，SONG Hui' ,QU Bo - yang2(1. School of Electrical Engineering, Zhengzhou University , Zhengzhou Henan 450001 , China;2. School of Electric and Information Engineering, Zhongyuan University of Technology,Zhengzhou Henan 450007 , China)ABSTRACT :The essence of robotic path planning is to fnd a cllision - free path from the start location to the targetlocation in an environment with obstacles which satisfy certain optimum criteria. Criteria of path length and securityare contradictory isues in path planning problem, most existing algorithms regard it as a single objective problem andare easily to be trapped into local optima while Pareto optimality in multi - objective optimizer can balance and solvethe combination well under different resource assigned of two goals. In the paper, Bezier curve was used to describepath in this task, and Pareto optimality was utilized to solve the coexistence of path length and security. The resultshows that compared with single - objective optimizer, the multi - objective optimizer is more stable in achieving thecriteria of path length and security and can find the shortest path which satisfies certain conditions. The Pareto opti-mality can effectively solve the coexistence problem of incompatible objectives and find the shortest path under differ-ent safety criteria.KEYWORDS: Bezier curve; Muti - objective optimizer; Pareto optimality最短,机器人消耗能量最低,花费时间最少,安全性及路径光1引言滑度等技术指标"。但是这些指标在作为单目标优化处理路径规划在移动机器人导航中占有很重要的位置,表现时容易陷局部最优,因此路径优化问题通常被当作很难发现为机器人按某--性能指标找到--条从起点到终点的和障碍最优解的具有多个目标的NP完全问题(2] ,即大多采用多目物无接触最优或者接近最优路径。路径问题通常涉及路径标优化来进行处理。与单目标优化问题不同,多目标优化向题的目标函数是大于等于二的,大多数专家学者用保持非支基金项目:国家自然科学基金项目(60905039) ;中国博士后科学基金配解集,同时将种群朝着非支配解集移动并最终收敛于帕累特别资助项目(2012750639);教育部高等学校博士学科点专项科研托曲面的中国煤化工基金( 2010000 ;河南省科技攻关项目(132102210521)本文中CNMH G'题，需要优化的目标收稿日期:2013 -07-26修回日期:2013-08 -05是路径长度相女王比伯你，很亚然，这是两个相互矛盾的概一364一念,这两个指标是不能同时满足的,那么就需要- - 些方法来其中，u∈[0,1],PO、P分别表示起点和终点,i表示产生路满足不同使用者的需求。多目标优化能够实现同时对多个径的曲线段。目标的优化,并对这些目标进行协调，设计者选择的算法每安全性指标指的是机器人要实现和障碍物之间无碰撞。运行一次都会产生一组Pareto 最优解,使用者可以根据自己用圆来表示障碍物,那么圆的半径就是用来评价安全性指标对优化指标的要求来选择合适的解。的重要因素,用R表示。用d,表示曲线上的点与障碍物j之从20世纪70年代中期,机器人路径规划问题就以多种间的最短距离,安全性指标的求解如下:形式被研究。传统的一些方法如图搜索法,人工势场法,栅forj=1:k格法等由于搜索效率比较低而逐渐被淘汰,遗传算法、蚁群fori=2:(L-1)算法、免疫算法、神经网络等智能算法得到了一些改进而被dis(i-1) = sqr(sum((P,(i)应用到路径优化中[41。- circle(j,1))~2 +例如裴振奎等提出了改变变异操作提高差分算法在优(P,(i) -circle(j,2))2));化多目标VRP问题(优化目标:路径长度和客户所需货物重end物的车辆)中的应用'5] ,申晓宁等用引用了删除,修复和平滑d(j) = min(dis-R)算子提高了多目标路径优化(优化目标:路径长度,路径安全性和平滑性)中遗传算法的搜索效率低并防止出现早熟现fy= - min(d)(2)象[6] ,王振华等采用增强全局搜索能力的改进蚁群算法解决其中,K表示障碍物的个数,circle表示障碍物的圆心坐标，了多目标无人机路径规划(优化目标:路径长度和无人机选P.P,表示曲线上每个点的坐标,L = length(P.)表示曲线上择该路径时所受到的威胁强度)问题[7] , Masehian等提出了用改进粒子群优化算法解决多目标路径优化(优化目标:最点的个数fw表示安全性指标,可以看出,当机器人为安全短路径和路径光滑性)问题[8] ,这些研究者及其它- -些没有情况下行驶,其值为负值;当机器人与障碍物相撞情况下,其提到的等在多目标路径规划中都做出了自己的成就，但由于值为正值。各个研究者在研究路径问题时设置的场景、障碍物的方式或路径规划描述的是在起点和终点已知的情况下,找到- -者用帕累托最优表示的目标不同,因此无法对不同研究者进个从起点到终点的和障碍物无碰撞的路径。用fmnmn 描述路行对比。径长度,表示方式如下: .本文采用克服了传统粒子群优化算法易于收敛和早熟fmgu=sum(sqr((P.(2:L) -P,(1:L-1))). ^2+(P,现象缺点的动态多组群粒子群优化算法,结合本文中要用到(2:L) -P,(1:L-1))).2))(3)的多目标优化思想来解决路径优化问题(多目标动态多组群2.2约束处理粒子群优化算法,简称MO - DMS- PS0)。同时,用三次在优化计算领域,很多问题被一些因素( 例如:物理,地Bezier 曲线来描述路径,对技术指标路径长度和安全性进行理等其它限制条件)所约束着。- -般情况下,这类问题可以优化。实验结果表明:动态多组群粒子群优化算法能够很好归纳如下":的解决路径优化问题, Pareto最优能够很好的表示相互矛盾最小化的目标之间的共存关系能够在不同组合的优化指标下寻求f(x),x= [x,*..*n](4)与障碍物无碰撞的最优路线。满足h,(x)≤0,i = 1,.,.,p;2问题描述(5)2.1技术指标g;(x) =0,j =p+1,"",m在机器人路径规划中,技术指标(路径最短、安全性、时其中x∈[xmn,x..]" ,p是不等式约束的个数,(m-p)是等间最短路径光滑性等)是- - 个非常重要的评价因素。接下式约束的个数,为了简化问题，所有的等式约束均可以转化来要讨论的技术性指标是安全性和最短路径指标，依然采用为如下不等式约東:Beier曲线911(]来描述路径,曲线的参数方程为:|g;(x)|-s≤0(6)(P。(1-u)3 +3P"u(1-u)2+其中8是允许的误差,然后所有的约束问题就可以被定3Pu2(1-u) +Pju',i=1义为:P(u) =.P5~'(1-u)3 +3(2P5-1 -P:-')u(1-u)2 +f(x),x= [*1.*](7)3P%u2(1-u) +PJu2,1e3.1动态多组群粒子群优化算法fne(x) >&nwe(x) > e&fne(x.)