Differentiable Approximations for Multi-resource Spatial Coverage Problems
Authors: Nitin Kamra
Yan Liu
Venue:  (2021)
Keywords: Multi-agent coverage
Multi-resource coverage
Areal coverage
Differentiable approximations

Abstract: Resource allocation for coverage of physical spaces is a challenging problem in robotic surveillance, mobile sensor networks and security domains. Recent gradient-based optimization approaches to this problem estimate utilities of actions by using neural networks to learn a differentiable approximation to spatial coverage objectives. In this work, we empirically show that spatial coverage objectives with multiple-resources are combinatorially hard to approximate for neural networks and lead to sub-optimal policies. As our major contribution, we propose a tractable framework to approximate a general class of spatial coverage objectives and their gradients using a combination of Newton-Leibniz theorem, spatial discretization and implicit boundary differentiation. We empirically demonstrate the efficacy of our proposed framework on single and multi-agent spatial coverage problems.

Under review as a conference paper at ICLR 2021
DIFFERENTIABLE APPROXIMATIONS FOR MULTI- RESOURCE SPATIAL COVERAGE PROBLEMS
Anonymous authors Paper under double-blind review
ABSTRACT
Resource allocation for coverage of physical spaces is challenging problem in robotic surveillance, mobile sensor networks and security domains. Recent gradient-basse optimization approaches this problem estimate utilities of actions by using neural networks to learn a differentiable approximation to spatial coverage objectives. In this work, empirically show that spatial coverage objectives with multiple-resoureee are combinatorially hard to approximate for neural networks and lead sub-optimal policies. As our major contribution, we propose tractable framework to approximate a general class of spatial coverage objectives and their gradients using combination of Newton-Leibniz theorem, spatial discretization and implicit boundary differentiation. We empirically demonstrate the efficacy of our proposed framework on single and multi-agent spatial coverage problems.
INTRODUCTION
Allocation of multiple resources for efficient spatial coverage is an important component of many practical single-agent and multi-agent systems, for e.g., robotic surveillance, mobile sensor networks and security game modeling. Surveillance tasks generally involve a single agent assigning resources c.g. drones or sensors, each of which can monitor physical areas, to various points in target domain such that a loss function associated with coverage of the domain is minimized (Renzaglia et al. 2012). Alternatively, security domains follow leader-follower game setup between two agents, where defender defends a set of targets (or a continuous target density in geographical area) with limited resources to be placed, while an attacker plans an attack after observing the defender's placement strategy using its own resources TTame 2011).
Traditional methods used to solve single-agent mulli-resource surveillance problems often rely on potential fields (Howard et al. 2002)) discretization based approaches (Kong et al.) (2006). voronoi tessellations (Dirafzoon et al. 2011) and particle swarm optimization (Nazif et al. 2010 Saska et al. 2014). Similarly, many exact and approximate approaches have been proposed to maximize the defender's ' expected utility in two-agent multi resourre security domains against a best responding attacker (Kiekintveld al. [2009] Amin et al.) [016)] Yang et al. [2014] Haskell et al.) [0014] Johnson eet al. |012]Huang et al.] (020). Notably, most existing traditional approaches focus on exploiting some specific spatio-temporal or symmetry structure of the domain being examined.
Since spatial coverage problems feature continuous action spaces, a common technique used across most previous works is to discretize the area be covered into grid cells and restrict the agents' actions to discrete sets (Kong et al. 2006 Yang et al.) 2014:) Haskell et al. 2014 Gan et al. 2017) to find the equilibrium mixed strategies or optimal pure strategies using integer linear programming. However, discretization quickly becomes intractable when the number of each agent's ' resources grows large. While some games can be characterized by succinet agent strategies and can be solved efficiently via mathematical programming after discretizing the agents' actions spaces (Behnezhad et al., 2018), this not true for most multi-resource games.
Related Work:
Recent works in spatial coverage domains have focused on incorporating advances from deep learning to solve the coverage problems with more general algorithms. For instance, /ham et al. 20018 focus on the multi-UAV coverage of field of interest using model-free multi-agent RL method while StackGrad (Amin et al. 2016). OptGradFP (Kamra et al., 2018), PSRO (Lanctot et al. 2017 are model-free fictitious play based algorithms which can be used to solve games in continuous action spaces. However model-fe free approaches are sample inefficient and require many interactions with the domain (or with simulator) to infer expected utilities of agents' actions. Secondly, they often rely

---

Under review as a conference paper at ICLR 2021
on the policy gradients to compute the derivative of the agents' expected utilities w.n.t their mixed strategies, which induces a high variance in the estimate.
To alleviate these issues, more recent works take actor-critic based approach (Lowe et al. 2017), which additionally learns a differentiable approximation to the agents' utilities (Kamra et al. 2019a Wang et al. 2019) and calculate gradients of strategies w.r.t. the utilities. But this requires learning accurate reward/value functions which becomes combinatorially hard for multi-resource coverage.
Contributions:
To address the above challenge, we present framework to tractably approximate a general class of spatial coverage objectives and their gradients via spatial discretization without having to learn neural network based reward models. We only discretize the target domain to represent integrals and all set operations over it, but not the action spaces of the agents. Hence we mitigate the intractability caused by discretizing high dimensional action spaces of agents with large number of resources, while also keeping agents' actions amenable to pradient-based optimization. By combining our framework with existing solution methods, we successfully solve both single-agent and adversarial two-agent multi-resource spatial coverage problems.
MULTI-RESOURCY SPATIAL COVERAGE PROBLEMS
In this section, we formally introduce notation and definitions for multi-resource allocation problems along with two example applications, which will be used for evaluation.
multi-resource spatial coverage: Spatial coverage problems comprise of a target space Q The (generally d E (2) and set of agents (or players) P with each agent p E P having mp resources. We will use the notation -p to denote all agents except p i.e. PV (p). Actions: An action Up E Xd, for agent p is the placement of all its resources in an appropriate coordinate system of dimension dp. Let Un denote the compact, continuous and convex action set of agent p. Mixed strategies: We represent mixed strategy i.e. the probability density of agent p over its action set Up as op (up) 2 S.t. Se,, pp(Up)dup
Multi-agent
We denote agent p sampling an action Up E Up from his mixed strategy density as up ~ Gp. Joints: Joint actions, action sets and densities for all represented
(upheer. U = XpEP(Up) and {aph [op)pEP respectively. Coverage: When placed, each resource covers (often probabilistically) some part of the target space Q. Let evgp q
agents together
RR. be function denoting the utility for agent p coming from a target point E Q due to a joint action u for all agents. We do not assume a specific form for the coverage utility cvg, and leave it to be defined flexibly, allow many different coverage applications to be amenable to our framework, Rewards: Due to the joint action u, each player achieves a coverage reward rp- u -> IR of the form ru( So cvg, u) imp,, (g) dg, where imp, denotes the importance of the target point q for agent p. With a joint mixed strategy a, player p achieves expected Objectives: In single-agent settings, the agent would directly optimize his expected utility w.r.t. action up. But in multi-agent settings, the expected utilitics of agents depend on other agents' actions and hence cannot be maximized with deterministic resource allocation due to potential exploitation by other agents. Instead agents aim to achieve Nash equilibrium mixed strategies
utility: Ens [rp] = Sy (u)or(())
(ophpE P over their action spaces. Nash equilibria: A joint mixed strategy o² = {op PEP is said to be a Nash equilibrium if no agent can increase its expected utility by changing its strategy while the other agents stick to their current strategy.
Two-player settings: While our proposed framework is not restricted to the number of agents or utility structure of the game, we will focus on single-player settings and zero-sum two-player games in subsequent examples. An additional concept required by fictitious play in two-player settings is that of a best response. best response agent p against strategy o p is an action which maximizes his expected utility against -pp
bry(a-p) E arg max (Eu-pro-p u-p)]} "y
The expected utility of any best response of agent p is called the exploitability of agent -p:
c-p(o-p) == max (Eu_p=a-,11y (up up)
up
Notably, a Nash equilibrium mixed strategy for each player is also their least exploitable strategy. Example 1 (Single-agent Areal Surveillance). A single agent, namely the defender (D), allocates m areal drones with the tth drone D2 having diree-dimelsoonll coordinates up, = (PD,s, hp.a)
2

---

Under review as a conference paper at ICLR 2021
[-1,1] x 10 surveil a two-dimensionalloree forest Q C [-1,1]² but arbitrary tree density p(g). Consequently, up E Rmmx3, Each drone has a downward looking camera with a circular lens and with half-angle 9 such that position (pp,s, D.))), the drone D, sees the set of points Sp.; = {q q - PD.illa S hpp tan 0). A visualization of this problem with We assume a probabilistic model of coverage Khout
112 of arbitrary shape and with known
m 2 drones is shown for a sample forest in Figure [a
with a point being covered by drone D; with probability (h((D,,) = (K(hutt-Da.. (DD.>) Rope
if q E SD. and otherwise. With multiple drones, the probability of point q being covered can then be written as: cvg(q,up) = IllEES, PH (hD,) where Ph stands for 1 - PH. Hence, the
reward function to be maximized is: TD.Ip(uD) = Sa (1- D.. PH((D.)) plg)dq with the tree density p(q) being the importance of target point (subscript 1p denotes one agent).
Example 2 (Two-agent Adversarial Coverage). Two agents, namely the defender D and the attacker A, compete in zero-sum game. The defender allocates m areal drones with the same coverage model as in example 1. The attacker controls n lumberjacks each with ground coordinates u.A.j E 1 to chop trees in the forest Q. Consequently, u E RR EEach lumberjack chops a constant fraction k of trees in a radius Rr, around its coordinates uA..j We denote the area covered by the j-th {q llq P.. S RL). A visualization of this problem with m is shown for a sample forest in Figure [b] A drone can potentially catch a lumberjack if its field of view overlaps with the chopping area. For given resource allocation = (uD, UA), we define 1 {i llPA. IlPA.--PD..ll S R2 thD tan f as the set of all drones which overlap with the j-th lumberjack. The areal overlap Qij- Jss, (SA.3 dq controls the probability of the j-th lumberjack being caught by the i-th drone: Po(D,, 0ug) = PH (.).)) Pa(au)) where PH is the same as that in example I and captures the effect of drone's 's height on quality of coverage, while Pa(arr)= = 11 exxp
lumberjack
SA.=
2
Kaagy
R.
captures the effect of areal overlap on probability of being caught. Hence, the reward achieved by the j-th lumberjack can be computed as: TA,(UD MA.)) = RR ISaann plq)dq with probability
IIEE, P(hD.i, ass), and -ki Jsa.nQ plq)dq otherwise i.e. the number of trees chopped if the j-th lumberjack is not caught by any drone or equivalent negative penalty if it is caught. Hence, the total agent rewards are: TAA UA) = -TD.2p(Up UA) = E; r TA. (UD, uAs) (subscript 2p denotes two-agent).
Note that in the above examples drones provide best probabilistic coverage at a height hopt- By increasing their height, a larger area can be covered at the cost of deterioration coverage probability. Further, the defender can increase coverage probability for regions with high tree density by placing multiple drones to oversee them; in which case, the drones can potentially stay at higher altitudes too. Example 2 further adds additional interactions due to overlaps between defender and attacker's resource Hence, these examples form a challenging set of evaluation domains with multiple trade-off's and complex possibilities of coverage involving combinatorial interactions between the players' resources. For both examples, we use the following constants: 0 = E. hopp = 0.2, K = 4.0, R2 = 0.1, K. 3.0, K= 0.1. However, note that these values only serve as practical representative values. The techniques that we introduce in this paper are not specific to the above probabilistic capture models specific values of game constants, but rather apply to a broad class of coverage problems where the agents act by placing resources with finite coverage fields and agents' rewards are of the form: (u) = Jq fp q)dq.
Dealing with zero gradients: In the two-agent game, the attacker's reward depends on the locations of its resources, but the defender's 's reward solely depends on overlaps with the attacker's 's resources. In absence of such overlap, the gradient of 2p w.r.t. up becomes O. Hence, we propose use the reward from the one-agent game as an intrinsic reward for the defender similar to how RL algorithms employ intrinsic rewards when extrinsic rewards are sparse (Pathak et al., 2017). Then the reward
function for the defender becomes: En, (uD, u.) = TD22p UA) + pr', 1p (un). We use a small μ = 0.001 to not cause significant deviation from the zero-sum structure of the game and yet provide non-zero gradient to guide the defender's resources in the absence of gradients from DD22p-
In reality, lumberjacks might act independent of each other and lack knowledge of each others' plans. By allowing them to he placed via single attacker and letting them collude, we tackle more challenging problem and ensure that not all of them get caught by independently going strongly covered forest regions.
3

---

Under review as a conference paper at ICLR 2021
(a)
(b)
Figure I: (a) Areal surveillance example with an arbitrary forest and 2 drones, (b) Adversarial coverage example with m = 2 drones and n = 2 lumberjacks (red circles).
METHODS
Solution approaches: The key idea for all solution approaches is to obtain a differentiable approx- imation to the expected utility of the agents and then maximize it w.r.t. the agents' actions (or mixed strategies). For single-agent games, this boils down to performing direct gradient ascent on a differentiable approximation rp(p)), thereby converging a (locally) optimal value of up. For two-agent adversarial games, DeepFP (Kamra et al., 2019b), an actor-critic based approach based on fictitious play be used. Briefly summarized in algorithm T it obtains differentiable approxi- mation to the reward functions ED2 and 4.p creates an empty memory to store a non-parametric representation of the agents' mixed strategies a (ØD, aA) and initializes best responses for both agents randomly [lines 1-3]. Then it alternatively updates: (a) the agents' strategies, by storing the current best responses in the memory [line 5], and (b) the best responses, by maximizing each agent y's differentiable reward function against batch of samples drawn from the other agent's strategy a a-p [lines 6-8]. Details of DeepFP hyperparameters used can be found in section AA6 the appendix. The key component required in both cases is a differentiable approximation to the reward function and we propose a tractable framework for this challenging task in the subsequent sub-sections.
Mitigating sub-optimal local best responses: During our preliminary experiments with DeepFP, we observed that updating best responses using purely gradient- basedd optimization can often get stuck in sub-optimal local optima. While DeepFP maintains stochastic best responses to alleviate this issue, it doesn't climinate it completely. We briefly describe our solution to this issue here (please section A.4 in the appendix for more elaborate discussion the proposed solution). Motivated by Long et al.] (2020). we propose a simple population-banl approach wherein we maintain set of K deterministic best responses br (a-p). for E {D, and vk E [K] During the best response optimization step for agent p [lines 6-8], optimize the K best responses independently and play the one which exploits agent -p the most. After the optimization step, the top K best responses are retained while the bottom half are discarded and freshly initialized with random placements for the next iteration. This allows retention and further refinement of the current best responses over subsequent iterations, while discarding and replacing the ones stuck in sub-optimal local minima.
the issue and details of
3.1 DIFFERENTIABLE APPROXIMATION FOR COVERAGE ORJECTIVES
First, we propose a method to approximate coverage objectives and their gradients w.r.t. agents' actions. Consider an objective of the form:
r(u) = f(u. dq
(1)
where u denotes actions of one or more agents having multiple resources to place at their disposal and q any point in the target domain Q. We assume that the action has m components with u, representing the location of i-th resource (i E [m]) and un representing the locations of all resources other than i. Note that the imp(g) function has been subsumed into fu, q) in this formulation. We are interested in computing the gradient: Fu.
Dr. However, this is a hard problem since: (a) r(u) involves
integration over arbitrary (non-convex shaped) target domains which does not admit a closed-for formm expression in terms of elementary functions and hence cannot be differentiated with autograd libraries
4

---

Under review as a conference paper at ICLR 2021
Algorithm 1: DeepFP
Result: Final strategies dD, σ in mem
Obtain differentiable approximation i = (řD, fA) to the reward functions: (fD.2p. TA22p)) Initialize best responses (brp, br randomly;
Create empty memory mem to store = (oD.
for game E {l...., max_games) do
** Update strategies
Update a by storing best responses fbrp, br in mem;
/+ Update best responses
for agent p & (D, A} do
Draw samples (u' p-iitbs from a-p mem;
b8 br, maX ii Pz (p: u p)
like PyTorch and TensorFlow, and (b) most resources have a finite coverage area, outside of which the coverage drops to zero. This often makes the function f(u, discontinuous w.r.t. given fixed u especially at the coverage boundaries induced by the resources' coordinates, for e.g., drones have a circular probabilistic coverage area governed by their height and camera half- 6, outside which the coverage probability suddenly drops to zero.
Theorem 1. Let the objective function be as shown in eq 7 r(u) - So f(u, q) dg. Denoting the set of points covered by the i-th resource as So, the interior of a set with in(-) and the boundary with 5()), the gradient of r(u) w.r.t the i-th resource's 's location is given by:
Ōr(u)
- Øf(u, 4)
Oqgnas. T
dq+ Janas. (f(u.q) - f(()..9)
Oug
Jitons.)
Ou,
Du,
Ryanss, dq
Proof. While function f can be potentially discontinuous in & across resources' coverage boundaries, r(u) integrates over q Q thereby removing the discontinuities. Hence, instead of directly taking the derivative w.r.t. a particular resource's location u, inside the integral sign, we split the integral into two parts over the i-th resource's 's coverage area S; and outside it:
r(u) = Jans. f(u. 4) dq + -oss. f(u, q) dg
(3)
Splitting the integral at the boundary of the discontinuity allows us to explicitly capture the effect of small change in u, this boundary. Denoting the interior of a with in(-) and the boundary with 5()), the derivative w.r.t. u4 can be expressed using the Newton-Leibniz formula as:
Ōr(u) Ou:
S Imigns.)
Of(u.9) dg + I [ssonss) f(u.9)
0qmenss)) T
Myscons,) dg
Ou,
Du,
Os( dq + [ ISCous)) f(u,,,
QqsiQrs) T Og dg.
Ou:
Ou;
where 0gs(onS)) Bu; normal to a point q on the boundary 8(Q St) (similarly for ((Q), Since f((,,,)) does
denotes the boundary velocity for 8(Q S.) and Mygenss denotes the unit-vector
depend on Ug
set (f(u))))) 0. Next observe that the boundaries
be further decomposed
du; (Q n 55²) and similarly (()).S.) (8Q)..) U (8,55,) However
as: 5(Q n S.) (&Q n S.)
since u; does not change the boundary of the target domain 8Q, we have:
Oqagns O, Vg E 8QQ ns
(5)
Ou:
0qsqus. O, Ag 6Q),S
Du;
Further on the boundary of S, the following vectovectors normal to the boundary are oppositely aligned:
B9 = =-agsgans)) Vg E Q 8S.
(7)
5

---

Under review as a conference paper at ICLR 2021
Substituting the above results, we can simplify the gradient expression in eq to:
ar(w) ou, Jmttnss
af(u. 4) pq + Janas. (f(u.g) - f(un,) aggnes. Ou:
Rygnas, dq (8)
du.
The first term in eq 2 corresponds to the change in inside the coverage area of resource i due to a small change in Uy while the second term elegantly factors-in the effects of movement or shape change of the coverage area boundary due to changes in u, (e.g. when drone moves elevates in 89gné3; T
height). While we show the general result here, the term 8ws Aganas, can be simplified further using implicit differentiation of the boundary of S,, which depends on the particular game under consideration. We show the simplification for our example domains in section A.2 in the appendix.
3.2 DISCRETIZATION BASED APPROXIMATIONS
While we now have general form for r(u) and år both forms comprise of non closed- ou. integrals over the target domain Q its subsets. While evaluating and är in practice, du discretization based approach approximate the integrals. Given target domain Q C Rd with d E (2,3), we discretize the full R space into Bı.... ....... Ba bins respectively in each of the d dimensions. Approximating spatial maps: All spatial maps i.e. functions over the target domain Q (e.g- [u, g)), are internally represented as real lensors of dimension d with size: (BI,... .... Ba). Approximating sets: All geometric shapes (or sets of points) including S; for all resources (e.g.. the circular coverage areas of drones and lumberjacks) and the target domain Q itself (e.g.. the irregular shaped forest) are converted to binary tensors each of dimension d+1 1 with size: (Bi..... Ba. 3). The final dimension of length 3 denotes interior, boundary and exterior of the geometric shape respectively, ie. a binary tensor T has To To.....bs.u shape, To.....bu..I = 1 if the bin is on the boundary of the geometric shape and .u. the bin is outside the geometric shape. Approximating operators: Doing the above discretization requires efficient function for computing the binary lensors associated with the in(-) and the 5()) operators. This is performed by our efficient wyrid--ndd-onquue shape discretizer, which is presented in section AA.3 due to space constraints. The other set operations are approximated as follows: (a) set intersections are performed by dlmenttwwise hinary tensor products, (b) integrals of spatial maps over geometrie sets are approximated by multiplying (i.e. masking) the real tensor corresponding to the spatial map with the binary tensor corresponding the geometric set followed by an across-dimenss sum over the appropriate set of axes.
adopt
if the bin at index (bI...., bu) is inside the geometric if
While our discretized bins growing exponentially with dimension d of the target domain may come off as limitation, our method still scales well for most real-world coverage problems since they reside on two dinee-iimesiionll target domains. Further, unlike previous methods which discretize the target domain and simultancously restrict the agents' actions to discrete bins (Yang et al. 2014 Haskell et al. 2014), we do not discretize the actions u of agents. Hence, we do not run into intractability induced by discretizing high-dimensional actions of agents owning multiple resources and we keep amenable to gradient-based optimization. Our proposed framework acts as an autograd module for r(u), differentiable w.r.t. input u, and provides both the forward and the backward calls (i.e. evaluation and gradients).
4 EXPERIMENTS
In our experiments on both our application domains, we differentiably approximate rewards using the following variants: (a) feedforward neural networks [nn]] (b) graph neural networks [gnn], and (c) and with our differentiable coverage approximation [diff]. For the nn and gnn baselines, we trained neural networks, one per forest and per value of m (and n for two-agent games), to predict the reward of the defender (and attacker in case of two-agent game). The neural networks take as imput the action up of the defender (and u also for two-agent game) and outputs a prediction for the reward i t (fD.2p and AA,p for two-agent game). Please see section A.6 in appendix for network architectures and hyperparameters. We also represent best responses with the following variants: (a) stochastic best response nets [brnet] as originally done by DeepFP, and (b) our deterministic evolutionary population [popK] with K being the population size. We use = 2 dimensional forests and discretize them into B B2 200 bins per dimension for a total of 40K bins.

---

Under review as a conference paper at ICLR 2021
4.1 RESULTS ON AREAL SURVEILLANCE DOMAIN
We maximized differentiable approximations of fp.1p using all three methods: un, gun and diff for different values of m E (1, 2, 4) over different forest instances differing in shape and tree density. The maximum true reward 1D.1p achieved by the three methods in all cases averaged over all the forest insaances is summarized in Table I It is clear that diff always achieves the maximum true reward. While the difference difference from nn and gnn is less pronounced for m 1, as the number of agent resources increases beyond 1, the approximation quality of nı and gun deteriorates and the difference becomes very significant, This is also reflected in the plots of true reward achieved vs training iterations shown in Figure 2 Since diff is unbiased approximator of the true reward" the true reward continues to increase till convergence for diff. For un and gnn, the true reward increases initially but eventually goes down as the defender action u.D begins to overfit the biased and potentially inaccurate approximations made by un and gma Figure showws the final locations computed for randomly chosen forest and with m for all three methods.
Table 1: Maximum reward averaged across forest instances achieved for Areal Surveillance domain.
771 1
m 2
m71 1554.34 25117.98
diff (ours)
9366.03
657.18
16091.09 + 932.77
9293.20 26 + 646.37
14649.32 + 1206.60
18962.87 + 2018.54
gnn
9294.47 + 664.28
14604.11 + 1189.48
19353.93 + 2701.81
15000
999
19000
2000
8000
110003
3000
11000
10003
0.0
14603
30 000339200 290139 82 99045330
0 30 320333300
30 200130300254 29000000888000000000000 4933
(a)
(b)
(c)
Figure 2: Plots of true reward achieved over DeepFP iterations by diff. nn and gmn.
000
015
28
T 85
12 2 as 2065
2008
200
(a) Forest tree density
(b) Action found via diff
(c) Action found via m (d) Action found via gnn
Figure 3: Visualizing final actions for randomly chosen forest with 2.
4.2 RESULTS ON ADVERSARIAL COVERAGE GAME
We implemented different variants DeepFP with variations of differentiable reward models in (nn, gnn, diff') along with variations of best responses in [brnet, pop4). We measured the exploitability Ep of the defender strategy found by all methods to compare them against each other. To compute the exploitability of the defender strategy found by any variant of DeepFP,
froze the defender strategy aD and directly maximized Euprap [f (uD, uAa]] w.r.t. UA with f being approximated by diff. This is single-agent objective and can be directly maximized with gradient ascent. We perform 30 independent maximization runs to avoid reporting local maxima and report the best of them as the exploitability, Note that nash equilibrium strategies the least exploitable strategies, hence the lower the value of Ep(ap) found, the closer op is to the nash equilibrium strategy.
"The only hias in diff is the discretization bin sizes, which can be made arbitrarily small in principle. Please section A.1 in the appendix for detailed analysis of this phenomenon.
7

---

Under review as a conference paper at ICLR 2021
Table 2 shows the exploitability values for different variants of DeepFP. We observe that the ex- ploitability when best responses are approximated by a population- always lower than that of stochastic best response networks employed by original DeepFP. Further, with few agent resources m = n 1, the exploitability across diff, nn and gun is nearly similar but the disparity increases for larger number of agent resources and diff dominates over mn and gnn with less exploitable defender strategies. Notably, the original DeepFP (nn + brnet) is heavily exploitable while our proposed variant (diff + popK) is the least exploitable. In Figure 4 we show visualization of the points sampled from the defender and attacker's ' strategies for m n = 2 case on the same forest from Figure Bal The visualization confirms that diff + popk covers the dense core of the forest with the defender's drones so the attacking lumberjacks attack only the regions surrounding the dense core, while an + brnnt drones often gets stuck and concentrated in a small region thereby allowing lumberjacks to exploit the remaining dense forest. Please also see section A.5 in the appendix exploring the trade-offs in the choice of population size K.
variant with K = is
Table 2: Exploitability of the defender averaged across forest instances.
<D(OD)
4
brnet
diff (ours)
209.78 49.94
399.95 57.70
559.36
164.21 787.53 = 194.82
an
203.92 = 54.67
323.00 = 39.55
gnn
204.55 = 50.72
307.74 = 62.67
597.23 - 125.01
pop4 (ours)
diff (ours)
116.41 + 15.02
141.09 = 13,90
141.54 + 26.60
nn
113.61 + 6.92
208. 23 22.76
339.31 + 116.77
gnn
113.99 + 13.74
176.25 + 15.21
172.30 + 34.08
24
24
1-48 18.33
(a) Strategy for diff' + brnet (b) Strategy for nn + brnet (c) Strategy for gnn + brnet
10
13
66
26
68
14
24
05
32
20
18 Forh Plari
(d) Strategy for diff' + pop4 (e) Strategy for nn + pup4 (l) Strategy for gan pop4
Figure 4: Visualizing final strategies found via diff. nn and gan with best responses of the form brnet and pop4 on randomly chosen forest with
2. The blue (red) dots sampled from the defender's 's (attacker's ') strategy for the 2 drones (lumberjacks).
CONCLUSION
In this work, we show that spatial coverage objectives with multiple-resouress are combinatorially hard to approximate with neural networks. We propose to directly approximate a large class of multi- agent multi multi-resource spatial coverage objectives and their gradients tractably without learning neural network based reward models. By augmenting existing approaches with spatial discretization based approximation framework, we show improved performance in both single-agent and adversarial two-agent multi-resource spatial coverage problems.
8

---

Under review as a conference paper at ICLR 2021
REFERENCES
Kareem Amin, Satinder Singh, and Michael P Wellman. Gradient methods for stackelberg security games. In UAI, pp. 2-11, 2016.
Peter Battaglia, Jessica B Hamrick, Victor Bapst, Alvaro Sanchez-Gonzalez, Vinicius Zambaldi, Mateusz Malinowski, Andrea Tacchetti, David Raposo, Adam Santoro, Ryan Faulkner, et al. Relational inductive biases, deep learning, and graph networks. arXiv preprint arXiv:1806.01261, 2018.
Soheil Behnezhad, Mahsa Derakhshan, Mohammadtaghi Hajiaghayi. and Saced Seddighin. Spatio- temporal games beyond one dimension. Proceedings of the 2018 ACM Conference on Economics and Computation, pp. 411-428, 2018.
Alireza Dirafzoon, Mohammad Bagher Menhaj, and Ahmad Afshar. Decentralized coverage control for multi-agent systems with nonlinear dynamics. IEICE TRANSACTIONS on Information and Systems, 1-0,, 2011.
Jiarui Gan, Bo An, Yevgeniy Vorobeychik, and Brian Gauch. Security games on a plane. In AAAI, pp. 5-0-5330---6 2017.
William Haskell, Debarun Kar, Fei Fang, Milind Tambe, Sam Cheung, and Elizabeth Denicola. Robust protection of fisheries with compass. In IAAI, 2014.
Andrew Howard, Maja J Matarić, and Gaurav S Sukhatme. Mobile sensor network deployment using potential fields: A distributed, scalable solution the area coverage problem. In Distributed Autonomous Robotic Systems 5, pp. 299-308. Springer, 2002.
Taoan Huang, Weiran Shen, David Zeng. Tianyu Gu, Rohit Singh, and Fei Fang. Green security game with community engagement. arXiv preprint arXiv:2002.09126 09126, 2020.
Matthew P. Johnson, Fei Fang, and Milind Tambe. Patrol strategies to maximize pristine forest area. In AAAI, 2012.
Nitin Kamra, Umang Gupta, Fei Fang, Yan Liu, and Milind Tambe. Policy learning for continuous space security games using neural networks. In AAAI, 2018.
Nitin Kamra, Umang Gupta, Kai Wang, Fei Fang, Yan Liu, and Milind Tambe. Deep fictitious play for games with continuous action spaces, In Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2019a.
Nitin Kamra, Umang Gupta, Kai Wang, Fei Fang. Yan Liu, and Milind Tambe. Deepfp for finding nash equilibrium in continuous action spaces. In Decision and Game Theory for Security (GameSec), pp. 238-258. Springer International Publishing, 2019b.
Christopher Kickintveld, Manish Jain, Jason Tsai, James Pita, Fernando Ordóñez,, and Milind Tambe. Computing optimal randomized resource allocations for massive security games. In AAMAS, pp. 689 696, 2009.
Chan Sze Kong. New Ai Peng, and Ioannis Rekleitis. Distributed coverage with multi-robot system. In Proceedings 2006 IEEE International Conference Robotics and Automation, 2006. ICRA 2006., pp. 2429. IEEE, 2006.
Mare Lanctot, Vinicius Zambaldi, Audrunas Gruslys, Angeliki Lazaridou, Karl Tuyls, Julien Pérolat, David Silver, and Thore Graepel. unified game-theoretic approach to multiagent reinforcement learning. In Advances in Neural Information Processing Systems, pp. 4190-4203, 2017.
Qian Long, Zihan Zhou, Abhibav Gupta, Fei Fang, Yi Wu, and Xiaolong Wang. Evolutionary popula- tion curriculum for scaling multi-agent reinforcement learning. arXiv preprint arXiv:2003. 10423, 2020.
Ryan Lowe, Yi Wu, Aviv Tamar, Jean Harb, OpenAl Pieter Abbeel, and Igor Mordatch. Multi-agent actor-critic for mixed eeseeratvv-compttttii environments. In Advances in Neural Information Processing Systems, pp. 6379 6390, 2017.

---

Under review as a conference paper at ICLR 2021
Ali Nasri Nazif, Alireza Davoodi, and Philippe Pasquier. Multi-agent coverage using single query roadmap: A swarm intelligence approach. Advances in practical systems, pp. 95-112. Springer, 2010.
Deepak Pathak, Pulkit Agrawal, Alexei A Efros, and Trevor Darrell. Curiosity-driven exploration by self-supervised prediction. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition Workshops, pp. 16-17, 2017.
Huy Xuan Pham, Hung Manh La, David Feil-Seifer, and Aria Nefian. Cooperative and distributed reinforcement learning of drones for field coverage. arXiv preprint arXiv: 1803.00200 2018.
Alessandro Renzaglia, Lefteris Doitsidis, Agostino Martinelli, and Elias B Kosmatopoulos. Multi- robot three-dimensional coverage of unknown areas. The International Journal of Robotics Research, 31(6):738-755 2012.
Martin Saska, Jan Chudoba, Libor Pfeučil, Justin Thomas, Giuseppe Loianno, Adam Třešñák, Vojtéch Vonásek, and Vijay Kumar. Autonomous deployment of swarms of micro-aerial vehicles in cooperative surveillance. In 2014 International Conference on Unmanned Aircraft Systems (ICUAS), pp. 584-595. IEEE, 2014.
Milind Tambe. Security and Game Theory: Algorithms, Deployed Systems, Lessons Learned. Cambridge University Press, New York, NY, 2011.
Yufei Wang, Zheyuan Ryan Shi, Lantao Yu, Yi Wu, Rohit Singh, Lucas Joppa, and Fei Fang. Deep reinforcement learning for green security games with real-time information. In Proceedings the AAAI Conference on Artificial Intelligence, volume 33, pp. 1401-1408, 2019.
Rong Yang, Benjamin Ford, Milind Tambe, and Andrew Lemieux. Adaptive resource allocation for wildlife protection against illegal poachers. AAMAS, 2014.
10


Reviews:
[{"review_id": "y2tyZFxrmz3", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "##########################################################################\nSummary:\n \nThis paper studies the (multi-)agent spatial coverage problem. They propose a framework that can approximate the general class of spatial coverage objectives and their gradients via spatial discretization methods.  \n\n##########################################################################\nReasons for score: \nThe contribution of this paper seems trivial, it is a refinement of training DeepFP [Kamra 2019] by deriving a differentiable loss function. The comparisons to existing baselines are missing. I therefore recommend for rejection.\n\n \n##########################################################################\nPros: \n \n1. This paper studies a specific problem of resource allocation problem in a continuous setting. I appreciate two detailed examples of problem formulation for both single-agent and multi-agent settings. \n\n2. The main contribution of this paper is the loss function derivative in Theorem 1, which mainly uses classical calculus.\n \n##########################################################################\nCons: \n \n1.\tThe author believes discretization the continuous domain is not a good way to solve resource allocation problem. However, the proposed method still have to adopte the discretization on computing the integral of r and \\partial r/u. Although the author emphasise that they do not need to discretize the action domain, but it seems to me that why it is significant is unclear. \n\n2. The author mentioned that model-free methods such as PSRO, has the issue of low sample efficiency and high variance issue for policy gradient methods, however, both of which has not been addressed by this work, and this proposed method is not compared to model-free method either. PSRO and its variants, for example, have shown many success on blotto type of game, so I think the advantages over PSRO [Lanctot 2017] type of methods need clarifying. I would consider improving the score if author can show comparative advantage over PSRO.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "xVjlO-Dwcd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 1, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper shows that spatial coverage objectives with multiple-resources are combinatorially hard to approximate with neural networks and proposes a spatial discretization based approximation framework to solve this problem. \n\nThe paper is very hard to follow due to all the notations the authors introduced and the details set up in the examples. Many details in the two examples look a little bit extra, which could be properly abstracted. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Bjdo5kXH7Xh", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "The main goal of this paper is to address the problem of multi resource spatial coverage.\nThe main challenges are the non differentiability of the utility function and the complexity of the action space making this problem hard to optimize.\nThe authors make a clear review of the state of the art approaches that often focus discretizing the action space. In the contrary, the authors propose to discretize the target space to construct a differentiable approximation of the utility function.\n\nI'm really not an expert on multi resource spatial coverage, so I am not able to judge if the presented results are original, nor significant.\n\nHowever, I found the paper clearly written, and the subject nicely presented with examples.\n\nI suggest a few points of improvement:\n- Part of the conclusion and the abstract mention that the paper proved that \"multiple-ressources are combinatorially hard to approximate with neural networks\". I didn't see proofs of that statement, I agree that the authors develop an approach that doesn't seem to suit NN and they outperform a few NN. This can be enough to show that the presented method is efficient but it is not enough to claim that the compared methods are not. \n- I read appendix A1, and I still do not understand why the NN curves, why do they have biases ?\n- In table 1 and 2, it would be great to indicate how confidence intervals are computed.\n\n\n----- Edit after rebutal ------\n\nThank you for the answers.\nThe authors only answered partly my concerns. I'm still not convinced by their explanation on the NN curves. I don't understand how their performance decreases with the number of iterations, it seems that they weren't well tuned.\n\nAnyway I've been convinced by R4 and R1 that a few baseline models are missing.", "extra_scores": {}, "extra_text": {}}, {"review_id": "5SeazvYKjAv", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "##########################################################################\nSummary:\nThis paper studies the coverage game where agents allocate their resources to target spaces to maximize their coverage, and the goal of this paper is to (approximately) compute the Nash Equilibrium. The proposed method simulates the game by iteratively updating the best response, and the main contribution is an algorithm to approximate the gradient of the utility function with respect to the resource allocation (over the space). In particular, the paper proposes to decompose the gradient into two parts and estimate each part by discretization. \n\n##########################################################################\nWhile the paper presents a viable method, I vote for reject for several reasons. The paper does not successfully justify the merits of the proposed method, with many hidden parts that are hard to follow. The paper lacks a good organization, and the writing could have been more formal (see detailed comments). The experiments are not convincing.\n##########################################################################\n\nDetailed comments:\n\nFirst of all, I am slightly concerned that this paper's work does not really fit ICLR, as its goal is to approximate the Nash Equilibrium of a game, without any learning process involved. The only part I see relevant is that two learning-based methods were adopted as competitors.  \n\nThe presentation of this paper lacks clarity and a good structure. I could not figure out the problem this paper wants to solve after reading the first three pages. The abstract and the introduction claim that the paper wants to solve the resource allocation problem, but it turns out the specific target is to approximate the gradient. \n\nFrom my view, using the proposed decomposition is a doable method, but I cannot see the novelty in doing so. The paper mentions some hardness to be overcome: (a) the integration has no closed-form and (b) the coverage drops to zero outside the coverage area. However, the paper does not justify how the aimed hardness was addressed by the proposed method. \n\nThe paper mentions some existing methods (such as DeepPF in a published paper) but does not take them as competitors. I am also confused that the paper names the proposed method also as DeepPF, so how does it compare to the existing DeepPF?\n\nIt looks like the competitors in experiments are baselines without much calibration. The information in the appendix does not provide sufficient details. In addition, instead of providing code in the appendix, it could better to include source files and datasets in the supplementary materials. The currently provided information does not support reproducibility. \n\n\nThe organization and writing of this paper could be improved – e.g.,\n-\tPlease specify the domain when introducing a variable.\n-\tThe definition U=\\times_{p \\in P} {U_p} is problematic – {U_p} is wired since U_p is already a set.\n-\tThe definition cvg: q \\times u -> R is problematic – it should be cvg: Q \\times u -> R\n-\tInstead of saying the agents aim to achieve Nash equilibrium, it would be better to say the game will reach the Nash equilibrium. In addition, is the Nash equilibrium unique? \n-\t“for e.g.” is not correct.\n\n\n\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers agreed that there were a few issues with the current version of this work, mainly:

- Some missing baselines that are mentioned in the paper, but not sufficiently compared to

- Problems with the presentation that did not make it easy to understand.

- Not an optimal fit with the intended audience of this conference.



Decision: Reject