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

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

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

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

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