Machine Learning and Intelligent Communications. 4th International Conference, MLICOM 2019, Nanjing, China, August 24–25, 2019, Proceedings

Research Article

Task Allocation in Multi-agent Systems Using Many-objective Evolutionary Algorithm NSGA-III

Download
71 downloads
  • @INPROCEEDINGS{10.1007/978-3-030-32388-2_56,
        author={Jing Zhou and Xiaozhe Zhao and Dongdong Zhao and Zhong Lin},
        title={Task Allocation in Multi-agent Systems Using Many-objective Evolutionary Algorithm NSGA-III},
        proceedings={Machine Learning and Intelligent Communications. 4th International Conference, MLICOM 2019, Nanjing, China, August 24--25, 2019, Proceedings},
        proceedings_a={MLICOM},
        year={2019},
        month={10},
        keywords={Multi-agent system Task allocation Evolutionary algorithm},
        doi={10.1007/978-3-030-32388-2_56}
    }
    
  • Jing Zhou
    Xiaozhe Zhao
    Dongdong Zhao
    Zhong Lin
    Year: 2019
    Task Allocation in Multi-agent Systems Using Many-objective Evolutionary Algorithm NSGA-III
    MLICOM
    Springer
    DOI: 10.1007/978-3-030-32388-2_56
Jing Zhou,*, Xiaozhe Zhao1, Dongdong Zhao2, Zhong Lin3
  • 1: Dalian University of Technology
  • 2: Wuhan University of Technology
  • 3: Dalian Naval Academy
*Contact email: zj_0562@163.com

Abstract

Task allocation is an important issue in multi-agent systems, and finding the optimal solution of task allocation has been demonstrated to be an NP-hard problem. In many scenarios, agents are equipped with not only communication resources but also computing resources, so that tasks can be allocated and executed more efficiently in a distributed and parallel manner. Presently, many methods have been proposed for distributed task allocation in multi-agent systems. Most of them are either based on complete/full search or local search, and the former usually can find the optimal solutions but requires high computational cost and communication cost; the latter is usually more efficient but could not guarantee the solution quality. Evolutionary algorithm (EA) is a promising optimization algorithm which could be more efficient than the full search algorithms and might have better search ability than the local search algorithms, but it is rarely applied to distributed task allocation in multi-agent systems. In this paper, we propose a distributed task allocation method based on EA. We choose the many-objective EA called NSGA-III to optimize four objectives (i.e., maximizing the number of successfully allocated and executed tasks, maximizing the gain by executing tasks, minimizing the resource cost, and minimizing the time cost) simultaneously. Experimental results show the effectiveness of the proposed method, and compared with the full search strategy, the proposed method could solve task allocation problems with more agents and tasks.