機(jī)器人導(dǎo)航的自主選擇搜索策略蜂群規(guī)劃算法

王明超

（無錫工藝職業(yè)技術(shù)學(xué)院，江蘇 宜興 214200）

1 引言

當(dāng)前機(jī)器人不僅應(yīng)用領(lǐng)域越來越廣，而且相關(guān)的智能技術(shù)研究也越來越深，使機(jī)器人在人類生產(chǎn)和生活種日益重要。機(jī)器人導(dǎo)航技術(shù)是移動(dòng)機(jī)器人一切工作的基礎(chǔ)，決定了機(jī)器人的安全和效率[1]。因此研究機(jī)器人智能導(dǎo)航問題具有明顯的安全意義和經(jīng)濟(jì)意義。

導(dǎo)航技術(shù)分為目標(biāo)定位、路徑規(guī)劃、環(huán)境建模等3 個(gè)子技術(shù)，研究導(dǎo)航路徑智能規(guī)劃問題。按照導(dǎo)航路徑規(guī)劃方法出現(xiàn)時(shí)間劃分，可以將路徑規(guī)劃分為傳統(tǒng)路徑規(guī)劃方法和智能算法規(guī)劃方法。傳統(tǒng)路徑規(guī)劃方法包括柵格法[2]、拓?fù)浞╗3]、可視圖法[4]、人工勢(shì)場(chǎng)法[5]等，其共同特點(diǎn)是使用簡(jiǎn)單的幾何數(shù)學(xué)模型完成路徑規(guī)劃。智能算法規(guī)劃方法包括基于遺傳算法規(guī)劃方法、基于蟻群算法規(guī)劃方法、基于神經(jīng)網(wǎng)絡(luò)規(guī)劃方法、基于粒子群算法規(guī)劃等，此類方法共同特點(diǎn)是將路徑規(guī)劃問題轉(zhuǎn)化為優(yōu)化問題，使用智能仿生算法進(jìn)行優(yōu)化。文獻(xiàn)[6]改進(jìn)了蟻群算法的轉(zhuǎn)移概率和信息素更新策略，提出了機(jī)器人路徑的自適應(yīng)蟻群算法規(guī)劃策略，降低了工作路徑長(zhǎng)度；文獻(xiàn)[7]使用萊維飛行優(yōu)化粒子群算法，優(yōu)化了焊接機(jī)器人工作路徑；文獻(xiàn)[8]建立了多個(gè)優(yōu)化目標(biāo)，分別為焊接質(zhì)量函數(shù)、機(jī)器人運(yùn)動(dòng)平穩(wěn)性函數(shù)、雙機(jī)器人碰撞函數(shù)，使用多目標(biāo)遺傳算法進(jìn)行求解，獲得了雙機(jī)器人協(xié)調(diào)焊接路徑?？傊?，機(jī)器人導(dǎo)航智能化程度越來越高，正朝著多傳感器融合、多算法融合、多機(jī)器人分工協(xié)作等方向發(fā)展。

為了提高機(jī)器人導(dǎo)航路徑的質(zhì)量和規(guī)劃速度，提出了自主選擇搜索策略蜂群算法的規(guī)劃方法。通過坐標(biāo)旋轉(zhuǎn)法將二維規(guī)劃問題轉(zhuǎn)化為一維，使用自主選擇搜索策略蜂群算法搜索最優(yōu)路徑點(diǎn)，達(dá)到了減少路徑長(zhǎng)度和提高規(guī)劃速度的目的。

2 自主選擇搜索策略蜂群算法

2.1 人工蜂群算法

人工蜂群算法將蜜蜂分為三類，分別為引領(lǐng)蜂、觀察蜂和偵查蜂，不同蜜蜂使用不同的蜜源搜索方式，通過分工協(xié)作發(fā)揮群體智能實(shí)現(xiàn)最優(yōu)蜜源搜索。

（1）蜜蜂位置初始化。蜂群規(guī)模記為N，生存維度記為D，蜂群以隨機(jī)的方式進(jìn)行位置初始化，為：

（2）引領(lǐng)蜂蜜源搜索策略。引領(lǐng)蜂使用交叉方式搜索蜜源，對(duì)于蜜蜂i，隨機(jī)選擇另一個(gè)體k≠i，則引領(lǐng)蜂蜜源搜索公式為：

（3）觀察蜂蜜源搜索策略。引領(lǐng)蜂通過搖擺舞將蜜源濃度信息傳遞給觀察蜂，觀察蜂依據(jù)蜜源濃度選擇觀察蜂，即：

式中：pi—引領(lǐng)蜂的被選概率；NB—引領(lǐng)蜂數(shù)量；fiti—第i 只引領(lǐng)蜂所在位置蜜源濃度。分析式（3）可知，引領(lǐng)蜂所在位置蜜源濃度越高則被選概率越大，保證了較優(yōu)蜜源附近區(qū)域的細(xì)致搜索。觀察蜂選擇引領(lǐng)蜂后，與引領(lǐng)蜂一起進(jìn)行小范圍細(xì)致搜索，蜜源搜索方式與引領(lǐng)蜂完全一致。

（4）偵查蜂蜜源搜索策略。當(dāng)引領(lǐng)蜂或觀察蜂在某一蜜源附近搜索次數(shù)達(dá)到設(shè)定次數(shù)且蜜源濃度沒有明顯提高時(shí)，則蜜蜂放棄此處蜜源同時(shí)轉(zhuǎn)化為偵查蜂，在搜索區(qū)域內(nèi)進(jìn)行大范圍隨機(jī)搜索，即：

2.2 多方式搜索策略

進(jìn)化論表明蜂群中蜜蜂的搜索行為受環(huán)境因素的影響，不同環(huán)境對(duì)應(yīng)的搜索行為也不一致。蜜蜂對(duì)環(huán)境的認(rèn)知信息有多種來源，包括個(gè)體自身認(rèn)知信息、群體最佳個(gè)體的認(rèn)知信息、種群平均認(rèn)知信息和其他個(gè)體認(rèn)知信息等，多種認(rèn)知信息來源對(duì)應(yīng)多種方式的蜜源搜索策略。在此需要強(qiáng)調(diào)的是，此多種方式的蜜源搜索策略適用于引領(lǐng)蜂或觀察蜂，偵查蜂的蜜源搜索方式保持不變。

（1）基于自身認(rèn)知、最佳個(gè)體認(rèn)知、其他個(gè)體認(rèn)知的蜜源搜索方式。此方法參考粒子群算法中的信息獲取方式，種群中蜜蜂參考自身對(duì)環(huán)境的認(rèn)知、種群中最優(yōu)認(rèn)知和其他個(gè)體的認(rèn)知，綜合形成自身的蜜源搜索方式，為：

（2）基于群體平均認(rèn)知的蜜源搜索方式。如同人類社會(huì)中的“從眾”心理，種群中的個(gè)體也具有一定的趨同性，也即蜜蜂的搜索行為受種群共同認(rèn)知的影響。使用所有蜜蜂的位置質(zhì)心表示種群平均認(rèn)知，則基于種群平均認(rèn)知的搜索方式為：

式中：pj—第j 維的質(zhì)心。

（3）基于其他個(gè)體認(rèn)知的蜜源搜索方式。這種隨機(jī)選取個(gè)體獲取認(rèn)知信息的方式類似于遺傳算法中的個(gè)體變異，此種信息獲取方式與混沌理論相比更具有方向性，對(duì)應(yīng)的蜜源搜索方式為：

式中：r1≠r2≠r3—隨機(jī)選擇的三個(gè)不同個(gè)體。

2.3 搜索策略自主選擇方法

2.2 節(jié)給出了3 種環(huán)境認(rèn)知方式和相應(yīng)的蜜源搜索方式，加上式（2）給出的原算法搜索方式，共有4 種蜜源搜索方式供引領(lǐng)蜂和觀察蜂選擇。在此提出不同蜜源搜索方法的即時(shí)價(jià)值和后效價(jià)值，通過即時(shí)價(jià)值和后效價(jià)值計(jì)算不同蜜源選擇策略的選擇概率，實(shí)現(xiàn)蜜蜂對(duì)搜索策略的自主選擇。

（1）不同蜜源搜索策略的即時(shí)價(jià)值。后文中將此算法應(yīng)用于機(jī)器人導(dǎo)航路徑規(guī)劃，因此將目標(biāo)函數(shù)f（x，t）定義為路徑長(zhǎng)度，則蜜蜂i 對(duì)應(yīng)的目標(biāo)函數(shù)f（xi，t）越小說明蜜蜂i 越優(yōu)。蜜源搜索策略的即時(shí)價(jià)值定義為迭代一次后目標(biāo)函數(shù)的減小程度，即：

式中：Valik（t）—粒子i 選擇蜜源搜索策略k 迭代后的即時(shí)價(jià)值；f（xi，t-1）—粒子i 迭代t-1 次時(shí)的目標(biāo)函數(shù)值；fk（xi，t）—粒子i 選擇搜索策略k 迭代t 次時(shí)的目標(biāo)函數(shù)值。當(dāng)Valik（t）＞0 時(shí)說明選擇搜索策略k 迭代一次后蜜源濃度有所提高，當(dāng)Valik（t）=0 時(shí)說明選擇搜索策略k 迭代一次后蜜源濃度沒有提高。

（2）不同蜜源搜索策略的后效價(jià)值。信心上界算法[9]在計(jì)算機(jī)棋盤程序中用于計(jì)算不同落子點(diǎn)的未來價(jià)值，在圍棋程序中取得了很好的效果。參考這一思想，使用信息上界算法計(jì)算蜜源選擇策略的后效價(jià)值，為：

（3）搜索策略自主選擇方法。首先使用不同搜索策略的即時(shí)價(jià)值、后效價(jià)值和歷史經(jīng)驗(yàn)計(jì)算搜索策略的得分，而后根據(jù)得分構(gòu)造不同搜索策略的選擇概率。使用即時(shí)價(jià)值、后效價(jià)值和歷史經(jīng)驗(yàn)構(gòu)造搜索策略的得分，為：

蜜蜂i 根據(jù)式（11）計(jì)算不同搜索策略的選擇概率，并最終選擇概率最大的搜索策略為下一次迭代的搜索策略，從而在迭代時(shí)獲得最佳的即時(shí)價(jià)值和后效價(jià)值。通過以上方式，蜜蜂完成了對(duì)搜索策略的自主選擇。

2.4 自主選擇搜索策略蜂群算法流程

根據(jù)人工蜂群算法原理和多方式蜜源搜索自主選擇策略，制定自主選擇搜索策略蜂群算法流程為：

（1）初始化人工蜂群算法參數(shù)和蜜蜂初始位置；

（2）根據(jù)蜜蜂位置對(duì)應(yīng)的目標(biāo)函數(shù)值，將蜜蜂區(qū)分為引領(lǐng)蜂和觀察蜂；

（3）引領(lǐng)蜂和觀察蜂計(jì)算使用不同蜜源搜索策略的即時(shí)價(jià)值、后效價(jià)值和選擇概率；

（4）引領(lǐng)蜂和觀察蜂自主選擇概率最大的蜜源搜索策略更新位置，若新位置蜜源優(yōu)于原位置則選擇新蜜源，否則選擇舊蜜源；

（5）引領(lǐng)蜂和觀察蜂是否滿足轉(zhuǎn)化為偵查蜂的條件？若滿足則轉(zhuǎn)化為偵查蜂，按照式（4）進(jìn)行搜索；若不滿足則繼續(xù)按照多搜索策略進(jìn)行搜索；

（6）算法是否達(dá)到最大迭代次數(shù)？若是則結(jié)束；若否則轉(zhuǎn)至（3）。

2.5 算法性能測(cè)試

為了驗(yàn)證自主選擇搜索策略蜂群算法的搜索性能，選擇具有代表性的3 個(gè)測(cè)試函數(shù)，如表1 所示。3 個(gè)測(cè)試函數(shù)的空間維度均設(shè)置為n=30。分別使用自主選擇搜索策略蜂群算法（Choose Searching Strategy Independently Bee Colony Algorithm，CSSIBC）、人工蜂群算法（Artificial Bee Colony Algorithm，ABC）、改進(jìn)人工蜂群算法[10]（Modified Artificial Bee Colony Algorithm，MABC）對(duì)測(cè)試函數(shù)進(jìn)行尋優(yōu)。

表1 測(cè)試函數(shù)Tab.1 Testing Function

性能測(cè)試的實(shí)驗(yàn)環(huán)境為：Windows 7 操作系統(tǒng)，Intel 酷睿i5處理器，2.5Hz 主頻，4G 內(nèi)存，仿真軟件為Matlab R2014a。算法參數(shù)設(shè)置為：種群規(guī)模N=30、迭代次數(shù)itermax=1000、個(gè)體未來價(jià)值和全局未來價(jià)值的平衡系數(shù)α=0.5；改進(jìn)人工蜂群算法參數(shù)設(shè)置參照文獻(xiàn)[10]。每種算法對(duì)3 個(gè)測(cè)試函數(shù)獨(dú)立運(yùn)行10 次，統(tǒng)計(jì)尋優(yōu)結(jié)果的最優(yōu)值、最差值、平均值、方差、迭代次數(shù)和運(yùn)行時(shí)間，結(jié)果如表2 所示。

表2 對(duì)測(cè)試函數(shù)的尋優(yōu)結(jié)果Tab.2 Optimizing Result for Testing Function

從表2 中對(duì)測(cè)試函數(shù)的尋優(yōu)結(jié)果可以看出，在對(duì)3 個(gè)測(cè)試函數(shù)的尋優(yōu)中，自主選擇搜索策略蜂群算法每次都能夠搜索到最優(yōu)值，說明了其強(qiáng)大的尋優(yōu)能力。從尋優(yōu)精度和穩(wěn)定性等方面看，CSSIBC 算法最優(yōu)，其次為MABC 算法，ABC 算法最差。從迭代次數(shù)和運(yùn)行時(shí)間看，CSSIBC 算法搜索到最優(yōu)值時(shí)的迭代次數(shù)最小、耗時(shí)也最少，但是就耗時(shí)與迭代次數(shù)的比值來看，CSSIBC 算法最大，說明CSSIBC 算法單次迭代時(shí)的耗時(shí)最多，這是因?yàn)槊看蔚鷷r(shí)對(duì)搜索策略的選擇過程耗時(shí)較大。總的來講，自主選擇搜索策略蜂群算法的尋優(yōu)精度最高、尋優(yōu)穩(wěn)定性最好，同時(shí)耗時(shí)也最少。

3 路徑規(guī)劃與仿真分析

3.1 路徑規(guī)劃方案與性能指標(biāo)

機(jī)器人工作空間設(shè)定為二維空間且為靜態(tài)環(huán)境，本節(jié)使用坐標(biāo)旋轉(zhuǎn)法將路徑的二維規(guī)劃問題轉(zhuǎn)化為一維規(guī)劃問題，如圖1所示。圖中OXY 坐標(biāo)系為原始坐標(biāo)系，稱其為慣性坐標(biāo)系，S 為路徑起點(diǎn)，T 為路徑目標(biāo)點(diǎn)。為了實(shí)現(xiàn)問題降維，以S 點(diǎn)為原點(diǎn)，以ST 方向?yàn)閄′軸，以ST 垂直方向?yàn)閅′軸，從而建立局部坐標(biāo)系SX′Y′。使用L1～LD共條平行線將ST 等分為D+1 段，那么路徑規(guī)劃可描述為在等分線L1～LD上確定各自的Y′坐標(biāo)值，將規(guī)劃點(diǎn)順次連接后進(jìn)行平滑處理就得到了規(guī)劃路徑，從而實(shí)現(xiàn)了路徑規(guī)劃由二維降為一維。

圖1 坐標(biāo)轉(zhuǎn)換方法Fig.1 Coordinate Transform Method

記X′軸與X 軸夾角為θ，則以S 點(diǎn)為頂點(diǎn)順時(shí)針旋轉(zhuǎn)角度θ，并將坐標(biāo)原點(diǎn)平移，就可以實(shí)現(xiàn)坐標(biāo)間的轉(zhuǎn)換。

慣性坐標(biāo)系任意一點(diǎn)（x，y）與局部坐標(biāo)系相應(yīng)點(diǎn)（x′，y′）間的轉(zhuǎn)換關(guān)系為：

式中：（xs，ys）—起始點(diǎn)S 坐標(biāo)。

使用路徑長(zhǎng)度作為機(jī)器人路徑規(guī)劃的唯一指標(biāo)，根據(jù)上文的路徑規(guī)劃方案，得到平行線間距為△l=‖ST‖/（D+1），則機(jī)器人路徑長(zhǎng)度為：

3.2 路徑規(guī)劃仿真分析

本節(jié)進(jìn)行機(jī)器人路徑規(guī)劃的仿真環(huán)境和參數(shù)設(shè)置與2.5 節(jié)保持一致。設(shè)置了兩種環(huán)境下的仿真驗(yàn)證，分別使用自主選擇搜索策略蜂群算法、人工蜂群算法進(jìn)行路徑規(guī)劃，每種算法獨(dú)立運(yùn)行10 次，兩種環(huán)境下搜索到的最優(yōu)路徑，如圖2 所示。圖中實(shí)線為自主選擇搜索策略蜂群算法規(guī)劃的路徑，虛線為人工蜂群算法規(guī)劃的路徑。路徑起點(diǎn)設(shè)置為（20，20），路徑目標(biāo)點(diǎn)設(shè)置為（190，190）。從圖中可以看出，自主選擇搜索策略蜂群算法規(guī)劃的路徑長(zhǎng)度明顯短于人工蜂群算法，人工蜂群算法為躲避障礙物而規(guī)劃的路徑存在較多的冗余曲折路徑。為了進(jìn)一步分析兩種算法在機(jī)器人路徑規(guī)劃中的性能，給出迭代過程中路徑長(zhǎng)度隨迭代次數(shù)的變化曲線，如圖3 所示。圖中虛線為人工蜂群算法的迭代曲線，實(shí)線為自主選擇搜索策略蜂群算法的迭代曲線。

圖2 兩種環(huán)境下的規(guī)劃路徑Fig.2 Path Planned Under Two Environment

圖3 兩種環(huán)境下的迭代曲線Fig.3 Iterating Curve Under Two Environment

從圖3 可以看出，在環(huán)境一和環(huán)境二兩種情況下，自主選擇搜索策略蜂群算法搜索到最優(yōu)值的迭代次數(shù)明顯少于人工蜂群算法，且收斂值也遠(yuǎn)小于人工蜂群算法。經(jīng)統(tǒng)計(jì)，在環(huán)境一中，自主選擇搜索策略蜂群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為389.12，人工蜂群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為441.36，比這里的算法增加了13.43%；自主選擇搜索策略蜂群算法搜索到最優(yōu)值的迭代次數(shù)為176 次，人工蜂群算法搜索到最優(yōu)值的迭代次數(shù)為289 次，比這里的算法增加了64.20%。在環(huán)境二中，自主選擇搜索策略蜂群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為263.72，人工蜂群算法規(guī)劃的最優(yōu)路徑長(zhǎng)度為321.56，比這里的算法增加了21.93%；自主選擇搜索策略蜂群算法搜索到最優(yōu)值的迭代次數(shù)為195 次，人工蜂群算法搜索到最優(yōu)值的迭代次數(shù)為302 次，比這里的算法增加了54.87%。綜合以上數(shù)據(jù)可以看出，在不同環(huán)境的路徑規(guī)劃中，自主選擇搜索策略蜂群算法規(guī)劃的路徑長(zhǎng)度遠(yuǎn)遠(yuǎn)優(yōu)于人工蜂群算法，搜索到最優(yōu)值時(shí)的迭代次數(shù)也遠(yuǎn)遠(yuǎn)優(yōu)于人工蜂群算法，這是因?yàn)樽灾鬟x擇搜索策略蜂群算法設(shè)計(jì)了多種蜜源搜索方式，并根據(jù)不同蜜源搜索方式的即時(shí)價(jià)值和后效價(jià)值給出了自主選擇方法，使算法每次迭代均使用最有價(jià)值的搜索方式，因此規(guī)劃的路徑質(zhì)量和迭代次數(shù)都遠(yuǎn)遠(yuǎn)優(yōu)于人工蜂群算法。

4 結(jié)論

研究了全局靜態(tài)環(huán)境下的機(jī)器人導(dǎo)航路徑規(guī)劃問題，使用坐標(biāo)旋轉(zhuǎn)法將二維問題轉(zhuǎn)化為一維，提出了自主選擇搜索策略蜂群算法用于路徑規(guī)劃，經(jīng)驗(yàn)證得出了以下結(jié)論：（1）自主選擇搜索策略蜂群算法的尋優(yōu)速度和尋優(yōu)精度遠(yuǎn)遠(yuǎn)優(yōu)于人工蜂群算法；（2）多種蜜源搜索方式相結(jié)合，并根據(jù)即時(shí)價(jià)值和后效價(jià)值對(duì)搜索方式自主選擇，能夠提高算法的搜索性能。