LFCS Seminar: Tuesday 28 October: Patrick Totzke

Title: Optimally Controlling a Random Population

Abstract:

We will quickly find a park and randomly walk around. I will show you some butterflies and sheep and tell you how to get them all home safely, for sure.

The population control problem is a parameterized control problem where a whole population of agents has to be moved into a target state. The decision problem asks whether this can be achieved for a finite but arbitrarily large population. We focus on the random version of this problem, where every agent is a copy of the same finite MDP and non-determinism on the global action chosen by the controller is resolved independently and uniformly at random. Controller seeks to almost-surely gather the agents in the target states. We show that the random population control problem is EXPTIME-complete.

Based on joint and unpublished work with Hugo Gimbert and Corto Mascle, preprint on the arXiv: https://arxiv.org/abs/2411.15181, and code on GitHub: https://github.com/SynthesisLab/shepherd.