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 2019.

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ü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.

Download

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

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

Wed Mar 4 12:52:19 EST 2020