Improvement to the Movement Algorithm in the MANA Agent-Based Distillation

Introduction

Background

Agent-based distillations (ABDs) are low-resolution simulations based on cellular automata concepts and have been used to explore land warfare problems. Project Albert [1] is a United States Marine Corps (USMC) research effort attempting to integrate the application of ABDs with conventional wargames and simulations, by addressing areas (such as morale and training; operations other than war; and co-evolution of tactics) for which conventional models perform inadequately.

A number of ABDs have been developed, including the United States Marine Corps Irreducible Semi-Autonomous Adaptive Combat (ISAAC) and the Enhanced ISAAC Neural Simulation Toolkit (EINSTein) simulations [2]; the New Zealand Defence Technology Agency (DTA) Map Aware Non-uniform Automata (MANA) simulation [3]; the United Kingdom High Level Operations model using Cellular Automata (HiLOCA) [4] and the Australian Comprehensive, Research Oriented, Combat Agent Distillation Implemented in the Littoral Environment (CROCADILE) [5].

Movement within MANA

The Users Manual of MANA [6] states that “the most important action of an agent is to move.” This appears justified since being deliberately low-resolution means that the detailed physics of combat are abstracted to simple constructs and thus any interesting behaviour should appear as a result of manoeuvring of the agents about the battlefield which is a result of agent interactions. Movement of agents within the MANA ABD is based on a simple attraction-repulsion weighting system and an associated numerical penalty function. From its current location, an agent moves to the location within its movement range that incurs the least penalty. That is, the agent attempts to satisfy its desire to move closer to or further away from other agents and other battlefield objects (such as terrain, waypoints or goals). This algorithm is applied to each agent on both sides and each is moved to its new location. This process is repeated for each time step in the simulation.

The form of the penalty function implemented by the MANA ABD is hard-coded. The user only has control over the value of the weightings for each battlefield object. The user defines these weightings when a scenario is constructed and weightings are chosen to represent surrogates for the tactics employed by the agents. For example, one can mimic aggressive (defensive) postures of Blue by assigning relatively large positive (negative) weights to Red agents.

Given the simplistic nature of the attraction-repulsion weighting system, this will be at best an approximation to the true behaviour being modelled. What is important then, is that the movement algorithm implements the relationships that the user intends by assigning values to those weights. For example, consider the situation with weightings of +40 towards other Blue agents, –10 towards Red agents, and +20 towards the Red flag. Perhaps the most natural interpretation of this situation is that the agent is four times more likely to move towards other Blue agents than it is to move away from Red agents, and that it is only two times more likely to move towards other Blue agents than it is to move towards the Red flag.

However, there are two key factors which are not stated in the above interpretation that are important in terms of what the user believes is being modelled. These factors are the number of agents the agent is aware of (generally those within its sensor range) and the distances those agents are from the agent in question. For example, does the above weighting system interpret the total weight for five Red agents as –50, or is it independent of the number of Red agents observed (or is it some non-linear function)? Similarly, does the above weighting system degrade the weight towards Red agents as their distance from the agent in question increases (and is this degradation a linear function), or is it independent of these distances? Both of these questions are important for any weighting system in general, but are particularly relevant for those that reside in MANA.

Motivation and scope

A previous paper by the author [7] investigated the above questions with regard to the MANA (and a similar) ABD. There, counter-intuitive behaviour was observed and traced back to the underlying penalty function used in the code and an alternative implementation was offered for consideration. A static, non-combative example was used to demonstrate that the two algorithms could generate different paths. At that time, access to the source code of MANA was unavailable so that proper testing and comparison of the two approaches was not possible.

This paper remedies that situation by quantitatively comparing the approaches on a dynamic, combative scenario. Appropriate parameter values for the proposed approach are derived and the effect of the movement algorithm on typical parametric studies is investigated.

MANA movement algorithm

The equation that MANA uses to compute the penalty at each potential new location is given by:

$Z\text{n}\text{e}\text{w}=\left(\frac{WR}{\text{100}\ast R}\right)\left({\sum }_{i=1}^R\frac{Di,\text{new}+\left(\text{100}-Di,\text{old}\right)}{\text{100}}\right)+\left(\frac{WB}{\text{100}\ast B}\right)\left({\sum }_{j=1}^B\frac{Dj,\text{new}+\left(\text{100}-Dj,\text{old}\right)}{\text{100}}\right)+\left(\frac{WF}{\text{100}}\right)\left(\frac{DF,\text{new}+\left(\text{100}-DF,\text{old}\right)}{\text{100}}\right)$

Table 1 lists the definitions of each of the variables in this equation.

There are two features within this equation that limit its effectiveness. First, MANA uses the knowledge of the change in distance from a battlefield object (Blue entity, Red entity, flag) as a result of the potential move only in an absolute sense. This means that the penalty for moving towards a Red entity that is 5 units away will be the same as that for moving towards a Red entity that is 50 units away.

Second, the penalties for each instance of a battlefield object (Blue, Red, flag) are converted into an average. This means that the penalties from a number of Red entities may equally be represented by a single penalty from a single ‘fictitious’ Red entity.

A recent paper by the author [7] showed how each of these features could produce behaviours inconsistent with the likely interpretation of the conceptual intent. They further derived a condition for penalty functions to meet that appear to provide more logical behaviours.

Alternative movement algorithm

An alternative movement algorithm, which satisfied the above condition, was proposed [7] whereby the denominator of the Red entity and Blue entity components of the penalty was divided by $Di,\text{old}$and $Dj,\text{old}$ (the distances from the current location to the location of the i-th Red entity and j-th Blue entity, respectively). The alternative penalty function was then given by:

$Z\text{n}\text{e}\text{w}=\left(\frac{WR}{R}\right){\sum }_{i=1}^R{\left(\frac{Di,\text{new}-Di,\text{old}}{Di,\text{old}}\right)}^r+\left(\frac{WB}{B}\right){\sum }_{j=1}^B{\left(\frac{Dj,\text{new}-Dj,\text{old}}{Dj,\text{old}}\right)}^r+WF\\$

Using the difference of distances in the numerators and the old distances in the denominator meant that the change in distances (from the current location to the new location) were compared in a relative sense. The power of the positive scaling parameter r is implemented such that if the argument is negative then the result should be the negative of the r-th power of the absolute value of the argument. This is to ensure that the effect of moving closer or further away is not lost when the power of r is applied. An added bonus was that the penalty for staying in place is by definition equal to zero and thus needn’t be calculated (thus saving some computation time).

Under this new penalty function, agents assigned a stronger weight to those agents that were nearby than to those far away. For example, with Red entities three and six units away and a flag ten units away, if a Blue entity moved forwards it was 33% closer to the first Red agent, only 17% closer to the second Red agent, and only 10% closer to the flag, and these relative percentages were reflected under the new penalty function.

As presented above, the new penalty function still computed an average (albeit relative) penalty as it divided by the number of Red entities within sensor range. An alternative would be to use a cumulative function instead of an average. However, at times it may not be desirable to use either the cumulative or average functional. A generalisation of the above penalty function to incorporate this was given by [7]:

$Z\text{n}\text{e}\text{w}=\left(\frac{WR}{R^{\alpha }}\right){\sum }_{i=1}^R{\left(\frac{Di,\text{new}-Di,\text{old}}{Di,\text{old}}\right)}^r+\left(\frac{WB}{B^{\alpha }}\right){\sum }_{j=1}^B{\left(\frac{Dj,\text{new}-Dj,\text{old}}{Dj,\text{old}}\right)}^r+WF\\$

where α is a positive parameter.

Patrol scenario

The new and old movement algorithms were examined in [7] in terms of the paths generated in an otherwise static environment and showed that significantly different paths did indeed eventuate. The scenario examined here explores the impact on the combat effectiveness of such differing paths to a combat force. Note that both the Blue and Red entities will be using the same movement algorithm (that is, both using the standard or both using the new algorithm).

A simplified patrol scenario was used, consisting of a Blue section and a Red platoon (see Figure 1). Blue’s objective was to reach a checkpoint (located at bottom-left) safely by avoiding the Red platoon (spread across the area of operations). The Blue section is unarmed and can thus only manoeuvre, while the Red platoon can and will engage Blue with lethal force if within weapon range. Both sides have equal sensor range (20 units), which is twice that of Red’s weapon range (10 units), and equal movement speed (1 unit per time-step). Blue entities are attracted to the checkpoint (flag) with weight 10 and repelled from Red entities with weighting –10. Red entities have only a weighting towards Blue entities (and thus the actual value is unimportant).

MANA was executed 500 times for this baseline scenario to produce stable average measures of effectiveness (MOE). The simulation was halted when the first Blue entity successfully reached the checkpoint. The primary MOE was the average number of Blue casualties sustained, while the secondary MOE was the average time to complete the mission.

Movement algorithm parameters

The new movement algorithm is defined by two positive scaling parameters r and α. These need to be chosen before the results of the study can be generated. Figure 2 below displays the variation of the primary MOE (average Blue casualties) with both parameters.

It is apparent that the results are more sensitive to the scaling parameter r than α and that an optimum setting would be α=1 and r=1/2. This implies an average functional and that distances are scaled by the square root.

Scenario results

The first set of results compare the standard MANA movement algorithm with the new algorithm (with parameter values as suggested in the previous section) on the baseline patrol scenario with regard to the primary and secondary MOE. Figure 3 compares the distribution of Blue casualties.

We see that there are significant differences when using the different movement algorithms. The standard MANA algorithm results in the Blue section having a 50% chance of suffering at least three losses. The new algorithm, on the other hand, results in the Blue section having a 33% chance of suffering low losses and a 66% chance of suffering at most one loss. On average, the new algorithm results in approximately half as many losses to Blue than the standard MANA algorithm.

Figure 4 displays the corresponding distribution of mission completion times for the two algorithms.

This also shows significant differences when using the different movement algorithms, with the new algorithm generally resulting in the Blue section taking significantly longer to complete its mission. The reason for these differences is that the two algorithms interpret the input weightings in different ways. Figure 4 therefore raises the possibility that the comparison made from Figure 3 is unfair, in the sense that perhaps the Blue entities under the standard MANA movement algorithm were not given sufficient time to manoeuvre to the checkpoint.

A better comparison then would be that based on the data contained in Figure 5 which plots both the primary and secondary MOE.

We see that for the quickest missions both algorithms produce high Blue casualties—this corresponds to the Blue entities moving directly to the checkpoint without any deviation as a result of detected Red entities. However, as mission completion times are relaxed, both algorithms result in fewer Blue losses. But it is also clear that the new algorithm is able to produce much better improvements than the standard MANA algorithm, and in fact for any given mission completion time the new algorithm on average always produced fewer Blue losses (approximately half as many losses than the standard MANA algorithm).

Parametric studies

The previous section demonstrated that the new movement algorithm provided the Blue section with a clear improvement in combat effectiveness by resulting in significantly fewer casualties in the baseline patrol scenario. A common use of ABDs is not for ‘point scenario’ results but rather to investigate the scenario parametrically. A typical example might be to investigate the combat utility of improved sensor technology (indeed, this has previously been examined in this journal both by the author [8] and the MANA developer [9]).

Figure 6 presents a comparison of the two movement algorithms for such a sensor range parametric study of the baseline patrol scenario.

As before, we note that the new algorithm produces fewer Blue casualties than the standard MANA movement algorithm, for all circumstances. But of more interest, from a parametric study viewpoint, is the variation of losses with the parameter and not the absolute values.

Under the standard MANA movement algorithm we see a fairly constant improvement with increasing Blue sensor range, whereas under the new algorithm there is decidedly more non-linearity. If we view the horizontal axis as three regions (inside Red’s weapon range, inside Red’s sensor range, and outside Red’s sensor range), one can see the principle of diminishing returns operating in each (although less so in the third region).

This increased ‘richness’ in the parametric study under the new movement algorithm may have important consequences for the particular research question. For example, the near-linear ‘return on investment’ suggested by the standard MANA algorithm results would indicate that additional investment in sensor technology would be as beneficial irrespective of the current level of performance. However, the results from the new algorithm would indicate that there are definite regions to avoid (diminishing returns).

Summary

A previous paper by the author discovered counter-intuitive behaviour in the MANA ABD and proposed a new movement algorithm as a solution. This paper sought to compare quantitatively the two algorithms on a scenario to determine the difference in combat effectiveness of using each algorithm.

Default parameter values for the new algorithm were determined and the results indicate that quite significant improvements in combat effectiveness can be achieved under the new algorithm. Perhaps more importantly, it was also discovered that quite different results (and conclusions) could be produced in a typical parametric study, depending on the algorithm used.

References

Author

Dr Andrew Gill is a senior defence analyst with the Defence Science and Technology Organisation, Australia. His research interests are in the application of operations research methods to defence analysis. Dr Gill can be contacted on 61 8 82595112 or by fax at 61 8 82595624.