牟帥,卜慧蛟,張進(jìn),羅亞中*

國防科學(xué)技術(shù)大學(xué) 航天科學(xué)與工程學(xué)院,長沙 410073

面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃方法

牟帥,卜慧蛟,張進(jìn),羅亞中*

國防科學(xué)技術(shù)大學(xué) 航天科學(xué)與工程學(xué)院,長沙 410073

針對(duì)空間站在軌運(yùn)營出現(xiàn)突發(fā)任務(wù)的情況,提出一種基于啟發(fā)式規(guī)則的任務(wù)重規(guī)劃方法,滿足了方案重規(guī)劃的快速響應(yīng)需求。根據(jù)任務(wù)執(zhí)行的連續(xù)性特點(diǎn)和沖突狀態(tài),建立了空間站突發(fā)任務(wù)規(guī)劃領(lǐng)域模型?？紤]重規(guī)劃過程中任務(wù)包含活動(dòng)間復(fù)雜約束關(guān)系傳播的影響,提出了時(shí)間回溯迭代沖突化解策略,同時(shí)依據(jù)任務(wù)執(zhí)行時(shí)間間隔,提出針對(duì)間隔插空的時(shí)間冗余啟發(fā)式規(guī)則?；跁r(shí)間回溯迭代沖突化解策略和時(shí)間冗余啟發(fā)式規(guī)則,對(duì)原任務(wù)執(zhí)行計(jì)劃進(jìn)行實(shí)時(shí)重規(guī)劃,實(shí)現(xiàn)了突發(fā)任務(wù)的快速響應(yīng)。應(yīng)用算例分析表明,提出的重規(guī)劃方法可以成功地滿足空間站突發(fā)任務(wù)規(guī)劃需求,實(shí)現(xiàn)實(shí)時(shí)更新空間站在軌任務(wù)執(zhí)行詳單的目的。

空間站;任務(wù)規(guī)劃;啟發(fā)式;突發(fā)任務(wù);快速響應(yīng)

空間站任務(wù)規(guī)劃是空間站長期運(yùn)營、有效管理的關(guān)鍵技術(shù),當(dāng)前的空間站任務(wù)規(guī)劃研究主要滿足國際空間站運(yùn)營需求。國際空間站已經(jīng)在軌運(yùn)行多年,參加運(yùn)營的主要國家和組織已經(jīng)開發(fā)了多種任務(wù)運(yùn)營規(guī)劃系統(tǒng)。美國約翰遜中心開發(fā)的集成規(guī)劃系統(tǒng)(Integrated Planning System,IPS)是國際空間站的核心任務(wù)規(guī)劃系統(tǒng)[1]。JPL人工智能部開發(fā)了連續(xù)活動(dòng)調(diào)度規(guī)劃執(zhí)行和重規(guī)劃系統(tǒng)[2-3]。歐洲航天局針對(duì)其運(yùn)營艙段,開發(fā)了運(yùn)營準(zhǔn)備與規(guī)劃系統(tǒng)(Operations Preparation and Planning System,OPPS)[4]。但是,上述文獻(xiàn)主要介紹了國際空間站軟件系統(tǒng)的功能架構(gòu),公開的國外文獻(xiàn)中很少有針對(duì)空間站任務(wù)規(guī)劃具體模型和方法的研究論述。

而國內(nèi)在空間站任務(wù)規(guī)劃方面的研究還處在起步階段。文獻(xiàn)[5-6]結(jié)合國外空間站運(yùn)營任務(wù)規(guī)劃概念和典型的空間站任務(wù)規(guī)劃系統(tǒng),對(duì)中國空間站運(yùn)營任務(wù)規(guī)劃關(guān)鍵技術(shù)提出了發(fā)展建議。文獻(xiàn)[7-8]對(duì)空間站長期運(yùn)營任務(wù)規(guī)劃及建模進(jìn)行了研究。文獻(xiàn)[9-10]對(duì)空間站短期任務(wù)規(guī)劃進(jìn)行了分析研究,提出了基于本體模型的任務(wù)規(guī)劃模型和基于時(shí)間迭代的任務(wù)沖突化解策略。

上述研究中沒有考慮空間站任務(wù)執(zhí)行過程中出現(xiàn)突發(fā)情況的影響,而在工程實(shí)際中,空間站在軌設(shè)備可能會(huì)發(fā)生故障,人員操作失誤等也難以完全避免。當(dāng)這些突發(fā)情況發(fā)生時(shí),航天員必須首先處理突發(fā)事件,這樣就會(huì)造成當(dāng)前執(zhí)行任務(wù)延遲或取消,原始的任務(wù)執(zhí)行計(jì)劃便失去了時(shí)效性。所以,尋找一種應(yīng)對(duì)突發(fā)任務(wù)的快速重規(guī)劃方法是十分必要的。在其他領(lǐng)域,文獻(xiàn)[11-13]對(duì)面向動(dòng)態(tài)需求的衛(wèi)星滾動(dòng)式重調(diào)度方法進(jìn)行了研究。文獻(xiàn)[14]解決了高空飛艇的應(yīng)急調(diào)度問題。但是,這些研究主要針對(duì)包含單個(gè)活動(dòng)的觀測任務(wù),對(duì)于時(shí)效性強(qiáng)、包含活動(dòng)多、約束復(fù)雜的空間站在軌運(yùn)營任務(wù),這些方法則不能完全適用。文獻(xiàn)[15-17]對(duì)深空探測器復(fù)雜約束和啟發(fā)式任務(wù)規(guī)劃方法進(jìn)行了研究。但是,這些方法沒有考慮重規(guī)劃過程中約束傳播以及突發(fā)任務(wù)對(duì)原任務(wù)執(zhí)行計(jì)劃帶來的影響,也不能直接應(yīng)用于空間站任務(wù)重規(guī)劃。

本文主要針對(duì)空間站運(yùn)營過程中出現(xiàn)突發(fā)情況時(shí),對(duì)原任務(wù)執(zhí)行計(jì)劃進(jìn)行快速地重新規(guī)劃。提出時(shí)間回溯迭代沖突化解策略,以解決重規(guī)劃過程中復(fù)雜約束關(guān)系傳播造成的影響,提出時(shí)間冗余啟發(fā)式規(guī)則,以實(shí)現(xiàn)對(duì)突發(fā)任務(wù)的快速響應(yīng),并維持原任務(wù)執(zhí)行計(jì)劃的相對(duì)穩(wěn)定性。

1 問題描述

面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃問題是指在空間站在軌運(yùn)行期間,當(dāng)設(shè)備故障、人員操作失誤、外部環(huán)境改變等不確定因素發(fā)生時(shí),快速對(duì)突發(fā)情況進(jìn)行分析處理,并對(duì)任務(wù)執(zhí)行計(jì)劃進(jìn)行重新規(guī)劃。

1.1 重規(guī)劃問題描述

重規(guī)劃問題可以視為一個(gè)快速求解的約束滿足問題,即不僅要求規(guī)劃方案結(jié)果滿足各項(xiàng)約束條件,還要求重規(guī)劃時(shí)間盡可能短并維持原任務(wù)執(zhí)行計(jì)劃的相對(duì)穩(wěn)定性,以實(shí)現(xiàn)對(duì)突發(fā)任務(wù)的快速響應(yīng)。重規(guī)劃問題描述如圖1所示。

圖1 重規(guī)劃問題示意圖Fig.1 Illustration of re-planning problem

初始條件為原在軌任務(wù)執(zhí)行詳單,當(dāng)突發(fā)時(shí)刻(Pop-up Moment)有突發(fā)任務(wù)發(fā)生時(shí),根據(jù)資源等約束條件對(duì)正在執(zhí)行任務(wù)進(jìn)行模型重構(gòu),并應(yīng)用合理有效的規(guī)劃求解策略,對(duì)突發(fā)任務(wù)、重構(gòu)后任務(wù)以及原計(jì)劃執(zhí)行任務(wù)進(jìn)行實(shí)時(shí)重新規(guī)劃,輸出新的、滿足要求的在軌任務(wù)執(zhí)行詳單。

1.2 概念模型描述

文獻(xiàn)[8]應(yīng)用本體模型對(duì)空間站短期任務(wù)規(guī)劃概念進(jìn)行了詳細(xì)描述,建立了任務(wù)、活動(dòng)、資源、約束等概念本體模型,并應(yīng)用屬性集合和關(guān)系集合分別對(duì)各概念模型進(jìn)行描述。本文在其工作基礎(chǔ)上增加了任務(wù)類型,明確了任務(wù)優(yōu)先級(jí)定義,提出了任務(wù)連續(xù)性等概念,建立了面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃模型。

任務(wù)概念描述如下:

式中:M 為任務(wù);dM.I.為任務(wù)編號(hào);NM.N.為任務(wù)名稱;tM.ST.為任務(wù)最早開始時(shí)間;tM.ET.為任務(wù)最晚結(jié)束時(shí)間;EM.P.為任務(wù)優(yōu)先級(jí),取值在0～100范圍內(nèi);OM.OI.為其他任務(wù)信息;SM.T.為任務(wù)類型,并根據(jù)任務(wù)重要級(jí)別分層定義其優(yōu)先級(jí):vCr為5級(jí)突發(fā)型(90～100),vEm為4級(jí)緊急型(70～89),vDa為3級(jí)日常維護(hù)型(50～69),vPa為2級(jí)載荷型(20～49),vUn為1級(jí)未知型(0～19);SM.C.為任務(wù)連續(xù)性類型:vNo為禁斷型,即如果任務(wù)執(zhí)行過程中受到干擾不能連續(xù)執(zhí)行,則該任務(wù)執(zhí)行失敗,放入不可執(zhí)行任務(wù)集合,vAl為允斷型,即任務(wù)在執(zhí)行過程中可以暫停執(zhí)行,而不影響其后續(xù)執(zhí)行和任務(wù)結(jié)果,vNe為重拾型,即如果任務(wù)執(zhí)行過程中受到干擾不能連續(xù)執(zhí)行,其已經(jīng)完成操作會(huì)對(duì)后面操作產(chǎn)生較大影響,不能繼續(xù)執(zhí)行,但是在軌資源和任務(wù)執(zhí)行條件允許該任務(wù)重新執(zhí)行;A為任務(wù)包含活動(dòng)。

活動(dòng)概念描述如下:

式中:dA.I.為活動(dòng)編號(hào);DA.D.為活動(dòng)持續(xù)時(shí)間;tA.S.為活動(dòng)開始時(shí)間;OA.OI.為其他活動(dòng)信息;SA.R.為活動(dòng)間時(shí)序關(guān)系類型:vEq為與關(guān)系任務(wù)同時(shí)發(fā)生,vBe為早于關(guān)系任務(wù)發(fā)生,vAf為晚于關(guān)系任務(wù)發(fā)生;R為活動(dòng)占用資源。

資源概念描述如下:

式中:dR.I.為資源編號(hào);CR.Max.為資源額定容量;pR.P.為資源功耗;QR.Th.為資源散熱;OR.OI.為其他資源信息;SR.T.為資源類型:vSt為平臺(tái)型,vPa為載荷型,vUk為未知型。

1.3 規(guī)劃模型描述

1)設(shè)計(jì)變量

將突發(fā)任務(wù)開始時(shí)刻和由突發(fā)任務(wù)引起原任務(wù)執(zhí)行計(jì)劃中發(fā)生調(diào)整任務(wù)的重新開始時(shí)刻作為設(shè)計(jì)變量。設(shè)計(jì)變量描述如下:

式中:X為設(shè)計(jì)變量;t(i)為第i個(gè)重規(guī)劃任務(wù)開始時(shí)刻;tM.ST.(i)為第i個(gè)重規(guī)劃任務(wù)最早開始時(shí)刻;tM.ET.(i)為第i個(gè)重規(guī)劃任務(wù)最晚結(jié)束時(shí)刻;n為由突發(fā)任務(wù)引起原任務(wù)執(zhí)行計(jì)劃中發(fā)生調(diào)整任務(wù)總數(shù)。

2)約束分析

約束分析主要考慮空間站在軌運(yùn)營功耗、散熱、數(shù)據(jù)傳輸帶寬、資源額定容量、天地通信窗口、活動(dòng)間先驗(yàn)關(guān)系等約束。各項(xiàng)約束描述如下:

式中:t為規(guī)劃時(shí)刻;nw為t時(shí)刻正在執(zhí)行任務(wù)數(shù);pR.P.(i)為t時(shí)刻正在執(zhí)行任務(wù)功耗;pMax為額定功耗;QR.Th.(i)為t時(shí)刻正在執(zhí)行任務(wù)散熱;QMax為額定散熱;bB.W.(i)為t時(shí)刻數(shù)據(jù)傳輸任務(wù)占用帶寬;bMax為額定帶寬;CR.A.(i)為t時(shí)刻資源占用量;tC.C.(j)為第j個(gè)通信任務(wù)執(zhí)行時(shí)間;[tC.S.(j),tC.E.(j)]為通信窗口;m為通信任務(wù)個(gè)數(shù)。

3)目標(biāo)函數(shù)

考慮空間站長期在軌運(yùn)營的安全性與穩(wěn)定性,應(yīng)該盡量減小突發(fā)任務(wù)對(duì)原任務(wù)執(zhí)行計(jì)劃產(chǎn)生的影響,因此本文提出任務(wù)執(zhí)行計(jì)劃穩(wěn)定性指標(biāo)作為規(guī)劃的目標(biāo)函數(shù)。

式中:f為穩(wěn)定性指標(biāo);tri為執(zhí)行時(shí)間發(fā)生改變?nèi)蝿?wù)的重排后開始時(shí)間;ti為執(zhí)行時(shí)間發(fā)生改變?nèi)蝿?wù)的原開始時(shí)間;δm為任務(wù)重要級(jí)別系數(shù);nc為取消執(zhí)行任務(wù)總數(shù)。

2 重規(guī)劃方法

面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃是當(dāng)空間站在軌運(yùn)營有突發(fā)任務(wù)發(fā)生時(shí),對(duì)與突發(fā)任務(wù)存在約束沖突的正在執(zhí)行任務(wù)相關(guān)參數(shù)進(jìn)行實(shí)時(shí)更新,即任務(wù)模型重構(gòu),并對(duì)突發(fā)任務(wù)以及重構(gòu)后任務(wù)進(jìn)行合理再安排,并通過一系列快速、有效的沖突化解策略,得到不存在任何約束沖突的規(guī)劃結(jié)果,實(shí)時(shí)更新在軌任務(wù)執(zhí)行詳單。

2.1 突發(fā)任務(wù)預(yù)處理策略

空間站在軌運(yùn)營有突發(fā)任務(wù)發(fā)生時(shí),首先對(duì)與突發(fā)任務(wù)存在約束沖突的正在執(zhí)行任務(wù)進(jìn)行搜索,再根據(jù)任務(wù)連續(xù)性對(duì)沖突任務(wù)相關(guān)參數(shù)進(jìn)行實(shí)時(shí)更新,建立沖突任務(wù)重構(gòu)模型。

1)沖突任務(wù)搜索。根據(jù)突發(fā)任務(wù)發(fā)生時(shí)刻搜索此時(shí)正在執(zhí)行的任務(wù),依次判斷此時(shí)資源、功耗、散熱、傳輸帶寬等約束條件是否滿足,如果有約束超出額定值,則依據(jù)任務(wù)優(yōu)先級(jí)將其中最小優(yōu)先級(jí)任務(wù)暫停執(zhí)行并放入重構(gòu)集合,循環(huán)判斷各約束條件直至無約束沖突存在。沖突任務(wù)搜索流程如圖2所示。

2)沖突任務(wù)模型重構(gòu)。依次判斷上文得到的重構(gòu)集合中任務(wù)連續(xù)性性質(zhì),若其為禁斷型,則直接取消執(zhí)行該任務(wù),并宣布任務(wù)執(zhí)行失敗,放入不可執(zhí)行任務(wù)集合;若其為允斷型,則依據(jù)未執(zhí)行活動(dòng)對(duì)該任務(wù)包含活動(dòng)、活動(dòng)的持續(xù)時(shí)間以及資源占用等相關(guān)參數(shù)信息進(jìn)行更新,得到重構(gòu)后任務(wù);若其為重拾型,則不考慮其已經(jīng)執(zhí)行過活動(dòng),直接將該任務(wù)整體推遲;并將重構(gòu)后任務(wù)和推遲后任務(wù)放入重規(guī)劃集合。沖突任務(wù)模型重構(gòu)流程如圖3所示。

圖2 沖突任務(wù)搜索流程圖Fig.2 Flow chart of conflict mission search

2.2 時(shí)間回溯迭代沖突化解策略

針對(duì)每個(gè)空間站任務(wù)由多個(gè)活動(dòng)組成,不同任務(wù)包含活動(dòng)間存在一定的約束關(guān)系,在沖突化解過程中,由于任務(wù)執(zhí)行時(shí)間調(diào)整可能會(huì)產(chǎn)生新的約束沖突的情況,提出基于時(shí)間回溯迭代的沖突化解策略。沖突化解流程如圖4所示。

圖4中,M1、M2為執(zhí)行時(shí)間存在重疊的2個(gè)任務(wù),且 M1優(yōu)先級(jí)大于 M2。a11、a12、a13、a14、a15、a16為 M1包含活動(dòng),a21、a22、a23、a24、a25、a26為M2包含活動(dòng),a13與a21存在約束沖突,a15與a24存在約束沖突。時(shí)間回溯迭代沖突化解策略按照一定步長在時(shí)間線上推進(jìn),判斷每一個(gè)時(shí)間節(jié)點(diǎn)上正在執(zhí)行任務(wù)活動(dòng)的資源占用、功耗、散熱和傳輸帶寬等約束條件,如果存在約束沖突,如M2中a24與M1中a15存在約束沖突,則將正在執(zhí)行任務(wù)中優(yōu)先級(jí)最小的任務(wù)(M2)推遲一個(gè)步長,同時(shí)返回到任務(wù)的開始時(shí)刻進(jìn)行回溯迭代,重新判斷每個(gè)時(shí)間節(jié)點(diǎn)上約束情況,直至無約束沖突存在,如M″2所示。

圖3 沖突任務(wù)模型重構(gòu)示意圖Fig.3 Illustration of re-construction of conflict mission model

圖4 時(shí)間回溯迭代沖突化解策略示意圖Fig.4 Illustration of time backtrack iteration strategy

2.3 時(shí)間冗余啟發(fā)式規(guī)則

為了盡量減小突發(fā)任務(wù)對(duì)原任務(wù)執(zhí)行計(jì)劃的影響,應(yīng)盡可能地將2.1節(jié)中得到的重規(guī)劃任務(wù)安排在任務(wù)允許發(fā)生時(shí)間范圍內(nèi)占用資源冗余量最大的時(shí)間段內(nèi)。即遍歷任務(wù)占用資源,在時(shí)間線上找出每種資源冗余量最大時(shí)間段,取幾個(gè)時(shí)間段中最短的時(shí)間范圍,將重規(guī)劃任務(wù)首先安排在該時(shí)間段的起始時(shí)刻,并用時(shí)間回溯迭代沖突化解策略對(duì)所有任務(wù)進(jìn)行約束沖突化解,以得到新的滿足約束條件的在軌任務(wù)執(zhí)行詳單。其具體規(guī)劃流程如圖5所示。圖中:nrp為2.1節(jié)中重規(guī)劃任務(wù)集合中任務(wù)總數(shù);nrw為正在執(zhí)行的重規(guī)劃任務(wù);tx為時(shí)間節(jié)點(diǎn);Δt為時(shí)間步長;T為規(guī)劃結(jié)束時(shí)間。

步驟1 將2.1節(jié)中得到的重規(guī)劃任務(wù)集合中任務(wù)按優(yōu)先級(jí)由大到小排列,并首先安排優(yōu)先級(jí)最大的任務(wù)。

步驟2 根據(jù)重規(guī)劃任務(wù)中最大優(yōu)先級(jí)任務(wù)占用的資源,在時(shí)間線上找到任務(wù)允許發(fā)生時(shí)間范圍內(nèi)每種資源被占用時(shí)間段,從而找出每種資源占用最大冗余時(shí)間段。

步驟3 根據(jù)每種資源占用最大冗余時(shí)間段找出幾個(gè)時(shí)間段中最短的時(shí)間范圍,將重規(guī)劃任務(wù)安排在時(shí)間線上該時(shí)間段的起始時(shí)刻。

步驟4 從重規(guī)劃任務(wù)開始時(shí)刻開始,對(duì)時(shí)間線上每個(gè)時(shí)間迭代步長節(jié)點(diǎn)的約束沖突情況進(jìn)行判斷。

步驟5 若存在約束沖突,則搜索存在約束沖突的正在執(zhí)行任務(wù),并將其中優(yōu)先級(jí)最小任務(wù)的開始時(shí)間推遲一個(gè)時(shí)間步長。

步驟6 若任務(wù)執(zhí)行時(shí)間超出允許發(fā)生時(shí)間范圍,則取消任務(wù)執(zhí)行,放入不可執(zhí)行任務(wù)集合,繼續(xù)執(zhí)行步驟8。否則,執(zhí)行步驟7。

步驟7 迭代時(shí)間返回到該任務(wù)的開始時(shí)刻,并重新對(duì)時(shí)間線上每個(gè)時(shí)間迭代步長節(jié)點(diǎn)的約束沖突情況進(jìn)行判斷,直到規(guī)劃結(jié)束時(shí)間。

步驟8 依據(jù)任務(wù)優(yōu)先級(jí)依次對(duì)重規(guī)劃任務(wù)集合中任務(wù)進(jìn)行安排,直到所有重規(guī)劃任務(wù)安排結(jié)束。

步驟9 輸出更新后的在軌任務(wù)執(zhí)行詳單。

圖5 時(shí)間冗余啟發(fā)式算法流程圖Fig.5 Flow chart of interval time heuristic algorithm

3 算例分析

為驗(yàn)證本文方法的有效性和優(yōu)越性,同時(shí)用本文提出的面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃方法、文獻(xiàn)[10]中應(yīng)用的時(shí)間迭代啟發(fā)式方法和文獻(xiàn)[9]中應(yīng)用的改進(jìn)遺傳算法對(duì)同一個(gè)算例進(jìn)行測試。測試環(huán)境為Windows 7 32位操作系統(tǒng),Intel(R)Core(TM)i7-4790 CPU3.60 GHz,內(nèi)存為4 G,編程環(huán)境為Visual C++6.0。

3.1 算例配置

為方便分析,將任務(wù)周期壓縮,選取24 h內(nèi)執(zhí)行日常維護(hù)、載荷試驗(yàn)等15項(xiàng)完整任務(wù)進(jìn)行分析,其中包含單次執(zhí)行活動(dòng)25項(xiàng),占用儀器、設(shè)備、物資等資源10種,涉及功耗、散熱、活動(dòng)順序等約束條件8種。設(shè)置突發(fā)任務(wù)1項(xiàng),突發(fā)時(shí)刻為10:00,空間站額定功耗為5 000 W,額定散熱能力為4 500 W,時(shí)間迭代步長為0.05 h。

3.2 規(guī)劃結(jié)果

為了更直觀地展現(xiàn)空間站任務(wù)間關(guān)系、活動(dòng)間執(zhí)行順序以及資源約束等關(guān)系,給出3種任務(wù)規(guī)劃方法規(guī)劃后的在軌任務(wù)執(zhí)行詳單信息,如圖6所示。圖中:R1～R10代表10種不同資源;M1～M14和M01代表15個(gè)規(guī)劃任務(wù)(M01代表突發(fā)任務(wù));a1～a23、a91和a92代表任務(wù)包含的25項(xiàng)活動(dòng);灰色框單元代表原任務(wù)執(zhí)行詳單;黑色框單元代表更新后任務(wù)執(zhí)行詳單;紅色單元代表突發(fā)任務(wù)。

為了方便對(duì)比分析3種規(guī)劃方法中不同算法策略對(duì)規(guī)劃結(jié)果的影響,將重規(guī)劃結(jié)果中各項(xiàng)參數(shù)信息統(tǒng)計(jì)如表1所示。

圖6 在軌任務(wù)執(zhí)行詳單示意圖Fig.6 Illustration of onboard mission list

表1 3種不同方法規(guī)劃結(jié)果對(duì)比Table 1 Comparison of planning results of three methods

3.3 結(jié)果分析

1)規(guī)劃結(jié)果任務(wù)詳單分析

將圖6(b)中本文方法規(guī)劃結(jié)果任務(wù)詳單與圖6(a)中原任務(wù)詳單對(duì)比可知,當(dāng)在任務(wù)執(zhí)行過程中有突發(fā)任務(wù)(M01)發(fā)生時(shí),通過本文提出的突發(fā)任務(wù)預(yù)處理策略,首先對(duì)突發(fā)任務(wù)進(jìn)行了安排,同時(shí)暫停執(zhí)行與突發(fā)任務(wù)存在約束沖突的正在執(zhí)行任務(wù)(M3～M6),并對(duì)其進(jìn)行任務(wù)模型重構(gòu),有效減少了沖突任務(wù)直接取消產(chǎn)生的影響。進(jìn)一步可以看出,應(yīng)用本文提出的時(shí)間回溯迭代沖突化解策略,除M5由于任務(wù)本身性質(zhì)取消執(zhí)行外,其余沖突任務(wù)均通過合理地推遲部分原任務(wù)而得到重新安排,顯著提高了任務(wù)執(zhí)行計(jì)劃的穩(wěn)定性。

將圖6(c)中文獻(xiàn)[10]方法規(guī)劃結(jié)果任務(wù)詳單與圖6(a)中原任務(wù)詳單對(duì)比可知,當(dāng)在任務(wù)執(zhí)行過程中有突發(fā)任務(wù)(M01)發(fā)生時(shí),由于該方法沒有對(duì)突發(fā)任務(wù)的預(yù)處理策略和對(duì)重規(guī)劃任務(wù)的回溯迭代過程,所以與突發(fā)任務(wù)存在約束沖突的4項(xiàng)任務(wù)(M3～M6)均取消執(zhí)行,如此將使任務(wù)的完成率明顯降低。

將圖6(d)中文獻(xiàn)[9]方法規(guī)劃結(jié)果任務(wù)詳單與圖6(a)中原任務(wù)詳單對(duì)比可知,該方法與本文方法結(jié)果基本相同,保證了原任務(wù)執(zhí)行計(jì)劃的相對(duì)穩(wěn)定性。

2)3種不同方法結(jié)果對(duì)比分析

從表1中本文方法和文獻(xiàn)[10]方法規(guī)劃結(jié)果數(shù)據(jù)對(duì)比可以看出,雖然本文方法計(jì)算時(shí)間比文獻(xiàn)[10]方法計(jì)算時(shí)間長,但前者規(guī)劃結(jié)果中任務(wù)的完成率明顯高于后者,并且規(guī)劃結(jié)果中穩(wěn)定性指標(biāo)后者顯著高于前者。因此,本文方法比文獻(xiàn)[10]方法具有更好的穩(wěn)定性。

從表1中本文方法和文獻(xiàn)[9]方法規(guī)劃結(jié)果數(shù)據(jù)對(duì)比可以看出,雖然后者的穩(wěn)定性指標(biāo)略優(yōu)于前者,但是其計(jì)算時(shí)間明顯大于前者,計(jì)算效率較低,不能滿足任務(wù)重規(guī)劃快速響應(yīng)的需求。因此,本文方法比文獻(xiàn)[9]方法具有更好的時(shí)效性。

4 結(jié) 論

1)提出的突發(fā)任務(wù)預(yù)處理策略,有效減少了沖突任務(wù)直接取消對(duì)空間站產(chǎn)生的影響。

2)提出的時(shí)間回溯迭代沖突化解策略,顯著提高了空間站任務(wù)執(zhí)行計(jì)劃的穩(wěn)定性。

3)提出的時(shí)間冗余啟發(fā)式規(guī)則,可以有效減少任務(wù)重規(guī)劃時(shí)間。

4)本文方法可以同時(shí)滿足空間站任務(wù)重規(guī)劃快速響應(yīng)和穩(wěn)定性需求,具有一定的工程實(shí)用價(jià)值。

[1] SAINT R.Lessons learned in developing an international planning software system[C]//Proceedings of the 7th International Conference on Space Operations,2002:1-10.

[2] CHIEN S A,KNIGHT R,STECHERT A,et al.Using iterative repair to improve the responsiveness of planning and scheduling[C]//Proceedings of the 5th International Conference on Artificial Intelligence Planning and Scheduling,2000:300-307.

[3] KNIGHT S,RABIDEAU G,CHIEN S,et al.Space exploration through continuous planning[J].IEEE Intelligent Systems,2001,16(5):70-75.

[4] ZOESCHINGER G A,WICKLER M,KOEHLER A,et al.A planning system for payload and system planning of the Columbus module on ISS[C]//Proceedings of the 8th International Conference on Space Operations,2004:1-6.

[5] 羅亞中,林鯤鵬,唐國金.空間站運(yùn)營任務(wù)規(guī)劃技術(shù)評(píng)述[J].載人航天,2012,18(2):7-13.

LUO Y Z,LIN K P,TANG G J.Review on space station mission planning technology[J].Manned Spaceflight,2012,18(2):7-13(in Chinese).

[6] 田坤黌,侯永青.國際空間站運(yùn)營管理體系架構(gòu)分析[J].載人航天,2011,17(1):10-15.

TIAN K H,HOU Y Q.Analysis of international space station operation architecture[J].Manned Spaceflight,2011,17(1):10-15(in Chinese).

[7] LIN K P,LUO Y Z,TANG G J.Optimization of logistics strategies for long-duration space station operation[J].Journal of Spacecraft and Rockets,2014,51(5):1709-1720.

[8] 李志海,侯永青,嚴(yán)厚民,等.空間站長期運(yùn)營任務(wù)規(guī)劃建模初步研究[J].載人航天,2013,19(5):52-58.

LI Z H,HOU Y Q,YAN H M,et al.Preliminary modeling study on long-term operation mission planning of space station[J].Manned Spaceflight,2013,19(5):52-58(in Chinese).

[9] BU H J,ZHANG J,LIN K P,et al.Short-term planning of the space station operation mission based on genetic algorithm[C]//Proceedings of 64th International Astronautical Congress,2013:1-9.

[10] BU H J,ZHANG J,LUO Y Z.Space station short-term mission planning using ontology modelling and time iteration[J].Journal of Systems Engineering and Electronics,2016,27(2):407-421.

[11] VERFAILLIE G,PRALET C,LEMAITRE M.Constraint-based modeling of discrete event dynamic systems[J].Journal of Intelligent Manufacturing,2010,21(1):31-47.

[12] 習(xí)婷,李菊芳.面向動(dòng)態(tài)需求的成像衛(wèi)星滾動(dòng)式重調(diào)度方法研究[J].中國管理科學(xué),2015,23(專輯):269-274.

XI T,LI J F.The rolling horizon method for EOS scheduling with dynamic request[J].Chinese Journal of Management Science,2015,23(Special Issue):269-274(in Chinese).

[13] 王建江,朱曉敏,吳朝波,等.面向應(yīng)急條件的多星動(dòng)態(tài)調(diào)度方法[J].航空學(xué)報(bào),2013,34(5):1151-1164.

WANG J J,ZHU X M,WU C B,et al.Multi-satellite dynamic scheduling method for emergencies[J].Acta Aeronautica et Astronautica Sinica,2013,34(5):1151-1164(in Chinese).

[14] 賀川,邱滌珊,許光,等.面向?qū)Φ爻上裼^測任務(wù)的高空飛艇應(yīng)急調(diào)度[J].航空學(xué)報(bào),2012,33(11):2082-2092.

HE C,QIU D S,XU G,et al.Emergency scheduling of earth-observing imaging tasks on high-altitude airships[J].Acta Aeronautica et Astronautica Sinica,2012,33(11):2082-2092(in Chinese).

[15] 趙凡宇,徐瑞,崔平遠(yuǎn).啟發(fā)式深空探測器任務(wù)規(guī)劃方法[J].宇航學(xué)報(bào),2015,36(5):496-503.

ZHAO F Y,XU R,CUI P Y.Heuristic mission planning approach for deep space explorer[J].Journal of Astronautics,2015,36(5):496-503(in Chinese).

[16] 傅陽光,周成平,王長青,等.考慮時(shí)間約束的無人飛行器航跡規(guī)劃[J].宇航學(xué)報(bào),2011,32(4):749-755.

FU Y G,ZHOU C P,WANG C Q,et al.Path planning for UAV considering time constraint[J].Journal of Astronautics,2011,32(4):749-755(in Chinese).

[17] 王曉暉,李爽.深空探測器約束簡化與任務(wù)規(guī)劃方法研究[J].宇航學(xué)報(bào),2016,37(7):768-774.

WANG X H,LI S.Research on constraint simplification and mission planning method for deep space explorer[J].Journal of Astronautics,2016,37(7):768-774(in Chinese).

Re-planning method for space station pop-up missions

MU Shuai,BU Huijiao,ZHANG Jin,LUO Yazhong*

College of Aerospace Science and Engineering,National University of Defense Technology,Changsha 410073,China

Considering pop-up missions in space station operation,a re-planning method based on heuristic algorithm is proposed to satisfy the requirement for fast responses of mission re-planning.According to the continuity characteristic and conflict condition in mission execution,a model for space station pop-up mission planning domain is constructed.Considering the propagation effects of complicated constraints between the activities of missions,the time backtrack iteration strategy is adopted to solve the conflicts,and then an interval time heuristic algorithm is proposed according to the interval time between missions'execution.A fast response to the pop-up mission is achieved using the time backtrack iteration strategy and the interval time heuristic algorithm to re-plan the missions.The results show that the proposed mission re-planning method can successfully satisfy the requirement for pop-up mission planning and real-time updating of the onboard mission list.

space station;mission planning;heuristic;pop-up mission;fast response

2016-09-19;Revised:2016-10-18;Accepted:2016-12-07;Published online:2016-12-19 16:13

URL:www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

s:National Natural Science Foundation of China(11402295);National Basic Research Program of China(2013CB733100);Natural Science Foundation of Hunan Province of China(2015JJ3020)

V423.7

A

1000-6893(2017)07-320793-08

10.7527/S1000-6893.2016.320793

2016-09-19;退修日期:2016-10-18;錄用日期:2016-12-07;網(wǎng)絡(luò)出版時(shí)間:2016-12-19 16:13

www.cnki.net/kcms/detail/11.1929.V.20161219.1613.002.html

國家自然科學(xué)基金 (11402295);國家“973”計(jì)劃 (2013CB733100);湖南省自然科學(xué)基金 (2015JJ3020)

*通訊作者.E-mail:luoyz@nudt.edu.cn

牟帥,卜慧蛟,張進(jìn),等.面向突發(fā)任務(wù)的空間站任務(wù)重規(guī)劃方法[J].航空學(xué)報(bào),2017,38(7):320793.MU S,BU H J,ZHANG J,et al.Re-planning method for space station pop-up missions[J].Acta Aeronautica et Astronautica Sinica,2017,38(7):320793.

(責(zé)任編輯:張玉)

*Corresponding author.E-mail:luoyz@nudt.edu.cn