Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userControlling a Population
47
0
0.0
(
0
)
Added by
Hugo Gimbert
Publication date
2017
fields
Informatics Engineering
and research's language is
English
Authors
Nathalie Bertrand
Ask ChatGPT about the research
No Arabic abstract
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 (Controller) chooses actions, and the second player (Agents) 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 Controller control the m-population game for all $m $in$ N$ whatever Agents 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 cutoff techniques, produces winning strategies which are symbolic, that is, they do not need to count precisely how the population is spread between states. We also show that if there is no winning strategy, then there is a population size M such that Controller wins the m-population game if and only if $m $le$ M$. Surprisingly, M can be doubly exponential in the number of states of the NFA, with tight upper and lower bounds.
rate research
Read More
In this paper, we show how a dynamic population game can model the strategic interaction and migration decisions made by a large population of agents in response to epidemic prevalence. Specifically, we consider a modified susceptible-asymptomatic-infected-recovered (SAIR) epidemic model over multiple zones. Agents choose whether to activate (i.e., interact with others), how many other agents to interact with, and which zone to move to in a time-scale which is comparable with the epidemic evolution. We define and analyze the notion of equilibrium in this game, and investigate the transient behavior of the epidemic spread in a range of numerical case studies, providing insights on the effects of the agents degree of future awareness, strategic migration decisions, as well as different levels of lockdown and other interventions. One of our key findings is that the strategic behavior of agents plays an important role in the progression of the epidemic and can be exploited in order to design suitable epidemic control measures.
Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm.
Zero automata are a probabilistic extension of parity automata on infinite trees. The satisfiability of a certain probabilistic variant of mso, called tmso + zero, reduces to the emptiness problem for zero automata. We introduce a variant of zero automata called nonzero automata. We prove that for every zero automaton there is an equivalent nonzero automaton of quadratic size and the emptiness problem of nonzero automata is decidable and both in NP and in coNP. These results imply that tmso + zero has decidable satisfiability.
This volume contains the proceedings of the 12th International Symposium on Games, Automata, Logic and Formal Verification (GandALF 2021). The aim of GandALF 2021 symposium is to bring together researchers from academia and industry which are actively working in the fields of Games, Automata, Logics, and Formal Verification. The idea is to cover an ample spectrum of themes, ranging from theory to applications, and stimulate cross-fertilization.
Ramp merging is considered as one of the major causes of traffic congestion and accidents because of its chaotic nature. With the development of connected and automated vehicle (CAV) technology, cooperative ramp merging has become one of the popular solutions to this problem. In a mixed traffic situation, CAVs will not only interact with each other, but also handle complicated situations with human-driven vehicles involved. In this paper, a game theory-based ramp merging strategy has been developed for the optimal merging coordination of CAVs in the mixed traffic, which determines dynamic merging sequence and corresponding longitudinal/lateral control. This strategy improves the safety and efficiency of the merging process by ensuring a safe inter-vehicle distance among the involved vehicles and harmonizing the speed of CAVs in the traffic stream. To verify the proposed strategy, mixed traffic simulations under different penetration rates and different congestion levels have been carried out on an innovative Unity-SUMO integrated platform, which connects a game engine-based driving simulator with a traffic simulator. This platform allows the human driver to participate in the simulation, and also equip CAVs with more realistic sensing systems. In the traffic flow level simulation test, Unity takes over the sensing and control of all CAVs in the simulation, while SUMO handles the behavior of all legacy vehicles. The results show that the average speed of traffic flow can be increased up to 110%, and the fuel consumption can be reduced up to 77%, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
