Near-Optimal Multi-Agent Learning for Safe Coverage Control
Authors: Manish Prajapat
Matteo Turchetta
Melanie Zeilinger
Andreas Krause
Venue: NeurIPS 2022 Accept (2022)
Keywords: Multi-agent learning
Submodular optimization
Safety
Bayesian optimization
Coverage control

Abstract: In multi-agent coverage control problems, agents navigate their environment to reach locations that maximize the coverage of some density. In practice, the density is rarely known $\textit{a priori}$, further complicating the original NP-hard problem. Moreover, in many applications, agents cannot visit arbitrary locations due to $\textit{a priori}$ unknown safety constraints. In this paper, we aim to efficiently learn the density to approximately solve the coverage problem while preserving the agents' safety. We first propose a conditionally linear submodular coverage function that facilitates theoretical analysis. Utilizing this structure, we develop MacOpt, a novel algorithm that efficiently trades off the exploration-exploitation dilemma due to partial observability, and show that it achieves sublinear regret. Next, we extend results on single-agent safe exploration to our multi-agent setting and propose SafeMac for safe coverage and exploration. We analyze SafeMac and give first of its kind results: near optimal coverage in finite time while provably guaranteeing safety. We extensively evaluate our algorithms on synthetic and real problems, including a bio-diversity monitoring task under safety constraints, where SafeMac outperforms competing methods.

Near-Optimal Multi-Agent Learning for Safe Coverage Control
Manish Prajapat
Matteo Turchetta
Melanie N. Zeilinger! ETH Zurich mzeilinger@ethz.co
ETH Zurich
ETH Zurich matteotušinf. ethz.
manishp0ai. wtwz.
Andreas Krause' ETH Zurich krausea@ethz.co ch
Abstract
multi-agent coverage control problems, agents navigate their environment reach locations that maximize the coverage of some density. In practice, the density is rarely known a priori, further complicating the original NP-hard problem. Moreover, in many applications, agents cannot visit arbitrary locations due to a priori unknown safety constraints. In this paper, we aim to efficiently learn the density approximately solve the coverage problem while preserving the agents' safety. We first propose a conditionally linear submodular coverage function that facilitates theoretical analysis. Utilizing this structure, develop MACOrT, novel algorithm that efficiently trades off the exploration-exploiaaiio dilemma due to partial observability, and show that it achieves sublinear regret. Next, we extend results on single-agent safe exploration to our multi-agent setting and propose SAFEMAC for safe coverage and exploration. We analyze SAFEMAC and give first of its kind results: near optimal coverage in finite time while provably guaranteeing safety. We extensively evaluate our algorithms on synthetic and real problems, including a biodiversity monitoring task under safety constraints, where SAFEMAC outperforms competing methods.
Introduction
In multi-agent coverage control (MAC) problems, multiple agents coordinate to maximize coverage over some spatially distributed events. Their applications abound, from collaborative mapping [i],
environmental monitoring [2], inspection robotics [3] to sensor networks 4 In addition, the coverage formulation can address challenges in cooperative multi-agent RL by providing high-level goals. In these applications, agents often encounter safety constraints that may lead to critical accidents when ignored, e.g., obstacles or extreme weather conditions (9] [0]
e.g., exploration (7).
Deploying coverage control solutions in the real world presents many challenges: (i) for given density of relevant events, this is an NP hard problem [II]; (ii) such density is rarely known in practice [2) and must be learned from data, which presents a complex active learning problem as the quantity measure (the density) differs from the agents often operate under safery-critte criiiicl conditions, [0), that may be unknown a priori. This requires cautious exploration of the environment prevent catastrophic outcomes. While prior work addresses subsets of these challenges (see Section we are not aware of methods that address them
want to optimize (its coverage); (iii)
jointly.
Joint supervision. Code available at attuttpss///etthbb..mmmm/maaatst paa.sseearaaaa/aaaaaaa
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

(a) Safe initialization
(b) Coverage maximization
(c) Safe coverage maximization
The three drones aim to maximize the gorilla nests' coverage (grey shaded circle) while avoiding unsafe extreme weather zones (red cross pattern). The contours (yellow is high and purple is low) represent the density of gorilla nests (blue dots). The density and the constraint unknown. a) To be safe, drones apply conservative strategy and do not explore, which results in poor coverage. In b), the drones maximize coverage but get destroyed in extreme weather. c) shows SAFEMAC solution. The drones strike a balance, trading off between learning the density and the constraints, and thus achieve near-optimal coverage while always being safe.
Figure 1:
a-prior
This work makes the following contributions toward efficiently solving safe coverage control with a-priori unknown objectives and constraints. Firstly, we model this multi-agen learning task as conditionally linear coverage function. We use the monotonocity and the submodularity of this function to propose MACOPT, a new algorithm for the unconstrained setting that enjoys sublinear cumulative regret and efficiently recommends near-optimal solution. Secondly, 12]. an algorithm for single agent safe exploration, to the multi-agent case. Combining our extension of GoOSE with MACOPT, we propose SAFEMAC, novel algorithm for safe multi-agent coverage control. We analyze and show it attains a near-optimal solution in a finite time. Finally, we demon- strate our algorithms on a synthetic and real world applications: safe biodiversity monitoring and obstacle avoidance. We show SAFEMAC finds better solutions than algorithms that do not actively explore the feasible region and is more sample efficient than competing near-optimal safe algorithms.
extend GOOSE
2 Problem Statement
We present the safety-con cidettconsttained multi-agen coverage control problem (Fig. that we aim to solve.
Coverage control. Coverage control models situations where we want deploy a swarm of dynamic agents to maximize the coverage of a quantity of interest, see Fig. [ Formally, given a finite set of possible locations V. the goal of coverage control is to maximize a function 2 + R that assigns to each subset, X C V, the corresponding coverage value. For N agents, the resulting problem arg maxx: X|SN F(X). The discrete domain V can be represented by graph, where nodes represent locations the domain, and an edge connects node v to v' the agent can go from v'. This corresponds to deterministic MDP where locations are states and edges represent transitions.
Sensing region. Depending the application, we may use different definitions of F. Here, model cases where agent i at location x² covers a limited sensing region around it, D³. While D can be any connected subset of V. in practice it is often ball centered x². Given function p: V > IR. denoting the density of a quantity of interest at each u E V, our coverage objective is
F(X:
Σ Σ
P(u)/IV).
x'EX VED
where == D' DI: i-11-11 indicates the elements in V covered by agent but not agents 1: i Di:i-1= and [V] denotes cardinality of the domain V.
Safety. In many real-world problems, agents cannot go to arbitrary locations due to safety concerns. To model this, we introduce constraint function q: V + R and we consider safe all locations e satisfying q(v)= 2 O. Such constraint restricts the space of possible solutions of our problem in two ways. First, prevents agents from monitoring from unsafe locations. Second, depending on its dynamics, agent i may be unable to safely reach disconnected safe area starting from z/ see
'Continuous domains can be handled via discretization

---

Appendix A.3
We denote with R., (fz))) ) the largest safely reachable region starting from zi and with B a collection of batches of agents such that all agents in the same batch B share the same safely reachable set, Vi,j E B: R,, (f*a)) n R., (f=²)) )) & W, see Appendix A for formal definitions. Based on this, we define the safely reachable control problem
F(XB; p. R.,, (x,)))
max X (XP)
BEB
where XØ= = (=r are the starting locations of all agents in B and R., (X8) = UieB R., ((=6)) indicates the largest safely reachable region from any point z/ for all in B (since the agents have the same dynamics, R. (X,") = R., (f*a1), vi E B). In safety- monitoring, there may be unreachable safe regions. However, since agents should be able to collect measurements if required, we focus only on covering the safely reachable region.
Unknown density and constraint. In practice, the density p and the constraint q are often unknown a priori. However, the agents can iteratively obtain noisy measurements of their values at target locations. We consider synchronous measurements, i.e., we wait until all agents have collected the desired measurement for the current iteration before moving the next one. Here, we focus on the high-level problem of choosing informative locations, rather than the design of low-level motion planning Therefore, our goal is to find an approximate solution to the problem in Eq. (2) preserving safety throughout exploration, i.e., at every location visited by the agents, while taking as few measurements as possible in case the dynamics of the agents are deterministic and known as in
3 Background
This section presents foundational ideas that our method builds on. In particular, it discusses (i) monotone submodular functions and (ii) previous work on single-agent safe exploration.
Submodularity. Optimizing a function defined over the power set of a finite domain, V, scales com- binatorially with the size of V in general. In special cases, we exploit the structure of the objective to find approximate solutions efficiently. Monotone submodular functions are one example of this.
A set function F 2 R is monotone if for all A C B C V we have F(A) < F(B). It is submodular VA C B C V, E V \ B, we have, F(AU U {w}) F(A) 2 U(BU(M) (w)) F(B), In coverage control, this means adding to A yields at least much increase in coverage than adding v to B. if A C B. Crucially, [13] guarantees that the greedy algorithm produces a solution within factor of (1 1/e) of the optimal solution for problems of the type arg max XISN F(X; P, V), when F is monotone and submodular. In practice, the greedy algorithm often outperforms this worst-case guarantee [4] and guaranteeing a solution better than (1 - 1/e) factor is NP hard [5).
The coverage function in Eq. ① is a conditionally linear, monotone and submodular function (proof in Appendix B). which lets us use the results above to design our algorithm for safe coverage control.
Goal-oriented safe exploration. GOOSE 12 is a single-agent safe exploration algorithm that extends unconstrained methods to safety-criticas cases. Concretely, it maintains under- and over- approximations of the feasible set, called pessimistic and optimistic safe sets. It preserves safety by re- stricting the agent to the pessimistic safe set. It efficiently explores the objective by letting the original unconstrained algorithm recommend locations within the optimistic safe set. If such recommendations are provably safe, the agent evaluates the objective there. Otherwise, evaluates the constraint at a se- quence of safe locations to prove that such recommendation is either safe, which allows it to evaluate the objective, or unsafe, which triggers the unconstrained algorithm to provide new recommendation.
Assumptions. To guarantee safety, GOOSE makes two main assumptions. First, it assumes there is an initial set of safe locations, Xo, from where the agent can start exploring. Second, it assumes the constraint is sufficiently well-behaved, so that we can use data to infer the safety of unvisited locations. Formally, it assumes the domain V is endowed with a positive definite kernel (."),), and that the constraint's norm in the associated Reproducing Kernel Hilbert Space [6] is bounded, llgll> < B, This lets us Gaussian Processes (GPs) [17] construct probabiiiyy confidence intervals for We specify the GP prior over through a mean function, which we assume to be
2 Agents can use their transition graph to find a path between two goals. In continuous domain, the path can be tracked with controller (e.g., MPC)
3

---

zero everywhere w.l.o.g., (lb) 0, Ve E V, and kernel function, k, that captures the covariance between different locations. If we have access to measurements, at V {ur perturbed by i.i.d. Gaussian noise, yr {g(()) + 7y 1 with v ~ (N,, we can compute the posterior mean and covariance over the constraint at unseen locations v, v' as pr(p) = (v) 'r and (u, o') = k(v, x') k (KT + + where kr(v) = [k(11, v), k(vT,)) v) Kr is the positive definite kernel matrix ("),,,")), and / E RTTT denotes the identity matrix.
In this work, we make the same assumptions about the safe seed and the regularity of q and p.
Approximations of the feasible set. Based on the GP posterior above, GOOSE builds monotonic con- fidence intervals for the constraint at each iteration & as (V(v) == max("" (0)_ (0) and u (w) = min (4[1("), (w), pi (v) + 3 - which contain the true constraint function for every v E V and 2 1, with high probability if 88 is selected as in [8] or Section 5 GoOSE uses these confidence intervals within set 5 C V together with the Lnp-Lipschitz continuity of g. to define operators that determine which locations are safe in plausible worst- and best-case scenarios,
(5) = (o E V, F E S: S: ([((=) L, (1, 2 0}:
(4) Notice that the pessimistic operator relies on the lower bound, 19 while the optimistic one on the upper bound, u². Moreover, the optimistic one uses margin Eg to exclude "barely" safe locations as the agent might get stuck learning about them. Finally, to disregard locations the agent could not safely reach or from where it could not safely return, GOOSE introduces the Re (-++) operator. Rergodii (S). S) indicates locations in S or locations in (S) reachable from S and from where the agent can return to S along a path contained in (S)). Combining Pe (S) and Rergodi GoOSE defines the pessimistic and ergodic operator
(S) = {u e V. E S c4 -, 20.
-4
(,)),, which it uses to update the pessimistic safe set. Similarly, it defines Ó,(+) using of" (.) to compute the optimistic safe set.
4
MACOPT and SAFEMAC
This section presents MACOPT and SAFEMAC, our algorithms for unconstrained and safety-constrained multi-agent coverage control, which we then formally analyze in Section 5
4.1
MACOPT: unconstrained multi-agent coverage control
Greedy sensing regions. In sequential optimization, it is crucial to balance exploration and exploita- tion. GP-UCB [19] is a theoretically sound strategy to strike such a trade-off that works well in practice. Agents evaluate the objective at locations that maximize an upper confidence bound over the objective given by the GP model such that locations with either a high posterior mean (exploitation) or standard deviation (exploration) are visited. We construct valid upper confidence bound for the cov- erage F(X) starting from our confidence intervals on p. by replacing the true density o with its upper bound uf in Eq. (I). Next, apply the greedy algorithm to this upper bound (Line 3 of Algorithm to select N candidate locations for evaluating the density. However, this simple exploration strategy may perform poorly, due to the fact that in order to reduce the uncertainty over the coverage F at X, we must learn the density at all locations inside the sensing region, U D' rather than simply X. It is form of partial monitoring (20). where the objective F' diffeers from the quantity we measure, i.c.. the density p. Next, we explain how to choose locations where to observe the density for a given X.
Uncertainty sampling. Given location assignments X for the agents, we measure the density to efficiently learn the function F(X). Intuitively, agent i observes the density where it's most uncertain within the area it covers that is not covered by agents (1,...i ......i111 i...i-1) 1], i..., Dj (Line Alg. 2 Fig 2ap.
Stopping criterion. The algorithm terminates when a near-optimal solution is achieved. Intuitively, this occurs when the uncertainty about the coverage value of the greedy recommendation is low, For- mally, we require the sum of the uncertainties over the sampling targets to be below a threshold, i.e.
w. = E - (x < e, 3 Algorithm Importantly, this stopping criterion requires the confidence intervals to shrink only at regions that potentially maximize the coverage.
MACOPT. Now, we introduce MACOPT in Algorithm 2 At round f, we select the sensing locations for the agents, X,, by greedily optimizing the upper confidence bound of the coverage. Then, each

---

x
R
Sp
(a) Uncertainty sampling in MACOPT
(b) Illustration of multi-agent GOOSE
Figure 2: a) The contours represent the density uncertainty, and the red x's correspond to the maximum coverage locations evaluated by the GREEDY Algorithm [ While these locations maximize coverage, they may not be informative about the coverage since the uncertainty can be low. Therefore, the agents collect measurements at the maximum uncertainty of the density in a dise (green x x's, " also known as uncertainty sampling. b) In a constrained environment, SAFEMAC evaluates x?" for all agents in the optimistic set 5t (violct) and set it as a next goal. It forms expander region (dark blue) to safely expand the pessimistic safe set Sp (green) toward the goal.
agent collects noisy density measurements the points of highest uncertainty within DJ- Finally, we update our GP over the density and, if the sum of maximum uncertainties within each sensing region small, we stop the algorithm.
4.2 SAFEMAC: safety-constrained multi-agent coverage control
separate the exploration of the safe set from the maximization of the coverage. Given an over and under approximation of the safe set (whose computation is discussed later), we want to explore optimistically optimal goals for each agent, similar to MACOPT. To this end, we find the maximizers of the density upper bound in the optimistic safe set with the GREEDY algorithm. Then, we define sampling goals learn the coverage at those locations.
Intuition. We adopt perspective similar to GoOSE
Phases of SAFEMAC. Coverage values depend both on the density and the feasible region (Eq. (2) Thus, there are two sensible sampling goals given disk assignment: i) optimistic coverage: if we uncertain about the density within the disks, we target locations with the highest density uncertainty (Line|Blof Algorithm 4 ii) optimistic exploration: if we know the density within the disk but there locations under that we cannot classify as either safe (in SP) or unsafe (in (o.t)) we target those with the highest constraint uncertainty among them (Line 8 If all the goal locations are safe with high probability, which can only happen during optimistic coverage, we safely evaluate the density there (Line 197. Otherwise, we explore the constraint with a goal directed strategy that aims classifying them as either safe or unsafe similar to GoOSE (Line 12). In case this changes the topological connection of the optimistic feasible set, we recompute the disks as this may change GREEDY'S 's output (Line 15 17). We repeat this loop until we know the feasibility of all the points under the disks recommended by GREEDY and their density uncertainty is low (Line 4 Next, we explain how the multiple agents coordinate their individual safe regions to evaluate goal (MACOPT in batches), how the agents progress toward their goals (safe expansion) and finally we describe SAFEMAC convergence.
MACOPT in batches, In the multi-agent setting of GoOSE (see Fig. 2b). each agent maintains Sp pessimistic (or S 5 an optimistic) belief of the safe locations, obtained by iteratively applying P.(-) the pessimistic or Ó.(-) the optimistic) ergodic operators (see Section 3 to the previous pessimistic belief sp (Line 11 of Algorithm 4). Since the agents cannot navigate to an arbitrary location in the constrained case, S SAFEMAC computes coverage maximizers on a restricted region, obtained by ignoring the known unsafe locations. denote such a restricted region, we define a union set S. := S 5... U S which is the largest set known to be optimistically or pessimistically safe up to time t. Moreover, if the agents are topologically disconnected, they cannot travel from one safe region to an- other and the best strategy for any batch of agents is to maximize coverage locally. For this, we form a collection of batches B,, such that any batch B B, contains agents that lie in topologically connected SAFEMAC computes a GREEDY solution for each This is the largest set where the agents can find an
regions determined by the union set (Line 13 14
B E B, in their corresponding Sp.
S.
5

---

Algorithm 1 Greedy UCB (GREEDY)
Algorithm 4 SAFEMAC
B, St 1: Inputs " 1/
1: Inputs Xo, Lg Ep. V. Gpp: GPg
2: for i = 1,2, ..., [B] do
2: Vi, 50 + -Xo, So + VV v
3: si + arg max
Σ u (1) WE DEDIAD D 5sa
3: X1, w1 + -GEEDY (ub. l. [M,,]
4: while Vi, (5 (91-1) 1) n Dj o or w Ep
4: 1t + arg max 1 (v) 19 (v)
do
EED* Dj 'sy
5:
if W. Ep then
5: 2/ f E 4 (x( (z9.1)
1=
B
6:
Vi, 2t gi+
+ arg max (0) (6-1(v)
6: Return X W
vED
7:
else
Algorithm 2 MACOPT
8:
0id + arg max ul (u) (1) Vi, 2t
NE(S " ssp
InD!
1: Inputs Xo. Ep. V. GP,, pt
2: X1, w f GREEDY (ug 66 [N], V)
9:
if [M] 2 & St.tt then
3: while w, Ep do
10:
SE(S Sp. 24 4.t)
Vi :n & Sp S (. So.60 O (St-), Vi
4: Vi, x6 + arg max 1 (v) (0)
11:
vEDi
12:
1+
5:
Vi, yb. = =(xx (1) + 7/ Update GP
13:
Vi, = [ n.o + 0}
6:
1. 1 1-1+1
14:
B, B.= L-UNEBBBB
7:
X,, (u
15:
if for any B E Br, St. f gu. then
8: Recommend X,
16:
X,, wy + GREEDY (uL 1: 11- B, S, SM.
17:
Vi, x[ +- arg max ( - 1/-1 (v) vED!
Al Algorithm& 3 Safe Expansion (SE)
1: Inputs S0 SP of
18:
if Vi, E ESt and wi Ep then
2: A,(p) + Eue S s (S (h()) pp
19:
Vi, = -((=?t)) + 11p
3: W²" - f St (1)
(v)) 5
20:
Update GP i.. compute uf 18
4: a* < max a s.t.
(G) 00
21:
t ++ X,, t (Uf B, S,
5: if Optimization problem feasible then "EG)" max, (a+) ub (v)
22:
6: 0r f-aarg arg max,
23:
Recommend X;
7: Update GP with yt (vv) + 174
optimistically safe path travel. Analogous B;, we define B. collection of batches where any B E By contains agents which are topologically connected in pessimistic set and ST. == St
Safe expansion. Safe expansion is the sub-routine inspired by GoOSE for goal-oriented exploration of the safe set that we use to learn about the feasibility of sampling targets. uses heuristic h to assign priority scores p to points that are optimistically but not pessimistically safe. Those determine locations whose feasibility is relevant to learn that of the sampling targets ( (Line Algorithm A simple and effective choice for the heuristic is the inverse of the distance to the targets. Then, it identifies safe locations where the constraint is not yet known cy- accuuratyy (Line Among them, determines the a a-immediate expanders, i.e., those that could potentially add locations with priority to the pessimistic set, (a) {u E W E2 E A+(a) u.( L,d(v, 2) 2 0}. In Line selects the non-empty a-expander set with the highest priority. In Line 6 7 the agent evaluates the
constraint at the location with the highest uncertainty in this set (see 112 for details).
SAFEMAC convergence. The optimistic coverage phase switches to optimistic exploration phase, when density uncertainty under the disks is low (w, S Ep). In the exploration, either the topological connection of the optimistic feasible set changes or will classify the uncertain region as pessimistically safe. In the former case, SAFEMAC will recompute a new coverage location and switch the coverage phase. Alternatively, if the uncertain region is pessimistically safe, SAFEMAC has converged since the density uncertainty the exploration phase already low. The phases show an interesting dynamics; SAFEMAC continuously iterates between the optimistic exploration and the optimistic coverage phase until we know about the feasibility of the disk and their uncertainty is low. the worst case, SAFEMAC might explore the entire environment. In this case the sample complexity will be similar to a two-stage algorithm, where we explore the whole domain and then optimize coverage in the resulting known environment. However, in practice, SAFEMAC is much better than this worst case.

---

5 Analysis
We now analyze MACOPT'S convergence and SAFEMAC's optimality and safety properties.
MACOPT. To measure the progress of MACOPT, we study its regret, i... the difference between its solution and the one could find if we knew the true density, Since control coverage consists in maximizing a monotone submodular function, we cannot efficiently compute the true optimum even for known densities. However, can efficiently find solution that is at least (1 1/e) within the optimum. Thus, we quantify performance using the following notion of cumulative regret. T
Reg (T) 1 Σ P(
E F(X.P,V)
(5)
where p. V) is the optimal coverage. We now state one of our main results, which guarantees that the cumulative regret of MACOPT grows sublinearly in time (proof in Appendix D
Theorem Let ó (0, 1), 06 = BB+ 40 / + 1n(1/8) and CD m ev |D1I/IV| S
With probability at least 1 8, MACOPT'S regret defined in Eq. 5 is bounded by O( TTVT590 (TNT))))
880 NT NT Y log(1 + No
Pr Regact (T)
21-5.
(6)
The proof [ on two key ideas. First, we exploit the conditional linearity of the submodular objective to bound the cumulative regret defined in Eq. ( with sum of per agent regrets. Secondly, we bound the per agent regret with the information capacity 7/y.. a quantity that measures the largest reduction in uncertainty about the density that can be obtained from NT' noisy evaluations of it. Since yv [2 grows sublinearly with T for commonly used kernels, so does MACOPT'S 's regret Eq. (6). The immediate corollary of the above theorem, when the MACOPT stopping criteria is reached (Line 3f Algorithm 2 guarantees a near optimal solution up to Ep precision.
sC3
Corollary 1. Let 1o be the smallest integer, such that Peg, 1og(I=No " then there exists
1 << l6 such that w.h.p, MACOPT terminates and achieves, F(X (1 (1-))F(X::p.)) Ep-
SAFEMAC.
This section presents our main result for safety-constrained multi-agent coverage control. In particular, Theorem 2 (proof in Appendix E guarantees that SAFEMAC safely achieves near-optimal safe coverage in finite time.
IN: Theorem 2. Let 8 E 10, ep 2 O, llelle S. Bp, g81/2 =Bp + A0, V ++ 1111=1/0)), Thee
denote the information capacity associated with the kernel kP, Let q(-) be Lipsschcii continuous and Cq I've be defined analogously. Given Xo + q(x)) 2 for all i E [N]. Then, for any heuristic hy : V + I., with probubility at least - 8. we have q(x) > O. for any along the state trajectory pursued by any agent in SAFEMAC. Moreover, let ln be the smallest integer such 8C7,N2
D
that BIRTNNT
log(1+No- with Cn = max
~VV TVT I 1 and let 1 be the smallest integer such
that probability at least
Cl CiRo(Xool, with C = 8/log(1 2 then, there exists 1. S fo + 122 such that with
oy
1-8.
Σ R, Ro(X))) (1 (1- Σ F(X Rx,(()))) cp- BEB.
BEB
The theoretical analysis has two components: (i) we show SAFEMAC's coverage is near-optimal at convergence (Lemma 10), and (ii) we prove it converges in finite time. Since SAFEMAC learns the constraint and the density, we must bound the sample complexity for both to prove (ii). For the constraint, we extend the results for single-agent GOOSE to our multi-agent setting (Appendix FF) For the density, we use results from Theorem Too to show that, within a coverage phase, the cumulative regret is sublinear. Next, we use additivity of the information gain (Lemma [3) between any pair of coverage phases to bound the sample complexity of density for the subsequent coverage phases. Combining these results, we obtain Theorem
Intermediate recommendation. Theorem 2 guarantees that SAFEMAC converges to safe and near- optimal solution. Can it also make sensible recommendations before the stopping criteria are met?
7

---

0.6
Ideally, such recommendations should (i) be safely reachable and (ii) ensure minimum coverage. To satisfy (i), they should be in the pessimistic safe set, Sy. To satisfy (i), their coverage should be computed according F. i.e., assuming worst-case density, 4- and a worst-case feasible set, ST. If the greedy recommendation X; is in S. we can recommend it at intermediate steps. However, this not always the case and we need an alternative. To this end, we compute X! i.e,, the greedy solution w.r.f. the worst-case objective, F ST. AB E B.- At any time T, SAFEMAC recommends the best of either strategy up time T according the worst-case objective. F(X;:p.V) V)
0.5
0.4
0.3
MacOpt-CUB
Mpc
MacOpt-H
UCB
0.2
50
100
150
Samples
(a) Obstacles environment
(b) Gorilla nest environment
(c) Coverage on gorilla nests (Sunny day)
Figure 3: The contours in: show the synthetic density and the obstacles marked by the black blocks, b) show the Gorilla nests distribution with weather constraints marked by the black dashed line, and its contours with grey dashed line. c) Compares MACOPT with UCB in the safe gorilla environment. MACOPT does a more principled exploration of the coverage and does not stick to local minimum.
In Appendix E.I. we show that such recommendation is also near optimal at convergence.
6 Experiments
This section compares MACOPT and SAFEMAC to existing methods (or their extensions) synthetic and real-world problems. We validate our theoretical claims and observe their superiority. We set 34 3 3 and 3 = 3 for all > 1, it ensures safety as well efficient exploration in practice [12] Experiment details and extended empirical analysis are in Appendix G
Environments. We perform our experiments with N = 3 agents in 30 x 30 grid world where states are evenly spaced over [0, 3|2. Each agent's disk is defined the region an agent can reach in r = 5 steps in the defined grid. We normalize coverage with a maximum value Rox P())/VV) Below, we present the 3 environments we consider.
In synthetic data, both the density p and the constrain g are sampled from GP with zero mean and Matérn Kernel with v = 2.5, scale aı = 1, and lengthscale / = 2. The observations are perturbed by ii.d noise (0, 30-3). ii) In obstacles, we sample maps with several block-shaped obstacles (Fig. Bap and we aim to maximize coverage while avoiding dangerous collisions. At u. each agent senses the distance to the nearest obstacle dm (v), which could be given by sensors such as ID-Lidars. We use (v) 1/(1 + exp(- mm (v))). to map the distance between [0,3] and saturate the constraint value for large distances, and we set (vv) ('(u) 0.5 avoid collisions. The density is sampled from the same GP as the synthetic case. iii) In gorilla nest, we simulate a bio-diversity monitoring task, where we aim to cover areas with high density of gorilla nests with a quadrotor in the Kagwene Gorilla Sanctuary (Fig. 3b) Regions affected by adverse weather (e.g. rain and storms) are unsafe for the drone due to higher chances of crashes and should be avoided. As proxy for bad weather, we use the cloud coverage data over the KGS from Open Weather [22]. The nest density is obtained by fitting a smooth rate function 23 over Gorilla nest counts 224.
MACOPT. We compare MACOPT to UCB, a baseline that skips the uncertainty sampling step from Section 4. and obtains measurements the centers of the GREEDY sensing regions. We further develop two sample-efficient extensions of MACOPT: i) Correlated upper bound (CUB), variant of MACOPT that constructs tighter upper confidence bound of the coverage function utilizing the covariance of density, instead of using the sum of density UCB. ii) Hallucinated uncertainty sampling (H), variant of MACOPT that samples at the most informative location for each agent i, after hallucinating sampling locations of (1, (l....i 1} agents. Please see Appendix D.I 1 for theoretical analysis. Fig. 3c shows comparison in the gorilla environment on day of good weather, i.e. when
all locations are safe. Here, UCB gets stuck in local optimum it does not reduce the uncertainty
8

---

0.4
0.4
0.8
F(Xy:p. ((Xy:p.R((X) RR)
Coverage
0.3
Samples
0.6
0.3
0.2
SafeMac
Two-Stage
0.2
0.1
0.2
PassiveMac
I
200
400
600
0.0
0.0
GP
Obst.
Gorilla
GP
Obst.
Gorilla
Samples
(a) Coverage at convergence
(b) Total number of samples
(c) Coverage on Gorilla nests (Rainy day)
Figure 4: Comparison of SAFEMAC with PASSIVEMAC and Two-Stage in all environments conver- gence (a) and (b) and during optimization for the gorilla environment in (c). SAFEMAC trades-off learning about density and constraints, such that it finds solution comparable to Two-Stage more efficiently, whereas PASSIVEMAC gets stuck in a local optimum.
of the density, whereas MACOPT explores more and achieves a higher coverage value up to 25%. Moreover, variants of MACOPT account for correlation and condition on other agents' measurement locations, which results in achieving the same coverage but more efficiently.
SAFEMAC. We compare SAFEMAC with two baselines: i) two-stage algorithm 25 that first fully explores the feasible region, and then uses MACOPT to maximize the coverage; ti) PASSIVEMAC, baseline inspired by [26] that runs MACOPT in the pessimistic set and passively measures the constraint in the process. Figs. 4a and 4b) show the coverage at convergence and the number of samples to converge for SAFRMAC and the two baselines across all the environments. The results are averaged over 50 instances produced using different seeds and samples for every environment. In Fig. 44b] the y-axis normalized with the maximum number of samples in the instance and then averaged over all instances. PASSIVEMAC converges quickly but gets stuck in a local optimum as it does not actively explore the constraint. SAFEMAC and Two-Stage converge much higher coverage values. However, SAFEMAC is up to 50% more sample efficient thanks to its goal goal-oriented exploration. Fig. 4c shows the coverage value the intermediate safe recommendations (Section (S) in the gorilla environment as a function of the number of samples. It confirms the previous results: SAFEMAC finds solutions comparable to Two-Stage more efficiently and PASSIVEMAC gets stuck in a local optimum.
Scalability. SAFEMAC utilizes the GREEDY algorithm, which is linear the number of nodes (domain size). In each iteration, SAFEMAC computes a greedy solution N times (one for each agent), which makes it linear in the number of agents. We model density and constraint using GP, which scales cu- bically with the number of samples. To demonstrate scalability in practice, we conducted experiments with N = 3, 6, 10, 15 agents each with domain length of 30, 40, 50 and 60 in Appendix G.I
7 Related work
Our work relates to multiple fields. We highlight the most relevant connections, referencing surveys where possible; exhaustive overview is beyond the scope of this paper.
Bayesian optimization. BO, an agent sequentially evaluates a noisy objective, seeking to max- imize it (27]. In contrast, the quantity we measure differs from our objective. Partial monitoring [28 addresses such issues in an abstract setting (20 29]. We exploit special structure in our problem. In coverage control with unknown density, this challenge is often addressed by learning the density uni-
formly over the domain [30 31]. In contrast, MACOPT learns the density only at promising locations.
Coverage control. MAC with known densities is a well-studied NP hard (32) problem. Many algorithms use efffciint heuristics converge quickly
local optimum. One popular strategy is Lloyd's algorithm (33. which has been studied in different settings, e.g., with known densities
34 B5), a-priori unknown densities [31 36 (38,, using graph neural networks [3)] taking into
account agent's 's dynamics and constraints 40,, or in case of non-identical robots [41]. These methods apply to continuous state and action spaces and show convergence to local optima, but lack optimality
guarantees 30 31 40 and sample complexity bounds. Moreover, their extension to non-convex,
disconnected domains is not trivial 42 Coverage control also studied the episodic setting
to learn the unknown policy the environment using deep RL methods 43 44)

---

Submodular optimization. Submodular functions are ubiquitous in machine learning 445 as they can be efficiently approximately maximized under different kinds of constraints 46) For example, the GREEDY algorithm can be used in case of cardinality constraints [3] to maximize quantities like mutual information [47] or weighted coverage functions [15]. Online submodular maximization aims optimizing unknown submodular functions from noisy measurements [48]. It has multiple applica- tions, including optimization of numerical solvers [49]. information gathering 50 and crowd-sourced image collection summarization [51]. Particularly related to ours is the work in [52], which proposes an algorithm for contextual news recommendation for linear user preferences with strong regret guar- antees. In contrast that setting, consider dynamic agents, safety constraints and partial feedback.
Safety. Depending on the safety formulation and the assumptions, many algorithms have been pro- posed for safe learning in dynamical systems, c.g., based on model predictive control [53], curriculum learning (54) Lyapunov functions [55] [6], reachability [57], CMDPs (58), behavioral system theory [59]. and more [60)62]. Here, we focus on the setting that is most closely related to ours, i.e., one with unknown but sufficiently regular instantaneous constraints that must be satisfied all times. For stateless problems, e.g. BO, [26] 63 propose algorithms with safety and optimality guarantees with different exploration strategies. For stateful problems, [64] studies the pure exploration case, while [63] These approaches may be sample inefficient as they may explore the constraint in regions irrelevant for the objective. GoOSE [2] addresses this problem for both the stateful and stateless setting. The only work in this context that addresses multi- -agent prob- lems is 665. However, their objective differs from ours, and they do not establish safety guarantees.
25 extends the two-stage approach from
Conclusion
We present two novel algorithms for multi-agent coverage control in unconstrained (MACOrT) and safety critical environments (SAFeMaC). We show MACOPT achieves sublinear cumulative regret, de- spite the challenge of partial observability. Moreover, we prove SAFEMAC achieves near optimal cov- erage in finite time while navigating safely. We demonstrate the superiority of our algorithms in terms of sample efficiency and coverage in real-world applications such as safe biodiversity monitoring.
Currently, our algorithms choose informative targets but do not plan informative trajectories, which crucial in robotics. We aim to address this in future work. Finally, while in many real-world applications the density and the constraints are as regular as assumed here, in some they are not. In these cases, our optimality and safety guarantees would not apply.
Acknowledgements
Manish Prajapat is supported by an ETH AI Center doctoral fellowship. Matteo Turchetta is supported by the Swiss National Science Foundation under NCCR Automation, grant agreement 5INF40 180545. We would like to thank Pawel Czyz for insightful discussions.
10

---

References
[1] Miquel Kegeleirs, Giorgio Grisetti, and Mauro Birattari. Swarm slam: Challenges and perspec- tives. Frontiers in Robotics and AI, 8:618268, 2021.
[2] Alan Mainwaring, David Culler, Joseph Polastre, Robert Szewezyk, and John Anderson. Wire- less sensor networks for habitat monitoring. In Proceedings of the 1st ACM international workshop on Wireless sensor networks and applications, pages 88 97, 2002.
[3] Mahmoud Tavakoli, Gonçlo Cabrita, Ricardo Faria, Lino Marques, and Anibal T de Almeida. Cooperative multi-agent mapping of three- siree-dimensioall structures for pipeline inspection appli- cations. The International Journal of Robotics Research, 31(12): 1503, 2012.
[4] Bang Wang. Coverage control in sensor networks. Springer Science & Business Media, 2010.
[5] Ryan Lowe, Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed cooperatiee-ompptttive environments. Advances in neural information processing systems, 30, 2017.
[6] Manish Prajapat, Kamyar Azizzadenesheli, Alexander Liniger, Yisong Yue, and Anima Anand- kumar. Competitive policy optimization. In Uncertainty in Artificial Intelligence, pages 64-74. PMLR, 2021.
[7] lou-Jen Liu, Unnat Jain, Raymond A Yeh, and Alexander Schwing. Cooperative exploration for multi-agent deep reinforcement learning. In International Conference Machine Learning, pages 6826-6836. PMLR, 2021.
[8] Pericle Salvini, Diego Paez-Granados, and Aude Billard. Safety concerns emerging from robots navigating in crowded pedestrian areas. International Journal of Social Robotics, 14(2): 441-462, 2022.
[9] Yuliya Averyanova and E. Znakovskaja. Weather hazards analysis for small uass durability enhancement. In 2021 IEEE 6th International Conference on Actual Problems of Unmanned Aerial Vehicles Development (APUAVD), pages 41 44, 2021. doi: 10. 109/APUAVD53800 2021.9615440.
[10] Mozhou Gao, Chris H Hugenholtz, Thomas A Fox, Maja Kucharczyk, Thomas E Barchyn, and Paul R Nesbit, Weather constraints on global drone flyability. Scientific reports, 11(1):1-13, 2021.
[11] Andreas Krause and Carlos Guestrin. Submodularity and its applications in optimized infor- mation gathering. ACM Trans. Intell. Syst. Technol., 2(4), jul 2011. ISSN 2157-6904. doi: 04.144//189733.1999777
lattpsss::///oi. org/ 10. 1145 11144/9999994411 1989736
[12] Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. Safe exploration for interactive machine learning. Advances in Neural Information Processing Systems, 32, 2019.
[13] George Nemhauser, Laurence Wolsey, and M. Fisher. An analysis of approximations for maximizing submodular set functions. Mathematical Programming, 14:265-294, 12 1978. doi: 10.1007/BF015888971.
[14] Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Natalie Glance. Cost-effective outbreak detection in networks. In Proceedings of the 13th ACM SIGKDD international conf. on Knowledge discovery and data mining, pages 420, 2007.
[15] Uriel Feige. A threshold of n for approximating set cover. J. ACM, 45(4):634 652. jul 1998. ISSN 0004-5411, doi: 10.1145/285055.28822 URL https:://ooi http////ooooo///////// 100....1152200000
285059
[16] Bernhard Schlkopf, Alexander J. Smola, and Francis Bach. Learning with Kernels: Support Vector Machines, Regularization, Optimization, and Beyond. The MIT Press, 2018. ISBN 0262536579.

---

[17] Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning (Adaptive Computation and Machine Learning). The MIT Press, 2005. ISBN
[18] Sayak Ray Chowdhury and Aditya Gopalan. On kernelized multi-armed bandits. In International Conference Machine Learning, pages 844-853. PMLR, 2017.
[19] Niranjan Srinivas, Andreas Krause, Sham M. Kakade, and Matthias W. Seeger. Information- theoretic regret bounds for gaussian process optimization in the bandit setting. IEEE Transac- tions on Information Theory, 5865):3250-3265 2012. doi: 10.1109/T1T.00 1.2182033.
[20] Johannes Kirschner, Tor Lattimore, and Andreas Krause. Information directed sampling for linear partial monitoring. In Conference on Learning Theory, pages 2328-2369. PMLR, 2020.
[21] Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Statistics, pages 82 90. PMLR, 2021.
[22] Open weather. Attps:://ppnneaathermm.p
2022.
[23] Mojmír Mutný and Andreas Krause. Sensing cox processes via posterior sampling and positive bases. CoRR, abs/2110.1118// 2021. URL URLnttpss//arrxww.rr/////// wwt./////a///....o///////////... 11181
[24] Neba Funwi-gabga and Jorge Mateu. Understanding the nesting spatial behaviour of gorillas in the kagwene sanctuary, cameroon. Stochastic Environmental Research and Risk Assessment, 26, 08 2011. doi: 10.11077:00047-0110555
[25] Akifumi Wachi and Yanan Sui. Safe reinforcement learning in constrained markov decision processes. JCML, pages 9797-9806, 2020. URL http://prooceedings .ll. mwr.prres.
v119/wachi h0m.hmml
html
[26] Yanan Sui, Alkis Gotovos, Joel Burdick, and Andreas Krause. Safe exploration for optimization with gaussian processes, In International conference machine learning, pages 997-1005. PMLR, 2015.
[27] Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104 doi: 10.1 110.//PR...2115.24442222
(1):148 175, 2016.
[28] Tor Lattimore and Csaba Szepesvári. Partial Monitoring, page 423-451. Cambridge University Press, 2020. doi: 00.10179971100857144 4046.
[29] Tor Lattimore and Csaba Szepesvári. An information-theoreti approach to minimax regret in partial monitoring. In Conference Learning Theory, pages 21 2111-2139, PMLR, 2019.
[30] Lai Wei, Andrew McDonald, and Vaibhav Srivastava. Regret analysis of distributed gaussian process estimation and coverage. CoRR, 0ass/2211.04006. 2021. httpps//////a org/ 0ba/21101.0435
[31] Andrea Carron, Marco Todescato, Ruggero Carli, Luca Schenato, and Gianluigi Pillonetto. Multi-agents adaptive estimation and coverage control using gaussian regression. In 2015 Euro- pean Control Conference (ECC), pages 2490-2495, 2015. doi: 10. /001////CCC.....33991911
[32] Andreas Krause, Ajit Singh, and Carlos Guestrin. Near-optimal sensor placements in gaussian processes: Theory, efficient algorithms and empirical studies. Mach. Learn. Res., 9:235-284, jun 2008. ISSN 1532-4435.
[33] Lloyd. Least squares quantization in pem. IEEE Transactions on Information Theory, 28(2): 129-137, 1982. doi: 10.
[34] Jorge Cortes, Sonia Martinez, Timur Karatas, and Francesco Bullo. Coverage control for mobile sensing networks. IEEE Transactions robotics and Automation, 20(2):243-255, 2004.
12

---

[35] Francois Lekien and Naomi Ehrich Leonard. Nonuniform coverage and cartograms. SIAM Journal on Control and Optimization, 48(1):351-372, 2009. doi: 10.1137/070681 1200. URL https://doi. http///ii.ogg//////// org/10. 1137/070681120
[36] Yunfei Xu and Jongeun Choi. Adaptive sampling for learning gaussian processes using mobile sensor networks. Sensors (Basel, Switzerland), 1 11:3051-66, 12 2011. doi: 10.3390/s11030300
[37] Wenhao Luo and Katia Sycara. Adaptive sampling and online learning in multi-robot sensor coverage with mixture of gaussian processes. In 2018 IEEE International Conference on Robotics and Automation (ICRA), pages 6359-6364. IEEE, 2018.
[38] Alessia Benevento, María Santos, Giuseppe Notarstefano, Kamran Paynabar, Matthieu Bloch, and Magnus Egerstedt. Multi-robot coordination for estimation and coverage of unknown spatial fields. In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 7740-7746, 2020. doi: 10.1 1LL1L///CRA444452200000000999
[39] Walker Gosrich, Siddharth Mayya, Rebecca Li, James Paulos, Mark Yim, Alejandro Ribeiro, and Vijay Kumar. Coverage control in multi-robot systems via graph neural networks. In 2022 International Conference on Robotics and Automation (ICRA), pages 8787-8793. IEEE, 2022.
[40] Andrea Carron and Melanie N Zeilinger. Model predictive coverage control. PapersOnLine, 53(2):6107-611 2020.
IFAC-
[41] Soobum Kim, María Santos, Luis Querrero-Bonilly Anthony Yezzi, and Magnus Egerstedt. Coverage control of mobile robots with different maximum speeds for time-sensitive applica- tions. IEEE Robotics and Automation Letters, 7(2):3001-3007, 2022. doi: 10.1 209/
3 3146593.
[42] Francesco Bullo, Ruggero Carli, and Paolo Frasca. Gossip coverage control for robotic networks: Dynamical systems on the space of partitions. SIAM Journal on Control and Optimization, 50 (1):419-447, 2012.
[43] Saba Faryadi and Javad Velni. reinforcement learning-based approach for modeling and coverage of unknown field using team of autonomous ground vehicles. International Journal of Inteligent Systems, 36, 11 2020, doi: 20311..
[44] Gianpietro Battocletti, Riccardo Urban, Simone Godio, and Giorgio Guglieri. Rl-based path planning for autonomous aerial vehicles in unknown environments. In AIAA AVIATION 2021 FORUM, page 3016, 2021.
[45] Jeff Bilmes. Submodularity in machine learning and artificial intelligence. arXiv preprint arXiv:2202.00/32, 2022.
[46] Andreas Krause and Daniel Golovin. Submodular function maximization. Tractability, 3:
71-104, 2014.
[47] Andreas Krause and Carlos Guestrin. Near-optimal nonmyopic value of information in graphical models. In Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence, UAI'05, page 324-331. AUAI Press, 2005. ISBN 0974903914.
[48] Lin Chen, Andreas Krause, and Amin Karbasi. Interactive submodular bandit. In NIPS, 2017.
[49] Matthew Streeter, Daniel Golovin, and Stephen F Smith. Combining multiple heuristics online. In AAAI, pages 1197-1203, 2007.
[50] Daniel Golovin, Andreas Krause, and Matthew Streeter. Online submodular maximization under matroid constraint with application to learning assignments. arXiv preprint arXiv:1407.1082. 2014.
[51] Adish Singla, Sebastian Tschiatschek, and Andreas Krause. Noisy submodular maximization via adaptive sampling with applications to crowdsourced image collection summarization. In Thirtieth AAAI Conference on Artificial Intelligence, 2016.
[52] Yisong Yue and Carlos Guestrin. Linear submodular bandits and their application to diversified retrieval. Advances in Neural Information Processing Systems, 24, 2011.
13

---

[53] Lukas Hewing, Kim P Wabersich, Marcel Menner, and Melanie N Zeilinger. Learning-bees based model predictive control: Toward safe learning in control. Annual Review of Control, Robotics, and Autonomous Systems, 3:269-296, 2020.
[54] Matteo Turchetta, Andrey Kolobov, Shital Shah, Andreas Krause, and Alekh Agarwal. Safe reinforcement learning via curriculum induction. Advances in Neural Information Processing Systems, 33:12151-1216: 2020.
[55] Felix Berkenkamp, Mateo Turchetta, Angela Schoellig, and Andreas Krause. Safe model-based reinforcement learning with stability guarantees. Advances in neural information processing systems, 30, 2017.
[56] Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman,, and Mohammad Ghavamzadeh. A lyapunov-based approach to safe reinforcement learning. Advances in neural information processing systems, 31, 2018.
[57] Jaime F Fisac, Anayo K Akametalu, Melanie N Zeilinger, Shahab Kaynama, Jeremy Gillula, and Claire J Tomlin. A general safety framework for learning-based control in uncertain robotic systems. IEEE Transactions on Automatic Control, 6477):2377-2752, 2018.
[58] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31. PMLR, 2017.
[59] Jeremy Coulson, John Lygeros, and Florian Dorfler. Distributionally robust chance constrained data-enabled predictive control. IEEE Transactions on Automatic Control, 2021.
[60] Lukas Brunke, Melissa Greeff, Adam W Hall, Zhaocong Yuan, Siqi Zhou, Jacopo Panerati, and Angela P Schoellig. Safe learning robotics: From learning- control to safe reinforcement learning. Annual Review of Control, Robotics, and Autonomous Systems, 5, 2021.
[61] Alex Ray, Joshua Achiam, and Dario Amodei. Benchmarking safe exploration in deep rein- forcement learning, arXiv preprint arXiv:1910.01708, 7:1, 2019.
[62] Jan Leike, Miljan Martic, Victoria Krakovna, Pedro A Ortega, Tom Everitt, Andrew Lefraneq, Laurent Orseau, and Shane Legg. Ai safety gridworlds. arXiv preprint arXiv: 1.79811.88,,,, 2017.
[63] Yanan Sui, Vincent Zhuang, Joel W. Burdick, and Yisong Yue. Stagewise safe bayesian optimization with gaussian processes, 2018. httptttss///xiii www.://gg..a.......e///o 07555
[64] Matteo Turchetta, Felix Berkenkamp, and Andreas Krause. Safe exploration in finite markov decision processes with gaussian processes. Advances in Neural Information Processing Systems, 29, 2016.
[65] Zheqing Zhu, Erdem BIyik, and Dorsa Sadigh. Multi-agent safe planning with gaussian processes. In International Conference on Intelligent Robots and Systems (IROS), pages 6260- 6267, 10 2020. doi: 10.100//R0045443300000911111
[66] Mojmír Mutný and Andreas Krause. Experimental design for linear functionals in reproducing kernel hilbert spaces. arXiv preprint urXiv:2205. 13627, 2022.
[67] Maximilian Balandat, Brian Karrer, Daniel Jiang, Samuel Daulton, Ben Letham, Andrew G Wil- son, and Eytan Bakshy. Botorch: framework for efficient monte-carlo bayesian optimization. Advances in neural information processing systems, 13:21524-21588 2020.
[68] Jacob Gardner, Geoff Pleiss, Kilian Q Weinberger, David Bindel, and Andrew G Wilson Gpytorch: Blackbox matrix matrix gaussian process inference with gpu acceleration. Advances in neural information processing systems, 31, 2018
[69] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. Advances in neural information processing systems, 32, 2019.
14

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] See Section for the main theorems and Section 6 for the experimental results
(b) Did you describe the limitations of your work? [Yes] See Section g
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes) See Section
(b) Did you include complete proofs of all theoretical results? [Yes] See Section 5 with corresponding links to the Appendix for Proofs
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes] Code is attached in the supplemental material along with the environment maps used. The code folder contains a ReadMe file containing instructions to reproduce the result.
(b) Did you specify all the training details (e.g.. data splits, hyperparameters, how they were chosen)? [Yes] See Section 6 with corresponding links Appendix G for complete experimental setup details
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Errors bars are reported by running experiments with multiple random seeds and random environments
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Compute details are in Appendix G
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) your work uses existing assets, did you cite the creators? [Yes] In Section we cited the data and the model used in the Gorilla nest dataset
(b) Did you mention the license of the assets? [Yes] In Appendix G along with the experiment setup details we mentioned the license of the relevant code and data used (c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
15


Reviews:
[{"review_id": "pzo92J0BzW", "reviewer": "Reviewer_9Vst", "summary": "The paper presents an algorithm for safe coverage and exploration with multiple robots.  Particularly, the paper focuses on an active information gathering problem where multiple mobile robots choose how to move around to explore the environment and maximize its coverage.  Coverage is modelled through a spatial Gaussian process density function.  Exploration is necessary since the density is unknown a priori.  Safety constraints are also considered (the robots cannot access all locations in the environment), which are also assumed unknown a priori.  The constraints are also modeled via Gaussian Processes.  The paper provides an algorithm that guarantees (i) near-optimal coverage and (ii) satisfaction of the safety constraints. The algorithm is evaluated on a synthetic and two real world applications: safe biodiversity monitoring and obstacle avoidance.", "questions": "1.  I would elaborate on how the chosen kernel functions are known a priori.\n2.  I would elaborate on how dynamics constraints are considered.  For example, can robots move arbitrarily within the safety sets?\n3.  I would elaborate on how scalable the proposed method is.  What is its computational complexity? Up to how many robots can it scale?\n", "limitations": "1.  The paper discusses in the conclusion that the robots currently are allowed to jump from any point in the safety set to any other; the conclusion states that future work will address the problem of planning feasible trajectories.\n2.  I would elaborate on the limitations of modeling the density and safety constraints as Gaussian Processes.\n3.  I would elaborate on how scalable the proposed method is.  \n", "rating": 5, "confidence": 5, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n(+)  Proposed algorithm guarantees sublinear regret and safety\n(+)  Algorithm’s effectiveness is illustrated in simulations\n\nWeaknesses\n(-)  Density and constraints have a known structure, being modeled as Gaussian Processes given kernel functions.  I would elaborate on how the chosen kernel functions are known a priori.\n(-)  The robots are allowed to jump from any point in the safety set to any other.\n(-)  The experiments consider robot teams of only 3 robots.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "ifyqmMr8mFh", "reviewer": "Reviewer_p24T", "summary": "This paper looks into multi-agent coverage control (MAC) problems, in which multiple agents coordinate and navigate the environment to maximize the coverage of some densities. It aims at learning the density to solve the problem while ensuring the safety of the agents. It formally defines the safety-constrained multi-agent coverage control problem. The MAC task is modeled as a conditionally linear coverage function that possesses monotonocity and submodularity. A single-agent safe exploration algorithm named GOOSE is introduced. Using GOOSE as the intuition, the authors propose MACOPT, an unconstrained multi-agent coverage control algorithm, and SAFEMAC, a safety-constrained multi-agent coverage control algorithm that is created by extending GOOSE to multi-agent cases and combining it with MACOPT. Then they prove the convergence of MACOPT and the optimality and safety properties of SAFEMAC. Finally, the paper discusses how MACOPT and SAFEMAC are superior compared to existing methods by doing experiments in synthetic and real-world applications. It shows that SAFEMAC obtains better solutions than algorithms that do not actively explore the feasible region and that it has higher sample efficiency than competing near-optimal safe algorithms. ", "questions": "In the Introduction section, the authors mentioned that deploying coverage control solutions in the real world presents many challenges and no prior work addressed them jointly. One of the challenges is that multi-agent coverage control with known densities is an NP-hard problem. Has the paper tried to address this specific problem? \n\nIn the Conclusion section, the authors noted that although in many real-world applications the density and the constraints are as regular as assumed in the paper, in some they are not. Is there a specific example in which the algorithms do not apply well?", "limitations": "The authors specified that the limitation of the paper is that the proposed algorithms choose informative targets without planning informative trajectories, which can be crucial in the research of robotics. Besides, in some real-world applications, the density and the constraints may not be the same as assumed in the paper. In these cases, the algorithms no longer have optimality and safety guarantees. It is not likely that this paper will cause any potential negative social impact.", "rating": 6, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "This paper introduces a single-agent safe exploration algorithm (GOOSE) as the background, extends it to a multi-agent version, and proposes two algorithms for unconstrained and safety-constrained multi-agent coverage control problems. It starts from a well-known method and then presents novel approaches inspired by it, which demonstrates good originality.\n\nThe submission is written in a very solid style. The problem statement and definitions are formal, and the pseudocodes for MACOPT and SAFEMAC are displayed in detail. The paper analyzes MACOPT ’s convergence and SAFEMAC ’s optimality and safety properties using theorems and mathematical proofs. The statements are accurately written and rigorously proved (the full derivation is included in the appendix). The structure of the main paper is clear and organized. The authors demonstrate that multi-agent coverage control tasks are a class of difficult problems, especially when safety needs to be guaranteed, and their new methods provably address the tasks more efficiently than previous works.\n\nOn the other hand, the description of the figures should be improved. In the caption of Figure 1, it says \"Agent 1 covers $D^1$ (green), 2 covers $D^{2-}$ (orange) and 3 covers $D^{3-}$ (yellow).\" However, I cannot see where $D^1$, $D^{2-}$ and $D^{3-}$ are labeled in Figure 1(a). It also says \"In b) ... in the optimistic set\", but this set is not marked and its color is not specified in Figure 1(b) either.\n\nAnother side note is about the grammar problem. For instance,  in line 108, \"... a the positive definite kernel matrix ...\" should be \"... the positive definite kernel matrix ...\" and in line 265, \"... such 1D-Lidars.\" should be \"... such as 1D-Lidars.\"\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "bWFSOUxjnLe", "reviewer": "Reviewer_EbSJ", "summary": "The paper proposes a multi-agent coverage algorithm for a 2D environment with a priori unknown unsafe regions and noise density estimates that is guaranteed to be within a constant factor away from the optimal solution under certain assumptions (e.g. well behaved density and safety functions).", "questions": "Would the problem under the assumption of conditionally linear, monotone and submodular functions still be NP hard?\n\nI am not sure if Algorithms 1 and 4 are fully correct. In Lines 3 and 5, respectively, initially when t=0, they probe w_0, which is not initialised. Should this be w_1?\n\nCorollary 1 seems to suggest that choosing t_p^* = 0 always works. I think it should be >= not <=.\n\nIn Section 5 (Analysis), you state \"Since control coverage consists in maximizing a monotone submodular function, we cannot compute the true optimum even for known densities\". Why is this the case (in general, that is, non-greedy approaches)? Could one not simply enumerate through all solutions?\n\nHow would the method scale with the number of agents (K beyond 3)?", "limitations": "Not applicable", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The strength of the paper is a novel formulation of the exploration vs exploitation problem that takes into account agent safety in a multi-agent setting as well as the performance guarantees obtained. Although the algorithms and analysis built on previous work (e.g. [11,16,23]), I thought the work to be sufficiently novel.\n\nThe performance guarantee (Theorem 2) states that by doing enough iterations (i.e. sampling as a function of epsilon and delta), one can guarantee that the solution quality gets arbitrarily close (i.e. epsilon) to within a constant factor of 1-1/e of the optimum [10] with probability 1 - delta. Hence, the claim in the abstract of \"near optimal coverage in finite time\" seems overstated. In fact, when running the algorithm for a finite time, with probability delta > 0 one may end up worse than within epsilon from the constant factor approximation. Moreover, even if running the algorithm indefinitely, one can end up 1/e which corresponds to about 37% away from the optimum, which is good, but may not be considered as \"near-optimal\" by everyone.\n\nThe main weakness of the paper is that:\n(i) path planning of individual agents is not considered (samples are taken from regions of sufficiently safe cells, hence, ignoring the time and risks that accumulate for an agent as it travels through this region);\n(ii) it is not clear to what extent the proposed methods scale as only K=3 agents are considered and the environment is relatively small considering the intended applications (30 x 30 cells) albeit it is not a toy problem. Given much prior work exists for K=1, I would have appreciated an evaluation of the methods (that specifically address the multi-agent scenario) in more complex settings.\n\nThe paper claims that constraints prevent \"agents from monitoring from unsafe locations\" and agents \"may be unable to safely reach a disconnected safe area\" starting from their initial locations. The problem statement assumes that agents can only monitor locations that they can (in principle) reach, as they have to be part of the subset of the largest \"safely reachable region\" (see equation 2). This prevents an agent from monitoring say the other side of a river if the river cannot be safely crossed, irrespective of their sensing range. Although reasonable (to not overly complicate the problem statement), this assumption should be explicitly acknowledged, as the optimality guarantees are not correct otherwise.\n\nThe problem statement is challenging to follow, given there are a number of inter-connected aspects. Up to equation (2) it is rather straightforward, however, given uncertainties are introduced regarding the density and safety it is less clear thereafter what is actually the objective. For example, if the objective was to obtain the best possible result over a fixed duration - which may be realistic objective in practice - than the methods would not necessarily deliver, as the solutions presented do not seem to be anytime algorithms. Instead, the objective seems to be provide a solutions however long it takes (see also minor suggestions below).\n\nA few assumptions may make it harder to implement the method in practice, including the need for a centralised optimisation and synchronous measurements as well as the functions needed to be continuous (if they are not, the advantage of the method may be reduced). Also, looking at Figure 3(c), it seems there is a certain window (in terms of number of samples) where SafeMac excels whereas if there are fewer samples the method is clearly outperformed by PassiveMac, and as the number of samples approach 800 (which is almost 900 = one sample per cell) I wonder whether other solutions exists that perform equally well or better.\n\nI am not sure if Algorithms 1 and 4 are fully correct. In Lines 3 and 5, respectively, initially when t=0, they probe w_0, which is not initialised. Should this be w_1?\n\nCorollary 1 seems to suggest that choosing t_p^* = 0 always works. I think it should be >= not <=.\n\nIn Section 5 (Analysis), you state \"Since control coverage consists in maximizing a monotone submodular function, we cannot compute the true optimum even for known densities\". Why is this the case (in general, that is, non-greedy approaches)? Could one not simply enumerate through all solutions?\n\nI could not find a definition of L_q (input of Algorithm 4).\n\nMinor comments:\n- When talking about approximations of the feasible sets, are the max and min operators over x?\n- You first refer to Algorithm 2, then to Line 4 in Algorithm 1, and then you write \"Now, we introduce MACOPT (Algorithm 1)\", which is not ideal.\n- Where is [11] published?\n- In Theorem 2, you start with \"Let delta be element of (0,1)\", but the same could be said for epsilon, as you chose to use 2 variables instead of one.\n- \"a expander\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "Gtj1-QZAA5", "reviewer": "Reviewer_rxa3", "summary": "Two algorithms to deal with a map covering problem where there are unknown obstacles is proposed. The first algorithm is a single agent algorithm in which it needs to deal with the exploration-exploitation dillema because of the partial observability of the environment. \nThe second algorithm, extends the first algorithm by considering multi-agent settings in which the exploration as well as the safe coverage is a chanllenge. It is shown that the second algorithm obtain near optimal coveragw while guarantees the safety.", "questions": "Q0- Would your algorithm works OK with larger number of agents? For example [3] and [4] run problems with 20 and 10 agents, respectively. Is it possible for you to run a problem with a same or bigger size? \nSimilarly, [5] has a 4 agents problem and the analyzed environment is also pretty similar to yours. That also could be a good benchmark. \n\nQ1- I have seen several RL and MARL algorithm to deal with this problem. Even though you propose a sublinear cumulative regret, but still you do not know if the RL based algorithm can achieve the same performance or not on a same problem. I think an interseted reader would like to see the comparisons of these two classes of algorithms. \n\n[1] A reinforcement learning‐based approach for modeling and coverage of an unknown field using a team of autonomous ground vehicles\n[2] Adepegba, Adekunle A., Suruz Miah, and Davide Spinello. \"Multi-agent area coverage control using reinforcement learning.\" The Twenty-Ninth International Flairs Conference. 2016.\n[3] Ye, Zhenhui, et al. \"Multi-UAV Navigation for Partially Observable Communication Coverage by Graph Reinforcement Learning.\" IEEE Transactions on Mobile Computing (2022).\n[4] Gosrich, Walker, et al. \"Coverage Control in Multi-Robot Systems via Graph Neural Networks.\" 2022 International Conference on Robotics and Automation (ICRA). IEEE, 2022.\n[5] Battocletti, Gianpietro, et al. \"RL-based Path Planning for Autonomous Aerial Vehicles in Unknown Environments.\" AIAA AVIATION 2021 FORUM. 2021.  \n[6] Din, Ahmad, et al. \"A deep reinforcement learning-based multi-agent area coverage control for smart agriculture.\" Computers and Electrical Engineering 101 (2022): 108089.\n[7] Faryadi, Saba, and Javad Mohammadpour Velni. \"A reinforcement learning‐based approach for modeling and coverage of an unknown field using a team of autonomous ground vehicles.\" International Journal of Intelligent Systems 36.2 (2021): 1069-1084.\n", "limitations": "Same as above ", "rating": 5, "confidence": 1, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Same as below ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept