Mousa, Mahmoud AA, Schewe, Sven and Wojtczak, Dominik
(2016)
Optimal Control for Simple Linear Hybrid Systems.
In: 2016 23rd International Symposium on Temporal Representation and Reasoning (TIME), 2016-10-17 - 2016-10-19.
Text
main.pdf - Author Accepted Manuscript Download (297kB) |
Abstract
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.
Item Type: | Conference or Workshop Item (Unspecified) |
---|---|
Additional Information: | keywords: approximation theory;computational complexity;continuous systems;discrete systems;optimal control;LOGSPACE;NP-complete;approximation schemes scale;continuous variable constraints;decision problem;discrete cost;global constraints;infinite time horizon;optimal time-bounded control;simple linear hybrid systems;sojourn time;Approximation algorithms;Automata;Computational modeling;Heating;Mathematical model;Schedules;Switches;approximation algorithms;linear hybrid automata;optimal control |
Uncontrolled Keywords: | 4901 Applied Mathematics, 40 Engineering, 4007 Control Engineering, Mechatronics and Robotics, 49 Mathematical Sciences |
Depositing User: | Symplectic Admin |
Date Deposited: | 31 Jan 2017 13:59 |
Last Modified: | 09 Sep 2024 06:28 |
DOI: | 10.1109/TIME.2016.9 |
Related URLs: | |
URI: | https://livrepository.liverpool.ac.uk/id/eprint/3005459 |