\chapter{L'activité dans la programmation spatiale}\label{chap:partie-activite} \minitoc \section{Introduction} Nous commencerons cette partie en introduisant la notion d'activité, ses origines et son rapport à la modélisation multi-niveau. Après une partie concernant \mgs{} et le formalisme qui lui est associé, nous aborderons ses liens avec l'\emph{activité}. Il apparaît que cette notion est intimement liée à la vision de l'espace que promeut le projet \mgs{} et ainsi, notre exploration mettra en évidence des résultats à la fois formels et pratiques. \section{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 \cite{tocher_art_1967} ; 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 \cite{muzy_refounding_2013} fait la synthèse des différents domaines et propose une définition de l'activité dans chacun de ces contextes. \paragraph{Activité en simulation} \begin{quote} 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). \hfill\textbf{Muzy et al.}~\cite{muzy_refounding_2013} \end{quote} % Une \emph{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 \emph{évènement} est ce qui change l'état d'un système (éventuellement composé de nombreux composants). Pour finir, on appelle un \emph{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é). \paragraph{Activité dans DEVS} Deux définitions de l'activité pour les systèmes à évènements discrets (Discrete-Event Systems ou DEVS) sont proposées : % \begin{itemize} \item L'activité \emph{qualitative} : un système est qualitativement inactif quand aucun évènement n'a lieu et est qualitativement actif sinon. \item L'activité \emph{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 (endogène ou exogène). L'\emph{activité quantitative interne} correspond au nombre d'évènements discrets internes, pendant un certain temps de simulation. L'\emph{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. \end{itemize} \paragraph{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 \emph{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 : % \begin{quote} […] 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.\\ \hfill\textbf{Muzy et al.}~\cite{muzy_refounding_2013} \end{quote} Un objet biologique est dit \emph{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. % La biologie, c'est le royaume des exemples. Avec ces deux définitions arrivent les problèmes de \emph{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$_2$ et de O$_2$ é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. \paragraph{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 : \begin{itemize} \item 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 (\emph{substantive rationality}), soit en groupe après délibération (\emph{procedural rationality}), en fonction de la valeur de gain liée à ce choix ; \item l'économie comportementale (\emph{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 (\emph{rule rationality}), un mode de comportement qui incorpore toutes les situations concernées par cette règle. \end{itemize} % On remarque que dans chacune de ces perspectives on \emph{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 \emph{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 \cite{muzy_refounding_2013}. \bigskip\noindent Pour conclure cette section sur l'activité, nous émettons les remarques suivantes: \begin{itemize} \item 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é ; \item La mesure d'activité donne une représentation abstraite du système étudié, une mesure agrégée qui \emph{appartient à un autre niveau de représentation que le système} lui-même. \end{itemize} 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. \section{Complexe cellulaire abstrait} \label{sec:cca} Les développements présentés dans la suite de ce chapitre reposent sur une classe d'objets mathématiques nommés \emph{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 \emph{cellules topologiques} dont l'assemblage combinatoire forme un \emph{complexe cellulaire abstrait} (\cca). Une \cell{p} est une cellule topologique de dimension $p$. Par exemple, les \cells{0} sont des points, les \cells{1} sont des arcs, les \cells{2} sont des surfaces, les \cells{3} des volumes, … Les cellules topologiques sont « jointes » par une relation appelée \emph{relation d'incidence}. Plus formellement, il s'ensuit les définitions correspondantes. % CCA \begin{mpo-definition} Soit $S$ un ensemble de symboles appelés \emph{cellules topologiques} muni d'un ordre partiel localement fini $\cdot\,\preceq\,\cdot \subset S \times S$ appelé \emph{relation d'incidence}. Le couple $\ccaK = (S, \preceq)$ est appelé \emph{complexe cellulaire abstrait}. \end{mpo-definition} % Dimension est une fonction monotone strictement croissante \begin{mpo-definition} Soit $\ccaK = (S, \preceq)$ un complexe cellulaire abstrait. La fonction $\ccad_{\ccaK} : S \rightarrow \mathbb{N}$ telle que pour $\sigma_1, \sigma_2 \in S,\:\sigma_1 \prec \sigma_2 \Rightarrow \ccad_{\ccaK}(\sigma_1) < \ccad_{\ccaK}(\sigma_2)$ est appelée fonction de \emph{dimension}. \end{mpo-definition} Dans la suite de ce manuscrit, on notera $\ccad$ au lieu de $\ccad_{\ccaK}$ quand il n'y a pas d'ambigüité sur \ccaK. De plus, on notera parfois $\sigma \in \ccaK$ au lieu de $\sigma \in S$. % Exemple \begin{figure}[h] \begin{center} \includegraphics{cc} \end{center} \caption{Diagramme de Hasse (à gauche) de la relation d'incidence dans le complexe cellulaire du milieu. Ce dernier est constitué d'une \cell{2} $f$, de trois \cells{1} ($e_1, e_2, e_3$) et de trois \cells{0} ($c_1, c_2, c_3$). Les trois arcs sont les faces de $f$ et par définition, $f$ est une coface de $e_1$, $e_2$ et $e_3$. 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.} \label{fig:cc} \end{figure} % Union L'opération ensembliste \emph{union} est naturellement étendue aux complexes cellulaires : soient $\ccaK_1 = (S_1, \preceq_1)$ et $\ccaK_2 = (S_2, \preceq_2)$ deux complexes cellulaires, $\ccaK_1 \cup \ccaK_2 = (S_1 \cup S_2, \preceq_1 \cup \preceq_2)$ si $\ccad_{\ccaK_1}$ et $\ccad_{\ccaK_2}$ coïncident sur $S_1 \cap S_2$. % Sous-complexe \begin{mpo-definition} Soient $\ccaK_1 = (S_1, \preceq_1) $ et $\ccaK_2 = (S_2, \preceq_2)$ deux complexes cellulaires abstraits. On dit que $\ccaK_2$ est un sous-complexe de $\ccaK_1$, noté $\ccaK_2 \subset \ccaK_1$, si : \begin{itemize} \item $S_2 \subset S_1$ \item $\preceq_2 \subset \preceq_1$ et \item $\ccad_{\ccaK_1}$ coïncide avec $\ccad_{\ccaK_2}$ sur $S_2$. \end{itemize} \end{mpo-definition} % Face coface \begin{mpo-definition} Soit $\ccaK = (S, \preceq)$ un complexe cellulaire abstrait et $\sigma \in \ccaK$ une cellule. L'ensemble des \emph{faces} de $\sigma$ est l'ensemble : \begin{equation*} \left\{ \tau \in K \mid \tau \prec \sigma \wedge \ccad(\tau) = \ccad(\sigma) - 1 \right\} \end{equation*} et $\sigma$ est appelée la \emph{coface} de $\tau$. \end{mpo-definition} 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~\cite{axen_topological_1998}. 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~\ref{fig:operateurs} présente une vue intuitive du fonctionnement de ces opérateurs. Les définitions suivantes les introduisent plus formellement. % Fermeture et étoile \begin{mpo-definition} Soit $\ccaK$ un complexe cellulaire abstrait et $S \subset \ccaK$. On nomme \emph{fermeture} de $S$ et on note $\fermeture{S}$ l'ensemble $\left\{ \sigma \in \ccaK \mid \exists \tau \in S,\: \sigma \preceq \tau \right\}$. Symétriquement, on nomme \emph{étoile} de $S \subset \ccaK$ l'ensemble $\left\{ \sigma \in \ccaK \mid \exists \tau \in S,\: \tau \preceq \sigma \right\}$. On note la fermeture de l'étoile $\fermeture{\etoile{}} S = \fermeture{\etoile{S}}$. \end{mpo-definition} % Link de Axen \begin{mpo-definition} Soit $\ccaK$ un complexe cellulaire abstrait et $S \subset \ccaK$. L'opérateur de \emph{liaison} (\emph{Link} en anglais et noté par conséquent $\liaison{}$ dans les travaux de~\cite{axen_topological_1998}) est défini ainsi : $\liaison{S} = \fermeture{\etoile{S}} - \etoile{\fermeture{S}}$, où $-$ est l'opérateur de soustraction classique de la théorie des ensembles. \end{mpo-definition} % % \begin{figure} \centerline{% \includegraphics[width=19cm]{link}} \caption{Construction de la liaison (à droite) d'un sous-complexe $S \subset \ccaK$ (à 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 $S$, $\liaison{S}$, s'obtient par la différence entre $\fermeture{\etoile{S}}$ et $\etoile{\fermeture{S}}$.} \label{fig:operateurs} \end{figure} % \section[\mgs{} et \dsds]{\mgs{} : un langage dédié à la modélisation et à la simulation des \dsds} \MGS{} est un langage dédié à la modélisation et à la simulation des \dsds. 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 \emph{collection topologique}) et aussi en une action sur cette structure (appelée \emph{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é\footnote{Dans notre contexte, \emph{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.} et fonctionnel\footnote{\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.}. 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. \subsection{Topologie des interactions} %Point de vue agent ou point de vue spatial 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 : \begin{itemize} \item 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 position de l'espace peut-être occupée soit par une proie, soit par un prédateur, soit vide ; \item 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. \end{itemize} % 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~\cite{toffoli_cellular_1987} (propagation et collision) et l'utilisation d'un gaz sur réseau~\cite{chopard_cellular_1998}, 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~\cite{% kubera_interaction-oriented_2008,mamei_field-based_2006,mamei_co-fields:_2003}. 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 \emph{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 \dsds, 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 \emph{à l'instant courant} comme illustré par la figure~\ref{fig:topo-interactions}. Cette partition forme un treillis d'atomes qu'il est possible et intéressant de voir comme une topologie : c'est la \emph{topologie des interactions}~\cite{giavitto_data_2002, giavitto_computations_2005}. Ce point de vue est incarné par les collections topologiques de \mgs. \begin{figure}[ht] \begin{center} \includegraphics{ds2} \end{center} \caption{Les partitions successives du système $S$ forment une topologie, c'est la topologie des interactions} \label{fig:topo-interactions} \end{figure} % \subsection{Collections topologiques} Une collection topologique est une \emph{structure de données générique} se fondant sur la topologie des interactions. Dans le paradigme adopté par \mgs, l'espace où évolue un phénomène, l'espace de modélisation, est spécifié à partir des interactions possibles entre les composantes du système à modéliser. Le fondement formel des collections topologiques est un objet mathématique appelé \emph{complexe cellulaire abstrait}~\cite{giavitto_computations_2005}, introduit dans la section~\ref{sec:cca}. Présentons d'abord quelques structures de données habituelles et leur implémentation sur des complexes cellulaires abstraits. \paragraph{Tableau} Un tableau est un ensemble compact de cases accolées les unes aux autres par un de leur bord. En 1D un tableau $t$ est définit par sa longueur $n$ et on le note par conséquent $t[n]$. À l'instar du modèle mémoire du langage C, un tableau est une sous-partie de la \emph{mémoire}. La structure de la mémoire peut être représentée par un complexe cellulaire constitué d'un nombre non borné de cellules où chaque «case» est une \cell{0} $\forall i \in \mathbb{N}\; c_i$. Nous représenterons le fait que deux \cells{0} $(c_i,c_{i+1})$ soient voisines par une \cell{1} $d_{i,i+1}$ de sorte que $\forall i \in \mathbb{N}\; c_i \preceq d_{i,i+1}$ et $c_{i+1} \preceq d_{i,i+i}$. Un tableau est une sous-partie de la mémoire où des \cells{0} consécutives sont décorées par $n$ valeurs différentes de la valeur spéciale \emph{null}. \noindent Dans \mgs, cette structure de donnée est directement disponible sous le type \ç|'array|. La syntaxe pour construire un tableau de trois cases contenant les valeurs $1,2,3$ est \begin{MGScode} 1, 2, 3, ():'array \end{MGScode} \paragraph{Liste} Une liste chaînée est une autre structure de données apparemment proche des tableaux où chaque élément d'une liste a soit un élément successeur, soit \emph{n'en a pas}. Cette structure de données peut être représentée par un complexe cellulaire abstrait où chaque élément $i$ est une \cell{0} $c_i$. Nous représenterons le fait que deux cellules $(c_i,c_j)$ soient voisines par une \cell{1} $d_{i,j}$ de sorte que $c_i \preceq d_{i,j}$ et $c_j \preceq d_{i,j}$. Dans \mgs, cette structure de donnée est appelée séquence, son type est \ç|'seq|. La syntaxe pour construire une séquence de trois éléments de valeurs $1,2,3$ est \begin{MGScode} 1, 2, 3, ():'seq \end{MGScode} La différence fondamentale entre liste et tableau tient au fait qu'il n'est pas possible de retirer une case dans un tableau : sa structure est fixée, seules ses valeurs peuvent être changées. Ces deux structures de données ont la même représentation structurelle mais leur comportement diffère quant à la sémantique de l'ajout et du retrait de valeurs décorant les cellules du complexe sous-jacent. Cette remarque prendra du sens dans la section~\ref{sec:transformations} consacrée aux transformations. \paragraph{\gbf} Les \emph{Group-Based Field} (\gbf) \cite{giavitto_group-based_1996, spicher_topological_2004} sont une collection topologique fondée sur les graphes de Cayley, des graphes qui encodent la structure d'un groupe. Plus particulièrement, les \gbf{} sont issus de graphes de Cayley de groupes Abélien, car ils ont un structure de grille. En pratique, ils représentent les espaces où les déplacements sont commutatifs comme les grilles carrées ou hexagonales où chaque générateur de la présentation d'un groupe indique une direction. La syntaxe \mgs{} pour construire une collection de type \ç|'gbf| représentant une grille hexagonale est \begin{MGScode} gbf hexa = < a, b, c | a + b = c > \end{MGScode} La collection \ç|hexa| possède trois opérateurs de voisinage notés \ç+|a>+, \ç+|b>+ et \ç+|c>+, ainsi que leurs opposés \ç+ expression_1; [...] motif_i => expression_i; [...] motif_n => expression_n; } \end{MGScode} À chaque motif de filtrage \ç|motif_i| correspond son expression \ç|expression_i| qui sera évaluée, puis «recollée» dans la collection topologique d'entrée. Un motif de filtrage prend la forme d'une succession d'éléments séparés par l'opérateur de voisinage « \ç|,| », dont la sémantique est la même \emph{quelle que soit la collection}. Le temps du modèle est déterminé par l'ordre et les conditions d'application des règles données dans une transformation. Est-ce que les motifs doivent être filtrés successivement (temps asynchrone), simultanément (temps synchrone) ou de manière probabiliste? Le modèle détermine quelle stratégie adopter. Il existe dans \mgs{} différentes \emph{stratégies} d'application des règles, dont les suivantes ont été utilisées dans nos travaux: \begin{itemize} \item \ç|`default| (Maximal-Parallel): les règles sont appliquées successivement jusqu'à ce que cela ne soit plus possible; \item \ç|`asynchronous| (Asynchrone ou Séquentielle): simule une évolution asynchrone, une seule règle est appliquée une fois, et l'ordre des règles fixe la priorité; \item \ç|`gillespie| (Gillespie): chaque règle décrit une réaction et se voit accorder une constante de réaction, par exemple $C = \num{0.01}$, \begin{MGScode} motif_i ={ C = 0.01 }=> expression_i; \end{MGScode} et est appliquée en fonction de cette constante en suivant la méthode de calcul stochastique proposée par Gillespie~\cite{gillespie_exact_1977}. \end{itemize} \noindent Comme pour la section précédente, cette courte présentation est fournie pour donner au lecteur une intuition sur le fonctionnement des transformations topologiques. Dans le reste du chapitre, un certain nombre d'exemples plus complets seront fournis. Le manuscrit~\cite{spicher_transformation_2006} traite en détail du sujet. \section{L'activité dans \mgs} \label{sec:activity}% Nous nous intéressons au concept d'\emph{activité} dans \mgs. Comme nous l'avons vu dans la section \ref{sec:activity}, l'activité est une mesure du nombre d'évènements ou de changement d'état dans une simulation. Cette mesure peut être utilisée pour différents objectifs, comme optimiser une simulation ou bien avoir une meilleur compréhension de sa dynamique. Dans le contexte de \mgs, l'activité nous permet \begin{enumerate} \item de développer un meilleur algorithme de filtrage par motifs et, \item d'identifier des structures d'ordre supérieur dans un modèle ainsi que de les suivre lors des simulations. \end{enumerate} Dans cette section nous présentons une méthode générique pour suivre une région active durant la simulation. Pour des raisons de simplicité, nous nous restreignons aux motifs ne comportant au maximum que deux éléments en interaction. Nous illustrons cette idée avec un exemple simple mais paradigmatique : un modèle de propagation de feu de forêt~\cite{potier_topological_2013} où le \emph{feu} se propage au travers d'une \emph{forêt} en laissant derrière lui de la matière calcinée sous la forme de \emph{cendres}. Ce modèle peut être décrit par un automate cellulaire à trois états que l'on peut aisément écrire dans une transformation \mgs: \begin{MGScode} trans fire_spread = { `Forest as x / member(`Fire, neighbors x) => `Fire; `Fire => `Ashes; } \end{MGScode} Les états sont représentés par trois symboles : \ç+`Forest+ pour la forêt, \ç+`Fire+ pour le feu et \ç+`Ashes+ pour les cendres. La première règle spécifie comment un élément de forêt prend feu avec pour voisin un élément de feu, la seconde règle spécifie comment un élément de feu s'éteint une fois la combustion terminée et devient un élément de cendre. La figure~\ref{fig:evolution} montre trois pas successifs de l'évolution de cet automate sur une collection topologique à grille carrée. % \begin{figure}[ht] \begin{center} \includegraphics[width=0.30\linewidth]{evolution01}\hfill \includegraphics[width=0.30\linewidth]{evolution02}\hfill \includegraphics[width=0.30\linewidth]{evolution03}\\ \begin{tikzpicture} \node[white] at (0,0) {.}; \node at (0.14\linewidth,0) {$C^0$}; \node at (0.50\linewidth,0) {$C^1=T(C^0)$}; \node at (0.84\linewidth,0) {$C^2=T(C^1)$}; \node[white] at (1.0\linewidth,0) {.}; \end{tikzpicture} \caption{Trois premiers pas de la simulation de la propagation d'un feu de forêt. Les cellules vertes (ou gris foncé) sont des cellules de forêt, les cellules oranges (hachurées) représentent le feu et les cellules foncées représentent les cendres.} \label{fig:evolution} \end{center} \end{figure} % Dans cet exemple, l'activité est située sur une sous-partie du domaine -- seuls les éléments de feu et leur cellules voisines évoluent -- et progresse de proche en proche. Néanmoins, l'algorithme de filtrage de motif de \mgs{} doit itérer sur toute la collection à chaque application de la transformation \ç+fire_spread+. %% Étant donné le faible nombre de cellules en interaction, le processus de filtrage est ici assez peu efficace. Par la suite, nous chercherons à cibler le filtrage sur les cellules qui évoluent grâce au mécanisme de filtrage. De plus, l'activité met en avant une structure de niveau supérieur importante de la propagation d'un feu de forêt: le \emph{front de propagation}. \paragraph{Activité et interactions} L'interprétation de l'activité dans \mgs{} correspond au nombre d'interactions ayant lieu à chaque pas de la simulation. Puisque les interactions arrivent à chaque fois qu'une règle de la transformation filtre une sous-collection, on constate que l'activité sépare naturellement une collection en deux parties : \begin{itemize} \item une sous-collection \emph{active} où une interaction peut avoir lieu et \item une sous-collection \emph{quiescente} où aucune interaction ne peut avoir lieu. \end{itemize} % Définissons les sous-collections actives et quiescentes d'une manière formelle et générale dans le cadre des collections topologiques. %% Soit $C$ un ensemble appelé collection topologique et $T$ une transformation. On définit la \emph{fonction de filtrage} $\mathbb{M}_T : C \rightarrow \mathcal{P}(C)$ de la transformation $T$ comme la fonction qui à $C$ fait correspondre l'ensemble des sous-collections de $C$ filtrées par un motif de $T$. En d'autres termes, la fonction de filtrage $\mathbb{M}_T$ représente un appel au processus de filtrage de motif. %% La \emph{sous-collection active} $A$ de $C$ est ainsi définie par % $$ A = \bigcup_{S\in \mathbb{M}_T(C)}{S} $$ % c'est à dire l'assemblage\footnote{L'opérateur $\bigcup$ est utilisé à la place de $+$ car certaines sous-collections filtrées par $\mathbb{M}_T$ peuvent avoir des supports qui se recouvrent.} de toutes les sous-collections filtrées de $C$. Ainsi, la \emph{sous-collection quiescente} $Q$ corresponds exactement au complémentaire de $A$ dans $C$ : % $$ Q = C\;\backslash\;A $$ % La figure~\ref{fig:assembly} montre la décomposition d'une collection en deux sous-collections actives et quiescentes dans le cas de l'exemple de propagation du feu de forêt. % \begin{figure}[ht] \begin{center} \includegraphics[width=0.30\linewidth]{assembly03}\hfill \includegraphics[width=0.30\linewidth]{assembly01}\hfill \includegraphics[width=0.30\linewidth]{assembly02}\\ \hspace{1cm}$C$\hfill $=$\hfill $A$\hfill $+$\hfill $Q$\hspace{1cm} \caption{Décomposition d'une collection topologique en deux ensembles de cellules actives et quiescentes. En vert (gris foncé), orange (hachuré) et foncé on représente la forêt, le feu et les cendres, respectivement.} \label{fig:assembly} \end{center} \end{figure} % \paragraph{Dynamique de l'activité} Afin de suivre une région active au cours de la simulation d'un modèle, nous définissons ci-après une manière de calculer l'évolution d'une région active (agrandissement, rétrécissement, creusement, \etc) reposant sur les propriétés topologiques de la sous-collection active. %% multiscale %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% La modélisation d'un système naturel implique souvent que des phénomènes apparaissent à des échelles temporelles et spatiales distinctes : chaque niveau est dédié à un phénomène se déroulant dans une fenêtre de temps et d'espace particulière. Ces échelles apparaissent pour des raisons logiques (à une certaine échelle, un système présente des propriétés uniformes et peut être modélisé par des règles homogènes agissant sur des objets pertinents à cette échelle) ou bien pour des raisons d'efficacité, par exemple la simulation réductionniste de l'intégralité du système à partir des premiers principes est difficile d'un point de vue calculatoire alors qu'une description plus grossière du modèle est bien souvent satisfaisante. % Les modèles et simulations à plusieurs échelles sont considérés lorsque des interactions apparaissent entre différentes échelles. Pour les échelles spatiales, on doit considérer simultanément plusieurs représentations spatiales comme dans le \emph{raffinement de maillage}~\cite{berger_adaptive_1984}. Cette méthode repose sur une séquence de « grilles rectangulaires entrelacées » sur lequel une \edp{} est discrétisée. Il est important de noter que ces sous grilles ne sont pas incorporées dans la grille principale mais superposées pour atteindre le but recherché. % Un autre exemple, dans le domaine de la modélisation discrète, est la classe \emph{automate complexe}~\cite{hoekstra_towards_2007} qui correspond à un « graphe d'automates cellulaires ». Considérons $(C^0,C^1,\dots)$ la trajectoire des collections par l'application successive de la transformations $T$, où $C^{i+1} = T(C^i)$ pour $i \ge 0$. %% En utilisant la décomposition active-quiescente sur $C^i=A^i+Q^i$, on peut remarquer que l'application de la transformation agit seulement sur la partie active et épargne $Q^i$ de telle sorte que le filtrage de motif peut n'être utilisé que sur $A^i$ : \begin{equation} \label{eq:app1} C^{i+1}=T(C^i)=T(A^i \mid F^i)+Q^i \end{equation} La notation $T(A^i \mid F^i)$ est introduite pour indiquer que le mécanisme de filtrage pourrait nécessiter des informations de $Q^i$, dans le cas où il est nécessaire de visiter le voisin d'un élément filtré. Par exemple, dans la précédente transformation \ç+fire_spread+, \ç+member(`Fire, neighbors x)+ n'implique pas que les voisins visités sont dans $A^i$. % Cette information, notée $F^i$, correspond à la sous-collection dont le support est constitué de tous les éléments de $Q^i$ ayant un voisin dans $A^i$ : \begin{equation*} F^i = \Lk\,A^i \end{equation*} % L'opérateur \emph{link} $\Lk$ sélectionne par construction l'ensemble de toutes les cellules voisines d'une cellule quelconque $\sigma$. Nous utilisons ici son extension naturelle à l'ensemble des cellules actives. La figure~\ref{fig:lk} montre un exemple d'application de $\Lk$ sur un complexe cellulaire. % \begin{figure}[h] \begin{center} {\hfill \includegraphics[width=0.30\linewidth]{s}\hfill \includegraphics[width=0.30\linewidth]{lks}\hfill} \caption{Application de l'opérateur $\Lk$ (droite) sur un complexe cellulaire de dimension 2 (gauche).} \label{fig:lk} \end{center} \end{figure} % La décomposition de $C^{i+1}$ proposée dans l'équation (\ref{eq:app1}) ne coïncide pas à la définition de $A^{i+1}$ et $Q^{i+1}$. En fait, quelques cellules de $Q^{i}$ peuvent devenir actives et \emph{vice versa}. % Néanmoins, le comportement de la frontière active-quiescente au cours de la simulation peut être raffiné en utilisant la sous-collection $F^i$. En effet, en supposant que la règle de transformation n'implique au maximum que deux éléments voisins, une cellule quiescente, à une certaine itération de la simulation, sans voisins appartenant à la sous-collection active aura un environnement inchangé et par conséquent restera dans son état courant à l'itération suivante. Formellement, on a : % \begin{equation} \label{eq:ineq} Q^i-\Lk\,A^i\subset Q^{i+1}\qquad A^{i+1}\subset T(A^i \mid \Lk\,A^i)+\Lk\,A^i \end{equation} % La seconde inclusion est obtenue en utilisant la complémentarité et signifie de manière équivalente que la partie active ne peut grandir au delà de $F^i$. L'équation (\ref{eq:app1}) se réécrit donc \begin{equation} \label{eq:app2} C^{i+1}=\left[T(A^i \mid \Lk\,A^i)+\Lk\,A^i\right]+\left[Q^i-\Lk\,A^i\right] \end{equation} \paragraph{Un filtrage de motif optimisé} Considérant l'équation~(\ref{eq:ineq}), il est clair que l'équation~(\ref{eq:app2}) est une sur-approximation de la décomposition active-quiescente de $C^{i+1}$. En exemple, sur la figure~\ref{fig:wave}, les lignes en gras représentent la limite d'expansion de la partie active au prochain pas de simulation et certaines cellules de cette sous-collection deviennent quiescentes. %% Ces cellules peuvent être identifiées comme les cellules de $T(A^i \mid \Lk\,A^i)+\Lk\,A^i$ ne pouvant être impliquées dans aucune des interactions au pas $i+1$. Autrement dit, elles ne sont pas sélectionnées par le mécanisme de filtrage : \begin{equation*} \mathbb{M}_T(C^{i+1}) = \mathbb{M}_T(T(A^i \mid \Lk\,A^i)+\Lk\,A^i) \end{equation*} et le calcul de la séquence $(A^i)_{i\in\N}$ suit \begin{equation*} \left\{ \begin{array}{lll} A^{0} & = & \bigcup_{S\in \mathbb{M}_T(C^{0})}{S}\\ A^{i+1} & = & \bigcup_{S\in \mathbb{M}_T(T(A^i \mid \Lk\,A^i)+\Lk\,A^i)}{S} \end{array} \right. \end{equation*} Il est important de noter que cette définition de $A^i$ ne se réfère aucunement à la sous-collection quiescente $Q^i$, car l'opérateur de voisinage $\Lk$ sélectionne exactement les cellules nécessaires. En conséquence, suivre l'activité durant la simulation nous permet de nous concentrer sur une partie réduite de la collection lors du filtrage. L'optimisation induite est discutée et illustrée dans les deux parties suivantes sur des exemples plus complexes. % \begin{figure}[h] \begin{center} \includegraphics[width=0.30\linewidth]{wave01}\hfill \includegraphics[width=0.30\linewidth]{wave02}\hfill \includegraphics[width=0.30\linewidth]{wave03} \caption{Évolution de la frontière active-quiecsente pour les trois pas de la figure~\protect\ref{fig:evolution}. Les cellules actives sont en rouge (gris foncé), les cellules quiescentes en bleu clair (hachuré). Les lignes en gras représentent la décomposition induite par l'équation~(\protect\ref{eq:app2}).} \label{fig:wave} \end{center} \end{figure} % \paragraph{Caractérisation topologique} \label{sec:morse} L'étude précédente peut être généralisée aux transformations impliquant plus de deux éléments en interaction en reconsidérant la distance à laquelle la sous-collection active peut s'étendre à chaque itération de la simulation. %% Soit $r$ le \emph{rayon} d'interaction, \ie\ la distance minimale (en terme de saut) entre éléments en interaction. La restriction précédente consistait à considérer les transformations de rayon $r = 1$; considérons maintenant un rayon arbitraire $r \in \N$. L'expansion de $F_r^i$ de $A^i$ pour un rayon $r$ est donnée récursivement par \begin{equation*} \left\{ \begin{array}{lll} F_0^i & = & 0\\ F_{r+1}^i & = & \Lk(A^i + F_{r}^i) + F_{r}^i \end{array} \right. \end{equation*} % Cette définition est analogue à la définition de l'\emph{opérateur de vague} $W(n)$ dans~\cite{axen_topological_1998} et révèle la nature topologique de l'activité. L'opérateur de vague est utilisé pour l'élaboration d'une théorie de Morse combinatoire. La théorie de Morse est un outil mathématique pour étudier la topologie des espaces. Brièvement, cette théorie traite des \emph{fonctions de Morse} -- une manière d'inonder l'espace avec un « liquide » -- et des \emph{points critiques} -- où le liquide révèle des bassins, des cols, des îles dans la topographie de l'espace. \section{Propagation d'un feu de forêt} \label{sec:fire} Dans cette section, nous illustrons les notions de collection topologique et de transformation sur l'exemple paradigmatique de la propagation d'un feu de forêt. \subsection{Un exemple canonique} Les incendies forestiers présentent des effets négatifs pour l'environnement. D'après l'organisation des nations unies pour l'alimentation et l'agriculture\footnote{\url{http://www.fao.org/news/story/fr/item/29097/icode/}}, \begin{quote} […] la destruction du couvert végétal par les incendies incontrôlés aggrave à la fois le réchauffement climatique, la pollution de l'air, la désertification et la perte de biodiversité. \end{quote} Ces effets nocifs incitent à développer les techniques de lutte contre les incendies ainsi que leur gestion~\cite{good_challenges_1989}. De nombreux modèles compliqués ont été établi dans le but de simuler la propagation d'un feu de forêt en temps réel comme~\cite{hu_devs-fire:_2011,ntaimo_devs-fire:_2008}. Ces modèles incluent des fonctionnalités supplémentaires comme un \emph{système d'information géographique}~\cite{wagner_single-pulse_2004}, \ldots De plus, d'après~\cite{karafyllidis_model_1997}, il existe différent types de modèle pour la propagation d'un feu de forêt, fondés soit sur la théorie des probabilités~\cite{ivanilova_set_1985}, sur une extension d'un modèle stochastique~\cite{hirabayashi_fire-spread_1988}, sur le principe de Huygens~\cite{beer_australian_1989} ou encore sur la simulation de l'écoulement d'un fluide~\cite{delemont_application_2007,tieszen_fluid_2001}. Remarquons que ces modèles sont soit imprécis soit trop consommateur en ressources~\cite{bardley_difficulties_1993}. De plus, aucun de ces modèle ne prend en compte l'intégralité des facteurs affectant la propagation d'un feu de forêt. Afin de représenter l'activité spatiale dans un cadre un plus concret que l'exemple ad hoc précédent, nous avons implémenté un modèle simple, efficace et réaliste pour la propagation d'un feu de forêt utilisant le formalisme des automates cellulaires (\AC)~\cite{karafyllidis_model_1997}, avec le langage de programmation \mgs. Notre modèle de propagation de feu de forêt prend en compte les principaux effets environnementaux, à savoir le vent (à la fois la force et la direction), le type de carburant et la topographie de la zone de propagation. Le \emph{front de l'incendie} est la zone séparant la forêt des cendres. Le principal objectif de notre modèle est de déterminer le prochain front de l'incendie en utilisant : \begin{itemize} \item le front de l'incendie actuel, \item la répartition des vitesses de propagation à chaque point de forêt, \item la force et la direction du vent ainsi que \item l'altitude de chaque point de la zone de propagation. \end{itemize} \subsubsection{Représentation des états avec \MGS} \begin{figure} \begin{center} \includegraphics{gbf} \vspace{-5mm} \end{center} \caption{Un \gbf\ définissant un voisinage de Moore, avec quatre générateurs \GBF{e}, \GBF{n}, \GBF{ne} et \GBF{se} et deux contraintes $\GBF{n} + \GBF{e} = \GBF{ne}$, $\GBF{e} - \GBF{n} = \GBF{se}$. Les directions $\GBF{w}$, $\GBF{s}$, $\GBF{sw}$ et $\GBF{nw}$ sont définies comme les inverses des générateurs.} \label{fig:grids} \end{figure} Chaque configuration de l'\ac\ est représenté par une collection topologique de type \gbf\ de \mgs{} avec un voisinage de Moore. Par exemple, afin de définir une grille avec un voisinage de Moore, on utilise quatre générateurs nord (\GBF{n}), est (\GBF{e}), nord est (\GBF{ne}) et sud est (\GBF{se}): \begin{MGScode} gbf Land = < n, ne, e, se ; 100 n = 0, 100 e = 0, ne = e + n, se = e - n > ;; \end{MGScode} Les générateurs \verb$s = ( let b = neighborsfold_indexed((\p,y,acc.( x.burning_rate * distance_effect(p,^x) * wind_effect(p,^x) * slope_effect(y,x) * y.burnt + acc )),x.burnt,x) in x + { burnt = min(1.0,b) } ); } ;; \end{MGScode} L'extrait de code précédent présente une transformation \mgs{} constitué d'une unique règle de réécriture pour mettre à jour l'état de chaque cellule. La fonction \ç|neighborsfold_indexed| est une fonction \ç|fold| classique conçue pour itérer sur chaque voisin d'une cellule. Elle prend en entrée une fonction à trois paramètres, qui sont \ç|p| la position de la cellule voisine, sa valeur \ç|y| et un accumulateur \ç|acc| des valeurs déjà réduites. Ainsi, cette simple fonction de transition itère sur chaque cellule en mettant à jour l'avancée de la combustion à chaque fois en prenant en compte l'effet de la distance aux voisins, la force et la direction du vent et l'altitude des voisins. Aussi, de part leur plus grande distance, les cellules en diagonale ont un effet moins conséquent sur leurs voisines, limité à 83\% (voir~\cite{karafyllidis_model_1997}). \subsection{Description de la propagation d'un feu de forêt du point de vue de l'activité} Nous avons réécrit l'exemple précédent afin que le mécanisme de filtrage ne s'applique que dans la zone active. En accord avec l'approche théorique présentée un peu plus tôt, l'espace des cellules de l'\ac\ est partagé entre les cellules actives qui prennent part à l'évolution de leurs voisines et les cellules quiescentes ne jouant aucun rôle à l'itération courante. Comme présenté à la fin de la section~\ref{sec:activity}, l'activité se propage comme une vague, à l'instar du feu de forêt. \begin{figure}[ht] \begin{center} \includegraphics[width=.3\linewidth]{fire-normal05} \includegraphics[width=.3\linewidth]{fire-normal22} \includegraphics[width=.3\linewidth]{fire-normal95} \\[1ex] \includegraphics[width=.3\linewidth]{fire-active05} \includegraphics[width=.3\linewidth]{fire-active22} \includegraphics[width=.3\linewidth]{fire-active95} \caption{Propagation du feu présentée à 3 itérations différentes, de gauche à droite, dans une simulation où les cellules enflammées sont initialement au centre d'une grille de taille $50\times 50$. Dans la première série, les cellules de forêt sont en vert (gris clair), les cellules enflammées sont en orange (gris clair) et les cellules entièrement consumées sont en gris foncé. Dans la seconde série (bas) les cellules actives sont en rouge (gris clair) et les cellules quiescentes en bleu (gris foncé).} % \label{fig:fire-simu} \end{center} \end{figure} Nous avons développé un algorithme générique nous permettant de suivre la zone active, dans laquelle des changement arrivent, au cours de la simulation. Ce dernier est exécuté à chaque itération. Commençons par introduire quelques points de notation. L'ensemble $A$ est choisi pour garder la trace des cellules actives durant la simulation et nous noterons $A^i$ avec $i \in \{0,\ldots,n\}$ l'ensemble des cellules actives à l'itération $i$ de la simulation, $n$ étant le dernier pas de la simulation. Au départ, $A^0$ contient toutes les cellules. L'ensemble $Q$ contient toutes les cellules quiescentes et $Q^0 = \emptyset$. L'ensemble $F^i$ permet de suivre les cellules pouvant devenir actives à l'itération suivante et correspond exactement à notre définition précédente d'un front d'incendie. Au début de la simulation, $F^0 = \emptyset$. \paragraph{Mise à jour de l'état des cellules} La première partie de l'algorithme concerne la mise à jour des cellules actives. Elle résulte de l'application des règles d'une transformation $T$ sur les cellules de $A$ plutôt que sur toutes les cellules. Une fois effectuée, une nouvelle ségrégation entre cellule active et quiescente apparaît et doit être calculée : certaines cellules deviennent actives, d'autres deviennent quiescentes. \begin{algorithm} \ForAll(\tcp*[f]{Mise à jour de l'état de toutes les cellules actives}) {$px \in A^i$} { \eIf {$syn < i$}{ $x \gets state.(px).cur$\; }{ $x \gets state.(px).backup$\; } $state.(px) \gets \{cur=T(x), backup=state.(px).cur, syn=i\}$\; } \end{algorithm} \paragraph{Mise à jour de la zone active} Afin de trier entre cellules active et quiescentes, nous utilisons un prédicat d'activité $P$ pour déterminer quelles cellules sont actives, soit restant active dans $A^i$ ou devenant active dans $F^i$. % \begin{MGScode} fun P(state, px) = ( let x = state.(px).cur in (x.burnt != 1.0) && exists((\y.(y.cur.burnt != 0.0)), neighbors(state,px)) ) ;; \end{MGScode} % Dans un premier temps, on rempli un ensemble $FQ$ comme stockage temporaire. Les éléments de cet ensemble seront répartis, plus tard, soit dans $F^{i+1}$ soit dans $Q^{i+1}$. \begin{algorithm}[H] \ForAll(\tcp*[f]{Mise à jour de la zone active}) {$a \in A^i$} { \eIf {$P(a)$}{ $A^{i+1} \gets a$\; }{ $FQ \gets a$\; } } \ForAll {$f \in F^i$}{ \eIf {$P(f)$}{ $A^{i+1} \gets f$\; }{ $FQ \gets f$\; } } \ForAll {$q \in Q^i$}{ \eIf {$not(HasNeighbor(q,F^i))$}{ $Q^{i+1} \gets q$\; }{ $FQ \gets q$\; } } \end{algorithm} Les cellules qui, soit restent actives, soit le deviennent, sont stockées dans $A^{i+1}$. Toutes les autres sont quiescentes, si elles sont suffisamment distantes de la zone active, ou dans $F^{i+1}$, si elles ont un voisin dans $A^{i+1}$ car elles peuvent devenir actives à la prochaine itération. \begin{algorithm} \ForAll(\tcp*[f]{Séparation de FQ}) {$c \in FQ$} { \eIf {$HasNeighbor(c,A^{i+1})$}{ $F^{i+1} \gets c$\; }{ $Q^{i+1} \gets c$\; } } \end{algorithm} \subsection{Mesure de performance} \begin{figure}[ht] \begin{center} \includegraphics{plot-ff} \end{center} \caption{Nombre de cellules actives et temps de calcul pour l'algorithme classique et optimisé par itération sur une grille de taille 500 $\times$ 500. Les valeurs sont normalisées selon la taille totale (\num{250000} cellules) en ce qui concerne le nombre de cellules, et le temps moyen de calcul d'une simulation classique en ce qui concerne le temps de calcul.} \label{fig:fire-speedup} \end{figure} En utilisant l'algorithme de filtrage de motif classique, l'intégralité de la collection doit être itérée à chaque mise à jour. Pour un \ac\ sur une grille carrée de côté $n$, l'algorithme doit parcourir $n^2$ cellules ce qui résulte en un pas d'itération en temps constant (voir figure~\ref{fig:fire-speedup}), tandis que seul un nombre fluctuant de cellules voient leur état changer (ce qui correspond à une fraction de la grille). Dans cette section, nous utilisons l'activité pour réduire le coût du filtrage. Nous avons réécrit l'exemple de la propagation d'un feu de forêt précédent pour que le filtrage n'ait lieu que dans la région active en ignorant la région quiescente. À l'instar de la partie théorique de la section~\ref{sec:activity}, l'espace de l'\ac\ est scindé entre cellules actives prenant part à la transformation de leurs voisines et cellules quiescentes ne jouant aucun rôle dans l'itération courante. Il en résulte une amélioration notable du temps de calcul sur l'ensemble de la simulation. La figure~\ref{fig:fire-speedup} montre le nombre de cellules actives à chaque itération ainsi que le temps de calcul par itération pour une simulation classique et optimisée. Le temps est normalisé par rapport au temps de calcul de la simulation classique de telle sorte qu'il soit aisé d'apprécier le gain induit par l'algorithme optimisé. Les pics et les fluctuations du temps de calcul proviennent de la variabilité des ressources disponibles lors du test. De la figure~\ref{fig:fire-simu}, on peut déduire qu'au début de la simulation, très peu de cellules sont actives. Leur nombre s'accroit dramatiquement avec la progression du feu pour ne diminuer qu'une fois la forêt consumée et transformée en cendres. % Pour l'\ac\, le temps de calcul est linéaire avec le nombre de cellules : plus il y a de cellules, plus le temps de calcul est élevé tout en restant constant par cellule. % De la figure précédente, on peut remarquer que le temps de calcul pour l'algorithme classique est le même à chaque itération : le mécanisme de filtrage doit explorer chacune des \num{250000} cellules pour vérifier si un motif peut s'appliquer ou non. Dans ce cas, qu'un motif corresponde ou non ne change pas le temps de calcul nécessaire à l'application d'une règle de transformation. On remarque également que le nombre de cellules actives et le temps de calcul de l'algorithme optimisé coïncident : ce dernier dépend effectivement du nombre de cellules à explorer, d'où le fait que la forme des deux courbes soit quasi identique. % Les cellules ne sont jamais toutes actives au même moment, c'est pourquoi, même quand un grand nombre de cellules sont actives, le temps de calcul par itération pour l'algorithme optimisé reste plus faible que pour sa contrepartie classique. % Le coût de la maintenance des ensembles des cellules actives et quiescentes peut se lire à partir de la différence entre le temps de calcul pour l'algorithme optimisé et le nombre de cellules actives. Cette optimisation dépend du problème étudié et le graphe en sortie est totalement dépendant de la configuration des données initiales. Ainsi, on ne peut pas parler en toute généralité d'une optimisation en temps de calcul. Le cas suivant donne des résultats sensiblement différents. \section{Agrégation limitée par diffusion} \label{sec:dla} Dans cette section, nous considérons un exemple plus élaboré : nous avons choisi d'implémenter le modèle d'un système présentant une \emph{agrégation limitée par diffusion} (\ald). Contrairement au modèle de propagation d'un feu de forêt, le modèle d'une \ald\ présente de réelles interactions entre deux particules au lieu du changement d'état d'une cellule en fonction de l'état de ses voisines. En \mgs, cela se traduit par le filtrage d'une paire de cellules au lieu d'un seule. Nous verrons néanmoins que cela n'affecte pas la propagation en vague de l'activité. % Les résultats suivants découlent de la section~\ref{sec:activity}, où apportée par l'activité est utilisée pour accélérer le temps de simulation en n'appliquant les règles de transformation \emph{qu'à la seule} région active. \subsection{L'exemple d'une simulation d'une \ald} Le phénomène d'\ald\ est un phénomène physique dans lequel on observe un ensemble de particules s'agrégeant pour former des arbres Brownien~\cite{witten_diffusion-limited_1981}. Un modèle de ce phénomène a été implémenté par~\cite{spicher_reactive_2009} sur un \ac{} avec \mgs{}. \subsubsection{Représentation des états avec \mgs} Le treillis régulier d'un \ac\ est représenté par un \gbf\ décrivant un voisinage de Moore sur une grille carrée cyclique en deux dimensions. En \mgs, cette collection est spécifiée à partir de la présentation du groupe des déplacements. Comme dans l'exemple précédent, la définition d'une grille au voisinage de Moore nécessite une base de quatre mouvements, nord (\GBF{n}), est (\GBF{e}), nord-est (\GBF{ne}) et sud-est (\GBF{se}) : \begin{MGScode} gbf Grid = < n, ne, e, se ; 50 n = 0, 50 e = 0, ne = e + n, se = e - n > ;; \end{MGScode} Les quatre équations additionnelles indiquent que la grille est cyclique et de taille $50\times 50$, et définit les relations entre les directions horizontale, verticale et diagonales tandis que les directions inverses sont générées automatiquement. Ensuite, chaque cellule du \gbf\ est étiqueté par son état, qui varie au cours des itérations de la simulation: \begin{MGScode} type cell = `empty | `mobile | `static ;; \end{MGScode} L'étiquette \ç+`mobile+ désigne une cellule contenant une particule pouvant se déplacer dans une direction aléatoire à l'itération suivante ; l'étiquette \ç+`static+ est utilisée pour les cellules contenant une particule qui restera fixe jusqu'à la fin de la simulation. Finalement l'étiquette \ç+`empty+ est utilisée pour les cellules vides, ne contenant aucune particule, et pouvant accueillir une particule à l'itération suivante. \subsubsection{Spécification dynamique en \mgs} Spécifier la dynamique d'une \ald\ dans une transformation revient à rédiger deux règles appliquées suivant une stratégie \emph{maximal-parallel}: \label{mgs:ald-evol} \begin{MGScode} trans evolution = { `mobile, `static => `static, `static ; `mobile, `empty => `empty, `mobile ; } ;; \end{MGScode} La première règle de la transformation est sélectionnée si deux cellules voisines sont dans les états \ç+`mobile+ et \ç+`static+, et les remplace par deux cellules dont l'état est \ç+`static+. % La seconde règle de la transformation s'applique si deux cellules voisines sont dans les états \ç+`mobile+ et \ç+`empty+ auquel cas elles échangent leurs états pour simuler un \emph{saut} d'un particule de la première vers la seconde. % On remarque que la priorité est donnée à la règle d'agrégation ce qui permet à une cellule étiquetée \ç+`mobile+ entourée de plusieurs \ç+`empty+ et d'au moins une \ç+`static+ de devenir \ç+`static+ plutôt que de continuer sa marche aléatoire. % Cette fonction de transition itère sur toutes les cellules et mets à jour leur état. La figure~\ref{fig:dla-simu} présente la simulation du modèle à différentes itérations. % \begin{figure}[ht] \begin{center} \includegraphics[width=.3\linewidth]{dla-normal000} \includegraphics[width=.3\linewidth]{dla-normal110} \includegraphics[width=.3\linewidth]{dla-normal687} \\[1ex] \includegraphics[width=.3\linewidth]{dla-active000} \includegraphics[width=.3\linewidth]{dla-active110} \includegraphics[width=.3\linewidth]{dla-active687} \caption{\ald\ à trois itérations différentes, de gauche à droite, d'une simulation comportant des particules mobiles au centre et des particules statiques aux bords sur une grille de $50 \times 50$. Dans la série du haut, les cellules \ç+`mobile+ sont en rouge, les cellules \ç+`static+ sont en bleu et les \ç+`empty+ sont en blanc. Dans la série du bas, les cellules actives sont en rouge et les cellules quiescentes sont en bleu.} % \label{fig:dla-simu} \end{center} \end{figure} % \subsection{L'activité dans une simulation d'\ald} Comme on pourrait s'y attendre, la nature d'une simulation d'\ald\ est bien différente de l'exemple précédent. On décèle moins bien la vague d'activité que dans la propagation d'un feu de forêt. Néanmoins, les mêmes principes sont utilisés sur l'exemple de l'\ald\ et les résultats sont présentés juste après. L'algorithme utilisé pour suivre l'évolution de l'activité doit prendre en compte l'interaction entre deux cellules voisines : il doit d'abord en filtrer une puis une seconde dans le voisinage de la première. Le mécanisme de filtrage et de mise à jour de l'état d'une cellule est au cœur de l'algorithme de filtrage de motif de \mgs. Mis à part la mis à jour de l'état d'une cellule, le reste de la procédure est identique : il faut répartir les cellules itérées dans $A^{i+1}$, $F^{i+1}$ et $Q^{i+1}$. \subsection{Mesure de performance} \label{sec:dla-bench} Dans cette section, nous utilisons l'information fournie par l'activité pour réduire le coût du filtrage. L'exemple d'une \ald\ a été réécrit pour que les règles de la transformation ne s'appliquent qu'aux cellules des régions actives en omettant les cellules quiescentes. À l'instar du point de vue théorique présenté dans la section~\ref{sec:activity}, l'espace de l'\ac\ est partagé entre cellules actives prenant par à la transformation et cellules quiescentes ne jouant aucun rôle à l'itération courante. La simulation s'en retrouve accélérée, mais dans de moins larges proportions par rapport à l'exemple précédent. \begin{figure}[ht] \begin{center} %\includegraphics[width=\linewidth]{bench} {\scriptsize\input{data/bench.tex}} \caption{Nombre de cellules actives, et temps de calcul pour l'algorithme optimisé par itération sur une grille de 100 $\times$ 100. Les valeurs ont été normalisées en utilisant la taille totale de la grille (\num{10000} cellules) et le temps de calcul par itération pour l'algorithme classique respectivement.} \label{fig:dla-speedup} \end{center} \end{figure} La figure~\ref{fig:dla-speedup} présente un graphe du nombre de cellules actives pour chaque itération et le temps de calcul par itération pour l'algorithme optimisé. Les fluctuations occasionnelles sont causées par une variation des ressources disponibles dans l'environnement de test. Comme montré sur la figure~\ref{fig:dla-simu}, au début de la simulation, très peu de cellules sont actives ; il n'y a que la \emph{couronne} autour du carré initial de particules mobiles représentant les particules ayant la possibilité de bouger. Leur nombre croît dramatiquement avec la marche aléatoire des particules remplissant l'espace et décroît dès qu'une particule mobile s'attache à une particule fixe. Comme dans le cas d'un \ac\ classique, le temps de calcul est linéaire avec le nombre de cellules : plus leur nombre est important, plus le temps nécessaire au calcul est important par itération. De plus, le temps de calcul pour l'algorithme classique est quasiment identique à chaque itération : le mécanisme de filtrage doit parcourir l'ensemble des \num{10000} cellules pour vérifier si un motif convient. Le fait qu'une règle s'applique ou non ne change que marginalement le temps de calcul nécessaire par cellule. Du graphe, nous remarquons que l'activité et le temps de calcul pour l'algorithme optimisé coïncident : en effet ce dernier dépend de la taille de la région active. Il semble donc naturel que l'allure générale de la courbe soit identique à celle de la variation du nombre de cellules actives. Les cellules ne sont pas toutes actives au même moment. En fait, pour la simulation présentée, le nombre maximum de cellules actives est très faible et reste en dessous de 30\% du total. Par conséquent, même à son pic, l'algorithme optimisé requiert moins de temps de calcul par itération que l'algorithme classique. Le coût de la maintenance de la zone active peut être lu à partir de la différence entre le temps de calcul pour l'algorithme optimisé et le nombre de cellules actives. Dans notre cas, il est assez élevé, peut être parce que le mécanisme d'optimisation lié à l'activité a été implémenté comme un programme \mgs{} et n'est pas directement inclus dans le langage lui-même. Cette optimisation est dépendante des données, cela se voit en comparant les différences de résultats par rapport à l'exemple précédent. De manière générale, il n'y a aucune garantie de l'optimisation en temps des calculs mais il ne peut y avoir de ralentissement car le pire scénario revient à devoir filtrer entièrement une collection topologique et calculer les collections $A, F$ et $Q$, ce qui est le cas par défaut. Concernant l'\ald, l'accélération de la simulation est aussi dépendante du type d'implémentation ; dans le cas d'un modèle à agent, le suivi de l'activité nous a permis de nous focaliser sur les particules mobiles et ainsi d'obtenir un temps de simulation optimal. \section{Conclusion et perspectives} Cette courte section vise à rappeler les principaux résultats obtenus suite à nos travaux sur l'activité spatiale ainsi que nos futures pistes de travail sur le sujet. \subsection{Conclusion} % Rappel du contexte et des résultats obtenus Nous avons, dans ce chapitre, présenté quelques points clef du formalisme de \mgs, en particulier: les collections topologiques et les transformations. Nous avons aussi succinctement décrit deux modèles formels, les complexes cellulaires abstraits et la réécriture topologique, servant de fondement au langage. Nous avons d'abord utilisé un automate à trois états minimal pour introduire le concept d'activité (section~\ref{sec:activity}) dans le domaine du calcul spatial en définissant une zone active comme étant les régions de l'espace filtrées, et où seules les cellules filtrées sont mises à jour. Bien que ce concept ait été introduit sur un exemple de propagation de feu de forêt (section~\ref{sec:fire}), le fait que l'activité progresse comme une vague n'est pas restreint à ce seul cas et s'étend naturellement à d'autres cas comme le modèle d'agrégation limitée par diffusion (section~\ref{sec:dla}). La propagation d'un feu de forêt semble être un cas particulier où l'activité est en adéquation presque parfaite avec la simulation où la sur-approximation induite par le suivi de l'activité est minimale. \noindent De nos précédentes observations, nous avons obtenus deux résultats principaux: \begin{enumerate} \item un résultat formel: la description générique du calcul de la zone active, indépendamment de toute connaissance sur la zone quiescente, et \item un résultat expérimental: la mise à jour de la zone active uniquement nous a apporté un gain en vitesse d'exécution inversement proportionnel au nombre de cellules actives, pour les deux applications. \end{enumerate} Notre motivation à l'exploration de l'activité dépasse la simple optimisation de temps des simulations avec \mgs. Elle découle de notre approche de la modélisation multi-niveau que nous avons introduit dans le chapitre~\ref{chap:partie-multi-modele}. À ce stade de nos travaux, au niveau du langage, les zones actives ne sont pas des objets de première classe: elles sont calculées à chaque pas de la simulation et il n'existe pas encore de lien entre ces régions entre deux pas de simulation différents. Par cet aspect, l'activité trace un chemin vers une définition générique et une utilisation du \emph{front} actif, de la \emph{réification} des régions actives en des objets de première classe. Reformulé en terme d'identité, notre implémentation permet par identification qualitative de découvrir les zones actives, qui sont des objets d'un autre niveau de modélisation. L'identité numérique de ce front actif n'est pas encore inclus au niveau du langage. D'autres questions demandent à être abordées avant de pouvoir manipuler les zones actives comme des objets de premier ordre. Nous les présentons dans la section suivante. \subsection{Perspectives} Nos travaux futurs s'articulent autour des grands axes suivants, conditions nécessaires à la \emph{réification} des fronts de vague d'activité et à leur inclusion en tant qu'objets de première classe dans \mgs: \begin{description} \item[Identifier] Nous avons déjà établi qu'il était possible, sans modifier le langage, d'identifier la zone spatiale active dans une simulation \mgs: cette zone est décrite par les trois ensembles de cellules $A$, $Q$ et $F$. Notre prochaine étape est d'étendre les tests effectués sur des ensembles de cellules plus grands, d'une part, et sur des modèles implémentés sur d'autres collections topologiques, d'autre part, afin de confirmer nos observations. Schématiquement, en prenant $C_i$ comme la collection topologique au pas $i$ et $A_i$ comme l'ensemble des cellules actives au pas $i$, alors nous avons: \begin{center} \begin{tikzpicture} \node (ci) at (0,0) {$C_i$}; \node (ai) at (0,1) {$A_i$}; \draw[->] (ci) -- (ai); \end{tikzpicture} \end{center} De plus, nous nous posons la question de la structure de donnée la mieux adaptée à l'ensemble des cellules actives: est-ce la collection topologique du modèle ? Ou bien d'autres candidats sont-ils plus appropriés ? \item[Suivre] Nous avons également mis en œuvre un suivi rudimentaire de la zone active. Cependant, ce suivi n'existe pas encore du point de vue de \mgs. Aussi, il est nécessaire de déterminer une correspondance directe, à deux pas successifs $i$ et $i+1$ de la simulation, entre $A_i$ et $A_{i+1}$. Autrement dit, il nous faudrait établir une transformation agissant directement sur $A_i$, indépendamment du modèle sous-jacent. Prenons $C_i$ comme l'ensemble des cellules de la collection topologique du modèle au pas $i$ et $C_{i+1}$ au pas $i+1$, si le diagramme suivant commute, alors cette transformation est une abstraction: \begin{center} \begin{tikzpicture} \node (ci) at (0,0) {$C_i$}; \node (ai) at (0,1) {$A_i$}; \node (cip1) at (2,0) {$C_{i+1}$}; \node (aip1) at (2,1) {$A_{i+1}$}; \draw[->] (ci) -- (ai); \draw[->] (ci) -- (cip1); \draw[->] (ai) -- (aip1); \draw[->] (cip1) -- (aip1); \end{tikzpicture} \end{center} \item[Différencier] Nous avons constitué les ensembles $A$, $Q$ et $F$ à partir de l'intégralité des règles d'une transformation. Nous souhaitons enquêter sur le sens de la distinction entre différents sous-ensembles d'activité engendrés par une ou plusieurs règles d'une transformation. Par exemple, dans le cas de la transformation de l'\ald, page \pageref{mgs:ald-evol}, nous avions deux règles, la première décrivant la capture par accrétion d'une particule, et l'autre décrivant leur déplacement brownien. Quel serait le sens, l'usage, la portée et l'implémentation du front actif d'accrétion ou du front actif de déplacement ? Qu'en est-il de leurs interactions ? \end{description} Une fois les réponses à ces questions clarifiées, nous pourrons alors proposer une syntaxe spécifique à la manipulation des fronts de vague d'activité au niveau du langage \mgs. \noindent À l'avenir, il sera intéressant de préciser les relations entre le contexte original de l'opérateur de vague, emprunté à la théorie de Morse, et notre exploration de l'activité spatiale.