Automata-based Optimal Planning with Relaxed Specifications
This addresses planning challenges in robotics where rigid specifications are impractical, though it appears incremental as it builds on existing automata-based planning methods.
The paper tackles the problem of planning for robots when specifications cannot be fully satisfied by introducing an automata-based framework that allows relaxation of tasks with user preferences, achieving minimal relaxation policies computed via shortest path algorithms.
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.