Grant: Discovery Grants Program - Individual
École Polytechnique de Montréal
$52,000.00
Propagating Marginal Probability Mass Functions in Constraint Programming Solvers: Challenges and Opportunities
EF 2023-24
Résumé
The core of my research has been about Constraint Programming (CP) as a computational method to solve complex combinatorial problems occurring in practice. CP models a problem through high level primitives, called constraints, that expose much of the combinatorial structure of that problem. These primitives have been identified over time as being complex enough to provide structural insight yet simple enough for some desired computing tasks to remain tractable. The distinctive driving force of CP has been this direct access to structure: it has been key to the design of powerful inference algorithms and it is increasingly exploited to learn from and to guide search. Through my current Discovery grant, I investigated even more insightful inference algorithms in the form of weighted model counting at the level of individual constraints and proposed a richer propagation medium for CP, inspired from belief propagation, in order to combine such weighted counting information. Instead of simply propagating inconsistent values from the domain of each variable, we propagate a whole marginal probability mass function over the domain of each variable. This generalization creates several opportunities but also challenges which I plan to investigate further: algorithmic challenges arising from computing such marginals for the more prevalent families of constraints as well as of the pragmatic compromises that will lead to an efficient solver; opportunities to solve combinatorial problems better but also to integrate CP solvers more naturally and broadly in machine learning architectures and to provide better search guidance in AI planning systems. The core insight of propagating marginals over variables' domains instead of simple value deletions in CP solvers is novel and I proposed it only a few years ago. Using such marginals from CP models to more naturally combine CP and neural networks is a very recent idea that I am only beginning to investigate. I expect it to have a significant impact in the field of machine learning both in the presence of deterministic constraints (structure) and as an alternative to large amounts of labeled data. CP-based AI planning is an old idea that I revisited recently with generic counting-based search heuristics to guide the construction of a plan. This has significantly improved the performance of a CP-based approach compared to other generic search heuristics. The concept of counting-based search has since evolved into using marginals to guide search but the latter has not been investigated yet for CP-based AI planning. I anticipate further improvements in performance, which could lead to a wider adoption of this approach within the AI planning research community. As for solving combinatorial problems, I expect that the further exploitation of marginal probability mass functions will have a significant impact on our ability to solve real-life problems, getting better solutions faster.
Programme
Discovery Grants Program - Individual
Bénéficiaire
Emplacement
Quebec, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
RGPIN-2023-05705
Name nom
Pesant, Gilles
Department département
Génie informatique et génie logiciel
Organization id
64
Institution établissement
École Polytechnique de Montréal
Province en
Québec
Province fr
Québec
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2023
Competition year année de concours
2023
Award amount
52000
Program id
RGPIN
Program name en
Discovery Grants Program - Individual
Program name fr
Programme de subventions à la découverte - individuelles
Group en
DISCOVERY RESEARCH
Group fr
RECHERCHE AXÉE SUR LA DÉCOUVERTE
Committee code
1507
Committee name en
Computer Science
Committee name fr
Sciences informatiques
Area of application code
520
Area of application group en
Manufacturing processes and products
Area of application group fr
Procédés et produits industriels
Area of application en
Production and operations management
Area of application fr
Production et gestion des opérations
Research subject code
9999
Research subject group en
Not available
Research subject group fr
Not available
Research subject en
Non disponible
Research subject fr
Non disponible
Application title
Propagating Marginal Probability Mass Functions in Constraint Programming Solvers: Challenges and Opportunities
Keyword
AI planning; belief propagation; combinatorial problem; constraint programming; machine learning; marginal probability mass function
Application summary
The core of my research has been about Constraint Programming (CP) as a computational method to solve complex combinatorial problems occurring in practice. CP models a problem through high level primitives, called constraints, that expose much of the combinatorial structure of that problem. These primitives have been identified over time as being complex enough to provide structural insight yet simple enough for some desired computing tasks to remain tractable. The distinctive driving force of CP has been this direct access to structure: it has been key to the design of powerful inference algorithms and it is increasingly exploited to learn from and to guide search. Through my current Discovery grant, I investigated even more insightful inference algorithms in the form of weighted model counting at the level of individual constraints and proposed a richer propagation medium for CP, inspired from belief propagation, in order to combine such weighted counting information. Instead of simply propagating inconsistent values from the domain of each variable, we propagate a whole marginal probability mass function over the domain of each variable. This generalization creates several opportunities but also challenges which I plan to investigate further: algorithmic challenges arising from computing such marginals for the more prevalent families of constraints as well as of the pragmatic compromises that will lead to an efficient solver; opportunities to solve combinatorial problems better but also to integrate CP solvers more naturally and broadly in machine learning architectures and to provide better search guidance in AI planning systems. The core insight of propagating marginals over variables' domains instead of simple value deletions in CP solvers is novel and I proposed it only a few years ago. Using such marginals from CP models to more naturally combine CP and neural networks is a very recent idea that I am only beginning to investigate. I expect it to have a significant impact in the field of machine learning both in the presence of deterministic constraints (structure) and as an alternative to large amounts of labeled data. CP-based AI planning is an old idea that I revisited recently with generic counting-based search heuristics to guide the construction of a plan. This has significantly improved the performance of a CP-based approach compared to other generic search heuristics. The concept of counting-based search has since evolved into using marginals to guide search but the latter has not been investigated yet for CP-based AI planning. I anticipate further improvements in performance, which could lead to a wider adoption of this approach within the AI planning research community. As for solving combinatorial problems, I expect that the further exploitation of marginal probability mass functions will have a significant impact on our ability to solve real-life problems, getting better solutions faster.