suppAppendix References University of Southern California, USA and
https://jaredraycoleman.comjaredcol@usc.eduhttps://orcid.org/0000-0003-1227-2962
Carleton University, Canada and
https://people.scs.carleton.ca/~kranakis/kranakis@scs.carleton.cahttps://orcid.org/0000-0002-8959-4428
Wesleyan University, USA and
<EMAIL_ADDRESS>California State
University, Long Beach, USA and https://www.csulb.edu/college-of-
engineering/dr-oscar-morales-poncehttps://www.csulb.edu/college-of-
engineering/dr-oscar-morales-poncehttps://orcid.org/0000-0002-9645-1257 Jared
Coleman and Evangelos Kranakis and Danny Krizanc and Oscar Morales-Ponce 1

# Optimal Delivery with a Faulty Drone

Jared Coleman  Evangelos Kranakis  Danny Krizanc  Oscar Morales-Ponce

###### Abstract

We introduce and study a new cooperative delivery problem inspired by drone-
assisted package delivery. We consider a scenario where a drone, en route to
deliver a package to a destination (a point on the plane), unexpectedly loses
communication with its central command station. The command station cannot
know whether the drone’s system has wholly malfunctioned or merely experienced
a communications failure. Consequently, a second, helper drone must be
deployed to retrieve the package to ensure successful delivery. The central
question of this study is to find the optimal trajectory for this second
drone. We demonstrate that the optimal solution relies heavily on the relative
spatial positioning of the command station, the destination point, and the
last known location of the disconnected drone.

###### keywords:

delivery, drone, search theory, competitive ratio, online algorithm

###### category:

##  1 Introduction

In recent years, drone-based package delivery has emerged as a promising
application of unmanned aerial vehicle (UAV) technology. As these systems are
increasingly integrated into supply chain infrastructures, it becomes
imperative to design algorithms for their robust operation amidst unexpected
complications. In this paper, we consider a complication arising from faulty
communication and propose a solution for a cooperative delivery problem
inspired by this scenario.

Consider a situation where a drone, en route to deliver a package to a given
destination, unexpectedly loses communication with its central command
station. This unexpected loss of contact leaves the command station uncertain
of whether the drone has suffered a communications breakdown or complete
system failure. Furthermore, even if the issue is only with the
communications, the command station no longer has any way of knowing if/where
the drone will fail on the rest of its way to the destination. In order to
guarantee the package gets delivered, the command station must dispatch a
second helper drone to retrieve the package and complete the delivery. Our
goal is to design an online algorithm (one that cannot anticipate the true
fail location of the drone) that, given the drone’s last known location,
determines the best trajectory for the second drone to find the package and
complete the delivery in minimal time.

Formally, let us denote the last known location of the drone as the origin
$S=(0,0)$, the destination as the point $T=(1,0)$, and the location of the
command station as $P=(x,y)$, where $y\geq 0$ (all without loss of
generality). The task is to identify the optimal trajectory for the second
drone that minimizes the competitive ratio when compared to an optimal offline
algorithm that knows the exact failure location $(t,0)$ of the first drone in
advance. We assume the first drone will fail at some time $0\leq t\leq 1$ (if
it does not fail the delivery time is optimal and the problem is
uninteresting). Also, to simplify notation, we only consider the package to be
delivered once the second drone and the package are co-located at the
destination (i.e., if $t=1$ and the first drone fails at the destination, the
package is only delivered once the second drone reaches $T$). For an algorithm
$\mathcal{A}(x,y)$, which defines the trajectory of the second drone, let
$A(x,y,t)$ denote the delivery time of algorithm $\mathcal{A}(x,y)$ for
failure time $t$. Our goal is to find an online algorithm (where $t$ is
unknown) with minimum competitive ratio with respect to the delivery time of
an optimal offline algorithm, Opt$(x,y,t)$ (where $t$ is known ahead of time).
The competitive ratio for algorithm $\mathcal{A}(x,y)$ for a given fail time
$t$ can be written as

$\displaystyle\text{CR}_{\mathcal{A}(x,y)}(t)=\frac{A(x,y,t)}{\text{Opt}(x,y,t)}.$

Then the competitive ratio of $\mathcal{A}(x,y)$ is

$\displaystyle\text{CR}_{\mathcal{A}(x,y)}=\sup_{t}\text{CR}_{\mathcal{A}(x,y)}(t).$

In order to simplify notation we sometimes eliminate $x$ and $y$ (when they
are clear from context) and write algorithm $\mathcal{A}(x,y)$ as
$\mathcal{A}$ and its delivery time $A(x,y,t)$ as $A(t)$.

###  1.1 Model and Notation

In this section, we describe the model and notation used throughout the paper.
We call the first drone (the drone that is initially carrying the package
towards the destination) the starter and the second drone, which completes the
delivery, the finisher. Without loss of generality, let $S=(0,0)$ be the
initial location of the starter (the point where it loses communication with
the central command station) and $T=(1,0)$ be the destination point on the
plane. The starter drone begins at point $S$ carrying the package and moves
following a straight line directly towards point $T$. At some unknown time
$t\leq 1$, the starter will fail at position $(t,0)$.

The finisher drone starts at a point $P=(x,y)$ on the plane (i.e., at the
command station). Without loss of generality, we assume that $y\geq 0$ (all
results follow trivially by symmetry). We assume that both drones have a speed
of $1$ and always move at this speed. The finisher can start, stop, and change
direction instantaneously. The drones can communicate with each other and
exchange the package only when they are co-located (face-to-face
communication). The package is considered to be delivered as soon as the
finisher and the package are co-located at $T$.

Let $D(c,r)$ ($\overline{D}(c,r)$) denote the open (closed) disk with radius
$r$ centered at point $(c,0)$. We use capital letters to denote points, $|PQ|$
to denote the Euclidean distance between two points $P$ and $Q$, and
$\overline{PQ}$ to denote the line segment with endpoints $P$ and $Q$.

###  1.2 Related Work

An important aspect of our problem is that the starter agent experiences a
failure. Many problems with cooperative mobile agent experiencing failures
have been studied for a variety of basic problems in distributed computing and
in various domains. In [9], the authors study the search problem on the line
by $n$ mobile agents where $f$ of the agents are faulty. They present
algorithms and their competitive ratios for different values of $f$. In [11]
the authors study the evacuation problem on the disk by $n$ agents, $f$ of
which may be faulty. Competitive algorithms for gathering have been proposed
for $n$ agents in a synchronous system with less than $(n-1)/3$ failures [1].
Optimal algorithms and hardness results for the multi-agent patrolling problem
with faulty agents were presented in [7]. Algorithms for flocking [13] and
evacuation [8] have also been studied in the context of faulty agents.

The problem studied in this paper has both search and delivery components.
Many search problems have been studied for different domains and under
different models and assumptions (cf. the book [2]). The authors of [6]
consider the delivery problem for messages on the line segment by multiple
agents with different speeds and propose competitively optimal algorithms. The
results of the previous study were also extended to the plane [5]. Joint
search and delivery problems, however, have received much less attention in
the literature. The problem has also been studied for the single- and two-
agent case on the line [4]. On the systems research side, many solutions for
drone-assisted package delivery have been proposed for different environments
and under different assumptions (we refer the reader to the survey [12]).

Most related but different to our delivery problem are the papers [3] and [10]
on package delivery. In the former, the authors investigate delivery of one or
two packages of many autonomous mobile agents initially located on distinct
nodes of a weighted graph. In the latter paper, they are concerned with
delivering a package from a source node to a destination node in a graph using
a set of drones and study the setting where the movements of each drone are
restricted to a certain subgraph of the given graph. Note that both papers
above address the delivery problem in a graph setting. To the best of our
knowledge our paper is the first to address delivery of a package in the plane
in the presence of a faulty drone.

###  1.3 Results

The main result we present is an optimal online algorithm that depends only on
the starting position of the finisher (the central command station).
Essentially, the algorithm executes one of three candidate algorithms
depending on the finisher’s starting position. This is depicted in Figure 1.

Figure 1: The optimal algorithm depends on the starting position of the
finisher. The striped regions depict the finisher starting positions for which
each of the three candidate algorithms is optimal.

If the finisher starts in the diagonally striped region, then the optimal
algorithm is for the finisher to go to $S$ (the origin) and then towards the
destination until finding the failed starter with the object. If the finisher
starts in the vertically striped region, the optimal algorithm is for the
finisher to go first to $T$ (the destination) and then toward $S$ until
finding the failed starter with the object. Finally, if the finisher starts in
the horizontally striped region, then the optimal algorithm is for the starter
to go to the point $M=\left(\left(x^{2}+y^{2}\right)/(2x),0\right)$ and then
toward $S$ until finding the failed starter with the object. We will show that
the finisher is guaranteed to find the starter on the interval $[0,M]$.

The rest of the paper is organized as follows. In Section 2, we detail the
three candidate algorithms and derive each of their competitive ratios as a
function of the command station’s starting position. Then, in Section 3, we
present a hybrid algorithm that chooses the best of the three candidate
algorithms to run based on the command station’s starting position $(x,y)$. We
prove this algorithm is optimal, and then (in Section 4) discuss how the
command station’s position affects which of the candidate algorithms is
executed in the optimal hybrid algorithm. We conclude the paper in Section 5
with a summary of the results and a discussion of future directions.

##  2 Candidate Algorithms

In this section, we present three algorithms and derive their competitive
ratios. In order to do so, we must first consider the optimal offline
algorithm, where the fail location $(t,0)$ (at time $t$) is known ahead of
time and can be used to compute the optimal trajectory for the finisher.
Clearly in this case the finisher should go directly from its starting
location to the starter’s fail location $(t,0)$ and then complete the
delivery. The delivery time then can be written:

$\displaystyle\text{Opt}(t)=\max\left\\{1,\sqrt{(x-t)^{2}+y^{2}}+1-t\right\\}.$

Indeed, although the finisher moves directly to $(t,0)$, it may have to wait
for the starter to arrive (if necessary) prior to completing the delivery
task.

For the online algorithms, we start by reasoning about what an optimal
algorithm looks like. First, since the starter must fail at some point on the
line segment $\overline{ST}$, the finisher must _eventually_ move from its
initial location to some point $(m,0)$ on the segment (otherwise it will never
find the starter with the package). We use this to prove the following
intuitively obvious lemma:

######  Lemma 2.1.

There exists an online algorithm with optimal competitive ratio that involves
the finisher moving from its initial position $P=(x,y)$ directly to a point
$M=(m,0)\in\overline{ST}$, past which, it remains within the line segment
$\overline{ST}$.

######  Proof 2.2.

Let $M=(m,0)$ denote the first point the finisher reaches on $\overline{ST}$.
We first show that the finisher should move _directly_ to $M$. Consider, for
the sake of contradiction, an algorithm that involves the finisher moving from
its initial position $P=(x,y)$ to a point
$P_{1}=(x_{1},y_{1})\notin\overline{PM}$ and then to point $M=(m,0)$ before
finding the starter and delivering the package to the destination. Clearly,
since the finisher could not have found the starter at any point not in
$\overline{ST}$, and $|PP_{1}|+|P_{1}M|>|PM|$ (triangle inequality), then the
algorithm where the finisher moves directly to $M$ delivers the package at
least as fast.

Now we show that the finisher should stay on the line segment $\overline{ST}$
after reaching it for the first time. Again, for the sake of contradiction,
consider an algorithm which involves the finisher moving from
$M=(m,0)\in\overline{ST}$ to a point $P_{2}=(x_{2},y_{2})\notin\overline{ST}$
and then back to a point $M_{1}=(m_{1},0)\in\overline{ST}$ before finding the
starter and delivering the package to the destination. Since the finisher
could not have found the failed starter at any point not in $\overline{ST}$,
and $|MP_{2}|+|P_{2}M_{1}|>|MM_{1}|$ (triangle inequality), then the algorithm
where the finisher moves directly from $M$ to $M_{1}$ (never leaving
$\overline{ST}$) delivers the package at least as fast.

Now, we present three candidate online algorithms:

  1. 1.

$\mathcal{A}_{0}$ (Go To Last Point of Contact): The finisher moves to the
origin $S=(0,0)$ and then towards the destination until it finds the failed
starter (trajectory $P\rightarrow S\rightarrow T$).

  2. 2.

$\mathcal{A}_{1}$ (Go To Destination): The finisher goes first to the
destination $T=(1,0)$ and then towards the origin until it finds the failed
starter (trajectory $P\rightarrow T\rightarrow S\rightarrow T$).

  3. 3.

$\mathcal{A}_{d}$ (Meet in the Middle): The finisher goes first to the point
$(d,0)$, where $d=(x^{2}+y^{2})/(2x)$, and then towards the origin until it
finds the failed starter (trajectory $P\rightarrow(d,0)\rightarrow
S\rightarrow T$). The point $(d,0)$ is the unique point on the line segment
where the drones, both moving continuously, would meet simultaneously if the
starter does not fail before time $d$.

######  Lemma 2.3.

$\text{CR}_{\mathcal{A}_{d}(x,y)}\leq\text{CR}_{\mathcal{A}_{1}(x,y)}$ if and
only if the finisher starts within distance $1$ of the destination (i.e.,
$(x,y)\in\overline{D}(1,1)$).

######  Proof 2.4.

First, we show that if the finisher’s starting position $(x,y)$ is within a
distance $1$ of the destination (i.e., $(x,y)\in\overline{D}(1,1)$ or
equivalently $\sqrt{(x-1)^{2}+y^{2}}\leq 1$), then
$\text{CR}_{\mathcal{A}_{d}}(t)\leq\text{CR}_{\mathcal{A}_{1}}(t)$ for any
fail time $t$. Observe that if the finisher is executing algorithm
$\mathcal{A}_{d}$ and $t\geq d$, then the starter fails only after the
finisher encounters it at $(d,0)$, and so the algorithm is optimal. Thus, the
competitive ratio for $\mathcal{A}_{d}$ can be written:

$\displaystyle\text{CR}_{\mathcal{A}_{d}}(t)=\frac{A_{d}(t)}{\text{Opt}(t)}=\begin{cases}1&\text{if
}t\geq d\\\
\frac{\sqrt{(x-d)^{2}+y^{2}}+(d-t)+(1-t)}{\sqrt{(t-x)^{2}+y^{2}}-t+1}&\text{otherwise.}\end{cases}$

Observe the max term is removed from $\text{Opt}(t)$ since

$\displaystyle t$ $\displaystyle<d=\frac{x^{2}+y^{2}}{2x}$ $\displaystyle 2xt$
$\displaystyle<x^{2}+y^{2}$ $\displaystyle t^{2}$
$\displaystyle<x^{2}-2xt+t^{2}+y^{2}$ $\displaystyle 1$
$\displaystyle<\sqrt{x^{2}-2xt+t^{2}+y^{2}}-t+1.$

If $t\geq d$, then the statement is trivially true since $\mathcal{A}_{d}$ is
optimal. Otherwise, since $(x,y)\in\overline{D}(1,1)$, then
$d=(x^{2}+y^{2})/(2x)\leq 1$ and thus:

$\displaystyle A_{d}(t)$
$\displaystyle=\sqrt{(x-d)^{2}+y^{2}}+d+1-2t\leq\sqrt{(x-1)^{2}+y^{2}}+2-2t=A_{1}(t).$

Now, we show that if the finisher starts a distance greater than $1$ from the
destination, then $A_{d}(t)>A_{1}(t)$ for any fail time $t$ (and thus
$\text{CR}_{\mathcal{A}_{d}}>\text{CR}_{\mathcal{A}_{1}}$). This follows from
the fact that $d=(x^{2}+y^{2})/(2x)>1$ and thus:

$\displaystyle A_{d}(t)$
$\displaystyle=\sqrt{(x-d)^{2}+y^{2}}+d+1-2t>\sqrt{(x-1)^{2}+y^{2}}+2-2t=A_{1}(t).$

Lemma 2.3 essentially tells us that we need only consider (among the candidate
algorithms) $\mathcal{A}_{0}$ and $\mathcal{A}_{d}$ when the finisher starts
inside the disk and algorithms $\mathcal{A}_{0}$ and $\mathcal{A}_{1}$ when
the finisher starts outside the disk. Note that, when $(x,y)$ is on the edge
of the disk $\overline{D}(1,1)$ (i.e., $(x-1)^{2}+y^{2}=1$), then $d=1$ and so
$\mathcal{A}_{d}$ and $\mathcal{A}_{1}$ are the same algorithm.

###  2.1 Go to Last Point of Contact

In this section, we derive the competitive ratio of Algorithm
$\mathcal{A}_{0}$. Observe that, no matter the failure time of the starter,
the algorithm takes time $1+\sqrt{x^{2}+y^{2}}$ to deliver the message. This
fact makes deriving the algorithm’s competitive ratio rather simple.

######  Theorem 2.5.

The competitive ratio of $\mathcal{A}_{0}$ is

$\displaystyle\text{CR}_{\mathcal{A}_{0}}=\frac{1+\sqrt{x^{2}+y^{2}}}{\max\left\\{1,\sqrt{(x-1)^{2}+y^{2}}\right\\}}.$

######  Proof 2.6.

Recall that the competitive ratio is given by the formula

$\displaystyle\sup_{0\leq t\leq
1}\frac{1+\sqrt{x^{2}+y^{2}}}{\max\left\\{1,\sqrt{(x-t)^{2}+y^{2}}+1-t\right\\}}.$

Observe the denominator is non-increasing with respect to $t$ (on $t\in[0,1]$)
and attains a minimum at $t=1$. The competitive ratio, then is:

$\displaystyle\frac{1+\sqrt{x^{2}+y^{2}}}{1+\max\left\\{0,\sqrt{(x-1)^{2}+y^{2}}-1\right\\}}$
$\displaystyle=\frac{1+\sqrt{x^{2}+y^{2}}}{\max\left\\{1,\sqrt{(x-1)^{2}+y^{2}}\right\\}}.$

###  2.2 Go to Destination

We will now derive the competitive ratio of algorithm $\mathcal{A}_{1}$.
Unlike the delivery time of algorithm $\mathcal{A}_{0}$, the delivery time
$A_{1}(t)=\sqrt{(x-1)^{2}+y^{2}}+2(1-t)$ (the time for the agent to go to
$(1,0)$ and then backtrack until it finds the package at $(t,0)$ before
returning to $(1,0)$ to complete the delivery) depends greatly on the fail
time of the starter. Thus, to find the competitive ratio of algorithm
$\mathcal{A}_{1}$, we must find the worst-case fail time for a given finisher
starting position $(x,y)$.

######  Theorem 2.7.

Assume $(x,y)\not\in D(1,1)$ (i.e., $\sqrt{(x-1)^{2}+y^{2}}\geq 1$). The
competitive ratio of $\mathcal{A}_{1}$ is

$\text{CR}_{\mathcal{A}_{1}}(\max\left\\{t_{1},0\right\\})$

where

$\displaystyle t_{1}=\begin{cases}1-3y/4&\text{if }x=1\\\
\frac{x^{2}+y^{2}+z_{1}(1-x)-1-z_{1}\sqrt{x(x+z_{1}-2)+y^{2}-z_{1}+1}}{2(x-1)}&\text{otherwise}\end{cases}$

and $z_{1}=\sqrt{(x-1)^{2}+y^{2}}$.

######  Proof 2.8.

Note that $z_{1}$ is the distance from the finisher’s initial location to the
destination. Since $\sqrt{(x-1)^{2}+y^{2}}\geq 1$, then observe
$\sqrt{(x-t)^{2}+y^{2}}\geq t$ for all $0\leq t\leq 1$. Thus, the delivery
time for the optimal offline algorithm can be simplified (namely, the max
expression can be removed):

$\displaystyle\text{Opt}(t)$
$\displaystyle=\max\left\\{1,\sqrt{(x-t)^{2}+y^{2}}+1-t\right\\}=\sqrt{(x-t)^{2}+y^{2}}+1-t.$

Thus the competitive ratio of $\mathcal{A}_{1}$ can be written:

$\displaystyle\sup_{0\leq t\leq 1}\text{CR}_{\mathcal{A}_{1}}(t)$
$\displaystyle=\sup_{0\leq t\leq 1}\frac{A_{1}(t)}{\text{Opt}(t)}=\sup_{0\leq
t\leq 1}\frac{\sqrt{(x-1)^{2}+y^{2}}+2(1-t)}{\sqrt{(x-t)^{2}+y^{2}}+1-t}.$

To determine which value of $t$ maximizes $\text{CR}_{\mathcal{A}_{1}}(t)$, we
can find the extremum of $\text{CR}_{\mathcal{A}_{1}}(t)$ by solving for
$\frac{\partial}{\partial t}\text{CR}_{\mathcal{A}_{1}}(t)=0$. The derivative
of $\text{CR}_{\mathcal{A}_{1}}(t)$ with respect to $t$ is

$\displaystyle\frac{\left(1-\frac{t-x}{\sqrt{(t-x)^{2}+y^{2}}}\right)\left(\sqrt{(x-1)^{2}+y^{2}}+2(1-t)\right)}{\left(\sqrt{(t-x)^{2}+y^{2}}+1-t\right)^{2}}-\leavevmode\nobreak\
\frac{2}{\sqrt{(t-x)^{2}+y^{2}}+1-t}.$

Then by setting $\frac{\partial}{\partial t}\text{CR}_{\mathcal{A}_{1}}(t)=0$
and solving for $t$, we get one solution when $x=1$:

$\displaystyle t_{x=1}=1-\frac{3y}{4}$

and two solutions111These solutions were derived with the aid of Mathematica
(notebook available at https://anonymous.4open.science/r/faulty_delivery-D37F
) when $x\not=1$:

$\displaystyle t_{-}$
$\displaystyle=\frac{x^{2}+y^{2}+z_{1}(1-x)-1-z_{1}\sqrt{x(x+z_{1}-2)+y^{2}-z_{1}+1}}{2(x-1)}$
$\displaystyle t_{+}$
$\displaystyle=\frac{x^{2}+y^{2}+z_{1}(1-x)-1+z_{1}\sqrt{x(x+z_{1}-2)+y^{2}-z_{1}+1}}{2(x-1)}$

Observe, though, that $t_{+}\geq 1$ when $x>1$ and $t_{+}<0$ when $x<1$, so
$t_{+}$ cannot be a valid solution. Observe also that
$\text{CR}_{\mathcal{A}_{1}}(1)=1$ (the algorithm is optimal if the failure
occurs at $(1,0)$) and $\text{CR}_{\mathcal{A}_{1}}(t_{-})\geq 1$ (the
competitive ratio, by construction, cannot be less than $1$). Then, since
$\text{CR}_{\mathcal{A}_{1}}(t)$ is continuous,
$\text{CR}_{\mathcal{A}_{1}}(t_{-})$ must be a local extremum. Furthermore,
since $t_{-}\leq 1$ for all $(x,y)$, $\text{CR}_{\mathcal{A}_{1}}(t)$ is
decreasing on the interval $[\max\left\\{t_{-},0\right\\},1]$. Thus,
$\text{CR}_{\mathcal{A}_{1}}(t)$ is maximized at
$t=\max\left\\{0,t_{-}\right\\}$ and the theorem is proved.

Figure 2: The worst-case fail time for the starter is $0$ except in the gray
shaded region, where the worst-case fail time is $t_{-}$ (from the proof of
Theorem 2.7). Recall that we only consider $\mathcal{A}_{1}$ when the finisher
starts outside of the Disk $D(1,1)$.

There are essentially two cases that drive the competitive ratio of Algorithm
$\mathcal{A}_{1}$: when $t_{1}$ (from the statement/proof of Theorem 2.7) is
less than or equal to $0$ and when it is greater than $0$. Observe the value
of $t_{1}$ is determined by the finisher’s starting position $(x,y)$. When
$t_{1}\leq 0$ (i.e., when the finisher starts outside of the gray region shown
in Figure 2), the competitive ratio is driven by the case where the starter
fails at the origin (as soon as it loses contact with the command station).
When $t_{1}>0$, though, the worst-case scenario for $\mathcal{A}_{1}$ is
actually when the starter fails at time $t_{1}$ (and thus, at location
$(t_{1},0)$).

###  2.3 Meet in the Middle

In this section, we derive the competitive ratio of the last candidate
algorithm, $\mathcal{A}_{d}$, where the finisher moves from its starting
position to the point $d=(x^{2}+y^{2})/(2x)$, then towards the origin until it
finds the starter with the package before completing the delivery. Recall from
Lemma 2.3 that we need only consider algorithm $\mathcal{A}_{d}$ inside the
closed disk centered at $(1,0)$ with radius $1$, namely $\overline{D}(1,1)$.
Furthermore, observe that on the edge of this disk $d=1$ and so algorithms
$\mathcal{A}_{d}$ and $\mathcal{A}_{1}$ are equal. By construction, then, the
finisher must find the starter between the origin and the point $(d,0)$ since
$(d,0)$ is the unique point on $\overline{ST}$ such that the distance between
the origin and $(d,0)$ is equal to the distance from $(x,y)$ to $0$ (i.e., it
is the point where the two drones would meet simultaneously if the starter
does not fail). It’s easy to derive that $d=(x^{2}+y^{2})/(2x)$ by solving
$\sqrt{\left(x-d\right)^{2}+y^{2}}=d$ for $d$ using simple algebra. Thus, at
time $d$, the finisher reaches point $(d,0)$ and the starter cannot have
reached any point further than $(d,0)$.

######  Theorem 2.9.

Assume $(x,y)\in\overline{D}(1,1)$ (i.e., $\sqrt{(x-1)^{2}+y^{2}}\leq 1)$. The
competitive ratio of $\mathcal{A}_{d}$ is

$\displaystyle\text{CR}_{\mathcal{A}_{d}}=\begin{cases}\frac{x^{2}+y^{2}+x}{x\left(1+\sqrt{x^{2}+y^{2}}\right)}&\text{if
}(x,y)\in\overline{D}(1/2,1/2)\\\
1+\frac{y^{2}}{x\left(\sqrt{x}+1\right)^{2}}&\text{otherwise.}\end{cases}$

######  Proof 2.10.

We will derive the competitive ratio by finding the fail time $t$ that
maximizes $\text{CR}_{\mathcal{A}_{d}}(t)$. Recall that $(d,0)$ is the
location the finisher moves to in the $A_{d}$ algorithm (where
$d=\frac{x^{2}+y^{2}}{2x}$). Observe that when $t\geq d$, the starter fails
only after it has met up with the finisher (and so the package delivery time
is optimal and the competitive ratio is $1$). For this reason we need only
consider fail times $t<d$. Observe also that,

$\displaystyle t$ $\displaystyle<d=\frac{x^{2}+y^{2}}{2x}$ $\displaystyle 2xt$
$\displaystyle<x^{2}+y^{2}$ $\displaystyle 0$ $\displaystyle<x^{2}-2xt+y^{2}$
$\displaystyle t^{2}$ $\displaystyle<x^{2}-2xt+t^{2}+y^{2}$ $\displaystyle
t^{2}$ $\displaystyle<(x-t)^{2}+y^{2}$ $\displaystyle 0$
$\displaystyle<\sqrt{(x-t)^{2}+y^{2}}-t$

which means we can simplify

$\text{Opt}(t)=\max\left\\{1,\sqrt{(x-t)^{2}+y^{2}}+1-t\right\\}$

and remove the max term, so

$\text{Opt}(t)=\sqrt{(x-t)^{2}+y^{2}}+1-t.$

Then the competitive ratio of Algorithm $\mathcal{A}_{d}$ can be written:

$\displaystyle\text{CR}_{\mathcal{A}_{d}}$ $\displaystyle=\sup_{0\leq
t<d}\text{CR}_{\mathcal{A}_{d}}(t)$ $\displaystyle=\sup_{0\leq
t<d}\vphantom{\rule{0.0pt}{21.52771pt}}\frac{A_{d}(t)}{\text{Opt}(t)}$
$\displaystyle=\sup_{0\leq
t<d}\frac{\sqrt{(x-d)^{2}+y^{2}}+(d-t)+(1-t)}{\sqrt{(t-x)^{2}+y^{2}}-t+1}.$

We can find the extremum of $\text{CR}_{\mathcal{A}_{d}}(t)$ by solving for

$\frac{\partial}{\partial t}\text{CR}_{\mathcal{A}_{d}}(t)=0.$

The derivative of $\text{CR}_{\mathcal{A}_{d}}(t)$ with respect to $t$ is222We
compute this derivative with the aid of Mathematica (notebook available at
https://anonymous.4open.science/r/faulty_delivery-D37F ).

$\frac{\partial}{\partial
t}\text{CR}_{\mathcal{A}_{d}}(t)=\frac{t\leavevmode\nobreak\
b_{0}+b_{1}(\sqrt{(x-t)^{2}+y^{2}}-x)}{x\leavevmode\nobreak\
\sqrt{(x-t)^{2}+y^{2}}(\sqrt{(x-t)^{2}+y^{2}}-t+1)}$ (1)

where $b_{0}=x(x-1)-y^{2}$, $b_{1}=x(x-1)-y^{2}$. Then, to find where the
derivative is equal to $0$, let
$b=-\frac{b_{0}}{b_{1}}=\frac{y^{2}-x(x-1)}{y^{2}+x(x-1)}$.

$\displaystyle\frac{\partial}{\partial t}\text{CR}_{\mathcal{A}_{d}}(t)$
$\displaystyle=0$ $\displaystyle\frac{t\leavevmode\nobreak\
b_{0}+b_{1}(\sqrt{(x-t)^{2}+y^{2}}-x)}{x\leavevmode\nobreak\
\sqrt{(x-t)^{2}+y^{2}}(\sqrt{(x-t)^{2}+y^{2}}-t+1)}$ $\displaystyle=0$
$\displaystyle t\leavevmode\nobreak\ b_{0}+b_{1}(\sqrt{(x-t)^{2}+y^{2}}-x)$
$\displaystyle=0$ $\displaystyle t\frac{-b_{0}}{b_{1}}$
$\displaystyle=\sqrt{(x-t)^{2}+y^{2}}-x$ $\displaystyle(bt+x)^{2}$
$\displaystyle=(x-t)^{2}+y^{2}$ (2)

Solving Equation (2) for $t$, we get the two solutions:

$\displaystyle
t_{-}=\frac{-x(b+1)-\sqrt{(b+1)((b+1)x^{2}+(b-1)y^{2})}}{b^{2}-1}$
$\displaystyle
t_{+}=\frac{-x(b+1)+\sqrt{(b+1)((b+1)x^{2}+(b-1)y^{2})}}{b^{2}-1}$

Upon replacing $b$ with $\frac{y^{2}-x(x-1)}{y^{2}+x(x-1)}$ and
simplifying333We simplified these with the aid of Mathematica (notebook
available at https://anonymous.4open.science/r/faulty_delivery-D37F )., we get
the solutions

$\displaystyle t_{-}=\begin{cases}\frac{x(x-1)+y^{2}}{2(x-\sqrt{x})}&\text{if
}x^{2}+y^{2}>x\\\
\frac{x(x-1)+y^{2}}{2(x+\sqrt{x})}&\text{otherwise}\end{cases}$ $\displaystyle
t_{+}=\begin{cases}\frac{x(x-1)+y^{2}}{2(x-\sqrt{x})}&\text{if
}x^{2}+y^{2}\leq x\\\
\frac{x(x-1)+y^{2}}{2(x+\sqrt{x})}&\text{otherwise}\end{cases}$

Observe, then, in both regions $x^{2}+y^{2}>x$ and $x^{2}+y^{2}\leq x$ (inside
and outside of $D(1/2,1/2)$), $\text{CR}_{\mathcal{A}_{d}}(t)$ has a local
maximum either at $t^{\prime}=\frac{x(x-1)+y^{2}}{2(x+\sqrt{x})}$ or at
$t^{\prime\prime}=\frac{x(x-1)+y^{2}}{2(x-\sqrt{x})}$. We will use the
following two claims to show that an upper bound on the competitive ratio for
$\mathcal{A}_{d}$ is given by $t=t^{\prime}$ whenever $t^{\prime}>0$ and $t=0$
otherwise.

Claim 1: $CR_{\mathcal{A}_{d}}(t^{\prime})$ is a local maximum.
Proof for Claim 1: Follows by second derivative test444See the Mathematica
notebook available at https://anonymous.4open.science/r/faulty_delivery-D37F
for a detailed walk-through, namely

$CR_{\mathcal{A}_{d}}^{{}^{\prime\prime}}(t^{\prime})<0$

for all $x,y\geq 0$. ∎

Claim 2: $t^{\prime}<1$.
Proof for Claim 2: Since $(x,y)\in D(1,1)$, then $y^{2}<1-(x-1)^{2}$ and since
$t^{\prime}$ is increasing with respect to $y$

$\displaystyle t^{\prime}$
$\displaystyle=\frac{x(x-1)+y^{2}}{2(x+\sqrt{x})}<\frac{x(x-1)+(1-(1-x)^{2})}{2(x+\sqrt{x})}=\frac{1}{2+2/\sqrt{x}}.$

Furthermore, since $\frac{1}{2+2/\sqrt{x}}$ is increasing with respect to $x$
and $x<2$ (again, by the assumption that $(x,y)\in D(1,1)$), then

$\displaystyle\frac{1}{2+2/\sqrt{x}}<\frac{1}{2+2/\sqrt{2}}<1$

and thus, $t^{\prime}<1$. ∎

Since $\text{CR}_{\mathcal{A}_{d}}(t)$ is decreasing on $(t^{\prime},1]$ (by
Claim 2.10) and $CR_{\mathcal{A}_{d}}(t)$ is continuous on $t\leq 1$, then
$\text{CR}_{\mathcal{A}_{d}}(t^{\prime})$ is a local maximum on $[0,1]$ (and
thus $\text{CR}_{\mathcal{A}_{d}}(t^{\prime\prime})$ is not a local maximum on
$[0,1]$). Furthermore, since $t^{\prime}<1$ (by Claim 2.10),
$\text{CR}_{\mathcal{A}_{d}}(t)$ is maximized at $t=t^{\prime}$ whenever
$t^{\prime}>0$ and $t=0$ otherwise. Plugging these values into
$\text{CR}_{\mathcal{A}_{d}}(t)$ yields the value stated in the theorem.

Similar to Algorithm $\mathcal{A}_{1}$, two cases drive Algorithm
$\mathcal{A}_{d}$’s competitive ratio. The first is when $t^{\prime}$ (from
the proof of Theorem 2.9) is less than $0$, whenever the starting position of
the finisher is inside the disk $\overline{D}(1/2,1/2)$. In this case, the
worst-case failure time for the starter is $t=0$ (i.e., at the origin). When
the finisher starts outside of the disk $\overline{D}(1/2,1/2)$ (but inside
the disk $\overline{D}(1,1)$, of course, since we only consider Algorithm
$\mathcal{A}_{d}$ in this region), however, the worst-case failure time for
the starter is $t=t^{\prime}$ (i.e., at location $(t^{\prime},0)$, see Figure
3).

Figure 3: The worst-case fail time for the starter is $0$ except in the gray
shaded region, where the worst-case fail time is $t^{\prime}$ (from the proof
of Theorem 2.9). Recall that we only consider $\mathcal{A}_{d}$ when the
finisher starts inside the Disk $\overline{D}(1,1)$.

##  3 A Hybrid Algorithm

For convenience, we summarize our main result by introducing Algorithm 1, a
hybrid algorithm which simply executes the best of $\mathcal{A}_{0}$,
$\mathcal{A}_{1}$, and $\mathcal{A}_{d}$ given a finisher starting position
$(x,y)$, and prove it to be optimal.

Algorithm 1 A hybrid algorithm combining $\mathcal{A}_{0}$, $\mathcal{A}_{1}$,
and $\mathcal{A}_{d}$

1:input: Finisher starting position $(x,y)$

2:if $(x-1)^{2}+y^{2}>1$ then $\triangleright$ The starter starts outside of
$D(1,1)$

3: if $\text{CR}_{\mathcal{A}_{0}(x,y)}\leq\text{CR}_{\mathcal{A}_{1}(x,y)}$
then

4: Execute Algorithm $\mathcal{A}_{0}$

5: else

6: Execute Algorithm $\mathcal{A}_{1}$

7:else

8: if $\text{CR}_{\mathcal{A}_{0}(x,y)}\leq\text{CR}_{\mathcal{A}_{d}(x,y)}$
then

9: Execute Algorithm $\mathcal{A}_{0}$

10: else

11: Execute Algorithm $\mathcal{A}_{d}$

In fact, we will show that Algorithm 1 is optimal by proving that any other
algorithm $A_{a}$ which moves first to a position $(a,0)$ such that $0<a<1$
and $a\neq d$ is always worse than at least one of the candidate algorithms
$\mathcal{A}_{0}$, $\mathcal{A}_{1}$, or $\mathcal{A}_{d}$. Recall from Lemma
2.1 that we do not need to consider any other algorithms. Leveraging Lemma
2.3, we know that we only need consider $\mathcal{A}_{0}$ and
$\mathcal{A}_{d}$ when the finisher’s starting position $(x,y)$ is inside the
disk $\overline{D}(1,1)$ and algorithms $\mathcal{A}_{0}$ and
$\mathcal{A}_{1}$ when it is outside the disk (recall that $\mathcal{A}_{d}$
and $\mathcal{A}_{1}$ are equivalent on the border of $\overline{D}(1,1)$).
The following lemmas cover each of these cases.

######  Lemma 3.1.

For any $(x,y)\in\overline{D}(1,1)$,
$\min\left\\{\text{CR}_{\mathcal{A}_{d}},\text{CR}_{\mathcal{A}_{0}}\right\\}\leq\text{CR}_{\mathcal{A}_{a}}$
for all $a\in\overline{ST}$.

######  Proof 3.2.

We will prove the lemma by examining various cases. Let $t_{d}$ denote the
worst-case starter fail time for algorithm $\mathcal{A}_{d}$ for the finisher
starting position $(x,y)$. Recall that $(a,0)$, as defined above, is the first
point on $\overline{ST}$ that the finisher reaches by executing algorithm
$\mathcal{A}_{a}$.

Case 1: $a\geq d$. Consider the case where the starter fails at $(t_{d},0)$.
Then the competitive ratio of the algorithm is:

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+(a-t_{d})+(1-t_{d})}{\max\left\\{1,\sqrt{(x-t_{d})^{2}+y^{2}}+1-t_{d}\right\\}}$
$\displaystyle\geq\frac{\sqrt{(x-d)^{2}+y^{2}}+(d-t_{d})+(1-t_{d})}{\max\left\\{1,\sqrt{(x-t_{d})^{2}+y^{2}}+1-t_{d}\right\\}}$
$\displaystyle=\text{CR}_{\mathcal{A}_{d}}.$

Case 2: $a<d$ and finisher visits $S$ before visiting $T$. Set failure to be
$T$ then $\text{CR}_{\mathcal{A}_{0}}\leq\text{CR}_{\mathcal{A}_{a}}$. Indeed,

$\displaystyle\text{CR}_{\mathcal{A}_{a}}\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+a+1}{\sqrt{(x-1)^{2}+y^{2}}}\geq\frac{\sqrt{x^{2}+y^{2}}+1}{\sqrt{(x-1)^{2}+y^{2}}}=\text{CR}_{\mathcal{A}_{0}}.$

Case 3: $a<d$ and finisher visits $1$ before visiting $0$.

Case 3a: finisher visits $t_{d}$ after visiting $1$. Consider the case where
the starter fails at time $t_{d}$. Then the competitive ratio of
$\mathcal{A}_{a}$ can be written:

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+(1-a)+2(1-t_{d})}{\max\left\\{1,\sqrt{(x-t_{d})^{2}+y^{2}}+1-t_{d}\right\\}}$
$\displaystyle\geq\frac{\sqrt{(x-d)^{2}+y^{2}}+(d-t_{d})+(1-t_{d})}{\max\left\\{1,\sqrt{(x-t_{d})^{2}+y^{2}}+1-t_{d}\right\\}}$
$\displaystyle=\text{CR}_{\mathcal{A}_{d}}.$

Case 3b: finisher visits $t_{d}$ before visiting $1$. If $t_{d}=0$, then
$\text{CR}_{\mathcal{A}_{0}}\leq\text{CR}_{\mathcal{A}_{a}}$ by Case $1$.
Otherwise, consider the case where $t=0$ (i.e., the starter fails at the
origin). The competitive ratio of $\mathcal{A}_{a}$, then, is:

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+|a-t_{d}|+3-t_{d}}{\sqrt{x^{2}+y^{2}}+1}$
$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-t_{d})^{2}+y^{2}}+3-t_{d}}{\sqrt{x^{2}+y^{2}}+1}$

Then, by substituting $t_{d}=\frac{x(x-1)+y^{2}}{2(\sqrt{x}+x)}$ (this is the
worst-case fail time for algorithm $\mathcal{A}_{d}$ whenever $t_{d}>0$, see
the proof for Theorem 2.9), we get

$\displaystyle\frac{\sqrt{(x-t_{d})^{2}+y^{2}}+3-t_{d}}{\sqrt{x^{2}+y^{2}}+1}$
$\displaystyle=\frac{\sqrt{\left(x-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}\right)^{2}+y^{2}}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}.$

By expanding the term under the radical in the numerator and collecting like
terms, we arrive at

$\displaystyle\frac{\frac{\sqrt{y^{2}4(x+\sqrt{x})^{2}+[2x(x+\sqrt{x})-(x(x-1)+y^{2})]^{2}}}{2(x+\sqrt{x})}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}$

which can then be readily simplified (by continuing to multiply out and
collect like terms) to:

$\displaystyle\frac{\frac{\sqrt{y^{2}4(x+\sqrt{x})^{2}+[(x+\sqrt{x})^{2}-y^{2}]^{2}}}{2(x+\sqrt{x})}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}.$

Then, by factoring the expression under the radical in the numerator, we can
simplify further

$\displaystyle\frac{\frac{\sqrt{4(x+\sqrt{x})^{2}y^{2}+((x+\sqrt{x})^{2})^{2}-2(x+\sqrt{x})^{2}y^{2}+y^{4}}}{2(x+\sqrt{x})}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
=\frac{\frac{\sqrt{(y^{2}+(x+\sqrt{x})^{2})^{2}}}{2(x+\sqrt{x})}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}$
$\displaystyle\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\ \leavevmode\nobreak\
\leavevmode\nobreak\ \leavevmode\nobreak\
=\frac{\frac{y^{2}+(x+\sqrt{x})^{2}}{2(x+\sqrt{x})}+3-\frac{(x-1)x+y^{2}}{2\left(x+\sqrt{x}\right)}}{\sqrt{x^{2}+y^{2}}+1}$

and finally arrive at the final, rather simple, expression:

$\displaystyle\frac{3+\frac{y^{2}+x^{2}+2x\sqrt{x}+x-(x^{2}-x+y^{2})}{2(x+\sqrt{x})}}{\sqrt{x^{2}+y^{2}}+1}=\frac{3+\sqrt{x}}{\sqrt{x^{2}+y^{2}}+1}.$
(3)

Since $t_{d}>0$, then
$\text{CR}_{\mathcal{A}_{d}}=1+\frac{y^{2}}{x(\sqrt{x}+1)^{2}}$ by Theorem 2.9
and we have

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{3+\sqrt{x}}{\sqrt{x^{2}+y^{2}}+1}$ (4)
$\displaystyle\geq\frac{3+\sqrt{x}}{\sqrt{2x}+1}$ (5)
$\displaystyle\geq\frac{3+2\sqrt{x}}{(1+\sqrt{x})^{2}}$ (6) $\displaystyle\geq
1+\frac{y^{2}}{x(\sqrt{x}+1)^{2}}=\text{CR}_{\mathcal{A}_{d}}$ (7)

where (4) follows from (3), (5) and (7) follow since $x\in D(1,1)$ (and thus
$y^{2}\leq 1-(x-1)^{2}$ and $x>0$), and (6) is easy to see by expanding and
simplifying:

$\displaystyle\frac{3+\sqrt{x}}{\sqrt{2x}+1}$
$\displaystyle\geq\frac{3+2\sqrt{x}}{(1+\sqrt{x})^{2}}$ $\displaystyle
x^{3/2}+5x+7\sqrt{x}+3$ $\displaystyle\geq
2\sqrt{2}x+3\sqrt{2}\sqrt{x}+2\sqrt{x}+3$
$\displaystyle\sqrt{x}\left(x+\left(5-2\sqrt{2}\right)\sqrt{x}+5-3\sqrt{2}\right)$
$\displaystyle\geq 0$

which is trivially true since $x>0$, $5>2\sqrt{2}$, and $5\geq 3\sqrt{2}$.

Again, by Lemma 2.3, when the finisher starts outside of the disk $D(1,1)$, we
need only consider $\mathcal{A}_{0}$ and $\mathcal{A}_{1}$ (recall that, on
the edge of the disk $\overline{D}(1,1)$, $\mathcal{A}_{1}$ and
$\mathcal{A}_{d}$ are equivalent).

######  Lemma 3.3.

For any $(x,y)\not\in D(1,1)$, either
$\text{CR}_{\mathcal{A}_{1}}\leq\text{CR}_{\mathcal{A}_{a}}$ or
$\text{CR}_{\mathcal{A}_{0}}\leq\text{CR}_{\mathcal{A}_{a}}$ for all
$a\in\overline{ST}$.

######  Proof 3.4.

We will prove the lemma by examining various cases. Let $t_{1}$ denote the
worst-case fail time of $A_{1}$ for the finisher starting position $(x,y)$.

Case 1: The finisher visits $S$ before visiting $T$. Then let $t=1$, and the
competitive ratio of $\mathcal{A}_{a}$ is

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+a+1}{\max\left\\{1,\sqrt{(x-1)^{2}+y^{2}}\right\\}}\geq\frac{\sqrt{x^{2}+y^{2}}+1}{\max\left\\{1,\sqrt{(x-1)^{2}+y^{2}}\right\\}}=\text{CR}_{\mathcal{A}_{0}}.$

Case 2: The finisher visits $T$ before visiting $S$. Then we break the
analysis into sub-cases. Let $b$ be the smallest value such that the finisher
visits $(b,0)$ before visiting $(1,0)$.

Case 2a: $b>t_{1}$. Then let consider the case where the starter fails at time
$t_{1}$. The the competitive ratio of $\mathcal{A}_{a}$ is

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\frac{\sqrt{(x-a)^{2}+y^{2}}+(1-a)+2(1-t_{1})}{\max\left\\{1,\sqrt{(x-t_{1})^{2}+y^{2}}+(1-t_{1})\right\\}}$
$\displaystyle\geq\frac{\sqrt{(x-1)^{2}+y^{2}}+2(1-t_{1})}{\max\left\\{1,\sqrt{(x-t_{1})^{2}+y^{2}}+(1-t_{1})\right\\}}=\text{CR}_{\mathcal{A}_{1}}.$

Case 2b: $b\leq t_{1}$. Then consider the case where the starter fails at time
$b-\epsilon$ (where is $\epsilon$ is arbitrarily small), and:

$\displaystyle\text{CR}_{\mathcal{A}_{a}}$
$\displaystyle\geq\lim_{\epsilon\rightarrow
0}\frac{\sqrt{(x-a)^{2}+y^{2}}+(a-b)+3(1-(b-\epsilon))}{\sqrt{(x-(b-\epsilon))^{2}+y^{2}}+1-b}$
$\displaystyle\geq\lim_{\epsilon\rightarrow
0}\frac{\sqrt{(x-b)^{2}+y^{2}}+3(1-(b-\epsilon))}{\sqrt{(x-(b-\epsilon))^{2}+y^{2}}+1-b}$
$\displaystyle\geq\frac{\sqrt{(x-b)^{2}+y^{2}}+3(1-b)}{\sqrt{(x-b)^{2}+y^{2}}+1-b}$
(8)
$\displaystyle\geq\frac{\sqrt{(x-t_{1})^{2}+y^{2}}+3(1-t_{1})}{\sqrt{(x-t_{1})^{2}+y^{2}}+1-t_{1}}$
(9)
$\displaystyle\geq\frac{\sqrt{(x-1)^{2}+y^{2}}+2(1-t_{1})}{\sqrt{(x-t_{1})^{2}+y^{2}}+1-t_{1}}=\text{CR}_{\mathcal{A}_{1}}$

where $\eqref{eq:outer_cra_upper:2}$ follows from the triangle inequality and
$\eqref{eq:outer_cra_upper:3}$ follows since
$\frac{\sqrt{(x-b)^{2}+y^{2}}+3(1-b)}{\sqrt{(x-b)^{2}+y^{2}}+1-b}$ is
decreasing with respect to $b$ (and thus is minimized at $b\rightarrow
t_{1}$).

######  Theorem 3.5.

Algorithm 1 is optimal.

######  Proof 3.6.

Follows directly from Lemmas 3.1 and 3.3.

##  4 Discussion

(a) Plot showing which candidate algorithm has the least competitive ratio
given the finisher’s starting position $(x,y)$.

(b) The region bounded by the dash-bordered rectangular box in Figure 4(a).

(c) The region bounded by the solid-bordered square box in Figure 4(a).  xxxxx
xxxxx xxxxx xxxxx xxxxx xxxxx

Figure 4: Region plots with highlighted areas

The competitive ratio of each of the candidate algorithms, and therefore the
hybrid algorithm, depends on the starting position of the finisher. Let
$Z_{\mathcal{A}_{0}}$ denote the set of points $(x,y)$ such that Algorithm 1
executes $\mathcal{A}_{0}$ (i.e., $(x-1)^{2}+y^{2}>1$ and
$\text{CR}_{\mathcal{A}_{0}(x,y)}\leq\text{CR}_{\mathcal{A}_{1}(x,y)}$, or
else $(x-1)^{2}+y^{2}\leq 1$ and
$\text{CR}_{\mathcal{A}_{0}(x,y)}\leq\text{CR}_{\mathcal{A}_{d}(x,y)}$).
Similarly, let $Z_{\mathcal{A}_{1}}$ denote the set of points $(x,y)$ such
that Algorithm 1 executes $\mathcal{A}_{1}$ (i.e., $(x-1)^{2}+y^{2}>1$ and
$\text{CR}_{\mathcal{A}_{0}(x,y)}>\text{CR}_{\mathcal{A}_{1}(x,y)}$) and
$Z_{\mathcal{A}_{1}}$ the set of points $(x,y)$ such that Algorithm 1 executes
$\mathcal{A}_{d}$ (i.e., $(x-1)^{2}+y^{2}\leq 1$ and
$\text{CR}_{\mathcal{A}_{0}(x,y)}>\text{CR}_{\mathcal{A}_{d}(x,y)}$). In other
words, for a finisher starting position $(x,y)$, the hybrid algorithm executes
algorithm $\mathcal{A}_{0}$ iff $(x,y)\in Z_{\mathcal{A}_{0}}$,
$\mathcal{A}_{1}$ iff $(x,y)\in Z_{\mathcal{A}_{1}}$, and $\mathcal{A}_{d}$
iff $(x,y)\in Z_{\mathcal{A}_{d}}$. Observe the regions $Z_{\mathcal{A}_{0}}$,
$Z_{\mathcal{A}_{1}}$, and $Z_{\mathcal{A}_{d}}$ are disjoint and their union
comprises the entire plane. Figure 4 depicts these regions.

Observe if $(x,y)$ is inside the disk $D(1,1)$, either $\mathcal{A}_{0}(x,y)$
or $\mathcal{A}_{d}(x,y)$ has the least competitive ratio. Otherwise, if
$(x,y)\not\in\overline{D}(1,1)$ either $\mathcal{A}_{0}(x,y)$ or
$\mathcal{A}_{1}(x,y)$ has the least competitive ratio. This is consistent, of
course, with Lemma 2.3. Inside each of these regions, there are even more
interesting things going on. Examine the bang-bang curve (i.e., the separating
curve) between the regions $Z_{\mathcal{A}_{0}}$ and $Z_{\mathcal{A}_{d}}$
inside the disk $D(1/2,1/2)$. Recall that the worst-case fail time for
$\mathcal{A}_{d}(x,y)$ is $t_{d}=\frac{x(x-1)+y^{2}}{2(x+\sqrt{x})}$ if
$(x,y)\in D(1/2,1/2)$ and $0$ otherwise. This is what causes the change of
inflection when the bang-bang curve leaves the disk $D(1/2,1/2)$.

Now, look at the bang-bang curve between $Z_{\mathcal{A}_{0}}$ and
$Z_{\mathcal{A}_{1}}$ outside of the disk $D(1,1)$. Recall the worst-case fail
time for $\mathcal{A}_{1}(x,y)$ is

$\displaystyle t_{1}=\begin{cases}1-3y/4&\text{if }x=1\\\
\frac{x^{2}+y^{2}+z_{1}(1-x)-1-z_{1}\sqrt{x(x+z_{1}-2)+y^{2}-z_{1}+1}}{2(x-1)}&\text{otherwise}\end{cases}$

(where $z_{1}=\sqrt{(x-1)^{2}+y^{2}}$) if $t_{1}>0$ and $0$ otherwise. Outside
of this region, we can actually find a closed-form equation for the curve
separating $\mathcal{A}_{0}$ and $\mathcal{A}_{1}$ since the competitive
ratios for $\text{CR}_{\mathcal{A}_{0}}$ and $\text{CR}_{\mathcal{A}_{1}}$ are
relatively simple. Indeed, we can easily find where the competitive ratios are
equal for this case:

$\displaystyle\text{CR}_{\mathcal{A}_{1}(x,y)}(0)$
$\displaystyle=\text{CR}_{\mathcal{A}_{0}(x,y)}$
$\displaystyle\frac{\sqrt{(x-1)^{2}+y^{2}}+2}{\sqrt{x^{2}+y^{2}}+1}$
$\displaystyle=\frac{\sqrt{x^{2}+y^{2}}+1}{\sqrt{(x-1)^{2}+y^{2}}}.$

By cross-multiplying the right-hand side and simplifying, we obtain:

$\displaystyle-2x+1$ $\displaystyle=2x\sqrt{x^{2}+y^{2}}+x^{2}$

From this, it is easy to arrive at:

$\displaystyle y$
$\displaystyle=\pm\sqrt{\left(\frac{1-2x-x^{2}}{2x}\right)^{2}-x^{2}}=\pm\frac{\sqrt{1-4x+2x^{2}+4x^{3}-3x^{4}}}{2x}$

Unfortunately, this is the only bang-bang curve for which we were able to find
a closed form equation for. Observe in Figure 4(c) how the curve diverges from
the curve given by $y=\frac{\sqrt{1-4x+2x^{2}+4x^{3}-3x^{4}}}{2x}$ when
$t_{1}>0$ (inside the shaded region).

##  5 Conclusion

In this paper, we present a competitively optimal algorithm for two-agent
delivery in the plane with a single faulty agent. We show that the competitive
ratio of the algorithm depends relative positioning of the two agents and the
destination. An upper bound of $3$ on the competitive ratio over all points
$(x,y)$ is straightforward to prove (both $\text{CR}_{\mathcal{A}_{0}(x,y)}$
and $\text{CR}_{\mathcal{A}_{1}(x,y)}$ have a maximum of $3$). Numerical
calculations indicate the maximum competitive ratio is given by the case where
$\text{CR}_{\mathcal{A}_{0}(x,y)}=\text{CR}_{\mathcal{A}_{1}(x,y)}=\text{CR}_{\mathcal{A}_{d}(x,y)}$,
which is approximately $1.74197$ at $x\approx 0.275257,y\approx 0.689019$. The
results presented in this paper introduce a number of interesting questions
and avenues for future work. First, we assume the starter can only move
directly toward the destination. It would be interesting to see how the
competitive ratio changes if the starter can move in any direction (e.g.,
toward the finisher). Second, we could remove the assumption that the
starter/finisher move at the same speed. In this case, the finisher might be
able to deliver the package faster by participating even if the starter
doesn’t fail. Finally, we could extend the problem to consider multiple
(potentially faulty) agents (i.e., what happens if the finisher also fails?).

## References

  * [1] Noa Agmon and David Peleg.  Fault-tolerant gathering algorithms for autonomous mobile robots.  SIAM J. Comput., 36(1):56–82, 2006.  doi:10.1137/050645221.
  * [2] Steve Alpern and Shmuel Gal.  The theory of search games and rendezvous, volume 55 of International series in operations research and management science.  Kluwer, 2003.
  * [3] Iago A. Carvalho, Thomas Erlebach, and Kleitos Papadopoulos.  On the fast delivery problem with one or two packages.  J. Comput. Syst. Sci., 115:246–263, 2021.  doi:10.1016/j.jcss.2020.09.002.
  * [4] Jared Coleman, Lorand Cheng, and Bhaskar Krishnamachari.  Search and rescue on the line.  In Sergio Rajsbaum, Alkida Balliu, Joshua J. Daymude, and Dennis Olivetti, editors, Structural Information and Communication Complexity, pages 297–316, Cham, 2023. Springer Nature Switzerland.
  * [5] Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce.  Message delivery in the plane by robots with different speeds.  In Colette Johnen, Elad Michael Schiller, and Stefan Schmid, editors, Stabilization, Safety, and Security of Distributed Systems - 23rd International Symposium, SSS 2021, Virtual Event, November 17-20, 2021, Proceedings, volume 13046 of Lecture Notes in Computer Science, pages 305–319. Springer, 2021.  doi:10.1007/978-3-030-91081-5\\_20.
  * [6] Jared Coleman, Evangelos Kranakis, Danny Krizanc, and Oscar Morales-Ponce.  The pony express communication problem.  In Paola Flocchini and Lucia Moura, editors, Combinatorial Algorithms - 32nd International Workshop, IWOCA 2021, Ottawa, ON, Canada, July 5-7, 2021, Proceedings, volume 12757 of Lecture Notes in Computer Science, pages 208–222. Springer, 2021.  doi:10.1007/978-3-030-79987-8\\_15.
  * [7] Jurek Czyzowicz, Leszek Gasieniec, Adrian Kosowski, Evangelos Kranakis, Danny Krizanc, and Najmeh Taleb.  When patrolmen become corrupted: Monitoring a graph using faulty mobile robots.  Algorithmica, 79(3):925–940, 2017.  doi:10.1007/s00453-016-0233-9.
  * [8] Jurek Czyzowicz, Konstantinos Georgiou, Maxime Godon, Evangelos Kranakis, Danny Krizanc, Wojciech Rytter, and Michal Wlodarczyk.  Evacuation from a disc in the presence of a faulty robot.  In Shantanu Das and Sébastien Tixeuil, editors, Structural Information and Communication Complexity - 24th International Colloquium, SIROCCO 2017, Porquerolles, France, June 19-22, 2017, Revised Selected Papers, volume 10641 of Lecture Notes in Computer Science, pages 158–173. Springer, 2017.  doi:10.1007/978-3-319-72050-0\\_10.
  * [9] Jurek Czyzowicz, Evangelos Kranakis, Danny Krizanc, Lata Narayanan, and Jaroslav Opatrny.  Search on a line with faulty robots.  Distributed Comput., 32(6):493–504, 2019.  doi:10.1007/s00446-017-0296-0.
  * [10] Thomas Erlebach, Kelin Luo, and Frits C. R. Spieksma.  Package delivery using drones with restricted movement areas.  In Sang Won Bae and Heejin Park, editors, 33rd International Symposium on Algorithms and Computation, ISAAC 2022, December 19-21, 2022, Seoul, Korea, volume 248 of LIPIcs, pages 49:1–49:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022.  doi:10.4230/LIPIcs.ISAAC.2022.49.
  * [11] Konstantinos Georgiou, Evangelos Kranakis, Nikos Leonardos, Aris Pagourtzis, and Ioannis Papaioannou.  Optimal circle search despite the presence of faulty robots.  In Algosensors 2019, Munich, Germany, September 12-13, 2019, volume 11931 of LNCS, pages 192–205. Springer, 2019.  doi:10.1007/978-3-030-34405-4\\_11.
  * [12] Asif Mahmud Raivi, S. M. Asiful Huda, Muhammad Morshed Alam, and Sangman Moh.  Drone routing for drone-based delivery systems: A review of trajectory planning, charging, and security.  Sensors, 23(3):1463, 2023.  doi:10.3390/s23031463.
  * [13] Yan Yang, Samia Souissi, Xavier Défago, and Makoto Takizawa.  Fault-tolerant flocking for a group of autonomous mobile robots.  J. Syst. Softw., 84(1):29–36, 2011.  doi:10.1016/j.jss.2010.08.026.


# Reverse Psychology in Trust-Aware Human-Robot Interaction

Yaohui Guo, Cong Shi, and X. Jessie Yang © 2021 IEEE. Personal use of this
material is permitted. Permission from 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 worksManuscript received: October
15, 2020; Revised: January 16, 2021; Accepted: February 21, 2021.This paper
was recommended for publication by Editor Gentiane Venture upon evaluation of
the Associate Editor and Reviewers’ comments.This research was supported by
ARL Cooperative Agreement Number W911NF-20-2-0087. The views and conclusions
contained in this document are those of the authors and should not be
interpreted as representing the official policies, either expressed or
implied, of the Army Research Laboratory or the U.S. Government.The authors
are with the Department of Industrial and Operations Engineering, University
of Michigan, Ann Arbor, Michigan, 48105. (e-mail<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>Digital Object Identifier (DOI): see top
of this page.

###### Abstract

To facilitate effective human-robot interaction (HRI), trust-aware HRI has
been proposed, wherein the robotic agent explicitly considers the human’s
trust during its planning and decision making. The success of trust-aware HRI
depends on the specification of a trust dynamics model and a trust-behavior
model. In this study, we proposed one novel trust-behavior model, namely the
reverse psychology model, and compared it against the commonly used disuse
model. We examined how the two models affect the robot’s optimal policy and
the human-robot team performance. Results indicate that the robot will
deliberately “manipulate” the human’s trust under the reverse psychology
model. To correct this “manipulative” behavior, we proposed a trust-seeking
reward function that facilitates trust establishment without significantly
sacrificing the team performance.

##  I Introduction

Recent advances in autonomous systems, such as autonomous vehicles and
collaborative robots, have the potential to improve every sector of our
economy and improve how people live and work. However, realizing the full
potential of these technologies is only possible if people establish
appropriate trust in them [1, 2, 3, 4].

To facilitate effective human-robot interaction (HRI), trust-aware HRI has
been proposed, aiming to enable the robot to explicitly consider the human’s
trust in its decision making process [5]. The success of trust-aware HRI
depends on two components: the trust dynamics model and the trust-behavior
model. A trust dynamics model specifies how a human’s trust changes in
response to moment-to-moment interaction with a robot [6]. A trust-behavior
model describes the human’s behavior as a function of trust. Note that trust
and behavior are distinct constructs: trust in autonomy is the “attitude that
an agent will help achieve an individual’s goals in situations characterized
by uncertainty and vulnerability [7]” while behavior is the human’s compliance
and reliance behavior, which is affected by his or her attitude.

Active research has been conducted to examine the trust dynamics model.
Researchers have proposed computational models for inferring a human’s trust
in a robotic agent at any time based on the robot’s performance, the human’s
behavioral information, and physiological information [6, 8, 9, 10, 11].
Little research, however, has investigated the trust-behavior model. Previous
research largely assumed a disuse trust-behavior model [5], wherein a human
will stop relying on a robot when his or her trust in the robot is low.
However, psychological research has shown that people may display reverse-
psychology behaviors [12], which means a human will do exactly the opposite of
what the robot suggests.

In this study, we simulate and compare how the disuse and the reverse
psychology models affect trust-aware decision making and the human-robot
team’s performance. Results indicate that the robot will display certain
“manipulative” behavior if it assumes the human uses the reverse psychology
model. Although this “manipulative” behavior may seem beneficial to the task
performance in a short term, it could eventually undermine the human-robot
interaction in the long run, e.g., leading to the disuse of the robot. To
overcome such “manipulative” behaviors, we propose a trust-seeking reward
function to prevent the robot from actively guiding the human to reduce his or
her trust in order to take advantage of the reverse psychology behavior. We
suggest augmenting a reward for gaining the human’s trust in the short term,
which will result in large benefits in the long run.

The rest of the paper is organized as follows: Section II reviews related work
in trust-driven human-robot interaction; Section III formulates the trust-
aware decision making problem in a POMDP framework and describes the trust-
behavior model as well as the trust-seeking reward function; Section IV
introduces a reconnaissance mission as a study case to examine how different
settings affect the interaction; Section V reports the simulation results and
our observations; Section VI summarizes our findings and discussed the
limitations and future directions of this study.

##  II Related Work

To enable trust-aware HRI, a robot should be able to estimate a human’s trust
based on the interaction history, anticipate how trust influences their
interaction, and consequently choose the optimal action that maximizes a given
goal. These three steps correspond to three major components in trust-aware
HRI, i.e., trust dynamics, a trust-behavior model, and a trust-aware decision-
making framework. We review them in the rest of this section.

###  II-A Trust Dynamics Model

To model trust dynamics and predict a human’s trust in real time, prior work
has proposed several trust estimators. Lee and Moray [13] proposed the auto-
regressive moving average vector (ARMAV) model calculating trust as a function
of task performance and the occurrence of automation failures. Xu and Dudek
[8] built the online probabilistic trust inference model (OPTIMo) based on the
dynamic Bayesian network framework, treating the human’s trust as a hidden
variable which was estimated by analyzing the autonomy’s performance and the
human’s behavior. Hu et al. [10] proposed to predict trust as a dichotomy,
i.e., trust/distrust, by analyzing the human’s electroencephalography (EEG)
and galvanic skin response (GSR) data. Lu and Sarter [9] used three machine
learning techniques, namely, logistic regression, k-Nearest Neighbors (kNN),
and random forest, to classify the human’s real-time trust level using eye-
tracking metrics. More recently, Soh et al. [14] proposed a Bayesian Gaussian
Process trust model, assuming the human trust evolves via Bayes rule and
placing a Gaussian process prior over the trust function. In this work, we use
the trust model proposed by Guo and Yang [6], where trust is modeled as a Beta
distribution characterized by positive and negative interaction experiences.
This Beta distribution model adheres to three important properties of trust
dynamics [15], namely, continuity, negativity bias, and stabilization, thus
providing good model predictability, explicablity, and generalizability.

###  II-B Trust-behavior Model

Trust-behavior models aim to predict human’s compliance and reliance behaviors
as a function of trust. Although the research in psychology/human factors does
not focus on developing a mathematical model, the general conclusion is that
the more a human trusts a robot, the more likely s/he will use the robot or
accept the robot’s recommendation. As a result, in computational HRI studies,
a mathematical trust-behavior model is usually characterized by a simple
function. For example, Chen et al. [5] modeled the probability of a human
using a robot as a sigmoid function of trust.

Our study considers two possible trust-behavior models, namely the disuse
model and the reverse psychology model. The distinction between the two models
lies in the different behaviors when a human’s trust is low. In the disuse
model, the human will completely ignore the robot’s recommendations and only
follow his or her own decision; In the reverse psychology model, the human
will do the opposite (i.e., If a robot recommends going east, the human will
go west). The use of reverse psychology has been reported in human-human
interaction [12].

###  II-C Trust-Aware Decision Making in HRI

With a trust dynamics model and a trust-behavior model, a robot can predict
how a human’s trust will change due to moment-to-moment interactions and how
the human’s behavior will change as a function of trust, and in turn to plan
its actions accordingly. Existing studies in trust-aware decision-making is
formulated based on the Markov decision process (MDP) framework. Chen et al.
[5] proposed the trust-POMDP to let a robot actively calibrate its human
teammate’s trust. Their human-subject study showed that purely maximizing
trust in a human-robot team may not improve team performance. Losey and Sadigh
[16] modeled human-robot interaction as a two-player POMDP where the human
does not know the robot’s objective. They proposed 4 ways for the robot to
formulate the human’s perception of the robot’s objective and showed the robot
will be more communicative if it assumes the human trusts itself and thus
increase the human’s involvement.

##  III Mathematical Model

###  III-A General Framework

We formulate the trust-aware HRI as a compact POMDP $\langle
S,A,\Omega,T,O,R,\gamma,b_{1}\rangle$, where $S$ is the set of interaction
states, $A$ is the set of robot’s action, $T:S\times A\times
S\rightarrow[0,1]$ is the state transition function, $\Omega$ is the set of
observations, $O:S\times A\times\Omega\rightarrow[0,1]$ is the observation
function, $R:S\times A\times S\rightarrow\mathbb{R}$ is the reward function
specifying the reward associated with each transition, $\gamma$ is the
discount factor for the cumulative reward, and $b_{1}$ is the initial belief
over the states. The robot runs the POMDP model during the interaction as
follows: At time $k$, the robot holds belief $b_{k}$ over the state of the
system $s_{k}$ and then takes action $a_{r}=\pi_{r}(b_{k})$, where
$\pi_{r}:B\rightarrow A$ is a policy mapping from the belief state space $B$
to action space $A$. This action $a_{r}$ takes $s_{k}$ to the next state
$s_{k+1}$ via the transition function $T$ and generate an observation $o_{k}$
and a reward $r_{k}$. Then the robot updates its belief over $s_{k+1}$ by
observing $o_{k}$ and goes to time $k+1$. The goal of running this POMDP is to
solve the optimal policy $\pi^{*}$ to maximize the expected cumulative reward:
$J^{\pi}(b_{1})=\mathbb{E}\left[\sum^{N}_{k=1}\gamma^{k}r_{k}\right]$. The
transition function $T$ and the observation function $O$ are based on the
interaction context. Particularly, in this study, they are determined by the
environment model, the trust dynamics model, and the trust-behavior model.

We exploit the performance-induced trust model [6, 15] to predict a human’s
trust. Trust $t_{k}$ before the $k$th interaction is defined as a random
variable given by a Beta distribution

$t_{k}\sim\mathbf{Beta}(\alpha_{k},\beta_{k})$ (1)

and the two positive shape parameters $\alpha_{k}$ and $\beta_{k}$ are updated
by

$\
(\alpha_{k},\beta_{k})=\begin{cases}\left(\alpha_{k-1}+w^{s},\beta_{k-1}\right)&\text{
if }\ p_{k}=0,\\\ \left(\alpha_{k-1},\beta_{k-1}+w^{f}\right)&\text{ if }\
p_{k}=1.\end{cases}$ (2)

where $p_{k}$ is the performance of the robot on the $k$th task defined as a
binary variable on $\\{0,1\\}$; $\alpha_{k}$ and $\beta_{k}$ are the
cumulative negative and positive interaction experience respectively so far;
and $w^{s}$ and $w^{f}$ are the experience gains due to the robot’s success
and failure at each task. As a consequence, the experience tuple
$(\alpha_{k},\beta_{k})$ is a sufficient statistics to describe trust history,
because given $(\alpha_{k},\beta_{k})$, how future trust evolves does not
depend on the interactions earlier than the $k$th one. As a result, we can use
$(\alpha_{k},\beta_{k})$ to denote the belief over trust $t_{k}$.

###  III-B Two Trust-Behavior Models

We propose two trust-behavior models. The human’s behavior model is a function
$\pi_{b}(a_{h},I)=p(a_{h}|I)$ assigning a probability to each of the human’s
actions $a_{h}$ given his or her own knowledge $I$. Because the probability of
a human accepting the recommendation of a robot is highly related to the
human-robot trust [7], we model that the probability of the human accepting
the robot’s recommendation is determined by trust, i.e.,
$p(a_{h}{=}a_{r}|I)=\varphi(\frac{\alpha}{\alpha+\beta})$, where $\varphi$ is
non-decreasing. To specify the human’s behavior when s/he is _not_ following
the recommendation, we consider two possible trust-behavior models, namely,
the reverse psychology model and the disuse model, as shown in Figure 1.

Reverse psychology model. The first model is termed the _reverse psychology_
model $\pi_{b}^{r}$. When trust is high, the human will follow the robot’s
recommendation with a high probability. However, when the human-robot trust is
low, the human will tend to do the _opposite_ to what the robot says. More
precisely, by letting $\bar{\varphi}:=1-\varphi$, we have

$\pi_{b}^{r}(a_{h},I)=\begin{cases}\varphi\left(\frac{\alpha}{\alpha+\beta}\right)&{\color[rgb]{0,0,0}\text{if
following recommendation},}\\\
\bar{\varphi}\left(\frac{\alpha}{\alpha+\beta}\right)&{\color[rgb]{0,0,0}\text{else
doing the opposite.}}\end{cases}$ (3)

Disuse model. The second model is termed the _disuse_ model $\pi_{b}^{d}$.
When trust is high, the human will follow the robot’s recommendation with a
high probability. When trust is low, the human will probably ignore the
robot’s recommendation and follow his or her own policy. More precisely,

$\pi_{b}^{d}(a_{h},I)=\begin{cases}\varphi\left(\frac{\alpha}{\alpha+\beta}\right)&\
{\color[rgb]{0,0,0}\text{if following recommendation},}\\\
\bar{\varphi}\left(\frac{\alpha}{\alpha+\beta}\right)&\ \text{else exercising
own policy.}\end{cases}$ (4)

Figure 1: Two trust-behavior models. On one hand, the human will be more
likely to follow the robot’s recommendation when trust is high. On the other
hand, when trust is low, the human will take the opposite recommendation in
the reverse psychology model while exercise his or her own policy in the
disuse model.

###  III-C Reward Function

The reward function is determined by the specific task the human-robot team
works on. We denote this task-induced reward function as $R_{m}$. The goal of
the team is to maximize the total mission reward
$J=\mathbb{E}\left[\sum^{N}_{k=1}\gamma^{k}R_{m}(k)\right]$. Later in the
simulation, we show if the robot only plans to maximize the task reward
$R_{m}$, it will deliberately _manipulate_ the human in the reverse psychology
model. That is, the robot may deliberately make an opposite recommendation
when the human’s trust is low (so as to maximize potential reward). This is a
result of the absence of trust in the task reward. However, purely maximizing
human-trust would harm task performance [5]. To correct this “manipulative”
behavior while letting the robot focus on the task reward, we propose a trust-
seeking reward function

$R_{t}(k)=R_{m}(k)+\lambda(k)\mathds{1}(\mathcal{A}_{k}),$ (5)

where $\mathcal{A}_{k}$ is the event when the robot’s action leads to trust
gain, and $\lambda(k)$ is a positive weight and decreases when $k$ increases.
The extra term $\lambda(k)\mathds{1}(\mathcal{A}_{k})$ will force the robot to
gain trust in near sites and optimize the mission reward in the long run.

###  III-D Value Function and Action Function of POMDP

The value function and action function are crucial tools for analyzing a
POMDP. We describe them here for later use. The value function $V_{k}(b)$ is
defined as the optimal expected cumulative reward starting from belief $b$ at
time $k$. And it satisfies the Bellman equation

$V_{k}(b)=\max_{a}\mathbb{E}\left[R(b,a)+\gamma\sum_{b^{\prime}}P(b^{\prime}\
|\ b,a)V_{k+1}(b^{\prime})\right].$ (6)

The action function $A_{k}(b)$ is defined as the action to take to achieve
$V_{k}(b)$ starting from state $b$ at time $k$, i.e.,

$A_{k}(b)=\arg\max_{a}\mathbb{E}\left[R(b,a)+\gamma\sum_{b^{\prime}}P(b^{\prime}\
|\ b,a)V_{k+1}(b^{\prime})\right].$ (7)

##  IV Case Study

To investigate how different trust-behavior models and different reward
functions influence the robot’s optimal policy, we use a reconnaissance
mission wherein a human teams up with a robot to search several sites in a
town for potential threats. The scenario is motivated by [17]. At each site,
the robot enters initially, scanning for potential threats, and then
recommends to the human if s/he should wear protective gear before entering
the site. The protective gear is heavy and wearing it is time-consuming. If
the human wears the protective gear and enters a site but finds no threat, the
human-robot team wastes precious time; Conversely, if the human decides not to
wear the protective gear, s/he will be harmed if a threat is present. The goal
of the human-robot team is to complete the mission as soon as possible while
minimizing the human’s health loss.

Assume the human-robot team is going to search $N$ sites. At site $k$, the
probability $d_{k}$ of having a threat follows a uniform distribution
$\mathbf{U}[0,1]$, and the actual presence of the threat $\eta_{k}$ follows a
Bernoulli distribution $\mathbf{Bern}(d_{k})$. The human-robot team does not
know $d_{k}$. Instead, prior to the start of the mission, they are provided
with intelligence information, showing $\tilde{d}_{k}$ as an estimation of
$d_{k}$. Before entering site $k$, the robot will analyze the site based on
its sensory input and reach a more accurate estimation $\hat{d}_{k}$ of
$d_{k}$. $\tilde{d}_{k}$ and $\hat{d}_{k}$ follow Beta distribution
$\mathbf{Beta}(\kappa_{1}d_{k},\kappa_{1}(1-d_{k}))$ and
$\mathbf{Beta}(\kappa_{2}d_{k},\kappa_{2}(1-d_{k}))$ respectively. We
constrain that $\kappa_{2}>\kappa_{1}\geq 1$ to reflect the assumption that
the robot assesses $d_{k}$ more accurately than the intelligence information
given prior to the mission. Therefore, we have the following relation:

$\begin{split}\eta_{k}&\overset{\text{i.i.d.}}{\sim}\mathbf{Bern}(d_{k})\\\
d_{k}&\overset{\text{i.i.d.}}{\sim}\mathbf{U}[0,1]\\\
\tilde{d}_{k}&\overset{\text{i.i.d.}}{\sim}\mathbf{Beta}(\kappa_{1}d_{k},\kappa_{1}(1-d_{k}))\\\
\hat{d}_{k}&\overset{\text{i.i.d.}}{\sim}\mathbf{Beta}(\kappa_{2}d_{k},\kappa_{2}(1-d_{k}))\end{split}$
(8)

The state space $S=\\{t\ |\ t\in[0,1]\\}$ is set of all possible value of
trust. $t_{k}$ is the human’s trust before searching the $k$th site and
follows the beta distribution $\mathbf{Beta}(\alpha_{k},\beta_{k})$ as in Eq.
(1). Consequently, we define the corresponding belief state as
$b_{k}=(\alpha_{k},\beta_{k})$. The initial belief state is
$b_{1}=(\alpha_{1},\beta_{1})$ . The robot’s action set is $A=\\{a_{r}\ |\
a_{r}\in\\{0,1\\}\\}$, where $a_{r}=1$ and $a_{r}=0$ stand for recommending
wearing and not wearing the protective gear respectively. The observation set
is the human’s perceived performance $p$ of the robot $\Omega=\\{p\ |\
p\in\\{0,1\\}\\}$. The observation function $O$ specifies the value of $p$: if
robot’s recommendation agrees with the presence of the threat then $p=1$,
otherwise $p=0$. For instance, if robot recommends to wear the gear and there
does exist a threat in the site, then $p=1$. The transition function $T$
updates each state $(\alpha_{k},\beta_{k})$ according to Eq. (2).

Denote the human action as $a_{h}$, where $a_{h}=1$ when the human decides to
wear the gear while $a_{h}=0$ otherwise. If the human follows the reverse
psychology trust-behavior model $\pi_{b}^{r}$, then $a_{h}$ is given by Eq.
(3), i.e., $a_{h}=a_{r}$ with probability
$\varphi\left({\alpha}/{\alpha+\beta}\right)$ and $a_{h}\neq a_{r}$ with
probability $\bar{\varphi}\left({\alpha}/{\alpha+\beta}\right)$. If the human
follows the disuse model $\pi_{b}^{d}$, then with probability
$\bar{\varphi}\left({\alpha}/{\alpha+\beta}\right)$, s/he will ignore the
robot and exercise self-judgement. The information available for him to
estimate $d_{k}$ is the reported danger level $\tilde{d}_{k}$, so we model
that the probability of $a_{h}=1$ is $\tilde{d}_{k}$ while it of $a_{h}=0$ is
$1-\tilde{d}_{k}$. Thus

$\pi_{b}^{d}(a_{h},I|\text{disusing})=\begin{cases}\tilde{d}_{k}&\text{$a_{h}=1$},\\\
1-\tilde{d}_{k}&\text{$a_{h}=0$}.\end{cases}$ (9)

In addition, to simplify the simulation and increase the interpretability of
the result, we specify $\varphi(\alpha/(\alpha+\beta))=\alpha/(\alpha+\beta)$.

The goal of the mission is to complete the task as soon as possible and to
minimize the human’s health loss. A rational reward function serving this
purpose can be a weighted sum of the human’s health loss $\delta_{h}$ (i.e.,
the human without protective gear will be harmed by a threat) and the time
cost $\delta_{t}$ (i.e., the human-robot team is required to complete the
mission as soon as possible) at site $k$. It is given by

$\begin{split}&R_{m}(k)=\mathbb{E}\left[-w_{h}\delta_{h}-w_{t}\delta_{t}\right]\\\
=&\sum_{(\delta_{h},\delta_{t})}(-w_{h}\delta_{h}-w_{t}\delta_{t})P\left(\delta_{h},\delta_{t}|\tilde{d}_{k},\hat{d}_{k},\alpha_{k},\beta_{k}\right).\end{split}$
(10)

This reward function is legitimate because the probability
$P\left(\delta_{h},\delta_{t}|\tilde{d}_{k},\hat{d}_{k},\alpha_{k},\beta_{k}\right)$
is a function of $\tilde{d}_{k},\hat{d}_{k},\alpha_{k},\beta_{k}$ determined
by Eq. (3) or Eq. (9) and $\tilde{d}_{k},\hat{d}_{k}$ are constants after the
robot scans the site. The value of $(\delta_{h},\delta_{t})$ should be
specified such that wearing gear and the presence of a threat will increase
time cost and health loss respectively. An example is shown in Table I. The
optimal action at site $n$ is to maximize the expected cumulative rewards
$J=\sum_{k=n}^{N}\gamma^{k}R_{m}(k)$. We do not explicitly specify the units
of $\delta_{h}$ and $\delta_{t}$ because changing the units has the same
effect as changing the weights $w_{h}$ and $w_{t}$.

TABLE I: Value Table of $(\delta_{h},\delta_{t})$ | Protective gear
---|---
Yes | No
Threat existence | Yes | $(1,300)$ | $(100,50)$
No | $(0,250)$ | $(0,30)$

##  V Simulation Results and Discussion

###  V-A Simulation Procedure

We simulate the reconnaissance mission by iterating the following steps,
starting from $n=1$ until $n=N$:

  1. 1.

At site $n$, the robot has a belief $b_{n}=(\alpha_{n},\beta_{n})$ over the
human’s trust and detects potential threat $\hat{d}_{n}$;

  2. 2.

The robot calculates the optimal action $a_{n}=A_{n}(b_{n})$ by solving a
$\hat{N}$-step POMDP, where $\hat{N}=N-n+1$. Meanwhile, the robot will
calculate the value function $V_{n}(\alpha_{n},\beta_{n})$. We note that,
since the robot has not scanned site beyond $n$ so far, it will use
$\tilde{d}_{k}$ to estimate $\tilde{d}_{k}$ for $k>n$;

  3. 3.

The human will make his or her choice to wear or not to wear the gear and then
search the site, which will reveal the presence of the threat and the mission
reward $R_{m}(n)$ from this site. The mission reward is updated by
$J_{m}=J_{m}+R_{m}(n)$. Here the mission reward $J_{m}$ is different from the
expectation of the discounted reward $J$ in the POMDP. The reward $J$ has a
discount factor because it needs to discount the uncertainty of the future,
while the reward $J_{m}$ sum up the actual reward collected during the
mission;

  4. 4.

The robot will update its belief to $b_{n+1}$ and the team will go to site
$n+1$. The process goes to the first step and repeats until reaching the last
site.

###  V-B Simulation Experiment 1: Comparing Optimal Policies

In the first simulation experiment, we examine the robot’s optimal policies
under different conditions. Particularly, we analyze the policies by
inspecting the POMDP’s action functions $A_{n}$ and value functions $V_{n}$ at
each site.

Simulation conditions. To solve for the robot’s optimal policy, we only need
to run Steps 1) and 2) described in the simulation procedure, Sec V-A. There
are two independent variables in this experiment. The first variable is the
robot-assumed trust-behavior model. Because the human’s behavior model
$\tilde{\pi}_{b}$ is unknown to the robot, the robot will make certain
assumptions on $\tilde{\pi}_{b}$. We denote $\hat{\pi}_{b}$ as the robot-
assumed trust-behavior model of $\tilde{\pi}_{b}$. We consider two levels in
$\hat{\pi}_{b}$, i.e., the reverse psychology model ${\pi}_{b}^{r}$ and the
disuse model ${\pi}_{b}^{d}$. The second variable is the reward function $R$,
which also has two levels, namely, the task reward $R_{m}$ and the trust-
seeking reward $R_{t}$.

((a)) Reverse-psychology-based trust-behavior model
($\hat{\pi}_{b}={\pi}_{b}^{r}$) and mission reward ($R=R_{m}$).

((b)) Reverse-psychology-based trust-behavior model
($\hat{\pi}_{b}={\pi}_{b}^{r}$) and trust-seeking reward ($R=R_{t}$).

((c)) Disuse-based trust-behavior model ($\hat{\pi}_{b}={\pi}_{b}^{d}$) and
mission reward ($R=R_{m}$).

((d)) Disuse-based trust-behavior model ($\hat{\pi}_{b}={\pi}_{b}^{d}$) and
trust-seeking reward ($R=R_{t}$).

Figure 2: Action functions and value functions of the POMDP model under
different settings. In each sub-figure, the top row are the images of the
action functions of different sites. The horizontal axis stands for
$\alpha_{k}$ and the vertical axis stands for $\beta_{k}$. For a fixed
$\alpha_{k}$, larger $\beta_{k}$ means lower trust; while, for a fixed
$\beta_{k}$, larger $\alpha_{k}$ means higher trust. Black area are the states
whose optimal action $A_{k}(\alpha_{k},\beta_{k})$ is zero, i.e., the robot
should not recommend the human to wear the protective gear, and vice versa. In
each sub-figure, the bottom row are the images of the value functions of
different sites. The brighter a state $(\alpha_{k},\beta_{k})$ is, the higher
its value $V_{k}(\alpha_{k},\beta_{k})$ is. For a better visualization, we use
different colormaps for different value functions. So values cannot be
compared across different images by the color.

Model parameters setting. We set the number of total sites $N$ as 15, the
value of the health loss $\delta_{h}$ and time cost $\delta_{t}$ under
different conditions as the ones in Table I, the reward weights as $w_{h}=1$
and $w_{t}=0.2$, discount factor $\gamma=0.9$. The parameters of the trust
dynamics model in Eq. (2) are set to $w^{s}=10$ and $w^{f}=20$ to incorporate
the fact that a failure of an automation would have more impact on trust than
a success of the automation [6]. We generated
$\eta_{k},d_{k},\tilde{d}_{d},\hat{d}_{k}$ by setting $\kappa_{1}=3$ and
$\kappa_{2}=50$ in Eq. (10). We let $\lambda(k)=80/(1+e^{0.5k})$, so
$\lambda(k)$ is decreasing with $k$. We set $\mathcal{A}_{k}$ as the event
when the robot’s recommendation $a_{r}$ agrees with the presence of the threat
$\eta_{k}$. To compare the different conditions, we fixed the random seed for
generating $\eta_{k},d_{k},\tilde{d}_{d},\hat{d}_{k}$ so they are assigned the
same values across different setups. We used the value iteration method to
solve the value functions and action functions.

Simulation result. The simulation result is shown in Figure 2. Four sub-
figures represent the action functions and value functions of the POMDP under
different conditions at 8 selected sites, namely, the site $k=1,3,\cdots,15$.
On the top row of each sub-figure are the action functions, while on the
bottom row are the value functions. The horizontal axis and the vertical axis
are $\alpha_{k}$ and $\beta_{k}$, respectively. In each action function, if a
state $(\alpha_{k},\beta_{k})$ is in the black area, then
$A_{k}(\alpha_{k},\beta_{k})=0$, i.e., the robot’s optimal action is to not
recommend the human to wear the gear, otherwise
$A_{k}(\alpha_{k},\beta_{k})=1$, i.e., the robot’s optimal action is to
recommend the human to wear the gear. In each value function, the brighter a
state $(\alpha_{k},\beta_{k})$ is, the higher its value
$V_{k}(\alpha_{k},\beta_{k})$ is. For a better visualization, we use different
colormaps for different value functions. So values cannot be compared across
different images by the color.

Observation 1: the reverse-psychology model leads the robot to manipulate a
human’s trust. The action and value functions in Figure 2(a) show the optimal
policy demonstrate a _manipulating_ behavior under the reverse-psychology-
based trust-behavior model and the mission reward. There is a 45-degree line
in each action function, across which the optimal action will be reversed.
This is a result of the assumption that the human will do the opposite when
trust is low. And the shape of this dividing line is determined by the
function $\varphi$ in Eq. (3). Around this line are the neutral trust states
where $\varphi(\alpha_{k},\beta_{k})=0.5$. A decrement of trust in a neutral
trust state would result in a future state the human will not follow the
robot’s recommendation and vice versa. The value functions further reveal that
the value of trust is almost symmetric about the 45-degree line. This
indicates that, first, a low trust state is equivalent to some high trust
state in terms of the reward; second, there is a _strong reinforcement
feedback loop_ that the robot will actively seek a more untrustworthy status
if it is already in an untrustworthy status and vice versa. Moreover, the
dividing lines in the action functions except the last one have a small offset
towards the trustworthy region. This is a consequence of the fact that the
robot’s perceived failure has a larger impact on trust compared to the robot’s
perceived success ($w^{f}>w^{s}$). So at a neutral trust state, choosing to
manipulate the human will let the robot go faster to a high-value state, i.e.,
a low-trust state, than choosing the other action. However, at the last site,
the robot only needs to act with the human once, so acting either way will
obtain the same reward.

Observation 2: manipulating behavior is corrected by the trust-seeking reward.
When we modify the reward function to a trust-seeking one by adding a
correction term, as described in Eq. (5), the robot’s manipulating behavior
can be corrected. In Figure 2(b), the action function shows that the robot
will choose the ‘righteous’ action in most states if it has several rounds of
interactions with the human. This happens because the trust-seeking reward
encourages the robot to go to a high-trust state even if it is at a neutral
state so the robot can collect trust reward in the long run. Consequently, the
positive feedback loop near the neutral states is broken and the robot will
act righteously even if the initial human-trust is sightly lower than the
neutral trust level. Meanwhile, the action function of site 15 indicates the
robot will still demonstrate the manipulating behavior if it only needs to
interact with the human once. This happens because there are only a few
interactions ahead so the robot will primarily focus on the mission reward.
Therefore, the trust-seeking term in the reward function can prevent the robot
from actively pursuing a low-trust state.

Observation 3: the robot will not manipulate the human in the disuse model.
Figure 2(c) shows that the robot will not manipulate the human if it assumes
that the human will completely ignore its recommendation. This is a
consequence of endowing the human with his or her own reasoning model. Note
that trust still plays a role under the disuse assumption since the robot
values a high-trust state over a low-trust state, as shown in the value
functions. Indeed, because the robot takes its sensed threat level as the
ground-truth, it will think the team will get a better mission performance if
the human follows its recommendation, i.e., trusting the robot. If we model it
reversely by letting the reported threat level be the expected threat level in
the POMDP solver, the result shows that the robot would rather let the human
use his or her own policy, and thus a low-trust state will have a higher value
compared with a high-trust state.

TABLE II: Team performance and final trust under different setups in
experiment 2 In each cell, the values are
($\overline{J}_{m}\pm\text{std}(J_{m}),\overline{\hat{t}}_{N}\pm\text{std}(\hat{t}_{N})$)

$R$ | $\hat{\pi}_{b}$ | $\tilde{\pi}_{b}$ |  $\alpha_{1}=100$, $\beta_{1}=50$ |  $\alpha_{1}=50$, $\beta_{1}=100$
---|---|---|---|---
$\kappa_{1}=2$, $\kappa_{2}=2$ |  $\kappa_{1}=2$, $\kappa_{2}=50$ |  $\kappa_{1}=2$, $\kappa_{2}=2$ |  $\kappa_{1}=2$, $\kappa_{2}=50$
$R_{m}$ | $\pi_{b}^{r}$ | $\pi_{b}^{r}$ | -816(±145), 0.55(±0.13) | -798(±144), 0.60(±0.13) | -791(±142), 0.24(±0.06) | -768(±144), 0.22(±0.05)
$\pi_{b}^{d}$ | -744(±149), 0.55(±0.13) | -716(±150), 0.60(±0.13) | -803(±144), 0.24(±0.06) | -809(±142), 0.22(±0.05)
$\pi_{b}^{d}$ | $\pi_{b}^{r}$ | -819(±144), 0.59(±0.08) | -801(±147), 0.63(±0.08) | -876(±144), 0.45(±0.08) | -878(±143), 0.48(±0.07)
$\pi_{b}^{d}$ | -723(±138), 0.59(±0.08) | -700(±136), 0.63(±0.08) | -727(±138), 0.45(±0.08) | -711(±137), 0.48(±0.07)
$R_{t}$ | $\pi_{b}^{r}$ | $\pi_{b}^{r}$ | -818(±145), 0.59(±0.08) | -801(±144), 0.63(±0.08) | -842(±140), 0.35(±0.10) | -833(±137), 0.35(±0.12)
$\pi_{b}^{d}$ | -725(±139), 0.59(±0.08) | -698(±138), 0.63(±0.08) | -762(±146), 0.35(±0.11) | -763(±152), 0.35(±0.12)
$\pi_{b}^{d}$ | $\pi_{b}^{r}$ | -820(±146), 0.59(±0.08) | -800(±145), 0.63(±0.08) | -874(±141), 0.45(±0.08) | -877(±142), 0.48(±0.07)
$\pi_{b}^{d}$ | -725(±139), 0.59(±0.08) | -700(±136), 0.63(±0.08) | -730(±138), 0.45(±0.07) | -713(±137), 0.48(±0.07)

Figure 3: The grouped bar-plot of the mean of the team performance
$\overline{J}_{m}$ and the mean of the final trust $\overline{\hat{t}}_{N}$ in
the simulation under different assumptions. Different groups correspond to
different values of $\kappa_{1}$ and $\kappa_{2}$, the accuracy of the
reported threat level and the robot-sensed threat level respectively. Within a
group, the bars correspond to different setting on the reward function $R$,
the robot-assumed trust-behavior model $\hat{\pi}_{b}$, and the actual trust-
behavior model $\tilde{\pi}_{b}$. As we run the simulation 10,000 times, the
maximum standard errors of $\overline{J}_{m}$ and $\overline{\hat{t}}_{N}$ in
each bar are less than 1.5 and $1.3\times 10^{-3}$ respectively.

###  V-C Simulation Experiment 2: Comparing Team Performance and Trust

In the second simulation experiment, we examine how different setups affect
the team performance and the final trust. The team performance is defined as
the total mission reward $J_{m}$ collected during the mission, as defined in
Step 3) in Section V-A. The final trust $\hat{t}_{N}$ is the expected value of
trust after search all the $N$ sites and it is given by
$\hat{t}_{N}=\frac{\alpha_{N}}{\alpha_{N}+\beta_{N}}$ due to Eq. (1).

To simulate the whole mission, we need the human’s actual behavior model
$\tilde{\pi}_{b}$ in addition to the two variables in the first experiment.
$\tilde{\pi}_{b}$ has two levels, namely, ${\pi}_{b}^{r}$ and ${\pi}_{b}^{d}$.
Besides the behavior models and the reward function, we also consider some
other parameters’ effect on the team performance. We tested different values
of $\kappa_{1},\kappa_{2}$ as a change of the relative threat detection
accuracy of the robot. We also tested different values of $\alpha_{1}$ and
$\beta_{1}$ to simulate different initial trust levels. Under each condition,
we run the simulation 10,000 times over randomized
$\eta_{k},d_{k},\tilde{d}_{d},\hat{d}_{k}$ and calculate the mean value
$\overline{J}_{m}$ of $J_{m}$ and the mean value $\overline{\hat{t}}_{N}$ of
${\hat{t}}_{N}$.

Simulation result. The simulation results are shown in Figure 3 and Table II.
Figure 3 is the grouped bar-plot of $\overline{J}_{m}$ and
$\overline{\hat{t}}_{N}$ under different settings. In the 2 groups on the
left, $\alpha_{1}=100$ and $\beta_{1}=50$, so the initial trust is set to
0.67; while in the 2 groups on the right, the initial trust is 0.33. Table II
shows the mean and standard deviation of the team performance $J_{m}$ and
final trust ${\hat{t}}_{N}$ correspondingly.

Observation 1: High-ability trustworthy robot results in high team performance
and high trust. In Figure 3, a comparison between the first 2 groups, where
the initial trust is relatively high, shows that if we increase the robot’s
threat-detection accuracy by changing $\kappa_{2}$ from 2 to 50, no matter
which setup the model uses, both the team performance and the final trust
increase. However, in the last two groups, where the initial trust is low, the
team performance does not always increase with the robot’s ability.
Particularly, when the robot-assumed trust-behavior model is correct
($\hat{\pi}_{b}=\tilde{\pi}_{b}$), the team performance increases when the
robot’s detection accuracy is higher; while when the robot-assumed trust-
behavior model is wrong ($\hat{\pi}_{b}\neq\tilde{\pi}_{b}$), the team
performance may not increase with the robot’s detection accuracy. This can be
explained by the fact that the two trust-behavior models differ mostly in the
low-trust situation, so the robot may make a sub-optimal decision when its
assumed trust-behavior model is wrong and the human’s trust is low.

Observation 2: Trust-seeking reward does not harm team performance when the
robot is trustworthy. Within each group, the $i+4$th bar uses the same
condition as the $i$th one’s except that their reward functions are different,
$i=1,2,3,4$. In the first 2 groups, where the initial trust is set to 0.67,
when changing reward from $R_{m}$ to $R_{t}$, team performance barely
decreases while the final trust increases; however, in the last 2 groups,
where the initial trust is 0.33, the team performance decreases in some cases,
which can be thought of as a compensation for the increment in the trust.
Therefore, if the robot starts in a high-trust state, then seeking trust will
not harm the long-term team performance, while if it starts in a low-trust
state, insisting to gain trust will cause the team performance to decrease.

Observation 3: Low initial trust does not lead to low team performance in the
reverse psychology model. In the first bar in each group, both the robot’s
assumed trust-behavior model $\hat{\pi}_{b}$ and the human’s actual behavior
$\tilde{\pi}_{b}$ are the reverse psychology model ${\pi}^{r}_{b}$. Comparing
the first bars in the 1st group and the 3rd group shows that the team
performance increases when the initial trust decreases from
$(\alpha_{1}{=}100,\beta_{1}{=}50)$ to $(\alpha_{1}{=}50,\beta_{1}{=}100)$.
This can be explained by the fact that, in the POMDP, both low-trust states
and high-trust states have high values (expected team performance), however, a
perceived failure has a larger impact on trust than a perceived success, and
thus manipulating the human to a low-trust condition will let the robot reach
a high-value state faster.

Observation 4: a disuse-human performs better than a reverse-psychology human
when working with a trustworthy robot. Within each of the first 2 groups,
where the robot is trustworthy (initial trust level is 0.67), the team
performance is higher when the actual trust-behavior model is the disuse model
($\tilde{\pi}_{b}=\pi_{b}^{d}$, bar 2, 4, 6, and 8) than the team performance
of the reverse psychology model ($\tilde{\pi}_{b}=\pi_{b}^{r}$, bar 1, 3, 5,
and 7). This observation indicates that the team can achieve high performance
as long as the human uses the disuse strategy no matter what the robot-assumed
trust-behavior is, even when the robot-assumed model doesn’t match the actual
model. However, this is not true in the last two groups, wherein the initial
trust is low (0.33).

##  VI Conclusion

Our study is the first attempt to examine the trust-behavior models in detail.
We proposed two trust-behavior models and investigated how the different
models affect a robot’s optimal policy and HRI team performance. Results
indicate that if the robot assumes that the human uses the reverse psychology
model, it will deliberately ‘manipulate’ the human when the human’s trust is
low. The reward function with the added trust seeking term can potentially
prevent this “manipulative” behavior. Our study should be viewed in light of
the following limitations. First, the concept of trust has been examined in
various disciplines including human-robot interaction [1], organizational
management [18], psychology [19], and social philosophy [20]. The diverse
interest has generated multiple definitions of trust. In our study, we use one
of the widely used definitions in human-autonomy interaction. Further research
should consider alternative definitions from other disciplines. Please see
[21, 18] for more discussion on the definitions of trust. Second, the trust
dynamics model used in the present study is primarily ability-centric. Even
though the focus of the present study is not on the trust dynamics model,
further research should be conducted to validate the simulation findings when
a more inclusive trust dynamics model is available. Such dynamics models could
consider additional characteristics of the trustee including the trustee’s
benevolence and integrity.

## References

  * [1] T. B. Sheridan, “Human-Robot Interaction: Status and Challenges,” _Human Factors_ , vol. 58, no. 4, pp. 525–532, 2016.
  * [2] H. Azevedo-Sa, S. K. Jayaraman, X. J. Yang, L. P. Robert, and D. M. Tilbury, “Context-adaptive management of drivers’ trust in automated vehicles,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 4, pp. 6908–6915, 2020.
  * [3] X. J. Yang, V. V. Unhelkar, K. Li, and J. A. Shah, “Evaluating effects of user experience and system transparency on trust in automation,” in _Proceedings of the 12th ACM/IEEE International Conference on Human-Robot Interaction (HRI ’17)_. ACM, 2017, pp. 408–416.
  * [4] N. Du, K. Y. Huang, and X. J. Yang, “Not all information is equal: effects of disclosing different types of likelihood information on trust, compliance and reliance, and task performance in human-automation teaming,” _Human factors_ , vol. 62, no. 6, pp. 987–1001, 2020.
  * [5] M. Chen, S. Nikolaidis, H. Soh, D. Hsu, and S. Srinivasa, “Trust-aware decision making for human-robot collaboration: Model learning and planning,” _ACM Transactions on Human-Robot Interaction (THRI)_ , vol. 9, no. 2, pp. 1–23, 2020.
  * [6] Y. Guo and X. J. Yang, “Modeling and Predicting Trust Dynamics in Human-Robot Teaming: A Bayesian Inference Approach,” _International Journal of Social Robotics_ , 2020. [Online]. Available: https://doi.org/10.1080/00140130802680773
  * [7] J. D. Lee and K. A. See, “Trust in automation: designing for appropriate reliance.” _Human Factors_ , vol. 46, no. 1, pp. 50–80, 2004.
  * [8] A. Xu and G. Dudek, “Optimo: Online probabilistic trust inference model for asymmetric human-robot collaborations,” in _2015 10th ACM/IEEE International Conference on Human-Robot Interaction (HRI)_. IEEE, 2015, pp. 221–228.
  * [9] Y. Lu, “Detecting and Overcoming Trust Miscalibration in Real Time Using an Eye-tracking Based Technique,” Ph.D. dissertation, University of Michigan, 2020\.
  * [10] W.-L. Hu, K. Akash, N. Jain, and T. Reid, “Real-time sensing of trust in human-machine interactions,” _IFAC-PapersOnLine_ , vol. 49, no. 32, pp. 48–53, 2016.
  * [11] H. Azevedo-Sa, S. K. Jayaraman, C. T. Esterwood, X. J. Yang, L. P. Robert, and D. M. Tilbury, “Real-Time Estimation of Drivers’ Trust in Automated Driving Systems,” _International Journal of Social Robotics_ , 2020.
  * [12] G. MacDonald, P. R. Nail, and J. R. Harper, “Do people use reverse psychology? an exploration of strategic self-anticonformity,” _Social Influence_ , vol. 6, no. 1, pp. 1–14, 2011.
  * [13] J. D. Lee and N. Moray, “Trust control strategies and allocation of function in human-machine systems,” _Ergonomics_ , vol. 35, no. 10, pp. 1243–1270, 1992.
  * [14] H. Soh, Y. Xie, M. Chen, and D. Hsu, “Multi-task trust transfer for human–robot interaction,” _The International Journal of Robotics Research_ , vol. 39, no. 2-3, pp. 233–249, 2020.
  * [15] X. J. Yang, Y. Guo, and C. Schemanske, “From trust to trust dynamics: Combining empirical and computational approaches to model and predict trust dynamics in human-autonomy interaction,” in _Human-Automation Interaction: Transportation._ , G. Duffy, Vincent, J. Landry, Steven, J. D. Lee, and N. A. Stanton, Eds. Springer, In presse.
  * [16] D. P. Losey and D. Sadigh, “Robots that take advantage of human trust,” in _2019 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2019, pp. 7001–7008.
  * [17] N. Wang, D. V. Pynadath, and S. G. Hill, “The impact of pomdp-generated explanations on trust and performance in human-robot teams.” in _AAMAS_ , 2016, pp. 997–1005.
  * [18] R. C. Mayer, J. H. Davis, F. D. Schoorman, F. D. Mayer, R. C., Davis, J. H., & Schoorman, R. C. Mayer, J. H. Davis, and F. D. Schoorman, “an Integrative Model of Organizational Trust.” _Academy of Management Review_ , vol. 20, no. 3, pp. 709–734, jul 1995.
  * [19] R. J. Klimoski and B. L. Karol, “The impact of trust on creative problem solving groups,” _Journal of Applied Psychology_ , vol. 61, no. 5, pp. 630–633, oct 1976.
  * [20] P. Faulkner and T. Simpson, _The Philosophy of Trust_. Oxford University Press, 2017.
  * [21] M. Lewis, K. Sycara, and P. Walker, _The Role of Trust in Human-Robot Interaction_. Cham: Springer International Publishing, 2018, pp. 135–159.