D. S. Yershov and S. M. LaValle. Simplicial Dijkstra and A* Algorithms for Optimal Feedback Planning. Proceedings of the IEEE International Conference on Intelligent Robots and Systems (IROS), 2011. [pdf]
This paper considers the Euclidean shortest path problem among obstacles in Rn. 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.