Keeping in Touch with Collaborative UAVs: A Deep Reinforcement Learning Approach

1 Introduction

Small unmanned aerial vehicles (UAVs) have an edge in ubiquitous-deployment, autonomous-mobility and flexiblemaneuverability, which can serve our daily life in an intelligent and convenient manner. Moreover, the unwearied UAVs can also replace human labors to fulfill challenging tasks in remote, unsafe and stricken environments. The increasing popularization of UAVs has boosted numerous applications such as goods delivery, environment surveillance, disaster relief assistance and terrorist defence. However, the capabilities of coverage, sensing and execution as well as the budgets of payload and energy of one single UAV are very limited. Thus, it is advocated for multiple UAVs to fulfill a complex task collaboratively [Wang et al., 2017].

The multi-UAV collaboration involves the necessary steps of connectivity maintenance and information sharing among distributed teammates in an uncertain or even unknown environment [Barrett et al., 2017]. Due to the restriction of local perceptions and the lack of a priori knowledge about the potential teammates, it is difficult to learn about the existence of the counterparts in the free flight space. The varying space locations and the intermittent link connectivity also hinder UAVs to share the reactions to the environment changes. A feasible solution to get connected with teammates is to broadcast announcement messages over qualified channels and set up links by trial and error. However, dispersed UAVs share unpredictable common channels and the channel availability in the air fluctuates frequently over time, which further challenges the multi-UAV collaboration issue.

As reinforcement learning (RL) [Sutton and Barto, 1998] emerges as a viable and elegant approach to yield an optimized policy for sequential decision-making tasks, the uncertain and time-varying channel availability and the resultant connectivity decision is suitable to be tackled by RL. RLbased agents (i.e., UAVs 1 ) gain experiences by exploration, and gradually converge to the optimal policy after repetitive interactions with the environment. However, the standard RL approach suffers from a high computational complexity due to the large-scale state-action spaces. To adapt to the environment variations quickly, the non-linear and parameterized Deep Neural Network (DNN) has become a dominant learning technique. The DNNs have several incomparable benefits such as compact and powerful encoding of the gained experiences, efficient training of the high-dimensional data samples, fine-grained approximation of the multi-scale objective functions, etc. [Sharma et al., 2017]. Thus, we investigate the UAVs' optimal link discovery and selection problem under the deep reinforcement learning (DRL) framework.

Multi-agent DRL has the potential to execute the joint task remarkably, but also brings about particular challenges. It naturally incurs high-dimensional and large-scale state-action spaces to decide on connected links over multiple candidate channels in a continuous period of time, making the optimal policy convergence intractable and inefficient. Besides, each agent makes independent policies based on local perceptions and neglects the time-varying surroundings, making the learning process isolated and nonstationary [Ye et al., 2017].

In this paper, we present an efficient multi-agent DRL algorithm to decide the optimal communication link for UAVs' continuous connectivity in uncertain environments. To improve the computational efficiency, we slice the holistic highdimensional action spaces into a number of tractable fractions. The "divide-and-conquer" strategy scales well to the massively increasing data over time. Moreover, to facilitate collaborations among autonomous UAVs, we investigate the multi-agent mutual sampling and joint learning method. The cross-network interactions are beneficial to stabilize and expedite the optimal policies learning. We evaluate the proposed Fractional Slicing & Mutual Sampling (FSMS) DRL algorithm on the UAVs' continuous network connectivity task. Results reveal that our algorithm enables UAVs to quickly discover potential links towards teammates.

1 Hereafter we use the terms UAV and agent interchangeably.

2 RelatedWork

We review the literature on single-agent and multi-agent DRL algorithms.

2.1 Single-Agent Deep Reinforcement Learning

Deep Q-network (DQN) [Mnih et al., 2015] is a representative work that iteratively approximates the state-action value (i.e., Q-value) function with a parameterized DNN. The core ingredients of experience replay and target network can improve the computational efficiency. However, the deficiency is that DQN overestimates the action values in practice. To this end, [Hasselt et al., 2016] propose a Double Q-learning algorithm to achieve the objectives of large-scale function approximation and stable learning. [Zhang et al., 2017] further propose a weighted double Q-learning algorithm to improve the underestimation of action values by heuristically selecting the weights from empirical results. [Anschel et al., 2017] extend the DQN algorithm by averaging over the afore learned Q-values, which can reduce the target approximation errors and stabilize the training process. [Wang et al., 2016] introduce a dueling network architecture that decouples the state value function and the action advantage function in DQN, which can figure out the appropriate action quickly during policy evaluation when similar actions are mixed. [Kulkarni et al., 2016] propose a hierarchical DRL framework, in which the top-level picks a policy over intrinsic goals and the bottom-level learns a policy over atomic actions to fulfill the chosen goals. However, the afore mentioned works concern on the discrete learning process with a limited number of action spaces. Accordingly, [Gu et al., 2016] present a normalized advantage function to simplify the sampling complexity and accelerate the model-free continuous Q-learning. [Mnih et al., 2016] execute agents asynchronously on continuous tasks and the shared model among the parallel actor-learners leads to a stabilized learning process. [Xu et al., 2018] propose a traffic-aware method to train an inexperienced DRL agent to gain exploration and make a rational policy in the continuous learning scenario with massive action spaces.

2.2 Multi-Agent Deep Reinforcement Learning

The general DRL algorithms deal with a certain number of agents in a coexisting environment, which should learn to maximize each individual's benefit while minimizing the influences on others. [Tampuu et al., 2017] investigate how multiple agents learn and make different policies under both collaborative and competitive tasks. [Foerster et al., 2016] tackle the multi-agent communication issue with partial observability in the decentralized execution but centralized learning setting. [He et al., 2016] model the implicit representation of the opponent's strategy according to past observations and then derive an adaptive response that better optimizes available rewards. [Chen et al., 2017] address the multi-agent cooperative collision avoidance problem by characterizing the stochastic behaviors as the compliance/violation of social norms. [Leibo et al., 2017] propose a sequential social dilemma (SSD) model to capture the structure of cooperation and defection when independent agents learn dynamic policies by using Markov games. [Omidshafiei et al., 2017] introduce a decentralized and stable experience replay method, which is combined with a generalized recurrent multi-task network to achieve multi-agent coordination.

Due to the powerful learning and decision capability, the DRL technique has been widely applied to the community of autonomous vehicle networks. For examples, [Liu et al., 2017] avoid the traffic jam problem by utilizing cooperative Q-values to balance the traffic flows among adjacent intersections. [Chinchali et al., 2018] tackle the traffic scheduling problem in IoTs in order to adapt to traffic variations dynamically and increase the network utilization significantly. [Wu et al., 2017] implement a DRL-based UAV sensing system, which can increase the airborne broadcast dissemination rate and reduce the data loss rate adaptively. [Xiao et al., 2018] accelerate the game between the UAV transmission and the smart attacks by removing the high dimension bottleneck of state spaces. [Zhang et al., 2018] control energy-limited UAVs to sample the most required data in the target zone, and also to schedule the ground unmanned charging vehicles to the UAV refueling point with the shortest time.

Although the essential DRL algorithms have various extensions and widespread applications, there have been relatively few investigations on efficient DRL solutions for continuous and stationary multi-agent collaborations, particularly for the durative UAV communications in uncertain environments. Thus, we aim at designing an effective DRL algorithm to address the UAVs' continuous network connectivity problem.

3 Background

In this section, we introduce the relevant background on RL and particularly on the deep Q-learning algorithm.

3.1 Reinforcement Learning

RL focuses on how the agents take proper actions in a specific or unknown environment so as to maximize (resp. minimize) the cumulative objective function of the long-term reward (resp. cost). Agents need to interact with the environment through direct experience by a sequential learning and decision-making process. At each time step t (t = 0, 1, . . .), one agent observes one possible environment state s(t) ∈ S and takes a potential optimal action a(t) ∈ A, which leads to an immediate optimized reward r(t) ∈ R. The environment state is transited to the next step s′ = s(t+1) ∈ S by following a probability p(s′ |s(t) , a(t) ). We consider the infinite horizon with a discounted cumulative reward R(t) = +∞ ∑ t′=t γ t′-t r(t′ ) , where γ ∈ (0, 1) denotes the discounted factor. Given the state set S and the action set A, a policy corresponds to a function π that guides the agent towards reward maximization. Particularly, each agent aims to figure out the optimal policy π∗ : S → A that harvests the maximized E[R(t) ], where E[·] denotes the expectation operation.

We are interested in the value-based RL methods that encode policies by applying the action-value function (i.e., Qfunction), which is given as

Accordingly, the optimal Q-function is Q∗ (s, a) = maxπ Qπ (s, a) and the optimal policy can be derived as π∗ = arg maxa Q∗ (s, a).

The above Q-function associated with the optimal policy π∗ can be solved by the following value-iteration-based Qlearning algorithm [Sutton and Barto, 1998]:

where η denotes the learning rate.

However, the number of training samples required for convergence in the above Q-learning algorithm grows immeasurably with the number of states. Thus, the standard Q-learning suffers from the curse of dimensionality as well as the low computational efficiency. As a countermeasure, the function approximation technique makes sense, which is explained in the next subsection.

3.2 Deep Q-Networks

The approximate non-linear Q-function is denoted as a neural network parameterized with θ (i.e., Q(s, a) ≈ Q(s, a; θ)), which is also referred to as a Q-network. The transitions of states, actions and rewards yielded from each step are explored and stored in memory D so that agents can replay these experiences later in diverse sorts to break the temporal correlation caused by the traditional sequential training. At the i-th training step, the data samples are randomly selected from D and are packed into a batch. The training objective at the i-th step is to update θ(i) , which minimizes the expected mean-square error (i.e., the loss function) of the samples within the batch operating the Bellman equation (2). The loss function is given as

where the parameter ¯ θ(i) depends on the previous update and is utilized to approximate the optimal target value.

The updates are made at each training step by using the following gradients:

During the process of minimizing the loss function, the cost of back-propagating over all the training samples is undesirable. As a result, the stochastic gradient descent (SGD) method, which only samples a subset of the candidate batch, is utilized for an improved computational efficiency.

4 DRL-based Optimal Link Selection

The link selection problem concerns how to decide the best link to get connected to another UAV. In this section, we present the DRL-based algorithm for optimal links decision.

4.1 Model Framework

We consider a multi-UAV coexisting environment, in which a set U of autonomous UAVs fulfill a collaborative task. From the perspective of DRL, each UAV u ∈ U is modeled as an agent, which has the capability of perceiving the local available channels and attempts to select a connected link over a common channel shared by another agent v ∈ U continuously. Due to the variations in space locations, channel quality, perception capabilities, etc., different agents tend to observe different local available channels. For any u ∈ U, let Cu denote the set of its local channels. To ensure the connectivity, we assume the time-varying local channels between any pair of agents overlap (i.e., ∀u, v ∈ U, Cu ∩ Cv ̸= ∅). If adjacent agents propagate announcement messages on the same channel simultaneously, a connected link can be built. Armed with no knowledge of the flight environment and no awareness of potential teammates, each agent explores to discover links and accumulates experiences by iteratively interacting with the surroundings. We define the necessary elements in the DRL framework as follows.

• States. At each time instant, an agent u propagating an announcement message corresponds to a state su ∈ S, which is defined as whether the message is delivered successfully or not. Let S = {succ, fail} denote the state set. If su = {fail}, agent u obviously needs to discover another available link at the next time instant. Whereas if su = {succ}, agent u still needs to check whether the previous link is continuously connected or not at the next time instant.
• Actions. Actions indicate the decisions on which channel to propagate the messages. Let Tu denote the set of teammates that agent u may reach. For any u ∈ U, su ∈ S, the set of potential actions is denoted as

where au = (v, chu) denotes the action of propagating a message to teammate v over channel chu, and we use Au instead of ACu u (su) for brevity.

• Rewards. As the channel availability fluctuates frequently in the air, we let p(t) u (chu) denote the probability that channel chu is available for agent u at time t. The decision-making depends on the channel quality, thus, the reward ru received by agent u is calculated as the number of messages that are propagated successfully over the most qualified common channel.

To make optimal link decisions, every time a message m is ready to be propagated, agent u ∈ U execute the DRLbased algorithm to learn the Q-function. According to the calculated action-value, agent u decides the best propagating action au = (v, chu) for m (i.e., over the best channel chu to reach teammate v).

4.2 Learning to Get Connected

The essentials of the proposed FSMS algorithm are two-fold: fractional slicing and mutual sampling.

(i) Fractional slicing. The UAVs' optimal links discovery and selection in uncertain and time-varying environments directly lead to high-dimensional and continuous action spaces. To balance the trade-off between representability and tractability, we slice the whole action spaces into a number of non-overlapped fractions while reserving a common coordinator, which deals with the functions of division and aggregation for all the fractions.

For agent u and its complex action set Au with F dimensions, let Au,f (f ∈ {1, . . . , F}) denote the f-th dimension of Au. Each fraction Au,f includes a finite number of subactions au,f . The agent u trains all the fractions independently and their respective Q-values (i.e., Qu,f (su, au,f )) are aggregated by the coordinator. As the initial division is estimated roughly and the output weights are usually biased, the training process is confronted with the instability barrier. We thus compute the F-fold average Q-value as the result, i.e., Qu(su, au; θu) = 1F ∑Ff=1 Qu,f (su, au,f ; θu). In accordance with the Q-value updates, the DQN target value is defined with an average operation: yu = ru + γ · 1F ∑f ¯Qu,f(s′u , argmax a′u,f ∈Au,f Qu,f (s′u , a′u,f ; θu)) ( ¯Qu,f

denotes the f-th fraction of the target DQN ¯Qu). Analogously, the loss function is the expectation value of the averaged yu across all fractions: Lu(θu) = (yu,f - Qu,f (su, au,f ; θu))2 ].

• (ii) Mutual sampling. From the perspective of one agent, the environment is nonstationary in the sense that the agents only own local perceptions and learn the separate polices all by themselves. This phenomenon shields off the macroperspective and slows down the convergence efficiency. To this end, we focus on the multi-agent mutual sampling and joint learning, i.e., each agent not only samples the correlative state-action information by itself but also from other peers.

In particular, we add a mutual learning parameter θmutual u , which is distinguished from the original independent learning parameter θown u , for each agent u ∈ U in the DQN. As a result, the training data is not only passed to all action fractions of one agent, but also passed to the associated cross-network fractions from other agents. Let Qu (su, au; θown u , θmutual u )

ᰐӪᵪ Ⲵ 䰤オࣘ⍫ ॿ䈳ಘ ⡷࠷ࣘ⍫ ��� ⤜・ᆖҐ denote the deep Q-function of agent u. Correspondingly, the gradient training on θown u and θmutual u is conducted on the joint loss function Lu(θown u , θmutual u ).

ㆆߣᴰՈ ⡷࠷ࣘ⍫ ᰐӪᵪ Ⲵ 䍴Ⓚ⊐ ᰐӪᵪ Ⲵ 䍴Ⓚ⊐࢟ᵜ ᰐӪᵪ Ⲵ 䰤オࣘ⍫ ॿ䈳ಘ ⡷࠷ࣘ⍫ ⡷࠷ࣘ⍫ ��� ᰐӪᵪ Ⲵ 䍴Ⓚ⊐ ᰐӪᵪ Ⲵ 䍴Ⓚ⊐࢟ᵜ ⤜・ᆖҐ Ӕӂ䍴Ⓚ⊐ 㚄ਸᆖҐ Then a problem arises, that one agent's own training data and the multi-agent mutual training data are mixed, making the passing of target information confusing. We thus utilize the duplication separation technique. In other words, each agent has a duplicate, which shares the same parameters as the original agent. These two parts can communicate with each other without any difficulty and are trained by performing the same algorithm. However, the underlying experience replay pools of these two parts are different, i.e., one part stores agent u's own experience Du while the other part stores the interacting agent v's mutual experience Dv→u(v ∈ T (u)). An improved convergence speed can be expected under the separation technique. For example, the cross-network training is only conducted on the reduced data set from Du∩v instead of the redundant data set fromDu or Dv.

In Fig.1, we take the case of two agents to illustrate the FSMS algorithm architecture.

We formally present the FSMS algorithm in Algorithm 1, which takes the current state as well as the local available channels as inputs. When agent u needs to get connected to another teammate, agent u updates the state-action model and calculates the new Q-function (lines 3∼5), where the Q-value is averaged across all fractions in its own action spaces and all associated cross-network fractions from the interacting agent v. To balance between exploration (gain of knowledge) and exploitation (usage of knowledge), we utilize the ϵ-greedy (ϵ ∈ (0, 1]) strategy (lines 6∼12). Specifically, agent u explores a random action with probability ϵ or exploits existing knowledge to select the optimal channel to propagate messages. According to the update results, agent u selects a proper action. After executing the current action a(t) u and yielding the corresponding reward r(t) u , we keep track of agent u's state transition information in both its own memory Du and the mutual memory Dv→u with teammate v (lines 14∼15). The parameters θown u and θmutual u are learnt jointly through stochastic gradient descent (i.e., only a subset of transitions is sampled for a reduced complexity as shown in line 16). Combining the techniques of fractional slicing and mutual sampling, the loss function is trained across all independent fractions within agent u's own DQN as well as the mutual DQN with the interacting teammate v (i.e., lines 17∼22). In consideration of the duplication separation technique that separates the pools of Du and Dv→u, the duplicate needs to be trained in a similar way (i.e., lines 23∼26).

Algorithm 1: FSMS algorithm

1 Initialize the experience memory Du and Dv→u; 2 Initialize the parameters of θown u and θmutual u randomly; 3 for ∀su ∈ S do 4 for ∀au ∈ ACu u (su) do 5 Qu(su, au) = 1F ∑Ff=1 Qu,f (su, au,f ; θown u , θmutual u ); 6 ρ = random number(0, 1); 7 if ρ < ϵ then 8 chu = a randomly selected channel in Cu; 9 (v, chu) = arg max au∈A{chu} u (su) Qu(su, au; θown u , θmutual u ); 10 else 11 Calculate Qu(su, au) for all actions au ∈ ACu u (su); 12 (v, chu) = arg max au∈ACu u (su) Qu(su, au; θown u , θmutual u ); 13 a(t) u = (v, chu); 14 Execute action a(t) u while yielding reward r(t) u and the next state s(t+1) u ; 15 Keep the transition (s(t) u , a(t) u , r(t) u , s(t+1) u ) in memory Du and Dv→u for all v ∈ T (u); 16 Sample a subset of transitions (su, au, ru, s′u) from Du randomly; 17 if s′u is the terminal state then 18 yu = ru; 19 else 20 yu = ru +γ · 1F ∑f ¯Qu,f (s′u, arg max a′u,f ∈Au,f Qu,f (s′u, a′u,f ; θown u , θmutual u )); 21 Perform the gradient descent training on the loss function of Lu(θu) = E[ 1F ∑f (yu,f - Qu,f (su, au,f ; θown u , θmutual u ))2 ]; 22 Share θmutual u to all agents v ∈ T (u); 23 for v ̸= u do 24 Sample a subset of transitions fromDv→u; 25 Update θown u , θmutual u as the above iterations; 26 Assign θmutual u to agent v;

Compared with the algorithm with the holistic action spaces, the FSMS algorithm's computational complexity is reduced fromO(|Tu| · |Cu|2 ) to O(|Tu| · ∑Ff=1 |Cu,f |2 ), where

|Tu| denotes the number of u's neighbors and |Cu,f | denotes the number of u's local channels in its f-th fraction.

5 Experiments

In this section, we conduct experiments to evaluate the FSMS algorithm. We select the DRON [He et al., 2016] and the DIAL [Foerster et al., 2016] algorithms as the benchmarks and apply them to the UAVs' optimal link discovery and selection problem. According to the number of UAVs participated in the connection task, we divide the experiments into two sets: five UAVs and ten UAVs. We utilize the performance metrics of average connection time among all the collaborative UAVs and average reward (number of messages that are delivered successfully) yielded by each iteration to evaluate the compared algorithms. Each result is obtained by averaging over 1,000 independent runs of the algorithms.

In terms of the metric of average connection time, as the number of common channels shared by the coexisting UAVs is a significant influence factor, we thus observe its variation trend under a fixed total number of channels and a varying number of shared channels. We assume there are totally 30 channels that are potentially available for all the UAVs. The local available channels perceived by the dispersed UAVs overlap but are different. We obtain the average connection time by varying the number of shared channels from 5 to 15. As for the metric of average reward, we compare the accumulative number of messages that are propagated among the connected UAVs at each iteration of the learning process.

Fig.2(a) shows the comparisons on average connection time with five UAVs. It can be seen that all algorithms need shorter time to get connected as the number of shared channels increases due to the fact that more shared channels indicate more connected opportunities. The DRON algorithm takes the longest average connection time, followed by the DIAL algorithm. Our FSMS algorithm takes the shortest connection time under all cases. The DRON model learns a reactive policy in a stochastic environment from the view point of one single agent and the policy space of other agents is unknown. Hence, DRON suffers from high complexity and nonstationary learning. The DIAL algorithm combines the centralized learning with the DQN, which indicates that the learning gradients can be passed from agent to agent. The end-to-end training across agents in DIAL is similar with our mutual sampling method. However, DIAL relies on the centralized learning, and the lack of duplication separation makes the interactive training confusing. As an improvement, FSMS utilizes fine-grained fractional slicing to achieve high-rate learning. Moreover, duplication separation is applied to the mutual sampling method, which can distinguish the mixed training information and expedite the convergence process. Fig.2(b) compares the average reward during 500 times of iterations. It can be seen that the FSMS algorithm yields the most rewards, followed by the DIAL and the DRON algorithms. The reason is that the better connected link is the foundation of successfully propagating more messages.

Fig.3(a) displays the comparisons on average connection time with ten collaborative UAVs. The downward trends of the three algorithms are similar with those of Fig.2(a). The difference is that all algorithms take longer time to get connected as the number of UAVs increases. Moreover, the superiority of the FSMS algorithm becomes more apparent. Fig.3(b) compares the average reward with ten UAVs. The reward results of all the three algorithms are relatively larger than those of Fig.2(b). The reason is that more interacting UAVs can facilitate the mutual learning about the connected links, leading to a more continuous propagation of messages.

From the evaluation results, we know that the key techniques of fractional slicing and mutual sampling in the FSMS algorithm are feasible and efficient in making optimal decisions on the UAVs' continuous link selection issue.

6 Conclusion

In this paper, we study the UAVs' optimal link discovery and selection problem, in which UAVs must select the most qualified link towards peers to support rapid information sharing and efficient teamwork. The usage of RL methods here is challenging since the action spaces are high-dimensional and continuous, and the UAVs should overcome the constraints of local perceptions and nonstationary learning. We propose a novel DRL algorithm to address these issues. The fractional slicing technique can train the sub-actions in a fine-grained manner and reduce the computational complexity. The mutual sampling technique can extend the perception range and expedite the policy-convergence process. Experiment results also verify the feasibility and efficiency of the proposed algorithm on the UAVs' continuous network connection task.

Acknowledgments

This work was supported by National Natural Science Foundation of China under Grants 61732017, 61472404, 61472402, 61501125 and 61502457, and China Postdoctoral Science Foundation under Grant 2018M631582. Min Liu is the contact author.