1. Introduction
In recent years, the number of deployments and applications of unmanned aerial vehicles (UAVs) or drones has skyrocketed. The commercial sectors are now using UAVs for different purposes, including parcel delivery, surveillance, and rescue operations [Reference Altshuler, Yanovsky, Wagner and Bruckstein1, Reference Barca and Sekercioglu2]. Meanwhile, consumer-based UAV models are also readily accessible to the general public. However, although there are sufficient regulations and standards to ensure order and safety in our sky, we expect a reasonable number of UAV users who do not abide by them [Reference Cavoukian3]. Recent media reports confirm unprecedented consequences of inappropriate utilization of these UAVs, such as disturbing regular flights in the airports, delivering illegal objects to restricted areas, or invading public privacy [Reference Bleasdale4]. Therefore, we require new technologies to overcome these issues as a future need [Reference Kappel, Cabreira, Marins, de Brisolara and Ferreira5]. Currently, in most cases, a UAV can work along by an operator. It is expected that many autonomous groups of UAVs may collaboratively perform different tasks in the near future.
Generally, UAV search approaches operate on the basis of radar acoustics [Reference Liu, Wei, Chen, Pan, Lin and Ren6], light detection-and-ranging [Reference Müller7], and cameras [Reference Watanabe, Manecy, Amiez, Aoki and Nagai8]. Radar and radar hybrids are typically linked to geographical locations and they often fail when a number of UAVs exceed a threshold [Reference Blackman9–Reference Tonissen and Evans11]. In addition, radar does not function well when its signals are obscured by barriers such as walls and buildings, which are common in urban sites. On the other hand, acoustic approaches suffer from noise interference in the atmosphere that creates shade (e.g., wind). Likewise, vision techniques do not function properly when UAVs are not in sight. For overcoming of geographical limitations, some of the typical solutions are applying electromagnetic interference, laser, or net-launcher guns. However, these technologies are unlikely to scale well to swarms of drones [Reference Farid, Egerton, Barca and Kamal12]. In addition, if UAVs have a cooperative motion, the traditional system might be easier to be distracted by other UAVs. Therefore, different approaches need to be devised to combat this new form of intrusion [Reference Farid, Kamal and Egerton13]. The task of searching for a group of coordinated UAVs is challenging. Existing search techniques are less likely to perform well when the UAVs show confusion. Here, confusion refers to a phenomenon where patrollers have a constrained field of view (FOV) while intruding UAVs are operating at high speed and density, performing criss-cross movements, as well as having strong uniformity in appearance [Reference Blackman9]. Several confusion models exist, including gazelle-lion [Reference Gómez, Thijssen, Symington, Hailes and Kappen14], and evasive models of fish schooling such as the ones presented in refs. [Reference Fetecau and Meskas15, Reference Luke and Spector16]. However, to the best of our knowledge, none of the confusion tactics have been evaluated.
The swarm technology is flexible, scalable, and robust, so we perceive this as an ideal search solution in the scenario of a group of drones. Specifically, a swarm of patrolling UAVs is capable of searching for a swarm of intruding UAVs that are attempting to confuse and evade the patrolling swarm. The intruding UAVs can be divided into two main classes, namely stochastic non-intelligent and intelligent evaders. The former does not consider the patrolling UAVs’ position, and it is assumed that intruders are not aware of other intruders. On the other hand, for the latter, it is assumed that the intruders are avoiding being detected by the patrollers and cooperating timely with other intruding peers to avoid the detection or to escape from the patrolling UAVs. The former type of intruding UAVs has been well-reviewed in ref. [Reference Stone17], while the latter type falls under the search and pursuit problem [Reference Chung, Hollinger and Isler18]. There are a number of search and pursuit techniques using UAVs, but most works are limited to search and pursuit for ground evaders [Reference Huang, Savkin and Ni19].
Although there are a few works on tracking the aerial evaders using game theory [Reference Alexopoulos, Schmidt and Badreddin20], they do not consider the swarm versus swarm tracking scenario, and it is only limited to two trackers and one evader. In addition, in the latter case, the speed of evaders is
$20\%$
less than the speed of the trackers. Our research considers a challenging scenario where evaders have 360
$^{\circ }$
FOV and a perfect communication field. According to Robin et al. [Reference Robin and Lacroix21], the cooperation in search could lead to different categories, including capture, probabilistic search, hunting, and patrolling of intruding UAVs. In the capture scenario, the system should be functional even in the worst-case scenario where the system always has sufficient resources for capturing the intruders in any condition. Conversely, in the probabilistic and hunting [Reference Stone, Streit, Corwin and Bell22] scenario, the search continues until the intruders are detected by using probability or random movements. However, there is no guarantee in detecting all the intruders. Moreover, when there is a need for cyclic mobile search, patrolling is preferred.
The current literature focuses mainly on flying robots deployed to search for objects on the ground [Reference Schwager, Julian, Angermann and Rus23], and there is very limited literature available in the context of searching for flying drones with patrolling swarms. In this context, most search strategies for UAVs are limited to the mathematical formulation without considering real-world challenges, including limitations in the FOV and communication range [Reference Alexopoulos, Schmidt and Badreddin20]. As alternatives, evolutionary algorithms are ideal for solving problems without a precise mathematical formulation. In general, an evolutionary algorithm uses several agents which are scattered throughout the search space. Each agent has access to information from all or nearby agents. The communication and exchange of information among agents lead them to converge to a solution after some iterations [Reference Simon24]. When we consider the tasks of searching for intruders in the surveillance space by using some UAVs, there are some similarities between evolutionary search and multi-UAV search. In multi-UAV search, all patrollers collaborate among each other by communicating the best search solution, also known as local optimum. Ultimately, all patrollers have the same goal, which is to converge to the global optimum, and in this context, to detect the intruding UAVs.
In a single-objective evolutionary algorithm, there are two important processes, namely exploration and exploitation. The exploration parameters improve the diversity level among agents by ensuring that agents reach different promising regions in the search space. Meanwhile, exploitation narrows down the search process to focus on searching for the optimal solution in the given region. It is a known challenge in setting the optimal balance between the exploration and exploitation rates for the agents to ensure convergence. Studies have shown that misuse of exploitation may lead to premature convergence [Reference Kim, Song and Nerkar25], and there is a set of approaches to improve the exploration as well as exploitation [Reference Moors, Rohling and Schulz, “26]. Besides, in the multi-objective evolutionary algorithm, good dispersion of candidate solutions in the Pareto front is crucial, because more distributed candidate solutions can lead to better decisions from the objective spaces. In this sense, to apply evolutionary algorithms in UAV searching, we are required to modify these algorithms.
This paper makes the following contributions: First, a comparison between two types of patrolling swarms is performed, namely single-objective and multi-objective swarm search methods. In addition, Lévy flight is also compared with single-objective and multi-objective search as it is a common type of random search in swarm robotics. Second, different intruding strategies are deployed on intruding swarms to expose the patrollers to a more realistic and challenging search environment. This provides an opportunity to evaluate the capability and robustness of the patrolling swarm of UAVs. In this research, we expected a general size multi-rotor UAV, such as hummingbird quadrotor, in which its camera can see a specific depth with a specific view as shown in Fig. 1. The UAV type in this paper is limited to multi-rotor, but it can be extended to fixed-wing too by considering the limitations such as turnings. The rest of this article is organized as follows: In Section 2, the swarm versus swarm scenario is described. Then, the behaviors of the patrolling swarm are presented in Section 3, while Section 4 presents the simulation results that evaluate the performance of the presented algorithm. Finally, Section 5 concludes this paper and identifies some potential future works.
Figure 1. The FOV coefficients of a camera mounted on the patrolling UAV.
2. Swarm versus swarm system
We consider an environment that includes two swarms of quadrotor UAVs, labeled as
$\mathcal{M}$
and
$\mathcal{H}$
. To ease the presentation, we call every UAV in both swarms an agent or node. Here, we let
$I \;:\!=\; |\mathcal{M}|$
and
$J \;:\!=\; |\mathcal{H}|$
, where
$|X|$
denotes the cardinality of the set
$X$
. Nodes in swarm
$\mathcal{M}$
are equipped with one camera mounted on a pan-tilt gimbal. This arrangement enables flexible tuning of camera orientation or FOV to enhance the perception of the environment. The goal of all nodes in the swarm
$\mathcal{M}$
, which is also known as the patrolling swarms, is to search the environment for any nodes of swarm from
$\mathcal{H}$
, also known as the intruding swarms. Consider two sets of nodes
$\alpha =\{m_i\}_{i = 1}^{I}$
and
$\beta =\{h_j\}_{j = 1}^{J}$
. Assume that the initial positions and number of swarms are known for
$\alpha$
, but not for any of the nodes in
$\beta$
. To facilitate the presentation, let
$p_i(t)$
denote the position at time
$t$
and
$f_i(t)$
represent the FOV at time
$t$
for node
$m_i$
. Similarly,
$p_j(t)$
and
$f_j(t)$
are defined for node
$h_j$
. Each
$m_i$
has a limited FOV, while each
$h_j$
has a 360
$^{\circ }$
view, and both
$m_i$
and
$h_j$
have a limited camera range, denoted by
$R$
. In other words, to simulate the worst-case scenario, while the patrolling swarm has a limited FOV, the intruding swarm has a 360
$^{\circ }$
FOV which can simulate a challenging scenario for patrolling swarm.
Each node has a maximum speed, which is denoted by
$v^{\textrm{max}}_M$
and
$v^{\textrm{max}}_H$
for nodes in
$\mathcal{M}$
and
$\mathcal{H}$
, respectively. If we define
$v_M(t,i)$
as the velocity of
$m_i$
at time
$t$
, then
$|v_M(t,i)|\le v^{\textrm{max}}_M$
. Similarly,
$|v_H(t,j)| \le v^{\textrm{max}}_H$
holds true.
At any time instant, each
$m_i$
at
$p_i(t)$
can sense the volume
$V(f_i(t))=qw\gamma/3$
, where
$q$
is the diagonal FOV,
$w$
is the horizontal FOV, and
$\gamma$
is the vertical FOV. This is illustrated in Fig. 1. The total volume seen by all nodes in
$\alpha$
at time
$t$
is
$T=\cup _{m_i \in \alpha }V(f_i(t))$
, which is significantly smaller than the total volume of the search space
$V_S$
, that is,
$T \ll V_S$
. At time
$t$
, each
$m_i$
plans for the next position, that is,
$p_i(t+1)$
as well as the FOV
$f_i(t+1)$
according to the peers within its neighborhood and the detected intruders. Likewise,
$h_j$
performs the same operations, except for the Constant mode, where intruders nodes fly in straight lines.
2.1. Behaviors of the intruding swarm (swarm
$\mathcal{H}$
)
There is no prior information about the intruding swarm of UAVs on the surveillance system. Since intruders may have different behaviors, the surveillance system has to be evaluated under different scenarios. In this study, we classify the behaviors of intruding swarms into two categories, namely: (i) intelligent and (ii) non-intelligent movements. Intelligent UAV decides on their path according to the information gained from the environment. Meanwhile, non-intelligent UAV simply follows a specific pattern regardless of the environment. In addition to the aforementioned two broad categories, we also introduce two additional variations to the behaviors, namely the homogeneous and heterogeneous scenarios. Specifically, in the homogeneous scenario, all intruding UAVs would behave similarly. In other words, all UAVs tend to move in a similar pattern. On the contrary, UAVs in heterogeneous scenarios may move with different patterns. This makes heterogeneous scenarios more challenging as one search strategy may not be effective in searching for all the different movements. The uncertainty of entry and exit points of the intruders further complicates the search process. For example, one UAV may move from the sides of the space while another may move through the center of the bounded environment. On the other hand, one UAV may remain within the search space while another may exit the space at different intervals. Finally, the pattern of movement is another factor that may affect the patrolling swarm’s performance. Intruders may travel densely or scattered, which can have impact on patrollers.
2.1.1. Non-intelligent intruding UAVs
Intruding UAVs may decide their position without considering the information from the environment. Their behavior is not dependent on the presence of the patrolling UAVs. In this case, the intruders are called non-intelligent. The non-intelligent movement is defined as constant mode for simplicity. In constant mode, intruder UAVs simply move from one location to another location without consideration of the position of
$m_i$
’s or
$h_j$
’s. Therefore, the constant mode cannot be considered a swarm, but it is useful as a reference (baseline) to show how the other search processes perform.
In constant mode, the position of the UAV changes
\begin{equation} p_{j}(t+1)=W+p_j(t), \end{equation}
where
$p_j(t)$
is the position of
$h_j$
with
$p_j=[p_{(j,x)},p_{(j,y)},p_{(j,z)}]$
at time
$t$
, and
$W$
is a displacement vector which is chosen as a constant in this paper.
2.1.2. Intelligent intruding UAVs
Intelligent intruders refer to a swarm of intruders that plan their paths by considering their surrounding environment. This means the intruding swarm may have a specific plan in different cases. For example, patrolling swarm
$\mathcal{M}$
may be present, searching for intruders within the surveillance area. Therefore, the aim of these plans is to minimize the chance of being detected by swarm
$\mathcal{M}$
. The intelligent intruders can be classified into two scenarios namely homogeneous and heterogeneous intruders. Specifically, homogeneous refers to the scenario when all intruding UAVs within the swarm have the same hardware and software configurations [Reference Bouffanais27]. In this work, we consider two types of homogeneous intruders, that is, evasive (E) and evasive+confusion (E + C).
First, in the evasive mode, the intruding UAVs are smarter than those working in the constant mode. They have awareness of their surroundings and share information with their neighbors or peers. They are able to detect
$m_i$
UAVs. To simulate the worst-case scenario, it is assumed that the intruding UAVs can predict or already know the sensing range of the patrolling UAVs. Although it may not be approachable with the current technology, intruders with awareness of the sensing range of the patrolling UAVs can evaluate the performance of the designed patrolling system in the most challenging scenario. Each for the constant mode, the intruding UAVs use multiple objective optimizations (MOO) to plan their movement. Specifically, each intruding UAV
$h_j$
plans its movement by MOO for time
$t+1$
, which is represented by
$p_j(t+1)$
, where
$j=1,\dots,J$
and
$p_j(t+1)$
represents the next position of the
$h_j$
UAV. It is assumed that
$h_j$
has
$n(j)$
neighbors within its communication range. Similarly, for the patrolling swarm, it is assumed that
$m_i$
has
$s(i)$
neighbors within its communication range. In such a case, there are two cost functions that must be minimized to meet the objectives. The first objective is to keep the intruding UAVs as dispersed as possible. In other words, keeping larger gaps among the intruding UAVs will reduce the probability of simultaneous detection by the patrolling UAVs.
\begin{equation} c_{e_1}=\sum _{l=1}^{n}\dfrac{1}{\|p_j(t+1)-p_l(t)\|}. \end{equation}
The second objective guides the intruding UAVs to keep their distance from the nearby patrolling UAVs, that is, to stay away from the sensing area to avoid detection. Since each intruder UAV is assumed to have a 360
$^{\circ }$
FOV view, the sensing area is a sphere. In this sense, the second objective is expressed as:
\begin{equation} c_{e_2}=\left \{ \begin{array}{c@{\quad}c} \dfrac{1}{{((p_j(t+1)-p_i(t))^2-(r)^2)}} &\textrm{if outside sensing sphere};\\\\ 1 &{\rm \ otherwise}, \\ \end{array} \right. \end{equation}
where
$p_j$
is the position of the intruding UAV
$h_j$
, while
$p_i$
is the position of the patrolling UAV
$m_i$
, and
$r$
is the sensing radius. However, there is still a chance that
$h_j$
being detected by
$m_i$
because they cannot predict
$m_i$
’s future positions.
In the second scenario, that is, evasive+confusion mode (hereinafter referred to as zig-zag), similar to the evasive mode, the UAVs are able to communicate with their peers within the communication range. This mode produces the most complex motions to confuse the patrolling swarm and adds non-linear motions to their evasive trajectories using Eqs. (2) and (4) in an attempt to confuse the patrolling UAVs and increase the chance of losing any intruding UAVs after being detected by any patrolling UAVs. In the zig-zag mode, the second cost function is defined as:
\begin{equation} c_{c_2}=\sum _{k=1}^{m}\dfrac{p_k(t)-p_j(t+1)}{(\|p_k(t)-p_j(t+1)\|)^2}+ \sigma \sum _{l=1}^{n}\dfrac{p_j(t+1)-p_l(t)}{(\|p_j(t+1)-p_l(t))\|)^2}, \end{equation}
where the value of
$\sigma$
changes randomly from zero to one in every iteration to produce complex swarm motions. These motions will produce similar patterns of fish schooling [Reference Luke and Spector16] and gazelle-lion [Reference Gómez, Thijssen, Symington, Hailes and Kappen14] models.
2.1.3. The direction of movement
Intruders may enter and leave the space at any point, making the search even more challenging. Also, they can move freely from anywhere in the search space, for example, (a) along the border (edge path) or (b) all the way through the center of the space. They can also enter and leave the space at any time intervals (middle path) as shown in Fig. 2.
Figure 2. The intruding swarm passes through the center or passes along borders.
2.1.4. Dense and scattered modes
The distance among intruders is another factor for consideration in the behaviors of the swarm. Generally, swarms can move in dense or scattered modes. It is more challenging to address the dense movement scenario because the chance of detecting intruders is reduced. In any case, the confusing behavior has two interpretations, that is, from the tracker’s and patroller’s perspectives. From the tracker’s perspective, the zig-zag scattered movement of intruders can reduce the chance of being tracked by trackers (patrolling UAVs), and it is more likely that trackers lose the intruders. However, from the patroller’s perspective, the intruders that are out of sight are the main challenge. In addition, according to ref. [Reference Partridge28], in nature, the larger and more dispersed the flock size is, the more likely that one patroller will notice the intruders sooner, and the patroller sends an alarm to others. On the contrary, the dense movement of intruders will reduce the chance of being detected by patrollers. Therefore, we introduce four cost functions that can simulate the dense movement of intruders where intruders fly closely among each other. An illustration of scattered and dense movements is shown in Fig. 3.
Figure 3. Illustration of scattered and dense movements.
First, the intruders plan the closest path to their destination
$G$
with position in the xyz-coordinate so that
$c_{S_{1}}$
is minimized:
\begin{equation} c_{S_{1}}={{\|G-p_j(t+1)}\|}. \end{equation}
Next, the intruders fly as close as possible to their peers by minimizing
$c_{S_{2}}$
:
\begin{equation} c_{S_{2}}={\sum _{l=1}^{n}{\|p_l(t)-p_j(t+1)}\|}. \end{equation}
It is worth mentioning that Eq. (6) could not lead to crashing
$n$
neighbors together because there are other objectives/conditions to fulfill, specifically:
\begin{equation} c_{S_{3}}=\left ({\sum _{k=1}^{m}{\|p_k(t)-p_i(t+1)}\|}\right )^{-1}. \end{equation}
In addition, to avoid collision, the repulsion cost is defined as follows:
\begin{equation} c_{S_4}=\sum _{l=1}^{n}C_r\times \textrm{exp}(D_l\tau _r), \end{equation}
where
$C_r$
and
$\tau _r$
are predefined constants and
$D_l$
is the Euclidean distance between the UAV and its neighbors
$l$
. The confusing behavior in intruders can be interpreted by using the
$C_{S_2}$
in Eq. (6), while Eqs. (7) and (8) are used for avoiding possible collisions.
2.1.5. Heterogeneous intruding UAVs
In practice, the surveillance area may be occupied by an intruding swarms of UAVs in which each swarm might have a different behaviors. Higher variations in behaviors might increase the complexity of the detection for the patrolling swarm. For simulating such a scenario, another type of intelligent intruder is categorized as heterogeneous intruders. These intruders can be defined in different ways. A heterogeneous swarm is a mixed set of different behaviors where a few UAVs show a specific behavior [Reference Bouffanais27].
2.1.6. Homogeneous and heterogeneous scenarios
In this study, we introduce two additional behaviors on the intruder UAVs, namely homogeneous and heterogeneous. In the homogeneous scenario, all intruding UAVs would move in similar patterns. Meanwhile, heterogeneous UAVs may have different behaviors within the swarm and they move with different patterns, which is a more realistic simulation of real-world surveillance scenarios. Another variation of the heterogeneous scenario includes a swarm of UAVs with sub-swarms, where each sub-swarm demonstrates different behaviors while an individual UAV within a particular sub-swarm behaves homogeneously. A heterogeneous swarm increases the difficulty and complexity of patrolling scenarios. Heterogeneous swarm has also been applied in the field of swarm robotics [Reference Bouffanais27].
3. The patrolling swarm (swarm
$\mathcal{M}$
)
An algorithm to develop a patrolling swarm is put forward in this section. We design the patrolling swarm based on the five objectives defined in ref. [Reference Farid, Egerton, Barca and Kamal12]. As a baseline, the performance of the patrolling swarm is then evaluated by considering intruders with different behaviors. In addition, we also define a novel algorithm for the patrolling swarm that we will introduce in the next subsection. In practice, the intruders may have different behaviors that may be unknown to the patrolling swarm. Therefore, two heuristic approaches are evaluated for the patrolling swarm, namely single-objective and multi-objective search.
Typically, a multi-objectives problem can be dealt with two general approaches. First, a multi-objectives problem can be converted into a single solution by using multiple weights (i.e., scalarization), which can be solved in a simpler way. However, the scalarization method is only effective if the various objectives can be expressed into a single unit by weighting them correctly. Second, when there exists a solution that is dominated by another solution, then approximating a set of possible solutions using the Pareto method would be more accurate. In the Pareto method, there are both dominated and non-dominated solutions. These solutions are obtained continuously from updating the algorithm. Since the behaviors of intruders are unknown, it is difficult to identify an optimal single solution. Therefore, the Pareto method is adopted in this study.
In the following, we first present an idea that we adapted from model predictive controller. Subsequently, we compare our proposed MOO with the adapted strategy from predictive control and finally we formulate the MOO search method.
3.1. Time receding horizon
In the model predictive control technique, the controller tries to find the best control actions by modeling the plant in a specific predictive time horizon [Reference Singh and Fuller29]. In this way, the actuator predicts the specific amount of time for modeling the plant and uses a smaller time for acting in the next control step. This is called time receding horizon (TRH). Similarly, in the developed algorithm, each patrolling UAV estimates the best path for time
$t_{p_1}$
and then proceeds to move in the planned path for time
$t_{p_2}$
, where
$t_{p_2} \lt t_{p_1}$
. This technique provides a more informed decision, but on the other hand, it requires more computing power. In this paper, as shown in Fig. 4 TRH plans for the next 1 second and move for 0.25 s and re-plan again accordingly.
Figure 4. Time receding horizon concept: planning for 1 s and re-plan after 0.25 s.
3.2. Multi-objective search
3.2.1. Multi-objective-based patrolling
It is assumed that the swarm
$\mathcal{M}$
is properly dispersed by using a proper dispersion algorithm. Specifically, patrolling swarm using MOO maximizes its search area. Here, MOO optimization is indicated by a combination of two objectives in each UAV within the swarm in a bounded search area. These objectives are related to the UAV’s position and the camera orientation. The position is selected in a way to maintain a suitable distance among
$m_i$
UAVs. On the other hand, camera orientation is chosen by considering the camera orientation of its neighbors for having the minimum or, if possible, no overlap. Similar to
$h_j$
described in the previous section, the patrolling UAVs also solve a multi-objective problem. Hence, before defining the search objectives and techniques, a brief formulation of the multi-objective problem is presented.
The MOO is an approach that determines the next position and camera orientation of each UAV. Since each UAV has access to its data and neighbors within its communication field in the swarm setting, the decision is made considering both the UAV and its neighbors. This behavior is shown in Fig. 9. In addition, MOO can be seen as a randomized algorithm. In this way, a set of random candidate solutions are generated within the sphere that is based on the maximum traveled distance and camera orientation for each iteration (as shown in Fig. 5). These data can be derived based on UAV specifications. Then the set of candidate solutions are compared based on the given cost (objective) functions. The MOO finds a set of non-dominated solutions on Pareto front, the decision maker later chooses the best optimal solution from the Pareto front.
Figure 5. The process of planning the next iteration for UAV
$m_1$
considering its peers (
$m_2$
,
$m_3$
,
$m_4$
) within the communication range: (a) the status at time
$t$
when candidate solutions for the next iteration are generated, and (b) the best solution is chosen according to the neighbors while the neighbors are planning their own new goals by using the proposed MOO algorithm [Reference Farid, Egerton, Barca and Kamal12].
3.2.2. Implementation of MOO
In the designed system, the MOO updates the position and the FOV of each UAV in a timely manner. Here, a pose comprises the coordinate position of the UAV and the coordinate position of the camera gimbal, which directly relates to the UAV’s FOV. The pose of
$m_i$
(patroller) is updated through the application of the embedded MOO techniques [Reference Deb, Sindhya and Hakanen30]. First, several pose offsets within a radius
$R$
are randomly generated around the current pose of a UAV. An illustration is shown in Fig. 5. Each offset is then evaluated by MOO and the best pose is chosen for the next simulated time step
$t+1$
. Likewise, the pose of
$h_j$
(intruder) is updated in a similar manner. They are designed to have a different set of objectives, that is, to either follow a zig-zag path or evasive trajectories. The detailed descriptions of our proposed approach can be found in ref. [Reference Farid, Egerton, Barca and Kamal12]. In our previous paper, a set of objectives are compared against each other and the results showed that the detection rate of both evasive and evasive+confusion may vary depending on the patrolling swarm’s position and camera orientation. Specifically, the patrolling swarm applies MOO-based decision-making, where each UAV can decide its path and camera orientation.
According to Fig. 6, the MOO considers the current position and the camera orientation of the UAV and its neighbors. Then, the MOO generate a Pareto front, which contains a set of solutions. Finally, a decision maker chooses the best solution among the Pareto front.
Figure 6. The MOO approach in search [Reference Farid, Egerton, Barca and Kamal12].
4. Results
4.1. Comparison among behaviors
We conduct experiments with the following three behaviors, namely (i) dense, (ii) mixed, and (iii) scattered. In each simulation, the intruding swarm enters from a specific location and leaves from a specific location with different behaviors and motion patterns throughout the space. Specifically, for dense movement, each UAV in the swarm keeps the minimum distance from its peers within the communication range. A sample trajectories of both swarms are shown in Figs. 7 and 8. For mixed movement, each group of UAVs chooses specific behavior (which differs from the other groups) to pass or move around the surveillance area. Here, mixed movement refers to heterogeneous behavior in intruders, and behaviors can be chosen randomly from dense or zig-zag motions (i.e., evasive). For scattered movement, each UAV keeps a large distance from its peers within the communication range.
Figure 7. The intruding swarm in dense mode passes from (a) edge or (b) center of surveillance area.
Figure 8. Patroling swarm UAVs’ sample trajectory works with “S1” strategy using
$I=16$
: (a) initial seconds and (b) end of mission.
The number of detected intruding UAVs is then evaluated by using percentage of detection, that is, the number of detected UAVs over the total number of intruding UAVs. Figures 9 and 10 show the results for mixed-mode, which suggest that the percentage of detection is lowest, in general, after 55 iterations. This is due to the fact that a mixed-mode includes multiple intruding swarms with different behaviors, which makes the surveillance task more difficult for the patrolling swarm. On the other hand, scattered movement is observed to have a higher percentage of detection by the patrolling swarm. Here, the patrolling swarm consists of a set of mobile cameras that spread over the surveillance area. Scattered path planning by the intruding UAVs can lead to an increase in the detection rate because in practice, there are some uncovered regions in the surveillance area, that is, due to limited resources (number of patrolling UAVs) – in which the patrolling swarm is vulnerable on those regions. To cover those regions, the patrolling swarm dynamically changes its position to overcome this vulnerability. From this perspective, in the dense movement scenario, in case one intruder is detected, all other intruding UAVs are in danger because the intruders are flying very close to each other. However, dense movement is used when the intruders prefer to avoid any detection. On the contrary, for passing-by, the scattered mode is preferred if the detection of a few intruders is not important. In this paper, we focus on evaluating the performance of the aforementioned algorithms, namely dense, mixed, and scattered. In practice, choosing whether scattered or dense movement may depend on the mission, for example, in a mission where intruders should not be detected at all, a dense movement will be more well suited.
Figure 9. A comparison of various modes of movement in intruders when the patrolling swarm works with “S1” strategy using
$I=16$
and
$J=40$
.
Figure 10. The bar chart for detection when the patrolling swarm works with “S1” strategy,
$I=16$
and
$J=40$
.
4.2. Lévy flight versus MOO
To further evaluate the effectiveness of MOO in swarm search, it is compared with Lévy flight. Lévy flight produces random jump for the next position for robot [Reference Sutantyo, Levi, Möslinger and Read, “31]. It is well-known in the biological random search process that can be effective in exploring the space to find the intruders in the simulation environment. Figure 11(a) and (b) shows the graphs of percentage of detection against number of iterations for different settings. The results demonstrate the effectiveness of the MOO approach as MOO is an intelligent method that utilizes the information of multiple solutions or UAVs in this case, as compared to the random search method using Lévy flight.
Figure 11. Comparison between MOOs search and Lévi random search in two different environments.
Figure 12. The intruders have evasive behavior and stay under the surveillance throughout all iterations.
4.3. Scalarization versus MOO
In scalarization, a scalarized single objective is formed by combining multiple objectives. For example,
$o_3=\gamma o_2+(1-\gamma )o_1$
is a scalarized single objective formed by combining two objectives (i.e.,
$o_1$
and
$o_2$
) where
$\gamma \in [0,1]$
. In other words, instead of optimizing
$o_1$
and
$o_2$
using MOO, SOO optimizes only a weighted sum of
$o_1$
and
$o_2$
in
$o_3$
. However, as expected, the scalarization approach suffers from theoretical limitations. First, scalarization is not able to cover the entire Pareto front while MOO predicts a better approximation of the front. The proper Pareto front leads to better tradeoff between
$o_1$
and
$o_2$
. Second, MOO produces a set of possible solutions while SOO is only based on a single solution. Third, the efficiency of scalarized SOO is highly related to the proper setting of weights (
$\gamma$
), but MOO does not need any manual setting for weights in a different situation and it is completely adaptive. Therefore, MOO is expected to show better performance when intruders have highly complex behaviors.
The aforementioned drawbacks of the scalarization method are verified through various simulations. In this sense, different intruder behaviors are evaluated by using different weight configurations. Figure 12 shows how choosing different scalarization coefficients leads to various performances. On the other hand, Fig. 13 suggests one configuration may appear as the best solution in a problem while falling short in another problem. In Fig. 12,
$\gamma =0.5$
yields the worst result, while it is the best solution in Fig. 13. This further reaffirms the drawback of the scalarization method, where the solution of the scalarized problem will be a Pareto optimal point (best case) only if the weighted sum is accurate. Furthermore, the simulation results confirm that static weights are not suitable to deal with the unknown behavior of intruders. Moreover, the simulation results suggest that it is difficult to choose the right compromise between the different objectives in the scalarization approach. For example, when the intruders stay in the surveillance area,
$\gamma$
= 0.3 yields the best performance, but when the intruders are leaving the area,
$\gamma$
= 0.5 appears to be the best setting. Considering these outcomes, we demonstrate the results for
$\gamma =0.5$
and
$\gamma =0.3$
.
Figure 13. The intruders have evasive behavior and start to leave the surveillance area after iteration 50.
As a summary, the aforementioned simulation results mainly stem from the weakness of SOO in determining the Pareto front. It is challenging to fine tune SOO and set a proper
$\gamma$
when one is dealing with unknown behaviors of the intruders. As shown in Fig. 14, although both SOO and MOO yield similar performance for the first few iterations, MOO has clear advantage (i.e., win) after the 12th iteration. Despite SOO having different settings, the results are somewhat bounded due to lack of proper adaptive coefficients of scalarization. On the other hand, Lévy performs the worst, because it randomly searches the area. All in all, MOO is the most efficient approach in a 3D swarm versus swarm search context in comparison to scalarization and Lévy flight search algorithms.
Figure 14. Comparison among MOO, scalarization, and Lévy flight search approaches when
$I=16, J=40$
and the intruders are operating in zig-zag mode.
Figure 15. Comparison of performance in both scattered (zig-zag) and dense movement of intruders when they are passing from the side or center of the surveillance area.
4.4. Confirming the natural phenomena
Based on the results shown in Fig. 15, patrollers detected fewer intruders when the intruders moved in dense motion in comparison to scattered. The dense movement of the intruders can reduce the chances of being detected by patrollers. Interestingly, in fish schooling, there is a similar observation [Reference Partridge28]. Specifically, in the sea, fishes (i.e., the preys) avoid hunters (i.e., the predators) by moving in dense motion. For fishes, this phenomenon is due to the encounter effect, which states that it is easier to detect a group of fish if they are scattered in a large area in comparison to the aggregated group of individuals with unpredictable patterns.
Aggregation is a desirable tactic in intruders except for a few situations, including: (a) when the patrolling swarm can detect and kill all groups and (b) when the size of the aggregated group is quite large where scattering would be more beneficial. In addition, the path of intruders can affect the patrolling performance. Anonymous swarm’s path might pass from the edges or sides (edge path) or from the center of the surveillance area (middle path). As expected, side movement (edge path) of intruders leads to a lower rate of detection by the patrolling swarm.
4.5. Comparison between TRH and MOO
In our previous paper [Reference Farid, Kamal and Egerton13], the simulation results showed MOO swarming (S1) is the best when compared with sub-swarming approaches. This is due to less complexity and higher amounts of detections. Since in normal conditions TRH has a very similar performance to S1, to show the difference between TRH and S1, few challenging situations are considered. Challenging situations refer to a very large surveillance area and a low number of patrolling UAVs with a large number of intruders.
TRH provides a more efficient decision in the UAV, but, on the other hand, it imposes a higher computational cost. The performance of this approach is compared in both cases in which the opponents stay in the surveillance area (
$1000\times 1000\times 1000$
m
$^3$
) and there are 16 patrolling and 20 intruding UAVs. As shown in Fig. 16, the time receding approach outperforms S1. In these results, TRH plans for next 1 s and move for 0.25 s and re-plan again accordingly. Indeed, the path planning decisions are more accurate when considering the information of the other neighboring UAVs within the patrolling swarm. For comparison purposes, when considering the average processing time for all detections for 10 UAVs, results indicate that TRH (36 s) requires more processing time than S1 (8.49 s).
Figure 16. Time receding horizon approach when the anonymous swarm stays in the area and move using dense mode.
5. Conclusion
After discussing the problem of a swarm of intruding UAVs, a patrolling swarm is formulated to search and follow the intruders. To have a realistic simulation of unknown intruding behaviors of the intruders, a set of objectives are defined to simulate intruding behaviors. For the patrolling swarm, first, we design a multi-objective approach to optimize the location and FOV of each patrolling UAV within the swarm. Next, a single-objective patrolling swarm is deployed for searching purpose by using scalarization. We compare the multi-objective approach with other methods, including single-objective and Lévy flight approaches to evaluate the rate of detection in the swarm versus swarm context. Results suggest that the multi-objective approach is superior, while Lévy appears to be less effective.
The simulation results further suggest that our findings agree with that of the fish schooling phenomena, that is, when intruding UAVs fly densely in a group and close to each other, it is more difficult for the patrolling UAVs to detect these UAVs. This finding also suggests that dispersed movement of intruders will result in higher chances of detection by a patrolling swarm. In addition, using TRH strategy, which is imitated from a receding horizon control, can outperform the simple MOO.
The MOO can improve the percentage of detection from 60% to more than 95% in a specific time frame. The detection is highly influenced by the size of searching space, the number of patrolling UAVs, and the intruders’ behaviors. Visualizing the trajectories to gain more insights into our proposed patrolling strategy will leave as a future work.
As future work, we want to examine other sophisticated intruding behaviors to check other natural swarm phenomena, for example, fountain splitting, in a swarm search. Improving the design of multi-objective approach by improving the current decision-making can be another future direction.
Author contributions
Ali Moltajaei Farid conceived and designed the study. Ali Moltajaei Farid, Lim Mei Kuan, MAS Kamal, and KokSheik Wong wrote the article.
Financial support
This research received no specific grant from any funding agency, commercial, or not-for-profit sectors.
Conflicts of interest
The authors declare no conflicts of interest exist.
Ethical approval
Not applicable.
