Approaching the Global Nash Equilibrium of Non-convex Multi-player Games.

Many machine learning problems can be formulated as non-convex multi-player games. Due to non-convexity, it is challenging to obtain the existence condition of the global Nash equilibrium (NE) and design theoretically guaranteed algorithms. This paper studies a class of non-convex multi-player games, where players' payoff functions consist of canonical functions and quadratic operators. We leverage conjugate properties to transform the complementary problem into a variational inequality (VI) problem using a continuous pseudo-gradient mapping. We prove the existence condition of the global NE as the solution to the VI problem satisfies a duality relation. We then design an ordinary differential equation to approach the global NE with an exponential convergence rate. For practical implementation, we derive a discretized algorithm and apply it to two scenarios: multi-player games with generalized monotonicity and multi-player potential games. In the two settings, step sizes are required to be O(1/k) and O(1/√k) to yield the convergence rates of O(1/ k) and O(1/√k), respectively. Extensive experiments on robust neural network training and sensor network localization validate our theory. Our code is available at https://github.com/GuanpuChen/Global-NE.

Cooperative Safe Trajectory Planning for Quadrotor Swarms.

In this paper, we propose a novel distributed algorithm based on model predictive control and alternating direction multiplier method (DMPC-ADMM) for cooperative trajectory planning of quadrotor swarms. First, a receding horizon trajectory planning optimization problem is constructed, in which the differential flatness property is used to deal with the nonlinear dynamics of quadrotors while we design a relaxed form of the discrete-time control barrier function (DCBF) constraint to balance feasibility and safety. Then, we decompose the original trajectory planning problem by ADMM and solve it in a fully distributed manner with peer-to-peer communication, which induces the quadrotors within the communication range to reach a consensus on their future trajectories to enhance safety. In addition, an event-triggered mechanism is designed to reduce the communication overhead. The simulation results verify that the trajectories generated by our method are real-time, safe, and smooth. A comprehensive comparison with the centralized strategy and several other distributed strategies in terms of real-time, safety, and feasibility verifies that our method is more suitable for the trajectory planning of large-scale quadrotor swarms.