一种新基于混沌优化算法的机器人路径规划方法

1、第 卷第 期 年 月机器人 ×文章编号 2 2 2一种基于混沌优化算法的机器人路径规划方法3石鸿雁 孙昌志沈阳工业大学电气工程系机器人电机研究所 辽宁沈阳摘要 提出了一种基于混沌优化算法的机器人路径规划方法 即混沌人工势场法 该方法能够在动态环境下实时!有效地产生避碰局部最优路径 避免了传统人工势场法容易陷入局部最优和在比较靠近的两个障碍物之间找不到通道的缺陷 仿真试验表明 提出的方法具有较强的路径规划能力 克服了传统人工势场法的缺点 具有较强的实用性关键词 混沌优化算法 人工势场法 局部最优 路径规划中图分类号 ×° 文献标识码 2 2(, ,:× &

2、#176; × × : 1引言(人工势场法是动态环境下移动机器人路径规划的常用方法 最初是作为在线避障方法提出的 当机器人事先没有环境信息 只能通过传感器感知环境时利用此方法 该方法具有避障能力 侧重于实时的效率 但并不能保证到达目标点 传统人工势场法 实际上给出了由环境信息到决策的直接映射 它是路径规划的一个十分有用的工具 在机器人局部避碰规划中较多地使用基于人工势场的方法 它在解决静态障碍物的局部避碰问题时 具有实时性好!比较实用等特点 但当障碍物为运动障碍时 其效果并不理想 会导致机器人的无效运动 此外还存在局部极小点!在距离近的障碍物 但机器人可以通过的 前面不能发

3、现路径!在障碍物面前振荡 的缺陷针对上述存在的缺陷 人们在寻找没有局部极小点的势场方面 做了很多有益的尝试 文献 提出了基于导航的人工势场中关于局部最小恢复的虚拟障碍概念 它把基于势场的方法与虚拟障碍概念结合起来 在未知或非结构环境下去操纵柱形机器人 在具有凹障碍和凹形障碍 即使障碍是凸形的 但是几个凸形的障碍可以构成一个凹障碍 的环境下 有效地克服了局部极小等问题 由于人工势场法被广泛地应用于机器人的导航中 于是在保持其优点的同时 找到快速移动机器人的路径规划问题的一个有效解是非常重要的 文献 提出了机器人实时的路径规划方法 称为进化人工势场法 它把遗传算法与人工势场法结合 推导出具有可调参

4、数的最优势场函数 文献 把人工势场法与模拟退火算法相结合 用于对移动机器人进行局部和全局的路径规划等等 在应用传统人工势场法对机器人进行路径规划时 常常在凹障碍或凹形障碍运行中失败 为3收稿日期此 本文提出了混沌人工势场法 它将改进的混沌优化算法与传统的人工势场法相结合 具有下述特点 在传感器的协助下 在未知或非结构环境下 自主移动机器人能够快速移动 而不陷入局部极小点 在动态环境下 避开工作环境中的障碍物 实时躲避局部极小点 在比较靠近的障碍物中间找到通道 当机器人面对极易产生局部极小点的凹障碍或凹形障碍时 利用混沌人工势场法也可以为机器人找到避障路径 此外 由于动态环境下规划的路径常常存在

5、突变点 于是为便于机器人跟踪 引入了平滑因子的概念2混沌优化算法与混沌人工势场法(22.1混沌优化算法及其改进混沌现象是不含外加随机因素完全确定性的系统所表现出的介于规则与随机之间的一种随机行为 混沌现象不同于混乱和无规律现象 存在于绝大多数非线性系统中 它虽然貌似随机现象 但并非真正的随机现象 因此具有独特的性质 随机性 即混沌表现出来的类似于随机变量的杂乱无章现象 遍历性 混沌可以不重复地历经一定范围内的全部状态 规律性 即混沌可由确定性的迭代式产生 正是由于混沌现象的上述性质使得它成为搜索过程中避免陷入局部最优的机制 于是混沌优化算法应运而生 著名的 映射+ =( = , ,( 为混沌优

6、化算法奠定了基础.可以证明,当 时,该映射成为 , 区间上的满射 ,于是利用该映射得到的混沌优化算法具有摆脱局部极小的能力,有关该算法的具体情况见文献 .通过对混沌优化算法的分析发现: 单纯提高迭代步数不能显著提高算法搜索的遍历程度; 多轨道并行搜索不能显著提高混沌搜索的遍历程度; 在粗略搜索后得到的最优点附近进行细搜索,可能导致偏离全局最优点,影响算法的搜索速度.此外,根据混沌变量的概率分布特点,在大范围搜索后,应缩小范围对概率分布较小的区间进行再搜索 .为此提出了改进的混沌优化算法,约束最优化问题为:8( = , ,(= = , ,= , ,( 改进的混沌优化算法求解非线性约束最优化问题的

7、实施步骤见文献 .为说明改进混沌优化算法的有效性进行如下试验,试验 : ( (. (. ( 其中 , . , . , . .这是一个求多极值函数最优解的问题.其理论最优解为,全局最优值( .利用改进的混沌优化算法得到的最优解为: ( .,最优值为( . .把每一次搜索到的满足约束条件的目标函数值记录下来,其收敛过程如图 所示 .图 应用混沌优化算法求解 可行解的搜索曲线 试验 :国际上常用的约束最优化测试函数: ( (满足约束条件为: + + = , ,( 其理论最优解: ( . , . , . , . ,. , . , . 最优值为:( . .应用改进的混沌优化算法求解 的最优解: ( .

8、, . , . , . ,. , . , . 最优值为:( . .求解 的局部放大可行解搜索曲线见图 .第 卷第 期石鸿雁等 一种基于混沌优化算法的机器人路径规划方法图 用改进的混沌优化法求解 的局部放大可行解搜索曲线 应用模拟退火算法求解 的最优解为:( . , . , . , . ,. , . , . 最优值为:(. .应用模拟退火算法求解的迭代过程收敛曲线见图 .图 应用模拟退火法求解 的迭代过程收敛曲线 应用禁忌搜索优化算法求解 的最优解:( . , . , . , . ,. , . , . 最优值:(. .应用禁忌搜索算法求解的迭代过程收敛曲线见图 .图 应用禁忌搜索算法求解 的迭代

9、过程收敛曲线 × 在上述仿真试验中 由于模拟退火算法和禁忌搜索算法在求解过程中搜索到的可行解容量比较大故只绘制出迭代次数的搜索曲线 从上述的仿真试验可以看出 改进的混沌优化算法不仅可以求解多极值函数的全局最优解 还可以求解约束最优化问题其优化过程结构简单!计算量小!求解精度高!速度快 适合处理无约束和约束最优化问题 且与模拟退火!禁忌搜索优化算法相比 具有较好的精度2 2 混沌人工势场法本文在对人工势场法和混沌优化算法进行深入研究的基础上将改进的混沌优化算法用于人工势场中 提出了混沌人工势场法 ° 2 ° 以避免单纯采用人工势场法对机器人进行路径规划时出现的不足

10、混沌人工势场法把势函数作为目标函数 控制变量为机器人行走的步长和运动方向相对于世界坐标的夹角 即方向角根据混沌人工势场法进行路径规划时 利用传感器的信息 在每次采样后 通过改进的混沌优化算法计算机器人下一周期的步长和方向角 从而确定下一个子目标点 如此下去 就可以实时地得到局部最优路径文中的吸引势函数为 ,关于第个障碍物的排斥势函数为: = 如果其它= , ,( 总的势函数为:= += ( 这里 是机器人与目标点之间的距离,是机器人与第个障碍物之间的距离, 是安全距离,!是分别由障碍物的形状决定的正常数,是工作环境中障碍物的数量(包括静止障碍物和移动障碍物.在本文中,机器人的路径是利用混沌人工

11、势场法确定的.由于改进混沌优化算法的良好性质,如此规划的机器人路径既可以摆脱局部极小点,同时也可以在两个彼此靠近但又允许机器人通过的障碍物之间找到通道.在工作环境中存在移动障碍物时,也能为机器人有效地规划出避开障碍物的近优路径.由于在未知环境下,机器人依靠传感器信息感知环境,因此产生的路径常常有突变点,即路径不平滑.这给机器人跟踪规划的路径带来困难,为了使机器人易于跟踪已规划的路径,引入了平滑因子的概念.一旦上述势函数比较小(根据实际问题确定何时引入平滑因子,就采用如下的平滑因子:=( ( 机 器 人 年 月这里是由实际情况确定的正常数.此时改进的混沌优化算法把 作为目标函数,于是通过计算可以

12、得到相应的步长和方向角,因此实时地得到了机器人的平滑路径.3 仿真试验(为验证提出方法的有效性,本文做了如下的仿真试验.在整个试验过程中,工作环境为正方形区域,机器人初始点和目标点坐标分别为( , ,( , ,试验中需要的参数为: = ,= ,= , . , 显示混沌人工势场法可以避免传统人工势场法容易陷入局部极小点缺陷的试验见图 图 在易产生局部极小的情况下 ° 为机器人规划的路径 × ° 图 是利用文中提出的方法在容易出现局部极小点的凹形障碍情况下 为机器人规划的避碰路径 图 的场景为 一个障碍物沿直线从点运动到 同时有两个静止障碍物 这是最容易出现局部极小点

13、的情况 此时利用混沌人工势场法为机器人规划出了从点 到点 与障碍物无碰撞的路径 见图 中的曲线 其中直线为移动障碍物的路径图 表明 当两个障碍物之间的距离比图 大 但仍不能通过时 机器人只好绕过障碍物 如图 所示 当两个障碍物之间的距离大到允许机器人通过时 为机器人规划出可在两个障碍物之间通过的路径 见图 如此可见 本文提出的方法克服了传统人工势场法的缺陷 即机器人在距离近的障碍物之间不能发现通道的缺陷 图 在距离近的障碍物前面 ° 可以找到通道 ° °图 是在受到障碍物连续的随机干扰时 提出的方法可以为机器人找到到达目标点的路径 其中图为存在移动和静止障碍物时

14、机器人到达目标点的情况 图 中 存在两个移动障碍物 一个沿直线运动一个沿正弦曲线运动 此时 仍然可以从起点出发 为机器人规划出不与障碍物碰撞的到达目标点的路径第 卷第 期石鸿雁等 一种基于混沌优化算法的机器人路径规划方法图 在受到移动障碍物干扰时 ° 为机器人规划的路径 × °在存在移动障碍物时 实时规划的路径常出现突变点 图 使得规划的路径不光滑 给机器人跟踪规划好的路径带来困难 机器人足球赛中 若把足球作为目标 则目标点是移动的 为将加入平滑因子的混沌人工势场法引入足球机器人比赛中 对移动的目标点也做了仿真 其结果见图 图 中 考虑了目标点以恒定速率从点 沿直

15、线运动到点 同时环境中有两个沿随机曲线运动的障碍物时 机器人跟踪目标点且避开障碍物的情况 场景 表明 目标点以随机速率从点 沿直线到达点 机器人仍然能够跟踪目标点且避开两个随机障碍物的情况4混沌人工势场法与遗传人工势场法的比较(2与混沌人工势场法类似 所谓的遗传人工势场法 ° ° 就是将遗传算法与传统人工势场法相结合 把势函数作为目标函数 控制变量取为机器人行走的步长和方向角 利用传感器的信息 在每次采样后 通过遗传算法计算机器人下一周期行走的步长和方向角 从而确定下一个子目标点 如此下去 实时地为机器人规划路径为说明混沌人工势场法的优越性 本文还做了与遗传人工势场法比较的

16、试验 整个试验环境和参数与图 ! 完全一样 图中出现的曲线为利用遗传人工势场法规划的机器人路径 如图 所示 显然 图 的路径优于图 的路径 体现在当机器人距离障碍物比较远 不需要避障时 图 的路径为最优路径 在距离障碍物比较近时才避开障碍物 而当机器人距离障碍物比较远不需要避障时 遗传人工势场法规划的路径如图 所示并不是最优路径 图 目标点以不同方式移动且存在移动障碍物时 ° 为机器人规划的路径 × ° ¬ 机器人 年 月第 卷第 期 石鸿雁等 一种基于混沌优化算法的机器人路径规划方法 5 结论 ( 利用混沌人工势场法 能够在动态环境下实时 ! 有效地为

17、机器人规划出避碰局部最优路径 仿真试 验也充分表明 该方法可以摆脱传统人工势场法容 易陷入局部最优的缺陷 能够在比较靠近的障碍物 之间为机器人找到通道 在动态环境下 机器人可 以实时找到近优路径 只是易于出现突变点 当引入 平滑因子后 规划的机器人路径比较平滑 !易于跟 踪 这说明了文献 中提出的人工势场法的缺陷 都被成功地克服 同时引入平滑因子的混沌人工势 场法也可以用于足球机器人的避障规划 尽管提出 的混沌人工势场法得到了比较满意的结果 但是要 想将它应用于实际的足球机器人比赛 需要我们进 一步做许多工作 参考文献 ° ° 图 在与图 × 相同场景下利用遗传人工势场法 为机器人规划的路径 ° 图 表明 在距离近的障碍物 但机器人可以 ! 通过的 之间发现路径能力方面 遗传人工势场法不 如混沌人工势场法 图 与图 ! ( 的场景完全一样 可以看出即使两个障碍物之间的 距离允许机器人通过 遗传人工势场法也不能为机 器人规划出从两个障碍物之间通过的路径 虽然有 从两个障碍物之间通过的企图 但最终仍然不能实 现 赵忆文 谈大龙 基于速度场的移动障碍物局部在线避碰 ° ° ° ° × ° ° 2