## 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 (LDL_{f}) 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.

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

*Last updated 2020-09-23.*