移動(dòng)機(jī)器人路徑規(guī)劃的現(xiàn)狀和發(fā)展

房亞群

摘要 移動(dòng)機(jī)器人路徑規(guī)劃是移動(dòng)機(jī)器人導(dǎo)航的核心技術(shù)之一。移動(dòng)規(guī)劃技術(shù)涌現(xiàn)出了許多規(guī)劃方法。本文總結(jié)了機(jī)器人發(fā)展史上具有典型意義的規(guī)劃方法,探討了幾種路徑規(guī)劃方法,并對(duì)其發(fā)展進(jìn)行了展望。

關(guān)鍵詞 路徑規(guī)劃;全局規(guī)劃;局部規(guī)劃

中圖分類號(hào) TP242 文獻(xiàn)標(biāo)識(shí)碼 A 文章編號(hào) 1674-6708(2009)10-0067-02

路徑規(guī)劃是指機(jī)器人從起始點(diǎn)到目標(biāo)點(diǎn)之間找到一條安全無(wú)碰的路徑,是機(jī)器人領(lǐng)域的重要課題。移動(dòng)機(jī)器人技術(shù)研究中的一個(gè)重要領(lǐng)域是路徑規(guī)劃技術(shù),它分為基于模型的環(huán)境已知的全局路徑規(guī)劃和基于傳感器的環(huán)境未知的局部路徑規(guī)劃。本文綜述了移動(dòng)機(jī)器人路徑規(guī)劃的發(fā)展?fàn)顩r,對(duì)移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的發(fā)展趨勢(shì)進(jìn)行了展望。

根據(jù)機(jī)器人工作環(huán)境路徑規(guī)劃模型可分為兩種:基于模型的全局路徑規(guī)劃,這種情況的作業(yè)環(huán)境的全部信息為已知;基于傳感器的局部路徑規(guī)劃,作業(yè)環(huán)境信息全部未知或部分未知,又稱動(dòng)態(tài)或在線路徑規(guī)劃。

1 全局路徑規(guī)劃

全局路徑規(guī)劃主要方法有:可視圖法、自由空間法、柵格法、拓?fù)浞ā⑸窠?jīng)網(wǎng)絡(luò)法等。

1.1 可視圖法

可視圖法視移動(dòng)機(jī)器人為一點(diǎn),將機(jī)器人、目標(biāo)點(diǎn)和多邊形障礙物的各頂點(diǎn)進(jìn)行組合連接,并保證這些直線均不與障礙物相交,這就形成了一張圖,稱為可視圖。由于任意兩直線的頂點(diǎn)都是可見的,從起點(diǎn)沿著這些直線到達(dá)目標(biāo)點(diǎn)的所有路徑均是運(yùn)動(dòng)物體的無(wú)碰路徑。搜索最優(yōu)路徑的問題就轉(zhuǎn)化為從起點(diǎn)到目標(biāo)點(diǎn)經(jīng)過這些可視直線的最短距離問題。

1.2 拓?fù)浞?/p>

拓?fù)浞▽⒁?guī)劃空間分割成具有拓?fù)涮卣鞯淖涌臻g,根據(jù)彼此連通性建立拓?fù)渚W(wǎng)絡(luò),在網(wǎng)絡(luò)上尋找起始點(diǎn)到目標(biāo)點(diǎn)的拓?fù)渎窂?最終由拓?fù)渎窂角蟪鰩缀温窂健Ｍ負(fù)浞ɑ舅枷胧墙稻S法,即將在高維幾何空間中求路徑的問題轉(zhuǎn)化為低維拓?fù)淇臻g中判別連通性的問題。

1.3 柵格法

柵格法將移動(dòng)機(jī)器人工作環(huán)境分解成一系列具有二值信息的網(wǎng)格單元,多采用四叉樹或八叉樹表示,并通過優(yōu)化算法完成路徑搜索,該法以柵格為單位記錄環(huán)境信息,有障礙物的地方累積值比較高,移動(dòng)機(jī)器人就會(huì)采用優(yōu)化算法避開。對(duì)柵格的改進(jìn)采用以障礙物為單位記錄的信息量大大減少,克服了柵格法中環(huán)境存儲(chǔ)量大的問題。

1.4 自由空間法

自由空間法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃,采用預(yù)先定義的如廣義錐形和凸多邊形等基本形狀構(gòu)造自由空間,并將自由空間表示為連通圖,通過搜索連通圖來進(jìn)行路徑規(guī)劃。自由空間的構(gòu)造方法是從障礙物的一個(gè)頂點(diǎn)開始,依次作其它頂點(diǎn)的鏈接線,刪除不必要的鏈接線,使得鏈接線與障礙物邊界所圍成的每一個(gè)自由空間都是面積最大的凸多邊形。連接各鏈接線的中點(diǎn)形成的網(wǎng)絡(luò)圖即為機(jī)器人可自由運(yùn)動(dòng)的路線。

1.5 神經(jīng)網(wǎng)絡(luò)法

可視圖法缺乏靈活性,且不適用于圓形障礙物的路徑規(guī)劃問題。神經(jīng)網(wǎng)絡(luò)法用于全局路徑規(guī)劃可以解決以上問題。算法定義了整條路徑的總能量函數(shù),相應(yīng)于路徑長(zhǎng)度部分的能量和相應(yīng)于碰撞函數(shù)部分的能量。由于整個(gè)能量是各個(gè)路徑點(diǎn)函數(shù),因此通過移動(dòng)每個(gè)路徑點(diǎn),使其朝著能量減少的方向運(yùn)動(dòng),最終便能獲得總能量最小的路徑。

2 局部路徑規(guī)劃

局部路徑規(guī)劃包括人工勢(shì)場(chǎng)法、模糊邏輯算法、神經(jīng)網(wǎng)絡(luò)法、遺傳算法等。

2.1 人工勢(shì)場(chǎng)法

人工勢(shì)場(chǎng)法基本思想是將移動(dòng)機(jī)器人在環(huán)境中的運(yùn)動(dòng)視為一種虛擬人工受力場(chǎng)中的運(yùn)動(dòng)。障礙物對(duì)移動(dòng)機(jī)器人產(chǎn)生斥力,目標(biāo)點(diǎn)產(chǎn)生引力,引力和斥力周圍由一定的算法產(chǎn)生相應(yīng)的勢(shì),機(jī)器人在勢(shì)場(chǎng)中受到抽象力作用,抽象力使得機(jī)器人繞過障礙物。

2.2 模糊邏輯算法

模糊邏輯算法基于對(duì)駕駛員的工作過程觀察研究得出。駕駛員避碰動(dòng)作并非對(duì)環(huán)境信息精確計(jì)算完成的,而是根據(jù)模糊的環(huán)境信息,通過查表得到規(guī)劃出的信息,完成局部路徑規(guī)劃。模糊邏輯算法的優(yōu)點(diǎn)是克服了勢(shì)場(chǎng)法易產(chǎn)生的局部極小問題,對(duì)處理未知環(huán)境下的規(guī)劃問題顯示出很大優(yōu)越性,對(duì)于解決用通常的定量方法來說是很復(fù)雜的問題或當(dāng)外界只能提供定性近似的、不確定信息數(shù)據(jù)時(shí)非常有效。

2.3 神經(jīng)網(wǎng)絡(luò)法

模糊控制算法有諸多優(yōu)點(diǎn),但也有固有缺陷:人的經(jīng)驗(yàn)不一定完備;輸入量增多時(shí),推理規(guī)則或模糊表會(huì)急劇膨脹。神經(jīng)網(wǎng)絡(luò)法則另辟蹊徑。路徑規(guī)劃是感知空間行為空間的一種映射,映射關(guān)系可用不同方法實(shí)現(xiàn),很難用精確數(shù)學(xué)方程表示,但采用神經(jīng)網(wǎng)絡(luò)易于表示,將傳感器數(shù)據(jù)作為網(wǎng)絡(luò)輸入,由人給定相應(yīng)場(chǎng)合下期望運(yùn)動(dòng)方向角增量作為網(wǎng)絡(luò)輸出,由多個(gè)選定位姿下的一組數(shù)據(jù)構(gòu)成原始樣本集,經(jīng)過剔除重復(fù)或沖突樣本等加工處理,得到最終樣本集。

2.4 遺傳算法

遺傳算法以自然遺傳機(jī)制和自然選擇等生物進(jìn)化理論為基礎(chǔ),構(gòu)造了一類隨機(jī)化搜索算法。利用選擇、交叉和變異編制控制機(jī)構(gòu)的計(jì)算程序,在某種程度上對(duì)生物進(jìn)化過程作數(shù)學(xué)方式的模擬,只要求適應(yīng)度函數(shù)為正,不要求可導(dǎo)或連續(xù),同時(shí)作為并行算法,其隱并行性適用于全局搜索。多數(shù)優(yōu)化算法都是單點(diǎn)搜索,易于陷入局部最優(yōu),而遺傳算法卻是一種多點(diǎn)搜索算法,故更有可能搜索到全局最優(yōu)解。

3 移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)的發(fā)展展望

隨著計(jì)算機(jī)、傳感器及控制技術(shù)的發(fā)展,特別是各種新算法不斷涌現(xiàn),移動(dòng)機(jī)器人路徑規(guī)劃技術(shù)已經(jīng)取得了豐碩研究成果。從研究成果看,有以下趨勢(shì):首先,移動(dòng)機(jī)器人路徑規(guī)劃的性能指標(biāo)要求不斷提高,這些性能指標(biāo)包括實(shí)時(shí)性、安全性和可達(dá)性等;其次,多移動(dòng)機(jī)器人系統(tǒng)的路徑規(guī)劃。協(xié)調(diào)路徑規(guī)劃已成為新的研究熱點(diǎn)。隨著應(yīng)用不斷擴(kuò)大,移動(dòng)機(jī)器人工作環(huán)境復(fù)雜度和任務(wù)的加重,對(duì)其要求不再局限于單臺(tái)移動(dòng)機(jī)器人。在動(dòng)態(tài)環(huán)境中多移動(dòng)機(jī)器人的合作與單個(gè)機(jī)器人路徑規(guī)劃要很好地統(tǒng)一;再次,多傳感器信息融合用于路徑規(guī)劃。移動(dòng)機(jī)器人在動(dòng)態(tài)環(huán)境中進(jìn)行路徑規(guī)劃所需信息都是從傳感器得來。單傳感器難以保證輸入信息準(zhǔn)確與可靠。此外基于功能/行為的移動(dòng)機(jī)器人路徑規(guī)劃,這是研究的新動(dòng)向之一。

總之,移動(dòng)機(jī)器人的路徑規(guī)劃技術(shù)已經(jīng)取得了豐碩成果,但各種方法各有優(yōu)缺點(diǎn),也沒有一種方法能適用于任何場(chǎng)合。在研究這一領(lǐng)域時(shí),要結(jié)合以前的研究成果,把握發(fā)展趨勢(shì),以實(shí)用性作為最終目的,這樣就能不斷推動(dòng)其向前發(fā)展。

參考文獻(xiàn)

[1]陳陳.優(yōu)化方法與最優(yōu)控制[M].北京:機(jī)械工業(yè)出版社,1993.

[2]孫增圻.智能控制理論與技術(shù)[M].北京:清華大學(xué)出版社,1997.

[3]禹建麗,等.一種快速神經(jīng)網(wǎng)絡(luò)路徑規(guī)劃算法[J].機(jī)器人,2001,23(3):201-205.