11

我正在计算机器人在具有多边形障碍物的平面上的最短路径。一切运行良好且快速，没有问题。但是，如何平滑路径使其变得弯曲？下面是用直线连接顶点的路径的图片。PS机器人只是一个圆圈。

顶点

4

4 回答 4

6

这篇论文可能有用。看起来这是一个不平凡的问题。抽象的：

自动绘图抽屉需要计算一个简单多边形的顶点之间的路径，除了保留在内部之外，还需要表现出某些美学特性。其中一些需要在不离实际最短路径太远的情况下合并一些关于多边形形状的信息。我们提出了一种算法来计算一个局部凸区域，该区域“包含”一个简单多边形的两个顶点之间的最短欧几里得路径。该区域具有“遵循”最短路径形状的边界形状。区域内部的三次贝塞尔样条曲线在两个给定顶点之间提供了一条“短而平滑”的无碰撞曲线。所获得的结果似乎在美学上令人愉悦，并且所使用的方法可能具有独立的兴趣。它们是基本的和可实施的。

于 2011-04-05T19:42:33.800 回答
5

在尝试制作要在Teragen中渲染的逼真飞行序列时，我经常使用路径计算技术。我最初尝试使用Bézier Curves。

曲线

但是发现（至少对于飞行）它们并没有那么有用。原因是曲线之间的曲率是不连续的，因此不能用于计算飞越的连续正确倾斜角。此外，很难确定曲线不会与山相交。

我跑题了。我最终确定的方式是一个简单的基于质量弹簧的路径，然后将其放松以提交。

将路径细分为许多小段，越多越好。对于每个点，将其向一个方向移动一点，以减少它与相邻点之间的角度，并远离障碍物。重复多次，直到路径安定下来。

k = 0.01    // Adjust the values of k and j to your liking.
j = 0.01    // Small values take longer to settle. Larger values are unstable.
For each point P
    normal_vector     = vector_to_previous_point + vector_to_next_point
    obstacle_vector   = vector_to_nearest_obstacle
    obstacle_distance = magnitude(obstacle_vector)
    obstacle_vector  *= obstacle_distance^2
    P                += (normal_vector * k) - (obstacle_vector * j)

这种有限元松弛技术的好处是您可以在其中编写各种约束，并且路径将根据权重（在本例中为 j 和 k）在它们之间做出某种妥协。

如果您喜欢机器人技术，为什么不来加入机器人提案？

于 2012-10-07T21:07:46.887 回答
3

你不能在路径跟随算法的实际执行中让路径弯曲吗？如果您将路径保持原样（即连接的直线），则在计算每个车轮速度的控制算法将自动平滑路径，无需任何预处理。

这是我的意思的快速图像......红色虚线是当您根据前瞻距离控制到一个点时机器人实际执行的路径。前瞻距离仅计算沿路径向下某个任意距离的点。

在此处输入图像描述

同样，您唯一需要担心的是您要填充多少障碍物以确保避免撞到它们。通常我相信障碍物的区域会被机器人半径的一半填充，但如果你控制到前瞻距离，你可能不得不把它稍微大一点。

于 2013-09-16T18:58:23.667 回答
0

对于机器人，我们无法知道未来。我们必须只知道机器人的位置和障碍物来绘制每个点。制作最小长度曲线路径的常用方法是用一个圆对机器人进行建模，然后移动这个圆，使其与障碍物保持接触。只要保持一个半径，转弯就会是曲线。

如果您想要曲线而不是最小距离，请尝试使上述半径与您与多边形顶点的距离成比例。

贝塞尔曲线的想法只适用于使路径在回溯中弯曲。它改变了机器人的位置。通常用机器人改变过去被称为“作弊”。避免改变你已经走过的路径的一种方法是向前看。但是机器人能看到角落吗？您必须更好地指定规则。

于 2013-12-31T22:30:25.830 回答