一種多基元類的布局遷移自適應(yīng)算法及在閘機(jī)設(shè)計(jì)中的應(yīng)用*

陳華江，趙翠蓮，范志堅(jiān)，黃松恩，趙 盟

(上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海 200072)

一種多基元類的布局遷移自適應(yīng)算法及在閘機(jī)設(shè)計(jì)中的應(yīng)用*

陳華江，趙翠蓮，范志堅(jiān)，黃松恩，趙 盟

(上海大學(xué)機(jī)電工程與自動(dòng)化學(xué)院，上海 200072)

布局問(wèn)題研究物體的布局先后或布局定位以滿足設(shè)計(jì)要求，布局遷移設(shè)計(jì)是在已有布局基礎(chǔ)上高效設(shè)計(jì)新布局的方法。在軌道交通自動(dòng)控制系統(tǒng)中，閘機(jī)表面?zhèn)鞲衅鞯牟季謱?duì)人與物的識(shí)別有重要的影響。為了實(shí)現(xiàn)閘機(jī)在不同地域環(huán)境中的快速設(shè)計(jì)，首先以閘機(jī)布局中的傳感器作為研究對(duì)象，進(jìn)行基元?jiǎng)澐?，提出了多種基元類型；并分析了基于拓?fù)浣Y(jié)構(gòu)的基元遷移變換方法，研究了人群特征因素、機(jī)械結(jié)構(gòu)約束的數(shù)學(xué)表達(dá)；然后提出基于包圍圓搜索的基元運(yùn)動(dòng)與干涉分析算法，其參數(shù)能夠根據(jù)求解精度進(jìn)行自適應(yīng)調(diào)整；并利用多目標(biāo)歸一化函數(shù)對(duì)各基元的解進(jìn)行擇優(yōu)，以獲取最終布局。最后以18對(duì)傳感器的閘機(jī)布局設(shè)計(jì)為例進(jìn)行實(shí)例分析，應(yīng)用此方法并借助于Visual Basic可視化編譯平臺(tái)，實(shí)現(xiàn)了閘機(jī)在不同地域環(huán)境中的傳感器布局快速設(shè)計(jì)。

布局遷移設(shè)計(jì)；傳感器；基元；包圍圓；自適應(yīng)算法

1 引言

布局問(wèn)題是給定一個(gè)布局空間和若干待布物體，將待布物體按一定的規(guī)則擺放在空間中以滿足必要的約束，并達(dá)到某種最優(yōu)指標(biāo)[1]，其研究的是布局物體的布局先后或布局位置的定位以滿足在空間中放置的物體最多，或空間利用率最大等指標(biāo)。現(xiàn)階段，一些基于遺傳算法、圖論、模擬退火算法的自適應(yīng)算法在布局問(wèn)題中都有一些應(yīng)用[2～4]，這些算法能根據(jù)布局約束與布局目標(biāo)自動(dòng)調(diào)整算法參數(shù)，以提高搜索效率和求解精度。布局求解時(shí)使用 Bottom-Up方式，首先產(chǎn)生初始解，再根據(jù)算法逐步尋優(yōu)，初始解的選擇對(duì)解的質(zhì)量和求解效率影響很大，因而有些學(xué)者專門研究布局初始方案的生成方法[5,6]。在電子設(shè)計(jì)自動(dòng)化EDA(Electronic Design Automation)領(lǐng)域，布局遷移設(shè)計(jì)LMD(Layout Migration Design)是在布局壓縮(Layout Compaction)基礎(chǔ)上發(fā)展起來(lái)的在已有布局基礎(chǔ)上高效設(shè)計(jì)新布局的方法[7]。LMD通過(guò)在初始布局中建立拓?fù)潢P(guān)系，并為拓?fù)洳季痔砑蛹s束，在布局變換中保持物體的拓?fù)浣Y(jié)構(gòu)不變，從而形成新的布局[8]。

在地鐵自動(dòng)售檢票系統(tǒng)中，利用閘機(jī)上布置的傳感器，識(shí)別在通道內(nèi)人攜帶物的位置和行為，從而控制閘門阻擋機(jī)構(gòu)的啟閉，實(shí)現(xiàn)軌道交通進(jìn)出口的自動(dòng)控制。其中，傳感器的布局位置對(duì)系統(tǒng)的識(shí)別效果有著重要的影響[9]，其布局方案受到地域人群特征和閘機(jī)本身結(jié)構(gòu)特征的影響。為了實(shí)現(xiàn)閘機(jī)在不同地域環(huán)境中的快速設(shè)計(jì)，本文受EDA領(lǐng)域中LMD技術(shù)的啟發(fā)，提出了一種利用已有的布局作為原始布局，建立自適應(yīng)算法，將上述影響因素歸納為布局約束，建立目標(biāo)函數(shù)實(shí)現(xiàn)快速布局的布局遷移設(shè)計(jì)優(yōu)化方法，并以18對(duì)傳感器的布局為例進(jìn)行了實(shí)例分析，實(shí)現(xiàn)了閘機(jī)在不同地域環(huán)境中的快速設(shè)計(jì)。

2 基元與布局物體

2.1 布局問(wèn)題

2.2 基元的分類與運(yùn)動(dòng)

鑒于傳感器在閘機(jī)表面的安裝孔位結(jié)構(gòu)，在此將基點(diǎn)抽象成圓，如圖1所示，在平面布局空間建立坐標(biāo)系X-O-Y，基點(diǎn)為si，其中心坐標(biāo)為si(xi,yi)，則常見(jiàn)的平面基元如圖1所示。

Figure 1 Common primitives in flat space圖1 平面空間常見(jiàn)基元示意圖

以基元為載體對(duì)各基元的中心點(diǎn)進(jìn)行坐標(biāo)變換，實(shí)現(xiàn)相應(yīng)基元中各基點(diǎn)的重新布局，可以用式(1)移動(dòng)變換和式(2)、式(3)旋轉(zhuǎn)變換對(duì)其描述：

(1)

(2)

(3)

3 布局空間基元自適應(yīng)算法

3.1 基于平面拓?fù)浣Y(jié)構(gòu)的基元運(yùn)動(dòng)

基元中的基點(diǎn)在保持基元拓?fù)浣Y(jié)構(gòu)的基礎(chǔ)上可以進(jìn)行平面運(yùn)動(dòng)。在閘機(jī)傳感器的布局遷移設(shè)計(jì)問(wèn)題中，受當(dāng)?shù)厝巳禾卣饕蛩赜绊懀謩e體現(xiàn)為身高和體厚因素，前者會(huì)改變傳感器布局設(shè)計(jì)中某些基點(diǎn)的垂直遷移變動(dòng)，后者則影響水平方向的遷移變動(dòng)，需要將這些設(shè)計(jì)影響因素與基元拓?fù)浣Y(jié)構(gòu)加以關(guān)聯(lián)。

(4)

(5)

3.2 基于包圍圓搜索的基元運(yùn)動(dòng)與干涉分析

在布局空間中基元通過(guò)一定方式的運(yùn)動(dòng)來(lái)避開(kāi)布局空間中存在的幾何約束，為此本文提出一種基于包圍圓搜索求解的自適應(yīng)算法，并以圖2為例進(jìn)行算法介紹。

Figure 2 Primitives and constraints圖2 基元與約束

在平面布局空間里有待布局的基元，并存在兩種典型的幾何約束：圓形約束和多邊形約束，后者可以簡(jiǎn)化為多個(gè)三角形約束問(wèn)題。要求基點(diǎn)在做遷移時(shí)與約束不能有位置干涉。為此，首先對(duì)基元中心O(x,y)沿著包圍圓的極坐標(biāo)方向進(jìn)行平移，再繞著基元中心進(jìn)行旋轉(zhuǎn)運(yùn)動(dòng)，并判斷約束干涉，得到布局的可行解。該算法分五個(gè)步驟：

步驟1參數(shù)初始化：包圍圓算法參數(shù)Δr、m、l影響到求解的精度與效率，Δr是包圍圓半徑擴(kuò)大的最小增量，m、l分別是移動(dòng)和旋轉(zhuǎn)時(shí)圓周等分?jǐn)?shù)量，為簡(jiǎn)化模型，參數(shù)l由m進(jìn)行傳遞。Δr與相鄰兩次基元的位移之差(圖3)共同影響精度ε，如下式：

(6)

當(dāng)m≥6時(shí)，2*Δr*sin(π/m)≤Δr≤ε，為提高搜索效率，取初始值l=m=6，Δr=ε。

Figure 3 Schematic diagram of minimun displacement圖3 最小位移示意圖

步驟2構(gòu)造包圍圓：以每個(gè)基元的中心O(x,y)為圓心，構(gòu)造同心包圍圓，半徑分別為i×Δr，i=1,2,…,n-1，i=0為點(diǎn)O。對(duì)半徑為i×Δr的圓的圓弧進(jìn)行m等分，圓弧上得到m個(gè)點(diǎn)，其相對(duì)O(x,y)的坐標(biāo)為(i×Δr×cos(2πj/m)，i×Δr×sin(2πj/m)，j=0,1,2,…,m-1，如圖4所示。

Figure 4 Bounding circle圖4 包圍圓

步驟3平移和旋轉(zhuǎn)：按式(7)進(jìn)行移動(dòng)，其中ψ為相關(guān)的一個(gè)約束中心C與基元中心O的向量與x軸正方向的夾角弧度(0≤ψ<2π)，如圖5所示。當(dāng)基元移到中心為O′(x′,y′)的位置時(shí)，按式(3)進(jìn)行繞基元中心的旋轉(zhuǎn)運(yùn)動(dòng)，以調(diào)整基元上基點(diǎn)的位置，將圓周l等分，由公式(8)得旋轉(zhuǎn)弧度θ，如圖6所示，式(9)為平移和旋轉(zhuǎn)總公式，即可解出P′；

(7)

(8)

(9)

Figure 5 Vector angle in radians ψ圖5 向量角弧度ψ

Figure 6 Primitive rotation in radians θ圖6 基元旋轉(zhuǎn)弧度θ

步驟4干涉判斷：經(jīng)過(guò)步驟3，得到了基元中各基點(diǎn)新的中心坐標(biāo)，根據(jù)基點(diǎn)形狀特征，反求出邊界坐標(biāo)方程，并判斷與約束的關(guān)系，如果還在約束內(nèi)，則重復(fù)執(zhí)行步驟2和步驟3，若在約束外，則輸出一組可行解。

圓類約束的干涉判斷如圖7所示，如果:

(10)

則基點(diǎn)在約束外，反之，則基點(diǎn)在約束內(nèi)。

Figure 7 Schematic diagram of circle class constraint judgement圖7 圓類約束判斷示意圖

以三角形為基礎(chǔ)的多邊形類約束判斷如圖8所示，D(x,y)是邊界點(diǎn)，

(11)

Figure 8 Schematic diagram of polygon class constraint judgement圖8 多邊形類約束判斷示意圖

如果θ∈[0,2π)時(shí)，

(12)

則基點(diǎn)在約束外，否則基點(diǎn)在約束內(nèi)。

步驟5步驟1中的參數(shù)進(jìn)行自適應(yīng)調(diào)整：精度要求為ε時(shí)，如果參數(shù)在初始值狀態(tài)下得不到可行解，則m、l自增，Δr自減，重復(fù)執(zhí)行步驟2～步驟5，直至得到可行解。

3.3 基于包圍圓自適應(yīng)算法的遷移布局目標(biāo)函數(shù)

通過(guò)上述計(jì)算，分別可以得到圖2中直線基元和三角形基元的多組可行解，為此考慮與初始布局最吻合的最小距離算法以及布局空間面積最小算法，提出歸一化的目標(biāo)函數(shù)。

(1)與初始布局最吻合。

(13)

(2)各基元組成的面積最小[10]。

(14)

設(shè)點(diǎn)p1(x1,y1)、p2(x2,y2)、…、pn(xn,yn)依次構(gòu)成首尾相接的凸多邊形，則：

(15)

歸一化處理之后目標(biāo)函數(shù)為：

(16)

其中,λ1、λ2為加權(quán)因子，需要根據(jù)工程實(shí)際中的側(cè)重程度來(lái)確定，其關(guān)系式為：

(17)

Z1j、Z2j為取第j組解時(shí)各自的取值。

4 算法應(yīng)用

閘機(jī)傳感器利用光電傳感器作為測(cè)量信號(hào)的元器件，探測(cè)乘客進(jìn)入通道、識(shí)別出行李與乘客以及判斷乘客離安全區(qū)的距離、保護(hù)乘客在安全區(qū)的安全通行、檢測(cè)乘客離開(kāi)通道，以及檢測(cè)乘客是否有反向闖入通道內(nèi)部等，布局區(qū)域依次可分為進(jìn)入?yún)^(qū)、檢測(cè)區(qū)、安全區(qū)、監(jiān)測(cè)區(qū)、出行區(qū)。常用的傳感器對(duì)數(shù)有16對(duì)、18對(duì)、19對(duì)等，其中18對(duì)傳感器式的分布特點(diǎn)為沿閘門阻擋機(jī)構(gòu)中心軸對(duì)稱，容易實(shí)現(xiàn)雙向通行的判斷，被某廠商在國(guó)外得到成熟的應(yīng)用，即原有布局及其通行控制算法充分考慮了人群特征及行為的復(fù)雜性，但是在引進(jìn)到國(guó)內(nèi)時(shí)需要根據(jù)當(dāng)?shù)厍闆r重新進(jìn)行布局設(shè)計(jì)。

4.1 傳感器布局基元?jiǎng)澐?/p>

閘機(jī)傳感器布局是基于人體的關(guān)鍵特征位置如膝蓋、腰部、腳踝等而布局的。將18對(duì)傳感器根據(jù)人群特征映射劃分成10對(duì)基元，如圖9所示，s1與s2構(gòu)成橫線基元j1，s3、s4、s5構(gòu)成三角形基元j2，s7、s8構(gòu)成豎線基元j3，s6、s9為點(diǎn)基元j4、j5，s10,s11,…,s18分別是s1,s2,…,s9關(guān)于閘機(jī)中心y軸對(duì)稱的傳感器，則相應(yīng)的對(duì)稱基元有j6、j7、j8、j9、j10。

Figure 9 Primitive of gate sensor partition圖9 閘機(jī)傳感器基元?jiǎng)澐謭D

4.2 基于VB的基元及設(shè)計(jì)約束表達(dá)

Visual Basic[11]具有可視化的用戶界面設(shè)計(jì)功能，利用VB作為求解平臺(tái)，可以將布局物體和約束在VB的界面中直觀地表達(dá)出來(lái)。

根據(jù)文獻(xiàn)[9]，在通行算法的約束下，新布局與原始布局在水平方向上的傳感器依次順序保持一致，由此可以推斷出應(yīng)用算法搜索解時(shí)對(duì)各基元只做移動(dòng)，不涉及旋轉(zhuǎn)。圖10是原始布局在VB中的示意圖，對(duì)左側(cè)布局物體矩陣進(jìn)行直線基元和三角形基元表達(dá)：

此外，對(duì)稱基元：xi+9=-xi、yi+9=yi(i=1,2,…,9)；點(diǎn)基元：x2

Figure 10 Schematic diagram of original layout圖10 原始布局示意圖

Figure 11 Constraints of gate mechanical structure圖11 閘機(jī)機(jī)械結(jié)構(gòu)約束

將布局物體即傳感器抽象成半徑為r1=5mm的圓，構(gòu)成動(dòng)態(tài)幾何約束；阻擋機(jī)構(gòu)的位置、閘機(jī)四周邊緣、立柱等位置不能放置傳感器，構(gòu)成靜態(tài)幾何約束，如圖11中約束1～約束9所示，傳感器在這些約束處需要讓位。以添加約束1和約束5為例的方法分別添加這些約束，并利用VB圖片框的繪圖方法在VB編譯界面中直觀地表達(dá)這些約束：

(1)圓類約束：VB的圓類表達(dá)為Picture1.Circle(X,Y),r,blue,a,b,ξ。其中，(x,y)為圓類中心坐標(biāo)，r為半徑，a與b為弧的起止點(diǎn)(缺省時(shí)為圓/橢圓)，ξ為縱橫比(缺省值為1，即圓)，約束1為橢圓弧，其約束形式為傳感器在此約束的下方，當(dāng)X-r

(2)三角形類約束：任何一個(gè)n邊形都可以看成是由n-2個(gè)彼此相鄰的三角形組成，而三角形是由三條邊首尾相接而成，VB直線表達(dá)為：Picture1.Line(x1,y1)-(x2,y2)。(x1,y1)與(x2,y2)分別為直線的起點(diǎn)和終點(diǎn)。約束5為矩形，其約束形式為傳感器在此約束的外面，則：xi+r1X2或yi+r1Y2，在本文所應(yīng)用的閘機(jī)中，X1=-28,X2=28,Y1=300,Y2=800。

4.3 基于VB的遷移布局求解

首先將人群特征作為一種布局遷移設(shè)計(jì)的驅(qū)動(dòng)作用于原始布局，使得與人群特征相關(guān)的傳感器按3.1節(jié)進(jìn)行基元運(yùn)動(dòng)。與身高相關(guān)的基元有j1、j2、j4及與之左右對(duì)稱的基元j6、j7、j9。中國(guó)成年男女平均身高[12]分別為169.7cm、160.1cm，某國(guó)的為180.2cm、170.1cm，則式(4)中的a取0.94。兩地域的人體體厚有差異，但由于考慮氣候原因衣服厚度的修正量不同，其存在很多不確定性，本文不考慮體厚因素對(duì)遷移變換的影響，故b=0，只考慮身高因素。根據(jù)式(4)對(duì)這些基元的基點(diǎn)做運(yùn)動(dòng)變換。結(jié)果如下：

然后，將閘機(jī)機(jī)械結(jié)構(gòu)包括閘機(jī)的外型、支撐部件，閘門阻擋機(jī)構(gòu)等因素作為空間幾何約束，其表達(dá)為4.2節(jié)中的約束1～約束9，在對(duì)各基元進(jìn)行包圍圓搜索運(yùn)動(dòng)時(shí)進(jìn)行干涉檢查。

由于人群特征的復(fù)雜性，使得傳感器在定位時(shí)在保證算法精度前提下在一定范圍內(nèi)是可以浮動(dòng)的。當(dāng)精度ε=1時(shí)，初始值Δr=1，m=6，由于基元不做旋轉(zhuǎn)運(yùn)動(dòng)，l取值無(wú)意義，求各布局物體圍成的面積優(yōu)化指標(biāo)可以用以j1、j2、j3、j5四個(gè)基元的中心點(diǎn)圍成的凸四邊形面積來(lái)等價(jià)，則式(16)中，根據(jù)工程實(shí)踐經(jīng)驗(yàn)，取λ1=0.4，λ2=0.6。得到14組可行解，其中第四組為最優(yōu)解，式(16)中，目標(biāo)值Z=0.32，如圖12所示；此時(shí)基元j1、j2、j3、j4、j5中心坐標(biāo)分別為(-727,827)、(-362,735)、(-80,429)、(-352,390)、(-571,200)，得到的最優(yōu)布局如圖13所示，其左側(cè)布局物體矩陣為：

Figure 12 Object function value圖12 目標(biāo)函數(shù)值

Figure 13 New layout chematic diagram圖13 新布局示意圖

5 結(jié)束語(yǔ)

本文提出了一種多基元類的布局遷移自適應(yīng)算法，并在地鐵閘機(jī)傳感器布局方案設(shè)計(jì)中得到了應(yīng)用。以基元為基本獨(dú)立單位做布局的調(diào)整，既保持了拓?fù)潢P(guān)系，又降低了布局復(fù)雜度。參數(shù)Δr、m、l與求解精度或求解效率相關(guān)，會(huì)隨著求解過(guò)程進(jìn)行自適應(yīng)性調(diào)整，ψ確保包圍圓算法的搜索是從約束中心與基元中心的矢量方向開(kāi)始，能提高搜索的有效性。但是，本文未考慮存在某些基點(diǎn)同時(shí)屬于多個(gè)基元的拓?fù)浼s束現(xiàn)象，這會(huì)對(duì)基元的運(yùn)動(dòng)以及多個(gè)基元的尋優(yōu)形成新的問(wèn)題。另外，利用本文提出的算法雖然求得了最優(yōu)布局解，但如果要將閘機(jī)傳感器布局應(yīng)用于實(shí)際工程中，進(jìn)一步的三維仿真與樣機(jī)測(cè)試是必要的。

[1]ZhaJian-zhong,TangXiao-jun,LuYi-ping.Surveyonpackingproblems[J].JournalofComputer-AidedDesign&ComputerGraphics, 2002,14(8):705-712.(inChinese)

[2]YuShi-gen,LuJian-xia.Studyonfacilitylayoutproblemofmulti-objective,fixedconstraintbasedonGA[J].JournalofZhejiangUniversityofTechnology, 2010,38(4):401-405.(inChinese)

[3]FrickA,LudwigA,MehldauH.Afastadaptivelayoutalgorithmforundirectedgraphs[C]∥ProcoftheDIMACSInternationalWorkshoponGraphDrawing, 1994:388-403.

[4]FanXiao-ning,LinYan,JiZhuo-shang.Approachofshippipepathsroutingoptimizationbasedonadaptiveannealinggeneticalgorithm[J].JournalofDalianUniversityofTechnology, 2007,47(2):215-221.(inChinese)

[5]LuYi-ping,ZhaJian-zhong,LiJian-yong,etal.Patterngenerationandsolutionoflayoutproblembasedonneighboringminimumsearching[J].JournalofNorthernJiaotongUniversity, 2000,24(4):52-56.(inChinese)

[6]TengHong-fei,SunShou-lin.Turntheroundtablebalanceplateontherotatingtable-packingproblemofdrivingthebalancedperformanceconstraints[J].ScienceinChina(ASeries), 1994,24(7):755-760.(inChinese)

[7]ChinHsiungHsu,YaoWenChang,NassifSR.Simultaneouslayoutmigrationanddecompositionfordoublepatterningtechnology[J].Journals&Magazines, 2011,30(2):284-294.

[8]FuDS,ChaungYZ,LinYH,etal.Topology-drivencelllayoutmigrationwithcollinearconstraints[C]∥ProcofIEEEInternationalConferenceonComputerDesign(ICCD2009),2009:439-444.

[9]CaiYi-long.Logicaldesignandimplementationofsubwaystationaccessdoorticketmachine[D].Shanghai:ShanghaiUniversity,2012.(inChinese)

[10]HengFL,ChenZhan,TellezGE.AVLSIartworklegalizationtechniquebasedonanewcriterionofminimumlayoutperturbation[C]∥ProcofInternationalSymposiumonPhysicalDesign, 1997:116-121.

[11]ZhangShu-bing,DaiHong,ChenZhe.VisualBasic6.0entryandimprove[M].Beijing:TsinghuaUniversityPress, 1999.(inChinese)

[12]GB/T10000-1998.HumandimensionsofChineseadults[S].Beijing:GeneralAdministrationofQualitySupervision,InspectionandQuarantineofthePeople’sRepublicofChina,1988.(inChinese)

附中文參考文獻(xiàn):

[1] 查建中,唐曉君,陸一平.布局及布置設(shè)計(jì)問(wèn)題求解自動(dòng)化的理論與方法綜述[J].計(jì)算機(jī)輔助設(shè)計(jì)與圖形學(xué)學(xué)報(bào), 2002,14(8):705-712.

[2] 余世根,魯建廈.基于GA的固定約束條件下多目標(biāo)車間設(shè)備布局問(wèn)題研究[J].浙江工業(yè)大學(xué)學(xué)報(bào), 2010,38(4):401-405.

[4] 范小寧,林焰,紀(jì)卓尚.基于自適應(yīng)退火遺傳算法的船舶管路布局優(yōu)化方法[J].大連理工大學(xué)學(xué)報(bào),2007,47(2):215-221.

[5] 陸一平,查建中,李建勇,等.一種基于鄰接極小搜索的布局模式生成方法[J].北方交通大學(xué)學(xué)報(bào),2000,24(4):52-56.

[6] 滕弘飛,孫守林,葛文海.轉(zhuǎn)動(dòng)圓桌平衡擺盤—帶動(dòng)平衡性能約束的Packing問(wèn)題[J].中國(guó)科學(xué)(A輯),1994,24(7):755-760.

[9] 柴益龍.地鐵車站門式檢票機(jī)的通行邏輯設(shè)計(jì)及其實(shí)現(xiàn)[D].上海：上海大學(xué),2012.

[11] 張樹(shù)兵,戴紅,陳哲.VisualBasic6.0入門與提高[M].北京:清華大學(xué)出版社,1999.

[12]GB10000-88.中國(guó)成年人人體尺寸[S].北京：國(guó)家技術(shù)監(jiān)督局，1988.

CHENHua-jiang,born in 1987,MS,his research interests include CIMS & process layout.

趙翠蓮(1963-),女,上海人，博士，教授，研究方向?yàn)閿?shù)字化測(cè)量和生機(jī)電工程。E-mail:clzhao@shu.edu.cn

ZHAOCui-lian,born in 1963,PhD,professor,her research interests include digital measurement，and bio-mechatronics engineering.

范志堅(jiān)(1982-),男,山西臨汾人，碩士，工程師，研究方向?yàn)闄C(jī)電一體化。E-mail:chris2813@shu.edu.cn

FANZhi-jian,born in 1982,MS,engineer,his research interest includes mechatronics.

Anadaptivealgorithmformulti-primitiveslayoutmigrationanditsapplicationingatedesign

CHEN Hua-jiang,ZHAO Cui-lian,FAN Zhi-jian,HUANG Song-en,ZHAO Meng

(School of Mechatronic Engineering and Automation,Shanghai University,Shanghai 200072,China)

Layout problem is regarding the study on the arrangement of the order and position of the objects according to the design requirements, while layout migration design is a new and efficient layout method based on the existing layout. In the automatic control system of rail transportation, the sensor layout of the auto gate plays an important role in the identification of human body and objects. In order to achieve the rapid design of auto gate for different geographical environments, firstly, sensors in auto gate layout are taken as the research object and broken down into various kinds of primitives, multiple primitive types are proposed, the topological-structure-based primitive migration transformation method is analyzed, and the crowd characteristics factors and the mathematical expression of the mechanical structure constraints are studied. Secondly, the primitive motions and interference analysis algorithm based on the bounding circle search is proposed, whose parameters can be adjusted according to the solution precision, and multi-objective normalization function is utilized to search for the optimum solution out of all the feasible solutions for each primitive. Finally, with the help of the visualization compile platform Visual Basic, the method is applied to the sensor layout design for the auto gate with eighteen-pair sensors and fast sensor layout design of auto gate for different geographical environment is achieved.

layout migration design;sensor;primitive;bounding circle;adaptive algorithm

1007-130X(2014)05-0929-07

2012-12-05;

：2013-04-13

TP399

：A

10.3969/j.issn.1007-130X.2014.05.024

陳華江(1987-),男,浙江上虞人，碩士，研究方向?yàn)镃IMS與工藝布局。E-mail:chjchj120@163.com

通信地址：312300 浙江省紹興市上虞區(qū)人民西路1801號(hào)

Address:1801 Renmin Rd West,Shangyu District,Shaoxing 312300,Zhejiang,P.R.China