# Defense Against Smart Invaders with Swarms of Sweeping 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

The goal of this research is to devise guaranteed defense policies that allow
to protect a given region from the entrance of smart mobile invaders by
detecting them using a team of defending agents equipped with identical line
sensors. By designing cooperative defense strategies that ensure all invaders
are detected, conditions on the defenders’ speed are derived. Successful
accomplishment of the defense task implies invaders with a known limit on
their speed cannot slip past the defenders and enter the guarded region
undetected. The desired outcome of the defense protocols is to defend the area
and additionally to expand it as much as possible. Expansion becomes possible
if the defenders’ speed exceeds a critical speed that is necessary to only
defend the initial region. We present results on the total search time,
critical speeds and maximal expansion possible for two types of novel pincer-
movement defense processes, circular and spiral, for any even number of
defenders. The proposed spiral process allows to detect invaders at nearly the
lowest theoretically optimal speed, and if this speed is exceeded, it also
allows to expand the protected region almost to the maximal area.

###### Index Terms:

Multiple Mobile Robot Systems, Motion and Path Planning for Multi Agent
Systems, Aerial Robots, Teamwork Analysis, Robot Surveillance and Security

##  I Introduction

The objective of this paper is to develop efficient guaranteed defense search
strategies in which a swarm of $n$ defending agents must guarantee the
detection of an unknown number of smart invaders from entering a region which
the defenders guard. An initially given circular region of radius $R_{0}$ is
assumed not to contain mobile invaders at the beginning of the sweep protocol,
and is referred to as the initial protected region. The invaders may attempt
to move into the protected region from any point outside of the initial
protected region and try to enter the protected region (the region where
invaders are not located) at a maximal speed of $V_{T}$, known to the
defenders. All defenders move at a speed $V_{s}>V_{T}$ and detect the invaders
with linear sensors of length $2r$. Once a defender’s sensor touches a
particular location, potential invaders that might have been present there are
detected and therefore are “eliminated”. Each guaranteed defense strategy
requires a minimal speed that depends on the trajectory of the sweeping
defenders and imposes a lower bound on the speed of the defenders. This
critical speed is derived to ensure the satisfaction of the guarding task.
Increasing the speed above the lower bound enables the defending agents to not
only complete the guarding task but also to expand the guarded region as well.

Performing an efficient defense protocol requires that the footprint of the
defenders’ sensors minimally overlaps the protected region, thus allowing them
to detect invaders further away from the protected region and stop their
advance. By sweeping around the initial region they are required to guard,
defenders with speeds higher than the critical speed, can increase the
protected region, up to a circular region with a maximal radius that depends
on their excess speed, their sensing capabilities and the sweep strategy they
employ. This research paper develops two guaranteed defense search protocols
for a swarm consisting of an even number of defenders that sweep the region.
There are two goals for each developed defense strategy, defending the initial
protected region in the defense task and performing the maximal expansion task
in which the defenders execute their defense strategy until the protected
region reaches its maximal defendable area, by employing novel pincer-movement
search strategies. The proposed defense protocols are based on pairs of
defenders that move toward each other thus entrapping invaders and halting
their advance into the protected region.

###  I-A Overview of Related Research

Multi-agent search problems have been an active area of research for almost a
century, where early works by [1] focused on designing algorithms for
detecting ships and submarines from surveillance aircraft in the English
channel during the second world war. Multi-agent search tasks involve
searching for static or mobile targets and can take place in environments that
range from being fully or partially known to being completely unknown [2, 3,
4].

In case the targets being searched are static, searching the entire area in
which the targets are located will surely result in their detection.
Therefore, in such scenarios, the goal in designing an optimal searching
algorithm is to find a traversal path for the searching agents that locates
all targets in minimal time. In case the targets are mobile, detection is not
always guaranteed since the targets’ movements might prevent the searchers to
detect them. This situation can occur even in closed and confined
environments, in which the targets cannot exit the borders of the area being
searched. In this paper we address the detection of a more challenging type of
target, a smart mobile target that may perform evasive maneuvers by detecting
and responding to the movements of the defending team in order to avoid being
intercepted by the defenders that wish to prevent it from entering the
protected region. Smart targets, which in the context of this paper are
referred to as invaders, are assumed to have full knowledge of the defenders’
strategy and to use that knowledge, to the best of their ability, in order to
devise a counter strategy that allows them to enter the protected region
without being caught. In this work we are interested in developing guaranteed
defense strategies against smart invaders, implying that regardless of the
infiltration plan the invaders choose and their resulting trajectories, they
will all be detected by the defending team. In [5], Vincent et. al investigate
guaranteed detection of smart targets in a channel environment using a team of
detecting sweeping agents and [6] provides optimal strategies to the same
problem.

In [7], McGee et al. study how to defend a given planar circular region
against the entrance of smart intruders. The intruders do not have any
maneuverability restrictions besides an upper limit on their speed. The
defenders are equipped with sensors that detect intruders that are inside a
disk shaped region around them. The considered search pattern is composed of
spiral and linear sections.

Somewhat related problems are pursuit-evasion games, in which the pursuers’
goal is to detect and catch the evaders and the evaders goal is to avoid being
detected and caught by the pursuing team. There are several variants of
pursuit-evasion games which include different combinations of single and
multiple evaders and pursuers settings. Pursuit-evasion games were also
applied to address defending a region from the entrance of intruders. Such
works are [8, 9, 10] by Shishika et al. which investigate perimeter defense
games and emphasize the cooperation between pursuers to improve the defense
tactic. In [8], members of the defending team of agents cooperate and form
defender pairs by moving in a ”pincer movement” to prevent intruders from
entering a convex region in the plane. Cooperation between the defender sub-
teams, allows to extend the winning regions of the defender team compared to
performing uncooperative defense strategies.

In [11], pursuit–evasion problems involving multiple pursuers and multiple
evaders (MPME) are studied. Pursuers and evaders are all assumed to be
identical, and pursuers follow either a constant bearing or a pure pursuit
strategy. The problem is simplified by adopting a dynamic divide and conquer
approach, where at every time instant each evader is assigned to a set of
pursuers based on the instantaneous positions of all the players. The original
MPME problem is decomposed to a sequence of simpler multiple pursuers single
evader (MPSE) problems by testing whether a pursuer is relevant or redundant
against each evader, by using Apollonius circles. Then, only the relevant
pursuers participate in the MPSE pursuit of each evader. Recent surveys on
pursuit evasion problems are [12, 13, 14].

In [12], a taxonomy of search problems is presented. The paper highlights
algorithms and results arising from different assumptions on searchers,
evaders and environments and discusses potential field applications for these
approaches. The authors focus on a number of pursuit-evasion games that are
directly connected to robotics and not on differential games which are the
focus of the other cited surveys. The paper concentrates on adversarial
pursuit-evasion games on graphs and in polygonal environments where the
objective is to maximize the worst-case performance on the search or capture
time and on probabilistic search scenarios where the objective is the
optimization of the expected value of the search objective, such as the
maximal probability of detection or minimal capture time. In [13], a survey on
pursuit problems with $1$ pursuer versus $2$ evaders or $2$ pursuers versus
$1$ evader are formulated as a dynamic game and solved with general methods of
zero-sum differential games. In [14], the authors present a recent survey on
pursuit-evasion differential games and classify the papers according to the
numbers of participating players: single-pursuer single-evader (SPSE), MPSE,
one- pursuer multiple-evaders (SPME) and MPME.

In [15], a two-player differential game in which a pursuer aims to capture an
evader before it escapes a circular region is investigated. The state space,
comprised of pursuer and evader locations, is divided into evader and defender
winning regions. In each region the players try to execute their optimal
strategies. The players’ strategy depends on the state of the system (if it is
in the capture or escape regions), and the proposed approach guarantees that
if the players execute the prescribed optimal moves they improve their chances
to win. The players move at a constant speed and the pursuer is faster than
the evader. The players’ controls are the instantaneous heading angles. The
game is a two-termination set differential game, i.e., the game ends when
either player wins. In [16], the problem of a border defense differential game
where $M$ pursuers cooperate in order to optimally catch $N$ evaders before
they reach the border of the region and escape is investigated. The members of
the pursuer team exchange information between the team members and decide on
the discrete assignment of pursers to evaders in an on-line manner.
Furthermore, the game is a perfect information differential game where both
pursuers and evaders have access to all state variables, which are the
locations of all players, as well all their dynamics and velocities. The
pursuers in this setting are assumed to have greater speeds than the evaders.
The game takes place in a simple half-plane environment, and ends when all
evaders are either caught or reach the border and escape.

Devising multi-robot perimeter patrol policies for adversarial settings in
which an opponent has complete knowledge of the robots’ patrol strategy are
developed in [17, 18]. Possessing information about the robots’ patrol policy
enables the smart opponent to attempt to enter the perimeter undetected at the
location with the highest probability of success. In order to prevent the
opponent to utilize its knowledge on the strategy of the robot team,
randomness is introduced into the robots’ perimeter patrol algorithm, thus
preventing the opponent from having full knowledge of the chosen patrol
strategy and consequently increasing the chances to detect it.

###  I-B Contributions

In this paper, we provide several theoretical and experimental contributions
to multi-agent search and coordinated motion planning literature. In the
considered scenario, a defending team of agents has to protect an initial
region from the entrance of an unknown number of smart invaders, that have
superior sensing and planning capabilities compared to the defender team. An
analysis on the defenders’ trajectories and critical speeds that enable the
successful completion of the defense task is provided. Additionally, if
possible, an additional goal for the defender team is to optimally expand the
region which they guard to the maximal allowable size that still enables the
defender team to detect any number of smart invaders that may attempt to enter
the protected region. Hence, the total search times and the maximal attainable
protected area are also reported. Extensive theoretical and numerical analysis
is performed for both the defense and maximal expansion tasks.

  * •

We propose two types of novel guarding and expansion strategies for any for
even number of defenders:

    * –

Circular defense pincer sweep strategy

    * –

Spiral defense pincer sweep strategy

  * •

Based on geometric and dynamic constraints we establish the necessary critical
speed for each defense protocol to be successful and derive analytical
expressions for the search times and radius of maximal expansion for the two
types of search patterns.

  * •

We show that the spiral defense pincer sweep strategy enables defenders that
sweep with speeds that are only slightly above the theoretical lower bound to
ensure all invaders attempting to enter the protected region are detected.

  * •

We compare between the circular and spiral defense pincer sweep expansion
strategies and highlight the advantages of the spiral strategy in both
enabling the expansion of the region to a larger size and the search time
required to reach it.

  * •

We provide a quantitative comparison between the developed pincer-based
defense protocols and the corresponding same-direction sweep protocols that
are regarded as the state-of-the-art in defense against smart invaders. We
prove that the corresponding pincer-based protocols yield lower critical
speeds, shorter time to increase the protected region to its maximal size as
well as the ability to expand the protected region to a larger area compared
to same-direction protocols.

  * •

We demonstrate through empirical simulations conducted with MATLAB and NetLogo
the theoretical results and present the evolution of the guarding and
expansion strategies graphically.

###  I-C Paper Organization

This article is organized as follows. Section III presents an optimal bound on
the speed of defenders employing the guarding task. This lower bound is
independent of the actual implemented defense protocol. The obtained lower
bound is used as a one of the comparison metrics for evaluation the
performance of different guard/defense protocols. Section IV provides an
analysis of the defense and maximal expansion problems when the defender team
performs the circular defense pincer sweep process. Section V presents an
analysis of the defense and maximal expansion problems when the defender team
performs the spiral defense pincer sweep process. Section VI provides a
comparison between the circular and spiral defense pincer defense strategies
and highlights the advantages of using the proposed spiral defense pincer
protocol. Section VII compares prevalent approaches for defense against smart
invaders which are considered the state-of-the-art in defense against smart
invaders and compares these approaches to the pincer-based defense protocols
developed in this work, proving the superiority of pincer-based approaches.
The last section draws conclusions from the performed analysis and provides
some interesting future research directions.

##  II Pincer-Based Defense

This research focuses on developing a guaranteed defense protocol of an
initial region from the entrance of an unknown number of smart invaders. The
region is protected by employing a multi-agent team of identical cooperating
defenders that sweep around the protected region and detect invaders that
attempt to enter it. The defenders possess a linear sensor of length $2r$ with
which they detect invaders that intersect their field-of-view. The only
information the defenders have is that invaders may be located at any point
outside of an initial circular region of radius $R_{0}$, referred to as the
initial protected region at the beginning of the defense process.

The proposed defense strategies are deterministic and pre-planned, and
therefore they can be accomplished by using simple agents-like defenders. All
defenders move with a speed is $V_{s}$ which is measured at the center of a
defender’s sensor. The invaders move at a maximal speed of $V_{T}$, and do not
have any maneuverability restrictions. There are two objectives for a defense
strategy, defending the initial protected region and, if possible, expanding
the protected region by performing an iterative expansion strategy until the
region reaches the maximal defendable area.

The time it takes the defender team to expand the protected region to the
maximal defendable size obviously depends on the applied defense protocol. Two
types of defense strategies are investigated, circular and spiral. When
defenders perform the maximal expansion task, their goal is to iteratively
increase the radius of the protected region after each sweep, up to the
maximal defendable size of the region. At the beginning of the circular
defense pincer sweep process only half the length of the defenders’ sensors is
outside of the protected region, i.e. a footprint of length $r$, while the
other half is inside the region in order to catch invaders that may move
inside the region while the search progresses. At the beginning of the spiral
defense pincer sweep process the entire length of the defenders’ sensors is
outside the protected region, i.e. a footprint of length $2r$.

The basic idea in performing pincer-based defense is requiring defenders to
search for invaders in opposite directions instead of equally distributing the
defenders around the region and letting them search in the same direction.
Defenders performing pincer movements address the worst-case scenario of
invader entrance to the protected region from the “most dangerous points”,
points situated at the edges of their sensors nearest to the protected
region’s boundary. Invaders located at these points have the maximal amount of
time to advance towards the protected region during defender movement and thus
if invaders that attempt to infiltrate the region from these points are
detected, invaders trying to enter from other points are detected as well. For
an extensive discussion about the comparison between pincer-based sweeps and
same-direction sweeps in search tasks against smart evaders see [19, 20].

Successfully completing the defense and maximal expansion tasks with the
lowest possible critical speed is one of the performance criteria for an
efficient defense strategy. Pincer-based defense procedures result in lower
critical speeds compared to their same-direction counterparts, and hence are
chosen in the developed defense protocols. The discussed pincer-based
strategies can be performed with any even number of defenders. The basic idea
of pincer-based defense is to decompose the defender team into pairs that are
placed back-to-back at the start of the protocol. Each defender in a pair
moves in an opposite direction, counter-clockwise or clockwise. When two
defenders meet at a location after the completion of a sweep, implying that
their sensors are again back-to-back, they switch their movement direction.
The direction switches are performed every time a defender meets the defender
scanning the adjacent angular section to its section. Based on the numbers of
defenders performing the defense task, the protected region is portioned into
equal angular sectors, where each sector is searched by a different defender.
The discussed defense protocols can be applied to both $2$ dimensional defense
tasks on the plane or in $3$ dimensional defense tasks where the defenders and
invaders are drone-like agents that fly over the protected region.

Figure 1: (a) - Initial placement of $2$ defenders performing the circular
defense pincer sweep process. (b) - Initial placement of $2$ defenders
performing the spiral defense pincer sweep process. Defenders’ sensors are
shown in green and red areas indicate locations where potential invaders may
be present. Blue areas represent locations that belong to the initial
protected region that does not contain invaders. The angle $\phi$ is the angle
between the tip of a defender’s sensor and the normal to of the edge of the
protected region. $\phi$ is an angle that depends on the ratio between the
defender and invader speeds.

The first considered defense protocol is the circular defense sweep protocol.
The circular defense protocol allows to perform the defense and maximal
expansion tasks with defenders with basic motion capabilities however as a
byproduct of its simplicity it is far from being optimal. Hence, we propose
the spiral defense pincer sweep process that provides an improved protocol
that uses spiral scans, drawing inspiration from [7]. The spiraling-in
trajectories of the defenders allow them to track the ”wavefront” of the
expanding protected region, thus detecting invaders at the furthest possible
locations from the invader region. At last, we compare and discuss the
obtained results of the two defense strategies. The evaluation metrics for the
defense strategies include the minimal defender speed required for successful
defense of the initial protected region, the time to expand the protected
region to the maximal defendable area as well as the maximal feasible
protected region’s radius resulting from the defense protocol. All these
quantities are expressed as a function of the search parameters $R_{0}$, $r$,
$V_{T}$ and the number of defenders, $n$.

Illustrative simulations demonstrating the evolution of the defense processes
were generated using NetLogo software [21] and are presented in Fig. $2$. and
Fig. $3$. Green areas show locations that were searched and hence do not
contain invaders and red areas indicate locations where potential invaders may
be present. Blue areas represent locations that belong to the initial
protected region that does not contain invaders. Fig. $2$. shows the cleaning
progress during the expansion of the protected region when $6$ defenders
perform the circular defense pincer sweep process. Fig. $3$. shows the
evolution of the defense process during the expansion of the protected region
when $4$ defenders perform the spiral defense pincer sweep process.

Figure 2: Swept areas and protected region status for different times in a
scenario where $6$ defenders perform the circular defense pincer sweep
process. (a) - Beginning of first sweep. (b) - Toward the completion of the
first sweep. (c) - Beginning of the second sweep. (d) - Midway of the second
sweep. (e) - End of the fourth sweep. (f) - Beginning of fifth sweep. Green
areas show locations that were searched and hence do not contain invaders and
red areas indicate locations where potential invaders may be present. Blue
areas represent locations that belong to the initial protected region that
does not contain invaders.  Figure 3: Swept areas and protected region status
for different times in a scenario where $4$ defenders perform the spiral
defense pincer sweep process. (a) - Beginning of first sweep. (b) - End of the
first sweep. (c) - Beginning of the second sweep. (d) - Midway of the second
sweep. (e) - End of the second sweep. (f) - Toward the end of the third sweep.
Green areas show locations that were searched and hence do not contain
invaders and red areas indicate locations where potential invaders may be
present. Blue areas represent locations that belong to the initial protected
region that does not contain invaders.

Note that in the considered problems, the search is continued until the
expansion of the protected region reaches the maximal attainable radius, and
afterwards the defenders continuously patrol around this radius.

###  II-A Comparison to Related Research

In our previous work [22], the confinement of an unknown number of smart
evaders that are originally located somewhere inside a given circular region
to their original domain is investigated. By deploying a line formation of
searching agents or alternatively a single agent with an equivalent sized
linear sensor that sweep inside and around the region, guaranteed detection
protocols are developed. In case the speed of the agents in the line formation
exceeds a critical speed, they may decrease the evader region by performing a
search protocol consisting of alternating circular sweeps around the region
that are followed by inward advancement steps toward the center of the evader
region ( the region in which evaders are located). A proof in the paper shows
that since the evaders are smart, a search pattern that uses circular sweeps
cannot completely clean the evader region, Therefore, after the evader region
is reduced by the circular sweeping protocol to a region that is bounded in a
circle with a radius equal to half the formation’s sensing range, the search
pattern must be changed in order to perform a set of end-game maneuvers that
allow to guarantee the detection of all smart evaders in the region.

In [19], we consider teams of agents that perform pincer sweep search
strategies with linear sensors, in order to detect all smart evaders that try
to escape from a given region. The paper presents two multi-agent pincer sweep
search strategies, circular and spiral, that can be applied with any even
number of sweeping agents. The results obtained from the paper show that
performing the circular pincer sweep process, where pairs of defenders sweep
toward each other allow for lower critical speeds and shorter sweep times
until the entire evader region is searched and cleared from evaders compared
to a circular sweep process in which the defenders are equally distributed
around the evader region and all sweep in the same direction. A circular sweep
process in which the searchers all rotate in the same direction is the
extension of [22] to a scenario where the defenders are distributed equally
around the region and perform the circular sweep protocol described in [22].
Therefore, defenders that rotate in the same direction have to perform an end-
game scenario similar to the one described in [22] in order to completely
clear the region from evaders, a set of maneuvers that is unnecessary when
using the circular pincer sweep protocol described in [19].

The second type of sweep pattern that is developed in [19] is the spiral
pincer sweep process that allows to complete the search of the evader region
in a significantly shorter time and at lower critical speeds compared to the
circular pincer sweep process. The critical speed of the spiral pincer sweep
process approaches the theoretical lower bound on the critical speed.

This work aims to solve the dual problem to the problem investigated in [22]
and [19], which is to protect a given initial region that does not contain
invaders from their entrance, and if possible to expand the protected region
to the maximal defendable size possible. The first task this work is concerned
with, the guarding task is analogous to the confinement task in [22, 19], in
the sense that it aims to keep the protected region’s radius constant after
the defenders complete a full sweep around the region. The maximal expansion
task, in which after each full sweep around the protected region, its radius
increases is the dual problem to the constriction of the evader region in [22,
19].

In contrast to the algorithms described in [22, 19] the defense process does
not terminate when the defenders expand the protected region to its maximal
size and they must continuously sweep around the region to keep the intruders
that are outside of the protected region from entering it. Additionally, this
work presents for each developed pincer sweep defense process the maximal
radius that the protected region can be extended into and presents an analysis
on the trade-off between approaching the maximal protected region’s radius and
the sweep time it takes to reach it. Alternatively to the barrier placement
problem in [7], our approach emphasizes the usage of cooperation between the
defenders by using pincer sweeps, calculates the maximal defendable region’s
size and presents analytical solutions to all aspects of the defense and
maximal expansion problems against smart invaders.

The research conducted in [8, 9, 10] also investigates protecting a region
from the entrance of invaders and uses pincer movements between pairs of
defenders as well. However, the goal of the defender team in these works is to
intercept the largest possible number of invaders contrary to our approach
which develops a defense protocol that ensures detection of all invaders,
regardless of their numbers, and consequently sets necessary requirements on
the defender team in order to achieve its goal. Furthermore, in [8, 9, 10],
the invaders’ locations are constantly known to the defenders hence this
information assists the defender team in planning and coordinating its
movements and its allocation of defender pairs. Conversely, our approach does
not assume any knowledge on the invaders’ locations or their number.

##  III A Universal Bound On Cleaning Rate

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

######  Theorem 1.

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

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

For proof see [22]. The desired outcome it that after the first sweep the
protected region is within a circle with a greater radius than the initial
protected region’s radius.

##  IV Circular Defense Pincer Sweep Process

At first, we study a scenario in which a multi-agent team comprising of $n$
agents, referred to as defenders, perform the defense task. The number of
defenders, $n$, is even, and all defenders are identical and are equipped with
a linear sensor with a length of $2r$. The initial defenders’ configuration at
the start of the defense protocol is such that each defender has half of its
linear sensor outside of the protected region, i.e. a length of $r$.

Figure 4: Swept areas and protected region status for different times in a
scenario where $4$ defenders perform the circular defense pincer sweep
process. (a) - Beginning of first sweep. (b) - Toward the end of the first
sweep. (c) - Beginning of second sweep. (d) - Midway of the third sweep. Green
areas show locations that were searched and hence do not contain invaders and
red areas indicate locations where potential invaders may be present. Blue
areas represent locations that belong to the initial protected region that
does not contain invaders.

###  IV-A The Defense Task and Critical Speed Analysis

Using pincer movements between adjacent pairs of defenders leverages the
symmetry between the trajectories of nearby defenders in order to impede the
entrance of invaders to the protected region from the most dangerous points
invaders can enter from (by using similar arguments to the proof provided in
([22]). Hence, the defenders’ critical speed is computed based on the time
required for a defender to scan the sector allocated for it, i.e. an angular
section of $\frac{2\pi}{n}$. In case the defenders’ speeds exceed the critical
speed required for successfully implementing the defense/guarding task, the
defenders can advance outwards together from the center of the protected
region after completing a sweep. A full sweep or iteration refers to a
defender’s scan of the sector of the protected region it guards spanning an
angle of $\frac{2\pi}{n}$. Hence, the scanned angle each defender guards is a
function of the participating defenders in the defense task. When defenders
perform the defense task, they change their scanning direction after the
completion of a full sweep.

######  Theorem 2.

The circular critical speed equals twice the optimal minimal critical speed,

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

###### Proof.

Every defender performing the circular defense pincer sweep process has a
sensor length of $r$ inside the protected region, to ensure no invader enters
the protected region without being detected by the defenders. Hence, in order
to catch all invaders, the spread from any potential location inside the
invader region (the region outside of the protected region where invaders
might be located), has to be restricted to a radius less than $r$ from its
origin point at the start of the defense protocol. Therefore, during an
angular traversal of $\frac{2\pi}{n}$ around a protected region with a radius
of $R_{0}$, this requirement implies that,

$\frac{{2\pi{R_{0}}}}{{n{V_{s}}}}\leq\frac{r}{{{V_{T}}}}$ (3)

Hence, in order to detect all invaders, the defenders’ speed has to exceed,

${V_{s}}\geq\frac{{2\pi{R_{0}}{V_{T}}}}{{nr}}$ (4)

The critical speed for the circular defense pincer sweep process is obtained
when (4) is satisfied with equality.

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

∎

The obtained result matches the observation that the circular critical speed
for defending a region against the entrance of smart invaders should equal the
critical speed required for confining smart evaders (developed in [19]) inside
a region having the same size.

###  IV-B The Maximal Expansion Task

####  IV-B1 Number of Sweeps Analysis

######  Theorem 3.

The maximal radius that $n$ circularly sweeping defenders, with a linear
sensor of length $2r$, a given speed $V_{s}$ and a maximal invader speed of
$V_{T}$ can safely protect against the entrance of invaders is,

${{\bar{R}}_{N_{c}}}=\frac{{n{V_{s}}r}}{{2\pi{V_{T}}}}$ (6)

######  Theorem 4.

For a defender team with $n$ defenders, for which $n$ is even, performing the
circular defense pincer sweep process, the number of sweeps required for the
defender team to expand the protected region to be bounded by a circle with a
radius that is $\varepsilon$ close to the maximal boundable radius
${{\bar{R}}_{N_{c}}}$ is,

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

Denote by ${T_{out}}$ the sum of all outward advancement times and by
${T_{circular}}$ the sum of all circular search times. Hence, the total search
time necessary for the defender team to expand the protected region to its
maximal size is given by,

$T(n)={T_{out}}(n)+{T_{circular}}(n)$ (8)

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

${T_{out}}(n)=\frac{{nr}}{{2\pi{V_{T}}}}-\frac{{{R_{0}}+\varepsilon}}{{{V_{s}}}}$
(9)

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

$\begin{array}[]{l}{T_{circular}}(n)=\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}-\frac{{rn\left({{V_{s}}+{V_{T}}}\right)}}{{2\pi{V_{T}}^{2}}}\\\
-{\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{V_{s}}}}{{{V_{s}}{V_{T}}}}}\right)\left({\frac{{{V_{s}}+{V_{T}}}}{{2\pi{V_{T}}}}}\right)+\frac{{{N_{n}}r}}{{{V_{T}}}}\end{array}$
(10)

###### Proof.

Denote by $\Delta V>0$ the excess speed of the defender above the critical
speed. Hence, the defender’s speed is $V_{s}=V_{c}+\Delta V$. The time
required for a defender to circularly sweep around its allocated section is,

${T_{circular}}_{i}=\frac{{2\pi{R_{i}}}}{{n({V_{c}}+\Delta V)}}$ (11)

Since $V_{s}=V_{c}+\Delta V$, ${T_{circular}}_{i}$ may also be expressed as,

${T_{circular}}_{i}=\frac{{2\pi{R_{i}}}}{{n{V_{s}}}}$ (12)

Depending on the number of participating defenders and the iteration number,
the distance a defender can advance outwards from the center of the protected
region after completing an iteration is,

${\delta_{i}}(\Delta V)=r-{V_{T}}{T_{circular}}_{i}\hskip 2.84526pt,\hskip
2.84526pt0\leq{\delta_{i}}(\Delta V)\leq r$ (13)

In the expression ${\delta_{i}}(\Delta V)$, $\Delta V$ is the excess speed of
a defender with respect to the critical speed. Denote by $i$ the number of
full sweeps defenders perform around the protected region, in which the first
sweep occurs when $i=0$. After completing a full sweep, the defenders move
outwards from the center of the protected region with the inner tips of their
sensors pointing to the center of the protected region. At times in which
defenders move outwards, they do so with a speed of $V_{s}$. This motion
continues up to the location in which the defenders begin their next sweep
once half of their sensor is inside the expanding wavefront of the invading
region. During the outward advancements no invaders are detected, while the
protected region continues to shrink.

The time it takes defenders to move outwards up to the point where half of
their sensors are outside of the protected region depends on the relative
speed between the defenders outward motion and the invader region’s inwards
expansion and is given by (15). As the defenders gradually head outward from
the center of the protected region, the protected region continuous to shrink.
Hence, in order for no invader to enter the region, defenders must advance
outwards to a lesser extent than ${\delta_{i}}(\Delta V)$. This quantity is
denoted by ${\delta_{{i_{eff}}}}(\Delta V)$, and depends on the ratio between
the speed in which defenders move outwards from the center of the protected
region and the sum of the defender and invader region spread speeds.
${\delta_{{i_{eff}}}}(\Delta V)$ is the actual distance defenders are allowed
to progress outwards after each sweep so that they meet the wavefront of the
expanding invader region at the point where half of their sensors are over the
invader region. Therefore, the distance a defender may advance outwards after
completing a sweep around the protected region is,

${\delta_{{i_{eff}}}}(\Delta V)={\delta_{i}}(\Delta
V)\left({\frac{{{V_{s}}}}{{{V_{s}}+{V_{T}}}}}\right)$ (14)

The outward advancement time depends on the iteration number. It is denoted by
$T_{out{{}_{i}}}$ and is expressed as,

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

The index $i$ in ${T_{out_{i}}}$ denotes the iteration number in which the
advancement takes place. After the defenders complete their sweep, the
protected region is bounded by a circle with a larger radius compared to the
previous sweep. Thus, the new radius of the circle bounding the protected
region is given by,

${R_{i+1}}={R_{i}}+{\delta_{{i_{eff}}}}(\Delta V)={R_{i}}+{\delta_{i}}(\Delta
V)\left({\frac{{{V_{s}}}}{{{V_{s}}+{V_{T}}}}}\right)$ (16)

Replacing the value of ${\delta_{i}}(\Delta V)$ from (13) into (16) results
in,

${R_{i+1}}={R_{i}}+{\delta_{{i_{eff}}}}(\Delta
V)={R_{i}}+\frac{{r{V_{s}}}}{{{V_{s}}+{V_{T}}}}-\frac{{2\pi{R_{i}}{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}$
(17)

Rearranging terms yields,

${R_{i+1}}={R_{i}}\left({1-\frac{{2\pi{V_{T}}}}{{n\left({{V_{s}}+{V_{T}}}\right)}}}\right)+\frac{{r{V_{s}}}}{{{V_{s}}+{V_{T}}}}$
(18)

Denote the coefficients $c_{1}$ and $c_{2}$ by,

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

Hence, (18) can be expressed as,

${R_{i+1}}={c_{2}}{R_{i}}+{c_{1}}$ (20)

Since the defenders need to move outwards from protecting a region with a
smaller radius, and during this outwards motion the protection region
continues to shrink, the defenders are able to protect a marginally smaller
region. The expansion task progresses by alternating circular sweeps and
outward movements until the protected region is bounded by the largest
possible circle. Let $\varepsilon>0$, and denote by
${\widehat{R}_{{N_{n}}-1}}$ the radius of the protected region that is
$\varepsilon$ close to ${{\bar{R}}_{N_{c}}}$,

$\widehat{R}{{}_{{N_{n}}-1}}=R_{max}=\frac{{n{V_{s}}r}}{{2\pi{V_{T}}}}-\varepsilon$
(21)

The number of iterations required for the defender team to expand the
protected region to be bounded by a circle with a radius of
$\widehat{R}{{}_{{N_{n}}-1}}$ that is $\varepsilon$ close to
${{\bar{R}}_{N_{c}}}$ is calculated by similar steps as the calculation in
Appendix $A$ of [19]. It is given by,

$N_{n}=\left\lceil\frac{1}{\ln{c_{2}}}\ln\left({\frac{{\widehat{R}{{}_{{N_{n}}-1}}-\frac{{{c_{1}}}}{{1-{c_{2}}}}}}{{{R_{0}}-\frac{{{c_{1}}}}{{1-{c_{2}}}}}}}\right)\right\rceil$
(22)

The radius $R_{max}=\widehat{R}{{}_{{N_{n}}-1}}$ is the maximal radius the
protected region expands to, and is used to calculate the number of sweeps
required to reach this radius. The actual radius that bounds the protected
region after $N_{n}$ sweeps is denoted by ${R}{{}_{{N_{n}}-1}}$ and is
computed after $N_{n}$ is calculated. Replacing the coefficients in (22)
yields that the number of sweeps required for the defenders to increase the
protected region to be in a circle with the radius of the last sweep around
the region, ${R_{{N_{n}}-1}}$, is,

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

To determine the number of required sweeps, the ceiling operator is used in
order to implicitly demand that the number of iterations is an integer number,
thus causing defenders to complete their sweep cycle and meet the defender
that searches the adjacent section. This leads defenders to finish sweep
$N_{n}-1$, even when the protected region’s radius is somewhat larger than
${\widehat{R}_{{N_{n}}-1}}$.

After completing the last circular sweep, defenders perform the last outward
advancement, and defenders continue to circularly patrol around a protected
region with a radius of $R_{max}$ indefinitely. The total search time required
for a defender team of $n$ defenders to enlarge the protected region to its
maximal size is obtained by combining the total outward advancement times
together with the total circular sweep times around the protected region in
all iterations. Denote by ${T_{out}}(n)$ the sum of all the outward
advancement times and by ${T_{circular}}(n)$ the sum of all circular sweep
times. Hence,

$T(n)={T_{out}}(n)+{T_{circular}}(n)$ (24)

####  IV-B2 Outward Advancement Times Calculation

Denote the total outward advancement times until the protected region is
within a circle of radius ${R_{N-1}}$ as $\widetilde{T}_{out}(n)$. This time
is calculated by,

$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}}$ (25)

Throughout the outward advancements phases the defenders do not perform
sweeping and detection of invaders and hence invaders are not detected until
the defenders finish their outwards motion and resume the sweeping of the
protected region. Following a defender’s completion of the outwards
progression phase, its sensor overlaps both the invader region and the
protected region by $r$.

Substituting ${T_{ou{t_{i}}}}$ in (25) yields that the accumulation of outward
advancement times prior to the protected region being within a circle of
radius ${R_{N-1}}$ can be calculated as follows,

$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}=}\frac{{\left({{N_{n}}-1}\right)r}}{{{V_{s}}+{V_{T}}}}-\frac{{2\pi{V_{T}}\sum\limits_{i=0}^{{N_{n}}-2}{{R_{i}}}}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}$
(26)

The first outward advancement takes place after the protected region is within
a circle of radius $R_{0}$ and the final outward advancement occurs after
iteration number ${N_{n}}-2$, causing the protected region to expand from
being inside a circle of radius ${R_{{N_{n}}-2}}$ to being within a circle of
radius ${R_{{N_{n}}-1}}$. Following this motion, the defender team circularly
sweeps around the protected region with a radius of ${R_{{N_{n}}-1}}$.
${R_{{N_{n}}-1}}$ that is calculated using the recursive relation in (20) and
is given by,

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

Substitution of coefficients in (27) yields,

$\begin{array}[]{l}{R_{{N_{n}}-1}}=\frac{{n{V_{s}}r}}{{2\pi{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}}-n{V_{s}}r}}{{2\pi{V_{T}}}}}\right)\end{array}$
(28)

The full derivation of $\widetilde{T}_{out}(n)$ is continued in Appendix $A$.
Hence,

$\begin{array}[]{l}\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}}=\\\
-\frac{{{R_{0}}}}{{{V_{s}}}}+\frac{{nr}}{{2\pi{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}}-n{V_{s}}r}}{{2\pi{V_{T}}{V_{s}}}}}\right)\end{array}$
(29)

Following the last circular sweep the defenders perform the last outward
advancement, until reaching $R_{max}$. The time it takes the defenders to
perform this last outward advancement is given by,

$T_{out_{last}}=\frac{\left(\widehat{R}{{}_{{N_{n}}-1}}-{R_{{N_{n}}-1}}\right)}{V_{s}}$
(30)

After this last outward sweep, the defenders perform circular sweeps around a
protected region of radius $R_{max}$ and continuously protect the region from
the entrance of invaders after reaching the maximal protected region the
defenders can guard. Summing $\widetilde{T}_{out}(n)$ and the last outward
advancement time in (30) yields,

${T_{out}}(n)=\frac{{nr}}{{2\pi{V_{T}}}}-\frac{{{R_{0}}+\varepsilon}}{{{V_{s}}}}$
(31)

####  IV-B3 Circular Sweep Times Calculation

The time to complete the first circular sweep is
${T_{0}}=\frac{{2\pi{R_{0}}}}{{n{V_{s}}}}$. Similarly, the time it takes to
perform a circular motion spanning an angular section of $\frac{2\pi}{n}$
around a circle of radius $R_{i}$ while moving with a speed of $V_{s}$ is,

${T_{i}}=\frac{{2\pi{R_{i}}}}{{n{V_{s}}}}$ (32)

Denote the coefficient $c_{3}$ by,

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

It can be noted that by multiplying (20) by $\frac{2\pi}{n{V_{s}}}$ one
obtains a recursive difference equation that cab be utilized to calculate the
circular sweep times. Therefore the sweep times can be written as,

$T_{i+1}=c_{2}{T_{i}}+c_{3}$ (34)

Denote by $T_{circular}(n)$ the total circular sweep times required to expand
the protected region to be within a circle having a radius equal to or greater
than ${\widehat{R}_{N-1}}$. The calculation of $T_{circular}(n)$ follows
similar steps as in appendix $C$ of [19]. Hence,

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

The calculation of the last circular sweep time prior to the protected region
being within a circle having a radius greater than or equal to
${\widehat{R}_{N-1}}$ follows similar steps as in appendix $D$ of [19]. Hence,

${T_{{N_{n}}-1}}=\frac{{{c_{3}}}}{{1-{c_{2}}}}+{{c_{2}}^{{N_{n}}-1}}\left({{T_{0}}-\frac{{{c_{3}}}}{{1-{c_{2}}}}}\right)$
(36)

Substitution of coefficients in (36) results in,

$\begin{array}[]{l}{T_{N-1}}=\frac{r}{{{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{V_{s}}}}{{n{V_{s}}{V_{T}}}}}\right)\end{array}$
(37)

Therefore, the total circular sweep times from (35) are,

$\begin{array}[]{l}T_{circular}(n)=\frac{{{R_{0}}\left({{V_{s}}+{V_{T}}}\right)}}{{{V_{s}}{V_{T}}}}-\frac{{rn\left({{V_{s}}+{V_{T}}}\right)}}{{2\pi{V_{T}}^{2}}}\\\
-{\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{V_{s}}}}{{{V_{s}}{V_{T}}}}}\right)\left({\frac{{{V_{s}}+{V_{T}}}}{{2\pi{V_{T}}}}}\right)+\frac{{{N_{n}}r}}{{{V_{T}}}}\end{array}$
(38)

Subsequently to the completion of sweep $N_{n}$ the protected region is within
a circle of ${R_{{N_{n}}-1}}$. ∎

####  IV-B4 Numerical Experiments

Fig. $5$ presents the maximal protected region’s radius that the defenders are
able to protect. The maximal radius clearly depends on the number of defenders
and their speed. Fig. $6$ presents the number of sweeps required to expand the
protected region to its maximal size as a function of $\varepsilon$. Fig. $7$
presents the expansion time of the protected region to $R_{N_{c}}-\varepsilon$
for a fixed speed exceeding the circular critical speed. Fig. $8$ presents the
total search times for different numbers of defenders until maximal expansion
of the protected region is achieved. In all presented graphs the defenders’
speed is equal and is independent of the number of defenders performing the
expansion protocols, and is chosen so that search times of defender teams with
different number of defenders are correctly compared. The values of $\Delta V$
mentioned in the plots are speeds exceeding the critical speed of two
defenders employing the circular defense pincer sweep process, due to the fact
that as the number of defenders increases, the critical speed required for
successfully performing the defense task decreases. Hence, defender teams with
more defenders can achieve their goal of defending the region while moving at
speeds exceeding the critical speed of two defenders, while the contrary
argument is false. The second plot from the top of Fig. $8$. presents the
search time reduction obtained when the number of participating defenders
increases.

Figure 5: Maximal protected region’s radius. We simulated circular defense
sweep processes with an even number of agents, ranging from $2$ to $32$
agents. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$\varepsilon=0.2$. Figure 6: Number of sweeps required to expand the protected
region to its maximal size as a function of $\varepsilon$. We plot the results
for defenders performing the circular defense pincer sweep processes with
$2,8,16$ and $32$ agents. The chosen values of the parameters are $r=10$,
$V_{T}=1$, $V_{s}=31.9159$. Figure 7: Time of maximal expansion of the
protected region to $R_{N_{c}}-\varepsilon$ and gain in adding more defenders
for equal defender speeds. We simulated the circular defense pincer sweep
processes for an even number of agents, ranging from $2$ to $32$ agents. The
chosen values of the parameters are $r=10$, $V_{T}=1$, $\Delta V=10$ and
$R_{max}=120$. Figure 8: Time of maximal expansion of the protected region and
gain in adding more defenders for different defender speeds. We simulated the
circular defense pincer sweep processes for an even number of agents, ranging
from $2$ to $32$ agents. The chosen values of the parameters are $r=10$,
$V_{T}=1$ and $R_{max}=120$.

##  V Spiral Defense Pincer Sweep Process

In order to handle the inherent inefficiency of the circular defense pincer
sweep protocol, which first and foremost results from the fact that at the
beginning of each sweep only half the length of the defenders’ sensors are
inside the invader region, we propose a modification to the defense process
that tackles this inefficiency. This modification strives to increase the part
of the defenders’ sensors over the invader region so that they can detect
invaders further away from the protected region. Therefore, a spiral scan in
which the tip of a defender’s sensor follows the expanding protected region’s
boundaries is proposed.

Figure 9: Swept areas and protected region’s status for different times in a
scenario where $2$ defenders perform the spiral defense pincer sweep process.
(a) - Beginning of first sweep. (b) - Midway of the second sweep. (c) -
Beginning of the second sweep. (d) - End of the second sweep. Green areas show
locations that were searched and hence do not contain invaders and red areas
indicate locations where potential invaders may be present. Blue areas
represent locations that belong to the initial protected region that does not
contain invaders.

###  V-A The Defense Task and Critical Speed Analysis

At the beginning of the defense protocol, each defender’s sensor overlaps the
protected region by $0$ (and consequently a length of is $2r$ over the
complementing invader region). Sweeping in a pincer movement enables defenders
to have a critical speed that is based only upon the time it takes them to
traverse their allocated angular section of $\frac{2\pi}{n}$. In a similar
manner as in the circular defense pincer sweep process, defenders sweeping at
greater speeds than the corresponding critical speed of the scenario, switch
their search direction once they finish their outward advancement phase. At
the next iteration defenders sweep around a section having a larger radius.

Defenders’ begin their spiral motion with their sensors’ tips tangent to the
boundary of the protected region. To keep their sensors tangent to the
protected region during the spiral sweeping phases, defenders move at an angle
$\phi$ with respect to the normal of the protected region. $\phi$ depends on
the ratio between defender and invader speeds. Moving by a constant angle
$\phi$ with respect to the normal of the protected region allows to preserve
the protected region’s circular shape and to keep the entire length of the
defenders’ sensors outside of the protected region, thus enabling detection of
invaders at greater distances from the boundary of the protected region. Fig.
$1$ (b) depicts the starting locations of $2$ defenders performing the spiral
defense pincer sweep process. Fig. $9$ shows the cleaning progress during the
expansion of the protected region when $2$ defenders employ the spiral defense
pincer sweep protocol. $\phi$ is given by,

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

Hence, $\phi=\arcsin\left({\frac{{{V_{T}}}}{{{V_{s}}}}}\right)$. The
defender’s angular speed or rate of change of its angle with respect to the
center of the protected region, $\theta_{s}$, can be expressed by the
following function of $\phi$,

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

Integration of (40) between the initial and final search times of a particular
sweep leads to,

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

Solving for $\theta\left({{t_{\theta}}}\right)$ from (41) results in,

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

Applying the exponent function to (42) yields,

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

The time required for a defender to complete a spiral scan of the angular
section under its responsibility corresponds to changing its angle $\theta$ by
$\frac{2\pi}{n}$. The expansion of the invading region at this time must be
less than or equal to $2r$, so that defenders will still be able to prevent
the entrance of invaders to the protected region. Since during the defenders’
outwards movements invaders may continue to progress toward the protected
region, defenders’ can only move outwards by a somewhat smaller distance to
address this concern. If we were to neglect invaders’ motion during the
outward movement phases, the necessary requirement to ensure invaders cannot
enter the protected region without being detected by the defenders is,

${R_{0}}-r\leq{R_{s}}({t_{\frac{2\pi}{n}}})$ (44)

Define,

$\lambda={e^{-\frac{{2\pi{V_{T}}}}{{n\sqrt{{V_{s}}^{2}-{V_{T}}^{2}}}}}}$ (45)

Replacing ${R_{s}}({t_{\frac{2\pi}{n}}})$ with the expression for the
defender’s trajectory results in,

${R_{0}}-r\leq\left({{R_{0}}+r}\right)\lambda$ (46)

Hence, to guarantee invaders cannot enter the protected region throughout the
spiral scans without being detected, the defenders’ speeds has to satisfy,

${V_{S}}\geq{V_{T}}\sqrt{\frac{{{{\left({\frac{{2\pi}}{n}}\right)}^{2}}}}{{{{\left({\ln\left({\frac{{{R_{0}}+r}}{{{R_{0}}-r}}}\right)}\right)}^{2}}}}+1}$
(47)

In order to consider the progression of invaders toward the protected region
and modify the critical speed in (47) to cope with this motion, defenders move
outward from the protected region after completing a spiral sweep until
meeting the invader region’s wavefront travelling towards them with a speed of
$V_{T}$ at the previous radius $R_{0}$. This consideration guarantees that all
invaders are detected and that the critical speed of the spiral defense pincer
sweep protocol is nearly equal to the optimal lower bound on the defender
speed of Theorem $1$. Denote the expansion of the invader region in the first
sweep by ${T_{c}}$. In order to ensure no invaders enter the region without
being detected the following inequality must hold,
${V_{T}}{T_{c}}\leq\frac{{2r{V_{s}}}}{{{V_{s}}+{V_{T}}}}$. Replacing the
expression for ${T_{c}}$ yields,

$\left({{R_{0}}+r}\right)\left(1-\lambda\right)\leq\frac{{2r{V_{s}}}}{{{V_{s}}+{V_{T}}}}$
(48)

######  Theorem 5.

In the spiral defense pincer sweep process, the critical speed ,${V_{s}}$,
enabling to successfully complete the defense task is obtained as the solution
of,

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

Where ${T_{c}}$ equals,

${T_{c}}=\frac{{\left({{R_{0}}+r}\right)\left(1-\lambda\right)}}{{{V_{T}}}}$
(50)

The critical speed required to successfully perform the spiral defense pincer
sweep strategy is computed by solving numerically the equation in Theorem $5$
with the Newton–Raphson method while using the critical speed in (47) as an
initial guess. This speed, that guarantees all invaders are detected, is used
in all further calculations of this section.

As shown in Fig. $10$. the spiral critical speed nearly equals the optimal
lower bound, specifically for a small number of defenders. For example, when
$2$ defenders perform the defense protocol the ratio between the spiral
critical speed and the optimal lower bound on the speed is $1.06$.

Figure 10: Critical speeds as a function of the number of defenders. The
number of defenders is even, and ranges from $2$ to $32$ defenders, that
perform the spiral defense pincer sweep protocol. The optimal lower bound on
the critical speeds and the resulting critical speeds of the circular defense
pincer sweep protocol are presented for comparison as well. The chosen values
of the parameters are $r=10$, $V_{T}=1$ and $R_{0}=100$.

###  V-B The Maximal Expansion Task

####  V-B1 Number of Sweeps Analysis

######  Theorem 6.

The maximal radius that $n$ spiral sweeping defenders, with a linear sensor of
length $2r$, a given speed $V_{s}$ and a maximal invader speed of $V_{T}$ can
safely protect against the entrance of invaders is,

${\bar{R}_{{N_{s}}}}=\frac{{2r}}{{{1-\lambda}}}-r$ (51)

######  Theorem 7.

For a defender team with $n$ defenders for which $n$ is even, performing the
spiral defense pincer sweep process, the number of sweeps required for the
defender team to expand the protected region to a circle with a radius that is
$\varepsilon$ close to the maximal boundable radius ${{\bar{R}}_{N_{s}}}$ is
given by,

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

Denote by ${T_{out}}(n)$ the sum of all outward advancement times and by
${T_{spiral}}(n)$ the sum of all the spiral search times. Hence, the total
search time necessary for the defender team to expand the protected region to
its maximal size is given by,

$T(n)={T_{out}}(n)+{T_{spiral}}(n)$ (53)

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

${T_{out}}(n)=\frac{{\lambda\left({{R_{0}}+r+\varepsilon}\right)+r-{R_{0}}-\varepsilon}}{{{V_{s}}\left({1-\lambda}\right)}}$
(54)

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

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

###### Proof.

Denote by $\Delta V>0$ the excess speed of the defender above the critical
speed. Hence, the defender’s speed is, $V_{s}=V_{c}+\Delta V$. At the start of
each sweep the center of the defender’s sensor is at a distance of ${R_{i}}+r$
from the protected region’s center. $\theta\left({{t_{\theta}}}\right)$ is
calculated in (42). Substituting $R_{0}$ with $R_{i}$ results in,

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

Denote the time required for a defender to complete the search of an angular
section of $\theta\left({{t_{\theta}}}\right)=\frac{2\pi}{n}$ by
${T_{spiral}}_{i}$. It is obtained from (56) and equals,

${T_{spiral}}_{{}_{i}}=\frac{{\left({{R_{i}}+r}\right)\left({1-\lambda}\right)}}{{{V_{T}}}}$
(57)

If defenders move with speeds greater than the critical speed required for the
scenario, the distance a defender may advance outward from the center of the
protected region is ${\delta_{i}}(\Delta V)$,

${\delta_{i}}(\Delta V)=2r-{V_{T}}{T_{spiral}}_{i}\hskip 2.84526pt,\hskip
2.84526pt0\leq{\delta_{i}}(\Delta V)\leq 2r$ (58)

Once defenders finish the outward advancement phase, the protected region
expands to an updated circular protected region with a radius of
${R_{i+1}}={R_{i}}+{\delta_{i}}(\Delta V)$. At the end of the spiral maneuver
the protected region is again circular, with a larger radius. The proof for
this property follows similar steps as provided in Appendix $H$ of [19].

Depending on the number of participating defenders and the iteration number,
the distance a defender can advance outwards after completing a sweep is,

${\delta_{i}}(\Delta V)=2r-\left({{R}_{i}+r}\right)\left({1-\lambda}\right)$
(59)

Where in the term ${\delta_{i}}(\Delta V)$, $\Delta V$ denotes the increase in
the agent’s speed relative to the critical speed. The number of sweep
iterations the defenders performed around the protected region is denoted by
$i$, where $i$ starts from sweep number $0$.

Since during the time in which defenders move outwards from the protected
region, invaders continue to advance towards it, defenders can advance
outwards by a slightly lesser distance than ${\delta_{i}}(\Delta V)$. The time
required for defenders to move outwards until their entire sensors are outside
of the protected region depends on the relative speed between the defenders’
outward speed and the invader region’s inwards expansion speed. Therefore,
defenders are able to advance outwards by,

${\delta_{{i_{eff}}}}(\Delta V)={\delta_{i}}(\Delta
V)\left({\frac{{{V_{s}}}}{{{V_{s}}+{V_{T}}}}}\right)$ (60)

Hence, the radius of the expanded circular protected region is,

${R_{i+1}}={R_{i}}+{\delta_{i}}(\Delta
V)\left({\frac{{{V_{s}}}}{{{V_{s}}+{V_{T}}}}}\right)$ (61)

Denote $\widetilde{R}_{i}=R_{i}+r$. Replacing $R_{i}$ with $\widetilde{R}_{i}$
results in a similar structure of formulas as in the circular defense pincer
sweep process and enables to use the same methodology along with the
appropriate change of coefficients to solve for the maximal defendable radius
of the protected region. Replacing the expression for ${{\delta_{i}}(\Delta
V)}$ into (61) yields,

${{\tilde{R}}_{i+1}}={{\tilde{R}}_{i}}+\left({2r-{{\tilde{R}}_{i}}\left({1-\lambda}\right)}\right)\frac{{{V_{s}}}}{{{V_{s}}+{V_{T}}}}$
(62)

Rearranging terms results in a difference equation that resembles the equation
obtained for the circular defense pincer sweep process,

${{\tilde{R}}_{i+1}}={{\tilde{R}}_{i}}\left({\frac{{{V_{T}}+{V_{s}}\lambda}}{{{V_{s}}+{V_{T}}}}}\right)+\frac{{2r{V_{s}}}}{{{V_{s}}+{V_{T}}}}$
(63)

Denote the coefficients in (63) by,

${c_{1}}=\frac{{2r{V_{s}}}}{{{V_{s}}+{V_{T}}}},{c_{2}}=\frac{{{V_{T}}+{V_{s}}\lambda}}{{{V_{s}}+{V_{T}}}}$
(64)

Hence, (63) is expressed as,

$\widetilde{R}_{i+1}={c_{2}}\widetilde{R}_{i}+{c_{1}}$ (65)

Since the defenders need to move outwards from protecting a region with a
smaller radius, and during this outwards movement the protected region
continues to shrink due to possible movements of invaders, the defenders can
protect a slightly smaller region. For any even number of defenders, $n$, the
expansion protocol continues in this way until the protected region is
enlarged to the largest possible circle. Let $\varepsilon>0$ and denote by
${\widehat{R}_{{N_{n}}-1}}$ the radius of the protected region that is
$\varepsilon$ close to ${{\bar{R}}_{N_{s}}}$,

$\widehat{R}{{}_{{N_{n}}-1}}=R_{max}=\frac{{2r}}{{1-\lambda}}-r-\varepsilon$
(66)

Due to the same difference equation structure as in the circular defense
pincer sweep protocol, the number of spiral sweeps is calculated similarly.
Hence, the number of iterations required for the defender team to expand the
protected region to a circle of radius $\widehat{R}{{}_{{N_{n}}-1}}$ is,

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

The radius $R_{max}=\widehat{R}{{}_{{N_{n}}-1}}$ is the maximal radius the
protected region expands to, and is used to calculate the number of sweeps
required to reach this radius. The actual radius of the protected region after
$N_{n}$ sweeps is denoted by ${R}{{}_{{N_{n}}-1}}$ and is computed after
$N_{n}$ is calculated. After the last spiral sweep, the defenders perform the
last outward advancement, and the defenders continue to perform spiral sweeps
around a protected region with a radius of $R_{max}$.

####  V-B2 Outward Advancement Times Calculation

The outward advancement time depends on the iteration number. It is denoted by
${T_{ou{t_{i}}}}$ and is expressed as,

${T_{ou{t_{i}}}}=\frac{{{\delta_{{i_{eff}}}}(\Delta
V)}}{{{V_{s}}}}=\frac{{2r-{{\tilde{R}}_{i}}\left({1-\lambda}\right)}}{{{V_{s}}+{V_{T}}}}$
(68)

Denote the total outward advancement times until the protected region is
enlarged to a circle of radius ${R}{{}_{{N_{n}}-1}}$ by $\widetilde{T}_{out}$,
where $\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{T_{ou{t_{i}}}}$.

Throughout the outward advancement phases the defenders do not perform
sweeping and detection of invaders and hence invaders are not detected until
the defenders finish their outwards motion and resume the sweeping of the
protected region. Following a defender’s completion of the outwards
progression phase, its sensor overlaps the invader region $2r$ (and therefore
the footprint of its sensor that is over the protected region is $0$). The
total search time until the protected region is expanded into a circle of
radius ${R}{{}_{{N_{n}}-1}}$ is given by the sum of the total spiral and
outward advancement sweep times. Hence,

$T(n)=\widetilde{T}_{out}(n)+T_{spiral}(n)$ (69)

Replacing the expression for ${T_{ou{t_{i}}}}$ yields that the accumulative
outward advancement times before the protected region is enlarged to its
maximal size are,

$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}=}\frac{{2r\left({{N_{n}}-1}\right)}}{{{V_{s}}+{V_{T}}}}-\frac{{\left({1-\lambda}\right)\sum\limits_{i=0}^{{N_{n}}-2}{{{\tilde{R}}_{i}}}}}{{{V_{s}}+{V_{T}}}}$
(70)

The full derivation of
$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}}$ is
continued in Appendix $B$. Hence,

$\begin{array}[]{l}\widetilde{T}_{out}(n)=\frac{{2r}}{{{V_{s}}+{V_{T}}}}-\frac{{{{\tilde{R}}_{0}}}}{{{V_{s}}}}+\frac{{2r\left({{V_{T}}+{V_{s}}\lambda}\right)}}{{{V_{s}}\left({{V_{s}}+{V_{T}}}\right)\left({1-\lambda}\right)}}+\\\
{\left({\frac{{{V_{T}}+{V_{s}}\lambda}}{{{V_{s}}+{V_{T}}}}}\right)^{{N_{n}}-1}}\left({\frac{{{{\tilde{R}}_{0}}}}{{{V_{s}}}}-\frac{{2r}}{{{V_{s}}\left({1-\lambda}\right)}}}\right)\end{array}$
(71)

${R}{{}_{{N_{n}}-1}}$ is computed by the same methodology as in the circular
defense sweep process section and is given by,

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

Following the last spiral sweep, the defenders perform the last outward
advancement, until reaching $R_{max}$. The time it takes them to perform this
last outward advancement is,

$T_{out_{last}}=\frac{\left(\widehat{R}{{}_{{N_{n}}-1}}-{R_{{N_{n}}-1}}\right)}{V_{s}}$
(73)

After this last outward sweep, the defenders perform spiral sweeps around a
protected region of radius $R_{max}$ and continuously protect the region from
the entrance of invaders after reaching the maximal protected region they can
guard. Summing $\widetilde{T}_{out}(n)$ and the last outward advancement time
in (73) yields,

${T_{out}}(n)=\frac{{\lambda\left({{R_{0}}+r+\varepsilon}\right)+r-{R_{0}}-\varepsilon}}{{{V_{s}}\left({1-\lambda}\right)}}$
(74)

####  V-B3 Spiral Sweep Times Calculation

The time to perform a spiral sweep around radius $\widetilde{R}_{i}$ is
calculated by multiplying $\widetilde{R}_{i}$ with $\frac{1-\lambda}{V_{T}}$.
Therefore, by multiplying (63) with $\frac{1-\lambda}{V_{T}}$ the following
difference equation for the sweep spiral times is,

${T_{i+1}}={c_{2}}{T_{i}}+{c_{3}}$ (75)

Where the coefficient $c_{3}$ is,

${c_{3}}=\frac{{2r{V_{s}}\left({1-\lambda}\right)}}{{\left({{V_{s}}+{V_{T}}}\right){V_{T}}}}$
(76)

The total spiral sweep times required to expand the protected region into its
largest size are calculated by similar steps as the circular sweep times in
the previous section. Hence,

$T_{spiral}(n)=\frac{{{T_{0}}-{c_{2}}{T_{N_{n}-1}}+\left({{N_{n}}-1}\right){c_{3}}}}{{1-{c_{2}}}}$
(77)

The time required for defenders to perform the first spiral sweep is,

${T_{0}}=\frac{{\left({{R_{0}}+r}\right)\left({1-\lambda}\right)}}{{{V_{T}}}}$
(78)

The time to perform the last spiral sweep before the protected region reaches
its maximal radius of ${R}{{}_{{N_{n}}-1}}$ is given by,

${T_{N_{n}-1}}=\frac{{{c_{3}}}}{{1-{c_{2}}}}+{{c_{2}}^{{N_{n}}-1}}\left({{T_{0}}-\frac{{{c_{3}}}}{{1-{c_{2}}}}}\right)$
(79)

Substitution of coefficients results in,

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

Yielding that the total spiral sweep times are,

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

∎

####  V-B4 Numerical Experiments

Fig. $11$ presents the maximal protected region’s radius that the defenders
are able to protect. The maximal radius clearly depends on the number of
defenders and their speeds. Fig. $12$ presents the number of sweeps required
to expand the protected region to its maximal size as a function of
$\varepsilon$. Fig. $13$ presents the expansion time of the protected region
to $R_{N_{s}}-\varepsilon$ for a fixed speed exceeding the spiral critical
speed of $2$ defenders that perform the spiral defense pincer sweep protocol.
Fig. $14$ presents the total search times for different numbers of defenders.
In all presented graphs the defenders’ speed is equal and is independent of
the number of defenders performing the expansion protocol, and is chosen so
that search times of defender teams with different number of defenders are
correctly compared. The values of $\Delta V$ mentioned in the plots are speeds
above the critical speed of two defenders employing the spiral defense pincer
sweep process. The second plot from the top of Fig. $14$. presents the search
time reduction obtained when the number of participating defenders increases.
The critical speed required for the defender team to perform the defense task
is determined by solving numerically the equation presented in Theorem $5$,
consequently ensuring invaders cannot enter the protected region undetected.

Figure 11: Maximal protected region’s radius. The spiral defense pincer sweep
processes were simulated with an even number of defenders, ranging from $2$ to
$32$ defenders. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$\varepsilon=0.2$. Figure 12: Number of sweeps required to expand the
protected region to its maximal size as a function of $\varepsilon$. We plot
the results for defenders performing the spiral defense pincer sweep processes
with $2,8,16$ and $32$ defenders. The chosen values of the parameters are
$r=10$, $V_{T}=1$, $V_{s}=17.2219$. Figure 13: Time of maximal expansion of
the protected region to $R_{N_{s}}-\varepsilon$ and gain in adding more
defenders for equal defender speeds. We simulated the spiral defense pincer
sweep processes for an even number of defenders, ranging from $2$ to $32$
defenders. The chosen values of the parameters are $r=10$, $V_{T}=1$, $\Delta
V=10$ and $R_{max}=150$. Figure 14: Time of maximal expansion of the protected
region and gain in adding more defenders for different defender speeds. We
simulated the spiral defense pincer sweep processes for an even number of
defenders, ranging from $2$ to $32$ defenders. The chosen values of the
parameters are $r=10$, $V_{T}=1$ and $R_{max}=150$.

##  VI Comparative Analysis Between Circular and Spiral Defense Pincer Sweep
Strategies

The purpose of this section is to compare between the attained results for the
circular and spiral defense pincer sweep processes using the relevant
performance metrics. These metrics constitute the minimal defender speed
required for successful defense of the initial protected region, the time to
expand the protected region to the maximal defendable area and the maximal
feasible protected region’s radius resulting from the defense protocol. To
accurately compare between the total search times of defender swarms that can
perform both the circular and spiral defense pincer sweep processes, the
number of defenders as well as the defenders’ speed has to be equal in the
compared circular and spiral defender swarms.

Defenders performing the circular defense pincer sweep process require a
higher critical speed compared to defenders performing the the spiral defense
pincer sweep process. Therefore, Fig. $15$ presents the maximal protected
region’s radius that the defender team is able to expand the region into, when
defenders employ the spiral defense pincer sweep process. The results are
obtained for different speeds above the circular critical speed. The resulting
maximal radius is clearly larger compared to the maximal protected region’s
radius that is achieved with a defender team that employs the circular defense
pincer sweep process in Fig. $5$.

Fig. $16$ shows the spiral defense pincer sweep process’s total search times
obtained for different speeds above the circular critical speed of $2$
defenders. This implies that values of $\Delta V$ shown in the plots
correspond to defender speeds that equal nearly twice the spiral critical
speeds. Requiring a higher critical speed means defender teams performing the
circular defense pincer sweep process can expand the protected region to a
smaller area compared to a defender team with the same capabilities performing
the spiral protocol.

Fig. $17$ compares the search times until the maximal expansion of the
protected region is obtained and the gain in adding more defenders for
circular sweeping swarms and spiral sweeping swarms. The results are computed
with the same defender speeds for both the circular and spiral defense pincer
sweep processes. The reduction in total search time achieved when defenders
perform the spiral defense pincer sweep process are clearly noticeable. This
result holds regardless to the number of defenders that perform the defense
protocols or to their speeds.

Figure 15: Maximal protected region’s radius. We simulated the spiral sweep
protocols with an even number of defenders, ranging from $2$ to $32$
defenders. We show results obtained for different values of speeds above the
critical speed of $2$ defenders that employ the circular defense pincer sweep
process. The chosen values of the parameters are $r=10$, $V_{T}=1$ and
$\varepsilon=0.2$. Figure 16: Time of maximal expansion of the protected
region and gain in adding more defenders for different defender speeds above
the critical speed of $2$ defenders employing the circular defense pincer
sweep process. We simulated the spiral pincer sweep protocols for an even
number of defenders, ranging from $2$ to $32$ defenders. The chosen values of
the parameters are $r=10$, $V_{T}=1$ and $R_{max}=120$. Figure 17: Time of
maximal expansion of the protected region and gain in adding more defenders
for the circular and spiral defense sweep protocols. We simulated sweep
protocols with an even number of defenders, ranging from $2$ to $32$
defenders, that perform the circular and spiral defense pincer sweep protocols
at speeds above the critical speed of $2$ defenders that perform the circular
defense pincer sweep process. The chosen values of the parameters are $r=10$,
$V_{T}=1$ and $R_{max}=120$.

##  VII Comparison to State-of-the-Art Same-Direction Defense Strategies

The purpose of this section is to compare the developed circular and spiral
pincer sweep guarding and expansion strategies to prevalent approaches for
defense against smart invaders which are considered as the state-of-the-art in
defense against smart invaders. Such approaches usually distribute the
defending agents equally around the protected region and require that all
defenders move in the same-direction. Such an approach is presented in [7],
although the authors are interested only on solving the defense task and do
not provide explicit expansion protocols that allow to achieve a maximal
protected region or a detailed analytical analysis of sweep times. Hence, we
develop two alternative same-direction defense protocols, circular and spiral,
that enable the comparison of pincer-based and same-direction defense
protocols against smart invaders.

We provide a quantitative comparison between the discussed $3$ metrics:
critical speeds, maximal defendable area and the time required to reach
maximal expansion. Circular and spiral defense pincer sweep protocols and
circular and spiral defense same-direction sweep protocols are compared,
proving the superiority of pincer-based approaches across all $3$ metrics. We
prove that the corresponding pincer-based protocols yield lower critical
speeds, shorter time to increase the protected region to its maximal size as
well as the ability to expand the protected region to a larger area compared
to same-direction protocols.

These results are expected since defenders implementing same-direction
protocols need to scan additional angular portions of the environment in each
sweep around the region, to ensure no invader enters the protected region
undetected. However, in pincer-based defense protocols, scanning such
additional sectors is not required as a result of the complementary
trajectories implemented by the defenders.

The critical speed necessary for defenders that perform the same-direction
circular or spiral defense sweep protocols is higher compared to the minimal
critical speed of their pincer-based counterparts. This can be observed in
Fig. $18$. The same-direction defense protocols are developed by using similar
considerations as the same-direction protocols in [20]. These considerations
lead to a same-direction circular protocol speed that equals,

${V_{{c_{circ\\_same}}}}=\frac{{2\pi{R_{0}}{V_{T}}}}{{nr}}+{V_{T}}$ (82)

The solution for the spiral same-direction defense protocol critical speed is
solved numerically using the Newton–Raphson method from the equation below
while using the spiral pincer-based critical speed as an initial guess.

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

The angle $\beta_{0}$ denotes an additional angular sector that needs to be
guarded in addition to the $\frac{2\pi}{n}$ angular sector that is swept when
performing the spiral defense pincer protocols. $\beta_{0}$ is given by,

${\beta_{0}}=\arcsin\left({\frac{{2r{V_{s}}}}{{\left({{V_{s}}+{V_{T}}}\right)\left({{R_{0}}+2r}\right)}}}\right)$
(84)

Figure 18: Critical speeds as a function of the number of defenders. The
number of defenders is even, and ranges from $2$ to $32$ defenders, that
perform the spiral and circular defense pincer sweep protocols as well as the
spiral and circular defense same-direction sweep protocols. The optimal lower
bound on the critical speeds is presented for comparison as well. The chosen
values of the parameters are $r=10$, $V_{T}=1$ and $R_{0}=100$.

Because pincer-based defense sweep protocols require a lower critical speed
compared to same-direction defense strategies, to fairly compare the
performance of the different defense protocols, all defenders in each of the
compared swarms is required to move at speeds above the critical speed of $2$
defenders that perform the same-direction circular defense protocol since it
has the highest critical speed compared to the circular pincer, spiral pincer
and spiral same-direction defense protocols.

The necessity to have a higher critical speed means that there are domains
that can be successfully guarded using a team of defenders implementing
pincer-based defense protocols but cannot be defended with a team of equal
capabilities that performs same-direction defense protocols. Additionally,
this means that defender teams performing pincer-based defense protocols are
able to expand the protected region into a larger area compared to their same-
direction alternative protocols.

Fig. $19$ shows the maximal defendable protected region’s radius attained for
each defense protocol. The results show that the spiral pincer-based
approaches are best while circular same-direction defense protocols allow
defenders to expand the protected region to the smallest area compared to the
other expansion algorithms.

Figure 19: Maximal protected region’s radius. We simulated the spiral and
circular defense pincer sweep protocols as well as the spiral and circular
defense same-direction sweep protocols with an even number of defenders,
ranging from $2$ to $32$ defenders. We show results obtained for $\Delta
V=10V_{T}$ above the critical speed of $2$ defenders that employ the circular
defense same-direction sweep process. The chosen values of the parameters are
$r=10$, $V_{T}=10$ and $\varepsilon=0.2$.

Fig. $20$ shows the time until maximal expansion of the protected region to a
radius of $R_{max}=120$ for circular and spiral same-direction and circular
and spiral pincer-based protocols. The value of $R_{max}=120$ was chosen since
a region with this radius can be successfully guarded by all $4$ protocols.
All compared swarms have equal number of defenders and move at speeds that are
$10V_{T}$ above the critical speed of $2$ defenders that perform the circular
defense same-direction sweep process. Results show that the spiral defense
pincer sweep protocol results in the fastest expansion time of the protected
region to a given radius.

Figure 20: Time of maximal expansion of the protected region for the circular
and spiral defense sweep protocols as well as the spiral and circular defense
same-direction sweep protocols. We simulated sweep protocols with an even
number of defenders, ranging from $2$ to $32$ defenders, that perform the
defense sweep protocols at speeds of $10V_{T}$ above the critical speed of $2$
defenders that perform the circular defense same-direction sweep process. The
chosen values of the parameters are $r=10$, and $R_{max}=120$.

Fig. $21$ shows a zoomed-in plot of Fig. $20$ that displays the time until
maximal expansion of the protected region, for swarms of defenders with $4$ to
$22$ defenders. Results show that the spiral pincer defense protocols enables
the defending team to expand the protected region to an area of a certain size
more quickly compared to the circular same-direction, circular pincer and
spiral same-direction defense protocols. Additionally, results show that for
increasing number of defenders, circular pincer-based protocols lead to
shorter sweep times even when compared to spiral same-direction defense
protocols. This implies that despite the fact that pincer-based circular
defense protocols may be implemented with defenders possessing more basic
capabilities compared to defenders executing spiral strategies, the
cooperation among defenders greatly improves the performance of the defender
team.

Figure 21: Zoom in on the time of maximal expansion of the protected region
for the circular and spiral defense sweep protocols as well as the spiral and
circular defense same-direction sweep protocols. We simulated sweep protocols
with an even number of defenders, ranging from $4$ to $22$ defenders, that
perform the defense sweep protocols at speeds of $10V_{T}$ above the critical
speed of $2$ defenders that perform the circular defense same-direction sweep
process. The chosen values of the parameters are $r=10$, and $R_{max}=120$.

##  VIII Conclusions and Future Research Directions

This research studies the problem of guaranteeing defense of an initial region
against smart mobile invaders by a swarm of defending agents that act as
visual sensors. Invaders are initially located outside a known circular
environment which they try to enter without being detected by the defenders.
Two novel algorithms that guarantee no intruder enters the region without
being detected by a defender team that uses pincer movements between defending
pairs are developed and compared to state-of-the-art approaches, proving the
superiority of pincer-based defense protocols. Having a speed that exceeds the
critical speed that allows defending the initial region, allows the defenders
to gradually expand the protected region as well. Numerical and illustrative
simulations using MATLAB and NetLogo demonstrate the performance of the
proposed algorithms.

A possible extension to this work is to generalize the results for
environments with more complex geometries, possibly in the presence of
obstacles and apply the pincer expansion protocols in such settings. An
additional interesting research avenue is to develop an algorithm that will be
robust to failures of defenders and will allow to reorganize the defender team
and enable it to continue the defense and expansion tasks with less defenders.

## Appendix A

This appendix provides an analytical computation of the total outward
advancement times required in order for a defender team performing the
circular defense pincer sweep process to expand the protected region to the
maximal defendable area and completes the calculation from section IV. Denote
the total outward advancement time by
$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{{out}_{i}}}}$.
Equation (29) is expressed as,

$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{{out}_{i}}}}=\frac{{\left({{N_{n}}-1}\right)r}}{{{V_{s}}+{V_{T}}}}-\frac{{2\pi{V_{T}}\sum\limits_{i=0}^{{N_{n}}-2}{{R_{i}}}}}{{n{V_{s}}\left({{V_{s}}+{V_{T}}}\right)}}$
(85)

The method to calculate $\sum\limits_{i=0}^{{N_{n}}-2}{R_{i}}$ is developed in
Appendix $E$ of [19] and equals,

$\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}}}}$
(86)

The calculation of $R_{{N_{n}}-2}$ is provided in Appendix $B$ of [19]. It is
given by,

$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)$
(87)

Replacement of coefficients in (87) results in,

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

exchanging the coefficients in (86) leads to,

$\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{{{n^{2}}{V_{s}}r\left({{V_{s}}+{V_{T}}}\right)}}{{{{\left({2\pi{V_{T}}}\right)}^{2}}}}+\frac{{nr{V_{s}}\left({{N_{n}}-1}\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{{n\left({2\pi{R_{0}}{V_{T}}-n{V_{s}}r}\right)\left({{V_{s}}+{V_{T}}}\right)}}{{{{\left({2\pi{V_{T}}}\right)}^{2}}}}}\right)\end{array}$
(89)

Replacing the expression for ${\sum\limits_{i=0}^{{N_{n}}-2}{{R_{i}}}}$ from
(89) to equation (85) yields,

$\begin{array}[]{l}\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}}=\\\
-\frac{{{R_{0}}}}{{{V_{s}}}}+\frac{{nr}}{{2\pi{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}}-n{V_{s}}r}}{{2\pi{V_{T}}{V_{s}}}}}\right)\end{array}$
(90)

## Appendix B

This appendix provides an analytical computation of the total outward
advancement times required in order for a defender team performing the spiral
defense pincer sweep process to expand the protected region to the maximal
defendable area and completes the calculation from section V. Denote the total
outward advancement time by
$\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{{out}_{i}}}}$.
Equation (70) is expressed as,

$\begin{array}[]{l}\widetilde{T}_{out}(n)=\sum\limits_{i=0}^{{N_{n}}-2}{{T_{ou{t_{i}}}}}=\frac{{2r\left({{N_{n}}-1}\right)}}{{{V_{s}}+{V_{T}}}}-\frac{{\left({1-\lambda}\right)\sum\limits_{i=0}^{{N_{n}}-2}{{{\tilde{R}}_{i}}}}}{{{V_{s}}+{V_{T}}}}\end{array}$
(91)

The method to calculate $\sum\limits_{i=0}^{{N_{n}}-2}{R_{i}}$ is developed in
Appendix $E$ of [19] and equals,

$\sum\limits_{i=0}^{{N_{n}}-2}{\widetilde{R}_{i}}=\frac{{\widetilde{R}_{0}-{c_{2}}\widetilde{R}_{{N_{n}}-2}+({N_{n}}-2){c_{1}}}}{{1-{c_{2}}}}$
(92)

The calculation of $R_{{N_{n}}-2}$ is provided in Appendix $B$ of [19]. It is
given by,

$\widetilde{R}_{{N_{n}}-2}=\frac{{{c_{1}}}}{{1-{c_{2}}}}+{c_{2}}^{{N_{n}}-2}\left({\widetilde{R}_{0}-\frac{{{c_{1}}}}{{1-{c_{2}}}}}\right)$
(93)

Replacement of coefficients in (93) results in,

$\begin{array}[]{l}{{\tilde{R}}_{{N_{n}}-2}}=\frac{{2r}}{{1-\lambda}}+{\left({\frac{{{V_{T}}+{V_{s}}\lambda}}{{{V_{s}}+{V_{T}}}}}\right)^{{N_{n}}-2}}\left({{{\tilde{R}}_{0}}-\frac{{2r}}{{1-\lambda}}}\right)\end{array}$
(94)

exchanging the coefficients in (92) leads to,

$\begin{array}[]{l}\sum\limits_{i=0}^{{N_{n}}-2}{{{\tilde{R}}_{i}}}={{\tilde{R}}_{0}}\frac{{{V_{s}}+{V_{T}}}}{{{V_{s}}\left({1-\lambda}\right)}}-\frac{{2r\left({{V_{T}}+{V_{s}}\lambda}\right)}}{{{V_{s}}{{\left({1-\lambda}\right)}^{2}}}}-\\\
\frac{{{V_{s}}+{V_{T}}}}{{{V_{s}}\left({1-\lambda}\right)}}{\left({\frac{{{V_{T}}+{V_{s}}\lambda}}{{{V_{s}}+{V_{T}}}}}\right)^{{N_{n}}-1}}\left({{{\tilde{R}}_{0}}-\frac{{2r}}{{1-\lambda}}}\right)+\frac{{2r({N_{n}}-2)}}{{1-\lambda}}\end{array}$
(95)

Replacing the expression for
$\sum\limits_{i=0}^{{N_{n}}-2}{\widetilde{R}_{i}}$ from (95) to equation (91)
yields,

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

## References

  * [1] B. O. Koopman, _Search and screening: general principles with historical applications_. Pergamon Press, 1980.
  * [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] I. Rekleitis, V. Lee-Shue, A. P. New, and H. Choset, “Limited communication, multi-robot team based coverage,” in _Proceeding of the IEEE International Conference on Robotics and Automation (ICRA) 2004_ , vol. 4. IEEE, 2004, pp. 3462–3468.
  * [4] S. Alpern and S. Gal, _The theory of search games and rendezvous_. Springer Science & Business Media, 2006, vol. 55.
  * [5] 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.
  * [6] 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.
  * [7] 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.
  * [8] 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.
  * [9] 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.
  * [10] 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.
  * [11] V. R. Makkapati and P. Tsiotras, “Optimal evading strategies and task allocation in multi-player pursuit–evasion problems,” _Dynamic Games and Applications_ , vol. 9, no. 4, pp. 1168–1187, 2019.
  * [12] T. H. Chung, G. A. Hollinger, and V. Isler, “Search and pursuit-evasion in mobile robotics,” _Autonomous robots_ , vol. 31, no. 4, pp. 299–316, 2011\.
  * [13] S. S. Kumkov, S. Le Ménec, and V. S. Patsko, “Zero-sum pursuit-evasion differential games with many objects: survey of publications,” _Dynamic games and applications_ , vol. 7, no. 4, pp. 609–633, 2017.
  * [14] I. E. Weintraub, M. Pachter, and E. Garcia, “An introduction to pursuit-evasion differential games,” in _2020 American Control Conference (ACC)_. IEEE, 2020, pp. 1049–1066.
  * [15] E. Garcia, D. W. Casbeer, and M. Pachter, “Optimal strategies of the differential game in a circular region,” _IEEE Control Systems Letters_ , vol. 4, no. 2, pp. 492–497, 2019.
  * [16] E. Garcia, D. W. Casbeer, A. Von Moll, and M. Pachter, “Multiple pursuer multiple evader differential games,” _IEEE Transactions on Automatic Control_ , vol. 66, no. 5, pp. 2345–2350, 2020.
  * [17] N. Agmon, S. Kraus, and G. A. Kaminka, “Multi-robot perimeter patrol in adversarial settings,” in _2008 IEEE International Conference on Robotics and Automation_. IEEE, 2008, pp. 2339–2345.
  * [18] N. Agmon, G. A. Kaminka, and S. Kraus, “Multi-robot adversarial patrolling: facing a full-knowledge opponent,” _Journal of Artificial Intelligence Research_ , vol. 42, pp. 887–916, 2011.
  * [19] R. M. Francos and A. M. Bruckstein, “Search for smart evaders with swarms of sweeping agents,” _IEEE Transactions on Robotics_ , vol. 38, no. 2, pp. 1080–1100, 2021.
  * [20] R. M. Francos and A. Bruckstein, “Pincer-based vs. same-direction strategies of search for smart evaders by swarms of agents,” _arXiv preprint arXiv:2104.06940_ , 2021.
  * [21] 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.
  * [22] R. M. Francos and A. M. Bruckstein, “Search for smart evaders with sweeping agents,” _Robotica_ , vol. 39, no. 12, pp. 2210–2245, 2021.