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

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

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

中图分类号: 

• TP18