一种快速神经网络路径规划算法概要

文章编号 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艾海舟 张朋飞 何克忠 江潍 张军宇 室外移动机器人的视觉临 场感系统 机器人