Projet COPRIN

INRIA - Sophia Antipolis

2004 Routes des Lucioles, BP 93

06902 Sophia Antipolis - France

INRIA - Sophia Antipolis

2004 Routes des Lucioles, BP 93

06902 Sophia Antipolis - France

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.

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).

My research interests are:

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

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.

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.

**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)

**C. Grandón, T. Alfaro, M. Moossen**

*Un algoritmo evolutivo híbrido para la planificación minera por extracción subterránea.*

**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)

**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)

**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)

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

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**.

**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 ;-)

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".

- Constraints Programming
- Interval Arithmetic
- C++, Python, VTK, LaTeX (Tools)
- MathWorld, Wikipedia (Encyclopedias)
- CiteSeer (Papers)

- 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)