陳宇帆，段中興，2

(1.西安建筑科技大學(xué) 信息與控制工程學(xué)院，西安 710055；2.西部綠色建筑國家重點實驗室，西安 710055)

0 引言

隨著城市化發(fā)展的進程，出現(xiàn)了越來越多的高樓大廈與大型公共建筑，實現(xiàn)智能與自動化成為當今社會進一步發(fā)展的新契機。隨著各類機器人的出現(xiàn)，使得人們的生產(chǎn)生活方式發(fā)生了變革，解放了很多人力勞動，同時也存在著一些棘手的問題。

由于建筑室內(nèi)環(huán)境的復(fù)雜與多變，移動機器人需要在技術(shù)性能上要求更高。當前地圖構(gòu)建方式大多采用SLAM (simultaneous localization and mapping) 技術(shù)[1]，讓機器人通過傳感器在未知的環(huán)境中得到識別信息，并逐步獲取相關(guān)地圖。當環(huán)境發(fā)生較大變化時，SLAM構(gòu)建的地圖將無法使用。并且面對面積較大的場景時，使用SLAM技術(shù)也會使得構(gòu)建地圖的過程變得更加復(fù)雜和繁瑣。由于建筑信息模型BIM (building information modeling)技術(shù)的快速推進，因此在工程建設(shè)中越來越廣泛使用BIM模型，獲取建筑的信息也更加的準確及時[2]。使用BIM模型能夠快速創(chuàng)建室內(nèi)地圖，因此將BIM模型與移動機器人室內(nèi)導(dǎo)航相結(jié)合，能夠提高機器人工作的效率。對于路徑規(guī)劃，目前比較常用的有人工勢場法[3]、A*算法[4]、迪杰斯特拉算法(Dijlstra)[5]、遺傳算法[6]、蟻群算法[7]等。動態(tài)窗口法(DWA)是目前局部路徑避障的主要算法，應(yīng)用于實時碰撞避免策略[8]。文獻[9]對A*算法進行了改進，使得規(guī)劃的路徑更加平滑，但是對于有隨機障礙物出現(xiàn)的情況不適用；文獻[10]將Dijkstra算法與DWA算法相融合，在全局路徑中規(guī)劃出最短路徑，并在局部路徑規(guī)劃中實現(xiàn)避障效果，但是沒有考慮動態(tài)障礙物與機器人之間的距離，容易使得機器人在狹窄空間內(nèi)無法通過；文獻[11]中將傳統(tǒng)A*算法的8鄰域搜索改為5鄰域搜索，使用DWA算法進行局部避障，使得路徑距離變短且平滑度提高，但是沒有考慮到其5個鄰域方向同時存在障礙的情況，容易使得全局路徑無法規(guī)劃。

針對上述問題，本文在地圖建立過程中采用BIM模型，提取建筑物的空間信息，從而使地圖構(gòu)建效率得到提高，讓移動機器人能夠快速獲取和熟知室內(nèi)環(huán)境。在室內(nèi)路徑規(guī)劃中，采用全局路徑與局部路徑相結(jié)合，對A*算法進行改進，擴大其搜索鄰域，考慮機器人通過的安全性，當有動態(tài)障礙時，采用DWA算法進行避障，保障運動的連續(xù)性。

1 BIM信息提取與地圖構(gòu)建

建筑信息模型BIM(building information modeling)是一個生產(chǎn)建筑數(shù)據(jù)和使用建筑數(shù)據(jù)的過程[12]，基于模型的智能化流程，包含與物理特性和功能特性相關(guān)的數(shù)據(jù)，BIM技術(shù)能更好的還原從概念到施工的建筑模型，使得建筑建造和運營建筑基礎(chǔ)設(shè)施變得更加高效、更加精細化和透明化。

使用Autodesk Revit軟件進行BIM建模，可以對現(xiàn)實三維事物進行準確的模擬，并且能夠呈現(xiàn)出準確的信息。

1.1 IFC簡述

IFC(industry foundation class)是針對BIM數(shù)據(jù)交換的唯一的開放式標準格式。文件IFC是一種交換格式，用于不同軟件系統(tǒng)之間交換建筑設(shè)計和建造中使用的建筑數(shù)據(jù)模型，從而達到數(shù)據(jù)共享。IFC標準分為4個結(jié)構(gòu)層次，分別為資源層、核心層、交互層和領(lǐng)域?qū)覽13]，4個層次共同來完成信息資源的穩(wěn)定。IFC 中運用 EXPRESS 語言描述建筑產(chǎn)品數(shù)據(jù)[14]。EXPRESS 是一種標準化數(shù)據(jù)建模語言，其定義在 STEP 國際標準中[15]。EXPRESS語言與其他編程語言不同，更看重對計算機大規(guī)模數(shù)據(jù)的可讀性，從而實現(xiàn)對數(shù)據(jù)信息的描述。

1.2 IFC數(shù)據(jù)前期處理

通過BIM建模，導(dǎo)出IFC文件，并對IFC文件進行解析，提取出所需要的室內(nèi)幾何信息[16-17]。IFC文件的基礎(chǔ)結(jié)構(gòu)包括項目的基本內(nèi)容、基本空間結(jié)構(gòu)以及幾何表示。項目的基本內(nèi)容主要由IfcProject提供，項目的基本空間結(jié)構(gòu)主要由IfcBuilding提供，幾何表示主要由IfcBuildingElement提供。在IFC文件中，實體的屬性具有繼承關(guān)系，屬性分為：直接屬性、導(dǎo)出屬性和反屬性。其中直接屬性很直觀的表達了構(gòu)件信息，導(dǎo)出屬性是通過不同構(gòu)件實體的屬性來構(gòu)成表達，而反屬性是構(gòu)件可以通過關(guān)聯(lián)實體從而獲得相關(guān)信息。IFC文件的數(shù)據(jù)部分包含了構(gòu)建模型的坐標位置、屬性值、長寬高、空間隸屬關(guān)系等相關(guān)信息。IFC數(shù)據(jù)段中的部分坐標信息如下：

#138=IFCCARTESIANPOINT((0.，0.，10800.));

#140=IFCAXIS2PLACEMENT3D(#138，$，$);

#141=IFCLOCALPLACEMENT(#32，#140)

其中#141是對象位置信息(ObjectPlacement)，IFCLOCALPLACEMENT(#32，#140)描述了該構(gòu)件的相對位置幾何坐標，這里幾何坐標引用了#32父坐標體系。

#140=IFCAXIS2PLACEMENT3D(#138，，);指定了局部坐標系的原點位置，符號代替語句中次要信息。#138= IFCCARTESIANPOINT是位置信息，表示((0.，0.，10800.)位置處。

使用IFC解析工具對IFC文件進行解析，對所需的室內(nèi)模型構(gòu)件的幾何信息進行提取。如圖1為其中一個柱IfcColumn的屬性和地點信息。

圖1 IfcColumn的屬性和地點信息

從屬性中可以看出構(gòu)件的實體名、類型、標簽以及輪廓等。從地點中可以看到構(gòu)件的位置坐標、長寬高以及所處的樓層信息等。圖中這個柱子長度為600 mm，寬度為600 mm，高度為3 400 mm。位置坐標為(9 082.337 744，-1 837.497 743，10 800)。

1.3 構(gòu)建地圖

獲取建筑環(huán)境的邊界頂點坐標，柵格平面的長為L=Xmax-Xmin,寬為W=Ymax-Ymin。則柵格平面行數(shù)為i=[L/S]，列數(shù)為j=[W/S]，S為每個柵格所代表的實際長寬。將幾何信息映射到柵格平面時，使用構(gòu)件在二維平面圖的起終點坐標進行映射，對應(yīng)網(wǎng)格屬性為1。(屬性為1代表不可通行，為0代表可通行)。當構(gòu)件映射不滿一個柵格時，則補齊這個柵格作為不可行區(qū)域。地圖構(gòu)建過程如圖2所示。

圖2 地圖構(gòu)建過程

2 A*算法的改進

2.1 傳統(tǒng)A*算法

A*(A-Star)算法是一種啟發(fā)式搜索，利用啟發(fā)函數(shù)對搜索過程進行指導(dǎo)，在靜態(tài)環(huán)境下的路徑規(guī)劃， A*算法不但能獲得較短路徑，并且其搜索效率比較高，廣泛應(yīng)用于室內(nèi)機器人路徑搜索、游戲動畫路徑搜索。A*算法的估價函數(shù)可以表示為：

f(n)=g(n)+h(n)

(1)

f(n)是從初始狀態(tài)經(jīng)由狀態(tài)n到目標狀態(tài)的代價估計，g(n)是狀態(tài)空間中從初始到狀態(tài)n的實際代價，h(n)是從狀態(tài)n到目標狀態(tài)的最佳路徑的估計代價。

2.2 48鄰域擴展

傳統(tǒng)A*算法為8鄰域搜索，也就是在該點周圍的8個相鄰柵格方向搜索，使得機器人的轉(zhuǎn)向方向也被限制于π/4的整數(shù)倍，這樣規(guī)劃出來的路徑轉(zhuǎn)折角度較大。如果轉(zhuǎn)折角度過大，不利于機器人在室內(nèi)狹窄空間移動，也會使得移動時間變長，降低了工作效率。因此，將原先的搜索范圍擴展至48鄰域搜索如圖3所示，對8個方向上每2個方向(如D、E之間)之間再增加3個方向搜索，由原來的8個方向變?yōu)?2個方向，這樣會使機器人在方向上有更多選擇，減少轉(zhuǎn)向次數(shù)，更加流暢的進行作業(yè)。圖4為使用48鄰域搜索的路徑規(guī)劃結(jié)果圖。S為起點位置，D為終點位置，直線所連接的方塊為規(guī)劃的路徑，周圍區(qū)域為48鄰域搜索空間。

圖3 A*算法的鄰域搜索空間

圖4 48鄰域搜索結(jié)果圖

2.3 搜索路徑改進

傳統(tǒng)A*算法在規(guī)劃路徑時沒有考慮到機器人本身的輪廓大小，規(guī)劃出來的路徑容易緊貼墻壁或者障礙物。由于室內(nèi)環(huán)境會有很多門或者相鄰柱體，且隨機障礙物較多，若按照傳統(tǒng)A*算法規(guī)劃出來的路徑移動，會使得機器人與障礙物相撞，更有可能損傷機器人機身。因此，除了對傳統(tǒng)A*算法在搜索方向上進行擴展，還需要考慮機器人安全性，將規(guī)劃出來的路徑進行改進。

機器人在移動過程中，將規(guī)劃出來的路徑與障礙物的距離記為s(m)，機器人機身半徑記d(m)，規(guī)定安全距離為0.2 m，當s≥d+0.2，則表示規(guī)劃的該路徑可通過，反之，不可通過。

3 進A*與動態(tài)窗口法的融合算法

3.1 動態(tài)窗口法

動態(tài)窗口法DWA(dynamic window approach) 作為局部路徑規(guī)劃避障的主要算法[18]，能夠接受全局路徑規(guī)劃生成的路徑以及里程計的信息、地圖的信息，輸出為底盤運動的速度信息。算法流程為：根據(jù)機器人當前的速度，計算出當前可采樣的速度范圍，然后對采樣的每一組速度都依據(jù)運動模型，模擬一段時間內(nèi)的路徑。把所有采樣速度生成的路徑都模擬出來后，接著根據(jù)評價函數(shù)對每一條路徑都打分，然后選取得分最高的一條路徑，那么這條路徑就對應(yīng)了一組采樣速度，就把這一組速度作為機器人下一時刻的速度，那機器人就會以新的速度繼續(xù)移動，這時候算法就會進入新的循環(huán)，以新的速度計算新的采樣速度范圍，然后模擬路徑，再次根據(jù)得分選取路徑和速度，把選取到的速度用于下一個時刻，以這種流程不斷循環(huán)下去。所以這些模擬路徑是不斷的在變化，因為在不斷的進行采樣、模擬、評價再采樣，一直刷新模擬的路徑，那機器人就會不斷的調(diào)整自身的速度和方向，往目標點移動，從而實現(xiàn)導(dǎo)航的功能。

3.1.1 機器人運動學(xué)模型

設(shè)機器人在全向運動過程中，在X方向的速度為Vx，在Y方向的速度為Vy，角速度為w。若將機器人在相鄰時刻兩點之間的軌跡看成直線，那么在△t的時間里，運動模型可表示為：

由X方向速度產(chǎn)生的機器人的坐標變化為：

△xx=vx△tcosθt

(2)

△yx=vx△tsinθt

(3)

由Y方向速度產(chǎn)生的機器人的坐標變化為：

△xy=-vy△tsinθt

(4)

△yx=vy△tcosθt

(5)

機器人下個狀態(tài)的位置：

x=x+vx△tcosθt-vy△tsinθt

(6)

y=y+vx△tsinθt+vy△tcosθt

(7)

θt=θt+w△t

(8)

3.1.2 速度采樣

依據(jù)機器人的運動模型，通過采樣多組速度，模擬出一段時間內(nèi)的路徑。

1)機器人最大速度與最小速度限制。

vm={(v,w)|v∈[vmin,vmax]∧w∈[wmin,wmax]}

(9)

式中，Vm為機器人速度；v為線速度；w為角速度。

2)機器人加速度限制。電機的力矩是有限的，電機性能也會有所影響，使得機器人移動時的加速度不能在短時間內(nèi)無限大。所以加速度是限制了采樣速度范圍的一個因素。因此，加速度限制范圍為：

Vd={(v,w)|v∈[vc-vb△t,vc+va△t]∧w∈

[wc-wb△t,wc+wa△t]}

(10)

式中，Vd為機器人受加速度限制后的速度；Vc為當前線速度；Va為最大線加速度；Vb為最大線減速度；Wc為當前角速度；Wa為最大角加速度；Wb為最大角減速度。

3)預(yù)留安全距離。當有障礙物時，機器人不是立馬能夠停下來，因此需要預(yù)留安全距離范圍為：

Va={(v,w)|v≤(2dist(v,w)vb)1/2,w≤

(2dist(v,w)wb)1/2}

(11)

式中，dist(v，w)為機器人與障礙物之間的距離。

3.1.3 評價函數(shù)

在利用采樣速度模擬了很多路徑以后，對速度的選擇需要使用評價函數(shù)來評估軌跡的好壞[19-20]。評價函數(shù)用以下表示：

G(v,w)=σ(α·heading(v,w)+β·dist(v,w)+

γ·velocity(v,w))

(12)

式中，heading(v，w)為方位角評價函數(shù)，指的是機器人與目標之間的角度差，角度差越小，得分越高；dist(v，w)為機器人與最近障礙物之間的距離，距離越遠，得分越高；velocity(v，w)為軌跡對應(yīng)的速度大小，速度越大，得分越高。

為了避免這三項不同類別的得分基數(shù)相差太大，影響結(jié)果。比如方位角的角度差得分在0～180之間，而障礙物距離得分可能都在5以內(nèi)，這樣就容易掩蓋了障礙物距離的影響。因此，需要對這3個方面的得分進行歸一化處理，把每一項的得分占比算出來再相加。歸一化如下：

(13)

(14)

(15)

在歸一化處理后，對每一部分賦權(quán)重，不同的權(quán)重值會影響機器人選取的路徑。將這3方面綜合起來的物理意義就是使得機器人避開障礙物，朝著目標點以較快的速度移動。

3.2 融合算法

將全局路徑規(guī)劃與局部路徑規(guī)劃相結(jié)合，先由全局路徑規(guī)劃器規(guī)劃出一條大致的路徑，接著局部路徑規(guī)劃器又會將它劃分為許多小區(qū)段，再完成整個局部路徑規(guī)劃。相當于是把一個總目標分成很多個小目標然后依次達成。這樣做的好處是在全局路徑規(guī)劃的時候，對地圖保存過的障礙物進行避障，而在局部路徑規(guī)劃的時候，會對新增的障礙物信息也進行避障。并且它支持對動態(tài)的障礙物進行避障。本文算法的流程如圖5所示。

圖5 算法流程圖

4 實驗與仿真

在獲取到的樓層地圖上進行短距離和長距離兩組路徑規(guī)劃，每一組實驗中都采用傳統(tǒng)A*算法、改進A*算法、改進A*與DWA的融合算法(無障礙物)、改進A*與DWA的融合算法(有障礙物)來進行路徑規(guī)劃。第一組實驗的起點坐標為(10，28)，終點坐標為(27，14)，動態(tài)障礙物設(shè)置為2個，坐標為(14，27)、(23，20)，結(jié)果如圖6和圖7所示；第二組實驗的起點坐標為(15，16)，終點坐標為(89，27)，動態(tài)障礙物設(shè)置為3個，坐標為(32，22)、(83，22)、(84，22)，結(jié)果如圖8和圖9所示。同時，記錄了每組實驗中各算法路徑規(guī)劃的運行時間和路徑長度，對傳統(tǒng)A*算法與改進A*算法的累計轉(zhuǎn)折角度進行了計算，結(jié)果如表1～4所示。

圖6 第一組路徑傳統(tǒng)與改進算法軌跡圖

圖7 第一組路徑融合算法軌跡圖

圖9 第二組路徑融合算法軌跡圖

表1 第一組路徑傳統(tǒng)與改進算法的性能比較

由圖6和圖8可以看出：傳統(tǒng)的A*算法在規(guī)劃路徑時，路徑與墻或門的距離較近，安全性比較低。而使用改進的A*算法考慮了機器人安全性的問題，增加了路徑與障礙物的安全距離，使得機器人不再靠著墻壁移動，確保了機器人能夠順利通過。由表1表2 可知，改進的A*算法比傳統(tǒng)A*算法在運行時間上快了2倍以上，由于節(jié)點轉(zhuǎn)折角度差的減小，改進后的兩組路徑長度也都相對的優(yōu)化。其次，第一組仿真實驗傳統(tǒng)算法累計轉(zhuǎn)折角度為225°，改進算法為162°，第二組仿真實驗原始算法累計轉(zhuǎn)折角度為225°，改進算法為128°，改進的A*算法優(yōu)化了搜索角度，比傳統(tǒng)A*算法的累計轉(zhuǎn)折角度減少了28%以上。綜合來看，改進后的算法在路徑規(guī)劃在性能上都有進一步的改善，且搜索效率有所提升。

表2 第二組路徑傳統(tǒng)與改進算法的性能比較

圖8 第一組路徑傳統(tǒng)與改進算法軌跡圖

采用改進A*與DWA的融合算法規(guī)劃的路徑如圖7、9所示，分別為無障礙物和有障礙物兩種情況。動態(tài)窗口法的參數(shù)設(shè)置如下：機器人運動學(xué)模型間隔時間為0.1 s，最大速度為1 m/s，最大角加速度為20°/s，速度分辨率為0.01 m/s，角加速度分辨率為1°/s，加速度為0.2 m/s2，角加速度為50°/s2。評價函數(shù)參數(shù)為：α=0.2，β=0.2，γ=0.1，預(yù)測時間周期為3.0 s。改進A*與DWA的融合算法的配合過程就是改進的A*算法出一條大致的路徑，然后DWA算法會把改進的A*算法規(guī)劃的路徑分割成很多段，大目標分割成很多小目標，然后用DWA算法依次導(dǎo)航到每一個小目標點。當沒有障礙物時，融合算法比改進的A*算法的路徑更加連續(xù)，平滑度更高；當有動態(tài)障礙物出現(xiàn)后，融合算法能夠及時實現(xiàn)避障，由表3所知，無障礙物時，使用融合算法第一組路徑規(guī)劃整個算法用時30.99 s，路徑長度為13.053 6 m；當出現(xiàn)兩個障礙物時，整個算法用時31.89 s，路徑長度變?yōu)?4.402 6 m。由表4所知，無障礙物時，使用融合算法第二組路徑規(guī)劃整個算法用時87.35 s，路徑度為48.241 8 m；當出現(xiàn)3個障礙物時，整個算法用時89.13 s，路徑長度變?yōu)?9.872 5 m。因此隨著障礙物的出現(xiàn)，運行時間和路徑長度也理應(yīng)有所增加。綜合來說，融合算法規(guī)劃的路徑平滑度更好，并且能及時避開出現(xiàn)的隨機障礙物，使得機器人在室內(nèi)場所的移動更加安全。

表3 第一組路徑融合算法的性能比較

表4 第二組路徑融合算法的性能比較

圖10為選取了第一組短路徑下傳統(tǒng)A*算法和融合算法的控制參數(shù)對比，機器人在傳統(tǒng)A*算法下的線速度和角速度變化范圍較大，變化不連續(xù)，這樣會不利于機器人的移動，長時間會損傷機器人機身。而在融合算法下的線速度變化波動較小，比較平穩(wěn)，并且角速度的曲率變化比較平滑連續(xù)，更符合機器人的動力學(xué)控制，也會使得機器人整個行駛過程變得流暢。

圖10 第一組路徑控制參數(shù)對比

5 結(jié)束語

通過BIM技術(shù)提取建筑空間信息，節(jié)省了機器人獲取室內(nèi)環(huán)境的時間，同時也提高了地圖構(gòu)建的效率。針對移動機器人路徑規(guī)劃問題，對傳統(tǒng)A*算法進行了改進，通過仿真結(jié)果得知累計轉(zhuǎn)折角度減少了28%以上，運行時間也快了2倍。同時，設(shè)置了路徑與障礙物的安全距離，保證了機器人的安全性。此外，為了解決移動機器人行駛過程中遇到動態(tài)障礙物的問題，將改進A*的算法和動態(tài)窗口法相結(jié)合，并對融合算法也進行了實驗仿真和性能對比，驗證了本文的融合算法路徑連續(xù)性更高，達到了避障能力，更具有環(huán)境適用性。