馬 碩，馬亞平

（1.國(guó)防大學(xué)，北京 100091；2.解放軍92232 部隊(duì)，北京 100161）

0 引言

在復(fù)雜的戰(zhàn)爭(zhēng)條件下，作戰(zhàn)單元面對(duì)的將是開放、動(dòng)態(tài)、不確定的環(huán)境，這對(duì)發(fā)展智能化任務(wù)規(guī)劃系統(tǒng)提出了更高的要求。特別是對(duì)于無(wú)人系統(tǒng)，如何在復(fù)雜的戰(zhàn)場(chǎng)環(huán)境中降低對(duì)人員操作的依賴性，是亟待解決的重要問(wèn)題。為此，智能無(wú)人系統(tǒng)的任務(wù)規(guī)劃技術(shù)也從預(yù)編程生成任務(wù)關(guān)聯(lián)動(dòng)作，向在未知環(huán)境中自主完成作戰(zhàn)任務(wù)的方向發(fā)展。

根據(jù)思維方式的不同，現(xiàn)代作戰(zhàn)籌劃方法一般分為逆向作戰(zhàn)籌劃方法和正向作戰(zhàn)籌劃方法兩大類［1］。分層任務(wù)網(wǎng)絡(luò)方法HTN 是一種層次化的規(guī)劃框架，規(guī)劃的目的是完成某一任務(wù)集合，規(guī)劃的過(guò)程是遞歸將非原子任務(wù)分解，直到出現(xiàn)可以直接執(zhí)行規(guī)劃動(dòng)作就能完成的原子任務(wù)為止［2］。HTN 對(duì)任務(wù)進(jìn)行逐層分解細(xì)化的處理方法，體現(xiàn)了“自上而下”、“由粗到精”的正向作戰(zhàn)籌劃思維模式，已在作戰(zhàn)任務(wù)規(guī)劃領(lǐng)域得到了應(yīng)用［3-5］，但HTN 不能根據(jù)任務(wù)目標(biāo)進(jìn)行決策推理生成作戰(zhàn)決策方案，沒(méi)有提供逆向推理規(guī)劃?rùn)C(jī)制，因此，也限制了HTN 在軍事領(lǐng)域的應(yīng)用范圍。此外，HTN 方法要求建立問(wèn)題領(lǐng)域完備的知識(shí)模型，處理方法需要覆蓋任務(wù)執(zhí)行過(guò)程中各種可能出現(xiàn)的狀況，否則將導(dǎo)致任務(wù)規(guī)劃失敗，這對(duì)HTN 使用人員開展問(wèn)題領(lǐng)域建模工作，特別是在動(dòng)態(tài)、不確定的任務(wù)執(zhí)行環(huán)境條件下建模，提出了很高的要求。

在HTN 基礎(chǔ)上，提出一種新的智能規(guī)劃方法—分層目標(biāo)任務(wù)網(wǎng)絡(luò)HGTN，給出了HGTN 的形式化定義和求解算法。HGTN 在保持HTN 的分層任務(wù)分解能力的同時(shí)，還具備基于目標(biāo)的任務(wù)推理規(guī)劃?rùn)C(jī)制，并在一定程度上改進(jìn)了HTN 方法的適應(yīng)性。

1 分層目標(biāo)任務(wù)網(wǎng)絡(luò)HGTN

1.1 HGTN 形式化定義

定義1：HGTN 任務(wù)網(wǎng)絡(luò)是形如tn=（T，C）的二元組，其中T 為有限任務(wù)節(jié)點(diǎn)集合，C 為任務(wù)節(jié)點(diǎn)的約束關(guān)系集合。每個(gè)節(jié)點(diǎn)t∈T 表示一個(gè)任務(wù)，可以是原子任務(wù)、目標(biāo)任務(wù)或組合任務(wù)（compound task）。關(guān)于操作（operation）和原子任務(wù)（atom task）的定義與HTN 定義相同。

定義2：HGTN 目標(biāo)任務(wù)（goal-based task）是一個(gè)二元組，t=（head（t），goal（t）），表示一項(xiàng)需要完成的非原子任務(wù)活動(dòng)，通過(guò)描述任務(wù)所要達(dá)成的目標(biāo)（goal）實(shí)現(xiàn)對(duì)任務(wù)的定義。式中，head（t）語(yǔ)法形式為nt（x1，…，xk），nt 是唯一的方法標(biāo)識(shí)符，（x1，…，xk）是所有在goal（t）中任意地方出現(xiàn)的變量符號(hào)。goal（t）表示任務(wù)t 的目標(biāo)，通過(guò)基文字集（ground literals set）的DNF（析取范式）公式表示。

定義3：HGTN 組合任務(wù)（compound task）是由多個(gè)原子任務(wù)或目標(biāo)任務(wù)組合而成的任務(wù)。

定義4：HGTN 方法（method）是一個(gè)四元組，m=（head（m），task（m），precond（m），subtasknet（m）），描述了對(duì)非原子任務(wù)的分解方法。式中，head（m）語(yǔ)法形式為nm（x1，…，xk），nm 是唯一的方法標(biāo)識(shí)符，（x1，…，xk）是所有在方法m 中任意地方出現(xiàn)的變量符號(hào)；task（m）為組合任務(wù)或目標(biāo)任務(wù)；文字集合precond（m）是方法的前提條件；subtasknet（m）是通過(guò)方法m 分解后的子任務(wù)網(wǎng)絡(luò)，子任務(wù)中可以包括原子任務(wù)、目標(biāo)任務(wù)或組合任務(wù)。

定義5：設(shè)m 為一個(gè)方法實(shí)例，t 為一個(gè)組合任務(wù)，如果task（m）=head（t），則m 與t 相關(guān)（relevant）。

定義6：設(shè)m 為一個(gè)方法實(shí)例，t 為一個(gè)目標(biāo)任務(wù)，goal（subtasknet（m））為子任務(wù)列表中目標(biāo)任務(wù)的目標(biāo)集合，如果goal（subtasknet（m））∩goal（t）≠?，則m 與t 相關(guān)。

定義7：HGTN 規(guī)劃域（planning domain）是形如D=（D'，M）的二元組，其中，D' 是經(jīng)典規(guī)劃領(lǐng)域模型［6］，M 是HGTN 方法集合。

定義8：HGTN 規(guī)劃問(wèn)題（planning problem）是一個(gè)三元組triple P=（D，S0，tn），其中，D 是規(guī)劃域，S0是初始狀態(tài)，tn=（T，C）是一個(gè)HGTN 任務(wù)網(wǎng)絡(luò)。

定義9：令規(guī)劃π 為規(guī)劃問(wèn)題P 的一個(gè)解，則規(guī)劃解π 滿足以下情況：

情況1：任務(wù)網(wǎng)絡(luò)tn 為空，此時(shí)如果規(guī)劃解π為空，則π 是P 的解。

情況2：存在t 為T 的一個(gè)無(wú)前驅(qū)（no predecessors）原子任務(wù)節(jié)點(diǎn)，如果操作a 在狀態(tài)S0下可作用于t，設(shè)π'為HGTN 規(guī)劃問(wèn)題（D，γ（S0，a），（T '，C'））的解，則＜a，π'＞是規(guī)劃問(wèn)題P 的解（符號(hào)＜＞表示序列）。式中，T'=T-{t}，C'是C 中關(guān)于T'的約束關(guān)系。

情況3：存在t 為T 的一個(gè)無(wú)前驅(qū)組合任務(wù)節(jié)點(diǎn)，設(shè)方法實(shí)例m 在狀態(tài)S0下可作用于t，且與t 相關(guān)，將節(jié)點(diǎn)t 從T 中刪除，在t 的位置上插入subtasknet（m）（先前作用于節(jié)點(diǎn)t 的約束條件作用于subtasknet（m）中的每個(gè)節(jié)點(diǎn)），形成的新任務(wù)網(wǎng)絡(luò)為tn'，如果π 為規(guī)劃問(wèn)題（D，S0，tn'）的解，則π 是P 的解。

1.2 HGTN 規(guī)劃算法GTDP

根據(jù)HGTN 的相關(guān)定義，設(shè)計(jì)規(guī)劃算法GTDP（Goal-Task Decomposition Planner）偽代碼如圖1 所示。

圖1 HGTN 規(guī)劃算法GTDP的流程描述

基本流程如下：

如果tn 為空集，則表示所有任務(wù)已完成，因此，GTDP 返回當(dāng)前規(guī)劃π。否則，GTDP 選擇一個(gè)無(wú)前驅(qū)任務(wù)節(jié)點(diǎn)t∈tn；如果t 是一個(gè)原子任務(wù)，在當(dāng)前狀態(tài)下可用的操作集合中（如果集合為空，則任務(wù)無(wú)法完成，規(guī)劃失?。稳∫粋€(gè)操作實(shí)例（instance），將其加入當(dāng)前計(jì)劃π 動(dòng)作序列后遞歸調(diào)用GTDP。如果t 不是原子任務(wù)，則在當(dāng)前狀態(tài)下可用的方法集合中取一個(gè)方法實(shí)例，任務(wù)子網(wǎng)絡(luò)替換任務(wù)t 后遞歸調(diào)用GTDP。

定理1（GTDP 正確性soundness）：設(shè)P=（D，S0，tn）是一個(gè)HGTN 規(guī)劃問(wèn)題，則任何由算法GTDP（D，S0，＜tn>，＜>）所返回的規(guī)劃π 都是規(guī)劃問(wèn)題P的解。

證明：根據(jù)HGTN 定義，采用歸納法證明。設(shè)GTDP 生成的規(guī)劃解π 的長(zhǎng)度為n，即π=＜a1，a2，…，an＞。

當(dāng)n=0 時(shí)，π=?。當(dāng)tn=?，或當(dāng)找不到與任務(wù)相關(guān)的操作或方法時(shí)GTDP 返回failure。

假設(shè)規(guī)劃＜a1，a2，…，ak，πk>（k＜n）是問(wèn)題P 的解，πk是問(wèn)題P'=（D，Sk，tnk）的解（其中，Sk=γ（γ（γ（S0，a1），a2），…，ak）=γ（S0，＜a1，a2，…，ak＞）；tnk為GTDP 在生成ak操作解時(shí)，所生成的任務(wù)網(wǎng)絡(luò)）。則算法GTDP（D，Sk，tnk，＜a1，a2，…，ak＞）在執(zhí)行過(guò)程中，當(dāng)tnk中存在無(wú)前驅(qū)的原子任務(wù)節(jié)點(diǎn)，且存在ak+1是與t 相關(guān)的、當(dāng)前狀態(tài)下可用的操作集合中的一個(gè)操作實(shí)例，根據(jù)定義8，＜ak+1，πk+1＞為問(wèn)題P'=（D，Sk，tnk）的解，因此，＜a1，a2，…，ak，ak+1，πk+1＞為問(wèn)題P 的解；當(dāng)tnk中存在無(wú)前驅(qū)的組合任務(wù)節(jié)點(diǎn)，且存在m是與t 相關(guān)的、在狀態(tài)S 下可用的方法實(shí)例，子任務(wù)網(wǎng)絡(luò)插入后形成新的任務(wù)網(wǎng)絡(luò)tnk'，根據(jù)定義8，問(wèn)題P"=（D，Sk，tnk'）的解πk"即為問(wèn)題P'的解，因此，＜a1，a2，…，ak，πk"＞是問(wèn)題P 的解。由于GTDP 計(jì)算過(guò)程是遞歸迭代的，因此，GTDP（D，S0，＜tn>，＜>）所返回的規(guī)劃π 是規(guī)劃問(wèn)題P 的解。

定理2（GTDP 完備性completeness）：設(shè)P=（D，S0，tn）是一個(gè)HGTN 規(guī)劃問(wèn)題，Π 是P 的所有解的集合，對(duì)于每個(gè)π∈Π，GTDP 至少有一條執(zhí)行路徑對(duì)應(yīng)π。

證明：采用歸納法證明，設(shè)π=＜a1，a2，…，an＞是規(guī)劃問(wèn)題P 的解。

當(dāng)n=0 時(shí)，π=?。在GTDP 算法中，當(dāng)tn=?，或當(dāng)找不到與任務(wù)相關(guān)的操作或方法時(shí)返回failure。

假設(shè)GTDP 生成規(guī)劃解π'的前k 項(xiàng)與π 的前k 項(xiàng)＜a1，a2，…，ak>相同（k＜n），且對(duì)應(yīng)的任務(wù)網(wǎng)絡(luò)tnk也相同。由于π 是P 的解，因此，任務(wù)網(wǎng)絡(luò)tnk，或通過(guò)相關(guān)方法集合分解后的任務(wù)網(wǎng)絡(luò)中應(yīng)包含與操作ak+1相關(guān)的原子任務(wù)。則根據(jù)算法1，GTDP（D，Sk，tnk，＜a1，a2，…，ak＞）在執(zhí)行過(guò)程中（其中，Sk=γ（γ（γ（S0，a1），a2），…ak）=γ（S0，＜a1，a2，…，ak＞）），當(dāng)tnk包含與操作ak+1相關(guān)的原子任務(wù)時(shí)，GTDP 返回的解為＜a1，a2，…，ak，ak+1＞；否則，由于存在相關(guān)的方法集合mk 可以分解得到與操作ak+1相關(guān)的原子任務(wù)，因此，存在一條GTDP 的執(zhí)行路徑，使得GTDP 選擇的任務(wù)相關(guān)方法集合與mk 相同，并返回解＜a1，a2，…，ak，ak+1＞。由于GTDP 計(jì)算過(guò)程是遞歸迭代的，因此，對(duì)于每個(gè)π∈Π，GTDP 至少存在一條執(zhí)行路徑對(duì)應(yīng)π。

1.3 GTDP 算法擴(kuò)展

1.3.1 啟發(fā)式搜索算法HGTDP

傳統(tǒng)HTN 規(guī)劃方法處理待分解的任務(wù)，采用的是按照指定的任務(wù)類型進(jìn)行替代的方式，無(wú)法引入搜索信息，只能采用盲目搜索方法，如SHOP2 等［7］。當(dāng)任務(wù)網(wǎng)絡(luò)中的任務(wù)均為原子任務(wù)和目標(biāo)任務(wù)時(shí)，原子任務(wù)的正效果effect+相當(dāng)于任務(wù)的目標(biāo)，因此，原子任務(wù)本身也可以作為一個(gè)目標(biāo)任務(wù)，從系統(tǒng)當(dāng)前狀態(tài)S 到目標(biāo)G，可以通過(guò)設(shè)計(jì)合理的啟發(fā)函數(shù)h（u），進(jìn)一步提高GTDP 算法的求解速度。HGTDP（Heuristic Goal-Task Decomposition Planner）算法偽代碼如圖2 所示。

算法2 與算法1 的主要區(qū)別，在于引入啟發(fā)函數(shù)h（u）后，將算法1 中行8、行11 中非確定性的選擇方式，轉(zhuǎn)換為根據(jù)啟發(fā)函數(shù)所計(jì)算的啟發(fā)值大小進(jìn)行排序，優(yōu)先執(zhí)行啟發(fā)值大的操作或方法。因此，算法2 性能優(yōu)劣很大程度上取決于啟發(fā)函數(shù)的設(shè)計(jì)，可根據(jù)具體領(lǐng)域問(wèn)題特點(diǎn)設(shè)計(jì)專有的啟發(fā)函數(shù)，也可以使用領(lǐng)域無(wú)關(guān)的啟發(fā)函數(shù)（如快速前向規(guī)劃器FF-planner［8］所使用的放松圖啟發(fā)函數(shù)）。

1.3.2 目標(biāo)推理規(guī)劃算法GTIDP

當(dāng)目標(biāo)任務(wù)無(wú)對(duì)應(yīng)的相關(guān)方法時(shí)，設(shè)當(dāng)前規(guī)劃問(wèn)題P=（D，S0，tn），以狀態(tài)S0為初始狀態(tài)，D 為規(guī)劃域，任務(wù)t 的目標(biāo)goal（t）為規(guī)劃目標(biāo)g，形成一個(gè)經(jīng)典規(guī)劃問(wèn)題P'=（D，S0，g），此時(shí)可以采用經(jīng)典規(guī)劃中的快速規(guī)劃方法（如FF-planner 等）求解。

GTIDP（Goal-Task Inferring and Decomposition Planner）偽代碼如圖3 所示。

圖3 GTIDP 的流程描述

2 基于HGTN 的作戰(zhàn)任務(wù)規(guī)劃方法

無(wú)人水下航行器（Unmanned Underwater Vehicle，UUV）在水雷戰(zhàn)等海上作戰(zhàn)領(lǐng)域得到了日益廣泛的應(yīng)用［9］。以UUV 執(zhí)行水下布雷任務(wù)為例［10］，說(shuō)明基于HGTN 的作戰(zhàn)任務(wù)規(guī)劃基本流程。示例語(yǔ)法格式參照HTN 以及PDDL［11］的相關(guān)定義。

2.1 建立規(guī)劃域D

根據(jù)定義，HGTN 的規(guī)劃域D 包括操作O 和方法M。操作描述作戰(zhàn)行動(dòng)執(zhí)行的約束以及效果，是可由作戰(zhàn)單元直接執(zhí)行的動(dòng)作，方法則描述了作戰(zhàn)任務(wù)分解的規(guī)則。接到布雷作戰(zhàn)命令后，通常需要開展布雷戰(zhàn)術(shù)計(jì)算（包括數(shù)量和位置計(jì)算等）、運(yùn)輸、布放、投送、回收等一系列子任務(wù)，因此，“布雷任務(wù)”可以作為一項(xiàng)組合任務(wù)，根據(jù)領(lǐng)域?qū)＜业慕?jīng)驗(yàn)知識(shí)或相關(guān)條例規(guī)定，使用相應(yīng)的方法進(jìn)行任務(wù)細(xì)化分解，見(jiàn)圖4 所示。

圖4 布雷任務(wù)方法示例

方法seamine_laying 對(duì)應(yīng)“布雷任務(wù)”，包括3個(gè)全序子任務(wù)：輔助戰(zhàn)術(shù)計(jì)算任務(wù)tactical_aids（可通過(guò)調(diào)用外部函數(shù)實(shí)現(xiàn)）、水雷布放任務(wù)mine_at（把水雷?mn 布放到指定位置點(diǎn)）以及回收UUV 任務(wù)uuv_at（UUV?uv 返回至回收點(diǎn)?recoverypoint）。前提條件是：水雷布放點(diǎn)?endpoint 在雷區(qū)?mf 內(nèi)，回收點(diǎn)?Recoverypoint 在布雷方控制區(qū)?cf 內(nèi)，且水雷?mn 和UUV?un 處于可用狀態(tài)。

水雷布放任務(wù)mine_at 可以作為組合任務(wù)，按HTN 的方式對(duì)其進(jìn)一步分解為一系列子任務(wù)。也可以作為HGTN 目標(biāo)任務(wù)，見(jiàn)圖5 所示。

水雷布放任務(wù)方法（將水雷?mn 從區(qū)域?cf 中的貯存點(diǎn)?storagepoint，經(jīng)由UUV 入水點(diǎn)?startpoint 投送到雷區(qū)?mf 中的終點(diǎn)?endpoint）

圖5 水雷布放任務(wù)方法

方法lay_mine 將目標(biāo)任務(wù)（mine_at?mn?endpoint）分解為兩個(gè)子目標(biāo)任務(wù)，實(shí)際的含義是：若要將水雷從貯存位置?storagepoint 投到指定的布雷點(diǎn)?endpoint，應(yīng)先將水雷?mn 運(yùn)輸至UUV 的入水點(diǎn)?startpoint，再由UUV 投送至布雷點(diǎn)?endpoint。任務(wù)目標(biāo)（mine_at ?mn ?endpoint）與方法lay_mine 的子目標(biāo)任務(wù)（mine_at ?mn ?endpoint）相匹配，因此，根據(jù)HGTN 定義6，lay_mine 是與目標(biāo)任務(wù)（mine_at?mn?endpoint）相關(guān)的方法之一。

圖4、圖5 分別對(duì)應(yīng)HGTN 組合任務(wù)方法（和HTN 方法一致）和目標(biāo)任務(wù)方法。

2.2 建立規(guī)劃問(wèn)題P

根據(jù)定義，規(guī)劃問(wèn)題P 包括初始狀態(tài)定義和任務(wù)網(wǎng)絡(luò)。初始任務(wù)為seamine_laying。

2.3 問(wèn)題求解

根據(jù)問(wèn)題領(lǐng)域要求，使用合理的求解算法。

如果規(guī)劃域中的部分方法建?？紤]不完備（例如沒(méi)有圖5 任務(wù)對(duì)應(yīng)的方法），對(duì)于傳統(tǒng)HTN 規(guī)劃方法，任務(wù)無(wú)法分解導(dǎo)致無(wú)解，而使用HGTN 的GTIDP 算法，以（mine_at?mn?endpoint）目標(biāo)進(jìn)行規(guī)劃，可以得到相應(yīng)的規(guī)劃解。

如果增加多種布雷投送方式，如無(wú)人機(jī)或無(wú)人艇等［12］，可以引入考慮任務(wù)成本（如時(shí)間成本）的啟發(fā)函數(shù)［13］，以成本最小為目標(biāo)使用GTIDP 算法求解，而傳統(tǒng)HTN 規(guī)劃方法無(wú)法使用搜索信息。

表1 幾種規(guī)劃方法對(duì)比

3 結(jié)論

HTN 逐層分解任務(wù)的規(guī)劃方法體現(xiàn)了問(wèn)題領(lǐng)域?qū)＜医鉀Q具體問(wèn)題的知識(shí)經(jīng)驗(yàn)，而本文提出的HGTN 規(guī)劃方法進(jìn)一步擴(kuò)展了HTN 概念，增加了目標(biāo)任務(wù)和相關(guān)處理方法，引入了基于目標(biāo)的推理規(guī)劃?rùn)C(jī)制，對(duì)問(wèn)題領(lǐng)域建模的表達(dá)上更為靈活，提高了規(guī)劃方法的適用性。目前對(duì)HTN 規(guī)劃方法的主要研究方向是擴(kuò)展時(shí)間、資源［14-15］、動(dòng)態(tài)任務(wù)規(guī)劃［16］等規(guī)劃能力，對(duì)HGTN 規(guī)劃方法擴(kuò)展上述功能，是后續(xù)需要開展的主要工作。