PRoID: Predicted Rate of Information Delivery in Multi-Robot Exploration and Relaying

Seungchan Kim; Seungjae Baek; Micah Corah; Graeme Best; Brady Moon; Sebastian Scherer

cs.ROApr 12, 2026

PRoID: Predicted Rate of Information Delivery in Multi-Robot Exploration and Relaying

Authors: Seungchan Kim, Seungjae Baek, Micah Corah, Graeme Best, Brady Moon, Sebastian Scherer

Organizations: Carnegie Mellon University Robotics Institute · Ulsan National Institute of Science & Technology · Colorado School of Mines · University of Technology Sydney ·

Abstract

We address Multi-Robot Exploration and Relaying (MRER): a team of robots must explore an unknown environment and deliver acquired information to a fixed base station within a mission time limit. The central challenge is deciding when each robot should stop exploring and relay: this depends on what the robot is likely to find ahead, what information it uniquely holds, and whether immediate or future delivery is more valuable. Prior approaches either ignore the reporting requirement entirely or rely on fixed-schedule relay strategies that cannot adapt to environment structure, team composition, or mission progress. We introduce PRoID (Predicted Rate of Information Delivery), a relay criterion that uses learned map prediction to estimate each robot's future information gain along its planned path, accounting for what teammates are already relaying. PRoID triggers relay when immediate return yields higher information delivery per unit time. We further propose PRoID-Safe, a failure-aware extension that incorporates robot survival probability into the relay criterion, naturally biasing decisions toward earlier relay as failure risk grows. We evaluate on real-world indoor floor plan datasets and show that PRoID and PRoID-Safe outperform fixed-schedule baselines, with stronger relative gains in failure scenarios.

Figures & tables

Fig. 1: Multi-robot exploration must not only cover unknown environments but also deliver collected information to a base station in time. PRoID enables adaptive relay decisions by comparing each robot’s current observed coverage against its predicted future sensor coverage along the planned path.

Fig. 2: Overview of PRoID : robots explore unknown environments and share map data when in range. Each robot tracks its unique unreported information and continuously evaluates whether to continue exploring or relay to the base, based on comparing current and predicted future rates of information delivery.

Fig. 3: (a) Robot 1 shares its map with Robot 2, delegating overlapping coverage (blue) and retaining its unique unreported area (green). (b) Robot 1 estimates predicted sensor coverage along its planned path (orange) and compares current vs. predicted rate of information delivery–deciding to continue exploring. (c) After further exploration, the current rate exceeds the predicted rate, triggering relay to the base station.

Fig. 4: Five Test Maps from KTH Indoor Floorplan Dataset [ 28 ] .

Fig. 5: (Left) At

T=400

, R1 delegates observed area (blue) to R3. R2, out of range of R3, still learns these areas are delegated via R1. (Right) Each robot compares unique unreported area (green) against predicted future coverage (orange). R1 relays (small predicted coverage); R2 explores; R3, having fully delivered all data, continues exploring.

Fig. 6: Quantitative comparison of PRoID against fixed-schedule baselines in the no-failure scenario, and PRoID-Safe in failure-prone scenarios ( $\lambda\in\{1100,900\}$ ). Our methods consistently outperform baselines in total information delivered to the base station.

	No Failure Scenario				Failure Scenario ( $\lambda=1100$ )				Failure Scenario ( $\lambda=900$ )
Method	$n{=}2$	$n{=}3$	$n{=}4$	$n{=}5$	$n{=}2$	$n{=}3$	$n{=}4$	$n{=}5$	$n{=}2$	$n{=}3$	$n{=}4$	$n{=}5$
Periodic Relay ( $P=100$ )	32.8	41.3	51.5	57.1	24.3	37.4	46.2	48.2	17.7	24.9	44.4	47.1
Periodic Relay ( $P=200$ )	40.9	51.6	59.0	68.2	30.7	45.8	55.8	56.8	21.9	33.7	53.7	56.9
Periodic Relay ( $P=300$ )	46.4	56.0	61.8	65.7	35.7	50.9	58.9	59.2	25.6	35.5	56.6	56.7
Final Relay Only	58.4	67.1	68.9	71.4	18.8	49.1	63.0	66.4	16.5	37.2	53.6	61.0
PRoID (Ours)	58.2	68.4	72.3	73.5	34.0	57.4	65.1	68.2	32.3	42.0	58.3	60.1

TABLE I: Coverage ratio (%) at mission end, averaged over all test configurations. Best results per column in bold .

System Components
Configuration	Coverage (%)
PRoID Full System (Ours)	67.9
w/o Relay Handoff	59.8
w/o Traj. & Plan Sharing	53.5
Effect of $\alpha$ — PRoID
$\alpha=1.0$	49.0

TABLE II: Ablation study. Coverage ratio (%) at

n=3

, averaged over test configurations (no-failure scenario).

Fig. 7: (Top) Final Relay Only robot fails at

T=560

before returning, losing all data. (Middle) At

T=320

, PRoID-Safe triggers relay despite

\Gamma_{\text{now}}<\alpha\Gamma_{\text{pred}}

, as survival probability shifts the criterion (

\Gamma_{\text{now}}S_{\text{now}}>\alpha\Gamma_{\text{pred}}S_{\text{pred}}

). (Bottom) Data already relayed; robot continues exploring safely.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

parameter	value
$\text{Communication Range}\quad d$	10m
$\text{Raycast Range}\quad l$	20m
Frontier penalty distance:
For trajectories $\epsilon_{\text{traj}}$	5m
For plans $\epsilon_{\text{plan}}$	10m
Frontier penalty value $\gamma$	$10^{6}$

Appendix

TABLE A.1: Hyperparameters of PRoID and PRoID-Safe

Parameter	Value
Number of map predictors in ensemble	3
Probabilistic raycast threshold	0.5
Use distance transform in planning	True
Hypothetical laser range	20m
Number of hypothetical lasers	250
Path sampling interval for raycast	25 points

Appendix

TABLE A.2: Hyperparameters of PIPE Planner [ 26 ] (map-prediction-based frontier exploration baseline)

Multi-Robot Exploration

Multi-robot exploration coordinates robot teams to map unknown environments, find targets, and gather information efficiently and safely.

See all 52 papers

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows
Sep 11, 2026Ben Rossano, Jaein Lim, Jonathan P. HowMulti-Robot Exploration Multi-Agent Communication
Aerospace Controls Lab, Massachusetts Institute of Technology, Cambridge, MA, USA · Draper Scholar with the Charles Stark Draper Laboratory, Cambridge, MA · Charles Stark Draper Laboratory, Cambridge, MA, USA
OpenSpace Lab Solution to the IROS 2026 Indoor Exploration Competition
Oct 1, 2026Yuxuan Zhang, Dong Li, Zezhou Sun +5Robot Navigation Multi-Robot Exploration
China University of Mining and Technology-Beijing · Macau University of Science and Technology · Institute of Automation, Chinese Academy of Sciences +3
DORA: Divergence-Oriented Data-Relay Algorithm for Partially Connected Robot Teams
Sep 28, 2026Jonathan Diller, Fernando Cladera, Camillo Jose Taylor +1Aerial Robotics Multi-Robot Systems
GRASP Laboratory, University of Pennsylvania, Philadelphia, PA 19104, USA

Sep 11, 2026J/K move · Enter open · S save

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

Ben Rossano, Jaein Lim, Jonathan P. How

Aerospace Controls Lab, Massachusetts Institute of Technology, Cambridge, MA, USA · Draper Scholar with the Charles Stark Draper Laboratory, Cambridge, MA · Charles Stark Draper Laboratory, Cambridge, MA, USA

Multi-Robot Exploration Multi-Agent Communication

Open paper AskPDF arXiv

Exploring unknown environments with multi-robot teams can improve efficiency by allowing robots to explore in parallel. However, realizing these gains requires effective information sharing. When communication is intermittent, robots must balance the benefits of sharing information against the cost of diverting from exploration to establish communication. This paper introduces MACE, a decentralized exploration framework that actively evaluates whether establishing communication is worthwhile. At scheduled communication windows, robots estimate the cost of reaching previously identified communication locations. By formulating this decision as a variant of the Vehicle Orienteering Problem, robots evaluate routes based on the travel required to establish communication and the exploration that can be completed along the way. This approach enables robots to communicate more frequently than under purely opportunistic strategies while reducing the unnecessary travel associated with fixed rendezvous strategies. Across a set of simulated environments with varying size and geometry, we demonstrate that MACE reduces the total exploration time by up to 23% compared to existing communication-constrained exploration strategies.

Abstract

Multi-Robot Exploration

Explore similar work

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

OpenSpace Lab Solution to the IROS 2026 Indoor Exploration Competition

DORA: Divergence-Oriented Data-Relay Algorithm for Partially Connected Robot Teams