Task Scheduling And Path Planning In Mobile Robot Fulfillment Systems

In recent years,a new type of storage system(Mobile Robot Fulfillment System,MRFS)which uses movable shelves has attracted widespread attention from industry and academia.MRFS is a parts-to-picker storage system where AGVs bring movable racks to workstations,and after picking operation the racks will be moved back to the designated locations.Scientific and reasonable task scheduling and path planning are of great significance for the system to improve efficiency and reduce costs.However,the research on scheduling and path planning in MRFS is extremely limited.This thesis focuses on the problems of task scheduling,routing and multi-AGV conflict-free path planning in the system.For the task scheduling and path planning problems in MRFS,mathematical models are established,and a variety of methods are proposed.Computational experiments are conducted to evaluate the performance of these methods.The mathematical models and algorithms described provide theoretical basis and solution for task scheduling and path planning in MRFS.The main research works and results are as follows:(1)For the task scheduling problem in MRFS,a mixed integer programming model is constructed with the goal of minimizing the maximum completion time,and two heuristic rules and algorithms for approximate solutions are proposed.Results of computational experiments show that these heuristic solution procedures can solve design instances of three different scales quickly.Simulated annealing algorithm can generally produce the best schedules,followed by ant colony optimization algorithm.In addition,the shortest setup time first rule can quickly obtain a good schedule.(2)To solve the routing problem in MRFS,firstly,a method based on traditional A* algorithm is proposed,and then a method based on improved A* algorithm considering task priority and utilization frequency of path nodes is further designed.Finally,a Markov decision process describing the problem is established,and a method based on Q-learning is proposed.Results of computational experiments show that these algorithms can quickly solve the problem.The methods based on the traditional A* algorithm and Q-learning can both obtain the shortest paths,and the method based on improved A* algorithm can effectively balance the traffic flow and significantly reduce the number of potential collisions.(3)In order to solve the multi-AGV conflict-free path planning problem in MRFS,firstly,the conflict types between AGVs in MRFS are introduced.A Markov decision process is established to describe the problem,and then two methods based on deep reinforcement learning are proposed.Results of computational experiments show that the proposed methods can obtain feasible schedules and effectively avoid the collision and deadlock problems between AGVs,and the average performance of DQN is better than DDQN.