  News | GDT | Docs | Devpt |
DÉcision, Systèmes Intelligents et Recherche opérationnelle
Responsable : Patrice PernyLes activités du département DÉcision, Systèmes Intelligents et Recherche opérationnelle (DESIR) concernent l'Intelligence Artificielle et la Recherche Opérationnelle ; elles se concentrent sur les problèmes de décision, d'optimisation et les systèmes adaptatifs.
Les travaux menés couvrent un large spectre, incluant des aspects théoriques
(modèles formels, analyses axiomatiques, études de complexité), le développement
d'algorithmes efficaces (exacts ou approchés) pour la résolution
de problèmes complexes, la conception de systèmes intelligents (agents adaptatifs,
systèmes multi-agents, systèmes d'aide à la décision, d'aide à la formation),
et leur mise en oeuvre au sein d'applications industrielles.
Le département DÉSIR est organisé en 5 équipes :
L'axe Optimisation Combinatoire concerne le développement
d'algorithmes exacts ou approchés pour la résolution de
problèmes combinatoires et les études de performance et de
complexité associées.
L'équipe est principalement
specialisée sur la résolution de certaines classes de
problèmes d'ordonnancement (problèmes avec temps de communication,
problèmes à une machine, problèmes d'atelier,
ordonnancement juste-à-temps) et sur la résolution de
problèmes de satisfiabilité (SAT).
Les principaux axes d'intérêt de l'équipe aide à la décision concernent les quatre domaines suivants :
- le développement de modèles formels sophistiqués et d'algorithmes pour la décision dans l'incertain,
- la décision multicritère,
- la décision collective,
- la décision basée sur le contexte.
L'équipe SMA s'intéresse à la conception de systèmes intelligents caractérisés principalement par :
- L'intelligence des agents : les agents du SMA sont autonomes, dotés de capacités cognitives (décision, raisonnement, apprentissage,) et d'un comportement réflexif leur permettant d'agir, d'observer leurs actions et d'en changer le cours.
- L'interactivité des agents : les agents sont situés dans un environnement partagé et ouverts vers des utilisateurs ou d'autres systèmes.
- La complexité du système : en conséquence des deux propriétés précédentes, les agents sont hétérogènes, multiples, voire très nombreux.
| [ travaux ] - Décision |
Travaux récents de l'équipe « Aide à la Décision »
L'équipe aide à la décision travaille sur le développement de modèles formels sophistiqués et d'algorithmes pour la Décision dans l'incertain, la décision multicritère, la décision collective et la décision basée sur le contexte.
En complément des travaux
théoriques, nous avons développé ces deux dernières
années des systèmes d'aide à la décision en contexte
industriel. Les résultats obtenus concernent les axes suivants :
1. Modélisation et agrégation des préférences, analyses axiomatiques
Nous développons et étudions des modèles ordinaux de
décision (i.e. n'utilisant pas de représentation quantitative des
préférences et des croyances) pour la prise de décision
dans un contexte d'information pauvre.
Les principaux résultats obtenus, en décision multicritère
comme en décision dans l'incertain, concernent :
- l'introduction de nouvelles procédures d'agrégation ordinales et
- leur caractérisation axiomatique (règles de concordance, intégrales de Sugeno).
Un second axe concerne les modèles quantitatifs et leur étude axiomatique. Dans cette direction, les principaux travaux concernent :
- l'utilisation de l'intégrale de Choquet en décision multicritère,
- l'obtention de résultats théoriques sur la décomposition additive des utilités multiattributs,
- enfin la modélisation des choix en univers partiellement analysable.
Enfin, diverses applications des modèles décisionnels et des
procédures d'agrégation multicritères ont été
explorées et implantées dans un contexte industriel, notamment
dans le domaine de la décision collaborative, de la fusion d'information,
de la reconnaissance des formes, de la classification et du diagnostic.
2. Recherche heuristique et algorithmes basés sur les préférences
En décision dans l'incertain, nous cherchons les moyens de contourner les problèmes de cohérence que pose l'utilisation d'un modèle non EU dans les problèmes de décision dynamique. Pour cela, nous avons proposé une approche heuristique pour l'obtention de stratégies nondominées dans les arbres de décision.
Indépendamment, nous avons étudié les problèmes liés à la prise en compte de structures de préférences partielles pour la résolution de problème en IA et en RO. Pour traiter de tels problèmes, nous avons généralisé au cas de préférences partielles non transitives l'algorithme A* et les algorithmes de Kruskal, Prim et Bellman dans les graphes.
Nous travaillons également sur la recherche de
solutions robustes dans des problèmes combinatoires où les coûts
dépendent de divers scénarios. Les travaux entrepris dans cette
direction devraient se poursuivre afin d'étudier la résolution
d'autres problèmes combinatoires en présence de
préférences nonclassiques.
3. Modèles graphiques pour le raisonnement et la décision
Les modèles graphiques sont utilisés pour représenter une masse d'information importante utiles à un raisonnement ou une décision (probabilités, utilités, préférences) de manière compacte en mémoire dans le but de les restituer de manière efficace (à moindre coût) dans un processus décisionnel. On peut mentionner :
- les réseaux Bayesiens utilisés pour la représentation d'une loi de probabilité jointe,
- les diagrammes d'influence utilisés pour représenter des problèmes de décision dans l'incertain et
- les réseaux de préférences (RP) pour représenter une préférence sur un ensemble combinatoire.
Les travaux que nous
menons en réseaux bayésiens (RB) ont pour but d'unifier l'ensemble
des techniques de propagation d'information dans les RB, de manière
à tirer parti des avantages de chacune des méthodes. En
parallèle, nous entamons des recherches sur l'apprentissage de la
structure des réseaux ainsi que sur des extensions des dites
structures. Pour lier choix et les RB, nous commençons également à
travailler sur les diagrammes d'influence. Concernant les réseaux de
préférences, nous étudions les capacités
descriptives de CP-nets et UCP-nets afin de proposer de nouveaux modèles
graphiques pour la représentation des préférences.
4. Décision basée sur le contexte
Les études menées dans cette direction portent sur l'étude des systèmes d'assistance intelligents en contexte (SAIC) à partir de plusieurs applications (e.g. projet SART). Les résultats obtenus ont reçu une reconnaissance nationale et contribué à l'émergence d'une communauté internationale rassemblée sur le thème du contexte.
Dans l'étude des SAIC, la
modélisation du contexte a conduit à une représentation du
raisonnement dans le formalisme des graphes contextuels. Les recherches sur les
SAIC et le contexte vont être poursuivies dans de nouvelles applications
pour la RATP (régulation temps réel d'une ligne de RER en
situation incidentielle), pour HewlettPackard (réalisation d'une
contextaware application) et pour Cegelec (projet emaintenance) avec le reste du
thème SYSDEF. Concrètement, les recherches porteront sur les
graphes contextuels (tant sur le plan théorique que logiciel), la
modélisation du contexte et la décision à partir de cas.
5. Explication dans les arbres de décision
Les travaux portent sur la qualification des résultats et l'étude de sensibilité dans les arbres de décision. Les objectifs pour les prochaines années sont d'exploiter le paradigme géométrique pour l'aide à la décision et l'aide à la négociation. On s'intéressera à la qualification des résultats d'un système discriminant (sensibilité, définition de solutions prototypiques par les propriétés de la surface de décision), aux interactions avec l'utilisateur (par l'intermédiaire de la métrique) et à l'analyse des résultats de simulations (sensibilité, stabilité morphologique).
| [ travaux ] - MOCAH |
Les recherches de l'équipe MOCAH portent sur les Environnements Informatiques pour l'Apprentissage Humain (EIAH).
Les principales problématiques abordées sont :
- la conception d’environnements d'apprentissage par la résolution de problèmes
- la qualification des ressources pédagogiques par des métadonnées
- l'aide à la recherche de ressources selon une approche qui articule métadonnées et ontologies
- le développement d’outils auteurs dédiés à la conception de scénarios pédagogiques ou de banques d’exercices respectant les standards internationaux
- le diagnostic des activités de l'apprenant en situation de résolution de problèmes, dans le cadre de logiciels de simulation et d'environnements dédiés
- la modélisation cognitive de l'apprenant à partir de diagnostics.
Plusieurs outils logiciels génériques, développés ou en cours de développement, concernent :
- le diagnostic des activités de l'apprenant basé sur les réseaux bayésiens (BSMod)
- la génération de patrons d'exercices basés sur la spécification IMS-QTI que nous avons étendue (projet C3)
- un environnement d'édition de qualification et de recherche de ressources éducatives (projet Acedu).
Nos travaux de recherche se sont également traduits par plusieurs applications spécifiques, pour la formation initiale ou la
formation professionnelle.
Projets :
- Combien ?
- Diapason
- Plastur
- Strex
- Spep
- C3 - C cube
Consulter la page Projets pour plus d'informations sur ces applications.
L'équipe MOCAH est d'autre part impliquée dans des groupes de travail de l'AFNOR (Commission de Normalisation 36, "Technologies de l'information pour l'éducation, la formation et l'apprentissage") concernant la standardisation et l'indexation des ressources pédagogiques, et a participé activement à l’'élaboration du profil d’application LOM.fr, standard français pour la description des ressources pédagogiques.
L'équipe est une composante de l'équipe projet AIDA (Approches Interdisciplinaires pour les Dispositifs d'Apprentissage),
Programme Pluri Formation (PPF) financé par le Ministère de la Recherche.
Au niveau national, l'équipe participe depuis de nombreuses années à l'ATIEF et au groupe EIAH du GDR-I3.
Au niveau international, l'équipe participe au réseau d'excellence européen Kaleidoscope.
| [ travaux ] - RO |
Travaux de l'équipe « Combinatoire »
Les recherches de l'équipe portent essentiellement sur la résolution de problèmes fondamentaux ouverts, de problèmes nouveaux ou émergents ainsi que la résolution de problèmes "challenges" qui intéressent des dizaines d'équipes dans le monde.
- Les principales applications sont liées à l'ordonnancement juste à temps. En effet, la prochaine génération de logiciels d'ordonnancement (horizon de 5 à 10 ans) intégrera des critères d'optimisation irréguliers. L'équipe produit de nouveaux résultats théoriques (preuves d'algorithmes et de complexité) et développe et teste ces algorithmes sur jeux de données.
- Les principaux résultats obtenus concernent les problèmes avec temps de communication (élaboration d'un algorithme polynomial exact pour le cas particulier d'arborescences UET-UCT et développement de méthodes tabou originales pour la résolution du problème à processeurs hétérogènes), les problèmes avec délais de communication généralisés (NP-complétude d'un problème ouvert pour un graphe de précédence biparti, polynomialité de problèmes avec chaînes de précédence), les problèmes d'atelier (étude de deux sous problèmes polynomiaux sur une machine et nouvel algorithme de branch and bound qui a permis de résoudre des instances jusqu'alors ouvertes) et l'ordonnancement juste à temps (preuves de cas polynomiaux : séquence de tâches sur une machine, ordonnancement de projet sans contraintes de ressources, ordonnancement cyclique, résolution exacte du problème général à une machine (NP-complet) par un algorithme de branch and bound, le plus efficace existant à ce jour).
- L'équipe développe actuellement ses travaux sur les algorithmes exacts ou d'approximation avec garantie de performance, notamment en collaboration avec des chercheurs étrangers.
- Des travaux sont également en cours sur les problèmes liés à la prise en compte de critères de coûts liés à la qualité de service pour le dimensionnement de réseau de télécommunications ainsi que des problèmes de planification de production.
- Un nouvel axe de recherche mettant à profit certains outils de l'optimisation combinatoire (complexité, approximation) à la résolution de problèmes de décision (projet PREFCOMB).
- Une action Jeune Chercheur du CNRS est actuellement en cours. Elle porte sur l'optimisation du cache pour un simulateur de circuits.
| [ travaux ] - SMA |
