Tom Portoleau
email: tom.portoleau@laas.fr

Christian Artigues
email: christian.artigues@laas.fr

Tamara Borreguero Sanchidrián

Alvaro García Sánchez

Miguel Ortega Mier
email: miguel.ortega.mier@upm.es

Pierre Lopez
email: pierre.lopez@laas.fr

Large neighborhood search for a multi-mode resource constrained scheduling problem with resource leveling objective

Keywords: multi-mode resource-constrained project scheduling, resource leveling, constraint programming, large neighborhood search

Introduction

The aeronautical industry has experienced an in-depth transformation in the last years. The demand for aircrafts has increased but also the complexity and customization of the products. As a result, aircraft manufacturers have had to produce more units of more complex aircrafts while trying to reduce time to market, production lead times and costs. In line with these objectives, this paper proposes solution methods for the detailed scheduling of stations in an aircraft final assembly line. This problem, described in [START_REF] Borreguero | Exact and heuristic methods for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective[END_REF], can be classified as a multi-mode resource-constrained project scheduling problem (MMRCPSP) with a resource leveling objective. In [START_REF] Gerhards | The multi-mode resource investment problem: a benchmark library and a computational study of lower and upper bounds[END_REF]) the author proposes a constraint programming (CP) model to solve the multi-mode resource investment problem (MMRIP). Formally, this problem is very similar to the assembly line scheduling problem at stake here. The notable differences are, firstly, the presence of non-renewable resources, and secondly, a slightly different objective function, as it considers a weighted sum of the maximums of the resources used, while the assembly line scheduling problem considers the maximum peak objective without weights. We propose a large neighborhood search (LNS) heuristic with neighborhoods tailored to the resource-leveling objective, with the aim to improve the performance of the CP exact methods and of the heuristic approach currently used by the company on large-scale industrial instances. As a result, the largeneighborhood search approach significantly improves the heuristic currently used by the aircraft manufacturer for assembly line scheduling. It also brings significant improvements to the method proposed by [START_REF] Gerhards | The multi-mode resource investment problem: a benchmark library and a computational study of lower and upper bounds[END_REF] in the multimode resource investment problem when short CPU times are required.

Problem statement and constraint programming formulation

In the assembly line scheduling problem the maximum cycle time CT is fixed. We have a set of tasks W with a release date 0 and a due date CT . We have a set P of operator profiles and a set A of station areas. Each task w ∈ W can be performed by a subset P w ⊆ P of operators profiles and by a number of operators that must lie in M w = {M N w , . . . , M X w }. The baseline duration of a task w ∈ W is denoted by D w . If task w ∈ W is performed by o ∈ M w operators of profile p ∈ P w , we apply a reduction coefficient Γ opw such that its duration is equal to Γ opw D w . Furthermore, each task is performed in an area indicated by A aw = 1 if task is performed in area a ∈ A. Each area has a maximum capacity of C a operators. There is also a set P R of standard precedence constraints such that (w, w ) ∈ P R means that w cannot start before the end of w, a set N P of non-overlapping constraints between pairs of tasks such that {w, w } ∈ N P means that w and w cannot be processed in parallel and a set M T of maximal time lag constraints such that (w, w ) ∈ M T means that the start time of w must not exceed the end time of w plus a fixed time lag ∆.

We formally define the problem through the presentation of its constraint programming formulation. For modeling and solving, we use the CP Optimizer constraint-based scheduling library [START_REF] Laborie | IBM ILOG CP Optimizer for scheduling[END_REF]). Below we refer to the basic modeling elements we use. We refer to [START_REF] Laborie | IBM ILOG CP Optimizer for scheduling[END_REF] for a more detailed definition of these elements. Each task w ∈ W is modeled as an interval decision variable T w . Each possible mode of a task (number of operators o and resource profile p) is modeled as an interval optional decision variable T wop linked to the task by an alternative constraint. Precedence constraints and maximal time lag constraints are modeled by endBeforeStart and startBeforeEnd constraints, respectively. Task consumption on a resource is modeled as a pulse function. We use also noOverlap constraints for constraints related to set N P . The model comes as follows:

min p∈P n p dvar interval T w in 0..CT , ∀w ∈ W dvar interval optional T wop in 0..CT size Γ opw D w , ∀w ∈ W , p ∈ P w , o ∈ M w alternative(T w , (T wop ) p∈Pw,o∈Mw ), ∀w ∈ W endBeforeStart(T w , T w ), ∀(w, w ) ∈ P R startBeforeEnd(T w , T w , -∆), ∀(w, w ) ∈ M T w∈W |Aaw=1 p∈Pw o∈Mw pulse(T wop , o)≤ C a , ∀a ∈ A w∈W,o∈Mw pulse(T wop , o)≤ n p , ∀p ∈ P noOverlap(T w , T w ), ∀{w, w } ∈ N P 3 A large neighborhood search approach
LNS is generally applied to scheduling problems where the objective is to minimize a time-related criterion or an outsourcing cost. A typical large neighborhood of a solution in this context consists in selecting a time interval and fixing all activities scheduled outside the interval and compacting as much as possible the activities scheduled over the interval, as it was done for the RCPSP in [START_REF] Palpant | LSSPER: Solving the resource-constrained project scheduling problem with large neighbourhood search[END_REF]. Notably, the default search of the IBM CP Optimizer we used in the previous section also implements an LNS method based on this principle [START_REF] Laborie | IBM ILOG CP Optimizer for scheduling[END_REF]. This is not what we should do for the considered problem, as compacting a schedule as much as possible would inevitably increase the resource usage. In the problem considered here, we aim at minimizing the maximal use of a given resource. We aim at identifying the set of tasks that are involved in the maximal resource peaks. Consider a solution S where each task w ∈ W has start time Sw ∈ [0, CT ], a number of assigned operators ōw ∈ M w for operator profile pw ∈ P w and a maximal number of operators np for each operator profile p ∈ P . The set of peak tasks is the set of all critical sets as defined below: Definition 1. A critical set W is a set of overlapping tasks that reaches the maximal number of operators for at least one profile p ∈ P . More formally: ∃t ∈ [0, CT ], ∃p ∈ P , ∀w ∈ W , pw = p, Sw ≤ t < Sw + Γ ōw pww D w and w∈C ōw = np .

In fact, the resource usage only changes at the beginning or the end of a task. Let T denote the set of different start and end times of the tasks. The set of all critical sets can be enumerated by a sweep algorithm that tests the condition of definition 1 for each set built by the task that overlaps each time point in T . Algorithm 1 describes the sweep algorithm that computes the set of all peak tasks C in O|W | 2 |P | time.

Algorithm 1 The sweep algorithm for peak task computation

Require: A problem P and a solution S = {( Sw, pw, ōw)w∈W , (np In order to generate a high quality neighborhood, we let free all the tasks that contribute to the maximal use of the objective resource (the ones belonging to the peak set computed by the sweep algorithm) and the tasks that must precede them by a precedence constraint, and we fix the others. We then solve this new problem given the bound provided by the value of the initial solution and the constraints induced by the fixed tasks, within a limited time. If a solution has been found, it replaces the initial solution as the best solution and we start over. However, if no solution was found, we solve a new problem, fixing fewer tasks and setting a greater solving time, using a self-adaptive principle [START_REF] Palpant | LSSPER: Solving the resource-constrained project scheduling problem with large neighbourhood search[END_REF]. To be more specific, each time the solver is unable to find a solution, we fix 10% less activities and add 10 seconds to the maximum solving time. These values were determined empirically using the instances from the benchmark considered in the previous sections. In our implementation, we use CP Optimizer as a black box to solve different generated subproblems using the constraint programming model described in Section 2. Algorithm 2 provides the pseudo-code of our implementation of the LNS method for the aircraft assembly line scheduling problem. Note that presenceOf(T wop ) in the CP Optimizer language is a constraint that enforces the presence of the optimal task T wop , while startAt(T w , t) is a constraint that fixes the start time of task T w to value t. These two constraints are used to fix the modes and the start times of the tasks in W \ W while the tasks in W are freed and form the LNS subproblem. Note that τ is a value much lower than τ giving the amount of time devoted to the CP solver to get an initial solution.

)p∈P } C ← ∅ T ← { Sw|w ∈ W } ∪ { Sw + Γō w pw w Dw|w ∈ W } for p ∈ P do for t ∈ T do W ← ∅; cons ← 0 for w ∈ W do if pw = p

Experimental results

We first compare LNS with CP optimizer and with a heuristic used by the aircraft manufacturer [START_REF] Borreguero | Exact and heuristic methods for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective[END_REF]) on a set of 7 industrial instances having from 90 up

  and Sw ≤ t < Sw + Γō w pw w Dw then W ← W ∪ {w}; cons ← cons + ōw

	end if
	end for
	if cons = np then
	C ← C ∪	W
	end if
	end for
	end for
	return C

to 721 tasks. For a 15 min CPU time limit, LNS improves the CP optimizer solutions for 5 out of 7 instances from 5.2% to 17.6%. Compared to the heuristic used by the manufacturer, the improvement on 4 out of 7 instances goes from 4.5% to 27.7% and for one instance LNS finds a solution while the heuristic is unable to find one. We also compare LNS to the CP optimizer model proposed in [START_REF] Gerhards | The multi-mode resource investment problem: a benchmark library and a computational study of lower and upper bounds[END_REF]) on the MMRIP. The results displayed in Table 1 for different CPU times and numbers of tasks (from 30 to 100) show significant improvements. Detailed results are given in [START_REF] Borreguero | Exact and heuristic methods for an aeronautical assembly line time-constrained scheduling problem with multiple modes and a resource leveling objective[END_REF].


Marius Bozga
email: fbozga@imag.fr

Conrado Daws
email: daws@imag.fr

Oded Maler
email: maler@imag.fr

Alfredo Olivero
email: alfredo@ungs.edu.ar

Stavros Tripakis
email: tripakisg@imag.fr

Sergio Yovine
email: yovine@imag.fr

Kronos: a model-checking tool for real-time systems

come

General presentation

 Kronos 8,[START_REF] Daws | Two examples of veri cation of multirate timed automata with KRONOS[END_REF][START_REF] Daws | The tool KRONOS[END_REF][START_REF] Daws | Reducing the number of clock variables of timed automata[END_REF][START_REF] Tripakis | Analysis of timed systems based on time{abstracting bisimulations[END_REF][START_REF] Maler | Hardware timing veri cation using KRONOS[END_REF][START_REF] Bozga | Some progress in the symbolic veri cation of timed automata[END_REF][START_REF] Bouajjani | On-the-y symbolic model checking for real-time systems[END_REF][START_REF] Daws | Model checking of real-time reachability properties using abstractions[END_REF]is a software tool aiming at assisting designers of real-time systems to develop projects meeting the speci ed requirements.

One major objective of Kronos is to provide a veri cation engine to be integrated into design environments for real-time systems in a wide range of application areas. Real-time communication protocols 8,10], timed asynchronous circuits [START_REF] Maler | Hardware timing veri cation using KRONOS[END_REF][START_REF] Bozga | Some progress in the symbolic veri cation of timed automata[END_REF], and hybrid systems [START_REF] Olivero | Using abstractions for the veri cation of linear hybrid systems[END_REF][START_REF] Daws | Two examples of veri cation of multirate timed automata with KRONOS[END_REF] are some examples of application domains where Kronos has already been used.

Kronos has been also used in analyzing real-time systems modeled in several other process description formalisms, such as Atp 17], Aorta 5], Et-lotos 8], and T-argos 15]. On the other direction, the tool itself provides an interface to untimed formalisms such as labeled-transition systems (LTS) which has been used to exploit untimed veri cation techniques 20].

Theoretical background

The system-description language of Kronos is the model of timed automata 2], which are communicating nite-state machines extended with continuous realvalued variables (clocks) used to measure time delays. Usually a system is modeled as a network of automata. Communication is achieved by label synchronization a la CCS or CSP (binary or n-ary rendez-vous), or shared variables (of bounded integer or enumeration type).

System requirements can be speci ed in Kronos using a variety of formalisms, such as the real-time logic Tctl 1,14], timed B uchi automata, or untimed LTS. These formalisms are useful for expressing most interesting classes of (timed or untimed) properties about systems, namely, safety properties (for example, absence of deadlock, invariant, bounded-delay response, etc), as well as liveness properties (for example, time progress, regular occurrence of certain events, etc) 1 .

The main veri cation engine of the tool is based on the model-checking approach which comprises both analysis: (a) checking whether requirements are satis ed, (b) providing diagnostic trails (i.e., execution sequences) demonstrating why a property holds or does not hold; and synthesis: adjusting the system (for instance, by computing a restricted sub-system) so that it meets its requirements. Model-checking is done using two methods: (a) the xpoint method, which, given a timed automaton and a Tctl formula, performs a nested xpoint computation starting from an initial set of states and iterating a precondition operator until stabilization (the operator depends on the type of the formula); (b) the explorative method, which, given a network of timed automata and a speci cation (in terms of a Tctl formula or a timed B uchi automaton), generates the reachability graph of the system while checking at the same time whether the property holds. In the case of safety properties a simple (depth-rst or breadth-rst) search of the reachability graph su ces. In the case of general properties, speci ed as timed B uchi automata, a double search is performed, rening parts of the graph whenever necessary. Both methods are interesting: the main advantage of the xpoint method is that it can be implemented in a purely symbolic manner, using structures like BDD for e ciency (see below); on the other hand, the explorative method is more suitable for on-the-y veri cation (see below) and can also provide diagnostic trails.

Apart from model-checking, Kronos o ers the possibility to (a) generate the system's reachable state space (to check, for instance, whether an error state can be reached), and (b) compute the coarsest partition of the state space with respect to the time-abstracting bisimulation, an equivalence relating states which lead to the same untimed behavior regardless the exact time delays. This method provides an interface to LTS and veri cation by bisimulation or simulation equivalences 20] using the Aldebaran tool suite 13].

Supported veri cation techniques

The main obstacle in the applicability of model-checking is the so-called stateexplosion problem re ecting the fact that the size of the system's state space is often huge. In order to tackle this, Kronos o ers a number of e cient veri cation techniques, each of which is best suited for di erent applications.

{ Symbolic representation of states means dealing with predicates representing sets of states rather than individual states. This results into a much more compact representation and storage. In the current Kronos implementation, sets of clock values are represented using the di erence bounds matrix (DBM) structure introduced in 12], whereas discrete variables are encoded as binary decision diagrams (BDD) 6].

{ On-the-y model-checking means dynamically building the state space during the model-checking process, as directed by the model-checking goal (for instance, the property to be veri ed); this results in saving up space and time, as well as in giving diagnostics as soon as possible.

{ Abstractions are used for the exploration of a coarser state space than the \real" (concrete) one; they result into space and time savings, at the cost of loosing information, so that sometimes de nite conclusions cannot be made.

{ Syntactic optimizations are used to reduce the number of clocks in the model to only the strict necessary; they allow for space and time savings at almost no cost since they are inexpensive to compute.

{ Forward or backward techniques: in the former (typically used in the explorative method) the exploration starts from initial states and tries to reach some target, while in the latter (typically used in the xpoint method) it is the inverse that happens. Combined with various search algorithms (such as depth-rst or breadth-rst) implemented in the model-checking engine of the tool, these alternative techniques result in a large exibility with respect to the di erent application needs.

{ Minimization: it is used to generate the time-abstracting minimal model of the system, which can then be visualized as an untimed graph, compared or further reduced with respect to untimed equivalences, or checked using untimed temporal logics.

Case studies

Kronos has been used to verify various industrial communication protocols, such as an audio-transmission protocol by Philips 10] (where errors have been found to the previously hand-made proofs) or an ATM protocol by CNET 19] (where a bug was also found relative to the consistency of the network components). Other communication protocols modeled and veri ed by Kronos include the carrier-sense multiple-access with collision detection (CSMA-CD) protocol 8] and the ber-optic data-interface (FDDI) protocol 9]. Well-known benchmark case studies veri ed by Kronos include Fischer's real-time mutualexclusion protocol 9] and a production-plant case study 10]. Finally, the tool has been also applied to the veri cation of the Stari chip 4] and to the synthesis of real-time schedulers 2 .

The most recent enhancements of Kronos include the implementation of different abstraction mechanisms 9], the implementation of a symbolic on-the-y algorithmfor checking timed B uchi automata emptiness 3] and a BDD-based implementation oriented towards the timing analysis of circuits 4]. Table 1 presents some typical experimental results extracted from the cited papers. The measurements were taken on a Sparc Ultra-1 with 128 Mbytes of main memory. Time is given in seconds. The size of the state space (when available) is given in symbolic states (i.e., control location plus DBM), BDD nodes, or states and transitions. \OTF" stands for \on-the-y". It is worth noting that the entire machinery of Kronos has been useful for handling the above examples. In particular, the xpoint method has been used in earlier versions of the tool for liveness properties, as well as for synthesis (see, for instance, 10], where initial constraints have been tightened so that the system behaves correctly). Forward model-checking using timed B uchi automata has been recently used for checking liveness on the FDDI protocol for up to 7 processes, as well as to provide diagnostics in the real-time scheduling problem. Minimization has been used for visualizing the behavior of timed automata. On-the-y techniques have been used whenever syntactic parallel composition could not be applied due to state explosion. Abstractions and clock-reduction techniques have been essential to the veri cation of the FDDI example for up to 50 processes, and Fischer's protocol for up to 9 processes 9].

Table 1 .

 1 Some performance results.

	Case study Production plant Fixpoint Method CNET Forward Philips Forward Fischer (5 processes) Minimization Fischer (6 processes) OTF Fischer (9 processes) OTF & Abstractions FDDI (7 stations) OTF & B uchi aut. FDDI (12 stations) Forward FDDI (50 stations) Forward & Abstractions 3900 4000 symb. states Time State space 26 not available 3 not available 2 not available 32 3000 states & trans. 2783 164935 symb. states 17098 1096194 symb. states 4813 57500 symb. states 1123 13000 symb. states Stari (17 stages) Fixpoint & BDD 100000 1000000 BDD nodes

? Kronos is developed at Verimag, a joint laboratory of UJF, Ensimag and CNRS. http://www.imag.fr/VERIMAG/PEOPLE/Sergio.Yovine/kronos/kronos.html. C. Daws, A. Olivero and S. Yovine partially supported by European Contract KIT

To our knowledge, Kronos is the only real-time veri cation tool which can handle liveness properties.

Unpublished work.

Availability Kronos is freely available for universities or any other non-pro t organisms. It can be obtained through the web at: http://www.imag.fr/VERIMAG/PEOPLE/Sergio.Yovine/kronos/kronos.html or by anonymous ftp at: host: ftp.imag.fr, directory: VERIMAG/KRONOS/tool/. The distribution package includes executables for various architectures (Sun5, Linux, Windows NT), documentation and examples.


Ben Ramzi

Marius Salah

Oded Bozga

Maler

On Timing Analysis of Combinational Circuits ⋆

In this paper we report some progress in applying timed automata technology to large-scale problems. We focus on the problem of finding maximal stabilization time for combinational circuits whose inputs change only once and hence they can be modeled using acyclic timed automata. We develop a "divideand-conquer" methodology based on decomposing the circuit into sub-circuits and using timed automata analysis tools to build conservative low-complexity approximations of the sub-circuits to be used as inputs for the rest of the system. Some preliminary results of this methodology are reported.

Introduction

It is well known that timed automata (TA) [START_REF] Alur | A Theory of Timed Automata[END_REF] are well suited for modeling delays in digital circuits [START_REF] Dill | Timing Assumptions and Verification of Finite-State Concurrent Systems[END_REF][START_REF] Lewis | Finite-state Analysis of Asynchronous Circuits with Bounded Temporal Uncertainty[END_REF][START_REF] Maler | Timing Analysis of Asynchronous Circuits using Timed Automata[END_REF]. Although some applications of TA technology for solving timing-related problems for such circuits have been reported [MY96,BMPY97,TKB97,TKY + 98,BMT99,BJMY02], the state-and clock-explosion associated with such models, restricted the applicability of TA to small circuits. In this work we try to treat larger combinational circuits by using the old-fashioned recipe of abstraction and approximation. When viewed from a purely-functional point of view, combinational circuits realize instantaneous Boolean functions. However, when gate delays are taken into account, the computation of that function is not considered anymore as an atomic action but rather as a process where changes in the inputs are gradually propagated to the outputs. The question of finding the worst-case propagation delay of the circuit, that is, the maximal time that may elapse between a change in the inputs and the last change in the outputs, is of extreme practical importance as it determines, for example, the frequency of the clock with which a circuit can operate. Static techniques currently practiced in industry are based on finding the longest (in terms of accumulated delays) path from inputs to outputs in the circuit. While these bounds are easy to compute (polynomial in the size of the circuit), they can be over pessimistic because they abstract from the particular logic of the circuit which may prevent such longest paths from being exercised. 1 On the other hand, models based on timed automata do express the interaction between logic and timing and hence can lead to more accurate results. Alas, TA-based techniques are still very far from being applicable to industrial-size circuits.

The present paper attempt to find a better trade-off between accuracy and tractability by using timed automata as an underlying semantic model and by applying abstraction techniques to parts of the circuit in order to build for them small over-approximating timed automata that can be plugged as inputs to other parts of the circuit. Our abstraction technique takes advantage of the acyclic nature of the circuits and their corresponding automata, which implies, among other things, that every variable changes finitely many times before stabilization in every run of the automaton.

The rest of the paper is organized as follows: in Section 2 we give a formal definition of circuits, their "languages" and the maximal stabilization time problem. In section 3 we explain the modeling of such circuits as timed automata. Section 4 is devoted to our abstraction technique, its properties and the way it is implemented using the tools IF/Kronos and Aldebaran. Preliminary experimental results are reported in Section 5 followed by a discussion of related work and future directions.

Timed Boolean Circuits

Throughout this paper we restrict ourselves to acyclic circuits.

Definition 1 (Boolean Circuits).

A Boolean circuit is C = (V, ;, F ) where V is a set of nodes, ; is an irreflexive and anti-symmetric binary relation and F is a function that assigns to every non-input node v a Boolean function F v Here v ; v ′ means that v influences v ′ directly. The transitive closure of ;, * ;, induces a strict partial order (V, * ;) where the minimal elements are called input nodes and are denoted by V x . The rest of the nodes are called non-input nodes and denoted by V y . A subset V z of V consists of output nodes, those that are observable from the outside. An example appears in Figure 1-(a). The set of immediate predecessors of a node is π(v) = {v ′ : v ′ ; v} and the set of its predecessors (backward cone) is π * (v) = {v ′ : v ′ * ; v}. By substitution we define for every node v a function G v defined on the inputs in its backward cone, for example,

G y 3 (x 1 , x 2 ) = f 3 (x 1 , f 2 (x 1 , x 2 )). We will use X = B |V x | , Y = B |V y | and Z = B |V z |
to denote the sets of possible 1 A lot of effort has been invested in the problem of detecting such "false paths". assignments to input, non-input and output nodes, respectively. The whole circuit can be viewed as computing a function G : X → Y . The stable state of the circuit associated with an input vector x ∈ X is y = G(x). This concludes the formalization of Boolean circuits and their functions. These functions are instantaneous with no notion of time. The next step is to lift them to functions (operators) on signals, that is, on functions that specify the evolution of a value over (continuous) time.

Definition 2 (Signals).

Let A be a set and let T = R + be a time domain. An A-valued signal over T is a partial function α : T → A whose domain of definition is an interval [0, r) for some r ∈ T .

We use α[t] to denote the value of α at t, and α[t] = ⊥ to denote the fact that a is not defined at t. When A is finite, signals are piecewise-constant and make discontinuous jumps at certain points in time. This is formalized as follows. The left limit of a signal α at time t is defined as α[t -] = lim t ′ →t α[t ′ ]. For every piecewise-constant signal α we define:

-The ordered set of jump points,

J (α) = {t : α[t -] = α[t]} = {t 0 , t 1 , . . .}.
-The set of maximally-uniform intervals I(α) = {I 1 , I 2 , . . .} where

I i = [t i-1 , t i ) for t i-1 , t i ∈ J (α).
Clearly, the value of α is uniform over any subset of a maximally-uniform interval. We restrict our attention to well-behaving signals i.e. those for which J (α) has finitely-many elements in any finite interval. We denote the set of A-valued signals by S(A).

When a gate or any other I/O device gets a signal as an input, it transforms it into an output signal. This is captured mathematically by what is called a transducer, or a signal operator, a function that maps signals to signals. We restrict such functions to be causal, that is, the value of the output at time t can depend only on the value of the input in times [0, t] and not on later values. The simplest type of operators are memoryless (instantaneous) operators defined as follows.

Definition 3 (Memoryless Operators). A memoryless signal operator is a function f : S(A) → S(B) obtained as a pointwise extension of a function f

: A → B, that is, β = f (α) if β[t] = f (α[t]
) for every t in the domain of α.

In reality, since gates are realized by continuous physical processes, it takes some time to propagate changes from input to output ports. To define this phenomenon mathematically we need the basic operator with memory for discretevalued signals, the delay, which takes a signal and "shifts" it in time. One can define a variety of delay operators differing from each other in complexity and in physical faithfulness. The class of models that we consider is called bi-bounded inertial delays [START_REF] Brzozowski | Asynchronous Circuits[END_REF] and is characterized by an interval I = [l, u] which gives lower and upper bounds on the propagation delay. For the purpose of this paper we will use the model introduced in [MP95] but since the choice of the delay model is orthogonal to the rest of the methodology we will defer the exact definition of the operator to Section 3 where it will be defined in terms of its corresponding timed automaton and use meanwhile a general semi-formal definition.

Definition 4 (Delay Operators). A delay operator is a non-deterministic function of the form D

I : A × S(A) → 2 S(A) where I = [l, u] is a parameter of the operator with l > 0. A signal β is in ∆ I (b, α) if 1.
The value of β is b at the initial interval [0, t); 2. Changes in α are not propagated to β before l time elapses; 3. Changes in α must be propagated to β if they persist for u time; 4. Changes in α that persist for less then l time are not propagated at all to β.

Figure 2 illustrates such an operator which, typically, will have uncountablymany output signals for an input signal. All signal operators can be lifted naturally into operators on sets of signals.

A timed circuit model is obtained from a Boolean circuit by connecting the output of every non-input node to a delay operator which models the delay associated with the computation of that node (see Figure 1-(b). In other words, a gate with a propagation delay is modeled as a composition of a memoryless Boolean operator and a delay operator (see [START_REF] Maler | Timing Analysis of Asynchronous Circuits using Timed Automata[END_REF]).

Definition 5 (Timed Boolean Circuits).

A timed Boolean circuit is C = (V, ; , F, I) where (V, ;, F ) is a Boolean circuit and I is a function assigning to every non-input node v a delay interval The semantics of a timed circuit is given in terms of a non-deterministic transducer F C : Y × S(X) → 2 S(Y ) such that β ∈ F C (y, α) if α and β satisfy the set of signal inclusions associated naturally with the circuit [START_REF] Maler | Timing Analysis of Asynchronous Circuits using Timed Automata[END_REF] and y is the initial state of the non-input part of the circuit.

I v = [l v , u v ] such that 0 < l v ≤ u v < ∞. t α . . . . . . t + 2 t + 2 < t ′ < t + 3 t + 3
The stabilization time problem is motivated by the use of Boolean circuits in synchronous sequential machines (the hardware name for automata). At the beginning of every clock cycle new input values together with the values of memory elements (computed in the previous cycle) are fed into the circuit and the changes are propagated until the circuit stabilizes and the clock falls. The "width" of the clock needs to be large enough to cover the longest possible stabilization time of the circuit over all admissible inputs. In our modeling approach we will consider primary inputs that change at most once and within a bounded amount of time and hence, due to acyclicity and the finite upper-bounds associated with the delays, they induce finitely many changes throughout the circuit.

Definition 6 (Ultimately-Constant Signals).

A signal α is ultimately-constant (u.c.) if it has a finite number of jump points (i.e. there is some time t such that the signal remains constant after t). The minimal such t for α is called its stabilization time and is denoted by θ(α). This definition extends to sets of signals by letting θ(L) = max{θ(α) : α ∈ L}.

The following properties hold for every u.c. signal α:

1. The signal f (α) is also u.c. for every Boolean function f . 2. For a delay operator D I with I = [l, u] and for every β

∈ D I (α), θ(β) ≤ θ(α) + u.
Consequently, u.c. inputs to acyclic timed circuits produce u.c. outputs. Constant signals constitute a special class of u.c. signals and we will use α x to denote a signal whose value is constantly x.

We can now define the problem of maximal stabilization time of a circuit with respect to a pair of input vectors x and x ′ where x is the input presented in the preceding cycle, and which determines the initial (stable) state, and x ′ is the value of a new constant signal. We denote by L(C, x, x ′ ) the set of Y -signals β ∈ F C (y, α x ′ ) when the circuit is initialized with the stable state y = G(x).

Definition 7 (Stabilization Time of a Circuit). Given a timed Boolean circuit C = (V, ;, F, I) and two input vectors x, x ′ ∈ X the stabilization time associated with (x, x ′ ) is θ(C, x, x ′ ) = max{θ(β) : β ∈ L(C, x, x ′ )} and the maximal stabilization time of the circuit is θ(C) = max{θ(C, x, x ′ ) : x, x ′ ∈ X}.

Modeling with Timed Automata

Timed automata are automata augmented with continuous clock variables whose values grow uniformly at every state. Clocks can be reset to zero at certain transitions and tests on their values can be used in conditions for enabling transitions.

Definition 8 (Timed Automaton). A timed automaton is

A = (Q, C, I, ∆)
where Q is a finite set of states, C is a finite set of clocks, I is the staying condition (invariant), assigning to every q ∈ Q a conjunction I q of inequalities of the form c ≤ u, for some clock c and integer u, and ∆ is a transition relation consisting of elements of the form (q, φ, ρ, q ′ ) where q and q ′ are states, ρ ⊆ C and φ (the transition guard) is a conjunction of formulae of the form (c ≥ l) for some clock c and integer l.

A clock valuation is a function v : C → R + ∪ {0} and a configuration of the automaton is a pair (q, v) consisting of a discrete state (location) and a clock valuation. Every subset ρ ⊆ C induces a reset function Reset ρ on valuations which resets to zero all the clocks in ρ and leaves the other clocks unchanged. We use 1 to denote the unit vector (1, . . . , 1) and 0 for the zero vector. We will use the term constraints to refer to both guards and staying conditions. A step of the automaton is one of the following:

-A discrete step: (q, v) δ -→ (q ′ , v ′ ), for some transition δ = (q, φ, ρ, q ′ ) ∈ ∆, such that v satisfies φ and v ′ = Reset ρ (v). -A time step: (q, v) t -→ (q, v + t1), t ∈ R + such that v + t1 satisfies I q .
A run of the automaton starting from a configuration (q 0 , v 0 ) is a finite sequence of steps ξ : (q 0 , v 0 )

t 1 -→ (q 1 , v 1 ) t 2 -→ • • • t n -→ (q n , v n ).
We model timed circuits as a composition of timed automata such that each automaton may observe the states of other automata and refer to them in its transition guards and staying conditions. 2 The automaton for a Boolean gate of the form y = f (x 1 , x 2 ) is just a trivial one-state automaton that has self-looping transitions for all tuples (x 1 , x 2 , y) that satisfy the equation. In fact, this is not really an automaton but an instantaneous logical constraint that must always be satisfied. The automaton for the delay operator D [l,u] (Figure 3) has four states, 0, 0 ′ , 1, 1 ′ . The 0 and 1 states are stable, that is, the values of the output of the delay is consistent with its input x. When at state 0, if the input changes to 1, the automaton moves to an unstable state 0 ′ and resets a clock C to zero. It can stay at 0 ′ as long as C < u and can switch to stable state 1 as soon as C ≥ l. If the input changes back to 0 before the transition to 1 the automaton returns to 0. We call these three types of transitions excite, stabilize and regret, respectively. Note that states 0 and 0 ′ are indistinguishable from the outside and another automaton will see a change from 0 to 1 only after the "stabilize" transition.

x = 0/C := 0 0 1 x = 1 x = 0 x = 1∧ C < u x = 0∧ C < u x = 1∧ l ≤ C∧ C ≤ u x = 0 ∧ C < u x = 1 ∧ C < u x = 1/C := 0 x = 0∧ l ≤ C∧ C ≤ u 1 ′ 0 ′
Fig. 3. The timed automaton for a delay element. The x variable refers to the observable state of the input automaton which is 0 at {0, 0 ′ } and 1 at {1, 1 ′ }.

Composing all the automata, together with the model of their inputs we obtain a closed automaton as in Definition 8 whose semantics is identical to that of the timed circuit [START_REF] Maler | Timing Analysis of Asynchronous Circuits using Timed Automata[END_REF]. To be more precise, an automaton whose semantics is L(C, x, x ′ ) is obtained by letting the initial state be the stable state corresponding to G(x) and composing it with a static automaton for the input x ′ . The obtained automaton is acyclic and all paths converge in finite time to the only stable state that corresponds to G(x ′ ). The maximal stabilization time is hence the maximal time that the automaton can stay in any unstable state. Note that in such a state at least one of the components is in a 0 ′ or 1 ′ state and hence its staying condition forces it to leave the state.

We recall some definitions commonly-used in the verification of timed automata [HNSY94,Y97,LPY97,BDM + 98,A99]. A zone is a set of clock valuations consisting of points satisfying a conjunction of inequalities of the form c i -c j ≥ d or c i ≥ d. A symbolic state is a pair (q, Z) where q is a discrete state and Z is a zone. It denotes the set of configurations {(q, z) : z ∈ Z}. Symbolic states are closed under the following operations:

-The time successor of (q, Z) is the set of configurations which are reachable from (q, Z) by letting time progress without violating the staying condition of q:

P ost t (q, Z) = {(q, z + r1) : z ∈ Z, r ≥ 0, z + r1 ∈ I q }.
We say that (q, Z) is time-closed if (q, Z) = P ost t (q, Z). -The δ-transition successor of (q, Z) is the set of configurations reachable from (q, Z) by taking the transition δ = (q, φ, ρ, q ′ ) ∈ ∆:

P ost δ (q, Z) = {(q ′ , Reset ρ (z)) : z ∈ Z ∩ φ}.
-The δ-successor of a time-closed symbolic state (q, Z) is the set of configurations reachable by a δ-transition followed by passage of time:

Succ δ (q, Z) = P ost t (P ost δ (q, Z)).

The forward reachability algorithm for TA starts with an initial zone and generates all successors until termination, while doing so it generates the reachability graph (also known as the simulation graph).

Definition 9 (Reachability Graph).

The reachability graph associated with a timed automaton starting from a state s is a directed graph S = (N, →) such that N is the smallest set of symbolic states containing P ost t (s, {0}) and closed under Succ δ . The edges are all pairs of symbolic states related by Succ δ .

The fundamental property of the reachability graph is that it admits a path from (q, Z) to (q ′ , Z ′ ) if and only if for every v ′ ∈ Z ′ there exists v ∈ Z and a run of the automaton from (q, v) to (q ′ , v ′ ). Hence the union of all reachable symbolic states gives exactly the reachable configurations. To compute the maximal stabilization time we add an auxiliary clock T which is never reset to zero and hence in every reachable configuration its value represents the total time elapsed since the beginning of the run. The maximal value of T over all reachable symbolic states (q, Z) with q unstable is the maximal stabilization time (note that due to acyclicity the value of T is bounded in all unstable states). Hence, the problem of maximal stabilization time can, in principle, be solved using standard TA verification tools.

Given the complexity of TA verification we move to an abstraction methodology based on the following simple idea. We decompose the circuit into sub-circuits small enough to be handled completely by TA verification tools. We take the automaton A which corresponds to such a sub-circuit and use its reachability graph to construct an automaton  having two important properties:

1. The set L( Â) of signals that it generates is a reasonable over-approximation of the projection of L(A) on the output variables of the circuit. 2. It is much smaller than A in terms of states and clocks.

Hence if we replace A by  as a model of the sub-circuit we are guaranteed to over-approximate the semantics of the circuit and hence to over-approximate the stabilization time. To better understand the technique it is worth looking at the reachability graph from a different angle. In timed automata, as in any other automata augmented with auxiliary variables, the transition graph is misleading because a discrete state stands for many possible clock valuation which may differ in the constraints they satisfy and hence in the behaviors that can be generated from them. It might be the case that a state q will never be reached with a clock valuation satisfying some transition guard and hence the corresponding transition will never be taken. By performing the reachability algorithm for A starting from an initial state we obtain a graph which represents the "feasible part" of A, excluding behaviors that violate timing constraints. Figure 5-(a) shows the reachability graph for the circuit of Figure 1-(b) where the inputs change from (0, 1) to (1, 0). In fact the reachability graph can serve as a skeleton of another timed automaton A ′ whose semantics in terms of runs is equivalent to that of A.

/C 2 := 0 C 1 ∈ [l 1 , u 1 ] C 2 ∈ [l 2 , u 2 ] T ∈ [l 1 , u 1 ] T ∈ [l 1 + l 2 , u 1 + u 2 ] (a) (b)
To see that, one just has to associate with each symbolic state (q, Z) the staying condition Z and label each transition (q, Z) δ -→ (q ′ , Z ′ ) by the guard and reset of δ. The resulting automaton A ′ differs from A in two aspects: certain states of A are split into several copies according to clock values, and all transitions that are not possible in A due to timing constraints do not appear in A ′ at all. Now if we relax some timing constraints in A ′ we may introduce spurious behaviors that violate these constraints, however we will not add any new qualitative behavior (sequence of events) that was not possible in A because such behaviors have already been eliminated while computing the reachability graph. The most straightforward way to relax timing constraints is to project the constraints on a subset of the clocks and discard the rest. In particular if we throw away all clocks except T which measures the absolute time, the relaxed guard for any transition will be of the form T ∈ [t 1 , t 2 ]. Clearly, a transition can be taken in the new automaton iff there is a run of the original automaton in which the corresponding transition could be taken at some time t ∈ [t 1 , t 2 ]. However, this abstraction can add additional runs which are impossible in the original automaton as the following example shows. Consider the automaton of Figure 4-(a) where the first transition could take place in [l 1 , u 1 ] while the second can take place between l 2 and u 2 after the occurrence of the first. Applying the above procedure we obtain the automaton of Figure 4-(b) where the second transition could be taken anywhere in [l 1 + l 2 , u 1 + u 2 ] regardless of the time of the first.

The next step is to hide transitions which are not observable from the outside, i.e. all transitions of non-output variable and all non-visible transitions ("excite" and "regret") of the output variables y 2 and z. The one-clock automaton thus obtained for our example appears in Figure 5-(b). We then apply a minimization algorithm which merges states that are indistinguishable with respect to the remaining visible transitions. More formally we consider the congruence relation ∼ on the nodes of the labeled reachability graph defined as the largest relation satisfying:

q 1 ∼ q 2 iff ∀δ, I q 1 τ * •(δ,I) -→ q ′ 1 ⇒ (∃q ′ 2 s.t. q 2 τ * •(δ,I) -→ q ′ 2 ∧ q ′ 1 ∼ q ′ 2 ).
(1) Here (δ, I) stands for a transition-interval pair and τ * to an arbitrary sequence of unobservable transition. This relation is the "safety bisimulation" of [BFG + 91]. The minimized automaton, whose states are congruence classes of ∼, can be seen in Figure 6-(a).

Relation (1) looks at transition labels in a purely-syntactic manner, that is, the label -y 2 [20,30] in Figure 6-(a) is considered distinct from -y 2 [20, 40] and hence the transitions are not merged. To obtain a more aggressive abstraction we define a weaker equivalence ∼ ′ that ignores differences in intervals:

q 1 ∼ ′ q 2 iff ∀δ, I q 1 τ * •(δ,I) -→ q ′ 1 ⇒ (∃q ′ 2 , I ′ s.t. q 2 τ * •(δ,I ′ ) -→ q ′ 2 ∧ q ′ 1 ∼ ′ q ′ 2 ).
(2) The states of the minimized automaton are equivalence classes of ∼ ′ and the transitions between these classes are labeled by (δ, Ī) where Ī is the join (convex hull) of all the intervals I i such that there are transition labeled by (δ, I i ) between elements of the corresponding classes (see Figure 7). 3 The result of minimization with respect to ∼ ′ appears in Figure 6-(b) and one can see that it gives a succinct over-approximation of the behavior of y 2 and z.

We have implemented the above mentioned technique. Our tool chain starts with a circuit description as Boolean equations with delays and generates from it automatically a network of interacting timed automata written in the IF format [START_REF] Bozga | IF-2.0: A Validation Environment for Component-Based Real-Time Systems[END_REF]. After generating the reachability graph with the interval labels we apply the Aldebaran tool set ( [START_REF] Bozga | Protocol Verification with the Aldebaran Toolset[END_REF]), slightly modified to implement minimization with respect to ∼ ′ to obtain the abstract model.

Experimental Results

We have conducted some preliminary experiments with our approach on some sample circuits that we have constructed. First, to demonstrate the semantic advantage of timed automata we analyzed the circuit of Figure 8 which has a false path. We use delays of [83,85] for all gates (except the inverters that have zero delay) and compare our results with static timing analysis which gives stabilization time of 7 × 85 = 594. Since our method works for the moment for one pair of input vectors, we repeat the analysis for all 12 pairs and obtain the results of Table 1. As one can see, the TA-based analysis discovers that the maximal stabilization time is only 6 × 85 = 510. The major set of experiments was conducted on circuits consisting of a sequential concatenation of an increasing number of copies of the circuit of Figure 1-(a) (the y 3 and y 4 of stage n are the x 1 and x 2 of stage n + 1). We assume that input x 1 may rise anywhere in [10, 35] and x 2 in [15,63]. In general, the complexity of the reachability graph is sensitive to the choice of delay bounds: for an interval [l, u], the larger is the ratio (u -l)/l, more "scenarios" are possible and transitions at "deep" gates can precede transitions in gates closer to the input. 4 Table 2 shows the performance of our technique (computation time and size of the reachability graph) as a function of the number of stages for three As the results show, currently the analysis of circuits with few dozens of gates for one pair of input vectors is feasible using our technique. This is a significant improvement for TA technology but still a small step toward industrialsize circuits. The current bottleneck is the memory consumption while generating the reachability graph and we believe the situation can be improved significantly if we modify the algorithm to take advantage of the acyclic nature of the automata.

There have been numerous publications on abstraction in general and abstraction of timed systems in particular, e.g. [AIKY95,WD94,B96,PCKP00], some based on relaxing the timing constraints and refining them successively if the abstract system cannot be verified. In [START_REF] Tasiran | Verifying Abstractions of Timed Systems[END_REF] an assume-guarantee framework is defined for timed automata, which is used later to verify a multi-stage asynchronous circuit [TB97] by using small abstractions for each stage. These abstractions are generated manually. The closest work to ours is [START_REF] Zheng | Modular Verification of Timed Circuits using Automatic Abstraction[END_REF] which uses timed Petri nets for describing circuits and their desired properties. To abstract a circuit they apply "safe transformations" that consist of hiding of internal actions and clocks, and possibly over-approximating the set of behaviors. This work does is not specialized to acyclic circuits and the formal properties of the abstraction (defined in terms of trace theory) seem to be more complicated. Other attempts to solve the maximal stabilization time using TA are reported in [TKB97,TKY + 98].

Due to space limitation we do not discuss here possible variation of the techniques such as different abstraction styles, nor other important ingredients of the methodology such as the partitioning strategy. The adaptation of the technique to cyclic circuits and to open systems in general is a very challenging goal whose achievement can have a big impact on the design of timed systems.

Fig. 1 .

 1 Fig. 1. (a) A Boolean circuit; (b) A timed Boolean circuit.

Fig. 2 .

 2 Fig. 2. An input signal α and few of the elements of D [2,3] (0, α).

Fig. 4 .

 4 Fig. 4. Projection on the absolute time introduces spurious runs.

Table 1 .

 1 Maximal stabilization time for all input pairs for the circuit of Figure8.

Fig. 5 .Fig. 6 .

 56 Fig. 5. (a) The reachability graph for the circuit of Figure 1-(b). The transition labels exc z, reg z, +z and -z correspond, respectively, to excitation, regret, rising and falling of the variable z. (b) The corresponding one-clock automaton after hiding internal transitions. The label +z[20,30] means that z may change from 0 to 1 anytime inside the interval [20, 30].

Fig. 7 .

 7 Fig. 7. Minimization by joining intervals.

Fig. 8 .

 8 Fig. 8. A circuit with a false path.

Table 2 .

 2 choices of gate delay intervals [1, 2], [10, 12] and [100, 102]. All the experiments were stopped upon memory overflow (1GB). For the [100, 102] interval we were able to analyze up to 22 stages (88 gates). Testing our technique with varying delay bounds. The 'states' column indicates the number of symbolic states in the model of stage n before the last minimization and the 'min' columns indicate the number of states after minimization. The 'time' column indicates the time for computing the abstraction of all stages up to n -1 and the reachability graph for stage n.

	[l, u]	[1, 2]		[10, 12]		[100, 102]
	no. states min time states min time states min	time
	1	71 4 0:01	65 3 0:01	65 3	0:01
	2 934 12 0:02	270 7 0:02	270 7	0:02
	3	--	-	2690 11 0:03	2690 11	0:04
	4			5397 23 0:05	4080 16	0:06
	5			217951 144 9:44 21498 30	0:12
	6			--	-50543 39	0:30
	7					73502 48	1:01
	8					95619 57	1:54
	9					117736 66	3:12
	10					139853 75	5:08
	11					161970 84	7:32
	12					184087 93 10:05
	13					206204 102 14:42
	14					228321 111 20:39
	15					250438 120 28:15
	16					272555 129 36:46
	17					117736 138 49:36
	18					316789 147 1:04:04
	19					338906 156 1:21:48
	20					361023 165 1:42:59
	21					383140 174 1:58:56
	22					405257 183 2:30:31
	23					--	-

To avoid over-formalization we do not define "open" interacting automata. Such definitions can be found in[START_REF] Maler | Timing Analysis of Asynchronous Circuits using Timed Automata[END_REF].

Another choice might be to join only intervals that have a non-empty intersection.

In fact, if we assume no lower-bound on the delay (the "up-bounded" model of[START_REF] Brzozowski | Asynchronous Circuits[END_REF]), events can happen in any order.

Acknowledgment: Many colleagues have contributed throughout the years to the work described in this paper. In particular, Sergio Yovine and Stavros Tripakis helped us a lot in understanding various aspects of the verification of timed automata. They also participated in previous efforts to apply it to circuit analysis. The development of the abstraction methodology was carried out at certain points in time by Nishant Sinha, Fadhel Graiet, Olfa Ben Sik Ali and Bara Diop. Comments and criticism made by Avi Efrati, Ken Stevens and anonymous referees improved the quality of the paper.

⋆ This work was partially supported by a grant from Intel and by the European Community Projects IST-2001-35304 AMETIST (Advanced Methods for Timed Systems), http://ametist.cs.utwente.nl


A E Jiménez-Cano

D Sanalitro
email: dario.sanalitro@laas.fr3juan.cortes@laas.fr

M Tognon
email: mtognon@ethz.ch

A Franchi
email: a.franchi@utwente.nl

J Cortés

Precise Cable-suspended Pick-and-Place with an Aerial Multi-robot System

Keywords: Aerial Robotics, Multi-robot systems, Shared Control, Novel construction techniques

This work introduces the G-Fly-Crane, a proof-of-concept aerial multi-robot system designed to demonstrate the advantage of using multiple aerial robots as a valuable tool for novel construction techniques, not requiring the use of heavy engines and costly infrastructures. We experimentally demonstrate its capability to perform pick-and-place and manipulation tasks in a construction scenario, with an increased payload capacity and dexterity compared to the single robot case. The system is composed of three aerial robots connected to a platform by three pairs of cables. The platform is equipped with a gripper, enabling the grasping of objects. The paper describes in detail the hardware and software architecture of our prototype and explains the implemented control methods. A shared control strategy incorporates the human operator in the control loop, thus increasing the overall system reliability when performing complex tasks. The paper also discusses the next steps required to bring this technology from indoor laboratory conditions to real-world applications.

INTRODUCTION

In construction, and more in general in the context of civil engineering, the manipulation of heavy and bulky loads is often required. In some cases, areas difficult to access make the use of ground cranes unfeasible, thus requiring the use of aerial cranes. Large helicopters, for example, are employed to transport and assemble elements for the construction of power transmission lines [START_REF] Tarapygin | Utilization of helicopters in power construction[END_REF]. Decommissioning of civil structures is also a fundamental and costly task in this field. Both assembly and decommissioning tasks can be accomplished using such heavy aerial machines. However, in addition to being extremely difficult to pilot, they could represent a danger for the construction workers. The use of Unmanned Aerial Vehicles (UAVs) for civil engineering applications, and in particular of multi-rotor platforms, would reduce the above-mentioned risk for the human workers. Moreover, UAVs working autonomously or semi-autonomously could potentially speed up the completion of construction/decommissioning tasks, thus reducing the associated costs. Hence, it is not surprising that the use of aerial robots for construction has gained popularity in the civil engineering domain. In this context, "drone compatible" bricks have recently been designed so that UAVs can rapidly construct real-scale structures, particularly masonry structures, without the use of concrete or other gluing materials [START_REF] Goessens | Feasibility study for dronebased masonry construction of real-scale structures[END_REF].

In the field of robotics, researchers have already investigated the problems of transporting objects and assembling small-scale structures. These problems have been firstly addressed by considering a single standard underactuated aerial vehicle equipped with a rigidly-attached gripper (mechanical or magnetic), allowing pick-and-place oper-Fig. 1: G-Fly-Crane and its main variables. Several types of grippers can be attached to the platform. In this work, we integrated a simple magnetic gripper.

ations [START_REF] Braithwaite | Tensile Web Construction and Perching with Nano Aerial Vehicles[END_REF][START_REF] Lindsey | Construction with quadrotor teams[END_REF][START_REF] Spurnỳ | Cooperative autonomous search, grasping, and delivering in a treasure hunt scenario by a team of unmanned aerial vehicles[END_REF]. However, having the load fixed on the aerial robot significantly reduces its agility. Moreover, the coupling of the translational and rotational dynamics makes pick-and-place operations more challenging. A possible solution is to transport the load by means of a cable attached to the robot, which makes it possible to keep the rotational dynamics of the vehicle decoupled from that of translation [START_REF] Foehn | Fast trajectory optimization for agile quadrotor maneuvers with a cable-suspended payload[END_REF][START_REF] Sreenath | Trajectory generation and control of a quadrotor with a cable-suspended load-a differentially-flat hybrid system[END_REF][START_REF] Tang | Aggressive flight with suspended payloads using vision-based control[END_REF]. Although the simplicity of such a system makes it suitable for transportation purposes, this solution is not optimal for construction uses. The limited payload of a single aerial robot and the inability to control the load attitude make the single-robot single-cable solution unsuitable for pick-and-place and complex manipulation tasks required in construction applications.

To the best of our knowledge, in this work, we introduce for the first time a real cable-suspended aerial multi-robot manipulator able to perform pick-and-place and manipulation operations in a construction/decommissioning scenario. The system developed for this proof of concept, called the G-Fly-Crane (Grasping Fly-Crane), is an extension of the Fly-Crane [START_REF] Manubens | Motion planning for 6-D manipulation with aerial towed-cable systems[END_REF]. Similarly to the Fly-Crane, the G-Fly-Crane consists of three quadrotors attached by pairs of cables to a rigid platform. However, the G-Fly-Crane is now equipped with a magnetic gripper (see Fig. 1) and incorporates a software architecture to deal with pick-and-place operations involving a shared control approach. The latter represents the main contribution of this work .

This new system is meant to solve the problems previously mentioned: it has an increased payload thanks to the use of multiple quadrotors, and can precisely control all the 6 degrees of freedom (d.o.f.) of the cable-suspended platform, and thus of the grasped object. We shall demon-strate through experiments, with real pick-and-place and manipulation operations, that these properties make the G-Fly-Crane particularly suited for construction and decommissioning applications. This proof of concept represents a preliminary, but fundamental, step in scaling up the system for real-world outdoor applications, with the inclusion of on-board sensors, more sophisticated grippers and larger aerial robots with increased payload capabilities.

Although the G-Fly-Crane could control its motion fully autonomously, the complexity of assembly operations in real construction sites, in addition to current safety standards and regulations, requires the possibility for a human operator to supervise and possibly intervene in the control of the system. For this purpose, we designed a shared control strategy, which allows a single user to control both the position and the attitude of the platform, without having to manage the simultaneous control of each robot. Such an assignment would be impossible for a single operator and would require a challenging coordination of multiple operators. Given the operator commands for the platform, the proposed control approach optimally resolves the system redundancy and computes the proper commands for each robot. The proposed control method relies on the kinematic controller presented in [START_REF] Petitti | Inertial estimation and energy-efficient control of a cable-suspended load with a team of UAVs[END_REF][START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF].

Other multi-robot systems and control strategies have been proposed for the cooperative transportation and manipulation of cable suspended loads. Detailed surveys have been presented in [START_REF] Bonyan Khamseh | Aerial manipulationa literature survey[END_REF][START_REF] Ollero | Past, present, and future of aerial robotic manipulators[END_REF]. Different strategies based on inverse dynamics, differential flatness, and formation control, have been proposed to control a team of aerial vehicles connected by cables to a point mass load for transportation purposes [START_REF] Bernard | Autonomous transportation and deployment with aerial robots for search and rescue missions[END_REF][START_REF] Erskine | Control and configuration planning of an aerial cable towed system[END_REF][START_REF] Klausen | Cooperative control for multirotors transporting an unknown suspended load under environmental disturbances[END_REF][START_REF] Marina | Flexible collaborative transportation by a team of rotorcraft[END_REF]. Aiming at more complex manipulation tasks, a two-robot system was considered proposing visionbased [START_REF] Gassner | Dynamic collaboration without communication: Vision-based cable-suspended load transport with two quadrotors[END_REF] and communication-less strategies [START_REF] Tagliabue | Collaborative transportation using MAVs via passive force control[END_REF][START_REF] Tognon | Aerial comanipulation with cables: The role of internal force for equilibria, stability, and passivity[END_REF] for the control of a cable-suspended bar. To control the full pose of a cable-suspended rigid load (requiring the ability to attain six-dimensional wrenches) at least three robots connected to three non-collinear points on the load by one cable each are needed [START_REF] Lee | Geometric control of quadrotor uavs transporting a cablesuspended rigid body[END_REF][START_REF] Sreenath | Dynamics, control and planning for cooperative manipulation of payloads suspended by cables from multiple quadrotor robots[END_REF]. However, to enhance the precision of the system by avoiding internal motions, a statically rigid [4] design is preferable. This can be obtained using six (or more) robots connected to six (or more) noncollinear points on the load by one cable each [START_REF] Masone | Cooperative transportation of a payload using quadrotors: A reconfigurable cable-driven parallel robot[END_REF]. The Fly-Crane [START_REF] Manubens | Motion planning for 6-D manipulation with aerial towed-cable systems[END_REF][START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF], and so the G-Fly-Crane (as well as similar designs [START_REF] Six | The kinematics, dynamics and control of a flying parallel robot with three quadrotors[END_REF]), use a simpler and more efficient statically rigid design involving only three robots, which is the minimum number to fully control the platform pose. This makes it preferable over the other statically-rigid solutions. Nevertheless, the current literature mainly focuses on demonstrating full-pose control capabilities without real interaction tasks. In this work, we go further by experimentally demonstrating the effectiveness of the G-Fly-Crane together with a shared control approach for pick-and-place and manipulation tasks in a construction scenario.

The paper is organized as follows. The G-Fly-Crane hardware and the scenario designed for the experiments are described in Section 2. Section 3 presents the software architecture implemented, and Section 4 describes the proposed control strategy. Experimental results of pickand-place operations with the G-Fly-Crane are shown in Section 5. Finally, Section 6 concludes the paper with final discussions and comments.

EXPERIMENTAL SETUP

Figure 2 shows the scenario designed to demonstrate pick-and-place and manipulation operations with the G-Fly-Crane. This scenario takes place inside an indoor arena equipped with a motion capture system and emulates the construction of a wall. Initially, the wall is incomplete. The two missing bricks, (red bricks in Fig. 2), necessary to complete the wall, are located in a random position on the ground. To increase the task difficulty, the wall was designed simulating an unevenness of the ground, presenting both flat and inclined surfaces. While one brick has to be placed on a flat spot, the other has to be positioned tilted, thus requiring 6D (position and orientation) manipulation capabilities. The bricks weight 0.5 [kg]. Besides, the G-Fly-Crane starts from a random location on the ground.

The G-Fly-Crane is made of three quadrotors (robots) and a platform. Figure 3 shows a graphical scheme of the hardware mounted on each quadrotor. Each robot is equipped with a Mikrokopter FlightCtrl V2.1 and four Mikrokopter ESC's BL-CTRL2.0c using a custom firmware allowing the controller to regulate the propeller speed in closed-loop [START_REF] Franchi | Adaptive closed-loop speed control of BLDC motors with applications to multi-rotor aerial vehicles[END_REF]. An Odroid XU4 is also mounted as on-board PC. The motors are Mikrokopter MK2832 motors with 10x4. 5 [inch] propellers. Each quadrotor weights 1.033 [kg] and measures 0.45 [m] diagonally. The available payload of each robot is 0.4 [kg] and, using a battery Six nylon cables are used to attach the robots to the platform, which is made of carbon fiber bars for a total weight of 0.350 [kg]. The platform was designed to dock different types of grippers. For the present work, the G-Fly-Crane is equipped with a gripper consisting of a matrix of four electromagnetic devices. This set-up, chosen after performing several tests, allows compensating undesirable torques while manipulating objects and, adds 0.1 [kg] to the total weight of the platform. The gripper control is implemented on an Arduino Board mounted on one of the robots and connected by USB to its onboard PC. A metal plate glued on top of the bricks allows their manipulation using this magnetic gripper.

Table 1 compares the weight and loading capability of a single quadrotor with respect to (w.r.t.) the one of the G-Fly-Crane system. The comparison is made fair by considering for the G-Fly-Crane system the extra weight introduced by the platform, and that the quadrotors always fly slightly tilted (on average χ = 10 [deg]). This is needed to keep the cables taut and to ensure the balance of forces needed for the 6D manipulation (see [START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF]). This causes a loss of efficiency of about 1 -cos(χ) these considerations, the G-Fly-Crane can manipulate loads that are almost 2.5 times heavier compared to what a single quadrotor unit, equipped with an identical gripper, can bear. Furthermore, the G-Fly-Crane has also the capability of manipulating the load in both position and orientation, and of keeping the rotating propellers farther from the environment during the pick-and-place operations. This configuration increases safety, reduces ground effects and creates less downwash on the environment thanks to the larger distance between the propellers and the ground.

SOFTWARE ARCHITECTURE

The software architecture for the G-Fly-Crane is implemented using GenoM3, an open-source (BSD-like license) tool developed at LAAS-CNRS to design real-time software architectures. GenoM3 allows the design and production of modules that encapsulate algorithms with inter-process communication, datapool capabilities with external access, and automatic telemetry generation. This framework has been tested in a variety of research robotic prototypes, and used in several European Space Agency (ESA) projects [START_REF] Ingrand | Decisional autonomy of planetary rovers[END_REF].

Figure 4 shows the architecture implemented. It is composed mostly by GenoM modules and divided into three layers, namely: (i) UAV layer, which includes the modules related with the flight controllers, state estimation and motor speed controller for each robot; (ii) shared control layer, which provides the connection between robots, platform and the user, implementing the controllers needed to operate the whole G-Fly-Crane system; and (iii) user layer, the inter-face with the human operator, which provides the visualization of the system status and the access to safety parameters, controller gains, logs, etc.

The UAV layer is composed of standard GenoM3 modules 1 running on the onboard PC of each quadrotor. On the other hand, the user layer is composed of a graphical interface and the joystick module running on the ground station PC. Both layers communicate thanks to the shared control layer, which runs also on the ground station PC. This layer implements the Fly-Crane Shared Control module (FSC) developed for this application. The FSC is based on the control strategy presented in the next section.

CONTROL

The G-Fly-Crane is designed to perform complex tasks related to structure construction. Because of the complexity of the involved problems, such as object localization and classification, obstacle avoidance and so on, real application scenarios and the corresponding regulations require the presence of humans to supervise or operate the robotic systems. However, when a system has a large number of degrees of freedom, such as the G-Fly-Crane, it is impossible to simultaneously command all of them for a single operator. Thus, we have developed the Fly-Crane Shared Control module (FSC) to assist the operator. Such a control strategy aims at allowing the operator to focus solely on the end-effector and the proper execution of the task, while the remaining degrees of freedom and the control of each robotic agent are automatically managed.

The control strategy, represented in Fig. 5, implements two flight modes:

-CRANE: the modality allows the operator to control the position and orientation of the platform/gripper. It is used during pick-and-place and manipulation operations; -MANUAL: this mode consists of two sub-modes. The first sub-mode maintains the formation shape and lets the human perform a rigid translation of the entire team; the second sub-mode allows the operator to control the position of a single robot while the other two remain stationary. This mode is used during take-off and landing operations and in case of emergency.

Depending on the active flight mode, the FSC module receives and interprets the commands from the human and computes the position and velocity references for the robots, which are sent to the corresponding position controllers.

Modeling

To present the derivation of the FSC, let us briefly introduce the kinematic model of the G-Fly-Crane (more details are available in [START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF]). The main variables are schematically represented in Fig. 1. We define two frames:

-an inertial frame F W = {O W , x W , y W , z W },
= [ φ θ ψ] ∈ R 3 .
The platform is attached by pairs of cables of the same length to three robots whose position w.r.t. F W is given by the vectors p Ri ∈ R 3 with i = 1, 2, 3, respectively. The configuration of each pair of cables w.r.t. F P is represented by the angle α i ∈ R between the plane {x P , y P } and the plane shaped by the cables attached to robot i. 2 The use of a minimal representation like Euler angles is justified by the fact that the platform will never operate at pitching angles close to π/2. Therefore any representation singularity problem is not pertinent here.

The system configuration is then entirely described by the variable q = [p P η P α ] ∈ C ⊂ R 9 , where α = [α 1 α 2 α 3 ] T ∈ R 3 . We also collect the position of all robots in the vector p R = [p R1 p R2 p R3 ] which can be written as function of q [20], p R = f (q). Differentiating such a kinematic relation, we obtain the differential kinematic model:

v R := ṗR = ∂f (q)
∂q q = J (q) q,

where

, v R = [v R1 v R2 v R3 ]
, and q = [v P η P α ] ∈ R 9 . The Jacobian matrix J (q) ∈ R 9×9 is a square invertible matrix in C, except for some singular configurations investigated in [START_REF] Six | The kinematics, dynamics and control of a flying parallel robot with three quadrotors[END_REF].

CRANE flight mode

In this mode, the human can directly specify the endeffector pose, i.e., the position and orientation of the platform, p P and η P , respectively. To do so, we rely on the inverse kinematics controller presented in [START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF]. Given a desired system trajectory in the configuration space q d (t) = [ p d P (t) η d P (t) α d (t) ] , the reference velocities of the aerial vehicles are computed as v R = J (q) K q e q + qd ,

where 3 K q = k q I 9 ∈ R 9×9 >0 is a positive definite matrix and e q = q d -q. In [START_REF] Sanalitro | Full-pose manipulation control of a cable-suspended load with multiple UAVs under uncertainties[END_REF], we showed how to optimally compute k q to guarantee the system stability and the minimum H ∞ gain under parametric uncertainties. We then integrate v R to obtain the position reference p R . Both are sent to the geometric position controller [START_REF] Lee | Geometric tracking control of a quadrotor UAV on SE(3)[END_REF] running on each aerial vehicle, which implements a PID action based on the position error. We remark that in the considered context, the integral term is sufficient to compensate external disturbances and changes of the platform mass during pick-and-place operations. The desired system trajectory in the configuration space q d (t) is defined in a shared way between the human operator and an online local planner. The human specifies the platform position and attitude, while the local planner resolves the redundancy of the system. Thus, we map the joystick commands available to the operator into desired translational and rotational velocities of the platform, i.e., v d P and ηd P , respectively (see Sec. 4.4). Such quantities are then integrated (starting from the initial configuration) to obtain the desired position and rotation of the platform, i.e., p d P and η d P , respectively. The final quantities to accomplish the desired configuration trajectory, namely α d , are computed through an online local planner [START_REF] Petitti | Inertial estimation and energy-efficient control of a cable-suspended load with a team of UAVs[END_REF] as the result of a optimization problem:

α d = arg min α s.t. 0<αi< π 2 λ 1 J 1 (q) -λ 2 J 2 (q), (3)
3 I n ∈ R n×n is the identity matrix of dimension n.

where J 1 (q), J 2 (q) are two configuration-dependent cost functions and λ 1 , λ 2 ∈ R >0 are the corresponding weights.

In particular,

J 1 (q) = |f R1 -f R2 |+|f R1 -f R3 |+|f R3 -f R2 | (4) J 2 (q) = det(J (q)J (q) ), (5)
where f Ri ∈ R ≥0 is the thrust intensity delivered by each robot, which depend on the configuration and the known parameters of the system. Solving (3), the local planner computes the cables angles that balance the effort among all the robots (J 1 (q)) while maximizing the manipulability index 4 (J 2 (q)). The time derivative of α d can be computed numerically or simply assumed zero in the domain of interest. Notice that the distribution of efforts among robots, or in other words the value of J 1 (q), also depends on the position of CoM of the platform. In this first proof of concept, we designed the platform and the gripping mechanism such that the position of the platform CoM can be assumed constant during the pick-and-place operations.

MANUAL flight mode

This flight mode allows the operator to command the position of each aerial vehicle. As for the CRANE flight mode, the operator uses the joystick to send the desired velocities, which are then integrated to obtain the desired position. In this specific flight mode, the operator can choose between two sub-modes:

-MANUAL-1: all robots are moved as a rigid body such that v R1 = v R2 = v R3 = v d R , -MANUAL-2: only one robot is displaced in an independent way while the others maintain their position. In particular v Ri = v d R for a single i ∈ {1, 2, 3}, while v Rj = 0 for the remaining j ∈ {1, 2, 3}/{i}.

Notice that v d R = [v d Rx v d Ry v d Rz ] ∈ R 3
is the velocity command provided by the user.

The MANUAL-1 modality is mostly used for take-off and landing operations while MANUAL-2 in case of emergency. For example, if one the robots face a technical issue, the operator can relocate the others until they reach a safe location, assuming the load and/or the platform can be detached.

Human interface

The operator interacts with the robotic system through a standard joystick (see Fig. 4). In this section, we describe how the human commands are mapped into directives for 4 Notice that other measures of the manipulability can be used.

B v d P x v d P y φd θd 0 k x a 3 k y a 4 0 0 1 0 0 k φ a 3 k θ Table 2:
Commanded horizontal velocity and roll and pitch rates according to the value of B. k x , k y , k φ , k θ ∈ R are scaling gains.

the system according to the flight mode. To keep the human interface as similar as possible to the one used by multi-rotor pilots, we employed a similar joystick set up by providing two analogue sticks with two axes each, (a 1 , a 2 , a 3 , a 4 ) with a i ∈ [-1, 1], and several buttons.

CRANE flight mode:

In this mode, commands available to the human are mapped into desired linear and rotational velocities of the platform. Mimicking a standard multi-rotor control interface, two axes of one stick are mapped into yaw rate and linear velocity along z W :

ψd = k ψ a 1 , v P z = k z a 2 , (6)
where k ψ , k z ∈ R are scaling gains. Through axes a 1 and a 2 , the human operator can control the yaw angle and the altitude of the platform, respectively. To control the planar position and attitude along the remaining x P and y P axes, we use the same joystick axes, a 3 and a 4 , according to the status of a button, called B ∈ (0, 1). The mapping between the axes a 3 , a 4 and the desired system commands depending on the value of B are described in Tab. 2.

In practice, with the joystick axes a 3 and a 4 , the operator controls the platform attitude when the button B is pressed, and the platform position otherwise. Separating the control of the horizontal position and the attitude, as well as making the human interface similar to the one used for standard multi-rotors, make the G-Fly-Crane operations simpler and more intuitive.

MANUAL flight mode: In this mode, the mapping is similar to the previous mode, with the difference that the axis a 1 and the B button are ignored. In particular:

v d Rx = k x a 3 , v d Ry = k y a 4 , v d Rz = k z a 2 . (7)
Additional joystick buttons are used to choose the mode MANUAL-1 or MANUAL-2 and select the robot to be moved.

RESULTS

To demonstrate and validate the pick-and-place and manipulation capabilities of the G-Fly-Crane, we present experiments performed in the indoor scenario shown in Section 2.

A video showing the experiments is provided as supplementary material. In these experiments, the G-Fly-Crane is operated by a single person via a Logitech F310 gamepad, supported by the presented shared control strategy.

In the first experiment, the task is to complete a wall by placing two missing bricks. Figure 6 shows the different phases of the experiment:

1. Take-off : the user commands the vertical position of the robots in MANUAL-1 mode to lift the platform; 2. Pick first brick: the user commands the position of the platform in CRANE mode (B = 0) placing the platform on top of the brick and triggering the magnetic gripper; 3-4) Place first brick: using the same mode, the user commands the G-Fly-Crane to lift the brick, bring it to the target position, and place it on the incomplete wall; 5-8) Pick and place second brick: operations 3 and 4 are repeated to pick and place the second brick. However, the second brick has to be placed on the tilted wall. Therefore, when the platform is above the target position and before placing the brick, the operator commands the orientation of the platform (B = 1) until the brick is parallel to the wall slope; 9-10) Landing: finally, the G-Fly-Crane is driven to its initial position for landing.

Considering the more challenging pick-and-place operation of the second brick, Fig. 7 Notice that during the pick operation (phase 5), the position error along z W increases. This is because the user commands a desired platform position such that the magnetic gripper slightly goes inside the brick. Thanks to the natural compliance of the cables, this does not constitute a problem, and the brick can be gently attached once perfectly in contact with the gripping system. During the lift of the brick (phase 6), again, the position error along z W increases. This is due to the additional mass of the brick that is compensated by the integral action of the robots' position controller only after a few seconds (around t = 225 [s]) when the error goes back to zero.

The tracking of the desired trajectory for the attitude and α angles, respectively, are shown in Fig. 8. The noise in these measurements is due to the internal forces acting through the cables and other disturbances generated by communication delays, wind turbulence caused by the rotors of each aerial vehicle, etc. Let us define the position, attitude and cable angles errors as e p P = p d P -p P , e η P = η d P -η P and e α = α d -α, respectively. In Tab. 3 we report the mean and variance of the norm of the previous errors.

Figure 8 also shows the extra thrust for each robot, fRi , defined as the total thrust minus the amount of thrust needed by each robot to hover the platform without the load. Thanks to the local optimization of the cables angles, α, the thrust values of each robot remain always close to each other indicating a good balance of the effort among the quadrotors. This keeps the energy consumption similar for each of the robots.

At t = 270 [s], during phase 8, the brick is located over the wall surface (see video provided as supplementary ma- terial). Interestingly, as shown in Fig. 8c, the extra thrust for each quadrotor has a sudden decrease because the weight of the brick is temporarily compensated by the contact with the wall.

Additionally, we performed a second experiment further showing the manipulation capabilities of the G-Fly-Crane (see video provided as supplementary material). This test emulates the decommissioning of a structure where bricks must be removed from the inclined wall. As in the previous experiment, the G-Fly-Crane takes off and the operator places it on top of the target brick. Before descending to perform the pick, the pilot provides the commands to adjust the platform orientation according to the inclination of the brick. The brick can be then removed from the wall safely and accurately, thanks to the dexterity provided by the G-Fly-Crane.

DISCUSSION AND CONCLUSIONS

For the first time, we have experimentally demonstrated the physical interaction capabilities of an aerial multi-robot system for complex pick-and-place and manipulation operations in the context of construction scenarios. We have proposed a shared control strategy that allows a single person to operate such a complex robotic system. As a result, the human has complete control over the manipulation operations rather than having to separately provide commands to each quadrotor. The obtained results successfully represent the first proof of concept for the potential use of the G-Fly-Crane in construction. However, we recognize that the presented experimental validation was conducted in an indoor laboratory setting and that there are several challenges ahead in bringing this technology to real-world applications. One of these challenges is the localization of the system (the robots and the platform). In general, a motion capture system (such as the one used in this work) is unsuitable for large outdoor workspaces, and the accuracy provided by a global positioning system is insufficient to perform precise manipulation tasks. A possible solution is the combination of a global positioning system with cameras and other onboard sensors, using VIO algorithms and sensor fusion techniques. Another key consideration is robustness, which is especially significant when dealing with diverse atmospheric conditions or when the system has to interact with the environment. Therefore, in addition to a more robust mechatronic design, robust control approaches will be necessary to enhance the proposed shared control strategy. Moreover, the optimization of the redundancy, i.e., the cables angles, is only local in our current implementation. A global planning method considering internal and external constraints (e.g., obstacles) in addition to an optimal balance of the payload among the robots would be relevant tools to increase robustness and to ease the system's operations. Furthermore, in the future, when new regulations will allow for manipulation activities to be performed with such complex aerial robotic systems, fully autonomous execution of the tasks could be envisioned. For this first proof of concept, we deliberately simplified the grasping problem by considering a magnetic gripper that can easily grasp and release bricks in our demonstration scenario. Nevertheless, the application of the G-Fly-Crane technology to real-world construction tasks will require the integration of more sophisticated automated grasping methods and grippers suited to the shape and material of the manipulated parts. The mentioned improvements are considered as future works.

Fig. 2 :

 2 Fig. 2: Scenario designed for the experiments.

Fig. 3 :

 3 Fig. 3: G-Fly-Crane hardware scheme.

Fig. 4 :

 4 Fig. 4: Software Architecture.

Fig. 5 :

 5 Fig. 5: Control strategy implemented for the G-Fly-Crane.

  shows the position tracking of the G-Fly-Crane during the phases 5, 6, 7, and 8 starting at time t 5 = 175 [s], t 6 = 195 [s], t 7 = 205 [s], t 8 = 250 [s], respectively. The second brick is successfully placed on the wall at time t = 285 [s].

Fig. 6 :

 6 Fig. 6: Snapshots of the wall construction task with the G-Fly-Crane, illustrating different phases.

Fig. 7 :

 7 Fig. 7: Position Tracking for the operation of pick-and-place for the second brick.

Fig. 8 :

 8 Fig. 8: Tracking of the desired trajectory for the attitude and α angles and comparing with the extra thrust.

Table 1 :

 1

	1.5%. Following

Weights and payload capability (in kg) of the G-Fly-Crane compared to a single quadrotor unit.

  where O W is its origin and {x W , y W , z W } are its unit axes; a body frame F P = {O P , x P , y P , z P } rigidly attached to the platform. F P is placed such that O P coincides with the Center of Mass (CoM) of the platform.The configuration of the platform is given by p P = [p P x p P y p P z ] ∈ R 3 , describing the position of O P w.r.t. F W , and by the Euler angles 2 η P = [φ θ ψ] ∈ R 3 describing the orientation of F P w.r.t. F W . The corresponding time derivatives are: its linear velocity v P = [v P x v P y v P z ] = dp P /dt ∈ R 3 w.r.t. F W , and the Euler angles rates ηP

Table 3 :

 3 e p P [m] e η P [Deg] e α [Deg] Mean and variance of the norm of the position, attitude and cable angles errors

	Mean	0.026	0.2	0.7
	Variance	0.078	1.2	2.8

Acknowledgements The authors would like to thank Quentin Sable from the University of Twente for his contribution to the experimental platform and Anthony Mallet from LAAS-CNRS who collaborated to develop the software architecture.

This work has been partially funded by the Région Occitanie under contract 2018 003431 -ESR PREMAT-000160, by the ANR project ANR-17-CE33-0007 'MuRoPhen', and by the European Commission project H2020 AERIAL-CORE (EC 871479)

Fundings

This work has been partially funded by the Région Occitanie under contract 2018 003431 -ESR PREMAT-000160, by the ANR project ANR-17-CE33-0007 'MuRoPhen', and by the European Commission project H2020 AERIAL-CORE (EC 871479).

Availability of data and material

Not applicable.

Code availability

Not applicable.

Conflict of interest

The authors declare that they have no conflict of interest.

Authors' contributions

A.E.J.C. and D.S.: Original draft preparation, hardware/software development and experimental tests. M.T.: writing -review and editing. A.F. and J.C.: Supervision, funding acquisition, writing -review and editing.

Ethics approval

Not applicable.

Consent to participate

Not applicable.

Consent for publication

Not applicable.