Lazy-DaSH

In this article, we introduce lazy-decomposable state-space hypergraph (Lazy-DaSH), an improvement over the recent state-of-the-art multirobot task and motion planning method decomposable state-space hypergraph (DaSH), which scales to more than twice as many robots and objects while achieving more than an order of magnitude faster planning when applied to a multimanipulator object rearrangement problem. We achieve this improvement through a hierarchical approach, where a high-level task planning layer identifies planning spaces required for task completion, and motion feasibility is validated lazily only within these spaces. In contrast, DaSH precomputes the motion feasibility of all possible actions, resulting in higher costs for constructing state-space representations. Lazy-DaSH ensures efficient query performance by utilizing a hierarchical constraint feedback mechanism, effectively conveying motion feasibility to the query process while incrementally expanding the task and motion space representations when failures are detected, so the search space grows only as needed. By maintaining smaller state-space representations, our method significantly reduces both representation construction time and query time. We evaluate Lazy-DaSH in five scenarios, demonstrating its scalability with increasing numbers of robots and objects, as well as its adaptability in resolving conflicts through the constraint feedback mechanism.