基于rrtconnect算法的双履带起重机路径规划研究_硕士学位论文(编辑修改稿)

基于rrtconnect算法的双履带起重机路径规划研究_硕士学位论文(编辑修改稿)内容摘要：

提出一种二阶段搜索的单台起重机路径规划方法 [2]，第一阶段 结合爬山策略采用深度优先图遍历的方法在无碰撞空间中找到一条可行路径，然后在第二阶段对此可行路径采用启发式函数进行优化。 该方法特点是在搜索之前需要将起重机的位形空间以一定的步长离散成点，并用碰撞检测函数构造无碰撞的搜索图。 因构造图需要大量的计算，因而该算法效率较低。 为了检验基于随机采样规划方法在起重机路径规划中的性能，王欣等人采用双向 RRT（ Bidirectional RRT） 规划不考虑行走的单台履带起重机的吊装路径 [3]，该方法考虑了起重机吊钩旋转自由度，案例表明，该方法求解效率很高且路径近似最优。 针对动态的作业环境， Cheng Zhang 提出一种实时的在线单台起重机吊装路径规划方法 [4, 5]，在执行离线规划出来的路径过程中，算法采用 UWB RTLS系统（ ultra wideband RealTime Location Systems）收集当前作业环境数据、更新环境模型，然后若有必要则采 用 DRRT规划算法（ RRT 的变种）重新规划路径，若规划成功则沿着更新后的路径继续工作，直至吊装任务完成。 该方法结合环境感知技术（传感器、定位系统等）实现吊装过程的监控和起重机吊装路径的实时规划，在一定程度上提高了吊装的安全性。 大连理工大学硕士学位论文 3 上海海事大学 黄有方 课题组对集装箱吊装的路径规划做了一定的研究，建立了以最短路径为目标函数、无碰撞为约束条件的集装箱装卸操作最优路径的单目标数学模型 [6, 7]。 丰桥技术科学大 学 的 Terashima, Kazuhiko、 杜兰大学 的 Lee, HoHoon、 okuyamna College of Teclmology 的 Akamatsu, 重机的吊装进行路径规划进行了大量的研究，主要研究单台起重机在高速吊装过程中如何规划其动作并进行控制，以实现安全、高效的吊装 [811]。 另外， Sun Ning 等 台湾国立大学土木系的康仕仲课题组提出的基于增量解耦多塔机协同路径规划 [12, 13]。 双机吊装路径规划研究现状 随着两台 起重机协同吊装日趋普遍， Sivakumar, P. A*算法、爬山算法进行双机协同吊装路径规划 [14]，实验表明爬山算法比 A*算法能快速找到可行路径但路径不优，而 A*算法能找到较优的路径但耗时长。 因 A*算法、爬山算法这类基于几何构造规划方法均需要构造庞大的无碰撞搜索图，其计算复杂度随着起重机的自由度及空间离散分辨率呈指数增长，难以胜任带高自由度的起重机吊装路径规划。 为此， . Ajmal Deen Ali 和 Sivakumar, P. 协同吊装提出一种基于遗传算法（ GA）的路径规划方法 [1519]，该方法采用固定长度的串表示吊装路径，根据位形间的偏移量构造适应度函数，应用遗传算法的选择、交叉、变异等操作不断演化路径种群，最终求得较优吊装路径，从文献中的实验可以看到，相比 A*算法，遗传算法的计算效率提高了 10~20 倍，所得路径长度相当。 该方法虽然避免空间的几何 构造而提高了计算性能，但其也存在一些不足，比如路径必须由数量固定的位形构成（等长的个体）、收敛速度及路径的质量难以控制等。 为了克服路径必须由数量固定位形构成的不足，王欣、张玉院等人采用蚁群算法进行单台起重机和两台起重机路径规划 [20, 21]，该方法将位形间距离、碰撞、起重机动作优先级及切换等因素融入路径点选择策略和信息素更新中，该方法能找到近似最优的路径且无需要求路径由确定数量的位形构成。 但蚁群算 法中信息素因子  、启发式因子  及信息残留系数  较难选择，且计算时间长。 为了进一步提高吊装路径规划的计算效率， YuCheng Chang 于 2020 年提出一种基于概率路标法（ PRM， Probabilistic roadmaps Method）规划单台起重机和两台起重机协同吊装的路径 [22]，该方法先将起重机的回转、变幅自由度作为位形的变量（此时暂未考虑起升自由度），在此位形空间中采用 PRM 规划出一条无碰撞的吊装路径，然后在此路径的基础上进行起重机起升动作的规划，从而最终得到一条可行的无碰撞吊装路径。 实验显示这种将自由度分解降维进行分步规划的方法可以提高规划的效率，相比遗传算法效率提高了数十倍，对于一些基于 RRTConnect 算法的双机路径规划研究 4 相对较为简单的吊装环境，该方法几乎达到实时。 针对吊装路径的平滑性问题，文献 [23]采用四次样条光滑遗传算法得到的两台起重机协同吊装路径。 双机协同吊装系统可视为两个移动式机器人协同作业。 因此本文研究的问题与 多机器人协作物体操作 （ Multirobot Cooperative Object Operation） 问题 有一定相似性。 然而双机 路径规划 为多种困难问题的结合体 ： a. 高维自由度问题； b. 协同问题 （ 其中的 闭环约束问题需要进一步的研究和解决 ） ； c. 行走非 完整 约束问题。 移动式起重机是一种用于吊装的刚柔耦合的机构，可被看成是一种特殊机器人。 它与传统的移动式机械臂相比，从起 重机机构和作业特点上来看，具有刚柔混合、机构尺寸可变、起升能力敏感等特征。 路径规划方法综述 （ 1） 路径规划方法分类 作为机器人研究领域的一个基本问题，路径规划经历近二、三十年的发展，已出现许多规划算法，主要分为三类： a. 基于自由空间几何构造的规划方法及前向图搜索算法； b. 智能规划方法； c. 基于随机采样的规划方法。 基于自由空间几何构造的规划方法及前向图搜索算法主要有可视图 [24, 25]、栅格分解 [2628]、 Voronoi 图 [28, 29]、 Dijkstra 算法 [30, 31]、 A*算法 [30]以及人工势场法[32, 33]等等，这些方法对于很多规划问题都具备了很强的适应性，但当面对高自由度机器人路径规划问题时，其计算复杂度将随自由度呈指数增长，而且对对微分约束和复杂环境也缺乏较好的解决办法。 智能规划方法主要包括遗传算法 [3438]、蚁群算法 [39, 40]和人工神经网络方法[4144]等等，这些方法可以得到最优或者近似最优路径，但是收敛速度和有效性难以保证，并且需要设置的经验参数太多，不利于自动处理。 基于随机采样的规划方法是路径规划的新手段。 基于随机采样的方法是在随机采样理论的基础上发展而来的一类路径规划新方 法，其仅仅通过对位形空间或状态空间中的采样点进行碰撞检测来获取障碍物信息 , 避免了对空间的建模，且在高维空间中的搜索效率很高，因而这类方法更适合于求解高自由度机器人在复杂环境中的规划问题，而且对带有微分约束的规划问题也具有较强的解决能力。 概率路标法（ PRM， Probabilistic Roadmaps Method） [4551]和快速随机生成树方法（ RRT， RapidlyExploring Random Trees） [3, 29, 5257]是目前最成功的两种基于采样的路径规划方法。 PRM 方法是通过在整个空间内采样得到若干个采样点，并由这些采样点构成一张概率地图，最后在地图中搜索得到合适的路径，其在高维静态空间中具有良好的表现。 RRT 算法遵循控制理论的系统状态方程大连理工大学硕士学位论文 5 ）（ uxfx ,39。  ， 在控制量的作用下增量式地产生新状态直至到达目标 , 这使它很容易满足系统运动动力 学约束方面的要求，且适用于动态环境。 基于随机采样的规划方法因其优良的特性已被广泛应用于机器人学、计算机动画、工业设计、生物计算等各领域的路径规划问题中，并已成为当前路径规划研究的热点。 本文双机路径规划为 高自由度 问题，并且是典型的非 完整 约束问题，因此采用基于 RRTConnect 算法的方法作为解决手段。 等人于 1998 年提出了一种基于采样的路径规划方法 —— 快速 随机 搜索 树 算 法 （ Rapidlyexploring Random Tree， RRT） ，由于此方法 在高维空间中 具有 突出表现，以及在规划 过程中可以引入运动学约束，因此目前 RRT 被广泛应用 于 许多路径规划问题中。 （ 2） 基本 RRT 算法 设 C 为路径规划问题的状态空间， Cfree（ Cfree C） 为 与障碍物无碰撞的机器人自由空间， Cobst （ Cobst  C） 为与障碍物发生 碰撞的机器人碰撞空间， T表示 含有 k 个节点的随机树，且 T Cfree， Xinit（ Xinit ∈ T） 为 树的 初始 点即 初始 姿态， Xgoal（ Xgoal ∈ T） 为树的 目标 点即 目标 姿态。 基本 RRT 算法流程 ： ① BULD_RRT(Xinit) (Xinit)。 While (Xgoal not in T ) { Xrand, Xnear} SELECT_NODE( T )。 EXTEND ( T, Xrand, Xnear)。 Return T。 ② SELECT_NODE(T) Xrand  RANDOM_STATE()。 Xnear  NEAREST_NEIGHBOR(X,T)。 return { Xrand, Xnear }。 ③ EXTEND(T, Xrand, Xnear) If (NEW_STATE (Xrand, Xnear, Xnew, u) )then (Xnew)。 (Xnear, Xnew, u)。 Return。 基于 RRTConnect 算法的双机路径规划研究 6 根据基本 RRT 算法流程及 图 的可知，基本 RRT 的算法为首先以 初始点Xinit 作为树 T 的根节点；在 Cfree 中用函数 RANDOM_STATE( )随机选择一个随机点 Xrand，即使得 Xrand Cfree；再用 函数 NEAREST_NEIGHBOR( )搜索树上离Xrand 最近的节点用来扩展，这个节点被称为 Xnear；用函数 EXTEND( )来扩展树，即随机或是根据给定的标准，选择一个输入 u，使得 Xnear 向 Xrand 靠近，这时产生一个新节点 Xnew，如果检测没有碰撞或满足要求，将 Xnew 加到树中。 如此重复 直到子节点集中包含 目标 姿态点 Xgoal 或 子节点集中有节点在 目标 区域内时终止算法执行，此时即找了一条以随机树 T 中节点组成 的 从 初始 姿态 Xinit 到 目标姿态 Xgoal的 路径。 X i n i t X n e a r X n e w X r a n d X g o a l u 图 随机树扩展示意图 Fig. Diagram of RRT expanding （ 3） 改进 RRT 算法 基本 RRT 主要缺陷在于其为了找到目标点需要在整个空间内进行搜索，效率很低。 为提高搜索的效率，与路径的质量，很多学者对基本 RRT 进行了改进，形成了一些改进版本的 RRT 算法，这些改进的 RRT 算法通常可分为以下三大类。 ① 改进分支扩展方式的 RRT 改进分支扩展方式的 RRT 包括 RRTGoalBias[58, 59]、 RRTConnect[60, 61]等。 RRTGoalBias： 此种改进 RRT 方法在扩展过程中不是完全以随机点作为牵引点而是以一定概率用目标点作为的牵引点。 RRTGoalBias 方法可使树快速向目标点增长，但是当过多偏向目标点时可能会使树的生长陷入局部最优。 RRTConnect： RRTConnect 的基本思想是使单步扩展的距离尽可能远，如下图所 示该算法将基本 RRT 的单步扩展改进为具有贪婪性质的多步扩展，直到碰到障碍或到达目标点才结束一次扩展迭代。 应用此多步扩展的方式可以有效避免陷入局部最优的可能，并且在相对开阔的区域 RRTConnect 可以快速向未探索的区域扩展从而可以大大提高生成树的效率。 大连理工大学硕士学位论文 7 ② 增加随机树的 数量 双棵树 RRT： 双棵树 RRT 方法包括 RRTExtExt、 RRTExtCon、 RRTConCon等，这些方法都是分别以起点和目标点作为树根，分别以单步或多步扩展的方式生长两棵树，直到两棵树相遇，此时即找到了从起点到终点的路径。 此方法由于采用 两棵树同时生长，大大提高了搜索的效率，尤其是双向都是多步生长的RRTConCon 方法具有很好的搜索特性，广泛应用于各路径规划问题中。 MultiRRT： MultiRRT 采用多棵树同时生长的方式进行路径规划，此方法除了应用 初始 点和 目标 点分别为树根构造两棵树外，还采用桥测试的方法取到狭窄通道内的点，并分别以这些点为树根分别生成树，当两棵树相遇则将这两棵树合并成一棵树，直到某一棵树中即包含了 初始 点 又 包含 目标 点此时意味着已经找到了从 初始 点到 目标 点的路径。 此方法因为增加了在狭窄通道内生长的树，使得该方法应用于多狭窄通 道的问题时具有十分好的特性。 ③ 应用 RRT 的搜索信息 VLRRT： 此方法是将树中的每个节点都关联一个关于生长步长的参数 r，每次生长的步长都由生长点的 r 值决定，并且 r 的值会根据此生长点是否可以成 功生长而实时变化。 如当 node1（ r = 2）为生长点时，以 node1 为生长点以 2 为步长生。