龐煒辰， 王富玉， 楊旭

(1.吉林大學(xué) 交通學(xué)院， 吉林 長春 130012； 2.長安大學(xué) 公路學(xué)院， 陜西 西安 710064)

目前中國已建成的公路總里程數(shù)增長迅速，在研究更為先進(jìn)的施工工藝及更為耐久的路面結(jié)構(gòu)與路面材料的同時，路面養(yǎng)護(hù)問題也受到越來越多的重視。在眾多路面病害形式中，路面裂縫是較為常見的一種，若路面裂縫不加以及時處理，長此以往會縮短路面的使用壽命。但是，修補裂縫的工作是一項龐大的工程，需要在待修補路段內(nèi)找到需要修補的裂縫，并完成裂縫中塵土、碎石等的清理工作，在注入密封膠后，還需進(jìn)行壓實。該過程若僅由人工完成，除耗費大量人力、物力、財力外，工作效率十分低下，修補時還需要對路段進(jìn)行關(guān)閉，會在較長時間內(nèi)影響路面的正常使用。

隨著科技的不斷進(jìn)步，工程技術(shù)也逐漸朝著機(jī)械自動化及計算智能化的趨勢發(fā)展。在這樣的大環(huán)境下，科研工作者研究出了一種自動化機(jī)械裝置，使其只需要經(jīng)過少量的人工控制就能夠完成上述修補工作?？焖?、準(zhǔn)確地實現(xiàn)這一目標(biāo)的重中之重在于為密封設(shè)備規(guī)劃出一條可不重復(fù)地遍歷設(shè)備工作區(qū)域內(nèi)所有裂縫的路徑。然而，不同路面的裂縫形態(tài)不盡相同，要想使機(jī)器設(shè)備在面對任何的裂縫分布情況時都能夠精確行走，必須研究出一種具有較強(qiáng)計算能力及較高適應(yīng)度的路徑規(guī)劃算法。該文對國外幾種路面裂縫自動化修補設(shè)備進(jìn)行研究，根據(jù)其設(shè)計思路的共性，簡要分析設(shè)備所需的功能模塊，著重概述各設(shè)備針對路徑規(guī)劃問題的解決方案，結(jié)合其他領(lǐng)域的研究成果對路徑規(guī)劃的研究進(jìn)行展望。

1 設(shè)備總體概述

自20世紀(jì)末期，國外學(xué)者開始研究并設(shè)計自動化的路面裂縫修補設(shè)備。Kim和Haas[1]于1999年提出一種基礎(chǔ)設(shè)施自動化維護(hù)模型——UT Automated Road Maintenance Machine(ARMM)，該模型包括機(jī)器視覺、人機(jī)交互、傳感器數(shù)據(jù)融合、自動任務(wù)規(guī)劃和控制循環(huán)、圖像獲取及可視化等模塊，通過修補人員與計算機(jī)計算過程的配合，可以高效地完成路面裂縫的修補工作；2004年，Lee等[2]借鑒ARMM設(shè)備的優(yōu)勢并改進(jìn)其不足，設(shè)計出一種以機(jī)器視覺為基礎(chǔ)的遠(yuǎn)程操作路面裂縫修補設(shè)備——Automated Pavement Crack Sealer(APCS)，該設(shè)備可以自動化地獲取裂縫信息并修補裂縫，還可通過手動操作修正自動化處理過程中由于識別誤差等原因而產(chǎn)生的誤差。檢測結(jié)果表明，與人工修補路面裂縫的方式相比，該設(shè)備可在很大程度上提高生產(chǎn)效率；Kim等[3]于2009年敘述二維自動化路面裂縫的修補設(shè)備時提到的CMU laboratory prototype (1990)及 CMU-UT field prototype(1992)，以及Feng等[4]描述的The Automated Crack Sealing Machine(ACSM)(1993)及The Operator Controlled Crack Sealing Machine(OCCSM)(2003)，同樣可完成類似工作。

上述裝置的共同點在于包含的主要模塊，分別為圖像獲取模塊、圖像處理模塊、路徑規(guī)劃模塊及機(jī)械控制模塊。各模塊的工作流程為：首先，圖像獲取模塊的功能是利用相機(jī)快速地捕捉路面圖像，并將其傳輸至圖像處理模塊，隨后圖像處理模塊需對采集到的圖像進(jìn)行處理，將圖像中的裂縫信息準(zhǔn)確地提取出來；其次，路徑規(guī)劃模塊找出各裂縫的端點位置，以修補設(shè)備行走距離最短為原則，或是采用只考慮當(dāng)前最優(yōu)情況的貪婪算法、或是選擇列出所有可能路徑的最短路徑算法、或是使用智能優(yōu)化算法——模擬退火的思想，為密封裝置規(guī)劃出可快速遍歷圖像中所有裂縫的行走路徑；最后，機(jī)械控制模塊控制密封裝置沿著規(guī)劃好的路徑完成修補工作。

當(dāng)前，針對圖像獲取和圖像處理模塊已進(jìn)行了較為深入的研究，對裂縫智能檢測、提取工作都有了較為深刻的認(rèn)識。馬建[5]等詳細(xì)總結(jié)了路面裂縫檢測及圖像增強(qiáng)、圖像分割、裂縫提取等相關(guān)技術(shù)的研究進(jìn)展，各類算法均較為成熟，也逐漸朝著人工智能化方向發(fā)展。但僅僅提取出路面裂縫并不是最終目的，對獲取到的需要修補的裂縫，研究出可控制密封設(shè)備自動化修補裂縫的高效算法是問題的關(guān)鍵。

2 路徑規(guī)劃問題分析

針對路徑規(guī)劃模塊，要想快速地找到較好的規(guī)劃路徑，首先需要明確規(guī)劃問題的實質(zhì)。Yoo和Kim[6]曾在2012年對路徑規(guī)劃問題的根本性質(zhì)進(jìn)行了深度剖析，在修補過程中，裂縫修補設(shè)備所走過的全部路程可分為兩個部分：① 工作區(qū)域全部裂縫長度的總和；② 車輛從起點運動到第一條待修補裂縫的端點，以及完成一條裂縫的修補工作后運行到下一條裂縫端點所走過的距離之和，稱之為冗余距離。顯然，一定區(qū)域內(nèi)全部裂縫長度的總和是固定的，因此，路徑規(guī)劃問題的關(guān)鍵是盡可能減少冗余距離，稱冗余距離最短的路徑為最優(yōu)路徑。明確了該過程后，可對修補裂縫的路徑規(guī)劃問題進(jìn)行簡化，即忽略掉裂縫的走向，僅考慮各裂縫的端點和裂縫之間的交點，這樣，該問題就可看作為一個經(jīng)典的組合優(yōu)化問題——Travelling Salesman Problem，即TSP問題。

TSP問題是一個經(jīng)典的Non-deterministic Polynomial(NP)問題，其原始問題為求解一位旅行商不重復(fù)地走遍所有城市并回到起點的最短路徑。NP問題的突出特點在于，要想求出最優(yōu)解，只有將所有解的可能性全部列出，通過比較大小找出最優(yōu)解。但隨著裂縫數(shù)量的增加，可行解的數(shù)量會急劇增加。Yoo和Kim[6]經(jīng)過計算發(fā)現(xiàn)，當(dāng)待修補區(qū)域內(nèi)存在n條裂縫時，單就裂縫的排列組合而言，可能解的個數(shù)為n!，而每條裂縫都具有兩個端點，需選擇一個端點進(jìn)入，n條裂縫共有2n種可能情況。因此，當(dāng)列出所有可行解時，算法求解的時間復(fù)雜度為O(2n×n!)，在裂縫數(shù)量較多的情況下，快速列出并存儲所有的可行解是不可能完成的任務(wù)，只能研究出一種算法，使其可以在保證計算速度的同時，盡可能找到一條冗余距離較短的路徑。也就是說，該問題研究的重點在于，找到一種能夠盡可能平衡解的質(zhì)量和計算時間的算法，即快速地求出較優(yōu)解的算法。

3 規(guī)劃算法概述

3.1 貪婪算法

在ARMM設(shè)備的設(shè)計過程中，Kim和Haas[1,7]提出可采用貪婪算法解決路面裂縫自動化修補的路徑規(guī)劃問題。貪婪算法的核心思想是：在解決一個問題時，不考慮每一個步驟對全局情況的影響，而總是做出當(dāng)前情況下最好的選擇，由此逐步進(jìn)行下去，雖然幾乎不能求得問題的最優(yōu)解，卻可極為快速地得到一個較為不錯的近似解。這種算法的核心思想非常適用于解決待修補區(qū)域內(nèi)有多條裂縫的路徑規(guī)劃問題。其計算步驟如下：

(1) 找到距離修補車輛當(dāng)前位置最近的裂縫端點，以該點為起點出發(fā)，修補第一條裂縫，直至該條裂縫終點。

(2) 找到距離上述裂縫終點最近的裂縫端點，以該點為起點出發(fā)，修補第二條裂縫，直至該條裂縫終點。

(3) 重復(fù)上步，直至修補完該區(qū)域內(nèi)全部裂縫。

上述過程即可完成工作區(qū)域內(nèi)全部裂縫的修補工作。該算法的最大優(yōu)點在于思路非常簡單，易于實現(xiàn)，但由于其僅僅遵循當(dāng)前最優(yōu)原則，故很難實現(xiàn)總體最優(yōu)，因而該方法并不十分完備。

3.2 最優(yōu)路徑算法

針對貪婪算法在求出最優(yōu)解方面的不足，APCS設(shè)備的設(shè)計者Lee等[2]提出了一種最優(yōu)路徑算法。該算法的核心思想在于利用樹形結(jié)構(gòu)列出所有的可行解，如圖1[6]所示，當(dāng)工作區(qū)域內(nèi)有4條裂縫時，具體步驟如下：

(1) 將裂縫修補車輛出發(fā)點O視為父節(jié)點，將4條裂縫視為子節(jié)點，再將每一條裂縫均視為父節(jié)點，將其他3條裂縫視為子節(jié)點，……，以此類推，將所有可能的節(jié)點排列方式均列出，即列出了裂縫的所有排列組合情況，如圖2[6]所示。

圖1 4條裂縫圖像示意圖

圖2 4條裂縫排列樹形結(jié)構(gòu)示例

(2) 考慮裂縫的兩個端點，將其分為前端點F及尾端點R，同樣將裂縫修補車輛出發(fā)點O視為父節(jié)點，無論車輛首先修補哪條裂縫，都要選擇進(jìn)入該裂縫的F點或是R點，因此，由出發(fā)點O這一父節(jié)點可指向兩個子節(jié)點，即前往裂縫的F點及R點，若車輛由F點開始修補裂縫，則在R點完成修補，那么前往下一條裂縫時，同樣會面臨F點及R點的選擇，這一過程將不斷進(jìn)行，可做出一個包含所有進(jìn)入裂縫可能點的二叉樹，如圖3[6]所示。

圖3 4條裂縫端點選擇二叉樹示意圖

(3) 在所有的可行解全部列出后，即可通過計算找到其中路徑最短的情況，該情況所對應(yīng)的裂縫及進(jìn)入各裂縫端點的排序即為求得的最優(yōu)路徑。

上述過程由于建立了兩個樹形結(jié)構(gòu)，因此又被稱為兩階段樹算法。在此基礎(chǔ)上，Yoo和Kim[6]又于2012年提出了省略第二階段的單階段樹算法。單階段樹算法沿用了兩階段樹算法中的第一階段，同樣需列出所有可能的節(jié)點(裂縫)排列方式，而將第二階段列出進(jìn)入裂縫的可能性這一步省略，僅考慮當(dāng)前情況與F點及R點之間的距離，從而簡化了計算過程。

Yoo和Kim[6]通過實例計算分析了上述兩種算法和貪婪算法的適用條件。計算結(jié)果表明：工作區(qū)域內(nèi)包含有1～6條裂縫時，選擇兩階段樹算法，包含有7～8條裂縫時，選擇單階段樹算法，包含有9條及以上數(shù)量裂縫時，選擇貪婪算法。這樣根據(jù)情況選擇3種算法之一的方式，可滿足大部分實際需要。

3.3 模擬退火算法

當(dāng)前，隨著啟發(fā)式算法研究成果的日益成熟，采用這樣的智能優(yōu)化算法對路徑進(jìn)行規(guī)劃，也是一個較為可行的思路。除此之外，便于較好地求解TSP問題的啟發(fā)式算法也受到了關(guān)注。Feng等[4]提出可采用模擬退火算法求解路徑規(guī)劃問題。該算法模擬了將固體加熱至充分高的溫度再徐徐冷卻的過程，其核心思想是在搜索到一個局部最優(yōu)解時，可以一定的概率跳出該局部最優(yōu)的情況，從而在全局范圍內(nèi)搜索到一個較優(yōu)甚至最優(yōu)的路徑，但不能保證全局最優(yōu)。這種算法的求解過程同樣較為迅速，與最優(yōu)路徑算法和貪婪算法相比，可適應(yīng)工作區(qū)域內(nèi)任意裂縫條數(shù)的情況，且隨著計算機(jī)計算速度的增加及各類編程語言的不斷發(fā)展，其編程過程也較為簡單。

3.4 交叉點的路徑選擇

在對裂縫修補路徑問題進(jìn)行簡化，從而找到合適的求解算法后，仍需針對現(xiàn)實中路面裂縫的實際情況進(jìn)一步考慮一個問題：根據(jù)裂縫走向的不同，路面裂縫通?？煞譃闄M向裂縫、縱向裂縫及網(wǎng)狀裂縫，除網(wǎng)狀裂縫中裂縫一定存在交叉的情況外，橫縱向裂縫也可能存在交叉，圖4為交叉裂縫的兩種形式，當(dāng)密封設(shè)備行走至兩條裂縫的交點處時，需明確該如何選擇設(shè)備的前進(jìn)方向[9]。

上述各類路徑規(guī)劃并沒有著重分析這一問題，但Ravani等[8]于2000年研究使用鏈表這一數(shù)據(jù)結(jié)構(gòu)及方向向量進(jìn)行路徑規(guī)劃時，提出可選擇夾角較小的方向前進(jìn)；2017年，楊延[9]在研究基于機(jī)器視覺的路面補縫軌跡控制時，明確提出在面對交叉點時，可選擇夾角較小的方向繼續(xù)進(jìn)行修補，這樣的算法實際上是直接控制了密封設(shè)備繼續(xù)沿著當(dāng)前的裂縫軌跡行走而不會在交叉點處轉(zhuǎn)至下一條裂縫。楊延通過模擬試驗證明了這種方法的可行性。

圖4 兩種形式的交叉裂縫

3.5 各方法評述

貪婪算法是路徑規(guī)劃問題中最早采用的規(guī)劃方法，由貪婪算法的核心思想可以看出：該算法的優(yōu)勢在于思路清晰、計算方法簡單、求解過程十分迅速，但也明顯存在很大弱點，即由于所求解很難保證是最優(yōu)解，因此計算得到的冗余距離較長，這會在一定程度上降低修補時的工作效率。此外，貪婪算法的突出優(yōu)勢僅在工作區(qū)域內(nèi)裂縫數(shù)量較多時才可得到明顯體現(xiàn)，當(dāng)工作區(qū)域內(nèi)僅存在1～2條裂縫時，貪婪算法所節(jié)約的計算時間與修補時在冗余距離上行走所耗費的時間相比就顯得不值一提，而在這種情況下，列出所有的可行解找出最優(yōu)路徑，反而是更好的解決思路。

最優(yōu)路徑算法的過程實質(zhì)上就是列出所有可行解的過程，樹形結(jié)構(gòu)使得排列思路更為清晰明了，使之可通過編程進(jìn)行實現(xiàn)，在建立樹形結(jié)構(gòu)后，比較所有可行路徑的大小，即可明確地得到最優(yōu)路徑。但是，樹形結(jié)構(gòu)并不能減少排列過程所需要的時間，當(dāng)裂縫數(shù)量增加時，計算時間同樣會急劇增加，因此，這種方法僅僅適用于工作區(qū)域內(nèi)裂縫數(shù)量較少的情況，并不具備普適性，若要確定使用此方法，也需在計算之前首先做出判斷，并在裂縫數(shù)量較少時選擇此方法，在裂縫數(shù)量多時選擇其他算法，例如利用上文中提出的兩階段樹算法、單階段樹算法及貪婪算法，或?qū)?種算法整合，選擇使用，計算效果會更好。

模擬退火算法則是當(dāng)下解決TSP等相關(guān)問題時更為常用的算法，由于其可依概率跳出局部最優(yōu)解，因此在使用此算法時，既可以在一定程度上彌補貪婪算法總是選擇局部最優(yōu)解導(dǎo)致的不足，又可以獲得較快的計算速度，彌補最短路徑算法的不足。此外，若選擇這類智能優(yōu)化算法，則不需要在規(guī)劃前根據(jù)裂縫數(shù)量做出選擇，算法的適用度較高。但就該算法本身而言，在具體實現(xiàn)過程中需要人為設(shè)置計算時所用到的參數(shù)，若參數(shù)選取不當(dāng)，計算結(jié)果也會不盡如人意。但是，該算法仍然具有不可替代的優(yōu)勢。

4 路徑規(guī)劃算法研究展望

由上文分析可知：裂縫修補的路徑規(guī)劃可轉(zhuǎn)化為TSP問題，那么，路徑規(guī)劃問題的求解過程也可以沿用TSP問題的求解算法。當(dāng)前，TSP問題的主流求解算法為智能優(yōu)化算法及相關(guān)改進(jìn)算法。王劍文等[10]曾在2008年總結(jié)了各類智能優(yōu)化算法，其中除模擬退火算法外，還有遺傳算法、蟻群算法、人工神經(jīng)網(wǎng)絡(luò)算法等算法，這類智能算法各自具備不同的優(yōu)勢，均可經(jīng)過改進(jìn)，使其適宜用于求解路徑規(guī)劃問題。此外，還可利用各類智能優(yōu)化算法的特點，將兩種或兩種以上的算法結(jié)合成混合優(yōu)化算法，這種改進(jìn)方法也在TSP問題的求解中得到了廣泛的應(yīng)用。因此，未來可考慮借鑒其他經(jīng)典的智能優(yōu)化算法及上文中的算法，設(shè)計出一種更為高效和準(zhǔn)確的路徑規(guī)劃算法。

5 結(jié)語

路面裂縫的自動化修補裝備可完成路面裂縫的檢測及修補工作，路徑規(guī)劃模塊是其中的核心模塊之一，當(dāng)前的研究已經(jīng)明確了路徑規(guī)劃問題的實質(zhì)，3種規(guī)劃算法——貪婪算法、最優(yōu)路徑算法及模擬退火算法均主要借鑒了求解TSP問題的相關(guān)思路，提出的算法可滿足實際要求，所有算法均可為密封設(shè)備規(guī)劃出一條行走路徑，各算法均具有不同的優(yōu)勢。但與圖像處理模塊相比，路徑規(guī)劃模塊的相關(guān)研究較少，針對交叉點問題的分析仍不夠明確，且創(chuàng)新性有待提高。未來可考慮將這些研究成果與當(dāng)前TSP問題的熱點研究成果進(jìn)行結(jié)合，在圖像處理最新技術(shù)的支撐下，研發(fā)出一種更為高效、更為一體化的自動化路面裂縫修補設(shè)備。