D0I:10.13374/1.issm100103.2008.03.019 第30卷第3期 北京科技大学学报 Vol.30 No.3 2008年3月 Journal of University of Science and Technology Beijing Mar,2008 自适应遗传算法在移动机器人路径规划中的应用 李擎) 冯金玲1) 柳延领)周洲)尹怡欣) 1)北京科技大学信息工程学院，北京1000832)唐山学院，唐山063000 摘要将一种自适应遗传算法应用于移动机器人路径规划·提出了一种基于几何避障法的初始种群产生算法：设计了基于 启发式知识的交叉、变异、求精和删除算子：采用一种新的模糊逻辑控制算法自适应地调节交叉概率和变异概率：对移动机器 人离线和在线规划问题进行了仿真研究·仿真结果表明：自适应遗传算法具有较快的搜索速度、较高的搜索质量以及较强的 自适应能力，为移动机器人最优路径规划问题的解决提供了一种新方法 关键词移动机器人；最优路径规划；自适应；遗传算法：模糊控制 分类号TP18;TP273+.4 Application of adaptive genetic algorithm to optimum path planning of mobile robots LI Qing,FENG Jinling,LIU Yanling2),ZHOU Zhou).YIN Yixin) 1)School of Information Engineering.University of Science and Technology Beijing.Beijing 100083,China 2)Tangshan College.Tangshan 063000.China ABSTRACI An adaptive genetic algorithm for the optimum path planning problem of a mobile robot was proposed.The research project was carried out from four aspects:a geometry obstacle avoiding algorithm was developed to generate initial population:the crossover,mutation,improving and deletion operators which base on heuristic knowledge were designed for path planning:a new kind of fuzzy logic control algorithm was adopted to self-adaptively adjust the probabilities of crossover and mutation:simulation stud- ies in both off-line and on-line environments were implemented.The simulation results show that the adaptive genetic algorithm has advantages such as rapid search speed.high search quality and strong self-adaptability.It is a new approach for solving the optimum path planning problem of a mobile robot. KEY WORDS mobile robot:optimum path planning:adaptive:genetic algorithm:fuzy control 所谓移动机器人的路径规划，就是指在一个含 研究如何在含有障碍的环境空间中为移动机器人规 有障碍的环境中，为移动机器人找出一条从起始节 划出一条从起始节点到目标节点的最短无障碍 点到目标节点的连通路径（避开障碍点），当然这条 路径 连通路径还应该满足一定的优化标准（如距离最短、 移动机器人的路径规划问题已经研究了很长时 时间最少或能量消耗最低)：如果涉及到轨迹跟踪问 间，也产生了很多方法，如全局C一空间法山、人工势 题，所规划的路径还要满足一定的约束条件（如机器 场法[以及人工神经网络法[3].每一种方法都具有 人在不同区段中最高行驶速度、加减速要求以及最 各自的优点；但总的看来，以上方法都或多或少地存 小转弯半径)·无论使用哪种标准，路径规划问题最 在着一些问题，如算法计算量大、容易陷入局部最优 终都可以归结为在特定的环境空间和约束条件下搜 解以及自适应能力差，作为优化算法中的一种，遗 索总代价最小的路径优化问题，本文只进行路径规 传算法在许多优化问题中得到了广泛应用并取得了 划问题的研究，而不考虑轨迹跟踪问题，简单讲就是 很好效果·近十年来，遗传算法同样被应用于移动 机器人的路径规划问题中[)，文献[4]利用经典 收稿日期：2006-12-04修回日期：2007-03-17 遗传算法对移动机器人进行路径规划，它采用固定 基金项目：国家自然科学基金资助项目(No.60374032) 长度的二进制编码方式，遗传算子也只有交叉和变 作者简介：李繁(1971一)男，副教授，博士 异两种.虽然该方法具有一定的自适应性，但其在自适应遗传算法在移动机器人路径规划中的应用 李 擎1） 冯金玲1） 柳延领2） 周 洲1） 尹怡欣1） 1） 北京科技大学信息工程学院‚北京100083 2） 唐山学院‚唐山063000 摘 要 将一种自适应遗传算法应用于移动机器人路径规划．提出了一种基于几何避障法的初始种群产生算法；设计了基于 启发式知识的交叉、变异、求精和删除算子；采用一种新的模糊逻辑控制算法自适应地调节交叉概率和变异概率；对移动机器 人离线和在线规划问题进行了仿真研究．仿真结果表明：自适应遗传算法具有较快的搜索速度、较高的搜索质量以及较强的 自适应能力‚为移动机器人最优路径规划问题的解决提供了一种新方法． 关键词 移动机器人；最优路径规划；自适应；遗传算法；模糊控制 分类号 TP18；TP273＋∙4 Application of adaptive genetic algorithm to optimum path planning of mobile robots LI Qing 1）‚FENG Jinling 1）‚LIU Y anling 2）‚ZHOU Zhou 1）‚Y IN Y ixin 1） 1） School of Information Engineering‚University of Science and Technology Beijing‚Beijing100083‚China 2） Tangshan College‚Tangshan063000‚China ABSTRACT An adaptive genetic algorithm for the optimum path planning problem of a mobile robot was proposed．T he research project was carried out from four aspects：a geometry obstacle avoiding algorithm was developed to generate initial population；the crossover‚mutation‚improving and deletion operators which base on heuristic knowledge were designed for path planning；a new kind of fuzzy logic control algorithm was adopted to self-adaptively adjust the probabilities of crossover and mutation；simulation stud￾ies in both off-line and on-line environments were implemented．T he simulation results show that the adaptive genetic algorithm has advantages such as rapid search speed‚high search quality and strong self-adaptability．It is a new approach for solving the optimum path planning problem of a mobile robot． KEY WORDS mobile robot；optimum path planning；adaptive；genetic algorithm；fuzzy control 收稿日期：2006-12-04 修回日期：2007-03-17 基金项目：国家自然科学基金资助项目（No．60374032） 作者简介：李 擎（1971—）‚男‚副教授‚博士 所谓移动机器人的路径规划‚就是指在一个含 有障碍的环境中‚为移动机器人找出一条从起始节 点到目标节点的连通路径（避开障碍点）．当然这条 连通路径还应该满足一定的优化标准（如距离最短、 时间最少或能量消耗最低）；如果涉及到轨迹跟踪问 题‚所规划的路径还要满足一定的约束条件（如机器 人在不同区段中最高行驶速度、加减速要求以及最 小转弯半径）．无论使用哪种标准‚路径规划问题最 终都可以归结为在特定的环境空间和约束条件下搜 索总代价最小的路径优化问题．本文只进行路径规 划问题的研究‚而不考虑轨迹跟踪问题‚简单讲就是 研究如何在含有障碍的环境空间中为移动机器人规 划出一条从起始节点到目标节点的最短无障碍 路径． 移动机器人的路径规划问题已经研究了很长时 间‚也产生了很多方法‚如全局 C—空间法［1］、人工势 场法［2］以及人工神经网络法［3］．每一种方法都具有 各自的优点；但总的看来‚以上方法都或多或少地存 在着一些问题‚如算法计算量大、容易陷入局部最优 解以及自适应能力差．作为优化算法中的一种‚遗 传算法在许多优化问题中得到了广泛应用并取得了 很好效果．近十年来‚遗传算法同样被应用于移动 机器人的路径规划问题中［4—7］．文献［4］利用经典 遗传算法对移动机器人进行路径规划‚它采用固定 长度的二进制编码方式‚遗传算子也只有交叉和变 异两种．虽然该方法具有一定的自适应性‚但其在 第30卷 第3期 2008年 3月 北 京 科 技 大 学 学 报 Journal of University of Science and Technology Beijing Vol．30No．3 Mar．2008 DOI:10．13374／j．issn1001－053x．2008．03．019