L’activité dans la programmation spatiale

L’activité dans la programmation spatiale

Activité Intuitivement, nous dirons que l’activité est constitué d’un ensemble des choses qui changent, c’est à dire sur lesquels une action a eu lieu, en opposition au reste qui ne change pas. Au delà des différents sens communs accordés à l’activité, on rencontre quelques autres termes qui y sont naturellement liés comme état, énergie, changement ou mouvement. Le concept, plus formel, d’activité est emprunté au domaine de la simulation [27] ; il est reconnu, défini et utilisé dans plusieurs domaines scientifiques, dont la physique, la biologie, l’économie, l’épistémologie et bien naturellement l’informatique. L’article [20] fait la synthèse des différents domaines et propose une définition de l’activité dans chacun de ces contextes. Activité en simulation An activity is an operation that transforms the state of a system over time. It begins with an event and ends by producing another event (linked to the termination of the activity). Muzy et al. [20] Une activité, terme dénombrable dans ce cas, est une opération transformant l’état d’un système au cours du temps. Elle commence avec un évènement et termine en produisant un autre évènement (lié à la fin de cette l’activité). Un évènement est ce qui change l’état d’un système (éventuellement composé de nombreux composants). Pour finir, on appelle un processus une séquence d’activités et d’évènements ordonnés dans le temps. On peut remarquer que le terme « évènement » est central dans cette définition des activités. De plus les activités sont des objets plutôt que la mesure d’une quantité (la quantité d’activité). Activité dans DEVS Deux définitions de l’activité pour les systèmes à évènements discrets (Discrete-Event Systems ou DEVS) sont proposées : L’activité qualitative : un système est qualitativement inactif quand aucun évènement n’a lieu et est qualitativement actif sinon. L’activité quantitative : la somme des activités quantitatives interne et externe est égale à la valeur de l’activité quantitative, pendant un certain temps de simulation. Les évènements discrets peuvent être de deux types : interne ou externe au modèle atomique 

Activité 69 (endogène ou exogène)

L’activité quantitative interne correspond au nombre d’évènements discrets internes, pendant un certain temps de simulation. L’activité quantitative externe correspond au nombre d’évènements discrets externes, pendant un certain temps de simulation. L’activité externe fournit une information sur la quantité de messages échangés par les modèles atomiques. Activité du vivant En biologie, l’activité semble être liée au vivant, à la propriété d’être vivant. Une cellule est dite active si elle est vivante, ce qui ramène à la question de la définition du vivant. À l’échelle infra-cellulaire, cette définition fonctionne moins bien : il suffit de considérer chaque partie d’une cellule et tenter de déterminer si elle est vivante ou pas. Pour résoudre ce problème, la définition d’activité que l’on souhaite considérer est celle du point de vue de la chimie, à l’échelle moléculaire : […] any biological object which is the locus of both exchanges (gas, liquids, nutrients, molecules, etc.) and transformations (chemical transformations), which result in maintaining the integrity of the object, is declared active. Muzy et al. [20] Un objet biologique est dit actif s’il est à la fois un locus d’échanges (gaz, liquides, nutriments, molécules, …) et de transformations (transformations chimiques) et que ces échanges et transformations assurent la persistance de cet objet. Avec ces deux définitions arrivent les problèmes de quantification de l’activité dans les systèmes biologiques ; les mesures sont indirectes et les observables, c’est à dire les paramètres mesurables, sont nombreuses. En effet, au delà de l’influence même de la mesure sur ces systèmes, parfois seules des mesures de paramètres globaux, comme la quantité de CO􏷫 et de O􏷫 échangé entre le système et l’extérieur, sont accessibles. Autre exemple, pour connaître l’activité d’un réseau de neurones dans le cerveau, les chercheurs et les médecins ont recourt à l’imagerie par résonance magnétique fonctionnelle (IRMf) qui permet de connaître les zones du cerveau qui sont irriguées par du sang oxygéné. Dans les deux cas les mesures sont indirectes : elles sont plus ou moins globales et ne permettent pas de connaître l’activité de chacune des parties du système, de chaque cellule ou de chaque partie d’une cellule. De plus, de par la redondance des systèmes biologiques, une même sous-partie peut avoir plusieurs fonctions et une même fonction peut-être assurée par des sous-parties différentes dans un même système. Il est ainsi difficile de déterminer quelle partie du système a contribué au fonctionnement global et dans quelle proportion. Activité économique L’activité est au cœur des sciences économiques de part l’objet d’étude de cette discipline. En effet l’économie est une science qui se focalise sur la manière dont des ressources rares sont utilisées dans le but de satisfaire les besoins humains. Elle s’intéresse par conséquent aux opérations de production, de distribution et de consommation des biens d’une part, aux institutions et aux structures dont le but est de faciliter ces opérations d’autre part. Autrement dit, l’activité correspond à « ce que les acteurs font » ; l’activité économique est donc un phénomène impactant une ressource rare. Deux perspectives sur l’activité cohabitent : l’économie (néo)classique se penche sur les conséquences de l’activité, c’est à dire sur l’utilité de la situation qui en découle et non pas sur les décisions prises par les acteurs. Ces décisions sont prises à la suite d’un calcul rationnel, soit seul (substantive rationality), soit en groupe après délibération (procedural rationality), en fonction de la valeur de gain liée à ce choix ; l’économie comportementale (behavioral economics) est plutôt portée sur la manière dont les acteurs choisissent leurs activités, comment ils choisissent ce qu’ils vont faire. Leurs choix sont dans ce cas dictés par une règle préétablie (rule rationality), un mode de comportement qui incorpore toutes les situations concernées par cette règle. On remarque que dans chacune de ces perspectives on ignore l’activité en elle-même ; la valeur de l’utilité, conséquence d’un choix d’activité, est mise en avant dans le premier cas, le choix du type d’activité lui-même est mis en avant dans le second cas. En économie, établir la mesure de l’activité ne suscite que peu d’intérêt et reste un défi à relever. Par analogie avec la définition de l’activité quantitative dans le cas des systèmes à évènements discrets, on donne la définition suivante : l’activité est le décompte du nombre d’évènements concernant des ressources rares. Un exemple d’usage prospectif est donné dans la section intitulée « Optimal Control Model of Activity » de [20]. Pour conclure cette section sur l’activité, nous émettons les remarques suivantes : Les différentes définitions de l’activité suivant les domaines d’études ne se recouvrent pas exactement, néanmoins dans chaque cas l’activité, ou les activités, nous offrent une mesure sur le système étudié ; La mesure d’activité donne une représentation abstraite du système étudié, une mesure agrégée qui appartient à un autre niveau de représentation que le système lui-même. Nous verrons dans la suite de ce chapitre qu’il est possible de définir un nouveau type d’activité, l’activité spatiale, dans le contexte de MGS et que cette activité nous apportera une représentation du système utile à la fois pour la simulation et pour la modélisation. 

Complexe cellulaire abstrait

Les développements présentés dans la suite de ce chapitre reposent sur une classe d’objets mathématiques nommés complexes cellulaires abstraits, une description formelle et abstraite de l’espace qui sert de fondement aux collections topologiques de MGS ainsi qu’à la définition de l’activité spatiale. Cette section présente le formalisme et quelques propriétés associées. Afin d’effectuer des calculs dans l’espace, il peut être pratique de découper cet espace en éléments primordiaux, possédant une dimension, « accolés » les uns aux autres. Nous appelons ces éléments primordiaux des cellules topologiques dont l’assemblage combinatoire forme un  complexe cellulaire abstrait (CCA). Une 𝑝-cellule est une cellule topologique de dimension 𝑝. Par exemple, les 0-cellules sont des points, les 1-cellules sont des arcs, les 2-cellules sont des surfaces, les 3-cellules des volumes, … Les cellules topologiques sont « jointes » par une relation appelée relation d’incidence. Plus formellement, il s’ensuit les définitions correspondantes. Définition 3.3.1. Soit 𝑆 un ensemble de symboles appelés cellules topologiques muni d’un ordre partiel localement fini ⋅ ⪯ ⋅ ⊂ 𝑆 × 𝑆 appelé relation d’incidence. Le couple 𝒦 = (𝑆, ⪯) est appelé complexe cellulaire abstrait. Définition 3.3.2. Soit 𝒦 = (𝑆, ⪯) un complexe cellulaire abstrait. La fonction dim𝒦 ∶ 𝑆 → ℕ telle que pour 𝜎􏷪 , 𝜎􏷫 ∈ 𝑆, 𝜎􏷪 ≺ 𝜎􏷫 ⇒ dim𝒦 (𝜎􏷪 ) < dim𝒦 (𝜎􏷫 ) est appelée fonction de dimension. Dans la suite de ce manuscrit, on notera dim au lieu de dim𝒦 quand il n’y a pas d’ambigüité sur 𝒦 . De plus, on notera parfois 𝜎 ∈ 𝒦 au lieu de 𝜎 ∈ 𝑆. 𝑓 𝑒􏷡 𝑒􏷠 𝑒􏷢 𝑐􏷡 𝑐􏷠 𝑐􏷢 𝑓 𝑒􏷠 𝑒􏷡 𝑒􏷢 𝑐􏷠 𝑐􏷡 𝑐􏷢 12 5 6 5 (0, 4) (−3, 0) (3, 0) Fig. 3.1: Diagramme de Hasse (à gauche) de la relation d’incidence dans le complexe cellulaire du milieu. Ce dernier est constitué d’une 2-cellule 𝑓, de trois 1-cellules (𝑒􏷪 , 𝑒􏷫 , 𝑒􏷬 ) et de trois 0-cellules (𝑐􏷪 , 𝑐􏷫 , 𝑐􏷬 ). Les trois arcs sont les faces de 𝑓 et par définition, 𝑓 est une coface de 𝑒􏷪 , 𝑒􏷫 et 𝑒􏷬 . Ce complexe est décoré par des valeurs arbitraires (à droite) comme des coordonnées pour les points, des distances pour les arcs et une aire pour la surface. L’opération ensembliste union est naturellement étendue aux complexes cellulaires : soient 𝒦􏷪 = (𝑆􏷪 , ⪯􏷪 ) et 𝒦􏷫 = (𝑆􏷫 , ⪯􏷫 ) deux complexes cellulaires, 𝒦􏷪 ∪ 𝒦􏷫 = (𝑆􏷪 ∪ 𝑆􏷫 , ⪯􏷪 ∪ ⪯􏷫 ) si dim𝒦􏷪 et dim𝒦􏷫 coïncident sur 𝑆􏷪 ∩ 𝑆􏷫 . Définition 3.3.3. Soient 𝒦􏷪 = (𝑆􏷪 , ⪯􏷪 ) et 𝒦􏷫 = (𝑆􏷫 , ⪯􏷫 ) deux complexes cellulaires abstraits. On dit que 𝒦􏷫 est un sous-complexe de 𝒦􏷪 , noté 𝒦􏷫 ⊂ 𝒦􏷪 , si : 𝑆􏷫 ⊂ 𝑆􏷪 ⪯􏷫⊂⪯􏷪 et dim𝒦􏷪 coïncide avec dim𝒦􏷫 sur 𝑆􏷫 . Définition 3.3.4. Soit 𝒦 = (𝑆, ⪯) un complexe cellulaire abstrait et 𝜎 ∈ 𝒦 une cellule. L’ensemble des faces de 𝜎 est l’ensemble : {𝜏 ∈ 𝐾 ∣ 𝜏 ≺ 𝜎 ∧ dim(𝜏) = dim(𝜎) − 1} et 𝜎 est appelée la coface de 𝜏. 72 Chapitre 3. L’activité dans la programmation spatiale Nous définissons ci-dessous trois opérateurs (fermeture, étoile et liaison) sur les CCA utilisant la relation d’incidence ; ils sont extraits des travaux d’Axen [1]. La fermeture d’un CCA « sélectionne » toutes les cellules adjacentes de dimension inférieure, à l’inverse l’étoile d’un CCA « sélectionne » toutes les cellules adjacentes de dimension supérieure. L’opérateur liaison capture les cellules en lien avec les cellules d’un CCA soit par une cellule de dimension supérieure, soit par une cellule de dimension inférieure. La figure 3.2 présente une vue intuitive du fonctionnement de ces opérateurs. Les définitions suivantes les introduisent plus formellement. Définition 3.3.5. Soit 𝒦 un complexe cellulaire abstrait et 𝑆 ⊂ 𝒦 . On nomme fermeture de 𝑆 et on note 𝑆 l’ensemble {𝜎 ∈ 𝒦 ∣ ∃𝜏 ∈ 𝑆, 𝜎 ⪯ 𝜏}. Symétriquement, on nomme étoile de 𝑆 ⊂ 𝒦 l’ensemble {𝜎 ∈ 𝒦 ∣ ∃𝜏 ∈ 𝑆, 𝜏 ⪯ 𝜎}. On note la fermeture de l’étoile St 𝑆 = St 𝑆. Définition 3.3.6. Soit 𝒦 un complexe cellulaire abstrait et 𝑆 ⊂ 𝒦 . L’opérateur de liaison (Link en anglais et noté par conséquent Lk dans les travaux de [1]) est défini ainsi : Lk 𝑆 = St 𝑆 − St 𝑆, où − est l’opérateur de soustraction classique de la théorie des ensembles. 3.4 MGS : un langage dédié à la modélisation et à la simulation des (DS) 􏷡 MGS est un langage dédié à la modélisation et à la simulation des (DS) 􏷫 . C’est un langage de programmation spatial : un calcul consiste en un déplacement, induit par la relation de voisinage, dans l’espace abstrait de la structure de donnée (appelée collection topologique) et aussi en une action sur cette structure (appelée transformation) dépendant du calcul. Dans ce but, MGS embarque les concept de collection topologique et de transformation dans le framework d’un langage dynamiquement typé1 et fonctionnel2 . Les collections topologiques sont les seules structures de données disponibles dans le langage, c’est à dire qu’il n’existe pas d’autre manière d’agréger des données par rapport à une certaine relation de voisinage dans MGS. Les transformations, définies par une syntaxe spécifique à base de règles de réécriture, sont des fonctions définies par cas agissant sur ces collections. 3.4.1 Topologie des interactions Pour décrire l’évolution spatiale d’un processus, d’un élément ou d’une sous-partie d’un système, il existe deux alternatives classiques : un point de vue spatial, dans lequel on considère ces mouvements par rapport à un espace préexistant, fixé. Dans le cas d’un système proie-prédateur par exemple, chaque 1. Dans notre contexte, dynamiquement typé signifie qu’il n’y a pas de vérification statique des types et que les erreurs de type sont détectées pendant l’exécution lors de l’évaluation d’une expression. 2. MGS est un langage de programmation applicatif : les opérateurs combinent les valeurs sur lesquels ils s’appliquent pour donner des nouvelles valeurs, ils ne produisent pas d’effet de bord. 3.4. MGS et (DS) 􏷫 73 𝑆 𝑆 St 𝑆 St 𝑆 St 𝑆 Lk 𝑆 St ␣ ␣ St ␣ ␣ ␣ − ␣ Fig. 3.2: Construction de la liaison (à droite) d’un sous-complexe 𝑆 ⊂ 𝒦 (à gauche). En passant par le haut, on applique successivement l’opérateur fermeture suivi d’étoile, en passant par le bas c’est d’abord étoile suivi de fermeture. La liaison de 𝑆, Lk 𝑆, s’obtient par la différence entre St 𝑆 et St 𝑆. position de l’espace peut-être occupée soit par une proie, soit par un prédateur, soit vide ; un point de vue agent, focalisé sur l’individu. Ce dernier émet et reçoit des messages d’autres agents pour interagir avec son environnement. Cependant, ni l’un ni l’autre de ces points de vue n’est satisfaisant essentiellement parce qu’ils se concentrent chacun sur l’évolution locale d’une unique entité. Par exemple, dans le cas d’un problème de collision de particules dans un automate cellulaire un choix se fait entre une évolution en deux étapes [28] (propagation et collision) et l’utilisation d’un gaz sur réseau [5], une variante d’automate cellulaire qui considère une évolution couplée de plusieurs cellules. Du point de vue agent, le problème de synchronisation entre plusieurs agents amène aussi au développement de stratégies plus flexibles [17, 18, 19]. Le parti pris dans MGS est de dépasser ces deux points de vue en se recentrant sur ce qui créée la dynamique d’un système : les interactions entre entités (qu’ils soient agents ou morceaux d’espace). Les interactions représentent l’évolution simultanée d’une sous-partie (souvent petite) des entités composant le système. Supposons maintenant qu’à chaque instant de l’évolution d’un (DS) 􏷫 , seules quelques entités interagissent entre elles. Isoler ces groupes d’éléments en interaction revient à partitionner le système en groupes d’interaction unitaires (ou atomes) n’étant pas en relation entre eux à l’instant courant comme illustré par la figure 3.3. Cette partition forme un treillis d’atomes qu’il est possible et intéressant de voir comme une topologie : c’est la topologie des interactions [7, 8].