張潤梅，任 瑞，袁 彬+，羅谷安，畢利君

(1.安徽建筑大學 機械與電氣工程學院，安徽 合肥 230601；2.安徽建筑大學 工程機械智能制造重點實驗室，安徽 合肥 230601)

0 引 言

裝配式建筑是促進建筑產(chǎn)業(yè)現(xiàn)代化發(fā)展的新型建造方式，但其技術(shù)難度較高，發(fā)展限制性較大，為了進一步提高工作效率，減輕工人勞動強度，建筑機器人的引入是建筑行業(yè)發(fā)展的必由之路[1,2]。針對裝配式建筑環(huán)境，利用傳統(tǒng)外部傳感器采集環(huán)境信息構(gòu)建地圖時，計算量較大，且因地圖環(huán)境復雜，信息采集困難，難以構(gòu)建出完整的地圖[3]，因此，設(shè)計新型導航地圖建立方法對建筑機器人路徑尋優(yōu)有重大意義。

路徑規(guī)劃問題經(jīng)過國內(nèi)外學者多年的研究，提出了大量的遺傳蟻群優(yōu)化算法[4]。Qiang Luo等[5]提出了一種改進的蟻群算法，提高了蟻群算法的全局搜索能力。Yen CT等[6]提出了一種模糊蟻群優(yōu)化方法，可以對簡單和復雜的拓撲結(jié)構(gòu)進行路徑規(guī)劃和避障。Lamini C等[7]提出了一種改進的交叉算子，用遺傳算法在靜態(tài)環(huán)境中解決路徑規(guī)劃問題。傳統(tǒng)蟻群算法具有正、負反饋和高魯棒性的特點[8]，而遺傳算法被稱為魯棒優(yōu)化方法，利于全局擇優(yōu)。因此，通過結(jié)合兩種算法的優(yōu)點，可以提高算法的迭代速度和求解效率[9]。

本文針對裝配式建筑這一復雜的應(yīng)用新領(lǐng)域，設(shè)計了一種基于BIM融合遺傳蟻群混合式算法的路徑優(yōu)化方法，通過BIM技術(shù)對建筑物進行數(shù)字建模，建立導航地圖和實驗環(huán)境，以3種傳統(tǒng)算法和混合式算法作為搜索策略，利用軟件分別在不同規(guī)格的柵格地圖和某常規(guī)公寓的BIM施工地圖的工作環(huán)境進行了算法性能測試，探究了混合式算法在不同障礙物布局的工作環(huán)境中路徑規(guī)劃的最優(yōu)性及應(yīng)用于裝配式建筑的可行性。

1 混合式優(yōu)化算法

1.1 蟻群算法

蟻群算法是模擬螞蟻覓食的原理，尋找優(yōu)化路徑的一種幾率型算法[10]。蟻群算法在求解機器人路徑優(yōu)化問題時，主要內(nèi)容如下：

(1)輸入機器人要尋找最優(yōu)路徑的地圖，并初始化各種信息參數(shù)。

(2)利用輪盤法選擇下一步節(jié)點

(1)

式中：α、β分別表示信息素、距離對螞蟻選擇路徑的影響程度；τij(t)表示路徑(i,j)上的信息素濃度；ηij(t)表示與路徑(i,j)相關(guān)聯(lián)的啟發(fā)式信息；Jk(i)表示螞蟻路徑搜索下一步所有可選路徑。

(3)持續(xù)更新路徑和路徑長度，直到某一代m只螞蟻全部迭代結(jié)束。

(4)更新信息素矩陣，未到達的螞蟻不計算在內(nèi)

τij(t+1)=(1-ρ)τij(t)+Δτij(t)

(2)

(3)

(4)

(5)當?shù)趎代螞蟻迭代結(jié)束時，算法結(jié)束，得到最優(yōu)路徑。

1.2 遺傳算法

遺傳算法是一種模擬自然界生物進化機制的智能優(yōu)化算法，主要通過種群初始化、適應(yīng)度函數(shù)計算、選擇、交叉和變異求出機器人路徑規(guī)劃的最優(yōu)解[11]。移動機器人利用遺傳算法在柵格環(huán)境中進行路徑尋優(yōu)時，主要內(nèi)容如下：

(1)初始化種群，要求隨機產(chǎn)生多條可行路徑，可行路徑表示不與障礙物相碰撞的路徑。

(2)通過適應(yīng)度計算可以判斷路徑的長短和平滑程度。

(3)選擇方法最常用的是輪盤賭法，可根據(jù)每個個體的概率選擇出下一代個體，保證了部分非優(yōu)個體，有效防止產(chǎn)生局部最優(yōu)解。

(4)交叉方式通常采用單點交叉式，找出所有路徑中相同的點，隨機選擇其中一個點，將之后的路徑進行交叉操作。

(5)變異方式是隨機選取除起點和終點的任意兩柵格，使兩柵格間連續(xù)化成功。

(6)當?shù)螖?shù)達到預設(shè)數(shù)值時，算法結(jié)束，得到最優(yōu)路徑。

1.3 混合式算法原理

傳統(tǒng)的遺傳蟻群混合式算法僅在遺傳算法結(jié)果的基礎(chǔ)上，利用蟻群算法再搜索一遍[12]。本文設(shè)計了一種全新的遺傳蟻群混合式算法，在混合式算法中，以蟻群算法為基礎(chǔ)，通常每只螞蟻在構(gòu)造出一條從起點到終點的路徑后，會根據(jù)路徑的總長度來更新這條路徑所包含的每條邊上信息素的濃度，而遺傳算法的染色體編碼結(jié)構(gòu)與蟻群算法信息素結(jié)構(gòu)類似，可以將蟻群算法當前的信息素轉(zhuǎn)化為遺傳算法染色體，通過遺傳算法和精英選擇，選擇出最優(yōu)個體，再轉(zhuǎn)化為信息素增量，影響蟻群整體的信息素。經(jīng)過多次迭代計算，可以得到最優(yōu)路徑。

在編碼設(shè)計中，蟻群算法的信息素結(jié)構(gòu)設(shè)計為：每一條邊有一個優(yōu)先級，節(jié)點通過邊與周圍的節(jié)點相連接，僅和上下左右相鄰節(jié)點連接。選擇下一個節(jié)點時，在節(jié)點與相鄰節(jié)點連線間邊的優(yōu)先級基礎(chǔ)上，計算概率隨機選擇。

遺傳算法的染色體編碼結(jié)構(gòu)與蟻群算法的信息素結(jié)構(gòu)類似。因此，遺傳蟻群混合式算法通過編碼設(shè)計，能夠使遺傳算法的染色體和蟻群算法的螞蟻個體相互轉(zhuǎn)換，使遺傳算法和蟻群算法結(jié)合更加緊密，能夠得到更好搜索效果，進一步提升了算法全局搜索的能力,并極大避免陷入局部最優(yōu)解的機率。

1.4 混合式算法步驟

基于混合式算法的路徑規(guī)劃流程如圖1所示，其主要步驟如下：

步驟1初始化參數(shù)，開始迭代計算。

步驟2初代種群螞蟻進行路徑尋優(yōu)，記錄路徑和適應(yīng)度函數(shù)值。

步驟3按照遺傳算法產(chǎn)生下一代。

步驟4將當前信息素轉(zhuǎn)化為一條新的染色體，加入到子代，通過精英選擇選出新的父代種群。

步驟5將新的父代種群的最優(yōu)染色體轉(zhuǎn)化為螞蟻的搜索路徑，即轉(zhuǎn)化為信息素增量，調(diào)節(jié)并更新當前蟻群的信息素。

步驟6將新螞蟻加入到當前的螞蟻群體中，進行路徑尋優(yōu)。

圖1 遺傳蟻群混合式算法流程

步驟7如果滿足循環(huán)結(jié)束條件(收斂或者達到迭代上限)，算法結(jié)束，輸出結(jié)果，否則轉(zhuǎn)到步驟3。

2 實驗內(nèi)容

2.1 實驗方案

本文實驗配備了戴爾R730服務(wù)器和AGV小車，如圖2所示，主要是通過服務(wù)器交換實時信息，控制AGV小車運動，完成小車路經(jīng)規(guī)劃和避障工作。

圖2 戴爾R730服務(wù)器與AGV小車

實驗將在不同障礙物布局的工作環(huán)境下，分別對蟻群算法、遺傳算法、粒子群算法和遺傳蟻群混合式算法進行性能測試，以最終路徑長度和收斂迭代次數(shù)作為性能判定指標，驗證混合式算法的優(yōu)越性及應(yīng)用于裝配式建筑環(huán)境的可行性。因此，本文分別在20×20柵格地圖、30×30柵格地圖這兩種不同復雜程度的工作環(huán)境進行算法性能測試，主要通過Matlab軟件進行實驗仿真，主要參數(shù)見表1。

表1 仿真參數(shù)

2.2 柵格法

實驗環(huán)境模擬方法有許多種，如拓撲圖法、柵格法和頂點圖法等。其中柵格法在移動機器人系統(tǒng)中應(yīng)用的較為廣泛，主要是把移動機器人所在的工作環(huán)境劃進行單元分割，用等尺寸的正方形表示出來，該方法在處理障礙物邊界問題上具有較大優(yōu)勢[13]。

利用柵格法對建筑機器人的路徑規(guī)劃過程進行實驗環(huán)境建模時，可做如下假設(shè)：建筑機器人工作環(huán)境中的墻體、支持斜柱等均為有限已知的障礙物，且忽略障礙物高度。因此，可以把整個工作空間建立成XOY二維坐標系，分為障礙物區(qū)域和自由區(qū)域兩個部分，可表示為

(5)

式中：f(x,y)=1表示障礙物區(qū)域，f(x,y)=0表示移動機器人可運動的自由區(qū)域。

移動機器人在柵格環(huán)境中的運動軌跡通常有8個方向可以選擇，如圖3所示，分別是OA、OB、OC、OD、OE、OF、OG和OH。但在裝配式建筑環(huán)境的現(xiàn)實工作空間中，由于機器人體型較大且規(guī)格不一，在運動過程中，容易與墻體發(fā)生碰撞，如圖3中節(jié)點1所示。所以本文在實驗過程中將只選取OA、OB、OC、OD這4個機器人運動方向。

2.3 實驗結(jié)果與分析

本文在20×20柵格地圖的工作環(huán)境下進行算法性能測試，機器人移動路線可視化結(jié)果如圖4所示，粒子群算法的總里程為39，遺傳算法的總里程為41，蟻群算法的總里程為37，遺傳蟻群混合式算法總里程為35。其中遺傳蟻群混合式算法得到的最終路徑長度最短，且收斂迭代次數(shù)最少。

本文在30×30柵格地圖工作環(huán)境下進行算法測試，機器人移動路線可視化結(jié)果如圖5所示，粒子群算法的總里 程為67，遺傳算法的總里程為59，蟻群算法的總里程為為了便于比較遺傳蟻群混合式算法的優(yōu)勢，記錄圖4和圖5相關(guān)數(shù)據(jù)見表2。

圖3 機器人運動軌跡

109，遺傳蟻群混合式算法的總里程為55。其中遺傳蟻群混合式算法得到的最終路徑長度最短，且收斂迭代次數(shù)最少。

圖4 20×20柵格地圖工作環(huán)境下的測試結(jié)果

圖5 30×30柵格地圖工作環(huán)境下的測試結(jié)果

表2 普通地圖下4種算法指標對比

通過仿真圖和記錄的相關(guān)數(shù)據(jù)可以看出，在20×20柵格地圖和30×30柵格地圖的工作環(huán)境下，遺傳蟻群混合式算法相較于蟻群算法、遺傳算法和粒子群算法，在最終的路徑規(guī)劃長度和收斂迭代次數(shù)上都優(yōu)于其它3種算法，可以得到最短路徑和最少收斂迭代次數(shù)。實驗結(jié)果可以看出，通過遺傳算法對蟻群算法搜索路徑信息素的最優(yōu)化選擇，化為信息素增量，實時負反饋影響蟻群信息素的方法來進行路徑規(guī)劃，實際效果達到最優(yōu)，驗證了混合式算法的優(yōu)越性。

3 BIM建模

BIM(building information modeling)技術(shù)是Autodesk公司在2002年率先提出的一種應(yīng)用于建造、管理與工程設(shè)計的數(shù)字化工具[14]，具有可視化、協(xié)調(diào)性、模擬性、優(yōu)化性和可出圖性；主要通過建立虛擬的建筑工程三維模型，為項目提供一個工程信息交換和共享的平臺，有助于建筑工程信息集成程度的提高[15]。

針對裝配式建筑的復雜工作環(huán)境，因建筑機器人體型龐大，移動緩慢，在路徑尋優(yōu)過程中，利用傳統(tǒng)外部傳感器采集環(huán)境信息構(gòu)建地圖，信息采集較困難，存在計算量大，耗時，耗能的缺點，難以構(gòu)建出完整的地圖。因此，可以利用BIM技術(shù)對建筑物進行數(shù)字建模，建立一種新型導航地圖。

在移動機器人路徑規(guī)劃的過程中，利用軟件Revit2018對裝配式建筑進行數(shù)字建模，可以準確模擬出現(xiàn)實的工作環(huán)境。如圖6所示，為兩個常規(guī)裝配式建筑三維模型，主要有障礙物墻體及墻體支撐斜柱等。根據(jù)建筑物三維模型可以建立出二維導航地圖，并模擬出BIM施工地圖實驗環(huán)境。

4 工程應(yīng)用

通過BIM建立常規(guī)裝配式建筑三維模型，模擬出裝配式建筑柵格地圖，如圖7所示。

圖6 裝配式建筑三維模型

圖7 裝配式建筑柵格地圖

在常規(guī)住宅BIM柵格地圖工作環(huán)境下進行算法測試，機器人移動路線可視化結(jié)果如圖8所示，粒子群算法的總里程為40，遺傳算法的總里程為38，蟻群算法的總里程為34，遺傳蟻群混合式算法的總里程為34。遺傳蟻群混合式算法得到的最終路徑長度最短，收斂迭代次數(shù)最少。

在常規(guī)公寓BIM柵格地圖工作環(huán)境下進行算法測試，機器人移動路線可視化結(jié)果如圖9所示，粒子群算法的總里程為59，遺傳算法的總里程為57，蟻群算法的總里程為63，遺傳蟻群混合式算法的總里程為55。其中遺傳蟻群混合式算法得到的最終路徑長度最短，且收斂迭代次數(shù)最少。

為了驗證遺傳蟻群混合式算法應(yīng)用于裝配式建筑環(huán)境的可行性及優(yōu)越性，記錄圖8和圖9相關(guān)數(shù)據(jù)見表3。

通過仿真圖和記錄的相關(guān)數(shù)據(jù)可以看出，在不同規(guī)格的BIM地圖工作環(huán)境下的性能測試中，遺傳蟻群混合式算法相較于蟻群算法、遺傳算法和粒子群算法，在最終的路徑規(guī)劃長度和收斂迭代次數(shù)上均優(yōu)于其它3種算法，可以得到最短路徑和最少收斂迭代次數(shù)。實驗結(jié)果驗證了混合式算法應(yīng)用于裝配式建筑的可行性和優(yōu)越性。

5 結(jié)束語

本文設(shè)計了一種遺傳蟻群混合式算法，通過遺傳算 法染色體和蟻群算法搜索路徑的信息素相互轉(zhuǎn)換，使這兩個算法結(jié)合的更加緊密，利用該算法對裝配式建筑機器人施工路徑問題進行了研究。為了測試該算法的實際效果，在Matlab中利用柵格法，分別在20×20柵格地圖、30×30柵格地圖和BIM建模的裝配式建筑這3種不同障礙物布局的工作環(huán)境中進行了算法性能測試。實驗結(jié)果表明，與傳統(tǒng)的蟻群算法、遺傳算法和粒子群算法相比，混合式算法在優(yōu)化路徑和搜索效率方面具有更大的優(yōu)勢。驗證了遺傳蟻群混合式算法在裝配式建筑機器人路徑規(guī)劃求解過程中，具有較好的收斂性能、較優(yōu)的全局搜索能力和較高的搜索效率。同時，本文由于沒有具體的工程實驗背景，仿真結(jié)果與實際工程應(yīng)用仍將存在一定的偏差，后期需要進一步改進及驗證，但本文方法具有普適性，可為多領(lǐng)域路徑規(guī)劃提供借鑒的思想和方法。

圖8 常規(guī)住宅BIM地圖環(huán)境下的測試結(jié)果

圖9 常規(guī)公寓BIM地圖環(huán)境下的測試結(jié)果

表3 BIM地圖下4種算法指標對比