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

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

?

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

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

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

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

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

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

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

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

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

2坐標(biāo)系．

2 包圍球法的二叉樹(shù)搜索

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

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

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

3 算法實(shí)現(xiàn)

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

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

4 實(shí)例分析

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

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

實(shí)例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)二叉樹(shù)分解，可以判斷塔機(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個(gè)頂端包圍球相交，所以兩塔機(jī)有發(fā)生碰撞的可能．

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

5 結(jié)論

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

[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] 章紅，梅健，盧揚(yáng)，等．塔機(jī)防碰撞控制算法研究[J]．機(jī)電工程，2015，32（7）：962-966

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

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

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

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

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

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

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