# Hierarchical Decompositions of Stochastic Pursuit-Evasion Games

Yue Guan1 Mohammad Afshari2 Qifan Zhang3 Panagiotis Tsiotras4 1Yue Guan is a
PhD Candidate with the School of Aerospace Engineering, Georgia Institute of
Technology, Atlanta, GA, USA. Email<EMAIL_ADDRESS>Afshari is a
Postdoctoral Fellow with the Institute for Robotics and Intelligent Machines,
Georgia Institute of Technology, Atlanta, GA, USA. Email:
<EMAIL_ADDRESS>Zhang is currently a Software Engineer at Google,
Mountain View, CA, USA. This work was done while QZ was at Georgia Tech.
Email<EMAIL_ADDRESS>Tsiotras is the David & Andrew Lewis
Chair and Professor with the School of Aerospace Engineering, Georgia
Institute of Technology, Atlanta, GA, USA. Email<EMAIL_ADDRESS>
###### Abstract

In this work we present a hierarchical framework for solving discrete
stochastic pursuit-evasion games (PEGs) in large grid worlds. With a partition
of the grid world into superstates (e.g., “rooms”), the proposed approach
creates a two-resolution decision-making process, which consists of a set of
local PEGs at the original state level and an aggregated PEG at the superstate
level. Having much smaller cardinality, both the local games and the
aggregated game can be easily solved to a Nash equilibrium. To connect the
decision-making at the two resolutions, we use the Nash values of the local
PEGs as the rewards for the aggregated game. Through numerical simulations, we
show that the proposed hierarchical framework significantly reduces the
computation overhead, while still maintaining a satisfactory level of
performance when competing against the flat Nash policies.

##  I Introduction

Pursuit-evasion games (PEGs) [1], also known as optimal tag games [2], were
introduced in 1960s. An abundance of literature exists on the topic, and some
notable examples include [3, 4, 5]. Many of the original pursuit-evasion games
are in a continuous setting, which makes their solution extremely difficult.
Often, some form of discretization is proposed to cast the problem on a
finite-dimensional space. A common numerical approach to discretize these
continuous stochastic games is via a Markov chain approximation method (MCAM)
[6]. MCAM approximates the original continuous stochastic PEG with a series of
discrete PEGs, each formulated as a Markov game. The discrete transition
probabilities are constructed based on the stochastic differential equations
(SDEs) governing the original stochastic game. Previous work [7] discussed the
details of the application of MCAM to PEGs. Under certain assumptions, and as
the discretization size approaches zero, the performance of the optimal policy
for the discrete PEG (extended to continuous domain through holding time)
converges to that of an optimal policy for the original PEG.

To achieve a good approximation, MCAM requires a fine discretization, which
leads to discrete PEGs with a prohibitively large state space. However,
solving for the Nash equilibrium for such large games is a challenge. For the
zero-sum case we consider in this paper, the classic value iteration for
stochastic games [8] requires solving a matrix game (equivalent to a linear
program) at each state and at each iteration. Even though efficient algorithms
exist for solving linear programs (LPs) [9], the sheer number of LPs to be
solved makes the classic “flat” state-space approach without hierarchy
extremely expensive. To address this challenge, we propose a hierarchical
framework to decompose a large PEG into multiple smaller ones.

In the single-agent domain, hierarchical decision-making has seen many
successes in expediting learning [10], addressing sparse rewards [11], etc.
One of the fundamental concepts in this area is the concept of options [12].
An option is a generalization of the concept of action, which, upon execution,
selects primitive actions (actions from the original action space) to reach
certain subgoals. Options can be regarded as a set of useful behaviors that an
agent can use directly off-the-shelf. By using options instead of primitive
actions, an agent can shorten its planning horizon and break down complex
tasks into multiple simpler subtasks.

Figure 1: A schematic of the proposed hierarchical approach. Left presents the
aggregated PEG, where the game is played at the room level and the agents
select options. Right is a local game restricted within a room. In this
scenario, the PEG ends with a successful capture.

Previous works [13, 14, 15] have extended the option framework and the
hierarchical approach to the multi-agent domain. However, the majority of that
research focuses on cooperative games [13] or team games [14, 15]; general
results in the competitive setting are still lacking. The key challenge in the
multi-agent scenario comes from the fact the subgoal exists in the joint state
space of all the agents. Subsequently, a subgoal preferable to one agent may
not be favorable to the others, especially in competitive games. As a result,
it is not straightforward to extend single-agent hierarchical techniques to
multi-agent competitive scenarios.

In this work, we propose a hierarchical framework to solve large two-agent
zero-sum pursuit-evasion games (PEGs). Under this framework, the grid world is
first abstracted into multiple superstates (i.e. “rooms”). The proposed method
then exploits the separable dynamics of the PEGs111The spatial transitions of
the individual agents are independent of the other agent’s position and
action. to construct options that serve as generalized action to navigate
agents among their individual superstates. With the superstates and the
options, we construct a competitive decision-making process operating at two
resolutions: local PEGs operating at the original resolution of the state
space, each restricted within a superstate, and an aggregated PEG operating at
the superstate-level, where the agents select options to navigate among the
superstates and the options subsequently select primitive actions to reach the
target superstate. An illustrative schematic is presented in Fig. 1. The local
PEGs and the aggregated game have much smaller state spaces than the original
game, and their Nash equilibria can be easily computed. A key element in our
approach is a way to transfer information between the two levels.
Specifically, we connect the two resolution levels through a value
propagation: we solve the Nash equilibrium of the local PEGs first and use the
computed Nash values as the rewards in the aggregated PEG. The end result is a
hierarchical policy that operates at the two resolutions. Finally, through
numerical simulations, we demonstrate that the proposed hierarchical approach
significantly reduces the computation overhead, while still achieving
satisfactory performance when competing against flat Nash policies.

##  II Problem Formulation

We consider a discrete two-player pursuit-evasion game (PEG) over a grid
world. An example is presented in Fig. 3, where a Pursuer (red) and an Evader
(blue) inhabit a 11-by-11 grid world and the dark cells denote obstacles
(e.g., walls). At the beginning of each episode, both the Pursuer and the
Evader start at a randomly-chosen position. The Pursuer needs to capture the
Evader by having the Evader within its capture zone (red dashed square), while
the Evader tries to avoid capture. The episode ends when the Evader is
captured. To ensure capture, we assume that the Pursuer can move at most two
cells in each of the four directions, while the Evader can move at most one
cell. Together with the “no-move” action, the Pursuer has nine primitive
actions, while the Evader has five. The reachable states for the two agents
are marked with the color of each agent, respectively, as shown in Fig. 3. If
an agent intends to make a move that will hit the wall, it stays at its
original position and no penalty is given.

Formally, we define a discrete pursuit-evasion game (PEG) as a tuple
${\mathcal{G}=\langle\mathcal{S}^{1},\mathcal{S}^{2},\mathcal{A}^{1},\mathcal{A}^{2},\mathcal{T}^{1},\mathcal{T}^{2},\mathcal{R},\mathcal{F},\beta\rangle}$.
The discrete individual state space $\mathcal{S}^{i}$ corresponds to the
position of agent $i$, and the discrete individual action space
$\mathcal{A}^{i}$ denotes the actions agent $i$ can take. We refer to these
actions as the primitive actions. We use
$\mathcal{S}=\mathcal{S}^{1}\times\mathcal{S}^{2}$ and
$\mathcal{A}=\mathcal{A}^{1}\times\mathcal{A}^{2}$ to denote the joint state
and action spaces. The superscript $i$ denotes that an entity is associated
with agent $i$. An entity without a superscript is assumed to be associated
with the joint (state or action) space. The terminal set $\mathcal{F}$
consists of all joint states $s=(s^{1},s^{2})$ that correspond to successful
capture. The movement of the agents is characterized by the individual agent
dynamics
$\mathcal{T}^{i}:\mathcal{S}^{i}\times\mathcal{A}^{i}\times\mathcal{S}^{i}\to[0,1]$,
where $\mathcal{T}^{i}(s^{{i\kern 0.70004pt\prime}},|s^{i},a^{i})$ denotes the
probability that agent $i$ transitions from its current state (position)
$s^{i}$ to $s^{{i\kern 0.70004pt\prime}}$ under the action $a^{i}$. The joint
dynamics is given by
$\mathcal{T}(s^{\prime}|s,a)=\mathcal{T}^{1}(s^{1\prime}|s^{1},a^{1})\mathcal{T}^{2}(s^{2\prime}|s^{2},a^{2})$
for all states $s=(s^{1},s^{2})\notin\mathcal{F}$, and $\mathcal{T}(s|s,a)=1$
for all joint action $a\in\mathcal{A}$ if $s\in\mathcal{F}$. In other words,
all terminal joint states in $\mathcal{F}$ are absorbing. The function
$\mathcal{R}:\mathcal{S}\to[R_{\min},R_{\max}]$ provides the reward at the
joint state $s$. We assume a zero-sum reward structure and let the Pursuer be
the maximizing Agent 1 and the Evader be the minimizing Agent 2. We further
consider a sparse reward and assign $\mathcal{R}(s)=+1$ for $s\in\mathcal{F}$,
and $\mathcal{R}(s)=0$ otherwise. Finally, $\beta\in(0,1)$ is the discount
factor.

Figure 2: A pursuit-evasion game.

Figure 3: The four “rooms”.

Assuming full observation of the joint states, we first consider Markovian
mixed policies for the two agents. Specifically, the policy $\pi^{i}$ for
agent $i$ is a mapping $\pi^{i}:\mathcal{A}^{i}\times\mathcal{S}\to[0,1]$,
where $\pi^{i}(a^{i}|s)$ gives the probability of choosing action $a^{i}$ at
the joint state $s$. Given a policy pair $(\pi^{1},\pi^{2})$, we denote the
induced value at each state $s\in\mathcal{S}$ as

$\mathcal{V}^{\pi^{1},\pi^{2}}(s)=\mathbb{E}^{\pi^{1},\pi^{2}}\left[\sum_{t=0}^{\infty}\beta^{t}\mathcal{R}(s_{t})|s_{0}=s\right],$
(1)

where $s_{t}=(s^{1}_{t},s^{2}_{t})$ is the joint state at time step $t$.

The Nash equilibrium (NE) is then defined as a policy pair
$(\pi^{1*},\pi^{2*})$, such that, at each joint state, $s\in\mathcal{S}$,

$\mathcal{V}^{\pi^{1},\pi^{2*}}(s)\leq\mathcal{V}^{\pi^{1*},\pi^{2*}}(s)\leq\mathcal{V}^{\pi^{1*},\pi^{2}}(s),$
(2)

for all admissible policies $\pi^{1}$ and $\pi^{2}$. That is, there is no
incentive for either agent to unilaterally deviate from a NE. Even though
multiple NEs may exist in a zero-sum game, the max-min (optimal) value of a NE
is unique and can be computed via value iterations [8] with the following
update rules:

$\displaystyle\mathcal{Q}_{k+1}$ $\displaystyle(s,a^{1},a^{2})$ (3)
$\displaystyle=\mathcal{R}(s)+\beta\sum_{s^{\prime}\in\mathcal{S}}\mathcal{T}(s^{\prime}|s,a^{1},a^{2})\mathrm{Nash}\left(\bm{\mathcal{Q}}_{k}(s^{\prime})\right),$

where the subscript $k$ indicates the iteration step and the Q-matrix
$\bm{\mathcal{Q}}(s)\in\mathbb{R}^{|\mathcal{A}^{1}|\times|\mathcal{A}^{2}|}$
is defined as
$[\bm{\mathcal{Q}}(s)]_{a^{1},a^{2}}=\mathcal{Q}(s,a^{1},a^{2})$. At each
joint state $s$, the Nash value of the Q-matrix can be computed via the
following linear program from Agent 1’s perspective:

$\displaystyle\quad\quad\max_{v,\bm{\pi}^{1}(s)}\quad$ $\displaystyle v$ (4)
subject to $\displaystyle
v\mathds{1}-\bm{\pi}^{1}(s)^{\top}\bm{\mathcal{Q}}(s)\leq 0,$
$\displaystyle\mathds{1}^{\top}\bm{\pi}^{1}(s)=1,~{}~{}\bm{\pi}^{1}(s)\geq 0,$

where $\bm{\pi}^{1}(s)\in\mathbb{R}^{|\mathcal{A}^{i}|}$ is the policy of
Agent 1 in vector form and $\mathds{1}$ is a column vector full of ones of
compatible dimension. The solution $v^{*}$ of (4) gives the Nash value
$v^{*}=\mathrm{Nash}\left(\bm{\mathcal{Q}}(s)\right)$, and $\bm{\pi}^{1*}(s)$
gives the Nash policy for Agent 1 at state $s$. The Nash policy for Agent 2
can be solved through a similar linear program.

Although efficient algorithms exist to solve linear programs [9], there are
still 4,624 states for the example shown in Fig. 3 (68 position states for
each agent). That is, to compute the Nash equilibrium for this rather small
problem one needs to solve 4,624 linear programs for each value iteration. The
number of linear programs can easily get prohibitively large. For example, the
last example in Fig. 7 requires almost one million LPs per iteration.
Consequently, we seek an alternative approach that will allow us to decompose
a large game into smaller pieces using a hierarchical approach.

The proposed hierarchical approach is motivated by the following intuitive
observations: (i) when the two agents are far away, knowing the approximate
position of the opponent is enough to make a decent decision, and at this
stage, the agents do not need to perform fine maneuvers to achieve
satisfactory performance; and (ii) when the two agents are close and a capture
is imminent, the agents need the exact position to perform precise maneuvers
to achieve (or avoid) capture. In this case, the agents can further restrict
their attention to the local environment and ignore the rest of the grid
world. Motivated by these two observations, we want to design intelligent
agents that make decisions according to various resolutions of the state
space, depending on the circumstances.

##  III The Hierarchical PEG

In this section, we will first partition the grid world domain (individual
state space $\mathcal{S}^{i}$) into smaller components, which we refer to as
the individual superstates (or “rooms,” see Fig. 3). A decision-making process
is then constructed to operate at two different resolutions: (i) superstate-
level, at which the two agents navigate among the “rooms” using options [12],
and the Pursuer tries to be in the same room as the Evader; and (ii) state-
level, where the two agents play a local PEG restricted within a superstate
that contains a terminal state 222With the capture region in Fig. 3, a capture
may happen when the two agents are in neighboring rooms. For conciseness,
however, we visualize local games when the two agents are in the same room..
If capture occurs, the game terminates (visualized in Fig. 1); otherwise, the
Evader escapes to another room, and the process reverses back to the
aggregated game at the superstate level. The end product is a hierarchical
policy, whose execution will be discussed in Section IV.

###  III-A Superstates

We first formalize the definition of “rooms” through the concept of individual
superstates. Let $\Gamma^{i}=\\{\gamma^{i}_{1},\ldots,\gamma^{i}_{\ell}\\}$
($i=1,2$) be a partition of the individual state space $\mathcal{S}^{i}$ for
agent $i$, where each $\gamma^{i}_{k}$, $k\in\\{1,2,\dots,\ell\\}$ is a subset
of $\mathcal{S}^{i}$. We say that a partition $\Gamma^{i}$ is an aggregated
state space for agent $i$ if
$\mathcal{S}^{i}=\bigcup_{k=1}^{\ell}\gamma^{i}_{k}$ and
$\gamma^{i}_{j}\bigcap\gamma^{i}_{k}=\varnothing$ for all $j\neq k$. We refer
to the subset $\gamma^{i}\in\Gamma^{i}$ as an individual superstate, while the
original individual state $s^{i}\in\mathcal{S}^{i}$ will still be referred to
as an individual state for agent $i$.

###### Remark 1

The “rooms” give a natural definition of individual superstates. That is, each
room can be treated as a single individual superstate. However, the concept of
superstate is much more general than the concept of a “room,” as it does not
hinge on a geometric interpretation.

Next, we identify two important classes of individual states that serve as a
medium through which agents transition from one individual superstate to
another.

######  Definition 1 (adopted from [16])

The periphery and the boundary of an individual superstate
$\gamma^{i}\in\Gamma^{i}$ are defined as

$\displaystyle\mathrm{Peri}(\gamma^{i})$
$\displaystyle~{}\quad=\big{\\{}s^{{i\kern
0.70004pt\prime}}\notin\gamma^{i}\kern 1.00006pt|\;\exists
s^{i}\in\gamma^{i},a^{i}\in\mathcal{A}^{i}\text{ s.t.
}\mathcal{T}^{i}(s^{{i\kern 0.70004pt\prime}}|s^{i},a^{i})>0\big{\\}},$
$\displaystyle\mathrm{Bndry}(\gamma^{i})$
$\displaystyle~{}\quad=\big{\\{}s^{{i\kern 0.70004pt\prime}}\in\gamma^{i}\kern
1.00006pt|\;\exists s^{i}\notin\gamma^{i},a^{i}\in\mathcal{A}^{i}\text{ s.t.
}\mathcal{T}^{i}(s^{{i\kern 0.70004pt\prime}}|s^{i},a^{i})>0\big{\\}}.$

Figure 4: Boundary (blue stripes) and Periphery (red stripes) of Room-0.

Figure 5: The option for navigating from Room-0 to Room-2.

In words, $\mathrm{Peri}(\gamma^{i})$ is the set of individual states outside
$\gamma^{i}$ that can be reached from $\gamma^{i}$ within one transition.
Similarly, $\mathrm{Bndry}(\gamma^{i})$ is the set of individual states within
$\gamma^{i}$ that can be reached from outside $\gamma^{i}$ within one
transition. The periphery and boundary for the Evader are visualized in Fig.
5, for the environment shown in Fig. 3.

###### Definition 2

An individual superstate $\gamma^{{i\kern 0.70004pt\prime}}$ is adjacent to
$\gamma^{i}$, denoted as $\gamma^{i}\leadsto\gamma^{{i\kern
0.70004pt\prime}}$, if $\mathrm{Peri}(\gamma^{i})\cap\gamma^{{i\kern
0.70004pt\prime}}\neq\varnothing$.

The joint aggregated state space is then defined as the Cartesian product
${\Gamma=\Gamma^{1}\times\Gamma^{2}}$, and the notion of periphery, boundary
and adjacency can be easily extended to the joint superstates. 333 For
simplicity, we consider the case where $\Gamma^{1}=\Gamma^{2}$. However, the
proposed framework can be easily extended to the scenarios where different
abstractions of the environment are used by the two agents.  For example, the
periphery of a joint superstate $\gamma\in\Gamma$ is defined as

$\mathrm{Peri}(\gamma)=\big{\\{}s^{\prime}\notin\gamma\kern
1.00006pt|\;\exists s\in\gamma,a\in\mathcal{A}\text{ s.t.
}\mathcal{T}(s^{\prime}|s,a)>0\big{\\}},$

where $s$ and $a$ are joint state and joint action, respectively.

###  III-B Options

To construct the corresponding macro-actions of the aggregated game that
result in transitions among individual superstates we leverage the option
framework [12]. The separable dynamics of PEGs allows us to generate options
in the individual state space, which significantly alleviates the
computational burden.

###### Definition 3

An option for agent $i$ is a tuple

$o^{i}=\langle\mathcal{S}^{i}_{o^{i}},\mathcal{F}^{i}_{o^{i}},\pi^{i}_{o^{i}}\rangle,$

where $\mathcal{S}^{i}_{o^{i}}\subset\mathcal{S}^{i}$ is the domain of the
option, and the option $o^{i}$ is only available over the individual states
within the domain; $\mathcal{F}^{i}_{o^{i}}$ is the terminal set, and the
option terminates once agent $i$ reaches an individual state within the set;
finally, ${\pi^{i}_{o^{i}}:\mathcal{S}^{i}_{o^{i}}\to\mathcal{A}^{i}}$ is the
local policy, according to which agent $i$ selects its primitive action given
its individual state within the domain.

For each pair of adjacent individual superstates
${\gamma^{i}\leadsto\gamma^{{i\kern 0.70004pt\prime}}}$, we construct a Markov
Decision Process (MDP) to generate the local policy for option
$o^{i}_{\gamma^{i}\leadsto\gamma^{i\kern 0.50003pt\prime}}$ that navigates
agent $i$ from individual states in $\gamma^{i}$ to $\gamma^{{i\kern
0.70004pt\prime}}$. This local MDP is defined as
$\mathcal{M}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}}=\langle\mathcal{S}^{i}|_{\gamma^{i}},\mathcal{A}^{i},\mathcal{T}^{i}|_{\gamma^{i}},\widetilde{\mathcal{R}}^{i}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}},\beta\rangle$, where

  1. $i)$

$\mathcal{S}^{i}|_{\gamma^{i}}=\gamma^{i}\cup\mathrm{Peri}(\gamma^{i})$ is the
restricted local state space;

  2. $ii)$

$\mathcal{A}^{i}$ is the original action space;

  3. $iii)$

$\mathcal{T}^{i}|_{\gamma^{i}}$ is the restricted transition kernel, such
that, for all ${a^{i}\in\mathcal{A}^{i}}$,

$\displaystyle\mathcal{T}^{i}|_{\gamma^{i}}(s^{{i\kern
0.70004pt\prime}}|s^{i},a^{i})$ $\displaystyle=\mathcal{T}^{i}(s^{{i\kern
0.70004pt\prime}}|s^{i},a^{i})\;$ $\displaystyle\text{if
}s^{i}\in\gamma^{i},s^{{i\kern
0.70004pt\prime}}\in\mathcal{S}^{i}|_{\gamma^{i}}$
$\displaystyle\mathcal{T}^{i}|_{\gamma^{i}}(s^{i}|s^{i},a^{i})$
$\displaystyle=1,$ $\displaystyle\text{if }s^{i}\in\mathrm{Peri}(\gamma^{i}).$

  4. $iv)$

$\widetilde{\mathcal{R}}^{i}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}}:\mathcal{S}^{i}|_{\gamma^{i}}\to\mathbb{R}$ is the local
pseudo-reward, given by

$\displaystyle\widetilde{\mathcal{R}}^{i}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}}(s^{i})$ $\displaystyle=+1,\qquad$ $\displaystyle\text{if
}s^{i}\in\mathrm{Peri}(\gamma^{i})\cap\gamma^{{i\kern 0.70004pt\prime}},$
$\displaystyle\widetilde{\mathcal{R}}^{i}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}}(s^{i})$ $\displaystyle=0,\qquad$ otherwise.

The local pseudo-reward provides an incentive for agent $i$ to move to the
periphery states in the target individual superstate $\gamma^{{i\kern
0.70004pt\prime}}$. Once the agent reaches the target superstate, the local
MDP terminates. The local MDP $\mathcal{M}_{\gamma^{i}\leadsto\gamma^{{i\kern
0.50003pt\prime}}}$ is a single-agent problem and can be easily solved via
value iterations or policy iterations444 We let both agent maximizes with
respect to this pseudo-reward, just for reaching the target superstate. . The
resulting optimal policy
$\pi^{i*}:\mathcal{S}^{i}|_{\gamma^{i}}\to\mathcal{A}^{i}$ is then assigned as
the local policy for option $o^{i}_{\gamma^{i}\leadsto\gamma^{i\kern
0.50003pt\prime}}$. Note that the local policy operates on the individual
state space.

We set the domain for option $o^{i}_{\gamma^{i}\leadsto\gamma^{i\kern
0.50003pt\prime}}$ as $\gamma^{i}\subset\mathcal{S}^{i}$, and the terminal set
as $\mathrm{Peri}(\gamma^{i})$. Consequently, agent $i$ can initiate option
$o^{i}_{\gamma^{i}\leadsto\gamma^{i\kern 0.50003pt\prime}}$ within superstate
$\gamma^{i}$ and the option automatically terminates when the agent leaves
$\gamma^{i}$. An example of the Evader’s ‘Room-0 To Room-2’ option is
presented in Fig 5. The arrows are the actions taken by the local policy at
each specific cell within the room, and the red cells are the target periphery
states within the individual superstate ‘Room-2’.

For each adjacent pair of individual superstates, we solve for all such
options, and we use $\mathcal{O}^{i}$ to denote the set of all these options
for agent $i$. Furthermore, we let $\mathcal{O}^{i}(\gamma)$ denote the
options available to agent $i$ at the joint superstate $\gamma$.

###  III-C Local Games

One key ingredient we are still missing for the aggregated game is the
aggregated rewards. Since the aggregated game transitions to a local game when
the two agents are in the same room2, we use the Nash value of the local PEG
to inform the decision-making at the superstate level.

Formally, we construct local games for each of the _joint_ superstates
$\gamma$ such that $\gamma\cap\mathcal{F}\neq\varnothing$, where $\mathcal{F}$
is the set of joint states that correspond to successful capture in PEG.

A local game, restricted to a joint superstate $\gamma$, is defined as a tuple
$\mathcal{G}_{\gamma}=\langle\mathcal{S}|_{\gamma},\mathcal{A}^{1},\mathcal{A}^{2},\mathcal{T}_{\gamma},\mathcal{R}_{\gamma},\beta\rangle$,
where

  1. $i)$

$\gamma\cap\mathcal{F}\neq\varnothing$.

  2. $ii)$

$\mathcal{S}|_{\gamma}$ is the restricted local joint state space, defined as

$\mathcal{S}|_{\gamma}=\gamma\cup\mathrm{Peri}(\gamma).$

  3. $iii)$

$\mathcal{A}^{i}$ ($i=1,2$) are the original action spaces.

  4. $iv)$

$\mathcal{T}_{\gamma}$ is the joint transition restricted to the local state
space, given by

$\displaystyle\mathcal{T}_{\gamma}(s^{\prime}|s,a^{1},a^{2})$
$\displaystyle=\mathcal{T}(s^{\prime}|s,a^{1},a^{2}),\;$
$\displaystyle\text{if}\kern 1.00006pts\in\gamma,\kern
1.00006pts^{\prime}\in\mathcal{S}|_{\gamma}$
$\displaystyle\mathcal{T}_{\gamma}(s|s,a^{1},a^{2})$ $\displaystyle=1,\qquad$
$\displaystyle\text{if}\;s\in\mathrm{Peri}(\gamma).$

  5. $v)$

$\mathcal{R}_{\gamma}$ is the local reward, and

$\mathcal{R}_{\gamma}(s)=\mathcal{R}(s)\quad\forall
a^{i}\in\mathcal{A}^{i},\;s\in\mathcal{S}|_{\gamma}.$

The local games terminates555If a capture happens, the PEG terminates.
Otherwise, the Evader escaped to another superstate, and we transition back to
the aggregated game. once the agents leave the superstate $\gamma$, which
corresponds to reaching the periphery states of the joint superstate $\gamma$.
Consequently, the local games have absorbing peripheries. Meanwhile, each of
these local games has a much smaller state space than the original game and
can be easily solved via value iteration as in (3)-(4). We denote the local
Nash value as $\mathcal{V}^{*}_{\gamma}$ and the local Nash policies as
$\pi^{i*}_{\gamma}$, $i=1,2$. The local Nash policy $\pi^{i*}_{\gamma}$
governs the behaviors of agent $i$ when it is in the superstate $\gamma$. The
Nash values will be used as the rewards for the aggregated game in the next
subsection.

###  III-D Aggregated Game

The aggregated game operates over the joint superstates. Instead of directly
selecting a primitive action, the agent in the aggregated game selects an
option based on the current joint superstate observation. First, we define the
transition probabilities between the joint superstates resulting from the
options introduced in Section III-B.

We leverage the discounted multi-step transition probability [12] to properly
address the different timescale on which the aggregated game operates. With
the convention $s=(s^{1},s^{2})$ and $s^{\prime}=(s^{1\prime},s^{2\prime})$,
the discounted multi-step transition probability between two joint superstates
$\gamma$ and $\gamma^{\prime}$ can be computed as

$\displaystyle\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime}|\gamma,o^{1},o^{2})=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\phi(\gamma^{\prime}|s,o^{1},o^{2}),$
(5)

where,

$\displaystyle\phi(\gamma^{\prime}|s,$ $\displaystyle
o^{1},o^{2})=\beta\sum_{s^{\prime}\in\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,\pi^{1}_{o^{1}}(s^{1}),\pi^{2}_{o^{2}}(s^{2}))$
(6)
$\displaystyle+\beta\sum_{s^{\prime}\in\gamma}\mathcal{T}\left(s^{\prime}|s,\pi^{1}_{o^{1}}(s^{1}),\pi^{2}_{o^{2}}(s^{2})\right)\phi(\gamma^{\prime}|s^{\prime},o^{1},o^{2}).$

The computation performed in (5) is equivalent to: (a) fix agent $i$’s policy
to $\pi^{i}_{o^{i}}$ ($i=1,2$) and set the $\mathrm{Peri}(\gamma)$ as
absorbing, (b) start the Markov Chain induced by
$(\pi^{1}_{o^{1}},\pi^{2}_{o^{2}})$ with a uniform distribution over
$\mathrm{Bndry}(\gamma)$, and (c) compute the probability of the Markov Chain
ending up in joint superstate $\gamma^{\prime}$ and properly discount the
probability based on the arrival time. See Appendix A for more details.

With the multi-step transitions, we can define the aggregated game
$\mathcal{G}_{\Gamma}=\langle\Gamma^{1},\Gamma^{2},\mathcal{O}^{1},\mathcal{O}^{2},\widetilde{\mathcal{T}}^{\beta},\widetilde{\mathcal{R}},\beta\rangle$,
where

  1. $i)$

$\Gamma=\Gamma^{1}\times\Gamma^{2}$ is the joint aggregated state space.

  2. $ii)$

$\mathcal{O}^{i}$ is the set of options constructed for agent $i$ to navigate
between its individual superstates.

  3. $iii)$

$\widetilde{\mathcal{T}}^{\beta}$ is the discounted transitions in (5)-(6).

  4. $iv)$

$\widetilde{\mathcal{R}}$ is the aggregated reward, given by

$\displaystyle\widetilde{\mathcal{R}}(\gamma)$
$\displaystyle=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\mathcal{V}^{*}_{\gamma}(s),\quad$
$\displaystyle\text{if }\gamma\cap\mathcal{F}\neq\varnothing,$
$\displaystyle\widetilde{\mathcal{R}}(\gamma)$ $\displaystyle=0,\quad$
$\displaystyle\text{if }\gamma\cap\mathcal{F}=\varnothing,$

where $\mathcal{V}^{*}_{\gamma}$ is the Nash value of the local game within
$\gamma$.

We will denote the Nash policies for the aggregated game by
$\pi^{i*}_{\Gamma}$ ($i=1,2$).

###### Remark 2

Since the boundary states are the entry points to a superstate, when computing
the aggregated transitions, we assign the initial distribution over the
boundary states. Since no prior knowledge is given regarding how agents
approach this superstate, a uniform distribution is considered. Similarly, we
average the Nash value on the boundary states and assign it as the terminal
reward for the aggregated game.

###  III-E Proposed Algorithm

We summarize the procedure to find the hierarchical policy for the PEG in
Algorithm 1.

###### Remark 3

Each of the local games can be further decomposed if needed. The trade-off
between having multiple levels of decomposition and having a single level with
local games of smaller size is a topic for future investigation.

1 Inputs: Game $\mathcal{G}$, Individual State Space Partition $\Gamma^{i}$ ;

/* Superstates and options */

2 Generate the superstates [Section III-A] ;

3 Generate option $o_{\gamma^{i}\leadsto\gamma^{{i\kern 0.50003pt\prime}}}$
for each agent $i$ and each adjacent individual superstate pair [Section
III-B] ;

4 Store the options in $\mathcal{O}^{i}$ ;

/* Local games */

5 Generate local games for joint superstate $\gamma$ if
$\gamma\cap\mathcal{F}\neq\varnothing$ [Section III-C];

6 Solve the Nash equilibrium of the local games;

7 Store the values of the local game within $\gamma$ as
$\mathcal{V}^{*}_{\gamma}$ and the local Nash policies as $\pi^{i*}_{\gamma}$;

/* Aggregated game */

8 Construct the aggregated game with $\mathcal{O}^{i}$ as the action space and
$\mathcal{V}^{*}_{\gamma}$ as the rewards [Section III-D];

9 Solve the NE of the aggregated game;

10 Store the Nash policy of the aggregated game as $\pi^{i*}_{\Gamma}$ ;

11 Outputs: Option sets $\mathcal{O}^{i}$; Local game NE $\pi^{i*}_{\gamma}$;
Aggregated game NE $\pi^{i*}_{\Gamma}$.

Algorithm 1 Hierarchical Decomposition Algorithm

###  III-F Complexity Analysis

We present a complexity comparison between the flat Nash approach and the
hierarchical approach. Suppose we have a grid world with $M\times M$ rooms,
each room consisting of $N\times N$ cells, and we generate an individual
superstate each with a single room within it.

#### Time Complexity

The original PEG has $(MN)^{4}$ joint states. Then, for each value iteration,
the flat Nash solution needs to compute $\mathcal{O}(M^{4}N^{4})$ matrix
games. On the other hand, we have an aggregated game with ${M^{2}}$ individual
superstates, where each individual superstate containing a room with $N^{2}$
individual states. There are at most $5M^{2}$ local games to be solved2, each
with $N^{4}$ joint states. There is an extra aggregated game with $M^{4}$
joint superstates. Consequently, the total number of matrix game solved per
iteration666The hierarchical approach does not solve all these games
simultaneously. We just sum the number of matrix games solved per iteration
for each of the games to give a qualitative comparison.  in the hierarchical
approach is $\mathcal{O}(M^{2}N^{4}+M^{4})$.

#### Space Complexity

We present a space complexity analysis for storing the flat Nash policy and
the hierarchical policies. The flat Nash policy for agent $i$ is a mapping
from the original joint state space to a distribution over the action space
$\mathcal{A}^{i}$. Storing this flat policy is equivalent to storing a vector
with $\mathcal{O}(M^{4}N^{4}|\mathcal{A}^{i}|)$ entries.

The hierarchical policy for agent $i$ has three components: the aggregated
Nash policy, the local Nash policies, and the local option policies. The
aggregated Nash policy observes the joint superstate and selects options,
consequently it requires $(M^{4}|\mathcal{O}^{i}|)$ entries to store. We have
at most $5M^{2}$ local games, and each has a local Nash policy that requires
$(N^{4}|\mathcal{A}^{i}|)$ entries to store. Finally, we have ${M}^{2}$
individual superstates, each with at most four adjacent superstates (“rooms”).
That is at most $4{M}^{2}$ options, each requiring $(N^{2}|\mathcal{A}^{i}|)$
entries to store. Under the assumption that the number of options available at
each joint superstate is of the same order as the number of actions, we have
the total amount of entries for the hierarchical policy of agent $i$ as
$\mathcal{O}\left((M^{4}+M^{2}N^{4}+4M^{2}N^{2})|\mathcal{A}^{i}|\right)$.

##  IV The Hierarchical Policy

The hierarchical policy constructed under the proposed framework consists of
policies in two resolutions: (i) the aggregated Nash policy
$\pi^{i*}_{\Gamma}$ observes the joint superstate $\gamma$ and selects an
option ${o^{i}\in\mathcal{O}^{i}(\gamma)}$; once an option $o^{i}$ is
selected, the local policy $\pi^{i}_{o^{i}}(s^{i})$ observes the individual
state $s^{i}$ and selects primitive actions; (ii) When the system transitions
to a joint superstate $\gamma$ that contains a local game, the local Nash
policy $\pi^{i*}_{\gamma}(s)$ is deployed, and the agents directly selects its
primitive action based on state observation. If the system later leaves the
superstate that contains a local game, the process reverse back to the
aggregated game. Algorithm 2 presents the execution of the proposed
hierarchical policy.

1 Inputs: Option sets $\mathcal{O}^{i}$, Local game NEs $\pi^{i*}_{\gamma}$,
Aggregated game NE $\pi^{i*}_{\Gamma}$, ($i=1,2$);

2 while  _PEG not terminated_ do

3 Observe current superstate $\gamma$;

4 if  _$\gamma$ contains a local game_ then

5 while  _Local PEG not terminated_ do

6 Observe current state $s$;

7 Select action $a^{i}$ according to $\pi^{i*}_{\gamma}(s)$ ;

8 Environment step forward with $(a^{1},a^{2})$;

9

10 end while

11

12 else

13 Select option $o^{i}$ according to $\pi^{i*}_{\Gamma}(\gamma)$ ;

14 while  _Not leaving joint $\gamma$_ do

15 Observe current individual state $s^{i}$ ;

16 Select action $a^{i}$ according to option local policy
$\pi^{i}_{o^{i}}(s^{i})$;

17 Environment step forward with $(a^{1},a^{2})$

18 end while

19

20

21 end while

Algorithm 2 Execution of the Hierarchical Policy

The while loop in lines 5 to 9 makes the hierarchical policy non-Markovian,
since once an option is selected, the option policy is executed till the
option terminates. Consequently, the primitive action taken by the agent
depends not only on its current state, but also on the option it has selected
when entering the superstate. At line 12, we let the agents terminate their
old options when the joint superstate makes a transition777 Equivalent to any
one of the agents reaches the terminal set of its option.. Note that this
“any” condition [15] is consistent with the definition of the aggregated
transitions in (5).

An example of the execution of the proposed hierarchical policy is presented
in Fig. 6. The agents first start with the aggregated game and select their
options based on the current superstate. After the selected option executes a
sequence of primitive actions, the system transitions to a local game, where
the agents select primitive actions according to the local Nash. In the last
subplot, the Evader escaped the room, and the system transitions back to the
aggregated game, and the process continues.

Figure 6: An example of the execution of the proposed hierarchical policy.

Finally, the hierarchical policy has a different information structure from
the flat policy. The flat Nash policy requires the exact individual state
information of both the agents at all time steps. The hierarchical policy, on
the other hand, requires the exact location of the opponent only when the two
agents are in the same room. When the two agents are far away, the
hierarchical policy only requires the room information of the opponent. In
that respect, the hierarchical policy can accommodate cases when the sensors
of the players are inaccurate and do not provide the precise location of the
other agent when the two are far apart.

##  V Numerical Results

In this section, we verify the efficacy of the proposed algorithm through
numerical simulations. We solve the original Nash equilibrium and the
hierarchical solution for four PEGs with different sizes, shown in Fig. 7.

Figure 7: The test grid worlds: 2$\times$2 (4.7K joint states), 3$\times$3
(56.6K joint states), 4$\times$4 (78.9K joint states), and 6$\times$6 (0.9M
joint states).

Table I shows the computation time using the flat method and the proposed
hierarchical approach. Each component of the hierarchical approach is also
presented. One easily sees that the computation time is significantly reduced
through the hierarchical decomposition of large games. Meanwhile, the majority
of the computation time is spent on the computation of NEs of the local games.
This is expected, as we have multiple local games and they are all executed at
the finest resolution. However, solving for the NE of the local games can be
easily parallelized, since the local games are independent from one another.
One also observes that when the state space is small (as in the 2$\times$2
case), the hierarchical approach is slower than the flat approach. This is due
to the additional auxiliary tasks the hierarchical approach needs to perform
(such as generating the abstract transitions and the local games) that add to
the initial computational overhead.

TABLE I: Computation Time Comparison [in seconds] PEG Size | 2 $\times$ 2 | 3 $\times$ 3 | 4 $\times$ 4 | 6 $\times$ 6
---|---|---|---|---
Flat | 380.62 | 916.85 | 7068.72 | 37412.62
Hierarchical | 477.46 | 638.91 | 2095.70 | 4501.27
\- Option | 0.92 | 2.07 | 4.70 | 9.70
\- Local Game | 462.54 | 610.98 | 2034.33 | 4257.70
\- Abstract Game | 14.00 | 25.86 | 56.67 | 233.87

We provide a log-log plot in Fig. 8 to better illustrate the trend of
computation time vs. state space size. The computation time of the
hierarchical approach grows slower with respect to the size of the PEG than
the flat approach, which confirms the motivation of this work.

Figure 8: The log-log plot of the computation time vs. state space size trend.

Table II compares the performance of the hierarchical policy versus the flat
Nash policy. For each grid world, we ran 2,000 episodes, with randomly
selected initial positions for the Pursuer and the Evader. We used the average
number of transitions till capture as the performance metric. We let the
agents with different types of policies play against each other. When the
hierarchical pursuer competed against the Nash evader, it took about 15% more
steps to capture compared to a Nash pursuer. This performance drop is
expected, since the Nash pursuit policy is, by definition, the best response
to the Nash evasion policy, but the relative performance drop decreases when
the state space gets larger.

TABLE II: Average # Steps till Capture P vs. E | 2 $\times$ 2 | 3 $\times$ 3 | 4 $\times$ 4 | 6 $\times$ 6
---|---|---|---|---
Nash vs. Nash | 5.41 | 13.12 | 18.42 | 25.85
Hier vs. Nash | 6.62 (+22%) | 15.55 (+18%) | 20.61 (+12%) | 28.18 (+9%)
Nash vs. Hier | 4.47 (-18%) | 10.86 (-17%) | 16.26 (-12%) | 23.05 (-10%)

One of the causes for the sub-optimal performance of the hierarchical approach
comes from the information loss, when the agents make decisions based on the
superstates. To better illustrate this point, we present two trajectories in
Fig. 9. The trajectories are truncated from the 4$\times$4 grid world, with
the four rooms corresponds to the the rooms in orange in Fig. 7. The right
subplot presents a trajectory of a Nash Pursuer against a Nash Evader. The
Nash Pursuer utilizes its speed advantage and captures the Evader with seven
steps.

Figure 9: A comparison of sample trajectories: left is Hierarchical Pursuer
vs. Nash Evader, and right is Nash Pursuer vs. Nash Evader. With the same
starting state, the hierarchical Pursuer takes thirteen steps to capture the
Nash Evader, while the Nash Pursuer only takes seven steps.

The left subplot in Fig. 9 presents the trajectory of a hierarchical Pursuer
against a Nash Evader. At timestep 3 (highlighted with stripes), given the
speed advantage, the Pursuer should directly chase down the Evader through
Room-B. However, at that moment, the hierarchical pursuer is still playing the
aggregated game. Based only on the room information, the Pursuer does not know
the exact location of the Evader within room-D (light orange area).
Furthermore, if the Evader is at the bottom part of room-D, it could easily
escape to one of the other rooms. Consequently, the Pursuer follows the sub-
optimal route down to Room-C and then come to Room-D to defend. Such behavior
is inevitable owing to the abstraction.

Another cause for the loss of performance comes from the less frequent
decision update in the hierarchical policy. While the Nash agent updates its
‘where-to-go’ decision every timestep, the hierarchical agent updates its
‘which-room-to-go’ decision only when the options terminate. Consequently, the
hierarchical agents are less responsive than the flat Nash agents.

Finally, we present the impact the aggregation size has on the algorithm.
Instead of having one room as one individual superstate, we have a
$K$$\times$$K$ block of rooms as a single individual superstate. An example of
such multi-room aggregation for the 6$\times$6 grid world is presented in Fig.
10. The performance for different aggregation size is presented in Table III.
Note that when all rooms coalesce into a single superstate, then the original
game is recovered as a single local game, and we recover the same performance
as the flat Nash policy. On the other extreme not presented here, where a
single state is treated as a superstate, we can recover the original game as
the aggregated game, under some additional conditions.

Figure 10: Different aggregation sizes. Each blue block is an individual superstate. From left to right: 1$\times$1, 2$\times$2, 3$\times$3 and 6$\times$6 room-blocks. TABLE III: Performance with Different Aggregations | each individual superstate contains
---|---
P vs. E | 1 room | 4 rooms | 9 rooms | 36 rooms
Nash vs. Nash | 25.85 | 25.85 | 25.85 | 25.85
Hier vs. Nash | 28.18 (+9%) | 28.79 (+11%) | 30.54 (+18%) | 25.79
Nash vs. Hier | 23.05 (-10%) | 21.55 (-16%) | 17.43 (-32%) | 25.82

When each superstate contains more states, the corresponding local games would
contain a larger region of the state space and the resulting hierarchical
agents are better informed in the local PEG. However, a larger superstate also
leads to a lower resolution for the aggregated game, and the hierarchical
agents ignore more information regarding the opponent’s position when
selecting options; this would result in a degraded performance due to playing
an aggregated game. The trade-off between the performance of the local games
and the aggregated game is not observed in this example. Future work will
further investigate this trade-off.

##  VI Conclusion

In this work, we proposed a hierarchical framework to decompose a large
pursuit-evasion game in a grid world. The proposed approach constructs a two-
resolution decision making process, which consists of a set of local PEGs at
the original state level and an aggregated PEG at the superstate level. For
the local PEGs, the agents restrict their attention within a superstate, while
in the aggregated PEG, the agents utilize options to navigate among the
superstates. With this hierarchy, the decomposed PEGs have much smaller state
spaces and can be easily solved to Nash equilibria. Through numerical
simulations, we showed that the proposed approach significantly reduced the
computation overhead compared to the non-hierarchical approach, while still
maintaining a good level of performance. Future work will extend this
framework to games with more than two players. It is also of interest to
investigate the theoretical bounds for the sub-optimality induced by the
hierarchical decomposition.

## References

  * [1] Y. Ho, A. Bryson, and S. Baron, “Differential games and optimal pursuit-evasion strategies,” _IEEE Transactions on Automatic Control_ , vol. 10, no. 4, pp. 385–389, 1965.
  * [2] R. Isaacs, _Differential Games_. John Wiley and Sons, 1965.
  * [3] T. Başar, _Dynamic Noncooperative Game Theory_. SIAM, 1998.
  * [4] R. Vidal, O. Shakernia, H. J. Kim, D. H. Shim, and S. Sastry, “Probabilistic pursuit-evasion games: theory, implementation, and experimental evaluation,” _IEEE Transactions on Robotics and Automation_ , vol. 18, no. 5, pp. 662–669, 2002.
  * [5] D. W. Oyler, P. T. Kabamba, and A. R. Girard, “Pursuit–evasion games in the presence of obstacles,” _Automatica_ , vol. 65, pp. 1–11, 2016.
  * [6] H. J. Kushner and P. G. Dupuis, _Numerical Methods for Stochastic Control Problems in Continuous Time_. Springer Science & Business Media, 2001, vol. 24.
  * [7] Y. Guan, D. Maity, C. M. Kroninger, and P. Tsiotras, “Bounded-rational pursuit-evasion games,” in _American Control Conference_ , New Orleans, LA, May, 25–28, 2021, pp. 3216–3221.
  * [8] J. Filar and K. Vrieze, _Competitive Markov Decision Processes_. Springer, 2012.
  * [9] D. Bertsimas and J. N. Tsitsiklis, _Introduction to Linear Optimization_. Athena Scientific Belmont, MA, 1997, vol. 6.
  * [10] T. G. Dietterich, “Hierarchical reinforcement learning with the MaxQ value function decomposition,” _Journal of Artificial Intelligence Research_ , vol. 13, pp. 227–303, 2000.
  * [11] A. Levy, G. Konidaris, R. Platt, and K. Saenko, “Learning multi-level hierarchies with hindsight,” _arXiv preprint arXiv:1712.00948_ , 2017.
  * [12] R. S. Sutton, D. Precup, and S. Singh, “Between MDPs and semi-MDPs: A framework for temporal abstraction in reinforcement learning,” _Artificial Intelligence_ , vol. 112, no. 1-2, pp. 181–211, 1999.
  * [13] M. Ghavamzadeh, S. Mahadevan, and R. Makar, “Hierarchical multi-agent reinforcement learning,” _Autonomous Agents and Multi-Agent Systems_ , vol. 13, no. 2, pp. 197–229, 2006.
  * [14] J. Yang, I. Borovikov, and H. Zha, “Hierarchical cooperative multi-agent reinforcement learning with skill discovery,” _arXiv preprint arXiv:1912.03558_ , 2019.
  * [15] R. Makar, S. Mahadevan, and M. Ghavamzadeh, “Hierarchical multi-agent reinforcement learning,” in _Proceedings of the Fifth International Conference on Autonomous Agents_ , 2001, pp. 246–253.
  * [16] T. Dean and S.-H. Lin, “Decomposition techniques for planning in stochastic domains,” in _IJCAI_ , vol. 2. Citeseer, 1995, p. 3.

##  Appendix A Discounted Multi-step Transition Probabilities

Suppose the joint system is currently in joint superstate $\gamma$, and the
agents apply a joint option $o=(o^{1},o^{2})$, the Q-function under the joint
options is given by

$\mathcal{Q}(\gamma,o^{1},o^{2})=\mathcal{R}(\gamma,o^{1},o^{2})+\sum_{\gamma^{\prime}\in\Gamma}\sum_{\tau=1}^{\infty}\widetilde{\mathcal{T}}(\gamma^{\prime},\tau|\gamma,o^{1},o^{2})\beta^{\tau}\mathcal{V}^{*}(\gamma^{\prime}),$

where $\widetilde{\mathcal{T}}(\gamma^{\prime},\tau|\gamma,o^{1},o^{2})$ is
the probability of transitioning from $\gamma$ directly to $\gamma^{\prime}$
right after $\tau$ timesteps. In other words, $\tau$ is the timestep the joint
process leaves $\gamma$ for the first time. The discount term $\beta^{\tau}$
is introduced to address the different timescale on which the aggregated game
operates. With the discounted multi-step transition probability

$\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime}|\gamma,o)=\sum_{\tau=1}^{\infty}\beta^{\tau}\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime},\tau|\gamma,o),$
(7)

we can compactly write the Q-function as

$\vspace{-1pt}\mathcal{Q}(\gamma,o)=\mathcal{R}(\gamma,o)+\sum_{\gamma^{\prime}\in\Gamma}\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime}|\gamma,o)\mathcal{V}^{*}(\gamma^{\prime}).$
(8)

Note that the discount factor is absorbed in
$\widetilde{\mathcal{T}}^{\beta}$, and therefore the discount factor is no
longer explicitly presented in (8).

Since we do not know how the agents approach the superstate $\gamma$, we
assume that the agents start with a uniform distribution on the boundary of
$\gamma$ (the entry points) and compute the $\tau$-step transition among
superstates as

$\widetilde{\mathcal{T}}(\gamma^{\prime},\tau|\gamma,o)=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\widetilde{\mathcal{T}}(\gamma^{\prime},\tau|s,o),$

where $\mathcal{T}(\gamma^{\prime},\tau|s,o)$ is the probability of the system
directly reaching joint superstate $\gamma^{\prime}$ at time $\tau$ starting
from joint state $s$. This probability can be computed as

$\mathcal{T}(\gamma^{\prime},\tau|s,o)=\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau|s,o),$

where $\tau$ is the timestep the joint system leaves $\gamma$ for the first
time. Now, we can re-write the multi-step transition in (7) as

$\displaystyle\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime}|\gamma,o)$
$\displaystyle=\sum_{\tau=1}^{\infty}\beta^{\tau}\widetilde{\mathcal{T}}(\gamma^{\prime},\tau|\gamma,o)$
$\displaystyle=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{\tau=1}^{\infty}\beta^{\tau}\sum_{s\in\mathrm{Bndry}(\gamma)}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau|s,o)$
$\displaystyle=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\sum_{\tau=1}^{\infty}\beta^{\tau}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau|s,o)$
$\displaystyle=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\phi(\gamma^{\prime}|s,o).$

We further examine the term $\phi(\gamma^{\prime}|s,o)$, which represents the
discounted multi-step transition starting from joint state $s$ to joint
superstate $\gamma^{\prime}$ under joint option $o$.

$\displaystyle\phi(\gamma^{\prime}|s,o)$
$\displaystyle=\sum_{\tau=1}^{\infty}\beta^{\tau}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau|s,o)$
$\displaystyle=\beta\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,o)+\sum_{\tau=2}^{\infty}\beta^{\tau}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau|s,o)$
(9a)
$\displaystyle=\beta\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,o)+\sum_{\tau=2}^{\infty}\beta^{\tau}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\sum_{\hat{s}\in\gamma}\mathcal{T}(\hat{s}|s,o)\mathcal{T}(s^{\prime},\tau-1|\hat{s},o)$
(9b)
$\displaystyle=\beta\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,o)+\beta\sum_{\hat{s}\in\gamma}\mathcal{T}(\hat{s}|s,o)\left(\sum_{\tau=2}^{\infty}\beta^{\tau-1}\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime},\tau-1|\hat{s},o)\right)$
$\displaystyle=\beta\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,o)+\beta\sum_{\hat{s}\in\gamma}\mathcal{T}(\hat{s}|s,o)\phi(\gamma^{\prime}|\hat{s},o).$

For the step from (9a) to (9b), we used the fact that $\tau$ is the first time
that the joint process leaves the superstate $\gamma$. Consequently, if
$\tau\geq 2$, the state $\hat{s}$ at the timestep $1$ needs to be within
superstate $\gamma$. Otherwise, the process has either already reached the
target $\gamma^{\prime}$ or has leaved $\gamma$ and reached superstates other
than $\gamma^{\prime}$. The rest of the derivations are simple algebraic
manipulations.

In summary, we can compute the discounted multi-step transition probability
starting from joint state $s$ to joint superstate $\gamma^{\prime}$ under
joint option $o$ as the fixed point of

$\phi(\gamma^{\prime}|s,o)=\beta\sum_{s^{\prime}\in\mathrm{Peri}(\gamma)\cap\gamma^{\prime}}\mathcal{T}(s^{\prime}|s,o)+\beta\sum_{\hat{s}\in\gamma}\mathcal{T}(\hat{s}|s,o)\phi(\gamma^{\prime}|\hat{s},o).$

The above iteration is similar to the value iteration of MDPs. Subsequently,
with $\beta\in(0,1)$, one can easily show that the fixed point iteration above
is guaranteed to converge to a unique fixed point.

Finally, the superstate-wise multi-step transition can be computed as

$\widetilde{\mathcal{T}}^{\beta}(\gamma^{\prime}|\gamma,o)=\frac{1}{|\mathrm{Bndry}(\gamma)|}\sum_{s\in\mathrm{Bndry}(\gamma)}\phi(\gamma^{\prime}|s,o).$


# Multimodal Search on Iconclass using Vision-Language Pre-Trained Models

Cristian Santini<EMAIL_ADDRESS>0000-0001-7363-6737 FIZ
KarlsruheGermany Institute AIFB, Karlsruhe Institute of TechnologyGermany ,
Etienne Posthumus<EMAIL_ADDRESS>FIZ
KarlsruheGermany ,  Tabea Tietz<EMAIL_ADDRESS>FIZ
KarlsruheGermany Institute AIFB, Karlsruhe Institute of TechnologyGermany ,
Mary Ann Tan<EMAIL_ADDRESS>FIZ KarlsruheGermany Institute AIFB,
Karlsruhe Institute of TechnologyGermany ,  Oleksandra Bruns
<EMAIL_ADDRESS>FIZ KarlsruheGermany Institute AIFB,
Karlsruhe Institute of TechnologyGermany and  Harald Sack  harald.sack@fiz-
karlsruhe.de 0000-0001-7363-6737 FIZ KarlsruheGermany Institute AIFB,
Karlsruhe Institute of TechnologyGermany

(2023)

###### Abstract.

Terminology sources, such as controlled vocabularies, thesauri and
classification systems, play a key role in digitizing cultural heritage.
However, Information Retrieval (IR) systems that allow to query and explore
these lexical resources often lack an adequate representation of the semantics
behind the user’s search, which can be conveyed through multiple expression
modalities (e.g., images, keywords or textual descriptions). This paper
presents the implementation of a new search engine for one of the most widely
used iconography classification system, Iconclass. The novelty of this system
is the use of a pre-trained vision-language model, namely CLIP, to retrieve
and explore Iconclass concepts using visual or textual queries.

art history, classification systems, information retrieval, multimodal search,
vision-language models

††copyright: acmcopyright††journalyear: 2023††submissionid: 123-A56-BU3††ccs:
Information systems Novelty in information retrieval††ccs: Information systems
Digital libraries and archives

##  1\. Introduction

Classification systems and other terminology sources, such as controlled
vocabularies and thesauri, play a key role in the digital curation of cultural
heritage objects. These lexical resources, are used by Galleries, Libraries,
Archives and Museums (GLAM) to describe items in their collection; the Getty
Vocabularies 111https://www.getty.edu/research/tools/vocabularies/ (Harpring,
2010) or the Social History and Industrial Classification (SHIC)
system222https://www.shcg.org.uk/About-SHIC are some examples in the GLAM
domain. Iconclass333www.iconclass.org (Waal, 1968) is the _de facto_ standard
for the classification of artistic representations and images. It is organized
as a hierarchy which comprises 10 main categories, or notations, (abstract and
non-representational art, religion and magic, etc.) and each category has
several narrower terms as descendants in a tree-like structure. Notations in
Iconclass are used to describe and index artworks based on their depicted
objects (animals, deities, etc.) or artistic themes (biblical, mythological,
etc.). Each notation is associated with a text which provides a label to the
notation.

Currently, some limitations affect the accessibility of the digital platforms
through which many controlled vocabularies, thesauri and classification
systems are published. Specifically, the adoption of Information Retrieval
(IR) techniques based on word occurrence, e.g. Term Frequency-Inverse Document
Frequency (TF-IDF) or set theory, e.g. Boolean search, to retrieve entries in
these lexical resources may create usability issues for non-expert users which
are not familiar with the terminology of iconography in the Western arts. In
order to solve this problem, word embeddings can be used to mitigate the
aforementioned limitation, since they are able to encode word meanings into
low-dimensional vectors, which alleviates the need for exact term matches.

The main contribution of this work is the implementation of a multimodal
search engine for Iconclass. This system is designed to leverage a vision-
language model, i.e. OpenAI’s CLIP (Radford et al., 2021), and a visual
similarity search (Posthumus and Sack, 2022), to retrieve Iconclass concepts,
or notations, based on either text or image inputs from the user. Section 2 of
this work discusses the adapted pre-trained Vision-Language model and the
implemented search system, Section 3 contains results from a small preference-
based survey conducted among Iconclass users of varying art historical
background and Section 4 concludes the paper.

##  2\. Multimodal IR in Iconclass

Following the development of deep learning architectures trained on a single
expression modality, which might consists either of texts, images, video,
audio or graphs, researchers have recently investigated the potentials of
training neural models on emerging patterns which can be expressed across
multiple modalities, e.g. with both visual and textual features. CLIP
(_Contrastive Language-Image Pre-training_) (Radford et al., 2021) follows
this intuition. Trained on a dataset of 400M (image-caption) pairs collected
from the internet, CLIP, given an image, must predict which out of a set of
32,768 randomly sampled text snippets it was paired with in the dataset. The
main idea behind this model is to use two different encoders, one for images
and one for texts, and by formulating the learning objective as a contrastive
loss, the model is able to align text and images into a shared embedding space
to learn diverse visual concepts.

The new multimodal search system in Iconclass takes advantage of the
aforementioned vision-language model to find appropriate Iconclass notations
given a text or image as input. The system consists of a database of
$\approx$500K images of artworks and photographs, hereinafter referred to as
_Images-DB_ , and a Faiss index (Johnson et al., 2017) of 2GB which stores the
embeddings of the images from the aforementioned database, retrieved from the
pre-trained CLIP model of (Radford et al., 2021). Images-DB collects 531,172
images described with Iconclass notations, which were kindly provided by the
Arkyves initiative444www.arkyves.org. The database contains 2,526,145
Iconclass notations, of which 90,347 were unique.

For visual search, the text or image initially given by the user as input is
encoded into a multidimensional vector by using either the text or image
encoder of CLIP. The obtained embedding is then used as seed for a similarity
search on the Faiss index, which returns the top-K most similar annotated
images in _Images-DB_ , by using a k-nearest neighbor algorithm. The output of
the similarity search is then the set of similar images and the list of
notations used to describe them, sorted by the number of assigned images in
reversed order. A diagram of the underlying algorithm of the system is
presented in Figure 1.

Figure 1. Diagram of the system architecture.

It is important to note that a user does not directly query the complete
Iconclass hierarchy, but a set of annotated images. This represents a novelty
since it indirectly exploits the information contained in the annotation of
$\approx$500K samples in _Images-DB_ , which was carried by expert annotators.
This multimodal search aims to exploit semantic similarity between text and
images to retrieve, from a candidate set of images, potentially relevant
notations provided by human experts, which is a relevant feature for users
which are not well-versed in iconography. The new multimodal search engine was
made available on a public demo555https://github.com/ISE-
FIZKarlsruhe/iconclass/tree/main/multimodal.

##  3\. Preference-based Evaluation

Currently, Iconclass provides a TF-IDF based text search. Through a
preference-based survey, the proposed multimodal search engine (_System A_)
was compared to the current approach (_System B_). For objectivity, the users
were unaware of the system designation. 10 participants were gathered with a
public call for volunteers. Each respondent had to fill a spreadsheet
containing overall 10 artwork images and 25 query strings. Given a query
string, the top-10 results of system A and B were placed side-by-side. The
users were then asked to select their preferred results, and to specify the
reason for this preference: _Preciseness_ , the correctness of the returned
notations (with respect to the image), and _Exhaustiveness_ , the recall of
valid notations in the result list. Results from the survey are reported in
Table 1.

Overall, respondents did not express a marked preference for one system over
another. However, from the survey emerged that, when multimodal search was
preferred, it was mainly due to exhaustiveness of the results. This result may
derive from the fact that CLIP-based search does not aim to retrieve a single
_pinpoint_ notation but a range of Iconclass codes related to a visual
concept. For example, the query string _Street_ returns, when using multimodal
IR, Iconclass notations which describe not only this iconographic element
(25I141: street), but also some related elements which are likely to occur in
pictures of streets, such as humans (31D14: adult man) or animals (34B11:
dog). The same does not happen for TF-IDF.

|  Multimodal Search |  TF-IDF
---|---|---
#Preferences |  105 |  104
#Preciseness |  64 |  72
#Exhaustiveness |  30 |  17
Table 1. Results from preference-based survey aimed to compare visual-
similarity search and TF-IDF search for Iconclass.

##  4\. Discussion and Conclusion

This paper presents the new multimodal search engine of Iconclass. This system
leverages pre-trained vision-language embeddings and a database of human-
annotated images to return Iconclass notations based on either textual or
visual inputs. The multimodal search engine offers users the advantage to
query Iconclass with both images or free-text descriptions, which is a
relevant feature to image curators which are not accustomed to the underlying
vocabulary in Iconclass. However, the quality of CLIP-based results is still
to be adequately estimated by using objective ground-truths. As a consequence,
multimodal search can be exploited in order to complement search results from
TF-IDF, rather than be considered as an equivalent alternative. As future
work, the possibility to combine results coming from different search systems
for Iconclass, e.g. both from visual similarity and word similarity, can and
will be taken in consideration. Moreover, new features and services for
Iconclass users will be introduced, such as the publication of a SPARQL
endpoint to enable external web services to exploit the new similarity-based
search.

## References

  * (1)
  * Harpring (2010) Patricia Harpring. 2010\.  Development of the Getty Vocabularies: AAT, TGN, ULAN, and CONA.  _Art Documentation: Journal of the Art Libraries Society of North America_ 29, 1 (2010), 67–72.  https://www.jstor.org/stable/27949541 Publisher: [The University of Chicago Press, Art Libraries Society of North America].
  * Johnson et al. (2017) Jeff Johnson, Matthijs Douze, and Hervé Jégou. 2017\.  Billion-scale similarity search with GPUs.  https://doi.org/10.48550/arXiv.1702.08734 arXiv:1702.08734 [cs].
  * Posthumus and Sack (2022) Etienne Posthumus and Harald Sack. 2022.  The Art Historian’s Bicycle Becomes an E-Bike.  (2022).
  * Radford et al. (2021) Alec Radford, Jong Wook Kim, Chris Hallacy, Aditya Ramesh, Gabriel Goh, Sandhini Agarwal, Girish Sastry, Amanda Askell, Pamela Mishkin, Jack Clark, Gretchen Krueger, and Ilya Sutskever. 2021\.  Learning Transferable Visual Models From Natural Language Supervision.  https://doi.org/10.48550/arXiv.2103.00020 arXiv:2103.00020 [cs].
  * Waal (1968) H. van de Waal. 1968\.  _Decimal index of the art of the Low Countries; D.I.A.L_ (abridged ed. of the iconclass system ed.).  Rijksbureau voor Kunsthistorische Documentatie, The Hague.  OCLC: 27696.


# Andreev reflection spectroscopy on SnAs single crystals

Sandeep Howlader1 Nikhlesh Mehta1 M. M. Sharma2 V.P.S. Awana3 Goutam Sheet1
<EMAIL_ADDRESS>1Department of Physical Sciences, Indian Institute of
Science Education and Research Mohali, 81, Knowledge city, S.A.S. Nagar,
Manauli 140306, Punjab, India  2 Academy of Scientific & Innovative Research
(AcSIR), Ghaziabad-201002  3 CSIR- National Physical Laboratory, New
Delhi-110012

###### Abstract

Binary compounds of SnT family(T= As, Sb, Te, S, Se, P) exhibit novel
properties like superconductivity, topologically protected states etc. Some of
these compounds crystallize in NaCl type structure or in layered structure,
both of which are considered potentially important for high-
temperature/unconventional superconductivity. It was previously shown that
K-doped BaBiO3 with NaCl type structure exhibits superconducting state below
$\sim$ 30 K. SnAs has crystallographic configuration that is exactly similar
to K-doped BaBiO3 and this warrants for the investigation of superconductivity
in this material. Previously it was reported that SnAs exhibits weakly coupled
type I superconductivity with an energy gap of 0.7 meV. Recently, the
electronic bandstructure calculations has hinted to the existence of possible
topologically protected states in SnAs. This has motivated us to investigate
the superconducting nature of SnAs using point contact Andreev reflection
spectroscopy. Our investigation revealed that superconductivity in SnAs can be
well explained within the BCS framework in the weak coupling limit.

Recently, investigation of the electronic properties of binary compounds of
SnT family (T= As, Sb, Te, S, Se, P) has garnered a lot of attentionZhao ; Sun
; Kamitani ; Hsieh . These materials exhibit novel properties and are
considered as sister compounds of topological materials (e.g. topological
semimetals and topologcial crystalline insulators), while some were also found
to be superconductorsBezotosnyi . The SnT family of compounds are also
candidate materials for topological superconductivity. In the context of
superconductivity, In doped SnTe was found to host an unusual pairing
mechanismErickson ; Balakrishnan ; Novak . Among the members of this family of
materials, being host to anisotropic properties, the materials with NaCl-type
structure are most widely studiedHulliger ; Tutuncu ; Wang ; Tanaka1 ; Tanaka2
. Even though the NaCl-type structural compounds are not layered, due to
highly symmetric nature of NaCl-type SnT, it is possible that due to the
presence of a single crystallographically independent site for Sn, the typical
mixed valence state of Sn (Sn4+(5s0) and Sn2+(5s2)) becomes naturally
forbidden. This is quite similar to the case of BaBiO3 where upon doping with
Potassium a high temperature superconducting phase was obtainedCava ;
Mattheiss . Therefore it becomes highly probable that NaCl-type SnT materials
may exhibit high Tc superconductivity.

Tin arsenide(SnAs) is a material that belongs to the SnT family and
crystallizes in the NaCl-type structure. SnAs was first demonstrated to
exhibit superconductivity by Geller and Hull in 1964Geller . In 2014, Wang et.
al performed transport and heat capacity measurements in SnAs and reported
that SnAs exhibits weakly coupled type-I superconductivity ($\lambda=0.62$)
with a low transition temperature of 3.58 KWang1 . Additionally, instead of
being in a mixed valence state, Sn was found to exist in a single valence
state. Phonon dispersion curves and phonon DOS were studied thoeretically
which revealed that the As p-states hybridize strongly with Sn p-states at the
Fermi levelTutuncu1 . Moreover, DFT calculations revealed that spin-orbit
coupling does not have any significant effect on the bandstructure. However,
ARPES measurements revealed significant band splittingBezotosnyi  . More
recent investigation of electronic band structure and Density of States(DOS)
within the Density Functional Theory (DFT) posited the possibility of non-
trivial topology in SnAs bands. Furthermore, the band dispersion obtained for
SnAs were also found to closely resemble to that of SnTe, a topological
crystalline insulatorSharma . These calculations also revealed band inversion,
gapped states near the Fermi level and possible existence of topological
surface states. This makes SnAs a good system for studying possible
topological superconductivity. In this paper, we investigated the possibility
of unconventional superconductivity in SnAs by performing Andreev reflection
spectroscopy at low temperatures and under the presence of high magnetic
fields.

Figure 1:  Rietveld refined XRD pattern of synthesized SnAs crystal, right
inset is showing FC and ZFC measurements of SnAs and left inset is showing M-H
plot at 2K of synthesized SnAs crystalSharma .

The SnAs crystals used in this study were grown by following a two-step method
as described in our previous reportSharma . Phase purity of the synthesized
SnAs crystal was determined through XRD pattern. Rietveld refined XRD pattern
is shown in Fig.1. Quality of refinement is determined by $\chi^{2}$ (goodness
of fit parameter) value which is found to be 3.50. The synthesized SnAs
crystal has NaCl type cubic structure with Fm-3m space group symmetry. Sn and
As occupy (0,0,0) and (0.5,0.5,0.5) atomic position in SnAs crystal lattice.
The lattice parameters obtained by reitveild refinement are shown in Table
(1). No impurity peak is visible in XRD pattern, showing that the synthesized
crystal is phase pure. Magnetization measurements under field-cooled (FC) and
zero field-cooled (ZFC) protocols were performed in presence of 12Oe magnetic
field. Both of these measurements confirmed the presence of bulk
superconductivity in the form of diamagnetic transition at around 4K as shown
in right inset of Fig. 1. This diamagnetic signal seems to saturate near 3.8
K, showing a transition width of 0.2K. Magnetization vs applied Field (M-H)
plot at 2K is shown in left inset of Fig.1. This wide open M-H loop shows the
observed superconductivity in synthesized sample is type-II superconductivity.
All previous reports shows SnAs to be a type-I superconductor with a critical
field of 150Oe Bezotosnyi ; Wang . In this result M-H loop starts to deviate
from linearity from around 60 Oe and it closes at around 290 Oe. This result
shows the superconductivity in synthesized SnAs crystal to be type-II
superconductivity. This result is discussed in detail in our previous report
Sharma .

Sample | a(Å) | b(Å) | c(Å) | $\alpha$ | $\beta$ | $\gamma$
---|---|---|---|---|---|---
SnAs | 5.721(9) | 5.721(9) | 5.721(9) | 90 | 90 | 90
Table 1: Rietveld refined lattice parameters of SnAs Figure 2: a) Needle-anvil
technique of point contact formation (b) a differential conductance spectrum
obtained in the ballistic regime (c) Field dependence of dI/dV vs. V spectrum
along with BTK-simulated curves (d) $\Delta$ vs. H

The point contact Andreev reflection spectroscopy measurements were performed
in a liquid helium cryostat which is equipped with a variable temperature
insert(VTI) operational between 1.4 K and 300 K. The cryostat is also equipped
with a superconducting vector magnet(6T-1T-1T). A home-built probe which
utilizes the needle anvil method, was used to form point contacts at low
temperatures. Here, a mesoscopic point contact junction was formed by engaging
a silver(Ag) tip on the surface of SnAs crystal. Contacts where the diameter
were small yielded two peaks in dI/dV vs V spectra, symmetric about the zero
bias. These peaks are signature of Andreev reflection phenomenonDuif ; Sheet ;
Jansen . Andreev reflection process is observed in ballistic point contacts
between a normal metal and a superconductor that leads to a special type of
non-linearity in the I-V spectrum. For such point contacts, the non linearity
is directly probed in a dI/dV vs. V spectrum. Andreev reflection spectra are
analyzed via the Blonder, Tinkham, and Klapwijk(BTK) modelBTK ; Strijkers .
Here, the normal metal/superconductor (N/S) interface is modeled as a
$\delta$-function potential barrier and its strength is characterized by $Z$,
a dimensionless parameter. For elemental superconductors, the quasi-particle
life-time (represented by $\Gamma$) is very small. Andreev reflection spectra
obtained for mesoscopic interfaces for such superconductors can be fitted by
using just two fitting parameters, the barrier potential and the
superconducting energy gap ($\Delta$). For non-zero barrier potential ($Z>0$),
the differential conductance spectrum obtained for a ballistic contact
contains Andreev peaks at bias V = $\pm\Delta$/e.

Figure 3: a), (c) Magnetic field dependence of point contact spectra along
with BTK-simulated curves (b), (d) corresponding $\Delta$ vs. H plots.

In Fig. 2a we show a typical point-contact formed using the needle-anvil
method. The corresponding normalized dI/dV vs. V spectrum obtained for the
contact is shown in Fig 2b. The spectrum was fitted under the BTK formalism
and corresponding fitting parameters used are shown in the figure. It is
clearly seen that the spectrum is well-fitted in the range $\pm$ 2 mV.
Additionally, the spectrum also contains two dips in dI/dV at a higher bias
arising due to critical current dominated non-linearities in I-V. Differential
conductance spectra obtained for a purely ballistic contact can be fitted in
the entire range under the BTK formalism. However, additional features due to
non-linearities in I-V that arise due to factors related to scattering
mechanisms occuring within the contact cannot be fitted within the BTK theory
and leads to under-estimation of superconducting energy gap ($\Delta$). By
fitting the Andreev reflection spectra we estimate $\Delta$ to be $\sim$ 0.62
meV. This is in accordance with the results obtained by Bezotosnyi et
alBezotosnyi .

In order to gain further understanding of the superconducting phase, detailed
field and temperature dependent measurements were carried out. We applied
magnetic field along the axis of the point contact ($B||c$). The dI/dV spectra
evolved smoothly with applied magnetic field (shown in Fig. 2c). The critical
field for a superconducting point contact is the applied field strength for
which the peak-dip structure completely vanishes. For our case this happened
at 3 kG. All of the spectra were fitted according to the BTK formalism and
information regarding change of energy gap with field was extracted. The
spectra were normalized to the conductance at the highest bias value.
Additionally, with increasing magnetic field the critical current dip
structure was observed to shift inwards. We present the change in $\Delta$
with applied magnetic field in Fig. 2d where, the energy gap is seen to
decrease monotonically with applied field strength.

We also studied field dependent measurements on some of the other point
contacts, where critical current dominated effects were prominent. These
measurements are shown in Fig. 3. Both spectra were seen to evolve
monotonically with applied magnetic field. These spectra were also fitted
according to the BTK theory and were normalized to the conductance at highest
bias value. The estimated value of $\Delta$ for these contacts is lower than
the estimated value for spectra presented in Fig. 2b. This reduction is a
result of analysing a spectrum where critical current dominated features are
present. As we have mentioned before, such features lead to underestimation of
energy gap. The overall spectroscopic features for these point contacts
vanished at a critical field of 8 kG.

Figure 4: a), c) Temperature dependence of SnAs/Ag point contact spectra along
with BTK-simulated curves b),d) corresponding $\Delta$ vs. T with BCS
simulated curve.

We present the temperature dependent measurements in Fig. 4. Here, we show
temperature dependent data for point contacts where both, spectroscopic
signatures associated with Andreev reflection and critical current of point
contact, are present. The data is normalized to the conductance at the highest
bias value. As expected for superconductors, the spectra evolved smoothly with
increasing temperature and the overall spectroscopic features disappeared
above 4.2 K. Again, as in the case of field dependence, the spectroscopic
features appearing due to critical current (dips in dI/dV vs. V) shift towards
lower bias value. This indicates temperature dependent suppression of critical
current for the point contacts.

Superconducting energy gap and its variation with temperature was obtained by
fitting the data under the BTK framework. We have shown the temperature
variation of $\Delta$ in Fig. 4b and 4d. The dots represent the estimated
value of $\Delta$ from BTK fitting of experimental data and the solid line
represent the simulated curve following the BCS predictionGasperovic ; Bardeen
. Clearly the obtained variation of $\Delta$ with temperature follows the BCS
prediction. Furthermore, the value of $\Delta$ as determined by BTK simulation
provides the ratio $\Delta(0)/K_{B}T_{C}=1.78$ indicating that
superconductivity in SnAs can be explained by BCS theory in the weak coupling
limit. Additionally, we did not detect any features related to unconventional
nature of superconducting order parameter.

In conclusion, we have performed spectroscopic investigation of
superconductivity in NaCl crystallized SnAs single crystals. We have estimated
the superconducting energy gap to 0.62 meV. On the basis of detailed
temperature and field dependence of various point contacts on SnAs, and
corresponding BTK simulated curves, we conclude that superconductivity in SnAs
is well explained within the BCS framework. We have determined that the
critical temperature is 4.2 K and critical field is 8 kG. Based on our
spectroscopic investigation we conclude that SnAs is a conventional
superconductor.

G. S. would like to acknowledge financial support from Swarnajayanti
fellowship awarded by the Department of Science and Technology (DST), Govt. of
India (grant No. DST/SJF/PSA-01/2015-16).

## References

  * (1) L.-D. Zhao, S.-H. Lo, Y. Zhang, H. Sun, G. Tan, C. Uher, C. Wolverton, V. P. Dravid, and M. G. Kanatzidis, Nature, 508, 373 (2014).
  * (2) Y. Sun, Z. Zhong, T. Shirakawa, C. Franchini, D. Li, Y. Li, S. Yunoki, and X.-Q. Chen, Phys. Rev. B, 88, 235122 (2013).
  * (3) M. Kamitani, M. S. Bahramy, T. Nakajima, C. Terakura, D. Hashizume, T. Arima, and Y. Tokura, Phys. Rev. Lett., 119, 207001 (2017).
  * (4) T. H. Hsieh, H. Lin, J. Liu, W. Duan, A. Bansil, and L. Fu, Nat. Commun., 3, 982 (2012).
  * (5) P. I. Bezotosnyi, K. A. Dmitrieva, A. V. Sadakov, K. S. Pervakov, A. V. Muratov, A. S. Usoltsev, A. Yu. Tsvetkov, S. Yu. Gavrilkin, N. S. Pavlov, A. A. Slobodchikov, O. Yu. Vilkov, A. G. Rybkin, I. A. Nekrasov, and V. M. Pudalov, Phys. Rev. B, 100, 184514 (2019).
  * (6) A. S. Erickson, J. H. Chu, M. F. Toney, T. H. Geballe, and I. R. Fisher, Phys. Rev. B, 79, 024520 (2009).
  * (7) G. Balakrishnan, L. Bawden, S. Cavendish, and M. R. Lees, Phys. Rev. b, 87, 140502 (2013).
  * (8) M. Novak, S. Sasaki, M. Kriener, K. Segawa, and Y. Ando, Phys. Rev. B, 88, 140502 (2013).
  * (9) F. Hullinger and G. W. Hull, Solid State Commun., 8, 1379 (1970).
  * (10) H. M. Tutuncu, S. Bagci, G. P. Srivastava, and A. Akbulut, J. Phys.: Condens. Matter, 24, 455704 (2014).
  * (11) Z. Wang, J. Wang, Y. Zang, Q. Zhang, J.-A. Shi, T. Jiang, Y. Gong, C.-L. Song, S.-H. Ji, L.-L. Wang, L. Gu, K. He, W. Duan, X. Ma, X. Chen, and Q.-K. Xue, Adv. Mater., 27, 4150 (2015).
  * (12) Y. Tanaka, Z. Ren, T. Sato, K. Nakayama, S. Souma, T. Takahashi, K. Segawa, and Y. Ando, Nat. Phys., 8, 800 (2012).
  * (13) Y. Tanaka, T. Shoman, K. Nakayama, S. Souma, T. Sato, T. Takahashi, M. Novak, K. Segawa, and Y. Ando, Phys. Rev. B, 88, 235126 (2013).
  * (14) R. J. Cava, B. Batlogg, J. J. Krajewski, R. Farrow, L. W. Rupp Jr., A. E. White, K. Short, W. F. Peck, T. Kometani, Nature, 332, 814 (1988).
  * (15) L. F. Mattheiss, E. M. Gyorgy, D. W. Johnson Jr., Phys. Rev. B, 37, 3745 (1988).
  * (16) S. Geller and G. W. Hull, Phys. Rev. Lett., 13, 127 (1964).
  * (17) Yue Wang, Hikaru Sato, Yohitake Toda, Shigenori Ueda, Hidenori Hiramatsu and Hideo Hosono, Chem. Mater, 26, 24, 7209-7213 (2014).
  * (18) H. M. Tütüncü and G. P. Srivastava, Solid State Commun., 221, 24-27 (2015).
  * (19) P. V. Sreenivasa Reddy, V. Kanchana, T. E. Millichamp, G. Vaitheeswaran, and S. B. Dugdale, Physica B: Condens. Matter, 505, 33 (2017).
  * (20) G. B. Demishev, S. S. Kabalkina, T. N. Kolobyanina, T. I. Dyuzheva, and V. G. Losev, High Press. Res., 1, 325 (1989).
  * (21) M.M. Sharma, Prince Sharma, Ganesh Gurjar, S. Patnaik and V.P.S. Awana Solid State Communications, 340, 114531 (2021).
  * (22) A. M. Duif, A. G. M. Jansen and P. Wyder, Journal of Phys.: Condensed matter. 1, 20, 3157-3189 (1989).
  * (23) G. Sheet, S. Mukhopadhyay, P. Raychaudhuri, Phys. Rev. B, 69, 134507 (2004).
  * (24) A. G. M. Jansen, A. P. Van Gelder and P. Wyder, Journ. of Phys. C: Solid State Physics, 13, 33, 6073-6118 (1980).
  * (25) G. E. Blonder, M. Tinkham, and T. M. Klapwijk Phys. Rev. B, 25, 7 (1981).
  * (26) G. J. Strijkers, Y. Ji, F. Y. Yang, and C. L. Chien, Phys. Rev. B, 63, 104510 (2001).
  * (27) R . F. Gasperovic, B. N. Taylor, and R. E. Eck, Solid State Communication, 4, 59-63 (1966).
  * (28) J. Bardeen, L. N. Cooper, and J. R. Schrieffer, Phys. Rev., 108, 1157 (1957).