Senior R&D Engineer · Huawei Technologies France, Paris Research Centre · Boulogne-Billancourt, Île-de-France, France
gael.glorian@huawei.com
Gaël Glorian is a Senior R&D Engineer in the Constraint Programming team of the Paris Research Centre at Huawei Technologies France since September 2021.
Before joining Huawei he did is PhD at CRIL, Artois University in France on Hybridization of Clause Learning Techniques in Constraint Programming. He has been interested in improving the CSP (Constraint Satisfaction Problem) solving techniques, especially in a hybrid context using the power of SAT (Boolean Satisfaction Problem) inference engines.
From this work, he has developed a tool called Nacre that won two gold medals at the XCSP3 Competition - Minitrack in 2018 and 2019.
After his PhD, he worked as a postdoctoral researcher at Ubisoft Bordeaux and LaBRI, Bordeaux University for the project KIWI of Région Nouvelle-Aquitaine to meet technological challenges on a set of fields related to automation of scalable interactive simulations in real time and to analyse actors and their behavior. His missions were to improve procedural content generation techniques and to formally guarantee certain
properties at the end of this type of generation.
Abstract: This thesis belongs to the field of constraint
programming (CP), one of the
most efficient
paradigms for solving many problems (of a combinatorial nature) in AI. We have been
interested in improving the CSP (constraint satisfaction problem) solving techniques,
especially in a hybrid context using the power of SAT (Boolean satisfaction problem)
inference engines. We have developed several conflict analysis techniques to extract useful
information for resolution, through fine analysis followed by a form of learning. To achieve
this goal, we first strengthened the power of nogoods recorded by the resolution system by
proposing several rules to combine them. In addition, we integrated a SAT resolution engine
into a CP system based on the notion of lazy explanations. The use of a SAT engine is
motivated by their high efficiency in producing and manipulating simple forms of nogoods in
clausal form. The NACRE software, a generic reasoning engine, is the result of this work; In
particular, it was designed to be a hybrid solver, solving constraint satisfaction problems
using dedicated or SAT-inspired methods. Our generic (i.e., valid for any problem) approach
has proved very effective in practice (NACRE has won 2 gold medals at the XCSP competitions
2018 and 2019). In order to enrich the SAT / CP hybridization, we conducted a study on the
quality of clauses produced by the SAT engine. This allowed us to propose new methods for
clauses database reduction, minimization and new search heuristics.
Faculté Jean Perrin · Lens, Hauts-de-France · France
2014 · 2016
Bachelor’s degree in computer science
Faculté Jean Perrin · Lens, Hauts-de-France · France
2009 · 2014
Scientific Baccalaureate
Lycée Louis Pasteur · Hénin-Beaumont, Hauts-de-France · France
2006 · 2009
Publications
International
The Dungeon Variations Problem Using Constraint Programming.
[ bib |
http |
pdf]
Gaël Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon.
In Laurent D. Michel, editor, 27th International Conference on
Principles and Practice of Constraint Programming, CP 2021, Montpellier,
France (Virtual Conference), October 25-29, 2021, volume 210 of
LIPIcs, pages 27:1--27:16. Schloss Dagstuhl - Leibniz-Zentrum für
Informatik, 2021.
The video games industry generates billions of dollars in sales every year. Video games can offer increasingly complex gaming experiences, with gigantic (but consistent) open worlds, thanks to larger and larger teams of developers and artists. In this paper, we propose a constraint-based approach for procedural dungeon generation in an open world/universe context, in order to provide players with consistent, open worlds with an excellent quality of storytelling. Thanks to a global description capturing all the possible rooms and situations of a given dungeon, our approach allows enumerating variations of this global pattern, which can then be presented to the player for more diversity. We formalise this problem in constraint programming by exploiting a graph abstraction of the dungeon pattern structure. Every path of the graph represents a possible variation matching a given set of constraints. We introduce a new propagator extending the "connected" graph constraint, which allows considering directed graphs with cycles. We show that thanks to this model and the proposed new propagator, it is possible to handle scenarios at the forefront of the game industry (AAA+ games). We demonstrate that our approach outperforms non-specialised solutions consisting of filtering only the relevant solutions a posteriori. We then conclude and offer several exciting perspectives raised by this approach to the Dungeon Variations Problem.
NACRE - A nogood and clause reasoning engine.
[ bib |
http |
pdf]
Gael Glorian, Jean-Marie Lagniez, and Christophe Lecoutre.
In Elvira Albert and Laura Kovács, editors, LPAR 2020:
23rd International Conference on Logic for Programming, Artificial
Intelligence and Reasoning, Alicante, Spain, May 22-27, 2020, volume 73 of
EPiC Series in Computing, pages 249--259. EasyChair, 2020.
NACRE, for Nogood And Clause Reasoning Engine, is a constraint solver written in
C++. It is based on a modular architecture designed to work with generic constraints while
implementing several state-of-the-art search methods and heuristics. Interestingly, its data
structures have been carefully designed to play around nogoods and clauses, making it suitable for
implementing learning strategies. NACRE was submitted to the CSP MiniTrack
of the 2018 and 2019 XCSP3 [8] competitions where it took the first place. This paper
gives a general description of NACRE as a framework. We present its kernel, the available
search algorithms, and the default settings (notably, used for XCSP3 competitions), which
makes NACRE efficient in practice when used as a black-box solver.
Hybridization of clause learning techniques in constraint programming.
[ bib |
http |
pdf ]
Gael Glorian.
Theses, Université d'Artois, December 2019.
This thesis belongs to the field of constraint programming (CP), one of the most efficient
paradigms for solving many problems (of a combinatorial nature) in AI. We have been
interested in improving the CSP (constraint satisfaction problem) solving techniques,
especially in a hybrid context using the power of SAT (Boolean satisfaction problem)
inference engines. We have developed several conflict analysis techniques to extract useful
information for resolution, through fine analysis followed by a form of learning. To achieve
this goal, we first strengthened the power of nogoods recorded by the resolution system by
proposing several rules to combine them. In addition, we integrated a SAT resolution engine
into a CP system based on the notion of lazy explanations. The use of a SAT engine is
motivated by their high efficiency in producing and manipulating simple forms of nogoods in
clausal form. The NACRE software, a generic reasoning engine, is the result of this work; In
particular, it was designed to be a hybrid solver, solving constraint satisfaction problems
using dedicated or SAT-inspired methods. Our generic (i.e., valid for any problem) approach
has proved very effective in practice (NACRE has won 2 gold medals at the XCSP competitions
2018 and 2019). In order to enrich the SAT / CP hybridization, we conducted a study on the
quality of clauses produced by the SAT engine. This allowed us to propose new methods for
clauses database reduction, minimization and new search heuristics.
pFactory: A generic library for designing parallel solvers.
[ bib |
http |
pdf]
Gilles Audemard, Gael Glorian, Jean-Marie Lagniez, Valentin Montmirail, and
Nicolas Szczepanski.
In Hans Weghorn, editor, the 16th International Conference on
Applied Computing, AC'19, pages 89--96, 2019.
With the advent of multi-core processors, it makes sense to design multithreaded solvers.
Nevertheless, implementing such solvers is often a cumbersome task. Indeed, multithreaded
SAT solvers are not easy to write, and only experienced programmers should undertake to code
for these types of applications. To overcome this problem, we propose a new library that
simplifies the design of multi thread solvers. Particular care was given to make efficient
the transfer of a large amount of information between solver units. We show that it is easy
to implement parallel solvers by using pFactory on SAT paradigm. We also experimentally
validate that such solvers are competitive against state-of-the-art parallel solvers.
An incremental sat-based approach to the graph colouring problem.
[ bib |
http |
pdf]
Gael Glorian, Jean-Marie Lagniez, Valentin Montmirail, and Nicolas
Szczepanski.
In Thomas Schiex and Simon de Givry, editors, Principles and
Practice of Constraint Programming · 25th International Conference, CP
2019, Stamford, CT, USA, September 30 · October 4, 2019, Proceedings, volume
11802 of Lecture Notes in Computer Science, pages 213--231. Springer,
2019.
We propose and evaluate a new CNF encoding based on Zykov’s tree
for computing the chromatic number of a graph. Zykov algorithms are branchand-bound procedures, that
branch on pairings of vertices that express whether or
not two non-adjacent vertices have the same colour. Thus, vertices with the same
colour are contracted whereas edges are added between vertices when they have
different colours. Such pairings make possible the use of a well-known recurrence
relation, that states that the chromatic number of a graph cannot be lower than the
the chromatic number of its subgraphs. Our encoding associates with any graph
and integer k a CNF formula that is satisfiable if and only if the chromatic number
of the graph is at least k. We first show that any colouring satisfying a complete
pairing always required a fixed number of colours. Then, we establish a CNF encoding that counts the
number of colours required by a pairing. However, due to
a large number of clauses required to encode transitivity constraints on pairings, a
direct encoding does not scale well in practice. To avoid this pitfall, we designed
a CEGAR-based (Counter-Example Guided Abstraction Refinement) approach
that only encodes a part of the problem and then adds the missing constraints in
an incremental way until a valid solution with k colours is found or the unsatisfiability of the problem
is proven, meaning that the chromatic number of the graph
is greater than k. We show that our encoding scheme performs in many cases
significantly better than the state-of-the-art approaches to colouring.
An incremental sat-based approach to reason efficiently on
qualitative constraint networks.
[ bib |
http |
pdf]
Gael Glorian, Jean-Marie Lagniez, Valentin Montmirail, and Michael Sioutis.
In John N. Hooker, editor, Principles and Practice of Constraint
Programming · 24th International Conference, CP 2018, Lille, France, August
27-31, 2018, Proceedings, volume 11008 of Lecture Notes in Computer
Science, pages 160--178. Springer, 2018.
The RCC8 language is a widely-studied formalism for describing topological arrangements of
spatial regions. Two fundamental reasoning problems that are associated with RCC8 are the problems of
satisfiability and realization. Given a qualitative constraint network (QCN) of RCC8, the
satisfiability problem is deciding whether it is possible to assign regions to the spatial variables of
the QCN in such a way that all of its constraints are satisfied (solution). The realization problem is
producing an actual spatial model that can serve as a solution. Researchers in RCC8 focus either
on symbolically checking the satisfiability of a QCN or on presenting a method to realize (valuate)
a satisfiable QCN. To the best of our knowledge, a combination of those two lines of research has
not been considered in the literature in a unified and homogeneous approach, as the first line deals
with native constraint-based methods, and the second one with rich mathematical structures that are
difficult to implement. In this article, we combine the two aforementioned lines of research and explore
the opportunities that surface by interrelating the corresponding reasoning problems, viz., the
problems of satisfiability and realization. We restrict ourselves to QCNs that, when satisfiable, are
realizable with rectangles. In particular, we propose an incremental SAT-based approach for providing a
framework that reasons about the RCC8 language in a counterexample-guided manner. The
incrementality of our approach also avoids the usual blow-up and the lack of scalability in SAT-based
encodings. Specifically, our SAT-translation is parsimonious, i.e, constraints are added incrementally
in a manner that guides the embedded SAT-solver and forbids it to find the same counter-example
twice. We experimentally evaluated our approach and studied its scalability against state-of-the-art
solvers for reasoning about RCC8 relations using a varied dataset of instances. The approach scales
up and is competitive with the state of the art for the considered benchmarks.
Combining nogoods in restart-based search.
[ bib |
http |
pdf]
Gael Glorian, Frédéric Boussemart, Jean-Marie Lagniez, Christophe
Lecoutre, and Bertrand Mazure.
In J. Christopher Beck, editor, Principles and Practice of
Constraint Programming · 23rd International Conference, CP 2017, Melbourne,
VIC, Australia, August 28 · September 1, 2017, Proceedings, volume 10416 of
Lecture Notes in Computer Science, pages 129--138. Springer, 2017.
Nogood recording is a form of learning that has been shown useful for solving constraint satisfaction
problems. One simple approach involves recording nogoods that are extracted from the rightmost
branches of the successive trees built by a backtrack search algorithm with restarts. In this paper, we
propose several mechanisms to reason with so-called increasing-nogoods that exactly correspond to
the states reached at the end of each search run. Interestingly, some similarities that can be observed
between increasing-nogoods allow us to propose new original ways of dynamically combining them
in order to improve the overall filtering capability of the learning system. Our preliminary results
show the practical interest of our approach.
National
Génération de donjons à l'aide de la programmation par contraintes.
[ bib |
pdf]
Gael Glorian, Adrien Debesson, Sylvain Yvon-Paliot, and Laurent Simon.
In Seizièmes Journées Francophones de Programmation par Contraintes, JFPC 2021, Nice, France, 22 au 24 juin, 2021, Actes.
L'industrie du jeu vidéo est l'une des plus importantes industries du secteur du loisir, générant des milliards de dollars de chiffre d'affaire chaque année. Les jeux vidéos se doivent donc d'offrir des expériences de jeu de plus en plus complexes, impliquant des équipes de développeurs et d'artistes de plus en plus importantes. Dans cet article, nous proposons une approche basée sur la programmation par contraintes pour la génération procédurale de donjons dans un contexte de monde/univers ouvert, dans le but d'offrir aux joueurs des mondes ouverts mais offrant une excellente cohérence et une narration de qualité. Grâce à une description globale capturant toutes les salles et situations possibles d'un donjon donné, notre approche propose d'énumérer des variations de ce schéma global, pouvant alors être présentées au joueur pour plus de diversité. Nous formalisons ce problème à l'aide de la programmation par contraintes en exploitant une abstraction sous forme de graphe de la structure du donjon, sur laquelle chaque chemin intéressant représente une variation possible correspondant aux contraintes désirées. Pour ce faire, nous introduisons un nouveau propagateur étendant la contrainte de graphe connected, qui per-met de considérer des graphes dirigés avec cycles. Nous montrons que, grâce à cette modélisation et le nouveau propagateur proposé, il est possible de prendre en compte des scénarios réalistes pouvant être utilisés dans les jeux AAA. Nous démontrons son efficacité en la comparant à une solution de base consistant à filtrer uniquement les solutions pertinentes a posteriori.
Une approche sat incrémentale pour raisonner efficacement sur les
réseaux de contraintes qualitatives.
[ bib |
pdf]
Gael Glorian, Jean-Marie Lagniez, Valentin Montmirail, and Michael Sioutis.
In Quizièmes journées Francophones de Programmation par
Contraintes, JFPC 2019, Albi, France, 10 au 13 juin, 2019, Actes,
volume 15, pages 67--76. AFPC, 2019.
Le langage RCC8 est un formalisme largement utilisé
pour décrire des arrangements topologiques de régions
dans l’espace. Deux problèmes fondamentaux sont associés au langage RCC8 : la satisfiabilité et la
réalisation.
Soit un réseau de contraintes qualitatives (QCN) de RCC8,
le problème de satisfiabilité est de décider s’il est possible d’assigner des régions aux variables du
QCN de telle
sorte que les contraintes soient satisfaites (solution). Le
problème de réalisation est le fait de produire un modèle
spatial qui peut servir de solution. Dans cet article, nous
combinons les deux lignes de recherches mentionnés audessus et nous explorons l’idée de relier le
problème de
satisfiabilité et de réalisation. Nous nous limitons aux QCN
qui, quand ils sont satisfiables, sont réalisables avec des
rectangles. En effet, nous proposons une approche SAT incrémentale afin d’être capable de raisonner sur
le langage
RCC8 en nous laissant guider par les contre-exemples.
Nous avons expérimentalement évalué notre approche
et étudié ses performances face aux solveurs de l’état
de l’art pour raisonner en RCC8 en utilisant de nombreux
ensembles d’instances. Notre approche tient la charge et
est compétitive face aux solveurs de l’état de l’art sur les
instances considérées.
Combinaison de nogoods extraits au redémarrage.
[ bib |
pdf]
Gael Glorian, Frédéric Boussemart, Jean-Marie Lagniez, Christophe
Lecoutre, and Bertrand Mazure.
In Treizièmes journées Francophones de Programmation par
Contraintes, JFPC 2017, Montreuil-sur-mer, France, 13 au 15 juin, 2017,
Actes, volume 13, pages 55--64. AFPC, 2017.
Dans cet article, nous nous intéressons à l’enregistrement de nogoods, instanciations partielles
globalement incohérentes, pouvant être extraits systématiquement lors du
redémarrage d’un algorithme complet (avec retour-arrière)
de résolution CSP (problème de satisfaction de contraintes).
Plus précisément, dans ce contexte, nous proposons plusieurs techniques de simplification et de
combinaison de
nogoods, dans le but d’accroître leur capacité de filtrage.
La base de notre approche est une généralisation des
nld-nogoods correspondant au concept introduit récemment d’increasing-nogoods. Nous proposons plusieurs
algorithmes portant sur des combinaisons de sous-ensembles
de nogoods identifiés de manière dynamique. Les simila15 rités entre les différents increasing-nogoods
permettent un
meilleur élagage de l’arbre de recherche, notamment grâce
à l’exploitation d’équivalences entre décisions. Nous proposons aussi quelques pistes d’amélioration,
notamment un
système de sentinelles et la génération de nld-nogoods à la
volée. Nos résultats préliminaires montrent l’intérêt de notre
approche pour certains problèmes.
Solver description
Nacre.
[ bib |
http |
pdf]
Gael Glorian.
In Christophe Lecoutre and Olivier Roussel, editors, Proceedings
of the 2018 XCSP3 Competition, pages 85--85, 2019.
NACRE (Nogood And Clause Reasoning Engine) is a constraint solver written in C++. The
main purpose of this solver is to experiment nogood recording (with a clause reasoning engine) in
Constraint Programming (CP). In particular, the data structures of the solver have been carefully
designed to play around nogoods and clauses. This is the first version of the solver and its first
submission ever to a competition.
Tools
NACRE
NACRE, for Nogood And Clause Reasoning Engine, is a constraint solver written in C++. It is
based on a modular architecture designed to work with generic constraints while implementing
several state-of-the-art search methods and heuristics. Interestingly, its data structures
have
been carefully designed to play around nogoods and clauses, making it suit-able for
implementing
learning strategies. NACRE was submitted to theCSP MiniTrack of the 2018 and 2019 XCSP3 [8]
competitions where it took the first place. This paper gives a general description of NACRE
as a
framework. We present its kernel, the available search algorithms, and the default settings
(notably, used for XCSP3 competitions), which makes NACRE efficient in practice when used as
a
black-box solver.
pFactory
pFactory is a parallel library designed to support and facilitate the implementation of
parallel solvers in C++. It provides robust implementations of parallel algorithms and
allows seamlessly sharing mechanisms, divide-and-conquer or portfolio methods. pFactory
is not related to a specific problem and can very easily be incorporated in order to
solve any kind of combinatorial problem (SAT, CSP, MAXSAT...).
Awards
1
st
Place · NACRE solver · XCSP3 Competition
2019 · CSP
Minitrack · Stamford, CT, USA
1
st
Place · NACRE solver · XCSP3 Competition
2018 · CSP
Minitrack · Lille, France