論文1：Autonomous On-Demand Free Flight Operations in Urban Air Mobility using Monte Carlo Tree Search
摘要：
- 為保證VTOL飛機(jī)安全高效地自主飛行，設(shè)計(jì)了一種避免碰撞的計(jì)算指導(dǎo)算法
- 將這個問題建模為馬爾可夫決策過程，使用蒙特卡羅樹搜索的在線算法來解決
- 基于數(shù)值實(shí)驗(yàn)來測試算法性能，結(jié)果表明可以使飛機(jī)快速到達(dá)目的地，避免與其他飛機(jī)的沖突
前人研究：
避碰算法：基于規(guī)則、基于優(yōu)化、遺傳算法、力場技術(shù) → 混合整數(shù)規(guī)劃（對小網(wǎng)絡(luò)較為合適，不適用于隨機(jī)動態(tài)模型）→ 基于馬爾可夫決策過程的方法（這些方法需要離散狀態(tài)空間，可能會丟失信息）→ 在線蒙特卡羅樹搜索算法（不需要對狀態(tài)空間進(jìn)行離散化，但對計(jì)算資源要求較高）
理論基礎(chǔ)：
-
馬爾可夫決策過程 MDP
- 蒙特卡洛樹搜索算法 MCTS
用于解決順序決策問題的在線啟發(fā)式搜索算法，通過在決策空間中隨機(jī)抽取樣本，并根據(jù)結(jié)果構(gòu)建搜索樹來判斷動作的值，以UCB for Tree(UCT)為例，計(jì)算過程如下：
-
選擇selection：選擇UCT值最大的子節(jié)點(diǎn)，UCT值計(jì)算公式中，第一項(xiàng)由總獎勵除以被訪問次數(shù)得到，第二項(xiàng)中C為常數(shù)，n為被探索
- 擴(kuò)展node expansion：創(chuàng)建一個或者多個子節(jié)點(diǎn)
- 仿真simulation：在某一結(jié)點(diǎn)用隨機(jī)策略進(jìn)行游戲，又稱playout或者rollout
-
反向傳播back propagation：使用隨機(jī)搜索的結(jié)果來更新整個結(jié)果樹
問題定義：
問題假設(shè)：
- 所有飛機(jī)只能以固定的速度直線飛行，只有一架飛機(jī)使用MCTS算法飛向目的地
- 所有飛機(jī)在相同高度飛行
- 不考慮入侵飛機(jī)之間的碰撞
狀態(tài)空間：包括所有飛機(jī)(1個本飛機(jī)，n個入侵飛機(jī))各自的位置(x, y)和速度(v_x, v_y)，以及本飛機(jī)的航向角和目的地。所以一共是4×n+4×1+2=4n+7個數(shù)字，狀態(tài)空間則有4n+7個維度
最終狀態(tài)：發(fā)生碰撞（做出行動后，下一秒兩飛機(jī)距離小于r_min）、沖出地圖和達(dá)到目的地
動作空間：{左轉(zhuǎn)2°，右轉(zhuǎn)2°，直行}
獎勵函數(shù)：包含兩個目標(biāo)，第一是短時間內(nèi)將飛機(jī)引導(dǎo)到目的地，第二是避免被控制的飛機(jī)和其他飛機(jī)之間的碰撞。獎勵函數(shù)設(shè)定為飛機(jī)無碰撞達(dá)到終點(diǎn)時R(s)=1，加上折扣系數(shù)小于1，可以保證較快達(dá)到終點(diǎn)
算法訓(xùn)練過程
參數(shù)設(shè)置：
- 仿真次數(shù)n
- 固定深度d（樹結(jié)構(gòu)到達(dá)該深度則停止，計(jì)算最終飛機(jī)位置與目的地的距離來確定結(jié)果好壞）
訓(xùn)練過程
-
隨機(jī)生成根節(jié)點(diǎn)狀態(tài)v_0，s_0，在規(guī)定時間內(nèi)進(jìn)行擴(kuò)展，仿真和反向傳播，最后選擇UCT值最大的子節(jié)點(diǎn)，繼續(xù)循環(huán)
論文2：Multi-Agent Autonomous On-Demand Free Flight Operations in Urban Air Mobility
摘要：
- 提出了一種多協(xié)作飛機(jī)集中計(jì)算指引算法，通過生成所有飛機(jī)的實(shí)時動作來引導(dǎo)所有飛機(jī)到達(dá)各自的目的地，同時避免了飛機(jī)之間潛在的沖突
- 將這個問題建模為馬爾可夫決策過程，使用蒙特卡羅樹搜索的在線算法來管理多架合作飛機(jī)
- 創(chuàng)建了空域模擬器來測試該算法性能，結(jié)果表明該算法可以幫助所有飛機(jī)到達(dá)目的地，而在飛行過程中沖突率僅為0.2%
- 相比于上一篇論文，本文的改進(jìn)之處：上一篇論文只能控制一架飛機(jī)來避免與其他入侵者飛機(jī)的沖突，本文可以通過讓當(dāng)前在空域飛行的多架飛機(jī)相互通信，來幫助它們以合作的方式采取行動
前人研究：
- 集中式/分散式：由一個中央控制器(集中式)解決，還是每架飛機(jī)單獨(dú)(分散式)解決
- 計(jì)劃/反應(yīng)：計(jì)劃式提前生成可行路徑，而反應(yīng)式通常使用在線避碰系統(tǒng)來應(yīng)對危險情況
- 合作/不合作:飛機(jī)之間或飛機(jī)與中央控制器之間是否存在在線通信。
集中式方法：中央控制器在飛行前為所有飛機(jī)單獨(dú)設(shè)計(jì)整體軌跡，可以表述成最優(yōu)控制問題，解決方法包括半定規(guī)劃、非線性規(guī)劃、混合整數(shù)線性規(guī)劃、混合整數(shù)二次規(guī)劃、序列凸規(guī)劃、二階錐規(guī)劃、進(jìn)化技術(shù)等。此外，visibility圖和Voronoi圖等路線圖方法也可以處理飛機(jī)的路徑規(guī)劃問題。當(dāng)狀態(tài)空間變大或高維時，精確解的計(jì)算將變得不切實(shí)際，因此提出了基于樣本的規(guī)劃算法，如概率路線圖、RRT、RRT等。這些集中式方法通常追求全局最優(yōu)解。然而隨著飛機(jī)數(shù)量的增加，這些方法的計(jì)算時間通常呈指數(shù)增長。此外，隨著環(huán)境中的新信息的更新(例如，一架新飛機(jī)進(jìn)入空域)，這些集中規(guī)劃方法通常需要重新運(yùn)行
分散式方法：所有的沖突由每架飛機(jī)單獨(dú)解決，可以是合作的，也可以是非合作的。在agent數(shù)量方面具有更好的擴(kuò)展性，也更健壯，因?yàn)樗鼈儾淮嬖趩吸c(diǎn)故障
在非通信模式下的避碰算法：蒙特卡羅樹搜索→基于幾何的方法 DAIDALUS (Detect and Avoid Alerting Logic for Unmanned Systems)
理論基礎(chǔ)：
Multi-Agent Systems
多智能體系統(tǒng)是一組自主的、相互作用的實(shí)體，它們共享一個共同的環(huán)境，通過傳感器進(jìn)行感知，并在此基礎(chǔ)上與執(zhí)行器進(jìn)行決策和行動
多智能體系統(tǒng)的兩個難點(diǎn)
- 維數(shù)災(zāi)難
- 非平穩(wěn)性（Nonstationarity）：最佳策略會隨著其他飛機(jī)的變化而變化
問題定義：
單機(jī)視角下與上文相同，讓所有的飛機(jī)一個接一個地進(jìn)行決策
當(dāng)一架飛機(jī)選擇了行動后，它將把這個信息廣播給所有其他飛機(jī)，然后飛機(jī)做出決定可以利用這個信息來選擇更好的行動
