李歡++唐江鋒++劉偉

[摘 要]細(xì)菌覓食算法是一種仿生學(xué)尋優(yōu)算法。本文根據(jù)傳統(tǒng)的細(xì)菌算法，對(duì)其與力場(chǎng)相結(jié)合，應(yīng)用于機(jī)器人路徑規(guī)劃領(lǐng)域。機(jī)器人在引力的作用下以定步長(zhǎng)變方向向目標(biāo)點(diǎn)運(yùn)動(dòng)，引入斥力作為躲避避障物的條件，引進(jìn)迭代終止條件，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了其可行性。

[關(guān)鍵詞]細(xì)菌覓食算法；路徑規(guī)劃；力場(chǎng)

中圖分類號(hào)：TP301.6 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-914X（2016）03-0122-01

1.引言

路徑規(guī)劃[1]是移動(dòng)機(jī)器人設(shè)計(jì)領(lǐng)域中的核心技術(shù)之一。移動(dòng)機(jī)器人路徑規(guī)劃是指在有一定障礙物的環(huán)境條件中，找到一條從給定起點(diǎn)到目標(biāo)點(diǎn)的適當(dāng)路徑，使機(jī)器人能夠安全無(wú)碰的繞過(guò)所有障礙物。機(jī)器人路徑規(guī)劃一般分為全局路徑規(guī)劃和局部路徑規(guī)劃兩種。全局路徑規(guī)劃是指環(huán)境信息已知，從起點(diǎn)到目標(biāo)點(diǎn)的無(wú)碰路徑規(guī)劃，常用的全局路徑規(guī)劃算法有可視圖法、柵格法[2]、自由空間法等。局部路徑規(guī)劃是指環(huán)境信息未知，機(jī)器人根據(jù)傳感器檢測(cè)到的環(huán)境信息，實(shí)時(shí)在線的調(diào)整機(jī)器人行走路線，最終安全無(wú)碰的到達(dá)目標(biāo)點(diǎn)，常用的局部路徑規(guī)劃算法有人工勢(shì)場(chǎng)法[3]、模糊算法、蟻群算法、粒子群算法以及遺傳算法等。

近年來(lái)，基于人工智能的仿生學(xué)算法，逐步融合甚至取代傳統(tǒng)算法應(yīng)用于機(jī)器人路徑規(guī)劃領(lǐng)域。比如，模仿螞蟻覓食行為而提出的蟻群算法根據(jù)螞蟻覓食過(guò)程中釋放的信息素濃度尋找最優(yōu)路徑；遺傳算法根據(jù)生物學(xué)中自然界物競(jìng)天擇適者生存的規(guī)律演化而來(lái)的啟發(fā)式隨機(jī)搜索算法。細(xì)菌算法[4]是近幾年出現(xiàn)的仿生學(xué)算法，它是根據(jù)細(xì)菌的覓食行為提出的，由于其與機(jī)器人路徑尋優(yōu)有很大的相似性，故本文把細(xì)菌算法引入機(jī)器人路徑規(guī)劃領(lǐng)域，并通過(guò)仿真實(shí)驗(yàn)驗(yàn)證了其可行性。

2.基于細(xì)菌覓食算法的路徑規(guī)劃

2.1 細(xì)菌覓食算法

細(xì)菌覓食算法，又稱細(xì)菌覓食優(yōu)化算法，它是由K.M.Passino在2002年根據(jù)大腸桿菌在人體腸道內(nèi)的覓食行為提出的，該算法由于具有群體智能并行搜索、易跳出局部極小值等優(yōu)點(diǎn)，成為生物啟發(fā)式搜索算法領(lǐng)域的研究熱點(diǎn)。在人體中，大腸桿菌周身長(zhǎng)滿鞭毛，大腸桿菌通過(guò)體表鞭毛的擺動(dòng)達(dá)到在環(huán)境中移動(dòng)的目的。當(dāng)大腸桿菌聚集區(qū)的食物消耗殆盡，細(xì)菌便會(huì)隨機(jī)選擇一個(gè)方向運(yùn)動(dòng)，以尋找新的食物源，如果食物豐富便會(huì)停下來(lái)，直到食物消耗殆盡，細(xì)菌便會(huì)沿著上一次的方向繼續(xù)向前運(yùn)動(dòng)；若是遇到無(wú)法通行的地方或者找尋一段距離未發(fā)現(xiàn)食物，細(xì)菌便會(huì)改變搜索方向，重新尋找食物。如果食物豐富能夠滿足細(xì)菌的繁殖需要，細(xì)菌便會(huì)進(jìn)行個(gè)體的分裂，壯大菌落；若是食物稀少細(xì)菌變化死亡。根據(jù)大腸桿菌的這種覓食行為，提出細(xì)菌覓食算法，其運(yùn)動(dòng)方式主要有：趨化、復(fù)制和驅(qū)散三個(gè)步驟。

趨化是指細(xì)菌向食物營(yíng)養(yǎng)富集的地方運(yùn)動(dòng)的過(guò)程，趨化過(guò)程由游動(dòng)和翻轉(zhuǎn)兩個(gè)動(dòng)作組成。游動(dòng)是指細(xì)菌向指定方向運(yùn)動(dòng)一定的距離；翻轉(zhuǎn)是指改變細(xì)菌游動(dòng)的方向。在細(xì)菌覓食算法中，用P（i，j，k，l）代表第l次驅(qū)散第k次復(fù)制第j次趨化運(yùn)動(dòng)中第i個(gè)細(xì)菌的位置坐標(biāo)。C（i，k）表示單位游動(dòng)步長(zhǎng)。因此，在每一次的趨化運(yùn)動(dòng)中，細(xì)菌的位置可表示為：

其中，Δ（i）表示細(xì)菌的游動(dòng)的方向，可根據(jù)round函數(shù)隨機(jī)產(chǎn)生，亦可根據(jù)目標(biāo)性能自行設(shè)定。

復(fù)制操作是指在完成趨化操作時(shí)，細(xì)菌進(jìn)行繁衍。在細(xì)菌繁殖前，對(duì)每個(gè)細(xì)菌個(gè)體進(jìn)行健康度評(píng)定。保留健康度較好的半數(shù)細(xì)菌，并將這些細(xì)菌一分為二分裂復(fù)制，復(fù)制后保留母細(xì)菌的特性，即保留運(yùn)動(dòng)方向和運(yùn)動(dòng)步長(zhǎng)，健康度較差的半數(shù)細(xì)菌便被淘汰。細(xì)菌健康度評(píng)價(jià)公式為：

其中，Nc表示細(xì)菌趨化的次數(shù)。

在細(xì)菌完成趨化和復(fù)制操作后，經(jīng)行消除和驅(qū)散操作。去除掉在復(fù)制過(guò)程中健康值較差的半數(shù)細(xì)菌，再以某一規(guī)則選取經(jīng)過(guò)復(fù)制操作的細(xì)菌，將其驅(qū)散到其他位置，這樣，被驅(qū)散的細(xì)菌便有了新的位置，可以進(jìn)行新的覓食行為。通過(guò)細(xì)菌驅(qū)散操作，減少了細(xì)菌陷入局部最優(yōu)解的可能性，但也驅(qū)散了接近全局最優(yōu)解的部分細(xì)菌。

2.2 改進(jìn)細(xì)菌覓食算法路徑規(guī)劃

在機(jī)器人路徑規(guī)劃領(lǐng)域中，一方面要保證機(jī)器人能夠持續(xù)向目標(biāo)位置運(yùn)動(dòng)，另一方面要保證機(jī)器人避開所走路徑上的所有障礙物，同時(shí)，要盡可能的使機(jī)器人走過(guò)的總路程最短。為保證細(xì)菌能夠持續(xù)向目標(biāo)運(yùn)動(dòng)，引入引力作為其適應(yīng)度函數(shù)：

式中，α為引力系數(shù)，d（P，T）為當(dāng)前細(xì)菌所處位置與目標(biāo)點(diǎn)位置的距離。細(xì)菌在引力的作用下持續(xù)向目標(biāo)點(diǎn)運(yùn)動(dòng)，當(dāng)細(xì)菌到達(dá)目標(biāo)點(diǎn)以后，引力為零，細(xì)菌停止運(yùn)動(dòng)，進(jìn)行復(fù)制、驅(qū)散操作。

為保證細(xì)菌在運(yùn)動(dòng)過(guò)程中能夠有效的避開障礙物，引入斥力函數(shù)進(jìn)行障礙物的躲避，障礙物大小對(duì)細(xì)菌的影響程度不同，障礙物越大，則對(duì)細(xì)菌的阻礙越大，設(shè)置斥力函數(shù)為：

式中，Radius 表示障礙物的最大半徑，即為障礙物中心到四周最遠(yuǎn)點(diǎn)距離；Raffect 表示障礙物的影響距離。根據(jù)斥力的大小情況，細(xì)菌實(shí)時(shí)調(diào)整運(yùn)動(dòng)方向，有效避開障礙物。

3 仿真實(shí)驗(yàn)及其結(jié)果

為驗(yàn)證上述方法的正確性和有效性，利用Matlab7.0軟件進(jìn)行仿真實(shí)驗(yàn)。在實(shí)驗(yàn)中，小圓圈形表示起始點(diǎn)，小正方形表示目標(biāo)位置，小六邊形表示細(xì)菌。仿真參數(shù)設(shè)置為：細(xì)菌個(gè)數(shù)為s=26，細(xì)菌趨化次數(shù)Nc=100，復(fù)制次數(shù)為Nre=4，驅(qū)散次數(shù)為Ned=2，障礙物中心坐標(biāo)為xo=[3.5 2 6 7 7 9]，yo=[3 5 5 8 10 5 ]，障礙物半徑Radius=[0.4 0.3 0.6 0.5 0.5 0.5]，障礙物影響距離Raffect=1，d_att、h_rep、om_att和om_rep均為0.05，細(xì)菌運(yùn)動(dòng)起點(diǎn)為[0 0]，運(yùn)動(dòng)目標(biāo)點(diǎn)為[10 10]，為保證細(xì)菌能夠盡可能的找到所有路徑，其運(yùn)動(dòng)步長(zhǎng)與方向均為隨機(jī)值。

實(shí)驗(yàn)結(jié)果如圖1、圖2所示。圖1是細(xì)菌進(jìn)行趨化操作，尋找到達(dá)目標(biāo)點(diǎn)的安全路徑，細(xì)菌隨機(jī)選擇運(yùn)動(dòng)方向，尋找盡可能的能夠到達(dá)目標(biāo)點(diǎn)的路徑，從而避免了因單一目標(biāo)陷入局部最小值不能到達(dá)目標(biāo)點(diǎn)的情況。圖2是從所有路徑中選出來(lái)的最優(yōu)路徑，路徑中在小范圍內(nèi)存在許多的彎曲點(diǎn)，對(duì)其進(jìn)行逼近，便可得到一條光滑的、最優(yōu)的路徑。通過(guò)仿真實(shí)驗(yàn)，說(shuō)明本文采用的細(xì)菌覓食算法能夠安全無(wú)碰的到達(dá)目標(biāo)點(diǎn)，尋找出一條最優(yōu)路徑，完成機(jī)器人路徑規(guī)劃的要求。

4 結(jié)論

本文采用的改進(jìn)細(xì)菌覓食算法采用引力場(chǎng)作為適應(yīng)度函數(shù)，引入障礙物大小與影響距離作為排斥力，分步尋找最優(yōu)路徑的方法，具有能夠快速的找到一條安全無(wú)碰的最優(yōu)路徑的能力，能夠很好的用于機(jī)器人路徑規(guī)劃，本算法采用的靜態(tài)仿真環(huán)境，同樣也可以應(yīng)用與動(dòng)態(tài)環(huán)境的避障研究。在以后的研究中，還可以對(duì)其操作步驟進(jìn)行優(yōu)化，與其他算法相結(jié)合，進(jìn)一步提高其可行性和可靠性。

參考文獻(xiàn)

[1] 曲道奎， 杜振軍， 徐殿國(guó)， 等. 移動(dòng)機(jī)器人路徑規(guī)劃方法研究[J]. 2008.

[2] Lee. Visibility of a simple polygon[J]. Computer version， Graphics and Image processing， 1983，2292）：207-221.

[3] Yogita Gigras， Kusum Gupta. Artificial Intelligence in Robot Path Planning[J].International Journal of Soft Computing and Engineering.2012（2）：171-174.

[4]吳曉濤，孫增圻.用遺傳算法進(jìn)行路徑規(guī)劃.清華大學(xué)學(xué)報(bào)（自然科學(xué)版）， 1995， 35（5）： 14-19.