Verification and Synthesis of Admissible Heuristics for Kinodynamic Motion Planning
Brian A. Paden, Valerio Varricchio, Emilio Frazzoli · IEEE Robotics and Automation Letters · 2017
How does one obtain an admissible heuristic for a kinodynamic motion planning problem? This letter 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 problem data. This condition is also used to formulate an infinite-dimensional linear program to optimize an admissible heuristic. We then investigate the use of sum-of-squares programming techniques to obtain an approximate solution to this linear program. A number of examples are provided to demonstrate these new concepts.