Decentralized Multi-Robot Exploration with Probabilistic Peer Intent and Multi-hop Plan Propagation

Saurbh Singh Jamwal; Nived Chebrolu; Shivaram Kalyanakrishnan

cs.ROSep 19, 2026

Decentralized Multi-Robot Exploration with Probabilistic Peer Intent and Multi-hop Plan Propagation

Authors: Saurbh Singh Jamwal, Nived Chebrolu, Shivaram Kalyanakrishnan

Organizations: Department of Computer Science and Engineering Indian Institute of Technology Bombay

Abstract

Efficient coordination under limited communication remains a key challenge in decentralized multi-robot exploration. While centralized approaches benefit from global information sharing, they are often impractical in large-scale or communication-constrained environments. Existing Monte Carlo Tree Search (MCTS)-based approaches, such as Decentralized Monte Carlo Exploration (DMCE), enable decentralized planning by taking peer intent into account. This peer intent is obtained by communicating sequences of planned waypoints with robots within direct communication range. In this work, we extend this idea by introducing Probabilistic Peer Intent (PPI), which converts peer trajectories into a continuous spatial representation of predicted intent and incorporates it into local MCTS action evaluation. We additionally study the effects of sharing peer intent beyond direct communication range by propagating plans over multiple hops. Experiments across multiple simulated environments and team sizes show that PPI and Multi-hop propagation can each improve decentralized exploration, with their relative benefits depending on environment structure and team size. We also demonstrate the real-world deployment of our method on three robots operating in different environment types.

Figures & tables

Fig. 1: Multi-robot exploration in two real-world indoor arenas. Online occupancy maps showing the regions explored during execution, together with the trajectories traced by the three robots.

Fig. 2: Overview of the proposed coordination mechanisms. (a) Probabilistic Peer Intent (PPI), where communicated peer trajectories are transformed into spatial intent fields used during local planning. (b) Multi-hop (MH) plan propagation, which extends peer-plan information beyond direct communication neighbors by relaying fresh peer plans while preserving their source identity and generation time.

	Open			Forest			Urban			Tunnel
Method	$\textbf{T90}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$	$\textbf{T90}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$	$\textbf{T90}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$	$\textbf{T90}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$
MCTS (Uncoord.)	150.9	177.0	49.46	94.9	111.4	60.41	162.0	178.6	58.64	97.7	107.5	56.03
RRT	183.1	231.2	20.88	87.3	130.1	40.50	–	–	44.48	317.9	353.5	35.38
MMPF	–	–	48.14	107.2	123.4	54.32	–	–	69.58	–	–	70.11
DMCE	132.1	150.9	32.59	92.0	117.0	49.95	158.9	169.4	53.99	85.5	100.4	50.77
DMCE-Global	89.7	107.8	35.65	69.4	81.3	51.85	132.3	157.7	49.45	70.5	79.6	56.75

TABLE I: Comparison with other methods across environments using 5 robots, averaged over 10 independent runs. Lower is better. Runs are limited to

450

s; “–” indicates that the corresponding coverage threshold was not reached in all 10 runs.

		Forest		Urban		Tunnel
Robots	Method	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$	$\textbf{T95}\downarrow$	$\textbf{Overlap}\downarrow$
5	DMCE	$117.0{\pm}30.6$	$49.95{\pm}6.75$	$\mathbf{169.4{\pm}19.9}$	$53.99{\pm}6.53$	$\mathbf{100.4{\pm}16.1}$	$50.77{\pm}4.96$
	+PPI	$94.5{\pm}18.8$	$47.64{\pm}8.30$	$179.5{\pm}16.8$	$53.42{\pm}8.41$	$106.4{\pm}11.3$	$\mathbf{48.92{\pm}7.23}$
	+MH	$\mathbf{93.2{\pm}17.6}$	$48.58{\pm}7.47$	$170.7{\pm}13.7$	$58.51{\pm}5.76$	$103.2{\pm}13.4$	$49.74{\pm}8.87$
	+PPI+MH	$95.1{\pm}11.7$	$\mathbf{44.08{\pm}8.06}$	$177.0{\pm}16.9$	$\mathbf{51.26{\pm}10.80}$	$117.4{\pm}10.5$	$49.72{\pm}6.59$
8	DMCE	$\mathbf{63.8{\pm}9.2}$	$62.39{\pm}7.08$	$154.9{\pm}20.8$	$\mathbf{70.26{\pm}5.65}$	$\mathbf{91.7{\pm}5.2}$	$\mathbf{60.46{\pm}4.86}$

TABLE II: Component analysis of PPI and Multi-hop propagation across team sizes. Lower is better.

Fig. 3: Exploration behavior and map knowledge distribution. Experiments performed with 12 robots in (a) Forest, (b) Urban, and (c) Tunnel. Top: environment layouts. Middle: normalized coverage over time, with shaded regions indicating variation across 10 independent runs. Bottom: local map knowledge at T95 for the DMCE variants. Each particle represents the average knowledge of one within-run agent computed across the 10 runs. Agents are ranked from least- to best-informed within each run before averaging.

Fig. 4: Conceptual illustration of environment-dependent peer intent. The same spatial peer-intent representation can have different implications in open and topologically constrained environments.

Environment	DMCE	PPI+MH	Relay [%] $\uparrow$
	Payload [kB/s] $\downarrow$
Open	57.74	342.37	26.15
Forest	46.77	230.66	40.18
Urban	46.61	242.56	54.15
Tunnel	78.11	262.18	37.96

TABLE III: Trajectory communication for

N=5

robots. Payload denotes mean serialized payload rate and Relay denotes the fraction of source plans received through relays.

Env.	Method	Mean K. $\uparrow$	Worst K. $\uparrow$	Gap $\downarrow$
		[%]	[%]	[%]
Open	DMCE	78.06	61.98	24.84
Open	PPI+MH	81.32	71.97	14.07
Forest	DMCE	72.65	64.10	13.65
Forest	PPI+MH	69.33	56.15	21.25
Urban	DMCE	90.77	76.30	18.66

TABLE IV: Local map knowledge at T95 for

N=5

. Higher Mean K. and Worst K., and lower Gap, are preferable.

$\lambda_{\mathrm{PPI}}$	T90 [s] $\downarrow$	T95 [s] $\downarrow$	Overlap [%] $\downarrow$
0.1	$73.8\pm 10.5$	$104.9\pm 33.3$	$46.67\pm 9.19$
0.3	$77.3\pm 7.8$	$112.9\pm 21.8$	$44.60\pm 8.99$
0.5	$86.3\pm 9.8$	$126.5\pm 26.6$	$45.84\pm 9.03$
1.0	$\mathbf{77.2\pm 9.7}$	$103.9\pm 15.4$	$48.51\pm 7.13$
2.0	$80.2\pm 14.2$	$\mathbf{97.4\pm 15.3}$	$\mathbf{43.69\pm 12.45}$

TABLE V: Effect of

\lambda_{\mathrm{PPI}}

with

\sigma=1

in Forest for

N=5

. Lower is better.

$\sigma$	T90 [s] $\downarrow$	T95 [s] $\downarrow$	Overlap [%] $\downarrow$
0.5	$76.3\pm 14.9$	$\mathbf{96.9\pm 18.4}$	$46.96\pm 7.98$
0.8	$81.3\pm 14.7$	$104.1\pm 25.8$	$\mathbf{42.97\pm 5.95}$
1.0	$78.1\pm 10.0$	$97.2\pm 17.3$	$44.65\pm 11.15$
1.5	$81.0\pm 18.2$	$110.1\pm 25.8$	$44.47\pm 7.19$
2.0	$75.9\pm 9.3$	$101.0\pm 11.5$	$47.25\pm 6.78$
3.0	$\mathbf{71.5\pm 8.8}$	$107.6\pm 31.4$	$46.83\pm 6.23$

TABLE VI: Effect of

\sigma

with

\lambda_{\mathrm{PPI}}=1

in Forest for

N=5

. Lower is better.

Fig. 5: Hardware validation. The proposed framework is deployed on three TurtleBot3 robots in a cluttered indoor environment using onboard LiDAR with an effective sensing range of 1.5 m and online occupancy mapping. The bottom row shows representative views of the physical testbed with the three robots and their initial positions indicated as R1, R2 and R3, while the top row shows the corresponding occupancy maps and executed trajectories obtained during the exploration.

Explore similar work

Mar 2, 2026

Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning (Extended Version)

Decentralized Monte Carlo Tree Search (Dec-MCTS) is widely used for cooperative multi-agent planning but struggles in sparse or skewed reward environments. We introduce Coordinated Boltzmann MCTS (CB-MCTS), which replaces deterministic UCT with a stochastic Boltzmann policy and a decaying entropy bonus for sustained yet focused exploration. While Boltzmann exploration has been studied in single-agent MCTS, applying it in multi-agent systems poses unique challenges. CB-MCTS is the first to address this. We analyze CB-MCTS in the simple-regret setting and show in simulations that it outperforms Dec-MCTS in deceptive scenarios and remains competitive on standard benchmarks, providing a robust solution for multi-agent planning.

Nhat D. A. Nguyen, Duong D. Nguyen, Gianluca Rizzo +1

Adelaide University, Australia · The University of Foggia, Italy · HES-SO Valais, Switzerland, and The University of Turin, Italy

Monte Carlo Tree Search Multi-Agent Planning Exploration-Exploitation Tradeoff

Ask PDF

Sep 11, 2026

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

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.

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

Ask PDF

Jul 10, 2026

Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints

Multi-UAV exploration is often constrained by unreliable communication, limited field-of-view sensing (e.g., lightweight onboard camera), and finite travel budgets that require each robot to reserve enough budget to return to its base. We present Dec-MARVEL, a decentralized budget-aware exploration framework for communication-free teams with directional sensing. Rather than exchanging maps, goals, or messages, each robot coordinates through its incidental observations: any teammate trajectory within its field of view serves as a coordination signal. A graph-attention actor fuses local frontier geometry, teammate motion, and budget features to select return-feasible waypoint-heading actions. The actor is trained with phase-conditioned critics, a training-only task-oriented privileged critic, and a mixture-based budget curriculum. Across 900 held-out trials spanning three team sizes (2, 4, 8 robots) and three travel budgets (720, 800, 1024 meters) against four baselines, Dec-MARVEL achieves the highest or tied-highest exploration rate and lowest sensing overlap across all nine team-size budget configurations. Under our tightest 720m budget, it reaches 53%, 94%, and 100% success for 2, 4, and 8 robots, versus 37%, 83%, and 99% for the strongest baseline. Physical-robot experiments demonstrate successful sim-to-real transfer and real-world deployment of Dec-MARVEL.

Janghyun Cho, Jimmy Chiun, Guillaume Sartoretti +1

1Dept. of Artificial Intelligence, Sogang University. · 2Dept. of Mechanical Engineering, College of Design and Engineering, National University of Singapore. · 3Dept. of Electronic Engineering, Sogang University.

Aerial Robotics Multi-Robot Exploration Multi-Robot Coordination Decentralized MARL

Ask PDF