Optimal temporal logic planning with cascading soft constraints

Hazhar Rahmani, Jason M. O'Kane
In Proc. IEEE/RSJ International Conference on Intelligent Robots and Systems

Abstract In this paper, we address the problem of temporal logic planning given both hard specifications of the robot's 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 robot's mission, and an ordered sequence of formulas expressed in linear dynamic logic over finite traces (LDLf) specifying the user's preferences for how the mission should be completed. The planner's objective is to synthesize, on this transition system, an infinite trajectory that best fits the user's 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 –-which is, in fact, a special kind of state-weighted B{\"u}chi automaton–- 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 all-pairs bottleneck paths problem on vertex-weighted graphs. We show the applicability of the approach via some case studies, for which we present results computed by an implementation.

  author = {Hazhar Rahmani and Jason M. O'Kane},
  booktitle = {Proc. IEEE/RSJ International Conference on Intelligent Robots and
  title = {Optimal temporal logic planning with cascading soft constraints},
  year = {2019}

O'Kane's home page
O'Kane's publication list

Last updated 2020-09-23.