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

• 016_hscc2008.ps · application/postscript · 394 kbytes
• 016_hscc2008.pdf · application/pdf · 169 kbytes

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