A Topological Representation with Object-Path Graphs for Open-Vocabulary Instance Navigation
Linwei Zheng, Daojie Peng, Bingtao Wang, Haoang Li, Jun Ma
cs.RO
2026-09-21
HKUST(GZ) unifies an open-vocabulary object graph with a traversability path graph so agents plan globally and servo locally without dense metric maps, reaching 0.88 SR on relational queries and 0.91 node-transition success.
Vision-language navigation usually takes one of two shapes. Either the instruction is broken into step-by-step actions and error piles up over distance, or the agent explores online with no map and retraces rooms. Scene graphs make a compact semantic memory, but the robot still walks on a dense metric map. The graph reasons; the grid drives.
HKUST(GZ) wants open-vocabulary semantics and topological navigation on one graph: queries land on the object layer, routes are searched on a traversability layer, and edges are executed by visual servoing, without rebuilding a dense metric field.
Open-vocabulary objects come from RGB-D. SAM yields class-agnostic masks, depth back-projects them, and new segments join existing objects by geometric overlap plus CLIP cosine similarity, with point-count weighted feature fusion. Multi-view crops go to a VLM; an LLM collapses the captions into one object description.
The object graph is room-partitioned using a layout projection and a Euclidean distance field. An LLM names each room from the objects inside it. Bounding-box volume splits supporters (beds, desks, cabinets) from smaller regular objects, which may attach to several nearby supporters. Adjacent pairs are sent to an LLM for relations such as on top of / inside / next to. Rooms connect through doorways.
Path nodes appear when view overlap, measured by shared visible objects, drops below a threshold. Doorways are forced in, and uncovered free space is clustered by view similarity. An edge exists if the straight line is collision-free. Extra nodes stitch disconnected components.
Navigation has three stages. A short exploration builds a panoramic semantic descriptor, matched with circular shifts for heading invariance; the most cosine-similar path node is the start. An LLM parses object, supporter, and room from the query, then retrieval walks room → supporter → object. Dijkstra produces a node list. Between nodes the robot does not track a metric pose. It servos to the next node's stored panorama: horizontal angular residuals between matched objects become planar velocity, then unicycle (v, ω). Below a residual threshold, it advances.
Open-vocabulary queries: 120 items, four scenes, object / relation / room+relation. Navigation SPL uses 10 start poses.
| Method | Object SR | Relation SR | Room+rel. SR | Avg SR | Avg SPL |
| ConceptGraphs | 0.58 | 0.63 | 0.60 | 0.60 | n/a |
| VLMaps | 0.60 | 0.70 | 0.75 | 0.68 | 0.234 |
| HOV-SG | 0.63 | 0.75 | 0.85 | 0.74 | 0.37 |
| Ours | 0.68 | 0.88 | 0.93 | 0.83 | 0.408 |
Relational SR jumping from HOV-SG's 0.75 to 0.88 is the hierarchy's main dividend. Node retrieval versus SceneGraphLoc: R@1 wins some scenes and loses others (0.78/0.72/0.88/0.74 vs 0.86/0.80/0.81/0.75); R@5 is comparable. Edge navigation averages NSR 0.91 and path-length ratio 1.23. Snapshots with fewer than eight objects and a 90° FOV drift off path; panoramas are stabler.
Ablation: without supporters, NSR 0.77 and SPL 0.32; the full weighted model is 0.88 / 0.42. The real robot is a Jetson base with an ORBBEC Gemini 336L; edge execution is shown, not scored.
Open-vocabulary home navigation that still maintains occupancy grids and global localization is expensive to ship. This design parks instance retrieval and node walking on one light graph. The controller is analytic visual servoing, not a learned policy. The relational-query jump is evidence that room-supporter-object layers beat flat object embeddings.
SPL is only 0.038 above HOV-SG, so the navigation gain is incremental. The saving is the dense map.
The authors note that inter-node servoing does not smooth the global path; PLR 1.23 is the cost of stops and kinks. Dynamic scenes are future work. The robot trial is qualitative. R@1 loses on two scenes against SceneGraphLoc, and a wrong start node poisons the rest of the search. Mapping still uses odometry, depth, and free-space collision checks, so this is not metric-free; "no dense map" means no dense localization or trajectory optimization at run time. LLM-written relations and room names are not audited for hallucinated edges.