Social Distancing via Coulomb’s Law

Show more

1. Introduction

COVID-19 became a major problem in the world in the early months of 2020. Countries have used varying approaches in addressing the problem, but the concept of “social-distancing” has become one of the most important defenses against the virus. Two major factors contribute to the spread of infection: population density [1] and transience [2]. The number of cases is disproportionately higher in densely-populated areas, such as New York City and Madrid. Additionally, these two cities also have a lot of “transience.” That is, many people move through these cities, due to the transportation infrastructure, leaving these cities more exposed to possible infections. New Orleans, Louisiana is a good example of transience being a problem. New Orleans is not a large city compared to those mentioned above, but the city held its annual Mardi Gras festival in February, where visitors came from all over the world. In March, public health officials realized holding Mardi Gras was a mistake, given that so many people in New Orleans became infected, presumably because of the large number of people who came to New Orleans [3].

In short, social-distancing is the best defense against the virus. Because of the importance of social distancing, a good social distancing tool is desired. The main motivation of this research effort is to assist with social distancing—finding the best way to address social distancing via our vast array of mathematical tools. These tools can be used to optimize the spacing of individuals in our collective attempt to minimize transmission of the virus. The body of literature contains a good amount of research relating to the circle-packing problem—a problem committed to optimizing placement of circles in a confined area such that the total area dedicated to circles is maximized. The research presented here slightly differs in that because particles, not circles, are placed into a unit square.

This research exploits Coulomb’s Law in an attempt to optimize the placement of charged particles in a confined environment. In this context, the charged particles are surrogates for individuals. Coulomb’s Law guides the charged particles as to where to go. This process is organized as a part of the meta-heuristic Simulated Annealing—a search process engineered to find near-optimal solutions for all sizes of optimization problems. The pursuance of Coulomb’s Law in this endeavor is considered the unique feature of this research.

In short, the contributions of this paper are summarized as follows:

· The social distancing problem is addressed, specifically via mathematical means

· Coulomb’s Law is employed in a novel fashion

· Near-optimal results are found for problems proven optimal

· The presented methodology can be employed to larger problems without loss of generality

The following sections describe Circle-Packing/Particle Arrangement, Coulomb’s Law, and how Coulomb’s Law is used to assist in particle movement via the Simulated Annealing search heuristic. The presented methodology is also used on sample problems resulting in near-optimal solutions. General conclusions are also offered, along with recommendations for subsequent research.

It should be noted that there are several terms defined in this paper. Specifically, Table 1 defines terms related to forces and Coulomb’s Law, Table 2 shows an example of this, while Table 3 defines terms related to the Simulated Annealing Process.

2. Circle-Packing and Arrangement of Particles

In its most general form, “circle-packing” is the practice of placing non-overlapping circles in a confined space. The circles need not be of the same diameter. The intention is to arrange the circles such that the wasted space (non-circle area) is minimized. This practice is important in the steel-stamping

Table 1. Coulomb’s law definitions.

Table 2. Net force calculation for example.

Table 3. Search parameters.

industry, as non-stamped steel is considered a form of waste. From an operations research perspective, packing some number of circles (*n*) of equal diameter in a confined space (such as a unit square or unit circle) has become a benchmark problem. For problems of this type, the objective is to maximize the diameter of the *n* circles [4] [5] [6]. The circle-packing problem’s optimal solution can only be determined via mathematical proof for a specific number of circles, and optimality has only been proven for small values of *n*. Optimal solutions for larger values of *n* remain an unresolved issue [7].

The research here differs from the above problem in that we are only interested in optimally spacing the *centers* of the *n* circles of concern. As such, we treat the centers of the circles as points on a two-dimensional plane, and wish to maximize the distance between centers of the two closest circles. Figure 1 shows optimal circle packing for *n* = 2.

Figure 1 shows two circles packed in an optimal fashion. The two circles do not overlap, and are both confined to the outer square. The inner square can be thought of as a unit square (all four sides having length of 1). Note that the centers of the two circles are contained in the inner unit square. Within the unit square the two centers comprise the optimal solution to the problem—the maximized distance between centers is $\sqrt{{1}^{2}+{1}^{2}}=\sqrt{2}$, and is illustrated by the diagonal line between the circle centers.

Maximizing the distance between the two closest circle centers is the objective for this research. Given that the larger values of *n* result in problems with unknown optimal solutions, we are motivated to provide a tool for addressing not just “large” values of *n*, but *any* particular value of *n*. From this point forward, these circle centers are referred to as “particles,” and in the context of social distancing, we wish to maximize the distance between the two closest particles (persons).

3. Particle Movement

In the context of this research, there are two ways to move individuals with the intent of social distancing in an optimal fashion. First of all, individuals hereafter are referred to as “particles,” which are simply points in space. It is desired that these particles be arranged such that the minimum pairwise distance between all

Figure 1. Two circles in optimal arrangement.

particles be maximized. In order to accomplish this objective, the particles are moved during a simulation process. For this research effort, two different ways to move the particles are pursued. The first is by exploiting the magnetic nature of charged particles, which is referred to as “polar movement.” The second way to move the particles is via “random movement.”

3.1. Coulomb’s Law and Polar Particle Movement

Magnetic particles are either positively charged or negatively charged. Particles of the same charge repel each other, while particles of differing charges are attracted to each other. Figure 2 shows this: (a) and (b) show repulsion, while (c) shows attraction.

Coulomb’s Law quantifies the force between the particles according to the Coulomb’s Law, which mathematically is as follows:

${F}_{ij}=\frac{1}{4\pi {\epsilon}_{0}}\frac{{q}_{i}{q}_{j}}{{d}_{ij}^{2}}$ (1)

The first term of this (1/4πe_{0}) is essentially a constant, used to convert the result into units of Newtons (N). This constant is not used here, as we are only interested in relative forces. The value of *q _{i}* and

${F}_{ij}=\frac{{q}_{i}{q}_{j}}{{d}_{ij}^{2}}$ (2)

We can state that the force between two charged particles is the product of their charges and inversely proportional to the squared distance between them, where the squared distance is as follows:

${d}_{ij}^{2}={\left({x}_{i}-{x}_{j}\right)}^{2}+{\left({y}_{i}-{y}_{j}\right)}^{2}$ (3)

With a basic understanding of Coulomb’s Law, we now need to understand how the forces of several charged particles affect a single particle. For this research, only positive particles move, while negative particles remain stationary – the forces imposed by the negative particles do, however, affect the movement of the positively-charged particles. Table 1 provides some relevant terms:

It is intended to determine the net force exerted on all positive particles. To do this, we combine the forces exerted on all positive particles in terms of horizontal and vertical components. Consider Figure 3, detailing a specific particle at the point (7, 11). It is our intent to sum all forces imposed on this specific particle to determine the net force acting on this particle.

(a) (b) (c)

Figure 2. Charged particles.

Figure 3. Forces imposed on a particle.

The find the net force exerted on some specific positive particle *i ^{+}*, the following two equations are used:

${\left({F}_{x}\right)}_{{i}^{+}}=\left({\displaystyle \underset{{j}^{+}=1}{\overset{{n}^{+}}{\sum}}\frac{\left({x}_{{i}^{+}}-{x}_{{j}^{+}}\right)}{{d}_{{i}^{+}{j}^{+}}}}\right)+\left({\displaystyle \underset{{j}^{-}=1}{\overset{{n}^{-}}{\sum}}\frac{\left({n}^{+}/{n}^{-}\right)\left({x}_{{j}^{-}}-{x}_{{i}^{+}}\right)}{{d}_{{i}^{+}{j}^{-}}}}\right),\forall {i}^{+},\forall j\ne {i}^{+}$ (4)

${\left({F}_{y}\right)}_{{i}^{+}}=\left({\displaystyle \underset{{j}^{+}=1}{\overset{{n}^{+}}{\sum}}\frac{\left({y}_{{i}^{+}}-{y}_{{j}^{+}}\right)}{{d}_{{i}^{+}{j}^{+}}}}\right)+\left({\displaystyle \underset{{j}^{-}=1}{\overset{{n}^{-}}{\sum}}\frac{\left({n}^{+}/{n}^{-}\right)\left({y}_{{j}^{-}}-{y}_{{i}^{+}}\right)}{{d}_{{i}^{+}{j}^{-}}}}\right)\forall {i}^{+},\forall j\ne {i}^{+}$ (5)

It is important to note that the first component of the above two formulae relates to the force between the particle *i ^{+}* and other positively-charged particles, while the second component relates to the force between positively-charged particle

The magnitude of the resultant net force is as follows:

${F}_{{i}^{+}}=\sqrt{{\left({F}_{x}^{2}\right)}_{{i}^{+}}+{\left({F}_{y}^{2}\right)}_{{i}^{+}}},\forall {i}^{+}$ (6)

The direction, or heading, of this resultant net force is as follows:

${h}_{{i}^{+}}={\mathrm{tan}}^{-1}\left(\frac{{\left({F}_{y}\right)}_{{i}^{+}}}{{\left({F}_{x}\right)}_{{i}^{+}}}\right),\forall {i}^{+}$ (7)

Table 2 shows how the net resultant force acting on the point (7, 11) is determined:

Using Equations (4) and (5) above, and summing the two right-most columns of Table 2, we have ${\left({F}_{x}\right)}_{i}^{+}$ of −0.3377, and ${\left({F}_{y}\right)}_{i}^{+}$ of −0.6263. This results in a net force magnitude of 0.7116 $\left({F}_{i}^{+}\right)$, and a heading of −151.67 degrees $\left({h}_{i}^{+}\right)$. Figure 4 details the resultant force.

Figure 4. Net force imposed in a single, positively-charged particle.

The importance of Figure 4 is that the resultant force (both magnitude and direction) presents the location to where the particle is inclined to move. Hereafter, this type of particle movement is referred to as “polar movement.”

Again, it is important to note that only positively-charged particles are subject to movement, so resultant forces are only determined for the positively-charged particles.

3.2. Random Particle Movement

Unfortunately, polar movement is not always possible, because resultant forces may take us outside the realm of feasible solutions (outside the unit square). Because in polar movement, only the positively-charged particles move, and their nature to repel each other will motivate these particles outside the realm of feasible solutions. Figure 5 shows an example of this.

Figure 5 shows us that the positively-charged particle desires to move outside the search space, rendering an infeasible solution. Furthermore, the heading of this particle will never change, essentially putting our search at a “dead end.”

In order to combat this problem, all movable particles are treated as “neutral” particles, and they are moved a very small amount according to randomly-selected magnitudes and headings. This approach is referred to as random movement, and is illustrated in Figure 6.

This research effort utilizes both polar movement and random movement in our attempt to find optimal spacing.

4. Search Methodology

This section describes the methodology used for finding the best spacing of particles according to the movement rules described above. Simulated annealing is the general search heuristic used. Simulated annealing starts with a random solution. Minor modifications are made to the random solution. If the modified solution is an improvement over the current solution, the modified solution

Figure 5. Example of infeasible polar movement.

Figure 6. Example of random movement.

replaces the current solution. Otherwise, the modified solution may replace the current solution, provided the degree of inferiority is small enough to meet a probabilistic threshold [8]. This process continues until a stopping criterion is met. At the end of the search, the best solution encountered is reported. The reason inferior solutions are sometimes accepted as current is to avoid being trapped at local optima in the search for a global optimum [9]. The following subsections detail the search.

4.1. Initialization

Prior to describing the search process, Table 3 provides definitions, some of which are a slight repeat of the definitions from Table 1.

Values for the following search parameters are chosen: *Iter*, *k _{B}*,

${x}_{i}~U\left(0,1\right),\forall i$ (8)

${y}_{i}~U\left(0,1\right),\forall i$ (9)

This is the initial solution. The objective function of this initial solution is as follows:

$\mathrm{max}\left(\mathrm{min}\left({d}_{ij}\right)\right),\forall i,j\ne i,where$ (10)

${d}_{ij}=\sqrt{{\left({x}_{i}-{x}_{j}\right)}^{2}+{\left({y}_{i}-{y}_{j}\right)}^{2}}$ (11)

Subject to the constraints:

$0\le {x}_{i}\le 1,\forall i$ (12)

$0\le {y}_{i}\le 1,\forall i$ (13)

The values of *Z _{C}*,

In layman’s terms, we wish to arrange *n* particles in the unit square such that the distance between the closest two particles is maximized. The mathematics of this model shows a scenario where the objective function is both nonlinear and discontinuous, meaning conventional solvers are unlikely to guarantee an optimal solution, especially for larger problems. This is the reason a search heuristic is pursued.

4.2. Movement

Prior to movement, the current solution is copied to the temporary solution. Movement is either in the form of polar movement or random movement, both described in Section 3. The probability of polar-movement is τ, implying that the probability of random movement is (1 − τ).

In polar movement, only the positively-charged particles move, while the negatively-charged particles remain stationary. All positively charged particles simultaneously move in the direction of their heading
$\left({h}_{i}^{+}\right)$ at a distance of
$\left({F}_{i}^{+}\right)$. In random movement, the *n*-particles move to a nearby, randomly-selected location. Regardless of the type of move, infeasible moves are not executed. The result of all movements is the temporary solution.

4.3. Evaluation

Once the (previously-described) move is complete, the objective function value (*Z _{T}*) is determined via Equation (10). A determination needs to be made as to whether or not to accept the temporary solution as the current solution. If the objective function value of the temporary solution is better than the objective function value of the current solution—that is, if

Otherwise, further evaluation is needed before accepting the temporary solution as the current solution. The inferiority of the temporary solution compared to the current solution is represented as δ, and is determined as follows:

$\delta =\frac{{Z}_{T}-{Z}_{C}}{{Z}_{C}}$ (14)

The probability of accepting the inferior temporary solution as the current solution occurs with the following probability:

$P\left(A\right)=\mathrm{exp}\left(\frac{\delta}{{k}_{B}T}\right)$ (15)

A uniformly-distributed random number of the interval (0, 1) is generated. If this value is less than *P*(*A*), the inferior temporary solution is accepted as the current solution. Otherwise, the inferior temporary solution does not replace the current solution. The content provided by Equations (14) and (15) cuts to the uniqueness of Simulated Annealing. Inferior solutions are occasionally accepted as current solutions so as to avoid being trapped at local optima. The probability of accepting inferior solutions decreases as the search progresses. The Boltzmann Constant (*k _{B}*) controls the probability of accepting inferior solutions [10].

A test step compares the temporary solution to the best solution. If the temporary solution objective function value exceeds the best solution objective function value (that is, if *Z _{T}* >

4.4. Search Status

If *q* is less than the specified number of iterations per temperature level (*Iter*), the value of *q* is incremented by one (*q* = *q* + 1), and control if the search returns to that described in Section 4.2. Otherwise, the current Temperature (*T*) is multiplied by the cooling rate to set the new current temperature (*T* = *T* * *CR*), and *q* is reset to 1. If the new resultant temperature is greater than *T _{F}*, control of the search returns to that described by Section 4.2, and

4.5. Search in Pseudocode

For a better understanding of the search process, details are provided in pseudocode form.

initialize();

while (T > T_{F}){

for(q = 1; q <= Iter; q++){

set temp-solution = current-solution();

if(~U(0,1)<τ)polar-movement();

else random-movement();

evaluate temp-solution();

if (Z_{T} > Z_{C}) set current-solution = temp-solution();

if (Z_{T} > Z_{B}) set best-solution = temp-solution();

else {if(~U(0,1)

set current-solution = temp-solution();}

} //end else

} //end q

T = T * CR

} //end while

report-best-solution();

When the best solution is returned, the x and y-coordinates of all particles associated with the best solution are reported, along with the objective function value.

5. Experimentation

The methodology presented above was carried out via agent-based modeling software. Agent based modeling is an extension of traditional object-oriented programming (such as Java or C++) in that the modeling environment is a dynamic system—the entire system is perpetually in a state of change [11]. The specific programming environment was NetLogo [12] [13].

5.1. Experiment in NetLogo

The methodology can be used for any value of *n*. As stated earlier, NetLogo was the programming software employed. The images provided via Figure 7 and Figure 8 are images from the NetLogo environment. Figure 7 details the randomly-generated initial solution for *n* = 18. The particles to be arranged are positively-charged, and shown via a blue “+” symbol. Additionally, the size of the particle is proportional to the net force acting on the particle, and the heading of the particle is also shown via the arrow at the end of the “+” symbol. The negatively-charged particles are shown in red via “−” symbols. These particles are stationary—they do not move, and are only present for their influence on the mobile, positively-charged particles.

After careful inspection of Figure 7, one will notice that the positive particles close to the negative particles have larger magnitudes and are pointed toward the negative particles. This is affirmation of Coulomb’s Law. Similarly, positive particle further from other particles have smaller magnitudes, again affirming Coulomb’s Law. Finally, positively-charged particles somewhat near each other are pointing in opposing directions.

After the Simulated Annealing was performed, the final solution was obtained and detailed via Figure 8. The is the “best” arrangement of the positively-charged particles is shown the maximized distance between the two closest

Figure 7. Starting solution, *n* = 18.

Figure 8. Final solution, *n* = 18.

particles was 0.3000, where the proven-optimal distance was found to be 0.3005 [14].

Figure 8 shows what the NetLogo program found to be the best overall solution. Here, the positively-charged particles are shown via black circles, and the negatively-charged particles are not shown. The maximized distance between the two closest particles is also shown.

5.2. Computational Experience

In finding the best solutions for values of *n *≥ 2, the search settings shown in Table 3 had to be adjusted for each unique value of *n*. For the trivial problems involving optimal spacing of 2, 3 and 4 particles (*n* = 2, 3, 4), the search best responded by eliminating the negative charge in the unit square. This makes sense, because for these values of *n*, the positively-charged particles are motivated to get as far away from each other as possible, regardless of other circumstances. Staring with five or more particles (*n *≥ 5), the negative force in the central portion of the unit square becomes more important. This is because for larger quantities of particles, some of them need to be attracted toward the central part of the unit square for optimal spacing. Adjusting the negative force from problem to problem was required to obtain desirable results.

For all problems, *T*_{1} was set to 40, while *T _{F}* was set to 1. The cooling ratio,

5.3. Experimental Results

Table 4 shows the results of the methodology presented here as compared to results proven to be optimal for several problems.

Table 4. Results from several problems.

For the problems pursued, the presented methodology averaged 99.89% as compared to proven optimal. The worst-performance was for *n* = 15, which was 99.27% as compared to optimal.

6. Concluding Comments

Methodology has been provided to address social distancing via Coulomb’s Law and a variant of the circle-packing problem. Results are encouraging. As the COVID-19 virus and its social impact continue to evolve, social distancing will likely be with us for a while, and what we’ve learned from the effects of social distancing will likely be applied to future crises of a similar nature.

The presented research most certainly can be taken further, particularly with regard to scale. While the virus continues to force us into social distancing, sporting events will have limited capacity, providing employment for the presented methodology. The same can be said for worship services. In these larger-scale situations; however, something other than a unit square will be required, given the differing shapes of large venues.

Another opportunity for subsequent research applies to the use of Coulomb’s Law, and more effective ways of using the law to find desirable spacing. Scientific principles of other types could also be investigated in attempt to achieve desirable spacing.

In summary, the findings of this work are as follows:

· Social-distancing in an optimal fashion can be addressed via an applied mathematical approach

· Near-optimal results were found when compared to existing problems with known optima

· A combination of Coulomb’s Law and random movement was needed to obtain desirable solutions

· The presented methodology can be scaled to larger problems without loss of generality

· The work exploited a novel application of Coulomb’s Law

It is possible that other scientific principles (other than Coulomb’s Law) would be employed to address this problem.

References

[1] Bosman, J., Harmon, A. and Smith, M. (2020) Corona Cases Slow in the US, But the Big Picture Remains Tenuous. New York Times, May 19, 2020.

[2] McCartney, S. (2020) Smart Travel Planning in the Time of Coronavirus. The Wall Street Journal, May 15, 2020.

[3] Woodruff, E. (2020) How Did Coronavirus Get to New Orleans? Scientists Scrutinize Virus Genome for Answers. The Times Picayune, April 20, 2020.

[4] Maranas, C.D., Floudas, C.A. and Pardolas, P.M. (1995) New Results in the Packing of Equal Circles in a Square. Discrete Mathematics, 142, 287-293.

https://doi.org/10.1016/0012-365X(93)E0230-2

[5] Specht, E. (2020) The Best Known Packings of Equal Circles in a Square.

http://hydra.nat.uni-magdeburg.de/packing/csq/csq.html

[6] Stephenson, K. (2003) Circle Packing: A Mathematical Tale. Notices of the AMS, 50, 1376-1388.

[7] Williams, R. (1979) Circle Packing, Plane Tessellations, and Networks, the Geometrical Foundation of Natural Structure: A Source Book of Design. Dover, New York.

[8] Kirkpatrick, S., Gelatt, C.D. and Vecchi, M.P. (1983) Optimization by Simulated Annealing. Science, 220, 671-679.

https://doi.org/10.1126/science.220.4598.671

[9] Metropolis, N., Rosenbluth, A., Rosenbluth, N., Teller, A. and Teller, E. (1953) Equation of State Calculations by Fast Computing Machines. Journal of Chemical Physics, 21, 1087-1092.

https://doi.org/10.1063/1.1699114

[10] Eglese, R.W. (1990) Simulated Annealing: A Tool for Operational Research. European Journal of Operational Research, 46, 271-271.

https://doi.org/10.1016/0377-2217(90)90001-R

[11] Castiglione, F. (2006) Agent-Based Modeling. Scholarpedia, 1, 1562.

https://doi.org/10.4249/scholarpedia.1562

[12] Railsback, S.F. and Grimm, V. (2015) Agent-Based and Individual-Based Modeling: A Practical Introduction. Princeton Press, Princeton.

[13] Wilensky, U. and Rand, W. (2015) An Introduction to Agent-Based Modeling: Modeling Natural, Social, and Engineered Complex Solutions with NetLogo. MIT Press, Cambridge.

[14] Mollard, M. and Payan, C. (1990) Some Progress in Packing Equal Circles in a Square. Discrete Mathematics, 84, 303-307.

https://doi.org/10.1016/0012-365X(90)90135-5