基于遺傳算法的多機器人協作建圖方法

(中南大學 信息科學與工程學院， 長沙 410083）

摘 要：

現有多機器人協作構建地圖的方法對環境和機器人位置信息有著較高要求，因而在實際應用中存在一定局限性。針對這一問題，提出了一種基于遺傳算法的改進方法。該方法采用獨立探索、集中建圖的探索策略，對環境建立局部柵格地圖并予以融合。在地圖融合過程中，無須考慮機器人位置信息，而是以柵格地圖相似度為度量標準，利用改進的遺傳算法快速、高效地搜索各局部地圖之間的最大重疊部分，進而予以融合。實驗結果驗證了該方法的可行性和有效性。

關鍵詞：多機器人； 復雜環境； 地圖構建； 遺傳算法

中圖分類號：TP242.6文獻標志碼：A

文章編號：1001-3695(2009)04-1289-03

Approach to cooperative multi-robot map-building based on genetic algorithm

PAN Wei， CAI Zi-xing， CHEN Bai-fan

（School of Information Science Engineering， Central South University， Changsha 410083， China）

Abstract:

The typical multi-robot map-building approaches have high requirements for environments and robots’localization information， so they have certain limitation in practical applications. To solve this problem， this paper proposed a novel improved approach. The approach let all robots operate individually and then tried to merge the different local grid maps into a single global one. Without using any pose information of the robots， performed the process of map merging by measuring the similarity between grid maps. It used an improved genetic algorithm to effectively search the maximum overlap at which the local maps could be joint together. Experimental results show the feasibility and effectiveness of this approach.

Key words：multi-robot； complex environments； map-building； genetic algorithm

0 引言

地圖創建是移動機器人研究的一個重要課題。具有自主能力的移動機器人必定能夠對其所工作的環境建立準確的地圖[1]。到目前為止，研究人員已針對單機器人地圖構建進行了大量工作，并取得了一些重大進展。然而在實際應用中，由于任務的復雜性，僅僅依靠單個機器人完成任務往往不能盡如人意，人們希望通過多機器人之間的協調合作來彌補這一缺陷 [2]。與單機器人相比，使用多個機器人進行協作建圖具有高效、高精度、高容錯性、高魯棒性、可重構性、低成本等優點，更適用于實際應用中的各種復雜任務。

到目前為止，國內外針對多機器人協作構建地圖的研究還不是很多。現有的建圖方法主要是將同時定位與建圖（simultaneous localization and mapping， SLAM）算法擴展到多機器人的情況中[3，4]。該方法的缺點在于對環境要求較高，即當地圖特征數較多時，算法的計算量較大，因而不適用于較大規模環境、動態環境以及環境特征較模糊的情況。期望最大化（expectation maximization，EM）算法是另一種常用的多機器人建圖方法[5，6]，該方法遞增式地生成最大似然地圖，而不需要像SLAM算法那樣計算所有后驗信息，減少了環境特征數對計算量的影響，但其局限性在于對傳感器測量精度要求較高，且必須已知各機器人之間的相對位置。此外，研究者們還提出了其他一些協作建圖方法。文獻[7]采用最大子地圖匹配算法對各機器人建立的拓撲地圖予以融合。文獻[8，9]采用折線表示地圖，并根據局部地圖的幾何相似性融合為全局地圖。這些方法不需要機器人的位置信息，但它們都以地圖的幾何特征為基礎，因而并不適用于非結構環境等難以提取環境特征的情況。

本文在現有研究的基礎上，提出了一種基于遺傳的多機器人協作建圖方法。該方法采用獨立探索、集中建圖的環境探索策略，即各機器人從同一環境的不同位置出發，獨立探索并建立局部地圖，然后將這些局部地圖融合為全局地圖。考慮到在實際情況中，某些復雜環境難以提取環境特征，因此采用柵格地圖表示方法，然后利用改進的遺傳算法搜索各局部柵格地圖之間的最大重疊部分，進而予以融合。實驗結果表明，該方法無須考慮機器人的位置信息，消除了定位誤差帶來的影響，更適合于大規模環境、非結構環境等復雜情況。

1 遺傳算法原理

遺傳算法是一類借鑒生物界遺傳機制的概率搜索算法[10]，其主要特點是群體搜索策略和群體中基因之間的信息交換，搜索不依賴于梯度信息。遺傳算法使用遺傳算子（genetic operations）作用于群體P(t)中，進行下述遺傳操作，從而得到新一代群體P(t+1)：

a）選擇(selection)。根據各個個體的適應度，按照一定的規則或方法，從第t代群體P(t)中選擇出一些優良的個體遺傳到下一代群體P(t+1)中。

b）交叉（crossover）。將群體P(t)內的各個個體隨機搭配成對，對每一對個體，以某個概率（稱為交叉概率，crossover rate）交換它們之間的部分染色體。

c）變異（mutation）。對群體P(t)中的每一個個體，以某一概率（稱為變異概率，mutation rate）改變某一個或某一些基因座上的基因值為其他的等位基因。

然而，傳統的遺傳算法應用到實際中時會產生一些問題：

a）全局搜索能力強而局部尋優能力較差。

b）易出現早熟收斂現象，使問題的求解陷于局部極值點。表現為群體中最優個體的適應度值得不到提高，群體在經過若干次迭代后仍找不到全局最優解。

c）對搜索空間變化的適應能力差。當搜索空間變化時，搜索策略卻沒有相應的變化。

d）交叉、變異操作的隨機性較強，致使搜索效率低下。

本文針對機器人所構建的柵格地圖，對基本遺傳算法引入了自適應策略等改進方法，設計了一種用于最優轉換函數搜索的改進遺傳算法流程。

2 協作建圖方法

2.1 問題描述

對于非結構環境或其他一些難以提取特征的復雜環境，柵格是一種較為合適的地圖表示方法。柵格地圖將整個工作環境分為若干大小相同的柵格，對于每個柵格指出其中存在障礙物的可能性。在處理地圖的過程中，可將柵格地圖離散化為N行、M列的矩陣。其函數可表示為

m:[0，N]×[0，M]→R (1)

其中：函數m為該地圖的置信度模型，用于表示柵格被障礙物占據的可能性。例如，當m(x，y)為1時表示在柵格(x，y)中有障礙物，而為0時則相反。

在地圖融合過程中，需要通過適當的轉換函數對地圖進行平移和旋轉。設a，b，φ為三個實數，可將該轉換函數定義為

Ta，b，φ(x，y)=cos φ-sin φ asin φcos φb001xy1 (2)

由式(2)可知，轉換函數Ta，b，φ(x，y)相當于在柵格(x， y)的初始位置處逆時針旋轉φ角度，并平移(a，b)的距離。

以兩個機器人為例，可以將協作建圖問題定義為：機器人 R1和R2從不同位置出發，對環境進行完全探索并分別建立兩個局部柵格地圖m1和 m2。讓m1保持靜止，m2則根據不同的轉換函數Ta，b，φ進行平移和旋轉，直到獲得與地圖m1之間的最大重疊部分。這樣就把地圖構建過程轉換為一個最優化問題，即搜索最優的地圖轉換函數Ts(a，b，φ)，使得Δ(m1，Ts(m2))最大。其中Δ為地圖相似度函數。本文采用改進的遺傳算法來完成這一最優搜索過程。

2.2 遺傳搜索

2.2.1 編碼

用遺傳算法進行參數提取時，首先需要通過編碼將模型中的一套參數轉換成遺傳算法種群中的一個個體，常用的編碼方法有二進制編碼和浮點數編碼。二進制編碼使用的符號集由二進制符號0和1組成，其每個個體由一個二進制符號串描述。其優點是編/解碼操作簡單，交叉、變異等遺傳操作便于實現。但由于模型中的大部分參數在某個區間連續取值，二進制編碼在離散化時存在映射誤差。如果碼串較短，可能達不到精度要求；如果碼串較長，會使算法的搜索空間急劇擴大，造成遺傳算法的時間性能降低。

為了提高參數提取精度，保持種群的多樣性，改善計算復雜性和運算效率，本文采用浮點數編碼，每個參數用一個浮點數表示。如果需要提取的參數共有n個，可分別用浮點數x1，x2，…，xn表示，一套參數可以使用一個n維浮點向量X=(x1，x2，…，xn)表示；每代種群中的N個個體，可分別用n維浮點向量X1，X2，…，XN來表示。

2.2.2 適應度函數

用遺傳算法進行優化需要確定一個合適的適應度函數，其數值將決定個體是繼續繁衍還是消亡。適應度函數是影響遺傳算法性能的主要因素之一，選取的合理與否不僅影響算法的收斂速度，而且關系到全局最優解能否實現。適應度函數通常取待優化的目標函數，或其某種變型。這里直接采用地圖相似度Δ(m1，Ta，b，φ(m2))作為尋優度量。

地圖m1和m2的相似度函數定義如下：

Δ(m1，m2)=1/∑c=Cd(m1，m2，c)+d(m2，m1，c)(3)

d(m1，m2，c)=(∑m1[p1]=cmin{dist(p1，p2)|m2[p2]=c})/numc(m1)(4)

其中：C表示柵格地圖中的置信度集合，在本文中，只考慮柵格是否被障礙物占據兩種情況，即C=[0，1]；numc(m1)表示地圖m1中置信度為c的柵格數；dist(p1，p2)為柵格p1與p2的距離。常見的距離測度函數有歐氏距離、切削距離和街區距離[11]。在本文中為了避免過大的計算量，使用街區距離計算垂直和水平路徑，即點p1和p2之間的街區距離為

dist(p1，p2)=|x1-x2|+|y1-y2|(5)

2.2.3 選擇機制

從群體中選擇優勝的個體，淘汰劣質個體的操作叫做選擇，其中最基本也是最常用的選擇方法是適應度比例方法，也叫賭輪或蒙特卡羅（Monte Carlo）選擇。本文采用適應度比例與最佳個體保存相結合的選擇機制。適應度比例選擇方法可以描述為：設群體大小為N，其中個體的適應度為fi，按照適應度比例方法個體i被選擇的概率Psi為

Pst=fi/∑Ni=1fi(6)

2.2.4 交叉與變異

遺傳算法一般采用固定的交叉算子pc（0.5~0.9）和變異算子pm（0.001~0.2）。單純增大pc和pm的值可以增強遺傳算法的全局搜索能力，但同時降低了其局部尋優能力[12]。本文對交叉和變異算子引入自適應策略，用gdm作為衡量每代群體中個體多樣性的量度，則既可以兼顧全局搜索和局部尋優，又可以動態地控制遺傳操作。gdm定義為

gdm=f/fmax(7)

其中：f為當前代的適應度平均值；fmax為當前代的最大適應值，gdm值越大，則個體越集中，個體的多樣性越小，需要適當增加變異概率而減小交叉概率來增加個體的多樣性以防止遺傳算法收斂于局部最優；反之，gdm越小，則個體多樣性越多，此時就適當減小變異概率而增加交叉概率。

2.2.5 停機準則

遺傳算法的停機準則就是遺傳算法的終止條件。常見的停機準則有：a）基于遺傳代數的停機準則，即當遺傳代數超過預先設定的代數，則停止循環；b）基于適應度的停機準則。即當當前代的適應度函數相同或者變化很小時，則停止循環；c）基于收斂性的停機準則，即當當前代的收斂值與預先設定的前n代收斂值相同或變化很小時，則停止循環。本文采用一種混合的停機準則，首先根據適應度停機準則判斷是否停機，同時設置一個最大遺傳代數，其目的是為了防止遺傳算法過度發散。本文采用的適應度停機準則滿足Δ/Δmax＜const。其中const為常數。

3 實驗結果

為了證明本文所提出方法的可靠性和正確性，實驗采用兩個自行改造的MORCS-Ⅱ機器人在自行搭建的非結構環境中完成， 如圖1所示。該移動機器人裝有八個聲納傳感器用于探測環境。實驗設定創建的柵格地圖大小為900×600，每個柵格單元對應實際環境大小為10 mm×10 mm，即該柵格地圖描述大約9 m×6 m的真實環境。機器人從環境的不同位置出發，獨立地對環境進行完全探索，并分別建立局部柵格地圖。主要實驗流程如下：

a)構建局部柵格地圖m1和m2。

b)在搜索窗內隨機產生N個初始種群，每個個體表示轉換函數的系列參數a，b，φ。初始種群數N=50。

c)對每個個體計算適應度函數Δ(m1，Ta，b，φ(m2))作為尋優度量。

d)選擇、交叉、變異。本文采用交叉率pc=0.9，變異率pm=0.01。

e)從d)開始進行遺傳迭代運算，判斷是否滿足終止條件，不滿足條件時，則轉到b）;否則到f)。本文采用的適應度停機常數const=0.75。

f)輸出最優轉換函數Ts(a，b，φ)。

g)依據最優轉換函數對m2進行平移和旋轉，并與m1融合。



圖2為兩個機器人協作建圖的實驗結果。其中：(a)和(b)分別為機器人R1和R2建立的局部柵格地圖m1和m2；(c)為采用本文方法進行地圖融合后所得到的全局地圖。經過30次重復實驗證明，該方法能夠獲得93.3%的成功率。



4 結束語

本文針對現有多機器人協作建圖方法在環境和機器人位置方面的局限性，提出了一種基于遺傳搜索的改進方法。該方法采用柵格地圖表示環境，利用遺傳算法進行全局尋優，快速高效地搜索出最優轉換函數，以找出柵格地圖之間的最大重疊部分并予以融合。實驗表明，在實際應用的各種環境中，該方法均能取得令人滿意的建圖效果；此外，由于該方法不需要已知各機器人的起始位置和相對位置信息，所受條件限制小，應用場合廣。

目前本文提出的方法只應用于兩個機器人的復雜環境探測實驗中，今后，筆者將研究更多機器人的協作建圖情況。此外還將進一步改進所采用的遺傳搜索算法，以提高地圖構建的效率和準確性。

參考文獻：

[1]蔡自興， 賀漢根， 陳虹. 未知環境中移動機器人導航控制研究的若干問題[J].控制與決策，2002，17(4): 385-390.

[2]THRUN S. Robotic mapping: a survey， CMU-CS-02-111[R]. Pittsburgh， PA: School of Computer Science， Carnegie Mellon University， 2002.

[3]FENWICK J W， NEWMAN P M， LEONARD J J. Cooperative concurrent mapping and localization[C]//Proc of IEEE International Conference on Intelligent Robots and Automation. Washington DC: IEEE Press， 2002:1810-1817.

[4]FOX D， KO J， KONOLIGE K， et al. Distributed multi-robot exploration and mapping[J]. Proceedings of the IEEE， 2006， 94(7):1325-1339.

[5]THRUN S. A probabilistic online mapping algorithm for teams of mobile robots[J]. International Journal of Robotics Research， 2001， 20(5):335-363.

[6]THRUN S， BURGARD W， FOX D. A real-time algorithm for mobile robot mapping with applications to multi-robot and 3D mapping[C]//Proc of IEEE International Conference on Robotics and Automation. San Francisco:IEEE Press，2000:321-328.

[7]HUANG W H， BEEVERS K R. Topological map merging[J]. International Journal of Robotics Research， 2005， 24(8):601-613.

[8]LAKAEMPER R， LATECKI L J， WOLTER D. Incremental multi-robot mapping[C]//Proc of IEEE International Conference on Intelligent Robots and Systems. Edmonton: IEEE Press， 2005: 3846-3851.

[9]AMIGONI F， GASPARINI S， GINI M. Building segment-based maps without pose information[J]. Proceedings of the IEEE， 2006， 94(7):1340-1359.

[10]田瑩， 苑瑋琦. 遺傳算法在圖像處理中的應用[J]. 中國圖象圖形學報， 2007，12(3):389-396.

[11]崔峰， 汪雪林， 彭思龍. 近似歐氏距離變換的一種并行算法[J].中國圖象圖形學報，2004，9(6): 693-698.