為了讓自動駕駛汽車成為日常現實，它們需要安全、完美地在彼此之間導航，而不會撞車或造成不必要的交通堵塞。

為了幫助實現這一目標，美國西北大學的研究人員開發了第一個分散算法，該算法保證無碰撞、無擁堵。

研究人員在實驗室模擬1024個機器人和100個真實機器人群體中測試了該算法。在不到一分鐘的時間里，這些機器人可靠、安全、高效地會聚在一起，形成一個預先確定的形狀。

“如果路上有很多自動駕駛汽車，你肯定不希望它們相撞或陷入僵局。”領導這項研究的西北大學的邁克爾·魯賓斯坦說，“通過了解如何控制我們的機器人排列隊形，我們可以了解如何控制自動駕駛車隊，因為它們之間的相互作用。”

這篇論文將于本月晚些時候發表在《IEEE機器人學報》上。魯賓斯坦是西北大學麥考密克工程學院計算機科學的教授。

一群小型機器人與一個大型機器人或一個領頭機器人相比的優勢是缺乏集中控制，這可能很快成為故障的中心。魯賓斯坦的分散算法可起到故障保護作用。

“如果系統是集中的，機器人停止工作，那么整個系統就會失靈。”魯賓斯坦說，“在一個分散的系統中，沒有領導者告訴所有其他機器人該做什么。每個機器人都有自己的決定。如果一個機器人在一個群體中失敗了，這個群體仍然可以完成任務。”

盡管如此，為了避免碰撞和鎖死，機器人需要進行協調。為此，算法將機器人下方的地面視為一個網格。通過使用類似GPS的技術，每個機器人都知道自己在網格中的位置。

在決定移動到哪里之前，每個機器人都使用傳感器與它相鄰的機器人進行通信，確定網格中附近空間是空閑的還是被占用的。

“機器人拒絕移動到一個地方，直到那個地方是空閑的，直到它們知道沒有其他機器人移動到同一個地方。”魯賓斯坦說，“它們很小心，會提前預留位置。”

即使有這些精心的協調，機器人仍然能夠溝通，并迅速移動形成一個隊形。魯賓斯坦通過保持機器人附近的視野來實現這一點。

“每個機器人只能感知三四個最近的機器人。”魯賓斯坦解釋說，“它們無法看到整個群體，這使得擴展系統更容易。這些機器人在沒有全局信息的情況下進行局部決策。”

例如，在魯賓斯坦的群體中，100個機器人可以在一分鐘內協調形成一個隊形。在以前的一些方法中，可能需要整整一個小時。魯賓斯坦設想，他的算法可以用于無人駕駛汽車車隊和自動化倉庫。

“大公司的倉庫里有數百個機器人，它們所做的工作與我們的機器人在實驗室里做的工作類似。”魯賓斯坦說，“這就需要確保機器人不會碰撞，但又要盡可能快地移動到最終將物體交給人類的地方。”