Organizations: 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-robot systems in automated warehouses must efficiently attend to a constant stream of pickup-and-delivery tasks while avoiding collisions. Existing Multi-Agent Pickup-and-Delivery (MAPD) solutions generate plans that are globally feasible but often locally inefficient. In large-scale, long-horizon deployments, these inefficiencies, such as robots backtracking from target goal locations and idling in congested areas, accumulate over time and degrade performance. This paper contributes Local Solution Repair (LSR), a goal replanning approach that detects suboptimal behaviors at run-time and locally improves plans to reduce conflict between agents. We demonstrate the utility of our approach by repairing solutions generated by state-of-the-art MAPD baselines, M2M and LNS-PBS. Our results in long-horizon warehouse simulations over three environments show upwards of 5.9% improvement in task throughput over current state-of-the-art methods by reducing the number of suboptimal instances by ~36k or by 14.6% with minor additional computation time.
Figures & tables
Fig. 1 : Examples of initial MAPD solutions in which robots pick up objects □ and deliver them to destinations △ within a warehouse scenario. The three initial MAPD solutions show examples of suboptimal actions (e.g., idling and backtracking) due to suboptimal and/or collision-unaware task allocations. For each of these scenarios, LSR detects the agents executing suboptimal actions, groups other agents contributing to these behaviors, then reassigns goals locations for the subset of agents. The final MAPD solutions show that LSR improves the overall solutions by: (1) rearranging goal order within aisles, (2) moving goal(s) to neighboring aisles, (3) moving goal(s) closer to an agent’s current location, or (4) a combination of the previous ways.
Fig. 2 : Overview of our Local Solution Repair (LSR) method.
Fig. 3 : Partial view of our three simulated warehouse layouts. All non-obstacle regions are traversable by agents, subject to collision constraints. Each map is 27 × 50.
Fig. 4 : Comparison of the rolling mean (line) and std-dev (shaded region) of η ( ↑ is better ) reported across Restricted (a), Open-Top (b), and Open (c) maps. Our repair methods LSRECR (orange) and LSRMCR (purple) consistently outperform the baselines (green), LNS-PBS (top row) and M2M (bottom row) across all map types.
Method
Restricted
Open-Top
Open
Metrics
η (tasks/min.)
Δη%
Rsubopt%
η (tasks/min.)
Δη%
Rsubopt%
η (tasks/min.)
Δη%
Rsubopt%
LNS-PBS + LSRMCR
128.8±0.6
+5.9%
+14.4%
130.1±0.7
+5.9%
+14.6%
136.1±0.7
+3.2%
+12.1%
LNS-PBS + LSRECR
125.8±0.6
+3.7%
+4.1%
127.6±0.4
+4.1%
+4.2%
134.5±0.8
+2.0%
+4.0%
LNS-PBS
121.2±0.4
122.4±0.4
131.8±0.6
M2M + LSRMCR
131.8±0.4
+3.2%
+12.7%
134.9±0.3
+3.7%
+13.8%
135.1±0.6
+2.6%
+10.3%
M2M + LSRECR
130.8±0.2
+2.4%
+4.4%
133.2±0.3
+2.5%
+4.2%
133.8±0.2
+1.6%
+4.2%
TABLE I : Throughput ( η ), percent change in throughput ( Δη% ), and percent change in suboptimal actions ( Rsubopt% ) across baseline methods, map types, and repair methods, averaged over 10 simulations each. LSRMCR performs best, reducing suboptimal actions by 14.6% , increasing throughput by 5.9% .
Fig. 5 : Breakdown of better (accepted), same (rejected), and worse (rejected) per combination of baseline method and repair method averaged across map types and seeds. LSRMCR proposes ≈3× more goal reassignments that are accepted than LSRECR . Across baseline methods, LNS-PBS has ≈2% more accepted goal reassignments than M2M.
Fig. 6 : Distribution of repair mechanisms for LSRECR and LSRMCR ( n=300 each) pooled across baselines and map types. LSRMCR ’s conflict-aware costs let it reason about goal order within aisle and goals between aisles, whereas LSRECR relies on inter-aisle and closer goal location goal reassignments through collision-unaware shortest-path distances.
Fig. 7 : Distribution of worse (rejected) goal reassignments for LSRECR and LSRMCR ( n=150 each) pooled across baselines and map types. LSRMCR suggests worse goal reassignments due to goal changes affecting outside-group agents. LSRECR suggests worse solutions primarily due to the lack of collision-aware planning for within-aisle goal reordering, then by outside-group agents.
Fig. 8 : Repair Computation Times (seconds) for LSRECR (orange) and LSRMCR (purple) across Restricted (left), Open-Top (middle), and Open maps (right). We note LSRECR substantially reduced computation time compared to LSRMCR .
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
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
Space-efficient warehouse layouts often contain single-agent-width aisles and dead-end workstations where robots have few places to wait without blocking others. In Multi-Agent Pickup and Delivery (MAPD) on such constrained layouts, robots must accept online pickup-delivery tasks while preserving protected waiting locations called Havens. The Safe HAven Retreat Planner (SHARP) introduced a mechanism that extends each committed task path with a validated retreat to the agent's dedicated initial Haven, but fixed-Haven commitments can send agents toward distant Havens after deliveries. We present A-sharp (Adaptive SHARP), which changes an agent's retreat target at task assignment time. A naive switch can cause two agents to rely on the same waiting location or let another committed path pass through a location that is still occupied or reserved. A-sharp prevents these failures with an availability test for candidate Havens and a pending-release rule that keeps the previous Haven protected until the agent departs. Under explicit Haven-structure and Safe Interval Path Planning (SIPP) assumptions, we prove invariant preservation and finite-release completeness: every task in any finite release sequence is delivered in finite time. Across 72,000 runs on 14,400 paired map-agent-count-rate-seed cases over four maps, both SHARP and A-sharp complete their respective 14,400 runs. For makespan (final delivery time), a prespecified paired comparison with Holm correction over all 138 configurations with more Havens than agents finds A-sharp significantly better in 107 configurations and never significantly worse than SHARP; on the tested tree map, the median reduction is 16.7%.
Taisei Hirayama, Kohei Yoshida, Hiroki Sakaji +1
Hokkaido University, Sapporo 060-0808, Japan · Toyota Industries Corporation, Aichi 474-8601, Japan