# Universally quantified interval constraint solving

**View the full content.**View Full Document

0 0 4 views

**Unformatted text preview: **

Universally Quantified Interval Constraint Solving Fre de ric Benhamou and Fre de ric Goualard Institut de Recherche en Informatique de Nantes France Universally Quantified Interval Constraint Solving p 1 Motivations x 3 sin cos sin cos 3 3 2 2 1 1 0 0 1 1 2 2 3 3 Object with trajectory y 3 sin cos sin cos z 0 Universally Quantified Interval Constraint Solving p 2 Motivations x 3 sin cos sin cos 3 3 3 2 2 1 1 0 0 1 1 2 2 Positions of a camera s t 0 5 at any time 3 Object with trajectory y 3 sin cos sin cos z 0 Universally Quantified Interval Constraint Solving p 2 Motivations x 3 sin cos sin cos 3 2 2 1 1 0 0 1 1 2 2 Positions of a camera s t 0 5 at any time 3 Object with trajectory y 3 sin cos sin cos z 0 3 sin cos sin cos x 2 3 sin cos sin cos y 2 z 2 3 3 0 5 Universally Quantified Interval Constraint Solving p 2 Motivations x 3 sin cos sin cos Object with trajectory y 3 sin cos sin cos z 0 Positions of a camera s t 0 5 at any time 3 sin cos sin cos x 2 3 sin cos sin cos y 2 z 2 0 5 Non linear real constraint compulsory to solve it soundly Universally Quantified Interval Constraint Solving p 2 Outline Sound techniques Cylindrical Algebraic Decomposition Interval arithmetic and inner approximation computation Complete techniques Interval constraint solving Interval constraint solving and soundness Solving constraints with universal quantifiers Conclusion and perspectives Universally Quantified Interval Constraint Solving p 3 Cylindrical Algebraic Decomposition Collins 1973 quantifier elimination Powerful method handling of universal existential quantifiers Sound solving of real constraints Universally Quantified Interval Constraint Solving p 4 Cylindrical Algebraic Decomposition Collins 1973 quantifier elimination Powerful method handling of universal existential quantifiers Sound solving of real constraints But Method restricted to polynomial constraints High complexity time consuming Universally Quantified Interval Constraint Solving p 4 Interval Arithmetic Moore