连续空间最短路径

Question

连续空间最短路径

algorithmshortest-patheuclidean-distancecontinuous

4

我需要一个最短路径算法来控制现实生活中的机器人。

假设我有一个环境地图，它以矩阵的形式存在，其中1表示障碍物，0表示自由空间。如果我使用传统的最短路径算法，比如A*算法，那么它会给出曼哈顿距离最短的路径。所以这个路径并不接近实际的最短路径。这个问题的原因在于我无法想到一种方法来惩罚移动，使得对角线比两条直线更好。我可以制定一种启发式算法，让A*首先尝试两点之间的欧几里得最短路径，但并不会使欧几里得最短路径成为更好的路径。

有没有人知道一种方法来获取连续空间的最短路径？它不一定是实际的最优路径，但比直线和90度角更好。

我有一个想法：从起点开始画一个圆。增加圆的半径，直到圆上的一个点靠近墙或到达目标。圆边上的所有点都设置为子节点，并带有圆的半径作为惩罚。圆内部的所有点，如果不开放，则将关闭，因为没有理由测试它们。按照欧几里得最短路径作为启发式，以A*方式重复此过程，直到达到目标状态。让机器人从一个点向下一个点直线运动。

这应该会给出更接近我所寻找的东西。一组具有不同角度的直线。当然，连续的曲线会更好...

- Kartoffel

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- NikoNyrh · Accepted Answer

我已经实现了一个连续空间路径规划算法，并在这里进行了博客记录。它使用A*以获得初始估计，并通过使用简单的梯度下降算法最终确定路径（并对目标处的锐角转弯和机器人方向进行惩罚）。

假设来自A*的离散路径有n个“路标”（网格上的坐标）。第一个和最后一个不能移动，但其他的可以，只要路径不穿过被阻塞的网格单元。要最小化的函数由n-2个参数参数化，这些参数使路标垂直于其当前方向移动。