1. 引言
近些年来，中国经济迅速发展，而交通与经济的发展相辅相成。在我国，桥梁的建设是发展交通的重要环节。所以近年来，我国桥梁建设得到了很大发展，港珠澳大桥、北盘江大桥、金沙江大桥、丽江大桥等超高难度大桥的建成，无不彰显着我国的综合实力 [1]。随着桥梁数量的增多，桥梁的日常维护以及检修工作也越发繁重。目前桥梁检测工作主要是通过人工目测加上采用一些仪器设备进行现场测试、荷载试验及其他辅助性试验来进行的 [2]。仪器设备主要是借助桥测车，然而桥检车存在价格昂贵、体积大以及定制困难等缺点。在实际工程中就需要灵活性高，安全可靠的且成本较低的检测设备携带检测视频设备到达工作人员不方便到达的地方，然后将检测素材传回到检测系统，以方便得出相应的检测报告。
随着无人飞行器的普及率越来越高，其应用领域也是越来越广。无人飞行器(UAV)以其轻巧、灵活的特点搭载高清摄像头等设备可以完成多个工程任务。将无人机技术应用在桥梁病害检测系统中，已成为未来桥梁病害检测的一种重要手段 [3]。同时无人机存在目视操作困难，电池容量小，极易受风影响等缺点，因此如何提高无人机检测效率，保障飞行安全是桥梁检测无人飞行器系统面临现的实问题，其关键技术之一是对无人机的飞行轨迹进行合理规划 [4]。
在无人机桥梁病害检测系统中，航线规划系统在其中占有重要地位，是指导其硬件系统正常工作的关键因素。在桥梁检测应用平台，航线规划系统功能是规划出满足桥梁检测任务要求的航线。以下是该应用平台系统组成示意图，该系统由不同模块组成：导航模块、控制模块、信息采集模块、桥梁检测分析模块等。无人机技术属于信息采集模块：利用无人机携带云台采集桥梁信息，作为桥梁检测分析模块的信息来源。所以在如下图1所示的无人机桥梁病害检测系统中，无人机的航线规划十分重要。
本文通过对桥梁病害检测无人机中常用航线规划算法进行分类归纳，并介绍分析了航线规划中各算法的应用方法，突出了不同算法的优缺点，然后介绍了无人机航线规划软件，最后对未来无人机航线规划发展进行展望总结。
2. 无人机航线规划算法
无人机航线规划是指依据无人机任务分配，规划出符合安全条件的飞行航线(Route Planning)。但是各种规划算法都存在优缺点，在具体使用过程中，要结合使用场景及要求选用算法。航线规划的算法很多，按使用方法可分为三类 [5]：常规航线规划、基于类比的航线规划和轨迹优化。
2.1. 常规航线规划
在基于图形的路径规划方法中，首先根据一定的规则将自由的C空间(Configuration Space)表示成一个由一维线段构成的网络图，然后采用某一搜索算法在该网络图上进行航迹搜索。这样，路径规划问题被转化为一个网络图搜索问题。主要的方法有Voronoi图法和PRM法 [6]。
除了上面的方法还有基于栅格的规划方法：基于栅格的规划方法首先将自由的C空间分解成为一些简单的单元，然后找到包含起始点和目标点的单元，最后寻找一系列连通的单元将起始单元和目标单元连接起来即可。主要的方法有动态规划法、A*算法等 [7]。
A*算法是一种经典的最优启发搜索算法，Rouse [8] 将整个区域划分成若干正方形栅格，以栅格的中心点作为路径点，通过启发式的A*算法实现最优航线规划。Szczerba [9] 等人采用一种称为稀疏A*搜索(SAS)的技术来进行航迹规划，该算法结合路径约束有效地削减搜索空间到能够实时收敛并得到满足要求的解，但它只是在二维平面进行航迹搜索。张瑞鑫 [10] 等人在SAS的基础上，提出了一种模型约束三维航迹规划的方法，该方法将物理约束与威胁环境融合后建立数学模型，通过将传统A*算法的代价函数优化，提高规划效率。A*算法由于提供了智能搜索，因此大幅度提高了搜索效率，但算法最终接近最优的程度取决于启发函数的表达式，当搜索空间很大时，计算量也会很大。
2.2. 基于类比的航线规划
基于类比的航线规划是借助于物理或生物学上的概念，将航线规划问题转化后进行求解 ，有人工势场法、遗传算法、神经网络法、RRT算法和蚁群算法等 [11]。
人工势场法的主要思想是利用物理中关于磁场吸引和排斥的有关法则，它将目标作为吸引场，威胁和障碍作为排斥场，飞行器在两者综合生成的势场中飞行。Bortoff给出了一个利用人工势场法计算无人机通过雷达威胁区的航迹规划实例 [12]。文中用处于势场中的弹簧链的状态来表示航迹，定义弹簧链的势能为弹簧长度及与雷达距离的加权和，经初始化后，在势场的作用下，弹簧链最终达到它的势能最低状态，此即最优航迹。该方法的一个显著优点就是规划速度快，但它可能找不到路径，从而导致规划失败，其原因是在吸引力和排斥力相等的地方存在局部最小点。
遗传算法提供了一种求解复杂问题的通用框架，它仿效生物的遗传和进化，根据“生存竞争、优胜劣汰”的原则，借助复制、杂交、变异等操作，使所要解决的问题从初始解，逐步逼近最优解 [13]。现在研究中很多研究者都将遗传算法用于飞行器的航迹规划求解 [14] [15] [16]。遗传算法利用简单的编码技术和繁殖机制来表现复杂的现象，从而解决了非常困难的问题。但是接近最优解后，收敛速度可能会变得很慢，可以考虑在收敛到次优解后采取其它的搜索技术。
遗传算法也被叫作进化算法。它是通过自然选择原理进行选择操作，将合适的个体保留下来，进而形成新一代。新一代通过逐步进化到最优解，具体进化过程如下图2。
Figure 2. Genetic algorithm process diagram
图2. 遗传算法过程图
使用遗传算法对问题求解时，为了方便数字串表示问题的解和遗传算子直接操作串，第一必须要明确问题的目标函数以及变量，其次编码变量。编码方式可分成实数编码以及二进制编码，如果个体用二进制表示，那么二进制转为十进制公式为：
(1)
上式中
是某个单体的第i段，单体中每段长均是1，每个
的值均为0或1，第i段分量
定义域的首未端点为
和
。
该算法所具有的鲁棒性可以应用于对复杂系统的优化。但是在编码过程中遗传算法易出现准确性、规范性问题，算法效率低，易出现过早收敛，这些短板都限制了其在无人机上的适用性。
神经网络法是在生物功能启示下建立起来的一种计算方法，通过设置不同神经元的值表征地图状况，进而将环境地图映射成神经元网络，最后训练神经网络以获得最优神经元集合，形成待飞航线 [17]。近年来有很多研究学者把神经网络用在无人机航迹规划上面 [18] [19]。将这些文献都把神经网络在无人机航线规划上的应用向智能化方向。文献 [20] 中提出了一种基于在线强化学习的行为动力学和滚动窗口方法进行路径规划。它应用Q学习来优化行为动力学模型参数可提高性能，行为动力学可指导Q学习的学习过程并提高学习效率，优化了学习过程。与优化前相比，优化后的算法不论在规划速度还是规划质量上都有较大的提升。
RRT (快速扩展随机树)算法是由S. M. Lavalle于1998年提出的，它是一种可在多维空间高效进行航线规划的算法 [21]。该算法主要由两部分构成：随机树的生长和路径的搜索。
假设在一个位姿空间C中，初始位置为Qint，目标位置是Qgoal，在生长阶段，以Qint作为树的根，在空间C中任意产生一个随机点Qrand，在随机节点Qrand周围找到任意一个与之距离最近的叶节点Qnear，连接Qnear与Qrand，从Qnear点出发在与Qrand的线段上选择一个步长S，取该点为Qnew，检查Qnew是否在障碍物区域内，Qnear与Qnew的连线是否穿过障碍物，如果有，则重新选择Qrand，重复上述过程；若没有则将Qnew加入到随机树中成为新的叶节点，随机树不断生长，直到新叶节点到达Qgoal或者离Qgoal距离在一个设定的范围内，这样随机树的生长结束。在路径搜索中，从目标位置Qgoal开始，逆向搜索父节点，以搜索到初始位置Qint结束，通过这种方式得到一条在起止点间无碰撞路径，即含有目标节点的随机树。随机树的生长过程如下图3所示。
Figure 3. Schematic diagram of random tree growth
图3. 随机树生长示意图
快速扩展随机树(Rapidly-Exploring Random Tree, RRT)作为一种新颖的随机节点采样算法，相对传统路径规划算法，具有建模时间短、搜索能力强、方便添加非完整约束等优点，自提出以来就得到了极大的关注 [22]。目前RRT在路径规划领域取得较大的进展，但算法仍存在节点利用率低、路径不稳定等不足 [23]。也有人提出双边随机树(Bidirectional RRT, bi-RRT)算法，算法从起点与目标点分别生成一颗随机树进行搜索，直到两颗随机树互相连接 [24]。
蚁群算法是模仿蚂蚁活动的新的仿生类算法 [25]，作为一种随机优化方法，它吸收了蚂蚁的行为特性，通过其内在的搜索机制，在一系列的困难组合优化问题求解中取得了成效。同样，蚁群算法也不受搜索空间限制性假设的约束，不必要求诸如连续性、导数存在和单峰等假设，但其收敛速度不是太快。
2.3. 轨迹优化
Asseo采用变分法结合最速下降法求解TF/TA2问题。先考虑飞行器的横向约束条件，计算生成水平面的二维路径，然后用抛物线拟合法计算水平面路径的垂直面路径 [26]。
动态规划法的模型简单，对地形要求不高，算法不依赖于威胁场的连续性，容易实现，适用小范围轨迹优化。Waller [27] 采用将飞行高度与速率作为状态变量、时间进行分段、推力与航向作为控制量的动态规划方法，进行了地形跟踪垂直平面内的二维仿真。
动态规划算法作为五大常用算法之一，其基础思想和分治法类似：就是把需要求解的问题分成多个小问题，然后依次求解小问题，解决前一小问题可以帮助求解后一小问题。针对小问题求解，利用决策从多种局部解中筛选出最优解，淘汰无用解。通过顺序解决每个小问题，最后一个小问题的解即是原始问题解 [28]。动态规划有一定的适用范围，一般应具备这3种特质：
1) 最优化原理：问题及其所包含的子问题的解都是最有的即是最优子结构。
2) 无后效性：状态以后的过程影响不到以前的状态，只受当前状态影响。
3) 重叠子问题：小问题是不独立的，决策的下一阶段可能会多次使用到一个小问题。
利用动态规划处理多阶段决策问题，如图4所示：
动态规划是最优化式的分阶段决策过程的一种数学方法。使用该方法进行航线规划时，构造的航线图必须为各级的连接，并最后归结于目标点。特定的评价函数给出每一级的航线代价，然后遵循分阶段决策规则寻求最优航线。在单一威胁情况下，无人机高空执行任务时，使用该方法可取得良好效果。但是这种算法所需空间较大，区域变大，威胁不再单一时，算法反应时间较慢。
例如以速度方向与地形的切平面坐标轴间的夹角作为控制量，飞机的位置坐标作为状态变量，将轨迹优化问题转化为一起点固定、终端自由、时间自由的最优控制问题进行求解 [29]。
3. 无人机航线规划与模拟软件
小型无人机在军事和民用领域方面得到了日益广泛的应用。在航线规划中合适的算法和模拟环境对无人机在桥梁病害检测中有十分重要的作用。
文献 [30] 以遗传模拟退火算法为依据，设计了一款基于GIS的无人机航迹规划软件，主要包含数据通信、地图处理显示和航迹规划3个模块。在航迹规划模块中，有航路点规划、航路信息生成与校验和历史航迹显示3种模式。可以在编辑状态下，设置航路点和航线，实现航迹规划的功能，方便航线生成与管理，使得航迹规划更具科学性和可靠性。该软件操作简单方便，给用户带来了方便快捷的导航和规划服务，为无人机任务规划提供了强有力的保障能力。
文献 [31] 中对无人机地面站监控软件的设计和实现方法进行了探索，最终设计并完成了一款除具备数据通信、飞行数据仪表显示、飞行航线规划、飞行数据的本地文件存储等常见功能外，还具备飞机姿态实时三维显示、飞行数据的数据库存储以及由数据库驱动的数据曲线分析功能的小型无人机地面站监控软件。
在数据通信上有多种通信模式。数据通信技术是随着计算机技术的普及和计算机远程信息处理应用而产生的一种新型的通信技术，它是通信技术和计算机技术相融合而产生的新的通信方式 [32]。
航迹规划模拟中地图的显示十分重要，而二维地图显示从PC平台到PDA的发展是地理信息系统多元化、跨平台的一次飞跃。文 [33] 中通过对嵌入式系统的研究，在WindowsCE平台下开发2维地图显示应用系统，克服了PDA内存小、处理速度慢等硬件限制，实现了2维地图在PDA客户端的快速显示，并对一些关键技术进行了深入研究。在用户用相机获取图片时，用户就有了可用一些免费的软件帮助地图和显示数据。Wessel P [34] 讲到GMT使用PostScript页面描述语言，通过叠加多个绘图文件，可以生成任意复杂的灰度或24位真实颜色的图像。行图、位图图像和文本可以很容易地组合在一个插图中。PostScript绘图文件与设备无关，这意味着相同的文件可以每英寸300个点(Dpi)的速度打印在普通的LaserWriter上，或者在需要最终质量的情况下以2470 dpi的速度打印在照排机上。GMT软件是作为一组UNIX工具编写的，并且是完全独立的和完整的文档。最后用户基于显示的地图来进行航线规划。
4. 未来研究展望
在无人机桥梁检测系统中，虽然已有航线规划算法种类繁多，但是大多只能应用在理想化的环境中。在实际应用中，无人机飞行时更加注重算法的收敛速度以及航线的平滑性等问题。针对目前已有算法，可以通过优化规划策略可以提高算法的收敛速度，增加其实用性；对航线点进行优化，使整个航迹具有较好的平滑性，大大提高无人机飞行过程的稳定性，保障了无人机的安全，同时提高了续航能力。
现有航线规划算法依据其原理，各有优缺点：常规算法有效性强但实用性较差；智能型规划算法具有较好的收敛速度但易陷入局部最优化。在实际工程应用中没有一种算法可以单独适用于所有实际环境，因此可以借鉴各算法优势进行融合。依据实际工程应用的不同需求，融合不同算法的优势，以达到航线规划的最优化。未来，针对无人机桥梁病害检测系统工程应用，算法融合将大大提高无人机的航线规划效率，同时也会更好地引领无人机技术在其它工程中的应用。
5. 总结
随着技术的发展，无人机正在以不同的方式与各行业结合，无人机的应用场景更加丰富，航线规划是无人机发展技术基础。在实际工程应用中，算法选择与设计应结合具体应用场景，以解决实际问题及无人机安全为导向，紧密联系行业场景，为无人机的发展与应用提供有力技术支撑。
基金项目
高校科研项目：基于桥梁病害检测无人机的航线规划研究(ky202107)。