Research On Dynamic Task Allocation Based On MAS

Dynamic task allocation is a process of assigning appropriate tasks to appropriate members in real time, in which way it can make full use of system resources to improve the system performance. It usually consists of 2 types, i.e., reallocation type and new task type. The former type is a typical issue in closed systems and many ripe techniques have been successfully applied to it, such as dynamic load balance and various optimization algorithms etc. The latter type is an important problem in complex systems, which is characterized as distribution, openness, intelligence and sociality, and the complexity brought by inhomogeneity of the system members and the uncertainty of the environment will bring lots of difficulties to the solving of this type of problems. However, the emergence of Multi-Agent Systems(MAS) has offered a new way to deal with such dynamic task allocation problems. The MAS-Based system cannot only reveal the operation characters more effectively, it can also solve the problems that are difficult to traditional methods, with the help of the theoretic results and techniques of MAS. In addition, the research achievements, driven by practical demand, can further enrich the MAS theory and direct the operation of more complex systems. Therefore, the research on the MAS-Based dynamic task allocation shows great significance.The basic idea of this research is to discuss the issues of task decomposition, centralized task allocation and distributed task allocation with the help of theoretic results and practical methods of the existing task allocation theory after the complex system is modeled as MAS. On the basis of analyzing the characteristics of tasks and the capacities of Agents, the principles and procedures of MAS-Based task decomposition are proposed. For the centralized task allocation problems, the Markov Decision Process (MDP) Based dynamic task allocation model is constructed to guide us to get the optimized allocation policy. For the distributed task allocation problems, the extended contract net protocol (ECNP)-Based dynamic task allocation model is constructed to standardize the process of the ECNP-Based dynamic task by describing the operation frame and the flow of task allocation.MAS-based task decomposition is the preliminary preparation for the task allocation of complex system. Generally, the allocated tasks of complex system can be divided into simple tasks and complex tasks. Simple tasks can be completed independently by a single agent while complex tasks usually need to be transformed into simple tasks before allocation. After the modeling of the characteristics of tasks and the capacities of Agents, 6 principles and 5 key steps of MAS-Based task decomposition are proposed. Such decomposition cannot only offer help to solve complex problems; it also gets closer to standardized task allocation.Centralization and distribution are the two important operational modes of complex systems. For the centralized task allocation problems, we construct an MDP model to meet the demands of sequential decision-making, the goal of maximized-profits and the uncertainty of the environment. It is proved that we can get an optimal solution to the model under the limited state space and the limited action space by iterated algorithms. The simulation results indicate that the task allocation policy based on MDP is better than other myopic policies in that the MDP-based task allocation policy considers both the immediate rewards and the future rewards while those myopic policies only consider the former. Therefore, the MDP-based dynamic task allocation model can be applied to solve the dynamic task allocation problems of a long-run and small-scale system.For the distributed dynamic task allocation problems, after the construction of extended-ECNP theory, we propose our basic ideas of ECNP-based dynamic task allocation by describing the 2 level MAS-Based dynamic task allocation framework and in this way, the procedure of the announcing bidding preparation, announcing bidding, bidding and evaluating bidding is standardized. The ideas include bidding announcement based on the acquaintance's trusts, bidding based on self-adaptation, bidding evaluation based on fuzzy synthetic evaluation, the protocol of joint commitment based on limit time, and communication norms based on KQML, etc. The ideas cannot only effectively guide task allocation in the complex system in distributed environment; it can also enrich and develop the theory of ECNP.The research on the MAS-Based dynamic task allocation involves MAS,organizational theory,decision technique and many other fields, there is a long way to go to develop and perfect it. In a word, the research on the MAS-Based dynamic task allocation is not only the need of practical application; it is also the inevitable trend of the theory development. There will be more and more scholars pay attention to this subject.