航跡規劃已經成為無人駕駛飛行器（UAVs）的一個熱點問題，特別是在復雜的室內環境中，現有無人機室內航跡規劃解決方案因其計算復雜度高、收斂速度慢和飛行航跡差而受到很大限制。此外，由于室內障礙物密度更高，無人機在室內航跡規劃過程中經常會陷入局部死區，導致算法死鎖，無法獲得飛行航跡。

近期，我司首席科學家、北京大學工學院程承旗教授課題組基于地球立體剖分網格GeoSOT-3D理論，建立起一套網格優化的無人機室內航跡規劃算法集。該研究成果以“Grid-optimized UAV Indoor Path Planning Algorithms in a Complex Environment”（https://doi.org/10.1016/j.jag.2022.102857）為題于2022年6月9日在中科院1區TOP期刊International Journal of Applied Earth Observation and Geoinformation在線發表。

       該研究提出了一套針對室內復雜環境、通過網格優化的無人機航跡規劃算法框架（圖1），主要包含三個網格優化的核心算法：

          圖1. 網格優化的無人機室內路徑規劃算法框架圖

網格優化的室內空域建模（GO-IAM）算法。基于GeoSOT-3D地球立體剖分網格模型，建立起一個增強的室內多層級三維網格空域模型，大大降低空域計算復雜性。

網格優化的A*航跡規劃（GO-APP）算法。以常規室內場景為重點，GO-APP通過采用改進的A*網格算法，增加無人機的飛行約束與代價限制，可快速有效完成建筑物內的航跡規劃（圖2）。

圖2. 多旋翼無人機路徑規劃結果。(a) 障礙物特殊放置下的路徑規劃。(b) 障礙物隨機放置下的路徑規劃

網格優化的局部回溯航跡規劃（GO-LBPP）算法。為了解決“死區問題”，GO-LBPP采用局部回溯策略，并改變無人機的視界，在多障礙物的室內場景中實現了有效精確的無人機航跡規劃（圖3）。

圖3. 局部回溯算法成功跳出室內環境中的局部死區。

(a) 使用普通路徑規劃算法造成的死區。(b) 使用GO-LBPP算法的航跡規劃結果

在多個無人機室內航跡規劃算法的對比實驗中，該研究將GO-APP算法與常用的模擬退火、Q-learning、人工勢場、遺傳算法、粒子群、蟻群等局部/全局規劃算法的規劃結果進行對比顯示，GO-APP算法的航跡規劃時間和規劃航跡路線長度最短（表1），規劃路徑更優、可飛行性更高（圖3）。而在多障礙物室內環境中采用GO-LBPP算法，則可以順利解決室內局部死區問題，避免規劃航跡的死鎖，這是現有其他算法均無法實現的。未來這項工作將繼續深入，將算法集與多機協同策略相結合，有望在無人集群協同規劃中取得更多進展。

圖4. 二維室內環境中不同無人機路徑規劃算法的規劃路徑圖比較

表1. 二維室內環境中不同無人機路徑規劃算法的結果比較

北京大學前沿交叉學科研究院博士生韓炳是論文第一作者，北京大學工學院曲騰騰助理研究員是論文通訊作者，北京大學工學院程承旗教授是論文合作作者。上述研究得到了國家重點研發計劃、國防基礎加強重點項目及國家自然科學基金等資助。