You sank my battleship, or did you?

The purpose of this thinkover is to demonstrate how to propagate epistemic uncertainty in an agent-based model, and to observe its consequences on what emergent properties can be observed in its simulations.  The title is a reference to the exciting board game Battleship by Milton Bradley.

The agent-based simulations implemented in Python (available at the bottom of this page) describe a theatre of battle engagement at sea in which every ship fights every other ship by firing missiles if a target is within range of its radar.  Different ships have different radar ranges, different complements of missiles, different locations, speeds and headings on a grid. Ships and their respective radar ranges are displayed as circles in (crude) animations.  Orange ships are on fire from missile hits; red ships are blazing. Any ship that receives more than a threshold number of missiles will sink and disappear. 

There are two Python implementations.  In the imprecise battleship simulation, radar ranging is imprecise. Any target outside a ship's outer range will not be detected. Any target within a ship's inner range is sure to be detected. Targets within a ship's outer range but outside its inner range creates epistemic uncertainty.  In such cases, the target was both detected and not detected.  Thus, a ship would consequently both fire missiles and not fire missiles at it.  Depending on whether sufficiently many missiles land on a particular ship it may or may not sink.  Thus, under this epistemic uncertainty, the ship both exists and does not exist à la Schrödinger's cat.  In the simulation animations, a ship's imprecise ranging is depicted as concentric circles, and a ship whose existence is in doubt is depicted with dotted lines.  Such ghost ships may in fact have sunk, or they may be very much still firing missiles at the other ships. Like Schrödinger, we're not suggesting that cats or ships can simultaneously exist and not exist; all we are saying is that the simulation cannot know which state is the actual state.

The imprecise simulation uses a generalised logic known as Kleene logic which represents Dunno ("don't know") in addition to the traditional Boolean concepts of True and False, and a generalised arithmetic based on intervals for situations in which counts or measurements that are imprecisely characterised can nevertheless be used in quantitative calculations.  For instance at the moment depicted below, because there may be as few as 16 ships still afloat or as many as 20 ships still engaged in the battle, we say that there are [16,20] ships active.  Uncertainty about how many ships are left means we are likewise uncertain about how many missiles are in play across their combined armamentaria.

Compared to the precise version (battleshipABM.py), the imprecise simulation (battleshipImpreciseABM.py) has very few ships that definitely sink.  By the end of the simulation period, many ships have become the ghost ships that both exist and do not exist.  Some ships do sink, but if any ship becomes a ghost it doesn't seem to ever definitively sink.  This seems counterintuitive, because the count of remaining ships falls to a low number, seemingly invariably, in every precise simulation.  The epistemic uncertainty seems to insulate these ships from their otherwise sure fates.  But should this happen?  This outcome may be occurring because

1. it's a logic error within the Python code in the targeting function,

2. it is the result of puffiness caused by repeated uncertain numbers in the interval calculations,

3. there is something amiss with how the conditional in the if-else is handled,

4. it is actually correct and our intuition is incorrect.

This thinkover is convened to consider this issue, uncover the explanation for this counterintuitive outcome, and explore the ramifications for introducing epistemic uncertainty into agent-based models.

A few details about how the Python program works will be useful.  The code generalises Python's if statement with the ifelse() function

def ifelse(k, yes, no, maybe=None) :

    if k==kleene.false : return no

    if k==kleene.true : return yes

    if maybe==None : return env(yes,no)

    return maybe

which uses Kleene logic to dispense three outcomes, for true, false, and dunno, rather than the traditional two.  If the argument k is true, then the function returns the value of the argument yes.  If k is false, the function return the value of no.  If k is dunno, the function returns the value of maybe, or, if an explicit value for maybe was not provided, the convex hull or envelope of yes and no.

Thus, in the target() function, up to 3 missiles from the complement of ship s are fired at target t according to the conditional doit, which is true according to whether both ships exist, the target ship is within range, and the target is not the same as the ship firing:

def target(s) :

    for t in combatants :

      launch = m[s].min(3)

      landed = binom(launch,targeting)

      doit = e[s] & e[t] & (t!=s) & (dist(s,t) < r[s])

      m[s] = ifelse(doit, (m[s]-launch).max(0), m[s])

      h[t] = ifelse(doit, h[t]+landed, h[t])

The number of missiles that are launched from ship s are decremented from the count of its complement of missiles m, unless doit is false, in which case the count of its remaining missiles stays the same.  Likewise the number of missiles that land on a target increment its tally of hits h, unless doit is false in which case h stays the same.  Not all fired missiles land on their targets.  How many land depends on a random function of how many are launched and a theatre-wide constant binomial hit rate targeting.

One change has already been suggested as a possible solution that might prevent the uncertainty from insulating the ghost ships from sinking surely is to distinguish the conditionals for the launching and hitting calculations like this:

      doit = e[s] & (t!=s) & (dist(s,t) < r[s])

      m[s]=ifelse(doit&e[t],(m[s]-launch).max(0),  m[s])  

      h[t] = ifelse(doit,        h[t]+landed,           h[t])

However, this change does not seem to erase the counterintuitive outcome.

The battleship simulation does not use a current/next data structure, but rather each ship's that may impact other ships are played out in order.  After all behaviours of all ships have been expressed, the consequences on each ship are then assessed.  The behaviours of each ship are 

   1) sail to a new position,

   2) display itself on the canvas,

   3) target and fire upon other ships, and

   4) assess the damage from other ships.

Run the main program to do an animated simulation.  

The battle theatre is a 100x100 grid with a toroidal or Pacman topology so that, if a ship moves too far left or right and goes off the edge of one side, it will reappear on the other side. Likewise, going too far up will warp the ship to the bottom of the grid. The function singlepath() will illustrate the path across the grid of a particular ship.

Both precise and imprecise implementations are available as Python files at the bottom of this page.  You can download and run either version of the battleship simulation immediately in Spyder. The animation will look best if you open the Plots frame (next to the Variable explorer) or just make the console the size of a single graph.

Further motivation and discussion of the general issue of handling epistemic uncertainty in agent-based models can be found in the proceedings paper “Epistemic Uncertainty in Agent-based Modeling” delivered at REC2016.

See also the paper "Agent-based models under uncertainty" which recently appeared in the Taylor & Francis journal F1000 Research.

Vladik:  It is not clear why an uncertain ship cannot sink a certainly existing ship: uncertain ship means, e.g., that without our general description, in some possible histories, the ship is already destroyed. However, the fact that the ship is uncertain at this moment of the simulation means that in some possible histories, the ship is still there -- in which case it can sink another ship.

Vladimir:  In summary, the scenarios demonstrate that an uncertain ship cannot sink a certainly existing ship, as the missiles fired from such a ship are uncertain. Thus only the upper bound of the hit count for the other ship is increased. When the hit count’s upper bound exceeds the ship’s upper existence limit, the previously certainly existing ship becomes uncertain about its existence. This can be expanded to include that two uncertain ships cannot sink each other and that only a certainly existing ship can sink another certainly existing ship. Though the scenarios represent possible edge cases that can occur in the simulation, they can also illustrate the in-between states satisfactorily. These scenarios have been presented to aid in the understanding of the model; as the ships do not communicate with an external observer, thus we do not know the state of the ships or the number of missiles remaining.

Scott:  I would augment Vladimir's response by adding “but it does not (certainly) sink.  Recall that uncertainty about a ship’s existence means that we don’t know whether it has been sunk or not.” after the phrase “becomes uncertain about its existence”.  

We might go even further to acknowledge that this outcome is a result of treating the uncertainty here as epistemic rather than aleatory.  If it were aleatory, it could make sense to argue that in some possible histories missiles on uncertain ships could be fired and successfully sink their target.  But if we take care to treat lack of knowledge appropriately, an opaque epistemological barrier arises that precludes knowing about any such successes.  This situation is a fundamental consequence of our treatment of uncertainty, and it creates big differences in the outcomes compared to deterministic models.