增强蚁群算法的机器人最优路径规划

第 41卷 � 第 3期 2 0 0 9年 3月 � 哈 � 尔 � 滨 � 工 � 业 � 大 � 学 � 学 � 报 JOURNAL OF HARBIN INSTITUTE OF TECHNOLOGY � Vo l�41 N o�3 M ar. 2009 � � � � � � 增强蚁群算法的机器人最优路径规划 齐 � 勇 1, 2, 魏志强 2, 殷 � 波 2, 费云瑞2, 于忠达 2, 庄晓东2 ( 1.山东省科学院 海洋仪器仪表研究所, 青岛 266001; 2.中国海洋大学 计算机科学系, 青岛 266100) 摘 � 要: 为解决复杂环境中机器人最优路径规划问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 , 本文结合增强学习和人工势场法的原理, 提出一种基 于增强势场优化的机器人路径规划方法,引入增强学习思想对人工势场法进行自适应路径规划.再把该规划 结果作为先验知识, 对蚁群算法进行初始化, 提高了蚁群算法的优化效率, 同时克服了传统人工势场法的局 部极小问题. 仿真实验结果表明, 该方法在复杂环境中,对机器人的路径规划效果令人满意. 关键词: 增强学习;增强势场 ;蚁群算法; 最优路径 中图分类号: TP24 文献标识码: A 文章编号: 0367- 6234( 2009) 03- 0130- 04 Path planning optim ization based on reinforcem ent of artificial potential field Q IYong 1, 2 , WE IZh-i q iang 2 , Y IN Bo 2 , FE IYun-ru i 2 , YU Zhong-da 2 , ZHUANG X iao-dong 2 ( 1. Institute o f Oceanag raph ic Instrum entation, Shandong Academ y o f Sc ience, Q ingdao 266001, China; 2. Dept. of Com puter Science, Ocean Un iversity o f China, Q ingdao 266100, Ch ina) Abstract: In order to solve the problem o f opt imal path plann ing for robot in comp lex env ironmen,t a path plann ing method based on the artif icial po tent ia l field optim ization is proposed in th is paper. The ant algo rithm is initialized by the plann ing result o f the art ific ia l po tentia l field re inforcement as the prio r know ledge, w hich improves the a lgorithm � s e ff ic iency. On the other hand, the localm in ima prob lem in the artif icial po tent ia l fieldmethod is so lved successfully. The result o f simu lation show s tha t the method in this paperw orks w e ll in solv ing the relevan t prob lem s. Key words: learn ing reinforcemen;t po tent ia l field reinforcemen;t ant colony a lgorithm; optmi al path planning 收稿日期: 2006- 05- 27. 基金项目: 国家自然科学基金资助项目 ( 60374031) . 作者简介: 齐 � 勇 ( 1980� ) ,男,硕士; 魏志强 ( 1969� ) ,男,教授,博士生导师. � � 路径规划算法的性能直接影响移动机器人的 智能度.多障碍复杂环境中的路径规划是目前研 究的热点和难点之一. 较成熟的规划方法有人工 势场法、栅格法等 [ 1~ 3] .这类方法通过环境模型或 者局部动态搜索来规划一条可行路径,但是没有 考察路径是否最优.比如人工势场法中会产生局 部极小值,引起机器人路径的振荡摆动.诸多改进 方法基本是通过合理定义势场方程,保证势场中 不存在局部极值,但也没有考察路径是否最优. 为解决此问题, 统计启发式优化算法被应用 到路径规划问题中. 比如遗传算法、蚁群算法 [ 4] 等.这类方法通过解空间中的优化搜索得到最优 路径, 但是随着问题复杂度的增大, 解空间也增 大,使得优化收敛的速度变慢, 影响了路径规划效 率.本文首先把增强学习思想引入人工势场法,提 出状态评价函数和势场的对应关系,以及控制策 略和势场力方向的对应关系.机器人通过自学习, 自适应调整势场空间,得到优于传统人工势场法 的路径.又提出一种基于增强势场优化的机器人 最优路径规划方法.将增强势场法的最优解作为 先验知识,对蚁群算法的 参数 转速和进给参数表a氧化沟运行参数高温蒸汽处理医疗废物pid参数自整定算法口腔医院集中消毒供应 进行初始化,缩小了 蚁群算法的解空间,加快了收敛速度,同时优化结 果克服了人工势场法的局部极小问题. 1� 增强学习与增强势场优化方法 1�1� 增强学习 增强学习是一种无监督、自适应的学习方法, 不需要给定确切的训练集合, 通过利用决策和控 制过程中的反馈信息, 把学习和决策过程结合在 一起. 见图 1, Agent选择一个动作作用于环境, 环境接受该动作后状态发生变化, 同时产生一个 增强信号 (奖励或惩罚 ) 反馈给 Agen,t A gent根 据强化信号和环境状态再选择下一个动作. 选择 的原则是使受到正信号 (奖励 ) 的概率增大 [ 6 ] . 图 1� 增强学习原理 � � 系统的状态属于一个有限的状态集合 S, 控 制策略产生的决策结果属于一个有限的控制行为 集合 A.在路径规划中, S对应于离散化的环境状 态集合 (机器人的位置 ); A 对应于离散化的运动 控制行为集合.控制策略 �被定义成状态集合到 控制行为集合 A 的映射, 表达成函数的形式是: a = �(x ), x � S, a � A. 其含义是: 根据策略 �, 当观察到系统状态为 x时, 决策结果是控制行为 a.控制策略可以由一系列控制参数描述, 学习中 通过参数的调整, 来实现策略的调整. 强化信号 r 是执行某个控制行为后, 环境给决策系统的反馈 信号, 其大小反映了该控制行为的直接效果. 状态评价函数 V是某个状态和目标状态之间 距离的度量.其定义如下:在某种控制策略下,从某 个状态转移到目标状态的过程中,把增强信号加权 和的数学期望定义为该状态的评价函数值,即: V ( x ) = E �� t= 0 �t r t+ 1 |x 0= x . ( 1) 式中: E表示数学期望; �称为折扣因子,也是 ( 0, 1)之间的常数,在数学上使上式中的无穷级数收 敛; r t+ 1是 t+ 1时刻产生的增强信号值; x0表示 初始状态.某个状态的评价函数值越大,表示它距 离目标状态越近.从上述定义可知,状态评价函数 和控制策略是相联系的, 不同控制策略下的状态 评价函数可能不同. 增强学习使状态评价的估计 值逐渐逼近最优策略控制下的状态评价值, 同时 使控制策略逼近最优策略. 1�2� 增强势场法路径规划 需要让机器人沿最短路径绕过障碍物, 并到 达目标.从增强学习的角度来看,就是要寻找一个 最优控制策略, 使机器人不论从哪个初始位置出 发,都能沿最短路径到达目标. 1�2�1� 增强学习与人工势场法的融合 人工势场法是仿照物理学中电场的概念, 通 过建立以目标点及障碍为场源的虚拟势场, 按照 势场力的方向规划出可行的避障路径 [ 5] . 该方法 擅长局部路径规划,对于简单环境很有效,但对于 复杂的多障碍环境,容易产生局部极值点,会使机 器人未达到目标就停止运动,或者产生振荡、摆动 现象. 把环境状态 (即前述系统状态 )定义为某时 刻机器人在二维运动平面上的坐标,并把坐标离 散化, 以构成增强学习中所要求的有限的、离散的 状态集合.在计算机模拟实验中,把机器人运动平 面离散化成 32 � 32的网格. 对于控制行为集合, 把机器人的运动方向离散化成 8个运动方向: Eas,t W es,t No rth, South, Northeas,t Northw es,t Southeas,t Southw es.t 在路径规划问题中, 状态评价值对应了待优 化的势场,而控制策略对应了势场力.对于强化信 号 r ( t)作如下规定: ( 1) 如果 t时刻的决策结果使机器人到达目 标状态,则 r( t ) = + 1; ( 2) 如果 t时刻的决策结果没有使机器人到 达目标状态,则 r( t ) = - 1,即 r( t) = + 1, if s( t + 1) is goa l po in t; - 1, othe rw ise. ( 2) 1�2�2� 采用具有随机性质的控制策略 为了实现增强学习的探索机制, 实验中采用 具有随机性质的控制策略.对于每个环境状态 s, 8种不同的控制行为被赋予 8个不同的概率值: Pe ( s), Pw ( s), Pn ( s), P s ( s), Pne ( s), Pnw ( s), P se ( s), P sw ( s). 在状态 s下究竟采取哪种控制行 为,按照各自概率随机选取. 对所有可能的状态, 这些概率值构成一个决策概率矩阵. 于是控制策 略可以表达成决策概率矩阵 P: P = P e ( s1 ) Pw ( s1 )� P sw ( s1 ) P e ( s2 ) Pw ( s2 )� P sw ( s2 ) � � � P e ( sN ) Pw ( sN )� P sw ( sN ) . ( 3) 式中N代表状态的总数.在各种状态下,不同的控 制行为都可能被尝试. 随着学习过程的进行, 最优控制行为不断得 到加强,其概率值逼近 1.而控制策略也会逼近一 个最优策略.这一点在实验过程中得到了验证. 2� 蚁群优化算法 蚁群优化算法是 M arco Dor igo等 [ 7 ]学者提出 的一种优化算法.在蚁群算法中,问题的解被抽象 成在离散状态空间中从起始状态到达目标状态的 �131�第 3期 齐 � 勇, 等: 增强蚁群算法的机器人最优路径规划 状态转移序列,即从起始状态到目标状态的路径. 最优解对应着满足最优评价准则的状态转移序 列 [ 3] .我们的最优评价准则是状态转移序列的长 度最短,即所经过的路径最短. 蚂蚁从起始状态开始在相邻状态之间转移, 直到达到目标状态完成一次解的搜索. 路径强度 值是蚂蚁进行状态转移的依据. 每只蚂蚁的状态 转移是根据状态转移概率随机进行的. 从状态 si 转移到某个相邻状态 sj的状态转移概率 pij ( t) 定 义为 [ 5] pij ( t) = [�ij ( t) ]�� [ �ij ]�� sj� A llow ed [ �ij ( t) ]�� [ �ij ]�, if sj � A llow ed; 0, o therw ise. ( 4) 式中: �ij ( t)是第 t次搜索时 si和 sj之间的路径强 度值; �和 �是大于零的参数; �ij是 si和 sj之间距 离的倒数, 是一种启发信息; A llow ed是与 si相邻 的、并且当前的蚂蚁未经历的状态的集合. 在群体中所有的蚂蚁都完成一次搜索后, 对 每一个状态 si,路径强度按下式更新 [ 7 ] �ij ( t+ 1) = �� �ij ( t) + ��ij ( t, t + 1) . ( 5) 式中: �ij ( t)和 �ij ( t+ 1)分别是 si和相邻状态 sj 之间在更新前和更新后的路径强度值, �是常数 且 0 < �< 1. ��ij ( t, t+ 1)是路径强度更新值,定 义为 [ 7] ��ij ( t, t + 1) = �m k= 1 ��kij ( t, t + 1) . ( 6) 式中: m是群体中蚂蚁的个数; ��kij ( t, t + 1)是第 t次搜索时,第 k只蚂蚁在 si和 sj之间的路径上留 下的路径增强信息,定义为 [ 7] : ��kij ( t, t+ 1) = 1/Lk, if the k-th ant goes from si to sj a t the t- th loop; 0, othe rw ise. ( 7) 式中: 1 /Lk是第 k只蚂蚁经过路径长度的倒数, 路径长度越短,增强值越大.如果一条路径有越多 的蚂蚁经过,该路径强度值就增大地越快,又会吸 引更多的蚂蚁沿该路径移动. 3� 基于增强势场法的路径规划 3�1� 路径强度初始化 蚁群算法的求解过程包含两个方面: 初始解 的产生和在此基础上的优化. 由于蚁群算法的正 反馈机制,质量不高的初始解有可能使算法收敛 于次优解.因此, 获得高质量的初始解可以提高算 法性能. 本文把增强势场法的最优解作为蚁群算法路 径强度初始值 �ij ( 0). 对应于蚁群算法的离散状 态,将机器人的二维工作平面离散化.机器人的运 动方向也被离散化成 {M ove Eas,t M ove Wes,t M ove North, M ove South, M ove Northeas,t M ove N orthw es,t M ove Southeas,t M ove Southw est} 8个 方向. 初始化的计算过程如下: ( 1)对机器人工作空间中的每一个位置 si, 计算 si处的增强势场矢量 E ( si ): E ( si ) = A� �M k= 1 nki r 2 ki + B� n it r 2 ti . ( 8) 式中: A、B是大于零的常数, 用来权衡避障和到达 目标两个因素的相对重要性; M 是离散工作平面 中障碍点的个数; rki是第 k个障碍点到 si的距离, r ti是目标点到 si的距离; nk i是从第 k个障碍点指 向 si的单位矢量, nit是从 si指向目标点的单位矢 量. E ( si )的方向就是根据增强势场优化法得到 的在位置 si的机器人运动方向; ( 2)分别计算机器人 8个运动方向和 E ( si ) 的夹角 �i ( i = 1, 2, �, 8); ( 3)按照 �i从小到大的顺序, 对相应方向的 路径强度赋以从大到小的值.这样, 与 E ( si )夹角 越小的运动方向上,路径强度越大. 根据增强势场法进行初始化之后, 如果从起 始点开始按照路径强度最大的方向移动, 得到的 初始路径就是增强势场法的规划结果. 随着优化 过程的进行,初始路径上由于势场局部极小问题 引起的振荡和摆动会减少,最终得到最优路径.仿 真实验中,对每个位置 si, 8个运动方向对应的路 径强度按照和势场矢量 E ( si )夹角从小到大的顺 序, 依次被赋值为实数集 R: R = { 0�5, 0�16, 0�16, 0�05, 0�05, 0�03, 0�03, 0�02}. 3�2� 蚁群算法规划最优路径 经过路径强度值的初始化之后, 蚂蚁群体开 始从起始点进行路径搜索. 蚂蚁在相邻的位置之 间移动,每次移动都按照式 ( 4)所定义的概率随 机决定下一个位置.当蚂蚁到达目标点时就完成 一次搜索.群体中所有蚂蚁都完成一次搜索之后, 按照式 ( 5 )进行路径强度值的更新, 式 ( 7)中 Lk 是根据第 k只蚂蚁的轨迹得到的路径长度. 蚂蚁 群体的搜索过程不断循环, 直到所有蚂蚁收敛到 同一路径,或者搜索次数达到一个预先规定的最 大值为止. 4� 仿真实验结果 仿真实验中,机器人的二维工作空间被离散 �132� 哈 � 尔 � 滨 � 工 � 业 � 大 � 学 � 学 � 报 � � � � � � � � � � � � � 第 41卷 � 化成 32 � 32的网格. 图 2和图 3是 1组实验结 果.图中黑色区域表示障碍, � S�表示机器人起始 点 ( Start Point) , � G�表示目标点 ( Goa l Po int). 图 2� 人工势场法的规划结果 图 3� 增强势场的蚁群算法的规划结果 � � 图中的箭头表示机器人处于该位置时的运动 方向. 图 2机器人经过 46步到达目标点. 图 3机 器人经过 42步到达目标点. 图 2中圆圈所示区 域 ,机器人的路径由于人工势场的局部极小问题 发生摇摆.由图 3可以看出,本文提出方法有效地 解决了这一问题,使路径规划结果更为优化. 5� 结 � 语 提出了一种增强势场优化的路径规划方法, 根据增强势场优化法来初始化蚁群算法的参数, 提高了蚁群算法的优化效率. 同时克服了势场法 中局部极小问题,得到最优路径.仿真实验结果表 明,在复杂环境中,该方法能够有效地帮助机器人 进行最优路径搜索. 参考文献: [ 1] 石鸿雁,孙茂相,孙昌志.未知环境下移动机器人路径规 划方法 [ J].沈阳工业大学学报, 2005, 27( 1): 63- 69. [ 2] NAGAYUK IY, ISH II S, DOYA K. Mu lt-i agent re in fo- rcem ent lea rning: an app roach based on the other agent� s interna l mode l[ C ] / / P ro ceedings o f the IEEE 5th Internationa l Con ference on Mu lt-iAgent System s. Boston, MA, USA: IEEE, 2000: 215- 221. [ 3 ] BORENSTE IN J, KOREN Y. The vector fie ld h isto- g ram- fast obstac le avo idance for m obile robo ts [ J ]. IEEE Journal of Robo tics and Automa tion, 1991, 7( 3): 278- 288. [ 4] 金飞虎, 洪炳熔, 高庆吉. 基于蚁群算法的自由飞行 空间机器人路径规划 [ J] . 机器人, 2002, 24 ( 6 ): 526- 529. [ 5] 庄晓东, 孟庆春,高云 ,等. 复杂环境中基于人工势场 优化算法的最优路径规划 [ J]. 机器人, 2003, 25 ( 6): 530- 535. [ 6] 张汝波,周宁, 顾国昌,等. 基于强化学习的智能机器人 避碰方法研究 [ J]. 机器人, 1999, 21( 3): 204- 209. [ 7] DORIGO M, D i CARO G, GAMBARDELLA L M. Ant co lony optim iza tion [ C ] / /New M eta-H euristic P roceed- ings o f the Cong ress on Evo lutionary Com putation. W ash ing ton: [ s. n. ], 1999: 1470- 1477. (编辑 � 赵丽莹 ) �133�第 3期 齐 � 勇, 等: 增强蚁群算法的机器人最优路径规划