基于人機交互改進A*算法的路徑規(guī)劃研究*

李思良，袁慶霓，胡 淶,黃 鑫，潘珠峰

(1.貴州大學(xué) 現(xiàn)代制造技術(shù)教育部重點實驗室，貴陽 550025；2.臺灣清華大學(xué) 資訊工程學(xué)系,臺灣 新竹 30013)

0 引言

隨著大規(guī)模工業(yè)化生產(chǎn)的興起，數(shù)字化裝配技術(shù)即虛擬裝配技術(shù)越來越多的應(yīng)用于實際工業(yè)生產(chǎn)。路徑規(guī)劃作為虛擬裝配技術(shù)的核心，是指以計算機技術(shù)、仿真技術(shù)和信息技術(shù)為支撐，在裝配體模型建立和裝配序列規(guī)劃的基礎(chǔ)上，利用裝配約束信息進行裝配路徑的求解、判斷與分析，并最終生成一條無干涉且最優(yōu)的裝配路徑。國內(nèi)外采用的裝配路徑規(guī)劃方法主要可以分為兩種：一種是通過裝配元件間的配合關(guān)系和裝配順序自動計算生成裝配路徑；另一種是通過人機交互的方式來規(guī)劃裝配路徑。目前，虛擬裝配路徑規(guī)劃的主流是對路徑自動規(guī)劃與自動搜索的研究，王光慧等[1]對傳統(tǒng)遺傳算法中變異算子和雜交算子進行了改進，從而提高了算法精確度；張會麗[2]提出了RC*算法，通過隨機選取后繼節(jié)點解決了單項搜索局部最優(yōu)問題；馮國強等[3]通過A*算法與蟻群算法的結(jié)合，實現(xiàn)了局部環(huán)境中障礙的規(guī)避，并加快了算法全局收斂速度。Mohammad Saiedur Rahaman[4]提出了一種考慮路徑可訪問性的多目標A*算法，豐富了用戶可選擇路徑范圍；KUROSAKA Tsubasa等[5]提出了一種改變局部采樣概率進行避障的RRT路徑規(guī)劃算法等。其中針對靜態(tài)路網(wǎng)問題求解最優(yōu)路徑的A*算法憑借其簡單、快速、效率高的特點，被越來越多的研究人員所認同并采用。但是，A*算法大多數(shù)還是應(yīng)用于單層次裝配的情況下，對于如何應(yīng)用于多層次裝配并沒有進行深入研究及分析。本文通過改進A*算法與人機交互方法的結(jié)合，提出了基于人機交互的改進A*算法，算法成功解決了多層次裝配體的裝配路徑規(guī)劃問題。

1 問題描述

在工業(yè)生產(chǎn)中，對復(fù)雜裝配體進行虛擬裝配路徑規(guī)劃是對裝配體零部件運用路徑規(guī)劃方法，從而避開環(huán)境中的障礙零部件，并最終將裝配體零部件無干涉且路徑最優(yōu)地裝配起來。構(gòu)建虛擬裝配環(huán)境示意圖如圖1所示。

圖1 虛擬裝配環(huán)境示意圖

根據(jù)圖1所示，其中零件1、2、3、4、5、6、7、8組成待裝配的裝配體，且陰影區(qū)域為障礙零部件。針對虛擬裝配路徑規(guī)劃問題，根據(jù)“可拆即可裝”原則，將裝配路徑規(guī)劃問題轉(zhuǎn)化為拆卸路徑規(guī)劃問題，即若在圖1中無干涉地規(guī)劃出等待裝配的裝配體的最優(yōu)拆卸路徑，即得到了裝配體的最優(yōu)裝配路徑。但在實際工業(yè)生產(chǎn)中，當?shù)却b配的裝配體零部件結(jié)構(gòu)復(fù)雜時，若采用傳統(tǒng)裝配路徑規(guī)劃方法對裝配體進行路徑規(guī)劃會出現(xiàn)組合爆炸的問題。

組合爆炸問題是當一個系統(tǒng)擁有兩個以上的有限個子系統(tǒng)時，多個子系統(tǒng)信息相互干擾影響可以構(gòu)成不同類別的大系統(tǒng)，且構(gòu)成的大系統(tǒng)數(shù)量遠遠超過子系統(tǒng)數(shù)量。針對裝配路徑規(guī)劃問題，當裝配體結(jié)構(gòu)復(fù)雜時，若運用傳統(tǒng)路徑規(guī)劃算法對裝配體進行路徑規(guī)劃，會導(dǎo)致算法計算復(fù)雜性過高，從而出現(xiàn)組合爆炸問題，嚴重影響裝配體路徑規(guī)劃效率。

2 改進A*算法

針對裝配體路徑規(guī)劃問題，在傳統(tǒng)A*算法的基礎(chǔ)上提出改進A*算法。算法對零部件進行了一次大跨步移出場景包圍盒的嘗試，并引入了干涉威脅概率、平滑度代價、權(quán)重系數(shù)等參數(shù)。改進A*算法實現(xiàn)了不同側(cè)重方向的最優(yōu)路徑尋找，豐富了路徑規(guī)劃多樣性，提升了算法效率。

2.1 A*算法

A*(A-mStar)算法是一種在Dijkstra’s方法基礎(chǔ)上提出的啟發(fā)式智能搜索算法，被廣泛應(yīng)用于靜態(tài)路網(wǎng)中最優(yōu)路徑求解問題。該算法在路徑搜索中引入了估值函數(shù)，并通過估值函數(shù)提前計算節(jié)點與目標終點之間的代價值，并以此判斷節(jié)點是否屬于最優(yōu)路徑節(jié)點，且優(yōu)先選擇最優(yōu)估值函數(shù)節(jié)點為下一路徑節(jié)點。最終，通過重復(fù)這一過程直至節(jié)點到達目標終點，以此來確保得到的路徑為最優(yōu)規(guī)劃路徑。A*算法在路徑規(guī)劃問題中啟發(fā)函數(shù)的代價權(quán)值為距離，同時距離的估計采用歐氏距離。

在A*算法中，對給定的起始點s(xs，ys)和目標終點e(xe，ye)，且n(xn，yn)為搜尋過程中的某個節(jié)點，A*算法的估值函數(shù)為：

f(n)=g(n,s)+h(n,e)

(1)

其中，f(n)為起始點s與目標終點e的全局估計代價函數(shù)；g(n,s)為起始點s到節(jié)點n的實際花費代價函數(shù)；h(n,e)為啟發(fā)項，是當前節(jié)點n到目標終點e的預(yù)估代價函數(shù)。其中:

(2)

d(t)為相鄰兩節(jié)點間的距離。

(3)

2.2 改進A*算法

在傳統(tǒng)A*算法基礎(chǔ)上引入干涉威脅概率、平滑度代價與權(quán)重系數(shù)參數(shù)，令:

g(n,s)=g(n-1)+dne(n,n-1)+P(n)+C(n)

(4)

(5)

其中，dne(n,n-1)為當前節(jié)點與上一節(jié)點間的距離；P(n)為起始點s到當前節(jié)點n的干涉威脅概率；C(n)為路徑平滑度代價；式(5)中，Pne(n)為當前節(jié)點n到目標終點e的干涉威脅概率；Lne(n)為當前節(jié)點n到目標終點e的路徑長度代價；ω1,ω2,ω3分別為Pne(n),Lne(n) ,C(n)的權(quán)重系數(shù)。

改進A*算法通過調(diào)節(jié)權(quán)重系數(shù)，可實現(xiàn)不同側(cè)重方向的規(guī)劃路徑選擇。當裝配體需要選擇一條干涉威脅最少的路徑時，則設(shè)置ω1較大，這樣規(guī)劃出的路徑使得裝配體面臨的干涉威脅最??；當需要保證規(guī)劃出的路徑距離最短時，則設(shè)置ω2較大，這樣規(guī)劃出的路徑距離最短；當需要規(guī)劃出平滑度更高的路徑時，則加大ω3權(quán)重，這樣規(guī)劃出的路徑曲線平滑度更高。同時，考慮到對裝配體路徑規(guī)劃而言，并不存在確定的目標終點e，即若裝配體零部件能無干涉的到達最終拆卸位置，則通過路徑反演認為裝配路徑規(guī)劃成功。根據(jù)劉江山等[6]提出的基于OBB包圍盒的A*算法，對裝配場景與裝配零部件構(gòu)建碰撞包圍盒，并讓零部件做一次大跨步移出場景包圍盒的嘗試，若零部件從當前節(jié)點n朝某一確定方向能夠無干涉的沖出裝配場景包圍盒，則認為此路徑即為該零部件的最優(yōu)拆卸路徑，且通過路徑反演得到該零部件的最優(yōu)裝配路徑；若在嘗試途中出現(xiàn)干涉的情況，則采取引用權(quán)重系數(shù)的傳統(tǒng)A*算法獲取最優(yōu)裝配路徑。

3 多層次裝配路徑規(guī)劃

針對裝配體復(fù)雜性提升，若對裝配體路徑規(guī)劃運用傳統(tǒng)路徑規(guī)劃方法會出現(xiàn)組合爆炸的問題，本文在改進A*算法的基礎(chǔ)上通過結(jié)合人機交互路徑規(guī)劃方法，提出了基于人機交互的改進A*算法。在基于人機交互的改進A*算法中，人機交互路徑規(guī)劃方法是指在三維裝配操作系統(tǒng)中，利用操作者的裝配經(jīng)驗，為裝配體選擇一條無干涉且路線最優(yōu)的裝配路徑。針對裝配體路徑規(guī)劃問題，將人機交互路徑規(guī)劃方法劃分為兩個階段：交互式仿真拆卸階段與拆卸路徑反演得出裝配路徑階段。對這兩個階段構(gòu)建人機交互路徑規(guī)劃方法流程圖如圖2所示。

圖2 人機交互路徑規(guī)劃方法流程圖

根據(jù)圖2人機交互路徑規(guī)劃算法流程圖所示，在交互式仿真拆卸階段中將裝配體模型導(dǎo)入三維裝配操作系統(tǒng)，并根據(jù)操作者裝配經(jīng)驗自定義拆卸方式和拆卸路徑，從而保證裝配體可以高效無干涉地拆卸成獨立的零部件。接下來，在路徑反演階段利用“可拆即可裝”原則進行拆卸路徑反演，并最終生成裝配體裝配路徑。

本文通過將人機交互路徑規(guī)劃方法與改進A*算法結(jié)合，提出基于人機交互的改進A*算法。該算法利用人機交互路徑規(guī)劃方法將復(fù)雜裝配體分成多個層次段，并對各層次段中的零部件運用改進A*算法進行裝配路徑規(guī)劃，最終得到了整個復(fù)雜裝配體的最優(yōu)規(guī)劃路徑且成功解決了傳統(tǒng)路徑規(guī)劃算法用于復(fù)雜裝配體路徑規(guī)劃時出現(xiàn)的組合爆炸問題。基于人機交互的改進A*算法流程圖如圖3所示。

圖3 基于人機交互的改進A*算法流程圖

根據(jù)圖3基于人機交互的改進A*算法流程圖所示，將算法實現(xiàn)過程劃分為以下幾個步驟：

步驟1：將裝配體三維模型導(dǎo)入虛擬裝配操作系統(tǒng)中，并記錄模型初始位姿。

步驟2：利用人機交互路徑規(guī)劃方法對裝配體模型劃分層次，并利用層次樹指導(dǎo)裝配體拆卸。

步驟3：對已劃分層次的裝配部件運用改進A*算法來進行裝配路徑規(guī)劃。以裝配體部件i為例，對裝配體部件i各零件及裝配場景創(chuàng)建碰撞包圍盒，并對零件包圍盒進行一次大跨步移出場景包圍盒嘗試，若嘗試過程中無干涉，則該試探路徑即為該零件的最優(yōu)拆卸路徑，并根據(jù)“可拆即可裝”原則，反演生成零件最優(yōu)裝配路徑；若嘗試過程中有干涉，則利用傳統(tǒng)A*算法生成零件最優(yōu)裝配路徑。

步驟4：對步驟3中完成路徑規(guī)劃的若干層次段進行分段路徑反演，并生成整個裝配體裝配路徑。

值得一提的是，在基于人機交互的改進A*算法中，因為各層次段中零部件裝配動作相互無影響，所以其各層次段裝配零部件路徑規(guī)劃采用并行輸入的方式，此方式不僅節(jié)省了裝配時間，而且提升了裝配效率。

4 實驗研究

4.1 仿真結(jié)果對比分析

為更明顯且直觀的表明改進A*算法在復(fù)雜裝配體路徑規(guī)劃中優(yōu)于傳統(tǒng)路徑規(guī)劃算法，對此進行仿真對比分析。此次仿真基于Intel Core i5-6500；3.20GHz處理器；內(nèi)存為4GB；操作系統(tǒng)為Windows7的電腦平臺實現(xiàn)。在Matlab環(huán)境中，對傳統(tǒng)A*算法與改進A*算法針對部件零件數(shù)(三角面片數(shù))進行算法效率對比如圖4所示。

圖4 傳統(tǒng)A*算法與改進A*算法比較

根據(jù)圖4算法比較可以看出，當裝配部件零件數(shù)(三角面片數(shù))較少時，傳統(tǒng)A*算法與改進A*算法完成時間相差不大，甚至一度幾乎相同，但隨著裝配部件零件數(shù)的增多，因為受組合爆炸問題的困擾，傳統(tǒng)A*算法效率落后于改進A*算法，并且當裝配部件零件數(shù)越多時，改進A*算法的優(yōu)越性越明顯。

在Matlab環(huán)境中，針對隨機障礙地圖，改進A*算法與K-Omega算法(當k=3b=lnfn=0時)從同一起始點出發(fā)到同一目標終點的仿真運行結(jié)果如圖5所示。

圖5 改進A*算法與K-Omega算法比較

在圖5中，對改進A*算法取干涉威脅概率、平滑度代價權(quán)重為0，路徑長度代價權(quán)重為1得出了一條距離最短的規(guī)劃路徑①；對改進A*算法取路徑長度代價、平滑度代價權(quán)重為0，干涉威脅概率權(quán)重為1得出了一條干涉威脅最少的規(guī)劃路徑②；對改進A*算法取干涉威脅概率、路徑長度代價權(quán)重為0，平滑度代價權(quán)重為1得出了一條平滑度最好的規(guī)劃路徑③。選取對比方法中最重要的兩個參數(shù)進行算法運行效率分析如表1所示

表1 改進A*算法與K-Omega算法運行效率分析

通過表1效率分析得出，當改進A*算法選取路徑長度代價權(quán)重為1時，其代價花費較K-Omega算法代價花費減少107，時間縮短0.0146s；同時以時間花費為標準，改進A*算法較K-Omega算法效率提升了33.6%，并且從圖5中可以直觀看出改進A*算法效率遠遠優(yōu)于K-Omega算法。

4.2 實例研究

電主軸作為加工中心的核心部件，由打刀缸、內(nèi)置編碼器、主軸等重要部件組成，具有結(jié)構(gòu)緊湊、零部件復(fù)雜等相關(guān)特點。本文針對電主軸應(yīng)用傳統(tǒng)路徑規(guī)劃方法進行路徑規(guī)劃會出現(xiàn)組合爆炸的問題，采用基于人機交互的改進A*算法進行電主軸路徑規(guī)劃仿真實驗。算法利用人機交互路徑規(guī)劃方法對加工中心電主軸進行分層次操作，即將電主軸裝配體劃分為換刀系統(tǒng)、氣缸、主軸、冷卻系統(tǒng)等6部分。在裝配圖中表示電主軸各部分的位置情況如圖6所示。

①換刀系統(tǒng) ②氣缸 ③主軸 ④冷卻系統(tǒng) ⑤軸承殼體 ⑥端蓋 1.進油口 2.進氣口 3.活塞 4.旋轉(zhuǎn)編碼器 5.軸承A 6.冷卻外殼 7.螺旋水槽 8.電機9.軸承B 10.隔套 11.軸承C 12.軸承D 13.刀柄 14.冷卻殼體 15.軸承座 16.打刀缸

圖6 電主軸主要部件位置表示

對圖6中電主軸主要部件進行層次劃分，且層次劃分圖如圖7所示。

根據(jù)圖7電主軸主要部件層次劃分圖，對電主軸進行裝配路徑規(guī)劃仿真實驗。在Unity虛擬環(huán)境下對電主軸利用人機交互路徑規(guī)劃方法進行拆卸分層次仿真實驗，實驗結(jié)果如圖8a所示。

(a) 電主軸人機交互路徑規(guī)劃方法仿真

(b) 對主軸進行改進A*算法仿真 圖8 仿真圖

對圖8a中已劃分層次的部件進行改進A*算法(取干涉威脅概率、平滑度代價權(quán)重為0，路徑長度代價權(quán)重為1)并行輸入獲取最優(yōu)裝配路徑演示。以主軸部分為例，其中主軸部分的軸承利用改進A*算法進行大跨步移出裝配場景包圍盒的嘗試如圖8b中的虛線所示。

通過圖4、圖5算法之間的比較及圖8電主軸在Unity虛擬環(huán)境中的路徑規(guī)劃仿真實驗，說明基于人機交互的改進A*算法較傳統(tǒng)路徑規(guī)劃算法運行效率更高，并可應(yīng)用于多層次復(fù)雜裝配體的規(guī)劃路徑尋找，且當裝配體零部件結(jié)構(gòu)越復(fù)雜時，該算法優(yōu)越性越明顯。

5 結(jié)論

本文將人機交互路徑規(guī)劃方法與改進A*算法相結(jié)合，提出了基于人機交互的改進A*算法。該算法可高效地規(guī)劃出復(fù)雜裝配體的最優(yōu)裝配路徑，且有效地避免了裝配體組合爆炸的問題。同時，通過對改進A*算法與傳統(tǒng)A*算法和K-Omega算法的比較，及對加工中心電主軸的路徑規(guī)劃仿真實驗，可以得出本文提出的基于人機交互的改進A*算法節(jié)省了復(fù)雜裝配體路徑規(guī)劃時間，提升了裝配效率，使自動路徑規(guī)劃方法應(yīng)用于實際工業(yè)生產(chǎn)成為可能。