JOVANA
Library Glossary Getting Started Three Levels Fields How it works Mission
Join the mission
All guides

沒有老闆也能達成一致:協調與共識

只與鄰居通訊的機器人如何達成共同決策,以及這如何驅動編隊與任務分配。

當沒有人發號施令時

想像十台送貨機器人共用一條倉庫通道。沒有一台中央電腦在發號施令;就算有,依賴它也很危險:它是一個單點故障,老闆一旦崩潰,所有機器人都會僵住。所以機器人必須一起把事情理清楚。這正是多機器人協調的核心——讓許多機器只憑各自能收集到的有限資訊,以及與鄰居之間傳遞的訊息,像一支團隊那樣行動。

難點在於,沒有哪一台機器人能看到全局。每台都有自己的感測器、自己略有偏差的時鐘,以及一個只能觸及附近少數同伴的無線電。一個協調的結果——大家就集合點、速度,或誰負責哪個貨架達成一致——必須從許多次小而局部的對話中浮現出來。這很像鳥群或蟻群在沒有管理者的情況下完成有組織的工作。

共識:所有機器人向一致緩緩平均

沒有老闆也能達成一致的經典辦法,是分散式共識。這個想法簡單得近乎不好意思:每台機器人反覆地把自己的數值,朝鄰居們數值的平均稍稍挪一點。這個數值可以是目標速度、集合地點,或對出口在哪裡的估計。沒有哪台機器人直接算出全局平均——但只要群體保持連通,所有數值就會緩緩彼此靠攏,直到匯合。

想像一圈人,每人舉著一個數字,且只能看到左右兩位鄰居。一輪又一輪,每個人都把自己的數字朝旁邊兩人挪近。儘管沒人能看到整個圓圈,每個人的數字最終都收斂到同一個值。機器人做的事情一模一樣,只是用無線電訊息代替了舉起的卡片。其中的數學不過是一次又一次地做加權平均。

# Each robot i runs this every tick:
if neighbors:
    neighbor_avg = sum(neighbors) / len(neighbors)
    my_value = my_value + step * (neighbor_avg - my_value)
# 'neighbors' is the list of neighbor values this robot can hear.
# step is small (e.g. 0.1). Repeat every tick; all values converge.
一次共識更新:朝鄰居的平均值邁一小步把自己拉過去。每台機器人、每一拍都執行它。

編隊控制:像大雁那樣保持人字形

一旦機器人能就數值達成一致,它們就能就形狀達成一致。編隊控制是讓團隊保持期望幾何圖案的技藝——一條線、一個網格、一個圓,或遷徙大雁那著名的人字形——並在整個群體移動和轉向時保持。每隻大雁並不盯著領頭雁看;牠只是與身旁那隻鳥保持一個固定的偏移。機器人也一樣:與鄰居保持一個設定的距離和角度,整體形狀便會自然成形。

錨定一個編隊通常有兩種方式。在領導者—跟隨者模式中,一台機器人選定路徑,其餘機器人相對於它保持各自的偏移——簡單,但領導者一旦失效,編隊便會瓦解。在基於共識的視角下,根本沒有領導者:每台機器人都用同樣的鄰居平均思想,只不過它要匹配的不是鄰居的精確數值,而是那個數值加上一個固定偏移(「待在我左側兩公尺處」)。團隊便在無人主導的情況下落定成形。

任務分配:用拍賣決定誰幹什麼

就一個數值或一種形狀達成一致是一回事;把一堆活兒分下去又是另一回事。多機器人任務分配要問的是:給定五台機器人和二十件要取的包裹,誰該去拿哪一件,才能讓工作盡快完成,且不會有兩台機器人去搶同一個箱子?做得糟,機器人就會相撞、重複勞動,或讓任務無人認領。做得好,團隊就像一間運轉良好的廚房,每個人都悄無聲息地站對了崗位。

一個廣受青睞的妙招借鑒自經濟學:舉行拍賣。每項任務被拿出來競標,每台機器人報出一個成本——通常是它需要移動的距離,或它已經有多忙。出價最低者(最便宜、最順路的機器人)贏得這項任務。舉行許多次小型拍賣,每項任務一次,整張任務清單便會在沒有中央規劃者的情況下自行清空。這被稱為基於市場的分配,因為機器人表現得就像市場上的買家。

  1. 宣布:一項任務(「去取7號包裹」)被廣播給團隊。
  2. 競標:每台機器人估算自己的成本——距離、電量、當前負載——並發出那個數值。
  3. 授予:出價最低者認領該任務;其餘機器人放棄它,轉看下一項。
  4. 重複:持續進行,直到每項任務都有歸屬;若有機器人失效或出現新任務,則重新拍賣。

為什麼達成一致真的很難

紙面上,鄰居平均和拍賣聽起來很整潔。現實世界卻亂糟糟的。訊息傳播需要時間——這種延遲稱為時延(latency)——所以當機器人A聽到機器人B的數值時,B早已挪到別處去了。更糟的是,無線訊息會遺失:一個封包憑空消失,沒人察覺,直到機器人之間已漸行漸遠。一致性協定必須能在陳舊的、缺失的、亂序的資訊中繼續運轉。

兩台機器人甚至會對現實本身產生分歧:A的感測器說走廊暢通,B的卻說被堵住了。沒有裁判來宣判誰對誰錯。因此,好的協調被設計成能從容容忍分歧——隨時間把分歧平均掉、在某個贏家沉默時重新拍賣,或在鄰居掉出無線電範圍時放鬆編隊。目標不是完美而即時的一致,而是能從不可避免的小故障中恢復過來的一致。