基于并行蟻群算法的設(shè)施溫室機(jī)器人多點(diǎn)路徑規(guī)劃的研究

王紅君 付勇 岳有軍

摘要：在設(shè)施溫室中，為了實(shí)現(xiàn)機(jī)器人在面對(duì)多個(gè)工作點(diǎn)時(shí)，能夠找到一個(gè)最優(yōu)順序使得完成全部工作所走過(guò)的路程最短，受蟻群算法解決旅行商問(wèn)題（TSP）的啟發(fā)，提出一種并行的蟻群算法來(lái)解決設(shè)施溫室農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃問(wèn)題。首先，該算法借助于螞蟻數(shù)量自調(diào)整的蟻群算法計(jì)算出所有點(diǎn)與點(diǎn)之間的最短安全距離，形成一個(gè)特殊的距離矩陣;然后借助于蟻群算法根據(jù)特殊的距離矩陣來(lái)尋找最優(yōu)順序;再按照最優(yōu)順序依次實(shí)現(xiàn)路徑規(guī)劃。仿真結(jié)果表明，該方法克服了目前蟻群算法在解決TSP上存在的近似計(jì)算及未考慮安全性問(wèn)題，提高了計(jì)算精度，可以快速找到最優(yōu)順序進(jìn)行路徑規(guī)劃，使機(jī)器人得到最短、最安全的路徑。

關(guān)鍵詞：溫室機(jī)器人;多工作點(diǎn);安全性;高精度;自調(diào)整

中圖分類(lèi)號(hào)： TP242 ?文獻(xiàn)標(biāo)志碼： A ?文章編號(hào)：1002-1302（2019）17-0237-05

路徑規(guī)劃是機(jī)器人領(lǐng)域研究的熱點(diǎn)之一。在溫室中，通過(guò)路徑規(guī)劃，機(jī)器人可以實(shí)現(xiàn)自主避開(kāi)障礙物，找到一條安全、最短的路徑到達(dá)指定位置進(jìn)行工作。由于在設(shè)施溫室中機(jī)器人的工作地點(diǎn)往往是隨機(jī)分布的，為了能讓機(jī)器人以最短的距離遍歷全部工作地點(diǎn)，并完成全部工作，要求機(jī)器人可以實(shí)現(xiàn)多點(diǎn)路徑規(guī)劃[1]。由于多點(diǎn)路徑規(guī)劃就是遍歷全部指定地點(diǎn)且僅經(jīng)過(guò)1次，最后到達(dá)終點(diǎn)，且總路程最短[2]，因此可以將多點(diǎn)路徑規(guī)劃歸結(jié)為旅行商問(wèn)題（TSP）[3]。

TSP問(wèn)題是一個(gè)著名的組合優(yōu)化問(wèn)題，同時(shí)也是頗具研發(fā)挑戰(zhàn)難度的一類(lèi)工程項(xiàng)目任務(wù)[4]?？梢院?jiǎn)單描述為有一個(gè)旅行商人要拜訪(fǎng)n個(gè)城市，他必須選擇所要走的路徑，路徑的限制是每個(gè)城市只能拜訪(fǎng)1次，而且最后要回到原來(lái)出發(fā)的城市[5]。路徑選擇目標(biāo)的要求是在走完所有城市到達(dá)終點(diǎn)后所走的總路程是最短的。

經(jīng)過(guò)不斷探索，目前已提出如蟻群算法、遺傳算法、粒子群算法等解決TSP問(wèn)題的智能算法。鄧慧允等通過(guò)對(duì)比發(fā)現(xiàn)，在解決TSP問(wèn)題上，無(wú)論城市個(gè)數(shù)多少、城市之間的距離遠(yuǎn)近，蟻群算法都要優(yōu)于遺傳算法[6]。蒲興成等將蟻群算法與粒子群算法相結(jié)合，不僅實(shí)現(xiàn)了點(diǎn)與點(diǎn)之間的距離最短，還將點(diǎn)與點(diǎn)之間的安全性考慮在內(nèi)，較好地實(shí)現(xiàn)了移動(dòng)機(jī)器人多目標(biāo)點(diǎn)的路徑規(guī)劃，但該方法所得到的路徑，并沒(méi)有達(dá)到最短[7];楊岱川等提出將蟻群算法和改進(jìn)PRM算法相結(jié)合，可以快速有效地實(shí)現(xiàn)多點(diǎn)路徑規(guī)劃，但該方法在路徑規(guī)劃時(shí)存在隨機(jī)性[8];余暉等提出將快速行進(jìn)（fast marching）算法與遺傳算法相結(jié)合來(lái)進(jìn)行路徑規(guī)劃，并將該方法應(yīng)用到水下多點(diǎn)水質(zhì)監(jiān)測(cè)[9]。

在設(shè)施溫室大棚中，多目標(biāo)點(diǎn)路徑規(guī)劃比TSP問(wèn)題復(fù)雜得多。既要找到使總路程最短的路徑，還要保證點(diǎn)與點(diǎn)之間路徑的安全性。雖然城市之間存在大量的障礙，且道路不可能是筆直的，因此蟻群算法在解決TSP問(wèn)題時(shí)通過(guò)近似計(jì)算來(lái)計(jì)算2個(gè)城市之間的距離，由于距離較遠(yuǎn)、范圍較大、要求精度不高，所以是合理的。但由于農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃的工作環(huán)境是在設(shè)施溫室中，范圍較小，且環(huán)境復(fù)雜存在著障礙物，要求精度較高，如果采用相同的方式進(jìn)行計(jì)算尋優(yōu)，會(huì)導(dǎo)致在設(shè)施溫室中，農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃所得到的最終結(jié)果不精準(zhǔn)、不安全。

本研究提出一種并行蟻群算法來(lái)解決設(shè)施溫室大棚中的農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃問(wèn)題，該算法使用改進(jìn)的螞蟻數(shù)量自調(diào)整的蟻群算法來(lái)計(jì)算多個(gè)點(diǎn)與點(diǎn)之間的最短安全距離，然后進(jìn)行尋優(yōu)，找到使得總體路徑最短的順序，最后進(jìn)行點(diǎn)與點(diǎn)之間的路徑規(guī)劃。

1 基本算法原理

1.1 基于柵格的環(huán)境地圖建模

本研究探討的是設(shè)施溫室中的農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃問(wèn)題，可以在二維空間進(jìn)行分析[10]。目前環(huán)境建模的方法有很多種：?jiǎn)卧纸夥?、模板模型法、拓?fù)浞?、可視圖法、幾何法。柵格法在實(shí)現(xiàn)上較為簡(jiǎn)單，通過(guò)矩陣就可以實(shí)現(xiàn)。因此本研究采用柵格法對(duì)設(shè)施溫室大棚環(huán)境進(jìn)行創(chuàng)建。

如圖1所示，采用直角坐標(biāo)法，黑色區(qū)域代表農(nóng)作物種植和設(shè)備所在區(qū)域（危險(xiǎn)區(qū)域），白色區(qū)域代表空地（安全區(qū)域）。危險(xiǎn)區(qū)域的柵格中心坐標(biāo)表示為障礙物的中心點(diǎn)，安全區(qū)域（白色部分）的柵格中心點(diǎn)作為農(nóng)業(yè)機(jī)器人可行走的路徑點(diǎn)。

1.2 蟻群算法

蟻群算法具有較強(qiáng)的魯棒性、優(yōu)良的分布式計(jì)算，易于與其他算法相結(jié)合[11-12]。蟻群算法解決TSP問(wèn)題的基本原理，是在最初的時(shí)候?qū)⑽浵伔诺礁鱾€(gè)城市上，根據(jù)城市之間的距離來(lái)確定螞蟻從某一城市到另一城市之間的概率，距離越小，被選中的概率越大，螞蟻在走過(guò)的路徑上釋放信息素，信息素濃度隨時(shí)間降低，后代螞蟻根據(jù)前一代螞蟻所留下的信息素的濃度的大小，確定行走的路徑，并在所確定的路徑上釋放信息素;經(jīng)過(guò)歷代螞蟻的尋找，最終找到信息素濃度最高的就是最優(yōu)路徑[13]。

2 改進(jìn)的蟻群算法

2.1 并行蟻群算法

由于在設(shè)施溫室大棚中的農(nóng)業(yè)機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃可以歸結(jié)為T(mén)SP問(wèn)題，但是多目標(biāo)點(diǎn)路徑規(guī)劃問(wèn)題要比TSP問(wèn)題復(fù)雜得多，不僅對(duì)精度要求較高，還要考慮到安全性的問(wèn)題[14-15]。在存在障礙物的設(shè)施溫室中，計(jì)算2點(diǎn)之間的距離不能忽略安全因素，須保證機(jī)器人能夠在2點(diǎn)之間安全行走。保證機(jī)器人實(shí)際行走路程與計(jì)算的距離相等，不存在近似計(jì)算，從而提高精確度。

目前蟻群算法雖然能很好地解決TSP問(wèn)題，但在設(shè)施溫室大棚中不能精準(zhǔn)、安全地實(shí)現(xiàn)多點(diǎn)路徑規(guī)劃。為此，本研究提出采用改進(jìn)的并行蟻群算法來(lái)解決設(shè)施溫室大棚農(nóng)業(yè)機(jī)器人多點(diǎn)路徑規(guī)劃的問(wèn)題。

2.2 點(diǎn)與點(diǎn)之間的距離計(jì)算

在存在障礙物的柵格圖中要計(jì)算2點(diǎn)之間的最短安全距離，僅利用歐拉公式（2）計(jì)算不能達(dá)到目的。

2.5 算法流程

本研究算法流程見(jiàn)圖2。

3 仿真試驗(yàn)及分析

為了檢測(cè)該算法的有效性及優(yōu)越性，本研究借助于Matlab軟件對(duì)其進(jìn)行了仿真試驗(yàn)。在帶有障礙物的柵格中隨機(jī)選取了14個(gè)點(diǎn)分別作為起點(diǎn)、終點(diǎn)以及必經(jīng)點(diǎn)，規(guī)定機(jī)器人從起點(diǎn)出發(fā)到達(dá)終點(diǎn)，中途只能經(jīng)過(guò)1次必經(jīng)點(diǎn)。設(shè)置搜索最優(yōu)順序的蟻群算法的相關(guān)參數(shù)：每一代的螞蟻數(shù)目m=50，蟻群迭代次數(shù)K=200，信息素α=1，啟發(fā)式因子β=4，信息素蒸發(fā)系數(shù)ρ=0.2，信息素增加Q=100[16-17]。所有點(diǎn)的坐標(biāo)a1（0.5，19.5）、a2（2.5，16.5）、a3（9.5，16.5）、a4（4.5，14.5）、a5（6.5，14.5）、a6（11.5，14.5）、a7（3.5，10.5）、a8（8.5，11.5）、a9（10.5，7.5）、a10（8.5，7.5）、a11（14.5，6-5）、a12（16.5，4.5）、a13（12.5，2.5）、a14（19.5，0.5）。

圖3是在設(shè)有障礙物的柵格中標(biāo)有多個(gè)工作點(diǎn)的坐標(biāo)點(diǎn)。其中1表示農(nóng)業(yè)機(jī)器人的起點(diǎn)，14表示終點(diǎn)，2～13表示的是必經(jīng)過(guò)點(diǎn)。

通過(guò)對(duì)未考慮ω和考慮ω且對(duì)不同的ω得到不同螞蟻數(shù)量所產(chǎn)生路徑規(guī)劃結(jié)果進(jìn)行分析比較得到表1、表2：在中短距離時(shí)，ω=2時(shí)花費(fèi)時(shí)間較短，而在長(zhǎng)距離時(shí)，未考慮ω的情況花費(fèi)時(shí)間較短，但是當(dāng)2點(diǎn)相距較遠(yuǎn)時(shí)，未考慮ω所得到的結(jié)果在迭代穩(wěn)定后又會(huì)出現(xiàn)跳變的不穩(wěn)定現(xiàn)象。因此要考慮復(fù)雜度系數(shù)ω。

由表1、表2也可以看出，當(dāng)2點(diǎn)距離較近時(shí)，復(fù)雜度系數(shù)ω的取值對(duì)趨于穩(wěn)定的時(shí)間影響較小;但是距離較遠(yuǎn)時(shí)，復(fù)雜度系數(shù)ω的取值對(duì)區(qū)域穩(wěn)定的時(shí)間影響較大。所以當(dāng)2點(diǎn)之間的距離較近時(shí)，確定螞蟻數(shù)量可以不考慮ω，當(dāng)距離較遠(yuǎn)時(shí)，就必須考慮ω。因此從全局的角度考慮，為了進(jìn)一步確定ω的范圍，以遠(yuǎn)距離為試驗(yàn)對(duì)象，對(duì)ω從1.3～2.0進(jìn)行試驗(yàn)，結(jié)果見(jiàn)圖4。通過(guò)多次試驗(yàn)發(fā)現(xiàn)，在ω小于等于1.4時(shí)易出現(xiàn)迭代穩(wěn)定后的跳變不穩(wěn)定現(xiàn)象，為了能夠保證蟻群算法的穩(wěn)定性，ω取值要大于1.4;從圖4曲線(xiàn)可知：當(dāng)ω為1.6時(shí)所用時(shí)間最短，且隨著復(fù)雜度系數(shù)ω的增加（螞蟻數(shù)量的增加），所耗時(shí)間越多。

取ω=1.6進(jìn)行全局的仿真試驗(yàn)，結(jié)果見(jiàn)表3，根據(jù)起點(diǎn)和終點(diǎn)的歐氏距離以及復(fù)雜度系數(shù)得到螞蟻的數(shù)量，從全局結(jié)果來(lái)看該方法得到的螞蟻數(shù)量較好，可以快速地找到最優(yōu)路徑。

多點(diǎn)路徑規(guī)劃得到的結(jié)果見(jiàn)圖5，用蟻群算法進(jìn)行多點(diǎn)規(guī)劃得到最優(yōu)順序?yàn)椋?、2、4、7、5、3、6、8、9、10、13、11、12、14。

在多點(diǎn)路徑規(guī)劃的過(guò)程中，隨著歷代螞蟻的尋優(yōu)，由圖6可知，在對(duì)14個(gè)點(diǎn)進(jìn)行路徑規(guī)劃的過(guò)程中，螞蟻在10代左右就可以找到最優(yōu)順序?qū)崿F(xiàn)總路程最短，總路程為55.355 0 cm。

4 結(jié)論

在農(nóng)業(yè)設(shè)施溫室大棚中，為了能夠讓機(jī)器人在面對(duì)多個(gè)工作點(diǎn)時(shí)，快速找到1條遍歷所有點(diǎn)完成相應(yīng)的工作最終到達(dá)終點(diǎn)的最短安全路徑，本研究在蟻群算法解決TSP問(wèn)題的基礎(chǔ)上，提出了一種精度高、安全性好的螞蟻數(shù)量自調(diào)整的并行蟻群算法進(jìn)行路徑規(guī)劃。從仿真結(jié)果來(lái)看，該算法有以下優(yōu)點(diǎn)：（1）構(gòu)建了一個(gè)新的數(shù)學(xué)模型來(lái)求解螞蟻數(shù)量，并找到了復(fù)雜度系數(shù)ω的合理取值范圍。（2）在計(jì)算不同點(diǎn)之間的距離時(shí)，可以根據(jù)距離自行調(diào)整螞蟻的數(shù)量在合理范圍之內(nèi)。（3）可以精確地計(jì)算出點(diǎn)與點(diǎn)之間的安全最短距離。（4）可以規(guī)劃出遍歷所有點(diǎn)的最優(yōu)順序，使得總的路程最短、最安全。（5）從收斂曲線(xiàn)來(lái)看，該算法在尋優(yōu)的過(guò)程中可以快速找到最優(yōu)路徑并趨于穩(wěn)定。

參考文獻(xiàn)：

[1]梁宏偉，陶學(xué)恒，張世文. 移動(dòng)機(jī)器人的遺傳多點(diǎn)路徑規(guī)劃[J]. 科技信息（學(xué)術(shù)研究），2008（21）：584-585，587.

[2]鄭繼明，楊 坤，劉慧鵬，等. 基于0-1線(xiàn)性規(guī)劃的多點(diǎn)路由規(guī)劃模型研究[J]. 通信技術(shù)，2017，50（7）：1443-1446.

[3]Dantzig G，F(xiàn)ulkerson R，Johnson S. Solution of a large-scale traveling-salesman problem[J]. Journal of the operations research society of America，1954，2（4）：393-410.

[4]Caballero R，Hernandez-Diaz A G，Laguna M，et al. Cross entropy for multiobjective optimization problems with linear relaxation[J]. European Journal of Operation Research，2015，243（2）：362-368.

[5]Lin W，Delgado-Frias J G，Gause D C，et al. Hybrid newton-raphson genetic algorithm for the traveling salesman problem[J]. Journal of Cybernetics，1995，26（4）：387-412.

[6]鄧慧允，張清泉. 蟻群算法與遺傳算法在TSP中的對(duì)比研究[J]. 山西師范大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，31（3）：34-37.

[7]蒲興成，李俊杰，吳慧超，等. 基于改進(jìn)粒子群算法的移動(dòng)機(jī)器人多目標(biāo)點(diǎn)路徑規(guī)劃[J]. 智能系統(tǒng)學(xué)報(bào)，2017，6（3）：301-309.

[8]楊岱川，文成林. 基于蟻群和改進(jìn)PRM算法的多目標(biāo)點(diǎn)路徑規(guī)劃[J]. 杭州電子科技大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，37（3）：63-67.

[9]于 暉，王永驥. 基于fast marching方法的多目標(biāo)點(diǎn)路徑規(guī)劃的研究[J]. 計(jì)算技術(shù)與自動(dòng)化，2015，34（3）：11-15.

[10]史恩秀，陳敏敏，李 俊，等. 基于蟻群算法的移動(dòng)機(jī)器人全局路徑規(guī)劃方法研究[J]. 農(nóng)業(yè)機(jī)械學(xué)報(bào)，2014，45（6）：53-57.

[11]Vogt L，Poojari C A，Beasley J E. A tabu search algorithm for the single vehicle routing allocation problem[J]. Journal of the Operational Research Society，2007，58（4）：467-480.

[12]朱鐵欣，董桂菊，顏丙學(xué)，等. 基于改進(jìn)蟻群算法的農(nóng)業(yè)機(jī)器人路徑規(guī)劃研究[J]. 農(nóng)機(jī)化研究，2016（9）：48-52.

[13]喻 環(huán). 改進(jìn)蟻群算法在機(jī)器人路徑規(guī)劃上的應(yīng)用研究[D]. 合肥：安徽大學(xué)，2017.

[14]朱 霞，陳仁文，徐棟霞，等. 基于改進(jìn)粒子群的焊點(diǎn)檢測(cè)路徑規(guī)劃方法[J]. 儀器儀表學(xué)報(bào)，2014，35（11）：2484-2493.

[15]蕭蘊(yùn)詩(shī)，李炳宇，吳啟迪. 求解TSP問(wèn)題的模式學(xué)習(xí)并行蟻群算法[J]. 控制與決策，2004（8）：885-888.

[16]張 可. 蟻群算法的參數(shù)調(diào)整研究[D]. 合肥：合肥工業(yè)大學(xué)，2012.

[17]楊亞南. 蟻群算法參數(shù)優(yōu)化及其應(yīng)用[D]. 南京：南京理工大學(xué)，2008.