蔣 強(qiáng)，易春林，張 偉，高 升

(1. 沈陽理工大學(xué)，遼寧 沈陽 110159；2. 中國(guó)科學(xué)院沈陽自動(dòng)化研究所，遼寧 沈陽110016)

1 引言

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

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

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

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

2.1 地圖建模

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

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

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

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

3)機(jī)器人不具備特殊的外形，如長(zhǎng)桿形等；

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

5)柵格地圖的精度選擇合理，不會(huì)因?yàn)闁鸥襁^大而致使地圖中的可通行信息被湮沒。

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

2.2 改進(jìn)的Dijkstra路徑搜索算法

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

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

圖2 基于A*和Dijkstra算法的多目標(biāo)路徑搜索

地圖序號(hào)(柵格尺寸)目標(biāo)序號(hào)目標(biāo)個(gè)數(shù)尋路時(shí)間(s)經(jīng)典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 列出了這兩種算法在不同情況下所需要的尋路時(shí)間，實(shí)驗(yàn)數(shù)據(jù)說明：對(duì)單目標(biāo)的路徑規(guī)劃，A*算法具有較好的時(shí)效性，而對(duì)多目標(biāo)的路徑規(guī)劃，Dijkstra算法具有較好的時(shí)效性。

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

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

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

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

圖5 路徑的鋸齒效應(yīng)

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

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

圖6 冗余轉(zhuǎn)折點(diǎn)(左)與必要轉(zhuǎn)折點(diǎn)(右)

設(shè)點(diǎn)Pi-1和Pi+1的柵格坐標(biāo)分別為(x1，y1)和(x2，y2)，并記Δx=|x2-x1|，Δy=|y2-y1|，對(duì)于Δx≥Δy的情形，以x為自變量來描述經(jīng)過Pi-1和Pi+1的直線方程

(1)

①若x1=x2時(shí)，線段Pi-1Pi+1所經(jīng)過的柵格單元的坐標(biāo)集合Sgrid可表示為

(2)

②若x1≠x2時(shí)，線段Pi-1Pi+1所經(jīng)過的柵格單元的坐標(biāo)集合Sgrid可表示為

Sgrid=S1∪S2

(3)

圖7 Pi-1Pi+1連線經(jīng)過的柵格單元

(5)

對(duì)于W(i)需按以下兩種情況來分析，當(dāng)k≥0時(shí)

(6)

當(dāng)k<0時(shí)

(7)

其中，符號(hào)[·]表示向下取整；上述公式中除or連接的兩個(gè)坐標(biāo)表示成對(duì)出現(xiàn)的綠色網(wǎng)格外，其余的坐標(biāo)均表示紅色網(wǎng)格。

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

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

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

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

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

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

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

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

3.1 路徑規(guī)劃

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

圖10 點(diǎn)Pi到點(diǎn)Pj的路徑示意圖

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

(8)

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

(9)

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

(10)

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

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

3.2 多目標(biāo)優(yōu)化

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

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

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

(11)

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

當(dāng)每只螞蟻?zhàn)咄暌徊交蛲瓿梢淮沃苡魏螅獙?duì)各路徑上殘留信息素進(jìn)行更新處理，通常t+1時(shí)刻在路徑(i，j)上的信息素可按如下規(guī)則進(jìn)行調(diào)整

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

(12)

(13)

(14)

4 仿真及結(jié)果分析

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

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

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

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

圖12 多目標(biāo)路徑規(guī)劃仿真結(jié)果

地圖基本信息實(shí)驗(yàn)數(shù)據(jù)地圖序號(hào)地圖尺寸目標(biāo)個(gè)數(shù)實(shí)際最短距離進(jìn)行10次重復(fù)仿真十次仿真中出現(xiàn)的最好結(jié)果十次仿真中出現(xiàn)的最壞結(jié)果平均搜索距離平均誤差出現(xiàn)實(shí)際最短距離的次數(shù)平均搜索時(shí)間(s)蟻群算法相關(guān)參數(shù)設(shè)置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

注：在每一次仿真中，螞蟻個(gè)數(shù)k與可到達(dá)的目標(biāo)點(diǎn)個(gè)數(shù)相同。

5 結(jié)論

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

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

2)大多數(shù)關(guān)于多目標(biāo)路徑規(guī)劃的研究都是基于靜態(tài)環(huán)境的，難以適用于復(fù)雜且多變的現(xiàn)實(shí)環(huán)境。相對(duì)靜態(tài)環(huán)境下的路徑規(guī)劃，動(dòng)態(tài)環(huán)境下的多目標(biāo)路徑規(guī)劃更加貼近實(shí)際應(yīng)用。

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