问题标签 [motion-planning]

Given a distance transform of a map with obstacles in it, how do I get the least cost path from a start pixel to a goal pixel? The distance transform image has the distance(euclidean) to the nearest obstacle of the original map, in each pixel i.e. if in the original map pixel (i,j) is 3 pixels away to the left and 2 pixels away to the down of an obstacle, then in the distance transform the pixel will have sqrt(4+9) = sqrt(13) as the pixel value. Thus darker pixels signify proximity to obstacles and lighter values signify that they are far from obstacles.

I want to plan a path from a given start to goal pixel using the information provided by this distance transform and optimize the cost of the path and also there is another constraint that the path should never reach a pixel which is less than 'x' pixels away from an obstacle.

How do I go about this?

P.S. A bit of description on the algorithm (or a bit of code) would be helpful as I am new to planning algorithms.

我正在尝试开发一种基于 delaunay 三角剖分、费马点、改进的 dijkstra 算法的算法来实现机器人运动规划。目前我已经介绍了德劳内三角剖分和费马点。我已经开始使用 Dijkstra 使用斐波那契堆。目前我正在研究多边形物体。假设如果我想包括现实生活中的弯曲障碍，我该怎么做？有没有办法将弯曲障碍物近似为多边形障碍物？此外，如果要纳入一个基于动态变化环境的项目，需要哪些基本思想，比如应该涵盖哪些内容？

我正在研究一个运动规划问题，我面临着数值精度的问题。

我的目标是用线段和圆弧划分实数的二维向量空间。CGAL 库的2D 排列很好地用于此目的。以下是我定义的类型：

在计算过程中，我需要移动一个端点具有有理坐标的线段，（由于线段的长度，即平方根），该线段的图像然后具有代数坐标。我还需要在此图像的端点上添加两个圆弧。

我在手册中发现的只是一种为中心添加有理坐标的圆弧的方法，如何处理具有代数坐标的圆弧（没有精度误差）？

谢谢。

我将开始我的机器人项目工作。在进入这个问题之前，让我先简要介绍一下这个项目的设置。

该设置包括一个设施，其中有一个轨道系统，并且安装了多个机器人。环境是静态的，只有移动机器人。至于现在，这些轨道上可以是 3 个机器人货车。这些机器人用于拾取和放置任务。因此，这些机器人之间没有通信，但它们连接到服务器，服务器为机器人提供任务。

请看一下粗略的草图（请原谅我这张糟糕的图表）以了解设置。

从上图中，R1 和 R2 是轨道上的机器人。服务器可以将作业分配给机器人 R1，用于在“A”处拾取对象并将其放在“B”处，并且机器人必须完全自主地移动。现在，我的查询如下：

• 机器人 R1 如何移动到“A”，然后移动到“B”，采取最优路径，涉及机器人的路径规划？
• 机器人如何避免在静态地图中与轨道上的其他移动机器人发生碰撞，避免碰撞？（我正在考虑使用相机来检测其他机器人）

我查阅了一些文献并有了一个基本的想法。我也在这里解决了一些被问到的问题。但是我没有任何具体的想法来开始工作。我正在寻找一些建议/想法/算法/文献来解决这个问题。请帮帮我。提前致谢 ！！

注意：我将在 3D 环境中模拟整个设置。

关于我的作业，我必须用数字标记的单元格绘制 10*10 网格。现在只有我开始学习 mat lab。我尝试了很多方法来绘制网格。但没有人给我解决方案。请帮帮我

我想做一些抓取运动规划实验，但我编译GraspIt 失败了！在 Win7 上使用 VS2010。有没有像GraspIt这样的抓握模拟工具！可以在Win7和VS2010环境下使用吗？谢谢！

假设我将三个机器人连接成三角形，我该如何避开工作空间中的障碍物？

我正在考虑使用 A*，但我遇到了一个问题，它适用于一个机器人，但当涉及 3 个机器人时，它会导致碰撞。

我对机器人技术真的很陌生，至少有人知道哪种算法更适合吗？

我不需要实际的代码，只要一个可行的想法就可以了。

提前致谢！！！

我在寻找什么

我在一个平面上有 300 个或更少的等半径圆盘。在时间 0，每个圆盘处于一个位置。在时间 1，每个圆盘可能处于不同的位置。我希望在 0 和 1 之间为每个圆盘生成一个 2D 路径，这样圆盘不会相交，并且路径相对有效（短）并且如果可能的话曲率低。（例如，直线优于波浪线）

• 较低的计算时间通常比解决方案的准确性更重要。（例如，一点点交叉也可以，我不一定需要最优结果）
• 然而，圆盘不应该相互传送，突然停止或减速，或者突然改变方向——“越平滑”越好。唯一的例外是时间 0 和 1。
• 路径可以以采样形式或分段线性性质（或更好）表示——我不担心通过样条线获得真正平滑的路径。（如果需要，我可以近似。）

我试过的

您可以看到我的最佳尝试演示（通过 Javascript + WebGL）。请注意，由于涉及的计算，它会在较旧的计算机上缓慢加载。它似乎在 Windows 下的 Firefox/Chrome/IE11 中工作。

在这个演示中，我将每个圆盘表示为 3D 中的“弹性带”（也就是说，每个圆盘每次都有一个位置）并运行一个简单的游戏式物理引擎，它可以解决约束并将每个时间点视为一个质量与弹簧到上一次/下一次。（在这种情况下，“时间”只是第三个维度。）

这实际上对于小 N (<20) 非常有效，但在常见的测试用例中（例如，从排列成圆形的圆盘开始，将每个圆盘移动到圆上的相对点）这无法生成令人信服的路径，因为约束和弹性在整个弹簧中缓慢传播。（例如，如果我将时间分成 100 个离散级别，则弹性带中的张力在每个模拟循环中仅传播一个级别）这使得好的解决方案需要多次（>10000）次迭代，这对我的应用程序来说非常缓慢。它也无法合理地解决许多 N>40 的情况，但这可能仅仅是因为我无法运行足够的迭代。

我还尝试了什么

我最初的尝试是爬山，从直线路径开始，逐渐变异。比当前最佳解决方案测量得更好的解决方案取代了当前最佳解决方案。更好的测量结果来自交叉点的数量（即完全重叠的测量结果比放牧更糟糕）和路径的长度（路径越短越好）。

这产生了一些令人惊讶的好结果，但不可靠，可能经常陷入局部最小值。N>20 时非常慢。我尝试应用一些技术（模拟退火、遗传算法方法等）试图解决局部最小值问题，但我从未取得太大成功。

我正在尝试什么

我正在优化“弹性带”模型，以便张力和约束在时间维度上传播得更快。在许多情况下，这将节省大量所需的迭代，但是在高度受限的情况下（例如，许多盘试图穿过同一位置）仍然需要难以维持的迭代量。我不是如何更快地解决约束或传播弹簧的专家（我已经尝试阅读一些关于不可拉伸布料模拟的论文，但我无法弄清楚它们是否适用），所以我会对是否有解决此问题的好方法感兴趣。

桌上的想法

• Spektre 实现了一种非常快速的 RTS 风格的单位移动算法，效果非常好。它快速而优雅，但它存在 RTS 运动风格问题：突然的方向变化，单位可以突然停止以解决碰撞。此外，并非所有单位都同时到达目的地，这本质上是一个突然停止。这可能是一个很好的启发式方法来制作可行的非平滑路径，之后可以及时重新采样路径并且可以运行“平滑”算法（很像我在演示中使用的算法。）
• Ashkan Kzme 认为问题可能与网络流量有关。看起来最小成本流问题是可行的，只要空间和时间可以以合理的方式进行区分，并且运行时间可以降低。这里的优点是它是一组经过充分研究的问题，但突然的速度变化仍然是一个问题，并且可能需要某种“平滑”的后期步骤。我目前遇到的绊脚石是决定时空网络表示不会导致光盘相互传送。
• Jay Kominek 发布了一个答案，该答案使用非线性优化器来优化二次贝塞尔曲线，并取得了一些有希望的结果。

我正在开发一个机器人，它能够在迷宫中导航、避开障碍物并识别其中的一些物体。我有一个迷宫的单色位图，应该用于机器人导航。

到目前为止，我已经处理了位图图像，并将其转换为邻接列表。我现在将使用 dijkstra 算法来规划路径。

然而问题是我必须从 bmp 图像本身中提取入口点/节点和出口节点，以便 dijkstra 的算法规划路径。

机器人的起始位置与迷宫的入口点略有不同（入口点前一英寸或两英寸），我应该使用任何“任意方法”移动到入口点，然后应用 dijkstra 算法来规划迷宫的路径入口到出口。

在途中，我还必须停在我附在下面的 bmp 文件中标记的“X”处。这些 X 基本上是我必须在其中装球的盒子。我将规划从入口点到出口点的路径，而不是从入口到第一个盒子，然后到第二个，然后到出口点；因为我认为这些盒子总是放在最短的路径上。

由于起始位置与入口点不同，我将如何将机器人的物理位置与程序中的坐标匹配并相应地移动它。即使入口位置与起始位置相同，也可能存在错误。我应该如何处理？我应该只根据 dijkstra 提供的坐标导航还是使用超声波来防止碰撞？如果是的话，你能给我一个关于我应该如何使用两者（超声波和坐标）的想法吗？

这是迷宫的示例位图图像。

我想为机械臂的运动规划实施 RRT。我在互联网上搜索了很多以获取一些用于运动规划的 RRT 示例代码，但我没有得到任何东西。有人可以建议一个很好的来源，我可以在其中找到用 C++ 实现的 RRT 用于任何类型的运动规划。