Optimal temporal logic planning with cascading soft constraints In this paper, we address the problem of temporal logic planning given both hard specifications of the robotxe2x80x99s mission and soft preferences on the plans that achieve the mission. In particular, we consider a problem whose inputs are a transition system, a linear temporal logic (LTL) formula specifying the robotxe2x80x99s mission, and an ordered sequence of formulas expressed in linear dynamic logic over finite traces (LDL f ) specifying the userxe2x80x99s preferences for how the mission should be completed. The plannerxe2x80x99s objective is to synthesize, on this transition system, an infinite trajectory that best fits the userxe2x80x99s preferences over finite prefixes of that trajectory while nonetheless satisfying the overall objective. We describe an algorithm for this problem that constructs, from the inputs, a product automaton xe2x80x94which is, in fact, a special kind of stateweighted Buchi automatonxe2x80x94 over which an optimal trajectory is synthesized. This synthesis problem is solved via reduction to the minimax path problem in vertex weighted graphs, which can be solved by variants of the standard algorithms for computing shortest paths in a graph or by algorithms for the allpairs bottleneck paths problem on vertexweighted graphs. We show the applicability of the approach via some case studies, for which we present results computed by an implementation.

Optimal Temporal Logic Planning for MultiRobot Systems in Uncertain Semantic Maps This paper addresses a multirobot 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 informationbased predicates allowing us to incorporate uncertainty and probabilistic satisfaction requirements directly into the task specification. We propose a new highly scalable samplingbased approach that synthesizes paths that satisfy the assigned task specification while minimizing a userspecified 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 largescale planning tasks.