王紅君 付勇 岳有軍

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

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

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

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

TSP問題是一個著名的組合優(yōu)化問題，同時也是頗具研發(fā)挑戰(zhàn)難度的一類工程項目任務(wù)[4]?？梢院唵蚊枋鰹橛幸粋€旅行商人要拜訪n個城市，他必須選擇所要走的路徑，路徑的限制是每個城市只能拜訪1次，而且最后要回到原來出發(fā)的城市[5]。路徑選擇目標(biāo)的要求是在走完所有城市到達終點后所走的總路程是最短的。

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

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

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

1 基本算法原理

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

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

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

1.2 蟻群算法

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

2 改進的蟻群算法

2.1 并行蟻群算法

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

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

2.2 點與點之間的距離計算

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

2.5 算法流程

本研究算法流程見圖2。

3 仿真試驗及分析

為了檢測該算法的有效性及優(yōu)越性，本研究借助于Matlab軟件對其進行了仿真試驗。在帶有障礙物的柵格中隨機選取了14個點分別作為起點、終點以及必經(jīng)點，規(guī)定機器人從起點出發(fā)到達終點，中途只能經(jīng)過1次必經(jīng)點。設(shè)置搜索最優(yōu)順序的蟻群算法的相關(guān)參數(shù)：每一代的螞蟻數(shù)目m=50，蟻群迭代次數(shù)K=200，信息素α=1，啟發(fā)式因子β=4，信息素蒸發(fā)系數(shù)ρ=0.2，信息素增加Q=100[16-17]。所有點的坐標(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)有多個工作點的坐標(biāo)點。其中1表示農(nóng)業(yè)機器人的起點，14表示終點，2～13表示的是必經(jīng)過點。

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

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

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

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

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

4 結(jié)論

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

參考文獻：

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

[2]鄭繼明，楊 坤，劉慧鵬，等. 基于0-1線性規(guī)劃的多點路由規(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中的對比研究[J]. 山西師范大學(xué)學(xué)報（自然科學(xué)版），2017，31（3）：34-37.

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

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

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

[10]史恩秀，陳敏敏，李 俊，等. 基于蟻群算法的移動機器人全局路徑規(guī)劃方法研究[J]. 農(nóng)業(yè)機械學(xué)報，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é)，等. 基于改進蟻群算法的農(nóng)業(yè)機器人路徑規(guī)劃研究[J]. 農(nóng)機化研究，2016（9）：48-52.

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

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

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

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

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