# Genetic Imitation Learning by Reward Extrapolation

Boyuan Zheng1 Jianlong Zhou1&Fang Chen1 1University of Technology Sydney
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Imitation learning demonstrates remarkable performance in various domains.
However, imitation learning is also constrained by many prerequisites. The
research community has done intensive research to alleviate these constraints,
such as adding the stochastic policy to avoid unseen states, eliminating the
need for action labels, and learning from the suboptimal demonstrations.
Inspired by the natural reproduction process, we proposed a method called
GenIL that integrates the Genetic Algorithm with imitation learning. The
involvement of the Genetic Algorithm improves the data efficiency by
reproducing trajectories with various returns and assists the model in
estimating more accurate and compact reward function parameters. We tested
GenIL in both Atari and Mujoco domains, and the result shows that it
successfully outperforms the previous extrapolation methods over extrapolation
accuracy, robustness, and overall policy performance when input data is
limited.

##  1 Introduction

Imitation learning, which leverages demonstration from other sources to
reproduce the target behavior without handcrafting reward function, gets
boosted with the help of recent advances in deep learning. Due to its “reward
function-free” characteristic, imitation learning plays a crucial role in
problems where designing a reward function is impractical, such as robotic arm
manipulation (Duan et al., 2017) and autonomous driving (Codevilla et al.,
2018). However, the vast amount of existing research develops their methods,
assuming that the input demonstrations are optimal or near-optimal. This
assumption sets up an upper bound to the agent performance, and to some
extent, it exacerbates the negative impact of suboptimal demonstrations on
final performance (Zheng et al., 2021). The agent performance would converge
to suboptimal when the input demonstrations are suboptimal. It is also a waste
as the suboptimal demonstrations are more abundant and accessible to collect
than the optimal demonstrations. Specifically, as imitation learning is
interdisciplinary, optimal demonstrations from experts who are working in
other research fields could be expensive and impractical.

Fortunately, a number of recent research (Chang et al., 2015; Brown et al.,
2019; Ding et al., 2019) have investigated and attempted to use the suboptimal
demonstration to obtain better-than-demonstrator performance. Adversarial
structured imitation learning and extrapolation are two mainstream approaches
to address this problem. The state-of-the-art adversarial method GAIL (Ho and
Ermon, 2016) presents considerable robustness on suboptimal input. Following
methods like RAIL (Zuo et al., 2020) developed a more mature framework to
better leverage suboptimal demonstration, but shortcomings like fragile
structure are also inherent from the adversarial structure. On the other hand,
the research community has widely investigated another research direction:
doing extrapolation induces better-than-demonstrator behavior. Besides the
suboptimal demonstrations, the input commonly involves extra information, such
as human preferences or the different levels of noise. The extra information
facilitates the model to establish a relationship between the suboptimal
demonstrations and the extra information and deduces the policy close to the
optimal. The extrapolation achieves considerable performance in both Atari and
Mujoco domains, but the extra information is commonly laborious.

In this work, we propose an imitation learning method called Genetic Imitation
Learning(GenIL). It advocates the Imitation from Observation(IfO) setting,
integrates genetic algorithm concepts with imitation learning, and achieves
more compact extrapolation using suboptimal demonstration. Unlike prior work,
GenIL gets rid of the laborious procedure and leverages the idea from the
genetic algorithm. By applying crossover and mutation on the input
trajectories, GenIL generates new trajectories with multiple levels of
quality. These newly generated trajectories serve as extra information to
assist the extrapolation process. We compare our method with other related
approaches on various Atari and Mujoco domains. The result shows that GenIL
could achieve data efficiency and extrapolate more accurate and compact
rewards for unseen trajectories than existing imitation learning algorithms.
As for the overall policy performance, GenIL also presents competitive
performance and outperforms previous methods.

The contributions of our work include:

  * •

We propose a better reward extrapolation model GenIL that generate a more
compact and stable extrapolation to estimate the reward parameter by
aggregating genetic algorithm and imitation learning.

  * •

GenIL makes better use of the suboptimal data and only uses two trajectories
with diverse performance as input to train the model.

  * •

We present a series of experiments and show that GenIL could obtain a
meaningful policy from the suboptimal demonstration and outperform previous
approaches.

##  2 Related Work

This section briefly summarizes the recent advances in related topics learning
from suboptimal demonstration, Imitation from Observation, reward
extrapolation and genetic algorithm.

Imitation learning aims to reproduce the target behavior with the help of
demonstrations, it plays a crucial role in training autonomous agents.
Typically, imitation learning could be categorized into behavior cloning (Bain
and Sammut, 1999) and inverse reinforcement learning (Russell, 1998). These
two classes are distinguished by whether to restore the reward function.
Commonly, they assume the input demonstration is optimal (or nearly optimal)
and take state-action pairs batched from the optimal demonstrations as input.
As the research on imitation learning continues to deepen, researchers have
begun to challenge these assumptions, including the challenge of the necessity
of optimal demonstration. Especially after GAIL (Ho and Ermon, 2016) was
proposed, the research community intensively investigated the feasibility of
learning from suboptimal demonstrations. One of the commonly used techniques
is integrating Hindsight Experience Replay(HER) (Andrychowicz et al., 2017)
into GAIL, research such as HGAIL (Liu et al., 2019) and GoalGAIL (Ding et
al., 2019) make use of the HER and set up new goals along the sub-optimal
demonstrations to outperform the suboptimal demonstration. In RAIL (Zuo et
al., 2020), besides making an extension on HER, they also proposed a technique
called hindsight copy which leverages both original demonstration and
hindsight acquired demonstration to speed up the learning process.

With the emergence of new imitation learning algorithms, the restricted input
form is also liberated. Until 2018, sequences of state-action pairs form the
input data for imitation learning algorithms. The actions are commonly used as
labels to train the model. However, in 2018, Liu et al. 2018 proposed a novel
imitation paradigm called Imitation from Observation(IfO) that changed the
previous tradition. Inspired by the nature of how humans and animals imitate,
IfO eliminates the need for action labels and only utilizes the observations
to train the model. IfO is working in a supervised learning manner, an
encoder-decoder structure is adopted to extract features from the
observations, and the distance between ground truth and predicted observation
is measured to replace the conventional action label. The presence of the IfO
provides a solution for the scenarios where action labels are not available
and enlarges the available training resource. Intensive research (Torabi et
al., 2019; Zhu et al., 2021; Aytar et al., 2018) is attracted to leverage raw
observation as input. For example, Sermanet et al. 2018 proposed a self-
supervised IL method Time-Contrastive Network (TCN), that uses unlabeled
multi-viewpoint video to assist the agent in learning its internal joint and
invariant representation about the task.

Figure 1: Graphical explanation about extrapolation. The red points are the
suboptimal demonstrations used for training, and the blue points are the
unseen trajectories.

In addition to using the adversarial structure to address the suboptimal
demonstration problem, the research community also explores other alternatives
for this problem. Extrapolating rewards from the suboptimal demonstration is
one of the reasonable solutions. Extrapolation means using additional
information or reward signals to assist the model in establishing a connection
between the suboptimal demonstration and intended goals. Figure 1 provides a
graphical explanation about extrapolation. Compared with adversarial
structured imitation learning, extrapolation requires less environmental
interaction and a more stable structure, but adding meaningful information
could be laborious and expensive. Palan et al. 2019 proposed DemPref that
utilizes online preference from humans to overcome the demonstration quality
problem in real-world robotic arm scenarios. Similarly, Brown et al. 2019
indicated that ranking the dataset in advance could help the agent infer
better-than-demonstrator behaviors. The proposed T-REX inputs a gradually
better demonstration dataset or manually ranked dataset for standard inverse
reinforcement learning and outperforms the state-of-the-art methods on
suboptimal scenarios. Their later approach, D-REX (Brown et al., 2020),
eliminates the laborious procedure and achieves ranking by injecting different
levels of noise. However, the noise is not always harmful to agent
performance. Involving appropriate stochastic steps in trajectories could
facilitate the generalization and prevent overfitting to the training dataset
distribution, as shown in (Brown et al., 2020). In this case, this paper uses
stochastic policy more flexibly to assist in achieving better policy
performance while implementing automated ranking.

Figure 2: A diagrammatic visualization of our method. The suboptimal
demonstrations $\mathcal{D}$ firstly serve as the individual chromosomes in
the genetic algorithm part to generate “fake” trajectories $\tau_{fake}$, then
together with the generated dataset to feed into the convolutional neural
network. The features extracted by the convolution neural network are used to
train the reward parameter $R_{\theta}$ represented by MLP.

On the other hand, this paper also leverages the idea of Genetic Algorithm
(GA). GA, an adaptive stochastic optimization algorithm, is one of the
evolutionary algorithms (Karakatič and Podgorelec, 2015). GA was firstly
proposed in (De Jong, 1975), and got further improved by (Holland, 1992;
Goldberg, 2006) to solve the complex optimization problems. The research
community developed several works in combining evolutionary algorithms with
imitation learning in the fields of game strategy learning (Eliya and
Herrmann, 2020), robot movement (Park et al., 2008) and autonomous driving
(Jalali et al., 2019). They leveraged evolutionary algorithms to either
achieve offline dataset enrichment or optimize the network parameter. GA
process mimics how genes generate and evolve to achieve efficient searching
and optimization. The genetic interchange is relatively sparse in the real
world and occurs when producing new generations. GA maintains three basic
biology principles: reproduction, natural selection and individual diversity
(Darwin, 1859), while bypassing other biological activities. It includes
different problem features as a chromosome or genotype and iteratively
reproduces new individuals by genetic operators. For instance, crossover
interchanges the genes between two chromosomes and generates new offspring,
and mutation mutates genetic snippets on a chromosome. One individual
represents one possible solution and participates in the natural selection
process, evaluated by the fitness function. The fitness function filters out
the weak individual and achieves optimization. In addition to having an
appropriate fitness function, in order to efficiently obtain the optimal
solution, individual diversity is also a crucial influencing factor. When
individuals are scattered in their features, GA procedure could be more
effective in finding the optimal global solution.

In this work, we introduce GA into imitation learning and propose a method
called GenIL. GenIL leverages the genetic operators,crossover and mutation, on
the suboptimal trajectories and generates new samples with various levels of
returns for extrapolating reward function parameters.

##  3 Problem definition

Algorithm 1 GenIL

Input: Demonstrations $\mathcal{D}$, number of offspring K, mutation rate
$p_{mut}$, crossover rate $p_{crx}$
Output: Estimated reward parameter $R_{\theta}$

1: Initialize reward parameter $R_{\theta}$ randomly.

2: relabel demonstrations with the initial
rank$\mathcal{D}=\\{(\tau_{1},Rank_{1}),(\tau_{2},Rank_{2})\\}$.

3: while number of (offspring) $<$ K do

4: $\tau_{x},Rank_{x},\tau_{y},Rank_{y}$ = SampleParents($\mathcal{D}$)

5: offspring $\tau_{fk},Rank_{f}k$ =
Crossover($p_{crx}$,$\tau_{x},Rank_{x},\tau_{y},Rank_{y}$)

6: offspring $\tau_{fk},Rank_{f}k$ = Mutation($p_{mut}$,
$\tau_{fk},Rank_{f}k$)

7: if $Rank_{f}k$ satisfy selection rule then

8: Add offspring $(\tau_{fk},Rank_{f}k)$ to $\mathcal{D}_{rank}$

9: $\mathcal{D}\to\mathcal{D}\cup\mathcal{D}_{rank}$

10: end if

11: end while

12: Run T-REX to obtain $R_{\theta}$

13: Obtain policy $\pi_{\theta}$ by reinforcement learning using reward
parameter $R_{\theta}$.

In this work, we assume that GenIL is modeled under the Markov Decision
Process (MDP) framework. MDP is the process satisfying the property that the
next state $s_{t+1}$ only depends on the current state $s_{t}$ at any time
$t$. Typically, a MDP is defined as a tuple
($\mathcal{S}$,$\mathcal{A}$,$\mathcal{P}$,$\gamma$,$\mathcal{D}$,$\mathcal{R}$),
where $\mathcal{S}$ is the finite set of states, $\mathcal{A}$ is the
corresponding set of actions, $\mathcal{P}$ is the set of state transition
probabilities and the successor states $s_{t+1}$ is drawn from this transition
model, i.e. $s_{t+1}=P(\cdot|s_{t},a_{t})$, $\gamma\in[1,0)$ is the discount
factor, $\mathcal{D}$ is the set of demonstration trajectories
$\mathcal{D}_{n}=\\{\tau_{1},\tau_{2},...,\tau_{n}\\}$ and $\mathcal{R}$ is
the reward function $\mathcal{S}\mapsto\mathcal{R}$. The expected cumulative
reward of a trajectory $\tau_{x}$ is
$G(\tau_{x})=\sum^{T}_{t=0}\gamma^{t}R(s^{t})$.

Similar to other imitation learning methods, we assume the optimal reward
function is not accessible. The input demonstration $\mathcal{D}_{original}$
consists of two trajectories: one good (or near-optimal) trajectory
$\tau_{good}$ and one suboptimal demonstration $\tau_{bad}$. Here we wish to
approximate a reward function parameter $\theta$, which reflects the intended
optimal policy as close as possible. To represent the goodness of the
trajectories, we propose to use a sequence of identical number to replace the
original step reward sequence, i.e. $R^{\prime}(S)=\\{rank\\}^{m}$, where
$\sum R^{\prime}_{\tau_{good}}(S)>\sum R^{\prime}_{\tau_{bad}}(S)$. In
previous work like T-REX (Brown et al., 2019), ranks are manually assigned by
the expert. The ranking serves as the training label via supervised learning.
This work inherits the previous setting while eliminating the laborious
ranking procedure for human experts, the ranking is generated by genetic
algorithm. By implementing crossover and mutation steps, the original
trajectories mix up and generate fake trajectories $\tau_{fake}$ with various
numbers as their fake step reward $\sum R^{\prime}_{\tau_{good}}(S)>\sum
R^{\prime}_{\tau_{fake}}(S)>\sum R^{\prime}_{\tau_{bad}}(S)$. According to the
accumulated fake step reward, these fake trajectories are classified into
different ranks, and form ranked input together with the original dataset. The
network trained on this combined dataset is expected to predict a more
significant return on the trajectory that contains more parts from the good
demonstration, i.e. $\mathbb{E}_{\pi}[\sum\gamma
R_{\theta}(\tau_{a})]>\mathbb{E}_{\pi}[\sum\gamma R_{\theta}(\tau_{b})]$ if
$R^{\prime}(\tau_{a})>R^{\prime}(\tau_{b})$.

##  4 Method

As mentioned in the introduction section, GenIL advocates the IfO setting
while making use of the genetic algorithm. We hypothesize that the GA could
achieve a meaningful ranking for reward inference. Like other IfO methods,
GenIL uses state information to train the model. Given a demonstration dataset
that is comprised of two trajectories
$\mathcal{D}_{original}=\\{\tau_{1},\tau_{2}\\}$ with diverse performance, the
target is to learn a reward inference model trained by a neural network to
distinguish the better trajectory from the unseen trajectory pairs, i.e.,
$\sum_{s\in\tau_{x}}\mathcal{R}_{\theta}(s)<\sum_{s\in\tau_{y}}\mathcal{R}_{\theta}(s)$
if $\sum R^{\prime}(\tau_{x})>\sum R^{\prime}(\tau_{y})$. It is proved that
involving extra information is necessary to recover the correct reward
function (Brown et al., 2020). Many prior works (Palan et al., 2019; Brown et
al., 2019; Castro et al., 2019) either leverage human preference or inject
noise to provide ranking as the extra information. Appropriately ranking the
instances could be regarded as an example of the ordinal regression problem,
leading to less ambiguity (Castro et al., 2019; Brown et al., 2020). This work
follows the prior framework and proposes a novel learning paradigm GenIL, that
leverages genetic algorithms as the extra information to achieve ranking and
assist the reward inference. Figure 2 demonstrates the working process of
GenIL.

GenIL consists of two components. (1) The genetic algorithm part operates
crossover and mutation steps on two trajectories randomly sampled from the
dataset, and outputs a ”fake” trajectory, i.e.,
$\tau_{fake}=\\{s_{i}|s_{i}\in\tau_{1}\cup\tau_{2}\cup S_{mut}\\}\text{ and }$

$\sum_{s_{i}\in\tau_{fake}}R^{\prime}(s_{i})=\sum_{s_{j}\in
S_{j}\subset\tau_{1}}R^{\prime}(s_{j})+\sum_{s_{k}\in
S_{k}\subset\tau_{2}}R^{\prime}(s_{k})+\sum_{s_{n}\in
S_{mut}}R^{\prime}(s_{n})$

where $S_{mut}$ is the available mutation sample set, the states in the
mutation set is batched from all visited states. Meanwhile, in order to
maintain the randomness and continuity between states, we set the crossover
step size in a random interval that is less than 10, and the mutation step
will provide a random rank on random states. As for the selection part, we
implement simple selection criteria: If the generated offspring’s average rank
lies in the predefined interval, then this offspring is added to the
corresponding ranking dataset. After selection steps, the ranking dataset is
combined with the original dataset as the ranked dataset, i.e.,
$D_{ranked}=D_{original}+D_{fake}$. In the experiment, we treat the number of
generated offspring as a hyperparameter and set its value as 12 based on trial
and error. Implementing GA on a generated dataset could make better use of the
data and outperform prior methods on data efficiency. (2) IRL part learns a
reward inference model from the generated ranked dataset. In order to extract
features from frames, we first implement a four-layer convolutional neural
network, followed by a multilayer perceptron(MLP) to reference reward. The
network takes trajectories as input and outputs an expected reward of the
given trajectory. Similar to prior work, the model is trained in a supervised
learning fashion with the pairwise ranking loss adapted from (Brown et al.,
2019):

$\mathcal{L}(\theta)\approx-\sum_{\tau_{i},\tau_{j}}\log\frac{\exp\sum_{s\in\tau_{j}}R_{\theta}(s)}{\exp\sum_{s\in\tau_{i}}R_{\theta}(s)+\exp\sum_{s\in\tau_{j}}R_{\theta}(s)}$

where $\sum_{s\in\tau_{j}}R^{\prime}(s)>\sum_{s\in\tau_{i}}R^{\prime}(s)$.
This loss function is in the form of Plackett-Luce model (Plackett, 1975;
Luce, 2012), which demonstrates effectiveness in learning a model from ranked
instance by neural network (Christiano et al., 2017; Mohlin et al., 2020). The
obtained reward function parameter $\theta$ could be further used by other
reinforcement learning algorithms to obtain the policy. The algorithmic
description of GenIL is presented in Algorithm 1.

##  5 Experiments

The algorithm GenIL proposed above implements a basic genetic algorithm under
imitation from observation paradigms. We hypothesize that the implementation
of the genetic algorithm could make better use of the suboptimal data and
achieve competitive performance while achieving data efficiency and
robustness. This section introduces the experimental design to validate our
hypothesis and discuss the results.

Figure 3: Extrapolation graphical comparison. The green points are the data
used for training, and the red points are the unseen trajectories for
prediction. The predicted and ground truth returns are normalized into the
same range for comparison.

###  5.1 Setup

We evaluate GenIL on five prevalent benchmarks on GPU NVIDIA Quadro RTX 5000.
Two robotic tasks by the Mujoco simulator (Todorov et al., 2012) within OpenAI
Gym (Brockman et al., 2016): Hopper, HalfCheetah, and three Atari tasks:
Breakout, Beamrider, SpaceInvaders.

We implement a three-layer neural network to represent the reward parameter
with 256 neurons and the ReLU activation function for each layer. For Mujoco
tasks, we directly use the state information provided by the simulator to
train the model. While in Atari tasks, we use the raw frames as input so that
we add a four-layer convolutional neural network in front of the fully
connected layers with a leaky-ReLU activation function for each layer. To
avoid the “causal confusion” problem (de Haan et al., 2019), which establishes
a wrong relationship with the irrelevant features, we mask the indicators part
such as score and remaining life.

Referring to the recent approach, we use the proximal policy optimization(PPO)
(Schulman et al., 2017) implemented by OpenAI baselines (Dhariwal et al.,
2017) with default parameters and reward function for generating the dataset.
The PPO training is checkpointed every 20 training steps. To represent the
difference in agent performance, we recover two agents, one from a checkpoint
in the early stage and another close to the end. For Atari tasks, we use
checkpoints 400 and 1000, while under the Mujoco domain, we choose checkpoints
40 and 220 as the input. The interactions between the recovered agents and the
task environment are recorded as trajectories. To ensure evaluation fairness,
the initial trajectories are recorded and serve as the input for other
baseline methods. Together with the GA-generated trajectories, these
trajectories are sub-sampled into about 5000 snippets with various lengths
ranging from 100 to 300 and feed into the network. As for the hyperparameters
for GA, we set the fixed mutation rate and crossover rate to 0.05 and 0.9,
respectively. To obtain the policy from the extrapolated reward parameter, we
train the policy over 480 training steps in the Mujoco domain, while in the
Atari domain, we evaluate the policy with 3000 training steps.

We compared the average performance between GenIL and other methods such as
BC, T-REX and D-REX from 20 trials that trained five models in each trial with
various random seeds. Specifically, as there is relatively little work on
using extrapolation to learn reward functions for imitation learning, we
compared the extrapolation performance with T-REX on aspects like accuracy and
robustness.

###  5.2 Result

We hypothesize that GenIL could achieve better extrapolation with the help of
the basic genetic algorithm over two aspects: (1) The extrapolation accuracy
on the unseen trajectories, we use the ratio of the normalized predicted
return and ground truth, i.e.,
$average(\frac{R_{\theta}(\tau_{t})}{R^{*}(\tau_{t})})$, to measure it. (2)
The overall performance of the trained agents on the target domain, which is
measured by the ground truth return obtained from simulation.

Figure 3 demonstrates the extrapolation comparison between the proposed GenIL
and the previous extrapolation algorithms T-REX and D-REX under the Mujoco
domain. The green points represent two training trajectories generated from
deviated checkpoints. The unseen trajectories that could be better or even
worse are depicted as the red points, and we aim to extrapolate compact
predictive rewards for these unseen trajectories. The x-axis represents the
ground truth returns of various demonstration levels, while the y-axis is the
return predicted by the extrapolation model. The expected and ground truth
returns are scaled into the same range for convenience. The dashed line is an
indicator to demonstrate the deviation between predicted and ground truth
returns.

Table 1: The policy performance comparison between GenIL and previous method T-REX. The value in this table is obtained from 20 trials with different random seeds.  | GenIL | T-REX | D-REX | BC
---|---|---|---|---
Tasks | Avg | Std | Avg | Std | Avg | Std | Avg | Std
HalfCheetah | 1765.9 | 383.7 | 1397.3 | 408.7 | 378.4 | 542.1 | -364.3 | 2.0
Hopper | 1693.0 | 657.3 | 1342.1 | 473.8 | 482.1 | 315.2 | 800.6 | 30.9
Beamrider | 927.6 | 647.2 | 825.4 | 265.5 | 843.7 | 176.3 | 477.2 | 155.5
Breakout | 17.5 | 6.3 | 14.1 | 5.9 | 11.8 | 2.9 | 2.1 | 4.1
Spaceinvaders | 478.1 | 192.5 | 364.3 | 151.2 | 299.3 | 87.6 | 127.3 | 85.4

From Figure 3, we can see all three extrapolation methods perform better in
Halfcheetah compared to Hopper, and their predictions are closer to the actual
value. In HalfCheetah, the unseen trajectories are intensively located at the
top-right part of the plot, which indicates the original PPO policy gradually
converges at the true reward of 1500. In contrast, in Hopper, most of the
unseen trajectories are concentrated around the true reward of 4000. As for
the comparison between methods, GenIL presents smaller vertical deviations in
the prediction for data points with similar ground-truth rewards, which means
GenIL takes advantage of the generated fake trajectories and makes a more
compact and robust prediction for unseen trajectories.

Figure 4: Policy performance change with respect to crossover step size. The
blue area reflects policy performance over from 10 trials for each crossover
step size under various random seeds. The red line is the performance’s
average standard deviation from five trained models of each trial using the
same crossover step size.

Table 1 compared the policy performance between GenIL and previous methods.
The value in this table is obtained from 20 trials with different random
seeds. From Table 1, we can conclude that GenIL outperforms the previous
method in all tasks. The obtained policy maintains a competitive performance
in different tasks over previous methods using limited demonstrations. The
amount of inputs seems to have less influence on GenIL and T-REX. In contrast,
the demonstration quality significantly restricts BC and D-REX. BC fails to
learn meaningful policy in most of the tasks, the demonstrations set up an
upper bound for BC’s performance. Compared to T-REX and GenIL, the standard
deviation of D-REX’s performance is the smallest, which indicates that D-REX
is more stable than T-REX and GenIL. The embedding BC process generates
sufficient demonstrations in each rank so that the produced policy can be more
stable. However, the BC process limited its performance. This could explain
why BC and D-REX perform poorly in some tasks simultaneously. Comparing the
performance between two classes of tasks, GenIL’s performance deviation in the
discrete Atari tasks is much larger than the deviation in continuous Mujoco
tasks.

For the Mujoco tasks, BC fails to learn meaningful policy in HalfCheetah, as
the suboptimal demonstrations might not be sufficient to establish an
executable mapping between states and actions. At the same time, BC’s
performance is also limited by the “compounding error” (Ross and Bagnell,
2010) so that the learned policy could not recover from the unseen states.
D-REX is also influenced by the BC limitation and fails to extrapolate good
reward parameters. But the effect of the numerous BC-generated trajectories
indicates that the performance deviation significantly depends on the number
of training samples, even if the samples are far suboptimal. T-REX achieves
good policy performance in HalfCheetah and Hopper and slightly outperforms the
suboptimal demonstration, but the deviation of the policy performance is the
largest overall evaluated method. From Table 1, we can see that GenIL also
achieves better performance in HalfCheetah and Hopper compared with other
evaluated methods, especially in HalfCheetah, GenIL surpasses the
demonstrations and T-REX by a large margin, which is consistent with Figure 3
that GenIL makes more compact and stable reward predictions of the unseen
data.

Throughout experiments, we find that the intrinsic parameters of genetic
algorithms could influence learning performance. For example, when the
difference between the initial input trajectories is significant, increasing
the number of ranks could lead to more accurate extrapolation, better policy
performance, and smaller variance. However, when the difference between the
initial input trajectories is small, fewer ranks could obtain good performance
as well as save time in finding the candidates for the end ranks. The number
of generated fake trajectories also plays a critical role in extrapolation.
The predictions of the unseen data clustered more compact when more fake
offspring are used in training, which presents similar characteristics as the
D-REX. Another important parameter in GenIL could be the ratio between the
crossover step size and the sub-sampling size. To ensure the effectiveness of
crossover, we set the crossover step size to less than 10, while the sub-
sampling size is about 200. In this case, there is a sufficient number of
small snippets from the initial trajectories in the fake trajectories after
crossover, and the number of small snippets from the good initial trajectory,
in fact, becomes the indicator of the strength of the fake trajectories. Take
the HalfCheetah domain as an example, we evaluated the policy performance
under different crossover step sizes (see Figure 4).

In Figure 4, the x-axis is the different crossover step sizes, the left y-axis
is the policy performance, and the right y-axis reflects the standard
deviation over five models of each trial. According to Figure 4, we can see
the crossover step size does not have an obvious influence on the upper bound
of the policy performance, but the consistency of the policy performance is
significantly impacted. When the crossover step size is too large compared to
the subsampling size, the crossover effect is significantly reduced, and the
differences between ranks become more blurred. As reflected in the policy
performance and the standard deviation of each trial, the trained agents vary
more significantly and behave more unstable when the crossover step size is
too large. On the other hand, when the crossover step size is too small, the
policy performance between trials becomes more consistent, but the standard
deviation of each trial becomes larger. We suspect the reason for this problem
is that the dynamic transition consistency cannot preserve well, which makes
the fake trajectories fragmented.

##  6 Limitations

There are still some challenges in making better use of genetic algorithms in
imitation learning. An important issue is the need for more dynamic
hyperparameter selection. The genetic algorithm process introduces more
hyperparameters for imitation learning. In this work, the hyperparameters are
selected through trial and error. Future work is needed to achieve better
optimization. Dynamic hyperparameter selection prevents dense crossovers and
mutations from fragmenting and randomizing the generated trajectories. How to
balance the generalization and fragmentation caused by genetic algorithms in
imitation learning could be an interesting topic for further research. Since
GenIL uses the same ranking for all observations in a trajectory, this may not
make much sense. Future research could use statistics such as observational
visit frequency or action frequency to differentiate segments and weigh more
meaningful parts. More advanced selection rules and learning paradigms in
GenIL can also be used in future work to improve inference and overall
performance.

##  7 Conclusion

In this paper, we presented GenIL, a reward extrapolation method based on the
combination of genetic algorithms and inverse reinforcement learning. GenIL
leveraged crossover and mutation to reproduce the demonstration improvement
process from far suboptimal to better and inferred the reward function
parameter through IRL from the resulting ranking dataset. This extrapolation
technique allowed us to make better use of the suboptimal demonstrations and
eliminate the laborious preference process for experts. From the experiments,
we have shown that GenIL has not only small fluctuations in extrapolation but
also better overall policy performance than previous methods.

## References

  * Andrychowicz et al. [2017] Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Pieter Abbeel, and Wojciech Zaremba.  Hindsight experience replay.  In Advances in neural information processing systems, pages 5048–5058, 2017.
  * Aytar et al. [2018] Yusuf Aytar, Tobias Pfaff, David Budden, Tom Le Paine, Ziyu Wang, and Nando de Freitas.  Playing hard exploration games by watching youtube.  arXiv preprint arXiv:1805.11592, 2018.
  * Bain and Sammut [1999] Michael Bain and Claude Sammut.  A framework for behavioural cloning.  In Machine Intelligence 15, pages 103–129. Oxford University Press, 1999.
  * Brockman et al. [2016] Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba.  Openai gym.  arXiv preprint arXiv:1606.01540, 2016.
  * Brown et al. [2019] Daniel Brown, Wonjoon Goo, Prabhat Nagarajan, and Scott Niekum.  Extrapolating beyond suboptimal demonstrations via inverse reinforcement learning from observations.  In International conference on machine learning, pages 783–792. PMLR, 2019.
  * Brown et al. [2020] Daniel S Brown, Wonjoon Goo, and Scott Niekum.  Better-than-demonstrator imitation learning via automatically-ranked demonstrations.  In Conference on robot learning, pages 330–359. PMLR, 2020.
  * Castro et al. [2019] Pablo Samuel Castro, Shijian Li, and Daqing Zhang.  Inverse reinforcement learning with multiple ranked experts.  arXiv preprint arXiv:1907.13411, 2019.
  * Chang et al. [2015] Kai-Wei Chang, Akshay Krishnamurthy, Alekh Agarwal, Hal Daumé III, and John Langford.  Learning to search better than your teacher.  In International Conference on Machine Learning, pages 2058–2066. PMLR, 2015.
  * Christiano et al. [2017] Paul Christiano, Jan Leike, Tom B Brown, Miljan Martic, Shane Legg, and Dario Amodei.  Deep reinforcement learning from human preferences.  arXiv preprint arXiv:1706.03741, 2017.
  * Codevilla et al. [2018] Felipe Codevilla, Matthias Müller, Antonio López, Vladlen Koltun, and Alexey Dosovitskiy.  End-to-end driving via conditional imitation learning.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 4693–4700. IEEE, 2018.
  * Darwin [1859] Charles Darwin.  The origin of species by means of natural selection.  Pub One Info, 1859.
  * de Haan et al. [2019] Pim de Haan, Dinesh Jayaraman, and Sergey Levine.  Causal confusion in imitation learning.  Advances in Neural Information Processing Systems, 32:11698–11709, 2019.
  * De Jong [1975] Kenneth Alan De Jong.  An analysis of the behavior of a class of genetic adaptive systems. University of Michigan, 1975.
  * Dhariwal et al. [2017] Prafulla Dhariwal, Christopher Hesse, Oleg Klimov, Alex Nichol, Matthias Plappert, Alec Radford, John Schulman, Szymon Sidor, Yuhuai Wu, and Peter Zhokhov.  Openai baselines, 2017.
  * Ding et al. [2019] Yiming Ding, Carlos Florensa, Mariano Phielipp, and Pieter Abbeel.  Goal-conditioned imitation learning.  arXiv preprint arXiv:1906.05838, 2019.
  * Duan et al. [2017] Yan Duan, Marcin Andrychowicz, Bradly C Stadie, Jonathan Ho, Jonas Schneider, Ilya Sutskever, Pieter Abbeel, and Wojciech Zaremba.  One-shot imitation learning.  arXiv preprint arXiv:1703.07326, 2017.
  * Eliya and Herrmann [2020] Roy Eliya and J Michael Herrmann.  Evolutionary selective imitation: Interpretable agents by imitation learning without a demonstrator.  arXiv preprint arXiv:2009.08403, 2020.
  * Goldberg [2006] David E Goldberg.  Genetic algorithms.  Pearson Education India, 2006.
  * Ho and Ermon [2016] Jonathan Ho and Stefano Ermon.  Generative adversarial imitation learning.  Advances in neural information processing systems, 29:4565–4573, 2016.
  * Holland [1992] John H Holland.  Adaptation in natural and artificial systems: an introductory analysis with applications to biology, control, and artificial intelligence.  MIT press, 1992.
  * Jalali et al. [2019] Seyed Mohammad Jafar Jalali, Parham M Kebria, Abbas Khosravi, Khaled Saleh, Darius Nahavandi, and Saeid Nahavandi.  Optimal autonomous driving through deep imitation learning and neuroevolution.  In 2019 IEEE International Conference on Systems, Man and Cybernetics (SMC), pages 1215–1220. IEEE, 2019.
  * Karakatič and Podgorelec [2015] Sašo Karakatič and Vili Podgorelec.  A survey of genetic algorithms for solving multi depot vehicle routing problem.  Applied Soft Computing, 27:519–532, 2015.
  * Liu et al. [2018] YuXuan Liu, Abhishek Gupta, Pieter Abbeel, and Sergey Levine.  Imitation from observation: Learning to imitate behaviors from raw video via context translation.  In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 1118–1125. IEEE, 2018.
  * Liu et al. [2019] Naijun Liu, Tao Lu, Yinghao Cai, Boyao Li, and Shuo Wang.  Hindsight generative adversarial imitation learning.  arXiv preprint arXiv:1903.07854, 2019.
  * Luce [2012] R Duncan Luce.  Individual choice behavior: A theoretical analysis.  Courier Corporation, 2012.
  * Mohlin et al. [2020] Erik Mohlin, Robert Östling, and Joseph Tao-yi Wang.  Learning by similarity-weighted imitation in winner-takes-all games.  Games and Economic Behavior, 120:225–245, 2020.
  * Palan et al. [2019] Malayandi Palan, Nicholas C Landolfi, Gleb Shevchuk, and Dorsa Sadigh.  Learning reward functions by integrating human demonstrations and preferences.  arXiv preprint arXiv:1906.08928, 2019.
  * Park et al. [2008] GaLam Park, Syungkwon Ra, ChangHwan Kim, and JaeBok Song.  Imitation learning of robot movement using evolutionary algorithm.  IFAC Proceedings Volumes, 41(2):730–735, 2008.
  * Plackett [1975] Robin L Plackett.  The analysis of permutations.  Journal of the Royal Statistical Society: Series C (Applied Statistics), 24(2):193–202, 1975.
  * Ross and Bagnell [2010] Stéphane Ross and Drew Bagnell.  Efficient reductions for imitation learning.  In Proceedings of the thirteenth international conference on artificial intelligence and statistics, pages 661–668. JMLR Workshop and Conference Proceedings, 2010.
  * Russell [1998] Stuart Russell.  Learning agents for uncertain environments.  In Proceedings of the eleventh annual conference on Computational learning theory, pages 101–103, 1998.
  * Schulman et al. [2017] John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov.  Proximal policy optimization algorithms.  arXiv preprint arXiv:1707.06347, 2017.
  * Sermanet et al. [2018] Pierre Sermanet, Corey Lynch, Yevgen Chebotar, Jasmine Hsu, Eric Jang, Stefan Schaal, Sergey Levine, and Google Brain.  Time-contrastive networks: Self-supervised learning from video.  In 2018 IEEE international conference on robotics and automation (ICRA), pages 1134–1141. IEEE, 2018.
  * Todorov et al. [2012] Emanuel Todorov, Tom Erez, and Yuval Tassa.  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems, pages 5026–5033. IEEE, 2012.
  * Torabi et al. [2019] Faraz Torabi, Garrett Warnell, and Peter Stone.  Imitation learning from video by leveraging proprioception.  arXiv preprint arXiv:1905.09335, 2019.
  * Zheng et al. [2021] Boyuan Zheng, Sunny Verma, Jianlong Zhou, Ivor Tsang, and Fang Chen.  Imitation learning: Progress, taxonomies and opportunities.  arXiv preprint arXiv:2106.12177, 2021.
  * Zhu et al. [2021] Zhuangdi Zhu, Kaixiang Lin, Bo Dai, and Jiayu Zhou.  Off-policy imitation learning from observations.  arXiv preprint arXiv:2102.13185, 2021.
  * Zuo et al. [2020] Guoyu Zuo, Qishen Zhao, Kexin Chen, Jiangeng Li, and Daoxiong Gong.  Off-policy adversarial imitation learning for robotic tasks with low-quality demonstrations.  Applied Soft Computing, 97:106795, 2020.


# Scheduling of Distributed Applications on the Computing Continuum: A Survey

Narges Mehran⋆, Dragi Kimovski⋆, Hermann Hellwagner⋆, Dumitru Roman‡§, Ahmet
Soylu§, Radu Prodan⋆ ⋆Alpen-Adria-Universität Klagenfurt, Austria
‡SINTEF AS, Oslo, Norway
§OsloMet - Oslo Metropolitan University, Oslo, Norway
Email<EMAIL_ADDRESS>
Email<EMAIL_ADDRESS>
###### Abstract

The demand for distributed applications has significantly increased over the
past decade, with improvements in machine learning techniques fueling this
growth. These applications predominantly utilize Cloud data centers for high-
performance computing and Fog and Edge devices for low-latency communication
for small-size machine learning model training and inference. The challenge of
executing applications with different requirements on heterogeneous devices
requires effective methods for solving NP-hard resource allocation and
application scheduling problems. The state-of-the-art techniques primarily
investigate conflicting objectives, such as the completion time, energy
consumption, and economic cost of application execution on the Cloud, Fog, and
Edge computing infrastructure. Therefore, in this work, we review these
research works considering their objectives, methods, and evaluation tools.
Based on the review, we provide a discussion on the scheduling methods in the
Computing Continuum.

###### Index Terms:

Scheduling, Placement, Energy efficiency, Cloud, Edge, Computing Continuum.

2023 ACM/IEEE. Personal use of this material is permitted. Permission from
ACM/IEEE must be obtained for all other uses, in any current or future media,
including reprinting/republishing this material for advertising or promotional
purposes, creating new collective works, for resale or redistribution to
servers or lists, or reuse of any copyrighted component of this work in other
works.

##  I Introduction

Distributed processing applications [1] encompass gathering, storing, and
analyzing massive amounts of data, gradually overwhelming centralized _Cloud_
data centers. On the other hand, _Fog and Edge computing_ technologies extend
the Cloud with computation, storage, and network services in the proximity of
the Internet of Things (IoT) devices [2]. Consequently, media, healthcare, and
manufacturing companies, to name a few, can move their latency-sensitive
applications from the Cloud data centers to utilize the Fog and Edge devices
near data producers and consumers.

As alternatives to the Cloud, infrastructures such as Exoscale Edge [3],
Google Distributed Cloud [4], along with local services provisioned by mobile
devices [5], consolidate the Fog and Edge with computing and data management
services. The unification of Cloud, Fog, and Edge infrastructures (aka.
_Computing Continuum_) aims to provide a seamless aggregation of distributed
resources of all kinds to support the emerging dataflow processing
applications [6].

Over the past few years, academia and industry investigated the challenges in
distributed application execution and scheduling on the Computing Continuum
[7]. This work reviews the state-of-the-art methods for scheduling distributed
applications on the Computing Continuum provisioned by different resource
providers.

Most scheduling and placement methods prioritize minimizing application
completion times, which is paramount in meeting users’ service level agreement
requirements. Fast completion times are a fundamental objective that the
methods address to ensure user satisfaction. Additionally, the timely delivery
of services remains a central concern for application scheduling. Moreover,
energy efficiency is a critical factor that resource allocation and scheduling
methods must consider. To underscore the magnitude of this issue, Google, for
instance, approximately consumes
$15.5\text{\,}\mathrm{TW}\text{\,}\mathrm{h}\text{/}$ of electricity annually,
with a significant portion being attributed to its data
centers111https://www.gstatic.com/gumdrop/sustainability/247-carbon-free-
energy.pdf. In addition, economic cost represents another critical parameter
that resource providers prioritize for optimizing infrastructure maintenance
expenses, ultimately benefiting their consumers. Hence, after reviewing the
research works, we categorize them based on the non-functional objectives,
such as the completion time, energy consumption, and economic cost.

The rest of the paper is structured as follows. We survey the literature
mainly addressing completion time in Section II. Section III describes the
application scheduling and resource allocation methods with the main objective
of minimizing energy consumption. Section IV categorizes the cost-optimizing
methods, followed by the discussion in Section V and the conclusion in Section
VI.

##  II Completion time

In this section, we begin by discussing the most prominent methods in the
literature, exploring the time of the application execution. Samani et al. [8]
proposed a multilayer resource partitioning method to minimize resource
wastage by utilizing the total capacity of heterogeneous Fog devices. This
method places each service on a Fog device in each partition by minimizing the
completion time of an application. Moreover, this method aims to maximize
deadline satisfaction in the Fog with a high arrival rate of requests.

Skarlat et al. [9] explored the Fog service placement problem and modeled it
as an integer programming model by optimizing the IoT application’s completion
time on Fog and Cloud resources. Therefore, in this method, an orchestrator
allocates the resources of the Fog data centers to users’ applications and
proactively collects periodic updates to satisfy the QoS metrics, such as the
deadline for the application’s completion and processing times.

Veith et al. [10] proposed a scheduling strategy called response time rate
with region patterns, which uses a greedy strategy to identify the resources
that minimize the service completion time on the Cloud and Fog. This method
decomposes the application based on dataflow patterns such as a fork or a join
and distributes it to the Cloud and Fog computing infrastructures.

Veith et al. [11] applied reinforcement learning and the Monte-Carlo tree
search algorithm to reschedule application operators during runtime. This
method formulates the operator assignment problem as a Markov decision process
to minimize the application’s completion time. Afterward, the learning
algorithm determines the reconfiguration of the resource allocation to the
operators.

Xia et al. [12] proposed four combined scheduling heuristics, such as Fog
devices and application components ordering, optimizing the weighted average
completion time for a large set of heterogeneous applications constrained by a
group of non-functional parameters, including processing and storage
capabilities.

Souza et al. [13] applied Min-Max heuristics to optimize the service
completion time. Best-fit with the queue method performs service atomization
to represent parallel and sequential service execution strategies. It analyzes
the service request and the expected availability time for Fog devices. The BQ
method minimizes the service’s transmission and processing times while
maximizing the priority of the Edge devices for the microservices waiting in a
processing queue.

Sun et al. [14] investigated a two-level scheduling model categorizing Fog
devices in clusters based on their locations. Afterward, the scheduling method
decides on the appropriate Fog cluster and the proper device within the given
cluster. The weighted multi-objective optimization method reduces the service
completion time and maximizes the reliability of application execution.

Elgamal et al. [15] proposed an algorithm to partition operations of an IoT
application on Edge and Cloud devices to minimize operations’ completion
times. This method includes data processing, queuing, and the tradeoff between
processing and transmission when placing operators on heterogeneous devices.

Khare et al. [16] presented an optimization-based scheduling method to
minimize the application’s completion time. This method decomposes an
application graph into several linear paths from the application’s source to
the sink. Afterward, it applies an execution-time prediction model for co-
located linear dependencies to minimize the completion times of all paths in
the application’s graph.

Ravindra et al. [17] proposed an open-source orchestration platform for
application execution on the Cloud, Fog, and Edge devices. This platform
supports streams, micro-batches, and various data processing frameworks like
Apache Edgent, Storm, and Spark. The modeled orchestrator supports the
migration of application components if the resource reaches an over-utilized
state by executing a high workload of operators and application components.

Renart et al. [18] extended a data analytics software framework called
R-Pulsar to solve the placement problem of IoT operators on the Edge and Cloud
devices. This method reduces data transfer rate, completion time, and economic
cost (based on AWS and Microsoft pricing models). It divides the IoT
application graph into paths consisting of sequences of operators. Afterward,
the longest path defines the completion time, including data transmission
times between operators over the path.

Summary. The works investigate a single [10, 11], weighted set of objectives
[15, 9], multi-objective [14, 17, 18, 13], or predictive [16] optimization
models. They do not minimize the cost and energy consumption of an
application’s execution on the heterogeneous Computing Continuum.

##  III Energy consumption

A growing body of literature has recently described various methods to curb
energy consumption. Kansal et al. [19] proposed a linear regression-based
method to reduce the energy consumption of virtual machines. The method
considers static and dynamic power consumption of a device’s processor,
memory, and storage. Therefore, it monitors the resource utilization of
virtual machines with the help of a virtualization monitoring tool, retrains
the regression-based model, and estimates the energy consumption.

Al Faruque et al. [20] proposed a decentralized optimization-based scheme in
which distributed controllers provide the energy management service in a Fog
computing infrastructure. This method manages the energy consumption of
residential buildings and all devices, such as sensors and actuators, along
with computing and network devices. The control-as-a-service architecture
module manages the devices to decrease energy consumption, cost, and time for
their product to be available in the market.

Shojafar et al. [21] proposed an energy-adaptive resource scheduler to
maximize computational efficiency while maintaining the user’s satisfaction.
The main goal of this method was to minimize energy consumption while
executing the application in the Fog infrastructure. This scheduler
consolidates the resources by managing the application execution without
reconfiguring virtual machines.

Pooranian et al. [22] designed a penalty-aware heuristic algorithm to minimize
processing and transmission energy in the Fog and preserve load balancing
among the data centers. Their penalty-aware algorithm assigns a negative score
to a Fog data center consuming more energy and avoids allocating its resources
to applications during the subsequent runtime iteration.

You et al. [23] proposed an energy-efficient asynchronous mobile edge
computation offloading method. This method solves the optimization-based
computation offloading problem to obtain a decision between local processing
on a mobile device and offloading the computation to the Edge infrastructure.

Reddy et al. [24] proposed a genetic-based model to minimize the energy
consumption of the Fog devices. This model reduces the number of service
requests failing to perform their operations while shortening the overall
execution time. This method applies a reinforcement learning model to optimize
the energy consumption of Fog devices while executing the applications.

Menouer [25] presented a scheduling model based on preference, similar to the
Technique for Order Preference by Similarity to Ideal Solution (TOPSIS) [26]
that optimizes multiple criteria, including resource utilization and energy
consumption. A decision-making algorithm reduces the processing, memory,
storage resource utilization, and power consumption of resources, aimed at
satisfying the user’s and resource provider’s requirements while balancing
them for executing every application.

Summary. These works optimize either a single constrained objective [19, 22,
21, 23] or bi-objective [25] model and do not focus on minimizing cost along
with the energy consumption of an application’s execution on the heterogeneous
Computing Continuum.

##  IV Economic cost

Recently, considerable ongoing research and effort has been dedicated to the
economic cost aspect within the Computing Continuum. Aazam et al. [27]
proposed a method to manage the Fog devices as a heterogeneous pool for data
processing with unpredictable resource demands. Therefore, the resource
provider considers the application requirements, such as the type and price of
the service, to reduce the economic cost of service execution in the Fog while
encouraging the application providers to use this infrastructure.

Zhao et al. [28] proposed a price-based competition between the heterogeneous
Edge and Cloud resources, while this method balances all the providers’
profits. Their proposed method maximizes both providers’ profit and users’
satisfaction. The Edge resources are more profitable when the cost is a user’s
essential metric.

De Maio and Kimovski [29] investigated a parallel task decomposition method
that could potentially improve the Fog’s completion time, reliability, and
monetary cost of extreme data workflows. They evaluated the Pareto-based
method with four use-case workflows from the field of natural sciences through
the Spark-enabled mobile Edge offloading Monte-Carlo simulator and extended
FogTorchPI [30]. Moreover, it categorized the workflow’s tasks based on their
dependencies and devised the independent tasks’ offloading to the Fog
infrastructure.

Sharghivand et al. [31] proposed a double-sided matching scheduler for data
analytics tasks at the Edge based on the device and application preferences
toward lower completion time and cost. This method uses game theory principles
to maximize the aggregated users’ and devices’ utilities. In particular, it
improves the application completion time, economic cost, service deadline, and
the Edge service violation when a device fails to complete its execution
within the deadline.

Nguyen et al. [32] proposed an optimization-based service placement method to
balance the tradeoff between total operating cost and service quality. This
optimization method aims to minimize the total operating cost for a service
provider and maximize the quality of the service in terms of network delay.

Li et al. [33] proposed a Cloud-based video streaming service called CVS2 that
enables on-demand transcoding of video streams. CVS2 focuses on the tradeoff
between the processing time and cost to encode on-demand video streams with
different qualities. This method aims to maintain a robust QoS for viewers and
minimize the cost for the video service providers.

Ni et al. [34] proposed a priced-timed Petri net-based strategy for resource
allocation in a Fog computing infrastructure. This method represents IoT tasks
in the Fog as a priced-timed Petri net ordered by the tasks’ completion times
and the user’s costs of their execution. Priced-timed Petri nets [35]
generalize classic Petri nets, incorporating continuous-time clocks, real-time
constraints, and computation pricing. A heuristic algorithm allocates IoT
applications to Fog devices to minimize the completion time and maximize
financial savings for the resource and application providers.

Pham et al. [36] proposed a heuristic algorithm for task scheduling on the
Cloud and Fog devices to maximize the aggregated utility of cost and
completion time. This method ranks the application’s tasks based on the
critical path length from every task to the exit task. Moreover, the method
assumes that the total cost of executing the application on the Fog devices is
lower than the Cloud because the Fog provider does not charge for its local
executions.

Summary. These works optimize two weighted objectives [33, 32, 34, 36, 24, 31,
28] combined in a nonlinear, prediction-based or multi-objective model [29].
However, they do not focus on the energy consumption of the application
execution on the Computing Continuum, along with the application’s completion
time and cost.

##  V Discussion

We briefly describe the main contributions of the existing works and identify
the research directions. We classify them based on their primary objectives
for optimization and methodologies.

Table I presents an overview of the prevailing research efforts discussed in
the previous sections. The table classifies the research works based on the
optimization metrics they use. Furthermore, it presents the factors of
processing time, latency, and bandwidth influencing the completion time.

As we observe in Table I, most methods optimize the factors influencing the
completion time (41%), network latency, and bandwidth. In addition to these
objectives, only a smaller fraction focuses on reducing energy consumption
(29.5%) and economic costs (29.5%). We summarize in Figure 1 the percentage of
research articles in this survey that address the aforementioned objectives.
Therefore, we can conclude that the currently available techniques do not
adequately address the energy efficiency issues and economic costs essential
for the resource providers.

TABLE I: Classification of the research works according to scheduling optimization metrics. | _Metric_
---|---
_Reference_ |  Completion time | Latency | Bandwidth | Energy consumption | Economic cost
Samani et al. [8] | ✓ | ✓ | ✓ |  |
Skarlat et al. [9] | ✓ | ✓ |  |  |
Veith et al. [10] | ✓ | ✓ | ✓ |  |
Veith et al. [11] | ✓ | ✓ | ✓ |  |
Xia et al. [12] | ✓ | ✓ | ✓ |  |
Souza et al. [13] | ✓ |  | ✓ |  |
Sun et al. [14] | ✓ | ✓ | ✓ |  |
Elgamal et al. [15] | ✓ |  | ✓ |  |
Khare et al. [16] | ✓ | ✓ |  |  |
Ravindra et al. [17] | ✓ |  | ✓ |  |
Renart et al. [18] | ✓ | ✓ | ✓ |  | ✓
Kansal et al. [19] | ✓ |  |  | ✓ |
Al Faruque et al. [20] |  |  |  | ✓ | ✓
Shojafar et al. [21] | ✓ | ✓ | ✓ | ✓ |
Pooranian et al. [22] | ✓ |  | ✓ | ✓ |
You et al. [23] |  | ✓ | ✓ | ✓ | ✓
Reddy et al. [24] | ✓ | ✓ | ✓ | ✓ |
Menouer [25] | ✓ |  |  | ✓ |
Aazam et al. [27] | ✓ |  | ✓ |  | ✓
Zhao et al. [28] | ✓ |  |  |  | ✓
De Maio et al. [29] | ✓ | ✓ | ✓ |  | ✓
Sharghivand et al. [31] | ✓ |  |  |  | ✓
Nguyen et al. [32] | ✓ | ✓ | ✓ |  | ✓
Li et al. [33] | ✓ |  |  |  | ✓
Ni et al. [34] | ✓ |  |  |  | ✓
Pham et al. [36] | ✓ |  | ✓ |  | ✓
Figure 1: Percentages of research articles addressing the time, energy, or
cost objectives.

Table II further summarizes the research works based on the optimization
methods and core algorithms used. We can observe that the majority of methods
are based on heuristic techniques. However, considering the other optimization
algorithms, other works use several possible methods, including graph theory
and machine learning. Figure 2 shows that most research works propose linear-,
nonlinear-programming, or heuristic-based scheduling methods.

In terms of evaluation tools, Table III reveals that most of the works use
either simulation or a real testbed to evaluate the placement and scheduling
methods. Only a small fraction implements both testbed infrastructures and
simulation. Figure 3 depicts the ratio of the research papers evaluating their
methods through the simulation or real testbed experiments.

TABLE II: Classification of the research works according to optimization methods. | _Method_
---|---
_Reference_ |  Non/- linear programming |  Heuristic | Game theory | Graph theory | Machine learning
Samani et al. [8] |  |  |  | ✓ |
Skarlat et al. [9] | ✓ |  |  |  |
Veith et al. [10] | ✓ |  |  | ✓ |
Veith et al. [11] |  |  |  | ✓ | ✓
Xia et al. [12] | ✓ |  |  |  |
Souza et al. [13] |  | ✓ |  |  |
Sun et al. [14] |  | ✓ |  |  |
Elgamal et al. [15] | ✓ |  |  |  |
Khare et al. [16] |  | ✓ |  |  | ✓
Ravindra et al. [17] |  | ✓ |  |  |
Renart et al. [18] | ✓ |  |  |  |
Kansal et al. [19] |  |  |  |  | ✓
Al Faruque et al. [20] |  | ✓ |  |  |
Shojafar et al. [21] | ✓ |  |  |  |
Pooranian et al. [22] | ✓ |  |  |  |
You et al. [23] | ✓ |  |  |  |
Reddy et al. [24] |  | ✓ |  |  | ✓
Menouer [25] |  | ✓ |  |  |
Aazam et al. [27] | ✓ |  |  |  |
Zhao et al. [28] |  |  | ✓ |  |
De Maio et al. [29] |  | ✓ |  |  |
Sharghivand et al. [31] |  |  | ✓ |  |
Nguyen et al. [32] | ✓ |  |  |  |
Li et al. [33] |  | ✓ |  |  |
Ni et al. [34] |  | ✓ |  |  |
Pham et al. [36] |  | ✓ |  |  |
Figure 2: Percentages of research articles presenting different methods. TABLE III: Classification of the research works according to evaluation tools. | _Evaluation tool_
---|---
| Simulation | Real
_Reference_ | CloudSim | iFogSim | SimGrid | FogTorchPI | SLEIPNIR | OMNET++ | YAFS | Matlab | testbed
Samani et al. [8] |  |  |  |  |  |  | ✓ |  | ✓
Skarlat et al. [9] |  | ✓ |  |  |  |  |  |  |
Veith et al. [10] |  |  |  |  |  | ✓ |  |  |
Veith et al. [11] |  |  |  |  |  | ✓ |  |  |
Xia et al. [12] |  |  | ✓ |  |  |  |  |  |
Souza et al. [13] |  |  |  |  |  |  |  |  | ✓
Sun et al. [14] |  |  |  |  |  |  |  | ✓ |
Elgamal et al. [15] |  |  |  |  |  |  |  |  | ✓
Khare et al. [16] |  |  |  |  |  |  |  |  | ✓
Ravindra et al. [17] |  |  |  |  |  |  |  |  | ✓
Renart et al. [18] |  |  |  |  |  |  |  |  | ✓
Kansal et al. [19] |  |  |  |  |  |  |  |  | ✓
Al Faruque et al. [20] |  |  |  |  |  |  |  |  | ✓
Shojafar et al. [21] |  |  |  |  |  |  |  | ✓ |
Pooranian et al. [22] |  | ✓ |  |  |  |  |  |  |
You et al. [23] |  |  |  |  |  |  |  | ✓ |
Reddy et al. [24] |  | ✓ |  |  |  |  |  |  | ✓
Menouer [25] | ✓ |  |  |  |  |  |  |  | ✓
Aazam et al. [27] | ✓ |  |  |  |  |  |  |  |
Zhao et al. [28] |  |  |  |  |  |  |  |  | ✓
De Maio et al. [29] |  |  |  | ✓ | ✓ |  |  |  |
Sharghivand et al. [31] |  |  |  |  |  |  |  |  | ✓
Nguyen et al. [32] |  |  |  |  |  |  |  | ✓ |
Li et al. [33] |  |  |  |  |  |  |  |  | ✓
Ni et al. [34] |  |  |  |  |  |  |  |  | ✓
Pham et al. [36] | ✓ |  |  |  |  |  |  |  |
Figure 3: Percentages of research articles evaluating their methods by
simulation, real testbed, or both tools.

##  VI Conclusion

We surveyed the literature’s objectives and methodologies related to resource
provisioning and scheduling for dataflow processing applications on the Cloud,
Fog, and Edge. We categorized the research studies based on their objectives:
completion time, energy consumption, and economic cost. The classification
shows that most of the research works explored the completion time with a
focus on the processing time and that energy consumption or user’s cost for
application execution were less often addressed. We plan to extend this survey
by exploring autoscaling methods for large-scale data processing in the
Computing Continuum.

## Acknowledgement

This work received partial funding from: _European Union_ ’s grant agreements
H2020 101016835 (DataCloud), HE 101093202 (Graph-Massivizer), and HE 101070284
(enRichMyData); _Austrian Research Promotion Agency (FFG)_ , grant agreement
888098 (Kärntner Fog) and FO999897846 (GAIA).

## References

  * [1] Marcos Dias de Assuncao, Alexandre da Silva Veith, and Rajkumar Buyya.  Distributed data stream processing and edge computing: A survey on resource elasticity and future directions.  Journal of Network and Computer Applications, 103:1–17, 2018.
  * [2] Narges Mehran, Zahra Najafabadi Samani, Dragi Kimovski, and Radu Prodan.  Matching-based scheduling of asynchronous data processing workflows on the computing continuum.  In 2022 IEEE International Conference on Cluster Computing (CLUSTER), pages 58–70. IEEE, 2022.
  * [3] Exoscale Corporation.  Exoscale edge.  https://www.exoscale.com/edge/, 2023.
  * [4] Google LLC.  Extend Google cloud’s infrastructure and services to the edge and your data centers.  https://cloud.google.com/distributed-cloud/, 2023.
  * [5] Dragi Kimovski, Narges Mehran, Christopher Emanuel Kerth, and Radu Prodan.  Mobility-aware IoT applications placement in the cloud edge continuum.  IEEE Transactions on Services Computing, 15(6):3358–3371, 2022.
  * [6] Daniel Balouek-Thomert, Eduard Gibert Renart, Ali Reza Zamani, Anthony Simonet, and Manish Parashar.  Towards a computing continuum: Enabling edge-to-cloud integration for data-driven workflows.  The International Journal of High Performance Computing Applications, 33(6):1159–1174, 2019.
  * [7] Petar Kochovski, Rizos Sakellariou, Marko Bajec, Pavel Drobintsev, and Vlado Stankovski.  An architecture and stochastic method for database container placement in the edge-fog-cloud continuum.  In IEEE International Parallel and Distributed Processing Symposium (IPDPS), pages 396–405. IEEE, 2019.
  * [8] Zahra Najafabadi Samani, Narges Mehran, Dragi Kimovski, Shajulin Benedict, Nishant Saurabh, and Radu Prodan.  Incremental multilayer resource partitioning for application placement in dynamic fog.  IEEE Transactions on Parallel and Distributed Systems, 34(6):1877–1896, 2023.
  * [9] Olena Skarlat, Matteo Nardelli, Stefan Schulte, and Schahram Dustdar.  Towards QoS-aware fog service placement.  In 1st International Conference on Fog and Edge Computing (ICFEC), pages 89–96. IEEE, 2017.
  * [10] Alexandre da Silva Veith, Marcos Dias de Assunçao, and Laurent Lefèvre.  Latency-aware placement of data stream analytics on edge computing.  In International Conference on Service-Oriented Computing, pages 215–229. Springer, 2018.
  * [11] Alexandre da Silva Veith, Marcos Dias de Assunçao, and Laurent Lefèvre.  Monte-Carlo tree search and reinforcement learning for reconfiguring data stream processing on edge computing.  In 2019 31st International Symposium on Computer Architecture and High Performance Computing (SBAC-PAD), pages 48–55. IEEE, 2019.
  * [12] Ye Xia, Xavier Etchevers, Loic Letondeur, Adrien Lebre, Thierry Coupaye, and Frédéric Desprez.  Combining heuristics to optimize and scale the placement of IoT applications in the fog.  In 11th IEEE/ACM Conference on Utility and Cloud Computing, UCC, pages 153–163, 2018.
  * [13] VB Souza, Xavier Masip-Bruin, Eva Marín-Tordera, Sergio Sànchez-López, Jordi Garcia, Guang-Jie Ren, Admela Jukan, and A Juan Ferrer.  Towards a proper service placement in combined fog-to-cloud (F2C) architectures.  Future Generation Computer Systems, 87:1–15, 2018.
  * [14] Yan Sun, Fuhong Lin, and Haitao Xu.  Multi-objective optimization of resource scheduling in fog computing using an improved NSGA-II.  Wireless Personal Communications, pages 1–17, 2018.
  * [15] Tarek Elgamal, Atul Sandur, Phuong Nguyen, Klara Nahrstedt, and Gul Agha.  Droplet: Distributed operator placement for IoT applications spanning edge and cloud resources.  In 2018 IEEE 11th International Conference on Cloud Computing (CLOUD), pages 1–8. IEEE, 2018.
  * [16] Shweta Khare, Hongyang Sun, Julien Gascon-Samson, Kaiwen Zhang, Aniruddha Gokhale, Yogesh Barve, Anirban Bhattacharjee, and Xenofon Koutsoukos.  Linearize, predict and place: minimizing the makespan for edge-based stream processing of directed acyclic graphs.  In Proceedings of the 4th ACM/IEEE Symposium on Edge Computing, pages 1–14, 2019.
  * [17] Pushkara Ravindra, Aakash Khochare, Siva Prakash Reddy, Sarthak Sharma, Prateeksha Varshney, and Yogesh Simmhan.  Echo: An adaptive orchestration platform for hybrid dataflows across cloud and edge.  In International Conference on Service-Oriented Computing, pages 395–410. Springer, 2017.
  * [18] Eduard Gibert Renart, Alexandre Da Silva Veith, Daniel Balouek-Thomert, Marcos Dias de Assuncao, Laurent Lefèvre, and Manish Parashar.  Distributed operator placement for IoT data analytics across edge and cloud resources.  In CCGrid 2019 - 19th Annual IEEE/ACM International Symposium in Cluster, Cloud, and Grid Computing, pages 1–10. IEEE/ACM, 2019.
  * [19] Aman Kansal, Feng Zhao, Jie Liu, Nupur Kothari, and Arka A Bhattacharya.  Virtual machine power metering and provisioning.  In Proceedings of the 1st ACM Symposium on Cloud Computing, pages 39–50, 2010.
  * [20] Mohammad Abdullah Al Faruque and Korosh Vatanparvar.  Energy management-as-a-service over fog computing platform.  IEEE Internet of Things Journal, 3(2):161–169, 2015.
  * [21] Mohammad Shojafar, Nicola Cordeschi, and Enzo Baccarelli.  Energy-efficient adaptive resource management for real-time vehicular cloud services.  IEEE Transactions on Cloud computing, 7(1):196–209, 2016.
  * [22] Zahra Pooranian, Mohammad Shojafar, Paola G Vinueza Naranjo, Luca Chiaraviglio, and Mauro Conti.  A novel distributed fog-based networked architecture to preserve energy in fog data centers.  In IEEE 14th International Conference on Mobile Ad Hoc and Sensor Systems (MASS), pages 604–609. IEEE, 2017.
  * [23] Changsheng You, Yong Zeng, Rui Zhang, and Kaibin Huang.  Asynchronous mobile-edge computation offloading: Energy-efficient resource management.  IEEE Transactions on Wireless Communications, 17(11):7590–7605, 2018.
  * [24] K Hemant Kumar Reddy, Ashish Kr Luhach, Buddhadeb Pradhan, Jatindra Kumar Dash, and Diptendu Sinha Roy.  A genetic algorithm for energy efficient fog layer resource management in context-aware smart cities.  Sustainable Cities and Society, 63:102428, 2020.
  * [25] Tarek Menouer.  KCSS: Kubernetes container scheduling strategy.  The Journal of Supercomputing, 77(5):4267–4293, 2021.
  * [26] C-L Hwang and Abu Syed Md Masud.  Multiple objective decision making—methods and applications: a state-of-the-art survey, volume 164.  Springer Science & Business Media, 2012.
  * [27] Mohammad Aazam and Eui-Nam Huh.  Fog computing micro datacenter based dynamic resource estimation and pricing model for IoT.  In IEEE 29th International Conference on Advanced Information Networking and Applications, pages 687–694. IEEE, 2015.
  * [28] Tianchu Zhao, Sheng Zhou, Xueying Guo, Yun Zhao, and Zhisheng Niu.  Pricing policy and computational resource provisioning for delay-aware mobile edge computing.  In 2016 IEEE/CIC International Conference on Communications in China (ICCC), pages 1–6. IEEE, 2016.
  * [29] Vincenzo De Maio and Dragi Kimovski.  Multi-objective scheduling of extreme data scientific workflows in fog.  Future Generation Computer Systems, 106:171 – 184, 2020.
  * [30] A. Brogi, S. Forti, and A. Ibrahim.  How to best deploy your fog applications, probably.  In 1st IEEE International Conference on Fog and Edge Computing (ICFEC), pages 105–114, 2017.
  * [31] Nafiseh Sharghivand, Farnaz Derakhshan, Lena Mashayekhy, and Leyli Mohammadkhanli.  An edge computing matching framework with guaranteed quality of service.  IEEE Transactions on Cloud Computing, 10(3):1557–1570, 2022.
  * [32] Duong Tung Nguyen, Hieu Trung Nguyen, Ni Trieu, and Vijay K Bhargava.  Two-stage robust edge service placement and sizing under demand uncertainty.  IEEE Internet of Things Journal, 9(2):1560–1574, 2021.
  * [33] Xiangbo Li, Mohsen Amini Salehi, Magdy Bayoumi, Nian-Feng Tzeng, and Rajkumar Buyya.  Cost-efficient and robust on-demand video transcoding using heterogeneous cloud services.  IEEE Transactions on Parallel and Distributed Systems, 29(3):556–571, 2017.
  * [34] Lina Ni, Jinquan Zhang, Changjun Jiang, Chungang Yan, and Kan Yu.  Resource allocation strategy in fog computing based on priced timed Petri nets.  IEEE Internet of Things Journal, 4(5):1216–1228, 2017.
  * [35] Richard M Mayr and Parosh Aziz Abdulla.  Priced timed Petri nets.  Logical Methods in Computer Science, 9, 2013.
  * [36] Xuan-Qui Pham and Eui-Nam Huh.  Towards task scheduling in a cloud-fog computing system.  In Network Operations and Management Symposium (APNOMS), 2016 18th Asia-Pacific, pages 1–4. IEEE, 2016.