光纖定位單元防碰撞分治標簽算法

孟祥偉，劉志剛

(中國科學技術大學工程科學學院，安徽合肥 230027)

多目標光纖光譜天文望遠鏡［1］通過焦面上的k個光纖定位單元可以快速準確地實現對k個星體目標同時定位［2］觀察。光纖定位單元［3］由光纖及其控制機構組成，采用雙回轉機構［4］(中心回轉軸和偏心回轉軸)，簡稱中心軸和偏心軸，兩軸均由電機驅動，它們的運動使光纖端部可以到達觀測區域圓的任何位置。光纖定位采用的是各個光纖定位單元自動定位的模式，每個光纖定位單元的觀測區域是一個圓形區域，為了保證所有光纖單元的觀察區域能夠覆蓋整個焦面以提高觀測效率［5］，必須使相鄰光纖的觀測區域有部分重疊，這樣相鄰光纖定位單元的夾持機構在運動過程中可能產生碰撞。對單元的中心軸和偏心軸的運行進行控制，使其按特定的運行序列運行，這樣就能夠規避碰撞。因此，從軟件控制上進行單元之間的防碰撞［6］處理具有重要意義。

1 單元簡介

焦面上有k個光纖定位單元，如圖1(a)所示。一個光纖定位單位周圍有6個單元與其相鄰，如圖1(b)所示。光纖定位單元的夾持機構在運動過程中的外形輪廓可以提取為中心板和偏心桿，如圖1(c)所示。中心板在中心軸上以O點為圓心旋轉范圍為0～360°，偏心桿在偏心軸上以E點為圓心旋轉范圍為0～180°，光纖端部在偏心桿上。當單元運行時，偏心軸的旋轉帶動偏心桿展開可能與其周圍單元的偏心桿或中心板產生碰撞，但它們中心板與中心板之間不會產生碰撞，且當單元偏心桿不展開時不會造成任何碰撞。

圖1 單元分析圖

在星象觀測［7］時，光纖定位單元要運行到星象位置，由星象坐標位置計算單元中心軸和偏心軸需要旋轉多少角度才能使光纖端部到達星象位置，也即目標位置。以一個單元運行到星象位置P為例，如圖1(d)所示，若已知星象坐標P(x，y)，單元中心軸圓心坐標O(x0，y0)，中心軸臂長為 Rc，偏心軸臂長為Re，則可得中心軸、偏心軸需要旋轉的角度θc、θe為

2 防碰撞分治標簽算法

2.1 劃分運行序列

運行序列即一行由0和1數值組成的數組［8］，光纖定位單元按照這行數組能夠運行到星象處的目標位置。把中心軸和偏心軸需要旋轉的角度θc、θe按一定比例劃分為兩組運行序列。序列中的數值0表示暫停，數值1表示運行，劃分比例按1 rad=100片數值1。

假設θc劃分為N片數值1，θe劃分為M片數值1，由于單元運行時間要求盡量短，且偏心桿不展開不會造成碰撞，則劃分運行序列：

①若N＞M，中心軸先運行，偏心軸和中心軸同時運行完成，如圖2(a)所示；

②若N＜M，偏心軸和中心軸同時開始運行，中心軸先運行完成，偏心軸后運行完成，如圖2(b)所示。

圖2 運行序列的劃分

2.2 單元運行

對于焦面上k個光纖定位單元，每個單元在進行定位時都按照其運行序列運行，運行流程如圖3(a)所示。當k個單元運行1片時，運行序列的運行位置向前移動1個，此時對每個單元進行碰撞檢測，相對于當前正在檢測碰撞的單元，只要檢測到此單元與其周圍相鄰的6個單元中的某一個單元產生碰撞，則立即處理碰撞，處理碰撞原理如圖3(b)所示。產生碰撞的兩個單元根據防碰撞算法進行規避碰撞，之后進行運行序列的整理。由于規避碰撞和整理運行序列會造成運行序列的改變，故要對其單元再次進行碰撞檢測，直至無碰撞產生。當k個單元運行1片產生的碰撞都處理完成后，則再進行下1片的運行，直至所有單元都運行到達其定位的目標位置。該防碰撞算法通過對焦面上每個單元與其周圍相鄰單元的碰撞檢測，把產生碰撞的兩個單元進行處理，直至無碰撞產生，從而解決焦面上k個光纖定位單元之間的碰撞。

由于單元在運行時是同時的，則運行時間最長的那個單元決定了一次光纖定位的完成時間。為了讓單元運行時間最短，即運行序列片數最小，在處理碰撞時，盡可能處理已經達到目標位置的單元，讓未達到目標位置的單元繼續運行。

圖3 單元運行流程與處理碰撞原理圖

2.3 碰撞類型

光纖定位單元在運行時與其周圍的單元都有關系，若發生碰撞現象，則處理碰撞時影響因素較多，難以直接解決，為此可以采用分治算法的思想［9］。分治算法［10］是將一個不能直接解決的大問題，分割成一些相對容易解決的小問題，以便各個擊破，分而治之。這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。

利用分治算法思想把復雜的單元碰撞現象劃分為幾種類型處理，經研究分析發現兩單元產生碰撞必定有單元偏心軸的旋轉，即必定有單元的偏心桿參與。假設單元在運行時，當前檢測碰撞的單元為n單元，則相對于單元n，檢測到n單元與m單元運行時產生碰撞，如圖4所示，可分解為4種碰撞類型。

①第1種碰撞類型：n單元中心板與m單元偏心桿相碰，如圖4(a)所示，記為Tp1；

②第2種碰撞類型：n單元偏心桿與m單元中心板相碰，如圖4(b)所示，記為Tp2；

③第3種碰撞類型：n單元已到目標位置，n單元偏心桿與m單元偏心桿相碰，如圖4(c)所示，記為Tp3；

④第4種碰撞類型：n單元未到目標位置，n單元偏心桿與m單元偏心桿相碰，如圖4(d)所示，記為Tp4。

2.4 碰撞標簽

兩個單元在運行過程中產生碰撞，判斷處理哪個單元以及是處理其中心板還是處理偏心桿，碰撞標簽就是判斷處理的重要依據。用單元碰撞屬性標簽化［11］方法生成每個單元的碰撞標簽［12］。

圖4 碰撞類型示意圖

假設以n單元的中心板在目標位置，其偏心桿從起始位置展開至目標位置的過程中是否與m單元在目標位置(中心板及偏心桿在目標位置)時產生碰撞，如圖5所示，進行碰撞標簽分類。

①第1種碰撞標簽：n單元偏心桿運行過程中與m單元中心板目標位置、偏心桿目標位置都不相碰，如圖5(a)所示，記為Tg1；

②第2種碰撞標簽：n單元偏心桿運行過程中與m單元中心板目標位置相碰，如圖5(b)所示，記為Tg2；

③第3種碰撞標簽：n單元偏心桿運行過程中與m單元偏心桿目標位置相碰，如圖5(c)所示，記為Tg3；

④第4種碰撞標簽：n單元偏心桿與運行過程中m單元中心板目標位置、偏心桿目標位置都相碰，如圖5(d)所示，記為Tg4。

圖5 碰撞標簽示意圖

由于單元碰撞屬性標簽化處理只與單元的目標位置有關，故可在單元運行之前預先處理，這樣在碰撞處理時可直接調用，能夠較大節省處理時間。

2.5 規避碰撞

規避碰撞就是碰撞處理，將單元的中心軸或偏心軸運行序列在當前的碰撞位置之前暫停p片運行數值為1的運行片，并在運行序列末尾加上p片運行數值為1的運行片。由于處理碰撞過程中要規避碰撞而處理p片運行片，當p值很小時，則碰撞單元不能有效地規避碰撞，從而需要再次規避碰撞，造成處理時間長。當p值很大時，雖然能有效地避免碰撞，但每次暫停的運行片多，檢測碰撞次數多，故造成處理時間長，且運行序列變長，將導致最終運行完成時間變長。如圖6所示，經分析驗證p=10時能有效地規避碰撞，且處理時間短。

圖6 處理時間與暫停片數關系

假設單元在運行時，當前檢測碰撞的單元為n單元，檢測到n單元與m單元在運行過程中產生碰撞，進行碰撞處理時，首先把碰撞情形對應其碰撞類型和碰撞標簽，最后判斷處理某個單元的某個軸運行序列。例如若碰撞情形對應第1種碰撞類型和第1種碰撞標簽(記為Tp1+Tg1)，則處理m單元偏心軸運行序列。處理單元運行序列的依據有3條：

①由于最長運行時間的單元決定光纖定位的完成時間，故為縮短光纖定位時間，應盡量處理已經到達目標位置的單元，例如碰撞情形Tp3+Tg1和Tp3+Tg3共2種；

②由于單元的偏心桿不展開不會造成碰撞，故應盡量處理單元偏心軸，例如碰撞情形Tp1+Tg1、Tp1+Tg3、Tp2+Tg1、Tp2+Tg3、Tp3+Tg2、Tp3+Tg4、Tp4+Tg1、Tp4+Tg2、Tp4+Tg4 共9 種；

③由于處理單元的偏心軸時，有時不能有效地規避碰撞，即會產生碰撞標簽中碰撞情形，故可處理單元的中心軸或碰撞的另一單元，例如碰撞情形Tp1+Tg2、Tp1+Tg4、Tp2+Tg2、Tp2+Tg4、Tp4+Tg3 共5 種。

經綜合分析具體碰撞情形處理如表1所示。

表1 碰撞情形處理

2.6 動態整理運行序列

由于碰撞處理是進行運行序列的暫停處理，則會造成運行的不連續，從而影響光纖單元的定位精度［13］，碰撞處理前后運行序列如圖7(a)和圖7(b)所示。因此要把運行序列進行整理，即運行序列整理成兩段式或三段式，如圖7(c)～圖7(e)所示。因為運行序列的調整必然會造成單元運行軌跡的變化，故在調整運行序列時要動態的檢測單元碰撞并處理碰撞，這整個過程即稱為動態整理運行序列。如圖7(f)和圖7(g)所示，單元在運行序列位置n處發生碰撞，在位置n之前暫停10片，然后進行運行序列的整理。

圖7 運行序列整理

3 仿真實驗及結果分析

編寫軟件程序對防碰撞分治標簽算法進行仿真模擬［14］實驗，如圖8所示，這6個模擬實驗快照(圖8(a)～圖8(f))直觀地反映了防碰撞處理的全過程。如圖8(a)所示，單元1、單元2和單元3在起始位置，它們對應的目標星象點分別為1*、2*和3*。如圖8(b)所示，單元1、單元2和單元3正在運行。如圖8(c)所示，單元1的偏心桿與單元3的偏心桿產生碰撞，屬于碰撞情形Tp3+Tg1。如圖8(d)所示，由于單元3已經到達目標位置，為縮短運行時間，故處理單元3的偏心桿規避碰撞，其運行序列也進行動態整理，同時單元1的中心板與單元2的偏心桿產生碰撞，屬于碰撞情形Tp3+Tg1。如圖8(e)所示，此時單元1與單元3的碰撞情形屬于Tp4+Tg1，而單元2已經到達目標位置，為縮短運行時間，故處理單元2的偏心桿與單元3的偏心桿規避碰撞，并動態整理其運行序列。如圖8(f)所示，單元1運行完成時，單元2和單元3也運行完成。

圖8 仿真演示

仿真實驗結果表明單元在處理碰撞時不僅規避碰撞，也動態整理運行序列。單元1、單元2和單元3在處理碰撞前的運行序列如圖9(a)、圖9(c)和圖9(e)所示，處理碰撞后的運行序列如圖9(b)、圖9(d)和圖9(f)所示。結果表明此算法能夠動態整理運行序列成兩段式或三段式。

圖9 處理碰撞前后單元運行序列

4 結束語

本文對光纖單元運行碰撞的問題，利用碰撞現象的特點，以分而治之的策略，將運行碰撞劃分為4個碰撞類型，并對單元進行標簽化處理生成4個碰撞標簽，以及碰撞處理后動態整理運行序列。實驗結果表明，該防碰撞算法不僅能夠有效地規避碰撞，而且保證單元運行連續。