粒子群算法在地圖構(gòu)建中的應(yīng)用研究.pdf

1、基于多機(jī)器人技術(shù)的地圖構(gòu)建方案由于其適應(yīng)性強(qiáng)、安全高效、精確可靠等特點(diǎn)已經(jīng)被視為地圖構(gòu)建問題的一個(gè)理想解決方案。在該方案中,節(jié)點(diǎn)間的協(xié)調(diào)和任務(wù)的分配是決定地圖構(gòu)建效率的主要難點(diǎn)。針對(duì)大規(guī)模節(jié)點(diǎn)協(xié)同的問題,并行、多點(diǎn)的方式是解決這一問題研究的要點(diǎn)。目前已有的節(jié)點(diǎn)協(xié)同算法是基于任務(wù)分配的算法,典型的有基于市場(chǎng)機(jī)制、基于閾值、基于行為的分配算法。這些算法將地圖構(gòu)建問題分解為若干子問題,依賴節(jié)點(diǎn)的層次結(jié)構(gòu),進(jìn)行集中式發(fā)布。這樣做不但會(huì)產(chǎn)生用于發(fā)

2、送指令的額外通信開銷,更會(huì)在節(jié)點(diǎn)數(shù)量上升時(shí)由于協(xié)同算法計(jì)算量上升，從而導(dǎo)致整個(gè)系統(tǒng)的效率下降。因此,我們需要尋找一種完全分布式并具有更好可擴(kuò)展性的節(jié)點(diǎn)協(xié)同算法。本文引入粒子群優(yōu)化模型,提出了一種新的分布式自組織地圖構(gòu)建算法,解決了上述問題。粒子群優(yōu)化是一種典型的群體智能算法,相比傳統(tǒng)的優(yōu)化算法更強(qiáng)調(diào)粒子之間的協(xié)同合作,用并行方式完成對(duì)解空間的搜索。本文提出算法的思路是,將粒子群優(yōu)化中在解空間對(duì)最優(yōu)解搜索的過程轉(zhuǎn)化為在未知區(qū)域?qū)ξ刺綔y(cè)區(qū)域

3、的搜索過程,從而實(shí)現(xiàn)對(duì)未知區(qū)域的地圖構(gòu)建。粒子群優(yōu)化中粒子是完全分布式和同構(gòu)化的,在搜索過程中所有粒子只需要進(jìn)行自身運(yùn)動(dòng)路徑的計(jì)算,因此當(dāng)粒子數(shù)目增加時(shí)原有節(jié)點(diǎn)不需要增加額外的計(jì)算量。針對(duì)通信量增加的問題,我們采用了一種虛擬信息素機(jī)制來(lái)完成節(jié)點(diǎn)間信息交互,通過小范圍廣播進(jìn)行通信,無(wú)需路徑計(jì)算,從而節(jié)省通信開銷。通過以上方法,采用本算法進(jìn)行地圖探索可以提高系統(tǒng)的規(guī)模特性。本文的主要工作包括:(1)總結(jié)現(xiàn)有地圖構(gòu)建算法和粒子群優(yōu)化算法研究現(xiàn)

4、狀,對(duì)算法的可行性進(jìn)行理論分析;(2)提出了基于粒子群優(yōu)化模型的地圖構(gòu)建算法,包括兩階段PSO搜索路徑?jīng)Q策機(jī)制和基于虛擬信息素的節(jié)點(diǎn)間交互機(jī)制,給出算法模型的詳細(xì)描述,對(duì)算法模型進(jìn)行理論分析,以偽代碼形式給出算法實(shí)現(xiàn);(3)在自主開發(fā)的仿真平臺(tái)上實(shí)現(xiàn)了算法,并針對(duì)算法的有效性、可擴(kuò)展性和參數(shù)影響進(jìn)行了一系列的對(duì)比仿真實(shí)驗(yàn),對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行詳細(xì)分析。本文提出的地圖構(gòu)建算法基于粒子群優(yōu)化模型,節(jié)點(diǎn)自組織地進(jìn)行協(xié)作,分布式地完成搜索路徑計(jì)算,能