A Two-Layer Task Allocation Algorithm for Search and Rescue under Communication Constraints

The task allocation of search and rescue tasks in post-disaster scenarios constitutes a complex scheduling challenge under communication constraints, considering mobility of targets, connectivity maintenance between agents executing tasks and the search and rescue center, and assignments for heterogeneous tasks. This paper proposes a two-layer task allocation algorithm comprising a task determination layer and an agent allocation layer. In response to the mobility of targets and the constraint of short communication distance, polynomial fitting is used for trajectory prediction of targets and a firework-merging fireworks algorithm (MFWA) is proposed to determine the number and positions of agents as communication relays in the task determination layer. To allocate heterogeneous tasks to heterogeneous agents, a neighborhood-exchange particle swarm optimization (NPSO) is proposed in the agent allocation layer. Experiments demonstrate the favorable results of the algorithm in various scales of scenarios, with MFWA requiring fewer computational resources and NPSO exhibiting advantages over the original discrete particle swarm optimization, binary particle swarm optimization, and genetic algorithm.