Complete, Scalable, and Robust Prioritized Planning for Multi-Robot Ordered Storage and Retrieval at Maximum Capacity

Automated warehouses face a fundamental trade-off between maximizing storage density and achieving high retrieval throughput. While puzzle-based storage (PBS) architectures increase capacity by eliminating aisles, coordinating multiple robots in these high-density spaces is computationally challenging. This paper formalizes the challenge through a novel multi-robot problem formulation for ordered storage and retrieval: We consider rectangular 2D grids, where uniform-sized loads are first stored, up to full capacity, and subsequently retrieved according to prescribed arrival and departure sequences. The main contribution of this work is an online prioritized multi-agent path planning algorithm for this problem. The algorithm builds on prior work that constructs arrangements supporting sequential storage and retrieval, i.e., of one load at a time, without relocating loads. By exploiting the structural invariants of such arrangements, we achieve the scalability of decoupled planning while guaranteeing complete, deadlock-free parallel execution even at full storage density. Experiments demonstrate that the algorithm achieves near-linear improvement in makespan with respect to the number of robots, up to $C$ robots, where $C$ is the width of the grid's open side. Furthermore, the algorithm supports robust storage arrangements that accommodate bounded uncertainty in the departure sequence, with negligible impact on execution makespan.

Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments

Autonomous robot teams navigating partially known environments face costly backtracking when ground robots encounter blocked roads that are only revealed upon physical traversal. We address this with Scout-Assisted Planning, a heterogeneous planning framework in which scouting Unmanned Aerial Vehicles proactively gather environmental information to improve Unmanned Ground Vehicle navigation. To focus scouting on the most consequential edges, we propose Information Gain-based Action Pruning, which scores candidate scouting actions by their expected impact on ground robot behavior. Since exact Information Gain-based Action Pruning computation is prohibitively expensive, we develop a Graph Neural Network based model that predicts information gain values directly from graph structure and belief state, reducing planning time to real-time levels without sacrificing solution quality. Experiments across three environment types show that SAP with Information Gain Action Pruning reduces ground robot travel cost by 31.9--37.7% over the Canadian Traveler Problem baseline, and outperforms proximity-based scouting guidance by an additional 8--14%, confirming that principled information-gain-guided scouting is both more effective and computationally feasible for real-world deployment