# Siamese convolutional networks based on phonetic features for cognate
identification

Taraka Rama
Seminar für Sprachwissenschaft
University of Tübingen
<EMAIL_ADDRESS>
###### Abstract

In this paper, we explore the use of convolutional networks (ConvNets) for the
purpose of cognate identification. We compare our architecture with binary
classifiers based on string similarity measures on different language
families. Our experiments show that convolutional networks achieve competitive
results across concepts and across language families at the task of cognate
identification.

##  1 Introduction

Cognates are words that are known to have descended from a common ancestral
language. In historical linguistics, identification of cognates is an
important step for positing relationships between languages. Historical
linguists apply the comparative method [Trask (1996] for positing
relationships between languages.

In NLP, automatic identification of cognates is associated with the task of
determining if two words are descended from a common ancestor or not. There
are at least two ways to achieve automatic identification of cognates.

One way is to modify a well-known string alignment technique such as Longest
Common Subsequence or Needleman-Wunsch algorithm [Needleman and Wunsch (1970]
to weigh the alignments differentially [Kondrak (2001, List (2012]. The
weights are determined through the linguistic knowledge of the sound changes
that occurred in the language family.

The second approach employs a machine learning perspective that is widely
employed in NLP. The cognate identification is achieved by training a linear
classifier or a sequence labeler on a set of labeled positive and negative
examples; and then employ the trained classifier to classify new word pairs.
The features for a classifier consist of word similarity measures based on
number of shared bigrams, edit distance, and longest common subsequence [Hauer
and Kondrak (2011, Inkpen et al. (2005].

The above procedures provide an estimate of the similarity between a pair of
words and cannot directly be used to infer a phylogeny based on models of
trait evolution. The pairwise judgments have to be converted into multiple
cognate judgments so that the multiple judgments can be supplied to a
automatic tree building program for inferring a phylogeny for the languages
under study.

It has to be noted that the Indo-European dating studies [Bouckaert et al.
(2012, Chang et al. (2015] employ human expert cognacy judgments for inferring
phylogeny and dates of a very well-studied language family. Hence, there is a
need for developing automated cognate identification methods that can be
applied to under-studied languages of the world.

##  2 Related work

The earlier computational effort of [Jäger (2013, Rama et al. (2013] employs
Pointwise Mutual Information (PMI) to compute transition matrices between
sounds. Both ?) and ?) employ undirectional sound correspondence based scorer
to compute word similarity. The general approach is to align word pairs using
vanilla edit distance and impose a cutoff to extract potential cognate pairs.
The aligned sound symbols are then employed to compute the PMI scoring matrix
that is used to realign the pairs. The PMI scoring matrix is recounted from
the realigned pairs. This procedure is repeated until convergence.

?) imposes an additional cutoff based on the PMI scoring matrix. Further, ?)
also employs the PMI scoring matrix to infer family trees for new language
families and compares those trees with the _expert_ trees given in _Glottolog_
[Nordhoff and Hammarström (2011]. ?) take a slightly different approach, in
that, the authors compute a PMI matrix independently for each language family
and evaluate its performance at the task of pair-wise cognate identification.
In this work, we also compare the convolutional networks against PMI based
binary classifier.

Previous works of cognate identification such as [Bergsma and Kondrak (2007,
Inkpen et al. (2005] supply string similarity measures as features for
training different classifiers such as decision trees, maximum-entropy, and
SVMs for the purpose of determining if a given word pair is cognate or not.

In another line of work, ?) employs a transition matrix derived from
historical linguistic knowledge to align and score word pairs. This approach
is algorithmically similar to that of ?) who employs articulation motivated
weights to score a sound transition matrix. The weighted sound transition
matrix is used to score a word pair.

The work of ?) known as Sound-Class Phonetic Alignment (SCA) approach reduces
the phonemes to historical linguistic motivated sound classes such that
transitions between some classes are less penalized than transitions between
the rest of the classes. For example, the probability of velars transitioning
to palatals is a well-attested sound change across the world. The SCA approach
employs a weighted directed graph to model directionality and proportionality
of sound changes between sound classes. For example, a direct change between
velars and dentals is unattested and would get a zero weight. Both ?) and ?)
set the weights and directions in the sound transition graph to suit the
reality of sound change.

All the above outlined approaches employ a scoring matrix that is derived
automatically or manually; or, employ a SVM to train form similarity based
features for the purpose of cognate identification.

##  3 Convolutional networks

This article is the first to apply convolutional networks (ConvNets) to
phonemes by treating each phoneme as a vector of binary valued phonetic
features. This approach has the advantage that it does not require explicit
feature engineering, alignments, and a sound transition matrix. The approach
requires cognacy statements and phonetic descriptions of sounds used to
transcribe the words. The cognacy statements can be obtained from etymological
dictionaries and the quality of the phonemes can be obtained from ?).

?) proposed ConvNets for NLP tasks in 2011 and were since applied for sentence
classification [Kim (2014, Johnson and Zhang (2015, Kalchbrenner et al. (2014,
Zhang et al. (2015], part-of-speech tagging [Santos and Zadrozny (2014], and
information retrieval [Shen et al. (2014].

?) applied convolutional networks to pre-trained word embeddings in a sentence
for the task of sentence classification. ?) train their convolutional network
from scratch by using a one-hot vector for each word. The authors show that
their convolutional network performs better than a SVM classifier trained on
bag-of-words features. ?) use character embeddings to train their POS-tagger.
The authors find that the POS-tagger performs better than the accuracies
reported in [Manning (2011].

In a recent work, ?) treat documents as a sequence of characters and transform
each document into a sequence of one-hot character vectors. The authors
designed and trained two 9-layer convolutional networks for the purpose of
sentiment classification. The authors report competitive or state-of-the art
performance on a wide range of benchmark sentiment classification datasets.

##  4 Character convolutional networks

?) extended the traditional ConvNets to classify if two images belong to the
same person. These ConvNets are known as Siamese Networks (inspired from
Siamese twins) and share weights for independent but identical layers of
convolutional networks. Siamese networks and their variants have been employed
for identifying if two images are from the same person or different persons
[Zagoruyko and Komodakis (2015]; and for recognizing if two speech segments
belong to the same word class [Kamper et al. (2015].

###  4.1 Word as image

Historical linguists perform cognate identification based on regular
correspondences which are described as changes in phonetic features of
phonemes. For instance, Grimm's law $b^{h}\sim b$ is described as loss of
aspiration; $p\sim f$ is described as change from plosives to fricatives; and
devoicing $d\sim t$ in English _ten_ $\sim$ Latin _decem_.

Learning criteria for cognacy through phonetic features from a set of training
examples implies that there is no need for explicit alignment and
design/learning of sound scoring matrices. In this article, we represent each
phoneme as a binary-valued vector of phonetic features and then perform
convolution on the two-dimensional matrix.

###  4.2 Siamese network

Intuitively, a network should learn a similarity function such that words that
diverged due to accountable sound shifts are placed close to one another than
two words that are not cognates. And, Siamese networks are suitable for this
task since, they learn a similarity function that has a higher similarity
between cognates as compared to non-cognates. The weight tying ensures that
two cognate words sharing similar phonetic features in a local context tend to
be get higher weights than words that are not cognate.

###  4.3 Phoneme vectorization

In this article, we work with the ASJP alphabet [Brown et al. (2013]. The ASJP
alphabet is coarser than IPA but is designed with the aim to capture highly
frequent sounds in the world's languages. The ASJP database has word lists for
60% of the world's languages but only has cognate judgments for some selected
families [Wichmann and Holman (2013].

p = voiceless bilabial stop and fricative [IPA: p, F]
---
b = voiced bilabial stop and fricative [IPA: b, B]
m = bilabial nasal [IPA: m]
f = voiceless labiodental fricative [IPA: f]
v = voiced labiodental fricative [IPA: v]
8 = voiceless and voiced dental fricative [IPA: T, D]
4 = dental nasal [IPA: ∥[n]
t = voiceless alveolar stop [IPA: t]
d = voiced alveolar stop [IPA: d]
s = voiceless alveolar fricative [IPA: s]
z = voiced alveolar fricative [IPA: z]
c = voiceless and voiced alveolar affricate [IPA: ts, dz]
n = voiceless and voiced alveolar nasal [IPA: n]
S = voiceless postalveolar fricative [IPA: S]
Z = voiced postalveolar fricative [IPA: Z]
C = voiceless palato-alveolar affricate [IPA: tS]
j = voiced palato-alveolar affricate [IPA: dZ]
T = voiceless and voiced palatal stop [IPA: c, ]
5 = palatal nasal [IPA: ]
k = voiceless velar stop [IPA: k]
g = voiced velar stop [IPA: g]
x = voiceless and voiced velar fricative [IPA: x, G]
N = velar nasal [IPA: N]
q = voiceless uvular stop [IPA: q]
G = voiced uvular stop [IPA: G]
X = voiceless and voiced uvular fricative, voiceless and voiced pharyngeal
fricative [IPA: X, K, , Q]
7 = voiceless glottal stop [IPA: P]
h = voiceless and voiced glottal fricative [IPA: h, H]
l = voiced alveolar lateral approximate [IPA: l]
L = all other laterals [IPA: L, L]
w = voiced bilabial-velar approximant [IPA: w]
y = palatal approximant [IPA: j]
r = voiced apico-alveolar trill and all varieties of ``r-sounds'' [IPA: r, R,
etc.]
! = all varieties of ``click-sounds'' [IPA: !, o, ——, ]
Table 1: ASJP consonants. ASJP has 6 vowels which we collapsed to a single
vowel _V_.

We composed a binary vector for each phoneme based on the description given in
table 1. In total, there are 16 binary valued features. We also reduced all
vowels to a single vowel that has a value of $1$ for voicing feature and $0$
for the rest of the features. The main motivation for such decision is that
vowels are diachronically unstable than consonants [Kessler (2007].

A word such as ``fat'' would be represented as $3\times 16$ matrix where each
column provides a binary value for the phonetic feature (cf. table 2).

p |  0 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0
---|---
b |  1 1 0 0 0 0 0 0 1 1 0 0 0 0 0 0
f |  0 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0
v |  1 1 1 0 0 0 0 0 0 1 0 0 0 0 0 0
m |  1 1 0 0 0 0 0 0 0 0 0 1 0 0 0 0
8 |  1 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0
4 |  1 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0
t |  0 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
d |  1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0
s |  0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
z |  1 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0
c |  1 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0
n |  1 0 0 1 0 0 0 0 0 0 0 1 0 0 0 0
S |  0 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
Z |  1 0 0 0 1 0 0 0 0 1 0 0 0 0 0 0
C |  0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
j |  1 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0
T |  1 0 0 0 1 0 0 0 1 0 0 0 0 0 0 0
5 |  0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0
k |  0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
g |  1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0
x |  1 0 0 0 0 1 0 0 0 1 0 0 0 0 0 0
N |  1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0
q |  0 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
G |  1 0 0 0 0 0 1 0 1 0 0 0 0 0 0 0
X |  1 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0
7 |  0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0
h |  1 0 0 0 0 0 0 1 0 1 0 0 0 0 0 0
l |  1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0
L |  1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0
w |  1 1 0 0 0 1 0 0 0 0 0 0 0 1 0 0
y |  1 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0
r |  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1
! |  1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0
V |  1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Table 2: Binarized ASJP alphabet used in our experiments. Each column
corresponds to the following features: Voiced, Labial, Dental, Alveolar,
Palatal/Post-alveolar, Velar, Uvular, Glottal, Stop, Fricative, Affricate,
Nasal, Click, Approximant, Lateral, and Rhotic.

###  4.4 ConvNet Models

In this subsection, we describe the ConvNet models used in our experiments.

Figure 1: Siamese network with fully connected layer. The weighted are shared
between the two convolutional networks.

Siamese ConvNet Siamese networks takes a pair of inputs and minimizes the
distance between the output representations. Each branch of the Siamese
network is composed of a convolutional network. The Euclidean distance $D$
between the representations of each branch is then used to train a
contrastive-loss function $yD+(1-y)max\\{0,m-D\\}$ where $m$ is the margin and
$y$ is the true label. We only describe the architecture since this forms the
basis for the rest of our experiments with Siamese architectures.111The
results were slightly better than a majority class classifier and were not
reported in the article

Manhattan Siamese ConvNet The second ConvNet is also a Siamese network where
the Euclidean distance is replaced by a element-wise absolute difference layer
followed by a fully connected layer (cf. figure 1). To the best of our
knowledge, only ?) added two fully connected layers to the concatenated
outputs of the Siamese network and trained a system that predicts if two image
patches belong to the same image or different images. We refer this
architecture as a Manhattan Siamese ConvNet due to the difference layer's
similarity to Manhattan distance.

2-channel Convnet Until now, each word is treated as a separate input. ?)
introduced a 2-channel architecture which treats a pair of image patches as a
2-channel image. This can also be applied to words. The 2-channel ConvNet has
two convolutional layers, a maxpooling layer, and a fully connected layer with
8 units.

The number of feature maps in each convolutional layer is fixed at $10$ with a
kernel size of $2\times 3$. The max-pooling layer halves the output of the
previous convolutional layer. We also inserted a dropout layer with $0.5$
probability [Srivastava et al. (2014] after a fully-connected layer to avoid
over-fitting. The convolutional layers were trained with ReLU non-linearity.

We zero-padded each word to obtain a length of $10$ for all the words to apply
the filter equally about a word. We used adadelta optimizer [Zeiler (2012]
with learning rate of $1.0$, $\rho=0.95$, and $\epsilon=10^{-6}$. We fixed the
mini-batch size to $128$ in all our experiments. We experimented with
different batch sizes ($[32,64,128,256]$) and did not observe any significant
deviation in the validation loss. Both, Manhattan and 2-stream ConvNets were
trained using the log-loss function. Both our architectures are relatively
shallow (3) as compared to the text classification architecture of ?). We
trained all our networks using Keras [Chollet (2015] and Theano [Bergstra et
al. (2010].

##  5 Comparison methods

We compare the ConvNet architectures with SVM classifiers trained with
different string similarities as features.

Other sound classes/alphabets Apart from ASJP alphabet, there are two other
alphabets that have been designed by historical linguists for the purpose of
modeling sound change. As mentioned before, the main idea behind the design of
sound classes is to discourage transitions between particular classes of
sounds but allow transitions within a sound class. ?) proposed a ten sound
class system based on the empirical data of $140$ languages. SCA alphabet
[List (2012] has a size of $25$ and attempts to address some issues with the
ASJP alphabet (lack of tones) and also extend Dolgopolsky's sound classes
based on evidence from more number of languages.

Orthographic measures as features We converted all the datasets into all the
three sound classes and computed the following string similarity scores:

  * •

Edit distance.

  * •

Common number of bigrams.

  * •

Length of the longest common subsequence.

  * •

Length of longest common prefix.

  * •

Common number of trigrams.

  * •

Global alignment based on Needlman-Wunch algorithm [Needleman and Wunsch
(1970].

  * •

Local alignment score based on Smith-Waterman algorithm [Smith and Waterman
(1981].

  * •

Semi-global alignment score is a compromise between global and local
alignments [Durbin et al. (2002].222The global, local, and alignment scores
were computed using LingPy library [List and Moran (2013].

  * •

Common number of skipped bigrams (XDICE).

  * •

A positional extension of XDICE known as XXDICE [Brew and McKelvie (1996].

Pair-wise Mutual Information (PMI) We also computed a PMI score for a pair of
ASJP transcribed words using the PMI scoring matrix developed by ?). This
system is referred to as PMI system.

We included length of each word and the absolute difference in length between
the words as features for both the Orthographic and PMI systems. The sound
class orthographic scores system attempts to combine the previous cognate
identification systems developed by [Inkpen et al. (2005, Hauer and Kondrak
(2011] and the insights from applying string similarities to sound classes for
language comparison [Kessler (2007].

##  6 Datasets

In this section, we describe the datasets used in our experiments.

IELex database The Indo-European Lexical database is created by ?) and curated
by Michael Dunn.333ielex.mpi.nl The transcription in IELex database is not
uniformly IPA and retains many forms transcribed in the Romanized IPA format
of ?). We cleaned the IELex database of any non-IPA-like transcriptions and
converted part of the database into ASJP format.

Austronesian vocabulary database The Austronesian Vocabulary Database
[Greenhill and Gray (2009] has word lists for 210 Swadesh concepts and 378
languages.444http://language.psy.auckland.ac.nz/austronesian/ The database
does not have transcriptions in a uniform IPA format. We removed all symbols
that do not appear in the standard IPA and converted the lexical items to ASJP
format.555For computational reasons, we work with a subset of 100 languages.

Family |  Concepts |  Languages |  Training |  Testing
---|---|---|---|---
Austronesian |  $210$ |  $100$ |  $334807$ |  $140697$
Mayan |  $100$ |  $30$ |  $28222$ |  $12344$
Indo-European |  $206$ |  $50$ |  $117740$ |  $49205$
Mixed dataset |  – |  – |  $176889$ |  –
Table 3: The number of languages, concepts, training, and test examples in our
datasets. We do not test on the mixed database and only use it for training
purpose.

Short word lists with cognacy judgments ?) and ?) compiled cognacy wordlists
for subsets of families from various scholarly sources such as comparative
handbooks and historical linguistics' articles. The details of this
compilation is given below. For each dataset, we give the number of
languages/the number of concepts in parantheses. This dataset is henceforth
referred to as ``Mixed dataset''.

  * •

?): Afrasian (21/40), Kadai (12/40), Kamasau (8/36), Lolo-Burmese (15/40),
Mayan (30/100), Miao-Yao (6/36), Mixe-Zoque (10/100), Mon-Khmer (16/100).

  * •

?): Bai dialects (9/110), Chinese dialects (18/180), Huon (14/84), Japanese
(10/200), ObUgrian (21/110; Hungarian excluded from Ugric sub-family), Tujia
(5/107; Sino-Tibetan).

We performed two experiments with these datasets. In the first experiment, we
randomly selected 70% of concepts from IELex, ABVD, and Mayan datasets for
training and the rest of the 30% concepts for testing. The motivation behind
this experiment is to test if ConvNets can learn phonetic feature patterns
across concepts. In the second experiment, we trained on the Mixed dataset but
tested on the Indo-European and Austronesian datasets. The motivation behind
this experiment is to test if ConvNets can learn general patterns of sound
change across language families. The number of training and testing examples
in each dataset is given in table 3.

Language family | Orthographic | PMI | Manhattan ConvNet | 2-Channel ConvNet
---|---|---|---|---
Austronesian | $77.92\%$ | $78\%$ | $79.04\%$ | $76.1\%$
Indo-European | $80\%$ | $78.58\%$ | $83.43\%$ | $81.7\%$
Mayan | $83.66\%$ | $85.25\%$ | $87.1\%$ | $82.1\%$
Austronesian | $0.833$ | $0.836$ | $0.861$ | $0.830$
$0.675$ | $0.665$ | $0.576$ | $0.595$
$0.783$ | $0.782$ | $0.776$ | $0.760$
Indo-European | $0.863$ | $0.854$ | $0.894$ | $0.883$
$0.628$ | $0.598$ | $0.618$ | $0.585$
$0.808$ | $0.794$ | $0.830$ | $0.813$
Mayan | $0.866$ | $0.885$ | $0.888$ | $0.865$
$0.791$ | $0.795$ | $0.756$ | $0.734$
$0.84$ | $0.853$ | $0.842$ | $0.819$
Austronesian | $0.749$ | $0.74$ | $0.683$ | $0.643$
Indo-European | $0.729$ | $0.678$ | $0.681$ | $0.64$
Mayan | $0.88$ | $0.892$ | $0.871$ | $0.805$
Table 4: Each system is trained on cognate and non-cognate pairs on 145
concepts in Indo-European and Austronesian families; and tested on the rest of
the concepts. For Mayan family, the number of training concepts is 70 and the
number of concepts in testing data is 30. For each family, numbers correspond
to the following metrics: Accuracies, F-scores (negative, positive, combined),
Average precision score.

##  7 Results

In this section, we report the results of our cross-concepts and cross-family
experiments.

SVM training and evaluation metrics We used a linear kernel and optimized the
SVM hyperparameter ($C$) through ten-fold cross-validation and grid search on
the training data. We report accuracies, class-wise F-scores (positive and
negative), combined F-score, and average precision score for each system on
concepts dataset in table 4. The average precision score corresponds to the
area under the precision-recall curve and is an indicator of the robustness of
the model to thresholds.

###  7.1 Cross-Concept experiments

Effect of size and width of fully connected layers We observed that both the
depth and width of the fully connected layers do not affect the performance of
the ConvNet models. We used a fully connected network of size 8 in all our
experiments. We increased the number of neurons from $8$ to $64$ in multiples
of two and observed that increasing the number of neurons hurts the
performance of the system.

Effect of filter size ?) observed that the size of the filter patch can affect
the performance of the system. We experimented with different filter sizes of
dimensions $m\times k$ where, $m\in[1,2]$ and $k\in[1,3]$. We did not find any
change in the performance in concepts experiments. We report the results for
$m=2,k=3$ filter size for cross-concept experiments.

###  7.2 Cross-Family experiments

Effect of filter size Unlike the previous experiment, the filter size has a
effect on the performance of the ConvNet system. We observed that the best
results were obtained with a filter size of $1\times 3$.

We did not include the results of the 2-channel ConvNet because of its worse
performance at the task of cross-family cognate identification. The results of
our experiments are given in table 5.

Dataset | Orthographic | PMI |  Manhattan ConvNet
---|---|---|---
Austronesian | $0.766$ | $0.78$ |  $0.746$
Indo-European | $0.815$ | $0.804$ |  $0.804$
Austronesian | $0.821$ | $0.837$ |  $0.820$
$0.661$ | $0.656$ |  $0.570$
$0.759$ | $0.768$ |  $0.728$
Indo-European | $0.876$ | $0.873$ |  $0.871$
$0.631$ | $0.569$ |  $0.590$
$0.806$ | $0.786$ |  $0.791$
Austronesian | $0.771$ | $0.795$ |  $0.707$
Indo-European | $0.731$ | $0.692$ |  $0.691$
Table 5: Testing accuracies, class-wise and combined F-scores, average
precision score of each system on Indo-European and Austronesian families.

##  8 Discussion

The Manhattan ConvNet competes with PMI and orthographic models at cross-
concept cognate identification task. The Manhattan ConvNet performs better
than PMI and orthographic models in terms of overall accuracy in all the three
language families. In terms of averaged F-scores, Manhattan ConvNet performs
slightly better than orthographic model and only performs worse than the other
models at Austronesian language family.

The Manhattan ConvNet shows mixed performance at the task of cross-family
cognate identification. The Manhattan ConvNet does not turn up as the best
system across all the evaluation metrics in a single language family. The
ConvNet performs better than PMI but is not as good as Orthographic measures
at Indo-European language family. In terms of accuracies, the ConvNet comes
closer to PMI than the orthographic system.

These experiments suggest that ConvNets can compete with a classifier trained
on different orthographic measures and different sound classes. ConvNets can
also compete with a data driven method like PMI which was trained in an EM-
like fashion on millions of word pairs. ConvNets can certainly perform better
than a classifier trained on word similarity scores at cross-concept
experiments.

The Orthographic system and PMI system show similar performance at the
Austronesian cross-concept task. However, ConvNets do not perform as well as
orthographic and PMI systems. The reason for this could be due to the
differential transcriptions in the database.

##  9 Conclusion

In this article, we explored the use of phonetic feature convolutional
networks for the task of pairwise cognate identification. Our experiments with
convolutional networks show that phonetic features can be directly used for
classifying if two words are related or not.

In the future, we intend to work directly with speech recordings and include
language relatedness information into ConvNets to improve the performance. We
are currently working towards building a larger database of word lists in IPA
transcription.

## Acknowledgments

I thank Aparna Subhakari, Vijayaditya Peddinti, Johann-Mattis List, Johannes
Dellert, Armin Buch, Çağrı Çöltekin, Gerhard Jäger, and Daniël de Kok for all
the useful comments. The data for the experiments was processed by Johann-
Mattis List and Pavel Sofroniev.

## References

  * [Bergsma and Kondrak (2007]  Shane Bergsma and Grzegorz Kondrak.  2007\.  Alignment-based discriminative string similarity.  In Proceedings of the 45th annual meeting of the association of computational linguistics, pages 656–663, Prague, Czech Republic, June. Association for Computational Linguistics.
  * [Bergstra et al. (2010]  James Bergstra, Olivier Breuleux, Frédéric Bastien, Pascal Lamblin, Razvan Pascanu, Guillaume Desjardins, Joseph Turian, David Warde-Farley, and Yoshua Bengio.  2010\.  Theano: a cpu and gpu math expression compiler.  In Proceedings of the Python for scientific computing conference (SciPy), volume 4, page 3. Austin, TX.
  * [Bouckaert et al. (2012]  Remco Bouckaert, Philippe Lemey, Michael Dunn, Simon J. Greenhill, Alexander V. Alekseyenko, Alexei J. Drummond, Russell D. Gray, Marc A. Suchard, and Quentin D. Atkinson.  2012\.  Mapping the origins and expansion of the Indo-European language family.  Science, 337(6097):957–960.
  * [Brew and McKelvie (1996]  Chris Brew and David McKelvie.  1996\.  Word-pair extraction for lexicography.  In Proceedings of the Second International Conference on New Methods in Language Processing, pages 45–55. Ankara.
  * [Brown et al. (2013]  Cecil H. Brown, Eric W. Holman, and Søren Wichmann.  2013\.  Sound correspondences in the world's languages.  Language, 89(1):4–29.
  * [Chang et al. (2015]  Will Chang, Chundra Cathcart, David Hall, and Andrew Garrett.  2015\.  Ancestry-constrained phylogenetic analysis supports the Indo-European steppe hypothesis.  Language, 91(1):194–244.
  * [Chollet (2015]  Franois Chollet.  2015\.  Keras.
  * [Chopra et al. (2005]  Sumit Chopra, Raia Hadsell, and Yann LeCun.  2005\.  Learning a similarity metric discriminatively, with application to face verification.  In Computer Vision and Pattern Recognition, 2005. CVPR 2005. IEEE Computer Society Conference on, volume 1, pages 539–546. IEEE.
  * [Collobert et al. (2011]  Ronan Collobert, Jason Weston, Léon Bottou, Michael Karlen, Koray Kavukcuoglu, and Pavel Kuksa.  2011\.  Natural language processing (almost) from scratch.  The Journal of Machine Learning Research, 12:2493–2537.
  * [Dolgopolsky (1986]  Aron B. Dolgopolsky.  1986\.  A probabilistic hypothesis concerning the oldest relationships among the language families of northern Eurasia.  In Vitalij V. Shevoroshkin and Thomas L. Markey, editors, Typology, Relationship, and Time: A Collection of Papers on Language Change and Relationship by Soviet Linguists, pages 27–50. Karoma, Ann Arbor, MI.
  * [Durbin et al. (2002]  Richard Durbin, Sean R. Eddy, Anders Krogh, and Graeme Mitchison.  2002\.  Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids.  Cambridge University Press, Cambridge.
  * [Dyen et al. (1992]  Isidore Dyen, Joseph B. Kruskal, and Paul Black.  1992\.  An Indo-European classification: A lexicostatistical experiment.  Transactions of the American Philosophical Society, 82(5):1–132.
  * [Greenhill and Gray (2009]  Simon J. Greenhill and Russell D. Gray.  2009\.  Austronesian language phylogenies: Myths and misconceptions about Bayesian computational methods.  Austronesian Historical Linguistics and Culture History: A Festschrift for Robert Blust, pages 375–397.
  * [Hauer and Kondrak (2011]  Bradley Hauer and Grzegorz Kondrak.  2011\.  Clustering semantically equivalent words into cognate sets in multilingual lists.  In Proceedings of 5th International Joint Conference on Natural Language Processing, pages 865–873, Chiang Mai, Thailand, November. Asian Federation of Natural Language Processing.
  * [Inkpen et al. (2005]  Diana Inkpen, Oana Frunza, and Grzegorz Kondrak.  2005\.  Automatic identification of cognates and false friends in French and English.  In Proceedings of the International Conference Recent Advances in Natural Language Processing, pages 251–257.
  * [Jäger (2013]  Gerhard Jäger.  2013\.  Phylogenetic inference from word lists using weighted alignment with empirically determined weights.  Language Dynamics and Change, 3(2):245–291.
  * [Johnson and Zhang (2015]  Rie Johnson and Tong Zhang.  2015\.  Effective use of word order for text categorization with convolutional neural networks.  In NAACL HLT 2015, The 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Denver, Colorado, USA, May 31 - June 5, 2015, pages 103–112.
  * [Kalchbrenner et al. (2014]  Nal Kalchbrenner, Edward Grefenstette, and Phil Blunsom.  2014\.  A convolutional neural network for modelling sentences.  Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, June.
  * [Kamper et al. (2015]  Herman Kamper, Weiran Wang, and Karen Livescu.  2015\.  Deep convolutional acoustic word embeddings using word-pair side information.  CoRR, abs/1510.01032.
  * [Kessler (2007]  Brett Kessler.  2007\.  Word similarity metrics and multilateral comparison.  In Proceedings of the Ninth Meeting of the ACL Special Interest Group in Computational Morphology and Phonology, pages 6–14. Association for Computational Linguistics.
  * [Kim (2014]  Yoon Kim.  2014\.  Convolutional neural networks for sentence classification.  In Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1746–1751, Doha, Qatar, October. Association for Computational Linguistics.
  * [Kondrak (2000]  Grzegorz Kondrak.  2000\.  A new algorithm for the alignment of phonetic sequences.  In Proceedings of the First Meeting of the North American Chapter of the Association for Computational Linguistics, pages 288–295.
  * [Kondrak (2001]  Grzegorz Kondrak.  2001\.  Identifying cognates by phonetic and semantic similarity.  In Proceedings of the second meeting of the North American Chapter of the Association for Computational Linguistics on Language technologies, pages 1–8. Association for Computational Linguistics.
  * [Ladefoged and Maddieson (1998]  Peter Ladefoged and Ian Maddieson.  1998\.  The sounds of the world's languages.  Language, 74(2):374–376.
  * [List and Moran (2013]  Johann-Mattis List and Steven Moran.  2013\.  An open source toolkit for quantitative historical linguistics.  In Proceedings of the 51st Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 13–18, Sofia, Bulgaria, August. Association for Computational Linguistics.
  * [List (2012]  Johann-Mattis List.  2012\.  SCA: phonetic alignment based on sound classes.  In New Directions in Logic, Language and Computation, pages 32–51. Springer.
  * [List (2014]  J.-M. List.  2014\.  Sequence comparison in historical linguistics.  Düsseldorf University Press, Düsseldorf.
  * [Manning (2011]  Christopher D Manning.  2011\.  Part-of-speech tagging from 97% to 100%: is it time for some linguistics?  In Computational Linguistics and Intelligent Text Processing, pages 171–189. Springer.
  * [Needleman and Wunsch (1970]  Saul B. Needleman and Christian D. Wunsch.  1970\.  A general method applicable to the search for similarities in the amino acid sequence of two proteins.  Journal of Molecular Biology, 48(3):443–453.
  * [Nordhoff and Hammarström (2011]  Sebastian Nordhoff and Harald Hammarström.  2011\.  Glottolog/Langdoc: Defining dialects, languages, and language families as collections of resources.  In Proceedings of the First International Workshop on Linked Science, volume 783.
  * [Rama et al. (2013]  Taraka Rama, Prasant Kolachina, and Sudheer Kolachina.  2013\.  Two methods for automatic identification of cognates.  QITL, 5:76.
  * [Santos and Zadrozny (2014]  Cicero D Santos and Bianca Zadrozny.  2014\.  Learning character-level representations for part-of-speech tagging.  In Proceedings of the 31st International Conference on Machine Learning (ICML-14), pages 1818–1826.
  * [Shen et al. (2014]  Yelong Shen, Xiaodong He, Jianfeng Gao, Li Deng, and Grégoire Mesnil.  2014\.  A latent semantic model with convolutional-pooling structure for information retrieval.  In Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management, pages 101–110. ACM.
  * [Smith and Waterman (1981]  Temple F. Smith and Michael S. Waterman.  1981\.  Identification of common molecular subsequences.  Journal of molecular biology, 147(1):195–197.
  * [Srivastava et al. (2014]  Nitish Srivastava, Geoffrey Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov.  2014\.  Dropout: A simple way to prevent neural networks from overfitting.  The Journal of Machine Learning Research, 15(1):1929–1958.
  * [Trask (1996]  Robert Lawrence Trask.  1996\.  Historical Linguistics.  Oxford University Press, London.
  * [Wichmann and Holman (2013]  Søren Wichmann and Eric W Holman.  2013\.  Languages with longer words have more lexical change.  In Approaches to Measuring Linguistic Differences, pages 249–281. Mouton de Gruyter.
  * [Zagoruyko and Komodakis (2015]  Sergey Zagoruyko and Nikos Komodakis.  2015\.  Learning to compare image patches via convolutional neural networks.  In The IEEE Conference on Computer Vision and Pattern Recognition (CVPR), June.
  * [Zeiler (2012]  Matthew D Zeiler.  2012\.  Adadelta: an adaptive learning rate method.  arXiv preprint arXiv:1212.5701.
  * [Zhang and Wallace (2015]  Ye Zhang and Byron Wallace.  2015\.  A sensitivity analysis of (and practitioners' guide to) convolutional neural networks for sentence classification.  arXiv preprint arXiv:1510.03820.
  * [Zhang et al. (2015]  Xiang Zhang, Junbo Zhao, and Yann LeCun.  2015\.  Character-level convolutional networks for text classification.  In C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, editors, Advances in Neural Information Processing Systems 28, pages 649–657. Curran Associates, Inc.


DSCC 2018 ASME 2018 Dynamic Systems and Control Conferences 24-28 September
30-October 3 2018 Atlanta USA DSCC2018-9161

# Human-Robot Trust Integrated Task Allocation and Symbolic Motion planning
for Heterogeneous Multi-robot Systems

Huanfei Zheng  Mechanical Engineering Department
Clemson University
Clemson, South Carolina 29634
Email<EMAIL_ADDRESS>Zhanrui Liao  Mechanical Engineering Department
Clemson University
Clemson, South Carolina 29634
Email<EMAIL_ADDRESS>Yue Wang This work is partially supported by the
Air Force Office of Scientific Research Young Investigator Program under grant
no. FA9550-17-1-0050. Mechanical Engineering Department
Clemson University
Clemson, South Carolina 29634
Email<EMAIL_ADDRESS>
###### Abstract

This paper presents a human-robot trust integrated task allocation and motion
planning framework for multi-robot systems (MRS) in performing a set of tasks
concurrently. A set of task specifications in parallel are conjuncted with MRS
to synthesize a task allocation automaton. Each transition of the task
allocation automaton is associated with the total trust value of human in
corresponding robots. Here, the human-robot trust model is constructed with a
dynamic Bayesian network (DBN) by considering individual robot performance,
safety coefficient, human cognitive workload and overall evaluation of task
allocation. Hence, a task allocation path with maximum encoded human-robot
trust can be searched based on the current trust value of each robot in the
task allocation automaton. Symbolic motion planning (SMP) is implemented for
each robot after they obtain the sequence of actions. The task allocation path
can be intermittently updated with this DBN based trust model. The overall
strategy is demonstrated by a simulation with 5 robots and 3 parallel subtask
automata.

##  1 Introduction

Symbolic motion planning (SMP) solves complex motion planning problems for
robots using linear temporal logic (LTL), languages and automata theory [1].
It enables the automatic control of a robot or teams of robots from high level
with different task specifications. However, computationally efficient
frameworks are often needed to deal with the increasing complexity of task
specifications and multi-robot system (MRS). Many centralized and
decentralized frameworks have been developed to deal with the “state-space
explosion” problems. A compositional multi-robot motion planning framework in
[2] uses precomputed motion primitives for robots and employs a satisfiability
modulo theory solver to synthesize robot trajectories. Event-based
synchronization approach is proposed in [3] to address interdependencies among
robots in motion planning. In [4, 5], a bottom-up strategy is proposed where
each robot is assigned with a local task and inter-robot dependence is
achieved through cooperative motion and task planning. In [6, 7], a top-down
framework is presented for the automatic deployment of a robotic team from a
specification by giving each robot the capabilities to serve the cooperation
requirements. Supervisor synthesis with compositional verification techniques
is utilized to guarantee robot performance in [8], where a given team mission
is decomposed into individual tasks.

The above multi-robot motion planning frameworks are however restricted either
in scalability in terms of the size of robot teams, or in complexity of tasks
due to the inter-dependencies among robots. The robot-task pairs are given as
fixed in dealing with the global task specifications. That is, these works do
not consider the task allocation problem. In this paper, we will first
establish a multi-robot multi-task task allocation framework to guarantee the
reachability of tasks and optimal assignment of robots. The motion planning of
each robots is implemented sequentially based on the task allocation results.
Reallocations can also be triggered in this automatic process to deal with the
uncertainties of the motion planning in the dynamic environment.

Under our proposed framework, SMP can therefore ensure automatic and scalable
solutions for MRS motion planning. Moreover, human supervision may facilitate
the efficiency and safety of MRS in a dynamic and uncertain environment
because humans excel in complex decision-making and robot’s performance in
such scenarios is not usually not satisfactory. Various designs and analyses
related with human-robot team cooperation have been conducted to improve
human’s situation awareness of robot. The work in [9] focuses on the
development and evaluation of complex socio-technical system for human-robot
teaming in Urban Search and Rescue with a user-centric design methodology,
which ranges from modeling situation awareness, human robot interaction (HRI),
flexible planning, and cognitive system design. In [10], an empirical analysis
of human teamwork is conducted to investigate the ways teammates incorporate
coordination behaviors, including both verbal and nonverbal cues, into their
action planning. Measurable Shared Mental Models (SMMs) are developed in [11]
to promote an effective human-robot teaming by observing a team of expert
human workers prior to task execution, and then robots executing an
interactive planning and cross-training process with a human co-worker to
iteratively refine and converge the team model. The framework of discrete-time
stochastic hybrid systems is utilized in [12] to model human-in-the-loop
cyber-physical systems with discrete choices, and pose the question of
expected outcome in terms of a stochastic reachability problem. The paper [13]
constructs a POMDP based trust model for human to a single robot to improve
performance of the joint human-robot system.

In this work, we will develop a human-robot trust integrated task allocation
and motion planning framework for MRS in order to enable a human-like
automatic decision-making process for multi-robot tasking. The contribution of
the paper is two-fold. First, we synthesize an automatic task (re)allocation
framework that can generate solutions with maximum human-robot trust for the
system. It enables real-time updating of task allocation of robots in a human-
like way. Furthermore, we construct a dynamic Bayesian network (DBN) based
human-robot trust model. This model will evaluate the robot performance,
safety, human cognitive workload, and the task (re)allocation framework in a
system wide trust setting.

The organization of the rest of the paper is as follows. Section 2 provides
the problem setup with a schematic of the human supervised MRS. Section 3
describes the human-robot trust associated task allocation framework and
symbolic motion planning of each robot for a set of parallel subtasks. Section
4 details the construction of the DBN based human-trust model, and integrates
the human-robot trust evaluation into task (re)allocation and motion planning
framework. A simulation in Section 5 demonstrates the viability and
effectiveness of the proposed framework and Section 6 concludes this paper.

##  2 Problem Setup

The schematic of human-robot trust integrated task allocation and SMP is shown
in Figure 1. Initially, a task allocation automaton is synthesized for a task
requirement that concurrently implementable subtasks are to be performed by a
set of heterogeneous robots. The subtasks are described by automata and each
robot can perform multiple actions in the subtasks. A task allocation path is
generated with the maximum accumulated trust of robots from the task
allocation automaton. Local action and motion specifications of each robot are
mapped from the maximal trust encoded task allocation path so that each robot
can execute the motions and actions sequentially. The SMP will also deal with
the obstacle collision avoidance in the discrete environment. All these
performance will be evaluated to contribute to the calculation of the
computational human-robot trust model.

On the other hand, human is allowed to participate into this task allocation
and motion planning process in order to improve system performance and
reliability. A system-wide human-robot trust model is constructed based on the
MRS task allocation by considering robot performance on task performing,
safety evaluation on malfunctioning, human cognitive workload of supervision
and inter-robot influence from task allocation. The trust of human in each
robot will be updated with the progress of task performing. The system-wide
trust model will increase or decrease the trust of robots involved with task
allocation to construct the interdependence relationship among robots. Once an
action is completed by a robot, human will be inquired for the task
reallocation based on his/her trust in the current robot. Finally, the
parallel subtasks will be completed with a maximum trust encoded task
allocation solution and motion planning paths by intermittently updating the
task allocation under human supervision.

Figure 1: Human-robot trust integrated task allocation and motion planning
framework. $\\{a,~{}b\\},~{}\\{c\\}$ are the action sets of parallel subtask
automata. $T_{1},\cdots,T_{i},\cdots,T_{I}$ are the respective trust value of
robots. $\Psi$ is the synthesized task allocation automaton.

We summarize the human-robot trust integrated multi-robot task allocation and
motion planning with the following assumption and problem.

######  Assumption 1.

Each heterogeneous robot $r_{i}\in\mathcal{R}$ is associated with an action
set $Er_{i}$ describing its capabilities in performing tasks. Assume that
$\cup_{i=1}^{I}Er_{i}\supseteq E_{g}$, i.e. all the subtasks can be
collaboratively performed by the MRS. Each robot may be able to perform
multiple actions, but it is assumed that a robot can only perform one action
at a time.

######  Problem 1.

Given a set of parallel subtasks, described with automata
$\\{G_{k},k=1,\cdots,K\\}$, each is associated with an action set $E_{k}$ that
robots need to perform, and all actions are scattered in a dynamic
environment, design a task (re)allocation framework such that these subtasks
can be completed by $I$ heterogeneous robots $r_{i}\in\mathcal{R}$ with
corresponding capability action set $Er_{i}$, where $i\in\\{1,\cdots,I\\}$; In
the meantime, a human-robot trust model is integrated into the MRS to enable
trust-based task reallocation such that human-like decision-making can be
deployed for multi-robot multi-task allocation.

##  3 Task Allocation and Symbolic Motion Planning

The subtasks of MRS can be described with a set of automata
$\\{G_{k},k=1,\cdots,K\\}$. These subtasks satisfy a parallel relationship
with $\|_{k=1}^{K}G_{k}\triangleq((G_{1}\|\cdots
G_{k})\|\cdots\|G_{K-1})\|G_{K}$, which represent a set of subtask automata
$G_{k}$s that can be concurrently dealt with using a team of robots. We will
construct the task allocation automaton with trust associated transitions for
these parallel subtasks and robots so that a maximal trust encoded task
allocation solution can be generated for the MRS.

###  3.1 Human-Robot Trust Associated Task Allocation

In order to find a maximum trust encoded task allocation solution, we
synthesize a task allocation automaton $\Psi$ by taking into account both
robot capabilities and subtask automata. A path from task allocation automaton
gives a task allocation solution regarding what actions to be allocated to
what robots. To explain the process of generating a maximum trust encoded path
from the task allocation automaton, we introduce the following definitions.

######  Definition 1 (Minimal Suffix Set of Language).

Given an automaton $G$ with an action set $E$, the minimal suffix set of
language $L(G)$ is denoted as $\mathcal{L}=\\{\ell\in E^{*}:\ell\text{ is the
suffix of }\min(s),~{}s\in L(G)\\}$, where $\min(s)$ is one of the minimal
length paths in $L(G)$ and $E^{*}$ is the Kleene-closure of $E$.

######  Definition 2 (Implementable Action Set).

Given a task automaton $G$ with an action set $E$, an action $e\in E$ is said
to be implementable for a robot $r$ with a capability action set $Er$ if the
following two conditions are satisfied: 1) $e\in Er$, which means the action
$e$ can be performed by robot $r$, and 2) $e\in\\{\ell(0)\\}$, i.e. action $e$
is ready to be performed at the states of $G$ that match $\ell$, where
$\ell(0)$ is the first element of $\ell$. Hence, an implementable action set
of automaton $G$ for robot $r$ is denoted as $IA=\\{(r,e):e\in
Er\cap\\{\ell(0)\\}\\}$.

Accordingly, the implementable action set of automaton $G_{k}$ for all robots
in the set $\mathcal{R}$ can be given as $IG_{k}=\cup_{i=1}^{I}IA_{i,k}$,
where $IA_{i,k}=\\{(r_{i},e_{k}):e_{k}\in Er_{i}\cap\\{\ell_{k}(0)\\}\\}$.

######  Definition 3 (Multi-action Set).

The set
$Act_{\psi}=\\{act_{\psi}\triangleq(\omega_{1},\cdots,\omega_{k},\cdots,\omega_{K}):\omega_{k}=(r_{i},\hat{e}_{k}),r_{i}\in\mathcal{R},\hat{e}_{k}\in
Er_{i}\cap\\{\ell_{k}(0)\\}\cup\\{\epsilon\\}\\}$ defines a multi-action set,
where the single-action $\omega_{i}=(r_{i},\hat{e}_{k})$,
$\hat{e}_{k}\neq\epsilon$ defines an action in automaton $G_{k}$ performed by
a robot in $r_{i}\in\mathcal{R}$; $\omega_{k}=(r_{i},\epsilon)$ means no
action in $G_{k}$ is assigned to robot $r_{i}$. A multi-action $act_{\psi}\in
Act_{\psi}$ holds if and only if it is (1) effective, i.e.
$\exists\omega_{k}\not\in\\{(r_{i},\epsilon),i=1,\cdots,I\\}$, (2) unique,
i.e.
$\forall\omega_{k},\omega_{k^{\prime}}\not\in\\{(r_{i},\epsilon),i=1,\cdots,I\\}$,
if $k\neq k^{\prime}$, then $r_{i}\neq r_{i^{\prime}}$. For simplicity of
notation, we further denote $\omega_{k}=(r_{i},\epsilon)$ as $\mathcal{E}$.

######  Remark 1.

The multi-action set combines multiple implementable actions and guarantees
not only the state transition of each subtask automaton but also the mutual
exclusion of subtask automata for robots.

Finally, we can define the task allocation automaton for multiple robots to
perform multiple tasks as follows.

######  Definition 4 (Task Allocation Automaton).

The task allocation automaton $\Psi$ describes the assignment of robots to the
actions in subtask automata. It is given by a tuple
$\Psi=(X_{\psi},Act_{\psi},\delta_{\psi},\chi_{0},W_{\psi})$ where

  1. 1.

$X_{\psi}=\mathcal{L}_{1}\times\cdots\mathcal{L}_{k}\times\cdots\mathcal{L}_{K}$
is the composite state set of task allocation including a set of composite
states $\chi=(\ell_{1},\cdots,\ell_{k},\cdots,\ell_{K})$ for the parallel
processes $\|_{k=1}^{K}G_{k}$, $\ell_{k}\in\mathcal{L}_{k}$, where
$\mathcal{L}_{k}$ is the minimal suffix set of $L(G_{k})$,

  2. 2.

the multi-action set
$Act_{\psi}\subseteq\prod_{k=1}^{K}({IG}_{k}\cup\\{\mathcal{E}\\})$ (Def. 3)
includes a finite set of actions $act_{\psi}\in Act_{\psi}$ that the
heterogeneous robots group $\mathcal{R}$ can perform,

  3. 3.

the transition relation $\delta_{\psi}(\chi,act_{\psi})$ is a process
$\chi\xrightarrow{act_{\psi}}\chi^{\prime}$, which can be detailed as
$(\ell_{1}\xrightarrow{\omega_{1}}\ell_{1}^{\prime},\cdots,\ell_{K}\xrightarrow{\omega_{K}}\ell_{K}^{\prime})$,

  4. 4.

$\chi_{0}$ is the initial state of task allocation,

  5. 5.

$W_{\psi}:Act_{\psi}\rightarrow\mathbb{R}$ is the set of accumulated trust of
all robots associated with the completion of each action,
$W_{\psi}(act_{\psi})=\sum_{i=1}^{I}T_{i}(t)$, where $T_{i}(t)$ is the trust
of human in a single robot $r_{i}$ at time $t$.

A finite path $\mathbb{S}_{\Psi}=act_{\psi}^{(0)}\cdots
act_{\psi}^{(\tau)}\cdots act_{\psi}^{(\mathbf{T})}$ with
$act_{\psi}^{(\tau)}\in Act_{\psi}$ presents a task allocation solution for
the parallel processes $\|_{k=1}^{K}G_{k}$ with robots $r_{i}$,
$i=1,\cdots,I$.

An initial task allocation $\mathbb{S}_{\psi}$ with maximum accumulated trust
of all robots $\max(\sum_{\tau=0}^{\mathbf{T}}W_{\psi})$ from initial state
$\chi_{0}$ to final state $\chi_{F}$ can be generated by searching the task
allocation automaton $\Psi$. The maximum trust encoded path presents the
optimal assignment of robots for all actions in a human-like decision-making
pattern, since the associated trust values in task allocation automaton are
evaluated with the impact factors in Section 4, such as robot performance,
safety, human cognitive workload, and system wide trust evaluated task
allocation. The accept state is reached when all subtask automata are reduced
to be empty and all its actions are completed. The parallel process based task
allocation is conducted among heterogeneous robots without subtask inter-
dependency.

###  3.2 Symbolic Motion Planning

The maximum trust encoded task allocation path may provide a task performing
sequence for each robot in a human-like decision-making process, but it is
also necessary to consider how to deal with the reachability of all these
actions in the dynamic environment. For SMP with a team of robots, paths
satisfying the global specification can be generated by model checking, which
encodes each robot a single path in the abstracted workspace.

In this work, we assume that the task environment is not known a priori, which
is also an important prerequisite for robot performance estimation on obstacle
avoidance to be discussed in Section 4. The paths of motion planning for
robots are intermittently replanned upon the information they get through
exploring the area. The mapping of $\mathbb{S}_{\psi}$ into each $r_{i}$ from
initial step to step $\mathbf{T}$ will give each robot a task allocation path
${s}_{\psi,i}={\omega}_{k_{0}}^{(0)}\cdots{\omega}_{k_{\tau}}^{(\tau)}\cdots{\omega}_{k_{\mathbf{T}}}^{(\mathbf{T})}$,
where $k_{\tau}\in\\{1,\cdots,K\\}$ is an index of subtask automaton.

Denote
${s}_{\pi,i}={\pi}_{k_{0}}^{(0)}\cdots{\pi}_{k_{\tau}}^{(\tau)}\cdots{\pi}_{k_{\mathbf{T}}}^{(\mathbf{T})}$
as the corresponding sequence of motion specifications of $r_{i}$.
${\pi}_{k_{\tau}}^{(\tau)}$ describes the reachability of
${\omega}_{k_{\tau}}^{(\tau)}$ with “a robot $r_{i}$ will go to the position
of action $e_{k}\in E_{k}$ if and only if it finds that the previous action
$\omega_{k_{\tau}}^{(\tau-1)}$ has been completed”. Thus, it requires each
$\pi_{k_{\tau}}^{(\tau)}$ to be conducted before $\omega_{k_{\tau}}^{(\tau)}$.
The motion specification can guarantee the actions to be conducted in a logic
sequence by robots in the decentralized multi-robot motion planning, and every
robot obtains the information about completion of action
$\omega_{k_{\tau}}^{(\tau-1)}$ by traveling to the location itself.

######  Definition 5 (Product Automaton of Robot).

Given an automaton $A=\left(X,E,f,x_{0},X_{m}\right)$ and a robot transition
system $TS=\left(Q,\delta,q_{init},\pi,L_{q},W_{q}\right)$. We define the
product automaton $\mathcal{P}=TS\times
A=(\hat{X},E,\hat{f},\hat{x}_{0},\hat{X}_{m},W_{q})$, where

  1. 1.

$\hat{X}=Q\times X$ is the state set,

  2. 2.

$E$ is the event set for the transitions,

  3. 3.

$\hat{f}(\hat{x},e^{\prime})=\hat{x}^{\prime}$ is the transition relation with
$\hat{x}=(q,x),~{}\hat{x}^{\prime}=(q^{\prime},x^{\prime})$, $q\rightarrow
q^{\prime},~{}f(x,e^{\prime})=x^{\prime}$, where $q,q^{\prime}\in Q$ and
$x,x^{\prime}\in X$,

  4. 4.

$\hat{x}_{0}=(q_{init},x_{0})$ is the initial state, $\hat{X}_{m}=Q\times
X_{m}$ is the final state set,

  5. 5.

$W_{q}$ is the cost set for the transitions in $\delta$.

The transition system of robot $r_{i}$ is abstracted as $TS_{i,k}^{(\tau)}$
for each action $e_{k}\in E_{k}$ it is going to perform at step $\tau$ in the
discrete space (e.g. see Figure 3). $\mathcal{A}_{k,i}^{(\tau)}$ is an
automaton representation of the motion specification $\pi_{k_{\tau}}^{(\tau)}$
of robot $r_{i}$ regarding subtask automaton $G_{k}$. The model checking
$TS_{i,k}^{(\tau)}\times\mathcal{A}_{k,i}^{(\tau)}$ can provide a motion
planning path $\sigma_{i,k}^{(\tau)}$ satisfying a motion specification
$\pi_{k_{\tau}}^{(\tau)}$.

Collision avoidance can be dealt within the transition system through a
reactive approach. Each robot $r_{i}$ detects its abstracted surrounding area
and stores the detected obstacles in the obstacle set $Obs_{i}^{(t)}$. These
robots regard the obstacles as inaccessible states in its transition system
$TS_{i,k}^{(\tau)}$. In addition, neighboring robots in communication ranges
are required to exchange the information of respective obstacles and next
states. The transition system is updated after the robot completes the current
allocated task or detects new obstacles.

##  4 Human-Robot Trust Model of Task Allocation

###  4.1 DBN based Human-Robot Trust Model

The human-robot trust model is developed to improve the task allocation and
motion planning of MRS to be similar as human decision-making. The trust
evaluation of human in each robot is involved with robot performance, risk of
occurrence of malfunctioning, and human cognitive workload. The robot
performance evaluation is dependent on the amount of tasks completed and the
success of obstacle collision avoidance. Risks are defined as the occurrence
of malfunctioning situations such as robots are unable to move or perform
tasks due to low battery level. The cognitive workload is related with the
complexity of surrounding environment, such as the amount of surrounded
obstacles of each robot, as well as the amount of robots that human has to
supervise after a task reallocation. These are all the possible factors that
may influence human’s interaction with multi-robot task allocation and motion
planning. Hence, it is favorable for the MRS to have a human-robot trust model
to integrate all these factors in order to enable human-like decision-making
for task allocation.

Besides the above influence from MRS, human and environment, we also consider
system-wide trust based influence (either positive or negative) into human-
robot trust evaluation regarding task reallocation. That is, robots assigned
with an action in the task reallocation will be given an opposite trust
evaluation with other robots that have a common implementable action but are
not selected for this action. Such influence on MRS will construct a system-
wide trust inter-relationship among robots. Finally, we will utilize a DBN
based human-robot trust model to assist MRS in task (re)allocation and motion
planning. Human will be intermittently inquired whether to allow a task
reallocation with this model.

The DBN trust model111The DBN human-robot model in this paper deals with the
human input with respect to each robot individually. In our future work, we
will determine the human input based on the trust of all robots involved in
task allocation. is shown in Figure 2. Based on the DBN model, we denote the
belief update of trust $T_{i}(t)$ for robot $r_{i}$ as

$\displaystyle\begin{split}bel(T_{i}(t))=&\textrm{Prob}(T_{i}(t)|P_{R,i}(1:t),a_{i}(1:t),U_{i}(1:t),\\\
&Br_{i}(1:t),Ac_{i}(1:t),h_{i}(1:t),T_{i}(0)),\end{split}$ (1)

where $\left[P_{R,i},a_{i},U_{i},Br_{i},Ac_{i}\right]^{T}$ are the impacting
factors of the hidden trust state, denoted by $\Omega_{i}$, and $h_{i}$ is the
observed evidence. To be more specific, $P_{R,i}(\cdot)$ is the accumulated
performance evaluation of robot $r_{i}$, $a_{i}(\cdot)\in[0,1]$ is the safety
coefficient of risk evaluation, $U_{i}(\cdot)$ is the human cognitive workload
due to the obstacle-crowded environment, $Br_{i}(\cdot)$ is the human
cognitive workload on supervising the MRS (e.g., monitoring multiple robots
decided by the task allocation), $Ac_{i}(\cdot)$ is the extra positive or
negative influence on the robots after human accepting of the task
(re)allocation. $h_{i}(\cdot)$ is the human intervention on whether to allow a
task reallocation for the MRS. Note that $Br_{i}(\cdot)$, $Ac_{i}(\cdot)$ and
$h_{i}(\cdot)$ are only intermittently updated when a task reallocation
occurs.

$\displaystyle\begin{split}\Omega_{i}(t)=\begin{cases}\left[P_{R,i}(t),a_{i}(t),U_{i}(t),Br_{i}(t)\right]^{T},\text{
if no reallocation}\\\
\left[P_{R,i}(t),a_{i}(t),U_{i}(t),Br_{i}(t),Ac_{i}(id)\right]^{T},\textrm{
otherwise}\\\ \end{cases},\end{split}$ (2)

Figure 2: A dynamic Bayesian network (DBN) based model for dynamic,
quantitative, and probabilistic trust estimates.

A forward algorithm is utilized by applying the principle of dynamic
programming to avoid incurring exponential computation time due to the
increase of $t$. Eqn. (1) can be calculated as

$\displaystyle
bel(T_{i}(t))=\frac{\int\overline{bel}(T_{i}(t),T_{i}(t-1))\textrm{d}T_{i}(t-1)}{\int\int\overline{bel}(T_{i}(t),T_{i}(t-1))\textrm{d}T_{i}(t-1)\textrm{d}T_{i}(t)},$
(3)

where

$\displaystyle\begin{split}\overline{bel}(&T_{i}(t),T_{i}(t-1))=\textrm{Prob}(h_{i}(t)|T_{i}(t),T_{i}(t-1))\cdot\\\
&\textrm{Prob}(T_{i}(t)|T_{i}(t-1),\Omega_{i}(t),\Omega_{i}(t-1))\cdot
bel(T_{i}(t-1)),\end{split}$ (4)

To obtain the belief update of each robot trust,
$\textrm{Prob}(h_{i}(t)|T_{i}(t),T_{i}(t-1))$ and
$\textrm{Prob}(T_{i}(t)|T_{i}(t-1),\Omega_{i}(t),\Omega_{i}(t-1))$ are
respectively calculated with different distribution models as shown in the
upcoming paragraphs.

The term $\textrm{Prob}(h_{i}(t)|T_{i}(t),T_{i}(t-1))$ is the conditional
probability of human intervention given the current and prior trust, which can
follow a similar sigmoid distribution as in [14]. Therefore, the conditional
probability distribution (CPD) of human intervention based on trust can be
modeled as follows

$\begin{split}\textrm{Prob}(h_{i}(t)=&1|T_{i}(t),T_{i}(t-1))=\frac{1}{1+exp(-\alpha_{1}T_{i}(t)+\alpha_{2}T_{i}(t-1))},\end{split}$
(5)

where $\alpha_{1}$ and $\alpha_{2}$ are positive weights and this CPD
indicates higher willingness for human to allow a task reallocation when
human-robot trust value is higher.

The CPD of human trust in robot $r_{i}$ at time $t$ can be constructed based
on the previous trust value, robot performance, risk coefficient, human
cognitive workload, and task allocation evaluation. It is expressed as a
Gaussian distribution with mean value $\bar{T}_{i}(t)$ and variance
$\rho_{i}(t)$,

$\displaystyle\begin{split}\textrm{Prob}(T_{i}&(t)|T_{i}(t-1),\Omega_{i}(t),\Omega_{i}(t-1))=\mathcal{N}(T_{i}(t);\bar{T}_{i}(t),\rho_{i}(t)),\\\
\bar{T}_{i}(t)=&A\cdot\bar{T}_{i}(t-1)+B_{1}\cdot a_{i}(t)\cdot
P_{R,i}(t)-B_{2}\cdot a_{i}(t-1)\cdot P_{R,i}(t-\\\ &1)+C_{1}\cdot
U_{i}(t)-C_{2}\cdot U_{i}(t-1)+D_{1}\cdot Br_{i}(t)-D_{2}\cdot Br_{i}(t\\\
&-1)+E_{1}\cdot Ac_{i}(id)-E_{2}\cdot Ac_{i}(id^{\prime}),\end{split}$ (6)

where $\bar{T}_{i}(t)\in(0,1)$ represents the mean value of human trust in
robot $r_{i}$ at time $t$, and $\rho_{i}(t)$ reflects the variance in each
individual’s trust update. Each parameter is evaluated with a function of
respective influence factors in task allocation and motion planning. The
coefficients $A,B_{1},B_{2},C_{1},C_{2},D_{1},D_{2},E_{1},E_{2}$ are
determined by data collected from human subject tests [15].

In our scenario, the accumulated performance evaluation $P_{R,i}(t)$ is
modeled as a function of rewards on robot for its completion of actions as
well as the avoidance of obstacles,

$\displaystyle\begin{split}P_{R,i}(t)&=P_{R,i}(t-1)+w(r_{i},\hat{e}_{k},t)+\beta_{i}(t)\cdot
w(o^{(t)}_{i}),\\\ \end{split}$ (7)

where $P_{R,i}(t-1)$ is the performance of robot at $t-1$,
$w(r_{i},\hat{e}_{k},t)\in\\{0,1\\}$ is the reward on robot $r_{i}$ for
completing an action $\hat{e}_{k}\in E_{k}$, $w(o^{(t)}_{i})\in\\{0,1\\}$ is
the reward on robot for avoiding a detected obstacle $o^{(t)}_{k}$ at $t$,
$\beta_{i}(t)$ is the number of obstacles the robot can avoid by re-planning
path at $t$. The safety coefficient $a_{i}(t)$ is introduced to evaluate the
potential of a single robot in completing all the capable actions in
$E_{r_{i}}$. Here, the risk of malfunction refers to the possibility of low
battery level of the robot, which may constrain it to perform more actions and
thus need other robots to substitute it for the remaining uncompleted actions.
The safety coefficient $a_{i}(t)$ is constructed as

$a_{i}(t)=\begin{cases}1,&~{}r_{i}\text{ is in normal state}\\\
\frac{1}{|E_{r_{i}|}},&~{}r_{i}\text{ is in low battery state}\end{cases}.$
(8)

This implies the system tends to trust the robot to complete all its capable
actions if it has enough electric capacity. On the other hand, if the battery
level is low, the robot is assigned to at most complete the current allocated
action.

The human cognitive workload is a result of interaction with the complex
environment and multiple robots. For the environmental complexity resulted
workload, it is constructed as

$U_{i}(t)=1-\gamma(t)^{S_{o,i}(t)+1},$ (9)

where $S_{o,i}(t)$ is the number of obstacles within sensing range of robot,
and $\gamma(t)$ is the utilization ratio [16, 17]. The human cognitive
workload resulted from supervising robots always exists but is only updated
after a task reallocation is implemented. It is estimated by the amount of
robots that human can deal with as well as the actual activated robots in the
supervision of a MRS. It is intermittently updated based on the $id$th task
reallocation as

$Br_{i}(t)=\begin{cases}1-I_{act}(id)/I_{\max},&\text{if $r_{i}$ is
activated}\\\ 1,&\text{otherwise}\end{cases},$ (10)

where $I_{act}(id)$ is the actual amount of activated robots in this task
reallocation, and $I_{\max}$ is the maximal number of robots that human feels
comfortable in supervising the MRS. Each robot will be updated the same
workload with the system-wide trust theory if it is activated in the task
(re)allocation, while $Br_{i}(t)=1$ if the robot is not activated at all.

The extra positive or negative influence of task reallocation on each robot
also works according to the system-wide trust theory after human accepts a
task reallocation solution. Recall that each robot has a task reallocation
path
${s}_{\psi,i}={\omega}_{k_{0}}^{(0)}\cdots{\omega}_{k_{\tau}}^{(\tau)}\cdots{\omega}_{k_{\mathbf{T}}}^{(\mathbf{T})}$.
Opposite influences can be enforced on the following situation: (1) the action
in path ${s}_{\psi,i}$ is an implementable action of $r_{i}$, and (2) the
implementable action of $r_{i}$ is not selected in the current task
allocation. As a result, an extra influence of $id$th task reallocation on
each robot is constructed as

$\displaystyle\begin{split}Ac_{i}(id)=&\sum_{\tau=0}^{\mathbf{T}}ac_{i}(\tau),\\\
ac_{i}(\tau)=&\begin{cases}\mu/I,&\text{if
${\omega}_{k_{\tau}}^{(\tau)}=IA_{i,k}(\tau)$}\\\ \overline{\mu}/I,&\text{if
${\omega}_{k_{\tau}}^{(\tau)}\neq IA_{i,k}(\tau)$}\end{cases},\end{split}$
(11)

where $ac_{i}(\tau)$ is the positive or negative influence of each action in
task reallocation path on robot $r_{i}$, $\mu>0$ and $\overline{\mu}<0$ are
the influence coefficients. If the action in task reallocation path is an
implementable action of $r_{i}$, a positive influence will be added for this
robot, which implies a trust increase of this robot in the current task
reallocation; A negative influence will be associated to a robot by decreasing
the trust of the robot if the implementable action of the robot is not
selected in the current task allocation.

######  Remark 2.

The network parameters for the DBN such as $\alpha_{1}$, $\alpha_{2}$ in
Equation (5) can be learned by the well-known expectation maximization (EM)
algorithm [18] off-line during the training session and hence will not affect
the functionality of the system and the user experience in real-time
operation. Besides, a separate and personalized trust model should be trained
based on each user’s experience since the model strongly depends on individual
human intervention $h_{i}(\cdot)$ as well as the impacting factors
$\left[P_{R,i}(\cdot),a_{i}(\cdot),U_{i}(\cdot),E_{H,i}(\cdot),Ac_{i}(\cdot)\right]$.

###  4.2 Human-Robot Trust based Real-time Interactive Task Reallocation and
Motion Re-planning

Human trust in robot can be updated at each time step $t$ or intermittently
after a task reallocation of MRS. Consequently, the previous maximum trust
encoded task allocation and motion planning solution need to be updated.

The reallocation request is triggered after an action is completed by a robot
in the MRS and the human-robot trust is higher enough. Human works as a
supervisor and will be inquired if he/she would like to have a task
reallocation. The system will reallocate the actions to robots and re-plan the
motion path of individual robot if human allows to have a task reallocation.
The task reallocation will be implemented on these uncompleted actions, i.e. a
task allocation automaton is re-synthesized with the unperformed actions
constituted state set. As a result, a new maximum trust encoded path is
generated from this automaton for the remaining task. In the mean time, the
human trust in each activated robot will be changed with $Ac_{i}(id)$ from a
system-wide trust perspective. However, if human refuses the task
reallocation, the MRS will continue the previous task allocation and motion
planning path. On the other hand, the human-robot trust model will be
continuously updated for robot performance, safety coefficient, and human
cognitive workload estimations while the robot is exploring in the work space.
Algorithm $1$ describes the complete process of human-robot trust model based
interactive task allocation and motion planning. The process is iterated until
all actions are completed.

Initial task allocation $\mathbb{S}_{\psi,0}$;

Update influence $Ac_{i}(0)$, trust $T_{i}(t)$ for $r_{i}\in\mathcal{I}$;

while  _Exist unperformed actions_ do

if  _An action completed_ then

Update $P_{R,i}(t),a_{i}(t),U_{i}(t),Br_{i}(t),T_{i}(t)$;

if  _Allow reallocation_ then

Task reallocation $\mathbb{S}_{\psi,\tau}$;

Update $Ac_{i}(id),T_{i}(t)$;

Motion planning $\sigma_{i}$ for all $r_{i}$;

end if

end if

Execute motions and actions;

Update $P_{R,i}(t),a_{i}(t),U_{i}(t),T_{i}(t)$;

end while

Algorithm 1 Human-robot trust integrated task (re)allocation and SMP

##  5 Simulation

###  5.1 System Configuration and Task Specification

The workspace of MRS is abstracted as a $10\times 10$ grid environment
occupied with obstacles and task stations as shown in Figure 3. Each task
station is associated with an action that needs a robot to perform. In the
SMP, we assume the motion primitives of each robot are the abstracted from one
grid to its adjacent four grids (north, east, south and west). A robot is also
assumed to be unable to enter into grids that are partially or totally taken
by obstacles. The linear quadratic regulator (LQR) is utilized to control the
motion of robots between two grids.

Figure 3: Abstracted workspace and paths of motion planning where
“$\boxtimes$” marks the obstacle and “$\bigstar$” marks the allocated task for
each robot.

3 parallel subtasks are to be allocated for MRS, each of the subtask is
described by an automaton, see Figure 4. The languages of the 3 subtask
automata are $L(G_{1})=\\{abc,acb\\}$, $L(G_{2})=\\{de\\}$, and
$L(G_{3})=\\{f,gf\\}$. A team of 5 robots $r_{i},~{}i=1,\cdots,5$ are assigned
to perform the actions in the 3 parallel subtasks. Each robot is associated
with its capability: $Er_{1}=\\{a,c,d\\}$, $Er_{2}=\\{b,e,f\\}$,
$Er_{3}=\\{a,f,g\\}$, $Er_{4}=\\{b,d,g\\}$, and $Er_{5}=\\{c,e\\}$. In
addition, we assume omni-directional sensors and set as two-grid length. The
communication radius is set as the same length.

Figure 4: Parallel subtask automata $G_{1}$, $G_{2}$ and $G_{3}$.

###  5.2 Results

The final motion paths of robots are shown in Figure 3. The corresponding
trust change of each robot is shown in Figure 5.

(a) Color bar of trust distribution

(b) Trust distribution of $r_{1}$

(c) Trust distribution of $r_{2}$

(d) Trust distribution of $r_{3}$

(e) Trust distribution of $r_{4}$

(f) Trust distribution of $r_{5}$

Figure 5: Evolution of trust distribution of each robot. Black curves are the
maximum values of trust distribution.

The initial generated task allocation path is
$\mathbb{S}_{\psi}=((r_{3},a),(r_{1},d),(r_{4},g))^{(0)}((r_{4},b),(r_{5},e),(r_{3},f))^{(1)}((r_{1},c),\mathcal{E},\mathcal{E})^{(2)}$.
The task allocation mappings into each robot are
$s_{\psi,1}=(r_{1},d)^{(0)}(r_{1},c)^{(2)}$,
$s_{\psi,3}=(r_{3},a)^{(0)}(r_{3},f)^{(1)}$,
$s_{\psi,4}=(r_{4},g)^{(0)}(r_{4},b)^{(1)}$ and $s_{\psi,5}=(r_{5},e)^{(1)}$.
As a result, the trust of each robot will be updated regarding the positive or
negative influence of task allocation on each robot.

Actions $(r_{4},g),~{}(r_{1},d),~{}(r_{5},e),~{}(r_{3},a)$ are first
sequentially completed with reference to the current task allocation solution
and motion specification. Each robot verifies the completion state of actions
that need to be performed before their current allocated actions in the
subtask automaton. The results are demonstrated in Figure 3, where robot
$r_{4}$, $r_{5}$ and $r_{3}$ first go to the neighboring positions of a, d,
and g respectively (i.e. within the robot’s sensing range) to detect the
completion states before they perform the current allocated actions. The
action $a$ is almost completed by robot $r_{3}$ at the same time with
$(r_{5},e)$. The rewards in performance evaluation of each robot are updated
immediately after they completed each assigned actions, and the cognitive
workload is also updated during the robot exploration. A reallocation inquiry
is triggered after robot $r_{5}$ completes its only assigned action $e$. The
reallocation is synthesized for the remaining subtasks $L(G_{1})=\\{c\\}$ and
$L(G_{3})=\\{f\\}$, while action $b$ is still performed by $r_{4}$ considering
the robot’s previous effort. The reallocation moment is at $110$ time step,
and trust change of each robot is demonstrated in the trust distribution in
Figure 5. The maximum trust value of each robot before the reallocation are
shown in Table 1.

Table 1: Maximum trust of each robot before task reallocation. robot | 1 | 2 | 3 | 4 | 5
---|---|---|---|---|---
Max trust | 0.3566 | 0.3167 | 0.2818 | 0.3267 | 0.3666

The robots that enable the task allocation associated with the highest
accumulated trust are selected to perform the remaining actions. According to
the maximum trust value table above, robot $r_{2}$ and $r_{5}$ are selected
respectively to perform action $f$ and $c$ rather than $r_{3}$ and $r_{1}$.
The updated task allocation path is
$\mathbb{S}^{\prime}_{\psi}=((r_{3},a)(r_{1},d)(r_{4},g))^{(0)}((r_{4},b),(r_{5},e),(r_{2},f))^{(1)}((r_{5},c),\mathcal{E},\mathcal{E})^{(2)}$.
The newly assigned task allocation mapping into each robot are
$s_{\psi,2}=(r_{2},f)^{(1)}$, $s_{\psi,4}=(r_{4},b)^{(1)}$ and
$s_{\psi,5}=(r_{5},c)^{(2)}$. Since human accepted the reallocation, the
positive or negative trust influence on each robot get updated. Eventually,
the MRS completes the remaining actions with this updated solution.

##  6 Conclusion

This paper presents a human supervised task allocation and motion planning
framework for MRS to perform multiple parallel subtasks in a human-like
decision making manner. These subtasks are described by automata and
conjuncted with MRS to synthesize a task allocation automaton. Transitions of
task allocation automaton are associated with the estimations of robot
performance and human cognitive workload. They are combined with a DBN human-
robot trust model and a maximal trust encoded task allocation path can be
found. This path reflects the maximum trust of human in task assignment of
MRS. Symbolic motion planning (SMP) is implemented for each robot after the
task allocation. The task reallocation is triggered after an action being
completed with human permission. The above process is demonstrated to be
effective for MRS task allocation by a simulation with 5 robots and 3 parallel
subtasks.

## References

  * [1] Belta, C., Bicchi, A., Egerstedt, M., Frazzoli, E., Klavins, E., and Pappas, G. J., 2007.  “Symbolic planning and control of robot motion [grand challenges of robotics]”.  IEEE Robotics & Automation Magazine,  14(1), pp. 61–70.
  * [2] Saha, I., Ramaithitima, R., Kumar, V., Pappas, G. J., and Seshia, S. A., 2014.  “Automated composition of motion primitives for multi-robot systems from safe ltl specifications”.  In Intelligent Robots and Systems (IROS 2014), 2014 IEEE/RSJ International Conference on, IEEE, pp. 1525–1532.
  * [3] Tumova, J., and Dimarogonas, D. V., 2015.  “Decomposition of multi-agent planning under distributed motion and task ltl specifications”.  In Decision and Control (CDC), 2015 IEEE 54th Annual Conference on, IEEE, pp. 7448–7453.
  * [4] Guo, M., and Dimarogonas, D. V., 2015.  “Multi-agent plan reconfiguration under local ltl specifications”.  The International Journal of Robotics Research,  34(2), pp. 218–235.
  * [5] Guo, M., and Dimarogonas, D. V., 2017.  “Task and motion coordination for heterogeneous multiagent systems with loosely coupled local tasks”.  IEEE Transactions on Automation Science and Engineering,  14(2), pp. 797–808.
  * [6] Ding, X. C., Kloetzer, M., Chen, Y., and Belta, C., 2011.  “Automatic deployment of robotic teams”.  IEEE Robotics & Automation Magazine,  18(3), pp. 75–86.
  * [7] Chen, Y., Ding, X. C., Stefanescu, A., and Belta, C., 2012.  “Formal approach to the deployment of distributed robotic teams”.  IEEE Transactions on Robotics,  28(1), pp. 158–171.
  * [8] Dai, J., Benini, A., Lin, H., Antsaklis, P. J., Rutherford, M. J., and Valavanis, K. P., 2016.  “Learning-based formal synthesis of cooperative multi-agent systems with an application to robotic coordination”.  In Control and Automation (MED), 2016 24th Mediterranean Conference on, IEEE, pp. 1008–1013.
  * [9] Kruijff, G.-J. M., Kruijff-Korbayová, I., Keshavdas, S., Larochelle, B., Janíček, M., Colas, F., Liu, M., Pomerleau, F., Siegwart, R., Neerincx, M. A., et al., 2014.  “Designing, developing, and deploying systems to support human–robot teams in disaster response”.  Advanced Robotics,  28(23), pp. 1547–1570.
  * [10] Shah, J., and Breazeal, C., 2010.  “An empirical analysis of team coordination behaviors and action planning with application to human–robot teaming”.  Human factors,  52(2), pp. 234–245.
  * [11] Nikolaidis, S., and Shah, J., 2012.  “Human-robot teaming using shared mental models”.  ACM/IEEE HRI.
  * [12] Vinod, A. P., Tang, Y., Oishi, M. M., Sycara, K., Lebiere, C., and Lewis, M., 2016\.  “Validation of cognitive models for collaborative hybrid systems with discrete human input”.  In Intelligent Robots and Systems (IROS), 2016 IEEE/RSJ International Conference on, IEEE, pp. 3339–3346.
  * [13] Chen, M., Nikolaidis, S., Soh, H., Hsu, D., and Srinivasa, S., 2018.  “Planning with trust for human-robot collaboration”.  arXiv preprint arXiv:1801.04099.
  * [14] Xu, A., and Dudek, G., 2015.  “Optimo: Online probabilistic trust inference model for asymmetric human-robot collaborations”.  In Proceedings of Tenth ACM/IEEE International Conference on Human-Robot Interaction, ACM, pp. 221–228.
  * [15] Sadrfaridpour, B., Saeidi, H., Burke, J., Madathil, K., and Wang, Y., 2015.  “Modeling and control of trust in human-robot collaborative manufacturing”.  In The Intersection of Robust Intelligence (RI) and Trust in Autonomous Systems. Springer.
  * [16] Spencer, D. A., and Wang, Y., 2015.  “Slqr suboptimal human-robot collaborative guidance and navigation for autonomous underwater vehicles”.  In American Control Conference (ACC), 2015, IEEE, pp. 2131–2136.
  * [17] Wang, Y., Humphrey, L., Liao, Z., and Zheng, H., 2018.  “Trust-based multi-robot symbolic motion planning with a human-in-the-loop”.  ACM Transactions on Interactive Intelligent Systems.
  * [18] Moon, T. K., 1996.  “The expectation-maximization algorithm”.  Signal processing magazine, IEEE,  13(6), pp. 47–60.