解决密集仓库中无指定任务的储物块重排难题
Symbolic Planning and Multi-Agent Path Finding in Extremely Dense Environments with Unassigned Agents
- 将重排问题建模为图搜索，融合滑块谜题思路设计五种算法
- 在80×80网格中成功规划深埋区块的重排路径，效率优于指数增长的搜索空间
- 适合物流自动化、仓储机器人调度等场景，尤其适用于高密度环境
我们提出块重排问题（BRaP），这是大型仓库管理中的一个挑战性任务，涉及在密集网格中重新排列存储块以达成目标状态。我们将BRaP正式定义为图搜索问题。基于滑块谜题的直觉，提出五种基于搜索的求解算法，结合联合配置空间搜索、经典规划、多智能体路径规划和专家启发式。我们在计划质量与可扩展性方面对五种方法进行了实证评估。尽管搜索空间大小与块数呈指数关系，我们的方法在80×80网格中仍能高效生成深埋块的重排计划。
原文摘要 · Abstract (English)
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 goal 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。