Optimization of A-Star Search Algorithm

Abstract

Introduction. Autonomous mobile robots must be able to plan global and local motion paths. The A-star path planning algorithm allows us to calculate the shortest path between the starting and end points on a map with known static obstacles. In real conditions, when additional information about the area is entered (difficult or dangerous sections, areas with speed limits) and the cost of overcoming them is taken into account, A-star can lead to a non-optimal, for these conditions, solution of the problem. Aim. Consider options for optimizing the A-star path planning algorithm for use in various conditions with restrictions on the number of turns, linking to critical points on a map of the area, difficult and dangerous areas and аssess the quality of the optimization. Materials and methods. Research is carried out by computer simulation of the A-star algorithm and options for its optimization in the MATLAB environment. The criteria for evaluating the quality of optimization are focused primarily on computational time and the path optimality with respect to the selected parameters. Results. The results of path calculation performed using the A-star algorithm before and after optimization are presented. In both cases, the following are estimated and compared: calcul ation time, number of analyzed polygons, number of turns and path length. Conclusion. In most cases, the optimization of the algorithm increases the path length and calculation time, but not significantly. Moreover, the new path corresponds to the given conditions, is the shortest in these conditions and, therefore, is optimal. The considered optimization options allow you to calculate the path taking into account additional information, estimate the path length and computational time. On the basis of these evaluations, it is possible to choose path planning method suitable for individual scenario.