GCS*: Forward Heuristic Search on Implicit Graphs of Convex Sets

我们考虑在凸集图（GCS）上应用基于大规模隐式搜索的最短路径问题的解决方案。我们提出了GCS*，一种前向启发式搜索算法，将A*搜索泛化到GCS设置中，在该设置中，在每个图顶点上做出连续值决策，并且图边上的约束将这些决策耦合在一起，影响成本和可行性。这种混合离散连续规划在许多领域中都是必要的，包括避开障碍物的运动规划和通过接触的规划。这种设置为最佳优先搜索算法提供了独特的挑战：路径的成本和可行性取决于沿路径选择的连续值点。我们展示了通过剪枝在整个终端顶点上被成本支配的路径，GCS*可以高效地搜索，同时仍然保证成本最优和完整性。为了快速找到满意的解决方案，我们还提出了一种完整但次优的变体，通过剪枝可达性支配路径。我们使用多面体包含或基于采样的方法来实现这些检查。基于采样的实现是概率完整和渐近成本最优的，即使在实践中仅有少量样本，也能有效地执行。我们在平面推动任务上展示了GCS*，在该任务中，接触模式的组合爆炸使得先前的方法难以处理，并且展示了与最先进技术相比的优异性能。项目网站：https://shaoyuan.cc/research/gcs-star/

GCS*算法解决了基于凸集图形的最短路径问题，其中需要在图形的每个节点上做出连续值决策，并且边缘上的约束会影响成本和可行性。这是一个新问题吗？

GCS*算法是一种前向启发式搜索算法，将A*搜索泛化到GCS设置中。通过修剪全局被支配的路径，GCS*可以高效地搜索，同时仍然保证成本最优和完整性。

该算法使用了多面体包容或基于采样的方法来实现路径修剪。采样实现是概率完整和渐近成本最优的，即使在实践中只有最少的样本也能有效地执行。在平面推动任务上进行了演示，并与现有方法进行了比较。

最近的相关研究包括：基于凸集的路径规划（Convex Set Path Planning）、A*搜索算法的改进和扩展、基于采样的路径规划（Sampling-Based Path Planning）等。