，，，，

(1.蘇州科技大學(xué) 江蘇省建筑智慧節(jié)能重點(diǎn)實(shí)驗(yàn)室，江蘇 蘇州 215009; 2.常州工學(xué)院 計(jì)算機(jī)信息工程學(xué)院，江蘇 常州 213002)

0 引言

近年來(lái)，隨著計(jì)算機(jī)技術(shù)的迅速發(fā)展，移動(dòng)機(jī)器人的研究日新月異。在機(jī)器人的研究領(lǐng)域中，常常需要規(guī)劃出一條行駛軌跡最優(yōu)、運(yùn)行代價(jià)最少的路線。機(jī)器人路徑優(yōu)化算法主要有貪心算法、模擬退火算法、遺傳算法、禁忌搜索算法、神經(jīng)網(wǎng)絡(luò)及人工勢(shì)場(chǎng)法等方法。針對(duì)模擬退火算法尋優(yōu)效率低的問(wèn)題，鞏敦衛(wèi)等人通過(guò)引入脫障算子和一致尋優(yōu)算子，提出了一種狀態(tài)產(chǎn)生方法[1]。然后該算法的計(jì)算復(fù)雜度較高。針對(duì)基本遺傳算法存在收斂速度慢的不足，王雷等人提出了一種改進(jìn)自適應(yīng)遺傳算法[2]。然而該算法的路徑規(guī)劃準(zhǔn)確性不高，容易與障礙物發(fā)生碰撞。杜宗宗等人提出了一種遺傳模擬退火算法[3]。但忽略了在實(shí)際環(huán)境中的驗(yàn)證。

針對(duì)上述算法中存在的在不同環(huán)境下，缺乏普遍適應(yīng)性的問(wèn)題。本文通過(guò)柵格法建立場(chǎng)地環(huán)境，針對(duì)機(jī)器人移動(dòng)路徑規(guī)劃，提出了一種改進(jìn)模擬退火算法，并且通過(guò)改變環(huán)境系數(shù)進(jìn)行仿真實(shí)驗(yàn)，驗(yàn)證了該算法能夠適用于不同的環(huán)境。

1 基于柵格法的環(huán)境建模

本文通過(guò)柵格法進(jìn)行場(chǎng)地環(huán)境建模。柵格法將場(chǎng)地環(huán)境進(jìn)行切割，分成一定數(shù)量同等大小的方塊，每個(gè)方塊都需要存放對(duì)應(yīng)區(qū)域的信息。因此分割的份數(shù)越多，對(duì)實(shí)際場(chǎng)地描述也越精細(xì)，但相應(yīng)的信息存儲(chǔ)空間開(kāi)銷(xiāo)增大，并且路徑規(guī)劃難度提高。

障礙物和自由區(qū)域由計(jì)算機(jī)隨機(jī)生成，但是需要根據(jù)機(jī)器人一般的工作環(huán)境，設(shè)定障礙物占據(jù)整個(gè)環(huán)境的比例以及障礙物分布的集中性。障礙物占據(jù)比例，在實(shí)際環(huán)境中是指投影到二維平面上障礙物總體面積占據(jù)環(huán)境總面積的比例，在柵格圖上則是黑色格子數(shù)目占總格子數(shù)目的比例。障礙物分布的集中性，描述障礙物成塊分布的程度。反映到柵格圖上就是若干黑色格子聚集在一起情況的多少。

機(jī)器人最理想的路線是由起始點(diǎn)Start直接指向終點(diǎn)End。本文參照正態(tài)分布刻畫(huà)上述兩種環(huán)境因素，且設(shè)定在圖形中間區(qū)域產(chǎn)生障礙物的概率比周邊高。用數(shù)學(xué)語(yǔ)言描述：設(shè)定任一格子到環(huán)境中心位置的距離為Distance，該格子是障礙物的概率為P，公式(1)中，λ為常系數(shù)，λ越大障礙物占據(jù)的比例越高，方差項(xiàng)σ調(diào)整障礙物集中分布的趨勢(shì)，σ越小，障礙物越集中在中心區(qū)域。

圖1是減小σ得到的結(jié)果，從圖中可以看出障礙物分布具有集中性。但是需要注意，如果λ和σ設(shè)置不合理，障礙物過(guò)多，會(huì)導(dǎo)致Start與End之間沒(méi)有路徑連接。

圖1 降低方差的場(chǎng)地柵格圖

2 改進(jìn)模擬退火算法

2.1 基礎(chǔ)算法

貪心算法通過(guò)每一次選擇局部最優(yōu)解，試圖求出整個(gè)問(wèn)題的最優(yōu)解。這種策略能解決許多問(wèn)題的整體最優(yōu)解，但并不能求得所有問(wèn)題的整體最優(yōu)解。改進(jìn)貪心算法在貪心算法的基礎(chǔ)上添加禁忌表，記錄機(jī)器人以往運(yùn)動(dòng)中由于“過(guò)于貪心”導(dǎo)致無(wú)法到達(dá)End的格子，具體算法如下。

如圖2，假設(shè)機(jī)器人當(dāng)前位置為O，A、B、C、D、E、F、G、H八個(gè)位置均可作為其下一步到達(dá)的位置。首先排除周?chē)恼系K物、邊界以及禁忌表(初始的禁忌表為空)中存在的格子。并且A、C、E、G四個(gè)斜方向格子需要約束，以A為例，如果機(jī)器人要從O到達(dá)A，B和H至少有一個(gè)不是障礙物。然后計(jì)算剩余格子與End的距離，機(jī)器人選擇結(jié)果最小的格子作為下一步。機(jī)器人通過(guò)每一步修正后最貪心的選擇和生成的禁忌表，逐步移動(dòng)，到達(dá)終點(diǎn)。

圖2 搬運(yùn)機(jī)器人當(dāng)前位置示意圖

通過(guò)仿真，依次派送20個(gè)機(jī)器人從Start前往End，得到路徑圖3，其中粗線是最短路徑?？梢钥闯?，禁忌表信息逐漸完善，機(jī)器人陷入“困境”的情況逐次減少。在一定環(huán)境條件下，機(jī)器人能夠通過(guò)改進(jìn)貪心算法到達(dá)End。但是可以看出即使進(jìn)行多次移動(dòng)，機(jī)器人的路徑?jīng)]有太大改變，僅僅是因?yàn)榻杀淼母?，有小范圍變化。因此，可能無(wú)法通過(guò)多次實(shí)驗(yàn)，找到Start到End的最短路徑，從而引入改進(jìn)模擬退火算法。

圖3 改進(jìn)貪心算法路徑

2.2 改進(jìn)模擬退火算法實(shí)現(xiàn)

退火算法來(lái)源于材料的統(tǒng)計(jì)力學(xué)的研究。高溫時(shí)的粒子包含大量的能量，具備隨機(jī)運(yùn)動(dòng)與重組條件；而低溫時(shí)，則反之。隨著溫度逐漸降低(退火)，當(dāng)溫度到達(dá)某個(gè)點(diǎn)時(shí)，粒子處于熱平衡狀態(tài)。隨著系統(tǒng)徹底冷卻，晶體也完全呈現(xiàn)低能狀態(tài)。

具體實(shí)現(xiàn)如下：機(jī)器人在約束條件下計(jì)算出最佳選擇，不妨設(shè)為E點(diǎn)。同時(shí)也找到次佳選擇，設(shè)為F點(diǎn)，在一定概率下機(jī)器人放棄選擇E點(diǎn)，而選擇F點(diǎn)。定義退火系數(shù)AcceptLower，公式(2)中X，Y分別為End或O格子中心的橫、縱坐標(biāo)。DistanceO是柵格O中心到End中心的距離，DistanceE和DistanceF同理。公式(3)中常系數(shù)k用作調(diào)整退火系數(shù)，當(dāng)隨機(jī)數(shù)0～1小于AcceptLower時(shí)，機(jī)器人做次佳選擇。

(2)

(3)

而退火算法收斂速度不夠快，因此以退火算法作為基礎(chǔ)，并融入遺傳算法的思想。遺傳算法將優(yōu)良個(gè)體的基因保留，進(jìn)行兩兩配對(duì)，變異，產(chǎn)生新生代，按此方法逐代進(jìn)化。機(jī)器人利用退火算法產(chǎn)生多組路徑，從中選取優(yōu)良的路徑。而這幾種路徑如果采取“兩兩配對(duì)”，“變異”顯然是難以完成的。因?yàn)榄h(huán)境中存在障礙物，如果將路徑進(jìn)行隨機(jī)改動(dòng)，會(huì)存在穿過(guò)障礙物的情況，因此需要具體情況具體分析。

基于柵格法建立的環(huán)境，對(duì)每一個(gè)格子建立參數(shù)Kij，初值均相等。首先采用退火算法產(chǎn)生若干條路徑，在這些路徑中挑選出最短的幾條。將這幾條路徑經(jīng)過(guò)的格子參數(shù)Kij分別加上不同的常數(shù)，這個(gè)常數(shù)按照排序設(shè)定，路徑越短對(duì)應(yīng)的常數(shù)越大。同時(shí)，后續(xù)組機(jī)器人每一次前往End，同第一組一樣更改Kij。不同的是每進(jìn)行一組，Kij需要略微衰減，以防收斂速度過(guò)快，但要求Kij始終大于初值。公式(4)中，KE和KF分別是E和F格子對(duì)應(yīng)的Kij參數(shù)。K′是常系數(shù)，如果KE>KF，就是在原退火系數(shù)的基礎(chǔ)上乘以了一個(gè)大于1的數(shù)，機(jī)器人做次佳選擇的概率提高。

(4)

2.3 路徑長(zhǎng)度計(jì)算

以圖3為例。公式(5)中，Lall是路徑總長(zhǎng)度，i表示路徑上第i個(gè)格子，L(i,i+1)是第i個(gè)格子與第i+1個(gè)格子間的距離。公式(6)給出了計(jì)算方法。注意水平垂直方向是二維柵格圖上的，并非實(shí)際的水平與垂直。

(5)

(6)

3 搬運(yùn)機(jī)器人硬件系統(tǒng)設(shè)計(jì)

本文選用STM32單片機(jī)作為搬運(yùn)機(jī)器人的微處理器。并且添加感知模塊、電機(jī)驅(qū)動(dòng)模塊、無(wú)線通信模塊、電源模塊。電源模塊負(fù)責(zé)給單片機(jī)和各個(gè)模塊供應(yīng)能量，選用5 V低壓電源，如圖4所示。感知模塊需要顏色傳感器和GPS模塊，顏色傳感器用于檢測(cè)機(jī)器人移動(dòng)過(guò)程中所處環(huán)境，分辨障礙物；GPS模塊用于機(jī)器人定位，在機(jī)器人從Start移動(dòng)到End過(guò)程中起到導(dǎo)航的作用；通信模塊用于單片機(jī)與上位機(jī)信息交流，派出的機(jī)器人將自己的移動(dòng)軌跡、總路程、禁忌表等信息上傳到上位機(jī)，上位機(jī)將處理信息后，下位機(jī)又進(jìn)行下載和更新。

圖4 搬運(yùn)機(jī)器人實(shí)物圖

本文設(shè)計(jì)的搬運(yùn)機(jī)器人在夾持器上進(jìn)行了改進(jìn)，如圖4所示。最初設(shè)計(jì)的搬運(yùn)機(jī)器人采用剪刀式夾子夾持貨物。改進(jìn)后更換為一個(gè)SG90舵機(jī)調(diào)整角度的鉤子。當(dāng)機(jī)器人檢測(cè)到貨物，調(diào)整車(chē)身使其與貨物良好接觸，調(diào)整鉤子角度使貨物與車(chē)身固定在一起，改進(jìn)后的機(jī)器人在運(yùn)輸貨物時(shí)更穩(wěn)定。

4 實(shí)驗(yàn)與分析

4.1 仿真實(shí)驗(yàn)

圖5是通過(guò)貪心算法得到的最優(yōu)路徑(粗線)，長(zhǎng)度為45.284 3；圖6是改進(jìn)模擬退火算法中機(jī)器人前往End過(guò)程產(chǎn)生的多組路徑，最優(yōu)路徑(粗線)長(zhǎng)度為44.698 5；對(duì)比改進(jìn)貪心算法，改進(jìn)模擬退火算法不會(huì)收斂于局部路徑，結(jié)果較好。

圖5 改進(jìn)貪心算法

圖6 改進(jìn)模擬退火算法

如果降低公式(1)中方差項(xiàng)σ，即提高障礙物集中程度，得到的新環(huán)境下的兩種方法仿真圖：圖7為改進(jìn)貪心算法結(jié)果，最短路徑為46.455 8；圖8為改進(jìn)模擬退火算法結(jié)果，最短路徑為43.112 7，二者差距較大。

圖7 改進(jìn)貪心算法

圖8 改進(jìn)模擬退火算法

根據(jù)不同的方差項(xiàng)，各進(jìn)行100次仿真實(shí)驗(yàn)，得改進(jìn)貪心算法和改進(jìn)退火算法的最短路徑的平均值，如圖表1所示。由表1可知，障礙物集中程度越高，即方差項(xiàng)σ越小，改進(jìn)貪心算法越可能陷入某個(gè)固定解，而改進(jìn)模擬退火算法可以找到較優(yōu)的最短路徑。

表1 不同方差項(xiàng)兩種算法的最短路徑均值

4.2 硬件平臺(tái)實(shí)驗(yàn)

將本文提出的改進(jìn)模擬退火算法應(yīng)用于實(shí)際搬運(yùn)機(jī)器人路徑規(guī)劃實(shí)驗(yàn)。通過(guò)多組實(shí)驗(yàn)表明，搬運(yùn)機(jī)器人能夠準(zhǔn)確地繞過(guò)障礙物，并最終在多種路徑中找到最優(yōu)路徑。如圖9為搬運(yùn)機(jī)器人行駛的最優(yōu)路徑。圖9(a)表示機(jī)器人從起點(diǎn)出發(fā)。圖9(b)、圖9(c)分別表示機(jī)器人在行駛途中。圖9(d)表示機(jī)器人到達(dá)終點(diǎn)。本實(shí)驗(yàn)驗(yàn)證了本文提出改進(jìn)模擬退火算法的可行性，并且能夠找到機(jī)器人路徑的最優(yōu)解或近似最優(yōu)解。

圖9 實(shí)際實(shí)驗(yàn)示意圖

5 結(jié)論

由于傳統(tǒng)路徑規(guī)劃算法普遍存在缺乏對(duì)環(huán)境適應(yīng)性的問(wèn)題，本文以改進(jìn)貪心算法為基礎(chǔ)，通過(guò)添加遺傳算法的思想，最終提出了一種改進(jìn)模擬退火算法，并分別在模擬環(huán)境和實(shí)際環(huán)境中對(duì)算法進(jìn)行了驗(yàn)證。即使環(huán)境中的障礙物分布離散或者集中，本文提出的算法都可以通過(guò)一定量的工作找到最優(yōu)解。此外，將本文提出的算法應(yīng)用到了自主設(shè)計(jì)的搬運(yùn)機(jī)器人，取得了2017年中國(guó)工程機(jī)器人大賽暨國(guó)際公開(kāi)賽一等獎(jiǎng)。