基于网络结构的并行路径规划算法new

《基于网络结构的并行路径规划算法new》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、清华大学学报(自然科学版)L2，191996年第卷如urns1ofTsinghuaUniv盯5ity(Sei＆Tech)第5期第67～71页@基于网络结构的并行路径规划算法0吴晓涛，孙增圻邓志东D22——一一一一清华大学计算机科学与技术系，北京100084文摘算法继承了人工势场法的基本思想，通过寻找路径点的髓量函数的极小值点而使路径避开障碍物。势场由排斥场和吸引场叠加而成．在算法中对于排斥场和吸引场的强度引入了一个平衡系数，井引入了模拟退火的思想和一些启发性知识，以避免某些局部极值的情况算法具有很大的并行性，收敛速度较快，易于从二维空间扩展到三维空间，对人工势场

2、法给予了较大的改进，取得了较好的仿真效果关键词苎鱼能量函数；堕壑堡查；井行网络同杓苛fj算分类号TP39住耽路径规划问题就是运用某种策略生成从出发位置到目标位置的无碰撞路径。已提出的方法主要有位形空间法，图搜索法，人工势场法，拓扑法等。一般来说，解决无碰撞路径规划的方法是构造一个数据结构来表示工作空间，然后，辖^障碍物及路径点通过对这个数据结构的搜索寻找到无碰撞路径。但是，这种方法通常存在着组合爆炸问题，计算各路径点能量函数厦其梯度所以很难做到在线实时地进行规划。并且，从二维寻优问题扩展到三维寻优问题也具有很大的沿梯度方向移动困难。而人工势场法基本上不存在组合爆

3、炸问各路径点题，并且从二维空间向三维空间的扩展也非常方便。本文算法用并行网络结构实现人工势场法，从而能够做到在线实时的进行规划，而且引入了模拟退火的基本思想和一些启发性知识以避免一些局部极值的情况。调节温度并引^其他l并行路径规划算法方法、隗出局部极值算法的流程见图1。其中输入部分给出障满足要求或T人由中止碍物的各项参数及初始路径点序列，初始路径图l规划系统流程圈点序列一般为在连接起始和终了路径点的直线收稿日期：1994—06—23‘修回日期1995—03一O7*国防科技预研基金项目清华大学学报(自然科学版)上均匀分布的点序列，这在大多数情况下可保证路径最短。在

4、获得输入的各项参数后，开始路径的寻优，也就是求能量函数的极小值问题其基本算法是梯度下降算法，为避免算法陷入某些局部极小值，引入了模拟退火的思想和一些启发性知识。令：R(∞，Y)为路径点的位置向量，=1，2，⋯，L；eo表示第i个障碍物的第条边，其方程为X+G一0，i一1，2，⋯，M；=1，2，⋯，M；其中X-，)；A一(n6)，I．．I一1；P=(岛，Y)为第i个障碍物的第J个端点的位置向量。能量函数的计算如下：E(R)一E+卢E(1)式中：E为路径点在相邻路径点的吸引函数场中的能量，卢为E相对于E的加权系数。路径点在障碍物的罚函数场中的能量为LE一∑∑(2)第

5、个路径点在第i个障碍物的罚函数能量场中的能量值为1一知(3)Ⅳ。则：ID^一roinD，sgn(D)=sgn(D)(4)fA．．R+G，条件1式中；D一J—IR—PI条件0(5)-一IR一Pll条件3令A=(6lJ，一Ⅱ)，A=(nfJ，一6)：则有条件1：(0R·+⋯P)(：R^+A只卅L)≥0；条件2：(R^+P)(R^+只，J十1)AiR。+ZP．．．DI。I所表示的实际上是路径点风到障碍物0．的最短距离。并且，D在障碍物内符号为正，在障碍物外符号为负。条件1、2、3的

6、几何含义如图2，D．n所表示的是点到线段的距离，所以，当风在满足条件1的区域内，D即为点到直线PPz的距离}当凤分别满足条件2和3时，D分别为和P，R。和P!两点间的距离。则LE^一∑FA(6)k——-I第个路径点在第一1和第+1个路径点的吸引函图2条件1、条件2、条件3的几何意义数场中能量的和为E：(IIR一R__ll+llR^一R1l)能量函数梯度的计算如下：可E(B)．：E(风)_-E(R)(8)M式中：VE()：∑(风)，(一半()VD吴晓涛-等基于网络结构的并行路径规划算法条件lP，)／llR。一P条件2条件1、条件2、条件3同(5)式P一)／RP．．

7、．+条件3E^(R)一(R^一R“)+(R^一R·一1)VD(计算出能量函数的梯度后，就沿梯度方向移动路径移动的步长n：由某种近似线性搜)R索策略给出，这种策略满足：f一．．．．【VE(RI(VE(R]c9)A(—(E(R)一E(R)≤n：(1lE(Ri))(10)RRf_7F，p[、T一式中：R：=R：一l一_Lr专黹·为第次第k个路径点的移动步长；和为满足o<≤<1的常数。当4：满足第(9)(1o)两式时，可证明E(R。)一0，设E(R)=0；进一步可证明Rg为E(R)的局部极小点，也就是说本算法是收敛的。当VE(R)小于某一个小的正数y时，则认为算法已经收

8、敛。为防止障碍物内的路径