Minimizing Running Costs in Consumption Systems

D 2014

Minimizing Running Costs in Consumption Systems

BRÁZDIL, Tomáš, David KLAŠKA, Antonín KUČERA and Petr NOVOTNÝ

Basic information

Original name

Minimizing Running Costs in Consumption Systems

Authors

BRÁZDIL, Tomáš (203 Czech Republic, belonging to the institution), David KLAŠKA (203 Czech Republic, belonging to the institution), Antonín KUČERA (203 Czech Republic, guarantor, belonging to the institution) and Petr NOVOTNÝ (203 Czech Republic, belonging to the institution)

Edition

Neuveden, Computer Aided Verification, p. 457-472, 16 pp. 2014

Publisher

Springer International Publishing

Other information

Language

English

Type of outcome

Stať ve sborníku

Field of Study

10201 Computer sciences, information science, bioinformatics

Country of publisher

United States of America

Confidentiality degree

není předmětem státního či obchodního tajemství

Publication form

printed version "print"

References:

URL

Impact factor

Impact factor: 0.402 in 2005

RIV identification code

RIV/00216224:14330/14:00074098

Organization unit

Faculty of Informatics

ISBN

978-3-319-08866-2

ISSN

DOI

http://dx.doi.org/10.1007/978-3-319-08867-9_30

Keywords in English

controller synthesis; consumption systems; mean payoff

Abstract

V originále

A standard approach to optimizing long-run running costs of discrete systems is based on minimizing the mean-payoff, i.e., the long-run average amount of resources ("energy") consumed per transition. However, this approach inherently assumes that the energy source has an unbounded capacity, which is not always realistic. For example, an autonomous robotic device has a battery of finite capacity that has to be recharged periodically, and the total amount of energy consumed between two successive charging cycles is bounded by the capacity. Hence, a controller minimizing the mean-payoff must obey this restriction. In this paper we study the controller synthesis problem for consumption systems with a finite battery capacity, where the task of the controller is to minimize the mean-payoff while preserving the functionality of the system encoded by a given linear-time property. We show that an optimal controller always exists, and it may either need only finite memory or require infinite memory (it is decidable in polynomial time which of the two cases holds). Further, we show how to compute an effective description of an optimal controller in polynomial time. Finally, we consider the limit values achievable by larger and larger battery capacity, show that these values are computable in polynomial time, and we also analyze the corresponding rate of convergence. To the best of our knowledge, these are the first results about optimizing the long-run running costs in systems with bounded energy stores.

Links

GAP202/10/1469, research and development project

Name: Formální metody pro analýzu a verifikaci komplexních systémů

Investor: Czech Science Foundation

MUNI/A/0765/2013, interní kód MU

Name: Zapojení studentů Fakulty informatiky do mezinárodní vědecké komunity (Acronym: SKOMU)

Investor: Masaryk University, Category A

MUNI/A/0855/2013, interní kód MU

Name: Rozsáhlé výpočetní systémy: modely, aplikace a verifikace III. (Acronym: FI MAV III.)

Investor: Masaryk University, Category A

Citovat

BRÁZDIL, Tomáš, David KLAŠKA, Antonín KUČERA and Petr NOVOTNÝ. Minimizing Running Costs in Consumption Systems. In Armin Biere, Roderick Bloem. Computer Aided Verification. Neuveden: Springer International Publishing, 2014, p. 457-472. ISBN 978-3-319-08866-2. Available from: https://dx.doi.org/10.1007/978-3-319-08867-9_30.

@inproceedings{1206158,
   author = {Brázdil, Tomáš and Klaška, David and Kučera, Antonín and Novotný, Petr},
   address = {Neuveden},
   booktitle = {Computer Aided Verification},
   doi = {http://dx.doi.org/10.1007/978-3-319-08867-9_30},
   editor = {Armin Biere, Roderick Bloem},
   keywords = {controller synthesis; consumption systems; mean payoff},
   howpublished = {tištěná verze "print"},
   language = {eng},
   location = {Neuveden},
   isbn = {978-3-319-08866-2},
   pages = {457-472},
   publisher = {Springer International Publishing},
   title = {Minimizing Running Costs in Consumption Systems},
   url = {http://arxiv.org/abs/1402.4995},
   year = {2014}
}

TY  - JOUR
ID  - 1206158
AU  - Brázdil, Tomáš - Klaška, David - Kučera, Antonín - Novotný, Petr
PY  - 2014
TI  - Minimizing Running Costs in Consumption Systems
PB  - Springer International Publishing
CY  - Neuveden
SN  - 9783319088662
KW  - controller synthesis
KW  - consumption systems
KW  - mean payoff
UR  - http://arxiv.org/abs/1402.4995
L2  - http://arxiv.org/abs/1402.4995
N2  - A standard approach to optimizing long-run running costs of discrete systems is based on minimizing the mean-payoff, i.e., the long-run average amount of resources ("energy") consumed per transition. However, this approach inherently assumes that the energy source has an unbounded capacity, which is not always realistic. For example, an autonomous robotic device has a battery of finite capacity that has to be recharged periodically, and the total amount of energy consumed between two successive charging cycles is bounded by the capacity. Hence, a controller minimizing the mean-payoff must obey this restriction. In this paper we study the controller synthesis problem for consumption systems with a finite battery capacity, where the task of the controller is to minimize the mean-payoff while preserving the functionality of the system encoded by a given linear-time property. We show that an optimal controller always exists, and it may either need only finite memory or require infinite memory (it is decidable in polynomial time which of the two cases holds). Further, we show how to compute an effective description of an optimal controller in polynomial time. Finally, we consider the limit values achievable by larger and larger battery capacity, show that these values are computable in polynomial time, and we also analyze the corresponding rate of convergence. To the best of our knowledge, these are the first results about optimizing the long-run running costs in systems with bounded energy stores.
ER  -

BRÁZDIL, Tomáš, David KLAŠKA, Antonín KUČERA and Petr NOVOTNÝ. Minimizing Running Costs in Consumption Systems. In Armin Biere, Roderick Bloem. \textit{Computer Aided Verification}. Neuveden: Springer International Publishing, 2014, p.~457-472. ISBN~978-3-319-08866-2. Available from: https://dx.doi.org/10.1007/978-3-319-08867-9\_{}30.

Detailed Information on Publication Record