Direction des Relations Internationales (DRI)

Programme INRIA "Equipes Associées"
(Demande de prolongation)

 


I. DEFINITION

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

LaBRI - Bâtiment A30

Campus Université Bordeaux I

351 Cours de la Libération

33405 Talence Cedex


Strand

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
NOTA : Si la proposition d'Equipe Associée comporte plusieurs partenaires, français et/ou étrangers, vous pouvez :
- soit ajouter une colonne,
- soit dupliquer le tableau ci-dessus autant de fois que nécessaire, en remplaçant "Coordinateur français ou étranger" par "Autre participant français ou étranger".

La proposition en bref

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.
Outre la modélisation de systèmes biologiques ou informatiques, nous travaillons notamment sur les réseaux d'interaction (définis par Yves Lafont en 1990) qui peuvent être vus comme une classe particulière de portgraphes avec des propriétes calculatoires intéressantes. Dans les réseaux d'interaction, les sommets possèdent un port distinct, appelé port principal, et les règles de réécriture, appelées règles d'interaction, s'appliquent toujours sur des paires de sommets reliés par leurs ports principaux. De plus, dans une réécriture, la partie droite de la règle doit avoir les mêmes connexions que la partie gauche (i.e., l'interface est préservée). Même avec ces contraintes, les réseaux d'interaction s'avèrent être un formalisme de calcul universel, utilisé avec succès pour l'implémentation efficace des langages de programmation fonctionnelle.

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 :

  • créer un portgraphe, les règles de réécriture associées et les stratégies, en utilisant un éditeur visuel ;
  • effectuer de façon visuelle et interactive des transformations sur un modèle de données représenté par un portgraphe avec les règles de réécriture selon une ou plusieurs stratégies définies par l'utilisateur ;
  • voir dynamiquement et visuellement les différentes évolutions du portgraphe au fur et à mesure des applications de règles ;
  • naviguer dans l'historique des transformations (backtracking) ;
  • mettre au point des méthodes d'analyses et de vérifications des différentes propriétés statiques et dynamiques des graphes générés.

 


II. BILAN 2009

Changements majeurs survenus concernant l'Equipe Associée (modifications des objectifs scientifiques, des chercheurs impliqués)

Evolution de la liste des chercheurs impliqués

Par rapport à la liste initiale des personnes impliquées dans PORGY, nous distinguons dorénavant plusieurs catégories de personnes selon leur implication dans le projet. De plus lors de nos séminaires à Bordeaux ou Londres, nous avons fait intervenir (exposé et discussion) d'autres chercheurs intéressés par notre projet qui pouvaient soit nous fournir de nouvelles applications de la plate-forme de réécriture soit nous aider pour les futurs développements. Nous avons aussi fait contribuer des étudiants de l'université de Bordeaux 1 à notre projet dans le cadre de leur formation.

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)


Rapport scientifique de l'année 2009

Le formulaire soumis en 2008 pour la demande d'équipe associée est disponible à http://gravite.labri.fr/porgy/soumission09.html

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) :


Le travail sur le projet PORGY a commencé peu de temps après la soumission du dossier de demande de projet (début octobre 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.

En ce qui concerne le cas plus spécifique de l'application de règles d'interaction dans un réseau d'interaction, ce problème ne demande pas l'utilisation d'un algorithme de recherche de motifs basé sur l'isomorphisme de graphes. Les membres gauches des règles ne contenant que deux sommets connectés par leurs ports principaux, il est possible de définir un algorithme simple d'application de règle : il suffit de chercher dans le graphe donné les arêtes qui connectent deux ports principaux. Dans une première étape, un plugin spécifique a été défini pour ce cas, mais nous avons ensuite remarqué que l'algorithme général de recherche de sous-graphes isomorphes peut être adapté pour tenir compte de cette propriété. L'idée est de commencer par chercher des arêtes isomorphes, au lieu de chercher d'abord des sommets isomorphes. L'algorithme qui a été implémenté se base sur une recherche d'arêtes isomorphes. Dans la réunion d'équipe prévue pour le mois de novembre, nous allons finaliser le plugin de recherche de motifs, le but étant d'avoir un seul plugin pour gérer les portgraphes en général et les réseaux d'interaction en particulier, tout en restant très efficace dans ce dernier cas. 

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éveloppements
Nous utilisons la plate-forme INRIAGforge pour héberger notre projet (appelé PORGY). Notre projet n'est pour le moment pas publiquement accessible. Nous pouvons ouvrir un accès au dépôt SVN sur simple demande.

Diffusion des résultats, organisation de colloques dans des domaines liés au projet:

La présentation de notre approche et la diffusion des premiers résultats se sont faites sous trois modes différents:

Publications ( à paraitre)


Bibliographie

[1] O. Andrei. A Rewriting Calculus for Graphs: Applications to Biology and Autonomous Systems, Thèse de Doctorat, Institut national polytechnique de Lorraine, 2008.
[2] L. P. Cordella, P. Foggia, C. Sansone et M. Vento. A (Sub)Graph Isomorphism Algorithm for Matching Large Graphs. IEEE Trans. on Pattern Analysis and Machines Intelligence, vol 26, n°10, pp 1367-1372, 2004.
[3] J. R. Ullmann. An Algorithm for Subgraph Isomorphism. J. of the Association for Computing Machinery, vol 23, n°1, pp 31-42, 1976 

Rapport financier 2009

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€

 

Bilan des échanges effectués en 2009


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 

(1) DR / CR / professeur
(2) colloque, thèse, stage, visite....
(3)
précisez l'unité (mois, semaine..)


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
(1) post-doc / doctorant / stagiaire
(2) colloque, thèse, stage, visite....
(3) précisez l'unité (mois, semaine..)

III. PREVISIONS 2010

Programme de travail

Description du programme scientifique de travail pour l'année 2010 

Objectifs :
Les objectifs de la 2e année annoncés dans la proposition initiale (rédigée en anglais) sont les suivants :
En conséquence, le programme de travail pour la deuxième année se centre sur le développement de mécanismes permettant de gérer les aspects dynamiques du graphe, et d'interagir avec la trace du processus de réécriture (l'arbre de dérivations), par exemple, en réalisant du backtracking (navigation libre dans l'arbre de dérivations).

Les défis scientifiques posés par ces objectifs sont de plusieurs ordres:

Organisation du travail

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.
Il est prévu d'organiser un séminaire ouvert (invitation de personnalités extérieures au projet fortement intéressées par nos travaux) en avril 2010, qui servira aussi pour faire le point sur l'avancement des travaux.
Des stages seront proposés à Bordeaux et à Londres sur des sujets liés, à des niveaux M1 ou M2. Nous envisageons aussi de déposer une demande de bourse de thèse à Bordeaux pour la deuxième tâche (sujet lié à la visualisation des chemins et la navigation dans l'arbre de dérivations). Cette organisation du travail, qui permet d'intégrer des étudiants dans le projet, s'est révélée fructueuse pendant la première année. Nous continuerons donc sur ce modèle.

Comme pour la première année, nos développements auront pour objectif la fourniture en fin de troisième année d'une plate-forme de manipulation de réécriture de graphes par l'intermédiaire de portgraphes. Nous nous appuierons particulièrement pour cette deuxième année sur deux applications : la programmation avec des réseaux d'interaction et la simulation de réseaux biochimiques.

Principales tâches


Les techniques de simulation et debugging qui seront développées dans la deuxième année du projet seront complétées dans la troisième année par des techniques d'analyse statique. En particulier, des techniques basées sur le typage permettront de détecter des erreurs dans la spécification avant l'exécution du programme.
Le développement des deux cas d'étude mentionnés plus haut se poursuivra aussi sur la troisième année. En parallèle, pendant la troisième année, nous travaillerons aussi sur la création d'une perspective Tulip "Portgraphes" qui sera une finalisation de la plate-forme PORGY. D'un point de vue fonctionnel, une perspective Tulip est semblable à une perspective de l'environnement de développement intégré Eclipse (http://www.eclipse.org). L'interface graphique du logiciel change selon ce que veut faire l'utilisateur. Par exemple, sous Eclipse, selon que le développeur veut faire du Java ou du C++, l'interface change ainsi que les fonctionnalités disponibles. Il a donc toujours l'environnement le mieux adapté possible au langage utilisé. Sous Tulip, l'utilisateur non spécialiste de visualisation et de tracé de graphes aura ainsi un environnement spécifiquement adapté à la réécriture de portgraphes avec seulement les fonctionnalités utiles associées.

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, 2006
[2] T. Dwyer, K. Marriott et M. Wybrow. Integrating Edge Routing into Force-Directed Layout. In Proc. 14th Intl. Symp. Graph Drawing (GD '06), volume 4372 of Lecture Notes in Computer Science, pages 8-19. Springer, 2007.
[3] T. Dwyer, K. Marriott, F. Schreiber, P. J. Stuckey, M. Woodward et M. Wybrow. Exploration of networks using overview+detail with constraint-based cooperative layout. IEEE Trans. on Visualization and Computer Graphics, 14(6):1293-1300, 2008
[4] E. Tufte. Envisioning Information. Graphics Press, 1990.

Programme d'échanges avec budget prévisionnel

1. 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 750 * 3 * 2 = 4500
Post-doctorants
750*2 + 750 (O. Andrei) * 2 + 500 *2 (O. Andrei) = 4000
Doctorants 750 

Stagiaires

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 450*2 = 900
Post-doctorants
   
Doctorants 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 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.)
(maximum 20 K€ pour une 2e année et 10 K€ pour une 3e année)

13300

Remarques ou observations :

 

 

 

© INRIA - mise à jour le 08/07/2009