Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints
Multi-Agent RLCommunication-Free CoordinationBudget-Aware PlanningConstrained Field-of-View
0 messages
exchanged between robots at deployment
no maps, goals, or task assignments shared
9 / 9
configurations won on exploration rate and overlap
900 held-out trials, 3 team sizes × 3 budgets
−17.7%
distance to 99% coverage, against the best baseline
averaged over the nine configurations
−26.4%
sensing overlap between teammates
robots partition the space without being told to
Abstract
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 720 m 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.
How It Works
Radio links fail in exactly the places worth exploring. Dec-MARVEL drops the radio entirely and coordinates on what a camera happens to catch — a teammate crossing the field of view — while keeping enough battery to fly home.
-
01
A glimpse of a teammate is the whole message
A robot updates its teammate buffer only when another robot is simultaneously inside its sensing range, inside its field of view, and visible through line of sight. When nobody is visible the token is zeroed and masked — never filled in from privileged state. Seeing where a teammate has just been is enough to infer which direction has already been covered.
-
02
Enough budget left to get home
Travel budget is spent by distance, and every candidate move is checked against the shortest graph path back to base plus a safety margin. Actions that would strand a robot are filtered before they can be sampled, and once even standing still is marginal the robot switches to return mode. Feasibility is a hard runtime guard, not a reward term to be traded away.
-
03
Where to go and where to look, chosen together
Each robot maintains a quadtree-backed graph over reachable free space, with a 0.4 m occupancy grid and 4 m nodes. Node utility is kept both as a scalar and as a 36-bin angular frontier histogram, so a sliding field-of-view window can pick the three headings covering the most frontier mass. An action is a waypoint–heading pair drawn from a 5 × 5 neighbourhood.
-
04
Trajectory tokens, not a pooled summary
The last ten observed states of each visible teammate — relative position, heading, and how stale the sighting is — pass through two masked temporal-attention layers with sinusoidal positional encoding. Unlike MARVEL, which pools teammate information into one vector, Dec-MARVEL keeps every agent-time token so each candidate action can cross-attend to the specific motion that matters to it.
-
05
A critic that sees what the actor cannot
During training only, the task-oriented privileged critic labels every cell as uncovered by this robot, covered by a teammate but still unknown locally, or unexplored by the whole team. Twin critics also carry separate heads for before and after mission completion, where the reward structure changes abruptly. The deployed actor keeps none of this.
-
06
A budget curriculum that does not forget
The target budget tightens from 1024 m toward 640 m as a smoothed success rate rises, so difficulty tracks competence. Sixty per cent of episodes still draw a budget uniformly across the whole range, which is what keeps the policy usable at budgets it was never centred on — including the unseen ones used at test time.
Results
Nine configurations — three team sizes crossed with three travel budgets — each run over 100 held-out environments, against four communication-free planners. Switch the metric to see where the differences come from; the numbers behind each chart are one click away.
Two more questions the tables answer: which parts of the training recipe actually matter, and what happens when robots stop working mid-mission.
Hardware Validation
Four ground robots with motion-capture localization, three indoor layouts of 3.6 m × 3.6 m, no radio between them. Waypoints are computed in about 0.3 s, and Dec-MARVEL explores more of each arena than the baseline planners.
Trajectories and sensing footprints overlaid on the real arena. The four robots fan out into separate regions purely from what they catch of one another.
Paper Video
BibTeX
@article{cho2026decmarvel,
title={Dec-MARVEL: Decentralized Multi-Agent Exploration without Communication under Budget Constraints},
author={Cho, Janghyun and Chiun, Jimmy and Sartoretti, Guillaume and Nam, Changjoo},
journal={arXiv preprint arXiv:2607.09060},
year={2026}
}