HCOA*: Hierarchical Class-Ordered A* for Navigation in Semantic Environments

Evangelos Psomiadis, Panagiotis Tsiotras

Abstract This letter addresses the problem of robot navigation in mixed geometric/semantic 3D environments. Given a hierarchical representation of the environment, the objective is to navigate from a start position to a goal, while satisfying task-specific safety constraints and minimizing computational cost. We introduce Hierarchical Class-ordered A (HCOA), an algorithm that leverages the environment’s hierarchy for efficient and safe path-planning in mixed geometric/semantic graphs. We use a total order over the semantic classes and prove theoretical performance guarantees for the algorithm. We propose three approaches for higher-layer node classification based on the semantics of the lowest layer: a Graph Neural Network method, a k-Nearest Neighbors method, and a Majority-Class method. We evaluate HCOA in simulations on two 3D Scene Graphs, comparing it to the state-of-the-art and assessing the performance of each classification approach. Results show that HCOA reduces the computational time of navigation by up to 50%, while maintaining near-optimal performance across a wide range of scenarios.

Introduction

As robots transition from controlled industrial settings to complex human-centric environments, navigation must evolve beyond simple geometric obstacle avoidance. Robots need to understand "semantics"—recognizing that a kitchen, a hallway, or a designated "danger zone" carries different operational priorities.

3D Scene Graphs (3DSGs) offer a powerful hierarchical framework for representing these environments. However, planning paths through them presents a computational challenge. High-resolution planning at the "place" level is precise but slow, while high-level "room" planning is fast but risks overlooking critical semantic details, such as a localized hazard within an otherwise safe room. HCOA (Hierarchical Class-ordered A) bridges this gap by integrating hierarchical efficiency with semantically-aware planning.

Methodology

HCOA* operates on multi-layered graphs, such as those representing 3D Mesh, Places, Rooms, and Buildings. The algorithm employs a three-step process:

  1. Top-Down Planning: The search begins at the highest level of abstraction. It identifies an optimal path based on a "total order" of semantic classes (e.g., prioritizing Road over Grass, and Grass over Water).
  2. Hierarchical Pruning: Once a high-level path is established, the algorithm prunes the lower-level graph. It restricts the search to the "children" nodes of the high-level path, significantly reducing the search space.
  3. Semantic Prediction: To classify high-level nodes (like rooms) based on their low-level components, the authors compared three methods: Majority-Class (MC), k-Nearest Neighbors (kNN), and Graph Neural Networks (GNN).
Hierarchical representation of a 3D Scene Graph, showing layers from 3D Mesh to Buildings.

A core innovation is the use of a total order over semantic classes rather than weighted costs. While weighted costs (e.g., "grass is 5x more expensive than road") require tedious tuning, a total order provides a robust guarantee: the robot will never choose a lower-priority path if a higher-priority one is available, regardless of distance (within defined limits).

Robot navigation in a semantic environment where different paths are chosen based on semantic priorities.

Evaluation and Results

The researchers evaluated HCOA using two 3D Scene Graph datasets: the uHumans2 Office Scene and the larger, more complex uHumans2 Subway Scene*.

The results demonstrate significant gains in efficiency:

  • Computational Speedup: The Majority-Class variant (HCOA-MC) reduced execution time by 14% in the office and 49% in the subway* compared to non-hierarchical methods.
  • Search Efficiency: The algorithm expanded 25% to 59% fewer nodes due to hierarchical pruning.
  • Optimality: HCOA maintained high path quality, finding the optimal path in nearly 97% of office scenarios. In the complex subway environment, optimality dropped to approximately 71%*, reflecting the trade-off between speed and perfect precision in irregular geometries.

Interestingly, while GNNs achieved the highest classification accuracy (74%), their inference overhead made them slower in practice. For smaller graphs, the simpler Majority-Class method proved most effective for overall navigation speed.

Conclusion and Future Work

HCOA* successfully demonstrates that hierarchical pruning can drastically reduce the computational burden of semantic navigation. However, the approach is sensitive to the quality of the high-level representation; if a room's connectivity is poorly captured by a single node (the "centroid trap"), the top-down search may miss the global optimum.

Future research will focus on refining high-level representations (e.g., using multiple nodes per room to better represent doors), incorporating temporal logic for time-dependent constraints, and extending the framework for online replanning in dynamic environments.

Summary updated

Abstract

This letter addresses the problem of robot navigation in mixed geometric/semantic 3D environments. Given a hierarchical representation of the environment, the objective is to navigate from a start position to a goal, while satisfying task-specific safety constraints and minimizing computational cost. We introduce Hierarchical Class-ordered A* (HCOA*), an algorithm that leverages the environment’s hierarchy for efficient and safe path-planning in mixed geometric/semantic graphs. We use a total order over the semantic classes and prove theoretical performance guarantees for the algorithm. We propose three approaches for higher-layer node classification based on the semantics of the lowest layer: a Graph Neural Network method, a k-Nearest Neighbors method, and a Majority-Class method. We evaluate HCOA* in simulations on two 3D Scene Graphs, comparing it to the state-of-the-art and assessing the performance of each classification approach. Results show that HCOA* reduces the computational time of navigation by up to 50%, while maintaining near-optimal performance across a wide range of scenarios.
BibTeX
@article{psomiadis2025hcoa,
  author = {Evangelos Psomiadis and Panagiotis Tsiotras},
  title = {{HCOA*: Hierarchical Class-Ordered A* for Navigation in Semantic Environments}},
  journal = {IEEE ROBOTICS AND AUTOMATION LETTERS},
  year = {2025},
  url = {https://openreview.net/forum?id=4qS6OHwRIT},
}
Figure