裝配式建筑機器人施工路徑優化方法

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

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

0 引 言

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

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

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

1 混合式優化算法

1.1 蟻群算法

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

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

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

(1)

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

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

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

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

(2)

(3)

(4)

(5)當第n代螞蟻迭代結束時，算法結束，得到最優路徑。

1.2 遺傳算法

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

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

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

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

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

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

(6)當迭代次數達到預設數值時，算法結束，得到最優路徑。

1.3 混合式算法原理

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

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

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

1.4 混合式算法步驟

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

步驟1初始化參數，開始迭代計算。

步驟2初代種群螞蟻進行路徑尋優，記錄路徑和適應度函數值。

步驟3按照遺傳算法產生下一代。

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

步驟5將新的父代種群的最優染色體轉化為螞蟻的搜索路徑，即轉化為信息素增量，調節并更新當前蟻群的信息素。

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

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

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

2 實驗內容

2.1 實驗方案

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

圖2 戴爾R730服務器與AGV小車

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

表1 仿真參數

2.2 柵格法

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

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

(5)

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

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

2.3 實驗結果與分析

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

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

圖3 機器人運動軌跡

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

圖4 20×20柵格地圖工作環境下的測試結果

圖5 30×30柵格地圖工作環境下的測試結果

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

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

3 BIM建模

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

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

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

4 工程應用

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

圖6 裝配式建筑三維模型

圖7 裝配式建筑柵格地圖

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

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

為了驗證遺傳蟻群混合式算法應用于裝配式建筑環境的可行性及優越性，記錄圖8和圖9相關數據見表3。

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

5 結束語

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

圖8 常規住宅BIM地圖環境下的測試結果

圖9 常規公寓BIM地圖環境下的測試結果

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