Swarm-GAP: A Swarm Based Approximation Algorithm for E-GAP

Abstract

Coordinating e orts of teams of professionals to search and rescue victims of emergency situations is a key point in dis- aster management. The disasters scenarios have been mod- elled as a distributed and large scale Extended Generalized Allocation Problem (E-GAP).We propose a novel algorithm to approximate the solution of E-GAP based on the theoret- ical division of labor models from colonies of social insects (swarms), called Swarm-GAP. This algorithm uses a proba- bilistic decision model, based on the social insects tendency of performing certain tasks. Each agent has an individual threshold used together with a stimulus associated with the tasks to compute that tendency. The Swarm-GAP means low communication and uses simple mechanisms. We show that the Swarm-GAP achieves rewards very close to the ones achieved by a greedy centralized approach.