Abstraction-Refinement Based Optimal Control with Regular Objectives
Preprint
Abstract
This paper presents an abstraction-refinement method to synthesize control inputs for a discrete-time piecewise linear system. The controlled system behavior satisfies a finite-word linear-time temporal objective while incurring minimal cost. An abstract finite state weighted transition system is constructed from finite partitions of the state and input spaces by solving optimization problems. A sequence of suboptimal controllers is obtained by considering a sequence of uniformly refined partitions. The abstract system satisfies the condition that the cost of the optimal control on the abstract system provides an upper bound on the cost of the optimal control for the original system. Furthermore, each suboptimal controller gives trajectories that have the cost upper bounded by the cost of the optimal control on the corresponding abstract system. In fact, the costs achieved by the sequence of suboptimal controllers converge to the optimal cost for the piecewise linear system. The tool OPTCAR implements the abstraction-refinement algorithm. Examples illustrate the feasibility of this approach to synthesize automatically suboptimal controllers with improving optimal costs.Keywords
All Related Versions
This publication has 14 references indexed in Scilit:
- Temporal logic model predictive controlAutomatica, 2015
- Controller synthesis for safety and reachability via approximate bisimulationAutomatica, 2012
- Receding Horizon Temporal Logic PlanningIEEE Transactions on Automatic Control, 2012
- Specifications for decidable hybrid gamesTheoretical Computer Science, 2011
- Discrete Abstractions of Nonlinear Systems Based on Error Propagation AnalysisIEEE Transactions on Automatic Control, 2011
- Symbolic approximate time-optimal controlSystems & Control Letters, 2011
- The Parma Polyhedra Library: Toward a complete set of numerical abstractions for the analysis and verification of hardware and software systemsScience of Computer Programming, 2008
- Optimal control of discrete-time hybrid automata under safety and liveness constraintsNonlinear Analysis, 2006
- LQR optimization of linear system switchingIEEE Transactions on Automatic Control, 2002
- Discrete approximation and supervisory control of continuous systemsIEEE Transactions on Automatic Control, 1998