一种快速神经网络路径规划算法概要.docx
《一种快速神经网络路径规划算法概要.docx》由会员分享，可在线阅读，更多相关《一种快速神经网络路径规划算法概要.docx（11页珍藏版）》请在冰点文库上搜索。
一种快速神经网络路径规划算法概要
文章编号222
一种快速神经网络路径规划算法α
禹建丽∂∏√孙增圻成久洋之
洛阳工学院应用数学系日本冈山理科大学工学部电子工学科2
清华大学计算机系国家智能技术与系统重点实验室日本冈山理科大学工学部信息工学科2
摘要本文研究已知障碍物形状和位置环境下的全局路径规划问题给出了一个路径规划算法其能量函数
利用神经网络结构定义根据路径点位于障碍物内外的不同位置选取不同的动态运动方程并针对障碍物的形状设
定各条边的模拟退火初始温度仿真研究表明本文提出的算法计算简单收敛速度快能够避免某些局部极值情
况规划的无碰路径达到了最短无碰路径
关键词全局路径规划能量函数神经网络模拟退火
中图分类号×°文献标识码
ΦΑΣΤΑΛΓΟΡΙΤΗΜΦΟΡΠΑΤΗΠΛΑΝΝΙΝΓ
ΒΑΣΕΔΟΝΝΕΥΡΑΛΝΕΤΩΟΡΚ
≠2∂∂≥2≥∏
ΔεπαρτμεντοφΜατηεματιχσΛυοψανγΙνστιτυτεοφΤεχηνολογψΛυοψανγ
ΔεπαρτμεντοφΕλεχτρονιχΕνγινεερινγΦαχυλτψοφΕνγινεερινγΟκαψαμαΥνιϖερσιτψοφΣχιενχε2Ριδαι2χηο2ϑαπανΔεπαρτμεντοφΧομπυτερΣχιενχεΤεχηνολογψΣτατεΚεψΛαβοφΙντελλιγεντΤεχηνολογψΣψστεμσΤσινγηυαΥνιϖερσιτψΒειϕινγΔεπαρτμεντοφΙνφορματιονΧομπυτερΕνγινεερινγΦαχυλτψοφΕνγινεερινγΟκαψαμαΥνιϖερσιτψοφΣχιενχε2Ριδαι2χηο2ϑαπαν
Αβστραχτ∏√√√×∏∏∏∏∏∏2∏√×∏∏∏∏
√∏
Κεψωορδσ∏∏∏
1引言Ιντροδυχτιον
机器人路径规划问题可以分为两种一种是基于环境先验完全信息的全局路径规划≈另一种是基于传感器信息的局部路径规划≈∗后者环境是未知或者部分未知的全局路径规划已提出的典型方法有可视图法!
图搜索法≈!
人工势场法等可视图法的优点是可以求得最短路径但缺乏灵活性并且存在组合爆炸问题图搜索法比较灵活机器人的起始点和目标点的改变不会造成连通图的重新构造但不是任何时候都可以获得最短路径可视图法和图搜索法适用于多边形障碍物的避障路径规划问题但不适用解决圆形障碍物的避障路径规划问题人工势场法的基本思想是通过寻找路径点的能量函数的极小值点而使路径避开障碍物但存在局部极小值问题且不适于寻求最短路径≈文献≈给出的神经网络路径规划算法我们称为原算法引入网络结构和模拟退火等方法计算简单能避免某些局部极值情况且具有并行性及易于从二维空间推广到三维空间等优点对人工势场法给予了较大的改进但在此算法中由于路径点的总能量函数是由碰撞罚函数和距离函数两部分的和构成的而路径点
第卷第期年月机器人ΡΟΒΟΤ∂
α收稿日期
一般由连接出发位置到目标位置的直线上均匀分布的点序列开始按使总能量函数减小的方向移动所以它得到的一般是无碰的且尽可能短的可行性路径难以得到最短路径本文在该算法的基础上提出了一个改进算法≈其主要特点是改进算法设有一个检测器它检测并将每个路径点的位置返回给系统系统对落在障碍物内部的点按使总能量函数减小的方向移动而障碍物外的点仅按距离减小的方向移动从而使规划的无碰路径达到了最短无碰路径而且收敛速度明显加快改进算法除了适用于障碍物是多边形围成的图形外还适用于障碍物是圆形的情形改进算法允许设定不同的障碍物各条边的模拟退火初始温度从而能够简单地避免某些局部极小值的情况
2神经网络路径规划Αλγοριτημφορπατη
πλαννινγβασεδοννευραλνετωορκ
这一节叙述文献≈给出的神经网络路径规划算法
21碰撞罚函数
一条路径的碰撞罚函数定义为各路径点的碰撞罚函数之和而一个点的碰撞罚函数是通过它对各个障碍物的神经网络表示得到的障碍物假设为多边形图表示了一个点到一个障碍物的罚函数的神经网络底层的两个结点分别表示给定路径点的坐标ξ!
ψ中间层的每个结点相应于障碍物的一条边的不等式限制条件底层和中间层的连接权系数就
等于不等式中ξ!
ψ前面的系数中间层每个结点的阈值等于相应不等式中的常数项中间层到顶层的连接权为顶层结点的阈值取为不等式的个数减去
后的负数
该连续网络的运算关系为
ΧφΙοΙο
Ε
Μ
μ
ΟΗμΗΤ
ΟΗμφΙΗμ
ΙΗμωξμξιωψμψιΗΗμ
其中各符号的含义为Χ顶层结点输出ΙΟ顶层结点输入ΗΤ顶层结点阈值ΟΗμ中间层第μ个结点的输出ΙΗμ中间层第μ个结点的输入ΗΗμ中间层
第μ个结点的阈值ωξμωψμ第μ个不等式限制条件的系数激发函数为常用的Σ形函数即
φξ
εξ
Τ
其中Τ为模拟退火方法中的/温度0按以下规律变化
Ττ
Β
τ
整条路径相应于碰撞函数部分的能量为
ΕΧ
ΕΝ
ιΕ
Κ
κ
Χκι
其中Κ是障碍物的个数Ν是路径点的个数Χκι表示第ι个路径点Πξιψι对第κ个障碍物的碰撞函数
图一个点到一个障碍物的罚函数的神经网络图神经网络路径规划算法的计算实例
ƒƒ∞¬×
22路径规划
相应于路径长度部分的能量定义为所有线段长
度的平方和即对所有路径点Πξιψιι,
Ν定义
机器人年月
ΕΕΝ
ι
≈ξιξιψιψι整条路径的总能量函数定义为
ΕωλΕλωχΕχ
其中ΩΛ和Ω
χ
分别表示对每一部分的加权
由于整个能量是各个路径点函数因此通过移动每个路径点使其朝着能量减少的方向运动最终便能获得总能量最小的路径关于点Πξ
ι
ψι的动态运动方程为
ξαιΓ≈ωλξιξιξι
ωχΕΚκφχΙΟκιΕΜ
μ
φχΙΗμκιωκξμ
ψαιΓ≈ωλψιψιψι
ωχΕΚκφχΙΟκιΕΜ
μ
φχΙΗμκιωκψμ
其中
φχ
Τ
φ图是利用此算法的计算实例因为总能量函数ΕωλΕλωχΕχ是有碰撞罚函数和距离函数两部分组成的路径点是向着尽量远离障碍物且使路径较短的位置移动因此一般情况下开始由于温度较高路径点移动到远离障碍物的位置随着温度值的减小路径的长度逐渐得到改善最后收敛到无碰的可行性路径
3快速神经网络最短路径规划算法Φασταλ−γοριτημφορπατηπλαννινγβασεδοννευ−ραλνετωορκ
在快速神经网络路径规划算法中设计了一个检测器它实际上是一个神经网络分类器利用检测器在路径规划的过程中始终检测着路径点的位置ξψ由神经网络分类器判断该点是否在障碍物内即是否与障碍物相碰并将检测结果返回系统神经网络分类器就是在路径点到一个障碍物的罚函数的神经网络中中间层和顶层结点的激发函数取为阶跃函数则中间层的每个结点是决定该结点是否满足它的限定条件若满足输出为否则输出为若所有中间点均满足则顶层输出为它表示该点在障碍物内若中间点检测出其中至少有一个不满足限制条件顶层输出便为它表示该点在障碍物外
系统根据检测器返回的信息选择路径点的动态运动方程若路径点在障碍物内则按动态运动方程移动若路径点在障碍物之外则按动态运动方程移动即若路径点在障碍物外或障碍物内的路径点一旦移出了障碍物就仅按减少路径长度的方向移动不再向远离障碍物的方向移动从而使路径能快速收敛到无碰的最短路径
下面给出改进的快速神经网络最短路径规划算法在此作了点假设障碍物是多边形围成的平面图形或者是圆形的平面图形机器人为圆形点机器人计算时障碍物的尺寸按机器人的半径作了适当拓展≈障碍物为静止的
步骤输入出发点Πξ
ψ及目标点ΠξΝψΝ的坐标对于τ初始路径一般取为出发点到
目标点的直线上均匀分布的点列当ξ
ΞξΝ时ξιξιξΝξΝ
ψιψΝψξιξξΝξψι,Ν步骤2对于路径点ΠξιψιιΝ用检测器检测是否在障碍物内
步骤3若Πξ
ι
ψι在障碍物内则按下列运动方程移动
ξαιΓωλξιξιξι
ωχΕΚ
κ
φχΙΟκιΕΜ
μ
φχΗμΙΗμκιωκξμψαιΓωλψιψιψι
ωχΕΚ
κ
φχΙΟκιΕΜ
μ
φχΗμΙΗμκιωκψμξαιΓωλξιξιξι
ωχφχΙΟιφχΗΙΗιΠξιψαιΓωλψιψιψι
ωχφχΙΟιφχΗΙΗιΘψι
其中用于Πξ
ι
ψι位于多边形的障碍物内的情
况用于Πξ
ι
ψι位于圆心在ΠΘ的圆形障碍物内的情况
Πξιψι若在障碍物之外则按下列运动方程移动
ξαιΓξιξιξι
ψαιΓψιψιψι步骤4重复执行步骤步骤直到路径收敛这里整条路径总能量函数的定义与原算法相同一个点到一个障碍物的罚函数的神经网络结构如图但是中间层第μ个结点的输出改为了ΟΗμφΗμΙΗμ中间层第μ个结点的激发函数改为
φΗμξ
εξΤΗμ
第卷第期禹建丽等一种快速神经网络路径规划算法
ΤΗμτ
Βμ
τ
其中Βμ是相应于障碍物每一条边的初始温度即可以根据障碍物的形状设定各边的不同的初始温度这样对于一些不对称图形可避免其罚函数曲面形成一边倒的情况从而避免路径规划收敛到局部极小值最后中间层第μ个结点的输入ΙΗμ当障碍物是多边形围成的平面图形时同原算法的式当障碍物是圆形的平面图形时不等式的个数取为一即中间层只有一个结点且输入为
ΙΗΡ
ξιΟ
ψιΘ
其中Ρ为圆形障碍物的半径ΠΘ为圆形障碍物的圆心
4仿真实验Σιμυλατιον
图是在参数ΒΓωλωχ
和图的完全一样的情况下用改进算法进行的仿真实验结果它是一条折线形的最短无碰路径图是图和图中两种算法下仿真实验收敛速度的比较其中横轴是计算次数ττ次纵轴是路径长度点线是实际无碰最短路径长度实线是图的仿真实验的收敛速度曲线虚线是图的仿真实验的收敛速度曲线它表明改进算法的收敛速度快于原算法的收敛速度
图的仿真实验表明改进算法不仅适用于障碍物是多边形围成的图形而且适用于障碍物是圆形的情形在多个障碍物的环境中改进算法也能得到最短的无碰路径其中初始温度均为ΓΓ
•
•
≤
图仿真实验
ƒ1
≥∏
图仿真实验
ƒ1
≥∏
机器人年月
5结论Χονχλυσιον
本文给出了一个快速神经网络最短路径规划算法成功地得到了最短的无碰路径而且计算简单收敛速度快它除了适用于障碍物是多边形围成的图形外还适用于障碍物是圆形的情形而且能够简单地避免某些局部极小值的情况为移动机器人的最优路径规划提供了一个简捷有效的算法
参考文献Ρεφερενχεσ
孙增圻智能控制理论与技术清华大学出版社
≤°∏°∏2
ƒ∏¬∏×2⁄√≥°∞∞∞×∏9
≠≥2√×⁄≥∏≥16
≠÷⁄≠°°•×∏≥13≠∏≥°≥°°
√≤∏≥15
孟庆浩彭商贤刘大伟基于±2图启发式搜索的移动机器人全局路径规划机器人20
°∂≥∏∏°2√°∞∞∞2≤∏
∞⁄⁄∞∞¬√2°ƒ∞∞∞×∏28
∏√∂≠∏°°∂°≤×≤×χ°∏
2°×•°≤22°°≤≤22
作者简介
禹建丽2女硕士副教授研究领域模糊控制遗传算法神经网络机器人智能控制
∂∂2男博士副教授研究领域自适应控制机器人智能控制等
上接第页
参考文献Ρεφερενχεσ
≤±∏×∏≥∏≥∂≥≤2≤∂χ
°√⁄2⁄⁄≥∞∞∞×°20
杨雨东徐光佑朱志刚维帧间运动估计方法清华大学学报自然科学版37
艾海舟张朋飞何克忠江潍张军宇室外移动机器人的视觉临场感系统机器人22
⁄∞22°∂∏≤°≥°∞
∏×⁄∂°清华大学出版社≥∏≥≥∏∞ו2≠
≥≤∂°∏∞≤∏∂∞∞∞°17
°°∏√∞≥∏∏ƒ∞∞∞×°17
罗恒虚拟环境的建模与应用硕士论文清华大学计算机系
作者简介
刘亚2男硕士研究生研究领域视觉侦察艾海舟2男副教授研究领域移动机器人计算机视觉模式识别
徐光佑2男教授研究领域计算机视觉多媒体信息处理
第卷第期禹建丽等一种快速神经网络路径规划算法
升级会员 