针对粒子群算法在解空间盲目搜索的缺点,提出一种基于时变适应度函数的改进粒子群路径规划算法。该算法有效地将人类搜索经验与粒子群算法相结合,利用神经网络描述环境约束和距离信息,并构造粒子的适应度函数,从而该算法在迭代过程中可以利用权值的改变合理地调整适应度函数。这样,新算法在寻优过程中能够先确定路径方向,然后逐步提高路径安全性。将该算法应用于机器人路径规划,与
第1 2期
蒲兴成,:于时变适应度函数的改进粒子群算法及其在移动机器人路径规划中的应用等基
‘ 4 5 45
定义为所有线段长度的平方之和,即对于所有路径点定义
1能量函数的构造 通常机器人活动空间假定为有限二维平面,间中的障碍空
E: L=[一 ) := (… f+( jl- + y ) 1一 ) y+(+ )] ( ) 4 1
其中表示第 i个线段的长度。整条路径的总能量定义为 E= E+ f∞E () 5
物视为位置已知的凸多边形障碍物。将工作空间中障碍物按 照机器人半径尺寸膨胀,可将机器人等效为一个点,这样可将
其中:、分别表示对每一部分的加权。 。
路径规划问题等价为约束优化问题: mn,,) i ( Y∈ Y∈R R
2改进粒子群算法在移动机器人路径规划中的应用 利用粒子群算法进行路径规划的传统思想是将 E作为粒 子的适应度函数,用粒子群算法在解空间进行寻优,利即对 E () 1
St g ( Y>0…, ( Y>0 . .: ), ,) , 1 1 g ( Y>0,,?,)>0 , ) i… g ( Y -
求极小值,最终得到的最优粒子即期望的最优路径。
算法在寻优过程中的盲目性严重降低了算法的寻优能力。 g ( Y>0…, ( y>0 ,), , ) t 1 1≤Ⅳ≤
为了克服盲目性的影响,以考虑将人类的寻优经验引入到算可
法的寻优过程中。在外部环境已知的情形下,人类的寻优经验
其中
,)目标函数, Y为即一般为路径的长度; 2,) g ( Y为第
m个障碍物对机器人的第 n个约束。能量函数便是通过 f, (
是:首先确定路径方向,在确定正确路径方向的基础上再考虑 路径安全。如果路径规划算法能利用人类经验,将很大程度地提高算法的寻优能力。 为了使算法能够利用人类经验进行寻优,算
法应具备两个 性质:
Y,n Y ( 12…,构造函数 Ff xY,: Y, )g (,) m=— Ⅳ) ((,)g( )…,, ( Y,,, )…,, )…,,)…,,) ,)… g ( Y, g ( Y, g ( Y, g ( Y ) 1
使原来的约束问题转换为无约束问题。笔者按照文献[] 4中的方法,采用神经网络法构造碰撞罚函数。为了对路径与障碍物之间的碰撞性质加以量化,一条路径的碰撞罚函数定义为各
a算法能够尽快找到正确路径方向。 )
b算法不能降低路径安全性的影响。 ) 采用固定适应度函数粒子群算法,不能同时满足以上两个性质。如果算法要满足性质 a, )则应减小路径安全对总能量
路径点的碰撞罚函数之和,而一个点的碰撞罚函数是通过它对各个障碍物的连接网络表示得到的。 假设障碍物为多边形,可以用一组线性不等式来表示,它 则在障碍物中的点必须满足所有不等式的限制, 1表示了一图个这样的神经网络。该网络的运算关系为 C= ( 1厂 l T) M
的影响力,同时增大路径长度信息的影响力。更侧重利用路径 长度评价粒子的优劣,有利于算法更快地确定正确的路径方将 向。如果要满足性质 b,不能减小路径安全性对总能量的 )则
影响力。因此,以上两性质对于固定适应度函数粒子群算法是矛盾的,采用时变适应度函数则可以解决这个矛盾,从而可以有效利用人类经验进行寻优操作。 由式 ( )知,过调整和∞可以改变 E和 E在 E 5可通
=∑ 0+0 r
oM j| m: M I m=∞ m+ ̄y Y M O m i+山肌 z i+
其中: C为顶层节点输出;为顶层节点输入;,为顶层节点 0
中所占的比重,比传统 P O算法采用固定的和。笔者相 S, 引入以下公式对和。出调整:作 0。 I 0W 9 1 一
阈值;为中间层第 m个节点的输出;为中间层第 m个节 0 点的输入;为中间层第 m个节点的阈值; m一 为第 、 m个不等式限制条件的系数。通常取激发函数为常用的型 函数,即 1
O J
一
ed+( s r一∞— n )× n∞—t t e d a
ep x (一5×(t/ x e) ) irmai r e t f n ow —∞f —
(
) 6 () 7
ed+( fs r一 ̄1ed n —t t 0一 n )× a
, )÷ (=
( 2 )
ep x (一5×(t/ x e)2 irmai r^ ) e t
其中:e为当前迭代步数; ai r ir t m x e为最大迭代步数;—nw和 t c o o∞一 o nw为当前迭代步数时碰撞罚函数的权值和路径长度函数的权值; s r和。e d为碰撞罚函数权值的初始值和终止 t一 t t o a _n 值; s r和 _ n t一 tt o a ed为长度函数权值的初始值和终止值。 假设在固定适应度函数 P O算法中, S∞取为定值,为 定值 Y。在改进 P O算法中,—tr>。s r<, S fs t,一tt Y因此改进 a a
图1计算到一个障碍物的罚函数的神经网络
无碰路径规划问题可以等效为具有两个约束条件的优化问题:一个是不与障碍物相碰,另一个是路径尽量短。基于上述关于障碍物的网络表示,两个约束条件可以加以量化,这这样,路径规划问题可变为一个极值问题。其优化的能量函数由
P O算法中路径长度对路径总能量的影响更大。利用此时刻 S的适应度函数有利于改进 P O算法挑选出路径长度更短的粒 S子作为更优秀的粒子,进而引导其他粒子向路径长度更短的方 向调整自身位置,因此改进 P O算法可以更快地确定正确的 S路径方向。在迭代过程中,采用式( ) 7更新权重的大小, 6和( ) f
路径长度和障碍物罚函数两部分组成。路径的罚函数定义为所有路径点的罚函数之和,每个点的罚函数可通过相应的网络来计算。相应于罚函数的这部分能量可以表示为 K
不断减小,不断增大,终∞=一 n, e d 最 f ed∞=∞一 n。其
中 6— n, ed>, 0 ed< 6一 n Y由于后期 C不断增大, z 0 . O 使得 E对 E 的影响力逐渐增大,用此时刻的适应度函数有利于挑选出路利
E I善 r J=I c
()径更安全的粒子作为更优秀的粒子, 3 进而引导其他粒子向路径 安全性更好的方向调整自身位置,前期忽略的安全性在后期逐 步得到弥补,最终得到最优路径。以上操作引导着粒子按照先
其中: k是障碍物的个数;Ⅳ是路径点的个数; C表示第 i路个径点对第 k障碍物的罚函数。相应于路径长
度这部分能量个

改进粒子群算法在机器人路径规划中的应用_城乡/... 结合移动机器人全局路径规划问题模型, 提出一种带...适应度函数选择机器人路径规划要求所规划路径既能安全...
一种改进粒子群算法的移动机器人路径规划_专业资料。在当今流行的几种生物启发... 基于改进粒子群算法的移... 9人阅读 3页 2.00 基于时变适应度函数的...
基于时变适应度函数的改进... 暂无评价 4页 2.00元 基于改进粒子群算法的...移动机器人路径规划 技术的 睿 ( a) 常规算法 ( b) 本文算法 ( c ) 本...
一种改进粒子群算法的移动机器人路径规划 摘要:在...多因素所产生的干扰, 提 高粒子群整体的适应度。...1.3 算法的基本流程 步骤 1 最小化目标函数,确定...
建立机器人工作空间障碍物顶点模型,根据障碍物顶点信息构造一个移动机器人从始点到终点的无碰距离函数,然后用改进的粒子群算法对此路径进行优化,得到全局最优路径....
基于改进粒子群算法的移动机器人全局路径规划_专业资料。在标准粒子群算法的基础... 基于神经网络和粒子群算... 6人阅读 4页 2.00 基于时变适应度函数的...
微粒群算法在机器人路径... 暂无评价 4页 2.00 基于时变适应度函数的...( 2011) 08 - 0167 - 03 改进微粒群算法在机器人路径规划中的应用李 巍, ...
基于时变适应度函数的改进... 暂无评价 4页 2.00元 粒子群算法在移动机器...赵先章等针对结构化环境中移动机器人路径规划问题 , 提出了一种基于粒子群的 [...
针对结构化环境中移动机器人路径规划问题,提出一种基于粒子群的路径规划算法。该算法利用适应度函数描述环境约束及路径的距离信息,适应度函数通过神经网络计算;由路径...
缺点,提出将改进的粒子群优化算法运用到静态环境下的移动机器人路径规划问题当 ...问题解的编码和适应度函数的选择,应用 PSO 算法进 行函数优化不仅可以避免遗传...
热门文档