1.

INTRODUCTION

Unmanned aerial vehicles (UAVs) have been widely emerged and employed in many areas such as military, scientific and civilian scenarios in the past decade. Because of their excellent manoeuvrability, the aerial communication system based on UAVs has been regarded as a new promising paradigm, which can promote rapid and flexible deployment^{1, 2}. Moreover, resource allocation is a crucial communication issue in UAV system. The discussion of resource allocation issue includes but is not limited to transmission power, service users and subchannels. It is important to solve these issues to improve the energy efficiency and coverage of UAV system. For these resource allocation problems, using a competitive way to deploy multiple UAVs has become an emerging research topic. Particularly, game theory is naturally a tool to model such an interactive mechanism between UAVs and enable us to study their complicated behaviors^{3, 4}. In this way, such shared resources between UAVs are frequently considered as coupled constraints in non-cooperative games.

As a reasonable solution to non-cooperative games, a generalized Nash equilibrium (GNE) refers to a strategy profile satisfying local and coupled constraints, in which no one can benefit from unilaterally changing its own strategy. Significant theoretic and algorithmic achievements of GNE seeking have been made⁵. Furthermore, a lot of research has been done to deploy multiple UAVs in a distributed manner to carry out tasks in various applications. This motivates the interest to seek GNE distributedly in UAV games, where the UAVs obtain a GNE by making decisions with local information and communicating with their neighbors through networks. Various distributed algorithms have been investigated, including asymmetric projection algorithms⁶, projected algorithms via non-smooth projected tracking dynamics⁷, and approximate projection-free algorithms⁸.

On the other hand, most references on UAV allocation are based on a fundamental assumption that all UAVs exactly share the resource allocation constraints information. Whereas, this argument is not always held in practical situations due to the underlying uncertainty. The uncertainty is usually due to many factors such as heavy communication burden² or environmental noise interferences⁹. Hence, the robustness of UAV allocation games needs to be considered.

One way to deal with uncertainties is by robust optimization, which provides a paradigm that relies on worst-case analysis. Specifically, computing the worst case means evaluating the solution by realizing the uncertainty that is most unfavourable. By employing the idea of robust optimization in games, the concept of robust game was first proposed in Reference¹⁰. This idea is not only limited to theoretical research, but also applied to other practical scenarios^{11, 12}.

The motivation of this work is to model a robust game to investigate the resource allocation issues among UAVs, and seek a GNE under the worst case via a distributed environment. The main technical contributions are listed as follows. Firstly, we employ game theory to build a robust model with polyhedral uncertain parameters for describing the competition among UAVs. Secondly, we convert the original robust game into an extended certain game by employing the idea of robust optimization. Then we investigate a novel continuous-time dynamics for seeking GNE of this certain game in a distributed way by gradient descent and projected output feedback. Finally, we illustrate several examples to present the feasibility of the distributed dynamics.

The remainder is organized as follows. Section 2 formulates a distributed robust game with parameter uncertainties in coupled constraints. Then Section 3 provides a distributed dynamics by considering a robust counterpart. Moreover, Section 4 presents numerical examples for illustration of the proposed dynamics in real UAV applications. Finally, we summary the results obtained in this paper in Section 5.

2.

PROBLEM FORMULATION

We first model a distributed robust game with resource allocation constraints to study the UAVs’ interactions in this section.

We consider an N-UAV communication system where UAVs take the optimal resources allocation. This formulates a non-cooperative game. We denote 𝒢 = (I, Ɛ) as a connected network graph, where I ≜ {1, … N} is the UAV set and ɛ is the edge set. Also, we take A = [a_ij] ∈ ℝ^n×n as the connected matrix of 𝒢. If the pair (j, i) ∈ ɛ, then we have a_ij ˃ 0, which indicates that UAV j can exchange the information with i, as shown in Figure 1.

Figure 1.

Multi-UAV communication network.

For i ∈ I, UAV i chooses a decision variable x_i from a compact and convex set C_i ⊆ ℝⁿ. We denote , x ≜ col{x₁, … x_N} ∈ C as the strategy profile for all UAVs, and x_−i ≜ col{x₁, …, x_i−1, x_i+1, …, x_N} as the strategy profile for all UAVs except i. The convex cost function for UAV i is J_i(x_i, x_−i): ℝ^nN → ℝ, which is continuously differentiable with respect to x_i, J_i(x) is Lipschitz continuous in x. Since the shared resources such as spectrum and power resources are usually limited, there exists a coupled allocation constraint in the UAV communication network. Moreover, considering the inevitable uncertainties in practice, the allocation constraint has uncertain parameters, which come from polyhedral uncertain convex sets. These uncertainties are usually caused by many factors, such as heavy transmission burden in communication channels² or noise interferences in complex environments¹⁰. We denote U ⊆ ℝ^Nn as the set for this allocation constraint. All UAVs should satisfy

where Ξ_i is a polyhedral uncertain set, defined as Ξ_i = {θ_i ∈ ℝⁿ: P_i θ_i ≤ d_i}, P_i ∈ ℝ^q_i×n, d_i ∈ ℝ^q_i. For all θ_i ∈ Ξ_i, must be satisfied. Denote 𝒳 ≜ U∩C as the feasible set of this game.

The feasible set of UAV i is

In a nutshell, given x_−i, UAV i aims to solve

For a reasonable solution of equation (1), a generalized Nash equilibrium (GNE) can be regarded an action profile x* that satisfies

in which no UAV can profit from unilaterally deviating from its own action⁵. On the other hand, each UAV may only access its local cost function J_i and action set Θ_i in the multi-UAV network, since these are private information. Also, UAV i can only know rather than . To fulfil cooperation, all UAVs exchange their local information through the network graph 𝒢. In this way, this paper studies the approach to find a GNE of equation (1) via a distributed environment.

3.

DYNAMICS DESIGN

Based on the formulated robust game, we then consider a distributed dynamics for seeking a GNE of equation (1) under the worst case, that is, the solution satisfies all possible constraints,

Due to the parameter uncertainty, we first utilize the idea in robust optimization to handle the coupled constraint¹⁰. Recalling that Ξ_i is a polyhedral uncertain set for i ∈ I. The independent optimization problem separated from equation (4) is

By introducing a dual variable , equation (2) becomes

We adopt the similar analysis for other UAVs. Whereupon, the robust game of equation (1) is transformed into a certain game with resource allocation constraints

where z_i = col{x_i, τ_i} ∈ ℝ^n+q_i, , , , .

We denote g_i(z_i,z_−i) ≜ col {∇_xiJ_i (·,x_−i), 0_qi} ∈ ℝ^n+qi as the pseudo-gradient. We decompose b_i. We define the projection operator Π_K: ℝⁿ → K on a closed and convex set K as

For designing a distributed dynamic, we introduce auxiliary variables y_i ∈ ℝⁿ, v_i ∈ ℝ, ω_i ∈ ℝ for each UAV i ∈ I. Moreover, we employ Π_Ωi(·),Π_ℝ+(·) as two projection operators on Ω_i and ℝ₊, respectively. Then we propose the following distributed dynamics for game of equation (3):

with the initial condition z_i (0) ∈ ℝⁿ, y_i (0) ∈ ℝⁿ, ω_i (0) ∈ ℝ, λ_i (0) ∈ ℝ, v_i (0) ∈ ℝ. Besides, a_ij represent the entries of the connected matrix A.

In distributed dynamics of equation (4), UAV i calculates y_i and v_i by using gradient descent. Π_Ωi(y_i) is the projection of y_i onto the local constraints Ω_i and Π_ℝ+(v_i) is the projection of v_i on the half space ℝ₊. The design idea is similar to Reference¹². The local variable λ_i(t) ∈ ℝ₊ is calculated as a Lagrangian multiplier to handle the coupled constraints, while the local auxiliary variable ω_i is calculated for the consensus of λ_i. The consensus among these λ_i guarantees that the decision variables x of all UAVs converge to the consensual GNE x*. The convergence proof can refer to References^{8, 12}.

On the other hand, the terms Π_Ωi(·) and Π_ℝ+(·) are regarded as the projected output feedback, which allows that the players’ initial variables do not need to restrict by the local constraints^13-15. Besides, dynamics of equation (4) avoid the nonsmoothness derived by the projection on tangent cones in Reference¹².

4.

NUMERICAL EXPERIMENTS

We show several experiments in this section for the accuracy of distributed dynamics of equation (4).

Considering a UAV communication system with N = 5 UAVs over a ring graph, i.e.,

These UAVs are regarded as decision-making units to adopt optimal strategy to achieve effective coverage value. For i ∈ I ≜ {1, … 5}, the action set for UAV i is C_i = {x_i ∈ ℝ²: u₁1₂ ≤ x_i ≤ u₂1₂}, with u₁ = –30 and u₂ = 30. Given x_−i, UAV i aims to address

where ρ_i = (15 − i)1₂ ∈ ℝ². All UAVs meet the allocation constraint with the parameter satisfying an octagonal set, defined as

Meanwhile, we set tolerance as t_tol = 10⁻⁴. Figure 2 provides the trajectories along dynamics (4) of each UAV’s decision variables x_i.

Figure 2.

Trajectories of all UAVs’ strategies.

Also, Figure 3 shows the Lagrangian multipliers λ_i reach consensus. Together with Figure 2, we present the correctness and feasibility of distributed dynamics of equation (4).

Figure 3.

The trajectories of λ_i’s.

Next, we show the effectiveness of dynamics of equation (4) by comparisons. The number of UAVs is increased to N = 20. Figure 4 presents the performance of dynamics of equation (4) and the algorithms in References^{8, 16}. The horizontal axis denotes the running time and the vertical axis denotes the optimal error ||x − x*|| under different algorithms. As shown in Figure 4, dynamics of equation (4) converge with a faster rate.

Figure 4.

Comparison of different algorithms.

5.

CONCLUSION

A distributed robust game model has been considered to model the interactions among multiple UAVs. These UAVs share an allocation constraint, where parameters endowed with the constraint have general uncertainties. By adopting the idea of robust optimization, the original game has been handled under the worst case, and transformed into an associated fixed game. Then a distributed dynamics has been proposed to seek GNE for the converted game by utilizing gradient descent and projected output feedback. Finally, numerical experiments have been illustrated to show the correctness and effectiveness of the dynamics.