A CSP versus a zonotope-based method for solving guard set intersection in nonlinear hybrid reachability

Moussa Maïga (1, 2) , Nacim Ramdani (1) , Louise Travé-Massuyès (2) , Christophe Combastel (3)

1 IRAUS - Département Images, Robotique, Automatique et Signal [Orléans]
2 LAAS-DISCO - Équipe DIagnostic, Supervision et COnduite
3 ENSEA - Ecole Nationale Supérieure de l'Electronique et de ses Applications

Computing the reachable set of hybrid dynamical systems in a reliable and verified way is an important step when addressing verification or synthesis tasks. This issue is still challenging for uncertain nonlinear hybrid dynamical systems. We show in this paper how to combine a method for computing continuous transitions via interval Taylor methods and a method for computing the geometrical intersection of a flowpipe with guard sets, to build an interval method for reachability computation that can be used with truly nonlinear hybrid systems. Our method for flowpipe guard set intersection has two variants. The first one relies on interval constraint propagation for solving a constraint satisfaction problem and applies in the general case. The second one computes the intersection of a zonotope and a hyperplane and applies only when the guard sets are linear. The performance of our method is illustrated on examples involving typical hybrid systems.

Mots clés: Intervals analysis; hybrid systems; event detection; event localization; zonotope; reachability analysis

Domaines: Intelligence artificielle [cs.AI]

Moussa Maïga, Nacim Ramdani, Louise Travé-Massuyès, Christophe Combastel. A CSP versus a zonotope-based method for solving guard set intersection in nonlinear hybrid reachability. Mathematics in Computer Science, 2014, Interval Methods and Applications, 8 (3-4), pp.407-423. ⟨hal-01400366⟩