NBA-guided heuristic sampling algorithm for multi-robot task planning under temporal logic

Aiming at the task planning problem of multi-robot under linear temporal logic (LTL), this paper proposes an improved sampling planning algorithm based on Nondeterministic Büchi automaton (NBA) guidance. Firstly, this paper defines a kind of LTL task planning problem, which mainly focuses on the meaningful key nodes in the task execution of each robot, and there are many sequential dependencies of task constraints. Then, an improved sampling algorithm framework is proposed, which uses a more efficient way to build a search tree and reduces the number of nodes in the tree. Furthermore, the sampling points are guided by NBA to ensure that sampling is conducive to the advancement of time-series tasks. And considering the task feasible region of each robot, the auction algorithm is introduced to optimize the local matching relationship, which greatly improves the quality of sampling points. Finally, numerical simulation is carried out to solve the LTL task planning problem. The optimality and stability of the algorithm are obviously improved, and the time consumption of this algorithm is obviously better than that of the existing advanced algorithms.