IEEE Access · 2020 · 60 citations · 23 references
ComputingComputer ScienceArtificial IntelligenceDistributed SystemsOptimizationDistributed AlgorithmsGreedy AlgorithmsMetaheuristic OptimizationMulti-agent SystemsMulti-objective OptimizationMultiobjective OptimizationEnergy ConsumptionGreedy HeuristicsLocal SearchLocal Search AlgorithmsMany-objective OptimizationMulti-objective Evolutionary AlgorithmsMulti-objective Evolutionary ComputationNp-hardness
Task allocation is a key issue in multi-agent systems, and finding the optimal strategy for task allocation has been proved to be an NP-hard problem. Existing task allocation methods for multi-agent systems mainly adopt distributed full search strategies or local search strategies. The former requires a lot of computation and communication costs, while the latter cannot ensure the diversity and quality of solutions. Therefore, in this paper, we combine a distributed many-objective evolutionary algorithm called D-NSGA3 with a greedy algorithm to search the task allocation solutions, and we comprehensively consider the constraints related to space, time, energy consumption and agent function in multi-agent systems. Specifically, D-NSGA3 is used to optimize multiple objectives simultaneously so as to ensure the search capability and the diversity of solutions. Alternate search between D-NSGA3 and the greedy algorithm is conducted to enhance the local optimizing ability. Experimental results show that the proposed method can effectively solve large-scale task allocation problems (e.g., the number of agents is not less than 250, and that of tasks is not less than 1000). Compared with the existing work called MSEA, the proposed method could achieve better and more diverse solutions.
23
Kalyanmoy Deb, Himanshu Jain · IEEE Transactions on Evolutionary Computation · 2013 · 6.8K citations
Methods for task allocation via agent coalition formation
Onn Shehory, Sarit Kraus · Artificial Intelligence · 1998 · 1.1K citations
Adopt: asynchronous distributed constraint optimization with quality guarantees
Pragnesh Jay Modi, Wei‐Min Shen, Milind Tambe et al. · Artificial Intelligence · 2004 · 762 citations
Coalition structure generation with worst case guarantees
Tüomas Sandholm, Kate Larson, Martin Andersson et al. · Artificial Intelligence · 1999 · 743 citations