为了实现微型足球机器人的平滑最优路径规划，提出了一种结合Ferguson样条路径描述和改进粒子群优化算法的路径规划方法。利用Ferguson样条描述移动机器人路径，将路径规划问题转化为三次样条曲线的参数优化问题，借助改进的具有速度变异的粒子群算法进行路径优化。仿真实验表明，算法可以有效进行障碍环境下机器人的无碰撞路径规划，改进的粒子群算法进行路径优化迭代80次左右即可收敛，规划路径平滑、合理，有一定的实用价值。
2422012,48(15) Computer Engineering and Applications计算机工程与应用 行,粒子群逐渐聚集到最优点。 2nd spline 13改进的粒子群优化算法 P2P2P2… Pa IPmIpp 在标准的粒子群优化算法中,若粒子的速度 v!()=(vn,V2,…,V)中的任一分量v小于-Vm或 I st spline 图1粒子构成 大于V、,则将其分别设置为-V或V。显然, 的安全性、最短性和易行性。由于采用 Ferguson样条 这种策略限制了大速度“兴奋”粒子的随机寻优能描述的路径具有连续的一阶导数保证了路径的易行 力,从而导致了标准粒子群优化算法进化曲线初期性,所以本文的最优准则应主要考虑安全性和最短性 下降缓慢。一方面,这种“一刀切”的策略可能导致 (1)规划的路径要尽量短,即样条的总长度应该 大量粒子因速度过大而超出寻优边界甚至可能在越小越好。最短性惩罚函数与路径的长度应成反 寻优边界内形成大幅度的“震荡”,这种现象在进化比。定义如下最短性惩罚函数。 初期更为明显。另一方面,这种“一刀切”的策略对 大速度“兴奋”粒子的随机寻优能力也是一种浪费。 f (11) 基丁以上分析,引入“兴奋”粒子速度随机赋值其中,l-为当前点到目标点的欧氏距离。l是轨线 的策略改善以上不足。当粒子速度绝对值大于速的长度,由下式计算 度分量的设定阈值时,在[Vmx,Vm-之间随机赋 (x)3(0)d (12) 值。在群进化初期,由于存在大量的大速度粒子,对 大速度粒子的速度随机平均分布可以充分发挥大速 (2)规划的路径必须是安全的,即粒子样条与障 度粒子初期的随机寻优能力。群进化后期,算法进碍物不能相交且应有一定的安全距离。为此,安全 入收敛阶段,大速度粒子的数量迅速减少。随机赋 性惩罚函数应体现:路径与所有障碍物之间最小距 值策略一方面可以使部分粒了通过随机赋值得到较 离d-n小于设定的安仝距离Da时,要进行惩罚,且 小的速度而具备跳出局部极优的能力,另一方面可惩罚函数为最小距离的减函数;路径与所有障碍物 中以使部分粒子通过随机赋值得到较大的速度而具备之间最小距离dm大于设定的安全距离Dm时,主 跳出局部极优的能力。可见, VMPSO算法兼顾了收要考虑路径的最短性,安全性惩罚函数应与dm 敛速度和全局收敛能力。 D的值连续以保证最终构造的适应度函数全局最 14粒子描述 小的惟一性。定义如下安全性惩罚函数 >D 利用 ferguson样条描述路径后,移动机器人路径 min 规划问题可以看做是在 Ferguson样条空间中搜索最 f2=10m+1 0<dmn≤Dae 优样条。 由公式(1)可知,二维空间中的 Ferguson样条可 D为反映障碍物影响的常数,由于本文针对Miro 以表示为: Sot机器人足球系统建模,障碍物的半径约为60,因 r(=(x()y()=a+at+a2+a12 (9)此取D>60。为了防止出现除数为0的情况,分式 的分子分母同时加1。dm-n为轨线与障碍物之间的 其中 最小距离,由下式计算: a=2P-2P,+Pt a,=-3P+3P,-2P-P m= min min(0o7)+(x())(14) (10) 上式中,x(O).y()由公式(9)确定,O为机器人空间的 所有障碍物的集合。 每个样条由点PP1与向量P。P1所决定。根 综上所述,本文 VMPSO算法适应度函数定义为: 据公式(5),每两个相邻的样条共用一个端点与相应 f=fi t af (15) 的切向量。假设一条二维路径轨线由n个 Ferguson其中,a为权值系数,用来调整最短性和安全性在路 样条连接而成,那么,整个轨线由4(n+1)个参量决径规划中所占的权重,本文取a=1。 定。用来进行优化的粒子结构如图1所示。 15适应度函数 2实验结果与分析 构造良好的评价函数对进化算法非常重要。根21 VMPSO算法性能测试 据路径规划的实际需求,最优准则应综合考虑路径 本文采用3个标准测试函数 Rastrigrin、 Griewank 王娟,吴宪祥,郭宝龙:基于改进粒子群优化算法的移动机器人路径规划 2012,48(15)243 利 Rosen brock,利用 Matlab6.5编程对改进的粒子群 优化算法进行了性能测试实验。实验参数如下:粒 子群人口数为30,c1=2,C2=2,3mn=0.95, 0.4,最大迭代次数为2000,“兴在”粒子速度阈值取 0.5m,每个测试函数运行50次取平均值,表1给出 (a)初始粒子群 (b)进化20代后的粒子群 了三个测试函数的参数设置,表2给出了50次实验 进化200代后最优解的平均值、达到容许误差的平 均迭代次数和优化成功率。从表2可以看出,本文算 法在优化精度、进化速度和成功率等方面均优于标 准的PSO算法。 表1测试两数参数设置 (c)进化40代后的粒子群(d)进化60代后的粒子群 函数名称取值范围维数容许误差 Rastrigrin [-5.12, 5.12 30 Griewank[-600,600 0.1 Rosenbrock [-30, 301 30 100 表2实验结果比较 (e)进化80代后的粒子群(f)进化100代后的粒子群 标准PSO VMPSO 函数名称平均最平均迭成功率平均最平均迭成功率 图2常规测试群进化过程 优解代次数(%)优解代次数/(%) (粗黑线表示当前代最优粒子) 46.55108010036.341008 Griewank 0.0137 1 325 1000.01211268 100 Rosenbrock 344.02 1 761 46 192.241589 2, VMPSO路径规划实验 利用 Matlab6.5编程对本文路径规划算法进行 (a)初始粒子群 (b)进化20代后的粒子群 了仿真实验。建模参考 Mirosot大型组比赛环境。实 验屮,ⅤMPSO参数Vmx=2000,Vnm=0,m3an 0.9,aand=0.2,最大进化代数为100,群人.20 D=120。设计了两组实验—常规测试、狭缝测 试。其中,常规测试实验用来验证本文提出的基于 VMPSO三次样条优化的路径规划算法的有效性和 (c)进化40代后的粒子群(d)进化60代后的粒子群 合理性。狭缝测试实验主要用来验证算法克服局部 极小的能力。 图2给出了利用 VMPSO进行常规路径规划的进 化过程。 图3给出了利用ⅴMPSO进行狭缝路径规划的进 (e)进化80代后的粒子群(f)进化100代后的粒子群 化过程。 图3狭缝测试群进化过程 通过以上两组实验可以看出,本文提出的基于 (粗黑线表示当前代最优粒子) MPSO的移动机器人路径规划算法综合考虑了路 结合图4给出的收敛曲线和图2的进化过程可 径的可行性、最短性和安全性,利用 VMPSO优化100以看出,本文算法在路径规划中只需经过80次左右 代后,路径均能达到最优,规划的路径平滑,且有效迭代即可收敛到最优路径,而文献[算法进化100 改善了早熟收敛问题。 代后仍未达到本文算法的收敛精度。 23与其他算法比较 图4给出了本文算法和文献[算法常规测试收3结束语 敛曲线的比较 提出一种结合三次 Ferguson样条和改进的粒子 2442012,48(15) Computer Engineering and Applications计算机工程与应用 2.8 [4 Kennedy J, Eberhart R C Particle swarm optimization[c]! 2. 文献[0算法 本文算法 Proceedings of the IEEE International Conference on Neu 65 ral Networks. Piscataway, New Jersey: IEEE, 1995: 1942-1948 [5]秦元庆,孙德宝基于粒子群算法的移动机器人路径规划叮 2.4 机器人,2004,26(3):222225 2.3 [6]孙波,陈卫东,席裕庚基于粒子群优化算法的移动机器人 2.2 全局路径规划[控制与决策,2005,20(9):1052-1055 [7 Qin Y Q, Sun D B, Li M. Path planning for mobile ro 0102030405060708090100 bot using the particle swarm optimization with mutation 迭代次数 operator[C]/Proc of Int Conf on Machine Learning and 囹4本文算法与文献[]0常规测试收敛曲线比较 Cybernetics, Perth, Australia, 2004: 2473-2478 群优化算法的移动机器人路径规划方法。由于Ferˉ[8]蔡晓慧,李艳君.基于PSO和滚动优化的不确定环境下移动 guson样条具有连续一二阶导数,其描述的路径平滑 机器人动态路径规划门科技通报,2008,24(2):260265 适于机器人运动控制。利用三次 ferguson样条描述91 Chen Xin, Li Yangmin Smooth path planning of a no 机器人路径,将路径规划问题转化为一次样条的参 bile robot using stochastic particle swarm optimization[c]/! 数优化问题。提出具有速度变异的粒子群优化算法 Proc of the ieee International Conference on mecha (MPSO)改善早熟收敛问题,并利用ⅴMPSO对样 tronics and Automation, Luoyang, China, 2006: 1722-1726 条参数进行优化。采用标准测试函数实验和路径规0吴宪祥,郭宝龙基于粒子群三次样条优化的移动机器人 路径规划算法[机器人,2009,31(6):556-560. 划测试实验对算法进行了验证,取得了理想的结果,11saka.M, Macas M, Preucil L. Robot path planning us 表明本文算法是一种有效的路径规划方案。将本文 ing particle swarm optimization of Ferguson splines[c]! 提出的路径规划方法拓展到动态障碍物环境是下一 ETFA 2006 Proceedings. Piscataway: IEEE, 2006: 833-839 步的研究重点。 [12 Ye J, Qu R Fairing of parametric cubic splines[J]. Math ematical and Computer Modelling, 1999,30(5): 121-131. 参考文献: [13 Eberhart R C, Shi Y Comparing inertia weights and con [1]刘华军,杨静宇移动机器人运动规划研究综述[J中国工 striction factors in Particle Swarm Optimization[c/Pro- 程科学,2006,8(1):85-94 ceedings of the Congress on Evolutionary Computating [2]陈雄,赵一路.一种改进的机器人路径规划的蚁群算法[J San Diego, CA: IEEE, 2000: 84-88 控制理论与应用,2010,27(6):821-825 [14] Clerc M, Kennedy J. The particle swarm--explosion, sla [3] Liu Yanfei Robot path planning based on genetic algo bility and convergence in a multidimensional complex rithms with two-layer encoding[J] Control Theory and Ap space]. IEEE Transactions on Evolutionary Computa- plications,2000,17(3);429432 tion,2002,6(1):58-73 (上接194页 η]成媛媛,满家巨,全惠云基于自适应遗传算法的点云曲线 [3 Huang Jianbing, Meng Chia-Hsiang. automatic data seg- 重建J中国图象图形学报,2006,11(9):1293-1298 mentation for geometric feature extraction from unorga- [8] Jun Y, Raja V, Park SGeometric feature recognition for nized 3-D coordinate points J]IEEE Transactions on Ro- reverse engineering using neural networks[!].Intermational botics and Automation, 2001, 17(3): 268-279 Journal of Advanced Manufacturing Technology, 2001,17 [4] Kos G, Martin RR, Tamas V Methods to recover con (6):462-470 stant radius rolling ball blends in reverse engineering.[9]肖少拥,金小刚,石文俊,等一种基于正交神经网络的曲 Computer Aided Geometric Deign, 2000, 17(2): 127-160 线重建方法[J中国图象图形学报,2000,5(1):62-65 5]柯映林,王青反求工程中的点云切片算法研究[计算机[10]王宏涛基于散乱数据点集的B样条曲面重建门中国图 辅助设计与图形学学报,2005,17(8):1798-1802 象图形学报,2007,12(2):349-355 [6]柯映林,李岸点云数据中拉伸面特征的提取[计算机辅1]飞,三次B样条反算的种简便算法门北京邮电大学 助设计与图形学学报,205,17(6):1329-1334 学报,1996,19(3):82-88