Light-assisted A⁎ path planning

This paper introduces a novel variant of the A⁎ path planning algorithm, which we call Light-assisted A⁎ (or LA⁎ for short). The LA⁎ algorithm expands less nodes than A⁎ during the search process, especially in scenarios where there are complex-shaped obstacles in the path between the start and goal nodes. This is achieved using the concept of (virtual) light which identifies and demotes dead-end paths blocked by obstacles, thus ensuring that the search stays focused on promising paths. Three path planning problems are used to test the performance of LA⁎. These include path finding in a grid cluttered by randomly placed obstacles, robot navigation in a map containing multiple solid walls, and finally mazes. The results of these experiments show that LA⁎ can achieve orders of magnitude improvement in performance over A⁎. In addition, LA⁎ results in near-optimal solutions that are very close to the optimal path obtained by the conventional A⁎ algorithm.