36
Certaines instances industrielles avec plus d’un million de variables booléennes sont résolues. Sur les
instances aléatoires, les algorithmes heuristiques dominent (Survey Propagation). Sur les problèmes
réels (industriels, jeux, scientifiques), les méthodes exactes, s’appuyant sur le ``Clause Learning'' dominent. Comme pour le “Deep Learning”, ce succès reste mystérieux. Des progrès similaires sont
obtenus dans le domaine des modèles graphiques déterministes (réseaux de contraintes, problème
CSP), en particulier via l’introduction des``contraintes globales'' et l’exploitation explicite de la structure des problèmes. Les jeux NP-complets usuels (Sudoku, Nonogrammes, Candy Crush. . . ) sont
trivialement résolus par ces outils. Les Sudoku du journal “Le Monde” sont synthétisés par un exchercheur du domaine (Y. Georget).
2000- : ces progrès se répandent au travers de l’introduction de “langages” s’appuyant sur ces progrès
fondamentaux dans les outils de résolution associés: ASP (Answer Set Programming), SMT (SAT
Modulo Theory), à côté de CP. L’intérêt des industriels s’accroît car il devient possible de résoudre
des problèmes industriels P-SPACE-complets (vérification de circuits digitaux, processeurs, vérification de logiciels). Intérêt similaire pour les techniques des réseaux de contraintes (CSP/CP) pour les
problèmes d’organisation dans le temps et l’espace (ordonnancement, affectation complexe). Les industriels développent leurs outils, embauchent les chercheurs du domaine (eg. Laurent Perron,
Google).
Les conférences sont soutenues par de grands groupes (Google, Microsoft, Intel, Cadence, IBM, Siemens,…) et des startups. Les chercheurs de l’IA mobilisent ces algorithmes pour les appliquer à des
problèmes difficiles de l’IA: planification automatique (SAT-Plan),``Data mining'' (Luc de Raedt).
2000+ : Ces techniques sont étendues pour résoudre des problèmes d’optimisation (critère numérique)
combinant contraintes, coûts, préférences, modèles graphiques discrets stochastiques (réseaux
Bayésiens, champs de Markov) permettant de raisonner sur la base d’un modèle ``appris'' par apprentissage automatique. Il devient possible de résoudre exactement certaines instances avec 2^{1 000
000} configurations. Depuis 2010, les outils exacts ``anytime'' finissent premier de compétitions internationales d’inférence probabiliste (UAI 2010, 2012, 2014). Ces algorithmes commencent à être mobilisés pour résoudre d’autres problèmes en IA (apprentissage par renforcement, NLP, conception musicale,…) et au delà (bioinformatique, développement durable. . . ). Dr Fill, entièrement écrit par M.
Ginsberg, finit successivement 131e (2012), 92e (2013), 64e (2014), 41e (2016) de l’American
CrossWorld Puzzle Tournament (deep learning free).
2012+: après les modèles graphiques stochastiques, introduction de contraintes globales ``Neuron'',
``Decision Tree'' et ``Random Forest'' pour élargir la gamme des modèles appris utilisables pour la
construction de décisions optimisées (M. Milano/M. Lombardi/Google).
2014-: Moshe Vardi, chercheur américain en informatique théorique, président de l’Association for
Computer machinery, annonce qu’il est temps de se lancer dans la résolution de problèmes au delà de
NP, en particulier les problèmes de comptage (#P-complets), au cœur du raisonnement probabiliste.
Les premiers algorithmes de calcul de fonction de partition avec garanties de type PAC (Probably
Approximately Correct), non asymptotiques, basées sur des outils SAT apparaissent. D’autres algorithmes ``anytime'' apparaissent.
Planification et recherche heuristique
Contexte historique
Les méta-heuristiques sont des algorithmes d’optimisation basés sur une randomisation de la recherche, alternant des étapes d’exploration de l’espace de recherche et des étapes d’exploitation des
meilleurs résultats passés, supervisées par une sélection des candidats-solutions elle aussi randomisée.
Certaines instances industrielles avec plus d’un million de variables booléennes sont résolues. Sur les
instances aléatoires, les algorithmes heuristiques dominent (Survey Propagation). Sur les problèmes
réels (industriels, jeux, scientifiques), les méthodes exactes, s’appuyant sur le ``Clause Learning'' dominent. Comme pour le “Deep Learning”, ce succès reste mystérieux. Des progrès similaires sont
obtenus dans le domaine des modèles graphiques déterministes (réseaux de contraintes, problème
CSP), en particulier via l’introduction des``contraintes globales'' et l’exploitation explicite de la structure des problèmes. Les jeux NP-complets usuels (Sudoku, Nonogrammes, Candy Crush. . . ) sont
trivialement résolus par ces outils. Les Sudoku du journal “Le Monde” sont synthétisés par un exchercheur du domaine (Y. Georget).
2000- : ces progrès se répandent au travers de l’introduction de “langages” s’appuyant sur ces progrès
fondamentaux dans les outils de résolution associés: ASP (Answer Set Programming), SMT (SAT
Modulo Theory), à côté de CP. L’intérêt des industriels s’accroît car il devient possible de résoudre
des problèmes industriels P-SPACE-complets (vérification de circuits digitaux, processeurs, vérification de logiciels). Intérêt similaire pour les techniques des réseaux de contraintes (CSP/CP) pour les
problèmes d’organisation dans le temps et l’espace (ordonnancement, affectation complexe). Les industriels développent leurs outils, embauchent les chercheurs du domaine (eg. Laurent Perron,
Google).
Les conférences sont soutenues par de grands groupes (Google, Microsoft, Intel, Cadence, IBM, Siemens,…) et des startups. Les chercheurs de l’IA mobilisent ces algorithmes pour les appliquer à des
problèmes difficiles de l’IA: planification automatique (SAT-Plan),``Data mining'' (Luc de Raedt).
2000+ : Ces techniques sont étendues pour résoudre des problèmes d’optimisation (critère numérique)
combinant contraintes, coûts, préférences, modèles graphiques discrets stochastiques (réseaux
Bayésiens, champs de Markov) permettant de raisonner sur la base d’un modèle ``appris'' par apprentissage automatique. Il devient possible de résoudre exactement certaines instances avec 2^{1 000
000} configurations. Depuis 2010, les outils exacts ``anytime'' finissent premier de compétitions internationales d’inférence probabiliste (UAI 2010, 2012, 2014). Ces algorithmes commencent à être mobilisés pour résoudre d’autres problèmes en IA (apprentissage par renforcement, NLP, conception musicale,…) et au delà (bioinformatique, développement durable. . . ). Dr Fill, entièrement écrit par M.
Ginsberg, finit successivement 131e (2012), 92e (2013), 64e (2014), 41e (2016) de l’American
CrossWorld Puzzle Tournament (deep learning free).
2012+: après les modèles graphiques stochastiques, introduction de contraintes globales ``Neuron'',
``Decision Tree'' et ``Random Forest'' pour élargir la gamme des modèles appris utilisables pour la
construction de décisions optimisées (M. Milano/M. Lombardi/Google).
2014-: Moshe Vardi, chercheur américain en informatique théorique, président de l’Association for
Computer machinery, annonce qu’il est temps de se lancer dans la résolution de problèmes au delà de
NP, en particulier les problèmes de comptage (#P-complets), au cœur du raisonnement probabiliste.
Les premiers algorithmes de calcul de fonction de partition avec garanties de type PAC (Probably
Approximately Correct), non asymptotiques, basées sur des outils SAT apparaissent. D’autres algorithmes ``anytime'' apparaissent.
Planification et recherche heuristique
Contexte historique
Les méta-heuristiques sont des algorithmes d’optimisation basés sur une randomisation de la recherche, alternant des étapes d’exploration de l’espace de recherche et des étapes d’exploitation des
meilleurs résultats passés, supervisées par une sélection des candidats-solutions elle aussi randomisée.