Multiple-Preys Pursuit based on Biquadratic Assignment Problem

Sun, Lijun1,3; Lyu, Chao2,3; Shi, Yuhui3; Lin, Chin-Teng1

10.1109/CEC45853.2021.9504823

2021

IEEE Congress on Evolutionary Computation (IEEE CEC)

978-1-7281-8394-7

2021 IEEE CONGRESS ON EVOLUTIONARY COMPUTATION (CEC 2021)

1585-1592

JUN 28-JUL 01, 2021

null,null,ELECTR NETWORK

345 E 47TH ST, NEW YORK, NY 10017 USA

IEEE

The multiple-preys pursuit (MPP) is the adversarial game between predators and preys. If the capture of a prey is defined as that it cannot move anymore due to the surrounding of predators, there are two kinds of task allocations. One is about assigning which prey to which group of predators so that all preys can be captured. The other is about assigning which capturing position to which predator to encircle the prey simultaneously. In this paper, the MPP is modeled as a dynamic optimization problem and each its time step is solved in two stages. Firstly, the first kind of task allocation problem is modeled as the biquadratic assignment problem (BiQAP) and a MPP fitness function is proposed for the evaluation of such BiQAP task allocations. In this way, the MPP is transformed to several single-prey pursuit (SPP) problems. Secondly, for each SPP, we extend the coordinated SPP strategy CCPSO-R (cooperative coevolutionary particle swarm optimization for robots) to its parallel version as PCCPSO-R to enable the parallel implicit capturing position allocating by parallel observation, decision making, and moving of predators. Through experiments of the current BiQAP solvers on the task allocation, we improve the best one of them in statistic based on the domain knowledge. Moreover, the advantages of PCCPSO-R in the capturing efficiency over CCPSO-R is testified in the MPP experiments.

multiple-preys pursuit biquadratic assignment problem (BiQAP) cooperative coevolutionary algorithm

通讯

英语

CPCI-S ; EI

Science and Technology Innovation Committee Foundation of Shenzhen["ZDSYS201703031748284","JCYJ20200109141235597"]

Computer Science ; Engineering ; Mathematical & Computational Biology ; Operations Research & Management Science

Computer Science, Artificial Intelligence ; Computer Science, Theory & Methods ; Engineering, Electrical & Electronic ; Mathematical & Computational Biology ; Operations Research & Management Science

WOS:000703866100200

20220711650683

Decision making ; Particle swarm optimization (PSO)

Computer Software, Data Handling and Applications:723 ; Management:912.2 ; Combinatorial Mathematics, Includes Graph Theory, Set Theory:921.4 ; Optimization Techniques:921.5

Web of Science

1.Univ Technol Sydney, Fac Engn & Informat Technol, Sydney, NSW, Australia
2.Harbin Inst Technol, Harbin, Peoples R China
3.Southern Univ Sci & Technol, Dept Comp Sci & Engn, Shenzhen, Peoples R China

Sun, Lijun,Lyu, Chao,Shi, Yuhui,et al. Multiple-Preys Pursuit based on Biquadratic Assignment Problem[C]. 345 E 47TH ST, NEW YORK, NY 10017 USA:IEEE,2021:1585-1592.