(中南大學(xué) 信息科學(xué)與工程學(xué)院， 長(zhǎng)沙 410083）

摘 要：

現(xiàn)有多機(jī)器人協(xié)作構(gòu)建地圖的方法對(duì)環(huán)境和機(jī)器人位置信息有著較高要求，因而在實(shí)際應(yīng)用中存在一定局限性。針對(duì)這一問(wèn)題，提出了一種基于遺傳算法的改進(jìn)方法。該方法采用獨(dú)立探索、集中建圖的探索策略，對(duì)環(huán)境建立局部柵格地圖并予以融合。在地圖融合過(guò)程中，無(wú)須考慮機(jī)器人位置信息，而是以柵格地圖相似度為度量標(biāo)準(zhǔn)，利用改進(jìn)的遺傳算法快速、高效地搜索各局部地圖之間的最大重疊部分，進(jìn)而予以融合。實(shí)驗(yàn)結(jié)果驗(yàn)證了該方法的可行性和有效性。

關(guān)鍵詞：多機(jī)器人； 復(fù)雜環(huán)境； 地圖構(gòu)建； 遺傳算法

中圖分類號(hào)：TP242.6文獻(xiàn)標(biāo)志碼：A

文章編號(hào)：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 引言

地圖創(chuàng)建是移動(dòng)機(jī)器人研究的一個(gè)重要課題。具有自主能力的移動(dòng)機(jī)器人必定能夠?qū)ζ渌ぷ鞯沫h(huán)境建立準(zhǔn)確的地圖[1]。到目前為止，研究人員已針對(duì)單機(jī)器人地圖構(gòu)建進(jìn)行了大量工作，并取得了一些重大進(jìn)展。然而在實(shí)際應(yīng)用中，由于任務(wù)的復(fù)雜性，僅僅依靠單個(gè)機(jī)器人完成任務(wù)往往不能盡如人意，人們希望通過(guò)多機(jī)器人之間的協(xié)調(diào)合作來(lái)彌補(bǔ)這一缺陷 [2]。與單機(jī)器人相比，使用多個(gè)機(jī)器人進(jìn)行協(xié)作建圖具有高效、高精度、高容錯(cuò)性、高魯棒性、可重構(gòu)性、低成本等優(yōu)點(diǎn)，更適用于實(shí)際應(yīng)用中的各種復(fù)雜任務(wù)。

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

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

1 遺傳算法原理

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

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

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

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

然而，傳統(tǒng)的遺傳算法應(yīng)用到實(shí)際中時(shí)會(huì)產(chǎn)生一些問(wèn)題：

a）全局搜索能力強(qiáng)而局部尋優(yōu)能力較差。

b）易出現(xiàn)早熟收斂現(xiàn)象，使問(wèn)題的求解陷于局部極值點(diǎn)。表現(xiàn)為群體中最優(yōu)個(gè)體的適應(yīng)度值得不到提高，群體在經(jīng)過(guò)若干次迭代后仍找不到全局最優(yōu)解。

c）對(duì)搜索空間變化的適應(yīng)能力差。當(dāng)搜索空間變化時(shí)，搜索策略卻沒(méi)有相應(yīng)的變化。

d）交叉、變異操作的隨機(jī)性較強(qiáng)，致使搜索效率低下。

本文針對(duì)機(jī)器人所構(gòu)建的柵格地圖，對(duì)基本遺傳算法引入了自適應(yīng)策略等改進(jìn)方法，設(shè)計(jì)了一種用于最優(yōu)轉(zhuǎn)換函數(shù)搜索的改進(jìn)遺傳算法流程。

2 協(xié)作建圖方法

2.1 問(wèn)題描述

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

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

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

在地圖融合過(guò)程中，需要通過(guò)適當(dāng)?shù)霓D(zhuǎn)換函數(shù)對(duì)地圖進(jìn)行平移和旋轉(zhuǎn)。設(shè)a，b，φ為三個(gè)實(shí)數(shù)，可將該轉(zhuǎn)換函數(shù)定義為

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

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

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

2.2 遺傳搜索

2.2.1 編碼

用遺傳算法進(jìn)行參數(shù)提取時(shí)，首先需要通過(guò)編碼將模型中的一套參數(shù)轉(zhuǎn)換成遺傳算法種群中的一個(gè)個(gè)體，常用的編碼方法有二進(jìn)制編碼和浮點(diǎn)數(shù)編碼。二進(jìn)制編碼使用的符號(hào)集由二進(jìn)制符號(hào)0和1組成，其每個(gè)個(gè)體由一個(gè)二進(jìn)制符號(hào)串描述。其優(yōu)點(diǎn)是編/解碼操作簡(jiǎn)單，交叉、變異等遺傳操作便于實(shí)現(xiàn)。但由于模型中的大部分參數(shù)在某個(gè)區(qū)間連續(xù)取值，二進(jìn)制編碼在離散化時(shí)存在映射誤差。如果碼串較短，可能達(dá)不到精度要求；如果碼串較長(zhǎng)，會(huì)使算法的搜索空間急劇擴(kuò)大，造成遺傳算法的時(shí)間性能降低。

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

2.2.2 適應(yīng)度函數(shù)

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

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

Δ(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表示柵格地圖中的置信度集合，在本文中，只考慮柵格是否被障礙物占據(jù)兩種情況，即C=[0，1]；numc(m1)表示地圖m1中置信度為c的柵格數(shù)；dist(p1，p2)為柵格p1與p2的距離。常見的距離測(cè)度函數(shù)有歐氏距離、切削距離和街區(qū)距離[11]。在本文中為了避免過(guò)大的計(jì)算量，使用街區(qū)距離計(jì)算垂直和水平路徑，即點(diǎn)p1和p2之間的街區(qū)距離為

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

2.2.3 選擇機(jī)制

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

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

2.2.4 交叉與變異

遺傳算法一般采用固定的交叉算子pc（0.5~0.9）和變異算子pm（0.001~0.2）。單純?cè)龃髉c和pm的值可以增強(qiáng)遺傳算法的全局搜索能力，但同時(shí)降低了其局部尋優(yōu)能力[12]。本文對(duì)交叉和變異算子引入自適應(yīng)策略，用gdm作為衡量每代群體中個(gè)體多樣性的量度，則既可以兼顧全局搜索和局部尋優(yōu)，又可以動(dòng)態(tài)地控制遺傳操作。gdm定義為

gdm=f/fmax(7)

其中：f為當(dāng)前代的適應(yīng)度平均值；fmax為當(dāng)前代的最大適應(yīng)值，gdm值越大，則個(gè)體越集中，個(gè)體的多樣性越小，需要適當(dāng)增加變異概率而減小交叉概率來(lái)增加個(gè)體的多樣性以防止遺傳算法收斂于局部最優(yōu)；反之，gdm越小，則個(gè)體多樣性越多，此時(shí)就適當(dāng)減小變異概率而增加交叉概率。

2.2.5 停機(jī)準(zhǔn)則

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

3 實(shí)驗(yàn)結(jié)果

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

a)構(gòu)建局部柵格地圖m1和m2。

b)在搜索窗內(nèi)隨機(jī)產(chǎn)生N個(gè)初始種群，每個(gè)個(gè)體表示轉(zhuǎn)換函數(shù)的系列參數(shù)a，b，φ。初始種群數(shù)N=50。

c)對(duì)每個(gè)個(gè)體計(jì)算適應(yīng)度函數(shù)Δ(m1，Ta，b，φ(m2))作為尋優(yōu)度量。

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

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

f)輸出最優(yōu)轉(zhuǎn)換函數(shù)Ts(a，b，φ)。

g)依據(jù)最優(yōu)轉(zhuǎn)換函數(shù)對(duì)m2進(jìn)行平移和旋轉(zhuǎn)，并與m1融合。



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



4 結(jié)束語(yǔ)

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

目前本文提出的方法只應(yīng)用于兩個(gè)機(jī)器人的復(fù)雜環(huán)境探測(cè)實(shí)驗(yàn)中，今后，筆者將研究更多機(jī)器人的協(xié)作建圖情況。此外還將進(jìn)一步改進(jìn)所采用的遺傳搜索算法，以提高地圖構(gòu)建的效率和準(zhǔn)確性。

參考文獻(xiàn)：

[1]蔡自興， 賀漢根， 陳虹. 未知環(huán)境中移動(dòng)機(jī)器人導(dǎo)航控制研究的若干問(wèn)題[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]田瑩， 苑瑋琦. 遺傳算法在圖像處理中的應(yīng)用[J]. 中國(guó)圖象圖形學(xué)報(bào)， 2007，12(3):389-396.

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