-1

我目前正在做一个项目，使用 Webots 来创建一个 3d 模拟世界 - 一个集装箱码头堆场，多个机器人（AGV）到达指定目的地以装载/卸载集装箱。

以下是我过去几周所做的一瞥。

http://www.youtube.com/watch?v=Rt6NlGP9wpA

您看到的圆形气泡充当向 AGV 发送方向的无线范围。

在最短路径算法（如 Dijkstra 或 A* 算法）上看到一些类似的线程，我很确定它可以完成，但我希望是否有人可以提供一些见解是否可能？以及首选使用哪种算法？

谢谢并恭祝安康

4

2 回答 2

0

鉴于您的说明，您需要在此处选择您的游戏。最直接的解决方案确实是运行 Dijkstra 算法并构建从任何航路点到任何其他航路点的最短路径（这意味着为每个可能的源点运行单个算法）。但是请注意，这仅执行一次（至少在移动或移除某个航路点之前）。顺便说一句，A* 在这里不相关，它旨在在决策/博弈树上运行并找到最小/最大最优路径（对您而言最大收益，对对手而言最小），那是另一回事。另一种选择是运行 Floyd–Warshall，它可以在一次运行中找到所有路径。

无论如何，一旦你运行它，你可以为每个航路点保留一个表格，说明每个目的地航路点最短路径中的下一个节点是什么。您不需要整个路径，只需要下一个顶点。一旦机器人到达那里，它就会被告知下一步要去哪里。这与大多数网络路由算法中所做的基本相同。

现在，如果你想展示机器人是如何工作的，你可以让它们在线运行这个算法并自己计算路径，但是与航点的通信是毫无意义的。

无论哪种方式，看起来你都会有一些乐趣，享受:-)

于 2013-09-10T22:14:27.217 回答
0

好吧，如果您有一条特定的路径可以用作示例，那么解释算法的工作原理会更简单。

但无论如何我都会尝试解释：

考虑到您有一个起点 A 和一个目的地 Z，我将在这个金字塔中表示：

. . . . 3 . . . .  
. . . 7 4 . . .  
. . 2 4 6 . .  
. 8 5 9 3 .

在这个金字塔中，我们将尝试找到从第一行开始到最后一行的最小路径和，方法是选择我们之前选择的两个数字中的任何一个。

在小树上，测量所有可能的解决方案并选择最小的解决方案会更简单。这对较大的树木无效。

解决它的方法是从底部开始向上，取 8 和 5，然后将最小的添加到它们上面的数字（这里是 2），然后是 5 和 9，然后是 9 和 3。你在上面重复这个过程上面的线，直到到达顶线，以及最小路径总和。

我希望这对节点和最小路径有所了解。尽管这可能很难为具有多个路径和节点交叉的 AGV 路径编码。

如果您有每个 AGV 节点（连接不同路径的停止点）的坐标，我将使用的一种简单方法是在目的地和起点之间画一条线，并逐个节点添加最接近该线的节点连接到前一个节点。

祝你好运 ：）

于 2013-09-09T19:34:01.897 回答