李辰豪 吳啟來 郭晟男
(南京理工大學 江蘇省南京市 210094)
目前,國內(nèi)外研究人員針對地面機器人的研究已經(jīng)取得了較大的成果,其發(fā)展也日益成熟。除此之外,在空中無人機和水中無人艦艇的開發(fā)與應用方面,很多學者都開展了較為豐富的研究。但是上述的機器人都局限于某一種特定工作環(huán)境,如,地面、空中、水面,因而針對這些機器人的研究也具有單一性。在現(xiàn)實世界中存在著多種環(huán)境域,當任務(wù)涉及到多種環(huán)境域時,這就要求機器人同時具備在多種環(huán)境域下的工作能力。路徑規(guī)劃是移動機器人運動與仿真領(lǐng)域的熱點研究問題,國內(nèi)外很多學者都在這個研究方向上進行了大量的研究與探索,但路徑規(guī)劃的算法仍有不足與可改進之處。
傳統(tǒng)A*算法以路徑最短作為規(guī)劃目標,以此目標規(guī)劃的路徑并不適用一些特定目標的任務(wù)。文獻中提到了機器人陸空兩棲的決策切換和規(guī)劃,文獻提出了水陸兩棲的路徑規(guī)劃,均不能解決水陸空三棲環(huán)境下的機器人規(guī)劃問題。
在此啟發(fā)下,我們提出一種適合水陸空三棲環(huán)境的基于改進三維A*算法的全局規(guī)劃算法,該算法以機器人的耗能和時間的綜合代價作為規(guī)劃目標。
A*算法是一種在全局靜態(tài)地圖中對最短路徑進行求解和規(guī)劃的最有效的直接搜索方法,也是解決許多其他問題時常用的啟發(fā)式算法,有著較好的性能和準確度。公式表示為:
傳統(tǒng)的A*算法沒有將機器人運動時不同運動狀態(tài)之間相互切換的耗能代價以及在不同環(huán)境運動的時間、耗能代價考慮進去。只把所求解的路徑長度作為規(guī)劃目標,然而,在實際中,多棲機器人的路徑規(guī)劃、運動要考慮諸如耗能、時間等因素,以達到任務(wù)對機器人運動的時間和耗能要求。而本文提出的改進算法將對這一問題進行優(yōu)化解決。
在二維環(huán)境下,A*算法只需拓展當前節(jié)點的8個子節(jié)點,而三維環(huán)境下,需拓展26個子節(jié)點。
三棲機器人的水、陸、空自主切換控制狀態(tài)機的實現(xiàn)如圖1所示。
圖1:機器人自主切換控制狀態(tài)機
由于機器人在水陸空各個環(huán)境下的狀態(tài)不相同,這使得機器人在環(huán)境變化時進行的狀態(tài)切換會產(chǎn)生比較多的能量損耗。表1是機器人不同狀態(tài)切換的能量損耗程度對應表,其對應的F切換損耗屬性評價分別為{0,1,2,3,4,5}。
表1:狀態(tài)切換能量損耗評價表
從當前工作狀態(tài)到待選節(jié)點工作狀態(tài)切換時會產(chǎn)生狀態(tài)切換能耗,在待選工作狀態(tài)向目標點的工作狀態(tài)轉(zhuǎn)換時也會產(chǎn)生狀態(tài)切換能耗。
當三棲機器人在現(xiàn)實環(huán)境下運動時,運動的能量消耗不可忽視。因此在路徑規(guī)劃時需要把機器人在不同環(huán)境下運動的耗能分析和運動時間都作為優(yōu)化目標考慮進去。本文選擇將運動耗能分析和運動時間同時作為三棲機器人最優(yōu)路徑規(guī)劃的優(yōu)化目標。又由于三棲機器人在不同環(huán)境下的運動耗能和運動時間不完全獨立,彼此之間有一定的依賴關(guān)系,所以使用為每個優(yōu)化目標賦予一定權(quán)值的方式對于路徑規(guī)劃算法的多目標啟發(fā)式函數(shù)進行描述。運動過程的耗能代價分為地面運動代價、空中飛行代價以及水面運動代價。
由于運動耗能和運動時間這兩個優(yōu)化目標的量綱不同,很難進行統(tǒng)一的計算與比較,因此本文對不同環(huán)境下運動耗能代價進行統(tǒng)一量綱處理。以地面運動耗能代價e作為基準(保證統(tǒng)一量綱處理后的計算比較耗能代價的值大于等于1),采用各環(huán)境下的運動耗能代價與e的比值作為各環(huán)境下的計算比較耗能代價。
式中E、E、E分別表示地面運動、空中飛行與水面運動的統(tǒng)一量綱處理后的計算比較耗能代價,e、e、e表示各環(huán)境下實際的單位距離耗能代價。
在地圖的三維柵格中,根據(jù)柵格存儲的環(huán)境屬性不同(水、陸、空),規(guī)劃出一條路徑之后,即可獲得在地面運動的距離s、在空中飛行的距離s以及在水面運動的距離s,分別除以三棲機器人在地面運動的速度v、在空中飛行的距離v以及在水面運動的速度v。便可得到不同環(huán)境下的運動時間t、t、t。同理,對其按照空中運動的時間t進行統(tǒng)一量綱處理,得到計算比較運動時間T、T、T。
本文為了與原A*算法的代價函數(shù)相區(qū)分,將代價函數(shù)設(shè)為g'(n),節(jié)點q的代價函數(shù)值g'(b)為其父節(jié)點q的代價函數(shù)值g'(a)與q到q的運動代價、狀態(tài)切換對應的代價之和,因此可以得到節(jié)點q的代價函數(shù)值g'(b)表達式如下:
cost(q,q)表示從節(jié)點q到節(jié)點q所需要耗費代價,結(jié)合2.4的分析,cost(q,q)值的計算表達式如下:
其中α與β分別為不同環(huán)境下運動過程耗能和運動時間的加權(quán)系數(shù),且滿足α+β=1,q.env,q.env分別表示節(jié)點q,q的環(huán)境屬性(land、air、water)。
change(q,q)表示從節(jié)點q到節(jié)點q狀態(tài)切換的代價,對其也按照地面運動的耗能進行統(tǒng)一量綱處理,結(jié)合表1,可得出change(q,q)值的計算表達式如下:
其中κ為正常數(shù),F(xiàn)表示節(jié)點q到節(jié)點q切換損耗屬性評價值。
本文為了與原A*算法的估價函數(shù)相區(qū)分,將代價設(shè)為h'(b)。h'(b)作為q至終點q的預估代價,結(jié)合前文,本文將h'(b)取為和g'(b)相同的形式,可以得到改進后的h'(b)表達式如下:
因此優(yōu)化后的三維A*算法的代價函數(shù)計算公式為:
本文采用三維柵格地圖對三棲環(huán)境進行建模,如圖2所示。
圖2:三維柵格環(huán)境
選擇空間中一固定點作為坐標原點, Z軸方向作為高度。在 Z 軸方向上,均勻?qū)⑷S空間n等分,形成n個平面。每個平面沿著 X 軸與 Y 軸方向分別再n和n等分,則可以用 n×n×n個柵格來表示三維空間環(huán)境信息。每個柵格包含了柵格可通行狀態(tài)和柵格空間類型,如水面、空中柵格或地面柵格。圖3中,藍色區(qū)域為水面柵格,粉色區(qū)域為不可通行柵格,Z=1的區(qū)域為地面柵格,其余為空中柵格。
圖3:第1組實驗軌跡俯視圖
在MATLAB2018環(huán)境下,對改進三維A*算法進行路徑規(guī)劃的仿真實驗。采用50×50×10的柵格地圖作為實驗的仿真環(huán)境。根據(jù)參考文獻、文獻、文獻所提出的機器人的耗能分析并進行仿真實驗,設(shè)置估價函數(shù)的參數(shù)為:
e=12.5, e=9, e=1, t=1,
t=6, t=13, κ=1.7
我們設(shè)置了三組仿真實驗,第1組為能耗、時間權(quán)重分別為0.5、0.5的改進算法與原算法對比實驗;第2組為權(quán)重分別為0.15、0.85的改進算法與原算法對比實驗;第3組實驗為權(quán)重分別0.5、0.5和0.15、0.85的改進算法之間的對比實驗。
圖3,圖4為第1組實驗仿真結(jié)果圖,將目標點設(shè)置在水面中央。藍色軌跡是傳統(tǒng)A*算法,綠色軌跡是改進A*算法。傳統(tǒng)A*算法規(guī)劃時采用了從地面運動狀態(tài)至飛行狀態(tài)的方式飛躍障礙物,并保持飛行狀態(tài),在接近終點時,切換至水面運動狀態(tài)后運動到目標點。改進A*算法規(guī)劃的路徑選擇了維持地面運動狀態(tài)繞開障礙物后,在面對水環(huán)境時,選擇了綜合代價較小的切換至飛行狀態(tài)并向目標點。通過分析表2第1組實驗數(shù)據(jù),在當前耗能、時間權(quán)重和環(huán)境下,改進A* 算法規(guī)劃的路徑雖然路徑長度和時間代價相對比較大,但是耗能代價明顯小,且綜合代價也更小,更利于降低機器人運動的成本。
圖4:第1組實驗軌跡立體圖
表2:傳統(tǒng)算法與改進算法對比實驗數(shù)據(jù)
圖5是第2組實驗仿真結(jié)果圖,將目標點設(shè)置在水面中央。藍色軌跡是傳統(tǒng)A*算法,綠色軌跡是改進A*算法,在第2組實驗中,調(diào)大時間在代價分析中的權(quán)重,讓機器人以更快的時間到達目標,而較小考慮耗能代價。傳統(tǒng)A*算法規(guī)劃時路徑保持不變。改進A*算法選擇了時間代價更小的路徑,直接從起點飛過障礙物,且中間不再進行狀態(tài)切換,也不再水面上運動,直接飛達目標點。通過分析表2第2組數(shù)據(jù),在當前耗能、時間權(quán)重和環(huán)境下,改進A* 算法規(guī)劃的路徑雖然耗能代價相對比較大,但是運動時間代價明顯小,且綜合代價也更小,有利于機器人完成對運動時間要求比較高的導航任務(wù)。
圖5:第2組實驗軌跡立體圖
圖6是第3組實驗仿真結(jié)果圖。綠色軌跡為能耗、時間權(quán)重分別為0.5,0.5的路徑軌跡,藍色軌跡為能耗、時間權(quán)重分別為0.15,0.85的路徑軌跡。藍色軌跡時間代價權(quán)重較大,因此在面對水環(huán)境時,選擇直接切換至飛行狀態(tài),飛達目標點。而綠色軌跡降低了時間權(quán)重,因此面對水環(huán)境,并沒有直接選擇切換至飛行狀態(tài)并飛達目標點這一時間代價較小的路徑,還是選擇了綜合代價較小的切換至水面狀態(tài),經(jīng)過水面環(huán)境后,切換至陸地狀態(tài)運動一段時間。之后,算法比較了直接飛過障礙物和通過陸地運動繞過障礙的綜合代價,選擇了飛過障礙物這一綜合代價較小的方式。表3數(shù)據(jù)表明,采取不同的權(quán)重,算法規(guī)劃的目標不同,結(jié)果也不一樣。可通過改變權(quán)重來改變規(guī)劃目標。
圖6:第3組實驗軌跡立體圖
表3:第3組實驗(不同權(quán)重的改進算法對比實驗)數(shù)據(jù)
本文研究并探討了三棲機器人的廣闊前景以及現(xiàn)有的路徑規(guī)劃方法的優(yōu)點以及不足之處,在現(xiàn)有學者的只針對陸空環(huán)境的規(guī)劃以及僅在突發(fā)環(huán)境下局部規(guī)劃等研究成果的基礎(chǔ)上,提出了基于運動狀態(tài)以及狀態(tài)切換的耗能分析和時間綜合代價分析的改進三維A*算法,實現(xiàn)三棲機器人的全局路徑規(guī)劃。經(jīng)實驗驗證,改進算法能夠降低機器人運動的綜合代價,且能夠通過改變權(quán)重來使機器人執(zhí)行特定要求下的導航任務(wù),這對多棲機器人運動的研究具有一定的借鑒意義。
此外,對于26鄰域進行搜索會導致算法的時間復雜度較高,可以考慮優(yōu)先對相同環(huán)境屬性或陸地屬性的柵格鄰域進行搜索,提高算法的時間性能。