# Decision Rule Elicitation for Domain Adaptation

Alexander Nikitin<EMAIL_ADDRESS>Helsinki Institute for
Information Technology HIIT, Department of Computer Science, Aalto
UniversityEspooFinland and  Samuel Kaski<EMAIL_ADDRESS>Helsinki
Institute for Information Technology HIIT, Department of Computer Science,
Aalto UniversityEspooFinland Department of Computer Science, University of
ManchesterManchesterUK

(2021)

###### Abstract.

Human-in-the-loop machine learning is widely used in artificial intelligence
(AI) to elicit labels for data points from experts or to provide feedback on
how close the predicted results are to the target. This simplifies away all
the details of the decision-making process of the expert. In this work, we
allow the experts to additionally produce decision rules describing their
decision-making; the rules are expected to be imperfect but to give additional
information. In particular, the rules can extend to new distributions, and
hence enable significantly improving performance for cases where the training
and testing distributions differ, such as in domain adaptation. We apply the
proposed method to lifelong learning and domain adaptation problems and
discuss applications in other branches of AI, such as knowledge acquisition
problems in expert systems. In simulated and real-user studies, we show that
decision rule elicitation improves domain adaptation of the algorithm and
helps to propagate expert’s knowledge to the AI model.

human computer interaction, knowledge elicitation, domain adaptation, human-
in-the-loop, user studies

††journalyear: 2021††copyright: acmlicensed††conference: 26th International
Conference on Intelligent User Interfaces; April 14–17, 2021; College Station,
TX, USA††booktitle: 26th International Conference on Intelligent User
Interfaces (IUI ’21), April 14–17, 2021, College Station, TX, USA††price:
15.00††doi: 10.1145/3397481.3450682††isbn: 978-1-4503-8017-1/21/04††copyright:
none††ccs: Computing methodologies Learning settings††ccs: Computing
methodologies Machine learning Figure 1. We consider a task where a machine
learning model has been trained to predict breaks in a set of workstations.
When the system receives new data about the workstations, it predicts their
fault-risk and passes some of the predictions to the expert user for
evaluation. Instead of just telling whether they agree, as in current human-
in-the-loop systems, the expert gives a heuristic rule describing their
decision-making. The machine learning system uses this rule to improve its
decision making. Even though the rules will be imperfect and noisy, they will
incorporate additional information available to the human users but not the
system.

##  1\. Introduction

This work is inspired by practical needs in industry, in equipping maintenance
systems with machine learning assistance. Straightforward ”black-box” machine
learning approaches would produce a prediction, for instance, a binary
variable indicating there may be something wrong with the workstations in
Figure 1. Human-in-the-loop approaches accept feedback from human experts in
the form of corrected values. Experience with real experts in practical
maintenance systems quickly reveals that the experts have their own rules of
thumb, by which they make their maintenance decisions. While working with a
telecom company, we noticed, to our surprise, that not only were the experts
able to explicate the rules, the rules also improved the performance of the
model and showed good generalization performance.

Knowledge from domain experts has been included in automated systems at least
since the expert systems popular in the ’80s. Difficulty in eliciting sets of
consistent rules from experts was one of the most important difficulties
(Hart, 1985) explaining why expert systems are not popular anymore. Another
widely-used formulation for human input is prior elicitation, that is, getting
the prior distributions of model parameters from experts for Bayesian
inference (Garthwaite et al., 2013; Kadane et al., 1980). The elicitation can
also be done indirectly, by eliciting similarities, for instance, (Afrabandpey
et al., 2017).

Even though humans may be able to explain their decisions using formal
decision rules, using logical predicates, that is laborious and error-prone.
Psychological research of decision-making has shown that fast heuristics are
often useful for generalization, one of the most popular branches being fast
and frugal decision-making (Gigerenzer and Todd, 1999). Essentially, fast and
frugal trees are a shallow decision tree that provides a heuristic for
decision-making. Experimental studies have shown that fast and frugal
heuristics can be used as a fast alternative to fully-Bayesian decisions. In
this work, we build on the assumption that human experts either naturally use
such trees, or at least can easily generate them, and use them as inputs to
machine learning.

In this paper, we introduce a new way to elicit and use the experts’ heuristic
rules to improve machine learning. We assume the explicit feedback can be
expressed as a Boolean formula, and handle it as an output of a weak learner
(Schapire, 1990). The rules are elicited for wrongly predicted data samples.
Additionally, we show that this approach helps to deal with several modern
artificial intelligence problems where generalization to new distributions is
required: out-of-distribution generalization, lifelong learning, and learning
from the feedback.

##  2\. Related work

This work extends directly earlier work in human-in-the-loop machine learning
or human-centered machine learning (Amershi et al., 2014). The new type of
human input we introduce could be directly used in active learning (Lewis and
Gale, 1994) instead of the usual labels requested from users to unlabeled
samples.

In reinforcement learning (Mandel et al., 2017), users can give feedback to a
system on the quality of its performance. In (Christiano et al., 2017), an
agent’s goals were derived from the preferences of non-expert humans on
trajectories. Cooperative inverse reinforcement learning (CIRL) (Hadfield-
Menell et al., 2016) is a related approach where a robot and a human user
collaborate in a partial-information game to maximize the human’s reward
function.

An expert system is an artificial intelligence system that emulates the
decision-making process of an expert (Russell and Norvig, 2009). The decision-
making is expressed as procedural code or simple decision rules (logical
predicates). Building of the necessary knowledge base for an expert system is
called knowledge engineering (Russell and Norvig, 2009). Knowledge acquisition
is one of the significant and critical tasks in developing an expert system
(Muhammad et al., 2018). Our work could help to construct the databases, but
has not been designed to solve the critical problem of expert systems, that
the rules may be inconsistent.

A recent line of works, complementary to ours, has done interactive knowledge
elicitation for statistical prediction tasks. In (Daee et al., 2017), the
authors proposed a method of knowledge elicitation for high-dimensional
datasets, where an expert knows about the relevance of the covariates or
values of the regression coefficients. A notable example of the practical
knowledge elicitation applications for genomics prediction was proposed in
(Sundin et al., 2018).

We elicit simple heuristics from the human experts, and the rules must be
natural and easy for the experts to express. The research line on fast and
frugal trees gives insights to this (Goldstein and Gigerenzer, 2002).

##  3\. The proposed method

###  3.1. Problem definition

We consider a prediction problem where an output $y^{i}_{train}\in Y$ needs to
be predicted based on an input $X^{i}_{train}\in\mathcal{X}$. The prediction
model $\mathcal{M}:\mathcal{X}\rightarrow Y$ is trained using a historical
dataset $(X_{train},y_{train})$. The testing data comes as a sequence of sets
$X^{t}_{test},\forall t\in[1,T]$; the data can be out-of-distribution or from
another domain. We consider the setting where the model $M$ is trained once
and should serve for a long time, improving the results ”on the fly.” This
paradigm is often called lifelong machine learning (Chen and Liu, 2018). The
user $U$ continuously interacts with the model in the following way, while the
system is in operation:

  * •

test data $X_{test}^{t}$ arrive at time $t$, and the model produces a
prediction for each item, $\hat{y}^{t}_{test}=\mathcal{M}(X^{t}_{test})$,

  * •

$U$ evaluates the predictions for a subset of $X^{t}_{test}$ chosen by the
user of the model, and called here the _observable dataset_. U finds the
mistakes made by the model $\mathcal{M}$, and provides feedback $f$ on them.
We will not consider further in this paper how the observable data set is
chosen; a natural choice would be based on the upper confidence bound, for
instance,

  * •

$\mathcal{M}$ uses the feedback $f$ for continuous learning and self-
improvement.

This process is described in more detail with Pseudocode 1 in Appendix A . In
the following sections, we will consider only one testing round, but the
method naturally generalizes to multiple testing rounds.

One of the key observations in the psychological literature is that the
heuristics that experts would use to describe their decision-making heuristics
can be described as fast and frugal trees and consequently by a logical
predicate (Martignon et al., 2003). In the following sections, we show how to
model this type of feedback and how it can be applied to natural language
processing.

###  3.2. User-aware prediction algorithm

We consider each of the decision rules, extracted from the users’ feedback, as
a weak learner (Schapire, 1990). The combination of the learners often
performs better than each weak learner; this is the main reason for the
popularity of the algorithms such as gradient boosting and random forests. We
combine the $f_{i}$ to

$C_{feedback}(x)=\sigma(\sum_{i=1}^{F}f_{i}(x)sim(X_{test}^{i},x)\theta_{i})$

where $f_{i}$ the decision rule extracted from the $i$th feedback, $F$ is the
total number of the decision rules, $sim$ is a measure of similarity between
test example (where the feedback is given) and $x$, $\theta_{i}$ is the weight
of the $i$th classifier learned from the data, $\sigma$ is an activation
function, $\mathcal{C}_{feedback}$ and the $\mathcal{C}_{hist}$ (a classifier
that is trained on $(X_{train},y_{train})$) are parameterized by $\theta_{f}$
and $\theta_{hist}$.

We combine the human feedback-derived and data-derived classification
algorithms with a weighted combination:

$\mathcal{C}(x)=\alpha\mathcal{C}_{hist}(x,\theta_{hist})+(1-\alpha)\mathcal{C}_{feedback}(x,\theta_{f})$

Here $\alpha$ is a weight that is used for making the algorithm more or less
sensitive to the human feedback. Alternatively, it could be learned in the
same manner as the parameters $\theta_{i}$ in the following subsection.

This algorithm could be extended to

$\mathcal{C}(x)=\alpha(x)*\mathcal{C}_{hist}(x,\theta_{hist})+(1-\alpha(x))*\mathcal{C}_{feedback}(x,\theta_{f})$

where $\alpha$ is variable across different data samples. For simplicity, we
will not study selection of $\alpha$ in this work, and will consider $\alpha$
as a hyperparameter of the algorithm and constant for all the samples.

####  3.2.1. Training the algorithm

Having the expressions for the gradients of the loss, one can apply one of the
standard optimization methods to estimate the parameters $\theta$, e.g.,
stochastic gradient descent (SGD) (Kiefer et al., 1952). We derive the
gradients for binary classification problem with binary cross-entropy loss
function in Appendix A.1 .

We can consider two cases: where the initial model can be changed and where it
should remain. In the first case, while algorithm training, the parameters
$\theta_{hist}$ and $\theta_{f}$ will be updated via an optimization
algorithm. And, in the second case, an optimization algorithm will update only
the parameters $\theta_{f}$.

###  3.3. Modeling the experts for the experiments

In this section, we propose a method for human modeling that can be used for
studies when experimenting with real domain experts is too difficult for
various reasons (cost, time, etc.). The modeled humans have several properties
to reflect the reality adequately. The depth of the human is the tendency of
human to construct complex rules. The second parameter is experience and it
can be defined in two following ways:

  1. (1)

fraction of the observed data (from the mixture of all distributions),

  2. (2)

if we consider the data as a mixture of a number of distributions
$p_{1},...,p_{n}$ and the human has faced the data from the distributions
$p_{i_{1}},...,p_{i_{k}}$, then we will call value $\frac{k}{n}$ as human
experience.

Thus, human feedback decision rules can be modeled as a set of decision trees
(Breiman et al., 1984) that trained on the historical data (observed from all
or a part of the distributions). The decision trees fitted to the data using
CART algorithm (Breiman et al., 1984). Parameter depth shows the complexity of
the rules; our experiments show that there is no need for too complex rules.
Experience refers to the variability of the samples seen by the expert.

##  4\. Experiments

In this section, we analyze the experimental performance of the proposed
methods. We first demonstrate the method with simulated humans, modelled to
produce decision trees (section 4.1), and then carry out several user studies
(Sections 4.2.1 and 4.2.2).

###  4.1. Switching distribution and user modelling

In this experiment, we consider the dataset
$X_{train},y_{train},X_{test},y_{test}$ presented in Figure 2. The total size
$N=400$, and each cluster contains 100 points. Details are in Appendix B.1 .

We simulate 10 human experts as follows. Human depth $d\sim U([1,2,3,4])$,
human experience $e\sim N(0.3,0.05)$ indicating the proportion of the data
seen by the human. We train the decision rule for each human as the decision
trees of depth $d$ on $e$ part of the data generated from the mixture of train
and test distributions. Thus, we model the experts as experienced across all
the distributions, however, having simple heuristic rules. The decision trees
were fitted to the data using CART algorithm (Breiman et al., 1984).

We collected feedback decision rules from 40 modeled experts. Then, we
compared the data-driven model, the model with decision rule feedback, and the
model with new labeled samples as feedback.

Table 1. Experimental evaluation on synthetic dataset with user modeling (Accuracy) feedback | Train distr. | Test distr. | Train + test distr.
---|---|---|---
Decision rule feedback | 1.0 | 0.88 | 0.94
Labels feedback 40 experts | 0.0 | 1.0 | 0.5
No feedback | 0.995 | 0.005 | 0.5

We used similarity function $sim\equiv constant=1$ and sigmoid activation
function $\sigma(x)=\frac{1}{1+e^{-x}}$.

What is striking in this table, is the high accuracy for the method with
decision rule feedback for train distribution and test distribution. That
confirms the domain adaptation properties of the proposed method for modeled
decision rules.

Figure 2. Switching distribution

###  4.2. User studies

####  4.2.1. Switching distribution

We conducted a user study on a dataset similar to the one studied in Section
4.1 using the same data generation process. We followed the proposed algorithm
of collecting the users’ feedback responses. We asked 10 people to formulate
the decision rules on how to distinguish the two classes. After this step, we
ran the logistic regression model on the dataset and evaluated it on the small
subsets of the test data. Misclassified data points were propagated to the
users, who could both use the previously formulated rule to provide the
feedback, or if the rule did not classify a new point correctly, they were
able to modify the rule.

We fix $\alpha(x)=0.5$ and found $\theta$ using SGD as described in Section
3.2.1.

The decision rule feedback model with the rules from all 10 participants
improved the test data results compared to data-driven logistic regression
from 0% to 99.8%, without significant performance decrease on training
distribution. The majority of the rules had depth 2. Experts with low
experience tended to create overcomplicated rules and often changed their
rules while acquiring new data points; at the same time, experts with high
experience created simple and precise rules.

####  4.2.2. Sentiment analysis

In this user study, we evaluated domain adaptation capability of the proposed
framework on a sentiment analysis task. Essentially, it is a binary text
classification task with two classes: positive and negative. The goal is to
understand the polarity of the given text. We trained a logistic regression
model on the movie review dataset (Maas et al., 2011). We evaluated the model
on topics from a new domain, different from movies. For this purpose, we used
multiple domain sentiment analysis dataset (Blitzer et al., 2007). The topics
in the second dataset are much broader than in the movie review dataset,
including music, video, electronics, grocery, software. The test dataset
contained 25 topics, and 10 people participated in the experiment.

We tested the proposed framework with the following sequence of actions. Each
participant of the user study received the reviews one by one. For each
review, the right class is known, and the predicted class is also known. The
participants needed to formulate a rule that helps to predict the correct
class of the review. The participants often used simple predicates such as the
presence of a particular phrase in the text, but sometimes also more
sophisticated rules such as regular expressions. In total, the participants
generated 139 rules for the positive class and 142 for the negative.

(a)  (b)

Figure 3. Model with decision rule feedback performs better than label
feedback (topics: ”jewelry and watches” and ”electronics”). _LogReg(IMDB)_ is
logistic regression trained on IMDB; _LogReg domain_ is logistic regression
trained on the considered domain, _(LogReg(IMDB) + labels)_ is logistic
regression trained on IMDB with feedback as labels, _(LogReg(IMDB) + decision
rules)_ is logistic regression with decision rule feedback (our proposed
method).

Experimental evaluation showed that the accuracy of the model with decision
rule feedback was better for most domains than the accuracy of the model
without feedback or with labels as feedback. Two selected topics are presented
in Figure 3. We can observe that our method outperforms the data-driven model
and the model with labels as feedback for $\alpha\approx 0.85$. We also can
see that for the topic ”jewelry_&_watches” the proposed approach performs even
better than a model specifically trained on this domain. The complete set of
the results for this experiment, as well as the experimental setting, are
presented in Appendix B.4 .

##  5\. Conclusion and discussion

In this work, we proposed a method for eliciting decision rules from experts,
and for using them effectively for machine learning. The proposed method was
demonstrated by simulations and user experiments to be useful for domain
adaptation. It is also less laborious than the standard knowledge elicitation
process. An additional advantage of the method is that it is model-agnostic
and can be used for lifelong learning. The experiments also showed that the
method helps an algorithm to generalize better to a new distribution, in a
setting with a dramatic change in the distributions. In a sentiment analysis
experiment, we showed the proposed method’s applicability in a real-life
problem, and demonstrated its domain generalization capability across
different topics.

An important restriction of this work is that the method is applicable only
when experts are able to elicit heuristic decision rules. However, we believe
that decision rule elicitation is possible for the majority of the modern ML
problems.

Decision rule elicitation gives a second wind to the expert systems by
resolving a challenging knowledge acquisition problem; it may lead to more
frequent usage of human-crafted decision rules in practice. This required a
statistical treatment of the rules, acknowledging that they are imperfect. The
proposed method is also an essential step in human-in-the-loop methods; we
show that humans can be more effectively included in the loop.

We believe that the proposed method is an essential step towards more
efficient interaction between experts and a model. As a generalization of our
idea, one can consider providing the feedback to the model in natural
language, where instead of using the decision rule predicates, an expert
provides an explanation of their decision in raw text. This idea needs more
careful investigation, and our method is a good indication that it is possible
in principle.

###### Acknowledgements.

This work was supported by the Academy of Finland (Flagship program: Finnish
Center for Artificial Intelligence FCAI) grants 319264 and 292334. We
acknowledge the computational resources provided by the Aalto Science-IT
Project.

## References

  * (1)
  * Afrabandpey et al. (2017) Homayun Afrabandpey, Tomi Peltola, and Samuel Kaski. 2017\.  Interactive prior elicitation of feature similarities for small sample size prediction. In _Proceedings of the 25th Conference on User Modeling, Adaptation and Personalization_. ACM, Bratislava, Slovakia, 265–269.
  * Amershi et al. (2014) Saleema Amershi, M. Cakmak, W. B. Knox, and T. Kulesza. 2014\.  Power to the people: The role of humans in interactive machine learning.  _AI Mag._ 35 (2014), 105–120.
  * Blitzer et al. (2007) John Blitzer, Mark Dredze, and Fernando Pereira. 2007\.  Biographies, Bollywood, boom-boxes and blenders: domain adaptation for sentiment classification. In _Proceedings of the 45th Annual Meeting of the Association of Computational Linguistics_. Association for Computational Linguistics, Prague, Czech Republic, 440–447.
  * Breiman et al. (1984) Leo Breiman, Jerome Friedman, Charles J Stone, and Richard A Olshen. 1984.  _Classification and Regression Trees_.  CRC Press, Monterey, CA.
  * Chen and Liu (2018) Zhiyuan Chen and Bing Liu. 2018.  Lifelong machine learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ 12, 3 (2018), 1–207.
  * Christiano et al. (2017) Paul F Christiano, Jan Leike, Tom Brown, Miljan Martic, Shane Legg, and Dario Amodei. 2017\.  Deep reinforcement learning from human preferences. In _Advances in Neural Information Processing Systems_ , Vol. 30. Curran Associates, Inc., 4299–4307.
  * Daee et al. (2017) Pedram Daee, Tomi Peltola, Marta Soare, and Samuel Kaski. 2017.  Knowledge elicitation via sequential probabilistic inference for high-dimensional prediction.  _Machine Learning_ 106, 9-10 (2017), 1599–1620.
  * Garthwaite et al. (2013) Paul H Garthwaite, Shafeeqah A Al-Awadhi, Fadlalla G Elfadaly, and David J Jenkinson. 2013\.  Prior distribution elicitation for generalized linear and piecewise-linear models.  _Journal of Applied Statistics_ 40, 1 (2013), 59–75.
  * Gigerenzer and Todd (1999) Gerd Gigerenzer and Peter M Todd. 1999.  _Simple Heuristics That Make Us Smart_.  Oxford University Press, USA.
  * Goldstein and Gigerenzer (2002) Daniel G Goldstein and Gerd Gigerenzer. 2002.  Models of ecological rationality: the recognition heuristic.  _Psychological review_ 109, 1 (2002), 75.
  * Hadfield-Menell et al. (2016) Dylan Hadfield-Menell, Stuart J Russell, Pieter Abbeel, and Anca Dragan. 2016.  Cooperative Inverse Reinforcement Learning. In _Advances in Neural Information Processing Systems_ , Vol. 29. Curran Associates, Inc., Red Hook, NY, USA, 3909–3917.
  * Hart (1985) Anna Hart. 1985\.  Knowledge elicitation: issues and methods.  _Computer-Aided Design_ 17, 9 (1985), 455–462.
  * Kadane et al. (1980) Joseph B Kadane, James M Dickey, Robert L Winkler, Wayne S Smith, and Stephen C Peters. 1980.  Interactive elicitation of opinion for a normal linear model.  _J. Amer. Statist. Assoc._ 75, 372 (1980), 845–854.
  * Kiefer et al. (1952) Jack Kiefer, Jacob Wolfowitz, et al. 1952\.  Stochastic estimation of the maximum of a regression function.  _The Annals of Mathematical Statistics_ 23, 3 (1952), 462–466.
  * Lewis and Gale (1994) David D. Lewis and William A. Gale. 1994.  A sequential algorithm for training text classifiers. In _SIGIR ’94_ , Bruce W. Croft and C. J. van Rijsbergen (Eds.). Springer London, London, 3–12.
  * Maas et al. (2011) Andrew L. Maas, Raymond E. Daly, Peter T. Pham, Dan Huang, Andrew Y. Ng, and Christopher Potts. 2011\.  Learning word vectors for sentiment analysis. In _Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies_. Association for Computational Linguistics, Portland, Oregon, USA, 142–150.
  * Mandel et al. (2017) Travis Mandel, Yun-En Liu, Emma Brunskill, and Zoran Popovic. 2017.  Where to add actions in human-in-the-Loop reinforcement learning. In _Proceedings of the Thirty-First AAAI Conference on Artificial Intelligence, February 4-9, 2017_. AAAI Press, San Francisco, California, USA, 2322–2328.
  * Martignon et al. (2003) Laura Martignon, Oliver Vitouch, Masanori Takezawa, and Malcolm Forster. 2003.  _Naive and Yet Enlightened: From Natural Frequencies to Fast and Frugal Decision Trees_.  Wiley, 189–211.
  * Muhammad et al. (2018) LJ Muhammad, EJ Garba, ND Oye, and GM Wajiga. 2018\.  On the problems of knowledge acquisition and representation of expert system for diagnosis of coronary artery disease (CAD).  _International Journal of u-and e-Service, Science and Technology_ 11, 30 (2018), 49–58.
  * Russell and Norvig (2009) Stuart Russell and Peter Norvig. 2009.  _Artificial Intelligence: A Modern Approach_ (3rd ed.).  Prentice Hall Press, USA.
  * Schapire (1990) Robert E Schapire. 1990\.  The strength of weak learnability.  _Machine Learning_ 5, 2 (1990), 197–227.
  * Sundin et al. (2018) Iiris Sundin, Tomi Peltola, Luana Micallef, Homayun Afrabandpey, Marta Soare, Muntasir Mamun Majumder, Pedram Daee, Chen He, Baris Serim, Aki Havulinna, Caroline Heckman, Giulio Jacucci, Pekka Marttinen, and Samuel Kaski. 2018\.  Improving genomics-based predictions for precision medicine through active elicitation of expert knowledge.  _Bioinformatics_ 34, 13 (1 July 2018), 395–403.

##  Appendix A Training the algorithm

In the listing 1, we present a pseudocode describing the training loop in the
setup we used.

1 M = train_ml_model(historical_data);

2 while  _The system is working_ do

3 test_data = gather_latest_test_data();

4 predictions = M.predict(test_data);

5 for  _user in all_users_ do

6 feedback_rules = user.use_predictions(predictions);

7 M.self_improve(feedback_rules);

8

9 end for

10

11 end while

Algorithm 1 Lifelong machine learning problem with the experts’ feedback

###  A.1. Binary classification

Let’s consider a binary classification task with cross-entropy as a loss
function:

$\mathcal{L}=-y_{i}log(C(x_{i}))-(1-y_{i})log(1-\mathcal{C}(x_{i}))$

The gradients for the parameters $\theta_{hist}$ and $\theta_{f}$ could be
written in the following form:

$\frac{\partial L}{\partial\theta_{hist}}=\alpha\frac{\partial
C_{h}}{\partial\theta_{h}}(\frac{1-y_{i}}{1-C(x_{i})}-\frac{y_{i}}{C(x)})$
$\frac{\partial L}{\partial\theta_{f}}=(1-\alpha)\frac{\partial
C_{f}}{\partial\theta_{f}}(\frac{1-y_{i}}{1-C(x_{i})}-\frac{y_{i}}{C(x)})$

###  A.2. Estimation of the mixture coefficient $\alpha$

####  A.2.1. Mixture coefficient between the model and the feedback

An essential practical aspect of the algorithm is the right choice of the
averaging coefficient between the machine learning model and the model based
on users’ decision rules. We propose various strategies for choosing $\alpha$:

  1. (1)

setting $\alpha$ as a hyperparameter of the algorithm,

  2. (2)

choosing larger coefficient for human-based decision rules in the areas of
$\mathcal{X}$ of the higher uncertainty,

  3. (3)

non-constant $\alpha$ dependent on probability density, can be estimated using
kernel density estimation (KDE),

  4. (4)

compare training and testing distribution with two-sample testing.

Experimentally we will focus only on setting $\alpha$ as a hyperparameter. We
leave hyperparameter choosing for future research.

##  Appendix B Experiments

###  B.1. Switching distribution

Here we provide extensive details on data generation process for the
experiments described in Sections 4.1 and 4.2.1.

The training dataset is a set of points described by two features of total
size $N=200$, with $\frac{N}{2}$ points of class $1$ ($y_{i}=0$) and
$\frac{N}{2}$ points of class $0$ ($y_{i}=0$) by the following rules

$\left\\{\begin{array}[]{ll}x^{train}_{i}\sim N(\mu_{1},\Sigma_{1})&\mbox{if
$y_{i}=1$},\\\ x^{train}_{i}\sim N(\mu_{2},\Sigma_{2})&\mbox{if $y_{i}=0$}.\\\
\end{array}\right.$

The testing dataset $X_{test},y_{test}$ is given from other distribution in
order to emulate how the human decision rules feedback help to better
generalize model to out-of-distribution samples. $X_{test},y_{test}$ of size
$N=200$, with $\frac{N}{2}$ points of class $1$ ($y_{i}=0$) and $\frac{N}{2}$
points of class $0$ ($y_{i}=0$) by the following rules

$\left\\{\begin{array}[]{ll}x^{test}_{i}\sim
N(\mu^{\prime}_{1},\Sigma^{\prime}_{1})&\mbox{if $y_{i}=1$},\\\
x^{test}_{i}\sim N(\mu^{\prime}_{2},\Sigma^{\prime}_{2})&\mbox{if
$y_{i}=0$}.\\\ \end{array}\right.$

For the experiments we took $\mu_{1}=\begin{pmatrix}0&0\end{pmatrix}$,
$\mu_{2}=\begin{pmatrix}6&0\end{pmatrix}$,
$\mu_{1}^{\prime}=\begin{pmatrix}6&6\end{pmatrix}$,
$\mu_{2}^{\prime}=\begin{pmatrix}0&6\end{pmatrix}$,
$\Sigma_{1}=\Sigma_{2}=\Sigma_{1}^{\prime}=\Sigma_{2}^{\prime}=\begin{pmatrix}1&0\\\
0&1\end{pmatrix}$.

###  B.2. Synthetic dataset and user modeling

In this section, we present full results for the experiments with switching
dataset and modeled experts. We generated humans as described in the Section
3.3. We used logistic regression as a base model, found misclassified samples,
and provided feedback decision rules from all experts. The number of generated
human experts is provided in the column n_humans. Each modeled expert can
produce the feedback in two following ways: (1) if its decision rule can
classify a particular sample, then it returns it’s decision rule, (2) if this
sample cannot be classified by its decision rule, it adds new sample to its
experience, train the underlying decision tree again, and returns it as a
feedback decision rule.

Table 2. User modeling results on synthetic dataset n_humans | n_feedback | LogReg + decision rule feedback | LogReg + label feedback
---|---|---|---
|  | Train distr | Test distr | Train + test distr | Train distr | Test distr | Train + test distr
1 | 8 | 0.705 | 0.5 | 0.603 | 0.965 | 0.495 | 0.73
5 | 33 | 0.96 | 0.47 | 0.715 | 0.975 | 0.495 | 0.735
10 | 67 | 0.99 | 0.65 | 0.82 | 0.28 | 0.5 | 0.593
20 | 133 | 1.0 | 0.45 | 0.725 | 0.015 | 0.78 | 0.398
30 | 241 | 0.995 | 0.565 | 0.78 | 0.0 | 1.0 | 0.5
40 | 288 | 1.0 | 0.88 | 0.94 | 0.0 | 1.0 | 0.5
50 | 385 | 1.0 | 0.81 | 0.905 | 0.0 | 1.0 | 0.5

###  B.3. Synthetic dataset and user studies

We describe the profiles of the experts in Table 3.

Table 3. The profiles of the experts participating in the user study with synthetic dataset User | Experience | n_feedback
---|---|---
0 | 0.1 | 10
1 | 0.1 | 10
2 | 0.1 | 9
3 | 0.03 | 8
4 | 0.01 | 9
5 | 0.01 | 9
6 | 0.03 | 9
7 | 0.03 | 9
8 | 0.01 | 10
8 | 0.03 | 10

We also provide the user studies results for all the experts and evaluate our
method with feedback decision rules elicited from each expert. Full results of
the user study are presented in Table 2.

Table 4. Full results of the user study on the synthetic data Model | User | $\alpha$ | Train distr. accuracy | Test distr. accuracy | Train + Test distr. accuracy
---|---|---|---|---|---
LogReg | No | - | 1.0 | 0.0 | 0.5
LogReg + decision rule feedback | 0 | 0.3 | 0.968 | 0.99 | 0.98
LogReg + decision rule feedback | 1 | 0.3 | 0.995 | 1.0 | 0.998
LogReg + decision rule feedback | 2 | 0.3 | 0.980 | 1.0 | 0.988
LogReg + decision rule feedback | 3 | 0.3 | 0.996 | 0.995 | 0.995
LogReg + decision rule feedback | 4 | 0.3 | 0.995 | 0.015 | 0.505
LogReg + decision rule feedback | 5 | 0.3 | 1.0 | 0.47 | 0.735
LogReg + decision rule feedback | 6 | 0.3 | 0.99 | 0.985 | 0.988
LogReg + decision rule feedback | 7 | 0.3 | 0.985 | 1.0 | 0.993
LogReg + decision rule feedback | 8 | 0.3 | 0.995 | 0.995 | 0.995
LogReg + decision rule feedback | 9 | 0.3 | 0.98 | 0.5 | 0.743
LogReg + decision rule feedback | All | 0.3 | 0.995 | 0.998 | 0.743
LogReg + label feedback | All | - | 0.005 | 0.995 | 0.5025

###  B.4. Sentiment analysis and user studies

We conducted a user study with 10 human experts on the sentiment analysis
problem. The algorithm was trained on IMDB dataset, and then evaluated on the
different topics.

In Figures 4, 5, 6, and 7 we compare accuracy (fraction of correctly
classified samples among all samples) for 4 different methods:

  1. (1)

Logistic regression trained on IMDB (LogReg (IMDB)),

  2. (2)

Logistic regression train on a given domain (LogReg domain),

  3. (3)

Logistic regression with feedback as labels (LogReg(IMDB) + labels),

  4. (4)

The proposed method: (LogReg (IMDB) + decision rules).

In Figures 4, 5, 6, and 7 we provide the results of the study for 25 different
topics. The filled area is the standard error, and we estimated it by 40
bootstrap iterations. We can see that in 4 cases, our method outperforms all
the other approaches for a certain value of $\alpha$. It also performs not
worse than feedback as labels in the majority of the cases.

The generated rules vary from the simplest checks that a particular pattern occurs in the sentence (e.g., a predicate "funny" in text) to quite sophisticated rules involving regular expressions (e.g., a regular expression * it(’s | is ) the best .*).

From this experiment, we also see that the correct choice of a hyperparameter
$\alpha$ is vital for the empirical performance of the algorithm. We also can
see that optimal values of $\alpha$ are close across the domains, which
simplifies the usage of the algorithm.

(a)  (b)

(c)  (d)  (e)  (f)

Figure 4. The experimental results for the topics 1-6 (standard error is
reported)

(a)  (b)  (c)  (d)

(e)  (f)  (g)  (h)

s

Figure 5. The experimental results for the topics 12-22 (standard error is
reported)

(a)  (b)  (c)  (d)

(e)  (f)  (g)  (h)

Figure 6. The experimental results for the topics 22-25 (standard error is
reported)

(a)

(b)

(c)

Figure 7. The experimental results for the topics 22-25 (standard error is
reported)


Figure 73: GMP5226, see Fig. 14 for details.


11institutetext: Department of Computer Science, City University of Hong Kong,
Kowloon, Hong Kong SAR, China
11email<EMAIL_ADDRESS><EMAIL_ADDRESS>22institutetext: Engineering Systems and Design Pillar, Singapore University
of Technology and Design, Singapore
22email<EMAIL_ADDRESS>33institutetext: Department of Electrical
and Electronic Engineering, The University of Hong Kong, Hong Kong SAR, China
33email<EMAIL_ADDRESS>
# Online Ride-Hitching in UAV Travelling††thanks: A preliminary version of
this paper is to appear in COCOON 2021.

Songhua Li (✉) 11 Minming Li 11 Lingjie Duan 22 Victor C.S. Lee 33

###### Abstract

The unmanned aerial vehicle (UAV) has emerged as a promising solution to
provide delivery and other mobile services to customers rapidly, yet it drains
its stored energy quickly when travelling on the way and (even if solar-
powered) it takes time for charging power on the way before reaching the
destination. To address this issue, existing works focus more on UAV’s path
planning with designated system vehicles providing charging service. However,
in some emergency cases and rural areas where system vehicles are not
available, public trucks can provide more feasible and cost-saving services
and hence a silver lining. In this paper, we explore how a single UAV can save
flying distance by exploiting public trucks, to minimize the travel time of
the UAV. We give the first theoretical work studying online algorithms for the
problem, which guarantees a worst-case performance. We first consider the
offline problem knowing future truck trip information far ahead of time. By
delicately transforming the problem into a graph satisfying both time and
power constraints, we present a shortest-path algorithm that outputs the
optimal solution of the problem. Then, we proceed to the online setting where
trucks appear in real-time and only inform the UAV of their trip information
some certain time $\Delta t$ beforehand. As a benchmark, we propose a well-
constructed lower bound that an online algorithm could achieve. We propose an
online algorithm MyopicHitching that greedily takes truck trips and an
improved algorithm Adaptive that further tolerates a waiting time in taking a
ride. Our theoretical analysis shows that Adaptive is asymptotically optimal
in the sense that its ratio approaches the proposed lower bounds as $\Delta t$
increases.

###### Keywords:

Ride-hitching Energy efficiency Online algorithm.

##  1 Introduction

As technologies in navigation and control progress, the application of
unmanned aerial vehicle (UAV) in package delivery is proved to be a promising
approach. For example, the e-commerce giant Amazon has been pushing to deliver
packages to its millions of customers by drones. DHL applies drones to provide
fully autonomous loading and offloading in the last-mile delivery [3], which
provides a silver lining in special situations (e.g., the COVID-19 pandemic)
with social-distancing. However, due to the nature of the UAV/drone in both
the low energy storage and high-rate flying consumption, it quickly drains its
stored energy, which limits the delivery range and affects the service
effectiveness remarkably. Although the UAV can be solar-powered by utilizing
solar radiation as energy [2], this is not sufficient since the charging-rate
is not high enough. Fortunately, the UAV is able to dock with road vehicles
automatically [17], which makes it possible for UAV to team up with trucks
spontaneously and instantaneously for reducing the transportation cost. This
is inspired by ride-sharing platforms, for example, GrabHitch allows
passengers to hitch ride on the way. However, it is still not clear what
ramifications of online ride-hitching are on UAV’s energy saving. This paper
aims to provide theoretical foundations for online ride hitching in UAV
travelling. We note that the UAV may not catch a truck which is far away from
its current location (spatial issue), nor wait for a truck for too long
(temporal issue) as time efficiency is critical in UAV’s delivery service.

Related works. We survey relevant researches along two threads. The first
thread studies UAV’s energy-efficiency problem with either routing or speed
scheduling optimization. For example, [6] proposed the looking before crossing
algorithm, which is proved to be optimal for the offline speed scheduling
problem under a practical flight energy model. [7] considers an energy-aware
path planning algorithm that minimizes energy consumption while satisfying
coverage and resolution constraints. Please refer to [4] for a survey work. In
contrast, we focus on theoretical issues of the problem especially when truck
trips are released in an online fashion. We aim to unveil the adaptability of
the ”ride-sharing” in UAV travelling in the worst-case scenario, which is
usually measured by online algorithms and competitive ratio [9]. The second
thread focuses on classical combinatorial optimization problems. The
$k$-server problem aims to efficiently move $k$ servers to serve a batch of
online requests of the metric space [12] such that the total moving distance
of all servers is minimized. The famous work function algorithm achieves a
competitive ratio of $2k-1$ on general metrics and hence is optimal for
$1$-server problem on the line [13]. When the server moves in constant
velocity, the work function algorithm is optimal in achieving minimum
completion time of serving all the online requests. A variant of the 1-server
problem is the online repairman problem [11] which asks for a tour that visits
a set of online cities in the metric space such that the weighted sum of
completion times of the cities is minimized. [11] proposes a
$(1+\sqrt{2})^{2}$-competitive deterministic online algorithm for the general
metric spaces and [14] gave an improved 5.429-competitive algorithm for line
metrics. A generalized version of the $k$-server problem is the $k$-taxi
problem in which each request is represented by a pair $(s,t)$ of two points
(including the start point $s$ and end point $t$) instead [15]. In the gas
station problem [5], a vehicle with a given tank capacity $U$ and an initial
amount $\mu_{s}$ of gas, can purchase gas at each vertex of a complete graph
at a certain price. And the objective of [5] is to find the cheapest way from
a given start node $s$ to a given target node $t$ of the graph. Note that the
gas station problem involves neither the time constraint on vertices nor
restrictions in the set of visited vertices. Another related problem is the
online maximum $k$-interval coverage problem which aims to select $k$ online
sub-intervals (i.e., truck trips) such that the total covered length of a
target interval (i.e., the UAV’s path) is maximized [16]. In contrast, the
problem studied in this paper is more complicated since one has to face both
the spatial and the temporal issues simultaneously and the power constraint of
UAV travelling is further involved.

Main contributions of this paper are summarized below. Due to space
constraints, some results and proofs are deferred to the Appendix.

  * •

We are the first to study UAV’s traveling problem by hitching on truck rides
in an online setting, for the purpose of minimizing the UAV’s travel time.
Comprehensively, we investigate different cases according to how early (i.e.,
$\Delta t$) a truck should inform the UAV of its trip before the departure.

  * •

For the offline version of the problem, we give a graph-based optimal
solution. Since it is intricate to capture both power and time constraints in
mapping truck trips to nodes of a graph, we delicately construct the graph by
screening unnecessary trucks iteratively, which is on top of some
characteristics of the problem. Based on this, we find an optimal solution in
$O(n^{2})$ time.

  * •

As a benchmark, we construct lower bounds on the competitive ratio for any
online algorithms, by considering different time gap $\Delta t$ between the
start time and release time.

  * •

We show that a simple myopic algorithm (where the UAV flies forward constantly
by default until using up its stored energy, and myopically accepts as many
rides as possible halfway) has a defect, which can be easily exploited by the
adversary, leading to negligible energy saved from taking rides. To fix this
defect, we propose a $\Delta t$-Adaptive algorithm by tolerating a waiting
time at most $\frac{\Delta t}{2}$ in taking each ride, which achieves a
provable competitive ratio very close to the lower bound.

##  2 Problem Formulation

We consider the following problem: the UAV, which is at its origin $O$, is
supposed to move to its destination $A$ as early as possible, in which the
path length $|OA|=a$. The UAV has a low charging rate $\alpha$ per unit time
and a high power-consuming rate $\beta$ ($>\alpha$) per unit time. Initially
at time $0$, the UAV stores an amount $P_{0}$ of energy (which is small and
could be zero) and it flies at its maximum velocity 111In practice, the UAV
can convert its speed between 0 and its maximum speed in few seconds [7].
Considering the dominant travel time, we assume the flying velocity as a
constant as in [8, 7]. $v_{0}$. To avoid the trivial case that the UAV
directly flies to the destination by charging on the way, we assume the UAV
has insufficient energy $P_{0}$ ($<\frac{(\beta-\alpha)a}{v_{0}}$). That is,
the UAV needs to hitch truck rides to save flying distance or charge for
sufficiently large amount of time to fly to the destination. Along the path
$OA$ of the UAV, a sequence $\mathbb{V}=\\{V_{1},V_{2},...,V_{n}\\}$ of
$n\in\mathbb{N}^{+}$ trucks will be released one by one to potentially offer
rides to the UAV. Each truck
$V_{i}=(r_{i},t_{i},o_{i},d_{i},v_{i})\in\mathbb{V}$ releases its trip
information to the UAV at time $r_{i}$ and departs from its origin $o_{i}$ at
time $t_{i}$ ($\geq r_{i}$) with a constant velocity $v_{i}$ to its
destination $d_{i}$. Further, we denote $\Delta t_{i}=t_{i}-r_{i}$ as the time
gap between the start time $t_{i}$ and the release time $r_{i}$ of a truck
ride $V_{i}$. The UAV is not informed of each ride $V_{i}\in\mathbb{V}$ until
its release time $r_{i}$ (when the truck’s schedule is determined) and needs
to determine whether to accept/catch or reject $V_{i}$ irrevocably at $r_{i}$.
The objective is to minimize the UAV’s travel time to the destination $A$ (or
equivalent, the arrival time at $A$) by using online truck rides to save
energy halfway. Key notations of this paper are given below in Table 1.

Table 1: Notations in this paper. Notations |  Physical meanings
---|---
$[0,a]$ |  The line segment representing the UAV’s route.
$\mathbb{V}_{i}=\\{V_{1},V_{2},...,V_{i}\\}$ |  The sequence of the first $i$ rides released, particularly, $\mathbb{V}_{n}=\mathbb{V}$.
$V_{i}=(r_{i},t_{i},o_{i},d_{i},v_{i})$ |  The $i$th released ride, with its release time $r_{i}$, departure time $t_{i}$, start location $o_{i}$, end location $d_{i}$ and flying velocity $v_{i}$.
$\Delta t_{i}=t_{i}-r_{i}$ |  the time gap between the start time $t_{i}$ and the release time $r_{i}$ of a ride $V_{i}$.
$v=\min\limits_{V_{i}\in\mathbb{V}}v_{i}$ |  the smallest possible velocity of a truck/ride.
$P_{0}$ |  The initial power that the UAV contains at time $t_{0}=0$.
$P_{i}$ |  The power that the UAV contains at the start time of the $i$th ride taken by the UAV.
$\beta$ |  The UAV’s power-consumption-rate for flying.
$\alpha$ |  The UAV’s recharging-rate, which satisfies $\alpha<\beta$;
$\xi(U)$ and $\xi(V_{|U|})$ |  The arrival time (or the overall travel time) of the UAV to the target $A$, given the set $U$ of rides and the last ride $V_{|U|}$ taken by the UAV, respectively, as formally defined later in (9) and (10).

Suppose that $U=(V_{1},\cdots,V_{|U|})$ is the sequence of rides to be taken
by the UAV. Denote $P_{i}$ as the power that the UAV contains at the start
time $t_{i}$ of the $i$th taken ride $V_{i}$. Now, we formally formulate our
model as the following mathematical problem (2)-(8). where the objective (2)
is to minimize the UAV’s travel time from $O$ to $A$, which is according to
the following Proposition 1 where we discuss the physical meaning of the two
terms of (2) and why we take the maximizing operation between the two.
Constraints (3)-(4) indicate the power $P_{i+1}$ that the UAV contains at the
start time $t_{i+1}$ of $V_{i+1}$ by transferring from $V_{i}$, which can be
calculated by the following power transfer function in (1).

$\textsc{PTF}(P_{i},V_{i},V_{i+1})=P_{i}+(t_{i+1}-t_{i})\cdot\alpha-\frac{|o_{i+1}-d_{i}|\beta}{v_{0}}$
(1)

After leaving each truck $V_{i}$, for $i\in\\{1,\cdots,|U|-1\\}$, note that
the UAV needs to have enough energy to fly to the following truck $V_{i+1}$’s
start location, which leads to the power compatibility constraint (5) as
$\textsc{PTF}(P_{i},V_{i},V_{i+1})\geq 0$; and it also needs to catch
$V_{i+1}$’s start time, which is reflected by the time compatibility
constraints (6)-(7). When the inequality in constraint (7) holds strictly, the
UAV needs to stop at the roadside to wait for $V_{i+1}$’s departure 222We use
stop-and-recharge time and waiting time interchangeably in this paper, to
refer to the time that the UAV stops at roadside. after leaving $V_{i}$.
Constraint (8) indicates the total flying distance of the UAV.

$\displaystyle\min\limits_{U\subseteq\mathbb{V}}\max\\{$
$\displaystyle\lambda\frac{\beta}{\alpha
v_{0}}-\frac{P_{0}}{\alpha},t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}+\frac{a-d_{|U|}}{v_{0}}\\}$
(2) s.t. $\displaystyle P_{1}=P_{0}+t_{1}\cdot\alpha-\frac{o_{1}}{v_{0}}\beta$
(3) $\displaystyle P_{i+1}=\textsc{PTF}(P_{i},V_{i},V_{i+1})$ (4)
$\displaystyle\textsc{PTF}(P_{i},V_{i},V_{i+1})\geq 0$ (5) $\displaystyle
t_{1}\geq\frac{o_{1}}{v_{0}}$ (6) $\displaystyle t_{i+1}\geq
t_{i}+\frac{d_{i}-o_{i}}{v_{i}}+\frac{|o_{i+1}-d_{i}|}{v_{0}}$ (7)
$\displaystyle\lambda=(o_{1}+\sum_{i=1}^{|U|-1}|o_{i+1}-d_{i}|+a-d_{|U|})$ (8)

For analytical tractability, the overall travel time of the UAV in objective
(2) is converted to (9) in the following Proposition 1. Intuitively, when the
UAV contains enough power to fly constantly to $A$ after completing the last-
taken ride $V_{|U|}$, UAV’s arrival time only corresponds to $V_{|U|}$;
otherwise, UAV’s arrival time to $A$ only corresponds to the UAV’s overall
flying distance. Thus, we have

###### Proposition 1

Given the sequence $U=(V_{1},\cdots,V_{|U|})$ of rides taken by the UAV, the
UAV’s arrival time $\xi(U)$ at the target $A$ is given by

$\xi(U)=\max\\{\underbrace{(o_{1}+\sum_{i=1}^{|U|-1}|o_{i+1}-d_{i}|+a-d_{|U|})}_{\rm
i.e.,\;UAV^{\prime}s\;overall\;flying\;distance}\frac{\beta}{\alpha
v_{0}}-\frac{P_{0}}{\alpha},t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}+\frac{a-d_{|U|}}{v_{0}}\\}$
(9)

Competitive Ratio. Online algorithms are typically measured by the competitive
ratio [9]. Given a sequence $\mathbb{V}$ of online trucks that can offer rides
to the UAV, denote by $\xi_{\rm ALG}(\mathbb{V})$ and $\xi_{\rm
OPT}(\mathbb{V})$ the UAV’s arrival time to the destination by an online
algorithm (ALG) and the optimal offline solution (OPT) where complete
information of $\mathbb{V}$ is given beforehand, respectively. Then, the
competitive ratio $\rho$ of the problem is defined as
$\rho=\max\limits_{\mathbb{V}}\frac{\xi_{\rm ALG}(\mathbb{V})}{\xi_{\rm
OPT}(\mathbb{V})}$. When a number $\theta\geq 1$ satisfies $\theta\leq\rho$
for all deterministic online algorithms, we say $\theta$ is a lower bound on
the competitive ratio of the problem.

##  3 Offline Problem And Algorithm Design

We present an optimal solution, named OptimalHitching, for the offline problem
in this section, in which the idea behind is to map the offline rides to nodes
in a graph, and further the taking sequence in achieving the earliest arrival
time is converted to a minimum-weight path in the constructed graph. In a
graph-based solution, we find it is difficult to map the UAV’s arrival time to
edge weight in the graph directly by using $\xi(U)$. This is because the
arrival time $\xi(U)$ corresponds to multi nodes/rides in the set $U$. Hence,
we transform the objective (9) to the following (10), which only corresponds
to the last ride $V_{|U|}$ taken by the UAV and the power $P_{|U|}$ that the
UAV contains at the start time $t_{|U|}$ of $V_{|U|}$.

$\xi(V_{|U|})=t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}+\frac{a-d_{|U|}}{v_{0}}+\underbrace{\frac{\max\\{\frac{a-d_{|U|}}{v_{0}}(\beta-\alpha)-(P_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}),0\\}}{\alpha}}_{\rm
the\;possible\;stop-and-recharge\;time\;of\;the\;UAV}$ (10)

Before going into the details of our offline algorithm, we first give the
following definitions together with some preliminary results.

######  Definition 1 (Adjacent)

Given the set $U\subset\mathbb{V}$ of rides accepted by the UAV, two trips
$V_{i}$ and $V_{j}$ in $U$ are called adjacent rides if and only if
$V_{j}\in\\{\arg\min\limits_{\mathclap{V_{x}\in
U,o_{x}>o_{i}}}\\{o_{x}-o_{i}\\},\;\arg\max\limits_{\mathclap{V_{x}\in
U,o_{x}<o_{i}}}\\{o_{x}-o_{i}\\}\\}$. Specifically, $V_{j}$ is regarded as the
prior one (resp. the following one) of the two if $o_{j}<o_{i}$ (resp.
$o_{j}>o_{i}$).

######  Definition 2 (Sequentially-taken)

Given the set $U\subset\mathbb{V}$ of rides taken by the UAV, we say $V_{i}$
and $V_{j}$ in $U$ are sequentially-taken if they are neighbors in the taking
sequence $U$ of rides. For example, when the UAV transfers from $V_{i}$ to
$V_{j}$ in the sequence, we call $V_{i}$ and $V_{j}$ the prior and the
following ride of the two sequentially-taken rides respectively.

To verify whether two rides can be taken together by the UAV or not, we have
Proposition 2, which is summarized from (2)-(8) and helps to determine whether
two nodes/rides should be connected/compatible in the constructed graph.

######  Proposition 2 (Compatible condition)

Given two rides $V_{j}$ and $V_{i}$ with $o_{j}<o_{i}$ and the power $P_{j}$
of the UAV at time $t_{j}$, we say they are compatible only when the UAV is
able to take both rides by transferring from $V_{j}$ to $V_{i}$. Specifically,
they satisfy the following compatible condition (11).

$\begin{split}&a)\;[{\rm time\;compatibility}]\;t_{i}\geq
t_{j}+\frac{d_{j}-o_{j}}{v_{j}}+\frac{|o_{i}-d_{j}|}{v_{0}}\\\ &b)\;[{\rm
power\;compatibility}]\;\textsc{PTF}(P_{j},V_{j},V_{i})\geq 0\end{split}$ (11)

The moment while the UAV is either landing-on or flying-off a truck, note that
the time and space dimensions keep in consistency between the UAV and the
truck. Given two sequentially-taken rides $V_{i}$ (the prior one) and $V_{j}$,
the UAV is supposed to land on $V_{j}$ right at time $t_{j}$ to catch the
start of $V_{j}$ without reducing its remaining power at time $t_{j}$. This is
because the power transfer function in (1) is independent from when the UAV
departs in transferring between $V_{i}$ and $V_{j}$. Or, the UAV can stop-and-
recharge at the end location $d_{i}$ of $V_{i}$ until it can fly constantly to
the start $o_{j}$ of $V_{j}$ (right at $t_{j}$). This helps us to better
understand the location of the UAV while transferring between two rides.
Theorem 3.1 shows the taking sequence of the UAV in a given set of accepted
rides.

###### Theorem 3.1

Given the set $U=\\{V_{1},\cdots,V_{|U|}\\}$ of rides that are accepted by the
optimal solution (OPT), OPT takes all rides in $U$ following the increasing
order of the rides’ start locations, i.e. the smaller $o_{i}$ is, the earlier
$V_{i}\in U$ is taken.

Offline Algorithm. At the high level, OptimalHitching first constructs a graph
by screening unnecessary truck rides iteratively, which is on top of some
characteristics of the problem. Afterwards, the optimal solution of the
offline problem in this paper is converted to a minimum-weight shortest path
of the graph. In the constructed graph, two virtual nodes $V_{0}$ and
$V_{n+1}$ are introduced to represent the origin $O$ and the destination $A$
respectively, while the other nodes in $\\{V_{1},\cdots,V_{n}\\}$ are
constructed to represent the taking sequence of rides in $\mathbb{V}$
respectively due to Theorem 3.1. Each node of $\\{V_{1},\cdots,V_{n}\\}$
maintains a weight of the maximum power that the UAV could remain at the
moment transferring to this node/ride, and connects to the previously
constructed node from which the UAV transfers to the new node and remains that
maximum power. In other words, node weights in the graph are only used for
checking the power compatibility of rides taken by the UAV. Due to (10), all
edges of the graph are set as zero weight except for those connecting to
$V_{n+1}$. In this way, the weight of a path connecting $V_{0}$/$O$ and
$V_{n+1}$/$A$ indicates the arrival time of the UAV at $A$ taking those rides
on the path. Below gives details of OptimalHitching.

  1. 1.

First, sort offline rides in $\mathbb{V}_{n}$, by increasing order of their
start locations as $(V_{1},V_{2},\cdots,V_{n})$; create virtual nodes
$V_{0}=(0,0,0,0,0)$ and $V_{n+1}$ representing the origin $O$ and the
destination $A$ respectively.

  2. 2.

Then, construct a graph $G=(N,E,w)$ with the weight function $w$ applying to
both nodes in $N$ and edges in $E$, in an iterative way:

    1. (a)

Include $V_{0}$ in $N$. Check in sequence $(V_{1},V_{2},\cdots,V_{n})$ the
rides one by one. When $V_{i}\in(V_{1},V_{2},\cdots,V_{n})$ is compatible with
at least one ride in $N$ by (11), denote $\Phi(V_{i})$ as the set of rides in
$N$ that are compatible with $V_{i}$:

      1. i.

find in $\Phi(V_{i})$ the node/ride, denoted by $V_{*}(i)$, to which the most
power remains to the UAV on arrival at the start of $V_{i}$ by transferring
from a ride in $\Phi(V_{i})$;

      2. ii.

include $V_{i}$ in $N$ and set weight
$w(V_{i})=\textsc{PTF}(w(V_{*}(i)),V_{*}(i),V_{i})$; include
($V_{*}(i)$,$V_{i}$) in $E$ and set edge weight $w(V_{*}(i),V_{i})=0$;

    2. (b)

Include $V_{n+1}$ in $N$. For each $V_{j}\in N$, add ($V_{j},V_{n+1}$) to $E$
with weight $w(V_{j},V_{n+1})=\xi(V_{j})$ that representing the UAV’s arrival
time to $A$ with taking $V_{j}$ as the last ride.

  3. 3.

Finally, find in $N$ the node $\overline{V}=\arg\min\limits_{V\in
N-\\{V_{n+1}\\}}w(V,V_{n+1})$ that has the minimum-weight edge connecting with
$V_{n+1}$, and further find backwards (from those nodes joining in $N$ earlier
than $\overline{V}$) the node that connects with $\overline{V}$.333Step 2.b.i
ensures only one node joining in $N$ earlier than $\overline{V}$ that connects
with $\overline{V}$.  Repeat this step backwards until node $V_{0}$ is
reached. Output the found nodes in the sequence of their joining time in $N$.

Note that the running time of OptimalHitching is dominated by graph
construction steps, which is in $O(n^{2})$. We have the following Theorem 3.2.

###### Theorem 3.2

OptimalHitching runs in $O(n^{2})$-time and outputs the sequence of rides that
are taken by an optimal offline solution.

##  4 Lower Bounds on Competitive Ratios

Table 2: Derived notations for bound analysis Derived notations |  Physical meanings
---|---
$T_{ru}:=\frac{\beta-\alpha}{\alpha\cdot v_{0}}$ |  the time duration for recharging the amount of power to fly a unit distance constantly.
$T_{mu}:=\frac{\beta}{\alpha\cdot v_{0}}$ |  the time duration for moving a unit distance in the case that the UAV contains no power at the beginning.
$T_{f0}:=\frac{P_{0}}{\beta-\alpha}$ |  the time duration that the UAV flies constantly from time $t_{0}$ on.
$l_{f}:=\frac{P_{0}v_{0}}{\beta-\alpha}$ |  the furthest location to which the UAV can reach by flying constantly from time $t_{0}$ on, note that $l_{f}=T_{f0}\cdot v_{0}$.
$\xi(\varnothing):=\frac{\beta}{\alpha}\frac{a}{v_{0}}-\frac{P_{0}}{\alpha}$ |  the earliest arrival time of the UAV to $A$ when no ride is taken, by (10) with $V_{|U|}=(0,0,0,0,v)$ and $P_{|U|}=P_{0}$.
$T_{ra}:=\frac{\beta-\alpha}{\alpha}\frac{a}{v_{0}}-\frac{P_{0}}{\alpha}$ |  the least time duration of the UAV to stop-and-recharge, to reach the target $A$ without taking rides, $T_{ra}=\xi(\varnothing)-\frac{a}{v_{0}}$.
$L_{\rm min}:=\frac{(a\beta-a\alpha-P_{0}v_{0})v}{v_{0}\alpha-v\alpha+v\beta}$ |  the minimum length to be saved by rides (with velocity $v$) to reach the target $A$ without stop-and-recharge, by Lemma 1.
$Len(T):=\max\\{\frac{(a\beta-a\alpha-P_{0}v_{0}-v_{0}T\alpha)v}{v_{0}\alpha-v\alpha+v\beta},0\\}$ |  the least amount of length that the UAV needs to save for avoiding more time in stop-and-recharge afterwards, given that the UAV already stop-and-recharges for a total amount $T$ of time.

We present the lower bounds of the UAV’s travel time by first releasing a hook
ride, and then releasing rides that are not compatible to ALG by power and
time constraint if ALG rejects/accepts the hook ride, since taking a ride
helps to save more energy in an early stage but moves more slowly. For bound
analysis, we further derive some notations as summarized in Table 2.

Notice that the UAV does not need a ride $V_{i}$ with $\Delta t_{i}\geq
T_{ra}+T_{f0}$. This is because the moment when $V_{i}$ starts, the UAV
already contains at least $(\Delta t_{i}-T_{f0})\alpha$ of power by stop-and-
recharging, which enables the UAV to fly constantly to $A$. Thus, we have the
following proposition 3. Then, Lemma 1 is given to better figure out the
minimum travel time that an OPT could achieve, based on which a lower bound is
presented in Theorem 4.1 as a benchmark for further online algorithm design.

###### Proposition 3

$\Delta t_{i}=t_{i}-r_{i}$ of each ride $V_{i}\in\mathbb{V}$ ranges in
$[0,T_{ra}+T_{f0}]$.

###### Lemma 1

The UAV needs to save an overall distance of at least $L_{\rm
min}=\frac{(a\beta-a\alpha-P_{0}v_{0})v}{v_{0}\alpha-v\alpha+v\beta}$ by
taking rides, in order to avoid stop-and-recharge halfway.

###### Theorem 4.1

For the problem with flexible $\Delta t_{i}\in[0,T_{ra}+T_{f0}]$, no online
deterministic algorithm can achieve a competitive ratio better than

$\frac{\xi(\varnothing)-T_{mu}}{\frac{\left\lceil L_{\rm
min}\right\rceil}{v}+\frac{a+1-\left\lceil L_{\rm min}\right\rceil}{v_{0}}}$
(12)

##  5 Online Algorithms with Competitive Analysis

We propose a myopic algorithm MyopicHitching and a near-optimal algorithm
$\Delta t$-Adaptive respectively, both of which inherit notations from Table
2.

###  5.1 MyopicHitching Algorithm

We first present the MyopicHitching algorithm under fixed $\Delta t$. By some
small changes in the following accepting conditions (i-ii), one can easily
extend it to the flexible $\Delta t$. MyopicHitching follows the route by
default to fly forward constantly until the first time it runs out of power.
Afterwards, the UAV stops-and-recharge until containing enough power to fly
constantly to the target $A$. The by-default action possibly changes only when
a ride is accepted. Denote $P(V)$ as the power that the UAV remains at the
start time of an accepted ride $V$ in the current solution, and $U$ as the set
of rides accepted by MyopicHitching. A new ride $V_{i}\in\mathbb{V}$ is
accepted only when $V_{i}$ meets the following two conditions together, i.e.,
$l_{\rm rc}\cdot l_{\rm aa}=1$. Accordingly, update both $P(V_{i})$ and power
attributes of those rides in $U$ that depart after $V_{i}$ by the power-
transfer-function in (1):

i) ride-compatible444Under fixed $\Delta t$, online algorithm must accept ride
that depart after previously accepted rides due to Observation 1. But this is
not the case under flexible $\Delta t$, a newly accepted ride can depart
between two rides in $U$, and the potential $V_{\rm
right}=\arg\min\limits_{\mathclap{\\{V_{j}\in U|o_{j}>o_{i}\\}}}o_{j}-o_{i}$
should also be compatible with $V_{i}$.: the new ride should meet (11) with
$V_{\rm left}=\arg\min\limits_{\mathclap{\\{V_{j}\in
U|o_{j}<o_{i}\\}}}\\{o_{i}-o_{j}\\}$ which is the only ride in $U$ that is
sequentially-taken with $V_{i}$, i.e., the following indicator should be equal
to 1.

$\mathbf{\textup{1}}_{\rm rc}=\left\\{\begin{matrix}1,&\begin{matrix}t_{i}\geq
t_{\rm left}+\frac{d_{\rm left}-o_{\rm left}}{v_{\rm
left}}+\frac{|o_{i}-d_{\rm left}|}{v_{0}}\\\
{\rm\;\textbf{and}\;}\textsc{PTF}(P_{\rm left},V_{\rm left},V_{i})\geq 0\\\
\end{matrix}\\\ 0,&{\rm otherwise}\end{matrix}\right.$

ii) arrival-ahead: the UAV will reduce its overall travel time when taking the
new ride, i.e., the following indicator which is due to (9) should be equal to
1.

$\mathbf{\textup{1}}_{\rm
aa}=\left\\{\begin{matrix}1,&\xi(U\cup\\{V_{i}\\})\leq\xi(U)\\\ 0,&{\rm
otherwise}\end{matrix}\right.$

To take each accepted ride in $U$, MyopicHitching guides the UAV to reach the
origin of the ride right at its start time. Whenever the UAV contains enough
power to fly constantly towards the target $A$, i.e., (13) is satisfied, it
stops accepting new ride and flies directly to $A$ after taking the last-
accepted ride.

$\left\\{\begin{matrix}u_{\textup{time}}\geq\max\\{(\frac{\beta}{\alpha}-1)\frac{a-d_{|U|}}{v_{0}}-\frac{\widetilde{P}(V_{|U|})}{\alpha},t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}\\}{\rm\;or}\\\
\widetilde{P}(V_{|U|})\geq\frac{a-d_{|U|}}{v_{0}}(\beta-\alpha){\rm\;\&\;}u_{\textup{time}}<t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}{\rm\;or}\\\
U=\varnothing{\rm\;\&\;}u_{\textup{time}}=T_{ra}\end{matrix}\right.$ (13)

in which
$\widetilde{P}(V_{|U|})=P(V_{|U|})+\frac{\alpha(d_{|U|}-o_{|U|})}{v_{|U|}}$
indicates the power remaining to the UAV on completing $V_{|U|}$, while
$u_{\rm time}$ indicates the real time in the execution.

###### Observation 1

For the problem with fixed $\Delta t$, the earlier a ride is released, the
earlier the ride departs.

###### Lemma 2

For the problem with fixed $\Delta t$, MyopicHitching always takes rides in
increasing order of their start locations.

Notice in the following example that MyopicHitching has a defect which can be
exploited by an adversary leading to a very bad competitive ratio: suppose
$V_{1}=(\frac{1}{2v_{0}},\frac{1}{2v_{0}}+\Delta
t,\varepsilon,1+\varepsilon,v)$ is the first released ride with a small
$\Delta t$. At the release time $\frac{1}{2v_{0}}$ of $V_{1}$, the UAV is at
location $\frac{1}{2}$ and contains power
$\overline{P}=P_{0}+(\alpha-\beta)\frac{1}{2v_{0}}$. We note that the arrival-
ahead condition (ii) implies a ride released at an early stage could be
accepted when the ride could help the UAV to save more energy. Since the UAV
can save a small amount $\frac{2\varepsilon}{v_{0}}\beta$ of power by taking
$V_{1}$, $V_{1}$ is accepted by accepting conditions (i)-(ii). Notice that
MyopicHitching actually costs $t_{\rm wait}=\Delta
t+\frac{1}{v_{1}}+\frac{\frac{1}{v_{0}}-1-2\varepsilon}{v_{0}}$ of waiting
time. The defect appears when $\Delta t<t_{\rm wait}$ since the adversary
could further releases rides making MyopicHitching violate constraints in
(11). When $\varepsilon\rightarrow 0$, we get the following Theorem 5.1.

###### Theorem 5.1

For the problem with fixed $\Delta t$, MyopicHitching achieves a competitive
ratio no worse than

$\frac{\xi(\varnothing)}{(a-\left\lceil{\rm L}_{\rm
min}\right\rceil)T_{mu}-\frac{P_{0}}{\alpha}}$ (14)

Particularly, in the scenario where the UAV already exhausts its power (i.e.,
$P_{0}=0$) at the very beginning, MyopicHitching achieves a competitive ratio
no worse than $\frac{a}{a-\left\lceil{\rm L}_{\rm min}\right\rceil}$.

###  5.2 $\Delta t$-Adaptive Algorithm

We fix the defect of MyopicHitching by leveraging adaptability of $\Delta t$
in MyopicHitching and present $\Delta t$-Adaptive algorithm by including the
following conditional-start condition (i.e., $\textup{1}_{\rm cs}=1$) in the
ride-accepting conditions. Specifically, $\Delta t$-Adaptive keeps the Input,
Lines 1-4, 6-15 of the pseudocode in Appendix 0.H of MyopicHitching the same,
but replaces the if condition $\textup{1}_{\rm rc}\cdot\textup{1}_{\rm aa}$==1
in Line 5 by $\textup{1}_{\rm rc}\cdot\textup{1}_{\rm aa}\cdot\textup{1}_{\rm
cs}$==1.

iii): conditional-start condition: the following indicator $l_{\rm cs}=1$.

$\textup{1}_{\rm
cs}=\left\\{\begin{matrix}1,&\begin{matrix}o_{i}\geq\frac{\Delta
tv_{0}}{2}+l(u_{\rm time}){\rm\;for\;}u_{\rm
time}\in[0,\frac{l_{f}}{v_{0}}],\\\ {\rm or,\;}o_{i}\geq l_{f}+\frac{\Delta
tv_{0}}{2}{\rm\;for\;}u_{\rm
time}\in(\frac{l_{f}}{v_{0}},\xi(\varnothing)]\end{matrix}\\\
0,&\textup{otherwise}\end{matrix}\right.$

###### Theorem 5.2

For the problem with fixed $\Delta t$, $\Delta t$-Adaptive algorithm achieves
a competitive ratio no worse than

$\frac{\xi(\varnothing)}{\frac{\Delta t}{2}+\frac{a-Len(\frac{\Delta
t}{2})}{v_{0}}+\frac{Len(\frac{\Delta t}{2})}{v}}$ (15)

Recall that rides with $\Delta t\geq T_{ra}+T_{f0}$ are not worth taking (see
Lemma 3). By Theorem 5.2, we know $\Delta t$-Adaptive prefers larger $\Delta
t$ since its competitive ratio decreases as $\Delta_{t}$ increases. Comparing
(15) and (14), we find that $\Delta t$-Adaptive algorithm outperforms
MyopicHitching especially when $\Delta t$ is large, this is because $\Delta
t$-Adaptive guarantees that OPT has to cost some waiting time of at least
$\frac{\Delta t}{2}$ in the case when all released truck rides are not
compatible to $\Delta t$-Adaptive. What’s more, $\Delta t$-Adaptive algorithm
actually achieves near-optimal performance compared to the best possible
online algorithm since the latter can save at most one ride while the OPT has
to pay a waiting time of $\Delta t$. Please refer to the figure in the
appendix 0.G for some comparison between MyopicHitching and $\Delta
t$-Adaptive.

##  6 Concluding Remarks

In this paper, we give the first theoretical work on the problem of online
ride-hitching in UAV travelling. By mapping truck trips to nodes in a graph in
an iterative way, we give a shortest-path-like solution for the offline
version of this problem where truck trips are all known in advance. As a
benchmark, we present lower bounds on the competitive ratio of the problem,
respectively, for different settings. Then, we show that a greedy algorithm
which accepts as many rides as possible has a defect. To fix the defect, we
propose the $\Delta t$-Adaptive algorithm, achieving near-optimal performance
in terms of the competitive ratio.

Acknowledgement. We thank the anonymous referees for their helpful feedback.
Part of this work was done while Songhua LI was visiting the Singapore
University of Technology and Design. Minming Li is also from City University
of Hong Kong Shenzhen Research Institute, Shenzhen, P.R. China. The work
described in this paper was sponsored by Project 11771365 supported by NSFC.

## References

  * [1] Bokeno, E. T., Bort, T. M., Burns, S. S., Rucidlo, M., Wei, W.and Wires, D. L.: Package delivery by means of an automated multi-copter UAS/UAV dispatched from a conventional delivery vehicle. U.S. Patent No. 9,915,956 (2018)
  * [2] Wu, J., Wang, H., Li, N., Yao, P., Huang, Y. and Yang, H.: Path planning for solar-powered UAV in urban environment. Neurocomputing, 275, 2055-2065 (2018)
  * [3] DHL Express. https://www.dhl.com/tw-en/home/press/press-archive/2019/dhl-express-launches-its-first-regular-fully-automated-and-intelligent-urban-drone-delivery-service. Accessed August 2021.
  * [4] Chung, S. H., Sah, B. and Lee, J.: Optimization for drone and drone-truck combined operations: A review of the state of the art and future directions. Computers & Operations Research, 123, 105004 (2020)
  * [5] Khuller, S., Malekian, A. and Mestre, J. To fill or not to fill: The gas station problem. ACM Transactions on Algorithms, 7(3), 1-16 (2011)
  * [6] Shan, F., Luo, J., Xiong, R., Wu, W. and Li, J.: Looking before crossing: An optimal algorithm to minimize UAV energy by speed scheduling with a practical flight energy model. In IEEE INFOCOM 2020-IEEE Conference on Computer Communications, pp. 1758-1767. IEEE. (2020)
  * [7] Di Franco, C. and Buttazzo, G. (2015, April).: Energy-aware coverage path planning of UAVs. In 2015 IEEE international conference on autonomous robot systems and competitions, pp. 111-117 (2015)
  * [8] Henchey, M. J., Batta, R., Karwan, M. and Crassidis, A.: A Flight Time Approximation Model for Unmanned Aerial Vehicles: Estimating the Effects of Path Variations and Wind. Operations Research for Unmanned Systems, pp. 95-117 (2016)
  * [9] Borodin, A. and El-Yaniv, R.: Online computation and competitive analysis. cambridge university press (2005)
  * [10] Wang, Z., Duan, L. and Zhang, R.: Adaptive deployment for UAV-aided communication networks. IEEE transactions on wireless communications, 18(9), 4531-4543 (2019)
  * [11] Krumke, S. O., De Paepe, W. E., Poensgen, D. and Stougie, L.: News from the online traveling repairman. Theoretical Computer Science, 295(1-3), 279-294 (2003)
  * [12] Koutsoupias, E.: The k-server problem. Computer Science Review, 3(2), 105-118 (2009)
  * [13] Koutsoupias, E. and Papadimitriou, C. H.: On the k-server conjecture. Journal of the ACM (JACM), 42(5), 971-983 (1995)
  * [14] Bienkowski, M. and Liu, H. H.: An Improved Online Algorithm for the Traveling Repairperson Problem on a Line. In 44th International Symposium on Mathematical Foundations of Computer Science. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik (2019)
  * [15] Coester, C. and Koutsoupias, E.: The online $k$-taxi problem. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1136-1147 (2019)
  * [16] Li, S., Li, M., Duan, L. and Lee, V. C.: Online Maximum k-Interval Coverage Problem. In International Conference on Combinatorial Optimization and Applications (pp. 455-470). Springer, Cham (2020)
  * [17] Bokeno, E. T., Bort, T. M., Burns, S. S., Rucidlo, M., Wei, W. and Wires, D. L. U.S. Patent No. 9,915,956. Washington, DC: U.S. Patent and Trademark Office (2018)
  * [18] Han, C. K. and Cheng, S. F. An exact single-agent task selection algorithm for the crowdsourced logistics. in IJCAI (2020)

##  Appendix 0.A Proof of Proposition 1

###### Proof

Given the ride $V_{|U|}=(r_{|U|},t_{|U|},o_{|U|},d_{|U|})$ that is finally
taken by the UAV among those taken rides in $U$, the overall flying distance
of the UAV, denoted by $dist_{f}$, is

$dist_{f}=o_{1}+\sum_{i=1}^{|U|-1}|o_{i+1}-d_{i}|+a-d_{|U|}$ (16)

We also note that the UAV flies off $V_{|U|}$ at time
$t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}$. Denote $P_{\rm r}$ as the power
remains to the UAV at time $t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}$, we
discuss two cases.
Case 1. $P_{\rm r}\geq\frac{a-d_{|U|}}{v_{0}}(\beta-\alpha)$. The UAV contains
enough power to fly constantly from $d_{|U|}$ (the fly-off point of $V_{|U|}$)
to the target $A$. Then, the arrival time $\xi(U)$ to $A$, which corresponds
to $V_{|U|}$ only, is
$t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}+\frac{a-d_{|U|}}{v_{0}}$. Meanwhile,
we have
$\xi(U)\geq\frac{dist_{f}}{v_{0}}\frac{\beta}{\alpha}-\frac{P_{0}}{\alpha}$ in
this case, since the UAV still contains non-negative power on arrival at $A$
at time $\xi(U)$, i.e., $P_{0}+\xi(U)\alpha-\frac{dist_{f}}{v_{0}}\beta\geq
0$.
Case 2. $P_{\rm r}<\frac{a-d_{|U|}}{v_{0}}(\beta-\alpha)$. The UAV does not
have enough power to fly constantly from $d_{|U|}$ to the target $A$. To
achieve the earliest possible arrival time to $A$, the UAV needs to stop-and-
recharge for an amount of power at least
$\frac{a-d_{|U|}}{v_{0}}(\beta-\alpha)-P_{\rm r}$ (and runs out of its power
on arrival at $A$). This implies
$\xi(U)=\frac{dist_{f}}{v_{0}}\frac{\beta}{\alpha}-\frac{P_{0}}{\alpha}$ in
this case. Clearly,
$\xi(U)>t_{|U|}+\frac{d_{|U|}-o_{|U|}}{v_{|U|}}+\frac{a-d_{|U|}}{v_{0}}$ as
otherwise it contradicts with the base of this case.

##  Appendix 0.B Proof of Theorem 3.1

###### Proof

Clearly, all rides accepted by OPT are finally taken. We just need to show
that any two adjacent rides in $U$ are actually sequentially-taken with the
same order by OPT. For the sake of contradiction, suppose there are two
adjacent rides $V_{i}$ (the prior one) and $V_{j}$ that are not sequentially-
taken, i.e., the UAV takes $V_{j}$ (with landing-on location $o_{j}$) prior to
$V_{i}$ (with the landing-on location $o_{i}$). Notice that, the UAV can save
$(\beta-\alpha)\frac{d_{j}-o_{i}}{v_{0}}$ more amount of energy by taking
$V_{i}$ first since $o_{i}<o_{j}$, which either contradicts with OPT (in the
case that the saved amount of energy leads to earlier arrival time to $A$) or
generates another optimal solution (in the case that this saved amount of
energy does not induce earlier arrival time to $A$), which is because the
land-on point (which is the start location of the ride) of each taken ride is
unique. Therefore, any two adjacent rides in OPT is sequentially-taken.

##  Appendix 0.C Proof of Lemma 1

###### Proof

Suppose, w.l.o.g., that the UAV takes rides in $\\{V_{1},\cdots,V_{m}\\}$ to
assist itself to reach the target $A$ without stopping halfway. Denote $L$ as
the overall length that the UAV saves by taking rides. As the UAV does not
stop halfway, the final arrival time of the UAV at the destination $A$,
denoted by $\textup{t}_{\rm final}$, consists of two parts, the time spent on
rides (denoted by $\textup{t}_{\rm r}$) and the flying time
$\frac{a-\textup{L}}{v_{0}}$. Denote $\textup{L}_{1},\cdots,\textup{L}_{m}$ as
the accumulative length in $L$ by rides $V_{1},\cdots,V_{m}$, respectively.
Then, $L=\sum_{i=1}^{i=m}\textup{L}_{i}$ and $\textup{t}_{\rm
r}=\frac{\textup{L}_{1}}{v_{1}}+\cdots+\frac{\textup{L}_{m}}{v_{m}}$. Further,

$\textup{t}_{\rm
final}=\frac{\textup{L}_{1}}{v_{1}}+\cdots+\frac{\textup{L}_{m}}{v_{m}}+\frac{a-L}{v_{0}}\leq\frac{L}{v}+\frac{a-L}{v_{0}}$
(17)

in which the inequality holds by
$v=\min\limits_{\mathclap{i\in\\{1,2,\cdots,m\\}}}v_{i}$. The moment when UAV
just reaches the target $A$, note that the power of the UAV remains non-
negative. Hence,

$P_{0}+\alpha\textup{t}_{\rm final}-\beta(\frac{a-L}{v_{0}})\geq 0$ (18)

Substituting (17) in (18), we have

$L\geq\frac{a(\beta-\alpha)-P_{0}v_{0}}{v_{0}}\cdot\frac{vv_{0}}{v_{0}\alpha+(\beta-\alpha)v}=\frac{(a\beta-a\alpha-
P_{0}v_{0})v}{v_{0}\alpha-v\alpha+v\beta}$

##  Appendix 0.D Omitted Proof of Theorem 4.1

###### Proof

Suppose all rides move with constant velocity $v$ and are of unit-length. By
the basic settings $P_{0}<(\beta-\alpha)\frac{a}{v_{0}}$ and $v_{0}>v$ of this
paper, we have $L_{\rm min}>0$ and further $\left\lceil L_{\rm
min}\right\rceil\geq 1$. Define $\tau=\left\lceil L_{\rm min}\right\rceil$ and
$\varsigma=\left\lfloor l_{f}\right\rfloor$. Suppose the length $a$ of the
trip $OA$ is larger than $l_{f}+\tau$. Now, we consider the first released
ride $V_{1}=(0,T_{f0},l_{f},l_{f}+1,v)$ which can only be taken when the UAV
departs from $t_{0}$ and consumes its entire power on arrival at the start
location $l_{f}$, i.e., the orange rectangle/ride in Fig. 1.
Case 1. ALG accepts $V_{1}$. We discuss two sub-cases.
Case 1.1. $\tau\geq\varsigma+2$. After a short time duration $\varepsilon$
($\geq\frac{1}{v_{0}}$), the adversary further releases another $\varsigma$
head-to-tail rides within $[0,L_{\rm min}]$: for
$i\in\\{2,\cdots,\varsigma+1\\}$

$V_{i}=(\varepsilon+\frac{i-2}{v},\varepsilon+\frac{i-2}{v},i-2,i-1,v)$ (19)

Notice that, at time $\varepsilon$ when $V_{2}$ departs, ALG already flies
over the location $\frac{1}{v_{0}}v_{0}=1$, implying that ALG does not need to
accept $V_{2}$. In other words, ALG does not fly backward until reaching the
origin of $V_{1}$. Note that the distance between the end location $\varsigma$
of ride $V_{\varsigma+1}$ with the location $L_{\rm min}$ is smaller than 1,
which takes $T_{f0}-\frac{\varsigma}{v_{0}}$ of time for flying. Further at
time $\varepsilon+\frac{\varsigma}{v}+T_{f0}-\frac{\varsigma}{v_{0}}$ (denoted
by $\textup{t}_{1}$), when OPT just flies-off $V_{\varsigma+2}$, the adversary
releases $V_{\varsigma+2}=(\textup{t}_{1},\textup{t}_{1},l_{f},l_{f}+1,v)$.
Clearly, the above $\varsigma+1$ rides $\\{V_{2},\cdots,V_{\varsigma+2}\\}$
cannot be taken by ALG since they are not compatible with $V_{1}$. However,
OPT can successfully take all rides in $\\{V_{2},\cdots,V_{\varsigma+2}\\}$
without violating the compatible constraints in (11), see the blue
rectangles/rides in Fig. 1. At time $\textup{t}_{1}+\frac{1}{v}$, when
completing taking the rides and flying-off $V_{\varsigma+2}$, OPT is located
at ($l_{f}+1$) and contains power of

$\begin{aligned} P_{\rm
OPT}&=P_{0}+\underbrace{(\varepsilon+\frac{\varsigma+1}{v}-\frac{\varsigma}{v_{0}}+T_{f0})\alpha}_{\rm
recharging\;power}-\frac{l_{f}-\varsigma}{v_{0}}\beta\\\
&=P_{0}+(\varepsilon+\frac{\varsigma+1}{v})\alpha+(l_{f}-\frac{\varsigma}{v_{0}})(\alpha-\beta)\end{aligned}$
Meanwhile at time $\textup{t}_{1}+\frac{1}{v}$, ALG is also located at
($l_{f}+1$) but contains power of just $P_{\rm
ALG}=(\varepsilon+\frac{\varsigma+1}{v}-\frac{\varsigma}{v_{0}})\alpha$, since
ALG just runs out of its power at time $T_{0}^{f}$ on arrival at $l_{f}$.
Right at time $\textup{t}_{1}+\frac{1}{v}$, the adversary further releases
another $\tau-\varsigma-2$ head-to-tail rides, i.e.,

$V_{\varsigma+3}=(\textup{t}_{1}+\frac{1}{v},\textup{t}_{1}+\frac{1}{v}+\frac{P_{\rm
OPT}}{\beta-\alpha},l_{f}+1+\frac{P_{\rm
OPT}v_{0}}{\beta-\alpha},l_{f}+2+\frac{P_{\rm OPT}v_{0}}{\beta-\alpha},v)$

, $\cdots$,

$V_{\tau+1}=(\textup{t}_{1}+\frac{1}{v}+\frac{\tau-\varsigma-3}{v},\textup{t}_{1}+\frac{1}{v}+\frac{P_{\rm
OPT}}{\beta-\alpha}+\frac{\tau-\varsigma-3}{v},l_{f}+\tau-\varsigma-2+\frac{P_{\rm
OPT}v_{0}}{\beta-\alpha},l_{f}+\tau-\varsigma-1+\frac{P_{\rm
OPT}v_{0}}{\beta-\alpha},v)$

Note that OPT can just catch $V_{\varsigma+3}$ by flying from $l_{f}+1$ at the
time $\textup{t}_{1}+\frac{1}{v}$ when UAV just takes off from
$V_{\varsigma+2}$ with its entire power. This implies that the OPT can take
all rides in $\\{V_{\varsigma+4},\cdots,V_{\tau+1}\\}$ successively (see those
blue rectangles/rides in Fig. 1). Hence, OPT can reach the target $A$ without
stop-and-recharge halfway by riding $\\{V_{2},\cdots,V_{\tau+1}\\}$ (see Lemma
1). As OPT only needs to stop-to-recharge some time of $\varepsilon$ from the
very beginning to wait for the departure of $V_{2}$, the arrival time of OPT
to the target $A$ is $\xi_{\rm
OPT}=\varepsilon+\frac{\tau}{v}+\frac{a-\tau}{v_{0}}$, which includes the time
$\frac{\tau}{v}$ spent on rides and the time $\frac{a-\tau}{v_{0}}$ while
flying. In contrast, the ALG cannot even catch up $V_{\varsigma+3}$ as the
power constraint is violated by $P_{\rm ALG}<P_{\rm OPT}$, and further ALG
cannot take rides in $\\{V_{\varsigma+3},\cdots,V_{\tau}\\}$. In other words,
ALG can only fly by itself towards $A$ after taking $V_{1}$. Hence, the
arrival time of ALG is $\xi_{\rm ALG}\geq
T_{f0}+(a-1-l_{f})\cdot\frac{\beta}{\alpha v_{0}}$. When
$\varepsilon\rightarrow\frac{1}{v_{0}}$, we get

$\rho=\frac{\xi_{\rm ALG}}{\xi_{\rm
OPT}}\geq\frac{T_{f0}+(a-1-l_{f})\cdot\frac{\beta}{\alpha
v_{0}}}{\varepsilon+\frac{\tau}{v}+\frac{a-\tau}{v_{0}}}\rightarrow\frac{(a-1)\frac{\beta}{\alpha
v_{0}}-\frac{P_{0}}{\alpha}}{\frac{\tau}{v}+\frac{a+1-\tau}{v_{0}}}$ (20)

Case 1.2. $\tau\leq\varsigma+1$. After time $\varepsilon$, the adversary
releases $\tau$ rides sequentially, including head-to-tail rides
$V_{i}=(\varepsilon+\frac{i-2}{v},\varepsilon+\frac{i-2}{v},i-2,i-1,v)$ for
$i\in\\{2,\cdots,\tau\\}$ and
$V_{\tau+1}=(\varepsilon+\frac{\tau-1}{v},\varepsilon+\frac{\tau-1}{v},l_{f},l_{f}+1,v)$.
OPT can take rides in $\\{V_{2},\cdots,V_{\tau+1}\\}$ without violating
compatible constraint. By a similar analysis as in subcase 1.1, we have a
lower bound of this subcase as $\rho=\frac{\xi_{\rm ALG}}{\xi_{\rm
OPT}}\geq\frac{(a-1)\frac{\beta}{\alpha
v_{0}}-\frac{P_{0}}{\alpha}}{\frac{\tau}{v}+\frac{a+1-\tau}{v_{0}}}$.
Case 2. ALG rejects $V_{1}$ at $t_{0}$. Note that the earliest arrival time
(say $\textup{t}_{a}$) of ALG to $l_{f}+1$ is $T_{f0}+\frac{\beta}{\alpha
v_{0}}$, which is derived by
$P_{0}+\textup{t}_{a}\alpha-\beta(T_{f0}+\frac{1}{v_{0}})\geq 0$. This implies
ALG should contain non-negative power at $\textup{t}_{a}$. Later, the
adversary only releases rides with start locations larger than $l_{f}+1$ and
start time earlier than time $T_{f0}+\frac{\beta}{\alpha v_{0}}$, which are
compatible in OPT but not in ALG. For example, rides in Fig. 2. By a similar
idea in Case 1, one can derive a lower bound of this case as
$\rho=\frac{\xi_{\rm ALG}}{\xi_{\rm
OPT}}\geq\frac{T_{f0}+\frac{\beta}{\alpha\cdot
v_{0}}(a-l_{f})}{\frac{\tau}{v}+\frac{a-\tau}{v_{0}}}=\frac{a\frac{\beta}{\alpha
v_{0}}-\frac{P_{0}}{\alpha}}{\frac{\tau}{v}+\frac{a-\tau}{v_{0}}}$.

Therefore, the lower bound could be got as summarized in (12).

Figure 1: Illustration example, in which the left-side, right-side, bottom-
side and top-side of a rectangle represent the start location, end location,
start time, and the end time of the ride, respectively. In this case, ALG
accepts the hook ride (which is the isolated orange rectangle), then, the
adversary releases rides before the hook ride (not compatible with the hook
ride) making ALG stores less energy than OPT does after the hook ride.
Further, more rides can be released that are not compatible in ALG due to
constraint (11). Figure 2: Illustration of rides configurations in Case 2. The
ALG rejects the hook ride (the left-most one in orange of Fig. 2), then, the
adversary only releases rides after the hook ride making ALG not able to take
as violate constraint (11) in power.

##  Appendix 0.E Omitted Proof of Theorem 5

###### Proof

Our discussion centers around the ride, denoted by
$\overline{V}=(\overline{r},\overline{r}+\Delta
t,\overline{o},\overline{d},\overline{v})$, which is the first ride accepted
by either OPT or ALG but not both. By Observation 1, $\overline{V}$ is also
the ride that is firstly taken by either OPT or ALG. Denote $l(\overline{r})$
as the real-time location of ALG.
Case 1. $\frac{\Delta t}{2}>\frac{l_{f}}{v_{0}}$ and
$\overline{r}\in[0,\frac{l_{f}}{v_{0}}]$.
Case 1.1. $V$ is accepted by ALG. This implies $\xi_{\rm
ALG}<\xi(\varnothing)$ as otherwise $V$ is rejected by the arrival-ahead
condition $\textup{1}_{\rm aa}$, and $\overline{o}\geq\frac{\Delta
tv_{0}}{2}+l(\overline{r})\geq\frac{\Delta tv_{0}}{2}>l_{f}$. Hence, ALG
stops-and-recharge some time of $\Delta
t-\frac{l_{f}-l(\overline{r})}{v_{0}}-\frac{\overline{o}-l(\overline{r})}{v_{0}}=\Delta
t+\frac{2l(\overline{r})-\overline{o}-l_{f}}{v_{0}}$ (denoted by ${\rm T}_{\rm
ALG}$). Later, one has to stop-and-recharge some time more than ${\rm T}_{\rm
ALG}$ since $\overline{r}$ increases. Suppose OPT totally accepts $x$ ($\geq
2$) rides, note that OPT stops-and-recharge at least $\frac{\Delta t}{2}$ for
each ride after the first ride since $\beta\geq 2\alpha$. Hence, we get

$\displaystyle\rho$
$\displaystyle\leq\frac{\xi(\varnothing)}{\frac{(x-1)\Delta
t}{2}+\frac{a-Len(\frac{(x-1)\Delta t}{2})}{v_{0}}+\frac{Len(\frac{(x-1)\Delta
t}{2})}{\overline{v}}}$ (21)
$\displaystyle\leq\frac{\frac{\beta}{\alpha}\frac{a}{v_{0}}-\frac{P_{0}}{\alpha}}{\frac{\Delta
t}{2}+\frac{a-Len(\frac{\Delta t}{2})}{v_{0}}+\frac{Len(\frac{\Delta
t}{2})}{\overline{v}}}$ $\displaystyle\leq\frac{\xi(\varnothing)}{\frac{\Delta
t}{2}+\frac{a-Len(\frac{\Delta t}{2})}{v_{0}}+\frac{Len(\frac{\Delta
t}{2})}{v}}$

Case 1.2. $V$ is accepted by OPT. This infers that the OPT has to stop-and-
recharge for some time at least $\frac{\Delta t}{2}$, implying

$\rho=\frac{\xi_{\rm ALG}}{\xi_{\rm
OPT}}\leq\frac{\xi(\varnothing)}{\frac{\Delta t}{2}+\frac{a-Len(\frac{\Delta
t}{2})}{v_{0}}+\frac{Len(\frac{\Delta t}{2})}{v}}$

Case 2. $\frac{\Delta t}{2}>\frac{l_{f}}{v_{0}}$ and
$\overline{r}\in(\frac{l_{f}}{v_{0}},\xi(\varnothing)]$, or $\frac{\Delta
t}{2}\leq\frac{l_{f}}{v_{0}}$. By applying a similar idea as Case 1, one can
derive an upper bound of $\frac{\xi(\varnothing)}{\frac{\Delta
t}{2}+\frac{a-Len(\frac{\Delta t}{2})}{v_{0}}+\frac{Len(\frac{\Delta
t}{2})}{v}}$ as well.

##  Appendix 0.F Pseudocode of OptimalHitching Refers to Algorithm 1

Algorithm 1 OptimalHitching

Input: A set $\mathbb{V}_{n}$ of rides, $\beta$, $\alpha$, $v_{o}$, $P_{0}$,
$a$;
Output: A set $U$ of accepted rides;

1: Initialization. $V_{0}\leftarrow(0,0,0,0,0)$, $i\leftarrow 1$,
$N\leftarrow\\{V_{0}\\}$, $E\leftarrow\varnothing$, $w(V_{0})\leftarrow
P_{0}$;

2: Sort rides in $\mathbb{V}_{n}\cap\\{V_{0}\\}$ in increasing order of their
origins, as $(V_{0},V_{1},V_{2},\cdots,V_{n})$;

3: for $i\leq n$ do

4: $\Phi(i)\leftarrow\\{V_{j}\in
N|V_{j}{\rm\;and\;}V_{i}{\rm\;are\;compatible\;in\;(\ref{compatibleconditions})}\\}$;

5: if $\Phi(i)==\varnothing$ then

6: $i++$;

7: else

8:
$V_{*}(i)\leftarrow\arg\max\limits_{V_{j}\in\Phi(i)}\\{\textsc{PTF}(w(V_{j}),V_{j},V_{i})\\}$;

9: $N\leftarrow N\cup\\{V_{*}(i)\\}$, $E\leftarrow
E\cup\\{(V_{*}(i),V_{i})\\}$,
$w(V_{i})\leftarrow\textsc{PTF}(w(V_{*}(i)),V_{*}(i),V_{i})$;$w(V_{*}(i),V_{i})\leftarrow
0$, $i++$;

10: end if

11: end for

12: $N\leftarrow N\cup\\{V_{n+1}\\}$;

13: for $V_{j}\in N-\\{V_{n+1}\\}$ do

14: $E\leftarrow E\cup\\{(V_{j},V_{n+1})\\}$,
$w(V_{j},V_{n+1})\leftarrow\xi(V_{j})$ by (10);

15: end for

16: Output the nodes on the minimum-weight path connecting $V_{0}$ and
$V_{n+1}$ in $G=(N,E,w)$.

##  Appendix 0.G Comparison Figure

Figure 3: Performance comparison in algorithms with input parameters
normalized as $a$=100 (km), $V_{0}$=100 (km/h), $V=60$ (km/h),
$\frac{\beta}{\alpha}$= 6, $P_{0}$ = 20.

##  Appendix 0.H Pseudocode of MyopicHitching Refers to Algorithm 2

Algorithm 2 MyopicHitching

Input: $\mathbb{V}_{n}=\\{V_{1},\cdots,V_{n}\\}$, $\beta$, $\alpha$, $v_{o}$,
$P_{0}$, $OA=a$;
Output: $U\subseteq\mathbb{V}_{n}$;

1: Initialization. $U\leftarrow\varnothing$, $u_{\textup{time}}\leftarrow
t_{0}$; {%$u_{\textup{time}}$: real time}

2: Route by default when no ride to be taken. Before the first time using up
power, UAV flies over $u_{\textup{time}}$ with velocity $v_{0}$. Afterwards,
the UAV does not move until it contains enough power to fly constantly to the
target $A$.{% the following loop shows ride-accepting procedure}

3: while $u_{\textup{time}}==r_{i}$ do

4: $V_{\rm left}\leftarrow\arg\min\limits_{\mathclap{\\{V_{j}\in
U|o_{j}<o_{i}\\}}}\\{o_{i}-o_{j}\\}$;

5: if $\textup{1}_{\rm rc}\cdot\textup{1}_{\rm aa}==1$ then

6: $U\leftarrow U\cup\\{V_{i}\\}$ {% accept $V_{i}$}

7: $P(V_{i})=\textsc{PTF}(P_{\rm left},V_{\rm left},V_{i})$;

8: end if

9: end while{% the following loop shows the ride-taking procedure}

10: while $U\neq\varnothing$ do

11: The UAV flies to $o_{i}$ of each $V_{i}\in U$ right at time $t_{i}$;

12: end while

13: if condition (13) is satisfied then

14: Ride-accepting procedure stops, UAV flies towards $A$ directly after
taking rides in $U$.

15: end if