一种基于遗传算法参数优化的改进人工势场法

D0L:10.13374M.issm1001-053x.2012.02.015 第34卷第2期 北京科技大学学报 Vol.34 No.2 2012年2月 Journal of University of Science and Technology Beijing Feb.2012 一种基于遗传算法参数优化的改进人工势场法 李擎⑧王丽君陈博周洲尹怡欣 北京科技大学自动化学院，北京100083 ☒通信作者，E-mail:liging@ies.ustb.cdu.cm 摘要人工势场法是一种简单有效的移动机器人路径规划算法.针对传统人工势场法在路径规划中的一类目标点不可达 问题，提出了一种在局部最小点改变斥力角度和设定虚拟最小局部区域的解决方案，同时采用遗传算法对改进算法中斥力改 变角度以及虚拟最小局部区域的半径两个参数进行优化.仿真实验说明本文所提算法能在起点和终点之间规划出一条简捷、 光滑和安全的路径. 关键词路径规划：移动机器人：人工势场法；遗传算法 分类号TP242.6 An improved artificial potential field method with parameters optimization based on genetic algorithms LI Qing☒，WANG Lijun,CHEN Bo,ZHOU Zhou,,YINi-xin School of Automation,University of Science and Technology Beijing.Beijing 100083.China Corresponding author,E-mail:liging@ies.ustb.edu.cn ABSTRACT The artificial potential field method is a simple and efficient path planning algorithm for mobile robots.Aiming at a kind of goal unreachable problem in traditional artificial potential field methods,an improved algorithm which changes the angle of repulsion at the local minimum point and sets the virtual local minimum area was proposed for problem-solving.The genetic algorithm was also introduced to optimize the parameters,i.e.the revolved angle of repulsion and the radius of the virtual local minimum area for the im- proved artificial potential field algorithm.It is proved that the proposed algorithm can plan out a simple,smooth and safe optimum path connecting the start point and the end point by simulation experiments. KEY WORDS path planning:mobile robots;artificial potential fields;genetic algorithms 路径规划是指移动机器人按照某一性能指标要达问题（局部最小问题）[6.国内外学者针对此问 求搜索一条从起始状态到目标状态最优或次优路径 题提出了很多方法：文献[7]提出了一种虚拟障碍 的过程，它是移动机器人研究领域中的一个重要分 物的算法，较好地解决了局部最小问题：文献[8]提 支，是移动机器人导航与控制的基础).路径规划 出了一种基于“沿边行走”的算法，使机器人沿着障 可分为基于已知环境的全局路径规划和基于未知环 碍物的边缘运动，同样成功地解决了局部最小问题： 境的局部路径规划).移动机器人路径规划的常用 文献[9]提出一种通过附加控制力的方法使移动机 方法有人工神经网络、遗传算法)、模糊逻辑方法 器人逃离局部最小点，进而完成路径规划任务.本 和人工势场artificial potential field,APF)法等. 文对传统人工势场法中一类目标不可达问题（局部 人工势场法作为经典而高效的路径规划算法， 最小问题出现的原因进行了分析，提出了一种通 虽然具有实时性好、路径安全性平滑性好等优点，但 过改变斥力角度和设置虚拟局部最小区域解决以上 仍然存在很多有待解决和探索的问题，如目标不可 问题的方法.该方法虽然保留了传统人工势场法的 收稿日期：2010-1201 基金项目：教育部第36批“留学回国人员科研启动基金”资助项目(1341)：国家自然科学基金资助项目(60374032)：北京市重点学科建设资 助项目(XK100080537)

第 34 卷 第 2 期 2012 年 2 月 北京科技大学学报 Journal of University of Science and Technology Beijing Vol． 34 No． 2 Feb． 2012 一种基于遗传算法参数优化的改进人工势场法 李 擎 王丽君 陈 博 周 洲 尹怡欣 北京科技大学自动化学院，北京 100083 通信作者，E-mail: liqing@ ies． ustb． edu． cn 摘 要 人工势场法是一种简单有效的移动机器人路径规划算法． 针对传统人工势场法在路径规划中的一类目标点不可达 问题，提出了一种在局部最小点改变斥力角度和设定虚拟最小局部区域的解决方案，同时采用遗传算法对改进算法中斥力改 变角度以及虚拟最小局部区域的半径两个参数进行优化． 仿真实验说明本文所提算法能在起点和终点之间规划出一条简捷、 光滑和安全的路径． 关键词 路径规划; 移动机器人; 人工势场法; 遗传算法 分类号 TP242. 6 An improved artificial potential field method with parameters optimization based on genetic algorithms LI Qing ，WANG Li-jun，CHEN Bo，ZHOU Zhou，YIN Yi-xin School of Automation，University of Science and Technology Beijing，Beijing 100083，China Corresponding author，E-mail: liqing@ ies． ustb． edu． cn ABSTRACT The artificial potential field method is a simple and efficient path planning algorithm for mobile robots． Aiming at a kind of goal unreachable problem in traditional artificial potential field methods，an improved algorithm which changes the angle of repulsion at the local minimum point and sets the virtual local minimum area was proposed for problem-solving． The genetic algorithm was also introduced to optimize the parameters，i． e． the revolved angle of repulsion and the radius of the virtual local minimum area for the im￾proved artificial potential field algorithm． It is proved that the proposed algorithm can plan out a simple，smooth and safe optimum path connecting the start point and the end point by simulation experiments． KEY WORDS path planning; mobile robots; artificial potential fields; genetic algorithms 收稿日期: 2010--12--01 基金项目: 教育部第 36 批“留学回国人员科研启动基金”资助项目( 1341) ; 国家自然科学基金资助项目( 60374032) ; 北京市重点学科建设资 助项目( XK100080537) 路径规划是指移动机器人按照某一性能指标要 求搜索一条从起始状态到目标状态最优或次优路径 的过程，它是移动机器人研究领域中的一个重要分 支，是移动机器人导航与控制的基础［1］． 路径规划 可分为基于已知环境的全局路径规划和基于未知环 境的局部路径规划［2］． 移动机器人路径规划的常用 方法有人工神经网络、遗传算法［3］、模糊逻辑方法［4］ 和人工势场( artificial potential field，APF) 法［5］等． 人工势场法作为经典而高效的路径规划算法， 虽然具有实时性好、路径安全性平滑性好等优点，但 仍然存在很多有待解决和探索的问题，如目标不可 达问题( 局部最小问题) ［6］． 国内外学者针对此问 题提出了很多方法: 文献［7］提出了一种虚拟障碍 物的算法，较好地解决了局部最小问题; 文献［8］提 出了一种基于“沿边行走”的算法，使机器人沿着障 碍物的边缘运动，同样成功地解决了局部最小问题; 文献［9］提出一种通过附加控制力的方法使移动机 器人逃离局部最小点，进而完成路径规划任务． 本 文对传统人工势场法中一类目标不可达问题( 局部 最小问题) 出现的原因进行了分析，提出了一种通 过改变斥力角度和设置虚拟局部最小区域解决以上 问题的方法． 该方法虽然保留了传统人工势场法的 DOI:10.13374/j.issn1001-053x.2012.02.015

第2期 李擎等：一种基于遗传算法参数优化的改进人工势场法 ·203· 所有优点，但其在应用过程中仍然存在一个重要的 问题：斥力改变角度和虚拟局部最小区域半径两个 参数的选取具有一定的随机性，且其值的大小将直 接关系到路径规划解的质量和规划时间的长短.为 障碍物影响范围 合力 了解决这个问题，本文又提出采用遗传算法优化斥 斥力 障碍物 力改变角度和虚拟局部最小区域半径两个参数，从 …⊙目标点 而得到一种基于遗传算法的改进人工势场法，多种 规划环境下的仿真研究说明了本文所提算法的有 效性. 1针对一类目标不可达问题的改进人工势 图2改变斥力角度的人工势场法受力分析 场法 Fig.2 Force analysis of the artificial potential field method with changing the angle of repulsion 1.1目标不可达的原因分析及基本改进思想 当机器人和目标点在同一条直线并且障碍物位 离开局部最小点P而到达Q点，下一步的合力又可 于两者之间时，根据人工势场法的基本原理可知，机 能驱使机器人从Q点运动到M点，此点所受到的合 器人在向目标点和障碍物移动过程中，引力不断减 力又会驱使机器人回到P点，就好像存在一个使机 小，斥力不断增大.因此，必然存在一点使得机器人 器人无法摆脱的局部最小区域（等势面）一样，如图 所受的斥力与引力恰好大小相等、方向相反.此时， 3所示.为了解决以上问题，本文又提出了虚拟局 机器人所受合力为零，机器人将停在障碍物前.此 部最小区域的概念，即为机器人设定一个局部最小 点是环境中的局部最小点，使得机器人路径规划无 区域，该区域是以局部最小点P为圆心，以参数r为 法顺利完成，如图1所示 半径的一个圆.当机器人尚未离开局部最小区域 前，始终使用改进算法进行路径规划：当机器人脱离 局部最小区域后，再切换回传统人工势场法.这样 既能解决规划过程中存在的上述问题，又能保持传 障碍物影响范围 统人工势场法的优点 斥力 引力 障碍物 十.⊙目标点 机器人 障碍物影响范围 障碍物 图1一种人工势场法中的目标点不可达情况 -○目标点 Fig.1 A kind of unreachable case in artificial potential field method 机器人 虚拟局部最小范围 本文提出的改进算法，其基本思想如下：一日机 器人陷入局部最小，将斥力的角度顺时针或逆时针 旋转一个角度9(-90°≤0≤90°，如果角度超出了 这个范围则斥力会使机器人靠近障碍物从而导致碰 图3路径规划中的虚拟局部最小区域问题 撞发生)，这样不仅仍能保证斥力使机器人远离障 Fig.3 Virtual local minimum area in path planning 碍物，也使得斥力和引力不在同一直线上，进而使得 合力不为零，迫使机器人走出局部最小点，继续完成 通过分析不难发现：参数r如果取得过小，机器 机器人的路径规划工作，改进算法对应的受力图如 人可能无法摆脱局部最小区域：？如果取得过大，路 图2所示. 径规划过程中调用改进人工势场法的次数将有所增 1.2虚拟局部最小区域概念的提出 加，从而会影响规划路径的安全性 当应用以上改进算法进行路径规划时，偶尔会 1.3仿真研究 发生以下现象：应用改进算法时，即便使机器人暂时 图4所示为存在多个障碍物的规划环境，其中

第 2 期 李 擎等: 一种基于遗传算法参数优化的改进人工势场法 所有优点，但其在应用过程中仍然存在一个重要的 问题: 斥力改变角度和虚拟局部最小区域半径两个 参数的选取具有一定的随机性，且其值的大小将直 接关系到路径规划解的质量和规划时间的长短． 为 了解决这个问题，本文又提出采用遗传算法优化斥 力改变角度和虚拟局部最小区域半径两个参数，从 而得到一种基于遗传算法的改进人工势场法，多种 规划环境下的仿真研究说明了本文所提算法的有 效性． 1 针对一类目标不可达问题的改进人工势 场法 1. 1 目标不可达的原因分析及基本改进思想 当机器人和目标点在同一条直线并且障碍物位 于两者之间时，根据人工势场法的基本原理可知，机 器人在向目标点和障碍物移动过程中，引力不断减 小，斥力不断增大． 因此，必然存在一点使得机器人 所受的斥力与引力恰好大小相等、方向相反． 此时， 机器人所受合力为零，机器人将停在障碍物前． 此 点是环境中的局部最小点，使得机器人路径规划无 法顺利完成，如图 1 所示． 图 1 一种人工势场法中的目标点不可达情况 Fig． 1 A kind of unreachable case in artificial potential field method 本文提出的改进算法，其基本思想如下: 一旦机 器人陷入局部最小，将斥力的角度顺时针或逆时针 旋转一个角度 θ( － 90°≤θ≤90°，如果角度超出了 这个范围则斥力会使机器人靠近障碍物从而导致碰 撞发生) ，这样不仅仍能保证斥力使机器人远离障 碍物，也使得斥力和引力不在同一直线上，进而使得 合力不为零，迫使机器人走出局部最小点，继续完成 机器人的路径规划工作，改进算法对应的受力图如 图 2 所示． 1. 2 虚拟局部最小区域概念的提出 当应用以上改进算法进行路径规划时，偶尔会 发生以下现象: 应用改进算法时，即便使机器人暂时 图 2 改变斥力角度的人工势场法受力分析 Fig． 2 Force analysis of the artificial potential field method with changing the angle of repulsion 离开局部最小点 P 而到达 Q 点，下一步的合力又可 能驱使机器人从 Q 点运动到 M 点，此点所受到的合 力又会驱使机器人回到 P 点，就好像存在一个使机 器人无法摆脱的局部最小区域( 等势面) 一样，如图 3 所示． 为了解决以上问题，本文又提出了虚拟局 部最小区域的概念，即为机器人设定一个局部最小 区域，该区域是以局部最小点 P 为圆心，以参数 r 为 半径的一个圆． 当机器人尚未离开局部最小区域 前，始终使用改进算法进行路径规划; 当机器人脱离 局部最小区域后，再切换回传统人工势场法． 这样 既能解决规划过程中存在的上述问题，又能保持传 统人工势场法的优点． 图 3 路径规划中的虚拟局部最小区域问题 Fig． 3 Virtual local minimum area in path planning 通过分析不难发现: 参数 r 如果取得过小，机器 人可能无法摆脱局部最小区域; r 如果取得过大，路 径规划过程中调用改进人工势场法的次数将有所增 加，从而会影响规划路径的安全性． 1. 3 仿真研究 图 4 所示为存在多个障碍物的规划环境，其中 ·203·

·204· 北京科技大学学报 第34卷 S为起点，G为目标点.采用传统人工势场法机器人 (4)计算种群中各个体适应度函数值∫，取f= 陷入局部最小点P,,这时启用改进人工势场法，随 1/J:,J:为第i个个体对应的路径长度 机选取0=70°，r=0.6,11步后切回传统人工势场 (5)采用适应度比例选择法对个体进行选择， 法.当机器人继续按照传统人工势场法规划的路径 即根据个体i的适应度占总适应度∑f的比例f/ 运动到P2,此时又会陷入局部最小点，再次启用改 ∑∫确定该个体被选择复制的概率. 进人工势场法，0和r的选取仍为原值，21步后再 (6)采用单点交叉和单点变异算子对种群 次切回传统人工势场法，直至到达目标点G,整个路 P()进行遗传操作，产生下一代种群P(k+1). 径长度为17.5. 其中交叉概率P。与变异概率P。分别取为o (1) 10r 0m00000080G P。=e~ash/c pm eo.it/c -1. (2) 式中，k为当前进化代数，G为预先设定的最大迭 代次数. (7)重复步骤(4)~(6)，直至参数连续10代 不再发生变化或达到预先设定的最大迭代次数. 2.3基于遗传算法参数优化的仿真研究 本文对如图4所示环境下改进人工势场法中的 参数进行优化.这里取最大迭代次数G=50,种群 规模size=10,编码长度codel=6,偏转角度0为 88 12345678910 -90°~90°，局部最小范围半径r为0.1~2.经过 图4多个障碍环境下改进人工势场法的仿真结果 26步迭代，算法收敛.此时参数优化结果为9t= Fig.4 Simulation result of the improved artificial potential field -35°，rt=0.67,对应于以上两个最优参数时的路 method in a multiple obstacle environment 径规划结果如图5所示，其路径长度为16.6.该路 径长度明显小于优化前图4中最优路径的长度 2改进人工势场算法的参数优化 2.1参数优化目的 本文提出的改进算法中引入了两个新的参数： 斥力改变角度0和虚拟局部最小区域半径.0选择 合适可以使改进算法获得较短的路径长度，而合理 r的选择更是直接关系到改进算法能否真正摆脱局 部最小区域的关键所在.为了克服0和r选取的随 机性，改善路径规划的效果，本文提出采用遗传算法 (genetic algorithm,GA)对这两个参数进行优化. 2.2基于遗传算法的参数优化 遗传算法的基本思想近似于自然选择的生物进 012345678910 化，是一种模仿生物进化过程的随机方法.本文中， 图5基于遗传算法优化参数的改进人工势场法仿真结果 选取路径长度作为适应度函数.利用遗传算法对改 Fig.5 Simulation result of the improved artificial potential field method with parameters optimization based on genetic algorithm 进人工势场法引入参数进行寻优的具体步骤如下. (1)确定遗传算法最大迭代次数G、参数0和r 参数整定过程中最优路径长度J的变化如图6 的允许范围. 所示 (2)确定参数编码方式和长度.两个参数均采 3U型槽环境下不同算法的对比研究 用codel位二进制字符进行编码，故而染色体上基 因总长度为2×codel,记为P=PP2P2oa: U型槽是路径规划中的典型环境，由于采用传 (3)随机产生size个个体构成初始种群P(0), 统人工势场法进行路径规划时常常会使机器人陷入 i=1,2,…,size. 局部最小点，因此受到相关研究者的广泛关注.本

北 京 科 技 大 学 学 报 第 34 卷 S 为起点，G 为目标点． 采用传统人工势场法机器人 陷入局部最小点 P1，这时启用改进人工势场法，随 机选取 θ = 70°，r = 0. 6，11 步后切回传统人工势场 法． 当机器人继续按照传统人工势场法规划的路径 运动到 P2，此时又会陷入局部最小点，再次启用改 进人工势场法，θ 和 r 的选取仍为原值，21 步后再 次切回传统人工势场法，直至到达目标点 G，整个路 径长度为 17. 5． 图 4 多个障碍环境下改进人工势场法的仿真结果 Fig． 4 Simulation result of the improved artificial potential field method in a multiple obstacle environment 2 改进人工势场算法的参数优化 2. 1 参数优化目的 本文提出的改进算法中引入了两个新的参数: 斥力改变角度 θ 和虚拟局部最小区域半径 r． θ 选择 合适可以使改进算法获得较短的路径长度，而合理 r 的选择更是直接关系到改进算法能否真正摆脱局 部最小区域的关键所在． 为了克服 θ 和 r 选取的随 机性，改善路径规划的效果，本文提出采用遗传算法 ( genetic algorithm，GA) 对这两个参数进行优化． 2. 2 基于遗传算法的参数优化 遗传算法的基本思想近似于自然选择的生物进 化，是一种模仿生物进化过程的随机方法． 本文中， 选取路径长度作为适应度函数． 利用遗传算法对改 进人工势场法引入参数进行寻优的具体步骤如下． ( 1) 确定遗传算法最大迭代次数 G、参数 θ 和 r 的允许范围． ( 2) 确定参数编码方式和长度． 两个参数均采 用 codel 位二进制字符进行编码，故而染色体上基 因总长度为 2 × codel，记为 P = p1 p2…p2codel ． ( 3) 随机产生 size 个个体构成初始种群Pi ( 0) ， i = 1，2，…，size． ( 4) 计算种群中各个体适应度函数值 fi，取 fi = 1 /Ji，Ji为第 i 个个体对应的路径长度． ( 5) 采用适应度比例选择法对个体进行选择， 即根据个体 i 的适应度 fi 占总适应度∑f 的比例fi ∑f 确定该个体被选择复制的概率． ( 6) 采用单点交叉和单点变异 算 子 对 种 群 Pi ( k) 进行遗传操作，产生下一代种群 Pi ( k + 1) ． 其中交叉概率 pc 与变异概率 pm 分别取为［10］ pc = e － 0. 5k /G ． ( 1) pm = e 0. 1k /G － 1． ( 2) 式中，k 为当前进化代数，G 为预先设定的最大迭 代次数． ( 7) 重复步骤( 4) ～ ( 6) ，直至参数连续 10 代 不再发生变化或达到预先设定的最大迭代次数． 2. 3 基于遗传算法参数优化的仿真研究 本文对如图 4 所示环境下改进人工势场法中的 参数进行优化． 这里取最大迭代次数 G = 50，种群 规模 size = 10，编码长度 codel = 6，偏转角度 θ 为 － 90° ～ 90°，局部最小范围半径 r 为 0. 1 ～ 2． 经过 26 步迭代，算法收敛． 此时参数优化结果为 θbest = － 35°，rbest = 0. 67，对应于以上两个最优参数时的路 径规划结果如图 5 所示，其路径长度为 16. 6． 该路 径长度明显小于优化前图 4 中最优路径的长度． 图 5 基于遗传算法优化参数的改进人工势场法仿真结果 Fig． 5 Simulation result of the improved artificial potential field method with parameters optimization based on genetic algorithm 参数整定过程中最优路径长度 J 的变化如图 6 所示． 3 U 型槽环境下不同算法的对比研究 U 型槽是路径规划中的典型环境，由于采用传 统人工势场法进行路径规划时常常会使机器人陷入 局部最小点，因此受到相关研究者的广泛关注． 本 ·204·

第2期 李擎等：一种基于遗传算法参数优化的改进人工势场法 ·205· 20.0r 。改进算法路径点 9 ◆基于CA的改进算法路径点 19.0 18.5 18.0 -5 18.5 17.0 2 16.5 0 1015 20.25 30 进化代数 12345678910 图6改进人工势场法参数整定过程中最优路径长度的变化 图8第二种U型槽时的路径规划 Fig.6 Change of the optimal path length in the parameters tuning Fig.8 Path planning in the second U-groove environment process of the improved artificial potential field method 文针对三种不同的U型槽情况，分别运用本文中提 取0=-30°，r=0.5时，路径长度为18.3.采用遗 出的改进算法以及基于遗传算法参数优化的改进算 传算法进行优化后的0=-50°，r=0.7,对应的最优 法进行路径规划. 路径长度为16.9. 3.1第一种U型槽情况 。改进算法路径点 针对如图7所示的第一种U型槽情况，随机选 9 +基于GA的改进算法路径点 取0=80°，r=0.6时路径长度为13.4.采用遗传算 8 法进行优化后0=60°，r=0.7,对应的最优路径长度 7 为12.1. 6 10「。改进算法路径点 9 ◆基于GA的改进算法路径点 345678910 图9第三种U型槽时的路径规划 Fig.9 Path planning in the third U-groove environment 3.4统计意义下的对比结果 2345678910 为了更好地说明遗传算法参数优化的作用，本 文在三种不同U型槽环境下分别将改进人工势场 图7第一种U型槽时的路径规划 Fig.7 Path planning in the first U-groove environment 法的参数0取为±15°、±30°、±45°、±60°和 ±75°，此时为了确保不出现再次回到局部最小的现 3.2第二种U型槽情况 象，r应取得较大一些，这里r取为固定值0.7，这10 针对如图8所示的第二种U型槽情况，随机选 种情况得到一个平均最优路径长度.考虑到遗传算 取0=60°，r=0.5时，路径长度为14.8.采用遗传 法初始参数选取的随机性，本文连续使用五次遗传 算法进行优化后0=20°，r=0.4,对应的最优路径长 算法进行参数优化，得到另一个平均最优路径长度， 度为13.1. 其结果如表1所示.从表1可以看出，基于遗传算 3.3第三种U型槽情况 法的改进人工势场法在一定程度上减小了路径规划 针对如图9所示的第三种U型槽情况，随机选 的长度

第 2 期 李 擎等: 一种基于遗传算法参数优化的改进人工势场法 图 6 改进人工势场法参数整定过程中最优路径长度的变化 Fig． 6 Change of the optimal path length in the parameters tuning process of the improved artificial potential field method 文针对三种不同的 U 型槽情况，分别运用本文中提 出的改进算法以及基于遗传算法参数优化的改进算 法进行路径规划． 3. 1 第一种 U 型槽情况 针对如图 7 所示的第一种 U 型槽情况，随机选 取 θ = 80°，r = 0. 6 时路径长度为 13. 4． 采用遗传算 法进行优化后 θ = 60°，r = 0. 7，对应的最优路径长度 为 12. 1． 图 7 第一种 U 型槽时的路径规划 Fig． 7 Path planning in the first U-groove environment 3. 2 第二种 U 型槽情况 针对如图 8 所示的第二种 U 型槽情况，随机选 取 θ = 60°，r = 0. 5 时，路径长度为 14. 8． 采用遗传 算法进行优化后 θ = 20°，r = 0. 4，对应的最优路径长 度为 13. 1． 3. 3 第三种 U 型槽情况 针对如图 9 所示的第三种 U 型槽情况，随机选 图 8 第二种 U 型槽时的路径规划 Fig． 8 Path planning in the second U-groove environment 取 θ = － 30°，r = 0. 5 时，路径长度为 18. 3． 采用遗 传算法进行优化后的 θ = － 50°，r = 0. 7，对应的最优 路径长度为 16. 9． 图 9 第三种 U 型槽时的路径规划 Fig． 9 Path planning in the third U-groove environment 3. 4 统计意义下的对比结果 为了更好地说明遗传算法参数优化的作用，本 文在三种不同 U 型槽环境下分别将改进人工势场 法的 参 数 θ 取 为 ± 15°、± 30°、± 45°、± 60° 和 ± 75°，此时为了确保不出现再次回到局部最小的现 象，r 应取得较大一些，这里 r 取为固定值 0. 7，这 10 种情况得到一个平均最优路径长度． 考虑到遗传算 法初始参数选取的随机性，本文连续使用五次遗传 算法进行参数优化，得到另一个平均最优路径长度， 其结果如表 1 所示． 从表 1 可以看出，基于遗传算 法的改进人工势场法在一定程度上减小了路径规划 的长度． ·205·

·206· 北京科技大学学报 第34卷 表1三种方法处理U型槽环境的路径长度 Univ Sci,2005,6A(6):549 Table 1 Path length calculated by the three methods in the three U- [4]Mucientes M.Moreno D L.Bugarin A.et al.Design of a fuzzy groove environments controller in mobile robotics using genetic algorithms.Appl Soft 第一种 第二种 第三种 Comput,2007,7(2):540 方法 U型槽 U型槽 0型槽 [5] Luo S H.Liu G R.Jiang Y.A path planning of mobile robot 传统人工势场法 不可达 不可达 不可达 based on improved artificial potential field method.Microcomput 改进人工势场法 13.8 14.2 18.1 mf,2009,25(29):188 (罗胜华，刘国荣，蒋燕.一种基于改进人工势场法的移动机 基于GA的改进人工势场法12.1 13.0 16.9 器人路径规划.微计算机信息，2009,25(29)：188) [6] Wang J.Wu X B.Xu Z L.A path planning algorithm avoiding a 4结论 class of local minima in artificial potential field.Comput Simul, 2007,24(11):151 本文提出了一种基于遗传算法优化参数的改进 (王佳，吴晓蓓，徐志良.避免人工势场中一类局部极小值的 人工势场法，该算法通过改变斥力角度和设置虚拟 规划方法.计算机仿真，2007,24(11)：151) 局部最小区域的方法解决一类目标不可达问题，同 [7]Park M G.Lee M C.Artificial potential field based path planning 时采用遗传算法对以上改进算法中的两个参数进行 for mobile robots using a virtual obstacle concept//Proceedings of 优化.含有多个障碍物以及三种不同U型槽环境下 the 2003 IEEE/ASME International Conference on Advanced Intelli- gent Mechatronics,2003:735 的仿真研究说明本文所提算法具有以下几个特点： [8]Zhang M K,Li L S.A method for solving local minimization prob- (1)保持了传统人工势场法的部分优越性，即算法 lem of artificial potential field.Comput Technol Dev,2007.17 简单、路径安全性平滑性好：(2)克服了传统人工势 (5):137 场法存在局部最小的不足：(3)遗传算法的引入在 (张明开，李龙澍.关于人工势场法局部极小问题的一种解决 一定程度上减小了最优路径的长度 方法.计算机技术与发展，2007,17(5)：137) [9]Zhang J Y.Zhao Z P.Liu D.A path planning method for mobile 参考文献 robot based on artificial potential field.J Harbin Inst Technol, [1]Zhang Y.Luo Y.Zheng T X.Mobile Robot Technology and Its 2006.38(8):1306 Applications.Beijing:Electronics Industry Press.2007 (张建英，赵志萍，刘暾.基于人工势场法的机器人路径规划 (张毅，罗元，郑太雄.移动机器人技术及其应用.北京：电子 哈尔滨工业大学学报，2006,38(8)：1306) 工业出版社，2007 [10]Kuang F.Wang Y N.Robot path planning based on hybrid artifi- [2]Jia Y H.Mei F X.Simple path planning for mobile robots in the cial potential field/genetic algorithm.Syst Simul,2006,18 present of obstacles.J Beijing Inst Technol,2002,11(2):208 (3):774 [3]Du X.Chen HH.Gu W K.Neural network and genetic algorithm (况菲，王耀南.基于混合人工势场一遗传算法的移动机器 based global path planning in a static environment.I Zhejiang 人路径规划仿真研究.系统仿真学报，2006,18(3)：774)

北 京 科 技 大 学 学 报 第 34 卷 表 1 三种方法处理 U 型槽环境的路径长度 Table 1 Path length calculated by the three methods in the three U￾groove environments 方法 第一种 U 型槽 第二种 U 型槽 第三种 U 型槽 传统人工势场法 不可达 不可达 不可达 改进人工势场法 13. 8 14. 2 18. 1 基于 GA 的改进人工势场法 12. 1 13. 0 16. 9 4 结论 本文提出了一种基于遗传算法优化参数的改进 人工势场法，该算法通过改变斥力角度和设置虚拟 局部最小区域的方法解决一类目标不可达问题，同 时采用遗传算法对以上改进算法中的两个参数进行 优化． 含有多个障碍物以及三种不同 U 型槽环境下 的仿真研究说明本文所提算法具有以下几个特点: ( 1) 保持了传统人工势场法的部分优越性，即算法 简单、路径安全性平滑性好; ( 2) 克服了传统人工势 场法存在局部最小的不足; ( 3) 遗传算法的引入在 一定程度上减小了最优路径的长度． 参 考 文 献 ［1］ Zhang Y，Luo Y，Zheng T X． Mobile Robot Technology and It's Applications． Beijing: Electronics Industry Press，2007 ( 张毅，罗元，郑太雄． 移动机器人技术及其应用． 北京: 电子 工业出版社，2007) ［2］ Jia Y H，Mei F X． Simple path planning for mobile robots in the present of obstacles． J Beijing Inst Technol，2002，11( 2) : 208 ［3］ Du X，Chen H H，Gu W K． Neural network and genetic algorithm based global path planning in a static environment． J Zhejiang Univ Sci，2005，6A( 6) : 549 ［4］ Mucientes M，Moreno D L，Bugarin A，et al． Design of a fuzzy controller in mobile robotics using genetic algorithms． Appl Soft Comput，2007，7( 2) : 540 ［5］ Luo S H，Liu G R，Jiang Y． A path planning of mobile robot based on improved artificial potential field method． Microcomput Inf，2009，25( 29) : 188 ( 罗胜华，刘国荣，蒋燕． 一种基于改进人工势场法的移动机 器人路径规划． 微计算机信息，2009，25( 29) : 188) ［6］ Wang J，Wu X B，Xu Z L． A path planning algorithm avoiding a class of local minima in artificial potential field． Comput Simul， 2007，24( 11) : 151 ( 王佳，吴晓蓓，徐志良． 避免人工势场中一类局部极小值的 规划方法． 计算机仿真，2007，24( 11) : 151) ［7］ Park M G，Lee M C． Artificial potential field based path planning for mobile robots using a virtual obstacle concept / / Proceedings of the 2003 IEEE /ASME International Conference on Advanced Intelli￾gent Mechatronics，2003: 735 ［8］ Zhang M K，Li L S． A method for solving local minimization prob￾lem of artificial potential field． Comput Technol Dev，2007，17 ( 5) : 137 ( 张明开，李龙澍． 关于人工势场法局部极小问题的一种解决 方法． 计算机技术与发展，2007，17( 5) : 137) ［9］ Zhang J Y，Zhao Z P，Liu D． A path planning method for mobile robot based on artificial potential field． J Harbin Inst Technol， 2006，38( 8) : 1306 ( 张建英，赵志萍，刘暾． 基于人工势场法的机器人路径规划． 哈尔滨工业大学学报，2006，38( 8) : 1306) ［10］ Kuang F，Wang Y N． Robot path planning based on hybrid artifi￾cial potential field /genetic algorithm． J Syst Simul，2006，18 ( 3) : 774 ( 况菲，王耀南． 基于混合人工势场—遗传算法的移动机器 人路径规划仿真研究． 系统仿真学报，2006，18( 3) : 774) ·206·