连续空间最短路径

Question

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

可以说我有在基质中，其中1是一个障碍，0是自由空间的形式对环境的地图。如果我使用传统的最短路径算法，如A *，那么这将给我一个曼哈顿距离最短路径。所以没有实际的最短路径。这个问题出现了，因为我想不出一种惩罚运动的方式，即对角线比两条直线更好。我可以尝试一种启发式方法，使A *先尝试欧几里得之间的最短路径，但实际上并没有使欧几里得最短路径成为更好的路径。

有谁知道一种获得连续空间最短路径的方法吗？它不必是实际的最佳路径，而是比直线和90度角更好的路径。

我有一个想法： 从起点作圆圈。 增加圆的半径，直到圆上的一点靠近墙壁或目标。圆的边上的所有点都被设置为子节点，并且惩罚圆的半径。因为没有理由对它们进行测试，因此圆圈内所有未开放的点将被关闭。以欧氏最短路径作为启发式以A *方式重复此操作，直到达到目标状态。使机器人从一点到另一点成直线。

这应该给我更接近我正在寻找的东西。一组不同角度的直线。当然，这将是一个连续弯曲的线条更好...

Answer 1

我实现了一个连续的空间路径规划算法，并在博客它here。它使用A *获得初始估计值，并使用简单的gradient descent算法对其进行最终确定（并针对尖锐转弯和机器人在目的地的方位进行编程）。

比方说从A *离散路径具有n “航点”（坐标上的网格）。只要路径不通过阻塞的网格单元，第一个和最后一个就不能移动，但其他的可以移动。要被最小化的功能通过将航点垂直于其当前方向的参数n - 2进行参数化。