图像 1 完美地反射(reflect)了问题并显示了机器人能够实现的运动自由度。
正方形->原点， 圆圈->目的地。
这是两个将同时工作的机器人。 如何引导这些机器人而不使彼此陷入僵局 如果他们中的任何一个应该先移动，那么如何选择哪个。
(上面的情况只是一个例子，我知道在这种情况下我们可以随机阻止他们中的任何一个并逃脱惩罚，但我正在寻找一个通用的解决方案。最近邻方法是被禁止的。) 注意:除上下两排外，机器人不能移动。
我有一个包含所有 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]
最佳答案
如果您的迷宫/网格有很多从源到目标的选项，则以下“贪婪”算法将起作用:
- 使用 shorthest path algorithm为第一个机器人绘制路径。
- 从迷宫中删除找到的路径的所有顶点
- 对下一个机器人重复此操作
这一次可以解析一个机器人的路线。通过从迷宫中删除先前机器人的路径，可以防止其他机器人使用相同的路径。
两个机器人有可能尝试占据同一个节点，但这不会使它们陷入僵局，因为它们的进入和退出路径是唯一的。两个机器人中的一个只需等待一个回合，直到另一个机器人消失。对于 i，让 robots[i] 的优先级高于 robots[j]
关于python - 多个机器人同时进行路径规划，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/46383407/