基于二叉樹搜索的塔機防碰撞包圍球判定方法

許景波，崔曉萌，劉泊，許曉紅

?

基于二叉樹搜索的塔機防碰撞包圍球判定方法

許景波[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