We introduce a new setting where a population of agents, each modelled by a finite-state system, are controlled uniformly: the controller applies the same action to every agent. The framework is largely inspired by the control of a biological system, namely a population of yeasts, where the controller may only change the environment common to all cells. We study a synchronisation problem for such populations: no matter how individual agents react to the actions of the controller, the controller aims at driving all agents synchronously to a target state. The agents are naturally represented by a non-deterministic finite state automaton (NFA), the same for every agent, and the whole system is encoded as a 2-player game. The first player chooses actions, and the second player resolves non-determinism for each agent. The game with m agents is called the m-population game. This gives rise to a parameterized control problem (where control refers to 2 player games), namely the population control problem: can playerone control the m-population game for all m in N whatever playertwo does? In this paper, we prove that the population control problem is decidable, and it is a EXPTIME-complete problem. As far as we know, this is one of the first results on parameterized control. Our algorithm, not based on cut-off techniques, produces winning strategies which are symbolic, that i they do not need to count precisely how the population is spread between states. We also show that if the is no winning strategy, then there is a population size cutoff such that playerone wins the m-population game if and only if m< cutoff. Surprisingly, cutoff can be doubly exponential in the number of states of the NFA, with tight upper and lower bounds.


    Access

    Download


    Export, share and cite



    Title :

    Controlling a Population


    Contributors:

    Publication date :

    2017-01-01



    Type of media :

    Conference paper


    Type of material :

    Electronic Resource


    Language :

    English



    Classification :

    DDC:    004 / 629





    HEIGHT CONTROLLING TOOL, HEIGHT CONTROLLING DEVICE AND HEIGHT CONTROLLING METHOD

    MATSUMURA SHIGEKI | European Patent Office | 2019

    Free access

    Lean Controlling und Reengineering Controlling

    Klingebiel, Norbert | IuD Bahn | 1996


    VEHICLE CONTROLLING SYSTEM AND CONTROLLING METHOD

    LEE HYUNG MYUNG | European Patent Office | 2022

    Free access

    Controlling device and drone controlling method

    CHEN KUAN-HUNG / LI CHIA-YIN / WANG CHI-TUNG et al. | European Patent Office | 2022

    Free access