改进双向蚁群算法的移动机器人路径规划

李二超，齐款款

兰州理工大学 电气工程与信息工程学院，兰州730050

静态环境下的移动机器人路径规划是指在已知环境中，按照一定的算法，根据目标函数（如距离最短等），寻找一条从起点到终点的安全且最优路径[1]。

二维静态环境下机器人路径规划算法有很多，如A*算法、遗传算法、粒子群算法和蚁群算法，其中，A*算法速度快但转折点较多，随着环境复杂度的增加，搜索代价呈指数增长[2]，遗传算法在种群初始化、算法迭代等环节代价函数建模困难，路径搜索效率低，耗费较大的计算和存储资源，在复杂环境下的路径规划效率低下，需要较长时间才能规划出可行路径，且路径并非最短[3]，粒子群算法简单易行，通用性强，但在算法初期局部搜索能力较差，后期易陷入局部最优等[4]，而选择蚁群算法的原因是，蚁群算法是一种启发式的随机搜索算法，该算法由模拟自然界蚂蚁行为而来，并通过信息素的积累产生的正向反馈来寻找最优路径，随着环境复杂度的增加，路径搜索代价不会指数增长，且具有较强的鲁棒性，优良的并行分布式计算能力、无中心控制、易于与其他算法融合的优点[5-6]，但无法找到最短路径，收敛速度慢，路径搜索盲目性大、且路径拐点较多。针对以上蚁群算法的缺陷，不同的学者有着各自的改进方法。张苏英等人[7]采用双向蚁群算法，但并未使用相遇条件，即起点蚂蚁搜索路径完成后，终点蚂蚁才开始进行路径搜索，虽然能提高全局搜索能力，但并不能缩减算法运行时间。……