粒子群算法在地圖構建中的應用研究.pdf

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

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

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

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