1

我尝试研究具有多边形障碍物的平面中两点之间的短路径的不同算法。

我发现的绝大多数算法都使用离散图（网格图、可见性图、Voronoi 路线图等）。

一些书籍（如 Ben-Ari 的“机器人学元素”或 Nikolaus Correll 的“自主机器人简介”）提到了连续地图（例如原始多边形数据），但没有解释相应的算法。他们声称对于少数简单的障碍物具有记忆或效率优势，这对我来说可能非常有趣。

我相信，应该有一个聪明的方法使用几何计算（例如交叉点检测）和一些算法范式（例如最小成本分支和界限），但我不想糟糕地重新发明轮子。

是否有一些使用连续地图或有用关键字搜索的最短路径算法的资源？

就像建议的那样，我尝试指定我使用的一些术语：

  1. 连续地图

如图。

指几何形状的（连续）实数值的存储。障碍物/三角形 I. 将存储为：A = (3,2), B=(7,5), C=(7,2)。

  1. 离散地图

如图。指细分为块（离散化，例如在网格图中）。障碍物/三角形 I. 现在将存储为单元格索引：

(3,2), (4,2), (5,2), (6,2), (5,3), (6,3), (6,4)

离散地图中的寻路通常由基于图的算法（如Dijkstra或）完成A*。

  1. 几何计算只是我用于计算几何操作的一个模糊术语，我希望在连续地图的寻路算法中使用它。（例如平移、垂直距离、交叉点检测）
4

2 回答 2

0

对于您所说的“连续地图”，只需在所有顶点上使用 Dijkstra。唯一的区别是在计算节点之间的距离时必须检查剪裁。

于 2020-08-29T22:41:52.023 回答
0

我的问题的另一个更常用的术语似乎是Euclidean Shortest Path(s)。连续映射和离散映射算法之间的区别对我来说似乎有点模棱两可。

然而，我发现最接近连续地图算法的是 Mitchell 的连续 Dijkstra 问题算法（或连续 Dijkstra 方法）。该算法使用从起点均匀分布的小波。通过小波的“衍射”，它们到达无法直接到达的区域。这将创建一个最短路径图，可用于识别到连续配置空间中任何点的欧几里得最短路径。

有关更多信息，请参阅：

有人可能会争辩说，创建的最短路径图只是连续配置空间的另一种离散化。但是，我猜最短路径图只是一个可以得到的结果，如果该算法应用于整个配置空间。如果只需要两点之间的最短路径，算法可以在到达目标点后停止。我仍然不确定这些算法的分类，但这应该回答我的问题。

于 2020-09-17T09:35:12.027 回答