Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Movable Obstacles
This addresses warehouse logistics efficiency, though it appears incremental as it builds on existing techniques like sliding puzzles and multi-agent pathfinding.
The paper tackles the Block Rearrangement Problem (BRaP) for warehouse management by developing five search-based algorithms to rearrange storage blocks in dense grids up to 80x80, achieving efficient plans for deeply buried blocks despite exponential search space growth.
We introduce the Block Rearrangement Problem (BRaP), a challenging component of large warehouse management which involves rearranging storage blocks within dense grids to achieve a target state. We formally define the BRaP as a graph search problem. Building on intuitions from sliding puzzle problems, we propose five search-based solution algorithms, leveraging joint configuration space search, classical planning, multi-agent pathfinding, and expert heuristics. We evaluate the five approaches empirically for plan quality and scalability. Despite the exponential relation between search space size and block number, our methods demonstrate efficiency in creating rearrangement plans for deeply buried blocks in up to 80x80 grids.