IEEE Robotics and Automation Letters · 2023 · 29 citations · 25 references
EngineeringComputer ScienceRobotics EngineeringIndustrial RoboticsPath PlanningRoboticsMappingRobot Motion PlanningWarehouse LayoutWarehouse LocationWarehouse OperationsMulti-agent OptimizationMulti-agent Path PlanningMulti-robot PlanningProblem Statement FormulationTask DependenciesWarehouse Aisle LayoutWarehouse Layout PlanningWarehouse Robotics
We introduce a new problem formulation, Double-Deck Multi-Agent Pickup and Delivery (DD-MAPD), which models the multi-robot shelf rearrangement problem in automated warehouses. DD-MAPD extends both Multi-Agent Pickup and Delivery (MAPD) and Multi-Agent Path Finding (MAPF) by allowing agents to move beneath shelves or lift and deliver a shelf to an arbitrary location, thereby changing the warehouse layout. We show that solving DD-MAPD is NP-hard. To tackle DD-MAPD, we propose MAPF-DECOMP, an algorithmic framework that decomposes a DD-MAPD instance into a MAPF instance for coordinating shelf trajectories and a subsequent MAPD instance with task dependencies for computing paths for agents. We also present an optimization technique to improve the performance of MAPF-DECOMP and demonstrate how to make MAPF-DECOMP complete for well-formed DD-MAPD instances, a realistic subclass of DD-MAPD instances. Our experimental results demonstrate the efficiency and effectiveness of MAPF-DECOMP, with the ability to compute high-quality solutions for large-scale instances with over one thousand shelves and hundreds of agents in just minutes of runtime.
25
The Hungarian method for the assignment problem
Harold W. Kuhn · Naval Research Logistics Quarterly · 1955 · 12.6K citations
Conflict-based search for optimal multi-agent pathfinding
Guni Sharon, Roni Stern, Ariel Felner et al. · Artificial Intelligence · 2014 · 1.2K citations
A simplified NP-complete satisfiability problem
Craig A. Tovey · Discrete Applied Mathematics · 1984 · 382 citations