《電子技術(shù)應(yīng)用》
您所在的位置:首頁(yè) > 其他 > 設(shè)計(jì)應(yīng)用 > 一種家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃的蟻群算法
一種家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃的蟻群算法
來(lái)源:微型機(jī)與應(yīng)用2012年第18期
龍 瓏1,, 鄧 偉2,, 胡秦斌1, 黃智海1
(1. 廣西師范學(xué)院 計(jì)算機(jī)與信息學(xué)院, 廣西 南寧530023,; 2. 廣西腫瘤防治研究所, 廣西
摘要: 由于家庭居住環(huán)境復(fù)雜,,家庭安保機(jī)器人導(dǎo)航問題難于解決,。使用傳統(tǒng)蟻群算法,家庭安保機(jī)器人容易陷入搜索家庭環(huán)境局部極值的困境,,無(wú)法找出在復(fù)雜環(huán)境下家庭最優(yōu)的運(yùn)動(dòng)路徑,。因此,家庭安保機(jī)器人設(shè)計(jì)方案引入混沌理論改良局部個(gè)體的質(zhì)量,,利用混沌擾動(dòng),,能夠避免家庭機(jī)器人陷入搜索家庭環(huán)境局部極值的困境,由最初的混沌行為過渡到群體智能行為,使家庭安保機(jī)器人找到最優(yōu)的運(yùn)動(dòng)路徑,。經(jīng)仿真實(shí)驗(yàn)表明,在復(fù)雜的家庭環(huán)境下,,家庭安保機(jī)器人也可以安全避障。
Abstract:
Key words :

摘  要: 由于家庭居住環(huán)境復(fù)雜,,家庭安保機(jī)器人導(dǎo)航問題難于解決,。使用傳統(tǒng)蟻群算法,家庭安保機(jī)器人容易陷入搜索家庭環(huán)境局部極值的困境,,無(wú)法找出在復(fù)雜環(huán)境下家庭最優(yōu)的運(yùn)動(dòng)路徑,。因此,家庭安保機(jī)器人設(shè)計(jì)方案引入混沌理論改良局部個(gè)體的質(zhì)量,,利用混沌擾動(dòng),,能夠避免家庭機(jī)器人陷入搜索家庭環(huán)境局部極值的困境,由最初的混沌行為過渡到群體智能行為,,使家庭安保機(jī)器人找到最優(yōu)的運(yùn)動(dòng)路徑,。經(jīng)仿真實(shí)驗(yàn)表明,在復(fù)雜的家庭環(huán)境下,家庭安保機(jī)器人也可以安全避障,。
關(guān)鍵詞: 家庭安保機(jī)器人,; 螞蟻算法; 混沌

    根據(jù)“十二五”國(guó)家發(fā)展規(guī)劃,,家庭信息數(shù)字化,、全智能化將成為我國(guó)信息產(chǎn)業(yè)發(fā)展的重點(diǎn),智能家庭安保機(jī)器人將作為一個(gè)新興產(chǎn)業(yè)的重要分支出現(xiàn),。合理的運(yùn)動(dòng)路徑規(guī)劃是家庭安保機(jī)器人研發(fā)面臨的難題之一,,它具體指家庭安保機(jī)器人在有障礙物(包括椅子、柜子,、冰箱等家具)的復(fù)雜家庭環(huán)境中,,根據(jù)某些優(yōu)化算法準(zhǔn)則,能快速找出從起點(diǎn)到目標(biāo)點(diǎn)最優(yōu)的安全運(yùn)動(dòng)路徑,。本文的家庭安保機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃使用蟻群算法中群智能技術(shù)來(lái)解決這個(gè)難題,。假如家庭安保機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃直接使用蟻群算法,會(huì)由于蟻群算法本身最優(yōu)解和收斂速度慢的特點(diǎn)[1-4],,造成家庭安保機(jī)器人運(yùn)動(dòng)軌跡局部路徑選取方法優(yōu)而全局路徑選取方案不是最好,。而混沌恰恰相反,具有全局遍歷性的特點(diǎn),,可以避免家庭安保機(jī)器人在搜索選取運(yùn)動(dòng)路徑時(shí)陷入局部最優(yōu)解,,確保全局路徑最優(yōu)。與家庭安保機(jī)器人運(yùn)動(dòng)路徑單獨(dú)采用蟻群算法相比,,混沌蟻群算法在家庭安保機(jī)器人在家庭復(fù)雜環(huán)境中搜索選取全局運(yùn)動(dòng)路徑方面具有優(yōu)勢(shì),。
1 家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃理論基礎(chǔ)
    混沌理論[5-8]是使用整體,、連續(xù)的數(shù)據(jù)關(guān)系解釋及預(yù)測(cè)探討動(dòng)態(tài)系統(tǒng)中無(wú)法用單一的數(shù)據(jù)關(guān)系與行為,如機(jī)器人搜索探知路線,、化學(xué)物理實(shí)驗(yàn),、氣候變化等屬于混沌理論范疇。當(dāng)物理系統(tǒng)行為接近實(shí)際而沒有內(nèi)在隨機(jī)性的模型但具有貌似隨機(jī)的行為,,稱此系統(tǒng)為混沌,。所以混沌理論看起來(lái)狀態(tài)是混沌的,是事實(shí)上內(nèi)在結(jié)構(gòu)卻非常精致,,具有全局性,、隨機(jī)性、遍歷性及規(guī)律性等諸多特性,,能在規(guī)定的范圍內(nèi)按已制定好的規(guī)則反復(fù)遍歷搜索所在狀態(tài),,直至達(dá)到最優(yōu)的選擇方案。如果在家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃中利用混沌理論的全局和遍歷等特性,,可幫助家庭安保機(jī)器人在復(fù)雜的家庭環(huán)境中找到最佳的運(yùn)動(dòng)路徑,。
    蟻群算法是意大利著名學(xué)者M(jìn).Dorigo受自然界蟻群外出覓食行為的啟發(fā)提出的,然后提出算法思想模擬蟻群外出覓食運(yùn)動(dòng)過程實(shí)現(xiàn)尋優(yōu),。這種算法是一種啟發(fā)式算法,,此后很多學(xué)者對(duì)蟻群算法不斷進(jìn)行改進(jìn)和深化,使得這種算法幫助人們解決了大量的實(shí)際問題,。蟻群捕食初始階段,,利用混沌運(yùn)動(dòng)的遍歷特性先進(jìn)行全局混沌初始化搜索;在給出一點(diǎn)啟發(fā)信息條件下每個(gè)混沌量對(duì)應(yīng)一條運(yùn)動(dòng)路徑,,選擇并記錄下比較好的運(yùn)動(dòng)路徑,,留下這些運(yùn)動(dòng)路徑的信息素;最后,,螞蟻再?gòu)倪@些比較好的運(yùn)動(dòng)路徑中選擇最佳的運(yùn)動(dòng)路徑,。整個(gè)過程數(shù)學(xué)建模工程認(rèn)為有x只螞蟻放在一個(gè)二維空間R中,蟻群最小化的函數(shù)f,,在二維空間R中的每個(gè)點(diǎn)d都是可以給出問題的可行解[9-12],。目前螞蟻的位置、螞蟻鄰居的位置和蟻群組織變量的函數(shù)構(gòu)成了每個(gè)螞蟻的運(yùn)動(dòng)軌跡規(guī)劃測(cè)量,,而蟻群的組織變量控制整個(gè)蟻群對(duì)個(gè)體螞蟻的影響,。有了這樣的理論基礎(chǔ),家庭安保機(jī)器人設(shè)計(jì)小組就可以把家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃問題數(shù)學(xué)建模為帶約束的優(yōu)化問題,。
2 家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃數(shù)學(xué)建模
2.1 運(yùn)動(dòng)路徑規(guī)劃問題描述與家庭環(huán)境建模

    家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃問題的目的就是讓家庭安保機(jī)器人能夠在家庭復(fù)雜環(huán)境中從起始位置出發(fā),安全快速地找到一條避障最短路徑,,從而達(dá)到目的位置,。
    為了便于表示家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃蟻群算法,,把家庭環(huán)境俯視圖方法映射為二維空間,用(x,,y)表示空間坐標(biāo),,并做以下一些假設(shè):家庭空間圖為矩形,其中分布有一定數(shù)量的家具等障礙物,;把家庭安保機(jī)器人看成質(zhì)點(diǎn)(家庭安保機(jī)器人相對(duì)家具很小,,可以看成是質(zhì)點(diǎn)),全部障礙物看成外切四邊形的形狀,,如果不滿一個(gè)網(wǎng)格點(diǎn),,就以一個(gè)網(wǎng)格計(jì)算,以此類推,。
    假設(shè)R為家庭安保機(jī)器人SRob(Security Robot)在二維家庭平面的運(yùn)動(dòng)區(qū)域,。建立一個(gè)家庭平面直角坐標(biāo)系,橫向坐標(biāo)為X軸,,縱向坐標(biāo)為Y軸,,家庭平面圖上在X、Y軸上的最大值為xm,、ym,,以家庭安保機(jī)器人平均步長(zhǎng)λ為柵格四邊形長(zhǎng)和寬距離,然后把家庭平面圖分為等間距的柵格圖,。家庭平面圖上X軸上柵格數(shù)I=xm/λ,,家庭平面圖上Y軸上柵格數(shù)J=ym/λ。在家庭平面圖中障礙物賦值為0,,自由柵格也賦予相應(yīng)的序號(hào)數(shù),,在家庭平面圖中柵格序號(hào)值坐標(biāo)關(guān)系可以表示為:



    (2)系統(tǒng)為每個(gè)螞蟻固定選取了3個(gè)鄰居并做記錄,開始時(shí)螞蟻基本處在混沌搜索過程,,每個(gè)螞蟻從記錄中搜索了解到鄰居螞蟻的最優(yōu)位置和最佳行進(jìn)路線,,并以此為依據(jù),取得下一步的行進(jìn)路線,。
    (3)隨著系統(tǒng)運(yùn)行時(shí)間增長(zhǎng),,組織變量也相應(yīng)地會(huì)不斷增大,家庭安保機(jī)器人運(yùn)動(dòng)軌跡算法中每個(gè)運(yùn)動(dòng)螞蟻在組織變量的互相影響下,,通過與其他鄰居螞蟻不斷通信獲得最佳的局部最優(yōu)值,,不斷更新它們運(yùn)動(dòng)的方位,最后朝最優(yōu)的位置移動(dòng),,從而獲得全局最佳解,,也就是獲得家庭安保機(jī)器人在家庭平面圖的最佳的運(yùn)動(dòng)路徑行進(jìn)路線。
    (4)假如算法中的蟻群全部收斂在一條運(yùn)動(dòng)路徑上,,則算法計(jì)算結(jié)束,,并可以輸出最佳的家庭安保機(jī)器人最佳運(yùn)動(dòng)路徑圖了,,否則轉(zhuǎn)向(3)繼續(xù)運(yùn)行。
3 家庭安保機(jī)器人運(yùn)動(dòng)路徑規(guī)劃算法仿真實(shí)驗(yàn)
    為了驗(yàn)證算法的有效性,,家庭安保機(jī)器人設(shè)計(jì)使用了如圖2所示的模擬家庭環(huán)境地形進(jìn)行仿真實(shí)驗(yàn),其中黑色為家庭環(huán)境中障礙物格(包括家具,、電器等)。家庭環(huán)境模擬地形圖規(guī)模大約為螞蟻數(shù)目的2倍左右,, 設(shè)計(jì)小組選取n=20,、組織因子Oi=0.1+0.2α(其中α為[0,1])、a=300,、b=5/6,、y(0)=0.998。圖3的仿真實(shí)驗(yàn)顯示的是直接用蟻群算法的家庭安保機(jī)器人得到的結(jié)果,,由于家庭安保機(jī)器人陷入了局部最優(yōu),,無(wú)法得到最佳路徑。圖4的仿真實(shí)驗(yàn)顯示本算法找到了最優(yōu)的運(yùn)動(dòng)規(guī)劃路徑,,這條路徑安全規(guī)避障礙物,,而且運(yùn)動(dòng)路徑最短。仿真實(shí)驗(yàn)結(jié)果表明,,增加了混沌理論的蟻群家庭安保機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃算法能有效避免陷入局部最優(yōu),,機(jī)器人可以快速準(zhǔn)確地在家庭復(fù)雜的環(huán)境中找到最佳的運(yùn)動(dòng)路徑。

 

 

     家庭安保機(jī)器人在家庭復(fù)雜環(huán)境中的運(yùn)動(dòng)僅使用一般蟻群算法非常容易陷入局部最優(yōu),,導(dǎo)致家庭安保機(jī)器人無(wú)法在家庭中找出最優(yōu)運(yùn)動(dòng)路徑,。為此,本文將混沌理論引入蟻群算法中,,利用混沌的遍歷特性,,為家庭安保機(jī)器人規(guī)劃出一條局部趨勢(shì)導(dǎo)航路徑,運(yùn)動(dòng)路徑在設(shè)定的組織因子的影響下動(dòng)態(tài)地修改,,加上在局部最優(yōu)路徑的互相影響引導(dǎo)下,,不但成功避免了死鎖、震蕩,,而且家庭安保機(jī)器人在家庭環(huán)境中的運(yùn)動(dòng)路徑是最優(yōu)的,。從仿真實(shí)驗(yàn)可以看出,本算法具有簡(jiǎn)單,、快速,、實(shí)用性強(qiáng)等特點(diǎn),家庭安保機(jī)器人使用本算法后能適應(yīng)家庭復(fù)雜環(huán)境,。進(jìn)一步提高家庭安保機(jī)器人適應(yīng)動(dòng)態(tài)不確定環(huán)境下的運(yùn)動(dòng)規(guī)劃能力是本課題下一步工作重點(diǎn),。
參考文獻(xiàn)
[1] BELLINGHAM J G, RAJAN K. Robotics in remoter hostitle[J].Science, 2007(318):1098-1102.
[2] 趙小川,劉子峰,楊立輝.特種機(jī)器人運(yùn)動(dòng)軌跡規(guī)劃及實(shí)現(xiàn)[J].計(jì)算機(jī)測(cè)量與控制,2011,19(8):2024-2026.
[3] 王華朋,鐘雄虎.基于模糊化卡爾曼濾波的信息融合[J].計(jì)算機(jī)測(cè)量與控制,2006,14(8):1230-1232.
[4] 趙小川,羅慶生,韓寶玲.機(jī)器人多傳感器信息融合研究綜述[J].傳感器與微系統(tǒng),2008,26(8):1-4.
[5] 高玉華,蘇劍波.JMF視頻傳輸技術(shù)在Web機(jī)器人的應(yīng)用[J].機(jī)器人,2004,25(3):218-221.
[6] 徐凱,馮瑞,董道國(guó).基于Web家庭安保機(jī)器人視頻傳輸?shù)难芯颗c實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用與實(shí)現(xiàn),2011,28(8):131-134.
[7] 王箐華,崔世剛.應(yīng)用幾何理論的智能化機(jī)器人路徑軌跡仿真[J].計(jì)算機(jī)仿真,2010,27(3):153-156.
[8] 孫波,陳衛(wèi)東.基于粒子群優(yōu)化算法的移動(dòng)機(jī)器人全局路徑規(guī)劃[J].控制與決策,2005,22(1):12-16.
[9] 劉召,陳懇.被動(dòng)型機(jī)器人控制算法[J].清華大學(xué)學(xué)報(bào),2010,50(2):254-257.
[10] 劉紅霞,印文達(dá),劉曉南.基于混沌蟻群算法的機(jī)器人路徑規(guī)劃[J].計(jì)算機(jī)測(cè)量與控制,2011,19(5):1181-1183.
[11] 左敏,曾廣平.基于平行化的機(jī)器人智能控制研究[J].計(jì)算機(jī)仿真,2011,28(8):202-205.
[12] 李麗香. 一種新的基于螞蟻混沌行為的群智能優(yōu)化算法及其應(yīng)用研究[D].北京:北京郵電大學(xué), 2008.

此內(nèi)容為AET網(wǎng)站原創(chuàng),未經(jīng)授權(quán)禁止轉(zhuǎn)載,。