E. Benenati
Please Note
9 records found
1
First of all, GNE problems typically admit multiple solutions, but currently available algorithms only compute an arbitrary, initialization-dependent GNE. In applications where a predictable and well-defined solution is necessary, it becomes important to select a specific GNE (among potentially infinitely many) that optimizes an arbitrary metric or a secondary, cooperative objective. We develop the first optimal GNE selection algorithms. We compare two different algorithm design methods, both developed under the framework of operator theory: the first, i.e. the hybrid steepest descent method (HSDM), entails a gradient descent of the selection function with vanishing step size combined with a GNE seeking algorithm, while the second requires the solution of a sequence of Variational Inequalities (VIs) with a vanishing regularizing term. Both design methods lead to algorithms that are suitable to distributing the computation between a central node and the agents, and we include ad-hoc algorithms for the particular cases of aggregative and cocoercive games.
Secondly, we consider time-varying games, motivated by the need for algorithms that continuously monitor and control physical multiagent systems. In such games, the agents must track an evolving solution with limited computation time between the problem's updates. This scenario is particularly relevant when the agents are affected by disturbances whose time-scale is comparable to the algorithm convergence rate. The challenge lies in finding algorithms that exhibit fast convergence and a robustness property to external disturbances, both typically associated with a linear convergence rate. We derive and study the asymptotic tracking error of a fully-distributed algorithm (i.e., without a central coordinator) for GNE problems with linear equality constraints. For a time-varying GNE selection problem, we find the HSDM with constant stepsize to be linearly convergent to an approximate solution. We find that the approximation error can be controller by an appropriate choice of the stepsize and number of iterations per time step, and we derive a bound to the asymptotic tracking error.
Finally, again driven by the need of applying GNE seeking algorithms to the control of physical systems, we consider dynamic games, where the decision each agent has to take is a time sequence of inputs to a dynamical system. In this case, the coupling between the agents emerges not only through the objectives and constraints, but also through the system dynamics. Ideally, one should compute the GNE solution by predicting the dynamics over an indefinitely long horizon. This is typically computationally intractable, especially when constraints are present. We then approximate the infinite-horizon control sequence by recomputing at each time instant the solutions to a finite-time equilibrium problem, a method typically known as receding-horizon control (or model predictive control, in the single-agent case). We derive a novel characterization of the infinite horizon objective achieved by the Nash equilibrium trajectory, and we show that one can recover the infinite-horizon performance by including this expression in the agents' objectives as an additive terminal cost. With this result, we conclude asymptotic stability of the steady state under a receding-horizon game-theoretic control action. Compared to the literature, we do not assume stability of the uncontrolled plant, nor we introduce auxiliary constraints. Furthermore, we find that the asymptotic stability of the steady state can be obtained with a more generic terminal cost if the game is potential, as we demonstrate on a practical traffic routing application. ...
First of all, GNE problems typically admit multiple solutions, but currently available algorithms only compute an arbitrary, initialization-dependent GNE. In applications where a predictable and well-defined solution is necessary, it becomes important to select a specific GNE (among potentially infinitely many) that optimizes an arbitrary metric or a secondary, cooperative objective. We develop the first optimal GNE selection algorithms. We compare two different algorithm design methods, both developed under the framework of operator theory: the first, i.e. the hybrid steepest descent method (HSDM), entails a gradient descent of the selection function with vanishing step size combined with a GNE seeking algorithm, while the second requires the solution of a sequence of Variational Inequalities (VIs) with a vanishing regularizing term. Both design methods lead to algorithms that are suitable to distributing the computation between a central node and the agents, and we include ad-hoc algorithms for the particular cases of aggregative and cocoercive games.
Secondly, we consider time-varying games, motivated by the need for algorithms that continuously monitor and control physical multiagent systems. In such games, the agents must track an evolving solution with limited computation time between the problem's updates. This scenario is particularly relevant when the agents are affected by disturbances whose time-scale is comparable to the algorithm convergence rate. The challenge lies in finding algorithms that exhibit fast convergence and a robustness property to external disturbances, both typically associated with a linear convergence rate. We derive and study the asymptotic tracking error of a fully-distributed algorithm (i.e., without a central coordinator) for GNE problems with linear equality constraints. For a time-varying GNE selection problem, we find the HSDM with constant stepsize to be linearly convergent to an approximate solution. We find that the approximation error can be controller by an appropriate choice of the stepsize and number of iterations per time step, and we derive a bound to the asymptotic tracking error.
Finally, again driven by the need of applying GNE seeking algorithms to the control of physical systems, we consider dynamic games, where the decision each agent has to take is a time sequence of inputs to a dynamical system. In this case, the coupling between the agents emerges not only through the objectives and constraints, but also through the system dynamics. Ideally, one should compute the GNE solution by predicting the dynamics over an indefinitely long horizon. This is typically computationally intractable, especially when constraints are present. We then approximate the infinite-horizon control sequence by recomputing at each time instant the solutions to a finite-time equilibrium problem, a method typically known as receding-horizon control (or model predictive control, in the single-agent case). We derive a novel characterization of the infinite horizon objective achieved by the Nash equilibrium trajectory, and we show that one can recover the infinite-horizon performance by including this expression in the agents' objectives as an additive terminal cost. With this result, we conclude asymptotic stability of the steady state under a receding-horizon game-theoretic control action. Compared to the literature, we do not assume stability of the uncontrolled plant, nor we introduce auxiliary constraints. Furthermore, we find that the asymptotic stability of the steady state can be obtained with a more generic terminal cost if the game is potential, as we demonstrate on a practical traffic routing application.
We examine the routing problem for self-interested vehicles using stochastic decision strategies. By approximating the road latency functions and a non-linear variable transformation, we frame the problem as an aggregative game. We characterize the approximation error and we derive a new monotonicity condition for a broad category of games that encompasses the problem under consideration. Next, we propose a semi-decentralized algorithm to calculate the routing as a variational generalized Nash equilibrium and demonstrate the solution's benefits with numerical simulations. In the particular case of potential games, which emerges for linear latency functions, we explore a receding-horizon formulation of the routing problem, showing asymptotic convergence to destinations and analysing closed-loop performance dependence on horizon length through numerical simulations.
To optimally select a generalized Nash equilibrium, in this paper, we consider a semi-decentralized algorithm based on a double-layer Tikhonov regularization algorithm. Technically, we extend the Tikhonov method for equilibrium selection to generalized games. Next, we couple such an algorithm with the preconditioned forward-backward splitting, which guarantees linear convergence to a solution of the inner layer problem and allows for a semi-decentralized implementation. We then establish a conceptual connection and draw a comparison between the considered algorithm and the hybrid steepest descent method, the other known distributed approach for solving the equilibrium selection problem.
We study generalized games with full row rank equality coupling constraints and we provide a strikingly simple proof of strong monotonicity of the associated KKT operator. This allows us to show linear convergence to a variational equilibrium of the resulting primal-dual pseudo-gradient dynamics. Then, we propose a fully-distributed algorithm with linear convergence guarantee for aggregative games under partial-decision information. Based on these results, we establish stability properties for online GNE seeking in games with time-varying cost functions and constraints. Finally, we illustrate our findings numerically on an economic dispatch problem for peer-to-peer energy markets.
Robotic Competitions to Design Future Transport Systems
The Case of JRC AUTOTRAC 2020
Vehicle automation and connectivity bring new opportunities for safe and sustainable mobility in urban and highway networks. Such opportunities are however not directly associated with traffic flow improvements. Research on exploitation of connected and automated vehicles (CAVs) toward a more efficient traffic currently remains at a theoretical level, and/or based on simulation models with limited reliability. Furthermore, testing CAVs in the real world is still costly and very challenging from an implementation perspective. A possible alternative is to use automated robots. By designing and testing both the low-and the high-level controllers of CAVs, it is indeed possible to reach a better understanding of the challenges that future vehicles will need to face. Robotic applications can effectively test these challenges within a wide variety of research communities—for example, via robotic competitions. Along this direction, the Joint Research Centre has organized the first European robotic traffic competition for automated miniature vehicles. Each team participated with four robots and was judged based on a set of indicators that assess the collective behaviors of the vehicles. Results show the suitability of the methodology with different teams proposing completely different approaches to deal with the challenge and thus achieving different results. Future competitions may further raise awareness about the possibility of using CAVs to improve traffic and to engage with a broader community to design systems that are really capable of achieving this goal.
A fundamental open problem in monotone game theory is the computation of a specific generalized Nash equilibrium (GNE) among all the available ones, e.g. the optimal equilibrium with respect to a system-level objective. The existing GNE seeking algorithms have in fact convergence guarantees toward an arbitrary, possibly inefficient, equilibrium. In this paper, we solve this open problem by leveraging results from fixed-point selection theory and in turn derive distributed algorithms for the computation of an optimal GNE in monotone games. We then extend the technical results to the time-varying setting and propose an algorithm that tracks the sequence of optimal equilibria up to an asymptotic error, whose bound depends on the local computational capabilities of the agents.
Monotone aggregative games may admit multiple (variational) generalized Nash equilibria, yet currently there is no algorithm able to provide an a-priori characterization of the equilibrium solution actually computed. In this paper, we formulate for the first time the problem of selecting a specific variational equilibrium that is optimal with respect to a given objective function. We then propose a semi-decentralized algorithm for optimal equilibrium selection in linearly coupled aggregative games and prove its convergence.
We study a particular class of online quadratic optimization problems, where the objective function linearly depends on some time-varying parameters. In the context of prediction-correction algorithms, that is, algorithms that combine a prediction of the future cost function and a correction on the observation of the past one, we explore the effect of a stochastic disturbance in the prediction. We then propose an algorithm that leverages the information on the prediction uncertainty and on the problem structure to approximate the optimal combination between prediction and correction.