$A^*$ for Graphs of Convex Sets

我们提出了一种新颖的算法，将现有的基于凸规划的方法与启发式信息融合起来，以找到凸集图中最短路径问题（SPP-GCS）的最优性保证和近似最优路径。我们的方法受$A^*$启发，从指定的顶点子集开始启动类似于最佳优先搜索的过程，并逐步扩展它，直到进一步的增长既不可能也不有益为止。传统上，获得带有优化问题边界的解决方案涉及求解松弛问题，将松弛解决方案修改为可行解决方案，然后将两个解决方案进行比较以建立边界。然而，对于SPP-GCS，我们证明了反转这个过程可能更有优势，特别是对于欧几里得旅行成本。换句话说，我们最初使用$A^*$来找到SPP-GCS的可行解，然后解决一个限制在$A^*$探索的顶点上的凸松弛，以获得松弛解决方案，最后，比较解决方案以得出边界。我们提供数字结果以突出我们的算法在解决凸规划的大小和计算时间方面相对于现有方法的优点。

本篇论文旨在解决凸集图最短路径问题（SPP-GCS），并提出一种新算法来寻找最优解和近似最优路径。

该算法将现有的基于凸规划的方法与启发式信息相结合，采用类似于A*的贪心策略，先用A*找到可行解，再通过凸松弛来得到最优解，并通过比较两者来得到界限。

论文通过实验验证了该算法相比现有方法在凸规划问题规模和计算时间方面的优势。

该领域的相关研究包括：Convex Programming-Based Shortest Path in Convex Sets、A* Algorithm、Shortest Path Problem等。