路面裂缝自动化修补中路径规划研究的进展概述与展望

庞炜辰， 王富玉， 杨旭

(1.吉林大学 交通学院， 吉林 长春 130012； 2.长安大学 公路学院， 陕西 西安 710064)

目前中国已建成的公路总里程数增长迅速，在研究更为先进的施工工艺及更为耐久的路面结构与路面材料的同时，路面养护问题也受到越来越多的重视。在众多路面病害形式中，路面裂缝是较为常见的一种，若路面裂缝不加以及时处理，长此以往会缩短路面的使用寿命。但是，修补裂缝的工作是一项庞大的工程，需要在待修补路段内找到需要修补的裂缝，并完成裂缝中尘土、碎石等的清理工作，在注入密封胶后，还需进行压实。该过程若仅由人工完成，除耗费大量人力、物力、财力外，工作效率十分低下，修补时还需要对路段进行关闭，会在较长时间内影响路面的正常使用。

随着科技的不断进步，工程技术也逐渐朝着机械自动化及计算智能化的趋势发展。在这样的大环境下，科研工作者研究出了一种自动化机械装置，使其只需要经过少量的人工控制就能够完成上述修补工作。快速、准确地实现这一目标的重中之重在于为密封设备规划出一条可不重复地遍历设备工作区域内所有裂缝的路径。然而，不同路面的裂缝形态不尽相同，要想使机器设备在面对任何的裂缝分布情况时都能够精确行走，必须研究出一种具有较强计算能力及较高适应度的路径规划算法。该文对国外几种路面裂缝自动化修补设备进行研究，根据其设计思路的共性，简要分析设备所需的功能模块，着重概述各设备针对路径规划问题的解决方案，结合其他领域的研究成果对路径规划的研究进行展望。

1 设备总体概述

自20世纪末期，国外学者开始研究并设计自动化的路面裂缝修补设备。Kim和Haas[1]于1999年提出一种基础设施自动化维护模型——UT Automated Road Maintenance Machine(ARMM)，该模型包括机器视觉、人机交互、传感器数据融合、自动任务规划和控制循环、图像获取及可视化等模块，通过修补人员与计算机计算过程的配合，可以高效地完成路面裂缝的修补工作；2004年，Lee等[2]借鉴ARMM设备的优势并改进其不足，设计出一种以机器视觉为基础的远程操作路面裂缝修补设备——Automated Pavement Crack Sealer(APCS)，该设备可以自动化地获取裂缝信息并修补裂缝，还可通过手动操作修正自动化处理过程中由于识别误差等原因而产生的误差。检测结果表明，与人工修补路面裂缝的方式相比，该设备可在很大程度上提高生产效率；Kim等[3]于2009年叙述二维自动化路面裂缝的修补设备时提到的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)，同样可完成类似工作。

上述装置的共同点在于包含的主要模块，分别为图像获取模块、图像处理模块、路径规划模块及机械控制模块。各模块的工作流程为：首先，图像获取模块的功能是利用相机快速地捕捉路面图像，并将其传输至图像处理模块，随后图像处理模块需对采集到的图像进行处理，将图像中的裂缝信息准确地提取出来；其次，路径规划模块找出各裂缝的端点位置，以修补设备行走距离最短为原则，或是采用只考虑当前最优情况的贪婪算法、或是选择列出所有可能路径的最短路径算法、或是使用智能优化算法——模拟退火的思想，为密封装置规划出可快速遍历图像中所有裂缝的行走路径；最后，机械控制模块控制密封装置沿着规划好的路径完成修补工作。

当前，针对图像获取和图像处理模块已进行了较为深入的研究，对裂缝智能检测、提取工作都有了较为深刻的认识。马建[5]等详细总结了路面裂缝检测及图像增强、图像分割、裂缝提取等相关技术的研究进展，各类算法均较为成熟，也逐渐朝着人工智能化方向发展。但仅仅提取出路面裂缝并不是最终目的，对获取到的需要修补的裂缝，研究出可控制密封设备自动化修补裂缝的高效算法是问题的关键。

2 路径规划问题分析

针对路径规划模块，要想快速地找到较好的规划路径，首先需要明确规划问题的实质。Yoo和Kim[6]曾在2012年对路径规划问题的根本性质进行了深度剖析，在修补过程中，裂缝修补设备所走过的全部路程可分为两个部分：① 工作区域全部裂缝长度的总和；② 车辆从起点运动到第一条待修补裂缝的端点，以及完成一条裂缝的修补工作后运行到下一条裂缝端点所走过的距离之和，称之为冗余距离。显然，一定区域内全部裂缝长度的总和是固定的，因此，路径规划问题的关键是尽可能减少冗余距离，称冗余距离最短的路径为最优路径。明确了该过程后，可对修补裂缝的路径规划问题进行简化，即忽略掉裂缝的走向，仅考虑各裂缝的端点和裂缝之间的交点，这样，该问题就可看作为一个经典的组合优化问题——Travelling Salesman Problem，即TSP问题。

TSP问题是一个经典的Non-deterministic Polynomial(NP)问题，其原始问题为求解一位旅行商不重复地走遍所有城市并回到起点的最短路径。NP问题的突出特点在于，要想求出最优解，只有将所有解的可能性全部列出，通过比较大小找出最优解。但随着裂缝数量的增加，可行解的数量会急剧增加。Yoo和Kim[6]经过计算发现，当待修补区域内存在n条裂缝时，单就裂缝的排列组合而言，可能解的个数为n!，而每条裂缝都具有两个端点，需选择一个端点进入，n条裂缝共有2n种可能情况。因此，当列出所有可行解时，算法求解的时间复杂度为O(2n×n!)，在裂缝数量较多的情况下，快速列出并存储所有的可行解是不可能完成的任务，只能研究出一种算法，使其可以在保证计算速度的同时，尽可能找到一条冗余距离较短的路径。也就是说，该问题研究的重点在于，找到一种能够尽可能平衡解的质量和计算时间的算法，即快速地求出较优解的算法。

3 规划算法概述

3.1 贪婪算法

在ARMM设备的设计过程中，Kim和Haas[1,7]提出可采用贪婪算法解决路面裂缝自动化修补的路径规划问题。贪婪算法的核心思想是：在解决一个问题时，不考虑每一个步骤对全局情况的影响，而总是做出当前情况下最好的选择，由此逐步进行下去，虽然几乎不能求得问题的最优解，却可极为快速地得到一个较为不错的近似解。这种算法的核心思想非常适用于解决待修补区域内有多条裂缝的路径规划问题。其计算步骤如下：

(1) 找到距离修补车辆当前位置最近的裂缝端点，以该点为起点出发，修补第一条裂缝，直至该条裂缝终点。

(2) 找到距离上述裂缝终点最近的裂缝端点，以该点为起点出发，修补第二条裂缝，直至该条裂缝终点。

(3) 重复上步，直至修补完该区域内全部裂缝。

上述过程即可完成工作区域内全部裂缝的修补工作。该算法的最大优点在于思路非常简单，易于实现，但由于其仅仅遵循当前最优原则，故很难实现总体最优，因而该方法并不十分完备。

3.2 最优路径算法

针对贪婪算法在求出最优解方面的不足，APCS设备的设计者Lee等[2]提出了一种最优路径算法。该算法的核心思想在于利用树形结构列出所有的可行解，如图1[6]所示，当工作区域内有4条裂缝时，具体步骤如下：

(1) 将裂缝修补车辆出发点O视为父节点，将4条裂缝视为子节点，再将每一条裂缝均视为父节点，将其他3条裂缝视为子节点，……，以此类推，将所有可能的节点排列方式均列出，即列出了裂缝的所有排列组合情况，如图2[6]所示。

图1 4条裂缝图像示意图

图2 4条裂缝排列树形结构示例

(2) 考虑裂缝的两个端点，将其分为前端点F及尾端点R，同样将裂缝修补车辆出发点O视为父节点，无论车辆首先修补哪条裂缝，都要选择进入该裂缝的F点或是R点，因此，由出发点O这一父节点可指向两个子节点，即前往裂缝的F点及R点，若车辆由F点开始修补裂缝，则在R点完成修补，那么前往下一条裂缝时，同样会面临F点及R点的选择，这一过程将不断进行，可做出一个包含所有进入裂缝可能点的二叉树，如图3[6]所示。

图3 4条裂缝端点选择二叉树示意图

(3) 在所有的可行解全部列出后，即可通过计算找到其中路径最短的情况，该情况所对应的裂缝及进入各裂缝端点的排序即为求得的最优路径。

上述过程由于建立了两个树形结构，因此又被称为两阶段树算法。在此基础上，Yoo和Kim[6]又于2012年提出了省略第二阶段的单阶段树算法。单阶段树算法沿用了两阶段树算法中的第一阶段，同样需列出所有可能的节点(裂缝)排列方式，而将第二阶段列出进入裂缝的可能性这一步省略，仅考虑当前情况与F点及R点之间的距离，从而简化了计算过程。

Yoo和Kim[6]通过实例计算分析了上述两种算法和贪婪算法的适用条件。计算结果表明：工作区域内包含有1～6条裂缝时，选择两阶段树算法，包含有7～8条裂缝时，选择单阶段树算法，包含有9条及以上数量裂缝时，选择贪婪算法。这样根据情况选择3种算法之一的方式，可满足大部分实际需要。

3.3 模拟退火算法

当前，随着启发式算法研究成果的日益成熟，采用这样的智能优化算法对路径进行规划，也是一个较为可行的思路。除此之外，便于较好地求解TSP问题的启发式算法也受到了关注。Feng等[4]提出可采用模拟退火算法求解路径规划问题。该算法模拟了将固体加热至充分高的温度再徐徐冷却的过程，其核心思想是在搜索到一个局部最优解时，可以一定的概率跳出该局部最优的情况，从而在全局范围内搜索到一个较优甚至最优的路径，但不能保证全局最优。这种算法的求解过程同样较为迅速，与最优路径算法和贪婪算法相比，可适应工作区域内任意裂缝条数的情况，且随着计算机计算速度的增加及各类编程语言的不断发展，其编程过程也较为简单。

3.4 交叉点的路径选择

在对裂缝修补路径问题进行简化，从而找到合适的求解算法后，仍需针对现实中路面裂缝的实际情况进一步考虑一个问题：根据裂缝走向的不同，路面裂缝通常可分为横向裂缝、纵向裂缝及网状裂缝，除网状裂缝中裂缝一定存在交叉的情况外，横纵向裂缝也可能存在交叉，图4为交叉裂缝的两种形式，当密封设备行走至两条裂缝的交点处时，需明确该如何选择设备的前进方向[9]。

上述各类路径规划并没有着重分析这一问题，但Ravani等[8]于2000年研究使用链表这一数据结构及方向向量进行路径规划时，提出可选择夹角较小的方向前进；2017年，杨延[9]在研究基于机器视觉的路面补缝轨迹控制时，明确提出在面对交叉点时，可选择夹角较小的方向继续进行修补，这样的算法实际上是直接控制了密封设备继续沿着当前的裂缝轨迹行走而不会在交叉点处转至下一条裂缝。杨延通过模拟试验证明了这种方法的可行性。

图4 两种形式的交叉裂缝

3.5 各方法评述

贪婪算法是路径规划问题中最早采用的规划方法，由贪婪算法的核心思想可以看出：该算法的优势在于思路清晰、计算方法简单、求解过程十分迅速，但也明显存在很大弱点，即由于所求解很难保证是最优解，因此计算得到的冗余距离较长，这会在一定程度上降低修补时的工作效率。此外，贪婪算法的突出优势仅在工作区域内裂缝数量较多时才可得到明显体现，当工作区域内仅存在1～2条裂缝时，贪婪算法所节约的计算时间与修补时在冗余距离上行走所耗费的时间相比就显得不值一提，而在这种情况下，列出所有的可行解找出最优路径，反而是更好的解决思路。

最优路径算法的过程实质上就是列出所有可行解的过程，树形结构使得排列思路更为清晰明了，使之可通过编程进行实现，在建立树形结构后，比较所有可行路径的大小，即可明确地得到最优路径。但是，树形结构并不能减少排列过程所需要的时间，当裂缝数量增加时，计算时间同样会急剧增加，因此，这种方法仅仅适用于工作区域内裂缝数量较少的情况，并不具备普适性，若要确定使用此方法，也需在计算之前首先做出判断，并在裂缝数量较少时选择此方法，在裂缝数量多时选择其他算法，例如利用上文中提出的两阶段树算法、单阶段树算法及贪婪算法，或将3种算法整合，选择使用，计算效果会更好。

模拟退火算法则是当下解决TSP等相关问题时更为常用的算法，由于其可依概率跳出局部最优解，因此在使用此算法时，既可以在一定程度上弥补贪婪算法总是选择局部最优解导致的不足，又可以获得较快的计算速度，弥补最短路径算法的不足。此外，若选择这类智能优化算法，则不需要在规划前根据裂缝数量做出选择，算法的适用度较高。但就该算法本身而言，在具体实现过程中需要人为设置计算时所用到的参数，若参数选取不当，计算结果也会不尽如人意。但是，该算法仍然具有不可替代的优势。

4 路径规划算法研究展望

由上文分析可知：裂缝修补的路径规划可转化为TSP问题，那么，路径规划问题的求解过程也可以沿用TSP问题的求解算法。当前，TSP问题的主流求解算法为智能优化算法及相关改进算法。王剑文等[10]曾在2008年总结了各类智能优化算法，其中除模拟退火算法外，还有遗传算法、蚁群算法、人工神经网络算法等算法，这类智能算法各自具备不同的优势，均可经过改进，使其适宜用于求解路径规划问题。此外，还可利用各类智能优化算法的特点，将两种或两种以上的算法结合成混合优化算法，这种改进方法也在TSP问题的求解中得到了广泛的应用。因此，未来可考虑借鉴其他经典的智能优化算法及上文中的算法，设计出一种更为高效和准确的路径规划算法。

5 结语

路面裂缝的自动化修补装备可完成路面裂缝的检测及修补工作，路径规划模块是其中的核心模块之一，当前的研究已经明确了路径规划问题的实质，3种规划算法——贪婪算法、最优路径算法及模拟退火算法均主要借鉴了求解TSP问题的相关思路，提出的算法可满足实际要求，所有算法均可为密封设备规划出一条行走路径，各算法均具有不同的优势。但与图像处理模块相比，路径规划模块的相关研究较少，针对交叉点问题的分析仍不够明确，且创新性有待提高。未来可考虑将这些研究成果与当前TSP问题的热点研究成果进行结合，在图像处理最新技术的支撑下，研发出一种更为高效、更为一体化的自动化路面裂缝修补设备。