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