Optimal Control for Simple Linear Hybrid Systems

This paper studies optimal time-bounded control in a simple subclass of linear hybrid systems, which consists of one continuous variable and global constraints. Each state has a continuous cost attached to it, which is linear in the sojourn time, while a discrete cost is attached to each transition taken. We show the corresponding decision problem to be NP-complete and develop an FPTAS for finding an approximate solution. We have implemented a small prototype to compare the performance of these approximate and precise algorithms for this problem. Our results indicate that the proposed approximation schemes scale. Furthermore, we show that the same problem with infinite time horizon is in LOGSPACE.

Authors

• Mahmoud A. A. Mousa
• Sven Schewe
• Dominik Wojtczak

Keywords

• Heating
• Schedules
• Automata
• Mathematical model
• Switches
• Approximation algorithms
• Computational modeling
• Optimal Control
• Linear System
• Hybrid System
• Simple Hybrid
• Linear Hybrid
• Simple Linear System
• Linear Hybrid Systems
• Estimation Algorithm
• Estimation Strategy
• Time Of Occurrence
• Decision Problem
• Algorithm For Problem
• Global Constraints
• Infinite Time Horizon
• Optimization Problem
• Relative Performance
• Average Cost
• Finite Time
• Optimal Decision
• Input Size
• Finite Time Horizon
• Knapsack Problem
• Optimal Schedule
• Consumption In Buildings
• Optimal Cost
• Optimal Control Problem
• Running Example
• Switching Costs
• Model Predictive Control
• Constant Approximation
• linear hybrid automata