胡章芳，程 亮，张 杰，王春瑞

(重庆邮电大学 光电工程学院，重庆 400065)

0 引 言

机器人路径规划一直以来都是研究的热点。移动机器人路径规划的一个难点是在有障碍物的环境中确定从起始点到目标点的全局最优路径，同时要避免碰撞。依据不同的角度，可以对路径规划方法进行不同的分类，本文将其分为传统算法和智能算法，前者主要包括图搜索法[1]、人工势场法[2]和栅格法[3]等，这些方法搜索效率低，得到的优化结果也不太理想，后者主要包括遗传算法[4]、蚁群算法[5]、免疫算法[6]和神经网络算法[7]等，这些算法虽然使机器人路径规划在性能方面得到提升，但是存在着运算时间较长、搜索空间较大、效率较低等问题。传统算法大部分解决的是单个约束条件下的问题(如路径最短)，在实际环境中往往需要考虑多个约束条件以寻找到一条最优或次优路径，而这些约束条件往往是相互协调、相互竞争的，不存在使多个约束条件同时达到最优解的情况。机器人路径规划本质上是一个具有多个性能指标的NP(non-deterministic polynomial)完全问题，很难找到精确的解决方案。因此，在多约束条件下优化机器人行走路径具有非常重要的实际意义[8]。

近年来，已有不少专家学者对此进行大量研究并提出多种路径优化方法和策略，文献[9]提出一种在离散环境下进行移动机器人路径规划的新方法，主要是基于电场势理论和电场对电荷的影响并在此基础上，借鉴前人关于非凸数据聚类的研究成果，构造了一种基于路径规划的优化算法，该算法虽然计算简单，但容易陷入局部最优。……