Nathan Itare
email: nathan.itare@univ-lemans.fr

Jean-Hugh Thomas
email: jean-hugh.thomas@univ-lemans.fr

Raoof Kosai
email: kosai.raoof@univ-lemans.fr

DOA estimation of an Unmanned Aerial Vehicle with few sensors in the case of disturbing sources

Keywords: Drones, Acoustic Source Localization, Beamforming, Microphone Array, Time-Frequency Representation

The increasing use of Unmanned Aerial Vehicles (UAVs) for several purposes can bring some concerns around sensitive sites. It is thus necessary to be able to locate drones when they become a threat. Thanks to many recent studies, the use of acoustical methods exploiting the sound emitted by UAVs enables to estimate the position or direction of the source. Sound produced by drones is still predominant and hence is a good way to compensate technological difficulties of other methods like optical, electromagnetic, or radar. Some sensitive sites could be situated around noisy environment where perturbing sources can be present. These perturbing sources can be produced by planes, cars, birds, etc. Experimental measurements have been conducted for this study to evaluate the performance of temporal beamforming coupling with the time-frequency representation of the focused signal. This enables us to take into account the UAV's acoustic signature. These measurements were carried out in an environment where some noise sources were present such as birds chirping and car passing. Beamforming with time-frequency representation has the advantage of providing a DOA estimation with only a few spectral contents considered, which can be particularly helpful in this kind of situations.

INTRODUCTION

During recent years, Unmanned Aerial Vehicles (UAVs) have been increasingly used to achieve various purposes. Among the multiple possible applications for these vehicles, some popular uses are: aerial filming, package deliveries, surveillance, inspection, and victim search and rescue. A recent study have shown several applications of UAV in the context of future smart cities [START_REF] Mohamed | Unmanned aerial vehicles applications in future smart cities[END_REF]. These smart cities will use emerging technologies like Internet of Things, robotics, and others to get a better management of their cities. In this study, the contribution of UAVs along these technologies is addressed as well as the possible challenges that could appear. Besides the numerous benefits of UAVs, their use can also be threats in lots of ways. There could be safety threats on sensitive sites like airports [START_REF] Nowacki | Challenges and threats of unmanned aerial vehicles for aviation transport safety[END_REF] where an UAV could collide with an airplane. Nuclear facilities are also concerned by safety and privacy threats [START_REF] Solodov | Analyzing the threat of unmanned aerial vehicles (UAV) to nuclear facilities[END_REF]. Two types of situations can occur with an UAVs' attack. In the first situation the drone is simply controlled by the pilot. But in the second situation, an ordinary flying UAV can be hacked and controlled by another pilot to perform an attack. In [START_REF] Mekdad | A Survey on Security and Privacy Issues of UAVs[END_REF], the second situation is addressed as well as other issues with UAVs' security and privacy issues. In order to react to these threatening behaviors, it is necessary to know the UAV's position or direction of arrival. Many methods exist and can be used either separately or simultaneously [START_REF] Technical Academy | A Study on the Methods and Technologies Used for Detection, Localization, and Tracking of LSS UASs[END_REF][START_REF] Park | Survey on Anti-Drone Systems: Components, Designs, and Challenges[END_REF]. Optical methods use cameras to detect and track a drone but can be limited by meteorological conditions [START_REF] Wang | Design of Airport Obstacle-Free Zone Monitoring UAV System Based on Computer Vision[END_REF]. Electromagnetic methods use the detection of signals exchanged between the UAV and the controller but are not usable with autonomous drones [START_REF] Medaiyese | Machine Learning Framework for RF-Based Drone Detection and Identification System[END_REF]. Sound emitted by UAVs can also be exploited by using a microphone antenna to obtain its direction of arrival (DOA) but these methods can be limited in noisy environment. A good way to enhance the possibility of locating a UAV is to combine multiple methods. In [START_REF] Bavu | Deeplomatics: A deep-learning based multimodal approach for aerial drone detection and localization[END_REF], an optronic system is combined with an acoustic system to perform the detection and the localization of drones using a deep learning approach. The work presented here will focus on an acoustic system to perform the UAV's direction of arrival estimation. Several studies have shown that UAVs produce a significant and particular noise [START_REF] Djurek | Analysis of a Quadcopter's Acoustic Signature in Different Flight Regimes[END_REF][START_REF] Kloet | Acoustic signature measurement of small multi-rotor unmanned aircraft systems[END_REF]. It is thus possible to use the acoustic signature to filter signals measured by a microphone array to enhance the DOA estimation [START_REF] Blanchard | Acoustic localization and tracking of a multi-rotor unmanned aerial vehicle using an array with few microphones[END_REF]. An alternative presented here uses a time-frequency representation of a beamformer's output to select time-frequency bins associated to the UAV [START_REF] Itare | Acoustic Estimation of the Direction of Arrival of an Unmanned Aerial Vehicle Based on Frequency Tracking in the Time-Frequency Plane[END_REF]. The aim of this work is to evaluate the performance of this process with perturbing sources like birds chirping or car passing.

The work is presented as follows: Part 2 presents Delay and Sum Beamforming and the use of the timefrequency representation approach. Part 3 describes the measurement set-up with the array geometry and the trajectories performed by the drone. Part 4 presents the results of DOA estimation for the situations considered. Part 5 conclude and presents some perspectives.

PRESENTATION OF THE DOA ESTIMATION METHODS

Delay and Sum Beamforming

Delay and Sum Beamforming (DSB) [START_REF] Van Veen | Beamforming: a versatile approach to spatial filtering[END_REF] is a well known method exploiting signals from a microphone array. Given the different positions of the microphones, the signal produced by the UAV will arrive at different times to the microphones. By realigning in time all these signals, it is possible to focus the signal in one direction. A reference microphone is chosen to calculate delays in regards to this reference. The 3D space is sampled with a spherical coordinate system, ϕ is the azimuth, θ is the elevation, and r is the distance between the origin and the source. In far field, a simplification can be made by considering a plane waveform. For this study, this plane wave model will be used which enables to search the source's DOA among the directions Ω = (ϕ, θ ). For one direction Ω, a set of delays is calculated and the focused signal is obtained by summing all the delayed signals. The DOA is given by the direction which gives the maximum energy of the focused signal.

Time-frequency Representation

In order to take into consideration the UAV's acoustic signature, the time-frequency representation (TFR) approach transforms the focused signal in one direction into a time-frequency plane. This time-frequency transformation is carried out with the Short Time Fourier Transform (STFT). It is then possible to select time-frequency bins associated with the UAV. The acoustic signature of UAVs have the particularity of having an harmonic structure. Two phenomena are present in this type of signals, the rotors' rotation which gives odd harmonics in the case of a two-blade drone, and the blade passing which gives even harmonics [START_REF] Blanchard | Acoustic localization and tracking of a multi-rotor unmanned aerial vehicle using an array with few microphones[END_REF]. Because of the noise, only even harmonics are generally presents. A pitch tracking algorithm is thus used to detect the blade passing frequency of the drone. A number of even harmonics n h is chosen to compute the energy of the corresponding time-frequency bins. To have more time-frequency bins, a bandwidth is defined to take bins around harmonics. This bandwidth is defined to be varying with the harmonic frequency such as ∆ f = f detect Q , with Q a factor determining the width, and f detect the blade passing frequency. In this way, all the time-frequency bins in

[ f detect * i * (1 -1 2Q ); f detect * i * (1 + 1 2Q )] are selected, i = 1, . . . , n h .
The pitch tracking algorithm chosen to detect the blade passing frequency is called the Spectral Harmonic Correlation (SHC) [START_REF] Zahorian | A spectral/temporal method for robust fundamental frequency tracking[END_REF]. This algorithm calculates the correlation between one frequency and a chosen number of multiple of this frequency. It is thus possible to obtain multiple candidates of the blade passing frequency. The frequency that has the maximum harmonic correlation is the estimation of the blade passing frequency. However, in some cases, computing energy with the content selected using the SHC maximum does not ensure continuity between two estimations. In this case, another candidate is chosen until the continuity with the previous DOA estimation is reached.

MEASUREMENT SET-UP

Array Geometry

The microphone antenna used is a 10 microphone array designed in [START_REF] Blanchard | Acoustic localization and tracking of a multi-rotor unmanned aerial vehicle using an array with few microphones[END_REF] to obtain a bandwidth of [220.5, 3430] Hz. Figure 1 shows the disposition of microphones and also the coordinate system used to position a source in the 3D space. The reference microphone is placed at the center and three microphones are distributed on three axes with three different spacings (Equation 1). The first spacing is l 1 = 5 cm which is linked to the high frequency limit. The second spacing is l 2 = 20 cm, and the last is l 3 = 110 cm which is linked to the low frequency limit. (1)

TFR Parameters and Trajectories

DOA estimation is performed on sections of 3000 points, using 2048 points for beamforming. Spatial sampling is carried out with a resolution of (4°, 2°), which corresponds to the azimuth and elevation, and with a distance of r=1 m between the source and the reference microphone. SHC is performed with 8192 points and 5 harmonics for the correlations. TFR is operated by selecting 5 harmonics with a factor Q=8. Two trajectories have been performed by a DJI Phantom IV to evaluate the performance of the TFR approach. In the first configuration, the drone performs three horizontal flights at heights of around 6, 10 and 14 m. During this flight, many bird chirps can be heard. Figure 2 shows the spectrogram of the reference microphone for this trajectory. The harmonic structure of the drone is visible particularly below 2 kHz. Above 2 kHz, all the bird chirps are noticeable by vertical lines around 3 kHz and above. In the second configuration, the drone performs a small and a large circle above the antenna at a height around 15 m. Figure 3 shows the spectrogram of the reference microphone. Bird chirps are present in the same frequency range but are less noticeable. The spectrogram also shows a car passing at the end of the trajectory.

RESULTS

Azimuth and elevation vs time results are presented in Figure 4 for the first trajectory, with classical DSB and the TFR approach in comparison with a GPS embedded in the drone. Results in azimuth for classical DSB show several fluctuations around the GPS reference and particularly at the beginning, estimations are far from the GPS. Between 10 s and 30 s, estimations are fluctuating with a symmetry centered on 0. This symmetry is due to the fact that the main lobe and the secondary lobe are symmetric with respect to 0 and their level is very close. The TFR approach performs better than classical DSB with less fluctuations overall. However, the confusion between the two symmetrical lobes is still present between 10 s and 28 s. The GPS has an incertitude around 3 meters which can explain the constant bias between the GPS and the results. In elevation, classical DSB performs better than in azimuth with still some fluctuations. The TFR approach gives better estimations globally with some fluctuations around 20 s and 40 s. As said before, bird chirps are above 2 kHz so taking harmonics between around 150 Hz and 1 kHz enables to select only content from the drone without the noise. According to the spectrogram in Figure 2, the signal is less strong in the intervals [START_REF] Djurek | Analysis of a Quadcopter's Acoustic Signature in Different Flight Regimes[END_REF]30] s and [38, 45] s so the signal to noise ratio is lower. This could explain the fluctuations for both methods.

Figure 5 shows the azimuth and elevation vs time for the second trajectory, for classical DSB and the TFR approach. Azimuth and elevation results for classical DSB show lots of bias but globally follow the trajectory until around 24 s. The TFR approach performs much better with only small fluctuations despite noise like bird chirps or car passing at the end of the trajectory. Car passing is below 100 Hz so as for the previous trajectory, taking harmonics above 150 Hz enables to select only content from the drone without the noise. Table 1 shows the mean errors and standard deviations for both trajectories and for the two methods used. Errors in elevation are lower than in azimuth and for both trajectories all values are lower with the TFR approach.

CONCLUSION

The purpose of this work is to evaluate the performance of a method exploiting a time-frequency representation of beamforming's output in a noisy environment. Two measurements were carried out, one with birds chirping and another with also a car passing. The time-frequency approach was compared with the classical delay and sum beamforming. The former approach enables to select time-frequency bins corresponding to the UAV to enhance the signal to noise ratio. Results show that for both trajectories, the time-frequency approach gives better DOA's estimations. Indeed, the content selected for energy calculation is not in the frequency range of the types of noise considered which increases the signal to noise ratio and enhances the performance of beamforming. There are still some bias for particular very noisy signal's sections, thus it could be useful to apply some filters like a Kalman filter to smooth those bias. It could also be interesting to know what is the limit signal to noise ratio where the time-frequency approach can still performs well.

Figure 1 .

 1 Figure 1. Microphone array disposition and coordinate system used.

Figure 2 .

 2 Figure 2. Spectrogram of the reference microphone for the first trajectory between 2 kHz and 8 kHz (top) and between 0 and 2 kHz (bottom) (red points are blade passing frequencies detected with SHC).

Figure 3 .

 3 Figure 3. Spectrogram of the reference microphone for the second trajectory between 2 kHz and 8 kHz (top) and between 0 and 2 kHz (bottom) (red points are blade passing frequencies detected with SHC).

Figure 4 .

 4 Figure 4. Azimuth and Elevation vs time for classical DSB and TFR method with Q=10, for the first trajectory.

Figure 5 .

 5 Figure 5. Azimuth and Elevation vs time for classical DSB and TFR method with Q=10, for the second trajectory.

Table 1 .

 1 Mean errors µ and standard deviations σ for classical DSB and TFR approach in azimuth and elevation for the two trajectories.

			First Trajectory			Second Trajectory
		Azimuth (°) Elevation (°) Azimuth (°) Elevation (°)
		µ	σ	µ	σ	µ	σ	µ	σ
	Classical DSB 85.9 69.7 12.6 12.1 63.7 42.7 29.1 21.4
	TFR	49.7 30.3	8.3	6.9	53.3 14.5	8.9	4.9

ACKNOWLEDGEMENTS

The authors thank the Direction Générale de l'Armement (DGA) and the Région des Pays de Loire for funding this work.


Javier Gil-Quijano

Thomas Louail

Guillaume Hutzler

From biological to urban cells: lessons

come

Introduction

Natural and social complex systems are often characterized by many different entities, heterogeneous in nature and dimensions, at various levels of organization. The interaction between these entities are intricated, and act at very different time and spatial scales. Addressing questions about these systems requires to consider simultaneously multiple levels of organization. Paradoxically, in this context, most of the "multiscale" or "multilevel" models implement a solution where the description of the thematic knowledge occur at one level only. The choice of this level of description determines the selection of the entities of the real system that are reified as agents in the model. The simulated system can then be analyzed at two organizational levels: at the agents' level on the one hand, through the analysis of their trajectories; at the system's level on the other hand, through a set of measures used to characterize the structures produced during the simulation. It should be noted that such systems can also be measured at intermediary levels that appear to be relevant to the modeler. These levels can for example correspond to groups of agents that share common characteristics. In practice, however, this refinement is rarely implemented.

In that case, it seems problematic to talk about truly multilevel modeling since only the "lower" level is present in the model and specified as such by the modeler. The "higher" levels are in this case the ones that can be observed by the experimenter who "looks at" and analyzes the simulations, but these levels are not reified in the model. This emergentist approach, which is singlelevel regarding the design of the model, and bi-level regarding the analysis of N. Desai, A. Liu, and M. Winikoff (Eds.): PRIMA 2010, LNAI 7057, pp. 620-635, 2012. c Springer-Verlag Berlin Heidelberg 2012 results, is by far the most commonly used in agent-based simulation. However, this approach can not always be satisfactorily applied when modeling real systems. Indeed, a number of complex systems dynamics can not be understood without integrating multiple levels of organization, and multiple processes that can not be reduced to a purely emergentist approach. In particular, social systems inherently include a structuring role of higher levels on lower levels. Thus, the corresponding domain theories are rarely single-level, either because there is a lack of knowledge at a given level or because the domain's ontologies mix entities and actors of different levels of organization. It is for example difficult to imagine modeling the evolution of a whole city over several years, on the basis of the sole specification of the behavior of its inhabitants. Moreover, it would be too expensive from a computational point of view to simulate a large system as a whole at the most detailed level. For example, simulating a cell consisting in more than 4.10 13 molecules (e.g. a cell of a rat's liver) at the atomic level, or even at the molecular level, is indeed completely unrealistic.

In the end, the question that is addressed by the model requires considering entities at different levels (for example the molecular and cellular levels, or the individual, neighborhood and city levels) which, as Servat et al. recall in [START_REF] Servat | When Agents Emerge From Agents: Introducing Multi-Scale Viewpoints In Multi-agent simulations[END_REF], is part of the scientist's "intellectual gymnastics": to make different points of views and different descriptions of the same system co-exist, and to coherently articulate them. And indeed, we perceive the world at several scale levels. They also underline two additional reasons that justify the integration of multiple levels. The first reason is computational, the collective behavior of many distributed systems changing remarkably when the number of their components reaches a critically large value. It is thus important to enable the simulation of such large numbers of components, which makes it impossible to model systems at the smallest possible scale. To circumvent this difficulty, we can imagine dynamically replacing some groups of agents by "super-agents". These would embed behavioral rules that would be equivalent to the measured result of the accumulated actions of the individual agents. That would allow to enhance the performance, and the modeler could then take advantage of the saved computational power to "zoom in" other parts of the system that he/she would like to model in more details. The second reason is "thematical". If an agent is able to realize that it belongs to (or is categorized as belonging to) a group of higher organizational level, like a social class, it might conscientiously affect his behavior in order to reinforce (or oppositely to diverge) his belonging to this group. In a general manner, integrating entities and rules of multiple levels of organization is an important issue. It should allow to tackle original questions, as compared to the possibilities offered by classical bi-level, micro-macro modeling.

Additionally, rather than representing all components and their relations, the key point should be to consider simultaneously the level of the system's components and the level of their emergent properties, as Lesne expressed in [START_REF] Lesne | Multi-scale approaches[END_REF]. It implies that our efforts should worth be made in accurately describing how the different levels articulate and influence each other, rather than solely juxtaposing many levels in a single model. Articulating levels implies to explicitly represent each of them into the model, and explicitly define how they are coupled. In agent-based modeling, this means that the model should incorporate some rules that specify how the agents associated to a given level would impact and modify agents at other levels. This is presently a central question in the agent-based modeling community and several projects focus on developing simulation platforms that allow to take into account simultaneously several levels within a single model (as for example the 3Worlds project [START_REF] Gignoux | 3worlds: a new platform for simulating ecological systems[END_REF] in ecology, or more generally in the GAMA platform [START_REF] Vo | A Modelling Language to Represent and Specify Emerging Structures in Agent-Based Model[END_REF]).

Before illustrating these different aspects by the presentation of three recent applications of multilevel simulation in section 3, we start in section 2 by a work of definition necessary to clarify the manipulated concepts. In the examples section, we concentrate on isolating the different organizational levels represented in each model and the mechanisms that support their coupling. In section 4, we generalize their underlying multi-agent organizations and we throw light upon their similarities and differences. From that discussion we propose a classification of multilevel agent-based architectures, based upon the criteria identified in this comparison. Finally, we conclude by discussing the research perspectives opened by this comparative study.

Multiscale or Multilevel ?

Scale or level, multiscale or multilevel ? The concepts of scale and level are frequently used to model complex systems and to characterize the manipulated abstractions, their granularity and their position in a hierarchy that structures and organizes the system. These two terms are often used interchangeably, moreover they are used in diverse manners depending on the disciplines, which is potentially very confusing.

The concept of scale is frequently characterized by an adjective that relates it to space or time: spatial scale, temporal scale. The term level is often associated with terms such as micro, macro or meso that situate the described system or phenomenon in respect to its size, its characteristic evolution time or an inclusion relation with other systems or subsystems. At first sight, we consider that the concept of scale refers to a dimension of analysis on which the phenomenon of interest can be measured. This dimension can be spatial or temporal, but also quantitative. The spatial and temporal dimensions refer respectively to the size of the entities involved in the phenomenon (typically from nanometers to thousands of miles throughout all the intermediate sizes), and the characteristic time associated with the behaviors of these entities and their interactions (from nanoseconds to centuries). The quantitative dimension refers to the number of entities involved in the phenomenon (typically from 2 to some billions).

Compared to that definition of scale, the concept of level is used to situate the studied phenomenon and/or the entities that compose it, along the considered dimension of analysis. A level usually corresponds to all the entities whose size and/or characteristic evolution time have the same or comparable orders of magnitude. If one sticks to this use of the scale and level concepts and being strict, one should not use the "multiscale " term to describe models. Indeed, most of the times "multiscale" means that the model considers entities at different levels along the spatial scale. Later in this article we will not use the multiscale adjective anymore to characterize models, prefering the use of the multilevel adjective instead.

It should be immediately noted that the concept of level is both relative and bounded to a modeling choice. With relative, we mean that an entity, which is considered in a given phenomenon, can not be totally described as belonging to a given level. For example, from the perspective of molecular biology, molecules are related to the micro level while the cell is associated to the macro level; from the standpoint of physiology, the cells are associated to the micro level and the macro level corresponds to the tissue. Moreover, the association of an entity with a given level is not exclusively related to the entity's characteristics along a given scale but it is the result of the analysis and modeling choices. Indeed, the decision of combining diverse entities within a given level often involves the fact that the entities belong to a structure or a relevant organization in terms of the system's description. It is indeed common to speak of "level of organization" or "level of abstraction".

Let us finally present two additional concepts that are useful in our analysis: hierarchy and structure. The concept of hierarchy, because systems are often described as a hierarchical interlocking of levels (molecules, cells, tissues, organs, individuals, group, society). The concept of structure, as it is often the recognition of a structuring set of entities at one level that allows the definition of entities at a higher level. In [START_REF] Gibson | The concept of scale and the human dimensions of global change: a survey[END_REF] the concept of hierarchy is defined as "A conceptually or causally linked system of grouping objects or processes along an analytical scale", and three types of hierarchies are distinguished: exclusive, inclusive and constitutive. An exclusive hierarchy is a hierarchy in which there is no inclusion relationship between entities in a level and higher level entities. For example, this is the case of military ranking systems or food chains in which individuals of a certain trophic level feed on lower-level individuals. Conversely, in inclusive or constitutive hierarchies the entities of a given level are included in a top-level entity. The objects in an inclusive hierarchies exhibit a categorical relationship similar to that present in hierarchies of classes in a object-oriented programming language or in taxonomical hierarchies (domain, kingdom, phylum, class, order, family, genus, species). In the case of constitutive hierarchies, entities of one level are grouped into new entities of the next level, the latter being characterized by new organizations, functions and emergent properties (molecules, cells, tissues, organs, individuals). To determine the levels where entities must be placed, more than their sizes, the important point is to consider the group they form, that is, how the entities organize within their group.

The Models

Now that the context has been clarified, we will focus on three proposed agentbased simulation models in which multilevel modeling issues have been addressed explicitly. The first example deals with the growth of a cancerous tumor, addressed at the molecular and cellular levels. The second deals with housing choices of households in Bogota, treated individually at the level of households and housings but also at the level of groups of housings and households. Finally, the third presents a model of urban morphogenesis, considered at inter-and intra-urban levels.

The objective is not to make an in-depth presentation either of the models or of their results, but rather to focus on how they implement the concept of multilevel modeling. To do this, and to facilitate the comparison between these different models, we will answer the following questions:

1. Specification of the levels: what are the different identified levels, what are the types of objects and/or agents defined at these levels, and how are these types defined (are they specified beforehand or are they dynamically discovered)? 2. Instanciation of the objects: how is the instanciation of the objects and/or agents done (is it done statically by explicitly defining the agents of the model or are they created dynamically in the simulation depending on the context)? 3. Coupling between the levels: how are the different levels coupled with one another (what is the nature of the interactions between agents of different levels)?

Cancer Cells Migration

Context and objective. When speaking about cancer, one of the major factors of bad prognosis is associated with the appearance of secondary tumors, called metastases. These secondary tumors can develop when a cell of the primary tumor switches from a proliferating to a migrating state, thus escaping towards other organs elsewhere in the body. When the micro-environmental conditions permit, the cell stops its migration and returns to a proliferating state, which leads to the development of a secondary tumor. We are interested in the microenvironmental conditions around the tumor which could lead to the metastatic escape of a cell. We study more precisely the role of a protein, which is suspected to have a role both in triggering the morphologic transformations of the cells and in providing loose adhesion contacts that enable the escape [START_REF] Maquerlot | Dual role for plasminogen activator inhibitor type 1 as soluble and as matricellular regulator of epithelial alveolar cell wound healing[END_REF].

The model. We developed a first agent-based model in which both cells and proteins are modeled as individual entities. The growth of the tumor is modeled by implementing a cellular division behavior, which depends mainly, for the cell, on its capacity to feed itself from surrounding nutrients. This proliferating behavior is coupled to an inter-cellular repulsion behavior. The model also takes into account the dynamics of production and internalization of proteins by the cells. The differential access to nutrients leads to three distinct states for the cells inside the tumor: a cell that has a satisfactory access to nutrients (external layer) is active and has both the proliferating and the protein production/internalization behaviors; a cell that receives too few nutrients dies (core); cells in-between receive enough nutrients to produce and internalize the proteins but too few to proliferate, thus becoming quiescent (intermediate region).

The main trouble is that when tumors reach a size of several thousands of cells, the number of proteins reaches several hundreds of thousands. We get therefore quickly limited by the size of the tumors that can reasonably be simulated. The proposed solution consists in abstracting some details of the model in regions where they are not necessary, thus allowing to simulate bigger tumors or to add details in the most interesting regions. Given that the main interesting area is at the interface between the external layer of the tumor and the environment, we proposed to replace the internal region of the tumor by an aggregated model, abstracting the set of cells and proteins in the core region as a global model of ingoing and outgoing flows. From a spatial point of view, this model is delimited by the entire set of necrosed and quiescent cells, and all the proteins in the so-defined area. Since these cells are static, or have a very limited mobility, this permits to neglect the repulsive movements of the cells (mainly due to the cellular-division behavior of the cells in the external proliferating layer). It is then a matter of calculating the interactions between the aggregated model and the external cells or proteins. It is straightforward to determine the cells or proteins that have to be integrated in the aggregated model: these are the quiescent cells, and the proteins in the corresponding area or the ones that, during their random diffusion movement, collide with the aggregated model. Symmetrically, in order to determine how many proteins will be released by this model, it is necessary to evaluate the relative proportion of necrosed and quiescent cells, so as to evaluate the number of cells that produce and internalize these proteins (the quiescent ones). It is then possible to update the concentration of proteins inside the aggregated model. By assimilating the proteins diffusing inside the model to a perfect gas, we can then calculate the "pressure" inside the model, thus determining the statistical quantity of proteins that leave the aggregated model. These proteins are finally stochastically distributed around the aggregated model, at the immediate vicinity of the frontier.

Agents and levels.

In this model, objects of very different sizes (cells and proteins) coexist. The levels correspond to two types of objects both types being defined beforehand. The instantiation is done by creating an initial cell, which itself creates other cells by successive division steps. The cellular and molecular levels are coupled thanks to the activity of the cells: the latter produce and internalize proteins. By simulating these agents together, a cluster of cells is produced. That cluster is observed and identified as the tumor. Up to this point, there is no scale crossing, but only the interaction, in a common environment, of objects of different levels in the spatial scale. The tumor's level is only observed and does not perform any active role in simulation.

On the contrary, when the aggregated model is introduced (see figure 1), we identify at run time an intermediate level (between the cellular and tumor levels) entity, which is reified during the simulation. This corresponds to the introduction of the additional modeling level of a multicellular tissue at the heart of the tumor. This kind of object is specified beforehand: we know for sure that the simulation will lead to the development of a tumor and we can therefore anticipate the appearance of this object. However, its instantiation will depend on the time at which such an object is observed in the simulation. The coupling of this structure with the other objects (cells and proteins) depends on if they are inside or outside the aggregated model. The coupling with the internal objects is implemented thanks to a set of very simple differential equations, which describe the evolution of the relative quantities of necrosed and quiescent cells, the evolution of the concentration of proteins inside the model and the amount of externalized proteins. The coupling with the external objects is implemented by describing both the conditions that lead the external objects to be integrated into the aggregated model and the rules defining the externalization of proteins. The dynamics of the aggregated object can then be seen as the numerical integration of very simple differential equations.

The multilevel character of this model can be seen in two complementary ways. The first one consists in noticing that the model, which is composed of both cells and proteins, integrates objects of very different sizes. The second one consists in proposing that objects corresponding to abstractions of higher levels of organization be introduced dynamically in the simulation.

SimulBogota : Households and Housings in Bogota City

Context and objective. The objective of the SimulBogota model [START_REF] Gil-Quijano | Mechanisms of automated formation and evolution of social-groups: A multi-agent system to model the intra-urban mobilities of Bogotá city[END_REF] is to reproduce the evolution of the spatial distribution of the population of the city of Bogota throughout several decades. This evolution depends on both the internal and external migrations as well as on the evolution of the population and of the housing-stock. The evolution of the population of households is the result of individual events (marriage, divorce, emancipation, death, etc.) that produce socio-economical changes as well as the creation and destruction of households. The evolution of the housing-stock depends mainly on both the housing-renewal and the aging-of-buildings processes. In the case of Bogota, these processes are the result of very complex dynamics that not only involve the construction controlled by planning policies, but also informal mechanisms such as self-construction and illegal occupation of housing estates.

The model. To implement our model, the only available data were the socioeconomical descriptions of households and housings as well as their spatial distribution for the years 1973 and 1993. In the absence of sufficient data, a model centered on the explicit representation of the decision and evolution mechanisms at the individual's level is inadequate or even impossible. Under these conditions, we proposed to consider groups of households and groups of housings as main modeling entities. This reduces the complexity of simulations by taking an aggregate level into account, in which the decision process that leads households to move is placed. However, it is necessary to consider the populations of households and housings in order to model the evolution of groups.

In this model we explicitly consider two levels of modeling, the microscopic level that contains data that describe the populations of households and housings and the mesoscopic level that contains the groups of households and the groups of housings. The model is mainly composed of three mechanisms executed in sequence at each step of simulation:

1. Formation of groups: this allows to go from the microscopic level (households and housings) to the mesoscopic level (groups of households and groups of housings). It is an automated clustering mechanism [START_REF] Gil-Quijano | Mechanisms of automated formation and evolution of social-groups: A multi-agent system to model the intra-urban mobilities of Bogotá city[END_REF] performed on the data that represent households and housings. 2. Interaction between groups: this allows to rehouse the households in the city.

It is an auction-based mechanism that is used to exchange housing-units between groups of households. These interactions are governed both by a set of lists of housing-preferences, which are built dynamically1 and a static matrix of costs of moving between urban areas. In this mechanism, we assume that households seek to move closer to households of their social group and to occupy the same group of housings. It is therefore a self-reinforced mechanism of spatial segregation. 3. Evolution of the population: this is a mechanism based on the execution of global rules of evolution of the populations of households and housings. These rules allow the creation or deletion of entities at the microscopic level (households or housings). Each rule associates an entity profile with a number of entities to be treated. These rules do not represent individual events (which are very difficult to be considered and very data-consuming) but global trends of evolution.

In order to trace the evolution of groups, a last mechanism is implemented, which allows to relate the groups found in two successive steps of simulation.

Agents and levels.

In this model, in order to reduce the complexity of simulations and the amount of data required to represent the dynamics of intra-urban migrations, we introduced an intermediate level composed of "artificial" structures: groups composed of similar microscopic entities. These structures have no "physical" equivalent and they are the result of the analysis of households data and housings data (microscopic level). Thus, physical objects, at the microscopic level, coexist with artificial objects, at the mesoscopic level, that are dynamically reified by clustering the objects of the microscopic level into homogeneous groups (see figure 2). Compared to models of physical phenomena, an additional question arises: it is necessary to define the number of groups to be considered, knowing that a small number can produce an oversimplification of the model, while a high number may get groups extremely closer to the microscopic level and cause a loss of the model's synthesis ability. Even if the level of groups has been specified beforehand, the number of considered groups is determined at run time and the groups are dynamically instantiated from the results of clustering the data of households and housings at every simulation's step.

From the evolution's perspective, general rules were constructed from descriptive data of households and housings. The core of the evolution mechanism is therefore located at the microscopic level and its effects are propagated to the level of groups by the clustering mechanism (bottom-up coupling). However, there is no direct interaction between microscopic entities. The microscopic level is used as an anchor with reality while the level of groups provides a synthetic vision of reality, which facilitates the formulation and the assessment of hypotheses about the behavior of the system, thus leading to a better understanding of the modeled phenomenon.

The "artificiality" of groups conditions the design of both the inter-groups interaction mechanisms and the interlevel interaction mechanisms. When simulating groups of micro-entities, one has to deal with abstract entities, that have no "physical" counterpart. Since the modeler can not rely on well established rules (or that can be easily deduced) that describe the behavior of the groups, he is therefore free in defining the interaction mechanisms. Since we know very little about the functioning of groups, the mechanism chosen to represent the interaction between groups is as artificial as the groups themselves. The proposed mechanism, based on auctions of housings, has no physical ground, it is simply an artifact that allows the dynamic multi-criteria matching between groups of households and groups of housings. The design of this mechanism has therefore more to do with modelers' intuition than with inspiration from "real" mechanisms. This mechanism, which is used to rehouse households, establishes the top-down coupling between the level of groups and the microscopic level.

Simpop3 : Exploring Urban Dynamics at Three Geographical Scales Simultaneously

Context and objective. The Simpop models are agent-based models dedicated to the understanding and reproduction of urban growth over periods of several centuries. Those models are used to study the different geographical parameters that lead to the differences that exist at different geographical levels (city, region, nation, continent) between the systems of cities in Europe and in United States. The first of these models, Simpop1 [START_REF] Bura | Multi-agents system and the dynamics of a settlement system[END_REF] has been one of the very first applications of MAS systems in geography. In this section, we briefly present two independent models, Simpop2 and SimpopNano. We then discuss their coupling, which results in a new multilevel model, Simpop3. The latter allows to tackle new geographical questions, regarding the multilevel processes that take part in the growth of urban systems. The Simpop2 model is based on the urban evolutionary theory [START_REF] Pumain | Pour une théorie évolutive des villes[END_REF] and focus on the modeling of systems of cities considered as self-organized complex systems. In that model, some generic and universal properties of the systems of cities are identified and separated from specific processes related to the history of each system. Thanks to that dissociation, Simpop2 allows to reproduce the differences that exist between global properties (for example hierarchical distribution of cities' sizes) of different systems of cities. simpopNano [START_REF] Louail | Can geometry explain socio-economical differences between US and european cities[END_REF] is an attempt to reproduce the emergence of typical patterns of organization inside the city and their long-time evolution (200 years), under the dependence of both the topology of the street networks, and the performance of the transports networks. The objective is twofold: to compare the morphogenesis of cities in Europe and United States and to isolate the minimal set of factors that allow to reproduce the observed differences between the cities of the two continents in terms of densities, prices and activities repartitions [START_REF] Bertaud | The spatial organization of cities: deliberate outcome or unforeseen consequence[END_REF]. The Simpop2 model. Cities are the model's main agents. They interact through the exchange of goods associated to the urban functions that they own. An urban function characterizes a role played by the city that owns that function (heavy industry, car industry, regional capital, etc.) in the system of cities. Each function has a specific period during which it is active. The spatial interactions between cities are of several types. They depend on the urban function that mediates the "communication": spatial proximity, administrative frontier or specialized large scale network. In parallel to these exchanges, cities compete for the acquisition of new innovations, which are represented by the dynamic arrival of new urban functions in the system during the simulation. At run time, the interaction network generate progressive specialization of the cities and differentiation between them. At the global level, the consequence is the emergence of a system of cities, whose properties can be determined by measuring key indicators as the total population, primacy indexes, etc.

The SimpopNano model. In this model, agents are of two types: neighborhood agents, which represent autonomous portions of the city space, and urban functions agents (the same as in Simpop2), which represent the main families of socio-economical activities owned by the city. Functions have employees to localize. They also have a budget to do so. Neighborhoods are linked to a dynamical network and differ by their accessibility and their functional composition. The combination of these two indicators make them more or less attractive for functions, and equally more or less expensive. Functions differentiate by their economic power and by their localization strategies. At each time step the model simulates the competition for space of these urban functions inside the neighborhoods. As a consequence of that competition one can observe at run time the structuration of the emerging city. Several measures are used to characterize the structures dynamically produced: densities and prices gradients, activities repartition maps, or functional specialization indexes of the neighborhood, etc. The Simpop3 model. Simpop3 includes agents at two levels: at the micro level, the urban functions and neighborhoods agents of simpopNano are considered. At the intermediate (meso) level, the urban functions and the cities agents of Simpop2 are considered. The link between levels is performed by the exchange of urban functions.

Simpop3's execution relies on the alternate execution of a Simpop2 iteration followed by a SimpopNano iteration:

at each time step Simpop2 computes the cities spatial interactions and the next state of each of them, i.e. the new functions they acquire, and the number of employees and budget of each of their functions; -the Simpop2's outputs are used as input data of SimpopNano, which ventilates these functions staff among the city's neighborhood. Urban functions pay their implantations with the money they have generated at the city level by the sell of goods produced by the function to other cities. SimpopNano outputs an indicator of the spatial "performance" of the functions, which qualify the quality of the functions' repartition inside the city. -This indicator is considered by the newly arriving urban functions agents to decide in which cities of the system of cities they will implant.

Agents and levels. In Simpop2, the spatial specification level, i.e. the level at which the thematic knowledge on the system is formalized as agents and interaction rules, is the level of cities. The cities are primary (micro level) entities, these are the agents of the model. The system of cities is then the emergent level (macro level). SimpopNano "works" at a more nested level: the spatial specification level is the level of neighborhoods, in which the urban functions (the same that are acquired by the city in Simpop2) must localize their employees. In this case, the city level is the emergent level. The "city" emerging from SimpopNano is not the same as the one that is specified as an agent in Simpop2. The city of SimpopNano is an entity that only exists at runtime, through a combination of measures that let the geographer decide whether the spatial structure emerging of the model "looks like" a real city or not. For Simpop3, we have faced the need to build a bridge between these two representations of the same city: the agent specified in Simpop2, and the structure emerging from SimpopNano. This is summarized by figure 3.

To implement this articulation between the two models, we have choosen to identify an entity that would be common to the two levels. This entity should represent the mutual influence between an individual city and the system of cities. The concept of urban function has been instantiated in the model as a somewhat "multilevel" agent. Urban function is an abstract concept defined by geographers to qualify the role played by a city in the system of cities it belongs to. This concept is relevant at the inter-urban scale. To implement the coupling, the concept has been generalized, and we have made the hypothesis that this concept could be used to qualify the various kinds of socio-economical activities that interact inside the city, and whose behavior shapes its spatial organization. In fact, this is the transfer of this inter-urban concept to the intraurban level that allowed us to design a bridge that links these three spatial levels all together. The urban function agent is like a buffer: it encapsulates variables that are affected by the dynamics at each level.

Towards Multilevel Multi-agent Organizations

Elaborating from the three preceding examples, and from other models taken from the literature, one can try to categorize multilevel models around three aspects:

1. Multimodels: we consider here models originally independent, placed at different levels, interacting with each other. The outputs of the upper level models are used to define global parameters of the lower level models; the outputs of the lower level models are considered as ingoing flows in upper level models. We can distinguish between two sub-categories:

(a) the different models are executed alternatively (it is the case for example in Simpop3). In that case, the coupling between the models is generally weak but difficulties may appear if the different models share objects that each of them may modify (the "urban function" entity in Simpop3). (b) a multi-agent model is encapsulated inside a higher-level agent. In the model of tumor growth, this would correspond to the fact that we model the internal dynamics of cells, rather than considering a fixed rate production of proteins. This would allow to take into account the genetic regulation networks controlling the production of these proteins. One has to be careful, in that case, to the scheduling of the agents of the different levels, which doesn't necessarily occur at the same time scale. 2. Models with multilevel specification: we consider here models where there exist interactions between entities placed at different levels along the spatial, temporal or quantitative scales. One can achieve this through two distinct approaches: (a) through the static specification of the simulated entities (e.g. cells interacting with proteins in the tumor growth model; Simpop3). Again, problems arise with the scheduling of agents. In the specific case of cells and proteins, the characteristic timescales are indeed very different. This imposes to focus on discrete-events simulation approaches, or to handle several schedulers in parallel for the different types of simulated objects. (b) through the dynamic specification of the simulated entities: implementation of mechanisms such as a "dynamic magnifier" that allow to focus on critical areas by raising the spatial resolution and the level of details (e.g. the fractal model of the environment proposed by [START_REF] Marilleau | Multiscale mas modelling to simulate the soil environment: Application to soil ecology[END_REF]). The main difficulty in that case lies in the continuous adaptation that is required to retain the higher possible level of details on the areas of interest, for example the ones where agents are situated. 3. Multilevel models with dynamic reification: we deal here with models that produce higher-level agents by automatic "observation" of the simulation, characterization of higher-level structures and reification of the structures as objects. We can again distinguish between two distinct cases: (a) the agents of the two levels do not directly interact with one another (e.g. simulBogota) because the entities of the two levels are not in the same modeling space. In some way, this case reminds the (1a) case, because we also have an alternating execution of models of the micro and macro levels: indeed, the simulator repeatedly computes the evolution of the model at the micro level, then dynamically reifies the macro level, and computes the evolution of the model at this macro level. (b) the agents of the two levels can interact with one another and with the agents of the other level: the entities of the two levels are in the same modeling space (e.g. tumor growth model with the aggregated model, RIVAGE [START_REF] Servat | When Agents Emerge From Agents: Introducing Multi-Scale Viewpoints In Multi-agent simulations[END_REF], or [START_REF] Gaud | Holonic multilevel simulation of complex systems: Application to real-time pedestrians simulation in virtual urban environment[END_REF] that develops hierarchical holonic approaches). This approach however induces a greater complexity since it requires to be able to detect the emergence of a structure and to characterize its dynamics and its interactions with the other agents, so as to be able to reify it. Moreover, it is necessary to control that the conditions required for the structure to be maintained hold, and if it is not the case, to dissolve the structure as such and to transform it back into individual agents.

In the examples that we have presented, only constitutive hierarchies are modeled. In these cases, levels can be either pre-specified beforehand or automatically discovered. When modeling exclusive hierarchies however, the entities and levels are usually specified beforehand. The modeling of exclusive hierarchies can be addressed by the methodologies dealing with the design of organizations. In that case, the modeling process focuses on the specification of roles, norms, functions that define the agents' behaviors and their interactions. Several methodologies have been developed to address organizations modeling, among which are MOISE [START_REF] Hubner | Developing organised multiagent systems using the moise model: programming issues at the system and agent levels[END_REF] or AGR [START_REF] Ferber | From Agents to Organizations: an Organizational View of Multiagent Systems[END_REF]. As the effort is done on specification of the entities and their interactions, we consider that these types of models can be included into the second category.

With respect to the modeling of constitutive hierarchies, in our knowledge no general methodology exists. However there exists methodologies that can be used to tackle the design of models of some of the described categories. The categories 1 and 2 can be addressed by multimodeling methodologies. Some of these methodologies are based on the DEVS approach [START_REF] Zeigler | Theory of Modeling and Simulation: Integrating Discrete Event and Continuous Complex Dynamic Systems[END_REF]. The Virtual Laboratory Environment (VLE) proposed by [START_REF] Quesnel | The Virtual Laboratory Environment An operational framework for multi-modelling, simulation and analysis of complex dynamical systems[END_REF] implements that approach. VLE provides modules for developing Petri nets, differential equations and spatialized agent based models among others. It also provides the capability to integrate existing models. The modular (every model is considered as an atomic and independent module) approach of VLE and the light coupling between models (based on the input/output events triggering) gives to VLE the flexibility needed to adapt to a large number of multilevel problems where levels can be specified beforehand as independent models. The design of constitutive hierarchies has also been tackled by simulation platforms such as SWARM2 that proposes the possibility of designing hierarchies as recursive groups of agents.

Nevertheless, these approaches are not well fitted to the case of automatic discovery and analysis of levels (category 3). A significant effort in that direction is currently being done in the development of the GAMA platform (related to the 3Worlds project [START_REF] Gignoux | 3worlds: a new platform for simulating ecological systems[END_REF]), which includes the use of statistical tools for the automatic discovering and tracking of emergent structures in simulations of ecological systems.

Conclusion

We have presented three agent-based models that can all, one way or another, be qualified as "multilevel". These models are but very different with one another, by their application domains, the scales of the modeled entities, or the approaches implemented to handle the complexity associated to the coexistence of different levels of organization. We proposed an analytical framework, which still needs to be completed and refined by integrating other works from the community, but which already enables the classification of multilevel models, and against which we positioned our models.

By so doing, we do not pretend proposing a step-by-step methodology for the design of new multilevel models. Instead, our aim is on the one hand to show that different modeling problematics can lead to very different solutions, and on the other hand to help the modeler identify the difficulties peculiar to each of the approaches. The identification of these difficulties also leads us to propose some directions for the implementation of agent-based inter-level coupling. We illustrated the pertinence of such couplings on the three presented examples, as well as on other examples drawn from the literature.

When existing models have demonstrated their "quality", it is both useful and important to reuse them, which implies to be able to couple models at different scales or based on heterogeneous formalisms (discrete/continuous for example). To this end, on the one hand microscopic models can be encapsulated as higherlevel agents, on the other hand continuous models (e.g. differential equations) can be used in the definition of global variables and dynamics that can feed lower-level models.

Because lots of complex systems have a dynamical structure, it is also important that the reification of entities of the system as agents could itself evolve dynamically. To achieve this, it is necessary to enable the automatic detection [START_REF] Moncion | Detection of emergent phenomena in multiagent systems[END_REF] and reification of emergent properties. Reciprocally, it is necessary to enable the splitting of agents into underlying organizations, interactively. By adapting the levels of description upon the system, the aim is not so much to gain in terms of computational efficiency, as to gain in terms of expressiveness and intelligibility. By selecting the most pertinent levels of organization and description, the aim is indeed to gain the deeper possible understanding of the mechanisms at work in the modeled system.

Fig. 1 .

 1 Fig. 1. Introduction of an aggregated model to account for the core of the tumour

Fig. 2 .

 2 Fig. 2. Diagram of interactions between levels in the simulation of the evolution of the spatial distribution of population in SimulBogota

Fig. 3 .

 3 Fig. 3. Simpop3: a multilevel MAS to test urban theories at the crossing of scales

Preferences evolve according to the changes in the spatial distribution of the groups.

http://www.swarm.org