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

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.