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:
- 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).
- 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.
- 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).
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).
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