Research On Multi-robot System Task Allocation And Formation Control

As a fundamental problem in the multi-robot system research domain, task allocation is becoming more and more important with the increase of system size and tasks complexity. Formation control is a geometry problem of multi-robot systems. As it is widely employed in military reconnaissance, search, mine removal, formation flight, space exploration, etc., formation control is becoming an active research topic. Therefore, this dissertation is dedicated to the two problems: task allocation and formation control.Firstly, the dissertation discusses the classification and formal description of multi-robot task allocation, and summarizes the current main methods of task allocation. The problem of multi-robot task allocation is classified and analyzed from the aspects of control framework, the dynamics of environments, communication methods, robot failure, heterogeneous, etc. The present main methods of task allocation are classified into two categories: emergent and intentional cooperative methods, main compositions of which are all discussed. From the aspect of state space, task allocation aims to reduce the dimensionality of the coordination problem by decomposing the system; while from the aspect of combinatorial optimization, it is a standard integer program problem and can be solved by Hungarian algorithm in the centralized framework.Secondly, as market mechanism is an effective rare resource configuration method, based upon the main procedure of the second price sealed bid auction method, two market based algorithms of NeA-MRTA and ReA-MRTA are proposed for the dynamic distributed simple task allocation problem. The NeA-MRTA algorithm deals with the allocation of the newly arrived tasks, which did not exist previously in the multi-robot systems. Then the ReA-MRTA algorithm reallocates tasks, which have already been allocated but may currently become inappropriate due to the change of environment caused by other auctions. Both theory analysis and simulation results indicate that the computation and communication requirements of the algorithms are reasonable, and that they are robust to part communication failure.For the problem of dynamic distributed complex task allocation, an algorithm of CA-MRTA is presented based upon the idea and main procedure of the NeA-MRTA algorithm. From the aspect of capability classification, the concept of capability vector and corresponding description methods of heterogeneous robots and tasks are presented. Based on the concept of information entropy and simple social entropy, capability entropy is defined as to measure the heterogeneous of robots and tasks described by capability vectors. A precedence order description method is proposed to deal with the tasks with dependence relationships. On the basis of the above description, the CA-MRTA algorithm can help robots accomplish tasks by intentional cooperation. Additionally simulation results show the effectiveness of this algorithm.Furthermore, a multi-robot simulation system named MRTASim is designed and implemented for the development of dynamic distributed task allocation algorithm. Compared with real multi-robot systems, this simulation system is cheaper, faster, more convenient and flexible to configuration. And in the system, the specification of each robot and task is based upon the method of the capability vector description proposed in this dissertation and their values can be set by a specific database file. Each robot is corresponding to an independent object entity and the explicit communications between robots can be designed as needed. Algorithms proposed in this dissertation are all tested in this simulation system.On the principle of the Leader-Follower method, two control algorithms named D-A and D-D controllers together with the corresponding formation tracking rules are proposed and implemented to control the formation of our NuBot omni-vision and omni-directional motion robots team. Based upon relative positioning and local communication, the proposed algorithms can implement distributed formation control of multiple robots, and can control the orientation of robots respectively. The D-A controller can switch the robot formation smoothly with high efficiency by avoiding oscillation. Two methods of formation switch and formation distortion are both proposed to deal with different obstacles. Obstacle avoidance can be achieved either through the formation switch method―changing to another formation type, or through the formation distortion method―keeping the original formation and changing it as little as possible.Finally, based upon the above research, the dissertation discusses the problem of the dynamic distributed role allocation of the NuBot robot soccer team established by National University of Defense Technology. As a classical multi-robot research and application environment, robot soccer is highly dynamic and competitive. This dissertation proposes a distributed role allocation algorithm suitable for the RoboCup middle-sized competition environment. With good robustness, this algorithm can not only satisfy the highly dynamic and competitive environment, but also select appropriate role combination and then allocate them in a distributed way with the autonomous judgment of team members'absentation, such as out of field caused by robot failure.