Path Planning Algorithm Of Multiple Robots In Warehouses

With the gradual development and maturity of e-commerce,warehousing system has become an important part worthy of people's attention.In order to improve the efficiency of picking and save manpower and material resources,the use of multiple robots for cargo transportation in warehouses is significantly more advantageous than manual transportation.Therefore,an efficient path planning algorithm of multiple robots for warehouses plays a crucial role in improving the overall productivity of the warehousing system.In this paper,a dynamic k shortest path planning algorithm based on time windows is proposed for the path planning of multiple robots in warehouses,which solves the problem of low real-time performance and system efficiency in the traditional path planning algorithm based on time windows.On the basis of this,this paper takes the disturbance factors such as motion delay of robots into consideration,and proposes a local path planning algorithm based on dynamic priority.Compared with the previous planning algorithm based on homotopy classes,the proposed method achieves the results that system efficiency is improved and the real-time performance is guaranteed.In order to resolve the problem of low efficiency and low real-time performance of traditional multi-robot path planning algorithm,this paper designs a dynamic k shortest path planning algorithm based on time windows for multiple robots.Firstly,from the viewpoint of warehousing environment,the mathematical model of the warehousing system is established.By making use of the structural characteristics of the warehousing system,the new map elements in the warehousing environment are defined.Aiming at the problem of low real-time performance of traditional methods based on time windows,a time-efficient insertion method of time windows is designed to improve the real-time performance of the path planning algorithm for multiple robots by making use of the space relationship of the designed map elements.Aiming at the problem that there would be deadlocks among multiple robots,this paper designs five operators for time windows to ensure that there are no deadlocks and conflicts.Furthermore,in order to solve the problem of low system efficiency in the previous methods based on time windows,this paper optimizes paths with k shortest path planning algorithm and dynamic path planning algorithm based on time windows for multiple robots.The simulation results verify the availability,better real-time performance and scalability of the proposed algorithm.And the efficiency of the system is improved compared with the previous methods.Aiming at the problem of system breakdown brought about by the delays of robots in the warehousing system and that the predecessors' methods can not solve the contradiction between improving system efficiency and ensuring the real-time performance of the algorithm,this paper designs a local path planning algorithm based on dynamic priority for multiple robots when there are delays of robots happening.The algorithm adopts a dynamic priority-based algorithm framework.Aiming at the problem that deadlocks still occur among multiple robots in predecessors' algorithms,this paper adopts the shortest path planning algorithm to generate local adjustable paths by distinguishing the influenced robots and introducing the local delay space.Furthermore,this paper uses local path planning algorithm based on time windows to generate deadlock-free and conflict-free paths for multiple robots.In view of the problem of the decrease of system efficiency caused by the path planning algorithm based on homotopy classes,this paper guarantees the efficiency of multi-robot system by introducing the local delay space and planning local adjustable paths.Aiming at the problem of high computation complexity in the re-planning algorithm,this paper designs a local path planning algorithm based on time windows and introduces the planning principles of the first and last time window to ensure the real-time performance of the designed algorithm.The simulation results validate that the efficiency of the system is improved compared with the previous method and the real-time performance is guaranteed.