#  Distributed Task Allocation in Homogeneous Swarms Using Language Measure
Theory

Devesh K. Jha† MERL, Cambridge, MA, USA
† Email<EMAIL_ADDRESS>
###### Abstract

In this paper, we present algorithms for synthesizing controllers to
distribute a group (possibly swarms) of homogeneous robots (agents) over
heterogeneous tasks which are operated in parallel. We present algorithms as
well as analysis for global and local-feedback-based controller for the
swarms. Using ergodicity property of irreducible Markov chains, we design a
controller for global swarm control. Furthermore, to provide some degree of
autonomy to the agents, we augment this global controller by a local feedback-
based controller using Language measure theory. We provide analysis of the
proposed algorithms to show their correctness. Numerical experiments are shown
to illustrate the performance of the proposed algorithms.

##  I Introduction

Swarms of robots are increasingly becoming popular with recent advances in
design of embedded processor. These are, in general, designed to perform
different complex tasks in a coordinated manner. Some important examples are
fleets of unmanned vehicles deployed in ocean bed for the purposes of mine-
hunting or surveillance or drug delivery techniques in humans using micro-
scale robots at pre-specified rate and locations [1, 2]. A common element in
all these applications is a desirable global behavior which can be achieved
where the individual behavior is achieved by the agents themselves and thus,
is not considered during global policy design. In these large-scale systems,
it is difficult to design controller for each agent (or robot) individually
and then coordinate their behavior due to computational requirements. A
critical challenge for these distributed systems is to guarantee stability and
performance with limited global information. In this paper, we are interested
in design and analysis of controllers for controlling global states of a
large-scale system with the assumption that each of the individual agents are
controllable. Such a controller could be designed using a multi-agent motion
planning algorithm [3, 4].

Following our previous work in [5], we model swarm of robots (which we also
interchangeably call agents) as a homogeneous collection of irreducible Markov
chains. The states of the Markov chain are the heterogeneous tasks that are
operated in parallel. The state of the system (swarm) is defined by the
distribution of agents over the tasks. A desired system state is then the
desired distribution of agents over the heterogeneous tasks. The control
problem is to design a policy that the agents can follow to transition between
the tasks so that the distribution of agents over tasks converges to the
desired distribution. Consequently, the swarm control problem is reduced to
achieving a desired probability stationary distribution of the Markov chain.
The design problem is to synthesize the transition kernel for the Markov chain
with a pre-specified stationary distribution over its states. We present a
closed-form solution to estimate a transition kernel for a Markov chain with a
known stationary distribution. We compute a state transition matrix to serve
as the global policy for the agents– agents transition between states using
this global policy. This policy guarantees convergence to the desired global
state. The agents then calculate the expected reward of moving to a different
task against staying in their current task based on the excess or deficit of
agents in the current and neighboring states. This local policy of an agent is
calculated as a perturbation to its global policy which is computed using
Language measure theory of Probabilistic Finite State Automata (PFSA) [6, 7,
8]. It is noted that in the following text we often call transition matrix as
Markov kernel even though kernels are generally defined for continuous state-
space (and our problem is discrete).

Contributions: An initial conference version of the paper was presented in
[5]. This paper has the following contributions over the previous publication.

  1. 1.

We present analysis of the algorithms for centralized as well as design of
stable local controllers for swarm control.

  2. 2.

We present empirical results about performance and stability of the proposed
controllers. We provide some empirical evidence about choice of parameters for
such a controller.

For the completeness of this work, we provide a full problem description which
was also described earlier in [5].

##  II Related Work

Traditionally, swarm control has been studied under two broad categories:
centralized control with global information, where the controller broadcasts
the policies to the swarm and decentralized control where some bio-inspired
collective behavior laws are used to replicate social behavior in nature [9].
A lot of work has been done in swarm control addressing issues of centralized
and decentralized control. Some examples of centralized control could be found
in [10, 11, 12, 13, 14, 15, 16]. The common idea in the centralized control
techniques is to synthesize stochastic policy for agents which they can use to
switch between the tasks such that the system is driven to the desired steady
distribution of agents over the tasks. This approach has the shortcomings that
we need global state information. Moreover, controller synthesis becomes
restrictive for large systems with large number of states or tasks.
Furthermore, it is difficult to make such a system react to local un-modeled
dynamics and other disturbances.

These restrictions have driven a lot of research effort in distributed control
approaches to circumvent the shortcomings of the centralized approaches. Some
distributed control approaches for swarm control could be found in [17, 18,
19, 20, 21, 22, 23, 9]. Most of the distributed strategies for swarm control
involve using bio-inspired logic to design reactive controllers for desired
global behavior. This work is motivated by the idea that we can augment the
centralized controller by a state-dependent feedback strategy so that the
agents can use the centralized control strategy with limited perturbation from
the same; the perturbation in the strategy depends on the current state of an
agent and the desired steady state of the system. The distributed state-
information-based feedback control leads to a time-varying stochastic linear
system. Such time varying stochastic analysis has been been extensively
presented in consensus literature [24, 25].

While our current problem is mainly motivated and closest to earlier work in
[11], the central control problem is similar to previous work in [15]. The
decentralized control problem is similar to the solution earlier presented in
[18]. We present a simplified solution to similar problems studied in these
previous papers. The proposed work presents a novel solution using language
measure theory and shows some analysis for the stability of the resulting
controller.

An initial version of this work was earlier presented at a conference [5].
However, in the current paper we present the proof for the correctness of the
centralized algorithm which was missing in [5]. Furthermore, we show that the
distributed framework can get stuck in limit cyclic (or oscillatory) behavior
if the feedback gains are not chosen appropriately. We provide a proof sketch
for the stability of the distributed system and show some empirical results to
demonstrate its correctness. We present several new empirical results
regarding stability of the distributed system that depends on controller
parameters. We believe that the current work provides more insight to the
whole framework than the preliminary version.

##  III Problem Formulation

Consider a set of $N$ robots to be allocated among $M$ heterogeneous tasks
which are operated in parallel. The number of robots performing task
$i\in\\{1,\dots,M\\}$ at a time epoch $k$ is denoted by $n_{i}^{[k]}$ . The
desired number of robots for task $i$ is denoted by $n^{d}_{i}$. We assume
that $n_{i}^{d}>0$ for all $i\in\\{1,\dots,M\\}$. Then, to make the system
scalable in the number of agents, we define the population fraction at any
task $i$ as $p^{[k]}_{i}=n_{i}^{[k]}/N$. The state of the swarm is then
defined as $\mathbf{p}^{[k]}=[p_{1}^{[k]},\dots,p_{M}^{[k]}]$. The desired
state of the swarm is given by the fraction of agents at the individual tasks
which is denoted by the vector $\mathbf{p}^{d}=[p_{1}^{d},\dots,p_{M}^{d}]$.
It is noted that since $n_{i}^{d}>0$ $\forall i\in\\{1,2,,\dots,M\\}$, thus we
have that $p_{i}^{d}>0\,\forall\,i\in\\{1,\dots,M\\}$.

######  Assumption III.1.

$|Q|=M<\infty$ i.e., the number of tasks operated in parallel are finite.

Next we formalize the definition of an agent and swarm before we state the
formal problem.

######  Definition III.1.

(Agent in Swarm Modeling): An agent is a connected digraph $R=(Q,E)$, where
each state $i\in Q$ represents a distinct predefined behavior (i.e., a
heterogeneous task), and $E\in\\{0,1\\}^{|Q|\times|Q|}$ is a matrix such that
$E_{ij}=1$ implies there exist a controllable transition from state $i$ to $j$
(implying the connectivity of the tasks).

The matrix $E$ in Definition III.1 specifies state transitions of the agent
$R$’s state. An agent can only transition to the tasks it is directly
connected with in a single hop (or a controllable movement). It is possible to
associate probabilities with the transition of an agent between tasks based on
the requirements at the tasks or the preference of the robot. The
probabilities of the state transitions constitute a finite-state irreducible
Markov chain, with the irreducibility property following from the
connectedness of the agent graph. Thus the behavior of an agent can be
represented by an irreducible Markov chain
$G=(Q,\textbf{P},\mathbf{p}^{[0]})$, where P represents a stochastic matrix
such that $\textbf{P}_{ij}>0$ if and only if $E_{ij}=1$; $\mathbf{p}^{[0]}$
represents its initial state (which could be a one-hot vector representing the
initial task of the agent). The swarm is a collection of such agents, and thus
could be denoted as $\mathds{S}=\\{G^{\alpha}:\alpha\in\mathbb{X}\\}$, such
that $G^{\alpha}=G$, and $\mathbb{X}$ is an index set (finite, countable or
uncountable). Consequently, the state of the swarm is defined by the
distribution of robots over the tasks i.e., $\mathbf{p}^{[k]}$. The swarm
dynamics is represented by the following equation:

$\mathbf{p}^{[k+1]}=\mathbf{p}^{[k]}\textbf{P}$ (1)

where $\textbf{P}_{ij}$ represents the probability with which an agent decides
to switch from task $i$ to task $j$.

###  III-A Central Controller Design

Consider a swarm of robots where the initial state of the swarm is
$\mathbf{p}^{[0]}$ and the desired state is represented by $\mathbf{p}^{d}$.
The goal of the central controller is to achieve the desired distribution of
agents over the tasks. This can be achieved in a probabilistic setting by
using a Markov kernel for transition between tasks such that the desired state
is the stationary distribution over the states of the swarm. Thus, given a
desired state distribution $\mathbf{p}^{d}$, the problem is to synthesize a
Markov kernel $\textbf{P}^{\star}$ given any initial kernel P such that the
following conditions hold.

  1. 1.

$\sum\limits_{j=1}^{M}\textbf{P}^{\star}_{ij}=1$ (i.e., the controller matrix
should be row stochastic).

  2. 2.

$\textbf{P}^{\star}_{ij}>0$ if and only if $\textbf{P}_{ij}>0$ for any $i,j$
$\in$ ${1,\dots,M}$.

  3. 3.

$\textbf{P}^{\star}$ is an irreducible matrix.

  4. 4.

$\lim\limits_{k\rightarrow\infty}\|\mathbf{p}^{[0]}(\textbf{P}^{\star})^{k}-\mathbf{p}^{d}\|_{\infty}=0$.

The initial kernel P contains the information about the connectivity of the
underlying tasks and one such kernel could be easily obtained by normalizing
the adjacency matrix for the swarm. It is noted that the second condition is
required to maintain the connectivity of the tasks that the agents are
supposed to perform. Irreducibility of $\textbf{P}^{\star}$ implies that the
limiting time average of the local state is independent of the initial
conditions. The last condition ensures the convergence to the desired
behavior. This defines the central control problem for swarm control.

###  III-B Central Control with Distributed Autonomy

The next problem is inspired by minimizing the movement of agents to achieve a
desired system state as well as during steady state after the desired state is
achieved ( due to energy limitations). For these considerations, we want to
have a local-information-based policy for the agents which could be calculated
as a perturbation to the central control policy $\textbf{P}^{\star}$. The
local communication-based information is used to calculate perturbations to
the Markov kernel calculated in the first step as a proportional feedback.
Given the state-dependent stochastic policy by the central controller, the
agents decide between following the central controller and staying in their
current state; this is decided as a function of deficit or excess of agents in
their current and neighboring tasks (states) when compared against the desired
distribution. The perturbed policy could be derived as a function of
$\mathbf{p}_{i}^{k}$, the desired state $\mathbf{p}^{d}_{i}$ and the
neighboring states $\mathbf{p}_{j}^{k}$ where $j$ is such that $E_{ij}=1$.
Then, it results in time varying stochastic policies for the agents depending
on their current state and local information. We denote the perturbed local
policies by $\tilde{\textbf{P}}^{[k]}$ at an instant $k$. Also, we want only
$\lambda$ fraction of the agents to switch between the tasks at steady state
when compared to the number of agents switching tasks under the central
policy. Then, the local-information-based perturbed policy has to satisfy the
following conditions.

  1. 1.

$\sum\limits_{j=1}^{M}\tilde{\textbf{P}}^{[k]}_{ij}=1$ (i.e., the resulting
matrix should be row stochastic at all instants).

  2. 2.

$\tilde{\textbf{P}}^{[k]}_{ij}>0$ if and only if $\textbf{P}^{\star}_{ij}>0$
for any $i,j$ $\in$ ${1,\dots,M}$..

  3. 3.

$\sum\limits_{j=1}^{|Q|}\tilde{\textbf{P}}^{[k]}_{ij}=1$.

  4. 4.

$\lim\limits_{k\rightarrow\infty}\|\mathbf{p}^{[0]}\tilde{\textbf{P}}^{[k]}\tilde{\textbf{P}}^{[k-1]}\dots\tilde{\textbf{P}}^{[0]}-\mathbf{p}^{d}\|_{\infty}=0$

  5. 5.

$\lim\limits_{k\rightarrow\infty}\tilde{\textbf{P}}^{[k]}_{ij}=\lambda\textbf{P}_{ij}^{\star}$
for $i\neq j$ and
$\lim\limits_{k\rightarrow\infty}\tilde{\textbf{P}}^{[k]}_{ii}=\lambda\textbf{P}_{ii}^{\star}+(1-\lambda)$

It is noted that the irreducibility of $\tilde{\textbf{P}}^{[k]}$ follows from
condition $(1)$ and the fact that $\textbf{P}^{\star}$ is an irreducible
matrix. At this point, we would like to clarify that condition $5$ implies
that the robots stay at the same task with an increased probability of
$(1-\lambda)$ and thus, the probability to switch task at any state is reduced
by fraction $\lambda$ (this defines the autonomy of individual agents).

Both problems are related to synthesis of Markov kernels such that the
stationary distribution of the underlying Markov chain achieves the desired
state of the swarm in the asymptotic limit. In the following sections, we
present solution as well as analysis of some of the proposed algorithms.

##  IV Proposed Algorithms and Analysis

In this section we present the proposed approach for estimation of the Markov
kernels described in section III.

###  IV-A Algorithm and Analysis for Central Controller Synthesis

This section presents an analytical solution to solve the control problem
described in section III-A. Let $\mathbf{p}^{d}$ be the desired state of the
swarm which begins in the state $\mathbf{p}^{[0]}$. Let P be an irreducible
stochastic matrix for $G$ and let $\tilde{\mathbf{p}}$ be its unique
stationary probability distribution vector. Then, a Markov kernel which
achieves the desired distribution over the swarm in the asymptotic limit could
be obtained using the following transformation of the matrix P.

$\textbf{P}_{ij}\longmapsto d_{i}\textbf{P}_{ij},i\neq j$
$\textbf{P}_{ij}\longmapsto d_{i}\textbf{P}_{ij}+(1-d_{i}),i=j$

where, $d_{i}\in(0,1)$ $\forall i\in\\{1,2,\dots,M\\}$ where the vector
$\mathbf{d}=[d_{1},\dots,d_{M}]$ is given by the following expression.

$[d_{1},\dots,d_{M}]=[\hat{d}_{1},\dots,\hat{d}_{M}]/\sum_{i=1}^{M}\hat{d}_{i}$
(2)

where
$[\hat{d}_{1},\dots,\hat{d}_{M}]=[p^{[0]}_{1},\dots,p^{[0]}_{M}]\mathbf{X}^{-1}$
where, $\mathbf{X}^{-1}={\rm diag}(p^{d}_{1},\dots,p^{d}_{M})^{-1}$. The
vector $\mathbf{p}^{d}$ and $\mathbf{p}^{[0]}$ denote the final and initial
distribution of the swarm, respectively. The vector $\mathbf{d}$ in equation
(2) gives the closed form solution to the iterative Algorithm 1 in [11]. This
helps in simplifying the controller synthesis complexity which is useful for
swarms with a large number of states. It is noted that the perturbations
preserve the original topology of the graph representing the connectivity of
the tasks. For convenience of presentation, the transformation is presented as
a psuedo-code in Algorithm 1. Clearly, the complexity of the Algorithm 1 is
$O(M)$ where $M$ is the size of the swarm.

Input: The initial stochastic transition matrix $\mathbf{P}$, the desired
probability $\mathbf{p}^{d}$.

Output: The global broadcast policy kernel $\mathbf{P}^{\star}$.

1 for  _$i\in\\{1,.\dots,M\\}$_ do

2 $\hat{d_{i}}=\frac{p^{[0]}_{i}}{p^{d}_{i}}$;

3for  _$i\in\\{1,.\dots,M\\}$_ do

4 Normalize $d_{i}=\frac{\hat{d_{i}}}{\sum_{i=1}^{M}\hat{d_{i}}}$;

_5_ return _$\\{d_{i}\\}_{i=1,\dots,M}$ ;_

6 return _$\mathbf{P}^{\star}=\tt{diag}(d)\mathbf{P}-\tt{diag}(d)+I$_
$\triangleright$ $\tt I$ represents the identity matrix of the same size as
$\mathbf{P}$

Algorithm 1 ${\tt EstimatingMarkovKernel}$

Next, we present the analysis of the above results to show its correctness.
The claim that we are going to prove is stated in Theorem IV.1. We first
present a lemma which is required to prove our main claim of this section.

######  Lemma IV.1.

We define a perturbation of an irreducible matrix P as follows:

$\hat{\mathbf{P}}=D\mathbf{P}-D+I{}$ (3)

where, $D=\rm{diag}(d_{i})\,i\in\\{1,\dots,M\\}$, where $d_{i}\in(0,1)$ and
$I$ is an identity matrix of size $M\times M$. Then $\hat{\mathbf{P}}$ is a
stochastic irreducible matrix.

###### Proof.

Clearly, $\mathbf{P}_{ij}\geq 0$. Since $D$ is a diagonal matrix, and $\Pi$ is
a stochastic matrix, we have

$\sum_{j}\hat{\mathbf{P}}_{ij}=a_{i}\sum_{j}\mathbf{P}_{ij}+(1-d_{i})=d_{i}+(1-d_{i})=1{}$
(4)

This shows that $\mathbf{P}$ is a stochastic matrix. We now show that
$\mathbf{P}$ is also irreducible. If we can show that $\hat{\mathbf{P}}$ has a
unique probability vector $\hat{{P}}$ that is element-wise positive, it would
imply $\hat{\mathbf{P}}$ is irreducible. Let $\tilde{{P}}$ be an element-wise
non-negative vector representing a direction in the eigen-space of
$\hat{\mathbf{P}}$ corresponding to its unity eigenvalue, i.e.,
$\tilde{{P}}[\hat{\mathbf{P}}-I]=0.$ Such a $\tilde{{P}}$ is guaranteed to
exist for any stochastic matrix. Equation (3) yields

$\tilde{{P}}[D\mathbf{P}-D+I-I]=0$ (5)
$\Rightarrow\tilde{{P}}D[\mathbf{P}-I]=0{}$ (6)

Since, $\mathbf{P}$ is an irreducible stochastic matrix, it has an unique
stationary probability vector, element-wise positive, ${P}$. From the
uniqueness of the probability vector ${P}$, it follows that,

$\tilde{{P}}D={P}.$ (7)

Define,

$\hat{{P}}=\frac{1}{\sum_{i}\tilde{{P}}_{i}}\tilde{{P}}{}$ (8)

where, $\tilde{{P}}={P}D^{-1}$. It is noted that $D$ is a diagonal matrix with
nonzero entries and hence invertible. Then, clearly, $\|\hat{P}\|_{1}=1$.
Also, $\hat{P}$ is unique (from equation 8), element-wise positive and it lies
in the eigen-space of the $\hat{\mathbf{P}}$ matrix corresponding to its unity
eigenvalue. Hence, the matrix $\hat{\mathbf{P}}$ is irreducible. ∎

######  Theorem IV.1.

Let $P^{\star}\in\mathds{R}^{M}$ be an element-wise positive probability
vector and let $\mathbf{P}\in\mathds{R}^{M\times M}$ be an irreducible
stochastic matrix with a stationary probability vector, $P$. Then, $\exists$ a
diagonal matrix $D\in\mathds{R}^{M\times M}$ with $D_{ii}\in(0,1)$ such that
$\mathbf{P}^{\star}=D\mathbf{P}-D+I$ is an irreducible stochastic matrix with
stationary probability vector $P^{\star}$.

###### Proof.

We first assume that such a $D$ matrix does exist and prove the claim by
finding one. So, let us assume such an $D$ matrix exist. Then,

$\mathbf{P}\mapsto D\mathbf{P}-D+I(=\mathbf{P}^{\star})$ (9)

such that,

$\displaystyle{P}^{\star}\mathbf{P}^{\star}={P}^{\star}$ (10)
$\displaystyle\Rightarrow{P}^{\star}D(\mathbf{P}-I)=0$ (11)
$\displaystyle\Rightarrow{P}^{\star}D={P}(\text{see Lemma~{}\ref{lemma1}})$
(12)

Since D is a diagonal matrix, we have

$\displaystyle\begin{aligned}
\begin{pmatrix}{P}^{\star}_{1}&\dots&{P}^{\star}_{N}\end{pmatrix}\begin{pmatrix}d_{1}&&&\\\
&&\ddots\\\
&&&d_{M}\end{pmatrix}=\begin{pmatrix}{P}_{1}&\cdots&{P}_{M}\end{pmatrix}\\\
\Rightarrow\begin{pmatrix}d_{1}&\cdots&d_{M}\end{pmatrix}\underbrace{\begin{pmatrix}{P}^{\star}_{1}&&&\\\
&&\ddots\\\ &&&{P}^{\star}_{M}\end{pmatrix}}_{\text{say
}\mathbb{P}^{\star}}=\begin{pmatrix}{P}_{1}&\dots&{P}_{M}\end{pmatrix}\\\
\Rightarrow\begin{pmatrix}d_{1}&\dots&d_{M}\end{pmatrix}=\begin{pmatrix}{P}_{1}&\dots&{P}_{M}\end{pmatrix}{\begin{pmatrix}{P}^{\star}_{1}&&&\\\
&&\ddots\\\ &&&{P}^{\star}_{M}\end{pmatrix}}^{-1}\end{aligned}$

where, $\mathbb{P}^{\star-1}$ exists as it is a diagonal matrix with positive
entries. We can normalize $d_{i}$’s to get $d_{i}\in(0,1)$. Then, the required
$D$ matrix is given by ${\rm diag}(d_{1},\dots,d_{M})$. ∎

It is easy to see that the matrix $\mathbf{P}^{\star}$ satisfies the four
conditions mentioned in Section III-A.

######  Remark IV.1.

In Lemma IV.1, we show that under the perturbations described, we retain the
irreducibility of the stochastic matrix (thus satisfy condition $1-3$ in
Section III-A) and through Theorem IV.1 we show synthesize a possible
perturbation so that the perturbed irreducible stochastic matrix attains the
desired distribution for the swarm (thus satisfy condition $4$ in Section
III-A). It is noted that the solution is not unique; however, this gives a
closed-form solution for controller synthesis.

The above calculation could be done in one-shot and thus, presents a one-stage
solution to the algorithm proposed for the same problem in [11]. Simulation
results demonstrating the correctness of the algorithm are presented in
section V. The synthesized controller has asymptotic convergence guarantees
and is globally stable (which follows from property of irreducible Markov
chains and their stochastic kernels) [26]. However, the controller is
implemented in an open-loop, feedforward fashion. Next we show how to
synthesize stable perturbations to the global policy matrix
$\textbf{P}^{\star}$ based on the local information which can help reduce
agent movement and can make the system possibly reactive to unmodeled events.

###  IV-B Algorithm and Analysis for Distributed Autonomy

In the last section, we presented an analytical solution to the controller
synthesis problem described in Section III-A. It was based on the knowledge of
global state of the swarm and the synthesized controller has asymptotic
convergence and global stability guarantees. However, it might lead to
unnecessary movement of agents at steady state as the controller is
implemented in an open-loop fashion and the knowledge of current state is not
considered. Furthermore, the swarm cannot react to any unforeseen changes
events which might lead to changes in requirement of agents at different
states. It is desirable that the robots (agents) should have some degree of
autonomy to choose their action based on their current state and local state
information of the swarm. This forms the motivation of the problem described
in Section III-B. In this section, we present a framework to allow distributed
autonomy to the agents so that they can decide to follow the global policy in
a probabilistic fashion while retaining global stability. While it is in
general difficult to define a unique notion of autonomy for distributed
systems, here we will define a very simple notion of the same.

We define the degree of autonomy as the fraction of the times an agent decides
to follow the global policy against the policy of staying in the same state.
To understand this notion more clearly, imagine the swarm is represented by a
two-state Markov chain. Let us further assume that the global policy is given
by the following stochastic matrix:

$B=\begin{bmatrix}p_{11}&p_{12}\\\ p_{21}&p_{22}\end{bmatrix}$

Then we define the degree of autonomy for a state $i$ by a scalar parameter
$a_{i}\in(0,1)$ such that the final policy used by the agents is represented
by the following matrix:

$\hat{B}=\begin{bmatrix}a_{1}p_{11}+(1-a_{1})&a_{1}p_{12}\\\
a_{2}p_{21}&a_{2}p_{22}+(1-a_{2})\end{bmatrix}$

Thus, the agents decide to use the global policy in a probabilistic fashion,
where the probability of following the global policy in a certain state is
represented by the degree of autonomy (like $a_{i}$ in the above example). It
is noted that all agents in the same state have the same degree of autonomy.

The idea presented in this section is to synthesize perturbations to the
global stochastic policy (which was synthesized in the last section). These
perturbations denote the autonomy (of the corresponding degree) for the
individual agents in following the global policy vs staying at the same state.
We estimate a state-value function for the Markov chain that represents the
swarm, based on the requirement of agents at the individual states.

The local policy represents the probability with which an agent decides to
either follow the global policy or stay in its current state. The goal is to
achieve a pre-defined percentage of activity at steady-state (as described
above in the notion of autonomy). To design such a controller, we use the
state value function defined by language measure theory (see [5] for a brief
introduction). To formulate the problem of distributed autonomy using language
measure theory, we augment the states of the Markov chain (that represents the
swarm) with characteristic weights The augmented Markov chain then defines a
probabilistic finite state automata (PFSA) which we use to define the state
value function for our problem using language measure of the PFSA (see [8, 27,
28]). The characteristic weights of the states are defined as follows:

$\chi_{i}^{[k]}=e_{i}^{[k]}$ (13)

The vector
$\mathbf{\chi}^{[k]}=[\chi_{1}^{[k]},\chi_{2}^{[k]},\dots,\chi_{M}^{[k]}]^{T}$
thus contains the information about the deficit or excess of agents at the
individual tasks (or the states of the swarm). A positive value of $\chi$
would suggest deficit of agent in one state and a negative value of $\chi$
suggests excess of agents. The states with positive values of $\chi$ represent
the good states to move to from a neighboring state. A greedy policy would
thus try to move to the states with the maximum positive characteristic
weights. As mentioned earlier, the goal is to achieve a certain fraction,
$\lambda$, of original activity level at steady state. During the transient
phase, some states with positive characteristic weights observe higher (than
steady-state) activity rates than states with negative characteristic weights.
It is presented more formally next.

Instead of using a greedy policy, we compute the expected characteristic
weights for the states which represent the overall expected rewards (where the
expectation is computed over the states using the stochastic transition matrix
of the agents) that the agents can accumulate while trying to achieve the
target state distribution. The expected value of the characteristic weights
for the Markov chain (that represents the swarm) is calculated using the
language measure theory. The expectation, parameterized by a parameter
$\theta\in(0,1)$, of the characteristic weights of an irreducible Markov chain
with stochastic matrix $\mathbf{P}$ is calculated by the following recursive
equation.

$\nu_{i}\leftarrow(1-\theta)\sum_{j\in{\mathrm{Nb}}(i)}\mathbf{P}_{ij}\nu_{j}+\theta\chi_{i}$
(14)

where, ${\mathrm{Nb}}(i)$ is the neighborhood of the agent $i$ (Note that this
requires computation over the nearest neighbors only and thus, doesnt require
global information). A value of $\theta$ close to $0$ is selected for
computing the expected sum. Interested readers are referred to earlier
publications [7] for further discussion on choice of the parameter $\theta$.
The parameter $\theta$ governs the horizon length for computation of
expectation– for values closer to $1$, we approach the greedy policy. We use
$\theta=0.02$ for the computation of the expectation. In the next section, we
will show that $\theta$ closer to $1$ makes system convergence slow but more
stable to higher rates of feedback. The measure $\nu_{i}$ is the discounted
expected value of $\chi$ for agents starting in state $i$. Clearly,
$\mathbf{\nu}=\mathbf{0}$ if $\mathbf{\chi}=\mathbf{0}$. Convergence of the
expected weights follow from the fact that $\mathbf{\chi}$ is a constant
vector and $\mathbf{P}$ is a row stochastic matrix (see previous work in [8,
29] for proofs on convergence). All the states (i.e., tasks) synchronously
calculate their own $\nu_{i}$ and then broadcast it to their neighbors. This
is repeated recursively till the expectations converge. Based on the measure
defined in (14), we define a quantity,
$\mathbf{\mu}=\mathbf{\nu}-\mathbf{\chi}$.

Input: The initial Markov kernel $\mathbf{P}$, the error vector
$\mathbf{\chi}^{[k]}$ and the proportionality constant $\beta$.

Output: The decentralized policy kernel $\mathbf{P}^{\star}$

1 for  _$k\in\mathbb{N}$_ do

2 for  _$i\in\\{1,.\dots,M\\}$ till convergence_ do

3 for  _$j\in\tt{Nb}(i)$_ do

4 $\triangleright$ $\tt{Nb}(i)$ represents the neighborhood of state $i$

5
$\nu_{i}^{[k]}\leftarrow\sum\limits_{j\in\tt{Nb}(i)}(1-\theta)\mathbf{P}_{ij}\nu_{j}+\theta\chi_{i}^{[k]}$;

6

7 $\mu^{[k]}=\nu^{[k]}-\chi^{[k]}$;

8 for  _$i\in\\{1,.\dots,M\\}$_ do

9
$f_{\lambda}(\mu_{i}^{[k]})=\frac{1}{1+(\frac{1}{\lambda}-1){\mathrm{exp}}(-\beta^{[k]}\mu_{i}^{[k]})}$;

_10_ _ _return _$b_{i}^{[k]}=\\{f_{\lambda}(\mu_{i}^{[k]})\\}_{i=1,\dots,M}$
;_

11 return _$\mathbf{P}^{\star}=B\mathbf{P}-B+I$ , where
$B=\mathrm{diag(\mathbf{b}^{[k]})}$ _

Algorithm 2 ${\tt EstimatingDistributedPolicy}$

The quantity $\mu_{i}$ represents the difference between the characteristic
weight for state $i$ and the expected value of the $\chi$ for agents starting
in state $i$. As such, a positive value of $\mu_{i}$ would mean that the
states to which the agents can go from that state have higher expected reward
than their current state and hence, such states are expected to have higher
activity. An activation function is defined according to the following sigmoid
function

$f_{\lambda}(\mu_{i}^{[k]})=\frac{1}{1+(\frac{1}{\lambda}-1){\mathrm{exp}}(-\beta^{[k]}\mu_{i}^{[k]})}$
(15)

where, $\lambda\in(0,1)$ and $\beta^{[k]}\in_{+}$ are parameters. $\lambda$
denotes the steady state activity level for the agents. $\beta^{[k]}$ is a
scaling factor for $\mu_{i}$. Clearly, $f_{\lambda}(\mu_{i}^{[k]})\in(0,1)$
for all $\mu_{i}^{[k]}\in$. The sigmoid functions are used to design smooth
(i.e., the feedback rate is differentiable) feedback controllers. Figure 1
shows the variation in the change in activity of agents with scaling factor
$\beta$ (superscript $k$ dropped for ease of notation). It can be seen in
Figure 1 that higher values of $\beta$ lead to an increase in the rate of
change of activity and thus, it can lead to instability (or oscillations) in
the system when increased beyond an unknown threshold. In the next section, we
will show that the system can get locked in limit cycles of different
amplitudes based on the magnitude of the feedback rate used for controller
design. The stable feedback rates depend on the size of the system, the
parameter $\theta$ for computing the expectation and the parameter $\lambda$.

Figure 1: This plot shows the effect of the parameter $\beta^{[k]}$ on the
rate of change of activity.

Thus, the feedback matrix for at epoch $k$ is given by,

$\displaystyle\tilde{\textbf{P}}^{[k]}_{ij}=b_{i}^{[k]}\textbf{P}^{\star}_{ij},i\neq
j$
$\displaystyle\tilde{\textbf{P}}^{[k]}_{ij}=b_{i}^{[k]}\textbf{P}^{\star}_{ij}+(1-b_{i}^{[k]}),i=j$
(16)

where, $b_{i}^{[k]}=f_{\lambda}(\mu_{i}^{[k]})$ and $\mu_{i}^{[k]}$ was
defined earlier. Thus the idea is that based on the state of a task and the
neighboring tasks, an agent can probabilistically decide whether to follow the
global policy or stay in the same task. Note that the perturbation in (IV-B)
satisfies conditions $1-3$ in Section III-B. Clearly,
$\lim\limits_{k\rightarrow\infty}f_{\lambda}(\mu_{i}^{[k]})=\lambda\text{ if
}\lim\limits_{k\rightarrow\infty}\mu_{i}^{[k]}=0$. At steady state,
$\nu=\chi=0$ and thus, $f_{\lambda}(\mu_{i}^{[k]})=0$ for all
$i\in\\{1,\dots,M\\}$. Thus, at steady state (or the desired state), this
should lead to $\lambda$ fraction of agents staying in their task by deciding
against the global policy to switch. At every iteration, the agent activity
level $b_{i}^{k}$ decides the probability with which the agents in task $i$
decide against the global policy and stay in the same task; this results in
overall reduced activity. The algorithm for computing the distributed policy
is also presented as a pseudo-code in Algorithm 2.

At steady state, $\chi=0$ and $\nu=0$ and thus
$\tilde{\mathbf{P}}=\lambda\mathbf{P}^{\star}-\lambda I+I$. It is easy to see
that the stationary distribution of the matrix $\mathbf{P}^{\star}$ is also
the stationary distribution of the steady-state matrix $\tilde{\mathbf{P}}$.
More concretely, if $\mathbf{p}^{d}$ is the stationary distribution of
$\mathbf{P}^{\star}$, then
$\mathbf{p}^{d}\tilde{\mathbf{P}}=\mathbf{p}^{d}(\lambda\mathbf{P}^{\star}-\lambda
I+I)=\lambda\mathbf{p}^{d}+(1-\lambda)\mathbf{p}^{d}=\mathbf{p}^{d}$. This
satisfies condition $5$ specified in Section III-B.

Design of Stable Feedback: Next we consider the convergence of the feedback
controller represented by condition $4$ in Section III-B. We first present a
candidate Lyapunov function to present the sufficient conditions for system
stability. A possible candidate is described next.

$V^{[k]}(\mathbf{p})=\sum_{i=1}^{M}(p_{i}^{d}-p_{i}^{[k]})^{2}$ (17)

From equation (17), we have $V^{[k]}(\mathbf{p}^{d})=0$ and
$V^{[k]}(\mathbf{p})\geq 0$ for all $\mathbf{p}$. Then, for system stability
it is required that $\Delta V^{[k]}(\mathbf{p})\leq 0$ for all
$k\in\mathds{N}$. From equation (17), we get the following expression for
$\Delta V^{[k]}(\mathbf{p})$.

$\Delta V^{[k]}(\mathbf{p})=V^{[k]}(\mathbf{p})-V^{[k-1]}(\mathbf{p})$ (18)

Further expansion of equation (17) leads to the following form

$\Delta
V^{[k]}(\mathbf{p})=\sum\limits_{i=1}^{M}(2p_{i}^{d}-p_{i}^{[k]}-p_{i}^{[k-1]})(p_{i}^{[k-1]}-p_{i}^{[k]})$
(19)

In equation (19), we introduce the following notations
$e_{i}^{[k]}=p_{i}^{d}-p_{i}^{[k]}$ and $\Delta
e_{i}^{[k]}=e_{i}^{[k]}-e_{i}^{[k-1]}$. Then, using the Lyapunov condition for
stability, the swarm is stable if the following holds true.

$\sum\limits_{i=1}^{M}(e_{i}^{[k]}+e_{i}^{[k-1]})\Delta e_{i}^{[k]}\leq 0$
(20)

Based on the definition of $e_{i}^{[k]}$, it is not difficult to see that a
sufficient condition for equation (20) to hold true is that

$e_{i}^{[k]}\Delta e_{i}^{[k]}\leq 0$ (21)

for all $i\in\\{1,\dots,M\\}$. Let us denote the sequence $e_{i}^{[k]}\Delta
e_{i}^{[k]}$ by $\zeta_{i}^{[k]}$. Thus a sufficient condition for stability
of the distributed system is that there exists a $N\in\mathds{N}$ such that
the sequence $\\{\zeta_{i}^{[k]}\\}_{k\geq N}$ is monotonic and as
$\zeta_{i}^{[k]}$ is upper bounded by $0$, we have that
$\lim\limits_{k\rightarrow\infty}\zeta_{i}^{[k]}=0$ for all
$i\in\\{1,\dots,M\\}$. Then, to ensure stability we design the perturbations
to the global policies so that the above condition holds. It is noted that
this only defines a sufficient condition for stability of the system. Based on
the condition expressed in (21), we need to ensure that for all $\beta\in$ we
can finally ensure that there exists a $N\in\mathds{N}$ such that
$\\{\zeta_{i}^{[k]}\\}_{k\geq N}$ is monotonic. Loosely speaking it means that
the feedback rate around the equilibrium point be sufficiently reduced. The
analysis of sigmoid functions for stability of neural networks has been well
studied in literature. In some analysis present in literature, it has been
shown that if the feedback rate should be smaller than inverse of the second
largest eigenvalue of the stochastic matrix [30]. With this motivation, we can
design a controller whose feedback rate decreases as we move closer to the
regulated state.

In the controller design, we don’t need to find the actual value of maximum
allowable $\beta^{[k]}$ to ensure stability; the existence is enough to
guarantee global asymptotic stability. The idea is to reduce the feedback
constant rate $\beta$ as the system moves towards the desired state– thus
reducing the activity of the states as the system moves towards the regulated
state. A very simple feedback rate dependent on the iteration number is
$\beta^{[k]}=\gamma/k$, where $\gamma\in_{+}$ is a constant. Similarly, an
exponentially decreasing $\beta^{[k]}$ could also work well (e.g.,
$\beta^{[k]}=\gamma*\exp^{(-k/N)}$, where $N$ is some large constant). As a
result of this feedback rate design, the feedback rate eventually reduces to a
level for monotonic convergence of the system irrespective of the size of the
system.

Figure 2: The tasks modeled as a graph with its connectivity topology.
Initially all the agents are in the state marked in red; the desired
distribution is to uniformly distribute them over all tasks.

##  V Numerical Results and Discussion

In this section, we present some numerical results based on the proposed
algorithms described in sections IV-A and IV-B. Through the numerical
experiments, we try to answer the following questions about the controller
design that was presented in the earlier sections:

  1. 1.

Can we show the correctness of the proposed central controller design? Does it
achieve the desired global behavior?

  2. 2.

Can we understand and ensure stability of the proposed distributed controller?

To answer the above mentioned questions, we design numerical experiments in a
swarm which is described next. We consider a task allocation problem which
consists of the $35$ tasks being operated in parallel. The connectivity of
tasks is represented as a graph which is shown in Figure 2. Each node of the
graph (or a task) is connected to $8$ neighboring nodes (or tasks) except for
the ones on the edges which are connected to either $5$ or $3$ nodes (see
Figure 2).

(a) Convergence of the agent distribution to the desired distribution

(b) Activity level at steady state

Figure 3: Convergence of system states and agent activity obtained by the
central control policy

(a) A high proportional gain in the local policy synthesis results in steady-
state error with oscillatory behavior

(b) Activity level at steady state

Figure 4: Results corresponding to a fixed high proportional gain leading to
oscillatory behavior

(a) Convergence of the agent distribution to the desired distribution over the
parallel tasks

(b) Activity level at steady state

Figure 5: Convergence and agent activity level obtained by the distributed
feedback controller with $\beta^{[k]}=\gamma/k$, where $\gamma=600$. Figure 6:
Convergence of agent movement with exponentially decaying
$\beta^{[k]}=\gamma*\exp^{(-k/N)}$, where $\gamma=2000$, $N=100$. Figure 7:
Convergence of the distributed controller for various values of $\beta$ for
$\theta=0.98$. Clearly, higher values of $\theta$ are slower but more stable
to feedback rates.

Initially all the agents are located at the same task which is marked in red
in the graph. The agents need to be distributed uniformly over all the tasks
at steady state. In Figure 3 we show the results obtained for the central
controller. The system converges to the desired distribution monotonically
(see Figure 3a) ; however, there is a lot of activity at steady state which is
undesirable (see Figure 3b).

Next we consider the distributed control which is calculated as perturbation
to the central control policy discussed earlier. For the distributed control,
the parameter $\theta$ is selected to be $0.02$ and the desired activity level
is taken to be $\lambda=0.2$ i.e., only $20\%$ of the agents should move at
steady state when compared to the movement shown in Figure 3b. We first show a
controller which is unstable due to very high gain which leads to unstable
(oscillatory) behavior in the swarm around the desired state. To see this, we
select a high proportional gain corresponding to $\beta=600$ which is kept
constant through all iterations i.e., $\beta^{[k]}=600$. The results (see
Figure 4) show the unstable or oscillatory behavior of the system; the agents
keep moving between the tasks without ever reaching the steady state. As it is
shown in Figure 4a, this results in steady state error. As seen in Figure 4b,
the agent activity becomes oscillatory and is not able to achieve $\lambda$
fraction of activity at steady state. The reason for the oscillatory behavior
is the high proportional feedback gain which is being used for estimating
feedback. With a high-feedback gain the system is never able to reach the
desired set-point and keeps over-shooting. This also motivates the Lyapunov-
based design where, a sufficient condition for stability is reached by the
proportional feedback gain given by $\beta^{[k]}=\gamma/k$ for $\gamma\in$.

Next we show the use of proportional feedback given by $\beta^{[k]}=\gamma/k$
where $\gamma=600$ which guarantees asymptotic convergence. In Figure 5, we
show the results of the stable distributed proportional controller. As seen in
Figure 5a, the error norm asymptotically converges to zero. Figure 5b shows
the agent activities at steady state reaches $\lambda$ fraction of the
activity achieved by the central control policy. It is noted that the system
convergence rate is slower than the global policy; however we reach with the
desired activity with lesser activity and a desired reduced activity can be
achieved at steady state. A similar result with an exponentially decaying
feedback rate is also shown as an example in Figure 6. Compared to the central
control, the distributed controller is slower (as seen by the error
convergence rates in Figures 3 and 4a). However, the distributed controller is
able to achieve the target state with reduced movement of agents and maintains
reduced activity at steady state. In general, using an exponentially decaying
feedback allowed use of more aggressive feedback rates in the beginning and
thus leads to faster convergence.

Next we present some results related to the dependence on the system
convergence rate and stability on the parameter $\theta$. As discussed
earlier, the parameter $\theta$ governs the horizon of the expected sum while
computing the state measure. A value of $\theta$ closer to $1$ leads to a
greedy policy by the agents (as the expected sum depends largely on the
immediate rewards). Figure 7 shows convergence of the distributed controller
for $\theta=0.98$ and different constant values of $\beta$. As can be seen,
with increasing values of $\beta$, the system convergence becomes slower for
values of $\theta$ closer to $1$. This becomes clear from the expression of
$\nu_{i}$ in Equation (14) where the coefficient of $\chi_{i}$ is $\theta$. As
a result, the term $\nu_{i}$ is dominated by $\chi_{i}$ and thus $\mu_{i}$ is
very close to $0$. This allows use of higher rates in Equation (15). This is
however, opposite of what was observed with $\theta$ close to $0$. In general,
using an exponentially decaying feedback rate with $\theta$ close to $0$ lead
to best performance as well as stability of the distributed system (seen in
Figure 6).

##  VI Conclusions

In this paper, we modeled a homogeneous swarm as a collection of irreducible
Markov chains. The problem of synthesizing controller for the swarm is then
equivalent to estimating the Markov kernel of the Markov chain whose
stationary distribution is the desired swarm state. We presented analysis for
an analytical solution to the centralized swarm control problem which greatly
alleviates controller synthesis computational complexity for swarms with large
number of states. Next we proposed a local-information-based perturbation to
the centralized controller which can achieve reduced activity with guarantees
of global asymptotic stability.

## References

  * [1] J. Werfel, K. Petersen, and R. Nagpal, “Designing collective behavior in a termite-inspired robot construction team,” Science, vol. 343, no. 6172, pp. 754–758, 2014.
  * [2] M. Rubenstein, A. Cornejo, and R. Nagpal, “Programmable self-assembly in a thousand-robot swarm,” Science, vol. 345, no. 6198, pp. 795–799, 2014\.
  * [3] D. K. Jha, M. Zhu, and A. Ray, “Game theoretic controller synthesis for multi-robot motion planning-part ii: Policy-based algorithms,” IFAC-PapersOnLine, vol. 48, no. 22, pp. 168–173, 2015.
  * [4] Y. Wang, D. K. Jha, and Y. Akemi, “A two-stage rrt path planner for automated parking,” in 2017 13th IEEE Conference on Automation Science and Engineering (CASE), pp. 496–502, IEEE, 2017.
  * [5] D. K. Jha, “Algorithms for task allocation in homogeneous swarms of robots,” in International Conference on Intelligent Robots and Systems (IROS), p. Accepted, IEEE/RSJ, 2018.
  * [6] A. Ray*, “Signed real measure of regular languages for discrete event supervisory control,” International Journal of Control, vol. 78, no. 12, pp. 949–967, 2005.
  * [7] I. Chattopadhyay and A. Ray, “Structural transformations of probabilistic finite state machines,” International Journal of Control, vol. 81, no. 5, pp. 820–835, 2008.
  * [8] D. K. Jha, Y. Li, T. A. Wettergren, and A. Ray, “Robot path planning in uncertain environments: A language-measure-theoretic approach,” Journal of Dynamic Systems, Measurement, and Control, vol. 137, no. 3, p. 034501, 2015\.
  * [9] A. Khamis, A. Hussein, and A. Elmogy, “Multi-robot task allocation: A review of the state-of-the-art,” in Cooperative Robots and Sensor Networks 2015, pp. 31–51, Springer, 2015.
  * [10] S. Berman, Á. Halász, M. A. Hsieh, and V. Kumar, “Optimized stochastic policies for task allocation in swarms of robots,” Robotics, IEEE Transactions on, vol. 25, no. 4, pp. 927–937, 2009.
  * [11] I. Chattopadhyay and A. Ray, “Supervised self-organization of homogeneous swarms using ergodic projections of Markov chains,” Systems, Man, and Cybernetics, Part B: Cybernetics, IEEE Transactions on, vol. 39, no. 6, pp. 1505–1515, 2009.
  * [12] N. Napp and E. Klavins, “A compositional framework for programming stochastically interacting robots,” The International Journal of Robotics Research, vol. 30, no. 6, pp. 713–729, 2011.
  * [13] B. Acikmese and D. S. Bayard, “A Markov chain approach to probabilistic swarm guidance,” in American Control Conference (ACC), 2012, pp. 6300–6307, IEEE, 2012.
  * [14] S. Berman, V. Kumar, and R. Nagpal, “Design of control policies for spatially inhomogeneous robot swarms with application to commercial pollination,” in Robotics and Automation (ICRA), 2011 IEEE International Conference on, pp. 378–385, IEEE, 2011.
  * [15] S.-i. Azuma, R. Yoshimura, and T. Sugie, “Broadcast control of multi-agent systems,” Automatica, vol. 49, no. 8, pp. 2307–2316, 2013.
  * [16] Y. Ito, M. A. S. Kamal, T. Yoshimura, and S.-i. Azuma, “Pseudo-perturbation-based broadcast control of multi-agent systems,” Automatica, vol. 113, p. 108769, 2020.
  * [17] A. Jevtić, A. Gutiérrez, D. Andina, and M. Jamshidi, “Distributed bees algorithm for task allocation in swarm of robots,” Systems Journal, IEEE, vol. 6, no. 2, pp. 296–304, 2012.
  * [18] B. Fonooni, A. Jevtić, T. Hellström, and L.-E. Janlert, “Applying ant colony optimization algorithms for high-level behavior learning and reproduction from demonstrations,” Robotics and Autonomous Systems, vol. 65, pp. 24–39, 2015.
  * [19] M. A. Hsieh, Á. Halász, S. Berman, and V. Kumar, “Biologically inspired redistribution of a swarm of robots among multiple sites,” Swarm Intelligence, vol. 2, no. 2-4, pp. 121–141, 2008.
  * [20] A. Cornejo, A. Dornhaus, N. Lynch, and R. Nagpal, “Task allocation in ant colonies,” in Distributed Computing, pp. 46–60, Springer, 2014.
  * [21] I. Jang, H.-S. Shin, and A. Tsourdos, “Local information-based control for probabilistic swarm distribution guidance,” Swarm Intelligence, vol. 12, no. 4, pp. 327–359, 2018.
  * [22] I. Jang, H.-S. Shin, and A. Tsourdos, “Anonymous hedonic game for task allocation in a large-scale multiple agent system,” IEEE Transactions on Robotics, no. 99, pp. 1–15, 2018.
  * [23] S. Bandyopadhyay, S.-J. Chung, and F. Y. Hadaegh, “Probabilistic and distributed control of a large-scale swarm of autonomous agents,” IEEE Transactions on Robotics, vol. 33, no. 5, pp. 1103–1123, 2017.
  * [24] B. Touri and A. Nedic, “Product of random stochastic matrices,” Automatic Control, IEEE Transactions on, vol. 59, no. 2, pp. 437–448, 2014.
  * [25] D. Bajovic, J. Xavier, J. M. Moura, and B. Sinopoli, “Consensus and products of random stochastic matrices: Exact rate for convergence in probability,” Signal Processing, IEEE Transactions on, vol. 61, no. 10, pp. 2557–2571, 2013.
  * [26] S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability.  Springer Science & Business Media, 2012.
  * [27] P. Chattopadhyay, D. K. Jha, S. Sarkar, and A. Ray, “Path planning in gps-denied environments: A collective intelligence approach,” in 2015 American Control Conference (ACC), pp. 3082–3087, IEEE, 2015.
  * [28] D. K. Jha, P. Chattopadhyay, S. Sarkar, and A. Ray, “Path planning in gps-denied environments via collective intelligence of distributed sensor networks,” International Journal of Control, vol. 89, no. 5, pp. 984–999, 2016.
  * [29] I. Chattopadhyay and A. Ray, “Goddes: Globally $\epsilon$-optimal routing via distributed decision-theoretic self-organization,” in Proceedings of the 2011 American Control Conference, pp. 3215–3220, IEEE, 2011.
  * [30] L. Jin and M. M. Gupta, “Globally asymptotical stability of discrete-time analog neural networks,” Neural Networks, IEEE Transactions on, vol. 7, no. 4, pp. 1024–1031, 1996.


# Quantifying Discourse Support for Omitted Pronouns

Shulin Zhang1, Jixing Li2, John Hale1
1University of Georgia, US
2City University of Hongkong, China
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>

###### Abstract

Pro-drop is commonly seen in many languages, but its discourse motivations
have not been well characterized. Inspired by the topic chain theory in
Chinese, this study shows how character-verb usage continuity distinguishes
dropped pronouns from overt references to story characters. We model the
choice to drop vs. not drop as a function of character-verb continuity. The
results show that omitted subjects have higher character history-current verb
continuity salience than non-omitted subjects. This is consistent with the
idea that discourse coherence with a particular topic, such as a story
character, indeed facilitates the omission of pronouns in languages and
contexts where they are optional.

##  1 Introduction

Pro-drop is a phenomenon that pronouns can be omitted when they are inferable.
It is common across the world’s languages, and Mandarin Chinese is one of them
(See examples (3) and (4) in Figure 1). Omitted pronouns in these languages,
also called zero pronouns, are increasingly important in computational
linguistics (e.g. Chen et al., 2021; Iida et al., 2006, 2015; Kong et al.,
2019). This paper formalizes the notion of Topic Chains, introduced by Tsao
(1977) and demonstrates that people omit pronouns when a certain kind of
discourse salience is high. We show that this notion of salience is robust
across various choices of language models, however, locality (i.e. clause
recency) seems to be a key requirement.

The proposed formalization leverages the idea that verbs predicated on the
same story-character exhibit discourse coherence (Huang, 1984, 1994; Li and
Thompson, 1979). Figure 1 shows a literary example where the same character,
the narrator, is explicitly referred to once using an explicit pronoun “wo”.
After that, the pronoun is dropped. The list of predicates (shown in red)
applying to the narrator in examples (1) - (3) is [“draw”, “lose”, “draw”].
When faced with another omitted pronoun in example (4), the fact that the
predicate is also “draw” supports the interpretation that the omitted element
refers to the narrator. This is because “draw” is similar to the history verbs
“draw” and “lose” which were predicated of this same character earlier in the
discourse. In this short example, there are other entities such as “grownups”
and the “boa constrictor”, but their verb histories make them less plausible
as candidate referents of the omitted pronoun.

In this paper, we use representations from three neural language models to
quantify character-verb usage continuity in a literary discourse, and
calculate salience values for each of 32 possible characters at the site of
each omitted pronoun. Figure 2 summarizes the analytical steps of this
process. Our contributions are as follows: (1) We provide a numerical
description of the topic chain continuity. (2) We elaborate on the role of
verbs in resolving omitted pronouns. (3) We show that verb similarity and
clause range offer reliable clues about the referent of the omitted pronoun.

Figure 1: Example of Chinese omitted pronouns in a topic chain. Omitted
pronouns, shown here in green with square brackets are not actually spoken.
However, their intended reference is unambiguous for native speakers.
Predicates are shown in red, and the overtly expressed entities are shown in
blue. Unlike in Romance languages, there is no morphological change on verbs
to mark the gender or number of omitted elements in Chinese. Figure 2:
Analysis steps adopted in this study: (a) Grammatical subjects and objects of
each main verb are identified via dependency parsing on the whole story
discourse of The Little Prince (See a sentence example from Table 1, columns
“S”, “V”, “O”); (b) Semantic role annotation: for all the subjects and
objects, annotate their semantic roles as Agent or Patient (See Table 1 column
“V-agent” and “V-patient”); (c) Character role annotation: assign story
character roles to the entities, see character occurrences in Table A1, and
Table 1 column “character”; (d) History verb retrieval for each story
character: for each story character, tabulate the verbs that are its main
verbs being used in the discourse (See example Table A3); (e) Relevance
between history verbs and a current verb: for each current verb, calculate its
relevance to the history verbs, and sum with or without their distance weight
(See Table 2 and A5); (f) Salience of the correct character: for each verb,
calculate how “salient” the correct character is compared to all other
characters (See example Table A6); (g) Group test between pro-drop verbs vs.
non-pro-drop verbs, and apply logistic regression to test predictability of
character salience on dropping behavior (See group results in Table 3 and
Figure 3).

##  2 Related Work

Various linguistic theories point to discourse coherence as a factor that
enables or encourages pro-drop. One of these is Tsao’s (1977) notion of Topic
Chain. As reviewed in Pu (2019a), a topic chain is a sequence of clauses
sharing an identical topic that occurs overtly in one of the clauses. Topic
Chains may cross several sentences and even paragraphs (Li, 2004). The
multiclausal aspect of Topic Chains supports long-distance coreference (Sun,
2019). Taking a dynamic perspective, Pu (2019b) suggests that a topic chain
“encodes a referent that is cognitively most accessible at the moment of
discourse production, as enhanced by maximum discourse coherence of topic
continuity and thematic coherence”.

We conceptualize accessibility in Pu’s sense as the relative salience of a
story character that participates in a chain of predications. Instead of
focusing on named entities, we form the chain based on the verbs in the
preceding discourse.

ID | word | S | V | O | V-agent | V-patient | character
---|---|---|---|---|---|---|---
56 |  | 这些 (these)
---
|  |  |  |  |
57 |  | 蟒蛇 (boa)
---
True |  |  |  |  | ch2_boa
58 |  | 把 (BA)
---
|  |  |  |  |
59 |  | 它们 (them)
---
|  |  |  |  |
60 |  | 的 (DE)
---
|  |  |  |  |
61 |  | 猎获物 (prey)
---
|  | True |  |  |
62 |  | 不 (not)
---
|  |  |  |  |
63 |  | 加 (with)
---
|  |  |  |  |
64 |  | 咀嚼 (chew)
---
| True |  |  | 57 (boa)
---
| 61 (prey)
---
65 |  | 地 (DI)
---
|  |  |  |  |
66 |  | 囫囵 (roughly)
---
|  |  |  |  |
67 |  | 吞 (swallow)
---
| True |  |  | 57 (boa)
---
| 61 (prey)
---
68 |  | 下 (down)
---
|  |  |  |  |

Table 1: Dependency structure and semantic role annotation table. An
annotation example for the sentence “These boas swallow their prey without
chewing.” The verbs “chew” and “swallow” are located as verbs in the column V.
Token indices for each verb’s Agent and/or Patient are annotated in the
columns V-agent and V-patient respectively, and the character roles they are
referring to are annotated in the column character.

##  3 Method

###  3.1 Discourse Material

The discourse material used in this study is a Chinese translation
(xiaowangzi.org, 2021) of Saint-Exupéry’s The Little Prince. It contains 2802
clauses and 16010 words, and the word tokenization was manually checked by
native Chinese speakers.

###  3.2 Dependency Structure Retrieval and Semantic Role Annotation

We manually annotate the semantic roles Agent and Patient for each verb using
dependency analyses provided by Stanza (Qi et al., 2020) and part of speech
tags provided by spaCy. For most cases in the discourse, subjects are acting
as agents whereas objects are acting as patients, but there are 494 exceptions
(i.e. 218 Agents are acting as Objects, and 276 Patients are acting as
Subjects) such as passives, the -BA(‘把’) construction, the relative clause
-DE(‘的’) construction etc. that call for our manual annotation (See Chapter 28
and 32 in The Oxford Handbook of Chinese Linguistics (Wang and Sun, 2015)
regarding these constructions).

The textual antecedents of each agent and patient are separately annotated
manually. As shown in Table 1, the sentence meaning “These boas swallow their
prey without chewing” has the following annotations: verbs annotated in column
V; verbs’ agents and patients annotated correspondingly in column V-agent and
V-patient; pronouns or named entities’ character roles are annotated in column
character. As described below in Section 3.4, information about characters in
particular semantic roles can be used to form a dynamic usage table, reifying
Pu’s view of Topic Chains.

###  3.3 Pro-drop Annotation

Omitted subjects and objects are manually resolved using numerical indices
from 1 to 32. As shown in Appendix Table A2, 422 Agents and 16 Patients are
found omitted in the discourse, and in the following analyses, we focus on
just story characters in the Agent semantic role.

###  3.4 Dynamic Character-Verb Usage Table

Based on the dependency annotation table, the verbs used for each character
are extracted and entered in a second table, the Character-Verb Usage Table
(See example in Appendix Table A3). This table includes the following
features: (1) verb, the original text of the verb; (2) verb_id, the index of
the verb in the whole discourse; (3) agent/patient_character, the verb’s agent
or patient story character; (4) pro_drop, whether the verb has pro-drop; (5)
ch[1-32]_prev_verbs, for characters 1 through 32, their corresponding previous
verbs and indexes are stored as lists.

The dynamic character-verb usage table includes the previous verbs for each
story character until a “current verb”, and this indicates the verb usage
history of each character. By transforming these verb usage histories into
numerical vectors, it is possible to use a simple notion of similarity to
formalize discourse coherence.

###  3.5 History-verb and Current-verb Relevance

The idea behind comparing the history verbs and the current verb for each
story character is to calculate a numerical similarity level between the
current verb and preceding verbs that are part of one or another Topic Chain.
Inspired by Sperber and Wilson (1986), we define a quantity called Relevance,
a time-weighted function of vector similarity with preceding predicates. The
Relevance evaluation process adopt three types of word embeddings (See Section
3.5.1 for details), and steps for the evaluation are introduced in Section
3.5.2.

####  3.5.1 Word Embeddings Methods

Word embeddings allow each word to be mapped to a single point in a vector
space. Under the Distributional Hypothesis (see e.g. Lenci, 2018), words with
similar meanings should be closer in vector space (for a textbook
introduction, see Pilehvar and Camacho-Collados, 2020). We use this idea to
calculate the similarity between the main verb of an omitted pronoun and the
verb chains of story characters that might serve as that omitted pronoun’s
referent.

We use three types of word embeddings: GloVe, BERT, and Word2Vec. The GloVe
model (Pennington et al., 2014) learns word embedding from the term co-
occurrence matrix by minimizing the reconstruction error. GloVe has a large
context window, which allows it to capture longer-term dependency features.
The BERT model (Kenton and Toutanova, 2019) consists of multi-layer
bidirectional transformer encoders. BERT is trained on two unsupervised tasks:
predict masked tokens, and predict the next sentence, and the BERT embeddings
reflect contextual corpus features. Word2Vec is a prediction-based model
(Mikolov et al., 2013a, b), and the word embeddings used in this study (Li et
al., 2018) were trained on a Skip-Gram with Negative Sampling (SGNS) model.
All word embeddings we used were trained on large Chinese corpora, and contain
contextual word knowledge that carries semantic, syntactic, and pragmatic
features. Among these three word embedding models, BERT can provide
contextualized features of the language compared to the others due to the
tasks and processes it has been trained on.

In this study, BERT and GloVe models are applied with
spaCy111https://spacy.io/models/zh, and Word2Vec model is applied with
pretrained Chinese Word Vectors222https://github.com/Embedding/Chinese-Word-
Vectors (Li et al., 2018). A baseline model with 300-dimension random value
vectors is adopted to calculate the baseline relevance as compared to the
other word embedding models.

The GloVe word embeddings are obtained from the zh_core_web_lg model in spaCy.
The GloVe model (Pennington et al., 2014) relies on word co-occurrence in the
training corpus, and considers the ratios of word-word co-occurrence
probabilities to encode semantic information. The model in spaCy was trained
on OntoNotes 5, CoreNLP Universal Dependencies Converter, and Explosion
fastText Vectors. It has 500,000 unique vectors with a dimension size of 300.
We obtained the word vectors by searching up the Chinese word in the word
dictionary.

The BERT word embeddings are retrieved from the zh_core_web_trf model in
spaCy. This transformer model was trained on OntoNotes 5, CoreNLP Universal
Dependencies Converter, and bert-base-chinese. The word embedding vectors were
obtained by grouping every 50 words in the discourse, and the model inputs
were the 50 words combined as a string (with space between the words). The
dimension of the BERT word embedding is 768. If there were more than 1
character in a word, their vectors’ mean value was used as the word embedding
for the whole word. For example, the word “只有” ’s embedding was calculated by
averaging its subwords’ embedding vectors of “只” and “有”.

The Word2Vec word embeddings were pretrained on Word2Vec model with a large
Chinese corpus containing data from Baidu Netdisk (22.6G), and the vector
dimension is 300 (Li et al., 2018).

Baseline Word Vectors were 300-dimension vectors generated randomly in the
range -1 to 1. The same analysis steps are applied to this model as a
baseline.

####  3.5.2 Relevance evaluation

The relevance between history verbs and current verbs is calculated based on
their word embedding similarities (see Section 3.5.1 for details). At the same
time, a weight decay function is applied to the influence of each history verb
based on its distance to the current verb, and the function used here is a
vanilla value decreasing function (see Equation 1), in which $\omega$ refers
to the weight applying on the similarity, d refers to the clause distance
between the verbs being compared, and j, k are the clause numbers the verbs
are in:

$\begin{split}\omega(j,k)=1/(d+1)\\\ d=\left|j-k\right|\end{split}$ (1)

In this study, the “word embedding similarity” method is realized by
calculating the Cosine Similarity between two word embedding vectors. As shown
in Equation 2, $v_{prev}$ refers to a word embedding vector of a previous
verb, and $v_{curr}$ refers to the one for the current verb:

$R(v_{prev},v_{curr})=\frac{v_{prev}\cdot v_{curr}}{||v_{prev}||||v_{curr}||}$
(2)

Therefore, the clause-distance-weighted similarity between history verbs and
the current verb is shown as Equation 3, in which n refers to the number of
verbs in the history verb list for a character, and cl_prev_i and cl_curr
refer to the clause numbers that the previous verb and the current verb are in
correspondingly.

$\begin{split}R_{weighted}([v_{prev\\_1},...,v_{prev\\_n}],v_{curr})=\\\
\sum_{i=1}^{n}\omega(cl\\_prev\\_i,cl\\_curr)*R(v_{prev\\_i},v_{curr})\end{split}$
(3)

Via Equation 3, for a current verb, each story character has a corresponding
relevance value: if the value is higher, the distance-weighted word embedding
similarity between history verbs and current verb is higher; and vice versa.

Appendix Table A3 shows an example of a verb and the history verbs for
characters 1 through 32. The GloVe, BERT, Word2Vec, and Baseline embeddings
are used to calculate the average relevance of the history verbs to each
current verb for each story character.

Regressors obtained from relevance evaluation introduced in this section are
shown in Table 2. The average similarity is calculated following Equation 2
and 3. Both distance-weighted and distance-unweighted relevance are explored
to see whether clause distance would play a role.

Regressor Number | Regressor Name | Regressor Meaning
---|---|---
1 | verb |  | the verb in the discourse acting
---
as a main verb of a clause
2 | verb-id |  | the word order id of this verb
---
in the original discourse
3 | agent-character |  | the story character referred
---
by the agent of the verb
4 | pro-drop |  | whether this agent is dropped
---
in the discourse
5 - 36 | ch{1-32}-prev-verbs |  | the previous verbs used by
---
each story character till the
current verb
37 - 68 | rel-glove-ch{1-32} |  | relevance obtained by
---
GloVe word embeddings
69 - 100 | rel-bert-ch{1-32} |  | relevance obtained by
---
BERT word embeddings
101 - 132 | rel-word2vec-ch{1-32} |  | relevance obtained by
---
Word2Vec word embeddings
133 - 164 | rel-baseline-ch{1-32} |  | relevance obtained by
---
Baseline word vectors

Table 2: Regressors obtained after the relevance calculation

As shown in Appendix Table A5, the relevance calculation results of the last
verb are presented as an example.

###  3.6 Character Salience

With the relevance between history-current verbs computed as described in the
previous section, we have a similarity value for each story character to the
current verb. This character salience value refers to whether a story
character stands out compared to other candidate characters. The salience
level function is described in Equation 4. In Equation 4, k refers to
character_k, and the relevance values were calculated based on its history-
current verbs by Equation 3.

$S(k)=\frac{\sum_{i=1}^{n}\left(\frac{R_{weighted}(k)+1}{R_{weighted}(i)+1}\right)}{n+1}$
(4)

Correct character salience pro-drop >non-pro-drop (n = 422) Candidates’ Range
range = all range <10 clause range <20 clause range <30 clause t-value p-value
t-value p-value t-value p-value t-value p-value Distance- Weighted GloVe
49090.319 0.063 51137.593 0.012* 52598.233 0.003** 52121.241 0.004** BERT
50555.45 0.023* 45310.076 0.029* 52105.854 0.005** 51582.819 0.008** Word2Vec
50358.954 0.025* 51268.800 0.011* 52747.81 0.002** 52246.569 0.004** Baseline
44656.318 0.496 44737.336 0.483 49199.853 0.060 47875.291 0.134 Distance-
Unweighted GloVe 39345.494 0.959 44384.169 0.531 43818.383 0.606 43837.85
0.604 BERT 42867.41 0.724 45310.076 0.411 45187.343 0.425 45220.75 0.421
Word2Vec 40865.782 0.898 45236.126 0.420 44672.755 0.494 44630.117 0.498
Baseline 43149.674 0.690 45940.625 0.330 46398.831 0.275 45552.563 0.377

Table 3: Single-sided nonparametric two-sample Wilcoxon test between pro-drop
and non-pro-drop salience values among three word embedding models and the
baseline model: With candidates included as all candidates, candidates within
10 clauses, 20 clauses, and 30 clauses.

Logistic Regression Model Pro-drop Prediction Accuracy Candidates’ Range range
= all range <10 clause range <20 clause range <30 clause Distance- Weighted
GloVe 0.518 0.535 0.527 0.539 BERT 0.538 0.532 0.536 0.546 Word2Vec 0.534
0.535 0.537 0.552 Baseline 0.497 0.489 0.495 0.498 Distance- Unweighted GloVe
0.524 0.487 0.490 0.485 BERT 0.493 0.488 0.492 0.482 Word2Vec 0.514 0.485
0.482 0.473 Baseline 0.485 0.485 0.485 0.485

Table 4: Pro-drop prediction accuracy results of the Logistic Regression model
from three word embedding models and one baseline model: salience value
calculated based on all previous clauses and ranged clauses.

####  3.6.1 Ranged Character Salience

Instead of taking all 32 story characters as candidates for the salience value
calculation, the ranged candidates’ salience compares the correct character’s
accumulated relevance value to the ones within a certain number of clauses. We
consider candidates within 10, 20, and 30 clauses for this ranged salience.

###  3.7 Pro-drop Prediction

With the correct story character’s salience level for each verb in the
annotated discourse, we apply a logistic regression model to predict pro-drop
based on the salience level. The sample sizes are chosen by the size of the
smaller group (i.e. pro-drop), and the chosen processes are repeated 100 times
to obtain the average accuracy level.

##  4 Results

In this study, the following analyses are applied to The Little Prince
discourse to explore the effect of verb continuity on the pro-drop phenomenon:
(1) relevance between history and current verbs for all story characters (with
three types of word embeddings applied); (2) character salience of the correct
character, and (3) correct character salience group comparison, and its
predictability on pro-drop in the discourse. The following sections describe
the results of (2) and (3), and (1) is an intermediate step introduced in
Section 3.5.

Figure 3: Salience distributions from the word embedding models: GloVe, BERT,
Word2Vec, and Baseline. (a) Salience distribution based on distance-weighted
models; (b) Salience distribution based on distance-unweighted models. The
blue boxplots are pro-drop salience cases, and the red ones are non-pro-drop.
The BERT and Word2Vec models show significant pro-drop > non-pro-drop effect,
and GloVe model shows marginally significant result (See detailed Wilcoxon
tests results in Table 3).

###  4.1 Character Salience: Pro-drop vs. Non-pro-drop

The correct story character’s salience compared to all other characters was
calculated following Equation 4. For each verb, we calculated a salience value
for the correct story character. See Appendix Table A6 for an example of the
salience values of the last verb.

The distributions for the salience value obtained from three word embedding
models and one baseline model are shown in Figure 3.

Single-sided nonparametric two-sample Wilcoxon Tests are carried out between
pro-drop and non-pro-drop character salience of all three word embedding
models and the baseline model. 422 cases are randomly selected from non-pro-
drop salience values to match the size of the pro-drop ones, and this process
is repeated 1000 times to gain the average statistic values. The test results
are shown in Table 3. For distance-weighted models, BERT and Word2Vec show
significant results (p $<$ 0.05), and GloVe show marginally significant result
(p = 0.063). For distance-unweighted models, none of them show significant
results. The Wilcoxon test results based on ranged salience are shown in Table
3 in columns “range $<$ 10/20/30 clauses” as compared to the non-ranged
results in “range = all”. As shown in the table, the effects of “pro-drop $>$
non-pro-drop” on correct character salience tend to be larger when the
salience is calculated based on ranged clauses. The Baseline model shows null
effects on both distance-weighted and distance-unweighted models for all the
ranged cases. As shown in Figure 3, the boxplots are consistent with the
Wilcoxon tests.

###  4.2 Logistic Regression: Predict Pro-drop with Character Salience

With the salience values described in the previous section, the logistic
regression model is applied to examine the effect of salience on pro-drop. 75%
of the data are used as the training set, and 25% of the data are used as the
testing set. See the prediction accuracy results in Table 4 based on salience
values obtained from all-ranged and clause-ranged clauses. As shown in Table
4, except for the baseline model, all the distance-weighted language models’
results show above chance ( $>$ 50%) accuracy. As for distance-unweighted
language models, only GloVe and Word2Vec show above chance results on all-
ranged predictions. Similar to the “range-effect” shown in the previous
section, it can be seen from the prediction results as well that ranged
clauses’ prediction accuracies tend to be slightly higher than non-ranged
results.

##  5 Discussion

The main findings of this study are: (1) Compared with overtly expressed
subjects, omitted subjects have higher verb-usage continuity. In this respect,
they stand out among other story characters; (2) Clause distance plays a role
in contextual information strength: With clause distance weighted, the pro-
drop $>$ non-pro-drop salience effects are statistically significant; (3)
Constraining the range of candidates by clause recency appears to strengthen
these effects.

These results validate Topic Chain theory (Tsao, 1977) by showing how verbs
contribute to the discourse coherence that omitted pronouns depend on. The
“ranged” recency effect indicates that local contextual coherence might play a
more important role than whole-discourse-level coherence. This recency effect
may also explain the better performance obtained by BERT and Word2Vec compared
to GloVe, since GloVe word embeddings are obtained from discourse-level word
co-occurrence statistical features, and BERT and Word2Vec are trained on
comparably smaller scale contextual information.

It shall be noted that verb-usage continuity is not the only factor that
conditions pro-drop. Other factors, including nonverbal lexical information
and syntactic patterns e.g. with conjunctions, also support discourse
coherence (Halliday and Hasan, 1976). In this light, it is remarkable that one
factor on its own, verb-usage continuity, yields above-chance accuracy in
predicting pro-drop.

##  6 Conclusion

This study quantifies character-verb usage continuity as an aspect of
discourse that helps comprehenders resolve omitted pronouns. Omitted pronouns
tend to show higher verb usage consistency compared to pronounced entities,
and this effect is strengthened by clause recency.

## Acknowledgements

This material is based upon work supported by the National Science Foundation
under Grant No. 1903783.

## References

  * Chen et al. (2021) Shisong Chen, Binbin Gu, Jianfeng Qu, Zhixu Li, An Liu, Lei Zhao, and Zhigang Chen. 2021.  Tackling zero pronoun resolution and non-zero coreference resolution jointly.  In _Proceedings of the 25th Conference on Computational Natural Language Learning_ , pages 518–527.
  * Halliday and Hasan (1976) Michael Alexander Kirkwood Halliday and Ruqaiya Hasan. 1976.  Cohesion in English.  _English Language Series, Longman, London_.
  * Huang (1984) C-T James Huang. 1984.  On the distribution and reference of empty pronouns.  _Linguistic inquiry_ , pages 531–574.
  * Huang (1994) Yan Huang. 1994.  _The syntax and pragmatics of anaphora: A study with special reference to Chinese_.  Cambridge University Press.
  * Iida et al. (2006) Ryu Iida, Kentaro Inui, and Yuji Matsumoto. 2006.  Exploiting syntactic patterns as clues in zero-anaphora resolution.  In _Proceedings of the 21st International Conference on Computational Linguistics and 44th Annual Meeting of the Association for Computational Linguistics_ , pages 625–632.
  * Iida et al. (2015) Ryu Iida, Kentaro Torisawa, Chikara Hashimoto, Jong-Hoon Oh, and Julien Kloetzer. 2015.  Intra-sentential zero anaphora resolution using subject sharing recognition.  In _EMNLP_ , pages 2179–2189.
  * Kenton and Toutanova (2019) Jacob Devlin Ming-Wei Chang Kenton and Lee Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of NAACL-HLT_ , pages 4171–4186.
  * Kong et al. (2019) Fang Kong, Min Zhang, and Guodong Zhou. 2019.  Chinese zero pronoun resolution: A chain-to-chain approach.  _ACM Transactions on Asian and Low-Resource Language Information Processing (TALLIP)_ , 19(1):1–21.
  * Lenci (2018) Alessandro Lenci. 2018.  Distributional models of word meaning.  _Annual review of Linguistics_ , 4:151–171.
  * Li and Thompson (1979) Charles N Li and Sandra A Thompson. 1979.  Third-person pronouns and zero-anaphora in Chinese discourse.  In _Discourse and syntax_ , pages 311–335. Brill.
  * Li et al. (2018) Shen Li, Zhe Zhao, Renfen Hu, Wensi Li, Tao Liu, and Xiaoyong Du. 2018.  Analogical reasoning on Chinese morphological and semantic relations.  In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 2: Short Papers)_ , pages 138–143, Melbourne, Australia. Association for Computational Linguistics.
  * Li (2004) Wendan Li. 2004.  Topic chains in Chinese discourse.  _Discourse Processes_ , 37(1):25–45.
  * Mikolov et al. (2013a) Tomas Mikolov, Kai Chen, Greg Corrado, and Jeffrey Dean. 2013a.  Efficient estimation of word representations in vector space.  _arXiv preprint arXiv:1301.3781_.
  * Mikolov et al. (2013b) Tomas Mikolov, Ilya Sutskever, Kai Chen, Greg S Corrado, and Jeff Dean. 2013b.  Distributed representations of words and phrases and their compositionality.  _Advances in neural information processing systems_ , 26.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D Manning. 2014.  GloVe: Global vectors for word representation.  In _Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP)_ , pages 1532–1543.
  * Pilehvar and Camacho-Collados (2020) Mohammad Taher Pilehvar and Jose Camacho-Collados. 2020.  Embeddings in natural language processing: theory and advances in vector representations of meaning.  _Synthesis Lectures on Human Language Technologies_ , 13(4):1–175.
  * Pu (2019a) Ming-Ming Pu. 2019a.  _Zero anaphora and topic chain in Chinese Discourse_.  Routledge.
  * Pu (2019b) Ming-Ming Pu. 2019b.  Zero anaphora and topic chain in Chinese discourse.  In _The Routledge Handbook of Chinese Discourse Analysis_ , pages 188–200. Routledge.
  * Qi et al. (2020) Peng Qi, Yuhao Zhang, Yuhui Zhang, Jason Bolton, and Christopher D Manning. 2020\.  Stanza: A python natural language processing toolkit for many human languages.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations_ , pages 101–108.
  * Sperber and Wilson (1986) Dan Sperber and Deirdre Wilson. 1986.  _Relevance: Communication and cognition_ , volume 142.  Citeseer.
  * Sun (2019) Kun Sun. 2019.  The integration functions of topic chains in Chinese discourse.  _Acta Linguistica Asiatica_ , 9(1):29–57.
  * Tsao (1977) Fengfu Tsao. 1977.  _A functional study of topic in Chinese: The first step towards discourse analysis_.  Ph.D. thesis, USC, Los Angeles, California.
  * Wang and Sun (2015) William SY Wang and Chaofen Sun. 2015.  _The Oxford handbook of Chinese linguistics_.  Oxford University Press.
  * xiaowangzi.org (2021) xiaowangzi.org. 2021.  小王子网站.  http://www.xiaowangzi.org/.  Accessed: 2021-04-03.

##  Appendix A Appendix

Story character | Annotation Label | Number of Occurrence
---|---|---
the little prince | ch4_prince | 676
the story teller | ch1_storyteller | 356
the rose | ch12_rose | 166
the king | ch18_king | 71
the fox | ch28_fox | 67
the planet | ch11_planet | 62
the lamplighter | ch23_lighter | 54
the sheep | ch5_sheep | 48
the geologist | ch24_geologist | 41
the grownups | ch3_grownups | 39
the snake | ch26_snake | 39
the businessman | ch22_shiyejia | 37
readers | ch8_audience | 30
the volcano | ch17_volcano | 22
the baobab | ch9_tree | 20
the drunk man | ch21_drunk | 18
the conceited man | ch20_xurong | 16
the travelers | ch31_traveler | 15
the seed | ch10_grass | 13
the explorer | ch25_explorer | 13
the red-faced man | ch14_redface | 11
the boa | ch2_boa | 10
the switch man | ch29_switcher | 10
the astronomer | ch6_universescholar | 7
the echo | ch27_echo | 5
the tiger | ch15_tiger | 5
the drafts | ch16_wind | 4
the train | ch30_train | 4
the merchant | ch32_merchant | 4
the children | ch13_kids | 3
the general | ch19_general | 3
the ruler | ch7_ruler | 1

Table A1: The number of occurrence of each
character in the annotated discourse

| Agent | Patient
---|---|---
pro-drop | 422 | 16
non-pro-drop | 2032 | 1329
total number | 2454 | 1345

Table A2: Distribution of annotated Agents and Patients in the whole
discourse.

verb | 回来
---|---
verb_id | 16008
agent_character | ch4
pro_drop | False
ch1_prev_verbs | [只有, 看到, 想, 用, 画, 画, 让, 画,…]
ch2_prev_verbs | [咀嚼, 吞, 动弹, 消化, 消化, 开, 闭, 闭,…]
ch3_prev_verbs | [理解, 看, 懂, 需要, 解释, 劝, 靠, 弄,…]
ch4_prev_verbs | [朝, 望, 出现, 给, 像, 没有, 像, 干,…]
ch5_prev_verbs | [病, 需要, 像, 睡, 去, 用, 跑, 跑,…]
… | …
ch30_prev_verbs | [运载, 发, 往, 朝着, 开, 过]
ch31_prev_verbs | [寻找, 回来, 满意, 住, 追随, 追随, 睡觉, 打哈欠,…]
ch32_prev_verbs | [说道, 贩卖, 卖, 说]

Table A3: Example of Verb-Character table. (See a translation of this table in
Table A4)

verb | come back
---|---
verb_id | 16008
agent_character | ch4
pro_drop | False
ch1_prev_verbs | [have, see, want, use, draw, draw, let, draw,…]
ch2_prev_verbs | [chew, swallow, move, digest, digest, open, close, close,…]
ch3_prev_verbs | [understand, see, understand, need, explain, advise, lean, play,…]
ch4_prev_verbs | [turn, watch, show up, give, alike, (not) have, alike, do,…]
ch5_prev_verbs | [sick, need, alike, sleep, go, use, run, run,…]
… | …
ch30_prev_verbs | [carry, send, go, turn, drive, pass]
ch31_prev_verbs | [look up, come back, satisfy, live, follow, follow, sleep, yawn,…]
ch32_prev_verbs | [speak, sell, sell, say]

Table A4: Translation of Table A3: Example of Verb-Character table.

Relevance Regressor | (Non-weighted relevance, Weighted relevance)
---|---
rel_glove_ch1 | (81.89066125531684, 0.32419914580071807)
rel_glove_ch2 | (1.8756812506219913, 0.001503683756709864)
… | …
rel_glove_ch32 | (0.8230171383397842, 0.001262691669193839)
rel_bert_ch1 | (176.59183087820725, 0.6119750732174682)
rel_bert_ch2 | (4.919826668243348, 0.0027848581443943223)
… | …
rel_bert_ch32 | (0.867459723760406, 0.001329274033713714)
rel_word2vec_ch1 | (134.572604613474, 0.4595537826115222)
rel_word2vec_ch2 | (2.8936049625643223, 0.0020496541891822087)
… | …
rel_word2vec_ch32 | (0.9999583161919829, 0.0015334960473239322)
rel_baseline_ch1 | (-0.771830408650495, 0.008005141647819333)
rel_baseline_ch2 | (-0.008373434318707955, 5.9110606393949324e-05)
… | …
rel_baseline_ch32 | (0.08827132539725344, 0.00013526127447238275)

Table A5: Example of relevance results for the last verb

Regressor | Example value
---|---
verb | 回来 (come back)
correct character | ch4
pro-drop | False
salience-glove-unweighted | 45.761057
salience-bert-unweighted | 57.886974
salience-word2vec-unweighted | 56.125342
salience-baseline-unweighted | 1.087911
salience-glove-weighted | 1.206085
salience-bert-weighted | 1.522071
salience-word2vec-weighted | 1.427663
salience-baseline-weighted | 0.979743

Table A6: Example of salience results for the last verb from three language
models and one baseline model with distance-weighted/-unweighted