融合改进人工势场法的A*算法优化

Optimization of A* Algorithm Integrating Improved Artificial Potential Field Method

摘要: 针对路面移动机器人搜索最优路径慢、效率低等问题，分别选用最优性的A*算法和人工势场法作为移动机器人的全局规划和局部规划的基本算法。针对全局规划中传统的A*算法搜索节点相对较多、最优路径选择慢的问题，进行了加权启发函数的优化，达到减少节点的遍历数量、提高搜索最佳路径速度的目的。针对人工势场法会出现的局部最优解和目标不可达的问题，进行了斥力场增强因子的改动，优化了斥力场函数，引入了脱离函数，降低了出现局部最优解的可能性，避免出现目标不可达。结果表明：在相同的地图环境中对比测试，相较于传统的A*算法与利用固定系数加权启发函数的A*算法，优化了融合改进人工势场法的A*算法能够有效地减少遍历的节点数量，提高搜索的效率，缩短路径的距离，获得最优路径。

Abstract: In order to solve the problem of slow and low efficiency in searching for the optimal path for the road-mobile robot, the optimal A* algorithm and artificial potential field method were selected as the basic algorithms for global planning and local planning of mobile robots. In order to solve the problem that the traditional A* algorithm has more searching nodes and the optimal path selection is slow, the weighted heuristic function is optimized to reduce the number of nodes traversing and improve the speed of searching the optimal path. In order to solve the problem of local optimal solution and target unreachable in the artificial potential field method, the enhancement factor of the repulsive field is changed, the function of the repulsive field is optimized, and the detachment function is introduced to reduce the possibility of the local optimal solution and avoid the target unreachable. The results show that compared with the traditional A* algorithm and the A* algorithm using the fixed coefficient weighted heuristic function in the same map environment, the optimized A* algorithm combining the improved artificial potential field method can effectively reduce the number of traversed nodes, increase the efficiency of search, shorten the distance of the path, and obtain the optimal path.