$A^*$ for Graphs of Convex Sets

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

本论文旨在解决图形凸集最短路径问题（SPP-GCS），并且验证了一种新的算法方案。

本论文提出了一种新的算法方案，将现有的凸规划方法与启发式信息相结合，使用类似于A*的最佳优先搜索方法来寻找最优路径，并通过反转优化过程来获得更好的结果。

本论文的算法方案在求解凸规划问题的规模和计算时间方面具有优势。实验结果表明，该算法能够在SPP-GCS问题上获得更好的结果。

最近的相关研究包括：Convex Optimization for Shortest Path Problems和A* Search Algorithm。