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

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

       該研究提出了一套針對室內(nèi)復(fù)雜環(huán)境、通過網(wǎng)格優(yōu)化的無人機(jī)航跡規(guī)劃算法框架（圖1），主要包含三個網(wǎng)格優(yōu)化的核心算法：

          圖1. 網(wǎng)格優(yōu)化的無人機(jī)室內(nèi)路徑規(guī)劃算法框架圖

網(wǎng)格優(yōu)化的室內(nèi)空域建模（GO-IAM）算法。基于GeoSOT-3D地球立體剖分網(wǎng)格模型，建立起一個增強(qiáng)的室內(nèi)多層級三維網(wǎng)格空域模型，大大降低空域計算復(fù)雜性。

網(wǎng)格優(yōu)化的A*航跡規(guī)劃（GO-APP）算法。以常規(guī)室內(nèi)場景為重點(diǎn)，GO-APP通過采用改進(jìn)的A*網(wǎng)格算法，增加無人機(jī)的飛行約束與代價限制，可快速有效完成建筑物內(nèi)的航跡規(guī)劃（圖2）。

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

網(wǎng)格優(yōu)化的局部回溯航跡規(guī)劃（GO-LBPP）算法。為了解決“死區(qū)問題”，GO-LBPP采用局部回溯策略，并改變無人機(jī)的視界，在多障礙物的室內(nèi)場景中實(shí)現(xiàn)了有效精確的無人機(jī)航跡規(guī)劃（圖3）。

圖3. 局部回溯算法成功跳出室內(nèi)環(huán)境中的局部死區(qū)。

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

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

圖4. 二維室內(nèi)環(huán)境中不同無人機(jī)路徑規(guī)劃算法的規(guī)劃路徑圖比較

表1. 二維室內(nèi)環(huán)境中不同無人機(jī)路徑規(guī)劃算法的結(jié)果比較

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