一種三臂鑿巖臺(tái)車孔序規(guī)劃

吳萬榮， 殷建坤

（中南大學(xué) 機(jī)電工程學(xué)院，湖南 長沙 410083）

三臂鑿巖臺(tái)車適用于隧道及地下大斷面工程采用鉆爆破的鉆孔施工作業(yè)，臺(tái)車鉆孔孔位根據(jù)爆破需要按一定規(guī)律隨機(jī)離散分布在隧道斷面上。鉆臂之間運(yùn)動(dòng)和控制相互獨(dú)立，每一個(gè)鉆臂可獨(dú)立完成鑿巖鉆孔任務(wù)，工作斷面上所有鉆孔任務(wù)是由3個(gè)鉆臂共同協(xié)作完成［1］，鉆孔順序是隨機(jī)的。對(duì)于多臂鑿巖臺(tái)車解決孔序規(guī)劃時(shí)，一般將單個(gè)鉆臂的作業(yè)孔序規(guī)劃看成獨(dú)立的TSP問題，多臂鑿巖臺(tái)車孔序規(guī)劃即為N－TSP問題［2］。三臂鑿巖臺(tái)車工作覆蓋面積由2部分組成，即單臂覆蓋區(qū)域及兩臂甚至三臂覆蓋區(qū)域。根據(jù)三臂鑿巖臺(tái)車作業(yè)覆蓋面積和鉆臂運(yùn)動(dòng)特點(diǎn)，考慮到鉆臂之間的干涉，將作業(yè)區(qū)域合理劃分，每個(gè)區(qū)域作業(yè)孔位基本相同，運(yùn)用自適應(yīng)遺傳算法對(duì)3塊作業(yè)區(qū)域分別進(jìn)行孔序計(jì)算［3］。

1 三臂鑿巖臺(tái)車孔序規(guī)劃的模型建立

三臂鑿巖臺(tái)車每個(gè)鉆臂有6個(gè)轉(zhuǎn)動(dòng)自由度和3個(gè)移動(dòng)自由度，左右鉆臂底座還各有2個(gè)移動(dòng)自由度，在每個(gè)作業(yè)斷面上每個(gè)鉆臂要完成幾十甚至上百個(gè)鉆孔任務(wù)，進(jìn)行鉆孔作業(yè)時(shí)，三臂必須協(xié)調(diào)時(shí)間關(guān)系和空間關(guān)系，保證鉆臂之間不發(fā)生干涉，能夠最大限度地提高鉆孔工作效率［4］。

三臂鑿巖臺(tái)車工作區(qū)域示意，如圖1所示。

由圖1可以看出，鑿巖臺(tái)車工作區(qū)域由6部分組成，第1部分只有左邊鉆臂可以覆蓋，第2部分由左邊鉆臂和中間鉆臂共同覆蓋，第3部分由3個(gè)鉆臂共同覆蓋，第4部分由左邊鉆臂和右邊鉆臂共同覆蓋，第5部分由中間鉆臂和右邊鉆臂共同覆蓋，第6部分只有右邊鉆臂可以覆蓋。

圖1 三鉆臂工作區(qū)域

鑿巖臺(tái)車工作區(qū)域是個(gè)軸對(duì)稱區(qū)域，而且左、右各有一部分區(qū)域只有1個(gè)鉆臂可以工作，考慮到鉆臂之間任務(wù)的均衡和工作時(shí)可能發(fā)生干涉，將鉆孔區(qū)域分成A、B、C、D、E區(qū)，如圖2所示。

圖2 協(xié)作工作空間

A、B、C區(qū)分別由左臂、中臂和右臂獨(dú)立完成鉆孔任務(wù)，而D和E區(qū)是協(xié)作區(qū)域，根據(jù)每個(gè)鉆臂任務(wù)進(jìn)展，合理地分配D、E區(qū)域的鉆孔任務(wù)。在單臂的孔序計(jì)算中，協(xié)作區(qū)域內(nèi)的所有孔都計(jì)算在內(nèi)，根據(jù)實(shí)際工作情況選擇跳過或鉆孔，這樣既可以避免鉆臂間的干涉，也可以均衡鉆臂任務(wù)，使每個(gè)鉆臂鉆孔數(shù)量盡量相等，臺(tái)車工作效率達(dá)到最大化。在3個(gè)鉆臂都能正常工作的條件下，為保證鉆臂之間不發(fā)生干涉，規(guī)定同時(shí)間只有1個(gè)鉆臂在協(xié)作區(qū)域內(nèi)工作，獨(dú)立的工作區(qū)域內(nèi)其他鉆臂不參與鉆孔。

2 TSP問題數(shù)學(xué)模型建立

假設(shè)G＝（V，E）為賦權(quán)圖，V＝｛1，2，…，n｝為頂點(diǎn)集，E為邊集，各頂點(diǎn)間的距離為cij，已知cij＞0，i，j∈V。TSP問題就是求出通過所有頂點(diǎn)，且每個(gè)頂點(diǎn)只通過1次的最短距離，在本實(shí)例中就是尋找一條最短的遍歷n個(gè)工作孔位的路徑。以鉆架末端移動(dòng)距離為優(yōu)化函數(shù)建立數(shù)學(xué)模型，即

則TSP問題可建立如下線性規(guī)劃：

其中，K是V的所有非空子集；｜K｜是集合K中所有包含圖G的頂點(diǎn)個(gè)數(shù)。

第1個(gè)和第2個(gè)約束條件旨在限制每個(gè)頂點(diǎn)只有1條邊進(jìn)1條邊出，第3個(gè)約束條件限制了子回路的產(chǎn)生［5－6］。

3 TSP問題的遺傳算法求解與實(shí)例應(yīng)用

對(duì)于n個(gè)工位的鉆孔孔序可能的路徑就有（n－1）！個(gè)。當(dāng)n比較小時(shí)，可以得到最短的路徑，當(dāng)n逐漸增大，組合路徑數(shù)目成指數(shù)級(jí)規(guī)律急劇增長，以致無法計(jì)算求得精確解。目前針對(duì)目標(biāo)TSP問題多采用近似解法，常用的方法有神經(jīng)網(wǎng)絡(luò)法、模擬退火法、最小生成樹法和遺傳算法等。遺傳算法是近些年發(fā)展起來的一種可全局優(yōu)化的算法，通過選擇、遺傳和變異等作用機(jī)理，不斷地提高個(gè)體適應(yīng)度，最終得到一個(gè)滿意的個(gè)體，即TSP問題的近似最優(yōu)解［7］。

3.1 算法設(shè)計(jì)

標(biāo)準(zhǔn)的遺傳算法包括初始種群的產(chǎn)生、選擇、交叉和變異。算法流程如圖3所示。

圖3 算法流程

本例中采用自適應(yīng)遺傳算法，適應(yīng)值高的選擇小的交叉和變異概率，適應(yīng)值低的選擇大的交叉和變異概率。這樣既可以保護(hù)優(yōu)良個(gè)體，又可以迅速淘汰差的個(gè)體。

應(yīng)用遺傳算法求解問題，遺傳基因的編碼是十分重要的一個(gè)環(huán)節(jié)，編碼遺傳基因應(yīng)考慮到是否有利于交叉和變異操作。

在本例求解孔序的TSP問題中，用最簡單、自然的孔序表示編碼方式。

3.2 適應(yīng)度函數(shù)

在遺傳算法中產(chǎn)生的每一個(gè)種群個(gè)體，任一個(gè)體的孔序序列s＝（v1，v2，…，vn），這個(gè)序列相鄰孔位之間距離之和的倒數(shù)為適應(yīng)度函數(shù)，即

個(gè)體的適應(yīng)度函數(shù)值越大，其存活下來的幾率越大。

3.3 選擇、交叉及變異操作

根據(jù)個(gè)體適應(yīng)值的大小選擇操作，即從起點(diǎn)到終點(diǎn)的總路徑長度越短，被選中的概率越大。被選中的就有機(jī)會(huì)產(chǎn)生子代個(gè)體。為了保證每一代個(gè)體中最優(yōu)的個(gè)體不被破壞，采用精英選擇策略，使最優(yōu)個(gè)體直接復(fù)制到下一代。

交叉操作直接關(guān)系到種群的收斂速度和最優(yōu)解的得到。在自適應(yīng)遺傳算法中，交叉概率pc與種群個(gè)體適應(yīng)度函數(shù)值有關(guān)。

其中，fmax是種群中最大個(gè)體的適應(yīng)度值；f′是要交叉的2個(gè)個(gè)體中較大的適應(yīng)值；favg是種群個(gè)體的平均適應(yīng)值；f是要交叉或變異個(gè)體的適應(yīng)值；pc1、pc2為常數(shù)，一般取值pc1＝0.9，pc2＝0.6。

變異操作有交換變異、插入變異和倒位變異，3種變異方法中只有倒位變異考慮到了邊的銜接關(guān)系，TSP算法編程采用倒位變異，這樣有利于較好的優(yōu)良性能遺傳到下一代，且可以提高尋優(yōu)速度［7－11］。變異概率與種群個(gè)體適應(yīng)值有關(guān)，根據(jù)種群個(gè)體適應(yīng)值大小選擇合理的變異概率，即

3.4 實(shí)例應(yīng)用

本例中在鉆機(jī)工作區(qū)域內(nèi)隨機(jī)產(chǎn)生90個(gè)工位，利用Matlab進(jìn)行自適應(yīng)遺傳算法編程，分別對(duì)左邊鉆臂、中間鉆臂和右邊鉆臂進(jìn)行孔序優(yōu)化，結(jié)果如圖4、圖5所示。

圖4 尋優(yōu)最優(yōu)路徑

圖5 尋優(yōu)過程

4 結(jié)束語

本文提出了一種三臂鑿巖臺(tái)車的孔序規(guī)劃算法，結(jié)合三臂鑿巖臺(tái)車本身的工作特點(diǎn)，合理地劃分臺(tái)車工作區(qū)域，然后將每塊工作工位利用改進(jìn)遺傳算法，求解出一個(gè)比較理想的鉆孔孔序，而且該算法有很大靈活性，可根據(jù)不同工況不同工位，迅速有效地規(guī)劃鉆孔工位。

［1］周友行.基于個(gè)體的雙機(jī)械手離散隨機(jī)合作任務(wù)規(guī)劃算法研究［J］.湘潭大學(xué)學(xué)報(bào)：自然科學(xué)版2006，28（1）：84－88.

［2］周友行，何清華.雙臂鑿巖機(jī)器人離散任務(wù)規(guī)劃［J］.中國機(jī)械工程，2006，17（13）：1334－1337.

［3］張 穎，吳成東，原寶龍.機(jī)器人路徑規(guī)劃技術(shù)的研究現(xiàn)狀與展望［J］.控制工程，2003，10（5）：152－155.

［4］周友行.鑿巖機(jī)器人孔序規(guī)劃的研究與實(shí)現(xiàn)［D］.長沙：中南大學(xué)，2003.

［5］Dubowsky S，Blubaugh T D.Planning time－optimal robotic manipulator motions and work places for point－to－point tasks［J］.IEEE Transaction on Robotics and Automation，1998，5（3）：377－381.

［6］Laporte G.The TSP：an overview of exact and approximate algorithm ［J］.European Journal of Operation Research，1992，59（1）：231－247.

［7］李 春，葛茂根，張銘鑫，等.遺傳粒子群算法的動(dòng)態(tài)計(jì)劃與排程問題研究［J］.合肥工業(yè)大學(xué)學(xué)報(bào)：自然科學(xué)版，2010，33（1）：5－9.

［8］李敏強(qiáng).遺傳算法的基本理論與應(yīng)用［M］.北京：科學(xué)出版社，2000：42－54.

［9］玄光男，程潤偉.遺傳算法與工程優(yōu)化［M］.北京：清華大學(xué)出版社，2004：2－30.

［10］Reinelt G.The traveling salesman：computational solutions for TSP applications［M］／／Lecture Notes in Computer Science.Berlin：Springer－Verlag，1994：23－31.

［11］高經(jīng)緯，張 煦，李 峰，等.求解TSP問題的遺傳算法實(shí)現(xiàn)［J］.計(jì)算機(jī)時(shí)代，2004（2）：19－21.