Decomposition-based Hierarchical Task Allocation and Planning for Multi-Robots under Hierarchical Temporal Logic Specifications

Past research into robotic planning with temporal logic specifications,notably Linear Temporal Logic (LTL), was largely based on singular formulas forindividual or groups of robots. But with increasing task complexity, LTLformulas unavoidably grow lengthy, complicating interpretation andspecification generation, and straining the computational capacities of theplanners. A recent development has been the hierarchical representation of LTL[1] that contains multiple temporal logic specifications, providing a moreinterpretable framework. However, the proposed planning algorithm assumes theindependence of robots within each specification, limiting their application tomulti-robot coordination with complex temporal constraints. In this work, weformulated a decomposition-based hierarchical framework. At the high level,each specification is first decomposed into a set of atomic sub-tasks. Wefurther infer the temporal relations among the sub-tasks of differentspecifications to construct a task network. Subsequently, a Mixed IntegerLinear Program is utilized to assign sub-tasks to various robots. At the lowerlevel, domain-specific controllers are employed to execute sub-tasks. Ourapproach was experimentally applied to domains of robotic navigation andmanipulation. The outcomes of thorough simulations, which included comparativeanalyses, demonstrated the effectiveness of the proposed approach.