Cellular Automata in Combat Modeling

This paper explores the workings and implications of cellular automata in the modeling of combat scenarios. We begin by explaining the core philosophy of complex systems theory and agent based modeling, and associated techniques. We then discuss several examples of one of those techniques: the use of cellular automata. After explaining some problems inherent to simulating battlefield conditions, we review some past methods such as Lanchester’s equations. We then continue on to the major idea of the paper with an overview of the first major use of a CA to model land combat: the ISAAC model. We discuss the core principles and functionality of ISAAC, and demonstrate a simplified version for one’s edification. We continue to survey improvements to ISAAC and subsequent models, as well as suggested vistas, with an eye towards the use of techniques in dynamical systems theory and ergodic theory.

2 History of the Use of Cellular Automata in Combat Modeling 

2.1 Cellular Automata, Agent Baed Modelling, and Complex Adaptive Systems

The original impetus for creating a model for battlefield scenarios using cellular automata techniques grew out of a new field of research known variously as complexity science or complex systems theory. Using this lens of approach one can model large and practically-irreducible systems using techniques other than traditional differential equation based methods. One encounters great difficulties when attempting to re- duce a complex phenomenon like combat, which includes many constituent independent agents, into a single, or even a set of traditional equations. This approach has been attempted (which we will discuss in the section on Lanchester’s laws), but its efficacy is limited by the myriad properties of a battlefield sce- nario. Another approach from complex systems theory, called Agent Based Modeling or ABM, attempts to create a large scale model of a complicated system from the ground up, by instantiating a large number of simple constituents with their own programmed behaviors. When the simple pieces start to interact, highly complex and nuanced behavior can arise–this process is known in CST as ”emergence.” One type of system commonly studied in complex systems theory is called a cellular automata. A traditional cellular automata, or CA is a dynamic environment consisting of a tessellated grid, which for our purposes will consist entirely of rectangles. Many common cellular automata (such as the famous ”Game of Life”) are two dimensional, however the more complicated cellular automata which we will consider will sometimes be of higher dimension.

Each space in this grid will have some finite set of properties, for example ”on/off.” And state of each space will evolve via a simple set of rules. For example: ”if all the neighbors of a space (x,y) are on, then (x,y) will turn on as well.” These rules govern how a space in our grid will look at time t + 1 and will depend only on local properties of the system, for example in the previous example it depended on the the states of adjacent spaces in the grid. The spaces on the grid can be thought of as simple constituents of a larger system, and CA have shown very complicated emergent properties such as phase transitions, Turing machine like computation, and the similar behavior to fluids and gases, and hence they are a useful tool in CST.

CST and CA have given us a new way to think about systems with many interacting parts, for example CST has been used to model natural ecosystems and the behavior of swarming insects. With these applica- tions in mind, one can imagine that a battlefield might be thought of as a similar type of system which arises from the individual behavior of many interacting agents–for example soldiers, vehicles, terrain, weather, drones, etc. It should then lead us to wonder what kind of emergent properties do battlefields display, and how can we capture those behaviors in a simpler environment.

Before we move on to modelling more complex phenomena however, it will be useful to see an example of a simple cellular automata, to see how a more complex one might be able to reflect the behavior of a larger complex system.

2.2 Life and other Cellular Automata

As an initial short example of a cellular automata we can look at ”Life,” developed in 1970 by the American mathematician John Conway. The premise is simple: a 2 dimensional grid of points which can be either on or off. The status of each node changes according to the number of adjacent elements which are active.

Some simple pseudo code will provide a more exact definition:

Life is the quintessential example of a CA because it can quickly be shown to generate regions which appear to behave like organisms. For example patterns which reproduce, move across space like crawling insects, or repeat themselves endlessly like Islamic mandalas. The basic structure of life appears to have a capacity to hold real organisms, hence its namesake. Life has even been shown to be Turing complete, i.e. it can simulate any possible computation with a proper set of initial conditions. In other words, one can create a suitable initial set of active and inactive nodes which act like a primitive computer, and can even be programmed to perform certain rudimentary tasks. If a system with such simple rules can generate such endless and dynamic conditions, it should be no wonder that scientists theorized that more complex CA could provide a way to model real world phenomena. Indeed the founder of CA theory, John Von Neumann, originally envisioned the project as a way to examine the potential ways in which biological life functions and emerges from dead matter. [5]

The CA which we will first concern ourselves with is much more complicated than Life, however some basic commonalities of design philosophy and setup will carry over. One could even, if so inclined, run a simulation of our combat models on a computer within life.

Another CA which is of enough interest to mention briefly is the Ising model. While Conway’s Life serves mostly as a mathematical curiosity, some CA are of use as practical models of physical reality. If we are to attempt to model real life military combat as a CA then we should first introduce a use case using a CA to model a real life physical phenomenon, in this case the magnetization of a simple piece of metal.

Our tool in this case is called the Ising model, named after physicist Ernst Ising. Like Life, the Ising model consists of a rectangular grid of notes with two possible states: in this case +1 and -1. These two states represent the spin of a particular particle. While we won’t delve too deeply into the physics it suffices to say that a magnetization is induced when the spins of a material’s constituent particles, (represented by our grid) align in phase.

The dynamic evolution of a node in the system is determined by the influence of the spins of adjacent nodes/particles (one can also take into account non adjacent particles, but using merely adjacent particles is a suitable approximation). If the underlying material is magnetic, the spin of each lattice node will tend to shift in order to match the average of its surrounding nodes. One can therefore see how a system becomes magnetized when exposed to an outside influence which biases the nodes toward aligning. Temperature acts as a confounding variable, and a higher temperature will cause nodes to switch at random. The model allows us to see the behavior of a material, (for example iron), over time at a particular temperature t, when it is exposed to a magnet.

The Ising model provides an example of a complex and nonlinear dynamical system in statistical me- chanics being reducible to a set of interacting parts. The Ising model is of great interest to CST, and its properties have been studied extensively. CST often concerns itself with the study of statistical mechanics, which likewise views the behavior of a highly complex system by examining it’s macroscopic, average be- havior over large time scales, rather than keeping track of minute details. Such techniques will later come into play when learning about battlefield modelling.

3 The Instantiating of ISAAC

The first combat model we will look at is called ISAAC, or Irreducible-Semi-Autonomous-Adaptive-Combat. ISAAC grew out of a desire to model combat using the tools and philosophy of Complex Systems Theory. Previously combat was understood mainly through the use of differential equations commonly called the Lanchester Equations or LEs. While these equations provided a useful macroscopic approximation of the state of a battle, they leave out much of the emergent complexity of a real life conflict.

3.1 Lanchester’s Equations

Lanchester’s equations describe the rate of attrition, or change in population, of two armies, for our pur- poses called ”Red” and ”Blue,” via the following linear dependency:

In the above equations, (t) is the rate of change in the number of red soldiers. If one were to solve this dt

differential equations, they could determine the number of red soldiers as a function of t. Lanchester’s Equations assume that (t) is proportional to the remaining population of blue soldiers and vice versa. The constants of proportionality: α and β must be solved for based on real world empirical data.
By dividing the two ordinary differential equations (1) and (2) by one another we can obtain another result, the famous ”Lanchester square law”:

This equation tells us that the incurred casualties of R will be proportional to the square of the enemy forces. This principle has been interpreted as vindicating the old military maxim: ”never divide your forces.” Since it implies that given the assumptions of Lanchester’s equations, shear numbers will always overwhelm the quality of an army.

Lanchester’s equations are a useful tool for gaining intuitions about combat, and provide a backbone to our way of thinking of attrition rates [4]. However their simplified nature, while providing a useful macroscopic model of combat attrition, has several notable drawbacks. First and most importantly the Lanchester model lacks any way to accommodate for varied terrain, army maneuvering, the geometry of force position, or anything other than pure fighting strength. Such considerations can only be expressed in the variable constants of proportionality, this type of dimensional reduction can help us to gain a quick overview of the situation and provide intuition, however it fails to capture more subtle changes which can result in novel battlefield tactics, it also requires a vast amount of data to calibrate α and β correctly.

Instead of modelling the entire system by only focusing on the number of extent forces of both sides, it is therefore useful to consider the interplay between each individual agent. This is an example of switching from a traditional viewpoint to the viewpoint of aent based modelling. Which brings us to the model in question: ISAAC.

[LANCHESTER PYTHON EXAMPLE]

3.2 ISAAC: the Basic Setup

Listing 2: Your Python Code

ISAAC or Irreducible-Semi-Autonomous-Adaptive-Combat, was an attempt to provide the first full model of war considered through the lens of complex systems theory. [3]

ISAAC is a CA/artificial life model, which considers combat from an agent based perspective. As dis- cussed earlier, Lanchester type models, and other differential equations used to estimate some state variable of a combat system (such as casualty rate, victory/defeat, etc) were limited to assessing macroscopic vari- ables such as total force numbers, and could not be readily modified to encompass changes in microscopic system variables, such as the ground level behavior of troops, the particular Command and Control ”C2” structure, or the local terrain. Such considerations had to be reduced down to constants which needed to be calculated empirically using past data. Even without considering the lack of high quality combat data to be considered, such a dimensionality reduction is bound to lose quite a bit of nuance.

In order to counter these limitations the CNA developed an agent based model inspired by cellular au- tomata theory, in order to better understand the large scale behavior of battlefields as nonlinear dynamical systems, and gain better insight into the emergent behaviors such systems produce [3]. The creators of ISAAC hoped that viewing combat through the lens of artificial life would allow for a valuable frame of reference with which to

• Study the efficacy of combat strategies • Capture patterns of behavior
• Sample probabilities of certain events • Use as a training aid

[3] In other words such a model would need to first reduce combat down to a set of simple agents and rules which govern those agent’s individual behavior and interactions. From there, the system would be allowed to evolve and demonstrate novel emergent behavior. As mentioned in ISAAC’s mission statement, seeing and studying this behavior could provide insight into basic principles of combat effectiveness and common behaviors of the entire battlefield as a complex system. Further tools of Complex Systems Theory could then be used to find the statistical probabilities of certain events, and a full theory of the behavior of battle as a dynamical system could take shape. Once this is realized, the insights taken from ISAAC could be used as a tool to aid real world combatants and commanders.

The basic idea of ISAAC is similar to the CA we have already seen in this paper. ISAAC consists of a two dimensional grid of arbitrary size, with each node either occupied or unoccupied by a unit known as an ”ISAACA” or ISAAC-Agent. The ISAACA takes the role of a discrete combat unit, for example an individual soldier, a platoon, a vehicle, etc. While ISAAC appears to be a 2 dimensional automata, it actually includes a third dimension, which for each node on the grid stores the information reflecting the prescience or lack thereof of its corresponding ISAACA. In this respect it is more similar to another CA which we will discuss later know as the Lattice Boltzmann Method or LBM.

The dynamical evolution of the ISAAC system is determined by a single function which specifies the movement of individual ISAACA into a new location. This objective function determines the individual ”goal” of an ISAACA and its interactions with nearby ISAACA in an analogous way to the rules of a more simple CA like Life. Such minimization functions are common to ABM methods, where individual agents must compete with each other to satisfy individual preferences, the field of operations research has been largely devoted to studying the best way to maximize the payoff of an agent given certain restraints using tools from optimization theory and game theory. During each time step of the ISAAC system, each ISAACA determines the location with the minimum value of its objective function, and moves accordingly. Likewise combat between ISAACAs is adjudicated, and the internal state of each ISAACA is updated.

3.3 ISAACA

We have already mentioned that each node in the ISAAC system’s area can be occupied by an ISAAC-Agent or ISAACA. These ISAACA can be thought of as individual combat units, as such they posses a number of state properties which determine their behavior, and have a number of capabilities which determine their behavior. These state properties can be broadly categorized into three categories:

• Goals/Personality
• Sensors
• Adaptive capabilities

[1]
These state properties determine the behavior of local ISAACA and are determined in turn by other

local ISAACA and global C2 hierarchy. These properties will determine how an ISAACA behaves in the next time step, as well influence other ISAACAs which must respond to its actions.

The most important of these ISAACA variables is whether a given ISAACA is alive, dead, or injured. This state of the ISAACA will determine the capabilities of the ISAACA at a given time step. We may call this the ”Status” variable if we like, and it takes 3 possible states. If an ISAACA is dead then it has no ability to influence other ISAACAs or the battlefield, if it is injured it will have decreased ability to influence the ISAAC system but will retain certain reduced functionality. If the ISAACA is alive it will behave according to its original personality vector without any additional modifiers.

The second consideration for each ISAACA is the ranges of its sensors, movement capabilities, commu- nication capabilities, etc. These are integers

rs, rm, rc, …

which determine the area inside which an ISAACA may perform a corresponding task. For example movement is generally restricted to an ISAACA’s directly adjacent cells, or its Moore neighborhood. This means at a given time step t, the ISAACA could move into one of nine possible locations by time t + 1, (including the option to stay in one place), as follows:

The possible locations to which the ISAACA can move is also the domain of its objective function Z(x, y), (x, y) ∈ [Moore neighborhood], it is represented above, where the black circle represents the current location of the ISAACA.

Instead of the general Euclidean or an approximation, we define the distance function on the ISAAC grid to be: d() and each integer ri represents the distance in this metric around the ISAACA that it can perform a given capability. These ranges appear on an instantiated ISAAC grid to be concentric boxes. This distance is also known as the Chebyshev distance or L∞ metric.

The ranges to be considered are given in the original ISAAC paper to be the following:

• Sensor range: maximum distance an ISAACA is able to detect other ISAACAs
• Fire range: maximum distance an ISAACA is able to fire at enemies
• Threshold range: maximum distance an ISAACA is willing to factor another ISAACA into its objec- tive funtion
• Communications range: maximum distance an ISAACA is able to take into account communications information from another ISAACA into its objective functionThe second major component of a given ISAACA is it’s objective function which was briefly mentioned before. The objective function is a function of the information currently available to a given ISAACA which outputs the location an ISAACA will inhabit at time t+1. The objective function is analogous to the ob- jective function of a linear program in operations research as discussed earlier. The function determines the ISAACA’s next move by minimizing the penalty incurred by each possible future movement. If the objective function gives equal penalty to two different spaces, it chooses between them at random [3]The objective function takes in the information available via the ISAACA’s sensors, namely:

where Ni,j represents the number of ISAACA of type i, j within the range of a given ISAACA’s sensors, rcolor and scolor are constants, and d[, (x, y)] is the distance function between two points x and y established earlier in this section.

The objective function outputs a number which increases or decreases proportionally to the number and distance of enemy and friendly ISAACA near a given potential grid space (x,y). Whether the function in- creases or decreases according to these considerations, and by what amount, is determined by the constants wi.

The ISAAC will determine its next move by minimizing the the distance function, so that its location at time t+1 will be:

(x′, y′) = min[Z(x, y)] x,y

with (x’,y’) within the ISAACA’s Moore neighborhood.

The proportionality constants wi are called the ISAACA’s personality vectors: Pi =<w1,w2,…,w6 >

each component of a given ISAACA’s personality vector represents the ISAACA’s disposition toward a particular course of action. namely each wi is a proportionality constant of one component in an ISAACA’s objective function.

If we take the view that an ISAACA is analogous to an individual soldier, then the purpose of the ISAACA objective function can be better understood. Under this view the ISAACA’s personality vector represents a soldier’s individual preferences and his/her superior’s orders. The soldier takes in the infor- mation which is available to them through their reconnaissance capabilities, and combines that information with their preferences. Through this process they decide on their next move as they continue throughout the battlefield.

Because the ISAACA’s decision making process is dependent on the behavior and location of other ISAACAs, the system has many built in feedback loops and can generate complex emergent behavior, which we will discuss in the upcoming sections of this paper.

3.4 Adaptive Behavior and Metapersonality

Each ISAACA can be programmed not just to statically react to its environment but also modify its own personality vector based on the current status of the battlefield (the entire ISAAC system). In this way an ISAACA’s personality vector was a function of the current state of the ISAAC:

P′ = M(P,C)

In the original CNA ISAAC paper, this was done via the existence of several threshold variables rT. Should a given battlefield parameter, such as number of friendly ISAACA’s within rS exceed rT, then the ISAACA’s personality vector P will change. Symbolically:

if N_alive_friends >= r_T P = M(P,C)

Listing 3: Your Python Code

The threshold ratios which are given in the original ISAAC paper give a number of friendly ISAACA’s which must be in range to begin advancing toward the enemies flag, a density after which an ISAACA will no longer tend to cluster to it’s allies, a threshold which specifies the combat advantage which must be present for the ISAAC to engage the enemy, and various minimum limits for unit density, distance to enemy, and distances to its own flag.

Each of these thresholds has an accompanying function which must surpass its associated threshold for the personality vector to be updated. In this way an ISAACA is able to adapt to its local environment in a similar way to a real soldier, albiet a much simplified model of one.

7

3.5 ISAACA Combat

ISAACA combat is an idealized model of real world combat, each ISAACA, in a given order, is given the opportunity to shoot at all enemy ISAACA’s within it’s fire range. The probability of a hit is given by p(hit|color), in general an ISAACA will have a reduced probability of hits while in an injured state. A hit ISAACA will revert to an injured or dead state according to the parameters of the simulation. If a shot ISAACA is transformed into its dead state, it will cease having an influence on the ISAAC system.

The situation can be modified by giving ISAACA’s an armor counter, equivalent to a health meter, which ticks down by one for each succesful hit. If desired, the model can be modified to include friendly fire.

3.6 ISAAC C2 Hierarchy

The ISAAC cellular automata also has the ability to accommodate a primitive command and control hi- erarchy. Each ISAACA can be a local or global commander. Once an ISAACA is instantiated as a local commander, or LC, that ISAACA is given a new range called its command radius Rcommabd. While within this radius, any non LC ISAACA will switch to a modified objective function which includes terms repre- senting the commands of their LC. This is given explicitly by the following.

Z(x, y) = Z0(x, y) + wLC(move to (xLC, yLC)) +wobey(move to (xB, yB))

In the above equation, Z0 is the objective function of a non commanded, i.e. independent ISAACA. Once it is under the command of its LC, an ISAACA will have an additional term in its objective function. Commanded ISAACA have new weights for staying close to commanders and obeying them, namely wLC and wobey in the above equation.

A given LC’s command radius, Rcommabd, is split into a grid of nine zones centered at the LC. The LC will order its commanded ISAACA’s in the direction of zone k ∈ [1, …, 9] according to which k minimizes the new command term in the objective function:

(Friendlyi − Enemyj) Zk=∑[ai(N ]

i,j∈(alive,injured) f riendly

where k is one of 9 cells surrounding the LC. and Friendly1 and Enemyi are the number of Friendly or enemy ISAACA in state i within the range of the LC. It should be noted that the command term of the objective function specifies the direction towards zone k, which modifies each of the nine squares around a commanded ISAACA.

in the event of an LC death a random ISAACA is promoted in it’s place.

In addition to local commanders, ISAAC can instantiate global commanders or GCs. GCs mediate interactions between LCs, and determine to send reinforcements to an LC if it is in danger.

Danger is determined by a health function which decays along with the ration of alive friendlies to ene- mies decreases within an LC’s command radius. These GCs also partition the battlefield into 16 subsections

with directions corresponding to way points along the outer edge. a sector is defined as a cone of approach in the direction of 3 way points and the action taken by a LC is defined by the minimization of a function Pi = (penalty for movement toward way point i) + density of enemies in that direction.

explicitly this is done by the following equation :

Pi = (1− fear)(waypointweight)+(fear)(EnemyDensityi)
where ”fear” is some constant representing the ISAACAs reluctance to move toward danger. The deci-

sion to obey a GC (and other drives) is governed by weights Oi as follows

−Z(x, y) = Z0 + ∑ Oobey [(move− > LCi ) + Osector (move− > LCi )] i

8

where if Oobey = 1 they treat their own desires and orders equally 3.7 Genetic Optimization

ISAAC is also capable of evolving in a system wide way. In order to accomplish this, one ISAAC force color will be fixed, and the other will be allowed to mututate over successive generations. This means that the personality vector, along with all other parameters governing each ISAACA in the mutable force color, will undergo successive changes over each iteration of the game.

The basic setup goes as follows: first, a large random assortment of ISAACA parameter vectors is cre- ated. Next each personality has it’s fitness determined by cycling through multiple runs of the ISAAC engine. ISAACA parameter vectors which are determined to minimize the fitness objective function are bred together with recombination, and those who are unfit are eliminated. Random mutations are created and the situation is repeated until the program is terminated.

3.8 ISAAC: Conclusion

Although the ISAAC model is relatively simple, and lacks much of the complexity of a true battlefield situ- ation, its value can be seen when one considers emergent behaviors that arise under its simple conditions.

4 EINSTein

The EINSTein system is an updated version of the ISAAC system created by CNA. It works similarly to the ISAAC system: agents are given a personality vector, an objective function to minimize, and a local C2 hierarchy is created. The EINSTein system builds on the ISAAC model by adding the option to create diverse terrain conditions which are either uninhabitable by ISAACA or modify the ISAACA’s personality vector in a certain way. For example a terrain area could represent foggy weather and hence reduce an ISAACA’s sensor range by a specified amount.

EINSTein once again is an attempt to model a battlefield as a complex adaptive system which arises from the simple behaviors of individual agents [2]. With this in mind, the system is not designed to be a true warfare simulation but an example of complex adaptive behavior which mirrors the behavior of real life strategic practices.

Once again the core philosophy is one of agent based modelling, which can show emergent macroscopic behaviors. EINSTein has shown such complex behavior emerging as consequences of its simple rules. For example advances, retreats, and even guerilla like attacks [2].

Moreover, the EINSTein system is described by IILachinsky in terms of fluid dynamics, displaying lam- inar, viscous, and turbulent flow. Illachinsky also describes autopoeisis occuring and the creation of tem- porary dissipative systems.

5 Vistas

Now, having seen previous attempts to create a battlefield simulator based on agent based modelling tech- niques, we might ask what future improvements and innovations might take place in the field, and to what areas these techniques could be applied for the use of modeling and simulation.

We suggest that while the geometry of force movements appears to be somewhat self emergent, further psychological considerations could take into account the topology of troop movements more significantly

We first suggest that a similar agent based modeling system could be applied to the study of political violence within a state. In this case, the shoot method coul dincur a cost of civilian casualties.

5.1 Example Code

The following is a short and simplified version of the code written in python: 9

References

1. [1]  Christopher P Fredlake, Kai Wang, and CENTER FOR NAVAL ANALYSES ARLINGTON VA. Einstein goes to war: A primer on ground combat models. Online Text], Center for Naval Analyses, http://www. dtic. mil/dtic/tr/fulltext/u2/a488178. pdf (accessed: 03/11/2016), 2008.
2. [2]  Andrew Ilachinski. Einstein: A multiagent-based model of combat. In Artificial Life Models in Software, pages 259–315. Springer, 2009.
3. [3]  Andy Ilachinski. Irreducible semi-autonomous adaptive combat (isaac): An artificial-life approach to land combat. Military Operations Research, pages 29–46, 2000.
4. [4]  Ronald L Johnson. Lanchester’s square law in theory and practice. School of Advanced Military Studies, Fort Leavenworth, Kansas, USA, 1990.
5. [5]  Palash Sarkar. A brief history of cellular automata. Acm computing surveys (csur), 32(1):80–107, 2000.