低成本、小型機器人平臺的廣泛使用,催生了機器人群。在機器人群中,大量的小型機器人平臺共同運作,協作完成一項復雜的任務。在所有有用的應用中,機器人群技術也可能對安全關鍵領域構成威脅。在機場、軍事基地、政府設施等安全關鍵區域周圍出現敵對的機器人群,意圖收集關鍵信息,或對該區域進行物理破壞,可能會造成災難性的后果。在這篇論文中,我們考慮了一個多智能體的區域防御游戲,它由以下部分組成: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)缺乏對環境中障礙物的考慮。然后,這兩個框架被結合在一起,為防御者團隊提供一個系統的、協作的防御策略,以應對攻擊者的各種行為。
在這篇論文中,研究了為防御者團隊設計任務分配和運動規劃算法的問題,以應對風險規避者和風險承擔者的蜂群攻擊。本論文的章節大綱和本論文對解決上述問題的具體貢獻列舉如下。
圖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"方法的每個階段適當地改變所需的隊形,引導(放牧)人類人群到障礙物密集環境的指定區域。
**強化學習(Reinforcement learning, RL)是一種機器學習范式,研究智能體如何學習預測和控制自己的經驗流,以最大化長期累積獎勵。**在過去的十年中,深度強化學習(deep reinforcement learning, DeepRL)是一個旨在將強化學習中的序列決策技術與深度學習提供的強大的非線性函數逼近工具相結合的子領域,取得了巨大的成功,例如在古老的棋盤游戲圍棋中擊敗人類冠軍,以及在復雜的戰略游戲如Dota 2和星際爭霸中取得專家級別的表現。它還對現實世界的應用產生了影響。例如機器人控制、平流層氣球導航和控制核聚變等離子體。
//deepblue.lib.umich.edu/handle/2027.42/174601
**本文旨在進一步推進深度學習技術。**具體而言,本文在以下四個方面做出了貢獻:1)在獎勵設計方面,提出了一種新的元學習算法,用于學習有助于策略優化的獎勵函數。該算法提高了策略梯度方法的性能,并優于手工設計的啟發式獎勵函數。在后續研究中,學習到的獎勵函數可以捕獲關于長期探索和開發的知識,并可以泛化到不同的強化學習算法和環境動態的變化。2)在時間信用分配中,本文探索了基于成對權重的方法,這些權重是采取行動的狀態、收到獎勵的狀態和之間經過的時間的函數。本文開發了一種元梯度算法,用于在策略學習期間自適應這些權重。實驗表明,該方法比其他方法取得了更好的性能。3)在狀態表示學習中,本文研究使用隨機深度動作條件預測任務作為輔助任務,以幫助智能體學習更好的狀態表示。實驗表明,隨機的深度動作條件預測通常可以產生比手工設計的輔助任務更好的性能。4)在模型學習和規劃中,提出了一種學習價值等價模型的新方法,這是一類最近表現出強大經驗性能的模型,推廣了現有的方法。實驗結果表明,該方法能夠提高模型預測精度和下游規劃過程的控制性能。
機器學習的現實應用通常具有復雜的目標和安全關鍵約束。當代的機器學習系統擅長于在具有簡單程序指定目標的任務中實現高平均性能,但它們在許多要求更高的現實世界任務中很困難。本文致力于開發可信的機器學習系統,理解人類的價值觀并可靠地優化它們。
機器學習的關鍵觀點是,學習一個算法通常比直接寫下來更容易,然而許多機器學習系統仍然有一個硬編碼的、程序指定的目標。獎勵學習領域將這種見解應用于學習目標本身。由于獎勵函數和目標之間存在多對一的映射,我們首先引入由指定相同目標的獎勵函數組成的等價類的概念。
在論文的第一部分,我們將等價類的概念應用于三種不同的情形。首先,我們研究了獎勵函數的可識別性:哪些獎勵函數集與數據兼容?我們首先對誘導相同數據的獎勵函數的等價類進行分類。通過與上述最優策略等價類進行比較,我們可以確定給定數據源是否提供了足夠的信息來恢復最優策略。
其次,我們解決了兩個獎勵函數等價類是相似還是不同的基本問題。我們在這些等價類上引入了一個距離度量,即等價策略不變比較(EPIC),并表明即使在不同的過渡動態下,低EPIC距離的獎勵也會誘導具有相似回報的策略。最后,我們介紹了獎勵函數等價類的可解釋性方法。該方法從等價類中選擇最容易理解的代表函數,然后將代表函數可視化。
在論文的第二部分,我們研究了模型的對抗魯棒性問題。本文首先介紹了一個物理上現實的威脅模型,包括在多智能體環境中行動的對抗性策略,以創建對防御者具有對抗性的自然觀察。用深度強化學習訓練對手,對抗一個凍結的最先進的防御者,該防御者通過自訓練,以對對手強大。這種攻擊可以可靠地戰勝最先進的模擬機器人RL智能體和超人圍棋程序。
最后,研究了提高智能體魯棒性的方法。對抗性訓練是無效的,而基于群體的訓練作為一種部分防御提供了希望:它不能阻止攻擊,但確實增加了攻擊者的計算負擔。使用顯式規劃也有幫助,因為我們發現具有大量搜索的防御者更難利用。
。
多智能體系統(MAS)已經在不同的環境和框架中得到了利用,因此已經成功地應用于許多應用中,以實現不同的目標。事實證明,與建立一個具有任務可能需要的所有能力的單一智能體相比,多智能體系統更具有成本效益。此外,成本并不是采用MASs的唯一驅動因素,例如,安全是另一個重要方面。在惡劣或極端的環境中部署一組智能體,而不是一個人類團隊,可以減少安全風險。此外,與單一智能體的解決方案相比,MAS提供了更多的靈活性和穩健性。靈活性來自于將資源分成不同的小組,而穩健性則來自于一個智能體的關鍵錯誤不一定會危及任務的成功這一事實。請注意,一個任務可能有許多不同的約束和方面,然而,最微不足道的情況是只有一個智能體和一個任務。
這些類型的任務可以由人類操作員計劃,監督任務,而不需要自動計劃器。另一方面,更復雜的任務,即利用大量的異質智能體和任務,以及約束條件(優先權、同步性等),對人類操作員來說并不是那么簡單的計劃。這些復雜的問題給制定一個可行的計劃帶來了巨大的挑戰,更不用說是最好的計劃了。此外,機器人系統中可用的計算平臺的功率增加,允許利用并行任務執行。更具體地說,它允許在傳感、計算、運動和操縱任務中可能的并行性。這反過來又有一個好處,即允許創建更復雜的機器人任務。然而,它的代價是增加了優化任務分配問題的復雜性。為了規避這些問題,需要一個自動規劃器。這些類型的問題是出了名的難解決,而且可能需要太長時間才能找到一個最佳計劃。因此,優化和產生計劃所需的計算時間之間的平衡變得非常重要。
本論文涉及兩個特殊的多機器人任務分配(MRTA)問題配置的正式定義,用于表示多智能體任務規劃問題。更具體地說,本論文的貢獻可以歸納為三類:
首先,這項工作提出了一個模型,以結構化的方式表示不同的問題配置,也被稱為任務。這個模型被稱為TAMER,它還允許以更系統的方式增加新的維度,與以前提出的MRTA分類法相比,擴大了可以描述的問題的數量。
其次,本論文以混合整數線性問題的形式,定義并提供了兩種不同的問題形式,即擴展的彩色旅行推銷員問題(ECTSP)。這些模型在CPLEX優化工具中對選定的問題實例進行了實施和驗證。此外,還設計了一個解決這些復雜問題的次優方法。提出的解決方案是基于遺傳算法(GA)的方法,并與最先進的(和實踐中的)求解器,即CPLEX獲得的解決方案進行比較。與經典方法相比,使用GA進行規劃的優勢在于它具有更好的可擴展性,使其能夠找到大規模問題的解決方案。盡管這些解決方案在大多數情況下是次優的,但它們比其他精確方法獲得的速度要快得多。另一個優勢體現在 "隨時停止 "選項的形式上。在時間緊迫的操作中,重要的是可以選擇停止規劃過程,并在需要時使用次優的解決方案。
最后,這項工作涉及到MRTA問題的一個維度,這個維度在過去沒有引起很多研究的關注。特別是,包括多任務(MT)機器人在內的問題配置被忽視了。為了克服上述問題,首先,對可能實現任務并行的情況進行了定義。此外,還介紹了物理和虛擬任務之間的區別以及它們在并行任務執行方面的相互關系。我們提出并比較了兩個模型。第一個模型以ILP的形式表達,并在CPLEX優化工具中實現。另一個被定義為限制性規劃(CP)模型并在CP優化工具中實現。兩種求解器都在一系列的問題實例上進行了評估。
人工智能的主要目標之一是構建智能Agent,如計算機游戲中的對手或將包裹送到客戶手中的無人駕駛飛行器。這些智能Agent在各種環境中感知和行動以實現其目標。例如,在電腦游戲的情況下,目標是擊敗玩家。在包裹運送無人機的情況下,目標是將包裹及時送到客戶手中。
Agent感知環境的狀態,并需要決定下一步該做什么。一種可能的方法是強化學習[36],即Agent從與環境的互動中學習。這種方法在一些領域是成功的,在圍棋[60]、《星際爭霸》[66]或Atari游戲[41]中取得了超人的表現。Agent如何在環境中行動的另一種方法是事先創建一個行動計劃。對于一個給定的目標,Agent計算出導致它的行動序列。自動計劃在許多領域都是成功的,如深空1號[4]或火星探測器任務[1]。自動規劃的一個缺點是,當環境意外改變時,Agent通常不能再向目標前進。這種情況要么是隨機發生的,要么是由其他對手Agent的行動引起的。為了明確地推理其他Agent并找到一個穩健的計劃,必須使用博弈論方法[59],如 double-oracle(DO,見圖1)。博弈論算法在實踐中有幾個成功的應用,例如,在物理安全[64]或保護野生動物[19]領域。我們關注的更多案例是戰斗情況,如用無人機保衛核電站,抵御侵略者。
這項工作的主要目標是通過加強幾何推理來推進自動對抗性規劃的算法。盡管規劃域定義語言(PDDL)[39]是一個富有表現力的建模工具,但對行動的結構有一個重要的限制:行動的參數被限制在有限(實際上是明確列舉的)域的值上。這種限制的動機是,它確保了有基礎的行動集合是有限的,而且,忽略持續時間,在一個狀態下的行動選擇的分支因素也是有限的。盡管持續時間參數可以使這種選擇無限大,但很少有規劃者支持這種可能性,而是將自己限制在固定的持續時間上。像吉普車穿越未知寬度的沙漠這樣的問題是無法解決的[32]。
圖 1:對抗性規劃、資源分配、雙預言機算法、幾何導航(從左到右)。
我們提議對PDDL進行擴展,以豐富具有幾何特征的行動。我們實現了能夠將推理提升到空間領域的規劃器,并將其應用于對抗性環境。我們說明這些方法可以解決有趣的問題,并將這項工作應用于任務和運動規劃場景(圖2),以表明我們的工作有很大的潛力,可以重新發明機器人技術中使用任務規劃器的方式。即使沒有對手,幾何學也是有效的,但在DO算法中,規劃器被多次調用以獲得最佳響應,所以作為一個乘數,我們有,如果對手的規劃域是幾何學的,可溶性和擴展性會變得更好。
圖 2:幾何任務-運動規劃:循環、線性近似、檢查運動規劃(從左到右)。
自主機器人系統的團隊有可能對我們的社會產生巨大的積極影響。特別是在水下領域,協作的多智能體自主系統有可能導致效率、安全和數據質量的顯著提高。然而,雖然自主系統在結構化環境中已被廣泛接受,如制造廠和配送設施,但它們在非結構化環境中還沒有被廣泛采用。其主要原因是,自主系統在非結構化環境中的可靠性尚未達到廣泛采用此類平臺的成本和時間效益。自主系統可靠性的一個關鍵因素是導航和定位算法對常見故障情況的魯棒性,如離群測量、糟糕的初始化和不準確的不確定性特征。因此,本論文提出了同步定位和測繪(SLAM)、多Agent地圖合并、軌跡對齊和不確定性表征的方法,試圖解決其中一些故障情況。
首先,我們提出了一種穩健的地圖合并算法,該算法采用兩個姿勢圖和它們之間的一組潛在的環形閉合,并選擇一組可用于持續對齊和合并兩個地圖的這些潛在的環形閉合。我們提出的算法不需要對準的初始估計,可以處理90%以上的離群率。我們利用現有的最大剪裁算法來提高效率,并表明我們的算法優于現有的最先進的方法。
第二,我們提出了一種算法,用于將查詢軌跡定位到參考軌跡上,該算法完全基于描述機器人智能體在其訪問的每個位置周圍環境的低維數據。我們的方法利用凸松弛技術來避免初始化和數據關聯的需要,使得它在高維數據不可用的情況下很有用。我們將我們提出的方法與其他現有的凸優化技術進行了比較,并表明它比其他現有的方法更好地執行了剛體轉換。
第三,我們將平面姿態圖SLAM和地標SLAM問題表述為多項式優化問題,并證明這兩個問題的全局最優解總是可以通過解決半有限程序(SDP)找到。由于SDP是凸的,這使得我們能夠保證在沒有任何初始軌跡估計的情況下找到真正的最大似然估計(MLE)。
第四,我們提出了一個框架,使用特殊歐氏群的李代數對聯合相關姿勢的不確定性進行建模。然后,我們推導出使用該框架時姿勢組成、姿勢反演和相對姿勢操作的一階不確定性傳播公式。我們使用模擬數據和從現有的SLAM數據集中提取的數據進行評估,結果表明我們的方法比常用的方法導致了更一致的不確定性估計。最后,我們發布了擬議方法的C++庫實現。
綜上所述,本論文提出了四種用于多Agent地圖合并、軌跡對齊、全局最優SLAM和姿態不確定性表征的方法,旨在解決現有定位和繪圖方法的一些常見故障情況。此外,我們還證明了我們提出的所有方法在與該領域的其他方法相比較時的性能。
在存在智能對手的情況下,博弈論模型(如安全博弈)已被證明是減輕保護和安全協議中可利用漏洞風險的有效工具,因為它們模擬了對手和防御者之間的戰略互動,并允許防御者在面對這種對手時計劃使用稀缺或有限的資源。然而,標準的安全博弈模型在允許防御者執行的規劃類型方面具有有限的表現力,因為它們只關注一組固定的安全資源的部署和分配。這忽略了兩個非常重要的規劃問題,它們涉及安全系統的戰略設計和部署的資源,以及安全協議的可用性和實施。當這些問題出現在現實世界的系統中時,如果不以一種原則性的方式來處理,安全協議的效用和效率就會出現重大損失。
為了解決這些局限性,在這篇論文中,我為安全博弈的規劃問題引入了一個新的層次結構,將問題分為三個層次的規劃(i)戰略規劃,考慮長期的規劃期限,以及與游戲設計有關的決策,這些決策限制了可能的防御者策略;(ii)戰術規劃,考慮較短的期限,處理資源的部署,以及在戰略層面的限制下選擇防御者策略;(iii)行動規劃,處理在現實世界中的策略實施。
首先,以戰略規劃為重點,我討論了選擇一組資源和時間表類型的設計問題。我引入了一個新的基本問題,即資源團隊和戰術的同步優化(SORT),它模擬了戰略和戰術規劃的耦合問題,在選擇資源類型方面對游戲設計進行了優化,并對它們在現場的實際部署進行了優化。我提供了有效解決SORT問題的算法,該算法使用優化問題的分層放松來計算這些戰略層面的投資決策。我表明,這種更具表現力的模型使防御者能夠進行更精細的決策,從而在效用上獲得巨大的收益。其次,在資源異質性的安全博弈的相關性和艱巨性的激勵下,我還通過提供一個計算異質資源的適應性策略的框架來解決戰術規劃方面的挑戰。最后,我研究了行動規劃的問題,這在安全博弈的文獻中從未被正式研究過。我提出了一個可操作策略的新解決方案概念,它隨機選擇一個最優選擇的純策略子集,其基數由防御者選擇。我展示了計算這種可操作策略的難度,并提供了一種用于計算可操作的最佳均衡的算法。
在所有這些問題中,我的動力來自于現實世界的挑戰,以及開發可在現實世界中使用的解決方法。因此,許多工作都是與Panthera、WWF和其他非政府組織(NGO)合作,幫助保護國家公園和野生動物免受森林砍伐和偷獵,以及與TSA合作,保護我們的機場等關鍵基礎設施免受恐怖襲擊。正因為如此,在處理這三個層次的規劃時,我開發的解決方案不僅是新穎的、學術上有趣的,而且是可部署的、對現實世界有影響的。
移動機器人的自主控制和導航受到了很多關注,因為機器人有能力在復雜的環境中以高精度和高效率完成復雜的任務。與移動機器人有關的經典控制問題涉及到目標導航、目標跟蹤和路徑跟蹤,他們都有一個預先定義行為的目標。因此,控制設計沒有考慮到目標的未來行為。在監視、攔截、追擊-規避問題中,必須考慮到目標的未來行為。這些玩家(控制系統)與對手交戰的問題最好用博弈論來解決,博弈論提供了獲勝的最佳策略。然而,博弈論算法需要大量關于對手的信息來考慮對手的最優策略,從玩家的角度來看,這是最糟糕的情況。這種信息要求往往限制了博弈論在移動機器人上的應用。另外,在文獻中發現的大多數作品提出的離線解決方案只適用于整體系統。這篇博士論文提出了三種不同的解決方案,以每個玩家可獲得的對手信息為基礎,解決非合作性博弈問題。所提出的解決方案在本質上是在線的,并能納入避開障礙物的能力。此外,所設計的控制器首先在模擬中應用于非holonomic移動機器人,然后在類似環境中進行實驗驗證。在工作的第一部分,復雜環境中的點穩定問題是用非線性模型預測控制(NMPC)處理的,其中包括圍繞目標位置的靜態和動態避障。其次,該問題被轉換為涉及具有沖突的移動目標,以形成追逐-逃避博弈。該問題采用非線性模型預測控制來解決,其中比較了兩種穩定方法。NMPC方法的工作原理是,每個玩家只知道對手的當前狀態。然后提出了博弈論的算法來解決同樣的問題。第一種方法需要對手的所有信息,而另一種方法只需要對手的當前位置。這些方法在捕獲時間、計算時間、納入障礙物規避的能力以及對噪聲和干擾的魯棒性方面進行了比較。利用博弈論模型預測控制,提出并解決了一個位于點穩定和追逃問題的交叉點的新問題。這個問題被稱為目標防御的差分博弈(DGTD),它涉及到在到達靜態目標之前攔截一個移動物體。最后,所有提出的控制器都使用兩個移動機器人和實驗室的運動捕捉平臺進行了實驗驗證。
Keywords: 非線性模型預測控制,博弈論,自主系統,非完整移動機器人,避障,實時實驗驗證。
人工智能(AI)正在成為國防工業的一個重要組成部分,最近美國DARPA的AlphaDogfight試驗(ADT)證明了這一點。ADT試圖審查能夠在模擬空對空戰斗中駕駛F-16的人工智能算法可行性。作為ADT的參與者,洛克希德-馬丁公司(LM)的方法將分層結構與最大熵強化學習(RL)相結合,通過獎勵塑造整合專家知識,并支持策略模塊化。該方法在ADT的最后比賽中取得了第二名的好成績(共有8名競爭者),并在比賽中擊敗了美國空軍(USAF)F-16武器教官課程的一名畢業生。
由DARPA組建的空戰進化(ACE)計劃,旨在推進空對空作戰自主性并建立信任。在部署方面,空戰自主性目前僅限于基于規則的系統,如自動駕駛和地形規避。在戰斗機飛行員群體中,視覺范圍內的戰斗(dogfighting)學習包含了許多成為可信賴的機翼伙伴所必需的基本飛行動作(BFM)。為了使自主系統在更復雜的交戰中有效,如壓制敵方防空系統、護航和保護點,首先需要掌握BFMs。出于這個原因,ACE選擇了dogfight作為建立對先進自主系統信任的起點。ACE計劃的頂峰是在全尺寸飛機上進行的實戰飛行演習。
AlphaDogfight Trials(ADT)是作為ACE計劃的前奏而創建的,以減輕風險。在ADT中,有八個團隊被選中,其方法從基于規則的系統到完全端到端的機器學習架構。通過試驗,各小組在高保真F-16飛行動力學模型中進行了1對1的模擬搏斗。這些比賽的對手是各種敵對的agent。DARPA提供了不同行為的agent(如快速平飛,模仿導彈攔截任務),其他競爭團隊的agent,以及一個有經驗的人類戰斗機飛行員。
在本文中,我們將介紹環境、agent設計、討論比賽的結果,并概述我們計劃的未來工作,以進一步發展該技術。我們的方法使用分層強化學習(RL),并利用一系列專門的策略,這些策略是根據當前參與的背景動態選擇的。我們的agent在最后的比賽中取得了第二名的成績,并在比賽中擊敗了美國空軍F-16武器教官課程的畢業生(5W - 0L)。
自20世紀50年代以來,人們一直在研究如何建立能夠自主地進行空戰的算法[1]。一些人用基于規則的方法來處理這個問題,使用專家知識來制定在不同位置背景下使用的反機動動作[2]。其他的探索以各種方式將空對空場景編成一個優化問題,通過計算來解決[2] [3] [4] [5] [6]。
一些研究依賴于博弈論方法,在一套離散的行動上建立效用函數[5] [6],而其他方法則采用各種形式的動態規劃(DP)[3] [4] [7]。在許多這些論文中,為了在合理的時間內達到近似最優的解決方案,在環境和算法的復雜性方面進行了權衡[5] [6] [3] [4] [7] 。一項值得注意的工作是使用遺傳模糊樹來開發一個能夠在AFSIM環境中擊敗美國空軍武器學校畢業生的agent[8]。
最近,深度強化學習(RL)已被應用于這個問題空間[9] [10] [11] [12] [13] [14]。例如,[12]在一個定制的3-D環境中訓練了一個agent,該agent從15個離散的機動動作集合中選擇,并能夠擊敗人類。[9]在AFSIM環境中評估了各種學習算法和場景。一般來說,許多被調查的深度RL方法要么利用低保真/維度模擬環境,要么將行動空間抽象為高水平的行為或戰術[9] [10] [11] [12] [13] [14]。
與其他許多作品相比,ADT仿真環境具有獨特的高保真度。該環境提供了一個具有六個自由度的F-16飛機的飛行動力學模型,并接受對飛行控制系統的直接輸入。該模型在JSBSim中運行,該開源軟件被普遍認為對空氣動力學建模非常精確[15] [16]。在這項工作中,我們概述了一個RL agent的設計,它在這個環境中展示了高度競爭的戰術。
將一個復雜的任務劃分為較小的任務是許多方法的核心,從經典的分而治之算法到行動規劃中生成子目標[36]。在RL中,狀態序列的時間抽象被用來將問題視為半馬爾科夫決策過程(SMDP)[37]。基本上,這個想法是定義宏觀行動(例程),由原始行動組成,允許在不同的抽象層次上對agent進行建模。這種方法被稱為分層RL[38][39],它與人類和動物學習的分層結構相類似[40],并在RL中產生了重要的進展,如選項學習[41]、通用價值函數[42]、選項批評[43]、FeUdal網絡[44]、被稱為HIRO的數據高效分層RL[45]等。使用分層RL的主要優點是轉移學習(在新的任務中使用以前學到的技能和子任務),可擴展性(將大問題分解成小問題,避免高維狀態空間的維度詛咒)和通用性(較小的子任務的組合允許產生新的技能,避免超級專業化)[46]。
我們使用策略選擇器的方法類似于選項學習算法[41],它與[47]提出的方法密切相關,在這些方法中,子策略被分層以執行新任務。在[47]中,子策略是在類似環境中預訓練的基元,但任務不同。我們的策略選擇器(類似于[47]中的主策略)學習如何在一組預先訓練好的專門策略下優化全局獎勵,我們稱之為低級策略。然而,與關注元學習的先前工作[47]不同,我們的主要目標是通過在低級策略之間動態切換,學習以最佳方式對抗不同的對手。此外,考慮到環境和任務的復雜性,我們不在策略選擇器和子策略的訓練之間進行迭代,也就是說,在訓練策略選擇器時,子策略agent的參數不被更新。
為dogfighting場景提供的環境是由約翰霍普金斯大學應用物理實驗室(JHU-APL)開發的OpenAI體育場環境。F-16飛機的物理特性是用JSBSim模擬的,這是一個高保真的開源飛行動力學模型[48]。環境的渲染圖見圖1。
圖1: 仿真環境的渲染圖
每個agent的觀察空間包括關于自己的飛機(燃料負荷、推力、控制面偏轉、健康狀況)、空氣動力學(α和β角)、位置(本地平面坐標、速度和加速度)和姿態(歐拉角、速率和加速度)的信息。agent還獲得其對手的位置(本地平面坐標和速度)和態度(歐拉角和速率)信息以及對手的健康狀況。所有來自環境的狀態信息都是在沒有建模傳感器噪聲的情況下提供的。
每一模擬秒有50次行動輸入。agent的行動是連續的,并映射到F-16的飛行控制系統(副翼、升降舵、方向舵和油門)的輸入。環境給予的獎勵是基于agent相對于對手的位置,其目標是將對手置于其武器交戰區(WEZ)內。
圖2:武器交戰區(WEZ)
WEZ被定義為位于2度孔徑的球形錐體內的點的位置,該錐體從機頭延伸出來,也在500-3000英尺之外(圖2)。盡管agent并沒有真正向其對手射擊,但在本文中,我們將把這種幾何形狀稱為 "槍響"。
我們的agent,PHANG-MAN(MANeuvers的自適應新生成的策略層次),是由兩層策略組成的。在低層,有一個策略陣列,這些策略已經被訓練成在狀態空間的一個特定區域內表現出色。在高層,一個單一的策略會根據當前的參與情況選擇要激活的低層策略。我們的架構如圖4所示。
圖4:PHANG-MAN agent的高層結構