*banner
 

Controller Synthesis with Budget Constraints
Krishnendu Chatterjee, Tom Henzinger, Rupak Majumdar

Citation
Krishnendu Chatterjee, Tom Henzinger, Rupak Majumdar. "Controller Synthesis with Budget Constraints". Hybrid Systems: Computation and Control, 11th International Workshop, HSCC 2008, St. Louis, MO, USA, April 22-24, 2008. Proceedings, Magnus Egerstedt and Bud Mishra (eds.), HSCC, 72-86, April, 2008.

Abstract
We study the controller synthesis problem under budget constraints. In this problem, there is a cost associated with making an observation, and a controller can make only a limited number of observations in each round so that the total cost of the observations does not exceed a given fixed budget. The controller must ensure some omega-regular requirement subject to the budget constraint. Budget constraints arise in designing and implementing controllers for resource-constrained embedded systems, where a controller may not have enough power, time, or bandwidth to obtain data from all sensors in each round. They lead to games of imperfect information, where the unknown information is not fixed a priori, but can vary from round to round, based on the choices made by the controller how to allocate its budget. We show that the budget-constrained synthesis problem for omega-regular objectives is complete for exponential time. In addition to studying synthesis under a fixed budget constraint, we study the budget optimization problem, where given a plant, an objective, and observation costs, we have to find a controller that achieves the objective with minimal average accumulated cost (or minimal peak cost). We show that this problem is reducible to a game of imperfect information where the winning objective is a conjunction of an omega-regular condition and a long-run average condition (or a least max-cost condition), and this again leads to an exponential-time algorithm. Finally, we extend our results to games over infinite state spaces, and show that the budget-constrained synthesis problem is decidable for infinite state games with stable quotients of finite index. Consequently, the discrete time budget-constrained synthesis problem is decidable for rectangular hybrid automata.

Electronic downloads

Citation formats  
  • HTML
    Krishnendu Chatterjee, Tom Henzinger, Rupak Majumdar. <a
    href="http://chess.eecs.berkeley.edu/pubs/468.html"
    >Controller Synthesis with Budget Constraints</a>,
    Hybrid Systems: Computation and Control, 11th International 
                  Workshop, HSCC 2008, St. Louis, MO, USA, April
    22-24, 2008. Proceedings, Magnus Egerstedt and Bud Mishra
    (eds.), HSCC, 72-86, April, 2008.
  • Plain text
    Krishnendu Chatterjee, Tom Henzinger, Rupak Majumdar.
    "Controller Synthesis with Budget Constraints".
    Hybrid Systems: Computation and Control, 11th International 
                  Workshop, HSCC 2008, St. Louis, MO, USA, April
    22-24, 2008. Proceedings, Magnus Egerstedt and Bud Mishra
    (eds.), HSCC, 72-86, April, 2008.
  • BibTeX
    @inproceedings{ChatterjeeHenzingerMajumdar08_ControllerSynthesisWithBudgetConstraints,
        author = {Krishnendu Chatterjee and Tom Henzinger and Rupak
                  Majumdar},
        title = {Controller Synthesis with Budget Constraints},
        booktitle = {Hybrid Systems: Computation and Control, 11th
                  International                Workshop, HSCC 2008,
                  St. Louis, MO, USA, April 22-24, 2008. Proceedings},
        editor = {Magnus Egerstedt and Bud Mishra},
        organization = {HSCC},
        pages = {72-86},
        month = {April},
        year = {2008},
        abstract = {We study the controller synthesis problem under
                  budget constraints. In this problem, there is a
                  cost associated with making an observation, and a
                  controller can make only a limited number of
                  observations in each round so that the total cost
                  of the observations does not exceed a given fixed
                  budget. The controller must ensure some
                  omega-regular requirement subject to the budget
                  constraint. Budget constraints arise in designing
                  and implementing controllers for
                  resource-constrained embedded systems, where a
                  controller may not have enough power, time, or
                  bandwidth to obtain data from all sensors in each
                  round. They lead to games of imperfect
                  information, where the unknown information is not
                  fixed a priori, but can vary from round to round,
                  based on the choices made by the controller how to
                  allocate its budget. We show that the
                  budget-constrained synthesis problem for
                  omega-regular objectives is complete for
                  exponential time. In addition to studying
                  synthesis under a fixed budget constraint, we
                  study the budget optimization problem, where given
                  a plant, an objective, and observation costs, we
                  have to find a controller that achieves the
                  objective with minimal average accumulated cost
                  (or minimal peak cost). We show that this problem
                  is reducible to a game of imperfect information
                  where the winning objective is a conjunction of an
                  omega-regular condition and a long-run average
                  condition (or a least max-cost condition), and
                  this again leads to an exponential-time algorithm.
                  Finally, we extend our results to games over
                  infinite state spaces, and show that the
                  budget-constrained synthesis problem is decidable
                  for infinite state games with stable quotients of
                  finite index. Consequently, the discrete time
                  budget-constrained synthesis problem is decidable
                  for rectangular hybrid automata.},
        URL = {http://chess.eecs.berkeley.edu/pubs/468.html}
    }
    

Posted by Krishnendu Chatterjee, PhD on 24 Jun 2008.
Groups: chess
For additional information, see the Publications FAQ or contact webmaster at chess eecs berkeley edu.

Notice: This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright.

©2002-2018 Chess