Controller synthesis with budget constraints Conference Paper


Author(s): Chatterjee, Krishnendu; Majumdar, Ritankar S; Henzinger, Thomas A
Title: Controller synthesis with budget constraints
Title Series: LNCS
Affiliation
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 W-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.
Conference Title: HSCC: Hybrid Systems - Computation and Control
Volume: 4981
Conference Dates: April 22-24, 2008
Conference Location: St. Louis, MO, USA
Publisher: Springer  
Location: Berlin, Heidelberg
Date Published: 2008-04-03
Start Page: 72
End Page: 86
DOI: 10.1007/978-3-540-78929-1_6
Open access: no
IST Austria Authors
  1. Thomas A. Henzinger
    415 Henzinger
Related IST Austria Work