[Individual Project Report] Communication and Localization Networks in Swarm-Intelligent Systems

Attachment大小
Image icon 090206_photo1..jpg101.27 KB
Image icon rover1.jpg36.99 KB
Image icon fr11deep_scansub_375x287.jpg8.76 KB
Image icon f1.png38.17 KB
Image icon f2.png38.83 KB
Image icon f3.png46.19 KB
Image icon f5.png105.78 KB
Image icon f6.png197.21 KB
Image icon f7.png277.19 KB

1. Introduction 簡介 

群聚智慧(Swarm Intelligence)是個既舊且新的概念。 

很多動物像是鳥、魚、螞蟻、蜜蜂都已使用了數千年,

但此概念才剛開始在某些領域解決一些具挑戰性的問題,

像是航空太空探索、還有智慧交通系統等等。 

 

從技術上來看, 

群聚智慧是個以分析和綜合集體行為為基礎、

建構在一個分散式(decentralized)、具自我組織(self-organized)系統上的人工智慧技術。

群聚智慧它特別吸引人的地方,

是因為保證系統具可適性(adaptive)、穩健(robust)、有成本效益(cost-efficient)

 

一般來說, 

群聚智慧系統的研究

對於像是網格運算(grid computing)或無線感測網路(WSN)等其他研究,

提供了一個具洞察力與總結歸納的觀點。

以群聚智慧系統的觀點來看,現今其他許多的系統都能看成是群聚智慧系統的部分功能。

 

 

2. Communication 通訊的重要性 

通訊讓群體中的個體,

得以分享測量的數據與運算後的結果,並調整和同步它們的行動,以實現共同的目標。

對群體中的每個個體而言,這是個必要的功能,這將有助於在不斷發展中的分散式智慧系統。 

 

若依據下列不同應用假設的特性,

就能決定出在其通訊子系統(communication subsystems)中不同的功能,

像是群聚中個體的空間分布、變動性、功率限制

資訊流(information flow)的強度等等假設情況。 

 

因為群聚智慧系統和感測網路(sensor network)相近,

在感測網路上的大量工作會使得成為在群聚智慧系統中一項在通訊方面的問題。

相反的,許多感測網路中的個體,

能主動引導它們的個體到正確的位置,使通訊更有效率或達到負載平衡

 

知道個體間的相對位置,對於彼此通訊中的個體而言能獲得較高的效能。 

以下提出兩種做法能使效能提高: 

第一,當拓樸時常在改變時, 

移動中的個體它們在路由資訊的決定與發送會佔掉它們通訊能力的大部分。 

依每個個體的數量移動的能力,可能會因為通訊能力運算能力被大量消耗掉 

而導致無法完成該項工作, 

所以個體間都要知道其他個體的位置以用來限制搜尋空間路由資訊的數量。  

第二,使用有向天線結合了解個體的位置,可以用來控制無線傳輸和接收天線的功率, 

從而可以對減少發送器的干擾所需的功率 

 


3. Location Determination 位置決定的因素 

當有些應用,它們經常性的需要藉由測量技術來完成位置估算時, 

我們發現,這在群聚智慧的系統中是有難度的。 

第一,個體間的拓墣結構改變太快。 

第二,在這篇作者所研究的狀況中,像是無人飛行載具、探月車、或海底地形探勘的個體 

其設備並不具測量角度的能力 

所以群聚智慧的個體必須藉由無線射頻或聲波來產生距離已決定它們的位置。 

 

 

3-1 Measure of Distances 測量個體間的距離 

 要決定相對位置的一個基本問題是在EAEB間的距離d該如何決定?

大部分的protocol,都能共同地測量距離,並且在傳送訊號時用一個已知的速度c在傳送。 

2: (下圖) 當EAt1時送訊號,

訊號中記有時間標記(time-stamped),或者由EA儲存發送時間。 

EB經過τ1時間,在t2'收到此訊號,t2' = t2 + ΔtA,B,ΔtA,BEAEBclock offset 

如果EAEB有同步的話,則ΔtA,B0,距離d = τ1 * c,τ1t2'- t1' 

不過因為石英震盪器的偏移是隨機的, 

使得ΔtA,B在兩個時脈間的轉換會產生一個error e = ΔtA,B * c。 

若此時是電磁波,且產生一個error 

就算小到1microsecond也會導致產生300公尺的誤差。 

 3: (下圖) 此方法不需要同步時脈。 

EAt1發送一個訊號,經過τ1時間傳送給EB 

再經過一個固定、已知的時間τ2做處理,再回傳給EA 

則我們可以求得距離d = (t2 t1τ2) / 2 * c 

4: (下圖) 在t1時間從EA發出兩種訊號s1s2 

分別有著c1c2的速度,其中c1速度遠快於c2,可想像成電磁波與聲波。 

t2't3'EB收到兩種訊號,此時距離d = ( t3' – t2' ) / ( 1/c2 – 1/c3), 

若求近似解則可假設c1遠快於c2,所以距離d = ( t3' - t2' ) * c2

 

3-2 Localization Network 決定個體的相對位置 

3-1中,我們決定了個體間的距離後,接下來就是要定位了。 

假設N是群聚中的個體數;Nmin是最小個體數;

 D是所在空間是幾維度,也就是一個個體會有D個座標;

Nu是未知的總座標數,Nm是最多的測量次數。 

 

Nu會與N呈線性關係。 

先設一個任意點為起始點0,所以未知的座標數Nu可以從ND降為(N-1)*D 

也就是N= (N-1)*D,令為第一式。 

 

假設群聚中的個體任兩點皆在彼此的範圍中,有N個點,而每個點至少做N-1次測量, 

Nm則與N的平方成正比,所以N= N(N-1)/2,令為第二式。 

 

由一、二式可得知最小的群聚個數Nmin = 2D 

因此,若在二維空間(D=2)中,若有四個個體(N=4),則我們有辦法決定它們的位置。 

 

群聚智慧系統的運作模式有很多,

 其中一個模式是當群體中的部分個體因移動位置而需要重新定位。

假設沒變動的座標數加上需要重新定位的座標數等於或大於總座標數 

則需要重新定位的那些座標還是可以被決定。 

 

為了要決定在空間圖中的一些物理量,例如像是化學物質的濃度,

就必須重複地執行距離測量與定位的動作。

 

大部分的情況下,群體中的個體不會納入在一個fully messed的網路,

也就是個體測量的距離通常不會涵蓋到整個範圍。

像下圖,這是在一個1x1的二維空間,裡頭散布100個個體(紅三角形)

有連線表示彼此在範圍之內,而測量的最大距離是0.15

這個網路已經將所有個體連結在一起,如此足以達到通訊的目的;

但是如果要得到全體的相對位置的話可能還稍嫌條件不足,

因為圖中至少還有三個點的位置是無法被確定的。

 

相對的,如下圖,若測量的範圍double,變0.3。如此一來,所有點的相對位置都能決定。

 

由此可知,通訊的測量範圍和定位所要的測量範圍不一定完全相同,

所以,在群聚智慧的系統網路中,通常要隨時隨地的去描繪這兩個圖。

 

 

4. Application Domains 應用範圍

群聚智慧的概念,一般來說,提供了在科學和工程問題上一個新的解決方案。

像是機載感測器(如迷你的無人飛行載具)智慧交通系統、天然或人為災害的早期預警系統

和天然氣石油或礦物的探勘

使得群聚智慧的個體能運用在太空、天空、陸地、海上、和水面下。

 

目前則是希望用在月球和火星上,運用智慧型機器人在月球表面上建立殖民地,

不過還是有一些問題,像是在月球上如何讓機器人做到集體學習故障排除、甚至自我修復

還有和人類一起執行任務動態感測網路的形成與運作等等。

 

以目前來說,大部分的應用目前都有複雜的問題出現,

像是將群體中的部分個體動態地重新分組以支援動態分配問題

還有需要先進的演算法將數據整合。

 

 

5. Conclusion 結論

群聚智慧中的這些個體同時扮演感測器與控制器,

而且這些個體一直的在動態地改變角色和彼此的關係。

 

在某種程度上來說,群聚智慧系統也可以算是分散式運算和網格運算的一種。

 

在群聚智慧系統中,通訊能力可視為一項很缺乏的資源,足以影響效能。

所以在演算法的設計方面,首要考慮的是通訊方面,這攸關著通訊負載。

不好的演算法,會因為造成通訊壅塞而使得任務失敗。

好的演算法,則會因為節省能源而讓個體的生命周期延長。

 

 

6. References

Communication and Localization Networks in Swarm-Intelligent Systems

Angermann, M. ; Truszkowski, W. ; German Aerosp. Center (DLR), Wessling

Radio and Wireless Symposium, 2008 IEEE

Issue Date :  22-24 Jan. 2008