Verification and Synthesis of Admissible Heuristics for Kinodynamic Motion Planning

Brian Paden; Valerio Varricchio; Emilio Frazzoli

RA-L 201715 citations

Verification and Synthesis of Admissible Heuristics for Kinodynamic Motion Planning

Brian Paden, Valerio Varricchio, Emilio Frazzoli

Abstract

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.

BibTeX

@inproceedings{ral2017_verificationands,
  title = {Verification and Synthesis of Admissible Heuristics for Kinodynamic Motion Planning},
  author = {Brian Paden and Valerio Varricchio and Emilio Frazzoli},
  booktitle = {RA-L 2017},
  year = {2017}
}