Rectangular hybrid games

T.A. Henzinger, B. Horowitz, R. Majumdar, in:, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1999, pp. 320–335.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
; ;
Series Title
LNCS
Abstract
In order to study control problems for hybrid systems, we generalize hybrid automata to hybrid games —say, controller vs. plant. If we specify the continuous dynamics by constant lower and upper bounds, we obtain rectangular games. We show that for rectangular games with objectives expressed in Ltl (linear temporal logic), the winning states for each player can be computed, and winning strategies can be synthesized. Our result is sharp, as already reachability is undecidable for generalizations of rectangular systems, and optimal —singly exponential in the size of the game structure and doubly exponential in the size of the Ltl objective. Our proof systematically generalizes the theory of hybrid systems from automata (single-player structures) [9] to games (multi-player structures): we show that the successively more general infinite-state classes of timed, 2D rectangular, and rectangular games induce successively weaker, but still finite, quotient structures called game bisimilarity, game similarity, and game trace equivalence. These quotients can be used, in particular, to solve the Ltl control problem.
Publishing Year
Date Published
1999-01-01
Acknowledgement
This research was supported in part by the NSF CAREER award CCR-9501708, by the NSF grant CCR-9504469, by the DARPA (NASA Ames) grant NAG2-1214, by the DARPA (Wright-Patterson AFB) grant F33615-98-C-3614, and by the ARO MURI grant DAAH-04-96-1-0341.
Volume
1664
Page
320 - 335
Conference
CONCUR: Concurrency Theory
IST-REx-ID

Cite this

Henzinger TA, Horowitz B, Majumdar R. Rectangular hybrid games. In: Vol 1664. Schloss Dagstuhl - Leibniz-Zentrum für Informatik; 1999:320-335. doi:10.1007/3-540-48320-9_23
Henzinger, T. A., Horowitz, B., & Majumdar, R. (1999). Rectangular hybrid games (Vol. 1664, pp. 320–335). Presented at the CONCUR: Concurrency Theory, Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.1007/3-540-48320-9_23
Henzinger, Thomas A, Benjamin Horowitz, and Ritankar Majumdar. “Rectangular Hybrid Games,” 1664:320–35. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1999. https://doi.org/10.1007/3-540-48320-9_23.
T. A. Henzinger, B. Horowitz, and R. Majumdar, “Rectangular hybrid games,” presented at the CONCUR: Concurrency Theory, 1999, vol. 1664, pp. 320–335.
Henzinger TA, Horowitz B, Majumdar R. 1999. Rectangular hybrid games. CONCUR: Concurrency Theory, LNCS, vol. 1664. 320–335.
Henzinger, Thomas A., et al. Rectangular Hybrid Games. Vol. 1664, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1999, pp. 320–35, doi:10.1007/3-540-48320-9_23.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar