基于蟻群算法的移動機器人多目標路徑規(guī)劃

蔣 強，易春林，張 偉，高 升

(1. 沈陽理工大學，遼寧 沈陽 110159；2. 中國科學院沈陽自動化研究所，遼寧 沈陽110016)

1 引言

隨著信息化與工業(yè)化的不斷融合，全球正經歷第四次工業(yè)革命浪潮，以機器人為代表的智能產業(yè)迅猛發(fā)展，將成為當代科技創(chuàng)新與智能制造的中流砥柱。與傳統(tǒng)工業(yè)機器人相比，具備自主感知、主動決策和自動執(zhí)行功能的智能機器人擁有更大的機動性和靈活性，在國防、航空航天、工業(yè)生產、智能物流運輸、社會服務等領域有著廣闊的應用前景。作為智能機器人研究領域的一個重要分支，路徑規(guī)劃技術是智能機器人實現自主導航、完成其它高級任務的前提與基礎，其目的是在具有障礙物的環(huán)境中，按照一定的評價標準(如路徑最短、耗能最小、安全性最高等)，尋找一條從起始點到目標點的無碰撞路徑[1]。

雖然單任務機器人可以在某種層面上滿足人類對智能制造的渴望，然而迫于成本與空間的限制以及對綠色生產理念的追求，人們更愿意在工業(yè)生產中使用多任務機器人。通常多任務可以分成串行多任務和并發(fā)多任務，對于串行多任務，機器人可按照任務之間的時序要求或先后關系，從前到后依次逐個執(zhí)行；而對于并發(fā)多任務，則需要優(yōu)化各個任務的執(zhí)行順序，盡可能減少機器人往返于各個任務點之間所需的時間或能源消耗，即需要考慮機器人的多目標路徑規(guī)劃問題。不同于M.Nazarahari等人在文獻[2]中對多目標路徑的描述，本文將多目標路徑規(guī)劃定義為：在具有障礙的環(huán)境中，按照一定的評價指標，尋找一條從初始位置出發(fā)并遍歷所有目標點的無碰撞路徑。顯然，多目標路徑規(guī)劃模型能更好的貼近現實，在無人生產、智能物流配送、車間調度等領域有著極大的應用價值。

這些年來在眾多學者的潛心鉆研下，人們對路徑規(guī)劃的研究已經取得了輝煌的成績，針對各種路徑規(guī)劃問題提出了大量不同的解決方法。例如柵格地圖[3]、幾何特征地圖、拓撲地圖以及混合地圖等方法被用于路徑規(guī)劃的地圖建模環(huán)節(jié)中；Dijkstra算法[4]、A*算法[5]、人工勢場法[6]以及一些諸如PRM、RRT[7]等基于采樣的方法被用于路徑規(guī)劃的路徑搜索環(huán)節(jié)中，此外隨著人工智能的發(fā)展，一些智能算法也逐漸被應用于路徑搜索中，如神經網絡算法[8]、遺傳算法[9]、蟻群算法[10]、粒子群算法[11]等。然而在這些成果中，幾乎沒有對本文所定義的多目標路徑規(guī)劃的研究，因此本論文致力于研究多個目標點之間的路徑規(guī)劃問題，期望所研究的內容有助于移動機器人技術的發(fā)展與進步。

2 地圖建模與路徑搜索算法

2.1 地圖建模

地圖建模是路徑規(guī)劃的重要環(huán)節(jié)，目的是將移動機器人所處的實際物理環(huán)境抽象成便于計算機存儲和處理的地圖模型，實現現實環(huán)境與虛擬地圖的相互映射。在前面提及的地圖建模方法中，柵格地圖具有簡單有效、易于實現、便于更新的特點，是目前研究和應用最廣泛的方法。通常根據柵格的劃分方式，可將其分為確切柵格和不確切柵格，其中確切柵格法編程簡單且易于實現，因此本文采用由正方形構成的確切柵格來表示機器人的真實工作場景，如圖1所示。

確切柵格是將機器人的工作環(huán)境按照一定的精度劃分成一系列大小相等的柵格單元，然后根據障礙物的占據情況將柵格分成兩種狀態(tài)：把包含障礙物的柵格標記為障礙柵格(黑色部分)，表示機器人不可通行的區(qū)域；把不包含障礙物的柵格標記為自由柵格(白色部分)，表示機器人可以通行的區(qū)域。由圖1(c)和1(d)可知，柵格單元的大小會直接影響環(huán)境的精度：當柵格單元劃分較小時，環(huán)境信息存儲量將增大，不利于進行路徑搜索；當劃分較大時，無法準確地表示真實環(huán)境，甚至會導致可通行的路徑信息被覆蓋掉。而且在實際情況中，機器人在障礙環(huán)境里的移動不能被簡單的視為質點的移動，需要考慮機器人自身的形狀、尺寸以及運動學與動力學約束對它的影響，甚至有時為了保證機器人在運動過程中的安全性，還需要讓機器人與障礙物保持足夠的距離。為了簡化問題以便于后續(xù)工作的開展，本文做出以下合理的假設：

1)仿真中所用的地圖是在考慮到機器人最大尺寸及安全距離的情況下建立的，已對地圖中的障礙物做膨脹處理，因此在規(guī)劃路徑時可將機器人視為一個質點；

2)機器人所處的環(huán)境是靜態(tài)的；

3)機器人不具備特殊的外形，如長桿形等；

4)機器人以麥克納姆輪或全向輪為驅動輪，在小范圍內具有360°全方位移動的能力，不受規(guī)劃路線是折線的影響；

5)柵格地圖的精度選擇合理，不會因為柵格過大而致使地圖中的可通行信息被湮沒。

圖1 基于柵格法的地圖模型

2.2 改進的Dijkstra路徑搜索算法

Dijkstra算法是荷蘭計算機科學家E.W. Dijkstra于1959年提出的一個適合于所有邊的權重均為非負值的最短路徑算法。作為圖論中一種典型的單源最短路徑求解方法，常被用于計算加權圖中指定節(jié)點到其它所有節(jié)點的最短路徑，它的主要特點是以起始點為中心按路徑遞增的順序逐漸向外層擴展，直至到達目標點為止。由于需要遍歷目標距離范圍內的所有節(jié)點，因而存在搜索效率低的缺點，不適合搜索單個目標；然而與A*算法以及一些智能搜索算法相比，它具有更好的廣度優(yōu)先搜索特性，在同時搜索多個目標對象時具有較好的實效性。

眾所周知，在路徑規(guī)劃中A*算法是一種實時性較好的搜索算法，因此這里將A*算法與Dijkstra算法進行比較，以驗證兩種算法在多目標路徑搜索中的時效性，仿真結果如圖2所示，其中紅色、藍色曲線分別表示使用Dijkstra、A*算法所規(guī)劃出的路徑，仿真結果表明：①在相同鄰域的搜索規(guī)則下，Dijkstra算法規(guī)劃的路徑更短；②這兩種算法均具有完備性，若環(huán)境中存在一條從起點到終點的無碰路徑，則該算法一定能找到，若不存在則會報告規(guī)劃失敗[12]。

圖2 基于A*和Dijkstra算法的多目標路徑搜索

地圖序號(柵格尺寸)目標序號目標個數尋路時間(s)經典A*DijkstraMap A110.00210.0039(13×13)1～770.00870.00511～13130.01390.0060Map B110.05340.0828(100×100)1～881.00790.20461～15151.82630.2475

表1 列出了這兩種算法在不同情況下所需要的尋路時間，實驗數據說明：對單目標的路徑規(guī)劃，A*算法具有較好的時效性，而對多目標的路徑規(guī)劃，Dijkstra算法具有較好的時效性。

現實中機器人的轉向角通常是某個范圍內的連續(xù)取值；而使用柵格地圖進行路徑搜索時，Dijkstra算法通常被限制在4鄰域或8鄰域，如圖3所示，因而搜索出的路徑一般是比較曲折的。為了使規(guī)劃的路徑性能更優(yōu)，本文針對搜索方向或搜索鄰域較少的問題進行了改進，提出了一種16鄰域的搜索規(guī)則。圖4顯示了在不同地圖中分別使用這三種規(guī)則進行路徑搜索所獲得的規(guī)劃路線，其中綠色、粉色和藍色曲線分別對應4、8和16鄰域的搜索規(guī)則。由仿真結果可知，隨著搜索鄰域的增多，所規(guī)劃的路徑效果越好。

圖3 四、八和十六鄰域搜索規(guī)則

圖4 三種規(guī)則下的路徑規(guī)劃結果

由于搜索方向的限制，使用A*或Dijkstra算法所規(guī)劃的路徑一般是由多條線段組成的折線，特別是在地圖尺寸較大的情況下，路徑存在一定的鋸齒效果，如圖5所示。從圖中的路徑曲線可以看出，路徑中存在一些不必要的轉折點，如P3和P5，刪除這些不必要的轉折點可以改善路徑在長度、平滑度等方面的性能，因此為了進一步提升路徑性能，本文提出了一種刪除這些冗余轉折點的方法。

圖5 路徑的鋸齒效應

刪除冗余轉折點的實質就是在路徑中找出冗余轉折點?？紤]到生成的路徑是一條折線，因而可用一系列由折線的轉折點構成的有序集合來表示Path={P0，P1，P2，…，Pn-1，Pn}，對于路徑上的轉折點Pi，若其前后兩個相鄰轉折點的連線Pi-1Pi+1不經過障礙物，則Pi是冗余轉折點；反之，若Pi-1Pi+1經過障礙物，則Pi是必要轉折點，刪除它將使路徑與障礙物發(fā)生碰撞，如圖6所示。

由上面的描述可知，Pi-1Pi+1是否穿過障礙物是判斷Pi是否為冗余轉折點的標志，而判斷Pi-1Pi+1是否穿過障礙物就是分析Pi-1Pi+1所經過的柵格單元中是否存在障礙柵格。圖7描述了柵格地圖中Pi-1Pi+1可能經過的柵格單元，其中紅色網格表示連線穿過的柵格單元，而成對出現的綠色網格則表示連線經過該網格的一個頂點但不穿過該網格。顯然只有當所有紅色網格都不是障礙網格且成對的綠色網格中至少有一個不是障礙網格，才能保證Pi-1Pi+1不穿過障礙。

圖6 冗余轉折點(左)與必要轉折點(右)

設點Pi-1和Pi+1的柵格坐標分別為(x1，y1)和(x2，y2)，并記Δx=|x2-x1|，Δy=|y2-y1|，對于Δx≥Δy的情形，以x為自變量來描述經過Pi-1和Pi+1的直線方程

(1)

①若x1=x2時，線段Pi-1Pi+1所經過的柵格單元的坐標集合Sgrid可表示為

(2)

②若x1≠x2時，線段Pi-1Pi+1所經過的柵格單元的坐標集合Sgrid可表示為

Sgrid=S1∪S2

(3)

圖7 Pi-1Pi+1連線經過的柵格單元

(5)

對于W(i)需按以下兩種情況來分析，當k≥0時

(6)

當k<0時

(7)

其中，符號[·]表示向下取整；上述公式中除or連接的兩個坐標表示成對出現的綠色網格外，其余的坐標均表示紅色網格。

而對于Δx<Δy的情形，以y為自變量來描述經過Pi-1和Pi+1的直線方程。同理，在分析Pi-1Pi+1所經柵格單元的坐標集合時，亦可按y1=y2和y1≠y2兩種情況來分別討論。最后，根據所經柵格單元中障礙物的占據情況可以判斷Pi-1Pi+1是否穿過障礙物。

圖8中的藍色和紅色曲線分別表示優(yōu)化(刪除冗余轉折點)前、后的路徑，結果表明優(yōu)化后的路徑更平滑也更短。

圖8 優(yōu)化前后的路徑效果

3 多目標路徑規(guī)劃算法

通常使用路徑長度、平滑度和安全性等三個指標來評價一條路徑，由于前面已假設按照安全距離對障礙物進行了膨脹，因此生成的路徑一定是安全可靠的。此外，由于機器人停留在任務點執(zhí)行任務的過程中可能會且有足夠的時間做出一些姿態(tài)調整，因此不必要求機器人進入某個目標地點或離開該目標點的姿態(tài)必須連貫，即無需考慮機器人進入或離開某個目標點時路徑的平滑度。

多目標路徑規(guī)劃問題本質上是一個需要大量已知環(huán)境信息的全局尋優(yōu)問題，因而只適合在環(huán)境信息已知的全局路徑規(guī)劃中實現，它主要包含路徑規(guī)劃技術和多目標優(yōu)化技術，兩種技術間的融合如圖9所示。

在全局路徑規(guī)劃部分，主要包含以下幾個環(huán)節(jié)：①選擇路徑搜索算法；②搜索并優(yōu)化起始點及各目標點之間的路徑；③計算每條優(yōu)化后的路徑距離。在多目標優(yōu)化部分，主要是利用由全局路徑規(guī)劃獲取的距離信息來搜索一條最短路徑。為了詳細地介紹多目標路徑規(guī)劃的實現過程，本文將分別從路徑規(guī)劃和多目標優(yōu)化兩個部分來進行描述。在此之前先假設在某個具有障礙物的環(huán)境中機器人的起始位置為T0，其期望到達的n個目標點的位置分別為T1，T2，…，Tn。

圖9 多目標路徑規(guī)劃框架圖

3.1 路徑規(guī)劃

在路徑規(guī)劃部分，需要采用一種有效的全局路徑搜索算法搜索出T0，T1，T2，…，Tn中每兩點之間的最短無碰撞路徑，然后對這些生成的路徑進行優(yōu)化處理。待路徑優(yōu)化完畢，將得到一系列由折線段組成的路徑，如圖10所示。

圖10 點Pi到點Pj的路徑示意圖

故點Ti到Tj的距離di，j(0≤i，j≤n，i≠j)可由式(8)計算。

(8)

最后可用一個距離矩陣來描述這些距離信息

(9)

從而多目標路徑規(guī)劃問題可以表述為

(10)

其中，R表示{1，2，3，…，n}的全排列，R(i)表示該排列中的第i個元素。

由于dij和dji是相等的，因此為了提高路徑規(guī)劃的效率，在搜索路徑時只需要獲取距離矩陣中上三角部分的元素對應的路徑及距離信息。除此以外，Dijkstra算法適合同時搜索大量目標，當目標個數較少時，為了保證算法的搜索速度，可選擇使用A*等算法來進行路徑搜索。

3.2 多目標優(yōu)化

在多目標優(yōu)化部分，需要采用優(yōu)化算法在距離矩陣中尋找出一條從起始點出發(fā)遍歷所有可到達的目標點的最短路徑。這是一種典型的TSP問題，它已被證實為具有NPC計算復雜度——隨著目標個數的增多，問題的可行解會產生組合爆炸。

當問題規(guī)模較大時，為了避免對整個可行解空間進行窮舉式的搜索，越來越多的學者熱衷于使用遺傳算法、蟻群算法、粒子群算法、免疫算法和細菌覓食算法等智能優(yōu)化算法來求解多目標問題的近似最優(yōu)解。與早期的分枝定界法、線性規(guī)劃法、動態(tài)規(guī)劃法等精確算法相比，智能算法無需遍歷整個可行解空間，計算效率較高。在上述智能優(yōu)化算法中，蟻群算法具有分布計算、信息正反饋和啟發(fā)式搜索等特征，在搜索最短路徑方面具有優(yōu)勢[13]，因此本文使用蟻群算法來解決多目標優(yōu)化問題。

蟻群算法是通過模擬蟻群覓食過程而提出的一種啟發(fā)式優(yōu)化算法，螞蟻在合作覓食的過程中，總能通過各自遺留在所經路線上的信息素來進行信息交流，從而指導整個蟻群在蟻穴與食物找到一條最優(yōu)路徑。受益于這一自然靈感的啟迪，M.Dorigo等人于上世紀90年代提出了蟻群算法基本模型[14]，其原理如下：

(11)

息啟發(fā)式因子，表示信息素的相對重要性，反映了路徑上殘留的信息素對螞蟻選擇路徑的影響程度；β為期望啟發(fā)式因子，表示能見度的相對重要性，反映了螞蟻在運動過程中啟發(fā)信息對螞蟻選擇路徑的影響程度。

當每只螞蟻走完一步或完成一次周游后，要對各路徑上殘留信息素進行更新處理，通常t+1時刻在路徑(i，j)上的信息素可按如下規(guī)則進行調整

τij(t+1)=(1-ρ)·τij(t)+Δτij(t)

(12)

(13)

(14)

4 仿真及結果分析

為了驗證該多目標路徑規(guī)劃算法的有效性，本文將采用一系列尺寸不同、環(huán)境各異的地圖來進行仿真。整個程序使用Python語言進行編寫，計算機配置為：Windows 7操作系統(tǒng)，處理器為E5620，主頻2.4GHz，運行內存為8G。

圖11 多目標路徑規(guī)劃仿真地圖

實驗所用的仿真地圖如圖11所示，其中藍色柵格(或圓)表示起始節(jié)點，綠色柵格(或圓)表示目標節(jié)點，為了便于計算所生成路徑的距離信息，在這里認為所有地圖中柵格單元的邊長為1，即地圖尺寸為100×100的地圖是由100×100個網格單元構成的。與精確算法不同的是，蟻群算法求解的是優(yōu)化問題的近似最優(yōu)解，并不能保證每一次仿真結果都是一致的。為了確保實驗結果有足夠的說服力，本文將對同一地圖進行多次(10次)重復仿真，并記錄相關實驗數據及對應的地圖信息至圖13中。最后在圖12中顯示了十次仿真中路徑長度最短的實驗結果，其中紅色線段表示所規(guī)劃的路線。

從圖12中各目標點之間的路徑曲線可以看出，該路徑搜索算法對最短路徑的搜索效果大體上能與可視圖法媲美，它所規(guī)劃的路徑大多都是最短的或近似最短的，符合多目標路徑規(guī)劃求解全局最短路徑的設計初衷。通過分析仿真結果可以看出：①由對Map_1、Map_2、Map_3以及Map_4的仿真結果可知，該算法對不同復雜度的環(huán)境均能做出有效的路徑規(guī)劃，具有較好的環(huán)境適應能力；②在Map_1中設定了與起點隔離的四個目標點，由此地圖的規(guī)劃結果可知該算法能夠判斷出某個目標是否可到達，并在多目標路徑規(guī)劃階段避開不可到達的目標點；③由表2中出現實際最短距離的次數可知，當目標點個數較少時，蟻群算法能大概率搜索出全局最優(yōu)解，而隨著目標個數的增加，蟻群算法開始陷入局部最優(yōu)解(見圖12中Map_6的仿真結果)，只有很小的概率能找到最優(yōu)解，因此在以后的研究中將重點對蟻群算法進行優(yōu)化，以提高算法的優(yōu)化性能；(4)通過分析圖13中Map_4、Map_5和Map_6的仿真數據可以發(fā)現，平均誤差會隨著目標個數的增加而逐漸增大，但整體平均偏差是在一個可接受的范圍內，從而說明該算法能有效解決多目標路徑規(guī)劃問題。

圖12 多目標路徑規(guī)劃仿真結果

地圖基本信息實驗數據地圖序號地圖尺寸目標個數實際最短距離進行10次重復仿真十次仿真中出現的最好結果十次仿真中出現的最壞結果平均搜索距離平均誤差出現實際最短距離的次數平均搜索時間(s)蟻群算法相關參數設置Map_1100×100153703703703700%102.292Map_2100×100156706706756710.15%84.077Map_3100×10015503503.6509503.60.12%93.297Map_4200×200116666666666660%107.357Map_5200×200211009101410301022.11.30%414.182Map_6200×200311186120512241213.12.28%323.216Q=1ρ=0.02α=3β=2.5

注：在每一次仿真中，螞蟻個數k與可到達的目標點個數相同。

5 結論

隨著無人生產理念的不斷深化以及智能制造技術的不斷進步，智能機器人將在我國今后的工業(yè)生產、產業(yè)結構轉型和產品優(yōu)化升級等方面發(fā)揮巨大的作用，本文針對智能機器人在復雜的靜態(tài)障礙物環(huán)境下執(zhí)行并發(fā)多任務的情況，提出了一種基于蟻群算法的多目標路徑規(guī)劃算法，通過仿真結果可驗證，在靜態(tài)環(huán)境中該算法能有效解決多目標路徑規(guī)劃問題。與單目標路徑規(guī)劃相比，多目標路徑規(guī)劃更為復雜，存在一些至今尚無高效解決方法的難點，這些問題的突破將有助于多目標路徑規(guī)劃的廣泛應用：

1)沒有考慮機器人的運動學與動力學特性，只是從決策層面(而非執(zhí)行層面)進行了路徑規(guī)劃，獲得的路徑不符合機器人的底層控制要求，不能將該路徑用于機器人的軌跡跟蹤。因此在未來的研究中應將機器人的底層控制與路徑規(guī)劃算法相結合。

2)大多數關于多目標路徑規(guī)劃的研究都是基于靜態(tài)環(huán)境的，難以適用于復雜且多變的現實環(huán)境。相對靜態(tài)環(huán)境下的路徑規(guī)劃，動態(tài)環(huán)境下的多目標路徑規(guī)劃更加貼近實際應用。

3)在諸如蟻群算法、遺傳算法等智能優(yōu)化算法中，參數的配置對優(yōu)化結果的好壞有著極大的影響，在解決各種優(yōu)化問題時往往需要根據實際問題來配置參數，并不存在一組適合解決各種優(yōu)化問題的萬能參數。因而根據當前的優(yōu)化問題自適應地配置并調節(jié)優(yōu)化算法的相關參數[15]是確保多目標路徑規(guī)劃算法自主適應各類地圖環(huán)境的關鍵。