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 $$ they want to be at distinct nodes; if $$ 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 $$ , 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.