More Like this

1. Control problems with vanishing Lie Bracket arising from complete odd circulant evolutionary games

   https://doi.org/10.3934/jdg.2022002  

   Griffin, Christopher; Fan, James (January 2022, Journal of Dynamics & Games)

   We study an optimal control problem arising from a generalization of rock-paper-scissors in which the number of strategies may be selected from any positive odd number greater than 1 and in which the payoff to the winner is controlled by a control variable \begin{document}$$ \gamma $$\end{document}. Using the replicator dynamics as the equations of motion, we show that a quasi-linearization of the problem admits a special optimal control form in which explicit dynamics for the controller can be identified. We show that all optimal controls must satisfy a specific second order differential equation parameterized by the number of strategies in the game. We show that as the number of strategies increases, a limiting case admits a closed form for the open-loop optimal control. In performing our analysis we show necessary conditions on an optimal control problem that allow this analytic approach to function. 

   more » « less
2. A Neural Network Approach for Stochastic Optimal Control

   Li, Xingjian; Verma, Deepanshu; Ruthotto, Lars (June 2024, SIAM journal on scientific computing)

   We present a neural network approach for approximating the value function of high- dimensional stochastic control problems. Our training process simultaneously updates our value function estimate and identifies the part of the state space likely to be visited by optimal trajectories. Our approach leverages insights from optimal control theory and the fundamental relation between semi-linear parabolic partial differential equations and forward-backward stochastic differential equations. To focus the sampling on relevant states during neural network training, we use the stochastic Pontryagin maximum principle (PMP) to obtain the optimal controls for the current value function estimate. By design, our approach coincides with the method of characteristics for the non-viscous Hamilton-Jacobi-Bellman equation arising in deterministic control problems. Our training loss consists of a weighted sum of the objective functional of the control problem and penalty terms that enforce the HJB equations along the sampled trajectories. Importantly, training is unsupervised in that it does not require solutions of the control problem. Our numerical experiments highlight our scheme’s ability to identify the relevant parts of the state space and produce meaningful value estimates. Using a two-dimensional model problem, we demonstrate the importance of the stochastic PMP to inform the sampling and compare to a finite element approach. With a nonlinear control affine quadcopter example, we illustrate that our approach can handle complicated dynamics. For a 100-dimensional benchmark problem, we demonstrate that our approach improves accuracy and time-to-solution and, via a modification, we show the wider applicability of our scheme. 

   more » « less
3. A Neural Network Approach for High-Dimensional Optimal Control Applied to Multi-Agent Path Finding

   Onken, Derek; Nurbekyan, Levon; Li, Xingjian; Wu Fung, Samy; Osher, Stan; Ruthotto, Lars (July 2022, IEEE transactions on control systems technology)

   We propose a neural network approach that yields approximate solutions for high-dimensional optimal control problems and demonstrate its effectiveness using examples from multi-agent path finding. Our approach yields controls in a feedback form, where the policy function is given by a neural network (NN). Specifically, we fuse the Hamilton-Jacobi-Bellman (HJB) and Pontryagin Maximum Principle (PMP) approaches by parameterizing the value function with an NN. Our approach enables us to obtain approximately optimal controls in real-time without having to solve an optimization problem. Once the policy function is trained, generating a control at a given space-time location takes milliseconds; in contrast, efficient nonlinear programming methods typically perform the same task in seconds. We train the NN offline using the objective function of the control problem and penalty terms that enforce the HJB equations. Therefore, our training algorithm does not involve data generated by another algorithm. By training on a distribution of initial states, we ensure the controls' optimality on a large portion of the state-space. Our grid-free approach scales efficiently to dimensions where grids become impractical or infeasible. We apply our approach to several multi-agent collision-avoidance problems in up to 150 dimensions. Furthermore, we empirically observe that the number of parameters in our approach scales linearly with the dimension of the control problem, thereby mitigating the curse of dimensionality. 

   more » « less
4. A Neural Network Approach Applied to Multi-Agent Optimal Control

   Onken, D; Nurbekyan, L; Li, Xingjian; Wu Fung, S; Osher, S; Ruthotto, L (January 2021, European Control Conference)

   null (Ed.)

   We propose a neural network approach for solving high-dimensional optimal control problems. In particular, we focus on multi-agent control problems with obstacle and collision avoidance. These problems immediately become high-dimensional, even for moderate phase-space dimensions per agent. Our approach fuses the Pontryagin Maximum Principle and Hamilton-Jacobi-Bellman (HJB) approaches and parameterizes the value function with a neural network. Our approach yields controls in a feedback form for quick calculation and robustness to moderate disturbances to the system. We train our model using the objective function and optimality conditions of the control problem. Therefore, our training algorithm neither involves a data generation phase nor solutions from another algorithm. Our model uses empirically effective HJB penalizers for efficient training. By training on a distribution of initial states, we ensure the controls' optimality is achieved on a large portion of the state-space. Our approach is grid-free and scales efficiently to dimensions where grids become impractical or infeasible. We demonstrate our approach's effectiveness on a 150-dimensional multi-agent problem with obstacles. 

   more » « less
5. Exit Time Risk-Sensitive Control for Systems of Cooperative Agents

   https://doi.org/10.1007/s00498-019-0239-3  

   Dupuis, P. (January 2019, Mathematics of control signals and systems)

   null (Ed.)

   We study a sequence of many-agent exit time stochastic control problems, parameterized by the number of agents, with risk-sensitive cost structure. We identify a fully characterizing assumption, under which each such control problem corresponds to a risk-neutral stochastic control problem with additive cost, and sequentially to a risk-neutral stochastic control problem on the simplex that retains only the distribution of states of agents, while discarding further specific information about the state of each agent. Under some additional assumptions, we also prove that the sequence of value functions of these stochastic control problems converges to the value function of a deterministic control problem, which can be used for the design of nearly optimal controls for the original problem, when the number of agents is sufficiently large. 

   more » « less