Controlling a random population

Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is decida...

Full description

Saved in:
Bibliographic Details
Published in:Logical methods in computer science 2021-01, Vol.17, Issue 4
Main Authors: Colcombet, Thomas, Fijalkow, Nathanaël, Ohlmann, Pierre
Format: Article
Language:English
Subjects:
computer science - computer science and game theory
computer science - distributed, parallel, and cluster computing
computer science - formal languages and automata theory
computer science - logic in computer science
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Bertrand et al. introduced a model of parameterised systems, where each agent is represented by a finite state system, and studied the following control problem: for any number of agents, does there exist a controller able to bring all agents to a target state? They showed that the problem is decidable and EXPTIME-complete in the adversarial setting, and posed as an open problem the stochastic setting, where the agent is represented by a Markov decision process. In this paper, we show that the stochastic control problem is decidable. Our solution makes significant uses of well quasi orders, of the max-flow min-cut theorem, and of the theory of regular cost functions. We introduce an intermediate problem of independence interest called the sequential flow problem and study its complexity.
ISSN:1860-5974
1860-5974
DOI:10.46298/lmcs-17(4:12)2021