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

?

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

許景波[1]，崔曉萌1，劉泊1，許曉紅2

（1. 哈爾濱理工大學(xué) 測控技術(shù)與通信工程學(xué)院，黑龍江 哈爾濱150080；2. 沙洲職業(yè)工學(xué)院 紡織工程系，江蘇 張家港 215699）

建筑工地中，往往是多塔機(jī)同時作業(yè)，而塔機(jī)間的防碰撞問題一直是建筑施工中所面臨的一項安全問題．在防碰撞包圍球判定方法基礎(chǔ)上，研究了二叉樹搜索算法在其中的應(yīng)用．借助空間坐標(biāo)變換以及位置信息的無線通信交換，詳細(xì)論述了二叉樹搜索算法的實現(xiàn)．該方法提高了碰撞區(qū)域判定效率，對于塔機(jī)安全運行，有效避免碰撞事故發(fā)生具有重要意義．

塔機(jī)防碰撞；包圍球法；坐標(biāo)變換；二叉樹

近年來，隨著建筑行業(yè)的蓬勃發(fā)展，塔機(jī)也越來越被廣泛應(yīng)用，建筑工地經(jīng)常是多塔機(jī)群同時作業(yè)，這也容易引起塔機(jī)間碰撞事故的發(fā)生．針對塔機(jī)間防碰撞問題，國內(nèi)外學(xué)者展開了廣泛研究，其關(guān)鍵在于如何判別定位預(yù)發(fā)生碰撞的區(qū)域，并對小于安全距離的情況及時報警，采取避讓．現(xiàn)有的研究大多采用齊次變換方法和包圍球法[1-3]，其中對齊次變換法的研究較多，它主要是將相鄰塔機(jī)的各自坐標(biāo)系通過齊次變換轉(zhuǎn)換成同一坐標(biāo)系，然后對碰撞情況進(jìn)行分類，利用空間幾何知識對將要發(fā)生碰撞的區(qū)域進(jìn)行判斷，并計算最小距離．該方法對碰撞情況分類較多，幾何量空間計算也比較復(fù)雜，不便于塔機(jī)控制器實現(xiàn)．常用的包圍球法需要由大到小逐級計算塔機(jī)間包圍球的干涉情況，該方法單次判斷計算比較簡單．但由于包圍球是由大到小逐級分解，單塔機(jī)分解的包圍球較多，而對于兩塔機(jī)，需要對2組包圍球互相間的干涉情況判別，所以計算量大，實現(xiàn)起來也比較繁瑣困難．

本文在常用包圍球法的基礎(chǔ)上，采用二叉樹搜索的方法，加快了搜索步驟，提高了碰撞區(qū)域判定的整體計算效率．

1 塔機(jī)空間坐標(biāo)變換

在塔機(jī)作業(yè)中，各塔機(jī)都有自己的坐標(biāo)系．在塔機(jī)間碰撞情況判別過程中，需建立一個統(tǒng)一的固定坐標(biāo)系，這就需要坐標(biāo)的齊次變換[4-5]．齊次變換源于機(jī)器人運動學(xué)，其可以推廣應(yīng)用于塔機(jī)作業(yè)中，坐標(biāo)系代表固定坐標(biāo)系（見圖1），坐標(biāo)系代表塔機(jī)1坐標(biāo)系，坐標(biāo)系代表塔機(jī)

2坐標(biāo)系．

2 包圍球法的二叉樹搜索

包圍球法源于虛擬現(xiàn)實技術(shù)，在虛擬現(xiàn)實世界中判斷一個物體是否穿過了場景中的某個部件，一個最簡單檢測方法就是分別用2個球形來包圍這2個物體，這2個包圍球近似代表了2個物體，然后再判斷它們之間是否相交[6]．這只需計算這2個球體球心距離是否小于它們的半徑和，如果小于則表示有可能發(fā)生碰撞．

由于塔機(jī)工作過程中的姿態(tài)任意性，很難對其進(jìn)行規(guī)范，而包圍球法能很好地解決這一問題．根據(jù)塔機(jī)的結(jié)構(gòu)，可分解為塔臂，斜拉絲、鋼絲與吊鉤3個需要保護(hù)的部分，以其外接球作為包圍球（見圖2）．當(dāng)兩塔機(jī)間的這些包圍球無交集時，說明不可能發(fā)生碰撞．當(dāng)有交集時，說明有碰撞的可能，需要將包圍球進(jìn)一步分解，以進(jìn)行更精細(xì)的判斷．考慮到塔機(jī)檢測精度的要求，最終可以分解為半徑0.5 m的包圍球進(jìn)行判斷（見圖3）．如果塔機(jī)間這些半徑為0.5 m的包圍球無交集說明無碰撞可能；如果有交集，則可以判斷出發(fā)生碰撞的部位．

由于有3個需要保護(hù)的部位，需要判斷這些部位上的每一個小球與相鄰塔機(jī)所有小球之間的位置關(guān)系，如此的計算工作量龐大，效率很低．二叉樹是一種特殊結(jié)構(gòu)的樹，它的每個節(jié)點最多只能有2個子節(jié)點，這種結(jié)構(gòu)很容易實現(xiàn)搜索，只需比較本層節(jié)點下的左、右2個子節(jié)點[7-8]．在此引進(jìn)二叉樹搜索的計算方法，提高了計算效率．首先對塔機(jī)的3個一級包圍球與相鄰塔機(jī)的一級包圍球進(jìn)行交集判斷，對于不存在交集的2個包圍球，不再進(jìn)行分解；對于存在交集的2個包圍球進(jìn)行二次分解，分解為上一級包圍球半徑一半的2個小包圍球．然后對這些分解的小包圍球再進(jìn)行上述分解判斷，如此反復(fù)，直至分解到0.5 m的包圍球．整個過程見圖4，可以看出其能夠有效提高整體的計算效率．

3 算法實現(xiàn)

以塔機(jī)中被保護(hù)部件幾何中心為球心，臂長為直徑建立一級包圍球，確定該球心在自身坐標(biāo)系中的坐標(biāo)，然后通過齊次變換得出該球心在固定坐標(biāo)系坐標(biāo)．相鄰塔機(jī)包圍球的空間坐標(biāo)參數(shù)，可以通過無線數(shù)據(jù)通信的方式進(jìn)行交換[9]．按式（5）判斷兩相鄰塔機(jī)包圍球干涉情況，如不干涉則結(jié)束判斷；如干涉，則將一級包圍球沿臂長平均分解成2個二級包圍球，球心沿臂長向兩端分別移動，重新計算球心坐標(biāo)及在固定坐標(biāo)系中坐標(biāo)．然后判斷與相鄰塔機(jī)二級包圍球的干涉情況，如沒有干涉則結(jié)束判斷；如干涉，則將發(fā)

生干涉的包圍球繼續(xù)分解，如此反復(fù)，直至分解的包圍球半徑小于0.5 m為止，在包圍球分解過程中分解半徑可以向上取整處理．從以上分析可以看出，整套算法可以用遞歸算法加以實現(xiàn)（見圖5）．

4 實例分析

對塔機(jī)間常遇到的幾種典型情況進(jìn)行了分析，通過計算仿真，可以看出本方法能夠?qū)@幾種碰撞情況進(jìn)行準(zhǔn)確有效判斷，增強(qiáng)了包圍球法的定位判別效率，也驗證了本方法的可行性．

實例1 設(shè)塔機(jī)甲吊臂長45 m，其在固定坐標(biāo)系中的坐標(biāo)為[（0，0，8），（38.97，22.5，8）]，相鄰塔機(jī)乙吊鉤及鋼絲空間坐標(biāo)為[（44，0，8），（44，0，18）]，由第一級包圍球可以判斷兩部件有相交可能，然后2個一級包圍球二叉樹分解為二級包圍球，而二級包圍球互不相交，所以可以判斷甲乙兩塔機(jī)中這2個部件不可能發(fā)生碰撞．

實例2 設(shè)塔機(jī)甲吊臂在固定坐標(biāo)系中坐標(biāo)為[（0，0，10），（31.82，31.82，10）]，相鄰塔機(jī)乙吊鉤鋼絲空間坐標(biāo)為[（31.5，31.5，9），（31.5，31.5，19）]，包圍球經(jīng)二叉樹分解，可以判斷塔機(jī)甲頂端分解的中心為（31.47，31.47，10），半徑為0.5 m的包圍球，與塔機(jī)乙分解的中心分別為（31.5，31.5，9.5），（31.5，31.5，10.5），半徑為0.5 m的2個頂端包圍球相交，所以兩塔機(jī)有發(fā)生碰撞的可能．

實例3 設(shè)塔機(jī)甲吊臂斜拉鋼絲線坐標(biāo)為[（0，0，13），（18，31.18，10）]，而相鄰塔機(jī)乙的吊鉤鋼絲空間坐標(biāo)為[（18，31，10），（18，31，20）]，包圍球經(jīng)二叉樹分解，可以判斷塔機(jī)甲頂端分解的中心為（17.75，30.75，10.04），半徑為0.5 m的包圍球，與塔機(jī)乙分解的中心為（18，31，10.5），半徑為0.5 m的頂端包圍球相交，所以兩塔機(jī)有發(fā)生碰撞的可能．

5 結(jié)論

本文在塔機(jī)碰撞包圍球判定方法基礎(chǔ)上，采用二叉樹搜索算法，實現(xiàn)了兩塔機(jī)間可能發(fā)生碰撞部位的預(yù)測判斷，據(jù)此兩塔機(jī)可以采取相應(yīng)的措施進(jìn)行有效避讓．在兩塔機(jī)空間坐標(biāo)變換的基礎(chǔ)上，使包圍球干涉判斷成為可能．在二叉樹搜索算法基礎(chǔ)上，進(jìn)一步提高了判定效率．此方法易于移植到塔機(jī)控制器中加以實現(xiàn)，具有實際應(yīng)用價值．

[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] 韓九強(qiáng)，趙瑋，魏全瑞．建筑塔吊群智能防碰撞系統(tǒng)[J]．建筑安全，2008（2）：12-14

[3] 章紅，梅健，盧揚，等．塔機(jī)防碰撞控制算法研究[J]．機(jī)電工程，2015，32（7）：962-966

[4] 沈雅瓊，葉伯生，熊爍．基于齊次變換矩陣的機(jī)器人軌跡規(guī)劃方法[J]．組合機(jī)床與自動化加工技術(shù)，2014（1）：5-9

[5] 舒志兵，張海榮．多關(guān)節(jié)機(jī)器人的運動學(xué)動態(tài)仿真研究[J]．機(jī)器人技術(shù)應(yīng)用，2006（6）：38-41

[6] 李洪亮．群塔機(jī)防碰撞算法與實驗研究[D]．哈爾濱：哈爾濱工業(yè)大學(xué)，2009：28-32

[7] 孫文勝，劉婷．一種改進(jìn)的基于二叉樹搜索的防碰撞算法[J]．計算機(jī)工程，2011，37（10）：257-259

[8] 葉品菊，吳斌，胡遠(yuǎn)望，等．直觀顯示二叉樹結(jié)構(gòu)的算法[J]．江南大學(xué)學(xué)報：自然科學(xué)版，2008，7（1）：60-63

[9] 張青春，王偉庚，孫志勇． ZigBee技術(shù)在塔吊安全監(jiān)測預(yù)警系統(tǒng)中的應(yīng)用[J]．計算機(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年住建部研究開發(fā)項目（2013-R3-7）

許景波（1973-），男，黑龍江齊齊哈爾人，教授，博士，從事精密測量、信號處理研究．E-mail：yucunl@163.com