Controlling a Population

Adwait Godbole

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


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. actions "" Run 1 actions "a" Run 1 actions "ab" Run 1 actions "aba" Run 1 actions "" Run 2 actions "a" Run 2 actions "ab" Run 2 actions "aba" Run 2
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

Thank You!

Back to research