Other formats:
BibTeX
LaTeX
RIS
@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/9783319088679_30}, editor = {Armin Biere, Roderick Bloem}, keywords = {controller synthesis; consumption systems; mean payoff}, howpublished = {tištěná verze "print"}, language = {eng}, location = {Neuveden}, isbn = {9783319088662}, pages = {457472}, 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 longrun running costs of discrete systems is based on minimizing the meanpayoff, i.e., the longrun 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 meanpayoff 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 meanpayoff while preserving the functionality of the system encoded by a given lineartime 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 longrun 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.~457472. ISBN~9783319088662. doi:10.1007/9783319088679\_{}30.
