基于元胞自動機的無人機航路規劃算法研究

劉震

【摘 要】本文利用元胞自動機算法模型，對無人機航路規劃進行仿真。實現了單目標和多目標，以及二維環境和三維環境下的航路規劃仿真。仿真結果表明，元胞自動機航路規劃算法實時性高，計算量少，可在短時間內規劃出一條安全可行的航路。

【關鍵詞】元胞自動機;航路規劃;無人機

中圖分類號： V249 文獻標識碼： A 文章編號： 2095-2457（2019）15-0016-002

DOI：10.19694/j.cnki.issn2095-2457.2019.15.007

Research on Unmanned Aerial Vehicle Route Planning Based on Cellular Automata

LIU Zhen

（No.20 Research Institute of CETC，Xi'an Shaanxi 710068，China）

【Abstract】This paper simulates UAV route planning based on cellular automata.The simulation achieves the route planning of single target and multi-target in 2D and 3D environments.The simulation results demonstrate that route planning based on cellular automata has high real-time performance and less computation.The algorithm can plan a safe and feasible route in a short time.

【Key words】Cellular automata;Route planning;Unmanned aerial vehicle

0 引言

航路規劃是根據無人機所處的環境和無人機自身的機動能力，在障礙環境中規劃出一條從起始點到目標點的安全路徑。航路規劃廣泛應用于有人和無人飛機突防、民用航空運輸、無人車、無人艇[1-2]等領域。目前的航路規劃算法有A*搜索算法、人工勢場法等[3-4]。A*搜索算法利用啟發信息來搜索，減少了搜索范圍，降低了問題復雜度，但是存在隨著搜索空間的增大會使計算時間變長、占用內存、只能用于離線狀態等問題[5]。人工勢場法是通過設定環境中目標與障礙的勢場函數，根據目標的引力和障礙的斥力，在環境中規劃出一條最優航跡。人工勢場法的優點是計算速度快，實時性好，但存在目標不可達和局部極值問題[6]，目前解決人工勢場法問題的方法有模糊控制器法、遺傳算法和模擬退火算法等[7]，這些解決方法均是在目標陷入局部極值后選擇跳出極值的策略，并沒有解決局部產生極值的問題。

本文利用元胞自動機演化算法模型，實現元胞自動機航路規劃算法，根據無人機周圍障礙分布情況，選擇出無障礙可行路徑，元胞自動機航路規劃算法實時性高，計算量少，可在短時間內規劃出一條最短的可行航路。

1 元胞自動機算法

元胞自動機是由馮諾依曼提出，來源于生物學的細胞繁殖。元胞自動機模型中，元胞分布于規則的網格中，一個網格為一個元胞，每一個元胞取有限的離散狀態，根據設定的規則，元胞通過規則與周圍其他元胞相互作用，實現狀態更新。元胞自動機由元胞、元胞空間、鄰居和狀態轉換規則四要素構成，用式（1）表示。

式中，A為元胞自動機系統;L為元胞空間，d為元胞空間維數;Q為元胞狀態的狀態集用式（2）表示;N為當前元胞在內所有鄰居元胞集合;f為元胞自動機狀態轉換規則。

式中，0表示睡眠，1表示工作。

基于元胞自動機的航路規劃算法大都選用Moore型元胞自動機，其原理如圖1所示。綠色方格為當前的元胞，鄰居的8個元胞為當前元胞下一步運動可達元胞位置。每個元胞的網格大小代表運動體每一步運動的實際大小，根據運動體實際周圍的障礙分布情況，將障礙所在區域設為障礙元胞，障礙元胞為不可達元胞。根據當前元胞周圍的8個元胞中可到元胞與目標元胞的距離，選取距離最短的可達元胞作為運動體下一步的位置，直到當前元胞到達目標元胞為止。

根據無人機周圍障礙分布情況，將無障礙范圍區域內坐標對應的數值設為0，即可達元胞位置坐標的數值為0;將障礙范圍區域內坐標對應的數值設為1，即障礙元胞位置的數值為1。

元胞自動機算法步驟：

第一步：根據出當前元胞周圍8個元胞坐標中的數值，選擇出可達元胞;

第二步：計算出每個可達元胞與目標元胞的位置;

第三步：將距離目標元胞最短的可達元胞設置為當前元胞下一步移動到的位置。

第四步：根據第三步結果，移動元胞位置。

2 航路規劃算法仿真

本文使用matlab平臺進行元胞自動機航路規劃算法仿真。設置了二維環境情況下，單目標和多目標等不同情況的航路規劃任務，以及三維環境下元胞自動機的航路規劃算法仿真分析。

設置如圖2所示的二維環境下障礙分布地形圖，航路規劃目標位置為1個。圖中紅色區域為障礙物，為了使規劃出的航路更加安全，對建立的環境障礙模型進行膨脹放大，以保證無人機與障礙物有一定的安全距離，黃色區域為膨脹放大區。仿真算法中，在紅色區域和黃色區域的元胞均為障礙元胞，其他區域均為可達元胞。

綠色航線為元胞自動機算法規劃出的航路，可以看到算法規劃出的航路能夠避開障礙物到達目標位置，并與實際的紅色障礙物保持一定的安全距離，保證了無人機的飛行安全?？梢钥闯鲆巹澇龅暮骄€都是直線到達，迭代步數少，耗時短。

設置如圖3所示的二維環境下障礙分布地形圖，航路規劃目標位置為4個。綠色航線為元胞自動機算法規劃出的航路，可以看到在多目標位置的情況下，算法規劃出的航路能夠安全的避開障礙物，并且按照設定的目標位置順序依次到達。

三維環境不同于二維環境，包含了高度方向，元胞從二維擴展到三維，當前元胞可達的元胞除了本層元胞外，還有上層元胞和下層元胞可達，因此當前元胞周圍可達的元胞數量增加到了26個。設置如圖4所示的三維環境下障礙分布地形圖，航路規劃目標位置為1個。同樣對建立的三維環境障礙模型進行膨脹放大，綠色航線為元胞自動機算法規劃出的航路，可以看到在三維環境情況下，算法規劃出的航路能夠改變高度，進而安全的避開障礙物，到達設定的目標位置。圖4 三維單目標實時規劃航路圖

3 總結

利用元胞自動機算法進行無人機航路規劃仿真，算法可實現單個和多個目標位置的航路規劃，為無人機規劃出一條安全可行的航線。并且在多目標位置情況下，可按照設定順序依次到達。元胞自動機航路規劃算法不僅可以實現二維障礙環境下的航路規劃，擴展到三維障礙環境下也可實現航路規劃。仿真結果表明，元胞自動機航路規劃算法實時性高，計算量少，可在短時間內規劃出一條安全可行的航路。

【參考文獻】

[1]王壯.無人機航路規劃方法研究[D].碩士學位論文，西安，西安電子科技大學，2017.

[2]趙云欽，蔡超，王厚軍，等.基于帶電粒子搜索的無人潛航器航路規劃方法[J]，計算機應用，2018，38（7）：2107-2112.

[3]程越，周中良，江建成.基于改進稀疏A*編隊航跡實時規劃方法[J].火力與指揮控制，2018，43（6）：0947-0950.

[4]盧艷軍，李月茹.基于改進人工勢場法的四旋翼飛行器航跡規劃[J].火力與指揮控制，2018，43（11）：1984-1986.

[5]王村松.多無人機編隊在線協同航路規劃方法研究[D]. 南昌：南昌航空大學，2016.

[6]熊俊強.基于人工勢場的多無人機航跡規劃一致性研究[D].南昌：南昌航空大學，2017.

[7]Zhang Yingkun.Flight path planning of agriculture UAV based on improved artificial potential field method[C].The 30th Chinese Control and Decision Conference，2018：1526-1530.