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

Boltzmann-based Exploration for Robust Decentralized Multi-Agent Planning (Extended Version)
Mar 2, 2026Nhat D. A. Nguyen, Duong D. Nguyen, Gianluca Rizzo +1Monte Carlo Tree Search Multi-Agent Planning
Adelaide University, Australia · The University of Foggia, Italy · HES-SO Valais, Switzerland, and The University of Turin, Italy
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
Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints
Jul 10, 2026Janghyun Cho, Jimmy Chiun, Guillaume Sartoretti +1Aerial Robotics Multi-Robot Exploration
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.

Mar 2, 2026J/K move · Enter open · S save

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

Nhat D. A. Nguyen, Duong D. Nguyen, Gianluca Rizzo, Hung X. Nguyen

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Communication-Constrained Multi-Robot Exploration With Adaptive Communication Windows

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