Optimal Control for Simple Linear Hybrid Systems

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

doi:10.1109/TIME.2016.9

Optimal Control for Simple Linear Hybrid Systems

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

School of Mathematical & Computer Sciences

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

2 Citations (Scopus)

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.

Original language	English
Title of host publication	23rd International Symposium on Temporal Representation and Reasoning 2016
Editors	Curtis Dyreson, Michael R. Hansen, Luke Hunsberger
Publisher	IEEE
Pages	12-20
Number of pages	9
ISBN (Electronic)	9781509038251
DOIs	https://doi.org/10.1109/TIME.2016.9
Publication status	Published - 8 Dec 2016
Event	23rd International Symposium on Temporal Representation and Reasoning, TIME 2016 - Kongens Lyngby, Denmark Duration: 17 Oct 2016 → 19 Oct 2016

Conference

Conference	23rd International Symposium on Temporal Representation and Reasoning, TIME 2016
Country/Territory	Denmark
City	Kongens Lyngby
Period	17/10/16 → 19/10/16

Keywords

approximation algorithms
linear hybrid automata
optimal control

ASJC Scopus subject areas

General Mathematics

Access to Document

10.1109/TIME.2016.9

Cite this

@inproceedings{b559384f09924119a8964ec89700790c,

title = "Optimal Control for Simple Linear Hybrid Systems",

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.",

keywords = "approximation algorithms, linear hybrid automata, optimal control",

author = "Mousa, {Mahmoud A. A.} and Sven Schewe and Dominik Wojtczak",

note = "Publisher Copyright: {\textcopyright} 2016 IEEE.; 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016 ; Conference date: 17-10-2016 Through 19-10-2016",

year = "2016",

month = dec,

day = "8",

doi = "10.1109/TIME.2016.9",

language = "English",

pages = "12--20",

editor = "Curtis Dyreson and Hansen, {Michael R.} and Luke Hunsberger",

booktitle = "23rd International Symposium on Temporal Representation and Reasoning 2016",

publisher = "IEEE",

address = "United States",

}

Mousa, MAA, Schewe, S & Wojtczak, D 2016, Optimal Control for Simple Linear Hybrid Systems. in C Dyreson, MR Hansen & L Hunsberger (eds), 23rd International Symposium on Temporal Representation and Reasoning 2016. IEEE, pp. 12-20, 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016, Kongens Lyngby, Denmark, 17/10/16. https://doi.org/10.1109/TIME.2016.9

TY - GEN

T1 - Optimal Control for Simple Linear Hybrid Systems

AU - Mousa, Mahmoud A. A.

AU - Schewe, Sven

AU - Wojtczak, Dominik

PY - 2016/12/8

Y1 - 2016/12/8

N2 - 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.

AB - 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.

KW - approximation algorithms

KW - linear hybrid automata

KW - optimal control

UR - http://www.scopus.com/inward/record.url?scp=85009784474&partnerID=8YFLogxK

U2 - 10.1109/TIME.2016.9

DO - 10.1109/TIME.2016.9

M3 - Conference contribution

AN - SCOPUS:85009784474

SP - 12

EP - 20

BT - 23rd International Symposium on Temporal Representation and Reasoning 2016

A2 - Dyreson, Curtis

A2 - Hansen, Michael R.

A2 - Hunsberger, Luke

PB - IEEE

T2 - 23rd International Symposium on Temporal Representation and Reasoning, TIME 2016

Y2 - 17 October 2016 through 19 October 2016

ER -

Optimal Control for Simple Linear Hybrid Systems

Abstract

Conference

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this