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
Jun 4, 2026

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

Robotic cellular warehousing systems (RCWS) give rise to multi-agent pickup and delivery (MAPD) processes in which robots sequentially collect multiple stock-keeping units (SKUs) for each order. Unlike classical MAPD formulations that assume static tasks, real warehouse operations often involve dynamic order evolution, where new SKUs may be appended to an order while it is being executed. Motivated by this practical requirement, this letter formulates the Dynamic-MAPD problem considering internal order evolution for the first time. Building on the token passing (TP) mechanism, we propose two event-triggered online replanning algorithms. The two strategies target different robot-resource configurations, depending on whether additional robotic resources are available for cooperative assistance. The first, Dynamic-TP, enables an event-triggered dynamic response by allowing robots to replan from their current execution states through priority-aware token acquisition after order updates. The second, Cooperative-TP, further enables reserved robots to assist newly added SKUs while preserving the original order ownership. Simulation results demonstrate that the proposed methods significantly reduce order flowtime compared with static and non-cooperative baselines, thereby improving the order fulfillment efficiency in RCWS.

Cheng Ren, Ming Li, Xinping Guan +1

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

Multi-Agent CoordinationRoboticsMulti-Robot Task AllocationMulti-Agent Planning
AskPDF
May 8, 2026

Many-to-Many Multi-Agent Pickup and Delivery

Multi-robot systems in automated warehouses must manage continuous streams of pickup-and-delivery tasks while ensuring efficiency and safety. Prior work on Multi-Agent Pickup-and-Delivery (MAPD) has largely focused on the one-to-one variant, where each task has a fixed pickup and delivery location. In contrast, real warehouses often present many-to-many MAPD scenarios, where items, tracked by stock keeping unit (SKU) identifiers, can be retrieved from or stored at multiple locations, resulting in an NP-hard four-dimensional assignment problem. To solve the many-to-many MAPD problem, we contribute our algorithm: Many-to-Many Multi-Agent Pickup and Delivery (M2M). We experiment with two variants of our algorithm: one that minimizes estimated task durations (M2M), and one which incorporates SKU distribution into the objective function (M2M-wSKU). Simulation results over 8-hour warehouse operations show that our method consistently matches or outperforms prior state of the art, with M2M completing up to 22,000 more tasks on average across different environments and warehouse inventory densities.

Ethan Schneider, Jingkai Chen, Tianyi Gu +3

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

Multi-Agent System OptimizationMulti-Robot Task AllocationMulti-Agent PlanningWarehouse Automation
AskPDF
Jul 10, 2026

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

Multi-robot path planning in human-shared environments requires a delicate balance between robust inter-robot coordination and socially aware behavior. While diffusion models excel at generating predictable, human-like paths, existing generative planners are often restricted to paths of fixed duration and high computational latency, limiting their adaptability to varying goal distances and hindering real-time deployment. We present Multi-Robot Rolling Diffusion (MRRD), a novel framework that enables real-time, long-horizon navigation for large robot teams through dense crowds. MRRD combines a rolling-horizon scheme to accommodate the limited prediction horizon of human motion, parallelized diffusion inference for scalable generation of human-like paths, and a conflict-based-search mechanism for resolving inter-robot collisions. It further incorporates urgency-based temporal conditioning to generate paths with varying speeds and employs differentiated guidance terms to maximize both social awareness around humans and efficient coordination between robots. Experimental results in crowded environments demonstrate that MRRD successfully scales to 15 robots in real-time, significantly outperforming existing baselines in both safety and mission success rates.

Vaibhav Sanjay, Yorai Shaoul, Jiaoyang Li

Robotics Institute, Carnegie Mellon University

Multi-Robot Motion PlanningDiffusion-Based PlanningSocial Robot NavigationMulti-Agent Path Finding
AskPDF