Social Distancing, Gathering, Search Games: Mobile Agents on Simple Networks

During epidemics, the population is asked to socially distance, with pairs of individuals keeping two meters apart. We model this as a new optimization problem by considering a team of agents placed on the nodes of a network. Their common aim is to achieve pairwise graph distances of at least D, a state we call socially distanced. (If $$D=1,$$ D = 1 , they want to be at distinct nodes; if $$D=2$$ D = 2 they want to be non-adjacent.) We allow only a simple type of motion called a lazy random walk: with probability p (called the laziness parameter), they remain at their current node next period; with complementary probability $$1-p$$ 1 - p , they move to a random adjacent node. The team seeks the common value of p which achieves social distance in the least expected time, which is the absorption time of a Markov chain. We observe that the same Markov chain, with different goals (absorbing states), models the gathering, or multi-rendezvous problem (all agents at the same node). Allowing distinct laziness for two types of agents (searchers and hider) extends the existing literature on predator–prey search games to multiple searchers. We consider only special networks: line, cycle and grid.