Parallel Swarm Intelligence Optimization And Its Application In Multi-Robots Path Planning

In recent years,with the development of hardware and software and the improvement of related theories,robot technology has developed rapidly.Robot path planning technology is the focus of many technologies,and multi-robot path planning is one of the difficulties,which is a field worth studying.Multi-robot path planning has been proved to be an NP problem from the point of view of task assignment.From the point of view of path planning,we need to solve problems such as path finding and obstacle avoidance.From the perspective of realistic scene,some problems such as robot dynamics constraint should be considered.Multi-robot path planning can be abstracted as a collection of multiple problems,which requires multiple algorithms to solve.This article from the perspective of global path planning,the assumption in a containing multiple tasks,multiple scene of irregular shape obstacles,to seek all robots in total travel the shortest path between task point is the primary goal of this article research,at the same time,considering the actual scene will appear task allocation imbalance caused some robot battery run out ahead of time,this article will also be more robot balanced energy consumption as the optimization goal.In this thesis,the overall train of thought to follow the dimension reduction optimization up another dimension reduction of the guiding ideology.First,the actual scene is modeled by the grid method,the useless information in the scene is ignored,and obstacles are integrated into the model to become a cost-balanced multi-weight traveling salesman.The(MTSP)problem aims to obtain a direct connection route between multiple robots and task points that satisfies basic constraints.On this basis,it is necessary to ensure that the cost of each travel path is balanced.The cost is a value of obstacle constraints and path length.This thesis proposes a hybrid particle swarm clustering-ant colony algorithm to solve this problem.During the research process,it was found that the convergence accuracy and execution efficiency could not be satisfied at the same time.According to the good parallel characteristics of the swarm intelligence algorithm,after conducting related research on GPU parallel computing,it was proposed A CUDA-based hybrid particle swarm clustering-ant colony algorithm(GPSO-AC).The algorithm uses the GPU's architecture features of multiple stream processors and single instruction multithreading(SIMT)to execute the search process of a large number of independent individuals in the algorithm at the same time.Experiments show that the execution speed of the algorithm is much faster than that of the CPU serial version algorithm,and it is also better than similar algorithms for solving MTSP problems in terms of convergence accuracy.After solving the MTSP problem to obtain the weighted path,the obstacle avoidance path generated by the A* algorithm between each task point is restored on the grid map,and the balance cost obtained by the previous algorithm is restored to the obstacle constraint.For after A *algorithm to search for the path of the turning point of too much problem,this thesis proposes A smooth grid path algorithm is used to improve the A * algorithm,the generated path at this time still does not conform to the real world A robot motion law,points in the path velocity mutation,but after A smooth path because fewer unnecessary interference node easier to combine with trajectory optimization algorithm,A trajectory optimization algorithm to generate dynamic constraints of robot motion path,can more truly simulate the robot motion state in reality.Finally,an experimental platform is built.This platform supports the creation,saving,and loading of experimental maps.This platform is used to verify a series of algorithms in this thesis.