基于A*算法的質(zhì)量特性測試流程規(guī)劃

陳 剛

（上海航天設(shè)備制造總廠，上海 200245）

0 引言

質(zhì)量特性測試是航天器總裝過程中的大型測試項(xiàng)目之一，其操作難度高、測試項(xiàng)多、風(fēng)險(xiǎn)大。盡管近年來其測試方法已從質(zhì)量、質(zhì)心、轉(zhuǎn)動慣量單獨(dú)測試[1]逐漸發(fā)展為集成測試[2-3]，但航天器質(zhì)量特性測試仍是一項(xiàng)煩瑣的工作，包含了垂直工裝、水平工裝及航天器各方向的質(zhì)心、轉(zhuǎn)動慣量的測試以及由此帶來的頻繁吊裝、精測和電氣操作。因此，測試前對相關(guān)操作流程進(jìn)行合理規(guī)劃對發(fā)揮集成測試優(yōu)勢、減少反復(fù)有著重要意義。

1 測試內(nèi)容分析

通常，質(zhì)量特性測試內(nèi)容包括質(zhì)量M、3個方向質(zhì)心坐標(biāo) (xc,yc,zc)及 3個方向轉(zhuǎn)動慣量Ix、Iy、Iz。實(shí)際操作時，還必須首先調(diào)平測試臺體并對相應(yīng)工裝進(jìn)行測量。質(zhì)量特性測試主流程見圖1。

圖1 質(zhì)量特性測試主流程Fig. 1 The main flow of the measurment of mass properties

任何一個測試項(xiàng)能夠執(zhí)行的必要條件是同時具備正確的臺體狀態(tài)和控制狀態(tài)，而相關(guān)測試狀態(tài)的存在又與其前置狀態(tài)相依賴（如圖2所示）。因此，在設(shè)置某個測試項(xiàng)的狀態(tài)時，不可避免地要從其相依賴的狀態(tài)一步步變遷過來。

圖2 測試狀態(tài)依賴關(guān)系Fig. 2 The relationship among measuring states

2 測試路網(wǎng)建模

按上述分析，每個測試狀態(tài)等價于臺體狀態(tài)和控制狀態(tài)的組合，測試過程即可映射為在各個測試狀態(tài)間的變遷。本文將測試狀態(tài)變遷路徑的集合稱為測試路網(wǎng)，路網(wǎng)中的每一條路徑都是潛在的測試過程。

2.1 路網(wǎng)初始化

本文分別對工裝測試和航天器測試獨(dú)立進(jìn)行路網(wǎng)初始化。原則上，路網(wǎng)中任意兩個狀態(tài)之間均能實(shí)現(xiàn)變遷，即任意兩個狀態(tài)節(jié)點(diǎn)均雙向連接，如圖3所示。

圖3 路網(wǎng)初始狀態(tài)Fig. 3 Initial state of path net

2.2 啟發(fā)式路網(wǎng)演變

初始狀態(tài)的路網(wǎng)中存在許多明顯不合理的路徑，同時，航天器測試前必須進(jìn)行相應(yīng)的工裝測試這個強(qiáng)約束（以下簡稱“工裝約束”）也沒有體現(xiàn)，因此需對路網(wǎng)進(jìn)行演變。

路網(wǎng)演變的啟發(fā)規(guī)律如下：

1）避免重大開銷，禁止航天器水平測試狀態(tài)向水平工裝測試狀態(tài)變遷；

2）符合測量一致性，工裝測試狀態(tài)不能向臺體狀態(tài)不同的航天器測試狀態(tài)直接變遷；

3）符合工裝約束，航天器測試狀態(tài)上游一定具備同類的工裝測試狀態(tài)，禁止航天器垂直測試狀態(tài)與水平測試狀態(tài)的直接變遷；

4）加入代表臺體調(diào)平等初始狀態(tài)的起始節(jié)點(diǎn)，符合對稱歸一化原則，起始節(jié)點(diǎn)僅需向單一臺體狀態(tài)的工裝測試狀態(tài)變遷。

按以上啟發(fā)規(guī)律對初始路網(wǎng)進(jìn)行逐步演變，得到路網(wǎng)最終狀態(tài)，如圖4所示。

圖4 路網(wǎng)最終狀態(tài)Fig. 4 Final state of path net

3 路徑搜索

圖4中，路網(wǎng)中符合工裝約束且途經(jīng)所有航天器測試狀態(tài)的路徑都對應(yīng)著有效的測試流程，本文中流程規(guī)劃的目的即是尋找其中開銷最小的路徑。通常，對于在有固定拓?fù)潢P(guān)系的圖結(jié)構(gòu)中進(jìn)行路徑搜索，A*算法是比較成熟的解決方案[4-5]。

3.1 代價函數(shù)

代價函數(shù) F(x)是 A*算法中單步路徑的判斷標(biāo)準(zhǔn)，表示從起始節(jié)點(diǎn)經(jīng)由節(jié)點(diǎn)x完成搜索的開銷，由G(x)和H(x)決定，即

式中：G(x)表示從起始節(jié)點(diǎn)到節(jié)點(diǎn)x變遷的實(shí)際開銷；H(x)表示從節(jié)點(diǎn)x到完成搜索的最佳路徑的估計(jì)開銷。為了對 G(x)和 H(x)做出合理的取值與估計(jì)，需對圖4路網(wǎng)中的所有變遷開銷進(jìn)行賦值。結(jié)合圖2所示狀態(tài)依賴關(guān)系，聯(lián)系工程實(shí)際，給出如表1所示賦值結(jié)果。

顯然，G(x)的取值即為實(shí)際路徑上所有變遷對應(yīng)于表1中的開銷之和。而H(x)只能給出估計(jì)值，本文取

其中：n為未經(jīng)歷的狀態(tài)節(jié)點(diǎn)數(shù)；K為所有變遷的平均開銷，按表1計(jì)算，K=225。

表1 狀態(tài)變遷開銷分析Table 1 Cost analysis of state transfer

續(xù)表1

3.2 搜索算法

參考A*算法典型步驟[6]并結(jié)合本文實(shí)際，給出搜索算法的主要邏輯如下：

1）將起始點(diǎn)設(shè)為當(dāng)前點(diǎn)，初始化未經(jīng)歷狀態(tài)節(jié)點(diǎn)數(shù)n。

2）考察當(dāng)前點(diǎn)向其子節(jié)點(diǎn)變遷的代價函數(shù)F(x)，將F(x)最小且滿足工裝約束的子節(jié)點(diǎn)（即目標(biāo)節(jié)點(diǎn)）設(shè)為當(dāng)前點(diǎn)；如果F(x)最小的子節(jié)點(diǎn)不滿足工裝約束，考察F(x)次小子節(jié)點(diǎn)，以此類推。

3）更改已經(jīng)歷節(jié)點(diǎn)記錄，重新計(jì)算n。

4）重復(fù)步驟 2）、3）。

5）如果找不到目標(biāo)節(jié)點(diǎn)，將與當(dāng)前點(diǎn)并列、F(x)次小且滿足工裝約束的節(jié)點(diǎn)設(shè)為當(dāng)前點(diǎn)并更改已經(jīng)歷節(jié)點(diǎn)記錄，以此類推。

6）重復(fù)步驟2）～5）。

7）如果n為0，搜索結(jié)束。

8）整理所有被設(shè)為當(dāng)前點(diǎn)的節(jié)點(diǎn)序列，即為目標(biāo)路徑。

4 流程規(guī)劃結(jié)果

目前，典型的測試流程為“先工裝再產(chǎn)品，先質(zhì)量再慣量”，如圖5所示，其狀態(tài)遷移總開銷為1805。

按3.2搜索算法，結(jié)合表1數(shù)據(jù)，對圖4路網(wǎng)進(jìn)行路徑搜索。經(jīng)過9次迭代后完成搜索，目標(biāo)路徑狀態(tài)遷移總開銷為1785（如圖6所示），比典型流程少20的開銷。

圖5 典型質(zhì)量特性測試流程Fig. 5 Typical flow of mass property measuring

圖6 質(zhì)量特性測試目標(biāo)流程Fig. 6 Target flow of mass property measuring

5 結(jié)束語

本文通過對測試內(nèi)容的分析，提出以測試狀態(tài)變遷表征測試流程的思想，據(jù)此構(gòu)建測試路網(wǎng)，并借助啟發(fā)規(guī)律對路網(wǎng)進(jìn)行合理的演變；綜合考慮各種依賴狀態(tài)后對路網(wǎng)中所有變遷進(jìn)行開銷賦值；最后，使用 A*算法從路網(wǎng)中搜索出目標(biāo)路徑。開銷計(jì)算表明，目標(biāo)路徑比目前典型流程的路徑減少開銷20，規(guī)劃效果明顯。

（References）

[1]杜晨, 陳勉. 衛(wèi)星質(zhì)量特性測試新方法研究[J]. 航天器環(huán)境工程, 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]王洪鑫, 徐在峰, 趙科, 等. 航天器質(zhì)量特性測試技術(shù)新進(jìn)展[J]. 航天器環(huán)境工程, 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]趙科, 王洪鑫, 徐在峰. 航天器質(zhì)量特性測試信息系統(tǒng)設(shè)計(jì)與實(shí)現(xiàn)[J]. 航天器環(huán)境工程, 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*算法在軍事路徑規(guī)劃中的應(yīng)用[J]. 計(jì)算機(jī)工程與應(yīng)用, 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* 算法的連續(xù)模型路徑搜索[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]田立中, 付宜利, 馬玉林, 等. 裝配路徑規(guī)劃中基于動態(tài)坐標(biāo)的A*搜索算法[J]. 計(jì)算機(jī)集成制造系統(tǒng), 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