# Automata-based Optimal Planning with Relaxed Specifications

arXiv: https://arxiv.org/abs/2107.13650 · HTML: https://mlsanity.com/paper/2107.13650/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 Jul 2021.

## Built on by (most cited first, 2 of 2)

- [Learning Minimally-Violating Continuous Control for Infeasible Linear Temporal Logic Specifications](https://mlsanity.com/paper/2210.01162/) (2022)
- [Optimal Cost-Preference Trade-off Planning with Multiple Temporal Tasks](https://mlsanity.com/paper/2306.13222/) (2023)

## Abstract (arXiv)

In this paper, we introduce an automata-based framework for planning with relaxed specifications. User relaxation preferences are represented as weighted finite state edit systems that capture permissible operations on the specification, substitution and deletion of tasks, with complex constraints on ordering and grouping. We propose a three-way product automaton construction method that allows us to compute minimal relaxation policies for the robots using standard shortest path algorithms. The three-way automaton captures the robot's motion, specification satisfaction, and available relaxations at the same time. Additionally, we consider a bi-objective problem that balances temporal relaxation of deadlines within specifications with changing and deleting tasks. Finally, we present the runtime performance and a case study that highlights different modalities of our framework.