11institutetext: Autonomous Systems Laboratory, Department of Future
Technologies, University of Turku, Vesilinnantie 5, 20500 Turku, Finland
11email: {janaya, mohhag<EMAIL_ADDRESS>
22institutetext: Connected Shopping Ltd, Thetford, UK
22email<EMAIL_ADDRESS>33institutetext: Department of
Computer Networks, College of Computer Sciences & Information Technology, King
Faisal University, Hofuf, Saudi Arabia
33email<EMAIL_ADDRESS>
# Cellular Formation Maintenance and Collision Avoidance Using Centroid-Based
Point Set Registration in a Swarm of Drones

Jawad N. Yasin 11 Huma Mahboob 22 Mohammad-Hashem Haghbayan 11 Muhammad
Mehboob Yasin 33 Juha Plosila 11

###### Abstract

This work focuses on low-energy collision avoidance and formation maintenance
in autonomous swarms of drones. Here, the two main problems are: 1) how to
avoid collisions by temporarily breaking the formation, i.e., collision
avoidance reformation, and 2) how do such reformation while minimizing the
deviation resulting in minimization of the overall time and energy consumption
of the drones. To address the first question, we use cellular automata based
technique to find an efficient formation that avoids the obstacle while
minimizing the time and energy. Concerning the second question, a near-optimal
reformation of the swarm after successful collision avoidance is achieved by
applying a temperature function reduction technique, originally used in the
point set registration process. The goal of the reformation process is to
remove the disturbance while minimizing the overall time it takes for the
swarm to reach the destination and consequently reducing the energy
consumption required by this operation. To measure the degree of formation
disturbance due to collision avoidance, deviation of the centroid of the swarm
formation is used, inspired by the concept of the center of mass in classical
mechanics. Experimental results show the efficiency of the proposed technique,
in terms of performance and energy.

###### keywords:

multi-agent system, formation maintenance, swarm intelligence, collision
avoidance, point set registration

##  1 Introduction

A swarm is a concept that seems to have no precise definition in literature as
such; instead, we find a lot of definitions and discussion addressing swarming
i.e. swarm behaviour [1]. Swarm robotics can be classified as the study of how
a system, consisting of large number of a relatively simple agents, can be
designed to attain a desired cumulative behaviour based on the interactions
between the agents themselves and between the agents and the environment [2,
3]. Due to their ability to work in a collaborative style, swarms of
autonomous agents add significant advantages over the use of single agent, and
therefore they have high demand in diverse fields such as search and rescue,
surveying and mapping, inspection, and delivery, in both military and
civilian/commercial contexts[4]. Consequently, the interest of the research
community is increasing towards optimization of various autonomy
characteristics of drone swarms, for instance collision avoidance, formation
maintenance, resource allocation, and navigation [5, 6]. In swarm navigation
and formation flight, collision avoidance and maintenance of the formation are
the most important problems [7, 8]. Formation control methodologies can be
categorized into three main approaches: 1) the leader-follower based approach,
where every node/drone works autonomously and individually by maintaining a
given formation as perfectly as possible by adjusting its position with
respect to its neighbours and the leader drone [9, 10, 4]; 2) the behaviour
based approach, where, based on a pre-determined strategy, one behaviour is
chosen out of the available ones [11, 12]; and 3) the virtual structure based
approach, where the swarm is considered a single entity, i.e. a single large
drone effectively, and navigated through a trajectory accordingly [13, 14].

Cellular automata based modelling provides the environment that each cell can
decide its movement by only looking at its neighbours and the environment and
based on its rules that are defined for each individual cell dynamically and
run-time [15]. The modelling of cellular automata in our collision avoidance
algorithm provide us the opportunity to reform the system to pass the obstacle
only by defining some distributed rules for each individual drone. In other
words to pass the collision we do not need to have a central processing
element that defines the path of each drone. In return each node,
individually, in a dynamic and flexible movement can pass the obstacle so that
the overall time and energy consumption of the swarm is optimized. To define
these rules for individual drones, we make use of genetic algorithm techniques
that is highly compatible with cellular automata model.

A genetic algorithm (GA) is one of the simplest random-based classical
evolutionary computing methods, where random changes are applied to the
current solutions to generate new solutions for finding an optimal or near-
optimal solution [16]. GAs work by utilizing the basic principles of
generation of potential random solutions, selection of the best solution by
calculating the distance of each solution to the destination, generation of
new solutions based on the generated good solutions, and repeating these steps
in order to reach the desired result [17, 18]. The ability of GAs to converge
close to the global optimum and their relatively simple implementation make
them quite popular among available optimization heuristics [19].

Point set registration is a commonly used method, playing an important role in
various applications such as image retrieval, 3D reconstruction, shape and
object recognition, and SLAM [20]. In point set registration, the correlation
between two point sets is determined in order to retrieve the required
transformation that maps one point set to the other [21].

Our algorithm has two phases:

  * •

The first phase is a cellular automata based collision avoidance scheme that
disturbs the original formation to pass the obstacle.

  * •

The second phase is a re-formation scheme, inspired by point set registration,
that will resume from the highest disturbed formation to the original
formation.

In this paper, the leader-follower based approach is utilized for drone swarm
control due to its reliability, ease of implementation and analysis, and
scalability [22, 23]. However, in our proposed solution, there is no unique
global leader, as the leader gets changed dynamically based on certain
constraints. The cellular formation and collision avoidance algorithms are
integrated with a simple GA-inspired approach and a point set registration
method in order to optimize the collision avoidance and re-formation phases.
The goal is to calculate the escape routes and select a near-optimal path upon
detection of an obstacle, having minimal deviation from the original route.
Once a defined danger zone has been passed, for reconstruction of the
formation, centroid-based point set registration (CPSR) is used in the
formation maintenance algorithm to optimally bring back each drone that lost
its position in the formation when avoiding a collision with the detected
moving obstacle.

Using a GA-inspired approach for collision avoidance in a swarm of robots/UAVs
is beneficial as it allows the algorithm to check for all possible maneuvers
and select the best solution depending on the pre-defined constraints such as
the minimal movement requirement and power consumption limitations.
Furthermore, with the help of CPSR, once a collision has been avoided, the
formation can be obtained again swiftly and optimally by bringing the UAVs
back to the desired formation shape. CPSR facilitates this dynamic recovery
process and autonomous switching of the swarm leader according to the
requirements posed by the scenario at hand. This can be very helpful
especially in cases where the time to complete a mission is critical.

The rest of the paper is structured as follows. In Section 2, the proposed
algorithm is described. Section 3 provides the simulation results. Finally,
Section 4 concludes the paper with some discussion and comments on future
work.

##  2 PROPOSED APPROACH

The general pseudo code of the proposed approach is given in Algorithm 1. We
start with the assumption that the leader-follower connection has been
established and that the formation is already maintained before a mission
starts. By utilizing the on-board processing units, this top-level algorithm
is executed by every individual node locally. Algorithm 1 starts by
initializing the Boolean variable/flag $FLAG_{obs}$ (Line 2) whose role is to
indicate absence ($False$) or presence ($True$) of an obstacle.Then the target
shape (TShape) of the swarm is initialized based on the current state or
position of each node with respect to the others (Line 3). TShape is the next
targeted formation shape calculated at every interval for the next time
interval, determining the next target position for each node to propagate to.

After the above initial steps, the main loop (Lines 4-13) is entered. First,
the procedure ObstacleDetection is called, and based on the values of the
variables/signals calculated by this algorithm, information on the presence
and characteristics of a potential obstacle is available (Line 5). In case an
obstacle is detected, i.e., $FLAG_{obs}$ $==$ $True$, the procedure
CollisionAvoidance is called, and TShape is set up according to the feedback
received (Lines 6-7). After this, once a collision has been successfully
avoided, $FLAG_{obs}$ is reset to $False$ (Line 8). On the other hand, if no
obstacle is detected, i.e., if $FLAG_{obs}$ $==$ $False$ holds after the
execution of ObstacleDetection, then TShape is updated without an involvement
of the collision avoidance procedure (Line 10). Finally, the point set
registration based re-formation algorithm PS-ReFormation is called to re-
establish the desired formation (Line 12). This has an effect only if the
formation is distorted due to a collision avoidance event.

It is important to note here that in the point set registration of the re-
formation process, it is crucial to optimally and rapidly calculate the
mapping between the current and desired shapes of the swarm. This is the case
especially when complicated movements are involved which drastically change
TShape of the swarm, for instance, when the angle of the leader’s movement
strongly changes due to the presence of an obstacle on the path.

Algorithm 1 Global Routine

procedure Obstacle Detection & Navigation

2: $FLAG_{obs}$ $\leftarrow$ $False$;

TShape $\leftarrow$ Initialization based on current state;

4: while True do

$FLAG_{obs},D_{obs},A_{obs},V_{obs},D_{impact}$ $\leftarrow$ Obstacle
Detection();

6: if $FLAG_{obs}$ then

TShape $\leftarrow$ CollisionAvoidance($D_{obs},A_{obs},V_{obs},D_{impact}$);

8: $FLAG_{obs}$ $\leftarrow$ $False$;

else

10: Update TShape;

end if

12: PS-Reformation(TShape);

end while

14:end procedure

###  2.1 Obstacle detection

Algorithm 2 Obstacle Detection

procedure Obstacle Detection()

2: if $obstacle$ in $Detection\\_Range$ then

$FLAG_{obs}$ $\leftarrow$ $True$;

4: $D_{obs}$, $A_{obs}$ $\leftarrow$ Calculate obstacle distance and angles at
which the edges lie;

$V_{obs}$ $\leftarrow$ Calculate obstacle Velocity;

6: $D_{impact}$ $\leftarrow$ Calculate distance to impact;

return($FLAG_{obs},D_{obs},A_{obs},V_{obs},D_{impact}$)

8: end if

end procedure

In this procedure (specified in Algorithm 2), the node continuously scans for
the obstacles, and soon as there is an obstacle in the detection range of the
on-board sensor system, the signal flag $FLAG_{obs}$ is set to $True$ (Lines
2-3). After this, the calculation of the parameters of the obstacle is done,
i.e., the distance to the obstacle ($D_{obs}$) and the angle at which the
detected obstacle lies $A_{obs}$ (Line 4), as shown in Figure 1. Then it is
determined if the obstacle is moving or stationary (Line 5), using Equations
(1)-(3) and illustrated in Figure 2. The velocity of the obstacle ($V_{obs}$)
is computed, and based on the value of $V_{obs}$, we have three possible case
scenarios: (1) if $V_{obs}$ == 0 then the environment is static or the
obstacle under observation is stationary; (2) if $V_{obs}$ is negative, then
the obstacle is coming towards the UAV; or (3) if $V_{obs}$ is positive, then
the obstacle is going away from the UAV. Based on the computed velocity of the
obstacle, distance to the potential impact ($D_{impact}$) is calculated (Lines
5-6). These calculations are elaborated in the equations below.

Figure 1: Distance and Direction Calculation  Table 1: Description of Variables from Fig. 1 Variables | Description
---|---
$DR_{i}$ | distance of right and left edges
$DL_{i}$ | of the obstacle from leader, follower 1
| and follower 2 as shown in Figure
dF1L | distance of leader from follower 1 and
dF2L | follower 2 respectively
$\theta\textsubscript{LOR}$ | angle at which right and left edges are
$\theta\textsubscript{LOL}$ | detected from leader respectively
$\theta\textsubscript{F1L}$ | angle of leader from follower 1 and
$\theta\textsubscript{F2L}$ | follower 2, respectively

We know that after $t_{1}$ seconds, the distance travelled by the UAV can be
calculated by:

$d_{UAV}=v*(t_{1}-{t_{0}})$ (1)

Figure 2: Moving Obstacle Calculation

Then the distance travelled in the meantime by the obstacle and the velocity
of the obstacle are calculated by (2) and (3), respectively:

$d_{obs}=d_{o}-d_{UAV}-d_{1}$ (2)

where $d_{o},d_{1}$ are the distances between the UAV and the obstacle at
times $t_{o}$ and $t_{1}$ respectively.

$v_{obs}=d_{obs}/\Delta t$ (3)

In Eq. (2), if $d_{obs}$ == 0, it means the obstacle is stationary. Otherwise
the obstacle is moving and in that case if the distance between the obstacle
and the UAV after $t_{1}$, i.e., $d_{1}$ is less than the distance detected at
time $t_{o}$, i.e., $d_{o}$, then the obstacle is moving towards the UAV
(Figure 2). If $d_{1}$ is greater than $d_{o}$, it means the obstacle moving
away from the UAV. Figure 3(a) shows the point when the obstacle has entered
the detection range of the UAV. The obstacle’s trace of movement is shown as a
red dotted line; similarly, the UAVs’ traces of movement are shown as
correspondingly coloured lines behind the smaller coloured circles
representing three UAVs. Based on the movement of the obstacle, the
computational point of impact and the dimensions of the obstacle are
calculated, and based on these the Danger Zone (the red circle, the point of
impact is the red dot inside it) is defined as shown in Figure 3(a).

(a)

(b)

Figure 3: (a) Point of impact and Danger Zone as they appear dynamically. (b)
Highest level of disturbance illustration

###  2.2 Collision Avoidance

Collision avoidance in our proposed algorithm is simply defining continuously
the next step formation for the swarm in a way that this sequence of
formations can pass the obstacle. This re-forming of the swarm continues until
the swarm reaches the highest formation disturbance in which it is guaranteed
the swarm can pass the obstacle. The highest formation disturbance is defined
as the state when all the drones have passed the line perpendicular to the
velocity vector of the swarm, i.e., swarm movement in Figure 3(b), and passing
through the mass point of the obstacle, see Figure 3(b). After that the swarm
resumes back to its original formation via TPS-based algorithm [24] that will
be discussed in the reformation section111Even though the highest formation
disturbance state might not totally guarantee not to have collision in TPS-
based reformation phase, we take this assumption to simplify finding the
moment of switching from GA-based collision avoidance phase to TPS-based
resuming the original formation.. In this section we only cover the collision
avoidance algorithm until reaching the highest level of disturbance. The goal
here is to determine rules for each drone by which the drones pass the
obstacle in a way that the time and energy minimizes. To do this we made use
of applying GA in a cellular automata (CA) model of the swarm. This model is
based on separating the space, 2D or 3D, into identical grid zones where the
size of the grid is determined to encompass one drone in its safe distance
from the borders of the grid. Using this modeling method, 2D/3D environment
can be divided to identical grid zones, cells, where existences and non-
existence of a drone in each grid can change the state of the cell to one and
zero respectively. Figure 4(a) shows such a model for 2 drones and one
obstacle in 2D environment. Each cell in this model only can see its
neighbors, like standard CA [15], and based on the neighbors it decides its
next state. If the cell is occupied by a drone, the next state of the cell is
determined via the movement of the drone that is limited towards cardinal and
inter-cardinal directions (Figure 4(b)).

Our GA-based algorithm tries to find the best possible rule for each cell
occupied by the drone i.e., black, that minimizes the time. The time in this
model is the number of steps for the swarm to reach the highest level of
disturbance. The energy in each step, i.e., for the CA rule, can only have
three values, 1) ’0’, when the drone stays in its position, 2) ’1’, when there
is a movement toward one cardinal direction, and 3) ’2’, when there is a
movement toward one inter-cardinal direction. The overall energy for a drone
is the summation of energy consumption in each iteration from the start of
reformation to highest formation disturbance state.

(a)

(b)

Figure 4: (a) 2D model of 2 drones and one obstacle. (b) Example of movement
according to a rule. Algorithm 3 CollisionAvoidance

procedure CollisionAvoidance($D_{obs},A_{obs},V_{obs},D_{impact}$)

2: $DangerZone$ $\leftarrow$ Calculate based on $D_{impact}$ and obstacle
dimensions;

while $DangerZone$ do

4: Calculate Escape routes;

Update the TShape using GA;

6: end while

return(TShape)

8:end procedure

The population of the potential solutions was done by applying the following
principles:

  * •

generation of potential random solutions by defining different rules for each
drone

  * •

calculate the time and energy of each solution when reaching the highest
disturbance formation is targeted, i.e., when all the drones pass the
obstacle,

  * •

regenerate new solutions by mutation of good obtained rules for each drone

These routines are integrated with the collision avoidance developed and
presented in [9], in such a way that the translated TShape destination of each
node of the swarm is checked at each time interval. If there is an obstacle in
the path of a node, the TShape destination may not be the same as the original
destination. Therefore, the TShape destination is calculated by using a fixed
grid around the danger zone in order to restrict the GA from populating
infinite exhaustive solutions. Afterwards at each iteration, the way to reach
the TShape destination is optimized by point set registration.

###  2.3 Re-Formation

Observing and avoiding an obstacle by the swarm, in most of the cases
changes/disturbs the formation of the swarm until reaching the highest
disturbance formation where after the swarm must be restored to the initial
formation state. This process raises a formation construction problem that is
widely covered in the literature. However, in our case, the re-formation
algorithm, or in other words the disturbance rejection of a swarm, must be
compatible with our obstacle detection and collision avoidance algorithm whose
main target is to reduce the overall settling time and energy of the system,
i.e., bringing the disturbed centroid back to its intended state in the
TShape. It is worth mentioning that in the process of resuming the formation
it is not necessarily needed to keep the initial neighbouring state among the
drones since in the formation all the drones are considered to be an identical
node. Furthermore, since there is no dedicated leader and leader is only
selected according to the situation at hand, therefore the dynamicity of re-
formation process gets smoother with no pauses or unnecessary waiting times
for nodes. For example, in the original state if drone 1 has two neighbors
drone 2 and 3, after the reconstruction and resuming the formation this might
not necessarily happen. Or as shown in next section (Figure 6), the leader
before the swarm gets disturbed and after the reformation process is not the
same, as the leader was re-elected dynamically.

In the process of resuming back from the disturbed state of the swarm
formation, referred to as the scene in this section, to the initial formation
state, i.e., the TShape model, two main questions are: 1) what is the optimal
alignment or mapping of identical nodes in the disturbed formation of the
swarm, i.e., the scene, and in the initial formation, i.e., TShape model; and
2) what is the optimal trajectory of each node in the scene to be mapped into
the corresponding node in the TShape model? For the first problem, we adopt a
well-know idea in point set registration [20, 21] that is based on the thin-
plate spline (TPS) technique that is used in data interpolation and smoothing
[25]. After determining the mapping strategy, for the second problem, we use
the shortest path scheme when applying the proposed collision avoidance
approach. In the following, we first explain the concept of thin-plate
splines, and after this we propose an algorithm based on that.

A piece-wise function defined by polynomials is known as a spline. Complex and
complicated shapes are approximated with ease via curve fitting using splines
due to their non-complicated construction [25]. For simplicity, we discuss the
algorithm for 2-dimensional formulation and presume to have two sets of
correlating data sets or points $X$ i.e. $x_{i}$, i = 1, 2, . . . , $n$ and
$V$ i.e. $v_{i}$, i = 1, 2, . . . , $n$. Where $x_{i}$ and $v_{i}$ are the
coordinate representation of the locations of a point, $x_{i}$ = (1, $x_{i}x$,
$x_{i}y$) and $v_{i}$ = (1, $v_{i}x$, $v_{i}y$), in the scene and model
respectively. Considering the shape of the disturbed function, finding a
mapping function $f(v_{i})$ that fits between correlating point sets $X$ and
$V$ can be obtained by minimizing the following:

$\begin{split}E_{TPS}(f)=\sum_{i=1}^{n}||x_{i}-f(v_{i})||^{2}+\\\
\lambda\iint[(\frac{\partial^{2}f}{\partial
x^{2}})^{2}+2(\frac{\partial^{2}f}{\partial x\partial
y})^{2}+(\frac{\partial^{2}f}{\partial y^{2}})]dxdy\end{split}$ (4)

Where $E_{TPS}$ is the energy function that is considered as the measurement
for the amount of formation disturbance. The integral part of the equation
represents how the corresponding point sets are mapped to the correlating
point set by keeping the intended formation under consideration. Also, the
factor $\lambda$ provides the scaling. If the intention is to map one point
set over the other without considering the shape of the disturbed swarm,
$\lambda$ should be set to zero and the closest points are mapped accordingly
without keeping the shape under consideration. In this situation, the
disturbance, i.e., $E_{TPS}$, is simply as follows:

$\begin{split}E_{TPS}(f)=\sum_{i=1}^{n}||x_{i}-f(v_{i})||^{2}\end{split}$ (5)

Minimization of such a temperature function determines the mapping process
from the disturbed swarm in the highest disturbance formation, i.e., the
scene, to the original shape after the obstacle. Via this mapping the new
leader also will be determined. After calculating the mapping function, each
drone from the scene follows the shortest path to reach its hypothetical
location in the model. Since the model in Equation 4 is hypothetical and
uncertain events might affect the process of reformation, a relative run-time
measurement is needed to continuously assure that the swarm is reaching its
formation. This metric is the hypothetical center of the swarm that can be
calculated from an instantaneous location of the drones in the swarm. The
continuous error in the formation that should be dynamically observed and
reduced is calculated by summation of the deviation of the distance of each
drone from the center w.r.t. the golden formation model, that is shown by
$d_{rms}$. As an example, Figure 5 shows the centroid point for three drones
in the golden formation model, i.e., the left side, and the disturbed model,
i.e., the right side. Based on this, the deviation of the distance of each
drone from the center w.r.t. the golden formation model is as follows:

$\displaystyle\begin{split}\Delta d_{1}=d_{c}-d_{1}\\\ \Delta
d_{2}=d_{c}-d_{2}\\\ \Delta d_{3}=d_{c}-d_{3}\end{split}$ (6)

and

$d_{rms}=\sqrt{\Delta d_{1}^{2}+\Delta d_{2}^{2}+\Delta d_{3}^{2}}$ (7)

Figure 5: Centroid of the swarm

The measurment of $d_{rms}$, is a figure of merit. From this equation it is
determined how much the current formation has been distorted from its
original/pre-defined formation. So, minimizing the $d_{rms}$ to zero will
bring back the formation optimally, i.e., $d_{rms}$ $\longrightarrow$ 0.

The reformation process is done by first calculating the centroid of the swarm
as shown in the Figure 5.

These values are then fed to the point set registration, in order to calculate
the optimal solution for bringing the UAVs back to the desired formation, and
in the meantime, bringing the centroid as quickly as possible to the final
destination, which can be seen in the next section, i.e, Simulation & Results.
During the re-formation the leader of the swarm changes dynamically, and the
previous leader (UAV1/Blue UAV) goes to the position of the current leader
(UAV2/Green UAV). The reason for that is, while UAV1 is deviating from its
current trajectory in order to avoid colliding with the obstacle, it slows
down. In the meantime UAV2, which continues in its path, becomes a more likely
candidate for going to the position of UAV1 rather than slowing down for it.
Therefore, UAV2 moves to the location of UAV1, and simultaneously UAV1 moves
to the previous location of UAV2, as soon as UAV1 has successfully avoided the
collision.

##  3 SIMULATION & RESULTS

(a)

(b)

(c)

(d)

(e)

Figure 6: Different time intervals from Spawning to when the obstacle comes in
detection range. (a) When the UAVs are spawned and obstacle is moving towards
the swarm. (b) obstacle is in detection range of the UAV, and Point of Impact
is calculated and shown, UAV1 is deviating from its original path in order to
avoid the Danger Zone. (c) Bypassing the obstacle. (d) bypassing the obstacle
2. (e) Leader changed while bypassing the obstacle.

(a)

(b)

(c)

(d)

(e)

Figure 7: Simulation snapshots at equal time intervals, i.e., 0%, 25%, 50%,
75%, 100% (a) When the UAVs are spawned and obstacle is moving towards the
swarm. (b) obstacle is in detection range of the UAV, and Point of Impact is
calculated and shown, UAV1 is deviating from its original path in order to
avoid the Danger Zone. (c) Bypassing the obstacle. (d) notice the change of
leader while bypassing the obstacle. (e) Leader changed while bypassing the
obstacle.

(a)

(b)

Figure 8: Swarm movement from start to destination. Navigational traces using:
(a) proposed approach (b) dedicated leader

The initial conditions/assumptions for our work are defined as follows:

  1. 1.

there is no explicit unique leader; the leader for the swarm changes
dynamically according to the situation, i.e., the leadership is a temporary
role

  2. 2.

UAVs accelerate or decelerate as needed.

  3. 3.

UAVs obtain their own position vectors using the on-board localization
techniques.

  4. 4.

communication channel ideal, i.e., lossless

  5. 5.

an obstacle can be stationary or moving towards the swarm or away from the
swarm with unknown velocity.

  6. 6.

for visualization purposes and to avoid the overlapping, the detection range
circle of only the leader is shown.

The UAVs are spawned at near the defined V-shaped formation (Figure 6). The
current leader UAV1 (blue), starts moving towards the destination and the
other UAVs start moving towards their positions in the formation. An obstacle
is also moving towards the swarm, but at this instant it is outside the
detection range of the on-board sensor system of the UAVs, as shown in Figure
6(a). In Figure 6(b), the obstacle is already in the detection range and the
Point of Impact and the Danger Zone has been computed, as explained in
Algorithm 2.

Figure 6(c), shows the trend of escape route chosen by the collision avoidance
module by deviating UAV1 to its right and slowing down the velocity of UAV3 to
allow UAV1 stay on chosen route, as explained in Algorithm 3. Figure 6(d) and
6(e) shows reformation process using CPSR, as shown that since UAV1 had to
slow down and deviate to avoid the Danger Zone, UAV2 in the meantime is
dynamically declared as the leader, as it continued its trajectory on the same
path with same velocity, gets ahead of the rest instead of waiting for UAV1 to
get back into its formation position. This is done to make sure time of
arrival of centroid to the destination is minimized. Similarly, the optimal
reformation would require UAV1 to go to UAV2’s place and UAV3 would just speed
up to catch with its position in the formation, as explained in Section II-C.

Figure 8(a), shows the movement of the swarm from starting point till it
reaches the destination. In comparison, the behaviour of the swarm if point
set registration is used with explicit unique leader and without balancing the
centroid of the swarm is shown in Figure 8(b).

The graph (Figure 9(a)) shows the overall trend of the distances maintained by
the UAVs throughout the course, where D31 is the distance between UAV1 and
UAV3, D21 is the distance between UAV1 and UAV2, and D32 is the distance
between UAV2 and UAV3. The obstacle gets detected at $t=30s$, and the
collision avoidance is enforced which distorts the formation (Figure 6).

In order to test the scalability of the proposed algorithm, the number of
nodes in the swarm was increased to make a two layered V-shaped formation, as
shown in Figure 7. The little overshoots in the movements of the drones in the
figure can be reduced by integrating a more stable speed controller into the
algorithm. Figure 9(b), shows the change in the temperature of the system,
i.e., the swarm, from the start until the destination is reached. At $t=30s$,
the disturbance/change in the temperature of the system shows the obstacle
detection. The other significant disturbance at $t=75s$ is due to the leader
change and from there on the swarm gradually reshapes itself into the target
shape defined by TShape.

(a) (b)

Figure 9: (a) Distance maintained by drones with each other. (b) Change in
Temperature of the system as a whole

Figure 10 shows the time taken for the swarm to reach its destination in four
different scenarios: ”No obstacle”, i.e., if it is not disturbed at all and
there are no deviations from the path, then $t_{0}=166s$; ”Unique”, i.e., if
there is an obstacle in the path and the swarm has a unique dedicated leader,
then $t_{1}=213s$; and finally two cases experimenting our proposed approach,
i.e., in ”3-CPSR” (a swarm with 3 nodes like in the previous cases) and
”8-CPSR” (with 8 nodes), the time to finish was $t_{2}=181s$ and $t_{3}=198s$,
respectively. This shows that we can considerably reduce the time by
dynamically re-forming the swarm and changing the leader at run-time whenever
the situation requires. The reason for this is that in the CPSR approach the
swarm does not stop at any moment but keeps on progressing towards the
destination, with each UAV deviating to avoid a collision when needed and
accelerating afterwards to reach its position, defined by TShape, to maintain
the formation. On the other hand, in the fixed leader case (”Unique”), the
swarm will slow down and wait for the leader to resume its position in the
front before continuing towards the destination.

When considering the three-drone formation (Figure 6), the swarm needed 56s
from the obstacle detection to come back into the initial formation, whereas
in the eight-drones case (Figure 7), this took 85s. It is evident from the
experiments that in the latter case, due to a much bigger obstacle, the drones
had to deviate more than in the former case. However, this did not affect the
overall mission time very much, as UAV2, which became the new leader, did not
have to deviate a lot from its path nor reduce its speed significantly.

$180$$200$$220$$166$$181$$198$$213$Time (s)No obstacle3-CPSR8-CPSRUnique

Figure 10: Time for mission completion for different approaches

##  4 CONCLUSION

In this paper, we developed a novel approach for collision avoidance and
formation maintenance in a swarm of drones in dynamic environments. The
proposed method utilizes a genetic algorithm inspired scheme in its collision
avoidance part and point set registration in its formation maintenance part.
In the approach, a swarm does not have a uniquely determined leader, and
formation maintenance is accomplished by stabilizing the centroid of the
swarm. The behaviour of the algorithm was theoretically analysed and tested in
a simulation environment. The simulation results shown provide sufficient
proof that the method works in a near-optimal manner in a dynamic environment,
where an obstacle continues movement in its detected trajectory. We tested the
efficiency of the proposed algorithm by comparing it with corresponding
algorithms that assume existence of an explicit/unique leader. It was
demonstrated that the ability to re-elect the leader dynamically, if required,
gets the mission completed more quickly, i.e., it saves time and consequently
energy by sparing the swarm from waiting for the leader to get back into its
defined position in the formation.

In our future work, we plan to extend the proposed approach by examining the
other environmental effects, such as air drag, on the layers of drones, such
as a two or multi layered V-shaped formation. That can help in optimizing the
resource management in the swarm by dynamically swapping the outer layer with
the inner layer in order to minimize the effect of air drag and maximize the
flight time on a single charge. Also, we will consider more complex scenarios
with several simultaneous obstacles and more versatile movement of obstacles.

## Acknowledgement

This work has been supported in part by the Academy of Finland-funded research
project 314048 and Nokia Foundation (Award No. 20200147).

## References

  * [1] Hamann, H.: Introduction to Swarm Robotics, pp. 1–32. Springer International Publishing, Cham (2018), https://doi.org/10.1007/978-3-319-74528-2“˙1
  * [2] Yasin, J.N., Mohamed, S.A.S., Haghbayan, M.H., Heikkonen, J., Tenhunen, H., Yasin, M.M., Plosila, J.: Dynamic formation reshaping based on point set registration in a swarm of drones (2020), https://arxiv.org/abs/2010.15506
  * [3] Dorigo, M., Roosevelt, A.F.: Swarm robotics. In: Special Issue”, Autonomous Robots. Citeseer (2004)
  * [4] Yasin, J.N., Mohamed, S.A.S., Haghbayan, M.H., Heikkonen, J., Tenhunen, H., Plosila, J.: Navigation of autonomous swarm of drones using translational coordinates. In: Demazeau, Y., Holvoet, T., Corchado, J.M., Costantini, S. (eds.) Advances in Practical Applications of Agents, Multi-Agent Systems, and Trustworthiness. The PAAMS Collection. pp. 353–362. Springer International Publishing, Cham (2020)
  * [5] Campion, M., Ranganathan, P., Faruque, S.: A review and future directions of uav swarm communication architectures. In: 2018 IEEE International Conference on Electro/Information Technology (EIT). pp. 0903–0908 (May 2018)
  * [6] He, L., Bai, P., Liang, X., Zhang, J., Wang, W.: Feedback formation control of uav swarm with multiple implicit leaders. Aerospace Science and Technology 72, 327 – 334 (2018), http://www.sciencedirect.com/science/article/pii/S1270963816309816
  * [7] Zhuge, C., Cai, Y., Tang, Z.: A novel dynamic obstacle avoidance algorithm based on collision time histogram. Chinese Journal of Electronics 26(3), 522–529 (2017)
  * [8] Yasin, J.N., Mohamed, S.A.S., Haghbayan, M., Heikkonen, J., Tenhunen, H., Plosila, J.: Unmanned aerial vehicles (uavs): Collision avoidance systems and approaches. IEEE Access 8, 105139–105155 (2020)
  * [9] Yasin, J.N., Haghbayan, M.H., Heikkonen, J., Tenhunen, H., Plosila, J.: Formation maintenance and collision avoidance in a swarm of drones. In: Proceedings of the 2019 3rd International Symposium on Computer Science and Intelligent Control. ISCSIC 2019, Association for Computing Machinery, New York, NY, USA (2019), https://doi.org/10.1145/3386164.3386176
  * [10] Oh, K.K., Park, M.C., Ahn, H.S.: A survey of multi-agent formation control. Automatica 53, 424 – 440 (2015), http://www.sciencedirect.com/science/article/pii/S0005109814004038
  * [11] Lawton, J.R.T., Beard, R.W., Young, B.J.: A decentralized approach to formation maneuvers. IEEE Transactions on Robotics and Automation 19(6), 933–941 (Dec 2003)
  * [12] Balch, T., Arkin, R.C.: Behavior-based formation control for multirobot teams. IEEE Transactions on Robotics and Automation 14(6), 926–939 (Dec 1998)
  * [13] Li, N.H.M., Liu, H.H.T.: Formation uav flight control using virtual structure and motion synchronization. In: 2008 American Control Conference. pp. 1782–1787 (June 2008)
  * [14] Dong, L., Chen, Y., Qu, X.: Formation control strategy for nonholonomic intelligent vehicles based on virtual structure and consensus approach. Procedia Engineering 137, 415 – 424 (2016), http://www.sciencedirect.com/science/article/pii/S1877705816003039, green Intelligent Transportation System and Safety
  * [15] Stephen Wolfram: A New Kind of Science | Online—Table of Contents, https://www.wolframscience.com/nks/, library Catalog: www.wolframscience.com
  * [16] Gad, A.: Introduction to Optimization with Genetic Algorithm (Jul 2018), https://towardsdatascience.com/introduction-to-optimization-with-genetic-algorithm-2f5001d9964b
  * [17] Alander, J.T.: On finding the optimal genetic algorithms for robot control problems. In: Proceedings IROS ’91:IEEE/RSJ International Workshop on Intelligent Robots and Systems ’91. pp. 1313–1318 vol.3 (Nov 1991)
  * [18] Vicencio, K., Davis, B., Gentilini, I.: Multi-goal path planning based on the generalized traveling salesman problem with neighborhoods. In: 2014 IEEE/RSJ International Conference on Intelligent Robots and Systems. pp. 2985–2990 (Sep 2014)
  * [19] Bansal, J.C., Singh, P.K., Pal, N.R.: Evolutionary and swarm intelligence algorithms. Springer (2019)
  * [20] Guo, P., Hu, W., Ren, H., Zhang, Y.: Pcaot: A manhattan point cloud registration method towards large rotation and small overlap. In: 2018 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). pp. 7912–7917 (Oct 2018)
  * [21] Myronenko, A., Song, X.B.: Point-set registration: Coherent point drift. CoRR abs/0905.2635 (2009), http://arxiv.org/abs/0905.2635
  * [22] Yasin, J.N., Mohamed, S.A.S., h. Haghbayan, M., Heikkonen, J., Tenhunen, H., Yasin, M.M., Plosila, J.: Night vision obstacle detection and avoidance based on bio-inspired vision sensors. In: 2020 IEEE Sensors. pp. 1–4 (2020)
  * [23] Han, Q., Li, T., Sun, S., Villarrubia, G., de la Prieta, F.: “1-n” leader-follower formation control of multiple agents based on bearing-only observation. In: Demazeau, Y., Decker, K.S., Bajo Pérez, J., de la Prieta, F. (eds.) Advances in Practical Applications of Agents, Multi-Agent Systems, and Sustainability: The PAAMS Collection. pp. 120–130. Springer International Publishing, Cham (2015)
  * [24] Yasin, J.N., Mohamed, S.A.S., Haghbayan, M.H., Heikkonen, J., Tenhunen, H., Yasin, M.M., Plosila, J.: Energy-efficient formation morphing for collision avoidance in a swarm of drones. IEEE Access 8, 170681–170695 (2020)
  * [25] Haili Chui, Rangarajan, A.: A new algorithm for non-rigid point matching. In: Proceedings IEEE Conference on Computer Vision and Pattern Recognition. CVPR 2000 (Cat. No.PR00662). vol. 2, pp. 44–51 vol.2 (June 2000)


# Weakly-Supervised Methods for Suicide Risk Assessment:
Role of Related Domains

Chenghao Yang1, Yudong Zhang1, Smaranda Muresan1,2
Department of Computer Science, Columbia University1
Data Science Institute, Columbia University2
<EMAIL_ADDRESS>
{zhang.yudong<EMAIL_ADDRESS>
###### Abstract

Social media has become a valuable resource for the study of suicidal ideation
and the assessment of suicide risk. Among social media platforms, Reddit has
emerged as the most promising one due to its anonymity and its focus on topic-
based communities (subreddits) that can be indicative of someone’s state of
mind or interest regarding mental health disorders such as r/SuicideWatch,
r/Anxiety, r/depression. A challenge for previous work on suicide risk
assessment has been the small amount of labeled data. We propose an empirical
investigation into several classes of weakly-supervised approaches, and show
that using pseudo-labeling based on related issues around mental health (e.g.,
anxiety, depression) helps improve model performance for suicide risk
assessment.

##  1 Introduction

Suicide has been identified as one of the leading causes of deaths and
approximately $1.5\%$ of people die by suicide every year WHO et al. (2016);
Fazel and Runeson (2020). Despite years of clinical research on suicide,
researoners have concluded that suicide cannot be predicted using the standard
clinical practice of asking patients about their suicidal thoughts McHugh et
al. (2019). Recently, Coppersmith et al. (2018) and Nock et al. (2019) discuss
the opportunities of using social media combined with natural language
processing (NLP) techniques to complement traditional clinical records and
help in suicide risk analysis and early suicide intervention.

To facilitate further research on automatic suicide risk assessment, Zirikly
et al. (2019) proposed a shared task, where they collected user data from
r/SuicideWatch subreddit and annotated it with user-level suicide risk: no-
risk, low-risk, medium-risk and high-risk. By comparing the results of the
participating teams in this shared task, Zirikly et al. (2019) conclude that
one of the major challenges comes from the insufficient data for intermediate
suicide risk levels (i.e., low risk and medium risk) rather than extreme risk
levels (i.e., no risk and high risk). Matero et al. (2019) find that using a
dual BERT-LSTM-Attention model to separately extract information from both
SuicideWatch and Non-SuicideWatch posts together with feature engineering that
includes emotion features, personality scores, user’s anxiety and depression
scores are important for model performance.

In this paper, instead of feature engineering or complex model architectures,
we explore whether weakly supervised methods and data augmentation techniques
based on clinical psychology research can help improve model performance. We
explore several weakly-supervised methods, and show that a simple approach
based on insights from clinical psychology research O’Connor and Nock (2014)
obtains the best performance. This model uses pseudo-labeling (PL) on data
from the subreddits r/Anxiety and r/depression, which are considered important
risk factors for suicide. We also present a potential application of our model
for studying the suicide risk among people who use drugs, opening the door for
using NLP methods to deepen our understanding between opioid use disorder
(OUD) and mental health. The code for this paper can be found at
https://github.com/yangalan123/WM-SRA.

##  2 Methods

We focus on Task A from the CLPsych 2019 shared task “Predicting the Degree of
Suicide Risk in Reddit Posts” Zirikly et al. (2019). The goal of the task is
to predict the user-level suicide risk category based on their posts in the
r/SuicideWatch subreddit. Specifically, a user $u_{i}$ is associated with a
collection of $n(i)$ posts $C_{i}=\\{x_{i,1},x_{i,2},\dots,x_{i,n(i)}\\}$,
where each post $x_{i,k}(1\leq k\leq n)$ has $m(i,k)$ sentences
$x_{i,k}=[s_{ik,1},s_{ik,2},\dots,s_{ik,m(i,k)}]$. We need to predict
$y_{i}\in\\{a,b,c,d\\}$ using $C_{i}$, where $a,b,c,d$ represent no-risk, low-
risk, medium-risk and high-risk, respectively. In the original dataset, there
are $496$ users in the training set and $125$ users in the test sets. We
further split $100$ users from the training set to create the validation set.
The sizes for the train/valid/test sets are 746, 173, and 186 respectively.

#### Data Pre-processing

Following the advice in Zirikly et al. (2019), we replace all human names and
URLs in the Reddit posts with special tokens ”_PERSON_” and ”_URL_”,
respectively. We also remove punctuation and stop words besides lowercasing.
Due to the limitation of GPU memory, we split those large posts to be passages
with no more than $128$ words111The $128$ maximum passage length is tuned
based on the validation set for both GPU memory and better computational
efficiency for large posts. We do not observe a significant performance drop
without a larger passage length. and make sure that the split point is not in
the middle of the sentence222We use a limited-size stack and greedily add each
sentence into the stack. If adding a new sentence will make the sum of lengths
of all sentences in the stack exceed $128$, we pop out all sentences,
concatenate them to a new passage and then add this new sentence to the stack.
For sentences having more than $128$ words, we treat them as individual
posts.. Such passages are treated as separate posts.

#### Model Architecture

Our architecture is a BERT Devlin et al. (2019) model. We also experimented
with other state-of-the-art pre-trained language models (PLMs), including
RoBERTa Liu et al. (2019) and XLNET Yang et al. (2019), but found BERT to work
the best and thus consider it as our baseline architecture (more details can
be found in Appendix A). Each post $x_{i,k}$ is fed into BERT Devlin et al.
(2019) and we get post embedding $\vec{e}_{i,k}=\text{BERT}(x_{i,k})$. Then we
do simple mean-pooling to obtain the user embedding
$\vec{u}_{i}=\frac{\sum_{k=1}^{n(i)}\vec{e}_{i,k}}{n(i)}$. Finally, we feed
$\vec{u}_{i}$ to a fully-connected layer and use the Softmax layer to predict
the risk level probability $\tilde{P}(y_{i}|C_{i})$. The label with the
largest probability is picked as the final prediction $\hat{y}_{i}$. For
training, the cross entropy loss $\mathcal{L}_{\text{clf}}$ is applied to
optimize our model.

###  2.1 Weakly-supervised Methods

#### Task-Adaptive Pre-training

Recent works Lee et al. (2020); Gururangan et al. (2020) point out that task-
adaptive pre-training (TAP) can help pre-trained language models better adapt
to the target domains and can bring improvement, especially in data-poor
scenarios. Specifically, we continue pre-training (e.g., masked language
modeling for BERT) on a task-relevant unlabeled corpus and then do normal
fine-tuning on the task. Our unlabeled corpus consists of all r/SuicideWatch
posts (aggregated per user) from the training sets of all the tasks (A, B, C)
in the shared task Zirikly et al. (2019). There are $621$ users and $138,057$
posts in this unlabeled corpus. We do continued pre-training for $2$ to $3$
epochs and do early stopping.

#### Multi-view Learning

Multi-view learning Xu et al. (2013) (MVL) is one of the widely recognized
semi-supervised methods. Clark et al. (2018) provides a successful example of
utilizing MVL in sequential labeling tasks. The idea is to create
perturbations by masking words in certain positions and requiring the model to
learn the similar distribution over the complete labeled examples and the
corresponding masked examples besides normal classification training. However,
since ours is a user-level classification task, we cannot directly borrow the
same strategy from Clark et al. (2018) as it mainly works on sequence
labeling. We propose to create perturbations $\tilde{C}_{i}$ based on four
strategies.333The masking proportions for Word-mask and Sent-Mask are tuned
empirically on the validation set.First, for each sentence, we will randomly
mask $10\%$ of tokens (Word-Mask). Second, considering that users may have
posts of many words, we also propose a sentence-level masking strategy (Sent-
Mask). For each post of a single user in the training set, we would randomly
mask $10\%$ of tokens. Third, we only keep the beginning and ending sentences
in each passage (BegEd). Usually these sentences convey the main purpose of
the posts and should preserve important semantics. Forth, we use Bert-
extractive-summarizer Miller (2019) to extract the summary for each passage
(K-Sum). It works mainly by first encoding each sentence $s_{ik,j}$ using a
PLM to a continuous-valued representation $\vec{s}_{ik,j}$ and then training a
K-means clustering over $\vec{s}_{ik,j}$. Finally it will pick $K$ sentences
for each passage that are closest to the center. Empirically, we set $K=5$.

In training, we use KL-divergence to enforce the constraint that the predicted
probability on perturbed examples $\tilde{P}(y_{i}|\tilde{C}_{i})$ should be
close to the one on complete examples (i.e., $\tilde{P}(y_{i}|{C}_{i})$). The
loss incurred by KL-divergence is simply added to the classification loss and
these two losses are optimized together for each training instance.

#### Clinical Psychology Inspired Pseudo-labeling

According to the analysis of the shared task report Zirikly et al. (2019), the
main challenge for the 4-way classification comes from insufficient data for
the intermediate classes (i.e., low-risk and medium-risk). A straightforward
solution is to collect data for these two classes. Recent clinical
psychological research O’Connor and Nock (2014) points out that mental health
issues such as depression and anxiety can be important risk factors for
suicide. Inspired by this study, we collect data from r/Anxiety and
r/depression from Reddit. The time range of all collected data is from
December 1, 2008 to September 30, 2020. We sample a small proportion of the
collected data from both subreddits and after manual verification, we decided
to assign _low-risk_ labels to all r/Anxiety users in the sample and _medium-
risk_ labels to all r/depression users in the sample. Since we do not have
experts to label these posts, adding too much pseudo-labeling data might
introduce too much noise. Based on preliminary experiments on the _validation
set_ , the number of added pseudo-labeling data is $8\%$ of the suicide risk
assessment training data. The only difference between these experiments and
the main experiments is that we only train the model for $10$ epochs rather
than full $20$ epochs. Table 1 show results for different sizes of added
pseudo-labeled data from r/depression on the validation set. All pseudo-
labeling data follows roughly the same pattern with the best proportion being
$8\%$.

$\frac{\\#(\text{r/depression})}{\\#(\text{Training})}$ | Macro-F1 on Validation set
---|---
$2\%$ | $0.408$
$8\%$ | $0.471$
$16\%$ | $0.442$
$32\%$ | $0.408$
Table 1: Results of different proportions of added pseudo-labeling data from r/depression. No. | Approach | Setup |  | Macro (P/R/F1)
---|---|---|---|---
1 | Baseline | BERT |  | 0.436 / 0.424 / 0.427
2 | TAP | BERT |  | 0.439 / 0.445 / 0.432
3 | MVL | Word-Mask |  | 0.464 / 0.466 / 0.463
4 | MVL | Sent-Mask |  | 0.380 / 0.409 / 0.383
5 | MVL | BegEd |  | 0.384 / 0.422 / 0.401
6 | MVL | K-Sum |  | 0.384 / 0.422 / 0.401
7 | PL |  | Depression
---
(medium-risk)
|  0.535 / 0.480 / 0.498
8 | PL |  | Anxiety
---
(low-risk)
| 0.495 / 0.469 / 0.478
9 | PL |  | Depression
---
\+ Anxiety
| 0.473 / 0.456 / 0.463
10 | PL |  | Task C
---
(low-risk)
| 0.475 / 0.462 / 0.460
11 | - |  | Task C
---
(crowd-
labeled)
| 0.418 / 0.406 / 0.408
Table 2: Results Task A test set. For each of tasks 7-11, the size of added
data is 8% of training data. Metrics are all reported on macro-average.

##  3 Experiments and Results

We implement our BERT model based on huggingface Transformer Wolf et al.
(2020). Due to the limitation of GPU memory, we only use the base version.We
split $20\%$ of original training data to be the validation set and fix the
split for all models. The model selection is made by early stopping and we
train all models for $20$ epochs with the batch size $32$. For users with too
many posts and words, we only sample $100$ passages for them. Table 2 shows
our results on Macro-F1.

#### Task-Adaptive Pre-training

After applying task-adaptive pre-training on BERT, we see small performance
gains over BERT (i.e., from $0.427$ to $0.432$). That might be because even we
use the whole corpus provided by the shared task, it is still not large
enough.

#### Multi-view Learning

Word-Mask strategy improves over the BERT baseline. Compared with the adaptive
pre-training results on BERT, which also do word-level masking but only
trained on language modeling, we can see that MVL provides a more efficient
way to utilize a small training corpus and bring $3.1\%$ gain on Macro-F1.
However, all the other MVL approaches hurt the performance when compared to
the BERT baseline. This might be because the proposed sentence-level
perturbation strategy can seriously break the semantics of each post and thus
influence the overall performance, and random sampling over sentences hurts
most.

Setup | a | b | c | d |
---|---|---|---|---|---
Baseline | 0.730 | 0.077 | 0.333 | 0.566 |
| Depression
---
(medium-risk)
0.764 | 0.273 | 0.327 | 0.627 |
| Anxiety
---
(low-risk)
0.724 | 0.160 | 0.415 | 0.614 |
| Depression
---
\+ Anxiety
0.767 | 0.143 | 0.370 | 0.574 |
| Task C
---
(low-risk)
0.762 | 0.080 | 0.318 | 0.678 |
| Task C
---
(crowd-
labeled)
0.667 | 0 | 0.357 | 0.609 |
Table 3: Class-wise performance (F1) for PL-based methods (a=no-risk; b=low-
risk; c=medium-risk; d=high-risk).

#### Clinical Psychology Inspired Pseudo-labeling

Exp 7, 8 and 9 in Table 2 achieve the Top-3 Macro-F1 scores. This indicates
that although our psychology-inspired pseudo-labeling technique is simpler
than other weakly-supervised methods, adding meaningful pseudo-label data from
relevant domains helps mitigate the problem of insufficient data in the
intermediate classes (b and c). To verify this point, we show the class-wise
classification results for PL-based models in Table 3 where we can see
improvements on b and c classes. Due to space constraints, we present the
class-wise performance for all models in Appendix C.

The investigation over the confusion matrix of the best model (shown in
Section 4) further supports our hypothesis. However, when we try to combine
different pseudo-labeling data together (see Exp 9, where we add users from
r/depression and r/Anxiety following the proportion of $1:2$444See
Supplemental material B for detailed experiments over different mixing
proportions and still keep the added user number the same), we observe a
slight performance drop. The reason might be that users in these two PL
datasets might be at the boundary of the low-risk and medium-risk and simply
mixing them together will make the model confuse between these two classes
(see Supplemental material D for all confusion matrices).

Figure 1: Visualization of the confusion matrices for the baseline model (Exp
1) and the best model (Exp 7) .

Furthermore, we wanted to test the role of the _clinical psychology_ aspect of
our pseudo-labeling approach. Does the gain come from the meaningful domains
(anxiety and depression) or just by adding additional data? To answer this, we
use additional data provided by Task C of the shared task that contains posts
from random subreddits (e.g., sports). We do two experiments: 1) assign low-
risk to all such users and 2) assign the gold labels provided by the task via
crowdsourcing. We add the same size as for the other pseudo-label experiment
($8\%$ of training data). The results (Exp 10 & 11 in Table 2) show that the
clinical psychology inspired PL outperforms these models by meaningfully
addressing the intermediate classes insufficient data problem.

##  4 Error Analysis

In this section, we take a closer look at the prediction results of our best
model (clinical psychology inspired pseudo labeling using r/depression as
medium risk) by looking at the confusion matrix and sampled error cases. We
plot the confusion matrices for the baseline model (Exp 1 in Table 2) and the
best model (Exp 7 in Table 2) in Figure 1. We can see that, the best model
achieves the improvement mainly by fixing error cases wrongly predicted as no-
risk (where the true labels are “b”, “c” and “d”, with greater error reduction
for ”d”) and low-risk (where the true labels are “c” and “d”). As O’Connor and
Nock (2014) point out, depression is a serious mental issue and has become one
of the most important risk factors of suicide. Adding posts from r/depression
can help the model understand better what is “medium-risk” and “high-risk” and
thus raise the alert for the signals of similar or related mental issues.

We can also see that the main problem of our best model, is still the
confusion between “b” (low-risk) and “c” (medium-risk). In addition, the
problem of wrongly predicting the examples belonging to intermediate classes
to high-risk ones still exists. By manual investigation, we find that both
problems require expertise in mental health to make the subtle distinctions.
For example, the following text comes from a low-risk example555Based on
ethical consideration, we drop out many sensitive and private content of this
example. that is wrongly predicted as high-risk by our best model:

> “  sadness has taken me…i am sad , lonely , and i have no interest in living
> anymore…i didnt want to die…my mind is diseased , unable to take happiness…i
> have no interest in forming any more. …i dont think ill do it…”

It can be seen that there are many negative or even desperate expressions
(marked as red) in this examples, mixed with some short signals (marked as
blue) possibly indicating a person considered at low-risk. The model can be
fooled by the massive negative expressions and make the wrong predictions if
the model is not aware of the true intent of the person. Therefore, reliable
intent identification that could consider user posts across time and other
information would be a powerful tool to help the model prevent mistakes like
this.

##  5 Application: Predicting Suicide Risk of People Who Use Drugs

In order to further verify the effectiveness of our model in real-world
applications, we create a simulation scenario: we apply our best model (Exp 7)
over the data that is collected for $612$ users who post on both r/opiates and
r/SuicideWatch. r/opiates is a subreddit where people discuss topics around
opioid usage (e.g., drug doses, withdrawal anguish, daily experiences, harm
reduction). This community members could often be at a high suicide risk
Aladağ et al. (2018); Yao et al. (2020). We apply our model over their $1,176$
posts on r/SuicideWatch and find that our model predicts that $15.52\%$ of
them are no-risk, while $84.48\%$ of them are of low-risk, medium-risk and
high-risk. The results on sampled $2,863$ r/opiate posts are $30.56\%$ for no-
risk and $69.44\%$ for at least some risk. The predicted outputs are highly
aligned with reported results using crowdsourcing annotation of suicidal or
not-suicidal by Yao et al. (2020) and show the effectiveness of our model in
this simulated scenario.666The original Mturk annotation dataset is not open-
sourced and thus we can only do rough trend matching on our own collected
data. We hope this will open the door of using NLP methods to investigate the
link between suicidal ideation and fatal overdoses among people who use drugs.

##  6 Conclusions

We investigated a series of weakly-supervised methods and find that pseudo-
labeling on data related to risk factors for suicide (depression, anxiety) can
help improve model performance. This provides an alternative way to use
theoretically-grounded models (e.g., compared to feature engineering). We also
show a potential use case of this work for understanding suicidal ideation
among users who use drugs (e.g., opiates).

## Ethical Considerations

The dataset for suicide risk assessment was obtained from the organizers of
the 2019 Clinical Psychology Shared Task on Suicide Risk Assessment, by
filling in a participant application where we affirmed that we would follow
the shared task’s rules. We have obtained IRB approval (exempt) from Columbia
University to use the data as it consists of publicly available and anonymous
posts extracted from Reddit. For the application part, we also obtained
Columbia IRB approval (exempt) for the data publicly available and anonymous
data from r/opiates. All data is kept secure and online userIDs are not
associated to the posts.

Our intention of developing and improving suicide risk assessment models is to
help health professionals and/or social workers identify people that might be
at risk of committing suicide. We emphasize our intention that suicide risk
assessment models such as the ones developed here to be used responsibly, with
a human in the loop — for example a medical professional, a mental health
specialist, who can look at the predicted labels and offer explanations and
decide whether or not they seem sensible. We would urge any user of suicide
risk assessment technology to carefully control who may use the system.
Currently, the presented models may fail in two ways: they may either mislabel
an at-risk user as no-risk (our current models are particularly designed to
minimize this risk), or classify a no-risk user with some level of risk.
Obviously, there is some potential harm to a person who is truly in need if a
system based on this work fails to detect their suicidal ideation, and it is
possible that a person who is not truly in need may be irritated or offended
if someone reaches out to them because of a mistake. That is why, this system
needs only to be used as additional help for health professionals.

We note that because most of our data were collected from Reddit, a website
with a known overall demographic skew (towards young, white, American
men777https://social.techjunkie.com/demographics-reddit), our conclusions
about what expressions of different suicide risk levels look like and how to
detect them cannot necessarily be applied to broader groups of people. This
might be particularly acute for vulnerable populations such as people with
opioid use disorder (OUD). We hope that this research stimulates more work by
the research community to consider and model ways in which different groups
express suicidal ideation.

## References

  * Aladağ et al. (2018) Ahmet Emre Aladağ, Serra Muderrisoglu, Naz Berfu Akbas, Oguzhan Zahmacioglu, and Haluk O Bingol. 2018.  Detecting suicidal ideation on forums: proof-of-concept study.  _Journal of medical Internet research_ , 20(6):e215.
  * Clark et al. (2018) Kevin Clark, Minh-Thang Luong, Christopher D Manning, and Quoc Le. 2018.  Semi-supervised sequence modeling with cross-view training.  In _Proceedings of the 2018 Conference on Empirical Methods in Natural Language Processing_ , pages 1914–1925.
  * Coppersmith et al. (2018) Glen Coppersmith, Ryan Leary, Patrick Crutchley, and Alex Fine. 2018.  Natural language processing of social media as screening for suicide risk.  _Biomedical informatics insights_ , 10:1178222618792860.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  Bert: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL_.
  * Fazel and Runeson (2020) Seena Fazel and Bo Runeson. 2020.  Suicide. reply.  _New England journal of medicine_ , 382(21):e66–e66.
  * Gururangan et al. (2020) Suchin Gururangan, Ana Marasović, Swabha Swayamdipta, Kyle Lo, Iz Beltagy, Doug Downey, and Noah A Smith. 2020.  Don’t stop pretraining: Adapt language models to domains and tasks.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8342–8360.
  * Lee et al. (2020) Jinhyuk Lee, Wonjin Yoon, Sungdong Kim, Donghyeon Kim, Sunkyu Kim, Chan Ho So, and Jaewoo Kang. 2020.  Biobert: a pre-trained biomedical language representation model for biomedical text mining.  _Bioinformatics_ , 36(4):1234–1240.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Matero et al. (2019) Matthew Matero, Akash Idnani, Youngseo Son, Salvatore Giorgi, Huy Vu, Mohammad Zamani, Parth Limbachiya, Sharath Chandra Guntuku, and H Andrew Schwartz. 2019\.  Suicide risk assessment with multi-level dual-context language and bert.  In _Proceedings of the Sixth Workshop on Computational Linguistics and Clinical Psychology_ , pages 39–44.
  * McHugh et al. (2019) Catherine M McHugh, Amy Corderoy, Christopher James Ryan, Ian B Hickie, and Matthew Michael Large. 2019.  Association between suicidal ideation and suicide: meta-analyses of odds ratios, sensitivity, specificity and positive predictive value.  _BJPsych open_ , 5(2).
  * Miller (2019) Derek Miller. 2019.  Leveraging bert for extractive text summarization on lectures.  _arXiv preprint arXiv:1906.04165_.
  * Nock et al. (2019) Matthew K Nock, Franchesca Ramirez, and Osiris Rankin. 2019.  Advancing our understanding of the who, when, and why of suicide risk.  _JAMA psychiatry_ , 76(1):11–12.
  * O’Connor and Nock (2014) Rory C O’Connor and Matthew K Nock. 2014.  The psychology of suicidal behaviour.  _The Lancet Psychiatry_ , 1(1):73–85.
  * WHO et al. (2016) WHO et al. 2016.  Suicide across the world.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Xu et al. (2013) Chang Xu, Dacheng Tao, and Chao Xu. 2013.  A survey on multi-view learning.  _arXiv preprint arXiv:1304.5634_.
  * Yang et al. (2019) Zhilin Yang, Zihang Dai, Yiming Yang, Jaime Carbonell, Russ R Salakhutdinov, and Quoc V Le. 2019.  Xlnet: Generalized autoregressive pretraining for language understanding.  In _NeurIPS_ , pages 5754–5764.
  * Yao et al. (2020) Hannah Yao, Sina Rashidian, Xinyu Dong, Hongyi Duanmu, Richard N Rosenthal, and Fusheng Wang. 2020.  Detection of suicidality among opioid users on reddit: Machine learning–based approach.  _Journal of medical internet research_ , 22(11):e15293.
  * Zirikly et al. (2019) Ayah Zirikly, Philip Resnik, Ozlem Uzuner, and Kristy Hollingshead. 2019.  Clpsych 2019 shared task: Predicting the degree of suicide risk in reddit posts.  In _Proceedings of the sixth workshop on computational linguistics and clinical psychology_ , pages 24–33.

##  Appendix A Comparison of Different Pre-trained Language Models

Given that there has been significant progress on the architecture designs
after BERT, we have experimented with different PLMs, such as RoBERTa Liu et
al. (2019) and XLNet Yang et al. (2019). From Table 4, we can see that on the
Test set, the Macro-F1 scores for BERT and RoBERTa are almost the same and
XLNet performs worse than BERT. Therefore, we hypothesis that the architecture
of PLMs will not influence substantially the results on this task so we chose
BERT model.

PLM | TAP? | PL? | MVL? |  | Macro-F1
---|---|---|---|---|---
BERT | No | No | No |  | 0.427
XLNET | No | No | No |  | 0.422
RoBERTa | No | No | No |  | 0.408
Table 4: Experiment results for different PLMs. Here we only show the macro-F1
for the baseline model built on different PLMs.

##  Appendix B Results for Different Mixing Proportions

Table 5 shows the results for different mixing proportions of pseudo-labeling
data from r/Anxiety and r/depression. Due to the limitation of space, in the
main paper, we only show the results achieved by the best mixing proportions.

Mixing Proportion |  | Macro-F1
---|---|---
1: 5 |  | 0.398
1: 2 |  | 0.463
1: 1 |  | 0.434
2: 1 |  | 0.441
5: 1 |  | 0.442
Table 5: Experiment results for different mixing proportions. Here the
proportion represents the user ratio of
$\\#(\text{r/depression}):\\#(\text{r/Anxiety})$.

##  Appendix C Class-wise Decomposition of Experimental Results

Here we show the class-wise performance for all the models in Table 6.

No. | Approach | Setup | a | b | c | d |
---|---|---|---|---|---|---|---
1 | Baseline | BERT | 0.742/0.719/0.730 | 0.077/0.077/0.077 | 0.400/0.286/0.333 | 0.525/0.615/0.566 |
2 | TAP | BERT | 0.774/0.750/0.762 | 0.143/0.154/0.148 | 0.250/0.107/0.150 | 0.588/0.769/0.667 |
3 | MVL | Word-Mask | 0.788/0.812/0.800 | 0.111/0.077/0.091 | 0.391/0.321/0.353 | 0.567/0.654/0.607 |
4 | MVL | Sent-Mask | 0.551/0.844/0.667 | 0.091/0.077/0.083 | 0.294/0.179/0.222 | 0.583/0.538/0.560 |
5 | MVL | BegEd | 0.686/0.750/0.716 | 0/0/0 | 0.320/0.286/0.302 | 0.531/0.654/0.586 |
6 | MVL | K-Sum | 0.686/0.750/0.716 | 0/0/0 | 0.320/0.286/0.302 | 0.531/0.654/0.586 |
7 | PL |  | Depression
---
(c)
0.913/0.656/0.764 | 0.333/0.231/0.273 | 0.333/0.321/0.327 | 0.561/0.712/0.627 |
8 | PL |  | Anxiety
---
(b)
0.808/0.656/0.724 | 0.167/0.154/0.160 | 0.440/0.393/0.415 | 0.565/0.673/0.614 |
9 | PL |  | Depression
---
\+ Anxiety
0.821/0.719/0.767 | 0.133/0.154/0.143 | 0.385/0.357/0.370 | 0.554/0.596/0.574 |
10 | PL |  | Task C
---
(b)
0.774/0.750/0.762 | 0.083/0.077/0.080 | 0.438/0.250/0.318 | 0.606/0.769/0.678 |
11 | - |  | Task C
---
(crowd-
labeled)
0.760/0.594/0.667 | 0/0/0 | 0.357/0.357/0.357 | 0.556/0.673/0.609 |
Table 6: Class-wise decomposition results for models considered in this paper.
The results under each class are presented following the ”Precision/Recall/F1”
format.

##  Appendix D Additional Error Analysis

Additional confusion matrices for high-performance models (8, 9, 10 in Table
2) are in Figure 3.

Figure 2: Word-Mask Confusion Matrix.

Figure 3: Additional Confusion Matrices for Task 8, 9, 10, 3 in Table 2