# Hierarchical Reinforcement Learning for Swarm Confrontation with High
Uncertainty

Qizhen Wu, Kexin Liu, Lei Chen, _Member, IEEE_ , and Jinhu Lü, _Fellow, IEEE_
*This work was supported in part by the National Key Research and Development
Program of China under Grant 2022YFB3305600, and in part by the National
Natural Science Foundation of China under Grants 62141604, 62088101, and
62003015. (Corresponding author: Lei Chen.)Qizhen Wu, Kexin Liu, and Jinhu Lü
are with the School of Automation Science and Electrical Engineering, Beihang
University, Beijing 100191, China. (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS>jhlu@iss.ac.cn)Lei Chen is with the Advanced Research
Institute of Multidisciplinary Sciences and State Key Laboratory of CNS/ATM,
Beijing Institute of Technology, Beijing 100081, China. (e-mail:
<EMAIL_ADDRESS>
###### Abstract

In swarm robotics, confrontation including the pursuit–evasion game is a key
scenario. High uncertainty caused by unknown opponents’ strategies and dynamic
obstacles complicates the action space into a hybrid decision process.
Although the deep reinforcement learning method is significant for swarm
confrontation since it can handle various sizes, as an end–to–end
implementation, it cannot deal with the hybrid process. Here, we propose a
novel hierarchical reinforcement learning approach consisting of a target
allocation layer, a path planning layer, and the underlying dynamic
interaction mechanism between the two layers, which indicates the quantified
uncertainty. It decouples the hybrid process into discrete allocation and
continuous planning layers, with a probabilistic ensemble model to quantify
the uncertainty and regulate the interaction frequency adaptively.
Furthermore, to overcome the unstable training process introduced by the two
layers, we design an integration training method including pre–training and
cross–training, which enhances the training efficiency and stability.
Experiment results in both comparison and ablation studies validate the
effectiveness and generalization performance of our proposed approach.

###### Note to Practitioners

With artificial intelligence rapidly developing, robots will play a
significant role in the future. Especially, the swarm formed by many robots
holds promising potential in civil and military applications. Promoting the
swarm into games or battles is rather riveting. The reinforcement learning
method provides a plausible solution to realize the battle of robotic swarms.
There are still some issues that need to be addressed. On one hand, we focus
on the uncertainty caused by the battlefield nature and the environment which
limits our ability for the implementation of swarms. On the other hand, we
solve the problem that the decision process combined with commands and actions
is a hybrid system, which cannot be directly reflected in the confrontation of
swarms. Overall, our approaches throw light on artificial general intelligence
and also reveal a solution to interpretable intelligence.

###### Index Terms:

Swarm, robotic confrontation, deep reinforcement learning, decision
uncertainty, artificial intelligence.

##  I Introduction

With the emergence of artificial intelligence, robotics [1, 2] is gaining more
attention. Confrontation [3, 4] is a crucial application of robotic swarm,
where robots are expected to win through artificial intelligent
decision–making. Typical scenarios include pursuit–evasion [5] and
defense–attack [6] games. However, its intrinsic mechanism is an $NP$–hard
complex problem due to vast involving agents and strong conflict uncertainties
[7, 8, 9]. Traditional algorithms [10, 11, 3] are struggling with computation
complexities and resource costs as the increasing number of robots and
actions.

Deep reinforcement learning (DRL) [12] is a plausible solution to this
problem. It adopts an end–to–end framework to approach the optimal decision
instead of enormous iterations, leading to many accomplishments in racing [13]
and competition [14]. Driven by maximizing cumulative values in reward
functions, DRL optimizes the decision network to produce a desirable strategy.
In practice, however, complex problem solving [15] brings a new challenge for
DRL. Focusing on global goals instead of reasoning the problem results in a
sparse reward issue [16, 17] that limits the application of DRL.

To avoid constructing intrinsic rewards directly, many researchers employ
hierarchical reinforcement learning (HRL)[18], which decouples the complex
problem through a divide–and–conquer framework[19]. The upper layer in HRL
divides the timeline into several non–uniform sections each of which it
designs a unique reward for the lower layer to train, and, by doing this, the
global reward for the upper layer is maximized. Sectional rewards fill the
timeline leading to the sparse reward problem being solved. Therefore,
designing the unique rewards, also addressed as interaction mechanisms, is a
significant trick to HRL. As a pioneer work, [20] generates unique rewards
from the upper layer in the form of differentiable functions. It soon shows
great potential in dynamic multiple object traveling salesman problem when
[21] investigates the distributed system Ray belonged to UC Berkeley RISELab.
Nevertheless, its framework is totally direct from the upper to the lower.
This open–loop feature is inapplicable in many cases, where the performance of
the lower layer is not considered once the unique rewards are designed. For
the purpose of the close–loop feature, [22] introduces bi–direct layers
adjusting the strategy of the upper according to the performance of the lower.
In addition, it limits our ability to promote HRL only by manipulating the
lower layer under the command of the upper layer. Hence, [23] facilitates an
additional reward into the lower to achieve more goals besides unique rewards
from the upper. It throws light on a more flexible solution for HRL in other
practical problems.

Swarm confrontation, being a typical complex problem solving, naturally
consists of discrete and continuous spaces under an uncertain environment.
Illustratively, commands on the battlefield always exist in the form of
discrete decisions, while actions usually take place in continuous time.
Recent works [24, 25] combine commands and actions into multiple high–level
spaces. This method blurs the interpretability of the spaces inevitably
resulting in slowly converging algorithms for large–scale swarms.
Alternatively, it is not hard to reflect the swarm confrontation to
divide–and–conquer framework, where the commands are translated into target
allocation and the actions are addressed as path planning, from the artificial
intelligence perspective[10]. Wang et al. [26] make an interesting attempt for
the first time to introduce HRL into swarm confrontation. Inspired by the
method, [27] decomposes multi–aircraft formation air combat into high–level
strategy and sub–strategy, achieving favorable effects in confrontation among
a few robots. However, the fact that we cannot guarantee the stability of the
algorithms prevents us from building a bridge between HRL and swarm
confrontation. Others [28, 19] have already improved the stability of the
algorithm for HRL in a different scenario. They design an interactive training
strategy, including pre–training, intensive training, and alternate training,
to ensure the stability guaranteed. A prerequisite for this strategy is only
the lower layer pre–trained, while the training of the upper is limited by the
cumulative feedback from the lower. Thus we cannot directly implement it to
swarm confrontation for the environment uncertainty will make the global
optimization impossible.

Here, we propose a guaranteed stable HRL method, which induces quantified
uncertainty into an interaction mechanism linking the allocation and planning
layers, to solve the hybrid problem of swarm confrontation in various sizes
and environments. Firstly, we construct two–layer DRL networks to reflect
commands and actions into target allocation and path planning, respectively,
since the high uncertainty caused by the nature of the confrontation,
including variant opponents’ strategies and transient battlefield environment,
demands a hybrid, flexible, and robust intelligent algorithm. Secondly, the
mechanism, which is embedded with a probabilistic ensemble model [29]
quantifying the uncertainty, regulates the interaction frequency between the
two layers. The essence is the frequency is increased as the circumstance
becomes uncertain and dire. Thirdly, a novel integration training method
(ITM), consisting of pre–training and cross–training, ensures the stability of
HRL, in which, notably, we combine pre–trained and an improved model–based
value estimation (IMVE) [30] method together to fasten the convergent speed of
the upper in case of few samples given by the lower. Finally, extensive
experiments on different–size swarms verify that our approach outperforms the
baselines including non–learning approach and traditional DRL, and they also
demonstrate the necessity of adaptive frequency approach and ITM through
ablation studies. Plus, our method shows that a trained model under a small
scale holds favorable generalization in various scales of swarm confrontation.
The main contributions of this paper are summarized as follows.

  * •

We propose a novel HRL framework that enables multiple agents to intelligently
interact with the environment under high uncertainty, overcoming the obstacle
that traditional DRL cannot handle disturbing hybrid spaces fluently.

  * •

The adaptive interaction mechanism proposed in HRL eliminates the high
uncertainty caused by some special scenarios like intelligent confrontation
and the integration training method guarantees the whole system stable.

  * •

Our method solves the realization problem of swarm confrontation,
demonstrating a new way for artificial intelligence to be applied in both
civil and military scenes.

We organize the rest of the paper as follows. Section II introduces the
research related to our study. Section III presents the problem formulation of
our problem. Section IV presents our two–layer networks and guaranteed stable
HRL method. Section V describes the experiments of our method. Section VI
presents our conclusions.

##  II Related Works

As a key scenario of robotics, swarm confrontation is a combinatorial
optimization problem with a hybrid decision process and transient environment.
This section reviews the related works for swarm confrontation in terms of
various methods. We first introduce and analyze the traditionally relevant
expert system, game theory, and heuristic approaches, followed by a review of
DRL solving swarm confrontation. Moreover, we summarize the characteristics of
the existing solutions and further induce the hierarchical learning method for
the swarm confrontation problem.

The expert system method [10] approaches the system with a prior knowledge of
human experts and selects the strategies in the knowledge base by fuzzy
matching method. Wang et al.[31] develop an effective self–organized swarm
confrontation decision–making method consisting of task allocation and swarm
motion. The method relies on rules developed by an enormous number of human
experts and is unable to ensure the optimality of decisions in a complex swarm
confrontation environment. In game theory[11], the swarm confrontation problem
is frequently modeled as a differential game. Liu et al.[32] adopt the Nash
equilibrium seeking strategy to respond to agents in a dual–coalition
non–cooperative game. Game theory suffers from problems such as too many state
variables and complex differential equations, making it difficult to apply to
complex multi–agent environments. The heuristic approach [3] considers
modeling the swarm as biologically inspired networks to simulate the dynamics
of swarm confrontation. Liu et al.[33] propose a novel evolutionary
algorithm–based attack strategy with swarm robots, which has more potential to
solve large–scale confrontational problems. However, the simulation and test
require a lot of computing resources and time.

Without relying on a prior knowledge, DRL learns strategies by interacting
with the environment. As a result, it gains more attention in fields such as
game playing[34], natural language processing[35], and robotics[12]. Recently,
DRL is applied to swarm confrontation, where it learns rules from huge numbers
of problem instances rather than designing them manually. De et al.[36]
combine DRL with curriculum learning for pursuing an omnidirectional target
with multi–agent. To improve training efficiency and learning stability, Zhang
et al.[7] propose several knowledge enhancement mechanisms in a confined–space
confrontation mission. However, taking the single–agent DRL approach becomes
difficult faced with large–scale swarm confrontation scenarios. Therefore, Xia
et al.[8] propose an end–to–end multi–agent reinforcement learning to enable
agents to make decisions for cooperative target tracking. Qu et al.[37]
further provide an adversarial–evolutionary game training method and designed
obstacle avoidance scenarios in swarm confrontation.

Among the existing methods for solving the swarm confrontation problem, expert
system, game theory, and heuristic methods cannot be well applied to
large–scale problems. Expert system and game theory methods are limited by
prior knowledge and differential equations, respectively, and heuristic
algorithms are expensive in computational resources. As a result, the
performance of all three methods degrades significantly when the problem size
increases. DRL is a desirable alternative due to the ability to learn
strategies just by interacting with the environment. However, the direct use
of an end–to–end approach in swarm confrontation [24, 25], results in the
non–interpretability of the hybrid decision space, hindering the training of
DRL on large–scale swarms.

To deal with the above issues, the hierarchical learning method reflects the
swarm confrontation to divide-–and–-conquer framework, where the commands and
the actions are addressed as discrete and continue decision spaces,
respectively. Hou et al.[10] integrate the finite state machine and
event–condition–action frameworks to give a more interpretable solution. Wang
et al.[26] decompose the swarm confrontation problem into multiple tasks to
reduce the challenges of sparse reward learning. Kong et al.[38] employ the
goal–conditioned HRL framework with feedback and construct a dual–aircraft
formation air combat scenario. Next, Kong. [27] further extend the scenario to
multiple aircraft and propose to train the lower layer through a competitive
self–play approach. They make interesting attempts to introduce HRL into swarm
confrontation. Inspired by them, we design a guaranteed stable HRL method for
quantifying the uncertainty caused by unknown opponents’ strategies and moving
obstacles. It establishes a dynamic interaction mechanism between the upper
and lower layers, which has favorable potential for solving the realization
problem of swarm confrontation.

##  III Problem Formulation and Preliminaries

###  III-A Definition of Swarm Confrontation

Figure 1: Representation of the parameters involved in the pursuit–evasion
game.

This study considers the swarm confrontation as a pursuit–evasion game where
exists dynamic obstacles. There are multiple heterogeneous pursuers to jointly
guard the preset target point. They need to work together to capture the same
number of evaders as soon as possible while avoiding collisions with obstacles
and neighbors. Evaders need to get to the preset target point as quickly as
possible without being caught by pursuers, as shown in Fig.1. We use blue and
red agents to denote pursuers and evaders, respectively. $D_{1}$, $D_{2}$, and
$D_{3}$ denote the length and width of the battlefield area and the
straight–line distance between the starting areas of both sides, respectively.
Let position and velocity vectors in two dimensions be denoted by $p$ and $v$,
respectively. Pursuers and evaders cannot exceed the boundaries of the
scenario and the maximum dynamic constraints, which can be bounded as

$\displaystyle-\frac{D_{1}}{2}\leq p_{x}\leq\frac{D_{1}}{2},$
$\displaystyle-\frac{D_{2}}{2}\leq p_{y}\leq\frac{D_{2}}{2},$
$\displaystyle\lVert v\rVert\leq v_{max},$ (1)

where $\lVert\cdot\rVert$ denotes the Euclidean norm. $p_{x}$ and $p_{y}$
denote the position of the horizontal and vertical coordinates, respectively.
$v_{max}$ denotes the maximum velocity. Let
$U_{p}=\left\\{u_{p,i}|i=1,...,I\right\\}$ and
$U_{e}=\left\\{u_{e,j}|j=1,...,J\right\\}$ denote a swarm of pursuers and
evaders, respectively. Both pursuers and evaders should avoid dynamic
obstacles $O=\left\\{o_{k}|k=1,...,K\right\\}$. For any pursuer
$u_{p,i}=\left(p,v,\rho_{c},v_{max}\right)$, $\rho_{c}$ denotes the capture
radius. For any evader $u_{e,j}=\left(p,v,v_{max}\right)$, its maximum
velocity is greater than the pursuers. We consider $\rho_{u}$ and $\rho_{o}$
as the radius of agents and obstacles, respectively. In this paper, we design
the HRL method for pursuers, while evaders use the expert system approach
[10]. The HRL method reflects the commands and actions of the pursuit–evasion
game into target allocation and path planning, respectively, through the
divide–and–conquer framework approach. We can use $x_{ij}$ to denote the
allocation variable which represents whether to allocate $u_{p,i}$ to
$u_{e,j}$. It yields that

$\begin{array}[]{c}x_{ij}=\left\\{\begin{array}[]{c}1,\ \text{if\ }u_{p,i}\
\text{is\ allocated\ to\ }u_{e,j}\\\ 0,\ \text{otherwise}\\\
\end{array}\right.,\end{array}$ (2)

where $\left[x_{ij}\right],\ i\in I,\ j\in J$ denotes the allocation matrix
for all pursuers. Subsequently, pursuers chase the assigned target through
real–time path planning. Throughout the process, target allocation and path
planning are dynamically alternated. For pursuers and evaders, we design the
rules as follows:

  * 1)

Each pursuer is allowed to select only one evader, and one evader can be
assigned to several pursuers.

  * 2)

If an evader enters the capture radius of one of the pursuers, it is being
captured.

  * 3)

Both evaders and pursuers that satisfy condition 2) cannot continue moving.

  * 4)

The successful condition of pursuers: evaders do not reach the preset target
point within the specified time or more than half of evaders are captured.

  * 5)

The successful condition of evaders: more than half of evaders can reach the
predetermined target point within the time limit without being captured by
pursuers.

###  III-B Markov Decision Process

Let $\mathbb{R}$ denote the set of real numbers. $\mathbb{E}$ denotes the
mathematical expectation. We can model reinforcement learning by a Markov
decision process (MDP). We represent the MDP as a five–tuple
$\left(S,A,P,R,\gamma\right)$. $S$ and $A$ denote the state of the environment
and action of the agent, respectively. $P:S\times A\rightarrow S$ denotes the
state transition function, $R:S\times A\rightarrow\mathbb{R}$ denotes the
reward function, and $\gamma$ denotes the discount factor.

MDP is the case when there is only a single agent or when the system is
considered a centralized agent. We can describe a fully cooperative
multi–agent reinforcement learning task as a decentralized partially
observable Markov decision process (Dec–POMDP). We represent Dec–POMDP as a
six–tuple $\left(S,A,P,R,Z,\gamma\right)$, where the state space $S$, state
transition function $P$, reward function $R$ and the discount factor $\gamma$
have the same denotation as the MDP. For each agent $i$, $a^{i}\in A$ and
$a=\left[a^{1},\cdots,a^{I}\right]$ denote the action of each agent and the
set of the joint actions of all agents, respectively. $z^{i}\in Z$ and
$z=\left[z^{1},\cdots,z^{I}\right]$ denote the observation of each agent and
the set of the joint observations of all agents, respectively.
$\varGamma^{i}=\left(z_{0}^{i},a_{0}^{i},z_{1}^{i},a_{1}^{i},...\right)$ is
the trajectory of each agent interacting with the environment under the
strategy, where $a_{t}^{i}\sim\pi^{i}\left(z_{t}^{i}\right)$ and
$z_{t+1}^{i}\sim P\left(z_{t}^{i},a_{t}^{i}\right)$ denote the selected action
and reaching observation at each decision step $t$, respectively. The purpose
of each agent is to optimize the policy network $\pi^{i}$ such that the
cumulative rewards
$\mathbb{E}_{\varGamma^{i}\sim\pi^{i}}\left[\sum_{t=1}^{\infty}{\gamma^{t}r_{t}}\right],r_{t}\sim
R$ is maximized under the policy.

##  IV Main Results

In this section, we introduce the guaranteed stable HRL method for solving the
swarm confrontation problem in the dynamic obstacles environment. In the upper
layer, it constructs an MDP model and designs a centralized deep Q–learning
(DQN) algorithm for the target allocation. In the lower layer, it establishes
a Dec–POMDP model and proposes a multi–agent deep deterministic policy
gradient (MADDPG) algorithm for path planning. Then, the method feeds the
cumulative rewards from the lower to the upper, and adopts a probabilistic
ensemble network to quantify the uncertainty caused by unknown evaders’
strategies and moving obstacles. Based on the uncertainty quantification, we
use an adaptive truncation method to optimize the interaction frequency
between the two layers. In addition, we employ an improved model–based value
estimation method to enhance the sample utilization in the upper layer which
has fewer samples. Afterward, we design an integration training method
including pre–training and cross–training to enhance the training efficiency
and stability of our approach.

###  IV-A Upper Layer for Target Allocation

  * 1)

Markov Decision Process. The procedure of the target allocation in the upper
layer can be deemed as a sequential decision–making process, where a pursuer
will be assigned for each evader. We cast such a process as an MDP which
includes state space $S$, action space $A$, reward $R$, and state transition
$P$. The detailed definition of our MDP is stated as follows.

  * $\bullet$

State. The state mainly consists of the current allocation of all pursuers
$\left[x_{ij}\right]$ as well as the information of pursuer $i$ that currently
needs to be allocated. It can be given as

$\displaystyle s\ =\
\left(\left[x_{ij}\right],p_{i},v_{i},\rho_{c,i},v_{max,i}\right).$ (3)

  * $\bullet$

Action. The action consists of the information of the selected evader, which
is

$\displaystyle a=\left(p_{j},v_{j},v_{max,j}\right).$ (4)

  * $\bullet$

Reward. Based on the critical model of the target allocation proposed in [10],
we get the one–step reward

$\displaystyle r=f\left(u_{p,i},u_{e,j}\right),$ (5)

where $f(\cdot)$ denotes the critical model with allocating $u_{e,j}$ to
$u_{p,i}$.

  * $\bullet$

State transition. After pursuer $i$ selects evader $j$, $x_{ij}$ becomes one,
and it is the turn of pursuer $i+1$ for target allocation.

  * 2)

Training method. Combining the above MDP settings, we adopt double DQN for
training on target allocation. The method estimates the optimal state–action
value function $Q^{*}:S\times A\rightarrow\mathbb{R}$ through a parameterized
neural network $Q_{\theta}\left(s_{t},a_{t}\right)\approx
Q^{*}\left(s_{t},a_{t}\right)=\mathbb{E}\left[R\left(s_{t},a_{t}\right)+\gamma\max
Q^{*}\left(s_{t+1},a_{t+1}\right)\right],\forall s_{t}\in S$. The subscript
$\theta$ is the weighting factor of the neural network. For $\gamma\approx 1$,
$Q^{*}$ estimates the discounted returns of the optimal strategy over an
infinite range. The method approximates $Q^{*}$ by $Q_{\theta}$ and the loss
function is set in the following form:

$\begin{array}[]{c}L_{\theta}=\mathbb{E}_{\left(s_{t},a_{t}\right)\sim\mathfrak{D}}\lVert
Q_{\theta}\left(s_{t},a_{t}\right)-y\rVert^{2},\end{array}$ (6)

where $y=R\left(s_{t},a_{t}\right)+\gamma\max
Q_{\theta^{-}}\left(s_{t+1},a_{t+1}\right)$ is the $Q$–target. The subscript
$\theta^{-}$ is a slow–moving online average that avoids overestimation of
$Q^{*}$. At each iteration, it is updated with the following rule:

$\begin{array}[]{c}\theta_{t+1}^{-}\leftarrow\left(1-\zeta\right)\theta_{t}^{-}+\zeta\theta_{t},\end{array}$
(7)

where $\zeta\in\left[0,1\right)$ is a constant factor. $\mathfrak{D}$ is a
replay buffer that iteratively grows as data are updated. We use the same DQN
network with a forward inference structure as [39], thus decoupling the
network from the size of the problem, which is similar to the critic network
in deep deterministic policy gradient (DDPG). Based on centralized DQN, the
pursuers maximize the cumulative rewards in (5) with a cooperative approach
for optimal target allocation.

###  IV-B Lower Layer for Path Planning

  * 1)

Decentralized Partially Observable Markov Decision Process. Based on the
allocation results of the upper layer, each pursuer needs to plan a route to
chase the assigned evader and avoid collisions. We model this process as a
Dec–POMDP, including the state space $S$, observation space $Z$, action space
$A$, reward $R$, and state transition $P$:

  * $\bullet$

State. The global state space includes information about all pursuers and
evaders. It can be described as

$\displaystyle s=\left(U_{P},U_{e}\right),$ (8)

  * $\bullet$

Observation. The local observation of a pursuer contains the information of
the allocated evader, its nearest neighbor and obstacle. It yields that

$\displaystyle
z=\left(p_{i},p_{j},p_{i}^{n},p_{k},v_{i},v_{j},v_{i}^{n},v_{k}\right),$ (9)

where $p_{i}^{n}$ and $v_{i}^{n}$ are the position and velocity of the nearest
neighbor of pursuer $i$.

  * $\bullet$

Action. The action consists of the velocity increment $\lVert\delta v\rVert$
and yaw $\psi$ of each UAV, which is denoted as

$\displaystyle a=\left(\lVert\delta v\rVert,\psi\right).$ (10)

  * $\bullet$

Reward. To intercept the allocated evader, pursuer $i$ receives an intrinsic
reward from the upper layer during path planning. The intrinsic reward can be
described as

$\displaystyle r_{int}=\left\\{\begin{matrix}\displaystyle-\frac{\lVert
p_{i}-p_{j}\rVert}{\rho_{c,i}}+r_{a}&\lVert p_{i}-p_{j}\rVert<\rho_{c,i}\\\
\displaystyle-\frac{\lVert p_{i}-p_{j}\rVert}{\rho_{c,i}}&\text{otherwise}\\\
\end{matrix}\right..$ (11)

In path planning, pursuers need to avoid collisions with their neighbors and
obstacles while chasing their allocated targets. The avoidance reward is set
in the following form:

$\displaystyle r_{avo}=r_{avo,1}+r_{avo,2}.$ (12)

If pursuer $i$ enters the threat zone of its nearest obstacle ($\lVert
p_{i}-p_{k}\rVert<\rho_{u}+\rho_{o}+d_{thr}$), there is

$\displaystyle r_{avo,1}=\frac{\lVert
p_{i}-p_{k}\rVert-\left(\rho_{u}+\rho_{o}+d_{thr}\right)}{\left(\rho_{u}+\rho_{o}+d_{thr}\right)}-r_{b},$
(13)

otherwise, $r_{avo,1}=0$. And if pursuer $i$ enters the threat zone of its
nearest neighbor ($2\rho_{u}<\lVert p_{i}-p_{i}^{n}\rVert<2\rho_{u}+d_{thr}$),
there is

$\displaystyle r_{avo,2}=\frac{\lVert
p_{i}-p_{i}^{n}\rVert-\left(2\rho_{u}+d_{thr}\right)}{\left(2\rho_{u}+d_{thr}\right)}-r_{c},$
(14)

otherwise, $r_{avo,2}=0$. $r_{a},r_{b},r_{c}$ are constant rewards. We set a
threat distance $d_{thr}$ to avoid collisions between pursuer $i$ with its
neighbors and obstacles. The total reward for path planning is a linear
operation consisting of the intrinsic and avoidance rewards, which is
calculated as

$\displaystyle r_{path}=\omega_{1}r_{int}+\omega_{2}r_{avo}.$ (15)

  * $\bullet$

State transition. Based on the current state and decisions, we can calculate
the position at the next moment through the first–order dynamics model

$\displaystyle p_{x,t+1}=p_{x,t}+\delta t\lVert\delta v\rVert\cos\psi,$
$\displaystyle p_{y,t+1}=p_{y,t}+\delta t\lVert\delta v\rVert\sin\psi.$ (16)

  * 2)

Training method. To enable pursuers to make decisions based on local
observations while realizing collaboration with each other to accomplish
interception, we use the MADDPG algorithm, which is a centralized training
with decentralized execution method. It designs a separate critic network
$Q_{\theta}^{i}\left(z_{t},a_{t}\right)$ for each agent, which is updated
similarly to (6) for double DQN as follows:

$\begin{array}[]{c}L_{\theta}^{i}=\mathbb{E}_{\left(z_{t},a_{t}\right)\sim\mathfrak{B}}\lVert
Q_{\theta}^{i}\left(z_{t},a_{t}\right)-y^{i}\rVert^{2},\end{array}$ (17)

where $y^{i}=R^{i}\left(z_{t},a_{t}\right)+\gamma\max
Q_{\theta^{-}}^{i}\left(z_{t+1},a_{t+1}\right)$. In addition, each agent holds
a policy network $\pi_{\beta}^{i}$ which has the following loss function:

$\begin{array}[]{c}L_{\beta}^{i}=-\mathbb{E}_{\left(z_{t},a_{t}\right)\sim\mathfrak{D}}\left[Q_{\theta}^{i}\left(z_{t},a_{t}\right)\right].\end{array}$
(18)

Based on MADDPG, the pursuers maximize the cumulative rewards in (15) by
collaborating while autonomous path planning.

Figure 2: Structure of the two–layer networks under swarm confrontation.

###  IV-C Hierarchical Network Interaction Method

This study decouples target allocation and path planning into a two–layer
networks, and unifies them into a dynamic cyclic process. After $H$ time steps
in path planning, we need to redo the target allocation based on the current
state, where interaction step $H$ is a variable related to the current state
$s_{t}$ and allocation $a_{t}$. In this dynamic process, the upper layer
allocates targets and provides an intrinsic reward to the lower layer, which
chases the assigned targets while avoiding obstacles through real–time path
planning. To quantify the uncertainty including variant opponents’ strategies
and transient battlefield environment, we construct a virtual environment
model $\mathcal{M}_{\phi}$ that incorporates both state transition and reward
function, which is expressed as

$\displaystyle\hat{s}_{t+H},\hat{r}_{t}\leftarrow\mathcal{M}_{\phi}\left(s_{t},a_{t}\right),$
(19)

where $\hat{s}_{t+H},\hat{r}_{t}$ denote the predicted value of $s_{t+H}$ and
$r_{t}$ with the environment model, respectively. We use an ensemble neural
network $(m_{\phi}^{1},...,m_{\phi}^{B})$ proposed in [29], which can be used
to quantify the epistemic uncertainty and aleatoric uncertainty in the
environment. Epistemic uncertainty results from the lack of sufficient
training data and aleatoric uncertainty refers to the unknown enemies’
strategies and moving obstacles in this study. It takes the state–action pair
as input and outputs Gaussian distribution $\mathcal{N}$ of the next state and
reward. The model $m_{\phi}^{b}$ can be expressed in the following form:

$\displaystyle m_{\phi}^{b}\left(s_{t+H},r_{t}\mid
s_{t},a_{t}\right)=\mathcal{N}\left(\mu_{\phi}^{b}\left(s_{t},a_{t}\right),\sigma_{\phi}^{b}\left(s_{t},a_{t}\right)\right),$
(20)

where $\mu$ and $\sigma$ represent the mean and variance of the Gaussian
distribution, respectively. This transition dynamics model is trained to
maximize the expected likelihood

$\displaystyle\displaystyle
L_{\phi}^{b}=\mathbb{E}_{\left(s_{t},a_{t}\right)\sim\mathcal{D}}\frac{1}{\lVert\mathcal{D}\rVert}\cdot\left[\frac{\log\sigma_{m_{\psi}^{b}}}{2}+\frac{\left(d_{t}-\mu_{m_{\psi}^{b}}\right)^{2}}{2\sigma_{m_{\psi}^{b}}}\right],$
(21)

where $d_{t}$ represents the model outputs. We omit the inputs
$\left(s_{t},a_{t}\right)$ of $\mu_{m_{\psi}^{b}}$ and $\sigma_{m_{\psi}^{b}}$
for brevity. Then, we employ the outputs of sub–models to denote the mean and
variance of the ensemble model $\mathcal{M}_{\phi}$, which are calculated as

$\displaystyle\mu_{\mathcal{M}_{\phi}}=$
$\displaystyle\frac{1}{B}\sum_{b=1}^{B}\mu_{m_{\psi}^{b}},$
$\displaystyle\sigma_{\mathcal{M}_{\phi}}^{2}=$
$\displaystyle\frac{1}{B}\left[\sum_{b=1}^{B}\left(\sigma_{m_{\psi}^{b}}^{2}+\mu_{m_{\psi}^{b}}^{2}\right)-\mu_{\mathcal{M}_{\phi}}^{2}\right].$
(22)

The uncertainty of $\mathcal{M}_{\phi}$ can be set to the variance of the
ensemble model. It is denoted as

$\displaystyle\hat{V}\left(s_{t},a_{t}\right)=\sigma_{\mathcal{M}_{\phi}}^{2}\left(s_{t},a_{t}\right).$
(23)

Instead of the conventional fixed–step or infinity iteration method, we adopt
an adaptive truncation approach, which calculates the prospective value of $H$
by the following linear operation:

$\displaystyle
H\left(s_{t},a_{t}\right)=\lfloor-\omega_{5}\hat{V}\left(s_{t},a_{t}\right)+H_{base}\rfloor,$
(24)

where $\omega_{5}$ is the weighting factor and $H\left(s_{t},a_{t}\right)$ is
an integer limited in $\left[H_{min},H_{max}\right]$. Subscripts $base$,
$min$, and $max$ are the settled based, minimum, and maximum values,
respectively. $\lfloor x\rfloor=\max\left\\{m\in\mathbb{Z}|m\leqslant
x\right\\}$, where $x\in\mathbb{R}$ and $\mathbb{Z}$ denotes the set of
integers. In [40], it is mentioned that aleatoric uncertainty cannot be
reduced with training, but we quantify the uncertainty to adjust the
interaction frequency adaptively. When uncertainty
$\hat{V}\left(s_{t},a_{t}\right)$ is higher, $H$ is smaller, indicating the
need for more frequent target allocation by the upper layer. As the model
$\mathcal{M}_{\phi}$ fits the environment, the epistemic uncertainty
decreases, as well as the frequency of target allocation.

In addition, we feed the cumulative rewards to the upper after the lower
executes $H$ time steps, as shown in Fig. 2. The upper layer linearly weights
the cumulative rewards in (15) and the static allocation reward in (5) as the
final reward, which can be denoted as

$\displaystyle r_{total}=\omega_{3}r_{allo}+\omega_{4}r_{path}.$ (25)

However, samples are greatly reduced since the effect of a single allocation
in the upper layer can only be obtained from the feedback of the lower layer
planning after $H$ steps. Here, we employ an improved model–based value
expansion (IMVE) method to improve the sample utilization of the upper layer.
The method performs $N$–step value estimation based on the real environment
state and allows $Q_{\theta}$ of $N$ steps to converge to $Q^{*}$. Similar to
$H\left(s_{t},a_{t}\right)$, $N\left(s_{t},a_{t}\right)$ is affect by the
uncertainty quantified by the model $\mathcal{M}_{\phi}$. We can calculate the
prospective length of $N$ in the following form:

$\displaystyle
N\left(s_{t},a_{t}\right)=\lfloor-\omega_{6}\hat{V}\left(s_{t},a_{t}\right)+N_{base}\rfloor,$
(26)

where $N\left(s_{t},a_{t}\right)$ is an integer limited in
$\left[0,N_{max}\right]$. The goal of policy in double DQN is to

Figure 3: Framework of our method and IMVE.

maximize the long–term cumulative rewards for all future moments, which can be
expressed as

$\displaystyle\pi_{1}\left(s_{t}\right)=~{}\underset{a_{t}}{\arg\max}~{}\mathbb{E}\left[\sum_{k=t}^{\infty}{\gamma^{k}R\left(s_{k},a_{k}\right)}\right].$
(27)

We reduce the prediction interval from infinity to a visual step $N$, and
replace the reward $R\left(s_{k},a_{k}\right)$ with the cumulative rewards
$\sum_{i=k}^{\infty}{\gamma^{i}r_{i}}$ in (27). The strategy of IMVE can be
described in the following form:

$\begin{array}[]{c}\pi_{2}\left(s_{t}\right)=\underset{a_{t:t+N}}{\arg\max}~{}\mathbb{E}\left[\sum\limits_{k=t}^{t+N}{\gamma^{k}\left(\sum\limits_{i=k}^{\infty}{\gamma^{i}r_{i}}\right)}\right].\end{array}$
(28)

It produces a local optimal solution by performing predictive control based on
the single moment $t$. Through rolling iterations at different times, it
generates multiple local optimal solutions and calculates the optimal value.
The use of cumulative rewards compensates for the lack of the terminal reward.
IMVE improves the sample utilization and training efficiency by performing
$N$–step value estimation and convergence, the loss function in (6) is
improved as follows:

$\begin{array}[]{c}L_{\theta}=\mathbb{E}_{\left(s_{t},a_{t}\right)\sim\mathfrak{D}}\sum\limits_{n=0}^{N-1}{\hat{\omega}\lVert
Q_{\theta}\left(\hat{s}_{t+H_{n}},\hat{a}_{t+H_{n}}\right)-y_{t+H_{n}}\rVert^{2}},\end{array}$
(29)

where $H_{n}$ is defined in the following recursive form:

$\displaystyle H_{n}=H\left(s_{t+H_{n-1}},a_{t+H_{n-1}}\right)+H_{n-1},$ (30)

where $H_{0}=0$. The $Q$–target is modified as follows:

$\displaystyle\displaystyle y_{t+H_{n}}=~{}$
$\displaystyle\sum\limits_{i=n}^{N-1}\gamma^{i-n}~{}\hat{r}_{t+i}$
$\displaystyle+\gamma^{N-n}\max
Q_{\theta^{-}}\left(s_{t+H_{N}},a_{t+H_{N}}\right).$ (31)

In (29), it introduces a discount weight $\hat{\omega}$, which is related to
the uncertainty of the model ${M}_{\phi}$ with respect to the sample
$\left(\hat{s},\hat{a}\right)$ produced. $\hat{\omega}$ is assigned as
follows:

$\displaystyle\hat{\omega}\left(\hat{s}_{t},\hat{a}_{t}\right)=-\omega_{7}\hat{V}\left(\hat{s}_{t},\hat{a}_{t}\right)+\hat{\omega}_{base},$
(32)

where $\hat{\omega}\left(\hat{s}_{t},\hat{a}_{t}\right)$ is limited in
$\left[\hat{\omega}_{min},1\right]$. By constructing the environment model
$M_{\phi}$, we can quantify the epistemic uncertainty and aleatoric
uncertainty, thus allowing $H$, $N$, and $\hat{\omega}$ to adjust adaptively.
Moreover, it allows us to improve the sample utilization of the upper layer
based on IMVE. The framework of our method is shown in Fig. 3.

###  IV-D Integration Training Method

Within the HRL, we design the upper layer and lower layer for target
allocation and path planning, respectively. The upper layer assigns targets
and intrinsic rewards to the lower layer, and the cumulative rewards of the
lower are fed to the upper after $H$ time steps. To deal with the strong
correlation between the two layers, we propose the integration training method
(ITM) consisting of pre–training and cross–training. The training framework is
shown in Algorithm 1.

Algorithm 1 Integration Training Method

0: the number of upper layer pre-training episodes $E_{p,u}$; the number of
lower layer pre-training episodes $E_{p,l}$; the number of upper layer
training steps $T_{u}$; the number of lower layer training steps $T_{l}$; the
number of cross-training episodes $E_{c}$;

0: the training datasets of the pre-training and cross-training processes; the
parameters of networks in the upper layer $Q_{\theta_{u}}$, lower layer
$Q^{i}_{\theta_{l}},\pi^{i}_{\beta_{l}}$, and Model $\mathcal{M}_{\phi}$;

1: for all $e\ =\ 1\rightarrow E_{p,u}$ do

2: for all $t\ =\ 1\rightarrow T_{u}$ do

3: $r_{u}\leftarrow$ Equ.(5); $\triangleright$ static allocation reward

4: $L_{u}\leftarrow$ Equ.(6);

5: Refresh network $Q_{\theta_{u}}$; $\triangleright$ gradient-descent

6: end for

7: end for

8: for all $e\ =\ 1\rightarrow E_{p,l}$ do

9: for all $t\ =\ 1\rightarrow T_{l}$ do

10: $r_{l}\leftarrow$ Equ.(15); $\triangleright$ path planning reward

11: $L_{l}\leftarrow$ Equ.(17)–(18);

12: Refresh networks $Q^{i}_{\theta_{l}},\pi^{i}_{\beta_{l}}$;

13: end for

14: end for

15: for all $e\ =\ 1\rightarrow E_{c}$ do

16: $t_{0}\leftarrow 1$, $H\leftarrow$ Equ.(25) $\triangleright$ initialize
$H$

17: for all $t\ =\ 1\rightarrow T_{l}$ do

18: $r_{l}\leftarrow$ Equ.(15);

19: $L_{l}\leftarrow$ Equ.(17)–(18);

20: if $t=t_{0}+H$ then

21: $r_{u}\leftarrow$ Equ.(26); $\triangleright$ total reward

22: $L_{u}\leftarrow$ Equ.(6);

23: Refresh networks $Q_{\theta_{u}}$ and $\mathcal{M}_{\phi}$;

24: $t_{0}\leftarrow t$, $H\leftarrow$ Equ.(25) $\triangleright$ refresh $H$

25: end if

26: Refresh networks $Q^{i}_{\theta_{l}},\pi^{i}_{\beta_{l}}$;

27: end for

28: end for

At the beginning of the ITM, we construct the pre–training phase for the upper
layer and lower layer for $E_{p,u}$ and $E_{p,l}$ episodes, respectively. This
phase allows the upper layer to learn a static allocation strategy and the
lower layer to train an initial path planning policy, which supports the
subsequent training phase. After the pre–training phase, we cross–train the
two–layer networks for $E_{c}$ episodes. Since the value of $H$ keeps changing
according to the state $s$ and allocation results $a$, we have to keep it
refreshed. Also, the model $M_{\phi}$ is keeping updating at the same time in
this phase.

Based on this method, we can effectively utilize a large amount of data to
learn the initial network in pre–training, thus speeding up the learning
process. In addition, it can avoid training instability due to the
interactions between the two layers in cross–training.

##  V Experiments

In this section, extensive experiments are conducted to evaluate the
performance of our HRL method for solving the swarm confrontation problem in
different sizes. In comparison experiments, we adopt various baselines
including the expert system, game theory, heuristic, and traditional DRL
algorithms. We verify the influence of adaptive frequency approach and ITM in
ablation studies. Moreover, we apply the model trained under a small size to
solve larger ones to investigate the generalization of our method.

TABLE I: The Hyperparameters of upper layer and lower layer. Parameter |  Upper layer |  Lower layer
---|---|---
Learning rate $\alpha$ |  $10^{-4}$ |  $10^{-3}$
Discount factor $\gamma$ |  0.95 |  0.99
Refresh factor $\zeta$ |  $10^{-2}$ |  $10^{-2}$
Batch size $\lVert\mathcal{D}\rVert$ |  120 |  1256
Optimizer |  Adam |  Adam
Figure 4: Learning curves of the pre–training for upper layer and lower layer.

###  V-A Setting Up

Figure 5: Learning curves of our method and baselines in different–size swarms. TABLE II: Experiment Results of Our Method and Baselines in Different–Size Swarms. Method | V10 | V15 | V20
---|---|---|---
Re. | Ti.(s) | W.R.(%) | Re. | Ti.(s) | W.R.(%) | Re. | Ti.(s) | W.R.(%)
Expert system | -1521 | 8.26 | 86 | -2603 | 8.89 | 79 | -3610 | 9.67 | 72
Game theory | -1816 | 4.39 | 69 | -2809 | 7.71 | 72 | -3804 | 10.43 | 68
Heuristic | -1564 | 6.45 | 85 | -2435 | 13.58 | 83 | -3302 | 25.30 | 80
DRL | -1703 |  0.49 | 77 | -2847 |  0.73 | 70 | -3786 |  1.06 | 69
UQ-HRL/IMVE | -1182 | 0.86 | 93 |  -2091 | 1.20 | 90 | -3078 | 1.87 | 86
UQ-HRL |  -1177 | 0.87 | 94 | -2093 | 1.22 | 90 |  -3071 | 1.87 | 87

Before analyzing the comparative results, we first introduce the detailed
settings of simulations. Following the convention in [10, 25, 37], we generate
the starting locations of pursuers and evaders in the rectangular area
($D_{1}=40m,D_{2}=20m,D_{3}=30m$). The target point of evaders is behind the
pursuers. Three scenarios including ten pursuers versus ten evaders (termed as
V$10$), fifteen pursuers versus fifteen evaders (termed as V$15$), and twenty
pursuers versus twenty evaders (termed as V$20$) are considered in our
experiment, all in the presence of four moving obstacles. In each scenario, we
set up five different abilities of pursuers and evaders. The capture radius of
pursuers $\rho_{c}$ is equalized from $0.6m$ to $1m$. The maximum velocities
of pursuers are all set to $0.5m/s$. The maximum velocities of evaders are
equalized from $0.6m/s$ to $1m/s$. The radius of the agents and obstacles are
$0.2m$ and $0.5m$, respectively.

For algorithm training, we pre–train the upper layer and lower layer for
$E_{p,u}=300$ and $E_{p,l}=20$ episodes in $100$ randomly generated instances,
respectively. The training steps of upper layer $T_{u}$ are equal to the
number of pursuers, and the training steps of lower layer $T_{l}=300$. Then,
the cross–training is adopted for $E_{c}=60$ episodes in the generated
instances above. In this way, we can enhance the training efficiency and
stability of the proposed method. We list all the hyperparameters in Table I
to demonstrate the details of our algorithm.

###  V-B Learning Performance in Pre–training

We conduct these simulations on a server with a Windows 10 operating system,
Intel Core i7–11700 CPU, 16–GB memory, and Radeon 520 GPU. All simulation
programs are developed based on Python 3.7 and PyCharm 2022.2.3 compiler. The
learning curves for each scenario of the upper layer and lower layer during
the pre–training process are shown in Fig. 4. The horizontal axis refers to
the number of episodes. The vertical axis of target allocation and path
planning refers to the episode returns calculated by (5) and (15),
respectively. To plot experimental curves, we adopt solid curves to depict the
mean of all instances and shaded regions corresponding to standard deviation
among instances. We can observe that the completely randomized experience
replay can lead to performance fluctuations in the initial stage due to the
use of the centralized algorithm in the upper layer. Since the rewards of
target allocation and path planning are related to the number of agents, the
episode returns gradually decrease as the problem size of swarm confrontation
increases. The curves for both upper and lower converge stably in different
sizes, suggesting that they have learned valid policies. Based on the
pre–trained upper layer and lower layer, we can cross–train the two layers and
compare our method with other baselines.

###  V-C Comparison Analysis in Cross–Training

In the cross–training process, we employ the proposed method to improve the
performance of the two layers. We compare the method with the baselines
including the expert system, game theory, heuristic approach, and traditional
DRL. IMVE adopts a rolling optimization approach to enhance the sample
utilization of the upper layer. To investigate the influence of IMVE, we
further conduct an ablation study with HRL absent on the IMVE method. The
baselines are briefly introduced as follows.

  * 1)

Expert system: Based on the rules of the target allocation and path planning
in [10], the algorithm can match the optimal action to the current state.
Therefore, it is also a rule–based swarm confrontation approach.

  * 2)

Game theory: The algorithm models the scenario as a differential game and
seeks strategies using Nash equilibrium in a two–coalition non–cooperative
game [32], which ultimately obtains the pursuers’ strategies.

  * 3)

Heuristic algorithm: The algorithm constructs biologically inspired mobile
adaptive networks to imitate the dynamics confrontation of swarms [3]. By
building a distributed modular framework that includes target allocation and
path planning, pursuers make successive and prompt decisions.

  * 4)

DRL: The algorithm considers swarm confrontation as an MDP process and
directly employs multi–agent reinforcement learning to output the pursuers’
strategies end–to–end [37].

  * 5)

HRL/IMVE: An approach adopts the uncertainty quantification as our HRL method,
while it updates the upper layer without IMVE.

The learning curves of HRL and baselines in different–size swarms are
presented in Fig. 5. Expert system, game theory, and heuristic algorithms can
develop strategies for pursuers in different instances. Among these three
non–learning algorithms, game theory performs the worst in uncertainty
scenarios. The heuristic algorithm outperforms the expert system algorithm in
large–scale swarms. Learning–based algorithms do not perform as well as
non–learning algorithms at first due to the randomness of the initial
strategy. However, with continuous exploration and training, their performance
gradually surpasses the latter. Due to the hybrid decision space in swarm
confrontation, the performance of DRL decreases continuously in the later
training. In contrast, HRL can find better strategies than non–learning
algorithms in different sizes. In addition, with the IMVE method, the
performance curve converges in fewer episodes, effectively improving the
learning efficiency of HRL.

We further deploy the policy networks trained by the learning–based methods in
$100$ different instances and compare them with the non–learning algorithms.
We propose two additional evaluation metrics: decision time and confrontation
win rate. Decision time refers to the total time taken by all pursuers for
task allocation and path planning based on their observations. We take the
average value after running different instances. The confrontation win rate
refers to the ratio of the number of pursuers’ successes to the number of all
instances. The experiment results of $100$ instances in different sizes are
shown in Table II. The table gathers the episode returns (Re.), decision time
(Ti.), and confrontation win rate (W.R.) of all methods. We can observe that
there is a relationship between the win rate and episode returns, which is
calculated by the reward function in this study. The higher the returns
achieved by pursuers, then the greater the win rate will be. Among these three
non–learning algorithms, the heuristic algorithm has a longer decision time,
although its returns and win rate are higher as the problem size increases.
Due to the end–to–end approach, DRL has the shortest decision time, but its
returns and win rate are much less than HRL. IMVE enhances the training
efficiency of the method, but there is no additional improvement in its
decision–making performance in the case of policy convergence. As a result,
all three metrics for HRL and HRL/IMVE are similar in different scales. The
results show that our method achieves better episode returns, decision time,
and confrontation win rate than the baselines, especially on large–scale
instances. The reason for this is that swarm confrontation in a dynamic
obstacle environment has a high degree of uncertainty, and the baselines lack
the ability to handle it. Our method optimizes the dynamic mechanism between
the two layers based on the probabilistic ensemble model, which quantifies the
uncertainty in the scenario.

Figure 6: Learning curves of adaptive and fixed $H$ approach in different–size
swarms.

###  V-D Ablation Study for Adaptive Interaction Frequency

In our method, we construct a probabilistic ensemble model between the upper
and lower to quantify the uncertainty. The method optimizes the interaction
frequency between the two layers based on the adaptive truncation approach.
With adaptive interaction frequency, we construct a dynamic mechanism between
target allocation and path planning that enables pursuers to overcome
uncertainty while chasing the evaders. To illustrate the effectiveness of the
adaptive frequency approach in our method, we conduct an ablation study by
fixing interaction step $H$ to three sets of constants ($H=13,16,19$). We
compare our adaptive method with them in the cross–training process in
different scenarios. The learning curves are shown in Fig. 6. When $H$ is a
constant, the curves first decline for a while, and the decline is greater as
$H$ is smaller, which means the target is assigned more frequently. This is
due to the fact that the upper layer, which is only pre–trained, is less
capable of handling uncertainty, and frequent use leads to a drop in
performance. When the upper layer has gone through several episodes of
cross–training, the curves will eventually converge to sub–optimal values,
although they will rise rapidly. Furthermore, the error of sub–optimal values
will become larger as the problem size increases.

Figure 7: The value of $H$ for our method in different–size swarms. Figure 8:
Ablation study results of ITM in different–size swarms.

Moreover, we plot the value of $H$ for the adaptive method in different sizes
and for different episodes ($0$–$60$) of cross–training in Fig. 7. The
horizontal coordinate refers to the time steps in each episode, and the
vertical coordinate refers to the value of $H$. In the early stage of
training, the method decreases the interaction step $H$ to augment the
training samples in the upper layer. Through constant training, the epistemic
uncertainty of the environment model decreases, so the interaction frequency
becomes progressively lower. However, since aleatoric uncertainty cannot be
eliminated, the increment in $H$ stabilizes after episode $15$. In addition,
during time steps $50$–$250$, the interaction frequency will be higher than
the other time steps because the pursuers will meet with evaders and
obstacles, and the aleatoric uncertainty will be higher at this time. Based on
the adaptive frequency method, we can overcome the negative effects of
uncertainty on cross–training, and finally achieve a favorable training
effect.

TABLE III: Generalization Results of Our Method and Baselines in Different Size Swarms. Number of | Method | V25 | V30 | V35
---|---|---|---|---
obstacles | Re. | Ti.(s) | W.R.(%) | Re. | Ti.(s) | W.R.(%) | Re. | Ti.(s) | W.R.(%)
4 | Expert system | -4738 | 10.25 | 69 | -5763 | 11.03 | 66 | -6984 | 12.12 | 62
Game theory | -4799 | 14.17 | 67 | -5905 | 18.89 | 63 | -7149 | 24.32 | 60
Heuristic | -4186 | 40.82 | 78 | -5094 | 61.34 | 76 | -6027 | 88.73 | 75
DRL | -4832 | 1.58 | 66 | -5871 | 2.10 | 63 | -6758 | 2.86 | 65
UQ-HRL | -3911 | 2.41 | 86 | -4862 | 3.05 | 84 | -5703 | 4.20 | 83
8 | Expert system | -5392 | 10.89 | 67 | -6499 | 11.94 | 65 | -7841 | 13.17 | 60
Game theory | -5521 | 15.87 | 66 | -6737 | 20.69 | 62 | -8120 | 26.85 | 57
Heuristic | -4849 | 48.95 | 80 | -5855 | 70.47 | 75 | -6834 | 99.51 | 73
DRL | -5296 | 1.74 | 68 | -6344 | 2.59 | 66 | -7295 | 3.37 | 65
UQ-HRL | -4194 | 2.88 | 84 | -5213 | 3.61 | 83 | -6159 | 4.93 | 80

###  V-E Ablation Study on ITM

In ITM, we pre–train the upper layer and lower layer based on the rewards
referred to (5) and (15), respectively. The pre–training phase allows the
upper layer to learn a static allocation strategy and the lower layer to train
an initial path planning policy. We conduct an ablation study in the
cross–training to investigate the efficiency of pre–training for the upper and
lower. The learning curves are shown in Fig. 8, where "ITM/X" refers to
adopting ITM but without the pre–training in the "X". For example, ITM/UL
denotes the training process only includes the pre–training in the lower layer
and cross–training. Due to the lack of pre–training in the upper layer, the
training efficiency of ITM/UL is significantly reduced. The curves of ITM/LL
first decline for a while, which is attributed to the poor ability of the
lower layer that lacks pre–training to deal with uncertainty. The absence of
pre–training on two layers leads ITM/UL&LL to perform the worst in cross-
training, although it does not affect the final convergence value. Moreover,
the effect of pre–training becomes more obvious as the problem size increases.
The results verify that ITM can effectively speed up the learning process and
avoid training instability.

Figure 9: Generalization to larger–scale instances.

###  V-F Generalization to Larger–Size Swarms

Figure 10: The swarm confrontation process with HRL in scenario V10.

In larger–scale swarm confrontation scenarios including V25, V30, and V35, we
will lose a lot of computational resources by retraining the model. Therefore,
we expect the trained model to have favorable generalization performance. We
employ the trained two–layer networks to solve the instances with more agents
and obstacles to verify the generalization performance of HRL. The models we
trained in V10, V15, and V20 are generalized to solve the problem of larger
sizes. The generalization results are shown in Fig. 9, where the horizontal
axis refers to the scenario sizes, and the vertical axis refers to the episode
returns. The legend refers to the model we trained in different sizes. Among
scenarios V10–V20, the model trained for a certain size performs best on the
corresponding scenario compared to those trained for other sizes. Although
models trained on a smaller size have lower returns, they still outperform
expert system, game theory, heuristic approach, and DRL. Due to the
uncertainty associated with the increase in the number of obstacles, the path
planning of the agents becomes more complex and the path reward is reduced. We
observe that the model trained in V20 performs best on scenarios V25–V35,
since it has a higher capability to handle uncertainty than the other models.

We compare the model trained in V20 with the baselines in scenarios V25–V35
similar to Table II. The experiment results are shown in Table III, which
displays the episode returns (Re.), decision time (Ti.), and confrontation win
rate (W.R.) testing in different problem sizes. As can be seen, HRL
outperforms other baselines in all instances. To further investigate the
generalization ability of our method, we utilize the trained model to solve
instances with eight obstacles in Table III. An increase in the number of
obstacles leads to a decrease in path rewards, but has a very small effect on
confrontation win rate. The results demonstrate that the trained policies
under small–size swarms are able to deal with the uncertainty in various scale
scenarios. Therefore, our method has a strong generalization ability on the
swarm confrontation problem.

###  V-G Emerged Coordinated Confrontation Behaviors

With sufficient training from scratch, the proposed HRL method can emerge
effective target allocation and path planning strategies. In this section, we
visualize the results of trained networks with our method on one of the V10
instances in Fig. 10, and analyze the coordinated behaviors in each stage.
Pursuers and evaders are labeled with "$X$" indicating their identification
numbers. The figure illustrates the process of target allocation and path
planning by pursuers through policy networks at different time steps. In the
figure, the upper layer assigns targets based on pursuers’ and evaders’
attributes to maximize the total reward in (25). The lower layer further plans
the safe paths to chase evaders while avoiding collisions with obstacles and
neighbors.

Time steps $0$–$50$: The upper layer allows for an even target allocation of
pursuers to ensure the best possible coverage of the defended area.

Time steps $50$–$100$: After time step $50$, the pursuers begin to encounter
evaders and obstacles, introducing more environment uncertainty into decision
making. Since pursuers with a large radius have a wider capture range, the
upper layer will prioritize mobilizing them to chase evaders with faster
escape velocities, such as evader $4$ and evader $7$.

Time steps $100$–$200$: In the round–up of evader $7$, the pursuers with a
large capture radius surround evader $7$ by path planning, and then allow the
pursuer $2$ with a smaller radius to conduct the final capture. This strategy
preserves the pursuers with large radius by sacrificing the ones with smaller
radius, which is beneficial to subsequent capture.

Time steps $200$–$250$: After the evaders have escaped the initial round–up by
the pursuers, the latter will choose to turn around and chase. The upper layer
will assign the pursuers priority to evaders who are closer because they have
a higher probability of being captured. Evaders may be hindered by an obstacle
or a neighbor ahead, resulting in a loss of velocities, and the pursuers
eventually catch up with them.

Time steps $250$–$300$: Even though evader $9$ is approaching the target area,
the others have been captured by pursuers. According to the rules in Section
III, pursuers capture more than half of the evaders, which win the
confrontation. Therefore, our trained models could deliver reasonably good
solutions in the swarm confrontation.

##  VI Conclusion

This paper has presented a guaranteed stable HRL method for hybrid decision
spaces and high uncertainty in swarm confrontation. It has designed two–layer
DRL networks to reflect commands and actions with target allocation and path
planning, and quantifies the uncertainty by constructing a probabilistic
ensemble model. Furthermore, the method has optimized the interaction
mechanism and enhances the sample utilization based on the uncertainty
quantification. We have also proposed an integration training method including
pre–training and cross–training to enhance the training efficiency and
stability. The experiment results have shown that our method achieves better
episode returns, decision time, and confrontation win rate than the baselines,
especially on large–size swarms. The influence of the adaptive frequency
approach and ITM has been verified via ablation studies. Moreover, we have
demonstrates the generalization of our method by applying a model trained
under small–size swarms to the larger ones. After sufficient training, our
method could emerge effective swarm confrontation strategies for agents.

## References

  * [1] X. Guo, W. Tang, K. Qin, Y. Zhong, H. Xu, Y. Qu, Z. Li, Q. Sheng, Y. Gao, H. Yang _et al._ , “Powerful uav manipulation via bioinspired self-adaptive soft self-contained gripper,” _Sci. Adv._ , vol. 10, no. 19, p. eadn6642, May 2024.
  * [2] A. Zhu, T. Dai, G. Xu, P. Pauwels, B. De Vries, and M. Fang, “Deep reinforcement learning for real-time assembly planning in robot-based prefabricated construction,” _IEEE Trans. Autom. Sci. Eng._ , vol. 20, no. 3, pp. 1515–1526, Jul. 2023.
  * [3] W. Xia, Z. Zhou, W. Jiang, and Y. Zhang, “Dynamic uav swarm confrontation: An imitation based on mobile adaptive networks,” _IEEE Trans. Aerosp. Electron. Syst._ , vol. 59, no. 5, pp. 7183–7202, Oct. 2023.
  * [4] H. Piao, Y. Han, S. He, C. Yu, S. Fan, Y. Hou, C. Bai, and L. Mo, “Spatio-temporal relationship cognitive learning for multi-robot air combat,” _IEEE Trans. Cognit. Dev. Syst._ , vol. 15, no. 4, pp. 2254–2268, Dec. 2023.
  * [5] S. Li, C. Wang, and G. Xie, “Optimal strategies for pursuit-evasion differential games of players with damped double integrator dynamics,” _IEEE Trans. Autom. Control_ , early access, Dec., 2023.
  * [6] D. Liu, Q. Zong, X. Zhang, R. Zhang, L. Dou, and B. Tian, “Game of drones: Intelligent online decision making of multi-uav confrontation,” _IEEE Trans. Emerging Top. Comput. Intell._ , vol. 8, no. 2, pp. 2086–2100, Dec. 2024.
  * [7] T. Zhang, L. Chai, S. Wang, J. Jin, X. Liu, A. Song, and Y. Lan, “Improving autonomous behavior strategy learning in an unmanned swarm system through knowledge enhancement,” _IEEE Trans. Reliab._ , vol. 71, no. 2, pp. 763–774, Jun. 2022.
  * [8] Z. Xia, J. Du, J. Wang, C. Jiang, Y. Ren, G. Li, and Z. Han, “Multi-agent reinforcement learning aided intelligent uav swarm for target tracking,” _IEEE Trans. Veh. Technol._ , vol. 71, no. 1, pp. 931–945, Jan. 2021.
  * [9] B. Wang, S. Li, X. Gao, and T. Xie, “Weighted mean field reinforcement learning for large-scale uav swarm confrontation,” _Appl. Intell._ , vol. 53, no. 5, pp. 5274–5289, Mar. 2023.
  * [10] Y. Hou, X. Liang, J. Zhang, M. Lv, and A. Yang, “Hierarchical decision-making framework for multiple ucavs autonomous confrontation,” _IEEE Trans. Veh. Technol._ , vol. 72, no. 11, pp. 13 953–13 968, Nov. 2023.
  * [11] K. G. Vamvoudakis, F. Fotiadis, A. Kanellopoulos, and N.-M. T. Kokolakis, “Nonequilibrium dynamical games: A control systems perspective,” _Annu. Rev. Control_ , vol. 53, pp. 6–18, May 2022.
  * [12] J. Kober, J. A. Bagnell, and J. Peters, “Reinforcement learning in robotics: A survey,” _Int. J. Robot. Res._ , vol. 32, no. 11, pp. 1238–1274, 2013.
  * [13] E. Kaufmann, L. Bauersfeld, A. Loquercio, M. Müller, V. Koltun, and D. Scaramuzza, “Champion-level drone racing using deep reinforcement learning,” _Nature_ , vol. 620, no. 7976, pp. 982–987, Aug. 2023.
  * [14] T. Haarnoja, B. Moran, G. Lever, S. H. Huang, D. Tirumala, J. Humplik, M. Wulfmeier, S. Tunyasuvunakool, N. Y. Siegel, R. Hafner _et al._ , “Learning agile soccer skills for a bipedal robot with deep reinforcement learning,” _Sci. Rob._ , vol. 9, no. 89, p. eadi8022, Apr. 2024.
  * [15] B. Eichmann, S. Greiff, J. Naumann, L. Brandhuber, and F. Goldhammer, “Exploring behavioural patterns during complex problem-solving,” _J. Comput. Assisted Learn._ , vol. 36, no. 6, pp. 933–956, Jun. 2020.
  * [16] X. Wang, Y. Laili, L. Zhang, and Y. Liu, “Hybrid task scheduling in cloud manufacturing with sparse-reward deep reinforcement learning,” _EEE Trans. Autom. Sci. Eng._ , early access, Mar., 2024.
  * [17] X. He and C. Lv, “Robotic control in adversarial and sparse reward environments: A robust goal-conditioned reinforcement learning approach,” _IEEE Trans. Artif. Intell._ , vol. 5, no. 1, pp. 244–253, Jan. 2023.
  * [18] M. Eppe, C. Gumbsch, M. Kerzel, P. D. Nguyen, M. V. Butz, and S. Wermter, “Intelligent problem-solving as integrated hierarchical reinforcement learning,” _Nat. Mach. Intell._ , vol. 4, no. 1, pp. 11–20, Jan. 2022.
  * [19] X. Mao, G. Wu, M. Fan, Z. Cao, and W. Pedrycz, “Dl-drl: A double-level deep reinforcement learning approach for large-scale task scheduling of multi-uav,” _IEEE Trans. Autom. Sci. Eng._ , early access, Feb., 2024.
  * [20] A. S. Vezhnevets, S. Osindero, T. Schaul, N. Heess, M. Jaderberg, D. Silver, and K. Kavukcuoglu, “Feudal networks for hierarchical reinforcement learning,” in _Proc. 34th Int. Conf. Mach. Learn. (ICML)_ , vol. 70, Aug. 2017, pp. 3540–3549.
  * [21] Y. Guan, Y. Liu, Y. Li, and X. Xu, “Hierrl: Hierarchical reinforcement learning for task scheduling in distributed systems,” in _Proceeding of IEEE International Joint Conference on Neural Networks (IJCNN)_ , Sep. 2022, pp. 1–8.
  * [22] Y. Ma, X. Hao, J. Hao, J. Lu, X. Liu, T. Xialiang, M. Yuan, Z. Li, J. Tang, and Z. Meng, “A hierarchical reinforcement learning based optimization framework for large-scale dynamic pickup and delivery problems,” in _Proc. 33rd Adv. Neural Inf. Process. Syst._ , vol. 34, 2021, pp. 23 609–23 620.
  * [23] Y. Geng, E. Liu, R. Wang, and Y. Liu, “Hierarchical reinforcement learning for relay selection and power optimization in two-hop cooperative relay network,” _IEEE Trans. Commun._ , vol. 70, no. 1, pp. 171–184, Jan. 2021.
  * [24] A. Asgharnia, H. M. Schwartz, and M. Atia, “Deception in the game of guarding multiple territories: A machine learning approach,” in _Proc. IEEE Int. Conf. Syst. Man Cybern. (SMC)_ , Oct. 2020, pp. 381–388.
  * [25] X. Nian, M. Li, H. Wang, Y. Gong, and H. Xiong, “Large-scale uav swarm confrontation based on hierarchical attention actor-critic algorithm,” _Appl. Intell._ , vol. 54, pp. 3279–3294, Feb. 2024.
  * [26] B. Wang, S. Li, X. Gao, and T. Xie, “Uav swarm confrontation using hierarchical multiagent reinforcement learning,” _Int. J. Aerosp. Eng._ , vol. 2021, pp. 1–12, Dec. 2021.
  * [27] W. Kong, D. Zhou, Y. Du, Y. Zhou, and Y. Zhao, “Hierarchical multi-agent reinforcement learning for multi-aircraft close-range air combat,” _IET Control Theory & Appl._, vol. 17, no. 13, pp. 1840–1862, Dec. 2023.
  * [28] T. Ren, J. Niu, B. Dai, X. Liu, Z. Hu, M. Xu, and M. Guizani, “Enabling efficient scheduling in large-scale uav-assisted mobile-edge computing via hierarchical reinforcement learning,” _IEEE Internet Things J._ , vol. 9, no. 10, pp. 7095–7109, May 2021.
  * [29] M. Janner, J. Fu, M. Zhang, and S. Levine, “When to trust your model: Model-based policy optimization,” in _Proc.33rd Adv. Neural Inf. Process. Syst._ , vol. 32, no. 1122, Dec. 2019, pp. 12 519–12 530.
  * [30] J. Buckman, D. Hafner, G. Tucker, E. Brevdo, and H. Lee, “Sample-efficient reinforcement learning with stochastic ensemble value expansion,” in _Proc.32nd Adv. Neural Inf. Process. Syst._ , vol. 31, Dec. 2018, pp. 8234–8244.
  * [31] L. Wang, T. Qiu, Z. Pu, J. Yi, J. Zhu, and Y. Zhao, “A decision-making method for swarm agents in attack-defense confrontation,” _22nd IFAC World Congress_ , vol. 56, no. 2, pp. 7858–7864, Nov. 2023.
  * [32] F. Liu, X. Dong, J. Yu, Y. Hua, Q. Li, and Z. Ren, “Distributed nash equilibrium seeking of $n$-coalition noncooperative games with application to uav swarms,” _IEEE Trans. Network Sci. Eng._ , vol. 9, no. 4, pp. 2392–2405, Jul.–Aug. 2022.
  * [33] H. Liu, J. Zhang, P. Zu, and M. Zhou, “Evolutionary algorithm-based attack strategy with swarm robots in denied environments,” _IEEE Trans. Evol. Comput._ , vol. 27, no. 6, pp. 1562–1574, Dec. 2023.
  * [34] P. R. Wurman, P. Stone, and M. Spranger, “Challenges and opportunities of applying reinforcement learning to autonomous racing,” _IEEE Intelligent Systems_ , vol. 37, no. 3, pp. 20–23, May–Jun. 2022.
  * [35] L. Gao, J. Schulman, and J. Hilton, “Scaling laws for reward model overoptimization,” in _Proc. 40th Int. Conf. Mach. Learn. (ICML)_ , no. 437, Jul. 2023, pp. 10 835–10 866.
  * [36] C. De Souza, R. Newbury, A. Cosgun, P. Castillo, B. Vidolov, and D. Kulić, “Decentralized multi-agent pursuit using deep reinforcement learning,” _IEEE Rob. Autom. Lett._ , vol. 6, no. 3, pp. 4552–4559, Jul. 2021.
  * [37] X. Qu, W. Gan, D. Song, and L. Zhou, “Pursuit-evasion game strategy of usv based on deep reinforcement learning in complex multi-obstacle environment,” _Ocean Eng._ , vol. 273, p. 114016, Feb. 2023.
  * [38] W. Kong, D. Zhou, Y. Zhou, and Y. Zhao, “Hierarchical reinforcement learning from competitive self-play for dual-aircraft formation air combat,” _J. Comput. Des. Eng._ , vol. 10, no. 2, pp. 830–859, Apr. 2022.
  * [39] W. Luo, J. Lü, K. Liu, and L. Chen, “Learning-based policy optimization for adversarial missile-target assignment,” _IEEE Trans. Syst. Man Cybern.: Syst._ , vol. 52, no. 7, pp. 4426–4437, Jul. 2021.
  * [40] K. Chua, R. Calandra, R. McAllister, and S. Levine, “Deep reinforcement learning in a handful of trials using probabilistic dynamics models,” in _Proc. 32nd Adv. Neural Inf. Process. Syst._ , vol. 31, 2018, p. 4759–4770.

Qizhen Wu received the B.S. degree in aeronautical and astronautical
engineering from Sun Yat–sen University, Guangzhou, China, in 2022. He is
currently pursuing the master degree with the School of Automation Science and
Electrical Engineering, Beihang University, Beijing, China. His current
research interests include reinforcement learning, robotic control, and swarm
confrontation.
---
Kexin Liu received the M.Sc. degree in control science and engineering from
Shandong University, Jinan, China, in 2013, and the Ph.D. degree in system
theory from the Academy of Mathematics and Systems Science, Chinese Academy of
Sciences, Beijing, China, in 2016. From 2016 to 2018, he was a Postdoctoral
Fellow with Peking University, Beijing. He is currently an Associated
Professor with the School of Automation Science and Electrical Engineering,
Beihang University, Beijing. His current research interests include multiagent
systems and complex networks
---
Lei Chen received the Ph.D. degree in control theory and engineering from
Southeast University, Nanjing, China, in 2018. He was a visiting Ph.D. student
with the Royal Melbourne Institute of Technology University, Melbourne, VIC,
Australia, and Okayama Prefectural University, Soja, Japan. From 2018 to 2020,
he was a Postdoctoral Fellow with the School of Automation Science and
Electrical Engineering, Beihang University, Beijing, China. He is currently
with the Advanced Research Institute of Multidisciplinary Science, Beijing
Institute of Technology, Beijing, as an Associate Research Fellow. His current
research interests include complex networks, characteristic model, spacecraft
control, and network control.
---
Jinhu Lü (Fellow, IEEE) received the Ph.D. degree in applied mathematics from
the Academy of Mathematics and Systems Science, Chinese Academy of Sciences,
Beijing, China, in 2002. He was a Professor with RMIT University, Melbourne,
VIC, Australia, and a Visiting Fellow with Princeton University, Princeton,
NJ, USA. He is currently the Dean of the School of Automation Science and
Electrical Engineering, Beihang University, Beijing. He is also a Professor
with the Academy of Mathematics and Systems Science, Chinese Academy of
Sciences. He is a Chief Scientist of the National Key Research and Development
Program of China and a Leading Scientist of Innovative Research Groups of the
National Natural Science Foundation of China. His current research interests
include complex networks, industrial Internet, network dynamics, and
cooperation control. Prof. Lü was a recipient of the Prestigious Ho Leung Ho
Lee Foundation Award in 2015, the National Innovation Competition Award in
2020, the State Natural Science Award three times from the Chinese Government
in 2008, 2012, and 2016, respectively, the Australian Research Council Future
Fellowships Award in 2009, the National Natural Science Fund for Distinguished
Young Scholars Award, and the Highly Cited Researcher Award in engineering
from 2014 to 2020. He is/was an Editor in various ranks for 15 SCI journals,
including the Co-Editor-in-Chief of IEEE TRANSACTIONS ON INDUSTRIAL
INFORMATICS. He served as a member in the Fellows Evaluating Committee of the
IEEE CASS, the IEEE CIS, and the IEEE IES. He was the General Co-Chair of
IECON 2017. He is a Fellow of CAA
---


#  Sparse-Encoded Codebook Index Modulation

Emre Arslan  Ali Tugberk Dogukan  and
Ertugrul Basar  The authors are with the Communications Research and
Innovation Laboratory (CoreLab), Department of Electrical and Electronics
Engineering, Koç University, Sariyer 34450, Istanbul, Turkey. Email:
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Ultra-reliable and low-latency communications (URLLC) partakes a major role in
5G networks for mission-critical applications. Sparse vector coding (SVC)
appears as a strong candidate for future URLLC networks by enabling superior
performance in terms of bit error rate (BER). SVC exploits the virtual digital
domain (VDD) and compressed sensing (CS) algorithms to encode and decode its
information through active symbol indices. In this paper, first, a clever
encoding/decoding algorithm is proposed for the SVC scheme, which allows the
use of all possible activation patterns (APs) resulting in increasing spectral
efficiency. Second, a novel solution is proposed to convey additional
information bits by further exploiting index modulation (IM) for the codebooks
of the SVC scheme. Computer simulation results reveal that our low-complexity
algorithm and novel IM solution provide not only a superior BER performance
but also an increase in the number of bits conveyed by IM compared to the
ordinary SVC approach.

###### Index Terms:

5G, index modulation (IM), sparse vector coding (SVC), ultra-reliable and low-
latency communications (URLLC), virtual digital domain (VDD).

##  I Introduction

Orthogonal frequency division multiplexing (OFDM) is the most popular multi-
carrier transmission technique due to its simplicity in generation and
recovery, high spectral efficiency, multiple-input multiple-output (MIMO)
compatibility and robustness to inter-symbol interference. Hence, OFDM is the
currently used waveform in 4G, while 5G utilizes a flexible multi-numerology
OFDM scheme. Great deal research has been done on OFDM and some have been very
successful such as OFDM with index modulation (OFDM-IM), where subcarriers are
grouped and data is transmitted through the indices of the active subcarriers
along with $M$-ary signal constellations as in classical OFDM [1, 2, 3].
However, even OFDM-IM alone, does not meet ultra-reliable and low-latency
communication (URLLC) requirements since it does not provide diversity in the
frequency domain.

URLLC is a critical service for 5G applications. Future applications such as
autonomous vehicles, wireless robotic surgery and real-time virtual reality
entertainment demand extremely low block error rate (BLER) performance, as low
as $10^{-5}$, with minimal latency on the order of milliseconds or less. As an
example, in contrast to traditional manned vehicles, autonomous vehicles are
extremely dependent on URLLC and waveform designs in 5G vehicular networks [4,
5]. Numerous techniques and algorithms are being developed to meet these
stringent requirements. However, it is challenging to have a highly reliable
and low-latency system concurrently because of the trade-offs among them.
Channel coding and various diversity techniques are widely used today to
achieve a higher bit error rate (BER) performance at the expense of lower
spectral efficiency and increased complexity. In addition, re-transmission is
used for increasing reliability while introducing further latency.

Recently, a number of methods have been implemented for OFDM to increase its
reliability, such as compressed sensing (CS) and sparse vector coding (SVC) as
given in [6] and [7], respectively. There have been many interesting CS-based
studies dealing with sparse matrices, successful recovery with a high
probability and sparse graph codes [8, 9, 10]. SVC appears as an attractive
tool for OFDM by enabling outstanding BLER values due to its extremely sparse
signal structure and CS-based ultra-reliable detection. Studies include
various iterative sparse approximation algorithms such as the greedy ones,
orthogonal matching pursuit (OMP) and multipath matching pursuit with depth-
first (MMP-DF) [11]. These algorithms provide robust sparsity recovery in low
signal-to-noise ratio (SNR) regions compared to previous approaches.
Nevertheless, state-of-the-art schemes do not provide low-latency solutions
and exhibit low data rates when using SVC with OFDM, which should be critical
for 5G and beyond URLLC applications.

This paper aims to improve the latency, spectral efficiency and BER of plain
SVC-based OFDM schemes for URLLC applications. Against this background, the
contributions of this paper are twofold. First, a clever encoding/decoding
technique is proposed for SVC-OFDM, which is referred to as enhanced SVC-OFDM
(E-SVC-OFDM). E-SVC-OFDM increases the number of bits transmitted by IM in an
intelligent manner. The MMP-DF algorithm is used for detection and since the
sparsity of the system is high, it can be considered as a system with low
complexity as in [11]. SVC-OFDM exploits a certain number of possible
activation patterns (APs) of the active indices and provides multiple sparse
vectors to use for data transmission. However, it is not always possible to
use all possible APs since the total number of combinations is not an integer
power of two. To solve this problem, E-SVC-OFDM runs a clever algorithm that
allows the use of all possible APs, hence, the number of bits transmitted by
APs is also increased. Second, a novel scheme called sparse-encoded codebook
IM (SE-CBIM) is introduced to further increase the number of bits transmitted
by IM. In this scheme, in addition to APs, IM is used also for codebook
indices with clever encoding and low-complexity decoding algorithms.

Figure 1: System model of E-SVC-OFDM

The rest of the paper can be summarized as follows. In Section II, the system
model of E-SVC-OFDM is presented. In Section III, the SE-CBIM technique is
proposed. Additionally, Section IV provides a complexity analysis. In Section
V, computer simulation results are presented to observe the effects of varying
parameters and to verify the superior performance of the proposed schemes. The
paper is concluded in Section VI.

##  II Enhanced Sparse Vector Coding OFDM

###  II-A E-SVC-OFDM Encoder

The block diagram of the considered E-SVC-OFDM system is shown in Fig. 1.
Firstly, using the combinatorial method [1], a sparse vector
$\mathbf{s}\in\mathbb{C}^{M\times 1}$, which has $K$ non-zero elements with
indices $(i_{1},i_{2},\cdots,i_{K})$, where $i_{k}\in\\{1,\cdots,M\\}$ is the
$k$th index, is constructed in the virtual digital domain (VDD)[6] according
to the decimal equivalent ($d$) of the incoming $m$ bits via binary to decimal
conversion. Once $(i_{1},i_{2},\cdots,i_{K})$ are selected, $K$ constant unit-
energy symbols that do not convey information, are assigned to these active
indices similar to space shift keying (SSK) schemes [12], where the vector of
these symbols is
$\mathbf{b}_{1}=\begin{bmatrix}x_{1}&x_{2}&\cdots&x_{K}\end{bmatrix}^{\mathrm{T}}$
and $[.]^{\mathrm{T}}$ denotes the transpose. A total of $\binom{M}{K}$ APs,
which can be generated by the combinatorial method and takes $d$ as an input,
are available, where $\binom{\cdot}{\cdot}$ is the binomial coefficient.
However, only $2^{\lfloor a\rfloor}$ APs can be used, which results in a waste
of potential use of all APs, where $a=\log_{2}\binom{M}{K}$ and
${\lfloor.\rfloor}$ is the floor function. At this point, a clever technique
that reuses the remaining $2^{\lfloor a\rfloor+1}-\binom{M}{K}$ APs by
extending the set of constant symbols as
$\mathbf{b}_{2}=\begin{bmatrix}\tilde{x}_{1}&\tilde{x}_{2}&\cdots&\tilde{x}_{K}\end{bmatrix}^{\mathrm{T}}$,
is proposed. Therefore, a total of $m={\lfloor a\rfloor}+1$ bits can be
transmitted for each OFDM symbol. This technique enables us to use all
possible APs and to transmit one additional bit. If $d$ is greater than
$\binom{M}{K}-1$, the indices corresponding to $d-\binom{M}{K}$ are reused by
extending the constant symbol set. We also avoid illegal APs in this way.

Figure 2: System model of SE-CBIM

As an example, assume two constant and unit-energy symbols $x_{1}=1$ and
$x_{2}=j$ are transmitted via active indices for $M=4$ and $K=2$. All possible
APs can be exploited with the reuse of the first two APs by extending the set
of the constant symbols by $\tilde{x}_{1}=-1$ and $\tilde{x}_{2}=-j$ as shown
in Table I. In the absence of this extension, we have a total of $6$ APs and
only $2^{\lfloor\log_{2}{6}\rfloor}=4$ out of them can be employed to convey
information. Here, the remaining $2$ APs are illegal. As seen from Table I,
our proposed method enables the use of all possible APs and the transmission
of $\log_{2}{8}=3$ bits.

TABLE I: Index combinations according to incoming bits Bits |  $d$ |  First Index $(i_{1})$ |  Second Index $(i_{2})$ |  First Symbol |  Second Symbol
---|---|---|---|---|---
$[000]$ |  $0$ |  $1$ |  $2$ |  $1$ |  $j$
$[001]$ |  $1$ |  $1$ |  $3$ |  $1$ |  $j$
$[010]$ |  $2$ |  $2$ |  $3$ |  $1$ |  $j$
$[011]$ |  $3$ |  $1$ |  $4$ |  $1$ |  $j$
$[100]$ |  $4$ |  $2$ |  $4$ |  $1$ |  $j$
$[101]$ |  $5$ |  $3$ |  $4$ |  $1$ |  $j$
$[110]$ |  $6$ |  $1$ |  $2$ |  $-1$ |  $-j$
$[111]$ |  $7$ |  $1$ |  $3$ |  $-1$ |  $-j$

After the formation of $\mathbf{s}$ as above, it is then spread by
multiplication with a predefined codebook matrix
$\mathbf{C}\in\mathbb{C}^{N\times M}$ whose elements are randomly generated
and Bernoulli distributed to enable CS-based detection at the receiver [7].
After spreading $\mathbf{s}$, the transmitted OFDM block
$\mathbf{x}_{F}\in\mathbb{C}^{N\times 1}$, whose all subcarriers are non-zero,
is obtained as:

$\mathbf{x}_{F}=\begin{bmatrix}x(1)&x(2)&\cdots&x(N)\end{bmatrix}^{\mathrm{T}}=\mathbf{Cs}.$
(1)

After this point, the same procedures for OFDM are applied. The inverse fast
fourier transform (IFFT) is applied to the OFDM block to obtain to the time
domain OFDM block $\mathbf{x}_{T}$:

$\mathbf{x}_{T}=\mathrm{IFFT}\big{\\{}\mathbf{x}_{F}\big{\\}}=\begin{bmatrix}X(1)&X(2)&\cdots&X(N)\end{bmatrix}^{\mathrm{T}}.$
(2)

After the IFFT operation, a cyclic prefix (CP) of length $L$ samples
$\begin{bmatrix}X(N-L+1)&\cdots&X(N-1)X(N)\end{bmatrix}^{\mathrm{T}}$ is added
to the beginning of the OFDM block. Once parallel to serial (P/S) and
digital/analog conversions are applied, the signal is transmitted over a
frequency-selective Rayleigh fading channel, which can be represented by the
channel impulse response (CIR) coefficients

$\mathbf{h}_{T}=\begin{bmatrix}h_{T}(1)&\cdots&h_{T}(v)\end{bmatrix}^{\mathrm{T}}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},}$
(3)

where $h_{T}(\alpha),\alpha=1,\dots,v$ are circularly symmetric complex
Gaussian random variables with the $\mathcal{C}\mathcal{N}(0,\frac{1}{v})$
distribution. With the assumption that the channel remains constant during
transmission of an OFDM block and the CP length $L$ is larger than $v$, the
equivalent frequency domain input-output relationship of this OFDM scheme is
given by

$y_{F}(\beta)=x_{F}(\beta)h_{F}(\beta)+w_{F}(\beta),\hskip
5.69046pt\beta=1,\dots,N$ (4)

where $y_{F}(\beta)$, $h_{F}(\beta)$ and $w_{F}(\beta)$ are the received
signals, the channel fading coefficients and the noise samples in the
frequency domain, whose vector forms are given as $\mathbf{y}_{F}$,
$\mathbf{h}_{F}$ and $\mathbf{w}_{F}$, respectively. The distributions of
$h_{F}(\beta)$ and $w_{F}(\beta)$ are $\mathcal{C}\mathcal{N}(0,1)$ and
$\mathcal{C}\mathcal{N}(0,N_{0})$, respectively, where $N_{0}$ is the noise
variance in the frequency domain, which is equal to the noise variance in the
time domain. The signal-to-noise ratio (SNR) is defined as $E_{b}/N_{0}$,
where $E_{b}=(N+L)/m$ is the average transmitted energy per bit. The spectral
efficiency of the proposed scheme is

$\eta=m/(N+L)\hskip 5.69046pt\text{[bits/s/Hz]}.\vspace{-0.4cm}$ (5)

###  II-B E-SVC-OFDM Decoder

At the receiver side, after removing CP and performing FFT, the MMP-DF
algorithm [11], whose inputs are given in Table II, is performed to decode
$\mathbf{y}_{F}$ under the assumption of perfect channel state information.
MMP-DF is chosen as the algorithm used due to its precise sparse vector
recovery and controllable complexity based on the number of candidates desired
for approximation. The MMP-DF algorithm outputs a sparse vector
$\mathbf{\hat{s}}\in\mathbb{C}^{M\times 1}$ and works by using a tree search
with the help of a greedy search method. As long as the performance gain is
high at low tree sizes, then the usage of MMP is well-justified [11]. $K$ is
fixed to two for efficient operation of the algorithm as in [7]. To be able to
apply the MMP-DF algorithm, $\mathbf{y}_{F}$ and $\mathbf{h}_{F}$ are modified
and used as an inputs for the algorithm. The modified received vector can be
expressed as[7]

$\hat{\mathbf{y}}_{F}=\mathrm{diag}(\hat{\mathbf{h}}_{F})\mathbf{y}_{F}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},}$
(6)

where $\mathrm{diag}(\mathbf{\cdot})$ creates a diagonal matrix from a vector,
$\hat{\mathbf{h}}_{F}=\begin{bmatrix}e^{j\angle{h_{F}(1)}}&\cdots&e^{j\angle{h_{F}(N)}}\end{bmatrix}^{\mathrm{T}}$
and $\angle{h_{F}(\beta)}$ is the angle of $h_{F}(\beta)$. The sensing matrix
can be expressed as

${\boldsymbol{\Psi}}=\mathrm{diag}(\mathbf{\hat{h}}_{F}\odot\mathbf{h}_{F})\mathbf{C}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},}$
(7)

TABLE II: MMP-DF Inputs and Parameters Inputs |  Notation
---|---
Modified received vector |  $\mathbf{\hat{y}}_{F}$
Sensing matrix |  ${\boldsymbol{\Psi}}$
Number of active subcarriers |  $K$
Number of search expansions |  $\Omega$
Stop threshold |  $\Lambda$
Maximum iterations |  $\Upsilon$

where $\odot$ stands for element-wise multiplication. Other inputs are the
numbers of active subcarriers $K$, number of search expansions $\Omega$, stop
threshold value $\lambda$ and maximum iterations $\Upsilon$. With all these
inputs, MMP-DF algorithm is run and outputs $\hat{\mathbf{s}}$ that only
includes $K$ non-zero elements [11].

The AP indices $(\hat{i}_{1},\hat{i}_{2},\cdots,\hat{i}_{K})$, which are
obtained from $\mathbf{\hat{s}}$, are applied to the combinatorial algorithm
[1] to obtain the decimal number $\hat{d}$. If $2^{{\lfloor
a\rfloor}+1}-\binom{M}{K}\leq\hat{d}$, meaning
$(\hat{i}_{1},\hat{i}_{2},\cdots,\hat{i}_{K})$ are non-reused indices,
$\hat{d}$ can be directly converted to bits. Otherwise, the two vectors
$\mathbf{b}_{1}$ and $\mathbf{b}_{2}$ that contain the symbols
$(x_{1},x_{2},\cdots,x_{K})$ and the extended ones
$(\tilde{x}_{1},\tilde{x}_{2},\cdots,\tilde{x}_{K})$, respectively, are used
for detection. For this purpose, the vector
$\mathbf{\hat{b}}=\begin{bmatrix}\hat{b}_{1}&\hat{b}_{2}&\cdots&\hat{b}_{K}\end{bmatrix}^{\mathrm{T}}$,
which includes the non-zero elements of $\mathbf{\hat{s}}$, is constructed.
Finally, in the following, two decision metrics are calculated to find whether
the original symbols or extended ones are employed:

$\hat{l}=\arg\underset{l\in{1,2}}{\min}\|\mathbf{\hat{b}}-\mathbf{b}_{l}\|^{2}.$
(8)

If $\hat{l}=1$, corresponding to the original symbols, then $\hat{d}$ is
directly converted to bits. On the other hand, if $\hat{l}=2$, which
represents the extended symbols, $\hat{d}+\binom{M}{K}$ is converted to bits.
To further illustrate the E-SVC-OFDM decoder, a simple example is shown in
Fig. 3.

Figure 3: A flow diagram example of the E-SVC-OFDM decoder for $M=4$ and
$K=2$.

##  III Codebook Index Modulation

In this section, we propose the novel scheme of SE-CBIM whose block diagram is
shown in Fig. 2. SE-CBIM is a waveform that further improves the spectral
efficiency of the reliable and low-latency E-SVC-OFDM system. This method
conveys information bits by not only the indices of active VDD components but
also the selected codebook index.

###  III-A SE-CBIM Encoder

The transmitter of the proposed system is built on to that of E-SVC-OFDM, with
a major difference due to the use of multiple codebooks instead of one. As
shown in Fig. 2, the incoming $m$ bits are split into $m_{1}=\log_{2}{G}$ and
$m_{2}={\lfloor a\rfloor}+1$ bits. Here, $m_{1}$ bits choose the $g$th
codebook $\mathbf{C}_{g}$, $g\in\\{1,\dots,G\\}$, where $G$ is the total
number of predefined codebook matrices whose elements are randomly generated
with Bernoulli distribution and is an integer power of two. Then,
$m_{2}={\lfloor a\rfloor}+1$ bits are applied to the E-SVC-OFDM encoder as
previously done to determine $\mathbf{s}$. Therefore, in SE-CBIM, for $G$
codebooks, a total of

$m=\log_{2}{G}+{\lfloor
a\rfloor}+1{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},}$
(9)

bits can be transmitted for each OFDM symbol.

###  III-B SE-CBIM Decoder

At the receiver side, the MMP-DF algorithm is run $G$ times for each generated
codebook resulting in $G$ number of output vectors $\mathbf{\hat{s}}_{g}$ with
the set of active indices
$\bar{I}_{g}=(\hat{i}_{g,1},\hat{i}_{g,2},\cdots,\hat{i}_{g,K})$, where
$\hat{i}_{g,k}$ is the $k$th active index of the output vector corresponding
to the $g$th codebook. For each $\mathbf{\hat{s}}_{g}$, two vectors
$\bar{\mathbf{b}}_{g,1}$, $\bar{\mathbf{b}}_{g,2}\in\mathbb{C}^{M\times 1}$,
which include the elements of $\mathbf{b}_{1}$ and $\mathbf{b}_{2}$,
respectively, are produced using the indices in $\bar{I}_{g}$. Then, the
decoded codebook index $\hat{g}$ is determined by calculating a total of $2G$
metrics as follows:

$(\hat{g},\hat{l})=\arg\underset{g,l\in{1,2}}{\min}\|\mathbf{\hat{s}}_{g}-\bar{\mathbf{b}}_{g,l}\|^{2}.$
(10)

According to $\hat{g}$, $m_{1}$ bits are decoded directly. Then, the active
indices $\bar{I}_{\hat{g}}$ of the determined codebook are applied to the
combinatorial algorithm to obtain the decimal value $\hat{d}$. If $2^{{\lfloor
a\rfloor}+1}-\binom{M}{K}\leq\hat{d}$ or if $\hat{d}<2^{{\lfloor
a\rfloor}+1}-\binom{M}{K}$ and $\hat{l}=1$, $\hat{d}$ is directly converted to
$m_{2}$ bits. Otherwise, if $\hat{d}<2^{{\lfloor a\rfloor}+1}-\binom{M}{K}$
and $\hat{l}=2$, meaning the symbols are extended, $\hat{d}+\binom{M}{K}$ is
converted to $m_{2}$ bits.

##  IV Complexity Analysis

Figure 4: Running time as a function of $M$ where the proposed schemes use ML
and MMP-DF detection.

In this section, we analyze the complexity of E-SVC-OFDM and SE-CBIM detectors
in terms of the running time as in [11]. We have exploited the MATLAB software
on a computer with an Intel Core i7-3930K processor and Microsoft Windows 10
environment to obtain the running time. In [11], it is stated that MMP-DF
algorithm is comparable with other greedy algorithms such as StOMP [13] and
CoSaMP [14] when $K$ is low. In our proposed schemes, we have selected $K=2$,
therefore, the algorithm we employ can be considered as a low-complexity one.
Also, since channel coding is not required to achieve outstanding BER in SE-
CBIM, it is relatively a much less complex scheme when compared to channel
coded ones. To give further insight into the decoding complexity, we show the
comparison of ML detection and the proposed detectors in Fig. 4. Assume that
the set including all possible sparse vectors in VDD is given by
$\mathcal{X}=\\{\mathbf{x}_{1},\cdots,\mathbf{x}_{2^{\lfloor a\rfloor+1}}\\}$.
Then, by employing $\mathcal{X}$, ML detection rules for E-SVC-OFDM and SE-
CBIM can be obtained, respectively, as:

$\hat{\mathbf{x}}=\arg\underset{\mathbf{x}\in\mathcal{X}}{\min}\|\mathbf{y}_{F}-\mathbf{h}_{F}\odot(\mathbf{C}\mathbf{x})\|^{2}.$
(11)
$(\hat{\mathbf{x}},\hat{g})=\arg\underset{g,\mathbf{x}\in\mathcal{X}}{\min}\|\mathbf{y}_{F}-\mathbf{h}_{F}\odot(\mathbf{C}_{g}\mathbf{x})\|^{2}.$
(12)

As seen from Fig. 4, ML detection is inefficient in terms of complexity for
the proposed schemes. However, MMP-DF algorithm presents much lower complexity
compared to ML method. In Fig. 4, since $K$ is low, the MMP-DF detector is
more efficient than the ML detector as in [11]. Also, it can be observed that
with an increase of the number of codebooks, the decoding complexity
increases. It should be noted that the complexity of the decision metric
calculations in (8) and (10) after the MMP-DF algorithm to determine whether
the symbols are extended, is negligible and can be ignored. Additionally, in
contrast to ML detection, MMP-DF is not effected by $M$ since $K$ is constant.

##  V Simulation Results

In this section, computer simulation results are presented for varying
parameters of E-SVC-OFDM and SE-CBIM. Additionally, a BER comparison is shown
for convolutional coded OFDM [15], E-SVC-OFDM and SE-CBIM. Error performance
of these schemes are obtained through Monte Carlo simulations. For all
simulations, a $10$-tap frequency-selective Rayleigh fading channel and two
active indices ($K=2$) in the VDD is assumed, where $x_{1}=1$, $x_{2}=j$ and
$\tilde{x}_{1}=-1$, $\tilde{x}_{2}=-j$. The CP length is set as $16$ and the
LTE convolutional code with rate $1/3$ was chosen [15]. The parameters
$\Omega$, $\Lambda$ and $\Upsilon$ for the MMP-DF algorithm are set as $2$,
$0.1$, and $2$, respectively.

The first simulation involves only the E-SVC-OFDM scheme with a varying number
of subcarriers $(N)$ in the frequency domain as $M=128$ is kept constant,
which changes the spectral efficiency. As seen from Fig. 5(a), as the number
of elements in the virtual domain is kept constant and the number of
subcarriers are escalated from $32$ to $512$, a noticeable improvement is
observed in BER performance due to the APs of the sparse vector being spread
to more resources in the frequency domain. In other words, spreading the APs
to more subcarriers provides a coding gain. As $N$ increases, the correlation
between randomly generated codewords decreases, and this helps with better
recovery of sparse vectors. However, spectral efficiency decreases as the
number of subcarriers increases because more spectrum is used with more
subcarriers. It is also seen in Fig. 5(a) that the BER improvement reaches a
saturation while the largest improvement occurs until $N\leq M$.

In Fig. 5(b), the number of subcarriers is fixed to $128$, and the number of
elements in the virtual domain ($M$) is varied as $32,64$ and $128$. It is
observed that with increasing the size of the virtual domain, the error
performance improves relatively. This can be explained by the fact that as $M$
increases, sparsity increases resulting in an improvement in BER and an
increase in the number of transmitted bits.

Figure 5: Error performance of E-SVC-OFDM (a) for $M=128$ and varying $N$ and
(b) for $N=128$ and varying $M$. Figure 6: Error performance of SE-CBIM (a)
for $N=128,M=128$ and (b) the comparison of relevant schemes for $N=64$ and
$M=64$.

Fig. 6(a) presents the improvements in BER as the number of codebooks are
increased in the proposed SE-CBIM scheme. It is shown that with this increase,
the number of bits transmitted increases and this also provides a slightly
better BER due to the characteristics of IM. However, there exists a trade-
off: as the number of codebooks and bits transmitted is increased, the latency
also increases due to additional codebook possibilities searched at the
receiver as discussed in Section IV. It is also worth noting that the spectral
efficiency values in the simulations are in the level of plain SVC-OFDM[7].

Finally, our scheme is compared to the existing LTE convolutional coded OFDM
[15] with zero padding in Fig. 6(b). We have used zero padding for coded OFDM
to obtain the same spectral efficiency with the proposed scheme and employed
random interleaving to improve its performance. SE-CBIM provides an
outstanding BER with an improvement of $10$ dB compared to coded-OFDM and
relatively lower complexity due to the requirement of coding being removed.
Additionally, it is seen that with SE-CBIM, without reducing the error
performance, additional bits can be transmitted by exploiting codebook indices
with increased complexity. Consequently, SE-CBIM presents an interesting
trade-off between complexity and the number of bits transmitted by IM.

##  VI Conclusion

In this paper, E-SVC-OFDM and SE-CBIM schemes have been presented as reliable
and low-latency waveforms. E-SVC-OFDM provides a clever and efficient use of
the APs compared to the existing SVC-OFDM. SE-CBIM has been introduced as a
novel waveform with increased spectral efficiency by utilizing IM compared to
conventional SVC-OFDM schemes. The improved BER of the SE-CBIM scheme over the
existing coded-OFDM scheme has been demonstrated through Monte Carlo
simulations. Further reliability and latency improvements with generalized
designs may be possible and left as future work.

## References

  * [1] E. Basar, U. Aygolu, E. Panayırcı, and H. V. Poor, “Orthogonal frequency division multiplexing with index modulation,” _IEEE Trans. Signal Process._ , vol. 61, no. 22, pp. 5536–5549, Nov. 2013.
  * [2] A. M. Jaradat, J. M. Hamamreh, and H. Arslan, “OFDM with subcarrier number modulation,” _IEEE Wireless Commun. Lett._ , vol. 7, no. 6, pp. 914–917, Dec. 2018.
  * [3] E. Basar, “OFDM with index modulation using coordinate interleaving,” _IEEE Wireless Commun. Lett._ , vol. 4, no. 4, pp. 381–384, Aug. 2015.
  * [4] X. Ge, “Ultra-reliable low-latency communications in autonomous vehicular networks,” _IEEE Trans. Veh. Technol._ , vol. 68, no. 5, pp. 5005–5016, May 2019.
  * [5] X. Cheng, M. Wen, L. Yang, and Y. Li, “Index modulated OFDM with interleaved grouping for V2X communications,” in _Proc. IEEE Int. Conf. Intell. Transp. Syst. (ITSC)_ , Oct. 2014, pp. 1097–1104.
  * [6] H. Zhang, L.-L. Yang, and L. Hanzo, “Compressed sensing improves the performance of subcarrier index-modulation-assisted OFDM,” _IEEE Access_ , vol. 4, pp. 7859–7873, Oct. 2016.
  * [7] H. Ji, S. Park, and B. Shim, “Sparse vector coding for ultra reliable and low latency communications,” _IEEE Trans. Wireless Commun._ , vol. 17, no. 10, pp. 6693–6706, Oct. 2018.
  * [8] M. Bakshi, S. Jaggi, S. Cai, and M. Chen, “Sho-fa: Robust compressive sensing with order-optimal complexity, measurements, and bits,” _IEEE Trans. Inf. Theory_ , vol. 62, no. 12, pp. 7419–7444, Dec 2016.
  * [9] S. Pawar and K. Ramchandran, “Computing a k-sparse n-length discrete fourier transform using at most 4k samples and o(k log k) complexity,” in _Proc. 2013 IEEE ISIT, Istanbul, Turkey_ , Jul 2013, pp. 464–468.
  * [10] X. Li, D. Yin, S. Pawar, R. Pedarsani, and K. Ramchandran, “Sub-linear time support recovery for compressed sensing using sparse-graph codes,” _IEEE Trans. Inf. Theory_ , vol. 65, no. 10, pp. 6580–6619, Oct 2019\.
  * [11] S. Kwon, J. Wang, and B. Shim, “Multipath matching pursuit,” _IEEE Trans. Inf. Theory_ , vol. 60, no. 5, pp. 2986–3001, May 2014.
  * [12] E. Basar et al., “Index modulation techniques for next-generation wireless networks,” _IEEE Access_ , vol. 5, pp. 16 693–16 746, Sep. 2017\.
  * [13] D. L. Donoho, Y. Tsaig, I. Drori, and J. Starck, “Sparse solution of underdetermined systems of linear equations by stagewise orthogonal matching pursuit,” _IEEE Trans. Inf. Theory_ , vol. 58, no. 2, pp. 1094–1121, Feb 2012.
  * [14] D. Needell and J. A. Tropp, “Cosamp: Iterative signal recovery from incomplete and inaccurate samples,” _Commun. ACM_ , vol. 53, no. 12, pp. 93–100, Dec. 2010.
  * [15] S. Ahmadi, “LTE-advanced: A practical systems approach to understanding 3gpp lte releases 10 and 11 radio access technologies,” _LTE-Advanced: A Practical Systems Approach to Understanding 3GPP LTE Releases 10 and 11 Radio Access Technologies_ , pp. 1–1116, Oct. 2014.