  Past research into robotic planning with temporal logic specifications,
notably Linear Temporal Logic (LTL), was largely based on singular formulas for
individual or groups of robots. But with increasing task complexity, LTL
formulas unavoidably grow lengthy, complicating interpretation and
specification generation, and straining the computational capacities of the
planners. By leveraging the intrinsic structure of tasks, we introduced a
hierarchical structure to LTL specifications with requirements on syntax and
semantics, and proved that they are more expressive than their flat
counterparts. Second, we employ a search-based approach to synthesize plans for
a multi-robot system, accomplishing simultaneous task allocation and planning.
The search space is approximated by loosely interconnected sub-spaces, with
each sub-space corresponding to one LTL specification. The search is
predominantly confined to a single sub-space, transitioning to another
sub-space under certain conditions, determined by the decomposition of
automatons. Moreover, multiple heuristics are formulated to expedite the search
significantly. A theoretical analysis concerning completeness and optimality is
conducted under mild assumptions. When compared with existing methods on
service tasks, our method outperforms in terms of execution times with
comparable solution quality. Finally, scalability is evaluated by testing a
group of 30 robots and achieving reasonable runtimes.
