Optimal Temporal Logic Planning for Multi-Robot Systems in Uncertain Semantic Maps

This paper addresses a multi-robot motion planning problem in probabilistic maps obtained by semantic simultaneous localization and mapping (SLAM). The goal of the robots is to accomplish complex collaborative high level tasks captured by global temporal logic specifications in the presence of uncertainty in the workspace. Specifically, the robots operate in an unknown environment modeled as a semantic map determined by Gaussian distributions over landmark positions and arbitrary discrete distributions over landmark classes. We extend Linear Temporal Logic by including information-based predicates allowing us to incorporate uncertainty and probabilistic satisfaction requirements directly into the task specification. We propose a new highly scalable sampling-based approach that synthesizes paths that satisfy the assigned task specification while minimizing a user-specified motion cost function. Finally, we show that the proposed algorithm is probabilistically complete, asymptotically optimal and supported by convergence rate bounds. We provide extensive simulation results that corroborate the theoretical analysis and show that the proposed algorithm can address large-scale planning tasks.