陳德相，徐文明，杜智遠(yuǎn)，徐瑞

(1.北京理工大學(xué) 宇航學(xué)院，北京 100081； 2.中國人民解放軍92493部隊(duì)，葫蘆島 125000)

航天器任務(wù)規(guī)劃中資源約束的可分配處理方法

陳德相1，徐文明1，杜智遠(yuǎn)2，徐瑞1

(1.北京理工大學(xué) 宇航學(xué)院，北京 100081； 2.中國人民解放軍92493部隊(duì)，葫蘆島 125000)

面對深空探測過程中環(huán)境的不確定性和擾動，航天器需要利用任務(wù)規(guī)劃技術(shù)實(shí)現(xiàn)自主控制。航天器應(yīng)用規(guī)劃算法時(shí)，需要考慮到執(zhí)行活動時(shí)滿足的時(shí)間約束和資源約束。通過分析資源約束之間的關(guān)系，提出了可重復(fù)資源在規(guī)劃執(zhí)行時(shí)的可分配處理方法，和判斷資源變量是否滿足的可分配性條件。通過航天器仿真算例，驗(yàn)證了可重復(fù)資源的可分配處理方法在規(guī)劃執(zhí)行時(shí)的有效性。

可重復(fù)資源；規(guī)劃執(zhí)行；可分配性；資源約束網(wǎng)絡(luò)

0 引 言

隨著人類對于深空目標(biāo)的探測，在航天器上實(shí)現(xiàn)自主控制的需求也越來越迫切。通過應(yīng)用人工智能理論中的任務(wù)規(guī)劃技術(shù)，可以使得航天器在執(zhí)行空間任務(wù)時(shí)，通過星載自主管理系統(tǒng)處理敏感元件采集到的空間環(huán)境狀態(tài)以及航天器的自身狀態(tài)，并根據(jù)航天器的任務(wù)目標(biāo)自主產(chǎn)生需要執(zhí)行的動作序列，實(shí)現(xiàn)航天器的自主運(yùn)行。

在實(shí)際應(yīng)用規(guī)劃技術(shù)時(shí)，需要考慮到在動作執(zhí)行時(shí)的時(shí)間約束和資源約束是否滿足，并為動作提供確切的執(zhí)行時(shí)間和資源變化值。判定資源約束的有效性時(shí)，可以通過最大流方法計(jì)算資源的數(shù)值范圍，并與資源總量相比較。

航天器執(zhí)行動作時(shí)，受到環(huán)境的不確定性及擾動的影響，規(guī)劃動作不是完全可控的，因此資源相關(guān)動作之間的關(guān)系也將受到實(shí)際執(zhí)行過程的影響，在資源約束不滿足時(shí)將導(dǎo)致規(guī)劃失效。為了滿足航天器規(guī)劃的魯棒性要求，規(guī)劃結(jié)果需要能夠?qū)_動作出動態(tài)響應(yīng)，根據(jù)航天器執(zhí)行情況的反饋，調(diào)整動作的執(zhí)行時(shí)間，保持規(guī)劃的動態(tài)可控性。在執(zhí)行時(shí)確定動作的資源改變量的方法稱為資源的可分配處理，需要在處理規(guī)劃動作的約束時(shí)，判定資源約束的可調(diào)度性。

在Deep Space 1中，NASA-Ame中心針對航天器的規(guī)劃執(zhí)行過程，提出了規(guī)劃執(zhí)行中時(shí)間約束的可調(diào)度性。Muscettola等(1998)[1-2]在規(guī)劃時(shí)生成時(shí)間約束網(wǎng)絡(luò)的可分配形式，并在執(zhí)行時(shí)通過可分配形式動態(tài)確定動作的執(zhí)行時(shí)間。Wallace等(2000)[3]擴(kuò)展了時(shí)間約束的可分配性，提出了規(guī)劃中消耗性資源的可調(diào)度性，結(jié)合時(shí)間約束網(wǎng)絡(luò)討論了資源約束與時(shí)間約束的關(guān)系，并給出了消耗性資源的可分配處理方法及可分配性的判定條件。規(guī)劃中需要處理的資源約束除了消耗性資源，還包括可重復(fù)資源，本文針對可重復(fù)資源討論了可分配性的相關(guān)計(jì)算過程。

分析規(guī)劃中的可重復(fù)資源時(shí)，需要求解規(guī)劃中資源的變化情況。國內(nèi)外學(xué)者對資源調(diào)度問題進(jìn)行了比較深入的研究。Yalcinkaya等(2012)[4]采用時(shí)間表(time table)模型描述資源調(diào)度問題的時(shí)間和資源約束，將其轉(zhuǎn)化為組合優(yōu)化問題進(jìn)行了處理。Nicola(2002)[5]分析了動作集隨時(shí)間變化對資源數(shù)量的影響，采用最大流網(wǎng)絡(luò)描述規(guī)劃中的資源約束，可以計(jì)算資源數(shù)量隨時(shí)間的變化。在國內(nèi)，李玉慶等(2012)[6]研究了航天測控中的資源調(diào)度問題，針對約束優(yōu)化問題建立模型，并采用遺傳算法和蟻群優(yōu)化-模擬退火算法尋求最優(yōu)解。

本文在資源約束網(wǎng)絡(luò)的最大流求解方法的基礎(chǔ)上，討論了航天器可重復(fù)資源的可分配處理方法。首先，介紹在航天任務(wù)的規(guī)劃過程中，資源約束的概念以及資源約束網(wǎng)絡(luò)的表達(dá)形式；然后，討論了可重復(fù)資源的處理過程，并在計(jì)算資源數(shù)量的基礎(chǔ)上，分析了可重復(fù)資源的可分配性及其條件；最后，通過實(shí)際航天器上資源變化的仿真算例，驗(yàn)證了本文算法的有效性。

1 航天器的資源約束模型

1.1 問題提出規(guī)劃中的資源約束

在航天器進(jìn)行連續(xù)任務(wù)規(guī)劃的過程中，自主規(guī)劃系統(tǒng)每執(zhí)行一次規(guī)劃將產(chǎn)生一個(gè)中間規(guī)劃結(jié)果，即包含順序約束的動作集合。驗(yàn)證規(guī)劃結(jié)果的有效性，需要檢驗(yàn)規(guī)劃結(jié)果中動作的時(shí)間約束和資源約束是否滿足。因此在每步規(guī)劃完成后進(jìn)行時(shí)間和資源分配，使規(guī)劃過程中的動作序列成功執(zhí)行。本文中僅討論資源約束，假定規(guī)劃結(jié)果中時(shí)間取值己經(jīng)滿足所有時(shí)間約束。

下面給出規(guī)劃結(jié)果處理過程中的相關(guān)定義。

定義1. 規(guī)劃結(jié)果定義為包含一組有限個(gè)動作的動作集

(1)

其中ai為規(guī)劃結(jié)果中包含的動作，動作間根據(jù)執(zhí)行條件的要求具有邏輯順序，航天器根據(jù)規(guī)劃結(jié)果中的邏輯順序約束執(zhí)行動作。

動作ai可以描述為動作所受約束的集合

(2)

定義2. 資源約束定義為動作執(zhí)行時(shí)需求的資源，表示為

(3)

其中：ai為動作；r為動作ai需求的資源變量；令資源r的數(shù)量為qr，Qr為資源的最大數(shù)量，資源數(shù)量須滿足qr∈[0，Qr]；Δqr為動作ai執(zhí)行后，資源r數(shù)量的改變量。動作ai消耗資源時(shí)Δqr<0，生產(chǎn)資源時(shí)Δqr>0。

在任務(wù)規(guī)劃中，資源可以分為可重復(fù)資源和消耗性資源兩種類型進(jìn)行處理?？芍貜?fù)資源在動作開始時(shí)消耗一定量的資源，并在動作結(jié)束時(shí)釋放相同數(shù)量的資源，因此它的變化可以表示為一系列的階躍變化。消耗性資源的資源量變化是連續(xù)的，可以通過生產(chǎn)或消耗活動變化。

1.2 資源約束網(wǎng)絡(luò)

根據(jù)資源突變之間的時(shí)間關(guān)系，將規(guī)劃結(jié)果中的資源約束全部表示為資源突變后，可以建立資源約束網(wǎng)絡(luò)模型，表述所有規(guī)劃結(jié)果中的資源約束。

定義3. 資源突變定義為資源數(shù)量的瞬時(shí)改變，表示為

(4)

在動作a開始和結(jié)束時(shí)，資源r的瞬時(shí)突變分別表示為資源突變δs和δe，則動作集A中的資源約束可表示為資源突變的集合

(5)

定義4. 資源約束網(wǎng)絡(luò)，規(guī)劃結(jié)果中的資源約束可表示為帶權(quán)有向圖GR=(VR，ER)，定義GR為資源約束網(wǎng)絡(luò)。

在GR中，VR是網(wǎng)絡(luò)頂點(diǎn)的集合，表示規(guī)劃結(jié)果中的資源突變。VR包括所有表示資源突變δ的頂點(diǎn)v，并增加了源點(diǎn)σ和匯點(diǎn)τ，分別表示資源的生產(chǎn)和消耗。對表示資源突變δ的頂點(diǎn)v，根據(jù)δ對資源數(shù)量的改變情況，可以分為以下兩類：

1)生產(chǎn)點(diǎn)VP：該點(diǎn)表示的δ生產(chǎn)資源，即資源數(shù)量改變值Δqr，δ>0，存在與源點(diǎn)σ相連的邊；

2)消耗點(diǎn)VC：該點(diǎn)表示的δ消耗資源，即資源數(shù)量改變值Δqr，δ<0，存在與匯點(diǎn)τ相連的邊。

ER是網(wǎng)絡(luò)邊的集合，表示資源突變間執(zhí)行時(shí)間的關(guān)系或資源改變量，根據(jù)端點(diǎn)的不同，可以分為以下三類：

1)內(nèi)部邊EI=(vi，vj)：表示資源突變δi和δj的時(shí)間關(guān)系為tδi≥tδj，EI從執(zhí)行時(shí)間晚的δi指向執(zhí)行時(shí)間早的δj，邊上的權(quán)值為

(6)

2)生產(chǎn)邊EP=(σ，vi)：表示執(zhí)行資源突變δi時(shí)生產(chǎn)資源，即Δqr，δi>0，邊上的權(quán)值為

(7)

3)消耗邊EC=(vi，τ)：表示執(zhí)行資源突變δi時(shí)消耗資源，即Δqr，δi<0，邊上的權(quán)值為

(8)

這樣，規(guī)劃結(jié)果中的資源約束就表示為資源約束網(wǎng)絡(luò)GR=(VR，ER)，包括資源約束的時(shí)間關(guān)系和資源使用情況。圖1所示的資源約束網(wǎng)絡(luò)表示了包含動作集A的規(guī)劃結(jié)果中的資源約束，其中動作集A={a1，a2，a3}，每個(gè)動作表示為兩個(gè)資源突變點(diǎn)。根據(jù)執(zhí)行動作時(shí)的時(shí)間順序，資源突變點(diǎn)在縱向從上向下分布。

圖1 資源約束網(wǎng)絡(luò)Fig.1 Resource constraint network

在規(guī)劃結(jié)果執(zhí)行時(shí)，系統(tǒng)依據(jù)時(shí)間約束的順序執(zhí)行動作，并根據(jù)動作的資源約束，對資源數(shù)量做出相應(yīng)改變。

(9)

下面分析各部分資源突變對t時(shí)刻資源數(shù)量qr(t)的影響。

(10)

對資源數(shù)量的改變值表示為

(11)

(12)

(13)

圖2 資源約束增量網(wǎng)絡(luò)Fig.2 Resource constraint incremental network

(14)

對資源數(shù)量的改變值表示為

(15)

根據(jù)以上對資源突變各部分的分析，在時(shí)刻t資源數(shù)量的改變值可由下式得出

(16)

隨著執(zhí)行時(shí)間t的增加，規(guī)劃結(jié)果中的動作執(zhí)行結(jié)束，各部分資源突變集也發(fā)生相應(yīng)的變化。

(17)

(18)

1.3 可重復(fù)資源的可分配性條件

在確定性的規(guī)劃結(jié)果中，資源約束的值為固定的值或區(qū)間。在執(zhí)行規(guī)劃動作時(shí)，動作將根據(jù)給定的值或從給定區(qū)間中選擇合適的值作為資源變化量。但在保證事先給定的資源值或區(qū)間滿足資源約束時(shí)，航天器資源未必能夠得到充分利用。通過選擇合適的資源分配方法，在執(zhí)行規(guī)劃結(jié)果的過程中動態(tài)調(diào)整資源突變的數(shù)量，可以更加靈活地利用資源。參考消耗性資源的相關(guān)概念，可重復(fù)資源的可分配性定義如下：

定義5. 可重復(fù)資源的可分配性定義為，在資源約束網(wǎng)絡(luò)實(shí)例化的過程中，當(dāng)任意一個(gè)資源突變在給定范圍中取任意值時(shí)，都能對所有資源突變給定一組值，使得所有資源約束得到滿足。

下面對可重復(fù)資源的可分配性條件進(jìn)行討論。當(dāng)所有資源突變的上限總和小于資源總量時(shí)，則任意一組值都必然滿足所有資源約束，如式(19-1)所示，其中的GR包括了規(guī)劃結(jié)果中的所有動作。

(19-1)

式(19-1)表明了統(tǒng)計(jì)從0時(shí)刻開始規(guī)劃結(jié)果中的所有活動，資源突變值的區(qū)間上限的總和小于資源總量。若在開始規(guī)劃時(shí)資源已被占用一部分，則上式須調(diào)整如下，其中的GR包括了規(guī)劃結(jié)果中的所有動作。

(19-2)

式(19)的條件雖然必然滿足可分配性，但過于嚴(yán)格，若所有資源突變中某一突變僅可取某一個(gè)特定值時(shí)，其它突變?nèi)∪我庵等钥蓾M足所有資源約束，則此時(shí)可分配性仍能得到滿足，且此特定值必為該資源突變的范圍下限，如式(20)所示，其中的GR包括了規(guī)劃結(jié)果中除最后一個(gè)動作的所有動作。

(20)

式(20)成立時(shí)，若取范圍下限的資源突變在執(zhí)行時(shí)間上是最后一個(gè)動作，則在規(guī)劃執(zhí)行過程中，無論前面的動作取區(qū)間內(nèi)的任何值，都能滿足可分配性。

通過分析資源約束網(wǎng)絡(luò)對應(yīng)的時(shí)間約束網(wǎng)絡(luò)中各動作的時(shí)間關(guān)系，可以獲得動作的時(shí)間拓?fù)漤樞颉２煌谙男再Y源，可重復(fù)資源的變化都是瞬時(shí)的。消耗性資源需要根據(jù)對應(yīng)動作的時(shí)間相互關(guān)系確定它們之間互相影響的關(guān)系，而可重復(fù)資源的突變只需要考慮整體上滿足資源約束即可，因此可將整個(gè)規(guī)劃結(jié)果的資源突變統(tǒng)一采用式(20)進(jìn)行檢驗(yàn)，并根據(jù)時(shí)間關(guān)系確定可能最后一個(gè)執(zhí)行的動作有哪些。

2 可重復(fù)資源的可分配處理算法

由于可重復(fù)資源的變化與時(shí)間值沒有直接關(guān)系，只與時(shí)間順序有關(guān)系，因此在分析資源數(shù)量變化時(shí)可以不考慮動作的時(shí)間值及時(shí)間長度。根據(jù)式(20)可得，若在最后一個(gè)動作之前的資源突變未達(dá)到區(qū)間上限，則可將其未使用完的資源在最后一次資源突變時(shí)使用掉，以免其僅使用了等于區(qū)間下限的資源，可表示為下式，其中的GR包括規(guī)劃結(jié)果中除了最后一個(gè)動作的所有動作。

(21)

根據(jù)上述討論，可以給出具有可分配性的可重復(fù)資源的執(zhí)行算法，如圖3所示。

圖3 可分配性的可重復(fù)資源執(zhí)行算法

Fig.3 Dispatchable execution algorithm of reusable resource

在圖3所示算法中，輸入數(shù)據(jù)為規(guī)劃結(jié)果中的動作集合，以及動作集合的執(zhí)行時(shí)間和需滿足的資源約束。執(zhí)行過程中動作的時(shí)間值可由可分配的時(shí)態(tài)規(guī)劃執(zhí)行算法生成，本文不作討論。與資源變化量的值僅有各動作執(zhí)行時(shí)的順序。最終可生成各資源突變的資源變化量。

3 仿真結(jié)果及分析

為了驗(yàn)證算法的有效性，建立了一個(gè)描述航天器動作的仿真實(shí)例，并采用本文提出的算法進(jìn)行了仿真驗(yàn)證。假設(shè)在航天器生成的規(guī)劃結(jié)果中，動作的時(shí)間約束都已得到滿足。動作的時(shí)間約束如圖4所示，且考慮的資源為航天器的存儲器。

圖4 航天器規(guī)劃結(jié)果中動作的時(shí)間約束網(wǎng)絡(luò)Fig.4 Temporal constraint network of activities in spacecraft planning result

假設(shè)航天器中存儲器的資源上限為Qr=30，資源初始值Qr，init=23。且為滿足突發(fā)任務(wù)需求，在初始時(shí)間段[1，4]范圍內(nèi)，資源變量需滿足qr≤20，保留一定的資源余量用于其他任務(wù)。在規(guī)劃結(jié)果中，首先進(jìn)行拍照動作，然后開始在航天器上進(jìn)行一次數(shù)據(jù)處理過程，最后在與地面進(jìn)行通信時(shí)，將數(shù)據(jù)傳往地面。在規(guī)劃結(jié)果的動作集合中，需要滿足的資源約束如表1所示。

表1 航天器規(guī)劃結(jié)果中的資源約束

下面檢測在規(guī)劃執(zhí)行過程中，為動作分配資源的執(zhí)行算法。與判斷資源可分配性時(shí)類似，分段確定動作的資源變化量。在時(shí)間范圍[1，4]內(nèi)，若動作集合{TakePhoto.Begin， TakePhoto.End， ProcessData. Begin}的執(zhí)行時(shí)間分別為2、3、6，則動作TakePhoto.Begin和TakePhoto.End執(zhí)行時(shí)的資源取值可以在給定范圍中任意取值。假設(shè)TakePhoto.Begin資源變化量取2，TakePhoto.End資源變化量取-4，此時(shí)動作ProcessData.Begin作為分段中最后一個(gè)動作，資源變化量可取值為(-2)+(3-2)+[(-4)-(-4)]=-1。

在時(shí)間范圍[4，10]內(nèi)，若動作集合{ProcessData.End， TransmitData.Begin}的執(zhí)行時(shí)間分別為7、11，則動作ProcessData.End的資源取值可以在給定范圍中任意取值。假設(shè)ProcessData.End資源變化量取4，則TransmitData.Begin資源變化量可以取區(qū)間上限2。

在整個(gè)規(guī)劃的執(zhí)行時(shí)間內(nèi)，資源變化過程如圖5所示。由圖示可得，航天器的資源約束始終得到滿足，證明了本文提出算法的有效性。

圖5 航天器規(guī)劃結(jié)果中資源的變化過程Fig.5 Change process of resource in spacecraft planning result

4 結(jié) 論

本文針對航天器環(huán)境不確定性和擾動的需要，分析了可重復(fù)資源的資源突變之間的關(guān)系。通過參考消耗性資源的相關(guān)概念，給出了可重復(fù)資源的可分配性定義及判定條件，并針對最大化利用資源的目標(biāo)，給出了可重復(fù)資源的可分配處理方法，在滿足規(guī)劃中資源約束的同時(shí)，盡可能對資源進(jìn)行了使用。通過航天器的仿真算例，驗(yàn)證了本文算法的有效性。在將來的工作中，我們將根據(jù)結(jié)合規(guī)劃動作在可調(diào)度執(zhí)行時(shí)約束參數(shù)對執(zhí)行過程結(jié)果的影響，在規(guī)劃啟發(fā)式中將航天器資源利用率及靈活性作為評價(jià)函數(shù)考慮。

[1] Muscettola N， Morris P， Tsamardinos I. Reformulating temporal plans for efficient execution[C]∥Proceedings of the 6th Intelligence Conference on Principles of Knowledge Representation and Reasoning. Trento， Italy：[s.n.]， 1998：444-452．

[2] Tsamardinos I， Muscettola N， Morris P. Fast transformation of temporal plans for efficient execution[C]∥Proceedings of the 15th National Conference on Artificial Intelligence. Madison， USA :[s. n.]， 1998:254-261．

[3] Wallace R J， Freuder E C. Dispatchable execution of schedules involving consumable resources[C]∥Proceedings of the Fifth International Conference on Artificial Intelligence Planning Systems. Breckenridge， USA:[s.n.]， 2000:283-290．

[5] Muscettola N. Computing the envelope for stepwise-constant resource allocations[C]∥Principles and Practice of Constraint Programming-CP 2002. Berlin Heidelberg： Springer， 2002:139-154．

[6] 李玉慶，王日新，徐敏強(qiáng)，等.基于改進(jìn)遺傳算法的一類多資源測控調(diào)度問題研究[J].宇航學(xué)報(bào)，2012，33(1):85-90.[Li Y Q，Wang R X，Xu M Q，et al.An improved genetic algorithm for a class of multi-resource range scheduling problem[J]. Journal of Astronautics， 2012，33(1):85-90.]

[責(zé)任編輯：高莎]

Dispatchable Processing Method of Resource Constraint in Spacecraft Mission Planning

CHEN Dexiang1， XU Wenming1, DU Zhiyuan2， XU Rui1

(1.School of Aerospace Engineering， Beijing Institute of Technology， Beijing 100081， China； 2.Unit 92493 of PLA， Huludao 125000， China)

Considering the uncertainty and disturbance of environment in deep space exploration， spacecraft need to use mission planning technology to realize autonomous control. When a spacecraft applies the planning algorithm in aerospace engineering actirities， the time constraints and resource constraints should be considered. By analyzing the relationship between resource constraints， the dispatchable processing method of reusable resources in the execution of planning and the standard to determine whether resource value is dispatchable are proposed. Through the spacecraft simulation example， the dispatchable processing method of reusable resource in planning implementation is demonstrated to be valid．

reusable resource； planning implementation； dispatchability； resource constraint network

2014-10-14

2015-06-01

民用航天預(yù)研項(xiàng)目；國家自然科學(xué)基金(60803051)；國家863計(jì)劃項(xiàng)目

TP18

A

2095-7777(2015)02-0180-06

10.15982/j.issn.2095-7777.2015.02.013

陳德相(1989—)，男，博士生，主要研究方向：航天器自主任務(wù)規(guī)劃。 通信地址：北京理工大學(xué)宇航學(xué)院22信箱(100081) 電話：(010)68913550 E-mail：chendexiangbit@163.com