Semantic Area Graph Reasoning for Multi-Robot Language-Guided Search

Coordinating multi-robot systems (MRS) to accomplish complex tasks in unknown environments is a fundamental challenge in robotics. Traditional multi-robot task allocation (MRTA) approaches formulate coordination as assigning robots to tasks in a way that optimizes system-level performance. These methods include centralized optimization-based methods and decentralized strategies such as auction-based mechanisms. However, these methods often rely on geometric objectives and struggle to effectively incorporate semantic information for task allocation and execution. Recent advances in foundation models have introduced new opportunities for integrating high-level reasoning into robotic systems. Large Language Models (LLMs) and Vision-Language Models (VLMs) have demonstrated strong capabilities in multimodal reasoning, semantic grounding, and long-horizon decision making. These capabilities have motivated growing interest in applying foundation models to multi-robot coordination.

Exploration and search in unknown environments typically rely on geometric objectives derived from occupancy maps, such as frontier boundaries or information-gain metrics. While modern robotic systems increasingly have access to semantic information through perception and mapping pipelines, existing coordination strategies still primarily rely on geometric objectives. Consequently, they cannot effectively incorporate these semantic priors or high-level task descriptions when coordinating robot teams, often resulting in exploration strategies that lack context-aware prioritization.

This paper introduces a hierarchical framework called Semantic Area Graph Reasoning (SAGR), which coordinates multi-robot exploration and semantic search through a structured semantic-topological abstraction. SAGR incrementally constructs a semantic area graph from a semantic occupancy map, encoding room instances, connectivity, frontier availability, and robot states into a compact task-relevant representation. Large Language Models (LLMs) perform high-level semantic room assignment based on spatial structure and task context, while deterministic frontier planning and local navigation handle geometric execution within assigned rooms. This approach fundamentally differs from existing methods that rely on high-dimensional visual observations or dense occupancy maps.

• �� The SAGR framework coordinates multi-robot exploration and semantic search through semantic area graph reasoning. • Semantic area graphs are incrementally constructed from semantic occupancy maps, encoding room instances, connectivity, frontier availability, and robot states into a compact task-relevant representation. • Large Language Models (LLMs) perform high-level semantic room assignment based on spatial structure and task context. • Deterministic frontier planning and local navigation handle geometric execution within assigned rooms. • Experiments are conducted on the Habitat-Matterport3D dataset across 100 scenarios to evaluate SAGR's performance in large environments.

Experiments are conducted on the Habitat-Matterport3D dataset across 100 scenarios to evaluate SAGR's performance in large environments. The experimental design includes: 1) selecting 10 different apartment layouts; 2) generating 10 scenarios for each layout by randomly sampling robot initial poses and target object locations; 3) comparing SAGR's performance with geometric coordination strategies, including Hungarian Frontier Assignment, RACER, and AEP + DVC. All methods are evaluated under the same map representation, sensing configuration, robot initialization protocol, and task setup.

Experiments demonstrate that SAGR improves semantic target search efficiency by up to 18.8% in large environments, while maintaining competitive exploration performance with state-of-the-art methods. SAGR compresses dense semantic occupancy maps into a compact room-level semantic graph, preserving task-relevant information including room semantics, spatial connectivity, frontier availability, and robot occupancy. The results highlight that SAGR achieves efficient multi-robot coordination in complex indoor environments, consistently improving semantic target search efficiency compared to state-of-the-art exploration baselines.

The SAGR framework has broad potential applications in multi-robot tasks requiring semantic reasoning. Direct application scenarios include: 1) indoor target object search, such as locating lost items or equipment in specific rooms; 2) navigation tasks in complex buildings, such as guiding tours in hospitals or malls. SAGR's structured semantic abstraction opens new possibilities for applying large language models in robotic systems, particularly for tasks requiring semantic reasoning.

Despite SAGR's impressive performance in semantic target search, it may face challenges in dynamic environments as the construction of semantic area graphs relies on static semantic occupancy maps. Additionally, the reliance on large language models may limit SAGR's applicability in real-time decision-making due to computational resource constraints. SAGR's performance may degrade in the absence of sufficient semantic information, particularly when the target room type has not yet been discovered. Future research directions include extending SAGR to handle changes in dynamic environments and optimizing the computational efficiency of large language models.