DELCO

This project aims at building on the recent progress in deep learning and reinforcement learning to design a new generation of more general constraint satisfaction and optimization (CSOP) solvers. More precisely, our goal is to develop a methodology to learn search heuristics that can be used to make informed branching decisions during the search. To achieve this result, we will use convolutional neural networks (CNNs) in order to model complex relations between the state of a CSOP and the optimal branching decision. We will also rely on the reinforcement learning framework to train the heuristic using sparse, but relevant rewards such as final execution time or number of nodes explored. Together, these two techniques will be used to quickly drive the search towards good feasible solutions without too much backtracking. During the project, we will evaluate the applicability of this approach on a variety of tasks. We will start with simple grid-based problems and puzzle games as they can be directly processed by CNNs. Later, we will address more complex graph-based problems using graph embeddings. We will also combine learned search heuristics with different search strategies, ranging from basic greedy search, to state-of-the-art solvers using complex constraint propagation techniques. We will be particularly careful at investigating the possible synergies between constraint propagation and learning. Since the generality of the approach is an important focus of this project, we will investigate several machine learning techniques that can be used to train more general and robust models. In particular, we will look at generating hard instances instances (i.e. instances that are difficult to solve), and we will adapt the GAN framework (Generative Adversarial Networks) to CSOPs. These new techniques will be useful to build search heuristics that are more robust to corner cases, and can be reused on different variations of similar problems. The success of our approach relies on a solid experimental methodology. In our project, an engineer will set up an automated testing plateform, that will be used along the course of the project to provide reliable evaluation metrics as well as rich experimental insights. Upon success, we can expect the following breakthroughs: - More general and efficient CSOP solving strategies. In particular, solving strategies whose efficiency does not depend on the way a problem is encoded using variables and constraints. This will make CSOP solving more accessible to non-experts. - CSOP solvers combining local logical reasoning, and long term probabilistic reasoning, paving the way for a new solver paradigm. - Hybrid solvers exploiting highly parallel GPU architectures (for inference) as well as CPU (for search). - New techniques for learning robust branching decisions based on recent developments such as GANs.