A Beamlet-Based Graph Structure for Path Planning Using Multiscale Information

Path-planning problems are fundamental in many applications, such as transportation, artificial intelligence, control of autonomous vehicles, and many more. In this paper, we consider the deterministic path-planning problem, equivalently, the single-pair shortest path problem on a given grid-like graph structure. Current commonly used algorithms in this area include the A* algorithm, Dijkstra´s algorithm, and their numerous variants. We propose an innovative beamlet-based graph structure for path planning that utilizes multiscale information of the environment. This information is collected via a bottom-up fusion algorithm. This new graph structure goes beyond “nearest-neighbor” connectivity, incorporating “long-distance” interactions between the nodes of the graph. Based on this new graph structure, we obtain a multiscale version of A* , which is advantageous when preprocessing is allowable and feasible. Compared to the benchmark A* algorithm, the use of multiscale information leads to an improvement in terms of computational complexity. Numerical experiments indicate an even more favorable behavior than the one predicted by the theoretical complexity analysis.