開發能夠與其他智能體互動以完成特定任務的自主智能體是人工智能和機器學習的一個核心研究領域。為了實現這一目標，自主智能體研究小組為自主系統控制開發了新的機器學習算法，具體重點是深度強化學習和多智能體強化學習。研究問題包括協調智能體策略和智能體間通信的可擴展學習；從有限的觀察中推理其他智能體的行為、目標和構成；以及基于內在動機、課程學習、因果推理和表征學習的樣本效率學習。本文對該小組正在進行的研究組合進行了廣泛的概述，并討論了未來方向的開放問題。

低成本、小型機器人平臺的廣泛使用，催生了機器人群。在機器人群中，大量的小型機器人平臺共同運作，協作完成一項復雜的任務。在所有有用的應用中，機器人群技術也可能對安全關鍵領域構成威脅。在機場、軍事基地、政府設施等安全關鍵區域周圍出現敵對的機器人群，意圖收集關鍵信息，或對該區域進行物理破壞，可能會造成災難性的后果。在這篇論文中，我們考慮了一個多智能體的區域防御游戲，它由以下部分組成：1）一隊或一群自主的、敵對的機器人平臺（稱為攻擊者），旨在到達一個安全關鍵區域，2）一隊自主的機器人平臺（稱為防御者），旨在阻止攻擊者到達安全關鍵區域，從而防止攻擊者可能造成的任何損害。我們考慮兩種類型的攻擊者：i）風險規避型，即關心自己生存的攻擊者；ii）風險承擔型，即不一定關心自己的生存，試圖到達安全關鍵區域的攻擊者。我們為防御者團隊提供協作任務分配和運動規劃算法，這樣他們就可以防止因安全關鍵區域附近存在規避風險和承擔風險的攻擊者而可能造成的損害。

首先，我們開發了一種叫做 "StringNet Herding"的放牧算法，讓防衛者將規避風險的攻擊者趕到一個預先指定的安全區域，在一個障礙物密集的環境中遠離安全關鍵區域。我們假設規避風險的攻擊者通過遠離防御者和環境中的其他靜態和動態智能體來避免對自己的傷害。在 "StringNet Herding "方法中，"規避風險的攻擊者 "被圍在由防御者形成的封閉的障礙物隊列中，稱為 "StringNet"，這樣，攻擊者的運動被限制在 "StringNet "的內部，攻擊者可以被安全地趕到安全區域。開發了一個開環時間最優和狀態反饋有限時間控制法的組合，為防御者在障礙物密集的環境中成功進行 "StringNet Herding"提供了一個策略。StringNet Herding通過模擬以及使用內部制造的四旋翼飛行器的實驗演示得到了證明。然后，"StringNet Herding "方法被擴展到對抗性蜂群可能分裂成多個小蜂群的情況。對于多群的情況，使用基于密度的空間聚類算法（DBSCAN）來識別空間上呆在一起的攻擊者群（或集群）。然后，提供一個混合整數二次約束規劃（MIQCP）和一個基于幾何學的啟發式方法，將防御者分成較小的團隊，并將這些團隊分配到攻擊者群中去。StringNet Herding方法也被擴展到三維環境。

第二，為防御者開發了一種防御者之間的碰撞感知攔截策略（IDCAIS），以盡可能快地攔截盡可能多的冒險攻擊者，同時確保防御者之間不發生碰撞。特別是，防衛者被分配到使用混合整數二次規劃（MIQP）攔截攻擊者，該規劃：1）在時間最優控制下，最小化防御者捕獲攻擊者的時間總和；2）有助于消除或推遲防御者之間在最優軌跡上可能發生的碰撞。為了防止在最優軌跡上不可避免的碰撞，或由于攻擊者的時間次優行為而產生的碰撞，為每個防御者提供了一個使用指數控制障礙函數（ECBF）的最小增強控制。

最后，我們為防御者提供了一個綜合戰略，以防御安全關鍵區域的風險規避者和冒險攻擊者的各種行為。我們通過在一個協作框架內將針對規避風險的攻擊者的 "StringNet Herding "策略和針對承擔風險的攻擊者的碰撞感知攔截策略IDCAIS結合起來，來制定這一策略。使用混合整數規劃（MIPs）和幾何啟發式方法開發了幾種算法，以分組和分配防御者團隊或單個防御者，來驅趕規避風險的攻擊者群，或攔截冒險的攻擊者，以應對攻擊者的行為，如分裂成更小的群來躲避防御者，或由一些冒險的攻擊者進行高速機動以最大化對保護區域的破壞。我們提供了這些MIPs和幾何啟發式啟發法的計算成本的理論和數值比較。

研究動機

由于最近的技術進步，自主系統（地面、海洋或空中）正變得無處不在。例如，根據美聯邦航空管理局的網站，截至2021年，美利堅合眾國（USA）有超過86萬架無人機注冊[1]。低成本技術已經催生了機器人（或機器人）群[2,3]。在機器人群中，大量的機器人車輛被一起使用，利用彼此間的局部互動，協作完成復雜的任務。這種協作可以提供：1）對系統部件故障的魯棒性，2）適應性，以及3）可擴展性。特別是，地面、海洋或空中機器人群正在被部署以完成：搜索和救援任務[4]，[5]；災害管理[6-8]；農業[9，10]和海洋[11]環境中的監測和測繪；空中包裹投遞[12]；以及合作運輸[13-15]等。機器人群的大量應用清單可以在評論文章[16]中找到。

圖1.1 集群機器人的應用

這類應用需要集群中各個智能體之間的合作，因此需要開發協作性任務分配、運動規劃和控制算法，以實現手頭的應用目標。一些智能體因故障而不合作，或因外部實體而不合作，對上述目標構成了進一步的挑戰。

然而，在機場、政府和軍事設施等安全關鍵基礎設施附近出現成群的對抗性智能體（攻擊者），旨在造成物理破壞或收集關鍵信息，可能導致災難性的后果。例如，媒體上有關于蜂群攻擊軍事基地的新聞[19-21]。在本論文中，我們考慮兩種類型的對抗性智能體（攻擊者）：1）規避風險的（自利的）攻擊者，或2）承擔風險的攻擊者。規避風險的攻擊者是指那些不一定想為手頭的任務冒生命危險的攻擊者。因此，我們假設規避風險的攻擊者更可能試圖避免與其他靜態或動態智能體的碰撞，以避免對自己造成任何損害。我們還假設，規避風險的攻擊者可能更有興趣通過在安全關鍵區域（保護區）周圍閑逛來收集關鍵信息，而不是打算對保護區進行物理破壞。另一方面，承擔風險的攻擊者被認為與他們的任務相比，他們對自己的生存有較低的優先權。這樣的攻擊者可能對物理上破壞保護區感興趣。攻擊者的風險規避程度可能有所不同。此外，攻擊者可能1）相互合作，作為一個蜂群集合在一起，或者2）相互之間不合作。攻擊者的各種可能的行為以及它們的后果，要求仔細設計防御團隊的協作任務分配、運動規劃和控制算法，以保護安全關鍵的基礎設施免受攻擊團隊的影響。

保護安全關鍵區域不受冒險攻擊者影響的一個可能機制是攔截或捕獲這些攻擊者（見圖1.2a的一個例子）。研究表明，防衛者（防衛者）有各種攔截或捕獲策略來抵御冒險攻擊者。例如，在多智能體到達-規避游戲中使用的HamiltonJacobi-Isaacs方法[22, 23]，攔截多個流氓智能體的Voronoibased分區方法[24]，攔截或捕獲攻擊者的最優控制技術[25-32]。然而，在這些方法中，防御者之間的合作并不考慮他們自己的安全，以試圖攔截或捕獲冒險的攻擊者。此外，在城市環境中的低空，由于人類和其他脆弱實體或基礎設施的存在，通過物理攔截或捕獲的手段來對抗規避風險的攻擊者群，如[23-32]中研究的那樣，可能并不可取。在這種情況下，受動物放牧的啟發（見圖1.2b），可以作為一種間接的方式，將攻擊者引導到一些安全區域。這樣，攻擊者將被安全地帶離保護區，從而減少他們對保護區的威脅。一旦被帶到安全區域，這些攻擊者可以被摧毀，或者被重新配置，用于其他一些有用的任務。在文獻中，有一些研究放牧問題的作品。例如，使用n-wavefront算法將鳥群趕出機場[33]，通過利用牧群和牧民之間基于幾何的互動，使用機器人牧民控制非合作的牧群[34]，使用受海豚啟發的包圍技術限制一組智能體[35]，使用勢能函數通過籠子進行牧群[36]。然而，這些方法大多沒有考慮到被自主智能體放牧的智能體對抗性[34-36]，而有些方法沒有考慮到要保護的環境中存在的安全關鍵區域。

圖1.2 針對對手的防御機制

在這篇論文中，我們研究的問題是設計：1）一個協作決策框架，以形成防衛者的分隊，并將其分配給攻擊者；2）防衛者的協作運動規劃算法，以應對攻擊者（對手）的蜂群攻擊，表現出規避風險和承擔風險的行為。防御者的目標是防止對抗性攻擊者的不同行為可能造成的損害。在這篇論文中，我們開發了兩個任務分配和運動規劃框架，以便防御者解決規避風險的攻擊者（在第一個框架中）和承擔風險的攻擊者（在第二個框架中）。這兩個框架解決了現有蜂群防御方法的一些主要缺點，如。1）簡單的運動模型，如單積分器動力學；2）強烈依賴特定的勢場數學形式來模擬攻擊者的排斥運動；3）防御者之間缺乏合作，以避免它們之間的碰撞；4）缺乏對環境中障礙物的考慮。然后，這兩個框架被結合在一起，為防御者團隊提供一個系統的、協作的防御策略，以應對攻擊者的各種行為。

貢獻與提綱

在這篇論文中，研究了為防御者團隊設計任務分配和運動規劃算法的問題，以應對風險規避者和風險承擔者的蜂群攻擊。本論文的章節大綱和本論文對解決上述問題的具體貢獻列舉如下。

• 在第2章中，開發了一種被稱為 "StringNet Herding "的放牧方法，即在規避風險的攻擊者群周圍形成一個被稱為 "StringNet "的封閉防御隊形（見圖1.5），使其運動被限制在StringNet的內部，然后將對抗者群放牧到一個安全區域，以保護障礙物密集環境中的一個保護區。與早期的文獻相比，本章的貢獻在于。i) 一種運動規劃策略，該策略結合了近乎時間最優的運動規劃和狀態反饋，在阻尼雙積分器動力學下運動的防御者的有限時間收斂、有界控制律，以完成對攻擊者的驅趕，同時避開凸形多邊形障礙物，該策略的實驗證明，以及對設計的控制律的收斂時間的明確保證。ii）一組條件，在這些條件下，防御者能夠在攻擊者到達聚集地點之前，聚集在即將到來的攻擊者通往保護區的最短路徑上，然后將所有攻擊者趕到安全區域。本章的結果是基于[99，100]中的工作。

圖1.5：StringNet：攻擊者群周圍形成的封閉式障礙物B的隊形（紅色的圓圈表示攻擊者，深綠色的圓圈表示防御者，連接這些防御者的白色虛線表示防御者之間的障礙物（字符串），藍色的圓圈表示在防御者完全包圍攻擊者之前，防御者形成的開放性障礙物）

• 在第3章中，第2章開發的 "StringNet Herding"方法被擴展到這樣的場景：攻擊者的蜂群可能會分裂成更小的蜂群，以應對防衛者的到來。特別是，使用混合整數規劃（MIP）開發了集中和分散的合作算法，以分組和分配防御者將識別的不同攻擊者群趕到最近的安全區域。還開發了一種受幾何學啟發的啟發式算法，以獲得對MIPs的次優但更快的分配方案。本章的結果是基于[101, 102]的工作。

• 在第4章中，為一組防守者開發了一種防守者之間的碰撞感知攔截策略（IDCAIS），以盡快攔截盡可能多的冒險攻擊者，同時確保防守者之間不發生碰撞。特別是，首先解決了防守者和攻擊者之間的非零和博弈，以獲得一個時間最優的防御策略，所有的防守者和攻擊者對。然后開發一個混合整數二次規劃（MIQP）來尋找碰撞感知的防御者-攻擊者分配（CADAA），以便盡可能多地和盡可能快地捕獲攻擊者，同時防止或推遲防御者之間的碰撞。本章的結果目前正在審查中[103]。

• 在第5章中，第2-3章開發的 "StringNet Herding"策略和第4章開發的碰撞感知攔截策略IDCAIS被結合在一起，以同時處理規避風險和冒險的攻擊者。特別是，使用MIPs和基于幾何學的啟發式方法開發了幾種算法，以分組和分配防御者團隊或單個防御者來驅趕風險規避型攻擊者群，或攔截風險規避型攻擊者，以應對攻擊者分裂成更小的群組來躲避防御者或一些風險規避型攻擊者的高速機動以最大限度地破壞保護區域。本章的結果目前正在審查中[104]。

• 在第6章中，"StringNet Herding"策略被擴展到三維環境中。特別是，為'StringNet Herding'策略的不同階段設計了三種三維防御隊形，對第2章中設計的控制法則進行了適當的修改以適應三維環境，然后提供了玩家初始狀態的條件，在這些條件下，保證防御者在攻擊者到達保護區前聚集在攻擊者最短路徑上的某個位置。本章的結果是基于我們在[105]的合作工作。

最后，在第7章中提供了論文的結論和未來的研究方向。

本論文中開發的任務分配和運動規劃算法是考慮應用于蜂群防御問題的（如前面第1.2節開頭所討論的），然而，這些算法，無論是原樣還是修改后的形式，也適用于其他場景。例如，第6章中開發的 "3D StringNet Herding "算法可用于解決[75]中研究的機器人放牧問題，該問題涉及將一群鳥從機場放牧到離機場足夠遠的安全區域，這樣鳥群就不會再對經過機場的航班造成任何危險。

如果我們不考慮問題中的對抗性攻擊者和保護區，那么這個問題可以被建模為一個協作載荷運輸問題，即一隊機器人圍繞著最初位于已知位置的載荷（如快遞包裹、緊急藥品或救援任務中的人）形成所需的隊形，然后將載荷運送到障礙物密集環境中的所需位置（安全區域）。在第二章介紹的 "StringNet Herding"方法中，只考慮聚集和放牧階段，通過在聚集階段結束時適當地改變所需的隊形，就可以實現這種協作式的負載運輸。

如果我們用動物代替對抗性攻擊者，那么這個問題就可以被建模為使用自主機器人的動物放養問題。第2章中開發的 "StringNet Herding"算法可以用來控制防御者（自主機器人），以便將動物趕到障礙物密集環境中的一個特定區域。

如果我們把敵對的攻擊者換成緊急情況下的人群（如火災、自然災害），那么這個問題可以被建模為使用自主機器人在緊急情況下的人群控制問題，自主機器人的任務是引導人類人群安全地到達一個沒有任何危險的指定區域。第2章中開發的 "StringNet Herding"算法可用于控制自主機器人（防衛者），以便通過在 "StringNet Herding"方法的每個階段適當地改變所需的隊形，引導（放牧）人類人群到障礙物密集環境的指定區域。

在存在智能對手的情況下，博弈論模型（如安全博弈）已被證明是減輕保護和安全協議中可利用漏洞風險的有效工具，因為它們模擬了對手和防御者之間的戰略互動，并允許防御者在面對這種對手時計劃使用稀缺或有限的資源。然而，標準的安全博弈模型在允許防御者執行的規劃類型方面具有有限的表現力，因為它們只關注一組固定的安全資源的部署和分配。這忽略了兩個非常重要的規劃問題，它們涉及安全系統的戰略設計和部署的資源，以及安全協議的可用性和實施。當這些問題出現在現實世界的系統中時，如果不以一種原則性的方式來處理，安全協議的效用和效率就會出現重大損失。

為了解決這些局限性，在這篇論文中，我為安全博弈的規劃問題引入了一個新的層次結構，將問題分為三個層次的規劃（i）戰略規劃，考慮長期的規劃期限，以及與游戲設計有關的決策，這些決策限制了可能的防御者策略；（ii）戰術規劃，考慮較短的期限，處理資源的部署，以及在戰略層面的限制下選擇防御者策略；（iii）行動規劃，處理在現實世界中的策略實施。

首先，以戰略規劃為重點，我討論了選擇一組資源和時間表類型的設計問題。我引入了一個新的基本問題，即資源團隊和戰術的同步優化（SORT），它模擬了戰略和戰術規劃的耦合問題，在選擇資源類型方面對游戲設計進行了優化，并對它們在現場的實際部署進行了優化。我提供了有效解決SORT問題的算法，該算法使用優化問題的分層放松來計算這些戰略層面的投資決策。我表明，這種更具表現力的模型使防御者能夠進行更精細的決策，從而在效用上獲得巨大的收益。其次，在資源異質性的安全博弈的相關性和艱巨性的激勵下，我還通過提供一個計算異質資源的適應性策略的框架來解決戰術規劃方面的挑戰。最后，我研究了行動規劃的問題，這在安全博弈的文獻中從未被正式研究過。我提出了一個可操作策略的新解決方案概念，它隨機選擇一個最優選擇的純策略子集，其基數由防御者選擇。我展示了計算這種可操作策略的難度，并提供了一種用于計算可操作的最佳均衡的算法。

在所有這些問題中，我的動力來自于現實世界的挑戰，以及開發可在現實世界中使用的解決方法。因此，許多工作都是與Panthera、WWF和其他非政府組織（NGO）合作，幫助保護國家公園和野生動物免受森林砍伐和偷獵，以及與TSA合作，保護我們的機場等關鍵基礎設施免受恐怖襲擊。正因為如此，在處理這三個層次的規劃時，我開發的解決方案不僅是新穎的、學術上有趣的，而且是可部署的、對現實世界有影響的。

在許多現實世界的應用中，多主體決策是一個普遍存在的問題，如自動駕駛、多人視頻游戲和機器人團隊運動。多智能體學習的主要挑戰包括其他智能體行為的不確定性，以及由聯合觀察、行動和策略空間的高維性導致的維數災難。由于未知的智能體意圖和意外的、可能的對抗性行為，這些挑戰在對抗性場景中進一步加劇。本文提出了魯棒和可擴展的多智能體學習方法，目標是高效地構建可以在對抗性場景中魯棒運行的自主智能體。通過觀察智能體的行為準確推斷其意圖的能力是魯棒決策的關鍵。在這種情況下，一個挑戰是對手實際行為的高度不確定性，包括潛在的欺騙，這可能與先驗行為模型有很大的不同。捕捉自我主體和對手之間的交互以及對雙方主體可用信息的推理，對于建模這種欺騙行為至關重要。本文采用博弈論對手建模方法解決了這一意圖識別問題，該方法基于一種新的多樣性驅動的信念空間集合訓練技術，用于實現對欺騙的魯棒性**。為了將集成方法擴展到具有多個智能體的場景，本文提出了一種可擴展的多智能體學習技術，該技術通過稀疏注意力機制促進了接近最優的聯合策略學習。該機制的結果是集中的參數更新，這大大提高了采樣效率**。此外，本文還提出了一種新的隱式集成訓練方法，該方法利用多任務學習和深度生成策略分布，以較低的計算和內存成本獲得更好的魯棒性。將魯棒的意圖識別和可擴展的多智能體學習結合起來，可以實現魯棒的、可擴展的離線策略學習。然而，完全自主的智能體還需要能夠不斷地從新的環境和對等智能體中學習(并適應)。因此，本文還提出了一種安全的適應方法，既能適應新的對手，又能在對抗場景中對任何可能的對手剝削保持低可利用性。本文的貢獻有助于構建自主代理，使其能夠在具有不確定性的競爭多智能體場景下做出魯棒的決策，并通過計算效率學習安全地適應以前未見的對等智能體。

學位論文摘要

在這篇論文中，我們研究了博弈論在確定各種基礎設施保護策略的應用。博弈模型是在防御者和對手之間進行的。防御者尋求最小化對基礎設施網絡的損害，而對手的目標則是最大化。本論文分為兩部分。在第一部分，我們考慮資源分配博弈模型，在第二部分，我們研究巡邏和搜索博弈。

在資源分配博弈領域，我們解決了文獻中現有的一些限制。其中一個限制是，這些模型大多假設博弈的參數是確定的，或者遵循一個已知的分布。而在現實中，博弈的某些參數可能是不確定的，沒有已知的分布，或者關于它們的分布信息可能是不可靠的。為此，我們研究了目標估值不確定情況下的一次性安全博弈。我們提出了一個模型，在這個模型中，雙方都使用一種穩健的方法來應對目標估值的不確定性。我們表明這個模型的納什均衡是門檻型的，并開發了封閉式的解決方案來描述均衡點的特征。然后，我們將我們的模型應用于向美國10個城市地區分配安全資金的真實案例。

另一個限制是缺乏解決分層決策的模型。保護基礎設施及其用戶免受蓄意攻擊，需要在組織結構中做出戰略和運行決策。盡管通常是分開分析的，但這些決策是相互影響的。為了解決這個問題，我們開發了一個兩階段的博弈模型。在第一階段，玩家做出投資決策，在第二階段，他們決定保衛/攻擊哪些網站。我們區分了在第二階段出現的兩種類型的博弈。最大損害博弈和滲透/騷擾博弈。我們證明，在預算約束下，這個博弈的解決方案是唯一的。事實上，當第二階段的博弈是滲透/騷擾類型時，投資-防御博弈有一個獨特的閉式解，這是非常直觀的。結果顯示，增加對一個目標地點的防御投資會降低防御和攻擊該目標的概率。然而，攻擊投資的增加會增加防守和攻擊該目標的概率。同樣，防御者（攻擊者）投資效率的提高會導致防御者和攻擊者的投資減少（增加）。我們還將提出的模型應用于一個真實的案例。真實數據的結果表明，攻擊者從失敗的攻擊中得到的懲罰是決定防御者的投資和防御概率的最佳分布的重要因素。防御者的第二階段防御決策是對第一階段投資決策的補充。也就是說，在得到很少或零投資的目標地點中，最重要的一個地點在第二階段以相對高的防御概率被覆蓋。此外，隨著攻擊者預算的增加，防御投資從不太重要的站點轉移到更重要的站點。

我們還研究了資源分配模型中的總體性保護選項。總體保護指的是同時保護多個目標的選項，例如，應急響應、邊境安全和情報。大多數帶有總體保護的防御性資源分配模型都假定只有一個總體保護選項可以保護所有目標。然而，這可能并不現實，例如，應急反應投資可能只覆蓋某個區域。為了解決這個問題，我們開發了一個新的資源分配模型，以適應針對故意攻擊的通用總體保護。該模型還考慮了多種自然災害類型。我們表明，我們提出的模型是一個凸優化問題，因此可以在多項式時間內求解到最佳狀態。此外，整個國家層面的資源分配問題可以被分解成更小的城市層面的子問題，從而產生一個更有效的算法。數字實驗證明了所提方法的性能。

巡邏和搜索博弈通常是在一個圖上進行的，玩家在一個時間范圍內做出決策。在巡邏博弈中，防御者控制一組巡邏者并指揮他們在圖上行走，以盡量減少對手的攻擊損失，而對手則選擇一個目標和攻擊時間。為了成功地摧毀一個目標地點，對手需要一些準備時間而不被巡邏者打斷。大多數巡邏博弈模型都假設站點的價值是相同的，或者說它們不會隨時間變化。然而，這并不是一個現實的假設。特別是在軟目標的情況下，這些值可能對應于一個地點的占用水平，因此，這樣的值可能是不同的，并可能隨時間變化。我們提出了具有隨時間變化的節點值和基于節點的攻擊時間的新模型。我們使用列生成、列和行生成等算法數值地解決這些模型。我們將這些算法應用于美國一個主要城市的城市鐵路網的真實案例。結果顯示了所提出的解決方法的效率。他們還證明了額外的巡邏員的回報率是遞減的。

在搜索博弈中，一個隱藏者將一組物體隱藏在一組潛在的隱藏地點。搜索者控制一組搜索隊，指揮他們在網絡上行走，找到隱藏的物體，使目標函數得到優化。然而，在某些情況下，玩家可能會將藏匿地點相互區分開來，目標是優化加權搜索時間。為了解決這個問題，我們引入了一個新的離散搜索博弈，并考慮到了不同地點的權重。我們表明，在某些條件下，該博弈有一個封閉式的納什均衡。對于一般情況，我們開發了一種基于列和行生成的算法。我們表明搜索者的子問題是NP-hard的，并提出了一個分支和價格算法來解決它。我們還提出了一個用于Hider子問題的多項式時間算法。數值實驗研究了該方法的性能，并揭示了對該博弈特性的洞察力。

第一章 簡介

恐怖襲擊是對國民經濟和生活質量的一個嚴重關切。每年都有成千上萬的人因為這些襲擊而喪生或受傷或被綁架。2015年，全世界共發生11774起恐怖襲擊事件，造成28300多人死亡，35300多人受傷。此外，有超過12,100人被綁架或劫持為人質[22]。恐怖主義的持續威脅帶來的心理影響也是相當大的。這類事件在社會上造成了恐懼、驚慌、焦慮和苦惱。

保護關鍵基礎設施不受恐怖主義侵害是國土安全的首要任務之一[104]。對關鍵基礎設施的物理保護可以防止成功實施高影響力的恐怖襲擊。此外，對針對關鍵基礎設施的恐怖襲擊作出即時反應，可以防止與此類襲擊相關的連帶效應。

這些原因以及在過去幾十年中發生的許多引人注目的恐怖襲擊，突出了此類基礎設施的安全建模和分析是一個主要的研究議程。通過評估與基礎設施內每個站點相關的風險、緩解計劃以及設計保護戰略和響應政策，可以大大減少攻擊的后果。基礎設施安全最近成為研究人員越來越感興趣的主題。人們提出了不同的方法來模擬安全問題中的戰略互動，這些方法包括系統分析[115]、數學建模[51]、概率風險分析[33, 39, 73, 100, 115, 116]，以及對抗性風險分析[123]。然而，由于恐怖分子的攻擊可能是戰略性的，對這種攻擊的博弈論分析會產生更真實的結果。因此，最近的研究集中在開發博弈論模型來捕捉恐怖主義風險，并將結果應用于加強安全措施。其中一個模型ARMOR[112, 113, 114, 118]已被部署在洛杉磯國際機場（LAX）以加強機場的安全。

這項研究的重點是博弈論的應用，為各種基礎設施尋找最佳保護策略，以抵御蓄意攻擊。這項工作可以分為兩部分：資源分配模型，以及巡邏和搜索博弈模型。

為防止蓄意攻擊而進行的資源分配通常是昂貴的，決定如何分配資源以保護關鍵基礎設施是一個困難的問題。許多因素會影響這種分配政策，例如，在實踐中，公平在確定防御分配方面起著重要作用[129]。此外，創造一種平衡以保護不同類型的威脅（例如，生物攻擊與炸彈攻擊，或恐怖主義與非恐怖主義預防活動之間）是另一個因素。其中一些因素已經在靜態安全博弈的文獻中得到了解決。然而，仍然有一些限制。例如，大多數基礎設施安全博弈假設博弈的參數是確定的或遵循一個已知的分布。而在現實中，博弈的一些參數可能是不確定的，沒有已知的分布，或者關于它們的分布信息可能是不可靠的。在這項研究中，我們建立了具有和不具有私人信息的不完全信息基礎設施安全博弈的穩健無分布模型。此外，決策的層次性在文獻中經常被忽略。然而，分配資源以保護關鍵的基礎設施涉及到組織結構中不同層次的決策：戰略和運行決策。這些決策相互影響，需要同時進行研究。在這項研究中，我們開發了兩階段的博弈模型來解決這個問題。此外，大多數現有的帶有總體保護選項的資源分配模型都假定只有一個總體保護選項可以保護所有目標。然而，在現實中，可能有許多總體保護方案，而每個方案可能只覆蓋一個子集的目標。為了解決這個問題，我們開發了一個新的資源分配模型，該模型具有通用的總體保護選項。我們還開發了高效的分解算法來尋找最佳的資源分配。

巡邏和搜索博弈通常是在一個圖形上進行的，玩家在一個時間范圍內做出決定。設計巡邏隊來保護開放的大眾運輸系統和其他軟目標帶來了獨特的挑戰，這些挑戰在巡邏博弈的文獻中還沒有被解決。其中一個挑戰是這些系統內人群規模的動態性質。因為對手的主要目標是造成人員傷亡，所以節點的價值取決于居住在這些節點的人數。這些數字隨著時間的推移而變化，恐怖分子往往根據這些變化來確定他們的攻擊時間[68]。其他挑戰包括處理多個攻擊者，適應人力資源的限制，以及開發有效的方法來設計一般網絡的巡邏。我們通過開發具有動態變化的節點值、基于節點的攻擊時間、多個巡邏員和多個攻擊者的新模型來應對這些挑戰。為了有效地解決這些模型，我們開發了先進的解決算法，如列生成，以及列和行生成。在搜索博弈中，一個隱藏者將一組物體隱藏在一組潛在的隱藏地點。搜索者控制一組搜索隊，指揮他們在網絡上行走，找到隱藏的物體，從而使目標函數得到優化。大多數搜索博弈模型都假定隱藏地點是相同的，玩家的目標是優化搜索時間。然而，在某些情況下，玩家可能會將藏匿地點相互區分開來，目標是優化加權搜索時間。為了解決這個問題，我們引入了一個新的離散搜索博弈，并考慮到了不同地點的權重。

1.1 問題陳述和研究動機

本研究考慮的主要問題是確定針對故意破壞（如恐怖襲擊）的最佳保護策略。因為對手的決策也是有策略的，所以對這些問題的博弈論分析會產生更現實的結果。本研究中考慮的博弈模型是在防御者（她）和對手（他）之間進行的。防御者想要最小化對基礎設施網絡的損害，而對手則想要最大化。這些模型可以分為兩類：資源分配博弈，以及巡邏和搜索博弈。在資源分配模型中，有一個N個目標的集合。每個目標i都有一個Ci的值。防守方決定防守哪個目標，而對抗方決定攻擊哪個目標。如果雙方都選擇相同的目標i，那么以δi的概率，攻擊將被檢測并挫敗。這個概率被稱為檢測概率。以下矩陣的(i, j)部分顯示了如果防御者選擇目標i，而對手選擇目標j的預期損害。注意，這個矩陣對應于對手的報酬矩陣，對手試圖使預期損害最大化。

我們的目標是在各種條件下，如博弈參數的不確定性和私人信息的存在，以閉合形式描述納什均衡（NE）的特征。

我們在這篇論文中討論的另一個問題是決策的層次性。保護基礎設施及其用戶不受破壞，需要在一個組織的層次結構中做出戰略和運行決策（見圖1.1）。戰略決策是具有長期影響的長期決策。例如，對目標站點進行 "加固"[17]以減少攻擊的成功概率的投資決策被歸類為戰略決策。這包括對新技術的投資，以加強網站的安全性。另一方面，運行決策是與日常運作有關的短期決策，如巡邏、分配第一反應者和安排車輛檢查站。請注意，"戰略 "這個詞也可以用來描述參與者。在這種情況下，"戰略玩家 "指的是一個理性的玩家，其目標是最大化回報。因此，在本論文中，"戰略決策 "是指具有長期影響的長期決策，"戰略參與者 "是指以報酬最大化為目標的理性參與者。大多數研究只關注純粹的戰略決策[63, 107]或純粹的運行決策[16, 35, 36, 38]。然而，這些決策是相互影響的。例如，在某一區域安裝閉路電視攝像機可能會使該區域的巡邏變得不必要。或者將金屬探測器和安檢系統分配給目標地點，可能會影響到這些目標中巡邏隊的最佳調度。此外，投資一項新技術以加強某個目標地點的安全，可能會降低其目標的吸引力，影響保衛該目標的最佳概率。因此，在同一個模型中考慮戰略和行動決策會產生一個更全面的分析。

圖1.1: 戰略決策與運行決策

我們研究了在考慮到人為和自然災害的資源分配模型中總體保護方案的影響。總體保護方案是指可以同時保護多個目標的替代方案。例如，對邊境安全和情報工作的投資有望保護多個目標免受恐怖主義的威脅。這一領域現有文獻的局限性在于，大多數現有的模型只考慮了保護所有目標的單一總體性保護方案。然而，這可能不是對現實的準確表述。例如，對邊境安全的投資可以分為不同的入境點，每一個入境點預計都會使離該特定入境點較近的地區受益。為此，一個新的資源分配模型，容納多個保護目標子集的總體保護措施，將導致一個更現實的分析。

本研究中調查的巡邏博弈G是一個由防御者和對手在連接圖Q = (N , E)上進行的零和博弈，節點集為N，邊集為E，時間跨度為T。防御者控制著一組安全人員（巡邏者）S，并指示他們在圖上行走，以盡量減少來自對手的攻擊的損害。而敵方控制著一組攻擊者A，并為每個攻擊者選擇一個節點和一個攻擊時間。為了成功地摧毀一個目標站點，攻擊者需要在目標上有一定數量的時間單位，不被任何巡邏者打斷。巡邏博弈文獻中的大多數論文都假設對手選擇一個目標進行攻擊，目標值在一段時間內是固定的，有些甚至假設所有目標是不可區分的，即它們都有相同的價值。然而，在許多現實情況下，情況并非如此。例如，在一個交通設施中，每個地點的人數、占用水平可以被認為是該地點的價值。此外，占用水平可能隨時間變化，預計在高峰期，占用水平會比正常時間高。因此，一個具有隨時間變化的節點價值、特定節點的攻擊時間、多個巡邏者和多個攻擊者的巡邏博弈模型將導致與現實更加一致的結果。

本研究中考慮的搜索博弈是在搜索者和隱藏者之間進行的。搜索者控制一組S個搜索隊，隱藏者控制一組H個要隱藏的對象。博弈是在一個完整的圖Q = (N , E)上進行的，其中N = {0, 1, 2, . ，N}是圖中節點的集合，E = {(i, j) : i, j∈N, i 6 = j}是邊的集合。文獻中的大多數搜索博弈模型都假設藏身之處是相同的，玩家的目標是優化搜索時間。然而，在某些情況下，玩家可能會將藏身之處相互區分開來，其目標是優化加權搜索時間。例如，在某些攻擊中（生物或化學），傷亡率取決于人口密度、環境條件等因素。因此，不同的地點可能有不同的傷亡率，而整體的損失將與暴露時間和傷亡率成正比。另一個例子是通過通信渠道檢測竊聽者的問題[37]。不同的信道可能有不同的傳輸能力，對網絡的破壞率將與檢測時間和信道的容量成正比。此外，藏匿地點可能分散在大片區域，搜索可能涉及多個搜索小組。為此，一個新的搜索博弈，容納了不同地點的不同權重，將導致一個更現實的分析。

1.2 研究貢獻

在這項研究中，提出了新的博弈論模型，以解決資源分配博弈、巡邏和搜索博弈領域中的一些現有差距。在資源分配博弈領域，主要貢獻是：擴展現有模型以處理分層決策；引入廣義的總體保護方案；用穩健的方法解決參數的不確定性；開發適合于更有效算法的新模型。在巡邏和搜索博弈領域，我們的主要貢獻是：納入了與時間相關的節點值，以及多個巡邏者和多個攻擊點；并引入新的和更有效的算法來解決博弈論模型。

在接下來的章節中，我們將介紹我們的主要貢獻，如下所述。

1.我們開發了一種穩健的方法來應對安全博弈中的參數不確定性，并在第二章提供了閉合形式的NE策略。

2.為了解決防范蓄意攻擊的決策的層次性問題，在第三章中，我們引入了一個兩階段的投資-防御博弈模型，并推導出某些條件下的閉合形式的NE策略。這個模型抓住了戰略投資決策和運行攻擊/防御決策的綜合效應。

3.在第四章中，我們提出了一個新的資源分配模型，用于保護資產免受人為和自然災害的影響，并具有廣義的總體保護。這個模型被證明導致了一個可分解的凸優化問題，因此可以被有效解決。

4.在第五章和第六章中，我們介紹了新的巡邏博弈模型，該模型具有與時間相關的節點值，基于節點的攻擊時間，多個巡邏者和多個攻擊點；并開發了高效的解決方法，基于列生成，以及列和行生成來解決現實的大小問題。

5.我們在第七章中介紹了一個新的搜索博弈模型，該模型具有不同的節點權重、多個搜索隊、多個隱藏對象和分散的隱藏地點；并在第七章中介紹了基于列和行生成的高效求解方法，以解決現實的大小模型。

6.我們在第八章中提出了本研究的結論并討論了未來的研究思路

自從十年前發現針對機器學習模型的對抗性攻擊以來，對抗性機器學習的研究已經迅速演變為一場永恒的戰爭，捍衛者尋求提高ML模型對對抗性攻擊的魯棒性，而對手則尋求開發能夠削弱或擊敗這些防御的更好攻擊。然而，這個領域幾乎沒有得到ML從業者的支持，他們既不關心這些攻擊對他們在現實世界中的系統的影響，也不愿意犧牲他們模型的準確性來追求對這些攻擊的魯棒性。

在本文中，我們旨在設計和實現Ares，這是一個對抗性ML的評估框架，允許研究人員在一個現實的兵棋推演環境中探索攻擊和防衛。Ares將攻擊者和防御者之間的沖突設定為強化學習環境中目標相反的兩個Agent。這允許引入系統級的評估指標，如失敗的時間和評估復雜的策略，如移動目標防御。我們提供了我們初步探索的結果，涉及一個白盒攻擊者對一個經過對抗性訓練的防御者。

I. 前言

人工智能系統的大規模采用，促使人們重新審視人工智能算法的可靠性、隱私性和安全性。在安全性方面，人們很早就發現，基于圖像的人工智能算法很容易受到一類對抗性規避攻擊[1]，[2]。在這種攻擊中，對手會引入人眼無法察覺的少量噪聲，以便在推理過程中可靠地誘發錯誤分類。自其發現以來，大量的研究提出了許多經驗性的防御策略，如改造模型的輸入[3]，修改神經網絡結構[4]，以及在另一個訓練數據集上訓練網絡[5]。盡管有大量的工作，無論是開發新的對抗性攻擊還是提出新的防御措施，包括強大的物理世界攻擊[6]，對抗性威脅模型對ML從業者來說仍然沒有動力。在一項小型的行業調查中，Kumar等人[7]發現，雖然大多數被調查的組織都知道對抗性樣本，但他們說 "對抗性ML是未來的"，并且缺乏研究和緩解這種攻擊的工具。

我們認為，有兩個關鍵問題阻礙了人們接受對抗性規避攻擊作為一種威脅：（1）大多數先前的工作所使用的非激勵性威脅模型；（2）缺乏評估復雜的對抗性攻擊者和防御者互動的工具。遵循Kerckhoffs原則，對抗性攻擊和防御的研究主要采用白盒威脅模型，即對網絡和防御參數的完全了解。在這種視角下，許多提議的防御措施被證明是無效的，因為擁有完美知識的攻擊者可以適應防御[8]。然而，這樣一個強大的威脅模型只能由具有內部訪問AI算法和訓練數據的攻擊者復制。在真實的部署場景中，一個組織主要關注的是其人工智能系統對外部攻擊者的安全性。

盡管沒有認識到對抗性ML是一種威脅，但對抗性攻擊庫已經興起，使ML從業者能夠研究目前最先進的攻擊和防御算法。一些例子包括多倫多大學的CleverHans[9]，麻省理工學院的魯棒性包[10]，圖賓根大學的Foolbox[11]，以及IBM的對抗性魯棒性工具箱（ART）[12]。每個庫都定義了一個統一的框架，從業者可以通過它來評估使用自己的人工智能系統的攻擊或防御的有效性。不幸的是，這種評估在本質上是有限的，因為評估的威脅模型受到攻擊算法的限制。此外，攻擊者和防御者都被認為是靜態的。他們不會根據對方的行動來修改自己的行為，因此，報告的有效性是誤導性的，不能轉化為現實世界中的有意義的有效性概念。

在本文中，我們描述了一個新的評估框架--Ares，它將對抗性攻擊場景表現為攻擊者和防御者之間復雜的、動態的互動。我們將攻擊者和防御者之間的沖突作為強化學習（RL）環境中的兩個獨立Agent來探索，其目標是對立的，為對抗性ML評估創造了一個更豐富、更真實的環境。通過利用這種RL環境，我們能夠將攻擊者或防御者的策略（RL策略）調整為靜態的、隨機的、甚至是可學習的。Ares還允許調查白盒和黑盒威脅模型，從先前評估的局限性中汲取靈感。

作為其首次亮相，我們使用Ares重新審查了白盒場景下的集合/移動目標防御（MTD）框架的安全性，并強調了這種設置的脆弱性。使用自然訓練和對抗性訓練模型的不同組合，Ares評估發現，一般來說，攻擊者總是獲勝，對抗性訓練只能稍微延遲攻擊者的成功。正如之前的工作所討論的，攻擊者的成功主要是由于對抗性例子的可轉移性[2]。我們通過Ares的視角對這一現象進行了更深入的調查，發現網絡之間共享的損失梯度，無論訓練方法或模型架構如何，都是罪魁禍首。然后，我們討論了如何根據這一發現改進MTD，以及我們下一步如何通過Ares在黑盒威脅模型中評估MTD和其他先前的工作。

在本文中，我們做出了以下貢獻:

• 我們開發了Ares，一個基于RL的對抗性ML的評估框架，允許研究人員在系統層面上探索攻擊/防御策略。

• 利用Ares，我們重新審查了白盒威脅模型下的集合/移動目標防御策略，并表明這種失敗的根本原因是由于網絡之間的共享損失梯度。

Ares框架在// github.com/Ethos-lab/ares上公開提供，我們將繼續開發更多的功能和改進。

為了實踐知識表示，知識表示語言具有形式化的語義是最重要的。然而，由于有許多不同的語言都具有形式化的特點，因此有一個統一的框架來捕捉語言和邏輯的語義是很有價值的。一個這樣的框架就是理由論，在這個框架中，語義是通過使用解釋來定義的，在我們的術語中稱為理由。直觀地說，一個理由是一個解釋某些事實的真值的圖。然而這引入了一個潛在的問題：一個事實的理由狀態和它的否定可能是不一致的。因此，為了使辯解語義得到良好的定義，這些狀態應該是相反的。這樣的語義學被稱為是一致的。

在本論文的第一部分，我們證明了理由論的主要語義實際上是一致的。此外，我們還證明了對理由的有用結果，比如將理由組合在一起的能力。理由論語義學的另一個問題是，有不同類別的理由，這可能導致不同的語義學。我們表明，這兩個看似不相關的問題實際上是有深刻聯系的。

之后，我們在理由論和博弈論之間建立了一種聯系，這使得理由可以被看作是雙人博弈中的策略。這種聯系通過在系統是有限的情況下為語義提供一個一般條件，為正當性理由論中的這兩個問題提供了一個解決方案。

理由論并不是非單調邏輯語義學的唯一統一框架。另一個著名的框架是近似定點理論（approximation fixpoint theory），它在本質上更加代數化。我們在證明理由論和近似定點理論之間建立了一種聯系。近似定點理論的終極語義的概念可以轉移到理由語義的領域。這使得證明語義學可以比以前捕獲更多的語義。

作為本論文的最后一個主題，我們研究了理由的嵌套，它可以用來定義模塊化語義。在以前的嵌套定義中，由于使用了壓縮操作，大量的信息被丟失。我們提供了一個替代的、更普遍的定義，沒有這個缺點。這允許基于理由的更直觀的模塊化語義。我們證明，這與樹狀理由的壓縮是等價的，在特殊情況下，對于圖狀理由也是如此。我們也研究了這兩種方法的一致性，作為額外的獎勵，我們解決了樹狀證明的一致性問題。

綜上所述，本論文收集了證明理由論中的一些進展，并以實例說明了這些進展。

第1章 緒論

1.1 背景

本論文位于人工智能（AI）領域，特別是知識表示和推理（KRR）子領域。KRR的主要關注點是定義表示知識的語言和邏輯，并構思用這些知識進行推理的工具和技術。當然，這是一個過于簡化的觀點，但它使我們能夠看到更大的畫面。要想擁有一個完美的推理器，首先應該捕捉問題領域的知識，然后釋放出手頭的推理能力。我們應該將其與人工智能其他部分的函數擬合方法進行對比，比如深度學習。這些方法雖然對其他問題（如語音識別）非常有用，但由于其近似的性質，并不總是能夠推理出100%的邏輯正確。Darwiche（2018）將人工智能的這種二分法定義為基于模型與基于函數的人工智能。基于模型的人工智能與基于函數的技術相比有一個明顯的優勢：內部機制通常也被捕獲，與基于函數的技術相比，它們的行為就像黑盒。因此，相對于更不透明的基于函數的方法，這些方法更傾向于可解釋的系統。此外，基于函數的人工智能通常是為一個特定的目標量身定做的。基于模型的人工智能的一個主要部分是知識表示和推理（KRR）。代表性的知識可以用來解決多個問題；因此它是面向多目標的。這個想法是知識庫范式的核心（Cat等人，2014；Denecker和Vennekens，2008）。因此，這些技術可以更好地處理新的場景，例如在因果推理中。由于人工智能的法規和政策，例如解釋權，基于模型的方法的更高程度的可解釋性顯得越來越重要。擁抱解釋將是實踐當代知識表示和推理（KRR）的一個完美起點。

在KRR中，許多語言和邏輯被發明用于不同的目的，從語義網本體語言（Antoniou和van Harmelen，2009；Baader等人，2005）到機器人學（Paulius和Sun，2019），立法和法律（Jones，1990）。通常情況下，這些邏輯都是基于相同的原則，但在工作中略有不同，或者是從不同的角度來解決。為了看清大局，最重要的是我們能在不同的語言和邏輯之間建立關系：它們是具有相同基本原則的不同方言，還是有本質的不同。研究這些關系的一種技術是定義語言之間的轉換。特別是，我們可以找到一種語言對另一種語言的嵌入。然而，由于現有的知識表示語言數量龐大，這是不現實的。另一個更可行的方法是設想統一一大批邏輯學的語義的框架。

幸運的是，證明理論既解決了可解釋性的問題，也解決了統一性的問題。理由論的語義（意義）是基于理由的概念，它是一個解釋某事為何成立的圖3。例如，理由（在這一點上完全理解這些圖片并不重要）作為一種解釋，為什么一個蘋果是美味的（當然你對美味的定義可以不同）。

理由語義學的工作方式是給每個理由打分，說明它是否好。通過改變我們對理由的評級方式，我們可以改變同一領域的語義。為了改變領域，辯解理論使用一套規則作為構建解釋的基礎。因此，不難看出，辯解理論作為一個統一的框架。再加上理由（解釋）是語義的主要構成部分，理由理論是KRR的一個很好的研究對象。

1.2 KRR中的理由說明

本論文所詳述的理由理論起源于Denecker（1993）的博士論文，并由Denecker, Brewka, and Strass（2015）進一步正式化。理由--盡管并不總是以Denecker（1993）；Denecker等人（2015）所描述的確切形式出現--以不同的方式出現在KRR的不同領域中。理由論起源于邏輯編程，其中理由的概念已經存在了相當長的時間。根據Fandinno和Schulz（2019）的說法，理由的概念起源于Shapiro（1983）；Sterling和Lalee（1986）關于調試的工作。在這項工作的基礎上，Lloyd（1987）為聲明式錯誤診斷器引入了不正確的規則和未發現的原子的概念。這些概念說明了什么時候一個結構不是給定邏輯程序的模型。第二年，Sterling和Yal?inalp（1989）用元解釋器解釋了Prolog專家系統。1990年，Fages(1990)用理由來定義邏輯程序的穩定語義，在這種情況下，理由是原子的集合。很多論證方法都使用了支持集/值的概念，這個概念是由Pereira等人（1992，1993）首次提出的。這大約是在Denecker和Schreye（1993）介紹早期版本的論證理論的同一時間。2000年，Roychoudhury等人（2000）通過為邏輯程序提供理由來證明基于表的證明。

Fandinno和Schulz（2019）列舉了除了證明理論之外的幾種突出的答案集編程（ASP）的證明方法。

• 離線論證（Pontelli和Son，2006)

• 基于標簽的假設論證的答案集（LABAS）論證（Schulz和Toni，2016）。

• 因果證明（Cabalar和Fandinno，2016；Cabalar等人，2014)

• Why-not出處（Damásio等人，2013年）

• 基于規則的論證（Béatrix等人，2016)

前三種方法與論證理論相似，因為論證也是字詞或規則之間的依賴圖。

離線證明（Pontelli and Son, 2006）是一種圖結構，描述了一個原子相對于給定答案集的真值。因為離線論證只使用原子作為節點，所以節點必須用 "+"或"-"來表示它是真的還是假的。同樣地，邊也必須用 "+"和"-"來表示正或負的關系。負數字的真實性被認為是真實的，不做進一步解釋。

LABAS論證（Schulz和Toni，2016）與離線論證非常相似，但它們對中間的規則應用進行了抽象。所以他們只指出有問題的字詞和推導中使用的規則中出現的事實。此外，否定字詞的真實性不是假設的，而是根據基礎原子的真值來進一步解釋。

因果圖論證（Cabalar and Fandinno, 2016, 2017; Cabalar et al., 2014），與離線和LABAS論證相反，被用來對因果知識進行形式化和推理，這是它的主要焦點。它們也可以用來解釋為什么一個字詞包含在一個答案集中。此外，還定義了一個用于組合論證的代數。

Why-not provenance（Damásio等人，2013）是基于數據庫文獻的。這里的論證不是基于圖的，而是用來解釋原子的真值。

基于規則的證明（Béatrix等人，2016）是在基于規則的答案集計算的背景下定義的（Lefèvre等人，2017）：搜索算法猜測的是規則的應用或不應用，而不是原子的真值。ASP-求解器ASPeRiX使用這些理由進行反跳。

對不同論證方法之間錯綜復雜的差異感興趣的讀者應該看看Fandinno和Schulz（2019）的出色工作。除了這些方法，還有一些應用也使用了論證方法。Mari?n（2009）；Mari?n等人（2005，2007，2008）關于歸納定義的工作將理由作為歸納定義的推理技術的語義基礎。理由被用來進行非因果的局部搜索（J?rvisalo等人，2008）。類似于理由的數據結構也被用于答案集求解器的實現中（它們構成了無根據集算法中所謂的源-指針方法的基礎（Gebser等人，2009））。此外，理由被證明是分析懶人接地背景下沖突的關鍵（Bogaerts和Weinzierl，2018）。最近，Lapauw等人（2020）使用理由來改進奇偶性博弈求解器。

1.3 研究目的和動機

從廣義上講，我們的目標是推進論證理由論。特別是，在本文中，我們廣泛地研究了兩個帶有相關研究問題的屬性。

第一個屬性是關于正當化語義的合理性。理由論的一個好處是它提供了很大的自由度，可以通過分支評價的方式來創建新的語義。這些評價為解釋圖中的路徑賦值，從而決定一個理由是否被認為是好的。在論證理由論中，一個事實和它的否定之間沒有真正的區別。這意味著一個事實和它的否定都可以有好的理由，這在正常情況下被認為是一種矛盾。例如，如果你有一個很好的理由說明x成立，又有一個很好的理由說明x不成立，那么我們就得到一個矛盾。如果這種矛盾沒有發生，我們就說它的正當性語義是一致的。

理由論最初是為了捕捉歸納定義的語義而開發的。歸納定義在數學中極為重要，因為它們被用來生成數學對象，如子集生成的子群、博勒集、自然數、遞歸公式、邏輯中的真值關系等（Buchholz等人，1981）。引用甘迪（1974年，第265頁）的話來說

數學邏輯當然滲透著歸納性的定義

例如，我們可以在給定父關系的情況下歸納定義祖先關系，規則如下：

• 如果一個人p是q的父母，他就是q的祖先。

• 如果有一個人r，使p是r的父母，并且r是q的祖先，那么p就是q的祖先。

直觀地講，這應該是很清楚的意思。然而，一組歸納規則的形式語義并不立即清楚。一般來說，有兩種方法可以為歸納定義提供形式語義。第一種方法是構造性的，從下往上建立關系：你從空的關系開始，反復地應用歸納定義中的規則，直到關系停止增加。第二種方法是將關系定義為滿足歸納規則的最小的關系。如果歸納規則中不出現否定，這兩種方法都能提供相同的結果，然而當涉及到否定時，這種方法就失效了。正當化理論遵循構造方法，但將其擴展到更廣泛的構造類別。在這個意義上，我們可以把正當化看作是對一個事實為什么屬于一個集合/關系的構造。回到祖先關系，下面的理由代表了為什么Alice是Bob的祖先的構造過程。

上面的論證描述了Alice是Bob的祖先的過程：需要哪些歸納規則。

仍然存在的問題是，像Bob不是Alice的祖先這樣的事實的理由意味著什么。這樣的理由提供了一個證據，說明為什么鮑勃是Alice的祖先是不可構造的。可建構性的概念當然是經典的：某物不可能既在一個關系中又不在一個關系中。這意味著，研究理由語義的一致性是最重要的。

第二個屬性更關心我們的解釋可以是什么形狀。用更專業的術語來說，理由是有向圖。然而，我們允許兩種形式，一種是總是做出相同的 "選擇"，另一種是可以做出多種選擇。讓我們看一下一個聯鎖齒輪的例子。

在這種情況下，我們有以下兩個理由：

在左邊，你看到一個循環推理，第一個齒輪的順時針轉動被第二個齒輪的逆時針轉動所證明，反之亦然。而在右邊，第一個齒輪的順時針轉動首先被第二個齒輪的逆時針轉動所證明，而后又被第三個齒輪的順時針轉動所證明。由于寫下正確的圖形類型，我們會得到一個樹狀結構（或根狀結構，取決于方向），我們說正確的類型是樹狀證明。為了對比樹狀證明，第一種類型被稱為類圖證明。最初，Denecker和Schreye（1993）發明了樹狀證明，但后來Denecker等人（2015）發明了圖狀證明。

現在我們有足夠的信息來說明本論文的第二個中心問題：這兩種類型的理由在什么時候是等價的；也就是說，當且僅當一個事實有一個好的樹狀理由時，它就有一個好的樹狀的理由。這一屬性被稱為圖式重現性，第二章中解釋了它被這樣稱呼的原因。

研究這兩個屬性是本論文的中心目標。特別是，我們的目標是找到對分支評價的限制，使這些屬性成立。此外，這些屬性是未來新的證明語義的準則。如果新的證明語義被設計出來，它應該滿足這兩個屬性才有實際用途，因為第一個屬性確保語義不矛盾，而第二個屬性允許將樹狀證明壓縮成圖狀證明。這在實際的計算機應用中有著重要的影響，因為大多數時候，樹狀的理由是一個無限的結構，因此不適合放在內存中。因此，如果有一個同樣好的類似圖的理由，那么就可以用它來代替。例如，理由被用于奇偶性博弈求解器中，見Lapauw等人（2020）的工作。

有點出乎意料的是，這些屬性在本質上是相互關聯的：如果類圖證明是一致的，那么圖的可重復性就成立，樹狀證明也是一致的。

除了這兩個屬性之外，我們還有兩個額外的研究方向。如前所述，論證理論旨在成為一個統一的框架。另一個起源于邏輯編程的框架是AFT。AFT的基礎在于Tarksi的fixpoint理論（Tarski, 1955）；因此AFT的基本對象是運算符和它們的fixpoint。由于邏輯論證和AFT捕獲之間存在重疊，這就引出了這兩種形式主義之間的關系問題。

我們最后的研究方向是關于知識表示的模塊化。為了擁有高效的知識表征，最重要的是，如果增加了新的邏輯構造，語義學就不需要完全被改造來獲得它的工作。也就是說，知識表示應該是可組合的。Denecker等人（2015）提供了一種通過嵌套理由框架來組合不同理由語義的方法。然而，為了賦予嵌套以意義，它被壓縮到常規的辯解語義。這樣做，在理由中失去了很多信息，其效果是，理由沒有一個合適的解釋特征。因此，這就提出了一個問題：我們是否可以通過提供另一種方法來改善嵌套，而不丟失理由中的信息。

1.4 論文的結構

在下一章中，我們建立了論證理由論的前期工作，其中包括論證理由論的詳細定義以及四個主要分支的評價。我們為接下來的章節做了一些基礎工作，如關于粘貼在一起的理由的結果，以及正式定義我們的兩個研究問題和目標。本章最后表明，理由論可以捕捉到邏輯編程語義和抽象的論證框架。

在第三章中，我們深入研究了四個主要理由語義的一致性，并證明了這些主要理由語義的模型之間的一些關系。

第四章進一步研究了一致性問題，但是從另一個角度進行的，即把理由論嵌入到博弈論中。這種嵌入有效地表明，理由可以被看作是一些雙人游戲中的策略。利用博弈論的結果，我們為分支評價找到了兩個額外的屬性，這意味著它在有限環境下的一致性。

之前，我們談到理由論是一個統一的框架。另一個試圖捕捉類似語義的統一框架是AFT。在第五章中，我們將探討這兩個統一框架之間的關系。作為額外的收獲，我們將終極語義（AFT中的一個概念）轉移到了證明理論中；進一步擴大了證明理論能夠捕獲的語義的數量。

我們還沒有討論的理由論的一個好處是它的模塊化。理由論通過嵌套實現了這一點。直觀地說，這可以被看作是理由中的理由。這將在第六章進一步探討。作為一個出乎意料的結果，我們發現了一個意味著滿足圖再現性的屬性。此外，我們還解決了樹狀證明的一致性問題。在本章的最后，我們介紹了一些使用嵌套證明系統的應用。

第七章也是最后一章提供了一個結論和這一研究方向的可能。

大多數章節都是獨立的主題，除了第二章，因為它為后面的章節打下了基礎。每一章都有一個結論，闡述了該研究方向的未來。

自主機器人團隊組成中的異質性什么時候是有益的，什么時候是有害的？我們在一個最小可行的模型中研究并回答了這個問題，該模型研究了異質速度在周界防御問題中的作用，其中防御者共享一個總的速度分配預案。我們考慮了兩種不同的問題背景，并制定了基于動態規劃和局部互動規則的策略。我們對這兩種方法進行了理論分析，并使用模擬方法對我們的結果進行了廣泛的驗證。有趣的是，我們的結果表明，異質團隊的生存能力取決于防御者可用的信息量。此外，我們的結果表明了一個普遍性屬性：在廣泛的問題參數范圍內，防守方的最佳速度比率幾乎保持不變。

關鍵詞：周界防御，異質多機器人團隊，動態規劃

引言

機器人系統的一項日益重要的任務是保衛一個地區免受外部因素的影響，這些因素構成了不同程度的威脅。這方面的例子包括保衛機場，防止無人機入侵[6]，保衛野生動物棲息地，防止偷獵者侵入[1]，撲滅和防止人類或自然活動造成的破壞性野火蔓延[8]，以及軍事應用[13]。

一般來說，周界防御問題的解決方案是為一組限制在某一區域周界的智能體尋找策略，這些智能體受托保衛該區域不受試圖突破該區域周界的入侵者侵害[16]。

與同質化的機器人團隊相比，具有不同能力的機器人團隊（異質化團隊）有其獨特的優勢和挑戰。為不同的智能體配備不同的能力可以形成協同效應，在這種情況下，異質系統勝過由相同智能體組成的同質系統。因此，在過去十年中，機器人界對定義、探索和量化不同機器人應用中的異質性產生了極大的興趣[19,14,11,7,12,10]。

本文研究了多機器人團隊中異質性對周界防御問題的影響。我們提出了兩種最優策略，在不同的假設條件下有效。第一個策略是基于動態規劃（DP）[2]。當防御者能夠預測來襲攻擊的位置時，它是最優的，但受到維度詛咒的影響，因此相關計算成本相對較高。第二種策略是基于局部互動規則的，當防御者沒有關于來襲攻擊的信息時是最佳的。這種策略可以以在線方式高效計算，但沒有提供對攻擊位置的任何先驗知識。

我們證明了兩種策略的最優性并分析了它們的時間復雜性。這些算法在模擬中得到了廣泛的驗證。我們的數值實驗是二維的，但大多數理論結果對任何維度都有效。這包括無人機應用中的三維周界，以及作為任意維度狀態空間中約束集產生的更高維度的周界。

我們的結果表明，異質性在防守方能夠獲得有關來襲攻擊信息的情況下是有益的，而在防守方沒有攻擊信息的情況下是有害的。此外，我們顯示了一個普遍性的屬性，即在兩個防御者的情況下，防御者的最佳速度比率幾乎保持不變。

相關工作：周界防御問題是追擊-規避問題的一個變體，在文獻中已經被廣泛地研究。Issacs的開創性工作描述了微分博弈的方法，以得出一個追求者一個規避者博弈的均衡策略[4]。不同研究人員為解決涉及多個追擊者和規避者的追擊規避博弈各種變體做了大量的工作[20,21,3]。這些論文包含了從追擊者方面、從規避者方面或兩者來看待追擊-逃避博弈的工作。維度的詛咒對解決涉及多個追擊者和規避者的問題構成了相當大的挑戰。本文提出的周界防御問題是Isaacs[4]首次提出的目標守衛問題的一個變體。在目標守衛問題的設定中，一個智能體的任務是對抗一個敵對智能體以守衛一個目標區域。對周界防御問題的研究還處于初級階段。Shishika和Kumar的綜述文章[16]描述了最近關于多機器人周界防御問題的工作[15,5,18,17]。與這些工作中考慮的問題不同，我們考慮的是一類周界防御問題，其中攻擊者的數量遠遠大于防御者的數量。

本文的其余部分組織如下。第2節包含了我們的符號和問題陳述。第3節和第4節分別詳細介紹了我們在非限定和單位時間范圍內的理論結果。第5節討論了模擬結果。

圖1：三個防守者面對三個攻擊者，每個防守者的單位時間可達集顯示。請注意，第三個維度是時間；如果攻擊代表一個物理物體，它是從圓圈外的某個地方接近的，但我們只關心它將在哪里和什么時候擊中周界。在這個例子中，防守者不允許離開周界，所以可達集的大小隨著速度的增加而線性增加（直到它覆蓋整個周界）。

強化學習定義了僅通過行動和觀察來學習做出好的決策的代理所面臨的問題。為了成為有效的問題解決器，這些代理必須能有效地探索廣闊的世界，從延遲的反饋中分配信用，并歸納出新的經驗，同時要利用有限的數據、計算資源和感知帶寬。抽象對所有這些努力都是必要的。通過抽象，代理可以形成其環境的簡潔模型，以支持一個理性的、自適應的決策者所需要的許多實踐。在這篇論文中，我提出了強化學習中的抽象理論。首先，我提出了執行抽象過程的函數的三個要求:它們應該1)保持近似最優行為的表示，2) 有效地被學習和構造，3) 更低的規劃或學習時間。然后，我提出了一套新的算法和分析，闡明了代理如何根據這些需求學習抽象。總的來說，這些結果提供了一條通向發現和使用抽象的部分路徑，將有效強化學習的復雜性降到最低。

強化學習問題如下。RL代理通過以下兩個離散步驟的無限重復與環境進行交互:

1. 代理收到觀察和獎勵。
2. 代理從這種交互中學習并執行一個動作。 這個過程如圖1.2所示。在這種互動過程中，agent的目標是做出決策，使其獲得的長期報酬最大化。

論文余下組織如下： 第1部分。在第2章中，我提供了關于RL(2.1節)以及狀態抽象(2.2節)和動作抽象(2.3節)的必要背景知識。

第2部分。下一部分將專注于狀態抽象。我提出了新的算法和三個緊密相連的分析集，每一個目標是發現滿足引入的需求的狀態抽象。在第3章中，我開發了一個形式化的框架來推理狀態抽象，以保持近似最優的行為。這個框架由定理3.1總結，它強調了值保持狀態抽象的四個充分條件。然后，在第4章中，我將這一分析擴展到終身RL設置，在終身RL設置中，代理必須不斷地與不同的任務交互并解決不同的任務。本章的主要觀點是介紹了用于終身學習設置的PAC狀態抽象，以及澄清如何有效計算它們的結果。定理4.4說明了保證這些抽象保持良好行為的意義，定理4.5說明了有多少以前已解決的任務足以計算PAC狀態抽象。我著重介紹了模擬實驗的結果，這些結果說明了所介紹的狀態抽象類型在加速學習和計劃方面的效用。最后，第五章介紹了信息論工具對狀態抽象的作用。我提出了狀態抽象和率失真理論[283,43]和信息瓶頸方法[318]之間的緊密聯系，并利用這種聯系設計新的算法，以高效地構建狀態抽象，優雅地在壓縮和良好行為表示之間進行權衡。我以各種方式擴展了這個算法框架，說明了它發現狀態抽象的能力，這些狀態抽象提供了良好行為的樣本高效學習。

第3部分。然后我轉向行動抽象。在第6章中，我展示了Jinnai等人的分析[144]，研究了尋找盡可能快地做出計劃的抽象動作的問題——主要結果表明，這個問題通常是NP困難的(在適當簡化的假設下)，甚至在多項式時間內很難近似。然后，在第7章中，我解決了在規劃中伴隨高層次行為構建預測模型的問題。這樣的模型使代理能夠估計在給定狀態下執行行為的結果。在本章中，我將介紹并分析一個用于這些高級行為的新模型，并證明在溫和的假設下，這個簡單的替代仍然是有用的。我提供的經驗證據表明，新的預測模型可以作為其更復雜的對等物的適當替代者。最后，在第8章中，我探討了抽象行動改善探索過程的潛力。我描述了Jinnai等人開發的一種算法[145]，該算法基于構建可以輕松到達環境所有部分的抽象行動的概念，并證明該算法可以加速對基準任務的探索。

第4部分。最后，我轉向狀態動作抽象的聯合過程。在第9章中，我介紹了一個將狀態和動作抽象結合在一起的簡單機制。使用這個方案，然后我證明了哪些狀態和動作抽象的組合可以在任何有限的MDP中保持良好的行為策略的表示，定理9.1總結了這一點。接下來，我將研究這些聯合抽象的反復應用，作為構建分層抽象的機制。在對層次結構和底層狀態動作抽象的溫和假設下，我證明了這些層次結構也可以保持全局近最優行為策略的表示，如定理9.3所述。然后，我將在第十章中總結我的思考和今后的方向。

總的來說，這些結果闡明了強化學習的抽象理論。圖1.4展示了本文的可視化概述。