機(jī)器人技術(shù)在地震廢墟搜索救援中的應(yīng)用?????

?

機(jī)器人技術(shù)在地震廢墟搜索救援中的應(yīng)用?????

戴博，肖曉明，蔡自興

（中南大學(xué)信息科學(xué)與工程學(xué)院，長沙 410083）

摘編自《控制工程》2005年12卷3期：198~202頁，圖、表、參考文獻(xiàn)已省略。

1　引 言

智能移動機(jī)器人是一類能夠通過傳感器感知環(huán)境和自身狀態(tài)，實現(xiàn)在有障礙物的環(huán)境中面向目標(biāo)的自主運動，從而完成一定作業(yè)功能的機(jī)器人系統(tǒng)[1,2]。近年來，移動機(jī)器人技術(shù)在工業(yè)、農(nóng)業(yè)、航天及空間探測等許多領(lǐng)域都起到了重要的作用，同時又顯示了廣泛的應(yīng)用前景，因而成為國際機(jī)器人學(xué)術(shù)界研究和關(guān)注的熱點問題。

在移動機(jī)器人相關(guān)技術(shù)的研究中，導(dǎo)航技術(shù)是其核心，而路徑規(guī)劃是導(dǎo)航研究的一個重要環(huán)節(jié)和課題。所謂路徑規(guī)劃是指移動機(jī)器人按照某一性能指標(biāo)（如距離、時間、能量等）搜索一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或次優(yōu)路徑[3]。路徑規(guī)劃主要涉及的問題包括：利用獲得的移動機(jī)器人環(huán)境信息建立較為合理的模型，再用某種算法尋找一條從起始狀態(tài)到目標(biāo)狀態(tài)的最優(yōu)或近似最優(yōu)的無碰撞路徑；能夠處理環(huán)境模型中的不確定因素和路徑跟蹤中出現(xiàn)的誤差，使外界物體對機(jī)器人的影響降到最??；如何利用已知的所有信息來引導(dǎo)機(jī)器人的動作，從而得到相對更優(yōu)的行為決策。目前，對于移動機(jī)器人路徑規(guī)劃技術(shù)的研究已經(jīng)取得了大量的成果，許多問題獲得了比較滿意的答案。本文將對移動機(jī)器人路徑規(guī)劃的一般方法進(jìn)行分類和較為詳細(xì)的闡述和介紹，并對其發(fā)展趨勢做相關(guān)的陳述。

2　移動機(jī)器人路徑規(guī)劃方法的分類及現(xiàn)狀

從到目前為止的研究來看，移動機(jī)器人路徑規(guī)劃方法主要可以分為以下三種類型：

1）基于事例的學(xué)習(xí)規(guī)劃方法

基于事例的學(xué)習(xí)規(guī)劃方法依靠過去的經(jīng)驗進(jìn)行學(xué)習(xí)及問題求解，一個新的事例可以通過修改事例庫中與當(dāng)前情況相似的舊的事例來獲得[4]。將其應(yīng)用于移動機(jī)器人的路徑規(guī)劃中可以描述為：首先，利用路徑規(guī)劃所用到的或已產(chǎn)生的信息建立一個事例庫，庫中的任一事例包含每一次規(guī)劃時的環(huán)境信息和路徑信息，這些事例可以通過特定的索引取得；隨后，將由當(dāng)前規(guī)劃任務(wù)和環(huán)境信息產(chǎn)生的事例與事例庫中的事例進(jìn)行匹配，以尋找出一個最優(yōu)匹配事例，然后對該事例進(jìn)行修正，并以此作為最后的結(jié)果。

移動機(jī)器人導(dǎo)航需要良好的自適應(yīng)性和穩(wěn)定性，而基于事例的方法能滿足這個需求。Ram[5]將基于事例的在線匹配和增強(qiáng)式學(xué)習(xí)相結(jié)合，提高了機(jī)器人的自適應(yīng)性能，較好地適應(yīng)了環(huán)境的變化。利用基于事例的方法時要注意保持事例庫中的事例數(shù)量，以防止增加機(jī)器人在線規(guī)劃時間或產(chǎn)生信息爆炸問題。Marefat[6]把基于事例的方法作為一個特征輔助規(guī)劃與全局規(guī)劃結(jié)合從而提高了全局規(guī)劃的效率。Kruusmaa[7]通過創(chuàng)建種群事例庫在理論上覆蓋了關(guān)于路徑搜尋問題所有可能的路徑解空間，克服了啟發(fā)式搜索方法在此方面的缺陷。

近年來，自主式水下機(jī)器人[8]（如圖1所示）由于其在海底資源探測上的優(yōu)勢而受到各國的關(guān)注，但因為水下環(huán)境十分復(fù)雜（能見度差、定位困難等），導(dǎo)致一般的規(guī)劃方法都難以奏效，而水下環(huán)境的擁擠程度相對較低、機(jī)器人工作在同一區(qū)域的可能性較大這一特征恰好有利于基于事例的規(guī)劃方法的應(yīng)用，因此該方法被廣泛的用于解決水下機(jī)器人的路徑規(guī)劃問題[9]，試驗證明其效果也較為理想。

2）基于環(huán)境模型的規(guī)劃方法

該方法首先需要建立一個關(guān)于機(jī)器人運動環(huán)境的環(huán)境模型。在很多時候由于移動機(jī)器人的工作環(huán)境具有不確定性（包括非結(jié)構(gòu)性、動態(tài)性等），使得移動機(jī)器人無法建立全局環(huán)境模型，而只能根據(jù)傳感器信息實時地建立局部環(huán)境模型，因此局部模型的實時性、可靠性成為影響移動機(jī)器人是否可以安全、連續(xù)、平穩(wěn)運動的關(guān)鍵。環(huán)境建模的方法基本上可以分為兩類：網(wǎng)絡(luò)?圖建模方法、基于網(wǎng)格的建模方法[10]。前者主要包括自由空間法、頂點圖像法、廣義錐法等，利用它們在進(jìn)行路徑規(guī)劃時可得到比較精確的解，但所耗費的計算量相當(dāng)大，不適合于實際的應(yīng)用。而后者在實現(xiàn)上要簡單許多，所以應(yīng)用比較廣泛，其典型代表就是四叉樹建模法[10]及其擴(kuò)展算法（如基于位置碼四叉樹建模法[11]、Framed quadtrees建模法[12]等）。

基于環(huán)境模型的規(guī)劃方法根據(jù)掌握環(huán)境信息的完整程度可以細(xì)分為環(huán)境信息完全已知的全局路徑規(guī)劃和環(huán)境信息完全未知或部分未知的局部路徑規(guī)劃[3]。由于環(huán)境模型是已知的，全局路徑規(guī)劃的設(shè)計標(biāo)準(zhǔn)是盡量使規(guī)劃的效果達(dá)到最優(yōu)。在此領(lǐng)域已經(jīng)有了許多成熟的方法，包括可視圖法、切線圖法、Voronoi圖法、拓?fù)浞?、懲罰函數(shù)法、柵格法等。前4種方法都是采用基于圖論的思想，將目標(biāo)、機(jī)器人及其工作空間用一個連接圖表示，如此一來，路徑規(guī)劃問題就轉(zhuǎn)化為在圖上尋找一條從起始節(jié)點到目標(biāo)節(jié)點的路線。懲罰函數(shù)法將路徑規(guī)劃這個有約束的問題（受到障礙物的限制）轉(zhuǎn)化為一個無約束最優(yōu)化問題，再求解就可得出解答。柵格法用網(wǎng)格描述機(jī)器人的工作環(huán)境，根據(jù)柵格的可信度值可確定出障礙物的分布，此時通過避障規(guī)劃就可得到無碰路徑。

作為當(dāng)前規(guī)劃研究的熱點問題，局部路徑規(guī)劃得到了深入細(xì)致的研究。對環(huán)境信息完全未知的情況，機(jī)器人沒有任何先驗信息，因此規(guī)劃是以提高機(jī)器人的避障能力為主，而效果作為其次。Koeing等[13]提出了增量式的D*Lite算法，該方法利用啟發(fā)式策略搜索一條從目標(biāo)點指向機(jī)器人當(dāng)前位置的路徑，并在機(jī)器人向目標(biāo)運動過程中根據(jù)局部環(huán)境的更新信息來實時重規(guī)劃路徑，由此得出一條最優(yōu)路徑。在國內(nèi)，張純剛等[14]提出了基于滾動窗口的規(guī)劃方法，也取得了較好的效果。在環(huán)境部分未知時的規(guī)劃方法主要有人工勢場法、模糊邏輯算法、遺傳算法、人工神經(jīng)網(wǎng)絡(luò)、模擬退火算法、蟻群優(yōu)化算法、粒子群算法和啟發(fā)式搜索[15]方法等。前4種方法相對應(yīng)用較廣，后幾種則是近年來才比較流行，其中啟發(fā)式方法的研究取得了較大進(jìn)展。啟發(fā)式方法的最初代表是A*算法[15，16]，而其新發(fā)展是D*[17]和Focussed D*[18]這兩種由Stentz A提出的增量式圖搜索算法（又稱作Dynamic A*算法）的產(chǎn)生。D*算法可以理解為動態(tài)的Dijkstra（最短路徑）算法，而Focussed D*算法則利用了A*算法的主要優(yōu)點即使用啟發(fā)式估價函數(shù)，兩種方法都能根據(jù)機(jī)器人在移動中探測到的新的環(huán)境信息快速地修正和重規(guī)劃出最優(yōu)路徑，減少了局部規(guī)劃的時間，對于在線的實時路徑規(guī)劃有很好的效果。此外，還出現(xiàn)了一些基于A*的改進(jìn)算法[19]，它們一般都是通過修改A*算法中的估價函數(shù)和圖搜索方向而實現(xiàn)的，可以較大地提高路徑規(guī)劃的速度，具有一定的復(fù)雜環(huán)境自適應(yīng)能力。

基于環(huán)境模型的方法由于其規(guī)劃的精確性和平穩(wěn)性應(yīng)用在很多領(lǐng)域特別是在宇宙空間探測中，美國于1996年12月發(fā)射了“火星探路者”探測器，并用所攜帶的“索杰納”火星車（如圖2所示）對火星進(jìn)行了實地考察，獲得了很大的成功。索杰納所采用路徑規(guī)劃方法就是D*算法，它使索杰納能在火星表面自如而謹(jǐn)慎地行走，且能自主判斷出前進(jìn)道路上的障礙物，并通過實時重規(guī)劃來作出后面行動的決策，真正做到了“三思而后行”。

3）基于行為的路徑規(guī)劃方法

基于行為的方法由Brooks在他著名的包容式結(jié)構(gòu)[20]中建立，它是一門從生物系統(tǒng)收到啟發(fā)而產(chǎn)生的用來設(shè)計自主機(jī)器人的技術(shù)，它采用類似動物進(jìn)化的自底向上的原理體系，嘗試從簡單的智能體來建立一個復(fù)雜的系統(tǒng)。將其用于解決移動機(jī)器人路徑規(guī)劃問題是一種新的發(fā)展趨勢，它把導(dǎo)航問題分解為許多相對獨立的行為單元，比如跟蹤、避碰、目標(biāo)制導(dǎo)等。這些行為單元是一些由傳感器和執(zhí)行器組成的完整的運動控制單元，具有相應(yīng)的導(dǎo)航功能，各行為單元所采用的行為方式各不相同，這些單元通過相互協(xié)調(diào)工作來完成導(dǎo)航任務(wù)。

基于行為的方法大體可以分為反射式行為、反應(yīng)式行為、慎思行為3種類型。反射式行為類似于青蛙的膝跳反射，是一種瞬間的應(yīng)激性本能反應(yīng)，它可以對突發(fā)性情況作出迅速反應(yīng)，如移動機(jī)器人在運動中緊急停止等，但該方法不具備智能性，一般是與其他方法結(jié)合使用?；诜磻?yīng)式行為的方法是由Brooks最先提出，它直接讀取傳感器數(shù)據(jù)來規(guī)劃下一步的動作，可以穩(wěn)定及時地對不可預(yù)知的障礙和環(huán)境變化作出反應(yīng)，但由于缺乏全局環(huán)境知識，因此所產(chǎn)生的動作序列可能不是全局最優(yōu)的，不適合于復(fù)雜環(huán)境下移動機(jī)器人的路徑規(guī)劃，機(jī)器人的沿墻走行為策略是其典型的代表。慎思行為利用已知的全局環(huán)境模型為智能體系統(tǒng)到達(dá)某個特定目標(biāo)提供最優(yōu)動作序列，適合于復(fù)雜靜態(tài)環(huán)境下的規(guī)劃，移動機(jī)器人在運動中的實時重規(guī)劃就是一種慎思行為，機(jī)器人可能出現(xiàn)倒退的動作以走出危險區(qū)域，但由于慎思規(guī)劃需要一定的時間去執(zhí)行，所以它對于環(huán)境中不可預(yù)知的改變反應(yīng)較慢。反應(yīng)式行為、慎思行為可以通過傳感器數(shù)據(jù)、全局知識、反應(yīng)速度、推理論證能力和計算的復(fù)雜性這幾方面來加以區(qū)分。近來，在慎思行為的發(fā)展中出現(xiàn)了一種類似于人的大腦記憶的陳述性認(rèn)知行為[21]，基于此的規(guī)劃不僅僅依靠傳感器和已有的先驗信息，還取決于所要到達(dá)的目標(biāo)。比如對于距離較遠(yuǎn)且暫時不可見的目標(biāo)，有可能存在一個行為分叉點，即有幾種行為可供采用，機(jī)器人要擇優(yōu)選擇，這種決策性行為就是陳述性認(rèn)知行為。將它用于路徑規(guī)劃中能使移動機(jī)器人具有更高的智能，但由于決策的復(fù)雜性，該方法難以用于實際之中，這方面工作還有待進(jìn)一步研究。

基于行為的方法在中智能家庭等商業(yè)領(lǐng)域受到了許多研究人員的青睞，劉瑜等[22,23]成功地研制出兩代自主智能吸塵機(jī)器人樣機(jī)（如圖3所示），將基于行為的思想引入機(jī)器人的作業(yè)規(guī)劃中，提高了規(guī)劃的效率和對環(huán)境的適應(yīng)度，具有良好的應(yīng)用前景。

3　移動機(jī)器人路徑規(guī)劃方法新的發(fā)展趨勢

隨著移動機(jī)器人應(yīng)用范圍的擴(kuò)大，對于規(guī)劃技術(shù)的要求也越來越高，單個規(guī)劃方法有時不能很好地解決某些規(guī)劃問題，所以新的發(fā)展趨向于將多種方法相結(jié)合，對此可從以下幾方面進(jìn)行探討。

1）基于反應(yīng)式行為規(guī)劃與基于慎思行為規(guī)劃的結(jié)合 基于反應(yīng)式行為的規(guī)劃方法在能建立靜態(tài)環(huán)境模型的前提下可取得不錯的規(guī)劃效果，但它不適合于環(huán)境中存在一些非模型障礙物（如桌子、人等）的情況。為此，一些學(xué)者提出了混合控制的結(jié)構(gòu)，即將慎思行為與反應(yīng)式行為相結(jié)合，可以較好地解決這種類型的問題。Low[24]將結(jié)合兩者的混合控制結(jié)構(gòu)運用在不可預(yù)知環(huán)境下的避撞導(dǎo)航，各個行為模塊之間是異步運行的，與一般的控制結(jié)構(gòu)相比，其規(guī)劃模塊得出的是一系列的點集而不是一條完整的路徑，反應(yīng)式模塊具有避碰和目標(biāo)制導(dǎo)的雙重功能。Gat[25]提出了著名的三層控制結(jié)構(gòu)，包括控制層、序列層、慎思層，控制層利用反應(yīng)式行為迅速地感應(yīng)環(huán)境，慎思層主要進(jìn)行路徑規(guī)劃等處理過程，序列層用于連接以上2層。該結(jié)構(gòu)保證了機(jī)器人在時間上對環(huán)境的準(zhǔn)確把握。Hassan[26]也提出了一種實時的混合控制結(jié)構(gòu)，能在有限的時間內(nèi)選擇合理的執(zhí)行動作，并能根據(jù)環(huán)境信息來調(diào)節(jié)機(jī)器人的行為，具有較強(qiáng)的靈活性，有效地解決了有限可用時間與慎思行為需要消耗一定時間之間的矛盾，滿足了反應(yīng)式行為的變化要求。

2）全局路徑規(guī)劃與局部路徑規(guī)劃的結(jié)合 全局規(guī)劃一般是建立在已知環(huán)境信息的基礎(chǔ)上，適應(yīng)范圍相對有限；局部規(guī)劃能適用于環(huán)境未知的情況，但有時反應(yīng)速度不快，對規(guī)劃系統(tǒng)品質(zhì)的要求較高，因此如果把兩者結(jié)合就可以達(dá)到更好的規(guī)劃效果。Guldner[27]提出了三層控制結(jié)構(gòu)，以全局規(guī)劃作為最高層，采用勢場方法的局部規(guī)劃為第二層，最底層用航向角方法（Steer Angle Field Approach）來進(jìn)行避障，適合于雜亂環(huán)境中的路徑規(guī)劃。Dieguez[28]提出了一種新的多級結(jié)構(gòu)，包括全局規(guī)劃、局部規(guī)劃、智能監(jiān)督、傳感器信息融合、路徑選擇和導(dǎo)航6個層次，其中局部規(guī)劃層還可以分為局部路徑計算和路徑優(yōu)化兩部分，該方法能有效地利用局部規(guī)劃時間從而得出相對更好的路徑。

3）傳統(tǒng)規(guī)劃方法與新的智能方法之間的結(jié)合 近年來，一些新的智能技術(shù)逐漸被引入到路徑規(guī)劃中來，也促使了各種方法的融合發(fā)展，例如人工勢場與神經(jīng)網(wǎng)絡(luò)、模糊控制的結(jié)合等。Kyun[29]的混合控制結(jié)構(gòu)先用神經(jīng)網(wǎng)絡(luò)對環(huán)境進(jìn)行分類以避免陷入局部最小，并建立基于反應(yīng)式行為的控制器，再根據(jù)勢場法選擇一個特定的反應(yīng)式行為來引導(dǎo)移動機(jī)器人前進(jìn)，該結(jié)構(gòu)有較好的魯棒穩(wěn)定性，對動態(tài)環(huán)境具有一定的適應(yīng)性。Mbede[30]設(shè)計了一種融合了模糊邏輯和人工勢場函數(shù)的模糊控制器，解決了已知環(huán)境中存在未知動態(tài)障礙的規(guī)劃問題，較大地提高了運動規(guī)劃的效率，適合于實時應(yīng)用。Wu[31]先利用人工勢場法引導(dǎo)移動機(jī)器人向目標(biāo)前進(jìn)，再采用模糊邏輯的方法使機(jī)器人能走出勢能陷阱并產(chǎn)生一條平坦而安全的路徑，實驗結(jié)果證明了該方法具有可行性。

4　結(jié)語

總結(jié)目前的研究可以看出：第一，許多路徑規(guī)劃方法在完全已知環(huán)境中能得到令人滿意的結(jié)果，但在未知環(huán)境特別是存在各種不規(guī)則障礙的復(fù)雜環(huán)境中，卻很可能失去效用。所以如何快速有效地完成移動機(jī)器人在復(fù)雜環(huán)境中的導(dǎo)航任務(wù)仍將是今后研究的主要方向之一。第二，對于各種規(guī)劃方法的改進(jìn)有這樣一個趨勢——從對某一種方法的局部修改轉(zhuǎn)向把某幾種方法相互結(jié)合。因此怎樣把各種方法的優(yōu)點融合到一起以達(dá)到更好的效果也是一個有待探討的問題。第三，目前大多數(shù)規(guī)劃方法都只針對固定目標(biāo)點而沒有考慮移動目標(biāo)點（如足球機(jī)器人比賽中的足球）的情況，此時的規(guī)劃由于要考慮機(jī)器人、目標(biāo)的位置信息和速度信息而更加復(fù)雜，這方面研究也是今后發(fā)展的重點。此外，多智能機(jī)器人系統(tǒng)（MARS）[32]（如足球機(jī)器人）作為一項新的智能技術(shù)逐漸成為關(guān)注熱點，它是在單體智能機(jī)器發(fā)展到需要協(xié)調(diào)作業(yè)的條件下產(chǎn)生的，其規(guī)劃的難點在于多機(jī)器人的協(xié)調(diào)和避碰前進(jìn)，這也將是移動機(jī)器人技術(shù)急需拓展的領(lǐng)域。