Many multi-robot decision-making problems can be formulated as combinatorial optimization problems, among which the objectives in some problems (e.g., mutual information [1], area explored, number of targets tracked [2], detection probability [3] etc.) have diminishing returns property i.e., submodularity. Intuitively, submodularity formalizes the notion that adding more robots to a larger multi-robot team cannot yield a smaller marginal gain in the objective than adding the same robot to a smaller team.
If the submodular objective is known and fixed, the multirobot decision-making problem boils down to a submodular maximization problem, which is NP-hard but can be solved with an (1 -1 e )-approximation by the greedy algorithm [4]. However, in practice, there are several parameters that affect the objective function that may not be known exactly. Consider the following illustrative example of a vehicle routing problem shown in Figure 2. Here, a team of Un- manned Ground Vehicles (UGVs) are tasked with servicing a set of requests that appear throughout the environment. We have a set of candidate routes of which we must select one for each UGV. The objective is to maximize the number of requests serviced. If a request location lies on more than one UGVs path (the paths may overlap as the UGVs move on a road network), it only counts once in the objective function. Thus, the objective function is a coverage function, which is a special case of the submodular function.
If we know the location of the requests, then we can solve this problem greedily to obtain a (1 -1 e )-approximation. The greedy algorithm requires the capability to compute the objective function f (S). However, there are many scenarios where we may not know where the requests show up and as such not know f (S). For example, the requests could correspond to Unmanned Aerial Vehicles (UAVs) that are carrying out persistent monitoring missions that land when out of charge so as to be recharged by mobile recharging stations [5]- [10]. Here, even if we know the routes followed by each UAV, we may not know their exact landing locations since the energy consumption is stochastic [9], [10] and communication between UAVs and UGVs is not available (e.g., due to stealth). In such cases, we may be able to predict f (S) using all the available information. We call the latter as context z, which can include the routes of the UAVs, the environmental conditions including the wind conditions, etc.
The traditional pipeline here would be to use the context information and predict f (S) and then solve the downstream UGV route selection problem, argmax S f (S), using this predicted f (S). However, as the following example shows a good predictor of f (S) does not necessarily align with making good decisions on the downstream task. On the other hand, a predictor that does not necessarily yield the best predictions of f (S) may still yield the best decisions for the downstream argmax S f (S) problem.
We present an illustrative example of such misalignment in Fig. 3. Let f 1 , f 2 be two coverage functions (coverage function is submodular by definition) defined over set {s 1 , s 2 , s 3 }. Given a subset S ⊆ {s 1 , s 2 , s 3 }, f i (S), i = 1, 2 will return the area covered by the selection. The submodular objective that we are interested in is defined as 1], which is also submodular by definition. Suppose that we want to maximize f β with a partition matroid:
Then the optimal solution is either {s 1 , s 2 } or {s 1 , s 3 }. In Fig. 3c, we show how the optimal decision changes w.r.t. β. When β ≥ 0.358, the optimal decision is {s 1 , s 3 } since f β ({s 1 , s 3 }) ≥ f β ({s 1 , s 2 }) (the blue line is above the red line). By contrast, when β < 0.358, the optimal decision is {s 1 , s 2 }. Next, let us look at the learning problem for f β . We want to find a mapping from the observation z to β. In Fig. 3d, we show the training data sampled from the ground truth and the optimal decision boundary z * = 0.8988, which is obtained by finding the intersection between the ground truth curve and β = 0.358. If we use Mean Square Error (MSE) as the objective for learning without considering the downstream task, we will get two lines as shown in Fig. 3e. The decision boundary (dashed vertical red line, z * = 1.34, passing the intersection of the learned red line and β = 0.358) is on the right of the optimal boundary, thus not optimal. By contrast, if we consider the downstream optimization, we will get two lines as shown in Fig. 3f and the decision boundary (dashed vertical blue line, z * = 1.02, passing the intersection of the learned blue line and β = 0.358) is closer to the optimal boundary, thus reducing the regions of suboptimal decisions. Such an observation motivates us to incorporate the decision process (submodular maximization) into the learning process.
To this end, we propose a Decision-Oriented-Learning (DOL) framework for learning context-aware parameterized submodular objectives. We focus on submodular functions that can be parameterized, i.e., f (S, w), where the parameters are to be learned from the context. As described earlier and pointed out in [11]- [13], the best estimator of w does not necessarily yield the best decisions for the downstream task. Instead, in the proposed framework, the decisionmaking problem (submodular maximization) is treated as a differentiable layer that takes as input the output from the prediction module as shown in Fig. 1. The prediction module takes as input a context observation z and predicts w, i.e., the parameterized submodular function. By using a differentiable submodular optimization layer, we can train the prediction module using the loss from the downstream task, thereby yielding aligned predictions.
In summary, the main contribution is this paper is:
• We propose a decision-oriented learning framework for mobile charging routing problems. We show how to formulate the learning problem for mobile charging routing and how to solve it. • We demonstrate the effectiveness of our framework in several examples through simulation. The rest of the paper is organized as follows. We first give a brief overview of the related work in Section II. Then, we explain the problem setup and formulation in Section III. We introduce the learning algorithm in Section V and validate the formulation and the proposed framework in Section VI.
Most existing multi-robot decision-making work consider the case where the optimization objective is well-defined and known. Wilde et al. [14] consider the case where the optimization objective is hard to quantitatively specify and may be subjective and proposed an interactive learning framework to learn the objectives. Our work shares a similar stance with [14] but differs in two aspects. First, we consider the fact that the task objective may change in different contexts, for example in different weather conditions, and aim at learning a context-aware objective. Second, our learning framework integrates the downstream decision-making process into the learning process.
Another line of research related to this work is decisionoriented learning. The key idea is to embed the decisionmaking problem as a differentiable layer in the learning pipelines. The main advantage is that it allows end-to-end training and reduces the engineering efforts to design some intermediate learning objectives. Such an idea was initially explored for continuous optimization problems [15], [16] and has gained popularity in control and robotics [17]- [20]. The idea was later extended to the combinatorial problems [12], [13], [21], [22]. Our work is inspired by [12], [21] and our framework integrates the decision-making process for mobile charging station routing, which is modeled as submodular maximization, into the learning process.
This work is also closely related to differentiable submodular maximization. Submodular maximization and its variants have been widely used in multi-robot decisionmaking problems including coverage, target tracking, exploration, and information gathering. These studies are all based on the fact that the greedy algorithm and its variants can solve submodular maximization problems its variants efficiently with a provable performance guarantee. Since the submodular objective and greedy algorithm are tightly coupled, it is better to take into account the influence of the greedy algorithm when we consider learning submodular functions [23]. To this end, several differentiable versions of the greedy algorithms have been proposed [23], [24]. The core idea behind these algorithms is stochastic smoothing, i.e., perturb the algorithm by introducing some probability distribution in the intermediate steps. Our framework is built on these differentiable greedy algorithms but is targeted specifically for context-dependent routing problems.
In this section, we first introduce the formulation of the learning problem. Then, we explain the setup of the case study and the parameterization of the objective.
We are interested in parameterized submodular objective function f (S, w), where w is the parameter vector. Readers are referred to [14] for a formal definition. In practice, such an objective is usually unknown and contextdependent, i.e., the parameters w ∈ W depend on the environment features. Our goal is to learn a function g θ : Z → W that maps the context observation z ∈ Z to the objective parameters w. Traditionally, finding the mapping g θ and optimizing the downstream objective f (S, w) are considered separately: given the training data D = {(z 1 , w 1 ), (z 2 , 2 ), . . . , (z |D| , w |D| )}, first find the mapping g θ by optimizing over θ in a supervised fashion, and then use the parameter w = g θ (z) to optimize f (S, w).
By contrast, the proposed paradigm that integrates downstream optimization is given below.
where S * (w i ) denotes the solution of (5) returned by some approximation algorithms with w = w i ; f (S * (w i ), w i ) denotes the decision quality when we use the ground truth parameter w i for decisions; f ( Ŝ, w i ) denotes the decision quality when we use the predicted parameter ŵi for decisions, i.e., use ŵi to obtain the decision Ŝ, but the decision is evaluated w.r.t. the true parameter w i .
The intuition for Eq. ( 3) is that we want to minimize the gap between the decision quality of the true parameters and that of the predicted parameters. One challenge is when we use the chain rule to compute the gradient of the loss function, we need to differentiate through the optimization problem (the first term on the r.h.s. of Eq. ( 4)) as shown in the illustrative computational graph in Fig. 1.
In the following sections, we will show how to approximately compute the first term on the r.h.s. of Eq. (4).
Suppose that there is a set of candidate routes, T , each of which starts and terminates at the same depot. Our goal is to select a subset from T for UGVs to traverse and recharge the UAV along the way such that the total number of UAVs that UGVs will recharge is maximized.
Environment Model: As shown in Fig. 2, the working environment is described by an area E ⊆ R 2 . There are n a UAVs that are executing persistent monitoring. The energy consumption of UAVs will be affected by the wind. The wind field is represented as a tuple (ω s , ω o ), where ω s and ω o denote the description vectors for the speed and the orientation of the wind, respectively. There are n g UGVs in E, denoted by the set {1, . . . , n g }.
UAV Behavior: There are three components defining the behavior of each UAV. The first one is the task route, which is defined as a sequence of ordered locations projected on the ground, and the UAV will persistently monitor these locations. The UAV will fly at a fixed speed v a between two task locations and its energy consumption will be affected by the wind. The second component is the recharging strategy dealing with the depletion of the battery. The third component is the energy consumption model. We use the same model as that in [25].
Context Observation: Each observation z consists of two components: the task routes of all UAVs; and the wind field (ω s , ω o ) of the working area.
If such submodular objective f is known, the problem boils down to a submodular maximization problem with a matroid constraint: let T be set of all candidate routes, the problem is to select a subset from T to maximize the objective, i.e., max
where w denotes the parameters in the objective function.
Parameterization of the Objective Function In general, such applications have no closed-form expression of the objective function. In this paper, we consider the case where the objective function f is the linear combination of a set of basis functions. Such parameterization techniques are commonly used in the literature on learning submodular functions [3], [14], [26]. Similar to [14], we assume without loss of generality that each basis function is characterized by a subset W i ⊆ V . That is, for any W i , let ψ i (S) be a count of how many vertices of the tours S lie in W i , then f i is a functional of ψ i (S).
The overall objective function is:
where w = [w i,j ] denotes the matrix of unknown parameters of the function; basis functions are defined as f i,j (S) = ψi(S) α=1 γ (α-1) j
; and γ j ∈ (0, 1] comes from a known set Γ.
In this section, we describe the stochastic techniques to smoothe the greedy algorithm for submodular maximization and how can we apply the result to our framework. The key idea is: by introducing proper stochastic perturbances into combinatorial optimization, the expected output as a function of its parameters can be smoothed and differentiable.
The Smoothed Greedy (SG) algorithm is given in Algorithm 1, which was first proposed in [24]. For a given w ∈ W, In each iteration step, we compute marginal gain f S (u, w) for each candidate element u ∈ U k (line 3); we define
denote the marginal gain vector. The probability vector, p k (w) = (p k (u 1 , w), . . . , p k (u n k , w)), is computed as:
Algorithm 1: Smoothed Greedy Input : f (S, w) and independent set I Output: Set S of tours for each robot 1 S ← ∅ 2 for k ← 1 to N do // find all addable elements in the current round
Next, we will show the theoretical results for Algorithm 1. Detailed explanations and proofs can be found in [24]. Let δ ≥ 0 be a constant that satisfies δ ≥ Ω k (p) -Ω k (q) for all k = 1, . . . , |S| and p, q ∈ ∆ n k . We will use δ to quantify the performance of SG.
As shown in Theorem 1 in [24], in expectation, the output of SG satisfies that E [f (S, w)] ≥ (1 -1 e )f (OP T, w)δn g , where OP T denotes the optimal solution. This result suggests that the SG algorithm in expectation almost preserves the performance of the deterministic greedy algorithm, whose approximation factor is (1 -1
e ), with one extra term δn g , which is the price for differentiability. It should be noted that by using SG, the output is stochastic and we focus on the expected result of the output. The regularization functions Ω k are chosen to guarantee the expected outputs of SG differentiable. Examples for Ω k will be discussed in the Sec. VI.
Let O I be the set of all possible solutions returned by SG. Let p(S, w) ∈ [0, 1] be the probability for S ∈ O I . Specifically, for a returned sequence S = {s 1 , . . . , s |S| } ∈ O I , the associated probability can be computed as p(S, w)
Next, we will show how to construct a gradient estimator based on the output distribution. Let Q(S) be any scalar-or vector-valued function. We want to compute ∇ w E S∼p(w) [Q(S)] = S∈O I Q(S)∇ w p(S, w). Since the size of the independent set will increase exponentially w.r.t. the size of the ground set, it is computationally expensive to compute this gradient exactly. Instead, we will use the following unbiased estimator for the gradient in training.
As shown in Proposition 1 in [24], let S j = (s 1 , . . . , s |Sj | ) ∼ p(w)(j = 1, . . . , N ) be outputs of SG.
Then,
is an unbiased estimator of ∇ w E S∼p(w) [Q(S)], where ⊗ denotes the outer product.
For the i-th training sample (z i , w i ), the associated cost w.r.t. θ is redefined for SG as:
where ŵi = g(z i , θ).
For a training set with batch size M , we are interested in minimizing the empirical objective function 1 M M i=1 ℓ i , where p( ŵ) is the output distribution of SG and ℓ i is defined in Eq. ( 9).
We compute the gradient using the chain rule:
where ŵ = g(z i , θ). Suppose we take N trials of SG, by setting Q( Ŝ) = f ( Ŝ, w i ) in Eq. ( 8), we have: r.h.s. of (10)
where ŵi = g(z i , θ).
Then, the remaining problem is how to compute ∇ ŵi ln p( Ŝj , ŵi ) for a given sample Ŝj = (s 1 , . . . , s | Ŝj | ) returned by SG. It should be noticed that ∇ ŵi ln p( Ŝj , ŵi ) = ∇ ŵi ln
, where p(s k , ŵi ) can be obtained when we run the SG algorithm. Therefore, we just need to compute ∇ ŵi p(s k , ŵi ). Let p k ( ŵi ) be the probability returned by Eq. ( 7) at the step k corresponding to the sample Ŝj . By using the chain rule,
the row in ∇ ŵi p k ( ŵi ) corresponding to s k will give ∇ ŵi p(s k , ŵi ). The first term on the r.h.s. of Eq. ( 12) can be computed using auto-differentiation tools [16] (the objective in ( 7) is strictly concave) and the second term can be computed by differentiating the parameterized submodular objective. We can then use the above result to compute the gradient of a batch and update the parameters θ using the stochastic gradient descent method.
VI. EXPERIMENTS UAV and UGV Behavior: In this case study, we consider the case that the task route is defined as a sequence of ordered locations uniformly sampled from a circle whose center is [C x , C y ] and radius is r. Using this geometric information, each route can be represented as a vector C x , C y , r. As for the recharging strategy, we use a simple strategy in the simulation: whenever the state of charge drops below 30%, fly to the nearest recharging location waiting for the UGVs. We use the same energy model as that in [25]. We generate UGV routes by first randomly selecting a set of nodes and then solving a Traveling Salesman Problem to get a route. Context Input z and mapping g θ (z): As shown in Fig. 1, each z consists of two components: the task routes of all UAVs and the wind field vector [a, b, ω o ] of the working area. Since the route of the UAV can be parameterized by a circle (C x , C y , r), z can be represented as
n k and ϵ > 0 is an arbitrary constant, δ can be set to ϵ ln n k . For the road graph G = (V, E), we use graph partition algorithms to generate nine sets of nodes, i.e., {W 1 , . . . , W 9 }. For each partition W i ⊂ V , we define three basis functions for decay parameters γ ∈ {0.001, 0.5, 1}.
2) Generate Training Data: Raw Data: Based on the UAV UGV behavior models, we build a simulator for the routing problems. Given simulation parameters (e.g., UAV routes, and wind conditions), it will simulate UAVs' execution of persistent tasks. If we provide several selected routes to the simulator, it will return the number of UAVs recharged if UGV follows these routes. Based on this simulator, for each context observation z, we test multiple possible route selections and obtain a set of the actual number of UAVs that UGV recharged. We will use this raw data to obtain the training data.
To train the decision-oriented framework proposed in Sec. III, we need the i-th data point to be in the form (z i , w i ), where z i denotes the context input and w i is the corresponding parameter vector of the objective function. However, w i is not directly available and we need to do some pre-processing of the raw data. Specifically, for each z, we have a set of values for different selections, i.e., F = {f (S 1 ), . . . , f (S |F | )}. We find the corresponding w by solving the following regularized least square optimization problem [26], i.e., min w≥0
, where ξ is a user-specified regularization parameter. 3) Results: Fig. 4 shows the learning curves over epochs. In each epoch, we compute the gradient by sampling a batch size of 40 in each iteration. We can see that as the training epoch increases, the loss will gradually decrease to a steady value. It should be noticed that the loss here represents the solution quality gap between the solution obtained using ground truth parameters and the solution obtained using predicted param- eters as defined in Problem 1. Therefore, such a decrease suggests that the decision quality is improving.
After training, we test the performance of the learned models using the simulator. We generate a set of context observations {z i } test and compute the corresponding predicted weights { ŵi } test . Then, we use { ŵi } test to select routes and feed the route to the simulator to obtain the actual number of UAVs recharged. The result is shown in Table VI-.2. We compare three approaches: DOL (our), two-stage (classic supervise learning with MSE loss), and random (select routes randomly without any learning ). As shown in Table VI-.2, our approach on average can result in better route selection and recharge more UAVs.
We propose a decision-oriented learning framework for mobile charging routing problems. We first show how to formulate the learning problem in the context of mobile charging routing. Then, we show how to make submodular maximization a differentiable layer by using stochastic smoothing techniques. The proposed framework and formulation are validated through several case studies.