Social distancing as a game of Tetris

Social distancing. Before the COVID-19 pandemic many of us had never heard about it. It refers to the act of introducing distances between people in order to prevent the spread of a contagious disease.

As the virus responsible for COVID-19 made its way around the world and started spreading throughout our communities, this crude measure became necessary to stop out-of-control growth of infections. Cinemas, restaurants, bars and other public venues had no choice but to close their doors, resulting in an enormous social and economic impact on society as a whole.

Gradually we learnt more about the virus and its major modes of transmission, directly through contact and respiratory droplets and indirectly through aerosols and contaminated surfaces. Mitigation strategies involving face masks and proper ventilation were introduced, and gradually a refined picture appeared of the effect and cost of the various containment measures.

Where are we right now? Vaccines have shown us the light at the end of the tunnel. However, with new variants appearing across the globe, it now also seems plausible that the disease will stay with us in some form in the foreseeable future. As a consequence it is important to employ targeted measures that keep society open at minimal risk for outbreaks.

In this article we will look at a tool we developed that allows public venues to open up safely and according to guidelines and rules, by placing groups of people (for instance, from the same household) at a safe distance from each other.

Auditoriums and group shapes

We consider a given auditorium with fixed seats at given locations. The simplest example is a rectangular grid

An auditorium with fixed seats at locations forming a rectangular grid

More exotic configurations can be imagined, but we will stick to this setting in this article.

We assume that people come in groups of different sizes. For a given group size we can arrange the group in different (connected) shapes. Taking into account all possible orientations, there are 2 such shapes of size 2, 6 shapes of size 3 and 19 configurations for shapes of size 4:

The dominoes (top left), trominoes (bottom left) and tetrominoes (right)

What are these shapes even called? One way of identifying a combinatorial structure and learning more about it is by simply counting and looking it up in the Online Encyclopedia of Integer Sequences. Searching for 1, 2, 6, 19, 63, yields the sequence A001168, describing the number of fixed polyominoes with n cells (generalizing dominos). We can simplify this a little bit, by only considering polyominoes up to rigid transformations (translations, rotations, reflections, and combinations thereof). For groups of size 4 we then get the blocks familiar from the game of Tetris.

Optimal seating plans

The goal is to maximize the number of people that can be seated in the auditorium, while satisfying social distancing constraints, as well as constraints involving the sizes of the groups in which people show up.

Let’s suppose our social distancing constraint is that people in different groups need to be seated at least 1 meter apart (from shoulder to shoulder). Because of this, placing such a shape in the grid will yield restrictions on the surrounding seats that are within this distance. We call these the buffer seats to distinguish them from the actual seats. Note that any seat can be used as a buffer seat by multiple groups, while using a seat as an actual seat disqualifies it from future use (as a buffer or actual seat) by another group. The figure below shows a shape that counts 4 people placed at their actual seats (red), together with surrounding buffer seats (grey)

A shape of four seats (red), with anchor at the cross, surrounded by buffer seats (grey)

One of the actual seats is designated as the anchor seat (cross); it tells us where in the grid we anchor this shape when enumerating the possible placements of this shape in the grid.

In order to get a computer to help us solve our problem, we need to formulate this more precisely (and sometimes state the obvious). We arrive at the following ABC of seating plan constraints:

  • Actual seat constraints: Any seat can contain at most one person.
  • Buffer seat constraints: Any seat cannot be used simultaneously as a buffer seat and as an actual seat.
  • Counting group constraints: Selected shapes have sizes consistent with those of the groups of people buying tickets.

Mathematical formulation

Inspired by [1], we can formulate the above problem mathematically as follows. Let the symbol S represent the set of all shapes that we consider (for instance the polyominoes up to a certain size), and let s denote any one of these shapes. Similarly L represents the set of all locations that we consider (for instance a rectangular grid), while l (and sometimes l’) denotes any one of these locations.

We need to make decisions on which shapes to select and where to place these shapes. Every such placement is represented as a pair (s,l) of a shape s and an anchor location l. The placements are unknowns, and they are decision variables that we represent by the symbol Xₛ,, which takes the value 1 if we decide to place shape s at anchor location l; otherwise it takes value 0. We specify in advance which combinations of the shape s and location l we will consider here. For formulating our actual seat constraints, it helps to specify a separate set A(l) for each location l, containing the considered pairs (s, l’) of shapes s with anchor location l’ that cover location l. Analogously for the buffer seat constraints, we specify a set B(l) for each location l, containing the considered pairs (s,l’) of shapes s with anchor location l’ that have a buffer area that covers location l. Let w be an upper bound on the number of placements that can share a given location as a buffer seat. This depends on the buffer area surrounding the shapes, but w = 10 will typically do. Next, we count the number of seats in each shape in S and collect these counts in a set C. Finally, we suppose that we have knowledge of the typical number of groups of a given count c that normally book for a show, in terms of a lower bound lower(c) and upper bound upper(c).

The (static) seat allocation problem can now be stated as the following binary integer linear program:

A toy example

Consider the auditorium given by the 2 x 2 grid

This grid can be indexed by the set L = {(0, 0), (1, 0), (0, 1), (1, 1)} of locations. We assume that the social distancing constraint requires a buffer seat both horizontally and vertically. We consider all the shapes s of counts c = 1, 2, that is,

Shapes of counts 1 and 2, surrounded vertically and horizontally by buffer seats

We can look at all possible placements of these shapes in the grid, that is, all possible combinations (s,l) of placing shape s in the grid at anchor location l. We obtain 8 such placements (s,l),

Placements of the shapes of counts 1 and 2 in the 2 x 2 grid of locations

There are 8 corresponding decision variables Xₛ, each with value 0 or 1, resulting in 2⁸ = 256 potential seating plans to be analyzed. Due to the constraints, only a subset of these are valid. Due to the small size of this theater, let’s forego the counting group constraint. Let’s analyze the remaining constraints by explicitly describing, for each location l (left) in the grid, the sets A(l) (middle) and B(l) (right).

For each location l (left), the sets A(l) (middle) and B(l) (right)

Recall that A(l) denotes the set of placements (s,l’) whose actual seats cover l, while B(l) denotes the set of placements (s,l’) whose buffer seats cover l. The actual seat constraint tells us that in each row corresponding to a location l, we can select at most one placement from the columns 2–4. If we do so, none of the layouts in columns 5–8 can be selected, because otherwise an actual seat would serve as a buffer seat for another group, which cannot happen.

Due to the tiny grid in this toy example, we can now simply enumerate all viable seating plans. If we select the placement with a singleton placed in the top-left corner, the only remaining valid placement is the singleton placed in the bottom-right corner. Taking symmetries into account, we obtain the viable seating plans

If we select the pair filling the top-row, then the constraints in the table exclude all the other placements. Again taking symmetry into account, we obtain the viable seating plans

Thus we find the following 6 optimal solutions in this case:

Optimal solutions to the static seat allocation problem for shapes of counts 1 and 2 on the 2 x 2 grid

What’s next?

The above toy example was chosen small enough for it to be solvable by hand. In the next part we will see how larger static seat allocation problems can be solved quickly using linear programming methods, and apply this implementation to obtain optimal seating plans for a venue in Oslo. After that we will describe how reinforcement learning can be applied to solve a more challenging problem, namely the dynamic seat allocation problem.

Acknowledgments

This is joint work with Daniel Palhazi Cuervo, Heidi E.I. Dahl, and Patrick Schittekat, and it was funded by an extraordinary basic funding grant by the Research Council of Norway.

Links

[1] https://sysid.github.io/polyominos

Research Scientist at SINTEF Digital, Mathematician