Direction des Relations Internationales (DRI)
Programme
INRIA "Equipes Associées"
(Demande de prolongation)
| EQUIPE ASSOCIEE |
PORGY |
|
sélection
|
2009 |
| Equipe-Projet INRIA : GRAVITE |
Organisme étranger partenaire : King's College
London |
| Centre de recherche INRIA : Bordeaux Sud-Ouest Thème INRIA : Systèmes cognitifs |
Pays : Grande-Bretagne (UK) |
|
Coordinateur français
|
Coordinateur étranger
|
||
| Nom, prénom | Mélançon Guy | Fernández Maribel |
|
| Grade/statut | Professeur des universités | Reader in Computer Science |
|
| Organisme d'appartenance (précisez le département et/ou le laboratoire) |
Université Bordeaux 1 | King's College London, Department of Computer Science |
|
Adresse postale |
|
London WC2R 2LS Angleterre |
|
| URL | http://www.labri.fr/perso/melancon
|
http://www.dcs.kcl.ac.uk/staff/maribel/
|
|
| Téléphone | +33 540008881 |
+44 2078482499 |
|
| Télécopie | +33 540006669 |
+44 442078482851 |
|
| Courriel | Guy.Melancon@inria.fr
|
Maribel.Fernandez@kcl.ac.uk
|
|
Titre de la thématique de collaboration (en français et en anglais) : PORGY – Interactive Analysis and Visualisation of Port Graph Rewriting Systems / Analyse visuelle interactive de systèmes de réécriture de graphes |
|
Descriptif (environ
10 lignes) :
L'objectif de PORGY est de concevoir une plate-forme visuelle et graphique complète de manipulation et d'exploitation de graphes dynamiques issus de systèmes de réécriture de graphes. Une telle plate-forme peut être vue comme un moyen de modéliser et d'étudier l'évolution de systèmes complexes tels que des réseaux biochimiques (modélisation et simulation des interactions entre les molécules), des systèmes de communication (par exemple simulation d'échanges de messages, simulation de pannes, ...), ou encore des modèles de calcul (la réécriture de graphes étant un formalisme équivalent, en pouvoir calculatoire, aux machines de Turing). Les systèmes de réécriture de graphes sont non seulement un outil de modélisation mais aussi un formalisme de calcul. Ainsi, la plate-forme visuelle et graphique que nous développons fournit en même temps un cadre de spécification et de programmation, puisque les spécifications écrites sous forme de règles de réecriture de graphes sont elles mêmes exécutables. D'un point de vue plus général,
la structure des graphes utilisée dans ces exemples peut être
représentée par un formalisme de graphe particulier : les
"portgraphes". Dans un portgraphe, les sommets possèdent des ports et
une arête ne peut relier les sommets que par l'intermédiaire des
ports. Un système peut alors être défini comme un
portgraphe P qui représente le modèle à étudier,
un ensemble de règles de réécriture qui décrit les évolutions de P
et une stratégie d'application de ces règles. Une règle peut être vue comme une
fonction f: A->B où A est un portgraphe isomorphe à un sous-graphe
de P et B est le portgraphe qui doit remplacer une instance de A dans
P. En utilisant la plate-forme Tulip (voir http://www.tulip-software.org) comme base de développement, nous souhaitons développer un environnement graphique et interactif pour :
|
|
Changements majeurs survenus concernant
l'Equipe Associée (modifications des objectifs scientifiques, des
chercheurs impliqués) |
| Chercheurs au coeur du projet |
|
| GRAVITE
et INRIA |
King's
College London |
| Guy Melançon (Pr) Bruno Pinaud (MCF depuis le 01/09/2008) Daniel Archambault (Post-doctorant GRAVITE) Chercheurs associés non membre de GRAVITE : Hélène Kirchner (DR INRIA) Oana Andrei (Post-doctorante) |
Maribel Fernandez (Reader in
Computer Science) Olivier Namet (Doctorant supervisé par Maribel Fernandez) |
| Chercheurs intervenus ponctuellement lors
des séminaires |
|
| Anatoli Degtyarev (senior
lecturer) Odinaldo Rodrigues (senior lecturer) Dov Gabbay (Augustus de Morgan Professor of Logic) |
|
| Etudiants en formation |
|
| Projet
pédagogique pour la formation d'étudiants (09/08 à 01/09) Florent Foucaud (étudiant Master 2 Bordeaux) Petru Valicov (étudiant Master 2 Bordeaux) Stage de fin de première année de Master (02/06/09 au 31/08/09) Damien Sabary (étudiant Master 1 Bordeaux) |
Matthew Walker (doctorant) Gabrielle Luciano (stagiaire, octobre 2009 - juillet 2010) |
Description de l'activité scientifique de l'équipe associée et des résultats obtenus : publications, communications, organisation de colloques, formation, soutenances de thèse, valorisation économique, sociale, industrielle, enregistrement de logiciels, dépôt de brevets ... (1 à 2 pages)
L'objectif général du projet PORGY, décrit dans le
document soumis en
2008, est de développer un environnement visuel pour la création, la
transformation et l'analyse de graphes dynamiques, et plus précisement
de
portgraphes qui évoluent par applications successives de règles de
réécriture.
Pour cela, nous avons décomposé le travail en plusieurs tâches, qui
devraient se dérouler sur trois ans. Le programme de la première année
inclut les points suivants (voir le formulaire soumis en 2008) :
Adoption de la notion de portgraphe. Une première étape a été de confirmer que, quelle que soit l'application utilisée, le modèle des portgraphes est une bonne représentation qui permet d'exprimer à la fois, et de façon uniforme, les règles de réécriture et les modèles sur lesquels sont appliqués les règles. Pour utiliser PORGY dans le cadre d'une application précise (réseaux d'interaction, modèles biologiques, réseaux autonomes,...), l'aspect esthétique des portgraphes peut être adapté au travers d'une interface particulière, mais la structure sous-jacente de graphe, de règle et de modèle à réécrire est commune à toutes ces applications.
Une première expérimentation.
Il fallait dans un premier temps comprendre ce qui était directement
faisable avec Tulip et mieux cerner
les ajouts nécessaires. Pour répondre à ces questions, une première
expérimentation a été réalisée dans Tulip, par deux
étudiants de Master 2, encadrés par G. Melançon et B. Pinaud à
l'université de Bordeaux 1
pendant le semestre d'automne 2008. L'objectif donné aux étudiants
était de développer sous Tulip les règles de réécritures
(codées directement en C++) décrites dans l'étude de cas "Autonomous Computing" issu de la thèse de
O. Andrei [1]. Ce travail a contribué au développement d'une
représentation interne des
portgraphes sous Tulip, une représentation visuelle et une première
version des algorithmes de tracé associés afin d'aboutir à
un premier prototype fonctionnel. Nous avons ainsi pu mettre
en exergue les limites de
Tulip concernant les portgraphes et les graphes dynamiques, et faire
un premier pas vers la réalisation du programme de travail prévu pour
la première année du projet, qui est développé ci-dessous.
|
Une première stratégie de dessin et visualisation de graphes. Dans un portgraphe, les sommets sont appelés des portnodes. Sous Tulip, chaque portnode est composé d'un sommet, appelé centre, auquel sont reliés autant de sommets qu'il y a de ports associés aux portnodes (voir la figure (a) qui représente un portnode appelé EGF.EGF avec des ports de type 1 et 2) . Nous avons bien sûr donné un meilleur aspect au portnode (figure b). Une règle de réécriture de graphes consiste en deux sous-graphes (partie gauche et partie droite) et une correspondance entre les ports de chaque partie. Elle est également représentée comme un portgraphe, avec un noeud particulier (appelé bridge) représentant cette correspondance. Grâce à ce premier travail des étudiants de Master 2, nous avons pu ensuite mettre au point une première version fonctionnelle de deux algorithmes de tracés pour Tulip : un premier pour dessiner les modèles et un autre pour les règles (figure c). |
![]() |
![]() |
![]() |
| a. Structure d'un PortNode sous
Tulip |
b. Le même portnode tel qu'il
est présenté à l'utilisateur |
c. Exemple de règle de
réécriture |
Une interface pour les réseaux
d'interactions. Pour les spécialistes de modèles de calculs
ou des réseaux d'interactions, l'interface par défaut de Tulip peut
être difficile à utiliser. Dans le cadre de son doctorat, O. Namet
développe "GraphPaper", un éditeur visuel de graphes et de règles de
réécriture, conçu pour faciliter la création et la gestion de réseaux
d'interaction. GraphPaper est basé sur les mêmes principes que les
nouvelles technologies utilisées dans les Human Interface Devices
(HID), par exemple les consoles de jeux électroniques ou les
téléphones portables "touch screen" : leur principe est de simuler les
interactions qu'un utilisateur aurait avec les objets réels. Dans
notre cas, il s'agit de dessiner des graphes à l'écran aussi
naturellement qu'avec un crayon sur un papier.
Dans le cas des
graphes, il y a deux types d'entités avec lesquelles l'utilisateur
doit interagir: les sommets et les arêtes. L'interface de GraphPaper
n'utilise pas de menus car l'outil peut déduire quel est l'objet de
l'interaction simplement par son contexte. Par exemple, une arête doit
connecter deux ports, donc il n'est pas possible de dessiner une arête
dans un autre contexte. Un cercle peut être tracé pour créer un noeud
ou pour sélectionner un sous-graphe. Pour dessiner une règle
d'interaction dans GraphPaper, il suffit de dessiner deux graphes
(partie gauche et partie droite de la règle) et de les
sélectionner. GraphPaper passe donc à l'état de création de règle, et
aide l'utilisateur à dessiner la correspondance entre les ports des
interfaces gauche et droite qui doit être indiquée explicitement, en
reliant ces ports (GraphPaper montre ces liens dans une couleur
différente).
GraphPaper
peut donc venir remplacer le moteur de
rendu visuel de Tulip pour dessiner un réseau d'interaction et les
règles de réécriture associées. Il interagit ensuite avec le moteur de
réécriture développé sous Tulip pour obtenir une application complète
de réécriture. Ce travail d'intégration a demandé une étroite
collaboration entre les membres de l'équipe associée et doit être
opérationnel pour la fin de la première année. Il rentre dans
l'optique de création d'interface spécialisée de Tulip pour une
application donnée de l'environnement PORGY.
|
La conception du système global. Conjointement
à
ce travail centré sur le dessin de représentation et visualisation de
graphes, nous avons également conçu l'organisation du système global,
dont les grandes lignes sont esquissées ci-dessous. Tulip n'est pas
spécifiquement conçu pour gérer les graphes dynamiques, la réécriture
et les différentes opérations à effectuer. Nous avons donc dû mettre au
point une organisation interne des données pour remédier à cela puisque
Tulip n'est capable de gérer qu'un seul graphe à la fois. Nous avons décidé d'utiliser le mécanisme de
hiérarchie de sous-graphes proposé par Tulip (voir la figure d). Nous
utilisons donc un
sous-graphe pour chaque règle(rule_1, rule_2 et rule_3 dans
l'exemple), un sous-graphe pour chaque état du modèle (m0 et m1) déjà calculé et un
dernier graphe appelé "arbre de dérivation" (Trace) qui permet de conserver une trace de toutes les réécritures effectuées. Dans cet arbre, les sommets
sont les différents états du modèle et une arête relie deux sommets A
et B si l'application d'une règle permet de transformer A en B.
Le graphe appelé E, ou "Root Graph", est imposé par Tulip. Les
sous-graphes associés aux différents états du modèle (sg_rule_1_0,
sg_rule_1_1, ...) représentent
une instanciation
d'une règle dans le modèle. Le nom de ces sous-graphes est calculé pour
nous permettre de conserver et retrouver aisément la trace des
différentes actions effectuées par l'utilisateur. Par exemple, le
sous-graphe sg_rule_1_1
associé à m1 représente la première instance possible (le dernier
chiffre 1) de la règle 1 dans le
modèle m1. La création initiale de la hiérarchie, des portnodes et a fortiori des règles et de l'état initial du système à étudier (le modèle m0) avec l'interface par défaut de Tulip sont des étapes longues, parfois complexes et laborieuses. Damien Sabary (étudiant de Master 1 à Bordeaux 1) a effectué un stage sur ce point. Son objectif était de créer une application pour générer (ou modifier) facilement un fichier Tulip qui contienne toutes ces informations. Ce stage a permis d'aboutir à une application parfaitement fonctionnelle qui est le premier élément de la plate-forme PORGY. |
![]() |
|
d. Hiérarchie de sous-graphes Tulip nécessaire pour gérer les aspects dynamiques et la conservation de l'historique de la réécriture |
Aspects dynamiques : application d'une règle de réécriture.
L'application d'une règle R donnée sur un modèle M0 donné
s'effectue en deux étapes, et nous avons décidé qu'elles seraient
effectuées par
des plugins Tulip.
La première étape est chargée de chercher dans M0
les sous-graphes SGM isomorphes à la partie gauche de R. Une première
version de ce plugin est terminée. Nous avons implémenté un algorithme
de recherche de sous-graphes isomorphes à un
graphe donné inspiré des travaux de Ullman [3] et de Cordella et al. [2]. Ces algorithmes ont été adaptés
pour tenir
compte de nos applications spécifiques, comme expliqué ci-dessous. Pour
préparer l'étape suivante qui consiste à effectuer le remplacement des
sommets de la partie gauche de la règle par ceux de la partie droite,
nous établissons une correspondance entre les sommets de la partie
gauche de la règle et ceux des sous-graphes de M0 qui représentent les
instanciations de cette règle. A l'aide du système de propriétés de
Tulip, pour chaque composante de chaque sous-graphe de M0, nous
ajoutons un "tag" qui est l'identifiant interne Tulip (unique) du
sommet ou de l'arête de la partie gauche de la règle.
Ensuite, si
l'utilisateur décide d'appliquer R sur un de ces sous-graphes, alors
dans une deuxième étape,
une copie de M0 est réalisée pour créer M1 et les sommets du
sous-graphe de M1 choisi sont remplacés par ceux de la
partie droite de la règle R en connectant correctement les nouveaux
sommets au reste du graphe. Pour réaliser ces opérations, la propriété
"tag" des sous-graphes de M0 permet de faire la liaison entre les ports
de l'instance de la règle et ceux de la partie gauche. Les arêtes
dessinées en rouge sur les règles (voir figure c) permettent de faire
la liaison entre la partie gauche et la partie droite de la règle. Une
fois le remplacement par la partie droite de la règle effectuée, nous
pouvons restaurer correctement l'état des ports et
reconnecter toutes les arêtes appartenant au modèle mais pas à
l'instance de la règle.
Un
méta-sommet qui représente M1 est alors ajouté au graphe de trace.
Ce nouveau sommet est relié par une arête au méta-sommet qui
représente le modèle qui a permis de le
créer. Afin de pouvoir reconstruire plus tard la dynamique et analyser
le système, nous conservons sur l'arête l'identifiant du sous-graphe
qui
a permis de créer M1. Donc, en effectuant un simple parcours de ce
graphe, nous pouvons facilement retrouver les enchainements
d'opérations effectuées par l'utilisateur.
Ces deux étapes qui représentent la base de la plate-forme PORGY sont implementées par deux plugins qui seront
ensuite pilotés par un gestionnaire de
stratégie. Le plugin chargé de gérer la deuxième étape (remplacement des sommets
dans le
modèle et ajout d'un nouveau sommet à l'arbre de dérivation) est en
cours de finalisation. Il devrait être terminé pour notre séminaire du mois de novembre.
Ainsi, toutes les tâches associées à la première année ont été réalisées ou seront finies dans les mois qui restent.
Hébergement des développementsLa présentation de notre approche et la diffusion des premiers résultats se sont faites sous trois modes différents:
Bibliographie
Avant de remplir les tableaux, consultez les règles au paragraphe "Financement" de la page d'accueil du programme.
| 1. Dépenses EA (effectuées sur les crédits de l'Equipe Associée) |
Montant dépensé
|
| Invitations des partenaires | 3 759,86€ |
| Missions INRIA | 2 422,32€ + 2000€ (mission novembre) |
|
Total
|
6182,18€ + 2000€ |
Justifiez en quelques lignes l'utilisation des
crédits
et en particulier une utilisation partielle du budget alloué.
Les crédits disponibles sur le budget de l'EA ont
été utilisés exclusivement pour le financement des séminaires communs
d'équipe et pour les voyages d'O. Namet vers Bordeaux afin de faciliter
le travail en commun. La somme de 2000€ supplémentaire est le budget
prévisionnel du déplacement à Londres de H.
Kirchner, B. Pinaud et O. Andrei prévu du 8 au 11 novembre.
Par rapport au budget demandé et alloué, il s'est avéré que les voyages
Bordeaux-Londres sont meilleur marché que ce que nous pensions. De
plus, nous n'avons malheureusement pas pu trouver tous les stagiaires
que nous espérions.
| 2. Dépenses externes (effectuées sur des financements hors EA) |
Montant dépensé
|
|
| Nom de l'organisme 1 (*):
King's College London |
||
| Invitations des partenaires | |
|
| Missions INRIA vers le partenaire | environ
£300 (organisation des
séminaires PORGY à Londres) |
|
|
Total
|
£300 (~330€) |
|
| Nom de l'organisme 2 (*):
INRIA Bordeaux Sud Ouest (ressources propres Equipe GRAVITE) |
||
| Gratification de stage (D.
Sabary) |
1132,83€ |
|
| Invitations des partenaires | ||
| Missions INRIA vers le partenaire | ||
|
Total
|
1132,83€ | |
(*) Ajouter ou supprimer
des lignes au tableau ci-dessus de façon à faire figurer tous les
organismes ayant contribué au financement de l'équipe associée
|
Total des financements externes dépensés |
1462.83€ |
|
Total des financements EA et externes dépensés |
7645,01€+2000€ |
1. Chercheurs Seniors
|
Nom
|
statut (1) | provenance | destination | objet (2) | durée (3) | Coût (si financement EA) |
Coût (si financement externe)
|
| Maribel Fernandez |
Lecturer | Londres | Talence | Séminaire de travail | 3 jours | 400,51€ | |
| Maribel Fernandez | Lecturer | Londres |
Talence | Séminaire de travail |
3 jours | 231,25€ | |
| Hélène Kirchner | DR |
Talence | Londres | Séminaire de travail |
3 jours | 754,64 | |
| Hélène Kirchner | DR | Talence |
Londres |
Séminaire de
travail |
3 jours |
Planifié 750€ |
|
| Guy Melançon | PR |
Talence | Londres | Séminaire de travail |
3 jours | 775,31 | |
| Bruno Pinaud |
MCF |
Talence | Londres | Séminaire de travail |
3 jours | 892,37 | |
| Bruno Pinaud | MCF |
Talence |
Londres |
Séminaire de travail |
3 jours | Planifié 750€ | |
|
Total des durées
|
21 jours |
2. Juniors
|
Nom
|
statut (1)
|
provenance
|
destination |
objet (2)
|
durée (3)
|
Coût (si financement EA)
|
Coût (si financement externe)
|
| Olivier Namet | Doctorant |
Londres | Talence | Formation à Tulip | 1 semaine |
837,74€ | |
| Olivier Namet | Doctorant | Londres | Talence | travail en commun et séminaire de travail | 1 semaine | 716,91€ | |
| Olivier Namet |
Doctorant |
Londres | Talence | Travail en commun et séminaire de travail | 1 semaine | 889,76€ | |
| Oana Andrei |
Post-doctorante |
Glasgow | Talence | séminaire de travail | 1 semaine |
683,69€ | |
| Oana Andrei | Post-doctorante |
Glasgow |
Londres |
Séminaire de travail | 2 jours | 500€ planifié |
|
Total des durées
|
4 semaines et 2 jours |
La dynamique du système est spécifiée par les règles de réécriture de graphes, qui décrivent les évolutions possibles du système. Le modèle initial évolue donc avec l'application des règles et une trace en résulte, représentée sous forme d'arbre de dérivations, comme expliqué plus haut. La notion de stratégie d'application des règles est essentielle dans la construction de l'arbre de dérivations, puisque la stratégie contrôle la création des différents sommets de cet arbre. Mais d'un point de vue théorique, le concept même de stratégie est encore l'objet de nombreuses recherches. De plus, il n'existe actuellement pas de langage général pour la définition de stratégies de réduction pour les systèmes de réécriture de graphes. Donc un premier point à étudier est la définition d'un tel langage.
D'un
point de vue global, la hiérarchie de sous-graphes mis en place pendant
la première année ainsi que l'utilisation du système de propriété de
Tulip nous permet de
conserver toutes les informations nécessaires pour reconstruire,
montrer et étudier la dynamique du système. A terme, la plate-forme
PORGY doit
permettre l'étude d'un point de vue visuel et dynamique de l'arbre de
dérivations. Un chemin
de la racine vers une feuille de cet arbre représente une
évolution dynamique du modèle étudié. Néanmoins, c'est l'utilisateur
qui construit dynamiquement son chemin en interagissant avec la
représentation visuelle, les interactions conduisant à appliquer de
nouvelles règles sur le modèle. De plus, l'utilisateur peut à tout
moment effectuer des retours en arrière (backtracking) dans l'arbre pas
forcément
par le même chemin. La visualisation et la navigation dans une telle
structure présentent
donc plusieurs défis. Par rapport aux travaux existants
sur les graphes dynamiques,
les nouveautés
importantes sont que la dynamique ne vient pas du
temps mais de l'application d'une ou plusieurs règles entre deux états
du modèle selon la stratégie utilisée, et du fait que nous ne connaissons pas non
plus a priori la structure de l'arbre de dérivation.
De façon plus générale, une nouvelle forme de navigation dynamique et
interactive est à mettre au point pour permettre à un utilisateur de
naviguer librement dans l'arbre de dérivations de façon interactive.
Cette navigation s'appuiera bien évidemment sur les différents états du
modèle calculés et des informations
portées par les arêtes de l'arbre de dérivations. Les branches de l'arbre de dérivations
peuvent alors être vues comme un ensemble de scénarios à suivre mais qui sont construits au
fur et à mesure de la lecture, sachant que des retours en arrière sont
toujours possibles pour emprunter une nouvelle voie.
Un système de réécriture de graphes avec une stratégie d'application de règles est à la fois une modélisation d'un système et un programme exécutable. Un environnement graphique permettant de déboguer un programme de réécriture de graphes, qui plus est suivant une statégie donnée, n'existe pas à l'heure actuelle. La réalisation d'un premier outil allant en ce sens serait donc une avancée importante car cela apporterait une assistance majeure au développeur pour comprendre l'évolution de son programme et l'impact des choix qu'il fait.
De façon plus précise, le travail de la 2e année s'organisera autour des tâches définies ci-dessous. Pour chacune de ces tâches, le travail commencera dès janvier 2010, et les idées préliminaires seront discutées pendant la première réunion d'équipe en février 2010 à Londres. Nous ferons le bilan du travail à mi-parcours lors de la réunion d'équipe à Bordeaux en juillet 2010. L'objectif à cette date est d'avoir une version du système intégrant le langage de stratégies et l'arbre de dérivations conçus dans les deux premières tâches décrites ci-dessous.
Une stratégie de réécriture est une expression, dans un langage de description de stratégies, qui sert à piloter l'application des règles de réécriture. Plus précisément, l'utilisateur de la plate-forme PORGY se servira de ce langage pour spécifier quelles règles doivent être appliquées, dans quel ordre, et dans quelle partie du modèle.
Les langages de description de stratégies disponibles à ce jour ont été développés pour des systèmes de réécriture de termes. Ils reposent fortement sur la notion de racine pour décrire des parcours dans l'arbre associé au terme. Dans le cas des graphes, la notion de racine n'existe pas mais nos travaux préliminaires montrent que cette notion peut être généralisée par la notion d'interface. Dans les expressions qui décrivent les stratégies pour la réécriture de graphes, on doit donc distinguer deux parties : la sélection des règles à appliquer, et la description du ou des sous-graphes sur lesquels ces règles doivent s'appliquer.
Ainsi, cette tâche qui implique des participants des deux sites, peut être décomposée en deux sous-tâches :Les algorithmes mis au point pendant la première année pour visualiser les règles et les différents états du modèle d'une manière statique nous permettent actuellement de travailler correctement. Néanmoins, ces algorithmes doivent être améliorés en tenant compte des propriétés spécifiques des graphes utilisés et étendus pour mieux gérer la visualisation dynamique du modèle. Les portgraphes, les portnodes ou les règles sont des modèles de graphes très contraints et très précis (par ex. une règle a une partie droite et une partie gauche, les ports d'un portnode sont forcément regroupés autour de son centre, ...). Les algorithmes classiques de visualisation de graphes, qui partent bien souvent du principe qu'il n'y a qu'un seul type de sommet et d'arêtes, ne peuvent donc pas être utilisés en l'état. Nous envisageons dans un premier temps d'étudier les travaux de T. Dwyer [1,2,3] sur le tracé de graphes et l'utilisation d'un moteur de résolution de contraintes pour effectuer ces tracés. Nous souhaitons confier une grande partie de ce travail à un stagiaire de niveau M2 à Bordeaux. Daniel Archambault qui effectue un post-doctorat à Bordeaux dans l'EPI GRAVITE nous apportera également son aide sur cette tâche.
L'arbre de dérivations nécessite une structure de données
adaptée, car non seulement on doit pouvoir représenter les différentes
évolutions possibles du système, dont on ne connait
pas a priori ni le nombre de
branches ni leur taille, mais on doit aussi pouvoir naviguer
facilement dans cet arbre. Il s'agit donc de concevoir une structure
de données et des algorithmes permettant à l'utilisateur de visualiser
dynamiquement des parties de l'arbre (pour visualiser des états précédents par
exemple), de revenir en arrière (faire du backtracking) pour naviguer
sur une branche différente, etc. Nous envisageons dans un premier
temps d'adapter les techniques classiques bien connues des "Small
Multiples" [4] (on affiche de façon statique comme dans une bande
dessinée plusieurs états du graphe) ou encore des
animations
(on fabrique une
sorte de film qui montre les transitions entre différents états du
graphe). On prévoit la participation de tous les membres de l'équipe
dans cette tâche, et un stage est prévu sur ce sujet à Londres
(Gabrielle Luciano, étudiante à King's College, travaillera avec nous à
partir
d'octobre 2009 dans le cadre de son projet de "graduation"). Daniel
Archambault nous apportera également son aide sur cette tâche.
La plate-forme PORGY sera un outil de simulation, de visualisation et d'analyse de systèmes dynamiques spécifiés par des règles de réécriture de graphes. La mise au point d'une modélisation dans le cas de systèmes complexes, comme les systèmes issus de la biologie ou les programmes en réseaux d'interaction, est un processus difficile. Un des buts de la plate-forme PORGY est de donner à l'utilisateur des outils pour l'aider dans cette tâche. Par exemple, l'utilisateur a souvent besoin d'expérimenter avec des règles différentes. Un changement dans les règles peut avoir comme conséquence une multitude de changements dans l'arbre de dérivations. En naviguant dans l'arbre de dérivations, l'utilisateur doit pouvoir spécifier des nouvelles règles, ou des changements dans les règles existantes. La trace du système doit ensuite refléter ces changements. Il s'agit donc de concevoir des algorithmes pour la modification locale et efficace de l'arbre de dérivations, avec la possibilité de visualiser les règles qui interviennent dans une partie spécifique de l'arbre. On prévoit la participation de tous les membres de l'équipe dans cette tâche.
Livrables
Chacune des tâches définies ci-dessus a vocation à donner lieu à
des publications conjointes.
A la fin de la deuxième année, nous prévoyons un article sur le langage
de description de stratégies, un article sur la visualisation des
règles et états du système, et un article sur la représentation et la
navigation dans l'arbre de dérivations. Les outils de vérification et
les cas d'étude donneront aboutiront à des publications
probablement pendant la troisième année.
De plus, PORGY rentre parfaitement dans le cadre du projet de
l'équipe-projet GRAVITE. En participant à l'extension de la librairie
TULIP pour la gestion, la manipulation et la visualisation des graphes
dynamiques, PORGY permet d'aider à atteindre les objectifs annoncés de
GRAVITE.
Notre projet d'équipe associée est associé à une forte composante de développement logiciel.
Le livrable final, prévu à la fin de la troisième année, est la plate-forme
PORGY complète, qui permettra la manipulation et l'exploitation de graphes
dynamiques dans un environnement graphique spécifique. Ce logiciel est construit de
manière modulaire; chacune des tâches définies ci-dessus inclut le
développement d'une partie du code qui sera integrée dans le système final.
Bibliographie
[1] T. Dwyer, Y. Koren et K. Marriot. IPSep-CoLa: An Incremental Procedure for Separation Constraint Layout of Graphs. IEEE Trans. on Visualization and Computer Graphics 12(5): 821-828, 20061. Echanges
Décrivez les échanges prévus dans les deux sens :
invitations de chercheurs de votre partenaire et missions INRIA vers
votre partenaire ;
Précisez s'il
s'agit de chercheurs confirmés ou de juniors (stagiaires,
doctorants, post-doctorants) ;
Motivez,
si possible, les raisons scientifiques (travail commun,
workshop,..) et précisez la durée prévue ;
Indiquez
les étudiants impliqués dans la proposition. Donnez une estimation de
leur nombre, pour chaque partenaire, et précisez si des thèses en
cotutelle sont prévues ;
Résumez ensuite ces informations dans les tableaux 1
et 2 ci-dessous en faisant une estimation budgétaire :
Les échanges de jeunes chercheurs entre les deux sites (Londres et
Bordeaux) avec une durée minimale d'une semaine, conjugués avec un
séminaire de travail rassemblant pendant 2-3 jours tous les membres de
l'équipe, se sont révélés fructueux. Nous continuerons donc sur ce
modèle, en réalisant les visites suivantes, comme mentionné dans le
programme de travail pour 2010. Les étudiants qui feront leurs stages
sur des sujets liés au
projet seront aussi invités à ces réunions.
Première réunion d'équipe, février 2010, Londres :
Réunion de travail sur 3 jours pour travailler sur les orientations de
l'année comme
indiqué dans le programme de travail.
Déplacements de jeunes chercheurs vers le partenaire : O. Andrei, D. Archambault
Déplacements de chercheurs confirmés vers le partenaire : H. Kirchner,
G. Melançon, B. Pinaud
Déplacement de stagiaire : un éventuel stagiaire de l'équipe GRAVITE
Réunion mi-parcours, juillet 2010, Bordeaux :
Réunion de travail sur 3 jours pour faire le point sur le développement
du projet a mi-parcours.
Invitation de jeunes chercheurs : O. Namet (déplacement à prévoir sur
la semaine entière)
Déplacement de jeune chercheur : O. Andrei
Invitation de chercheurs confirmés : M. Fernandez
Invitation de stagiaire : G. Luciano, stagiaire de King's College
(déplacement à prévoir sur la semaine entière)
Réunion de fin d'année, novembre 2010,
Londres :
Réunion de travail sur 3 jours pour faire le bilan des résultats, le
travail restant à faire sur le programme de travail, préparation de la dernière année
Déplacements de jeunes chercheurs vers le partenaire : O. Andrei, D.
Archambault, un éventuel nouveau doctorant (encadrement G. Melançon, B.
Pinaud)
Déplacements de chercheurs confirmés vers le partenaire : H. Kirchner,
G. Melançon, B. Pinaud
Réunions ouvertes :
Par ailleurs, nous organiserons également au moins un séminaire
ouvert à des collègues extérieurs au projet qui ont manifesté leur
intérêt pour PORGY, en particulier Vincent Danos (U.Paris7 et
Edinburgh) et Rachid Echahed (CNRS IMAG Grenoble). Pour ce séminaire,
nous souhaitons pouvoir inviter les collègues extérieurs qui nous
apporteront leur expérience sur leur domaine respectif de compétence
par l'intermédiaire d'un exposé et d'une discussion.
Pour l'équipe associée, l'objectif de
ces séminaires est d'exposer notre approche pour recueillir un
feedback ainsi que des nouveaux exemples d'applications. Nous avons planifié la réalisation d'au moins un séminaire en Avril 2010 à Bordeaux,
sur 3 jours.
Invitation de jeunes chercheurs : O. Andrei, O. Namet (déplacement à
prévoir sur l'ensemble de la semaine)
Invitation de chercheurs confirmés : M. Fernandez
Invitation des conférenciers : Vincent Danos (U.Paris7 et
Edinburgh) et Rachid Echahed (CNRS IMAG Grenoble)
Selon budget : invitation d'un stagiaire du partenaire
| 1. ESTIMATION DES DÉPENSES EN MISSIONS INRIA VERS LE PARTENAIRE |
Nombre de personnes
|
Coût estimé
|
| Chercheurs confirmés | 3 | 750 * 3 * 2 = 4500 |
| Post-doctorants |
2 | 750*2 + 750 (O. Andrei) * 2 + 500 *2 (O. Andrei) = 4000 |
| Doctorants | 1 | 750 |
|
Stagiaires |
1 | 750 |
| Autre (précisez) : |
||
|
Total
|
7 | 10000 |
Note : O. Andrei effectue son post-doctorat à Glasgow. Selon si on va à Londres ou à Bordeaux, le coût du voyage est différent.
| 2. ESTIMATION DES DÉPENSES EN INVITATIONS DES PARTENAIRES |
Nombre de personnes
|
Coût estimé
|
| Chercheurs confirmés | 1 | 450*2 = 900 |
| Post-doctorants |
||
| Doctorants | 1 | 800*2 = 1600 |
|
Stagiaires |
1 |
800*2 = 1600 |
| Autre (précisez) : |
||
|
Total
|
3 | 4100 |
| 3.
ESTIMATION DES DÉPENSES EN INVITATIONS DE PERSONNALITES |
Nombre de personnes
|
Coût estimé
|
| Chercheurs confirmés | 2 | 415*2 =830 |
| Autre (précisez) : |
||
|
Total
|
1 |
830 |
2. Cofinancement
Cette coopération bénéficie-t-elle déjà d'un soutien
financier de la part de l'INRIA, de l'organisme étranger partenaire ou
d'un organisme tiers (projet européen, NSF, ...) ?
Indiquez ces éléments et donnez les montants associés.
Oui, pour la première année, cette coopération a
bénéficié du soutien financier
de
King's College London (environ 300£ ) et de l'équipe GRAVITE (1132.83
euros pour le stage de D. Sabary).
En 2010, King's College London continuera de soutenir ce projet, en
particulier
avec une contribution au coût de l'organisation des reunions a Londres
(estimation à 300 £, env. 330€),
et la prise en charge d'une mission de Londres vers la France
(estimation à 1300 €). GRAVITE financera aussi un éventuel stagiaire (M2 et/ou M1) en
2010 et des ressources seront trouvées pour accueillir un nouveau doctorant.
3. Demande budgétaire
Indiquez, dans le tableau ci-dessous, le coût global
estimé de la proposition et le budget demandé à la DRI dans le cadre de
cette Equipe Associée.
(maximum 20 K€ pour une prolongation en 2e année et 10 K€ pour une
3e année).
|
Commentaires
|
Montant
|
| A. Coût global de la proposition (total des tableaux 1 et 2 : invitations, missions, ...) | 14930 |
| B. Cofinancements utilisés (financements autres que Equipe Associée) | 1630 |
|
Financement "Équipe Associée" demandé (A.-B.)
|
13300 |
Remarques ou observations :