Okan Yurduseven
email: okanyurduseven@ieee.org

Thomas Fromenteze

Rixi Peng

David R Smith

Frequency-Diverse Computational Polarimetic Imaging

Keywords: Imaging, antenna, metasurface, polarimetry, computational. I

In this paper, a frequency-diverse computational polarimetric imaging system is demonstrated at K-band (17.5-26.5 GHz) frequencies. The frequency-diverse operation enables all-electronic data-acquisition by means of a simple frequency-sweep and requires no mechanically moving apparatus or phase shifting circuits for imaging. Leveraging a tensor model for the scattering behavior, as opposed to a scalar model, enables the extraction of further information from the imaged objects. This is shown by means of frequency-diverse polarimetric imaging of complex objects, such as the letters of the word "DUKE", and comparing the reconstructed polarimetric images to the reflectivity-only reconstructions of the same objects.

INTRODUCTION

Computational imaging has gained traction because of its potential to address the challenges of conventional imaging modalities [START_REF] Hunt | Metamaterial apertures for computational imaging[END_REF][START_REF] Brady | Optical imaging and spectroscopy[END_REF][START_REF] Shrekenhamer | Terahertz single pixel imaging with an optically controlled dynamic spatial light modulator[END_REF][START_REF] Fromenteze | Sparsity-Driven Reconstruction Technique for Microwave/Millimeter-Wave Computational Imaging[END_REF][START_REF] Caorsi | A computational technique based on a real-coded genetic algorithm for microwave imaging purposes[END_REF][START_REF] Donelli | Computational approach based on a particle swarm optimizer for microwave imaging of two-dimensional dielectric scatterers[END_REF][START_REF] Sleasman | Design considerations for a dynamic metamaterial aperture for computational imaging at microwave frequencies[END_REF][START_REF] Molaei | 3D Printed E-Band Compressive Horn Antenna for High-sensing-capacity Imaging Applications[END_REF][START_REF] Obermeier | Sensing matrix design via mutual coherence minimization for electromagnetic compressive imaging applications[END_REF][START_REF] Álvarez | Three-Dimensional Compressed Sensing-Based Millimeter-Wave Imaging[END_REF][START_REF] Kpré | Computational Imaging for Compressive Synthetic Aperture Interferometric Radiometer (CSAIR)[END_REF][START_REF] Kpré | MIMO radar pseudoorthogonal waveform generation by a passive 1× M mode-mixing microwave cavity[END_REF][START_REF] Sleasman | Single-frequency microwave imaging with dynamic metasurface apertures[END_REF]. Frequency-diversity is a computational imaging technique that leverages spatially varying radiation patterns to encode the scene information by means of a simple frequency sweep . These frequency-dependent radiation patterns are used to illuminate the scene and collect the scattered signal from the scene. As a result, the scene information is encoded onto a set of measurement modes from which an estimate of the scene can be reconstructed using computational imaging techniques. This retrieval process is all-electronic and does not require any mechanical scanning apparatus or phase shifting circuits.

Conventionally, computationally retrieved scene information provides scalar information of the scene, mostly the reflectivity distribution [START_REF] Hunt | Metamaterial microwave holographic imaging system[END_REF]. At microwave and millimeter-wave frequencies, information content of the reconstructed images can be greatly enhanced by leveraging the vectoral relationship between the incident field and the scattered field. This additional set of information, namely polarization, can be used to reveal further information on the geometrical features of the imaged objects. In this paper, we study the retrieval of polarimetric information from computational frequency-diverse imaging. It is shown that by taking into account the tensorial behavior of the scattering from the imaged objects, polarimetric images can be obtained from frequency-diverse measurements.

II. COMPUTATIONAL FREQUENCY-DIVERSE POLARIMETRIC IMAGING

Retrieving the scene information from a set of known measurements is an inverse problem. In frequency-diverse imaging, the measurements are correlated to the scene by means of the following forward model:

3 ( ) ( ) ( ) ( ) Tx Rx g w E w E w f d =  r r, r, r r (1)
In [START_REF] Hunt | Metamaterial apertures for computational imaging[END_REF], g is the measurement vector (as a function of frequency, w), ETx is the radiated field from the transmit frequency-diverse antennas propagated to the scene, ERx is the radiated field from the receive frequency-diverse antennas propagated to the scene, f is the reflectivity distribution of the scene, and r denotes the scene coordinates. For a frequency-diverse imaging system producing M measurement modes and a scene discretized into N voxels, the integral equation of (1) is discretized as follows:

1 1 1 Mx MxN Nx Mx = + g H f n (2)
In [START_REF] Brady | Optical imaging and spectroscopy[END_REF], n is the system measurement noise. The bold font in ( 2) is used to denote the vector-matrix notation. Using the first Born approximation, the sensing matrix (or the transfer function of the system) H can be expressed as proportional to the element-wise matrix multiplication of the transmit and receive frequency-diverse antennas, both of which are propagated to the scene to be imaged, [START_REF] Lipworth | Comprehensive simulation platform for a metamaterial imaging system[END_REF]. To retrieve an estimate of the scene information from (2), several computational imaging techniques can be used, from single-shot matched-filter to iterative least-squares algorithms. Using the least-squares algorithm, the scene estimate, fest, can be obtained as follows [START_REF] Yurduseven | Resolution of the frequency diverse metamaterial aperture imager[END_REF]:

Tx Rx ∝ H E E
2 2 arg min est = - f f g H f (3)
The retrieved scene information fest in ( 3) is a map of scalar susceptibility distribution of the scene and has a single column vector format (Nx1 dimension).

In polarimetric imaging, the scalar relationship between the antenna radiated fields and the scene susceptibility is replaced by a vector model, correlating the different polarizations of the transmit and receive fields and a susceptibility tensor. For a radar system operating in the farfield, four possible polarization configurations of the transmit and receive fields can be considered; VV, HH, HV and VH, where H denotes the horizontal component and V denotes the vertical component [START_REF] Brown | High-resolution microwave polarimetric imaging of small trees[END_REF][START_REF] Lee | Polarimetric Radar Imaging[END_REF]. Operating in the near-field, the interaction between all the three components of the electric-field vectors can be leveraged, resulting in a 3

x 3 susceptibility tensor, χ , given in (4) [START_REF] Fromenteze | Computational polarimetric microwave imaging[END_REF].

    =       (4)
Expressing the forward model given in ( 1) by taking the polarimetry information into account, we obtain the following:

3 , ( ) ( , ) ( ) ( , ) i j i j Tx Rx g w E w E w d χ =  r r r r r (5)
From ( 5), it is possible to reconstruct the scene information on nine different polarization bases , i j χ where i=x, y, z and j=x, y, z.

III. IMAGING RESULTS AND DISCUSSION

The frequency-diverse imaging system is shown in Fig. 1.

Fig. 1. Frequency-diverse imaging system used for computational polarimetric imaging (feeding ports are shown as inset).

The frequency-diverse imager consists of an air-filled, cavity-backed metasurface antenna interrogating the scene to be imaged at K-band frequencies (17.5-26.5 GHz). The antenna is fed by two ports, port 1 (transmit) and port 2 (receive). Both ports are terminated using an ultra-wideband (UWB) monopole antennas inside the cavity. The dimensions of the cavity-backed metasurface antenna are 15.2 cm x 28.5 cm x 28.5 cm, corresponding to an electrically large loaded cavity supporting multiple mode combinations at K-band frequencies. Feeding the cavity through the first port excites multiple cavity modes which are mixed upon reflections from the cavity walls. The superposed mode patterns inside the cavity are highly diverse. In addition, the cavity antenna has a sphere inclusion embedded inside the cavity in between port 1 and port 2, reducing the direct coupling between the ports and helps mode-mixing [START_REF] Fromenteze | Computational imaging using a mode-mixing cavity at microwave frequencies[END_REF][START_REF] Fromenteze | Computational polarimetric microwave imaging[END_REF]. The metasurface consists of an array of subwavelength, circular irises, radiating in dualpolarization. The frequency-dependent cavity modes launched into the cavity by port 1 are sampled by these irises, radiating into free-space and interrogating the imaged object as depicted in Fig. 2. Fig. 2. Frequency-diverse imaging of the letters "D","U", "K", "E". The frequency-diverse field interrogating the imaged object is shown at the center frequency, 22 GHz, within the K-band.

The scattered field from the object is received through the second port. Because the cavity-backed metasurface antenna shares the same aperture to transmit and receive, it has a monostatic system layout. Within the scene, the individual letters of the word "DUKE" are present as the imaged object. As shown in Fig. 3(a), the "DUKE" letters were made from an array of copper wires with a diameter of around 5 mm. The object is placed at d=30 cm from the antenna, ensuring sufficient spatial resolution to distinguish the geometrical features of the letters. At d=30 cm distance, the cross-range resolution is δcr=0.5 cm while the range resolution of the imager is determined by the imaging bandwidth, calculated to be δr=1.5 cm.

For a frequency-diverse antenna, the orthogonality of the measurement modes interrogating the scene is governed by the quality factor (Q) of the antenna. As a result, having a large Q-factor is important to be able to minimize the redundancy of the information collected from the scene as the frequency is swept. Due to the air-filled structure (no dielectric loss is present) and the polished metal walls (reducing the conduction loss), the Q-factor of the cavitybacked metasurface antenna is high, Q=12000. The Q-factor of the antenna is measured by the decay rate of the time domain impulse response of the antenna [START_REF] Yurduseven | Frequency-diverse microwave imaging using planar Mills-Cross cavity apertures[END_REF]. As a result, the upper-bound limit for the number of measurement modes is calculated to be 4901 [START_REF] Marks | Spatially resolving antenna arrays using frequency diversity[END_REF]. In this work, the K-band is sampled at 4001 discrete frequency points, selected in accordance with the theoretical upper bound limit. The scene is discretized into N=8000 cubic voxels, and for image reconstruction, the least squares-algorithm is used [START_REF] Yurduseven | Resolution of the frequency diverse metamaterial aperture imager[END_REF]. The reconstructed images in Fig. 3(b) present the scalar susceptibility distribution of the "DUKE" letters. In addition to the intensity information, the reconstructed images in Fig. 3(c) provide polarimetric information. It is well-known in electromagnetic (EM) theory that electric-field (E-field) incident upon a wire along its longitudinal axis induces a current distribution along the longitudinal axis, re-radiating in the same direction. Based on this principle, a vertical wire with an impinging E-field in the vertical direction, scatters a vertically-polarized E-field while a horizontal wire with an impinging horizontally polarized E-field scatters an E-field in the horizontal direction. In Fig. 3(c), this phenomenon is evident. The vertical wires are excited by a verticallypolarized incident E-field and appear in vertical polarization (coded in red). The horizontal wires are excited by a horizontally polarized incident E-field and appear in horizontal polarization (coded in blue).

IV. CONCLUSION

We have demonstrated the application of polarimetry to computational frequency-diverse imaging. Different from the scalar susceptibility model, the polarimetric computational imaging leverages a tensor model, interacting the different polarization states of the antenna radiated fields incident upon and reflected from the imaged object. Leveraging polarimetry, further information about the geometrical features of the imaged objects can be extracted. The demonstrated polarimetric computational imaging system exhibits all-electronic operation and requires no phase shifting circuits, significantly simplifying the physical hardware layer of the system. Although demonstrated for microwave frequencies, it can reality be scaled to higher frequencies, where finer resolution limits and smaller antennas are required.

Fig. 3 .

 3 Imaging of the letters "DUKE" (a) actual imaged object (b) scalar reconstructed image (intensity) (c) polarimetric image.

13th European Conference on Antennas and Propagation (EuCAP 2019)


Pierre Thalamy
email: pierre.thalamy@femto-st.fr

Benoît Piranda
email: benoit.piranda@femto-st.fr

Julien Bourgeois
email: julien.bourgeois@femto-st.fr

Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure

Keywords: Self-Reconfiguration, Autonomous Robots, Distributed Algorithm

In the context of large distributed modular robots, self-reconfiguration is the process of having modules, seen as autonomous agents, acting together and moving to transform the morphology of their physical arrangement to produce a desired shape. However, due to motion constraints, the number of modules that can move concurrently is greatly limited, thus making self-reconfiguration a very slow process. In this paper, we propose an approach for accelerating self-reconfiguration to build a porous version of the desired shape, using scaffolding. We expand this idea and propose a method for constructing a parametric scaffolding model that increases the parallelism of the reconfiguration, supports its mechanical stability, and simplifies planning and coordination between agents. Each agent has a set of basic rules using only four states which guarantees that module movements and the construction of the scaffold are deterministic. Coupled with an underneath reserve of modules that allows the introduction of rotating quasi-spherical modules at various ground locations of the growing porous structure, our method is able to build the scaffolding structure in O(N 2 3 ) time with N the number of modules composing the structure. Furthermore, we provide simulation results showing that our method uses O(N 4 3 ) messages with no congestion.

INTRODUCTION

Programmable Matter (PM) [START_REF] Copen Goldstein | Programmable matter[END_REF] is defined as matter that can autonomously alter its physical properties such as its shape or color, as a response to an internal or an external event. While many technologies on the rise claim to be PM, we believe PM based on Modular Self-reconfigurable Robots (MSR) [START_REF] Fukuda | Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulator[END_REF] to be the most promising endeavor, owing to the versatility of the systems [START_REF] Bourgeois | Programmable matter as a cyber-physical conjugation[END_REF].

MSR are robots composed of an arbitrary number of individual modules, which can be seen as autonomous agents, that can physically attach to each other and coordinate through communication to achieve a common goal. Though various types of modular robot architecture exist [START_REF] Ahmadzadeh | Modular Robotic Systems: Characteristics and Applications[END_REF], we are interested in lattice-based modular robots, where connected modules are organized in a regular lattice structure, on which modules navigate using their neighbors.

Self-reconfiguration is a notoriously intricate problem [START_REF] Gorbenko | Programming for modular reconfigurable robots[END_REF][START_REF] Hou | On the complexity of optimal reconfiguration planning for modular reconfigurable robots[END_REF] which can be stated as finding a series of individual motions (preferably performed in parallel) that can transform an initial arrangement of modular robotic modules (also named configuration or shape) into a goal one. It is a fundamental algorithm for large modular robots and PM that encompasses a number of non-trivial subproblems, such as defining the goal shape [START_REF] Bie | L-systems driven self-reconfiguration of modular robots[END_REF][START_REF] Pescher | Molding a Shape-Memory Polymer with Programmable Matter[END_REF][START_REF] Støy | Self-Reconfiguration Using Directed Growth[END_REF][START_REF] Tucci | Efficient Scene Encoding for Programmable Matter Self-reconfiguration Algorithms[END_REF], computing a feasible construction plan [START_REF] Fitch | Reconfiguration planning for heterogeneous self-reconfiguring robots[END_REF][START_REF] Tucci | A Distributed Self-Assembly Planning Algorithm for Modular Robots[END_REF], or coordinating the motion of modules along multiple paths in parallel while avoiding collisions [START_REF] Fitch | Million Module March: Scalable Locomotion for Large Self-Reconfiguring Robots[END_REF][START_REF] Naz | A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots[END_REF]. Solutions have been proposed from various research perspectives such as control theory, computational geometry, multi-agent systems, and biomimetics [START_REF] Ahmadzadeh | Modular robotic systems: Methods and algorithms for abstraction, planning, control, and synchronization[END_REF].

Self-reconfiguration can be viewed both as a destruction [START_REF] Fitch | Reconfiguration planning for heterogeneous self-reconfiguring robots[END_REF][START_REF] Gilpin | Robot pebbles: One centimeter modules for programmable matter through self-disassembly[END_REF]] and a construction process; while we mainly tackle the latter problem in this article, the algorithm proposed in this article could easily be reversed to perform a clean destruction.

Self-reconfiguration is a notably slow process that is very demanding in term of resources. Therefore, in this article, we would like to propose a method for building 3D objects that is both fast and efficient in term of communication and computation. Furthermore, we would like to offer more guarantees on the respect of mechanical constraints throughout the construction.

In order to attain these objectives, we start by redefining the notion of a shape as its Boundary Representation, an external surface with a mechanically sound internal organization. This is then transposed into the context of self-reconfiguration as the construction of a scaffolding structure representing the object that satisfies mechanical constraints and provides a structure for supporting a massive number of module movements. We, hence, introduce an algorithm for deterministically constructing this structure based on simple local rules and only 4 agent states.

Such a deterministic approach naturally poses fault-tolerance issues, which will be the topic of future works.

In this article, we obtain the following results. By using scaffolding and coating instead of a filled object, a pyramid requires b 3 3 times less modules with b the tile branches length. Our method is able to build the scaffolding structure of a coated pyramid in O(N 2 3 ) time with N the number of modules composing the structure whereas the filled pyramid requires O(N 4 3 ) time, that is N 2 3 times more. Furthermore, we demonstrate that our method uses O(N 4 3 ) messages with no congestion as the modules having the highest throughput manage 4 messages/time step and we provide simulation results that confirm this complexity for several scenarios.

CONTEXT

We mainly perceive objects by their optical and mechanical characteristics. From an optical standpoint, an object can be represented by its external surface, which reflects the light that is provided by an external source. In order to visually materialize an object, it is sufficient to coat the boundary between the interior and the exterior of the object with light-scattering matter (in image synthesis, this is called the Boundary Representation (BRep) [START_REF] Foley | Computer Graphics: Principles and Practice[END_REF]) model of an object). (See Figure 3.c) From a mechanical standpoint, however, an object must, thanks to its internal structure, be able to withstand external forces such as gravity or contact forces. An internal structure is therefore practical for the mechanical coherence of an object (Figure 3.b).

In the context of the self-reconfiguration of an arbitrary shape A into a goal shape B, every module has to navigate a path from its initial position in configuration A to its final position in configuration B. If we consider a filled object then all the possible paths are placed on the external surface of the object, which lowers the number of possible simultaneous movements.

Indeed, moving through the volume of an object multiplies the number of potential paths that can be followed by modules in parallel. This can be guided by a skeletal structure forming a scaffold on the interior of the object, where all these paths can be followed simultaneously by moving modules.

In order to preserve the external aspect of the object, it is then necessary to cover, or coat, the scaffolding structure, which can be done by navigating the many paths provided by the scaffold in parallel.

In this paper, we focus on a solution for the construction of this scaffolding structure.

To do so, we have made the following assumptions:

(1) The object we aim to build resides in a regular Face-Centered Cubic (FCC) lattice which ensures a high density of modules and therefore a compelling visual representation of the shape as it will be more difficult for light to traverse its boundary. (2) Underneath the object lies a sandbox-like environment, acting as a reserve of modules, and from which modules can be moved at various ground locations of a regular square grid (Figure 3.a).

(3) This sandbox also brings the energy and the initial communication that provides the description of the goal shape.

RELATED WORKS

One particularly tricky aspect of self-reconfiguration stated earlier is the coordination of motions between concurrently moving modules so that they avoid blocking the motion of each other or attempting to simultaneously move into the same space. Some authors such as Naz et al. [START_REF] Naz | A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots[END_REF] proposed to leave a gap between moving modules through communication-based coordination in order to limit the risk of collisions. While this is powerful and practical for the rotating motion of 2D space modules, it cannot be applied efficiently to 3D space as is. Furthermore, most existing solutions to the self-reconfiguration problem in large modular robots consider simple module geometries (such as different flavors of cubes [START_REF] Butler | Distributed Planning and Control for Modular Robots with Unit-Compressible Modules[END_REF][START_REF] Kawano | Distributed Tunneling Reconfiguration of Sliding Cubic Modular Robots in Severe Space Requirements[END_REF][START_REF] Lengiewicz | Efficient collective shape shifting and locomotion of massively-modular robotic structures[END_REF][START_REF] Vassilvitskii | A complete, local and parallel reconfiguration algorithm for cube style modular robots[END_REF][START_REF] Zhu | A distributed and parallel control mechanism for self-reconfiguration of modular robots using L-systems and cellular automata[END_REF]), and actuators capable of performing both translation and rotation motions. Yet, the self-reconfiguration of modules with more complex geometries [START_REF] Yim | Distributed Control for 3D Metamorphosis[END_REF][START_REF] Yoshida | A distributed method for reconfiguration of a three-dimensional homogeneous structure[END_REF] has proven itself much harder, especially when only the latter form of motion is possible [START_REF] Michail | On the Transformation Capability of Feasible Mechanisms for Programmable Matter[END_REF], as modules are more likely to prevent the motion of another due to blocking constraints, especially when they have rigid non-deformable bodies.

The most relevant reconfiguration work to our module geometry is the one of Yim et al. [START_REF] Yim | Distributed Control for 3D Metamorphosis[END_REF], where the authors proposed a probabilistic self-reconfiguration algorithm for reconfiguring rhombic dodecahedron modules residing in a FCC lattice, and that can only move using rotation. They proposed a method named Goal-Ordering, in which modules use one or two metrics to decide which target location in the goal configuration they should go fill. Their method however, suffers from overcrowding around the open goal positions, and is likely to get stuck in local minima and avoid converging altogether, especially in solid and hollow shapes.

In order to ease the motion constraints of self-reconfiguration and increase motion parallelism, Kotay and Rus [START_REF] Kotay | Algorithms for self-reconfiguring molecule motion planning[END_REF] proposed to engineer the interior of the target shape by discretizing it into repeating hollow multi-module sub-structures named tiles, that would leave large tunnels for modules to navigate the structure in parallel, at the cost of a large increase in the granularity of the shape. This approach is referred to as Scaffolding. In this work, we are also interested in scaffolding as a way to increase the parallelism potential of the reconfiguration, as well as to ease coordination between moving modules and avoid blocking issues due to overcrowding.

More recent works have also considered a similar approach to lowering the complexity of reconfiguration for cubic modules capable of both rotation and translation. Støy approximated the target shape with a porous representation made by removing individual modules from its volume in a manner that would guarantee an absence of local minima, and hollow or solid sub-configurations. He, then, proposed to use local rules and cellular automata to perform the reconfiguration in [START_REF] Støy | Using cellular automata and gradients to control selfreconfiguration[END_REF], or through a gradient descent method in [START_REF] Støy | Self-Reconfiguration Using Directed Growth[END_REF].

Furthermore, an aspect of self-reconfiguration that should be further considered is the mechanical constraints imposed on the system. Two main types of mechanical failures are identified in [START_REF] Hołobut | Distributed computation of forces in modular-robotic ensembles as part of reconfiguration planning[END_REF]:

(1) loss of stability due to a shift in the center of mass of the system;

(2) structural failure, caused by the breaking of a bond between modules after an excessive stress. While Hołobut and Lengiewicz also present a distributed procedure for predicting if the next reconfiguration step will cause a structural failure in their paper, to the best of our knowledge, no self-reconfiguration algorithm truly considers mechanical constraints in their design-when these same constraints might prevent them from working in practice. With our novel approach to scaffolding, we aim to make progress towards achieving mechanically sound reconfigurations by structural design, hence without having to resort to such software methods that involve a costly performance overhead.

In this work, we consider a modular robot made from an arbitrary number of quasi-spherical modules named 3D Catoms, that move by rotating on the surface of neighbors, and connect to up to 12 neighbor modules, one on each of their connectors (see Figure 1). We strongly advise readers to browse through [START_REF] Piranda | Designing a quasi-spherical module for a huge modular robot to create programmable matter[END_REF] for a better sense of the geometry and motion mechanisms of 3D Catoms. Our project is a follow-up of the Claytronics project [START_REF] Copen Goldstein | Programmable matter[END_REF] and Catom stands for Claytronics atoms. 3D Catoms reside in a 3-dimensional grid described as a Face-Centered-Cubic Lattice (FCC), with coordinates in Z 3 . 3D Catoms are symmetrical and therefore their orientation does not matter. Positions on the grid are referred throughout the paper as lattice cells, or simply as positions.

A 3D Catom M is able to move from one cell to a free neighbor position by rotating on the surface of another 3D Catom P acting as a pivot. This corresponds to a change of latching connectors on the surface of P; a rotation can therefore be described as a couple ⟨C i , C j ⟩ P , where C i and C j refer to connectors with identifier i, j ∈ [0, 11]. These connectors are also used by 3D Catoms to communicate with their immediate neighbors, the only mode of communication available to them. Furthermore, a rotation ⟨C i , C j ⟩ P can be performed through one of two paths on the surface of P, either by rotation on an hexagonal face, or through an octagonal face (R h and R o on Figure 1, respectively). We provide a YouTube video illustrating this mode of motion (see footnote 1 ).

A 3D Catom is said to be mobile if it can reach at least one of its neighbor cells according to its motion constraints. The set of all motion constraints imposed on a module M that seeks to move to a neighbor position N is identical to the one introduced by Yim et al. in Proteo [START_REF] Yim | Distributed Control for 3D Metamorphosis[END_REF].

Due to the geometry of the modules and the resulting blocking constraints, it is not possible to bridge the gap between two lines of modules growing towards each other, therefore the construction of a shape that has all its elements connected on each layer needs to be grown from a single initial point, and with a carefully designed set of construction rules, likely resulting in a diagonal growth of the volume of the object. 1 Youtube video illustrating 3D Catom motions https://youtu.be/IZh-5p1dbKk

SCAFFOLDING

Our scaffold model is defined as an arrangement of canonical components sharing a common structure named tiles.

Anatomy of a Scaffold Tile

A tile is composed of a core made of a root module surrounded by 4 support modules (placed to help others to vertically traverse the structure), and a number of branches connecting it to other tiles. The length of these branches b is a parameter of our model, it is determined by the mechanical capabilities of the structure, in relation to the connector strength of the 3D Catom hardware. However, b has to be greater than 4 as the space would be too tight for module motion otherwise. We can express the number of modules that compose a tile using the relation N tile modules = 6(b -1) + 5. In the remaining figures, we will use b = 6, which yields N tile modules = 35. This number can be compared to the fully filled bounding box of the tile that would use b 3 modules (216 with b = 6).

Each tile is an arrangement of modules that follows the axes of the FCC grid. As shown in Figure 2.b, the center node R (also referred to as Tile Root, drawn in white) is connected to:

• a branch made of modules We also define eight special empty positions below the tile, placed near the tip of incoming vertical branches named Entry Point Locations (EPL), and shown as transparent cells on Figure 2.a. EPL are the positions that allow modules to enter a growing tile from the lower levels. When a module enters one of these positions (as a FreeAgent), it stops and either requests a goal destination into this tile from the Coordinator of this tile (i.e., Tile Root), or in some cases waits for some condition to clear before moving to its destination. There are two types of entry points, appearing in purple and blue on Figure 2.a: the blue EPL are temporary and will become unreachable as branches X and Y start growing, they are used for introducing future Support modules into the tile; purple EPL are the main entry points that are used for the rest of the life cycle of the tile, but can only be used once support modules are in place.

{X i |i ∈ [1..b -1]} (in orange) following the - → x axis; • a branch {Y i |i ∈ [1..b -1]} (drawn in green in Figure 2.c) following the - → y axis; • four branches {Z i |i ∈ [1..b -1]}, {RiдhtZ i |i ∈ [1..b -1]}, {RevZ i |i ∈ [1..b -1]}, {Le f tZ i |i ∈ [1..b -1]} (in blue in Fig- ure 2.e) following axes - → z , (1, -1, 1), (-1, -1, 1) and (-1, 1, 1), respectively
Our scaffolding is then made of regularly placed instances of partial or complete tiles that can be connected to up to 6 neighbor tiles through modules

X b-1 , Y b-1 , Z b-1 , RiдhtZ b-1 , RevZ b-1 and
Le f tZ b-1 as shown in Figure 2.f. Partial tiles are tiles whose number of branches is lower than 6, as found on the borders of the object.

Hierarchical Organization

We define an h-pyramid as a pyramid with a height of h tiles (that is to say b(h -1) + 1 modules from the base to the tip). For instance, Let us consider a h-pyramid shape composed of N t il es scaffold tiles assembled together in the FCC lattice. This shape is made of 5 modules at the tip of the pyramid (constituting the top tile at height h), 4 tiles under these modules at height h -1, and again 4 overlapping tiles under each of these tiles and so on until reaching the base level at height 1). This h-pyramid is composed of tiles whose origins R i, j,k are placed at:

R i, j,k (b × i, b × j, b × k) with        0 ≤ i ≤ h -k 0 ≤ j ≤ h -k 0 ≤ k ≤ h
In our example shown on Figure 3, for a 4-pyramid with b = 6, the number of modules comprising the scaffold is 630 and the coating uses 760 additional modules.

N t il es = h i=1 i 2 = h 3 3 + h 2 2 + h 6 (1)
Then, we can express the number of modules used to construct the scaffold of the h-pyramid (including support modules drawn in yellow in Figure 3.b). First, consider N i the number of modules from tiles at level i of the pyramid, as they appear on Figure 3.b. We sum i segments along the hich composed of one white module plus (i -1) groups of 1 white and b -1 red modules; (i -1) segments along the -→ y axis made of (b -1 green modules); 4(i -1) 2 ascending branches of (b -1) blue modules; and 4i 2 support modules in yellow.

N i = i ((i -1)b + 1 + (i -1)(b -1)) + 4(b -1)(i -1) 2 + 4i 2 (2) N modul es = h i=1 N i = (2b - 1 3 )h 3 + ( 9 2 -2b)h 2 + 5 6 h (3)
And the number of modules comprising the coating of the pyramid (h ≥ 2) as:

N coat inд = 4 (h-1)b+1 i=1 i = 2 b 2 h 2 + (3b -2b 2 )h -3b + 2 (4)
Note that from h = 6 and on, more modules are required for building the structure than for building the coating of the pyramid.

Since that due to the geometrical constraint of 3D Catoms, we need to enforce a strict construction order of the tiles of the pyramid (bottom to top, left to right, front to back), we can construct a graph connecting these tiles, and a spanning tree within that graph expressing the precedence of the tiles in term of their construction order. The scaffold formation problem fits into our idea of a larger and more comprehensive self-reconfiguration scheme, introduced in the next section.

Self-Reconfiguration Scheme

In the context of the self-reconfiguration into an arbitrary goal shape G from an empty sandbox, our approach consists in a sequence of several phases:

(1) Scaffold construction: If the desired shape is not convex by itself or when connected to the sandbox, we build a fold encompassing a tile approximation of the convex hull of the union of the object and the base of the sandbox (e.g, in Figure 4.a, the native white scaffolding of the sphere is complemented by a red scaffolding, filling the gap between the object and the base), and fill holes in the shapes. Under a carefully designed construction plan, this supports the mechanical stability of intermediate configurations.

Construction Agent Roles

Each tile is composed of {6i + 5|i ∈ [0..b -1]} modules (see Figure 2) that must be inserted in a specific order so as to avoid deadlocks. When docked as a tile component, some of these modules endorse active roles, while others are simply passive structural components.

We consider that during its life, a module can be in four different states. For each of these state it runs a corresponding agent code:

(1) Idle modules are sandbox modules which are waiting to be called in to partake in the reconfiguration by modules from the growing structure. (2) Free Agent modules are Idle modules that have been called in and entered the reconfiguration scene, waiting to be assigned a goal position or in motion to their assigned position. (3) Coordinators are modules docked in the root position of a tile, and which are responsible for scheduling the construction of their tile. More specifically, the role of the Coordinator is to ensure that modules arrive at specific branches in an order compatible with the construction order of the components of the tile, and inform incoming modules on where they are needed. (4) Relay modules are docked robots whose only role is to forward messages between FreeAgents transiting through its tile and the local Coordinator. This role can be endorsed by supports or vertical branch tip modules.

Tile Construction Process

The tile construction process is performed by modules arriving at the various EPL of the vertical incident branches of parent tiles (i.e., FreeAgent modules), and coordinated by the root module of the tile (i.e., Coordinator module). The construction is started by the arrival of the coordinator into the tile root position, which can only happen once the branches incident to its tile are complete. While waiting for this condition to clear, the future coordinator awaits on one of the entry points of the RevZ branch. If there are no incoming branches whose completion to wait for, as on some corner cases, it can directly proceed to its position; otherwise, it keeps waiting for the tip module of the last incoming branch to notify it that the tile is ready to start growing. When the coordinator gets into position, it immediately sends down all the vertical branches below it a message expressing the requirements of the construction of its tile: an 8-bit word indicating which branches it has to build, and whether or not it will need to provide a tile root through its RevZ branch. This message is routed all the way down to the four ground coordinators located under the current tile, where ground coordinators can then summon Idle modules from the sandbox according to the requirements and send them up towards the growing root. It is assumed that the four ground coordinators are able to share a common notion of time, that allows them to temporally coordinate their feeding of modules to the system.

When a previously Idle module is called in for construction, it endorses the FreeAgent (FA) role, behaving as specified by Algorithm 1, getting routed from tile to tile by local coordinators and locally navigating each tile from an entry point to a destination using a set of local rules common to all modules. Every time a FA module enters a new tile, it updates its coordinate system to use positions relative to the local coordinator, set as its origin. If the module is just transiting through the tile, the position returned by the coordinator will be an EPL, otherwise it will be one of the 6b + 4 non-root tile components. The local rules can be seen as a dictionary whose key is the tuple ⟨N , P Goal , Step⟩, and P disp is the value. N is a 12-bit representation of the local neighborhood of the module; P Goal is the goal position of the module in the tile (relative to the position of the coordinator); Step is there to avoid rule-matching collision between rules and denotes how many motions the module has already performed in the tile; P disp is the displacement corresponding to the rotation that the module has to perform.

Once a FA module has reached its position as a component of the tile, it updates its state based on its new position, and when relevant, notifies waiting modules that they can resume their motion.

Messaging

There are four kinds of messages being exchanged in a distributed manner during the reconfiguration process detailed in the last section: down all of its incident vertical branches to express its resource requirements to 4 lower-level Coordinators connected to the sandbox-i.e., how many modules it needs for building its tile.

ANALYSIS 6.1 Algorithmic Complexity

In this section we study the time and message complexities of the reconfiguration method in the case of the pyramid. Results can then be generalized to more complex shapes in subsequent works. Let's consider throughout this section the construction tree of the pyramid, whose vertices are the tiles of the pyramid, and whose edges denote the precedence in the construction order of these tiles. The root of the tree is the tile at position (0, 0, 0). An edge between a father and a child vertex means that the start of the construction of the child is triggered by the completion of the father. We determine for each of the edges, the time elapsed between the construction of the father and the one of the child. For instance, within a tile, the X branch is the first branch to be built, and its completion will allow the child tile at position (b, 0, 0) relative to tile X to get its construction process under way.

We assume that the duration of the construction of a tile only depends on the number of modules forming it, it is therefore built in constant time. By studying displacement rules, we can deduce that the sum of the waiting time and the motion time necessary for a R module to reach its position depends on its height i in the construction tree, which can be expressed as:

T t il e (i) = [24 + 6b + 2b(i -1)] × ts = [24 + 4b + 2b × i] × ts (5)
where ts is the duration of an unitary 3D Catom motion, constituting a time step. Theorem 1. In the case of the h-pyramid, the height of construction tree is 3(h -1).

Proof. Given that the construction of the tile at (0, 0, i + b) requires the construction of 4 lower tiles: (0, 0, i), (b, 0, i), (0, b, i) and (b, b, i), the height of the higher vertex in the tree is equal to the height of the lower vertex + 3, therefore heiдht(0, 0, h) = 3(h -1).

Considering that the depth of two vertices placed in the same plane is 2(h -1) in the construction tree, which is indeed lower than 3(h -1), we can deduce that the previous path (0, 0, i) to (0, 0, i + b) is a critical path. □ Theorem 2. The reconfiguration time of the reconfiguration of the h-pyramid is O(N 2 3 ).

Proof. Using Equation 5, we can express the time required to construct the h t h level of the hpyramid in number of motion times as:

T = h i=1 24 + 4b + 2b × i = 24h + b(5h + h 2 ) (6)
We conclude that the reconfiguration time is O(h2 ) time steps. Using Equation 3, and considering that the parameter b is a positive constant, we can assume that there exist two positive real numbers {p, q} ∈ R 2 verifying: p × h 3 < N < q × h 3 .

Then, we deduce bounds for h:

N q 1 3 < h < N p 1 3
Combining with previous Equation 6, we deduce bounds for the motion time T :

6 N q 2 3 + 54 N p 1 3 < T < 6 N p 2 3 + 54 N p 1 3
We conclude that the reconfiguration time is O(N Proof. Each module sends 4 kinds of messages during a reconfiguration: N messaдes = N RG P + N PG P + N T I R + N I F . Where RGP, PGP, T IR and I F messages denote the messages detailed in Section 5.6. At worst case N T I R = c × h i=1 i 2 = N t il es , c is a small constant. The number m of I F messages sent by a module depends on the level i of its docking tile: m = 4b × (h -1). Then,

N I F = h i=1 i 2 (4b × (h -i)) = 4b 12 (h -1)h 2 (h + 1)
Similarly, messages RGP and PGP are sent k = 3 or k = 4 times every time a FA module enters a tile, except if it will become root, therefore using Equation 2,

N RG P = N PG P = k × h i=1 (N i -i 2 ) × i
As N I F , N RG P , and N PG P are O(h 4 ), we can deduce as in the previous proof that N messaдes is O(N 4 3 modul es ). □

Comparison with a Filled Pyramid

In this section, we compare our scaffolding approach that builds porous objects with the construction of filled objects.

For the h-pyramid, scaffolding uses N modul es (cf. Equation 3) modules whereas a filled shape uses:

N compact modul es = b(h-1)+1 i=1 i 2 = 2b 3 (h -1) 3 + 9b 2 (h -1) 2 + 13b(h -1) + 6 6
We observe that the filled pyramid requires b 2 6 times more modules than the one using scaffolding.

In order to evaluate the number of motions for building a filled configuration, we notice that for each layer j we have a number of motions of:

N l ayer j = j 2 + j-1 i=1 2i × j
As we have n = b(h -1) + 1 layers, and each 3D Catom has to climb j + 1 layers, then we have a total number of movements for building the filled h-pyramid of:

N f ill ed mot ions = b(h-1)+1 j=1 h -j + j 2 + j-1 i=1 2i × j = O(h 4 )
Using an algorithm similar to Tucci et al. [START_REF] Tucci | A Distributed Self-Assembly Planning Algorithm for Modular Robots[END_REF] to cover each plane of the pyramid, we can build two distinct parts of the structure in parallel, hence:

T f ill ed = O(N 4
3 ) However, this does not take into account the construction of the surface of the pyramid. Nevertheless, as the algorithm does not use the vertical border branches of level i to construct the tiles of level i + 1, we can use these branches [1..i] to transport modules from the sandbox to fill the borders during the construction of upper tiles. Then, only the last tile at the top of the pyramid will remain to be covered, which can be done at the end of the construction of the scaffold.

To summarize, the reconfiguration time of the construction of the h-pyramid with scaffolding is O(N 2 3 ) and the visual aspect is similar to the one of the fully filled pyramid whose construction takes O(N

3 ) time.

EXPERIMENTS

The experiments were made on the VisibleSim [START_REF] Piranda | VisibleSim: Your simulator for Programmable Matter[END_REF] simulator. They consist in building pyramids of various base sizes (4 × 4, 5 × 5 ... 9 × 9) from an equal-size sandbox.

The video available on YouTube 2 shows recordings of these simulations. One notable aspect of these recordings is that the growth of the scaffold progresses in a roughly diagonal manner. This is due to the enforced construction order that makes sure that there are never two branches growing facing each other, as our module geometry would not be able to bridge the gap between them. Furthermore, it is clear from this video that our method is able to leverage the potential for parallelism of such a modular robotic system, with a large number of modules moving concurrently to reach their goal positions, approximately following a bell curve with surges of parallelism, as can be seen on Figure 5.

In this set of experiments, we will study the following properties of our method: motion parallelism, number of messages exchanged between any two modules, temporal distribution of these messages. Other properties of the method can be theoretically derived, which was done in the previous section. In the following figures, time is represented as time steps relative to the rotation time of a module. One time step corresponds to the time it takes for a single module to move from one position of the grid to a neighbor one. Also, we assume that communication time is negligible relative to the motion time of a module. Figure 6 displays the total number of messages exchanged between any two neighbor modules during reconfiguration, as a function of the number of modules required to build various sizes of pyramids. We verify that the curve given by simulations for 1x1 to 9x9 base tiles is compliant with the expression of the complexity of Theorem 3.

Furthermore, Figure 7 provides information on the temporal distribution of these messages, by showing the maximum throughput observed by each module during a reconfiguration. It shows that a maximum of four messages are sent within a single time step (this corresponds to INITIATE_FEEDING messages by newly arrived Coordinators, being sent down all incident vertical branches at once). On average, the maximum message rate per module is 1.325, which together show that a congestion of the network, whose avoidance is a critical aspect of such large distributed systems [START_REF] Naz | Network Characterization of Lattice-Based Modular Robots with Neighbor-to-Neighbor Communications[END_REF], cannot occur.

CONCLUSION AND FUTURE WORKS

In this paper, we introduced of novel approach to the distributed scaffold-based self-reconfiguration of large modular robotic ensembles, using a parameterizable scaffold model, local rules, and simple coordination. We defined the purpose and geometry of our scaffold, proposed a distributed and deterministic method for constructing it from a sandbox of modules, and explained how its construction fits into a larger self-reconfiguration scheme that involves the coating of the structure. We provided an analysis of this method with the example of the construction of a pyramid, as well as a set of experiments, which showed that our approach can perform selfreconfiguration into a porous version of an object in O(N 2 3 ) time, leveraging the potential for parallel motion of our modules, and using O(N 4 3 ) messages, with no possibility of network congestion. We envision as future works to replace the resource requests sent by arriving tile roots, by a continuous feeding of 3D Catoms up every branch of the scaffold, which could be interrupted by tile roots when they stop requiring resources. We believe this would allow us to reach a O(N 1 3 ) reconfiguration time. Furthermore, we are interested in generalizing this method to any shape, which requires additional coordination at the tile level to allow modules to traverse the tile horizontally without colliding. The scaffold coating algorithm for rendering the surface of objects also needs to be designed. Finally, an interesting topic is the complete removal of tile root modules, which would direct us towards fully-decentralized and probabilistic construction methods, and possibly allow a faster growth order to emerge.

Figure 1 :

 1 Figure 1: Two possible paths that can be used to perform motion ⟨C 0 , C 2 ⟩ P on the surface of a module P.

  . Finally, the tile is also composed of four support modules named SZ , SRiдhtZ , SRevZ and SLe f tZ at respective positions (1, 1, 0), (1, -1, 0), (-1, -1, 0) and (-1, 1, 0) relative to R (in yellow on Figure 2.b).

Figure 2 :

 2 Figure 2: 3D structure of a tile with b = 6. a) Existing structure made from previous tile. Transparent cells represent entry points into the tile; b) White module represents the root R of the new tile, origin of the local coordinates system; c,d,e) 3D position of branch and support modules of the tile; f) Assembly of multiple tiles to construct a scaffold.

Figure 3 :

 3 Figure 3: Construction of a 3D model using scaffolding (b = 6). a) Support structure; b) Scaffold of the 4-pyramid; c) Coated 4-pyramid, after removal of support modules.

( 2 )

 2 Removing excess modules: Non-essential modules are removed from the shape, and stored onto the scaffold, ready to be used as coating later on.(3) Coating: Construction of the surface of the shape, using excess modules and additional modules called in from the sandbox (see Figure4.b).

Figure 4 :

 4 Figure 4: Complete self-reconfiguration scheme example for the construction of a more complex shape, a sphere. a) Extended scaffold; b) Coating of the white part of the scaffold.

( 1 )

 1 REQUEST_GOAL_POSITION: Sent through Relay modules to the local Coordinator by a FreeAgent module arriving at a tile entry point location, to request a destination within this tile. (2) PROVIDE_GOAL_POSITION: Response to a goal request by a Coordinator to a FreeAgent. Follows the same path as the request. Contains a grid position to be used as goal by the receiver. (3) TILE_INSERTION_READY: Sent by the last arrived horizontal branch tip module to the FreeAgent and future tile root waiting at one of RevZ EPL of the neighbor tile. (4) INITIATE_FEEDING: Sent by a freshly arrived Coordinator

Theorem 3 . 3

 33 The complexity of the number of messages N messaдes sent to schedule the construction of a N modules pyramid is O(N 4 modul es ).

Figure 5 :

 5 Figure 5: Motion parallelism over time during the reconfiguration into a 9-pyramid (7905 modules).

Figure 6 :

 6 Figure 6: Number of messages exchanged during scaffold construction for various sizes of goal configurations.

Figure 7 :

 7 Figure 7: Maximum number of messages sent per module in a single time step for every module during a reconfiguration into a 4-pyramid

Algorithm 1 :

 1 Distributed control algorithm for the FreeAgent module role.

	Function reachedNewTileEntryPoint():
	coordinatorPos = getNearestTileRoot(getPosition());
	relayModule = findSupportOrBranchTipNeighbor();
	sendMessage(relayModule, REQUEST_GOAL_POSITION);
	Function planNextRotation():
	nbh = getNeighborhood();
	nextPosition = matchLocalRules(nbh, goalPosition, step);
	rotateTo(nextPosition);
	Event Handler ROTATION_END:
	if getPosition() == goalPosition then
	if isScaffoldComponent(getPosition()) then
	agentRole = agentRoleForComponent(getPosition());
	else
	reachedNewTileEntryPoint();
	return;
	else
	step++;
	planNextRotation();
	Message Handler PROVIDE_GOAL_POSITION(rcvdPosition):
	step = 0;
	goalPosition = rcvdPosition;
	planNextRotation();

Proc. of the 18th International Conference on Autonomous Agents and Multiagent Systems (AAMAS 2019), N. Agmon, M. E. Taylor, E. Elkind, M. Veloso (eds.), May 13-17, 2019, Montreal, Canada. © 2019 International Foundation for Autonomous Agents and Multiagent Systems (www.ifaamas.org). All rights reserved.

YouTube video of simulation at https://youtu.be/1pvNBQlcVGE

ACKNOWLEDGMENTS

This work was partially supported by the ANR (ANR-16-CE33-0022-02), the French Investissements d'Avenir program, ISITE-BFC project (ANR-15-IDEX-03), Labex ACTION program (ANR-11-LABX-01-01), and the Mobilitech project.


Pierre Thalamy

Benoît Piranda

Frédéric Lassabe

Julien Bourgeois

SCAFFOLD-BASED ASYNCHRONOUS DISTRIBUTED SELF-RECONFIGURATION BY CONTINUOUS MODULE FLOW

Distributed self-reconfiguration in large-scale modular robots is a slow process and increasing its speed a major challenge. In this article, we propose an improved and asynchronous version of a previously proposed distributed self-reconfiguration algorithm to build a parametric scaffolding structure. This scaffold can then be coated to form the desired final object. The scaffolding is built through a continuous feeding of modules into the growing shape from an underneath reserve of modules which shows a reconfiguration time improved by a factor of 3 √ N compared to the previous and synchronous version of the algorithm, therefore attaining an O(N 1/3 ) reconfiguration time, with N the number of modules in the system. Our algorithm uses a local motion coordination algorithm and pipelining techniques to ensure that modules can traverse the structure without collisions or creating deadlocks. Last but not least, our algorithm manages uncertainty in the motion duration of modules without negatively impacting reconfiguration time.

FreeAgent

I. INTRODUCTION

The Programmable Matter Project 1 [START_REF] Bourgeois | Programmable matter as a cyber-physical conjugation[END_REF] aims to build objects using modular self-reconfigurable robots [START_REF] Fukuda | Cellular robotic system (CEBOT) as one of the realization of self-organizing intelligent universal manipulator[END_REF] composed of micro-robots thus able to change their shape, a process called self-reconfiguration. The Programmable Matter Project is a follow up of the Claytonics project [START_REF] Copen Goldstein | Programmable matter[END_REF] where each micro-robot is called a Claytronics atom (Catom). An object made of Programmable Matter can be densely filled with Catoms but this creates two major problems: movements can only occur on the surface, which limits the number of parallel movements, and it immobilizes the Catoms making up the interior of the volume, which could be put to better use. Reconfiguration time is a crucial parameter for self-reconfiguration. In [START_REF] Michael Rubenstein | Kilobot: A low cost scalable robot system for collective behaviors[END_REF], using a thousand Kilobots, a reconfiguration takes from 6 to 12 hours, which limits the usefulness of self-reconfiguration. To improve on this, we propose to build objects using a sparse scaffold structure for their inner part, to which we add a coating for their outer part, thus creating the illusion of a densely filled object at a lesser cost and dramatically speeding up the reconfiguration.

In [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF], we defined the scaffolding structure, and proposed a synchronous self-reconfiguration method based on two levels of planning: (i) an ordering in the construction of the scaffold; (ii) local rules for guiding the local motion of modules. It also assumes an underneath reserve of modules, named sandbox, from which modules can be called in to take part in the reconfiguration. We showed that this method is able to build square pyramids with n O(N 2 3 ) reconfiguration † All authors are with Univ. Bourgogne Franche-Comté, FEMTO-ST Institute, CNRS, 1 cours Leprince-Ringuet, 25200, Montbéliard, France.

{first}.{last}@femto-st.fr 1 http://projects.femto-st.fr/programmable-matter/ time and using O(N 4 3 ) messages without congesting the network, with N the total number of Catoms.

However, this work presents some limitations: it relies heavily on a synchronization between the central node of a scaffold tile and the ones of the four tiles feeding it from the sandbox, as well as a fixed movement time for all modules, which is unrealistic. Furthermore, it requests modules from the sandbox only when they are needed, which slows down the reconfiguration process due to the delay between their request and arrival.

To address these limitations, we propose in this paper an asynchronous distributed algorithm which improves on the algorithm in [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF] by continuously injecting modules on the scaffold from the sandbox, regardless of the requirements of the goal shape. It therefore uses a surplus of modules which can later be used for the coating and it improves the reconfiguration time of the self-reconfiguration by a factor of 3

√

N, which corresponds to an O(N 1/3 ) reconfiguration time when building the scaffold of a square pyramid, with N the total number of Catoms. Furthermore, our algorithm does not assume any synchronization of the system to achieve these results, and is resistant to uncertainty in the rotation time of the modules. Both are made possible thanks to our motion coordination algorithm.

II. RELATED WORKS

Using scaffolding to aid self-reconfiguration is not a novel approach. To the best of our knowledge, it was introduced in [START_REF] Kotay | Algorithms for self-reconfiguring molecule motion planning[END_REF] with massive scaffold tiles consisting of 54 modules. It was then further investigated in works with cubic modules [START_REF] Støy | Using cellular automata and gradients to control selfreconfiguration[END_REF][START_REF] Støy | Self-Reconfiguration Using Directed Growth[END_REF] and [START_REF] Lengiewicz | Efficient collective shape shifting and locomotion of massively-modular robotic structures[END_REF] with a much simpler scaffold design in which modules could slide through one-modulethick tunnels. Scaffolding is very much alike some of the applications of the concept of meta-modules [START_REF] Nguyen | Controlled module density helps reconfiguration planning[END_REF][START_REF] Dewey | Generalizing metamodules to simplify planning in modular robotic systems[END_REF][START_REF] Vassilvitskii | A complete, local and parallel reconfiguration algorithm for cube style modular robots[END_REF][START_REF] Kawano | Distributed Tunneling Reconfiguration of Sliding Cubic Modular Robots in Severe Space Requirements[END_REF], where modules are grouped into logical units, which can be organized so as to form a porous structure that allows internal module movement through tunneling.

Reconfiguration can also be aided through communication. For instance, in [START_REF] Naz | A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots[END_REF], the authors propose a reconfiguration algorithm for 2D cylindrical robotic modules that uses message-based coordination to ensure that modules moving in parallel are not impeding on their respective motions. In practice, this method creates trains of rotating modules that move and stop in unison, always keeping one free lattice cell between them. Yet, the generalization of this method to 3D reconfiguration is non-trivial, as the added dimension prevents the identification of a common direction of motion for modules moving in parallel. Nevertheless, with the addition of a scaffolding structure such as ours, the navigation on a single branch of the scaffold can be again reduced to a 2D problem through pipelining, thus restoring its benefits.

III. PREREQUISITES

A. THE 3D CATOM MODULAR ROBOT

We consider a modular robot made of a very large number of 3D Catom [START_REF] Piranda | Designing a quasi-spherical module for a huge modular robot to create programmable matter[END_REF] robotic modules, arranged in a Face-Centered Cubic (FCC) lattice. 3D Catoms are micro-scale quasi spherical modules that are under development. Each 3D Catom can connect to up to 12 neighbor modules thanks to the connectors positioned on each of its sides. They communicate locally to their immediate neighbors through these same connectors, also supplying power.

3D Catoms move by rotating on the surface of a neighbor module using electrostatic actuators, acting as a pivot and providing the necessary actuation. They can use either one of the two faces (hexagonal and octagonal) to rotate on their surface (see video in footnote2 ), depending on their local motion constraints.

We assume that our modules are able to react through their programming to events related to their state or local environment, such as the arrival or departure of a neighbor (ADD NEIGHBOR / REMOVE NEIGHBOR), or the end of a rotation (ROTATION END).

Due to the geometry of 3D Catoms, a position can only be filled if the two opposite positions around it are free. Filling a gap in a line of modules is therefore impossible [START_REF] Tucci | A Distributed Self-Assembly Planning Algorithm for Modular Robots[END_REF]. This is why it is crucial to enforce a methodical construction strategy in order to avoid the occurrence of deadlocks.

Furthermore, additional motion constraints prevent a 3D Catom from performing a motion if that motion will result in a collision with another module in its first-or second-order neighborhood.

B. SCAFFOLD MODEL

We define our scaffold model as an arrangement of structured groups of modules named tiles. A scaffold tile consists of a single module at the core, referred to as tile root, and acting as the Coordinator of the construction of the tile; one or two horizontal branches along the -→ x and -→ y axes; from one to four vertical branches named ZBranch, LZBranch, RevZBranch, RZBranch; and four Support modules between the vertical branches, allowing modules coming from incident vertical branches to traverse the tile vertically. Each branch is made of b modules including the tile root, such that 4 < b < m, with b a parameter of our model and m a constant defined by the mechanical strength of 3D Catom connectors.

Modules navigate the scaffolding structure by vertically flowing from tile to tile, rotating on Support modules or the modules making up the branches of the tiles, acting as pivots. Each module or position comprising the structure of a tile can be referred to as a Tile Component. In addition to components, we define special positions around the tiles to which we will refer as Entry Point Positions, or EPL. These are the lattice cells through which modules entering a tile must pass. In this work we use the 4 EPL located centrally on each of the incoming vertical branches, over the second to last module of each incident branches (see Figure 1.a)

When a module enters a tile through one of its EPL, it has to request a goal position within that tile from the local Coordinator of that tile, which will either direct it to one of the children tile above, or a destination tile component to be claimed, if the tile is still under construction.

This work focuses on the construction of structures where all tiles of the scaffold are resting on four incident vertical branches, and therefore 4 parent tiles underneath, namely, h-pyramids. An h-pyramid is a square pyramid shape with an h-tile large square base and a height of h tiles. This simplification is useful as modules can flow through the structure vertically without having to coordinate the horizontal traversal of tiles by modules flowing from different incoming vertical tiles. This restriction will be lifted with further coordination works, and we are confident this can be done without affecting on the present results.

C. SANDBOX

As mentioned earlier, we assume that underneath the reconfiguration scene is located a reserve of modules which we will refer to as sandbox. The sandbox is a cubic volume organized into our scaffolding structure and holding a surplus of modules on its branches, and provides both power and the description of the goal shape to all modules. It allows to introduce 3D Catoms at various ground locations of the reconfiguration space, by having them rotating from the sandbox using the scaffold branches just as in our reconfiguration algorithm.

IV. SELF-RECONFIGURATION ALGORITHM

A. ROLES

Throughout this paper, we consider the following module roles for explaining the algorithm: Coordinator is the root module of a tile, acting as a local coordinator guiding the construction process of its tile; FreeAgent modules are introduced from the sandbox underneath and navigate the structure until they encounter a tile with a scaffold position to be claimed; Beam modules are any final scaffold components that are not a Coordinator (thus, branches or support modules).

B. MESSAGING

Our reconfiguration algorithm uses a number of different message types. Some of them are used by the high level reconfiguration process to direct the growth of the structure. Others have to do exclusively with the coordination of modules navigating the structure in parallel. Below is a summary of the messages used in our algorithm, their function, and their data. For additional details on RGP, PGP, and TIR, see [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF].

2) Motion coordination messages:

• PROBE LIGHT STATE (PLS) [sender, nextPos]: Sent by a module about to move in order to obtain an authorization of moving from the pivot module to which it will latch after its motion. It holds the position of the sender for routing the reply, and the position to which it seeks to move (nextPos). The latter is used by a receiver to dynamically determine the pivot that should answer. • GREEN LIGHT ON (GLO) [recipient]: This is a reply to PLS, sent back to the module which made the request by the pivot module that is ready to receive it as a neighbor.

• FINAL TARGET REACHED (FTR) [ / 0]: Pivot modules monitor changes in their neighborhood caused by moving modules in order to update their state and block or resume the flow of modules moving to their location. The flow of modules is usually resumed by a pivot when a moving module leaves the neighborhood of the pivot. However, if a moving module claims a scaffold position that is next to the pivot, a moving module will enter its neighborhood but never leave it. In this scenario, FTR is sent by the module that has just arrived to its claimed scaffold position module to instruct the pivot to resume the flow of modules even though it is still in its neighborhood. We use a distributed message passing paradigm to deliver messages from one module to another non-neighboring module. Intermediate modules (between the sender and the recipient) leverage the geometrical regularity of the structure and their local knowledge to deduce the next hop according to the message type.

C. OVERVIEW

Our reconfiguration method operates at two levels of planning.

1) High-Level Planning: The higher level of planning consists in the construction of the scaffold at the tile level, in other words, the construction of the tiles relative to each other in term of their precedence. A construction order is enforced (roughly 3D diagonal growth) based on a very simple set of rules: (i) scaffold construction must start from a single ground point; (ii) A new tile can only start undergoing construction once all its incident branches are complete. The tile construction process is then directed by the first module of a tile placed in the root position, whose role is to direct incoming module flows to the next position to be filled in the tile, following a predetermined construction plan based on the specific location of that tile within the goal shape. When their tile is complete, Coordinators are responsible for directing all modules arriving to a branch, to the branch directly above that branch.

Algorithm 1 illustrates how this behavior is implemented. See Algorithm 2 for the complementary viewpoint of FreeAgent modules.

During the construction of the scaffold, modules are continuously flowing through the structure vertically, from the sandbox below, and they only stop when they are blocked by a Coordinator after entering an EPL of its tile. The motion coordination algorithm explained in the next section allows the propagation of the halt of the flow through message passing, in addition to preventing potential collisions.

When a Coordinator gets into its final position, it initializes a queue data structure holding a list of couples SC i , EPL j where SC i is a scaffold component, i ∈ [0, 5b + 4], and EPL j is the EPL from which a module claiming the component SC i should come, j ∈ [0, 3]. This list therefore represents the ordered construction plan of the tile, computed dynamically by the Coordinator when it arrives into the tile root position and based on its position within the overall structure. This plan enforces a precedence in the placement of modules coming from different directions, in order to minimize the risk of collisions. Upon reception of an RGP message, the Coordinator checks whether the request comes from the entry point EPL i of the next component in the plan and responds with a PGP message or puts the module on hold otherwise. Whenever the construction advances through the claim of the next component by a FreeAgent module, the Coordinator checks whether it previously put on hold a module waiting on the EPL for the next component to be filled, and so on. Once the construction of the tile is over, the flow of incoming modules is left uninterrupted, and all modules are routed towards the EPL of the branch directly over the one on which they arrived.

2) Low Level Planning: Conversely, the low level planning consists in the mechanisms of the flow of modules themselves, or in other words, how FreeAgent modules navigate the tile structure once they have been assigned a goal position within a tile. Just like in [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF], each 3D Catom is given an identical set of local rules that describes the sequence of motions to be taken in order to navigate from each EPL of a tile to any component locations within that tile, or EPL of children tiles. Every time a module has to perform a motion towards a goal position, it attempts to match its local neighborhood, the number of motions since its entry into the tiles, and its goal position to an entry in its local rules database. The result is the displacement induced by its next motion towards its goal. It then searches its neighborhood for a pivot that can be used to perform a rotation representing this movement. If it cannot find a rule to match or a pivot to perform the motion, it waits and periodically checks for these conditions until they are satisfied.

D. MOTION COORDINATION ALGORITHM

We find that managing a large numbers and a high density of modules across the structure is too slow and too complicated as moving modules tend to block each other. We therefore force all modules moving concurrently to always keep a free position between each other, in a manner similar to [START_REF] Naz | A distributed self-reconfiguration algorithm for cylindrical lattice-based modular robots[END_REF].

A major difference with our previous work is that module motions now are asynchronous and can have different stochastic durations. In order to support both, we propose a distributed and local motion coordination algorithm, described in this section.

A straightforward condition to ensure that two mobile modules have always a space between them is to prevent Algorithm 2: Distributed control algorithm pseudo-code for the FreeAgent module role.

Event any module that could potentially act as a pivot from having two mobile modules connected to it at the same time. In the context of the scaffolding, pivot modules are all Beam modules, immobile modules constituting the components of the scaffold. These pivot modules can be in two states GREEN LIGHT, and RED LIGHT. GREEN LIGHT means that the pivot is accepting that a new mobile module latches onto it, while RED LIGHT means the opposite. The transition between states occurs every time a mobile module latches onto a pivot or unlatches from it, as it can be seen on Figure 2. However, if the mobile module is on its final motion to its goal position, it will send send a FTR to instruct the pivot to turn back green, as explained in Section IV-B.

Every time a module wants to move, it sends a PLS message to the pivot it plans to use for the motion. The pivot then evaluates if it should be the one responding to the request. The target pivot is one of the pivots to which the module will connect at the end of its motion. It is the one that is the farthest along the path of the moving module. When a pivot receives a motion request, it either responds directly with a GLO message if it is in the GREEN LIGHT state, or waits for its state to change back to GREEN LIGHT before responding, therefore holding the motion of the module until it is safe to proceed. This could be modeled as an ORANGE LIGHT state. Algorithms 2 and 3 show how these mechanisms are implemented. V. ANALYSIS

In this section, we study the number of modules used to construct the scaffold, and the time complexity of the reconfiguration method in the case of a pyramid shape with a height of h tiles. We also compare this work with the synchronous construction time of the scaffold presented in [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF].

The total number of modules engaged in the scaffold construction algorithm corresponds to the number of modules constituting the scaffolding structure N scaffold added to the excess modules sent by the algorithm to anticipate future constructions.

The expression of N scaffold and of the number of tiles N tiles in a pyramid of height h tiles are calculated in [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF], and reminded below:

N scaffold = (2b - 1 3 )h 3 + ( 9 2 -2b)h 2 + 5 6 h N tiles = h 3 3 + h 2 2 + h 6
Excess modules are present along the paths formed by the ascending branches of the structure. In the case of the pyramid, for each level i ∈ [2..h] there are (hi + 1) 2 tiles, each receiving 4 ascending branches from the lower level. Therefore, the total number of ascending branches is:

N Zbranch = h ∑ i=2 4(h -i + 1) 2 = 4h 3 -6h 2 + 2h 3
For each branches of length b, excess modules will fill the EPL cell at the extremity of the branch, and a number of internal position along the branch, keeping one free position between any two mobile modules. Thus, we obtain e = b 2 -2, the average number of modules per branch plus 4 modules on EPL cells for each tile.

We then deduce the total number of modules N modules :

N modules = N scaffold + 4N tile + e × N Zbranch = h 3 3 (8b + 5) + h 2 ( 25 2 -3b) + h 6 (2b -3)
We can conclude that in the case of a pyramid of height h, and in spite of excess modules, the complexity of N module is still O(h 3 ).

In the same way as in [START_REF] Thalamy | Distributed Self-Reconfiguration using a Deterministic Autonomous Scaffolding Structure[END_REF], we base our analysis on the construction tree of the scaffold, consisting of the tiles of the scaffold as vertices, and expressing the precedence in the construction of these tiles through its edges. The first tile of the pyramid, located at (0, 0, 0), is the root of the tree.

By studying displacement rules, we can observe that the time needed to place the root module of the first tile of each level i of the pyramid takes 16(b -1) time steps (ts). We can deduce that the sum of the waiting time and the motion time necessary for a tile root module to reach its position depends on its height i in the construction tree, which can be expressed as:

T tile = [16(b -1)] × ts
T tile does not depend on its height in the construction tree i, while in the previous version with waiting times, we had T tile (i) = 24 + 4b + 2b × i. This is the reason why the time complexity of this version is linear, as proven below.

T old = h ∑ i=1 24 + 4b + 2b × i = 24h + b(5h + h 2 ) (1)
Then, in the case of the pyramid of height h, considering that the number of modules is N module = O(h3 ), we can conclude that the complexity of the reconfiguration time is

O(N 1 3 modules ).
It is worth noting that for the same configuration of height h, our method admits a time complexity of O(h), a factor of h lower than our previous algorithm with waiting times admitting O(h 2 ) time steps, and without relying on any synchronization.

VI. SIMULATION

We conduct various simulations to evaluate our contributions using VisibleSim [START_REF] Benoit Piranda | VisibleSim: Your simulator for Programmable Matter[END_REF], a modular robot simulator. We study the following:

• Compare synchronous and asynchronous selfreconfiguration algorithms with varying scaffold sizes. We focus on studying the impact of the asynchronous algorithm in terms of modules count and total reconfiguration time. We measure the reconfiguration speedup and modules usage as performance indicators compared to the synchronous algorithm. • We compare an ideal fixed-time module movement model, with a more realistic model, where modules have a pseudo random movement duration defined as a normal distribution X ∼ N (µ, σ 2 ), where µ is the fixed value, and σ can be configured for simulating of varying movement reliability. • We run those tests for various scaffold height h, where h is the number of tiles layers. In Figure 3, we compare the construction time of a scaffold for various scaffold heights. The figure shows the construction time in simulator time steps in Y-axis for several h values in X-axis. Three algorithms are compared: synchronous feeding, and two variants of continuous feeding, one with fixed movement time, one with pseudo random varying movement time. We make several observations from the results: first, continuous feeding performs faster than synchronous feeding, with a speedup increasing as the scaffold height increases (This can be seen in the video showing the side-by-side execution of the two algorithms, accessible from footnote 3 . Second, both variants of continuous feeding perform almost identically, which shows that our motion coordination algorithm allow modules to synchronize with their predecessors in a very efficient manner. Figure 4 shows the percentage of module overuse due to continuous feeding, this can be compared to synchronous feeding, which has no overuse. These modules are not lost since they can be sent back to the sandbox, or used for further operations. What seems interesting is that this unused quantity starts at 36% for a small scaffold and quickly drops and stabilizes to about 25% when h ≥ 6. We provide an analysis of the convergence of the surplus as the size of the structure increases below.

Theorem 2: The rate of modules in excess has an infinite limit lower than 25%.

Proof: We express the number of modules in excess E(h) depending on the height of the pyramid by:

E(h) = N Zbranch × e E(h) N modules (h) = (b -4)(2h 3 -3h 2 + h) h 3 (8b + 5) + 3h 2 ( 25 2 -3b) + h(b -1 2 )
If we calculate lim h→∞ E(h) N modules (h) , we get:

lim h→∞ E(h) N modules (h) = 1 4 - 37 32b + 20
We can conclude that the rate of modules in excess is less than 25% for large size pyramids.

As the construction time gain increases and modules overuse remains stable as the size of the construction increases, we conclude that our new algorithm, continuous feeding, scales better than synchronous feeding. It is a key property when dealing with programmable matter, since we aim at building shapes based on micro-robots which will require an enormous amount of robots.

VII. CONCLUSION

In this paper, we propose an improved and asynchronous version of our algorithm for building a scaffold using microrobots. This algorithm uses a continuous feeding of the modules into the goal shape thus speeding the completion time by a factor of O(N 1/3 ) compared to the previous version, owing to the removal of waiting times. We also propose a coordination algorithm to avoid modules collisions during the reconfiguration. This algorithm is expressed as a set of callbacks, raised by events and messages, which sets a traffic light-like module inner state indicating when it must move and when it must wait.

Our proposal is experimented on a simple goal shape: a pyramid, defined by its global height and its individual tile size, and we provide results for varying values of both parameters. From the results, we show that our algorithm is promising: it is scalable and the modules overuse is, in percentage, stable. Furthermore, the modules unused by the scaffold could still be useful for further operations, for instance to fill the outer envelop of the goal shape. Our results also show that small motion time variations have a negligible impact on the whole reconfiguration time, making our algorithm robust to physical variations in module movements.

VIII. FUTURE WORKS

We envision as future works to first eliminate the necessity for a module surplus, which stands as the main drawback of this method, and would necessitate that each Coordinator geometrically computes the resource requirements of each children tiles. Then, we aim to extend this work to all convex shapes, for which we think our reconfiguration time result can be preserved. This requires supporting the construction of incomplete branches (i.e., where their length l < b), and new rules for feeding any growing branch from any vertical branch below. Next, we focus on concave shapes, which would necessitate the design of a coordination mechanism for modules to traverse tiles horizontally from any incident branch, as well as a way to construct tile branches in the opposite direction. This jump to generic shapes would also require a systematic method for generating a scaffold structure from the 3D description of an object. Furthermore, we plan to allow the reconfiguration of an arbitrary scaffold into another, by absorbing part of the structure to construct another in an efficient manner. Finally, we aim to design a coating algorithm that would enable one or several layers of modules to cover the scaffolding structure and therefore preserve the external aspect of the represented object.

Fig. 1 .

 1 Fig. 1. 3D structure of a tile with b = 6. a) Pink transparent cells represent the four entry points into the tile that we use, and white module represents the root R of the new tile, origin of the local coordinates system; b) 3D position of support (yellow) and branch modules of the tile.

Fig. 2 .

 2 Fig. 2. Pivot light states transition diagram. The two Beam routines are executed concurrently on pivot modules.

Theorem 1 :Fig. 3 .16b - 16 =

 1316 Fig. 3. Synchronous vs. continuous feeding comparison

Fig. 4 .

 4 Fig. 4. Modules overuse by continuous feeding

  1) Scaffold construction messages: MESSAGE NAME (ACRONYM) [DATA] • REQUEST GOAL POSITION (RGP) [sender]: Sent to the local Coordinator by a FreeAgent arriving into a new tile, to request its next destination. • PROVIDE GOAL POSITION (PGP) [recipient, goal]: Response to RGP sent by a Coordinator to a requesting FreeAgent. Includes a goal position that can either be an unfilled component of the current tile or the EPL of a tile above. Signals to the modules waiting on the EPL of a future tile that construction can proceed. Sent by the last arrived module from the last arrived incident branch to that tile.

• TILE INSERTION READY (TIR) [ / 0]: • COORDINATOR READY (CR) [ / 0]: Sent by a newly arrived coordinator to instruct FreeAgent modules waiting on an EPL that it is ready to process RGP messages.

Algorithm 1 :

 1 Distributed control algorithm pseudo-code for the Coordinator module role.

	Msg Handler REQUEST GOAL POSITION(srcPos):
	epl = getEPLForPosition(srcPos);
	if plan.isOver() then
	goalPos = getAlternateBranchEPLfor(epl);
	else if plan.nextComponentIsSourcedBy(epl) then
	goalPos = plan.popNextComponent();
	else
	moduleWaitingOnEPL[epl] = true; return;
	sendMsg(sender, PGP(srcPos, goalPos));
	checkModulesWaitingOnEntryPoints();
	Function checkModulesWaitingOnEPL:
	do
	moduleAwoken = false;
	foreach epl ∈ getAllEntryPoints() do
	if plan.nextComponentIsSourcedBy(epl) then
	goalPos = plan.popNextComponent();
	sendMsg(sender, PGP(srcPos, goalPos));
	moduleAwoken = true;
	while moduleAwoken = true;

Algorithm 3 :

 3 Distributed control algorithm pseudo-code for the Beam module role.

	Function setGreenLightAndResumeFlow():
	if state == ORANGE then
	sendMessage(sender, GLO(waitingModulePos));
	state = GREEN;
	Event Handler ADD NEIGHBOR: state = RED ;
	Event Handler REMOVE NEIGHBOR:
	setGreenLightAndResumeFlow();
	Msg Handler REQUEST GOAL POSITION(RGPmsg):
	forwardMsgTowardsCoordinator(RGPmsg);
	Msg Handler PROVIDE GOAL POSITION(PGPmsg):
	forwardMsgTowardsRecipient(PGPmsg);
	Msg Handler PROBE LIGHT STATE(PLSmsg):
	if state == GREEN then
	sendMsg(sender, GLO(PLSmsg.source));
	else
	state = ORANGE ;
	waitingModule = PLSmsg.source;
	Msg Handler FINAL TARGET REACHED(FTRmsg):
	setGreenLightAndResumeFlow();

3D Catoms motion video: https://youtu.be/IZh-5p1dbKk

Side-by-side comparison video of synchronous feeding and async: https://youtu.be/XpG20m7waJk

ACKNOWLEDGMENT

This work was partially supported by the ANR (ANR-16-CE33-0022-02), the French Investissements d'Avenir program, ISITE-BFC project (ANR-15-IDEX-03).