基于元胞自動(dòng)機(jī)的無人機(jī)航路規(guī)劃算法研究

劉震

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3 總結(jié)

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

【參考文獻(xiàn)】

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

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

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

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

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

[6]熊俊強(qiáng).基于人工勢(shì)場(chǎ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.