1. Introduction

The construction of a new conceptual weapon system requires a large budget and an extended period. Engagement-level simulation is a quantitative method to evaluate the effectiveness of a weapon system before its construction and acquisition, minimizing the investment risk and also providing feedback to optimize the technology solutions¹.

Before finalizing the design, various technology solutions for new weapon systems need to be evaluated in multiple engagement scenarios. Classical tactics are no longer applicable to operate weapon systems utilizing advanced technologies, and test scenarios show that no universal tactic performs well under these conditions; consequently, a lot of competent tactics are required to conduct a comprehensive evaluation. However, developing tactics requires significant domain expertise, and scripting tactics is time-consuming and labor-intensive in practice². Therefore subject matter experts (SMEs) need a more efficient method to develop competent tactics.

Evolutionary algorithms (EAs)³ are a class of population-based stochastic search techniques to search complex problem for optimal solutions, providing a potential framework to explore engagement-level tactic space. However, tactics are more about structures (e.g., the goal hierarchy and action sequence) than numerical parameters, and classical EAs focus on numerical optimization and lack the ability to explore structure space.

Genetic programming (GP)^4,5, as an extension of the classical genetic algorithm (GA)⁶, is defined as a structural optimization algorithm⁷, which evolves solutions represented with executable programs instead of linear strings. Grammar-based GP⁸ redefined the elements on a derivation tree with a problem-oriented context-free grammar (CFG) instead of Lisp expressions as in the original GP. CFG provides a general representation structure for defining constraints and limits in problem solutions.

The advantages of grammar-based GP include the following: 1) formal grammar restricts the search space; 2) problem-oriented grammar provides a flexible representation for domain knowledge and problem solutions; and 3) grammar-based GP extends GA with the ability of structure optimization. In summary, grammar-based GP is a promising framework to explore tactic space, as tactics are both domain knowledge intensive and representation structured.

In this paper, we proposed our tactics exploration framework (TEF) based on grammar-based GP to evolve tactics in simulation, in which a grammar of behavior tree (BT)⁹ formalism is used for tactic representation. BTs are a formal method to represent both goal hierarchies and action sequences in tactics; moreover, the modular tree structure is inherently compatible with genetic operators in grammar-based GP. To validate our method, an undersea warfare scenario is built to explore submarine tactics in the engagement-level simulation.

The outline of this paper is as follows: Section 2 presents some related work. Section 3 is an overview of our proposed framework to explore submarine tactics with grammar-based GP. Section 4 introduces BTs and details their specific application to submarine warfare. Section 5 presents a grammar-based GP technique to evolve tactics, followed in Section 6 by submarine tactics exploration experiments to validate our method and also the analysis of experimental results. Conclusions and the future works are presented in Section 7.

2. Related Work

In most military simulation systems, tactics are script-based. SMEs propose new tactics and represent them with informal paper-based diagrams before coding them into scripts to do the simulation. The most often-used tactics representations are rule-set, decision tree, and finite state machine (FSM). These are criticized for their defects in practice^10,11,12, such as the inability to scale up in the complex domain, the difficulties for SMEs to understand and reuse tactic scripts, and the tedious scripting.

To address these problems, software engineering is introduced to provide domain specific language (DSL)¹³ for tactics representation with automatic script generation. For example, Kerbusch implemented a simple FSM with the scripting language Lua to describe air combat tactics¹⁴. Evertsz proposed a Tactics Development Framework (TDF)^2,12, which fully defined the tactical elements, such as missions, actors, roles, and scenarios. In TDF methodology, a goal structure is designed to decompose the mission objectives into sub-goals, and a plan diagram based upon activity diagrams is provided to describe the procedure of tactic. However, it is noteworthy that DSL is just a method to represent tactics, and the tactics development still relies heavily on domain expertise.

Developing tactics for a new weapon system used to be an “trial and error” process; that is costly and time-consuming for SMEs to propose, test, and redesign tactics. Therefore, technologies in artificial intelligence (AI), such as EA and reinforcement learning (RL), are introduced to optimize and learn tactics in the simulation.

EA, as a general search technique, is widely used to optimize tactics in the military domain. Mulgund applied GA to optimize the team formation and intercept geometry in large-scale air combat¹⁵. Liang also used GA to design anti-torpedo tactics¹⁶. Similar works can be found in^17,18,19. In these applications, SMEs built the structures of tactics and implemented EAs to optimize the critical parameters on the structures; however, EAs did little exploration in tactic structures.

While EA searches for optimal tactics through evolving a population of individual agents, RL enables an agent to improve its tactic through training in the simulation. Teng proposed the FALCON²⁰ architecture based on the self-organizing neural network to train strategies in 1-v-1 dogfight training simulation. The proposed models showed significantly improved adaptivity and higher performance in human-in-the-loop (HIL) experiments. Toubman applied dynamic scripting (DS)²¹ to improving team coordination behavior in air combat and got a higher performance in experiments²². DS selects high weight rules from a rule base to build scripts for combat simulation; then the results are fed back to update the weight of rules. This process continues until a reliable script is reached. However, tactics represented with weighted rule-set models or neural network models were black box systems, from which it is difficult for SMEs to understand the internal logic and get explicit tactics²³.

3. Tactics Exploration Framework

This section presents an overview of our proposed framework to explore tactics, including components and workflow. TEF consists of an engagement-level simulator to conduct experiments and a grammar-based GP as a tactic exploration engine. A tactics representation tool (TRT) is also provided for SMEs to edit and read tactics represented with BTs diagrams.

TEF is based on an engagement-level simulator, named Weapon Effectiveness Simulation System (WESS)²⁴, which supports submarine warfare with high-fidelity models of the submarine, sonar, torpedo, etc. Tactics are defined with Python for execution, a scripting language that is close to a natural language. The Python interfaces for state query and action execution are listed out as the basic elements in tactic scripts. State variables in queries are extracted from onboard instruments, and available actions to execute are basic orders from control systems as in real-life combat.

Tactic representation is a core issue in a combat simulation. In TEF, we use the BTs to represent tactics. Compared to other forms of representation (e.g., rule-set, FSM), BTs enable SMEs to represent both the goal hierarchies and action sequences of a tactic in one diagram. The inherent advantage comes from the modularity of the tree structure in that the subtrees can be composed into new BTs without limits. Moreover, both BTs and the derivation trees of GP are in the tree structure. Thus the genetic operators of GP are compatible with BTs in semantics. A TRT is also developed as the bridge between SMEs and GP, which enables SMEs to edit domain knowledge for GP and also read the tactics generated from the evolution of GP.

Grammar-based GP works as the engine in TEF, which produces tactics to conduct simulations and updates tactics with feedback engagement results. To utilize grammar-based GP in tactic exploration, a context-free grammar of BT formalism in Backus-Naur form (BNF) is defined to represent tactics, and the genetic operators are improved to stabilize the evolution process. The details are presented in Section 5.

The workflow of TEF in Fig. 1 proceeds as follows. First, a repository of the most used tactics and tactic modules in doctrine is built up. Next, SMEs draft initial generation of tactics in BT diagrams based on the tactic repository. The diagrams are mapped to derivation trees for genetic manipulation and translated into executable tactic scripts with TRT. After that, simulations are conducted to evaluate the fitness of tactics in combat. Guided with the feedback fitness, GP produces a new generation of tactics with genetic operators and starts new simulations to iterate the exploration. SMEs validate new tactics in exploration to update the tactic repository.

Fig. 1.

Tactics Exploration Framework

4. Tactic Representation

for i←1 to N do

  state←Tick(child(i));

  if state = = Running then

    return Running;

  end

  if state = = Success then

    return Success;

  end

end

return Failure;

for i←1 to N do

  state←Tick(child(i));

  if state = = Running then

    return Running;

  end

  if state = = Failure then

    return Failure;

  end

end

return Success;

for i ← 1 to N do

  statei←Tick(child(i));

end

if nSuccNodes(statei) ⩾ nS then

  return Success;

else if nFailNodes(statei) ⩾ nF

then

  return Failure;

else

  return Running;

end

if Xn(t) ∈ Sn then

  return Success;

end

if Xn(t) ∈ Fn then

  return Failure;

end

if Xn(t) ∈ Rn then

  Un(t)←γn(Xn(t));

  return Running;

end

if Xn(t) ∈ Sn then

  return Success;

end

if Xn(t) ∈ Fn then

  return Failure;

end

if Check(constrains) = =

True then

  state←Tick(child);

  return state;

else

  return Failure;

end

return Tick(child(0));

4.3. Representing Submarine Tactics with Behavior Trees

According to the definitions, tactics are goaloriented and procedural in nature. Thus the representation focuses on the decomposition of goals and the sequence of action in the procedure.

4.3.1. Goal Hierarchies

BTs provide tree structure to support top-down decomposition from mission goal to subtasks, state queries and actions. In turn, low-level subtasks can also be composed into higher-level tasks to achieve specific goals through bottom-up integration.

In littoral defense, the tactical goal of the conventional submarine is to destroy or clear out warships in the operation area. In general, submarine tactics can be decomposed into approach, attack, defense, and retreat, as shown in Fig. 2(a). For example, the approaching task is further decomposed into several legs to locate and chase a warship, and each leg is composed of actions to set heading and speed. Classical tactic modules in the repository, such as an effective torpedo defense, can be added to a new tactic or replace the same part in an old one.

Fig. 2.

An example of submarine tactic in Behavior Tree formalism

4.3.2. Action Sequences

The sequence of actions is defined with control nodes in BTs; Sequence and Selector for serial actions, Parallel for concurrent actions, and Decorator for specific temporal actions.

In submarine warfare, a tactic consists of maneuver and fire control. Sequence executes subtasks or actions with a strict time order, such as legs to locate the warship¹. Fig. 2(b) is a simple Point-Lead-Point leg. Selector defines the priorities of subtasks or actions; for example, submarine interrupts attacking maneuver to high prior torpedo defense, shown in Fig. 2(b). Fire control, including sensor management, weapon launch, and countermeasure release, is concurrent with the maneuver. As in the torpedo defense, submarine maneuvers to avoid torpedo and releases decoys at the same time, as shown in Fig. 2(c) with a Parallel. Moreover, actions with specific constraints on intervals and times are defined with Decorator.

4.4. Tactics Representation Tool

Based on BT formalism, we developed a DSL for tactic representation with Eclipse Modeling Framework (EMF)²⁹. First, the abstract syntax of DSL was developed with Ecore metamodeling, which defined both the domain-independent elements of BTs formalism and the domain elements, such as actions and state variables. Following this, a graphical editor with concrete syntax was built with Graphical Modeling Framework (GMF)³⁰, which provided SMEs a graphical user interface to design tactic models. Finally, a code generator was implemented with Acceleo³¹, which mapped tactic diagrams into Python scripts. TRT was an Eclipse-based plugin based on the components above. See Ref. 32 for more details.

TRT provided features such as friendly tactic editor environment and flexible domain knowledge management. Tactic diagrams also promoted user comprehension and the potential for tactics reuse and sharing. Fig. 3 showed the snapshot of TRT and an example of generated script.

Fig. 3.

Tactics representation tool and generated tactic script

In TEF, TRT bridged the GP algorithm and SMEs by automatically translating between tactic diagrams and scripts. Domain knowledge, such as classical tactic modules, represented by diagrams were translated into scripts for GP manipulation. On the other hand, tactic scripts generated from GP evolution were translated back to diagrams for expert analysis and validation.

5. Exploring Tactics with Grammar-based Genetic Programming

5.1. Grammar-based Genetic Programming

In this work, we implemented CFG-GP^33,34 to explore tactics, in which a CFG of BT formalism was defined to generate the derivation trees, and extended genetic operators are proposed to stabilize the evolution.

In the terminology of grammar-based GP, the genotype is a derivation tree in the language defined by a problem-oriented grammar, while the phenotype refers to a program that produces the behavior of an individual. The grammar defines the interpretation between genotype and phenotype. Fig. 4 showed an example to generate a derivation tree from a grammar. In the evolution process, genetic operators manipulate genotypic derivation trees, while the fitness of individuals is calculated based on the performance of phenotypic programs in combat simulations.

Fig. 4.

An application of grammar to generate a derivation tree

As for any EAs, an initial population of individuals is created at random, and each individual is executed to ascertain its fitness. The individuals with higher fitness get more possibilities of being selected as parents to generate a new population through selection, crossover, and mutation operators. The evolution loop is run until a certain termination condition is met (e.g., obtaining an acceptable solution, or a maximum number of generations is reached).

5.3. Genetic Operators

5.3.1. Crossover

The genotype in CFG-GP is a derivation tree, and the typical form of crossover is a subtree crossover. Two individuals called the parents are selected from the population. A crossover node is chosen at random in each parent, and the subtrees rooted at the crossover nodes are swapped between parents to generate child individuals, as shown in Fig. 5(a).

Fig. 5.

Examples of subtree crossover and subtree mutation

The tree structure is more sensitive to the changes on high-level nodes than on low-level ones. In contrast, the high-level goal hierarchies and action sequences of tactic BTs are more stable than the lower ones. In fact, frequent changes on high-level nodes of tactic BTs trend to generate tactics that are syntactically correct but obviously violate the doctrine and perform stupid actions, leading to an unstable evolution.

As a consequence, we used a variable probability for crossover operator at different levels to keep the BT structure stable. For a BT with N levels, the top node (root) is level 0 and the lowest leaf node is level N − 1. Assuming P_x is the crossover probability parameter for GP, we set P_x(i) = P_x ∗ (1 − e⁻ⁱ) as the crossover probability for nodes at level i.

Most tactic modules (e.g., Approach) are self-contained blocks, in which the actions and conditions are customized. For example, the submarine would not launch torpedoes in Defense. The crossover between different modules destroys the integrity of tactic modules.

To overcome this defect, we introduced an 〈X O〉 to separate tactic modules and indicate the crossover boundaries. In the evolution process, the crossover is performed on the same tactic modules, in which Approach exchanges internal actions with Approach in other tactics and avoid random exchange with Attack.

• 〈Tactic〉 ::= Defence = 〈BT〉; 〈XO〉;

•   Approach = 〈BT〉; 〈XO〉;

•   Attack = 〈BT〉; 〈XO〉;

•   Retreat = 〈BT〉; 〈XO〉;

5.3.2. Mutation

A mutation operator selects a mutation node at random in a single parent, removes the subtree at that point, and inserts a new derivation tree generated with the CFG, as shown in Fig. 5(b).

Just as the same as the crossover, we used a variable probability for mutation operator to decrease changes on the high-level nodes. Assuming P_m is the mutation probability parameter, we set P_m(i) = P_m ∗ (1−e⁻ⁱ) as the mutation probability for nodes at level i.

6. Case Study

6.1. Submarine Warfare Scenario

A littoral area submarine warfare scenario was built to validate our proposed method. In the scenario, a patrolling submarine dived underwater to ambush a warship. As an opponent, the warship cruised with active sonar working and attacked any submarines within its torpedo range.

To model the uncertainties in warfare, the position, speed, and heading of an adversary warship were initialized randomly in scenarios. As shown in Fig. 6, the initial position was randomly distributed in a circle with a radius of 10 nautical miles (nm). The speed was sampled from a uniform distribution on [10, 30] knots, and the heading of the warship was sampled from a uniform distribution from 330 to 30.

Fig. 6.

Scenario of submarine warfare

6.3. Results

Because of the sensitive nature of the simulations, the results analysis focused on the efficiency of tactics in the exploration process rather than the specific tactics. Fig. 7. visualizes the experimental results with the average fitness of the tactics in the exploration.

Fig. 7.

Fitness of tactics in the exploration

6.3.1. Baseline

The 20 expert tactics were tested in simulation to get the baseline, with 0.513 for Sub_Active and 0.636 for Sub_New. It means that new technologies in Sub_New brought about 23.9% increment in capability even run with expert tactics for Sub_Active.

6.3.2. Exploration results

In Fig. 7, it was obvious that the exploration began with a low average fitness value, the reason was that 80% of initial tactics were generated randomly. However, the average fitness value shows an uptrend in the following generations. In the Sub_Active experiment, the tactics started with 0.285 and rose to about 0.451 after 50 generations and then stagnated across the subsequent 50 generations. It was almost the same in the Sub_New experiment, with tactics raised from 0.245 to 0.55 before 70 generations. The evolution processes for both Sub_Active and Sub_New show an obvious uptrend on average fitness with decreasing standard deviation. It demonstrates the capability of grammar-based GP to explore tactics with a stable process.

In our experiments, the average fitness of both Sub_Active and Sub_New did not make evident breakthroughs over the baseline. However, the top 15% tactics show some differences. The top 15% tactics performance and expert tactics in the Sub_Active experiment mean that the expert tactics gave full play to Sub_Active, and GP did not make any breakthrough. In contrast, the top 15% tactics for Sub_New show slightly higher efficiency than expert ones in the last 30 generations. A one-sided t-test rejected the null hypothesis that the top 15% with average fitness equaled baseline (0.636) at the 5% significance level and accepted the alternative hypothesis of the top 15% with an average fitness greater than the baseline. From this observation, it can be concluded that expert tactics worked well but did not make full use of Sub_new; however, GP found new tactics to exploit the capability of Sub_New further.

Acknowledgments

This work is partly supported by the National Natural Science Foundation of China (no. 61273198 and no. 71373282). The authors acknowledge Qiwang Huang for his detailed and helpful advices to the paper.