基于擴(kuò)展?fàn)顟B(tài)深空探測(cè)器任務(wù)規(guī)劃方法

金顥，徐瑞，崔平遠(yuǎn)，朱圣英

（1.北京理工大學(xué) 深空探測(cè)技術(shù)研究所，北京 100081；2.深空自主導(dǎo)航與控制工業(yè)和信息化部重點(diǎn)實(shí)驗(yàn)室，北京 100081）

引 言

深空探測(cè)器自主任務(wù)規(guī)劃技術(shù)是解決遠(yuǎn)距離探測(cè)器自主運(yùn)行問(wèn)題的一項(xiàng)關(guān)鍵技術(shù)[1-4]。由于深空距離遠(yuǎn)、外部環(huán)境復(fù)雜且不確定性強(qiáng)、科學(xué)目標(biāo)的突現(xiàn)性等特點(diǎn)，傳統(tǒng)的地面控制方法已經(jīng)逐漸無(wú)法滿足深空探測(cè)的需求[5-7]，需要探測(cè)器在在軌運(yùn)行過(guò)程中，根據(jù)對(duì)空間環(huán)境的感知和認(rèn)識(shí)及其本身的能力和狀態(tài)，利用智能規(guī)劃理論技術(shù)，依據(jù)一段時(shí)間內(nèi)的任務(wù)目標(biāo)，對(duì)若干可供選擇的活動(dòng)或狀態(tài)及所建模的約束進(jìn)行推理，自動(dòng)地生成一組時(shí)間有序活動(dòng)或狀態(tài)序列來(lái)支持探測(cè)器在未來(lái)一段時(shí)間內(nèi)的自主運(yùn)行[8-10]。探測(cè)器系統(tǒng)復(fù)雜，且存在約束類(lèi)型多、子系統(tǒng)耦合性強(qiáng)、運(yùn)行環(huán)境不確知等特點(diǎn)，傳統(tǒng)規(guī)劃模型難以準(zhǔn)確描述系統(tǒng)的功能特性，從而降低了探測(cè)器在軌自主任務(wù)規(guī)劃的可靠性[11-13]。針對(duì)自主任務(wù)規(guī)劃中系統(tǒng)模型難于精確描述、規(guī)劃效率低等難點(diǎn)，尋求一種新的合適的建模方法成為深空探測(cè)器自主任務(wù)規(guī)劃中亟待解決的問(wèn)題之一。

深空探測(cè)器自主任務(wù)規(guī)劃需要對(duì)問(wèn)題進(jìn)行更簡(jiǎn)潔、明確的描述。通過(guò)將探測(cè)器各子系統(tǒng)的行為表示為時(shí)間的函數(shù)，對(duì)任務(wù)規(guī)劃中涉及的時(shí)間約束關(guān)系進(jìn)行統(tǒng)一處理。并且子系統(tǒng)的狀態(tài)轉(zhuǎn)換由若干事件組成，需要定義在一定的時(shí)間區(qū)間上[14]。如相機(jī)拍照前需要進(jìn)行一系列的準(zhǔn)備事件:主通道開(kāi)啟、大容量上電等。狀態(tài)轉(zhuǎn)移能夠表示時(shí)間線上狀態(tài)之間的邏輯關(guān)系，并且轉(zhuǎn)移的持續(xù)時(shí)間會(huì)對(duì)問(wèn)題的規(guī)模和局部搜索技術(shù)產(chǎn)生影響，為了應(yīng)對(duì)規(guī)劃執(zhí)行時(shí)的不確定性，需要在規(guī)劃過(guò)程中對(duì)狀態(tài)轉(zhuǎn)移進(jìn)行顯式處理。

知識(shí)建模是知識(shí)推理的前提。Fike和Nilsson提出的斯坦福研究委員會(huì)問(wèn)題求解器（STanford Research Institute Problem Solve，STRIPS）[15]由于引入了STRIPS操作符而使得規(guī)劃可以非常容易地進(jìn)行描述和操作。但STRIPS的表達(dá)能力存在很大的局限性，它不能描述具有一定持續(xù)時(shí)間的動(dòng)作，不能描述動(dòng)作間復(fù)雜的約束關(guān)系等。O-Plan和IxTeT規(guī)劃器采用動(dòng)作的概念對(duì)物理系統(tǒng)進(jìn)行描述，并且能夠?qū)r(shí)間約束進(jìn)行處理[16-17]。然而，它們一般默認(rèn)只考慮在動(dòng)作開(kāi)始點(diǎn)和結(jié)束點(diǎn)上需要滿足的約束，這樣的處理方式可能會(huì)影響到模型的準(zhǔn)確性。APSI（Advanced Planning and Scheduling Initiative） 規(guī)劃系統(tǒng)，作為“火星快車(chē)”任務(wù)中自主規(guī)劃系統(tǒng)的開(kāi)發(fā)框架，能夠有效地處理任務(wù)規(guī)劃中復(fù)雜的時(shí)間、資源及參數(shù)約束[18-19]。但是，規(guī)劃器中并沒(méi)有涉及狀態(tài)轉(zhuǎn)換時(shí)間的處理問(wèn)題。在EUROPA（Extensible Universal Remote Operations Planning Architecture）規(guī)劃系統(tǒng)中，將各子系統(tǒng)的活動(dòng)與狀態(tài)等統(tǒng)一采用token的形式進(jìn)行描述，并引入時(shí)間線的概念，直觀地描述token之間的時(shí)間約束關(guān)系[20-21]。模型中采用統(tǒng)一的形式對(duì)動(dòng)作、狀態(tài)、目標(biāo)等概念進(jìn)行描述，在描述探測(cè)器時(shí)并不能真實(shí)地體現(xiàn)各子系統(tǒng)狀態(tài)或活動(dòng)信息。任務(wù)規(guī)劃領(lǐng)域知識(shí)建模技術(shù)的發(fā)展趨向于更合理準(zhǔn)確全面的描述實(shí)際問(wèn)題[22-25]，實(shí)際系統(tǒng)狀態(tài)變化靈活、功能高度復(fù)雜的特性，往往導(dǎo)致模型并不能很好地描述。

本文針對(duì)規(guī)劃問(wèn)題中系統(tǒng)間狀態(tài)轉(zhuǎn)換頻繁及狀態(tài)間切換并非瞬時(shí)完成的特點(diǎn)，引入了擴(kuò)展?fàn)顟B(tài)的概念。建立基于擴(kuò)展?fàn)顟B(tài)的任務(wù)規(guī)劃模型對(duì)各子系統(tǒng)復(fù)雜功能進(jìn)行描述，設(shè)計(jì)基于擴(kuò)展?fàn)顟B(tài)的任務(wù)規(guī)劃算法，對(duì)問(wèn)題搜索空間進(jìn)行削減，實(shí)現(xiàn)降低規(guī)劃步數(shù)，提高規(guī)劃效率的目標(biāo)。最后通過(guò)仿真計(jì)算，驗(yàn)證了模型的合理性及算法的有效性。

1 狀態(tài)知識(shí)表示

狀態(tài)是一個(gè)不斷變化的系統(tǒng)的條件描述，它表示被控系統(tǒng)在一段時(shí)間內(nèi)的行為表現(xiàn)。為了便于對(duì)本文中任務(wù)規(guī)劃方法進(jìn)行描述，首先給出狀態(tài)知識(shí)表示中幾個(gè)基本的概念。

定義1.狀態(tài)變量SV（State Variable）是建模時(shí)對(duì)于系統(tǒng)知識(shí)的抽象結(jié)果，可定義為一個(gè)四元組的形式。

其中:N為該狀態(tài)變量的名稱(chēng)；V是該狀態(tài)變量的取值空間，即狀態(tài)變量的值域，為一個(gè)非空集合；T為該狀態(tài)變量各取值之間的轉(zhuǎn)換規(guī)則或約束；D表示該狀態(tài)變量各取值的持續(xù)時(shí)間。

定義2.狀態(tài)S是狀態(tài)變量在某一個(gè)時(shí)間點(diǎn)或某一時(shí)間區(qū)間上的取值，可用一個(gè)四元組進(jìn)行表示。

其中:N為該狀態(tài)的名稱(chēng)；ts、te、d分別為該狀態(tài)的起始時(shí)間、結(jié)束時(shí)間和持續(xù)時(shí)間，并且均表示為區(qū)間的形式，即ts=[s,s′]，te=[e,e′]，d=[d,d′]，用于應(yīng)對(duì)執(zhí)行過(guò)程中所可能出現(xiàn)的不確定性問(wèn)題。

定義3.狀態(tài)時(shí)間線STL（State Time Line）用于表示系統(tǒng)狀態(tài)變量在規(guī)劃周期內(nèi)取值（即狀態(tài)）隨時(shí)間的變化情況。每一條狀態(tài)時(shí)間線都是系統(tǒng)在規(guī)劃周期內(nèi)的連續(xù)狀態(tài)序列，即

規(guī)劃問(wèn)題的一個(gè)可行解就是一個(gè)狀態(tài)時(shí)間線的集合。定義4.運(yùn)行規(guī)則表示狀態(tài)之間或者狀態(tài)和資源之間的約束關(guān)系。

定義5.基于狀態(tài)時(shí)間線規(guī)劃問(wèn)題P可表示為一個(gè)二元組為

其中:SV表示狀態(tài)變量的集合；OP表示涉及SV中變量的運(yùn)行規(guī)則的集合。

定義6.規(guī)劃解Ω的形式為一個(gè)時(shí)間線集合。

其中:STLk為一條狀態(tài)時(shí)間線，是一個(gè)在時(shí)間上連續(xù)的狀態(tài)序列。

STL0,STL1,···,STLk-1,STLk為滿足規(guī)劃問(wèn)題目標(biāo)及狀態(tài)間同步性約束，并且在時(shí)間關(guān)系上并行的狀態(tài)序列集合。

2 擴(kuò)展?fàn)顟B(tài)知識(shí)描述

由定義可以得到，每一條狀態(tài)時(shí)間線都由連續(xù)排列的狀態(tài)序列組成，用于描述系統(tǒng)狀態(tài)隨時(shí)間的變化情況。而狀態(tài)序列的連續(xù)排列表示系統(tǒng)狀態(tài)的轉(zhuǎn)換是瞬時(shí)完成的，即狀態(tài)轉(zhuǎn)換事件定義在某個(gè)時(shí)間點(diǎn)上，并不考慮該事件本身對(duì)規(guī)劃過(guò)程產(chǎn)生的影響，如圖1所示。但是，對(duì)于實(shí)際任務(wù)規(guī)劃系統(tǒng)來(lái)說(shuō)，每個(gè)狀態(tài)轉(zhuǎn)換描述一個(gè)事件集合，即狀態(tài)轉(zhuǎn)換不可能瞬時(shí)完成，需要一定的持續(xù)時(shí)間，并且可能同樣涉及資源、變量等約束關(guān)系。因此，若是在規(guī)劃中忽略狀態(tài)轉(zhuǎn)換帶來(lái)的影響，可能會(huì)致使規(guī)劃結(jié)果無(wú)法適用于實(shí)際系統(tǒng)，導(dǎo)致執(zhí)行過(guò)程的失敗。

圖1 狀態(tài)轉(zhuǎn)換示意圖Fig.1 Illustration of state transitions

為了更準(zhǔn)確地描述規(guī)劃問(wèn)題，確保規(guī)劃結(jié)果成功執(zhí)行，本文在原有模型的基礎(chǔ)上，引入過(guò)渡狀態(tài)的概念，補(bǔ)充對(duì)于轉(zhuǎn)換事件的建模，如圖2所示。過(guò)渡狀態(tài)鏈接同一時(shí)間線上兩個(gè)不同的狀態(tài)，用于描述不同狀態(tài)之間的轉(zhuǎn)換活動(dòng)。例如，相機(jī)進(jìn)行圖像獲取前需要進(jìn)行一系列準(zhǔn)備動(dòng)作，如主通道開(kāi)啟、大容量上電等。由于這一系列動(dòng)作持續(xù)時(shí)間短、事件數(shù)量多且不可避免，在規(guī)劃中需要對(duì)這一類(lèi)事件進(jìn)行處理。若是對(duì)所有事件都進(jìn)行描述并在規(guī)劃過(guò)程中搜索，會(huì)大大增加問(wèn)題的搜索空間，降低規(guī)劃的效率。于是，考慮這些事件持續(xù)時(shí)間短、與其他時(shí)間線狀態(tài)約束少等特性，特引入過(guò)渡狀態(tài)這一概念，將這一系列事件作為一個(gè)整體對(duì)其進(jìn)行描述。既能滿足對(duì)模型描述的需求，也不會(huì)給規(guī)劃搜索帶來(lái)太大負(fù)擔(dān)。同時(shí)，過(guò)渡狀態(tài)應(yīng)具有下列特點(diǎn):

1）過(guò)渡狀態(tài)的約束關(guān)系中包含較少的邏輯約束。

2）過(guò)渡狀態(tài)的持續(xù)時(shí)間較短或與同時(shí)間線狀態(tài)相比較短。

3）過(guò)渡狀態(tài)在整個(gè)規(guī)劃周期中所占時(shí)間比例一般較小。

圖2 過(guò)渡狀態(tài)示意圖Fig.2 Illustration of transition states

在同一時(shí)間線上，每個(gè)過(guò)渡狀態(tài)的后繼狀態(tài)是唯一確定的。為了達(dá)到削減規(guī)劃搜索空間的目的，本文將過(guò)渡狀態(tài)與其后繼狀態(tài)進(jìn)行組合，并通過(guò)時(shí)間約束關(guān)系將二者進(jìn)行綁定（過(guò)渡狀態(tài)的結(jié)束時(shí)間與其綁定的后繼狀態(tài)的起始時(shí)間相同），作為搜索空間中規(guī)劃操作新的基本對(duì)象。考慮過(guò)渡狀態(tài)的約束關(guān)系中邏輯約束數(shù)量較少，這表明過(guò)渡狀態(tài)被挑選添加到規(guī)劃中的概率會(huì)小于其后繼狀態(tài)的概率。

定義7.擴(kuò)展?fàn)顟B(tài)κ可表示為一個(gè)六元組的形式為

其中:N表示擴(kuò)展?fàn)顟B(tài)的名稱(chēng)；Υ表示后繼狀態(tài)為S′的過(guò)渡狀態(tài)的集合；ts，te，d分別表示κ的起始時(shí)間、結(jié)束時(shí)間和持續(xù)時(shí)間。

通過(guò)擴(kuò)展?fàn)顟B(tài)κ的定義可以看出，過(guò)渡狀態(tài)并不獨(dú)立出現(xiàn)在問(wèn)題的搜索空間中，而是被視為類(lèi)似于κ的一種屬性參與規(guī)劃。另外，擴(kuò)展?fàn)顟B(tài)κ的定義并沒(méi)有對(duì)原有問(wèn)題的搜索空間進(jìn)行擴(kuò)展，合理有效地解決了過(guò)渡狀態(tài)可能引起的搜索空間急劇膨脹的問(wèn)題。針對(duì)上述擴(kuò)展?fàn)顟B(tài)定義，本文設(shè)計(jì)了基于擴(kuò)展?fàn)顟B(tài)任務(wù)規(guī)劃算法，能夠在合理描述實(shí)際物理系統(tǒng)的同時(shí)，較為高效地實(shí)現(xiàn)問(wèn)題規(guī)劃。

3 基于擴(kuò)展?fàn)顟B(tài)規(guī)劃算法

深空探測(cè)器具有多子系統(tǒng)并行、運(yùn)行約束復(fù)雜等特點(diǎn)，狀態(tài)空間搜索會(huì)導(dǎo)致搜索空間指數(shù)爆炸。本文采用規(guī)劃空間搜索策略，針對(duì)擴(kuò)展?fàn)顟B(tài)模型定義過(guò)渡狀態(tài)挑選策略，設(shè)計(jì)基于擴(kuò)展?fàn)顟B(tài)規(guī)劃算法實(shí)現(xiàn)縮減搜索空間、提高規(guī)劃效率的目的。

3.1 缺陷類(lèi)型設(shè)計(jì)

規(guī)劃空間規(guī)劃方法主要是搜索缺陷、挑選缺陷和解決缺陷3部分反復(fù)迭代的過(guò)程。每迭代一步需要進(jìn)行一次約束傳播檢測(cè)，驗(yàn)證規(guī)劃操作的合理性，并在必要時(shí)可以進(jìn)行回溯。整個(gè)規(guī)劃是對(duì)初始部分規(guī)劃不斷迭代求精的過(guò)程，直到搜索出規(guī)劃問(wèn)題的一個(gè)可行解。

在規(guī)劃空間搜索中，缺陷是指導(dǎo)致當(dāng)前部分規(guī)劃不一致的潛在因素。規(guī)劃搜索就是不斷地檢測(cè)當(dāng)前部分規(guī)劃中存在的不一致的因素，并逐步進(jìn)行解決的過(guò)程?？紤]到缺陷的語(yǔ)義和深空探測(cè)器系統(tǒng)復(fù)雜的運(yùn)行約束，這里定義了下述5類(lèi)缺陷:

1）擴(kuò)展?fàn)顟B(tài)缺陷:如果當(dāng)前部分規(guī)劃中存在一個(gè)或多個(gè)擴(kuò)展?fàn)顟B(tài)前提條件未得到滿足，則該部分規(guī)劃存在擴(kuò)展?fàn)顟B(tài)缺陷。

2）未綁定過(guò)渡狀態(tài)缺陷:如果當(dāng)前部分規(guī)劃中存在一個(gè)或多個(gè)未確定過(guò)渡狀態(tài)的擴(kuò)展?fàn)顟B(tài)，則該部分規(guī)劃存在未綁定過(guò)渡狀態(tài)缺陷。

3）變量缺陷:如果當(dāng)前部分規(guī)劃中存在包含一個(gè)或多個(gè)未賦值變量的擴(kuò)展?fàn)顟B(tài)，則該部分規(guī)劃存在變量缺陷。

4）互斥缺陷:如果當(dāng)前部分規(guī)劃中存在同一時(shí)間線，時(shí)間區(qū)間存在交叉的擴(kuò)展?fàn)顟B(tài)，則該部分規(guī)劃存在互斥缺陷。

5）資源缺陷:如果當(dāng)前部分規(guī)劃中資源分配不合理，如擴(kuò)展?fàn)顟B(tài)的資源分配超出該資源的總量，則該部分規(guī)劃存在資源缺陷。

解決缺陷過(guò)程中需要對(duì)挑選出的狀態(tài)進(jìn)行實(shí)例化，而狀態(tài)的實(shí)例化又會(huì)向當(dāng)前候選部分規(guī)劃中引入缺陷。如果一個(gè)候選規(guī)劃中不存在缺陷，那么該候選規(guī)劃就是規(guī)劃問(wèn)題的一個(gè)可行解。

3.2 過(guò)渡狀態(tài)挑選策略

每個(gè)擴(kuò)展?fàn)顟B(tài)對(duì)應(yīng)一個(gè)可能的過(guò)渡狀態(tài)集合，針對(duì)這一特點(diǎn)，本文設(shè)計(jì)了下列4種過(guò)渡狀態(tài)挑選策略:

1）約束導(dǎo)向策略，與擴(kuò)展?fàn)顟B(tài)相關(guān)的約束決定它綁定的過(guò)渡狀態(tài)。

2）最小缺陷導(dǎo)向策略，首先選擇引入缺陷最少的過(guò)渡狀態(tài)，如果有兩個(gè)及以上的過(guò)渡狀態(tài)滿足最佳選擇，它們將按任意順序進(jìn)行選擇或用其他方法進(jìn)行評(píng)估。

3）資源導(dǎo)向策略，首先選擇涉及資源類(lèi)型最少的過(guò)渡狀態(tài)，如果有兩個(gè)及以上的過(guò)渡狀態(tài)滿足最佳選擇，它們將按任意順序進(jìn)行選擇或用其他方法進(jìn)行評(píng)估。

4）隨機(jī)策略，如果對(duì)于過(guò)渡狀態(tài)選擇順序沒(méi)有特定需求，則按隨機(jī)策略進(jìn)行選擇。

為了獲取合適的過(guò)渡狀態(tài)，本文對(duì)上述策略進(jìn)行組合，并且采用資源導(dǎo)向及隨機(jī)策略作為二次評(píng)估標(biāo)準(zhǔn)，保證了搜索策略的完備性。具體方法如圖3所示。

圖3 過(guò)渡狀態(tài)搜索流程Fig.3 The process of transition state searching

3.3 規(guī)劃搜索算法

本文的規(guī)劃算法采用規(guī)劃空間搜索的策略，在其架構(gòu)的基礎(chǔ)上，根據(jù)擴(kuò)展?fàn)顟B(tài)的定義和結(jié)構(gòu)特點(diǎn)，同時(shí)考慮上述過(guò)渡狀態(tài)選擇策略，設(shè)計(jì)了表1所示的基于擴(kuò)展?fàn)顟B(tài)的任務(wù)規(guī)劃算法。該算法能夠有效地減少由于算法缺陷挑選順序不合理和引發(fā)的回溯，提高算法的效率。

表1 基于擴(kuò)展?fàn)顟B(tài)規(guī)劃算法Table 1 Planning algorithm based on extensible states

4 仿真計(jì)算結(jié)果及分析

為了驗(yàn)證算法的有效性，建立了一個(gè)描述深空探測(cè)器領(lǐng)域的模型，并采用本文提出的算法進(jìn)行了仿真驗(yàn)證。選取美國(guó)航空航天局在“深空1號(hào)”上已在軌驗(yàn)證的規(guī)劃算法Europa算法進(jìn)行比較，通過(guò)與Europa算法仿真結(jié)果進(jìn)行對(duì)比，驗(yàn)證了該算法能夠提高規(guī)劃搜索的效率，進(jìn)一步證明了該模型的合理性和有效性。

本文對(duì)深空探測(cè)器任務(wù)規(guī)劃系統(tǒng)進(jìn)行建模。每個(gè)狀態(tài)變量描述一個(gè)探測(cè)器子系統(tǒng)，如推進(jìn)子系統(tǒng)，太陽(yáng)帆板子系統(tǒng)等。同時(shí)，將科學(xué)載荷亦作為子系統(tǒng)進(jìn)行建模，每一種載荷視為一個(gè)子系統(tǒng)模型，并將載荷的操作作為規(guī)劃問(wèn)題的目標(biāo)，例如導(dǎo)航相機(jī)的拍照操作。在實(shí)現(xiàn)目標(biāo)獲取規(guī)劃解的過(guò)程中，主要處理下列幾種約束關(guān)系:

1）狀態(tài)同步約束:例如在拍照前，探測(cè)器的姿態(tài)需要指向所要拍攝的目標(biāo)，對(duì)地通信時(shí)同樣需要姿態(tài)系統(tǒng)保證一定的指向。

2）變量約束:探測(cè)器機(jī)動(dòng)的角度應(yīng)與下一時(shí)刻姿態(tài)的指向相對(duì)應(yīng)。

3）資源約束:能源的最大值是一定的，任何時(shí)刻，狀態(tài)消耗能源的總和不能超過(guò)能源最大值等。

考慮上述建模方法和約束關(guān)系，該模型包括11個(gè)子系統(tǒng)，共包含56個(gè)狀態(tài)模型和92個(gè)約束關(guān)系。

本文選取深空探測(cè)器領(lǐng)域中10個(gè)不同的問(wèn)題進(jìn)行了仿真測(cè)試，結(jié)果如圖4～5所示。由于測(cè)試問(wèn)題按序號(hào)順序所包含的目標(biāo)的數(shù)量是逐漸增多的，故兩種模型的計(jì)算處理時(shí)間是遞增的。并且，為避免出現(xiàn)偶然性，本文的測(cè)試用例中對(duì)每個(gè)問(wèn)題統(tǒng)計(jì)其10次計(jì)算的平均值。

圖4 運(yùn)行時(shí)間結(jié)果曲線Fig.4 Computational results of runtime curves

由于過(guò)渡狀態(tài)的引入，對(duì)于同一個(gè)規(guī)劃問(wèn)題能夠有效地削減問(wèn)題搜索空間，減少規(guī)劃過(guò)程中的搜索對(duì)象，提高規(guī)劃搜索的效率。通過(guò)仿真結(jié)果可以看出，采用擴(kuò)展?fàn)顟B(tài)算法的處理時(shí)間要低于采用Europa算法的處理時(shí)間，且隨著問(wèn)題中所含目標(biāo)數(shù)量的增多，后者運(yùn)行時(shí)間增加的速率亦超過(guò)前者。同時(shí)，過(guò)渡狀態(tài)對(duì)一系列狀態(tài)轉(zhuǎn)換事件進(jìn)行統(tǒng)一描述，可以減少規(guī)劃迭代步數(shù)，從而進(jìn)一步降低規(guī)劃的時(shí)間消耗，使得擴(kuò)展?fàn)顟B(tài)算法相比Europa算法能夠較快獲得規(guī)劃結(jié)果。從仿真結(jié)果可得，基于擴(kuò)展?fàn)顟B(tài)算法的規(guī)劃步數(shù)也全部低于Europa算法，如圖5所示，可以看出，針對(duì)同一領(lǐng)域中不同的問(wèn)題，前者的規(guī)劃步數(shù)均近似等于后者的一半。仿真試驗(yàn)結(jié)果表明，基于擴(kuò)展?fàn)顟B(tài)規(guī)劃算法能夠減少無(wú)效的規(guī)劃步數(shù)，降低規(guī)劃搜索時(shí)間，有效地提高算法的求解速度。

圖5 規(guī)劃步數(shù)結(jié)果曲線Fig.5 Computational results of planning steps

5 結(jié) 論

本文針對(duì)深空探測(cè)器任務(wù)規(guī)劃中系統(tǒng)功能復(fù)雜、狀態(tài)轉(zhuǎn)換頻繁且并非瞬時(shí)完成等問(wèn)題，引入過(guò)渡狀態(tài)的定義，并在此基礎(chǔ)上提出了擴(kuò)展?fàn)顟B(tài)的概念，縮減了問(wèn)題搜索空間，優(yōu)化了規(guī)劃搜索過(guò)程。通過(guò)分析擴(kuò)展?fàn)顟B(tài)的結(jié)構(gòu)特點(diǎn)，設(shè)計(jì)了過(guò)渡狀態(tài)挑選策略，并提出基于擴(kuò)展?fàn)顟B(tài)的規(guī)劃搜索算法。最后針對(duì)深空探測(cè)器任務(wù)規(guī)劃系統(tǒng)進(jìn)行建模仿真，并選用Europa算法進(jìn)行對(duì)比實(shí)驗(yàn)。數(shù)值仿真結(jié)果驗(yàn)證了本文的算法能夠有效地減少規(guī)劃過(guò)程中的規(guī)劃步數(shù)，提高任務(wù)規(guī)劃的效率。