Pascal Ballet

Latim

ORPHY Michaël Theron

Modelling and Simulating Complex Systems in Biology: Introducing NetBioDyn -A Pedagogical and Intuitive Agent-Based Software

Modelling and teaching complex biological systems is a difficult process. Multi-Agent Based Simulations (MABS) have proved to be an appropriate approach both in research and education when dealing with such systems including emergent, self-organizing phenomena. This chapter presents NetBioDyn, an original software aimed at biologists (students, teachers, researchers) to easily build and simulate complex biological mechanisms observed in multicellular and molecular systems. Thanks to its specific graphical user interface guided by the multi-agent paradigm, this software does not need any prerequisite in computer programming. It thus allows users to create in a simple way bottom-up models where unexpected behaviours can emerge from many interacting entities. This multi-platform software has been used in middle schools, high schools and universities since 2010. A qualitative survey is also presented, showing its ability to adapt to a wide and heterogeneous audience.

INTRODUCTION

The theory of complex systems has become more and more relevant over the last thirty years to understand concepts such as emergence and self-organization and their role in biological, physical, chemical and social systems [START_REF] Jacobson | Complex systems in education: Scientific and educational importance and implications for the learning science[END_REF]. Modelling and simulating these concepts behind the theory of complex systems is now very important, especially for biologists (students, teachers, researchers). For example, recent works have highlighted the complementarity of modelling both bottom-up and top-down (aggregated) approaches [START_REF] Stroup | On the embedded complementary of agent-based and aggregate reasoning in students developing understanding of dynamic systems[END_REF]. It has been shown though that teaching and learning complex systems are challenging tasks, and raise a lot of pedagogical issues. The two main issues are:

1. A widely taught top-down approach that have led students to think in that unique way; and 2. System dynamics that are difficult to understand and can be non-linear and counterintuitive [START_REF] Jacobson | Complex systems in education: Scientific and educational importance and implications for the learning science[END_REF]).

Among different strategies, the use of Multi-Agent Based Simulations (MABS) in research, teaching and learning has proved to be an efficient way of answering (some of) these issues [START_REF] Epstein | Using NetLogo as a tool to encourage scientific thinking across disciplines[END_REF][START_REF] Jacobson | Complex systems in education: Scientific and educational importance and implications for the learning science[END_REF][START_REF] Ginovart | Discovering the power of individual-based modelling in teaching and learning: The study of a predator-prey system[END_REF]. Indeed, the individual-based approach, in opposition to a population-based approach (such as ordinary differential equations), focuses on the entities of the system, their behaviour and their local interactions to explain the global system's behaviour. As such, this concept is easier to understand, more intuitive and do not require advanced mathematical skills [START_REF] Ginovart | Discovering the power of individual-based modelling in teaching and learning: The study of a predator-prey system[END_REF]. The use of computer tools to implement these models in virtual environments and simulate them allows researchers and students to generate hypothesis, test them and, especially for students, build their knowledge more efficiently (in a process of abduction [START_REF] Houser | The Essential Peirce: Selected Philosophical Writings (1867-1893[END_REF]), see Section 2.2). NetLogo [START_REF] Wilensky | Netlogo. Center for Connected Learning and Computer-Based Modeling[END_REF] is a good example of such agent-based software, and has been used in a lot of works, both in education [START_REF] Epstein | Using NetLogo as a tool to encourage scientific thinking across disciplines[END_REF] and research [START_REF] Banitz | Individual-based modeling of soil organic matter in NetLogo: Transparent, user-friendly, and open[END_REF].

This chapter focuses on how to teach complex biological systems to, for example, university students in Biology, middle school and high school students; students who often do not have any experience in computer programming, and/or are reluctant to implement any code. The problem is that most of agent-based software require knowledge and skills in programming languages such as Java (e.g. the Repast software [START_REF] North | Experiences Creating Three Implementations of the Repast Agent Modeling Toolkit[END_REF])) or the NetLogo environment. This is an issue that occurs more and more as the use of agent-based software, both in research and teaching, grows in social and life sciences. In [START_REF] Ginovart | Discovering the power of individual-based modelling in teaching and learning: The study of a predator-prey system[END_REF] and [START_REF] Gkiolmas | Using simulation of Netlogo as a tool for introducing Greek high-school students to eco-systemic thinking[END_REF], a model of a predator-prey system is used with NetLogo to help respectively first-year and high-school students to understand individual-based approaches and eco-systemic mechanisms. Despite its interest, this model is a ready-made one, coded in NetLogo, where the students can change some parameters of the simulation, but are not implied in the process of creating their own simulation from scratch. Indeed, implementing this model is considered as "a hard task" by the students [START_REF] Ginovart | Discovering the power of individual-based modelling in teaching and learning: The study of a predator-prey system[END_REF] and could be counterproductive: looking for errors in the code instead of thinking at the rightness of the model. The authors argue that using pre-existent models could have a part in preventing students for building their own system's representation (this point will be developed in Section 2.2). The gap between most of agentbased software prerequisites and the actual programming skills of students (and sometimes researchers) in these fields has to be dramatically reduced and the processes of implementing a model and simulate it should be more intuitive.

This chapter essentially looks at the modelling of biological systems at and around the cellular scale. However, it is interesting to note that a lot of works have been focusing on modelling and simulating systems at the molecular scale, resulting in several software developed for students. For example, it is possible to find molecular visualisation systems like PyMol [START_REF] Schrödinger | The PyMOL Molecular Graphics System, Version 1.8[END_REF] or software that help the docking of molecules like AutoDock Vina [START_REF] Trott | AutoDock Vina: Improving the speed and accuracy of docking with a new scoring function, efficient optimization and multithreading[END_REF]. There is also an automatic plotting of protein-ligand interactions with Lig-Plot [START_REF] Wallace | LIGPLOT: A program to generate schematic diagrams of protein-ligand interactions[END_REF]. It is possible to visualise molecular interaction networks and biological pathways thanks to software like CytoScape [START_REF] Shannon | Cytoscape: A software environment for integrated models of biomolecular interaction networks[END_REF]. When focusing on DNA, a complete suite in Python can be used for the sequence alignment (BioPython -Cock et al., 2009). All these software are sources of inspiration when dealing at the cellular level.

In this chapter, the authors propose a software called NetBioDyn working like a game construction kit, where entities are located in a 3D grid environment and follow simple local transformation rules. In the name NetBioDyn, Bio stands for Biology, Dyn for Dynamic and Net comes from Internet because initially NetBioDyn was a Java Applet. Though this software is dedicated to cellular systems where several cells are in interaction, it can also model and simulate molecular mechanisms in a simple and symbolic way. The process of building models and simulations is facilitated by a graphical user interface similar to a drawing software like Microsoft ® Paint. Researchers or students can build their own models, continuously visualize a clear representation of these models, and see them evolving in time and space. The results are displayed like a chess board with moving and changing coloured entities and can be analysed thanks to recorded population curves. From the point of view of the researcher (who usually is a teacher too), the software can help to explain non-intuitive and complex biological systems in a visual way, easily understandable by his peers or students. The authors present in this chapter the key principles of the software in rigorous but comprehensive language and develop three examples coming from real biological systems.

The first example is a predator-prey system involving two bacteria. The second one simulates the mechanism of oxygen exchange in the zebra fish gills between water and blood. The third one simulates the blood coagulation mechanisms in a small section of a vein. A discussion is then engaged to show the interests of such software as well as the limits and drawbacks. A qualitative survey is also presented to show how students in biology and students in computer sciences have received the software. After the conclusion, different perspectives are presented in order to improve both the software and its use.

BACKGROUND

The use of computers in teaching biology can be divided into three common practices:

1. The development of models and simulations using a programming language like C++, Python or Java. This practice is powerful but takes time and requires advanced programming skills. 2. The use of customizable software, where students work on pre-existent models and can only change some parameters in simulations. This approach is very easy to use with students, but is not as efficient as building their own models. 3. The use of modelling software to help students develop their own models without any programming skills.

This third practice requires though the development of complex software that simplifies the process of modelling, by proposing for example, a graphical representation and construction of virtual agents, their behaviours and their environment.

Naturally, these three practices can also be found in the use of Multi-Agent Based Simulations and agent-based software in teaching biology. A quick overview of:

1. Agent-based modelling software that allow the development of models and simulations thanks to a programming language, 2. Agent-based modelling software that propose pre-made simulations, or 3. Computer aided-design modelling software is presented here.

A more complete review of agent-based environments has been made by [START_REF] Nikolai | Tools of the trade: A survey of various agent based modelling platforms[END_REF], where more than 50 platforms are classified and discussed. Readers who wish to deepen the potential of the multi-agent approach for the simulation of complex systems can refer to the book edited by Weiss (2000), especially the chapter "Search Algorithms for Agents".

Agent-Based Software in Biology

Programming Languages NetLogo [START_REF] Wilensky | Netlogo. Center for Connected Learning and Computer-Based Modeling[END_REF] is one of the most well-known software allowing the development of agent-based programs, including simulations. It has a simplified programming language and simple mechanisms to create interfaces. This software is widely used in the community of biologists and many biological systems have been developed thanks to it. It has also been specifically used to help students understand the mechanisms behind complex systems [START_REF] Stroup | On the embedded complementary of agent-based and aggregate reasoning in students developing understanding of dynamic systems[END_REF][START_REF] Jacobson | Complex systems in education: Scientific and educational importance and implications for the learning science[END_REF]). Nevertheless, pupils or students have to learn a programming language if they want to create their own models [START_REF] Ginovart | Discovering the power of individual-based modelling in teaching and learning: The study of a predator-prey system[END_REF][START_REF] Gkiolmas | Using simulation of Netlogo as a tool for introducing Greek high-school students to eco-systemic thinking[END_REF]. One can also mention AgentSheets [START_REF] Repenning | Agentsheets: A medium for creating domain-oriented visual languages[END_REF] and AgentCubes [START_REF] Repenning | Agentcubes: Enabling 3d creativity by addressing cognitive and affective programming challenges[END_REF], which are simple programming environments allowing middle school pupils to learn programming in an appealing manner. These software are designed for multi-purpose applications and mostly games. They are based on a multi-agent system where behaviours are created by drag and drop condition-action algorithms. Although the programming is easy, some code is still required. Among generic multi-agent platforms, one can cite Breve [START_REF] Klein | Breve [computer software[END_REF][START_REF] Klein | 3D Multi-Agent Simulations in the Breve Simulation Environment[END_REF] and Repast [START_REF] North | Experiences Creating Three Implementations of the Repast Agent Modeling Toolkit[END_REF]. Despite the fact that they have integrated development environments, the creation of models and simulations needs the knowledge of a programming language like Python, Groovy or Java. More recently, Biocellion [START_REF] Kang | Biocellion: Accelerating computer simulation of multicellular biological system models[END_REF] allows accelerating discrete agent-based simulation of biological systems with millions to trillions of cells. It uses cluster computers by partitioning the work to run on multiple compute nodes. It requires though mathematical modelling backgrounds and C++ programming skills.

Pre-Maid Simulations

Different simulations of multi-agent systems have been developed with NetLogo. The community models website of NetLogo proposes, for example, a customizable simulation of a predator -prey -poison system with 11 parameters: initial number rabbits and coyotes, rabbit reproducing probability, grass regrowth time, poison quantity, etc. [START_REF] Jenkins | Tools for critical thinking in biology[END_REF]. Concerning the simulation of multicellular systems, one can cite VirtualLeaf [START_REF] Merks | VirtualLeaf: An open-source framework for cell-based modelling of plant tissue growth and development[END_REF] which allows the simulation of tree-like structures based on agent representing cells and regulation network. It includes 12 different models and about 60 parameters that can be adjusted (e.g. cell mechanic or mathematical integration parameters).

Computer Aided-Design Software

In addition to a simplified programming language, NetLogo provides a "System Dynamic Modeler" that can be used to represent the dynamic of the system, entities inter-relations, feedback loops, flows and stocks. However, this tool requires a global understanding of the system (that is often missing with an agent-based approach) and is quite difficult to use as an intuitive modelling tool. Ioda (Interaction-Oriented Design of Agent simulations) and Jedi (an implementation of the Ioda concepts), allow the creation of multi-agent simulations in a very simple manner (without any coding skill), where predefined interactions can be added between agents [START_REF] Kubera | Interaction-oriented agent simulations: From theory to implementation[END_REF]. As Jedi is a demonstration software, it cannot be used to create complex simulations (4 agents maximum can be manipulated at the same time and there is no graphical user interface to precisely build the initial state). AnyLogic (XJ Technologies Company Ltd., 2012) is a multipurpose simulation software with a visual development environment. It has pre-built object libraries allowing users to create models by a drag-and-drop of elements. Its generic architecture makes it a powerful software but it could be relatively complex to understand for some students, especially the secondary ones. Another very interesting human-computer interaction is developed in the SimSketch software [START_REF] Bollen | Simsketch: Multiagent simulations based on learnercreated sketches for early science education[END_REF]. In this approach, the user draws the agents using an integrated paint tool then adds a name, a type and different pre-defined behaviours. This software focuses on primary and early secondary school students whereas this work focuses on the end of the secondary school to the university. Note that, this tool is not yet totally usable to create multicellular systems because there is no if...then...else structure. The software called CompuCell3D [START_REF] Izaguirre | Compucell, a multi-model framework for simulation of morphogenesis[END_REF] allows the simulation of multicellular systems with a user-friendly interface. The Python programming language can be used to create models but an XML file can also be edited to create simulations without coding. SimBioDyn [START_REF] Ballet | The Biodyn language and simulators, application to an immune response and E. coli and phage interaction[END_REF]) is a software based on a hybrid multi-agent and mass-spring system designed to graphically create multicellular systems. Although rich in features (cell deformation, migration, adhesion and differentiation, molecular production and consumption and configurable through scripts in Python), it remains hard to use by non-specialists without a course of several hours [START_REF] Ballet | The Biodyn language and simulators, application to an immune response and E. coli and phage interaction[END_REF].

Among computer aided-design software, there are also some interesting works that have focused on modelling biological systems following other bottom-up or top-down approaches. For example, one can cite Virtual Cell [START_REF] Shin | Virtual cell: A general framework for simulating and visualizing cellular physiology[END_REF], a software allowing to model intra-cellular mechanisms thanks to differential equations. It has a rich web-based Java interface to specify compartmental topology and geometry, molecular data and interaction parameters. However, the purpose of this software is to simulate a single whole cell or sub-parts of a cell but not multicellular systems, and it is not fitted for non-specialist users as advanced skills in mathematics are needed.

In this chapter, the authors focus on teaching pupils or students with no programming knowledge complex biological systems, such as multicellular systems.

In this context, the interests of using computer aided-design software are multiple :  The student do not focus on how to program but on what to model (they remain in the field of biology).  They cannot make syntactic or lexical errors: their models are always functional despite the fact that they can make semantic errors.

 They are no longer in charge of just some simulation parameters, but become the main actors of the model building, thus favouring the building of their knowledge.  The teacher visualizes quickly where a student has insufficient knowledge.

So what is needed is a modelling software designed to be used by students with no programming knowledge and dedicated to agent-based multicellular systems modelling and simulation. However, this survey shows that many computer aided-design software exist, but to our knowledge none of them are intuitive enough to be used in this context. In order to answer these issues and give students the ability to easily create their own models, the authors have developed the software called NetBioDyn.

Reasoning About Complexity

Presenting essential concepts on system dynamics has become very important for students in biology. Teaching and reasoning about complex systems still raise a lot of pedagogical issues as shown in particular by [START_REF] Jacobson | Complex systems in education: Scientific and educational importance and implications for the learning science[END_REF]. [START_REF] Lynch | Reasoning about complexity -software models as external representations[END_REF] argue that grasping the complexity requires a representational framework able both to describe executable computer models and to support reasoning as a simply readable "external representation", as opposed to internal representations that are the user's mental models [START_REF] Zhang | Distributed cognition, representation, and affordance[END_REF]. According to them, a good external representation affords the classic scientific approach, called abduction, emphasizing the observation, the build of hypothesis and the tests to verify the relevance of assumptions [START_REF] Houser | The Essential Peirce: Selected Philosophical Writings (1867-1893[END_REF]: it promotes the exploration and understanding of a phenomena thanks to a practical approach. It should be too constructed by the students themselves for two principal reasons: the first one is that it improves their learning (better memorization, quasi-physical experimentation of the model and appropriation of fundamental mechanisms) and the second one concerns the amelioration of their self-commitment [START_REF] Prain | An exploratory study of teachers and students use of multimodal representations of concepts in primary science[END_REF]. Lynch and Ferguson define an ideal representation as "some written, external representation to complement user's internal representations [...], producing an external cognitive artefact which facilitates exploration and discovery [...] while also offering the ability to be executed".

Lynch and Ferguson summarize the 9 properties of a suitable external representation that were previously defined by [START_REF] Zhang | Distributed cognition, representation, and affordance[END_REF]:  Short-term or long-term memory aids.  Directly perceived information.  Knowledge and skills that are unavailable internally.  Support for easy recognition and inference.  Unconscious support for cognitive behaviour.  More efficient action sequences generated.  Facilities to stop time and make information visible and sustainable.  Need for abstraction reduced.  Aids to decision making through high accuracy and low effort.

Following these properties, the authors claim that NetBioDyn, thanks to its graphic interface and its simulation tools proposes a suitable external representation. It gives to students and teacher a simple way to create and experiment and test models of biological systems, while providing at any time a simplified and complete view of the system's state.

More generally, readers who want to improve their knowledge on "learning by doing" in virtual environments (VE) can read the book of [START_REF] Aldrich | The Complete Guide to Simulations and Serious Games[END_REF].

NETBIODYN, A PEDAGOGICAL AND INTUITIVE AGENT-BASED SOFTWARE

NetBioDyn is a fully open source Integrated Development Environment (IDE) dedicated to teaching activities in biological complex systems, mainly at the cellular level and secondarily at the molecular scale. It gives the possibility to teachers and students to create simulations of multicellular and multi-molecular systems in a simple and visual manner. NetBioDyn does not require any skill in computing and lays on the agent-based approach. Besides being simple to understand for students, this approach allowed the authors to design an intuitive graphical user interface to easily manipulate the agent-based concepts: entity, behaviour and interaction.

In this section the graphical user interface of the software is first presented. Then, the section goes inside the software architecture with the description of the entities populating the simulated environment and how they can evolve thanks to algorithmic behaviours (movement, differentiation, division, apoptosis, etc.). In the next section, three examples of easily reproducible simulations are detailed. The code and the executable (for UNIX, Mac and Windows Operating Systems) are available for download on the website http://virtulab.univ-brest.fr.

Graphical User Interface

For educational purpose, the design of a graphical user interface is a crucial point. For the student or the teacher who creates a simulation it must be:  Intuitive, to prevent the user from being lost in multiple buttons or lists.  Logic, to build a structured simulation.  Clear, to show important data and hide less important ones.  Accessible, to concentrate on "what to simulate" instead of "how to simulate".  Complete, to have a powerful tool that can simulate advanced biological behaviours.  Attractive, to stimulate student's imagination and motivation.

For the teacher who uses the software in a course, it must:  Be robust, avoiding the teacher to help students in case of inappropriate action (for example, no source code is required, avoiding student to make syntax mistakes -only semantic errors can be made, which are the most relevant ones to test the student comprehension of the modelled biological system).  Show relevant information, to quickly see where each student is and if he is mistaken.  Allow a short learning curve, not to spend more than one hour to explain how the software works.

To try to achieve these points, the authors decided to use Multi-Agent Based Simulations (MABS) to guide the development of the graphical user interface. MABS are naturally close to how biological objects like cells are described, reducing the abstraction needed to make simulations. In this chapter, the authors use the term "entity" to represent biological objects (or group of objects) and the term "behaviour" to explain how the entities evolve in time. The word "environment" is used to represent the space where simulations occur. A good analogy can be done with board games like chess: an entity is a piece, a behaviour is a game rule, the environment is the board and the initial state of the simulation corresponds to the initial positions of the pieces.

Figure 1 shows the different parts of the interface. The first part of the graphical user interface is made of a list of entities, followed by a list of behaviours and then a button to change the environment's properties (such as size and textual description). The position order of the two lists is logic: entities must be defined before their behaviours. Nevertheless, note that a new entity or a new behaviour can be added, changed, renamed or removed at any time by the user to support the creation process which is rarely linear. The environment button is located below the two lists because the default properties do not change frequently.

Figure 1. NetBioDyn graphical user interface

The second part of the graphical user interface is the placement and the display of entities in their environment. A central panel serves as a paint area where entities can be individually or collectively located or removed thanks to classic drawing tools like pen, spray, line and eraser, plus a random initializer tool. Entities are located in several layers that can be displayed or hidden using the Z slider. The simulator is controlled by three buttons:

 Play (a green right arrow),  Play one step (an orange right arrow), and  Stop (a red square).

The simulator can also be paused at any time to observe a specific state or make a screen capture, and its speed can be reduced or increased.

The third part displays the population curves of entities evolving in real time. Several curves can be displayed at the same time to compare their values according to the simulation steps.

The user can also display several population curves according to a specific entity (for an example, see next section Examples).

The fourth part enables the user to change miscellaneous properties and export simulation data in the well-used formats in Biology CSV (spreadsheet) and R programming language. A tool to automatically adjust the simulation's parameters according to in-vitro results is a work in progress and will be available soon.

The fifth and last part display in a specific frame the environment in 3D in real-time.

In the next subsection, the NetBioDyn entities are described in details.

Entities

An entity in NetBioDyn is a simple cube of size 1 x 1 x 1, located as a grid element of the environment (which is described in details below), having a unique name and a unique colour.

Other forms (triangle, disc, star) or images can also replace the coloured cube.

An entity also has a half-life parameter indicating its speed of degradation or destruction.

For each entity, a short description can also be added. This is made for two main reasons. The first is to encourage students to comment their models because they will have to maintain and share their work. The second reason is to help students to understand pre-made models that the teacher created.

Finally a cleanable property can be unselected to prevent entities from being removed when the environment is cleaned by the user. This is useful when the teacher created a simulation where the initial state contains a minimum of entities located at specific positions: the student can clean his own entities but the teacher's ones always remain.

The entity configuration window can be seen on Figure 2.

Figure 2. The name, the half-life and the appearance of an entity is made in the entity configuration window. Note also the description field on the right and the cleanable checkbox at the bottom-left

In the following sub-section the behaviours allowing entities to change their states are explained.

Behaviours

In NetBioDyn, a behaviour aims to change entity's states. For example an entity can be put in motion, differentiated or destroyed. Four parts are required to define a behaviour, three conditions and one action: The first condition identifies all entities that are involved in the simulation. Only those that are in a good position from each other are kept (condition two). Thanks to the third condition, a behaviour is probabilistically performed: a random number between 0.0 and 1.0 is generated and must be inferior to the probability of the behaviour.


If the conditions are validated at different areas in the environment, a behaviour applies several times during one simulation step. Conflicting areas are detected where a same entity can be used two or more times by behaviours. In this case, only one area is randomly chosen among the conflicting areas (see Figure 3). 1), a behaviour can be applied several times during one simulation step. In this example the system detects that the entities A and B are in contact. The probability to perform the behaviour, if the entities are found in contact, is 0.8. So, of the six areas where the behaviour can be performed, four are kept (continuous circles) whereas two are not (dotted circle). Note that this area configuration can change accordingly to the random numbers generated. Moreover notice that three areas are in conflict and must be treated before the action can be applied (continuous circles including the same entity A). In (2), the system manage the conflicting areas. Among them, only one can be kept (the horizontal continuous circle) whereas the two others cannot. All conflicting areas have the same probability to be kept (or not kept). Note that the probabilities of behaviours have already been validated before the conflicting areas are treated. Finally, only two areas will apply the behaviour (continuous circles)

In order to ease the design of behaviours, the authors created a graphical representation consisting of two main parts (see Figure 4). The first part containing three lines indicates the behaviour's name, its description and its probability to occur. The second part is divided in three columns: the left one contains the entities involved in the behaviour (reactive), the middle one indicates where the entities are located one from each other and the right column indicates how entities are changed. In the software NetBioDyn, the graphical user interface is very close in terms of displayed data. The entities are selected thanks to a combo-box containing all the created entities. The positions are selected by clicking on the light or dark squares. The cross at the left allows the user to remove a full line of reactive and products (see Figure 5).

The next subsection describes the environment, where entities are placed and behaviours occur.

Environment

The environment represents a 2D or 3D space where entities evolve and behaviours take place. It is a simple grid where a grid cell contains none or a maximum of one entity. An entity occupies a whole grid cell. It follows Von Neumann neighbourhood: it has four neighbours in 2D and six in 3D. The size of the environment is by default 100 x 100 x 2 but can be changed by the user. The view is only 2D when the user put, move or remove entities but a 3D view can be activated for a better and more intuitive rendering.

From the principles presented, the next section develops three examples that can be realised by pupils or students Figure 5. The graphical user interface of behaviours in NetBioDyn has the same properties as seen previously. In this example, an entity A is removed from its current position (first line of the lower part), to be placed at a free location (second line). The third line contains the symbol * as reactive (which means anything) and the symbol -as product (which means do nothing). This behaviour applies a random walk to all A entities in the simulation

EXAMPLES

The examples detailed in this section can be performed using the software NetBioDyn freely available at http://virtulab.univ-brest.fr.

It can be made by pupils from age 14 to university students. The first example deals with a prey-predator system involving two species of bacteria: Bdellovibrio and Photobacterium leiognathi. The second example models the dioxygen exchanges between water and the blood of zebra fishes. Finally, the third one aims to reproduce and understand the blood coagulation mechanisms.

These examples show to the students how to create a model in four stages:

1. The next sub-section expose in details the process of modelling three cellular and molecular systems, following these four stages from the real system to the simulation.

Bdellovibrio and Photobacterium Leiognathi

Real System

Bdellovibrio and Photobacterium leiognathi are marine bacteria. The interactions between these two bacteria represent a good example of a predator-prey system. Bdellovibrio is a predator of Photobacterium leiognathi. It penetrates inside its prey, proliferates, kills the host and finally releases its progeny. This cycle time is about 4 hours. Bdellovibrio is a bacterium of 1 µm in size and thanks to its flagellum, moves very fast (up to 160 µm/s). The size of Photobacterium leiognathi is about 2 µm. They usually are in symbiosis with fishes and, in this case, have not shown to be motile.

Biological systems involve too many parameters, objects and behaviours to be fully modelled and simulated. A simplification of the system described here is needed in order to focus on the predator-prey principles.

Simplification

In order to reproduce the Bdellovibrio and Photobacterium leiognathi relationship, a simplified model which takes into account five objects and five behaviours is proposed: This model has to be also adapted to our simulator. The next section explains how to put the model in the software NetBioDyn, which has its own possibilities (i.e. multiple entities and behaviours) and constraints (i.e. the environment is a 3D grid and a grid element has a maximum of six neighbours).



Model

The entities chosen for the simulation are Bdel, Leio and LeioInfected. The fish tissue and the nutriments are implicit in our simulation. This is a choice which can be changed if the fish tissue or the nutriments must be quantitatively taken into account or if their spatial distribution has to be studied. The graphical representation used for entities are simple coloured cubes of volume 1 µm 3 . In this example Bdel is red, Leio is blue and LeioInfected is purple. Bdel and Leio have a half-life of 100 simulation steps (which means that after 100 simulation steps a Bdel or a Leio entity has 50% of chance to die, or said differently, after 100 simulation steps for a non-reproductive population of N individuals, only N/2 individuals will remain).

Four behaviours have been kept to simulate the bacterial system (see Figure 6):

1. The movement of Bdel entities which is a simple 3D random walk. The probability of this behaviour is 1.0, the maximum possible, because no other behaviour is as fast as this one.

The bibliography gives the speed of 160 µm/s for Bdellovibrio. This is a maximum and an instantaneous speed. Due to its frequent directional changes, its average speed is closer to few µm/s. A grid cell can contain one bacterial entity at the same time, so a grid cell represents a cube of 1 x 1 x 1 µm 3 . 2. The infection of Leio by Bdel. The probability of infection is 0.1, indicating that one contact over ten can produce an infection. 3. The lysis of Leio and the release of two Bdel. The probability is chosen to reproduce the 4 hours of incubation for Bdel. A time step is equivalent to one second, so 4 hours are simulated by 14400 steps. At this time, this is supposed that 99% of the LeioInfected have been killed. 4. The division of Leio following the nutriment intake.

The environment is a 100 x 100 x 2 grid. All the Leio entities are at z=0 in order to imitate the fact that they are on the fish tissue.

Figure 6. The four behaviours described using the previously seen representation

Simulation and Results

The initial state of the simulation is given by Figure 7. The initial state is made of 1000 Leio entities and 100 Bdel entities randomly located in the environment. Leio entities have been placed at z=0 while Bdel entities are located at z=1. The number of preys is ten times inferior to the number of predators in order to initiate the system without having the preys eaten by too numerous predators at the beginning. They all are located at random in the same 3D environment. [START_REF] Odum | Fundamentals of Ecology[END_REF]).

The simulation expresses classical cycles of predator-prey systems, indicating that the results are qualitatively correct.

Water-Blood Dioxygen Exchanges in Zebra Fish

Real System

Zebra fishes have an efficient respiratory organ able to extract dioxygen from the water to their blood. Their gills use a counter-current system to improve the dioxygen exchange. Figure 9 represents how the system works. The water contains dioxygen molecules which circulate from the left to the right. A permeable membrane, that only gazes can cross (dotted line), separates the blood from the water. The dioxygen can cross the membrane from the water to the blood or from the blood to the water with exactly the same probability. In the real system, the blood circulates in the opposite direction. However, by using the simulation, the benefits of such mechanism will be studied as compared with the co-current one. The simulation will aim to evaluate the impact of the current direction (counter-current co-current) on the blood oxygenation.

Figure 9. Mechanisms of dioxygen exchange inside the zebra fish gills

Simplification

The simulation focuses on a small part of the system of the Zebra Fish, where the dioxygen exchanges occur. The red blood cells responsible for the transport of the dioxygen in the blood are not modelled, because this mechanism occurs essentially after the exchange. Other blood components, like immune cells for example, are not modelled because they do not interfere in the dioxygen exchange.

Model

The model is made to test the efficiency of the zebra fish counter-current respiratory system where the O 2 is central. The chosen model has three types of biological entities, the O 2 in various states, and two membranes:

1. The O 2 is divided into three types of entity in order to give them different behaviours and count them according to their locations: o The O 2 in water (O2Water). o The O 2 in blood (O2Blood). o The O 2 in water which can no longer go to the blood (O2WaterLost) because it has been evacuated outside the respiratory system. 2. The permeable membrane that can be crossed by the O 2 (Membrane).

The impermeable membrane (Wall).

To complete the model, four dedicated types of entity have been used: 1. Entities O2WaterIn, which perform the addition of O2Water thanks to the behaviour called O2WaterGetIn. 2. Entities O2WaterOut, which remove O2Water thanks to the behaviour O2WaterGetOut. 3. Entities O2BloodOut, which remove O2Blood thanks to the behaviour O2BloodGetOut. 4. Entities O2WaterLostBorder, which detect O2Water entities that can no more go into the blood thanks to the behaviour O2WaterIsLost.

Figure 10 shows how entities are located in their grid environment at t=0.

Figure 10. The gill model at its initial state (t=0)

Only two biological entities are placed: the impermeable membrane (Wall) and the permeable membrane (Membrane) which creates the upper row of blood circulation and the lower row of water circulation. There is also the four ad-hoc entities (non-biological entities). Note that the O 2 is not present at t=0 but will be added at the right to the ad-hoc entities O2WaterIn. When O 2 entities in the water diffuse to the right, they can cross the Membrane to go in the blood.

The O 2 in the blood can also go back to the water by crossing again the Membrane. The O 2 entities in water reaching the O2WaterLostBorder can no longer cross the Membrane, and they become lost for the blood (O2WaterLost). The region between O2WaterLostBorder and O2WaterOut only contains O2WaterLost entities that will be counted to test the efficiency of the current and counter-current mechanisms. The O2BloodOut are located at both left and right sides of the upper row in order to evacuate the O 2 in the blood whatever the direction the current follows.

Nine behaviours have been made to add movement, membrane crossing, transformation, creation and removal of entities. O 2 entities move up, down or right at random in water at each simulation step (probability set to 1). The same mechanism is used to define the movements of O 2 in blood and O2WaterLost entities. Note that this behaviour can be modified by changing the left direction by the right, giving the possibility to test the impact of the O 2 transfer efficiency from the water to the blood according to the relative direction of both flows.

Figure 11 shows how the O 2 crosses the membrane. The behaviour indicating how the O 2 entities in water become lost for the blood is described in Figure 12. Finally, Figure 13 shows the only one behaviour that adds entities in the environment. It creates O2Water entities just on the right of O2WaterIn entities with a probability of 0.1. It means that one time step over 10 (on average), one O2WaterIn adds one O2Water (if there is an empty space at its right). The same mechanisms are used to define two more behaviours: the behaviour removing the O 2 entities in the water that are too far from the membrane to be useful for the blood (O2WaterLost), and the behaviour removing the O 2 entities in blood (probabilities at 1). Defining these behaviours led to create dedicated entities O2WaterIn, O2WaterOut and O2BloodOut that do not exist in the real system. They only are here to simulate the continuous flow of O 2 in the water coming from the left and disappearing on the right, when they go out of the simulation area.

Simulation and Results

The simulation using the counter-current behaviour is shown as an example of the dynamics of the gills (see figure 14).

The counting of O2WaterLost gives the efficiency of the system and shows that, for the given initial state and the given behaviours' parameters, the co-current mechanism is about 42% worse in O2WaterLost as compared with the counter-current one. To evaluate the benefit of the counter-current direction as compared with the same current direction, the number of O2WaterLost has to be counted when the simulation is in a relative permanent state. To calculate when the permanent state arises, we need to know how long it takes for the O 2 newly created in water to cross the entire lower compartment. By looking at the behaviour of O2Water (normal or lost), it is clear that the right movement occurs, in average, one time over three (the two other possible movements are up and down). The length of the compartment is about 100. So, at least, 300 time steps are needed for the O 2 in the water to run through the lower compartment. Moreover, the O 2 can cross the membrane and go back to the left, following the blood flow. About 3/4 of the compartment have the permeable membrane, slowing down the movement of the O 2 in the water. Because this is a stochastic simulation, only probabilities can be calculated. The chosen criterion is arbitrary set by looking at the curves of O2LostWater concentration and by choosing a time from which the state looks permanent enough. The average number of O2LostWater is calculated between 1000 and 4000, which seem consistent (see Figure 15).

Blood Coagulation

Real System

The real system simulated in this example is a small section of a vein, in which a lesion is present. The aim of this model is to reproduce some of the molecular and cellular mechanisms during the blood coagulation leading to the formation of a blood clot. Three stages are usually described. The primary hemostasis starts with the vein lesion and finishes with the formation of a plug covering the lesion. The plug is made of platelets and soluble rod-like shaped proteins called fibrinogen. The secondary hemostasis is the transformation of the platelets plug into a blood clot thanks to the conversion of the fibrinogen into insoluble strands called fibrins. The third and final stage is the fibrinolysis, when the clot is broken down.

Model

The model presented here includes the primary hemostasis but not the secondary one nor the fibrinolysis. Moreover, not all the known mechanisms are simulated to improve the model clarity. The model is described using all the involved entities (cells, molecules and others), their initial state (stored into a 2D matrix) and their behaviours (interactions, transformations, creations and blood flow).

Two types of entities can be distinguished. The first ones are those which directly represent real biological entities like molecules or cells:

1. Fibro (for the fibroblast cells). 2. Endo (for the endothelial cells).

3. PlaC (for the circulating platelets). 4. PlaF (for the fixated platelets). 5. Fibri (for the fibrinogen molecule).

The second ones are those which do not exist as such, but are needed to simulate abstract biological mechanisms, like the blood flow in this case:

1. FlowS (for start of the blood flow). 2. FlowE (for end of the blood flow).

The initial state looks like a rectangle in which the upper edge consists of one layer of endothelial cells. The lower edge contains one layer of endothelial cells (with a discontinuity representing the lesion in the vein) plus one layer of fibroblast cells, below the endothelial layer. The left edge is made of entities regulating the blood flow entrance and the right side consists of entities regulating the blood flow exit (see Figure 16).

The behaviours developed in this simulation aim to model the blood flow and the core mechanisms of primary hemostasis. Firstly, five behaviours are needed to model the blood flow (see Figure 17) :

 One behaviour to model the apparition of the platelets coming from the left of the vein section.  Two behaviours to model the blood flow circulating from the left to the right which are applied to the platelets (PlaC entities) and the fibrinogens (Fibri entities).  Two behaviours to model the disappearance of the circulating entities (PlaC and Fibri) when they reach the right of the vein section.

Secondly, three behaviours are needed to model the coagulation (see Figure 18):

 The first behaviour models the fixation of circulating platelets on the lesion (on the fibroblasts).  The second one models the fixation of circulating platelets on the plug of platelets in presence of fibrinogens.  The third behaviour models the indirect production of fibrinogens by fibroblasts. Note that this last behaviour is a simplification of a more complex molecular pathway.

The end of the growth of the platelet plug is not modeled thanks to a behaviour but emerges from the simulation. More precisely, when all the fibroblast cells are covered with the anchored platelets, they simply cannot produce fibrinogen, stopping the growth of the plug.

Simulation and Results

In the simulation, 1 step corresponds to 1 second. The size of the vein is about 3 millimeter long and 1 millimeter large. As outputs, the shape of the plug is observed and the quantity of circulating fibrinogen is measured at each time step (see Figure 19).

The simulation shows that the plug of platelets starts after 139 steps (2 minutes and 19 seconds) and ends at step 254 (4 minutes and 14 seconds). After this step, no more fibrinogen entity is produced because the fibroblasts are no more in contact with the blood flow. The remaining fibrinogen disappears at the right of the vein section. The simulation is stopped at 360 steps, when all fibrinogen entities have disappeared.

With such a model, it could be possible to use the results of different simulations to build a synthetic and formalised mathematical model of the primary hemostasis. The virtual experiments can be performed quickly and at a very little price. Another interesting feature of such a model is that during a simulation it is possible to create new lesions, change the size or the shape of lesions, modify the platelet concentration, etc. The user can experiment many different scenario and hypothesis and see the validity but also the limits of the model.

DISCUSSION

Here, the authors discuss the interests and the drawbacks of NetBioDyn.

NetBioDyn Interests

The use of software in biology and education is interesting, both for teachers and students. It enables teachers to explain complex systems in an intuitive and pseudo-experimental way. It also helps students to create their own computational biological systems and see the important stages by creating a virtual system that rebuilds the real system. They can learn efficiently how the real system works.

From the teacher point of view, the modelling and simulation using such a software enable to:

 Create explicative and predictive simulations which can be easily handled by students  Teach the students how to "program" complex systems with very little knowledge in computer sciences.  Improve the learning curve of students.  Stimulate students' creativity.  Quickly find out which students have assimilated the course and which have not.  See where, in the system, a student is right or wrong.

For the students, NetBioDyn gives the possibility to:  Build or explore biological systems in an intuitive way with entities, behaviours and environments.  Focus on the main mechanisms of a system and acquire a synthetic view.  Pay attention to important mechanisms even if they look like details.  Learn partially by themselves what is important and what is negligible.  Organise their data and knowledge.  Play at a motivating construction-like game.  Explore the impact of parameters or behaviour variations in a simple way.  Show the teacher what is their comprehension or misunderstanding of the real system.  Share their knowledge with other students in a formal way.

A survey of 30 students (between 22 and 25 years old) has been made to assess the interest of the use of NetBioDyn in class. The results are presented in Figure 20. What is noteworthy is that biologist as well as computer scientist students are mostly interested by such an approach. The question of ease of use for NetBioDyn obtains the most "Very Good" answers for the two master students. Note that this survey is anonymous and that no teacher was present. This software has also been successfully used by pupils (between 14 and 16 years old) of the middle school Max Jacob in Quimper (France) in May 2011.

NetBioDyn Drawbacks

The limitations of NetBioDyn can be divided into two kinds. The first concerns the multiagent approach itself and the second specifically concerns the software.

Multi-agent systems involve many interacting agents. This usually requires powerful computers, in term of computation and memory, to perform all the entities and their interactions. NetBioDyn reduces this problem by only implementing algorithms of complexity N+B (where N is the number of entities and B the number of behaviours). This is possible because the simulator only uses a small local neighbourhood on a grid. Another problem with multi-agent systems is the number of parameters that can be very important. The simulations made with NetBioDyn could become difficult to control and understand if too many types of entities and behaviours are added. Usually the authors recommend to their students not to add more than 20 types of entity or more than 20 different behaviours. Note that a type of entity is not an entity: a type of entity is a prototype that can be instantiated many times into entities without any problem of parameters.

Regarding the software limitations, the most important one is the entity shape that can only be a cube, implying that the simulations cannot be multi-scale. This last point can be partially circumvented as seen in all the presented examples where molecules, cells and tissues are mingled. For instance, an entity can represent far more than just one molecule, but a group of molecules. An entity can represent a single cell, but also a part of a tissue. What is important here is that an intrinsically multi-scale problem can generally be flattened. Moreover, the software is adapted to their skills (no code is required). Finally, the course on modelling and the software interest them and are useful for their studies

CONCLUSION

The simulation of complex multi-cellular systems using computers represents a great challenge, both scientifically and technically. Scientifically, it serves the comprehension of fundamental mechanisms governing cells, from single-cell behaviours to whole systems involving numerous interacting cells.

Technically, the creation of computational models imitating multicellular systems requires advanced computational skills. This is why the authors have developed and presented in this chapter a software making it accessible for non-computer specialists by simplifying the process of modelling and simulation.

This simulator is made to create and manipulate models whereas most of educational software are already-made models that researchers or students can test by only changing some parameters or initial state (see for example the simulator presented in [START_REF] Meir | How effective are simulated molecular-level experiments for teaching diffusion and osmosis?[END_REF]).

Three simulations have been presented to show the diversity of models that can be done and to explain how they can be made.

To support this statement, this software has been evaluated by pupils of middle school and higher education students, especially those in the field of biology.

The interest of this software has been discussed to bring out both positive contributions like focusing in what to model instead of how to model but also negative ones like the absence of multi-scale entities.

The perspectives are multiple and can be divided into two parts. Firstly the software itself can be improved. One of the most important features could be the possibility to factorise similar behaviours into one. This could be performed for the entities by adding generic behaviours like Random Walk. Another one is to increase the number of graphical tools to quickly draw shapes of entities like squares, circles or filler. The authors are also working on a selfadjusting system to find the proper values for all the parameters involved in a simulation (behaviours' probabilities, entities half-lives etc.), in order to stay close to real results obtained for example in vitro.

Secondly, in terms of communication between NetBioDyn users, the main point to address will be the development of an internet social network where researchers, students and teachers will share their works, models and experiences (a starting professional network can be found at http://lefil.univ-brest.fr then NetBioDyn group).

Figure 3 .

 3 Figure 3. In (1), a behaviour can be applied several times during one simulation step. In this example the system detects that the entities A and B are in contact. The probability to perform the behaviour, if the entities are found in contact, is 0.8. So, of the six areas where the behaviour can be performed, four are kept (continuous circles) whereas two are not (dotted circle). Note that this area configuration can change accordingly to the random numbers generated. Moreover notice that three areas are in conflict and must be treated before the action can be applied (continuous circles including the same entity A). In (2), the system manage the conflicting areas. Among them, only one can be kept (the horizontal continuous circle) whereas the two others cannot. All conflicting areas have the same probability to be kept (or not kept). Note that the probabilities of behaviours have already been validated before the conflicting areas are treated. Finally, only two areas will apply the behaviour (continuous circles)

Figure 4 .

 4 Figure4. For this example, the behaviour is read like this: "the entity A, which is the centre of the behaviour (+) must be in contact with one entity B and one entity C. B can be anywhere(up, down, left, right, front, behind) around A and C can be at the left, the front or behind A. Moreover, if the probability is validated and the possible conflicts resolved, A will become A', B will become B' and C will be changed in C' ". The first reactive is always at the centre of the reaction. A reactive or a product can be 0 which means no entity. The diagonals are not taken into account in the positions

Figure 7 .

 7 Figure 7. This screen capture of NetBioDyn shows the initial state of the simulation where 1000 Leio (triangles) and 100 Bdel (squares) have been placed at random in the environment using the random initializer tool. Only entities placed at z=0 are here visible

Figure 8 .

 8 Figure 8. Screen captures of the simulation at time steps 1490 and 12840. From left to right: the environment states, the population curves of entities Bdel (dark grey) and Leio (light grey) according to time, and the population curve of Leio according to Bdel (after change of the abscissa)

Figure 11 .

 11 Figure 11. The two behaviours of this figure indicate how O 2 entities cross the membrane separating the blood and the water. The left one concerns the crossing of O 2 in water (O2Water) to the blood (O2Blood). The right one describes the crossing of O 2 located in blood (O2Blood) toward the water. Both of these behaviours have the same probability: 0.3

Figure 12 .

 12 Figure12. This behaviour changes O2Water entities touching the O2WaterLostBorder into O2WaterLost entities. Thus, O 2 that cannot be used by the blood can be counted to evaluate the efficiency of the counter-current mechanism as compared with the current one. The less O2WaterLost entities are present, the more the gills are efficient

Figure 14 .

 14 Figure14. Three screen captures show how the system evolves when the currents are in opposition (water comes from the left and circulates to the right; blood circulates from the right to the left). At t=150, the O2Water created by the O2WaterGetIn behaviour starts to diffuse to the right of the water compartment (the lower one). The O2Blood entities that reach the O2BloodOut are removed from the simulation thanks to the O2BloodGetOut behaviour. Few O2Blood, coming from the O2Water having crossed the membrane, move in the opposite direction. At t=350, O2Water entities reach the O2WaterLostBorder. At t=2000, the system is in a relatively stable state and O2WaterLost entities can be seen

Figure 16 .

 16 Figure16. The initial state, and more generally all the simulation, takes place into a 100x28 matrix where entities are distributed according to a simple rectangle corresponding to a vein section. The vein is made-up of three layers, two of endothelial cells (Endo entities) and one layer of fibroblast cells (Fibro entities). Note that the bottom layer of endothelial cells has a hole in order to simulate a lesion, resulting in a direct contact between the fibroblast cells and the circulating blood. The two vertical edges do not exist as real biological entities but are necessary to represent, at the left side of the vein, the incoming of circulating entities (FlowS entities) like the platelets and, at the right side of the vein, the disappearing entities (FlowE entities). The flow of circulating entities moves from the left (Start) to the right(End)

Figure 18 .

 18 Figure18. The core mechanism governing the apparition of a plug of platelets is only made with three behaviours. The first behaviour (upper-left) is the creation of fibrinogen entities from fibroblast ones. In the real system, it does not occur like this, but it is a convenient simplification for this simple example. The second one is the fixation of circulating platelets that enter in contact with the fibroblast cells of the lesion. The third one, involving three reactive entities, simulates the fixation of circulating platelets onto the plug of anchored platelets, allowing it to grow

Figure 20 .

 20 Figure 20. Survey of 24 students in Master 1 Biology and 6 students in Master 2 Computer Science at the Université de Bretagne Occidentale. 10 questions have to be answered on the course they had on computational biology and on the use of the software NetBioDyn. Answers show that both the course and the software are considered important for their training.Moreover, the software is adapted to their skills (no code is required). Finally, the course on modelling and the software interest them and are useful for their studies

  Does the simulation inspire me in order to prepare real experiments? o Is the simulation robust to small changes (probabilities or initial state for example)? o Is the simulation clear enough to share and confront my knowledge with others?

	o Am I able to distinguish, among the current knowledge, what are hypothesis and what
	are facts?
	2. The Simplifications
	o What have I to keep absolutely from the real system?
	o What can be neglected?
	3. The Model
	o How to represent real entities using virtual ones?
	o How to model biological mechanisms thanks to algorithms or equations?
	o What are the dimensions and the topology of the environment and how to represent it
	on a computer?
	4. The Simulation

The Real System o What is the current knowledge? o What part of the system would I model? o What are the limits of my study (dimensions, time, energy, etc.)? o Can I trust the results? o What are the limits concerning explanation and prediction? o Are the results qualitative or quantitative? o

KEY TERMS AND DEFINITONS

Behaviour : a rule that transform or move entities in the simulated environment.

Bdellovibrio: A motile, vibrio shaped, monoflagellated, gram negative bacteria. It is a predator of Photobacterium leiognathi.

Entity:

A virtual entity representing a cell or a molecule.

Integrated Development Environment (IDE):

A software with an advanced graphical user interface (GUI) aiding the user to create other software applications.

Lysis:

The death of an entity representing a cell.

Multi-Agent System:

A set of interacting agents (also called entities). In our system, each agent has behaviours to perform simple reactive tasks.

Photobacterium Leiognathi:

A bacteria which is bioluminescent and a prey for Bdellovibrio.

ABOUT THE AUTHORS

Pascal Ballet is an associate professor in computer science. He develops software for the field of computational biology, especially at the cellular scale.

Jérémy Rivière has a PhD in computer science and has been an associate professor at the Université de Bretagne Occidentale since 2014. His research focuses on multi-agent systems (MAS) for modelling and simulating complex biological phenomena, as well as cooperative agents for resolving problems. He is also interested in interaction and cognition mechanisms for intelligent agents, and their application in complex systems, multi-agent systems and agent-based simulations.

Alain Pothet is a teacher of Biology in secondary level

Michaël Theron

Karine Pichavant is an assistant professor in animal physiology. Research on physiological mechanisms developed by animals to face with changes at several integration levels (cell, tissue, organ, organism).

Frank Abautret

Alexandra Fronville went to the university Pierre et Marie Curie in Paris, where she studied mathematics and obtained her PhD in 1986. After a post-doctoral position at INRIA, she works for a couple of years for the university of Brest. Her research focuses on viability theory and morphological analysis applied to biological shapes. She also teaches how to use computers and scientific software for young teachers.

Vincent Rodin is a full professor of computer science at the University of Western Brittany in Brest, France. His research interests include image processing, multi-agent systems, and biological processes simulation.


Mai Quyen Pham

Benoit Oudompheng
email: benoit.oudompheng@grenoble-inp.org

Jérôme I Mars
email: jerome.mars@gipsa-lab.grenoble-inp.fr

Barbara Nicolas
email: barbara.nicolas@creatis.insa-lyon.fr

A Noise-Robust Method with Smoothed 1 / 2 Regularization for Sparse Moving-Source Mapping

Keywords: Smoothed 1 / 2 regularization, Sparse representation, Proximal forward-backward, Acoustic moving-source localization, Beamforming blind deconvolution, Robustness algorithms

The method described here performs blind deconvolution of the beamforming output in the frequency domain.

To provide accurate blind deconvolution, sparsity priors are introduced with a smoothed 1 / 2 regularization term. As the mean of the noise in the power spectrum domain depends on its variance in the time domain, the proposed method includes a variance estimation step, which allows more robust blind deconvolution. Validation of the method on both simulated and real data, and of its performance, are compared with two well-known methods from the literature: the deconvolution approach for the mapping of acoustic sources, and sound density modeling.

Introduction

Blind deconvolution has a central role in the field of signal and image processing. It has many applications in communications [1], nondestructive testing [2], image processing [3, 4, 5], medical imaging processing [6], and in acoustics [7]. Moreover, in underwater acoustics, blind deconvolution methods have already been proposed to estimate simultaneously the transfer function of the environment and the unknown source signal in multipath underwater sound channels [8,9,10]. In many realistic scenarios, the blurring kernel (or the system) is imprecise or not known. Thus, the deconvolution problem becomes blind and underdetermined, and often requires additional hypotheses.

One possible additional hypothesis is the sparsity of the signal, which is an extensively studied topic in signal processing. The main idea is to find the 1 In this paper the terms "source localization" and "source mapping" are equivalent. These refer to the goal of the paper, which is to map noise sources inside a global vehicle (here a boat) during a pass-by experiment. regularization is applied to jet noise-source localization [33]. The sparse distribution of sources is also commonly used, as in [START_REF] Suzuki | L 1 generalized inverse beam-forming al-8 gorithm resolving coherent/incoherent, distributed and 9 multipole sources[END_REF]34,35,13,36,37,[START_REF] Chen | Sparse Representations for Multi-104 ple Measurement Vectors (MMV) in an Over-Complete 105 Dictionary[END_REF]. These methods were developed for fixed-source localization and have not currently been extended to moving sources.

The goal of the present paper is to propose a new blind deconvolution method that is applied to BF-MS results to improve moving-source mapping.

The strategy is to formulate the forward problem as an optimization problem, with constraints that are derived from the physical context. The proposed cost function contains several parts: (i) a data-fidelity term that accounts for the noise characteristics; (ii) the smoothed 1 / 2 ratio [18] that promotes sparsity in the moving-source locations; and (iii) the knowledge of some physical properties of the sources and the system, and of the variance noise, introduced through indicator functions.

Observation model

Beamforming for moving sources

Beamforming for moving sources compensates for the Doppler effect and back-propagates the pressures measured by the M sensor array to a calculation grid of N points, which correspond to the possible source locations. We consider the classical case of pass-by experiments, in the far-field, with sources that share the same global movement and have low

Mach numbers,

--→ M a 1. For these conditions, some assumptions can be made over short time intervals of duration T , which are referred to as snapshots [20], whereby:

1) The sources are in fixed positions;

39

2) The Doppler effect is negligible at the frequen-

57

This defines the vectors:

58 Pk = (p k 1 ) , (p k 2 ) , . . . , (p k T ) ∈ R M T , Pk = ( pk 1 ) , ( pk 2 ) , . . . , ( pk T ) ∈ R M T , Řk = (ř k 1 ) , (ř k 2 ) , . . . , (ř k T ) ∈ R M T ,
where • denotes the transpose.

59

We now consider the pressures measured in the 64

P k = (p k 1 ) , (p k 2 ) , . . . , (p k F ) ∈ C M F P k = (p k 1 ) , (p k 2 ) , . . . , (p k F ) ∈ C M F , R k = (r k 1 ) , (r k 2 ) , . . . , (r k F ) ∈ C M F
where for every f ∈ {1, . . The BF-MS computed for the n th calculation 2 point at the frequency ζ f ∈ F, and for the snapshot

3 k, b k f (n), is given by: b k f (n) = | w k f,n H p k f | 2 (2)
where • H is the conjugate transpose, and w k f,n is the 5 steering vector of length M between the M sensors 6 and the n th calculation point. The m th element

7 w k f,n (m) of w k f,n is: w k f,n (m) =   M m =1 1 d k n,m 2   -1 exp(-jζ f d k n,m ) d k n,m (
(n) = 1 K K k=1 b k f (n). (4)
Note that in the case considered, the receiver array is a linear array along the x-axis. Consequently,

35 b f = A f q f + z f (5)
where A f ∈ R N ×N (Fig. 1, middle) is the array 36 transfer function matrix that contains the beam-

37 forming point-spread functions. The (n, n ) ∈ 38 {1, . . . , N } 2 element a f (n, n ) of A f is: 39 a f (n, n ) = 1 K K k=1 M m=1 w k f,n (m) H exp(-jζ f d k n ,m ) d k n ,m 2 (6) z f ∈ R N is the measurement noise, and q f ∈ R N is
53 b f = h f * q f + z f (7)
where and assumptions (H1) -(H3), we have:

h f ∈ R N is
68 b f (n) = 1 K K k=1 | w k f,n H p k f | 2 + | w k f,n H r k f | 2
(8) Using Equation (8), we assume in this paper that 69 the observation noise z f can be divided into two 70 terms:

71 z f = 1 K K k=1 w k f,n 2 σ 2 1 1 N + e f ( 9
)
where • is the 2 -norm (which is also known as

1 the Euclidean norm), 1 1 N is a vector of ones of length 2 N
, and e f ∈ R N represents the remaining unknown 3 effects, where the amplitude of these remaining ef-4 fects is much lower than that of the variance σ 2 of 5 the Gaussian noise. Note that:

6 w k f,n 2 = M m=1 1 d k n,m 2 -1
Consequently, Equation ( 7) can be expressed as the

B = b 1 , b 2 , . . . , b F ∈ R N F , H = h 1 , h 2 , . . . , h F ∈ R N F , Q = q 1 , q 2 , . . . , q F ∈ R N F , δ = 1 K K k=1 M m=1 1 d k n,m 2 -1 , E = e 1 , e 2 , . . . , e F ∈ R N F ,
and the discrete-time convolution operator be-10 tween H and Q is defined as follows:

11 H Q = (h 1 * q 1 ) , (h 2 * q 2 ) , . . . , (h F * q F ) .

Proposed method

Find ( H, Q, σ 2 ) ∈ argmin H∈R 2N F ,Q∈R 2N F ,σ 2 ∈R+ θ(H, Q, σ 2 ) (11) where: θ(H, Q, σ 2 ) = ψ(H, Q, σ 2 ) + ρ(H, Q, σ 2 ). (12)
The first term of Equation ( 12) can be split into two new terms

20 ψ(H, Q, σ 2 ) = φ(H, Q, σ 2 ) + ϕ(Q), (13)
where φ :

R N F × R N F × R + → R is a data fidelity 21
term that is related to the observation model. In this 22 case, we choose the least-squares objective function,

23 i.e., 24 φ(H, Q, σ 2 ) = 1 2 H Q + σ 2 δ1 1 N F -B 2 . ( 14
)
ϕ models a regularization function that accounts for 25 the sparsity of the solution. In the present paper,

26
we propose to use a new regularization function, the 27 smoothed 1 / 2 ratio, as proposed by [18]; i.e., for

28 every Q ∈ R N F , (λ, α, β, η) ∈ ]0, +∞[ 4 : 29 ϕ(Q) = λ log 1,α (Q) + β 2,η (Q) (15) with, 30 1,α (Q) = F f =1 N n=1 q f (n) 2 + α 2 -α , 2,η (Q) = F f =1 N n=1 q f (n) 2 + η 2 .
Note that empirically, the SOOT algorithm provides 31 better results if the condition β < η 2 /α is satisfied.

32

The second term of Equation ( 12), ρ : R N F ×R N F × 33 R + → R is a regularization term that is related to 34 some a-priori constraints on the solution. In the 35 following, we assume that ρ can be split into three 36 new terms that concern the three quantities to be 37 estimated:

38 ρ(H, Q, σ 2 ) = ρ 1 (H) + ρ 2 (Q) + ρ 3 (σ 2 )
where ρ 1 , ρ 2 and ρ 3 are (not necessarily smooth) x ∈ R N :

(x , x) = ψ(x)+(x-x ) ∇ψ(x)+ 1 2 (x-x ) U (x)(x-x ),
where U (x) ∈ R N ×N is a semidefinite positive matrix. Then, U (x) satisfies the majoration condition for ψ at x if (•, x) is a quadratic majorant of the function ψ at x; i.e., for every x ∈ R N ,

ψ(x ) ≤ (x , x).
A function ψ has a µ-Lipschitzian gradient on a convex subset C ∈ R N , with µ > 0, if for every

(x, x ) ∈ C 2 , ∇ψ(x) -∇ψ(x ) ≤ µ x -x .
ν I N F G 1 (H l,i , Q l , σ 2,l ) ν I N F , (∀j ∈ {0, . . . , J l -1}) ν I N F G 2 (H l+1 , Q l,j , σ 2,l ) ν I N F , ν G 3 (H l+1 , Q l+1 , σ 2,l ) ν.

2.

Step-sizes (γ l,i 1 ) l∈N,0≤i≤I l -1 , (γ l,j 2 ) l∈N,0≤j≤J l -1 For every l ∈ N , let I l ∈ N * , J l ∈ N * . Let (γ l,i 1 ) 0≤i≤I l -1 , (γ l,j 2 ) 0≤j≤J l -1 , and γ l 3 be positive sequences. Initialize with H 0 ∈ dom(ρ 1 ), Q 0 ∈ dom(ρ 2 ), and σ 2,0 ∈ dom(ρ 3 ).

Iterations:

For l = 0, 1, . . .

                      Q l,0 = Q l , H l,0 = H l , For i = 0, . . . , I l -1 H l,i+1 = H l,i -γ l,i 1 G 1 (H l,i , Q l , σ 2,l ) -1 ∇ 1 ψ(H l,i , Q l , σ 2,l ) H l,i+1 = prox (γ l,i 1 ) -1 G1(H l,i ,Q l ,σ 2,l ),ρ1 ( H l,i+1 ) H l+1 = H l,I l For j = 0, . . . , J l -1 Q l,j+1 = Q l,j -γ l,j 2 G 2 (H l+1 , Q l,j , σ 2,l ) -1 ∇ 2 ψ(H l+1 , Q l,j , σ 2,l ) Q l,j+1 = prox (γ l,j 2 ) -1 G2(H l+1 ,Q l,j ,σ 2,l ),ρ2 ( Q l,j+1 ) Q l+1 = Q l,J l σ 2,l = σ 2,l -γ l 3 G 3 (H l+1 , Q l+1 , σ 2,l ) -1 ∇ 3 ψ(H l+1 , Q l+1 , σ 2,l ) σ 2,l+1 = prox (γ l 3 ) -1 G3(H l+1 ,Q l+1 ,σ 2,l ),ρ3 σ 2,l Proposition 2 For every (H, Q, σ 2 ) ∈ R N F × R N F × R + , let: G 1 (H, Q, σ 2 ) = µ 1 (Q, σ 2 ) I N F , G 2 (H, Q, σ 2 ) = µ 2 (H, σ 2 ) + 9λ 8η 2 I N F + λ 1,α (Q) + β G 1,α (Q), G 3 (H, Q, σ 2 ) = µ 3 (H, Q),
where:

G 1,α (Q) = Diag (q f (n) 2 + α 2 ) -1/2 1≤f ≤F, 1≤n≤N , (16)
and µ 1 (Q, σ 2 ), µ 2 (H, σ 2 ), and

µ 3 (H, Q) are the Lipschitz constants for ∇ 1 φ(•, Q, σ 2 ), ∇ 2 φ(H, •, σ 2 ), and ∇ 3 φ(H, Q, •), respectively. 3 Then, G 1 (H, Q, σ 2 ), G 2 (H, Q, σ 2 )), and
G 3 (H, Q, σ 2 ) satisfy the majoration condition for ψ(•, Q, σ 2 ) at H, ψ(H, •, σ 2 ) at Q, and
ψ(H, Q, •) at σ 2 , respectively.
To conclude, we have proposed a blind deconvolution method to apply to the BF-MS that imposes sparsity on the noise acoustic-source locations. This method is validated in the next section, and compared to the classical methods of DAMAS-MS and SDM, used in acoustics for moving-source deconvolution.

3 These Lipschitz constants are straightforward to derive since φ is a quadratic cost.

Results

18

We consider synthetic and real data for the

1 (0) X N (0) S 1 (0) S 2 (0) 5m 20m v X 1 (D) X N (D) S 1 (D) S 2 (D) • • • • • • • 21 hydrophones 10m 10m
Figure 2: Simulated configuration of a pass-by experiment. Black, source S 1 ; green, source S 2 ; red, calculation grid; blue arrow, global movement of the sources. autospectra of sources Q is sparse; moreover, it is limited in amplitude. Then, one natural choice for ρ 2 is the indicator function of the hypercube [q min , q max ] N F , where q min (resp. q max ) is the lower (resp., upper) boundary of Q. In practice, we choose q min as 0, which leads to a nonnegative constraint on the source power variables, and q max is the maximum value of B.

l if Q l -Q l-1 ≤ √ N F × 10 -6 .

Synthetic data

The simulated configuration is presented in Fig-

SNR (dB)

0 1 2 3 ℓ1(Q-Q) ℓ1(Q)
Figure 3: Comparison of the results for input data without noise and for three different signal-to-noise ratios (SNR) ∈ {-10, -5, 0} dB.

1 -norm (Fig. 3, bottom) between the real Q and 52 the estimated Q. It demonstrates that the method data without noise and for a SNR of -10 dB. Figure 4 and Figure 5 show the results for the DAMAS-MS, SDM, original SOOT, and NR-SOOT algorithms at frequencies of 1400 Hz and 770 Hz, respectively.

In these Figures, the green We now turn our attention to the case at the low frequency 770 Hz (Fig. 5), for which only the source S 1 exists. In this case, DAMAS-MS and SDM give unsatisfactory results, with a spatially extended source and false alarms even in the noise-free case for DAMAS-MS. The original SOOT gives satisfactory results without noise (Fig. 5a 3 ), although when the SNR decreases, the original SOOT algorithm creates false alarms (Fig. 5b 3 ), while the NR-SOOT algorithm shows excellent results in terms of position and amplitude (Fig. 5b 3 ). The NR-SOOT algorithm is robust against noise. In the following, for the sake of simplicity, and as it always provides the best results, vol. 330, no. 24, pp. 5835-5851, November 21, 2011.

11

[13] N. Chu, J. Picheral, A. Mohammad-Djafari, and N.

12 Gac, "A robust super-resolution approach with sparsity 13 constraint in acoustic imaging", Applied Acoustics, vol.

Figure 1 :

 1 Figure 1: Modeling of the forward problem

40 cies

 40 and speeds of interest (i.e., it does not 41 exceed the frequency resolution defined for the 42 localization results).43 Under these assumptions, BF-MS can be imple-44 mented in a simple way in the frequency domain. 45 The measured acoustic pressures are temporally 46 sliced into K snapshots that are indexed by k. The 47 calculation grid of N points is defined for the snap-48 shot k using the a-priori known global trajectory of 49 the vehicle. Note that this grid moves according to 50 this trajectory.

60 frequency domain between ζ 1

 1 and ζ F Hz, which is 61 related to a vector F = [ζ 1 , . . . , ζ F ] ∈ R F . We 62 define the Fourier transforms of Pk , Pk and Řk for 63 each snapshot k, as following:

  3) where j is the square root of -1, and d k n,m is the 9 distance between the m th sensor and the n th calcu-10 lation point during the snapshot k. We then define 11 the vector b f ∈ R N with its n th element b f (n) as 12 the estimate of the BF-MS output for the n th cal-13 culation point, through averaging over all of the K 14 snapshots; i.e., b f

17 BF-

 17 MS is performed along the x dimension, and the 18 calculation grid is a one-dimension vector of length 19 N along x. For more details on these computations, 20 we refer the reader to[START_REF] Oudompheng | Passive 108 synthetic aperture array to improve noise mapping of a 109 moving ship[END_REF][START_REF] Oudompheng | Localisation et contribution de 112 sources acoustiques de navire au passage par traitement 113 d'antenne réduite[END_REF]. 21 3.2. Inverse problem formulation 22 We set the following assumptions: 23 (H1) : The sources are random variables that are 24 mutually independent and stationary; 25 (H2) : The number M of the sensors is greater than 26 the number N s of the sources (i.e., M > N s ), and these N s sources are sparsely distributed 28 on the calculation grid; 29 (H3) : The noise components are mutually independent, and independent of the sources. Using the expression of the BF-MS, and assuming 32 that the sources are located at the N points of the 33 calculation grid, it is possible to express the BF-MS 34 output at a given frequency ζ f , b f ∈ R N , by:

40 the autospectra of the possible sources located at 41 the

 4041 N calculation points (Fig. 1, right), which are 42 the unknowns to be estimated. This expression is 43 frequently used in deconvolution [20, 27, 31, 41], al-44 though it needs the knowledge of matrix A f related 45 to the environment and to the array to perform the 46 deconvolution. Nowadays, some research projects 47 are focused on uncertain cases with partially known 48 or unknown ocean environments and experimen-49 tal configurations [42]. Consequently, when A f is 50 unknown, we propose in this paper to formulate 51 the BF-MS output at the frequency ζ f as a blind 52 deconvolution problem:

12 4. 1 .

 121 Criterion to be minimized 13 The purpose of this study is to identify (H, Q, σ 2 ) 14 from B through Equation (10), which leads to an 15 inverse problem. To solve this, we propose the 16 following optimization problem:

48 U 50 ρ

 4850 Then, for every x ∈ C, a quadratic majorant of ψ at x is easily obtained taking U (x) = µ I N , where I N is the identity matrix of R N ×N . The second optimization principle is the definition of the proximity operator of a proper, lower semicontinuous, convex function, relative to the metric induced by a symmetric positive definite matrix, which is defined in [48] as follows: Definition 2 Let ρ : R N →] -∞, +∞] be a proper, 47 lower semicontinuous, and convex function, let ∈ R N ×N be a symmetric positive definite ma-49 trix, and let x ∈ R N . The proximity operator of at x relative to the metric induced by U is the 51 unique minimizer of ρ + 1 2 (• -x) U (• -x), and it 52 is denoted by prox U,ρ (x). If U is equal to I N , then 53 prox ρ := prox I N ,ρ is the proximity operator origi-54 nally defined in [50]. 55 The convergence property of the NR-SOOT al-56 gorithm can be derived from the general results 57 established in [44]: 58 Proposition 1 Let Q l l∈N , H l l∈N and 59 σ 2,l l∈N be sequences generated by Algorithm 60 1. Assume that: 61 1. There exists (ν, ν) ∈]0, +∞[ 2 such that, for all 62 l ∈ N, 63 (∀i ∈ {0, . . . , I l -1})

64 and (γ l 3 )

 3 l∈N are chosen in the interval [γ, 2 -65 γ] where γ and γ are some given positive real 66 constants. 67 3. ρ is a semi-algebraic function. 2 68Then, the sequence (H l , Q l , σ 2,l ) l∈N converges to the69 critical point ( H, Q, σ 2 ) of Equation (11). Moreover, 70 θ(H l , Q l , σ 2,l ) l∈N is a nonincreasing sequence that 71 converges to θ( H, Q, σ 2 ).72 In NR-SOOT algorithm 1, ∇ 1 , ∇ 2 , and ∇ 3 are the 73 partial gradients of ψ with respect to the variables 74 H, Q, and σ 2 . G 1 , G 2 , and G 3 are the semidefi-75 nite positive matrix used to build the majorizing 76 approximations of ψ with respect to H, Q, and σ 2 , 77 and their expressions are given by the following 78 proposition, as established in [18]: Algorithm 1 The NR-SOOT algorithm.

19

  method validation. The synthetic data allow the 20 use of quantitative indicators, whereas real data 21 only provide subjective results. For both cases, 22 we perform comparative evaluation with the stan-23 dard algorithms DAMAS-MS and SDM. In prac-24 tice, the kernel blur related to the array trans-25 fer function has finite energy, and thus ρ 1 can 26 be chosen as an indicator function of set C = 27 H ∈ [h min , h max ] N F | H ≤ κ (equal to 0 if H ∈ 28 C, and +∞ otherwise), where κ > 0, and h min 29 and h max are the minimum and maximum values 30 of H, respectively. In the real data case, we choose 31 h min = 0 and h max = 1. As mentioned before, the

  Finally, the function ρ 3 related to the constraint on the noise variance is equal to the indicator function of the interval [σ 2 min , σ 2 max ], where σ 2 min = 0 and σ 2 max = 1. Note that the proximity operators can be easily explicitly expressed (see Appendix). The NR-SOOT algorithm with the penalty smoothed 1 / 2 function and the classical DAMAS-MS and SDM algorithms are applied to the BF-MS result. For every l ∈ N, the number of inner-loops are fixed as I l = 1 and J l = 100. The NR-SOOT algorithm is launched on 5000 iterations, and it can stop earlier at iteration

ure 2 .

 2 Here, we consider two sources: a random broadband source located at S 1 = (-4 m, 0 m, 0 m) (Fig. 2, black) and a sum of 3 sine functions at frequencies 1200 Hz, 1400 Hz, and 1800 Hz located at S 2 = (1 m, 0 m, 0 m) (Fig. 2, green), in the coordinate system where the origin is the center of the moving calculation grid all the time. The sources are moving jointly, and they follow a linear trajectory of length 20 m at constant speed v = 2 m/s. A linear antenna of 21 hydrophones that are equally spaced (with an inter-sensor distance of 0.5 m) records the propagated acoustic signals over D = 10 s. Zeromean white Gaussian noise is added to the recorded signals. To perform BF-MS, the moving calculation grid X n (t), ∀n ∈ {1, . . . , N } has a length of 20 m and contains N = 101 points. Concerning the initialization of the methods; Q 0 is the BF-MS output B. The initialization of the blur H 0 for the SOOT and NR-SOOT algorithms is a centered Gaussian filter, such that H 0 ∈ C. The regularization parameters of SDM, and (λ, α, β, η) ∈ ]0, +∞[ 4 (depending on the SOOT or NR-SOOT algorithms) are empirically adjusted, although it can be noted that the method is not too sensitive to their initialization.

Figure 3

 3 Figure 3 summarizes the quantitative results in terms of reconstruction error Q. The relative error is defined with the 2 -norm (Fig. 3, top) and

  lines (a 1 ,b 1 ) represent the theoretical sources to estimate (in terms of position and amplitude), the magenta lines represent the BF-MS results, which are the starting points of the DAMAS-MS, SDM, original SOOT, and NR-SOOT algorithms. In Figure 4 and Figure 5, the results obtained by DAMAS-MS are in greenishblue, those of SDM are in black (a 2 ,b 2 ), those of original SOOT are in red, and those of NR-SOOT are in blue (a 3 ,b 3 ). At the frequency of 1400 Hz (Fig. 4), for which both sources exist, for the case without noise on the recorded data (Fig. 4a) both the original SOOT and the NR-SOOT algorithms detect the source positions accurately. DAMAS-MS gives some false alarms at x = -3 m and x = 2.5 m. These false sources have small amplitudes, but they are a real problem because the number of sources is generally unknown. SDM locates two sources, but the amplitude estimation is not satisfactory and these sources are spread in the space. For the case of a SNR of -10 dB, DAMAS-MS does not succeed at all, and it shows several false alarms with significant amplitudes. With the SDM method, there is one false alarm around x = -1 m, and the amplitudes are not correct. The original SOOT algorithm gives good results, although there are two false alarms around x = -9 m and x = 9 m. In contrast, the NR-SOOT algorithm gives perfect results in terms of localization and source amplitude estimation.

  Figure 4: Comparison of the results at the frequency of 1400 Hz, without noise (a), and with SNR of -10 dB (b).

Figure 8 ,

 8 Figure 8, which are related to the autospectrum of 64

1vides the best performance compared to the three 8 other methods. 9 Figure 6 Figure 6 :8

 966 Figure6shows the computational time (in min-

39 This 40 SOOT, that is an extension of the SOOT algorithm 41 [

 394041 paper proposes a new method, known as NR-18], for moving-source localization based on blind 42 deconvolution in underwater acoustic data. As the 43 number of sources is small enough and they do 44 not spread spatially, its autospectrum has a sparse 45 representation, and it is possible to obtain more [10] S.-H. Abadi, H.-C. Song, and D.-R. Dowling, "Broad-1 band sparse-array blind deconvolution using frequency-2 difference beamforming", The Journal of the Acoustical 3 Society of America, 132(5), 3018-3029, 2012. 4 [11] A. Pereira, "Acoustic imaging in enclosed spaces", Phd 5 thesis, Laboratoire de Vibro-acoustique , INSA Lyon,

  ] A. Benichoux, E. Vincent, and R. Gribonval, " A fun-16 damental pitfall in blind deconvolution with sparse and 17 shift-invariant priors," in Proc. Int. Conf. on Acoustics,

	14
	76, pp. 197-208, Feb. 2014.

15

[14

Semi-algebraicity is a property satisfied by a wide class of functions, which means that their graph is a finite union of sets defined by a finite number of polynomial inequalities.

Jul. 1996.

following nonlinear problem in the standard form:

62 which can be easily computed.