Automated Guided Vehicles (AGV) are becoming increasingly important in modern warehouses to cope with the enormous logistic demands of developing e-commerce and the growing operational costs. The key component of implementing such a system is planning the paths of a large horde of AGVs to deliver orders from shelves to packing locations. The existing solutions regard it as a Multi Agent PathFinding (MAPF) problem, but they can hardly be applied in practice because none of them could satisfy the continuous (temporal), lifelong (future task unknown and keeps appearing), kinematic (acceleration/deceleration/rotation), online (fast response), and scalability (large network, large AGV number, large task number) at the same time. Therefore, we first propose an AGV routing framework that can satisfy all these properties with its corresponding routing algorithm. Then, to improve the efficiency, we propose the Multi-Hop Conflict-Aware Search method (MHCAS) with action combination, MHSC to reduce the search space, and OHSMD to decompose motions such that routing time is reduced by three orders of magnitude. Extensive experimental studies verify the superiority of our methods compared with the state-of-the-art.

Abstract Coverage Centrality is an important metric to evaluate vertex importance in road networks. However, current solutions have to compute the coverage centrality of all the vertices together, which is resource-wasting, especially when only some vertices centrality is required. In addition, they have poor adaption to the dynamic scenario because of the computation inefficiency. In this paper, we focus on the coverage centrality query problem and propose a method that efficiently computes the centrality of single vertices without relying on the underlying graph being static by employing the intra-region pruning, inter-region pruning, and top-down search. We further propose the bottom-up search and mixed search to improve efficiency. Experiments validate the efficiency and effectiveness of our algorithms compared with the state-of-the-art method.