基于RRTConnect算法的双履带起重机路径规划研究论文

1、 PAGE59 / NUMPAGES68硕 士 学 位 论 文基于RRTConnect算法的双履带起重机路径规划研究Path Planning for Two Crawler Cranes Heavy Lifting Based on RRTConnect理工大学DalianUniversity of Technology理工大学学位论文独创性声明作者重声明：所呈交的学位论文，是本人在导师的指导下进行研究工作所取得的成果。尽我所知，除文中已经注明引用容和致的地方外，本论文不包含其他个人或集体已经发表的研究成果，也不包含其他已申请学位或其他用途使用过的成果。与我一同工作的同志对本研究所做的贡献均

2、已在论文中做了明确的说明并表示了意。若有不实之处，本人愿意承担相关法律责任。学位论文题目：基于RRTConnect算法的双履带起重机路径规划研究作 者 签 名 ： 日期：年月日摘 要被吊设备、起重机以与吊装方式的多样化、复杂化等特点决定了起重机吊装是一类高危险性的活动。与单机吊装作业相比，两台履带起重机（文中简称双机）协同吊装的危险系数更高。为了安全顺利地完成吊装作业，合理高效的起重机路径规划就显得尤为重要。为此，本课题将针对双机协同吊装任务，抽象问题的数学模型，对闭环约束、非完整约束等开展深入研究，应用并改进RRTConnect算法，提出可以应用于平移和翻转被吊设备的通用方法，规划出满足无碰

3、撞、实时保证绳偏角、履带起重机行走特性和起重性能等要求的优化路径。首先，通过对吊装存在的安全性问题进行分析，以与对起重机吊装路径规划研究现状进行总结，论述了本课题的研究意义，同时对路径规划方法的特点进行研究确定应用和改进RRTConnect（双向多步扩展快速随机搜索树）算法来解决双机路径规划问题。其次，在讨论机器人路径规划的基础上，对双机路径规划问题进行深入剖析，构建双机吊装系统数学模型，并对数学模型的变量进行详细说明。再次，对双机吊装中两类常见吊装任务即将被吊设备翻转和将被吊设备平移，论述了采用RRTConnect算法解决双机路径规划问题的步骤，同时给出了逆向运动学确定双机初始和目标位姿的计

4、算过程和对路径的优化处理方法，并用三个典型案例验证方法的可行性。最后，对RRTConnect算法做改进，提出了基于关键位姿的RRTMultiPhrase算法，以解决双机吊装中较为复杂的吊装任务路径规划，论述了RRTMultiPhrase算法的原理，同时给出了关键点选择的一般方法，接着对两个复杂案例分别用三种方法进行路径规划，说明本文提出算法的可行性。本文分析了双机吊装作业的特点，对给定双机初始和目标位姿的协同吊装路径规划问题展开深入的探索和研究，实现了考虑直线行走、转弯、起升、回转和变幅等动作并满足无碰撞、闭环约束、非完整约束、不超载等约束的路径规划，解决了前人规划方法不适用于需要起重机行走或

5、者使被吊设备翻转的吊装任务的局限性，并且将提出的方法应用于典型的吊装案例，证明其可行性、实用性和高效性。关键词：路径规划；双机协同吊装；RRTConnect；闭环约束；非完整约束Path Planning for Two Crawler Cranes Heavy Lifting Based on RRTConnectAbstractNowadays, loads, cranes and lifting methods become more and more diversified and complicated which makes the heavy lifting a high ris

6、k activity. Compared with single crane lifting, two crawler cranes (dual-crane) lifting has a greater risk. To finish the lifting task successfully, it is very important to make a suitable and safe path planning as quickly as possible. So, this paper researches on dual-crane system, abstracts themat

7、hematicalmodel, applies and improves RRTConnect algorithm, proposes general methods which can be used in bothtranslating task and rotating task, and gains an optimized path which fulfillsconstraints such as collision-free, minimum rope-slope requirement, traveling feature of crawler crane and liftin

8、g capacity and so on.Firstly, by analyzing security problem existingin lifting task, and summary current achievement of path planning, we present the purpose and significance of this paper. Moreover, this paper studies on feature of algorithms used in path planning, and chooses RRTConnect (Rapidly-e

9、xploring Random Tree with Multi-step Expanding) as basic method to solve path planning of dual-crane.Secondly, based on the previous researches on robot path planning, this paper makes deep study on heavy lifting of dual-crane, and then builds mathematical model for this path planning problem. Moreo

10、ver, it makes definition and detailed description of the variant relevant to mathematical model. Thirdly,this paper adopts RRTConnect algorithm to search a feasible path. This method can be used in both translating task and rotating task which commonly exist in construction projects. Furthermore, ca

11、lculation of dual-cranes initial and target configuration applying inverse kinematical and optimization method are presented. Besides, three cases verify the method is feasible.Finally,it proposes RRTMultiPhrase algorithm which improves RRTConnect algorithm and bases on key configuration to deal wit

12、h complicated path planning of dual-crane.Whereafter, theory of RRTMultiPhrase algorithm and method of choosing a key configuration are presented. After that, we carry on path planning on two complicated cases with three methods independently. Results indicate the feasibility of proposed methods.Thi

13、s paper analyzes features of dual-crane lifting, makes deep exploration of path planning on condition that initial and target configuration is known. This approach takes cranes traveling, turning, hoisting, slewing and luffing action into consideration, aims to find a path satisfying collision-free,

14、 nonholonomic constraint, loop closure constraint and within lifting capacity and so on. Actual cases are described and corresponding results are listed. By analysis of the typical cases, we conclude that the proposed method is practical and efficient.Key Words：Path Planning; Dual-Crane Heavy Liftin

15、g;RRTConnect;Kinematic Closure Constraints;Nonholonomic Constraints目 录 TOC o 1-3 h z u HYPERLINK l _Toc327252642摘要 PAGEREF _Toc327252642 h IHYPERLINK l _Toc327252643Abstract PAGEREF _Toc327252643 h IIHYPERLINK l _Toc3272526441 绪论 PAGEREF _Toc327252644 h 1HYPERLINK l _Toc3272526451.1 吊装路径规划的重要性 PAGER

16、EF _Toc327252645 h 1HYPERLINK l _Toc3272526461.2 吊装路径规划研究现状 PAGEREF _Toc327252646 h 2HYPERLINK l _Toc3272526471.3 双机吊装路径规划研究现状 PAGEREF _Toc327252647 h 3HYPERLINK l _Toc3272526481.4 路径规划方法综述 PAGEREF _Toc327252648 h 4HYPERLINK l _Toc3272526491.5 课题的目的意义与主要工作容 PAGEREF _Toc327252649 h 7HYPERLINK l _Toc3

17、272526502 双机吊装路径规划数学模型 PAGEREF _Toc327252650 h 9HYPERLINK l _Toc3272526512.1 数学模型 PAGEREF _Toc327252651 h 9HYPERLINK l _Toc3272526522.2 名词定义 PAGEREF _Toc327252652 h 10HYPERLINK l _Toc3272526532.2.1 刚体模型 PAGEREF _Toc327252653 h 10HYPERLINK l _Toc3272526542.2.2 位姿空间 PAGEREF _Toc327252654 h 12HYPERLINK

18、 l _Toc3272526552.2.3 控制输入集 PAGEREF _Toc327252655 h 14HYPERLINK l _Toc3272526562.2.4 位姿变换 PAGEREF _Toc327252656 h 15HYPERLINK l _Toc3272526572.2.5 距离函数 PAGEREF _Toc327252657 h 16HYPERLINK l _Toc3272526582.3 路径约束 PAGEREF _Toc327252658 h 17HYPERLINK l _Toc3272526592.3.1 行走非完整约束 PAGEREF _Toc327252659 h

19、 17HYPERLINK l _Toc3272526602.3.2 双机闭环约束 PAGEREF _Toc327252660 h 18HYPERLINK l _Toc3272526612.3.3 碰撞检测 PAGEREF _Toc327252661 h 19HYPERLINK l _Toc3272526622.4 本章小结 PAGEREF _Toc327252662 h 20HYPERLINK l _Toc3272526633 基于RRTConnect算法的双机路径规划方法 PAGEREF _Toc327252663 h 21HYPERLINK l _Toc3272526643.1 问题描述

20、PAGEREF _Toc327252664 h 21HYPERLINK l _Toc3272526653.2 问题解决 PAGEREF _Toc327252665 h 21HYPERLINK l _Toc3272526663.2.1 RRTConnect算法 PAGEREF _Toc327252666 h 22HYPERLINK l _Toc3272526673.2.2 始末位姿确定 PAGEREF _Toc327252667 h 25HYPERLINK l _Toc3272526683.2.3 路径优化 PAGEREF _Toc327252668 h 26HYPERLINK l _Toc32

21、72526693.3 案例演示与分析 PAGEREF _Toc327252669 h 27HYPERLINK l _Toc3272526703.3.1 案例一 PAGEREF _Toc327252670 h 27HYPERLINK l _Toc3272526713.3.2 案例二 PAGEREF _Toc327252671 h 30HYPERLINK l _Toc3272526723.3.3 案例三 PAGEREF _Toc327252672 h 34HYPERLINK l _Toc3272526733.3.4 案例分析 PAGEREF _Toc327252673 h 37HYPERLINK

22、l _Toc3272526743.4 本章小结 PAGEREF _Toc327252674 h 38HYPERLINK l _Toc3272526754 改进RRTConnect算法的双机路径规划方法 PAGEREF _Toc327252675 h 39HYPERLINK l _Toc3272526764.1 问题描述 PAGEREF _Toc327252676 h 39HYPERLINK l _Toc3272526774.2 问题解决 PAGEREF _Toc327252677 h 39HYPERLINK l _Toc3272526784.2.1 RRTMultiPhrase算法 PAGER

23、EF _Toc327252678 h 39HYPERLINK l _Toc3272526794.2.2 关键位姿点选择 PAGEREF _Toc327252679 h 40HYPERLINK l _Toc3272526804.3 案例演示与分析 PAGEREF _Toc327252680 h 41HYPERLINK l _Toc3272526814.3.1 案例一 PAGEREF _Toc327252681 h 41HYPERLINK l _Toc3272526824.3.2 案例二 PAGEREF _Toc327252682 h 46HYPERLINK l _Toc3272526834.3.

24、3 案例分析 PAGEREF _Toc327252683 h 50HYPERLINK l _Toc3272526844.4 本章小结 PAGEREF _Toc327252684 h 50HYPERLINK l _Toc327252685结论 PAGEREF _Toc327252685 h 51HYPERLINK l _Toc327252686参考文献 PAGEREF _Toc327252686 h 53HYPERLINK l _Toc327252687附录A 主要符号的意义 PAGEREF _Toc327252687 h 58HYPERLINK l _Toc327252688攻读硕士学位期间发

25、表学术论文情况 PAGEREF _Toc327252688 h 59HYPERLINK l _Toc327252689致 PAGEREF _Toc327252689 h 60HYPERLINK l _Toc327252690理工大学学位论文使用授权书 PAGEREF _Toc327252690 h 611 绪论1.1 吊装路径规划的重要性本文的研究对象为两台履带起重机，简称为双机。保证安全性是起重机吊装的首要问题。被吊设备、起重机以与吊装方式的多样化、复杂化等特点决定了起重机吊装是一类高危险性的活动。对于单台起重机吊装，需确保吊装过程中不发生碰撞且起重机负载率在允许的围之，因其不需协同，可控性

26、好，吊装安全性较易得到保证。然而对于两台或多台起重机协同吊装，起重机之间的运动相互影响，一台起重机的动作引起的多机系统整体位姿变化和载荷重分配难以确定，其吊装的危险性要比想象严重得多，极容易出现负载不均引起某台起重机臂架折断或整机倾翻，随后形成多米诺骨牌效应，可能会导致所有起重机全部翻车。多机吊装失败造成巨大经济损失，甚至车毁人亡的案例比比皆是。如，1993年在澳大利亚昆士，两台Lampson起重机M4100和M4600协同吊装一个大跨度的钢架立片时，因吊装方案制定阶段起重机动作规划不当，致使实施过程中M4100严重超载，造成此起重机臂架折断的重大事故，如图1.1所示。2008年1月美国圣彼德

27、斯堡市，六台汽车式起重机协同吊装一根用于电力的巨大钢管道时，由于一台起重机超载致使上车倾翻，造成了人员伤亡和巨大的经济损失，如图1.2所示。2009年7月印度新德里，四台起重机协同吊起一个巨大钢梁，由于其中一台起重机的误操作致使另外三台起重机无法承受钢梁重量而被砸翻，造成至少四至六人受伤的严重后果。而在国也不乏类似的案例。因此，保证安全性是起重机吊装尤其多机协同作业的首要问题。 图1.1 1993年在澳大利亚昆士兰事故 图1.2 2008年在美国圣彼德斯堡事故 Fig. 1.1 Accident in QueenslandAustralia Fig. 1.2 Accident in St Pe

28、tersburgAmerica in 1993in Jan. 2008以上事件的发生归根结底是方案本身不安全和实际执行时误造作并未能与时修正。对于吊装方案制定，传统方法存在严重不足，例如：a. 由CAD设计软件自身的限制致使关键点的分析和选取不够全面，难以保证安全性；b. 路径规划涉与碰撞、起重性能、环境因素等多方面容，制定过程工作非常繁杂，反复进行大量查阅资料和计算任务，耗时长；c. 关键点之间的路径规划严重依赖于指挥人员的主观判断，大大提高对方案制作人员的要求。吊装路径规划是近年来所采用的保证安全性的新型吊装技术，即在有障碍物的环境，按照一定的评价标准，寻找一条从起吊状态（起吊时刻各起重机

29、位姿）到就位状态（就位时刻各起重机位姿）的无碰撞优化路径。此处路径定义为起重机吊装被吊设备过程中，按时间顺序组成的每台起重机的动作（起升、变幅、回转、行走）序列。吊装路径规划具有安全性、高效性、指导性等优点，能很好的解决传统方法存在的不足，在仿真基础上提出自动寻找路径的方法，因此，吊装路径规划是保证安全性的重要手段。1.2 吊装路径规划研究现状一直从事起重机吊装技术研究的著名专家Koshy Varghese教授与其团队是最早开展移动式起重机路径规划研究的学者，于1997年Raghunatha Reddy, H在他硕士论文中提出一种基于图论的单台起重机路径规划方法 ADDIN NE.Ref.51

30、0AC75D-3D8C-4CFD-80E0-7C8E8B22BBA61。于2002年他提出一种二阶段搜索的单台起重机路径规划方法 ADDIN NE.Ref.CCE1A585-C1C0-4894-AAD8-97C959D6389A2，第一阶段结合爬山策略采用深度优先图遍历的方法在无碰撞空间中找到一条可行路径，然后在第二阶段对此可行路径采用启发式函数进行优化。该方法特点是在搜索之前需要将起重机的位形空间以一定的步长离散成点，并用碰撞检测函数构造无碰撞的搜索图。因构造图需要大量的计算，因而该算法效率较低。为了检验基于随机采样规划方法在起重机路径规划中的性能，王欣等人采用双向RRT（Bi-direct

31、ional RRT）规划不考虑行走的单台履带起重机的吊装路径 ADDIN NE.Ref.B365ED53-72BA-45E1-8C25-B58D3FFE4A143，该方法考虑了起重机吊钩旋转自由度，案例表明，该方法求解效率很高且路径近似最优。针对动态的作业环境，Cheng Zhang提出一种实时的在线单台起重机吊装路径规划方法 ADDIN NE.Ref.52354DEA-6B16-47F3-970D-C767746D544A4, 5，在执行离线规划出来的路径过程中，算法采用UWB RTLS系统（ultra wideband Real-Time Location Systems）收集当前作业环境

32、数据、更新环境模型，然后若有必要则采用DRRT规划算法（RRT的变种）重新规划路径，若规划成功则沿着更新后的路径继续工作，直至吊装任务完成。该方法结合环境感知技术（传感器、定位系统等）实现吊装过程的监控和起重机吊装路径的实时规划，在一定程度上提高了吊装的安全性。海事大学黄有方课题组对集装箱吊装的路径规划做了一定的研究，建立了以最短路径为目标函数、无碰撞为约束条件的集装箱装卸操作最优路径的单目标数学模型 ADDIN NE.Ref.88A45948-F022-4FD7-9015-1A91BF219B0E6, 7。丰桥技术科学大学的 HYPERLINK :/ engineeringvillage /

33、controller/servlet/Controller?CID=expertSearchCitationFormat&searchWord1=%7bTerashima%2C+Kazuhiko%7d+WN+AU&database=1&yearselect=yearrange&searchtype=Expert&sort=yr Terashima, Kazuhiko、杜兰大学的 HYPERLINK :/ engineeringvillage /controller/servlet/Controller?CID=expertSearchCitationFormat&searchWord1=%7b

34、Lee%2C+Ho-Hoon%7d+WN+AU&database=1&yearselect=yearrange&searchtype=Expert&sort=yr Lee, Ho-Hoon、okuyamna College of Teclmology的Akamatsu, T.等人对桥式起重机的吊装进行路径规划进行了大量的研究，主要研究单台起重机在高速吊装过程中如何规划其动作并进行控制，以实现安全、高效的吊装 ADDIN NE.Ref.F3659571-FB84-4692-90C0-E22412AB38BB8-11。另外，SunNing等国立大学土木系的康仕仲课题组提出的基于增量解耦多塔机协同路

35、径规划 ADDIN NE.Ref.3EF1F992-40F2-4E9E-8933-A87F7869FE9112, 13。1.3 双机吊装路径规划研究现状随着两台起重机协同吊装日趋普遍， Sivakumar, P. L.应用A*算法、爬山算法进行双机协同吊装路径规划 ADDIN NE.Ref.F5D05B76-BA7C-4BBF-8414-067FABA12FD214，实验表明爬山算法比A*算法能快速找到可行路径但路径不优，而A*算法能找到较优的路径但耗时长。因A*算法、爬山算法这类基于几何构造规划方法均需要构造庞大的无碰撞搜索图，其计算复杂度随着起重机的自由度与空间离散分辨率呈指数增长，难以胜

36、任带高自由度的起重机吊装路径规划。为此，M.S.Ajmal Deen Ali和Sivakumar, P. L.等人面向两台起重机协同吊装提出一种基于遗传算法（GA）的路径规划方法 ADDIN NE.Ref.9F4695A6-F634-4DEE-8C5C-258322F0ECA615-19，该方法采用固定长度的串表示吊装路径，根据位形间的偏移量构造适应度函数，应用遗传算法的选择、交叉、变异等操作不断演化路径种群，最终求得较优吊装路径，从文献中的实验可以看到，相比A*算法，遗传算法的计算效率提高了1020倍，所得路径长度相当。该方法虽然避免空间的几何构造而提高了计算性能，但其也存在一些不足，比如路

37、径必须由数量固定的位形构成（等长的个体）、收敛速度与路径的质量难以控制等。为了克服路径必须由数量固定位形构成的不足，王欣、玉院等人采用蚁群算法进行单台起重机和两台起重机路径规划 ADDIN NE.Ref.AD1C54A3-5566-4986-AD53-C044FAE5AA4420, 21，该方法将位形间距离、碰撞、起重机动作优先级与切换等因素融入路径点选择策略和信息素更新中，该方法能找到近似最优的路径且无需要求路径由确定数量的位形构成。但蚁群算法息素因子、启发式因子与信息残留系数较难选择，且计算时间长。为了进一步提高吊装路径规划的计算效率，Yu-Cheng Chang于2012年提出一种基于概

38、率路标法（PRM，Probabilistic roadmaps Method）规划单台起重机和两台起重机协同吊装的路径 ADDIN NE.Ref.EFDCEE86-9DC6-4C3F-9A39-3FF1AEEC0C7522，该方法先将起重机的回转、变幅自由度作为位形的变量（此时暂未考虑起升自由度），在此位形空间中采用PRM规划出一条无碰撞的吊装路径，然后在此路径的基础上进行起重机起升动作的规划，从而最终得到一条可行的无碰撞吊装路径。实验显示这种将自由度分解降维进行分步规划的方法可以提高规划的效率，相比遗传算法效率提高了数十倍，对于一些相对较为简单的吊装环境，该方法几乎达到实时。针对吊装路径的平

39、滑性问题，文献 ADDIN NE.Ref.047CEBAD-BF8B-4719-AC08-04B181CA2CD223采用四次样条光滑遗传算法得到的两台起重机协同吊装路径。双机协同吊装系统可视为两个移动式机器人协同作业。因此本文研究的问题与多机器人协作物体操作（Multi-robot Cooperative Object Operation）问题有一定相似性。然而双机路径规划为多种困难问题的结合体：a. 高维自由度问题；b. 协同问题（其中的闭环约束问题需要进一步的研究和解决）；c. 行走非完整约束问题。移动式起重机是一种用于吊装的刚柔耦合的机构，可被看成是一种特殊机器人。它与传统的移动式机械

40、臂相比，从起重机机构和作业特点上来看，具有刚柔混合、机构尺寸可变、起升能力敏感等特征。1.4 路径规划方法综述（1） 路径规划方法分类作为机器人研究领域的一个基本问题，路径规划经历近二、三十年的发展，已出现许多规划算法，主要分为三类：a. 基于自由空间几何构造的规划方法与前向图搜索算法；b. 智能规划方法；c. 基于随机采样的规划方法。基于自由空间几何构造的规划方法与前向图搜索算法主要有可视图 ADDIN NE.Ref.D8946B9E-BAFD-4986-A062-8F05731D2B2324, 25、栅格分解 ADDIN NE.Ref.B466A019-DA84-4857-A346-C1C

41、B05441EE126-28、Voronoi图 ADDIN NE.Ref.F44B2936-2C09-4DF7-9057-B1C79690222228, 29、Dijkstra算法 ADDIN NE.Ref.2192CF72-5091-4ABC-99F0-DD2C59B7B15A30, 31、A*算法 ADDIN NE.Ref.A9D41578-F4D8-4929-98B5-C2AEB9E0BD8B30以与人工势场法 ADDIN NE.Ref.988581DB-0DB5-4ADB-82FC-AFDAF796FD5632, 33等等，这些方法对于很多规划问题都具备了很强的适应性，但当面对高自由度

42、机器人路径规划问题时，其计算复杂度将随自由度呈指数增长，而且对对微分约束和复杂环境也缺乏较好的解决办法。智能规划方法主要包括遗传算法 ADDIN NE.Ref.02B21AB0-9764-4D24-B121-BCE147BE06DD34-38、蚁群算法 ADDIN NE.Ref.D052B850-9288-4EE3-B255-C42D5AFF9A8B39, 40和人工神经网络方法 ADDIN NE.Ref.9C84C3B4-F578-401A-AFF8-ED3992EC8A9541-44等等，这些方法可以得到最优或者近似最优路径，但是收敛速度和有效性难以保证，并且需要设置的经验参数太多，不利于

43、自动处理。基于随机采样的规划方法是路径规划的新手段。基于随机采样的方法是在随机采样理论的基础上发展而来的一类路径规划新方法，其仅仅通过对位形空间或状态空间中的采样点进行碰撞检测来获取障碍物信息, 避免了对空间的建模，且在高维空间中的搜索效率很高，因而这类方法更适合于求解高自由度机器人在复杂环境中的规划问题，而且对带有微分约束的规划问题也具有较强的解决能力。概率路标法（PRM，Probabilistic Roadmaps Method） ADDIN NE.Ref.7E95619C-C936-4890-8433-CCF1106CF9ED45-51和快速随机生成树方法（RRT，Rapidly-Exp

44、loring Random Trees） ADDIN NE.Ref.784AD3D7-AFF9-47F3-BCB4-19B20C218B933, 29, 52-57是目前最成功的两种基于采样的路径规划方法。PRM方法是通过在整个空间采样得到若干个采样点，并由这些采样点构成一概率地图，最后在地图中搜索得到合适的路径，其在高维静态空间中具有良好的表现。RRT算法遵循控制理论的系统状态方程，在控制量的作用下增量式地产生新状态直至到达目标, 这使它很容易满足系统运动动力学约束方面的要求，且适用于动态环境。基于随机采样的规划方法因其优良的特性已被广泛应用于机器人学、计算机动画、工业设计、生物计算等各领域

45、的路径规划问题中，并已成为当前路径规划研究的热点。本文双机路径规划为高自由度问题，并且是典型的非完整约束问题，因此采用基于RRTConnect算法的方法作为解决手段。S.M.LaVall等人于1998年提出了一种基于采样的路径规划方法快速随机搜索树算法（Rapidly-exploring RandomTree，RRT），由于此方法在高维空间中具有突出表现，以与在规划过程中可以引入运动学约束，因此目前RRT被广泛应用于许多路径规划问题中。（2） 基本RRT算法设C为路径规划问题的状态空间，Cfree（CfreeC）为与障碍物无碰撞的机器人自由空间，Cobst （CobstC）为与障碍物发生碰撞的

46、机器人碰撞空间，T表示含有k个节点的随机树，且TCfree，Xinit（Xinit T）为树的初始点即初始姿态，Xgoal（Xgoal T）为树的目标点即目标姿态。基本RRT算法流程：BULD_RRT(Xinit)T.init (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, X

47、rand,Xnear)If (NEW_STATE (Xrand,Xnear,Xnew,u) )thenT.add_vertex (Xnew);T.add_edge (Xnear,Xnew, u);Return;根据基本RRT算法流程与图1.3的可知，基本RRT的算法为首先以初始点Xinit作为树T的根节点；在Cfree中用函数RANDOM_STATE( )随机选择一个随机点Xrand，即使得XrandCfree；再用函数NEAREST_NEIGHBOR( )搜索树上离Xrand最近的节点用来扩展，这个节点被称为Xnear；用函数EXTEND( )来扩展树，即随机或是根据给定的标准，选择一个输入

48、u，使得Xnear向Xrand靠近，这时产生一个新节点Xnew，如果检测没有碰撞或满足要求，将Xnew加到树中。如此重复直到子节点集中包含目标姿态点Xgoal或子节点集中有节点在目标区域时终止算法执行，此时即找了一条以随机树T中节点组成的从初始姿态Xinit到目标姿态Xgoal的路径。图1.3 随机树扩展示意图Fig. 1.3Diagram of RRT expanding（3） 改进RRT算法基本RRT主要缺陷在于其为了找到目标点需要在整个空间进行搜索，效率很低。为提高搜索的效率，与路径的质量，很多学者对基本RRT进行了改进，形成了一些改进版本的RRT算法，这些改进的RRT算法通常可分为以下

49、三大类。 改进分支扩展方式的RRT改进分支扩展方式的RRT包括RRTGoalBias ADDIN NE.Ref.58546FCD-5B63-4D8F-B4FE-CF17D5CE0F5458, 59、RRTConnect ADDIN NE.Ref.92C9F81F-EBFB-4844-A857-0FF7DB82A0E860, 61等。RRTGoalBias：此种改进RRT方法在扩展过程中不是完全以随机点作为牵引点而是以一定概率用目标点作为的牵引点。RRTGoalBias方法可使树快速向目标点增长，但是当过多偏向目标点时可能会使树的生长陷入局部最优。RRTConnect：RRTConnect的基本

50、思想是使单步扩展的距离尽可能远，如下图所示该算法将基本RRT的单步扩展改进为具有贪婪性质的多步扩展，直到碰到障碍或到达目标点才结束一次扩展迭代。应用此多步扩展的方式可以有效避免陷入局部最优的可能，并且在相对开阔的区域RRTConnect可以快速向未探索的区域扩展从而可以大大提高生成树的效率。 增加随机树的数量双棵树RRT：双棵树RRT方法包括RRTExtExt、RRTExtCon、RRTConCon等，这些方法都是分别以起点和目标点作为树根，分别以单步或多步扩展的方式生长两棵树，直到两棵树相遇，此时即找到了从起点到终点的路径。此方法由于采用两棵树同时生长，大大提高了搜索的效率，尤其是双向都是多

51、步生长的RRTConCon方法具有很好的搜索特性，广泛应用于各路径规划问题中。MultiRRT：MultiRRT采用多棵树同时生长的方式进行路径规划，此方法除了应用初始点和目标点分别为树根构造两棵树外，还采用桥测试的方法取到狭窄通道的点，并分别以这些点为树根分别生成树，当两棵树相遇则将这两棵树合并成一棵树，直到某一棵树中即包含了初始点又包含目标点此时意味着已经找到了从初始点到目标点的路径。此方法因为增加了在狭窄通道生长的树，使得该方法应用于多狭窄通道的问题时具有十分好的特性。 应用RRT的搜索信息VLRRT：此方法是将树中的每个节点都关联一个关于生长步长的参数r，每次生长的步长都由生长点的r值

52、决定，并且r的值会根据此生长点是否可以成功生长而实时变化。如当node1（r = 2）为生长点时，以node1为生长点以2为步长生长新的的节点node2，如成功生长则将node2的r值设为2，并增大node1的r值，如生长失败则减小node1的r值。应用此方法可以根据环境的特点实时调整生长的步长，使步长的选择更加合理。1.5 课题的目的意义与主要工作容从以上的发展现状可以看出，面向双机协同吊装的路径规划是具有明确的应用背景和相当研究难度的研究课题，传统的技术和方法很难适应实际问题的需求，因而需要开展进一步的探索工作，吊装方案制定的安全性、合理性和高效性亟待提高，计算机辅助路径规划将成为重要的手

53、段。然而，关于起重机路径规划的相关研究在国尚未较好的展开，国外虽然针对吊装行业有较多的相关研究，但应用辅助吊装方案制作的并不多见，因此把路径规划应用于辅助吊装方案制作有着重要的工程应用意义和先进性，并且由路径规划展开的研究多针对单机。目前关于双机路径规划的研究一般只考虑起升、回转和变幅三个动作，且只针对平移搬运设备的吊装任务。而在一些实际吊装项目中起重机直线行走和转弯必不可少，否则无法完成吊装任务；并且建筑工程中同时存在将被吊设备平移搬运以与将被吊设备从水平状态竖直并安装的任务。可见对双机路径规划作进一步研究非常必要，对路径规划中存在的高自由度、闭环约束、行走非完整约束等问题进行研究解决，具有

54、一定的科学意义。本文以提高吊装方案制定的合理性，高效性和可靠性为目标，以两台移动式起重机吊装作业为基础，着重对双机吊装系统研究对象进行分析，构建几何和问题模型以应用RRTConnect算法进行寻路，并提出RRTMultiPhrase算法解决了双机路径规划更复杂的问题，实现在给定双机初始和目标位姿信息的情况下，在C空间中搜索到满足无碰撞、实时保证绳偏角要求、起重性能和履带起重机行走特性等约束的路径。该方法适用于双机平移设备和翻转设备两种吊装任务，同时，双机均可以通过直线行走、转弯、起升、变幅、回转等动作完成。本文的主要研究工作：（1） 研究当前机器人和起重机路径规划的研究成果，总结路径规划算法。

55、（2） 研究双机吊装系统结构，分析履带起重机的动作特点，将双机简化为具有十二个自由度的机器人，建立几何模型和可视化模型。（3） 分析吊装路径需要满足的约束，重点研究了满足行走非完整约束和闭环约束的实现方法，构建适用于RRTConnect算法解决的数学模型，并根据双机研究对象对数学模型中的名词变量做了具体定义。（4） 实现用RRTConnect算法解决双机路径规划问题，设计三个典型吊装案例并分析用该方法进行路径规划的结果，证实其可行性。（5） 改进RRTConnect算法，提出基于关键位姿点的RRTMultiPhrase算法，设计两个复杂的吊装案例，对比三种不同方法分别进行路径规划的结果，说明提

56、出算法的优缺点和可行性。本文的容大致安排如下：第一章对吊装路径规划的重要性，以与吊装路径规划尤其双机吊装路径规划以与路径规划方法进行概述，提出本文的研究目的和意义。第二章对双机路径规划问题进行深入剖析，构建双机吊装数学模型，并对模型中相关变量进行定义，说明了路径满足约束的方法。第三章对论述了采用RRTConnect算法解决双机路径规划问题的过程，通过典型的实例分析，证实了该方法的可行性、灵活性和可控性。第四章提出了基于关键位姿的RRTMultiPhrase算法，以解决双机吊装中较为复杂的吊装任务路径规划，接着对比分析了同一个问题用三种方法得到的结果，验证其有效性。最后总结全文，并给出需进一步展

57、开研究的方向和容。2 双机吊装路径规划数学模型双机吊装主要有两种形式：一种为两台起重机协同完成被吊设备的转移，在此过程中设备不翻转，一般使用两台完全一样的起重机，并且双机的位姿、动作是对称的，后文中用起重机A和起重机B表示；一种为两台起重机协同将设备翻转，一台完成主要的起升任务，称为主起重机，用起重机A表示，另一台通过简单的配合动作直到设备竖直，称为溜尾起重机，用起重机B表示，起重机B与设备脱离后完成双机吊装任务，之后由起重机A转移并安装设备以完成整个吊装任务。本文研究的路径规划即针对以上两种情况的双机吊装过程。2.1 数学模型双机路径规划是指已知双机的初始和目标位姿以与吊装现场的环境设施，找

58、到从初始位姿到目标位姿的的满足约束的双机动作序列，即按时间顺序依次执行的动作类型和动作量。因此，对双机路径规划问题数学描述如下： P = ， （2.1）式中，位姿空间，用双机的各自由度与其取值围描述；双机的初始位姿；双机的目标位姿；每一步可选择的输入集；位姿空间约束，双机的各个自由度在其取值围；起重性能约束，双机均满足一定的负载率要求；无碰撞约束，吊装过程中起重机、被吊设备和环境三者之间无碰撞；闭环约束，双机、被吊设备和地面组成闭环，允许起重机动作时吊索具的偏角在设定的围；行走特性约束，履带起重机行走为差分运动形式，需满足非完整约束；路径长度约束，即期望两吊点在吊装过程中运动轨迹长度最短。本文

59、提出的算法需满足以下假设：（1） 吊装过程中环境为静止的，起重机的下车、转台、臂架以与被吊设备模型均简化为长方体；（2） 被吊设备重心在两个吊点连线上，因此整个吊装过程中分配到两台起重机上的重量不变，将臂架仰角限定在一定围可满足负载率约束，即转化为位姿空间的约束。2.2 名词定义2.2.1 刚体模型研究双机路径规划问题首先要对双机、被吊设备与场地中的障碍物建立三维模型。本文将这些真实的物理模型进行抽象，建立相应的简单刚体模型。将双机和设备简化为9个刚体，包括双机的下车、转台、臂架、吊索具以与被吊设备，除了吊索具以外的7个刚体为由6个面包围的长方体，如图2.1所示。本文中障碍物刚体模型也简化为长

60、方体。由于本文研究的是静态环境下的双机路径规划，障碍物为静态物体，双机和被吊设备为运动物体。因此，障碍物的建模需要各自的位置和尺寸信息，而双机和设备随时间变化位姿不断转变，其建模相对复杂，需要各个刚体的尺寸信息即双机和设备固有的尺寸信息包括9个长方体的长宽高，并且需要刚体间的相对位置数据。0：起重机A下车；1：起重机A转台；2：起重机A臂架；3：起重机A吊索具；4：起重机B下车；5：起重机B转台；6：起重机B臂架；7：起重机B吊索具；8：被吊设备图2.1 双机和设备模型Fig. 2.1 Model of dual-crane system建立了表示双机和设备各个部分的刚体模型，我们需要通过刚体