Study of Pathfinding Approach Based on A* with Adaptive Occupancy Grid

Abstract

This paper presents the results of a study on the A* search algorithm applied to a two-dimensional map with obstacles. Since, in typical cases, A* is implemented on a map divided into cells of equal size, a scientific interest has lies in investigating the efficiency of this algorithm on a map with dynamically variable cell size. Such a map representation increases the “resolution” of constructing a better trajectory near obstacles. For this purpose, the paper proposes an approach to representing the search space as a dynamic adaptive grid using a QuadTree structure. Additionally, a modification of the A* algorithm has been proposed and investigated, which involves selecting the best cell in the neighborhood of the agent’s current position and performing pathfinding from a starting point to a goal. The paper considers maps of various sizes and complexities for numerical experiments and compares the classical and modified A* algorithms. It has been shown that the proposed modification of the A* algorithm demonstrates better computational properties than the classical version of the algorithm on an adaptive grid.