Asymptotically Optimal A* for Kinodynamic Planning

Abstract

The paper presents Asymptotically Optimal A* (AOA*), a heuristically guided, sampling-based algorithm for motion planning without a steering function. AOA* is an attempt to adapt the A* algorithm for planning in a continuous search space while preserving the simplicity of the original A* and using a heuristic function as simple as an Euclidean distance. Using techniques such as adaptive cost-to-come-based pruning, open-list reinitialization, and adaptive blossom number adjustment, AOA* outperforms algorithms such as SST*, AO-RRT, and DIRT in terms of time to the first solution and convergence rate.