## Controlling a Population

Internship work at Inria, Rennes in Summer of 2018 under guidance of Prof. Blaise Genest

## Animations

Consider the following system with $m = 2$ (depicted as red and blue). Press "space" for animations!
Controller chooses $\pi = aba$. The following runs are possible amongst others.
Clearly run 1 was winning for the Controller but run 2 was not. Hence $\pi = aba$ is not a winning strategy for Controller. (Trivially though $\pi = \epsilon$ is.)

## Overview of results

• The population control problem is $\mathrm{EXPTIME}$-complete
• In case the system $\mathcal{A}$ is synchronizable, the synchronization time (worst case number of actions to be performed) is ${\color{blue} {polynomial}}$ in the number of agents and ${\color{red} {exponential}}$ in the size (number of states) of $\mathcal{A}$. These bounds are tight upto a constant factor in the exponent.
• Hence the algorithm proposed is optimal

## Possible Future Work

Probabilistic extensions of these systems - MDPs- may be used to model agents

NFAs are polynomial-time synchronizable. An interesting problem is to identify MDPs which are sub-polynomial - polylog-time synchronizable