孔继利，张鹏坤，刘晓平

北京邮电大学 现代邮政学院，北京100876

随着经济日益发展以及生产管理水平的进步，高度自动化、智能化的AGV应用愈加广泛，柔性制造系统[1]、智慧仓储[2]、自动化码头[3]、智能停车场[4]都是AGV常见的应用场景。对AGV 调度而言，最重要的内容之一就是路径规划。AGV的路径规划是指选取从任务起始点到目标点的一条路线，使一定目标（时间、距离、能耗等）达到最优化，并且避免与已知障碍物的碰撞。为AGV选择有效的路径，可以提高物流效率，降低运输成本。因此，对AGV路径规划算法进行研究具有重要意义。

在点点间运输问题的路径规划中，常见的算法有Dijkstra 算法[5]、Floyd 算法[6]、人工势场法等。A*算法同样作为常见的点点间路径规划算法[7]，与Dijkstra算法和Floyd 算法相比具有更强的启发式信息，在最短路径的搜索效率上存在一定优势。A*算法是一种基于全局的最短路径搜索算法，能够较好地避免人工势场法频繁出现的局部最优问题。A*算法已经广泛应用于多种场景，包括室内机器人的路径规划、无人船的路径规划和电子游戏中的无碰撞检测等。但A*算法在实际应用中存在着遍历节点多、搜索过程中计算量庞大等问题，在大规模环境下不断调用A*算法会占据大量内存资源。因此，传统A*算法以及改进A*算法在计算效率上依旧有提升空间。

国内外已有不少学者针对A*算法的局限性，对A*算法进行改进。Harabor 和Grastien[8]提出了跳点算法，其OPEN列表中只储存有代表性的跳点，通过对跳点的连接可以实现长距离的跳跃，提高计算效率；……