cs.MAOct 17, 2026

CARVS: A Congestion-Aware Algorithm for Online Multi-Agent Pickup-and-Delivery in Human-Collaborative Warehouses

Authors: Chaoran Li, Zeyuan Zhao, Shao Zhang

Organizations: Shanghai Jiao Tong University, Department of Computer Science and Engineering, Shanghai, China · Shanghai Artificial Intelligence Laboratory, Shanghai, China

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Intelligent warehouse systems have transformed logistics by integrating robots with minimal infrastructure changes, boosting efficiency and optimizing workflows compared to traditional human-only operations. However, human-robot collaboration introduces new challenges, particularly due to human uncertainty, which leads to dynamic interactions and unpredictable behavior. To address these complexities, this paper presents the Multi-Agent Pickup-and-Delivery with Human Collaboration (MAPDwHC) problem, an extension of the Multi-Agent Pickup-and-Delivery (MAPD) problem that incorporates human unpredictability. This problem adds key constraints, such as dynamic obstacles caused by robots temporarily blocking paths when interacting with humans, and the need for real-time responsiveness. We formalize the MAPDwHC problem with additional constraints and properties. Based on this problem setting, we propose the CARVS algorithm, which improves task assignment and path planning by integrating task swapping, validation checks, and random initialization. CARVS reduces congestion, enhances adaptability to human-robot interactions, and ensures real-time responsiveness. Simulation results show that CARVS significantly reduces timeouts of path planning in large-scale scenarios where traditional MAPD algorithms fail, improving both efficiency and scalability.

Figures & tables

Figure 1. An illustration of the online MAPDwHC problem, showing key features: (a, c) Robots must stay stationary during human interaction, creating dynamic obstacles . (b) Robots must avoid humans and obstacles, necessitating algorithms with real-time responsiveness . (d) Items are unevenly distributed. (e) Robots can carry multiple items. An illustration of the online MAPDwHC problem, showing key features: (a, c) Robots must stay stationary during human interaction, creating dynamic obstacles. (b) Robots must avoid humans and obstacles, necessitating algorithms with real-time responsiveness. (d) Items are unevenly distributed. (e) Robots can carry multiple items.
Figure 2. A diagram illustrating optimization methods: the picking area is blue, the packing area green, and shelves are orange. Circles represent agents, diamonds represent humans, and squares represent goal points, with arrows indicating robot targets. (a) Goal swapping reduces delays from intersecting paths. (b) Stars mark wait points for blocked agents. (c) Greedy assignment leads to congestion near the packing area, mitigated by random initial goal assignment for idle agents. A diagram illustrating optimization methods: the picking area is blue, the packing area green, and shelves are orange. Circles represent agents, diamonds represent humans, and squares represent goal points, with arrows indicating robot targets. (a) Goal swapping reduces delays from intersecting paths. (b) Stars mark wait points for blocked agents. (c) Greedy assignment leads to congestion near the packing area, mitigated by random initial goal assignment for idle agents.
Figure 3. Mean skip count on the warehouse_small map for 10 to 100 robots. A skip occurs when the planner fails to return a solution within the time limit. CARVS variants substantially reduce skips as the robot count grows. Mean skip count on the warehouse\_small map for 10 to 100 robots. A skip occurs when the planner fails to return a solution within the time limit. CARVS variants substantially reduce skips as the robot count grows.
Figure 4. The performance metrics of various algorithms across multiple warehouse configurations, which show the mean number of completed tasks across 10 random seeds as a function of agent count, ranging from 10 to 100. CARVS scales effectively with the number of agents, outperforming other algorithms. The performance metrics of various algorithms across multiple warehouse configurations, which show the mean number of completed tasks across 10 random seeds as a function of agent count, ranging from 10 to 100. CARVS scales effectively with the number of agents, outperforming other algorithms.
 Vert #Obst %Tun #Avg. LDeg-3 %
warehouse_tiny85125.385398.58
warehouse-10-20-10-2-11014343.81388.256.76
warehouse_small478566.541914.782.82
warehouse_large861179.47813.243.12
Table 1. Metrics on Map Layout
Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5. The autonomous mobile robots operating in the warehouse transport plastic totes that serve as carriers for customer orders. Each robot can carry multiple SKUs at once. Because the robots are not equipped with grippers, human workers manually place items into the totes. The merchandise is stored on shelving units and exhibits considerable variation in size, shape, and packaging. The autonomous mobile robots operating in the warehouse transport plastic totes that serve as carriers for customer orders. Each robot can carry multiple SKUs at once. Because the robots are not equipped with grippers, human workers manually place items into the totes. The merchandise is stored on shelving units and exhibits considerable variation in size, shape, and packaging.
Figure 6. Coordination in narrow aisles. During the picking phase, the tote-carrying robot in the foreground remains stationary, allowing the human picker to quickly place items into its bins. Two autonomous robots in the background detect this stationary robot and navigate around it while maintaining a safe clearance. Accordingly, the tote-carrying robot is treated as a static obstacle in our MAPDwHC formulation during human-robot interaction. Coordination in narrow aisles. During the picking phase, the tote-carrying robot in the foreground remains stationary, allowing the human picker to quickly place items into its bins. Two autonomous robots in the background detect this stationary robot and navigate around it while maintaining a safe clearance. Accordingly, the tote-carrying robot is treated as a static obstacle in our MAPDwHC formulation during human-robot interaction.
AlgorithmAgentsTasks Completed
CBSH2RTC4025±70
600
800
EECBS404,938±4,310
60775±820
80101±215
Appendix
Table 2. MAPF Algorithms Performance by Number of Agents
Figure 7. Impact of human-efficiency parameters on the performance of CARVS with LaCAM2 on warehouse_small for 10 to 100 robots. The reaction time η\eta is fixed at 1 second. Configuration D5S2 sets the interaction duration to δ=5\delta=5 time steps and assigns humans a speed twice that of the robots. Reducing the interaction duration substantially decreases the number of skips. Impact of human-efficiency parameters on the performance of CARVS with LaCAM2 on warehouse\_small for 10 to 100 robots. The reaction time η\eta is fixed at 1 second. Configuration D5S2 sets the interaction duration to δ=5\delta= 5 time steps and assigns humans a speed twice that of the robots. Reducing the interaction duration substantially decreases the number of skips.
Figure 8. Impact of human workforce size on CARVS performance on warehouse_small with 50 and 100 robots. After about 50 workers, each additional worker yields progressively smaller increases in the number of completed tasks. Impact of human workforce size on CARVS performance on warehouse\_small with 50 and 100 robots. After about 50 workers, each additional worker yields progressively smaller increases in the number of completed tasks.
More in this topic

Multi-Agent Path Finding

Multi-agent path finding (MAPF) plans collision-free routes for multiple agents sharing an environment.

See all 92 papers

Explore similar work

CardsList

  1. Dynamic Multi-Agent Pickup and Delivery in Robotic Cellular Warehousing Systems

    Jun 4, 2026Cheng Ren, Ming Li, Xinping Guan +1Multi-Agent CoordinationRobotics

    Department of Industrial and Systems Engineering, The Hong Kong Polytechnic University, Hong Kong, China · School of Automation and Intelligent Sensing, Shanghai Jiao Tong University, Shanghai, China

  2. Many-to-Many Multi-Agent Pickup and Delivery

    May 8, 2026Ethan Schneider, Jingkai Chen, Tianyi Gu +3Multi-Agent System OptimizationMulti-Robot Task Allocation

    Institute of Robotics and Intelligent Machines, Georgia Institute of Technology, Atlanta, GA 30332, USA · Symbotic Inc., Wilmington, MA 01887, USA · Northeastern University, Boston, MA 02115, USA

  3. Diffusion for Long-Horizon Multi-Robot Path Planning in Human-Shared Environments

    Jul 10, 2026Vaibhav Sanjay, Yorai Shaoul, Jiaoyang LiMulti-Robot Motion PlanningDiffusion-Based Planning

    Robotics Institute, Carnegie Mellon University