# Shepherding Heterogeneous Flocks: Overview and Prospect

Anna Fujioka∗ Masaki Ogura∗∗ Naoki Wakamiya∗∗∗ Department of Bioinformatic
Engineering, Graduate School of Information Science and Technology, Osaka
University, Osaka, Japan email<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

The problem of guiding a flock of several autonomous agents using repulsion
force exerted by a smaller number of agents is called the shepherding problem
and has been attracting attention due to its potential engineering
applications. Although several works propose methodologies for achieving the
shepherding task in this context, most assume that sheep agents have the same
dynamics, which only sometimes holds in reality. The objective of this
discussion paper is to overview a recent research trend addressing the gap
mentioned above between the commonly placed uniformity assumption and the
reality. Specifically, we first introduce recent guidance methods for
heterogeneous flocks and then describe the prospects of the shepherding
problem for heterogeneous flocks.

###### keywords:

Multi-Agent System; Shepherding Problem; Navigation

††thanks: This work was supported by JSPS KAKENHI Grant Numbers JP21H01352,
JP21H01353, JP22H00514 and JST Moonshot R&D Grant Number JPMJMS2284.

##  1 Introduction

Flocking systems inspired by flocks of fish, birds, and other living animals
are attracting attentions due to their potential applications in various areas
of control engineering (Hemelrijk and Hildenbrandt, 2008; Ballerini et al.,
2008; Mikami et al., 2020) . Among these navigation, a navigation inspired by
shepherds’ behavior of guiding a flock of sheep is called shepherding (Long et
al., 2020). In shepherding, a small number of the shepherd agents guide a
flock of sheep agents using their repulsion force to the sheep agents. This
guidance has many potential applications including crowd control (Lien et al.,
2009) and oil spill cleanups (Masehian et al., 2015). The mathematical model
of such guidance is called the shepherding model and the problem of guiding a
flock of sheep agents is called the shepherding problem. The objective of this
problem is to design a movement law of the shepherd agent for guiding the
sheep agents.

Although there exist several movement laws (Tsunoda et al., 2019; Deng et al.,
2022) , most of these studies assume that all sheep agents have the same
dynamics. However, this assumption does not necessarily hold in several
practical scenarios (Hemelrijk and Hildenbrandt, 2008; Ballerini et al., 2008;
Jolles et al., 2020). In this context, we can find in the literature a recent
research trend in which the heterogeneity of the sheep agents is explicitly
considered for designing the shepherding algorithm.

Recently, Himo et al. (2022) proposed a guidance method for a flock of agents
containing those which do not receive repulsion force from the shepherd. In
this method, the shepherd guides the responsive sheep around an unresponsive
sheep, and then, guides all sheep to a goal area using the sheep’s behavior of
making a flock. Furthermore, we recently expanded this method and proposed the
guidance method for a flock containing variant sheep. In this method, the
shepherd determine the type of the sheep based on the estimated dynamics.
Then, the shepherd guide the sheep which are determined to be normal to the
goal area. The objective of this paper is to describe these previous research
works by the authors and, furthermore, provide future prospects on the problem
of shepherding heterogeneous flocks.

##  2 PREVIOUS RESEARCHES

In this section, we describe the previous research works for shepherding a
heterogeneous flock. First, in Subsection 2.1, we introduce a mathematical
model of the dynamics of sheep agents. We then in Subsection 2.2 introduce a
guidance method for shepherding a homogeneous flock, as this method forms a
basis of the ones for a heterogeneous flock. We then describe two existing
methodologies for shepherding heterogeneous flocks in Subsections 2.3 and 2.4.

###  2.1 Shepherding Model

First, we introduce the sheep agent model commonly used in the literature. The
model is based on the Boid model proposed by Reynolds (1987). Within the
model, the position $x_{i}(k)$ of the $i$th sheep agent at time $k$ is updated
by the difference equation

$x_{i}(k+1)=x_{i}(k)+v_{i}(k),$ (1)

where $v_{i}(k)$ denotes the movement vector of the $i$th sheep at time $k$.
In the Boid model, sheep agents are assumed to receive the following three
types of forces: “separation force” to prevent sheep from colliding with each
other, “alignment force” to match the velocity of other agents, and
“attraction force” to approach other agents. In addition to these forces, it
is assumed that the sheep avoid the shepherd agent. Therefore, the movement
vector of $i$th sheep at time $k$ is given by

$\begin{multlined}v_{i}(k)=K_{i1}v_{i1}(k)+{K_{i2}v_{i2}(k)}+{}\\\
K_{i3}v_{i3}(k)+K_{i4}v_{i4}(k),\end{multlined}v_{i}(k)=K_{i1}v_{i1}(k)+{K_{i2}v_{i2}(k)}+{}\\\
K_{i3}v_{i3}(k)+K_{i4}v_{i4}(k),$ (2)

where $K_{i1}$, $K_{i2}$, $K_{i3}$, and $K_{i4}$ are non-negative constants
depending on individual sheep agents, and the vectors $v_{i1}$, $v_{i2}$,
$v_{i3}$, and $v_{i4}$ correspond to the four forces described above.

We assume that the $i$th sheep receives forces from all sheep in the circle
with center $x_{i}(k)$ and radius $R>0$. If there are no other sheep in this
range, then we set $v_{i1}(k)=v_{i2}(k)=v_{i3}(k)=0$. If we let $S_{i}(k)$
denote the set of the indices of the sheep within radius $R$ of the $i$th
sheep at time $k$, then the vectors $v_{i1}(k)$, $v_{i2}(k)$, $v_{i3}(k)$, and
$v_{i4}(k)$ are given by

$\displaystyle v_{i1}(k)$ $\displaystyle=-\frac{1}{|S_{i}(k)|}\sum_{j\in
S_{i}(k)}\frac{x_{j}(k)-x_{i}(k)}{\lVert x_{j}(k)-x_{i}(k)\rVert^{3}},$ (3)
$\displaystyle v_{i2}(k)$ $\displaystyle=\frac{1}{|S_{i}(k)|}\sum_{j\in
S_{i}(k)}\frac{v_{j}(k-1)}{\lVert v_{j}(k-1)\rVert},$ (4) $\displaystyle
v_{i3}(k)$ $\displaystyle=\frac{1}{|S_{i}(k)|}\sum_{j\in
S_{i}(k)}\frac{x_{j}(k)-x_{i}(k)}{\lVert x_{j}(k)-x_{i}(k)\rVert}$ (5)
$\displaystyle v_{i4}(k)$ $\displaystyle=-\frac{x_{d}(k)-x_{i}(k)}{\lVert
x_{d}(k)-x_{i}(k)\rVert^{3}}.$ (6)

###  2.2 Farthest-Agent Targeting Method

The two methodologies for shepherding heterogeneous flocks are based on the
shepherding algorithm for homogeneous flocks called the Farthest-Agent
Targeting (FAT) method (Tsunoda et al., 2019). In the FAT method, the shepherd
guides the sheep farthest from a goal area. It is known that this simple
strategy allows us to effectively guide the sheep agents.

In order to describe the FAT method, we prepare some notations. Let the
position of the shepherd at time $k$ be denoted by $x_{d}(k)$. Then the update
rule of the position $x_{d}(k)$ within the FAT method is given by

$x_{d}(k+1)=x_{d}(k)+v_{d}(k),$ (7)

where $v_{d}(k)$ denotes the movement vector of the shepherd at time $k$. The
shepherd is assumed to receive the following three forces: an attractive force
$v_{d1}$ to the farthest sheep from the goal, a separation force $v_{d2}$ to
avoid colliding with nearest sheep to the shepherd, and a repulsion force
$v_{d3}$ to the goal area. Due to these three forces, the shepherd is able to
get behind the sheep flock and guide it to the goal. Specifically, the
movement vector $v_{d}(k)$ is given by

$v_{d}(k)=K_{d1}v_{d1}(k)+K_{d2}v_{d2}(k)+K_{d3}v_{d3}(k),$ (8)

where $K_{d1}$, $K_{d2}$, and $K_{d3}$ are non-negative constants, and the
vectors $v_{d1}(k)$, $v_{d2}(k)$, and $v_{d3}(k)$ are given by

$\displaystyle v_{1}(k)$
$\displaystyle=\frac{x_{t(k)}(k)-x_{\mathrm{d}}(k)}{||x_{t(k)}(k)-x_{\mathrm{d}}(k)||},$
(9) $\displaystyle v_{2}(k)$
$\displaystyle=-\frac{x_{n(k)}(k)-x_{\mathrm{d}}(k)}{||x_{n(k)}(k)-x_{\mathrm{d}}(k)||^{3}},$
(10) $\displaystyle v_{3}(k)$
$\displaystyle=-\frac{x_{\mathrm{g}}(k)-x_{\mathrm{d}}}{||x_{\mathrm{g}}(k)-x_{\mathrm{d}}||},$
(11)

where $t(k)$ denotes the index of the sheep farthest from the goal and $n(k)$
is the index of the sheep closest to the shepherd.

###  2.3 Shepherding Algorithm for Flock Containing Unre- sponsive Sheep

The first guidance method for heterogeneous flocks that we present is the one
proposed by Himo et al. (2022). Within their model, the sheep flock contains
the following two types of sheep agents: responsive ones and unresponsive
ones. While the responsive sheep agents are assumed to have positive gains
$K_{i1}$, …, $K_{i4}$, the unresponsive ones are supposed to have zero gain
for avoidance of the shepherd agent: i.e., $K_{i4}=0$.

Within the method by Himo et al. (2022), the shepherd is assumed to be given
the position of all sheep as well as the type of each sheep (i.e., responsive
or unresponsive). Based on these pieces of information, the shepherd is
required to guide all the sheep agents to a prescribed goal area. The guiding
behavior of the shepherd within the method can be divided into the following
two types: collecting and guiding. First, the shepherd tries to guide
responsive sheep around the unresponsive sheep. Notice that unresponsive sheep
are assumed to still have an attractive force to responsive sheep. Therefore,
guiding all the unresponsive sheep around the responsive sheep allows the
shepherd to indirectly guide the unresponsive sheep via guidance of responsive
sheep. Therefore, after making sure that all the unresponsive sheep are close
to responsive sheep, the shepherd can guide all sheep to the goal area. The
guidance of a responsive sheep to unresponsive sheep within the method is
performed by the FAT method described in Subsection 2.2. Specifically, the
shepherd guides a responsive sheep farthest from the unresponsive sheep to
which the shepherd navigate the responsive sheep.

It is shown in Himo et al. (2022) that the guidance methodology shows a high
guidance success rate. Specifically, they define the shepherding success rate
as the number of simulations of 100 different initial arrangements of sheep
that resulted in guiding the flock to the destination by a prescribed time
limit. They have observed that their method outperforms the FAT method
regardless of the number of unresponsive sheep for any of the scenarios of
$N=10$, $N=30$, and $N=50$, where $N$ denotes the total number of sheep.

###  2.4 Shepherding Algorithm for Flock Containing Variant Sheep

In this subsection, we describe the heterogeneous flock and guidance method
proposed by Fujioka et al. (2022). Let us first describe their model. Within
their model, they introduce a sheep agent called a variant sheep, which makes
the flock heterogeneous. Within their model, the variant sheep is assumed not
to receive more than one force among the separation, alignment, attraction,
and avoidance. For this reason, there are a total of $14$ different kinds of
variant sheep: those receiving only one force, two forces, and three forces,
respectively. They further assume that one and only one type of variant sheep
can exist. To model the variant sheep, they simply set the gain of the forces
that the variant sheep is not receiving to be zero, which is similar to the
model by Himo et al. (2022) described in Subsection 2.3.

In this method, the shepherd is assumed to be able to periodically obtain the
positions of all sheep. It is also assumed that a set of estimated
coefficients of the normal sheep (i.e., the sheep that are not variant) is
given to the shepherd. It should be remarked that the estimate is not
necessarily correct. Based on the estimate, the shepherd then predicts the
trajectories of the sheep. In periodic acquisition of sheep positions, the
shepherd measure the distance between the predicted trajectory and the actual,
measured position. If the distance is larger than a threshold value, the sheep
is determined to be variant by the shepherd. Then the shepherd guide only
sheep which are determined to be normal. We show the outline of the method in
Fig. 1.

Figure 1: The outline of the method proposed by Fujioka et al. (2022).
Illustration by Chihiro Kinoshita.

In Fujioka et al. (2022), the authors have compared the guidance performance
of their method and the FAT method. They have confirmed that, due to the
incorporated discrimination mechanism, their guidance method generally
performs better than the FAT method. Specifically, although the FAT method
tends to show smaller guidance success rates as the number of the variant
sheep in the flock increases, their method exhibited relatively high
performance (guidance success rates $>$ 60%) irrespective of the type of
variant sheep.

##  3 PROSPECTS

In this section, we describe the prospects of shepherding research for
heterogeneous flocks.

As we described in Section 2, some guidance methods have been proposed so far.
Himo et al. (2022) proposed the shepherding algorithm for a flock containing
unresponsive sheep. Our research group extended this work by defining $14$
types of variant sheep and proposed a method that can be applied to all types.
The development of such a method for guiding a heterogeneous flock will expand
the potential applications. However, there are still some problems with the
methods as described below.

###  3.1 Generalization of Sheep Model

First, let us consider the generalization of the sheep model. The first
possible extension of the sheep model is to further increase the variety of
variant types by changing the gains. For example, if the coefficient of
repulsion $K_{i4}$ is set to any value greater than $0$, the magnitude of the
response to the shepherd can be varied. If set to a negative number, it is
possible to define variant sheep that attract to the shepherd. This kind of
induction on variant sheep allows us to develop a method that is robust
against sheep that move unexpectedly.

Another option is to increase the number of variant types present at the same
time. In our method, the shepherd calculates the threshold value based on the
distance between the actual and predicted positions of all sheep, but this
threshold may not be set appropriately when multiple types of variant sheep
are present at the same time. Therefore, one of our future works is to develop
a guidance method for such a situation.

Also, we can consider a more significant change to the sheep model. In this
paper, we presented sheep model based on Boid model. However, we would like to
redefine a heterogeneous flock using a model other than the Boid model. For
example, Go et al. (2021) assumed that the sheep receives the following five
forces: “previous force” to attract to previous direction, “attraction force”
to the center of mass of the group, “repulsion force” to avoid other sheep,
“repulsion force” to avoid the shepherd, and “random error force”. This change
in the sheep model may change the method of efficient flock guidance. Another
future task is to develop a method that can correctly guide flocks for any
sheep model.

###  3.2 Expansion of the Shepherd Model

Next, let us discuss the shepherd model and the movement laws. It is unclear
whether our determine method is effective when there are several shepherds. If
the shepherds cannot communicate with each other, the trajectory predicted by
one shepherd may be inaccurate due to the influence of the other shepherds
(See Fig. 2).

(a) One shepherd

(b) Two shepherds

Figure 2: If there is one shepherd, the shepherd can estimate trajectories of
sheep properly. However, if there are more than one shepherd, it is difficult
to consider the impact of other shepherds on the sheep’s trajectory.

If shepherds can communicate with each other (e.g., if they can obtain the
positions of other shepherds), such inaccuracies in predicted trajectories are
unlikely to occur. However, when the FAT method is used, there is a high
probability that all shepherds will chase the same sheep. To prevent this, it
would be necessary to use a different movement law for multiple shepherds
(Lien et al., 2005). We would also like to evaluate the effectiveness of our
determine method when used in these methods.

###  3.3 Theoretical Analysis

In all of the methods described in Section 2, the effectiveness of the method
is measured by simulating the success rate of guidance using multiple initial
positions. The agent models are nonlinear and, therefore, it is difficult to
prove that the guidance is successful. However, we believe that the search for
a proof method will allow us to investigate the exact effectiveness of the
method.

Let us discuss how the proof can be done. The cause of the difficulty of the
proof is the non-linearity of the agent’s model. One idea is to simplify the
model. For example, in the FAT method described in Subsection 2.2, we can
assume that the shepherd always exists at a fixed distance from the farthest
sheep, or we can consider only minimal interactions by setting the number of
sheep to be equal to two. Such a proof would allow us to analyze Degree of
heterogeneity for successful guidance. For example, when the coefficient of a
variant sheep is $\alpha K_{i}$ using an arbitrary real number $\alpha$ for
the coefficient $K_{i}$ of a normal sheep, it will be possible to identify the
range of $\alpha$ with high guidance succeeds. Further consideration of these
results will enable us to develop a method with a higher guidance success
rate.

##  4 CONCLUSION

In this paper, we have described conventional researches and have presented
future perspectives on a heterogeneous flock and its guidance methods. The
definition of heterogeneous flocks and the development of movement laws of the
shepherd are still far from complete. However, we believe that further
research on heterogeneous flocks will lead to a better understanding of flock
control. Through further research, we hope to expand the applicability of
flock control.

## References

  * Ballerini et al. (2008) Ballerini, M., Cabibbo, N., Candelier, R., Cavagna, A., Cisbani, E., Giardina, I., Orlandi, A., Parisi, G., Procaccini, A., Viale, M., et al. (2008).  Empirical investigation of starling flocks: a benchmark study in collective animal behaviour.  _Animal behaviour_ , 76(1), 201–215.
  * Deng et al. (2022) Deng, Y., Ogura, M., Li, A., and Wakamiya, N. (2022).  Shepherding control for separating a single agent from a swarm.  In _1st IFAC Workshop on Control of Complex Systems_.
  * Fujioka et al. (2022) Fujioka, A., Ogura, M., and Wakamiya, N. (2022).  Shepherding algorithm for heterogeneous flock with model-based discrimination.  _Advanced Robotics_ , 1–16.
  * Go et al. (2021) Go, C.K., Koganti, N., and Ikeda, K. (2021).  Solving the shepherding problem: Imitation learning can acquire the switching algorithm.  In _2021 International Joint Conference on Neural Networks_ , 1–7.
  * Hemelrijk and Hildenbrandt (2008) Hemelrijk, C.K. and Hildenbrandt, H. (2008).  Self-organized shape and frontal density of fish schools.  _Ethology_ , 114(3), 245–254.
  * Himo et al. (2022) Himo, R., Ogura, M., and Wakamiya, N. (2022).  Iterative algorithm for shepherding unresponsive sheep.  _Mathematical Biosciences and Engineering_ , 19(4), 3509–3525.
  * Jolles et al. (2020) Jolles, J.W., King, A.J., and Killen, S.S. (2020).  The role of individual heterogeneity in collective animal behaviour.  _Trends in Ecology & Evolution_, 35(3), 278–291.
  * Lien et al. (2005) Lien, J.M., Rodriguez, S., Malric, J.P., and Amato, N.M. (2005).  Shepherding behaviors with multiple shepherds.  In _2005 IEEE International Conference on Robotics and Automation_ , 3402–3407.
  * Lien et al. (2009) Lien J.-M, and Pratt E. (2009).  Interactive Planning for Shepherd Motion.  In _AAAI Spring Symposium: Agents that Learn from Human Teachers_ , 95–102.
  * Long et al. (2020) Long, N.K., Sammut, K., Sgarioto, D., Garratt, M., and Abbass, H.A. (2020).  A comprehensive review of shepherding as a bio-inspired swarm-robotics guidance approach.  _IEEE Transactions on Emerging Topics in Computational Intelligence_ , 4(4), 523–537.
  * Masehian et al. (2015) Masehian E., and Royan M. (2015)  Cooperative Control of a Multi Robot Flocking System for Simultaneous Object Collection and Shepherding.  _Cham: Springer International Publishing_ , 97–114
  * Mikami et al. (2020) Mikami, T., Kano, T., and Ishiguro, A. (2020).  An agent-based model for community formation process of vampire bats that survive by sharing food.  _Artificial Life and Robotics_ , 25(4), 561–568.
  * Reynolds (1987) Reynolds, C.W. (1987).  Flocks, herds and schools: A distributed behavioral model.  In _14th Annual Conference on Computer Graphics and Interactive Techniques_ , 25–34.
  * Strombom et al. (2014) Strömbom D., Mann R.P., Wilson A.M., Hailes S., Morton A.J., Sumpter D.JT. and King A.J. (2014).  Solving the shepherding problem: heuristics for herding autonomous, interacting agents.  _Journal of the Royal Society Interface_ , 11, 20140719.
  * Tsunoda et al. (2019) Tsunoda, Y., Ishitani, M., Sueoka, Y., and Osuka, K. (2019).  Analysis of sheepdog-type navigation for a sheep model with dynamics.  In _Twenty-Fourth International Symposium on Artificial Life and Robotics_ , 499–503.