Multiple-Preys Pursuit based on Biquadratic Assignment Problem

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.