On scaling multi-agent task reallocation using market-based approach

Multi-agent systems (MAS) provide a promising technology for addressing problems such as search and rescue missions, mine sweeping, and surveillance. These problems are a form of the computationally intractable Multi-Depot Traveling Salesman Problem (MDTSP). We propose a novel market-based approach, called Market-based Approach with Look-ahead Agents (MALA), to address the problem. In MALA, agents use look ahead to optimize their behavior. Each agent plans a preferred, reward-maximizing tour for itself using our proposed algorithm which is based on the Universal TSP algorithm. The agent then uses the preferred tour to evaluate potential trades with other agents in linear time - a necessary prerequisite for scalability of market-based approach. We use simulations in a two dimensional world to study the performance of MALA and compare it with O-contracts and TraderBots, respectively, a centralized approach and a distributed approach. Experiments suggest that MALA efficiently scales to thousands of tasks and hundreds of agents in terms of both computation and communication complexity, while delivering relatively good-quality but approximate solutions.