基于B样条路径的机器人时间最优轨迹规划_钱东海 1998.pdf
第 32 卷 第 12 期1998 年12 月上海交通大学学报JOURNAL OF SHANGHAI JIAOTONG U NIVERSITYVol.32 No.12Dec.1998收稿日期:1998-05-10*863 网点基金(863-512-20-04)和中日合作基金资助项目钱东海:男,1971 年生,博士生.邮编:200030基于 B 样条路径的机器人时间最优轨迹规划*钱东海,谭伟,赵锡芳(上海交通大学机器人研究所)摘要现代制造业要求机器人不仅能够实现常规的 PTP 运动和简单的 CP 运动,而且还能够沿着任意特定路径进行高速运动.为此,对沿着特定路径运动的机器人的时间最优轨迹规划问题作深入研究,成功地运用了三次 B 样条对由一系列离散路径点组成的机器人特定路径进行了逼近,并利用动态规划方法,沿着逼近所得的机器人路径,对机器人进行了时间最优轨迹规划,从而保证机器人在不偏离原有路径的基础上,实现时间最优运动.通过计算机仿真实验,证明算法可行,效率较高.关键词机器人;轨迹规划;时间最优;动态规划;B 样条中图法分类号T P 241;T P 242Time Optimum Trajectory Planning for RobotsBased on B-Spline PathQian Donghai,Tan Wei,Zhao X if angResearch Institute of Robotics,Shanghai Jiaotong University,ChinaAbstractIn modern manufacturing,robots should not only be capable of moving in conventionalPT P manner and simple CP manner,but also be capable of moving along a specified path of arbitraryshape at high velocity.T o satisfy such demand,a profound research about the time optimum trajecto-ry planning of robots along a specified path is carried out in this paper.The specified path is assumedto be composed of a series of discrete path points,and the whole time optimum trajectory planning isdecomposed into two steps.First,cube B-spline is employed to approach these discrete path points.Then,dynamic programming method is employed to generate a time optimum trajectory along the B-spline path.With the algorithm,the robot is guaranteed to move in an optimal manner and not deviatefrom its original path.The algorithm has been proved to be feasible and effective by the simulations.Key wordsrobot;trajectory planning;time optimum;dynamic programming;B-spline由于机器人控制中的非线性和强耦合,故机器人控制通常分两级进行,即机器人运动规划和机器人伺服跟踪.机器人运动规划通常又可分为路径规划和轨迹规划上下两级:路径规划用于在机器人操作空间或关节空间中产生一无碰撞的几何路径;轨迹规划用于产生机器人沿着该几何路径运动至各点处的时间序列.机器人伺服跟踪用于实现机器人各关节精确而实时地对规划出的轨迹进行伺服跟踪.目前,绝大多数机器人控制中,通常只能实现 PT P 运动和种类有限的 CP 运动(如直线运动和圆弧运动).但随着高性能机器的逐步应用及作业复杂程度的增加,更要求机器人能够沿着任意特定路径进行高速运动.目前部分学者对沿着特定路径运动的机器人时间最优控制问题进行了比较深入的研究.Bobrow和 Shin 等 1,2利用机器人操作臂的动力学方程,建立了考虑机器人动力学特性的时间最优轨迹规划算法.但通常在机器人控制中,因动力学方程求解过程中计算量大,以及动力学方程参数难以精确确定使得上述算法很难应用于实际工作.故在本文的算法中,假定机器人各关节具有确定的极限上限加速度和极限上限速度(通常这些数据可通过实验取得),同时假定机器人已通过路径规划 3,在机器人的关节空间中形成一无碰撞的运动路径,并依据常规假定该路径由关节空间中的一系列离散路径点构成.本文所要解决的问题是:沿着该离散路径点组成的几何路径,在满足各关节速度、加速度约束的条件下,实现机器人的时间最优轨迹规划.1利用 B 样条进行路径逼近假定机器人具有 m 个自由度,即机器人关节空间为一 m 维空间,同时假定机器人路径由该 m 维空间中的 n 个离散点Qj=(H1j,H2j,Hmj)T,j=1,2,n 所组成,其中 H1j,H2j,Hmj表示机器人在 Qj点时的m 个关节的关节值.为保证机器人高速度运动时平稳无冲击,需对规划出的离散路径进行插值或逼近,通常可采用三次样条 4进行插值,但三次样条要求样条曲线严格通过每一个插值点.当规划出的离散路径点分布参差不齐时,机器人难以实现高速运动,故选用三次 B 样条对离散路径点进行逼近.为保证所得 B 样条曲线起始于 Q1点,终止于 Qn点,在 Q1点前和 Qn点后各新增两个节点 Q1、Q2、Qn+3、Qn+4,同时将原有节点下标编号加 2,并取新增节点的值分别为:Q1=Q3,Q2=Q3,Qn+3=Qn+2,Qn+4=Qn+2,即新增节点分别和原有 Q1、Qn重合.故逼近后的机器人路径由 n+1 段三次 B 样条曲线组成,各段 B 样条曲线可表示为 5Qj(s)=4i=1N 4i(s)Qj+i-1j=1,2,n+1,0 s 1其 中:N 41(s)=(-s3+3s2-3s+1)/6,N 42(s)=(3s3-6s2+4)/6,N 43(s)=(-3s3+3s2+3s+1)/6,N 44(s)=s3/6.当利用 B 样条 Qj(s)表示机器人路径后,机器人的位姿则由B 样条曲线Qj(s)中的伪距离s 唯一确定,故对机器人进行的时间最优轨迹规划就转化为对伪距离 s 进行速度和加速度规划.因机器人各关节具有极限上限速度 Ximax和极限上限加速度 Eimax约束,i=1,2,m,故在对伪距离 s 进行速度和加速度规划时,需将关节空间中的 Ximax、Eimax约束(i=1,2,m)转换为对伪距离 s 速度和加速度的约束.样条曲线 Qj(s)对时间 t 的速度和加速度可通过伪距离 s 表示,即dQj(s)/dt=dQj(s)/ds ds/dt(1)d2Qj(s)/dt2=d2Qj(s)/ds2(ds/dt)2+dQj(s)/ds d2s/dt2(2)对 于确定的第 j 段 B 样条曲线 Qj(s),其上任一点 s 处,dQj(s)/ds 具有确定的数值 dH1j(s)/ds,dH2j(s)/ds,dHmj(s)/dsT,d2Qj(s)/ds2具有确定的数值 d2H1j(s)/ds2,d2H2j(s)/ds2,d2Hmj(s)/ds2T,故当dQj(s)/dt取极限上限速度(X1max,X2max,Xmmax)T,d2Qj(s)/dt2取极限上限加速度(E1max,E2max,Emmax)T时,可分别从式(1)和(2)推得 s 的极限上下限伪速度和伪加速度分别为smax=mini=1,2,mXimax/dHij(s)/ds,smin=0smax=mini=1,2,mEimax-d2Hij(s)/ds2(s)2dHij(s)/ds,smin=maxi=1,2,m-Eimax-d2Hij(s)/ds2(s)2dHij(s)/ds(3)(4)式中,min()、max()分别表示对括号内的 m 个值取其中极小值和极大值.从式(3)和(4)可以看出,除smin=0 外,smax是s 的函数,而 smin、smax是 s 和 s的函数,故关节空间中恒定的速度、加速度约束转化为s和 s约束时成为时变的量.2利用动态规划法进行时间最优轨迹规划当利用 B 样条对离散路径点进行了逼近,并且沿着 B 样条路径求得了 s 的速度、加速度约束后,则可进行时间最优轨迹规划.由于 s和 s约束较为复杂,很难运用极大值或极小值原理求解,故采用图搜30上海交通大学学报第32 卷索的方法求解,本文采用动态规划方法.具有m 个自由度的机器人进行时间最优轨迹规划时,共用 m 个变量,分别表示 m 个关节的角度.由于动态规划法计算量较大,当 m 也较大时,利用动态规划法进行时间最优轨迹规划也就不太现实.在本算法中,轨迹规划是沿着已规划好的 B 样条路径进行的,故具有 m个变量的时间最优轨迹规划问题已经退化为具有一个变量 s的时间最优轨迹规划问题,利用动态规划方法进行时间最优轨迹规划也就成为可能了.为进行动态规划,按下述 4 个步骤进行:(1)对应于 n+1 段三次 B 样条曲线,将各段 B 样条曲线分割成 u 小段,并取各小段的分割点为 s从 01 的 u 等分点,从而整个机器人路径共有 u(n+1)个曲线段组成.对应于每一个等分点,依据式(3)可求得机器人在该等分点处的 sj,kmax和 sj,kmin,其中 j=1,2,n+1;k=1,2,u.(2)对应于上述所得的u(n+1)个离散点,在各离散点处,自 sj,kmin至 sj,kmax,将 s等分成v 段,共得v+1个等分点.对应于每一个等分点,依据式(4)计算机器人在该点处的 sj,k,lmax和 sj,k,lmin(j=1,2,n+1;k=1,2,u;l=0;1,v).取 s 递增的方向为 x 轴,s递增的方向为 y 轴,建立机器人的 ss 二维有向搜索图.因 s 被 u(n+1)等分,而 s被 v 等分,故 ss 二维有向搜索图上共有u(n+1)(v+1)个节点.(3)定义 pj,k,l表示 ss 二维有向搜索图上第 j 段 B 样条曲线第 k 个等分点处,伪速度方向第 l 个等分点处的节点(j=1,2,n+1;k=1,2,u;l=0,1,v).定义 pj1,k1,l1、pj 2,k2,l2表示伪距离方向上两个相邻节点.当 k1 为所在 B 样条曲线段上最后一个等分点时,有 j 1=j 2-1,k1=u,k2=0;否则,j 1=j 2,k1=k2-1.对于给定的节点 pj 1,k1,l1,机器人在该节点处的伪速度为sj1,k1,l1=(sj 1,k1max-sj 1,k1min)l1/v+sj 1,k1min(5)式中 sj 1,k1max、sj 1,k1min表示第 j1 段 B 样条曲线上第 k1 个等分点处机器人的极限上、下伪速度,可由式(3)求得.对于给定的两相邻节点 pj1,k1,l1、pj 2,k2,l2,假定机器人在两相邻节点之间具有恒定的 sj1,k1,l1-j 2,k2,l2,则sj 1,k1,l1-j2,k2,l2=(sj 1,k1,l1)2-(sj2,k2,l2)2/2(sj 1,k1,l1-sj 2,k2,l2)(6)式中机器人在节点 pj1,k1,l1处的伪位移 sj 1,k1,l1=j 1+k1/u.在求得各节点处的 sj1,k1,l1后,则可建立相邻两节点间的代价函数 5j 1,k1,l1-j 2,k2,l2和各节点至终节点的总代价函数 Jj1,k1,l1.定义两相邻节点 pj 1,k1,l1、pj 2,k2,l2间的5j 1,k1,l1-j2,k2,l2为机器人自节点 pj 1,k1,l 1运动至节点 pj2,k2,l2所要用的时间,其数学表达式为:5j 1,k1,l1-j2,k2,l2=2(sj1,k1,l1-sj2,k2,l2)/(sj1,k1,l1+sj 2,k2,l2).定义节点 pj 1,k1,l 1的 Jj 1,k1,l1为机器人在满足伪速度约束和伪加速度约束条件下,自节点 pj 1,k1,l1运动至终节点时,所需的最短时间.(4)在求得 ss 二维有向搜索图上所有相邻节点间的 5j1,k1,l1-j 2,k2,l2后,就可自机器人终节点开始,沿着 s 递减的方向逐层求解各节点的总代价函数.假定机器人在第 j2 段 B 样条曲线上的第 k2 等分点处的v 个节点 pj 2,k2,l 2(l2=0,1,v)的总代价函数Jj2,k2,l2已分别求得,并假定pj1,k1,l1为pj2,k2,l2在 s 递减方向上的邻接节点,则节点 pj 1,k1,l1的 Jj1,k1,l1可按 Jj 1,k1,l1=minl28(5j 1,k1,l1-j 2,k2,l2+Jj2,k2,l2)求得,其中 8 为满足伪加速度约束的节点的集合:8=pj2,k2,l2 sj1,k1,l1min sj1,k1,l1-j2,k2,l2,sj 1,k1,l1-j2,k2,l2 sj 1,k1,l1max,l2=0,1,u自节点 p0,0,0开始,依次连接生成总代价函数 J0,0,0时经过的中间节点,直至终点节点,则可求得构成机器人时间最优轨迹的伪速度和伪加速度序列,利用式(1)和(2)则可求得机器人在关节空间中的时间最优轨迹.3算法仿真为简化算法,在本仿真实例中,假定机器人为一具有两个转动关节的 2自由度机器人,如图 1 所示.31第 12 期钱东海,等:基于 B 样条路径的机器人时间最优轨迹规划同时假定机器人已通过路径规划,在关节空间中形成一以离散路径点 Q1、Q2、Q10表示的机器人路径.利用三次 B 样条对 Q1、Q2、Q10进行逼近,可得图 2所示的 B 样条路径.因起始和终止节点前后各新增了 2 个节点,故该路径共由 11 段三次 B 样条曲线组成.图 1两自由度机器人Fig.1Robot of two degrees of freedom图 2利用 B 样条对离散路径点进行逼近Fig.2Approaching the discrete path pointswith B spline假定机器人关节 1、2 极限上限角速度分别为 8.7 rad/s 和 14 rad/s,极限上限角加速度分别为 87rad/s2和 140 rad/s2.利用上述动态规划法沿着图 2 所示的 B 样条路径进行时间最优轨迹规划,可得时间最优轨迹的伪速度曲线,如图 3 所示.因该曲线由图 2 中 11 段三次 B 样条曲线形成,故 s 的总长为11.相应可得伪加速度曲线如图 4 所示.图 3伪速度曲线图Fig.3Curve graph of pseudo-speed图 4伪加速度曲线图Fig.4Curve graph of pseudo-acceleration对应于图 3、4 中的伪速度曲线和伪加速度曲线,关节 1、2 的角速度、角加速度曲线分别如图 5、6 所示.从图中可以看出,机器人时间最优运动共用了 0.671 s.这比机器人在相同的关节速度、加速度约束下,沿 Q1Q4、Q4Q7、Q7Q10三段折线,做 CP 运动时所花费的时间(0.774 s)要短.图 5关节 1、2 角速度随时间变化规律 Fig.5Joint 1 and 2s angle velocity changingwith time图 6关节 1、2 角加速度随时间变化规律 Fig.6Joint 1 and 2s angle acceleration changingwith time本仿真实例中,对应于图 2 中的每一段 B 样条,s 被 10 等分,并在每一伪位移等分点处,s被 200 等分,整个二维有向搜索图上共有 10(10+1)(200+1)个节点.在奔腾 200 型微机上进行轨迹规划,约需费时 1.5 s,该时间已能很好地满足一般离线运动规划的需要.需指出的是,图 4 中的伪加速度曲线,以及图 6 中的角加速度曲线有毛刺出现,这是动态规划本质为一离散算法的必然结果.一般可通过提高量化精度来加以改善,对应于本算法,就是提高伪速度的量化精度.另需要指出的是,利用 B 样条路径代替原有的离散路径点路径,可能会引起新的碰撞.该问题一般可在机器人路径规划时,通过增加离散路径点的个数,以及增大操作臂和障碍物之间最小安全距离等措施加以解决.32上海交通大学学报第32 卷4结语本文对沿着特定路径运动的机器人的时间最优轨迹规划问题作了研究,成功地运用了动态规划法,沿着三次 B 样条逼近所得的路径,对机器人实现时间最优轨迹规划.算法通过了仿真实验,证明是可行的,效率较高.参考文献1Bobrow J E,Dubowsky S,Gibson J S.Time optimal control of robotic manipulator along specified paths.Ins JRobotics Research,1985,(3):3172Shin K G,Mckay N D.Minimum-time control of robotic manipulators with geometric path constraints.IEEETransactions on Automatic Control,June1985,AC-30(6):5315413Loano-Perez T.Spatial planning:a configuration space approach.IEEE T ransaction on Computers,1983,C-32(2):1081204Lin C S,Chang P R,Luh J Y S.Formulation and optimization of cubic polynomial joint trajectories for industrialrobots.IEEE T rans on Auto Contr,Dec1983,AC-28(12):106610745袁奇荪.计算几何造型学基础.北京:航空工业出版社,1987.下期发表论文摘要预报线性化逐层优化 MLP 训练算法周志杰,胡光锐(上海交通大学电子工程系)李群(南京通信工程学院)摘要:提出了线性化逐层优化M LP训练算法(LOLL).LOLL采用循环的方式逐层对MLP的连接权值进行训练.训练连接权值时用一阶泰勒级数表示神经元的非线性激活函数以实现神经网络的线性化,使 MLP的训练问题转化为一个线性问题.同时为保证神经网络线性化条件不被破坏,LOLL 通过在神经网络的误差函数中计入部分线性化误差限制参数的改变幅度,对神经网络的误差函数进行了修正.实验结果显示,LOLL训练算法的速度比传统的BP算法快 4 倍,用它构成的语音信号非线性预测器有较好的预测性能.用于 FD 法电容参数提取的高效截断边界条件曹毅,金荣洪,李征帆(上海交通大学电子工程系)摘要:基于测度不变方程(M EI)的概念和局部等效原理,将截断边界的确定归结为网格边界上一小区域的电位场模拟问题,并讨论了二维、三维情况下的具体处理.计算实例表明,应用这种截断边界条件的 FD 法得到的电容计算结果与矩量法和 FASTCAP 软件所得结果吻合得较好.33第 12 期钱东海,等:基于 B 样条路径的机器人时间最优轨迹规划
