This project is to implement the task allocation alogrithms of multi-robot task allocation (MRTA) problems.
Based on the paper of CHEN Xia and QIAO Yan-zhi
in Summary of unmanned aerial vehicle task allocation [1], the algorithms can be generally divided into 4 parts:
Centralized control system indicates that the group of UAVs (Unmanned Aerial Vehicles) are regulated and controlled by a single control center, including the signal transmission, communication between UAVs and the control commands of UAVs. The typical models are MTSP
, VRP
, MILP
, DNFO
, CMTAP
.
The common LS methods:
Dynamic List Scheduling (DLS)
, Multi-Dimensional Dynamic List Scheduling (MDLS)
, Multi-Priority List Dynamic Scheduling (MPLDS)
and so on.
Genetic Algorithm (GA)
, Evolutionary Programming (GP)
, Evolution Strategy (ES)
and Evolutionary Programming (EP)
Particle Swarm Optimization (PSO)
and Ant Colony Optimization(ACO)
Artificial Immune (AI)
, Tabu Search (TS)
and Simulated Annealing Algorithm (SA)
Distributed control system is different from Centralized control system in the way of signal transmission. The Distributed control system can allow UAVs communicated with each other in the group.
first price auctions
, Dynamic role assignment
, Trade robots
, Murdoch
, Demircf
, M+
, etc.
This method is basically combine the first 2 methods. There is a centralized control system to control several UAV groups and for each group there is a distributed control system. The structure is shown below.
Finally, the Ant Colony Optimization (ACO) and Hungarian Algorithm have been implemented.
The simulated initial map in 2D and 3D are displayed, and the detailed results are indicated in subfloders.
[1] Chen, Xia, and Yan-zhi Qiao. "Summary of unmanned aerial vehicle task allocation." Journal of Shenyang Aerospace University 33.6 (2016): 1-7.
[2] Wang, Jianping, Yuesheng Gu, and Xiaomin Li. "Multi-robot task allocation based on ant colony algorithm." Journal of Computers 7.9 (2012): 2160-2167.