Spatially constrained semantic navigation requires robots to identify targets specified not only by semantic categories but also by relations to surrounding objects. In unknown environments, resolving such goals requires efficient exploration together with sufficient target and contextual evidence for reliable relation verification. Existing methods leave relation-aware verification and multi-robot collaboration largely disconnected: relational navigation is predominantly single-agent, while multi-robot systems seldom coordinate distributed observations for instance-specific relation verification. We propose CoRelNav, whose core is coupling task-conditioned multi-robot exploration with candidate-driven collaborative verification. A spatial-semantic field converts task constraints, scene nodes, and object features into exploration utility; as candidate information accumulates, robots are reallocated toward complementary evidence under team navigation costs, while instance-consistent observations are aggregated across topology nodes. This coupling reduces redundant search and enables relation hypotheses to be resolved from distributed partial evidence that independent exploration or isolated-view verification can leave ambiguous. Experiments in photorealistic simulation demonstrate consistent improvements over representative baselines, with ablations validating the proposed exploration and verification mechanisms. We further deploy the complete system on two physical mobile robots, demonstrating its applicability to real-world collaborative navigation.
Figures & tables
Fig. 1: Example of CoRelNav. Given concurrent category-level and relational goals, two robots collaboratively explore task-relevant regions and acquire cross-view evidence around candidate instances. The spatial relation verifier aggregates complementary observations around the same candidate and confirms bed_3 as the bed between the mirror and the stool, while the sofa is handled as a category-level target.
Fig. 2: Overview of CoRelNav. Relational instructions, topology nodes, and object records form an object-centered task field for multi-robot exploration. Acquisition-aware frontier shortlists are jointly assigned using team unknown-space gain, object and uncertain-target relevance, navigation effort, teammate-history reuse, and navigable frontier separation. Candidate hypotheses are then resolved by candidate-level spatial verification; uncertain cases trigger complementary views and cross-node evidence aggregation before final robot–target navigation. An ordered-assignment hysteresis margin limits unnecessary goal switching.
Fig. 3: Cross-node complementary evidence aggregation for the subtask “find the bed between a shelf and a window.” Node A observes candidate bed_a with shelf_b but lacks window_c , while Node B provides the complementary observation with window_c . Aggregating the two node-level observations around the same candidate hypothesis enables the verifier to confirm that bed_a lies between shelf_b and window_c .
Fig. 4: Progression of CoRelNav on the episode “find a sofa and a bed between a stool and a mirror.” The four panels show (a) verification of the first bed at step 38, (b) discovery of the sofa at step 54, (c) verification of the second bed at step 172, and (d) verification of the third bed and its confirmation as the final target at step 314. In each panel, the main map shows the evolving shared map and robot trajectories, with orange and red point-cloud projections denoting uncertain and final targets, respectively; the side insets show task-conditioned heatmaps, while the bottom rows show the latest panoramic observations from UGV0 and UGV1.
Method
Same-region
Cross-region
SR ↑
SPL ↑
SR ↑
SPL ↑
Greedy
0.648
0.168
0.655
0.166
Cost–Util.
0.675
0.169
0.672
0.175
Co-NavGPT
0.709
0.202
0.701
0.214
CoRelNav
0.716
0.208
0.746
0.252
TABLE I: Performance stratified by spatial distribution.
Method
Object
Relational
Overall
SR ↑
SR ↑
SR ↑
SPL ↑
Tokens/Ep. ↓
Embedding
0.776
0.282
0.224
0.079
–
VLN-Game (Dual)
0.755
0.563
0.395
0.084
189.5
CoRelNav
0.816
0.631
0.513
0.129
91.2
Tokens are reported in thousands per episode.
TABLE II: Main results in mixed multi-task navigation.
Fig. 5: Comparison of VLN-Game (Dual) and CoRelNav on the same episode as Fig. 4 , with the instruction “find a sofa and a bed between a stool and a mirror.” Red and blue curves denote the trajectories of Robot 1 and Robot 2, respectively, and the labeled circles mark their start positions. Target 1 and Target 2 denote the ground-truth sofa and relational bed, while Nav Goal 1 and Nav Goal 2 denote the final navigation goals selected by each method; ✓ / × indicate correct/incorrect target selection. (a) VLN-Game (Dual) verifies the relational candidate using a candidate-marked top view and first-person RGB evidence from the highlighted candidate viewpoint, but selects an incorrect bed. (b) CoRelNav aggregates instance-level evidence from topology nodes N21–N24, with object identities indexed in the inset, and correctly identifies the bed between the stool and the mirror.
Variant
#R
Joint Alloc.
Cross-node Agg.
1-Support
Multi-Support
SR ↑
SPL ↑
SR ↑
SPL ↑
Single-Agent
1
–
✓
0.421
0.099
0.316
0.090
w/o Joint Alloc.
2
×
✓
0.526
0.116
0.395
0.102
w/o Cross-node Agg.
2
✓
×
0.553
0.141
0.342
0.105
CoRelNav
2
✓
✓
0.579
0.143
0.447
0.115
TABLE III: Component ablations by relation complexity.
Fig. 6: Representative real-world execution of “find a fire extinguisher box and the bag near a chair.” The shared map shows their coordinated trajectories, task goals, and topology nodes, while the insets present the corresponding task-conditioned heatmaps and third-person observations.