Research On Task Assignment For Multiple Mobile Robots Systems Based On Combinatorial Auction

The task goal search of multi-robots is one of the important directions in study of multi-robots system, and environment map can be roughly divided into three conditions: known and unknown or partially unknown, among which the allocation of task problem is a difficult problem in the process of the searching. If we set the journey as the mobile robot system consumption to evaluate task allocation of performance indicators, multi-robots searching multiple tasks can be summed up as MTSP(Multiple Traveling Salesmen Problem). Different task allocation of consumption of the whole system is often different. Fully considering the correlation and alternative between tasks, this paper adopts combination of preprocessing, and then to the combination of the generated task cluster auction to corresponding robot, adopts the method of mission objectives combinatorial auction can produce smaller system consumption, therefore multiple mobile robot system is more robust.This paper uses the combination method which is based on the improved K-means clustering algorithm, because K-means cluster is a kind of online clustering algorithm based on partition. In this paper, three algorithms is proposed for Multi-robot task searching a problem: the first kind of algorithm is KCA-I, which has redefined the task attribute vector, according to the condition of each robot to complete this task within clusters to judge whether to produce instant auction. Comparing with KCA the simulation proves that idle consumption and the total consumption can be effectively reduced. The second algorithm is improved on the combination of clustering algorithm of K-means which introduces the ideas of public sub clusters, and task within the cluster can be searched by any of the mobile robot, This idea can solve the problem of k value selection, And simulation proves idle consumption and the total consumption can be effectively reduced by a certain extent. The third algorithm is mainly aimed at the complex searching problem of multi-robot office environment, improving the maximum distance method of selecting initial cluster centers K-means task clustering algorithm, choosing the maximum distance from each other task point as the initial clustering center can effectively generate reasonable task clustering. improving the task of combination algorithm of task clusters which were auctioned to the corresponding robot. Path planning algorithm based on grid method is introduced the Gate-gird. Simulation show the mobile robot will not occur task deadlock in the process of searching, the total consumption is more lower than that based on KCA, and fully analyzed consumption with different coordinate of the mobile robots...