周國(guó)春，肖本賢

（1.合肥工業(yè)大學(xué) 工業(yè)與裝備技術(shù)研究院，合肥 230009；2.合肥工業(yè)大學(xué) 電氣與自動(dòng)化工程學(xué)院，合肥 230009）

近年來(lái)，移動(dòng)機(jī)器人系統(tǒng)已經(jīng)成為人工智能和智能控制等領(lǐng)域的一個(gè)研究熱點(diǎn)，受到了越來(lái)越多研究者的重視[1-2]。移動(dòng)機(jī)器人最重要的作用就是能移動(dòng)，這種移動(dòng)并不是漫無(wú)目的的移動(dòng)，而是能夠自動(dòng)從起點(diǎn)運(yùn)動(dòng)到終點(diǎn)的能力。在移動(dòng)機(jī)器人移動(dòng)之前，就已經(jīng)生成一條從起點(diǎn)到終點(diǎn)的最佳路徑，并且這條路徑能夠躲避一切固定的障礙物，還能夠提前規(guī)避其他機(jī)器人[3]。移動(dòng)機(jī)器人的路徑規(guī)劃問(wèn)題經(jīng)過(guò)幾十年的研究，我們得到很多關(guān)于這類問(wèn)題的有效解決方法。傳統(tǒng)的路徑規(guī)劃方法有可視圖法、柵格法和人工勢(shì)場(chǎng)等，群智能算法有蟻群算法、粒子群算法和人工蜂群算法等。這些算法都能夠在一些環(huán)境中解決了路徑規(guī)劃問(wèn)題，同樣也存在不足[4-6]。

當(dāng)前對(duì)于機(jī)器人路徑規(guī)劃方法的研究，有時(shí)候會(huì)考慮到很多因素，不一定不需要移動(dòng)機(jī)器人規(guī)劃出距離最短的路徑。所以在實(shí)際應(yīng)用中，我們考慮路徑規(guī)劃的時(shí)候要結(jié)合當(dāng)前環(huán)境以及實(shí)際要求來(lái)確定出最優(yōu)路徑。通常評(píng)判路徑規(guī)劃的指標(biāo)有路徑距離的大小、與障礙物保持安全距離以及路徑?jīng)]有過(guò)多曲折。在這類情況中，需要移動(dòng)機(jī)器人路徑規(guī)劃的結(jié)果滿足上述要求多個(gè)指標(biāo)的要求。目前，對(duì)于機(jī)器人路徑規(guī)劃實(shí)時(shí)性要求較高并且對(duì)可行路徑有多標(biāo)準(zhǔn)的任務(wù)中，通過(guò)將路徑規(guī)劃所要滿足的多個(gè)指標(biāo)通過(guò)一定的方式轉(zhuǎn)化成一個(gè)綜合評(píng)價(jià)指標(biāo)來(lái)規(guī)劃出最適合機(jī)器人的最優(yōu)路徑。常用的轉(zhuǎn)化方式有約束法和權(quán)重系數(shù)變化法。本文采取設(shè)置權(quán)重系數(shù)，將多個(gè)路徑評(píng)價(jià)指標(biāo)轉(zhuǎn)化成一個(gè)綜合評(píng)價(jià)指標(biāo)，并且和優(yōu)化后人工蜂群算法合并進(jìn)行仿真試驗(yàn)，試驗(yàn)可知提出的方法可更快速地尋得更優(yōu)的全局最優(yōu)解。

1 人工蜂群算法

人工蜂群算法[7-10]從提出開始，由于其參數(shù)少，自適應(yīng)強(qiáng)，受到很多研究者的追捧，廣泛應(yīng)用于各大領(lǐng)域，其中就包括移動(dòng)機(jī)器人的路徑規(guī)劃領(lǐng)域。

1.1 人工蜂群算法的數(shù)學(xué)模型

初始化會(huì)形成一個(gè)初始食物源。即初始解（x1，x2，…，xn，…，xN）：

式中：lbi為可行解的最小值；ubi是可行解的最大值；rand（0，1）生成（0，1）之間的隨機(jī)數(shù)；n∈｛1，2，3，…Fn｝，F(xiàn)n為食物源數(shù)目。

食物源生成之后，評(píng)價(jià)函數(shù)會(huì)對(duì)生成的食物源進(jìn)行評(píng)價(jià)，評(píng)價(jià)函數(shù)如式（2）所示：

式中：f（xn）為對(duì)應(yīng)的解向量xn的目標(biāo)函數(shù)值。

雇傭蜂在當(dāng)前食物源附近搜索新食物源的方法如式（3）所示：

式中：xni′為新食物源；xni為當(dāng)前食物源；ε為搜索系數(shù)，其值介于［-1，1］之間；xki是食物源中一個(gè)不同于 xni的食物源，k∈｛1，2，3，…Fn｝。

當(dāng)搜索到新食物源，雇傭蜂會(huì)對(duì)這個(gè)新食物源進(jìn)行評(píng)價(jià)，并與之前的食物源進(jìn)行對(duì)比，來(lái)決定放棄哪個(gè)食物源。

觀察蜂參照雇傭蜂返回時(shí)所帶來(lái)的食物源信息進(jìn)行選擇覓食。它們會(huì)利用食物源的評(píng)價(jià)函數(shù)來(lái)計(jì)算他們選擇某個(gè)食物源的可開采的概率probabilityn，計(jì)算方法如式（4）所示：

觀察蜂會(huì)因個(gè)體差異，存在各自對(duì)食物源的期望。然后將期望和可開采概率比較，來(lái)決定觀察蜂是否選擇此食物源進(jìn)行開采。

偵察蜂的作用是搜索新的食物源，并不參照當(dāng)前食物源，而是類似初始化一樣隨機(jī)生成。在此之前會(huì)對(duì)選擇次數(shù)超過(guò)限定值的食物源進(jìn)行放棄，如式（5）所示：

式中：trial是當(dāng)前蜜蜂對(duì)食物源優(yōu)化的次數(shù)。

1.2 移動(dòng)機(jī)器人的環(huán)境地圖

在移動(dòng)機(jī)器人路徑仿真中，如果不考慮機(jī)器人的結(jié)構(gòu)，通常將移動(dòng)機(jī)器人當(dāng)作一個(gè)質(zhì)點(diǎn)。由于柵格法建立的地圖存在一些缺陷，我們采用坐標(biāo)法來(lái)定位移動(dòng)機(jī)器人的位置。在移動(dòng)機(jī)器人路徑規(guī)劃中，由于一開始就知道移動(dòng)機(jī)器人的位置，也知道它將要到達(dá)的地方。這樣根據(jù)移動(dòng)機(jī)器人的起點(diǎn)和終點(diǎn)的坐標(biāo)對(duì)應(yīng)的X軸和Y軸上的數(shù)值最小值和最大值來(lái)生成一個(gè)長(zhǎng)和寬均大一的矩形地圖。這樣機(jī)器人在地圖中的任何位置都可以由坐標(biāo)值來(lái)表示。在這里我們規(guī)定移動(dòng)機(jī)器人的移動(dòng)步長(zhǎng)Stepl，那么機(jī)器人的下一個(gè)位置就是以當(dāng)前位置為圓心，半徑為Stepl的圓上。這樣如果我們可以得知下一個(gè)位置相對(duì)當(dāng)前位置的角度，則可以準(zhǔn)確得到下一個(gè)位置的準(zhǔn)確值。公式如下所示：

式中：（xk＋1，yk＋1） 是移動(dòng)機(jī)器人下一位置；（xk，yk）是移動(dòng)機(jī)器人當(dāng)前位置；θk是移動(dòng)機(jī)器人下一位置相對(duì)當(dāng)前位置的夾角。

通過(guò)這種表示方法，我們可以由移動(dòng)機(jī)器人的起點(diǎn)坐標(biāo)就可以直接得出移動(dòng)機(jī)器人規(guī)劃出的路徑上任何一個(gè)點(diǎn)，如式（7）所示。

式中：（xk，yk）是移動(dòng)機(jī)器人的任一路徑點(diǎn)坐標(biāo)，k＝（1，2，…Fn）；（xs，ys）是移動(dòng)機(jī)器人起點(diǎn)。

在工作環(huán)境地圖中，通常存在一些障礙物，對(duì)于已知的靜態(tài)環(huán)境來(lái)說(shuō)，障礙物也是已知。我們采用一個(gè)比障礙物大一些的同心圓將障礙物包圍。這樣得出的移動(dòng)機(jī)器人環(huán)境地圖如圖1所示。

圖1 機(jī)器人路徑規(guī)劃環(huán)境地圖Fig.1 Robot path planning environment map

在路徑仿真中，移動(dòng)機(jī)器人要計(jì)算到障礙物的距離就可以通過(guò)已經(jīng)得知障礙物同心圓的圓心和半徑來(lái)計(jì)算。

2 基于人工蜂群算法的路徑規(guī)劃

2.1 人工蜂群算法的改進(jìn)

在人工蜂群算法中隨機(jī)搜索系數(shù) ε=［-1，1］。隨機(jī)搜索系數(shù)是來(lái)確定蜜蜂對(duì)當(dāng)前食物源附近的范圍進(jìn)行搜索，在迭代早期需要進(jìn)行范圍較大搜索，有利于得到全局最優(yōu)解，但在迭代后期，目標(biāo)解已經(jīng)趨于穩(wěn)定，這時(shí)候過(guò)大的搜索范圍不利于算法收斂，還會(huì)增加算法優(yōu)化的時(shí)間。這里，我們對(duì)隨機(jī)搜索系數(shù)ε進(jìn)行改進(jìn)，設(shè)計(jì)了如式（8）所示的新隨機(jī)搜索因子。新的隨機(jī)搜索系數(shù)與迭代的次數(shù)成反比，在迭代初期仍在［-1，1］之間，但在迭代后期，隨機(jī)搜索系數(shù)只有早期的e-1，這樣符合我們的要求。

式中：Loop為當(dāng)前迭代次數(shù)；MaxLoop為最大的迭代次數(shù)。

同時(shí)人工蜂群算法中雇傭蜂和觀察蜂搜索食物源時(shí)較大程度依賴當(dāng)前所采蜜的食物源，雖然參考的其它蜜蜂的食物，但所占比重較小，這樣極易陷入局部最優(yōu)，所以采用在食物源中隨機(jī)選擇3個(gè)食物源進(jìn)行交叉產(chǎn)生新的食物源，公式如下：

式中：p，k，q均不等于n，將其與之前的隨機(jī)搜索相結(jié)合，搜索前產(chǎn)生一個(gè)隨機(jī)數(shù)P，隨機(jī)數(shù)P的大小和迭代次數(shù)成反比，這樣在算法的初期很好地進(jìn)行全局搜索，在算法的后期只進(jìn)行局部搜索，不會(huì)增加算法的運(yùn)行時(shí)間。當(dāng)隨機(jī)數(shù)P小于設(shè)定參數(shù)Pm時(shí)執(zhí)行隨機(jī)搜索方式，反之執(zhí)行新的搜索方式，如式（10）所示。通過(guò)將兩種搜索方式相結(jié)合，在蜜蜂搜索食物源的過(guò)程中，既能夠進(jìn)行全局搜索，也能夠避免陷入局部最優(yōu)。

人工蜂群算法應(yīng)用于移動(dòng)機(jī)器人路徑規(guī)劃中，就要對(duì)算法的目標(biāo)函數(shù)提出新的要求。本文中，路徑規(guī)劃的評(píng)價(jià)指標(biāo)存在3種，所以算法的目標(biāo)函數(shù)也要包括這3項(xiàng)指標(biāo)。三項(xiàng)指標(biāo)分別是規(guī)劃出的路徑總長(zhǎng)度；二是路徑是否安全，是根據(jù)移動(dòng)機(jī)器人到障礙物的最小長(zhǎng)度是否大于最小安全距離，最小長(zhǎng)度的計(jì)算方法是移動(dòng)機(jī)器人的位置點(diǎn)到障礙物同心圓邊界的最小長(zhǎng)度；三是路徑的曲折性，通過(guò)計(jì)算各個(gè)位置點(diǎn)之間對(duì)應(yīng)的夾角和。通過(guò)動(dòng)態(tài)加權(quán)系數(shù)后得出評(píng)價(jià)任一條路徑的目標(biāo)函數(shù)如式（11）所示。

式中：distgoali代表機(jī)器人的路徑點(diǎn)（xi，yi）到目標(biāo)點(diǎn)（xgoal，ygoal）的距離；distobsi為機(jī)器人的路徑點(diǎn)（xi，yi）到障礙物（oxk，oky）的距離；rj為障礙物安全區(qū)半徑；obs為障礙物的數(shù)目；ω1、ω2、ω3為權(quán)重系數(shù)，其中 ω1+ω2+ω3=1。

為了使目標(biāo)函數(shù)符合實(shí)際要求，一般設(shè)置ω3為定值，ω2隨著路徑點(diǎn)離障礙物的距離變化，如式（12）所示，而 ω1=1-ω2-ω3。

式中：ω2在［0.1，0.3］之間變化；distmax是絕對(duì)安全距離；distmin是最小安全距離。

2.2 改進(jìn)后的人工蜂群算法在移動(dòng)機(jī)器人路徑規(guī)劃的應(yīng)用

為了使移動(dòng)機(jī)器人能夠正確規(guī)劃出起點(diǎn)到終點(diǎn)的路徑。在環(huán)境地圖那章中，我們用規(guī)定的定步長(zhǎng)，以及相對(duì)位置的夾角作為標(biāo)記移動(dòng)機(jī)器人的位置。因此，算法初始化生產(chǎn)一組關(guān)于初始角度大小的初始解，之后通過(guò)不斷優(yōu)化得到最終最優(yōu)角度解，最優(yōu)解包含了移動(dòng)機(jī)器人所有路徑點(diǎn)的信息。移動(dòng)機(jī)器人在開始路徑規(guī)劃之前，就已經(jīng)得知環(huán)境中的靜態(tài)障礙物的位置和大小，環(huán)境中存在的動(dòng)態(tài)障礙物為同一工作空間中的其它移動(dòng)機(jī)器人。一旦路徑點(diǎn)與所有障礙物的最小距離大于絕對(duì)安全距離，基本不用考慮安全性的問(wèn)題。但是一旦低于最小安全距離，則該路徑的適應(yīng)值變?yōu)?，重新規(guī)劃路徑。

在實(shí)際情況中，通常會(huì)存在多個(gè)移動(dòng)機(jī)器人同時(shí)進(jìn)行路徑規(guī)劃工作。在這種多機(jī)器人路徑規(guī)劃任務(wù)中，先給各移動(dòng)機(jī)器人進(jìn)行編號(hào)，編號(hào)小的機(jī)器人擁有較高優(yōu)先級(jí)。這樣多移動(dòng)機(jī)器人在進(jìn)行路徑規(guī)劃時(shí)，首先會(huì)判斷該移動(dòng)機(jī)器人是否與優(yōu)先級(jí)較高的移動(dòng)機(jī)器人存在交叉點(diǎn)。一旦發(fā)現(xiàn)存在交點(diǎn)，則會(huì)進(jìn)一步判斷是否同時(shí)經(jīng)過(guò)該點(diǎn)。在相同的步長(zhǎng)中，通過(guò)步數(shù)來(lái)判斷是否同時(shí)經(jīng)過(guò)交叉點(diǎn)。如果兩個(gè)機(jī)器人同時(shí)經(jīng)過(guò)交叉點(diǎn)，則將優(yōu)先級(jí)點(diǎn)的移動(dòng)機(jī)器人在該路徑適應(yīng)度值置為0，并重新規(guī)劃路徑。在規(guī)劃某一移動(dòng)機(jī)器人路徑點(diǎn)時(shí)，會(huì)計(jì)算該移動(dòng)機(jī)器人與當(dāng)前所有優(yōu)先級(jí)比它高的機(jī)器人所處的位置點(diǎn)之間的距離，如果有小于最小安全距離的，則將該移動(dòng)機(jī)器人當(dāng)前規(guī)劃的路徑適應(yīng)值置為0，并重新規(guī)劃路徑。

3 仿真試驗(yàn)及分析

3.1 仿真環(huán)境設(shè)置

為了驗(yàn)證總評(píng)價(jià)標(biāo)準(zhǔn)的目標(biāo)函數(shù)對(duì)路徑規(guī)劃的影響，同時(shí)也測(cè)試改進(jìn)后的人工蜂群算法的優(yōu)點(diǎn)，使用Matlab軟件進(jìn)行仿真實(shí)驗(yàn)。仿真實(shí)驗(yàn)中設(shè)置編號(hào)為1、2、3的移動(dòng)機(jī)器人和4個(gè)用同心圓包圍的障礙物。移動(dòng)機(jī)器人路徑的起點(diǎn)和目標(biāo)點(diǎn)坐標(biāo)如表1所示，障礙物中心點(diǎn)的坐標(biāo)及危險(xiǎn)區(qū)半徑大小如表2所示。

表1 移動(dòng)機(jī)器人起點(diǎn)和終點(diǎn)坐標(biāo)Tab.1 Mobile robot start and end coordinates

表2 障礙物中心坐標(biāo)及危險(xiǎn)區(qū)半徑Tab.2 Center coordinates of obstacles and radius of danger zone

為了評(píng)估所提方法的有效性，仿真條件設(shè)置如下：

（1）分別采用標(biāo)準(zhǔn)人工蜂群算法（目標(biāo)函數(shù)只考慮路徑距離）和改進(jìn)后的人工蜂群算法（目標(biāo)函數(shù)采用綜合評(píng)價(jià)指標(biāo)）進(jìn)行移動(dòng)機(jī)器人路徑規(guī)劃。

（2）為了比較改進(jìn)前和改進(jìn)后的算法在移動(dòng)機(jī)器人路徑規(guī)劃所得出總長(zhǎng)度和規(guī)劃所需要的總時(shí)間，將兩種算法在相同的環(huán)境下各自運(yùn)行10次。

3.2 仿真結(jié)果

我們?cè)O(shè)置循環(huán)次數(shù)為1500次，種群大小為40，即可行解的數(shù)量為 20，ω3=0.2、-45°≤θ≤45°。 仿真結(jié)果如圖2和圖3所示。

從圖2和圖3的仿真結(jié)果對(duì)比可知，采用綜合評(píng)價(jià)指標(biāo)路徑是要優(yōu)于只考慮路離指標(biāo)的路徑，并且可以改進(jìn)后的人工蜂群算法得到的路徑點(diǎn)的曲折性較標(biāo)準(zhǔn)人工蜂群算法的路徑要小，減小移動(dòng)機(jī)器人的轉(zhuǎn)向負(fù)擔(dān)。

為了證明改進(jìn)后的人工蜂群算法加快了收斂速度，減少了路徑規(guī)劃所花費(fèi)的時(shí)間。將這兩種方法在同樣的實(shí)驗(yàn)條件（同樣的綜合評(píng)價(jià)指標(biāo)）下各自運(yùn)行10次，其結(jié)果如表3所示。

圖2 標(biāo)準(zhǔn)人工蜂群算法的規(guī)劃結(jié)果Fig.2 Programming results of standard artificial bee colony algorithm

圖3 改進(jìn)后的人工蜂群算法的規(guī)劃結(jié)果Fig.3 Programming results of optimized artificial bee colony algorithm

表3 路徑規(guī)劃的總長(zhǎng)度和運(yùn)行時(shí)間Tab.3 Total length and run time of path planning

由表3的數(shù)據(jù)可知，從規(guī)劃所得的路徑總長(zhǎng)度上來(lái)看，兩種路徑規(guī)劃的基本一致。改進(jìn)后的人工蜂群算法所得出路徑總長(zhǎng)度比較穩(wěn)定，標(biāo)準(zhǔn)的人工蜂群算法存在一點(diǎn)浮動(dòng)。在移動(dòng)機(jī)器人路徑規(guī)劃所花費(fèi)的時(shí)間上，采用改進(jìn)后的人工蜂群算法要明顯少于采用標(biāo)準(zhǔn)人工蜂群算法，這樣使得路徑規(guī)劃的效率得到提高。仿真結(jié)果證明人工蜂群算法可以用來(lái)解決移動(dòng)機(jī)器人路徑規(guī)劃問(wèn)題，改進(jìn)的人工蜂群算法在路徑規(guī)劃方面更加穩(wěn)定，并且節(jié)省路徑規(guī)劃所需要的時(shí)間。

4 結(jié)語(yǔ)

針對(duì)路徑規(guī)劃的特點(diǎn)，提出了評(píng)價(jià)路徑的綜合指標(biāo)，利用綜合指標(biāo)去考查移動(dòng)機(jī)器人的路徑規(guī)劃，得出的路徑的綜合評(píng)價(jià)是最優(yōu)的。對(duì)標(biāo)準(zhǔn)人工蜂群算法的食物源搜索方式進(jìn)行改進(jìn)，使算法在初期能夠進(jìn)行全局搜索，而在后期又可以加快收斂速度。仿真結(jié)果表明，利用綜合評(píng)價(jià)標(biāo)準(zhǔn)得出的路徑滿足移動(dòng)機(jī)器人的要求，并且通過(guò)對(duì)算法的改進(jìn)較大的縮短了路徑規(guī)劃的時(shí)間，使得移動(dòng)機(jī)器人工作的更加有效率。

[1]Lei Ulusoy，Alphan，Smith，et al.Optimal multi-robot path planning with temporal logic constraints[C]//International Conference on Intelligent Robots and Systems，IEEE，2011：3087-3092.

[2]Hou Y B，Wang W，et al.Mobile robot path planning and research in the improved artificial immune algorithm[J].Advanced Materials Research，2012，466-467.

[3]Jur P.van den Berg，Mark H.Roadmap-based motion planning in dynamic environments[J].IEEE Transactions on Robotics，2005，21（5）：885-897.

[4]陳超，唐堅(jiān)，靳祖光.一種基于可視圖法導(dǎo)盲機(jī)器人路徑規(guī)劃的研究[J].機(jī)械科學(xué)與技術(shù)，2014，33（4）：490-495.

[5]柴寅，唐秋華，鄧明星.機(jī)器人路徑規(guī)劃的柵格模型構(gòu)建與蟻群算法求解[J].機(jī)械設(shè)計(jì)與制造，2016（4）：178-181.

[6]蔡炯，汪小志.基于粗糙集與遺傳算法的采摘機(jī)器人路徑規(guī)劃[J].農(nóng)機(jī)化研究，2016，38（8）：189-193.

[7]李彥蒼，彭?yè)P(yáng).基于信息熵的改進(jìn)人工蜂群算法[J].控制與決策，2015（6）：1121-1125.

[8]Mansury E，Nikoorar A，Salehi M E.Artificail Bee Colony optimization of ferguson splines for soccer robot path planning[C]//2013 First RSI/ISM International Conference on Robotics and Mechatronics（ICRoM)，2013：85-89

[9]張長(zhǎng)勝.多目標(biāo)人工蜂群算法及遺傳算法的研究與應(yīng)用[M].沈陽(yáng)：東北大學(xué)出版社，2013.

[10]竇連航.基于人工蜂群算法的多機(jī)器人路徑規(guī)劃研究[D].上海：上海大學(xué)，2015.