# Simultaneous Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 97 references that are in the map.
- First posted on arXiv 8 Jan 2024.

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

- [AI2-THOR: An Interactive 3D Environment for Visual AI](https://mlsanity.com/paper/1712.05474/) (2017)
- [ALFRED: A Benchmark for Interpreting Grounded Instructions for Everyday Tasks](https://mlsanity.com/paper/1912.01734/) (2019)
- [Integrated Task and Motion Planning](https://mlsanity.com/paper/2010.01083/) (2020)
- [Integrated Task Assignment and Path Planning for Capacitated Multi-Agent Pickup and Delivery](https://mlsanity.com/paper/2110.14891/) (2021)
- [Optimal Target Assignment and Path Finding for Teams of Agents](https://mlsanity.com/paper/1612.05693/) (2016)
- [STyLuS*: A Temporal Logic Optimal Control Synthesis Algorithm for Large-Scale Multi-Robot Systems](https://mlsanity.com/paper/1809.08345/) (2018)
- [Optimal Multi-Robot Path Planning on Graphs: Complete Algorithms and Effective Heuristics](https://mlsanity.com/paper/1507.03290/) (2015)
- [Perception-Based Temporal Logic Planning in Uncertain Semantic Maps](https://mlsanity.com/paper/2012.10490/) (2020)
- [An Abstraction-Free Method for Multi-Robot Temporal Logic Optimal Control Synthesis](https://mlsanity.com/paper/1909.00526/) (2019)
- [Solving Simultaneous Target Assignment and Path Planning Efficiently with Time-Independent Execution](https://mlsanity.com/paper/2109.04264/) (2021)
- [Temporal Logic Motion Planning with Convex Optimization via Graphs of Convex Sets](https://mlsanity.com/paper/2301.07773/) (2023)
- [Multirobot Coordination with Counting Temporal Logics](https://mlsanity.com/paper/1810.13087/) (2018)
- [Multi-Agent Planning under Local LTL Specifications and Event-Based Synchronization](https://mlsanity.com/paper/1610.08380/) (2016)
- [Simultaneous Task Allocation and Planning Under Uncertainty](https://mlsanity.com/paper/1803.02906/) (2018)
- [Fast Decomposition of Temporal Logic Specifications for Heterogeneous Teams](https://mlsanity.com/paper/2010.00030/) (2020)
- [Time Minimization and Online Synchronization for Multi-agent Systems under Collaborative Temporal Tasks](https://mlsanity.com/paper/2208.07756/) (2022)
- [Sampling-Based Optimal Control Synthesis for Multi-Robot Systems under Global Temporal Tasks](https://mlsanity.com/paper/1706.04216/) (2017)
- [Hypergraph-based Multi-Robot Task and Motion Planning](https://mlsanity.com/paper/2210.04333/) (2022)
- [Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications](https://mlsanity.com/paper/2308.10393/) (2023)
- [Distributed motion coordination for multi-robot systems under LTL specifications](https://mlsanity.com/paper/2103.09111/) (2021)
- [A MIP-Based Approach for Multi-Robot Geometric Task-and-Motion Planning](https://mlsanity.com/paper/2210.08005/) (2022)
- [Interval vs. Point Temporal Logic Model Checking: an Expressiveness Comparison](https://mlsanity.com/paper/1711.08191/) (2017)

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

- [Nl2Hltl2Plan: Scaling Up Natural Language Understanding for Multi-Robots Through Hierarchical Temporal Logic Task Representation](https://mlsanity.com/paper/2408.08188/) (2024)
- [LLM-Grounded Dynamic Task Planning with Hierarchical Temporal Logic for Human-Aware Multi-Robot Handover](https://mlsanity.com/paper/2602.09472/) (2026)

## Abstract (arXiv)

Research in robotic planning with temporal logic specifications, such as Linear Temporal Logic (LTL), has relied on single formulas. However, as task complexity increases, LTL formulas become lengthy, making them difficult to interpret and generate, and straining the computational capacities of planners. To address this, we introduce a hierarchical structure for a widely used specification type -- LTL on finite traces (LTLf). The resulting language, termed H-LTLf, is defined with both its syntax and semantics. We further prove that H-LTLf is more expressive than its standard "flat" counterparts. Moreover, we conducted a user study that compared the standard LTLf with our hierarchical version and found that users could more easily comprehend complex tasks using the hierarchical structure. We develop a search-based approach to synthesize plans for multi-robot systems, achieving simultaneous task allocation and planning. This method approximates the search space by loosely interconnected sub-spaces, each corresponding to an LTLf specification. The search primarily focuses on a single sub-space, transitioning to another under conditions determined by the decomposition of automata. We develop multiple heuristics to significantly expedite the search. Our theoretical analysis, conducted under mild assumptions, addresses completeness and optimality. Compared to existing methods used in various simulators for service tasks, our approach improves planning times while maintaining comparable solution quality.