Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments

Hoang-Dung Bui, Abhish Khanal, Raihan Islam Arnob, Gregory J. Stein · George Mason University · 2026

Summary

SAP pairs aerial scouts with ground robots to gather environmental information ahead of time, reducing mission time by 40% through information-theoretic POMDP planning.

Abstract Summary

Multi-robot teams navigating partially known environments suffer costly delays when ground robots encounter impassable terrain only visible at close range. Scout-Assisted Planning (SAP) pairs fast aerial scouts with slower ground robots to gather environmental information ahead of time, enabling informed path selection before ground robots commit to potentially blocked routes. SAP formalizes the problem as a Partially Observable Markov Decision Process (POMDP) in which scout actions are explicitly modeled as information-gathering operations. A belief-space planner dynamically allocates scout missions based on expected information gain and the anticipated reduction in ground-robot plan cost. When a scout reveals a blocked road, the ground robot replans immediately rather than backtracking after physical traversal, saving both time and energy. The framework is evaluated in simulation on forest and urban navigation scenarios with a heterogeneous team consisting of a quadcopter and a Clearpath Husky ground robot. Results show a 40 percent reduction in total mission time compared to baseline replanning methods that do not use scouts. The method is also validated on a physical heterogeneous robot team, demonstrating real-world feasibility without perfect prior maps.

Key Points

Formalizes heterogeneous team planning as a belief-space POMDP.
Aerial scouts gather information ahead of ground robot traversal.
Dynamic mission allocation based on information gain and cost reduction.
Validated on quadcopter and Clearpath Husky in forest and urban scenarios.
Reduces total mission time by 40% compared to baseline replanning.

Problem Formulation

We consider a heterogeneous robot team consisting of two sub-teams: a ground team of $N$ ugv sand a scout team of $M$ uav s, 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.

Problem Formulation — Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments — Figure 2: Abstract Actions for both uav s ugv s . The ugv has two actions: move to {$\textsc{b}_{1},\textsc{b}_{2}$}, while the uav has a action set of all unvisited pbp s{$\textsc{b}_{1},\textsc{b}_{2},\ldots,\textsc{b}_{10}$}.

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.

Learning-informed Drone’s Action Pruning

Computing the team value change $\sum_{i=1}^{N}v_{c}^{i}(b,a_{e})$ (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 $v_{c}^{i}(b,a_{e})$ 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.

Learning-informed Drone’s Action Pruning — Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments — 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 $\textsc{p}_{i}$ with a blocking probability $p_{i}$.

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 . We evaluate four planners against the classical Canadian Traveler Problem ( ctp ) as a baseline, which represents the setting without any scouting drone assistance.

The base variant considers the full drone action set during Monte Carlo Tree Search ( mcts )search.

Experiments and Results — Scout-Assisted Planning for Heterogeneous Robot Teams under Partially Known Environments — Figure 5: Travel Distances of five planners: ctp , sap , sap-dap , sap-iap , and sap-liap with varying number of ugv sand 1 uav in three environments. The performance of sap-iap and sap-liap are comparable in travel cost metric.

Sources and Demonstrations

Figures are reproduced from Bui et al. See the full paper for experimental details and the project page, when the paper links one, for demonstrations and videos.