A hyper-heuristic constructive method for dynamic coalition formation in multi-agent systems for forest rescue

This paper investigates coalition formation in heterogeneous multi-agent systems for forest fire rescue missions, which are characterized by uncertainty and high dynamism. The system comprises agents with specialized roles, such as detection and execution. A many-objective mathematical programming model is established to holistically evaluate coalition quality, incorporating optimization metrics like compactness and stability, alongside constraints including detection/execution capabilities and coverage. To overcome the limitations of traditional iterative methods in adapting to dynamic mission evolution, a Two-Stage Hyper-Heuristic Constructive (TSHHC) algorithm is proposed. Instead of generating coalition structures directly online, TSHHC utilizes differential evolution during an offline training phase to evolve a set of constructive coalition-forming heuristics that demonstrate superior performance in convergence precision and distribution diversity along the Pareto front. During online operation, Pareto dominance relations are applied to dynamically select the most effective coalition from the outputs of these heuristics, ensuring both adaptability to the current scenario and compliance with real-time requirements. Simulations across diverse forest fire rescue scenarios show that a combination of offline-trained constructive heuristics outperforms several state-of-the-art algorithms in most test cases. This result validates its effectiveness for complex dynamic coalition formation in firefighting operations.