# Hypergraph-based Multi-Robot Task and Motion Planning

arXiv: https://arxiv.org/abs/2210.04333 · HTML: https://mlsanity.com/paper/2210.04333/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 45 references that are in the map.
- First posted on arXiv 9 Oct 2022.

## Builds on (most cited first, 10 of 10)

- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Searching with Consistent Prioritization for Multi-Agent Path Finding](https://mlsanity.com/paper/1812.06356/) (2018)
- [Long-Horizon Multi-Robot Rearrangement Planning for Construction Assembly](https://mlsanity.com/paper/2106.02489/) (2021)
- [Representation-Optimal Multi-Robot Motion Planning using Conflict-Based Search](https://mlsanity.com/paper/1909.13352/) (2019)
- [dRRT*: Scalable and Informed Asymptotically-Optimal Multi-Robot Motion Planning](https://mlsanity.com/paper/1903.00994/) (2019)
- [Optimal Sequential Task Assignment and Path Finding for Multi-Agent Robotic Assembly Planning](https://mlsanity.com/paper/2006.08845/) (2020)
- [Finding a needle in an exponential haystack: Discrete RRT for exploration of implicit roadmaps in multi-robot motion planning](https://mlsanity.com/paper/1305.2889/) (2013)
- [An Optimal Algorithm to Solve the Combined Task Allocation and Path Finding Problem](https://mlsanity.com/paper/1907.10360/) (2019)
- [Synchronized Multi-Arm Rearrangement Guided by Mode Graphs with Capacity Constraints](https://mlsanity.com/paper/2005.09127/) (2020)
- [Anytime Multi-arm Task and Motion Planning for Pick-and-Place of Individual Objects via Handoffs](https://mlsanity.com/paper/1905.03179/) (2019)

## Built on by (most cited first, 3 of 3)

- [Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2401.04003/) (2024)
- [MANER: Multi-Agent Neural Rearrangement Planning of Objects in Cluttered Environments](https://mlsanity.com/paper/2306.06543/) (2023)
- [Encoding Reusable Multi-Robot Planning Strategies as Abstract Hypergraphs](https://mlsanity.com/paper/2409.10692/) (2024)

## Abstract (arXiv)

We present a multi-robot task and motion planning method that, when applied to the rearrangement of objects by manipulators, results in solution times up to three orders of magnitude faster than existing methods and successfully plans for problems with up to twenty objects, more than three times as many objects as comparable methods. We achieve this improvement by decomposing the planning space to consider manipulators alone, objects, and manipulators holding objects. We represent this decomposition with a hypergraph where vertices are decomposed elements of the planning spaces and hyperarcs are transitions between elements. Existing methods use graph-based representations where vertices are full composite spaces and edges are transitions between these. Using the hypergraph reduces the representation size of the planning space-for multi-manipulator object rearrangement, the number of hypergraph vertices scales linearly with the number of either robots or objects, while the number of hyperarcs scales quadratically with the number of robots and linearly with the number of objects. In contrast, the number of vertices and edges in graph-based representations scales exponentially in the number of robots and objects. We show that similar gains can be achieved for other multi-robot task and motion planning problems.