计算机工程 ›› 2012, Vol. 38 ›› Issue (9): 166-169.doi: 10.3969/j.issn.1000-3428.2012.09.050

• 人工智能及识别技术 • 上一篇    下一篇

基于关键链遗传操作的机器人路径规划

梁金泉,周之平,黎 明,万 国   

  1. (南昌航空大学信息工程学院,南昌 330063)
  • 收稿日期:2011-06-30 出版日期:2012-05-05 发布日期:2012-05-05
  • 作者简介:梁金泉(1986-),男,硕士研究生,主研方向:机器人路径规划;周之平,副教授、博士;黎 明,教授、博士;万 国,硕士研究生
  • 基金项目:
    国家自然科学基金资助项目(60963002);江西省自然科学基金资助项目(2009GZS0090)

Robot Path Planning Based on Key Chain Genetic Operation

LIANG Jin-quan, ZHOU Zhi-ping, LI Ming, WAN Guo   

  1. (School of Information Engineering, Nanchang Hangkong University, Nanchang 330063, China)
  • Received:2011-06-30 Online:2012-05-05 Published:2012-05-05

摘要: 针对复杂环境下遗传算法规划路径难的问题,提出一种基于关键链遗传操作的机器人路径规划方法。将回退策略和禁忌策略与启发式邻域搜索相结合保证路径的可行性。通过提取初始可行路径中的关键链,降低算法所需存储空间及计算代价。对关键链进行局部自适应变异和交叉操作,增强算法的优化能力。实验结果表明,该方法能有效地规划复杂环境下的机器人运动路径,算法性能优于同类算法,规划时间可满足实际应用需求。

关键词: 关键链, 路径规划, 可视性检测, 遗传算, 回退策略, 禁忌策略

Abstract: To solve the problem of robot path planning under complicated environment, a genetic operation based on key chains is proposed. Both retroversion and taboo strategy are incorporated into heuristic neighboring search to guarantee the feasibility of path. The memory requirement and computing cost are reduced by extracting key chain from original feasible route. The optimization performance is improved by locally adaptive mutation and crossover operator acting on key chains. Experimental results show new algorithm can plan the safety trajectory of robot under complex obstacle environment and overmatch other algorithms, as well as running time can meet the demand of practical applications.

Key words: key chain, path planning, visibility detection, genetic algorithm, retroversion strategy, taboo strategy

中图分类号: