Q-intersection Algorithms for Constraint-Based Robust Parameter Estimation

Clément Carbonnel 1 Gilles Trombettoni 2 Philippe Vismara 2 Gilles Chabert 3
1 LAAS-ROC - Équipe Recherche Opérationnelle, Optimisation Combinatoire et Contraintes
LAAS - Laboratoire d'analyse et d'architecture des systèmes [Toulouse]
2 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 TASC - Theory, Algorithms and Systems for Constraints
LINA - Laboratoire d'Informatique de Nantes Atlantique, Département informatique - EMN, Inria Rennes – Bretagne Atlantique
Abstract : Given a set of axis-parallel n-dimensional boxes, the q-intersection is defined as the smallest box encompassing all the points that belong to at least q boxes. Computing the q-intersection is a combinatorial problem that allows us to han-dle robust parameter estimation with a numerical constraint programming approach. The q-intersection can be viewed as a filtering operator for soft constraints that model measure-ments subject to outliers. This paper highlights the equiva-lence of this operator with the search of q-cliques in a graph whose boxicity is bounded by the number of variables in the constraint network. We present a computational study of the q-intersection. We also propose a fast heuristic and a sophisti-cated exact q-intersection algorithm. First experiments show that our exact algorithm outperforms the existing one while our heuristic performs an efficient filtering on hard problems.
Type de document :
Communication dans un congrès
AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada. pp.2630-2636, 2014, AAAI'14 - Twenty-Eighth Conference on Artificial Intelligence
Liste complète des métadonnées


https://hal.archives-ouvertes.fr/hal-01084606
Contributeur : Gilles Chabert <>
Soumis le : vendredi 21 novembre 2014 - 22:12:43
Dernière modification le : vendredi 9 juin 2017 - 10:42:46
Document(s) archivé(s) le : vendredi 14 avril 2017 - 20:53:20

Fichier

carbonnel_et_al_aaai14.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01084606, version 1

Citation

Clément Carbonnel, Gilles Trombettoni, Philippe Vismara, Gilles Chabert. Q-intersection Algorithms for Constraint-Based Robust Parameter Estimation. AAAI Conference on Artificial Intelligence, Jul 2014, Québec City, Canada. pp.2630-2636, 2014, AAAI'14 - Twenty-Eighth Conference on Artificial Intelligence. <hal-01084606>

Partager

Métriques

Consultations de
la notice

370

Téléchargements du document

105