In this work, we propose a method for multiple mobile robot motion planning that efficiently plans for robot teams up to 128 robots (an order of magnitude larger than existing state-of-the-art methods) in congested settings with narrow passages in the environment. We achieve this improvement in scalability by extending the state-of-the-art Decomposable State Space Hypergraph (DaSH) multi-robot planning framework to support mobile robot motion planning in congested environments. This is a problem that DaSH cannot be directly applied to because it lacks a highly structured, easily discretizable task space and features kinodynamic constraints. We accomplish this by exploiting knowledge about the workspace topology to limit exploration of the planning space and through modifying DaSH's conflict resolution scheme. This guidance captures when coordination between robots is necessary, allowing us to decompose the intractably large multi-robot search space while limiting risk of inter-robot conflicts by composing relevant robot groups together while planning.

翻译：本文提出一种面向多移动机器人的运动规划方法，能够在包含狭窄通道的拥挤环境中为多达128台机器人的团队高效规划路径（规模较现有先进方法提升一个数量级）。为实现可扩展性的显著提升，本研究对当前先进的Decomposable State Space Hypergraph（DaSH）多机器人规划框架进行扩展，使其支持拥挤环境下的移动机器人运动规划。该问题无法直接应用DaSH框架，因其缺乏高度结构化且易于离散化的任务空间，并涉及运动动力学约束。我们通过以下方式实现突破：利用工作空间拓扑知识限制规划空间的探索范围，并改进DaSH的冲突消解机制。这种引导机制能识别机器人间必须协调的时机，使我们在规划过程中既能将庞大难解的多机器人搜索空间进行分解，又能通过组合相关机器人组来降低机器人间冲突风险。