Reinforcement Learning in Multiple-UAV Networks: Deployment and Movement Design

Xiao Liu, Yuanwei Liu, Yue ChenIEEE Trans. Vehicular Technology 2019

Abstract

This paper presents a novel framework for Quality of Experience (QoE)-driven deployment and dynamic movement of multiple Unmanned Aerial Vehicles (UAVs). The challenge involves a non-convex three-dimensional (3D) optimization problem to maximize the sum Mean Opinion Score (MOS) of ground users, which is NP-hard. We propose a three-step approach: genetic algorithm-based K-means for cell partitioning, followed by Q-learning for both static 3D deployment and dynamic movement tracking. Numerical results demonstrate that our Q-learning approach achieves fast convergence and outperforms traditional K-means and Iterative-GAKmean (IGK) algorithms with lower complexity.

Problem Statement: The 3D Challenge of Aerial Base Stations

Deploying UAVs as aerial base stations offers a flexible solution for temporary or emergency network coverage. However, optimizing a fleet of these vehicles involves navigating complex 3D environments where traditional 2D models fail.

System model of UAV-assisted communication network showing 3D coordinates and user clustering.

The authors identify three primary hurdles:

  1. 3D Spatial Complexity: UAVs must balance altitude—higher altitudes improve Line-of-Sight (LoS) probability but increase path loss. Finding the optimal 3D coordinate is a non-convex problem.
  2. User Mobility: Ground users are dynamic. A static deployment quickly becomes obsolete as users roam.
  3. QoE vs. Throughput: Traditional metrics like raw throughput do not linearly correlate with human satisfaction. This paper focuses on the Mean Opinion Score (MOS) to better reflect the actual user experience.

Methodology: A Three-Step Reinforcement Learning Framework

To address the NP-hard nature of joint deployment and movement, the researchers developed a "divide and conquer" strategy.

The proposed three-step framework: from initial user distribution to dynamic UAV movement.

Step I: Cell Partitioning

The system first partitions ground users into clusters using a Genetic Algorithm-based K-means (GAK-means). Unlike standard K-means, which often converges to local optima, the genetic component ensures a more globally optimized initial user distribution.

Step II: Static 3D Deployment

With clusters defined, each UAV acts as an autonomous agent. Using Q-learning, UAVs learn through trial and error to find optimal 3D positions. The state space is a 3D grid, and actions include discrete movements in seven directions (up, down, left, right, forward, backward, or static).

Step III: Dynamic Movement Design

As users move according to a random walk model, the Q-learning algorithm enables UAVs to adjust their positions in real-time. This ensures the network maintains a high MOS even as user density shifts. A key advantage is the ability to train the direction-selection strategy offline, reducing real-time computational overhead.

Key Results and Insights

  • Performance and Stability: The Q-learning approach consistently outperformed standard K-means and IGK algorithms. Notably, it provides a stable solution where others might fluctuate.
  • Convergence: The algorithm demonstrates a reliable convergence rate, typically reaching an optimal state within approximately 450,000 training episodes.
  • QoE Fairness: By prioritizing MOS, the model naturally balances resources, ensuring users with poor signal quality are prioritized over those who already have sufficient service.
  • Computational Efficiency: Once the Q-table is trained offline, the real-time deployment complexity is comparable to a simple K-means operation ($O(TUN)$), making it feasible for practical use.

Conclusion and Future Directions

This reinforcement learning framework provides a robust method for managing UAV fleets in dynamic environments. Future work will look to expand the action space from discrete directions to continuous 360-degree movement and incorporate Deep Reinforcement Learning (DRL) to handle larger state spaces. Additionally, integrating energy constraints and dynamic user re-association (hand-offs) will be critical for real-world implementation.

Summary updated

Abstract

A novel framework is proposed for quality of experience (QoE)-driven deployment and dynamic movement of multiple unmanned aerial vehicles (UAVs). The problem of joint non-convex three-dimensional (3D) deployment and dynamic movement of the UAVs is formulated for maximizing the sum mean opinion score (MOS) of ground users, which is proved to be NP-hard. In the aim of solving this pertinent problem, a three-step approach is proposed for attaining 3D deployment and dynamic movement of multiple UAVs. Firstly, genetic algorithm based K-means (GAK-means) algorithm is utilized for obtaining the cell partition of the users. Secondly, Q-learning based deployment algorithm is proposed, in which each UAV acts as an agent, making their own decision for attaining 3D position by learning from trial and mistake. In contrast to conventional genetic algorithm based learning algorithms, the proposed algorithm is capable of training the direction selection strategy offline. Thirdly, Q-learning based movement algorithm is proposed in the scenario that the users are roaming. The proposed algorithm is capable of converging to an optimal state. Numerical results reveal that the proposed algorithms show a fast convergence rate after a small number of iterations. Additionally, the proposed Q-learning based deployment algorithm outperforms K-means algorithms and Iterative-GAKmean (IGK) algorithms with a low complexity.
BibTeX
@article{liu2019reinforcement,
  author = {Xiao Liu and Yuanwei Liu and Yue Chen},
  title = {{Reinforcement Learning in Multiple-UAV Networks: Deployment and Movement Design}},
  journal = {IEEE Trans. Vehicular Technology},
  year = {2019},
}
Figure