Paper deep dive
Pairwise Approximation Can Select the Wrong Multi-Robot Plan
William Teo
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%
Last extracted: 9/25/2026, 3:37:55 AM
Summary
This paper investigates the plan-selection regret caused by using pairwise approximations (specifically the exact order-2 Möbius truncation F2 and a least-squares two-additive fit G) instead of the exact delivered-coverage set function F in multi-robot coordination. Using an indoor exploration benchmark with four-robot teams, the study finds that F2 frequently selects suboptimal plans, with regret up to 33.7% of map coverage, whereas the additive score F1 (singletons only) often performs better. The results indicate that lower average reconstruction error does not guarantee lower selection regret.
Entities (7)
Relation Signals (7)
F2 → causeshighregret → selection regret
confidence 95% · Ranking by F2 instead of F changes the selected plan on six of seven maps... with regret up to 0.337 of map coverage.
Reconstruction Error → doesnotguarantee → selection regret
confidence 95% · We also find that lower average reconstruction error does not guarantee lower selection regret.
G → isapproximationof → F
confidence 95% · and an equal-weight least-squares two-additive fit G... Switching to G reduces the regret but still changes the selection
F1 → isapproximationof → F
confidence 95% · The additive score F1, which keeps only the singleton terms, selects the exact winner on six of seven maps
F2 → isapproximationof → F
confidence 95% · From the same subset values we compute two pairwise scores: the exact order-2 Möbius truncation F2... Ranking by F2 instead of F changes the selected plan
G → reducesregret → F2
confidence 90% · Switching to G reduces the regret but still changes the selection on three of seven maps in each family.
indoor exploration benchmark → usedforevaluation → F2
confidence 90% · For each four-robot plan on an indoor exploration benchmark, replaying all 16 robot subsets gives the exact delivered-coverage set function F.
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:Multi-robot coordination methods often score a joint plan from singleton and pairwise terms, leaving out the terms that involve three or more robots. We measure the plan-selection regret of two pairwise approximations to delivered coverage using frozen multi-robot trajectories. For each four-robot plan on an indoor exploration benchmark, replaying all 16 robot subsets gives the exact delivered-coverage set function $F$. From the same subset values we compute two pairwise scores: the exact order-2 Möbius truncation $F_2$, which depends only on the singleton and pair values, and an equal-weight least-squares two-additive fit $G$. Ranking by $F_2$ instead of $F$ changes the selected plan on six of seven maps at the 15 m candidate-generation range in each of two candidate families, with regret up to 0.337 of map coverage. Switching to $G$ reduces the regret but still changes the selection on three of seven maps in each family. The additive score $F_1$, which keeps only the singleton terms, selects the exact winner on six of seven maps in one family and four of seven in the other, against one of seven for $F_2$. We also find that lower average reconstruction error does not guarantee lower selection regret.
Tags
Links
- Source: https://arxiv.org/abs/2609.29929v1
- Canonical: https://arxiv.org/abs/2609.29929v1
Trouble viewing inline? Open PDF directly →
Full Text
28,334 characters extracted from source content.
Expand or collapse full text
Pairwise Approximation Can Select the Wrong Multi-Robot Plan William Teo MARMoT Lab, Department of Mechanical Engineering, National University of Singapore NEAR Lab, AI.Robotics Strategic Technology Centre, Singapore Technologies Engineering williamteo@u.nus.edu Same eight candidate plans, ranked by F and F 2 (a) Selected by exact F(b) Selected by pairwise F 2 79.4% delivered45.6% delivered selection regret = 33.7% of map coverage delivered to baseexplored, never deliveredunknownwallrobot end position Fig. 1. Plans selected on env1 at the 15 m generation range. Both scores rank the same eight logged candidates. Ranking by F selects the plan in (a), which delivers 79.4% of the map. Ranking by F 2 selects the plan in (b), which delivers 45.6%, giving 0.337 regret. The warm shaded region in (b) was explored but had not reached the base by episode end. Colored lines show robot trajectories; circles mark final positions away from the base in (b), where R1, R2, and R4 end together in the top corridor and R3 ends near the base. In (a), every robot ends at the base. Abstract—Multi-robot coordination methods often score a joint plan from singleton and pairwise terms, leaving out the terms that involve three or more robots. We measure the plan-selection regret of two pairwise approximations to delivered coverage using frozen multi-robot trajectories. For each four-robot plan on an indoor exploration benchmark, replaying all 16 robot subsets gives the exact delivered-coverage set functionF . From the same subset values we compute two pairwise scores: the exact order-2 Möbius truncationF 2 , which depends only on the singleton and pair values, and an equal-weight least-squares two-additive fitG. Ranking byF 2 instead ofF changes the selected plan on six of seven maps at the 15 m candidate-generation range in each of two candidate families, with regret up to 0.337 of map coverage. Switching toG reduces the regret but still changes the selection on three of seven maps in each family. The additive scoreF 1 , which keeps only the singleton terms, selects the exact winner on six of seven maps in one family and four of seven in the other, against one of seven forF 2 . We also find that lower average reconstruction error does not guarantee lower selection regret. I. INTRODUCTION We test whether a score that keeps only singleton and pairwise interaction terms selects the same multi-robot plan as the exact delivered-coverage objective. Figure 1 shows a case where the two scores select different plans from the same pool. The plan selected by the pairwise score leaves much of its explored area undelivered to the base station. We compare exact order-2 truncation F 2 with a least-squares two-additive fit G and the additive score F 1 . The comparison measures the coverage lost when each score selects a plan from a fixed candidate pool. We also examine whether lower average reconstruction error corresponds to lower selection regret. For a set function over n robots, restricting its interaction terms to singletons and pairs reduces their number from 2 n − 1 to n + n 2 . Pairwise interaction terms are common in multi-robot coordination. For example, edge-based coor- dination graphs [1] and pairwise payoff functions in deep arXiv:2609.29929v1 [cs.RO] 24 Sep 2026 multi-agent learning [2] keep only singleton and pairwise terms. In coordinated frontier exploration, Burgard et al. [3] reduce the utility of a frontier target by a pairwise visibility penalty for each target already assigned to another robot, so each assignment is scored by its own utility minus pairwise discounts, less a path cost. Other frontier and sequential greedy methods simplify the search rather than the objective, for example by steering robots toward map frontiers or adding robots by marginal gain [4]–[8]. Factored formulations write the joint value as a sum of terms over small cliques [9]. A set function whose Möbius terms vanish above order k is called k-additive [10]; the fitted model below is the two-additive case. Those methods factor value over joint actions or target assignments. Here we apply the same pairwise restriction to a set function over robot subsets, and measure whether remov- ing higher-order terms changes the selected plan. Worst-case analysis shows that maximizing a submodular function from evaluations on bounded-size subsets alone can be far from optimal [11]. Under unconstrained communication, delivered coverage is a coverage function, and its order-3 and order-4 Möbius terms are the signed areas seen jointly by three or by four robots. Under finite communication, delivery can also depend on relay and connectivity patterns involving several robots [12]–[15]. We use the indoor exploration benchmark from the IROS 2026 Intelligent Information Gathering workshop [16], with four-robot teams on its seven released maps. Replaying logged trajectories over all 2 4 robot subsets evaluates the delivered- coverage set function exactly. The 2 n subset replays per candidate are the raw measurements from which the Möbius decomposition is computed; they are used here for offline analysis, not as a proposed runtime method. I. PLAN SELECTION WITH AN APPROXIMATE SCORE We select one plan from a pool B. Each candidate is a frozen set of trajectories for the full team N . The exact objective assigns each candidate b a full-team score F b (N), and a selector picks arg max b∈B F b (N). A pairwise repre- sentation replaces F with an approximate score ˆ F and picks arg max b∈B ˆ F b (N) instead. The regret of the approximate selection is F b F (N) − F b ′ (N) ≥ 0, where b F is the plan F ranks first and b ′ is the plan ˆ F selects, measured in map coverage. For each score, the top set contains all candidates within 10 −12 of its maximum. Among candidates in the approximate top set, we report the smallest exact regret. We count a selection change when the top sets under the two scores are disjoint or the regret exceeds 10 −12 . Large errors can be harmless if they shift competing plans by about the same amount. A ranking flips only when the difference between those shifts exceeds the exact-score gap. Let e b = F b (N)− ˆ F b (N) denote a candidate’s approximation error, let w be the plan ranked first by F , and let c be a competitor. Apart from ties within the stated tolerance, c outranks w under ˆ F exactly when e w − e c > F w (N)− F c (N).(1) 4-robot term 3-robot term R1 R2R3 R4 Full objectiveF orders 1–4 retain orders 1–2 R1 R2R3 R4 Order-2 scoreF 2 node and edge terms Fig. 2. Graph view of the interaction-order decomposition. Singleton terms attach to individual robots and pairwise terms to edges. The order-2 score F 2 retains these terms and omits the terms involving three or four robots. If all candidates have the same approximation error, every ranking is preserved. Equation (1) uses the exact-score gap between w and c. We call the gap between w and the exact runner-up the top-two margin. Equation (1) compares the errors of two candidates. Av- eraging errors across the pool hides that difference, so av- erage reconstruction error need not track selection changes. Section V-B compares the two on the benchmark. Equation (1) is an algebraic identity. We use it to describe observed ranking changes. Because it requires the exact scores, it is not a predictive or runtime test. A selection guarantee based on this identity would need bounds on individual candidates’ errors relative to the score gaps between plans. We do not derive such bounds in this paper. I. DELIVERED COVERAGE AND ITS PAIRWISE REPRESENTATIONS A. Exact subset values by frozen replay A team N = 1, . . . , n of robots explores an occupancy- grid indoor environment. Robots sense locally, exchange maps with peers within communication range, subject to the bench- mark’s wall-attenuated path-loss model, and deliver fused maps to a fixed base station. The benchmark scores an episode by delivered coverage: the fraction of the map known to the base station when the episode ends [16]. For a subset S ⊆ N we define F(S) as the delivered cover- age of the episode replayed with only the robots in S present, each following its logged trajectory exactly; absent robots never sense, communicate, or relay. Each replay starts from a fresh world, so evaluation order cannot leak state, and replay never invokes a planning policy. Although the remaining robots do not replan, the subset values still measure how each robot’s presence changes which observations reach the base through the benchmark’s communication model. F(∅) = 0. Evaluating F at all 2 n subsets gives every interaction term in Section I-B exactly, including the higher-order terms that the pairwise scores omit. We verify that, under the conditions used to generate each plan, the full-team replay F(N) reproduces the original score bit-exactly. B. Exact truncation and fitted approximation In the graph view of Figure 2, singleton terms attach to nodes and pairwise terms to edges. Higher-order terms involve larger robot groups. The Möbius decomposition makes this split exact [17]–[19]: every finite set function decomposes into interaction terms m(T) = X U⊆T (−1) |T | F(U),F(S) = X T⊆S m(T), (2) where m(T) is the part of the value that belongs to the group T jointly and to no smaller group inside it. Keeping only terms up to order two gives the order-2 score F 2 (S) = X T⊆S,|T|≤2 m(T),(3) the exact sum of the node and edge terms. F 2 depends only on the singleton and pair values. For n = 4, F 2 (N) = P i<j F(i, j) − 2 P i F(i), so it is the team score that a method evaluating only individual robots and pairs assigns by inclusion–exclusion. Keeping only the singleton terms gives the additive score F 1 (S) = P i∈S F(i). For n = 4, F 2 omits five interaction terms: the four triples and the quadruple. The order-4 truncation equals F identically, which we verify to 10 −12 in every episode. F 2 keeps the original singleton and pairwise terms, whereas a fitted model refits them to the observed subset values. We therefore also evaluate the two-additive fit G(S) = X i∈S a i + X i,j⊆S b ij ,(4) with coefficients chosen by ordinary unregularized least squares. We fit G separately for each candidate using all 15 non-empty subset values with equal weight, including the full- team value F(N). The fit has no hyperparameters and no intercept, so G(∅) = 0. For four robots this fits 10 coefficients to 15 equations. Unlike F 2 , G uses the triple and quadruple subset values, which a method that evaluates only singletons and pairs does not have. We use F 2 and G as the two pairwise scores in Section I, and F 1 as the additive reference. The residual F(S) − F 2 (S) is zero for |S| ≤ 2 by construction, so any nonzero residual is order-three-or-four structure. Unlike F , which is a coverage fraction in [0, 1], F 2 need not stay in this range: removing higher-order terms can push F 2 (S) below 0 or above 1. We summarize reconstruction quality by the normalized error E 2 = P ∅̸=S⊆N F(S)− F 2 (S) P ∅̸=S⊆N F(S) .(5) E 2 averages reconstruction error over all subset values. Se- lection uses the ordering of the full-team candidate scores (Section I). IV. EXPERIMENTAL SETUP Benchmark. All experiments use the workshop’s indoor exploration competition simulator [16], pinned at commit 2a2c751, with its seven released maps (env1–env7). The benchmark’s multi-agent track supports teams of two to five robots. We fix the team size at four so that all 2 4 = 16 robot subsets can be replayed exhaustively. Candidate plans use the shipped local-development start pose [15, 15], start delays of 0, 5, 10, and 15 steps, and a 1000-step horizon on every map. Candidate generation uses the benchmark’s 15 m communication-range parameter. Candidate plans. The primary pool contains eight can- didate joint plans per map, generated by the benchmark’s shipped nearest-frontier policy under a parameter grid: relay period 100, 300 × relay handoff on, off × frontier- crowding penalty default, off. A second family of eight candidate plans per map replaces the heuristic with uniform- random frontier selection, combining relay period and handoff toggles across generator seeds 0 and 1. All eight resulting trajectories were distinct on every evaluated map. All candi- dates were generated at the 15 m range, and all replays are deterministic. Communication conditions. Each primary-family candi- date is replayed at ranges 3, 6, 9, 15, and 30 m and at an idealized condition with unconstrained communication, under which delivered coverage equals the geometric union of what the team observed. The plans were generated at 15 m and replayed unchanged at every other range and under idealized communication. The logged trajectories are identical across these replays. The second family is evaluated at the generation-consistent 15 m setting on all seven maps (plus all six conditions on env1). In the primary family, two to four of the eight candidates per map have delivered scores that change with the communication range; the rest are range-invariant. Enumeration. For every candidate–condition pair we replay all 2 4 = 16 subsets from fresh worlds, 768 replays per map for the primary family, 128 per map for the second at 15 m, with the full-team consistency check of Section I-A at the 15 m generation condition. All scores use the same candidate pool, trajectories, and subset replays. 1 V. RESULTS A. Selection changes across maps and candidate families Figure 1 shows the two plans selected on env1 at the 15 m generation range. Both scores rank the same eight logged can- didate plans. The candidate selected by F 2 has F(N) = 0.456, compared with 0.794 for the plan F ranks first, giving regret 0.337 of map coverage. The top-two margin under F is 0.016. The F 2 -selected team explores 68.3% of the map and delivers 45.6%. Of the 33.7 percentage point gap to the exact winner, 22.6 points correspond to explored area that did not reach the base (Fig. 1b). The F -selected plan delivers everything it explores. Figure 3 reports the same comparison on all seven released maps. At the 15 m generation range, F 2 selects a lower- coverage plan on six of the seven maps in the primary family, with regret from 0.0034 (env2) to 0.337 (env1). Changing the communication range can create or remove these ranking changes. On env5, regret is zero at 3 and 9 m and 0.240 at 6, 15, and 30 m. The env5 exact winner has the same scores 1 Analysis code, all subset values, and an interactive results page: https: //github.com/williamteo/pairwise-regret. env1 env2 env3 env4 env5 env6 env7 33.7% 0.3% 13.3% 24.0% 4.4% 7.2% 18.1% 3.5% 6.4% 2.5% 5.9% 6.3% F 2 : 6/7 in each family LS fit G: 3/7 in each family Regret at the 15 m generation range nearest-frontier random-frontier LS fit G regret env1 env2 env3 env4 env5 env6 env7 42.739.739.733.711.111.1 1.30.313.60.30.30.3 000006.9 18.718.019.513.311.60 024.0024.024.00 18.411.38.14.413.24.4 016.010.57.26.90 3 m6 m9 m15 m30 m generation range idealized (reference) Exact truncation F 2 : selection outcome by map and communication range different selection (darker = larger regret)same selection a b Fig. 3. Pairwise-score regret across the seven benchmark maps. (a) At the 15 m generation range, exact order-2 truncation has nonzero regret on six of seven maps in each candidate family; the least-squares (LS) two-additive fit G has nonzero regret on three of seven in each. Bars show F 2 regret for the two families; charcoal ticks mark G’s regret, with a tick at zero where the fit selects F ’s plan; a dot at zero in the family’s bar color marks maps where F 2 does the same. (b) Exact-truncation (F 2 ) outcomes for the nearest- frontier pool across communication ranges; accented cells mark conditions where F and F 2 select different plans, darker for larger regret (printed as % of map coverage); neutral cells select the same plan. The boxed column is the generation range; the idealized column removes the communication constraint as a reference. at every range, and the plan F 2 selects at 6, 15, and 30 m is one of the two env5 candidates whose scores change with range. Its F 2 (N) moves above and below the winner’s as the range changes. The largest regret at any finite range is 0.427 (env1 at 3 m). On env3, F 2 selects the same plan as F at every finite range, and a lower-coverage plan under idealized communication. Ranking the second family’s eight uniform-random frontier plans by F 2 at 15 m selects a lower-coverage plan on six of seven maps, with regret from 0.025 (env5) to 0.181 (env2) (Fig. 3a). The map with zero regret at 15 m differs between families: env3 in the primary family and env1 in the second. Table I adds the additive score F 1 and the expected regret of a uniformly random pick from the eight candidates. At 15 m, TABLE I SELECTION REGRET AT THE 15 M GENERATION RANGE AS % OF MAP COVERAGE, FOR THE ADDITIVE SCORE F 1 , THE TWO PAIRWISE SCORES, AND A UNIFORMLY RANDOM PICK FROM THE EIGHT CANDIDATES (EXPECTED REGRET). Nearest-frontierRandom-frontier Map F 1 F 2 G Rand. F 1 F 2 G Rand. env10 33.7 7.124.9 15.60023.7 env200.3 0.37.31.3 18.1012.4 env3 36.60025.803.5 3.510.1 env40 13.3023.306.4 6.414.0 env50 24.0022.33.52.508.7 env604.4 4.414.605.9 5.99.1 env707.2013.306.307.5 F(N)F 2 (N) −0.5 0.0 0.5 1.0 selected by F and F 2 env3 — average E 2 0.26, same plan selected F(N)F 2 (N) −0.5 0.0 0.5 1.0 selected by F 2 selected by F env5 — average E 2 0.14, regret 24.0% F 2 score gap = 0.005 Fig. 4. Exact and order-2 full-team scores for the eight candidates on env3 (top) and env5 (bottom) at 15 m. Each line connects a candidate’s F(N) to its F 2 (N); truncated scores can be negative (Section I). On env3, the average reconstruction error E 2 (Eq. (5)) is 0.26 and both scores rank the same plan first. On env5, average E 2 is 0.14, the smallest at 15 m, yet F 2 selects a different plan, which delivers 24.0 percentage points less map coverage. F 1 selects the exact winner on six of seven maps in the primary family and four of seven in the second. F 2 has larger regret than F 1 on 11 of the 14 map–family cases and smaller regret on three (env3 in the primary family, env1 and env5 in the second). On env1 and env5 in the primary family and env2 in the second, the F 2 regret exceeds the expected regret of a random pick. On env1 in the primary family and env3 in the second, F 2 ranks the exact winner last of the eight candidates. B. Reconstruction error and selection regret Figure 4 shows the eight full-team scores on env3 and env5 at 15 m. The average E 2 on env3 (0.26) is nearly double env5’s (0.14, the smallest at 15 m). On env3, F and F 2 rank the same plan first, while on env5 they select different plans and the F 2 -selected plan delivers 0.240 less coverage; F 2 prefers that plan by 0.005. Lower average reconstruction error does not guarantee lower selection regret. The map with the largest average E 2 at 15 m in the primary family, env2 at 0.30, has regret 0.003. C. Why the ranking changes At 15 m, the top-two margin under F spans 0.001–0.124 across maps in the primary family and 0.002–0.133 in the second. Full-team truncation errors are larger and differ across candidates: e b reaches +1.80, while F is bounded by 1. In 10 of the 12 misranked map–family cases at 15 m the regret exceeds the top-two margin, so the F 2 -selected plan is not the exact runner-up. The env1 selection change in Fig. 1 gives one numerical example. For the plan that F ranks first, the signed order con- tributions to F(N) are +2.50, −3.09, +1.77, and −0.39, so F 2 (N) =−0.59 while the complete sum gives F(N) = 0.79, a truncation error of 1.38. For the plan that F 2 ranks first, F 2 (N) = 0.408 and F(N) = 0.456, an error of 0.049. The two errors differ by 1.33 and the exact-score gap is 0.34, so Eq. (1) holds and the ranking changes. Under idealized communication, F is a coverage function. For a coverage function, F−F 2 equals the area seen by exactly three robots plus three times the area seen by all four, nor- malized by map area. Therefore, greater three- and four-robot overlap increases the amount by which F 2 underestimates F . The Bonferroni inequalities give F 1 ≥ F ≥ F 2 and F 3 ≥ F . In the idealized condition every candidate’s truncation error e b is positive. However, under finite communication, F need not be a coverage function and e b can be negative, which occurs in 32 of the 280 finite-range primary evaluations. The env1 winner’s order sums above show the same alternation, and its four singleton values sum to 2.50 while the team delivers 0.79. F 2 is an algebraic truncation, so its values can fall outside the coverage range [0, 1]. This occurs in 185 of 336 primary- family evaluations and 79 of 96 second-family evaluations. All fitted full-team scores G(N) remain within [0, 1]. D. Least-squares fitting and order-3 truncation We also refit the node and edge terms to all subset values. The fitted score G reduces misranking but does not eliminate it. Across all 54 evaluated settings, G never has greater regret than F 2 , and has smaller regret in 28. Across the 42 primary settings, it reduces the number of selection changes from 31 to 10 and removes the largest truncation regrets entirely (env5 at 15 m, 0.240→ 0; env1 at 3 m, 0.427→ 0). At the 15 m generation range, G selects a lower-coverage plan on three of seven maps in each family: env1 (regret 0.071, versus 0.337 under exact truncation), env2 (0.003), and env6 (0.044) for the nearest-frontier pool, and env3 (0.035), env4 (0.064), and env6 (0.059) for the random-frontier pool. In the random-frontier pool, these three regrets are the same as the exact truncation’s regrets on those maps. The order-3 truncation F 3 includes all triple terms. It re- moves 30 of F 2 ’s 31 primary selection changes, but introduces four on env3, with regret up to 0.070. In the second family it introduces changes on env1 at 15 and 30 m, where F 2 and G both agree with F , and at 15 m it selects a lower-coverage plan on three of seven maps, with regret up to 0.156. Adding order-3 terms removes most F 2 selection changes, but it also creates new ones in some settings where F 2 agrees with F . At 15 m, F 1 and F 3 each change the selection on one map in the primary family and three in the second, against six of seven for F 2 in each. VI. DISCUSSION AND LIMITATIONS Communication. The ranking changes occur at finite com- munication ranges, including the 15 m generation range. Under idealized communication F is a coverage function, and its truncation error is the multi-robot overlap of Section V-C, positive for every candidate on every map. At finite ranges the error can be negative. Limitations. We evaluate one benchmark, one fixed start configuration, and four-robot teams. Exhaustive subset evalu- ation grows exponentially with team size, so four robots allow all 16 subsets to be replayed. The plans are deterministic and evaluated by frozen replay of logged trajectories. Removing a robot does not replan the remaining trajectories, so the measured set function is specific to frozen replay. We do not test other team sizes, start poses, or benchmarks. Both candidate families are eight-plan sets built on the benchmark’s frontier machinery and relay-parameter grid, generated at 15 m. In the primary family, F ranks the same parameter setting first in every map and condition. The six communication conditions on each map therefore reuse the same map-specific candidate plan. In the second family, the top-ranked plan varies across maps. We fit one model class: the equal-weight least-squares two- additive model of Eq. (4), fitted in-sample. The pairwise terms studied here are set-function terms over robot subsets rather than payoff functions over joint actions, so the results do not transfer directly to coordination-graph methods. The selectors rank a fixed candidate pool; we do not evaluate planners that search or optimize over a pairwise model, and we do not evaluate online replanning. VII. CONCLUSION For four-robot teams on the seven evaluated maps, both exact order-2 truncation and a fitted two-additive score can select a lower-coverage plan from a fixed pool. Refitting reduces the observed regret but does not eliminate it. Adding pairwise terms to the additive score also does not consistently improve selection. These results suggest that we should evaluate approximate objectives both by the plans they select and by how accurately they reconstruct objective values. In the tested candidate pools, retaining more interaction terms did not consistently improve selection. Measuring the delivered coverage of the selected plan reveals losses that average reconstruction error alone does not capture. REFERENCES [1] J. R. Kok and N. Vlassis, “Collaborative multiagent reinforcement learning by payoff propagation,” Journal of Machine Learning Research, vol. 7, no. 65, p. 1789–1828, 2006. [2] W. Böhmer, V. Kurin, and S. Whiteson, “Deep coordination graphs,” in Proceedings of the 37th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 119. PMLR, 2020, p. 980–991. [3] W. Burgard, M. Moors, C. Stachniss, and F. E. Schneider, “Coordinated multi-robot exploration,” IEEE Transactions on Robotics, vol. 21, no. 3, p. 376–386, 2005. [4] B. Yamauchi, “A frontier-based approach for autonomous exploration,” in Proc. 1997 IEEE Int. Symp. on Computational Intelligence in Robotics and Automation (CIRA), 1997, p. 146–151. [5] —, “Frontier-based exploration using multiple robots,” in Proc. Sec- ond Int. Conf. on Autonomous Agents. ACM, 1998, p. 47–53. [6] A. Krause, A. Singh, and C. Guestrin, “Near-optimal sensor placements in Gaussian processes: Theory, efficient algorithms and empirical stud- ies,” Journal of Machine Learning Research, vol. 9, p. 235–284, 2008. [7] A. Singh, A. Krause, C. Guestrin, and W. J. Kaiser, “Efficient infor- mative sensing using multiple robots,” Journal of Artificial Intelligence Research, vol. 34, p. 707–755, 2009. [8] M. Corah and N. Michael, “Distributed matroid-constrained submod- ular maximization for multi-robot exploration: Theory and practice,” Autonomous Robots, vol. 43, no. 2, p. 485–501, 2019. [9] C. Guestrin, D. Koller, and R. Parr, “Multiagent planning with factored MDPs,” in Advances in Neural Information Processing Systems 14, 2001, p. 1523–1530. [10] M. Grabisch, “k-order additive discrete fuzzy measures and their repre- sentation,” Fuzzy Sets and Systems, vol. 92, no. 2, p. 167–189, 1997. [11] A. Downie, B. Gharesifard, and S. L. Smith, “Submodular maximization with limited function access,” IEEE Transactions on Automatic Control, vol. 68, no. 9, p. 5522–5535, 2023. [12] M. N. Rooker and A. Birk, “Multi-robot exploration under the con- straints of wireless networking,” Control Engineering Practice, vol. 15, no. 4, p. 435–445, 2007. [13] J. Banfi, A. Quattrini Li, I. M. Rekleitis, F. Amigoni, and N. Basilico, “Strategies for coordinated multirobot exploration with recurrent con- nectivity constraints,” Autonomous Robots, vol. 42, no. 4, p. 875–894, 2018. [14] R. Hull, R. Fitch, and G. Best, “Bandwidth-aware multi-robot coordi- nation with utility-guided coalition formation,” in 2025 IEEE Int. Symp. on Multi-Robot and Multi-Agent Systems (MRS), 2025, p. 1–7. [15] S. Kim, S. Baek, M. Corah, G. Best, B. Moon, and S. Scherer, “PRoID: Predicted rate of information delivery in multi-robot exploration and relaying,” arXiv:2604.10433 [cs.RO], 2026. [16] BYU FROST Lab, “Indoor exploration competition,” GitHub repository, 2026, commit 2a2c751; benchmark of the IROS 2026 Workshop on Intelligent Information Gathering. [Online]. Available: https: //github.com/BYU-FROST-Lab/indoor-exploration-competition [17] G.-C. Rota, “On the foundations of combinatorial theory I. Theory of Möbius functions,” Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete, vol. 2, no. 4, p. 340–368, 1964. [18] J. C. Harsanyi, “A simplified bargaining model for the n-person cooper- ative game,” International Economic Review, vol. 4, no. 2, p. 194–220, 1963. [19] M. Grabisch and M. Roubens, “An axiomatic approach to the concept of interaction among players in cooperative games,” International Journal of Game Theory, vol. 28, no. 4, p. 547–565, 1999.