Design of Admissible Heuristics for Kinodynamic Motion Planning via Sum-of-Squares Programming
This work addresses a key challenge in motion planning for robotics, providing a systematic approach to heuristic design, though it appears incremental as it builds on existing optimization methods.
The paper tackled the problem of generating admissible heuristics for kinodynamic motion planning by developing a sufficient condition for admissibility and formulating a concave optimization program, which was solved efficiently using sum-of-squares programming techniques.
How does one obtain an admissible heuristic for a kinodynamic motion planning problem? This paper develops the analytical tools and techniques to answer this question. A sufficient condition for the admissibility of a heuristic is presented which can be checked directly from the problem data. This condition is also used to formulate a concave program to optimize an admissible heuristic. This optimization is then approximated and solved in polynomial time using sum-of-squares programming techniques. A number of examples are provided to demonstrate these concepts.