一种无人化平台作战命令的形式化语法及检验算法*

鲍广宇 吴亚宁

(中国人民解放军理工大学 南京 210007)



一种无人化平台作战命令的形式化语法及检验算法*

鲍广宇 吴亚宁

(中国人民解放军理工大学 南京 210007)

作战命令是我军实施指挥和部队遂行作战任务的基本依据,也是联系指控系统、仿真系统与无人作战平台的重要桥梁。为了实现系统之间对作战命令的无歧义理解,论文运用一种改进的巴科斯范式方法对作战命令进行了形式化描述。同时,论文提出了一种基于与/或树的语法检验算法,以保证作战命令形式化语法的正确性与合法性。

作战命令; 形式化描述; 与/或树; 语法检验

Class Number E94

1 引言

近年来无人化装备的广泛应用,在减少执行任务中人员伤亡的同时,也促进了作战样式的革新。当前典型的无人化作战样式是由前方的无人化装备进行侦察感知和目标匹配,再由人在后方发布命令实施指挥控制,最终由前方的无人化装备遂行打击行动[1]。这种无人/有人相结合的作战方式要求前方的无人化装备必须能够对作战命令无歧义理解与执行。目前,我军主要是以自然语言的形式在系统间传递作战命令,虽能充分表达指挥员意图,但由于受到人工智能领域语言处理技术发展的限制,很难实现机器对自然语言消息的无歧义处理[2],因此需对作战命令进行形式化描述,从而保证各系统对作战命令具有一致、无歧义的理解。

为实现这个目标,美军先后启动了作战管理语言[3]、可扩展作战管理语言[4]、联盟作战管理语言[5]等项目。国内国防大学的岳磊等从语义的角度,对作战命令构建语义层本体[6],实现了作战命令在结构上的形式化;我们则从语法的角度,提出了一种改进的巴科斯范式方法[7],实现了作战命令在语法上的形式化。总之,我军虽然取得了一些成果,但大部分侧重于方法本身的论述,对将方法与作战命令相结合的应用研究较少。因此,论文结合改进的巴科斯范式方法对作战命令进行了形式化描述,并提出了一种基于与/或树的语法检验算法。

2 对作战命令的形式化描述

2.1 语言特征分析与语法形式化表示方法

为了能够以更接近人类思维的方式组织作战命令元素,准确地表达指挥员意图,作战命令语法形式化方法应充分符合作战命令的语言结构特点。通常来说,作战命令具有如下典型特征[2]:格式固定,内容规范;句式简练,组织有序;语法精确性高;军事术语较多,修饰词和连接词等较少;适合网络传输。并且,由于受到汉语语法规范以及格式要求的约束,作战命令往往还具有大量的重复内容结构,并更注重语义表达。因此,语法形式化描述方法必须至少满足以下几点:表示简单、用词准确;结构规范、语义明确;可扩展性良好;适合网络环境下的应用。

针对上述要求,论文采用了一种改进的巴科斯范式(Improved Backus-Naur Form,IBNF)方法对作战命令进行形式化描述。该方法针对标准BNF在描述重复、引用时结构生硬、效率不高等问题,在原有的基础上增加了一些新的表示符号,对其进行了适当的改进,文献[7]对该方法进行了详细描述,这里不再赘述。通过大量的实例验证,IBNF方法满足我军作战命令语言特性及语法结构的要求,具有结构简单、轻量易理解等特点,在适应信息多变的战场环境上具有一定优势。

2.2 语法元素的提取及描述

作战命令通常包括头部、尾部和正文三个部分[8],其中正文是主体部分,包含各类形式区别于其他形式的独特结构,因此论文主要是针对正文部分而言。正文部分主要由一些公共的基础元素组成,如动作、时间、空间元素等。其中最重要的语法元素可归纳为“5Ws”,即Who(谁),What(什么),When(何时),Where(何地)和Why(为什么),具体含义为: 1) Who:表示采取或应该采取行动的交战对象或者是已侦查到或已采取行动的交战对象; 2) What:表示将采取的行动或者是已采取的行动; 3) When:描述将采取的行动的时间结点或者是已发生的行动、事件的时间; 4) Where:提供交战对象的位置,行动发生的地点,或者是行动、事件已经发生的地点; 5) Why:描述待执行行动的理由或目标,或者是一个计划行动希望得到的最终状态。“5Ws”按照一定的规则又可进行扩展,但Who和What为简单类型,如“驱逐舰”、“发射”等,不需要扩展,而其它几个元素的扩展规则如下所示。

1) When元素主要分为开始时间Start-When和结束时间End-When两大类,它们都具有两种扩展形式:一种是开始或结束的标识符、修饰符和相对时间点的组合;另一种是开始或结束的标识符、相对时间点修饰词和行动的组合。以Start-When为例来说明,其扩展规则为

〈Start-When〉::= *start

*〈Qualifier1〉〈Point-in-Time〉

(1)

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

(2)

其中,start表示开始;Qualifier1为修饰词,如“不晚于”;Point-in-Time代表某一时间点;Qualifier2代表一个相对时间点的修饰词,如“在行动Action结束后”;Action代表另一个将被执行的行动。

2) Where元素可分为在某地At-Where和经过某地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为语法终结符;Location代表位置信息,如“A码头”;Path代表某一路线,如“环B岛一线”。

3) Why元素包括为了达到某个行动目标、实现某一状态和获得进一步的目的:

〈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为任务引用标识符;EndState-Label为最终状态引用标识符;Expanded-Purpose-Label为扩展目标引用标识符。

通过提取语法元素并形式化描述,在某一元素发生变化的情况下,维护人员无需更新整个作战命令模板,而只用更新变化的元素,因此可大幅度减少日后维护模板的工作量。

2.3 作战命令的IBNF形式化描述

作战命令通常包括命令标识符OI、命令活动OB这两个元素,因此,可以以一种标识和活动的方式表示命令语法:

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

(11)

其中,S是语法的开始符,用于表示语法的开始;符号“{}”的使用意味着一个命令可以由任意多个活动、时间位置和空间位置组成。OI代表一类命令的唯一标识符,如预先号令、进攻命令等;OB用于表示命令活动,进一步分析作战命令的内容,命令活动又包括三方面的内容:敌情Enemy-Situation、我部/分队命令活动OB-Main和友邻/协同部/分队命令活动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代表要执行的行动,如“进攻”、“防御”、“埋伏”等;Tasker代表发出命令的实体名称;Taskee代表接受命令的实体名称;Affected代表任务影响的实体名称,它的出现与否由Verb决定;Action代表另一个将被执行的行动;Where代表位置短语,如“在何地”、“经过何地”等;Start-When代表时间短语,如“不晚于某个时间点开始”,这里的“开始”和“不晚于”都是语法终结符;End-When也代表一个时间短语,它的扩展规则与Start-When类似;Why代表任务要求被执行的原因;Label代表一个唯一标识符,其它命令可以通过使用这个唯一标识符来引用该命令,一般形式为“作战命令类型_引用类型_标识编号”,如“命令_引用_标识1”;Mod代表描述特定任务所需要额外附加的信息,如“编队”、“速度”等。

3 基于与/或树的语法检验算法

当无人化装备接收到作战命令后,先要对其进行语法解析,提取出语法元素,再根据这些元素做出行为响应。一旦作战命令存在语法错误,该过程便不能实现,作战命令也将无法执行。针对这种情况一般有两种解决方法:一种是在无人化装备上构建语法纠错机制,使其能够辨识出语法错误并自动进行纠正。但由于目前的无人化技术水平还不能满足高效的智能化处理,因此当作战命令数据较大时,会严重降低无人化装备的处理效率和响应速度;另一种则是在作战命令发布之前对其进行语法检验,以保证所接收到的作战命令语法正确。这种方法较之第一种降低了无人化装备的系统复杂度,也更为容易实现。因此,论文围绕第二种方法对语法检验方法进行了研究。目前使用较为广泛的语法检验方法主要被应用于源代码检测,其算法并不能适用于作战命令的特定结构,因此,笔者尝试运用与/或树方法对作战命令语法进行合法性验证。经过多次的实验,该算法能够以很小的时间复杂度完成大量作战命令的合法性检验工作,具体算法分析将在下文进行描述。

3.1 与/或树的相关概念

与/或树搜索是指用问题归约法来求解问题时所进行的搜索。当一个问题比较复杂时,直接求解往往比较困难,此时可通过分解或变换,将它转化为一系列较简单的问题,然后通过对这些较简单问题的求解来实现对原问题的求解[9]。其中,把一个原问题归约为一系列本原问题的过程,若只需通过分解,则可用与树来表示;若只需通过变换,则可用或树来表示;若既需分解也需变换,则用与/或树来表示。在与/或树中,由可解结点构成,并且由这些可解结点可以推出初始结点为可解结点的子树称为解树。

通过对作战命令的IBNF形式化语法结构以及与/或树的结构特征进行对比分析后可发现,对IBNF形式化语法的合法性检验过程可看作一个问题规约求解的过程,原问题即一条完备的作战命令,本原问题即作战命令中的各个语法元素。一条作战命令是否合法的问题,可转化为是否能够生成解树的问题,若能够生成解树,则合法,反之则不合法。

3.2 作战命令形式化语法检验与/或树

但是在研究过程中发现,作战命令的IBNF形式化语法并不能完全符合与/或树的结构。例如,作战命令根结点可以包含OI、Enemy-Situation、OB-Main和OB-Adjacent四个子结点,其中,OI结点是必须包含的,而另外三个子结点只要包含大于等于一个即可。因此,若要使作战命令的形式化语法完全符合与/或树的结构,则需要在原有的基础上构建新的结点,如添加命令主体(Order Main)结点,并将Enemy-Situation、OB-Main和OB-Adjacent这三个结点作为Order Main的子结点。此外,还有一种情况需要考虑,即不同的作战命令包含的元素可能是不同的,如有些需要包含时间元素,而有些可以不包含。对于这种情况,论文采用了添加空结点(即内容为空的结点)作为子结点的方法进行处理。最终,可得到一棵完备的作战命令IBNF形式化语法检验与/或树,如图1所示。

图1 作战命令IBNF形式化语法检验与/或树

图中的OB-Main和OB-Adjacent结点拥有与Enemy-Situation结点相同的子结点,因此为了图形的简洁清晰,不再对其重复描述。

3.3 检验算法

IBNF与/或树检验算法的执行步骤如下:

1) 载入作战命令IBNF形式化语法,并将语法检验树的根结点记为Root;

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

3) 判断Root结点的状态:

(1)若Root结点为与结点,则将指针P指向Root→firstSon;

(2)判断P结点的状态:

①若P为解结点,匹配Attri中元素与P结点,若一致,i=i+1,执行2)。P=P→nextSibling,若P不为空,执行(2),若P为空,执行4);若不一致,语法不合格,算法终止;

②若P为与(或)结点,Root=P,执行3);

(3)若Root结点为或结点,则将指针P指向Root→firstSon;

(4)判断P结点的状态:

①若P为解结点,匹配Attri中元素与P结点,若一致,i=i+1,执行2)。P=P→nextSibling,若P不为空,执行(4),若P为空,执行4);若不一致,P=P→nextSibling,若P不为空,执行(4),若P为空,执行4);

②若P为与(或)结点,Root=P,执行3);

4) 若P为空结点,P=Root,Root=Root→father,若Root不为空结点,P=P→nextSibling,判断Root结点的状态,若Root为与结点,执行(2),若Root为或结点,执行(4);若Root为空结点,检验过程结束,语法合格。

在上述算法中,因为是通过元素的比较进行查找的,所以用查找长度(即测试的元素个数)度量算法的时间复杂性T(n)[10]。设某条作战命令语法元素个数为n,其查找长度为T(n),根据算法,可分为以下几种情况进行计算:

1) 语法合格。在算法中,后一个元素的查找匹配取决于前一个元素的匹配结果,因此在语法检验合格时,结点最长查找长度为树的高度5,最短查找长度为1。语法检验树中,解结点共有49个,其中五层结点39个,四层结点7个,三层结点2个,二层结点0个,一层结点1个,则可得到n个元素中各层结点所占的比重。按照上述分析,可列出计算式:

(16)

因此,在语法合格的情况下,算法的时间复杂度为O(n)。

2) 语法不合格。语法不合格时,最好的情况是第一个元素即不合格,最坏的情况是最后一个元素不合格。当第一个元素不合格时,查找长度为1,则T(n)=1;当最后一个元素不合格时,查找长度与语法合格的情况相同,为T(n)=230n/49。因此,在语法不合格的情况下,算法的时间复杂度为O(n)。

综上所述,该语法检验算法的时间复杂度为O(n)。

4 实例检验

以某摩步团进攻战斗命令中某一作战任务为例,说明语法形式化描述方法的应用。总体情况为:步兵第1营配属坦克营第1连,集团军炮兵旅反坦克导弹连,担负团左翼突击任务。在红村桥至张家村一线占领进攻出发阵地,集中主力在岔路口突破敌人防御,向乌龟岭方向实施主要突击。通过提取分析该命令的语法元素,可得到该命令的IBNF形式化语法描述为

〈Operational-Order〉::=〈进攻战斗命令OCO〉

(17)

{/OCO_OBM_1/〈突击〉〈团指挥所〉〈步兵第1营〉〈Route-Where〉*from**红村桥**to**张家村*〈Mod〉〈作战编成:坦克营第1连,集团军炮兵旅反坦克导弹连〉〈Why〉*in-order-to*〈占领进攻出发阵地〉}

(18)

{/OCO_OBM_2/〈突破〉〈团指挥所〉〈步兵第1营〉〈Route-Where〉*from**岔路口**to**乌龟岭*〉}

(19)

5 结语

在无人作战平台应用日益广泛的背景下,论文针对实现无人化装备对作战命令的无歧义理解这一问题,对我军作战命令的语法进行了形式化描述,并提出了一种基于与/或树的作战命令语法检验算法。首先,在对作战命令语言结构特点的研究基础上,运用一种IBNF方法,对其进行了形式化描述。其次,结合与/或树的方法,提出了一种作战命令的语法检验算法,保证了作战命令语法的正确性和有效性,为系统间的信息交互提供了技术支撑。

[1] 刘晓明,曹雷,鲍广宇,等.无人化指挥控制初探[C]//2013第一届中国指挥控制大会,北京,2013,8:954-957.

[2] 张广军.基于XML作战文书理解关键技术研究[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] 岳磊,马亚平,徐俊强,等.面向语义的作战命令形式化描述及本体构建[J].指挥控制与仿真,2012,34(1):11-14.

[7] 吴亚宁,谭伟,周伟,等.未来数字化战场中的指挥控制语言研究[J].指挥控制与仿真,2014,36(1):56-60.

[8] 中国人民解放军司令部条例[S].2006,4.

[9] 王万森.人工智能原理及其应用[M].北京:电子工业出版社,2008:106-108.

[10] 王庆瑞.数据结构教程(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)资助。

鲍广宇,男,博士后,教授,研究方向:指挥信息系统集成与应用。吴亚宁,女,硕士研究生,研究方向:作战信息管理。

E94

10.3969/j.issn.1672-9730.2015.09.009