SEEK-Multi: Collaborative Multi-Agent Semantic Navigation

3.85×

Speedup with 6 Agents

97%

Success Rate

93%

Belief Convergence

8

Comm. Rounds to Converge

Abstract

This paper addresses the fundamental challenge of collaborative multi-agent object-goal navigation for autonomous inspections in complex, real-world environments. While single-agent approaches to object-goal navigation have demonstrated considerable promise, scaling these methods to larger environments necessitates the coordination of multiple robots to achieve efficient coverage, faster task completion, and robust operation under uncertainty.

We introduce SEEK-Multi, a comprehensive framework that extends semantic-guided object inspection to multi-robot systems through distributed belief sharing, collaborative planning, coordinated task allocation, and adaptive communication protocols. SEEK-Multi enables multiple agents to share semantic understanding and inspection findings through a distributed Relational Semantic Network (RSN) and a shared Dynamic Scene Graph (DSG), maintaining consistency across the team while accommodating communication constraints.

We propose novel algorithms for collaborative exploration that leverage semantic priors, belief fusion using consensus protocols with provable convergence guarantees, and conflict-free task allocation based on auction mechanisms. Our extensive simulation analyses demonstrate that SEEK-Multi achieves significant speedup over single-agent approaches while maintaining high success rates, with near-linear scaling efficiency for up to four agents and graceful degradation under communication failures.

Key Features

Semantic Reasoning

Leverages Relational Semantic Networks to encode object-room relationships, enabling intelligent search prioritization based on semantic priors.

Distributed Belief Fusion

Consensus-based protocols ensure beliefs converge across the team while handling communication delays, losses, and correlated observations.

Shared Scene Graphs

Dynamic Scene Graphs maintain hierarchical environment representations with efficient incremental updates and conflict resolution.

Auction-Based Allocation

Market-based task allocation using semantic-aware bidding ensures efficient workload distribution and conflict-free assignments.

Adaptive Communication

Priority-based message protocols balance information sharing with bandwidth constraints, supporting both centralized and decentralized modes.

Robust Operation

Graceful degradation under communication failures, agent heterogeneity, and dynamic environmental changes ensures reliable performance.

System Architecture

SEEK-Multi extends the single-agent SEEK architecture to multi-robot teams through three key components: distributed semantic representations, collaborative planning, and a communication protocol for belief sharing.

Figure 1: SEEK-Multi architecture showing the internal structure of each agent, including the Local DSG, RSN Belief module, Task Allocator, Collaborative Planner, Communication Module, and Belief Fusion components. Agents communicate through a range-limited network to share beliefs and coordinate actions.

Distributed Scene Graph

Each robot maintains a local copy of the Dynamic Scene Graph (DSG) with hierarchical layers representing objects, places, rooms, and building structure. Incremental updates are broadcast and merged using timestamp-based conflict resolution with confidence weighting.

Relational Semantic Network

The RSN encodes object-room relationships learned from training data. Each robot maintains local beliefs over target location, initialized from semantic priors and updated through Bayesian inference from observations and fused beliefs from teammates.

Core Components

Local DSG: Hierarchical representation of the environment (objects → places → rooms → building)
RSN Belief P_i(y_G): Probability distribution over target location based on semantic priors and observations
Task Allocator: Auction-based mechanism for conflict-free task assignment with load balancing
Collaborative Planner: Path planning with intention sharing and priority-based conflict resolution
Communication Module: Priority-queued message passing with bandwidth management
Belief Fusion: Weighted consensus protocol with confidence tracking and correlation handling

Technical Approach

Semantic Prior Model

We leverage semantic priors about object-room relationships, captured in the Relational Semantic Network. The RSN encodes the conditional probability of finding an object class in a room type:

$$P(y^l \in \ell) = \text{RSN}(y^l, \ell)$$

For example, $P(\text{fire extinguisher} \in \text{kitchen})$ captures the prior knowledge that fire extinguishers are commonly found in kitchens.

Distributed Belief Fusion

When robot $r_i$ receives belief $P_j(y_G)$ from robot $r_j$ with confidence $c_j$, it updates its belief using weighted averaging:

$$P_i^{\text{new}}(y_G \in v) = \frac{c_i \cdot P_i(y_G \in v) + c_j \cdot P_j(y_G \in v)}{c_i + c_j}$$

The confidence is updated based on the number and quality of observations:

$$c_i^{\text{new}} = \min\left(c_{\max}, \sqrt{c_i^2 + c_j^2} + \alpha \cdot |\text{obs}_i^{\text{new}}|\right)$$

Auction-Based Task Allocation

We use an auction-based allocation mechanism inspired by market-based multi-robot coordination. Each robot computes bids based on task priority, travel cost, and current workload:

$$\text{Bid}_i(v) = \frac{\text{Priority}(v)}{\text{Cost}_i(v) + \epsilon} \cdot \text{LoadFactor}_i$$

where $\text{Priority}(v) = P(y_G \in v) \cdot \text{Value}(v) \cdot (1 - \text{Searched}(v))$

Algorithm Overview

Algorithm SEEK-Multi-Execute(target_class, time_limit):
    // Initialize distributed representations
    for each agent i in parallel:
        Initialize local_dsg[i], belief[i] from RSN priors
        assigned_tasks[i] ← ∅
    
    while not found and t < time_limit:
        // Phase 1: Sense and update
        observations ← SenseEnvironment()
        UpdateLocalDSG(observations)
        UpdateBelief(observations)
        
        // Phase 2: Communicate
        BroadcastUpdates(dsg_delta, belief, intention)
        received ← ReceiveMessages()
        FuseBeliefs(received)
        MergeDSG(received)
        
        // Phase 3: Plan and allocate
        tasks ← ComputeTaskPriorities(belief)
        assignment ← DistributedAuction(tasks)
        path ← PlanPath(assignment, intentions)
        
        // Phase 4: Execute
        ExecuteAction(path.next_action)
        
    return success, total_path_length

Experimental Results

We evaluate SEEK-Multi through extensive simulations across diverse environment configurations, analyzing scaling behavior, belief convergence, and communication requirements.

Multi-Agent Scaling Performance

SEEK-Multi achieves near-linear speedup for up to 4 agents, with graceful diminishing returns as the team size increases. The system maintains high SPL (Success weighted by Path Length) across all configurations.

Scaling results showing speedup and SPL vs number of agents

Figure 2: Multi-agent scaling performance in medium building environment (100 trials). SEEK-Multi achieves 3.85× speedup with 6 agents while maintaining 97% success rate. The near-linear scaling region extends to 4 agents before diminishing returns.

Belief Convergence Analysis

The distributed belief fusion protocol ensures rapid convergence across all agents. SEEK-Multi achieves 93% entropy reduction in just 8 communication rounds, significantly outperforming pairwise-only communication and independent agent baselines.

Belief convergence showing entropy reduction over communication rounds

Figure 3: Collaborative belief convergence analysis showing information entropy and cross-agent belief divergence over communication rounds. SEEK-Multi achieves 95% convergence by round 8, with the consensus protocol significantly outperforming pairwise and independent baselines.

Communication Range Impact

We analyze the effect of communication range on system performance, identifying optimal operating regions and minimum viable configurations. The system shows graceful degradation in intermittent connectivity scenarios.

Figure 4: Communication range impact on multi-agent coordination. The optimal range (25-35m) balances success rate, completion time, and message overhead. Minimum viable operation requires ~15m range for 60% success rate.

Quantitative Results

Configuration	Success Rate	Speedup	Team SPL	Comm. Msgs
Single Agent (Baseline)	94.2%	1.00×	0.84	—
2 Agents	95.8%	1.87×	0.81	124
3 Agents	96.4%	2.59×	0.78	218
4 Agents	96.9%	3.10×	0.75	342
5 Agents	97.1%	3.53×	0.71	456
6 Agents	97.3%	3.85×	0.68	589

Comparison with Baselines

Method	SR (%)	SPL	Time (s)	Coordination
SEEK-Multi (Ours)	96.9	0.75	45.2	Semantic + Auction
Frontier-Based Multi-Robot	89.3	0.58	72.8	Geometric
Random Allocation	78.4	0.42	98.3	None
Greedy Distance	85.1	0.51	81.5	Local
MCTS Coordination	92.7	0.68	56.4	Centralized

Applications

Industrial Inspection

Autonomous monitoring of manufacturing facilities, warehouses, and production lines for equipment status and safety compliance.

Search and Rescue

Rapid, coordinated search of disaster sites and collapsed structures to locate survivors and assess hazards.

Domestic Robotics

Multi-robot household assistance for object retrieval, cleaning coordination, and elderly care support.

Security Patrols

Coordinated surveillance of large facilities with intelligent coverage optimization and anomaly detection.

Healthcare Logistics

Autonomous delivery and inventory management in hospitals, clinics, and pharmaceutical facilities.

Energy Infrastructure

Inspection of power plants, substations, and renewable energy installations for maintenance and safety.

SEEK-Multi

Collaborative Multi-Agent Semantic Reasoning for
Object Goal Navigation in Inspection Tasks

SEEK-Multi enables teams of robots to collaboratively search for and inspect target objects through distributed semantic reasoning, belief sharing, and coordinated task allocation.

Abstract