基于A*算法的质量特性测试流程规划

陈 刚

（上海航天设备制造总厂，上海 200245）

0 引言

质量特性测试是航天器总装过程中的大型测试项目之一，其操作难度高、测试项多、风险大。尽管近年来其测试方法已从质量、质心、转动惯量单独测试[1]逐渐发展为集成测试[2-3]，但航天器质量特性测试仍是一项烦琐的工作，包含了垂直工装、水平工装及航天器各方向的质心、转动惯量的测试以及由此带来的频繁吊装、精测和电气操作。因此，测试前对相关操作流程进行合理规划对发挥集成测试优势、减少反复有着重要意义。

1 测试内容分析

通常，质量特性测试内容包括质量M、3个方向质心坐标 (xc,yc,zc)及 3个方向转动惯量Ix、Iy、Iz。实际操作时，还必须首先调平测试台体并对相应工装进行测量。质量特性测试主流程见图1。

图1 质量特性测试主流程Fig. 1 The main flow of the measurment of mass properties

任何一个测试项能够执行的必要条件是同时具备正确的台体状态和控制状态，而相关测试状态的存在又与其前置状态相依赖（如图2所示）。因此，在设置某个测试项的状态时，不可避免地要从其相依赖的状态一步步变迁过来。

图2 测试状态依赖关系Fig. 2 The relationship among measuring states

2 测试路网建模

按上述分析，每个测试状态等价于台体状态和控制状态的组合，测试过程即可映射为在各个测试状态间的变迁。本文将测试状态变迁路径的集合称为测试路网，路网中的每一条路径都是潜在的测试过程。

2.1 路网初始化

本文分别对工装测试和航天器测试独立进行路网初始化。原则上，路网中任意两个状态之间均能实现变迁，即任意两个状态节点均双向连接，如图3所示。

图3 路网初始状态Fig. 3 Initial state of path net

2.2 启发式路网演变

初始状态的路网中存在许多明显不合理的路径，同时，航天器测试前必须进行相应的工装测试这个强约束（以下简称“工装约束”）也没有体现，因此需对路网进行演变。

路网演变的启发规律如下：

1）避免重大开销，禁止航天器水平测试状态向水平工装测试状态变迁；

2）符合测量一致性，工装测试状态不能向台体状态不同的航天器测试状态直接变迁；

3）符合工装约束，航天器测试状态上游一定具备同类的工装测试状态，禁止航天器垂直测试状态与水平测试状态的直接变迁；

4）加入代表台体调平等初始状态的起始节点，符合对称归一化原则，起始节点仅需向单一台体状态的工装测试状态变迁。

按以上启发规律对初始路网进行逐步演变，得到路网最终状态，如图4所示。

图4 路网最终状态Fig. 4 Final state of path net

3 路径搜索

图4中，路网中符合工装约束且途经所有航天器测试状态的路径都对应着有效的测试流程，本文中流程规划的目的即是寻找其中开销最小的路径。通常，对于在有固定拓扑关系的图结构中进行路径搜索，A*算法是比较成熟的解决方案[4-5]。

3.1 代价函数

代价函数 F(x)是 A*算法中单步路径的判断标准，表示从起始节点经由节点x完成搜索的开销，由G(x)和H(x)决定，即

式中：G(x)表示从起始节点到节点x变迁的实际开销；H(x)表示从节点x到完成搜索的最佳路径的估计开销。为了对 G(x)和 H(x)做出合理的取值与估计，需对图4路网中的所有变迁开销进行赋值。结合图2所示状态依赖关系，联系工程实际，给出如表1所示赋值结果。

显然，G(x)的取值即为实际路径上所有变迁对应于表1中的开销之和。而H(x)只能给出估计值，本文取

其中：n为未经历的状态节点数；K为所有变迁的平均开销，按表1计算，K=225。

表1 状态变迁开销分析Table 1 Cost analysis of state transfer

续表1

3.2 搜索算法

参考A*算法典型步骤[6]并结合本文实际，给出搜索算法的主要逻辑如下：

1）将起始点设为当前点，初始化未经历状态节点数n。

2）考察当前点向其子节点变迁的代价函数F(x)，将F(x)最小且满足工装约束的子节点（即目标节点）设为当前点；如果F(x)最小的子节点不满足工装约束，考察F(x)次小子节点，以此类推。

3）更改已经历节点记录，重新计算n。

4）重复步骤 2）、3）。

5）如果找不到目标节点，将与当前点并列、F(x)次小且满足工装约束的节点设为当前点并更改已经历节点记录，以此类推。

6）重复步骤2）～5）。

7）如果n为0，搜索结束。

8）整理所有被设为当前点的节点序列，即为目标路径。

4 流程规划结果

目前，典型的测试流程为“先工装再产品，先质量再惯量”，如图5所示，其状态迁移总开销为1805。

按3.2搜索算法，结合表1数据，对图4路网进行路径搜索。经过9次迭代后完成搜索，目标路径状态迁移总开销为1785（如图6所示），比典型流程少20的开销。

图5 典型质量特性测试流程Fig. 5 Typical flow of mass property measuring

图6 质量特性测试目标流程Fig. 6 Target flow of mass property measuring

5 结束语

本文通过对测试内容的分析，提出以测试状态变迁表征测试流程的思想，据此构建测试路网，并借助启发规律对路网进行合理的演变；综合考虑各种依赖状态后对路网中所有变迁进行开销赋值；最后，使用 A*算法从路网中搜索出目标路径。开销计算表明，目标路径比目前典型流程的路径减少开销20，规划效果明显。

（References）

[1]杜晨, 陈勉. 卫星质量特性测试新方法研究[J]. 航天器环境工程, 2004, 21(3): 11-15 Du Chen, Chen Mian. Research on new test method of mass properties of spacecraft[J]. Spacecraft Environment Engineering, 2004, 21(3): 11-15

[2]王洪鑫, 徐在峰, 赵科, 等. 航天器质量特性测试技术新进展[J]. 航天器环境工程, 2011, 28(2): 171-174 Wang Hongxin, Xu Zaifeng, Zhao Ke, et al. Recent advances of mass property measuring technology for spacecraft[J]. Spacecraft Environment Engineering, 2011,28(2): 171-174

[3]赵科, 王洪鑫, 徐在峰. 航天器质量特性测试信息系统设计与实现[J]. 航天器环境工程, 2011, 28(5):486-489 Zhao Ke, Wang Hongxin, Xu Zaifeng. The design and realization of an information system for mass property test of spacecraft[J]. Spacecraft Environment Engineering,2011, 28(5): 486-489

[4]郝振国, 王玉玫. 双向 A*算法在军事路径规划中的应用[J]. 计算机工程与应用, 2011, 47(29): 246-248 Hao Zhenguo, Wang Yumei. Application of bidirectional A*method in military route planning[J]. Computer Engineering and Applications, 2011, 47(29): 246-248

[5]陈彬, 李靖靖, 宋磊, 等. 基于可视图和 A* 算法的连续模型路径搜索[J]. 交通信息与安全, 2012, 30(3):39-42 Chen Bin, Li Jingjing, Song Lei, et al. Search for continuous model based on visibility graph and A*algorithm[J]. Journal of Transport Information and Safety, 2012, 30(3): 39-42

[6]田立中, 付宜利, 马玉林, 等. 装配路径规划中基于动态坐标的A*搜索算法[J]. 计算机集成制造系统, 2002,8(4): 316-319 Tian Lizhong, Fu Yili, Ma Yulin, et al. A*search arithmetic based on dynamic coordinate in assembly path plan[J]. Computer Integrated Manufacturing Systems,2002, 8(4): 316-319