> ## Documentation Index
> Fetch the complete documentation index at: https://aegean.ai/llms.txt
> Use this file to discover all available pages before exploring further.

# Semantic Graphs and Re-Localization

> Building a semantic property graph from robot detections using Apache AGE, online DBSCAN for place clustering, and CLIP-based landmark fusion for visual re-localization.

This page describes the methodology for building a semantic spatial graph from robot detection events and using it for visual re-localization. The graph is constructed incrementally as the robot explores, stored in Apache AGE (a PostgreSQL graph extension), and queried jointly with pgvector embeddings to infer the robot's location from visual observations alone.

The reference implementation is in the [turtlebot-maze](https://github.com/pantelis/turtlebot-maze) repository. This page builds on the [Object Detection](/aiml-common/lectures/simulation/object-detection) page, which covers the upstream detection and embedding pipeline.

## Problem Statement

A robot explores an environment (Run A), detecting objects and recording where it saw them. Later (Run B), the robot is placed at an unknown location. It captures a few images, detects objects, and needs to determine where it is using only the visual observations and the semantic map built during Run A.

This requires two capabilities:

1. A structured representation of what the robot saw and where  - the semantic graph
2. A query mechanism that matches new observations against stored ones and infers location  - re-localization

## Architecture

The graph builder runs as a standalone service alongside the detection pipeline. Both subscribe to the same Zenoh topic independently.

```mermaid theme={null}
graph LR
    subgraph Detection Pipeline
        DET["Detector<br/>(YOLOv8 + CLIP)"]
    end

    subgraph Zenoh
        ZR["Zenoh Router"]
    end

    subgraph Graph Builder
        GB["graph_builder.py"]
        DBSCAN["Online DBSCAN"]
        FUSE["Landmark Fusion"]
        GB --> DBSCAN
        GB --> FUSE
    end

    subgraph Storage
        PGV["pgvector<br/>detection_embeddings"]
        AGE["Apache AGE<br/>semantic_map graph"]
    end

    DET -->|"tb/detections"| ZR
    ZR -->|"tb/detections"| GB
    ZR -->|"tb/detections"| PGV
    GB -->|Cypher| AGE

    classDef gpu fill:#e65100,stroke:#bf360c,color:#fff
    classDef zenoh fill:#0277bd,stroke:#01579b,color:#fff
    classDef builder fill:#2e7d32,stroke:#1b5e20,color:#fff
    classDef db fill:#37474f,stroke:#546e7a,color:#fff

    class DET gpu
    class ZR zenoh
    class GB,DBSCAN,FUSE builder
    class PGV,AGE db
```

The `det_id` field in the Zenoh payload is the join key between the two databases. pgvector stores the embedding vector; AGE stores the graph structure. Re-localization queries both.

## Graph Schema

The semantic graph uses six node types connected by seven edge types:

```mermaid theme={null}
graph TD
    R["Run"] -->|HAS_KEYFRAME| K["Keyframe"]
    K -->|HAS_POSE| P["Pose"]
    K -->|HAS_OBSERVATION| O["Observation"]
    K -->|IN_PLACE| PL["Place"]
    O -->|OBSERVES| OBJ["Object"]
    OBJ -->|LOCATED_IN| PL
    PL -->|ADJACENT_TO| PL2["Place"]

    classDef node fill:#0277bd,stroke:#01579b,color:#fff
    class R,K,P,O,OBJ,PL,PL2 node
```

| Node        | Key Properties                                             |
| ----------- | ---------------------------------------------------------- |
| Run         | `run_id`, `started_at`                                     |
| Keyframe    | `run_id`, `keyframe_id`, `timestamp`                       |
| Pose        | `map_x`, `map_y`, `map_yaw`                                |
| Observation | `det_id`, `class_name`, `confidence`                       |
| Object      | `object_id`, `class_name`, `mean_x`, `mean_y`, `obs_count` |
| Place       | `place_id`, `centroid_x`, `centroid_y`, `keyframe_count`   |

Each Observation carries a `det_id` that uniquely identifies it across both pgvector and the graph. This enables the cross-database join needed for re-localization.

## Online DBSCAN for Place Construction

As the robot moves, keyframe poses arrive one at a time. These must be clustered into Places (spatial regions like rooms or hallway segments). Standard DBSCAN requires all points upfront. Online DBSCAN processes points incrementally and supports cluster merges  - critical in house environments where the robot enters the same room from multiple doorways.

### Why online DBSCAN over simpler alternatives

Grid binning (divide the map into fixed cells) is simple but produces arbitrary rectangular places that ignore room boundaries. Leader clustering (assign to nearest centroid within radius) is fast but cannot merge two clusters when a new point bridges them. In a house, the robot might enter the living room from the hallway, then later from the kitchen. Leader clustering creates two separate living room clusters that never merge. Online DBSCAN detects the bridge and unifies them.

### Algorithm

For each new keyframe pose `(x, y)`:

1. Compute distances to all existing poses and identify neighbors within epsilon (1.5 m), including self
2. Update neighbor sets of affected existing points
3. Recompute core status: a point is core if it has at least `min_samples` (3) neighbors including itself
4. Determine cluster assignment:
   * If core neighbors belong to one existing cluster, join it
   * If core neighbors span multiple clusters, merge them (lowest place\_id survives, all points relabeled)
   * If no neighboring clusters and the point is core, create a new cluster
   * Otherwise the point is noise (may join a cluster later)
5. Promote noise neighbors that became border points (neighbor of a newly-core point)

Place centroids are maintained as running averages. On merge, centroids are recomputed from the combined member sets.

### Cluster merge example

```
Before:  Place A (kitchen entry)    Place B (hallway entry)
           *  *  *                     *  *  *

After bridge point arrives:
           *  *  *  ---- * ----  *  *  *
                    (bridge)
           All points now in Place A (survivor)
```

## Object Landmark Fusion

The same physical object (e.g. a cup on a table) is detected in multiple keyframes as the robot passes. Landmark fusion merges these repeated observations into a single Object node.

### The position problem

The Zenoh payload includes the robot's map-frame pose but not the object's world position. Without depth data, the observation position used for fusion is the robot's pose at the time of detection, not the object's actual coordinates. This means:

* Multiple objects detected from the same keyframe share the same spatial coordinates
* Spatial distance alone cannot distinguish them
* CLIP embedding cosine similarity is the primary discriminator
* Spatial distance serves as a secondary filter to prevent merging visually similar objects in different rooms

### Algorithm

For each observation with class `C`, robot pose `(x, y)`, and CLIP embedding `e`:

1. Filter existing landmarks to class `C`
2. For each candidate, compute cosine similarity `sim = dot(e, mean_embedding)` (primary filter, threshold 0.7)
3. For candidates passing similarity, compute spatial distance (secondary filter, threshold 3.0 m)
4. Best match above both thresholds: merge (update running averages of position, embedding, count)
5. No match: create new Object node

The landmark's mean position converges toward the centroid of robot poses from which the object was observed. For precise object localization, depth integration would be needed.

## Place Adjacency

Two places are adjacent if the robot drove between them. The graph builder tracks `last_keyframe_place` and creates an ADJACENT\_TO edge (with `shared_transitions` count) whenever consecutive keyframes belong to different places. On cluster merge, adjacency edges from the absorbed place transfer to the survivor.

## Identity and Cross-Database Joins

Every entity has a globally unique identifier that survives service restarts:

| Entity      | ID Format                         | Example                         |
| ----------- | --------------------------------- | ------------------------------- |
| Run         | hostname + timestamp              | `robot-20260324T130000`         |
| Keyframe    | `(run_id, keyframe_id)`           | scoped to run                   |
| Observation | `\{run_id\}_kf\{kf_id\}_d\{idx\}` | `robot-20260324T130000_kf42_d0` |
| Object      | UUID                              | `obj-a1b2c3`                    |
| Place       | `\{run_id\}_p\{counter\}`         | `robot-20260324T130000_p3`      |

The `det_id` on each Observation is stored in both pgvector (`detection_embeddings.det_id`) and AGE (Observation node property). This is the join key for re-localization queries.

## Semantic Re-Localization

Given a robot at an unknown location with a few object observations:

### Step 1: Vector search

Compute CLIP embeddings for query crops and find the top-k most visually similar stored detections:

```sql theme={null}
SELECT det_id, embedding <=> $query_vec AS distance
FROM detection_embeddings
ORDER BY distance
LIMIT 10;
```

### Step 2: Graph traversal

For each matched `det_id`, traverse the graph to find which Place the object is in:

```sql theme={null}
SELECT * FROM cypher('semantic_map', $$
  MATCH (obs:Observation {det_id: 'robot-20260324T130000_kf42_d0'})
        -[:OBSERVES]->(obj:Object)
        -[:LOCATED_IN]->(p:Place)
  RETURN p.place_id, p.centroid_x, p.centroid_y, obj.class_name
$$) AS (place_id agtype, cx agtype, cy agtype, class agtype);
```

### Step 3: Aggregate and rank

Group results by Place, sum similarity scores, rank top-3. The winning Place's centroid is the pose hypothesis.

### Why two databases

pgvector handles the high-dimensional KNN search (optimized vector index). AGE handles the graph traversal (Observation to Object to Place). Combining both in a single query would require scanning embeddings inside Cypher, which AGE is not optimized for. The `det_id` join bridges the two with minimal overhead.

## Bootstrap and Idempotency

All clustering and fusion state lives in memory. On service restart, the graph builder reconstructs its state from the existing AGE graph:

1. Query all Keyframe/Pose nodes for the current run, ordered by keyframe\_id
2. Replay poses through online DBSCAN (without writing, since the graph already has the data)
3. Query all Object nodes to rebuild the landmark index
4. Record the highest keyframe\_id seen and only process newer messages

Idempotency is enforced by checking for existing nodes before creation (MERGE in Cypher). Duplicate `det_id` inserts in pgvector are rejected by the UNIQUE constraint.

## Docker Services

The full pipeline requires these services:

| Service            | Role                                  |
| ------------------ | ------------------------------------- |
| `demo-world-house` | Gazebo house simulation with Nav2     |
| `zenoh-router`     | Zenoh message bus                     |
| `zenoh-bridge`     | DDS to Zenoh bridge                   |
| `detector`         | YOLOv8 + CLIP keyframe detector (GPU) |
| `embedding-ingest` | Writes embeddings to pgvector         |
| `graph-builder`    | Writes property graph to AGE          |
| `vector`           | PostgreSQL + pgvector (port 5436)     |
| `age`              | PostgreSQL + Apache AGE (port 5435)   |

```bash theme={null}
docker compose up -d \
  demo-world-house \
  zenoh-router zenoh-bridge \
  detector embedding-ingest graph-builder \
  vector age
```

***

<Callout icon="pen-to-square" iconType="regular">
  [Edit this page on GitHub](https://github.com/aegean-ai/eaia/edit/main/src/aiml-common/lectures/simulation/semantic-graphs.mdx) or [file an issue](https://github.com/aegean-ai/eaia/issues/new/choose).
</Callout>