# Multi-Agent Reinforcement Learning for Offloading Cellular Communications
with Cooperating UAVs

Abhishek Mondal, Deepak Mishra, _Senior Member, IEEE_ , Ganesh Prasad,
_Member, IEEE_ ,
George C. Alexandropoulos, _Senior Member, IEEE_ , Azzam Al-nahari, and Riku
Jäntti, _Senior Member, IEEE_ Abhishek Mondal is with the Department of
Electronics and Communication Engineering, National Institute of Technology
Calicut, 673601 Kerala, India (e-mail: abhishekmondal@nitc.ac.in). Deepak
Mishra is with the School of Electrical Engineering and Telecommunications,
University of New South Wales, 2052 Sydney, Australia (e-mail:
d.mishra@unsw.edu.au). Ganesh Prasad is with the Department of Electronics and
Communication Engineering, National Institute of Technology Silchar, 788010
Assam, India (e-mail: gpkeshri@ece.nits.ac.in). George C. Alexandropoulos is
with the Department of Informatics and Telecommunications, National and
Kapodistrian University of Athens, 15784 Athens, Greece (e-mail:
alexandg@di.uoa.gr). Al-nahari is with the Department of Information and
Communications Engineering, Aalto University, 02150 Espoo, Finland, and also
with the Department of Electrical Engineering, Ibb University, Ibb 70270,
Yemen (e-mail: azzamyn@gmail.com). Riku Jäntti is with the Department of
Information and Communications Engineering, Aalto University, 02150 Espoo,
Finland, (e-mail: riku.jantti@aalto.fi). Part of this paper has been presented
at the IEEE ICC Workshops 2023, Rome, Italy, June 2023 [1].

###### Abstract

Effective solutions for intelligent data collection in terrestrial cellular
networks are crucial, especially in the context of Internet of Things (IoT)
applications. The limited spectrum and coverage area of terrestrial base
stations (BSs) pose challenges in meeting the escalating data rate demands of
network users. Unmanned aerial vehicles (UAVs), known for their high agility,
mobility, and flexibility, present an alternative means to offload data
traffic from terrestrial BSs, serving as additional access points. This paper
introduces a novel approach to efficiently maximize the utilization of
multiple UAVs for data traffic offloading from terrestrial BSs. Specifically,
the focus is on maximizing user association with UAVs by jointly optimizing
UAV trajectories and users’ association indicators under quality-of-service
(QoS) constraints. Since, the formulated UAVs control problem is non-convex
and combinatorial, this study leverages the multi-agent reinforcement learning
(MARL) framework. In this framework, each UAV acts as an independent agent,
aiming to maintain inter-UAV cooperative behavior. The proposed approach
utilizes the finite-state Markov decision process (MDP) to account for UAVs’
velocity constraints and the relationship between their trajectories and state
space. A low-complexity distributed state-action-reward-state-action (SARSA)
algorithm is presented to determine UAVs’ optimal sequential decision-making
policies over training episodes. The extensive simulation results validate the
proposed analysis and offer valuable insights into the optimal UAV
trajectories. The derived trajectories demonstrate superior average UAV
association performance compared to benchmark techniques such as Q-learning
and particle swarm optimization.

###### Index Terms:

Unmanned aerial vehicle, reinforcement learning, data offloading, trajectory
optimization, user association.

##  I Introduction

###  I-A Background

The rapid and continuous advancement in sophisticated mobile communication
technology is driving the integration of intelligent transportation into the
Internet of Things (IoT) domain. This integration introduces a variety of
emerging applications for vehicular networks, such as prompt safety
assessment, early warning systems for obstacles, and efficient task dispatch
[2, 3]. By embedding computing capabilities into intelligent vehicles within
IoT networks for the collection and analysis of data, the concept of a smart
city emerges, offering a diverse range of services and simultaneously
improving the quality of experience (QoE) for residents’ comfort [4, 5].
However, these applications often face challenges, given that current cellular
networks grapple with issues related to data perception, transmission,
storage, and analysis. These challenges arise primarily from the substantial
expansion of intelligent IoT devices and the vast amount of data they generate
[6]. In such scenarios, cellular offloading becomes crucial to enhance network
connectivity.

At present, addressing the offloading of computational tasks from cellular
hotspots involves the development of WiFi infrastructure or small-scale
cellular networks [7]. However, these solutions typically rely on the
deployment of cost-inefficient fixed base stations (BSs), which struggle to
meet the highly dynamic and diverse traffic demands associated with temporary
high user density. In specific scenarios, such as when a group of mobile users
gathers in a designated location for temporary events like festivals,
concerts, and stadium games, certain users may encounter unsatisfactory
quality of service (QoS) from the cellular network due to limited spectrum
capacity, resulting in connectivity issues. In contrast, cellular offloading
through unmanned aerial vehicles (UAVs) proves effective in overcoming
practical cellular hotspot challenges by efficiently balancing data traffic
and providing seamless wireless coverage for ubiquitous connectivity [8]. The
promising advantages of integrating UAVs into cellular networks include cost-
effectiveness in deployment and operation, with significantly lower costs
compared to establishing or maintaining typical cellular infrastructure.

UAVs play a crucial role in alleviating network congestion and reducing
latency by offloading data or computational tasks, particularly in densely
populated areas or during periods of peak usage. However, developing a
flexible and efficient UAV-assisted intelligent vehicular network faces
challenges due to the limited computing and offloading capacity of individual
UAVs. Consequently, there is a need for multi-UAV-enabled systems that
maintain inter-UAV coordination through a centralized server, establishing an
ad hoc network of multiple UAVs [9]. Notably, UAVs connected to cellular
networks significantly enhance coverage and throughput in terrestrial
communications by associating with users located at a distance [10]. Cellular-
connected UAVs have the potential to reduce data traffic load on terrestrial
BSs and meet QoS requirements for network users. However, several practical
challenges in UAV implementation need addressing, including identifying
suitable deployment locations, effectively allocating resources, and
optimizing trajectories within constrained flying durations. The ultimate goal
is to maximize their utilization, quantified by serving the highest number of
users through UAVs [11]. Therefore, UAV-aided cellular communication emerges
as a compelling research paradigm, focusing on load balancing from terrestrial
BSs.

###  I-B State of the Art

Until now, Unmanned Aerial Vehicles (UAVs) have been integrated into vehicular
networks [12, 13, 14, 15, 16] with objectives ranging from maximizing coverage
area [12], optimizing system throughput [13], enhancing energy efficiency (EE)
[14], minimizing transmission delay [15], and managing UAVs’ energy
consumption [16]. These UAV-enabled vehicular networks [14, 15] operate under
the supervision of software-defined frameworks, employing a centralized
controller to schedule concurrent actions of multiple UAVs and improve the
performance of existing cellular infrastructures. Consequently, research
efforts [17, 18, 19, 20, 21] concentrate on maximizing the utilization of
multiple UAVs within their operational energy constraints by determining
optimal trajectories and resource allocation. However, these investigations
rely on non-convex optimization techniques, necessitating multiple steps of
relaxation and approximation in the optimization variables. Moreover, non-
convex optimization techniques require re-execution whenever system
parameters, such as channel gains, undergo unpredictable updates, and they
entail high computational complexity when jointly optimizing the control of
multiple UAVs. In dynamic network environments, approximating and pre-
configuring UAVs’ flight paths is highly challenging, prompting the adoption
of meta-heuristic approaches. Genetic algorithms (GAs) and particle swarm
optimization (PSO) [22] autonomously control multiple UAVs for data collection
along specific flight routes, considering their dynamic properties and the
complexity of the real-time environment. Within this context, Sawalmeh et al.
[23] introduced genetic algorithms (GA) and particle swarm optimization (PSO)
to determine optimal trajectories for UAVs, aiming to meet the minimum data
rate requirements of multiple users. Their findings suggested that PSO
outperforms GA in terms of UAVs’ wireless coverage. Despite the numerous
advantages of meta-heuristic algorithms, challenges persist in exchanging
information between UAVs and core networks due to practical constraints, and
analytically computing gradients of these algorithms remains problematic.

To address convergence challenges associated with attaining global optima in
meta-heuristic algorithms, recent efforts have employed reinforcement learning
(RL) techniques [24, 25, 26, 27, 28, 29] for tasks such as mobility
management, resource allocation, and coverage optimization of UAVs. For
instance, in [25], optimal deployment and power allocation of UAVs were
explored to enhance users’ data rates using an RL approach based on the
Q-learning algorithm. Authors in [26] maximized the long-term reward in UAV-
enabled communication networks through a multi-agent RL (MARL) framework
employing the Q-learning algorithm. Here, each agent made decisions based on
its local observations. Works in [27] and [28] determined optimal UAV
trajectories using RL-based state-action-reward-state-action (SARSA) and
Q-learning algorithms, respectively, under limited spectrum resources.
Additionally, in [29], the optimization problem for UAV trajectories was
transformed into a Markov decision process (MDP) to maximize collected sensor
data. Although the SARSA algorithm demonstrated superiority over the
Q-learning technique, it requires extensive pre-calculated training labels for
deployment and control of multiple UAVs using standard RL algorithms. In
contrast, a centralized controller-operated distributed RL algorithm proves
more storage-efficient, avoiding the need for training labels and exhibiting
online learning for sample generation. Furthermore, wireless channel
allocation becomes crucial for UAVs to serve cell-edge users, particularly
during hotspot periods when terrestrial base stations are heavily loaded.
Hence, the challenge remains in alleviating data traffic from terrestrial base
stations while meeting individual users’ quality of service requirements as
data rate constraints, achieved through maximizing UAV utilization along their
optimized trajectory, a matter that remains an open problem.

###  I-C Motivation and Key Contributions

All the previously mentioned studies have introduced various resource
allocation strategies with optimal UAV trajectories to ascertain the highest
throughput and minimal energy consumption for both network users and UAVs.
Nevertheless, there has been limited investigation into leveraging UAVs to
serve a larger number of ground users, aiming to alleviate the data traffic
burden on the established terrestrial cellular network. Only a restricted
amount of research delves into maximizing the utility of UAVs at predetermined
hovering locations rather than optimizing trajectories, presenting significant
drawbacks, including:

  1. I)

_Low endurance:_ Since UAVs have limited on-board battery capacity, their
flying and hovering duration are short, which cannot provide sensing and
communication over a long periods [16]. This results in poor QoS delivered by
UAVs. Furthermore, the aerial cost of UAVs in terms of propulsion energy
consumption has been overlooked.

  2. II)

_Limited computing power:_ UAVs’ limited payload carrying constraints restrict
their computing power ability [17]. Hence, the ground users encounter high
transmission delays and low QoE while UAVs process computation-intensive
tasks.

  3. III)

_Inefficient offloading:_ During conventional offloading tasks, UAVs transfer
data to the cloud server or BS using a centralized architecture model [19].
This introduces high energy consumption, and low computing efficiency for
simultaneous task processing.

To address these constraints, it is imperative to develop an efficient
offloading mechanism that enhances the effectiveness of UAVs in load
balancing, particularly when transitioning from traditional terrestrial
communication systems. Recent research has explored the use of reinforcement
learning (RL) techniques [25, 26, 27, 28, 29] in UAV-assisted communications.
RL models the problem as a Markov Decision Process (MDP), where agents observe
the environment’s states, take actions, receive rewards, and transition to new
states accordingly. RL algorithms strive to maximize the expected cumulative
reward without converting non-convex problems into convex ones. They leverage
the capacity of state-action values to handle time-varying network parameters.
In this study, inspired by RL features and the challenges in UAV-enabled
wireless communication systems, we propose a cost-effective approach for
utilizing UAVs in offloading tasks for terrestrial base stations. This
approach considers both the propulsion energy consumption costs and operating
costs of UAVs as the total aerial cost. To the best of our knowledge, there
has been no exploration of an RL framework for maximizing UAV utility in terms
of associating with more users along their trajectories to achieve maximum
data offloading from cellular networks. Notably, optimizing UAV trajectories
for utility differs significantly from optimizing for users’ throughput or
minimizing energy consumption. As a result, cellular-connected UAVs can
dynamically manage transmission channels, enabling users to associate with
UAVs when meeting the minimum data rate constraint. The contributions of this
paper can be summarized in four main aspects:

  1. I)

The proposed framework optimizes the trajectories of multiple QoS-aware UAVs
as well as the instantaneous user-association indicators to maximize their
utilization while satisfying the data rate requirements of the individual
cellular users. Since UAVs have limited onboard energy capacity and certain
deployment costs, we efficiently determine their trajectories so that all UAVs
reach their destination from their respective initial position within a given
time and with fixed aerial costs.

  2. II)

We simplify the originally formulated problem into a finite state MDP that
maps between state and action spaces, by considering the impact of UAVs’ speed
on their trajectories. The transformed problem ensures UAVs’ actions that
drive them toward their final destinations at the end of the fixed duration
flying period.

  3. III)

We adopt a low-complexity reward impact cooperative MARL that helps UAVs to
decide discrete actions independently at a given discrete state. The proposed
approach provides more accurate guidance to the RL agents for maximizing the
long-term rewards corresponding to the optimal policy.

  4. IV)

Our extensive simulation results showcase that the proposed distributed SARSA
algorithm can effectively solve the considered problem that has multiple
optimization variables and practical constraints. The proposed design yields
high average UAV-associated users and improves offloading from the terrestrial
BSs, as compared with the benchmark Q-learning and PSO algorithms.

This paper represents a substantial expansion from its original conference
version [1], as it now incorporates the utilization of multiple UAVs to
facilitate load balancing in existing cellular networks, especially during
periods of high demand. In order to assess the performance of each UAV, an
average UAV association metric has been introduced to gauge the effectiveness
of the considered multi-UAV cooperative network. Significantly, a centralized
controller continuously monitors the collaborative behavior among UAVs and
optimizes their movement using a novel distributed SARSA algorithm, which
differs from the standard RL-based approach employed in [1]. Subsequently, we
demonstrate how the coordinated efforts of multiple UAVs can effectively
mitigate data traffic from terrestrial base stations through comprehensive
simulation results.

The remaining sections of the document are structured as follows. In Section
II, we provide the system model for the data offloading network under
consideration. Section III details the mathematical formulation of our defined
objective. The MARL framework and the proposed distributive SARSA algorithm
for controlling UAV trajectories optimization are introduced in Section IV.
Section V presents various insights derived from the simulation results to
assess the performance of the proposed approach. Lastly, Section VI concludes
the paper and outlines potential avenues for future research.

_Notation:_ Boldface variables denote vectors. The notation $\left\|x\right\|$
represents the Euclidean norm of $x$, the circularly symmetric complex
Gaussian variable $x$ with mean $\mu$ and variance $\sigma^{2}$ is denoted by
$x\sim\mathcal{CN}\left(\mu,\sigma^{2}\right)$, the statistical expectation is
defined as $\mathbb{E}\left\\{.\right\\}$, and $\mathcal{O}\left(.\right)$
denotes the big-O computational complexity notation.

##  II System and Channel Models

We commence by providing a brief overview of the chosen system and network
architecture, followed by an examination of the achievable throughput for the
UAVs. Subsequently, we outline the costs for the proposed system, taking into
account the comprehensive cost model that encompasses both propulsion energy
consumption costs and the costs associated with data reception and
transmission for all users and UAVs.

Figure 1: The considered cellular offloading network, assisted by multiple
cellular-connected UAVs.

###  II-A System Model

The multi-UAV-assisted cellular offloading network is depicted in Fig. 1. In
this network, $L$ UAVs undertake the task of offloading data traffic from $M$
terrestrial BSs, supporting uplink transmissions from $K$ static and uniformly
distributed ground users situated within a specified geographical area. To
ensure interference-free simultaneous transmission to the access points, it is
assumed that both UAVs and BSs are capable of receiving preallocated dedicated
subcarrier-enabled orthogonal signals following the orthogonal frequency
division multiple access (OFDMA) protocol [30]. As shown in [31, Fig. 2], $M$
BSs, positioned at a fixed height $H_{B}$, are strategically located on the
ground at positions
$\mathbf{\Theta}_{m}=\left(x_{m}^{B},y_{m}^{B},H_{B}\right),\forall
m\in\mathcal{M}=\left\\{1,2,...,M\right\\}$. These BSs establish hexagonal
grid cells with an inter-BS distance maintained at $D_{S}$. Each $l$th UAV,
$l\in\mathcal{L}=\left\\{1,2,…,L\right\\}$, maintains a fixed altitude of
$H_{0}$ during its flight from the initial location
$\mathbf{U}_{s_{l}}=\left(x_{s_{l}},y_{s_{l}},H_{0}\right)$ to the final
location $\mathbf{U}_{e_{l}}=\left(x_{e_{l}},y_{e_{l}},H_{0}\right)$ at a
constant speed of $v$. Due to the limited on-board energy capacity of UAVs,
their total energy budget remains constant, and each UAV is equipped with
sufficient energy for a fixed-duration flight, ensuring their arrival at the
destination before depleting their battery charges completely. The entire
flight time $\mathcal{T}$ for all UAVs is divided into $N$ discrete time slots
of equal length $\delta=\mathcal{T}/N$. The chosen slot duration $\delta$ is
sufficiently small to maintain each UAV’s location constant within a time
slot. With this time discretization, the instantaneous position of the $l$th
UAV is denoted by
$\mathbf{\Psi}_{l}\left[n\right]=\left(x_{l}\left[n\right],y_{l}\left[n\right],z_{l}\left[n\right]\right)$,
where $z_{l}\left[n\right]=H_{0}$ and
$n\in\mathcal{N}=\left\\{1,2,...,N\right\\}$.

###  II-B Channel Model

The transmission environment of the considered multi-UAV-assisted cellular
offloading network, as illustrated in Fig. 1, is governed by two types of
channels: user to BS and user to UAV channels. These channels serve as the
links between users and their respective nearest BS, as well as the links
between users and the reliable UAV platform. Assuming quasi-static block
fading channel properties, the instantaneous channel gain for each $k$th user
positioned at
$\mathbf{\Omega}_{k}=\left(x_{k},y_{k},0\right),k\in\mathcal{K}=\left\\{1,2,...,K\right\\}$
can be expressed as [27]

$h_{k}^{i}\left[n\right]=g_{k}^{i}\left[n\right]\sqrt{L_{k}^{i}\left[n\right]},$
(1)

Here, $i\in\left\\{U_{l},B_{m}\right\\},\forall
l\in\mathcal{L},m\in\mathcal{M}$ serves as the destination indicator, where
$U_{l}$ and $B_{m}$ represent the associated UAV and the nearest BS,
respectively.
$L_{k}^{i}\left[n\right]=\beta_{0}\left(d_{k}^{i}\left[n\right]\right)^{-\varrho}$
defines the average channel power gain, where $\varrho$ is the path loss
exponent, $\beta_{0}=\left(4\pi f_{c}c^{-1}\right)^{2}$ is the free space path
loss at a reference distance of $1$ m, $f_{c}$ is the carrier frequency, and
$c$ represents the speed of light. The small-scale fading coefficient is
described using the Rician fading distribution as [27]:

$g_{k}^{i}\left[n\right]\triangleq\sqrt{\frac{G_{k}^{i}\left[n\right]}{G_{k}^{i}\left[n\right]+1}}\bar{g}_{k}^{i}\left[n\right]+\sqrt{\frac{1}{G_{k}^{i}\left[n\right]+1}}\tilde{g}_{k}^{i}\left[n\right],$
(2)

Here, $\bar{g}_{k}^{i}\left[n\right]$ denotes the deterministic Line of Sight
(LoS) channel component with
$\mathbb{E}\left[|\bar{g}_{k}^{i}\left[n\right]|\right]=1$, and
$\tilde{g}k^{i}\left[n\right]\sim\mathcal{CN}\left(0,1\right)$ represents the
random scattering component.
$G_{k}^{i}\left[n\right]=A_{1}\exp{\left(A_{2}\phi_{k}^{i}\left[n\right]\right)}$
is the Rician factor, where
$\phi_{k}^{i}\left[n\right]=\sin^{-1}\left({H_{i}}/{d{k}^{i}\left[n\right]}\right)$
defines the elevation angle, $A_{1}$ and $A_{2}$ are environment-dependent
constants [27]. The instantaneous distance between the $k$th user and its
destination:

$d_{k}^{m}\left[n\right]=\left\|\mathbf{\Theta}_{m}-\mathbf{\Omega}_{k}\right\|,\forall
m\in\mathcal{M},$ (3)
$d_{k}^{l}\left[n\right]=\left\|\mathbf{\Psi}_{l}\left[n\right]-\mathbf{\Omega}_{k}\right\|,\forall
l\in\mathcal{L},$ (4)

The achievable instantaneous transmission rate of user $k$ can be expressed as
[27]

$R_{k}^{i}\left[n\right]=C_{B}\log_{2}\left(1+\frac{P_{k}\big{|}h_{k}^{i}\left[n\right]\big{|}^{2}}{\sigma^{2}}\right).$
(5)

Here, $\sigma^{2}$ is the noise power, $P_{k}$ is the transmit power of each
user, and $C_{B}$ represents the transmission bandwidth.

###  II-C UAVs’ Cost Model

The aerial cost encompasses all expenditures associated with UAVs, covering
both internal energy consumption and operating costs, which include
displacement and remote control costs. The momentary operational cost
$C_{O}\left[n\right]=\varsigma L$ follows a linear function of the number of
UAVs, where $\varsigma$ represents the cost of operating a single UAV [32].
UAVs’ internal energy consumption serves two purposes: one is for propulsion,
supporting mobility by generating the necessary thrust to overcome drag forces
and gravity; the other is for communication with ground users, involving
energy consumption in electronic circuits, signal processing, signal
radiation, and reception. The required propulsion power for a quadrotor UAV
$l$ to maintain a constant speed $v$ can be expressed as [33]

$\small{P_{F}^{l}\left(v\right)=n_{r}\Bigg{[}\frac{\zeta}{8}\left(\frac{T_{h}\left(v\right)}{c_{T}\rho
A}+3v^{2}\right)\sqrt{\frac{\rho
c_{s}^{2}AT_{h}\left(v\right)}{c_{T}}}+\frac{1}{2}d_{0}v^{3}\rho c_{s}A}$
$\small{+T_{h}\left(v\right)\left(1+c_{f}\right)\sqrt{\sqrt{\frac{T_{h}^{2}\left(v\right)}{4\rho^{2}A^{2}}+\frac{v^{4}}{4}}-\frac{v^{2}}{2}}+\frac{\mathfrak{m}gv}{n_{r}}\sin\left(\tau_{c}\right)\Bigg{]},}$
(6)

In the expression, $n_{r}$ stands for the number of rotors, $\zeta$ represents
the drag coefficient, $T_{h}\left(v\right)$ signifies the thrust generated by
each rotor to achieve a speed of $v$, $c_{T}$ denotes the thrust coefficient
based on disc area, $\rho$ stands for air density, $A$ represents the disc
area of each rotor, $c_{s}$ signifies the rotor solidity, $d_{0}$ is the
fuselage drag ratio for each rotor, $c_{f}$ represents an incremental
correlation factor, $\mathfrak{m}$ denotes the mass of the UAV, $g$ stands for
gravitational acceleration, and $\tau_{c}$ represents the climb angle. The
parameter values utilized in (6) are elaborated in [33, Table-III]. Given that
UAVs function as receivers, their energy expenditure is solely incurred for
collecting data from ground users for BS offloading purposes. Consequently,
UAVs do not consume any energy for signal transmission through radiation. The
required power of UAV $l$ to collect data from associated users at $n$th slot
can be expressed as [34]

$P_{C}^{l}\left[n\right]=P_{S}+\sigma_{D}\sum_{k=1}^{K}I_{k}^{l}\left[n\right]R_{k}^{l}\left[n\right],$
(7)

In this context, $R_{k}^{l}\left[n\right]$ represents the instantaneous
transmission rate of the $k$th user while being associated with the UAV,
$P_{S}$ denotes the static power necessary for receiving, and $\sigma_{D}$
stands for the dynamic unit rate decoding power. The overall energy consumed
by each UAV at each moment is

$E_{S}^{l}\left[n\right]=\left(P_{F}^{l}\left(v\right)+P_{C}^{l}\left[n\right]\right)\delta,$
(8)

We define the total instantaneous aerial cost as the sum of the energy
consumption cost for all UAVs and their overall operating cost, represented as
[32]

$C_{T}\left[n\right]=C_{O}\left[n\right]+\sum_{l=1}^{L}\mu
E_{S}^{l}\left[n\right].$ (9)

where, $\mu$ is the energy cost of a UAV measured in price/Joul.

##  III Problem Definition

In this section, we elucidate the definition of user association, followed by
the mathematical formulation of the UAVs’ utility maximization problem.
Subsequently, we address the non-convex nature of the problem and introduce
the Multi-Agent Reinforcement Learning (MARL) scheme for attaining optimal
user association and UAV trajectory within the prescribed limited flying
period. Our proposed approach offers a distinctive methodology for resolving
the non-convex optimization problem associated with multiple cooperative and
interacting agents, highlighting significant novelty of the work.

###  III-A User Association

Each user has the option to connect with a single UAV during a time slot,
contingent on the maximum achievable transmission rate among all UAVs.
Conversely, individual UAVs can concurrently serve up to $K$ users. In
practice, effective offloading from base stations (BSs) occurs when a greater
number of users opt to connect with UAVs rather than the BS. All UAVs are
equipped with ample onboard energy for limited flight duration and data
collection from users, maintaining a safe distance to prevent inter-UAV
collisions. The offloading of data traffic from terrestrial BSs occurs only
when users transmit a minimum of $D_{\min}$ bits of data to the UAVs within a
time slot; otherwise, users associate with their respective nearest BS.
Consequently, the instantaneous association indicator of the $k$th user with
UAVs and the nearest BS is defined as

$I_{k}^{l}\left[n\right]=\begin{cases}1,\text{if}\hskip
2.84526pt{D}_{k}^{l}\left[n\right]\geq{D}_{\min}\\\ 0,\text{if}\hskip
2.84526pt{D}_{k}^{l}\left[n\right]<{D}_{\min}\end{cases},l=\underset{\bar{l}\in\mathcal{L}}{\arg\max}\,{D}_{k}^{\bar{l}}\left[n\right],$
(10) $I_{k}^{m}\left[n\right]=\begin{cases}1,\text{if}\hskip
2.84526pt{D}_{k}^{m}\left[n\right]<{D}_{\min}\\\
0,\text{Otherwise}\end{cases},m=\underset{\bar{m}\in\mathcal{M}}{\arg\max}\,{D}_{k}^{\bar{m}}\left[n\right].$
(11)

where $D_{k}^{i}\left[n\right]=\delta R_{k}^{i}\left[n\right]$ is the data
transmitted by user $k$ during the $n$th time slot.

###  III-B Optimization Formulation

To facilitate the offloading of data traffic from terrestrial base stations,
thereby improving the efficiency of UAVs for service delivery, the objective
in this paper is to maximize the average UAV-user associations. This is
achieved by optimizing the flight trajectory of UAVs and corresponding user-
association indicators, with the constraint that each user transmits a minimum
of $D_{\min}$ bits of data during each time slot to be associated with the
UAVs. In mathematical terms, the proposed maximization of UAV utilization is
expressed as

$\displaystyle\begin{split}\mathcal{OP}:\,\,&\underset{\Big{\\{}\underset{\forall
l\in\mathcal{L},k\in\mathcal{K},m\in\mathcal{M},n\in\mathcal{N}}{\left(x_{l}\left[n\right],y_{l}\left[n\right]\right),I_{k}^{l}\left[n\right],I_{k}^{m}\left[n\right],}\Big{\\}}}{\text{Maximize}}\,\,\sum_{n=1}^{N}\sum_{l=1}^{L}\sum_{k=1}^{K}\frac{I_{k}^{l}\left[n\right]}{L},\\\
&\text{Subject to}\,\eqref{Eq_10},\,\eqref{Eq_11},\end{split}$
$\displaystyle\begin{split}(a):\sum_{n=1}^{N}C_{T}\left[n\right]\leq
C_{\max},\\\ &(b):I_{k}^{l}\left[n\right]+I_{k}^{m}\left[n\right]=1,\forall
l\in\mathcal{L},k\in\mathcal{K},m\in\mathcal{M},n\in\mathcal{N},\\\
&(c):\left\|\mathbf{\Psi}_{l}\left[n\right]-\mathbf{\Psi}_{\bar{l}}\left[n\right]\right\|\geq
d_{S},\forall l,\bar{l}\in\mathcal{L},l\neq\bar{l},n\in\mathcal{N},\\\
&(d):\left\|\mathbf{\Psi}_{l}\left[n+1\right]-\mathbf{\Psi}_{l}\left[n\right]\right\|=\delta
v,\forall l\in\mathcal{L},n\in\mathcal{N},\\\
&(e):\left(x_{l}\left[1\right],y_{l}\left[1\right],H_{0}\right)=\mathbf{U}_{s_{l}},\forall
l\in\mathcal{L},\\\
&(f):\left(x_{l}\left[N\right],y_{l}\left[N\right],H_{0}\right)=\mathbf{U}_{e_{l}},\forall
l\in\mathcal{L}.\end{split}$

where $(a)$ denotes the overall aerial cost budget allocated to all UAVs for
the entire operation; $(b)$ specifies that a user can associate with either a
UAV or the nearest base station during a time slot; $(c)$ defines the
condition to prevent collisions among UAVs; $(d)$ ensures that UAVs maintain a
constant velocity throughout their trajectory. Additionally, constraints $(e)$
and $(f)$ represent the initial and final locations of all UAVs, respectively.

The optimization problem $\mathcal{OP}$ involves dynamic variables, making it
non-convex and challenging to achieve optimal solutions. Additionally, the
left side of constraint $(a)$ represents a cumulative variable over the long
term, related to UAVs’ flight trajectories, considering the entire flight
process when determining the position of each UAV in a specific time slot.
Consequently, it becomes highly challenging for successive convex optimization
tools or meta-heuristic algorithms to efficiently explore and adapt to multi-
dimensional search spaces for all potential state changes, leading to a
significant increase in computational complexity. As an alternative, we
propose a Multi-Agent Reinforcement Learning (MARL) framework with finite
discrete states and action spaces to address this complexity. Specifically, we
model each UAV as an independent Reinforcement Learning (RL) agent tasked with
learning to select a specific action at a discrete state that maximizes the
long-term objective. Standard RL algorithms like Q-learning and SARSA can
formulate optimal policies for a single agent. Although we treat each UAV as
an individual RL agent in our approach, standard RL algorithms cannot observe
the activities of all UAVs simultaneously, making them unsuitable for
maintaining inter-UAV cooperative behavior. To overcome this limitation, we
adopt a distributed SARSA algorithm that ensures rapid convergence. This
algorithm is capable of finding the optimal placement of UAVs in consecutive
discrete time slots and determining the corresponding user-association
indicators based on the instantaneous channel gains of the current time slot,
promoting efficient inter-UAV collaboration.

##  IV Proposed UAVs Utility Maximization

This section is focused on the collective optimization investigation to
identify the most effective utilization of UAVs for data offloading from
terrestrial base stations during hotspot periods. We commence with the
formulation of a Markov Decision Process (MDP), incorporating the intelligent
selection of access points by users based on their real-time location in the
dynamic environment.

###  IV-A MDP-Based Problem Transformation

In a multi-agent setting, UAVs function as Reinforcement Learning (RL) agents,
and the immediate decision made by each UAV is contingent on the collective
actions of all UAVs during each time slot. In this setup, a centralized
controller continuously monitors the activities of all UAVs and assigns a
valid instantaneous action to each UAV. As a result, each UAV independently
makes decisions and operates as an intelligent entity. Therefore, we formulate
the decision-making process of multiple UAVs as a Markov Decision Process
(MDP) to facilitate inter-UAV cooperative behavior within a constrained
timeframe. Following the Markovian properties, the current states of UAVs are
solely dependent on their preceding states and actions. The MDP for a total of
$L$ UAVs encompasses the state space, action space, state transition, and
reward. The components of the proposed MDP model are as follows:

####  IV-A1 State Space

The system’s state vector at $n$th time slot is defined as
$\mathbf{s}\left[n\right]=\left[\mathbf{\psi}\left[n\right],\mathbf{E}\left[n\right]\right]\in\mathcal{S}$,
which is composed of two elements as follows:

  * •

$\mathbf{\psi}\left[n\right]=\left[\left(x_{1}\left[n\right],y_{1}\left[n\right]\right),…,\left(x_{L}\left[n\right],y_{L}\left[n\right]\right)\right]\in\mathcal{U}^{L}$
is the vector of all UAVs’ current location projected on the ground, where
$\mathcal{U}^{L}$ is the set of all UAVs’ possible two dimensional (2D)
locations.

  * •

The vector
$\mathbf{E}\left[n\right]=\left[E_{S}^{1}\left[n\right],E_{S}^{2}\left[n\right],…,E_{S}^{L}\left[n\right]\right]\in\mathcal{E}^{L}=\left[0,E_{\max}\right]$
represents the energy consumption of all UAVs at the $n$th time slot. Here,
$\mathcal{E}^{L}$ denotes the set of energy consumptions for all UAVs, and
$E_{\max}$ is the maximum battery capacity of each UAV.

####  IV-A2 Action Space

We define the current action $\theta_{l}\left[n\right]$ of the $l$th UAV as
the change in its direction angle, measured from its current location. In each
time slot, the UAV selects a direction from the four available options: EAST,
NORTH, WEST, and SOUTH. The corresponding action values are represented as
$\theta_{l}\left[n\right]=\left\\{0,\pi/2,\pi,3\pi/2\right\\}\in\mathbf{a}\left[n\right]$
radians, respectively. After choosing an action, the changes in the $x$ and
$y$ coordinates of the $l$th UAV are measured as

$\Delta_{x}^{l}\left[n\right]=v\delta\cos{\theta_{l}\left[n\right]},$ (12)
$\Delta_{y}^{l}\left[n\right]=v\delta\sin{\theta_{l}\left[n\right]},$ (13)

We partition the designated area into non-overlapping square grid sections,
forming a grid of dimensions $L_{1}\times L_{2}$, with each grid having sides
of length $\delta v$. Specifically, we have chosen $L_{1}=\frac{X_{1}}{\delta
v}+1$ and $L_{2}=\frac{X_{2}}{\delta v}+1$, where $X_{1}$ and $X_{2}$
represent the length and width of the target area, respectively. During a time
slot, UAVs travel at a fixed altitude from the center of one grid to the
center of an adjacent grid. This straightforward design of the action space
reduces the dimensionality of the Markov Decision Process (MDP) problem,
allows for a greater number of action values, providing more trajectory
choices for UAVs, and enhances the convergence of learning-based algorithms.
Any action that results in an invalid flight at a given state is disregarded
for each UAV. Thus, the available set of actions varies at a particular state,
where an invalid flight implies that UAVs go beyond the target area or collide
with each other.

####  IV-A3 State Transition

It is defined as the probability of the system transitioning from state
$\mathbf{s}\left[n\right]$ to $\mathbf{s}\left[n+1\right]$ after taking action
$\mathbf{a}\left[n\right]$, denoted as
$P_{r}\left(\mathbf{s}\left[n+1\right]=s^{\prime}|\mathbf{s}\left[n\right]=s,\mathbf{a}\left[n\right]=a\right)$.
As the location of each UAV at the $\left[n+1\right]$th time slot depends on
its position and moving direction at the $n$th time slot, the UAV’s flight
process can be viewed as a discrete-time Markov Decision Process (MDP). The
dynamics of the $l$th UAV are updated as

$x_{l}\left[n+1\right]=x_{l}\left[n\right]+\Delta_{x}^{l}\left[n\right],$ (14)
$y_{l}\left[n+1\right]=y_{l}\left[n\right]+\Delta_{y}^{l}\left[n\right],$ (15)

The remaining energy of each UAV diminishes over time. When the $l$th UAV
possesses ample on-board energy in the present time slot, that is, $0\leq
e_{l}\left[n\right]\leq E_{\max}$, it can efficiently collect data. The energy
consumption of each UAV is assessed using (8) in the current time slot, and
its remaining energy for future times can be computed as

$e_{l}\left[n+1\right]=e_{l}\left[n\right]-E_{S}^{l}\left[n\right],$ (16)

####  IV-A4 Reward

All UAVs generate rewards based on the current state, action, and the
subsequent state
$\left(\mathbf{s}\left[n\right],\mathbf{a}\left[n\right],\mathbf{s}\left[n+1\right]\right)$.
In this context, the immediate reward includes the instantaneous objective
value contributed by each UAV, specifically, the individual UAV-user
associations at the $n$th time slot. Therefore, the reward contribution of the
$l$th UAV is assessed at the current time slot as

$r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)=\sum_{k=1}^{K}I_{k}^{l}\left[n\right].$
(17)

###  IV-B Equivalent Transformation

We simplify the original optimization problem to facilitate the RL framework
in selecting a straightforward action at a given state. In the original
problem, the optimizing variables
$\left(x_{l}\left[n\right],y_{l}\left[n\right]\right),I_{k}^{l}\left[n\right],I_{k}^{m}\left[n\right],\forall
l\in\mathcal{L},k\in\mathcal{K},m\in\mathcal{M},n\in\mathcal{N}$ encompass a
total of $N\left(K\left(L+M\right)+2L\right)$ decision spaces. To reduce this
extensive dimension, we model the RL framework as a Gridworld virtual
environment, where the $L$ UAVs can only move to one of four possible adjacent
grids instantaneously due to velocity constraints, as mentioned in Section
IV-A2. With the number of decision spaces now reduced to $NL$, the RL
framework can implement real-time trajectories of the UAVs with low
complexity. All UAVs are aware of the current channel gains of all users and
calculate users’ instantaneous transmission rates according to (5). If the
achievable transmission rates of multiple UAVs corresponding to a user surpass
the data rate constraints, the user associates with the UAV providing the
maximum transmission rate among all UAVs. Otherwise, the user associates with
the nearest BS, as defined in (10) and (11), and
$I_{k}^{m}\left[n\right]=1-I_{k}^{l}\left[n\right],\forall
l\in\mathcal{L},k\in\mathcal{K},m\in\mathcal{M},n\in\mathcal{N}$. Over
successive time slots within the given flight period, the user association
process is reiterated, maximizing the long-term reward by finding the optimal
successive locations of UAVs
$\left(\hat{x}_{l}\left[n\right],\hat{y}_{l}\left[n\right]\right),\forall
l\in\mathcal{L},n\in\mathcal{N}$. Importantly, users’ achievable transmission
rates depend on UAVs’ trajectories, which, in turn, depend on their changed
location at every time slot, as defined in (14) and (15) after taking their
respective direction angles. Thus, the multiple optimizing variables of
$\mathcal{OP}$ can be transformed into UAVs’ one-dimensional time-varying
moving directions as their immediate action values. The corresponding
objective problem is then simplified as

$\displaystyle\begin{split}\mathcal{OP}1:\,\,&\max_{\big{\\{}\underset{}{\theta_{l}\left[n\right],\forall
l\in\mathcal{L},n\in\mathcal{N}}\big{\\}}}\,\,\sum_{n=1}^{N}\sum_{l=1}^{L}\sum_{k=1}^{K}\frac{I_{k}^{l}\left[n\right]}{L},\\\
&\text{Subject to}\,\eqref{Eq_10},\,\eqref{Eq_11},\,(a),\,(b),\,(c),\quad\\\
&(g):\left(x_{l}\left[1\right]+\sum_{u=1}^{N-1}v\delta\cos{\theta_{l}\left[u\right]},y_{l}\left[1\right]+\sum_{u=1}^{N-1}v\delta\sin{\theta_{l}\left[u\right]},H_{0}\right)^{2}\\\
&=\mathbf{U}_{E_{l}},\forall l\in\mathcal{L},\\\
&(h):\left(x_{l}\left[N\right]-x_{l}\left[1\right]-\sum_{u=1}^{n-1}v\delta\cos{\theta_{l}\left[u\right]}\right)^{2}+\Bigg{(}y_{l}\left[N\right]-y_{l}\left[1\right]\\\
&-\sum_{u=1}^{n-1}v\delta\sin{\theta_{l}\left[u\right]}\Bigg{)}^{2}\leq{v^{2}}{\delta^{2}}{\left(N-n\right)}^{2},\forall
n>1.\end{split}$

Here, constraint $(g)$ guarantees that the UAVs reach their destination by the
final time slot, and $(h)$ ensures the successive actions of UAVs leading them
to the destination at the $N$th time slot.

###  IV-C Optimal Trajectories using Distributed SARSA Algorithm

Based on their current states, UAVs determine optimal flight paths through
trial and error, aiming to maximize the number of users associated with UAVs
throughout the entire flight duration. Thus, we denote the policy of each UAV
as $\Pi_{l}\left(\theta_{l}\left[n\right]|\mathbf{s}\left[n\right]\right)={\rm
Pr}\left(\theta_{l}\left[n\right]=\mathfrak{a}|\mathbf{s}\left[n\right]=\mathfrak{s}\right)$,
where ${\rm Pr}\left(\cdot|\cdot\right)$ represents conditional probability.
This policy serves as a mapping from a state to an action, intending to
maximize the discounted cumulative long-term reward provided by all UAVs. The
expression for the total reward $\bar{r}$ is given by
$\sum_{n=0}^{N-1}\sum_{l=1}^{L}\gamma^{n}r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$,
where $\gamma\in\left(0,1\right)$ serves as the discount factor. The
$\epsilon$-greedy policy is employed to maximize the Q-value, i.e., the state-
action value of each UAV. This Q-value, representing the probability of taking
an action at a discrete state
$\mathbf{s}_{l}\left[n\right]=\left[\left(x_{l}\left[n\right],y_{l}\left[n\right]\right),e_{l}\left[n\right]\right]$,
is defined as [27]

$\small{{\Pi_{\epsilon}^{l}}\left(\theta_{l}\left[n\right]|\mathbf{s}\left[n\right]\right)\\!=\\!\begin{cases}\underset{\theta_{l}\left[n\right]}{\arg\max}\,\,Q\left(\mathbf{s}\left[n\right],\theta_{l}\left[n\right]\right),\,\text{probability}\hskip
5.69054pt1-\epsilon\\\ \text{Randomly
select}\,\theta_{l}\left[n\right],\,\text{with probability}\hskip
2.84526pt\epsilon\end{cases},}$ (18)

At each state, every UAV selects an action from the action space, gaining an
immediate reward. Subsequently, its current state transitions to the next
state, and it chooses an action for this subsequent state following the same
action selection approach. This iterative action selection and state updating
sequence is termed as an episode spanning across the total number of steps. As
a result, the state-action value of the $l$th UAV at each $n$th time slot
undergoes an update relative to the learning rate $\alpha$ as [27]

$\displaystyle
Q_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$
$\displaystyle\leftarrow\left(1-\alpha\right)Q\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$
$\displaystyle+\alpha\left[r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)+\gamma
Q\left(\mathbf{s}_{l}\left[n+1\right],\theta_{l}\left[n+1\right]\right)\right].$
(19)

###  IV-D Algorithmic Implementation

Algorithm 1 Distributed learning of UAVs’ trajectories

1:

  * $\gamma$, $\alpha$, $\epsilon$, $K$, $M$, $L$, $N$, $H_{B}$, $H_{0}$, $\delta$, $v$, $T$, ${D}_{\min}$, $\mathbf{U}_{s_{l}}=\left(x_{s_{l}},y_{s_{l}},H_{0}\right)$, $\mathbf{U}_{e_{l}}=\left(x_{e_{l}},y_{e_{l}},H_{0}\right)$, $\mathbf{\Omega}_{k}$, $\mathbf{\Theta}_{m}$, $h_{k}^{i}\left[n\right]$, $\forall\mathbf{s}_{l}\left[n\right]\in\mathcal{S},\theta_{l}\left[n\right]\in\mathcal{A},k\in\mathcal{K},m\in\mathcal{M},l\in\mathcal{L},n\in\mathcal{N}$.

2:

  * Optimal policy $\Pi_{l}^{*}\left(\theta_{l}\left[n\right]|\mathbf{s}\left[n\right]\right)$ .

3:Initialize
$Q\left(\mathbf{s}\left[n\right],\theta_{l}\left[n\right]\right)=0,\forall\mathbf{s}\left[n\right]\in\mathcal{S},\theta_{l}\left[n\right]\in\mathcal{A},l\in\mathcal{L}$.

4:for $t=1,2,...,T$ do

5:

  * Set the start point and initial onboard energy of all UAVs as

  * $\mathbf{\Psi}_{l}\left[1\right]=\left(x_{l}\left[1\right],y_{l}\left[1\right],H_{0}\right)=\mathbf{U}_{S_{l}},e_{l}\left[1\right]=E_{\max},\forall l\in\mathcal{L}$

6: for $n=1,2,...,N$ do

7: if $n\leq N-2$ then

8: for $l=1,2,...,L$ do

9: if $e_{l}\left[n\right]\geq 0$ and

10:
$\left\|\mathbf{\Psi}_{l}\left[n\right]-\mathbf{U}_{E_{l}}\right\|\leq\delta
v\left(N-n\right),\forall l\in\mathcal{L}$ then

11:

  * Choose the action values

  * $\theta_{l}\left[n\right]=\left\\{\Delta_{x}^{l}\left[n\right],\Delta_{y}^{l}\left[n\right]\right\\}$ by (18)

12: Get immediate reward
$r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$ by
(17)

13:

  * Find next state by (14), (15), and (16), as

  * $\mathbf{s}_{l}\left[n+1\right]=\left[\left(x_{l}\left[n+1\right],y_{l}\left[n+1\right]\right),e_{l}\left[n+1\right]\right]$

14:

  * Take joint observations $\mathbf{s}\left[n\right]=\left[\mathbf{\Psi}_{l}\left[n\right],e_{l}\left[n\right]\right]_{l=1}^{L}$,

  * joint actions $\left[\theta_{l}\left[n\right]\right]_{l=1}^{L}$, joint reward

  * $\left[r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)\right]_{l=1}^{L}$, and joint next observations

  * $\mathbf{s}\left[n+1\right]=\left[\mathbf{\Psi}_{l}\left[n+1\right],e_{l}\left[n+1\right]\right]_{l=1}^{L}$

  * while satisfying (10), (11), and $(a)$-$(f)$

15: for $l=1,2,...,L$ do

16:

  * Choose the next action values using (18) as

  * $\theta_{l}\left[n+1\right]=\left\\{\Delta_{x}^{l}\left[n+1\right],\Delta_{y}^{l}\left[n+1\right]\right\\}$

17: Update
$Q_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$
value by (IV-C)

18:

  * Update state and action respectively as

  * $\mathbf{s}_{l}\left[n\right]\leftarrow\mathbf{s}_{l}\left[n+1\right]$ and $\theta_{l}\left[n\right]\leftarrow\theta_{l}\left[n+1\right]$

19: else if $n=N-1$ then

20: for $l=1,2,...,L$ do

21: if $e_{l}\left[n\right]\geq 0$ and
$\left\|\mathbf{\Psi}_{l}\left[n\right]-\mathbf{U}_{E_{l}}\right\|\leq\delta
v$ then

22: Obtain next state as
$\mathbf{s}_{l}\left[n+1\right]=\left[\left(x_{E_{l}},y_{E_{l}}\right)\right]$

23: Get instant reward
$r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$ by
(17)

24:

  * Choose the next action using (18) as

  * $\theta_{l}\left[n+1\right]=\left\\{\Delta_{x}^{l}\left[n+1\right],\Delta_{y}^{l}\left[n+1\right]\right\\}$

25: Update
$Q_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$
value by (IV-C)

26:

  * Update state and action respectively as

  * $\mathbf{s}_{l}\left[n\right]\leftarrow\mathbf{s}_{l}\left[n+1\right]$ and $\theta_{l}\left[n\right]\leftarrow\theta_{l}\left[n+1\right]$

27: else

28: Break

29: Get $l$th UAV’s utility as
$\sum_{n=1}^{N}r_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right),\forall
l\in\mathcal{L}$

30:

  * Find optimal policy $\forall\mathbf{s}_{l}\left[n\right]\in\mathcal{S},\theta_{l}\left[n\right]\in\mathcal{A},l\in\mathcal{L},n\in\mathcal{N}$ as

  * $\Pi_{l}^{*}\left(\theta_{l}\left[n\right]|\mathbf{s}_{l}\left[n\right]\right)=\underset{\theta_{l}\left[n\right]=\left\\{\Delta_{x}^{l}\left[n\right],\Delta_{y}^{l}\left[n\right]\right\\}}{\arg\max}\hskip 2.84526ptQ_{l}\left(\mathbf{s}_{l}\left[n\right],\theta_{l}\left[n\right]\right)$

UAVs repetitively acquire state-action pair values at each time slot within
every episode, engaging in interactions with the environment. These
interaction outcomes are logged in their respective Q-tables and incorporated
into their learning policies after each episode, continuing until the Q-tables
converge. Decision-making policies are obtained for suboptimal solutions as
UAVs relocate. The optimal trajectory learning process, utilizing the
distributed SARSA technique, is summarized in Algorithm 1. In this scheme, the
centralized controller initially computes the current state of UAVs, distances
from all users to UAVs and the nearest BS at each time slot in every episode,
adhering to constraints $(a)$, $(e)$, and $(f)$ that ensure UAVs’ remaining
cost budget and initial and final states are met. Subsequently, UAVs take
actions in accordance with the $\epsilon$-greedy scheme. The centralized
controller then observes the joint actions of all UAVs, evaluating the impact
of each action on the long-term reward. Prohibited actions are discarded to
ensure UAVs maintain a safe distance from each other and stay within the
boundaries of a predefined target area while flying at a constant speed, as
specified by constraints $(c)$ and $(d)$. This ensures the generation of valid
policies. Users transmit data to either UAVs or the nearest BS based on the
instantaneous user association indicator value, considering constraints $(b)$,
(10), and (11). Finally, UAVs update their locations using (14) and (15).
Thus, all UAVs determine the most suitable discrete actions in each discrete
state according to the $\epsilon$-greedy policy, ensuring their initial and
final positions comply with constraints $(g)$ and $(h)$. This approach
enforces action bounds for all UAVs, preventing the generation of unbounded
actions corresponding to their optimal trajectories.

###  IV-E Complexity Analysis

The steps from 5 to 25 in Algorithm 1 encapsulates the collaborative behavior
of all UAVs to optimize data traffic offloading from terrestrial BSs,
effectively approximating the transformed problem into a convex format. As
convex problems can be directly addressed using interior point methods, the
computational complexity of our proposed algorithm is predominantly determined
by the total number of optimizing variables. Consequently, we train the MARL
model proposed in our study over $T$ episodes, each spanning $N$ discrete time
slots. The computational complexity is contingent on the total number of
steps, which amounts to $TN$. Given that $L$ UAVs navigate through $L_{1}$ and
$L_{2}$ grid rows and columns, respectively, with four potential actions for
each state, the overall computational complexity of Algorithm 1 is denoted as
$\mathcal{O}\left(4TNLL_{1}L_{2}\right)$, encompassing the complexity
associated with the $\epsilon$-greedy policy at each step.

(a) Learn rate = $10^{-4}$.

(b) Learn rate = $5\times 10^{-4}$.

(c) Learn rate = $10^{-5}$.

Figure 2: Convergence behavior of the average UAV association for different
hyperparameter values.

##  V Simulation Results and Discussion

This section conducts comprehensive simulations to validate the performance of
the multi-UAV-supported offloading systems through various numerical analyses.
Traditionally, Particle Swarm Optimization (PSO), as a meta-heuristic
algorithm [23], has been utilized for evaluating UAV trajectories. In this
study, we aim to demonstrate the effectiveness of the proposed design by
comparing it to the benchmark PSO and another RL algorithm, Q-learning [28].
Using the system parameters outlined in [27], we randomly distribute 100 users
within a $2000\times 2000$ m square field, with default values as follows:
$D_{S}=500$ m, $\sigma^{2}=-110$ dBm, $f_{c}=2.4$ GHz, $C_{B}=1$ MHz,
$\varrho=2$, $A_{1}=3.1623$, $A_{2}=1.466$, $M=17$, $H_{B}=30$ m, $H_{0}=50$
m, $v=20$ m/s, $\delta=5$ s, $L=4$, $d_{S}=100$ m, $K=100$, $N=200$,
$\epsilon=0.1$, $\gamma=0.9$, $\mathbf{U}_{S_{1}}=\left(-1000,-1000,50\right)$
m, $\mathbf{U}_{S_{2}}=\left(1000,-1000,50\right)$ m,
$\mathbf{U}_{S_{3}}=\left(1000,1000,50\right)$ m,
$\mathbf{U}_{S_{4}}=\left(-1000,1000,50\right)$ m,
$\mathbf{U}_{E_{1}}=\left(1000,1000,50\right)$ m,
$\mathbf{U}_{E_{2}}=\left(1000,1000,50\right)$ m,
$\mathbf{U}_{E_{3}}=\left(-1000,-1000,50\right)$ m,
$\mathbf{U}_{E_{4}}=\left(1000,-1000,50\right)$ m.

###  V-A Convergence Analysis

Fig. 2 depicts the episodic variations in the average UAV association achieved
by the proposed distributed SARSA algorithm. In these simulations, we maintain
users’ transmit power at $-65$ dBm to meet the data rate constraint of $12.5$
Mbps per time slot. As observed in the figure, the average UAV association
demonstrates an increasing trend across episodes and eventually converges. The
choice of learning rate significantly influences the training process. A low
learning rate results in slow progress since it updates the Q-value gradually,
leading to a prolonged convergence time for optimal policy. Conversely, a high
learning rate leads to aggressive Q-value updates, causing overshooting and
oscillation around the optimal policy. The figure highlights that fluctuations
and convergence rates vary when the learning rate changes from $10^{-5}$ to
$10^{-4}$. Considering model stability, we set the learning rate at $0.0005$
for subsequent simulations.

To assess the computational complexity of both the proposed and benchmark
algorithms, we examine the evolution of the objective value over running time,
as depicted in Fig.3. Notably, the meta-heuristic PSO exhibits swift
convergence to the optimal value, contrasting with RL algorithms such as
distributed SARSA and Q-learning. The latter transforms the formulated problem
into finite discrete states and actions, causing UAVs to consider all
predefined discrete state and action space elements, thereby requiring more
time to find the optimal solution. In contrast, PSO navigates the solution
space through a random inertia weight and corresponding updates to particles’
positions and velocities, effectively reducing the search space to find local
optima. Additionally, distributed SARSA employs an $\epsilon$-greedy action
selection scheme for all states when updating the Q-table. In contrast, the
Q-learning algorithm updates by considering the maximum reward corresponding
to an action from possible future states without verifying the significance of
that action. Consequently, the proposed distributed SARSA algorithm achieves
more substantial convergence values. Given the extensive number of state
elements and multiple interactive optimizing variables in the objective
problem, PSO inefficiently explores the search space due to its random inertia
weight. Consequently, the performance of PSO is notably inferior. Fig. 3
reveals that the distributed SARSA, benchmark Q-learning, and PSO algorithms
take approximately $9000$ s, $7000$ s, and $5000$ s to converge, respectively.
The proposed algorithm outperforms benchmark Q-learning and PSO by $4.55\%$
and $15.08\%$, respectively.

Figure 3: Computational time comparison between proposed and benchmark
algorithms.

(a) UAVs’ movement corresponding distributed SARSA algorithm.

(b) UAVs’ movement corresponding Q-learning algorithm.

(c) UAVs’ movement corresponding PSO algorithm.

Figure 4: Optimized UAVs’ trajectory obtained by proposed and benchmark
algorithms.

###  V-B Insights on Trajectory and Association

As depicted in Fig. 4, the UAVs successfully reach their designated
destinations by the end of the given time slot. Throughout their flight, the
UAVs strategically associate with users situated at a considerable distance
from the BSs. These users, unable to meet the required data rate constraint,
prompt the UAVs to extend their coverage by navigating towards them.
Consequently, these users opt to transmit data to the UAVs rather than the
nearest BS, contributing to an enhanced utility for the UAVs through maximal
data traffic offloading from terrestrial BS. Previous observations have
revealed distinct limitations in the benchmark algorithms, preventing them
from accurately determining UAVs’ optimal successive locations. In contrast,
our proposed approach significantly refines UAV trajectories, meeting more
users’ QoS requirements and effectively offloading data traffic from BSs.

(a) $n=50$.

(b) $n=100$.

(c) $n=150$.

Figure 5: User association for different time instance locations of UAVs.

To obtain a clear view of BS offloading during UAVs’ optimal trajectories,
Fig. 5 presents the users’ association for optimal instant UAVs’ location
while maintaining the same parameter settings mentioned in Fig. 3 and Fig. 4.
In this figure, we demonstrate how the users are being served instantaneously
by the suitable access point (either UAV or nearest BS). Here, we can observe
that when UAVs are near to their respective initial and destination points at
$n=50$ and $n=150$, mostly the users located at the boundary region of the
target area are associated with the UAVs because they are near to the UAVs.
However, since the users located in the central region of the target area are
far away from the UAVs, those users can not achieve the required data rate
constraint. Hence most users are associated with the nearest BS, resulting in
low load balancing for data traffic offloading. On the other hand, at $n=100$,
all UAVs arrive at the central region of the target area. At these instant
locations, all UAVs can cover a wide region of the target area, and most users
associate with the UAVs instead of BS because they can easily achieve the
required data rate constraint. As of now, the distances between users and UAVs
are shorter resulting in high load balancing for data traffic offloading. From
this figure, we can say that during UAVs’ flight period, BS offloading
increases initially up to the highest level when all UAVs arrive at the
central region of the target area. Later when UAVs proceed toward their
respective destination, BS offloading decreases because the distances between
users and UAVs are greater for this situation. Thereby, the overall utility of
the UAVs can be maximized during their optimal trajectory. Fig. 4 also
validates this concept where we can observe that all UAVs aviate around the
central region of the target area for a certain amount of time to obtain
maximum instantaneous user association for efficient BS offloading.

###  V-C Performance Evaluation

In Fig. 6(a), the average UAV association consistently decreases with the
escalation of the data rate constraint, irrespective of the algorithm used.
Among these algorithms, distributed SARSA exhibits superior performance,
achieving optimal solutions with centralized training and execution.
Q-learning, with its partial environment observations, achieves a slightly
lower average UAV association compared to distributed SARSA. In contrast, the
meta-heuristic PSO algorithm, relying solely on instant UAV associations at
their current location for decision-making, leads to performance degradation,
resulting in a lower average UAV association. This figure highlights that
distributed SARSA enhances the average UAV association by $7.74\%$ and
$18.04\%$ compared to the benchmark Q-learning and PSO algorithms,
respectively.

(a) Average UAV association versus the data rate constraint for various
transmitting.

(b) Average UAV association versus the transmit power for various data rate
constraints.

(c) Average UAV association versus UAVs’ altitude for various channel
bandwidth allocations.

Figure 6: Performance comparison of average UAV association under variation of
different system parameters.

In Fig. 6(b), the average UAV association is depicted for different values of
the data rate constraint with respect to users’ transmitting power. The
average UAV association rises with increasing users’ transmitting power,
regardless of the algorithm employed. When users utilize higher power, they
achieve greater transmission rates. Consequently, more users associate with
UAVs during each time slot, irrespective of whether learning-based or meta-
heuristic algorithms are employed. This leads to increased BS offloading and
enhanced UAV utility. The benchmark algorithm encounters challenges in finding
the optimal policy. Therefore, distributed SARSA improves the average UAV
association by $3.67\%$ and $8.22\%$ compared to the Q-learning and PSO
algorithms respectively.

Fig. 6(c) illustrates the variation in average UAV association concerning UAV
flying altitude for different channel bandwidth allocations. It is evident
that the average UAV association experiences a slight decrease with increasing
UAV altitude. This decline can be attributed to the fact that as UAV altitude
rises, the Line of Sight (LoS) probability increases, leading to larger
distances between users and UAVs. Consequently, higher path loss and lower
channel gain are observed. Hence, there is a tradeoff between LoS probability
and path loss of the channel. Furthermore, with increased channel bandwidth
allocation, users attain higher transmission rates, resulting in more users
associating with UAVs. This, in turn, amplifies BS offloading and enhances UAV
utility. As observed previously, the PSO algorithm updates particle position
and velocity through random inertia weight sampling, making it challenging for
UAVs to plan efficiently for flying and data collection from ground users. In
contrast, learning-based algorithms such as distributed SARSA and Q-learning
leverage UAVs’ historical experiences from their respective Q-tables to make
informed decisions. Consequently, the performance gap between the meta-
heuristic algorithm and the learning-based policy is more pronounced, with the
proposed technique improving average UAV association by $8.21\%$ and $18.39\%$
compared to benchmark Q-learning and PSO algorithms, respectively.

##  VI Conclusions

In this study, we explored the efficacy of a cellular offloading system
employing multiple UAVs to address temporary overload situations in
terrestrial BSs caused by their limited spectrum capacity. The proposed
approach focuses on optimizing the utilization of UAVs to maximize the average
number of users associated with them. This is achieved by jointly optimizing
the trajectories of UAVs and user-association indicators under a specified
data rate constraint. Utilizing a finite-state Markov Decision Process (MDP)
model, we decomposed the original optimization problem into a Multi-Agent
Reinforcement Learning (MARL) framework. This transformation simplifies the
problem into multiple subproblems, each involving the optimization of a single
variable. We introduced a novel, low-complexity distributed SARSA algorithm
designed to find asymptotically optimal policies for multiple UAVs. In this
approach, each UAV functions as an independent agent, learning to make
decisions regarding its flight path and data collection based on partial and
time-varying observations. Extensive simulations were conducted to validate
the effectiveness of the proposed learning-based algorithm in comparison to
baseline Q-learning and Particle Swarm Optimization (PSO) algorithms. The
results demonstrated that distributed SARSA outperforms Q-learning and PSO by
improving average UAV association by $6.04\%$ and $14.93\%$, respectively,
even though it exhibits a slower convergence rate due to increased
computational complexity. Looking ahead, future work will extend this research
to UAV-assisted multi-access edge computing systems, incorporating
reconfigurable intelligent surfaces and employing more advanced offloading
schemes.

## References

  * [1] A. Mondal, D. Mishra, G. Prasad, G. C. Alexandropoulos, and A. Hossain, ”Reinforcement-learning-based UAV utility maximization for offloading cellular communication systems,” _IEEE International Conference Communications_ , Rome, Italy, 28 May – 1 June 2023, pp. 1–6.
  * [2] P. Chen, X. Luo, D. Guo, Y. Sun, J. Xie, Y. Zhao, and R. Zhou, “Secure task offloading for MEC-aided-UAV system,” _IEEE Trans. Intell. Veh._ , vol. 8, no. 5, pp. 3444–3457, May 2023.
  * [3] D. Yin, X. Yang, H. Yu, S. Chen, and C. Wang, “An air-to-ground relay communication planning method for UAVs swarm applications,” _IEEE Trans. Intell. Veh._ , vol. 8, no. 4, pp. 2983 - 2997, Apr. 2023.
  * [4] H. Chen, H. Kim, M. Ammous, G. Seco-Granados, G. C. Alexandropoulos, S. Valaee, and H. Wymeersch, ”RISs and sidelink communications in smart cities: The key to seamless localization and sensing,” _IEEE Commun. Mag._ , vol. 61, no. 8, pp. 140-146, Aug. 2023.
  * [5] A. Masaracchia, D. V. Huynh, G. C. Alexandropoulos, B. Canberk, O. A. Dobre, and T. Q. Duong, ”Towards the metaverse realization in 6G: Orchestration of RIS-enabled Smart wireless environments via digital twins,” _IEEE Internet Things Mag._ , to appear, 2023.
  * [6] W. Lu, Y. Ding, Y. Gao, S. Hu, Y. Wu, N. Zhao, and Y. Gong, “Resource and trajectory optimization for secure communications in dual unmanned aerial vehicle mobile edge computing systems,” _IEEE Trans. Ind. Inform._ , vol. 18, no. 4, pp. 2704–2713, Apr. 2022.
  * [7] J. G. Andrews, S. Buzzi, W. Choi, S. V. Hanly, A. Lozano, A. C. K. Soong, and J. C. Zhang, “What will 5G be?” _IEEE J. Sel. Areas Commun._ , vol. 32, no. 6, pp. 1065–1082, Jun. 2014.
  * [8] D. V. Huynh, T. D. Duy, L. D. Nguyen, M. T. Le, N. S. Vo, and T. Q. Duong, “Real-time optimized path planning and energy consumption for data collection in unmanned ariel vehicles-aided intelligent wireless sensing,” _IEEE Trans. Ind. Informal._ , vol. 18, no. 4, pp. 2753 – 2761, Apr. 2022.
  * [9] S. Ivic, “Motion control for autonomous heterogeneous multiagent area search in uncertain conditions,” _IEEE Trans. Cybern._ , vol. 52, no. 5, pp. 3123–3135, May 2022.
  * [10] Y. Zeng, J. Lyu, and R. Zhang, “Cellular-connected UAV: Potential, challenges, and promising technologies,” _IEEE Wireless Commun._ , vol. 26, no. 1, pp. 120–127, Feb. 2019.
  * [11] M. Alzenad, A. El-Keyi, F. Lagum, and H. Yanikomeroglu, “3-D placement of an unmanned aerial vehicle base station (UAV-BS) for energy-efficient maximal coverage,” _IEEE Wireless Commun. Lett._ , vol. 6, no. 4, pp. 434–437, Aug. 2017.
  * [12] X. Liu, Z. Li, N. Zhao, W. Meng, G. Gui, Y. Chen, and F. Adachi, “Transceiver design and multihop D2D for UAV IoT coverage in disasters,” _IEEE Internet Things J._ , vol. 6, no. 2, pp. 1803–1815, Apr. 2019.
  * [13] Y. Zeng, R. Zhang, and T. J. Lim, “Throughput maximization for UAV-enabled mobile relaying systems,” _IEEE Trans. Commun._ , vol. 64, no. 12, pp. 4983–4996, Dec. 2016.
  * [14] Y. Zeng and R. Zhang, “Energy-efficient UAV communication with trajectory optimization,” _IEEE Trans. Wireless Commun._ , vol. 16, no. 6, pp. 3747–3760, Jun. 2017.
  * [15] J. Li and Y. Han, “A traffic service scheme for delay minimization in multi-layer UAV networks,” _IEEE Trans. Veh. Technol._ , vol. 67, no. 6, pp. 5500–5504, Jun. 2018.
  * [16] Y. Liu, K. Xiong, Q. Ni, P. Fan, and K. B. Letaief, “UAV-assisted wireless powered cooperative mobile edge computing: Joint offloading, CPU control, and trajectory optimization,” _IEEE Internet Things J._ , vol. 7, no. 4, pp. 2777–2790, Apr. 2020.
  * [17] M. Dai, Z. Su, Q. Xu, and N. Zhang, “Vehicle assisted computing offloading for unmanned aerial vehicles in smart city,” _IEEE Trans. Intell. Transp. Sys._ , vol. 22, no. 3, pp. 1932–1944, Mar. 2021.
  * [18] B. Zhang, M. Wang, J. L. Yu, C. Guo, and Z. Han, “Joint 3-D position deployment and traffic offloading for caching and computing-enabled uav under asymmetric information,” _IEEE Internet Things J._ , vol. 10, no. 7, pp. 6312–6323, Apr. 2023.
  * [19] A. Bejaoui, K. Park and M. Alouini, ”A QoS-oriented trajectory optimization in swarming unmanned-aerial-vehicles communications”, _IEEE Wireless Commun. Lett._ , vol. 9, no. 6, pp. 791-794, 2020.
  * [20] M. Hua, Y. Wang, C. Li, Y. Huang, and L. Yang, “Energy-efficient optimization for UAV-aided cellular offloading,” _IEEE Wireless Commun. Lett._ , vol. 8, no.3, pp. 769–772, Jun. 2019.
  * [21] P. Lohan and D. Mishra, ”Utility-aware optimal resource allocation protocol for UAV-assisted small cells with heterogeneous coverage demands,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 2, pp. 1221-1236, Feb. 2020.
  * [22] V. Roberge, M. Tarbouchi, and G. Labonte, “Comparison of parallel genetic algorithm and particle swarm optimization for real-time uav path planning,” _IEEE Trans. Ind. Inform._ , vol. 9, no. 1, pp. 132–141, Feb. 2013.
  * [23] A. H. Sawalmeh, N. S. Othman, H. Shakhatreh, and A. Khreishah, “Wireless coverage for mobile users in dynamic environments using UAV,” _IEEE Access_ , vol. 7, pp. 126376 – 126390, Aug. 2019.
  * [24] G. C. Alexandropoulos, K. Stylianopoulos, C. Huang, C. Yuen, M. Bennis, and M. Debbah, ”Pervasive machine learning for smart radio environments enabled by reconfigurable intelligent surfaces,” _IEEE Proceedings_ , vol. 110, no. 9, pp. 1494–1525, Sept. 2022.
  * [25] Z. Kaleem, A. Ahmad, O. Chughtai, and J. J. P. C. Rodrigues, “Enhanced max-min rate of users in UAV-assisted emergency networks using reinforcement learning,” _IEEE Netw. Lett._ , vol. 4, no. 3, pp. 104 – 107, Sept. 2022.
  * [26] J. Cui, Y. Liu, and A. Nallanathan, “Multi-agent reinforcement learning-based resource allocation for UAV networks,” _IEEE Trans. Wireless Commun._ , vol. 19, no. 2, pp. 729–743, Feb. 2020.
  * [27] A. Mondal, D. Mishra, G. Prasad, and A. Hossain, “Joint optimization framework for minimization of device energy consumption in transmission rate constrained UAV-assisted IoT network,” _IEEE Internet Things J._ , vol. 9, no. 12, pp. 9591 – 9607, Nov. 2021.
  * [28] J. Hu, H. Zhang, and L. Song, “Reinforcement learning for decentralized trajectory design in cellular UAV networks with sense-and-send protocol”, _IEEE Internet Things J._ , vol. 6, no. 4, pp. 6177 – 6189, Aug 2019.
  * [29] J. Cui, Z. Ding, Y. Deng, A. Nallanathan, and L. Hanzo, “Adaptive UAV-trajectory optimization under quality of service constraints: a model-free solution,” _IEEE Access_ , vol. 8, pp. 112253 – 112265, Jun. 2020.
  * [30] B. Ahuja, D. Mishra, and R. Bose, ”Fair subcarrier allocation for securing OFDMA in IoT against full-duplex hybrid attacker,” _IEEE Trans. Inf. Forensics Security_ , vol. 16, pp. 2898-2911, Mar. 2021.
  * [31] Z. Wang, R. Liu, Q. Liu, J. S. Thompson, and M. Kadoch, ”Energy-efficient data collection and device positioning in UAV-assisted IoT,” _IEEE Internet Things J._ , vol. 7, no. 2, pp. 1122-1139, Feb. 2020.
  * [32] C. Zhan and Y. Zeng, “Aerial–ground cost tradeoff for multi-UAV-enabled data collection in wireless sensor networks,” IEEE Trans. Commun., vol. 68, no. 3, pp. 1937–1950, Mar. 2020.
  * [33] R. Ding, F. Gao, and X. S. Shen, ”3D UAV trajectory design and frequency band allocation for energy-efficient and fair communication: A deep reinforcement learning approach”, _IEEE Trans. Wireless Commun._ , vol. 19, no. 12, pp. 7796-7809, Dec. 2020.
  * [34] B. Ahuja, D. Mishra, and R. Bose, ”Optimal green hybrid attacks in secure IoT”, _IEEE Wireless Commun. Lett._ , vol. 9, no. 4, pp. 457-460, Apr. 2020.