Simplicial dijkstra and A* algorithms for optimal feedback planning

This paper considers the Euclidean shortest path problem among obstacles in ℝⁿ. Adaptations of Dijkstra´s and A* algorithms are introduced that compute the approximate cost-to-go function over a simplicial complex embedded in the free space. Interpolation methods are carefully designed and analyzed so that they are proven to converge numerically to the optimal cost-to-go function. As the result, the computed function produces approximately optimal trajectories. The methods are implemented and demonstrated on 2D and 3D examples. As expected, the simplicial A* algorithm significantly improves performance over the simplicial Dijkstra´s algorithm.