Topic description
Contexte
En programmation par contraintes (CP), le domaine est généralement fini. Il peut inclure des valeurs numériques ou symboliques. Un problème de satisfaction de contraintes (CSP) permet de modéliser ce type de problèmes combinatoires [1].
Cependant, dans de nombreux cas réels, le domaine peut être infini, comme l'espace ou le temps. Les valeurs du domaine peuvent également être vagues ou imprécises. Par exemple, on peut vouloir planifier une tâche avant une autre sans connaître les durées exactes ni les intervalles entre elles.
C'est pourquoi le raisonnement spatio-temporel qualitatif (QSTR) a émergé. Il peut être vu comme une variante de la programmation par contraintes avec des domaines infinis. Des algèbres de relations abstraites sont souvent utilisées pour modéliser les contraintes et effectuer un raisonnement symbolique [2,3]. Dans une telle algèbre, on peut utiliser une relation comme « avant ou après » pour contraindre deux intervalles temporels, sans nécessiter d'informations quantitatives sur ces intervalles ou sur la relation elle-même.
Motivation
Les données du monde réel sont souvent hétérogènes. Il existe de multiples sources d'information pour un même problème. Les connaissances disponibles sont souvent partielles, incomplètes ou bruitées. Pour ces raisons, ni l'approche quantitative ni l'approche qualitative basée sur des contraintes ne suffisent généralement à elles seules pour modéliser un problème complexe et réaliste. Il est donc souvent nécessaire de faire des hypothèses ou des compromis.
Par exemple, l'environnement impose des contraintes quantitatives fixes et strictes. Celles-ci incluent les structures physiques et spatiales, ainsi que des aspects temporels comme la durée d'une journée. En même temps, de nombreuses actions spatio-temporelles sont dynamiques et flexibles. Par exemple, conduire une voiture dans une direction donnée peut nécessiter de respecter des contraintes de temps tout en s'adaptant aux situations. Ces actions sont souvent décrites en termes proches du langage humain, comme « prenez la première à gauche après le prochain feu de signalisation ».
Objectifs
L'objectif principal de cette thèse est de développer un cadre qui unifie les contraintes quantitatives et qualitatives. Les utilisateurs doivent pouvoir modéliser leurs problèmes en utilisant des contraintes quantitatives, qualitatives, ou les deux.
Par exemple : « Planifier la tâche A avant la tâche B, mais pas plus tôt que 2 heures avant. »
Ou encore : « Placer l'objet X à droite de l'objet Y, mais à une distance d'au moins 1 mètre. »
L'objectif secondaire de cette thèse est de valider ce cadre à l'aide de cas d'usage réels. Ceux-ci incluent : la conception de vergers maraîchers et la modélisation de leur évolution dans le temps, avec des applications en agroécologie [4] ; ou encore la modélisation de compositions musicales, où les contraintes qualitatives capturent la structure ou l'évolution harmonique, tandis que les contraintes quantitatives représentent les notes et les accords, avec des applications en intelligence artificielle, en arts et en créativité [5].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Context
In Constraint Programming (CP), the domain is usually finite. It can
include numerical or symbolic values. A Constraint Satisfaction
Problem (CSP) can model such combinatorial problems [1]. However, in
many real-world cases, the domain can be infinite, such as space or
time. Domain values may also be vague or imprecise. For example, we
might want to schedule a task before another without knowing the exact
durations or gaps between them. This is why Qualitative
Spatio-Temporal Reasoning (QSTR) has emerged. It can be seen as a
variant of CP with infinite domains. Abstract relation algebras are
often used to model constraints and reason symbolically [2,3]. In such
an algebra, we could use a relation like “before or after” to
constrain two temporal intervals. No quantitative information is
required for the intervals or the relation itself.
Motivation
Real-world data is often heterogeneous. Multiple sources of
information exist for a single problem. Knowledge about the problem is
often partial, incomplete, or noisy. For these reasons, neither the
quantitative nor the qualitative constraint-based approach alone is
usually enough to model a complex, realistic problem. Some assumptions
or compromises are typically needed. For instance, the environment
imposes fixed, hard, quantitative constraints. These include physical
and spatial structures, as well as temporal aspects, such as the
duration of a day. At the same time, many spatio-temporal actions are
dynamic and flexible. For example, navigating a car to a certain
direction can also require following time constraints while adapting
to situations. These actions are often described in human-like terms,
such as “take the first left after the next traffic light.”
Goals
The main goal of this thesis is to develop a framework that unifies
quantitative and qualitative constraints. Users should be able to
model problems using quantitative constraints, qualitative
constraints, or both. Examples include statements like: “Schedule
task A before task B, but no earlier than 2 hours before.” “Place
item X to the right of item Y, but at least 1 meter away.” The
secondary goal of this thesis is to validate the framework with
real-world use cases. These include: Designing vegetable orchards and
modeling their evolution over time, with applications in agroecology
[4]; or: Modeling musical compositions, where qualitative constraints
capture the structure or harmonic evolution, while quantitative
constraints represent notes and chords, with applications in AI, arts,
and creativity [5].
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Début de la thèse : 01/10/
Funding category
Public funding alone (i.e. government, region, European, international organization research grant)
Funding further details
Concours pour un contrat doctoral
En cliquant sur "JE DÉPOSE MON CV", vous acceptez nos CGU et déclarez avoir pris connaissance de la politique de protection des données du site jobijoba.com.