Research On Multi-Robot Path Planning And Task Assignment In Obstacle Environment

Compared with a single-robot system,the multi-robot system has the advantages of parallelism,reliability,strong robustness and so on,and it can accomplish various tasks more efficiently.At present,multi-robot system have been widely used in various fields,such as automobile manufacturing,intelligent security,mil itary patrol and so on.However,the research of multi-robot-system is also facing some difficulties and challenges.For example,the task assignment has become a difficu lt problem in the research of multi-robot system,and it should be solved urgently.In this paper,the research on path planning and task assignment is carried out in the multi-robot system with obstacle environment.In this thesis,An improved A* algorithm for robot path planning is proposed.In the improved A* algorithm,the 5*5 domain expansion is used to replace the traditional 3*3 domain expansion method,which expands the scope of the current nodes and reduces the limitation of path direction.In addition,the path is smoothed.By removing the redundant intermediate nodes between the two nodes,and then connecting the remaining nodes into line segments,the smooth path is finally obtained.Some simulation experiments are carried out,and it turns out that the improved A* algorithm for robot path planning is beneficial to reduce the length of the path,reduce the number of turns,improve the smoothness of path,and find a more optimized path.In this thesis,a multi-robot task assignment method based on the improved genetic algorithm is proposed to solve the multi-robot task assignment problem.Firstly,The chromosome is coded with ring coding method.In a multi-robot system with m robots and n tasks,the random arrangement of m+n integer,which is from 1 to m+n,represents a chromosome.Then,the first part of the chromosomes is connected with the tail to form a ring chromosome,which can solve the problem of how the tasks should be assigned to the corresponding robot and the performing task order of robot.Secondly,a heuristic operation and inverted mutation operation are used to improve the quality of the solution in the population,which is beneficial to the search of the optimal solution.In addition,the parallel structure is used by dividing a large population into several sub populations randomly and evenly,so that each sub population perform genetic operations at the same time,such as selection,crossover,and mutation,which is helpful for reducing the running time of the algorithm and improving the efficiency of the algorithm.Finally,a lot of simulation experiments have been conducted,and it shows that the improved genetic algorithm for multi-robot task assignment can get smaller system cost,faster convergence rate,and shorter running time of the algorithm than the traditional g enetic algorithm,which verifies the feasibility and the effectiveness greatly of the proposed genetic algorithm for multi-robot task assignment.