## Controller Synthesis with Budget Constraints

*Krishnendu Chatterjee, Rupak Majumdar, and
Thomas A. Henzinger*

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

*Proceedings of the
11th International Workshop on Hybrid Systems: Computation and Control*
(HSCC),
Lecture Notes in Computer Science 4981,
Springer,
2008,
pp. 72-86.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 2008 Springer.