Research On Multi-task Assignment And Path Planning Of AGVs

Nowdays,automated guided vehicles(AGVs)are widely used in manufacturing and warehousing industries.For example,in the automated storage system,the most cost is the transportation cost of the AGV.The AGV uses the electric energy as the energy source,with reasonable scheduling strategy and good AGV path planning strategy,it can significantly reduce transportation costs and improve transportation efficiency.Therefore,this paper constructs a distributed warehousing multi-AGV system,and proposes solutions for multi-AGV task scheduling problems and path planning problems.The main innovations are as follows:(1)In the AGV task scheduling problem,given an incumbent solution with N tasks,the existing best method requires a complexity of O(N ~3)to evaluate all the O(N ~2)possible 2-opt based movements,and thus,the computational cost is too expensive,especially for large-scale instances.This paper develops a series of data structures,to reduce the above time complexity from O(N ~3)to O(N ~2).Experimental results indicate that,the proposed method can significantly improve the efficiency of 2-opt based local search.(2)In order to solve the dynamic tasks scheduling problem of AGV,this paper proposes a dynamic Monte Carlo tree search algorithm,which uses historical information to speed up the sorting process and adapt to dynamic changes in time;then,2-opt move and 3-opt move constitute the neighbors to alternately search local space,and optimize the solution generated by the dynamic Monte Carlo tree search algorithm.Experimental results show that the dynamic Monte Carlo tree search and the variable neighborhood local search algorithm can significantly improve the transportation efficiency and reduce transportation costs,thus improving the economic benefits of enterprises.(3)In order to solve the problem of multi-AGV path planning,this paper proposes a two-stage path planning method.First,a modified A*algorithm is used to plan a path for each AGV that does not collide with static obstacles.Secondly,if the AGV collides along the planned path,the AGV senses the running status of other AGVs in its two units in advance through the carried sensors,and then uses the game theory-based method to resolve the conflicts,avoids the conflict between the AGVs,and completes the tasks faster.