基于改進細菌覓食算法的機器人路徑規(guī)劃

李歡++唐江鋒++劉偉

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

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

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

1.引言

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

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

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

2.1 細菌覓食算法

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

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

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

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

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

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

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

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

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

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

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

3 仿真實驗及其結(jié)果

為驗證上述方法的正確性和有效性，利用Matlab7.0軟件進行仿真實驗。在實驗中，小圓圈形表示起始點，小正方形表示目標(biāo)位置，小六邊形表示細菌。仿真參數(shù)設(shè)置為：細菌個數(shù)為s=26，細菌趨化次數(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，細菌運動起點為[0 0]，運動目標(biāo)點為[10 10]，為保證細菌能夠盡可能的找到所有路徑，其運動步長與方向均為隨機值。

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

4 結(jié)論

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

參考文獻

[1] 曲道奎， 杜振軍， 徐殿國， 等. 移動機器人路徑規(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]吳曉濤，孫增圻.用遺傳算法進行路徑規(guī)劃.清華大學(xué)學(xué)報（自然科學(xué)版）， 1995， 35（5）： 14-19.