2

在此处输入图像描述绘制路径

Image1 完美地代表了问题，并显示了机器人的运动自由度。

方形-> 原点，圆形-> 目的地。

这是两个将同时工作的机器人。如何引导这些机器人互不死锁，如果它们中的任何一个应该先移动，那么如何选择哪一个。

（上面的例子只是一个例子，我知道在这种情况下我们可以随机阻止他们中的任何一个并逃脱它，但我正在寻找一个通用的解决方案。禁止最近邻方法。） 注意：机器人不能移动除了上排和下排外。

我有一个所有 X 标记点的字典，还有它在下面的 id 和坐标中的路线，

# X generated points  
{1: [0, 0], 2: [0, 30], 3: [0, 60], 4: [0, 90], 5: [30, 0], 6: [30, 30], 7: [30, 60], 8: [30, 90], 9: [60, 0], 10: [60, 30], 11: [60, 60], 12: [60, 90], 13: [90, 0], 14: [90, 30], 15: [90, 60], 16: [90, 90]}

# Routes:
red=[11,12,8,4]
blue=[7,8,12,6]
4

3 回答 3

1

在势场中进行梯度下降。

将您的棋盘想象成 3 维（好的，2.5 维），在壁垒等障碍物所在的地方有“山”，在目标所在的地方有“山谷”。每个机器人都有自己的势场，其分辨率可以与您绘制的网格相同或更高。字段可以随时间变化t。

所以现在你有一个函数 ，z(x, y, t)你可以在机器人的附近进行探测，你可以计算增量（梯度），向你展示“下山”的方式，即通往目标状态的方式。例如，在穿过走廊时，您的机器人会更喜欢从中心向下走，因为势场会从墙壁向外延伸，基本上会排斥机器人。您绘制的网格被 4 堵不可逾越的墙壁包围。

现在让我们从固定障碍物转向移动对等机器人。听起来你有一些方法可以让机器人向它的同伴广播它的意图。机器人有一个 A* 规划器，它预测它将在未来的某个时间访问某些位置。当然，由于传感器噪声和事件的不确定性，这可能行不通，但这是一个计划。所以把它广播给同行。他们会将预期的路径添加到他们正在使用的势场中，因此其他机器人会像墙壁和固定物体一样施加排斥场。这鼓励对等点规划一个轨迹，该轨迹围绕预计在未来某个位置的障碍物（机器人）转向。仍然会遇到局部最大值和死锁，因此仍然需要一些随机退避。例如，两个机器人在大厅里正面相遇，

像洪水填充这样的技术可以从目标向外传播梯度激励，以鼓励机器人“远离”目标以绕过迷宫障碍。

这种方法适用于具有零星传感/通信的自主机器人，也适用于中央控制机器人。中央控制器将为每个机器人维护一个计划，以及每个机器人的一个势场，对应于障碍物和同伴。在第一个运动命令甚至发送到物理机器人之前，Planner 组件可以组装从开始到结束的轨迹。如果规划者循环遍历机器人 1..N，编号较小的机器人将倾向于获得更短的路径，因为它们首先宣布计划并享有更大的运动自由度。例如，如果紫色在 t0 时首先移动，那么它的势场在 t1 及以后的时间里基本上会与墙的势场混合，因此 Pink 自然会制定避开墙的计划，因此两者不会冲突。您可以将其视为紫色优先于粉色。

于 2017-09-23T19:25:24.373 回答
1

如果您的迷宫/网格有很多从源到目标的选项，则以下“贪婪”算法将起作用：

  • 使用最短路径算法为第一个机器人绘制路径。
  • 从迷宫中删除找到的路径的所有顶点
  • 重复下一个机器人

这一次解决了一个机器人的路线。通过从迷宫中删除前一个机器人的路径，可以防止其他机器人使用相同的路径。

有两个机器人试图占据同一个节点的可能性，但这不会使它们死锁，因为它们的进入和退出路径是唯一的。两个机器人中的一个只需要等待一圈，直到另一个机器人消失。让机器人[i] 优先于机器人[j] for i

于 2017-09-23T19:34:10.203 回答
1

让所有机器人在外圈内转，直到目的地一步之遥，目的地为空。在这种情况下，移动到目的地点。

于是算法变为：

  • 如果在内圈且外圈是自由的，则移动到那里；否则等待一个周期（或者如果不允许，则在内圈中迈出一步）
  • 如果在外圈，检查目的地是否在 1 步之外。如果是这样的话，去那里。否则，在外圈上移动一步。

没有碰撞。没有奇怪的案例。100% 的时间工作。

迂回

应用于您的示例：机器人 A 将分 3 步回家。机器人 B 将走 11 步。

解决方案

于 2017-09-24T12:41:24.750 回答