Decentralised Multi-Demic Evolutionary Approach to the Dynamic Multi-Agent Travelling Salesman Problem
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.
Code (0)
등록된 구현이 없습니다.
Tasks
Evolutionary AlgorithmsSimilar Papers 제목 키워드 기반
Practical Handling of Dynamic Environments in Decentralised Multi-Robot Patrol
Persistent monitoring using robot teams is of interest in fields such as security, environmental monitoring, and disaster recovery. Performing such monitoring in a fully on-line decentralised fashion has significant pote…
Epidemic Propagation under Evolutionary Behavioral Dynamics: Stability and Bifurcation Analysis
We consider the class of SIS epidemic models in which a large population of individuals chooses whether to adopt protection or to remain unprotected as the epidemic evolves. For a susceptible individual, adopting protect…
Evolution of a Functionally Diverse Swarm via a Novel Decentralised Quality-Diversity Algorithm
The presence of functional diversity within a group has been demonstrated to lead to greater robustness, higher performance and increased problem-solving ability in a broad range of studies that includes insect groups, h…
DiversityEco-evolutionary constraints for the endemicity of rapidly evolving viruses
Antigenic escape constitutes the main mechanism allowing rapidly evolving viruses to achieve endemicity. Beyond granting immune escape, empirical evidence also suggests that mutations of viruses might increase their inte…
Balancing Common Treatment and Epidemic Control in Medical Procurement during COVID-19: Transform-and-Divide Evolutionary Optimization
Balancing common disease treatment and epidemic control is a key objective of medical supplies procurement in hospitals during a pandemic such as COVID-19. This problem can be formulated as a bi-objective optimization pr…
Evolutionary AlgorithmsMultiobjective Optimization