ReVoLT: Relational Reasoning and Voronoi Local Graph Planning
for Target-driven Navigation

As illustrated in Fig. 2 (a), the object-to-object relationship consists of not only pair-wise semantic similarity, but also distances and the number of hops between object pairs. We first extract an object-level graph $\mathcal{G}_{o}(\mathcal{V}_{o},\mathcal{E}_{o})$ through object positions $pos$ and category $\mathcal{C}_{o}$ from Matterport3D dataset. Objects in the same room are fully connected. As for object pairs in different rooms, only those closest to a common door have an connecting edge. This is useful for the robot to infer objects that are strongly related to the target just using object-level embedding.

GraphSAGE [8] is a popular model in the node embedding field. We adopt it to obtain the embedding of each object category to fuse semantics and proximity relationships with other categories. Our node embedding procedure uses GloVe [17] as the initial node semantic feature $\left\{\mathbf{x}_{v},\forall v\in\mathcal{V}_{o}\right\}$, and employ an unsupervised form of GraphSAGE with a loss that penalizes the embedding similarity between two objects far apart and reward the adjacent two. Different from the original GraphSAGE, edge features $\left\{\omega_{e:u\rightarrow v},\forall e\in\mathcal{E}_{o}\right\}$ are also taken into account in aggregation and loss calculations. For each search depth $k$, weight matrices $\mathbf{W}^{k},\forall k\in\{1,\dots,K\}$, we employ an edge-weighted mean aggregator which simply takes the element-wise mean of the vectors in $\{h^{k-1}_{u},\forall u\in\mathcal{N}(v)\}$ to aggregate information from node neighbors:

Then an edge-weighted loss function is applied to the output $\{\mathbf{z}_{v},\forall v\in\mathcal{V}_{o}\}$, and tune the weight matrices $\mathbf{W}^{k}$:

where $P_{n}$ is a negative sampling distribution, $Q$ defines the number of negative samples, $\sigma$ is the sigmoid function.

Since object embeddings with the same category $\{\mathbf{z}_{c},\forall c\in\mathcal{C}_{o}\}$ should have consistent representation, another mean aggregation is performed on the embeddings of same category between the final GraphSAGE aggregation and loss function. This overwrites the original value with the final embedding for each category $\{\mathbf{z}_{c}\leftarrow\text{mean}(\mathbf{h}_{v}^{K}),\textrm{if }\mathcal{C}_{o}(v)=c\}$.

Apart from the pairwise relationship between objects, the many-to-one relationship between an object and a room or region is also indispensable for inferring the existence possibility of the target object in a certain room or among multiple observed objects. Besides, to evaluate the similarity, relationships of different levels should have a unified paradigm to obtain representation of consistent metrics. Therefore, for region-level sub-graphs, we still opt for the same embedding representation procedure. This part is shown in Fig. 2 (b).

Region embedding is carried out in a self-supervised form. We take the sub-graph $\mathcal{G}_{r}(\mathcal{V}_{r},\mathcal{E}_{r})$ as input, with embedding of objects in the same region $\{\mathbf{z}_{c},\forall c\in\mathcal{C}_{o}\}$ as nodes and weighted spatial distances as edges. The batch composed of these sub-graphs is passed into the GCN[18], and the corresponding region embedding $\{\mathbf{r}_{v},\forall v\in\mathcal{V}_{r}\}$ is obtained. Similarly from the previous procedure, for region embedding with the same label, a mean aggregation is performed to obtain a uniform vector representation $\{\mathbf{r}_{l},\forall l\in\mathcal{L}_{r}\}$. Since there is no need to do multi-hop aggregations at region-level, a simple GCN layer is applied rather than GraphSAGE.

To enable membership calculation between region embedding $\mathbf{r}_{l}$ and object embedding $\mathbf{z}_{c}$ and distinguish regions with different labels, we use a combined loss which comprises two parts: the classification loss of embedding label and the membership loss of object-in-region:

where $P_{n}(v)$ represents objects not in region $v$, and $\hat{l}(\cdot)$ is a multi-layer perceptron (MLP) network.

As the third and most important part of relation extraction, the structural relationship reasoning ability plays a crucial role in understanding the correct direction of navigation and shortening the exploration period. To achieve this, the joint probability $p(\mathcal{G}_{h})$ of houses need to be learned to conceive a probable house layout memory $\mathcal{G}_{h}\sim p(\mathcal{G}_{h}|\mathcal{G}_{sub})$ conditioned on observed regions $\mathcal{G}_{sub}$. However, its sample space might not be easily characterized. Thus, the house graphs are modeled as sequences by following the idea of GraphRNN[19], and redefine some concepts to make it more suitable for conditional reasoning with embedding. This part is shown in Fig. 2 (c).

where $\pi$ represents the node order, and each element $A_{i}^{\pi}\in\{0,1\}_{(i-1)\times(i-1)},i\in\{1,\ldots,n\}$ is an adjacent matrix referring the edges between node $\pi(v_{i})$ and its previous nodes $\pi(v_{j}),j\in\{1,\dots,i-1\}$ already in the graph.

Since each $A_{i}^{\pi}$ has variable dimensions, we first fill them up to the maximum dimension $n$ and then repeat the 2D matrix 16 times to form a 3D matrix with $n\times n\times 16$ dimensions as an edge mask where 16 is the embedding length. Therefore, a featured graph can be expressed as the element-wise product of the region embedding matrix $X^{\pi}$ under corresponding order and sequence matrix $\{S^{\pi}\}^{3D}$:

where $X_{i-1}^{\pi}$ is the embedding matrix with $(i-1)\times(i-1)\times 16$ dimensions referring to region embeddings before region $\pi(v_{i})$, and $\mathbf{x}_{i}^{\pi}$ refers to the embedding of $\pi(v_{i})$.

Passing $\{S^{\pi}\}^{3D}\odot X^{\pi}$ as a sequence into GRU or LSTM, we can get the structure distribution of houses. This allows us to predict the next region embedding and label under the condition of the observed subgraph. The loss function of the Region Rollout network is a CrossEntropy between generated embedding label and the real label:

In conclusion, with the combination of III-A unsupervised edge-weighted GraphSAGE object embedding learning, III-B self-supervised GCN region embedding learning, and III-C c-GraphRNN conditional region rollout, we can now extract multiform structural relationships. Meanwhile, embedding is used as a unified paradigm for representation, and the similarity between objects or regions (either observed or predicted) embeddings and the target object embedding is used as a prior to guide the exploration in an unknown domain.

A prior alone cannot lead to success. Inspired by [13], a posterior topological representation is also constructed in each specific task to combine experience with practice. Specifically, we build a multi-layer posterior topological graph covering all object-level, clique-level and vertex-level. clique divides rooms into small clustered regions and reduces the burden of the visual front-end. Each vertex governs the three nearest cliques. Object Embedding network provides the object node features, and Region Embedding network generates the features of both clique and vertex from their attached objects. Region Rollout network gives an evaluation about ghost nodes. However, there are always situations contrary to experience in reality. In other words, robots must have the ability to balance exploration and exploitation online.

We adopt Upper Confidence Bound for Tree (UCT) method[20] to set an online bonus. The simulation procedure of UCT is supported by the Region Rollout network, thus the robot is not only able to obtain the bonus from reached count, but also estimate the future exploration value inductive bias $\omega_{i}$ of selected path. It can effectively prevent the robot from being trapped in a useless area. The combined effect of inductive bias $\omega$ and bonus will discourage the repetitive search near negative (non-success) sub-goals and drive the robot to return to parent nodes for back-tracking, which we term Revolt Reasoning. The word Revolt summarizes the characteristics of our method vividly, which allows robots to regret at nodes with low exploration value, discarding them and returning to previous paths. To avoid robots wandering between two goals, it is necessary to introduce a navigation loss term $\mathcal{L}_{dis}$ to penalize node distances. Hence, we can finally obtain the exploration value $\mathbf{V}$ of the node $i$ as:

where factors $c_{1}$ and $c_{2}$ are set as 1 and 0.5. $j$ refers to one of node $i$’s descendants in the tree, and $m$ is its total number. $N_{i}$ is the total arrivals of node $i$ and its descendants, while $n_{i}$ just represents arrivals of node $i$.

The reasoner only gives a semantic node id in a graph as a sub-goal. If the low-level controller directly uses it as a navigation goal, it will inevitably lead to over-coupling and increase the difficulty of navigation success. We can refer to the hierarchical human central nervous system composed of the brain, cerebellum, brain-stem and spinal cord[21], if the high-level reasoner is compared to the brain, then the skeletal muscle is the low-level motor controller. The brain does not directly transmit motion instructions to the skeletal muscles, but passes it through the brain-stem, spinal cord and other lower-level central nervous system for information conversion[22]. Besides, the brain does not actually support high-speed, low-latency information interaction while controlling a motion[23]. Therefore, it is necessary to use a RGB-D camera and an odometer to construct a local Voronoi graph, offering approximate relative coordinates of the sub-goal within a reachable range as an input to the low-level controller. The Voronoi graph can record the relationship between the robot and obstacles, and provide an available path. Since the TDN task is map-less, we construct a local Voronoi graph within a fixed step online.

Conditioning on the depth information, the parameters (internal and external) of the camera, and the odometer information, obstacles in depth images can be easily converted into coordinates in a world coordinate system. This system is derived from the birth pose of the robot. Projecting this partially reconstructed 3D map onto a 2D plane along the vertical axis forms a scatter diagram depicting obstacles. We can construct a Voronoi diagram online by segmenting navigable paths and explorable cliques with multiple related objects. Different from traditional methods [24], we use DBSCAN [25, 26] (a density-based clustering algorithm) to cluster the scattered points of adjacent obstacles into convex hulls first, and then filter out noise points. Followed by constructing Delaunay triangle with the center of scattered points in the convex hull, thereby generating a Voronoi diagram.

In this section, we will summarize how the proposed reasoner and planner cooperate to complete navigation tasks. The curves in Fig. 5 show the correspondence of concepts between the topological graph in reasoner and the Voronoi diagram in planner. The aggregation of obstacles is regarded as a clique, each of which attaches and records all objects in its convex hull, and evaluates its inductive bias value according to the object-in-region membership via the Region Embedding network. The position of a vertex is generated by Voronoi. Multiple cliques and their subordinate objects surrounding the vertex jointly determine the general room label of it, and use the label for the inductive bias evaluation. Relative directions and distances between two adjacent vertex nodes are stored in gray ghost nodes. Since the robot exploits relative coordinates and directions, it effectively avoids the influence of odometer and depth camera error, thus insensitive to cumulative error. Besides, thanks to the Voronoi local diagram, only short-period scatter data need to be saved, and there is no need to consider the closed-loop matching problem like SLAM.

With the construction of Voronoi diagram and its transformation to a hierarchical topology, we can conduct reasoning in vertex/clique-level and object-level, searching for the best vertex position and the most likely clique based on the exploration value. After selecting a clique, the robot will navigate towards it, and explore it more explicitly as object-level reasoning. Besides, the Voronoi diagram provides the evidence for choosing the next best view of one clique. By changing multiple perspectives, the robot can find the target object in a clique more efficiently.

We use the Habitat simulator [27] with Matterport3D [28] environment as our experiment platform. Habitat simulator is a 3D simulator with configurable agents, multiple sensors, and generic 3D dataset handling. Matterport3D dataset contains 90 houses with 40 categories of objects and 31 labels of regions. It also provides detailed object and region segmentation information. Here we just focus on 21 categories of target object required by the task: chair, table, picture, cabinet, cushion, sofa, bed, chest of drawers, plant, sink, toilet, stool, towel, tv monitor, shower, bathtub, counter, fireplace, gym equipment, seating, clothes and also ignore some meaningless room labels, like outdoor, no label, other room and empty room. We use YOLOv4 [29] as our object detection module, which is fine-tuned using objects in Matterport3D dataset. Because the aiming of low-level controller is the same as PointNav task’s [30], we adapt a pre-trained state-of-the-art PointNav method occupancy anticipation [31] as our controller.

During a specific TDN task, the robot is spawned at a random location in a certain house and is demanded to find a object of a given category as quickly as possible. The task is evaluated with three commonly used indicators: Success Rate (SR), the Success weighted by Path Length (SPL) and Distance to Success (DTS). SR represents the number of times the target was found in multiple episodes and is defined as $\frac{1}{N}\sum^{N}_{i=1}Su_{i}$, where $N$ is the number of total episodes and $Su_{i}$ is a binary value representing the success or failure of the $i$-th episode. SPL depicts both success and the optimal path length, it is defined as $\frac{1}{N}\sum_{i=1}^{N}S_{i}\frac{L_{i}}{\max\left(P_{i},L_{i}\right)}$. Here we use the shortest length provided by the simulator as $L_{i}$ and the path length of the robot as $P_{i}$ in episode $i$. DTS is the distance of the agent from the success threshold boundary when the episode ends. The boundary is set to $1m$ and the maximum episode length is $500$ steps, which are the same as [14].

Furthermore, our navigation task has two modes: independent (ReVoLT-i) and continuous (ReVoLT-c). Independent mode is the traditional one, the environment is reset after each episode and the robot clears its memory. While the continuous mode allows the robot to keep the topological graph if it resets in the same house. It is used for evaluating the robot’s capability of keeping and updating the environment memory.

Random: At each step, the agent randomly samples an action from the action space with a uniform distribution.

RGBD + DD-PPO: This baseline is provided by ObjectNav Challenge 2020 [27]. Directly pass RGB-D information to an end-to-end DD-PPO and output an action from the policy.

Active Neural SLAM: This baseline uses an exploration policy trained to maximize coverage from [2], followed by the heuristic-based local policy as described above.

SemExp: Since [14] has not open-sourced their code, we directly use results in their paper as a state-of-the-art method.