时时彩计划软件破解版|天机时时彩计划王网站
?

基于并行蟻群算法的設施溫室機器人多點路徑規劃的研究

2019-11-13 03:11:12 江蘇農業科學 2019年17期

王紅君 付勇 岳有軍

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

關鍵詞:溫室機器人;多工作點;安全性;高精度;自調整

中圖分類號: TP242 ?文獻標志碼: A ?文章編號:1002-1302(2019)17-0237-05

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

TSP問題是一個著名的組合優化問題,同時也是頗具研發挑戰難度的一類工程項目任務[4]。可以簡單描述為有一個旅行商人要拜訪n個城市,他必須選擇所要走的路徑,路徑的限制是每個城市只能拜訪1次,而且最后要回到原來出發的城市[5]。路徑選擇目標的要求是在走完所有城市到達終點后所走的總路程是最短的。

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

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

本研究提出一種并行蟻群算法來解決設施溫室大棚中的農業機器人多點路徑規劃問題,該算法使用改進的螞蟻數量自調整的蟻群算法來計算多個點與點之間的最短安全距離,然后進行尋優,找到使得總體路徑最短的順序,最后進行點與點之間的路徑規劃。

1 基本算法原理

1.1 基于柵格的環境地圖建模

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

如圖1所示,采用直角坐標法,黑色區域代表農作物種植和設備所在區域(危險區域),白色區域代表空地(安全區域)。危險區域的柵格中心坐標表示為障礙物的中心點,安全區域(白色部分)的柵格中心點作為農業機器人可行走的路徑點。

1.2 蟻群算法

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

2 改進的蟻群算法

2.1 并行蟻群算法

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

目前蟻群算法雖然能很好地解決TSP問題,但在設施溫室大棚中不能精準、安全地實現多點路徑規劃。為此,本研究提出采用改進的并行蟻群算法來解決設施溫室大棚農業機器人多點路徑規劃的問題。

2.2 點與點之間的距離計算

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

2.5 算法流程

本研究算法流程見圖2。

3 仿真試驗及分析

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

通過對未考慮ω和考慮ω且對不同的ω得到不同螞蟻數量所產生路徑規劃結果進行分析比較得到表1、表2:在中短距離時,ω=2時花費時間較短,而在長距離時,未考慮ω的情況花費時間較短,但是當2點相距較遠時,未考慮ω所得到的結果在迭代穩定后又會出現跳變的不穩定現象。因此要考慮復雜度系數ω。

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

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

多點路徑規劃得到的結果見圖5,用蟻群算法進行多點規劃得到最優順序為:1、2、4、7、5、3、6、8、9、10、13、11、12、14。

在多點路徑規劃的過程中,隨著歷代螞蟻的尋優,由圖6可知,在對14個點進行路徑規劃的過程中,螞蟻在10代左右就可以找到最優順序實現總路程最短,總路程為55.355 0 cm。

4 結論

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

參考文獻:

[1]梁宏偉,陶學恒,張世文. 移動機器人的遺傳多點路徑規劃[J]. 科技信息(學術研究),2008(21):584-585,587.

[2]鄭繼明,楊 坤,劉慧鵬,等. 基于0-1線性規劃的多點路由規劃模型研究[J]. 通信技術,2017,50(7):1443-1446.

[3]Dantzig G,Fulkerson 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]. 山西師范大學學報(自然科學版),2017,31(3):34-37.

[7]蒲興成,李俊杰,吳慧超,等. 基于改進粒子群算法的移動機器人多目標點路徑規劃[J]. 智能系統學報,2017,6(3):301-309.

[8]楊岱川,文成林. 基于蟻群和改進PRM算法的多目標點路徑規劃[J]. 杭州電子科技大學學報(自然科學版),2017,37(3):63-67.

[9]于 暉,王永驥. 基于fast marching方法的多目標點路徑規劃的研究[J]. 計算技術與自動化,2015,34(3):11-15.

[10]史恩秀,陳敏敏,李 俊,等. 基于蟻群算法的移動機器人全局路徑規劃方法研究[J]. 農業機械學報,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]朱鐵欣,董桂菊,顏丙學,等. 基于改進蟻群算法的農業機器人路徑規劃研究[J]. 農機化研究,2016(9):48-52.

[13]喻 環. 改進蟻群算法在機器人路徑規劃上的應用研究[D]. 合肥:安徽大學,2017.

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

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

[16]張 可. 蟻群算法的參數調整研究[D]. 合肥:合肥工業大學,2012.

[17]楊亞南. 蟻群算法參數優化及其應用[D]. 南京:南京理工大學,2008.

?
(function(){ var bp = document.createElement('script'); var curProtocol = window.location.protocol.split(':')[0]; if (curProtocol === 'https') { bp.src = 'https://zz.bdstatic.com/linksubmit/push.js'; } else { bp.src = 'http://push.zhanzhang.baidu.com/push.js'; } var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(bp, s); })();
时时彩计划软件破解版 pk10一天赚一千的方法 贝贝捕鱼大闹天宫 ag街头烈战开奖结果 棋牌捕鱼平台 做ipo很赚钱么 pk10最牛稳赚模式最新 手机微信能赚钱的软件叫什么 pk10人工计划在线划准 刷金币赚钱的游戏吗 福彩快三中奖奖金规则 如何在快手赚钱 吉林快三下载安装官网 微信赌博大小单双玩法 天龙国际娱乐网址 山东11选5走势图表 小长假怎么赚钱