摘 要：针对复杂作业环境下的工程机械路径规划问题，提出了一种基于快速扩展随机树的路径规划方法。首先分别对路径规划的目的、约束条件、任务环境建模、路径表述方法以及针对机械本体大小的障碍物膨化方法进行了分析论述，进而介绍了RRT算法的基本原理，并给出了基于RRT的路径规划算法步骤，最后通过仿真试验验证了所提方法的有效性和先进性。
关键词：工程机械；路径规划；快速扩展随机树
DOI：10.16640/j.cnki.37-1222/t.2017.21.248
0 前言
以推土机、挖掘机为代表的工程机械，通常在地面崎岖、障碍物众多的复杂环境进行土石方作业。传统的人工驾驶方式是通过车载驾驶人员进行机械设备的现场操作，但是一些特殊领域，工作环境可能存在地面塌陷、山体垮塌等危险情况，会给驾驶人员的生命安全带来威胁。智能化、精准化、无人化代表了工程机械行业未来的发展方向[1]。通过无人化设计，实现操作人员对设备的远程遥控或者机械设备的任务级自主控制，能够极大的提高工程施工的安全性、拓宽工程机械的应用场合。
路径规划是综合考虑移动主体的运动学、动力学约束，以及任务环境的地形地貌、障碍分布等情况，为移动主体规划出从起始位置到目标位置的可行路径或最优路径。路径规划是实现工程机械无人化作业的关键技术之一。常见的路径规划方法包括基于数学规划的方法，基于群体智能的规划方法、基于启发式计算的方法等[1，2]。其中混合整数线性规划为典型的数学规划方法，具有严格的数学理论依据，但随着规划问题的增大，其计算量会急剧增加，因此只适合于小规模的路径规划问题。以蚁群算法、遗传算法、粒子群算法为代表的群体智能优化方法具有内在的并行机制，全局优化能力强，但存在优化时间长，有时可能会规划失败等不足。人工势场方法也是一种常见的路径规划方法，能够在势场引力和势场斥力的综合作用下，将路径向着目标位置延伸，但也存在着存在引力和斥力相同的局部极小点问题，会导致规划失败。
快速扩展随机树算法 （Rapidly-exploring Random Tree，RRT）是一种基于空间采样的路径规划方法，由美国学者LaValle于上个世纪末提出[3]。RRT在任务空间内采用节点生长的方式构造随机树，逐步构建出连通起始位置与目标位置的可行路径。该算法具有参数少、结构简单、收敛速度快等优点，自算法提出后，逐渐得到的学术界的认可，已有的研究表明，RRT算法具有比A*算法、隨机路线图算法等原有的路径规划算法更高的优化效率[4]。
本文采用RRT算法求解复杂工作环境下的工程机械路径规划问题，包括路径规划问题描述与数学建模、算法设计、仿真试验等内容。
1 问题描述
自动地规划出工程机械的行驶路径，是未来的智能化和无人化工程机械实现自主行进与施工作业的重要前提。该路径规划问题可以描述为：
（1）根据工作环境和任务要求，为工程机械生成从起始位置到目标位置的可行路径。
（2）所得路径应能够避开已知的障碍物体或危险区域，保证设备的行进安全。
（3）所得路径应满足机械设备的运动学和动力学约束，比如路径长度应小于工程机械的最大行程，转弯半径应符合工程机械的机动性能。
机械的行进路径由任务区域中一系列的路径节点组成，路径节点的顺序对应着工程机械的依次需要到达的行进位置。用直线段连接相邻的路径节点。假设工程机械的起始位置为，目标位置为，第个路径节点表示为，其中分别为该路径节点位置的纵横向坐标，则从起始位置历经个路径节点到达目标位置的路径可以表示为：
基于上述分析，可以采用二值化的任务环境建模方法。将障碍物、危险区域、机动性能受限区域等简化为具有同等威胁程度的不可行区域，即整个工作环境区分为威胁区域（不可行区域）和可行区域两种情况。威胁区域完全不可行，规划所得路径不能与威胁区域有重合。
另外由于工程机械具有自身的形状和较大的外形尺寸，在实际的行驶时，需要避免车体与周围物体的碰撞，不能简单的将车体看作为没有尺寸大小的质点。在路径规划过程中，可以采用障碍物膨胀的方法，将车体的外形尺寸进行等效处理，即根据工程机械的车体大小，将障碍物或危险区域进行等值的膨胀放大处理。经膨胀处理之后，不但解决了车体的碰撞问题，而且对于常见的推土机、挖掘机等低速运动的工程机械而言，其转弯半径、爬坡率等运动学约束也不用在规划过程中单独处理。
2 算法设计
RRT算法是一种以空间采样的方式实现路径搜索的规划算法。假设任务区域为，表示其中的可行区域，表示威胁区域，和同为的子集，并且满足和。路径规划的起始位置和目标位置，起始位置和目标位置位于同一连通区之内，路径规划的目的是得到从到的可行路径。
RRT算法首先通过节点扩展的方式在构建随机树，在构建过程中，以为根节点，依照概率选择目标位置或者空间中的随意一个位置作为随机目标点，并从原有的随机树上延伸一个步长，拓展出一个新节点，当随机树延伸到与足够近的时候，通过反向搜索，可获得从到的路径。RRT算法的步骤如下：
（1）算法初始化；
（2）未到达目标位置则转向步骤（3）；否则转向步骤（7）；
（3）生成随机数，若，则转向步骤（4），否则转向步骤（5）；
（4）以作为，确定临近节点，进而得到，转向步骤（6）；
（5）在任务区域内随机生成，计算对应的；
（6）判断与之间是否存在威胁，若无威胁则将添加到随机树之中，实现随机树的扩展，并转向步骤2），若存在威胁则转向步骤3）；
（7）从开始反向搜索父节点，直至找到起始节点，完成路径规划。
3 仿真试验
采用RRT算法进行复杂任务环境中的路径规划仿真试验，仿真软件平台为MATLAB2009。假设任务环境为的无量纲二维区域，任务环境内共有100个不可行的威胁区域。每个威胁区域的位置和覆盖半径都随机产生。路径规划的起始位置坐标为（0，0），目标位置坐标为（100，100），设置RRT算法的参数为和。endprint
图1为通过RRT算法得到路径结果。由图可知，所得路径避开了所有的已知威胁区域，生成了从起始位置到目標位置的可行。在随机树在生长过程中产生了很多分支，这是由于对于复杂的任务环境，RRT算法必须通过不断的在整个任务区域内容进行拓展搜索，以图找到潜在的路径。算法具有良好的时效性，仿真运行时间0.38秒，能够满足实际的工程机械路径规划的快速性要求。RRT算法在规划过程中总共扩展出258个节点，其中所得路径的长度175.3，这说明算法具有较好的方向性，没有产生过多的迂回曲折。
4 结束语
以推土机、挖掘机、铲车为代表的工程机械在工程施工领域有着不可替代的重要作用，随着科技的发展，智能化、无人化代表了工程机械的发展方向。针对复杂作业环境下的工程机械路径规划问题，本文提出了一种基于快速扩展随机树的路径规划方法。首先对工程机械路径规划问题的目的、约束条件、任务环境建模、路径表述以及障碍物膨化处理方法进行了分析论述，进而给出了基于RRT算法的路径规划方法，通过仿真试验对所提方法的有效性和先进性进行了验证。结果表明RRT算法是一种高效的路径规划方法，在工程机械路径规划领域有广泛的应用前景。
参考文献：
[1]朱大奇，颜明重.移动机器人路径规划技术综述[J].控制与决策，2010，25（07）：961-967.
[2]孙梅.移动机器人路径规划技术综述[J].山东工业技术，2016（21）：164.
[3]LaValle S M，Kuffner J J.Donald B R，et al.Rapidly-exploring random trees：Progress and prospects[J].Algorithmic and Computational Robotics：New Directions，Wellesley，2001： 293-308.
[4]David B.Comparison of A*and RRT-connect motion planning techniques for self-reconfiguration planning[C]. International Conference on Intelligent Robots and Systems， Beijing，2006：892-897.
本论文来源于山东省重大科技创新工程项目，项目名称《基于工业物联网的工程机械智能装配数据采集与处理关键技术研究与应用》，项目编号：2017CXGC0603
作者简介：田从丰（1985-），男，山东微山人，工学硕士，工程师，研究方向：工程机械自动控制。endprint
