杨 钊，李 原，俞 琳，张 杰

（西北工业大学 现代设计与集成制造技术教育部重点实验室，陕西 西安 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.