基于改進RRT算法的露天礦路徑優化模型

黃金彪，白潤才，劉 威，柴森霖，劉光偉

(1. 遼寧工程技術大學 礦業學院，遼寧 阜新 123000；2. 寧夏煤炭基本建設有限公司，寧夏 銀川 750004；3. 遼寧工程技術大學 遼寧省高等學校礦產資源開發利用技術及裝備研究院，遼寧 阜新 123000；4. 遼寧工程技術大學 理學院，遼寧 阜新 123000；5. 鹽城工學院 經濟管理學院,江蘇 鹽城 224051)

露天礦道路運輸系統優化問題一直是礦山系統工程及規劃、優化建模所需要重點考慮的關鍵問題之一，對于提高露天礦的產量規模、作業效率具有重要意義[1-4]。特別是，隨著部分礦山產量規模及作業設備的逐步大型化，運輸系統對于剝、采、排各系統的銜接紐帶作用逐步凸顯，原本靜態的道路優化及路徑規劃方法難以應付復雜條件下的優化、規劃任務。因此，嘗試采用特定的優化、規劃模型對露天礦運輸道路及尋徑問題進行有效求解，對于提高礦山產能及效率、優化現場生產調度流程將具有切實意義。

目前，國內外學者對于運輸線路及運輸系統規劃問題研究主要集中于2類：① 為對礦山初始運輸溝道的開拓定線及既有坑線的動態更新算法的研究，如余鼎[5]針對于山坡露天礦的特殊地理地形條件，提出山坡型露天礦開拓定線的具體方法；朱明海[6]結合廠礦道路規范內容要求提出了三維選線方法；劉光偉等[7-8]在時變運輸功框架下，結合時空拓撲判別地方提出了全新的道路選線及線路更新判別算法；DIAZ等[9]從露天煤礦運輸系統布置過程中的波動變化入手，提出了一種用于自動更新靜態道路網絡基有向圖的新方法；② 為基于既有坑線形態及道路運輸網絡圖進行尋徑算法設計，此類研究的經典求解算法為以張幼蒂教授引入的有向圖理論[2]及其發展模型為代表，如WHITE和OLSON[10]在靜態有向圖的基礎上，基于場內等效距離全局最優化為目標，建立路徑規劃模型；HU[11]采用和聲搜索算法設計了露天礦路徑優化算法；LI等[12]提出了一種兼顧設備作業和時效性成本最小化的車輛線路優化策略；柴森霖等[13-15]在傳統有向圖規劃建模的基礎上，將時變運輸功與時空拓撲連通性的方法引入到優化建模中，提出了路徑規劃及運輸系統費用建模的全新方法。

近年來，隨著人工智能、深度學習以及最優化理論方法的快速發展，國內外學者在機器人避障、運動學規劃等多方面提出了大量效果顯著成果，其中頗具代表性的算法如：張衛波等[16]在考慮存在大量復雜障礙物避障問題的前提下，基于改進搜索策略構建了智能機器人快速尋徑算法；張玉偉等[17]基于啟發式策略對RRT*算法的尋徑策略進行了啟發式修正；鄒啟杰等[18]基于強化學習框架驅動，提出了一種未知環境下機器人快速盲尋路徑的規劃算法。雖然上述方法在其領域范圍內的實際應用情景中，均給出了自身運動規劃過程的理想化解決方案，但由于露天礦山場景的獨特性及其尋徑策略間存在主、客觀因素的自耦合現象，導致現有的此類優秀算法均無法被直接應用于指導礦山實際生產。

鑒于對露天礦尋徑算法設計重要性的考量，筆者在前述成果的基礎上，為進一步彌補現有算法在目標函數建模、執行效率等方面的局限問題，將改進RRT算法引入到求解露天礦路徑規劃問題中，嘗試利用RRT算法的檢索能力擴展尋徑算法的備選路徑解，從而進一步實現路徑連通性計算與目標函數指標值計算的分離；另外，考慮到路面受到重載卡車頻繁碾壓及周期性養護作用，對現有的時變運輸功模型[13,15]進行改進，建立全局時變成本的綜合評價模型并將其作為規劃模型的目標函數，給出了路面條件浮動狀態的下評價模型估計方法，并最終結合改進的RRT算法實現對露天礦運輸線路規劃問題的快速求解。結合現場數據仿真實驗，論證了文中算法對于解決露天礦運輸線路規劃、優化問題現實可行且有效。

1 RRT算法基本原理

快速搜索隨機樹算法(Rapidly-exploring Random Tree，RRT)是美國愛荷華州立大學的LAVALLE教授于1998年提出，是一種通過增量采樣進行隨機構建空間填充樹的高效搜索算法，由于其算法自身的索引邏輯及特性對于提升非凸、高維空間的搜索效率具有極好的適應性，且無需提前對搜索區域的環境狀態進行系統化建模或特殊的識別及幾何劃分，便可實現對存在代數約束(存在移動障礙的環境)或微分約束(局部動態或全局動態環境)的高維空間進行高效搜索，而被廣泛應用于機器人避障、運動規劃等相關問題的求解過程中。

對于經典RRT算法的執行邏輯原理如圖1所示，其偽代碼見表1。

圖1 RRT算法基本原理

表1 經典RRT算法偽代碼

表1算法中參數、方法定義及執行流程如下：Q為場景圖，即道路網絡圖；qinit為選線起始位置節點；qgoal為選線目標位置節點；n為有向圖中節點數量；R為最終搜索到的目標路徑；r搜索路徑的節點及有向邊集合；rinit()為初始化備選路徑的節點和有向邊的方法。算法從qinit開始，循環遍歷n個節點，其中i為當前遍歷節點的索引。在遍歷循環中，通過隨機散布qrandom節點構造備選節點集，并通過查找距離qrandom節點最近的qnear節點來確定算法前進方向，前進方向上以step為前進步長，從而生產qnew節點。當具備qnew節點條件后，算法以qnew,qnear節點構建有向邊，并最終通過CollisionFree方法判斷當前路徑是否可行，如可行，則確立當前路徑，直至最終到達目標節點為止。

2 露天礦路徑優化問題建模

2.1 模型的參、變量定義

為表述模型方便，現對模型中的參變量做如下定義。

(1)有向圖參、變量定義：Ω={1,2,…,n}為道路網絡有向圖中的非空節點集合；ei,j=(i,j)∈E，為道路網絡有向圖中的非空節點i，j間的有向邊，i,j∈Ω。其中，E為圖中有向邊集合。

(3)規劃模型的決策變量：xi為有向邊是否為最優路徑的可行解。

2.2 約束條件

計算模型是對現實工程場景的合理抽象，故對于場景內的部分特殊的礦山工程條件，則需通過特定的指標值約束來進行有效表達。為進一步保證模型的合理性及完整性，筆者對模型中的數值型指標約束進行如下分類。

(1)道路網絡圖中任意單一有向邊上的車流密度約束。

(1)

(2)

(2)道路網絡飽和狀態下全路徑車流密度約束。

(3)

(4)

(3)尋徑決策階段的道路通過能力約束。

(5)

2.3 目標函數

當尋徑算法選擇不同的路段組合時，不僅會觸發線路總長度、提升高度等運輸功、能耗屬性的變化，同時也會誘發路面平整度等能耗特征指標產生波動，加之重型卡車的頻繁碾壓與路面的周期性養護，會導致車-路系統間形成內蘊的耦合聯系，并進一步促進功、能關系產生極為明顯的時間效應[13-15]。鑒于對上述因素的綜合考量，在尋徑算法的規劃建模中，以差異路段及周期性道路養護作用下的路面平整度分析為切入點，結合對路面平整度時效性變化的擾動分析，建立全局時變成本綜合評價模型，并將綜合評價模型確立為優化問題的全局目標函數，具體評價模型為

Q(t)=k1U(t)+k2C(φ)

(6)

式中，Q(t)為具有時間效應的綜合評價模型；U(t)為時變運輸功函數，表達形式如式(7)所示；k1為評價模型的能耗折算系數；C(φ)為以時變阻力系數的隸屬度函數為參數的路面養護費用及成本估計函數；φ為分類型時變道路阻力系數(f(t))的隸屬度函數；k2為路面養護費用函數的折算系數。

(7)

式中，Fei,j為有向圖中任意有向邊上的時變阻力的估計值。

2.4 模型中的波動參數估計

對比式(6)，(7)兩組模型可知，模型中的未知參數主要分為：①k1，k2為2個未知參數；②U(t)，C(φ)均為未知估計。其中，k1，k2均為折算系數，為計算這部分折算系數及2組未知函數的估算結果，以神華新疆公司紅沙泉露天煤礦為例，通過利用該礦部分生產運營數據及相關數理統計進行分析。從統計結果來看，對比U和C兩組函數均勻滾動阻力的發展存在正向相關性，并通過對比該礦近4個月內會計統計出的噸公里運輸及養護費用結果，將最終評價函數Q的線性權重指標定為k1=k2=0.5。

考慮到綜合評價模型Q(t)主要包括U(t)(時變運輸功函數)和C(φ)(浮動線路條件下的路面養護費用及成本估計函數)2個部分。其中，對于時變運輸功函數，筆者團隊曾給出具體的函數估計方法[13]。在前述成果介紹方法的基礎上，以紅沙泉露天煤礦生產運營數據為例，直接給出時變阻力系數的估算過程。其中，根據紅沙泉露天礦測試路段的阻力特征變化分析結果，研究中將該礦測試研究路段共劃分為4組不同類型路面，宏觀路面特征描述及阻力系數變化范圍數據見表2。

表2 紅沙泉露天煤礦不同路面條件下的滾動阻力系數分類

當具備路面類型的分類基準后，采用趨勢估計及最小二乘方法，建立不同路面類型下的滾動阻力系數隨養護時間及累計物料量間的趨勢面估計，具體的估計結果如圖2所示。

圖2 不同特征路面上的阻力系數估計結果

對于上述滾動阻力系數的精準估計是時變運輸功計算及養護成本估計的重要基礎，當給定任意時段的滾動阻力系數的估計函數形式后，按照前述方法其運輸功計算則相對簡單，但對于路面養護則容易因超載重車頻繁碾壓、集中降雨以及養護不及時等問題，極易誘發路面養護成本出現2次波動。為保證在養護成本計算過程中，可以對上述偶發性問題進行有效評估，以該礦采場南側端幫不同水平上的2條平直運輸干線為測試區域(S1線全長2.78 km，S2線全長2.64 km)，分別進行差異環境下的道路養護成本測試，以期構造出全局合理的養護費用成本估計。

2.4.1均衡路面條件下的養護成本估計

對于所述的均衡路面條件是指預先設計的運輸道路在計劃場景中被使用，且以路面平整度范圍指標為基礎嚴格按照養護周期執行對應養護的部分路面。為保證上述條件，研究中以該礦南端幫干線S1為例，對生產運營期間該路段進行均衡路面條件養護，并排除場內的部分偶發擾動因素，如雨雪天氣、超重超負荷運載等現象，在此基礎上對不同狀態下養護費用進行合理估計及分析。

(1)常規路面平整養護狀態下的成本估計。平路機在作業線路上的隨機平整屬于常規路面養護，通常此類作業相對較為頻繁，平均每組線路的養護周期均值一般在24～28 h。為有效描述此種作業條件下的成本變化趨勢，研究中對累計物料量、養護間隔時間以及等效距離等指標分別進行相關性測試，通過對比3組不同時間段上的干線S1上的采樣數據，發現養護費用僅與等效距離間存在近似線性關系，且這種線性關系無法擬合累計物料量及養護周期等指標。其中，基于60組采樣數據所構建出的線性擬合結果如圖3所示。

圖3 路面養護費用與等效距離間的線性擬合關系

由于上述存在線性表達，故對于常規路面平整養護狀態下的成本估計均采用等效距離的線性估計來處理，其成本估計模型如式(8)所示。

Cnormal=χLeq+b

(8)

式中，Cnormal為成本估計值；χ為養護費用的等效距離折算系數；Leq為待養護線路的等效距離，km；b為費用的軸向截距。

(2)破損路面修整狀態下的成本估計。基于上述分析方法，對于破損路面上的養護成本估算，通過與養護成本間的多因素套合分析發現，修正破損路面的費用模型仍可利用線性模型來表征，僅線性模型中的ε截距項變為浮動變量，且通過多組對比分析發現，其浮動狀態及指標變化規律與全路面的平均滾動阻力系數的3次多項式曲線具有較好的擬合特性。為有效論證上述浮動截距與全路面的平均滾動阻力系數間的3次特性，研究中共采集了測試干線上不同時段內的多組滾動阻力及浮動截距數據進行擬合，其中采用3次多項式擬合出的2組干線上的曲線結果如圖4所示。

圖4 浮動截距的3次擬合曲線

通過上述分析，可知均衡路面條件下的養護費用與運輸線路的等效距離間存在明顯的線性關系，這也很好的解釋了部分場景中可以通過等效距離進行費用整體費用描述的主要原因。

2.4.2非均衡路面條件下的養護成本估計

非均衡路面與均衡路面條件下的成本估計問題存在著本質上的不同，原因在于非均衡路面受多種綜合誘因控制而產生養護成本偶發性波動，在這種情況下，養護費用將不再與等效距離間存在簡單的線性相關性。因此，為進一步確定該狀態下的養護成本，研究中以因子分析法、統計學習方法建立各主控分項作用下的最佳成本估計。具體方法如下：

(1)識別成本波動的主控誘因。為確定出非均衡路面條件下的成本波動控制因素，研究中將統計數據中的主控要素重點分為5組，具體指標如圖5所示，其中，0.1，0.2，…，0.5為相關系數。并以上述主控指標為依據，結合論文現有測試線路確定出5種綜合誘因。

圖5 分類型引誘條件下的主控因素作用

(2)非主控誘因的非均衡路面成本估計。當識別出主控成本波動誘因后，5種誘因形成對波動函數的綜合作用，且作用函數待估計，且函數形態未知。為進一步提高此類估計過程的精度，研究中嘗試采用SVR(支持向量非線性回歸模型，Support Vector Regression)進行回歸建模，基于最小二乘思想，同時考慮在希爾伯特空間內多元回歸問題具有線性可分特性，故對于任意擬合點均可嘗試擬合基于y=ωTx的線性表達，故其具有損失的目標函數均可按照式(9)，(10)中函數形態進行建模。

(9)

s.t.δi=ωTφ(xi)+η-yi,i=1,2,…，N

(10)

式中，ω為權系數向量；φ(xi)為輸入參數到希爾伯特空間的映射；x為對主探誘因進行量化后的指標向量；C為懲罰因子；η為模型偏差；λ為誤差權重向量；λi為向量中的一個值。

當具備全局目標函數后，多元回歸問題則轉化為在希爾伯特空間線性可分的最優化問題，對應指標值的求解則可通過智能優化算法(如遺傳算法、蟻群算法等)進行迭代求解。

3 基于改進RRT的路徑優化算法

露天礦的路徑優化問題與機器人避障等傳統的運動學規劃問題隨同屬路徑規劃或尋徑問題，但2者間對于優化及規劃建模則有著本質上的差異。其中，避障問題更注重對于場景地圖連通性的判別，且場景地圖一般不可知，存在無現實可行解的情況；而露天礦尋徑問題的運輸網絡在計劃階段內其圖結構是可知的，且其路徑的可行解定然滿足連通性條件，但解集內路徑會存在明顯的費用差異，且費用計算任務更為繁重。因此，為保證算法在具體尋徑過程中具有更好的效果及效率表現，將改進的RRT算法引入到路徑優化算法的設計過程中，試圖通過RRT算法隨機特性，為優化算法提供啟發式策略及路徑連通性的判別結果，最終輔助優化算法實現快速尋徑計算。

3.1 基于改進RRT算法的啟發式策略

原始的RRT算法在地圖空間內多以均勻隨機采樣策略來完成對尋徑算法的建模，以最大限度的保證算法的避障能力，但對于文中基于改進有向圖內的尋徑算法設計將直接影響算法的執行效率。為保證算法可以具有快速拓撲及優化能力，文中從采樣策略及鄰近點選擇2個方面入手，對RRT算法進行改進，以期為后續的遺傳算法快速迭代計算提供連通性判別依據。

3.1.1采樣策略修正

在經典RRT算法中，對區域內擴展點的采樣采用均勻隨機采樣策略，其優點在于可以發現更多不同類型的路徑來參與碰撞檢測，但也受制于采樣規模，當采樣規模較大時，算法迭代效率較低，特別是類似于文中需要頻繁計算全局的費用指標的決策過程，經典算法無法滿足特定工程背景下的效率需求。

為有效解決上述局限性問題，嘗試引入浮動同心圓采樣策略[16-17]，并結合文中算法的尋徑目標對采樣策略的浮動策略進行修正。其核心思想是嘗試利用如式(11)所示的圓的極坐標方程，以目標點為中心、浮動半徑ρ向外逐步擴展采樣，計算新的隨機點坐標(xqrandom,yqrandom)。其中，隨機點(xqrandom,yqrandom)的隨機采樣位置指導后續尋徑過程中的采樣方向。

(11)

式中，ρ為同心圓采樣區域的浮動半徑，由后續鄰近點選擇策略控制；(xqgoal,yqgoal)及(xqrandom,yqrandom)分別為描述目標點及隨機點坐標值。

3.1.2鄰近點的選擇

浮動同心圓采樣策略雖在一定程度上可以減緩全區隨機采樣的枚舉規模，但由于可以在圓周上全角度的初始化坐標角度，則仍存在隨機采樣規模不可控的現實問題。因此，為進一步保證采樣范圍可控且路徑前進方向不存在回溯問題，文獻[16]利用路徑點夾角特性而非物理距離指標進行采樣區域臨近點選擇的具體方法，對啟發式算法進行設計。

具體原理如圖6所示，選擇過程為：在規劃初始階段，算法以起始點為RRT算法隨機樹r的根節點，并以該點為基礎采用同心圓采樣策略向外擴展隨機點qrandom。當確定隨機點后，算法首先在浮動同心圓內搜索有向圖節點，若在同心圓內存在節點ni，則遍歷r上的所有qi節點，分別計算每一組qrandom，qi組成的有向邊與x軸向的夾角，記為φr-i，以及qi，ni組成的有向邊與x軸向間的夾角，記為φn-i，并利用式(12)進行判斷，保證每組角度應控制在φΔ角度容差范圍內；否則，調整浮動同心圓采樣半徑大小。

圖6 鄰近點方向性約束原理

Δ(qrandom,qi,ni)=|φr-i-φn-i|<φΔ

(12)

式中，φΔ為鄰近點角度約束，該角度控制在6°以內。

3.2 融合啟發式策略的尋徑算法設計

對于RRT算法的改進僅能實現對備選路徑解連通性的判別，并不能對路徑規劃模型進行求解。因此，為保證尋徑算法可以快速搜索出路網中的全局最優解，文中嘗試將連通性的啟發式計算策略融合到遺傳編碼過程中，實現對備選路徑解的啟發式編碼，并以min[1/Q(t)]為目標函數進行最優化建模，最終利用遺傳算法迭代出全局最優解。具體最優化算法設計及執行邏輯流程如圖7所示，其中G表示遺傳算法種群迭代的次數。

圖7 改進遺傳算法邏輯流程

4 仿真實驗對比分析

為有效驗證算法的現實有效性及性能表現，在前述分析結果的基礎上，以常規養護狀態、偶發性的天氣變化以及多類型車型參與運輸等情況的分析任務為基礎，在采場內選擇不同的5組路線，分別計算綜合折算費用(運輸功轉化成本+路面養護成本)。試驗模型中5條線路的初始化條件及指標參數賦值情況如下，其中R1～R5五條線路的平均路面滾動阻力系數分別為0.047 1,0.024 6,0.033 9,0.046 8,0.041 2。遺傳算法試驗參數：算法種群規模為50；最大進化次數150次；交叉概率0.8，變異概率0.05。實例運輸卡車采用MT5500B，空車質量223 t，額定載質量326 t，最大載質量360 t，平裝容積158 m3，2∶1堆裝218 m3。通過重復多次優化迭代計算，遺傳算法穩定迭代后，費用評價指標收斂結果如圖8所示。

圖8 5組測試數據迭代收斂結果

觀察分析對比圖8中迭代結果發現，5組線路經150次迭代完成后，均能收斂于全局費用最優解。其中，均衡路面(R2,R3,R5三組)收斂速度較快，基本在50～60次迭代后既可以搜索到全局最優線路，而非均衡路面由于需要頻繁進行費用成本計算，迭代速度相對較慢，但在70～80次迭代計算后，同樣可以獲得不錯的全局最優解。因此，從該層面看，改進算法具有較好的迭代收斂特性。

同時，為驗證算法具有較好的收斂特性，研究中進行了多次重復測試，以驗證算法的穩定性。其中，20次重復試驗后，算法精度及穩定性評價的平均指標統計見表3。

表3 20組重復試驗對比數據

對5組實例進行20次重復試驗后，對比統計結果發現，在R1,R4,R5三組路徑上，重復迭代20次后，算法均能收斂于最優解；而R2,R3兩組在20次測試過程中，均出現一次無法收斂于參考值的現象，但其平均誤差不到1%，對于路徑規劃露天礦路徑問題影響不大，能滿足露天礦尋徑算法的現實需求。

5 結 論

(1)為有效解決傳統模型評價建模困難、尋徑效率受限等問題，在時變運輸功計算的基礎上，將車路兩系統產生的能耗費用耦合看待，提出了兼顧路面隨機損傷作用下的尋徑費用評價函數及路徑規劃模型，改善了現有運輸系統規劃建模過程中缺失路面損傷成本考量的部分局限性問題。

(2)從智能優化算法隨機初始化備選路徑效率低下的切實問題出發，提出了規劃模型標量計算與拓撲連通性判別相分離的基本思想，并基于快速搜索隨機樹算法改進了遺傳算法尋徑過程中的遺傳編碼方式，提出了備選路徑拓撲連通性判別方法。

(3)車輛運輸過程中路面變化不但會引起車輛能耗變化，同時也會帶來路面養護成本的波動變化，通過分析不同路面狀態下的養護成本波動規律，證實了傳統基于等效路徑折算的成本組成僅適用于均衡路面條件，真實礦山生產過程中，路面狀態常介于均衡與非均衡之間。因此，傳統的費用折算方法在精準估計時并不準確。

(4)通過對比多組重復實驗及部分尋徑算法，證實基于車-路耦合思想所構建的兼顧路面隨機損傷作用的費用評價函數及路徑規劃模型現實有效，能作為現有礦山尋徑任務的替代算法，對于降低礦山運輸系統總體能耗、指導礦山生產實踐及組織協調具有重要現實意義。