Market-based Approsch To Multi-Robot Task Allocation

Multiple mobile robot systems can be used to execute many stuffy, heavy, complex, and dangerous tasks instead of human being in many fields, such as industry autonomous production, national defense, and science research etc. Through using multiple mobile robot systems, the labors'work extensity can be lightened, the efficiency can be promoted, the casualty of human can be decreased, and the space that human being can be being is extended. Allocating tasks properly among the robots is the vital foundation to utilize the resources, and to exert the power of multiple mobile robot system. Task allocation is becoming more and more significant as the size of multi-robot system and the complexity of the global tasks increases. For any multi-robot system, optimizing the task allocation is a precondition to maximize the performance of the whole system. But in most of the cases, the computation complexity of any algorithm to optimizing task allocation is exponential to scale of the problem. Especially, as the task allocation problem is more dynamic and uncertain, it is more difficult for multiple mobile robot systems to allocation tasks within a reasonable time.Market-based approach to task allocation is robust, flexible, and scalable. The most important advantage of market-based approach is that it is suitable for distributed coordinated multi-robot systems in dynamic, uncertain environments to maximize the performance of the whole system through maximizing the individual performance.This thesis addressed some market-based approaches to task allocation, such as loosely-coupled task allocation, tightly-coupled task allocation, and dynamic task reallocation. The purpose of research is to find some new methods to improve the optimization of task allocation and task reallocation.(1) In order to prescribe the execution cost and the reward of a mobile robot that execute several tasks in turn, one kind of cost description graph was proposed. By using capability vector to show the kinds and magnitude of a robot's capability, it is very convenient to express the heterogeneousness of the system, and the requirement of given tasks.(2) Concurrency is a notable characteristic of robots in distributed mobile robot team. The optimization of global task allocation is limited if the system restricts the robots to initiate task allocation negotiation concurrently. An auction algorithm and a biding algorithm were proposed based on the contract net confirmation protocol to implement concurrent task negotiation. A kind of dynamic neighbor set was presented to determine the potential bidders as well. The method is propitious to improve the optimization of task allocation and to reduce the time to negotiate.(3) A method combining sequent single-task auction mechanism and task clustering mechanism was proposed to improve optimization of loosely-coupled task allocation of multiple mobile robot systems. The allocation process includes two phrases. The tasks were pre-assigned by sequent single-task auction in the first phrase. Then, the task manger clusters the pre-assigned tasks by using movable attractors to optimize the allocation. The proposed method needs more computation cost of O(m3) to cluster m tasks than traditional sequential single-task auction methods, and only add O(n) communication cost to the system consisting of n robots.(4) As for tightly-coupled task allocation, it can be divided into two allocation level. The firs level is to find a group of robots to execute some tasks which demand several robots tightly coordinated. The second level is to allocation the tightly-coupled subtasks to robots within a group. The problem of the first level equals to find a robot coalition to execute some tightly-coupled subtasks as a whole. Robot coalition formation problem is only addressed in the chapter four. A particle swarm optimization algorithm was proposed to form an optimized robot coalition for a given task. The results of stimulated experiments verified the presented algorithm.(5) In order to reduce the cost of computation and communication for multi-robot system to reallocate unfinished tasks in dynamic uncertain environments, a new method to estimate the dynamic extensity of the task utility value was developed based on predictive control theory. The new strategy reduces magnitude auction call and biding proposal according to simulation experiments.