一種無人化平臺作戰(zhàn)命令的形式化語法及檢驗算法*

鮑廣宇 吳亞寧

(中國人民解放軍理工大學 南京 210007)

?

一種無人化平臺作戰(zhàn)命令的形式化語法及檢驗算法*

鮑廣宇 吳亞寧

(中國人民解放軍理工大學 南京 210007)

作戰(zhàn)命令是我軍實施指揮和部隊遂行作戰(zhàn)任務(wù)的基本依據(jù),也是聯(lián)系指控系統(tǒng)、仿真系統(tǒng)與無人作戰(zhàn)平臺的重要橋梁。為了實現(xiàn)系統(tǒng)之間對作戰(zhàn)命令的無歧義理解,論文運用一種改進的巴科斯范式方法對作戰(zhàn)命令進行了形式化描述。同時,論文提出了一種基于與/或樹的語法檢驗算法,以保證作戰(zhàn)命令形式化語法的正確性與合法性。

作戰(zhàn)命令; 形式化描述; 與/或樹; 語法檢驗

Class Number E94

1 引言

近年來無人化裝備的廣泛應(yīng)用,在減少執(zhí)行任務(wù)中人員傷亡的同時,也促進了作戰(zhàn)樣式的革新。當前典型的無人化作戰(zhàn)樣式是由前方的無人化裝備進行偵察感知和目標匹配,再由人在后方發(fā)布命令實施指揮控制,最終由前方的無人化裝備遂行打擊行動[1]。這種無人/有人相結(jié)合的作戰(zhàn)方式要求前方的無人化裝備必須能夠?qū)ψ鲬?zhàn)命令無歧義理解與執(zhí)行。目前,我軍主要是以自然語言的形式在系統(tǒng)間傳遞作戰(zhàn)命令,雖能充分表達指揮員意圖,但由于受到人工智能領(lǐng)域語言處理技術(shù)發(fā)展的限制,很難實現(xiàn)機器對自然語言消息的無歧義處理[2],因此需對作戰(zhàn)命令進行形式化描述,從而保證各系統(tǒng)對作戰(zhàn)命令具有一致、無歧義的理解。

為實現(xiàn)這個目標,美軍先后啟動了作戰(zhàn)管理語言[3]、可擴展作戰(zhàn)管理語言[4]、聯(lián)盟作戰(zhàn)管理語言[5]等項目。國內(nèi)國防大學的岳磊等從語義的角度,對作戰(zhàn)命令構(gòu)建語義層本體[6],實現(xiàn)了作戰(zhàn)命令在結(jié)構(gòu)上的形式化;我們則從語法的角度,提出了一種改進的巴科斯范式方法[7],實現(xiàn)了作戰(zhàn)命令在語法上的形式化?？傊?我軍雖然取得了一些成果,但大部分側(cè)重于方法本身的論述,對將方法與作戰(zhàn)命令相結(jié)合的應(yīng)用研究較少。因此,論文結(jié)合改進的巴科斯范式方法對作戰(zhàn)命令進行了形式化描述,并提出了一種基于與/或樹的語法檢驗算法。

2 對作戰(zhàn)命令的形式化描述

2.1 語言特征分析與語法形式化表示方法

為了能夠以更接近人類思維的方式組織作戰(zhàn)命令元素,準確地表達指揮員意圖,作戰(zhàn)命令語法形式化方法應(yīng)充分符合作戰(zhàn)命令的語言結(jié)構(gòu)特點。通常來說,作戰(zhàn)命令具有如下典型特征[2]:格式固定,內(nèi)容規(guī)范;句式簡練,組織有序;語法精確性高;軍事術(shù)語較多,修飾詞和連接詞等較少;適合網(wǎng)絡(luò)傳輸。并且,由于受到漢語語法規(guī)范以及格式要求的約束,作戰(zhàn)命令往往還具有大量的重復內(nèi)容結(jié)構(gòu),并更注重語義表達。因此,語法形式化描述方法必須至少滿足以下幾點:表示簡單、用詞準確;結(jié)構(gòu)規(guī)范、語義明確;可擴展性良好;適合網(wǎng)絡(luò)環(huán)境下的應(yīng)用。

針對上述要求,論文采用了一種改進的巴科斯范式(Improved Backus-Naur Form,IBNF)方法對作戰(zhàn)命令進行形式化描述。該方法針對標準BNF在描述重復、引用時結(jié)構(gòu)生硬、效率不高等問題,在原有的基礎(chǔ)上增加了一些新的表示符號,對其進行了適當?shù)母倪M,文獻[7]對該方法進行了詳細描述,這里不再贅述。通過大量的實例驗證,IBNF方法滿足我軍作戰(zhàn)命令語言特性及語法結(jié)構(gòu)的要求,具有結(jié)構(gòu)簡單、輕量易理解等特點,在適應(yīng)信息多變的戰(zhàn)場環(huán)境上具有一定優(yōu)勢。

2.2 語法元素的提取及描述

作戰(zhàn)命令通常包括頭部、尾部和正文三個部分[8],其中正文是主體部分,包含各類形式區(qū)別于其他形式的獨特結(jié)構(gòu),因此論文主要是針對正文部分而言。正文部分主要由一些公共的基礎(chǔ)元素組成,如動作、時間、空間元素等。其中最重要的語法元素可歸納為“5Ws”,即Who(誰),What(什么),When(何時),Where(何地)和Why(為什么),具體含義為: 1) Who:表示采取或應(yīng)該采取行動的交戰(zhàn)對象或者是已偵查到或已采取行動的交戰(zhàn)對象; 2) What:表示將采取的行動或者是已采取的行動; 3) When:描述將采取的行動的時間結(jié)點或者是已發(fā)生的行動、事件的時間; 4) Where:提供交戰(zhàn)對象的位置,行動發(fā)生的地點,或者是行動、事件已經(jīng)發(fā)生的地點; 5) Why:描述待執(zhí)行行動的理由或目標,或者是一個計劃行動希望得到的最終狀態(tài)。“5Ws”按照一定的規(guī)則又可進行擴展,但Who和What為簡單類型,如“驅(qū)逐艦”、“發(fā)射”等,不需要擴展,而其它幾個元素的擴展規(guī)則如下所示。

1) When元素主要分為開始時間Start-When和結(jié)束時間End-When兩大類,它們都具有兩種擴展形式:一種是開始或結(jié)束的標識符、修飾符和相對時間點的組合;另一種是開始或結(jié)束的標識符、相對時間點修飾詞和行動的組合。以Start-When為例來說明,其擴展規(guī)則為

〈Start-When〉::= *start

*〈Qualifier1〉〈Point-in-Time〉

(1)

〈Start-When〉::=*start*〈Qualifier2〉〈Action〉

(2)

其中,start表示開始;Qualifier1為修飾詞,如“不晚于”;Point-in-Time代表某一時間點;Qualifier2代表一個相對時間點的修飾詞,如“在行動Action結(jié)束后”;Action代表另一個將被執(zhí)行的行動。

2) Where元素可分為在某地At-Where和經(jīng)過某地Route-Where兩種擴展類型:

〈Where〉::=〈At-Where〉|〈Route-Where〉

(3)

〈At-Where〉::=*at*〈Location〉

(4)〈Route-Where〉::=(〈Source〉〈Destination〉〈Path〉)

|(〈Source〉〈Path〉)|(〈Destination〉〈Path〉)|…

|(*along*〈Path〉)

(5)

〈Source〉::=*from*〈Location〉

(6)

〈Destination〉::=*to*〈Location〉

(7)

其中,at、from、to、along為語法終結(jié)符;Location代表位置信息,如“A碼頭”;Path代表某一路線,如“環(huán)B島一線”。

3) Why元素包括為了達到某個行動目標、實現(xiàn)某一狀態(tài)和獲得進一步的目的:

〈Why〉::=*in-order-to*〈Verb〉[Task-Label]

(8)

〈Why〉::= *in-order-to**cause

*EndState-Label

(9)

〈Why〉::= *in-order-to**enable*

Expanded-Purpose-Label

(10)

其中in-order-to用于表示目的;Verb代表命令動作;Task-Label為任務(wù)引用標識符;EndState-Label為最終狀態(tài)引用標識符;Expanded-Purpose-Label為擴展目標引用標識符。

通過提取語法元素并形式化描述,在某一元素發(fā)生變化的情況下,維護人員無需更新整個作戰(zhàn)命令模板,而只用更新變化的元素,因此可大幅度減少日后維護模板的工作量。

2.3 作戰(zhàn)命令的IBNF形式化描述

作戰(zhàn)命令通常包括命令標識符OI、命令活動OB這兩個元素,因此,可以以一種標識和活動的方式表示命令語法:

S::=〈OI〉{〈OB〉}

(11)

其中,S是語法的開始符,用于表示語法的開始;符號“{}”的使用意味著一個命令可以由任意多個活動、時間位置和空間位置組成。OI代表一類命令的唯一標識符,如預(yù)先號令、進攻命令等;OB用于表示命令活動,進一步分析作戰(zhàn)命令的內(nèi)容,命令活動又包括三方面的內(nèi)容:敵情Enemy-Situation、我部/分隊命令活動OB-Main和友鄰/協(xié)同部/分隊命令活動OB-Adjacent,可分別擴展為

〈OB〉::= {〈Enemy-Situation〉}{〈OB-Main〉}

{〈OB-Adjacent〉}

(12)

〈Enemy-Situation〉::=/Label/〈Verb〉〈Tasker〉

〈Taskee〉[〈Affected〉|〈Action〉]〈Start-When〉

[〈End-When〉][〈Where〉][〈Why〉]{〈Mod〉}

(13)

〈OB-Main〉::=/Label/〈Verb〉〈Tasker〉〈Taskee〉

[〈Affected〉|〈Action〉]〈Start-When〉

[〈End-When〉]〈Where〉[〈Why〉]{〈Mod〉}

(14)〈OB-Adjacent〉::=/Label/〈Verb〉〈Tasker〉〈Taskee〉

[〈Affected〉|〈Action〉]〈Start-When〉

[〈End-When〉]〈Where〉[〈Why〉]{〈Mod〉}

(15)

其中,Verb代表要執(zhí)行的行動,如“進攻”、“防御”、“埋伏”等;Tasker代表發(fā)出命令的實體名稱;Taskee代表接受命令的實體名稱;Affected代表任務(wù)影響的實體名稱,它的出現(xiàn)與否由Verb決定;Action代表另一個將被執(zhí)行的行動;Where代表位置短語,如“在何地”、“經(jīng)過何地”等;Start-When代表時間短語,如“不晚于某個時間點開始”,這里的“開始”和“不晚于”都是語法終結(jié)符;End-When也代表一個時間短語,它的擴展規(guī)則與Start-When類似;Why代表任務(wù)要求被執(zhí)行的原因;Label代表一個唯一標識符,其它命令可以通過使用這個唯一標識符來引用該命令,一般形式為“作戰(zhàn)命令類型_引用類型_標識編號”,如“命令_引用_標識1”;Mod代表描述特定任務(wù)所需要額外附加的信息,如“編隊”、“速度”等。

3 基于與/或樹的語法檢驗算法

當無人化裝備接收到作戰(zhàn)命令后,先要對其進行語法解析,提取出語法元素,再根據(jù)這些元素做出行為響應(yīng)。一旦作戰(zhàn)命令存在語法錯誤,該過程便不能實現(xiàn),作戰(zhàn)命令也將無法執(zhí)行。針對這種情況一般有兩種解決方法:一種是在無人化裝備上構(gòu)建語法糾錯機制,使其能夠辨識出語法錯誤并自動進行糾正。但由于目前的無人化技術(shù)水平還不能滿足高效的智能化處理,因此當作戰(zhàn)命令數(shù)據(jù)較大時,會嚴重降低無人化裝備的處理效率和響應(yīng)速度;另一種則是在作戰(zhàn)命令發(fā)布之前對其進行語法檢驗,以保證所接收到的作戰(zhàn)命令語法正確。這種方法較之第一種降低了無人化裝備的系統(tǒng)復雜度,也更為容易實現(xiàn)。因此,論文圍繞第二種方法對語法檢驗方法進行了研究。目前使用較為廣泛的語法檢驗方法主要被應(yīng)用于源代碼檢測,其算法并不能適用于作戰(zhàn)命令的特定結(jié)構(gòu),因此,筆者嘗試運用與/或樹方法對作戰(zhàn)命令語法進行合法性驗證。經(jīng)過多次的實驗,該算法能夠以很小的時間復雜度完成大量作戰(zhàn)命令的合法性檢驗工作,具體算法分析將在下文進行描述。

3.1 與/或樹的相關(guān)概念

與/或樹搜索是指用問題歸約法來求解問題時所進行的搜索。當一個問題比較復雜時,直接求解往往比較困難,此時可通過分解或變換,將它轉(zhuǎn)化為一系列較簡單的問題,然后通過對這些較簡單問題的求解來實現(xiàn)對原問題的求解[9]。其中,把一個原問題歸約為一系列本原問題的過程,若只需通過分解,則可用與樹來表示;若只需通過變換,則可用或樹來表示;若既需分解也需變換,則用與/或樹來表示。在與/或樹中,由可解結(jié)點構(gòu)成,并且由這些可解結(jié)點可以推出初始結(jié)點為可解結(jié)點的子樹稱為解樹。

通過對作戰(zhàn)命令的IBNF形式化語法結(jié)構(gòu)以及與/或樹的結(jié)構(gòu)特征進行對比分析后可發(fā)現(xiàn),對IBNF形式化語法的合法性檢驗過程可看作一個問題規(guī)約求解的過程,原問題即一條完備的作戰(zhàn)命令,本原問題即作戰(zhàn)命令中的各個語法元素。一條作戰(zhàn)命令是否合法的問題,可轉(zhuǎn)化為是否能夠生成解樹的問題,若能夠生成解樹,則合法,反之則不合法。

3.2 作戰(zhàn)命令形式化語法檢驗與/或樹

但是在研究過程中發(fā)現(xiàn),作戰(zhàn)命令的IBNF形式化語法并不能完全符合與/或樹的結(jié)構(gòu)。例如,作戰(zhàn)命令根結(jié)點可以包含OI、Enemy-Situation、OB-Main和OB-Adjacent四個子結(jié)點,其中,OI結(jié)點是必須包含的,而另外三個子結(jié)點只要包含大于等于一個即可。因此,若要使作戰(zhàn)命令的形式化語法完全符合與/或樹的結(jié)構(gòu),則需要在原有的基礎(chǔ)上構(gòu)建新的結(jié)點,如添加命令主體(Order Main)結(jié)點,并將Enemy-Situation、OB-Main和OB-Adjacent這三個結(jié)點作為Order Main的子結(jié)點。此外,還有一種情況需要考慮,即不同的作戰(zhàn)命令包含的元素可能是不同的,如有些需要包含時間元素,而有些可以不包含。對于這種情況,論文采用了添加空結(jié)點(即內(nèi)容為空的結(jié)點)作為子結(jié)點的方法進行處理。最終,可得到一棵完備的作戰(zhàn)命令I(lǐng)BNF形式化語法檢驗與/或樹,如圖1所示。

圖1 作戰(zhàn)命令I(lǐng)BNF形式化語法檢驗與/或樹

圖中的OB-Main和OB-Adjacent結(jié)點擁有與Enemy-Situation結(jié)點相同的子結(jié)點,因此為了圖形的簡潔清晰,不再對其重復描述。

3.3 檢驗算法

IBNF與/或樹檢驗算法的執(zhí)行步驟如下:

1) 載入作戰(zhàn)命令I(lǐng)BNF形式化語法,并將語法檢驗樹的根結(jié)點記為Root;

2) 提取出語法中的第i個元素(i=1,2…),放入容器Attri中;

3) 判斷Root結(jié)點的狀態(tài):

(1)若Root結(jié)點為與結(jié)點,則將指針P指向Root→firstSon;

(2)判斷P結(jié)點的狀態(tài):

①若P為解結(jié)點,匹配Attri中元素與P結(jié)點,若一致,i=i+1,執(zhí)行2)。P=P→nextSibling,若P不為空,執(zhí)行(2),若P為空,執(zhí)行4);若不一致,語法不合格,算法終止;

②若P為與(或)結(jié)點,Root=P,執(zhí)行3);

(3)若Root結(jié)點為或結(jié)點,則將指針P指向Root→firstSon;

(4)判斷P結(jié)點的狀態(tài):

①若P為解結(jié)點,匹配Attri中元素與P結(jié)點,若一致,i=i+1,執(zhí)行2)。P=P→nextSibling,若P不為空,執(zhí)行(4),若P為空,執(zhí)行4);若不一致,P=P→nextSibling,若P不為空,執(zhí)行(4),若P為空,執(zhí)行4);

②若P為與(或)結(jié)點,Root=P,執(zhí)行3);

4) 若P為空結(jié)點,P=Root,Root=Root→father,若Root不為空結(jié)點,P=P→nextSibling,判斷Root結(jié)點的狀態(tài),若Root為與結(jié)點,執(zhí)行(2),若Root為或結(jié)點,執(zhí)行(4);若Root為空結(jié)點,檢驗過程結(jié)束,語法合格。

在上述算法中,因為是通過元素的比較進行查找的,所以用查找長度(即測試的元素個數(shù))度量算法的時間復雜性T(n)[10]。設(shè)某條作戰(zhàn)命令語法元素個數(shù)為n,其查找長度為T(n),根據(jù)算法,可分為以下幾種情況進行計算:

1) 語法合格。在算法中,后一個元素的查找匹配取決于前一個元素的匹配結(jié)果,因此在語法檢驗合格時,結(jié)點最長查找長度為樹的高度5,最短查找長度為1。語法檢驗樹中,解結(jié)點共有49個,其中五層結(jié)點39個,四層結(jié)點7個,三層結(jié)點2個,二層結(jié)點0個,一層結(jié)點1個,則可得到n個元素中各層結(jié)點所占的比重。按照上述分析,可列出計算式:

(16)

因此,在語法合格的情況下,算法的時間復雜度為O(n)。

2) 語法不合格。語法不合格時,最好的情況是第一個元素即不合格,最壞的情況是最后一個元素不合格。當?shù)谝粋€元素不合格時,查找長度為1,則T(n)=1;當最后一個元素不合格時,查找長度與語法合格的情況相同,為T(n)=230n/49。因此,在語法不合格的情況下,算法的時間復雜度為O(n)。

綜上所述,該語法檢驗算法的時間復雜度為O(n)。

4 實例檢驗

以某摩步團進攻戰(zhàn)斗命令中某一作戰(zhàn)任務(wù)為例,說明語法形式化描述方法的應(yīng)用?？傮w情況為:步兵第1營配屬坦克營第1連,集團軍炮兵旅反坦克導彈連,擔負團左翼突擊任務(wù)。在紅村橋至張家村一線占領(lǐng)進攻出發(fā)陣地,集中主力在岔路口突破敵人防御,向烏龜嶺方向?qū)嵤┲饕粨?。通過提取分析該命令的語法元素,可得到該命令的IBNF形式化語法描述為

〈Operational-Order〉::=〈進攻戰(zhàn)斗命令OCO〉

(17)

{/OCO_OBM_1/〈突擊〉〈團指揮所〉〈步兵第1營〉〈Route-Where〉*from**紅村橋**to**張家村*〈Mod〉〈作戰(zhàn)編成:坦克營第1連,集團軍炮兵旅反坦克導彈連〉〈Why〉*in-order-to*〈占領(lǐng)進攻出發(fā)陣地〉}

(18)

{/OCO_OBM_2/〈突破〉〈團指揮所〉〈步兵第1營〉〈Route-Where〉*from**岔路口**to**烏龜嶺*〉}

(19)

5 結(jié)語

在無人作戰(zhàn)平臺應(yīng)用日益廣泛的背景下,論文針對實現(xiàn)無人化裝備對作戰(zhàn)命令的無歧義理解這一問題,對我軍作戰(zhàn)命令的語法進行了形式化描述,并提出了一種基于與/或樹的作戰(zhàn)命令語法檢驗算法。首先,在對作戰(zhàn)命令語言結(jié)構(gòu)特點的研究基礎(chǔ)上,運用一種IBNF方法,對其進行了形式化描述。其次,結(jié)合與/或樹的方法,提出了一種作戰(zhàn)命令的語法檢驗算法,保證了作戰(zhàn)命令語法的正確性和有效性,為系統(tǒng)間的信息交互提供了技術(shù)支撐。

[1] 劉曉明,曹雷,鮑廣宇,等.無人化指揮控制初探[C]//2013第一屆中國指揮控制大會,北京,2013,8:954-957.

[2] 張廣軍.基于XML作戰(zhàn)文書理解關(guān)鍵技術(shù)研究[D].南京:南京理工大學,2009.

[3] Gustavsson P M, Hieb M R, et al. Machine Interpretable Representation of Commander’s Intent[C]//Proceedings of the 13th International Command and Control Research Technology Symposium, Bellevue WA, USA,2008.

[4] SISO(Simulation Interoperability Standards Organization). Coalition Battle Management Language(C-BML)[R]. Study Group Final Report, SISO-REF-016-2006,2006.

[5] J. Mark P, Michael R. H, Stan L, et al. Joint Battle Management Language(JBML)-US Contribution to the C-BML PDG and NATO MSG-048 TA[C]//07E-SIW-029,2007.

[6] 岳磊,馬亞平,徐俊強,等.面向語義的作戰(zhàn)命令形式化描述及本體構(gòu)建[J].指揮控制與仿真,2012,34(1):11-14.

[7] 吳亞寧,譚偉,周偉,等.未來數(shù)字化戰(zhàn)場中的指揮控制語言研究[J].指揮控制與仿真,2014,36(1):56-60.

[8] 中國人民解放軍司令部條例[S].2006,4.

[9] 王萬森.人工智能原理及其應(yīng)用[M].北京:電子工業(yè)出版社,2008:106-108.

[10] 王慶瑞.數(shù)據(jù)結(jié)構(gòu)教程(C語言版)[M].北京:希望電子出版社,2002:12-13.

A Formal Grammar and Grammar Validation Algorithm of Unmanned Platforms’ Operational Orders

BAO Guangyu WU Yaning

(PLA University of Science and Technology, Nanjing 210007)

Operational orders are the basis of conducting combat tasks in the army, as well as the important connection between of command and control systems, simulation systems and unmanned platforms. In order to make the orders understandable by these systems, the orders are formally described with an improved backus-naur form(IBNF). And for the accuracy and validity of the described orders, an and/or tree-based grammar validation algorithm is put forward.

operational orders, formal description, and/or tree, grammar validation

2015年3月4日,

2015年4月26日

2011年度國家自然科學基金(編號:61174198)資助。

鮑廣宇,男,博士后,教授,研究方向:指揮信息系統(tǒng)集成與應(yīng)用。吳亞寧,女,碩士研究生,研究方向:作戰(zhàn)信息管理。

E94

10.3969/j.issn.1672-9730.2015.09.009