基于二叉树搜索的塔机防碰撞包围球判定方法

许景波，崔晓萌，刘泊，许晓红



基于二叉树搜索的塔机防碰撞包围球判定方法

许景波[1]，崔晓萌1，刘泊1，许晓红2

（1. 哈尔滨理工大学 测控技术与通信工程学院，黑龙江 哈尔滨150080；2. 沙洲职业工学院 纺织工程系，江苏 张家港 215699）

建筑工地中，往往是多塔机同时作业，而塔机间的防碰撞问题一直是建筑施工中所面临的一项安全问题．在防碰撞包围球判定方法基础上，研究了二叉树搜索算法在其中的应用．借助空间坐标变换以及位置信息的无线通信交换，详细论述了二叉树搜索算法的实现．该方法提高了碰撞区域判定效率，对于塔机安全运行，有效避免碰撞事故发生具有重要意义．

塔机防碰撞；包围球法；坐标变换；二叉树

近年来，随着建筑行业的蓬勃发展，塔机也越来越被广泛应用，建筑工地经常是多塔机群同时作业，这也容易引起塔机间碰撞事故的发生．针对塔机间防碰撞问题，国内外学者展开了广泛研究，其关键在于如何判别定位预发生碰撞的区域，并对小于安全距离的情况及时报警，采取避让．现有的研究大多采用齐次变换方法和包围球法[1-3]，其中对齐次变换法的研究较多，它主要是将相邻塔机的各自坐标系通过齐次变换转换成同一坐标系，然后对碰撞情况进行分类，利用空间几何知识对将要发生碰撞的区域进行判断，并计算最小距离．该方法对碰撞情况分类较多，几何量空间计算也比较复杂，不便于塔机控制器实现．常用的包围球法需要由大到小逐级计算塔机间包围球的干涉情况，该方法单次判断计算比较简单．但由于包围球是由大到小逐级分解，单塔机分解的包围球较多，而对于两塔机，需要对2组包围球互相间的干涉情况判别，所以计算量大，实现起来也比较繁琐困难．

本文在常用包围球法的基础上，采用二叉树搜索的方法，加快了搜索步骤，提高了碰撞区域判定的整体计算效率．

1 塔机空间坐标变换

在塔机作业中，各塔机都有自己的坐标系．在塔机间碰撞情况判别过程中，需建立一个统一的固定坐标系，这就需要坐标的齐次变换[4-5]．齐次变换源于机器人运动学，其可以推广应用于塔机作业中，坐标系代表固定坐标系（见图1），坐标系代表塔机1坐标系，坐标系代表塔机

2坐标系．

2 包围球法的二叉树搜索

包围球法源于虚拟现实技术，在虚拟现实世界中判断一个物体是否穿过了场景中的某个部件，一个最简单检测方法就是分别用2个球形来包围这2个物体，这2个包围球近似代表了2个物体，然后再判断它们之间是否相交[6]．这只需计算这2个球体球心距离是否小于它们的半径和，如果小于则表示有可能发生碰撞．

由于塔机工作过程中的姿态任意性，很难对其进行规范，而包围球法能很好地解决这一问题．根据塔机的结构，可分解为塔臂，斜拉丝、钢丝与吊钩3个需要保护的部分，以其外接球作为包围球（见图2）．当两塔机间的这些包围球无交集时，说明不可能发生碰撞．当有交集时，说明有碰撞的可能，需要将包围球进一步分解，以进行更精细的判断．考虑到塔机检测精度的要求，最终可以分解为半径0.5 m的包围球进行判断（见图3）．如果塔机间这些半径为0.5 m的包围球无交集说明无碰撞可能；如果有交集，则可以判断出发生碰撞的部位．

由于有3个需要保护的部位，需要判断这些部位上的每一个小球与相邻塔机所有小球之间的位置关系，如此的计算工作量庞大，效率很低．二叉树是一种特殊结构的树，它的每个节点最多只能有2个子节点，这种结构很容易实现搜索，只需比较本层节点下的左、右2个子节点[7-8]．在此引进二叉树搜索的计算方法，提高了计算效率．首先对塔机的3个一级包围球与相邻塔机的一级包围球进行交集判断，对于不存在交集的2个包围球，不再进行分解；对于存在交集的2个包围球进行二次分解，分解为上一级包围球半径一半的2个小包围球．然后对这些分解的小包围球再进行上述分解判断，如此反复，直至分解到0.5 m的包围球．整个过程见图4，可以看出其能够有效提高整体的计算效率．

3 算法实现

以塔机中被保护部件几何中心为球心，臂长为直径建立一级包围球，确定该球心在自身坐标系中的坐标，然后通过齐次变换得出该球心在固定坐标系坐标．相邻塔机包围球的空间坐标参数，可以通过无线数据通信的方式进行交换[9]．按式（5）判断两相邻塔机包围球干涉情况，如不干涉则结束判断；如干涉，则将一级包围球沿臂长平均分解成2个二级包围球，球心沿臂长向两端分别移动，重新计算球心坐标及在固定坐标系中坐标．然后判断与相邻塔机二级包围球的干涉情况，如没有干涉则结束判断；如干涉，则将发

生干涉的包围球继续分解，如此反复，直至分解的包围球半径小于0.5 m为止，在包围球分解过程中分解半径可以向上取整处理．从以上分析可以看出，整套算法可以用递归算法加以实现（见图5）．

4 实例分析

对塔机间常遇到的几种典型情况进行了分析，通过计算仿真，可以看出本方法能够对这几种碰撞情况进行准确有效判断，增强了包围球法的定位判别效率，也验证了本方法的可行性．

实例1 设塔机甲吊臂长45 m，其在固定坐标系中的坐标为[（0，0，8），（38.97，22.5，8）]，相邻塔机乙吊钩及钢丝空间坐标为[（44，0，8），（44，0，18）]，由第一级包围球可以判断两部件有相交可能，然后2个一级包围球二叉树分解为二级包围球，而二级包围球互不相交，所以可以判断甲乙两塔机中这2个部件不可能发生碰撞．

实例2 设塔机甲吊臂在固定坐标系中坐标为[（0，0，10），（31.82，31.82，10）]，相邻塔机乙吊钩钢丝空间坐标为[（31.5，31.5，9），（31.5，31.5，19）]，包围球经二叉树分解，可以判断塔机甲顶端分解的中心为（31.47，31.47，10），半径为0.5 m的包围球，与塔机乙分解的中心分别为（31.5，31.5，9.5），（31.5，31.5，10.5），半径为0.5 m的2个顶端包围球相交，所以两塔机有发生碰撞的可能．

实例3 设塔机甲吊臂斜拉钢丝线坐标为[（0，0，13），（18，31.18，10）]，而相邻塔机乙的吊钩钢丝空间坐标为[（18，31，10），（18，31，20）]，包围球经二叉树分解，可以判断塔机甲顶端分解的中心为（17.75，30.75，10.04），半径为0.5 m的包围球，与塔机乙分解的中心为（18，31，10.5），半径为0.5 m的顶端包围球相交，所以两塔机有发生碰撞的可能．

5 结论

本文在塔机碰撞包围球判定方法基础上，采用二叉树搜索算法，实现了两塔机间可能发生碰撞部位的预测判断，据此两塔机可以采取相应的措施进行有效避让．在两塔机空间坐标变换的基础上，使包围球干涉判断成为可能．在二叉树搜索算法基础上，进一步提高了判定效率．此方法易于移植到塔机控制器中加以实现，具有实际应用价值．

[1] Deen Ali，Ajmal M S，Babu，et al．Collision Free Path Planning of Cooperative Crane Manipulators Using Genetic Algorithm[J]．

Journal of Computing in Civil Engineering，2005，19（2）：182-193

[2] 韩九强，赵玮，魏全瑞．建筑塔吊群智能防碰撞系统[J]．建筑安全，2008（2）：12-14

[3] 章红，梅健，卢扬，等．塔机防碰撞控制算法研究[J]．机电工程，2015，32（7）：962-966

[4] 沈雅琼，叶伯生，熊烁．基于齐次变换矩阵的机器人轨迹规划方法[J]．组合机床与自动化加工技术，2014（1）：5-9

[5] 舒志兵，张海荣．多关节机器人的运动学动态仿真研究[J]．机器人技术应用，2006（6）：38-41

[6] 李洪亮．群塔机防碰撞算法与实验研究[D]．哈尔滨：哈尔滨工业大学，2009：28-32

[7] 孙文胜，刘婷．一种改进的基于二叉树搜索的防碰撞算法[J]．计算机工程，2011，37（10）：257-259

[8] 叶品菊，吴斌，胡远望，等．直观显示二叉树结构的算法[J]．江南大学学报：自然科学版，2008，7（1）：60-63

[9] 张青春，王伟庚，孙志勇． ZigBee技术在塔吊安全监测预警系统中的应用[J]．计算机测量与控制，2014，22（8）：2615-2618

The judgment method of tower crane collision with bounding sphere based on binary search tree

XU Jing-bo1，CUI Xiao-meng1，LIU Bo1，XU Xiao-hong2

，Harbin University of Science and Technology，Harbin 150080，China；2. Department of Textile Engineering，Shazhou Professional Institute of Technology，Zhangjiagang 215699，China）

In the construction site， multiple tower cranes often work at the same time， and so that collision problem between the tower crane has been faced in the building construction as a security problem．Deals with the binary tree search algorithm and its application in the judgment method of bounding sphere. By space coordinates transformation and location information exchange with wireless communication，the realization of the binary tree search algorithm is discussed in detail．The method improves the judgment efficiency of collision area．It is of great significance for the safe operation of tower crane and avoiding the accident effectively.

tower crane anti-collision；bounding sphere method；coordinate change；binary tree

TU61

A

10.3969/j.issn.1007-9831.2016.03.007

2016-01-10

2013年住建部研究开发项目（2013-R3-7）

许景波（1973-），男，黑龙江齐齐哈尔人，教授，博士，从事精密测量、信号处理研究．E-mail：yucunl@163.com