Authors: Kaarthik Sundar, Sivakumar Rathinam
Abstract: We present a novel algorithm that fuses the existing convex-programming based
approach with heuristic information to find optimality guarantees and
near-optimal paths for the Shortest Path Problem in the Graph of Convex Sets
(SPP-GCS). Our method, inspired by $A^*$, initiates a best-first-like procedure
from a designated subset of vertices and iteratively expands it until further
growth is neither possible nor beneficial. Traditionally, obtaining solutions
with bounds for an optimization problem involves solving a relaxation,
modifying the relaxed solution to a feasible one, and then comparing the two
solutions to establish bounds. However, for SPP-GCS, we demonstrate that
reversing this process can be more advantageous, especially with Euclidean
travel costs. In other words, we initially employ $A^*$ to find a feasible
solution for SPP-GCS, then solve a convex relaxation restricted to the vertices
explored by $A^*$ to obtain a relaxed solution, and finally, compare the
solutions to derive bounds. We present numerical results to highlight the
advantages of our algorithm over the existing approach in terms of the sizes of
the convex programs solved and computation time.
Source: http://arxiv.org/abs/2407.17413v1
