Optimally Controlling a Random Population
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866910016995328000 |
|---|---|
| author | Gimbert, Hugo Mascle, Corto Totzke, Patrick |
| author_facet | Gimbert, Hugo Mascle, Corto Totzke, Patrick |
| contents | The population control problem is a parameterised problem where a controller sends messages to a whole population of identical finite-state agents, aiming to eventually move them all into a target state. The decision problem asks whether this can be achieved for arbitrarily large finite populations. We focus on the randomised version of this problem, where every agent is a copy of the same finite Markov Decision Process and non-determinism in the {global} action chosen by the controller is resolved independently and uniformly at random. Colcombet, Fijalkow and Ohlmann showed that this problem is decidable, but without any complexity upper bound. We show that the random population control problem is in fact EXPTIME-complete. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2411_15181 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Optimally Controlling a Random Population Gimbert, Hugo Mascle, Corto Totzke, Patrick Optimization and Control The population control problem is a parameterised problem where a controller sends messages to a whole population of identical finite-state agents, aiming to eventually move them all into a target state. The decision problem asks whether this can be achieved for arbitrarily large finite populations. We focus on the randomised version of this problem, where every agent is a copy of the same finite Markov Decision Process and non-determinism in the {global} action chosen by the controller is resolved independently and uniformly at random. Colcombet, Fijalkow and Ohlmann showed that this problem is decidable, but without any complexity upper bound. We show that the random population control problem is in fact EXPTIME-complete. |
| title | Optimally Controlling a Random Population |
| topic | Optimization and Control |
| url | https://arxiv.org/abs/2411.15181 |