2018, Adwait Godbole’s internship

The population control problem is a parameterized control problem. We consider a population of m agents that all have the same behavior (described by a non-deterministic automaton) and a uniform controller that can enforce the same action for every agent. The objective of the controller is to guide agents in such a way that all agents reach synchronously a given target state. This model is insipired by control questions in biological systems. The population control problem then asks whether a controler can control a population of m agents, for every integer m.
This problem was shown to be EXPTIME-complete. More details are available in this report.