Multi-robot Path Planning And Task Allocation In Obstacle Environment

Compared to single robot system,the multi-robot system performs tasks more reliably,more fast and more economically.So far,the main application fields of multi-robot system are intelligent security,searching and rescuing,monitor and patrol,environmental monitoring and so on.However,the multi-robot system still face many challenges.And task allocation is one of the thorny problems in the research filed of multi-robot system.Focusing on the multi-robot task allocation and path planning problem in the environment with obstacles,the author makes a deep research.The path information between robots and tasks is an essential anchor for addressing multi-robot task assignment problem in the present of obstacle environment.And the purpose of path planning is to find a secure,avoiding colliding,feasible path from starting point to ending point.A improved A*algorithm is proposed for the mobile robot path planning.First,the grid modeling of robot two-dimension working environment is achieved through grid method,and the original path is obtained by traditional A*algorithm.And then,the original path is partitioned by tiny step to obtain a series of path points.Finally,from the start point,the straight line is used to connect the finishing point in sequence.To decrease path length and turning angle,the path nodes will be removed if there are no obstacles existing on the lines,and the rest path nodes are reconnected by straight lines,the new path is produced successfully.Preliminary experiments results show that the modified A*algorithm proposed in this paper is capable of planning a safe and feasible path for mobile robot,and cutting down the path length and turning angle.The improved A*algorithm futher optimize primary path,and supply the path information for multi-robot task allocation.After obtaining the path information,a novel fruit fly optimization algorithm is presented to tackle with the multi-robot task assignment problem in the obstacle environment.First,to apply continuous optimization algorithm to addressing discrete problem,the integer circular coding is employed for the expression of solutions.Second,the Contingent auction method is introduced to initialize the fruit fly population locations,and to produce good solutions.Third,based on the knowledge of multi-robot allocation three operators are proposed in the smell searching stage.Adjusting the task sequences of robots,the first one is aiming at generating domain solutions.Changing the assignment of tasks,the second operator is designed to escape local optimization trap.And the third operator is used to repair unfeasible solutions.The three well-designed operators guide the algorithm to approach the best solution space.In the visual searching phase,the elitism is introduced to protect current optimum solution.If there exist a fruit fly individual better than the primary one,the population fly to the position of the fruit fly individual.Otherwise,the position of population stays the same.Through orthogonal test,the parameter of the proposed algorithm is set.And then the feasibility and efficient of the heuristic strategy initializing population position is demonstrated by contrast experiments.At last,a lot of experiment results show that the proposed method solve the multi-robot task allocation problem in obstacle environment effectively.