李辰豪 吳啟來 郭晟男

（南京理工大學 江蘇省南京市 210094）

1 引言

目前，國內(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ī)劃目標。

2 基于狀態(tài)切換和代價分析的改進三維A*算法

2.1 傳統(tǒng)A*算法

A*算法是一種在全局靜態(tài)地圖中對最短路徑進行求解和規(guī)劃的最有效的直接搜索方法，也是解決許多其他問題時常用的啟發(fā)式算法，有著較好的性能和準確度。公式表示為：

傳統(tǒng)的A*算法沒有將機器人運動時不同運動狀態(tài)之間相互切換的耗能代價以及在不同環(huán)境運動的時間、耗能代價考慮進去。只把所求解的路徑長度作為規(guī)劃目標，然而，在實際中，多棲機器人的路徑規(guī)劃、運動要考慮諸如耗能、時間等因素，以達到任務(wù)對機器人運動的時間和耗能要求。而本文提出的改進算法將對這一問題進行優(yōu)化解決。

2.2 搜索鄰域簡介

在二維環(huán)境下，A*算法只需拓展當前節(jié)點的8個子節(jié)點，而三維環(huán)境下，需拓展26個子節(jié)點。

2.3 三棲機器人狀態(tài)切換的代價分析

三棲機器人的水、陸、空自主切換控制狀態(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)切換能耗。

2.4 多目標啟發(fā)式函數(shù)設(shè)計

當三棲機器人在現(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ù)計算公式為：

3 仿真環(huán)境搭建

本文采用三維柵格地圖對三棲環(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組實驗軌跡俯視圖

4 算法驗證與分析

在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ù)

5 結(jié)語

本文研究并探討了三棲機器人的廣闊前景以及現(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)境屬性或陸地屬性的柵格鄰域進行搜索，提高算法的時間性能。