Julius Ibenthal

Luc Meyer

Hélène Piet-Lahanier

Michel Kieffer
email: michel.kieffer@l2s.centralesupelec.fr

Localization of partially hidden targets using a fleet of UAVs via robust bounded-error estimation

This paper addresses the cooperative search of static ground targets by a group of Unmanned Aerial Vehicles (UAVs) over some region of interest. The search strategy dependents on the availability and accuracy of the information collected. When a target is detected, a probabilistic description of the measurement noise is usually considered, as well as probabilities of false alarm and non-detection, which may prove difficult to characterize a priori.

An alternative modeling is introduced here. The ability to detect and identify a target depends deterministically on the point of view from which the target is observed. Introducing the notion of detectability sets for targets, we propose a robust distributed set-membership estimator to provide set estimates of target locations. The obtained set estimates are guaranteed to contain all target locations when the search is completed. The target search is formulated as a multi-agent cooperative control problem where the control inputs are obtained using a Model Predictive Control (MPC) approach minimizing a measure of the set estimates representing the detection performance. The proposed set estimator and cooperative control scheme are distributed, i.e., accounting only for information from neighbors within communication range. The effectiveness of the proposed algorithm is illustrated by simulation.

I. INTRODUCTION

The Cooperative Search and Track (CST) of multiple targets can be addressed by the deployment of multiple UAVs. CST consists of a continuous search for targets while keeping track of already detected targets in some Region of Interest (RoI). The number of targets is unknown and may vary as targets may enter or leave the RoI during the search. This application has received increased interest in the last decades due to the recent advances in the development of UAVs. Various approaches have been developed for that purpose see, e.g., [START_REF] Robin | Multi-robot target detection and tracking: taxonomy and survey[END_REF] and [START_REF] Khan | Cooperative robots to observe moving targets[END_REF] and the references therein. Most of the techniques of the state-of-the-art rely on cooperative strategies and on distributed estimation of the target locations. The displacement strategies alternate between the search for new targets and track of already identified ones. The evolution of the UAVs depends on the collected information quality, which then impacts the estimation uncertainty of target locations. Various approaches for displacement strategy have been suggested including search trajectory optimization accounting for kinematic constraints as in [START_REF] Raap | Trajectory optimization under kinematical constraints for moving target search[END_REF] or game-theoretic techniques as in [START_REF] Li | A potential game approach to multiple UAV cooperative search and surveillance[END_REF].

One of the major issue of CST is the limited ability of the UAVs to detect a target located in its field of view and to discriminate targets from potential decoys. Limited discrimination and detection abilities are usually modeled with a probability of false alarm and a probability of nondetection. For a given seeker, these probabilities are either chosen as constant over the RoI as in [START_REF] Li | A potential game approach to multiple UAV cooperative search and surveillance[END_REF], dependent on the detection range, or measurement signal-to-noise ratio as in [START_REF] Hu | Multi-agent cooperative target search[END_REF]. These probabilities play an important role for the search performance, however, it is difficult to provide reasonable values. Moreover, such probabilistic representation poorly accounts for the influence of the local environment on the ability to detect targets or to misinterpret a decoy as a target, which is usually deterministic. If, e.g., a target is partially hidden by some obstacle, the ability of the UAV to detect it is severely decreased. A decoy located in a clustered environment can be more easily mistaken with a real target. These examples illustrate that the ability of detecting a target may be more efficiently modeled by accounting for the point of view from which the target is observed. Observation quality depending on the point-of-view has been suggested in [START_REF] Pan | Directional monitoring of multiple moving targets by multiple unmanned aerial vehicles[END_REF]. In [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF], the ability to discriminate between a decoy and a real target depends on the observation point of view. The limitation of the UAV's field of view in presence of known obstacles has been considered in [START_REF] Reboul | Cooperative guidance of a fleet of UAVs for multi-target discovery and tracking in presence of obstacles using a set membership approach[END_REF]. Set-membership estimation techniques [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF] are then well-suited to account for deterministic detection and discrimination issues. In [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF], one can conclude that an observed subset is free from any target, when no target is detected.

In this paper, we consider a fleet of UAVs equipped with optical seekers able to detect and localize targets. Targets are assumed to be static. Due to the existence of unknown obstacles, a target may be masked and hence not detected even if it belongs to the observed subset of the optical seeker. We assume that the ability to detect and identify a target depends deterministically on the point of view from which it is observed: a target can be detected when observed from some conic detectability set with its apex at the targets location. Additionally, the target has to be located within the field of view of the seeker. As a consequence, a target, even located in the field of view of a seeker may be missed when not observed from a point of view belonging to the detectability set. This issue is difficult to address with the set-membership estimation technique presented in [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF]. Here, when no target is detected, the observed subset cannot be immediately declared free from any target. Such conclusion is only possible when the same area of the RoI is observed from a sufficient variety of points of view.

To address this problem, L non-overlapping conic observation subsets of points of view are considered for each location of the RoI. We assume that one of these conic subsets is included in the detectability set associated to each location of the RoI. Under this hypothesis, it is possible to guarantee that a location is free from a target when observed from L different points of view, each belonging to a different observation subset.

Based on this hypothesis, we propose a distributed setmembership estimator able to provide set estimates guaranteed to contain all target locations within the RoI. Each UAV runs a set estimator that evaluates target locations accounting for its own measurements and for information received during communications with other UAVs. Contrary to [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF], the proposed approach is able to guarantee the detection of hidden targets. The control input for each UAV is designed using a distributed MPC approach compliant with the set-membership estimator. The resulting control inputs account for the point of view of future observations, extending [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF], [START_REF] Reboul | Cooperative guidance of a fleet of UAVs for multi-target discovery and tracking in presence of obstacles using a set membership approach[END_REF], and aims at minimizing a measure of the estimation uncertainty. The controller accounts for the impact of future measurements on the set estimates and infers future information communicated by neighbors.

The paper is organized as follows. The context and hypotheses are recalled in Section II. The target detectability set is introduced in Section III. Sections IV and V present respectively the distributed estimator and the design of the associated cooperative control strategy. Section VI introduces simulation examples illustrating the performance obtained with a fleet of UAVs. Section VII concludes the paper.

II. HYPOTHESES AND PROBLEM FORMULATION

We consider the search for an unknown number N t of static targets by a fleet of N u UAVs within a bounded RoI X 0 ⊂ R 3 . A frame (O, F) is attached to X 0 where O is the origin. One assumes that a unique identifier j = 1, . . . , N t can be associated to each target. The RoI contains an a priori unknown number of static obstacles.

A. UAV states and target locations

Time is discretized with a constant period T . At time instant t = kT , the state vector

x u i,k ∈ R nu of UAV i ∈ N u = {1, . . . , N u } evolves according to x u i,k+1 = f u k x u i,k , u i,k , (1)
where u i,k is the control input for UAV i, to be chosen in a set U of admissible control inputs. The position of UAV i is denoted as x u i,k = p(x u i,k ), where p (x) represents the three first components of x ∈ R nu .

The RoI X 0 is assumed to be compact and connected. Due to the presence of obstacles, targets may only be located in a subset X T ⊂ X 0 of the RoI. The set X T is not known a priori. The location of target j is denoted x t j ∈ X T , j ∈ {1, . . . , N t }.

B. Detectability set

The obstacles within the RoI may partly hide some points x ∈ X T . This leads to restricted detectability of targets located at these points. To represent this restricted detectability, for possible target locations x ∈ X T , one introduces the detectability set D (x) ⊂ R 3 , as the subset of locations x ′ ∈ R 3 from where a target located at x can be detected. D (x) depends on the environment (obstacles) and is unknown to the UAVs. D (x) does not depend on the characteristics of the seeker, which are taken into account in Section II-C.

We assume that for all x = (x 1 , x 2 , x 3 ) T ∈ X T , there exists a set of n (x)

⩾ 3 unit vectors v 1 (x) ∈ R 3 , . . . , v n(x) (x) ∈ R 3 defining a cone of non-zero volume with apex x D (x) = {x + a 1 v 1 (x) + • • • + a n(x) v n(x) (x) | a i ∈ R + , i = 1, . . . , n (x)} such that D (x) ⊂ D (x).
This assumption facilitates the characterization of the detectability set. Fig. 1 illustrates the detectability set D (x) ⊂ R 3 (red and gray) for a point x ∈ X T (blue) and a simple box-shaped obstacle (dark gray).

C. Measurements

Each UAV i is equipped with a sensor to observe a subset F i (x u i ) (Field of View, FoV) of the RoI X T , when its state is x u i . The subset F i (x u i ) is assumed to be described by a nonzero volume cone characterized by a set of n i unit vectors v F i,m (x u i ), m = 1, . . . , n i , depending on the UAV state

x u i F i (x u i ) = {x u i + a 1 v F i,1 (x u i ) + • • • + a ni v F i,ni (x u i ) | a m ∈ R + , m = 1, . . . , n i }. (2)
The mean of the vectors

v F i,1 (x u i ) , . . . , v F i,ni (x u i ) v F i (x u i ) = m=1,...,ni v F i,m (x u i ) / m=1,...,ni v F i,m (x u i ) (3)
represents the FoV orientation of UAV i with state x u i . Let D i,k be the set of indexes of targets detected by UAV i at time k. Assuming the state of UAV i is

x u i,k , one has j ∈ D i,k ⇐⇒ x u i,k ∈ D x t j and x t j ∈ F i x u i,k . (4)
For each detected target j ∈ D i,k , a noisy observation of the location x t j is obtained as

y i,j,k = h i x u i,k , x t j + w i,j,k , (5)
where h i is the observation function of UAV i and w i,j,k represents the measurement noise, bounded in some box [w i,j,k ]. Usually the box size varies according to environmental conditions and is unknown [START_REF] Li | A potential game approach to multiple UAV cooperative search and surveillance[END_REF], [START_REF] Cortes | Coverage control for mobile sensing networks[END_REF]. One assumes, that a known box [w i ] such that [w i,j,k ] ⊂ [w i ] can be obtained, considering, e.g., worst-case measurement conditions.

D. Communications

The communication topology is described by the undirected graph G k = (N u , E k ) at time k. The set of edges E k ⊂ N u ×N u represents connections between the UAVs. We assume that UAVs i and i ′ are able to communicate at time k if their positions x u i,k and x u i ′ ,k satisfy some communication condition c, i.e.,

c x u i,k , x u i ′ ,k ⩾ 0 ⇐⇒ (i, i ′ ) ∈ E k . (6)
The communication condition c may account for the distance between two UAVs, or for the presence of an obstacle between them. The set of neighbors of UAV i is denoted as

N i,k = {i ′ ∈ N u | (i, i ′ ) ∈ E k , i ̸ = i ′ }.

E. Problem formulation

For each UAV i ∈ N u , our aim is, at each time k, to build a list X i,k of set estimates X i,j,k , j ∈ L i,k of target locations, where L i,k is the set of already detected target indexes. The set estimates have to be consistent with the observations collected by UAV i and with the information collected and transmitted by its neighbors. Moreover, each UAV has be able to determine when all targets in the RoI have been detected. This requires to be able to prove, from a finite number of observations, that there is no target at a location x of the RoI.

III. PROPOSED SOLUTION

Consider a generic UAV with state x u . According to the target detection model (4), even if x t j corresponding to the jth target is such that x t j ∈ F i (x u ), the target is not detected by the UAV when x u / ∈ D x t j . To be detected, a target located at x t j has to be observed from a location x ′ ∈ D x t j . The difficulty is that D x t j is not known a priori. Conversely, to prove that there is no target located at x ∈ X T , since D (x) is unknown a priori, several conditions have to be satisfied. First, a sufficient variety of observation locations x ′ ℓ has to be considered to be sure that at least one of these observation locations is such that x ′ ℓ ∈ D (x) . Second, for each of these locations, the state x ′ ℓ of a UAV located at x ′ ℓ has to be such that

x ′ ℓ = p (x ′ ℓ ) and x ∈ F i (x ′ ℓ ) .
Third, for all observations F i (x ′ ℓ ), one has to conclude that there is no target at x. The fact that the cone D (x) ⊂ D (x) is of non-zero volume ensures that only a finite number of observation locations is required to state the absence of target at some x ∈ X 0 .

Section III-A introduces L conic observation subsets for all x ∈ X T . Choosing L sufficiently large ensures that at least one of these subsets is included in D (x) for all x ∈ X T . It is then possible to state that there is no target at x provided that x has been observed from a location in

v 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 9 O Fig. 2. Partition in 8 cones of the set of points of view for O with x 3 ⩾ 0; the cone C 1 (O) is shown in blue; its n 1 = 4 vertices are v 1 , v 2 , v 6 , and v 5 .
each of the L conic observation subsets and that no target has been detected. Section III-B introduces L subsets of locations where no target has been detected. To account for the points of view from which the locations have been observed, each of these subsets is associated to one of the L conic observation subsets. Finally, the estimation uncertainty is defined in Section III-C, which states the target detection problem more formally.

A. Conic observation subsets

Consider L non-zero volume cones C ℓ (O) ∈ R 3 , ℓ = 1, . . . , L with apex O. Each cone C ℓ (O) is defined by a set of n ℓ unit-norm vectors v ℓ,1 ∈ R 3 , . . . , v ℓ,n ℓ ∈ R 3 , such that C ℓ (O) = {a 1 v ℓ,1 + • • • + a n ℓ v ℓ,n ℓ | a m ∈ R + , m = 1, . . . , n ℓ }. (7)
Fig. 2 illustrates 8 cones with their apex O realizing a partition of the half space with x 3 ⩾ 0. The 8 cones form a partition of the set of points of view with x 3 ⩾ 0 from which O may be observed.

Considering the cones C ℓ (O), ℓ = 1, . . . , L, one introduces for all x ∈ R 3 the translated cones C ℓ (x), ℓ = 1, . . . , L of apex x such that

x ′ ∈ C ℓ (x) ⇔ x ′ -x ∈ C ℓ (O) . (8)
The mean of the vectors

v ℓ,1 , . . . , v ℓ,n ℓ v c ℓ = m=1,...,n ℓ v ℓ,m / m=1,...,n ℓ v ℓ,m , (9)
represents the orientation of the cones C ℓ (O) and C ℓ (x).

We assume that the cones

C 1 (x) , . . . , C L (x) satisfy ∀x ∈ X T , ∃ℓ ∈ {1, . . . , L} , C ℓ (x) ⊂ D (x) , (10)
i.e., for every point x ∈ X T there exists a cone C ℓ (x) included in D (x), and thus also included in D (x). Consider the state x u i,k of UAV i at time k and its FoV F i (x u i,k ). The observed locations x ∈ F i (x u i,k ) do not necessarily belong to the same conic observation subset. Thus, one introduces the following subsets of the FoV

F i (x u i,k ) F i,ℓ x u i,k = x ∈ F i x u i,k | x u i,k ∈ C ℓ (x) , (11)
ℓ ∈ {1, . . . , L}. F i,ℓ (x u i,k ) is the subset of locations x ∈ F i (x u i,k ) which are observed from a point of view belonging to C ℓ (x).

Processing the information available from F i (x u i,k ) at time k, one gets the set of detected targets D i,k and the measurements y i,j,k , j ∈ D i,k . Using (4) and ( 5), one can state that no target is detected at position x when observed from a location

x u i,k = p(x u i,k ) belonging to C ℓ (x) either when D i,k = ∅ or when ∀j ∈ D i,k , h i (x u i,k , x) / ∈ [y i,j,k ], where [y i,j,k ] = y i,j,k -[w i ].
The latter condition indicates that the candidate target location x is not consistent with the measurement y i,j,k the measurement function h i , and the noise bound [w i ]. From these conditions, we can define

c ℓ x u i,k , x =              1 if x ∈ F i,ℓ x u i,k and D i,k = ∅, 1 if x ∈ F i,ℓ x u i,k and ∀j ∈ D i,k , h i x u i,k , x / ∈ [y i,j,k ] 0 else. When c ℓ (x u i,k , x) = 1, no target is detected at position x when observed from a location x u i,k = p(x u i,k ) belonging to C ℓ (x).
Theorem 1. Consider some x ∈ X T with detectability set D (x), L conic observations subsets C ℓ (x), and a set of

L UAV states x u ℓ , ℓ = 1, . . . , L, such that x u ℓ = p (x u ℓ ) ∈ C ℓ (x) and x ∈ F ℓ (x u ℓ ). Assuming that C ℓ (x), ℓ = 1, . . . , L satisfy (10), if c ℓ (x u ℓ , x) = 1
for all ℓ = 1, . . . , L, then there is no target at x. Proof: Assume that target j is located at x, i.e., x t j = x, and that c ℓ (x u ℓ , x) = 1 for all ℓ = 1, . . . , L. Since ∃ℓ such that C ℓ (x) ⊂ D (x), we have x u ℓ ∈ C ℓ (x) ⊂ D (x). Moreover, as x ∈ F ℓ (x u ℓ ), according (4), target j should have been detected, i.e., j ∈ D ℓ and a measurement y ℓ,j = h ℓ x u ℓ , x t j + w ℓ,j , with w ℓ,j ∈ [w ℓ ] should be available. Thus h ℓ (x u ℓ,k , x) ∈ [y ℓ,j,k ] and c ℓ (x u ℓ,k , x) = 0, which contradicts the initial assumptions.

The observations obtained from UAVs with states x u ℓ , ℓ = 1, . . . , L, could be taken by different UAVs and at different time instants.

B. Estimates

Let I i,k be the set gathering the information available to UAV i up to time k. From I i,k , UAV i is able to evaluate L i,k , the list of indices of targets already detected or which presence has been signaled by an other UAV of the fleet to UAV i. I i,k is used to evaluate a list of target set estimates X i,k = {X i,j,k } j∈L i,k such that x t j ∈ X i,j,k , for all j ∈ L i,k . X i,j,k ⊂ X 0 contains all possible values of the state of the detected target j that are consistent with the information available to UAV i at time k.

Additionally, UAV i maintains the subsets X i,ℓ,k ⊂ X 0 , ℓ = 1, . . . , L, of potential target locations x that have not been observed from a point of view belonging to the cone C ℓ (x) up to time k. The subsets X i,ℓ,k , ℓ = 1, . . . , L, are collected in the list X i,k = X i,ℓ,k ℓ=1,...,L . Moreover

X i,k = ℓ∈{1,...,L} X i,ℓ,k , (12)
is the set of potential target locations x which have not been observed from at least one point of view in each cone C ℓ (x), ℓ = 1, . . . , L.

C. Estimation uncertainty

At time k, the target estimation uncertainty for UAV i is evaluated as

Φ X i,k , X i,k = j∈L i,k ϕ (X i,j,k ) + 1 L L ℓ=1 ϕ X i,ℓ,k , (13)
where ϕ (X) represents a measure of X. Φ X i,k , X i,k accounts for the set estimates X i,j,k , j ∈ L i,k of detected targets and for the sets X i,ℓ,k , ℓ = 1, . . . , L, which have to be further explored. The average estimation uncertainty among all UAVs at time k is

Φ k = 1 N u Nu i=1 Φ X i,k , X i,k . (14)
As in [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF], the UAVs have to evaluate a sequence of control inputs that minimizes the estimation uncertainty Φ k . The main difficulty compared to [START_REF] Ibenthal | Boundederror target localization and tracking in presence of decoys using a fleet of UAVs[END_REF] lies in the fact that L sets X i,ℓ,k are taken into account, each associated with a specific cone C ℓ , ℓ = 1, . . . , L. This requires first to be able to determine the evolution of the various set estimates managed by the UAVs when new measurements are available.

IV. EVOLUTION OF THE SET ESTIMATES

UAV i manages the sets L i,k , X i,k , and X i,k introduced in Section III-B. These sets are initialized at time k = 0 as L i,0 = ∅, X i,0 = ∅, X i,ℓ,0 = X 0 , ℓ = 1, ..., L, for i = 1, . . . , N u . In what follows, their evolutions are described when new measurements are taken into account, either coming from UAV i or from its neighbors.

A. Accounting for measurements

Assume that at time k+1, after processing the information in F i (x u i,k+1 ), UAV i obtains a measurement y i,j,k+1 for each detected target j ∈ D i,k+1 . Consequently, the information gathered in I i,k+1|k+1 is

I i,k+1|k+1 = I i,k ∪ D i,k+1 , {y i,j,k+1 } j∈D i,k+1 . (15)
Using the new information in I i,k+1|k+1 and F i (x u i,k+1 ), three cases have to be considered for updating the sets X i,k , and X i,k .

When j ∈ L i,k and j ∈ D i,k+1 , a known target j is observed again. The new measurement y i,j,k+1 has to be consistent with the previous target set estimate X i,j,k . Consequently,

X i,j,k+1|k+1 = x ∈ X i,j,k | h i x u i,k+1 , x ∈ [y i,j,k ] . When j / ∈ L i,k and j ∈ D i,k+1
, a new target is detected. The target location belongs to one of the non-empty subsets F i,ℓ (x u i,k ) of the FoV F i (x u i,k ), and to one of the corresponding set X i,ℓ,k . Since determining which of these sets contains the target is difficult, one gets

X i,j,k+1|k+1 = ℓ=1,...,L F i,ℓ (x u i,k )̸ =∅ x ∈ X i,ℓ,k | h i x u i,k+1 , x ∈ [y i,j,k ] .
When j ∈ L i,k and j / ∈ D i,k+1 , a previously detected and known target j is not detected at time instant k + 1 and X i,j,k+1|k+1 = X i,j,k .

(16) Once all information in F i,ℓ (x u i,k+1 ) has been exploited, one may update the sets X i,ℓ,k , ℓ = 1, . . . , L by removing the locations x ∈ F i,ℓ (x u i,k+1 ) observed from

x u i,k+1 ∈ C ℓ (x), thus X i,ℓ,k+1|k+1 = X i,ℓ,k \F i,ℓ x u i,k+1 . (17)
According to [START_REF] Tokekar | Multi-target visual tracking with aerial robots[END_REF], one gets

X i,k+1|k+1 = ℓ∈{1,...,L} X i,ℓ,k+1|k+1 . (18)
Fig. 3 shows different sets X i,ℓ,k at time k considering four cones C ℓ (O), ℓ ∈ {1, ..., 4}. The newly explored space X i,ℓ,k ∩ F i,ℓ (x u i,k+1 ) at time k is shown in orange for each UAV. The vertices of the associated cone C ℓ (x) are highlighted in red. Fig. 3 (right) shows the resulting set X i,k . One observes that the orientation of the FoV of each UAV determines the index ℓ of the set X i,ℓ,k which size will be the most significantly reduced using the measurement at time k + 1. For example, the FoV of the red UAV has an orientation opposite to the one of the cone C 2 , leading to a significant reduction of X i,2,k . The reduction of the size of X i,4,k is null, due to the relatively close orientation of the FoV of the red UAV and that of the cone C 4 . This property will have to be taken into account in the design of the control inputs of the UAVs.

B. Accounting for communication

UAV i receives the information I n,k+1|k+1 from each UAV n ∈ N i,k . Using that information, UAV i first updates the list of known targets as L i,k+1 = n∈N i,k ∪{i} L n,k+1|k+1 . Then for each j ∈ L i,k+1 , the corrected target set estimate X i,j,k+1 is evaluated as

X i,j,k+1 = n∈N i,k ∪{i} | j∈L n,k+1|k+1 X n,j,k+1|k+1 , (19)
since X i,j,k+1 has to be consistent with all observations from the UAVs which have detected target j.

If, for some ℓ ∈ {1, ..., L}, UAV i or one of its neighbors have observed x ∈ X 0 from a location x ′ ∈ C ℓ (x), it is not necessary to observe x again from a location in C ℓ (x). A target has either been detected, leading to one of the sets X i,j,k+1 , j ∈ L n,k+1|k+1 , or no target has been detected. In both cases, x can be removed from X i,ℓ,k+1|k+1 . Consequently, for each ℓ ∈ {1, ..., L},

X i,ℓ,k+1 = n∈N i,k ∪{i} X n,ℓ,k+1|k+1 . (20)
Finally, one has

X i,k+1 = L ℓ=1 X i,ℓ,k+1 . V. COOPERATIVE CONTROL DESIGN
The aim of the control input design is to compute, in a distributed way, a sequence of control inputs u i,k:k+h-1 = (u i,k , . . . , u i,k+h-1 ) for each UAV i ∈ {1, . . . , N u } that minimizes the predicted estimation uncertainty ( 14)

Φ k+h = 1 N u Nu i=1 Φ X i,k+h , X i,k+h , (21)
at time k + h where h ⩾ 1 is the prediction horizon and X i,k+h and X i,k+h depend on u i,k:k+h-1 . The setmembership estimators described in Section IV are combined with a Model Predictive Control approach [START_REF] Morari | Model predictive control: past, present and future[END_REF], [START_REF] Camacho | Model predictive control[END_REF], [START_REF] Tokekar | Multi-target visual tracking with aerial robots[END_REF], [START_REF] Farmani | Tracking multiple mobile targets using cooperative unmanned aerial vehicles[END_REF], to get a Set-Membership Model Predictive Control (SM-MPC) design of the control inputs.

We assume that the UAVs compute their control inputs sequentially. Once UAV i has evaluated u i,k:k+h-1 , it is broadcast to its neighbors, which then compute their sequence of control inputs accounting for those evaluated by their neighbors. The order in which the evaluations are done may clearly be optimized, but is left for future research.

A. Control input design

One assumes that UAV i has to evaluate u i,k:k+h-1 accounting for the sequences of control inputs already evaluated by a subset N C i,k ⊂ N i,k of its neighbors. Thus, one assumes that all UAVs n ∈ N C i,k have broadcasted their sequence u n,k:k+h-1 as well as their states x u n,k , at time k. Consequently, at time k, UAV i has access to L i,k , X i,k , X i,k , u n,k:k+h-1 , and x u n,k , n ∈ N C i,k . When UAV i has to evaluate the sequence of control inputs minimizing Φ k+h , it has in fact to evaluate

u i,k:k+h-1 = arg min u i,k:k+h-1 Φ X P i,k+h , X P i,k+h . ( 22
)
Since one is unable to predict whether new targets will be detected between time k + 1 and k + h, the predicted values of L i,k+κ are set to L P i,k+κ = L i,k , κ = 1, . . . , h. Moreover, in the considered SM-MPC approach, the impact of the control input sequence on X i,j,k+κ , κ = 1, . . . , h is difficult to evaluate and is thus neglected. This approximation is reasonable, since most of the time, the contribution of X i,k+h to Φ k+h is negligible compared to that of X i,k+h . We thus focus on the evolution of the components of X i,k+κ , κ = 1, . . . , h from control input sequences provided by UAV i and its neighbors n ∈ N C i,k . Consequently, (22) can be simplified to

u i,k:k+h-1 = arg min u i,k:k+h-1 L ℓ=1 ϕ X P i,ℓ,k+h . (23)
We determine now the impact of the control input sequences of UAV i and of its neighbors n ∈ N C i,k on the predicted sets X P i,ℓ,k+h . For all n ∈ N C i,k , UAV i predicts recursively x u,P n,k+1 , ..., x u,P n,k+h from x u n,k and u n,k:k+h-1 using (1). From x u,P n,k+1 , UAV i derives F n,ℓ (x u,P n,k+1 ) as in

 C 1 C 2 C 3 C 4  C 1 C 2 C 3 C 4  C 1 C 2 C 3 C 4  C 1 C 2 C 3 C 4 X i,1,k X i,2,k X i,3,k X i,4,k X i,k
Fig. 3. Evolution of X i,ℓ,k , ℓ ∈ {1, ..., 4} when considering 3 UAVs; Each column shows a set X i,ℓ,k in yellow and the corresponding cone C ℓ (O), ℓ ∈ {1, ..., 4}; The last column represents X i,k ; The orange area indicates the set X i,ℓ,k ∩ F i,ℓ (x u i,k+1 ) at time k. [START_REF] Camacho | Model predictive control[END_REF]. Each UAV n ∈ N C i,k will contribute to the reduction of X i,ℓ,k as follows

X P i,ℓ,k+ = X i,ℓ,k \ n∈N C i,k F n,ℓ x u,P n,k+1 , (24)
ℓ ∈ {1, ..., L}. The previous approach can be applied iteratively on X P i,ℓ,k+ to evaluate the impact of u n,k+κ-1 , n ∈ N C i,k and κ = 1, . . . , h, as

X P i,ℓ,k+κ+ = X P i,ℓ,k+κ-1+ \ n∈N C i,k F n,ℓ x u,P n,k+κ .
Finally, one may write

X P i,ℓ,k+h+ = X i,ℓ,k \ h κ=1 n∈N C i,k
F n,ℓ x u,P n,k+κ .

In the same way, and for any control input sequence u i,k:k+h-1 , UAV i can predict recursively x u,P i,k+1 , ..., x u,P i,k+h from x u i,k and can derive F i,ℓ (x u,P i,k+κ ), κ = 1, ..., h, which contributes to the reduction of X P i,ℓ,k+h+ to get X P i,ℓ,k+h

X P i,ℓ,k+h = X P i,ℓ,k+h+ \ h κ=1 F i,ℓ x u,P i,k+κ .
Hence, (23) can finally be written as

u i,k:k+h-1 = arg min u i,k:k+h-1 L ℓ=1 ϕ X P i,ℓ,k+h = arg min u i,k:k+h-1 L ℓ=1 ϕ X P i,ℓ,k+h+ \ h κ=1 F i,ℓ x u,P i,k+κ (25)
= arg max

u i,k:k+h-1 L ℓ=1 ϕ X P i,ℓ,k+h+ ∩ h κ=1 F i,ℓ x u,P i,k+κ . (26)
The resulting sequence of control inputs leads to the maximum average reduction of the size of X P i,ℓ,k+h+ .

B. Practical issues

In practice, obtaining u i,k:k+h-1 from (26), when h is limited may prove to be inefficient, especially when

X P i,ℓ,k+h+ ∩ ( h κ=1 F i,ℓ (x u,P i,k+κ )) = ∅ for all ℓ = 1, . . . , L,
whatever the sequence of control inputs. Such situation may occur, e.g., when a UAV reaches the boundary of X 0 .

To address this issue, one observes that the orientation of F i (x u i,k+1 ) and of the cone C ℓ are quite different when

v F i (x u i,k+1 ) T v c ℓ < 0. In that case, ϕ(F i,ℓ (x u i,k+1
)) is likely to be large and the UAV may be able to get observations able to reduce X i,ℓ,k , provided that X i,ℓ,k ∩F i,ℓ (x u i,k+1 ) ̸ = ∅. This is, for example, the case with the red UAV in Fig. 3

for C 2 and X i,2,k . When v F i (x u i,k+1 ) T v c ℓ > 0, the orientation of F i (x u i,k+1 ) is close to that of the cone C ℓ . In that case, ϕ(F i,ℓ (x u i,k+1
)) is likely to be small. The observation performed at time k + 1 is likely to leave X i,ℓ,k unchanged. This is the case with the red UAV in Fig. 3 for C 4 and X i,4,k .

In order to get an efficient reduction of X i,ℓ,k or X P i,ℓ,k+h+ , it may thus be of interest to control UAV i in such a way that v F i (x u i,k+κ ) T v c ℓ is as negative as possible for some ℓ ∈ {1, . . . , L}. This is nevertheless not sufficient, since one should have, e.g., X i,ℓ,k ∩ F i,ℓ (x u i,k+1 ) ̸ = ∅. Hence, when X P i,ℓ,k+h+ ∩ ( h κ=1 F i,ℓ (x u,P i,k+κ )) = ∅ for all ℓ = 1, . . . , L whatever the input sequences, while X P i,ℓ,k+h+ ̸ = ∅ for some ℓ, it may be of interest to find a control input that drives UAV i to a point of X P i,ℓ,k+h+ which may lead to future reductions via observations such that v

F i (x u i ) T v c ℓ < 0. The point x * i,ℓ,k+h = arg max x∈X P i,ℓ,k+h+ x T v c ℓ ,
is a good candidate for that purpose as it is the farthest point of X P i,ℓ,k+h+ from the origin along v c ℓ . For each cone C ℓ , ℓ = 1, . . . , L, one may then introduce the cost function

J ℓ (u i,k , . . . , u i,k+h-1 ) = ϕ X P i,ℓ,k+h+ ∩ h κ=1 F i,ℓ x u,P i,k+κ -α 1 x * i,ℓ,k+h -x u,P i,k+h + λv F i x u,P i,k+h -α 2 v F i x u,P i,k+h T v c ℓ . (27)
In the right-hand side of ( 27), the first term represents the reduction of the measure of X P i,ℓ,k+h+ that may be obtained from successive measurements, as in (26). The second term accounts for the Euclidian distance between x * i,ℓ,k+h and a point x u,P i,k+h + λv F i (x u,P i,k+h ) of the FoV of UAV i when it is located at x u,P i,k+h . The parameter λ can be tuned to select specific locations in the FoV. Choosing λ > 0 proves to be more efficient in practice. The last term favors v F i (x u,P i,k+h ) T v c ℓ < 0 as J ℓ is maximized. The tuning parameters α 1 and α 2 adjust the weight of each term in the cost function. The second and third terms of the right-hand side of (27) are most often negligible compared to the first term, as long as it is non-zero.

The control input for UAV i is obtained as the first element of the control sequence

u i,k:k+h-1 = arg max u i,k:k+h-1 max ℓ (J ℓ (u i,k , . . . , u i,k+h-1 )) .
The cone C ℓ for which the reduction of the size of X i,ℓ,k is maximum is selected. This avoids changing too frequently the orientation of the UAVs. The control inputs belong to the set U of admissible control inputs. In practice, to lighten computations, U is partitioned into discrete subsets U 0 , . . . , U h-1 .

VI. SIMULATIONS

In the proposed simulation, X 0 is taken as The location of the j-th target is then x t j = (x j,1 , x j,2 , 0) T , j = 1, . . . , N t . The locations are generated by distributing the targets uniformly inside X T and discarding locations inside of or too far from the obstacles.

The state of UAV i at time k consists of its location evolves according to

x u i,k = (x u i,k,1 , x u i,k,2 , x u i,k,3 ) ⊤ ,
          x u i,k+1,1
x u i,k+1,2

x u i,k+1,3

x u i,k+1,4

x u i,k+1,5

x u i,k+1,6

x u i,k+1,7           =              x u i,k,1 + T d cos x u i,k,4 cos x u i,k,5 V u x u i,k,2 + T d cos x u i,k,4 sin x u i,k,5 V u x u i,k,3 + T d sin x u i,k,4 V u x u i,k,4 x u i,k,5 + T d x t i,k,6 x u i,k,6 + T d x t i,k,7 u i,k              . (28)
The altitude x u i,k,3 = 100 m, the flight path angle x u i,k,4 = 0, and the speed module V u = 16.6 m/s are assumed constant.

The UAVs are equipped with identical optical seekers able to observe a subset of the RoI. The angle between the longitudinal axis of the UAV and the orientation of the seeker is 3π/8. The apertures of the seekers are equal to π/4 in azimuth and in elevation. A set of 8 observation cones is chosen as in Fig. 2. The vertices are at π/4, 3π/4, 5π/4, and 7π/4 for the azimuth and at 0, π/3, and π for the elevation. Consequently, The communication condition ( 6) is defined as

v 1 = (1/ √ 2, -1/ √ 2, 0) T , v 2 = (1/(2 √ 2), -1/(2 √ 2), √ 3
c x u i,k , x u i ′ ,k = d c -x u i,k -x u i ′ ,k
, where d c = 200 m is the maximum communication range and x u i,kx u i ′ ,k is the distance between the locations of the UAVs i and i ′ . Some results accounting for the impact of the choice of d c are presented in [START_REF] Ibenthal | Bounded-error target localization and tracking using a fleet of UAVs[END_REF]. The prediction horizon for the SM-MPC is h = 2. The control input is computed with a period T c = 0.5 s and is equal to the communication period. The parameters of (27) are α 1 = 0.002, α 2 = 1, and λ = 100. The exact values for α 1 and α 2 are less important for the proper functionality of the control, nevertheless, their ratio should give more importance to the value of ϕ in the criterion of (27) and thus to the reduction of the sets.

The simulations have been carried out in Matlab where Matlab's polyshapes are used to represent sets. Polyshapes simplify the handling of sets in R 2 regarding Boolean and geometrical operations. In higher-dimensions, subpavings, i.e., unions of non-overlapping interval vectors [START_REF] Kieffer | Guaranteed recursive non-linear state bounding using interval analysis[END_REF] can be used.

Fig. 4 is an example of the resulting simulation with 7 obstacles (gray boxes), 10 targets (black circles) and 4 UAVs. The plot on the left illustrates the simulation scenario and the occluded area (darker gray) for the red UAV. This information is not accessible for the UAVs. The plot on the right shows the set estimates X i,j,k (green) and X i,k (yellow) known to the red UAV.

The results in Fig. 5 are obtained for 30 independent simulations with the same number of obstacles, targets, and UAVs. The initial locations of the obstacles, targets, and UAVs are changed in each simulation. Fig. 5 shows the evolution with time of ϕ Mean value of ϕ (X k ), ϕ X ℓ * ,k , and ϕ X ℓ * * ,k for 30 simulations; 10 targets, 7 obstacles, and 4 UAVs; Mean values (line) and root-mean-square error (area) of ϕ X k . and into ℓ * = {5, 6, 7, 8}, cones with elevation bounds [π/3, π/2]. In Fig. 5, one can see that the evolution of ϕ(X ℓ,k ) is similar for all ℓ ∈ {1, ..., L}. One observes a slightly faster decrease of ϕ(X ℓ * * ,k ) for indexes ℓ * * of cones with elevation in [0, π/3] compared to ϕ(X ℓ * ,k ) for indexes ℓ * of cones with elevation in [π/3, π/2]. This is caused by the elevation of the FoV that leads to larger intersection with X i,ℓℓ * * ,k for cones with low value of elevation.

X k = Nu i=1 ϕ X i,k /N u and of the contribution to Φ k of ϕ X ℓ,k = Nu i=1 ϕ X i,ℓ,k /N u , ℓ ∈ {1, ..., L}, and ϕ (X k ) = Nu i=1 ϕ( X i,j,k ∈X i,k X i,j,k )/ N u .
Regarding the target set estimate, one observes that ϕ(X k ) remains small compared to ϕ(X ℓ,k ) and that the assumptions considered in Section V-A are reasonable.

The reduction of ϕ(X k ) appears only after an area has been explored from locations belonging to the L different observation cones since X i,k = ℓ∈{1,...,L} X i,ℓ,k .

The average computation time for a simulated time horizon of 600 s was 2121 s on a Windows 10 machine with an Intel Xeon W-2123 processor. Some video sequences associated to the simulations are at https://drive.google.com/drive/folders/ 1djk7qQJCGBYPKVwD8nAey7C9f4bbQ65I?usp= sharing Note that in the video sequences some UAVs are leaving the RoI during the search. This allows UAVs to turn and better reduce the size of the unexplored sets.

VII. CONCLUSIONS

In this paper, we proposed and illustrated via simulations a new algorithm for cooperative search of ground targets by a fleet of UAVs. The approach accounts for potential occultation of targets by unknown obstacles. This makes it necessary to collect observations from a variety of points of view to assess the presence or absence of targets.

Instead of considering a of non-detection that could be difficult to tailor to the various relative positions of the targets and obstacles, we introduce the notion of detectability set for a target, used in a robust distributed set-membership estimator able to provide set estimates of the target locations. The resulting set estimates are guaranteed to contain the locations of all the targets within the search area. The search strategy needs to be adapted to provide trajectories that sweep the different points of view required to conclude to the effective presence or absence of a target at a given location. A multi-agent cooperative control problem has then to be solved. A model predictive control approach determines the UAVs control inputs that minimize a measure of the set estimates accounting for the detection performance. The distributed algorithms take advantage of communications of data among neighboring UAVs within communication range. The performance of the resulting method is illustrated on simulations.

Future work includes accounting for varying sensor and communication parameters. Further developments are also foreseen to take into account moving targets.

Fig. 1 .

 1 Fig. 1. Detectability set D (x) ⊂ R 3 (red and gray) for a point x ∈ X T (blue) and a simple box shaped obstacle (dark gray).

  [0, 300] × [0, 300] × [0, 100] m 3 . Obstacles, consist in boxes, randomly placed with a minimal distance of 20 m from each other. They are uniformly scattered over [0, 300] × [0, 300] m 2 . Their lengths and widths are uniformly distributed in [40 m, 60 m] × [40 m, 60 m]. Their heights are uniformly distributed in [80 m, 90 m]. Only static targets at an altitude 0 m are considered in the RoI X T = [0, 300] × [0, 300] × [0, 0].

Fig. 4 .

 4 Fig. 4. Map of the environment with obstacles, targets, and UAVs (left side). Estimates X 1,2,191 (yellow) and X 191 (green) of UAV 1 (red) (right side)

/ 2 )

 2 T ,. . . and v 9 = (0, 0, 1) T . A noisy measurement of the first two components of x j is obtained when target j is detected by UAV i at time k. The noise is bounded in [-5 m, 5 m].

  Fig. 5.Mean value of ϕ (X k ), ϕ X ℓ * ,k , and ϕ X ℓ * * ,k for 30 simulations; 10 targets, 7 obstacles, and 4 UAVs; Mean values (line) and root-mean-square error (area) of ϕ X k .

Acknowledgments

The authors gratefully thank the french Agence de l'Innovation de Défense (AID) for its fundings.