一種基于交互特征偶的虛擬對象路徑規(guī)劃方法

楊 釗，李 原，俞 琳，張 杰

（西北工業(yè)大學(xué) 現(xiàn)代設(shè)計與集成制造技術(shù)教育部重點實驗室，陜西 西安 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)為虛擬對象之間的交互，設(shè)計人員通過定義幾何體之間的交互來完成產(chǎn)品的可裝配性分析。

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

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

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

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

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

1.1 交互特征偶建模理論

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

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

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

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

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

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

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

1.2 交互過程的離散化描述

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

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

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

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

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

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

定義5 交互狀態(tài)：被賦予交互特征偶屬性的虛擬對象，在動態(tài)交互過程中某一時刻t的交互特征偶匹配狀態(tài)稱為交互狀態(tài)。初始狀態(tài)和目標(biāo)狀態(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)的集合，還應(yīng)具有一定的時序特征。例如，對于圖2所示的交互過程，首先完成“外圓柱面-內(nèi)圓柱面對齊”偶的匹配，然后該特征偶的約束下再完成“面-面貼合”偶的匹配。如果先完成“面-面貼合”偶的匹配，則在進行“外圓柱面-內(nèi)圓柱面對齊”偶匹配的過程中必然會使得主客體對象發(fā)生干涉。

圖2 交互過程示例

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

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

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

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

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

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

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

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

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

Step3：確定交互過程的初始狀態(tài)和目標(biāo)狀態(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：判斷主體對象是否到達目標(biāo)狀態(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é)點的引導(dǎo)約束。然后在中間狀態(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加入到隨機樹中。重復(fù)上述步驟直到xnear與xgoal距離小于搜索步長L（即dis（xnear，xgoal）≤L），則代表隨機樹達到了目標(biāo)狀態(tài)節(jié)點，算法結(jié)束。

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

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

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

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

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

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

4 結(jié)語

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

[1]國家自然基金科學(xué)委員會.機械工程學(xué)科發(fā)展戰(zhàn)略報告[M].北京：科學(xué)出版社，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)件虛擬裝配技術(shù)研究[D].南京：南京航空航天大學(xué)，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]李 剛，馬良荔，郭曉明.交互式拆卸引導(dǎo)裝配路徑規(guī)劃方法研究[J].計算機應(yīng)用與軟件，2012，29（10）：248-250.

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

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

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

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