Carlos Grandón's Home Page

Presentation

Hello!. My name is Carlos Grandón. I'm Engineer in Computer Sciences and I have a Master degree in Computer Sciences from Federico Santa María University (UTFSM). At present, I'm doing a PhD in the COPRIN project of the French National Institute for Research in Computer Science and Control (INRIA) in Sophia Antipolis.

I belong to the second generation of Chileans arrived to INRIA, in the framework of an international agreement between the National Commission for Scientific and Technological Research of Chile (CONICYT) and the INRIA - Sophia Antipolis research unit, which supports scholarships for superior studies in this center.

My thesis subject is solving systems of equations with uncertainties, and more specifically, solving distance equations systems when there are uncertainties in the measure of distances in one o more equations. My PhD advisor is Bertrand Neveu, who works on solving CSP (Constraint Satisfaction Problems) since 1992.

Research

The subject of my thesis is to develop a methodology based on constraint programming for tackling uncertainty in Numeric CSP. In order to limit the research, we study the quadratic problems (the first step to the nonlinear problems), particularly, the systems of distance equations, since these have special characteristics that facilitate their study (continuity, symmetry, differentiation, among others).

Research interests

My research interests are:

Interval Arithmetic (Interval analysis).
Techniques for solving Numeric CSPs.
Tackling uncertainties in equations systems.
Filtering and consistency in continuous domains.

Problem Description

A more formal description of the problem is:

We have a set of n points in the real space, in principle, of two or three dimensions, and a set of m relations among them (distance between pairs of points). Knowing that we don't have the exact value of the distance between one or more pairs of points, but a little interval [a,b], we want to determine as precise as possible, the positions of the points in the space. Figure 1 and Figure 2 show a distance constraint between three points in a two dimensional space. Figure 1 shows the problem without uncertainty, whereas figure B shows the same problem when the distance is determined by an interval.

Figura 1: Problem without uncertainty

Figura 2: Problem with uncertainty

The first difficulty that we found when the problem has uncertainties, is the number of solutions. The uncertainty transforms solution points (ABC and ABC') into connected sets containing each an infinite number of solutions (shown in red color in the figure 2). There are an continuous of solutions to the problem in both sets (in addition these sets are nonconvex). The aim is to identify the sets (more precisely, the solution configurations) as precise as prossible, using convex sets.

Publications

Conference full Papers

C. Grandón, A. Goldsztejn
Quantifier Elimination versus Generalized Interval Evaluation: A comparison on a Special Class of Quantified Constraints. In Proc. of IPMU 2006, pages 786--793, Paris, France, 2006. (BibTeX)
C. Grandón, N. Morales, G. Chabert
A Strategy for solving Systems of Equations with Uncertainties. Accepted for publication in SCAN 2006, Duisburg, Germany, 2006. (BibTeX)
M.C. Riff, T. Alfaro, X. Bonnaire, C. Grandón
An evolutionary algorithm to solve a Mine Planning Problem. Accepted for publication in NMA'06, Borovets, Bulgaria, 2006. (BibTeX)
C. Grandón, R. Torres, M.C. Riff
Evaluación de algoritmos híbridos basados en colonias de hormigas para TSP. The Fourth Chilean Operations Research Conference, OPTIMA 2001, Curicó, Chile, 2001. (BibTeX)

International Workshops

C. Grandón, T. Alfaro, M. Moossen
Un algoritmo evolutivo híbrido para la planificación minera por extracción subterránea. XXII International Conference of the Chilean Computer Science Society, Copiapó, Chile, 2002. (BibTeX)

Short Papers and Posters

C. Grandón, A. Goldsztejn
Inner Aproximation of Distance Constraints with Existentially Quantified Parameters.. In proceedings of the 2006 ACM symposium on Applied computing, Dijon, France, 2006. ACM Press. (poster) (BibTeX)
C. Grandón, B. Neveu
Using Constraint Programming for Solving Distance CSP with Uncertainty. In Principles and Practice of Constraint Programming - CP 2005, Sitges, Spain. LNCS 3709, 2005. (full paper) (BibTeX)

Technical and Research Reports

C. Grandón, B. Neveu
A Specific Quantifier Elimination for Inner Box Test in Distance Constraints with Uncertainties . Research Report 5883, INRIA Sophia-Antipolis, France, 2006. (BibTeX)

Thesis

C. Grandón
Programación con restricciones para el tratamiento de incertidumbre en CSP numéricos (In Spanish). Master Thesis in Computer Sciences, Federico Santa María Technical University, Valparaíso, Chile, 2004. (BibTeX)

Downloads

You can find here some resources and examples of my work.

Mapa v1.0

Mapa (MA Petite Application) is a small program that allows one to display boxes in 2D and 3D. It was made to graphically show the results of the algorithm we use. Basically it is a Python script that uses VTK and TKinter to do interact the graphical interface with the user. It runs on Linux and the documentation is in Spanish, English and French. The right animation was completely made in Mapa.

Executable: Mapa-v1.0
Documentation español, english, français.

Lastest News!!!. I did some little changes for using Mapa in a Windows based Machine. The script is basically the same, but it needs some additional tools (like python and VTK compiled and installed on Windows). The good news is I have these tools. The bad news is you must install it on your windows machine.

Look my Readme in order to do it. You will need:

1. Python installer (I got it from http://www.python.org)
2. Vtk-python (I got it from http://mayavi.sourceforge.net)
3. vtkRenderingPythonTkWidgets.dll (It comes with the vtk-python installer)
4. Mapawin (of course, my program ;-)

Links

This section is dedicated to give useful information, as general as personal nature. In the first half there are many links to the subjects in which I work. In the second half, there are some interesting links (specially for my compatriots and foreigners), related to the transports, the life in France and the "bureaucracy".

General links

Personal Links

Mi página de ayuda a la comunidad (en construcción)
Envibus, Sophia Express, SNCF (bus and trains)
EasyJet, Ryanair, GermanWings (very cheap airline companies)
Mappy (maps of the zone)
Jeunes (The French yellow pages)
CIV (Practically, all people arriven here the first time)
CAF (It provides aid for lodging)