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

楊 釗，李 原，俞 琳，張 杰

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

0 引言

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

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

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

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

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

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

1.1 交互特征偶建模理論

虛擬對象的自主交互過程即主體對象能夠按目標約束主動完成與客體對象的動態交互過程，這一過程的實現依賴于虛擬對象的個體結構，并通過結構間幾何要素的逐步關聯來完成預期目標。

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

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

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

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

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

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

1.2 交互過程的離散化描述

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

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

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

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

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

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

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

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

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

圖2 交互過程示例

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

圖3 交互過程的交互狀態離散化描述

2 交互特征偶引導的路徑規劃方法

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

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

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

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

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

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

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

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

Step5：基于快速搜索隨機樹（RRT）法規劃較優路徑；

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

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

3 數字化裝配仿真領域實例

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

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

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

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

圖6中所示主客體對象的交互過程表現為螺釘從初始狀態位置到目標狀態位置（箱蓋上螺釘孔處）的連續動畫過程，其間要經過兩個交互狀態：第一個狀態是螺釘的外圓柱面與螺釘孔的內圓柱面對齊，此時的交互自由度為2，螺釘只能沿著螺釘孔的軸線方向平移或者繞軸線旋轉；另一個狀態是螺釘的平面與箱蓋吊耳的平面貼合，此時螺釘的交互自由度為0，到達目標狀態位置。確定交互過程的初始狀態節點（節點1）和目標狀態節點（節點70），根據交互特征偶匹配順序，添加交互狀態順序節點（節點60），單擊RRT路徑搜索按鈕，系統將以離散路徑點（組件質心）的形式進行運動路徑的顯示，其中節點60為路徑的引導點。

4 結語

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

[1]國家自然基金科學委員會.機械工程學科發展戰略報告[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]楊 驥.飛機構件虛擬裝配技術研究[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]李 剛，馬良荔，郭曉明.交互式拆卸引導裝配路徑規劃方法研究[J].計算機應用與軟件，2012，29（10）：248-250.

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

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

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

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