2023/03/07 by Yiduo Huang, Huang, Yiduo, Zuo‐Jun Max Shen +1 · 1 citation
Computer Science · Engineering · Mathematics · #Algorithm #Artificial intelligence #Assignment problem #Computer network #Computer science #Distributed computing #FOS: Computer and information sciences #FOS: Electrical engineering #Flow (mathematics) #Flow network #Mathematical optimization #Mathematics #Mobile robot #Motion planning #Online algorithm #Optimization and Search Problems #Path (computing) #Real-time computing #Robot #Robotics (cs.RO) #Sorting #Systems and Control (eess.SY) #Throughput #Traffic control and management #Transportation and Mobility Innovations #electronic engineering #information engineering #sort
paper · pdf · doi:10.48550/arxiv.2303.04070
openalex publication_date 2023/03/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Express companies are deploying more robotic sorting systems, where mobile robots are used to sort incoming parcels by destination. In this study, we propose an integrated assignment and path-finding method for robots in such sorting systems. The method has two parts: offline and online. In the offline part, we represent the system as a traffic flow network, develop an approximate delay function using stochastic models, and solve the min-cost network flow problem. In the online part, robots are guided through the system according to the calculated optimal flow split probability. The online calculation of the method is decentralized and has linear complexity. Our method outperforms fast multi-agent path planning algorithms like prioritized planning because such algorithms lead to stochastic user equilibrium traffic assignment. In contrast, our method gives the approximated system-optimal traffic assignment. According to our simulations, our method can achieve 10%--20% higher throughput than zoning or random assignment. We also show that our method is robust even if the initial demand estimation is inaccurate.