The Research On Task Allocation And Load Balancing In Multi-Agent Systems Considering Task Characteristics

There is a high significance in the research on task allocation and load balancing in multi-agent systems. Most previous scholars focus on either agents’ individual attributes or multi-agent sytems’ topological structure, ignoring the influence of task characteristics. Hence, this issue mainly studies the influence of tasks’ relationship on task allocation and load balancing systematically. We focus on three types of task characteristics which are similarity, locality and dependency and propose responding allocation algorithms aiming at improving the system efficiency. The main work is as follows:Firstly, task similarity refers to the approaching degree of tasks’ required resources’types and quantities. It can avoid repeated calculation when allocating arriving tasks based on the experience of historical similar tasks. The Q value table in Q-learning is applied to store the allocation result of historical tasks in this chapter and the action selection when allocating arriving tasks is according to its similarity to stored historical tasks in the Q value table. Experimental results show that the algorithm can effectively improve the system utilities and reduce the computational cost of allocating tasks.Secondly, task locality refers to the smooth characteristics of the task arrival sequences, namely the tasks arrive stably, incrementally or degressively. Emplying the local task sequences when predicting future tasks’ arrival strength can obtain a more accurate result than employing the global task sequences. This chapter adopts a window mechanism which records the local information of task arrival process and puts forward to an improved exponential smoothing methods to calculate the arrival strength of future tasks. Considering this factor in the period of task allocation can achieve dynamic load balancing. Experimental results show that the load balancing factor can decrease the task completion time effectively.Finally, the arriving tasks in the actual systems sometimes have the data and time dependencies. The data dependency means that there is data transmission among tasks and the time dependency indicates that a task must start executing within specified time steps after another task completes executing. This chapter focuses on this kind of tasks and adopts a heuristic algorithm based on the earlies/latest execution time and communication cost, which allocates the task to the agent owning the highest heuristic value according to the topological order of task dependency gragh. Experimental results show that the proposed algorithm can reduce the communication cost among tasks and improve the success rate of task allocation effectively.