{"id":47,"date":"2021-11-12T17:28:59","date_gmt":"2021-11-12T16:28:59","guid":{"rendered":"https:\/\/leria.univ-angers.fr\/?page_id=47"},"modified":"2024-04-15T09:57:58","modified_gmt":"2024-04-15T07:57:58","slug":"rasionnement-dans-lincertain-et-contraintes","status":"publish","type":"page","link":"https:\/\/leria.univ-angers.fr\/?page_id=47","title":{"rendered":"Raisonnement dans l&#8217;Incertain et Contraintes"},"content":{"rendered":"\n<h3 class=\"wp-block-heading\">Membres du th\u00e8me<\/h3>\n\n\n\n<figure class=\"wp-block-table is-style-stripes\" style=\"font-size:80%\">\n    <table>\n        <thead>\n            <tr>\n                <th>NOM Pr\u00e9nom<\/th>\n                <th>Statut<\/th>\n            <\/tr>\n        <\/thead>\n        <tbody>\n            <tr>\n                <td>BARICHARD Vincent<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>BEHUET Corentin<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>DEGUIEZ LODEIRO Martin<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>DEVRED Caroline<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>GARCIA Laurent<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>GARREAU Bryan<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>LARDEUX Fr\u00e9d\u00e9ric<\/td>\n                <td>Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>LEFEVRE Claire<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>LEGEAY Marc<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences<\/td>\n            <\/tr>\n            <tr>\n                <td>LESAINT David<\/td>\n                <td>Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>MONFROY \u00c9ric<\/td>\n                <td>Professeur<\/td>\n            <\/tr>\n            <tr>\n                <td>SEKAR Suruthy<\/td>\n                <td>Doctorant<\/td>\n            <\/tr>\n            <tr>\n                <td>STEPHAN Igor<\/td>\n                <td>Ma\u00eetre de conf\u00e9rences\/HDR<\/td>\n            <\/tr>\n            <tr>\n                <td>VASCONCELLOS Claudia<\/td>\n                <td>Enseignant-chercheur contractuel<\/td>\n            <\/tr>\n        <\/tbody>\n    <\/table>\n<\/figure>\n\n\n\n<p>Le th\u00e8me RIC f\u00e9d\u00e8re les travaux du laboratoire autour du raisonnement non-monotone et des approches d\u00e9claratives pour la r\u00e9solution de probl\u00e8mes combinatoires (<a href=\"https:\/\/leria.univ-angers.fr\/wp-content\/uploads\/2021\/11\/RIC.pdf\" target=\"_blank\" rel=\"noreferrer noopener\">livret d\u00e9taill\u00e9<\/a>). L\u2019accent est mis sur la repr\u00e9sentation des connaissances et les efforts se portent sur la conception de langages de mod\u00e9lisation et le d\u00e9veloppement de techniques de transformation ou d\u2019encodage de mod\u00e8les visant \u00e0 concilier flexibilit\u00e9 et efficacit\u00e9. Les travaux, qui abordent les fondements th\u00e9oriques de ces outils mais aussi leur implantation et leurs applications, s\u2019appuient sur des paradigmes de mod\u00e9lisation haut-niveau tels la programmation par ensembles-r\u00e9ponses (ASP) et la programmation par contraintes (PPC, CHR) ainsi que sur des formalismes plus \u00e9l\u00e9mentaires tels CSP et SAT :<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li>Extension des cadres ASP et CHR : int\u00e9gration de variables existentielles en ASP pour le raisonnement ontologique, gestion de pr\u00e9f\u00e9rences en ASP possibilistes pour la r\u00e9vision de croyances, quantification de contraintes en CHR pour les probl\u00e8mes \u00e0 horizon non born\u00e9.<\/li>\n\n\n\n<li>Mod\u00e9lisation, transformation et encodage : CSP ensemblistes et encodages CSP\/SAT, d\u00e9composition de probl\u00e8me fond\u00e9e sur l\u2019interpr\u00e9tation abstraite et la PPC, PPC pour la transformation de mod\u00e8les en ing\u00e9nierie des mod\u00e8les, PPC pour la recherche de motifs en fouille de donn\u00e9es.<\/li>\n<\/ul>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"programmation-par-ensembles-r\u00e9ponses\">Programmation par ensembles-r\u00e9ponses<\/h2>\n\n\n\n<p>L\u2019ASP (Answer Set Programming) est un langage d\u00e9claratif d\u00e9velopp\u00e9 afin de traiter des connaissances en intelligence artificielle, lorsque les informations sont incompl\u00e8tes, ou pour r\u00e9soudre des probl\u00e8mes combinatoires. Nos travaux portent sur diverses extensions du cadre de l\u2019ASP et allient th\u00e9orie et pratique.<\/p>\n\n\n\n<p>Nous d\u00e9veloppons depuis plusieurs ann\u00e9es un solveur ASP, ASPeRiX, bas\u00e9 sur une approche originale guid\u00e9e par les r\u00e8gles et ne n\u00e9cessitant pas d\u2019instanciation pr\u00e9alable du programme. Nos travaux r\u00e9cents montrent que l\u2019algorithme sous-jacent \u00e0 ASPeRiX peut s\u2019exprimer de mani\u00e8re efficace et extensible en CHR. Nous travaillons \u00e0 une mise \u00e0 jour majeure d\u2019ASPeRiX bas\u00e9e sur le langage CHR (et sa version CHR++ d\u00e9velopp\u00e9e au sein du laboratoire) qui permettra de remplacer le backtrack chronologique d\u2019ASPeRiX par un backtrack intelligent et, d\u2019un autre c\u00f4t\u00e9, pourra int\u00e9grer ais\u00e9ment des contraintes d\u00e9finies par l\u2019utilisateur ainsi que les extensions modernes d\u2019ASP.<\/p>\n\n\n\n<p>Par ailleurs, dans le cadre de l\u2019\u00e9tude de la fusion multi-sources et de l\u2019interrogation d\u2019informations issues du web, g\u00e9n\u00e9ralement exprim\u00e9es en logique de description (projet ANR ASPIQ), nous nous sommes par exemple int\u00e9ress\u00e9s \u00e0 l\u2019int\u00e9gration dans l\u2019ASP des variables existentielles, inh\u00e9rentes aux ontologies exprim\u00e9es en logique de description, ainsi qu\u2019\u00e0 l\u2019interrogation de ces ontologies en ASP.<\/p>\n\n\n\n<p>D\u2019autre part, nous nous int\u00e9ressons \u00e0 la r\u00e9vision de croyances lorsque les connaissances sont exprim\u00e9es par un programme ASP. Cette probl\u00e9matique \u00e9tant peu \u00e9tudi\u00e9e, nous proposons une s\u00e9mantique, des postulats de r\u00e9vision et une \u00e9tude de complexit\u00e9 de la r\u00e9vision en ASP. Enfin, l\u2019int\u00e9gration de pr\u00e9f\u00e9rences entre connaissances a amen\u00e9 \u00e0 l\u2019\u00e9tude de la r\u00e9vision en ASP possibiliste. Nous \u00e9tudions de nouveaux modes de r\u00e9vision tirant profit de la structure des r\u00e8gles ASP (r\u00e9vision par ajout, par exemple) et nous essayons de d\u00e9terminer s\u2019il est possible d\u2019\u00e9laborer une caract\u00e9risation logique de l\u2019ASP possibiliste en termes de logique d\u2019\u00e9quilibre ce qui pourrait donner un cadre pour l\u2019\u00e9tude de th\u00e9ories arbitraires dans l\u2019ASP possibiliste.<\/p>\n\n\n\n<p>Concernant l\u2019ASP, nous nous int\u00e9ressons plus g\u00e9n\u00e9ralement \u00e0 l\u2019explicabilit\u00e9 des r\u00e9sultats. Cette \u00e9tude est n\u00e9cessaire pour nos travaux sur le backjumping et pourra aussi \u00eatre utilis\u00e9e dans le cadre de l\u2019ASP possibiliste.<\/p>\n\n\n\n<p>Toujours pr\u00e9occup\u00e9s par la mise en pratique de l\u2019ASP sur des applications r\u00e9elles, nous sommes partie prenante du projet Potassco Solutions, initi\u00e9 par nos coll\u00e8gues de Potsdam, dont nous sommes les correspondants fran\u00e7ais.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"mod\u00e9lisation-par-contraintes-conversion-et-reformulation-de-mod\u00e8les\">Mod\u00e9lisation par contraintes, conversion et reformulation de mod\u00e8les<\/h2>\n\n\n\n<p>\u00c0 l\u2019origine, la programmation par contraintes comportait deux volets primordiaux : le langage pour mod\u00e9liser les probl\u00e8mes, et les solveurs pour r\u00e9soudre ces derniers. Pendant de nombreuses ann\u00e9es, les efforts se sont port\u00e9s sur les solveurs afin d\u2019am\u00e9liorer la r\u00e9solution. Cependant, il y a quelques ann\u00e9es, la partie langage est revenue sur l\u2019avant de la sc\u00e8ne, car la mod\u00e9lisation permet d\u2019ouvrir les contraintes \u00e0 des utilisateurs non experts, mais \u00e9galement d\u2019obtenir des mod\u00e8les possiblement plus robustes et r\u00e9solus beaucoup plus efficacement. Diff\u00e9rents aspects peuvent \u00eatre pris en compte tels que la reformulation de mod\u00e8le, la conversion de mod\u00e8le ou le langage de mod\u00e9lisation. Nous travaillons principalement sur les voies suivantes.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"contraintes-ensemblistes\">Contraintes ensemblistes<\/h3>\n\n\n\n<p>Par rapport aux mod\u00e9lisations bas\u00e9es sur des matrices ou des entiers, les ensembles sont pratiques car ils r\u00e9duisent naturellement le nombre de sym\u00e9tries. De plus, il est bien connu que de nombreux probl\u00e8mes peuvent \u00eatre facilement mod\u00e9lis\u00e9s avec des contraintes ensemblistes. Plusieurs solveurs de contraintes sp\u00e9cialis\u00e9s pour les contraintes ensemblistes existent d\u00e9j\u00e0. Nous nous int\u00e9ressons \u00e0 divers aspects des contraintes ensemblistes : les mod\u00e8les CSP avec contraintes ensemblistes, la r\u00e9duction des variables \u00e0 domaine fini et des variables ensemblistes ainsi qu\u2019\u00e0 l\u2019encodage des contraintes ensemblistes en SAT.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"encodage-cspsat\">Encodage CSP\/SAT<\/h3>\n\n\n\n<p>Nous travaillons sur les encodages CSP vers SAT afin de mieux comprendre les facteurs cl\u00e9s qui d\u00e9terminent leurs caract\u00e9ristiques ainsi que leurs effets sur la r\u00e9solution. Dans un premier temps, nous analysons l\u2019impact de la provenance des variables du mod\u00e8le SAT sur l\u2019heuristique de branchement les solveurs SAT. En effet, certaines variables du mod\u00e8le SAT correspondent directement \u00e0 des variables du mod\u00e8le CSP alors que d\u2019autres, dites auxiliaires, sont ajout\u00e9es lors de l\u2019encodage des contraintes du mod\u00e8le CSP. Nous travaillons \u00e9galement sur l\u2019encodage de m\u00e9canismes de propagation propres aux solveurs CSP dans le mod\u00e8le SAT. Afin d\u2019encoder au mieux le maximum d\u2019informations provenant du m\u00e9canisme de propagation CSP sans pour autant augmenter de mani\u00e8re d\u00e9mesur\u00e9e la taille de l\u2019instance SAT, nous proposons de nouveaux encodages SAT comme par exemple l\u2019Abacus encoding.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"probl\u00e8mes-quantifi\u00e9s-sous-contraintes\">Probl\u00e8mes quantifi\u00e9s sous contraintes<\/h3>\n\n\n\n<p>Il existe plusieurs formalismes et langages de mod\u00e9lisation issus de la programmation par contraintes comme CSP et CHR (Constraint Handling Rules). Les CSP ont donn\u00e9 lieu \u00e0 plusieurs extensions dont les QCSP (Quanfitied Constraint Satisfaction Problem) qui adressent les probl\u00e8mes quantifi\u00e9s sous contraintes. N\u00e9anmoins les formalismes quantifi\u00e9s de la litt\u00e9rature sont \u00e0 horizon born\u00e9 ce qui rend difficile voire impossible la mod\u00e9lisation de certains probl\u00e8mes quantifi\u00e9s qui n\u00e9cessite une repr\u00e9sentation en intention et non en extension de la combinatoire. C\u2019est pourquoi nous proposons une approche \u00e9tendant CHR pour int\u00e9grer la quantification. Ceci nous permet de mod\u00e9liser des probl\u00e8mes \u00e0 horizon non born\u00e9.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"constraint-handling-rules\"><strong>C<\/strong>onstraint <strong>H<\/strong>andling <strong>R<\/strong>ules<\/h3>\n\n\n\n<p>La programmation par contraintes tire ses racines de la programmation logique et peut \u00eatre vue comme une forme de programmation logique qui incorpore des contraintes. Cette variante de la programmation logique, appel\u00e9e commun\u00e9ment programmation logique par contraintes, a \u00e9t\u00e9 impl\u00e9ment\u00e9e dans diff\u00e9rents syst\u00e8mes (<code>Prolog III<\/code>, <code>CLP (R)<\/code> et <code>CHIP<\/code>). Ces syst\u00e8mes sont aujourd\u2019hui supplant\u00e9s par les solveurs PPC plus efficaces. Toutefois, lorsque l\u2019on souhaite innover, il est n\u00e9cessaire de sortir du carcan d\u2019un solveur PPC, t\u00e2che difficile avec les solveurs actuels. C\u2019est pourquoi depuis quelques ann\u00e9es nous cherchons un langage de mod\u00e9lisation de contraintes d\u2019un autre niveau d\u2019abstraction. Notre choix s\u2019est port\u00e9 sur CHR (Constraint Handling Rules). CHR est un langage de mod\u00e9lisation et de programmation de haut niveau bas\u00e9 sur des r\u00e8gles de propagation descriptives et applicables. Les axiomes du langage sont de plus bas niveau que les contraintes habituelles d\u2019un solveur PPC, mais elles permettent de red\u00e9finir facilement et rapidement chacune d\u2019elles. CHR est impl\u00e9ment\u00e9e comme extension d\u2019un langage h\u00f4te et est disponible pour <code>Prolog<\/code>, <code>Haskell<\/code>, <code>Java<\/code> \u2026C\u2019est pourquoi nous d\u00e9veloppons <code>CHR++<\/code><a href=\"#fn1\"><sup>1<\/sup><\/a>, notre propre impl\u00e9mentation de CHR au dessus de <code>C++<\/code>. <code>CHR++<\/code> impl\u00e9mente un m\u00e9canisme d\u2019exploration arborescent avec retour arri\u00e8re permettant la recherche d\u2019une solution comme un solveur PPC. Il allie \u00e0 la fois la puissance de mod\u00e9lisation et la simplicit\u00e9 d\u2019utilisation d\u2019un solveur PPC, la souplesse d\u2019un langage de programmation logique et la performance d\u2019un langage imp\u00e9ratif. Nous avons utilis\u00e9 la logique lin\u00e9aire pour formaliser le syst\u00e8me, et travaillons \u00e0 \u00e9tendre le langage par l\u2019ajout de concepts tels que : la disjonction hi\u00e9rarchique, les contraintes <em>bang<\/em> ou les contraintes permanentes. Nos travaux sont ensuite appliqu\u00e9s \u00e0 divers domaines et applications comme les QCSP, l\u2019ASP, la transformation de mod\u00e8les et la conception d\u2019emplois du temps.<br><\/p>\n\n\n\n<h3 class=\"wp-block-heading\" id=\"mod\u00e9lisation-et-r\u00e9solution-hybrides\">Mod\u00e9lisation et r\u00e9solution hybrides<\/h3>\n\n\n\n<p>Actuellement, les travaux li\u00e9s \u00e0 la fronti\u00e8re entre la programmation logique non-monotone (et de son langage phare, ASP) et la r\u00e9solution de probl\u00e8mes combinatoires contraints sur les domaines finis ne consid\u00e8re qu\u2019un unique point de vue consistant \u00e0 faire coop\u00e9rer \u00e0 haut niveau un solveur ASP et un solveur de contraintes. Un axe que nous explorons est d\u2019appliquer des m\u00e9canismes de la propagation de contraintes \u00e0 l\u2019ASP.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\" id=\"applications-en-cours\">Applications en cours<\/h2>\n\n\n\n<ul class=\"wp-block-list\">\n<li><em>L\u2019ing\u00e9nierie dirig\u00e9e par les mod\u00e8les<\/em> consiste \u00e0 abstraire les diff\u00e9rentes parties d\u2019un syst\u00e8me sous la forme d\u2019un ensemble de mod\u00e8les, chaque mod\u00e8le adoptant un niveau d\u2019abstraction diff\u00e9rent et adapt\u00e9 aux besoins de la personne les utilisant. Nous avons d\u00e9fini une approche permettant d\u2019int\u00e9grer des contraintes dans des transformations de mod\u00e8les, pour sp\u00e9cifier certaines contraintes sp\u00e9cifiques au domaine d\u2019application (par exemple, la planification d\u2019emploi du temps).<\/li>\n\n\n\n<li><em>Les emplois du temps universitaires (EDT)<\/em> se construisent g\u00e9n\u00e9ralement par optimisation combinatoire et des travaux r\u00e9cents se sont int\u00e9ress\u00e9s \u00e0 la r\u00e9vision d\u2019EDT pour mieux r\u00e9pondre au caract\u00e8re dynamique du probl\u00e8me et aux exigences des diff\u00e9rents acteurs en termes de contr\u00f4le et d\u2019explicabilit\u00e9 du calcul. Notre approche vise \u00e0 \u00e9tablir un cadre formel pour la r\u00e9vision d\u2019EDT ciblant particuli\u00e8rement le syst\u00e8me universitaire fran\u00e7ais et qui se fonde sur la programmation par contraintes et possibles hybridations afin d\u2019int\u00e9grer op\u00e9rations et strat\u00e9gies de r\u00e9paration.<\/li>\n\n\n\n<li>L\u2019<em>Inf\u00e9rence grammaticale<\/em> consiste \u00e0 apprendre automatiquement une grammaire formelle (g\u00e9n\u00e9ralement sous forme de r\u00e8gles de productions ou d\u2019un automate) \u00e0 partir d\u2019un ensemble d\u2019observations. Nous nous int\u00e9ressons actuellement \u00e0 la mod\u00e9lisation SAT et INLP d\u2019automates finis non d\u00e9terministes devant accepter un ensemble de mots donn\u00e9s et rejeter un ensemble de mots n\u2019appartenant pas au langage.<\/li>\n<\/ul>\n\n\n\n<hr class=\"wp-block-separator has-css-opacity\"\/>\n\n\n\n<ol class=\"wp-block-list\">\n<li><a href=\"http:\/\/chrpp.barichard.com\/\">http:\/\/chrpp.barichard.com\/<\/a><a href=\"#fnref1\">\u21a9\ufe0e<\/a><\/li>\n<\/ol>\n","protected":false},"excerpt":{"rendered":"<p>Membres du th\u00e8me NOM Pr\u00e9nom Statut BARICHARD Vincent Ma\u00eetre de conf\u00e9rences BEHUET Corentin Doctorant DEGUIEZ LODEIRO Martin Ma\u00eetre de conf\u00e9rences DEVRED Caroline Ma\u00eetre de conf\u00e9rences GARCIA Laurent Ma\u00eetre de conf\u00e9rences GARREAU Bryan Doctorant LARDEUX Fr\u00e9d\u00e9ric Professeur LEFEVRE Claire Ma\u00eetre de &hellip; <a href=\"https:\/\/leria.univ-angers.fr\/?page_id=47\">Continuer la lecture <span class=\"meta-nav\">&rarr;<\/span><\/a><\/p>\n","protected":false},"author":5,"featured_media":0,"parent":38,"menu_order":1,"comment_status":"closed","ping_status":"closed","template":"","meta":{"footnotes":""},"class_list":["post-47","page","type-page","status-publish","hentry"],"_links":{"self":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/47","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/users\/5"}],"replies":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=47"}],"version-history":[{"count":9,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/47\/revisions"}],"predecessor-version":[{"id":394,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/47\/revisions\/394"}],"up":[{"embeddable":true,"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=\/wp\/v2\/pages\/38"}],"wp:attachment":[{"href":"https:\/\/leria.univ-angers.fr\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=47"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}