Multi-Robot Coalition Formation Based On Quantum Evolutionary Algorithm

Multi-robot coalition problem is a kind of NP-complete and complicated combinatorial optimization problems. The way of quantum information expression based on quantum derivative mechanism and quantum gate interference inference method is a potential feasible solution. The diversity of quantum probability coding and concurrent searching ability of quantum evolutionary algorithm make it very suitable to solve the combinatorial optimization problem. The success of applying quantum evolutionary algorithm to solve the classic combinatorial optimization problem inspires us to apply it to the robot coalition problem.In this thesis, the characteristics of multi-robot coalition problem and coalition structure generation problem has been analyzed and the current multi-robot coalition generation algorithms have been summarized and classified. The advantages and disadvantages of these algorithms have also been analyzed. It is pointed out that the combination of heuristic algorithm and evolutionary algorithm is an effective way to solve the multi-robot coalition generation problem. The quantum evolutionary algorithm is applied to the multi-robot coalition problem and coalition structure generation problem. The complexity of the problem is decreased by merging the processes of resource configuration and task distribution into one process using coding mapping. The results of contrastive experiment show that the proposed algorithm could solve the multi-robot coalition problem effectively and efficiently.The main content is as follows:(1) Multi-robot coalition and its related issues are discussed, including the presentation of multi-robot coalition problem, the formalized description of multi-robot coalition problem and the environment of coalition,the mathematical model of the problem of single coalition and coalition structure as well as the analysis of the solution space complexity of coalition problem.(2) For single coalition problem, an improved quantum evolutionary algorithm is proposed. And based on the general quantum evolutionary algorithm,"the islands model based on information positive feedback"is introduced to the algorithm for improvement. Evolutionary equation is used to update the quantum gates to ensure a faster pace of convergence, not liable to fall into the local extremum areas. The results of comparative experiment show that the algorithm we proposed in the thesis not only inherits the advantages of concurrency and robustness of the quantum evolutionary algorithm, but also advances the quality of the solution, quickens the pace of convergence and is not liable to fall into local extremum areas, the stability of the convergence is very high. Meanwhile, the algorithm is based on the islands model based on information positive feedback and uses evolutionary equation to update the quantum gates, enabling it to be more flexible, effective and have higher robustness compared to mechanism of the general quantum evolutionary algorithm, the search time and the amount of computation can be effectively reduced and the realizability is relatively good.(3) For the coalition structure problem, a coalition structure generation algorithm based on quantum evolutionary algorithm is proposed. The complexity of the problem is reduced by merging resource combination and task distribution into one process using coding mapping. According to the characteristic of the coalition structure problem, some related parts of quantum evolutionary algorithm have been redesigned while applying quantum evolutionary algorithm to find the solution. The results of comparative experiment show that the algorithm can still assure the quality of the solution in the coalition structure generation problem, quicken the pace of convergence, is not liable to fall into local extremum area, has a relatively high stability of convergence and can effectively reduce the search time and the amount of computation from the generation of coalition structure.