{'fraction_non_alphanumeric': 0.041950437818348306, 'fraction_numerical': 0.010129914725576604, 'mean_word_length': 4.219086021505376, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 2, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 22, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Learning Submodular Objectives for Team Environmental Monitoring

In this paper, we study the well-known team orienteering problem where a fleet of robots collects rewards by visiting locations. Usually, the rewards are assumed to be known to the robots; however, in applications such as environmental monitoring or scene reconstruction, the rewards are often subjective and specifying them is challenging. We propose a framework to learn the unknown preferences of the user by presenting alternative solutions to them, and the user provides a ranking on the proposed alternative solutions. We consider the two cases for the user: 1) a deterministic user which provides the optimal ranking for the alternative solutions, and 2) a noisy user which provides the optimal ranking according to an unknown probability distribution. For the deterministic user we propose a framework to minimize a bound on the maximum deviation from the optimal solution, namely regret. We adapt the approach to capture the noisy user and minimize the expected regret. Finally, we demonstrate the importance of learning user preferences and the performance of the proposed methods in an extensive set of experimental results using real world datasets for environmental monitoring problems.


I. INTRODUCTION
Autonomous multi-robots systems find wide-spread acceptance in an increasing number of applications such as persistent monitoring, environmental data collection, shared autonomy and scene reconstruction. A key challenge remains the design of frameworks that allow users who are not robotic experts to deploy them effectively and efficiently.
We study a generalized version of the well known Team-Orienteering Problem (TOP) [1] where a fleet of robot has to visit multiple locations in the environment. Upon visit, the respective robot collects a reward and the objective is to maximize the total reward collected by the fleet, subject to constraints on the robots' maximum travel distance. Multiple variants have been studied, including uncertainty [2], [3], and complex reward functions modelling correlations [4] and diminishing returns [5].
In some applications, such as servicing tasks or delivery, the reward is directly given, e.g., as a monetary value. However, in other applications the reward can be difficult to quantify and might be user dependent. For example, in environmental monitoring, scientists may have differing opinions on the importance of gaining information in a certain region. Often the user can indicate regions of interest that the robots should visit. Yet, defining numerical values for a reward function to prioritize between regions is challenging. This is further enhanced when the reward exhibits a diminishing return property: Additional visits of the same region have decreasing additional value. Thus, defining reward functions becomes impractical, especially when the user is not a robotics expert. In human-robot interaction (HRI) the problem of defining reward functions is known as reward design. To reduce the complexity and thus enable a broader range of users to deploy autonomous robots, researchers have studied different frameworks for reward learning [6]- [17]. In contrast to designing parameters of a reward function, users interact with the robot via modalities such as demonstrations, corrections, critique, or choice feedback.
We apply learning from choice to enable users to specify complex submodular reward functions for GTOP and present new solution techniques that are able to handle the high number of dimensions often encountered in these problems. In our framework the robot fleet is given a set of areas of interest. Over multiple iterations, the user is (virtually) presented with two different sets of tours for the robot fleet; they then choose the preferred option. Using a finite set of submodular basis functions, the user's choice allows the robot fleet to estimate the user reward function. Figure 1 illustrates an example for environmental data collection. The regions of interest are protected areas along a coastline. Without designing or learning a reward function, the robots prioritize them equally (a). Learning from choice feedback allows the robot fleet to identify which regions are most relevant to the user and finds better tours (b).
Contributions: In this paper we make the following contributions: (1) We design submodular basis functions to describe rewards for the generalized team orienteering problem. (2) We propose a novel heuristic policy for active preference learning that can handle a high number of basis functions. (3) To handle uncertainty in the user feedback, we present a novel framework that casts this probabilistic problem to a distribution over instances with noiseless feedback, allowing for efficient learning under uncertainty. (4) Finally, we demonstrate the practicality of the approach in simulation using real-world locations for environmental data collection.
Related Work: We address the challenge of defining reward functions for generalized team-orienteering problems and propose an interactive learning framework. Similarly, researchers in HRI study the design of interactive frameworks that allow inexperienced users to define reward functions for autonomous robots in a wide range of applications. Since classical approaches such as learning from demonstrations are not always suitable, alternative modes of interaction including corrections, proxy rewards, critique, and choice have been developed [6]. This work is based on learning from choice (sometimes also referred to as active preference learning), where a user iteratively chooses between two presented options [7], [9]- [11], [16], [18]. Similar to existing work, we pose the problem as learning weights in a linear reward function. We make novel contributions to address challenges arising from the high dimensionality often found in multi-robot problems. Existing approaches usually rely on sampling potential solutions as well as weights for the reward function [7], [9]. We study how the min-max regret technique from [11] can be extended so it can be used without any samples in a noiseless setting. Further, to handle noisy user feedback we propose a method to cast such feedback to multiple noiseless instances and solve the problem on them.
We focus on a generalized version of the team orienteering problem (TOP) [1], which is NP-hard. Using basis functions we consider variances of TOP where reward functions can be correlated between vertices, as well as have a diminishing return, i.e., are submodular [19]. The authors of [4] study OPs with correlated rewards and give a Mixed-Integer-Quadratic-Program solution, which can also be applied to the multirobot case. For single-robot OP with submodular rewards, the authors of [5] provide a constant factor approximation algorithm. The authors of [20] propose an approximation algorithm for TOP by sequentially solving single OPs for each robot. We combine the latter two techniques to obtain a constant factor approximation for submodular TOP.
Stochastic variants of orienteering problems include uncertainty on edge weights [3], [21], time to service a location [22], and rewards [2]. Similar to the latter case, we study the problem where the robot fleet does not know the rewards. In [23] the rewards of an orienteering problem are dynamic and depend on measurements taken at previous locations. In [2] robots learn the reward function by iteratively executing tours and use these observations to improve future tours. In contrast, our framework allows robots to learn the reward function by querying a user; the user then does not assign a reward to a single set of tours but instead chooses the preferred set of tours among two presented options. Another difference to [2] is that our framework can be used as an offline method, where the user is shown tours virtually allowing robots to learn the reward function prior to execution.
Potential applications of the proposed framework include persistent monitoring [24], [25], environmental data collection [23], and scene reconstruction [26]. The authors of [27], [28] propose an interactive framework for marine data collection: Users define desired targets for observation, the robot then proposes alternatives based on additional information about risks in the environment. Similar to our work, users then choose between different options. This allows the robot to learn the user's utility function trading off reward and risk.

II. PROBLEM FORMULATION
Consider a set of m robots collecting information in an environment represented by a graph G = (V, E, l). The set V is the set of vertices, E is the set of edges between the vertices, and l : E → R ≥0 assigns costs to the edges of the graph. A tour T is a sequence of vertices v 0 , v 1 , . . . , v n , v 0 . Given a depot location s ∈ V , a tour starts at s, i.e., v 0 = s. The reward function R : 2 V → R + assigns a reward to each set of vertices, i.e., the reward of visiting the vertices in a tour T denoted by V (T ). With a slight abuse of notation we write the reward R(V (T )) simply as R(T ).
Problem 1 (Orienteering Problem). Given a graph G = (V, E, l), a reward function R : 2 V → R ≥0 and a positive number B, find a tour T of length at most B that maximizes the reward collected R(T ).
We are interested in monotone, normalized submodular reward functions [19]. Such a function has the following prop- Remark 1 (Comments on Problem Formulation). The set V i contains a vertex for each location that robot i can visit. Each vertex is contained in just one set. Thus, if multiple robots can visit the same location, then each has a corresponding vertex in their set V i . The advantage of this representation is that each vertex encodes both the location and the robot performing a visit, and thus a submodular function can be defined directly over sets of vertices. This is in contrast to other formulations of the submodular team orienteering problem [3], [29] where the submodular function is defined over the set of all tours/paths, which is exponential in the number of vertices.
• GTOP with Unknown Reward Function: In this work we consider the case where the reward function R is unknown to the robot. We denote the hidden optimal reward function as R * and the corresponding GTOP solution T * . Further, let R be a robot's estimate of the reward function andT the corresponding optimal tour; we are interested in finding an estimateR of the reward function with corresponding optimal toursT = {T 1 , . . . ,T m } that solves We notice that this is an ill-posed problem as the reward function R * is not available to the robot. However, we consider a framework where the robot iteratively interacts with the user, allowing it to make observations about the user's hidden reward function. This is known as reward learning, where the robot presents the user with one or multiple possible solutions to it's task and then obtains feedback in the form of corrections, choice, labels, or others [6]. We define a query as a set of possible solutions for the GTOP Q = {T 1 , T 2 , . . . , T l }. Let f (R) be some prior belief over the set of all possible reward functions R. Given feedback U , the robot can compute a posterior f (R|(Q, U )). We can express the expected outcome with respect to the prior E U ∼f (R) [R|(Q, U )]. This framework allows us to state our problem as an adaptive stochastic optimization problem: Problem 3 (Learning GTOP Rewards). Given G = (V, E, l), a hidden reward function R * , a fleet of m robots with travel budgets B 1 , . . . , B m ; find a sequence of K queries (Q 1 , Q 2 , . . . , Q K ) such that the expected estimated reward functionR = E U k ∼f (R) [R|(Q 1 , U 1 ), . . . , (Q K , U K )] and the corresponding sets of m toursT solves (2).

BASIS FUNCTIONS
In this section, we present a linear approximation of a submodular reward function, then we propose an approximation algorithm for the GTOP for the linearized reward function.

A. Basis functions
We consider the reward function R(T ) to be be composed of a set of basis functions r 1 , . . . , r n : 2 V → R ≥0 . Given tours T , the reward function is then a weighted sum of the basis functions R(T , w) = n i=1 w i r i (T ). Similar approaches are commonly used in reward learning problems [6], [7], [9]- [11], where basis functions are usually referred to as features. Given that r i depend only on the vertices, we can 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 (T ) be a count of how many vertices of the The subsets W 1 , . . . , W n can reflect a spatial relation between vertices, i.e., describe neighborhoods, but can also express other features, such as grouping all vertices where the robots can make certain observations. The basic case r i (T ) = ψ i (T ) is a modular function describing the number of times subset W i is visited. However, many real-world problems exhibit a diminishing return property [30], [31]. In order for r i to be growing submodularly with ψ i , we choose where γ ∈ (0, 1]. If γ = 1 we recover the modular case; in the other extreme that γ → 0, visiting W i more than once effectively does not yield a larger reward than the first visit. Using these basis functions, the problem of learning the user reward function R * becomes one of learning the weights w * = (w * 1 , . . . , w * n ), i.e., the importance of each basis function, as well as the decay parameters γ * 1 , . . . , γ * n describing the diminishing return. Unfortunately, the proposed reward function is only linear in the weights w, but not in the decays. Therefore, we assume that γ comes from a discrete set Γ. For each subset W i we define |Γ| basis functions r i,j for j = 1, . . . , |Γ|, using the different values γ j . Using this discretization the overall reward function becomes For a sparse notation let φ = r 1 , r 2 , . . . , allowing us to write R(T , w) = φ(T ) · w. Further, for any given weight w, let T (w) denote the set of tours maximizing the reward, i.e., T (w) = arg max T R(T , w). Consequently, φ(T ) denotes the features of the tour T .
Observation 1 (Submodularity). The reward function R(T , w) proposed in Equation (4) is a normalized, monotone and submodular set function.
; adding an additional vertex can only increase the vertex count of any set W i . Hence, for any V (T ) ⊇ V (T ) and any γ j ∈ (0, 1], making R monotonically increasing. Finally, consider any vertex v and two sets of tours T and adding v does not change the vertex count ψ i and thus the value of the basis function r i,j . Since this holds for all Algorithm 1: Bi-criterion approximation for GTOP Input: G = (V, E, l), start s ∈ V , #robots m, budget B, weights w Output: Tours

B. Solving the GTOP for a Given Set of Weights
In [5], authors provide a bi-criterion approximation algorithm for the orienteering problem with submodular rewards, and in [20] propose an approximation algorithm to extend the results of the orienteering problem to the team orienteering problem. In the rest of the paper, for a given w, we combine these two approaches to achieve a bi-criterion approximation algorithm for the team orienteering problem with submodular reward functions. Algorithm 1 shows the proposed approach for the GTOP problem. The algorithm sequentially solves the submodular orienteering problem with the algorithm proposed in [5] (line 3). Then after iteration k, ψ i is incremented by the number of vertices T k visits in W i (line 5). At each iteration, the SINGLEOP implements the proposed bi-criterion approximation algorithm in [5] with approximation factor η = 2(1 − 1 e ) −1 on the collected rewards. Hence, by Theorem 1 in [20], Algorithm 1 is a 1 + η approximation algorithm for the GTOP problem.

IV. LEARNING REWARDS FROM CHOICE FEEDBACK
One framework for learning reward functions via user interaction that found widespread attention in HRI in recent years is learning from choice. Iteratively, the robots present the user with two alternative solutions to some robot planning problems. The user then chooses the preferred option. The user is assumed to make that choice based on some hidden reward function which allows the robot to infer the parameters of that reward function.

A. Deterministic user feedback
We begin by posing our problem for a deterministic user, whose feedback always follows the assumed cost function. Consider that two sets of tours T 1 and T 2 are proposed to the user, and the user indicates their preference.
Definition 1 (Deterministic user model). Given two sets of tours T 1 and T 2 , a deterministic user always prefers the tours with larger reward with respect to the hidden user weights w * . Let I ∈ {1, 2} denote the user feedback.Then Learning Cuts: Without loss of generality, assume that the user prefers T 1 (we can simply reassign the labels after observing the choice), therefore we have, φ(T 1 ) · w − φ(T 2 ) · w ≥ 0. We refer to this inequality as a cut. Let P (c 1:k ) denote the polyhedron constructed by the cuts {c 1 , . . . , c k }. Now we define a valid cut as follows: Definition 2 (Valid Cut). Given a polyhedron P (c 1:k ), a cut c k+1 is valid if the intersection of the cut and P (c 1:k ) has dimension greater than zero.
Note that each valid cut partitions the space of valid rewards w, therefore by adding a valid cut at each step we monotonically decrease the set of valid rewards. Now assume that we have a tours T 1 in hand, we want to construct the set T 2 such that the tours in T 2 satisfy the budget constraints and the cut constructed by comparing T 1 and T 2 is valid. Lemma 1. Given two set of tours T 1 and T 2 and a set of prior cuts {c 1 , . . . , c k }, the cut constructed by comparing T 1 and T 2 is valid if and only if the solutions to the following problems are greater than zero: Proof. The first part is trivial. Now assume that the cut is valid, then the cut intersects the interior of P (c 1:k ). Let d be the vector normal to the line defined by the cut, then there exists a w 0 , δ 1 and δ 2 such that w 0 +δ 1 d ∈ P (c 1:k ) and w 0 − δ 2 d ∈ P (c 1:k ). Therefore, the solution to the two problems are greater than zero.
In essence, Lemma 1 states that for a valid cut (T 1 , T 2 ) there must exist some w in the current polyhedron P (c 1:k ) for which T 1 has a higher reward than T 2 , and vice versa. In other words, the hyperplane defining a valid cut passes through the interior of the current polyhedron P (c 1:k ).
Query generation: The main challenge in active preference learning is to iteratively generate valid cuts that allow for efficient learning.
Related work in HRI is usually based on heuristic solutions that greedily optimize some auxiliary function h to maximize the expected learning benefit of presenting two solutions (T 1 , T 2 ). Recent approaches include h capturing the volume of the probability space over weights [7], the information entropy [9] or the maximum regret [11].
These optimizations are usually difficult on two different levels: Computing h often poses a hard problem and the potential solutions require solving some robot planning problem, making this a nested optimization. Most solution techniques rely on sampling candidates solutions, as well as approximating h using sampled weights. While this might be suitable for low-dimensional applications, the number of basis functions for team orienteering problems of our problem is O(n|Γ|). Thus, accurately approximating information entropy requires a prohibitively large number of samples.
We design a novel query generation method that does not require any form of sampling. Similar to [10] we choose a variation of learning from choice in which one of the two presented options comes from the previous iteration: At iteration k, let T curr be the tours the user preferred in the previous iteration. We now need to find only one new set of tours T new such that observing feedback to (T curr , T new ) yields a valid cut with respect to {c 1 , . . . , c k }.
To find T new given the previous cuts {c 1 , . . . , c k } and T curr , we adapt the maximum regret approach proposed in [11]. Regret measures how suboptimal the solution of estimated parameters w is. In the GTOP, this is captured by the reward of some tours T , evaluated by the users true reward function w * compared against the user-optimal solution T * , evaluated by w * , i.e., R(T * , w * ) − R(T , w * ) = φ * w * − φ w * . Using regret we can find T new by solving That is, given the current solution, we seek to find T new such that if T new was optimal, the current solution would be most suboptimal, i.e., have maximum regret. If the user chooses T curr , the weight w new becomes infeasible thus (w curr , w new ) will no longer be the maximizer for the updated polyhedron P (c 1:k ) -we greedily reduce the upper bound on the error. On the other hand, if the user chooses T new , we improve the current solution. This formulation makes two major changes to the max regret approach in [11]: 1) we fix one set of tours to be shown to be T curr , and 2) we use the difference instead of a ratio in the definition of regret. The following proposition ensures that an algorithm that iteratively solves (6) and then updates the polyhedron given the user feedback will eventually find an optimal solution, i.e., a weight w curr where R(T (w curr )) = R(T (w * )).

Proposition 1.
If the optimal solution to Problem (6) is not a valid cut, then the reward collected by T curr is optimal.
Proof. Let w new be the optimal solution to Problem (6). Since the cut defined by T curr and T (w new ) is not a valid cut, then we have φ(T (w * ))w * − φ(T curr )w * ≤ φ(T (w new ))w new − φ(T curr )w new = 0, where the first inequality comes from w * ∈ P (c 1:k−1 ) and the second equality comes from Lemma 1. Therefore, T curr collects the optimal reward. Now we establish the following result on the complexity of Problem (6).

Lemma 2. The problem of finding the tour with maximum regret is NP-hard.
Proof. We show the result by a reduction from the traveling salesman problem (TSP). Given a TSP instance G = (V, E, c) and a budget B, we construct an instance of problem (6). We set the polyhedron P to be unit cube and T curr to be the set of empty tours. Then problem (6) becomes max w new φ(T (w new ))w new and budget B on the tours. Let w * be the optimal solution to this problem, then T (w * ) where φ(T (w * ))w * = |V | is a valid solution to the TSP. Now note that if there is no solution to the max regret problem collecting |V | reward, then there is no solution to the TSP problem, therefore, the result follows immediately.
We observe the following property of the objective function in (6) which will help us provide a bound on it.
Lemma 3. The objective function φ(T (w))w − φ(T )w is a convex function in w for any set of tours T .
Proof. Consider w = λw 1 + (1 − λ)w 2 for some λ ∈ [0, 1]. Then, Note that the second term in the objective function is linear in w. Therefore, the result follows immediately.
While Lemma 2 shows that finding the set of tours maximizing the regret is NP-hard, Lemma 3 implies that the optimal solution of (6) is on a vertex of the polyhedron P (c 1:k ). We can upper bound that solution with min w new φ(T curr ) · w new subject to: w new ∈ P (c 1:k ).
In conclusion, at iteration k our min-max regret heuristic proposes two new sets of tours (T curr , T new ) where T curr is the solution the user preferred in the previous iteration, and T new is the approximate GTOP solution for w new solving (7).

B. Extension to noisy user feedback
In the previous section, we considered the problem with a deterministic user who always chooses the set of tours with higher reward with respect to w * . In practice, this assumption can lead to suboptimal outcomes when the user decision is not accurately captured in the assumed reward function. Thus, we consider the problem with a noisy user where the set of tours chosen by the user is not the set of tours collecting higher rewards. We model the noisy user with the Boltzmann model as follows: Definition 3 (Noisy user model). Given two sets of tours T 1 and T 2 , and a user with hidden rewards w, then the probability that the user chooses T 1 is where β> 0 represents the level of expertise of the user.
The Boltzmann model is widely used in reward learning [7], [9], [13], [32] and describes a user whose choice becomes more uncertain when the presented options have a similar reward with respect to w * . Now consider a set of cuts {c 1 , . . . , c k } which are results of the preference questions, then the probability that the hidden reward function lies in P (c 1:k ) is P(w * ∈ P (c 1:k )) = Π k i=1 P(c i ), where P(c i ) is the probability that the user has responded to the ith query correctly. We denote the negation of a cut c i byc i and the probability of it as P(c i ) = 1 − P(c i ).
Algorithm 2 shows the proposed algorithm for learning the reward function of the user. In Line 1 of the algorithm, we initialize the set of observed cuts to Q = ∅.
In Line 4, function PROBABLEREGIONS(Q, N ) takes the current set of cuts Q = {c 1 , . . . , c i } and an integer N as input and returns a set of N polyhedrons. Each such polyhedron is constructed as follows: We initialize a set of cuts Q = Algorithm 2: Learning GTOP Rewards Input: graph G = (V, E, l), start s ∈ V , fleet size m, budget B, sample budget N Output: Tours Then for each cut c i ∈ Q , we replace c i withc i with probability 1 − P(c i ). This then defines a new polyhedron P (Q ). That is, we sample from the set of all 2 K possible combinations of cuts or their negations. Thus, the probability of sampling a set of cuts Q and thus a polyhedron P (Q ) is P(w * ∈ P (Q )). Considering multiple polyhedrons allows us to take into account inconsistency in the answers by the user.
For each of the constructed polyhedrons, function MAXIMUMREGRET solves Problem (7). We generate a set of tours for each of the rewards as a candidate sets of tours for the next preference questions. Finally, in Line 8 we evaluate the maximum regret for each polyhedron and discount it by their probabilities. The level of expertise for the user and the reward function are not known, however observe that by Definition 3 we have P(c i ) > 1 /2. Therefore, we approximate the probabilities of regions as a monotonically decreasing function of the number of negated cuts in the construction of the polyhedron. Finally, the sets of tours with the highest discounted regret is presented to the user as a new query.

V. EVALUATION
We evaluate the performance in environmental monitoring missions using real-world and randomly generated scenarios.

A. Experiment Setup
In the experiments, the robot fleet is given a set of regions of interest, but no information on how valuable it is to collect environmental data in each region. The objective is to learn a reward function describing which regions are to be prioritized when battery life does not allow to visit all of them.
Basis functions: We define basis functions that capture the visits to each of the regions of interest. In each region, we randomly place 1 to 5 vertices. For each set W i of vertices in a single region we define three different basis functions as in (3) for decay parameters γ ∈ {.001, .5, 1}. That is, the user reward for each region can follow a step function, a curved submodular function, or a linear function.
User design: Drawing user weights for the basis functions uniformly random does not yield relevant problem instances: the initial solution T = GTOP(G, w = 1) is often already close to the optimal solution.
Thus, we design a probability function for how a user places weights on these basis functions. First, we model the user weight w i as a function of the distance of the region V i from the depot. In detail, the weight is a Gaussian random variable is the distance from the start vertex to the mean location of V i , and the variance σ is a design parameter A second parameter p describes a probability over the different values of γ-for each region the user "picks" only one of the three decay parameters. Thus, the vector p = p 1 , p 2 , p 3 where p 1 + p 2 + p 3 = 1 describes the probabilities for γ taking values {.001, .5, 1}, respectively.
We simulate users with values σ ∈ {.5, 10} representing scenarios with moderate and almost no correlation of reward and distance, and distributions over decay functions We consider all robots start at the same depot and have a budget equal to twice the distance from the depot to the furthest region. In the implementation of Algorithm 2, we use a simple static probability P(c i ) = 0.8 and N = 10 PROBABLEREGIONS. We measure how well Algorithm 2 learns the weights w * of the user reward function, i.e., solves Problem 3. Let T be the set of tours returned by Algorithm 2, the reward ratio is R(T , w * )/R(T * , w * ), where w * are the hidden user weights, and T * is the corresponding approximate GTOP solution using Algorithm 1. We notice that T * is only an approximation to the optimum; thus, the ratio can be larger than 1.

B. Baselines
We compare the proposed maximum regret heuristic against two classes of baselines.
Richer user input: The first class of baselines consists of non-learning approaches. Instead, we consider that the user provides more information about their reward function to the robot. In the proposed framework, the user only identifies regions of interest such as the protected areas in Figure 1. Without any learning, the robot fleet assumes equal reward for all regions, and that the decay can be either linear, submodular, or a step function. This constitutes the initial solution of our algorithm. With increasing complexity of user input we consider: Decay -users do not provide numerical reward values for the regions, but indicate what decay function each region has, Ranking + Decay -the user gives a ranking of the importance of each region, and the decay function, Reward - the user provides the exact rewards for the region, but not the decay, and finally Reward + Decay where the user provides the rewards and the decay, which is equivalent to providing w * . The latter two methods are effectively reward designs, which require a very high level of expertise from the user and thus are often impractical.
Competing active learning methods: The second class of baselines consists of competing approaches for the active query generation. The first is Random Uniform where we replace line 9 of Algorithm 2 with computing T new for some uniformly randomly sampled weight w new . A second method Random Posterior samples based on previously observed user feedback. We replace the direction φ(T curr ) of the objective function in (7) with some uniformly randomly sampled direction d ∈ [−1, 1] n , and set N = 1 in line 5 of Algorithm 2, i.e., generate only one probable region P .
The third query generation method Information Gain adapts the information entropy approach proposed in [9]. However, the original algorithm is unsuccessful in our problem: It returns the expected weight, which is often rendered 0 as the weight samples do insufficiently cover the high dimensional space. Thus, we adapted the entropy approach to also follow our framework where we show the previously preferred option T curr again. To find the second set of tours, we compute a set of candidates T 1 , . . . , T k : We execute lines 5 to 8 of our Algorithm 2, but replace line 7 with a linear program optimizing in a random direction, similar to Random Posterior. We then select the best candidate by solving Equation (4) from [9], using M = 300 weight samples. Each sample is drawn uniformly random from a sampled polyhedron returned by PROBABLEREGIONS(Q, 1).

C. Results
Real world environment with two robots: In the first experiment, we use part of the World Database on Protected Areas (WDPA) 1 , illustrated in Figure 2. The problem contains 17 regions, and for each of the 8 user types we simulated 25 trials. 1 Dataset from https://data.unep-wcmc.org/datasets/12   Figure 3 shows the comparison of our proposed method against the two baseline classes. In Figure 3a we observe that Maximum Regret drastically improves the reward ratio within the first few iterations, finding tours as good as Ranking + Decay, where the user would provide a noiseless ranking of all regions and identify the decay function. After 12 iterations the learning collects as much reward as Reward and approaches Reward + Decay (i.e., the ground truth) after 20 iterations. This showcases that the learning approach is able to find tours equally good to those that require much more complex user input when not using preference learning. Furthermore, after 20 iterations the learned set of tours collects 95% of the reward of the approximately optimal tours. Figure  3b shows that Maximum Regret collects the most reward after 20 iterations (95% compared to 82% for Information Gain, 75% for Random Posterior and 68% for Random Uniform). Moreover, there is a strong difference in the learning speed: After only 2 iterations Maximum Regret already achieves 82%, matching the result for Information Gain after 18 iterations.
Synthetic environment with 4 robots: To assert that the real-world experiment is representative of a wider range of problem instances, we consider a synthetic experiment where the regions of interest are randomly generated. We construct additional problem instances by sampling 20 regions of interest, each offering 1 to 5 observations points. We observed similar performance on the synthetic instances: After 10 iterations the proposed method collects as much reward as Ranking + Decay and Reward (81%). After 20 iterations our method achieves a reward ratio of 89% compared to 72% for Random Posterior, 70% for Information Gain, and 68% for Random Uniform.
In summary, the proposed method finds high-quality tours for the data collection task that, when no learning was used, would require much richer user input; and our method outperforms other learning approaches in terms of collected reward and learning speed.
VI. DISCUSSION This paper considers the problem of reward collection by a team of robots with a hidden submodular reward function. First, we presented a linear approximation of the submodular reward function. Second, we proposed an approximation algorithm when the weights on the linear approximation is known. Finally, we proposed a framework to learn the underlying hidden user reward function for deterministic and noisy users from choice feedback. The experimental results on real-world data show that the proposed framework provides near-optimal tours after a few iterations of user feedback. For future work, we consider investigating the effectiveness of the proposed method in data collection missions in the field.