Hybrid Systems: Computation and Control

This volume contains the proceedings ofthe 11th Workshop on Hybrid Systems: Computation and Control (HSCC 2008) held in St. Louis, Missouriduring April 22-24,2008.The annual workshop on hybrid systems focuses on researchin - bedded,reactivesystemsinvolvingtheinterplaybetweensymbolic/switchingand continuous dynamical behaviors. HSCC attracts academic as well as industrial researchers to exchange information on the latest developments of applications and theoretical advancements in the design, analysis, control, optimization, and implementation of hybrid systems, with particular attention to embedded and networked control systems. New for this year was that HSCC was part of the inaugural CPSWEEK (Cyber-Physical Systems Week) - a co-located cluster of three conferences: HSCC, RTAS (Real-Time and Embedded Technology and Applications Sym- sium), and IPSN (International Conference on Information Processing in Sensor Networks). The previous workshops in the series of HSCC were held in Berkeley, USA (1998),Nijmegen,TheNetherlands(1999),Pittsburgh,USA(2000),Rome,Italy (2001), Palo Alto, USA (2002), Prague, Czech Republic (2003), Philadelphia, USA (2004),Zurich, Switzerland (2005) , Santa Barbara,USA (2006), and Pisa, Italy (2007). We would like to thank the Program Committee members and the reviewers for an excellent job of evaluating the submissions and participating in the online Program Committee discussions. We are grateful to the Steering Committee for their helpful guidance and support. We would also like to thank Patrick Martin for putting together these proceedings, and Jiuguang Wang for developing and maintaining the HSCC 2008 website. January 2008 Magnus Egerstedt Bud Mishra Organization HSCC 2008 was technically co-sponsored by the IEEE Control Systems Society andorganized in cooperation with ACM/SIGBED.

This book constitutes the refereed proceedings of the 11th International Conference on Hybrid Systems: Computation and Control, HSCC 2008. The 42 revised full papers and 20 revised short papers were carefully reviewed and selected from numerous submissions.

Regular Papers.- Markov Set-Chains as Abstractions of Stochastic Hybrid Systems.- Co-simulation Tools for Networked Control Systems.- On the Maximum Principle for Impulsive Hybrid Systems.- Algebraic Identification of MIMO SARX Models.- Contract-Based Design for Computation and Verification of a Closed-Loop Hybrid System.- Controller Synthesis with Budget Constraints.- Trading Infinite Memory for Uniform Randomness in Timed Games.- Solutions to Switched Hamilton-Jacobi Equations and Conservation Laws Using Hybrid Components.- Lost in Translation: Hybrid-Time Flows vs. Real-Time Transitions.- A Control Lyapunov Approach to Predictive Control of Hybrid Systems.- Discrete and Hybrid Stochastic State Estimation Algorithms for Networked Control Systems.- Anytime Control Algorithms for Embedded Real-Time Systems.- Stochastic Satisfiability Modulo Theory: A Novel Technique for the Analysis of Probabilistic Hybrid Systems.- A Counterexample-Guided Approach to Parameter Synthesis for Linear Hybrid Automata.- Approximately Bisimilar Symbolic Models for Incrementally Stable Switched Systems.- Zonotope/Hyperplane Intersection for Hybrid Systems Reachability Analysis.- Learning and Detecting Emergent Behavior in Networks of Cardiac Myocytes.- Compositional Modeling and Minimization of Time-Inhomogeneous Markov Chains.- Observer-Based Control of Linear Complementarity Systems.- Complementarity Systems in Constrained Steady-State Optimal Control.- Dealing with Nondeterminism in Symbolic Control.- Safety and Liveness in Intelligent Intersections.- LTLC: Linear Temporal Logic for Control.- Switched and PieceWise Nonlinear Hybrid System Identification.- Verification of Supervisory Control Software Using State Proximity and Merging.- Optimotaxis: A Stochastic Multi-agent OptimizationProcedure with Point Measurements.- Noncausal Optimal Tracking of Linear Switched Systems.- Realization Theory for Discrete-Time Semi-algebraic Hybrid Systems.- A Decidable Class of Planar Linear Hybrid Systems.- Reachability of Uncertain Nonlinear Systems Using a Nonlinear Hybridization.- Modeling and Simulation of Biochemical Processes Using Stochastic Hybrid Systems: The Sugar Cataract Development Process.- Distributed Lyapunov Functions in Analysis of Graph Models of Software.- On the Optimality of Dubins Paths across Heterogeneous Terrain.- Switching Surface Design for Periodically Operated Discretely Controlled Continuous Systems.- Discrete Dynamics of Two-Dimensional Nonlinear Hybrid Automata.- Input-to-State Stabilization with Quantized Output Feedback.- Bisimilar Finite Abstractions of Interconnected Systems.- On Controllability of Timed Continuous Petri Nets.- Parameter Synthesis for Piecewise Affine Systems from Temporal Logic Specifications.- Necessary Conditions for the Impulsive Time-Optimal Control of Finite-Dimensional Lagrangian Systems.- Composition of Motion Description Languages.- On Optimal Quadratic Regulation for Discrete-Time Switched Linear Systems.- Short Papers.- Approximation of General Stochastic Hybrid Systems by Switching Diffusions with Random Hybrid Jumps.- On Stability of Switched Linear Hyperbolic Conservation Laws with Reflecting Boundaries.- Sampling-Based Resolution-Complete Algorithms for Safety Falsification of Linear Systems.- Reachability Analysis of Stochastic Hybrid Systems by Optimal Control.- An Integrated Approach to Parametric and Discrete Fault Diagnosis in Hybrid Systems.- d-IRA: A Distributed Reachability Algorithm for Analysis of Linear Hybrid Automata.- Sufficient Conditions for Zeno Behavior in Lagrangian Hybrid Systems.- Separation in Stability Analysis of Piecewise Linear Systems in Discrete Time.- Level Set Methods for Computing Reachable Sets of Hybrid Systems with Differential Algebraic Equation Dynamics.- Approximate Control Design for Solar Driven Sensor Nodes.- Modular Development of Hybrid Systems for Verification in Coq.- Steering a Leader-Follower Team Via Linear Consensus.- Logical Verification and Systematic Parametric Analysis in Train Control.- Information Theoretical Approach to Identification of Hybrid Systems.- A Policy Iteration Technique for Time Elapse over Template Polyhedra.- Generating Box Invariants.- Qualitative Stability Patterns for Lotka-Volterra Systems on Rectangles.- Sampled-Data Event Control of Hybrid Systems for Control Specifications Given by Predicates.- On the Timing of Discrete Events in Event-Driven Control Systems.- Decentralized Event-Triggered Broadcasts over Networked Control Systems.