1438 lines
72 KiB
TeX
1438 lines
72 KiB
TeX
\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 \ç+<a|+, \ç+<b|+, \ç+<c|+. Nous
|
|
utiliserons cette collection plus tard dans le chapitre \ref{sec:fire} pour les
|
|
simulations de la propagation d'un feu de forêt.
|
|
|
|
\paragraph{Chaînes topologiques} La collection la plus générale de \mgs{} est la
|
|
\emph{chaîne topologique}, dans le sens où elle permet la manipulation plus
|
|
libre de la structure des collections topologiques. On définit une collection de
|
|
ce type en construisant un arbre de cellules, munies d'une valeur arbitraire,
|
|
reliées par leur incidence.
|
|
\begin{MGScode}
|
|
v1 := new_dvertex(`a) ;;
|
|
v2 := new_dvertex(`b) ;;
|
|
e1 := new_edge(v1,v2) ;;
|
|
\end{MGScode}
|
|
\ç|v1|, \ç|v2| et \ç|e1| sont trois valeurs de type \ç|`dcell| ; \ç|v1| et
|
|
\ç|v2| sont des \cells{0} et \ç|e1| est une \cell{1}.
|
|
|
|
\noindent
|
|
Ces quelques exemples permettent de se faire une première idée sur le
|
|
fonctionnement des collections topologiques et la manière dont elle sont
|
|
implémentées. Le lecteur intéressé par une présentation plus formelle pourra se
|
|
référer au manuscrit de thèse d'Antoine
|
|
Spicher~\cite{spicher_transformation_2006} traitant en détail du sujet.
|
|
|
|
\subsection{Transformations topologiques} \label{sec:transformations}%
|
|
Une transformation topologique est une fonction définie par cas sur les
|
|
collections topologiques: elle prend en argument une collection topologique et
|
|
retourne en sortie une collection topologique du même type en effectuant le
|
|
remplacement d'une sous-collection de la collection fournie en paramètre. Cette
|
|
opération, par analogie avec la réécriture de chaînes de caractère, est appelée
|
|
\emph{réécriture topologique} du fait que modifier une collection topologique
|
|
permet de modifier aussi bien les données que leur structure. La syntaxe d'une
|
|
transformation est
|
|
\begin{MGScode}
|
|
trans NomDeLaTransformation = {
|
|
motif_1 => 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 = <n|$, \verb$sw = <ne|$, \verb$w = <e|$ et
|
|
\verb$nw = <se|$ sont automatiquement définis car ils correspondent aux
|
|
déplacements inverses sur la présentation d'un groupe abélien.
|
|
|
|
On associe ensuite une valeur à chaque cellule d'un \gbf. Cette valeur est un
|
|
dictionnaire contenant l'avancée de sa combustion (une valeur réelle), la
|
|
direction du vent (un générateur de \gbf), la vitesse de combustion (une valeur
|
|
réelle) et l'altitude (une valeur entière) :
|
|
\begin{MGScode}
|
|
record cell = {
|
|
burned_out : float,
|
|
wind_direction : position,
|
|
burning_rate : float,
|
|
altitude : int
|
|
} ;;
|
|
\end{MGScode}
|
|
L'\emph{avancée de la combustion} correspond à la surface de la cellule déjà
|
|
consumée. Lorsque cette valeur atteint $1.0$, cela signifie que l'intégralité de
|
|
la cellule a été consumée et donc qu'elle est transformée en cendres.
|
|
|
|
Une cellule a sa propre vitesse de combustion qui peut être vue comme une mesure
|
|
agrégée des caractéristiques du carburant comme son type, sa densité, \etc.
|
|
L'effet de la vitesse de combustion est ensuite renforcé ou bien inhibé par
|
|
d'autres facteurs environnementaux. La \emph{direction du vent} et sa force
|
|
peuvent accentuer ou inhiber la propagation du feu en fonction de la position du
|
|
voisin et la direction du vent : si le voisin est dans la direction opposée au
|
|
vent alors la cellule brûlera plus vite, sinon si le voisin est dans la
|
|
direction du vent alors la cellule brûlera moins rapidement. Dans notre
|
|
simulation, le vent peut soit être fort (effet marqué) ou faible (effet plus
|
|
marginal). L'\emph{altitude} des voisins peut jouer un rôle similaire : si le
|
|
voisin est plus élevé alors son effet sur la vitesse du propagation du feu sera
|
|
inhibé alors que s'il est plus bas alors son effet sera accentué (le feu a
|
|
tendance à monter).
|
|
|
|
\subsubsection{Spécification dynamique en \MGS}
|
|
Voici la fonction de transition \mgs{} représentant l'évolution locale de chaque
|
|
cellule de l'\ac~:
|
|
\begin{MGScode} trans rules = {
|
|
|
|
x => (
|
|
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.
|
|
|