Deep Reinforcement Learning Based Dynamic Trajectory Control for UAV-assisted Mobile Edge Computing

Liang Wang; Kezhi Wang; Cunhua Pan; Wei Xu; Nauman Aslam; Arumugam Nallanathan

Source-linked AI summary

Deep Reinforcement Learning Based Dynamic Trajectory Control for UAV-assisted Mobile Edge Computing

Liang Wang, Kezhi Wang, Cunhua Pan, Wei Xu, Nauman Aslam, Arumugam Nallanathan

arXiv:1911.03887v2Nov 10, 2019eess.SPcs.LGcs.NIstat.ML

TL;DR

The paper addresses UE energy minimization in UAV-assisted MEC by jointly optimizing associations, resources, and UAV trajectories. It develops iterative CAT and DRL-based RAT with prioritized replay, finding similar CAT/RAT performance and faster post-training decisions for RAT.

Problem
UEs have limited computation and battery resources, while F-MEC must jointly manage association, UAV resources, and trajectories to reduce long-term UE energy consumption.
Method
The paper proposes iterative BCD-based CAT and DRL-based RAT, which combines actor-critic control, matching-based allocation, and prioritized experience replay.
Results
CAT and RAT achieve similar performance and both outperform traditional algorithms; RAT takes 1.2 seconds on average after training, versus over 1400 seconds for CAT.
Takeaways & Limitations
After training, RAT can rapidly adapt trajectories to arbitrary UAV takeoff points using simple calculations instead of repeatedly solving the original optimization problem.

Abstract

from arXiv · show

In this paper, we consider a platform of flying mobile edge computing (F-MEC), where unmanned aerial vehicles (UAVs) serve as equipment providing computation resource, and they enable task offloading from user equipment (UE). We aim to minimize energy consumption of all the UEs via optimizing the user association, resource allocation and the trajectory of UAVs. To this end, we first propose a Convex optimizAtion based Trajectory control algorithm (CAT), which solves the problem in an iterative way by using block coordinate descent (BCD) method. Then, to make the real-time decision while taking into account the dynamics of the environment (i.e., UAV may take off from different locations), we propose a deep Reinforcement leArning based Trajectory control algorithm (RAT). In RAT, we apply the Prioritized Experience Replay (PER) to improve the convergence of the training procedure. Different from the convex optimization based algorithm which may be susceptible to the initial points and requires iterations, RAT can be adapted to any taking off points of the UAVs and can obtain the solution more rapidly than CAT once training process has been completed. Simulation results show that the proposed CAT and RAT achieve the similar performance and both outperform traditional algorithms.

I. INTRODUCTION

The paper studies energy-efficient task execution in flying MEC by jointly controlling UAV trajectories, user association, and computation resources. It proposes CAT for iterative optimization and RAT for rapid decisions in dynamic UAV environments, with simulations showing similar performance and gains over traditional algorithms.

F-MEC uses UAVs as mobile computing platforms to provide more flexible, faster, and easier-to-deploy edge services than fixed-location MEC.
The central objective is minimizing long-term UE energy consumption through joint user association, resource allocation, and UAV trajectory control.
CAT: CAT applies block coordinate descent by alternating trajectory optimization with user-association and resource-allocation subproblems until convergence.
RAT: RAT uses actor and critic deep Q networks, a matching algorithm, UE energy consumption as reward, and prioritized experience replay for dynamic real-time control.
RAT: RAT accepts arbitrary UAV takeoff points and rapidly determines trajectories after training, avoiding repeated high-complexity optimization iterations.
Results: CAT and RAT achieve similar performance, both outperform traditional algorithms, and RAT is less sensitive to selected learning hyperparameters than reinforcement learning without PER.

A. UAV Movement

The system model represents UAV movement, wireless offloading, local execution, task deadlines, and resource limits. It accounts for bounded flight geometry, channel conditions, execution time, and UE energy consumption.

UAV Movement: Each UAV moves at a fixed altitude within a rectangle-shaped area, with per-slot distance limited by its power budget.
UAV Movement: The model constrains UAV coverage through altitude, antenna azimuth angle, and the resulting maximal horizontal coverage.
UAV Movement: UAV positions are described in Cartesian coordinates using initial coordinates, horizontal direction, and flying distance for each time slot.
Task Execution: Communication-related energy, including circuitry and signal processing, is excluded from the model.
Task Execution: UEs may execute tasks locally or offload them to UAVs, with energy models covering both local computation and offloaded execution.
Task Execution: Offloaded task completion time includes uplink transmission and UAV execution, while returned-result time is ignored.
Task Execution: The model uses a free-space channel with orthogonal frequency-division multiplexing, so users experience no mutual interference.
Task Execution: Tasks must meet a maximum completion duration, while UAV computation resources are limited per time slot.

C. Problem Formulation

The formulated energy-minimization problem jointly represents association, computation-resource allocation, and UAV trajectory variables. Because it is a mixed integer nonlinear program, the paper develops iterative CAT and DRL-based RAT solutions.

The optimization variables comprise UAV movement controls, user-association decisions, and computation-resource allocations.
P1 is a mixed integer nonlinear programming problem containing integer association variables and continuous resource and trajectory variables.
The paper addresses P1 first with iterative convex optimization CAT and then with DRL-based RAT for fast decisions in dynamic environments.

IV. PROPOSED CAT ALGORITHM

CAT reformulates the F-MEC optimization around UAV trajectories and solves it by alternating user association/resource allocation with trajectory optimization until convergence.

IV. PROPOSED CAT ALGORITHM: CAT represents each UAV trajectory as time-indexed horizontal coordinates derived from initial positions and flight actions.The trajectory variables are G_j(t) = [X_j(t), Y_j(t)].
IV. PROPOSED CAT ALGORITHM: The reformulated problem is divided into user association/resource allocation and UAV trajectory subproblems.The two blocks are optimized alternately while the other block remains fixed.
IV. PROPOSED CAT ALGORITHM: CAT iteratively optimizes association and resource allocation first, then UAV trajectories, repeating until convergence.The association/resource-allocation subproblem is solved for a given trajectory, and the trajectory subproblem is then solved for the resulting allocation.
IV. PROPOSED CAT ALGORITHM: The association and resource-allocation subproblem resembles a Multiple-Choice Multi-Dimensional 0-1 Knapsack Problem and is difficult in general.The paper addresses it using Branch and Bound through the PULP package.

B. UAV Trajectory Optimization

CAT handles UAV trajectory optimization by fixing association and resource allocation, introducing auxiliary variables, and applying successive convex approximation to the resulting non-convex problem.

B. UAV Trajectory Optimization: With association and resource allocation fixed, CAT simplifies the objective to a trajectory-only optimization problem.The formulation retains trajectory-related constraints, including UAV movement and target-area conditions.
B. UAV Trajectory Optimization: CAT introduces η_ij(t) to represent the association-weighted transmission-related quantity in the trajectory subproblem.The auxiliary variable is defined using a_ij(t), P^Tr, and D_i(t).
B. UAV Trajectory Optimization: The trajectory formulation is non-convex with respect to UAV coordinates, so CAT applies successive convex approximation at a local point G^r.This converts the relevant non-convex constraints into a tractable approximation.
B. UAV Trajectory Optimization: The approximated trajectory problem becomes a convex quadratically constrained quadratic program solvable with CVXPY.The paper identifies the resulting formulation as a convex QCQP.

C. Overall Algorithm Design

CAT repeatedly solves its allocation and trajectory blocks, but its iterative complexity and dependence on changing UAV launch points motivate the DRL-based RAT algorithm.

C. Overall Algorithm Design: Algorithm 1 alternates allocation optimization and trajectory optimization, updating the two blocks until convergence.The procedure initializes G^r, solves for A and F, updates G, and repeats.
C. Overall Algorithm Design: CAT must be rerun when the UAVs’ initial taking-off locations change.This limits direct reuse of the computed solution across different launch configurations.
C. Overall Algorithm Design: CAT has high computational complexity because each iteration includes large optimization subproblems, especially with many time slots.The paper gives a worst-case Branch and Bound term and additional SCA-related variables and constraints.
C. Overall Algorithm Design: The paper motivates RAT for emergency scenarios where fast decision making is highly demanded.RAT is introduced as the DRL-based alternative in the following section.
C. Overall Algorithm Design: A DQN estimates action values from states and actions, using target networks and experience replay to support training convergence.The Q-value is defined as the expected accumulated discounted reward.

2) DDPG:

RAT combines actor-critic deep reinforcement learning with matching-based association and resource allocation, using prioritized replay to train UAV trajectory control for continuous actions.

2) DDPG:: DDPG uses actor and critic networks to generate and evaluate continuous UAV trajectory actions.The actor produces actions from states, while the critic estimates Q-values for state-action pairs.
B. The RAT Algorithm: RAT defines the state as all UAV coordinates and the action as each UAV’s flying direction and distance.The action includes horizontal direction and distance, with the full set assembled across UAVs.
B. The RAT Algorithm: RAT uses the negative overall UE energy consumption in each time slot as its reward.A penalty is applied when a UAV flies outside the target area.
B. The RAT Algorithm: An agent generates UAV actions, then matching associates UEs with covered UAVs when offloading saves more energy than local execution.RAT uses the same resource-allocation optimization strategy as CAT.
B. The RAT Algorithm: RAT stores transitions in a replay buffer and, once full, samples experiences with prioritized replay before updating actor, critic, and target networks.The algorithm computes TD-errors and importance-sampling weights for sampled experiences.
B. The RAT Algorithm: Exploration adds normally distributed noise to actor-generated actions, with a decaying coefficient across time steps.The stated noise has mean 0 and variance 1, while ρ is set to 2 and decays.
B. The RAT Algorithm: The matching algorithm builds UAV preference lists from feasible UEs and prioritizes UEs according to energy saved by offloading.Assignments are made iteratively subject to the stated feasibility conditions.

VI. EXTENSION TO 3-D CHANNEL MODEL

The paper extends the channel model to a practical 3-D setting with blockage and shadowing, while modeling UAV motion, energy, and reinforcement-learning control variables.

Channel and UAV model: The extended 3-D channel model accounts for blockage and shadowing beyond the previous free-space model.The UAV can fly vertically, with elevation angle included in the channel description.
Channel and UAV model: Each UAV is represented by its 3-D coordinate, with motion specified through a vertical direction and flying distance.The coordinate is [X_j(t), Y_j(t), Z_j(t)], while the action uses θv_j(t) and d_j(t).
Communication model: The model defines UAV–UE distance, coverage radius, path loss, and data rate for each time slot.Path loss depends on line-of-sight and non-line-of-sight terms, elevation angle, and distance.
Energy model: UAV energy consumption includes propulsion-related power terms, and remaining energy is bounded by each UAV’s maximum energy.The propulsion model defines constants and physical parameters such as rotor speed, air density, rotor radius, UAV weight, and gravity.
RAT formulation: RAT formulates UAV control through state, action, and reward variables, penalizing UAVs that leave the target area.The state includes UAV coordinates and remaining energy; the action controls direction and flying distance.

VII. SIMULATION RESULTS

The simulations evaluate CAT and RAT in a two-UAV F-MEC setting against local, random, clustered, and DDPG-based baselines using specified task and computation workloads.

Simulation setup: The evaluation uses two UAVs serving UEs in a target area, with RAT trained from 20 different taking off points per UAV.The implementation uses fully connected actor and critic networks with hidden layers of 1024, 800, and 600 neurons.
Simulation setup: Each time slot generates tasks requiring 10–50 KB of communication and 2 × 10^9–2 × 10^10 computation cycles.UAVs activate corresponding UEs, which either offload tasks or execute them locally within the delay requirement.
Compared algorithms: CAT and RAT are compared with Local Execution, Random Moving, Cluster Moving, and DDPG.The baselines represent no offloading, random UAV motion, cluster-center trajectories, and reinforcement learning without prioritized replay.

A. Convergence Evaluation of CAT and RAT

CAT’s energy objective decreases and stabilizes across initial trajectories but converges to solutions influenced by initialization, while PER makes RAT less sensitive to training hyperparameters than DDPG.

CAT convergence: CAT’s overall UE energy consumption decreases and stabilizes after several iterations for each tested initial trajectory.The evaluation uses three pairs of circular initial trajectories with radii 80 m, 100 m, and 120 m.
CAT convergence: CAT’s convergent solution is influenced by the initial trajectory.This demonstrates sensitivity to initialization despite convergence for every tested trajectory.
RAT training: Overall, RAT is less sensitive to mini-batch and experience-replay-buffer sizes than DDPG during training.RAT applies prioritized experience replay, while DDPG uniformly samples experiences from its replay buffer.
RAT training: RAT has similar convergence performance across different mini-batch sizes and becomes more stable during learning.The comparison evaluates RAT and DDPG with an experience replay buffer size of 50000.
RAT training: When the buffer size is 10000, RAT stabilizes between 450 J and 500 J, whereas DDPG shows no convergence tendency.With buffer size 50000, DDPG worsens after the 1000-th epoch and finally reaches 550 J.

B. Trajectory Evaluation of CAT and RAT

Trajectory evaluations show RAT serving UEs from varied UAV taking off points, whereas CAT produces trajectories resembling its initial trajectories and may remain near a local optimum.

RAT trajectories: RAT is evaluated from five randomly selected pairs of UAV taking off points and guides UAVs toward service areas for different UEs.The training procedure uses 20 different taking off points, and testing outputs solutions once the taking off points are given.
RAT trajectories: RAT can immediately output solutions after taking off points are provided, using training across randomly generated starting locations.The reported behavior is attributed to convergence during training over multiple taking off points.
CAT trajectories: CAT’s trajectories are similar to the initial trajectories used in the evaluation.The CAT comparison uses the same taking off points as RAT and runs for 10 iterations.
CAT trajectories: The authors suggest CAT may fall into a local optimum, while RAT has global search ability associated with DRL exploration.This comparison links the observed trajectory patterns to the differing optimization and exploration behaviors.

C. Energy Consumption Evaluation of CAT and RAT

RAT achieves the lowest reported UE energy consumption across the evaluated comparisons, while CAT remains close in performance and requires far more execution time. In the 3-D scenario, RAT also outperforms CM and RM for UE and UAV energy consumption.

2-D energy evaluation: RAT achieves the best UE energy-consumption performance among RAT, CAT, CM, RM, and LE across different taking-off points.CAT remains around 500 J, while CM stays between 520 J and 550 J; LE performs worst because all tasks execute locally.
2-D energy evaluation: RAT outperforms the other algorithms as the number of time slots increases, while LE eventually consumes above 700 J and CAT is only slightly worse than RAT.
Execution time: RAT requires 1.2 seconds on average to obtain solutions after training, whereas CAT takes over 1400 seconds for all evaluated taking-off points.RAT uses a few algebraic calculations after training, while CAT uses 10 iterations; RAT training lasted 3000 epochs.
Effect of UAV count: UE energy consumption decreases as the number of UAVs increases because additional UAVs provide higher computational capacity and enable more task offloading.
3-D channel model: During 3-D testing, UAVs increase altitude initially because higher altitude may expand coverage and serve more UEs, despite reducing offloading data rate.
3-D channel model: In the 3-D channel model, RAT consistently outperforms CM and RM for overall UE and UAV energy consumption.For UE energy, CM performs better than RM; the same ordering is reported for UAV energy consumption.