为了让自动驾驶汽车成为日常现实，它们需要安全、完美地在彼此之间导航，而不会撞车或造成不必要的交通堵塞。

为了帮助实现这一目标，美国西北大学的研究人员开发了第一个分散算法，该算法保证无碰撞、无拥堵。

研究人员在实验室模拟1024个机器人和100个真实机器人群体中测试了该算法。在不到一分钟的时间里，这些机器人可靠、安全、高效地会聚在一起，形成一个预先确定的形状。

“如果路上有很多自动驾驶汽车，你肯定不希望它们相撞或陷入僵局。”领导这项研究的西北大学的迈克尔·鲁宾斯坦说，“通过了解如何控制我们的机器人排列队形，我们可以了解如何控制自动驾驶车队，因为它们之间的相互作用。”

这篇论文将于本月晚些时候发表在《IEEE机器人学报》上。鲁宾斯坦是西北大学麦考密克工程学院计算机科学的教授。

一群小型机器人与一个大型机器人或一个领头机器人相比的优势是缺乏集中控制，这可能很快成为故障的中心。鲁宾斯坦的分散算法可起到故障保护作用。

“如果系统是集中的，机器人停止工作，那么整个系统就会失灵。”鲁宾斯坦说，“在一个分散的系统中，没有领导者告诉所有其他机器人该做什么。每个机器人都有自己的决定。如果一个机器人在一个群体中失败了，这个群体仍然可以完成任务。”

尽管如此，为了避免碰撞和锁死，机器人需要进行协调。为此，算法将机器人下方的地面视为一个网格。通过使用类似GPS的技术，每个机器人都知道自己在网格中的位置。

在决定移动到哪里之前，每个机器人都使用传感器与它相邻的机器人进行通信，确定网格中附近空间是空闲的还是被占用的。

“机器人拒绝移动到一个地方，直到那个地方是空闲的，直到它们知道没有其他机器人移动到同一个地方。”鲁宾斯坦说，“它们很小心，会提前预留位置。”

即使有这些精心的协调，机器人仍然能够沟通，并迅速移动形成一个队形。鲁宾斯坦通过保持机器人附近的视野来实现这一点。

“每个机器人只能感知三四个最近的机器人。”鲁宾斯坦解释说，“它们无法看到整个群体，这使得扩展系统更容易。这些机器人在没有全局信息的情况下进行局部决策。”

例如，在鲁宾斯坦的群体中，100个机器人可以在一分钟内协调形成一个队形。在以前的一些方法中，可能需要整整一个小时。鲁宾斯坦设想，他的算法可以用于无人驾驶汽车车队和自动化仓库。

“大公司的仓库里有数百个机器人，它们所做的工作与我们的机器人在实验室里做的工作类似。”鲁宾斯坦说，“这就需要确保机器人不会碰撞，但又要尽可能快地移动到最终将物体交给人类的地方。”