# A Deep Investigation of Deep IR Models

Liang Pang, Yanyan Lan, Jiafeng Guo, Jun Xu, Xueqi Cheng  CAS Key Lab of
Network Data Science and Technology, Institute of Computing Technology,
Chinese Academy of SciencesBeijing, China<EMAIL_ADDRESS>lanyanyan, guojiafeng, junxu<EMAIL_ADDRESS>
(2017)

###### Abstract.

The effective of information retrieval (IR) systems have become more important
than ever. Deep IR models have gained increasing attention for its ability to
automatically learning features from raw text; thus, many deep IR models have
been proposed recently. However, the learning process of these deep IR models
resemble a black box. Therefore, it is necessary to identify the difference
between automatically learned features by deep IR models and hand-crafted
features used in traditional learning to rank approaches. Furthermore, it is
valuable to investigate the differences between these deep IR models. This
paper aims to conduct a deep investigation on deep IR models. Specifically, we
conduct an extensive empirical study on two different datasets, including
Robust and LETOR4.0. We first compared the automatically learned features and
hand-crafted features on the respects of query term coverage, document length,
embeddings and robustness. It reveals a number of disadvantages compared with
hand-crafted features. Therefore, we establish guidelines for improving
existing deep IR models. Furthermore, we compare two different categories of
deep IR models, i.e. representation-focused models and interaction-focused
models. It is shown that two types of deep IR models focus on different
categories of words, including topic-related words and query-related words.

Deep Learning; Ranking; Text Matching; Information Retrieval

††copyright: rightsretained††doi: 10.475/123_4††isbn:
123-4567-24-567/08/06††journalyear: 2017††copyright:
rightsretained††conference: SIGIR 2017 Workshop on Neural Information
Retrieval (Neu-IR’17); ; August 7–11, 2017, Shinjuku, Tokyo, Japan††ccs:
Information systems Retrieval models and ranking

##  1\. Introduction

Relevance ranking is the core problem in information retrieval (IR) system,
which is to determine the relevance score for a document with respect to a
particular query. Traditional approaches to tackle this problem include
heuristic retrieval models and learning to rank approach. Heuristic retrieval
models, such as TF-IDF (Salton and McGill, 1986) and BM25 (Robertson and
Walker, 1994), propose to incorporate human knowledge on relevance into the
design of ranking function. Modern learning to rank approach currently turns
to apply machine learning techniques to the ranking function, which combines
different kinds of human knowledge (relevance features such as BM25 and
PageRank) and therefore has achieved great improvements on the ranking
performances (Liu, 2009). However, a successful learning to rank algorithm
usually relies on effective hand-crafted features for the learning process.
The feature engineering work is usually time consuming, incomplete and over-
specified, which largely hinder the further development of this approach (Guo
et al., 2016).

Deep IR models have gained increasing attention for its ability to
automatically learning features from raw text of query and document.
Therefore, many deep IR models have been proposed to solve relevance ranking
problem only considering the query and document textual data. As (Guo et al.,
2016) has mentioned, deep IR models can be categorized into two branches,
namely representation-focused models and interaction-focused models, depending
on the different structures. However, deep IR models are the end-to-end
system, the learning process of the deep IR models are still resemble a black
box. Thus, it is curious to us that the different between automatically
learned features by deep IR models and hand-crafted features used in
traditional learning to rank approaches, and the differences between these
deep IR models.

In this paper, we conduct a deep investigation on deep IR models under two
aspects. Firstly, we compare the automatically learned features with hand-
crafted features. Hand-crafted features, including TF-IDF, BM25 and other
traditional retrieval models, are combined human knowledge and proven to
follow some heuristic retrieval constrains (Fang et al., 2004). Incorporate
with these constrains, we check the properties of deep IR models, for example
query term coverage, document length and embedding affect the performance of
deep IR models. Additionally, We pick out bad cases from test dataset to
conduct error analysis. For each group of bad cases, we establish guidelines
for improving existing deep IR models. We also show that the robustness of
automatically features are stronger than hand-crafted features. Secondly, we
compare the differences between two kinds of deep IR models. By visualizing
the pooling words of these deep IR models, it is shown that representation-
focused models focus on topic-related words and interaction-focused models
focus on query-related words. A synthetic experiment further prove these
properties.

The rest of the paper is organized as follows. In Section 2, we introduce two
types of existing deep IR models. In Section 3, we introduce the datasets for
performance evaluation. Section 4 compares the differences between the
automatically learned features and the hand-crafted features and Section 5
compares the differences between two types of deep IR models. Section 6
concludes the paper.

##  2\. Existing Deep IR Model

The core problem of information retrieval is to determine the relevance score
for a document with respect to a particular query, which can be formalized as
the follows as indicated in (Hu et al., 2014) and (Pang et al., 2016). Given a
query $Q=\\{q_{1},\cdots,q_{m}\\}$ and a document
$D=\\{w_{1},\cdots,w_{n}\\}$, where $q_{i}$ and $w_{j}$ stand for the $i$-th
and $j$-th words in the query and document respectively, the degree of
relevance is usually measured as a score produced by a scoring function based
on the representations of the query and document:

(1) $match(Q,D)=F(\Phi(Q),\Phi(D)),$

where $\Phi$ is a function to map query/document to a vector, and $F$ is a
scoring function for modeling the interactions between them.

Deep IR models propose to automatically learn relevance features from raw text
data, i.e. $Q$ and $D$. Considering different structures, existing deep models
can be categorized into two kinds: representation-focused models and
interaction-focused models. The representation-focused models propose to focus
on the learning parameters of function $\Phi$, while interaction-focused
models put more efforts on learning parameters of function $F$.

###  2.1. Representation-Focused Models

Representation-focused models try to build a good representation for
query/document with a deep neural network, and then conduct matching between
two abstract representation vector. In this approach, $\Phi$ is a relatively
complex representation mapping function from text to vector, while $F$ is a
relatively simple matching function. For example, in DSSM (Huang et al.,
2013), $\Phi$ is a feed forward neural network with letter trigram
representation as the input, while $F$ is the cosine similarity function. In
CDSSM (Shen et al., 2014), $\Phi$ is a convolutional neural network (CNN) with
letter trigram representation as the input, while $F$ is the cosine similarity
function. In ARC-I (Hu et al., 2014), $\Phi$ is a CNN with word embeddings as
the input, while $F$ is a multi-layer perceptron (MLP). Without loss of
generality, all the model architectures of representation-focused models can
be viewed as a Siamese (symmetric) architecture over the text inputs, as shown
in Figure 1.

Figure 1. Representation-Focused Models

###  2.2. Interaction-Focused Models

Interaction-focused models first build the local interactions between query
and document, based on basic representations, and then use deep neural
networks to learn the complex interaction patterns for relevance. In this
approach, $\Phi$ is usually a simple mapping function to map query and
document to a sequence of words or word vectors, while $F$ is a complex deep
model with many learnable parameters. Typically, function $F$ can be
represented as the compound function of $H$, $G$ and $M$, i.e. $F=H\circ
G\circ M$, and the scoring function can be written as the following form:

(2) $match(Q,D)=H\circ G\circ M(\Phi(Q),\Phi(D)),$

where $M$ is a function used to obtain the local interactions between the
representation of $Q$ and $D$, $H$ is a deep neural network to obtain the
abstract interaction patterns, and $H$ is an aggregation function to obtain
the relevance score based on the interaction patterns.

For example, in DeepMatch (Lu and Li, 2013), $\Phi$ is an identical function
which maintains the representation of query/document as a sequences of words,
$M$ is a basic interaction function to output parallel texts, i.e. the set of
interacting pairs of words from $Q$ and $D$, $G$ is a feed forward neural
network constructed by a topic model over the parallel texts, and $H$ is a
logistic regression unit to summarize the decision to obtain the final
relevance score. In ARC-II (Hu et al., 2014), $\Phi$ is a mapping function to
map query/document to a sequence of word embeddings, $M$ is the 1-D
convolution operation over each patch of words from $Q$ and $D$, $G$ is a CNN,
and $H$ is an MLP. In MatchPyramid (Pang et al., 2016), $\Phi$ maps
query/document to a sequence of word vectors, $M$ is the similarity function
between each word pair from $Q$ and $D$ to output a word-level interaction
matrix, $G$ is a CNN, and $H$ is an MLP. In Match-SRNN, $\Phi$ is the same as
that in MatchPyramid, $M$ is a tensor operation to incorporate high
dimensional word level interactions, $G$ is a 2D-GRU, and $H$ is an MLP.
Without loss of generality, all the interaction focused models can be viewed
as a deep architecture over the local interaction matrix, as shown in Figure
2.

Figure 2. Interaction-Foused Models

##  3\. Dataset

In this section, we introduce two datasets used for model analysis, namely
Robust Dataset, LETOR 4.0 Dataset. The statistics of these datasets are shown
in Table 1. We can see that these datasets represent different sizes and
genres of heterogeneous text collections.

Table 1. Statistics on Robust and LETOR 4.0 . Dataset | #Query | #Doc | #Relevance
---|---|---|---
Robust | 250 | 12240 | 12881
LETOR 4.0 | 1501 | 57899 | 61480

###  3.1. Robust Dataset

Robust data is a small news dataset. Its topics are collected from TREC Robust
Track 2004. We made use of the title of each TREC topic in our experiments.
The retrieval experiments on this dataset are implemented using the Galago
Search Engine111http://www.lemurproject.org/galago.php. During indexing and
retrieval, both documents and query words are white-space tokenized, lower-
cased, and stemmed using the Krovetz stemmer. Stopword removal is performed on
query words during retrieval using the INQUERY stop list.

###  3.2. LETOR 4.0 Dataset

LETOR4.0 dataset (Qin et al., 2010) is a benchmark data for evaluating
learning to rank methods. This dataset is sampled from the .GOV2 corpus using
the TREC 2007 Million Query track queries. This dataset contains two subsets,
i.e. MQ2007 and MQ2008. In this paper, we use MQ2007 for evaluation because it
is much larger than MQ2008. MQ2007 contains 1692 queries and 65,323 documents,
which is much larger than Robust. Each query and document pair in this dataset
is represented as a vector using 46 different features. The separation of
training, validation and testing set are set to default. The reason to choose
LETOR4.0 beyond Robust lie in that: 1) the LETOR4.0 data is relatively large
(especially for the query number), therefore it is more appropriate for
training a deep learning model; 2) the features have already been extracted,
therefore it is convenient to conduct comparisons with learning to rank
baselines.

##  4\. Comparisons with Hand-crafted Features

Learning to rank approaches with hand-crafted features have achieved a great
success in information retrieval. In these hand-crafted features, BM25 and
language model are the strong baselines in information retrieval. It is mainly
because these traditional models satisfied several heuristic retrieval
constrains proposed by Fang et al. (Fang et al., 2004). These constrains
reveal importance properties in information retrieval. They are 1) Term
Frequency Constraints (TFC1 / TCF2); 2) Term Discrimination Constraint (TDC);
3) Length Normalization Constraints (LNC1 / LNC2); 4) TF-LENGTH Constraint
(TF-LNC). Empirical results show that when a constraint is not satisfied, it
often indicates non-optimality of the method.

In this section, our aim is to find out the differences between deep IR models
and hand-crafted features. Firstly, bad cases are categorized to identify the
weakness of deep IR models. Then we make use of heuristic retrieval constrains
to explain the disadvantages of the deep IR models, such as query term
coverage problem, document length problem and embedding semantic abuse
problem. Lastly, we point out that the advantage of the deep IR models is the
robustness of the automatically learnt features.

###  4.1. Performance Comparison

Before we conduct error analysis, we first overview the performance of two
kinds of deep IR models and two strong hand-crafted features, namely BM25 and
language model, shown in Table 2.

The experimental result shows that deep IR models perform worse than the hand-
crafted features, especially compared with BM25. Furthermore, we find that the
performance gap between deep IR models and hand-crafted features is large in
Robust dataset compared with LETOR 4.0 dataset. The main reason lays to the
small size of the dataset, which go against the data-driven mechanism in deep
learning. We reduce the performance gap by increasing the size of the dataset
in LETOR 4.0, and we believe that the larger dataset will result in better
performance, even better than the hand-crafted features.

Apart from the affection of dataset size, other heuristic problems are found
by conducting error analysis. We will demonstrate these heuristic problem in
the next section.

Table 2. Performance comparison of deep IR models and hand-crafted features on
Robust, LETOR 4.0. Robust
---
Model | NDCG@1 | NDCG@10 | P@1 | P@10 | MAP
BM25-Title | 0.563 | 0.445 | 0.563 | 0.402 | 0.255
LM.JM-Title | 0.560 | 0.443 | 0.560 | 0.400 | 0.253
Arc-I | 0.124 | 0.138 | 0.124 | 0.132 | 0.050
MatchPyramid | 0.364 | 0.242 | 0.364 | 0.240 | 0.164
LETOR 4.0
Model | NDCG@1 | NDCG@10 | P@1 | P@10 | MAP
BM25-Title | 0.358 | 0.414 | 0.427 | 0.366 | 0.450
LM.JM-Title | 0.300 | 0.374 | 0.359 | 0.329 | 0.421
Arc-I | 0.310 | 0.386 | 0.376 | 0.364 | 0.417
MatchPyramid | 0.362 | 0.409 | 0.428 | 0.371 | 0.434

###  4.2. Error Analysis

####  4.2.1. Query term coverage problem

With analyzing number of bad cases of deep IR model results, we find that in
the most of the cases, deep IR models are hard to satisfy the Term
Discrimination Constraint (TDC) (Fang et al., 2004). TDC ensures that given a
fixed number of occurrences of query terms, we favor a document that has more
occurrences of discriminative terms. However, for both Arc-I and MatchPyramid,
we never intentionally designed a network structure to distinguish two same
query terms matching from two discriminative query terms matching. Although,
it is possible for these two models to learn from data, the limitation is the
size of the dataset, which make it hard for deep IR models to learn TDC
without any prior information.

We pick out one example, shown in Figure 3, to demonstrate this issue. Here
the query is “tooth fairy museum”. In the left part of Figure 3, the document
only contains query terms “museum” and “fairy”, where term “fairy” occurs more
than 10 times. While in the right part of Figure 3, the document contains all
three query terms, but the total number of query terms is only 6 times. With
the constrain of TDC, a good IR model prefer to rank right side document
higher than left side. However, the deep IR models make the opposite decision.

Suggestions: In order to recover query term coverage problem we propose two
suggestions for representation-focused model and interaction-focused model
respectively. 1) For representation-focused models, an attention mechanism
turns to be a useful strategy to distinguish different query terms. 2) For
interaction-focused models, pooling across each query term rows in the
interaction matrix is helpful for considering different query terms
individually.

… library museum legend christmas fairy legend christmas fairy word fairy come
latin word fata meaning fate means fairy cousin classical fates believe
control fate destiny human race hope fairy associate christmas good … good men
germany christmas fairy legend tell … patter small feet coming hall room open
door fairy clad sparkle robe dance laugh singing splendid … ernestine queen
fairy came return lost gold ring love sight count otto soon ask fairy queen
bride … live happily years count otto fairy wife decided hunt forest near
castle count grew impatient … … dr samuel harris national museum dentistry
baltimore made possible generous support colgate palmolive children museum
virginia select nine children science museum host branch bristle … toothbrush
ancient babylonia st century tooth sticks made wild … proper space inspire
visitor make healthy snack choice computer driven essential toothbrush tooth
fairy tech savvy visitor option create virtual toothbrush learn evolutionary
time periods emphasize dimension timeline visitor take time innovate design
handcrafte toothbrush bench view vintage dental product poster find … Figure
3. Two documents related to query “tooth fairy museum”, the right document
cover one more query term than the left document, while the left document rank
high in the deep IR models.

####  4.2.2. Document length problem

Another type of errors relates to the general preprocessing of document length
limitation before feed it into the deep IR models. With the limitation of
memory and time, documents tailor to a maximum length. It always make sense in
paraphrase identification tasks and question answering tasks, which have the
similar text length. But in information retrieval tasks, documents have
variance length, ranging from 10 to 10,000 words. Directly cut off the
exceeded text leads to information loss and violates the Term Frequency
Constrain (TF1). TF1 claims that replacing one of the non-query term word to a
query term increases the relevance score. Therefore for a cut-offed document,
if the replacement occurs in the exceeded part, the relevance score keeps the
same in deep IR models.

For example, a document contains 5000 words in Figure 4, and the maximum
length of our model set to 500 words. Thus we find that in the view of deep IR
models, only few query terms “withdrawal” occur in the top 500 words of the
document. While, as the figure shown, the query terms “methadone” and “baby”
occur in the exceeded part of the document.

A more precision statistic of the last query term match position in a document
is shown in Figure 5. The red line represents the 500 words threshold, thus
about 40% of document loss the query term information because of the length
limitation of the document. So this special preprocess affect 40% of the
documents, which reflecting on the worse model performance.

Suggestions: For this situation, inspired by passage retrieval approaches,
document can be split into several short passages. Then deep IR models apply
on each ¡query, passage¿ pairs. Finally, the relevance score is the
aggregation of each ¡query, passage¿ local relevance scores.

Figure 4. An example document shows that the exceed part of a long document
has much query term matching information. Figure 5. The distribution of last
query term matching position.

####  4.2.3. Embedding semantic abuse problem

Different from using one hot word representation in the hand-craft features
such as BM25 and language model, recently most deep IR models adopt pre-
trained word embeddings as the word representation, except the letter-trigrams
used in DSSM and CDSSM. The advantage of adopting word embedding as the word
representation is to investigate semantic matching information into the model.
However, on the flip side, semantic matching brings too much noise matching
signals, which covers up the exact matching signals and dominates the final
matching score. Similar to the heuristic constrains proposed in (Fang et al.,
2004) which only consider exact matching signals, we append one constrain by
considering semantic matching signals, called Term Semantic Frequency
Constrain (TSFC).

TSFC: Let $q=\\{w\\}$ be a query with only one term $w$. Assume $|d1|=|d2|$
and $s(w,d1)=s(w,d2)$. If $c(w,d1)>c(w,d2)$, then $f(d1,q)>f(d2,q)$.

This constrain assumes that two documents have the same length, and the sum of
the semantic matching signals (including exact matching signals) are
equivalent, $s(w,d1)=s(w,d2)$. The larger number of the exact matching signals
$c(w,d)$, the higher relevance score $f(d,q)$.

Figure 6. An example illustrates the embedding semantic matching problem. The
first document contains exact matching signals, while the second document
contains much high semantic matching signals.

Take an instance in LETOR 4.0 Dataset as an example shown in Figure 6. The
given query term “noradrenaline” has a high similarity with so many medical
related words, such as “epinephrine”, “catecholamine” and “metabolism”. Thus
the sum of matching signals in the lower document is higher than that in the
upper document, even the lower document dose not has any exact matching signal
with query term “noradrenaline”. As the experiment shows that deep IR models
prefer the lower document, for the sake of the higher density matching
signals.

Suggestions: As TSFC shown that we need enlarge the gap between semantic
matching signals and exact matching signals. As the Figure 7 shows that for
interaction-focused models, we can define a proper similarity function between
words, so that the exact matching signals are larger than all semantic
matching signals, such as the similarity functions show in Figure 7(b) and
Figure 7(c).

(a) Dot Product

(b) Cosine

(c) Gaussian Kernel

Figure 7. Choose one word from the vocabulary and measure the similarity
between other words, we draw the histogram of three type of similarity
functions: dot product, cosine and gaussian kernel. The arrow point the
similarity between two identity word (the word we choose).

####  4.2.4. Feature Robustness

The robustness of the features can be interpreted as that when some of the
features are missing, how much it affects the model performance. The features
we take into consideration are the 46 dimensional features provided in LETOR
4.0 dataset and the last layer 20 dimensional outputs in the Arc-I and
MatchPyramid. Then we use a linear model to fit these 3 sets of features to
the final relevance labels. In this way, the learnt weights reflect the
importance of the features.

In order to visualize the robustness different between hand-crafted features,
Arc-I and MatchPyramid, we conduct experiments on the first fold of LETOR 4.0
dataset. After sufficient model training, we firstly sort features by its
importance (their corresponding weight). Then remove features one-by-one
following the order of the feature importance at each time. Finally, evaluate
the performance of the rest of the features. The Figure 8 illustrates the
procedure of the feature removing. Figure 8(a) shows the result of hand-
crafted features, as we can see that when we remove the first two features the
performance drops a lot to about 0.36. Figure 8(b-c) shows the results of
Arc-I and MatchPyramid, as we can see that even half of the feature have been
removed, the model performance affects a little. That is to say, deep IR
models automatically learnt features turn to be more robustness than the hand-
crafted features.

Figure 8. Left: 46 dimensional hand-crafted features; Middle: Arc-I last layer
20 dimensional features; Top: MatchPyramid last layer 20 dimensional features.

##  5\. Comparisons Among Deep IR Models

In this section, we investigate the differences between representation-focused
models and interaction-focused models based on information retrieval task.
Deep IR models lay into these two categories, such as DSSM, CDSSM and Arc-I
belong to representation-focused models, Arc-II and MatchPyramid belong to
interaction-focused models. We choose two classical models from each category,
Arc-I and MatchPyramid. In order to explorer their intrinsic differences, we
conduct our analysis on Robust dataset, LETOR 4.0 dataset and a simulated
dataset.

###  5.1. Performance Comparison

Table 3. Performance comparison of different deep IR models on Robust, LETOR
4.0. Robust
---
Model | NDCG@1 | NDCG@10 | P@1 | P@10 | MAP
DSSM | 0.122 | 0.137 | 0.122 | 0.135 | 0.048
CDSSM | 0.118 | 0.134 | 0.118 | 0.130 | 0.042
Arc-I | 0.124 | 0.138 | 0.124 | 0.132 | 0.050
Arc-II | 0.140 | 0.148 | 0.140 | 0.156 | 0.054
MatchPyramid | 0.364 | 0.242 | 0.364 | 0.240 | 0.164
LETOR 4.0
Model | NDCG@1 | NDCG@10 | P@1 | P@10 | MAP
DSSM | 0.290 | 0.371 | 0.345 | 0.352 | 0.409
CDSSM | 0.288 | 0.325 | 0.333 | 0.291 | 0.364
Arc-I | 0.310 | 0.386 | 0.376 | 0.364 | 0.417
Arc-II | 0.317 | 0.390 | 0.379 | 0.366 | 0.421
MatchPyramid | 0.362 | 0.409 | 0.428 | 0.371 | 0.434

The performance comparison results illustrate in Table. 3. After comparing
different models on different datasets, we can conclude as follow: 1)
interaction-focused models are performed better than representation-focused
models; 2) the gap between representation-focused models and interaction-
focused models on dataset Robust is larger than the gap on dataset LETOR 4.0.

It motives us to explore the differences between representation-focused models
and interaction-focused models.

###  5.2. Property Analysis

####  5.2.1. Text Representations

Text representations is a major task for representation-focused models, since
text representation is used to compress most valuable and distinguishable
information into one vector. In paraphrase identification task, two sentences
are symmetric and have similar length. However, in information retrieval,
query and document are totally different objects. Query is abstract and almost
every terms in it reflect a perspective of search intent. Thus, text
representation for a query need to keep all the query terms information in one
vector. On contrast, document is elaborate and relevant document just follow
two hypotheses in the literature (Robertson and Walker, 1994). The Verbosity
Hypothesis assumes that a long document is like a short document, covering a
similar scope but with more words; while the Scope Hypothesis assumes a long
document consists of a number of unrelated short documents concatenated
together. Thus, text representation for a document only need to contain the
important part of a document.

In order to analyze the information encoded in text representation, we
visualize the words at the max pooling position in Arc-I model.

As an example, in Figure 9, the query terms are “sante fe new mexico”, which
are listed in the first text box. The words selected by max pooling layer
based on convolution output feature maps, are listed in second text box, such
as “national” “part”. It is evident to see, all of the pooling words are not
the words appear in query terms. The reason of the above observation is that
the document and query text representations are extracted independently, thus
the relation of these two representations are weak. For document, most
informative words are extracted to composite the representation, which have
the same purpose with the topic models. Thus we assume that the pooling words
are related to the topic words in the topic models.

Figure 9. The Arc-I pooling words have relation to LDA topic words. Figure 10.
The overlap ratio of top pooling words in Arc-I with LDA topics top50 words
and query words.

To further check this assumption, we conduct comparison with topic model.
Without loss of generality, we choose the state-of-the-art, LDA model (Blei et
al., 2003) to generate topic words. LDA model is trained on the whole corpus,
with 50 topics and default parameters in package gensim (Řehůřek and Sojka,
2010). Then we collect top 50 words in each topic, totally 853 words (some
words lay in multiple topics). Meanwhile, we collect all pooling words using
the Arc-I model, and sort decreasing by the words frequency. The Figure 10
shows the distribution of the word overlap ratio between top pooling words and
the top 50 LDA topic words. From the results as we can see, 80% of top 500
pooling words come from the top 50 LDA topic words, for example in Figure 9,
“national” and “park” come from the topic 48 and “office” come from the topic
36. Additionally, we also measure the overlap ratio between top pooling words
and query words (green line in Figure 10). Contrast with LDA topic words, the
overlap ratio of query words is relative small, for example about 30% of top
500 pooling words come from the query terms.

With above observation, we can conclude that representation-focused models,
eg. Arc-I, generate topic related text representation as the topic model do.

Figure 11. The different pooling words, highlighted using bold font, in the
model of Arc-I and MatchPyramid.

####  5.2.2. Interaction Representations

Interaction-focused models aim to extract interaction representations on the
top of interaction matrix, which is constructed using word-by-word similarity.
In paraphrase identification, interaction representation can be interpreted as
a hierarchical matching signal composition process, as described in (Pang et
al., 2016). Firstly, word level matching signals can be composited to phrase
level matching signals, for example n-grams matching and n-terms matching.
Then, conduct several composition steps to achieve sentence level matching
signal. However, it differs a lot when we apply MatchPyramid in information
retrieval task. Query is too short to be treated as a sentence, for instance,
query “tooth fairy museum” only can be treated as a phrase or query
“guatemala” only has one word. So that hierarchical matching signal
composition reduces to word/phrase matching signals aggregation.

In order to understand what interaction-focused models have learnt, we analyze
the MatchPyramid model from the pooling words. Different from the Arc-I model,
given a query document pair, almost all pooling words of MatchPyramid come
from the query terms. Figure 11 shows the different words pooling by Arc-I and
MatchPyramid. In MatchPyramid, we use cosine similarity function to evaluate
words similarity, thus identical words in query and document achieve the
highest similarity value as 1. Then the following convolutional and pooling
operations have a high probability to pool out these words.

####  5.2.3. Synthetic Analysis

From the above discussion, we realize that presentation-focused models and
interaction-focused models capture different kinds of informations in IR task.
In order to distinguish the performance of text representations and
interaction representations, we introduce an additional synthetic dataset to
verify the ability of two kinds of deep IR models.

The synthetic dataset is constructed using two well-designed ground truth.

  1. (1)

Topic Match The relevance document contain a specific topic, where each topic
expresses as a sequential of words. For example, word sequence “neural
network” represent a topic, and any document contains this word sequence lays
into this topic, marked as relevance.

  2. (2)

Density Match The relevance degree of a document is proportional to the
density of query terms it contained. For example, the document contain 100
query terms is more relevant compare to the one contain 10 query terms.

The whole dataset contains 10,000 queries. In each query, words are randomly
sampled from a 2000 words vocabulary. Then, for each query we construct one
relevant document and four irrelevant documents. In each document, words are
randomly sampled from the same vocabulary with query. The length of query is
ranging from 2 to 8, while the length of the document is ranging from 300 to
700.

Arc-I and MatchPyramid are evaluated on these two dataset respectively, and
the results are shown in Figure 12. As we can see, the performance of
representation-focused model Arc-I and interaction-focused model MatchPyramid
is quite the opposite. The representation-focused model have ability to learn
topic information, while very little information about query terms density. On
the contrast, interaction-focused model is good at learning query terms
density information, but almost no topic information covered.

RandomArc-
IMatchPyramid$0$$0.2$$0.4$$0.6$$0.8$$1$$0.46$$0.71$$0.46$$0.46$$0.47$$0.98$MAPTopic
MatchDense Match Figure 12. Performance comparison of Random, Arc-I and
MatchPyramid on synthetic data.

##  6\. Conclusions and Future Work

As a conclusion, deep IR models still perform worse than hand-crafted
features. The possible reason is that under a limit size of dataset, hand-
crafted features, such as BM25, obey the heuristic retrieval constrains, while
deep IR models ignored. Apart from using larger dataset, we establish
guidelines to explicit using heuristic retrieval constrains, in order to
further improvement of deep IR models.

On comparing representation-focused models and interaction-focused models, we
can conclude that, 1) representation-focused models focus on learning good
text representation, which encode the topic related words in the final
representation; 2) interaction-focused models focus on learning good
interaction representation, which good at collecting the density of matching
signals. These interesting findings pave a way to better understand the
different deep IR models and demonstrate that for different applications we
need to choose different deep IR models.

## References

  * (1)
  * Blei et al. (2003) David M Blei, Andrew Y Ng, and Michael I Jordan. 2003\.  Latent dirichlet allocation.  Journal of machine Learning research 3, Jan (2003), 993–1022.
  * Fang et al. (2004) Hui Fang, Tao Tao, and ChengXiang Zhai. 2004.  A formal study of information retrieval heuristics. In Proceedings of the 27th annual international ACM SIGIR conference on Research and development in information retrieval. ACM, 49–56.
  * Guo et al. (2016) Jiafeng Guo, Yixing Fan, Qingyao Ai, and W Bruce Croft. 2016\.  A deep relevance matching model for ad-hoc retrieval. In CIKM. ACM, 55–64.
  * Hu et al. (2014) Baotian Hu, Zhengdong Lu, Hang Li, and Qingcai Chen. 2014\.  Convolutional neural network architectures for matching natural language sentences. In NIPS. 2042–2050.
  * Huang et al. (2013) Po-Sen Huang, Xiaodong He, Jianfeng Gao, Li Deng, Alex Acero, and Larry Heck. 2013\.  Learning deep structured semantic models for web search using clickthrough data. In CIKM. ACM, 2333–2338.
  * Liu (2009) Tie-Yan Liu. 2009\.  Learning to rank for information retrieval.  Foundations and Trends in Information Retrieval 3, 3 (2009), 225–331.
  * Lu and Li (2013) Zhengdong Lu and Hang Li. 2013.  A deep architecture for matching short texts. In Advances in Neural Information Processing Systems. 1367–1375.
  * Pang et al. (2016) Liang Pang, Yanyan Lan, Jiafeng Guo, Jun Xu, Shengxian Wan, and Xueqi Cheng. 2016\.  Text matching as image recognition. In AAAI. AAAI Press, 2793–2799.
  * Qin et al. (2010) Tao Qin, Tie-Yan Liu, Jun Xu, and Hang Li. 2010\.  LETOR: A benchmark collection for research on learning to rank for information retrieval.  Information Retrieval 13, 4 (2010), 346–374.
  * Řehůřek and Sojka (2010) Radim Řehůřek and Petr Sojka. 2010.  Software Framework for Topic Modelling with Large Corpora. In Proceedings of the LREC 2010 Workshop on New Challenges for NLP Frameworks. ELRA, Valletta, Malta, 45–50.  http://is.muni.cz/publication/884893/en.
  * Robertson and Walker (1994) Stephen E Robertson and Steve Walker. 1994.  Some simple effective approximations to the 2-poisson model for probabilistic weighted retrieval. In SIGIR. Springer-Verlag New York, Inc., 232–241.
  * Salton and McGill (1986) Gerard Salton and Michael J McGill. 1986.  Introduction to modern information retrieval.  (1986).
  * Shen et al. (2014) Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil. 2014.  Learning semantic representations using convolutional neural networks for web search. In WWW. International WWW Conferences Steering Committee, 373–374.


# Analysing Ultra-Wide Band Positioning for Geofencing in a Safety Assurance
Context

Victoria J. Hodge,  Richard Hawkins, James Hilder and  Ibrahim Habli
Department of Computer Science
University of York
York, UK
{victoria.hodge, richard.hawkins, james.hilder<EMAIL_ADDRESS>
Corresponding author: Dr Victoria Hodge, Department of Computer Science,
University of York, Heslington, York, UK. email<EMAIL_ADDRESS>
###### Abstract

There is a desire to move towards more flexible and automated factories. To
enable this, we need to assure the safety of these dynamic factories. This
safety assurance must be achieved in a manner that does not unnecessarily
constrain the systems and thus negate the benefits of flexibility and
automation. We previously developed a modular safety assurance approach, using
safety contracts, as a way to achieve this. In this case study we show how
this approach can be applied to Autonomous Guided Vehicles (AGV) operating as
part of a dynamic factory and why it is necessary. We empirically evaluate
commercial, indoor fog/edge localisation technology to provide geofencing for
hazardous areas in a laboratory. The experiments determine how factors such as
AGV speeds, tag transmission timings, control software and AGV capabilities
affect the ability of the AGV to stop outside the hazardous areas. We describe
how this approach could be used to create a safety case for the AGV operation.

_K_ eywords Safety assurance $\cdot$ geolocation $\cdot$ geofencing $\cdot$
dynamic factories $\cdot$ modular safety contracts

##  1 Introduction

As manufacturing becomes increasingly automated and requires increased
flexibility, there is a move to more dynamic factories. This necessitates
dynamic supply chain solutions where factories manufacture a broad range of
products using frequent reconfiguration of the factory layout to optimise
production, efficiency and costs. This dynamism brings particular challenges
when attempting to provide assurance for the safety of operation prior to
deployment.

Dynamic factory operations require increased digitisation to provide increased
flexibility and automation. The implementation of this often requires
extensive use of commercial off the shelf (COTS) systems and components, which
provide accessible and competitively priced capabilities, but often lack the
rigorous certification of components developed specifically for safety-related
tasks [1]. Dynamic factories are also inherently interconnected, adding to the
complexity of the safety analysis and assurance task. It is crucial that these
safety challenges are addressed, particularly for autonomous applications [2].
It is only if the safety of dynamic factories can be assured that they can be
fully embraced. It is also vital that safety assurance is achieved in a manner
that does not unnecessarily constrain the systems and thus negate the benefits
of flexibility and automation.

This paper analyses our approach to safety assurance for dynamic factories
using a case study. We aim to achieve a balance between safety assurance and
viability (cost and efficiency). For this. we consider factory operations that
use autonomous guided vehicles (AGV) to move products and components around in
an efficient manner. Unlike AGVs in traditional factories, the AGV operation
is not constrained to fixed routes, and cannot rely on a fixed infrastructure
or environment. In addition AGVs will often have to operate in collaborating
teams and in cooperation with humans. To assure factory safety, it must be
proven that AGVs can navigate safely by not colliding with other objects or
humans present in the factory and by keeping away from potentially changing
hazardous areas (danger zones). Geofencing is a commonly used location-based
approach which we analyse to control the risk in hazardous areas of a factory.
Factories are indoor environments so geofencing requires indoor localisation
capability such as through the use of Ultra-Wide Band (UWB) IoT technology.
Shule et al. [3] state that “ _UWB has the potential to become a standard
technology for relative positioning and ranging in multi-robot systems, having
been applied to a wide variety of scenarios in recent years_ ”.

We undertake an experimental evaluation in a laboratory setting using AGVs
that must not encroach into a danger zone. Our platform uses commercial
hardware for UWB geofencing and an AGV built from COTS hardware plus PC
software we developed to analyse the data and communicate with the AGV.
Commercial AGVs are expensive so using COTS hardware for the AGV is more
economically viable if AGVs are to be used more widely. It also allows us
extensive control and enables a more thorough analyses of a number of aspects
of AGVs and how they affect safety constraints.

Our main contributions are: we run a lab-based case study of AGV operations
making use of commercial IoT geofencing technology and relate our experimental
results to the specification of safety contracts. From these evaluations, we
consider a modular safety assurance approach for dynamic factories.

The rest of the paper is organised as follows: section 2 provides background
for our overall approach that we adopt to safety assurance of dynamic
factories. We introduce a scenario that is the subject of our experimental
study and describe the safety requirements that we derived in section 3.
Section 4 describes our experimental design and evaluates the results. Section
5 considers related indoor localisation work and section 6 details future
work.

##  2 Safety Assurance of Dynamic Factories

It is crucial that the safety risk associated with factory operations is
sufficiently analysed, controlled and monitored [1]. Many of the same
characteristics that make dynamic factories desirable from a technical
perspective also pose significant safety assurance challenges. Dynamic
factories are designed to be flexible and easily reconfigured. This makes
safety analysis, which is traditionally conducted prior to operation, a
challenge since the state of the system is hard to predict in advance [4].
Control in dynamic factories is also often widely distributed, with limited
centralised control. This can make the task of determining and enforcing
safety requirements more challenging. Compounding this, factory operators will
often have little control over the design and evolution of the commercial
systems and components that are used. This can significantly weaken safety
assurance due to a high degree of uncertainty about the actual performance or
behaviour of these commercial components.

Our approach to safety assurance is modular and based on the use of safety
contracts [5] between elements of the factory. The German automation
technology supplier ‘PILZ’ [6] places emphasis on the necessary modular
certification of the individual factory devices (PILZ uses the term Safety 4.0
to indicate modular safety solutions). Most of the literature however focuses
on dependability in general but without much focus on safety which is
challenging in dynamic environments [4].

###  2.1 Safety Cases for Dynamic Factories

In many safety-related domains, such as railways or nuclear, it is common
practice to develop an explicit safety case for systems. The safety case sets
out the argument as to why a system is considered safe to operate in a
particular environment, and provides evidence to support the argument (such as
results from analysis or testing) [7]. Safety cases are particularly used for
novel systems where there is limited established best practice for assuring
safety, where the explanation for why the system is safe must be clearly
communicated [8]. Given the novelty of dynamic factories, we propose that an
explicit safety case should be provided.

Making factories more dynamic often requires a shift from standalone systems
to edge or fog networks of devices and services performing, cooperatively, a
number of functionalities [9]. Creation of a safety case will therefore
generally need to be cooperative in the sense that a safety case for a dynamic
factory cannot be built by a single stakeholder or organisation. The supplier
organisations, (e.g. the supplier of a smart sensor used in the factory), have
the best knowledge of the properties and characteristics of their components
and should define a set of safety guarantees for different usages. However,
there is a limit to what the supplier organisation is able to provide out-of-
context from the particular factory or operation; remember that such
components are often general-purpose commercial products that may be used in
many different applications. The suppliers can provide assurance for the
component (e.g. through the use of UL/ CE certification [10]), but can say
little about the safety assurance of the factory operation as a whole as they
do not have the necessary knowledge. It is the responsibility therefore of the
system integrator to assess whether the overall safety of the system can be
demonstrated by the integration of the components. In particular, the
integrator must identify, through safety analysis, the hazards posed by
factory operation and determine how the components may contribute to hazards
(this could for example be done through considering deviations on the
functionality of the components and their interactions).

As a result of this delegation of safety responsibility to different
stakeholders, we determined that a modular safety case approach should be
adopted [11]. In a modular safety case, the overall safety case for the
dynamic factory is split into separate modules of argument and evidence
relating to different system components.

###  2.2 Safety Contracts

The safety case modules can be linked together using safety contracts in order
to create a coherent case for the overall system. Such a modular approach
requires that the safety contract for each component in the factory be
determined and explicitly defined. This contract defines the set of properties
that the component is able to assure and a definition of potential failure
behaviour of the component. In order to be usable as part of the integrated
safety case for the factory, we propose that each of the identified properties
should be defined with the following assume-guarantee reasoning form:

> _if{condition} then {component} shall provide {property} with confidence of
> {confidence}_

The _condition_ and _property_ represent, respectively, the assumptions and
guarantees of an assume-guarantee contract [12]. In particular the _condition_
and _confidence_ of this assume-guarantee contract specification is crucial to
our approach; for any component there exist limitations on the circumstances
under which its behaviour is guaranteed and these must be clearly understood
and specified. Understanding and expressing these limitations is particularly
important in systems that make use of COTS components, where the confidence
may be quite low. The conditions that affect a guarantee could be diverse,
depending on the nature of the guarantee and the component. Conditions may
relate to the state of the operating environmental, such as the effects of
lighting conditions on sensor performance. They may be conditions on other
system components, such as the availability of electrical power. Conditions
may also include operational constraints on the way a system or component is
installed or operated.

As an example, an assurance contract for a pressure sensor may include:

> _If temperature is greater than -20 ∘C then pressure sensor shall provide
> air pressure value with accuracy of 0.1% with confidence of 99%._

The construction of such a safety contract requires evidence for the accuracy
of the pressure sensor, for example evidence from testing of the sensors and
in-service data for the sensor performance in operation. The more evidence
that is available, the higher the confidence in that performance will be. This
evidence would be included as part of the safety case module for the pressure
sensor. The safety contract also reflects the knowledge that the sensor
providers have that the sensors do not perform as well at very low
temperatures. This places the limitation condition on temperature defined in
the contract. Using the safety contract, the integrator will be able to assess
whether a pressure sensor meeting this safety contract will be sufficient to
meet the safety requirements identified for the overall system.

In this paper we analyse the safety requirements for an experimental scenario
involving the use of geofencing technology in the operation of an AGV in a
factory. The results highlight the need for the development of a modular
safety case and help us determine the required safety contracts for key
elements of the system.

##  3 Factory AGV Geofencing Scenario

Our scenario considers a highly automated and flexible factory that includes
AGVs that move inventory and equipment around a factory. Due to the dynamic
reconfiguration that may occur in the factory, the AGVs cannot simply follow
fixed routes around the factory, but must instead be capable of planning their
own paths through the factory in order to fulfill their task. The AGVs must
determine the best path to safely perform a task without colliding with
objects in the factory environment (such as equipment, machinery, humans or
other AGVs), or entering restricted areas (such as areas of high human
occupancy). Achieving this requires sensing, perception and path planning
technology on the AGVs. There are three techniques that combine to achieve
this:

1\. Localisation: (see Hodge [13] and Zafari et al. [14] for surveys of
techniques). This harnesses the ubiquitous connectivity of Internet of Things
(IoT) to localize and position IoT devices (tags). This is suitable for
dynamic factories to set up safe areas with restricted access (geofencing),
e.g., areas under maintenance, where humans operate or where the AGV would be
unsafe, e.g. a spillage. It gives a global overview of the AGV and its
navigation environment but cannot locate obstacles or other collision points
(local view).

2\. Local motion planning: Using object detection/recognition [15]. This
requires AGV-mounted sensors such as IR proximity sensors, LIDAR, or cameras.
This navigation is suitable for detecting dense objects such as relocatable
machinery, boxes, other AGVs, vehicles. It generates a detailed and high
fidelity map of the AGV’s immediate surroundings. It provides a fine-grained
local view but not a global overview of the navigation so the AGV cannot avoid
danger zones or areas where humans are working.

3\. Global path planning: Generally uses a map which generates a fixed
overview and may require prior knowledge of the layout. It is ideal for large
and immovable objects. The map can be a) pre-defined and fixed such as a
floorplan or CAD drawing; or b) constructed by the AGV itself using SLAM “to
incrementally build a map of this environment while simultaneously using this
map to compute absolute vehicle location” [16]. This is more dynamic but is
slow and compute-intensive. In [15] we developed a mapless navigation
algorithm that uses only data from on-board sensors (local data) to navigate;
and analysed its safety.

A combined navigation approach would overcome the weaknesses in each technique
and achieve both a detailed local view and an overall view of the navigation.
It helps ensure no single point of failure. In [15] we developed and assured
global path planning. As a further step to achieving a combined approach, we
focus on ensuring the safety of 1) localisation using fog/edge geofencing to
create an overall view, to provide protection for areas of the factory where
humans work and stop AGV encroachment into danger zones. Geofenced areas can
be created and removed when needed (e.g. during emergency repairs or where
humans are working) and are more flexible than maps as comparing an AGV’s
location against a pre-defined map cannot cope with dynamic layout changes.
The geofencing can be used to provide an emergency stop capability for the
AGV.

Figure 1: Our scenario is 8m x 8m x 2.5m high with four geofencing anchors in
a square configuration (master anchor bottom right). The geofenced zone is the
danger zone (bottom right) plus 30cm buffer zone where the AGV stops.

The core requirements of the geofencing are:

  1. 1.

The AGV should STOP before entering the danger zone.

  2. 2.

If the AGV enters the danger zone, then it should be immediately stopped.

  3. 3.

The AGV should navigate away from the buffer zone.

  4. 4.

Accurate geolocation of tags placed on the AGV.

  5. 5.

The system should detect possible failures of hardware, software and comms and
ensure “Safe Failure”. If this affects an AGV then that AGV should stop. If it
affects all AGVs (network outage) then they should all stop.

Criteria 3 and 5 are not considered in our initial work here as they relate to
the AGV’s path-planning abilities rather than the geofencing. Fig. 1 shows a
schematic of our UWB geofenced laboratory where AGVs must not encroach into
the danger zone and must obey safety requirements.

###  3.1 Safety Requirements

By considering the hazards associated with the scenario described above the
following high-level safety requirements can be identified for the AGV system:

  * •

SR1 – AGV shall not plan a path that results in collision with an object in
the factory

  * •

SR2 – AGV shall stop before entering an unsafe zone (danger zone in Fig. 1) or
colliding with an object

SR1 says that when planning a path in order to achieve a task within the
factory (such as moving parts from one location to another) the AGV should
ensure that its path does not result in a collision. This can be achieved
using information from sensors and object detection to locate objects [15].
SR2 says that even if an unsafe path is planned, the AGV should not enter a
danger zone or collide with an object. This requirement can be considered as
an “emergency stop” or ”collision avoidance“ facility, which provides extra
safety assurance.

This second safety requirement is the focus in this paper. We focus on an
“emergency stop” with geofencing. This allows the AGV to avoid dangerous areas
that a sensor-based collision avoidance system would not be able to ‘see’.
Sensor-based collision avoidance is covered extensively in the literature,
e.g., [17]. We consider how geofencing implemented using a real-time indoor
location system (RTLS) can provide assurance against SR2. We analyse how
modular safety criteria can be developed. This entails determining safety
contracts for each of the components of the RTLS, and generating evidence to
support the satisfaction of the safety contracts. This involves the following
steps:

  * •

identifying the properties that can be guaranteed for the components

  * •

generating evidence to support these properties

  * •

understanding the conditions under which the properties hold

  * •

identifying failure conditions for the components

###  3.2 Geofencing Implementation

One emerging RF technology for accurate localisation is ultra-wideband (UWB)
ranging technology which uses tags and anchors for geolocation. We provide a
literature review of UWB geofencing in section 5. UWB devices transmit ultra
short-pulses over a large bandwidth ($>$500MHz), with frequency range between
3.1 and 10.6GHz, and a very low duty cycle. This reduces power consumption
[14]. UWB is robust to interference from other signals [18].

Our experimental setting is based on Sewio’s Indoor UWB RTLS Kit [19] for AGV
geofencing, analysed against our safety requirements, determining what factors
affect its ability to meet those requirements. It is widely used in industry,
can support up to 5000 tags and has a reported positioning accuracy of +-30cm
(98% of positions have an error $<$30 cm). Hulka et al. [20] found the Sewio
RTLS UWB tracking system accurate and reliable for tracking basketball
players. Contigiani et al. [21] compared the Sewio and Openrtls UWB tracking
systems and found similar positioning accuracy but Sewio had superior battery
life due to its energy saving. However, they found positioning accuracy
degraded when used in an occluded environment due to NLOS errors. Hence, we
evaluate NLOS tracking in section 4.2.

Our RTLS geofencing system has five modules 1) Tags mounted on the AGVs and
powered by rechargeable Li-Ion batteries. The tags transmit data packets
periodically over Decawave UWB radio to data receivers (anchors). The tags do
not communicate peer-to-peer. 2) Anchors mounted on brackets in fixed
positions (see Fig. 1) which are reference devices with a known position. One
anchor is designated the “main”. The system uses triangulation and the precise
measurement of time difference between a signal arriving from a tag (blink) to
a set of anchors to calculate the tag’s exact location. To ensure high
accuracy, the anchors need to be synchronized very precisely which is done
periodically from the master. 3) Location Engine software that collects the
tag and anchor data and calculates the absolute tag positions. 4) Safety
Controller. We developed this in Java using Sewio’s Java API [22] to calculate
the relative distance between tags and geofenced zones. If a tag encroaches
into a zone, the controller generates an “alert” and sends a “STOP” signal
(see section 4.1.2). Although we only analyse two AGVs here, having the
controller on a laptop (or laptops) connected to the main anchor via wi-fi
router allows us to generate an overall picture of a factory. This controls
the AGVs and factory safety and can also incorporate global maps and map-based
control. If we had a safety controller on each AGV then we would need to
update all AGV controllers every time there was a factory layout change and
would have difficulty controlling the AGVs as a group. 5) User Interface,
currently a simple command line interface that runs in conjunction with the
safety controller and is designed to display tag locations and geofenced zone
alerts.

##  4 Evaluating safety contracts for UWB Geofencing

From SR2 we know that our system described above must provide a stop command
to the AGV in sufficient time for it to stop before entering the danger zone.
In this section we describe experiments conducted to determine the nature of
the safety contract for our system by identifying the safety guarantees that
it is possible to make for the system, as well as the conditions under which
those guarantees hold.

###  4.1 Experiment Design

The purpose of our experiment is to determine if properties can be guaranteed
by the fog/edge UWB system in the defined scenario and to identify what
factors impact on the ability of the UWB system to provide these guarantees.
This will allow us to develop the safety contract for the UWB geofencing
system. We will also use to results of the experiment to understand the
dependencies on the UWB system components and their safety contracts.

####  4.1.1 UWB Indoor Geofencing System

As we are making our initial investigation of safety and developing safety
assurance, the entire real-time location system was implemented and evaluated
in the University of York Robotics Lab [23], a purpose-built research
facility.

Sewio provided detailed instructions on how to install the system correctly.
We ensured we followed these, placing the anchors in a square configuration
all around 2.5m off the ground to ensure consistent and reliable coverage,
using Sewio’s software and charts to optimise the signal strengths and
synchronisation stability between anchors. We ensured that the tags were at
least 15cm above the floor at all times (by placing them on a cardboard box on
top of our AGV) to ensure height compliance and to keep them away from metal
objects on the AGV which can cause interference. As stated earlier, Sewio tags
have a claimed positioning accuracy of +-30cm so we set the virtual stop line
30cm back from our physical stop line giving a buffer zone where the AGV
should stop (shown in Fig. 1) with 98% confidence.

In section 4.2, we analyse this setup for accuracy and latency. Sedlacek et
al. [24] found that Sewio tags had a median positioning error of 39.6cm at
various locations including those with diminished anchor coverage. The errors
varied with location. A tag placed in the centre of the coverage area had
median positioning error of 23.0cm but one near the corner with line-of-sight
of fewer anchors had median error of 73.8cm [24]. In our future work, we will
analyse varying the size of the buffer zone allocated to each AGV according to
that AGV’s specifications (velocity, size, tag transmission rate etc.). Here,
we focus on developing safety assurances so mandate that all AGVs have
identical setup so we can investigate what specifications ensure the AGV stops
in time (and what specifications cannot ensure the AGV stops) and thus what
guarantees we can make.

####  4.1.2 Safety Controller

We need to detect encroachments using the AGV tag’s location and issue a
safety alert to the AGV so it stops. For this, we used a MS Windows laptop
connected to the Sewio wi-fi network. It runs the Sewio VirtualBox VM image
[19] and provides a bridge between:
(tags+anchors) $\leftrightarrow$ (Cisco router) $\leftrightarrow$ (Java API in
the VM).

We setup one geofenced zone (as shown in Fig. 1) via Sewio’s software. Our
Java Safety Controller (section 3.2) analyses tag and geofence information
extracted using Sewio’s API [22]. It provides command-line alerts to the user
and issues “Stop” commands to the AGV if it encroaches. The communication from
laptop to the AGV uses plink [25] \- a command-line tool from MS Windows
(laptop) to Linux (AGV) that executes remote commands on the AGV via a non-
interactive _ssh_ session. This ensures minimal processing overhead and so we
can pinpoint delays more easily.

####  4.1.3  Control and Communication with AGV and Machine

Our evaluation used two purpose-built AGVs based upon the York Robotics Kit
hardware [26]; R1 controlled by a Raspberry Pi 3B+ and R2 controlled by a
Raspberry Pi 3A. They have different speeds of travel. R1 defaults to 0.093
m/s and R2 to 0.277 m/s, i.e., R2 is 3x faster than R1. This provides the
opportunity for evaluating different speeds and its effects. Using COTS AGVs
ensures we have total control over the AGVs (full software access). COTS AGVs
are also more accessible. Many commercial AGVs are out of the price range of
all but high-end factories. We aim to demonstrate that we can assure safety
across the range from COTS to high-end commercial AGVs. We start here by
analysing and ensuring the safety of COTS AGVs. The AGVs run York Robotics Lab
Python control software to control the motor speeds [27]. The Java Safety
Controller on the laptop uses plink to call the Python running under Linux on
the AGV. Each robot travels on a variety of (randomly chosen) trajectories
towards the protected zone to thoroughly analyse the stopping conditions as
shown by the blue dotted arrows in Fig. 1.

###  4.2 Experimental Results

To analyse the safety guarantees of the geofencing, we set the tags to default
settings: transmission every 100ms with medium signal strength to ensure
battery life without compromising signal quality. We ran 2 evaluations.

####  4.2.1 Non-Line-of-Sight (NLOS) test

We investigated NLOS detection by running R1 with a tag mounted on top into a
tunnel constructed from three (thick-walled) cardboard boxes. The tunnel was
39cm wide, 31cm high, 43 cm deep and placed straddling the virtual stop line.
While inside the tunnel, the tag functioned normally while the AGV travelled
through the tunnel and the AGV stopped in the same range (within the box plots
in Fig. 2) as when the AGV was not in the tunnel.

####  4.2.2 AGV Configurations test

Table 1: Table listing the AGV test configurations and whether the AGV stopped safely outside the danger zone. Tag transmits every $n$ milliseconds (Tag Period). $v$ is max speed of R2, $v/3$ is max speed of R1 (and R2 running at 1/3 speed). Server indicates if the Python data server was running. Rand indicates whether a random offset is added to the gaps between tag transmissions. Test ID | AGV | Tag Period | Speed | Server | Rand | Stopped?
---|---|---|---|---|---|---
T1 | R1 | 100 | v/3 | N | Y | yes
T2 | R2 | 100 | v | Y | Y | no
T3 | R2 | 100 | v/3 | Y | Y | no
T4 | R2 | 100 | v | N | Y | no
T5 | R2 | 100 | v/3 | N | Y | yes
T6 | R2 | 200 | v | N | Y | no
T7 | R2 | 200 | v/3 | N | Y | no
T8 | R2 | 200 | v | N | N | no
T9 | R2 | 200 | v/3 | N | N | no (once)

We drove the AGVs at the danger zone at a range of angles (see Fig. 1). The
AGV stops when the system detects an encroachment. We measured the distance
from the front of the tag to the front of the physical stop line (black dashed
line shown in Fig. 1), repeating this process 50 times (over a number of days)
for the nine AGV configurations given in Table 1. By varying the
configurations, we evaluate the following criteria:

  * •

AGV speed where $v$ is max speed of R2, $v/3$ is max speed of R1 (and is R2
running at 1/3 speed).

  * •

processor / RAM. R1’s Raspberry Pi has a Cortex-A53 (ARMv8) 64-bit @1.4GHz
with 1GB LPDDR2 SDRAM while R2 has the same CPU with 512MB LPDDR2 SDRAM. Both
run Linux (and Python).

  * •

effect of running processes - run a Python data server on the Raspberry Pi
that hogs the CPU periodically.

  * •

tag transmission period (in ms).

  * •

regularity of tag transmission.

We list if the AGV stops before the danger zone for each configuration in
Table 1 and create box and whisker plots for the AGVs’ stopping distances in
Fig. 2 (distance between tag and boundary of danger zone which should be
$>$0cm). The box and whisker plots show the median, inter-quartile range
(box), upper and lower extremes (whiskers) and outlier points (dots). To meet
the safety guarantee each box, whisker and dots should be above the y=0 line
in their entirety.

Figure 2: Box and Whisker Plots of the stopping distances (measured
perpendicularly from the stop line with a tape measure) for test
configurations (T1-T9) over 50 runs per configuration. 0cm is the danger zone.
+30cm is the virtual stop line to give a stopping buffer. 60cm is the outer
edge of the buffer. AGVs should stop before 0cm line on all runs.

###  4.3 Using Results to Define Safety Contracts for Geofencing System

From experiments we can identify the properties that can be guaranteeed by the
geofencing system along with the conditions under which those properties can
be guaranteed. In our case study, with relation to safety requirement SR2 (see
section 3.1), the property of concern for the safety contract is the stopping
distance. This requires the following guarantee: The AGV will stop no more
than 30 cm beyond the defined virtual stop line (giving a buffer zone). We
need to analyse the results of our case study to determine the factors that
guarantee this.

From the results in Table 1 and Fig. 2 we find that only T1 and T5 guaranteed
this result over 50 runs. Analysing further, with 99% confidence the
population mean stopping distance (assuming a population of 1M runs) is
between 31.3 and 42.2cm based on 50 samples for T1 (36.74 $\pm$ 5.46cm before
the danger zone), and with 99% confidence the population mean stopping
distance is between 31.1 and 38.4cm based on 50 samples for T5 (34.76 $\pm$
3.68cm before the danger zone). T1 uses AGV R1; and T5 uses R2 with the same
configuration as R1 had for T1. This provides a preliminary analysis of safety
guarantees for geolocation of AGVs. If we want a confidence level of $99\%\pm
1$ ($>$98%) then we need to analyse each configuration over 16369 runs to
provide true safety guarantees for a safety-critical task or environment.

Even over 50 runs, we can identify factors of the AGVs that would fail to
guarantee safety. T9 encroached once into the danger zone (the lower extreme
of the box and whisker is below the stop line in Fig. 2) but this fails the
safety guarantee nonetheless. With 99% confidence the population mean of T9 is
between 20.6 and 30.1cm, based on 50 samples - this fails SR2. All other test
configurations encroach multiple times. The variables that were seen to affect
these results were: AGV velocities, running processes on AGVs, tag
transmission periods (gaps) and tag transmission regularity. In particular,
having a server running on the AGV caused extreme outlier values in stopping
distances and large encroachments as did a combination of faster AGV speed and
slower tag transmission rates. Switching off random offset on the tag
transmission gap also caused large encroachments on the faster AGV. NLOS
operation did not affect the AGV stopping distance in our analyses though
other authors found that NLOS did adversely affect geolocation [21, 28]. These
observations allow us to identify the conditions for safety assurance and plan
our future work such as dynamic buffer zones (see section 6) related to AGV
velocity.

Based on our case study we can therefore identify the following conditions
upon which the guarantee relies:

  * •

AGV speed does not exceed 0.093 m/s

  * •

Control command software process has schedule priority on AGV Raspberry Pi

  * •

Tag transmission gap is at least 100 milliseconds

  * •

There is a random offset between tag transmissions

In fact, by considering geofencing as an end-to-end service, we can see that
it consists of a number of stages. Fig. 3 illustrates the stages required for
AGV control using geofencing. A safety contract could be specified for any of
these stages, defining the individual properties that can be guaranteed, and
the conditions under which they hold. This illustrates why a modular safety
approach is required; properties cannot be guaranteed for geofencing unless
properties of the individual components (wifi, comms, tags, anchors,
processors) can also be guaranteed. For example the tags must guarantee with
sufficient confidence that 100 millisecond transmission gaps can be provided.
The conditions that are required for this must be specified as part of the
contract for the tag. These conditions in turn must be demonstrated to hold.
Adopting a modular safety approach also supports changes to the system and the
configuration of the factory. The explicit safety contract for each system
element defines the bounds within which that element must perform. When
changes are made to any individual element, as long as the element can still
be shown to satisfy the safety contract, we know that the overall safety
requirement can still be met without the need to re-evaluate the whole system.
This would allow, for example, different tags with different performance to be
used, so long as the guarantees specified by the contract are still met.

Figure 3: Stages for geofencing control.

##  5 Related Geolocation Work

Other authors have analysed various aspects of UWB geolocation. Zandian and
Witkowski use similar performance analyses to ours but they built their own
UWB system rather than using a commercially available system [28]. Segura et
al. [29] also built a real-time AGV navigation system for indoor environments
using COTS components. We want to verify industry-standard UWB kit and can
incorporate industry standard AGVs as we develop our safety assurance
framework and safety-assured system. For the initial analyses here, it is much
easier to control, assess and verify our COTS AGVs. Ruiz and Granja [30]
compared three commercial UWB systems for accuracy in an experimental
evaluation and found a range of performances with Decawave outperforming
BeSpoon which in turn outperforms UbiSense. The Sewio kit we analysed uses
Decawave hardware.

Martinkovič et al. [31] investigate a real-time location system for hybrid
assembly environments. They analyse how UWB tracking can be incorporated in
manufacturing where humans and AGVs cooperate closely. Similarly, Park et al.
[32] combine UWB tracking with dead reckoning and a path planner for safe AGV
navigation in indoor construction sites. Ridolfi et al. [33] look at the
scalability of indoor UWB tracking systems and how to maximise the number of
tags that can be tracked. Krishnan et al. [34] focus on optimising the network
setup for best localisation accuracy. Ieni [35] analyses the performance of
indoor UWB tracking by evaluating different localization algorithms. These
systems provide practical localisation results for analysis but do not provide
safety-assessments or safety guarantees.

Černohorskỳ et al. [36] investigate UWB tracking in confined spaces (e.g.,
corridors) and provide suggestions for overcoming issues with interference and
accuracy. Zandian et al. [28] compare the performance of LOS vs NLOS UWB
tracking. They find a slight degradation in positioning accuracy with NLOS
compared to LOS geolocation. These authors findings will need to be considered
in our future work on developing safety contracts for dynamic factories.

Other uses of UWB tracking include tracking sports players such as basketball
players [20] for player movement analysis, tracking shoppers inside retail
stores to analyse their behaviour (movements) [21] [37], tracking players in
large-scale augmented reality (AR) systems [38], incorporating tracking tags
in AR headsets to geolocate users [39] or tracking indoor drones in warehouses
[3, 40, 41].

##  6 Conclusion and Future Work

This paper introduces a case study for evaluating the safety assurance of AGVs
in dynamic factories. We analyse the accuracy of geolocating AGVs using
fog/edge computing and whether an AGV can stop outside a virtual danger zone
set up using a commercial UWB tracking system to protect the area from
encroachment. In particular we investigated safety requirement SR2 from
section 3.1, AGV shall stop outside the danger zone and before colliding with
an object. We found that the safety contract conditions rely on guarantees
made by different components of the UWB system (tags, anchors, AGV speed and
on-board processors which affect AGV response time) and fog/edge (wi-fi)
capabilities - these components will all require safety contracts.
Additionally, AGV geofencing is an end-to-end service that requires a number
of stages. Each stage could have a separate contract defining the properties
that can be guaranteed and the conditions under which they hold, supporting a
modular approach to safety assurance.

This study is a proof-of-concept. Further work will analyse the geofencing and
guarantees over more AGV runs and extend the analyses to navigating the AGV
away from the danger zone and detecting failures of software and comms. We
will perform load testing to investigate how many AGVs can be safely
controlled in conjunction with how many safety controller laptops are
necessary for a given number of AGVs. We can further investigate the fog/edge
network and its effects on stopping distances. How do we certify the network?
What limits do we need to impose? How can we overcome network errors and still
ensure safety?

Future work will develop a set of contract templates and establish a set of
heuristics for guaranteeing that the contracts can be met (e.g., min/max AGV
speed, tag transmission rate). We will evaluate a range of AGVs (COTS to
commercial AGVs) to establish these parameters and also investigate using a
variable-depth buffer zone for different AGVs. The radius of the buffer will
vary to reflect how the guaranteed stopping distance changes with different
AGVs and according to the current state of an AGV (its speed, tag transmission
gap, wi-fi network throughput, network delay etc.)

Further ahead, we can combine the UWB geolocation with global path planning
using maps and algorithms such as A* and mapless path planning using sensor
data only [15].

## Acknowledgement

The work is funded by the Swedish Foundation for Strategic Research under the
project “Future factories in the cloud (FiC)” and the Assuring Autonomy
International Programme (www.york.ac.uk/assuring-autonomy).

## References

  * [1] O. Jaradat, I. Sljivo, I. Habli, and R. Hawkins, “Challenges of safety assurance for industry 4.0,” in 2017 13th European Dependable Computing Conference (EDCC), pp. 103–106, IEEE, 2017.
  * [2] S. Burton, I. Habli, T. Lawton, J. McDermid, P. Morgan, and Z. Porter, “Mind the gaps: Assuring the safety of autonomous systems from an engineering, ethical, and legal perspective,” Artificial Intelligence, vol. 279, p. 103201, 2020.
  * [3] W. Shule, C. M. Almansa, J. P. Queralta, Z. Zou, and T. Westerlund, “Uwb-based localization for multi-uav systems and collaborative heterogeneous multi-robot systems: a survey,” arXiv preprint arXiv:2004.08174, 2020.
  * [4] M. A. Javed, F. U. Muram, H. Hansson, S. Punnekkat, and H. Thane, “Towards dynamic safety assurance for industry 4.0,” Journal of Systems Architecture, p. 101914, 2020.
  * [5] J. Fenn, R. Hawkins, P. Williams, and T. Kelly, “Safety case composition using contracts-refinements based on feedback from an industrial case study,” in The Safety of Systems, pp. 133–146, Springer, 2007.
  * [6] PILZ GmbH & Co, Industrie 4.0 – safe and smart (white paper), June 2016, (accessed January 04, 2022).
  * [7] T. Kelly and R. Weaver, “The goal structuring notation–a safety argument notation,” in Proceedings of the dependable systems and networks 2004 workshop on assurance cases, p. 6, Citeseer, 2004.
  * [8] M. A. Sujan, I. Habli, T. P. Kelly, S. Pozzi, and C. W. Johnson, “Should healthcare providers do safety cases? lessons from a cross-industry review of safety case practices,” Safety science, vol. 84, pp. 181–189, 2016.
  * [9] H. Kagermann, J. Helbig, A. Hellinger, and W. Wahlster, Recommendations for implementing the strategic initiative INDUSTRIE 4.0: Securing the future of German manufacturing industry; final report of the Industrie 4.0 Working Group.  Forschungsunion, 2013.
  * [10] M. Kostoláni, J. Murín, and Š. Kozák, “An effective industrial control approach,” in 2019 Federated Conference on Computer Science and Information Systems (FedCSIS), pp. 911–914, IEEE, 2019.
  * [11] T. Kelly, “Concepts and principles of compositional safety cases,” QinetiQ Research Report COMSA/2001/1/1, 2001.
  * [12] A. Sangiovanni-Vincentelli, W. Damm, and R. Passerone, “Taming dr. frankenstein: Contract-based design for cyber-physical systems,” European journal of control, vol. 18, no. 3, pp. 217–238, 2012.
  * [13] V. J. Hodge, “Sensors and data in mobile robotics for localisation,” in Encyclopedia of Data Science and Machine Learning (J. Wang, ed.), IGI Global, 2022, to appear.
  * [14] F. Zafari, A. Gkelias, and K. K. Leung, “A survey of indoor localization systems and technologies,” IEEE Communications Surveys & Tutorials, 2019\.
  * [15] V. J. Hodge, R. Hawkins, and R. Alexander, “Deep reinforcement learning for drone navigation using sensor data,” Neural Computing and Applications, vol. 33, no. 6, pp. 2015–2033, 2021.
  * [16] M. G. Dissanayake, P. Newman, S. Clark, H. F. Durrant-Whyte, and M. Csorba, “A solution to the simultaneous localization and map building (slam) problem,” IEEE Transactions on robotics and automation, vol. 17, no. 3, pp. 229–241, 2001.
  * [17] J. Guiochet, M. Machin, and H. Waeselynck, “Safety-critical advanced robots: A survey,” Robotics and Autonomous Systems, vol. 94, pp. 43–52, 2017.
  * [18] S. Geng, S. Ranvier, X. Zhao, J. Kivinen, and P. Vainikainen, “Multipath propagation characterization of ultra-wide band indoor radio channels,” in 2005 IEEE international conference on ultra-wideband, pp. 11–15, IEEE, 2005\.
  * [19] Sewio, RTLS for precise indoor tracking, 2022 (accessed January 04, 2022).
  * [20] K. Hulka, M. Strniste, and D. Prycl, “Accuracy and reliability of sage analytics tracking system based on uwb technology for indoor team sports,” International Journal of Performance Analysis in Sport, pp. 1–8, 2020.
  * [21] M. Contigiani, R. Pietrini, A. Mancini, and P. Zingaretti, “Implementation of a tracking system based on uwb technology in a retail environment,” in 12th IEEE/ASME International Conference on Mechatronic and Embedded Systems and Applications, pp. 1–6, Aug 2016.
  * [22] Sewio, API Documentation, 2022 (accessed January 04, 2022).
  * [23] York Robotics Lab, University of York, UK, 2022 (accessed January 04, 2022).
  * [24] P. Sedlacek, M. Slanina, and D. Kovac, “An overview of indoor and outdoor positioning technologies with focus on their precision,” ElektroRevue, vol. 18, no. 6, 2016.
  * [25] Plink, USING THE COMMAND-LINE CONNECTION TOOL PLINK, 2022 (accessed January 04, 2022).
  * [26] York Robotics Kit, OctPi Robots, 2022 (accessed January 04, 2022).
  * [27] York Robotics Lab Github, York Robotics Kit, 2022 (accessed January 04, 2022).
  * [28] R. Zandian and U. Witkowski, “Performance analysis of small size and power efficient uwb communication nodes for indoor localization,” in Annual Conference Towards Autonomous Robotic Systems, pp. 371–382, Springer, 2016.
  * [29] M. Segura, H. Hashemi, C. Sisterna, and V. Mut, “Experimental demonstration of self-localized ultra wideband indoor mobile robot navigation system,” in 2010 International Conference on Indoor Positioning and Indoor Navigation, pp. 1–9, IEEE, 2010.
  * [30] A. R. J. Ruiz and F. S. Granja, “Comparing ubisense, bespoon, and decawave uwb location systems: Indoor performance analysis,” IEEE Transactions on instrumentation and Measurement, vol. 66, no. 8, pp. 2106–2117, 2017.
  * [31] M. Martinkovič, B. Mičieta, and V. Biňasová, “The use of real-time location system in hybrid assembly,” in Prumyslove inzenyrství, DOI:10.24132/pi.2019.08948.101-108, Západočeská univerzita v Plzni, 2019.
  * [32] J. Park, Y. K. Cho, and D. Martinez, “A bim and uwb integrated mobile robot navigation system for indoor position tracking applications,” Journal of Construction Engineering and Project Management, vol. 6, no. 2, pp. 30–39, 2016.
  * [33] M. Ridolfi, S. Van de Velde, H. Steendam, and E. De Poorter, “Analysis of the scalability of uwb indoor localization solutions for high user densities,” Sensors, vol. 18, no. 6, p. 1875, 2018.
  * [34] S. Krishnan, P. Sharma, Z. Guoping, and O. H. Woon, “A uwb based localization system for indoor robot navigation,” in 2007 IEEE International Conference on Ultra-Wideband, pp. 77–82, IEEE, 2007.
  * [35] M. Ieni, “Realization and performance evaluation of a hybrid uwb/wifi indoor localization system,” Master’s thesis, Scuola di Ingegneria Industriale e dell’Informazione, Dipartimento di Elettronica, Informazione e Bioingegneria, Politecnico di Milano, Italy, 2018.
  * [36] J. Černohorskỳ, P. Jandura, and P. Rydlo, “Real time ultra-wideband localisation,” in 2018 19th International Carpathian Control Conference (ICCC), pp. 445–450, IEEE, 2018.
  * [37] P. Gabellini, M. D’Aloisio, M. Fabiani, and V. Placidi, “A large scale trajectory dataset for shopper behaviour understanding,” in International Conference on Image Analysis and Processing, pp. 285–295, Springer, 2019.
  * [38] A. Cirulis, “Ultra wideband tracking potential for augmented reality environments,” in Augmented Reality, Virtual Reality, and Computer Graphics (L. T. De Paolis and P. Bourdot, eds.), (Cham), pp. 126–136, Springer International Publishing, 2019.
  * [39] J. Cyrus, D. Krcmarik, R. Moezzi, J. Koci, and M. Petru, “Hololens used for precise position tracking of the third party devices-autonomous vehicles,” Communications-Scientific letters of the University of Zilina, vol. 21, no. 2, pp. 18–23, 2019.
  * [40] N. Macoir, J. Bauwens, B. Jooris, B. Van Herbruggen, J. Rossey, J. Hoebeke, and E. De Poorter, “Uwb localization with battery-powered wireless backbone for drone-based inventory management,” Sensors, vol. 19, no. 3, p. 467, 2019\.
  * [41] J. Tiemann, F. Schweikowski, and C. Wietfeld, “Design of an uwb indoor-positioning system for uav navigation in gnss-denied environments,” in 2015 International Conference on Indoor Positioning and Indoor Navigation (IPIN), pp. 1–7, IEEE, 2015.