一種家庭安保機器人運動路徑規(guī)劃的蟻群算法*

龍 瓏 ，鄧 偉 ，胡秦斌 ，黃智海

(1.廣西師范學院 計算機與信息學院,廣西 南寧530023；2.廣西腫瘤防治研究所，廣西 南寧530021)

根據(jù)“十二五”國家發(fā)展規(guī)劃，家庭信息數(shù)字化、全智能化將成為我國信息產(chǎn)業(yè)發(fā)展的重點，智能家庭安保機器人將作為一個新興產(chǎn)業(yè)的重要分支出現(xiàn)。合理的運動路徑規(guī)劃是家庭安保機器人研發(fā)面臨的難題之一，它具體指家庭安保機器人在有障礙物（包括椅子、柜子、冰箱等家具）的復雜家庭環(huán)境中，根據(jù)某些優(yōu)化算法準則，能快速找出從起點到目標點最優(yōu)的安全運動路徑。本文的家庭安保機器人運動軌跡規(guī)劃使用蟻群算法中群智能技術(shù)來解決這個難題。假如家庭安保機器人運動軌跡規(guī)劃直接使用蟻群算法，會由于蟻群算法本身最優(yōu)解和收斂速度慢的特點[1-4]，造成家庭安保機器人運動軌跡局部路徑選取方法優(yōu)而全局路徑選取方案不是最好。而混沌恰恰相反，具有全局遍歷性的特點，可以避免家庭安保機器人在搜索選取運動路徑時陷入局部最優(yōu)解，確保全局路徑最優(yōu)。與家庭安保機器人運動路徑單獨采用蟻群算法相比，混沌蟻群算法在家庭安保機器人在家庭復雜環(huán)境中搜索選取全局運動路徑方面具有優(yōu)勢。

1 家庭安保機器人運動路徑規(guī)劃理論基礎(chǔ)

混沌理論[5-8]是使用整體、連續(xù)的數(shù)據(jù)關(guān)系解釋及預測探討動態(tài)系統(tǒng)中無法用單一的數(shù)據(jù)關(guān)系與行為，如機器人搜索探知路線、化學物理實驗、氣候變化等屬于混沌理論范疇。當物理系統(tǒng)行為接近實際而沒有內(nèi)在隨機性的模型但具有貌似隨機的行為，稱此系統(tǒng)為混沌。所以混沌理論看起來狀態(tài)是混沌的，是事實上內(nèi)在結(jié)構(gòu)卻非常精致，具有全局性、隨機性、遍歷性及規(guī)律性等諸多特性，能在規(guī)定的范圍內(nèi)按已制定好的規(guī)則反復遍歷搜索所在狀態(tài)，直至達到最優(yōu)的選擇方案。如果在家庭安保機器人運動路徑規(guī)劃中利用混沌理論的全局和遍歷等特性，可幫助家庭安保機器人在復雜的家庭環(huán)境中找到最佳的運動路徑。

蟻群算法是意大利著名學者M.Dorigo受自然界蟻群外出覓食行為的啟發(fā)提出的，然后提出算法思想模擬蟻群外出覓食運動過程實現(xiàn)尋優(yōu)。這種算法是一種啟發(fā)式算法，此后很多學者對蟻群算法不斷進行改進和深化，使得這種算法幫助人們解決了大量的實際問題。蟻群捕食初始階段，利用混沌運動的遍歷特性先進行全局混沌初始化搜索；在給出一點啟發(fā)信息條件下每個混沌量對應(yīng)一條運動路徑，選擇并記錄下比較好的運動路徑，留下這些運動路徑的信息素；最后，螞蟻再從這些比較好的運動路徑中選擇最佳的運動路徑。整個過程數(shù)學建模工程認為有x只螞蟻放在一個二維空間R中，蟻群最小化的函數(shù)f，在二維空間R中的每個點d都是可以給出問題的可行解[9-12]。目前螞蟻的位置、螞蟻鄰居的位置和蟻群組織變量的函數(shù)構(gòu)成了每個螞蟻的運動軌跡規(guī)劃測量，而蟻群的組織變量控制整個蟻群對個體螞蟻的影響。有了這樣的理論基礎(chǔ)，家庭安保機器人設(shè)計小組就可以把家庭安保機器人運動路徑規(guī)劃問題數(shù)學建模為帶約束的優(yōu)化問題。

2 家庭安保機器人運動路徑規(guī)劃數(shù)學建模

2.1 運動路徑規(guī)劃問題描述與家庭環(huán)境建模

家庭安保機器人運動路徑規(guī)劃問題的目的就是讓家庭安保機器人能夠在家庭復雜環(huán)境中從起始位置出發(fā)，安全快速地找到一條避障最短路徑，從而達到目的位置。

為了便于表示家庭安保機器人運動路徑規(guī)劃蟻群算法，把家庭環(huán)境俯視圖方法映射為二維空間，用(x，y)表示空間坐標，并做以下一些假設(shè)：家庭空間圖為矩形，其中分布有一定數(shù)量的家具等障礙物；把家庭安保機器人看成質(zhì)點(家庭安保機器人相對家具很小，可以看成是質(zhì)點)，全部障礙物看成外切四邊形的形狀，如果不滿一個網(wǎng)格點，就以一個網(wǎng)格計算，以此類推。

假設(shè)R為家庭安保機器人SRob(Security Robot)在二維家庭平面的運動區(qū)域。建立一個家庭平面直角坐標系，橫向坐標為X軸，縱向坐標為Y軸，家庭平面圖上在X、Y軸上的最大值為xm、ym，以家庭安保機器人平均步長λ為柵格四邊形長和寬距離，然后把家庭平面圖分為等間距的柵格圖。家庭平面圖上X軸上柵格數(shù)I=xm/λ，家庭平面圖上 Y軸上柵格數(shù)J=ym/λ。在家庭平面圖中障礙物賦值為0，自由柵格也賦予相應(yīng)的序號數(shù)，在家庭平面圖中柵格序號值坐標關(guān)系可以表示為：

其中，Int為取整運算，Rem為求余運算，SumN總柵格數(shù)。家庭平面圖所得坐標與序號的關(guān)系如圖1所示。

圖1中，家庭平面圖任意兩個柵格間距離長度表示為 L(di，dj)，d表示家庭平面圖的可行節(jié)點。則

S為家庭安保機器人SRob在家庭平面圖的行走步幅的取值范圍，S={1,}，家庭安保機器人 SRob取值范圍領(lǐng)域 SR(di(xi,yi))={d|L(d,di)≤S}，圖 1中的粗實線表示以上情況的區(qū)域。可以得知在家庭平面圖中的第n只螞蟻的可行區(qū)Hi(n)=SRgi(k)-OBS-GriSn,其中OBS表示家庭平面圖障礙物柵格的集合總數(shù)，GriSn表示家庭安保機器人在家庭平面度走過的柵格位置的集合。GriSn中在家庭平面圖各個位置點的連線稱為家庭安保機器人起始點dbegin到局部最優(yōu)點的長度距離，記為D，有以下公式表示：

家庭安保機器人設(shè)計小組可以把家庭安保機器人在家庭復雜環(huán)境下的路徑規(guī)劃問題轉(zhuǎn)化為帶約束的優(yōu)化問題，約束函數(shù)為D。

2.2 家庭安保機器人運動路徑規(guī)劃算法的模型

家庭安保機器人設(shè)計小組要把算法中單個螞蟻的運動路徑規(guī)劃策略與螞蟻所在的現(xiàn)在位置、局部最優(yōu)解和組織變量做綜合性考慮，以達到尋找全局最優(yōu)的運動路徑的目的。家庭安保機器人算法的螞蟻i當前的位置是個體與群體的函數(shù)，表示為：

其中，STi(t)表示算法中第 i只螞蟻的當前狀態(tài)情況，ne(t-1)表示第i只螞蟻與其鄰居之間在t-1柵格內(nèi)找到的最佳位置，or(t)表示這個系統(tǒng)的組織變量的當前狀態(tài)情況。

家庭安保機器設(shè)計小組設(shè)第i只螞蟻的固定鄰居數(shù)目為3只，這只螞蟻的鄰居分別為第j只螞蟻、第h只、第p只螞蟻，它們在前面n-1次的迭代計算中的最佳位置是Ljbest、Lhbest、Lpbest,這些鄰居螞蟻的位置與信息都被傳給第i只螞蟻，這只螞蟻根據(jù)自身的位置以及鄰居螞蟻的位置與信息，得出最佳的選擇解。

把n只螞蟻放到家庭平面二維空間中，蟻群之間的最小距離函數(shù)D，家庭平面二維空間的每個點d都是問題的可行解。當前螞蟻的位置、螞蟻鄰居的位置和蟻群組織變量的函數(shù)構(gòu)成了每個螞蟻的運動軌跡規(guī)劃測量，而蟻群的組織變量又可以控制整個蟻群對個體螞蟻的影響，由此家庭安保機器人路徑規(guī)劃算法的優(yōu)化系統(tǒng)模型可以表示為：

其中本家庭安保機器人的算法中實際應(yīng)用時取0≤a≤2/3，b為相對足夠大的數(shù)，在本家庭安保機器人的算法中實際取 b=300,組織因子Oi取 0～1之間，yi(0)=0.998。

2.3 家庭安保機器人運動路徑規(guī)劃算法實現(xiàn)流程

設(shè)計小組設(shè)dbegin為螞蟻出發(fā)原點，dend為目標點，算法實現(xiàn)流程采用Sole的混沌系統(tǒng)流程，算法系統(tǒng)從開始就可以進行混沌搜索，算法實現(xiàn)流程如下：

(1)隨機產(chǎn)生了起始原點 dbegin和起始終點 dend，所有參數(shù)被混沌初始化，記錄和隨時調(diào)整各螞蟻行進路徑的信息。

(2)系統(tǒng)為每個螞蟻固定選取了3個鄰居并做記錄，開始時螞蟻基本處在混沌搜索過程，每個螞蟻從記錄中搜索了解到鄰居螞蟻的最優(yōu)位置和最佳行進路線，并以此為依據(jù)，取得下一步的行進路線。

(3)隨著系統(tǒng)運行時間增長，組織變量也相應(yīng)地會不斷增大，家庭安保機器人運動軌跡算法中每個運動螞蟻在組織變量的互相影響下，通過與其他鄰居螞蟻不斷通信獲得最佳的局部最優(yōu)值，不斷更新它們運動的方位，最后朝最優(yōu)的位置移動，從而獲得全局最佳解，也就是獲得家庭安保機器人在家庭平面圖的最佳的運動路徑行進路線。

(4)假如算法中的蟻群全部收斂在一條運動路徑上，則算法計算結(jié)束，并可以輸出最佳的家庭安保機器人最佳運動路徑圖了，否則轉(zhuǎn)向(3)繼續(xù)運行。

3 家庭安保機器人運動路徑規(guī)劃算法仿真實驗

為了驗證算法的有效性，家庭安保機器人設(shè)計使用了如圖2所示的模擬家庭環(huán)境地形進行仿真實驗,其中黑色為家庭環(huán)境中障礙物格(包括家具、電器等)。家庭環(huán)境模擬地形圖規(guī)模大約為螞蟻數(shù)目的2倍左右，設(shè)計小組選取 n=20、組織因子 Oi=0.1+0.2α(其中 α為[0,1])、a=300、b=5/6、y(0)=0.998。 圖 3 的仿真實驗顯示的是直接用蟻群算法的家庭安保機器人得到的結(jié)果，由于家庭安保機器人陷入了局部最優(yōu)，無法得到最佳路徑。圖4的仿真實驗顯示本算法找到了最優(yōu)的運動規(guī)劃路徑，這條路徑安全規(guī)避障礙物，而且運動路徑最短。仿真實驗結(jié)果表明，增加了混沌理論的蟻群家庭安保機器人運動軌跡規(guī)劃算法能有效避免陷入局部最優(yōu)，機器人可以快速準確地在家庭復雜的環(huán)境中找到最佳的運動路徑。

圖2 家庭地形圖

圖3 直接蟻群算法得到路徑圖

圖4 本算法得到路徑圖

家庭安保機器人在家庭復雜環(huán)境中的運動僅使用一般蟻群算法非常容易陷入局部最優(yōu)，導致家庭安保機器人無法在家庭中找出最優(yōu)運動路徑。為此，本文將混沌理論引入蟻群算法中，利用混沌的遍歷特性，為家庭安保機器人規(guī)劃出一條局部趨勢導航路徑，運動路徑在設(shè)定的組織因子的影響下動態(tài)地修改，加上在局部最優(yōu)路徑的互相影響引導下，不但成功避免了死鎖、震蕩，而且家庭安保機器人在家庭環(huán)境中的運動路徑是最優(yōu)的。從仿真實驗可以看出，本算法具有簡單、快速、實用性強等特點，家庭安保機器人使用本算法后能適應(yīng)家庭復雜環(huán)境。進一步提高家庭安保機器人適應(yīng)動態(tài)不確定環(huán)境下的運動規(guī)劃能力是本課題下一步工作重點。

[1]BELLINGHAM J G,RAJAN K.Robotics in remoter hostitle[J].Science,2007(318)：1098-1102.

[2]趙小川,劉子峰,楊立輝.特種機器人運動軌跡規(guī)劃及實現(xiàn)[J].計算機測量與控制,2011,19(8)：2024-2026.

[3]王華朋,鐘雄虎.基于模糊化卡爾曼濾波的信息融合[J].計算機測量與控制,2006,14(8)：1230-1232.

[4]趙小川,羅慶生,韓寶玲.機器人多傳感器信息融合研究綜述[J].傳感器與微系統(tǒng),2008,26(8)：1-4.

[5]高玉華,蘇劍波.JMF視頻傳輸技術(shù)在Web機器人的應(yīng)用[J].機 器 人 ,2004,25(3)：218-221.

[6]徐凱,馮瑞,董道國.基于 Web家庭安保機器人視頻傳輸?shù)难芯颗c實現(xiàn)[J].計算機應(yīng)用與實現(xiàn),2011,28(8)：131-134.

[7]王箐華,崔世剛.應(yīng)用幾何理論的智能化機器人路徑軌跡 仿 真 [J].計 算 機 仿 真,2010,27(3)：153-156.

[8]孫波,陳衛(wèi)東.基于粒子群優(yōu)化算法的移動機器人全局路徑規(guī)劃[J].控制與決策,2005,22(1)：12-16.

[9]劉召,陳懇.被動型機器人控制算法[J].清華大學學報,2010,50(2)：254-257.

[10]劉紅霞,印文達,劉曉南.基于混沌蟻群算法的機器人路徑規(guī)劃[J].計算機測量與控制,2011,19(5)：1181-1183.

[11]左敏,曾廣平.基于平行化的機器人智能控制研究[J].計算 機 仿 真 ,2011,28(8)：202-205.

[12]李麗香.一種新的基于螞蟻混沌行為的群智能優(yōu)化算法及其應(yīng)用研究[D].北京：北京郵電大學,2008.