是否有一种算法可以将像素化路径转换为一组向量和曲线？

Question

我为我的机器人团队制作了一个寻路程序，它使用 Dijkstra 算法（最终将更改为 A*）来获得两点之间的最快路径。它输出路径中的点列表，但它们位于像素化网格上，我需要将它们转换为机器人运动。我如何才能构建一个算法将其转换为向量和曲线的集合，以便机器人可以进行有效的运动？

我做了一些小编程，它试图找到直线的斜率，并从那里构建向量，它有效，但是我想合并曲线来平滑运动。我不知道该怎么做，这似乎是一项非常困难的任务。 我还没有尝试过制作矢量/曲线寻路算法，但数据输入将在网格点中，所以我不知道这会有多高效。

Answer 1

首先，我建议您将路径计算升级到更好的算法，最好是 LazyTheta*。这将使你的像素化路径（我假设由许多 45° 的许多小块组成）成为一条更平滑的任意角度路径，接近实际的几何最短路径。

然后，为了让你的机器人顺利潜入，只需从计算的路径中选择一个近距离目标，即所谓的胡萝卜，并使用 pd 控制器将“驴”引向胡萝卜。不需要显式计算曲线（即轨迹），这对于非完整车辆来说相当困难。我在下面提供了一个在生产中使用的 pd 控制器的示例。

// This is a simple PD controller that computes steering commands towards
// the target q. The PD controller can be used for acceleration and for 
// velocity control, depending Only on how you interpret the output.
// I found that for velocity control only the p parameters are needed.
Vec2 UnicycleRobot::pdControlTo(const Vec2 &q) const
{
    // Tune these parameters to your system:
    double P_lin = 2.0;
    double D_lin = -0.1;
    double P_rot = 1.0;
    double D_rot = -0.1;

    Vec2 forward(1,0);
    double projectedTransErr = q * forward;
    double rotErr = forward.angleTo(q);
    double a = P_lin * projectedTransErr + D_lin * v;
    double b = P_rot * rotErr + D_rot * w;
    if (q.norm() < 0.01) // Dead band.
        return Vec2();
    return Vec2(a,b);
}