智能算法在機器人路徑規劃中的應用研究

摘要：移動機器人技術研究中的一個重要領域是路徑規劃技術。綜述了智能算法在移動機器人路徑規劃技術中的發展現狀，指出了各種方法的優點與不足。最后對移動機器人路徑規劃技術的發展趨勢進行了展望。

關鍵詞：機器人路徑規劃；智能算法；遺傳算法；蟻群優化算法；粒子群優化

中圖分類號：TP18文獻標識碼：A文章編號：1009-3044(2008)36-2733-02

Research for Robot Path Planning Using Intelligent Algorithms

JIANG Zhi-jian， XU Xiao-mei

(Teaching Department of Modern Education Technology， Ludong University， Yantai 264025， China)

Abstract: Mobile robot path planning technology is one of the important domains in mobile robot technologies research. Present situation of mobile robot is summarized. In addition， the advantages and disadvantages of these algorithms are pointed out. At last， the trend of mobile robot path planning is described.

Key words: robot path planning; intelligent algorithm; genetic algorithm; ant colony optimization algorithm; particle swarm optimization

1 引言

智能移動機器人是一類能夠通過傳感器感知環境和自身狀態，實現在有障礙物的環境中向目標的自主運動，從而完成一定作業功能的機器人系統。近年來，移動機器人技術在工業、農業、航天及空間探測等許多領域都起到了重要的作用，同時又顯示了廣泛的應用前景，因而成為國際機器人學術界研究和關注的熱點問題。在移動機器人相關技術的研究中，導航技術是其核心，而路徑規劃是導航研究的一個重要環節和課題。本文系統地討論智能算法在路徑規劃技術研究中的應用現狀與發展趨勢。

移動機器人路徑規劃是指在有障礙物的工作環境中，如何尋找一條從給定起點到終點較優的運動路徑，使機器人在運動過程中能安全、無碰地繞過所有障礙物。路徑規劃主要解決三個問題：1)使機器人能從初始點運動到目標點；2)用一定的算法使機器人能繞開障礙物，并且經過某些必須經過的點；3)在完成以上任務的前提下，盡量優化機器人運行軌跡。

近年來，智能算法不斷涌現。智能化方法能模擬人的經驗，逼近非線性，具有自組織、自學習功能并且具有一定的容錯能力。這些方法應用于路徑規劃會使移動機器人在動態環境中更靈活，更具智能化。

2 基于遺傳算法的機器人路徑規劃

遺傳算法是一種借鑒生物界自然選擇和進化機制發展起來的高度并行、隨機、自適應搜索算法。由于其思想簡單、易于實現以及表現出來的健壯性，遺傳算法贏得了許多學者的青睞，特別是近年來在問題求解、優化和搜索、機器學習、智能控制、模式識別和人工生命等領域取得了許多令人鼓舞的成就。

根據遺傳算法的流程將其應用于路徑規劃所需解決的問題如下：環境表示、路徑編碼、構造適應度函數、構造選擇算子、構造交叉算子和構造變異算子。針對上述問題所提出的不同解決辦法構成了大量的基于遺傳算法的路徑規劃算法解決方案。目前針對這些問題的解決方法概述如下：

環境表示的解決方法：因為遺傳算法要對路徑進行編碼，因此環境表示的方法將直接影響到路徑的表示。一般而言可以將原始環境表示為柵格，即采用柵格法建模或者將環境劃分為若干(凸)多邊形區域，建立“緊湊”區域圖，區域的權表示機器人在區域內行走單位距離所需代價；也可以如文獻直接用二維笛卡兒坐標表示環境，還可以事先對環境做結構化處理，將環境中可行區域用自由鏈接圖表示，這樣整個環境就可以用鏈接圖中的各個鏈接點來表示。

路徑編碼的解決方法：經典的遺傳算法使用二進制串來表示種群中的個體，因此許多基于遺傳算法的路徑規劃也采用二進制串來表示路徑，串中的每一位代表環境中表示的一個單位。但是當所處環境比較復雜時，表示路徑的二進制串也較長，使算法的搜索空間急劇擴大，降低遺傳算法的性能。針對復雜環境可以采用浮點數編碼或符號編碼以提高遺傳算法性能和保持更好的種群多樣性。

適應度函數構造方法：遺傳算法在進化搜索中基本不利用外部信息，僅以適應度函數為依據，利用種群中每個個體的適應度值來進行搜索。因此適應度函數的選取至關重要，直接影響到遺傳算法的收斂速度以及能否找到最優解。一般而言，適應度函數是由目標函數變換而成的。對目標函數值域的某種映射變換稱為適應度的尺度變換。

路徑規劃的目標一般是對從起點到終點的可行路徑選取時間最短或長度最短的一條路徑，因此根據路徑編碼的方式可以時間函數或路徑長度函數映射為適應度函數。而各種針對具體情況的算法的編碼并不一致、規劃目標也不相同，因此適應度應視具體的算法而定。

選擇算子的構造方法：選擇過程的第一步是計算適應度。在被選可行路徑集中每條路徑具有一個選擇概率，這個選擇概率取決于種群中個體的適應度及其分布。路徑個體選擇概率的常用分配辦法有：輪盤堵選擇法、按比例的適應度分配、基于排序的適應度分配、隨機遍歷抽樣法、局部選擇法、錦標賽選擇法等。不管采用哪種選擇方法都要體現出適應度高的路徑個體要得到更多的機會進入新一輪循環的思想。

交叉算子的構造方法：交叉就是把兩個父路徑個體的部分結構加以替換重組而產生新路徑個體的操作。交叉的目的是為了能夠在下一代產生新的路徑個體，通過重組交叉操作，遺傳算法的搜索能力得以飛躍地提高。對于二進制串個體可采用單點交叉、多點交叉和均勻交叉等交叉方法；對于實數個體可以采用離散重組、中間重組和線性重組等方法。

變異算子的構造方法：交叉之后是子代的變異，路徑子個體以很小的概率或步長產生轉變，變量轉變的概率或步長與維數(即變量的個數)成反比，與種群的大小無關。變異本身是一種局部隨機搜索，與選擇、交叉算子結合在一起，保證了遺傳算法的有效性，使遺傳算法具有局部的隨機搜索能力；同時使得遺傳算法保持種群的多樣性，以防止出現非成熟收斂。在變異操作中，變異率不能取得太大，如果變異率大于0.5，遺傳算法就退化為隨機搜索，而遺傳算法的一些重要的特性和搜索能力也不復存在了。

現在有很多學者已經將遺傳算法用于機器人路徑規劃中，但是因為其本身的缺陷（早熟、局部能力搜索差），還不能保證計算機效率和路徑的可靠性，因此還存在很大的改進發展空間。

3 基于螞蟻算法的機器人路徑規劃

在 20 世紀90年代，意大利學者 M.Dorigo，V.Maniezzao，A.Colorni等人從生物進化的機理中受到啟發，通過模擬自然界螞蟻尋食的行為，提出了一種全新的模擬進化算法：蟻群優化算法 (Ant Colony Optimization Algorithm簡稱ACOA)。

蟻群算法將路徑規劃看成是帶有一定限制條件的函數優化問題，將蟻群算法（Ant Colony Optimization 簡稱ACO）引入到機器人路徑規劃領域，很好地解決了環境中存在大量不規則靜態障礙物的路徑規劃問題。在機器人很難具有先驗知識的動態不確定環境中，機器人只能根據實時探測到的環境信息進行路徑規劃，針對這一問題結合兩步策略、滾動策略等的蟻群路徑規劃方法被提了出來，采用兩步策略進行動態路徑規劃，首先用最近鄰居策略和趨近導向函數完成全局最優路徑搜索，然后應用蟻群算法進行局部避障規劃，結合滾動窗口法，將目標點映射到機器人視野域附近，用蟻群算法完成局部最優路徑搜索，機器人每前進一步，都應用蟻群算法對局部最優路徑重新搜索，從而使機器人沿著一條全局優化的路徑到達目標點。

當一只螞蟻發現了獵物，嘗試搬動，如果不成功，則試著變換方向和位置，如果再次失敗，就會召集同伴。召集同伴的過程中也會撒下信息素告知獵物的大小。螞蟻合作搬運顯示出遠遠高于個體搬運的優勢，整體所能搬動的重量w和螞蟻的個數N呈指數關系。所以螞蟻整體顯示出驚人的力量。螞蟻之間通過影響環境來協調動作。搬運過程中，可能遇到死鎖，它們會變換方向和位置解除死鎖。合作搬運行為是基于群體的機器人研究的基準任務之一。機器人學家對螞蟻的合作搬運進行了建模，并設計了幾個相互無通信、無中心控制的機器人進行推盒子的實驗。這些機器人結構相同，各自有3個傳感器和1個行為裝置。傳感器用來感知障礙物、其他機器人和目標。

4 基于粒子群算法的機器人路徑規劃

粒子群優化算法(Particle Swarm Optimization 簡稱PSO)是基于群體智能的一種進化計算方法，由Eberhart和Kennedy于1995年提出。與一般的進化算法相比，PSO概念簡單、容易實現并且需要調整的參數少，目前廣泛應用于函數優化、模式分類、優化調度、神經網絡訓練、模糊系統控制等領域。將PSO引入移動機器人路徑規劃中，每個粒子就是一個機器人，每個機器人只搜索自己附近的區域，只更新自己的速度和自己的位置。建立一個由多個比較簡單的，類似昆蟲的機器人的群體swarm-bots。這些機器人使用相對便宜的構件，具有自組織和自組裝能力來適應環境。也有的將路徑規劃問題抽象為對一個罰函數的優化問題，該罰函數通過神經網絡結構構造，其中包含環境中障礙物的約束及路徑的長度信息。將該罰函數作為粒子群算法中的適應度函數，而路徑中除去起點與終點外的路徑節點作為粒子，通過混合粒子群算法進行尋優。由于適應度函數中包含了環境約束信息及路徑長度信息，最后規劃結果為一條安全無碰且長度較短的路徑。這種轉化思想也出現了，通過新的建模方法將機器人路徑規劃問題轉化為函數優化問題不失一種解決問題的好思路。

5 智能算法在機器人路徑規劃的發展趨勢

機器人路徑規劃研究自20世紀60年代出現以來，經過廣大專家學者幾十年的努力，在各個方面已有很大進步，特別是全局環境信息已知的路徑規劃已趨于完善，但未知環境中的路徑規劃，特別是存在未知動態障礙物的路徑規劃是一個NP-hard問題，此領域還有許多問題有待于進一步探討。從已有的成果可以看出智能算法在機器人路徑規劃中的應用有以下發展趨勢：

1) 向現有規劃方法有效結合的方向發展

無論是傳統規劃方法還是新生的智能算法都有一定的缺陷，傳統規劃方法過程簡單，容易實現但路徑優化效果較差，仿生智能算法魯棒性較好，能夠獲得較優化的路徑，但計算量較大，如何把各種算法的優點融合到一起在提高路徑搜索效率的同時又能獲得較優化的路徑是一個很好的研究方向。

2) 動態路徑規劃方法仍將是今后研究的重點

近年來動態不確定環境下的路徑規劃已取得長足發展，在路徑規劃效率及路徑優化方面均取得不錯效果。然而，應用于此領域的方法，無論是傳統的規劃方法還是新型的智能算法，均出現一些無法克服的問題，譬如，路徑搜索過程中的振蕩現象的發生，無法保證找到一條全局最優路徑等。動態不確定環境下的路徑規劃已經證明是一個NP-hard問題，如何在此環境中保證找到一條全局最優路徑及提高路徑規劃的實時性，避免振蕩現象的發生，還需要進一步深入地研究。

3) 多移動機器人系統的路徑規劃將取得長足發展

由多個簡單機器人組成的群體機器人系統通過協調、協作可以完成單機器人無法完成或難以完成的工作。相對于單個機器人，基于群體的機器人系統具有很大的優勢：相互合作的N個機器人的能力遠遠大于一個單機器人的N倍；設計和制造多個簡單機器人比單個復雜機器人更容易、成本更低；群體機器人系統的平行性和冗余性可以提高系統的靈活性和魯棒性等。研究群體機器人系統，目標是能夠建立經濟、靈活、健壯的系統去完成復雜的任務。群體機器人系統的主要研究內容為群體機器人之間的交互、通信、協作與控制、機器人的自組裝等。這些都可以從對生物群體的研究中得到啟示。隨著機器人系統應用的不斷擴大，工作環境復雜度和任務的加重，對其要求不再局限于單個機器人，而是多機器人系統，多移動機器人路徑規劃已成為新的研究熱點。

參考文獻：

[1] 張捍東，鄭睿. 移動機器人路徑規劃技術的研究現狀與展望[J].系統仿真學報，2005，17(2):439-443.

[2] Yanrong Hu and Simon X. Yang. A Knowledge Based Genetic A1gorithm for Path Planning of a Mobile Robot[C]. Proceedings of the 2004 IEEE international Conference on RoboticsAutomation New Orleans，2004:4350-4355.

[3] TAN Guan-Zheng，HE Huan，SLOMAN Aaron. Ant Colony System Algorithm for Real-Time Globally Optimal Path Planning of Mobile Robots[J].acta automatica sinica，2007，33(3):279-285.

[4] Hussein A.Abdullah，Shawki Areibi. Mobile Robots Path Planning Optimization in Static and Dynamic Environments[C]. Ahmed ELSHAMLI， University of Guelph，2004.

[5] 樊曉平，羅熊，易晟，等. 復雜環境下基于蟻群優化算法的機器人路徑規劃[J].控制與決策，2004，19(2):166-170.

[6] James M.Hereford，Member，IEEE，MichaelSiebold，Shannon Nichols. Using the Particle Swarm Optimization Algorithm for Robotic Search Applications[C]. Proceedings of the 2007 IEEE Swarm Intelligence Symposium (SIS 2007):4244-4251.

[7] 趙先章，常紅星，曾雋芳. 一種基于粒子群算法的移動機器人路徑規劃方法[J].計算機應用研究，2007，24(3):181-186.