Computer Engineering and Applications ›› 2008, Vol. 44 ›› Issue (1): 54-56.

• 学术探讨 • Previous Articles     Next Articles

Global robot path planning based on positive feedback GA

SI Ying-tao,ZHU Qing-bao,GUO Hai-tao   

  1. Computer Department of Nanjing Normal University,Nanjing 210097,China
  • Received:1900-01-01 Revised:1900-01-01 Online:2008-01-01 Published:2008-01-01
  • Contact: SI Ying-tao

基于正反馈遗传算法的机器人全局路径规划

司应涛,朱庆保,国海涛   

  1. 南京师范大学 计算机系,南京 210097
  • 通讯作者: 司应涛

Abstract: Genetic Algorithm(GA) is applied to the global Robot Path Planning in this article.A novel modeling method is presented for GA for global robot path planning,which is implemented only dependent on the positions of the start node and the goal node of the robot.This method avoids the disadvantages of the complexity of the MAKLINK Graph modeling and the most popular Grid modeling method,such as the difficulty of allocating grid grain,the inconsistence of the chromosomes’ length and the complexity of calculation.Genes lie in the vertical lines of nodes that equally divide the line from the start node of the robot to the goal node,and are denoted in single value .To speed up the convergence of GA,the positive feedback from the Ant Colony Optimization(ACO) is introduced to the crossover operation and the mutation operation.The experiment results demonstrate this algorithm can immediately find a path even in complex environments.

Key words: global path planning, environment model, positive feedback, genetic algorithm

摘要: 应用遗传算法进行机器人全局路径规划,针对该算法,目前常用的建模方法均存在一定缺陷,如链接图法过程复杂,栅格法栅格粒度难以控制,且随栅格数增加,算法复杂度急剧增加等等。论文采用了一种新颖的建模方法,该方法根据机器人出发点、目标点的位置建立起新的坐标空间,染色体各基因位于机器人出发点及目标点连线的各等分点垂线上,这样,可行解的基因可以单值表示,使算法简化。算法还借鉴蚁群算法思想,在交叉、变异算子中引入了正反馈机制,以提高算法的收敛速度。仿真试验显示了在复杂的环境中机器人仍能够以较快的速度找到一条最优路径。

关键词: 全局路径规划, 环境建模, 正反馈, 遗传算法