The Modeling And Design Of Selforganized Multi-robot System On Task Allocation

Using robots is a potential way to solve the increasing cost of human resources. In recent years, the research of robotics has entered a new stage where the focus has shifted from complex single robot to multi-robot system which consists of many relative simple robots. In multi-robot systems the system which is composed of a large number of simple robots is called swarm robotic system. To give a full play to the superiority of the multi-robot systems the problem of coordination difficulties among multiple robots has to be solved.Multi-robot task allocation belongs to the task planning layer which is the highest level in the intelligent multi-robot coordination. In traditional MRTA the central and distributed methods have shortcomings of poor robustness and scalability, and the requirement on communication is too high. In addition, most researches on MRTA only carry out simulations rather than physical experiments based on real robots. Self-organized method has advantages of good scalability, simple control, and high flexibility, while it still has three open problems which may have no standerd answers: 1) the lack of formal description of self-organized system; 2) to predict high collective behavior of self-organized system based on local individual rules is a challenge; 3) the self-organized system is short of reliable method of performance analysis. Inspired by these three problems, under the background of task allocation this thesis studies the modeling and design of self-organized multi-robot task allocation. By imitating the emerging mechanism of swarm intelligence originated from the social species, the predictive and microscopic model that the task allocation of N types of tasks of self-organized multi-robot is built. The task allocation prototype system using behavior-based design method is constructed from bottom to up. Finally we put forward a macroscopic swarm analytic model.This study is an interdiscipline of robotics, biological science, and applied mathematics. Its main purpose is to satisfy the demand of the most senior level in multi-robot coordination---the task planning and coordination level, so that a number of mobile robots can divide labor and work together in a parallel and coordinated way, and can complete the predefined collective behavior objectives in a more effective way. The main contributions of this dissertation are summarized as follows:1. In the context of the robot vision system, the image processing pipeline method is proposed. In order to solve the problem that reduces the response speed and information accuracy of vision sensor caused by the large amount of image data, we propose a cascade information acquisition model based on image processing pipeline. It includes four modules: 1) the image pyramids module to reduce the resolution of raw images; 2) the back projection module to do object segmentation, where the threshold method and image morphology are introduced to increase the information processing accuracy; 3) the bounding rectangle module to extract object; 4) the behavioral information creating module to do localization and statistics of objects.2. In order to solve the problem that the actuator and sensor information do not match sometimes in the traditional Sense-Plan-Act mode, we propose an improved individual behavior control method based on the subsumption architecture. The C-S-B behavior releasing mechanism is proposed, which includes: the conflict resolution rule based on behavior suppression, C-S-B relational mapping, and the framework topology based on priority level. The experiments show that our strategy can deal with the information from visual, infrared, and pressure sensors simultaneously and timely, and meanwhile eliminate their conflicts.3. An expandable model for self-organized multi-robot task allocation based on statistical physics and stochastic process is constructed. The master differential equation set that models the task allocation dynamic is established, and the theories of eigen-value and differential equations are used to obtain the closed form expressions describing the time evolution of probability vector of robot task allocation, and its steady-state expression is derived.4. A fully parametric task allocation model which is proved correct using state space theory is constructed. A markov model of task allocation for arbitrary finite number of states N is proposed. A self-organized local optimal task allocation algorithm(SOLOA) to fulfill task allocation in a fully distributed way is presented. Compared with other bench algorithms, SOLOA increases the parallelism, shorten the time consumption to complete all tasks, decreases the collision rates among robots.5. A macroscopic analytic model for multi-robot task allocation is constructed, where a tool to understand the relationship between the systematic performance and the model parameters is provided. Quasi-birth-and-death process model is employed to model the dynamics of the state of the whole swarm directly. We introduce matrix analytic method to swarm robotics to derive the statistic law that the collective task allocation results obey. Synthesizing quantitative and qualitative analysis we can conclude that the positive effect of collective task allocation behavior is the expectation of binomial distribution, and the negative effect is its variance, and the increase of system scale can reduce the variance of the result of task allocation.Finally, we conclude this dissertation and point out the future work.