连续空间最短路径

Question

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

假设我有矩阵形式的环境地图，其中 1 是障碍物，0 是自由空间。如果我使用传统的最短路径算法，例如 A*，那么这将为我提供曼哈顿距离最短路径。所以离实际的最短路径还差得很远。出现这个问题是因为我想不出一种方法来惩罚运动，使对角线比两条直线更好。我可以做一个启发式，让 A* 首先尝试两点之间的欧几里德最短路径，但实际上并没有使欧几里德最短路径成为更好的路径。

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

我有一个想法：从起点画一个圆。增加圆的半径，直到圆上的一个点靠近墙壁或球门。圆边缘上的所有点都被设置为子节点，并受到圆半径的惩罚。圆内所有不开放的点都将被关闭，因为没有理由测试它们。以欧几里德最短路径为启发式，以 A* 方式重复此过程，直到达到目标状态。使机器人从一个点直线移动到下一个点。

这应该会提供更接近我正在寻找的东西。一组具有不同角度的直线。当然，如果有连续的曲线就更好了……

Answer 1

我已经实现了连续空间路径规划算法并在此处发布了相关博客。它使用 A* 来获得初始估计并通过使用简单的梯度下降算法最终确定它（并针对急转弯和机器人在目的地的方向进行惩罚）。

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