Predicting the global structure of indoor environments: A constructive machine learning approach

Consider a mobile robot exploring an initially unknown school building and assume that it has already discovered some corridors, classrooms, offices, and bathrooms. What can the robot infer about the presence and the locations of other classrooms and offices and, more generally, about the structure of the rest of the building? This paper presents a system that makes a step towards providing an answer to the above question. The proposed system is based on a generative model that is able to represent the topological structures and the semantic labeling schemas of buildings and to generate plausible hypotheses for unvisited portions of these environments. We represent the buildings as undirected graphs, whose nodes are rooms and edges are physical connections between them. Given an initial knowledge base of graphs, our approach, relying on constructive machine learning techniques, segments each graph for finding significant subgraphs and clusters them according to their similarity, which is measured using graph kernels. A graph representing a new building or an unvisited part of a building is eventually generated by sampling subgraphs from clusters and connecting them.

1. Code is available at: https://github.com/goldleaf3i/generativeCMLgraphs.

Authors gratefully thank Modestino Cucciniello and Mattia Di Vitto for their contributions to the implementation of the system presented in this paper.

Authors and Affiliations

1. Artificial Intelligence and Robotics Laboratory, Politecnico di Milano, Piazza Leonardo da Vinci 32, 20133, Milano, Italy

   Matteo Luperto & Francesco Amigoni

Corresponding author

Correspondence to Matteo Luperto.

Appendix: graph kernels

The task of learning a model of structured data like graphs, as we do in this paper, is often complex and requires ad hoc techniques since standard machine learning techniques cannot be naturally adopted due to the dimensionality of the data (De Raedt 2008). We make a substantial use of graph kernel methods, which use a decompositional approach to measure the similarity between two graphs. In this appendix we provide a general overview on the concept of graph kernel, as introduced by Haussler (1999), and we describe the graph kernels that we use in our method. Graph kernel methods are the equivalent for structured data of kernel methods (Gärtner et al. 2004), which are typically defined in a vectorial space. Among the graph kernel families, the general class of convolutional kernels proposed by Haussler (1999) represents the guiding principle in kernel design for structured objects (Costa and De Grave 2010; Gärtner et al. 2004). Convolutional kernels are based on the idea that the structure of a graph can be captured by a relation R between the graph and its parts. A graph kernel is then defined as a composition of kernels defined on different parts of the graph.

Let \(G=(N,E)\in \mathcal {G}\) be a graph and \(\{g_1, \ldots , g_D\}\) one of its decompositions into (possibly overlapping) parts (subgraphs). Each part \(g_d\) in an element of a countable set \(G_d\), for \(d=1,\ldots ,D\), \(D \ge 1\). Consider a relation R defined on \(G_1 \times \cdots \times G_D \times \mathcal {G}\), where \(R(g_1,\ldots ,g_D,G)\) is true if the set \(\{g_1,g_2,\ldots ,g_D\}\) is one of the possible sets of the parts (subgraphs) of G (i.e., in which G can be decomposed). Given R, we can define the function \(R^{-1}\) as the decomposition function which returns the sets of parts (decompositions) of G: \(R^{-1}(G) = \{ g_1,\ldots ,g_D : R(g_1,\ldots ,g_D,G) \}\). Consider now any positive definite kernel function \(K_d\) over \(G_d \times G_d\), \(d=1,\ldots ,D\). For two graphs \(G, Q \in \mathcal {G}\), we can define a convolutional or decomposition kernel on graphs as the function:

Given a generic graph kernel K, the similarity measure between two graphs \(G,Q \in \mathcal {G}\) can be defined as the normalized version of the graph kernel:

In this work we use two instances of convolutional graph kernels: the Weisfeiler-Lehman Subtree Kernel (\(K_{\textit{WL}}\)) (Shervashidze et al. 2011) and the Graph Hopper Kernel (\(K_{\textit{GH}}\)) (Feragen et al. 2013). Several other kernels, such as those by Costa and De Grave (2010), Menchetti et al. (2005), and Kashima et al. (2003) have been empirically tested with less convincing results (numerical results are not reported here).

An example of a \(d=2\) subtree rooted from node 1

Full size image

The \(K_{\textit{WL}}\) belongs to the family of Weisfeiler-Lehman graph kernels (Shervashidze et al. 2011), that exploit the Weisfeiler-Lehman test of isomorphism on graphs as a rapid feature extraction scheme. \(K_{\textit{WL}}\) is implemented as an iterative procedure in which, at each iteration, the node labels are augmented by concatenating to the current label of each node the sorted list of labels of its adjacent nodes. The resulting augmented label list is then compressed into a new, shorter label list using an hash function. Each graph G is thus mapped to a sequence of graphs \(\{ G_0,G_1,\ldots ,G_h\} = \{(N,E,L_0),(N,E,L_1), \ldots ,(N,E,L_h)\}\), where \(G_i\) and \(L_i\) are the graph and the label set (one label per node) after i iterations of the algorithm, respectively, and h is the total number of iterations. Given any graph kernel \(K_b\) called base kernel, \(K_{\textit{WL}}\) is then computed as:

In our setting we use as base kernel \(K_b(G_i,Q_i)\) a subtree kernel. It computes all the rooted subtrees of \(G=(N,E)\) (a rooted subtree is an acyclic sub-graph of G with a given depth d and rooted on a node \(n \in N\), where nodes \(n'\in N\) can be repeated in different branches of the tree; an example of a rooted subtree is shown in Fig. 14). These rooted subtrees are the outcome of the decomposition \(R^{-1}\). For each iteration i, \(i=1, \ldots , h\), \(K_b\) counts the number of common labels between all the subtrees of \(G_i\) and \(Q_i\) rooted in two nodes with the same label \(l^* \in L_i\). The complexity of \(K_{\textit{WL}}\) when applied to a set of N graphs is \(O(Nhm+N^2hn)\), where N is the total number of graphs, and n and m are the number of nodes and edges of the graphs respectively (assumed equal for all graphs for simplicity).

In \(K_{\textit{GH}}\) (Feragen et al. 2013), the decomposition relation \(R^{-1}\) is based on the shortest path between each pair of nodes:

where \(k_p\) is a kernel defined on paths and \(\mathcal {P}\) and \(\mathcal {P}^{'}\) are the sets of shortest paths between all pairs of nodes of G and Q, respectively. The path-kernel \(k_p\) is defined on two paths \(\pi \) and \(\pi '\) as:

where \(\pi (i) = n_i\) indicates the i-th node in the path \(\pi = (n_1,\ldots , n_{|\pi |})\). We use a linear node kernel \(k_n(n_i,n_j)\) that returns 1 if \(n_i\) and \(n_j\) have the same label and 0 otherwise. Total complexity of \(K_{\textit{GH}}\) is \(O(N^2(n^2(m+\log n + d + \delta ^2)))\) where N, n, and m are defined as in \(K_{\textit{WL}}\), \(\delta \) is the length of the longest shortest path, and d is a constant.

Reprints and permissions