Robotics: Science and Systems XIX
G*: A New Approach to Bounding Curvature Constrained Shortest Paths through Dubins Gates
Satyanarayana Gupta Manyam, Abhishek Nayak, Sivakumar RathinamAbstract:
We consider a Curvature-constrained Shortest Path (CSP) problem on a 2D plane for a robot with minimum turning radius constraints in the presence of obstacles. We introduce a new bounding technique called Gate* (G*) that provides optimality guarantees to the CSP. Our approach relies on relaxing the obstacle avoidance constraints but allows a path to travel through some restricted sets of configurations called gates which are informed by the obstacles. We also let the path to be discontinuous when it reaches a gate. This approach allows us to pose the bounding problem as a least-cost problem in a graph where the cost of traveling an edge requires us to solve a new motion planning problem called the Dubins gate problem. In addition to the theoretical results, our numerical tests show that G* can significantly improve the lower bounds with respect to the baseline approaches, and by more than 60% in some instances.
Bibtex:
@INPROCEEDINGS{Manyam-RSS-23, AUTHOR = {Satyanarayana Gupta Manyam AND Abhishek Nayak AND Sivakumar Rathinam}, TITLE = {{G*: A New Approach to Bounding Curvature Constrained Shortest Paths through Dubins Gates}}, BOOKTITLE = {Proceedings of Robotics: Science and Systems}, YEAR = {2023}, ADDRESS = {Daegu, Republic of Korea}, MONTH = {July}, DOI = {10.15607/RSS.2023.XIX.059} }