Robotics: Science and Systems XIX

G*: A New Approach to Bounding Curvature Constrained Shortest Paths through Dubins Gates

Satyanarayana Gupta Manyam, Abhishek Nayak, Sivakumar Rathinam

Abstract:

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.

Download:

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} 
}