一句话：证明了随机参数化系统的控制问题是可判定的，并引入顺序流问题研究其复杂度。
Bertrand 等人提出了参数化系统模型：每个 agent 由有限状态系统表示，并研究控制问题——对任意数量的 agent，是否存在控制器使所有 agent 到达目标状态。该问题在对抗环境下可判定且 EXPTIME 完全，而随机环境（agent 为马尔可夫决策过程）仍是开放问题。本文证明随机控制问题可判定。方法上显著使用了良拟序、最大流最小割定理以及正则代价函数理论，并引入一个具有独立意义的中间问题——顺序流问题，研究其复杂度。
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.
@article{paperbot1264,
title = {Controlling a random population},
author = {Thomas Colcombet and Nathanaël Fijalkow and Pierre Ohlmann},
journal = {Logical Methods in Computer Science},
volume = {Volume 17, Issue 4},
year = {2021},
doi = {10.46298/lmcs-17(4:12)2021}
}