Research On Problems Of Multi-robots Path Planning Under Complicated Environment

Multi-robot path planning problem is not only the core content of robot navigation but also is the key and difficult issues in robotics.Path planning problem for multiple mobile robots under complicated environment refers to find an optimal and collision-free path for each robot from the start point go the goal point in a workspace with static and dynamic obstacles.So far,most of existing researches on the multi-robot path planning problem are under known environment without dynamic obstacles or limited in 2 dimensional environment with some dynamic obstacles,while for the 3 dimensional environment for multi-robot system,is still a difficult problem that need to be solved.For this reason,this paper aims to solve the multi-robot path planning problem with static and dynamic obstacles by using particle warm optimization(PSO)algorithm.And an effective collision forecasting and an collision avoidance strategy,which help to solve path planning problem,are presented in this paper.During the procedure of the research,we make full use of the characteristics of rapid solving rate,strong global optimization ability of PSO,and combine with the multi-process computation of multi-core CPU technology,and the efficiency of the algorithm has improved more.Besides,for the environment that has high demand of real-time reaction,we also introduced rolling window strategy.The research is developed according to the order of “Environment Modeling-Algorithm Improvement-2D Path Planning-3D Path Planning”,and the logic of “First theory then application,first static environment then dynamic environment”.The main research contents and achievements include:First,for the shortcomings of solving path planning problem using particle swarm optimization,an improved particle swarm optimization algorithm based on social behavior is presented.In order to guarantee the good performance of PSO,the optimization principal is first analyzed,the function and affect of the parameters are studied.Then,with the application background,we listed the shortcomings of the standard PSO,and presented our improved PSO based on social-behavior.In our method,“the worst particle” is introduced,which overcomes the disadvantage of the standard PSO that easy to fall into local optimum,and the flow chart of our new algorithm is also presented.Last,we compare our method with standard PSO by optimizing 20 benchmark functions,the results show our competitiveness of our method.Second,we discussed the environment modeling and collision-avoidance strategy for multi-robot path planning.A suitable model for the environment is the first necessary step before path planning,the quality of the feasible path is also decided by the match level of the model and path planning algorithm.The common used models that used in path planning are presented in the thesis,and the advantage and disadvantage is also discussed.Besides,we discussed four situations of the multi-robots collision avoidance strategy,and explained the collision forecasting strategy and collision avoidance strategy between robots and known movement direction obstacles and unknown movement direction obstacles,and the cooperative collision forecasting and cooperative collision avoidance strategy among other robots in details.These strategies gave the theory support for the later use of the thesis.Next,2D and 3D real time path planning by improved PSO algorithm.2D environment and 3D environment are totally different,so two different models are used in this thesis.For 2D environment,in order to improve the calculating rate,parallel lines division method is used;while for the 3D environment,2D grid decomposition method is used,each element of the grid is the elevation value of the terrain.Then,the global optimum path is generated using the improved PSO that combined with parallel computation process.Two different fitness valuation functions are also presented in order to better match our proposed method.After the generation of the global path for each robot,the rolling window procedure is acted,and the robot moves one step in the rolling window,unless it reaches the goal point.Last,under MATLAB simulation environment,the simulation results for multi-robot path planning problem under 2D/3D static and dynamic environment are presented separately.We compared the feasible path and fitness value of the path with standard PSO,and proved the feasibility of our method and provided theory references for multi-robot path planning problem in complicated environment.