Skip to Main content Skip to Navigation
Reports

A Specific Quantifier Elimination for Inner Box Test in Distance Constraints with Uncertainties

Carlos Grandón 1 Bertrand Neveu 1
1 COPRIN - Constraints solving, optimization and robust interval analysis
CRISAM - Inria Sophia Antipolis - Méditerranée , ENPC - École des Ponts ParisTech
Abstract : This document presents a specific quantifier elimination algorithm for distance constraints with uncertainties represented by constraints with existentially quantified parameters. Generally, the solution set of this type of constraints has a non-null volume, and therefore an interval based solver that implements a branch and prune algorithm will bisect again and again the boxes included inside the solution set, leading to inefficient computation. This situation can be strongly improved using a test for detecting inner boxes. In this work, we show how interval arithmetics can be successfully used for building an inner box test in some types of constraints and how it can be combined with a quantifier elimination algorithm for handling constraints with existentially quantified parameters.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00071385
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:06:07 PM
Last modification on : Saturday, April 7, 2018 - 1:18:24 AM
Long-term archiving on: : Tuesday, February 22, 2011 - 11:55:23 AM

Identifiers

  • HAL Id : inria-00071385, version 1

Collections

Citation

Carlos Grandón, Bertrand Neveu. A Specific Quantifier Elimination for Inner Box Test in Distance Constraints with Uncertainties. [Research Report] RR-5883, INRIA. 2006. ⟨inria-00071385⟩

Share

Metrics

Record views

170

Files downloads

244