Implementing Vaccination v3.4

This document describes the implementation of vaccination in ADSM 3.4.

Problem statement

In versions of ADSM up to and including 3.3, the priority system for vaccination was based on production type, reason for vaccination, and time waiting. This system is fairly static: once a unit is flagged for vaccination, there is not much opportunity for it to move around within the priority system. The only time a unit’s priority changes is if it is flagged for vaccination again, but for a different reason that outranks the previous reason.

In ADSM 3.4, it will be possible to prioritize vaccination to produce outside-in or inside-out vaccination ring patterns. The appearance of a new vaccination ring around a newly discovered IP will be able to substantially re-shuffle the priorities for units currently awaiting vaccination. The internal implementation of priority queues needs to change to handle this new fluidity.

Background

Figure 1 shows how pending vaccinations were stored in ADSM 3.3. The figure shows just the cases where production type has priority over reason. The queues of pending vaccinations capture the time waiting (older ↔ newer), and the vertical ordering of the queues captures the importance of different production type/reason combinations.

Figure 1: The data structure used for priority queues in ADSM 3.3.

Figure 2 shows what happens if the modeler sets up a priority scheme where production type is most important, reason for vaccination is next, and time waiting is last. We consume the entirety of the first queue, then move on to the next one down.

Figure 2: Priority order is production type, then reason, then time waiting.

Figure 3 shows what happens if the modeler sets up a priority scheme where time waiting is most important, production type is next, and reason is last. We scan down the queues, peeking at the oldest pending vaccination in each one, and select the overall oldest pending vaccination (ties are resolved by selecting the higher-up one). Then we repeat.

Figure 3: Priority order is time waiting, then production type, then reason.

Finally, Figure 4 shows what happens if the modeler sets up a priority scheme where production type is most important, time waiting is next, and reason is last. We scan down the queues for the first production type, selecting the oldest pending vaccination just for that production type, and repeat. Once the queues for this production type are empty, we skip down to the queues for the next production type.

Figure 4: Priority order is production type, then time waiting, then reason.

Proposed replacement

The proposed replacement will use a generic sorting function. A sorting function requires two things: a list of items, and a comparison function that, given two items A and B, returns either A<B, A>B, or A=B.

In our case the list of items will be a list of scorecards. The “scorecard” is a data structure that Drew Schwickerath developed for NAADSM 4 and 5. It holds all the information that the simulated authorities in the scenario would know about a given unit: whether it has been detected, whether it is awaiting vaccination and for what reason, when it was last vaccinated, etc.

The comparison function will be a function that takes 2 scorecards A and B and a chain of prioritizer objects. Each prioritizer object will compare scorecards based on a single criterion. For example, the prioritizer may contain an ordered list of production types and return A>B if A’s production type is higher in the list. Or, the prioritizer may compare the sizes of units A and B and return A>B if A contains more animals.

The comparison function will ask the first prioritizer in the chain to compare scorecards A and B. If the prioritizer decides that A has a higher priority than B (or vice versa) then the sort function is finished. However, if the prioritizer decides that A and B have equal priority, then the sort function will ask the next prioritizer in the chain to break the tie, and so on down the chain.

There are a variety of sorting functions available, for example, the classic quick sort and merge sort. I propose to start with qsort but also test Timsort, an algorithm developed in 2002 that is a hybrid of earlier algorithms and reportedly excels in situations when a list may be in nearly-sorted order already (as is likely to be the case for us). An open-source implementation is here.

Data structures for priorities

Figure 5 shows the data structures used. There is a set (GHashTable) of units currently awaiting vaccination; this allows for quick lookups of a unit’s status w.r.t. vaccination when a request to vaccinate or a request to cancel vaccination occurs. There is a list (GPtrArray) of scorecards, which is sorted into reverse priority order and used to get the units to vaccinate each day.

Figure 5: C data structures to store the set of units currently awaiting vaccination and sort them by priority.

Figure 6 shows additional data structures used to implement round-robin priority order. Round-robin maintains a list of active vaccination rings, and vaccinates the highest-priority unit in the first ring, then the highest-priority unit in the next ring, and so on. This is done by creating one “bucket” per active vaccination ring, then making a single pass over the sorted list of scorecards, either vaccinating the unit immediately (if the unit belongs to the ring we want) or placing the scorecard into a bucket.

Figure 6: C data structures to implement round-robin priority order.

Outside-in/inside-out order

This section will look at some possible ways of expressing the idea of outside-in/inside-out order, find one that produces a sensible-looking result.

Beginning with outside-in order, the first iteration at finding a strategy is:

Create an image in which a single protective vaccination ring is defined.
For each point in the image,

• find the distance d from the center of the ring
• if d > r_outer (outer radius), priority = do not vaccinate
• if d < r_inner, priority = do not vaccinate
• otherwise, priority = (d - r_inner)/(r_outer - r_inner)

This formula is meant to produce 0 for the lowest priority and 1 for the highest priority.

It creates the pattern seen in figure 7. The colors follow rainbow order (ROYGBIV), with red being the highest priority and violet, the lowest. White means “will not be vaccinated”.

Figure 7. Outside-to-inside priority order.

As a next check, create an image in which two non-overlapping protective vaccination rings of different sizes are defined.
Follow the same rules as before: for each point in the image,

• find the distance d from the center of the ring
• if d > r_outer, priority = do not vaccinate
• if d < r_inner, priority = do not vaccinate
• otherwise, priority = (d - r_inner)/(r_outer - r_inner)

This produces the pattern seen in figure 8, which is not correct. The RFC states that 2 rings should maintain the same thickness as they grow. But it is clear from figure 8 that that is not the case here: as the simulator vaccinates in priority order (following the colors), by the time the simulator is working on the yellow part of the rings, the completed (red) part of the large ring will be twice as thick as the completed part of the small ring.

Figure 8: Two rings that would not maintain the same thickness as they grow.

Modify the rules as follows:
Begin by finding w_max, the width (r_outer - r_inner) of the thickest possible ring. Then for each point in the image,

• find the distance d from the center of the ring
• if d > r_outer, priority = do not vaccinate
• if d < r_inner, priority = do not vaccinate
• otherwise, priority = (w_max - (r_outer - d)) / w_max

This produces the better outcome seen in figure 9.

Figure 9: Two rings that will maintain the same thickness as they grow.

Now what happens when rings overlap? So far it has been possible to define d as “the distance from the center of the ring” because it has been unambiguous which ring each point belongs to.

Try these rules:
Begin by finding w_max, the width (r_outer - r_inner) of the thickest possible ring. Then for each point in the image,

• assign the point as “belonging” to the ring whose center is nearest
• d = distance from the center of the ring the point belongs to
• if d > r_outer, priority = do not vaccinate
• if d < r_inner, priority = do not vaccinate
• otherwise, priority = (w_max - (r_outer - d)) / w_max

This produces the not very appealing outcome seen in figure 10.

Figure 10. Assigning each point to the ring whose center is nearest.

Try this modification:
Begin by finding w_max, the width (r_outer - r_inner) of the thickest possible ring. Then for each point in the image,

• for each active ring,
  • d = distance from the center of this ring
  • if d > r_outer, priority = do not vaccinate
  • if d < r_inner, priority = do not vaccinate
  • otherwise, priority = (w_max - (r_outer - d)) / w_max
• Take the lowest priority found for any active ring.

This produces the better outcome seen in figure 11.

Figure 11. Assigning each point the lowest priority it would get from any ring it is in.