Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments
arXiv:2605.22693v1 [cs.RO] 21 May 2026
Hoang-Dung Bui , Abhish Khanal , Raihan Islam Arnob , Gregory J. Stein George Mason University {hbui20, akhanal7, rarnob, gjstein}@gmu.edu,
Abstract Autonomous robot teams navigating partially known environments face costly backtracking when ground robots encounter blocked roads that are only revealed upon physical traversal. We address this with Scout-Assisted Planning (SAP), a heterogeneous planning framework in which scouting Unmanned Aerial Vehicles (UAVs) proactively gather environmental information to improve Unmanned Ground Vehicle (UGV) navigation. To focus scouting on the most consequential edges, we propose Information Gain-based Action Pruning (IAP), which scores candidate scouting actions by their expected impact on ground robot behavior. Since exact Information Gain-based Action Pruning (IAP) computation is prohibitively expensive, we develop a Graph Neural Network (GNN)based model that predicts information gain values directly from graph structure and belief state, reducing planning time to real-time levels without sacrificing solution quality. Experiments across three environment types show that SAP with Information Gain Action Pruning (SAP-IAP) reduces ground robot travel cost by 31.9–37.7% over the Canadian Traveler Problem (CTP) baseline, and outperforms proximity-based scouting guidance by an additional 8–14%, confirming that principled information-gain-guided scouting is both more effective and computationally feasible for real-world deployment.
Introduction Autonomous robot teams operating in disaster-struck or hazardous environments must navigate through partially known terrain where roads or pathways may be blocked by debris, flooding, or structural damage. Making efficient decisions under this uncertainty is critical — unnecessary detours and backtracking waste time and resources that could be lifesaving in search-and-rescue or logistics scenarios. This problem is formalized as the CTP, originally introduced by Papadimitriou and Yannakakis Papadimitriou and Yannakakis [1991]. In CTP, a UGV navigates in a graph where some edges may be blocked, and blockages are only
a) Canadian Traveler Problem (CTP) b) Scout-Assist Planning (SAP) Figure 1: Gaining critical environmental data earlier improves significantly travel distance for UGV’s navigation. In CTP (a), a UGV follows its policy until facing a blocked street, then replan. Gaining environmental information sooner from a scouting UAV (b), the UGVs can replan and change its behavior earlier that saves significant travel cost.
revealed upon physical traversal. When a robot reaches a blocked edge, it must backtrack and replan — a costly cycle that grows more expensive as environments scale in complexity. A natural remedy is to augment the ground team with scouting UAVs. Unlike ground robots, UAVs are unconstrained by terrain and can rapidly overfly edges to verify their status, feeding that information back to improve ground robot planning. However, deploying scouts can be inefficient without principled guidance. Without a strategy for choosing which edges to inspect, drones may expend resource on low-utility edges that are irrelevant to the ground team’s current path — providing information that never changes robot behavior. Computing an optimal scouting policy by sampling over all unvisited edges is computationally intractable due to the exponential branching factor this introduces. A straightforward heuristic is to guide drones toward edges spatially close to the ground robots — a proximity-based strategy that ensures scouted information is locally relevant. This reduces unnecessary backtracking and lowers ground robot travel cost compared to unguided scouting (up to 26% in our experiments). However, proximity-based guidance is inherently myopic: it focuses drones on nearby edges regardless of whether those edges are actually on any plausible future path for the ground team, ignoring the long-term struc-
ture of the planning problem. To move beyond local heuristics, we formulate an Information-Gain (IG) criterion that estimates the expected reduction in ground robot travel cost if a given edge’s status were known. By ranking edges according to this value and pruning low-utility candidates, the drone’s attention is concentrated on edges that meaningfully alter the ground team’s decisions. This yields further improvements over the distance-based heuristic (around 12% in our evaluation). However, computing IG values exactly requires evaluating ground robot policies under all possible edge-status combinations — a process too computationally expensive for realtime deployment. To close the gap between solution quality and computational feasibility, we develop a GNN model trained to predict IG values directly from the graph structure and current robot state. The GNN captures the relational dependencies between edges — which paths the ground robot is likely to use, which blockages would force costly detours — and produces accurate IG estimates in a fraction of the time required by exact computation. This makes the full planning framework applicable to real-time settings. We formalize this setting as the Canadian Traveler Problem with Scouts (CTPwS), a new variant of CTP in which a heterogeneous team of UGVs and UAVs collaboratively navigates a partially known environment toward a shared goal. Although the map topology is known, edge blockages due to weather or disaster events are initially unknown and only verifiable by direct inspection. CTPwS inherits the exponential state-space growth of CTP — compounded by the drone’s unconstrained action space across all unvisited edges — and additionally requires a unified high-level action representation applicable to both UGVs and UAVs. Existing work on scout-assisted planning [Stadler et al., 2023] partially addresses CTPwS through a hybrid approach that computes a joint policy only when scouting is expected to improve overall performance. This approach relies on an approximated IG formulation that assume a deterministic ground robot finishing time — an assumption that breaks down with more than one ground robot, restricting the framework to single-UGV settings. We present Scout-Assisted Planning (SAP) with Information Gain Action Pruning (SAP-IAP), a learning-informed planning framework for heterogeneous robot teams that is tractable at scale. Our contributions are: • An Information-Gain (IG) formulation that estimates the value of each UAV scouting action and focuses exploration on a compact, high-utility subset of edges. • A GNN-based predictor that approximates IG values in real time, reducing planning overhead from seconds to milliseconds and enabling deployment in dynamic environments. • Empirical evaluation on three types of environments demonstrating up to (31.5–51.2)% reduction in ground robot travel cost compared to baselines.
Related Work Canadian Traveler Problem (CTP) CTP was introduced by Papadimitriou and Yannakakis [1991] and characterized as a deterministic Partial Observation MDP (POMDP) and Phard problem. Three broad families of approaches have been proposed to address it. The first family adopts an optimistic assumption: all unknown edges are treated as passable, and the agent computes a shortest path on this free-space graph. When a blocked edge is encountered during execution, the agent replans. Bnaya et al. [2009] augmented this strategy with remote sensing, triggering observations only when the expected improvement in travel cost exceeded the sensing overhead. Eyerich et al. [2010] contributed two samplingbased algorithms within this family: Hindsight Optimization and Optimistic Rollout, which differ in how rollout costs are estimated. Hindsight Optimization uses the shortest path on a sampled graph, while Optimistic Rollout accumulates travel cost along optimistic shortest paths until a blocked edge is encountered or the goal is reached. While computationally efficient, optimistic methods force the agent to replan repeatedly upon encountering blocked edges, causing travel costs to accumulate significantly over time. The second family incorporates edge uncertainty directly into the search. Nikolova and Karger [2008] proposed a minimum expected distance criterion to estimate edge costs under blocking probabilities, paired with an expected minimum distance heuristic to approximate cost-to-goal. Guo and Barfoot [2019] extended this line with LAO* search, which trades off policy quality against planning time by minimizing Exponential Risk — the variance from the optimal expected cost. More recently, Veys et al. [2024] reduced runtime by constructing sparse probabilistic graphs that prune edges unlikely to improve the expected plan cost, narrowing the search space without sacrificing solution quality. The third family reasons over expected shortest paths on the uncertain graph directly. Narayanan and Likhachev [2017] computed all relevant shortest paths along with their probabilities and selected the path with the lowest expected cost. Bampis et al. [2022] proposed a CAO* algorithm with a caching mechanism to avoid re-expanding nodes in the AO* tree, combined with an upper-bound heuristic to preserve admissibility. Despite these improvements, both approaches require polynomial runtime in the number of edges, limiting their scalability to larger graphs. Eyerich et al. [2010] also presented a Upper Confidence Bounds (UCB)-based algorithm that uses sampling with agent history to evolve belief states, computing rollout costs as the sum of travel cost with a heuristic evaluated on the optimistic graph. We build on this idea in developing our own planner for CTP. Across all three families, a shared limitation is that the robot must physically traverse an edge to verify its status — meaning blocked edges are discovered only after costly travel. This motivates integrating scouting agents that can gather information proactively, before the ground robot commits to a path. Canadian Traveler Problem with Scouts (CTPwS) Several frameworks have explored leveraging scouting robots to improve the planning of other team members, though none fully addresses the challenges of the CTPwS setting. Stadler et al. [2023] propose the most closely related work, restricting at-
tention to a single ground robot supported by multiple sensing agents. Their approach uses deterministic navigation macroactions defined over the observed graph, and derives policy approximation formulas under the assumption that the ground robot is the sole source of stochasticity. This assumption becomes untenable when multiple ground robots are introduced: each robot can trigger independent belief updates, causing macro-action termination times to become unpredictable under the abstraction used. As a result, the policy approximation formulas are invalidated, and the framework does not extend to teams with more than one ground robot. Addressing this limitation requires joint reasoning over the interruption events that arise from shared belief updates across all agents. Graph Neural Networks for Planning under Uncertainty GNNs have recently emerged as a powerful tool for learning heuristics and value estimates over graph-structured problems, replacing hand-crafted rules with strategies inferred directly from data [Drori et al., 2020]. In robotics, this paradigm has been extended to planning under uncertainty: Chen et al. [2020] combine GNNs with deep reinforcement learning to predict optimal sensing actions in belief space for autonomous exploration, while Arnob and Stein [2024] use a GNN to reason over both local and non-local graph structure to improve navigation under partial observability. However, these approaches either target fully observable routing problems or learn end-to-end action policies in continuous exploration settings. None address the problem of predicting per-edge information gain values in a partially observable graph where an edge’s scouting utility depends jointly on the ground robot’s belief state, its planned path, and the probabilistic structure of remaining unknown edges. In our work, we address this gap by building on Partial Observation Monte Carlo Planning (POMCP) [Silver and Veness, 2010] to solve the classical CTP, following the spirit of the UCB-based approach of Eyerich et al. [2010]. Like that method, POMCP is a sampling-based planner that constructs a Monte Carlo tree to evolve belief states from agent history. From this foundation, we develop SAP to solve CTPwS for a heterogeneous robot team on uncertain graphs, supporting multiple ground robots without the single-robot restriction of prior work.
Problem Formulation We consider a heterogeneous robot team consisting of two sub-teams: a ground team of N UGVs and a scout team of M UAVs, operating in a partially known environment. The ground team is tasked to reach N designated goal locations, while the scout team is assigned to rapidly gather environmental information to improve the ground team’s navigation. As new information becomes available, the ground team updates its behavior to benefit from the incoming observations. Environments are represented as graphs in which edges and vertices correspond to roads and intersections, respectively. Due to weather or disaster events, roads might be blocked at specific points. To verify whether a road is blocked, a robot must physically visit the corresponding point. We assume that each edge ei has one Possible Blocking Point (PBP), denoted as Bi , with blocking probability pi , located at the mid-
Figure 2: Abstract Actions for both UAVs UGVs. The UGV has two actions: move to {B1 , B2 }, while the UAV has a action set of all unvisited PBPs {B1 , B2 , . . . , B10 }.
point of the edge. PBPs are treated as additional vertices in the graph. Accordingly, a graph G in our formulation consists of two types of nodes: regular vertices (intersections) with zero blocking probability and PBPs. This unified graph representation enables a share high-level action space for both ground robots and scouting drones. We further assume that observations are perfect and instantaneous relative to travel time, so observation cost is negledted. Defining Abstract Action Unlike prior CTP work in which actions begin and end at vertices, our high-level action σ must accumulate arbitrary robot locations since robots immediately interrupt and restart their actions upon receiving updated environmental information. Accordingly, each action σ originates from the robot’s current location and navigates to a graph’s vertex or a PBP Bi . Each action also contains a robot’s identifier, ensuring correct assignment when multiple robots complete actions simultaneously. Defining Belief State The belief state bt in CTPwS is discrete with respect to each robot’s binary observations of whether a given road is blocked or not. We assume lossless communication between all robots, so every agent maintains an identical, up-to-date partial graph at all times. Formally, the belief state at time t is defined as bt (s) = P (st = s|ht ), where ht is the history of actions, observations, and initial belief, and st is the true state at time t. The true state is represented as the tuple: bt = {pg , pd , G, BU , BT , BB } (1) where pg , pd are the current positions of ground robots and drones, respectively; G is a graph representing the environment; and BU , BT , BB are sets of unknown, traversable, and blocked points, respectively. POMDP Formulation Planning is centrally coordinated: at each time step, a joint action at is computed for the entire team, specifying each robot’s next movement so as to minimize the expected travel cost of the ground team. Formally, the problem is cast as a Partial Observation MDP (POMDP) [Kaelbling et al., 1998]. The expected cost Q under this model is expressed via the belief-space Bellman Equation [Pineau and Thrun, 2002] :
Figure 3: Transition Model of Scout-Assisted Planning (SAP) for a team of 1 UGV & 1 UAV . The UGV is tasked to reach its goal G with the minimal expected cost. The graph has four vertices: V = {S, G, U, V} and five edges with five PBPs= {B1 , B2 , B3 , B4 , B5 }. At step 1, both robots are assigned to move to B2 . The drone reaches its goal first (step 2). The observation of B2 resets the action of the ground robot. If B2 is blocked (p2 percent), the UGV should terminate its current action and go back to S (step 3a). The UAV then heads to B1 to support the ground robot making decision as reaching S. At step 3b, there is (1-p2 ) percent B2 is traversable, and the ground robot continues its action. The information from the drone is not matter to the ground robots from this point. The process is continue until the robots reach their goals or the sampling tree gets its maximum depth.
Q(bt , at ) =
X
P (bt+1 |bT , at )[R(bt+1 , bt , at )
bt+1
+
min
Q(bt+1 , at+1 )]
at+1 ∈A(bt+1 )
(2)
where R(bt+1 , bT , at ) is the cost accumulated by reaching belief state bt+1 from bt by taking action at . The objective is to find a policy π that minimizes the expected cumulative cost of the ground robot team.
Scout-Assisted Planning (SAP) We present Scout-Assisted Planning (SAP), a model-based planning framework for heterogeneous robot teams operating in partially known environments. SAP enables concurrent action execution across ground robots and scouting drones, allowing the team to share observations in real time and update behavior as new environmental information arrives. Building on the multi-robot sub-goal planning framework of Khanal and Stein [2023], in which robot actions are concurrent and may finish at different times, we extend the transition model to support heterogeneous robot teams composed of both UGVs and and UAVs. The key distinction of our model is that robots may terminate their current actions immediately upon receiving new observations, enabling ground robots to replan and adapt as the scout team resolves edge uncertainty. This capability introduces two modeling changes: (1) robots may interrupt
and restart actions from arbitrary positions rather than fixed graph’s vertices, requiring a new high-level action definition that is not anchored to graph vertices, and (2) the action spaces of drones and ground robots are structurally different, requiring a hierarchical treatment of joint actions. In this section, we formalize the SAP state representation, the concurrent state transition model, and the joint-action Bellman equation used to compute expected team cost. We then present a Distance-based Action Pruning (DAP) heuristic that prunes low-value drone actions by prioritizing PBPs near the ground team, yielding a significant reduction in travel cost over unguided scouting. Building on its limitations, we introduce Information Gain-based Action Pruning (IAP), a principled pruning strategy that guides scouting drones toward edges with highest expected impact on ground robot behavior. Finally, we describe how IAP is integrated with SAP into the full SAP-IAP planner.
Expected Cost of Scout-Assisted Planning with High-Level Joint Actions A high-level joint action at is a list of single-robot actions at = [σ1 , . . . , σN , σN +1 , . . . , σN +M ], assigning each robot a target vertex or a PBP to navigate to. For a belief state bt , the joint action set A(bt ) is the outer product of all individual robot’s action sets, where UGVs may move to neighboring vertices or PBPs along edges, and UAVs may fly directly to any unvisited PBPs. To avoid redundant scouting, no two drones can be assigned the same PBP simultaneously. The action sets of drones and ground robots differ in an important structural way: Drones share a common action set consisting of all unvisited PBPs, which shrinks monotonically as scouting progresses. Ground robots, by contrast, act on their local neighborhood of vertices, and their action sets remain stable in size through execution. State Transition. The core principle of the SAP transition model is that whenever any robot acquires a new observation, all other robot immediately terminate their current actions and are reassigned based on the update belief state. If a robot completes its action without generating a new observation, the planner simply assigns it a new action. The highlevel satate is thus updated at the moment of the first robot among the team completes its assigned action. The time cost of a joint action T ′ is therefore determined by the robot completing its action first.
T ′ (bt , at ) = min (T (bt , σ)); σ ′ (bt , at ) = argmin(T (bt , σ)) ∀σ∈at
∀σ∈at
(3) The outcome of completing joint action at depends on whether the completing robot reaches an unvisited PBP. If so, the observation is binary: the PBP is blocked with probability PB (σ ′ ), yielding successor state bB , or traversable with probability 1 − PB (σ ′ ), yielding successor state bT :
bB = ⟨pt (at , T ′ ), G,B′U = BU \{σ ′ }, B′B = BB ∪ {σ ′ }, ′
BT = BT ⟩
(4)
bT = ⟨p (at , T ), G,B′U = BU \{σ ′ }, B′B = BB , ′ ′ B T = B T ∪ {σ }⟩ t
′
Information Gain-based Action Pruning (IAP)
If the completing robot instead reaches or graph vertex or an already-known PBP, no new observation is generated and only the robot positions are updated: bN = ⟨pt (at , T ′ ), G, B′U = BU , B′B = BB , B′T = BT ⟩
(5)
Bellman Equation. Given our state and action abstraction above, the expected cost of a joint action at in belief state bt is defined by the following Bellman equation (see also Fig. 3). Q(bt , σt ∈A(bt )) = T ′ + PB (σ ′ )
min′
Q(bB , at+1 )
at+1 ∈A (bB )
+ [1 − PB (σ ′ )]
min′
Q(bT , at+1 )
at+1 ∈A (bT )
from edges that would genuinely alter robot behavior. This limitation motivates a more principled formulation that accounts for the global structure of the planning problem, which we develop next.
(6)
This equation accumulates the travel cost T ′ of the current join action and branches over the two possible observation outcomes, each leading to a recursively evaluated successor state. The SAP framework—comprising the state representation, joint action formulation, and transition model— is solved approximately using POMDP [Silver and Veness, 2010], a sampling-based solver that constructs a Monte Carlo tree over belief states without requiring explicit state enumeration.
Distance-Based Action Pruning (DAP) While SAP provides a complete planning framework for the heterogeneous team, the drone’s action set grows with the number of unvisited PBPs, making exhaustive evaluation of all scouting candidates computationally expensive. A natural first approach to guide the scouting drone is to prioritize PBPs that are spatially close to the ground robots. The intuition is straightforward: edges near the ground team are more likely to be on their imminent path, so resolving their status early reduces the chance that a robot commits to a blocked route. Formally, the priority score for drone j to scout PBP Be under the distance-based heuristic is: 1 j (7) vD (b, ae ) = PN i=1 dist(qgi , qbe ) where qgi is the current position of ground robot i and qbe is the location of PBP Be . The drone is assigned to the highestscoring candidate, prioritizing the PBPs that minimizes the distance to the ground robot team. While this heuristic is computationally lightweight and improves over unguided scouting by directing the drone toward locally relevant edges, it is inherently myopic. Proximity to the ground robot team does not imply that an edge lies on any plausible future path toward the team’s goals — a nearby edge that is structurally irrelevant to all ground robot plans j will score highly under vD while displacing scouting effort
To address the limitation of DAP, we introduce Information Gain-based Action Pruning (IAP), a principled pruning strategy that focuses the drone’s attention on edges whose observation is most likely to improve ground robot behavior. Value Change of a Scouting Action. Consider a belief state b in which each uncertain edge e carries a blocking probability pe in ∈ (0, 1) and contains a PBP Be . A scouting action ae dispatches the drone to observe Be , revealing whether edge e is traversable or blocked. The value of this observation to ground robot i is measured by the change in its value function across the two possible outcomes: vci (b, ae ) = V i (b | ae = block) − V i (b | ae = trav)
(8)
A large vci indicates that the two outcomes lead to substantially different plans for robot i, making edge e a high-priority scouting target. Conversely, a small vci indicates that the observation would not meaningfully alter the robot’s behavior regardless of the outcome. Team-Level Value Change. To account for the full ground team of N robots, individual value changes are aggregated: N X
vci (b, ae )
(9)
i=1
This decoupled formulation is deliberately scalable: each robot’s value change is evaluated independently given its start and goal configuration, and contributions are summed at runtime. Adding further ground robots requires no modification to the formulation for existing team members. Travel Cost. The second factor governing action priority is the time required for drone j to reach Be from its current position: dist(qdj , qbe ) (10) vd where qdj is the drone’s current position, qbe is the location of Be , and vd is the drone’s velocity. This term penalizes distant scouting targets, reflecting the practical constraint that a delayed observation reaches the ground team too late to meaningfully influence their planning. IAP Formulation. Combining Equations 8–10, the full IAP priority value for drone j scouting edge e is: tjae =
vIj (b, ae ) =
1 tjae
· pe (1 − pe ) ·
N X
vci (b, ae )
(11)
i=1
The middle factor pe (1−pe ) is the variance of the Bernoulli distribution over edge e’s blocking state. It is maximized at pe = 0.5, where uncertainty is greatest, and vanishes at pe ∈ {0, 1}, where the edge state is already known with certainty. This term acts as a natural gating mechanism,
suppressing scouting actions on edges that are already effectively resolved regardless of their potential value change. Together, the three factors reward scouting actions that are nearby, target highly uncertain PBPs, and are consequential to the ground team’s plans—capturing the essential properties of an effective scouting decision in a single interpretable expression. The travel cost and uncertainty terms are computed analytically from known quantities at runtime. The value change PN i term i=1 vc , however, depends on the full graph topology and belief state, and is the central quantity to be estimated. We next describe how this quantity is approximated efficiently using a learned model.
SAPIAP: Integrating IAP into SAP The complete SAP-IAP planner integrates the two components described above. At each planning step, IAP evaluates the priority score vIj (b, ae ) for every candidate scouting action and retains only those exceeding a threshold, reducing the effective branching factor of the drone’s action space. The pruned joint action set is then passed to the POMCP-based SAP solver, which constructs a Monte Carlo search tree over the reduced space to compute the expected cost of each joint action and select the team’s next move. This integration preserves the theoretical guarantees of POMCP — asymptotic convergence to the optimal policy as sample count grows — while substantially reducing the perstep computational cost by eliminating low-value scouting candidates before the tree search begins. The practical effect is a planner that scales to realistic graph sizes and team configurations without sacrificing solution quality, as we demonstrate in the experimental evaluation that follows.
Learning-informed Drone’s Action Pruning PN i Computing the team value change i=1 vc (b, ae ) (Equation 9) exactly at runtime requires Monte Carlo sampling over the full graph and belief state at every decision step — a process that is computationally prohibitive in time-critical scenarios. To address this, we propose a learning-based approach that approximates vci (b, ae ) directly from the graph structure and belief state. A model is trained offline to predict the value change for each edge e and each ground robot i given its start and goal configuration. At runtime, the predicted values are summed across all robots and combined with the analytically computed travel cost and uncertainty terms from Equation 11 to produce the final IAP priority scores.
relevance of a neighboring node’s information depends not only on the node’s features but also on the edge connecting them — specifically its distance and blocking probability. Input Features Each node u in the graph is assigned a binary feature vector xu ∈ R2 encoding its role for a given ground robot: [1, 0] if u is the start node xu = [0, 1] if u is the goal node (12) [0, 0] otherwise Each edge e = (u, v) is associated with a feature vector fe ∈ R2 containing its Euclidean distance de and blocking probability pe : fe = [de , pe ]
(13)
Since the graph is undirected, each edge is stored once in the forward direction. The reverse direction is constructed internally during the forward pass to ensure that information propagates symmetrically between both endpoints. Architecture The model consists of three stages: an input encoding stage, a message passing stage, and an edge-level decoding stage. In the encoding stage, node and edge features are independently projected into a shared d-dimensional latent space through separate linear layers, followed by a ReLU activation. In the message passing stage, the node embeddings are refined over L GATv2 layers. At each layer, every node aggregates information from its neighbors with attention coefficients conditioned on both the neighboring node embeddings and the connecting edge embeddings. A residual connection and Layer Normalization are applied after each layer to stabilize training across graphs of varying size and topology. In the decoding stage, the final node embeddings are used to produce a value change estimate for each edge. For each edge (u, v), an edge representation is constructed by concatenating the embeddings of its two endpoints with a symmetric edge embedding, obtained by averaging the forward and reverse edge features. This concatenated representation is passed through an MLP to produce a scalar output. A Softplus activation enforces non-negativity of the predictions, consistent with the theoretical property that vci ≥ 0 under a costminimizing value function. Certain edges with pe ∈ {0, 1} are masked to exactly zero, as their blocking state is already known and scouting them yields no information gain.
GNN Structure The value change vci (b, ae ) depends on the global structure of the graph: an edge that lies on every shortest path between a robot’s start and goal is far more consequential to scout than one that lies on no shortest path. Capturing this dependency requires reasoning over the entire graph topology simultaneously, which motivates the use of a GNN. We adopt a GATv2 Brody et al. [2022] architecture, which extends the original Graph Attention Network by computing dynamic, content-dependent attention coefficients for each edge. This is particularly suited to our setting because the
Data Generation Training data is generated offline through Monte Carlo simulation. For each training instance, a random graph is sampled with varying topology, edge distances, and blocking probabilities. A single ground robot is assigned a start and goal node, and its node features are constructed according to Equation 12. The ground-truth value change vci (b, ae ) for each uncertain edge is then estimated by sampling the edge’s state and computing the resulting change in the robot’s optimal path cost.
Specifically, for each uncertain edge e with blocking probability pe , the ground-truth label is computed as: vci (b, ae ) = V i (b | ae = block) − V i (b | ae = trav) (14) where each value V i is estimated by averaging the robot’s shortest path cost over M sampled realizations of the remaining uncertain edges, conditioned on the known state of edge e. In our experiments, we use M = 1,000 samples per edge, which provides a sufficiently low-variance estimate for training purposes. Since Monte Carlo estimation introduces sampling noise, the raw labels are clipped to zero from below before training: vci ← max 0, vci
(15)
This is justified by the theoretical guarantee that vci ≥ 0 under a cost-minimizing value function: knowing the true state of an edge can never increase the expected cost of an optimal plan relative to remaining uncertain about it. Certain edges with pe ∈ {0, 1} are assigned a ground-truth label of exactly zero, as their states are already known and scouting them yields no information. The dataset is constructed at the single-robot level: each training example corresponds to one robot’s start–goal pair on one graph instance. For a scenario with N ground robots, this produces N independent training examples from a single graph, naturally augmenting the dataset by a factor of N without additional simulation cost. The model is trained to minimize a weighted Huber loss over all edges, assigning full weight to uncertain edges and a small regularization weight to certain edges to reinforce the boundary condition at pe ∈ {0, 1}: L=
1 X we · Lδ v̂ci , vci |E|
(16)
e∈E
we =
1.0 if pe ∈ (0, 1) λ otherwise
(17)
where Lδ is the Huber loss with threshold δ, and λ ≪ 1 is a small regularization weight applied to certain edges.
a) Bridges Graph
b) Islands Graph
c) Random Graph
Figure 4: Three graph structures represent three environments. The bridges graph represents river-crossing cities with limited bridge connection between two regions. The island graph captures village-style environments consisting of locally dense street with sparse interconnections between clusters. The dense-connected graph models urban areas with high-degree intersections and dense connectivity. Each edge has a possible blocking point Pi with a blocking probability pi . SAP with Distance-based Action Pruning ( SAP- DAP) This variant prunes the drone action set using the distance-based heuristic (Eq. 7), assigning each drone to the PBP nearest to the ground team. The reduced branching factor enables deeper MCTS search, though the heuristic remains myopic: proximity does not guarantee structural relevance to any ground robot’s future plan. SAP with Information Gain Action Pruning ( SAP- IAP) This variant prunes drone actions by their IAP information gain scores (Eq. 11), focusing scouting on edges most likely to alter ground robot behavior. Exact IAP evaluation requires Monte Carlo sampling, however, limiting its applicability to real-time settings. SAP with Learning-informed Action Pruning ( SAP- LIAP) This variant replaces exact IAP computation with a learned model that predicts information gain directly, preserving decision quality while reducing computational overhead to realtime levels.
Environments
We evaluate four planners against the classical Canadian Traveler Problem (CTP) as a baseline, which represents the setting without any scouting drone assistance.
City with river-crossing In this environment, there is a river crossing a city, dividing it into two regions (Fig. 4a). There are several bridges connecting two sides. The environment is modeled as a bridge graph with two group of vertices connecting with each other via some edges. The starting vertices are on the top of the graph while the goals are on the bottom. The bridge on the shortest path connecting start and goal has the highest blocking probability (in range of (0.45 − 0.65), while the bridge of the medium path has a blocking probability of (0.35 − 0.45), and the bridge on the longest path has blocking probability of (0.15 − 0.25). Other edges have blocking probabilities in range of (0.1 − 0.70).
Scout-Assisted Planning (SAP) The base variant considers the full drone action set during Monte Carlo Tree Search (MCTS) search. The large branching factor limits tree depth, making it difficult to identify high-quality scouting decisions.
Rural Villages This environment consists of several villages that have locally dense streets with sparse long interconnections between them. We model the environment as islands graph (Fig. 4b) in which each island is represented
Experiments and Results We evaluated our planning framework, SAP, and its variants under travel cost and runtime as performance metrics across three representative environments: a river-crossing city, dense urban town, and rural villages.
SAP Variants and Baselines
Table 1: Travel distance and runtime of CTP, SAP, SAP - DAP, SAP - IAP, and SAP - LIAP across team configurations of up to 3 UGVs and 2 UAVs on three environments. All planners use 1,000 MCTS rollouts. For SAP - DAP, SAP - IAP, and SAP - LIAP, aggressive pruning is applied: each scouting drone is assigned exactly one action per decision step, corresponding to the highest-scoring candidate under the respective pruning strategy. Travel distance and runtime are reported in meters and seconds, respectively. AP-time denotes the time to compute IAP action values, while plan-time and No. of steps denote planning time in each decision step and number of decision steps, respectively. CTP serves as the baseline for travel cost comparison. Planners UGV
City with river-crossing (Bridges Graph—Fig. 4a) Distances AP plan- No. of time time steps
CTP SAP SAP - DAP SAP - IAP SAP - LIAP SAP SAP - DAP SAP - IAP SAP - LIAP
0 384.4 – 2.7 1 364.0 (↓ 5.3%) – 1.6 1 269.4 (↓ 30.0%) – 2.5 1 239.5 (↓ 37.7%) 100.0 104.0 1 249.2 (↓ 35.2%) 0.75 5.2 2 268.6 (↓ 30.1 %) – 1.8 2 233.1 (↓ 39.4%) – 2.5 2 222.8 (↓ 42.0%) 96.55 99.8 2 221.5 (↓ 42.4%) 0.53 4.1
15 33 31 24 27 33 33 30 33
CTP SAP SAP - DAP SAP - IAP SAP - LIAP SAP SAP - DAP SAP - IAP SAP - LIAP
0 1 1 1 1 2 2 2 2
849.6 709.4(↓ 16.5%) 583.8 (↓ 31.3%) 472.1(↓ 44.4%) 479.5 (↓ 43.6%) 541.5(↓ 36.3%) 470.4 (↓ 44.6%) 438.7 (↓ 48.4%) 445.2 (↓ 47.6%)
– 3.2 – 2.3 – 2.6 128.8 131.9 0.49 5.1 – 2.4 – 2.3 131.6 134.7 0.33 3.8
20 34 32 26 30 34 34 31 33
CTP SAP SAP - DAP SAP - IAP SAP - LIAP SAP SAP - DAP SAP - IAP SAP - LIAP
0 1 1 1 1 2 2 2 2
1301.5 981.0 (↓ 24.6%) 806.1 (↓ 38.1%) 719.5 (↓ 44.7%) 729.8 (↓ 43.9%) 786.4 (↓ 39.6%) 700.6 (↓ 46.2%) 658.7 (↓ 49.4%) 652.6 (↓ 49.9%)
– 3.3 – 2.5 – 2.7 150.5 154.1 0.34 4.8 – 2.4 – 2.5 158.0 161.6 0.24 3.6
24 35 33 29 32 34 34 33 34
Rural villages Dense Urban Town (Islands Graph—Fig. 4b) (Random Graph—Fig. 4c) Distances AP plan- No. of Distances AP plan- No. of time time steps time time steps 1 UGV 342.3 – 2.6 11 288.8 – 3.22 9 346.9 (↓ -1.3 %) – 2.2 31 277.3 (↓ 4.0%) – 2.4 27 248.6 (↓ 27.4%) – 3.6 27 212.9 (↓ 26.3%) – 3.7 25 214.7 (↓ 37.3%) 106.4 110.3 25 196.7 (↓ 31.9%) 130.1 133.4 17 223.4(↓ 34.7%) 0.62 5.6 29 191.7 (↓ 33.6%) 0.61 4.36 22 241.4 (↓ 29.5%) – 2.4 31 250.8 (↓ 13.1%) – 2.5 28 224.3 (↓ 34.5%) – 3.2 31 200.0 (↓ 30.7%) – 3.6 28 206.3 (↓ 39.7%) 97.5 101.3 29 196.7 (↓ 31.9%) 134.5 137.5 17 206.6 (↓ 39.6%) 0.44 5.3 31 189.0 (↓ 34.6%) 0.47 4.2 28 2 UGVs 784.9 – 3.7 19 641.1 – 4.6 14 627.6(↓ 20.0%) – 4.1 32 568.3 (↓ 11.4%) – 3.4 28 452.4 (↓ 42.4%) – 3.1 29 448.4 (↓ 30.1%) – 3.6 26 435.1(↓ 44.6%) 162.0 167.5 27 397.1(↓ 38.1%) 172.5 174.9 20 444.1(↓ 43.4%) 0.42 5.7 28 386.1 (↓ 39.8%) 0.43 4.3 25 494.0(↓ 37.1%) – 2.8 32 514.2 (↓ 19.8%) – 2.6 29 405.3 (↓ 48.4%) – 3.2 31 383.4 (↓ 40.2%) – 3.4 28 413.9 (↓ 47.3%) 168.0 173.7 31 386.4 (↓ 39.7%) 149.9 152.3 26 396.8 (↓ 49.4%) 0.34 5.3 31 363.2 (↓ 43.4%) 0.35 4.0 28 3 UGVs 1190.2 – 3.5 23 994.8 – 4.4 16 923.2 (↓ 22.4%) – 6.8 33 810.1 (↓ 18.6%) – 3.8 29 706.0 (↓ 40.6%) – 7.1 30 667.7 (↓ 32.9%) – 3.7 27 633.3 (↓ 46.8%) 187.0 193.4 27 595.6 (↓ 40.1%) 181.3 183.2 22 651.6(↓ 45.3%) 0.29 5.5 28 598.1(↓ 39.9%) 0.33 4.4 26 793.6(↓ 33.3%)v – 4.9 33 762.4 (↓ 23.4%) – 3.2 30 642.1 (↓ 46.1%) – 6.1 32 575.5 (↓ 42.1%) – 3.4 28 614.4 (↓ 48.4%) 218.0 224.9 31 552.4 (↓ 44.5%) 156.6 159.4 23 624.2(↓ 47.6%) 0.29 5.9 32 537.1 (↓ 46.0%) 0.25 3.9 29
Figure 5: Travel Distances of five planners: CTP, SAP, SAP - DAP, SAP - IAP, and SAP - LIAP with varying number of UGVs and 1 UAV in three environments. The performance of SAP - IAP and SAP - LIAP are comparable in travel cost metric.
We evaluate SAP, SAP with Distance-based Action Pruning (SAP-DAP), SAP-IAP, and SAP with Learning-informed Action Pruning (SAP-LIAP) against the CTP baseline across three environments with team configurations of up to 3 UGVs and 2 UAVs, measuring ground robot travel distance and planning runtime. For SAP-DAP, SAP-IAP, and SAP-LIAP, we apply aggressive pruning in which each scouting drone is assigned exactly one action per decision step—the highest-scoring candidate under the respective pruning strategy. The drone velocity is set to be three times that of the ground robots. Results are reported in Table 1 and Fig. 5.
identifies more consequential scouting targets than proximity alone. For a 1 UGV–1 UAV team, SAP-IAP reduces travel cost by 37.7%, 37.3%, and 31.9% on City with river-crossing, Rural Villages, and Dense Urban Town, respectively — improvements of approximately (8–14) percentage points over SAP-DAP in each environment. With 2 UAVs, SAP-IAP achieves 42.0%, 39.7%, and 31.9% reductions on the three environments, maintaining its lead over SAP-DAP. The behavioral difference between the two strategies is illustrated in Fig. 6. On City with river-crossing (Fig. 6a), the three central bridge edges are structurally critical: their blocking status determines which of the two city regions is accessible, and therefore fundamentally changes the ground robot’s route. IAP correctly identifies these edges as highvalue scouting targets and directs the drone to verify them early, giving the ground robot the information it needs to commit to the shortest viable path. DAP, by contrast, guides the drone toward whichever edges are nearest to the UGV, regardless of structural relevance. This myopic strategy leaves critical edges unverified until later in the mission, causing the ground robot to commit to a path that may require costly backtracking. The same pattern appears on Rural Villages (Fig. 6b), where IAP prioritizes the inter-island connector roads that govern which paths between islands are viable, while DAP wastes scouting effort on nearby but structurally unimportant edges. On Dense Urban Town (Fig. 6c), the advantage of IAP over DAP is less pronounced: the denser connectivity means ground robots can reroute through neighboring edges without incurring significant additional travel cost. reducing the penalty for late or misdirected scouting.
Does scouting guidance reduce ground robot travel cost? Scouting drones improve ground robot planning only when their actions are guided by a pruning strategy. Without pruning, SAP relies entirely on MCTS sampling over the full drone action set, whose exponential branching factor keeps the search tree shallow and scouting decisions uninformed. The result is inconsistent and marginal improvement: a team of 1 UGV and 1 UAV achieves only 4–5% travel cost reduction on City with river-crossing and Dense Urban Town environments, and even slightly underperforms the CTP baseline by 1.0% on Rural Villages environment. Guided pruning changes this picture substantially. SAPDAP , which uses the distance-based heuristic to focus scouting on PBPs near the ground team, reduces travel cost by 30.0%, 27.4%, and 26.3% on City with river-crossing, Rural Villages, and Dense Urban Town, respectively, for a 1 UGV–1 UAV team. The reduced branching factor enables deeper MCTS search, and the locally relevant scouting targets help ground robots avoid committed paths that turn out to be blocked. Adding a second drone accelerates environment coverage further: with 2 UAVs, all planners achieve at least 13% travel cost reduction across all environments, as critical edge statuses are resolved earlier in the mission.
Does the GNN preserve solution quality while achieving real-time speed? Although SAP-IAP achieves the best travel cost among all variants in most environments, its exact IAP computation requires Monte Carlo sampling at every decision step, resulting in planning times that are too long for real-time deployment (Table 1). SAP-LIAP addresses this by replacing exact sampling with a learned GNN model that predicts information gain values directly from the graph structure and belief state. The predicted values are used in place of the sampled ones within the same IAP priority formula, leaving the rest of the planning pipeline unchanged. SAP- LIAP reduces planning time to within seconds per decision step, making it applicable to real-time settings, while achieving travel costs comparable to SAP-IAP, even outperforming in Dense Urban Town environments. The SAP framework also demonstrates scalability to larger ground teams: unlike the approximation-based approach of Stadler et al. [2023], which is restricted to a single ground robot, SAP supports up to 3 UGVs without modification. Adding more ground robots and scouting drones continues to improve team performance, as broader environment coverage resolves edge uncertainty earlier and enables better coordinated routing across the ground team.
Does information gain-based guidance outperform distance-based guidance? SAP-IAP consistently outperforms SAP-DAP across all environments and team configurations, confirming that principled information gain scoring
How many drone action candidates should be retained after pruning? The MCTS search tree grows exponentially with the number of retained drone action candidates, making the choice of pruning aggressiveness critical for both plan-
as a group of 4-5 vertices connected by short edges. The blocked probabilities of the local streets are low (in range of (0.0 − 0.2)). The islands are connected by long edges that have high blocked probability of (0.20 − 0.65). Dense Urban Town In this environment, the traffic system consists of high-degree intersections and dense connectivity. We model this environment as random graphs (Fig. 4c) with 16 vertices (intersections) that are selected randomly with a minimal distance to a neighbor vertex of 20 m. The edges are made by connecting the neighboring vertices using Delaunay triangulation package Virtanen et al. [2020] with maximal distance of 40 m. We limits the number of edges within (28–30). To model a post-diaster event, we set high blocking probabilities for the edges: 40% of them having blocking probabilities in range (0.6 − 0.8), others have blocking values in range of (0.1 − 0.6). The starting positions are the left vertices on the graph, while the goals are the vertices with the longest distance to the corresponding starting vertices.
Results
a) City with river Crossing(Bridges Graph
b) Rural Villages (Islands Graph)
c) Dense-Urban Town (Random Graph)
Figure 6: Behavior of SAP-DAP and SAP-IAP in three type of environments. The purple lines with solid arrow heads represent UGV’s paths, while the blue lines with hollow arrow heads demonstrate UAV’s paths.
ning quality and tractability. To investigate this, we compare retaining 1 versus 2 action candidates under SAP-LIAP and SAP- DAP while varying the MCTS rollout budget from 1000 to 64000, measuring the resulting ground robot travel cost. As shown in Fig. 7, for the distance-based planner SAP-
DAP , retaining only a single action candidate at limited rollout budgets (1000 and 4000) improves planner performance. As the rollout budget increases, the performance difference becomes negligible because the planner has sufficient rollouts to effectively sample two action candidates and select a favorable action for execution.
Meanwhile, retaining a single action candidate for the SAPLIAP planner consistently outperforms retaining two candi-
Figure 7: Performance of SAP-LIAP and SAP-DAP with one and two action candidates after pruning in Dense Urban Town Env.
dates across all rollout budgets. With 1000 rollouts, the single-candidate setting achieves a travel cost of 192.1m, compared to 239.4m for the two-candidate setting — a difference of 47.3m. Increasing the rollout budget only marginally reduces this gap: even at 64000 rollouts, the two-candidate setting reaches 203.9m, which remains 18.7m higher than the single-candidate setting at the same budget (185.2m). This persistent performance gap suggests that the additional branching introduced by a second candidate cannot be sufficiently compensated for through increased sampling within a practical rollout budget. Moreover, these results highlight the effectiveness of the IAP formulation in identifying actions with the highest information gain. Expanding the action set substantially increases computational effort without yielding
corresponding improvements in planner performance. These results confirm that aggressively pruning to the single top-ranked action is not only computationally advantageous but also produces the best planning performance. Therefore, we adopt this setting across all experiments.
Conclusion This paper presents Scout-Assisted Planning (SAP), a heterogeneous planning framework for robot teams operating in partially known environments. SAP introduces a unified graph representation and a shared high-level action abstraction that allows both UGVs and UAVs to operate within a single planning framework, and supports immediate behavior adaptation by ground robots whenever new environmental information becomes available. The core technical contribution is the Information Gainbased Action Pruning (IAP) formulation, which computes per-edge information gain values to focus scouting drones on actions most likely to alter ground robot behavior. To make this tractable for real-time deployment, we develop a GNNbased model that predicts these values directly from graph structure and belief state, reducing planning time from minutes to seconds without sacrificing solution quality. The resulting planner, SAP-IAP, is scalable to teams of up to 3 UGVs and 2 UAVs. Experimentally, our framework consistently outperforms the CTP baseline across all environments and team configurations. With a single UGV and UAV, SAP-IAP reduces ground robot travel cost by 31.9%–37.7% depending on the environment. Travel cost reductions grow further with larger ground teams and additional scouting drones, as broader environment coverage resolves edge uncertainty earlier and enables better coordinated routing. These results confirm that principled, information-gain-guided scouting is both significantly more effective than proximity-based guidance and, with learned value estimation, computationally feasible for real-world deployment.
References Raihan Islam Arnob and Gregory J. Stein. Active information gathering for long-horizon navigation under uncertainty by learning the value of information. In 2024 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS), pages 3036–3042, 2024. Evripidis Bampis, Bruno Escoffier, and Michalis Xefteris. Canadian traveller problem with predictions. In International Workshop on Approximation and Online Algorithms, pages 116–133. Springer, 2022. Zahy Bnaya, Ariel Felner, and Solomon Eyal Shimony. Canadian traveler problem with remote sensing. In IJCAI, pages 437–442, 2009. Shaked Brody, Uri Alon, and Eran Yahav. How attentive are graph attention networks? In International Conference on Learning Representations, 2022. Fanfei Chen, John D Martin, Yewei Huang, Jinkun Wang, and Brendan Englot. Autonomous exploration under uncertainty via deep reinforcement learning on graphs. In 2020
IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 6140–6147. IEEE, 2020. Iddo Drori, Anant Kharkar, William R Sickinger, Brandon Kates, Qiang Ma, Suwen Ge, Eden Dolev, Brenda Dietrich, David P Williamson, and Madeleine Udell. Learning to solve combinatorial optimization problems on realworld graphs in linear time. In 2020 19th IEEE International Conference on Machine Learning and Applications (ICMLA), pages 19–24. IEEE, 2020. Patrick Eyerich, Thomas Keller, and Malte Helmert. Highquality policies for the canadian traveler’s problem. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 24, pages 51–58, 2010. Hengwei Guo and Timothy D Barfoot. The robust canadian traveler problem applied to robot routing. In 2019 International Conference on Robotics and Automation (ICRA), pages 5523–5529. IEEE, 2019. Leslie Pack Kaelbling, Michael L Littman, and Anthony R Cassandra. Planning and acting in partially observable stochastic domains. Artificial intelligence, 101(1-2):99– 134, 1998. Abhish Khanal and Gregory J Stein. Learning augmented, multi-robot long-horizon navigation in partially mapped environments. In 2023 IEEE International Conference on Robotics and Automation (ICRA), pages 10167–10173. IEEE, 2023. Venkatraman Narayanan and Maxim Likhachev. Heuristic search on graphs with existence priors for expensive-toevaluate edges. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 27, pages 522–530, 2017. Evdokia Nikolova and David R Karger. Route planning under uncertainty: The canadian traveller problem. In AAAI, pages 969–974, 2008. Christos H Papadimitriou and Mihalis Yannakakis. Shortest paths without a map. Theoretical Computer Science, 84(1):127–150, 1991. Joelle Pineau and Sebastian Thrun. An integrated approach to hierarchy and abstraction for POMDPs. Carnegie Mellon University, the Robotics Institute, 2002. David Silver and Joel Veness. Monte-carlo planning in large pomdps. Advances in neural information processing systems, 23, 2010. Martina Stadler, Jacopo Banfi, and Nicholas Roy. Approximating the value of collaborative team actions for efficient multiagent navigation in uncertain graphs. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 33, pages 677–685, 2023. Yasmin Veys, Martina Stadler Kurtz, and Nicholas Roy. Generating sparse probabilistic graphs for efficient planning in uncertain environments. In 2024 IEEE International Conference on Robotics and Automation (ICRA), pages 133– 139. IEEE, 2024. Pauli Virtanen, Ralf Gommers, Travis E. Oliphant, Matt Haberland, Tyler Reddy, David Cournapeau, Evgeni
Burovski, Pearu Peterson, Warren Weckesser, Jonathan Bright, Stéfan J. van der Walt, Matthew Brett, Joshua Wilson, K. Jarrod Millman, Nikolay Mayorov, Andrew R. J. Nelson, Eric Jones, Robert Kern, Eric Larson, (...), and Paul van Mulbregt. SciPy 1.0: Fundamental Algorithms for Scientific Computing in Python. Nature Methods, 17:261–272, 2020.