李孟锡，何博侠，周 俣

(南京理工大学机械工程学院,江苏 南京 210094)

0 引言

移动机器人多目标路径规划,是指在环境中找到一条经过所有目标点且安全无碰撞的最优路径[1]。移动机器人多目标路径规划通常可以分为2个问题[2]：任意两目标间最短路径规划问题；多目标全局最优路径问题。常用二维栅格地图最短路径规划算法有Dijkstra算法[3]、最佳优先搜索(BFS)算法、A*算法[4]、Floyd[5]算法和D*算法[2]。其中，A*算法搜索的路径综合考虑了当前点与起点及目标点的代价值，是目前最常用的路径规划算法。但该算法也有一定缺陷，在扩展节点时，该算法将相邻的所有节点都加入搜索列表，造成大量的无用计算。多目标点全局最优路径问题可以转换为TSP(traveling salesman problem)问题，TSP 问题通常采用启发式算法求解1个较优解。常用的求解方法有粒子群算法[6]、遗传算法[7]、模拟退火算法[8]和蚁群算法[9]等。蚁群算法将蚂蚁觅食过程抽象为数学模型求解TSP问题。优点是编程简单、鲁棒性强，缺点是易陷入局部最优值。针对该缺点，文献[10]提出一种动态蚁群遗传算法，通过将蚁群算法与遗传算法动态融合，避免算法陷入局部最优解。文献[11]通过将蚁群算法与贪心算法相结合，并引入变异算子进行改进。

本文提出一种基于启发信息扩展节点的A*算法与混合蚁群算法相结合的方法，求解移动机器人多目标路径规划问题。针对A*算法扩展节点时，会造成无用计算的缺点，通过基于启发信息的扩展函数进行改进，减少无用节点计算，提升规划效率。……