10/14/2011
Written by
University of Illinois computer science PhD student Dmitry Yershov has won the Best Student Paper Award at the IROS 2011 Conference for his work on the Euclidean shortest path problem. The paper, “Simplicial Dijkstra and A* Algorithms for Optimal Feedback Planning”, introduces algorithms that compute the approximate cost-to-go function over a simplicial complex embedded in free space. His approach provides new benefits over existing approaches, including reduced computational costs, efficiency, and applicability to manifolds of two, three, or more dimensions.
“Computing the Euclidean shortest path to a given goal is a recurring problem in robotics,” explains Yershov in the paper. “In addition to optimal robot navigation and manipulation, it is also useful in image processing, financial modeling, physics, and more.”
Yershov’s work introduces an interpolation-based method for approximating the cost-to-go function associated with shortest path problems over simplicial complexes. His work extends existing interpolation techniques beyond regular grids in 2D or 3D, resulting in an approach that is applicable to spaces in any dimension, even in various topologies, such as a torus. His novel Dijkstra-like algorithm is able to inherit the causality property of the original problem, resulting in improved efficiency. Using a proposed continuous version of the A* algorithm, Yershov demonstrates a further reduction in computational costs for cases in which the initial point is known. Finally, the paper provides error bounds for Yershov’s proposed algorithms, leading to convergence of the approximate path to the optimal path as the resolution of the simplicial mesh is refined.
"One challenge with the work is that previous methods are scattered across various research fields such as control theory, computational physics, computational geometry, and robotics. There is not much awareness of each others results," said computer science professor Steven M. LaValle, the paper's co-author. "Dmitry was able to build on the best ideas from these scattered works to provide an effective new method. I am amazed that he was able to make substantial progress on such a thoroughly studied and central problem in robotics."