Multi-Robot Motion Coordination In Complex And Dynamic Environments

With the development of DAI(Distributed Artificial Intelligence), someresearchers applied Multi-agent theories to Multi-robot system (MRS) and began toresearch Multi-robot technologies. Compared with a single-robot system, amulti-robot system involves some advantages as follows: wider application fields,inherent parallelism, higher efficiency, robustness, easier and cheaper to build,distributed sensor and cooperation, scalability, beneficial to study swarm intelligence.Accordingly, more and more researchers are interested in multi-robot systems.In the past two decades, multi-robot systems have improved greatly in theoryand application. Nowadays, MRS is applied in various fields, such as the cleanup oftoxic waste, planetary exploration, search and rescue missions, surveillance,cooperative transportation. With the increasing requirements, MRS will be applied tobroader fields. In following years, the major research directions on MRS will focuson enlarging the number of robots, improving the cooperation ability, studying theswarm intelligence. Environments of MRS will be changed from certain, structuredand static to uncertain, unstructured and dynamic. The results of study will beomereal applications. Therefore, it is very important to research MRS used into thecomplex and dynamic environments.This paper studies multi-robot motion coordination in an complex and dynamicenvironment based on object transportation domain. The main research work aboutthis dissertation is as follows:1. Propose a hybrid architecture for large-scale multi-robot systems. Thisarchitecture is composed of two sections. The hierarchical control of the architectureonly serves as task level while motion level of the robot adopts distributedarchitecture. Robots can plan motions and accomplish missions autonomously.During executing task, a robot can communicate with neighbor robots to coordinatetheir motions. The control information on task level is relatively little so that thecomputational load is low. Therefore, the proposed architecture can be applied to alarge-scale autonomous robot system. A coordination mechanism combined explicit communication and blackboard isput forward for above architecture. The explicit communication is used for the taskassignment and motion coordination with local robots. Blackboard is used for thefeedback of the task executive state. Because the task executive state should be fedback real-time, there is a lot of feedback information. After using blackboard,executive robots write state information real-time while other robots accessinformation based on requirements so as to reduce the communication load greatly. 2. Study multi-robot motion planning. Motion planning is one of most importantresearch issues in this paper. In many such applications of MRS, the basic demand isthat all robots are able to move from initial to goal positions efficiently, withoutcollisions with obstacles and other robots. The multi-robot motion planning iscomplicated by the presence of a dynamic environment in which obstacles and otherrobots are moving. It is a new and independent issue but not simple addition ofsingle-robot motion methods. This paper studies a large-scale MRS. In order toreduce the computation load, decoupled planning is adopted. That is, every robotplans own path and then resolves path conflict. Firstly, the path planning method based on GA (Genetic Algorithm) isproposeGA embodies complicated object by simple encoding and reproducingmechanism. Because GA is not confined by search space, it is able to applied tovarious fields, such as engineering optimization, autonomous control, patternrecognition, machine learning. The disadvantage of GA is slow so as to takes solarge memory space and much run time to evolve a lot of plans. Some improvementto GA is given in this paper. Chromosome is denoted by dynamic data structure–Linklist. The performance of the Genetic Algorithm has been increased greatly byusing knowledge-based operators and some active constraint is added to create aninitial population. The improved Genetic Algorithm satisfies real-time demand andcan be used on-line. Afterwards, a multi-level conflict resolution method is put forward. Thismethod adopts some simple rules to coordinate path and avoid obstacles. Simulationresults show that the effect of this method is good and it can be used in large-scalerobot systems. 3. Build a distributed multi-robot simulation system based on C/S structure.Because robot usually is expensive, simulation is necessary to research the robotsystem. After the algorithm is verified in simulation system, it can be applied to areal system to protect robots. Especially, simulation is necessary for a multi-robotsystem in complex and dynamic environments. Accordingly, the development of adistributed multi-robot simulation is discussed in this paper. This system cansimulate a multi-level robot system. Server is a central station and responsible forreceiving and assigning task. In addition, central station serves as a global monitor toshow the executive state of the system. The main thread of client side serves as agroup control robot and is responsible for assigning task received from the centralstation to an executive robot including this group. Other threads of client sideinstantiate executive robots. Each thread denotes a robot. After assigned a task,executive robots plan motion and accomplish task autonomously. The simulationsystem is developed based on Agent techniques and programmed with JAVA so thatit can run on various OS. Therefore, this simulation system is fit for large-scale robotsystems. 4. Extend KQML according to KQML syntax. Some performatives andcorresponding semantic parser are defined in JAVA. The extended KQML is appliedto the multi-robot simulation system and complete communication between robots. Due toutilizing KQML protocol , the openness and compatibility of the simulation system is...