基于啟發強化學習的大規模ADR任務優化方法

楊家男，侯曉磊，HU Yu Hen，劉勇，潘泉，馮乾

1. 西北工業大學 自動化學院，西安 710129 2.美國威斯康星大學麥迪遜分校 電氣與計算機工程系，麥迪遜 53706

低軌(Low Earth Orbit，LEO)空間碎片是當下世界航天所共同面臨的問題和挑戰[1-2]，隨著空間碎片數量的持續增加，其對未來在軌任務產生的威脅也在不斷增加[3]。根據Kessler現象的預測，如果對空間環境不加以干預，未來低軌空間碎片碰撞會產生更多新的空間碎片，進而引發鏈式連鎖效應，危害在軌運行的任務以及未來的航天發射[4]。即使各國航天器遵守任務末期自動離軌要求(Post-Mission Disposal，PMD)，如果無法每年清除至少5個大型空間碎片，就無法阻止現階段不斷增長的趨勢，并且無法避免失效航天器之間的相互碰撞所引發的連鎖效應[5]。Cosmos 2251衛星與銥星33衛星碰撞即為典型案例，此次空間物體碰撞導致空間碎片數量呈爆炸式增長[6]。

現有低軌空間碎片主動清除方式多樣，分為地基激光離軌、天基捕捉離軌兩類[7-8]。其中，使用專用航天器的天基捕捉方式較為成熟，且擁有多種捕捉形式，如網爪、叉型、繩系、離軌包等。能夠一次任務清除多個碎片的天基碎片清除航天器對完成多碎片主動清除任務(Active multi-Debris Removal，ADR)是非常高效的[9]，而子母星空間碎片清除航天器是一種通用可行的航天器方案。其中，子星為離軌包載荷(Deorbiting Kit，DK)，用以捕獲空間碎片并將其離軌到再入軌道；母星為軌道轉移航天器(Orbital Transfer Vehicle，OTV)，攜帶剩余資源轉移到下一個目標碎片附近[10]，直到用盡其星上資源為止。

由于碎片間的軌道轉移推力消耗(Δv)與變軌時刻、轉移時間相關，所以多碎片主動清除任務規劃可視為時關旅行商問題(Time-Dependent Traveling Salesman Problem，TDTSP)。相比傳統TSP，時間維度的加入使問題變得更加復雜。而且當面對大規模空間碎片時，ADR任務規劃問題的解空間巨大，數據相關性弱，給規劃算法提出巨大挑戰[11-13]。所以，本文面向子母星空間碎片清除平臺建立空間碎片主動清除任務規劃模型，針對大規模空間碎片集合設計快速有效的任務規劃方法。

對于該任務優化問題，多數傳統研究[14]關注于最小化軌道轉移燃料消耗或總任務時間，或者同時最小化這兩種損耗[10,14-18]。現逐漸向最大化任務收益方向發展[13,17]，多采用傳統優化方法求解上述模型，如窮舉法[9,19-20]、剪枝法[10,16,21-22]、蟻群算法[17,23]、遺傳算法[2,11-12,14]以及啟發式算法[13,15,24]。現有研究都是在傳統優化模型基礎上直接使用隨機優化算法或確定性算法，在搜索上往往會陷入局部最優或消耗很多算力，沒有較好的機制來平衡探索與利用。隨著人工智能的飛速發展，逐漸有研究探索了機器學習算法在空間任務中的應用[25-30]。其中強化學習作為一種任務決策框架也是通過尋找最優動作的方式逐漸達到目標[31-32]，能夠在利用歷史信息的同時保持較好的探索能力。空間多碎片清除任務規劃作為一個優化問題，可將任務的每一個清除階段視為一次任務決策，則整個離線任務規劃可描述為多個階段的任務決策，那么強化學習模型就可以被用于提高其決策能力，高效完成離線任務規劃。同時該過程也可以作為未來在軌自主規劃的基礎。

具體而言，強化學習能夠選擇指向最大化積累總收益的動作[33]。這適用于機器人[34]、多智能體系統[35]、博弈[36]以及最優控制[37]等領域。強化學習已經在AlphaGo Zero[38]上顯示出非常優越的性能，并且ADR任務規劃在很多方面都與圍棋博弈規劃過程相似。比如在走棋過程中，規劃程序根據當前狀態、未來可能的選擇還有允許的落子空位，來決定能夠勝利的動作。在ADR任務規劃中，規劃程序根據當前ADR航天器的狀態以及剩下所有待清除空間碎片的狀態，逐步選擇目標碎片及清除時間，并納入到產生的清除序列解中，以期獲得更大收益。強化學習中的基于收益的動作選擇模式令規劃器傾向于能夠獲得更高收益的節點，這種收益導向分步執行的策略與最大收益模型[13]下的ADR任務規劃是相同的。經過合理的設計，融合領域知識，就能有效利用強化學習框架在這類超大解空間中的優勢，高效收斂出更優結果。

綜上所述，本文意在針對ADR任務規劃提出相應的強化學習模型，獲得專用的強化學習框架與算法，并且根據領域實際情況，增加高效啟發因子，提出基于啟發的改進蒙特卡羅樹搜索算法，以求解最大收益模型下的大規模ADR任務規劃問題，并在完整銥星33碎片云上驗證模型與算法有效性。

1 模型建立

在軌道轉移理論中，碎片間轉移消耗是跟隨轉移起始時間、轉移時長的變化而變化的。假設空間碎片軌道在任務期間符合J2攝動軌道動力學模型推演，其位置為關于時間的確定函數。稱這種動態確定性為時間相關特性，則多碎片主動清除任務規劃可以建模為一種時關旅行商問題[10,13]。雖然這種時關函數為確定性函數，但仍然令傳統旅行商問題搜索空間激增。模型中增加了時間變量，求解過程需采用跟隨時間逐步選擇的方式，才能夠在解序列長度不確定的情況下完成規劃問題的求解。

以任務的總收益為目標，建立ADR任務的最大收益模型。鑒于ADR任務規劃僅是針對軌道轉移的離線優化，所以假設ADR航天器采用J2攝動下的漂移軌道脈沖變軌轉移策略[11]，任務時間與轉移消耗為任務約束主要考慮的因素，離軌包數量模型暫不考慮。

1.1 任務描述

假設碎片集合包含Ntotal個低軌空間碎片，以每個空間碎片在集合中的索引表示。任務計劃完成n(≤Ntotal)個碎片的清除，n可變且由最終規劃結果決定。在規劃完成之后，獲得碎片序列為n×1向量d=[d1,d2, …,dn]T，其中di(di∈ 1≤di≤Ntotal)代表第i(1 ≤i≤n)個要清除碎片的索引，清除時間序列的表達形式為n× 1向量t=[t1,t2, …,tn]T，其中T0≤t1

最大收益優化模型的目標是通過規劃解d與t，獲得在任務時間限制與推力限制下積累收益的最大值。模型數學表達為

(1)

式中：G(d)為任務的積累總收益；g(di)>0為di的收益；Cv和CVelocity分別為每段與整個任務的轉移脈沖消耗；Cd和CDuration分別為每段與整個任務的轉移時間間隔；ΔVmax為ADR航天器攜帶的總變軌能力。

1.2 強化學習建模

基本的強化學習模型由狀態空間、動作空間、狀態轉移方程組成。假設一個虛擬的智能體根據當前狀態不斷選擇動作，然后該智能體達到下一個狀態，并且通過環境模型推演獲得收益，最終動作的選擇策略會隨著搜索過程而不斷更新。強化學習模型的目標是最大化所選擇動作序列的積累收益，與ADR最大收益優化模型對應，所以建成后的強化學習模型可以解決本問題。

1.2.1 狀態向量

(2)

該狀態向量理論上有NtotalΔVmaxTleft2N種情況。所有狀態組成的狀態空間一定程度反映了本ADR任務規劃問題的復雜度。例如，如果脈沖消耗與任務時間分別離散為1 m/s與1 d，Ntotal=320，ΔVmax=3 000 m/s，Tmax=365 d，所有的狀態數量為7.5×10104。

1.2.2 動作向量

在ADR任務規劃過程中，動作ai代表虛擬智能體不斷選擇清除的目標和清除的時間，也是解向量的組成片段。如式(3)所示，ai即可表達所有可能的動作，并組成動作集合A。

ai=[di,Δti]T

(3)

式中：

(4)

其中：di為被選擇的目標碎片；Δti=ti-ti-1為碎片間轉移的時間間隔，且離散粒度為1 d。狀態、動作均建模為與清除步驟相關，滿足狀態轉換需求。

在采用漂移軌道轉移策略的ADR任務規劃問題中，ADR航天器會轉移到漂移軌道等待升交點赤經(Right Ascension at Ascending Node，RAAN)與目標軌道重合。由于整個任務時間較長，ADR航天器在碎片附近停留的時間可忽略不計，即假設到達目標碎片的時間與前往下一個碎片的時間相同。為貼近實際并降低搜索難度，假設轉移時間不超過30 d。

1.2.3 狀態轉移方程

給出當前狀態和動作，下一個狀態可以通過式(5)的狀態轉移方程T(si,ai+1)求得。T可視作一種運算,只改變狀態向量的部分元素，未改變的標志位沿用上一狀態。ADR航天器狀態隨著清除步驟逐步改變。通常在強化學習中，狀態轉移方程為概率形式，但是因ADR規劃為離線優化，碎片位置時關可推演，清除離軌過程可靠，所以在本問題中智能體與環境交互的狀態轉移方程為確定的。

(5)

1.2.4 收益函數

由于本問題是離線規劃問題，所以收益函數為狀態-動作對的確定函數，如式(6)所示。在狀態演化過程中，任務的單步收益通過函數R獲得。

ri=R(si,ai+1)

(6)

該收益函數直接與最大收益模型的目標函數式(1)對應，是其單步收益。每當任務優化算法給出一個完整解，優化模型所得到的最終目標是單步收益的總和。這與強化學習狀態值函數式(7)在初始狀態處、折扣因子γ=1時的含義相同。

(7)

式中：π表示選擇動作的概率；a～π(s)為在狀態s下動作a的選擇依照策略π(s)，a=[d, Δt]T，其中d為目標碎片，Δt為轉移時間間隔。

同樣的，在本文強化學習框架中，每個單步收益的期望與優化函數中單個碎片的收益相同，如式(8)所示。所以優化目標中的積累收益是強化學習狀態值函數的一種特例。這也證明強化學習框架是一個契合ADR任務規劃問題的求解方式。

E{R(s,a)|a=[d,Δt]T}=g(d)

(8)

單個碎片的收益因為任務的不同而不同，它通過任務目標中的g(d)反映在強化學習框架的收益函數中。由于意在建立任務規劃的強化學習框架，所以收益函數沒有限定具體內容，而在仿真實驗中假定清除序列總長度即為任務收益，此時所有g(di)=1，最終結果將從清除數量上反映該框架的可行性。其他形式的碎片收益函數可參照文獻[10,13,39]。

1.2.5 搜索樹

完成強化學習框架下的ADR任務規劃狀態、動作及收益函數后，優化搜索過程需要明確搜索樹。如圖1所示，搜索樹的每個節點代表著一個狀態，節點間的轉移過程代表執行特定動作。虛擬的智能體在搜索樹上不斷重復著動作決策與狀態轉移，從初始狀態向下一層探索，逐步完善搜索樹。在每一次的嘗試中，智能體作為規劃器向著收益更大的方向搜索，直至終止狀態，并總結本次搜索過程。終止狀態的判斷條件與優化模型約束集合對應，當狀態向量顯示剩余脈沖小于0或剩余任務時間小于0或剩余待清除碎片數小于0時，達到葉子節點的智能體會重置到初始節點，繼而進行下一次嘗試。

圖1 ADR任務規劃強化學習框架搜索樹Fig.1 Search tree of ADR mission planning under reinforcement learning scheme

隨著搜索過程的進展，基于每次迭代選擇動作的收益，智能體通過更新搜索樹的信息，在每個節點處總結出動作選擇的概率分布，并以此為策略，以期獲得更高的收益[36]。雖然每一步的轉移脈沖消耗損失函數是已知的，但是只有訪問到終止節點，形成了完整的解向量，才能獲得完整的損耗與收益信息。

所以，搜索算法如果能夠快速生成優質的解向量，就可以更快地收斂出最優策略，也就可以用較少的探索時間獲得較優解。同時，也要避免過于利用歷史信息，提高其魯棒性，保持探索可能，使之不易落入局部最優。所以，在窮盡搜索樹之前，搜索過程應該配合適當的評估方法，平衡探索與利用，使得最優解能夠更快地找到。

2 求解算法

現有很多強化學習方法以及相關變體，分為基于值函數的、基于策略梯度的、基于搜索與監督的強化學習方法，如Q學習、深度Q學習(Deep Q-Network，DQN)、異步優勢行動者評論家算法(Asynchronous Advantage Actor-Critic，A3C)和蒙特卡羅樹搜索(Monte Carlo Tree Search，MCTS)方法等[40-41]。其中MCTS在圍棋機器人AlphaGo Zero中得到高效利用。它所使用的算法為上界置信樹(Upper Condence bound Tree，UCT)搜索方法，是在MCTS加入上置信確界(Upper Confidence Bound，UCB)[42]平衡探索與利用，并以深度神經網絡作為評估手段。

針對大規模空間碎片清除數據規模大、搜索空間大、全局最優解無法確定等問題，避免單純通過重啟搜索以及提高算力來解決問題，在ADR任務規劃的強化學習框架上提出一種改進的MCTS方法(ADR-MCTS)，以提高求解ADR任務規劃問題的效率。該算法使用雙層循環結構，內部循環以MCTS為基本結構，使用高效啟發式完成探索，外部循環控制搜索進程以及執行動作決策、完成環境交互步驟。內環為外環提供搜索樹，外環以搜索樹指導決策。

內環仍然使用UCB保持選擇的平衡性，不再使用神經網絡模型作為評估方法，是因為其泛化特點在輸入的大規模碎片數據離散且相關性較小時會誤導搜索。在大規模ADR任務規劃問題中，由于解的元素多，每一次清除步驟間環環相扣，高收益解往往是稀疏的，神經網絡暫時無法較好地評估本問題的期望收益。而且在已知損失函數的條件下，訓練所有數據顯然是不明智的。除此之外，MCTS的roll-out模擬步驟以其優良的魯棒性替換神經網絡的作用，即在非終止狀態的葉子節點處用隨機選擇動作策略模擬至終止狀態，以此獲得可供反饋的評估收益。

即便如此，現有通用智能優化算法在解決該大規模ADR問題時，仍會出現長時間無最優解、指標提升緩慢、陷入指標很差的局部解等現象。為了使搜索更加高效、更加接近全局最優，引入啟發因子擇優擴展策略，在虛擬智能體可獲取本層所有可行的動作時，對比啟發因子，擇優選擇少數可拓展的方案，提高效率。

2.1 基本定義

ADR任務優化模型的解為d與t，他們可以由動作序列(a1,a2,…)表達，其下標為清除步驟。虛擬智能體每一次搜索的過程為(s1,a2,r1;s2,a3,r2;s3,a4,r3;…)，其中假定(s0,a1)為ADR航天器被運抵首個碎片的過程，不計入優化范圍。根據狀態值函數，狀態-動作值函數即為

Qπ(si,ai+1)=Eπ{R(si,ai+1)+γVπ(si+1)}

(9)

式中：Vπ(si+1)為在策略π下的狀態值函數。

2.2 改進的MCTS算法

AlphaGo Zero的基本搜索步驟如圖2[38]所示，包括選擇、擴展與評估、反推以及執行。圖2中Q0為狀態-動作值、V為狀態值、U0為平衡搜索與利用的項、P0為動作選擇概率、p與v為估神經網絡fθ估計的動作選擇概率與狀態值。其優勢在于狀態值估計精確，可較好指導搜索。

圖2 AlphaGo Zero的UCT算法框架圖[38]Fig.2 UCT algorithm structure of AlphaGo Zero[38]

與之不同的是，本研究期望利用MCTS的搜索能力，為避免神經網絡在相關度較小的空間碎片集合中無法發揮優勢，使用roll-out模擬評估非終止葉子節點。并且，針對ADR任務規劃問題高收益解的稀疏性，在選擇步驟中引入適用于漂移軌道轉移策略損失函數的啟發式[13]，以此獲得高效的搜索進程。

2.2.1 節點信息與啟發因子

節點信息的維護是搜索樹連接內環外環的關鍵。節點存儲了從上一步到達自身節點的推演過程，即上一步狀態s、所執行動作a、到達本節點的狀態s′。除此之外還需要定義MCTS需要的決策信息，以及引入的啟發信息。

節點信息有訪問次數N(s,a)、節點歷史積累收益W(s,a)、節點Q值Q(s,a)，新節點在創建之初，所有的參數都初始化為0。一旦某節點被重新訪問，該節點的信息由如式(10)所示的規則更新：

(10)

式中：z為由roll-out步驟更新的收益值，代表沿該路徑時期望獲得的總收益；N′(si,ai+1)、W′(si,ai+1)和Q′(si,ai+1)為更新后的參數值。

啟發信息提供的是人類知識，反映該節點向下搜索達到更優結果的可能性。通過收益消耗比的形式給出。首先給出綜合消耗CR，為考慮所有消耗的加權評估，特別之處在于按照當前對應剩余資源的比例完成組合：

(11)

式中：(si,ai+1)為(di,di+1,ti,ti+1)在節點中的表達；α∈ [0,1]為表達重要程度的加權系數。

結合每一步的收益ri，則啟發因子H如式(12) 所示。搜索樹中的每一個節點都包含以上信息，用以完成內環搜索與外環推演。

(12)

2.2.2 外環結構

外環結構主要包含環境交互外循環以及決策過程，與蟻群算法(ACO)類似[31]。都有智能體在沒有先驗知識的情況下，在地圖中完成路徑尋優。隨著搜索的繼續，知識不斷累積，蟻群算法通過信息素的形式體現，本算法是將該知識存儲在搜索樹中，以狀態值函數的形式表達期望目標函數值。外環結構如算法1所示。

算法1 ADR-MCTS外環結構輸入: 轉移模型式(5)、初始狀態輸出: ADR任務規劃結果1: while 迭代次數不到M do2: 設置虛擬智能體從初始節點出發,對應狀態s03: while 當前節點狀態s非終止 do4: 輸入當前節點進入ADR-MCTS內環作為根節點5: 獲得內環輸出動作a6: 使用狀態轉移方程獲得下一步狀態s'7: end while8: 與歷史解對比保留較優解9: end while

2.2.3 內環搜索算法

ADR-MCTS內環搜索從第一個節點開始，期望找到能夠達到最高收益的子集。在這個過程中輸出動作選擇概率π，并且擴展搜索樹。經過一定數量迭代，搜索樹不斷延伸，作為輸入的根節點的信息也因為子樹的擴展而更加接近真實情況。

流程如圖3所示。智能體所在節點被視作根節點輸入到內環搜索中。整體循環為4步：啟發式選擇、隨機擴展、roll-out模擬、反推更新。啟發式選擇讓搜索樹的擴展方向限定在較少的幾個引向高收益的動作上。在一些次內循環迭代后，ADR-MCTS建立的搜索樹子樹上的節點信息逐步完善，最終形成根節點處的策略，使用模擬退火的方法選擇動作輸出給外環。

圖3 ADR-MCTS內環搜索流程圖Fig.3 Inner loop searching structure of ADR-MCTS

核心步驟描述如下：

U(ai+1)=βQ(si,ai+1)+(1-β)H(si,ai+1)

(13)

式中：β∈ [0,1]為啟發調節參數。

(14)

針對ADR問題最優解的出現比較稀疏，搜索方向落在有限的最有可能出現最優解的方向最為合理。該選擇策略既保留了多個選擇的可能，又避免了在顯而易見的次優節點上浪費過多搜索。

2) 隨機擴展：如果智能體到達節點不滿足搜索樹寬度條件，它將隨機選擇探索方向并擴展節點。由于啟發選擇步驟控制了每一層有資格被擴展的子樹數量為X，搜索樹寬度對搜索量影響不再顯著。假設搜索樹寬度為w，清除了n個碎片使搜索樹下探n層，可能訪問的節點數就從wn變為w+(n-1)Xw，適用于隨機擴展。

3) Roll-out模擬：因為在隨機擴展步驟后搜索樹更深層情況未知，roll-out模擬步驟便不間斷隨機選擇節點直至終止節點。該步驟不會擴展搜索樹，也不會增加節點的訪問次數。它僅僅給出當前已有路線上節點共同的期望總收益z。

4) 反推更新：在獲得當前解的模擬收益z后，將該解路徑上的所有節點都通過式(10)更新。

在足夠多次迭代后，ADR-MCTS內環搜索提供根節點處的動作選擇策略為

(15)

式中：τ為由外環控制的模擬退火溫度，控制決策在搜索之初偏向探索，在溫度下降的搜索末期偏向利用；b為遍歷動作的標識符。所有符合式(16) 的合法動作均可作為決策對象。經過足夠的迭代，最終將收斂的動作序列輸出。

(16)

內環搜索細節如算法2所示。

算法2 ADR-MCTS內環搜索算法輸入:s節點(包含子樹)作為根節點1: while 迭代次數不到預設值T do2: 初始化智能體以根節點作為當前節點開始訪問3: while 當前節點狀態si非終止且滿足搜索樹寬度條件 do4: 啟發地從aXi+1中選擇節點5: end while6: if 當前節點狀態si非終止 then7: 使用隨機函數擴展節點si+18: 使用roll-out模擬直到到達終止狀態,并獲得期望總收益z9: end if10: 通過式(10)從si+1開始向所有母節點更新z11: end while12: 輸出:依π(a|s)所決策的動作

3 仿真實驗

使用銥星33碎片云的子集進行仿真實驗，以測試ADR任務規劃的強化學習框架及改進的MCTS方法。設置碎片清除序列的長度為目標函數，將其作為積累收益在終止節點處獲取并反推更新給路徑上所有節點。

由于窮舉法在本大規模問題中無法完成，進行長時間的搜索也只能獲得8個長度碎片解。因算力有限，窮舉無法繼續深入，也就無法以此作為全局最優點進行算法驗證。所以ADR-MCTS算法將與AlphaGo Zero中的UCT方法以及啟發貪婪算法[13]對比，檢驗框架和算法的有效性。

3.1 測試數據集

圖4 銥星33碎片云概況Fig.4 Overview of Iridium 33 debris cloud

表1 銥星33碎片云實驗數據集(部分)

(17)

ADR航天器假設擁有3 km/s的變軌能力，有1年的任務時間。目標碎片總數320枚，實驗以清除序列總長度為任務收益，即假設碎片的清除收益相等且為1。算法可變參數設置γ=1，α=0.5，β=0.5，啟發選擇子節點個數X=5，外環最大迭代次數M=300，內環迭代最大次數T=3 500，搜索樹寬度條件設置為本層無未訪問的節點。

實驗結果以動作序列形式呈現，碎片集合確定后，動作空間即可構建。動作由其在動作空間A中的索引代表。動作排序方式參照表2所示規律，先排列轉移時間間隔(粒度設置為3 d，最大值不超過30 d)，再排列目標碎片號。

表2 動作空間Table 2 Action space

3.2 結果分析

因為該大規模的優化問題沒有窮舉法作為全局最優解的支撐，所以結果僅通過相關算法結果間的比較來說明本文算法有效性。

3.2.1 實驗1：貪婪啟發算法

對比單純采用啟發因子的貪婪算法[13]結果，都從動作1開始任務搜索，以0.5為啟發因式參數獲得解為[1, 2 472, 2 665, 303, 2 651, 1 243, 203, 1 074, 2 993, 2 093, 354, 3 163, 261, 2 186, 902, 1 662, 864, 776, 492, 2 573, 535, 2 618, 50, 1 960, 1 865, 2 855, 875, 2 223, 196, 724, 397, 2 124, 1 969, 2 756]，該解的長度為34，實際規劃清除33枚碎片，最后一個節點為終止狀態。

嘗試使用不同的啟發參數，獲得該方法下可能的更優解。但是α以0.01為粒度在區間[0.4, 0.5]間調節，都無法獲得更加優秀的解。平均約700 s輸出1次，34長度的解有8次，33長度的解有13次。

3.2.2 實驗2：AlphaGo Zero中的UCT算法

使用該算法時，采用2層的殘差網絡分別模擬狀態值函數以及動作決策概率，經過29 h的搜索，可獲得最優解長度為13，其動作序列為[1, 268, 305, 2 170, 1 917, 130, 379, 2 467, 508, 2 068, 699, 2 500, 1 797]，此時為存儲所有搜索樹節點信息及其他必要資源，128 G字節內存已耗盡，無法繼續搜索。

表3給出的是該最優解路徑上的節點信息及選擇概率，其中W/N代表平均Q值，π(a|si)為對應動作選擇概率。實際在每一層都有能量消耗較小且時間消耗也較小的節點。但是由于沒有啟發，該算法僅通過訪問次數的積累而判斷最優解方向。又由于單純的收益導向，當沒有嘗試到更深的節點時算法收效甚微，仍然需要更多的算力進行試錯。所以原算法解的優化效率很低。

表3 UCT算法最優解上各節點信息Table 3 Nodes information on solution of UCT

圖5給出了UCT算法最終產生的搜索樹形態，圖中的毛刺代表在尋優過程出現的向各方向的探索，那些嘗試均未達到更好的結果。節點總量非常巨大，但是仍然沒有找到優于貪婪啟發算法的結果。從圖5可以看出，每深入一層都有非常多的同層節點不斷被擴展，UCT在碎片間無收益差別時，只能通過不斷嘗試判斷長遠收益。而面對消耗較大的動作時，無法在有限的時間內準確推斷其對長期收益的影響而減少該方向子樹的訪問，對于大規模問題來講效率較低，但是很難收斂到較其他算法優秀的解。

圖5 UCT搜索樹節點深度Fig.5 Depth of nodes on search tree of UCT

3.2.3 實驗3：ADR-MCTS結果

本算法以3.1節中參數運行24 h至第8個循環時，占用內存約20 G，得到當前最優解長度為43。搜索過程經歷長度18的解1次，長度30的解1次，長度32的解3次，長度33的解1次，長度42的解3次，長度43的解1次。最終算法輸出的長度43的最優解節點信息比本文算法ADR-MCTS在與UCT運行相似時間時獲得的解收益更高，占用內存空間更小，與啟發貪婪算法相比雖然運行時間長，但具有更強的擴展能力，能夠獲得貪婪啟發算法無法獲得的結果。

表4為ADR-MCTS算法最優解上各節點信息。值得注意的是該解的第3、6步驟面臨著其他具有競爭性的節點，說明同層其他節點的子樹也有相似程度的拓展。以第3步驟節點舉例，存在兩個有競爭力的節點動作為2 665(π(a|si)=26.06%,W/N=20.259 35)和854(π(a|si)=38.86%,W/N=24.847 95)，其中動作854選擇概率較動作855高，但是其平均Q值相對較低，其子樹無法達到最優解的收益。如果繼續搜索，則虛擬智能體會更加頻繁訪問最優子樹而收斂至最優解，或者發現更加優秀的子樹。改變搜索方向。

表4 ADR-MCTS算法最優解上各節點信息Table 4 Nodes information on optimal solution of ADR-MCTS

續表

實驗搜索樹中所有訪問過的節點深度如圖6所示，可以看出每次搜索都試圖在加深搜索樹深度，正對應任務收益目標。毛刺較少說明搜索方向性較強，且基本能夠探索出附近通往更深層次的子樹。每次程序外循環都可以將搜索樹探至某個方向的局部最優。這也印證了選擇概率相近的同層節點背后的子樹同樣是具有競爭力的。

圖6 ADR-MCTS搜索樹節點深度Fig.6 Depth of nodes on search tree of ADR-MCTS

可見，本文算法ADR-MCTS在與UCT運行相似時間時獲得的解收益更高，占用內存空間更小，與啟發貪婪算法相比雖然運行時間長，但具有更強的擴展能力，能夠獲得貪婪啟發算法無法獲得的結果。

三者對比結果如圖7所示，三者均沿著RAAN漂移方向清除，符合漂移軌道策略，但是UCT的解跨度較大，不如具有啟發因子的方法更加高效，而啟發貪婪算法則不如本文算法擴展得更深，收益更高。由此可得本文改進MCTS算法效率更高，獲得的解更加接近全局最優。

圖7 最優解運行軌跡示意圖Fig.7 Sketch moving trajectory of optimal solution

4 結 論

論述了強化學習框架在大規模多碎片主動清除任務規劃問題中的應用，利用強化學習在任務決策中能有效平衡探索與利用的優勢，建立了最大收益模型下的強化學習框架，提出了一種基于啟發的改進MCTS算法，通過人類認知指導搜索，使探索更加高效。最終在大規模數據集對比實驗中，提出的強化學習框架和算法具有良好可行性與高效性，能夠利用較少時間得出更優的規劃結果，并保持充足的探索能力。

未來將利用該框架，研究其在長期在軌自主航天器的任務決策以及多平臺多目標任務規劃中的可行性。