HCOA*: Hierarchical Class-Ordered A* for Navigation in Semantic Environments
Evangelos Psomiadis, Panagiotis Tsiotras
AI summary
Problem
Navigating robots in large-scale 3D environments with mixed geometric and semantic data is computationally prohibitive and often fails to efficiently enforce task-specific safety constraints.
Approach
The authors propose a top-down hierarchical search algorithm that prunes semantic graphs layer-by-layer and applies a total order over semantic classes to prioritize safety during planning, supplemented by three methods for predicting higher-layer node semantics.
Key results
- Guarantees path completeness and derives theoretical optimality conditions
- Introduces GNN, k-Nearest Neighbors, and Majority-Class methods for higher-layer node classification
- Reduces computational navigation time by up to 50% compared to state-of-the-art baselines
- Maintains near-optimal path quality across diverse 3D Scene Graph simulations
Why it matters
Provides a scalable, safety-aware planning framework for autonomous robots operating in complex, semantically rich environments.
Abstract
This letter addresses the problem of robot navigation in mixed geometric/semantic 3D environments. Given a hierarchi- cal representation of the environment, the objective is to navigate from a start position to a goal, while satisfying task-specific safety constraintsandminimizingcomputationalcost.WeintroduceHier- archical 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.