011章 現實世界的規劃與行動

Post date: 2012/11/7 下午 01:19:29

目前茄子也沒能力簡化~只能先挑著書中的內容填在這裡了QAQ

本章中我們將看到,更有表達力的表示法和更具交互性的代理人結構,兩者是如何導致在現實世界中有用的規劃器。

時間、排程和資源

經典規劃表示談論該做什麼,以及依什麼次序,但是該表示不討論時間方面的事:一個動作需時多久以及它什麼時候會發生。

第10 章的規劃器能夠產生一個時程表,表中會說哪一架飛機預計分配到哪一個航次,但是我們實際上也需要知道起飛與抵達時間。

一架飛機的機組人員數目是有限的——在某航次的機組人員不可能同一時間會出現在另一個航次。

這一節中我們採用的方法是「先規劃,後排程」:也就是說,我們將整個問題分成一個規劃階段和一個排程階段,

規劃階段選擇行動並對其進行偏序排序以滿足問題的目標,之後是排程安排階段,時序資訊被添加到規劃中以確保滿足資源和最終期限的限制。

表示時序與資源限制

一個典型的加工車間排程問題,首見於第6.1.2 節,由一組作業所組成,每個作業由一群具有排

序限制的動作所組成。每個動作有一個持續時間以及該動作所需的一組資源限制。

資源能夠也可以由負向消耗的動作所產生,包括製造、種植與重新供應等等動作。

一個加工車間排程問題的解答必須敘明每個動作的開始時間,並且必須滿足所有的時序排序限制與

資源限制。正如搜尋與規劃問題,解答能夠根據某個代價函數被計算出來;這可能會非常的複雜,

具有非線性的資源成本,與時間有關的延遲成本,等等。為求簡化,我們假設代價函數就是該規劃

的全部持續時間,稱之為完工時間(makespan)。

資源表示為數值量,如Inspectors(2),而不是作為名稱實體,諸如Inspectors(I1)和Inspectors(I2),

這是一種稱為聚集的非常通用技術的一個例子。

求解排程問題

欲最小化完工時間(規劃的持續時間),我們必須尋找出所有動作的最早開始時間並須滿足問題所提出的排序限制。

將這些排序限制視為一個與動作有關聯之有向圖是很有幫助的,如圖11.2 所示。

我們能夠對於這個圖形運用要徑法(CPM)來決定每個動作可能的開始與結束時間。

分層規劃

前面幾章之問題求解與規劃方法都是在固定的一組原子動作下運作。動作能夠被串成序列或是

具有分枝的網路;最先進的演算法能夠產生含有數以千計的動作的解答。

由人腦執行的規劃,原子動作是肌肉致動的。粗略的估算,我們有大約10^3 肌肉可抽動(有些人

算的是639,但是其中許多有數個子組織);我們能以約每秒10 次的頻率來控制它們的抽動;我們活

著且醒著的時間大約有10^9 秒。因此,一個人終其生包含大約10^13 個動作,增或減兩個量級。即使

我們限制我們規劃於短促得許多的時間範圍——舉例來說,夏威夷度假兩週——一個詳細的行動規

劃包含約10^10 動作。這比1000 多上許多。

要跨越這個鴻溝,AI 系統必須做出人類顯然會做的事情:在更高的抽象層次做規劃。一個合理

的夏威夷假期規劃可能是「前往舊金山機場;搭乘夏威夷航空公司的第11 次航班去檀香山;享受兩

週假期;搭乘夏威夷航空公司第12 次航班回舊金山;回家。」給予這樣的規劃,「前往舊金山飛機

場」這個動作本身就能夠被看成是一個規劃任務,其解答像是「駕車去長期停車場;停車;乘機場

巴士去航空站。」這其中的每一個動作,反過來,能夠被更進一步分解,直到我們達到讓動作能夠

被不假思索地執行來製造出所需的行動控制序列的層次。

我們致力於階層分解方面,所有觸及管理複雜性的概念都會論及此。

複雜軟體從副程式或物件類的層次體系建立出來,軍隊作為單位的等級體系而運轉,政府和企業有部門、子部門和分支辦公室的分層體系。

層次結構的關鍵好處是,在層次的每一層上,一個計算任務、軍事任務或管理功能都被還原為下一個較低層次的少量行動,

所以對當前問題尋找正確的方法來安排這些行動的計算消耗是小的。

在另一方面,非層次方法將一個任務還原為大量單個行動;對大規模問題,這是完全不切實際的。

高層次動作

我們採用來了解階層分解的基本方法論,是來自於分層任務網路(hierarchical task networks)或稱HTN 規劃的領域。

另外的關鍵概念是高層次動作或HLA——舉例來說,於先前提到的例子,「前往舊金山飛機場」的動作。

每個HLA 有一個以上可能的強化調整,為一序列的動作[1],每個調整可能是個HLA 或是一個原始動作(依定義它不會有任何調整)。

一個只包含原始動作的HLA 調整稱之為該HLA 的一個實作。

搜尋原始解答

HTN 規劃常常用一個稱之為Act 的單一「上層」動作來公式化,這麼做的目標是尋找一個達成

目標的Act 實作。這是個全然地一般性的方法。

舉例來說,經典規劃問題能夠被定義如下:對每個原始動作ai,以步驟[ai,Act]提供一個Act 的調整。

這樣創造了一個讓我們增加動作的Act 的遞迴定義。

但是我們需要一些中斷遞迴的方法;我們的辦法是對Act 提供一個額外的調整,它具有空步驟

表且其前提等於問題之目標。這是說如果目標已經達成,那麼那個對的實作什麼都不會做。

該方法引申出一個簡單的演算法:於目前的規劃中重複地選取一個HLA 並以它的調整取代它,

直到該規劃達成目標。

搜尋抽象解答

將某人送到機場而不必決定一條精確路線、選擇停車地點等等。解答似乎是顯而易見的:寫出HLA

的前提-效果描述,一如我們寫下該原始動作做什麼。從該描述,應該很容易證明該高層次規劃達成

了目標。

如果我們推導出一個高層次規劃,經過證明於高層次動作的小範圍搜尋空間中是可達成該目標的,

那麼我們能夠承諾該規劃,且著力於調整該規劃的個步驟的問題。

這給了我們所渴求的指數量級的縮減量。要使這個能發生作用,就必須是達成目

標的每一個「鏈接」(憑藉它的步驟描述)的高層次規劃事實上是以符合稍早前定義的意義來達成目標

的情況:它必須至少有一個實作確能達成目標。這個性質被稱為HLA 描述的向下強化調整性質

(downward refinement property)。

一個安全的答案是(至少對所有前提與目標都是正的問題而言)是只要納入已被HLA 的每個實作

達成之正效果以及任一實作的負效果。那麼向下調整性質就會被滿足。不幸的是,這對HLA 而言是

過於保守的語意。

程式設計語言社群稱對手作出選擇的情況為惡魔般的不確定性,相對之下,代理人本身作出選

擇的情況,則稱之為天使般的不確定性。我們借用這名詞來定義HLA 描述的天使般語意。了解天使

般語意所需的基本的概念是HLA 的可到達集(reachable set):給定一個狀態s,一個HLA h 的可到達

集,寫成REACH(s, h),是任何HLA 的實作都可達到之狀態的集合。關鍵之處在於代理人能夠選取

它執行HLA 時所達的可到達集個元素;因此,一個具有數個調整的HLA 較諸相同但具有較少調整

的HLA 更「有力」。

一個HLA h 的樂觀描述REACH+(s, h)可能誇大了可到達集,然而悲觀描述REACH−(s, h)可能低估了可

到達集。因此,我們有:

REACH−(s, h) ⊆ REACH(s, h) ⊆ REACH+(s, h)

舉例來說,於規劃前述的兩週夏威夷假期,你可能會提議在七座島的每一座

島上各度假兩天。審慎的人會指出這個富有野心的規劃必須予以修改而加入島際間的交通往返細節。

具有承諾或是拒絕高層次規劃的能力能夠給予ANGELIC-SEARCH 較諸

HIERARCHICAL-SEARCH 有可觀的計算優勢,順帶的也比平淡古老的BREADTH-FIRST-SEARCH更具有鉅大的優勢。

考慮清理一個由狹窄走廊圍繞出的長方形房間所組成的真空吸塵器

世界。安排一個HLA 予Navigate(如圖11.4 所示)以及一個HLA 予CleanWholeRoom 是有意義的(重

複運用清理每行之HLA 得以使清理房間被實作出來) 。因為於這領域中有五個動作,

BREADTH-FIRST-SEARCH 所需的成本增加約5d 倍,其中d 是最短解答的長度(約略等於全部方格

數的兩倍);該演算法即使是兩個2×2 房間也無法處理。HIERARCHICAL-SEARCH 是更有效率的,

但是仍然受到以指數量級增加之苦,因為它會儘可能的清理與該分層一致者。ANGELIC-SEARCH

的大小約與方格之數目呈線性關係——它承諾好的高層次序列並刪去其它選擇。

天使方法能夠藉由一般化可到達集而延伸至尋找代價最小的答案。與其說狀態可以達到與否,

以最有效率的方式到該狀態時,它會有一個代價。(對於無法達到的狀態,該代價是∞)。樂觀的與悲

觀的描述圈出了這些代價的上下範圍。於這個方式,天使搜尋能夠尋找可證明最佳抽象規劃而毋需

考慮它們的實作。相同的方法能夠用於獲取有效的分層前瞻演算法(hierarchical lookahead

algorithms),以LRTA*的型式(4.5.3 節),供線上搜尋之用。

在某些方面,這樣的演算法反射了人類對於任務深思熟慮的一面,

例如規劃一個到夏威夷的假期——替代的想法剛開始時是經過很長的時間在一個抽象層次上完成;

規劃的某些部份會駐留在相當抽象的狀態直到執行的時候,例如如何在莫洛凱島渡過兩個慵懶的日子,

然而其他的部份則規劃的很詳細,例如打算搭乘的班次以及預約好的旅店——沒有這些調整,並不保證該規劃會是可行的。

在非確定性領域中進行規劃和行動

於這第一節我們延伸規劃至處理那些局部可觀察、非確定以及未知的環境。

無感測器的規劃(也被稱為一致性規劃)適用於不做觀察的環境;

應變規劃適用於局部可觀察的且不確定性的環境;而線上規劃與重規劃適用於未知的環境。

雖然基本的概念與第4 章者相同,也有顯著的不同之處。這些會發生是因為規劃器處理分解過

的表示而非原子的表示。這影響我們用來表示代理人動作與觀察之能力的方式,以及我們對無法觀

察與局部可觀察之環境信度狀態——代理人可能置身之實體狀態的集合——的表示方式。我們也能

夠運用第10 章中得到的許多領域無關方法的優點來計算搜尋啟發式。

考慮這個問題:已知一把椅子和一張桌子,目標是將它們配對起來——有相同的顏色。於初始

狀態我們有兩罐油漆,但是油漆和家具的顏色是未知的。只有桌子剛開始的時候是在代理人的視野

之內:

Init(Object(Table)∧Object(Chair)∧Can(C1)∧Can(C2)∧InView(Table))

Goal(Color(Chair, c)∧Color(Table, c))

有兩個動作:將蓋子從油漆罐移走並使用被打開之漆罐內的油漆來漆物件。行動模式很簡單,但有

一個例外:我們現在允許前提與效果包含沒有出現在動作變數表內的變數。也就是說,Paint(x, can)

沒有提到代表罐裡油漆顏色的變數c。

至於規劃,我們以一個新的模式類型,察覺模式,

來擴增PDDL:

Percept(Color(x, c),

PRECOND:Object(x) ∧ InView(x)

Percept(Color(can, c),

PRECOND:Can(can) ∧ InView(can)∧Open(can)

請注意即使無感測器代理人也能夠求解塗漆問題。解是

能夠打開任何一罐油漆並把它用於椅子和桌子上,這樣強制它們成為同一種顏色(即使代理人不知道

是什麼顏色)。

在真實世界中,代理人使用這些方法的組合。車輛製造商出售備胎與氣囊,這些是應變規劃一

部分的實際體現,旨在處理刺穿或碰撞等意外事件。

通常,代理人僅僅會去規劃那些有重要的後果且發生機會不可輕忽的意外事件。

因此,一個打算來趟橫越撒哈拉沙漠之旅的汽車駕駛員應該會對汽車拋錨做出仔細的應變規劃,

然而去趟超市則較不需預先規劃。

無感測規劃

轉換無感測器規劃問題為信度狀態規劃問題的運作方式與第4.4.1 節所做的方式相同;

主要差別是底層的實體轉移模型被表示成一群行動模式且信度狀態被表示成一個邏輯公式而非逐一列舉的狀態集。

我們假設底層的規劃問題是確定的。

無感測器油漆問題的初始信度狀態能夠不考慮InView 流,因為代理人沒有感測器。

代理人不知道罐子或是物件的顏色,或罐子是否已被打開的還是仍然是緊閉的,但是它確實知道物件與罐子有顏色

:∀x ∃c Color (x, c)。

特殊化推論(Skolemizing)之後,(見第9.5 節),我們獲得初始信度狀態:

b0 = Color(x, C(x))

其中已設定封閉世界假設,我們會假設任何沒有於狀態提及的流都為假但是於無感測器(與局部可觀察的)規劃,

我們必須轉向到開放世界假設,於此,同時存在正和負流的狀態,如果流沒有出現,則它的值是未知的。

我們現在展示如何透過動作序列來發展信度狀態,以顯示滿足目標的最後信度狀態。

首先,注意於一個已知的信度狀態b,代理人可以考慮任何前提被b 滿足的動作。(其他動作無法被使用,

因為轉移模型並沒有定義前提未被滿足之動作的效果)。

根據式(4.4),用於更新於一個確定世界中已給定之適用動作a 的信度狀態b 的一般公式如下:

b′ = RESULT(b, a) = {s′ : s′ = RESULTP(s, a) 及s∈b}

對於那些在b 中真假值是未知的文字該如何處理呢?有3 點不同:

1. 如果動作加入ℓ,則ℓ 會轉換成b′無論它的初始值為何。

2. 如果動作刪除ℓ,則ℓ 於b′中會為假無論它的初始值為何。

3. 如果動作不影響ℓ,則ℓ 將停留在它的初始值(是未知的)且將不會出現於b′。

因此,我們看到b′的計算幾乎與於可觀察的情況是一般無貳的,於該情況是透過式(10.1)來制定:

b′ = RESULT(b, a) = (b − DEL(a)) ∪ ADD(a)

舉例來說,如果我們施加RemoveLid(Can1)到初始信度狀態b0,我們得到

b1 = Color(x, C(x)) ∧ Open(Can1)

當我們施加動作Paint(Chair, Can1),前提Color(Can1, c)可透過已知的文字Color(x, C(x))滿足綁定

{x/Can1, c/C(Can1)}而新的信度狀態是

b2 = Color(x, C(x)) ∧ Open(Can1) ∧ Color(Chair, C(Can1))

最後,我們施加動作Paint(Table, Can1)得到

b3 = Color(x, C(x)) ∧ Open(Can1) ∧ Color(Chair, C(Can1)) ∧ Color(Table, C(Can1))

最後的信度狀態滿足目標,Color(Table, c) ∧ Color(Chair, c),變數c 勢必為C(Can1)。

如果目標是機器人要在乾淨的方格,那麼[Suck]是一個解答,

但是一個沒有感測器而堅持處於1-CNF 信度狀態的代理人就找不到它。

或許一個更好的解答是尋找個簡單的動作序列,儘可能的保持信度狀態。舉例來說,在無感測

器的真空吸塵器世界,動作序列[Right, Suck, Left, Suck]產生如下的信度狀態序列:

b0 = True

b1 = AtR

b2 = AtR ∧ CleanR

b3 = AtL ∧ CleanR

b4 = AtL ∧ CleanR ∧ CleanL

亦即,代理人能於保持1-CNF 信度狀態下解出該問題,即使一些的序列(例如,那些以Suck 開頭者)

偏離1-CNF。

一般的教訓是不要悖離人性:我們總是執行少數的動作(核對時間,輕拍我們的口袋確保我們還懷著車鑰匙,

當我們在一座城市中行走時會看路標)消除不確定性並讓信度狀態容易管理。

對於無法管理地扭曲信度狀態的問題有另一個非常的不同的方法:根本就不要想去計算它們。

假設初始的信度狀態是b0,且我們會想要知道從動作序列[a1, ..., am]所得到的信度狀態。不直接地計

算它,而是將它表示為「b0 則[a1, ..., am]」。這是偷懶的做法但是信度狀態的表示並不含糊,且它是

非常的簡明的——O(n + m)其中n 是初始信度狀態的大小(假設是於1-CNF)而m是動作序列的最大長度。

不過,做為信度狀態表示,它有一個缺點:判斷該目標是否被滿足了或是一個動作是否能用,

可能需要大量的計算。

該計算能夠當成一個蘊涵測試來實作:如果Am 代表一群定義動作a1, ..., am 發生所需的後續狀態

公理——一如於第10.4.1 節對SATPLAN 所做的解釋——而Gm 斷言於數個步驟之後目標為真,如果

b0 ∧ Am |= Gm,也就是說,如果b0 ∧ Am ∧¬Gm 未被滿足,那麼該規劃就達成目標。

給予一個現代的SAT 求解器,有可能比計算整個信度狀態更快完成這件事。舉例來說,如果在它的增加表中並沒有

一個序列中的動作有特別的目標流,求解器會立即發現這件事。

如果關信度狀態的部分結果——舉例來說,流已經知道為真或假——被快取起來以簡化隨後的計算也是有幫助的。

無感測器規劃謎題的最後一片拼圖是個啟發式函數,用來引導搜尋。啟發式函數的意義與經典

規劃者是相同的:從已知的信度狀態達成目標之代價的估計(或許可採納的)。

有了信度狀態,我們有一個額外的事實:求解任何一個信度狀態的子集合一定比求解信度狀態簡單:

如果b1⊆b2,則h*(b1) ≤ h*(b2)

因此,任何為子集合所計算之可採納啟發式,該信度狀態本身是可採納的。最明顯的候選者是單值

子集合,也就是說,個別實體的狀態。我們能夠隨機拿取信度狀態b 中任何一群狀態s1, ..., sN,運用

第10 章中任一個可採納啟發式h,再回來。

H(b) = max{h(s1), ..., h(sN)}

當作啟發式估計用以求解b。我們也能夠直接使用a 規劃圖於b 本身:如果它是文字的連言(1-CNF),

只要設定那些文字為圖形的初始狀態層。如果b 不是在1-CNF,那麼也有可能找出一起蘊涵b 的一

組文字。舉例來說,如果b 是在選言正規形式(DNF),DNF 公式是文字的連言,它蘊涵b 且能夠形

成規劃圖初始層。一如先前,我們能夠拿出由每組文字所得到的最大啟發式。我們也能夠使用非可

採納啟發式,如忽略刪除表啟發式(10.2.3 節),實務上效果似乎不錯。

應變規劃

我們於第4 章看過應變規劃——根據察覺產生有條件的分支規劃——是適合部分可觀察性,非

決定性,或是兩者兼具的環境。對於稍早所給具有知覺公理的局部可觀察的油漆問題,一個可能的

應變解答如下:

[LookAt(Table), LookAt(Chair),

if Color(Table, c)∧Color(Chair, c) then NoOp

else [RemoveLid(Can1), LookAt(Can1), RemoveLid(Can2), LookAt(Can2),

if Color(Table, c)∧Color(can, c) then Paint(Chair, can)

else if Color(Chair, c)∧Color(can, c) then Paint(Table, can)

else [Paint(Chair, Can1), Paint(Table, Can1)]]]

於這規劃中的變數應該被視為被存在性性地量化了;第二行說的是如果存在一些的顏色c 也就是說

桌子與椅子的顏色,則代理人不必做任何事情來達成目標。

當執行這規劃,應變規劃代理人能夠維持它的信度狀態如一個邏輯的公式,

並且藉由決定信度狀態蘊涵條件公式或是它的否定來評估每個分支狀態。

(端視應變規劃演算法如何確認代理人永遠不會陷於條件公式的真假值為未知的信度狀態)。

注意於一階條件下,該公式可以用一個以上的方式來滿足;舉例來說,如果兩個罐子的顏色與

桌子是相同的,條件Color(Table, c)∧Color(can, c)可以被{can/Can1}與{can/Can2}所滿足。那樣的話,

代理人能夠選取有令人滿意的代換運用於其餘的規劃。

如第4.4.2 節所示,在一個動作之後計算新的信度狀態且隨後的察覺於兩個階段內完成。第一個

階段計算動作之後的信度狀態,一如為無感測器代理人所做的:

bˆ = (b − DEL(a)) ∪ ADD(a)

其中,一如之前,我們已經假設信度狀態以一個文字的連言來表示。第二個階段有些難對付。假設

察覺文字p1,...,pk 被收到。你可能會想我們只須要將這些加入到信度狀態;事實上,我們也能夠推斷

用於感測的前提被滿足。現下,若察覺p 正好有一個察覺公理,Percept(p, PRECOND:c),其中c

是一個文字的連言,那麼那些文字能夠隨p 一起扔入信度狀態。在另一方面,如果p 有多於一個察

覺公理,根據所預測的信度狀態bˆ,它的前提或許會成立,則我們必須加進前提的選言。顯而易見,

這將信度狀態取離1-CNF,並帶來與有條件效果相同的複雜情況,具有大致相同的解答類型。

給予一個計算精確或者近似信度狀態的機制,我們能夠以於第4.4 節對信度狀態所用的AND-OR

前向搜尋的延伸來製造出應變規劃。具有不確定性效果的動作——它是只使用行動模式EFFECT 中

的選言來定義——能夠接受於信度狀態更新計算上的細微變更,而不會更動搜尋演算法[2]。對於啟

發式函數,許多對無感測器規劃方法的建議也適用於局部可觀察的,不確定性的情況。

線上重規劃

想像看著於一個車輛工廠的點焊機器人。當每台車輛通過作業線,機器人迅速,準確的動作會

一再重複。儘管技術上給人深刻印象,機器人看不出有些許的智慧,因為運動是一個固定的、預先

設計好的順序;在任何有意義的感知中,機器人顯而易見不 「知道它正做什麼」。現在假設正當機

器人準備點焊的時候,一個沒固定好的門掉出車外。機器人迅速將它的焊接致動器換為夾鉗,拿起

車門,檢查是否有任何抓痕,重新裝上車輛,發電子郵件給廠區作業主管人員,換回焊接致動器,

並且恢復它的作業。突然之間,機器人的行為好像有目的而非機械性的方法;我們假設它不是肇因

於一個龐大,預先計算好的應變規劃,而是從一個線上重規劃過程——這意指機器人必須知道它試

圖做的是什麼事情。

重規劃預先假設執行監控的形式以判斷是否需要一個新的規劃。

如果代理人的世界模型是錯誤的,重規劃便有其需要。

一個動作模型,可能有前提漏失——舉例來說,代理人可能不知道,打開漆罐的蓋子通常需要一個螺絲起子

模型可能有效果漏失——舉例來說,漆一個物件時也可能一併漆到地板

模型可能有個狀態變數漏失——舉例來說,前面所給的模型並沒有註記罐內的漆量多少、它的動作會如何改變漆量、或是需要漆量不是空的等等。

模型也可是缺乏對於外來事件的條款,例如有人打翻漆罐。

外來的事件也包括目標的變更,如增加桌子與椅子不能被漆成黑色的需求。

如果代理人倚賴絕對正確性的模型,但沒有監視與重規劃的能力,則它的動作很可能是極其脆弱的。

線上代理人有個如何小心地去監視環境的選擇。我們區分三個層級:

● 動作監控:執行動作之前,代理人先確認所有的前提仍然成立

● 規劃監控:執行動作之前,代理人確認其餘的規劃仍然成功。

● 目標監控:之前執行動作之前,代理人檢查看看是否有一個更好的目標集是它能夠努力達成的。

行動監控是執行監控的一個十分簡單的方法,但是它有時導致不太智慧的行動。例如,假定沒

有黑色或白色油漆,且代理人構造一個規劃來透過將桌子和椅子兩者漆成紅色而解決油漆問題。假

設只有足夠的紅色漆供椅子所用。隨著動作監控,代理人將如期動作並將椅子漆成紅色,然後注意

到漆沒有了且無法漆桌子,此時它會重規劃一個修復——或許是椅子和桌子都漆成綠色。

規劃-監控代理人能夠發現失敗,只要目前的狀態會使得其餘的規劃變得無用時。因此,它不會浪費時間去將

椅子漆成紅色。規劃監控透過檢驗整個剩餘規劃成功的前提——也就是,規劃中每一步的前提,除

了那些被剩餘規劃中另一個步驟獲得的前提之外——來實現這個目的。規劃監控儘早截斷註定失敗

的規劃的執行,而不是繼續執行直到失敗確實出現[4]。規劃監控也允許意外發現——偶然的成功——

偶然的成功。如果有人一起過來,在代理人把椅子漆成紅色的同時,把桌子漆成紅色,那麼最後規

劃前提得到滿足(已經獲得目標),代理人能夠早早回家。

多代理人規劃

迄今,我們已經假設認為只有一個代理人在感測、規劃並採取動作。當環境中有數個代理人,

每個代理人面臨一個多代理人規劃問題,於此在其他代理人的幫助或妨礙之下,它努力達成自己的

目標。

一個具有數個能夠同時運行之作用器的代理人——舉例來說,一個在同一個時間能夠打

字和講話的人——必須做多重作用器規劃,以便在應付作用器之間的正負互動的同時管理每個作用

器。當作用器實際地被拆解成各自獨立的單元——如在一間工廠一群輸送機器人——多重作用器規

劃變成多體規劃。

舉例來說,數個偵察機器人,巡察的範圍很廣泛,可能常常會在無線電能互相聯繫的範圍之

外,應該在通訊可及之時分享它們的調查結果。

當一個單一個實體在做規劃,其實只有一個目標,是所有個體需要分享。當個體是不同代理人

做它們自己的規劃時,它們仍然可以分享相同的目標;舉例來說,兩個由人類網球選手組成的雙打

隊伍分享贏得比賽的目標。

多體和多代理人情況是非常的不同。在一個多體機器人的雙打隊伍,一個單一規劃會指明哪個個體應上球場,

哪個個體應擊球。另一方面,於一個多代理人雙打隊伍中,每個代理人決定該做什麼;並沒有協調的方法,

雙方代理人可決定涵蓋同一部分的場地,而每個代理人可能將球留給其他代理人去打擊。

最後,某些系統是一個集中式和多代理人規劃的混合體。舉例來說,一個宅配公司可以離線地

規劃卡車的路線且每天規劃,但是留下某些面向予司機與飛行員為自主決定,由其個別地根據交通

和天候的情況做出反應。此外,藉由獎勵的付出(薪水和紅利)讓公司及其員工的目標達成一致,至相

當的程度——一個真的是多代理人系統的明確徵兆。

與多代理人規劃有關的議題能夠被粗略分成為兩組。第一組,涵蓋在第11.4.1 節,是與表示有

關的議題,並規劃數個同步動作;這些議題出現於所有的設定,從多作用器到多代理人規劃。第二

組,涵蓋在第11.4.2 節,牽涉到真正多代理人出現之合作、協調和競爭的議題。

規劃數個同步動作

眼下,我們將會以相同方式對待多作用器、多個體、多代理人等等設定,將它們統稱為多行為

者設定(multiactor seetings),將作用器、個體和代理人統稱為行為者(actor)。這一節的目標是針對多

行為者設定研究出如何定義轉移模型,正確的規劃以及有效率的規劃演算法。

n 個行為者每個人玩單人球戲——則我們只需要求解n 個不同的問題。

於CSP 範圍內我們已明確地看過它,其中「近似樹形」的限制

圖可得到有效率的解答方法(見6.5 節),以及於無交集的模式資料庫(3.6.3 節)範圍和附加啟發式規劃

(10.2.3 節)。

圖11.10 網球雙打問題。兩個代理人A 及B 正在一起打球,而且可以是下面4 個位置之一:LeftBaseline,

RightBaseline,LeftNet 及RightNet。僅當打者在合適位置時才能把球打回去。請注意,每個行動包含當作

引數的行為者

非緊密耦合問題的標準方法是假裝該問題是完全地脫鉤,然後安排互動。

對於轉移模型,這意指寫出宛如行為者各自獨立地行動的行動模式。讓我們看看這個方式如何運用在雙人網球問題。

讓我們假設在遊戲中的某一點,它們有聯合目標,將擊給它們的球打回去並確保它們中至少有一個防

守網前。第一個多行為者定義可能看起來像圖11.10。以這個定義,很容易看出下述聯合規劃能發揮

效用:

PLAN 1:

A : [Go(A, RightBaseline), Hit(A, Ball)]

B : [NoOp(B), NoOp(B)]

不過,當規劃中兩名代理人同一時間擊中球時,問題就出現了。於真實的世界,這不會發揮作用,

但是Hit 行動模式說的是球會被成功地回傳。

技術上,困難之處在於前提限制了一個動作能夠被成

功執行的狀態,而不限制可能弄得一團亂的其他動作。我們藉由將行動模式擴增一個新的功能來解

決這個困難:一份明白列出必須或不必須同時執行的同步動作清單。例如,Hit 行動可以被描述如下:

Action(Hit(a, Ball),

CONCURRENT: b ≠ a ⇒ ¬Hit(b, Ball)

PRECOND: Approaching(Ball, loc) ∧ At(a, loc)

EFFECT: Returned(Ball))

換句話說,僅僅如果在同一個時間在另一個代理人沒有其他Hit 動作出現,Hit 動作才有它指明的效

果(於SATPLAN 的方式,這會被一個部份動作排斥公理所處理)。

對於某些動作,僅僅當另一個動作同時發生時所想要的效果才會被達成。舉例來說,需要兩個代理人才能把一個裝滿飲料的冷飲箱帶

到網球場:

Action(Carry(a, cooler, here, there),

CONCURRENT: b ≠ a ∧ Carry(b, cooler, here, there)

PRECOND: At(a, here) ∧ At(cooler, here) ∧ Cooler(cooler)

EFFECT: At(a, there) ∧ At(cooler, there) ∧ ¬At(a, here) ∧ ¬At(cooler, here))

數個代理人的規劃:合作和協調

現在讓我們考慮真的多代理人設定,於此每個代理人製作它自己的規劃。開始前,讓我們假設

目標與知識庫是共享的。你可能會想這縮減為多體情況——每個代理人僅僅計算該聯合解答並執行

解答中它自己的部份。可惜,於「該聯合解答」中的「該」會引人誤解。對於我們的雙打比賽隊伍

來說,存在一個以上的聯合解答:

PLAN2:

A : [Go(A, LeftNet), NoOp(A)]

B : [Go(B, RightBaseline), Hit(B, Ball)]

如果兩個代理人能夠同意於規劃1 或者規劃2,目標將會達成。如果A 選擇規劃2,B 選擇規劃1,

那麼沒有人會把球打回去。相反,如果A 選擇1 並且B 選擇2,那時它們都會去擊球。代理人可能

察覺到這個,但是它們該如何協調以確保它們都同意於該規劃呢?

選擇之一是在展開聯合活動之前採納一項公約

舉例來說,公約「堅守你這一邊的場地」會排除規劃1,導致雙打夥伴選擇規劃2。在路上的司機面臨不彼

此碰撞的問題;這可以採用在大多數國家的公約「靠右行駛」而被(部分的)解出

當公約是廣泛使用時,稱為社會法律

在缺乏可應用的公約時,代理人可以使用通訊來獲得一個可行聯合規劃的常識。例如,一個網

球雙打比賽者可能喊「我的!」或「你的!」以指示一個偏好的聯合規劃。

其中我們觀察到涉及口頭交換的通訊不是必要的。例如,一個比賽者可以簡

單地透過執行規劃的第一部分來對另一個同伴傳達一個偏好聯合規劃。在我們的網球問題中,如果

代理人A 去網前,那麼代理人B 不得不後退到底線來擊球,因為規劃2 是唯一的以A 去網前開始的

聯合規劃。這個協調的方法,有時稱為規劃識別,在一個單個行動(或短的行動序列)足以無歧義地確

定一個聯合規劃時是可行的。注意通訊於競爭性代理人與作用於合作性代理人一樣的適用。

公約也會透過進化的過程出現。舉例來說,吃種子的收穫蟻是從較低等的胡蜂進化過來的群居

動物。螞蟻的殖民地執行非常詳細的聯合規劃而沒有任何集中化的控制——女王的工作是生育,不

做集中化規劃——全賴每隻螞蟻非常有限的計算、通訊和記憶能力(Gordon,2000,2007)。殖民地

有許多的角色,包括內部工作人員、巡邏者和工蜂。每隻螞蟻根據它觀察到的當地條件來選擇一個

角色來執行。舉例來說,蜂遠離蜂巢,搜尋種子,當它們找到一顆,立即將其帶回。

因此,工蜂回巢的速率是今天食物夠用程度的近似值。當回巢率很高,其他螞蟻會放棄它們目前的動作,

併承擔起清道夫的角色。螞蟻似乎有一個重要角色公約——覓食是最重要的——螞蟻會輕易地切換到更重

要的角色,但是不會換到較不重要的。有一些學習機制:一個殖民地在長達幾十年的生活中學會作

出更審慎與更成功的動作,即使各個螞蟻只活大約一年。

最後一個合作性多代理人行為的例子出現在一群鳥的行為。我們能夠獲得鳥群的合理模擬,如

果每隻鳥代理人(有時候稱之為boid)觀察最靠近它的鳥的位置,然後選擇會最大化這三個分量加權

總和的飛行方向與加速度:

1. 凝聚性:越接近鄰鳥的平均位置得正分。

2. 分離性:過於接近任何一隻鄰鳥得負分。

3. 列隊性:越接近鄰鳥的平均飛行方向得正分。

如果所有的boids 執行這個策略,鳥群飛行的突現行為會有如虛似剛體(pseudorigid)的結構,鳥群密

度大約保持一定,不會隨時間沖散,且有時會出現突然俯衝動作。你能夠看看圖11.11(a)中的靜止圖

片並與(b)中的實際鳥群做比較。如同昆蟲,不需要每個代理人都擁有以其他代理人的行動為模型的

聯合規劃。

總結

本章處理了真實世界的規劃和行動的一些複雜因素。要點為:

● 許多行動消耗資源,諸如錢、汽油或原材料。把這些資源看作池中的數值度量是方便的,勝過

試著去推理,例如說,關於世界上每個單個的硬幣和鈔票。行動能夠產生和消耗資源,通常在

嘗試進一步調整之前對滿足資源限制的偏序規劃進行檢驗是便宜和有效的。

● 時間是一種最重要的資源。它能被專門的排程演算法或者與規劃整合在一起的排程安排來處理。

● 分層式任務網路(HTN)規劃可以讓代理人自領域設計者以高層次動作(HLAs)的形式取得建議,

這些高層次的動作能夠透過更低層次動作順序以不同的方式被實作出來。HLA 的效果夠以天使

語意予以定義,讓可證明正確高層次規劃被推導出來,而不用考慮更低層次的實作。HTN 方法

能夠製作出許多的真實世界應用所需的大型規劃。

● 標準規劃演算法假設有完備的和正確的資訊、確定性的和完全可觀察的環境。許多領域違反這

個假設。

● 應變規劃允許代理人在執行期間感覺世界以決定遵循規劃的哪個分支。在某些情況下,無感測

或一致性規劃可以被用來構造一個不需要感知就能工作的規劃。無感測規劃和條件規劃都能透

過信度狀態空間的搜尋進行構造。有效率的表示或是計算信度狀態是個關鍵的問題。

● 一個線上規劃代理人在需要時使用執行監控並結合修復,以便從起因於非確定性的動作、外來

的事件或是錯誤的環境模型等等意想不到的情境中恢復。

● 當環境中有其他合作、競爭或協調的代理人時,多代理人規劃是必要的。聯合規劃能夠被建構

出來,但是如果兩個代理人同意該執行哪一個聯合規劃時,就必須以某種形式的協調予以擴增。

● 本章延伸經典規劃以涵蓋不確定的環境(於此動作的結果不確定),但是這還不是規劃的最後介紹

文字。第17 章描述隨機性環境(於此動作的結果具有機率性)的技術:馬爾可夫決策過程,局部

可觀察的馬爾可夫決策過程,以及賽局理論。於第21 章我們展示強化學習(reinforcement

learninmg)可以讓一個代理人從過去的成功與失敗經驗中學習如何行為。