Optimal Control for Simple Linear Hybrid Systems

Mousa, Mahmoud AA, Schewe, Sven ORCID: 0000-0002-9093-9518 and Wojtczak, Dominik ORCID: 0000-0001-5560-0546 (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
Depositing User:	Symplectic Admin
Date Deposited:	31 Jan 2017 13:59
Last Modified:	19 Jan 2023 07:19
DOI:	10.1109/TIME.2016.9
Related URLs:	Author Publisher
URI:	https://livrepository.liverpool.ac.uk/id/eprint/3005459