A discrete particle swarm optimization coalition formation algorithm for multi-pursuer multi-evader game

Abstract

Multi-Pursuers Multi-Evader Game (MPMEG) is considered as a multi-agent complex problem in which the pursuers must perform the capture of the detected evaders according to the temporal constraints. In this paper, we propose a metaheuristic approach based on a Discrete Particle Swarm Optimization in order to allow a dynamic coalition formation of the pursuers during the pursuit game. A pursuit coalition can be considered as the role definition of each pursuer during the game. In this work, each possible coalition is represented by a feasible particle’s position, which changes the concerned coalition according to its velocity during the pursuit game. With the aim of showcasing the performance of the new approach, we propose a comparison study in relation to recent approaches processing the MPMEG in term of capturing time and payoff acquisition. Moreover, we have studied the pursuit capturing time according to the number of used particles as well as the dynamism of the pursuit coalitions formed during the game. The obtained results note that the proposed approach outperforms the compared approaches in relation to the capturing time by only using eight particles. Moreover, this approach improves the pursuers’ payoff acquisition, which represents the pursuers’ learning rate during the task execution.

Keywords

Multi-agent systems coalition formation algorithm discrete particle swarm optimization pursuit-evasion game

Nomenclature

Symbol

Description

The inertia weight

The particle’s velocity

The particle’s position

r₁, r₂

generated numbers in the range of [0, 1]

c₁, c₂

The Acceleration parameter

⋌

The coalition fitness

α, β

the agent’s ability coefficients.

The reward’s ability

The coalition representation

the Euclidean distance

the agent’s internal velocity

The changes’ percentage of each particle

℧

the maximum of the possible changes

A pursuit group

the number of possible agent’s next states.

The discount factor in the range of [0, 1]

The step-size sequence

The number of possible pursuers

Average reward obtained per pursuit

1 Introduction

Multi- agent Pursuit-Evasion Game (PEG) [1] is considered as one the most attractive research field in distributed artificial intelligence. This kind of game consists on a set of pursuers’ agents requiring a task coordination mechanism [2] to form pursuit coalitions with the aim of allocating the different tasks. These tasks concern the question “how the pursuers should be grouped to stop the motion of each detected pursuer”. Furthermore, the pursuers require a path planning mechanism [3] allowing them to take a decision regarding their displacements during the pursuit steps. Knowing that, the motion decision could be made in a centralized [4] or decentralized way [5]. On the one hand, the centralized way regards the case where the pursuers have to cooperate via the generation of an intelligent and collective path planning strategy. In other words, the path of each agent depends on the other agents’ trajectories. On the other hand, the decentralized approach concerns the case where the pursuers are independently moving until they reach their common objective.

In relation to the number of pursuers and evaders used in PEG, we can distinguish three variants of the PEG. In the case of a single pursuer purchasing a single evader SPSEG [6], only a path planning strategy must be provided to the pursuer in order to be able to perform the pursuit. However, if a set of pursuers are available to chase a single evader MPSEG [7], a task coordination mechanism could be also incorporated to select the most convenient pursuers that can form the single pursuit group. In the case of MPMEG [8], the task allocation concerns how the available pursuers will be grouped in different and optimal pursuit groups in order to parallelly perform the multi-pursuit game.

In general, Metaheuristic approaches [9] can be defined as iterative stochastic algorithms aiming to provide solutions for hard optimization problems. Multiagent (MAS) approaches and metaheuristics are closely linked to each other knowing that both are based on the social metaphor exploitation as well as the self-organization paradigm. Consequently, multiagent principles are hugely used in metaheuristics, especially for hybrid, distributed, and population-based metaheuristics. The positive points concerning the utilization of multiagent approaches in combination with metaheuristics can be vindicated by the distribution and robustness characterizing the multiagent systems, in addition to the flexibility and the modularity requirements. In relation to MAS, a metaheuristic can be defined as an organization aiming to efficiently explore the search space in order to discover highly advantageous solutions in accordance to the temporal constraints.

Among the existing Metaheuristic approaches, Particle Swarm Optimization (PSO) [10] is considered as one of the most popular. PSO is defined as a population-based optimization approach taken inspiration from the swarm movement of bird flocks as well as schooling fish. PSO has several similarities in comparison with evolutionary computation methods [11]. At the initialization step, the system generates a population reflecting random solutions, and the location of the optimal solution is carried out through the update of the generations. Contrary to Genetic Algorithms [12], PSO is not based on evolution operators, such as crossover and mutation. In PSO, the probable solutions, known as particles, change their positions in the problem space by following the actual optimum particles. From a computational point of view, PSO provides more performance in terms of both velocity and memory requirements [13]. In relation to the discrete problems, PSO algorithm is usually extended to discrete versions in order to be applicable. In [14], the authors introduced a novel discrete PSO model through a hybrid approach. Precisely, the hybrid approach takes into consideration the local search of the particle to move in accordance to its own experience, as well as the Path relinking to move in accordance to other particles’ experience. Knowing that the bionic PSO approach was designed for the continuous problems, many PSO-based optimization methods suffered due to the random displacements of the particles, which is caused by their inappropriate discretization strategies. To counter these issues, a PSO-based static load balancing algorithm aiming to appropriately affect every federate to an available host was recently introduced [15]. In other words, they improved the Personal best update of a given particle in the population through the use of better solutions stored in the external archive dominating it. In addition, a probability-based discretization approach was proposed to adapt the PSO algorithm to the discrete problem via the modification of the particles’ velocities and positions updates. In another context [16], a multi objective optimization method regarding the palm vein feature selection based on the discrete Particle Swarm Optimization (PSO) was recently introduced. The proposed multi-objective function takes into account the accuracy of the biometrics system as well as the size of the selected feature vector with the aim of increasing the accuracy of the system and decreasing the size of the feature vector.

In recent years, PSO is hugely combined with MAS in order to process several problems such as collaborative work planning strategy [17], expert systems optimization [18], medical image segmentation control [19], and Travelling Salesman Problem (TSP) [20]. Specifically, in this last, the original PSO algorithm was improved with the aim of incorporating the desired learning capacities into the agents. In relation to these lasts, they were designed to perform parallel calculations of fitness values based on the personal best of many neighborhoods and save the result in the belief database in order to be reused. The proposed work has improved the conventional PSO by increasing both the intelligence and autonomy rates of the swarm.

In this paper, we process the MPMEG via the proposition of a MAS coalition formation based on Discrete PSO approach in order to allow an optimal pursuits tasks’ allocation. The principal motivation of using this metaheuristic approach is that it allows an interesting exploration of the search space through the number of used particles as well as their dynamism provided by their velocities. Knowing that, the particles’ velocities are iteratively updated in relation to their personal best solution and also to the global best solution achieved in the search space. Moreover, the particles’ velocities calculation is based on different coefficients allowing the control of the solution convergence. The proposed approach is applied to MPMEG in comparison with dynamic task coordination methods. The necessity of dynamic approaches in MPMEG is due to the fact that the pursuit coalition dynamically changes according to the new environment positions of the mobile pursuers at each pursuit iteration. In comparison with the recent heuristics applied to the MPMEG for providing coalition formation, such as MAS organizational models and game theoretic methods, the proposed approach is categorized in the range of meta-heuristics. Knowing that meta-heuristics are problem-independent, the proposed approach can be applied to other np-hard problems. However, organizational models can only be used in order to coordinate the agents’ behavior. The game theoretic approaches based on the iterated elimination of dominated strategies need the generation of all the possible combinations in order to be efficient, which can lead in some cases to combinatorial explosions. Moreover, the strategies used in the dominance principle are considered as statics by the fact that they are not iteratively modified unlike the particles that continuously change according to their dynamic velocities. Furthermore, the proposed approach can also be efficient through the utilization of a small number of particles as demonstrated in section 5. This fact means that there are no risks to stuck in a combinatorial explosion via the use of the proposed approach. The main contributions of this work can be resumed as follows:

The proposition of a discrete version of Particle the Swarm Optimization (DPSO) for the Multi-Pursuer Multi-Evader Game (MPMEG).

The study of the impact of the particles’ number on the pursuit processing as well as their velocities changes during this process.

The comparison study of the proposed DPSO with recent optimization methods processing the MPMEG. This comparison study aims to prove the feasibility of the proposed DPSO in relation to the pursuit capturing time and the pursuers’ acquisition payoffs during the pursuit.

The paper is organized as follows: in section 2, we discuss some related works regarding the pursuit coalition formation as well as the application of PSO in MAS. In section 3, we define the PSO algorithm and PEG problem and how they are linked in this work. In section 4, we introduce the proposed pursuit coalition formation algorithm based on PSO via the explanation of the different algorithm’s steps. The simulation results in comparison with recent related cases are showcased in section 5 of the paper in order to showcase the improvement brought by the new proposal. Finally in section 6, we conclude our work by a brief summary of the work effectuated in this paper and some perspectives of our future works.

2 Related work

Multi-agent organizational models are often used to provide pursuit coalition formation algorithms. In [21], the authors proposed a fuzzy logic extension of Agent Group Role (AGR) organizational model to allow dynamic grouping of the pursuers. In other words, they equipped each pursuit group with a membership function determining the membership degree of each agent in relation to each group. The role of this membership function is to attribute the roles proposed by the group to the agents according to their membership degrees. Also, they studied the PEG by using AGRMF with static and dynamic coalition formation to showcase pursuit the impact of the groups’ dynamism. In another work [22], they have based on the Yet Another Multi-Agent Model (YAMAM) to process the PEG. thus, they used the concepts Agent, Role, Skills, and Task forming YAMAM organizational model to create a pursuit access mechanism to each pursuit group. They also introduced an interesting path planning method based on Reinforcement learning to allow a decentralized multi-agent motion strategy.

Game theory approaches are also usually used in relation to PEG. In [23], the authors were inspired by the Iterative Elimination of Dominated Strategies model (IEDS) to process the PE problem. In other words, they proposed a pursuit coalition formation algorithm based on IEDS. They considered a possible pursuit coalition as a strategy returning a specific reward according to the agents’ roles. After that, the pursuers in turn and iteratively eliminate the dominated coalitions according to their rewards’ impacts. The remaining strategy is considered as the selected pursuit coalition through this process. The process is repeated before each pursuit iteration allowing the dynamism of the pursuit coalition.

In relation to PEG, PSO algorithm was often used in different ways. In [24], PSO was used in order to control the mobile agents’ path planning. In other words, both pursuers and evaders are considered as particles. The motion strategy of evading particles is devised into local moving functions. Through the application of PSO algorithm, the pursuit particles resolve these local functions. On the one hand, the closest function value in relation to the evading particles is considered as the local best value. On the other hand, the global best value can be acquired in the case where the evading particle is captured. In [25], they proposed a binary PSO alliance generation for multi emotional robots chasing single evader. Specifically, each particle is considered as a possible pursuit alliance. The position variable of the alliance (i) is characterized by (m) dimensions (m represents the number of the existing pursuers’ robots). The size of the particle’s position variable can only take the value 0 or 1 in each dimension, meaning that the concerned pursuer belongs to the alliance or not. The size of particle’s velocity variable reflects the pursuit alliance adhesion probability of the concerned pursuer, whereas the global best variable is a record of the optimal solution of this alliance obtained during the best coalition finding process.

Metaheuristic approaches are hugely utilized in order to provide coalition formation algorithms. In [26], an improved particle swarm optimization (IPSO) was introduced for resolving the problem linked to the generation of the task-oriented optimal agent coalition formation. With the aim of overcoming the premature and local optimization problem in the original version of the PSO algorithm, they proposed a variation of inertia weight PSO algorithm through the analyze of the feasibility regarding the particle optimization process in PSO. In [27], PSO-based optimal multiple agents task allocation algorithm was proposed to process the cooperative timing mission problem. The traditional PSO-based algorithm for the cooperative timing mission was improved via the use of the graph theoretic constraints to guarantee the simultaneous arrivals. Recently in the context of task allocation [28], the authors proposed an efficient stability quantum particle swarm optimization (SQPSO) algorithm, which provides high payoffs acquisition, benefit division, coalition stability guarantee, as well as a historical task mechanism concerning the search acceleration. In addition, they designed an effective establishment quantum particle swarm optimization (EQPSO) algorithm for coalition scheduling, which is improved by a coalition similarity judgment aiming to decrease the coalition formation time cost. In another type of MAS games known as Coalitional Resources Games (CRG), which could be defined as a natural and formal framework based on agents desiring to form coalitions to pool their infrequent resources with the aim of reaching a set of objectives satisfying all members of a coalition, the research activities provided a large variance of task coordination mechanisms allowing the agents’ coalitions. In relation to PSO, the authors in [29] studied the possibility of involving binary particle swarm optimization (BPSO) in the role of stochastic search process in order to identify the Maximal Successful Coalition (MAXSC) in CRGs. To achieve their goals, they proposed a one-dimensional binary encoding scheme, and developed methods for encoding repair to guarantee the approximate validity and the logical consistency of each encoding in every iteration process. Finally, they discussed some essential properties regarding repair methods.

Moreover, other types of metaheuristic algorithms are also used to generate coalition formation approaches. In relation to Genetic Algorithms [30], they considered three variants of the coalition formation problem, which are, the single-task single-coalition formation, the multi-task single-coalition formation, and the multi-task multi-coalition formation. With the aim of decreasing the total cost, and at the same time satisfying the ability requirement constraint, the mathematical models of the three coalition variants were formulated. An effective genetic algorithm with heuristic initialization and repair strategy (GAHIR) was introduced to resolve the coalition formation problem. Multiple initialization and repair approaches using the prior knowledge of the specific problems were showcased to ameliorate the solution quality. In [31], the authors were inspired by Quantum Evolutionary Algorithms to expose a leader-follower coalition formation algorithm in a large-scale UAV network in order to constitute the best possible coalitions of the agents to perform the detected tasks in an unknown environment. Three principal goals have been taken into consideration in this coalition formation, the first objective was the decrease of resource consumption during the execution of the assigned tasks on time. The second objective regarded the upgrade of the coalitions’ reliability. Finally, they differentiated the most trustworthy UAVs from the self-interested UAVs in constituting the coalitions. In [32], taking into account the UAV coalition loss cost and time cost during a multi-task allocation problem, an ameliorated quantum genetic algorithm was suggested with the aim of resolving the task allocation problem of multi-UAV coalition. Based on the principles of quantum genetic algorithm, the historical optimal solution memorization method as well as the distribution estimation algorithm were proposed for respectively accelerating the convergence speed and decreasing the probability falling into the local optimum of the algorithm. Furthermore, in order to enhance the performance of the algorithm in relation to the problem background, a gene repair was incorporated.

Recently in [33], MPSEG was processed in the case where the evader’s velocity is higher than velocity of the pursuers. Knowing that in the discussed approach, the evader is randomly moving in the environment. To perform the capture, the authors proposed a new collaborative path planning aiming to provide an equilibrium that allows the pursuers to form an encirclement and to decrease the distance separating them from the evader at the same time. In the same pursuit context (MPSEG), in [34], deep reinforcement learning was used to process the problem related to the environment sensing as well as the decision-making. Specifically, a control mechanism inspired by the multiagent deep deterministic policy gradient (MADDPG) algorithm was constructed with the aim of implementing a multi-agent cooperative path planning decision-making to cross the limitation of the tedious state variables needed for the complex modeling treatment.

In relation to SPSEG, a general stochastic multi-agent Pursuit Evasion differential game based on additive Gaussian noise in the dynamics has been proposed in [35]. For avoiding the complexity linked to the multiplicity of the agents in conventional Dynamic Programming methods, a class of suboptimal approaches was introduced to reach a suboptimal solution with an enhancing property based on the optimization with restricted look-ahead.

In the case of MPMEG path planning [36], the authors proposed a pursuers’ path planning algorithm based on Theta* search to decrease the expected distance to the probability distribution of the concerned evader, which is measured via Markov localization principle. Also, they introduced a new repetitive pursuer assignment algorithm based on an excessive number of pursuers in order to minimize the expected time required to capture the evaders.

3 Background

In this section, we introduce the principles of PSO algorithm in subsection 3.1. Moreover, a large definition of PEG and the necessity of forming pursuit coalitions are detailed in subsection 3.2. Finally, we explain how the PSO principles will be used in order to provide a pursuit coalition formation algorithm.

3.1 Particle swarm optimization algorithm

In mathematics and computer science, an optimization problem refers to the problem of finding the best solution among all feasible ones. In the simplest terms, an optimization problem has for objective to maximize or minimize a real function known as the objective function through the systematic selection of input values according to a specific set and calculating the value of the function.

In general, an optimization problem can be described as follows:

$\begin{matrix} Min or Max f (x), x = (x_{1}, x_{2}, \dots, x_{N}) \\ subject to L_{i} ⩽ x_{i} ⩽ U_{i} \end{matrix}$ (1) where f(x) is the objective function of the optimization problem; x_i is the i^th decision variable; L_i and U_i are the lower and upper bounds of x_i in the case of the continued optimization problem; N is the number of variables defining the optimization problem dimension size. In the case where x_i can only take the values 0 or 1, the optimization problem becomes a binary optimization problem. However, in the case where the values of x_i are discrete values, the optimization problem is called discrete optimization problem.

An optimization algorithm can be defined as a set of instructions which are iteratively executed via the comparison of different solutions until finding an optimum or a satisfactory solution. The PSO algorithm introduced firstly by Kennedy and Eberhart [37], is a population-based optimization algorithm using a swarm of particles. It was inspired by the social behavior of individuals (particles) within a swarm to solve the optimization problems. In the PSO, a number of particles are stochastically generated and moving in the search space with a velocity determined according to its own search experience and the experience of its neighbors in the swarm. In [38], an important PSO version was introduced. Specifically, the authors introduced a new parameter known as the inertia weight aiming to balance the global search as well as the local search. Generally, Each particle is represented by a current position X_i =(x₁, x₂ … x_N), which is considered as a solution of the optimization problem, a velocity Vi =(v₁, v₂ … V_N) used for updating the particle’s position, and their best position visited Pbest =(p₁, p₂ … p_N). where N is the number of decision variables of the optimization problem. In the PSO algorithm, all particle’s positions are randomly initialized in the search space. Also, each particle updates its position at each iteration by adding a velocity (displacement step) to its current position as shown in the Equation (2) [38].

$x_{i}^{t + 1} = x_{i}^{t} + v_{i}^{t + 1}$ (2) where $x_{i}^{t}$ , $x_{i}^{t + 1}$ and $v_{i}^{t + 1}$ are the current position, the new position and the velocity of the i^th particle in the d^th dimension respectively.

The velocity of each particle is updated by using the personal best position and the global best position (the best position of all particles of the swarm) as presented in Equation (3) [38].

$\begin{matrix} v_{i}^{t + 1} = & {wv}_{i}^{t} + c_{1} r_{1} (Pbes t_{i} - x_{i}^{t}) \\ + c_{2} r_{2} (Gbes t_{i} - x_{i}^{t}) \end{matrix}$ (3) where $v_{i}^{t}$ and $v_{i}^{t + 1}$ are the current and the new velocity of the i^th particle in the d^th dimension respectively; and $x_{i}^{t}$ and $x_{i}^{t + 1}$ are the current and the new position respectively; Pbest_i and Gbest_i are the best position found by the i^th particle and the best position found by all particles of the swarm respectively; w is the inertia weight used to control the exploration and the exploitation power of the particle. c₁ and c₂ are called the acceleration parameters; r₁ and r₂ are randomly generated numbers in the range of [0, 1].

At each iteration, the performance of each particle x is calculated using its current position and the fitness function f(x). After that, the Pbest and Gbest are updated. The PSO algorithm automatically stops after a predefined number of iterations.

3.2 Pursuit-evasion game

Multi-Pursuer-Multi-Evader game is considered as np-hard multi-agent problem in which the existing pursuers P = {p₁, p₂ … p_j} cooperate with each other in order to generate a collective intelligent behavior allowing the capture of the detected evaders E = {e₁, e₂ … e_k}. The main objective of a coalition formation algorithm is to provide a task coordination mechanism to the pursuers with the aim of minimizing the pursuit iterations used in the chase process. A coalition formation can be defined as follows:

$C = {p_{1}^{r_{1}}, p_{2}^{r_{2}} \dots p_{j}^{r_{j}}}$ (4) where r represents the role that the pursuer has to play through the coalition. This role defines which evader is purchased by the concerned pursuer. Knowing that, each evader requires a specific number (Re) of pursuers in order to be captured. The pursuers having the same role or purchasing the same evader form a pursuit group. Consequently, in order to effectuate a feasible pursuit, the following condition must be verified:

$j \geq \sum_{k}^{i = 1} R e_{i}$ (5)

The pursuit environment allows the localization of the agents according to their cartesian coordinates. In this work, the pursuit-evasion world is represented by a limited grid of cells environment. Each cell represents a position that can be occupied by only one agent at each pursuit iteration. Knowing that each agent can only percept the information contained in the adjacent cells. Consequently, the pursuit environment can be considered as partially observable. Moreover, each pursuer can move from a cell to another one according to its internal velocity. An evader is considered as captured if only all its adjacent cells are occupied by pursuers. The capture of an evader is checked according to the following expression:

$\begin{matrix} \forall cell, adjacent_cell (e, cell) \\ = true \land Occupation (cell) \\ = true \Rightarrow capture (e) = true \end{matrix}$ (6)

In relation to PSO algorithm, we have seen the usefulness to consider each possible coalition formation as a particle. Knowing that the particle changes each position according to its velocity at each iteration, this fact provokes the dynamism of the coalition formation according to the new pursuers’ positions. Also, the number of used particles increases the coalition formation possibilities. The Global best position represents the selected pursuit coalition formation. Knowing that the global best position can change from an iteration to another allowing the dynamism of the selected coalition.

4 Pursuit-evasion algorithm based on discrete PSO algorithm

PSO is a metaheuristic algorithm that has demonstrated its performance on several continuous optimization problems. However, in some special problems such as MPMEG, the solutions are restricted to discrete values knowing that continuous version of the metaheuristics cannot be directly applied to this kind of optimization problems. Several discretization techniques are described in the literature [40]. The modification of the position’s equation is a very popular method regarding the transformation of continuous space into a discrete space by using discrete operators. In this paper, a new Discrete PSO (DPSO) is proposed and used for the PEG optimization problem with the aim of improving the performance of pursuit coalition selection. In this section, we introduce the proposed PEG algorithm based on DPSO. Through the pseudo-code showcased in algorithm 1, we detail how the PEG is inspired by the particles swarm behavior. Moreover, we explain how the personal-best of each particle as well as the global-best are updated during the different steps of the pursuit.

Algorithm: Pursuit coalition formation based on DPSO
Input: agents_position;
Capture = false;
Initialize (nbr_ρ);
Initialize (w, c₁, r₁, c₂, r₂);
Foreach particle_ido
Initialize (ρ_i);
$V_{pi}^{0}$ ← 0;
Evaluate (_⋌ρi);
Pbest_i ← p_i;
End for;
Gbest ← Max (Pbest);
While (capture = false) do
Role-attribution ();
Foreach Ag_ido
If (Role-attribution (Ag_i)=Pursuer) then
Q-learning-move (Ag_i);
Elseif (Role-attribution (Ag_i) ≠ Pursuer and Role-attribution (Ag_i) ≠ Evader) then
Random-move (Ag_i);
End_if;
End_for;
If (Adjacent_Cells (all_evaders)=“occupied”) then
Capture = true;
Update (agents_position);
Particles_velocities_update ();
Foreach particle_ido
V_i+1 ← Classification (V_i+1);
x ← 0;
While (x< V_i+1) do
y ← one_of (0 to ρ_i (length));
z ← one_of (0 to ρ_i (length));
if (ρ_i [y] ≠ ρ_i [z]) do
Permutate (ρ_i [y], ρ_i [z]);
x ← x + 2;
End_if;
End_while
Update (_⋌ρi);
If (_⋌ρi > _⋌Pbesti) then
Pbest_i ← P_i;
End_for;
If (max (_⋌Pbest) > _⋌Gbest) then
Gbest ← Max (Pbest);
End_while;
End.
Output: Capture = true;

The different algorithm’s steps can be explained in the subsections 4.1, and 4.2. In the first subsection, the particles’ encodings and initializations are detailed in addition to the particles’ fitness calculation and the pursuers’ displacement in the pursuit environment. In subsection 4.2, the particles’ velocities and the positions updates used to maintain the particles’ feasibility are explained. Finally, in subsection 4.3, a demonstration example regarding the calculation of the particles’ velocities as well as the update of their positions is provided.

4.1 Particles’ encodings and initializations

At the beginning of the PEG, the number of used particles is initialized. Knowing that each particle represents a possible coalition formation dedicated to all the detected evaders, the particles’ values are randomly generated. At the particles’ generation step, the particles are conditioned by a certain feasibility in order to be usable. With the aim of understanding the particle feasibility, we take an example where 2 evaders need successively 2 and 3 pursuers to be captured knowing that there exist 6 agents that can play the role pursuer. In this case, the coalition is structured as follows:

$ρ = [A g_{1}, A g_{2}, A g_{2}, A g_{3}, A g_{4}, A g_{5}, A g_{6}]$ (7) Each item of the coalition can take 3 different values:

$\begin{matrix} Ag = \\ {\begin{matrix} 1 & if Ag \in G r_{1} \\ 2 & if Ag \in G r_{2} \\ 0 & if Ag \notin G r_{1} and Ag \notin G r_{2} \end{matrix} \end{matrix}$ (8)

Gr₁, Gr₂: the pursuit groups regarding the capture of evader 1 and 2.

in this example, the coalition must contain the value 1 twice, the value 2 three times, and the value 0 once in order to be feasible, for example:

$ρ = [2, 0, 1, 2, 1, 2]$ (9)

After the particles’ generation, the fitness of each particle is generated according to the ability factors of each agent in relation to the role played through the concerned coalition. The fitness of each coalition (particle’s position) is calculated as follows:

$⋌_{ρ} = \frac{1}{n} \sum_{n}^{i = 1} (α . R_{i} + β . S_{i})$ (10)

n: the number of agents that can play the role pursuer.

α, β: the agent’s ability coefficients.

R: the reward ability, which is proportionally inverse to the distance between the pursuer and the concerned evader. It is calculated in the following way:

$R_{(P, E)} = R_{\max} - γ (P, E)$ (11)

γ (P, E): represents the distance between the pursuer P and the evader E.

S: the agent’s internal velocity, or how many pursuit cells the agent can cross during a pursuit iteration.

The initial coalition value of each particle known as the particle’s initial position is considered as the initial Pbest value of each particle. From the fitness of the Pbest values, the Gbest value is calculated in order to select which coalition the pursuers have to follow. The Gbest is represented by the particle with the highest fitness value.

After the coalition selection (Gbest selection), the pursuers execute a pursuit iteration according to their internal velocity. However, the agents that do not belong to any pursuit group move randomly in the environment with a specific internal movement’s velocity in order to increase the exploration of the search space. To allow the pursuers’ displacement in the environment, we have based on Reinforcement learning method known as Q-learning [39]. Via this learning method, the pursuers can maximize the expected reward at each pursuit iteration:

$\begin{matrix} Q_{i + 1} (s, a) = Q_{i} (s, a) + η_{i} [\begin{array}{l} r_{i + 1} + ƛ \max_{a^{'}} [Q_{i} (S_{1}, a^{'}), \dots, \\ Q_{i} (S_{z}, a^{'})] - Q_{i} (s, a) \end{array}] \end{matrix}$ (12)

z: the number of possible agent’s next states.

ƛ: The discount factor (ƛ ∈ [0, 1]).

η_i: The step-size sequence.

4.2 Particles’ velocities and positions updates

After the first pursuit iteration, the velocity of each particle is updated according to algorithm 2. As shown in this algorithm, the position values of each particle are compared with the personal best and the global best positions in order to estimate the difference degrees, which represent the second and the third parts of the velocity update equation (equation 03). Knowing that, the initial value of each particle’s velocity is 0 as reflected in algorithm 1.

Algorithm 2: Particles’ velocities update
Input: particles_positions;
ForeachP_ido
k ← 0;
d₁ ← 0;
d₂ ← 0;
While (k < n) do
If (P_i[k] ≠ Pbest_i[k])then
d₁ ← d₁+1;
End_if;
If (P_i[k] ≠ Gbest[k]) then
d₂ ← d₂+1;
End_if;
K ← k + 1;
End_while;
$V_{p}^{i}$ ← w* $V_{p}^{i - 1}$ +c₁* r₁ * d₁+c₂* r₂ * d₂;
End_for;
End.
Output: particles_velocities;

In order to update its position according to the principles of equation 02, each particle changes the roles of its agents according to its new velocity. However, the feasibility of each particle must be preserved. The changes’ percentage of each particle in relation to the updated velocity is calculated as follows:

$Ɣ = \frac{(V_{i + 1} * 100)}{V_{\max}}$ (13)

After that, the changes are performed according to the percentage of each particle and the maximum number of the possible changes (℧) that we can effectuate on the particle. In order to preserve the feasibility of the particle, the changes are effectuated through the permutation of the agents’ roles in the case where these roles are different. Consequently, the change number of a particle must be an even number. From the above example, we consider that the maximum of the possible changes (℧) is 6, then:

$V_{i + 1} = {\begin{matrix} 0 & if Ɣ \in [0, 25 %] \\ 2 & if Ɣ \in [25 %, 50 %] \\ 4 & if Ɣ \in [50 %, 75 %] \\ 6 & if Ɣ \in [75 %, 100 %] \end{matrix}$ (14)

From the equation (14), we can generalize the V_i+1 calculation as follows:

$V_{i + 1} = {\begin{matrix} 0 & if Ɣ \in [0, 1 * 100 % / (\frac{℧}{2} + 1)] \\ 2 & if Ɣ \in [1 * 100 % / (\frac{℧}{2} + 1), 2 * 100 % / (\frac{℧}{2} + 1)] \\ 4 & if Ɣ \in [2 * 100 % / (\frac{℧}{2} + 1), 3 * 100 % / (\frac{℧}{2} + 1)] \\ 6 & if Ɣ \in [3 * 100 % / (\frac{℧}{2} + 1), 4 * 100 % / (\frac{℧}{2} + 1)] \\ \cdot \\ \cdot \\ i & if Ɣ \in [\frac{i}{2} * 100 % / (\frac{℧}{2} + 1), (\frac{i}{2} + 1) * 100 % / (\frac{℧}{2} + 1)] \\ \cdot \\ \cdot \\ (2 n = ℧) & if Ɣ \in [n * 100 % / (\frac{℧}{2} + 1), (n + 1) * 100 % / (\frac{℧}{2} + 1)] \end{matrix}$ (15)

After that, the personal-best value of each particle is updated as well as the global-best value. Noting that the agents change their environmental position after each pursuit iteration, these updates are performed after the update of each particle’s fitness calculated according to equation (10). Each particle compares its Pbest fitness value with the fitness value of its new position. The fitness value of the new position is considered as the particle’s Pbest position if it is superior to the particle’s Pbest fitness value. in the same way, the Gbest is updated by the Pbest with the highest fitness value if it is superior to the Gbest actual fitness value according to equation (16). The update process is repeated after each pursuit iteration (Pursuers’ displacement) until the capture of the purchased evaders. An evader is considered as captured in the case where all its adjacent cells are occupied by pursuers.

$Gbest = {\begin{matrix} Gbest & if (⋌_{Gbest} > ⋌_{max (Pbest)}) \\ max (Pbest) & if (⋌_{Gbest} ⋌_{max (Pbest)}) \end{matrix}$ (16)

4.3 Demonstration example

To clarify the velocities as well as the positions updates process proposed in this section, we showcase the following example: in relation to the particle position reflected in equation (9), we assume that the Pbest position = [2, 2, 2, 1, 1, 0], Gbest position = [2, 1, 2, 2, 0, 1], and $V_{p}^{0}$ =0. Moreover, we assume that (w, c₁, r₁, c₂, r₂) are initialized by the values (1, 1, 1, 1, 1). According to algorithm 2, we can calculate the value (d₁=4), (d₂=4), and ( $V_{p}^{1}$ =8). In order to update its position of this particle, the new particle’s velocity must be classified according to equation (15) knowing that in this case, the maximum velocity is (V_max=18). From equation (13), we can deduce that the changes’ percentage of this particle is (Ɣ=44.44%). In addition, from equations (14, 15), we can classify the value of ( $V_{p}^{1}$ =2). As shown in Algorithm 1, the particle’s position update is based on the random permutation of different values of the particle. In this example, the new position of the particle could be as follows: ρ=[2, 1, 1, 2, 0, 2] after the permutation of the second and the fifth item, which are randomly chosen.

5 Simulation results

To showcase the performance of the new proposal, we have carried out the simulation experiments by using Netlogo platform 5.0.4 [41] running on Windows 8.1 64 bits, and a processor intel i5 4300M (2.6 GHz) accompanied with 12 GO of memory. The choice concerning the choose of this multi-agent platform is related to the fact that it provides a MAS environment known as patch, which allows the control of the agents’ motion. The studied case in this section is based on 2 evaders requiring each one a pursuit group formed of 4 pursuers to be captured. Knowing that, there exist 10 agents that can play the role pursuer. With the aim of specifying the simulation inputs, we have seen the usefulness of indicating the initial Cartesian coordinates of the agents in the pursuit environment as shown in Table 1. These agents are situated in 100*100 grid of cells environment and they can move in specified directions at each pursuit iteration according to a specific velocity. In these simulations, the agents’ velocities change according to role of the agent. Specifically, the agents playing the role Pursuer have a specific velocity. However, the velocity increases in the case where the agent does not play any role in order increase the dynamism chances of the selected coalition. During these simulations, the inertia (w) as well as the acceleration parameters (c₁, c₂) are used according to the original PSO principles (w = 1, c₁ ∈ [0, 1] , c₂ ∈ [0, 1]) as detailed in section 3.1 of this paper. Knowing that Metaheuristic approaches play the role of organizational models in MAS, the proposed approach is compared with two recent approaches based on organization and another game theoretic optimization method. furthermore, we note that the principles of the 3 compared cases are well discussed in section 2 of this paper:

Table 1
Agents’ initial positions

Agent Cartesian coordinate

P1 (12, 81)

P2 (66, 47)

P3 (54, 8)

P4 (94, 88)

P5 (98, 74)

P6 (94, 49)

P7 (66, 87)

P8 (14, 14)

P9 (39, 89)

P10 (94, 19)

E1 (55, 55)

E2 (50, 50)

Agent	Cartesian coordinate
P1	(12, 81)
P2	(66, 47)
P3	(54, 8)
P4	(94, 88)
P5	(98, 74)
P6	(94, 49)
P7	(66, 87)
P8	(14, 14)
P9	(39, 89)
P10	(94, 19)
E1	(55, 55)
E2	(50, 50)

Case 1: in this case, the coalition of the agents is based on AGRMF organizational model [21].

Case 2: in this case, the recent coalition formation algorithm based on YAMAM organizational model [22] is applied to allow the grouping of the agents.

Case 3: this case concerns in the game theoretic coalition formation algorithm based on the IEDS principle [23]. In order to determine the internal movement velocity of each pursuer used during these simulations, we proposer the following equation:

$Pursue r_{velocity} = {\begin{matrix} 1 cell / Pursuit_iteration & if (Pursuer \in G r_{1} \lor Pursuer \in G r_{2}) \\ 10 cell / Pursuit_iteration & else \end{matrix}$ (17)

Figure 1 represents the average capturing time obtained after 100 pursuit episodes in the four compared cases. The capturing time is reflected by the number of pursuit iterations effectuated by the pursuers in order to block the evaders’ movements. A pursuer iteration can be defined as the pursuers’ displacements from their current to other positions according to their velocities. From this figure, we can note that the capturing time decreases by 17.07%, 47,62%, and 64.17% by using the proposed approach in relation to AGRMF, YAMAM, and IEDS cases. Knowing that in the proposed algorithm, we have used 100 particles to find the appropriate coalition formation reflecting this result. The stability of the capturing time regarding YAMAM case can be explained by the fact that the pursuit groups are fixed from the first pursuit iteration to the end of the pursuit.

Fig. 1

Average pursuit capturing time obtained (Pursuit iteration).

Furthermore, we have studied the capturing time in relation to the number of used particles, as shown in Fig. 2. From the showcased curve, we can easily constate that the capturing time is proportionally inverse to the number of used particles. Also, the average capturing starts to be better than that obtained in AGRMF case after the use of only 8 particles. Specifically, the average capturing time obtained by using 8 particles decreases by 0.197% in relation to AGRMF case. From the results shown in the Figs. 1 and 2, we can prove that the number of particles as well as their velocities allow to consequently decrease the average capturing time in relation to the recent works used in the comparison study.

Fig. 2

The study of the capturing time in relation to the number of used particles.

Moreover, the pursuit capturing time in millisecond (ms) was also studied in comparison with AGRMF and YAMAM cases during 20 pursuit episodes as shown in Fig. 3. The showcased result confirms the result obtained in Fig. 1, in which the capturing time was studied in relation to the number of the pursuit iterations. Specifically, the average capturing time obtained through the application of the proposed algorithm (6197.1 ms) decreases by 36.68% in relation to AGRMF (9787 MS), and by 21.06% in relation to YAMAM case (7851.15 ms). Knowing that, we have used 100 initial particles in PEPSO case.

Fig. 3

Average pursuit capturing time obtained in millisecond.

Figure 4 shows the development of the average reward acquisition from the beginning to the end of a pursuit episode. A pursuit episode can be defined as a complete chase from the detection to the capture of the evaders. In relation to PSO principles, this figure represents the fitness development of global-best position. At the first pursuit iteration, we note that the pursuers achieve a higher average reward 47.625 through the proposed approach (PEPSO) in comparison with AGRMF (46.75), YAMAM (46.75), and IEDS (43.625). Moreover, at each iteration, PEPSO achieves a better average. This fact leads to the reach of the maximum average reward after 37 iterations, which means that the pursuers have accomplished the capture of the evaders. According to the reflected results in this figure, we can deduce that the proposed approach clearly increases the learning rate of the pursuers during the pursuit processing leading them to reach the maximum reward in minimal time in relation to the compared approaches.

Fig. 4

Pursuers average reward development.

To clarify the reward acquisition study, we have focused on the average reward obtained per pursuit iteration, calculated according to equation (18), and shown in Fig. 5. According to the results shown in this figure, we can note that there are no negative values in PEPSO case unlike in IEDS case. This fact means that the proposed approach is goal-oriented. In addition, the average reward per iteration in PEPSO case increases by 16.9%, 48.52%, and 63.23% in relation to AGRMF, YAMAM, and IEDS cases. According to the results depicted in Figs. 4 and 5, we can conclude that the number of particles and their dynamism also improve the agents’ internal development during the tasks execution.

Fig. 5

Average reward obtained per pursuit iteration.

$Ω = \frac{1}{n} * \sum_{n}^{i = 1} (R_{i}^{t + 1} - R_{i}^{t})$ (18)

t: the pursuit iteration index.

In order to study the particles’ velocity development during the pursuit, we have compared the velocity of each particle at the First Pursuit Iteration (FPI) with its velocity at the Last Pursuit Iteration (LPI), as shown in Fig. 6. At FPI, the particles achieved an average of 21% in relation to the maximum velocity value. However, at LPI, they reached an average of 60.16% in relation to the maximum value. Furthermore, we can notice that the particle number 12 achieved a velocity of 83.33% . In relation to PEG, the particle’s velocity corresponds to the degree of roles’ changes in the coalition formation. Consequently, if the particle velocity is high, then the coalition’s dynamism is strongly impacted. Moreover, the obtained results prove the performance provided by the PSO principles regarding the exploration of the search space. In some cases, we can note the decrease of the particles’ velocity. This fact is due to the use of the acceleration parameters c₁ and c₂, which can impact the particles’ velocities. knowing that, these parameters take random values between 0 and 1 at each pursuit iteration as shown in equation (03).

Fig. 6

Comparison between the particles’ velocities.

Also, we have studied the dynamism of the global-best during a complete pursuit episode, as showcased in Fig. 7. In relation to PEG, the global-best corresponds to the selected coalition formation. From this result, we can note that the selected coalition changed 10 times during the studied pursuit. These changes are based on different velocity degrees contained between 20% and 80%. At the first pursuit iteration, we note that the percentage of changes achieves 80%, which means that the 8 required pursuers are selected. However, the values 40% and 20% means that a coalition with higher fitness degree (⋌) was achieved by the proposed pursuit algorithm. The percentage determines the degree of changes (permutations) between the values of the new and the precedent global best particle.

Fig. 7

The selected coalition dynamism degree changes.

In addition, we have seen the usefulness to compare the proposed approach with a recent path pursuers’ planning method known as Theta Based Pursuer Control (TBPC) [36], which is based on finding the shortest path separating the pursuer from the concerned evader in the case where the position of this last is known. As shown in Fig. 8 where 100 pursuit episodes were effectuated comparing the proposed PEPSO to TBPC, we can easily constate that the proposed approach achieves better results than those achieved by TBPS regarding the pursuit capturing time, as shown in Table 2. This fact is due to the reason that TBPC is not equipped with a task sharing mechanism allowing the grouping of the pursuers in different pursuit groups in order to parallelly execute the multi-task problem. However, the proposed approach is equipped with a task sharing mechanism based on DPSO. Thus, we can constate that the use of coalition formation algorithms in PEG has a consequent impact on the pursuit processing even using an adequate collaborative path planning. Knowing that, a coalition formation algorithm aims to provide an

Fig. 8

Average pursuit capturing time (PEPSO vs TBPC).

Table 2

Simulation results

	AGRMF [21]	YAMAM [22]	IEDS [23]	TBPC [36]	PEPSO
Average capturing time (iteration)	45.67	72.31	105.70	54.1	37.87
Average payoff per iteration	1.13	0.70	0.50	0.85	1.36

equitable task sharing mechanism between the different pursuit groups in order to parallelly execute the multi-task problem such as MPMEG.

Finally, we have also studied the reward’s acquisition development of the proposed approach in comparison with TBPC method during a complete pursuit episode, as shown in Fig. 9. At the first pursuit iteration, we note that TBPC (51.375) reaches a better average reward in comparison with PEPSO (47.625), which is due to the reason that TBPC allows the pursuers to independently undertake the path returning the maximum reward in order to follow the shortest trajectory. After the two first iterations, PEPSO overtakes PBPC due to the goal-orientation of the approach provided via the application of the coalition formation algorithm based on DPSO. Consequently. The maximum average reward is achieved after 37 pursuit iteration in PEPSO, and after 54 iterations in TBPC case. As shown in Table 2, we can note that the average reward obtained per iteration (Ω) increases by 24.77% in PEPSO in relation to TBPC.

Fig. 9

Pursuers average reward development (PEPSO vs TBPC).

Table 2 summarizes the results obtained during the simulation experiments concerning the pursuit capturing time as well as the pursuers’ internal development analyzed in this section of the paper.

In order to provide a visualization of the pursuit environment, we have seen the usefulness to study the coverage zone degree after the pursuit processing. Figure 10 represents the initial state of the pursuit environment in which the agents are initially positioned according to the data reflected in Table 01. The green agents represent the pursuers, which have to be reached in order to perform the tasks. On the one hand, the red agents represent the pursuers that have the role to capture the evader E1. On the other hand, the blue agents are the pursuers having the role to capture the evader E2. However, the yellow agents are not yet affected and move randomly in the environment at each pursuit iteration. Knowing that, this pursuit coalition is generated according to the application of the proposed DPSO algorithm based on 100 initial particles.

Fig. 10

Pursuit environment before the pursuits’ processing.

Figure 11 reflects the pursuit environment after the capture of the detected evaders (E1, E2). The red cells represent the covered zones by the pursuers during the pursuit episode. A covered cell can be defined as a cell that has been already occupied by a pursuer. From this example, we can note that the pursuers have exactly overed 7.37% of the pursuit environment in order to perform the captures. The covered cells far from the objective cells (containing the evaders) are due to the fact that the pursuers not belonging to the pursuit groups are randomly moving in the environment with a high velocity (10 cells / iteration). According to the selected trajectories shown in Fig. 11, we can easily constate that the DPSO algorithm provides a significant goal-orientation during the coalition selection process. This goal-orientation proves that the proposed discrete PSO version avoids the selection of inappropriate particles, which is a crucial problem in continuous PSO versions.

Fig. 11

Pursuit environment after the pursuits’ processing.

In this section, we have studied the proposed approach in comparison with (04) recent approaches processing the PEG [21–23 , 36]. During these simulations, we have studied the pursuit capturing time reflected through the used pursuit iterations as well as the development of the pursuers’ acquisition rewards. From the obtained results, we can conclude that the proposed approach brings an interesting enhance regarding the processing of PE problem. Moreover, we have studied the pursuit capturing time in relation to the number of used particles (from 2 to 100 particles). According to this study, we have concluded that the capturing time decreases in relation to the number of particles’ increase. The effectiveness of the obtained results is proved by the fact that all the showcased results are obtained after an average of 100 pursuit episodes.

6 Conclusion

In this paper, we proposed a new pursuit coalition formation algorithm based on metaheuristic approach with the aim of providing an optimal and dynamic grouping of the pursuers’ agents. Specifically, we were inspired by the intelligent swarm behavior provided by PSO approach to model the pursuit problem. In relation to the Pursuit-Evasion game, the particle’s position represents a possible coalition that the agents can form to improve the chase. At each pursuit iteration, each particle is metamorphosed according to its updated velocity. Moreover, the Personal-best of each particle is updated after each pursuit iteration. The selected pursuit coalition represents the Global-best particle, which is also updated after each pursuit iteration. The global-best is updated in relation to its precedent value as well as the maximum p-best of each particle at the current iteration. The new approach is considered as discrete knowing that the particles’ items can have more than two different values. In order to reflect the impact of the proposed approach, we have effectuated comparison studies with recent coalition formation algorithms regarding the pursuit capturing time and the pursuers payoff acquisition during the pursuit processing. According to the results obtained in section 5 of the paper, we can deduce that the proposed Discrete PSO algorithm decreases the pursuit capturing time and increases the pursuers’ internal development. Furthermore, we have studied the pursuit capturing in relation to the number of used particles as well as the particles’ velocities development during the Pursuit. Specifically, the proposed approach consequently decreases the pursuit capturing time by respectively 17.07%, 47,62%, 64.17%, and 30% in relation to the compared cases shown in Table 2, which are classified among the last research activities in this field. Moreover, this approach respectively increases the pursuers’ learning rate by 16.9%, 48.52%, 63.23%, and 37.5% in relation to the latest cited research activities. In relation to the real-world application, the proposed approach can easily be applied in order to control the cooperative behavior of mobile robots or unmanned aerial vehicles during the processing of complex problem such as zone coverage or targets’ detection. Knowing that the showcased results are effectuated in the case of static evaders, the proposed algorithm should be improved in future works with the aim of reflecting the efficiency of the Discrete PSO on the Pursuit-Evasion game based on dynamic evaders. In addition, we will improve the proposed algorithm via the particles’ initialization phase in order to increase the exploration of the search space. Finally, we will focus on the particles’ velocities parameters, which are used in the current work according to the original PSO principles. In other words, we will study the impact of the inertia weight on the pursuit game, knowing that this parameter aims to balance the exploration as well as the exploitation of the search space.

References

Yan

, Jiang

, DI

et al. Multiagent pursuit-evasion problem with the pursuers moving at uncertain speeds, Journal of Intelligent & Robotic Systems 95(1) (2019), 119–135.

Nelke

S.A.

, Okamoto

and Zivan

, Market clearing–based dynamic multi-agent task allocation, ACM Transactions on Intelligent Systems and Technology (TIST) 11(1) (2020), 1–25.

Afzalov

, He

, Lotfi

et al. Multi-Agent Path Planning Approach Using Assignment Strategy Variations in Pursuit of Moving Targets. In: Agents and Multi-Agent Systems: Technologies and Applications 2021. Springer, Singapore (2021), 451–463.

Souidi

M.E.H.

, Maarouk

T.M.

, Ledmi.

Multiagent Ludo Game Collaborative Path Planning based on Markov Decision Process. In: Inventive Systems and Control. Springer, Singapore (2021), 37–51.

, Gama

, Ribeiro

et al. Graph Neural Networks for Decentralized Path Planning. In: Proceedings of the 19th International Conference on Autonomous Agents and MultiAgent Systems (2020), 1901–1903.

Amigoni

, Basilico

A game theoretical approach to finding optimal strategies for pursuit evasion in grid environments. In: 2012 IEEE international conference on robotics and automation. IEEE (2012), 2155–2162.

Von Moll

, Casbeer

, Garcia

, et al. The multi-pursuer single-evader game, Journal of Intelligent & Robotic Systems 96(2) (2019), 193–207.

Bertram

, Wei

An efficient algorithm for multiple pursuer-multiple-evader pursuit/evasion game. In: AIAA Scitech 2021 Forum (2021), 1862.

Meignan

, Koukam

and Creput

, Coalition-based metaheuristic: a self-adaptive metaheuristic using reinforcement learning and mimetism, Journal of Heuristics 16(6) (2010), 859–879.

10.

Sengupta

, Basak

and Peters

R.A.

, Particle Swarm Optimization: A survey of historical and recent developments with hybridization perspectives, Machine Learning and Knowledge Extraction 1(1) (2019), 157–191.

11.

Yar

M.H.

, Rahmati

and Oskouei

H.R.D.

, A survey on evolutionary computation: Methods and their applications in engineering, Mod. Appl. Sci 10(11) (2016), 131139.

12.

Katoch

, Chauhan

S.S.

and Kumar

, A review on genetic algorithm: past, present, and future, Multimedia Tools and Applications 80(5) (2021), 8091–8126.

13.

Yang

, Chapter 7-Particle Swarm Optimization, Nature-Inspired Optimization Algorithms 7 (2014), 99–110.

14.

Rosendo

, Pozo

Applying a discrete particle swarm optimization algorithm to combinatorial problems. In: 2010 Eleventh Brazilian symposium on neural networks. IEEE (2010), 235–240.

15.

Miao

, Yong

, Mei

et al. A discrete PSO-based static load balancing algorithm for distributed simulations in a cloud environment, Future Generation Computer Systems 115 (2021), 497–516.

16.

Ghoualmi

, Benkechkache

M.E.A.

, Draa

et al. A multi-objective optimization approach for palm vein feature selection based on the discrete PSO. In: 2021 IEEE 6th International Conference on Signal and Image Processing (ICSIP). IEEE (2021), 159–163.

17.

Zuo

, Chen

, Tan

et al. A multi-agent collaborative work planning strategy based on AFSA-PSO algorithm. In: 2019 International Conference on Robots & Intelligent System (ICRIS). IEEE (2019), 254–257.

18.

Roshanzamir

, Balafar

M.A.

, Razavi

S.N.

et al. A new hierarchical multi group particle swarm optimization with different task allocations inspired by holonic multi agent systems, Expert Systems with Applications 149 (2020), 113292.

19.

Allioui

, Sadgal

, Elfazziki

Optimized control for medical image segmentation: improved multi-agent systems agreements using Particle Swarm Optimization, Journal of Ambient Intelligence and Humanized Computing (2021), 1–19.

20.

Blamah

N.V.

, Oluyinka

A.A.

, Wajiga

et al. MAPSOFT: A Multi-Agent based Particle Swarm Optimization Framework for Travelling Salesman Problem, Journal of Intelligent Systems 30(1) (2021), 413–428.

21.

Souidi

M.E.H.

, Songhao

, Guo

et al. Multi-agent cooperation pursuit based on an extension of AALAADIN organisational model, Journal of Experimental Theoretical & Artificial Intelligence 28(6) (2016), 1075–1088.

22.

Souidi

M.E.H.

, Siam

, Pei

et al. Multi-agent pursuit-evasion game based on organizational architecture, Journal of computing and information technology 27(1) (2019), 1–11.

23.

Souidi

M.E.H.

, Piao

Anewdecentralized approach of multiagent cooperative pursuit based on the iterated elimination of dominated strategies model, Mathematical Problems in Engineering (2016).

24.

Fan

, Ruan

, Liang

et al. A pso solution for pursuit-evasion problem of randomly mobile agents. In: 2009 Chinese Control and Decision Conference. IEEE (2009), 4032–4035.

25.

Wang

, Luo

, Fang

An alliance generation algorithm based on modified particle swarm optimization for multiple emotional robots pursuit-evader problem. In: 2014 11th International Conference on Fuzzy Systems and Knowledge Discovery (FSKD). IEEE (2014), 886–891.

26.

, Yang

, Ge

et al. Coalition formation in multi-agent systems based on improved particle swarm optimization algorithm, International Journal of Hybrid Information Technology 8(3) (2015), 1–8.

27.

, Kim

, Ahn

and Choi

H.L.

, PSO-based Optimal taskallocation for cooperative timing missions, IFAC-Papers On Line 49 (2016), 314–319.

28.

, Liu

, Li

et al. Multi-task allocation with an optimized quantum particle swarm method, Applied Soft Computing 96 (2020), 106603.

29.

Zhang

, Yang

, Su

et al. Using binary particle swarm optimization to search for maximal successful coalition, Applied Intelligence 42(2) (2015), 195–209.

30.

Guo

, Xin

, Chen

et al. Multi-agent coalition formation by an efficient genetic algorithm with heuristic initialization and repair strategy, Swarm and Evolutionary Computation 55 (2020), 100686.

31.

Mousavi

, Afghah

, Ashdown

J.D.

et al. Use of a quantum genetic algorithm for coalition formation in large-scale UAV networks, Ad Hoc Networks 87 (2019), 26–36.

32.

Liu

, Wang

, Liu

et al. Multi-task Allocation of Multi-UAV Coalition Based on Improved Quantum Genetic Algorithm. In: 2021 40th Chinese Control Conference (CCC). IEEE (2021), 1802–1807.

33.

Fang

, Wang

, Xie

et al. Cooperative pursuit with multi-pursuer and one faster free-moving evader, IEEE Transactions on Cybernetics (2020).

34.

Wan

, Wu

, Zhai

et al. An Improved Approach towards Multi-Agent Pursuit–Evasion Game Decision-Making Using Deep Reinforcement Learning, Entropy 23(11) (2021), 1433.

35.

, Cruz

J.B.

Jr and Schumacher

C.J.

, Stochastic multi-player pursuit–evasion differential games, International Journal of Robust and Nonlinear Control: IFAC-Affiliated Journal 18(2) (2008), 218–247.

36.

Zhang

, Prorok

, Bhattacharya

Pursuer Assignment and Control Strategies in Multi-Agent Pursuit-Evasion Under Uncertainties, Frontiers in Robotics and AI (2021), 262.

37.

Kennedy

, Eberhart

Particle swarm optimization. In: Proceedings of ICNN’95-international conference on neural networks. IEEE (1995), 1942–1948.

38.

Shi

, Eberhart

Amodified particle swarm optimizer. In: 1998 IEEE international conference on evolutionary computation proceedings. IEEE world congress on computational intelligence (Cat. No. 98TH8360). IEEE (1998), 69–73.

39.

Tashakori

Survey on Multi-Agent Q-Learning frameworks for resource management in wireless sensor network, arXiv preprint arXiv:2105.02371, 2021.

40.

Krause

, Cordeiro

, Parpinelli

R.S.

et al. A survey of swarm algorithms applied to discrete optimization problems. In: Swarm Intelligence and Bio-Inspired Computation. Elsevier (2013), 169–191.

41.

Gunaratne

and Garibay

, NL4Py: Agent-based modeling in Python with parallelizable NetLogo workspaces, SoftwareX 16 (2021), 100801.

A discrete particle swarm optimization coalition formation algorithm for multi-pursuer multi-evader game

Abstract

Keywords

Nomenclature

1 Introduction

2 Related work

3 Background

3.1 Particle swarm optimization algorithm

4.1 Particles’ encodings and initializations

5 Simulation results

Table 1 Agents’ initial positions Agent Cartesian coordinate P1 (12, 81) P2 (66, 47) P3 (54, 8) P4 (94, 88) P5 (98, 74) P6 (94, 49) P7 (66, 87) P8 (14, 14) P9 (39, 89) P10 (94, 19) E1 (55, 55) E2 (50, 50)

References

Table 1
Agents’ initial positions

Agent Cartesian coordinate

P1 (12, 81)

P2 (66, 47)

P3 (54, 8)

P4 (94, 88)

P5 (98, 74)

P6 (94, 49)

P7 (66, 87)

P8 (14, 14)

P9 (39, 89)

P10 (94, 19)

E1 (55, 55)

E2 (50, 50)