# 論文筆記——Multiagent Systems: A Survey from a Machine Learning Perspective

## Ch. 2 Multiagent System
這段會藉由提供可從中受益的典型領域的特徵，強調MAS的需求和實用性。

如果不同的人或者組織之間有不同的目標和專有資訊，就需要MAS來處理他們的交流，就算每個組織都希望使用單一系統來處理內部事務，也還是不會給予任何一個人建構代表群體系統的權力。綜上所述就是不同組織都需要屬於自己的系統來反映他們的能力和優先度。

==例子1：有生產輪胎的公司X，和被X發包製作螺帽的公司Y。為了自動化某些生產流程，公司XY的內部必須各自被規範，但他們都不想把自己公司的資訊和控制權放出給對方，這時就需要MAS幫助。==
==例子2：醫院排程MAS需要各種不同代理人來代表不同醫院人員的利益，想要讓病患待在醫院的時間越少越好的護理師、想要讓X光機吞吐量最大化的操作員等等。因為每種職責的人所考量的東西不一樣，所以需要不同的代理人來公正考量他們的利益==

對於處理多樣化的任務，比起交由一個中心化代理人，使用擁有各自專業的代理人來分配子任務更能有效解決問題。(當然比如只有單一化任務或者沒有不確定性的任務還是可以使用單一代理人)

就算是使用非分布式系統的情況也仍然有使用MAS的理由，其中之一是利用平行運算來加速系統，來克服擁有時空間複雜度限制的推理運算；其餘則是健壯性和可擴充性。
### 分類
從分佈式人工智慧可以列出四種面向
1. 代理細緻度(粗與細)
2. 代理人知識異質性(多餘與專業)
3. 分散控制方法(和平與競爭、團隊與階級、穩定與切換角色)
4. 交流可能性(留言板與傳訊、高階與低階、內容差別)
MAS擁有粗顆粒的代理細緻度以及高階通訊，第2,3點則是整個囊括在內，其中異質性對MAS又尤為重要，這篇論文的重點會放在代理人的同/異質性與通訊程度。

從MAS的應用面向又可以列出三種重要特性
1. 系統功能
2. 代理人架構(異質性程度、反應性與協商性)
3. 系統架構(通訊、協定、人為操作)

### 單一代理人v.s.多重代理人系統
每個中心化系統都擁有單一代理人負責進行決策，其他都算是魁儡，不過還是具有多重執行的能力，不過也代表每個實體在傳送或接收資訊時都只經由同一個中心代理人。

#### 單一代理人系統
代理人建模的範圍有自己、環境、和他們 之間的互動，且代理人擁有自己的目標、行動和知識，在這個環境中只有代理人本身擁有這些特質，就算有其他代理人，也不會被建模為擁有目標之類。

#### 多重代理人系統
代理人之間會知道互相的目標和行動，和單一代理人系統最大的差別在於環境的動態會受到其他主體影響。除了不可抗的環境變動以外，每個代理人都能以自己的意志影響環境。

系統內的代理人們可能有不同程度的異質性、擁有/沒有通訊手段

## Ch. 3 現有成品整理
許多機器學習技術都可以透過劃分出只需要單一代理人的領域，應用到多重代理人之中，並藉由數個代理人同時學習來完成。

### 捕食者/獵物，又稱為追逐(pursuit)領域
已被廣泛進行研究、擁有多主體案例的實例化、又涉及讓代理人在環境中移動的特性，適合作為機器人MAS的示範解說。

捕食者的目的是抓住獵物，或者包圍使獵物無法逃脫，也可以利用環境的邊界(如果有)協助圍捕。圖3的環境設定是離散網格狀(也可以有各種不同形狀的邊界or無邊界)且頭尾相連的方形世界，捕食者和獵物每步都只能移動到各自的相鄰或對角格子。
初始的獵物移動模式是隨機的，且偶爾停止以模擬比捕食者還要慢的速度。也可以讓獵物主動逃離包圍網，關於逃離包圍網的研究還有很大的進步空間。其他可調整參數如下表

這個主題適合被用來示範是因為捕食者和獵物的行動和目的都有良好規範，又足夠靈活套用各種變化。雖然沒有使用MAS的必要，但在某些實例中，它符合了MAS的平行運算、強健性和簡易程式設計。

如上所述，這個主題可以用單一代理人完成，上帝視角的代理人經由觀察捕食者的位子來決定他們的移動方式，獵物仍然是隨機移動，情況會是如下圖
如果把問題想做DPS其實也可行，只要分割成子任務就好。

#### 領域問題
對系統設計者來說，領域的特性和代理人的性能同樣重要，領域特性包刮：
1. 代理人數量
2. 進行決策的時間限制
3. 是否追加新的目標
4. 交流成本
5. 失敗成本
6. 使用者干涉
7. 環境不確定性

有個失敗成本高的例子是空中交通管制；低的則是被稱為定向即興創作，代理人會接受所有來自其他人的即興建議，出發點是不用害怕去犯錯。

人為干涉的情況下，代理人必須去計算與使用者的通訊問題，有個例子是對用戶回饋訊息進行過濾的代理人。

## Ch. 4 同質非交流MAS
如下圖，在代理人不會互相溝通的情況下，目標、行動、領域知識都會相同
這樣的系統下，所有代理人有著相同的內部結構、目標領域知識和可行動作，他們在選擇行動時也會有相同的思考過程。不同的只有他們的輸入資訊以及實際行動(不同工作分配給不同代理人)。

### 追逐(pursuit)
比起交由單一代理人決定所有捕食者的行動，四個捕食者都會各有一個相同的代理人。就算他們的思考決策能力都相同，對於其他代理人的資訊所知甚少，所以預測各自的行動會有點困難。反過來說，只要能得知各自的輸入資訊，就能預測彼此的行動，知道捕食者接下來會往哪裡走。

Stephens and Merx提出以區域知識為基礎的訣竅式行為，藉由獵物的周圍四點作為輸入的位置資訊，並讓捕食者將離他最近的一點作為移動目標。因為沒有彼此的資訊，同時有兩個或以上的捕食者想去同一個目標點是正常的，也因此可能會造成捕食者在路上互相阻擋。就結果來說不能說很成功，但提供了以下兩種控制方法的比較基礎：分散式和中心式。

Vidal and Durfee使用叫做Recursive Modeling Method(RMM，遞迴建模法)的方式，大意是藉由預測另一個代理人的行動來決定自己該怎麼走，因為可以無限遞迴推理(我預測你預測我的預測)，需要設定停止點。

Levy and Rosenschein將賽局理論應用進這個主題，使用payoff function(感覺像機會成本，選A會得到多少收益、選B會得到...)使代理人互相合作，需要知道其他捕食者的位置資訊。他們的模型混合了賽局理論的合作和非合作賽局。

Korf則是使用了讓每個代理人最大化自身效益的方法，藉由獵物的吸引力和其他捕食者的排斥力形成一套法則，使得每個捕食者都會由不同方向靠近獵物，就結果來說非常成功，尤其是在可走對角線或者六角形的地圖。他提出了一項結論是，至少在這個主題下，合作是幾乎不需要的，有效的反而是貪婪行為。但後續會有部分案例不適用貪婪行為。

### 一般的同質MAS
這個情況下會有一些有著相同結構，比方說感應器、動器、領域知識、決策函式等等，但輸入資訊和動器輸出不同的代理人，換句話說就是在環境中各司其職。讓不同的輸入資訊帶出不同的動器輸出對多重代理人系統是必要的，不然每個代理人都只會做相同動作。

### 問題與技術
多重限制下仍然會遇到的問題&作為例子示範解決問題的方法
#### 反應式v.s.協商式代理人
決定代理人推理的複雜度是很重要的，反應式代理人單純對於外部環境刺激給予預設反應，因而不需要保存內部狀態；協商式的行為反而像是在思考，考量行為、保存內部狀態、並預測行動帶來的影響；當然也存在兩者混合的模式。

##### 反應式代理人的部分
Balch and Arkin使用同質非交流的反應式代理人研究自動化機器人的編隊維護。機器人的目標是保持軍事隊形進行移動，途中可能會遇上障礙物而需要繞行，經過障礙物後要回復成原來的隊形。代理人運用感應器得到的資料(其他機器人的位置)反射性迴避障礙物和其他機器人，並朝目標前進、整合隊形，前進方向由以上四點的向量加總而成。

##### 協商式的部分
在協商式光譜的最極端處是Levy and Rosenschein的追逐(pursuit)領域，代理人依靠賽局理論的技術以及推估各自的行動權衡出應該進行的行為。

Rao and Georgeff提出了名為OASIS系統的混合反應以及協商的代理人系統，這個系統能推算什麼時候該反射行動、什麼時候該遵循計畫行事。

有一種混合式方法名為反應式協商，Sahota提出一種代理人，需在60赫茲頻率下推理該進行哪一項反應行為。Barman等人開發了使用反應式協商的足球機器人系統。

雖然反應式協商不是為了MAS而設計，但因為有著實時運算的能力而有著擴展到多重代理人的可行性。
領域狀態的變化可以是不確定的，代理人可能不清楚其他代理人的行為，或者不知道自己行動後的影響，被稱為「先驗」，獲取經驗之前的狀態。

#### 區域或全域視角
該讓代理人接收多少資訊也是個重要的問題，因為僅給予部分資訊的效果可能來的比什麼都給還要好。

Roychowdhury等人考量了一種多個代理人分享相同的資源，他們必須學習(或適應)如何分配資源，要記得這裡的代理人沒有溝通手段又有相同的行為規則，所以可想而知會同時目光放在資源使用率最低的部分。如果相反過來，對每個代理人開放不同的資源資訊，反而會有好的成效。

#### 對其他代理人狀態的建模
Durfee做了一項實驗「幸福的無知」(Blissful Ignorance)，使用有限的RMM(遞迴建模法)來讓代理人清楚地建模其他代理人的belief state，包括通曉其他人的belief states。這樣的知識背景一旦加上RMM就會造成無限遞迴，所以必須忽略一些潛在知識，因此Durfee提出了更普遍適用的方法。

RMM旨在於藉由建模內部狀態資訊和其他代理人來預測他們的行動，因為具同質性也知道其架構。不過行動終究是推測而來的，因為各自的輸入資訊不同，也不知道實際的內部資訊。隊更複雜的MAS而言，可能還要額外對其他代理人的目標、行動和能力進行建模。

代理人的建模距離完成還很遙遠，Schmidhuber將多重代理人強化學習的形式定義為：代理人不對其他代理人視為代理人，而是將他們當作環境的一部分以及視作感知的一部份來影響彼此的決策。代理人將重點放在獎勵機制和如何行動可以得到獎勵，並藉此發現，不需要互相建模也能夠達成合作關係。

#### 如何互相影響
因為不能交流，想要對其他代理人提供訊息就只能靠間接方法，比方說可以被偵測，或者受到他代理人影響而轉換狀態。Holland提出了刺激(stigmergy)的概念，分為主動刺激(active stigmergy)和被動刺激(passive stigmergy)。
- 主動刺激(active stigmergy)意思是讓代理人改變環境狀態以影響其他代理人偵測到的資訊，比方說機器代理人可以做記號讓其他代理人知道，或是用訣竅來改變環境，對其他代理人的未知任務推一把。
- 被動刺激(passive stigmergy)意思是讓代理人改變環境狀態已影響其他代理人行動時帶來的結果，比方說讓代理人關閉主水閥，另一個代理人打開受到主水閥影響的水龍頭的效果就會隨之改變。

對於被動刺激，Holland用機器人系統說明其概念，系統模擬蟻群在蟻巢周圍遇到許多死螞蟻的行為，螞蟻會轉為將死螞蟻運送一小段距離並丟棄，經過好一段時間後，死螞蟻會被群聚為好幾個小山，在經過一些時間，死螞蟻會被堆疊成一座大山。雖然代理人具同質性，但沒有溝通手段，但卻經由合作完成一項任務。

Holland再進行一項實驗，這次將相同的數個機器人放置在散落許多曲棍球的空間，行為只有直直前進或者遇到牆壁時轉彎，當一次堆動大於三顆曲棍球時停止，機器人一樣不會溝通。經過一段時間後也能將曲棍球聚成一堆，這是因為當機器人推著曲棍球靠近成堆的球山時會因為數量而被迫停止，另外若是帶著角度接近球山時則會將一些曲棍球給帶走，經過足夠的時間就會形成跟螞蟻實驗一樣的結果。

Mataric讓機器人進行Q-learning(強化學習方法)來學習尋找曲棍球、回家、和跟隨等行為。機器人學習如何獨自決策，並借助進度計算機給予的中途獎勵來處理高維狀態空間，以及利用boolean值來壓縮各種狀態成一種。實驗結果展示了會跟隨其他機器人的機器人能根據其他機器人的相對位置進行相應行為。

### 額外的學習機會
關於尚未開發過的學習方法可參考表格5，其中一項是可以使其他代理人做某些事，或許做這件事不會給自己幫助，但代理人可以藉由這件事幫助其他代理人，Kaelbling提出延遲獎勵型的強化學習會鼓勵代理人學習藉著回傳區域強化資訊給之前的狀態和行動來達成目標。缺點是如果只會獎勵其他代理人，這個代理人就無法進步，能解決的話對於MAS會很有用。

對於無法得知其他代理人的內部資訊和輸入資訊的情況下，建模其他代理人的方法還有多開發空間。成功得知的話便能確定自身未來的行為，不能得知的話也能對代理人的學習提供幫助。如果代理人X的輸入和代理人Y的有一定程度的相關，X就能夠靠學習方式將自己得到的輸入推算Y的輸入，再將這個輸入用RMM預測Y的行為。

## Ch 5. 異質非交流MAS

### 追逐(pursuit)
這裡的追逐領域不需要讓每個捕食者都有相同的目標、行動、或領域知識，而且獵物也不再受到限制(因先前的同質限制而只能隨機移動)，現在可以讓他有明確目標，可以被建模成一個代理人。

Haynes等人讓捕食者成為團隊，並增加他們的案例資料庫，讓捕食者和獵物競爭性成長。1995年使用基因程式設計(genetic programming)來設計一組四個捕食者的隊伍，每個個體都已經被分配好隊伍中的工作，並從中學習合作，彌補不能溝通的限制，了解彼此的未來行動。

1996年，他們使用案例推理讓捕食者學習合作。起初是讓獨立的代理人各自操作單一捕食者，這讓他們單純的靠近離自己最近的包圍網位置，同樣發生了互相搶點的情況而讓捕食者停止動作，這時代理人會記住這樣的負面案例以避免重蹈覆轍，隨著各自累積的經驗不一樣，思考模式也開始分歧，成為異質代理人，並在最後懂得避免在狩獵途中擋到其他捕食者路線的代理人。

同一年，他們用上設定了各種行為的捕食者(ex. ch4的追逐中提到的Korf的貪婪訣竅)以及自己設計的GP(genetic programming)捕食者，獵物也設定了一些脫逃演算法。結果發現獵物只要保持直線運動就不會被抓到，推測是因為Korf的方法只能對隨機運動的獵物起效用。這項發現對於使用MAS研究捕食者行為提供了更多的價值。

至於合作式的捕食者應該能夠處理懂得直線運動的獵物，比方說讓其中一個捕食者站在與獵物行進方向的同一直線，其他捕食者就能轉而進行包圍，但實際上沒有捕食者能夠朝這一方向進步，或者說沒有成為能力更強的捕食者。

### 一般的異質MAS
圖中以不同字型代表不同類型的單一項目，可以看到每個代理人的特性都不同，除了同質就不同的輸入資訊、動器輸出以外，目標、行動、領域知識都不盡相同。

### 問題與技術
表6提出一些摘要整理。首先是系統架設者的問題，在訓練進化型代理人面臨著信用分配問題：當數個異質代理人同時進化，可以是由於自身行為或是他人行為，但在讓代理人進步之前，他們得先理解給定的行為改變是有益或有害的。

#### 和善v.s.競爭
以複雜度作為代價加入異質代理人為MAS提供了巨大的潛力，異質可以有各種類型和數量的不同，目標、領域、行動等等，異質代理人系統其中一個重要的面向是，代理人帶不帶有競爭性。

是否要讓代理人互相競爭一直是設計MAS很重要的問題，和善的代理人可以去協助擁有不同目標的代理人達成目標，反之也可以只考慮自己，甚至在zero-sum的世界中還會去干擾對方。以生物學角度來看或許競爭才比較正常，合作只有在符合自身最大利益的時候才會去做。

而Ridley提出了細節記事來解釋大自然中各種利他主義的案例，通常是親屬關係造成的行為，以及人類社會的合作關係。不過不管有沒有利他主義，在適當的時機合作都能帶來效益。

Mor and Rosenschein模擬了囚徒困境，模擬中兩個代理人之間互相包庇可以得到最大利益，因為不是zero-sum關係，所以不會去陷害對方。若是給予代理人招出或合作兩種選擇，招出同伴會給予獎勵，但沒有透露其實合作帶來的利益更多，又因為這是囚徒困境，代理人之間沒辦法互相溝通，導致代理人會想要招出同伴。但如果持續對這兩個進行相同的模擬，合作的行為就會開始出現，還會利用合作帶來信用，如此以來以後遇到其他的合作代理人也能夠持續合作。

囚徒困境中的代理人雖然自私但不具競爭性，所以才有辦法合作，競爭性的代理人之間要合作就不大可能。比方說Littman讓兩個代理人進行zero-sum的遊戲，造成代理人會在對方完成任務的路上互相阻礙。
四種多重代理人的情況如下：同質非交流、異質非交流、同質交流和異質交流，每種情況都出現研究問題和解決方案，以及額外的機器學習機會。

#### 穩定型v.s.進步型代理人
進步型代理人較能適應動態環境，只是隨著學習進步，代理人會變得越來越複雜。和善進步代理人被稱為合作共同進步，競爭進步代理人則被稱為競爭共同進步。

機器人足球領域提供以上兩者成長機會，Stone使用TPOT-RL(Team-Partitioned, Opaque-Transition Reinforcement Learning)的方式讓足球代理人同時學習合作和競爭。

Grefenstette and Daley進行了一套與追逐領域有輕度相關的研究，環境中有兩個機器人以及放置在隨機位置且有香氣的食物，合作共同進步的機器人們必須都到達食物所在才算成功，競爭共同進步則是只有首個到達的才算成功。

競爭共同進步需要面對的一個問題是，雙方或者多方的進步可能是沒有盡頭的，對手之間互相抗衡並反擊的情況會一再上演，代理人對對手的行為特化並反擊的情況會一再上演，導致代理人不會收斂。第二個問題是信用分配(credit-assignment)問題，意旨當效能增加的時候，我們不一定清楚究竟是代理人進步導致，還是代理人的對手退步導致，相反過來看效能減少的時候也有相同的問題。

對於第二種問題有種解決方式是先固定一方的行為直到另一方進步，然後再交換，這個方法讓進步更加快速。除此之外Rosin and Belew搭配維持種族基因多樣性的方法讓代理人可以玩井字遊戲、Nim以及簡單版的圍棋。代理人運用基因演算法和名為competitive fitness sharing的方式進行競爭，competitive fitness sharing能保持族群基因多樣性，大略概念是同個族群內能夠擊敗對手，又不會被同伴擊敗的個體能夠得到更多信用，這些能夠擊敗對手個個體們會均分獎勵。

#### 建模其他代理人的目標、行動和領域知識
異質代理人的建模問題想當然比同質代理人還要複雜，再加上無法溝通，想要建模只能靠觀察取得資訊。Huber and Durfee模擬了通訊成本過高的背景，讓多個行動機器人協調運動控制的案例。機器人只能經過觀察動作模式來推測其他代理人的目的地，這個推測代理人目標的行為叫做計畫識別(plan recognition)，對於競爭型代理人有不少用途，因為可以透過對手的目標或者意圖反過來擊敗對手。

OBSERVER系統提供了另外一種代理人學習的模式，透過觀察領域專家進而逐步了解計畫行動的前提和影響，觀察夠久後就能自行練習來完善這個模型。除此之外，對未知情況進行推理或許也會有幫助，稱為autoepistemic reasoning(自動認識推理)。

RMM同樣可以用於異質代理人，Tambe進行了讓代理人學習代理人團隊模型的研究，他先模擬空中戰鬥的環境，再讓代理人根據對手的行動用RMM推斷他們的計畫。比方說擊發的導彈雖然快到看不到，但根據觀察到他們在準備時的行為可以推測導彈已經被擊發。

整個代理人團隊進步後可能發展出的問題是，如果沒有對團隊角色建模，除非是在團隊練習中，不然對手的行為可能沒有任何意義。(這段翻譯不確定，ctrl+f [Tambe, 1996])

建模其他代理人這件事也有著不少必要性，因為代理人有時候不得不依賴其他代理人來完成目標，比ㄤ說合力推動木塊、或是追逐領域要合力進行獵捕。Sichman and Demazeau分析了如何產生和處理不同依賴性的代理人之間互相衝突的模型的案例。

#### 資源管理
異質MAS也會面臨資源短缺的問題比如，網路負載下有多個代理人需要傳送多個不同資料。Glance and Hogg使用基因演算法研究多代理人狀況下的布雷斯悖論，布雷斯悖論是指當在網路上增加了一條路線反而拉長傳輸時間的現象。他們使用基因演算法來呈現不同網路管道在不同使用方式下的資源花費，而正在使用該網路且各自推理該取用哪條網路管道的代理人就無法達到全域最佳解。有研究得出想要有全域最佳解可以從改善基因演算法的呈現方式(Arora and Sen)。

關於適應負載平衡已經被作為多重代理人問題研究，研究如何讓不同代理人決定該使用哪個處理器。Schaerf運用強化學習，使異質MAS能夠在沒有中央控制和溝通的情況下完成負載平衡推理。代理人持續追蹤每項工作在配給資源的情況下完成的時間，並給予鼓勵他們嘗試之前沒被使用過或成效不彰的處理器。

#### 社會習俗(social convention)
現在已經有不少針對異質代理人如何達成協議或共識所做的研究，以人類例子來看，今天我身處巴黎要跟朋友見面，但沒有聯絡手段，也沒有事先溝通，那麼要幾點到哪裡才見的到面？提問者當場得到的回覆有75%都是在中午前往艾菲爾鐵塔，由此可知，具有共識的顯著特徵常常就是解答。

Fenster等人提出了焦點法，討論出文化上或是程式編寫的偏好特殊事物來讓代理人不用溝通就見到面，在沒有其他變數影響的情況下應該要選擇的應該是罕見或者極端的目標物。但上述技術上是有事先經過討論的結果，Walker and Wooldridge則提出選擇會偏向最近曾去過或頻繁來往的地方，也就是由經驗累積。

#### 角色
有相似目標的代理人可以組成團隊，並各有各的角色。在和善情況下，先由一個代理人分派角色給不同代理人，如果代理人具有靈活性，那他就可以切換角色。Prasad等人設計了可以初始化或是擴充蒸氣泵(ㄅㄥˋ)設計的代理人，再使用監督式學習幫助代理人決定在不同情況下該扮演哪個角色。

Tambe的STEAM系統能夠動態去指派或切換團隊中的代理人該扮演的角色，使得當關鍵代理人停止運作的時候能夠即時回復系統運作。Stone and Veloso的locker-room agreement系統也能做到類似行動。

如果代理人是獨自進步，則系統最後會以代理人陷在同一角色或代理人們都只會做相同事情作結，Balch以鼓勵行為多樣化的方法去研究克服這個問題。

### 額外的學習機會
客觀能力評量(objective fitness measurement)的方法需要用在測試各種進步技術中，在競爭性代理人情境中，很難隨著時間經過提供充足的效能測量，如果雙方進步一樣多，不管代理人進步程度如何應該都很難顯示在結果上。其中一個方法就是讓他去應對過去的對手才有好的指標，但又會面臨到，或許現在的代理人是對現在的對手特化的，並不適合舊對手。

而在合作性代理人情境中，雖然代理人能穩定學習互助行為，目前大多數機器學習技術都在探索有助於解決自身缺陷的行為。這個現象反而使得代理人在學習過程輸入能和其他代理人的行為良好結合的偏差值。(這段不確定)

在建模其他代理人的狀態後，下一部可以進行的研究是對他們的未來行動進行預測。

而在團隊的議題中，也可以不須經由指派任務的過程切換角色，若是自己發現另一個角色更適合現時的自己，就自行切換過去。最大的挑戰是要讓代理人任知道當時適任的角色。

## Ch 6. 同質交流MAS
有了溝通手段，代理人之間可以更有效地合作

### 追逐(Pursuit)
回顧之前Stephens and Merx的方法，原本只顧著往離自己最近的獵物周圍前進，導致捕食者互相阻擋，但現在捕食者之間能夠交換資訊來讓圍捕更加有效率，透過確認大家要前往的位置都不一樣，並讓最遠的捕食者選擇最近的位子並通知前進路線，其餘依序做同樣的事完成工作分配。(但只使用簡單的溝通也帶來了部分的失敗可能)

### 一般的溝通MAS
代理人之間依照圖示的方式互相溝通，從實際角度來看，訊息流通的方式應該是廣播、黑板系統、或者是單一代理人對單一代理人。

### 問題與技術
溝通功能的增加帶來一些需要解決的問題，大多數都發生在異質代理人，僅有少數在同質。

#### 分散的感官
Matsuyama的合作分散視覺計畫(cooperative distributed vision project)目標是透過不管是固定或是動態機器人裝載的多個攝影機，動態建構廣闊的三維視覺場景。比方說在城市中追蹤一輛車的動態，當車子離開一台攝影機又進到另一台的視野的時候，需要判斷是否是同一台車。這其中涉及的是對於環境中新資訊的注意力轉移，稱為主動感應，及攝影機間的溝通。

另一個例子是Moukas and Maes的trafficopter系統，車子蒐集路況資訊並傳送給其他車輛，以幫助彼此找尋出導航的最佳路線。舉例來說，當一條路線上的汽車可能會收到路況詢問，通過車輛之間的通訊，這台車能夠建構出有不同路線的交通地圖。(trafficopter原意為交通直升機，但應該無關)

#### 通訊內容
代理人能夠交換他們擁有的各種資訊，Balch and Arkin進行多機器人交流各自狀態和目標的實驗，發現在交換目標資訊後的成效會稍微優於交換狀態資訊的成效，而兩者又都比不溝通要好上許多。Stone and Veloso也發現讓代理人交流內部狀態資訊可以在足球機器人產生效用，因為能夠讓整個隊伍的成員都確切知道對手和球的位置。

### 額外的學習機會
通訊所依靠的其中一項要素是頻寬，而在許多領域會遇上無法完整交換訊息的情況；另一項是延遲，過時的資訊可能一點幫助都沒有。對付這樣的情況，可以嘗試讓代理人經由觀察學習到對話對團隊效能的影響。

## Ch 7. 異質交流代理人
這個類型的代理人有不同的輸入資訊、目標、行動、領域知識，又能夠互相交流，讓MAS的長才在這裡完整發揮，而且通過這兩個特性，MAS可以變相成為一個單一代理人系統，經由把情報和指揮權交給一個代理人實現。

### 追逐(pursuit)
Tan在這個主題下進行Q-Learning的實驗，環境中有數個獵物以及數個視野被限制的捕食者，捕食者不會隨時知道獵物的位置，因此捕食者需要互相給予資訊來狩獵，而且還能交換強化資訊和控制策略來幫助彼此。

Stephens and Merx使用一種每次都能成功的方法，它需要比第六章的方法要多的通訊成本。其中三個捕食者會將所有的輸入資訊交給剩下的那個捕食者代理人，它會決定並回傳大家接下來的移動路線，這個方法符合一開始定義的單一代理人系統。

Benda等人(追逐的開創人)考慮了可以交換資料、交換資料和目標、單一控制等等由四個捕食者的組成架構，並且在較少的交流成本和較好的決策之間進行權衡，最後得出交流成本可能會以頻寬限制或浪費推理時間的形式出現。

也有對成本和自由度進行權衡的實例，兩者程度呈反比。Osawa提出捕食者所要經歷的四個階段按照成本由小到大分別為：自治、交流、談判、控制，當現時使用的方法無法有足夠進步的時候就應該往下一個決策方式前進，照這樣的方法來捕捉獵物。

### 一般的MAS
代理人可以各自保有不同程度的異質性

### 問題與技術
異質代理人可以選擇不溝通，也可以在某些時候選擇變成同質代理人或調整自己的異質性。最常在這裡被研究的議題是通訊協定和承諾理論，合作或競爭性代理人在這要處理的也愈發複雜。

#### 互相理解
不管是哪種類型的交流MAS和某些由不同設計者建立的代理人，在溝通時一定是遵循某種通訊協定，協定面相包括訊息內容、通訊格式和協調規則。對此設計出的協議有：
* Genesereth and Fikes的內容的知識交換格式(KIF，Knowledge Interchange Format，用於在不同的電腦程式之間交換知識)
* Finin等人的通訊格式的(KQML，Knowledge Query and Manipulation Language，知識查詢與控制語言)
* Barbuceanu and Fox的用於描述協調方式的COOL語言

讓代理人以符號交流的方法確保了符號是能以類似方式紮跟在不同代理人之間的內部表示法(我覺得是像暗號那樣的意思)，第五章提到的社會習慣也可以透過分享過去經驗讓一個符號紮跟為表示法(用到習慣用到懂)，這個技術已經被Jung and Zelinsky用在異質多重吸塵機器人的清掃任務。

Jennings and Wittig創造了身為第一個用在工業MAS的ARCHON成功整合幾個legacy system，在同時應用五個不同的工業設定時，ARCHON讓獨立開發的異質電腦系統互相溝通以達成合作加工的控制系統。

Grand and Cliff的creatures是基於複雜的生物學模型的多重代理人電腦遊戲，模型中的代理人能夠透過和環境中的其他代理人和人類使用者互動來生長和學習，甚至能學習簡單的動詞賓語。

#### 計畫交流行為
當代理人與其他人交換資訊時一樣會對代理人產生影響，所以在計畫的架構中可以先為代理人定義交流行動的前提和影響。而當和其他代理人模型接觸時，交流可能會導致改變代理人對其他人狀態的認知，這樣的交流理論被Cohen and Levesque及Lux and Steiner叫做speech acts。

Mataric在這項理論加上學習的維度，他先用自己的曲棍球機器人實驗，讓機器人學習選擇社會行為包含廣播和聆聽，並將Q-learning擴充以便透過自身獲得的獎勵或其他代理人獲得的獎勵來得到強化。

而有的代理人為了達成特定目標可能會傳送錯誤的資訊，像是欺騙的情況就會發生。Sandholm and Lesser分析了一種框架，框架中的代理人可以透過罰款來撤回與其他人的協議，有時候能觀察到代理人隱瞞他違背規定，而希望其他代理人先這麼做，這樣的情況下，代理人就得思考該不該相信收到的訊息。

#### 和善v.s.競爭
這邊會提更多的競爭性代理人範例。Weiß做了很像Tan的多重代理人強化學習追逐實驗，讓Q-learners互相競爭，他們會用競標爭取單一系統的控制權，得注人能夠行動並獲得這個行動的所有收穫。

Clouse一樣用Q-learning訓練和善代理人，讓代理人在溝通中教導其他代理人。一開始有個訓練者擁有中等專業知識，而學習者可以經由模仿得到獎勵，且訓練者可以推薦學習者該在什麼情況做什麼事以便得到獎勵，最後訓練成不須指導就完成任務。

因為訓練的概念大有看頭，不少研究把目標放在減少人為訓練，系統設計者只要開發簡單的代理人行為並慢慢增加複雜行為，適當加入競爭性共同進步的族群可以減少設計者的工作量。Potter and Grefenstette用兩個互相爭奪食物的代理人進行此一研究，基因演算法規則的subpopulations(亞種?)的加入讓代理人處理不同情況時更有效果，因此對於各種情況特化出來的規則可以相應地塑形行為進而使訓練收斂。

Bull等人也將基因演算法被用在合作共同進化的分散式通訊代理人，訓練控制四足機器人的四隻腳。

#### 談判
有些研究者根據供需法則(the law of suplly and demand)設計了談判MAS。在Smith的contract nets框架中，代理人自私、都有各自的目標且推理資源有限，他們可以出價收購，並且執行其他人的任務或將任務發包給其他人，發包時必須付出金額，因此會去尋找最低的出價者，Sandholm and Lesser發現整個過程中會出現不少問題。

Huberman and Clearwater做了類似的研究，他們的MAS要控制一棟建築中不同房間的氣溫，人可以任意設定空調溫度，不管是要增溫或降溫，代理人都必須去向其他代理人請求多出來的空氣，他也可以將自己房間多出來的空氣賣出，代理人的目標是要模擬熱量轉換並用最好的價碼達成目的，市場會調整自身以提供合理的共享資源。

Zeng and Sycara使用競爭性MAS來研究談判系統，代理人使用貝氏推論來更新彼此議價的模型。Parunak等人的MarCon系統利用基於市場的方法處理分散式約束問題，供應鏈中不同位置的設計師通過買賣特徵並傳遞產生的約束來談判整體設計的特徵。(最後一句不確定)

#### 資源管理
MarCon是其中一個例子，因為一個代理人所想要的設計特徵可能會消耗另一個的資源。GPGP(generalized partial global planning)讓數個異質代理人在一段一間內發布限制或允許做某項任務給區域性的排程者，不需要中心式代理人的幫助進行協調。Lesser提出基於GPGP的一般多重代理人包含五種元素：
* 區域代理人排程
* 多重代理人協調
* 組織設計
* 檢測
* 診斷

Sugawara and Lesser提出異質交流代理人可以學習根據現在狀況選擇協調策略，以此診斷區域網路(LAN)。較不複雜的協調策略雖然需要較少的網路和時間資源，但可能造成多餘的行為或甚至任務失敗。

Sycara等人的RETSINA利用三種類型的異質交流代理人來傳送資訊來回應特定用戶的資料查詢，也能同時在符合資訊代理人的網路和資源限制下搜索多個資訊資源來滿足多個使用者的需求。這個MAS已經被應用在數個分散式網路應用程式包括財務投資組合管理、個人資訊管理、會議排程、以及衛星能見度預測。

Parker的ALLIANCE和L-ALLIANCE使用異質機器人的通訊協助區分獨立任務，這兩個系統強調容錯性，只將當前進行中的任務廣播出去。如果通訊出差錯，多重機器人會先暫時執行相同的任務，接著由觀察得知任務重複被進行，該代理人便會去做其他任務。L-ALLIANCE在這之上還讓代理人學習評估任務的適合度，以有效分配任務。

#### 承諾/解除承諾
經過交流，代理人可能會全心全意或暫時協助任務，這時他們需要訂定承諾，以確保他們會投入工作，其中不會管他能為自己提供自己多少利益。這樣的機制因為提供了讓代理人互相信任的媒介，使得系統運作得比較平穩，但問題就出在不知道該怎麼讓自私的代理人做出承諾，承諾/解除承諾的理論開始被研究。

Castelfranchi定義三種承諾的類型：
* 內部承諾：約束自己進行某種事
* 社會承諾：兩個代理人互相的約束
* 集體承諾：一個代理人同意擔任某種角色

Haddadi將承諾狀態用在計畫狀態上，包含潛在合作、預先承諾和一般的承諾。代理人可以用[手段與目的分析](https://terms.naer.edu.tw/detail/1303176/)來規劃有關承諾機會的目標，會在BDI(belief/desire/intention)模型中運作。BDI是一種建模其他代理人的技術belief代表其他代理人的領域知識，desire代表目標，以上兩者被建模為他們的意圖(intention)，或者當前要達成的目標以及達成目標的方法。OASIS(空中交通管制方法)就有使用到BDI，在澳洲的Sydney機場和有完全控制權的飛行員進行測試，每架飛機都是控制代理人，且與全域排序代理人交流。OASIS是混合了反應式與協商式行為的代理人，他們可以在遇上需要及時反映的形況時打破排定的流程，而因為代理人不能控制自己的目標或領域知識，因此只能根據自己的意圖做出承諾。

Stone and Veloso的Locker-room agreements是另一種交流代理人承諾的型態，當代理人能在安全通訊環境中同步時，他們會同意協定和工作分解，以在通訊受限的動態時段使用，而在這段期間，代理人會互相依靠來遵從條約。

整個集團的代理人或許會打算互相承諾，但比起一對一承諾或者全員承諾，Zlotkin and Rosenschein提出有些情況會讓代理人想組成聯盟，代理人在賽局理論的框架下會考量加入聯盟帶來的好處，像是藉由提升其他成員的效用來相對提升對方對自己的評價。Shehory and Kraus提出了用於任務分配的一種分散式演算法，可以用在需要聯盟的存在來進行任務或者提供比單一代理人更好的成效的時候。Sandholm and Lesser使用汽車路徑問題來說明在難以尋找最佳聯盟的情況下如何自行成立有價值的聯盟。

#### 合作定位
定位是機器人自動常面對的挑戰，大多數的機器人任務要求機器人得先認知自己身處世界的哪個位置，才能有效行動。常見的一種定位方法是Markov localization，機器人藉由觀察和環境地圖對當前位置保持機率性的信念。Fox對這個方法進行深入研究，當機器人A偵測到B，他可以用B的當前位置信念來強化自身認定的位置可靠性，這個方法在同質機器人和擁有不同感應器的機器人都有良好的運作。

Grabowski等人的Millibots是異質交流多重機器人系統的最小型原件，他能提供合作定位和地圖製作功能。每個millibot都只佔六立方公分，且專門配備一個子集合的感應器來蒐集環境資料。為了保持定位，團體中的其中三台millibot會停留在原地作為其他機器人的參考點，而這三台的其中之一可以定期移動到新的位置或者找另一台外人替代，如此一來整個全體都能夠移動。同時配有感應器的機器人會將蒐集到的資料廣播給較大的隊長機器人，他會整合資料並且回傳任務給其他機器人。

#### 變換形狀與大小
Castano等人開發了名為CONRO的具有變質能力的可部屬機器人，目標是創造一個可以重新拆分拼湊身上的元件而形成新型態的機器人(XX戰隊...)，當時他們把目標放在創造必要硬體元件，他們考量到在通訊方面需要使用到無線通訊以支援連接和遠端感應的需求。

### 額外的學習機會
有很多機會能靠機器學習來增強MAS能力，首要任務是預定義代理人的語言和通訊協定。而有個不同的選擇是讓代理人學習自成一格的通訊方式，比方說在一開始給代理人一小段語言和小集合的字義，但沒有去設定語言和字義的對照資訊，如此一來代理人就得學習如何發話和解讀接收到的訊息。預期會得到更有效的結果，因為他們理解的只有跟自身相關的東西，也就跟自身任務密切相關。

若將通訊視為發言行為，代理人就能被允許學習發言對系統的全域動態的影響。而在通訊頻寬較低或有過大延遲的情況下，代理人會學習各種時段的通訊效用。如果額外讓他們學習交流，代理人也比較有可能避免被不誠實的交流欺騙，可以經由多方資訊整合出真實情報。

而承諾能帶來的影響有好有壞，系統建構者可能想要允許他的代理人學習人麼時候要和其他代理人立定承諾。

###### tags: `論文` `Intellingent Agent`