楊 釗，李 原，俞 琳，張 杰

（西北工業(yè)大學 現(xiàn)代設計與集成制造技術教育部重點實驗室，陜西 西安 710072）

0 引言

由現(xiàn)代CAD、CAM和CAE等工具構(gòu)成的虛擬環(huán)境在產(chǎn)品研制各環(huán)節(jié)中發(fā)揮著巨大作用[1]，虛擬環(huán)境是由若干虛擬對象（Virtual Object）構(gòu)成的，這些虛擬對象之間并不孤立，而是通過進行頻繁的交互（Interaction）來實現(xiàn)特定的功能。對于虛擬裝配而言，零部件、工裝、工具等實體在虛擬環(huán)境中體現(xiàn)為虛擬對象，零部件之間的裝配、工裝工具對零件產(chǎn)品的夾持與定位等則體現(xiàn)為虛擬對象之間的交互，設計人員通過定義幾何體之間的交互來完成產(chǎn)品的可裝配性分析。

虛擬對象在交互過程中通常只涉及兩個對象，事實上，三個或者更多對象之間的交互可以看成是對象兩兩交互的組合。為了便于描述，將兩個對象中相對主動（交互過程的發(fā)起者）的一方稱為主體對象（Active Object，AO），相對被動（交互過程的承受者）的一方稱為客體對象（Passive Object，PO）。虛擬對象的交互過程往往伴隨著主體對象從初始位置到目標位置的運動過程，然而這一過程一直沒有得到令人滿意的描述，導致產(chǎn)品開發(fā)過程中很多環(huán)節(jié)不得不依賴冗繁的人機交互。為實現(xiàn)圖1所示產(chǎn)品的裝配，設計者必須通過手動定義幾何體之間的所有約束；同時當約束定義好之后，零件會直接從初始位置變換到目標位置，所有的中間過程都被忽略。而在裝配仿真領域，用戶必須對產(chǎn)品、工裝等的空間姿態(tài)以及動作形式進行詳盡的定義，例如實現(xiàn)螺栓和螺母的裝配，必須首先移動螺母使其與螺栓同軸，然后控制其連續(xù)移動直到合適的位置?？梢娂词挂粋€如此簡單的交互過程，操作起來也非常復雜。隨著飛機等產(chǎn)品復雜度的增加，虛擬對象交互的業(yè)務量將日益繁重，人工干預模式將嚴重影響交互效率的提高。

針對上述問題，一個有效的解決途徑是使虛擬對象具有一定的自主交互能力。文獻[2]從交互結(jié)構(gòu)與行為的內(nèi)在統(tǒng)一性出發(fā)，提出了主客體對象交互結(jié)構(gòu)的特征偶構(gòu)造理論，將交互特征偶（Interaction Feature Pair，IFP）定義為主客體對象交互過程中，雙方直接參與交互的幾何特征所構(gòu)成的偶對。虛擬對象的交互行為可以根據(jù)其交互特征偶類型來判斷，從而為虛擬對象間的自主交互問題提供解決思路。本文在其研究基礎上，探討如何利用交互特征偶解決虛擬對象交互過程的路徑規(guī)劃問題，以實現(xiàn)使路徑規(guī)劃更趨于智能化和自動化的目標。

目前路徑規(guī)劃的方法可以歸納為兩大類：一類是通過典型的路徑規(guī)劃算法自動計算和搜索路徑[3]，主要方法有隨機采樣法（包括概率路標法（PRM）和快速搜索隨機樹（RRT）法）、柵格法、人工勢場法、位姿空間（C空間）方法、人工智能方法等[4]，在這些方法中，隨機采樣法適用于解決高維空間復雜路徑規(guī)劃問題，其中PRM[5]主要應用于高維靜態(tài)空間，而RRT[6]適用于動態(tài)環(huán)境或者運動約束下的路徑規(guī)劃，其他算法大都計算復雜性較高，路徑的規(guī)劃容易出現(xiàn)組合爆炸問題且效率低下[7]；另一類是通過交互的辦法定義路徑[8]，交互可在傳統(tǒng)的CAD工具上進行，也可利用虛擬裝配系統(tǒng)，但需要用戶手動輸入相關參數(shù)，在路徑規(guī)劃過程中不得不依賴冗繁的人機交互。

綜上考慮，本文提出了一種基于交互特征偶的路徑規(guī)劃方法，通過交互特征偶匹配順序引導虛擬對象的交互過程，將主體對象的運動路徑以離散點的形式進行記錄，并基于快速搜索隨機樹（RRT）法實現(xiàn)其路徑規(guī)劃。該方法的優(yōu)點在于既簡化了路徑規(guī)劃過程中的人機交互，又在一定程度上提高了路徑規(guī)劃的效率。

1 基于交互特征偶的交互過程描述

1.1 交互特征偶建模理論

虛擬對象的自主交互過程即主體對象能夠按目標約束主動完成與客體對象的動態(tài)交互過程，這一過程的實現(xiàn)依賴于虛擬對象的個體結(jié)構(gòu)，并通過結(jié)構(gòu)間幾何要素的逐步關聯(lián)來完成預期目標。

定義1 交互特征（Interaction Feature，IF）：在交互過程中，虛擬對象的幾何體上具有一定工程意義、并且直接參與交互的幾何特征叫做交互特征。從幾何及計算機圖形學上考慮，交互特征包括“點（Point）”、“線（Curve）”、“面（Surface）”三種基本類型。而且，交互特征總是成對出現(xiàn)，每個交互特征總有一個與之相匹配的交互特征同時存在。

定義2 交互特征偶（Interaction Feature Pair，IFP）：兩個虛擬對象進行交互過程中，雙方的交互特征通過匹配所形成的偶對叫做交互特征偶。一個交互特征偶中至少含有一對基本交互特征，根據(jù)交互特征偶中包含的基本特征元素的數(shù)目，將其分為基本交互特征偶和復合交互特征偶。只含有一對基本特征元素的交互特征偶叫做基本交互特征偶?；窘换ヌ卣髋及N基本類型：點點偶（BIFPPP）、點線偶（BIFPPC）、點面偶（BIFPPS）、線線偶（BIFPCC）、線面偶（BIFPCS）和面面偶（BIFPSS），如表1 所示。復合交互特征偶是由若干基本交互特征偶組合而成的。

交互特征偶中至少應包含兩類信息：分屬于主客體對象的交互特征信息以及交互規(guī)則信息。因此，交互特征偶可以用如式（1）所示的四元組來表示。

表1 基本交互特征偶（BIFP）

其中，Name為交互特征偶的名稱，IF|AO表示主體對象上的交互特征，IF|PO表示客體對象上的交互特征，{IR}表示交互規(guī)則集（Interactive Rule Set），即兩個對象的交互特征進行匹配時所應遵循的規(guī)則，包含了主客體對象交互特征元素之間的幾何約束關系，以及交互過程中所必須遵循的工程規(guī)則。其中幾何約束集描述了交互特征之間的配合關系，而工程規(guī)則集描述了交互過程中主客體對象所必須遵守的領域規(guī)則。當然，針對不同的領域，基本交互特征偶遠不止六種，而是根據(jù)具體的工程實際意義賦予其不同的名稱。例如，在裝配仿真領域，比較典型的基本交互特征偶如表2所示。在該領域中，最重要的工程規(guī)則為避障，即主體對象在運動過程中不能與環(huán)境中的其他對象發(fā)生干涉。

表2 常見的基本交互特征偶舉例（裝配仿真領域）

1.2 交互過程的離散化描述

實際上，虛擬對象交互過程的實現(xiàn)并不是一步完成的，而是隨著交互特征偶的匹配逐步完成的。虛擬對象的交互過程可以看作是虛擬對象的交互狀態(tài)隨時間（離散的時間單元）的不斷變遷，趨于目標狀態(tài)的過程。

由于虛擬對象交互過程的實現(xiàn)依賴于計算機信息環(huán)境，在利用計算機進行交互過程仿真時，所見到的動態(tài)畫面實際上是由一幀幀靜止畫面連續(xù)播放而成的。這些靜止的畫面可以用“狀態(tài)”來描述。

定義3 狀態(tài)（State）：指虛擬對象在某一時刻或階段所表現(xiàn)出來的空間位置、姿態(tài)及其屬性?？梢詫討B(tài)的交互過程通過不同的靜態(tài)狀態(tài)來定義。例如在裝配仿真領域，在裝配過程中的每一幀畫面都可以認為是一個狀態(tài)。

由于虛擬對象的交互過程伴隨著主體對象從初始位置運動到目標位置的過程，該過程包含的狀態(tài)包括初始狀態(tài)、目標狀態(tài)和中間狀態(tài)。分別定義如下：

定義4 初始狀態(tài)（Initial State）：主體對象在初始位置時，主客體對象所表現(xiàn)出來的空間位置、姿態(tài)及其屬性；目標狀態(tài)（Goal State）：主體對象運動到目標位置時，主客體對象所表現(xiàn)出來的空間位置、姿態(tài)及其屬性；中間狀態(tài)（Intermediate State）：主體對象從初始位置運動到目標位置過程中主客體對象所表現(xiàn)出來的空間位置、姿態(tài)及其屬性。初始狀態(tài)經(jīng)過一系列中間狀態(tài)的轉(zhuǎn)變，最終達到目標狀態(tài)。

由于交互特征偶對于交互過程具有引導作用，因此，當某一時刻被賦予交互特征偶屬性的虛擬對象之間進行IFP匹配時，此時的狀態(tài)對于整個交互過程來說是很“關鍵”的，它不僅體現(xiàn)了主客體對象間存在的交互信息，而且對于整個交互過程狀態(tài)的變化趨勢起到了目標導向作用。該狀態(tài)在所有狀態(tài)中的作用類似于計算機動畫領域中關鍵幀的作用，它描述了虛擬對象運動或變化中的關鍵動作所處的那一幀的靜態(tài)畫面。我們將其定義為交互狀態(tài)。

定義5 交互狀態(tài)：被賦予交互特征偶屬性的虛擬對象，在動態(tài)交互過程中某一時刻t的交互特征偶匹配狀態(tài)稱為交互狀態(tài)。初始狀態(tài)和目標狀態(tài)均可視為交互狀態(tài)，而中間狀態(tài)則包含交互狀態(tài)。交互狀態(tài)的定義如式2所示。

其中，{IS}表示交互狀態(tài)集（Interactive State Set），IFP（ti）（i=0，1，L m）表示某一時刻的交互特征偶匹配狀態(tài)，t0為初始時刻。

交互過程不僅僅是交互狀態(tài)的集合，還應具有一定的時序特征。例如，對于圖2所示的交互過程，首先完成“外圓柱面-內(nèi)圓柱面對齊”偶的匹配，然后該特征偶的約束下再完成“面-面貼合”偶的匹配。如果先完成“面-面貼合”偶的匹配，則在進行“外圓柱面-內(nèi)圓柱面對齊”偶匹配的過程中必然會使得主客體對象發(fā)生干涉。

圖2 交互過程示例

通過以上定義，虛擬對象的交互過程可看作是虛擬對象的交互狀態(tài)隨時間（離散的時間單元）的不斷變遷，趨于目標狀態(tài)的過程。交互過程與狀態(tài)機[9]中的有向圖描述較為相似，其組成包括狀態(tài)（State）、轉(zhuǎn)移（Transition）、事件（Event）、動作（Action）等。狀態(tài)機理論的研究已較為成熟，此處不過多闡述。可用如圖3所示來描述交互狀態(tài)及其轉(zhuǎn)化關系。從初始狀態(tài)起，在事件（如位姿變換、運動規(guī)劃等）的觸發(fā)下，通過執(zhí)行某些動作（平移、旋轉(zhuǎn)等），引起各交互狀態(tài)之間的遷移，從一個交互狀態(tài)轉(zhuǎn)移到下一個交互狀態(tài)，直到所有的交互特征偶均已匹配完成。這樣，虛擬對象的交互過程就被離散化為一系列的順序交互狀態(tài)，在其引導作用下，主體對象從初始位置運動到目標位置，整個交互過程結(jié)束。

圖3 交互過程的交互狀態(tài)離散化描述

2 交互特征偶引導的路徑規(guī)劃方法

交互特征偶匹配的本質(zhì)是幾何約束的滿足，最終表現(xiàn)為對象之間相對位移的限制，即自由度限制。主體對象在空間中相對于客體對象所有可能的運動方式的總和，稱為交互自由度。每當一個交互特征偶匹配完成后，其中的幾何約束集限定了主體對象的自由度空間，主體對象只能在其自由度空間中運動，直到完成下一個交互特征偶的匹配。在虛擬環(huán)境下，主體對象的運動路徑是通過記錄一系列離散的空間位姿點得到的，可用一系列狀態(tài)節(jié)點來描述，如式3所示。

其中X為狀態(tài)搜索空間，一般采用C空間法對其進行描述，首先進行當前狀態(tài)下交互自由度的判斷，以此來確定C空間的維數(shù)，從而簡化計算；xinit∈X為初始狀態(tài)節(jié)點，xgoal∈X為目標狀態(tài)節(jié)點（交互特征偶匹配完成）；（x1，x2，L，xn）∈X 為一系列中間狀態(tài)節(jié)點，這些節(jié)點由交互狀態(tài)節(jié)點和離散的空間隨機采樣點組成；xobst∈X為不可通行的非法狀態(tài)的集合，即C空間中障礙的集合。

交互特征偶引導的交互過程路徑規(guī)劃方法流程圖如圖4所示。

圖4 交互特征偶引導的路徑規(guī)劃算法流程圖

Step1：在虛擬環(huán)境中激活主體對象（AO），識別其IFP類型；

Step2：判斷當前交互狀態(tài)下主體對象的交互自由度。在交互過程中，隨著交互狀態(tài)的改變，主體對象的自由度空間一直在發(fā)生變化（而且一般情況下會越來越小）；

Step3：確定交互過程的初始狀態(tài)和目標狀態(tài)xgoal，根據(jù)交互特征偶匹配順序，確定交互狀態(tài)順序節(jié)點（IFPi（i=1，2，L，n）（匹配完成）；

Step4：隨機選取一系列離散的空間位姿點，與交互狀態(tài)順序節(jié)點組成中間狀態(tài)節(jié)點（x1，x2，L，xn）；

Step5：基于快速搜索隨機樹（RRT）法規(guī)劃較優(yōu)路徑；

Step6：判斷主體對象是否到達目標狀態(tài)位置，若是，則記錄所生成的路徑，生成計算機可以執(zhí)行的動作指令，否則返回Step1。

其中，RRT法規(guī)劃較優(yōu)路徑的具體過程如下：從初始狀態(tài)位置xinit出發(fā)構(gòu)造搜索樹T，并將xinit作為T的根節(jié)點，交互狀態(tài)順序節(jié)點作為初始葉節(jié)點（IFPi（i=1，2，L，n），T在生長過程中必須滿足交互狀態(tài)順序節(jié)點的引導約束。然后在中間狀態(tài)節(jié)點（x1，x2，L，xn）中除交互狀態(tài)順序節(jié)點外隨機選擇一個狀態(tài)點xrand，遍歷T，找到T上距xrand最近距離的節(jié)點xnear，主體對象沿著xrand到xnear依照交互自由度產(chǎn)生滿足全局約束的候選路徑集合，經(jīng)歷時間Δt，到達一個新的狀態(tài)點xnew，若運動過程中與障礙物xobst發(fā)生碰撞，則放棄這次生長，否則將xnew加入到隨機樹中。重復上述步驟直到xnear與xgoal距離小于搜索步長L（即dis（xnear，xgoal）≤L），則代表隨機樹達到了目標狀態(tài)節(jié)點，算法結(jié)束。

3 數(shù)字化裝配仿真領域?qū)嵗?/h2>

本文所提出的方法與開發(fā)的功能模塊，在CATIA V5 R18平臺上，以CAA FOR CATIA V5為開發(fā)工具，MS Visual Studio 2005為開發(fā)環(huán)境，以某型發(fā)動機組件為例在數(shù)字化裝配仿真領域進行實例驗證。用戶只需選擇主體對象和客體對象，系統(tǒng)將自動讀取其交互特征偶，此時便可預覽兩個對象的交互過程，并對交互過程進行路徑規(guī)劃。如圖5所示，選擇螺釘（Air_Filter_Bolt.4）為主體對象，空氣過濾器箱蓋（Air__Filter_Cover.1）為客體對象，系統(tǒng)將通過檢索預先建立的裝配與仿真領域中的基本交互特征偶BIFP庫，自動讀取其交互特征偶并賦予對象的屬性值。

圖5 主客體對象選擇及交互特征偶實例化

表3 主客體對象的交互特征偶

單擊路徑規(guī)劃按鈕，彈出RRT算法路徑規(guī)劃對話框，如圖6所示。

圖6中所示主客體對象的交互過程表現(xiàn)為螺釘從初始狀態(tài)位置到目標狀態(tài)位置（箱蓋上螺釘孔處）的連續(xù)動畫過程，其間要經(jīng)過兩個交互狀態(tài)：第一個狀態(tài)是螺釘?shù)耐鈭A柱面與螺釘孔的內(nèi)圓柱面對齊，此時的交互自由度為2，螺釘只能沿著螺釘孔的軸線方向平移或者繞軸線旋轉(zhuǎn)；另一個狀態(tài)是螺釘?shù)钠矫媾c箱蓋吊耳的平面貼合，此時螺釘?shù)慕换プ杂啥葹?，到達目標狀態(tài)位置。確定交互過程的初始狀態(tài)節(jié)點（節(jié)點1）和目標狀態(tài)節(jié)點（節(jié)點70），根據(jù)交互特征偶匹配順序，添加交互狀態(tài)順序節(jié)點（節(jié)點60），單擊RRT路徑搜索按鈕，系統(tǒng)將以離散路徑點（組件質(zhì)心）的形式進行運動路徑的顯示，其中節(jié)點60為路徑的引導點。

4 結(jié)語

路徑規(guī)劃是分析和控制虛擬對象交互過程的重要研究內(nèi)容之一，在虛擬環(huán)境中如何在封閉狹窄空間內(nèi)規(guī)劃一條合理的主體對象運動路徑，是有效提高交互過程執(zhí)行效率的重要考慮因素。本文所提出的交互特征偶引導的路徑規(guī)劃算法，通過將交互狀態(tài)順序節(jié)點定義為路徑的引導點，這樣在使用RRT算法構(gòu)建擴展樹時既可繞過障礙物，又可朝著目標點方向生長，從而減少了擴展樹生長的隨機性，在一定程度上有效提高了路徑規(guī)劃效率，同時，該方法使得主客體對象在交互過程定義時只需三次人機交互（即分別選擇主客體對象和添加交互狀態(tài)順序節(jié)點），而根據(jù)實際經(jīng)驗，完成這樣兩個零件裝配仿真詳細動作的定義至少需要10次人機交互，因此本文提出的方法在一定程度上也滿足了對象智能交互的需求，對于提升虛擬對象的自主交互能力具有重要的實踐意義和參考價值。

[1]國家自然基金科學委員會.機械工程學科發(fā)展戰(zhàn)略報告[M].北京：科學出版社，2010.

[2]Zhang J，Sun Y L，Xu Z J，Li Y.An Interaction Process Model for Virtual Objects Based on Interaction Structures.ICMSE 2013.

[3]楊 驥.飛機構(gòu)件虛擬裝配技術研究[D].南京：南京航空航天大學，2007.

[4]Latombe J C.Robot Motion Planning[M].Boston：Kluwer Academic Publishers，1991.

[5]Kavraki L E，Kolountzakis M，Latombe J C.Analysis of Probabilistic Roadmaps for Path Planning.IEEE Tr.on Robotics and Automation.Minneapolis，1996[C].14（1）：166-171.

[6]LaValle，Steven M.Rapidly-exploring Random Trees：A New Tool for Path Planning [R].ComputerScienceDepartment，IowaState University，1998.

[7]李 剛，馬良荔，郭曉明.交互式拆卸引導裝配路徑規(guī)劃方法研究[J].計算機應用與軟件，2012，29（10）：248-250.

[8]鄭 軼，寧汝新，劉檢華，等.交互式虛擬裝配路徑規(guī)劃及優(yōu)選方法研究[J].機械工程學報，2006，17（11）：1153-1156.

[9]李志軍.基于狀態(tài)機的安全漏洞檢查機制的設計與實現(xiàn) [D].西安：西安電子科技大學，2010.

[10]符 磊，余劍峰，張 杰.基于多級骨架模型的關聯(lián)設計方法研究[J].鍛壓裝備與制造技術，2013，48（4）：94-98.

[11]龔志海，葉春生，黃樹槐.FDM支撐生成算法及支撐路徑規(guī)劃研究[J].鍛壓裝備與制造技術，2006，41（3）：92-94.