移動機器人路徑規(guī)劃算法研究綜述

趙鑫

（內(nèi)蒙古工業(yè)大學，內(nèi)蒙古 呼和浩特 010000）

0 引言

近年來，對于移動機器人的研究越來越廣泛，目前在綜合了各個學科的技術(shù)，在各個行業(yè)得到廣泛的應(yīng)用。機器人作為一種新型工具，它的出現(xiàn)為人們帶來了很大的好處，例如在很大程度上減輕勞動壓力，改善環(huán)境，促進機器人路徑規(guī)劃的實行是一個關(guān)鍵的環(huán)節(jié)，移動機器人涉及很多的重要技術(shù)，他被創(chuàng)造出來的好壞優(yōu)劣直接關(guān)乎機器人的智能水平。所以按照兩種路徑進行規(guī)劃，增強機器人的科技能力，促進我國科技的發(fā)展，加快我國科技進程具有重大意義。

所謂移動機器人路徑規(guī)劃，指的是各種傳感器對機器人自身的影響，依照環(huán)境的感知，通過一個或多個評判標準規(guī)劃安全的運行路線，尋找出一條機器人能從從起始點運動到目標點的最佳路線。在規(guī)劃中根據(jù)機器人功能用一定的算法計算機器人繞過某些必要的障礙物所需要完成的時間和效率，上述講到可以將計算機路徑規(guī)劃分為全局和局部路徑。全局路徑和局部路徑各有各的優(yōu)勢，我們要在此基礎(chǔ)上，在機器人繞開障礙物的同時也要盡量選擇最優(yōu)路線。

1 關(guān)于路徑規(guī)劃的算法研究

路徑規(guī)劃是最重要的研究移動機器人的技術(shù)研發(fā)的技術(shù)，在了解周圍的環(huán)境之后，移動機器人的路徑規(guī)劃大多是根據(jù)指標，在所在的環(huán)境中選擇出從起始點到終點的最好或最壞的無碰撞的路徑。最終所要得到的結(jié)果是在相對應(yīng)的條件下得到可以解決問題的方法。路徑規(guī)劃的結(jié)果會對移動機器人的研究產(chǎn)生極大的影響。機器人路徑規(guī)劃研究從開始到現(xiàn)在已經(jīng)取得了一部分的成就，但是就相對來講這些還遠遠是不夠的。從研究的環(huán)境來看，路徑規(guī)劃可分為全局或局部規(guī)劃。根據(jù)路徑規(guī)劃分類的研究，全局規(guī)劃路徑在于全面解決環(huán)境的規(guī)劃問題，二局部規(guī)劃可以說重點是在表示對未知或者已經(jīng)知道的部分路徑問題。我們可以依據(jù)移動機器人在工作中環(huán)境的復(fù)雜性，將機器人路徑的兩種分類更加細致的介紹。因為局部路徑規(guī)劃的不確定性，所以具有很高的靈活性，在工作中根據(jù)環(huán)境去調(diào)整。但因為是局部環(huán)境特征，所以路徑只能代表局部最優(yōu)。全局路徑規(guī)劃是在整體的環(huán)境下在環(huán)境尋找最優(yōu)路徑，最終引導(dǎo)路徑從起始點到最終點所成為的是最優(yōu)路徑[1-4]。

1.1 全局路徑規(guī)劃及算法

1.1.1 圖搜索類法

圖搜索算法基于各種算法，其中有代表性的是A*算法，以移動機器人作為關(guān)鍵部分，將機器人和障礙物在移動過程中看做各種有目標的關(guān)鍵點，在機器人繞障礙物的時候?qū)⑺渣c成線，以線成面，將其構(gòu)成一個圖，這個圖被叫做可視圖。因為可視圖的目標點是可以看見的，從一個點到另一個點需設(shè)置成清晰可見的兩個頂點。圖搜索就會變成像數(shù)學問題中求最短路線的問題，從起點到目標點最短的距離。通過優(yōu)化算法，刪除不必要的連線，簡化可視圖，縮短搜索時間。該方法可以算出最優(yōu)的距離，可以準確計算使機器人靠近障礙物時迅速的閃躲[5]。

1.1.2 A*算法

A*算法在說圖搜索法的時候講到過，它相對來講最有效求解最短路徑的方法它通過控制實驗使其走過從開始到結(jié)束的所有設(shè)立的點，然后通過數(shù)據(jù)計算選擇一個最短的路徑作為移動機器人的路徑，它通過這種方法進行進一步的探索研究，一次次的找出最短和最長的路徑[6-7]。其中很多前輩都用自己獨特的方法做這種實驗，具有代表性的有王中玉和李強，像李強就是一個目標向另一個目標的節(jié)點性擴展，有效減少了實驗過程的繁瑣問題，提高了實驗的效率。

1.1.3 智能仿生算法

智能仿生算法是模模仿自然界中動物進化或者有些昆蟲覓食捕獵的行為，利用動物的方法來解決研究中的各項問題。其中包括蟻群算法和粒子群算法等。

蟻群算法是受自然界中螞蟻覓食這種行為啟發(fā)而產(chǎn)生的算法，這種方法也叫ACA，最早在1991年提出，他們發(fā)現(xiàn)螞蟻在覓食的過程中，通過分泌一種叫做信息素的東西，會在已走過的道路上留下痕跡螞蟻走的越多，留下來的信息素就會越多，后來再次覓食的螞蟻就會根據(jù)信息素來確定自己要走的路線，搜索信息素濃度最高的最短路徑，這樣最優(yōu)路徑就會被選出來了。根據(jù)文獻中對于這種信息的分析，全局路徑在螞蟻群法中會被根據(jù)螞蟻數(shù)量，期望啟發(fā)因子和信息素的數(shù)量做影響我們要根據(jù)所有可能出現(xiàn)新的問題的方向，考慮各種因素，通過移動機器人規(guī)劃路徑，使路徑快速準確的收斂于最優(yōu)路徑，從信息素改進，提高算法的收斂速度和螞蟻的搜索效率。

1.2 局部路徑規(guī)劃及算法

1.2.1 模擬退火算法

這是目前來看較為有效的解決組合優(yōu)化問題時的算法。這種通過研究金屬熱在算法中被處理時的有效退火，在開始的時候控制金屬環(huán)溫度的有效降低，在發(fā)生突變事件時，有效進行隨機搜索，在出現(xiàn)狀況的同時簡單收集數(shù)據(jù)。模擬退火算法的優(yōu)勢是簡單有效，控制的數(shù)據(jù)相對較少，具有彈性等，但同時也會出現(xiàn)概率性，發(fā)生速度慢等問題。通過模擬退火法進行局部路徑規(guī)劃可以進行簡單的促使路徑脫離原始路徑，發(fā)現(xiàn)新的跳躍的目標點，最終達到自己所要找的最優(yōu)路徑。

1.2.2 人工勢場法。

人工勢場是將機器人所在的環(huán)境路徑規(guī)劃，做成人工場中的運動，這是一種抽象的人造受力場，通過目標點對機器人產(chǎn)生的“引力”以及障礙物產(chǎn)生的“斥力”來移動機器人的運動輸出，還有在各種環(huán)境下產(chǎn)生的合力來確定機器人的輸出。這種方式的優(yōu)點是結(jié)構(gòu)簡單，便于底層的實時控制，規(guī)劃出來的路徑一般是比較平滑并且安全，但仍存在局部最優(yōu)和易在狹窄通道中動蕩的缺點。當環(huán)境的要求比較過的時候，它的虛擬合力便會成為零，這就會進一步導(dǎo)致機器人不能繼續(xù)執(zhí)行任務(wù)[8]。利用人工勢場啟發(fā)函數(shù)，實現(xiàn)全局最優(yōu)，避免局部最優(yōu)。針對人工勢場法存在的缺陷，引入斥力模型，在路徑規(guī)劃時機器人便可以避開局部極小點，進一步優(yōu)化路徑規(guī)劃中的問題。

2 展望

從移動機器人路徑規(guī)劃的發(fā)現(xiàn)狀以及研究需求看，未來移動機器人的路徑規(guī)劃研究主要集中在以下四個方面。

（1）現(xiàn)有算法的改進。雖然關(guān)于路徑規(guī)劃算法很多，并且取得很多成果，但是每種算法都有自己的局限性，不能很好地適應(yīng)更復(fù)雜的環(huán)境，因此對算法進行不斷的創(chuàng)新改進儼然成為了一個成本相對較低突破點;

（2）多機器人協(xié)同路徑的研究。隨著機器人工作環(huán)境的不斷擴大、任務(wù)的復(fù)雜度的增加以及應(yīng)用范圍的擴大，系統(tǒng)需根據(jù)環(huán)境和任務(wù)在保證成員之間相互交換信息的前提下高效、快速、準確地組織多個機器人協(xié)同并行的完成多個任務(wù)。

（3）新路徑規(guī)劃算法的研究。隨著科技的發(fā)展，尋找更新更優(yōu)的路徑規(guī)劃算法解決復(fù)雜的路徑規(guī)劃問題將會成為一種趨勢[9]。比如近幾年興起的深度學習、強化學習等或是未來新的仿生算法的出現(xiàn)。

（4）路徑規(guī)劃算法的有效結(jié)合。任何的單一路徑規(guī)劃算法都不可能解決所有實際應(yīng)用中的路徑規(guī)劃問題，特別是面對復(fù)雜環(huán)境下的任務(wù)，加之研究新算法的難度較大，將出現(xiàn)更多的相互結(jié)合的路徑規(guī)劃算法來彌補彼此的不足。

3 總結(jié)

本文通過對全局和局部路徑規(guī)劃兩類算法所對應(yīng)的常用算法的發(fā)展現(xiàn)狀和優(yōu)缺點進行分析和歸納，從過去的研究狀況和機器人未來的發(fā)展需求來看，目前移動機器人路徑規(guī)劃技術(shù)研究主要集中在以下幾個方面：（1）新的路徑方法的研究；（2）機器人底層控制與路徑規(guī)劃算法的結(jié)合研究；（3）多機器人任務(wù)分配、通信協(xié)作及路徑規(guī)劃的研究。指出了路徑規(guī)劃算法未來的研究方向。隨著科技的發(fā)展，路徑規(guī)劃技術(shù)將會在更多的領(lǐng)域得到應(yīng)用，并且將深入到我們生活的方方面面。