# State Estimation in Electric Power Systems Leveraging Graph Neural Networks
††thanks: This paper has received funding from the European Union’s Horizon
2020 research and innovation programme under Grant Agreement number 856967.

Ognjen Kundacina  The Institute for Artificial Intelligence
Research and Development of Serbia
Novi Sad, Serbia
<EMAIL_ADDRESS>Mirsad Cosovic  Faculty of Electrical Engineering
University of Sarajevo
Sarajevo, Bosnia and Herzegovina
<EMAIL_ADDRESS>Dejan Vukobratovic  Faculty of Technical Sciences
University of Novi Sad
Novi Sad, Serbia
<EMAIL_ADDRESS>
###### Abstract

The goal of the state estimation (SE) algorithm is to estimate complex bus
voltages as state variables based on the available set of measurements in the
power system. Because phasor measurement units (PMUs) are increasingly being
used in transmission power systems, there is a need for a fast SE solver that
can take advantage of high sampling rates of PMUs. This paper proposes
training a graph neural network (GNN) to learn the estimates given the PMU
voltage and current measurements as inputs, with the intent of obtaining fast
and accurate predictions during the evaluation phase. GNN is trained using
synthetic datasets, created by randomly sampling sets of measurements in the
power system and labelling them with a solution obtained using a linear SE
with PMUs solver. The presented results display the accuracy of GNN
predictions in various test scenarios and tackle the sensitivity of the
predictions to the missing input data.

###### Index Terms:

state estimation, graph neural networks, machine learning, power systems,
real-time

††publicationid: pubid: 978-1-6654-1211-7/22/$31.00 ©2022 IEEE

##  I Introduction

The state estimation (SE), which estimates the set of power system state
variables based on the available set of measurements, is an essential tool
used for the power system’s monitoring and operation [1]. A fast state
estimator is required to maximise the use of high sampling rates of phasor
measurement units (PMUs). In this paper, we propose training a graph neural
network (GNN) for a regression problem on a dataset of SE inputs and outputs,
to provide fast and accurate predictions during the evaluation phase. One of
the main benefits of using GNNs in power systems instead of common deep
learning methods is the fact that the prediction model is not limited to the
training and test examples of fixed power system topologies. GNNs exploit the
graph structure of the input data [2][3], resulting in a lower number of
learning parameters, reduced memory requirements, and incorporate the
connectivity information into the learning process as well. Furthermore, the
inference phase of the trained GNN model can be distributed, since the
prediction of the state variable of a node requires only $K$-hop neighbourhood
measurements.

##  II Related Research and Contributions

Several pieces of research suggest learning computationally heavy algorithms’
outputs using a deep learning model, trained on the set of examples generated
by the algorithm offline. In [4] combination of recurrent and feed-forward
neural networks is used to solve the power system SE problem, given the
measurement data and the history of network voltages. An example of training a
feed-forward neural network to initialise the network voltages for the Gauss-
Newton distribution system SE solver is given in [5]. GNNs are beginning to be
used for solving similar problems, like in [6], where power flows in the
system are predicted based on the power injection data labelled by the
traditional power flow solver. In paper [7], the authors propose a combined
model and data-based approach in which GNNs are used for the power system
parameter and state estimation. The model predicts power
injections/consumptions in the nodes where voltages and phases are measured,
whereas it doesn’t include the branch measurements, as well as node
measurement types other than the voltage in the calculation. In [8], GNN was
trained to provide state variable initialization to existing SE solver by
propagating simulated or measured voltages through the graph to learn the
voltage labels from the historical dataset. However, the proposed GNN also
does not take into account measurement types other than node voltage
measurements, but they are handled in the other parts of the algorithm.

In this paper, the proposed model operates on factor-graph-like structures,
which enables trivial inclusion and exclusion of any type of measurements on
the power system’s buses and branches, by adding or removing the corresponding
nodes in the graph. The trained model is tested thoroughly in the various
missing data scenarios which include communication errors in the delivery of
isolated phasor data or failures of the complete PMUs, in which the power
system is unobservable, and the reports on the prediction qualities are
presented.

##  III Linear State Estimation with PMUs

The SE algorithm estimates the values of the state variables $\mathbf{x}$
based on the knowledge of the network topology and parameters, and measured
values obtained from the measurement devices spread across the power system.

The power system network topology is described by the bus/branch model and can
be represented using a graph $\mathcal{G}=(\mathcal{H},\mathcal{E})$, where
the set of nodes $\mathcal{H}=\\{1,\dots,n\\}$ represents the set of buses,
while the set of edges $\mathcal{E}\subseteq\mathcal{H}\times\mathcal{H}$
represents the set of branches of the power network. The branches of the
network are defined using the two-port $\pi$-model. More precisely, the branch
$(i,j)\in\mathcal{E}$ between buses $\\{i,j\\}\in\mathcal{H}$ can be modelled
using complex expressions:

$\begin{bmatrix}{I}_{ij}\\\
{I}_{ji}\end{bmatrix}=\begin{bmatrix}\cfrac{1}{\tau_{ij}^{2}}(y_{ij}+y_{\text{s}ij})&-\alpha_{ij}^{*}{y}_{ij}\\\
-\alpha_{ij}{y}_{ij}&{y}_{ij}+y_{\text{s}ij}\end{bmatrix}\begin{bmatrix}{V}_{i}\\\
{V}_{j}\end{bmatrix},$ (1)

where the parameter $y_{ij}=g_{ij}+\text{j}b_{ij}$ represents the branch
series admittance, half of the total branch shunt admittance (i.e., charging
admittance) is given as $y_{\text{s}ij}=\text{j}b_{si}$. Further, the
transformer complex ratio is defined as
$\alpha_{ij}=(1/\tau_{ij})\text{e}^{-\text{j}\phi_{ij}}$, where $\tau_{ij}$ is
the transformer tap ratio magnitude, while $\phi_{ij}$ is the transformer
phase shift angle. It is important to remember that the transformer is always
located at the bus $i$ of the branch described by (1). Using the branch model
defined by (1), if $\tau_{ij}=1$ and $\phi_{ij}=0$ the system of equations
describes a line. In-phase transformers are defined if $\phi_{ij}=0$ and
$y_{\text{s}ij}=0$, while phase-shifting transformers are obtained if
$y_{\text{s}ij}=0$. The complex expressions ${I}_{ij}$ and ${I}_{ji}$ define
branch currents from the bus $i$ to the bus $j$, and from the bus $j$ to the
bus $i$, respectively. The complex bus voltages at buses $\\{i,j\\}$ are given
as $V_{i}$ and $V_{j}$, respectively.

PMUs measure complex bus voltages and complex branch currents. More precisely,
phasor measurement provided by PMU is formed by a magnitude, equal to the root
mean square value of the signal, and phase angle [9, Sec. 5.6]. The PMU placed
at the bus measures bus voltage phasor and current phasors along all branches
incident to the bus [10]. Thus, the PMU outputs phasor measurements in polar
coordinates. In addition, PMU outputs can be observed in the rectangular
coordinates with real and imaginary parts of the bus voltage and branch
current phasors. In that case, the vector of state variables $\mathbf{x}$ can
be given in rectangular coordinates
$\mathbf{x}\equiv[\mathbf{V}_{\mathrm{re}},\mathbf{V}_{\mathrm{im}}]^{\mathrm{T}}$,
where we can observe real and imaginary components of bus voltages as state
variables:

$\displaystyle\mathbf{V}_{\mathrm{re}}$
$\displaystyle=\big{[}\Re({V}_{1}),\dots,\Re({V}_{n})\big{]}$ (2)
$\displaystyle\mathbf{V}_{\mathrm{im}}$
$\displaystyle=\big{[}\Im({V}_{1}),\dots,\Im({V}_{n})\big{]}.$

Using rectangular coordinates, we obtain the linear system of equations
defined by voltage and current measurements obtained from PMUs. The
measurement functions corresponding to the bus voltage phasor measurement on
the bus $i\in\mathcal{H}$ are simply equal to:

$\displaystyle f_{\Re\\{V_{i}\\}}(\cdot)=\Re\\{V_{i}\\}$ (3) $\displaystyle
f_{\Im\\{V_{i}\\}}(\cdot)=\Im\\{V_{i}\\}.$

According to the unified branch model (1), functions corresponding to the
branch current phasor measurement vary depending on where the PMU is located.
If PMU is placed at the bus $i$ where the transformer is located, functions
are given as:

$\displaystyle\begin{aligned}
f_{\Re\\{I_{ij}\\}}(\cdot)&=q\Re\\{V_{i}\\}-w\Im\\{V_{i}\\}-(r-t)\Re\\{V_{j}\\}+(u+p)\Im\\{V_{j}\\}\\\
f_{\Im\\{I_{ij}\\}}(\cdot)&=w\Re\\{V_{i}\\}+q\Im\\{V_{i}\\}-(u+p)\Re\\{V_{j}\\}-(r-t)\Im\\{V_{j}\\},\end{aligned}$

(4)

where $q=$ $g_{ij}/\tau_{ij}^{2}$, $w=$ $(b_{ij}+b_{si})/\tau_{ij}^{2}$, $r=$
$(g_{ij}/\tau_{ij})$ $\cos\phi_{ij}$, $t=$ $(b_{ij}/\tau_{ij})$
$\sin\phi_{ij}$, $u=$ $(b_{ij}/\tau_{ij})$ $\cos\phi_{ij}$, $p=$
$(g_{ij}/\tau_{ij})$ $\sin\phi_{ij}$. In the case where PMU is installed at
the bus $j$, at the opposite side of the transformer, measurement functions
are:

$\displaystyle\begin{aligned}
f_{\Re\\{I_{ji}\\}}(\cdot)&=z\Re\\{V_{j}\\}-e\Im\\{V_{j}\\}-(r+t)\Re\\{V_{i}\\}+(u-p)\Im\\{V_{i}\\}\\\
f_{\Im\\{I_{ji}\\}}(\cdot)&=e\Re\\{V_{j}\\}+z\Im\\{V_{j}\\}-(u-p)\Re\\{V_{i}\\}-(r+t)\Im\\{V_{i}\\},\end{aligned}$

(5)

where $z=g_{ij}$ and $e=$ $b_{ij}+b_{si}$. To recall, the presented model
represents the system of linear equations, where the solution can be found by
solving the linear weighted least-squares (WLS) problem:

$\left(\mathbf{H}^{T}\mathbf{R}^{-1}\mathbf{H}\right)\mathbf{x}=\mathbf{H}^{T}\mathbf{R}^{-1}\mathbf{z},$
(6)

where the Jacobian matrix $\mathbf{H}\in\mathbb{R}^{k\times 2n}$ is defined
according to measurement functions, $k$ is the total number of linear
equations, the covariance matrix is given as $\mathbf{R}\in\mathbb{R}^{k\times
k}$, and the vector $\mathbf{z}\in\mathbb{R}^{k}$ contains measurement values
given in rectangular coordinate system.

##  IV Graph Neural Network based State Estimation

GNNs are a suitable tool for learning over graph-structured data, which is
being processed by following a recursive neighbourhood aggregation scheme,
also known as message passing procedure [2]. This results in an
$s$-dimensional vector embedding $\mathbf{h}\in\mathbb{R}^{s}$ of each node,
which captures the information about the node’s position in the graph, as well
as it’s own and the input features of the neighboring nodes. The GNN layer,
which implements one iteration of the recursive neighbourhood aggregation
consists of several functions, that can be represented using a trainable set
of parameters, usually in form of the feed-forward neural networks. Those
include the message function between two node embeddings, the aggregation
function which defines in which way are incoming messages combined and the
update function which updates the node embedding based on the aggregated
messages and the current node embedding value. The recursive neighbourhood
aggregation scheme is repeated a predefined number of times $K$, also known as
the number of GNN layers, where the initial node embedding values are equal to
the $l$-dimensional node input features, linearly transformed to the initial
node embedding $\mathbf{h}^{0}\in\mathbb{R}^{s}$. The output of this process
are final node embeddings which can be used for the classification or
regression over the nodes, edges, or the whole graph, or can be used directly
for the unsupervised node or edge analysis of the graph. In the case of
supervised learning over the nodes, the final embeddings are passed through
the additional nonlinear function, creating the outputs that represent the
predictions of the GNN model for the set of inputs fed into the nodes and
their neighbors. The GNN model is trained by backpropagation of the loss
function between the labels and the predictions over the whole computational
graph.

Inspired by the recent work [11] in which the power system SE is modelled as a
probabilistic graphical model, the initial version of the graph over which GNN
operates has a power system’s factor graph topology, which is a bipartite
graph consisted of the factor and variable nodes, and the edges between them.
Variable nodes, two per each power system bus, learn the $s$-dimensional
representation of the state variables $\mathbf{x}$, i.e. real and imaginary
parts of the bus voltages, $\Re({V}_{i})$ and $\Im({V}_{i})$, defined in (2).
Factor nodes, two per each measurement phasor, serve as inputs for the
measurement values and variances, also given in rectangular coordinates, and
whose embedded values are sent to variable nodes via GNN message passing.
Feature augmentation using one-hot index encoding is performed for variable
nodes only, to help the GNN model to represent the neighbourhood structure of
a node better, since variable nodes have no additional input features. Nodes
connected by full lines in Fig. 1 represent a simple example of the factor
graph for a two-bus power system, with a PMU on the first bus, containing one
voltage and one current phasor measurement. Compared to the approaches like
[7], in which GNN nodes correspond to state variables only, we find factor-
graph-like GNN topology convenient for incorporating measurements in the GNN,
because factor nodes can be added or removed from any place in the graph,
using which one can simulate inclusion of various types and quantities of
measurements both on power system buses and branches.

$f_{\Re({V}_{1})}$$f_{\Im({V}_{1})}$$\Re({V}_{1})$$\Im({V}_{1})$$f_{\Re({I}_{12})}$$f_{\Im({I}_{12})}$$\Re({V}_{2})$$\Im({V}_{2})$
Figure 1: Example of the factor graph (full-line edges) and the augmented
factor graph for a two-bus power system. Variable nodes are depicted as
circles, and factor nodes as squares, colored differently to distinguish
between measurement types.

We extend this approach by augmenting the graph topology by connecting the
variable nodes in the 2-hop neighbourhood, following the idea that the graph
should stay connected even in a case of simulating measurement loss by
removing the factor nodes, enabling the messages to still be propagated in the
whole $K$-hop neighbourhood of the variable node. In other words, a factor
node corresponding to a branch current measurement can be removed, while still
preserving the physical connection that exists between the power system buses.
This requires adding an additional set of trainable parameters for variable-
to-variable message function. We will still use the terms factor and variable
nodes, although the second version graph over which the GNN operates,
displayed in Fig. 1 with additional edges depicted with dashed lines is not a
factor graph, since it is no longer bipartite.

Since our GNN operates on a heterogeneous graph, in this work we employ two
different types of GNN layers,
$\operatorname{Layer^{f}}(\cdot|\theta^{\operatorname{Layer^{f}}}):\mathbb{R}^{\textrm{deg}(f)+1}\mapsto\mathbb{R}^{s}$
for aggregation in factor nodes $f$, and
$\operatorname{Layer^{v}}(\cdot|\theta^{\operatorname{Layer^{v}}}):\mathbb{R}^{\textrm{deg}(v)+1}\mapsto\mathbb{R}^{s}$
for variable nodes $v$, so that their message, aggregation, and update
functions are learned using a separate set of trainable parameters, denoted
all together as $\theta^{\operatorname{Layer^{f}}}$ and
$\theta^{\operatorname{Layer^{v}}}$. Additionally, we use a different set of
parameters for variable-to-variable and factor-to-variable node messages in
the $\operatorname{Layer^{v}}(\cdot|\theta^{\operatorname{Layer^{v}}})$ layer.
In both GNN layers, we used two-layer feed-forward neural networks as message
functions, gated recurrent units as update functions and the attention
mechanism in the aggregation function [12], using which the importance factor
of each neighbour is learned. Furthermore, we apply a two-layer neural network
$\operatorname{Pred}(\cdot|\theta^{\operatorname{Pred}}):\mathbb{R}^{s}\mapsto\mathbb{R}$
on top of the final node embeddings $\mathbf{h}^{K}$ of variable nodes only,
to create the state variable predictions $\mathbf{x^{pred}}$. For the factor
and variable nodes with indices $f$ and $v$, neighbourhood aggregation, and
state variable prediction can be described as:

$\begin{gathered}{h_{v}}^{k}=\operatorname{Layer^{v}}(\\{{h_{i}}^{k-1}|i\in\\{v\mathop{\cup}\mathcal{N}_{v}\\}\\}|\theta^{\operatorname{Layer^{v}}})\\\
{h_{f}}^{k}=\operatorname{Layer^{f}}(\\{{h_{i}}^{k-1}|i\in\\{f\mathop{\cup}\mathcal{N}_{f}\\}\\}|\theta^{\operatorname{Layer^{f}}})\\\
{x_{v}}^{pred}=\operatorname{Pred}({h_{v}}^{K}|\theta^{\operatorname{Pred}})\\\
k\in\\{1,\dots,K\\}.\end{gathered}$ (7)

All of the GNN trainable parameters $\theta$ are updated by applying gradient
descent (i.e. backpropagation) to a loss function calculated over the whole
mini-batch of graphs, as a mean squared difference between the state variable
predictions and labels $\mathbf{x^{label}}$:

$\begin{gathered}L(\theta)=\frac{1}{2nB}\sum_{i=1}^{2nB}({{x_{i}}^{pred}}-{{x_{i}}^{label}})^{2}\\\
\theta=\\{\theta^{\operatorname{Layer^{f}}}\mathop{\cup}\theta^{\operatorname{Layer^{v}}}\mathop{\cup}\theta^{\operatorname{Pred}}\\},\end{gathered}$
(8)

where $2n$ is the total number of variable nodes in a graph, and $B$ is the
number of graphs in the mini-batch.

The inference process using the trained model can be computationally and
geographically distributed, as long as all of the measurements within the
$K$-hop neighbourhood in the augmented factor graph are fed into the
computational module that generates the predictions. For arbitrary $K$, PMUs
required for the inference will be physically located within the $\lceil
K/2\rceil$-hop neighbourhood of the power system bus.

##  V Numerical results

In this section, we describe the training setup which is used for both GNN
models described in the previous section and assess the prediction quality of
the trained models in various test scenarios. Training, validation, and test
sets are obtained using the WLS solutions of the system described in (6) for
various measurement samples. The number and the positions on PMUs are fixed
and determined using the optimal PMU placement algorithm [13], which finds the
smallest set of PMU measurements that make the system observable. The
algorithm has resulted in a total of 50 measurement phasors, 10 of which are
the voltage phasors and the rest are the current phasors. The IEEE 30-bus test
case is the foundation for all of the datasets we used in our experiments,
which is enriched by measurements, obtained by adding Gaussian noise to the
exact power flow solutions, with each power flow calculation executed with
different load profile.

The training set consists of 10000 samples, while validation and test set both
contain 100 samples. The GNN model for factor graphs, as well as the model for
augmented factor graphs, were both trained on 100 epochs, which was sufficient
to reach convergence considering both training and validation loss functions.
We used the IGNNITION framework [14] for building and utilising GNN models,
with the hyperparameters presented in Table I, the first three of which were
obtained with the grid search hyperparameter optimization.

TABLE I: List of GNN hyperparameters. Hyperparameters | Values
---|---
Node embedding size $s$ | $64$
Learning rate | $4\times 10^{-4}$
Minibatch size $B$ | $32$
Number of GNN layers $K$ | $4$
Activation functions | ReLU
Gradient clipping value | $0.5$
Optimizer | Adam
Batch normalization type | Mean

To assess the quality of the proposed GNN model in unobservable areas, we test
the trained models by excluding various numbers of measurement phasors from
the previously used test samples, making the system of equations that
describes the SE problem underdetermined. Excluding the measurement phasor
from the test sample is realised by removing its real and imaginary parts from
the input data, which is equivalent to removing two factor nodes from the
graph on which the GNN operates. Using the previously used 100-sample test set
we create 49 additional test sets, by removing a number in a range of $[1,49]$
measurement phasors randomly from each sample, while preserving the same
labels obtained as SE solutions of the system with all of the measurements
present. Fig. 2 summarises the quality of predictions of the both GNN models
on the mentioned test sets. For the test set with no measurements excluded,
the average mean square error (MSE) between the predictions and the labels for
GNN models for factor graphs and augmented factor graphs equals $1.056\times
10^{-5}$ and $1.051\times 10^{-5}$, respectively, while for the test set with
49 measurement phasors excluded, the corresponding values are $8.2235\times
10^{-2}$ and $3.193\times 10^{-2}$. Both models displayed very low MSE on test
examples with no excluded measurements, but the second model performed better
on test sets with excluded measurements. This confirms the assumption that
additional connections between variable nodes in the graph will preserve
information exchange when factor nodes are removed. Therefore, we will analyse
the second model in the detail in the rest of the paper.

01020304050$0$$0.02$$0.04$$0.06$$0.08$Excluded phasorsAverage MSEsAugmented
factor graphsFactor graphs Figure 2: Average MSEs of test sets created by
randomly excluding measurement phasors.

###  V-A Analysis of results for the GNN model operating on augmented factor
graphs

Average MSEs and Pearson’s Correlations between the prediction and the labels
over the whole test sets with various numbers of excluded measurement phasors
are presented in Table II. To further depict the quality of the trained model,
for one of the test samples, in Fig. 3 we present the predictions and the
labels for each of the variable nodes, where the upper plot displays the
results for the real parts of complex node voltages, while the lower plot
displays the imaginary parts. Fig. 3 also displays the minimal and the maximal
value of the state variables for each node, looking over every sample in the
training, validation, and test set. Presented results indicate that GNNs can
be used as accurate SE approximators when trained on the representative
dataset.

TABLE II: Average MSEs and Pearson’s Correlations for test sets with various numbers of randomly excluding measurement phasors. Excluded phasors | Pearson’s Correlation | MSE
---|---|---
0 | 0.9999948 | $1.0512\times 10^{-5}$
2 | 0.9986435 | $1.2259\times 10^{-5}$
10 | 0.9947819 | $6.8697\times 10^{-3}$
25 | 0.9880212 | $2.3002\times 10^{-2}$
49 | 0.9697979 | $3.1927\times 10^{-2}$
$0.8$$0.9$$1$$1.1$$\displaystyle\Re({V}_{i})$PredictionsLabelsBounds$0$$5$$10$$15$$20$$25$$30$$-0.4$$-0.2$$0$Bus
index ($i$)$\displaystyle\Im({V}_{i})$ Figure 3: Predictions and labels for
one test example with no measurement phasors removed.

Fig. 4 and Fig. 5 depict predictions and labels for the model evaluated on the
same test example with 2 and 49 measurement phasors excluded, respectively. We
can observe that GNN predictions are a decent fit for many of the node labels
when small fractions of all PMU measurements are not delivered to the state
estimator, demonstrating robustness in these unobservable scenarios. In the
unlikely scenario of only one measurement phasor left in the power system, the
proposed model generates predictions within the scope of the depicted bounds
for most of the variable nodes, although GNN inputs, in this case, differ
significantly from the samples on which the proposed model was trained.

$0.8$$0.9$$1$$1.1$$\displaystyle\Re({V}_{i})$PredictionsLabelsBounds$0$$5$$10$$15$$20$$25$$30$$-0.4$$-0.2$$0$Bus
index ($i$)$\displaystyle\Im({V}_{i})$ Figure 4: Predictions and labels for
one test example with two measurement phasors removed.
$0.8$$0.9$$1$$1.1$$\displaystyle\Re({V}_{i})$PredictionsLabelsBounds$0$$5$$10$$15$$20$$25$$30$$-0.5$$0$$0.5$$1$Bus
index ($i$)$\displaystyle\Im({V}_{i})$ Figure 5: Predictions and labels for
one test example with 49 measurement phasors removed.

To further analyze the robustness of the proposed model, we observe the
predictions for the scenario where 2 neighboring PMUs fail to deliver
measurements to the state estimator, hence all of the 8 measurement phasors
associated to the removed PMUs are excluded from the GNN inputs. Average
Pearson’s Correlation and MSE for the test set of 100 samples created by
removing these measurements from the original test set used throughout this
section are equal to $0.9985532$ and $1.3815\times 10^{-3}$. Predictions and
labels per variable node index for one sample are shown in Fig 6, in which
vertical dashed lines indicate indices of the variable nodes within 1-hop
neighbourhood of the removed PMUs. We stress that significant deviations from
the labels occur for the neighboring nodes only, with no greater effect on the
predictions for the remaining nodes, making the proposed model a suitable tool
to be used in PMU failure scenarios.

$0.8$$0.9$$1$$1.1$$\displaystyle\Re({V}_{i})$PredictionsLabelsBounds$0$$5$$10$$15$$20$$25$$30$$-0.4$$-0.2$$0$Bus
index ($i$)$\displaystyle\Im({V}_{i})$ Figure 6: Predictions and labels for
one test example with phasors from two neighboring PMUs removed.

###  V-B Sample efficiency analysis

To demonstrate how sample efficient is the proposed method, it is trained on
three training sets with sizes of 100, 1000, and 10000, for which validation
set losses converged after 10000, 1000, and 100 epochs respectively. All three
trained models are tested on the same test set of size 100, which contains no
excluded measurements. The average Pearson’s Correlation and MSE between the
labels and the predicted bus voltages over the entire test set are shown in
Table III. It can be seen that models trained with 1000 and 10000 samples
produce results of similar quality during the test phase, whereas there is a
more noticeable deterioration of results for the model trained with 100
samples. We assume that further exponential increase in training set size
would not be followed by significant improvements in the displayed performance
indicators.

TABLE III: Test set results for different training set sizes. Training set size | Pearson’s Correlation | MSE
---|---|---
100 | 0.9999642 | $1.5329\times 10^{-4}$
1000 | 0.9999909 | $1.4891\times 10^{-5}$
10000 | 0.9999948 | $1.0512\times 10^{-5}$

##  VI Conclusions

In this paper, we present a study on possibilities to use GNNs as fast linear
SE with PMUs solvers. We propose a model with graph attention network based
architecture, which operates on heterogeneous graphs, containing variable
nodes that output the predictions based on the WLS SE solutions, and factor
nodes, which take PMU voltage and current measurements and variances as inputs
and propagate them in the local neighbourhood. Evaluating the trained model on
the unseen data samples confirms that the proposed GNN approach can be used as
a very accurate approximator of the WLS SE solutions. By testing the model on
scenarios in which individual phasor measurements, or the whole PMUs fail to
deliver measurement data to the proposed SE solver, we have found that adding
variable-to-variable node connections in the training and test graphs
significantly improves the predictions in the cases when the system of
equations defining the SE problem becomes underdetermined.

## References

  * [1] A. Monticelli, “Electric power system state estimation,” _Proceedings of the IEEE_ , vol. 88, no. 2, pp. 262–282, 2000.
  * [2] J. Gilmer, S. S. Schoenholz, P. F. Riley, O. Vinyals, and G. E. Dahl, “Neural message passing for quantum chemistry,” in _Proceedings of the 34th International Conference on Machine Learning_ , ser. Proceedings of Machine Learning Research, D. Precup and Y. W. Teh, Eds., vol. 70. PMLR, 06–11 Aug 2017, pp. 1263–1272. [Online]. Available: https://proceedings.mlr.press/v70/gilmer17a.html
  * [3] M. M. Bronstein, J. Bruna, Y. LeCun, A. Szlam, and P. Vandergheynst, “Geometric deep learning: Going beyond euclidean data,” _IEEE Signal Processing Magazine_ , vol. 34, no. 4, pp. 18–42, 2017.
  * [4] L. Zhang, G. Wang, and G. B. Giannakis, “Real-time power system state estimation and forecasting via deep unrolled neural networks,” _IEEE Transactions on Signal Processing_ , vol. 67, no. 15, pp. 4069–4077, 2019.
  * [5] A. S. Zamzam, X. Fu, and N. D. Sidiropoulos, “Data-driven learning-based optimization for distribution system state estimation,” _IEEE Transactions on Power Systems_ , vol. 34, no. 6, pp. 4796–4805, 2019.
  * [6] B. Donon, B. Donnot, I. Guyon, and A. Marot, “Graph neural solver for power systems,” in _Proc. IJCNN_ , 2019, pp. 1–8.
  * [7] L. Pagnier and M. Chertkov, “Physics-informed graphical neural network for parameter & state estimations in power systems,” 2021.
  * [8] Q. Yang, A. Sadeghi, G. Wang, G. B. Giannakis, and J. Sun, “Robust psse using graph neural networks for data-driven and topology-aware priors,” _ArXiv_ , vol. abs/2003.01667, 2020.
  * [9] J. De La Ree, V. Centeno, J. S. Thorp, and A. G. Phadke, “Synchronized phasor measurement applications in power systems,” _IEEE Transactions on smart grid_ , vol. 1, no. 1, pp. 20–27, 2010.
  * [10] A. Gomez-Exposito, A. Abur, P. Rousseaux, A. de la Villa Jaen, and C. Gomez-Quiles, “On the use of PMUs in power system state estimation,” _Proceedings of the 17th PSCC_ , 2011.
  * [11] M. Cosovic and D. Vukobratovic, “Distributed Gauss–Newton method for state estimation using belief propagation,” _IEEE Trans. Power Syst._ , vol. 34, no. 1, pp. 648–658, 2019.
  * [12] P. Veličković, G. Cucurull, A. Casanova, A. Romero, P. Liò, and Y. Bengio, “Graph Attention Networks,” _International Conference on Learning Representations_ , 2018. [Online]. Available: https://openreview.net/forum?id=rJXMpikCZ
  * [13] B. Gou, “Optimal placement of pmus by integer linear programming,” _Power Systems, IEEE Transactions on_ , vol. 23, pp. 1525 – 1526, 09 2008\.
  * [14] D. Pujol-Perich, J. Suárez-Varela, M. Ferriol, S. Xiao, B. Wu, A. Cabellos-Aparicio, and P. Barlet-Ros, “Ignnition: Bridging the gap between graph neural networks and networking systems,” 2021.


# Semantic Layering in Room Segmentation via LLMs

Taehyeon Kim and Byung-Cheol Min The authors are with SMART Lab, Department of
Computer and Information Technology, Purdue University, West Lafayette, IN
47907, USA {kim4435<EMAIL_ADDRESS>
###### Abstract

In this paper, we introduce Semantic Layering in Room Segmentation via LLMs
(SeLRoS), an advanced method for semantic room segmentation by integrating
Large Language Models (LLMs) with traditional 2D map-based segmentation.
Unlike previous approaches that solely focus on the geometric segmentation of
indoor environments, our work enriches segmented maps with semantic data,
including object identification and spatial relationships, to enhance robotic
navigation. By leveraging LLMs, we provide a novel framework that interprets
and organizes complex information about each segmented area, thereby improving
the accuracy and contextual relevance of room segmentation. Furthermore,
SeLRoS overcomes the limitations of existing algorithms by using a semantic
evaluation method to accurately distinguish true room divisions from those
erroneously generated by furniture and segmentation inaccuracies. The
effectiveness of SeLRoS is verified through its application across 30
different 3D environments. Source code and experiment videos for this work are
available at: https://sites.google.com/view/selros.

##  I Introduction

Navigating through home indoor environments with the aid of robotics has
increasingly relied on vision-language cues for object-oriented navigation
[1][2][3][4]. Yet, the challenge of autonomously recognizing and targeting
specific ‘contextual’ places, such as kitchens, living rooms, and bathrooms,
without direct human input remains largely unexplored. Traditional approaches
to room segmentation have predominantly utilized 2D maps to classify spaces
within indoor environments [5][6]. However, these methods focus strictly on
the segmentation aspect, neglecting the semantic information that is crucial
for a more nuanced understanding and navigation of these spaces. This paper
introduces Semantic Layering in Room Segmentation via LLMs (SeLRoS), an
innovative approach that leverages Large Language Models (LLMs) to integrate
semantic information into segmented 2D maps. This method significantly
enhances the functionality of robotic navigation systems and the accuracy of
traditional segmentation algorithms.

As illustrated in Fig. 1, SeLRoS addresses the limitations of existing room
segmentation algorithms by integrating semantic data into the segmentation
process. This involves analyzing objects within each room, as well as
considering spatial relationships and the physical characteristics of spaces,
such as size and shape. By utilizing LLMs, we can organize this diverse array
of information and make additional inferences, thus providing a richer, more
contextually aware mapping of home indoor environments. The incorporation of
semantic data not only augments the segmented maps with meaningful information
but also serves to refine the segmentation algorithm itself.

Figure 1: Semantic Layering in Room Segmentation via LLMs (SeLRoS) employs a
room segmentation algorithm, an object detection algorithm, and Large Language
Models (LLMs) to derive a 2D segmentation map from a 3D environment (left side
of the figure), as well as to produce semantic information for each segmented
room (right side of the figure).

Conventional room segmentation methods have shown proficiency in mapping
unfurnished spaces [5][6][7]. However, they falter when confronted with
complex environments where furniture and other objects can lead to the
erroneous division of rooms. By applying semantic insights, our study aims to
discern whether segmented spaces are distinct rooms or erroneously divided
sections of the same room due to the limitations of current algorithms. This
semantic evaluation allows for a more accurate representation of indoor
spaces, distinguishing between, for instance, multiple bedrooms or a single
living room fragmented by the presence of furniture.

In summary, this paper introduces SeLRoS, a novel approach to room
segmentation by leveraging the analytical prowess of LLMs to assign semantic
information to 2D maps. This method not only enhances the accuracy of room
segmentation in furnished environments but also enriches the semantic
understanding of indoor spaces, paving the way for more sophisticated and
contextually aware navigation systems. The contributions of this paper are as
follows:

  * •

We propose an innovative architecture using LLMs to integrate semantic
information into existing room segmentation results including algorithm for
interpreting room segmentation outcomes and a prompt engineering technique.

  * •

We enhance the accuracy of room segmentation by utilizing semantic data to
rectify segmentation errors caused by furniture in home indoor environments.

  * •

We conducted extensive experiments to validate SeLRoS and have made the source
code and related-map files available to the community for further research and
development.

Figure 2: Overview of SeLRoS’s structure: SeLRoS begins with Geometric Room
Segmentation, where a 2D map ($M$) from the Original Environment ($E$) is
transformed into a Segmentation Map ($S$). Following this, the Object Mapping
process extracts Object Information ($O_{s}$) by analyzing scenes from the
Original Environment’s center coordinates of each segmented space ($s$),
employing an Object Detection algorithm. In the Semantic Integration process,
harmonizing $s$, $O_{s}$ and the data of spatial relations ($R_{s}$) through
the Room Information Interpreter and generating prompts $P(s,O_{s},R_{s})$ via
Hierarchical Query. The final outputs are Improved Segmentation Map
($S^{\prime}$) with Semantic Information ($I$).

##  II Related Works

Traditional Room Segmentation. Research in traditional room segmentation
primarily focuses on utilizing 2D maps to delineate individual rooms within an
indoor environment [5][8]. Recent advancements in this field have achieved
considerable accuracy in segmenting spaces based on geometric properties [6].
However, these methods often face limitations when applied to environments
with furniture, where the presence of objects can significantly impact
segmentation accuracy. To address these challenges, some studies have explored
the use of additional sensors, such as 3D LiDARs, to enhance segmentation
precision [7][9][10]. However, as suggested in this paper, the integration of
semantic information into the segmentation process to improve the utility and
accuracy of segmented maps in furnished environments has yet to be fully
explored.

Indoor Scene Classification. Indoor scene classification research aims to
identify and classify various scenes within indoor environments based on their
characteristics and features [11][12][13][14][15]. This approach differs from
room segmentation in that it focuses on the scene’s content rather than its
geometric boundaries. While these studies provide valuable insights into
understanding indoor environments[16], their application to traditional robot
navigation, particularly in enhancing segmented maps, is limited. Moreover,
although scene classification can infer the function of a specific area, it
does not address the challenge of defining the spatial extent of these
inferred places, leaving a gap in the application of scene classification data
to practical navigation tasks.

Robotics-related Research Using LLMs. The use of LLMs in robotics-related
research represents a burgeoning area of interest, marked by various
innovative attempts to integrate LLMs capabilities into robotic
systems[17][18][19]. While the potential of LLMs in enhancing robot autonomy
and decision-making is vast, their application, especially in writing
comprehensive robot control codes, poses stability and reliability
concerns[20][21][22][23]. Our study distinguishes itself within this context
by leveraging the strengths of LLMs not to replace, but to augment existing
methods[24][25][26]. By combining LLMs with widely used segmentation
techniques, our approach aims to enhance the semantic understanding of
segmented spaces, thereby offering a novel contribution to the field of
robotic navigation and indoor mapping.

##  III Problem Formulation

Let $S$ represent the set of all segmented spaces based on original indoor
environment $E$, where each space $s\in S$ is defined by its geometric
properties derived from a 2D map. The traditional room segmentation problem
can be defined as a function $f:M\rightarrow S$, where $M$ represents the 2D
map of the environment, and $S$ is the set of segmented spaces. The semantic
gap is defined by the lack of functional and contextual information in $S$,
which is necessary for distinguishing between different types of rooms beyond
their geometric properties.

We aim to obtain semantic information $I$ and utilize it to enhance Set $S$,
resulting in the creation of $S^{\prime}$. This semantic enrichment boosts the
accuracy of the resulting set and expands the usability of the map. Let
$O_{s}$ represent the set of objects observed in the segmented environment,
and $R_{s}$ represent the set of relations among segmented rooms $s$,
including adjacency and spatial characteristics. Given a segmented space $s$
and its corresponding objects and relations $O_{s}$ and $R_{s}$, we formulate
a prompt $P(s,O_{s},R_{s})$ that encapsulates this information for the LLM.
The LLM’s response to $P$ becomes semantic information $I$. This $I$ is used
to improve $s$ by providing additional context, transforming $s$ into
$s^{\prime}$. Therefore, the objective of our study is to define a function
$g:S\times I\rightarrow S^{\prime}$ that maps each segmented space $s$,
enhanced with semantic information $I$ derived from $P(s,O_{s},R_{s})$, to
$s^{\prime}$.

##  IV Methodology

SeLRoS consists of three parts: geometric room segmentation, object mapping,
and semantic integration, as depicted in Fig. 2.

###  IV-A Geometric Room Segmentation

This process involves generating a segmentation map ($S$) from a 2D map ($M$),
which itself is derived from the original environment ($E$). The purpose of
this phase is to accurately delineate the spatial boundaries within an
environment, setting the stage for further semantic enhancement.

For the implementation of SeLRoS, the Voronoi Random Field (VRF) algorithm is
chosen for room segmentation. This decision is informed by a comparative
analysis of existing renowned room segmentation algorithms [5][6]. While
morphological and distance algorithms are recognized for producing clear and
well-defined segmentation maps, they tend to prioritize geometric accuracy
over the nuanced understanding of space. Conversely, VRF adopts a variability
and stochastic approach [27]. This method is adept at capturing more intricate
segmentation patterns, offering a richer, albeit more fragmented, portrayal of
room divisions. The challenge of over-segmentation associated with VRF,
typically seen as a drawback, is adeptly mitigated in SeLRoS through the
subsequent integration of semantic information. SeLRoS effectively
consolidates excessively divided segmented spaces using semantic information.

An important aspect of SeLRoS’s design is its modular architecture. This
modularity ensures flexibility in the choice of Room Segmentation algorithms.
Should the need arise to adapt SeLRoS to different environments or to leverage
advancements in segmentation techniques, the Room Segmentation algorithm can
be seamlessly updated or replaced.

###  IV-B Object Mapping

In the object mapping phase of the SeLRoS, we first determine the geometric
center of each segmented room ($s$). This is achieved by calculating the mean
position of all constituent points within a segment, specifically by averaging
the $x$ and $y$ coordinates separately to ascertain the room’s centroid.

Subsequently, we acquire visual data from the original environment ($E$) at
these center positions. Utilizing an Object Detection algorithm, we then
systematically extract a list of objects present within each scene. For the
purpose of object detection within SeLRoS, we employ Detic[28], a robust
algorithm known for its accuracy and efficiency in identifying and classifying
objects within complex environments.

This procedure is executed for every segmented room, resulting in the creation
of object information ($O_{s}$) for the segmentation map. This information
specifies which objects are located in each segmented room, effectively
mapping object presence across the entire segmented area.

###  IV-C Semantic Integration

The semantic integration process comprises two distinct parts. Initially, the
Room Information Interpretation phase processes the segmentation map ($S$),
extracting key details for each segmented room, including area, shape, and
adjacency relationships with neighboring rooms. This phase also integrates
this spatial data with the object information ($O_{s}$). Following this, the
Hierarchical Query stage implements prompt engineering techniques to
efficiently relay this combined information to LLMs, ensuring reliable and
high-quality outcomes.

Figure 3: Hierarchical Query is hierarchically composed of Room-Level Query
and Environment-Level Query. The red box represents the role component, the
yellow box represents the instruction, and blue box signifies the set of
Semantic Information.

####  IV-C1 Room Information Interpretation

The Room Information Interpretation phase stands as a crucial element of our
methodology, designed to analyze the segmentation map ($S$) through the Room
Information Interpreter. This process entails a comprehensive interpretation
of each segmented room’s characteristics, including its area, shape, and the
adjacency relationships it shares with surrounding rooms. Initially, the
interpreter identifies each room within the segmentation map ($S$) by
utilizing unique RGB values as markers. It then calculates the area of each
room by tallying the pixels corresponding to each RGB value, offering an
accurate representation of room sizes. To assess the shape of each room, our
approach involves estimating the contours of rectangular shapes that
approximate each room’s boundaries, from which we derive the dimensions—length
and width—providing a geometric approximation of the room’s shape.
Furthermore, the adjacency relationships between rooms are determined by
slightly dilating each room’s mask to create an expanded boundary. When these
dilated masks overlap with those of neighboring rooms, it indicates adjacency,
thereby enabling us to map the complex network of connections between rooms
within the segmented environment.

####  IV-C2 Hierarchical Query

Hierarchical Query, depicted in Fig. 3, is our novel approach to prompt
engineering. This technique is inspired by and extends upon concepts from
prior research, drawing upon the structural query organization found in our
previous work [29] and the analytical decomposition from [30]. However,
Hierarchical Query advances these ideas by partitioning a comprehensive
query—aimed at requesting semantic information ($I$) for each segmented room
($s$)—into a series of targeted sub-queries. These sub-queries, comprising
both Role and Instruction elements, are individually presented to LLMs. The
Role is crafted to designate a specific function to the LLMs, guiding it on
which domain of knowledge to access by setting a particular context or
perspective. Concurrently, the Instruction serves to define the bounds of the
LLM’s action. Considering the LLM’s foundation on vast datasets for
information, this Instruction acts as a constraint, either by prescribing a
desired format for structuring the answer or by narrowing the dataset’s scope
through a description of the current context.

The core distinction of Hierarchical Query lies in its integration of
responses. Initially, LLMs address the segmented Room-Level Query, engaging
with discrete elements of the environment. Subsequently, the responses to
these sub-queries are aggregated, and the Environment-Level Query, or in other
words, the prompt $P(s,O_{s},R_{s})$ that is ultimately delivered to the LLMs,
is generated. This process permits LLMs to reconsider their previous responses
within the complete context information and enhances the accuracy and
relevance of the answers.

A pivotal aspect of Hierarchical Query is its emphasis on the format and
structure of the responses. By incorporating instruction within the
Environment-Level Query, we guide LLMs to not only revisit their answers but
also to align their responses with a predefined answer format. This prompt
engineering technique ensures that the obtained answers are not only
contextually enriched but also consistent and structured, significantly
boosting the reliability and stability of the semantic information ($I$).

Input: Original Environment $E$

Output: Improved Segmentation Map $S^{\prime}$, Semantic Information $I$

function _GeometricRoomSegmentation($E$)_

$M\leftarrow\textsc{Get\\_2D\\_map}(E)$

$S\leftarrow\textsc{VRF\\_Segmetation}(M)$

for  _each room in $S$_ do

$C[room]\leftarrow\textsc{Get\\_center}(room)$

return  $S,C$

function _ObjectMapping($S,C$)_

for  _each room in $S$_ do

$scene[room]\leftarrow\textsc{GetVisualData}(C[room])$

$O[room]\leftarrow\textsc{ObjectDetection}(scene[room])$

return  $O$

function _SemanticIntegration($S,O$)_

for  _each room in $S$_ do $\triangleright$ Room Info Interpretation

$area\leftarrow\textsc{CalculateArea}(room)$

$shape\leftarrow\textsc{CalculateShape}(room)$

$adjacency\leftarrow\textsc{DetectAdjacency}(room)$

$R[room]\leftarrow\\{area,shape,adjacency\\}$

for  _each room in $S$_ do $\triangleright$ Room-Level Query

$p[room]\leftarrow\textsc{MakePrompt}(O[room],R[room])$

$i[room]\leftarrow\textsc{LLM}(p[room])$

$P\leftarrow\textsc{MakePrompt}(i,O,R)$ $\triangleright$ Env-Level Query

$I\leftarrow\textsc{LLM}(P)$

$S^{\prime}\leftarrow\textsc{IntegrationMap}(S,I)$

return  $S^{\prime},I$

$S,C\leftarrow\textsc{GeometricRoomSegmentation}(E)$

$O\leftarrow\textsc{ObjectMapping}(S,C)$

$S^{\prime},I\leftarrow\textsc{SemanticIntegration}(S,O)$

return  $S^{\prime},I$

Algorithm 1 Process of SeLRoS

The pseudo-code, detailed in Algorithm 1, provides a technical overview of the
entire SeLRoS process. This methodology significantly enhances the
segmentation map by incorporating semantic information, thereby allowing for a
more accurate and context-aware delineation of spaces within the environment.

##  V Experiments

###  V-A Experimental Setup

To demonstrate SeLRoS’s applicability across a spectrum of structures,
experiments were conducted in various home indoor environments, utilizing 30
diverse 3D models generated through ProcTHOR[31] within the AI2-THOR[32]
framework. For each environment, a 2D map was crafted using AI2-THOR’s
reachable position extraction function, from which a segmentation map was
subsequently derived. Following the procedures outlined in Section IV, visual
data were captured from the center coordinates of each segmented room, serving
as the basis for acquiring object information. This collected data was
processed through the semantic integration phase, resulting in an improved
segmentation map enriched with semantic information.

###  V-B Evaluation Criteria

To substantiate our contributions, evaluation is bifurcated into qualitative
and quantitative analyses. The qualitative analysis involves a heuristic
comparison of our result against the original 3D environment, providing an
intuitive assessment of the improvements offered by SeLRoS.

The quantitative analysis is further split into two parts. The initial part
evaluates the enhancements in room segmentation accuracy brought about by
SeLRoS, utilizing well-known room segmentation algorithms as baselines for
comparison. For this evaluation, we employ Intersection over Union (IoU) and
our newly introduced evaluation criterion, Match Scaled Intersection over
Union (MSIoU), to quantitatively assess these improvements. The IoU metric,
traditionally used to gauge segmentation accuracy, measures the overlap ratio
between the predicted segmentation and the ground truth versus their
collective area. MSIoU, however, enhances this assessment by implementing a
scaling mechanism that adjusts based on the match quality rank of each
segmented room’s correspondence. The MSIoU formula is articulated as follows:

$\text{MSIoU}=\text{$\frac{1}{N}\sum_{i=1}^{N}\left(\sum_{j=1}^{M_{i}}\text{IoU}(A_{i},S_{ij})\times\Delta\alpha\right)$}$
(1)

where $N$ represents the total number of actual rooms, while $M_{i}$ indicates
the number of segmented rooms associated with the actual room $A_{i}$. The
$\text{IoU}(A_{i},S_{ij})$ refers to the IoU for the $j$th best-matched
segmented room $S_{ij}$ relative to the actual room $A_{i}$. The decrement
factor, $\Delta\alpha$, is applied to each successive match’s IoU value to
diminish its weight, starting from the best match. In this context,
$\Delta\alpha$ decreases from 1.0 by 0.1 for each subsequent match, with a
minimum value of 0.1, ensuring that even the lowest-ranked matches contribute
to the overall MSIoU but with diminishing influence.

This metric not only allows us to assess the geometric accuracy of the
segmentation but also introduces a graded evaluation that reflects the
segmentation performance more comprehensively, taking into account both
accuracy and the algorithm’s tendency towards over-segmentation. Through this
dual approach, utilizing both IoU and MSIoU, our analysis aims to provide a
more detailed and nuanced understanding of SeLRoS’s contributions to the field
of room segmentation.

Figure 4: Results for Environment 1 - (a) depicts the original 3D environment,
(b) shows the segmentation map created using the Voronoi Random Field (VRF)
algorithm, and (c) presents the improved segmentation map, the final result
achieved through SeLRoS, with semantic information added for readability.

The subsequent part, combining of baseline and ablation studies, focuses on
evaluating the accuracy of the semantic information generated by SeLRoS. This
is achieved by benchmarking against existing indoor scene classifier and
examining the performance impact of omitting specific methodologies from our
proposed approach. Through this comprehensive review, we aim to underscore the
validity and innovative capacity of SeLRoS.

##  VI Results and Analysis

###  VI-A Qualitative Analysis

In this section, we delve into the visual and interpretative evaluation of the
improved segmentation map with semantic information outputted by our proposed
SeLRoS system. This analysis focuses on observing the enhancements achieved
through SeLRoS in comparison to the initial 3D environments and the
segmentation maps generated by the VRF algorithm. Our experiments conducted
across 30 3D environments, from which two environments will be selected for
detailed review and analysis in the subsequent sections. All experiment
results for the 30 environments can be found at our project website at:
https://sites.google.com/view/selros. This qualitative assessment serves to
highlight the tangible benefits of incorporating semantic information into the
segmentation map, showcasing the practical application and effectiveness of
SeLRoS in refining and enriching segmentation maps for enhanced spatial
understanding and recognition.

Figure 5: Results for Environment 2 - (a) depicts the original 3D environment,
(b) shows the segmentation map created using the VRF algorithm, and (c)
presents the improved segmentation map, the final result achieved through
SeLRoS, with semantic information added for readability.

####  VI-A1 Environment 1

In the qualitative analysis of Environment 1, the outcomes are showcased in
Fig. 4, highlighting the effectiveness of SeLRoS in enhancing room
segmentation through semantic integration. Initially, the application of
SeLRoS is evident in the consolidation of segmented spaces that were
previously divided without necessity. A notable example is the integration of
areas marked in blue and purple on the center-right of the map, now
collectively identified as the Livingroom, thanks to specified semantic
information. Furthermore, a region in the upper right corner, initially
segmented into three separate areas, has been unified under the singular
semantic information of Bedroom. Similarly, what were once three distinct
segmented rooms within the bathroom area at the bottom right have been merged
into a single area. This consolidation underscores the capability of SeLRoS to
utilize the relational data between observed objects and their corresponding
spaces, effectively addressing the issue of rooms fragmented by the presence
of furniture when relying solely on 2D map-based segmentation.

With regard to semantic information, the application of SeLRoS has enabled
precise room identification: the Livingroom is designated where the TV and
sofa reside, the Bedroom is identified by the presence of a bed, and the
Bathroom is recognized by the toilet’s location. Additionally, the Kitchen
area, discernible near the sink in the 3D environment, illustrates a nuanced
aspect of semantic integration. However, the case of kithchen, the initial
segmentation inaccurately divided this area into two separate sections with
intervening Livingroom space in the VRF-derived segmentation map, preventing
their integration. Also, some misclassifications were observed in the Storage
area. Despite their open-space nature, these areas were incorrectly labeled as
storage by LLMs, a judgment likely influenced by the small size of the
segmented spaces and the diversity of observed objects within them.

####  VI-A2 Environment 2

The analysis of Environment 2, as illustrated in Fig. 5, also reveals
significant advancements in the segmentation of indoor environments through
the SeLRoS. In this instance, it was observed that segmented rooms, previously
divided due to the presence of furniture such as the Hallway, Kitchen, and
Livingroom1, were effectively integrated through semantic information.

Regarding the precision of the semantic information, most areas were
accurately categorized, except for a space labeled as Livingroom2 located at
the bottom left. This particular room, more appropriately characterized as an
Officeroom based on its function and contents, was inaccurately identified as
another living room. This likely stems from this room’s size being
significantly larger than what is typically observed for bedrooms.

Through the experiment, the utility of SeLRoS in enhancing room segmentation
by integrating semantic information is further validated, demonstrating its
potential in overcoming challenges posed by traditional segmentation
approaches. However, the mislabeling of the Officeroom as Livingroom2
underscores the need for refined criteria within LLMs that consider beyond
mere spatial dimensions to include a broader range of contextual information
for accurate semantic labeling.

###  VI-B Quantitative Analysis

####  VI-B1 Improvement in Segmentation Accuracy

In our first part of quantitative analysis, the segmentation accuracy of
SeLRoS is compared against four conventional segmentation algorithms:
Morphological Segmentation[33], Distance Segmentation[34], Voronoi
Segmentation[35], and VRF Segmentation[27].

Morphological Segmentation, Distance Segmentation, Voronoi Segmentation, and
VRF Segmentation each bring distinct approaches to room segmentation,
exhibiting varying degrees of effectiveness across different environmental
setups. Morphological Segmentation shines in settings with clear structural
delineations for room boundaries but faces challenges in more intricate scenes
where furniture and other items blur these edges. Distance Segmentation
leverages proximity measures to differentiate spaces, yet its accuracy
diminish in environments densely populated with furniture similarly to
Morphological Segmentation. Meanwhile, Voronoi-based methods, including both
Voronoi Segmentation and VRF Segmentation, apply a mathematical strategy for
dividing space that heavily relies on the strategic placement of seed points.
While this approach is adept at sketching out a basic spatial layout, it is
susceptible to over-segmenting areas, inadvertently increasing the perceived
number of rooms.

Fig. 6, which presents the segmentation results alongside the ground truth for
Environment 1 upon applying each segmentation algorithm, elucidates the
distinctive behaviors of these algorithms. For the Morphological and Distance
Segmentation algorithms, the segmentation results in expansive areas like the
Livingroom align closely with those of SeLRoS, showing no superfluous
segmentation. However, inaccuracies arise in the Bedroom, especially around a
table, leading to erroneous segmentation. Conversely, the two Voronoi-based
segmentation approaches demonstrate improved segmentation performance in the
Bathroom area at the right-bottom, surpassing the other algorithms in this
aspect. Yet, they tend to generate an excessive number of segmented rooms.

TABLE I: Experiment results for room segmentation accuracy Test | Morphological | Distance | Voronoi | VRF | SeLRoS
---|---|---|---|---|---
IoU | 63.27 | 59.45 | 60.51 | 61.89 | 69.98
MSIoU | 52.36 | 49.41 | 50.7 | 51.56 | 57.73

Our experiments for comparison is grounded on the evaluation metrics of IoU
and MSIoU, with the detailed numerical results presented in Table I, covering
experiments across 30 different environments. The analysis confirms SeLRoS’s
superior performance in both IoU and MSIoU metrics, indicative of its enhanced
precision in identifying room boundaries. Specifically, SeLRoS’s capability to
integrate semantic information effectively mitigates the over-segmentation
tendency seen in Voronoi-based methods. Through this comparative analysis, it
becomes evident that the integration of semantic information is pivotal in
transcending the limitations inherent to purely geometric approaches to room
segmentation.

Figure 6: Comparison results for the Environment 1, showing the performance of
four existing segmentation algorithms (Morphological, Distance, Voronoi, VRF)
from (b) to (e), and SeLRoS (f). This is done by comparing them using IoU and
MSIoU metrics with the ground truth (a).

####  VI-B2 Evaluating Semantic Information

In the second part of quantitative analysis, we conducted a comparative
evaluation focusing on the semantic information derived from scene data
observed at the center of each segmented room. The findings from this analysis
are detailed in Table II. For benchmarking purposes, we utilized an Indoor
Scene Classifier, which processes images to categorize indoor environments, as
the baseline for our study. For this, we leverage YOLOv8 Image Classifier
[36], trained on the MIT Indoor Scene Recognition Image Dataset (comprising
15k images) [37].

TABLE II: Experiment results for semantic information accuracy Test | Scene Classifier | Obj Info | Obj & Room Info | SeLRoS
---|---|---|---|---
Acc (%) | 62.67 | 67.5 | 72.57 | 82.26

Additionally, we engaged in an ablation study by examining variations of our
proposed method, where specific components were systematically omitted to
assess their impact on performance. The ablation study differentiates between
two key variations: Obj Info, which represents the semantic information ($I$)
generated from only the object information ($O_{s}$) observed at the center of
each segmented room, and Obj & Room Info, which represents the semantic
information ($I$) created by object information ($O_{s}$) and contextual
information ($R_{s}$) interpreted by the Room Information Interpreter.
Notably, these variations exclude the application of SeLRoS’s hierarchical
query prompt engineering technique.

Our results demonstrate that the semantic information generated by SeLRoS
outperforms all other methods under comparison in terms of accuracy. A
significant observation is the underperformance of the Indoor Scene Classifier
based on YOLOv8 compared to its typical application. This discrepancy arises
from our unique methodology for capturing scene data, which diverges from
conventional indoor scene classification that relies on scenes rich in
distinctive objects. In our approach, which gathers images from four
directions centered within each segmented room, may capture scenes dominated
by non-descriptive elements like walls and doors, especially in smaller areas.
This scenario can affect the classifier’s performance, implicating its limited
applicability to the SeLRoS framework, which employs a more comprehensive
strategy for semantic information extraction by considering the entire
environment’s context.

##  VII Conclusion

In this paper, we introduced SeLRoS, a novel framework designed to enhance
room segmentation with semantic information. SeLRoS is designed with a modular
architecture, comprising geometric room segmentation, object mapping, and
semantic integration components. geometric room segmentation forms the
foundational layer of SeLRoS, where the 2D map extracted from the original
environment undergoes segmentation using the VRF algorithm. object mapping
then creates object information based on visual data obtained from the center
coordinates of each segmented room. semantic integration represents the
culmination of the entire process, where the segmented spaces are merged with
object information and spacial context information. This phase leverages LLMs
to interpret the contextual relationships between objects and spaces,
generating the semantic information that used to enhance segmentation map. To
evaluate the effectiveness of SeLRoS, we conducted extensive experiments
across 30 diverse environments generated by AI2-THOR, analyzing the results
through both qualitative and quantitative analysis. These experiments showed
the capabilities of SeLRoS in improving room segmentation accuracy by
leveraging semantic insights.

Despite its promising outcomes, our study has several limitations. Initially,
while SeLRoS can effectively integrate segmented rooms within the segmentation
map, it cannot divide spaces for more detailed refinement. This limitation
impacts the system’s ability to fine-tune room boundaries for improved
accuracy. Additionally, SeLRoS determines the center of each segmented room
using a scalar mean to collect visual data. Whether these central points best
capture the essence of each room requires further discussion and
investigation. Finally, using ProcTHOR from AI2-THOR to create indoor
environments sometimes presents challenges because the automatically generated
structures can be placed in unusual or mismatched contexts in a few cases.
These situations can make it hard for SeLRoS, which relies on understanding
the context, to add correct semantic information to the segmentation results.

Therefore, future research will aim to more systematically integrate
segmentation maps with a broader range of contextual information. This goal
will enhance the accuracy of both semantic information and segmentation maps,
resulting in a more precise representation of indoor environments.

## References

  * [1] P. Anderson, Q. Wu, D. Teney, J. Bruce, M. Johnson, N. Sünderhauf, I. Reid, S. Gould, and A. Van Den Hengel, “Vision-and-language navigation: Interpreting visually-grounded navigation instructions in real environments,” in _Proceedings of the IEEE conference on computer vision and pattern recognition_ , 2018, pp. 3674–3683.
  * [2] F. Zhu, Y. Zhu, X. Chang, and X. Liang, “Vision-language navigation with self-supervised auxiliary reasoning tasks,” in _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_ , 2020, pp. 10 012–10 022.
  * [3] M. Murray and M. Cakmak, “Following natural language instructions for household tasks with landmark guided search and reinforced pose adjustment,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 3, pp. 6870–6877, 2022.
  * [4] Y. Obinata, K. Kawaharazuka, N. Kanazawa, N. Yamaguchi, N. Tsukamoto, I. Yanokura, S. Kitagawa, K. Shinjo, K. Okada, and M. Inaba, “Semantic scene difference detection in daily life patroling by mobile robots using pre-trained large-scale vision-language model,” in _2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2023, pp. 3228–3233.
  * [5] R. Bormann, F. Jordan, W. Li, J. Hampp, and M. Hägele, “Room segmentation: Survey, implementation, and analysis,” in _2016 IEEE international conference on robotics and automation (ICRA)_. IEEE, 2016, pp. 1019–1026.
  * [6] M. Luperto, T. P. Kucner, A. Tassi, M. Magnusson, and F. Amigoni, “Robust structure identification and room segmentation of cluttered indoor environments from occupancy grid maps,” _IEEE Robotics and Automation Letters_ , vol. 7, no. 3, pp. 7974–7981, 2022.
  * [7] Z. He, J. Hou, and S. Schwertfeger, “Furniture free mapping using 3d lidars,” in _2019 IEEE International Conference on Robotics and Biomimetics (ROBIO)_ , 2019, pp. 583–589.
  * [8] M. Mielle, M. Magnusson, and A. J. Lilienthal, “A method to segment maps from different modalities using free space layout maoris: Map of ripples segmentation,” in _2018 IEEE International Conference on Robotics and Automation (ICRA)_ , 2018, pp. 4993–4999.
  * [9] R. Ambruş, S. Claici, and A. Wendt, “Automatic room segmentation from unstructured 3-d data of indoor environments,” _IEEE Robotics and Automation Letters_ , vol. 2, no. 2, pp. 749–756, 2017.
  * [10] D. Bobkov, M. Kiechle, S. Hilsenbeck, and E. Steinbach, “Room segmentation in 3d point clouds using anisotropic potential fields,” in _2017 IEEE International Conference on Multimedia and Expo (ICME)_ , 2017, pp. 727–732.
  * [11] M. Afif, R. Ayachi, Y. Said, and M. Atri, “Deep learning based application for indoor scene recognition,” _Neural Processing Letters_ , vol. 51, pp. 2827–2837, 2020.
  * [12] A. Basu, L. Petropoulakis, G. Di Caterina, and J. Soraghan, “Indoor home scene recognition using capsule neural networks,” _Procedia Computer Science_ , vol. 167, pp. 440–448, 2020.
  * [13] S. Huang, M. Usvyatsov, and K. Schindler, “Indoor scene recognition in 3d,” in _2020 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_ , 2020, pp. 8041–8048.
  * [14] L. Zhou, J. Cen, X. Wang, Z. Sun, T. L. Lam, and Y. Xu, “Borm: Bayesian object relation model for indoor scene recognition,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 39–46.
  * [15] B. Miao, L. Zhou, A. S. Mian, T. L. Lam, and Y. Xu, “Object-to-scene: Learning to transfer object knowledge to indoor scene recognition,” in _2021 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS)_. IEEE, 2021, pp. 2069–2075.
  * [16] B. A. Labinghisa and D. M. Lee, “Indoor localization system using deep learning based scene recognition,” _Multimedia Tools and Applications_ , vol. 81, no. 20, pp. 28 405–28 429, 2022.
  * [17] J. Wu, R. Antonova, A. Kan, M. Lepert, A. Zeng, S. Song, J. Bohg, S. Rusinkiewicz, and T. Funkhouser, “Tidybot: Personalized robot assistance with large language models,” _arXiv preprint arXiv:2305.05658_ , 2023.
  * [18] B. Zhang and H. Soh, “Large language models as zero-shot human models for human-robot interaction,” _arXiv preprint arXiv:2303.03548_ , 2023.
  * [19] Y. Ding, X. Zhang, C. Paxton, and S. Zhang, “Task and motion planning with large language models for object rearrangement,” _arXiv preprint arXiv:2303.06247_ , 2023.
  * [20] S. Vemprala, R. Bonatti, A. Bucker, and A. Kapoor, “Chatgpt for robotics: Design principles and model abilities,” _Microsoft Auton. Syst. Robot. Res_ , vol. 2, p. 20, 2023.
  * [21] I. Singh, V. Blukis, A. Mousavian, A. Goyal, D. Xu, J. Tremblay, D. Fox, J. Thomason, and A. Garg, “Progprompt: Generating situated robot task plans using large language models,” in _2023 IEEE International Conference on Robotics and Automation (ICRA)_. IEEE, 2023, pp. 11 523–11 530.
  * [22] Y.-J. Wang, B. Zhang, J. Chen, and K. Sreenath, “Prompt a robot to walk with large language models,” _ArXiv_ , vol. abs/2309.09969, 2023.
  * [23] Y. Cao and C. G. Lee, “Ground manipulator primitive tasks to executable actions using large language models,” in _Proceedings of the AAAI Symposium Series_ , vol. 2, no. 1, 2023, pp. 502–507.
  * [24] D. Shah, M. R. Equi, B. Osiński, F. Xia, B. Ichter, and S. Levine, “Navigation with large language models: Semantic guesswork as a heuristic for planning,” in _Conference on Robot Learning_. PMLR, 2023, pp. 2683–2699.
  * [25] T. Yu, T. Xiao, A. Stone, J. Tompson, A. Brohan, S. Wang, J. Singh, C. Tan, D. M, J. Peralta, B. Ichter, K. Hausman, and F. Xia, “Scaling robot learning with semantically imagined experience,” in _arXiv preprint arXiv:2302.11550_ , 2023.
  * [26] B. Yu, H. Kasaei, and M. Cao, “L3mvn: Leveraging large language models for visual target navigation,” _arXiv preprint arXiv:2304.05501_ , 2023.
  * [27] S. Friedman, H. Pasula, and D. Fox, “Voronoi random fields: Extracting topological structure of indoor environments via place labeling.” in _IJCAI_ , vol. 7, 2007, pp. 2109–2114.
  * [28] X. Zhou, R. Girdhar, A. Joulin, P. Krähenbühl, and I. Misra, “Detecting twenty-thousand classes using image-level supervision,” in _ECCV_ , 2022.
  * [29] G. Kim, T. Kim, S. S. Kannan, V. L. Venkatesh, D. Kim, and B.-C. Min, “Dynacon: Dynamic robot planner with contextual awareness via llms,” _arXiv preprint arXiv:2309.16031_ , 2023.
  * [30] J. Wei, X. Wang, D. Schuurmans, M. Bosma, F. Xia, E. Chi, Q. V. Le, D. Zhou, _et al._ , “Chain-of-thought prompting elicits reasoning in large language models,” _Advances in Neural Information Processing Systems_ , vol. 35, pp. 24 824–24 837, 2022.
  * [31] M. Deitke, E. VanderBilt, A. Herrasti, L. Weihs, J. Salvador, K. Ehsani, W. Han, E. Kolve, A. Farhadi, A. Kembhavi, and R. Mottaghi, “ProcTHOR: Large-Scale Embodied AI Using Procedural Generation,” in _NeurIPS_ , 2022, outstanding Paper Award.
  * [32] E. Kolve, R. Mottaghi, W. Han, E. VanderBilt, L. Weihs, A. Herrasti, D. Gordon, Y. Zhu, A. Gupta, and A. Farhadi, “AI2-THOR: An Interactive 3D Environment for Visual AI,” _arXiv_ , 2017.
  * [33] P. Buschka and A. Saffiotti, “A virtual sensor for room detection,” in _IEEE/RSJ international conference on intelligent robots and systems_ , vol. 1. IEEE, 2002, pp. 637–642.
  * [34] A. Diosi, G. Taylor, and L. Kleeman, “Interactive slam using laser and advanced sonar,” in _Proceedings of the 2005 IEEE International Conference on Robotics and Automation_. IEEE, 2005, pp. 1103–1108.
  * [35] S. Thrun, “Learning metric-topological maps for indoor mobile robot navigation,” _Artificial Intelligence_ , vol. 99, no. 1, pp. 21–71, 1998.
  * [36] Ultralytics, “YOLOv8: Real-time object detection,” https://github.com/ultralytics/ultralytics, 2023, accessed: 2024-02-28.
  * [37] Roboflow, “MIT Indoor Scene Recognition,” https://universe.roboflow.com/popular-benchmarks/mit-indoor-scene-recognition/dataset/5, Oct 2022, accessed: 2024-02-28.