# Pincer-based vs. Same-direction Search Strategies After Smart Evaders by
Swarms of Agents

Roee M. Francos and Alfred M. Bruckstein Roee M. Francos and Alfred M.
Bruckstein are with the Faculty of Computer Science, Technion- Israel
Institute of Technology, Haifa, Israel, 32000,
<EMAIL_ADDRESS>alfred.bruckstein@cs.technion.ac.il).

###### Abstract

Suppose in a given planar region, there are smart mobile evaders and we want
to detect them using sweeping agents. We assume that the agents have line
sensors of equal length. We propose procedures for designing cooperative
sweeping processes that ensure successful completion of the task, thereby
deriving conditions on the sweeping velocity of the agents and their paths.
Successful completion of the task means that evaders with a known limit on
their velocity cannot escape the sweeping agents. A simpler task for the
sweeping swarm is the confinement of the evaders to their initial domain. The
feasibility of completing these tasks depends on geometric and dynamic
constraints that impose a lower bound on the velocity the sweeping agent must
have. This critical velocity is derived to ensure the satisfaction of the
confinement task. Increasing the velocity above the lower bound enables the
agents to complete the search task as well. We present a quantitative and
qualitative comparison analysis between the total search time of same-
direction sweep processes and pincer- movement search strategies. We evaluate
the different strategies by using two metrics, total search time and the
minimal critical velocity required for a successful search. We compare two
types of pincer-movement search processes, circular and spiral, with their
same-direction counterparts, for any even number of sweeping agents. We prove
that pincer based strategies provide superior results for all practical
scenarios and that the spiral pincer sweep process allows detection of all
evaders while sweeping at nearly theoretically optimal velocities.

###### Index Terms:

Multiple Mobile Robot Systems, Motion Planning, Aerial Robots, Search and
Rescue Robotics, Robot Surveillance and Security, Cooperating Robots, Swarms

##  I Introduction

The aim of this work is to provide an efficient ”must-win” search policy for a
swarm of $n$ sweeping agents that must guarantee detection of an unknown
number of smart evaders initially residing inside a given circular region of
radius $R_{0}$ while minimizing the search time. The evaders move and try to
escape the initial region at a maximal velocity of $V_{T}$, known to the
sweepers. All sweepers move at a velocity $V_{s}>V_{T}$ and detect the evaders
using linear sensors of length $2r$. Each ”must-win” policy requires a minimal
velocity that depends on the trajectory of the sweepers. Finding an efficient
algorithm requires that, throughout the sweep, the footprint of the sweepers’
sensors maximally overlaps the evader region (the region where evaders may
possibly be). This work develops two ”must-win” same-direction search
strategies, circular and spiral, for a swarm consisting of an even number of
searchers that sweep the evader region until all evaders are detected.
Afterwards, a comparison between the developed same-direction and pincer-based
search strategies developed in [1] is performed.

##  II Overview of Related Research

An interesting challenge for multi-agent systems is the design of searching or
sweeping algorithms for static or mobile targets in a region, which can either
be fully mapped in advance or unknown, see e.g. [2, 3, 4, 5]. Often the aim is
to continuously patrol a domain in order to detect intruders or to
systematically search for mobile targets known to be located within a given
area [6]. Search for static targets involves complete covering of the area
where they are located, but a much more interesting and realistic scenario is
the question of how to efficiently search for targets that are dynamic and
smart. A smart target is one that detects and responds to the motions of
searchers by performing optimal evasive maneuvers, to avoid interception.

Several such problems originated in the second world war due to the need to
design patrol strategies for aircraft aiming to detect ships or submarines in
the English channel, see [7]. The problem of patrolling a corridor using multi
agent sweeping systems in order to ensure the detection and interception of
smart targets was also investigated by Vincent et al. in [8] and provably
optimal strategies were provided by Altshuler et al. in [9]. A somewhat
related, discrete version of the problem, was also investigated by Wagner et
al. and later by Altshuler et al. in [10], [11] and [12]. It focuses on a
dynamic variant of the cooperative cleaners problem, a problem that requires
several simple agents to a clean a connected region on the grid with
contaminated pixels. This contamination is assumed to spread to neighbors at a
given rate.

In [6], Tang et al. propose a non-escape search procedure for evaders. Evaders
are originally located in a convex region of the plane and may move out of it.
Tang et al. propose a cooperative progressing spiral-in algorithm performed by
several agents with disk shaped sensors in a leader-follower formation. The
authors establish a sufficient condition for the number of searching agents
required to guarantee that no evader can escape the region undetected. This
lower bound is based on the sensor radius, searcher and evader velocities and
the initial perimeter of the region. In [13], McGee et al. also investigate a
search problem for smart targets that do not have any maneuverability
restrictions except for an upper limit on their velocity. The sensor that the
agents are equipped with detects targets within a disk shaped area around the
searcher location. Search patterns consisting of spiral and linear sections
are considered. In [14], Hew proposes searching for smart evaders using
concentric arc trajectories with agents sensors similar to [13]. Such a search
is aimed at detecting submarines in a channel or in a half plane. The paper
focuses on determining the size of a region that can be successfully patrolled
by a single searcher, where the searcher and evader velocities are known. The
search problem is formulated as an optimization problem. The search progress
per arc or linear iteration is maximized while guaranteeing that the evader
cannot slip past the searcher undetected.

Another set of related problems are pursuit-evasion games, where the pursuers’
objective is to detect evaders and the evaders objective is to avoid the
pursuers. In this context several works considered the problem of defending a
region from the entrance of intruders under the name of perimeter defense
games by Shishika et al. in [15, 16, 17], with a focus on utilizing
cooperation between pursuers to improve the defense strategy.

##  III Same-direction Sweeps

This paper considers a scenario in which a multi-agent swarm of identical
agents search for mobile targets or evaders that are to be detected. The
information the agents perceive only comes from their own sensors, and all
evaders that intersect a sweeper’s field of view are detected. We assume that
all agents have a linear sensor of length $2r$. The evaders are initially
located in a disk shaped region of radius $R_{0}$. There can be many evaders,
and we consider the domain to be continuous, meaning that evaders can be
located at any point in the interior of the circular region at the beginning
of the search process. The sweeping protocols proposed are predetermined and
deterministic, hence the sweepers can perform them using a minimal amount of
memory and computations. All sweepers move with a speed of $V_{s}$ (measured
at the center of the linear sensor). By assumption the evaders move at a
maximal speed of $V_{T}$, without any maneuverability restrictions. The
sweeper swarm’s objective is to ”clean” or to detect all evaders that can move
freely in all directions from their initial locations in the circular region
of radius $R_{0}$.

Search time clearly depends on the type of sweeping movement the swarm
employs. Detection of evaders is based on deterministic and preprogrammed
search protocols. We consider two types of search patterns, circular and
spiral patterns. The desired result is that after each sweep around the
region, the radius of the circle that bounds the evader region (for the
circular sweep), or the actual radius of the evader region (for the spiral
sweep), decreases by a value that is strictly positive. This guarantees
complete cleaning of the evader region, by shrinking in finite time the
possible area in which evaders can reside to zero. At the beginning of the
circular search process we assume that only half the length of the agents’
sensors is inside the evader region, i.e. a footprint of length $r$, while the
other half is outside the region in order to catch evaders that may move
outside the region while the search progresses. At the beginning of the spiral
search process we assume that the entire length of the agents’ sensors is
inside the evader region, i.e. a footprint of length $2r$.

In the single agent search problem described in [18], we observed that there
can be escape from point $P=(0,R_{0})$ (shown in Fig. $1\hskip 2.84526pt(a)$),
when basing the searcher’s velocity only on a single traversal around the
evader region. Therefore we had to increase the agent’s critical velocity to
deal with this possible escape. If we were to distribute a multi-agent swarm
say, equally along the boundary of the initial evader region, we would have
the same problem of possible escape from the points adjacent to the starting
locations of the sweepers.

Figure 1: (a) - Initial placement of $2$ agents employing the same-direction
circular sweep process. (b) - Initial placement of $2$ agents employing the
same-direction spiral sweep process. The sweepers sensors are shown in green.
The angle $\phi$ is the angle between the tip of a sweeper’s sensor and the
normal of the evader region. $\phi$ is an angle that depends on the ratio
between the sweeper and evader velocities.

##  IV Pincer-based Search

Since we wish the sweepers to have the lowest possible critical velocity, in
[1] we propose a different idea than same-direction sweeps for the search
process. The idea is to have pairs of sweeping agents move out in opposite
directions along the boundary of the evader region and sweep in a pincer
movement rather than having a convoy of sweepers all moving in the same-
direction along the boundary.

Our method is readily applicable for any even number of sweepers. The sweepers
are initially positioned in pairs back to back. One sweeper in the pair moves
counter clockwise while the other sweeper in the pair moves clockwise. In case
the search is planar, once the sweepers meet, i.e. their sensors are again
superimposed at a meeting point, they switch the directions in which they
move. For example, if the search if carried out by two sweepers, after the
first sweep this switching point is located at $(0,-R_{0})$. This changing of
directions occurs every time a sweeper bumps into another. Each sweeper is
responsible for an angular sector of the evader region that is proportional to
the number of participating agents in the search. The search process can be
viewed as a $2$ dimensional search in which the actual agents travel on a
plane or as a $3$ dimensional search where the sweepers are drone like agents
which fly over the evader area. In case the search is $3$ dimensional, where
sweepers fly at different heights above the evader region, every time a
sweeper is directly above another, they exchange the angular section they are
responsible to sweep between them, and continue the search. The analysis of
the two cases is exactly the same.

Sweepers that employ a pincer movement solve the problem of evader region’s
spread from the ”most dangerous points”, points located at the tips of their
sensors closest to the evader region’s center. These points have the maximum
time to spread during sweeper movement and therefore if evaders that try to
escape from these points are detected, evaders trying to escape from other
points are detected as well. When a sweeper returns to a location, the evader
region has a smaller or equal radius than it had $2$ cycles previously. If all
sweepers were to rotate in the same-direction after being deployed equally
around the circle, the evader region’s points that need to be considered for
limiting the region’s spread are points that are adjacent to the center of the
sensor (for a circular sweep) and points that are adjacent to the sensors’
tips that are furthest from the center of the evader region (for a spiral
sweep). This consideration would lead to higher critical velocities for
sweepers that employ same-direction sweeps. Higher critical velocities also
imply that, for a given sweeper velocity above the critical velocity, that is
sufficient for both same-direction and pincer based sweep processes, sweep
time is reduced when sweepers perform pincer movement sweep. In [18], the
analysis of a single agent circular sweep process indicates that the critical
velocity for agents employing same-direction sweeps is indeed higher compared
to the pincer based critical velocities developed in [1]. In this paper it is
proven that for swarms with multiple sweepers same-direction critical
velocities are indeed higher than their pincer-based counterparts.

Figure 2: (a) - Initial placement of $2$ agents employing the circular pincer
sweep process. (b) - Initial placement of $2$ agents employing the spiral
pincer sweep process. The sweepers sensors are shown in green. The angle
$\phi$ is the angle between the tip of a sweeper’s sensor and the normal of
the evader region. $\phi$ is an angle that depends on the ratio between the
sweeper and evader velocities.

We analyze the proposed sweep processes’ performance in terms of the total
time to complete the search, defined as the time at which all potential
evaders that resided in the initial evader region were detected. Expressions
for the complete cleaning times of the evader region as a function of the
search parameters, $R_{0}$, $r$, $V_{T}$ and the number of agents, $n$, in the
swarm are derived, evaluated and discussed for each developed sweep process.

Illustrative simulations that demonstrate the evolution of the search
processes were generated using NetLogo software [19] and are presented in Fig.
$3$. and Fig. $4$. Green areas are locations that are free from evaders and
red areas indicate locations where potential evaders may still be located.
Fig. $3$. shows the cleaning progress of the evader region when $6$ agents
employ the circular pincer sweep process. Fig. $4$. shows the cleaning
progress of the evader region when $4$ agents employ the spiral pincer sweep
process.

Figure 3: Swept areas and evader region status for different times in a
scenario where $6$ agents employ the circular pincer sweep process. (a) -
Beginning of first cycle. (b) - Midway of the first cycle. (c) - toward the
completion of the first cycle. (d) - Beginning of the second cycle. (e) -
toward the end of the third cycle. (f) - Beginning of the one before last
cycle. Green areas are locations that are free from evaders and red areas
indicate locations where potential evaders may still be located.  Figure 4:
Swept areas and evader region status for different times in a scenario where
$4$ agents employ the spiral pincer sweep process. (a) - Beginning of first
cycle. (b) - toward the midway of the first cycle. (c) - toward the completion
of the first cycle. (d) - Beginning of the second cycle. (e) - toward the end
of the second cycle. (f) - toward the midway of the third cycle. Green areas
are locations that are free from evaders and red areas indicate locations
where potential evaders may still be located.

Note that in the considered problems, we consider the exact locations of
evaders and even their numbers is a priori unknown. The only information the
sweepers have about the evaders locations is that the evaders are located
somewhere inside a given circular region at the beginning of the search
process, and that the evaders may try to move and slip undetected out of this
region as the search progresses, to avoid interception. Since the sweepers do
not have any additional knowledge about the evaders whereabouts, or even if
all evaders were found at some intermediate point of time during the search,
the search is continued until the whole region is searched, thus reducing the
uncertainty region where potential evaders might be located to have an area of
$0$.

The contributions of the paper are as follows. A complete theoretical analysis
of trajectories, critical velocities and search times for a swarm of $n$
cooperative agents whose mission is to guarantee detection of all smart
evaders that are initially located in given circular region from which they
may move out of in order to escape the pursuing sweeping agents. The
theoretical analysis is provided by designing search algorithms for any even
number of sweeping agents the employ same-direction circular and spiral search
processes and qualitatively and quantitatively comparing between them to their
pincer-based counterparts. The theoretical analysis is complemented by
simulation experiments that verify the theoretical results and illustrate them
graphically.

For both circular and spiral sweep processes, it is quantitatively proven that
sweeping with pairs of sweepers that employ pincer movements between
themselves and between adjacent sweeper pairs yields a lower critical velocity
than the case where sweepers are distributed evenly around the region and
sweep in the same-direction. Additionally, the derived expressions for the
complete sweep time of the evader region, show that the spiral pincer sweep
process allows sweepers to successfully detect all evaders in the region while
sweeping with velocities that are nearly theoretically optimal and also
enables the sweepers to detect all evaders in the region at a significantly
shorter amount of time compared to its same-direction spiral counterpart and
to the circular pincer sweep process.

##  V A Universal Bound On Cleaning Rate

In this section we present an optimal bound on the cleaning rate of a searcher
with a linear shaped sensor. This bound is independent of the particular
search pattern employed. For each of the proposed search methods we then
compare the resulting cleaning rate to the optimal derived bound in order to
compare between different search methods. We denote the searcher’s velocity as
$V_{s}$, the sensor length as $2r$, the evader region’s initial radius as
$R_{0}$ and the maximal velocity of an evading agent as $V_{T}$. The maximal
cleaning rate occurs when the footprint of the sensor over the evader region
is maximal. For a line shaped sensor of length $2r$ this happens when the
entire length of the sensor fully overlaps the evader region and it moves
perpendicular to its orientation. The rate of sweeping when this happens has
to be higher than the minimal expansion rate of the evader region (given its
total area) otherwise no sweeping process can ensure detection of all evaders.
We analyze the search process when the sweeper swarm is comprised of $n$
identical agents. The smallest searcher velocity satisfying this requirement
is defined as the critical velocity and denoted by $V_{LB}$, we have:

######  Theorem 1.

No sweeping process is able to successfully complete the confinement task if
its velocity, $V_{s}$, is less than,

${{\rm{V}}_{LB}}=\frac{{\pi{R_{0}}{V_{T}}}}{nr}$ (1)

For proof see [1]. Hopefully, after the first sweep the evader region is
within a circle with a smaller radius than the initial evader region’s radius.
Since the sweepers travel along the perimeter of the evader region and this
perimeter decreases after the first sweep, ensuring a sufficient sweeper
velocity that guarantees that no evader escapes during the initial sweep
guarantees also that the sweeper velocity is sufficient to prevent escape in
subsequent sweeps as well.

##  VI Pincer Sweep Process

###  VI-A Multiple Agents with Linear Sensors: the Circular Pincer Sweep
Process

We analyze the case that the multi-agent swarm consists of $n$ agents, where
$n$ is an even number, and each sweeper has a sensor length of $2r$. At the
beginning of the search process the footprint of each sweeper’s sensor that is
over the evader region is equal to $r$. When employing this type of search
pattern the symmetry between the two agent trajectories prevents the escape
from point $P=(0,R_{0})$ that is the most dangerous point an evader can escape
from as proved in [18]. Therefore each sweeper’s critical velocity is based
only upon the time it takes it to traverse the angular section it responsible
for, namely $\frac{2\pi}{n}$. For example, if the sweeper swarm consists of
only two sweepers, each sweeper is required to scan an angle of $\pi$. If the
sweepers’ velocities are above the critical velocity of the scenario the
agents can advance inward toward the center of the evader region after
completing a cycle. The notion of a cycle or an iteration corresponds to an
agent’s traversal of the angular section it is required to scan, i.e. an angle
of $\frac{2\pi}{n}$. Therefore, its definition varies with the number of
sweepers. Once the agents finish scanning the angular section they are
responsible for, and if their velocities allow it, they advance inward
together. In case the search is performed in the $2D$ plane, the sweepers
change their scanning direction only after the completion of an inward
advancement maneuver. In case the search is $3$ dimensional, i.e. the sweepers
fly over the evader region, the sweepers first advance inward together, and
only then exchange between them the angular section they are responsible to
sweep. Afterwards the sweepers continue to scan a section with a smaller
radius. Contrary to the works in [15, 16, 17] that devise methods for
intercepting as many intruders as possible with agents that can intercept only
a single invader, the circular pincer sweep process guarantees evaders are
detected regardless of their number and the number of pursuing sweepers. Since
each sweeper has a sensor length of $r$ outside the evader region, in order to
guarantee that no evader escapes the sweepers, we must demand that the spread
of the evader region, from any potential location where an evader might be
located, is confined to a radius of no more than $r$ from its origin point at
the beginning of the cycle. During an angular traversal of $\frac{2\pi}{n}$
around the evader region radius of $R_{0}$, this yields the circular pincer
sweep process’s critical velocity,

${V_{c}}=\frac{{2\pi{R_{0}}{V_{T}}}}{{nr}}$ (2)

Therefore, we obtain that the circular critical velocity equals twice the
optimal minimal critical velocity,

${V_{c}}=2V_{LB}$ (3)

######  Theorem 2.

For an $n$ agent swarm for which $n$ is even, that performs the circular sweep
process, where the sweeper distribution is as described, the number of
iterations it takes the swarm to reduce the evader region to be bounded by a
circle with a radius that is less than or equal to $r$ is given by,

${N_{n}}=\left\lceil{\frac{{\ln\left({\frac{{2\pi
r{V_{T}}-nr{V_{s}}}}{{2\pi{R_{0}}{V_{T}}-nr{V_{s}}}}}\right)}}{{\ln\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)}}}\right\rceil$
(4)

After ${N_{n}}$ sweeps the sweeper swarm performs an additional circular sweep
and cleans the entire evader region.
We denote by ${T_{in}}$ the sum of all inward advancement times and by
${T_{circular}}$ the sum of all the circular traversal times. Therefore, the
time it takes the swarm to clean the entire evader region is given by,

$T(n)={T_{in}}(n)+{T_{circular}}(n)$ (5)

Where ${T_{in}}(n)$ is given by,

$\begin{array}[]{l}{T_{in}}(n)=\frac{{{R_{0}}}}{{{V_{s}}}}+\left({\frac{{2\pi{R_{0}}{V_{T}}-nr{V_{s}}}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}}\right){\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}-1}}\end{array}$
(6)

And ${T_{circular}}(n)$ is given by,

$\begin{array}[]{l}{T_{circular}}(n)=-\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{T}}{V_{s}}}}+\frac{{nr\left({{V_{s}}+{V_{T}}}\right)+2\pi
r{V_{T}}}}{{2\pi{V_{T}}^{2}}}\\\
+{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({\frac{{\left({{V_{s}}+{V_{T}}}\right)\left({2\pi{R_{0}}{V_{T}}-rn{V_{s}}}\right)}}{{2\pi{V_{s}}{V_{T}}^{2}}}}\right)\\\
+\frac{{r\left({{N_{n}}-1}\right)}}{{{V_{T}}}}+\frac{{2\pi
r}}{{n{V_{s}}}}\end{array}$ (7)

For proof see [1].

###  VI-B Multiple Agents with Linear Sensors: the Spiral Pincer Sweep Process

Since at the start of every circular sweep process half of the sweepers’
sensors are outside of the evader region, we would like the sweepers to employ
a more efficient motion throughout the cleaning process. This means that
throughout the motion of the searcher the footprint of its sensor that is
above the evader region should maximally overlap the evader region. This can
be achieved with a spiral scan, where the agent’s sensor tracks the expanding
evader region wavefront, while preserving its shape to be as close as possible
to a circle.

We analyze the case that the multi-agent swarm consists of $n$ agents, where
$n$ is an even number, and each sweeper has a line sensor length of $2r$.
choosing all sweepers to have sensors of equal lengths implies that when the
sweepers’ sensors reach the same point and are tangent to each other, escape
will not be possible from the gap between the sensors. This is a necessary
requirement since the process that is described below relies on the symmetry
between the agents sensors that are over the evader region.

At the beginning of the search process the footprint of each sweeper’s sensor
that is over the evader region is equal to $2r$. When employing this type of
search pattern the symmetry between the two agent trajectories prevents the
escape from point $P=(0,R_{0})$ that is the most dangerous point an evader can
escape from. Therefore, each sweeper’s critical velocity can be based only
upon the time it takes it to traverse the angular section it responsible for,
namely $\frac{2\pi}{n}$. Similarly to the circular sweep process, when
sweepers move at a velocity greater than their critical velocity and if the
search is carried out on the $2$D plane, sweepers change their direction of
scanning after performing an inward advancement. If the search is $3$
dimensional, the sweepers advance inward together, exchanging afterwards
between them the angular section they are responsible to sweep. After this
motion the sweepers start scanning a section with a smaller radius.

Each searcher begins its spiral traversal with the tip of its sensor tangent
to the edge of the evader region. In order to keep its sensor tangent to the
evader region throughout the sweep, the searcher must travel at angle $\phi$
to the normal of the evader region. $\phi$ is an angle that depends on the
ratio between the sweeper and evader velocities. The incentive of a sweeper to
travel in a constant angle $\phi$ to the normal of the evader region is to
preserve the evader region’s circular shape and keep the entire length of its
sensor inside the evader region at all times. Fig $2$ (b) shows an initial
placement of $2$ agents that employ the pincer movement spiral sweep process.
$\phi$ is calculated by,

$\sin\phi=\frac{{{V_{T}}}}{{{V_{s}}}}$ (8)

Thus we have,

$\phi=\arcsin\left({\frac{{{V_{T}}}}{{{V_{s}}}}}\right)$ (9)

The isoperimeteric inequality states that for a given area, the shape of the
curve that bounds the area which has the smallest perimeter is circular. Since
the agent travels along the perimeter of the evader region while keeping the
evader region’s shape close to circular, the isoperimeteric inequality implies
that the time it takes to complete a sweep around the region is minimal. The
agent’s angular velocity or rate of change of its angle with respect to the
center of the evader region, $\theta_{s}$, can be described as a function of
$\phi$ as,

$\frac{{d{\theta_{s}}}}{{dt}}=\frac{{{V_{s}}\cos\phi}}{{{R_{s}}(t)}}=\frac{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}{{{R_{s}}(t)}}$
(10)

And the instantaneous growth rate of the searcher radius will be given by,

$\frac{{d{R_{s}}(t)}}{{dt}}={V_{s}}\sin\phi={V_{T}}$ (11)

Integrating equation (10) between the initial and final sweep times of the
angular section yields that,

$\theta\left({{t_{\theta}}}\right)=\frac{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}{{{V_{T}}}}\ln\left({\frac{{{V_{T}}{t_{\theta}}+{R_{0}}-r}}{{{R_{0}}-r}}}\right)$
(12)

Applying the exponent function to both sides of the equation results in,

$\left({{R_{0}}-r}\right){e^{\frac{{{V_{T}}{\theta({t_{\theta}})}}}{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}={V_{T}}{t_{\theta}}+{R_{0}}-r={R_{s}}({t_{\theta}})$
(13)

Each sweeper begins its spiral traversal with the tip of its sensor tangent to
the edge of the evader region. The time it takes a sweeper to complete a
spiral traversal around the angular region of the evader region it is
responsible to scan corresponds to changing its angle $\theta$ by
$\frac{2\pi}{n}$. During this time the expansion of the evader region has to
be by no more than $2r$ from its initial radius, in order for the sweeper to
prevent the escape of potential evaders. This assertion holds under the
assumption that after each cycle when the sweeper advances inward toward the
center of the evader region it completes this motion in zero time. Otherwise,
the spread of evaders has be less than $2r$ and sweepers that travel toward
the center of the evader region after completing the spiral sweep have to meet
the evader wavefront travelling outward the region with a speed of $V_{T}$ at
the previous radius $R_{0}$. This yields a critical velocity for the spiral
sweep process that is slightly above the optimal lower bound $V_{LB}$. The
derived critical velocity ensures that no evaders escape while the sweepers
advance toward the center of the evader region. These considerations are
formulated in Corollary $1$ in [1].

######  Corollary 1.

In the spiral pincer sweep process for the $n$ agent case, where $n$ is even,
the critical velocity ,${V_{s}}$, that allows the satisfaction of the
confinement task, is obtained as the solution of,

${V_{T}}{T_{c}}=\frac{{2r{V_{s}}}}{{V_{s}}+{V_{T}}}$ (14)

Where ${T_{c}}$ is given by

${T_{c}}=\frac{{\left({{R_{0}}-r}\right)\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$
(15)

As shown in Fig. $5$. the computed spiral critical velocity is close to the
optimal lower bound, especially for a small number of sweepers. For example,
for the $2$ sweeper case the ratio between the spiral critical velocity and
the optimal velocity is $1.05$.

Figure 5: Critical velocities as a function of the number of sweepers. The
number of sweeper agents is even, and ranges from $2$ to $32$ agents, that
employ the multi-agent spiral sweep process where the inward advancements
toward the center of the evader are taken into account. We also plot the
optimal critical velocities and the circular critical velocities for
comparison. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$R_{0}=100$.

######  Theorem 3.

For an $n$ agent swarm for which $n$ is even, that performs the spiral sweep
process, where the sweepers distribution is as described, the number of
iterations it takes the swarm to clean the entire evader region is given by,

$\begin{array}[]{l}\widetilde{{N_{n}}}={N_{n}}+\eta+1=\\\
\left\lceil{\frac{{\ln\left({\frac{{r\left({3-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}{{{R_{0}}\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)+r\left({1+{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}}\right)}}{{\ln\left({\frac{{{V_{T}}+{V_{s}}{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}}{{{V_{s}}+{V_{T}}}}}\right)}}}\right\rceil+\eta+1\end{array}$
(16)

Where $\eta=0$, or $\eta=1$
We denote by ${T_{in}}(n)$ the sum of all the inward advancement times and by
${T_{spiral}}(n)$ the sum of all the spiral traversal times. Therefore, the
time it takes the swarm to clean the entire evader region is given by,

$T(n)={T_{in}}(n)+{T_{spiral}}(n)$ (17)

Where ${T_{in}}(n)$ is given by,

${T_{in}}(n)=\widetilde{T}_{in}(n)+{T_{{}_{in}last}}(n)+\eta{T_{i{n_{f}}}}(n)$
(18)

Where $\widetilde{T}_{in}(n)$ is given by,

$\begin{array}[]{l}\widetilde{T}_{in}(n)=\frac{{2r}}{{{V_{s}}+{V_{T}}}}+\frac{{{R_{0}}-r}}{{{V_{s}}}}+\frac{{2r\left({{V_{T}}+{V_{s}}{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}{{{V_{s}}\left({{V_{s}}+{V_{T}}}\right)\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}\\\
-\frac{{{{\left({{V_{T}}+{V_{s}}{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}^{{N_{n}}-1}}}}{{{V_{s}}\left({{V_{s}}+{V_{T}}}\right)\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}\\\
\left({{R_{0}}\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)+r\left({1+{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}\right)\end{array}$
(19)

${T_{{}_{in}last}}(n)$ is given by ${T_{{}_{in}last}}(n)=\frac{R_{N}}{V_{s}}$
and ${T_{i{n_{f}}}}(n)$ is given by
${T_{i{n_{f}}}}(n)=\frac{{{T_{l}}{V_{T}}}}{{{V_{s}}}}$. Therefore,

${T_{in}}(n)=\widetilde{T}_{in}(n)+\frac{{{R_{N}}}}{{{V_{s}}}}+\frac{{\eta
r}}{{{V_{s}}}}\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)$
(20)

${T_{spiral}}(n)$ is given by,

${T_{spiral}}(n)=\widetilde{T}_{spiral}(n)+{T_{last}}(n)+\eta{T_{l}}(n)$ (21)

Where $\widetilde{T}_{spiral}(n)$ is given by,

$\begin{array}[]{l}\widetilde{T}_{spiral}(n)=\frac{{\left({r-{R_{0}}}\right)\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{T}}{V_{s}}}}-\frac{{2r\left({{V_{T}}+{V_{s}}{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}{{{V_{T}}{V_{s}}\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}\\\
+\frac{{2r\left({{N_{n}}-1}\right)}}{{{V_{T}}}}-{\left({\frac{{{V_{T}}+{V_{s}}{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}}{{{V_{s}}+{V_{T}}}}}\right)^{{N_{n}}}}\\\
\left({\frac{{\left({{V_{s}}+{V_{T}}}\right)\left({{R_{0}}\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)-r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}+1}\right)}\right)}}{{{V_{T}}{V_{s}}\left({1-{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}}\right)\end{array}$
(22)

${T_{last}}(n)$ is given by ${T_{last}}(n)=\frac{{2\pi r}}{{n{V_{s}}}}$ and
${T_{l}}(n)$ is given by
${T_{l}}(n)=\frac{{r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$.
Hence, ${T_{spiral}}(n)$ is given by,

${T_{spiral}}(n)=\widetilde{T}_{spiral}(n)+\frac{{2\pi
r}}{{{n{V_{s}}}}}+\eta\frac{{r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$
(23)

For a derivation of the sweep times for the spiral pincer sweep process see
[1].

##  VII same-direction Circular Sweep

Previously, we tried to find the tightest lower bound of a searcher’s velocity
by constructing a function of $2$ variables $f(t,V_{s})$, by demanding that
the furthest possible spread of the evader region is cleaned by the furthest
tip of the sweeper’s line sensor. A lesser requirement is to demand that by
the time the most problematic point in the evader region, point $P$, spreads
to a possible circle of radius of $r$ around point $P$, the sweeping swarm
completes in addition to a sweep of $\frac{2\pi}{n}$ around the evader region
an additional angular traversal that is proportional to traversing an arc of
length $r$. This means that the agent travels an angle of
$\frac{2\pi}{n}+\beta_{0}$ where $\beta_{0}$ is marked in Fig. $6$.

Figure 6: Geometric representation of the critical velocity calculation that
results in a simpler critical velocity expression. The simplified expression
for the critical velocity bounds the previously found critical velocity from
above for all choices of geometric parameters. Red areas indicate locations
where potential evaders may be located. The orange circles denote the spread
of potential evaders to a circle of radius $r$ around the most problematic
points $P_{1}$ and $P_{2}$ and its during a traversal of $2\pi+\beta_{0}$
around the evader region, where $\beta_{0}=\arcsin\frac{r}{{R_{0}}}$.

We denote the time it takes the most problematic points to spread a distance
of $r$ as $T_{e}$. These points are adjacent to the starting locations of the
sweepers, and $2$ such points $P_{1}$ and $P_{2}$, exist in case the search is
performed with $2$ sweepers, as shown in Fig. $6$. We have that
$T_{e}=\frac{r}{{{V_{T}}}}$. We can see from Fig. $6$. that
$\sin\beta_{0}=\frac{r}{{R_{0}}}$, therefore
$\beta_{0}=\arcsin\frac{r}{{R_{0}}}$. The time it takes the sweeper to travel
an angle of $\frac{2\pi}{n}+\beta_{0}$ is therefore given by
${T_{s}}=\frac{{\left({\frac{2\pi}{n}+\arcsin\left(\frac{r}{{R_{0}}}\right)}\right){R_{0}}}}{{{V_{s}}}}$.
In order to guarantee no escape, we demand that $T_{s}\leq T_{e}$. Therefore,
rearranging terms in the previous equation and plugging $T_{e}$ instead of
$T_{s}$ we get that,

${V_{c}}\geq\frac{{\left({\frac{2\pi}{n}+\arcsin\left(\frac{r}{{R_{0}}}\right)}\right){R_{0}}{V_{T}}}}{r}$
(24)

The lower bound on a sweeper velocity that ensures confinement is obtained
when we have equality in (24), i.e.
${V_{{c_{LB}}}}=\frac{{\left({\frac{2\pi}{n}+\arcsin\left(\frac{r}{{R_{0}}}\right)}\right){R_{0}}{V_{T}}}}{r}$.
In future derivations we use the first order Taylor approximation for the
arcsine function in (24), in order to enable the construction of analytical
results for the sweep times of the evader region. Such an approximation is
valid since in all practical scenarios the ratio between $\frac{r}{R_{0}}$ is
sufficiently small. Applying this approximation to (24) allows us to define
${V_{c}}$, the chosen critical velocity, given by,

${V_{{c_{LB}}}}=\frac{{2\pi{R_{0}}{V_{T}}}}{{rn}}+{V_{T}}$ (25)

In order for the sweeper swarm to advance inward toward the center of the
evader region it must travel in a velocity that is greater than the critical
velocity. We denote by $\Delta V>0$ the increment in the sweeping agents’
velocity that is above the critical velocity. Each agent’s velocity ${V_{s}}$
is therefore given by the sum of the critical velocity and $\Delta V$, namely
${V_{s}}={V_{c}}+\Delta V$. The total sweep times it takes the sweeper swarm
to reduce the evader region to a region bounded by a circle with a radius that
is smaller or equal to $r$ is given by the sum of the circular motions and
inward advancements that are performed after the completion of each circular
sweep. The time it takes the sweepers to perform the circular sweeps is given
by,

$\begin{array}[]{l}{T_{circular}}=-\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}+\frac{{r\left({{V_{s}}-{V_{T}}}\right)\left({n\left({{V_{s}}+{V_{T}}}\right)+2\pi{V_{T}}{N_{n}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({{V_{s}}+{V_{T}}}\right)\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}}\right)\\\
+\frac{{2\pi r}}{{n{V_{s}}}}\end{array}$ (26)

The time it takes the sweepers to perform the inward advancement is given by,

$\begin{array}[]{l}{T_{in}}=\frac{{{R_{0}}}}{{{V_{s}}}}+{\left({1+\frac{{2\pi{V_{T}}}}{{{V_{s}}+{V_{T}}}}}\right)^{N-1}}\left({\frac{{2\pi{R_{0}}{V_{T}}-r\left({{V_{s}}-{V_{T}}}\right)}}{{{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}}\right)\end{array}$
(27)

The full analytical development is provided in Appendix $A$.

###  VII-A same-direction Circular Sweep End-Game

In order to entirely clean the evader region the sweepers need to change the
scanning method when the evader region is bounded by a circle of radius $r$.
This is due to the fact that a smart evader that is very close to the center
of the evader region can travel at a very high angular velocity compared to
the angular velocity of the pursuing agents. This constraint is described by
the following two equations,
${\omega_{s}}=\frac{{{V_{s}}}}{r},{\omega_{T}}=\frac{{{V_{T}}}}{\varepsilon}$.
The first describes the searcher’s angular velocity and the second the
evader’s angular velocity. Since $\varepsilon$ can be arbitrarily small the
evader can move just behind a sweeper’s sensor and never be detected. Thus a
slight modification to the sweep process needs to be applied in order to clean
the entire evader region with the sweeper swarm that employs a circular scan.
After completing sweep number $N_{n}-1$ the sweepers move toward the center of
the evader region until the tip of the sweeper’s sensors closest to the center
of the evader region are placed at the center of the evader region. Following
this motion the sweepers perform a circular sweep of radius $r$ around the
center of the evader region. The time this last circular sweep takes is given
by ${T_{last}}=\frac{{2\pi r}}{{{nV_{s}}}}$. Therefore, after the last
circular scan the evader region is bounded by a circle of radius ${R_{last}}$,
given by,

${R_{last}}={T_{last}}{V_{T}}=\frac{{2\pi rV_{T}}}{{{nV_{s}}}}$ (28)

In order to overcome the challenges in the circular search that were described
we propose that after scan number $N_{n}+1$ the sweeper swarm will travel to
the right until cleaning the wavefront that propagates from the right portion
of the remaining evader region and then travel to the left until cleaning the
remaining evader region. A depiction of the scenario at the beginning of the
end-game is presented in Fig. $7$.

Figure 7: Depiction of the end-game steps for the same-direction circular
sweep performed by $2$ sweepers. The sweepers sensors’ are shown in green and
red areas indicate locations where potential evaders may still be located. In
order to overcome the challenges in the circular search that were described,
we propose that after scan number $N+1$ the sweepers will travel to the right
until cleaning the wavefront that propagates from the right portion of the
remaining evader region and then travel to the left until cleaning the
remaining evader region. (a) - Evader region status and sweepers’ locations
prior to the last inward advancement. (b) - Evader region status and sweepers’
locations prior to the linear sweep.

Theorem $4$ states the conditions for this demand to hold.

######  Theorem 4.

When defining $\alpha=\frac{{R_{0}}}{r}$, if $\Delta V$ satisfies that,

$\Delta V\geq\frac{{-4\pi{V_{T}}\alpha+\pi{V_{T}}+{V_{T}}\sqrt{{\pi^{2}}+8\pi
n}}}{{2n}}$ (29)

then the evader region will be completely cleaned by $n$ sweepers that employ
the linear scan after $N_{n}+1$ iterations.

###### Proof.

During the previously mentioned movement the margin between the tip of the
sensor in each direction to the evader region boundaries must satisfy,

$\frac{{2r-{R_{last}}}}{{{V_{T}}}}>{T_{linear}}$ (30)

in order to guarantee no escape. ${T_{linear}}$ denotes the time it takes the
sweepers to clean the right section of the remaining evader region in addition
to the time it takes them to scan from the rightmost point they got to until
the leftmost point of the expansion. These times are respectively denoted as
$t$ and $\tilde{t}$. Therefore, ${T_{linear}}$ is given by
${T_{linear}}=\tilde{t}+t$. The evader region’s rightmost point of expansion
starts from the point $(R_{last},0)$ and spreads at a velocity of $V_{T}$.
Therefore, if the constraint in (30) is satisfied we can view the rightward
and leftward linear sweeps as a one dimensional scan. This geometric
constraint can be observed in Fig. $7$. Therefore, the time $t$ it takes the
sweepers to clean the spread of potential evaders from the right section of
the region can be calculated from, ${V_{s}}t={R_{last}}+{V_{T}}t$. Therefore,
$t$ is given by, $t=\frac{{{R_{last}}}}{{{V_{s}}-{V_{T}}}}$. $\tilde{t}$ is
computed by calculating the time it takes the sweepers located at point
$(tV_{s},0)$ to change their scanning direction and perform a leftward scan to
a point that spread at a velocity of $V_{T}$ from the leftmost point in the
evader region at the origin of the search, the point $(-R_{last},0)$, for a
time given by ${\tilde{t}+t}$. We have that,
$-{R_{last}}-{V_{T}}\left({\tilde{t}+t}\right)=t{V_{s}}-{V_{s}}\tilde{t}$.
Plugging in the value of $t$ yields
$\tilde{t}=\frac{{2{V_{s}}{R_{last}}}}{{{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}$.
$T_{linear}$ is therefore given by,

${T_{linear}}=t+\tilde{t}=\frac{{6\pi r{V_{T}}{V_{s}}-2\pi
r{V_{T}}^{2}}}{{n{V_{s}}{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}$ (31)

Fig. $8$ shows a plot of ${T_{linear}}$ as a function of $n$. Therefore, the
total scan time until a complete cleaning of the evader region is given by
$T_{total}={T_{circular}}+{T_{in}}+{T_{linear}}$. For the one dimensional scan
to be valid and ensure a non escape search and complete cleaning of the evader
region (30) must be satisfied. This demand implies that,

$\frac{{2r-{R_{last}}}}{{{V_{T}}}}>\frac{{{R_{last}}\left({3{V_{s}}-{V_{T}}}\right)}}{{{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}$
(32)

By rearranging terms, (32) can be written as,

$2r{\left({{V_{s}}-{V_{T}}}\right)^{2}}>{R_{last}}{V_{s}}\left({{V_{s}}+{V_{T}}}\right)$
(33)

By substitution of $R_{0}$ with $\alpha r$ where $\alpha>1$ and by
substituting the terms for $V_{s}$ and ${R_{last}}$, (33) resolves to a
quadratic equation in $\Delta V$ that has only one positive root. This root is
a monotonically decreasing function in $\alpha$, given by

$\Delta V\geq\frac{{-4\pi{V_{T}}\alpha+\pi{V_{T}}+{V_{T}}\sqrt{{\pi^{2}}+8\pi
n}}}{{2n}}$ (34)

Therefore, for a given $\alpha$, the designer of the sweep process can infer
which $\Delta V$ needs to be chosen in order to completely clean the evader
region using the final linear sweeping motion. ∎

For a complete derivation see Appendix $B$.

######  Theorem 5.

For a valid circular search process the total search time until a complete
cleaning of the evader region is given by,
$T={T_{circular}}+{T_{in}}+{T_{linear}}$, or as,

$\begin{array}[]{l}T=-\frac{{{R_{0}}}}{{{V_{T}}}}+\frac{{r\left({{V_{s}}-{V_{T}}}\right)\left({n\left({{V_{s}}+{V_{T}}}\right)+2\pi{V_{T}}{N_{n}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}-1}}\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{{V_{s}}}}}\right)\\\
\left({\frac{1}{{n\left({{V_{s}}+{V_{T}}}\right)}}+\frac{{{V_{s}}}}{{2\pi{V_{T}}^{2}}}+\frac{1}{{2\pi{V_{T}}}}+\frac{1}{{n{V_{T}}}}}\right)+\frac{{2\pi
r}}{{n{V_{s}}}}\\\ +\frac{{6\pi r{V_{T}}{V_{s}}-2\pi
r{V_{T}}^{2}}}{{n{V_{s}}{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}\end{array}$
(35)

Figure 8: End-game search times until complete cleaning of the evader region
for the same-direction circular sweep processes. We simulated sweep processes
with an even number of agents, ranging from $2$ to $32$ agents, that employ
the multi-agent same-direction circular sweep processes. We show results
obtained for different values of velocities above the circular critical
velocity. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$R_{0}=100$. Figure 9: Total search times until complete cleaning of the
evader region for the same-direction circular sweep processes. We simulated
sweep processes with an even number of agents, ranging from $2$ to $32$
agents, that employ the multi-agent same-direction circular sweep processes.
We show results obtained for different values of velocities above the circular
critical velocity. The chosen values of the parameters are $r=10$, $V_{T}=1$
and $R_{0}=100$.

##  VIII Same-direction Spiral Sweep

Since our aim is to provide a sweep process that improves the same-direction
circular sweep process we would like the sweepers to employ a more efficient
motion throughout the sweep process. Therefore, we wish that throughout the
motion of the sweepers, their sensors’ footprint will maximally overlap the
evader region. This can be obtained by a spiral scan, where the sweepers’
sensors track the expanding evader region’s wavefront, while preserving its
shape to be as close as possible to a circle. An illustration of the initial
placement of $2$ sweepers that employ the same-direction spiral sweep process
is presented in Fig. $10$. The sweepers start with a sensor length of $2r$
inside the evader region. If the sweeper agents’ velocities are above the
scenario’s critical velocity, the sweepers reduce the evader region’s area
after completing a traversal around the region. Each sweeper begins its spiral
traversal with the tip of its sensor that is furthest from the center of the
evader region, in a position that is tangent to the boundary of the evader
region. In order to keep their sensors tangent to the evader region, the
sweepers must travel at angle $\phi$ to the normal of the evader region.
$\phi$ is calculated in equation (9) in section $VI$. This method of traveling
at angle $\phi$ preserves the evader region’s circular shape.

$\theta\left({{t_{\theta}}}\right)$ describes the angle a sweeper travelled
around the region and is calculated in section $VI$, equation (12).
${t_{\theta}}$ denotes the sweep time after a sweeper completes a traversal of
angle $\theta$ around the center of the evader region. The time it takes a
sweeper to travel an angle of $\theta$ around the center of the evader region,
${t_{\theta}}$ is obtained from (12).

Figure 10: At each cycle each sweeper travels more than an angle of
$\frac{2\pi}{n}$ around the evader region in order to detect all escaping
smart evaders. The additional angle, denoted by $\beta$ needs to be traversed
in order to detect all evaders that may have spread from the most dangerous
point at the beginning of the sweep. The angle $\beta$ depends on the radius
of the circle that bounds the evader region and therefore changes as the
search task progresses and the evader region is shrunk. $\beta_{0}$ is the
additional angle that must be traversed during the initial sweep around the
region. Orange areas show a circular spread to a radius of
$V_{T}t_{\frac{2\pi}{n}}$ around their origin points. Spread from these origin
points determines the same-direction spiral process’s critical velocity. Red
areas indicate additional locations where potential evaders may still be
located.

Contrary to the pincer-based strategy where each sweeper travels only an angle
of $\frac{2\pi}{n}$ at each sweep iteration, in same-direction sweeps, each
sweeper travels a larger angle than $\frac{2\pi}{n}$ at each iteration around
the evader region in order to detect all escaping smart evaders. The
additional angle, denoted by $\beta$, needs to be traversed in order to detect
all evaders that may have spread from the ”most dangerous points” at the
beginning of each sweep. Such points are adjacent to the starting locations of
every sweeper. The angle $\beta$ depends on the radius of the circle that
bounds the evader region. After a sweeper traverses the additional angle
$\beta$, the evader region’s boundary is due to spread from points that
resided at the lower tips of the sensors. When the tips of the sensors leave
these points, evaders may spread from them in all directions at a velocity of
$V_{T}$.

There exists a geometric relation between $\beta$, which is measured with
respect to the center of the evader region, and $\varphi$. $\varphi$ is an
angle that measures the angle between the center of the sweeper after it
completes a sweep of $\frac{2\pi}{n}$ with respect to the center of the spread
from the most dangerous points at each iteration. $\varphi$ is measured only
for the additional sweeping after the sweeper completes a sweep of
$\frac{2\pi}{n}$ and is shown in Fig. $10$.

The most dangerous points for a swarm consisting of $2$ sweepers are shown in
Fig. $10$ as points $p_{1}$ and $p_{2}$. Points $q_{1}$ and $q_{2}$ are the
points at the inner tips of the sweepers’ sensors that are the most dangerous
points for the subsequent sweep. After each traversal of
$\frac{2\pi}{n}+\varphi$ new ”most dangerous points” have to be accounted for.
The number of ”most dangerous points” equals to the number of sweepers that
perform the search protocol. The time it takes the sweeper to travel an angle
of $\frac{2\pi}{n}$ is given by,

${t_{\frac{2\pi}{n}}}=\frac{{\left({{R_{0}}-r}\right)\left({{e^{\frac{{{2\pi}{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$
(36)

After the sweepers complete a traversal of $\frac{2\pi}{n}$ around the evader
region they change their sweeping pattern and move in an inward spiral that
tracks the residual wavefront that expanded from points $p_{1}$ and $p_{2}$
move toward the center of the evader region. During this motion their lower
tips point to the center of the region. The sweepers move in an inward spiral
until the tips of their sensors that are furthest away from the center of the
evader region are inside the expanding evader region. This occurs at the
intersection point between the inward spiral trajectory and the expanding
wavefront from each of the ”most dangerous points”. Following this movement,
after-which the entire sweepers’ sensors are over the evader region, they
sweep again with an outward spiral with a smaller radius of the evader region.
They continue this outward and inward spiral motion until the evader region is
bounded by a circle with a radius that is less than or equal to $2r$.

We have that the coordinates of the outer tip of the sweeper that starts to
sweep in the counter-clockwise direction from point $p_{2}=(0,-R_{0})$ after
it completes a traversal of $\frac{2\pi}{n}$ as a function of $\varphi$ are
given by,

$x=-{V_{T}}{t_{\varphi}}\sin\varphi_{i}\hskip 2.84526pt,\hskip
2.84526pty=\left({{R_{i}}+{V_{T}}{t_{\frac{{2\pi}}{n}}}-{V_{T}}{t_{\varphi}}}\right)\cos\varphi_{i}$
(37)

During the time that the sweeper executes the outward spiral for time
${t_{\frac{{2\pi}}{n}}}$ and the inward spiral for time $t_{\varphi}$ the
evader region spreads from the ”most dangerous point” $q_{1}=(0,R_{0}-2r)$ at
a velocity of $V_{T}$ in all directions. The equation of the points $(x,y)$ on
the wavefront that originates from $q_{1}$ are given by,

${x^{2}}+{\left({y-{R_{0}}+2r}\right)^{2}}={V_{T}}^{2}{\left({{t_{\frac{{2\pi}}{n}}}+{t_{\varphi}}}\right)^{2}}$
(38)

The sweeper will travel in an inward spiral until the upper tip of its sensor
satisfies (38). $\beta_{0}$ is given by,

$\tan{\beta_{0}}=\frac{x}{y}$ (39)

The subscript $0$ in ${\beta_{0}}$ denotes the iteration or cycle number,
indicating that the value of $\beta$ changes as the sweep process progresses.
The same reasoning and notations hold for $\varphi$. Substituting the
expressions for $x$ and $y$ from (37) in (39) yields,

$\tan{\beta_{0}}=\frac{{-{V_{T}}{t_{\varphi}}\sin\varphi}}{{\left({{R_{0}}+{V_{T}}{t_{\frac{{2\pi}}{n}}}-{V_{T}}{t_{\varphi}}}\right)\cos\varphi}}$
(40)

Therefore,

${\beta_{i}}==\arctan\left({-\frac{{{V_{T}}{t_{{\varphi_{i}}}}\tan{\varphi_{i}}}}{{{R_{0}}+{V_{T}}\left({{t_{\frac{{2\pi}}{n}}}-{t_{{\varphi_{i}}}}}\right)}}}\right)$
(41)

When the sweeper completes a traversal of $\frac{2r}{n}$, its center is
located at a distance of ${{R_{0}}-r+{V_{T}}{t_{\frac{{2\pi}}{n}}}}$ from the
center of the evader region. It then starts sweeping in an inwards spiral for
a time given by,

${t_{\varphi}}=\frac{{\left({{R_{0}}-r+{V_{T}}{t_{\frac{{2\pi}}{n}}}}\right)\left({1-{e^{-\frac{{\varphi{V_{T}}}}{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)}}{{{V_{T}}}}$
(42)

The angle $\varphi$ is calculated from the equation,

$\int_{0}^{{t_{\varphi}}}{\dot{\varphi}\left(\zeta\right)}d\zeta=\int_{0}^{{t_{\varphi}}}{\frac{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}{{{R_{0}}-r+{V_{T}}{t_{\frac{{2\pi}}{n}}}-{V_{T}}\zeta}}d}\zeta$
(43)

Hence $\varphi$ is given by,

${\varphi_{0}}\left({{t_{\varphi}}}\right)=-\frac{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}{{{V_{T}}}}\ln\left({\frac{{{R_{0}}-r+{V_{T}}{t_{\frac{{2\pi}}{n}}}-{V_{T}}{t_{\varphi}}}}{{{R_{0}}-r+{V_{T}}{t_{\frac{{2\pi}}{n}}}}}}\right)$
(44)

In order to solve for the critical velocity that satisfies the confinement
task for the same-direction spiral sweep process, we need to determine both
$\varphi_{0}$ and the critical velocity. The critical velocity and
$\varphi_{0}$ are calculated from the demand that the expansion of the evader
region after the first sweep at time
${t_{\frac{2\pi}{n}}}+{{t_{\varphi}}_{0}}$, has to satisfy that,

${V_{T}}\left({{t_{\frac{{2\pi}}{n}}}+{t_{{\varphi_{0}}}}}\right)\leq 2r$ (45)

Substitution of terms yields,

${t_{\frac{{2\pi}}{n}}}+{t_{{\varphi_{i}}}}=\frac{{\left({{R_{0}}-r}\right)\left({2{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-{e^{\frac{{{V_{T}}\left({2\pi-n{\varphi_{i}}}\right)}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$
(46)

In order to solve for the critical velocity of the same direction spiral sweep
process, denoted by ${V_{c_{spiral_{same}}}}$ and $\varphi_{0}$ we write (44)
as,

$\begin{array}[]{l}H({V_{s}},{\varphi_{i}})=\left({{R_{0}}-r}\right)\left({2{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-{e^{\frac{{{V_{T}}\left({2\pi-n{\varphi_{i}}}\right)}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)\\\
-2r\end{array}$ (47)

The critical velocity and $\varphi_{0}$ can be computed numerically using the
Newton method. Since $\varphi_{0}\leq\beta_{0}$ we choose the initial estimate
for $\varphi_{0}$ to be,

${\varphi_{{0_{0}}}}=\arcsin\left({\frac{{2r}}{{{R_{0}}-2r}}}\right)$ (48)

We choose the initial estimate for the critical velocity as the lower bound on
the sweeper velocity given by,

${V_{{s_{0}}}}=\frac{{\pi{R_{0}}{V_{T}}}}{r}=V_{LB}$ (49)

From (45) we find ${V_{c_{spiral_{same}}}}$ and $\varphi_{0}$ using the Newton
iterative method for the velocity whose equation is given by,

${V_{{s_{n+1}}}}={V_{{s_{n}}}}-\frac{{H\left({{V_{{s_{n}}}},{\varphi_{i}}}\right)}}{{\frac{{\partial
H\left({{V_{{s_{n}}}},{\varphi_{i}}}\right)}}{{\partial{V_{{s_{n}}}}}}}}$ (50)

Using,

$\begin{array}[]{l}\frac{{\partial
H({V_{s}},{\varphi_{i}})}}{{\partial{V_{s}}}}=\frac{{\left({{R_{0}}-r}\right){V_{T}}{V_{s}}}}{{n{{\left({{V_{s}}^{2}-{V_{T}}^{2}}\right)}^{1.5}}}}\\\
\left({-4\pi{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}+\left({2\pi-n{\varphi_{i}}}\right){e^{\frac{{{V_{T}}\left({2\pi-n{\varphi_{i}}}\right)}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}\right)\end{array}$
(51)

And by using the Newton iterative method for $\varphi_{0}$ whose equation is
given by,

${\varphi_{{i_{n+1}}}}={\varphi_{{i_{n}}}}-\frac{{H\left({{V_{s}},{\varphi_{{i_{n}}}}}\right)}}{{\frac{{\partial
H\left({{V_{s}},{\varphi_{{i_{n}}}}}\right)}}{{\partial{\varphi_{{i_{n}}}}}}}}$
(52)

Using,

$\frac{{\partial
H({V_{s}},{\varphi_{i}})}}{{\partial{\varphi_{i}}}}=\frac{{{V_{T}}\left({{R_{0}}-r}\right){e^{\frac{{{V_{T}}\left({2\pi-n{\varphi_{i}}}\right)}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}}}{{\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}$
(53)

With an initial estimate for $\varphi_{0}$ given in (48), an iterative
convergence to a solution for $V_{s}$ satisfying (45) with equality, is
achieved by substituting the solution for $V_{s}$ in equation (50), solving
for an updated $\varphi_{0}$ using (52), and repeating this process until
converging to a solution with a desired tolerance. This alternating root
finding approach yields solution for $\varphi_{0}$ and
${V_{c_{spiral_{same}}}}$. After the sweepers traverse an angle of
$\frac{2\pi}{n}+\beta_{0}$ around the evader region the evader region’s
boundary is due to evaders that originated from points $q_{1}$ and $q_{2}$ (in
case the sweep process is performed with $2$ sweepers), and not from points
$p_{1}$ and $p_{2}$ as can be seen in Fig. $10$.

Let us denote by $\Delta V>0$ the addition to the sweeper’s velocity above the
critical velocity. The velocity is therefore given by,
$V_{s}={V_{c_{spiral_{same}}}}+\Delta V$. If a sweeper moves with a velocity
greater than the critical velocity, after the completion of the inwards spiral
sweep the evader region is bounded in a circle with a radius that is less than
$R_{0}$. After the sweepers complete an inwards spiral sweep the new radius of
the evader region is given by,

${R_{i+1}}={R_{i}}-{V_{T}}\left({{t_{\frac{{2\pi}}{n}}}+{t_{{\varphi_{0}}}}}\right)$
(54)

Therefore after a set of outward and inward spirals as described, the sweepers
sweep around an evader region that is bounded by a circle with a smaller
radius. After each sweep $\varphi_{i}$ is calculated using the Newton method
with respect to the new radius of the circle that bounds the evader region,
allowing for the calculation of $t_{{\varphi}_{i}}$. This search methodology
continues until the evader region is bounded by a circle with a radius that is
less than or equal to $2r$.

##  IX same-direction Spiral Sweep end-game

###  IX-A The end-game

In order to entirely clean the evader region, the sweepers need to change the
scanning method when the evader region is bounded by a circle of radius $2r$,
due to the same consideration that are described in the end-game of the same-
direction circular sweep process. The depiction of the scenario at the
beginning of the end-game is shown in Fig. $11(a)$.

Figure 11:  Different stages of the end-game. The sweepers’ sensors are shown
in green and the evader region is shown in red. (a) - Depiction of the state
at the beginning of the end-game. (b) - Depiction of the scenario after the
sweepers move toward the center of the evader region and place the tips of
their sensors at the center of the region. (c) - Depiction of the scenario
after the last spiral sweep. (d) - Depiction of the scenario prior to the
linear sweep.

In the last inward advancement, the sweepers place the tips of their sensors
at the center of the evader region. The time it takes the sweepers to complete
this movement is given by,

${T_{e}}=\frac{{{R_{N}}}}{{{V_{s}}}}$ (55)

Following the last inward advancement, the sweepers perform the last spiral
sweep when the tips of their sensors are placed at the center of the evader
region as can be seen in Fig. $11(b)$. In order to apply a linear sweeping
movement the last spiral sweep has to reduce the evader region to be bounded
by a circle of radius less than $2r$. Following the last inward advancement,
the sweepers performs an additional spiral sweep when the center of each
sweeper’s sensor is as at a distance of $r$ from the center of the evader
region. The time it takes to complete this sweep is denoted by $T_{l}$ and is
given by,

${T_{l}}=\frac{{r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)}}{{{V_{T}}}}$
(56)

The depiction after the sweepers complete this last spiral movement can be
seen in Fig. $11(c)$. During the last spiral sweep, the evader region spreads
from its center point to a circle with a radius of,

${R_{last}}={T_{l}}{V_{T}}=r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)$
(57)

In order for a linear scan to be applicable ${R_{last}}$ has to be smaller
than $2r$. This leads to a requirement on the sweeper’s velocity,

$r\left({{e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}-1}\right)<2r$
(58)

Which resolves to,

${e^{\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}<2$ (59)

Yielding the requirement on the velocity,

${V_{s}}>{V_{T}}\sqrt{\frac{{4{\pi^{2}}}}{{{{\left({n\ln 2}\right)}^{2}}}}+1}$
(60)

Since we previously observed that the spiral critical velocity (for the
considered spiral process) is close to the lower bound on the critical
velocity, $V_{LB}$, we can check whether the condition in (58) is
automatically satisfied. If the requirement on $V_{s}$ in (60) is less than
$V_{LB}$, then since the sweepers move with a velocity above it, then (58) is
always satisfied. Therefore if,

${V_{T}}\sqrt{\frac{{4{\pi^{2}}}}{{{{\left({n\ln
2}\right)}^{2}}}}+1}<\frac{{\pi{R_{0}}{V_{T}}}}{nr}=V_{LB}$ (61)

Or if the ratio $\frac{{{R_{0}}}}{r}$ satisfies that,

$\sqrt{\frac{4}{{{{\left({n\ln
2}\right)}^{2}}}}+\frac{1}{{{\pi^{2}}}}}<\frac{{{R_{0}}}}{r}$ (62)

Then ${R_{last}}$ is smaller than $2r$. Following this last spiral sweep, two
sweepers place the tips of their sensors at the center of the evader region,
advancing a distance of,

${R_{in}}=2r-{R_{last}}$ (63)

The time it takes the sweepers to complete this motion is given by,

${T_{f}}=\frac{2r-{R_{last}}}{{{V_{s}}}}$ (64)

During this time the evaders spread to a circle of radius $R_{f}$ around the
center of the region given by,

${R_{f}}={T_{f}}{V_{T}}+{R_{last}}$ (65)

The depiction of the scenario at this time instance is shown in Fig. $11(d)$.
Following this movement, the sweepers perform a linear motion and complete the
search process. During the previously mentioned movement the margin between
the edge of the sensors in each direction to the evader region boundaries must
satisfy,

$\frac{{2r-{R_{f}}}}{{{V_{T}}}}>{T_{linear}}$ (66)

In order to guarantee no evader escapes undetected. ${T_{linear}}$ denotes the
time it takes the sweepers to clean the right section of the remaining evader
region in addition to the time it takes it to scan from the rightmost point it
got to until the leftmost point of the expansion. These times are respectively
denoted as $t$ and $\tilde{t}$. Therefore, ${T_{linear}}$ is given by
${T_{linear}}=\tilde{t}+t$. The evader region’s rightmost point of expansion
starts from the point $(R_{f},0)$ and spreads at a velocity of $V_{T}$.
Therefore, if the constraint in (66) is satisfied, we can view the rightward
and leftward linear sweeps as a one dimensional scan. Therefore, the time $t$
it takes the sweepers to clean the spread of potential evaders from the right
section of the region can be calculated from, ${V_{s}}t={R_{f}}+{V_{T}}t$.
Therefore, $t$ is given by,

$t=\frac{{{R_{f}}}}{{{V_{s}}-{V_{T}}}}$ (67)

$\tilde{t}$ is computed by calculating the time it takes the sweepers located
at point $(tV_{s},0)$ to change their scanning direction and perform a
leftward scan to a point that spread at a velocity of $V_{T}$ from the
leftmost point in the evader region at the origin of the search, the point
$(-R_{f},0)$, for a time given by ${\tilde{t}+t}$. We have that,

$-{R_{f}}-{V_{T}}\left({\tilde{t}+t}\right)=t{V_{s}}-{V_{s}}\tilde{t}$ (68)

Plugging in the value of $t$ yields,

$\tilde{t}=\frac{{2{V_{s}}{R_{f}}}}{{{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}$
(69)

$T_{linear}$ is therefore given by,

${T_{linear}}=t+\tilde{t}$ (70)

Therefore, the total scan time until a complete cleaning of the evader region
is given by,

$T_{total}=T_{spiral}+T_{in}+T_{e}+T_{l}+T_{f}+T_{linear}$ (71)

For the one dimensional scan to be valid and ensure a non escape search and
complete cleaning of the evader region, (66) must be satisfied. This demand
implies that,

$\frac{{2r-{R_{f}}}}{{{V_{T}}}}>\frac{{{R_{f}}\left({3{V_{s}}-{V_{T}}}\right)}}{{{{\left({{V_{s}}-{V_{T}}}\right)}^{2}}}}$
(72)

By rearranging terms, (72) can be written as,

$2r{\left({{V_{s}}-{V_{T}}}\right)^{2}}>{R_{f}}{V_{s}}\left({{V_{s}}+{V_{T}}}\right)$
(73)

By substitution of $R_{0}$ with $\alpha r$ where $\alpha>1$ and by
substituting the terms for $V_{s}$ and ${R_{f}}$, (73) resolves to a quadratic
equation in $\Delta V$ that has only one positive root. This root is a
monotonically decreasing function in $\alpha$, given by

${V_{s}}^{2}\left({2r-{R_{f}}}\right)-{V_{s}}{V_{T}}\left({4r+{R_{f}}}\right)+2r{V_{T}}^{2}>0$
(74)

The quadratic equation in (74) has $2$ positive roots. Therefore, in order for
the one dimensional linear scan to be valid $V_{s}$ has to be greater than the
largest positive root. Implying that,

${V_{s}}\geq\frac{{2r{V_{T}}+{V_{T}}{R_{f}}}}{{2r-{R_{f}}}}$ (75)

Figure 12: End-game search times until complete cleaning of the evader region
for the same-direction spiral sweep processes. We simulated sweep processes
with an even number of agents, ranging from $2$ to $32$ agents, that employ
the multi-agent same-direction spiral sweep processes. We show results
obtained for different values of velocities above the spiral critical
velocity. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$R_{0}=100$. Figure 13: Total search times until complete cleaning of the
evader region for the same-direction spiral sweep processes. We simulated
sweep processes with an even number of agents, ranging from $2$ to $32$
agents, that employ the multi-agent same-direction spiral sweep processes. We
show results obtained for different values of velocities above the spiral
critical velocity. The chosen values of the parameters are $r=10$, $V_{T}=1$
and $R_{0}=100$.

##  X Comparative Analysis of Pincer Movement Search Strategies and same-
direction Sweeps

The purpose of this section is to compare between the obtained results for the
circular and spiral same-direction sweep processes that were developed in the
previous sections and compare them to pincer sweep processes developed in [1].
In order to make a fair comparison between the total sweep times of sweeper
swarms that can perform both the circular and spiral sweep processes the
number of sweepers and sweeper velocity must be the same in each of the tested
spiral and circular swarms. The critical velocity that is required for
sweepers that perform the same-direction circular or spiral sweep processes is
higher than the minimal critical velocity of their pincer sweep counterparts.
Additionally, since pincer sweep processes require a smaller critical velocity
compared to same-direction sweep processes, in order to make a fair comparison
all sweepers in the swarm move at velocities above the critical velocity of
$2$ sweepers that perform the same-direction circular sweep.

In Fig. $14$ we show the ratio between the time it takes swarms that employ
same-direction circular sweeps to the time it takes swarms that perform their
circular pincer sweep processes counterparts to detect all evaders in the
region. We see that for all choices of velocities above the same-direction
circular critical velocity, the ratio is greater than $1$, implying that same-
direction circular sweeps require more time in order to clean the entire
evader region. The sweep times are obtained for different values of velocities
above the same-direction circular critical velocity of $2$ sweepers, since
this velocity is greater than the critical velocity of search processes
performed with more sweepers.

In Fig. $15$ we show the ratio between the time it takes swarms that employ
same-direction spiral sweeps to the time it takes swarms that perform their
spiral pincer sweep processes counterparts to detect all evaders in the
region. We see that when $4$ or more sweepers perform the search process, for
all choices of velocities above the same-direction circular critical velocity,
the ratio is greater than $1$, implying that same-direction spiral sweeps
require more time in order to clean the entire evader region. The only cases
where same-direction spiral sweeps are better than their pincer based
counterparts are when sweepers move at velocities that are close to the
critical velocity and where the sweep process is performed with more than $2$
sweeping agents. We observe that as the number of sweepers increases, the gain
in utilizing the cooperation between the sweeping pairs in the pincer-based
sweep processes decreases the sweeping time dramatically. When the sweepers
perform the same-direction spiral sweeps they have to sweep large sections at
each iteration in order to ensure no evader escapes, while in pincer-based
spiral search strategies, sweeping these additional sections in unnecessary to
the complementary and symmetric trajectories of the sweepers. The sweep times
in Fig $15$ are obtained for different values of velocities above the same-
direction spiral critical velocity of $2$ sweepers, since this velocity is
greater than the critical velocity of search processes performed with more
sweepers. This means that the values of $\Delta V$ that are mentioned in Fig.
$14$ correspond to sweeper velocities that are almost twice the same-direction
spiral critical velocities presented in Fig. $15$. Requiring a higher critical
velocity implies that there are entire regions of operation where an evader
region with a given radius could be cleaned by a sweeper swarm that performs
the same-direction spiral sweep process but cannot be cleaned by a sweeper
swarm that performs the same-direction circular sweep process. This also
implies that swarms that perform pincer movement search strategies can sweep
larger regions than their same-direction sweeps counterparts.

Figure 14: Ratio between total search times until complete cleaning of the
evader region for circular same-direction and pincer sweep processes. We
simulated sweep processes with an even number of agents, ranging from $2$ to
$32$ agents, that employ the multi-agent same-direction and pincer circular
sweep processes. We show results obtained for different values of velocities
above the same-direction circular critical velocity. The chosen values of the
parameters are $r=10$, $V_{T}=1$ and $R_{0}=100$. Figure 15: Ratio between
total search times until complete cleaning of the evader region for spiral
same-direction and pincer sweep processes. We simulated sweep processes with
an even number of agents, ranging from $2$ to $32$ agents, that employ the
multi-agent same-direction and pincer spiral sweep processes. We show results
obtained for different values of velocities above the same-direction spiral
critical velocity. The chosen values of the parameters are $r=10$, $V_{T}=1$
and $R_{0}=100$.

##  XI Conclusions and Future Research Directions

This research considers a scenario in which a multi-agent swarm of agents
performs a search of an area containing smart mobile evaders that are to be
detected. There can be many evaders in this area, and potential evaders can be
located at any point in an initial circular region of radius $R_{0}$. The
sweepers objective is to “clean” or to detect all evaders that can move freely
in all directions from their initial locations. The search time depends on the
type of sweeping movement the sweeper swarm employs. This work compares same-
direction sweeps and pincer movement sweep protocols demonstrating and proving
the superiority of the latter. We perform a quantitative comparison between
pincer based sweep protocols and same-direction sweep protocols for any number
of even sweepers where the sensing capabilities and velocities of the swarms
are equivalent. We prove that critical velocities for pincer based search
methods are lower than their same-direction counterparts and therefore allow
to sweep successfully larger regions. Afterwards, we provide a comparison
between the different search methods in terms of completion times of the sweep
processes.

## Appendix A

The inward advancement time at iteration $i$ is denoted by ${T_{i{n_{i}}}}$.
It is given by,

${T_{i{n_{i}}}}=\frac{{{\delta_{{i_{eff}}}}(\Delta
V)}}{{{V_{s}}}}=\frac{{rn\left({{V_{s}}-{V_{T}}}\right)-2\pi{R_{i}}{V_{T}}}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}$
(76)

The total advancement time until the evader region is bounded by a circle of
with a radius that is less than or equal to r is denoted as
$\widetilde{T}_{in}$. It is given by,

$\widetilde{T}_{in}=\sum\limits_{i=0}^{N-2}{{T_{i{n_{i}}}}}=\frac{{\left({{N_{n}}-1}\right)rn\left({{V_{s}}-{V_{T}}}\right)}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}-\frac{{2\pi{V_{T}}\sum\limits_{i=0}^{{N_{n}}-2}{{R_{i}}}}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}$
(77)

We have that,

${R_{N_{n}-2}}=\frac{{{c_{1}}}}{{1-{c_{2}}}}+{c_{2}}^{N_{n}-2}\left({{R_{0}}-\frac{{{c_{1}}}}{{1-{c_{2}}}}}\right)$
(78)

The sum of the radii is given by,

$\sum\limits_{i=0}^{N_{n}-2}{{R_{i}}}=\frac{{{R_{0}}-{c_{2}}{R_{N_{n}-2}}+(N_{n}-2){c_{1}}}}{{1-{c_{2}}}}$
(79)

Where the coefficients $c_{1}$ and $c_{2}$ are given by,

${c_{1}}=-\frac{{r\left({{V_{s}}-{V_{T}}}\right)}}{{{V_{s}}+{V_{T}}}},{c_{2}}=1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}$
(80)

Substitution of terms for the expression of ${R_{N_{n}-2}}$ in (78) yields,

$\begin{array}[]{l}{R_{N_{n}-2}}=\frac{{r\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{{V_{s}}+{V_{T}}}}}\right)^{N_{n}-2}}\left({\frac{{2\pi{R_{0}}{V_{T}}-r\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}}\right)\end{array}$
(81)

Substitution of terms in (79) yields,

$\begin{array}[]{l}\sum\limits_{i=0}^{{N_{n}}-2}{{R_{i}}}=-\frac{{{R_{0}}n\left({{V_{s}}+{V_{T}}}\right)}}{{2\pi{V_{T}}}}+\frac{{r{n^{2}}\left({{V_{s}}-{V_{T}}}\right)\left({{V_{s}}+{V_{T}}}\right)}}{{{{\left({2\pi{V_{T}}}\right)}^{2}}}}+\\\
\frac{{{N_{n}}nr\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}-\frac{{rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}-1}}\left({\frac{{\left({2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}\right)n\left({{V_{s}}+{V_{T}}}\right)}}{{{{\left({2\pi{V_{T}}}\right)}^{2}}}}}\right)\end{array}$
(82)

We therefore obtain that,

$\begin{array}[]{l}\widetilde{T}_{in}=\frac{{{R_{0}}}}{{{V_{s}}}}-\frac{{rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}{V_{s}}}}\\\
-{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}-1}}\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}{V_{s}}}}}\right)\end{array}$
(83)

The last inward advancement is given by,

${T_{{}_{in}last}}=\frac{{{R_{N_{n}}}}}{{{V_{s}}}}$ (84)

We have that,

${R_{N_{n}}}=\frac{{{c_{1}}}}{{1-{c_{2}}}}+{c_{2}}^{N_{n}}\left({{R_{0}}-\frac{{{c_{1}}}}{{1-{c_{2}}}}}\right)$
(85)

Therefore,

$\begin{array}[]{l}{R_{{N_{n}}}}=\frac{{rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}}}}\right)\end{array}$
(86)

Substitution of terms yields,

$\begin{array}[]{l}{T_{{}_{in}last}}=\frac{{rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}{V_{s}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}{V_{s}}}}}\right)\end{array}$
(87)

The total inward advancement times is therefore given by,

${T_{in}}=\frac{{{R_{0}}}}{{{V_{s}}}}+{\left({1+\frac{{2\pi{V_{T}}}}{{{V_{s}}+{V_{T}}}}}\right)^{N-1}}\left({\frac{{2\pi{R_{0}}{V_{T}}-r\left({{V_{s}}-{V_{T}}}\right)}}{{{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}}\right)$
(88)

The time it takes the sweepers to perform the circular sweeps before the
evader region is bounded by a circle with a radius that is smaller or equal to
$r$ is given by,

$\widetilde{T}_{circular}=\frac{{{T_{0}}-{c_{2}}{T_{{N_{n}}-1}}+\left({{N_{n}}-1}\right){c_{3}}}}{{1-{c_{2}}}}$
(89)

Where the coefficient $c_{3}$ is given by,

${c_{3}}=-\frac{{2\pi
r\left({{V_{s}}-{V_{T}}}\right)}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}$
(90)

The time it takes the sweepers to perform the first sweep is given by,

${T_{0}}=\frac{{2\pi{R_{0}}}}{{n{V_{s}}}}$ (91)

The time it takes the sweepers to perform the last circular sweep is given by,

$\begin{array}[]{l}{T_{{N_{n}}-1}}=\frac{{r\left({{V_{s}}-{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}-1}}\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{n{V_{s}}{V_{T}}}}}\right)\end{array}$
(92)

Therefore $\widetilde{T}_{circular}$ is given by,

$\begin{array}[]{l}\widetilde{T}_{circular}=-\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}+\frac{{r\left({{V_{s}}-{V_{T}}}\right)\left({n\left({{V_{s}}+{V_{T}}}\right)+2\pi{V_{T}}{N_{n}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({{V_{s}}+{V_{T}}}\right)\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}}\right)\end{array}$
(93)

The last circular sweep occurs when the lowest tips of the sweepers’ sensors
are located at the center of the evader region. It is given by,

${T_{last}}=\frac{{2\pi r}}{{{nV_{s}}}}$ (94)

Therefore the total circular traversal times are given by,

$\begin{array}[]{l}{T_{circular}}=-\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}+\frac{{r\left({{V_{s}}-{V_{T}}}\right)\left({n\left({{V_{s}}+{V_{T}}}\right)+2\pi{V_{T}}{N_{n}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}+\\\
{\left({1+\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)^{{N_{n}}}}\left({{V_{s}}+{V_{T}}}\right)\left({\frac{{2\pi{R_{0}}{V_{T}}-rn\left({{V_{s}}-{V_{T}}}\right)}}{{2\pi{V_{T}}^{2}{V_{s}}}}}\right)+\\\
\frac{{2\pi r}}{{n{V_{s}}}}\end{array}$ (95)

## Appendix B

We have that,

$2r{\left({{V_{s}}-{V_{T}}}\right)^{2}}>{R_{last}}{V_{s}}\left({{V_{s}}+{V_{T}}}\right)$
(96)

And,

${V_{s}}=\frac{{2\pi{R_{0}}{V_{T}}}}{{rn}}+{V_{T}}+\Delta V\hskip
2.84526pt{R_{last}}=\frac{{2\pi r{V_{T}}}}{{n{V_{s}}}}$ (97)

Denoting $\alpha=\frac{{{R_{0}}}}{r}$ and substituting the following terms in
(96) yields,

$2r{\left({\frac{{2\pi{V_{T}}\alpha}}{n}+\Delta V}\right)^{2}}>\frac{{2\pi
r{V_{T}}}}{n}\left({\frac{{2\pi\alpha{V_{T}}}}{n}+2{V_{T}}+\Delta V}\right)$
(98)

Rearranging terms yields a quadratic equation in $\Delta V$,

$\begin{array}[]{{l}}\Delta{V^{2}}+\Delta
V\left({\frac{{4\pi{V_{T}}\alpha-\pi{V_{T}}}}{n}}\right)+\frac{{4{\pi^{2}}{V_{T}}^{2}{\alpha^{2}}-2{\pi^{2}}\alpha{V_{T}}^{2}-2\pi
n{V_{T}}^{2}}}{{{n^{2}}}}\\\ >0\end{array}$ (99)

Equation (99) has a positive and a negative root. Since $\Delta V$ is non-
negative we are interested only in the positive root. Therefore, in order to
completely clean the evader region $\Delta V$ has to satisfy

$\Delta V\geq\frac{{-4\pi{V_{T}}\alpha+\pi{V_{T}}+{V_{T}}\sqrt{{\pi^{2}}+8\pi
n}}}{{2n}}$ (100)

## References

  * [1] R. M. Francos and A. M. Bruckstein, “Search for smart evaders with swarms of sweeping agents,” _arXiv preprint arXiv:2005.01011_ , 2020.
  * [2] L. D. Stone, J. O. Royset, and A. R. Washburn, “Optimal search for moving targets (international series in operations research & management science 237),” _Cham, Switzerland: Springer_ , 2016.
  * [3] K. Passino, M. Polycarpou, D. Jacques, M. Pachter, Y. Liu, Y. Yang, M. Flint, and M. Baum, “Cooperative control for autonomous air vehicles,” in _Cooperative control and optimization_. Springer, 2002, pp. 233–271.
  * [4] I. Rekleitis, V. Lee-Shue, A. P. New, and H. Choset, “Limited communication, multi-robot team based coverage,” in _IEEE International Conference on Robotics and Automation, 2004. Proceedings. ICRA’04. 2004_ , vol. 4. IEEE, 2004, pp. 3462–3468.
  * [5] S. Alpern and S. Gal, _The theory of search games and rendezvous_. Springer Science & Business Media, 2006, vol. 55.
  * [6] Z. Tang and U. Ozguner, “On non-escape search for a moving target by multiple mobile sensor agents,” in _2006 American Control Conference_. IEEE, 2006, pp. 6–pp.
  * [7] B. O. Koopman, _Search and screening: general principles with historical applications_. Pergamon Press, 1980.
  * [8] P. Vincent and I. Rubin, “A framework and analysis for cooperative search using uav swarms,” in _Proceedings of the 2004 ACM symposium on Applied computing_. ACM, 2004, pp. 79–86.
  * [9] Y. Altshuler, V. Yanovsky, I. A. Wagner, and A. M. Bruckstein, “Efficient cooperative search of smart targets using uav swarms,” _Robotica_ , vol. 26, no. 4, pp. 551–557, 2008.
  * [10] I. A. Wagner and A. M. Bruckstein, “Cooperative cleaners: A case of distributed ant-robotics,” _Communications, Computation, Control, and Signal Processing: A Tribute to Thomas Kailath_ , pp. 289–308, 1997.
  * [11] Y. Altshuler, A. M. Bruckstein, and I. A. Wagner, “Swarm robotics for a dynamic cleaning problem,” in _Proceedings 2005 IEEE Swarm Intelligence Symposium, 2005. SIS 2005._ IEEE, 2005, pp. 209–216.
  * [12] Y. Altshuler, V. Yanovski, I. A. Wagner, and A. M. Bruckstein, “Multi-agent cooperative cleaning of expanding domains,” _The International Journal of Robotics Research_ , vol. 30, no. 8, pp. 1037–1071, 2011.
  * [13] T. G. McGee and J. K. Hedrick, “Guaranteed strategies to search for mobile evaders in the plane,” in _2006 American Control Conference_. IEEE, 2006, pp. 6–pp.
  * [14] P. C. Hew, “Linear and concentric arc patrols against smart evaders,” _Military Operations Research_ , vol. 20, no. 3, pp. 39–48, 2015.
  * [15] D. Shishika and V. Kumar, “Local-game decomposition for multiplayer perimeter-defense problem,” in _2018 IEEE Conference on Decision and Control (CDC)_. IEEE, 2018, pp. 2093–2100.
  * [16] D. Shishika, J. Paulos, M. R. Dorothy, M. A. Hsieh, and V. Kumar, “Team composition for perimeter defense with patrollers and defenders,” in _2019 IEEE 58th Conference on Decision and Control (CDC)_. IEEE, 2019, pp. 7325–7332.
  * [17] D. Shishika, J. Paulos, and V. Kumar, “Cooperative team strategies for multi-player perimeter-defense games,” _IEEE Robotics and Automation Letters_ , vol. 5, no. 2, pp. 2738–2745, 2020.
  * [18] R. M. Francos and A. M. Bruckstein, “Search for smart evaders with sweeping agents,” _arXiv preprint arXiv:1905.04006_ , 2019.
  * [19] S. Tisue and U. Wilensky, “Netlogo: A simple environment for modeling complexity,” in _International conference on complex systems_ , vol. 21. Boston, MA, 2004, pp. 16–21.