[發明專利]一種基于改進NSGA-II的無人機路徑規劃方法

有效

• 申請號: 202011362427.8
• 申請日: 2020-11-27
• 公開（公告）號: CN112462803B
• 公開（公告）日: 2022-06-17
• 發明（設計）人: 譚勵;王浩宇;連曉峰
• 申請（專利權）人: 北京工商大學
• 主分類號: G05D1/10
• 分類號: G05D1/10
• 代理公司: 北京萬象新悅知識產權代理有限公司 11360
• 代理人: 黃鳳茹

本發明公布了一種基于改進NSGA?II的無人機路徑規劃方法，NSGA?II為基于非支配排序遺傳算法NSGA的改進算法，通過指數分布自適應動態調整交叉概率和突變概率，利用定向突變策略改進NSGA?II的隨機突變機制，由此減少計算過程中陷入局部最小值陷阱的風險，提升方法的局部搜索能力，從而快速生成三維環境下長度較短且安全無碰撞的無人機飛行路徑。

技術領域

本發明屬于空中無線傳感器網絡技術領域，涉及一種三維環境下的無人機路徑規劃方法，尤其涉及一種基于改進NSGA-II的無人機路徑規劃方法。

背景技術

近年來，無線傳感器網絡憑借著高度的學科融合性和廣闊的應用前景而受到學術界和高新技術領域的廣泛關注。無線傳感器網絡根據其傳感器節點的不同特點可以劃分為各種類型，其中，空中無線傳感器網絡因為其采用兼具感知能力和自主飛行能力的微小型無人機作為傳感器節點，能夠根據實際情況，在多種復雜環境條件下準確的獲取信息而成為計算機領域的研究熱點。

在空中無線傳感器網絡中，由于需要通過飛行穿越各種環境完成信息采集等任務，無人機的路徑規劃方法一直是研究者們的重點關注對象。無人機路徑規劃問題的主要目標在于尋找一條可行路徑，該路徑要求無人機能夠安全無碰撞的到達目的地。由于在實際應用中，需要考慮路徑長度、路徑安全性等多種因素，往往需要考慮多個優化目標以獲得準確的解決方案，因此無人機路徑規劃問題也被歸類為多目標優化問題(Multi-ObjectiveOptimization Problem，MOOP)。

目前解決多目標優化問題的主要方法有兩種。第一是使用加權和函數，將多目標問題轉換為單目標問題。此類方法的缺點是需要提前設置好不同優化目標的權重，并且在優化過程中進行權重的變化。第二種方法是提供一組基于pareto最優解集的解決方案。Pareto解集是指在多目標函數的優化過程，對某目標的提高可能會造成其他目標的降低，這一類改進任何目標函數的同時，必定會削弱其他一個或多個目標函數的解集就是pareto解集，而一組目標函數最優解的集合被稱為pareto最優解集。決策者可以根據應用環境的實際情況，利用pareto最優解集選擇一種最合適的解決方案，而不是只能在一次運行中得到單個解決方案。近年來，眾多研究者針對利用pareto的方法進行了研究，并提出了許多方案，其中，基于元啟發式算法的遺傳算法，尤其是改進算法NSGA-II算法憑借著覆蓋面廣，全局擇優的優勢，成為眾多研究者解決MOOP的首選方法。

NSGA-II是在非支配排序遺傳算法NSGA的基礎上改進后得到的。NSGA是引入了非支配分層思想的遺傳算法，在進行選擇操作之前，利用虛擬適應度和共享半徑技術計算個體之間的支配關系并進行分層，使表現良好的個體有更大概率遺傳至下一代。NSGA-II算法繼承了NSGA算法的非支配分層思想并進一步改進，利用擁擠度算子替代共享半徑，引入了精英策略和快速非支配排序方法，在實際應用中表現出卓越的性能。Mansoor等提出了在離散空間中針對路徑長度和間隙，使用NSGA-II作為框架，利用新的路徑優化算子解決了復雜環境下的路徑規劃問題，但是該方法需要手動改變不同情況下的交叉概率，且容易過早收斂到局部最優；Lucas等考慮了海洋洋流影響，使用NSGA-II算法解決水下滑翔機的四維多目標優化尋路問題，但是其適應度函數只適用于特定海洋結構環境；Ren等針對城市環境下，通過考慮距離和安全性，提出了基于距離的CDNSGA-II方法，但是該方法使用了八叉樹的層次結構數據，在非結構化的環境下，容易陷入局部極小值陷阱。

綜上所述，NSGA-II在解決無人機的路徑規劃這一類MOOP問題上有著運行速度快，收斂性強等優點，但是其自身也存在局限性。由于NSGA-II針對全局最優進行搜索，雖然使用了擁擠度算子，但由于其延續了遺傳算法的基本流程，因此仍然存在局部搜索能力不強，陷入早熟收斂的風險，難以實現有效的無人機路徑規劃。

發明內容