Decentralised Multi-Demic Evolutionary Approach to the Dynamic Multi-Agent Travelling Salesman Problem
This addresses the need for robust, on-line optimisation in distributed multi-agent systems with communication constraints, though it appears incremental as it builds on existing evolutionary approaches.
The paper tackles the dynamic Multi-Agent Travelling Salesman Problem by using a multi-demic evolutionary algorithm to allocate tasks and plan routes for agents in real-time, achieving a decentralised solution that handles task additions and removals during simulation.
The Travelling Salesman and its variations are some of the most well known NP hard optimisation problems. This paper looks to use both centralised and decentralised implementations of Evolutionary Algorithms (EA) to solve a dynamic variant of the Multi-Agent Travelling Salesman Problem (MATSP). The problem is dynamic, requiring an on-line solution, whereby tasks are completed during simulation with new tasks added and completed ones removed. The problem is allocating an active set of tasks to a set of agents whilst simultaneously planning the route for each agent. The allocation and routing are closely coupled parts of the same problem making it difficult to decompose, instead this paper uses multiple populations with well defined interactions to exploit the problem structure. This work attempts to align the real world implementation demands of a decentralised solution, where agents are far apart and have communication limits, to that of the structure of the multi-demic EA solution process, ultimately allowing decentralised parts of the problem to be solved `on board' agents and allow for robust communication and exchange of tasks.