HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Theses

Solveurs de Contraintes Autonomes

Abstract : Constraint programming is declarative: the user models the problem (in the form of constraints) without worrying about the solving part. The solving is delegated to a generic program called a constraint solver. Constraint solvers use mechanisms from artificial intelligence to guide its choices (heuristics), and to efficiently reduce the search space (inference). Recent constraint solvers are equipped with several heuristics. Choosing the best heuristic to solve a given problem instance is currently delegated to the user. The goal of this thesis is to make constraint solvers more autonomous. We want to remove any cognitive burden from the user regarding the solving process. While searching for solutions, the solver often restarts the search to avoid expensive dead-ends. We propose to automatically select the most promising heuristic after each restart. In response to this sequential choice problem, we take inspiration from policies addressing the multi-armed bandit problem. Such policies are derived from reinforcement learning and allow to explore a set of actions while exploiting the most profitable one as often as possible. After having defined how to incorporate this machine learning tool in a solver, we propose several applications to make modern constraint solvers more autonomous. First, we apply the policies proposed in the multi-armed-bandits literature to learn the best heuristic among a set of heuristics provided by the solver. Based on this first application, we propose a new policy that is more consistent with the structure of current solvers. Still using bandit policies, we propose to adapt the amount of randomization needed to perturb a given heuristic and make it more efficient. Finally, we extend these results to constraint optimization solvers.
Complete list of metadata

https://hal-univ-artois.archives-ouvertes.fr/tel-03648917
Contributor : Hugues Wattez Connect in order to contact the contributor
Submitted on : Friday, April 22, 2022 - 9:49:28 AM
Last modification on : Tuesday, April 26, 2022 - 3:36:58 AM

File

these_light.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : tel-03648917, version 1

Collections

Citation

Hugues Wattez. Solveurs de Contraintes Autonomes. Intelligence artificielle [cs.AI]. Université d'Artois, 2021. Français. ⟨tel-03648917⟩

Share

Metrics

Record views

7

Files downloads

7