劉震

【摘 要】本文利用元胞自動機(jī)算法模型，對無人機(jī)航路規(guī)劃進(jìn)行仿真。實現(xiàn)了單目標(biāo)和多目標(biāo)，以及二維環(huán)境和三維環(huán)境下的航路規(guī)劃仿真。仿真結(jié)果表明，元胞自動機(jī)航路規(guī)劃算法實時性高，計算量少，可在短時間內(nèi)規(guī)劃出一條安全可行的航路。

【關(guān)鍵詞】元胞自動機(jī);航路規(guī)劃;無人機(jī)

中圖分類號： V249 文獻(xiàn)標(biāo)識碼： 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 引言

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

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

1 元胞自動機(jī)算法

元胞自動機(jī)是由馮諾依曼提出，來源于生物學(xué)的細(xì)胞繁殖。元胞自動機(jī)模型中，元胞分布于規(guī)則的網(wǎng)格中，一個網(wǎng)格為一個元胞，每一個元胞取有限的離散狀態(tài)，根據(jù)設(shè)定的規(guī)則，元胞通過規(guī)則與周圍其他元胞相互作用，實現(xiàn)狀態(tài)更新。元胞自動機(jī)由元胞、元胞空間、鄰居和狀態(tài)轉(zhuǎn)換規(guī)則四要素構(gòu)成，用式（1）表示。

式中，A為元胞自動機(jī)系統(tǒng);L為元胞空間，d為元胞空間維數(shù);Q為元胞狀態(tài)的狀態(tài)集用式（2）表示;N為當(dāng)前元胞在內(nèi)所有鄰居元胞集合;f為元胞自動機(jī)狀態(tài)轉(zhuǎn)換規(guī)則。

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

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

根據(jù)無人機(jī)周圍障礙分布情況，將無障礙范圍區(qū)域內(nèi)坐標(biāo)對應(yīng)的數(shù)值設(shè)為0，即可達(dá)元胞位置坐標(biāo)的數(shù)值為0;將障礙范圍區(qū)域內(nèi)坐標(biāo)對應(yīng)的數(shù)值設(shè)為1，即障礙元胞位置的數(shù)值為1。

元胞自動機(jī)算法步驟：

第一步：根據(jù)出當(dāng)前元胞周圍8個元胞坐標(biāo)中的數(shù)值，選擇出可達(dá)元胞;

第二步：計算出每個可達(dá)元胞與目標(biāo)元胞的位置;

第三步：將距離目標(biāo)元胞最短的可達(dá)元胞設(shè)置為當(dāng)前元胞下一步移動到的位置。

第四步：根據(jù)第三步結(jié)果，移動元胞位置。

2 航路規(guī)劃算法仿真

本文使用matlab平臺進(jìn)行元胞自動機(jī)航路規(guī)劃算法仿真。設(shè)置了二維環(huán)境情況下，單目標(biāo)和多目標(biāo)等不同情況的航路規(guī)劃任務(wù)，以及三維環(huán)境下元胞自動機(jī)的航路規(guī)劃算法仿真分析。

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

綠色航線為元胞自動機(jī)算法規(guī)劃出的航路，可以看到算法規(guī)劃出的航路能夠避開障礙物到達(dá)目標(biāo)位置，并與實際的紅色障礙物保持一定的安全距離，保證了無人機(jī)的飛行安全?？梢钥闯鲆?guī)劃出的航線都是直線到達(dá)，迭代步數(shù)少，耗時短。

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

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

3 總結(jié)

利用元胞自動機(jī)算法進(jìn)行無人機(jī)航路規(guī)劃仿真，算法可實現(xiàn)單個和多個目標(biāo)位置的航路規(guī)劃，為無人機(jī)規(guī)劃出一條安全可行的航線。并且在多目標(biāo)位置情況下，可按照設(shè)定順序依次到達(dá)。元胞自動機(jī)航路規(guī)劃算法不僅可以實現(xiàn)二維障礙環(huán)境下的航路規(guī)劃，擴(kuò)展到三維障礙環(huán)境下也可實現(xiàn)航路規(guī)劃。仿真結(jié)果表明，元胞自動機(jī)航路規(guī)劃算法實時性高，計算量少，可在短時間內(nèi)規(guī)劃出一條安全可行的航路。

【參考文獻(xiàn)】

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

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

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

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

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

[6]熊俊強(qiáng).基于人工勢場的多無人機(jī)航跡規(guī)劃一致性研究[D].南昌：南昌航空大學(xué)，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.